summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--llvm/include/llvm/Transforms/Utils/LoopUtils.h17
-rw-r--r--llvm/lib/Transforms/Utils/LoopUtils.cpp33
-rw-r--r--llvm/lib/Transforms/Vectorize/LoopVectorize.cpp22
-rw-r--r--llvm/test/Transforms/LoopVectorize/induction.ll75
4 files changed, 136 insertions, 11 deletions
diff --git a/llvm/include/llvm/Transforms/Utils/LoopUtils.h b/llvm/include/llvm/Transforms/Utils/LoopUtils.h
index b91a313ea02..bd00a008a77 100644
--- a/llvm/include/llvm/Transforms/Utils/LoopUtils.h
+++ b/llvm/include/llvm/Transforms/Utils/LoopUtils.h
@@ -30,6 +30,7 @@ class DominatorTree;
class Loop;
class LoopInfo;
class Pass;
+class PredicatedScalarEvolution;
class PredIteratorCache;
class ScalarEvolution;
class TargetLibraryInfo;
@@ -287,8 +288,22 @@ public:
InductionKind getKind() const { return IK; }
ConstantInt *getStepValue() const { return StepValue; }
+ /// Returns true if \p Phi is an induction. If \p Phi is an induction,
+ /// the induction descriptor \p D will contain the data describing this
+ /// induction. If by some other means the caller has a better SCEV
+ /// expression for \p Phi than the one returned by the ScalarEvolution
+ /// analysis, it can be passed through \p Expr.
static bool isInductionPHI(PHINode *Phi, ScalarEvolution *SE,
- InductionDescriptor &D);
+ InductionDescriptor &D,
+ const SCEV *Expr = nullptr);
+
+ /// Returns true if \p Phi is an induction, in the context associated with
+ /// the run-time predicate of PSE. If \p Assume is true, this can add further
+ /// SCEV predicates to \p PSE in order to prove that \p Phi is an induction.
+ /// If \p Phi is an induction, \p D will contain the data describing this
+ /// induction.
+ static bool isInductionPHI(PHINode *Phi, PredicatedScalarEvolution &PSE,
+ InductionDescriptor &D, bool Assume = false);
private:
/// Private constructor - used by \c isInductionPHI.
diff --git a/llvm/lib/Transforms/Utils/LoopUtils.cpp b/llvm/lib/Transforms/Utils/LoopUtils.cpp
index 2d1f10f0591..c6b0f7b8d71 100644
--- a/llvm/lib/Transforms/Utils/LoopUtils.cpp
+++ b/llvm/lib/Transforms/Utils/LoopUtils.cpp
@@ -698,16 +698,43 @@ Value *InductionDescriptor::transform(IRBuilder<> &B, Value *Index) const {
llvm_unreachable("invalid enum");
}
-bool InductionDescriptor::isInductionPHI(PHINode *Phi, ScalarEvolution *SE,
- InductionDescriptor &D) {
+bool InductionDescriptor::isInductionPHI(PHINode *Phi,
+ PredicatedScalarEvolution &PSE,
+ InductionDescriptor &D,
+ bool Assume) {
+ Type *PhiTy = Phi->getType();
+ // We only handle integer and pointer inductions variables.
+ if (!PhiTy->isIntegerTy() && !PhiTy->isPointerTy())
+ return false;
+
+ const SCEV *PhiScev = PSE.getSCEV(Phi);
+ const auto *AR = dyn_cast<SCEVAddRecExpr>(PhiScev);
+
+ // We need this expression to be an AddRecExpr.
+ if (Assume && !AR)
+ AR = PSE.getAsAddRec(Phi);
+
+ if (!AR) {
+ DEBUG(dbgs() << "LV: PHI is not a poly recurrence.\n");
+ return false;
+ }
+
+ return isInductionPHI(Phi, PSE.getSE(), D, AR);
+}
+
+bool InductionDescriptor::isInductionPHI(PHINode *Phi,
+ ScalarEvolution *SE,
+ InductionDescriptor &D,
+ const SCEV *Expr) {
Type *PhiTy = Phi->getType();
// We only handle integer and pointer inductions variables.
if (!PhiTy->isIntegerTy() && !PhiTy->isPointerTy())
return false;
// Check that the PHI is consecutive.
- const SCEV *PhiScev = SE->getSCEV(Phi);
+ const SCEV *PhiScev = Expr ? Expr : SE->getSCEV(Phi);
const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(PhiScev);
+
if (!AR) {
DEBUG(dbgs() << "LV: PHI is not a poly recurrence.\n");
return false;
diff --git a/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp b/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
index 22f52a3986a..321ee4850f8 100644
--- a/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
+++ b/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
@@ -4673,13 +4673,6 @@ bool LoopVectorizationLegality::canVectorizeInstrs() {
return false;
}
- InductionDescriptor ID;
- if (InductionDescriptor::isInductionPHI(Phi, PSE.getSE(), ID)) {
- if (!addInductionPhi(Phi, ID))
- return false;
- continue;
- }
-
RecurrenceDescriptor RedDes;
if (RecurrenceDescriptor::isReductionPHI(Phi, TheLoop, RedDes)) {
if (RedDes.hasUnsafeAlgebra())
@@ -4689,11 +4682,26 @@ bool LoopVectorizationLegality::canVectorizeInstrs() {
continue;
}
+ InductionDescriptor ID;
+ if (InductionDescriptor::isInductionPHI(Phi, PSE, ID)) {
+ if (!addInductionPhi(Phi, ID))
+ return false;
+ continue;
+ }
+
if (RecurrenceDescriptor::isFirstOrderRecurrence(Phi, TheLoop, DT)) {
FirstOrderRecurrences.insert(Phi);
continue;
}
+ // As a last resort, coerce the PHI to a AddRec expression
+ // and re-try classifying it a an induction PHI.
+ if (InductionDescriptor::isInductionPHI(Phi, PSE, ID, true)) {
+ if (!addInductionPhi(Phi, ID))
+ return false;
+ continue;
+ }
+
emitAnalysis(VectorizationReport(&*it)
<< "value that could not be identified as "
"reduction is used outside the loop");
diff --git a/llvm/test/Transforms/LoopVectorize/induction.ll b/llvm/test/Transforms/LoopVectorize/induction.ll
index 59ee66a4a35..8e3cf365e83 100644
--- a/llvm/test/Transforms/LoopVectorize/induction.ll
+++ b/llvm/test/Transforms/LoopVectorize/induction.ll
@@ -166,3 +166,78 @@ cond.end.i:
loopexit:
ret i32 %and.i
}
+
+; The SCEV expression of %sphi is (zext i8 {%t,+,1}<%loop> to i32)
+; In order to recognize %sphi as an induction PHI and vectorize this loop,
+; we need to convert the SCEV expression into an AddRecExpr.
+; The expression gets converted to {zext i8 %t to i32,+,1}.
+
+; CHECK-LABEL: wrappingindvars1
+; CHECK-LABEL: vector.scevcheck
+; CHECK-LABEL: vector.body
+; CHECK: add <2 x i32> {{%[^ ]*}}, <i32 0, i32 1>
+define void @wrappingindvars1(i8 %t, i32 %len, i32 *%A) {
+ entry:
+ %st = zext i8 %t to i16
+ %ext = zext i8 %t to i32
+ %ecmp = icmp ult i16 %st, 42
+ br i1 %ecmp, label %loop, label %exit
+
+ loop:
+
+ %idx = phi i8 [ %t, %entry ], [ %idx.inc, %loop ]
+ %idx.b = phi i32 [ 0, %entry ], [ %idx.b.inc, %loop ]
+ %sphi = phi i32 [ %ext, %entry ], [%idx.inc.ext, %loop]
+
+ %ptr = getelementptr inbounds i32, i32* %A, i8 %idx
+ store i32 %sphi, i32* %ptr
+
+ %idx.inc = add i8 %idx, 1
+ %idx.inc.ext = zext i8 %idx.inc to i32
+ %idx.b.inc = add nuw nsw i32 %idx.b, 1
+
+ %c = icmp ult i32 %idx.b, %len
+ br i1 %c, label %loop, label %exit
+
+ exit:
+ ret void
+}
+
+; The SCEV expression of %sphi is (4 * (zext i8 {%t,+,1}<%loop> to i32))
+; In order to recognize %sphi as an induction PHI and vectorize this loop,
+; we need to convert the SCEV expression into an AddRecExpr.
+; The expression gets converted to ({4 * (zext %t to i32),+,4}).
+; CHECK-LABEL: wrappingindvars2
+; CHECK-LABEL: vector.scevcheck
+; CHECK-LABEL: vector.body
+; CHECK: add <2 x i32> {{%[^ ]*}}, <i32 0, i32 4>
+define void @wrappingindvars2(i8 %t, i32 %len, i32 *%A) {
+
+entry:
+ %st = zext i8 %t to i16
+ %ext = zext i8 %t to i32
+ %ext.mul = mul i32 %ext, 4
+
+ %ecmp = icmp ult i16 %st, 42
+ br i1 %ecmp, label %loop, label %exit
+
+ loop:
+
+ %idx = phi i8 [ %t, %entry ], [ %idx.inc, %loop ]
+ %sphi = phi i32 [ %ext.mul, %entry ], [%mul, %loop]
+ %idx.b = phi i32 [ 0, %entry ], [ %idx.b.inc, %loop ]
+
+ %ptr = getelementptr inbounds i32, i32* %A, i8 %idx
+ store i32 %sphi, i32* %ptr
+
+ %idx.inc = add i8 %idx, 1
+ %idx.inc.ext = zext i8 %idx.inc to i32
+ %mul = mul i32 %idx.inc.ext, 4
+ %idx.b.inc = add nuw nsw i32 %idx.b, 1
+
+ %c = icmp ult i32 %idx.b, %len
+ br i1 %c, label %loop, label %exit
+
+ exit:
+ ret void
+}
OpenPOWER on IntegriCloud