From d3488c6060efc5cc554c15d30917c25acf98eeaa Mon Sep 17 00:00:00 2001 From: Sanjoy Das Date: Wed, 9 Mar 2016 01:50:57 +0000 Subject: [PATCH] [SCEV] Slightly generalize getRangeViaFactoring This change generalizes ScalarEvolution::getRangeViaFactoring to work with {Ext(C?A:B),+,Ext(C?A:B)} where Ext can be a zero extend, sign extend or truncate operation. llvm-svn: 262978 --- llvm/lib/Analysis/ScalarEvolution.cpp | 74 +++++++++++++++------- .../ScalarEvolution/increasing-or-decreasing-iv.ll | 55 +++++++++++++++- 2 files changed, 104 insertions(+), 25 deletions(-) diff --git a/llvm/lib/Analysis/ScalarEvolution.cpp b/llvm/lib/Analysis/ScalarEvolution.cpp index 2f03477..aa5bfad 100644 --- a/llvm/lib/Analysis/ScalarEvolution.cpp +++ b/llvm/lib/Analysis/ScalarEvolution.cpp @@ -4568,42 +4568,70 @@ ConstantRange ScalarEvolution::getRangeViaFactoring(const SCEV *Start, Start = SA->getOperand(1); } - if (!isa(Start) || !isa(Step)) - // We don't have anything new to contribute in this case. - return ConstantRange(BitWidth, /* isFullSet = */ true); - // RangeOf({C?A:B,+,C?P:Q}) == RangeOf(C?{A,+,P}:{B,+,Q}) // == RangeOf({A,+,P}) union RangeOf({B,+,Q}) struct SelectPattern { Value *Condition = nullptr; - const APInt *TrueValue = nullptr; - const APInt *FalseValue = nullptr; + APInt TrueValue; + APInt FalseValue; + + explicit SelectPattern(ScalarEvolution &SE, unsigned BitWidth, + const SCEV *S) { + Optional CastOp; + + assert(SE.getTypeSizeInBits(S->getType()) == BitWidth && + "Should be!"); + + // Peel off a cast operation + if (auto *SCast = dyn_cast(S)) { + CastOp = SCast->getSCEVType(); + S = SCast->getOperand(); + } - explicit SelectPattern(const SCEVUnknown *SU) { using namespace llvm::PatternMatch; - if (!match(SU->getValue(), - m_Select(m_Value(Condition), m_APInt(TrueValue), - m_APInt(FalseValue)))) { + auto *SU = dyn_cast(S); + const APInt *TrueVal, *FalseVal; + if (!SU || + !match(SU->getValue(), m_Select(m_Value(Condition), m_APInt(TrueVal), + m_APInt(FalseVal)))) { Condition = nullptr; - TrueValue = FalseValue = nullptr; + return; } - } - bool isRecognized() { - assert(((Condition && TrueValue && FalseValue) || - (!Condition && !TrueValue && !FalseValue)) && - "Invariant: either all three are non-null or all three are null"); - return TrueValue != nullptr; + TrueValue = *TrueVal; + FalseValue = *FalseVal; + + // Re-apply the cast we peeled off earlier + if (CastOp.hasValue()) + switch (*CastOp) { + default: + llvm_unreachable("Unknown SCEV cast type!"); + + case scTruncate: + TrueValue = TrueValue.trunc(BitWidth); + FalseValue = FalseValue.trunc(BitWidth); + break; + case scZeroExtend: + TrueValue = TrueValue.zext(BitWidth); + FalseValue = FalseValue.zext(BitWidth); + break; + case scSignExtend: + TrueValue = TrueValue.sext(BitWidth); + FalseValue = FalseValue.sext(BitWidth); + break; + } } + + bool isRecognized() { return Condition != nullptr; } }; - SelectPattern StartPattern(cast(Start)); + SelectPattern StartPattern(*this, BitWidth, Start); if (!StartPattern.isRecognized()) return ConstantRange(BitWidth, /* isFullSet = */ true); - SelectPattern StepPattern(cast(Step)); + SelectPattern StepPattern(*this, BitWidth, Step); if (!StepPattern.isRecognized()) return ConstantRange(BitWidth, /* isFullSet = */ true); @@ -4622,10 +4650,10 @@ ConstantRange ScalarEvolution::getRangeViaFactoring(const SCEV *Start, // FIXME: without the explicit `this` receiver below, MSVC errors out with // C2352 and C2512 (otherwise it isn't needed). - const SCEV *TrueStart = this->getConstant(*StartPattern.TrueValue + Offset); - const SCEV *TrueStep = this->getConstant(*StepPattern.TrueValue); - const SCEV *FalseStart = this->getConstant(*StartPattern.FalseValue + Offset); - const SCEV *FalseStep = this->getConstant(*StepPattern.FalseValue); + const SCEV *TrueStart = this->getConstant(StartPattern.TrueValue + Offset); + const SCEV *TrueStep = this->getConstant(StepPattern.TrueValue); + const SCEV *FalseStart = this->getConstant(StartPattern.FalseValue + Offset); + const SCEV *FalseStep = this->getConstant(StepPattern.FalseValue); ConstantRange TrueRange = this->getRangeForAffineAR(TrueStart, TrueStep, MaxBECount, BitWidth); diff --git a/llvm/test/Analysis/ScalarEvolution/increasing-or-decreasing-iv.ll b/llvm/test/Analysis/ScalarEvolution/increasing-or-decreasing-iv.ll index 36dcfd3..bb06291 100644 --- a/llvm/test/Analysis/ScalarEvolution/increasing-or-decreasing-iv.ll +++ b/llvm/test/Analysis/ScalarEvolution/increasing-or-decreasing-iv.ll @@ -100,7 +100,7 @@ loop: %iv.sext = sext i32 %iv to i64 %iv.next = add i32 %iv, %step ; CHECK: %iv.sext = sext i32 %iv to i64 -; CHECK-NEXT: --> {(sext i32 %start to i64),+,(sext i32 %step to i64)}<%loop> +; CHECK-NEXT: --> {(sext i32 %start to i64),+,(sext i32 %step to i64)}<%loop> U: [0,128) S: [0,128) %loop.iv.inc = add i32 %loop.iv, 1 %be.cond = icmp ne i32 %loop.iv.inc, 128 br i1 %be.cond, label %loop, label %leave @@ -128,7 +128,7 @@ loop: %iv = phi i16 [ %start, %entry ], [ %iv.next, %loop ] %iv.zext = zext i16 %iv to i64 ; CHECK: %iv.zext = zext i16 %iv to i64 -; CHECK-NEXT: --> {(zext i16 %start to i64),+,(zext i16 %step to i64)}<%loop> +; CHECK-NEXT: --> {(zext i16 %start to i64),+,(zext i16 %step to i64)}<%loop> U: [0,64644) S: [0,64644) %iv.next = add i16 %iv, %step %loop.iv.inc = add i16 %loop.iv, 1 %be.cond = icmp ne i16 %loop.iv.inc, 128 @@ -137,3 +137,54 @@ loop: leave: ret void } + +define void @f4(i1 %c) { +; CHECK-LABEL: Classifying expressions for: @f4 + +; @f4() demonstrates a case where SCEV is not able to compute a +; precise range for %iv.trunc, though it should be able to, in theory. +; This is because SCEV looks into affine add recurrences only when the +; backedge taken count of the loop has the same bitwidth as the +; induction variable. +entry: + %start = select i1 %c, i32 127, i32 0 + %step = select i1 %c, i32 -1, i32 1 + br label %loop + +loop: + %loop.iv = phi i32 [ 0, %entry ], [ %loop.iv.inc, %loop ] + %iv = phi i32 [ %start, %entry ], [ %iv.next, %loop ] + %iv.trunc = trunc i32 %iv to i16 +; CHECK: %iv.trunc = trunc i32 %iv to i16 +; CHECK-NEXT: --> {(trunc i32 %start to i16),+,(trunc i32 %step to i16)}<%loop> U: full-set S: full-set + %iv.next = add i32 %iv, %step + %loop.iv.inc = add i32 %loop.iv, 1 + %be.cond = icmp ne i32 %loop.iv.inc, 128 + br i1 %be.cond, label %loop, label %leave + +leave: + ret void +} + +define void @f5(i1 %c) { +; CHECK-LABEL: Classifying expressions for: @f5 +entry: + %start = select i1 %c, i32 127, i32 0 + %step = select i1 %c, i32 -1, i32 1 + br label %loop + +loop: + %loop.iv = phi i16 [ 0, %entry ], [ %loop.iv.inc, %loop ] + %iv = phi i32 [ %start, %entry ], [ %iv.next, %loop ] + %iv.trunc = trunc i32 %iv to i16 +; CHECK: %iv.trunc = trunc i32 %iv to i16 +; CHECK-NEXT: --> {(trunc i32 %start to i16),+,(trunc i32 %step to i16)}<%loop> U: [0,128) S: [0,128) + %iv.next = add i32 %iv, %step + + %loop.iv.inc = add i16 %loop.iv, 1 + %be.cond = icmp ne i16 %loop.iv.inc, 128 + br i1 %be.cond, label %loop, label %leave + +leave: + ret void +} -- 2.7.4