[SCEV] Recognize min/max intrinsics

[nikic]

Summary

Recognize umin/umax/smin/smax intrinsics and convert them to the already existing SCEV nodes of the same name.

In the future we'll want SCEVExpander to also produce the intrinsics, but we're not there yet...

[lebedev.ri]

This LG, thanks.

[lebedev.ri]

Two afterthoughts:

1. I suspect that until SCEV actually produces these intrinsics, this is undef-unsafe. Thought i suspect there are other similar problems, so i'm not sure if we should worry about it just yet.
2. Should also handle abs:

----------------------------------------
define i32 @src(i32 %x, i1 %y) {
%0:
  %r = abs i32 %x, %y
  ret i32 %r
}
=>
define i32 @tgt(i32 %x, i1 %y) {
%0:
  %x_frozen = freeze i32 %x
  %t0 = sub i32 0, %x_frozen
  %r = smax i32 %x_frozen, %t0
  ret i32 %r
}
Transformation seems to be correct!

----------------------------------------
define i32 @src(i32 %x) {
%0:
  %r = abs i32 %x, 1
  ret i32 %r
}
=>
define i32 @tgt(i32 %x) {
%0:
  %x_frozen = freeze i32 %x
  %t0 = sub nsw i32 0, %x_frozen
  %r = smax i32 %x_frozen, %t0
  ret i32 %r
}
Transformation seems to be correct!

[nikic]

In D87160#2257554, @lebedev.ri wrote:

Two afterthoughts:

1. I suspect that until SCEV actually produces these intrinsics, this is undef-unsafe. Thought i suspect there are other similar problems, so i'm not sure if we should worry about it just yet.

Yes, that's right. This will get resolved once we start canonicalizing to intrinsics, and until then a lot of the min/max handling is undef-unsafe anyway.

2. Should also handle abs:

Would you like to have that included in this patch or separately? I don't believe that SCEV currently recognizes abs in select form, so this one might need additional SCEVExpander support at the same time (to at least expand it into a reasonable select). There's also some other intrinsics that could be handled, e.g. usub.sat(a, b) is umax(a, b) - b.

[lebedev.ri]

In D87160#2257569, @nikic wrote:

In D87160#2257554, @lebedev.ri wrote:

Two afterthoughts:

1. I suspect that until SCEV actually produces these intrinsics, this is undef-unsafe. Thought i suspect there are other similar problems, so i'm not sure if we should worry about it just yet.

Yes, that's right. This will get resolved once we start canonicalizing to intrinsics, and until then a lot of the min/max handling is undef-unsafe anyway.

2. Should also handle abs:

Would you like to have that included in this patch or separately?

Separate patch is fine i think.

I don't believe that SCEV currently recognizes abs in select form,
so this one might need additional SCEVExpander support at the same time (to at least expand it into a reasonable select).

Maybe, but i don't anticipate such need.

There's also some other intrinsics that could be handled, e.g. usub.sat(a, b) is umax(a, b) - b.

llvm/lib/Analysis/ScalarEvolution.cpp

if (isa<Instruction>(U))
       return createNodeForSelectOrPHI(cast<Instruction>(U), U->getOperand(0),
                                       U->getOperand(1), U->getOperand(2));
     break;
 
   case Instruction::Call:
   case Instruction::Invoke:
     if (Value *RV = cast<CallBase>(U)->getReturnedArgOperand())
       return getSCEV(RV);
+
+    if (auto *II = dyn_cast<IntrinsicInst>(U)) {
+      switch (II->getIntrinsicID()) {
+      case Intrinsic::umax:
+        return getUMaxExpr(getSCEV(II->getArgOperand(0)),
+                           getSCEV(II->getArgOperand(1)));
+      case Intrinsic::umin:
+        return getUMinExpr(getSCEV(II->getArgOperand(0)),
+                           getSCEV(II->getArgOperand(1)));
+      case Intrinsic::smax:
+        return getSMaxExpr(getSCEV(II->getArgOperand(0)),
+                           getSCEV(II->getArgOperand(1)));
+      case Intrinsic::smin:
+        return getSMinExpr(getSCEV(II->getArgOperand(0)),
+                           getSCEV(II->getArgOperand(1)));
+      default:
+        break;
+      }
+    }
     break;
   }
 
   return getUnknown(V);
 }
 
 //===----------------------------------------------------------------------===//
 //                   Iteration Count Computation Code

llvm/test/Analysis/ScalarEvolution/minmax-intrinsics.ll

 ; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py
 ; RUN: opt -analyze -enable-new-pm=0 -scalar-evolution < %s | FileCheck %s
 ; RUN: opt -disable-output "-passes=print<scalar-evolution>" < %s 2>&1 | FileCheck %s
 
 declare i32 @llvm.umax.i32(i32, i32)
 declare i32 @llvm.umin.i32(i32, i32)
 declare i32 @llvm.smax.i32(i32, i32)
 declare i32 @llvm.smin.i32(i32, i32)
 
 define i32 @umax(i32 %x, i32 %y) {
 ; CHECK-LABEL: 'umax'
 ; CHECK-NEXT:  Classifying expressions for: @umax
 ; CHECK-NEXT:    %z = call i32 @llvm.umax.i32(i32 %x, i32 %y)
-; CHECK-NEXT:    --> %z U: full-set S: full-set
+; CHECK-NEXT:    --> (%x umax %y) U: full-set S: full-set
 ; CHECK-NEXT:  Determining loop execution counts for: @umax
 ;
   %z = call i32 @llvm.umax.i32(i32 %x, i32 %y)
   ret i32 %z
 }
 
 define i32 @umin(i32 %x, i32 %y) {
 ; CHECK-LABEL: 'umin'
 ; CHECK-NEXT:  Classifying expressions for: @umin
 ; CHECK-NEXT:    %z = call i32 @llvm.umin.i32(i32 %x, i32 %y)
-; CHECK-NEXT:    --> %z U: full-set S: full-set
+; CHECK-NEXT:    --> (%x umin %y) U: full-set S: full-set
 ; CHECK-NEXT:  Determining loop execution counts for: @umin
 ;
   %z = call i32 @llvm.umin.i32(i32 %x, i32 %y)
   ret i32 %z
 }
 
 define i32 @smax(i32 %x, i32 %y) {
 ; CHECK-LABEL: 'smax'
 ; CHECK-NEXT:  Classifying expressions for: @smax
 ; CHECK-NEXT:    %z = call i32 @llvm.smax.i32(i32 %x, i32 %y)
-; CHECK-NEXT:    --> %z U: full-set S: full-set
+; CHECK-NEXT:    --> (%x smax %y) U: full-set S: full-set
 ; CHECK-NEXT:  Determining loop execution counts for: @smax
 ;
   %z = call i32 @llvm.smax.i32(i32 %x, i32 %y)
   ret i32 %z
 }
 
 define i32 @smin(i32 %x, i32 %y) {
 ; CHECK-LABEL: 'smin'
 ; CHECK-NEXT:  Classifying expressions for: @smin
 ; CHECK-NEXT:    %z = call i32 @llvm.smin.i32(i32 %x, i32 %y)
-; CHECK-NEXT:    --> %z U: full-set S: full-set
+; CHECK-NEXT:    --> (%x smin %y) U: full-set S: full-set
 ; CHECK-NEXT:  Determining loop execution counts for: @smin
 ;
   %z = call i32 @llvm.smin.i32(i32 %x, i32 %y)
   ret i32 %z
 }
 
 define i32 @clamp(i32 %x) {
 ; CHECK-LABEL: 'clamp'
 ; CHECK-NEXT:  Classifying expressions for: @clamp
 ; CHECK-NEXT:    %y = call i32 @llvm.umax.i32(i32 %x, i32 10)
-; CHECK-NEXT:    --> %y U: full-set S: full-set
+; CHECK-NEXT:    --> (10 umax %x) U: [10,0) S: [10,0)
 ; CHECK-NEXT:    %z = call i32 @llvm.umin.i32(i32 %y, i32 20)
-; CHECK-NEXT:    --> %z U: full-set S: full-set
+; CHECK-NEXT:    --> (20 umin (10 umax %x)) U: [10,21) S: [10,21)
 ; CHECK-NEXT:  Determining loop execution counts for: @clamp
 ;
   %y = call i32 @llvm.umax.i32(i32 %x, i32 10)
   %z = call i32 @llvm.umin.i32(i32 %y, i32 20)
   ret i32 %z
 }