From dcf748827b3d1b243cf36a62efc763ebd9d5ca44 Mon Sep 17 00:00:00 2001 From: Igor Laevsky Date: Mon, 17 Aug 2015 16:37:04 +0000 Subject: [PATCH] [ScalarEvolutionExpander] Reuse findExistingExpansion during expansion cost calculation for division Primary purpose of this change is to reuse existing code inside findExistingExpansion. However it introduces very slight semantic change - findExistingExpansion now looks into exiting blocks instead of a loop latches. Originally heuristic was based on the fact that we want to look at the loop exit conditions. And since all exiting latches will be listed in the ExitingBlocks, heuristic stays roughly the same. Differential Revision: http://reviews.llvm.org/D12008 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@245227 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Analysis/ScalarEvolutionExpander.cpp | 30 +++++++++--------------- 1 file changed, 11 insertions(+), 19 deletions(-) diff --git a/lib/Analysis/ScalarEvolutionExpander.cpp b/lib/Analysis/ScalarEvolutionExpander.cpp index d0b36431130..ed7386b26f8 100644 --- a/lib/Analysis/ScalarEvolutionExpander.cpp +++ b/lib/Analysis/ScalarEvolutionExpander.cpp @@ -1815,11 +1815,11 @@ Value *SCEVExpander::findExistingExpansion(const SCEV *S, const Instruction *At, Loop *L) { using namespace llvm::PatternMatch; - SmallVector Latches; - L->getLoopLatches(Latches); + SmallVector 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; @@ -1892,22 +1892,14 @@ bool SCEVExpander::isHighCostExpansionHelper( if (!ExitingBB) return true; - BranchInst *ExitingBI = dyn_cast(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(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 -- 2.34.1