[STLExtras] Use return type from operator* of the wrapped iter.

[fhahn]

Summary

Currently make_early_inc_range cannot be used with iterators with
operator* implementations that do not return a reference.

Most notably in the LLVM codebase, this means the User iterator ranges
cannot be used with make_early_inc_range, which slightly simplifies
iterating over ranges while elements are removed.

Instead of directly using BaseT::reference as return type of operator*,
this patch uses decltype to get the actual return type of the operator*
implementation in WrappedIteratorT.

This patch also updates a few places to use make use of
make_early_inc_range.

[dblaikie]

Please add some test coverage to llvm/unittests/ADT/STLExtrasTest.cpp

[fhahn]

In D93992#2481098, @dblaikie wrote:

Please add some test coverage to llvm/unittests/ADT/STLExtrasTest.cpp

Done, I added a version of the existing test with a custom iterator that returns a pointer on dereference.

[dblaikie]

llvm/unittests/ADT/STLExtrasTest.cpp

458

std::iterator is deprecated - you could try using llvm::iterator_adaptor_base, it'll also simplify the implementation by providing default implementations of several operations required for the iterator concepts.

[fhahn]

simplified using iterator_adaptor_base, thanks!

[fhahn]

llvm/unittests/ADT/STLExtrasTest.cpp

458

Thanks, that indeed really simplifies the code :)

[dblaikie]

Looks good

[fhahn]

Great, thanks for taking a look and the very helpful comments!

llvm/include/llvm/ADT/STLExtras.h

 #if LLVM_ENABLE_ABI_BREAKING_CHECKS
   bool IsEarlyIncremented = false;
 #endif
 
 public:
   early_inc_iterator_impl(WrappedIteratorT I) : BaseT(I) {}
 
   using BaseT::operator*;
-  typename BaseT::reference operator*() {
+  decltype(*std::declval<WrappedIteratorT>()) operator*() {
 #if LLVM_ENABLE_ABI_BREAKING_CHECKS
     assert(!IsEarlyIncremented && "Cannot dereference twice!");
     IsEarlyIncremented = true;
 #endif
     return *(this->I)++;
   }
 
   using BaseT::operator++;

llvm/lib/Analysis/MemoryBuiltins.cpp

 PointerType *llvm::getMallocType(const CallInst *CI,
                                  const TargetLibraryInfo *TLI) {
   assert(isMallocLikeFn(CI, TLI) && "getMallocType and not malloc call");
 
   PointerType *MallocType = nullptr;
   unsigned NumOfBitCastUses = 0;
 
   // Determine if CallInst has a bitcast use.
-  for (Value::const_user_iterator UI = CI->user_begin(), E = CI->user_end();
-       UI != E;)
-    if (const BitCastInst *BCI = dyn_cast<BitCastInst>(*UI++)) {
+  for (const User *U : CI->users())
+    if (const BitCastInst *BCI = dyn_cast<BitCastInst>(U)) {
       MallocType = cast<PointerType>(BCI->getDestTy());
       NumOfBitCastUses++;
     }
 
   // Malloc call has 1 bitcast use, so type is the bitcast's destination type.
   if (NumOfBitCastUses == 1)
     return MallocType;
 

llvm/lib/IR/AutoUpgrade.cpp

void llvm::UpgradeCallsToIntrinsic(Function *F) {
   assert(F && "Illegal attempt to upgrade a non-existent intrinsic.");
 
   // Check if this function should be upgraded and get the replacement function
   // if there is one.
   Function *NewFn;
   if (UpgradeIntrinsicFunction(F, NewFn)) {
     // Replace all users of the old function with the new function or new
     // instructions. This is not a range loop because the call is deleted.
-    for (auto UI = F->user_begin(), UE = F->user_end(); UI != UE; )
-      if (CallInst *CI = dyn_cast<CallInst>(*UI++))
+    for (User *U : make_early_inc_range(F->users()))
+      if (CallInst *CI = dyn_cast<CallInst>(U))
         UpgradeIntrinsicCall(CI, NewFn);
 
     // Remove old function, no longer used, from the module.
     F->eraseFromParent();
   }
 }
 
 MDNode *llvm::UpgradeTBAANode(MDNode &MD) {
auto UpgradeToIntrinsic = [&](const char *OldFunc,
                                 llvm::Intrinsic::ID IntrinsicFunc) {
     Function *Fn = M.getFunction(OldFunc);
 
     if (!Fn)
       return;
 
     Function *NewFn = llvm::Intrinsic::getDeclaration(&M, IntrinsicFunc);
 
-    for (auto I = Fn->user_begin(), E = Fn->user_end(); I != E;) {
-      CallInst *CI = dyn_cast<CallInst>(*I++);
+    for (User *U : make_early_inc_range(Fn->users())) {
+      CallInst *CI = dyn_cast<CallInst>(U);
       if (!CI || CI->getCalledFunction() != Fn)
         continue;
 
       IRBuilder<> Builder(CI->getParent(), CI->getIterator());
       FunctionType *NewFuncTy = NewFn->getFunctionType();
       SmallVector<Value *, 2> Args;
 
       // Don't upgrade the intrinsic if it's not valid to bitcast the return

llvm/lib/Transforms/IPO/ArgumentPromotion.cpp

if (ByValArgsToTransform.count(&*I)) {
       ++NumArgumentsDead;
     } else {
       // Okay, this is being promoted. This means that the only uses are loads
       // or GEPs which are only used by loads
 
       // In this table, we will track which indices are loaded from the argument
       // (where direct loads are tracked as no indices).
       ScalarizeTable &ArgIndices = ScalarizedElements[&*I];
-      for (auto Iter = I->user_begin(), End = I->user_end(); Iter != End;) {
-        Instruction *UI = cast<Instruction>(*Iter++);
+      for (User *U : make_early_inc_range(I->users())) {
+        Instruction *UI = cast<Instruction>(U);
         Type *SrcTy;
         if (LoadInst *L = dyn_cast<LoadInst>(UI))
           SrcTy = L->getType();
         else
           SrcTy = cast<GetElementPtrInst>(UI)->getSourceElementType();
         // Skip dead GEPs and remove them.
         if (isa<GetElementPtrInst>(UI) && UI->use_empty()) {
           UI->eraseFromParent();

llvm/lib/Transforms/InstCombine/InstCombineCasts.cpp

Instruction *InstCombinerImpl::optimizeBitCastFromPhi(CastInst &CI,
   // If there is a store with type B, change it to type A.
 
 
   // Replace users of BitCast B->A with NewPHI. These will help
   // later to get rid off a closure formed by OldPHI nodes.
   Instruction *RetVal = nullptr;
   for (auto *OldPN : OldPhiNodes) {
     PHINode *NewPN = NewPNodes[OldPN];
-    for (auto It = OldPN->user_begin(), End = OldPN->user_end(); It != End; ) {
-      User *V = *It;
-      // We may remove this user, advance to avoid iterator invalidation.
-      ++It;
+    for (User *V : make_early_inc_range(OldPN->users())) {
       if (auto *SI = dyn_cast<StoreInst>(V)) {
         assert(SI->isSimple() && SI->getOperand(0) == OldPN);
         Builder.SetInsertPoint(SI);
         auto *NewBC =
           cast<BitCastInst>(Builder.CreateBitCast(NewPN, SrcTy));
         SI->setOperand(0, NewBC);
         Worklist.push(SI);
         assert(hasStoreUsersOnly(*NewBC));

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

static Instruction *processUMulZExtIdiom(ICmpInst &I, Value *MulVal,
   CallInst *Call = Builder.CreateCall(F, {MulA, MulB}, "umul");
   IC.addToWorklist(MulInstr);
 
   // If there are uses of mul result other than the comparison, we know that
   // they are truncation or binary AND. Change them to use result of
   // mul.with.overflow and adjust properly mask/size.
   if (MulVal->hasNUsesOrMore(2)) {
     Value *Mul = Builder.CreateExtractValue(Call, 0, "umul.value");
-    for (auto UI = MulVal->user_begin(), UE = MulVal->user_end(); UI != UE;) {
-      User *U = *UI++;
+    for (User *U : make_early_inc_range(MulVal->users())) {
       if (U == &I || U == OtherVal)
         continue;
       if (TruncInst *TI = dyn_cast<TruncInst>(U)) {
         if (TI->getType()->getPrimitiveSizeInBits() == MulWidth)
           IC.replaceInstUsesWith(*TI, Mul);
         else
           TI->setOperand(0, Mul);
       } else if (BinaryOperator *BO = dyn_cast<BinaryOperator>(U)) {

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

for (unsigned i = 0; i != NumPHIValues; ++i) {
         InV = ConstantExpr::getCast(CI->getOpcode(), InC, RetTy);
       else
         InV = Builder.CreateCast(CI->getOpcode(), PN->getIncomingValue(i),
                                  I.getType(), "phi.cast");
       NewPN->addIncoming(InV, PN->getIncomingBlock(i));
     }
   }
 
-  for (auto UI = PN->user_begin(), E = PN->user_end(); UI != E;) {
-    Instruction *User = cast<Instruction>(*UI++);
+  for (User *U : make_early_inc_range(PN->users())) {
+    Instruction *User = cast<Instruction>(U);
     if (User == &I) continue;
     replaceInstUsesWith(*User, NewPN);
     eraseInstFromFunction(*User);
   }
   return replaceInstUsesWith(I, NewPN);
 }
 
 Instruction *InstCombinerImpl::foldBinOpIntoSelectOrPhi(BinaryOperator &I) {

llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp

struct AllocaInfo {
   /// Scan the uses of the specified alloca, filling in the AllocaInfo used
   /// by the rest of the pass to reason about the uses of this alloca.
   void AnalyzeAlloca(AllocaInst *AI) {
     clear();
 
     // As we scan the uses of the alloca instruction, keep track of stores,
     // and decide whether all of the loads and stores to the alloca are within
     // the same basic block.
-    for (auto UI = AI->user_begin(), E = AI->user_end(); UI != E;) {
-      Instruction *User = cast<Instruction>(*UI++);
+    for (User *U : AI->users()) {
+      Instruction *User = cast<Instruction>(U);
 
       if (StoreInst *SI = dyn_cast<StoreInst>(User)) {
         // Remember the basic blocks which define new values for the alloca
         DefiningBlocks.push_back(SI->getParent());
         OnlyStore = SI;
       } else {
         LoadInst *LI = cast<LoadInst>(User);
         // Otherwise it must be a load instruction, keep track of variable
static bool rewriteSingleStoreAlloca(AllocaInst *AI, AllocaInfo &Info,
   StoreInst *OnlyStore = Info.OnlyStore;
   bool StoringGlobalVal = !isa<Instruction>(OnlyStore->getOperand(0));
   BasicBlock *StoreBB = OnlyStore->getParent();
   int StoreIndex = -1;
 
   // Clear out UsingBlocks.  We will reconstruct it here if needed.
   Info.UsingBlocks.clear();
 
-  for (auto UI = AI->user_begin(), E = AI->user_end(); UI != E;) {
-    Instruction *UserInst = cast<Instruction>(*UI++);
+  for (User *U : make_early_inc_range(AI->users())) {
+    Instruction *UserInst = cast<Instruction>(U);
     if (UserInst == OnlyStore)
       continue;
     LoadInst *LI = cast<LoadInst>(UserInst);
 
     // Okay, if we have a load from the alloca, we want to replace it with the
     // only value stored to the alloca.  We can do this if the value is
     // dominated by the store.  If not, we use the rest of the mem2reg machinery
     // to insert the phi nodes as needed.
if (StoreInst *SI = dyn_cast<StoreInst>(U))
       StoresByIndex.push_back(std::make_pair(LBI.getInstructionIndex(SI), SI));
 
   // Sort the stores by their index, making it efficient to do a lookup with a
   // binary search.
   llvm::sort(StoresByIndex, less_first());
 
   // Walk all of the loads from this alloca, replacing them with the nearest
   // store above them, if any.
-  for (auto UI = AI->user_begin(), E = AI->user_end(); UI != E;) {
-    LoadInst *LI = dyn_cast<LoadInst>(*UI++);
+  for (User *U : make_early_inc_range(AI->users())) {
+    LoadInst *LI = dyn_cast<LoadInst>(U);
     if (!LI)
       continue;
 
     unsigned LoadIdx = LBI.getInstructionIndex(LI);
 
     // Find the nearest store that has a lower index than this load.
     StoresByIndexTy::iterator I = llvm::lower_bound(
         StoresByIndex,

llvm/unittests/ADT/STLExtrasTest.cpp

#endif
   // Erasing the front including the current doesn't break incrementing.
   L.erase(L.begin(), std::prev(L.end()));
   ++I;
   EXPECT_EQ(4, *I);
   ++I;
   EXPECT_EQ(EIR.end(), I);
 }
 
+// A custom iterator that returns a pointer when dereferenced. This is used to
+// test make_early_inc_range with iterators that do not return a reference on
+// dereferencing.
+struct CustomPointerIterator
+    : public iterator_adaptor_base<CustomPointerIterator,
+                                   std::list<int>::iterator,
+                                   std::forward_iterator_tag> {
+  using base_type =
+      iterator_adaptor_base<CustomPointerIterator, std::list<int>::iterator,
+                            std::forward_iterator_tag>;
+
+  explicit CustomPointerIterator(std::list<int>::iterator I) : base_type(I) {}
+
+  // Retrieve a pointer to the current int.
+  int *operator*() const { return &*base_type::wrapped(); }
+};
+
+// Make sure make_early_inc_range works with iterators that do not return a
+// reference on dereferencing. The test is similar to EarlyIncrementTest, but
+// uses CustomPointerIterator.
+TEST(STLExtrasTest, EarlyIncrementTestCustomPointerIterator) {
+  std::list<int> L = {1, 2, 3, 4};
+
+  auto CustomRange = make_range(CustomPointerIterator(L.begin()),
+                                CustomPointerIterator(L.end()));
+  auto EIR = make_early_inc_range(CustomRange);
+
+  auto I = EIR.begin();
+  auto EI = EIR.end();
+  EXPECT_NE(I, EI);
+
+  EXPECT_EQ(&*L.begin(), *I);
+#if LLVM_ENABLE_ABI_BREAKING_CHECKS
+#ifndef NDEBUG
+  // Repeated dereferences are not allowed.
+  EXPECT_DEATH(*I, "Cannot dereference");
+  // Comparison after dereference is not allowed.
+  EXPECT_DEATH((void)(I == EI), "Cannot compare");
+  EXPECT_DEATH((void)(I != EI), "Cannot compare");
+#endif
+#endif
+
+  ++I;
+  EXPECT_NE(I, EI);
+#if LLVM_ENABLE_ABI_BREAKING_CHECKS
+#ifndef NDEBUG
+  // You cannot increment prior to dereference.
+  EXPECT_DEATH(++I, "Cannot increment");
+#endif
+#endif
+  EXPECT_EQ(&*std::next(L.begin()), *I);
+#if LLVM_ENABLE_ABI_BREAKING_CHECKS
+#ifndef NDEBUG
+  // Repeated dereferences are not allowed.
+  EXPECT_DEATH(*I, "Cannot dereference");
+#endif
+#endif
+
+  // Inserting shouldn't break anything. We should be able to keep dereferencing
+  // the currrent iterator and increment. The increment to go to the "next"
+  // iterator from before we inserted.
+  L.insert(std::next(L.begin(), 2), -1);
+  ++I;
+  EXPECT_EQ(&*std::next(L.begin(), 3), *I);
+
+  // Erasing the front including the current doesn't break incrementing.
+  L.erase(L.begin(), std::prev(L.end()));
+  ++I;
+  EXPECT_EQ(&*L.begin(), *I);
+  ++I;
+  EXPECT_EQ(EIR.end(), I);
+}
+
 TEST(STLExtrasTest, splat) {
   std::vector<int> V;
   EXPECT_FALSE(is_splat(V));
 
   V.push_back(1);
   EXPECT_TRUE(is_splat(V));
 
   V.push_back(1);