[ScalarEvolutionExpander] Refactor isHighCostExpansionHelper division case

[igor-laevsky]

Summary

This is follow up after http://reviews.llvm.org/D11687

In SCEVUDivExpr case inside isHighCostExpansionHelper we had lookup code which was almost exactly same as code inside findExistingExpansion. Refactor it to make use of the existing function.

[sanjoy]

lib/Analysis/ScalarEvolutionExpander.cpp

1819

Latches are not exiting blocks, so this is a semantic change. Perhaps this should be iterating over both exits and latches?

1890

Typo here?

1898

Nit: "This is just a simple search heuristic."

[igor-laevsky]

lib/Analysis/ScalarEvolutionExpander.cpp

1819

Right. However this heuristic is based on the fact that we are looking at the loop exit conditions. All latches which exit loop should be listed in the ExitingBlocks. So the overall heuristic stays roughly the same. I probably shouldn't call this change purely a refactoring though.

If you think that it is important to visit non-exiting latches it would be easy to add them into lookup list. It's just small amount of additional complexity which I don't see real need for.

[sanjoy]

LGTM, but please mention something along the lines of

"However this heuristic is based on the fact that we are looking at the loop exit conditions. All latches which exit loop should be listed in the ExitingBlocks. So the overall heuristic stays roughly the same."

in the commit message.

lib/Analysis/ScalarEvolutionExpander.cpp

1819

Ok.

lib/Analysis/ScalarEvolutionExpander.cpp

unsigned SCEVExpander::replaceCongruentIVs(Loop *L, const DominatorTree *DT,
   }
   return NumElim;
 }
 
 Value *SCEVExpander::findExistingExpansion(const SCEV *S,
                                            const Instruction *At, Loop *L) {
   using namespace llvm::PatternMatch;
 
-  SmallVector<BasicBlock *, 4> Latches;
-  L->getLoopLatches(Latches);
+  SmallVector<BasicBlock *, 4> ExitingBlocks;
+  L->getExitingBlocks(ExitingBlocks);
 
-  // Look for suitable value in simple conditions at the loop latches.
-  for (BasicBlock *BB : Latches) {
+  // Look for suitable value in simple conditions at the loop exits.
+  for (BasicBlock *BB : ExitingBlocks) {
     ICmpInst::Predicate Pred;
     Instruction *LHS, *RHS;
     BasicBlock *TrueBB, *FalseBB;
 
     if (!match(BB->getTerminator(),
                m_Br(m_ICmp(Pred, m_Instruction(LHS), m_Instruction(RHS)),
                     TrueBB, FalseBB)))
       continue;
if (auto *SC = dyn_cast<SCEVConstant>(UDivExpr->getRHS()))
             L->getHeader()->getParent()->getParent()->getDataLayout();
         unsigned Width = cast<IntegerType>(UDivExpr->getType())->getBitWidth();
         return DL.isIllegalInteger(Width);
       }
 
     // UDivExpr is very likely a UDiv that ScalarEvolution's HowFarToZero or
     // HowManyLessThans produced to compute a precise expression, rather than a
     // UDiv from the user's code. If we can't find a UDiv in the code with some
-    // simple searching, assume the former consider UDivExpr expensive to
+    // simple searaching, assume the former consider UDivExpr expensive to
     // compute.
     BasicBlock *ExitingBB = L->getExitingBlock();
     if (!ExitingBB)
       return true;
 
-    BranchInst *ExitingBI = dyn_cast<BranchInst>(ExitingBB->getTerminator());
-    if (!ExitingBI || !ExitingBI->isConditional())
+    // We already tried to find existing value for plain 'S' at the beginning of
+    // this function. Now try to lookup 'S + 1' as it is common pattern
+    // involving division. This is just simple search heuristic.
+    if (!At)
+      At = &ExitingBB->back();
+    if (!findExistingExpansion(
+            SE.getAddExpr(S, SE.getConstant(S->getType(), 1)), At, L))
       return true;
-
-    ICmpInst *OrigCond = dyn_cast<ICmpInst>(ExitingBI->getCondition());
-    if (!OrigCond)
-      return true;
-
-    const SCEV *RHS = SE.getSCEV(OrigCond->getOperand(1));
-    RHS = SE.getMinusSCEV(RHS, SE.getConstant(RHS->getType(), 1));
-    if (RHS != S) {
-      const SCEV *LHS = SE.getSCEV(OrigCond->getOperand(0));
-      LHS = SE.getMinusSCEV(LHS, SE.getConstant(LHS->getType(), 1));
-      if (LHS != S)
-        return true;
-    }
   }
 
   // HowManyLessThans uses a Max expression whenever the loop is not guarded by
   // the exit condition.
   if (isa<SCEVSMaxExpr>(S) || isa<SCEVUMaxExpr>(S))
     return true;
 
   // Recurse past nary expressions, which commonly occur in the