Index: include/llvm/Analysis/ScalarEvolutionExpander.h =================================================================== --- include/llvm/Analysis/ScalarEvolutionExpander.h +++ include/llvm/Analysis/ScalarEvolutionExpander.h @@ -14,6 +14,7 @@ #ifndef LLVM_ANALYSIS_SCALAREVOLUTIONEXPANDER_H #define LLVM_ANALYSIS_SCALAREVOLUTIONEXPANDER_H +#include "llvm/ADT/Optional.h" #include "llvm/Analysis/ScalarEvolutionExpressions.h" #include "llvm/Analysis/ScalarEvolutionNormalization.h" #include "llvm/Analysis/TargetFolder.h" @@ -270,13 +271,29 @@ /// \brief Try to find LLVM IR value for S available at the point At. /// + /// Note the func is different from getRelatedExistingExpansion in that + /// it only gets "existing" value in IR. If the `ValueOffsetPair` + /// returned by getRelatedExistingExpansion contains non-zero offset, + /// which means `ValueOffsetPair` has to be expanded to newly create + /// the correct Value, the func will return nullptr. + Value *getExactExistingExpansion(const SCEV *S, const Instruction *At, + Loop *L); + + /// \brief Try to find ValueOffsetPair for S. The func is mainly used + /// to check whether S can be expanded cheaply. + /// If only return is non-None, we know we can codegen the `ValueOffsetPair` + /// into a suitable expansion identical with S so that S can be expanded + /// cheaply. + /// /// L is a hint which tells in which loop to look for the suitable value. /// On success return value which is equivalent to the expanded S at point /// At. Return nullptr if value was not found. /// /// Note that this function does not perform an exhaustive search. I.e if it /// didn't find any value it does not mean that there is no such value. - Value *findExistingExpansion(const SCEV *S, const Instruction *At, Loop *L); + /// + Optional + getRelatedExistingExpansion(const SCEV *S, const Instruction *At, Loop *L); private: LLVMContext &getContext() const { return SE.getContext(); } Index: lib/Analysis/ScalarEvolutionExpander.cpp =================================================================== --- lib/Analysis/ScalarEvolutionExpander.cpp +++ lib/Analysis/ScalarEvolutionExpander.cpp @@ -1893,8 +1893,18 @@ return NumElim; } -Value *SCEVExpander::findExistingExpansion(const SCEV *S, - const Instruction *At, Loop *L) { +Value *SCEVExpander::getExactExistingExpansion(const SCEV *S, + const Instruction *At, Loop *L) { + Optional VO = + getRelatedExistingExpansion(S, At, L); + if (VO.hasValue() && VO.getValue().second == nullptr) + return VO.getValue().first; + return nullptr; +} + +Optional +SCEVExpander::getRelatedExistingExpansion(const SCEV *S, const Instruction *At, + Loop *L) { using namespace llvm::PatternMatch; SmallVector ExitingBlocks; @@ -1912,22 +1922,23 @@ continue; if (SE.getSCEV(LHS) == S && SE.DT.dominates(LHS, At)) - return LHS; + return ScalarEvolution::ValueOffsetPair(LHS, nullptr); if (SE.getSCEV(RHS) == S && SE.DT.dominates(RHS, At)) - return RHS; + return ScalarEvolution::ValueOffsetPair(RHS, nullptr); } // Use expand's logic which is used for reusing a previous Value in // ExprValueMap. - if (Value *Val = FindValueInExprValueMap(S, At).first) - return Val; + ScalarEvolution::ValueOffsetPair VO = FindValueInExprValueMap(S, At); + if (VO.first) + return VO; // There is potential to make this significantly smarter, but this simple // heuristic already gets some interesting cases. // Can not find suitable value. - return nullptr; + return None; } bool SCEVExpander::isHighCostExpansionHelper( @@ -1936,7 +1947,7 @@ // If we can find an existing value for this scev avaliable at the point "At" // then consider the expression cheap. - if (At && findExistingExpansion(S, At, L) != nullptr) + if (At && getRelatedExistingExpansion(S, At, L).hasValue()) return false; // Zero/One operand expressions @@ -1984,8 +1995,9 @@ // 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)) + if (!getRelatedExistingExpansion( + SE.getAddExpr(S, SE.getConstant(S->getType(), 1)), At, L) + .hasValue()) return true; } Index: lib/Transforms/Scalar/IndVarSimplify.cpp =================================================================== --- lib/Transforms/Scalar/IndVarSimplify.cpp +++ lib/Transforms/Scalar/IndVarSimplify.cpp @@ -481,7 +481,7 @@ Type *ResultTy) { // Before expanding S into an expensive LLVM expression, see if we can use an // already existing value as the expansion for S. - if (Value *ExistingValue = Rewriter.findExistingExpansion(S, InsertPt, L)) + if (Value *ExistingValue = Rewriter.getExactExistingExpansion(S, InsertPt, L)) if (ExistingValue->getType() == ResultTy) return ExistingValue; Index: test/Analysis/ScalarEvolution/pr28705.ll =================================================================== --- test/Analysis/ScalarEvolution/pr28705.ll +++ test/Analysis/ScalarEvolution/pr28705.ll @@ -0,0 +1,41 @@ +; PR28705 +; RUN: opt < %s -indvars -debug-only=indvars -S | FileCheck %s + +; Check IndVarSimplify replaces the exitval use of the induction var "%inc.i.i" +; with "%.sroa.speculated + 1". +; +; CHECK-LABEL: @foo( +; CHECK: %[[EXIT:.+]] = sub i32 %.sroa.speculated, -1 +; CHECK: %DB.sroa.9.0.lcssa = phi i32 [ 1, %entry ], [ %[[EXIT]], %loopexit ] +; +define void @foo(i32 %sub.ptr.div.i, i8* %ref.i1174) local_unnamed_addr { +entry: + %cmp.i1137 = icmp ugt i32 %sub.ptr.div.i, 3 + %.sroa.speculated = select i1 %cmp.i1137, i32 3, i32 %sub.ptr.div.i + %cmp6483126 = icmp eq i32 %.sroa.speculated, 0 + br i1 %cmp6483126, label %XZ.exit, label %for.body650.lr.ph + +for.body650.lr.ph: + br label %for.body650 + +loopexit: + %inc.i.i.lcssa = phi i32 [ %inc.i.i, %for.body650 ] + br label %XZ.exit + +XZ.exit: + %DB.sroa.9.0.lcssa = phi i32 [ 1, %entry ], [ %inc.i.i.lcssa, %loopexit ] + br label %end + +for.body650: + %I641.03128 = phi i32 [ 0, %for.body650.lr.ph ], [ %inc655, %for.body650 ] + %DB.sroa.9.03127 = phi i32 [ 1, %for.body650.lr.ph ], [ %inc.i.i, %for.body650 ] + %arrayidx.i.i1105 = getelementptr inbounds i8, i8* %ref.i1174, i32 %DB.sroa.9.03127 + store i8 7, i8* %arrayidx.i.i1105, align 1 + %inc.i.i = add i32 %DB.sroa.9.03127, 1 + %inc655 = add i32 %I641.03128, 1 + %cmp648 = icmp eq i32 %inc655, %.sroa.speculated + br i1 %cmp648, label %loopexit, label %for.body650 + +end: + ret void +}