ScalarEvolution: Add URem support

[alexandre.isoard]

Summary

Add URem support to SCEV.

In LLVM IR the following code:

%r = urem <ty> %t, %b

is equivalent to:

%q = udiv <ty> %t, %b
%s = mul <ty> nuw %q, %b
%r = sub <ty> nuw %t, %q ; (t / b) * b + (t % b) = t

As UDiv, Mul and Sub are already supported by SCEV, URem can be implemented with minimal effort this way.

We implement two special cases:

• if %b is 1, the result is always 0
• if %b is a power-of-two, we produce a zext(trunc(%t)) instead

[efriedma]

This is correct, as far as I can tell... but I'd like to see an example of a loop where this is useful.

[alexandre.isoard]

Added an additional testcase with a loop.

It is a loop iterating over the cells of a [5 x [7 x i8]] array in increasing order.

[mkazantsev]

lib/Analysis/ScalarEvolution.cpp

5782

Can we handle RHS = 1 separately and return constant 0 in this case?

[alexandre.isoard]

lib/Analysis/ScalarEvolution.cpp

5782

That is doable, although I am not sure about the saved time as:

• getUDivExpr detect division by 1
• getMulExpr detect the multiplication by 1
• getMinusSCEV detect the subtraction of equal SCEV

But it might be useful to separate the code into a getURemExpr.

[efriedma]

lib/Analysis/ScalarEvolution.cpp

5782

Yes, getURemExpr would be nice.

test/Analysis/ScalarEvolution/flattened.ll

1 ↗

(On Diff #104382)

"tee /dev/fd/2" is not portable.

Not sure why you need it, anyway; -analyze output goes to stdout.

14 ↗

(On Diff #104382)

CHECK-NEXT

[alexandre.isoard]

test/Analysis/ScalarEvolution/flattened.ll

1 ↗

(On Diff #104382)

Oops. That is a hack I use to print all of the stdout when the test case fail. (instead of the best matching line only)

I forgot to remove it.

14 ↗

(On Diff #104382)

Indeed. I add that in the next update.

[alexandre.isoard]

Updated testcase, outlined into a getURemExpr and added a x urem 1 shortcut.

[efriedma]

lib/Analysis/ScalarEvolution.cpp

2957

"X urem 1 --> X"????

[alexandre.isoard]

Fixed the short-circuit. (should be 0, not x)

[efriedma]

LGTM with one minor comment.

lib/Analysis/ScalarEvolution.cpp

2958

Please add a test for this.

[alexandre.isoard]

lib/Analysis/ScalarEvolution.cpp

2957

End here I was thinking I revolutionized all modern cryptography.

[grosser]

Very nice.

[sanjoy]

test/Analysis/ScalarEvolution/flattened.ll

5 ↗

(On Diff #104482)

I'd suggest adding a CHECK-LABEL: @foo( here and in the other test.

[alexandre.isoard]

I added handling for urem by a power-of-two so as to fix the failing test-case.

[alexandre.isoard]

Please check I didn't introduce new errors (off by one?).

Note that I did not add code to normalize zext(trunc(%a))+shl(lshr(%a)) into %a, yet.
That will be done in a future independent patch.

[efriedma]

lib/Analysis/ScalarEvolution.cpp

2962

Redundant check: zero isn't a power of two.

2968

There's a logBase2 helper on APInt.

test/Analysis/ScalarEvolution/flattened-0.ll

5

CHECK-LABEL

[alexandre.isoard]

Updated the test cases and simplified the power-of-two special case.

[alexandre.isoard]

Hello, is there any modifications I didn't apply or do you have any change you would like to see?

[efriedma]

LGTM

include/llvm/Analysis/ScalarEvolution.h

public:
   const SCEV *getMulExpr(const SCEV *Op0, const SCEV *Op1, const SCEV *Op2,
                          SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap,
                          unsigned Depth = 0) {
     SmallVector<const SCEV *, 3> Ops = {Op0, Op1, Op2};
     return getMulExpr(Ops, Flags, Depth);
   }
   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,
                             const Loop *L, SCEV::NoWrapFlags Flags);
   const SCEV *getAddRecExpr(const SmallVectorImpl<const SCEV *> &Operands,
                             const Loop *L, SCEV::NoWrapFlags Flags) {
     SmallVector<const SCEV *, 4> NewOp(Operands.begin(), Operands.end());
     return getAddRecExpr(NewOp, L, Flags);

lib/Analysis/ScalarEvolution.cpp

for (; Idx < Ops.size() && isa<SCEVAddRecExpr>(Ops[Idx]); ++Idx) {
     // next one.
   }
 
   // Okay, it looks like we really DO need an mul expr.  Check to see if we
   // already have one, otherwise create a new one.
   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!");
+
+  // Short-circuit easy cases
+  if (const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(RHS)) {
+    // If constant is one, the result is trivial
+    if (RHSC->getValue()->isOne())
+      return getZero(LHS->getType()); // X urem 1 --> 0
+
+    // If constant is a power of two, fold into a zext(trunc(LHS)).
+    if (RHSC->getAPInt().isPowerOf2()) {
+      Type *FullTy = LHS->getType();
+      Type *TruncTy =
+          IntegerType::get(getContext(), RHSC->getAPInt().logBase2());
+      return getZeroExtendExpr(getTruncateExpr(LHS, TruncTy), FullTy);
+    }
+  }
+
+  // Fallback to %a == %x urem %y == %x -<nuw> ((%x udiv %y) *<nuw> %y)
+  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,
                                          const SCEV *RHS) {
   assert(getEffectiveSCEVType(LHS->getType()) ==
          getEffectiveSCEVType(RHS->getType()) &&
          "SCEVUDivExpr operand types don't match!");
 
static Optional<BinaryOp> MatchBinaryOp(Value *V, DominatorTree &DT) {
   // creating new SCEV expressions -- our caller knowns tricks to avoid creating
   // SCEV expressions when possible, and we should not break that.
 
   switch (Op->getOpcode()) {
   case Instruction::Add:
   case Instruction::Sub:
   case Instruction::Mul:
   case Instruction::UDiv:
+  case Instruction::URem:
   case Instruction::And:
   case Instruction::Or:
   case Instruction::AShr:
   case Instruction::Shl:
     return BinaryOp(Op);
 
   case Instruction::Xor:
     if (auto *RHSC = dyn_cast<ConstantInt>(Op->getOperand(1)))
case Instruction::Mul: {
         }
         BO = NewBO;
       } while (true);
 
       return getMulExpr(MulOps);
     }
     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)
         Flags = getNoWrapFlagsFromUB(BO->Op);
       return getMinusSCEV(getSCEV(BO->LHS), getSCEV(BO->RHS), Flags);
     }
     case Instruction::And:
       // For an expression like x&255 that merely masks off the high bits,

test/Analysis/ScalarEvolution/flattened-0.ll

+; RUN: opt < %s -scalar-evolution -analyze | FileCheck %s
+
+define void @foo([7 x i8]* %a) {
+; CHECK-LABEL: @foo
+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 = getelementptr [7 x i8], [7 x i8]* %a, i64 %i, i64 %j
+; 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
+}

test/Analysis/ScalarEvolution/urem-0.ll

 ; RUN: opt < %s -scalar-evolution -analyze | FileCheck %s
 
 define i8 @foo(i8 %a) {
+; CHECK-LABEL: @foo
         %t0 = urem i8 %a, 27
-; CHECK: %t0
+; CHECK: %t0 = urem i8 %a, 27
 ; CHECK-NEXT: -->  ((-27 * (%a /u 27)) + %a)
         ret i8 %t0
 }
 
 define i8 @bar(i8 %a) {
+; CHECK-LABEL: @bar
         %t1 = urem i8 %a, 1
-; CHECK: %t1
+; CHECK: %t1 = urem i8 %a, 1
 ; CHECK-NEXT: -->  0
         ret i8 %t1
 }
+
+define i8 @baz(i8 %a) {
+; CHECK-LABEL: @baz
+        %t2 = urem i8 %a, 32
+; CHECK: %t2 = urem i8 %a, 32
+; CHECK-NEXT: -->  (zext i5 (trunc i8 %a to i5) to i8)
+        ret i8 %t2
+}
+
+define i8 @qux(i8 %a) {
+; CHECK-LABEL: @qux
+        %t3 = urem i8 %a, 2
+; CHECK: %t3 = urem i8 %a, 2
+; CHECK-NEXT: -->  (zext i1 (trunc i8 %a to i1) to i8)
+        ret i8 %t3
+}