Detect more min/max patterns in ScalarEvolution

[mreisinger]

Summary

The exact patterns, that this patch will enable to be detected, are the following:

a+1 >s b ? a+x : b+x -> smax(a, b)+x
a+1 >s b ? b+x : a+x -> smin(a, b)+x
a+1 >u b ? a+x : b+x -> umax(a, b)+x
a+1 >u b ? b+x : a+x -> umin(a, b)+x

Computations of this form are currently emitted, for example, by the LLVM code generator of the Julia language. This change also resolves the following bug that has been reported for Polly: https://llvm.org/bugs/show_bug.cgi?id=28126. Special thanks go to Michael Kruse for his detailed hints on how to address this problem.

[mreisinger]

Unfortunately, these changes cause the function createNodeForSelectOrPHI to get quite long. Originally I tried to combine the added code with the existing pattern matching logic in the ICMP_SGE and ICMP_UGE case branches. But in my opinion this caused the code to get too unclear, so I decided to separate the logic. In case the provided test cases are too compact, I can also try to define more extensive ones. Also I was not sure where the existing pattern matching logic is tested, therefore, for now, I added a separate test file for this.

Thank you in advance for any kind of input on this!

[sanjoy]

I'm not sure if these are correct. What if a is INT_MAX in the signed case or -1 in the unsigned case?

[mreisinger]

Thank you for bringing this to my notice, I will address these issues and update the patch.

[Meinersbur]

lib/Analysis/ScalarEvolution.cpp

4251

This fall through doesn't work. The a <s (b+1) case is only correct with strict comparisons (ICMP_SLT), but the code below would also allow it with ICMP_SLE.

4292

same as above

[Meinersbur]

For less code duplication, you might extract out a function that takes as argument whether it's a strict comparison and whether it's signed/unsigned comparison.

Michael

[mreisinger]

Thank you for your comments Michael! However, regarding Sanjoy's concerns, I am unsure if it's really possible to change these patterns to be applicable in cases where the absence of a wraparound cannot be assured, like in the provided test cases. I hope not to overlook obvious opportunities for such a generalization. However, if it's indeed unattainable at the level of ScalarEvolution, this would at least unveil the necessity to handle this via canonicalization on the side of Julia's LLVM code generator. If true, I am sorry that this patch was needed to gain this insight.

[Meinersbur]

Teaching the Julia complier to add nsw/nuw flags shouldn't be that difficult. One might also test first whether the register has its extreme value. However, this would replace a select with another select and probably not that useful.

[mreisinger]

Thank you for all the comments. I close this now, in favor of a different approach. The recent discussion on this can also be followed at https://groups.google.com/forum/#!topic/julia-dev/5io1KnEswqs

lib/Analysis/ScalarEvolution.cpp

const SCEV *ScalarEvolution::createNodeForSelectOrPHI(Instruction *I,
 
   Value *LHS = ICI->getOperand(0);
   Value *RHS = ICI->getOperand(1);
 
   switch (ICI->getPredicate()) {
   case ICmpInst::ICMP_SLT:
   case ICmpInst::ICMP_SLE:
     std::swap(LHS, RHS);
   // fall through
   case ICmpInst::ICMP_SGT:
+    // a+1 >s b ? a+x : b+x  ->  smax(a, b)+x
+    // a+1 >s b ? b+x : a+x  ->  smin(a, b)+x
+    if (getTypeSizeInBits(LHS->getType()) <= getTypeSizeInBits(I->getType())) {
+      const SCEV *LS = getNoopOrSignExtend(getSCEV(LHS), I->getType());
+      const SCEV *LSMinusOne = getMinusSCEV(LS, getOne(I->getType()));
+      const SCEV *RS = getNoopOrSignExtend(getSCEV(RHS), I->getType());
+      const SCEV *LA = getSCEV(TrueVal);
+      const SCEV *RA = getSCEV(FalseVal);
+      const SCEV *LDiff = getMinusSCEV(LA, LSMinusOne);
+      const SCEV *RDiff = getMinusSCEV(RA, RS);
+      if (LDiff == RDiff)
+        return getAddExpr(getSMaxExpr(LSMinusOne, RS), RDiff);
+      LDiff = getMinusSCEV(LA, RS);
+      RDiff = getMinusSCEV(RA, LSMinusOne);
+      if (LDiff == RDiff)
+        return getAddExpr(getSMinExpr(LSMinusOne, RS), LDiff);
+    }
+  // fall through
   case ICmpInst::ICMP_SGE:
     // a >s b ? a+x : b+x  ->  smax(a, b)+x
     // a >s b ? b+x : a+x  ->  smin(a, b)+x
     if (getTypeSizeInBits(LHS->getType()) <= getTypeSizeInBits(I->getType())) {
       const SCEV *LS = getNoopOrSignExtend(getSCEV(LHS), I->getType());
       const SCEV *RS = getNoopOrSignExtend(getSCEV(RHS), I->getType());
       const SCEV *LA = getSCEV(TrueVal);
       const SCEV *RA = getSCEV(FalseVal);
       const SCEV *LDiff = getMinusSCEV(LA, LS);
       const SCEV *RDiff = getMinusSCEV(RA, RS);
       if (LDiff == RDiff)
         return getAddExpr(getSMaxExpr(LS, RS), LDiff);
       LDiff = getMinusSCEV(LA, RS);
       RDiff = getMinusSCEV(RA, LS);
       if (LDiff == RDiff)
         return getAddExpr(getSMinExpr(LS, RS), LDiff);
     }
     break;
   case ICmpInst::ICMP_ULT:
   case ICmpInst::ICMP_ULE:
     std::swap(LHS, RHS);
   // fall through
   case ICmpInst::ICMP_UGT:
+    // a+1 >u b ? a+x : b+x  ->  umax(a, b)+x
+    // a+1 >u b ? b+x : a+x  ->  umin(a, b)+x
+    if (getTypeSizeInBits(LHS->getType()) <= getTypeSizeInBits(I->getType())) {
+      const SCEV *LS = getNoopOrSignExtend(getSCEV(LHS), I->getType());
+      const SCEV *LSMinusOne = getMinusSCEV(LS, getOne(I->getType()));
+      const SCEV *RS = getNoopOrSignExtend(getSCEV(RHS), I->getType());
+      const SCEV *LA = getSCEV(TrueVal);
+      const SCEV *RA = getSCEV(FalseVal);
+      const SCEV *LDiff = getMinusSCEV(LA, LSMinusOne);
+      const SCEV *RDiff = getMinusSCEV(RA, RS);
+      if (LDiff == RDiff)
+        return getAddExpr(getUMaxExpr(LSMinusOne, RS), RDiff);
+      LDiff = getMinusSCEV(LA, RS);
+      RDiff = getMinusSCEV(RA, LSMinusOne);
+      if (LDiff == RDiff)
+        return getAddExpr(getUMinExpr(LSMinusOne, RS), LDiff);
+    }
+  // fall through
   case ICmpInst::ICMP_UGE:
     // a >u b ? a+x : b+x  ->  umax(a, b)+x
     // a >u b ? b+x : a+x  ->  umin(a, b)+x
     if (getTypeSizeInBits(LHS->getType()) <= getTypeSizeInBits(I->getType())) {
       const SCEV *LS = getNoopOrZeroExtend(getSCEV(LHS), I->getType());
       const SCEV *RS = getNoopOrZeroExtend(getSCEV(RHS), I->getType());
       const SCEV *LA = getSCEV(TrueVal);
       const SCEV *RA = getSCEV(FalseVal);

test/Analysis/ScalarEvolution/min-max-patterns.ll

+; RUN: opt -analyze -scalar-evolution < %s | FileCheck %s
+;
+; This file contains test cases that verify that some simple uses of ICMP and
+; SELECT are recognized as SMAX/UMAX or SMIN/UMIN.
+
+; Try to match the following pattern in function f0:
+; a+1 >s b ? a+x : b+x  ->  smax(a, b)+x
+define void @f0(i64 %x, i64 %y) {
+; CHECK-LABEL: Classifying expressions for: @f0
+entry:
+  %z = add i64 %x, 1
+  %cond = icmp sgt i64 %z, %y
+  %max = select i1 %cond, i64 %x, i64 %y
+; CHECK: %max = select i1 %cond, i64 %x, i64 %y
+; CHECK-NEXT: -->  (%x smax %y)
+  ret void
+}
+
+; Try to match the following pattern in function f1:
+; a+1 >s b ? b+x : a+x  ->  smin(a, b)+x
+define void @f1(i64 %x, i64 %y) {
+; CHECK-LABEL: Classifying expressions for: @f1
+entry:
+  %z = add i64 %x, 1
+  %cond = icmp sgt i64 %z, %y
+  %min = select i1 %cond, i64 %y, i64 %x
+; CHECK: %min = select i1 %cond, i64 %y, i64 %x
+; CHECK-NEXT: -->  (-1 + (-1 * ((-1 + (-1 * %x)) smax (-1 + (-1 * %y)))))
+  ret void
+}
+
+; Try to match the following pattern in function f2:
+; a+1 >u b ? a+x : b+x  ->  umax(a, b)+x
+define void @f2(i64 %x, i64 %y) {
+; CHECK-LABEL: Classifying expressions for: @f2
+entry:
+  %z = add i64 %x, 1
+  %cond = icmp ugt i64 %z, %y
+  %max = select i1 %cond, i64 %x, i64 %y
+; CHECK: %max = select i1 %cond, i64 %x, i64 %y
+; CHECK-NEXT: -->  (%x umax %y)
+  ret void
+}
+
+; Try to match the following pattern in function f3:
+; a+1 >u b ? b+x : a+x  ->  umin(a, b)+x
+define void @f3(i64 %x, i64 %y) {
+; CHECK-LABEL: Classifying expressions for: @f3
+entry:
+  %z = add i64 %x, 1
+  %cond = icmp ugt i64 %z, %y
+  %min = select i1 %cond, i64 %y, i64 %x
+; CHECK: %min = select i1 %cond, i64 %y, i64 %x
+; CHECK-NEXT: -->  (-1 + (-1 * ((-1 + (-1 * %x)) umax (-1 + (-1 * %y)))))
+  ret void
+}