[NFC][CodeGenPrepare] Match against the correct instruction when checking profitability of folding an address

[chill]

Summary

The "nested" AddressingModeMatchers in
AddressingModeMatcher::isProfitableToFoldIntoAddressingMode are constructed
using the original memory instruction, even though they check whether the
address operand of a differrent memory instructon is foldable. The memory
instruction is used only for a dominance check (when not checking for
profitability), and using the wrong memory instruction does not change the
outcome of the test - if an address is foldable, the dominance test afects which
of the two possible ways to fold is chosen, but this result is discarded.

As an example, in

target triple = "x86_64-linux"

declare i1 @check(i64, i64)
define i32 @f(i1 %cc, ptr %p, ptr %q, i64 %n) {
entry:
  br label %loop

loop:
  %iv = phi i64 [ %i, %C ], [ 0, %entry ]
  %offs = mul i64 %iv, 4

  %c.0 = icmp  ult i64 %iv, %n
  br i1 %c.0, label %A, label %fail

A:
  br i1 %cc, label %B, label %C

C:
  %u = phi i32 [0, %A], [%w, %B]
  %i = add i64 %iv, 1
  %a.0 = getelementptr i8, ptr %p, i64 %offs
  %a.1 = getelementptr i8, ptr %a.0, i64 4
  %v = load i32, ptr %a.1
  %c.1 = icmp eq i32 %v, %u
  br i1 %c.1, label %exit, label %loop

B:
  %a.2 = getelementptr i8, ptr %p, i64 %offs
  %a.3 = getelementptr i8, ptr %a.2, i64 4
  %w = load i32, ptr %a.3
  br label %C

exit:
  ret i32 -1

fail:
   ret i32 0
}

the dominance test is perfomed between %i = ... and %v = ... at the moment
we're checking whether %a3 = ... is foldable

Using the memory instruction, which uses the interesting address is "more
correct" and this change is needed by a future patch.

[chill]

PIng?

[chill]

Ping?

[mkazantsev]

I think this is fine.

[chill]

Rebased to resolve a trivial merge conflict (int &SeenInsts vs. unsigned &SeenInsts)

llvm/lib/CodeGen/CodeGenPrepare.cpp

static bool IsOperandAMemoryOperand(CallInst *CI, InlineAsm *IA, Value *OpVal,
 
   return true;
 }
 
 /// Recursively walk all the uses of I until we find a memory use.
 /// If we find an obviously non-foldable instruction, return true.
 /// Add accessed addresses and types to MemoryUses.
 static bool FindAllMemoryUses(
-    Instruction *I, SmallVectorImpl<std::pair<Value *, Type *>> &MemoryUses,
+    Instruction *I, SmallVectorImpl<std::pair<Use *, Type *>> &MemoryUses,
     SmallPtrSetImpl<Instruction *> &ConsideredInsts, const TargetLowering &TLI,
     const TargetRegisterInfo &TRI, bool OptSize, ProfileSummaryInfo *PSI,
     BlockFrequencyInfo *BFI, unsigned &SeenInsts) {
   // If we already considered this instruction, we're done.
   if (!ConsideredInsts.insert(I).second)
     return false;
 
   // If this is an obviously unfoldable instruction, bail out.
   if (!MightBeFoldableInst(I))
     return true;
 
   // Loop over all the uses, recursively processing them.
   for (Use &U : I->uses()) {
     // Conservatively return true if we're seeing a large number or a deep chain
     // of users. This avoids excessive compilation times in pathological cases.
     if (SeenInsts++ >= MaxAddressUsersToScan)
       return true;
 
     Instruction *UserI = cast<Instruction>(U.getUser());
     if (LoadInst *LI = dyn_cast<LoadInst>(UserI)) {
-      MemoryUses.push_back({U.get(), LI->getType()});
+      MemoryUses.push_back({&U, LI->getType()});
       continue;
     }
 
     if (StoreInst *SI = dyn_cast<StoreInst>(UserI)) {
       if (U.getOperandNo() != StoreInst::getPointerOperandIndex())
         return true; // Storing addr, not into addr.
-      MemoryUses.push_back({U.get(), SI->getValueOperand()->getType()});
+      MemoryUses.push_back({&U, SI->getValueOperand()->getType()});
       continue;
     }
 
     if (AtomicRMWInst *RMW = dyn_cast<AtomicRMWInst>(UserI)) {
       if (U.getOperandNo() != AtomicRMWInst::getPointerOperandIndex())
         return true; // Storing addr, not into addr.
-      MemoryUses.push_back({U.get(), RMW->getValOperand()->getType()});
+      MemoryUses.push_back({&U, RMW->getValOperand()->getType()});
       continue;
     }
 
     if (AtomicCmpXchgInst *CmpX = dyn_cast<AtomicCmpXchgInst>(UserI)) {
       if (U.getOperandNo() != AtomicCmpXchgInst::getPointerOperandIndex())
         return true; // Storing addr, not into addr.
-      MemoryUses.push_back({U.get(), CmpX->getCompareOperand()->getType()});
+      MemoryUses.push_back({&U, CmpX->getCompareOperand()->getType()});
       continue;
     }
 
     if (CallInst *CI = dyn_cast<CallInst>(UserI)) {
       if (CI->hasFnAttr(Attribute::Cold)) {
         // If this is a cold call, we can sink the addressing calculation into
         // the cold path.  See optimizeCallInst
         bool OptForSize =
if (FindAllMemoryUses(UserI, MemoryUses, ConsideredInsts, TLI, TRI, OptSize,
                           PSI, BFI, SeenInsts))
       return true;
   }
 
   return false;
 }
 
 static bool FindAllMemoryUses(
-    Instruction *I, SmallVectorImpl<std::pair<Value *, Type *>> &MemoryUses,
+    Instruction *I, SmallVectorImpl<std::pair<Use *, Type *>> &MemoryUses,
     const TargetLowering &TLI, const TargetRegisterInfo &TRI, bool OptSize,
     ProfileSummaryInfo *PSI, BlockFrequencyInfo *BFI) {
   unsigned SeenInsts = 0;
   SmallPtrSet<Instruction *, 16> ConsideredInsts;
   return FindAllMemoryUses(I, MemoryUses, ConsideredInsts, TLI, TRI, OptSize,
                            PSI, BFI, SeenInsts);
 }
 
bool AddressingModeMatcher::isProfitableToFoldIntoAddressingMode(
   // ranges, we're ok with it.
   if (!BaseReg && !ScaledReg)
     return true;
 
   // If all uses of this instruction can have the address mode sunk into them,
   // we can remove the addressing mode and effectively trade one live register
   // for another (at worst.)  In this context, folding an addressing mode into
   // the use is just a particularly nice way of sinking it.
-  SmallVector<std::pair<Value *, Type *>, 16> MemoryUses;
+  SmallVector<std::pair<Use *, Type *>, 16> MemoryUses;
   if (FindAllMemoryUses(I, MemoryUses, TLI, TRI, OptSize, PSI, BFI))
     return false; // Has a non-memory, non-foldable use!
 
   // Now that we know that all uses of this instruction are part of a chain of
   // computation involving only operations that could theoretically be folded
   // into a memory use, loop over each of these memory operation uses and see
   // if they could  *actually* fold the instruction.  The assumption is that
   // addressing modes are cheap and that duplicating the computation involved
   // many times is worthwhile, even on a fastpath. For sinking candidates
   // (i.e. cold call sites), this serves as a way to prevent excessive code
   // growth since most architectures have some reasonable small and fast way to
   // compute an effective address.  (i.e LEA on x86)
   SmallVector<Instruction *, 32> MatchedAddrModeInsts;
-  for (const std::pair<Value *, Type *> &Pair : MemoryUses) {
-    Value *Address = Pair.first;
+  for (const std::pair<Use *, Type *> &Pair : MemoryUses) {
+    Value *Address = Pair.first->get();
+    Instruction *UserI = cast<Instruction>(Pair.first->getUser());
     Type *AddressAccessTy = Pair.second;
     unsigned AS = Address->getType()->getPointerAddressSpace();
 
     // Do a match against the root of this address, ignoring profitability. This
     // will tell us if the addressing mode for the memory operation will
     // *actually* cover the shared instruction.
     ExtAddrMode Result;
     std::pair<AssertingVH<GetElementPtrInst>, int64_t> LargeOffsetGEP(nullptr,
                                                                       0);
     TypePromotionTransaction::ConstRestorationPt LastKnownGood =
         TPT.getRestorationPoint();
     AddressingModeMatcher Matcher(MatchedAddrModeInsts, TLI, TRI, LI, getDTFn,
-                                  AddressAccessTy, AS, MemoryInst, Result,
+                                  AddressAccessTy, AS, UserI, Result,
                                   InsertedInsts, PromotedInsts, TPT,
                                   LargeOffsetGEP, OptSize, PSI, BFI);
     Matcher.IgnoreProfitability = true;
     bool Success = Matcher.matchAddr(Address, 0);
     (void)Success;
     assert(Success && "Couldn't select *anything*?");
 
     // The match was to check the profitability, the changes made are not