[SCEV] Support SMin/Umin for GetMinTrailingZeros

[caojoshua]

Summary

There is already support for Max counterparts. No reason why Min should
not be supported.

NFC: code in GetMinTrailingZeroes is copied for a couple node types.
Refactor them into a single code block.

[caojoshua]

This comment was removed by caojoshua.

[caojoshua]

edit comment in test

[caojoshua]

Add a test where trip multiple is 1

[nikic]

llvm/lib/Analysis/ScalarEvolution.cpp

6341

While here, would you mind supporting UMinSeq as well?

6346–6347

Any reason to deviate from the previous structure?

[caojoshua]

llvm/lib/Analysis/ScalarEvolution.cpp

6341

Yeah sure. Let me test this later. I think we can simplify this to

isa<SCEVMinMaxExpr> || isa<SCEVSequentialMinMaxExpr>

6346–6347

i -> I because LLVM coding standards state that Variable names should be nouns (as they represent state). The name should be camel case, and start with an upper case letter (e.g. Leader or Boats). And cause my editor is smart enough to know we are using LLVM coding standards and recommend this change.

No need to assign assign getNumOperands() to E. Can just compare directly against getNumOperands(), and remove unnecessary E variable. M is const, so we know the number of operands will not change through iterations barring some unsafe casting (I think this is how C++ const works).

No strong opinions from me. This deviates from code style in rest of function. I can update the rest of the function as a NFC followup to make sure everything is consistent.

[caojoshua]

• support UMinSequential. Add a test (see note below)
• single isa<SCEVMinMaxExpr>(S) instead of checking each subtype
• fix code style based on comments

I am unable to create a testcase for GetMinTrailingZeroes on UMinSequential
SCEVs. I tried adapting some tests from https://reviews.llvm.org/D116766, but
however I modify tests, either the Trip Multiple is not returning what I would
expect, or the UMinSequential turns into a regular umin.

All existing integration tests pass. Not sure if we need more testing, or we
can support UMinSequential in a separate work.

[caojoshua]

llvm/lib/Analysis/ScalarEvolution.cpp

6346–6347

I reverted the previous structure, but kept the variable names capitalized

[nikic]

LGTM

llvm/lib/Analysis/ScalarEvolution.cpp

uint32_t ScalarEvolution::GetMinTrailingZerosImpl(const SCEV *S) {
 
   if (const SCEVSignExtendExpr *E = dyn_cast<SCEVSignExtendExpr>(S)) {
     uint32_t OpRes = GetMinTrailingZeros(E->getOperand());
     return OpRes == getTypeSizeInBits(E->getOperand()->getType())
                ? getTypeSizeInBits(E->getType())
                : OpRes;
   }
 
-  if (const SCEVAddExpr *A = dyn_cast<SCEVAddExpr>(S)) {
-    // The result is the min of all operands results.
-    uint32_t MinOpRes = GetMinTrailingZeros(A->getOperand(0));
-    for (unsigned i = 1, e = A->getNumOperands(); MinOpRes && i != e; ++i)
-      MinOpRes = std::min(MinOpRes, GetMinTrailingZeros(A->getOperand(i)));
-    return MinOpRes;
-  }
-
   if (const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(S)) {
     // The result is the sum of all operands results.
     uint32_t SumOpRes = GetMinTrailingZeros(M->getOperand(0));
     uint32_t BitWidth = getTypeSizeInBits(M->getType());
     for (unsigned i = 1, e = M->getNumOperands();
          SumOpRes != BitWidth && i != e; ++i)
       SumOpRes =
           std::min(SumOpRes + GetMinTrailingZeros(M->getOperand(i)), BitWidth);
     return SumOpRes;
   }
 
-  if (const SCEVAddRecExpr *A = dyn_cast<SCEVAddRecExpr>(S)) {
-    // The result is the min of all operands results.
-    uint32_t MinOpRes = GetMinTrailingZeros(A->getOperand(0));
-    for (unsigned i = 1, e = A->getNumOperands(); MinOpRes && i != e; ++i)
-      MinOpRes = std::min(MinOpRes, GetMinTrailingZeros(A->getOperand(i)));
-    return MinOpRes;
-  }
-
-  if (const SCEVSMaxExpr *M = dyn_cast<SCEVSMaxExpr>(S)) {
-    // The result is the min of all operands results.
-    uint32_t MinOpRes = GetMinTrailingZeros(M->getOperand(0));
-    for (unsigned i = 1, e = M->getNumOperands(); MinOpRes && i != e; ++i)
-      MinOpRes = std::min(MinOpRes, GetMinTrailingZeros(M->getOperand(i)));
-    return MinOpRes;
-  }
-
-  if (const SCEVUMaxExpr *M = dyn_cast<SCEVUMaxExpr>(S)) {
-    // The result is the min of all operands results.
+  // SCEV nodes whose result is the min of all operands results.
+  if (isa<SCEVAddExpr>(S) || isa<SCEVAddRecExpr>(S) || isa<SCEVSMaxExpr>(S) ||
+      isa<SCEVUMaxExpr>(S) || isa<SCEVSMinExpr>(S) || isa<SCEVUMinExpr>(S)) {
+    const SCEVNAryExpr *M = cast<SCEVNAryExpr>(S);
     uint32_t MinOpRes = GetMinTrailingZeros(M->getOperand(0));
-    for (unsigned i = 1, e = M->getNumOperands(); MinOpRes && i != e; ++i)
-      MinOpRes = std::min(MinOpRes, GetMinTrailingZeros(M->getOperand(i)));
+    for (unsigned I = 1; MinOpRes && I != M->getNumOperands(); ++I)
+      MinOpRes = std::min(MinOpRes, GetMinTrailingZeros(M->getOperand(I)));
     return MinOpRes;
   }
 
   if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) {
     // For a SCEVUnknown, ask ValueTracking.
     KnownBits Known = computeKnownBits(U->getValue(), getDataLayout(), 0, &AC, nullptr, &DT);
     return Known.countMinTrailingZeros();
   }

llvm/test/Analysis/ScalarEvolution/trip-count-minmax.ll

+; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py
+; RUN: opt -passes='print<scalar-evolution>' -disable-output %s 2>&1 | FileCheck %s
+
+; Tests for cmp'ing induction variables against Min/Max SCEVs
+
+define void @umin(i32 noundef %a, i32 noundef %b) {
+; CHECK-LABEL: 'umin'
+; CHECK-NEXT:  Classifying expressions for: @umin
+; CHECK-NEXT:    %mul = shl i32 %a, 1
+; CHECK-NEXT:    --> (2 * %a) U: [0,-1) S: [-2147483648,2147483647)
+; CHECK-NEXT:    %mul1 = shl i32 %b, 2
+; CHECK-NEXT:    --> (4 * %b) U: [0,-3) S: [-2147483648,2147483645)
+; CHECK-NEXT:    %cond = select i1 %cmp, i32 %mul, i32 %mul1
+; CHECK-NEXT:    --> ((2 * %a) umin (4 * %b)) U: [0,-3) S: [-2147483648,2147483647)
+; CHECK-NEXT:    %i.011 = phi i32 [ %inc, %for.body ], [ 0, %entry ]
+; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%for.body> U: [0,-2147483648) S: [0,-2147483648) Exits: (-1 + ((2 * %a) umin (4 * %b))) LoopDispositions: { %for.body: Computable }
+; CHECK-NEXT:    %inc = add nuw nsw i32 %i.011, 1
+; CHECK-NEXT:    --> {1,+,1}<nuw><%for.body> U: [1,-3) S: [1,-3) Exits: ((2 * %a) umin (4 * %b)) LoopDispositions: { %for.body: Computable }
+; CHECK-NEXT:  Determining loop execution counts for: @umin
+; CHECK-NEXT:  Loop %for.body: backedge-taken count is (-1 + ((2 * %a) umin (4 * %b)))
+; CHECK-NEXT:  Loop %for.body: constant max backedge-taken count is -5
+; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is (-1 + ((2 * %a) umin (4 * %b)))
+; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (-1 + ((2 * %a) umin (4 * %b)))
+; CHECK-NEXT:   Predicates:
+; CHECK:       Loop %for.body: Trip multiple is 2
+;
+; void umin(unsigned a, unsigned b) {
+;   a *= 2;
+;   b *= 4;
+;   int N = a < b ? a : b;
+;   for (int i = 0; i < N; ++i) {
+;     foo();
+;   }
+;  }
+
+entry:
+  %mul = shl i32 %a, 1
+  %mul1 = shl i32 %b, 2
+  %cmp = icmp ult i32 %mul, %mul1
+  %cond = select i1 %cmp, i32 %mul, i32 %mul1
+  %cmp210 = icmp sgt i32 %cond, 0
+  br i1 %cmp210, label %for.body, label %for.cond.cleanup
+
+for.cond.cleanup:                                 ; preds = %for.body, %entry
+  ret void
+
+for.body:                                         ; preds = %entry, %for.body
+  %i.011 = phi i32 [ %inc, %for.body ], [ 0, %entry ]
+  tail call void (...) @foo() #2
+  %inc = add nuw nsw i32 %i.011, 1
+  %exitcond.not = icmp eq i32 %inc, %cond
+  br i1 %exitcond.not, label %for.cond.cleanup, label %for.body
+}
+
+
+define void @umax(i32 noundef %a, i32 noundef %b) {
+; CHECK-LABEL: 'umax'
+; CHECK-NEXT:  Classifying expressions for: @umax
+; CHECK-NEXT:    %mul = shl i32 %a, 1
+; CHECK-NEXT:    --> (2 * %a) U: [0,-1) S: [-2147483648,2147483647)
+; CHECK-NEXT:    %mul1 = shl i32 %b, 2
+; CHECK-NEXT:    --> (4 * %b) U: [0,-3) S: [-2147483648,2147483645)
+; CHECK-NEXT:    %cond = select i1 %cmp, i32 %mul, i32 %mul1
+; CHECK-NEXT:    --> ((2 * %a) umax (4 * %b)) U: [0,-1) S: [-2147483648,2147483647)
+; CHECK-NEXT:    %i.011 = phi i32 [ %inc, %for.body ], [ 0, %entry ]
+; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%for.body> U: [0,-2147483648) S: [0,-2147483648) Exits: (-1 + ((2 * %a) umax (4 * %b))) LoopDispositions: { %for.body: Computable }
+; CHECK-NEXT:    %inc = add nuw nsw i32 %i.011, 1
+; CHECK-NEXT:    --> {1,+,1}<nuw><%for.body> U: [1,-1) S: [1,-1) Exits: ((2 * %a) umax (4 * %b)) LoopDispositions: { %for.body: Computable }
+; CHECK-NEXT:  Determining loop execution counts for: @umax
+; CHECK-NEXT:  Loop %for.body: backedge-taken count is (-1 + ((2 * %a) umax (4 * %b)))
+; CHECK-NEXT:  Loop %for.body: constant max backedge-taken count is -3
+; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is (-1 + ((2 * %a) umax (4 * %b)))
+; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (-1 + ((2 * %a) umax (4 * %b)))
+; CHECK-NEXT:   Predicates:
+; CHECK:       Loop %for.body: Trip multiple is 2
+;
+
+; void umax(unsigned a, unsigned b) {
+;   a *= 2;
+;   b *= 4;
+;   int N = a > b ? a : b;
+;   for (int i = 0; i < N; ++i) {
+;     foo();
+;   }
+; }
+
+entry:
+  %mul = shl i32 %a, 1
+  %mul1 = shl i32 %b, 2
+  %cmp = icmp ugt i32 %mul, %mul1
+  %cond = select i1 %cmp, i32 %mul, i32 %mul1
+  %cmp210 = icmp sgt i32 %cond, 0
+  br i1 %cmp210, label %for.body, label %for.cond.cleanup
+
+for.cond.cleanup:                                 ; preds = %for.body, %entry
+  ret void
+
+for.body:                                         ; preds = %entry, %for.body
+  %i.011 = phi i32 [ %inc, %for.body ], [ 0, %entry ]
+  tail call void (...) @foo() #2
+  %inc = add nuw nsw i32 %i.011, 1
+  %exitcond.not = icmp eq i32 %inc, %cond
+  br i1 %exitcond.not, label %for.cond.cleanup, label %for.body
+}
+
+define void @smin(i32 noundef %a, i32 noundef %b) {
+; CHECK-LABEL: 'smin'
+; CHECK-NEXT:  Classifying expressions for: @smin
+; CHECK-NEXT:    %mul = shl nsw i32 %a, 1
+; CHECK-NEXT:    --> (2 * %a)<nsw> U: [0,-1) S: [-2147483648,2147483647)
+; CHECK-NEXT:    %mul1 = shl nsw i32 %b, 2
+; CHECK-NEXT:    --> (4 * %b)<nsw> U: [0,-3) S: [-2147483648,2147483645)
+; CHECK-NEXT:    %cond = select i1 %cmp, i32 %mul, i32 %mul1
+; CHECK-NEXT:    --> ((2 * %a)<nsw> smin (4 * %b)<nsw>) U: [0,-1) S: [-2147483648,2147483645)
+; CHECK-NEXT:    %i.011 = phi i32 [ %inc, %for.body ], [ 0, %entry ]
+; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%for.body> U: [0,-2147483648) S: [0,-2147483648) Exits: (-1 + ((2 * %a)<nsw> smin (4 * %b)<nsw>)) LoopDispositions: { %for.body: Computable }
+; CHECK-NEXT:    %inc = add nuw nsw i32 %i.011, 1
+; CHECK-NEXT:    --> {1,+,1}<nuw><%for.body> U: [1,-1) S: [1,-1) Exits: ((2 * %a)<nsw> smin (4 * %b)<nsw>) LoopDispositions: { %for.body: Computable }
+; CHECK-NEXT:  Determining loop execution counts for: @smin
+; CHECK-NEXT:  Loop %for.body: backedge-taken count is (-1 + ((2 * %a)<nsw> smin (4 * %b)<nsw>))
+; CHECK-NEXT:  Loop %for.body: constant max backedge-taken count is -3
+; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is (-1 + ((2 * %a)<nsw> smin (4 * %b)<nsw>))
+; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (-1 + ((2 * %a)<nsw> smin (4 * %b)<nsw>))
+; CHECK-NEXT:   Predicates:
+; CHECK:       Loop %for.body: Trip multiple is 2
+;
+; void smin(signed a, signed b) {
+;   a *= 2;
+;   b *= 4;
+;   int N = a < b ? a : b;
+;   for (int i = 0; i < N; ++i) {
+;     foo();
+;   }
+; }
+
+entry:
+  %mul = shl nsw i32 %a, 1
+  %mul1 = shl nsw i32 %b, 2
+  %cmp = icmp slt i32 %mul, %mul1
+  %cond = select i1 %cmp, i32 %mul, i32 %mul1
+  %cmp210 = icmp sgt i32 %cond, 0
+  br i1 %cmp210, label %for.body, label %for.cond.cleanup
+
+for.cond.cleanup:                                 ; preds = %for.body, %entry
+  ret void
+
+for.body:                                         ; preds = %entry, %for.body
+  %i.011 = phi i32 [ %inc, %for.body ], [ 0, %entry ]
+  tail call void (...) @foo() #2
+  %inc = add nuw nsw i32 %i.011, 1
+  %exitcond.not = icmp eq i32 %inc, %cond
+  br i1 %exitcond.not, label %for.cond.cleanup, label %for.body
+}
+
+define void @smax(i32 noundef %a, i32 noundef %b) {
+; CHECK-LABEL: 'smax'
+; CHECK-NEXT:  Classifying expressions for: @smax
+; CHECK-NEXT:    %mul = shl nsw i32 %a, 1
+; CHECK-NEXT:    --> (2 * %a)<nsw> U: [0,-1) S: [-2147483648,2147483647)
+; CHECK-NEXT:    %mul1 = shl nsw i32 %b, 2
+; CHECK-NEXT:    --> (4 * %b)<nsw> U: [0,-3) S: [-2147483648,2147483645)
+; CHECK-NEXT:    %cond = select i1 %cmp, i32 %mul, i32 %mul1
+; CHECK-NEXT:    --> ((2 * %a)<nsw> smax (4 * %b)<nsw>) U: [0,-1) S: [-2147483648,2147483647)
+; CHECK-NEXT:    %i.011 = phi i32 [ %inc, %for.body ], [ 0, %entry ]
+; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%for.body> U: [0,-2147483648) S: [0,-2147483648) Exits: (-1 + ((2 * %a)<nsw> smax (4 * %b)<nsw>)) LoopDispositions: { %for.body: Computable }
+; CHECK-NEXT:    %inc = add nuw nsw i32 %i.011, 1
+; CHECK-NEXT:    --> {1,+,1}<nuw><%for.body> U: [1,-1) S: [1,-1) Exits: ((2 * %a)<nsw> smax (4 * %b)<nsw>) LoopDispositions: { %for.body: Computable }
+; CHECK-NEXT:  Determining loop execution counts for: @smax
+; CHECK-NEXT:  Loop %for.body: backedge-taken count is (-1 + ((2 * %a)<nsw> smax (4 * %b)<nsw>))
+; CHECK-NEXT:  Loop %for.body: constant max backedge-taken count is -3
+; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is (-1 + ((2 * %a)<nsw> smax (4 * %b)<nsw>))
+; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (-1 + ((2 * %a)<nsw> smax (4 * %b)<nsw>))
+; CHECK-NEXT:   Predicates:
+; CHECK:       Loop %for.body: Trip multiple is 2
+;
+; void smax(signed a, signed b) {
+;   a *= 2;
+;   b *= 4;
+;   int N = a > b ? a : b;
+;   for (int i = 0; i < N; ++i) {
+;     foo();
+;   }
+; }
+
+entry:
+  %mul = shl nsw i32 %a, 1
+  %mul1 = shl nsw i32 %b, 2
+  %cmp = icmp sgt i32 %mul, %mul1
+  %cond = select i1 %cmp, i32 %mul, i32 %mul1
+  %cmp210 = icmp sgt i32 %cond, 0
+  br i1 %cmp210, label %for.body, label %for.cond.cleanup
+
+for.cond.cleanup:                                 ; preds = %for.body, %entry
+  ret void
+
+for.body:                                         ; preds = %entry, %for.body
+  %i.011 = phi i32 [ %inc, %for.body ], [ 0, %entry ]
+  tail call void (...) @foo() #2
+  %inc = add nuw nsw i32 %i.011, 1
+  %exitcond.not = icmp eq i32 %inc, %cond
+  br i1 %exitcond.not, label %for.cond.cleanup, label %for.body
+}
+
+define void @umin-3and6(i32 noundef %a, i32 noundef %b) {
+; CHECK-LABEL: 'umin-3and6'
+; CHECK-NEXT:  Classifying expressions for: @umin-3and6
+; CHECK-NEXT:    %mul = mul i32 %a, 3
+; CHECK-NEXT:    --> (3 * %a) U: full-set S: full-set
+; CHECK-NEXT:    %mul1 = mul i32 %b, 6
+; CHECK-NEXT:    --> (6 * %b) U: [0,-1) S: [-2147483648,2147483647)
+; CHECK-NEXT:    %cond = select i1 %cmp, i32 %mul, i32 %mul1
+; CHECK-NEXT:    --> ((3 * %a) umin (6 * %b)) U: [0,-1) S: full-set
+; CHECK-NEXT:    %i.011 = phi i32 [ %inc, %for.body ], [ 0, %entry ]
+; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%for.body> U: [0,-2147483648) S: [0,-2147483648) Exits: (-1 + ((3 * %a) umin (6 * %b))) LoopDispositions: { %for.body: Computable }
+; CHECK-NEXT:    %inc = add nuw nsw i32 %i.011, 1
+; CHECK-NEXT:    --> {1,+,1}<nuw><%for.body> U: [1,-1) S: [1,-1) Exits: ((3 * %a) umin (6 * %b)) LoopDispositions: { %for.body: Computable }
+; CHECK-NEXT:  Determining loop execution counts for: @umin-3and6
+; CHECK-NEXT:  Loop %for.body: backedge-taken count is (-1 + ((3 * %a) umin (6 * %b)))
+; CHECK-NEXT:  Loop %for.body: constant max backedge-taken count is -3
+; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is (-1 + ((3 * %a) umin (6 * %b)))
+; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (-1 + ((3 * %a) umin (6 * %b)))
+; CHECK-NEXT:   Predicates:
+; CHECK:       Loop %for.body: Trip multiple is 1
+;
+; Trip multiple is 1 because we use GetMinTrailingZeros() to compute trip multiples.
+; SCEV cannot compute that the trip multiple is 3.
+; void umin(unsigned a, unsigned b) {
+;   a *= 3;
+;   b *= 6;
+;   int N = a < b ? a : b;
+;   for (int i = 0; i < N; ++i) {
+;     foo();
+;   }
+;  }
+
+entry:
+  %mul = mul i32 %a, 3
+  %mul1 = mul i32 %b, 6
+  %cmp = icmp ult i32 %mul, %mul1
+  %cond = select i1 %cmp, i32 %mul, i32 %mul1
+  %cmp210 = icmp sgt i32 %cond, 0
+  br i1 %cmp210, label %for.body, label %for.cond.cleanup
+
+for.cond.cleanup:                                 ; preds = %for.body, %entry
+  ret void
+
+for.body:                                         ; preds = %entry, %for.body
+  %i.011 = phi i32 [ %inc, %for.body ], [ 0, %entry ]
+  tail call void (...) @foo() #2
+  %inc = add nuw nsw i32 %i.011, 1
+  %exitcond.not = icmp eq i32 %inc, %cond
+  br i1 %exitcond.not, label %for.cond.cleanup, label %for.body
+}
+
+declare void @foo(...) local_unnamed_addr #1