[IVUsers] Check for preheader instead of loop simplify form

[nikic]

Summary

IVUsers currently makes sure that all loops dominating a user are in loop simplify form, because SCEVExpander needs a preheader to insert into. However, loop simplify form requires much more than that. In particular, it requires dedicated exits, which means that exits need to be found and walked. For large functions with many nested loops, this can result in pathological compile-time explosion.

Fix this by only checking the property we're actually interested in, which is incidentally cheap to check.

[nikic]

llvm/lib/Analysis/IVUsers.cpp

107

This is the only functional change in the patch, the rest is just renames.

[mkazantsev]

Looks fair. Just curious, what's the CT impact?

[reames]

LGTM from me as well.

Glancing through the SCEVExpander code, I only see one unconditional use of a preheader assumption, and that looks easy to bail out of. Are you sure we need this restriction at all? (Landing this and then investigating is encouraged.)

[nikic]

In D111493#3054181, @mkazantsev wrote:

Looks fair. Just curious, what's the CT impact?

For the average case this is only a small improvement: https://llvm-compile-time-tracker.com/compare.php?from=943b3048484b7e3cf04f4d51c23c82fcece2185d&to=272c643a5149425ef577312ae494e726c8b15d9e&stat=instructions

For the pathological case I was looking at compile-time for LSR drops to 40s from previously [unknown but at least 10 minutes].

In D111493#3055286, @reames wrote:

Glancing through the SCEVExpander code, I only see one unconditional use of a preheader assumption, and that looks easy to bail out of. Are you sure we need this restriction at all? (Landing this and then investigating is encouraged.)

Not sure, but I think the difference to those other usages is that they are only used for optimization, i.e. for basic LICM during expansion. For addrecs having no preheader can make expansion impossible. I guess one would have to check that in isSafeToExpand() instead?

llvm/lib/Analysis/IVUsers.cpp

for (const auto *Op : Add->operands())
       }
     return AnyInterestingYet;
   }
 
   // Nothing else is interesting here.
   return false;
 }
 
-/// Return true if all loop headers that dominate this block are in simplified
-/// form.
-static bool isSimplifiedLoopNest(BasicBlock *BB, const DominatorTree *DT,
-                                 const LoopInfo *LI,
-                                 SmallPtrSetImpl<Loop*> &SimpleLoopNests) {
+/// Return true if all loop headers that dominate this block have a preheader.
+static bool isPreheaderLoopNest(BasicBlock *BB, const DominatorTree *DT,
+                                SmallPtrSetImpl<Loop*> &PreheaderLoopNests) {
   Loop *NearestLoop = nullptr;
   for (DomTreeNode *Rung = DT->getNode(BB);
        Rung; Rung = Rung->getIDom()) {
     BasicBlock *DomBB = Rung->getBlock();
     Loop *DomLoop = LI->getLoopFor(DomBB);
     if (DomLoop && DomLoop->getHeader() == DomBB) {
       // If we have already checked this loop nest, stop checking.
-      if (SimpleLoopNests.count(DomLoop))
+      if (PreheaderLoopNests.count(DomLoop))
         break;
       // If the domtree walk reaches a loop with no preheader, return false.
-      if (!DomLoop->isLoopSimplifyForm())
+      if (!DomLoop->getLoopPreheader())
         return false;
       // If we have not already checked this loop nest, remember the loop
       // header nearest to BB. The nearest loop may not contain BB.
       if (!NearestLoop)
         NearestLoop = DomLoop;
     }
   }
   if (NearestLoop)
-    SimpleLoopNests.insert(NearestLoop);
+    PreheaderLoopNests.insert(NearestLoop);
   return true;
 }
 
 /// IVUseShouldUsePostIncValue - We have discovered a "User" of an IV expression
 /// and now we need to decide whether the user should use the preinc or post-inc
 /// value.  If this user should use the post-inc version of the IV, return true.
 ///
 /// Choosing wrong here can break dominance properties (if we choose to use the
static bool IVUseShouldUsePostIncValue(Instruction *User, Value *Operand,
   // dominated by the latch block.  Use the post-incremented value.
   return true;
 }
 
 /// AddUsersImpl - Inspect the specified instruction.  If it is a
 /// reducible SCEV, recursively add its users to the IVUsesByStride set and
 /// return true.  Otherwise, return false.
 bool IVUsers::AddUsersImpl(Instruction *I,
-                           SmallPtrSetImpl<Loop*> &SimpleLoopNests) {
+                           SmallPtrSetImpl<Loop*> &PreheaderLoopNests) {
   const DataLayout &DL = I->getModule()->getDataLayout();
 
   // Add this IV user to the Processed set before returning false to ensure that
   // all IV users are members of the set. See IVUsers::isIVUserOrOperand.
   if (!Processed.insert(I).second)
     return true;    // Instruction already handled.
 
   if (!SE->isSCEVable(I->getType()))
for (Use &U : I->uses()) {
     // headers. Otherwise, SCEVExpander will crash.
     BasicBlock *UseBB = User->getParent();
     // A phi's use is live out of its predecessor block.
     if (PHINode *PHI = dyn_cast<PHINode>(User)) {
       unsigned OperandNo = U.getOperandNo();
       unsigned ValNo = PHINode::getIncomingValueNumForOperand(OperandNo);
       UseBB = PHI->getIncomingBlock(ValNo);
     }
-    if (!isSimplifiedLoopNest(UseBB, DT, LI, SimpleLoopNests))
+    if (!isPreheaderLoopNest(UseBB, DT, LI, PreheaderLoopNests))
       return false;
 
     // Descend recursively, but not into PHI nodes outside the current loop.
     // It's important to see the entire expression outside the loop to get
     // choices that depend on addressing mode use right, although we won't
     // consider references outside the loop in all cases.
     // If User is already in Processed, we don't want to recurse into it again,
     // but do want to record a second reference in the same instruction.
     bool AddUserToIVUsers = false;
     if (LI->getLoopFor(User->getParent()) != L) {
       if (isa<PHINode>(User) || Processed.count(User) ||
-          !AddUsersImpl(User, SimpleLoopNests)) {
+          !AddUsersImpl(User, PreheaderLoopNests)) {
         LLVM_DEBUG(dbgs() << "FOUND USER in other loop: " << *User << '\n'
                           << "   OF SCEV: " << *ISE << '\n');
         AddUserToIVUsers = true;
       }
-    } else if (Processed.count(User) || !AddUsersImpl(User, SimpleLoopNests)) {
+    } else if (Processed.count(User) ||
+               !AddUsersImpl(User, PreheaderLoopNests)) {
       LLVM_DEBUG(dbgs() << "FOUND USER: " << *User << '\n'
                         << "   OF SCEV: " << *ISE << '\n');
       AddUserToIVUsers = true;
     }
 
     if (AddUserToIVUsers) {
       // Okay, we found a user that we cannot reduce.
       IVStrideUse &NewUse = AddUser(User, I);
if (AddUserToIVUsers) {
       LLVM_DEBUG(if (SE->getSCEV(I) != ISE) dbgs()
                  << "   NORMALIZED TO: " << *ISE << '\n');
     }
   }
   return true;
 }
 
 bool IVUsers::AddUsersIfInteresting(Instruction *I) {
-  // SCEVExpander can only handle users that are dominated by simplified loop
-  // entries. Keep track of all loops that are only dominated by other simple
+  // SCEVExpander can only handle users that are dominated by loops with
+  // preheaders. Keep track of all loops that are only dominated by preheader
   // loops so we don't traverse the domtree for each user.
-  SmallPtrSet<Loop*,16> SimpleLoopNests;
+  SmallPtrSet<Loop*,16> PreheaderLoopNests;
 
-  return AddUsersImpl(I, SimpleLoopNests);
+  return AddUsersImpl(I, PreheaderLoopNests);
 }
 
 IVStrideUse &IVUsers::AddUser(Instruction *User, Value *Operand) {
   IVUses.push_back(new IVStrideUse(this, User, Operand));
   return IVUses.back();
 }
 
 IVUsers::IVUsers(Loop *L, AssumptionCache *AC, LoopInfo *LI, DominatorTree *DT,