summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--llvm/include/llvm/Analysis/ScalarEvolutionExpander.h15
-rw-r--r--llvm/lib/Analysis/ScalarEvolutionExpander.cpp29
-rw-r--r--llvm/lib/Transforms/Scalar/IndVarSimplify.cpp2
-rw-r--r--llvm/test/Analysis/ScalarEvolution/pr28705.ll41
4 files changed, 75 insertions, 12 deletions
diff --git a/llvm/include/llvm/Analysis/ScalarEvolutionExpander.h b/llvm/include/llvm/Analysis/ScalarEvolutionExpander.h
index ba6a977e361..e2e2c025a95 100644
--- a/llvm/include/llvm/Analysis/ScalarEvolutionExpander.h
+++ b/llvm/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"
@@ -268,7 +269,15 @@ namespace llvm {
void setChainedPhi(PHINode *PN) { ChainedPhis.insert(PN); }
- /// \brief Try to find LLVM IR value for S available at the point At.
+ /// Try to find existing LLVM IR value for S available at the point At.
+ Value *getExactExistingExpansion(const SCEV *S, const Instruction *At,
+ Loop *L);
+
+ /// Try to find the ValueOffsetPair for S. The function is mainly
+ /// used to check whether S can be expanded cheaply.
+ /// If this returns a non-None value, 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
@@ -276,7 +285,9 @@ namespace llvm {
///
/// 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<ScalarEvolution::ValueOffsetPair>
+ getRelatedExistingExpansion(const SCEV *S, const Instruction *At, Loop *L);
private:
LLVMContext &getContext() const { return SE.getContext(); }
diff --git a/llvm/lib/Analysis/ScalarEvolutionExpander.cpp b/llvm/lib/Analysis/ScalarEvolutionExpander.cpp
index 3f0d926e421..341a230edb0 100644
--- a/llvm/lib/Analysis/ScalarEvolutionExpander.cpp
+++ b/llvm/lib/Analysis/ScalarEvolutionExpander.cpp
@@ -1892,8 +1892,18 @@ unsigned SCEVExpander::replaceCongruentIVs(Loop *L, const DominatorTree *DT,
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<ScalarEvolution::ValueOffsetPair> VO =
+ getRelatedExistingExpansion(S, At, L);
+ if (VO && VO.getValue().second == nullptr)
+ return VO.getValue().first;
+ return nullptr;
+}
+
+Optional<ScalarEvolution::ValueOffsetPair>
+SCEVExpander::getRelatedExistingExpansion(const SCEV *S, const Instruction *At,
+ Loop *L) {
using namespace llvm::PatternMatch;
SmallVector<BasicBlock *, 4> ExitingBlocks;
@@ -1911,22 +1921,23 @@ Value *SCEVExpander::findExistingExpansion(const SCEV *S,
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(
@@ -1935,7 +1946,7 @@ bool SCEVExpander::isHighCostExpansionHelper(
// 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))
return false;
// Zero/One operand expressions
@@ -1983,7 +1994,7 @@ bool SCEVExpander::isHighCostExpansionHelper(
// involving division. This is just a simple search heuristic.
if (!At)
At = &ExitingBB->back();
- if (!findExistingExpansion(
+ if (!getRelatedExistingExpansion(
SE.getAddExpr(S, SE.getConstant(S->getType(), 1)), At, L))
return true;
}
diff --git a/llvm/lib/Transforms/Scalar/IndVarSimplify.cpp b/llvm/lib/Transforms/Scalar/IndVarSimplify.cpp
index 4986b842e93..4f6dbd994e0 100644
--- a/llvm/lib/Transforms/Scalar/IndVarSimplify.cpp
+++ b/llvm/lib/Transforms/Scalar/IndVarSimplify.cpp
@@ -481,7 +481,7 @@ Value *IndVarSimplify::expandSCEVIfNeeded(SCEVExpander &Rewriter, const SCEV *S,
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;
diff --git a/llvm/test/Analysis/ScalarEvolution/pr28705.ll b/llvm/test/Analysis/ScalarEvolution/pr28705.ll
new file mode 100644
index 00000000000..8fbc08e3ca6
--- /dev/null
+++ b/llvm/test/Analysis/ScalarEvolution/pr28705.ll
@@ -0,0 +1,41 @@
+; PR28705
+; RUN: opt < %s -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:
+ %iv = phi i32 [ 0, %for.body650.lr.ph ], [ %inc655, %for.body650 ]
+ %iv2 = phi i32 [ 1, %for.body650.lr.ph ], [ %inc.i.i, %for.body650 ]
+ %arrayidx.i.i1105 = getelementptr inbounds i8, i8* %ref.i1174, i32 %iv2
+ store i8 7, i8* %arrayidx.i.i1105, align 1
+ %inc.i.i = add i32 %iv2, 1
+ %inc655 = add i32 %iv, 1
+ %cmp648 = icmp eq i32 %inc655, %.sroa.speculated
+ br i1 %cmp648, label %loopexit, label %for.body650
+
+end:
+ ret void
+}
OpenPOWER on IntegriCloud