[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 ↗

(On Diff #32047)

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

1890 ↗

(On Diff #32047)

Typo here?

1898 ↗

(On Diff #32047)

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

[igor-laevsky]

lib/Analysis/ScalarEvolutionExpander.cpp

1819 ↗

(On Diff #32047)

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 ↗

(On Diff #32047)

Ok.

llvm/trunk/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 *UDivExpr = dyn_cast<SCEVUDivExpr>(S)) {
     // 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
     // compute.
     BasicBlock *ExitingBB = L->getExitingBlock();
     if (!ExitingBB)
       return true;
 
-    BranchInst *ExitingBI = dyn_cast<BranchInst>(ExitingBB->getTerminator());
-    if (!ExitingBI || !ExitingBI->isConditional())
+    // At the beginning of this function we already tried to find existing value
+    // for plain 'S'. Now try to lookup 'S + 1' since it is common pattern
+    // involving division. This is just a 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