Index: include/llvm/Analysis/ScalarEvolutionExpander.h =================================================================== --- include/llvm/Analysis/ScalarEvolutionExpander.h +++ include/llvm/Analysis/ScalarEvolutionExpander.h @@ -116,6 +116,13 @@ ChainedPhis.clear(); } + /// isHighCostExpansion - Return true for expressions that may incur + /// non-trivial cost to evaluate at runtime. + bool isHighCostExpansion(const SCEV *Expr, Loop *L) { + SmallPtrSet Processed; + return isHighCostExpansionHelper(Expr, L, Processed); + } + /// getOrInsertCanonicalInductionVariable - This method returns the /// canonical induction variable of the specified type for the specified /// loop (inserting one if there is none). A canonical induction variable @@ -192,6 +199,11 @@ private: LLVMContext &getContext() const { return SE.getContext(); } + /// isHighCostExpansionHelper - Recursive helper function for + /// isHighCostExpansion. + bool isHighCostExpansionHelper(const SCEV *S, Loop *L, + SmallPtrSetImpl &Processed); + /// InsertBinop - Insert the specified binary operator, doing a small amount /// of work to avoid inserting an obviously redundant operation. Value *InsertBinop(Instruction::BinaryOps Opcode, Value *LHS, Value *RHS); Index: lib/Analysis/ScalarEvolutionExpander.cpp =================================================================== --- lib/Analysis/ScalarEvolutionExpander.cpp +++ lib/Analysis/ScalarEvolutionExpander.cpp @@ -23,6 +23,7 @@ #include "llvm/IR/Dominators.h" #include "llvm/IR/IntrinsicInst.h" #include "llvm/IR/LLVMContext.h" +#include "llvm/IR/Module.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" @@ -1804,6 +1805,72 @@ return NumElim; } +bool SCEVExpander::isHighCostExpansionHelper( + const SCEV *S, Loop *L, SmallPtrSetImpl &Processed) { + if (!Processed.insert(S).second) + return false; + + if (auto *UDivExpr = dyn_cast(S)) { + // If the divisor is a power of two and the SCEV type fits in a native + // integer, consider the divison cheap irrespective of whether it occurs in + // the user code since it can be lowered into a right shift. + if (auto *SC = dyn_cast(UDivExpr->getRHS())) + if (SC->getValue()->getValue().isPowerOf2()) { + const DataLayout &DL = + L->getHeader()->getParent()->getParent()->getDataLayout(); + unsigned Width = cast(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 + // compute. + BasicBlock *ExitingBB = L->getExitingBlock(); + if (!ExitingBB) + return true; + + BranchInst *ExitingBI = dyn_cast(ExitingBB->getTerminator()); + if (!ExitingBI || !ExitingBI->isConditional()) + 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; + } + } + + // Recurse past add expressions, which commonly occur in the + // BackedgeTakenCount. They may already exist in program code, and if not, + // they are not too expensive rematerialize. + if (const SCEVAddExpr *Add = dyn_cast(S)) { + for (SCEVAddExpr::op_iterator I = Add->op_begin(), E = Add->op_end(); + I != E; ++I) { + if (isHighCostExpansionHelper(*I, L, Processed)) + return true; + } + return false; + } + + // HowManyLessThans uses a Max expression whenever the loop is not guarded by + // the exit condition. + if (isa(S) || isa(S)) + return true; + + // If we haven't recognized an expensive SCEV pattern, assume it's an + // expression produced by program code. + return false; +} + namespace { // Search for a SCEV subexpression that is not safe to expand. Any expression // that may expand to a !isSafeToSpeculativelyExecute value is unsafe, namely Index: lib/Transforms/Scalar/IndVarSimplify.cpp =================================================================== --- lib/Transforms/Scalar/IndVarSimplify.cpp +++ lib/Transforms/Scalar/IndVarSimplify.cpp @@ -1274,55 +1274,6 @@ // LinearFunctionTestReplace and its kin. Rewrite the loop exit condition. //===----------------------------------------------------------------------===// -/// Check for expressions that ScalarEvolution generates to compute -/// BackedgeTakenInfo. If these expressions have not been reduced, then -/// expanding them may incur additional cost (albeit in the loop preheader). -static bool isHighCostExpansion(const SCEV *S, BranchInst *BI, - SmallPtrSetImpl &Processed, - ScalarEvolution *SE) { - if (!Processed.insert(S).second) - return false; - - // If the backedge-taken count is a UDiv, it's 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 and - // forego rewriting the loop. - if (isa(S)) { - ICmpInst *OrigCond = dyn_cast(BI->getCondition()); - if (!OrigCond) return true; - const SCEV *R = SE->getSCEV(OrigCond->getOperand(1)); - R = SE->getMinusSCEV(R, SE->getConstant(R->getType(), 1)); - if (R != S) { - const SCEV *L = SE->getSCEV(OrigCond->getOperand(0)); - L = SE->getMinusSCEV(L, SE->getConstant(L->getType(), 1)); - if (L != S) - return true; - } - } - - // Recurse past add expressions, which commonly occur in the - // BackedgeTakenCount. They may already exist in program code, and if not, - // they are not too expensive rematerialize. - if (const SCEVAddExpr *Add = dyn_cast(S)) { - for (SCEVAddExpr::op_iterator I = Add->op_begin(), E = Add->op_end(); - I != E; ++I) { - if (isHighCostExpansion(*I, BI, Processed, SE)) - return true; - } - return false; - } - - // HowManyLessThans uses a Max expression whenever the loop is not guarded by - // the exit condition. - if (isa(S) || isa(S)) - return true; - - // If we haven't recognized an expensive SCEV pattern, assume it's an - // expression produced by program code. - return false; -} - /// canExpandBackedgeTakenCount - Return true if this loop's backedge taken /// count expression can be safely and cheaply expanded into an instruction /// sequence that can be used by LinearFunctionTestReplace. @@ -1336,7 +1287,8 @@ /// used by ABI constrained operation, as opposed to inttoptr/ptrtoint). /// However, we don't yet have a strong motivation for converting loop tests /// into inequality tests. -static bool canExpandBackedgeTakenCount(Loop *L, ScalarEvolution *SE) { +static bool canExpandBackedgeTakenCount(Loop *L, ScalarEvolution *SE, + SCEVExpander &Rewriter) { const SCEV *BackedgeTakenCount = SE->getBackedgeTakenCount(L); if (isa(BackedgeTakenCount) || BackedgeTakenCount->isZero()) @@ -1346,12 +1298,10 @@ return false; // Can't rewrite non-branch yet. - BranchInst *BI = dyn_cast(L->getExitingBlock()->getTerminator()); - if (!BI) + if (!isa(L->getExitingBlock()->getTerminator())) return false; - SmallPtrSet Processed; - if (isHighCostExpansion(BackedgeTakenCount, BI, Processed, SE)) + if (Rewriter.isHighCostExpansion(BackedgeTakenCount, L)) return false; return true; @@ -1691,7 +1641,7 @@ const SCEV *BackedgeTakenCount, PHINode *IndVar, SCEVExpander &Rewriter) { - assert(canExpandBackedgeTakenCount(L, SE) && "precondition"); + assert(canExpandBackedgeTakenCount(L, SE, Rewriter) && "precondition"); // Initialize CmpIndVar and IVCount to their preincremented values. Value *CmpIndVar = IndVar; @@ -1936,7 +1886,7 @@ // If we have a trip count expression, rewrite the loop's exit condition // using it. We can currently only handle loops with a single exit. - if (canExpandBackedgeTakenCount(L, SE) && needsLFTR(L, DT)) { + if (canExpandBackedgeTakenCount(L, SE, Rewriter) && needsLFTR(L, DT)) { PHINode *IndVar = FindLoopCounter(L, BackedgeTakenCount, SE, DT); if (IndVar) { // Check preconditions for proper SCEVExpander operation. SCEV does not Index: test/Transforms/IndVarSimplify/lftr-udiv-tripcount.ll =================================================================== --- /dev/null +++ test/Transforms/IndVarSimplify/lftr-udiv-tripcount.ll @@ -0,0 +1,25 @@ +; RUN: opt < %s -indvars -S | FileCheck %s + +target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128" + +define void @foo(i8* %a, i8 %n) nounwind uwtable ssp { +; CHECK-LABEL: @foo( + entry: + %e = icmp sgt i8 %n, 3 + br i1 %e, label %loop, label %exit + + loop: +; CHECK-LABEL: loop: + %i = phi i8 [ 0, %entry ], [ %i.inc, %loop ] + %i1 = phi i8 [ 0, %entry ], [ %i1.inc, %loop ] + %i.inc = add nsw i8 %i, 4 + %i1.inc = add i8 %i1, 1 + store volatile i8 0, i8* %a + %c = icmp slt i8 %i, %n +; CHECK-LABEL: %exitcond = icmp ne i8 %i1.inc + br i1 %c, label %loop, label %exit + + exit: +; CHECK-LABEL: exit: + ret void +}