From 97d19bd95fb724c937cf3e32d91296fe12476ad5 Mon Sep 17 00:00:00 2001 From: Sanjoy Das Date: Wed, 9 Mar 2016 01:51:02 +0000 Subject: [PATCH] [SCEV] Slightly generalize getRangeViaFactoring Building on the previous change, this generalizes ScalarEvolution::getRangeViaFactoring to work with {Ext(C?A:B)+k0,+,Ext(C?A:B)+k1} where Ext can be a zero extend, sign extend or truncate operation, and k0 and k1 are constants. llvm-svn: 262979 --- llvm/lib/Analysis/ScalarEvolution.cpp | 31 +++++++----- .../ScalarEvolution/increasing-or-decreasing-iv.ll | 58 ++++++++++++++++++++++ 2 files changed, 76 insertions(+), 13 deletions(-) diff --git a/llvm/lib/Analysis/ScalarEvolution.cpp b/llvm/lib/Analysis/ScalarEvolution.cpp index aa5bfad..b8bf0f1 100644 --- a/llvm/lib/Analysis/ScalarEvolution.cpp +++ b/llvm/lib/Analysis/ScalarEvolution.cpp @@ -4557,17 +4557,6 @@ ConstantRange ScalarEvolution::getRangeViaFactoring(const SCEV *Start, const SCEV *Step, const SCEV *MaxBECount, unsigned BitWidth) { - APInt Offset(BitWidth, 0); - - if (auto *SA = dyn_cast(Start)) { - // Peel off a constant offset, if possible. In the future we could consider - // being smarter here and handle {Start+Step,+,Step} too. - if (SA->getNumOperands() != 2 || !isa(SA->getOperand(0))) - return ConstantRange(BitWidth, /* isFullSet = */ true); - Offset = cast(SA->getOperand(0))->getAPInt(); - Start = SA->getOperand(1); - } - // RangeOf({C?A:B,+,C?P:Q}) == RangeOf(C?{A,+,P}:{B,+,Q}) // == RangeOf({A,+,P}) union RangeOf({B,+,Q}) @@ -4579,10 +4568,22 @@ ConstantRange ScalarEvolution::getRangeViaFactoring(const SCEV *Start, explicit SelectPattern(ScalarEvolution &SE, unsigned BitWidth, const SCEV *S) { Optional CastOp; + APInt Offset(BitWidth, 0); assert(SE.getTypeSizeInBits(S->getType()) == BitWidth && "Should be!"); + // Peel off a constant offset: + if (auto *SA = dyn_cast(S)) { + // In the future we could consider being smarter here and handle + // {Start+Step,+,Step} too. + if (SA->getNumOperands() != 2 || !isa(SA->getOperand(0))) + return; + + Offset = cast(SA->getOperand(0))->getAPInt(); + S = SA->getOperand(1); + } + // Peel off a cast operation if (auto *SCast = dyn_cast(S)) { CastOp = SCast->getSCEVType(); @@ -4622,6 +4623,10 @@ ConstantRange ScalarEvolution::getRangeViaFactoring(const SCEV *Start, FalseValue = FalseValue.sext(BitWidth); break; } + + // Re-apply the constant offset we peeled off earlier + TrueValue += Offset; + FalseValue += Offset; } bool isRecognized() { return Condition != nullptr; } @@ -4650,9 +4655,9 @@ 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 *TrueStart = this->getConstant(StartPattern.TrueValue); const SCEV *TrueStep = this->getConstant(StepPattern.TrueValue); - const SCEV *FalseStart = this->getConstant(StartPattern.FalseValue + Offset); + const SCEV *FalseStart = this->getConstant(StartPattern.FalseValue); const SCEV *FalseStep = this->getConstant(StepPattern.FalseValue); ConstantRange TrueRange = diff --git a/llvm/test/Analysis/ScalarEvolution/increasing-or-decreasing-iv.ll b/llvm/test/Analysis/ScalarEvolution/increasing-or-decreasing-iv.ll index bb06291..8c631a4 100644 --- a/llvm/test/Analysis/ScalarEvolution/increasing-or-decreasing-iv.ll +++ b/llvm/test/Analysis/ScalarEvolution/increasing-or-decreasing-iv.ll @@ -188,3 +188,61 @@ loop: leave: ret void } + +define void @f6(i1 %c) { +; CHECK-LABEL: Classifying expressions for: @f6 +entry: + %start = select i1 %c, i32 127, i32 0 + %step = select i1 %c, i32 -2, i32 0 + br label %loop + +loop: + %loop.iv = phi i16 [ 0, %entry ], [ %loop.iv.inc, %loop ] + %iv = phi i32 [ %start, %entry ], [ %iv.next, %loop ] +; CHECK: %iv = phi i32 [ %start, %entry ], [ %iv.next, %loop ] +; CHECK-NEXT: --> {%start,+,(1 + %step)}<%loop> U: [0,128) S: [0,128) + + %step.plus.one = add i32 %step, 1 + %iv.next = add i32 %iv, %step.plus.one + %iv.sext = sext i32 %iv to i64 +; CHECK: %iv.sext = sext i32 %iv to i64 +; CHECK-NEXT: --> {(sext i32 %start to i64),+,(1 + (sext i32 %step to i64))}<%loop> U: [0,128) S: [0,128) + %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 +} + +define void @f7(i1 %c) { +; CHECK-LABEL: Classifying expressions for: @f7 +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 + + %iv.trunc.plus.one = add i16 %iv.trunc, 1 +; CHECK: %iv.trunc.plus.one = add i16 %iv.trunc, 1 +; CHECK-NEXT: --> {(1 + (trunc i32 %start to i16)),+,(trunc i32 %step to i16)}<%loop> U: [1,129) S: [1,129) + + %iv.trunc.plus.two = add i16 %iv.trunc, 2 +; CHECK: %iv.trunc.plus.two = add i16 %iv.trunc, 2 +; CHECK-NEXT: --> {(2 + (trunc i32 %start to i16)),+,(trunc i32 %step to i16)}<%loop> U: [2,130) S: [2,130) + + %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