diff options
| -rw-r--r-- | llvm/include/llvm/Analysis/ScalarEvolution.h | 1 | ||||
| -rw-r--r-- | llvm/lib/Analysis/ScalarEvolution.cpp | 26 | ||||
| -rw-r--r-- | llvm/test/Analysis/ScalarEvolution/flattened.ll | 22 | ||||
| -rw-r--r-- | llvm/test/Analysis/ScalarEvolution/urem-0.ll | 15 |
4 files changed, 64 insertions, 0 deletions
diff --git a/llvm/include/llvm/Analysis/ScalarEvolution.h b/llvm/include/llvm/Analysis/ScalarEvolution.h index 002a3174fd1..c57c600075e 100644 --- a/llvm/include/llvm/Analysis/ScalarEvolution.h +++ b/llvm/include/llvm/Analysis/ScalarEvolution.h @@ -1244,6 +1244,7 @@ public: } const SCEV *getUDivExpr(const SCEV *LHS, const SCEV *RHS); const SCEV *getUDivExactExpr(const SCEV *LHS, const SCEV *RHS); + const SCEV *getURemExpr(const SCEV *LHS, const SCEV *RHS); const SCEV *getAddRecExpr(const SCEV *Start, const SCEV *Step, const Loop *L, SCEV::NoWrapFlags Flags); const SCEV *getAddRecExpr(SmallVectorImpl<const SCEV *> &Operands, diff --git a/llvm/lib/Analysis/ScalarEvolution.cpp b/llvm/lib/Analysis/ScalarEvolution.cpp index 73a95ec405c..80bbc8b05e2 100644 --- a/llvm/lib/Analysis/ScalarEvolution.cpp +++ b/llvm/lib/Analysis/ScalarEvolution.cpp @@ -2935,6 +2935,29 @@ const SCEV *ScalarEvolution::getMulExpr(SmallVectorImpl<const SCEV *> &Ops, return getOrCreateMulExpr(Ops, Flags); } +/// Represents an unsigned remainder expression based on unsigned division. +const SCEV *ScalarEvolution::getURemExpr(const SCEV *LHS, + const SCEV *RHS) { + assert(getEffectiveSCEVType(LHS->getType()) == + getEffectiveSCEVType(RHS->getType()) && + "SCEVURemExpr operand types don't match!"); + + // TODO: + // - short circuit '%a = %x urem %x --> 0' (why is it not done for udiv?) + // - short circuit '%a = %x urem 0 --> %a' (same as for udiv) + // - update upper-bound and lower-bound cache for the final result + // (or improve how subtraction is estimated) + + // Short-circuit easy cases + if (const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(RHS)) + if (RHSC->getValue()->equalsInt(1)) + return getZero(LHS->getType()); // X urem 1 --> 0 + + const SCEV *UDiv = getUDivExpr(LHS, RHS); + const SCEV *Mult = getMulExpr(UDiv, RHS, SCEV::FlagNUW); + return getMinusSCEV(LHS, Mult, SCEV::FlagNUW); +} + /// Get a canonical unsigned division expression, or something simpler if /// possible. const SCEV *ScalarEvolution::getUDivExpr(const SCEV *LHS, @@ -4095,6 +4118,7 @@ static Optional<BinaryOp> MatchBinaryOp(Value *V, DominatorTree &DT) { case Instruction::Sub: case Instruction::Mul: case Instruction::UDiv: + case Instruction::URem: case Instruction::And: case Instruction::Or: case Instruction::AShr: @@ -5416,6 +5440,8 @@ const SCEV *ScalarEvolution::createSCEV(Value *V) { } case Instruction::UDiv: return getUDivExpr(getSCEV(BO->LHS), getSCEV(BO->RHS)); + case Instruction::URem: + return getURemExpr(getSCEV(BO->LHS), getSCEV(BO->RHS)); case Instruction::Sub: { SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap; if (BO->Op) diff --git a/llvm/test/Analysis/ScalarEvolution/flattened.ll b/llvm/test/Analysis/ScalarEvolution/flattened.ll new file mode 100644 index 00000000000..3ca5cf166c8 --- /dev/null +++ b/llvm/test/Analysis/ScalarEvolution/flattened.ll @@ -0,0 +1,22 @@ +; RUN: opt < %s -scalar-evolution -analyze | FileCheck %s + + +define void @foo([7 x i8]* %a) { +entry: + br label %bb + +bb: + %idx = phi i64 [ 0, %entry ], [ %idx.incr, %bb ] + %i = udiv i64 %idx, 7 + %j = urem i64 %idx, 7 + %a.ptr = getelementptr [7 x i8], [7 x i8]* %a, i64 %i, i64 %j +; CHECK: %a.ptr +; CHECK-NEXT: --> {%a,+,1}<nw><%bb> + %val = load i8, i8* %a.ptr + %idx.incr = add i64 %idx, 1 + %test = icmp ne i64 %idx.incr, 35 + br i1 %test, label %bb, label %exit + +exit: + ret void +} diff --git a/llvm/test/Analysis/ScalarEvolution/urem-0.ll b/llvm/test/Analysis/ScalarEvolution/urem-0.ll new file mode 100644 index 00000000000..423911706ad --- /dev/null +++ b/llvm/test/Analysis/ScalarEvolution/urem-0.ll @@ -0,0 +1,15 @@ +; RUN: opt < %s -scalar-evolution -analyze | FileCheck %s + +define i8 @foo(i8 %a) { + %t0 = urem i8 %a, 27 +; CHECK: %t0 +; CHECK-NEXT: --> ((-27 * (%a /u 27)) + %a) + ret i8 %t0 +} + +define i8 @bar(i8 %a) { + %t1 = urem i8 %a, 1 +; CHECK: %t1 +; CHECK-NEXT: --> 0 + ret i8 %t1 +} |
