[CGP] Replace MaxMemoryUsesToScan cut-off with Use::moveToFrontOfUseList()

[rtereshin]

Summary

This is another take on PR33900: the patch replaces the cut-off based
fix introduced in r308891 with Use::moveToFrontOfUseList() calls
that keep memory uses resulting in early exits from FindAllMemoryUses
in the beginning of the use list, reducing the overall number of iterations
over the users.

The performance impact is measured on the Function.cpp from
PR33900 compiled with -O3:

Fix	# of iterations	CodeGenPrepare, s	Wall Time, s
No (r308891 reverted)	367,047,160	13.28	25.17
Before this patch	1,521,619	0.08	11.96
After this patch	76,733	0.05	11.71

where number of iterations is the number of iterations over the
users in the FindAllMemoryUses function only.

lib/CodeGen/CodeGenPrepare.cpp

if (OpInfo.CallOperandVal == OpVal &&
         (OpInfo.ConstraintType != TargetLowering::C_Memory ||
          !OpInfo.isIndirect))
       return false;
   }
 
   return true;
 }
 
-// Max number of memory uses to look at before aborting the search to conserve
-// compile time.
-static constexpr int MaxMemoryUsesToScan = 20;
-
 /// Recursively walk all the uses of I until we find a memory use.
 /// If we find an obviously non-foldable instruction, return true.
 /// Add the ultimately found memory instructions to MemoryUses.
 static bool FindAllMemoryUses(
     Instruction *I,
     SmallVectorImpl<std::pair<Instruction *, unsigned>> &MemoryUses,
     SmallPtrSetImpl<Instruction *> &ConsideredInsts, const TargetLowering &TLI,
-    const TargetRegisterInfo &TRI, int SeenInsts = 0) {
+    const TargetRegisterInfo &TRI) {
   // 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;
 
   const bool OptSize = I->getFunction()->optForSize();
 
   // 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++ >= MaxMemoryUsesToScan)
-      return true;
-
     Instruction *UserI = cast<Instruction>(U.getUser());
     if (LoadInst *LI = dyn_cast<LoadInst>(UserI)) {
       MemoryUses.push_back(std::make_pair(LI, U.getOperandNo()));
       continue;
     }
 
     if (StoreInst *SI = dyn_cast<StoreInst>(UserI)) {
       unsigned opNo = U.getOperandNo();
-      if (opNo != StoreInst::getPointerOperandIndex())
+      if (opNo != StoreInst::getPointerOperandIndex()) {
+        U.moveToFrontOfUseList();
         return true; // Storing addr, not into addr.
+      }
       MemoryUses.push_back(std::make_pair(SI, opNo));
       continue;
     }
 
     if (AtomicRMWInst *RMW = dyn_cast<AtomicRMWInst>(UserI)) {
       unsigned opNo = U.getOperandNo();
-      if (opNo != AtomicRMWInst::getPointerOperandIndex())
+      if (opNo != AtomicRMWInst::getPointerOperandIndex()) {
+        U.moveToFrontOfUseList();
         return true; // Storing addr, not into addr.
+      }
       MemoryUses.push_back(std::make_pair(RMW, opNo));
       continue;
     }
 
     if (AtomicCmpXchgInst *CmpX = dyn_cast<AtomicCmpXchgInst>(UserI)) {
       unsigned opNo = U.getOperandNo();
-      if (opNo != AtomicCmpXchgInst::getPointerOperandIndex())
+      if (opNo != AtomicCmpXchgInst::getPointerOperandIndex()) {
+        U.moveToFrontOfUseList();
         return true; // Storing addr, not into addr.
+      }
       MemoryUses.push_back(std::make_pair(CmpX, opNo));
       continue;
     }
 
     if (CallInst *CI = dyn_cast<CallInst>(UserI)) {
       // If this is a cold call, we can sink the addressing calculation into
       // the cold path.  See optimizeCallInst
       if (!OptSize && CI->hasFnAttr(Attribute::Cold))
         continue;
 
       InlineAsm *IA = dyn_cast<InlineAsm>(CI->getCalledValue());
-      if (!IA) return true;
+      if (!IA) {
+        U.moveToFrontOfUseList();
+        return true;
+      }
 
       // If this is a memory operand, we're cool, otherwise bail out.
-      if (!IsOperandAMemoryOperand(CI, IA, I, TLI, TRI))
+      if (!IsOperandAMemoryOperand(CI, IA, I, TLI, TRI)) {
+        U.moveToFrontOfUseList();
         return true;
+      }
       continue;
     }
 
-    if (FindAllMemoryUses(UserI, MemoryUses, ConsideredInsts, TLI, TRI,
-                          SeenInsts))
+    if (FindAllMemoryUses(UserI, MemoryUses, ConsideredInsts, TLI, TRI)) {
+      U.moveToFrontOfUseList();
       return true;
     }
+  }
 
   return false;
 }
 
 /// Return true if Val is already known to be live at the use site that we're
 /// folding it into. If so, there is no cost to include it in the addressing
 /// mode. KnownLive1 and KnownLive2 are two values that we know are live at the
 /// instruction already.