[SCEV] Model simple same base pointer `select`s via `umin_seq`

[lebedev.ri]

Summary

We can't model pointer selects (or even fully variable integer selects) in SCEV in their generality.

But, *IFF* we are selecting between pointers with the same base object,
we can instead decompose the pointers into pointer base + integer offset,
try to model the select of said integer offsets, and add the result
to the base pointer, thus modelling the original select,
because we do support limited modelling for partially-variable integer selects.

[nikic]

The general concept of modelling pointer selects as %base.ptr + (%cond ? %offset1 : %offset2) is pretty reasonable -- but the actual expressions produced for the integer select part are downright ridiculous. Is the SCEVExpander capable of reliably converting these back into a proper select? I feel like if this is something we want to model in SCEV, we should probably be adding a first-class select node.

[mkazantsev]

llvm/lib/Analysis/ScalarEvolution.cpp

6063

Does createNodeForSelectViaUMinSeq do anything useful for pointers? I guess it maybe an else-if then (with pointer check coming first).

llvm/lib/Analysis/ScalarEvolution.cpp

const SCEV *ScalarEvolution::createNodeForSelectOrPHIInstWithICmpInstCond(
   return getUnknown(I);
 }
 
 static Optional<const SCEV *>
 createNodeForSelectViaUMinSeq(ScalarEvolution *SE, const SCEV *CondExpr,
                               const SCEV *TrueExpr, const SCEV *FalseExpr) {
   assert(CondExpr->getType()->isIntegerTy(1) &&
          TrueExpr->getType() == FalseExpr->getType() &&
-         TrueExpr->getType()->isIntegerTy(1) &&
+         TrueExpr->getType()->isIntegerTy() &&
          "Unexpected operands of a select.");
 
-  // i1 cond ? i1 x : i1 C  -->  C + (i1  cond ? (i1 x - i1 C) : i1 0)
-  //                        -->  C + (umin_seq  cond, x - C)
+  // i1 cond ? iN x : iN C  -->  C + (i1  cond ? (iN x - iN C) : iN 0)
+  //                        -->  C + (umin_seq (sext  cond), x - C)
   //
-  // i1 cond ? i1 C : i1 x  -->  C + (i1  cond ? i1 0 : (i1 x - i1 C))
-  //                        -->  C + (i1 ~cond ? (i1 x - i1 C) : i1 0)
-  //                        -->  C + (umin_seq ~cond, x - C)
+  // i1 cond ? iN C : iN x  -->  C + (i1  cond ? iN 0 : (iN x - iN C))
+  //                        -->  C + (i1 ~cond ? (iN x - iN C) : iN 0)
+  //                        -->  C + (umin_seq (sext ~cond), x - C)
 
   // FIXME: while we can't legally model the case where both of the hands
   // are fully variable, we only require that the *difference* is constant.
   if (!isa<SCEVConstant>(TrueExpr) && !isa<SCEVConstant>(FalseExpr))
     return None;
 
   const SCEV *X, *C;
+  if (SE->getTypeSizeInBits(TrueExpr->getType()) >
+      SE->getTypeSizeInBits(CondExpr->getType()))
+    CondExpr = SE->getSignExtendExpr(CondExpr, TrueExpr->getType());
   if (isa<SCEVConstant>(TrueExpr)) {
     CondExpr = SE->getNotSCEV(CondExpr);
     X = FalseExpr;
     C = TrueExpr;
   } else {
     X = TrueExpr;
     C = FalseExpr;
   }

 
 const SCEV *ScalarEvolution::createNodeForSelectOrPHIViaUMinSeq(
     Value *V, Value *Cond, Value *TrueVal, Value *FalseVal) {
   assert(Cond->getType()->isIntegerTy(1) && "Select condition is not an i1?");
   assert(TrueVal->getType() == FalseVal->getType() &&
          V->getType() == TrueVal->getType() &&
          "Types of select hands and of the result must match.");
 
-  // For now, only deal with i1-typed `select`s.
-  if (!V->getType()->isIntegerTy(1))
+  // For now, only deal with i1-typed, or pointer-typed `select`s,
+  // but not arbitrary iN-typed `select`s.
+  if (!V->getType()->isIntegerTy(1) && !V->getType()->isPointerTy())
     return getUnknown(V);
 
   if (Optional<const SCEV *> S =
           createNodeForSelectViaUMinSeq(this, Cond, TrueVal, FalseVal))
     return *S;
 
+  if (V->getType()->isPointerTy()) {
+    // We can't model pointer selects in SCEV in their generality.
+    //
+    // But, *IFF* we are selecting between pointers with the same base object,
+    // we can instead decompose the pointers into pointer base + integer offset,
+    // try to model the select of said integer offsets, and add the result
+    // to the base pointer, thus modelling the original select.
+
+    const SCEV *TrueExpr = getSCEV(TrueVal);
+    const SCEV *FalseExpr = getSCEV(FalseVal);
+
+    const SCEV *TrueExprBasePtr = getPointerBase(TrueExpr);
+    const SCEV *FalseExprBasePtr = getPointerBase(FalseExpr);
+    if (TrueExprBasePtr == FalseExprBasePtr) {
+      const SCEV *BasePtrExpr = TrueExprBasePtr;
+      const SCEV *TrueOffsetExpr = removePointerBase(TrueExpr);
+      const SCEV *FalseOffsetExpr = removePointerBase(FalseExpr);
+
+      if (Optional<const SCEV *> OffsetSelect = createNodeForSelectViaUMinSeq(
+              this, getSCEV(Cond), TrueOffsetExpr, FalseOffsetExpr))
+        return getAddExpr(BasePtrExpr, *OffsetSelect);
+    }
+  }
+
   return getUnknown(V);
 }
 
 const SCEV *ScalarEvolution::createNodeForSelectOrPHI(Value *V, Value *Cond,
                                                       Value *TrueVal,
                                                       Value *FalseVal) {
   // Handle "constant" branch or select. This can occur for instance when a
   // loop pass transforms an inner loop and moves on to process the outer loop.

llvm/test/Analysis/ScalarEvolution/pointer-rounding.ll

 ; CHECK-NEXT:    --> (zext i4 (trunc i64 (ptrtoint ptr %obj to i64) to i4) to i64) U: [0,16) S: [0,16)
 ; CHECK-NEXT:    %i4 = sub nsw i64 0, %i2
 ; CHECK-NEXT:    --> (-1 * (zext i4 (trunc i64 (ptrtoint ptr %obj to i64) to i4) to i64))<nsw> U: [-15,1) S: [-15,1)
 ; CHECK-NEXT:    %i5 = getelementptr i8, ptr %obj, i64 %i4
 ; CHECK-NEXT:    --> ((-1 * (zext i4 (trunc i64 (ptrtoint ptr %obj to i64) to i4) to i64))<nsw> + %obj) U: full-set S: full-set
 ; CHECK-NEXT:    %i6 = getelementptr i8, ptr %i5, i64 16
 ; CHECK-NEXT:    --> (16 + (-1 * (zext i4 (trunc i64 (ptrtoint ptr %obj to i64) to i4) to i64))<nsw> + %obj) U: full-set S: full-set
 ; CHECK-NEXT:    %i7 = select i1 %i3, ptr %obj, ptr %i6
-; CHECK-NEXT:    --> %i7 U: full-set S: full-set
+; CHECK-NEXT:    --> (((-1 + (-1 * (sext i1 %i3 to i64))<nsw>)<nsw> umin_seq (16 + (-1 * (zext i4 (trunc i64 (ptrtoint ptr %obj to i64) to i4) to i64))<nsw>)<nsw>) + %obj) U: full-set S: full-set
 ; CHECK-NEXT:  Determining loop execution counts for: @pointer_align_up_with_select
 ;
   %i = ptrtoint ptr %obj to i64
   %i2 = and i64 %i, 15
   %i3 = icmp eq i64 %i2, 0
   %i4 = sub nsw i64 0, %i2
   %i5 = getelementptr i8, ptr %obj, i64 %i4
   %i6 = getelementptr i8, ptr %i5, i64 16

 ; CHECK-NEXT:    --> (zext i4 (trunc i64 (ptrtoint ptr %obj_donor to i64) to i4) to i64) U: [0,16) S: [0,16)
 ; CHECK-NEXT:    %i4 = sub nsw i64 0, %i2
 ; CHECK-NEXT:    --> (-1 * (zext i4 (trunc i64 (ptrtoint ptr %obj_donor to i64) to i4) to i64))<nsw> U: [-15,1) S: [-15,1)
 ; CHECK-NEXT:    %i5 = getelementptr i8, ptr %obj_to_align, i64 %i4
 ; CHECK-NEXT:    --> ((-1 * (zext i4 (trunc i64 (ptrtoint ptr %obj_donor to i64) to i4) to i64))<nsw> + %obj_to_align) U: full-set S: full-set
 ; CHECK-NEXT:    %i6 = getelementptr i8, ptr %i5, i64 16
 ; CHECK-NEXT:    --> (16 + (-1 * (zext i4 (trunc i64 (ptrtoint ptr %obj_donor to i64) to i4) to i64))<nsw> + %obj_to_align) U: full-set S: full-set
 ; CHECK-NEXT:    %i7 = select i1 %i3, ptr %obj_to_align, ptr %i6
-; CHECK-NEXT:    --> %i7 U: full-set S: full-set
+; CHECK-NEXT:    --> (((-1 + (-1 * (sext i1 %i3 to i64))<nsw>)<nsw> umin_seq (16 + (-1 * (zext i4 (trunc i64 (ptrtoint ptr %obj_donor to i64) to i4) to i64))<nsw>)<nsw>) + %obj_to_align) U: full-set S: full-set
 ; CHECK-NEXT:  Determining loop execution counts for: @pointer_align_up_with_select_different_donor
 ;
   %i = ptrtoint ptr %obj_donor to i64
   %i2 = and i64 %i, 15
   %i3 = icmp eq i64 %i2, 0
   %i4 = sub nsw i64 0, %i2
   %i5 = getelementptr i8, ptr %obj_to_align, i64 %i4
   %i6 = getelementptr i8, ptr %i5, i64 16

llvm/test/Analysis/ScalarEvolution/pointer-select.ll

 define ptr @pointer_select_same_object_constant_offsets(i1 %cond, ptr %obj) {
 ; CHECK-LABEL: 'pointer_select_same_object_constant_offsets'
 ; CHECK-NEXT:  Classifying expressions for: @pointer_select_same_object_constant_offsets
 ; CHECK-NEXT:    %true_ptr = getelementptr i8, ptr %obj, i64 42
 ; CHECK-NEXT:    --> (42 + %obj) U: full-set S: full-set
 ; CHECK-NEXT:    %false_ptr = getelementptr i8, ptr %obj, i64 24
 ; CHECK-NEXT:    --> (24 + %obj) U: full-set S: full-set
 ; CHECK-NEXT:    %r = select i1 %cond, ptr %true_ptr, ptr %false_ptr
-; CHECK-NEXT:    --> %r U: full-set S: full-set
+; CHECK-NEXT:    --> (42 + (-18 umin (-1 + (-1 * (sext i1 %cond to i64))<nsw>)<nsw>) + %obj) U: full-set S: full-set
 ; CHECK-NEXT:  Determining loop execution counts for: @pointer_select_same_object_constant_offsets
 ;
   %true_ptr = getelementptr i8, ptr %obj, i64 42
   %false_ptr = getelementptr i8, ptr %obj, i64 24
   %r = select i1 %cond, ptr %true_ptr, ptr %false_ptr
   ret ptr %r
 }
 

 define ptr @pointer_select_same_object_constant_offset_vs_variable_offset(i1 %cond, ptr %obj, i64 %false_off) {
 ; CHECK-LABEL: 'pointer_select_same_object_constant_offset_vs_variable_offset'
 ; CHECK-NEXT:  Classifying expressions for: @pointer_select_same_object_constant_offset_vs_variable_offset
 ; CHECK-NEXT:    %true_ptr = getelementptr i8, ptr %obj, i64 42
 ; CHECK-NEXT:    --> (42 + %obj) U: full-set S: full-set
 ; CHECK-NEXT:    %false_ptr = getelementptr i8, ptr %obj, i64 %false_off
 ; CHECK-NEXT:    --> (%false_off + %obj) U: full-set S: full-set
 ; CHECK-NEXT:    %r = select i1 %cond, ptr %true_ptr, ptr %false_ptr
-; CHECK-NEXT:    --> %r U: full-set S: full-set
+; CHECK-NEXT:    --> (42 + ((-1 + (-1 * (sext i1 %cond to i64))<nsw>)<nsw> umin_seq (-42 + %false_off)) + %obj) U: full-set S: full-set
 ; CHECK-NEXT:  Determining loop execution counts for: @pointer_select_same_object_constant_offset_vs_variable_offset
 ;
   %true_ptr = getelementptr i8, ptr %obj, i64 42
   %false_ptr = getelementptr i8, ptr %obj, i64 %false_off
   %r = select i1 %cond, ptr %true_ptr, ptr %false_ptr
   ret ptr %r
 }
 
 define ptr @pointer_select_same_object_variable_offset_vs_constant_offset(i1 %cond, ptr %obj, i64 %true_off) {
 ; CHECK-LABEL: 'pointer_select_same_object_variable_offset_vs_constant_offset'
 ; CHECK-NEXT:  Classifying expressions for: @pointer_select_same_object_variable_offset_vs_constant_offset
 ; CHECK-NEXT:    %true_ptr = getelementptr i8, ptr %obj, i64 %true_off
 ; CHECK-NEXT:    --> (%true_off + %obj) U: full-set S: full-set
 ; CHECK-NEXT:    %false_ptr = getelementptr i8, ptr %obj, i64 42
 ; CHECK-NEXT:    --> (42 + %obj) U: full-set S: full-set
 ; CHECK-NEXT:    %r = select i1 %cond, ptr %true_ptr, ptr %false_ptr
-; CHECK-NEXT:    --> %r U: full-set S: full-set
+; CHECK-NEXT:    --> (42 + ((sext i1 %cond to i64) umin_seq (-42 + %true_off)) + %obj) U: full-set S: full-set
 ; CHECK-NEXT:  Determining loop execution counts for: @pointer_select_same_object_variable_offset_vs_constant_offset
 ;
   %true_ptr = getelementptr i8, ptr %obj, i64 %true_off
   %false_ptr = getelementptr i8, ptr %obj, i64 42
   %r = select i1 %cond, ptr %true_ptr, ptr %false_ptr
   ret ptr %r
 }
 
 ;--
 
 define ptr @pointer_select_same_object_with_constant_base_offset__constant_offsets(i1 %cond, ptr %obj.base) {
 ; CHECK-LABEL: 'pointer_select_same_object_with_constant_base_offset__constant_offsets'
 ; CHECK-NEXT:  Classifying expressions for: @pointer_select_same_object_with_constant_base_offset__constant_offsets
 ; CHECK-NEXT:    %obj = getelementptr i8, ptr %obj.base, i64 12
 ; CHECK-NEXT:    --> (12 + %obj.base) U: full-set S: full-set
 ; CHECK-NEXT:    %true_ptr = getelementptr i8, ptr %obj, i64 42
 ; CHECK-NEXT:    --> (54 + %obj.base) U: full-set S: full-set
 ; CHECK-NEXT:    %false_ptr = getelementptr i8, ptr %obj, i64 24
 ; CHECK-NEXT:    --> (36 + %obj.base) U: full-set S: full-set
 ; CHECK-NEXT:    %r = select i1 %cond, ptr %true_ptr, ptr %false_ptr
-; CHECK-NEXT:    --> %r U: full-set S: full-set
+; CHECK-NEXT:    --> (54 + (-18 umin (-1 + (-1 * (sext i1 %cond to i64))<nsw>)<nsw>) + %obj.base) U: full-set S: full-set
 ; CHECK-NEXT:  Determining loop execution counts for: @pointer_select_same_object_with_constant_base_offset__constant_offsets
 ;
   %obj = getelementptr i8, ptr %obj.base, i64 12
   %true_ptr = getelementptr i8, ptr %obj, i64 42
   %false_ptr = getelementptr i8, ptr %obj, i64 24
   %r = select i1 %cond, ptr %true_ptr, ptr %false_ptr
   ret ptr %r
 }

 ; CHECK-NEXT:  Classifying expressions for: @pointer_select_same_object_with_constant_base_offset__constant_offset_vs_variable_offset
 ; CHECK-NEXT:    %obj = getelementptr i8, ptr %obj.base, i64 12
 ; CHECK-NEXT:    --> (12 + %obj.base) U: full-set S: full-set
 ; CHECK-NEXT:    %true_ptr = getelementptr i8, ptr %obj, i64 42
 ; CHECK-NEXT:    --> (54 + %obj.base) U: full-set S: full-set
 ; CHECK-NEXT:    %false_ptr = getelementptr i8, ptr %obj, i64 %false_off
 ; CHECK-NEXT:    --> (12 + %false_off + %obj.base) U: full-set S: full-set
 ; CHECK-NEXT:    %r = select i1 %cond, ptr %true_ptr, ptr %false_ptr
-; CHECK-NEXT:    --> %r U: full-set S: full-set
+; CHECK-NEXT:    --> (54 + ((-1 + (-1 * (sext i1 %cond to i64))<nsw>)<nsw> umin_seq (-42 + %false_off)) + %obj.base) U: full-set S: full-set
 ; CHECK-NEXT:  Determining loop execution counts for: @pointer_select_same_object_with_constant_base_offset__constant_offset_vs_variable_offset
 ;
   %obj = getelementptr i8, ptr %obj.base, i64 12
   %true_ptr = getelementptr i8, ptr %obj, i64 42
   %false_ptr = getelementptr i8, ptr %obj, i64 %false_off
   %r = select i1 %cond, ptr %true_ptr, ptr %false_ptr
   ret ptr %r
 }
 
 define ptr @pointer_select_same_object_with_constant_base_offset__variable_offset_vs_constant_offset(i1 %cond, ptr %obj.base, i64 %true_off) {
 ; CHECK-LABEL: 'pointer_select_same_object_with_constant_base_offset__variable_offset_vs_constant_offset'
 ; CHECK-NEXT:  Classifying expressions for: @pointer_select_same_object_with_constant_base_offset__variable_offset_vs_constant_offset
 ; CHECK-NEXT:    %obj = getelementptr i8, ptr %obj.base, i64 12
 ; CHECK-NEXT:    --> (12 + %obj.base) U: full-set S: full-set
 ; CHECK-NEXT:    %true_ptr = getelementptr i8, ptr %obj, i64 %true_off
 ; CHECK-NEXT:    --> (12 + %true_off + %obj.base) U: full-set S: full-set
 ; CHECK-NEXT:    %false_ptr = getelementptr i8, ptr %obj, i64 42
 ; CHECK-NEXT:    --> (54 + %obj.base) U: full-set S: full-set
 ; CHECK-NEXT:    %r = select i1 %cond, ptr %true_ptr, ptr %false_ptr
-; CHECK-NEXT:    --> %r U: full-set S: full-set
+; CHECK-NEXT:    --> (54 + ((sext i1 %cond to i64) umin_seq (-42 + %true_off)) + %obj.base) U: full-set S: full-set
 ; CHECK-NEXT:  Determining loop execution counts for: @pointer_select_same_object_with_constant_base_offset__variable_offset_vs_constant_offset
 ;
   %obj = getelementptr i8, ptr %obj.base, i64 12
   %true_ptr = getelementptr i8, ptr %obj, i64 %true_off
   %false_ptr = getelementptr i8, ptr %obj, i64 42
   %r = select i1 %cond, ptr %true_ptr, ptr %false_ptr
   ret ptr %r
 }