[InstCombine] Strip offset when folding and/or of icmps

[nikic]

Summary

When folding and/or of icmps, look through add of a constant and adjust the icmp range instead. Effectively, this decomposes X + C1 < C2 style range checks back into a normal range. This allows us to fold comparisons involving two range checks or one range check and some other condition. We had a fold for a really specific case of this (or of range check and eq, and only one one side!) while this handles it in fully generality.

[nikic]

I expect this will subsume a few more folds strewn about, such as https://github.com/llvm/llvm-project/blob/24e07e1cf58841601287dca3df55078041dde00d/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp#L777-L789. However, this fold needs to be expanded to support splats first (which is trivial, but affects a number of folds under the same branch, so I'll do that separately).

[spatel]

Nice!

I don't see any test diffs with 2 signed preds. Is there any value in adding a test like that to further exercise the range logic?

define i1 @src(i64 %x) {
  %t1 = add i64 %x, 127
  %t2 = icmp slt i64 %t1, 1024
  %t3 = add i64 %x, 128
  %t4 = icmp slt i64 %t3, 256
  %t5 = and i1 %t2, %t4
  ret i1 %t5
}

llvm/test/Transforms/InstCombine/signed-truncation-check.ll

957–958

It's not a single instruction, but don't need this comment now.

[nikic]

Rebase over test with signed preds (https://alive2.llvm.org/ce/z/qv9MZr), drop outdated comment.

I actually thought that we were already canonicalizing signed range checks to unsigned ones, but apparently we aren't.

[lebedev.ri]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

1209–1221

What about the case where both of them are add's,
but we should have matched only one of them,
i.e. y = x + C0; q = ((y + C1) < C2) | (y < C3) ?

2467

Hm, but that new code expects two add's.

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

1209–1221

Can this happen though? In canonical IR this will get folded to (x + (C1 + C0) < C2) | (x + C0 < C3), at which point we have the expected pattern. (In non-canonical IR this is not the case, but that shouldn't be a problem as this is not a question of correctness -- the fold will apply only once it has become canonical.)

2467

It doesn't require both comparisons to have an add. We can have an add on neither, both or one of them (this pattern).

[lebedev.ri]

LG, @spatel ?

[spatel]

LGTM

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

1209–1210

On first look, I also didn't catch that this block will match either 1 or 2 offsets, so we should make that clear in the code comment.
Something like:

// Look through add of a constant offset on V1, V2, or both operands...

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

 
 /// Fold (icmp Pred1 V1, C1) & (icmp Pred2 V2, C2)
 /// or   (icmp Pred1 V1, C1) | (icmp Pred2 V2, C2)
 /// into a single comparison using range-based reasoning.
 static Value *foldAndOrOfICmpsUsingRanges(
     ICmpInst::Predicate Pred1, Value *V1, const APInt &C1,
     ICmpInst::Predicate Pred2, Value *V2, const APInt &C2,
     IRBuilderBase &Builder, bool IsAnd) {
+  // Look through addition of a constant offset. This allows us to interpret
+  // the V + C' < C'' range idiom into a proper range.
+  const APInt *Offset1 = nullptr, *Offset2 = nullptr;
+  if (V1 != V2) {
+    Value *X;
+    if (match(V1, m_Add(m_Value(X), m_APInt(Offset1))))
+      V1 = X;
+    if (match(V2, m_Add(m_Value(X), m_APInt(Offset2))))
+      V2 = X;
+  }
+
   if (V1 != V2)
     return nullptr;
 
   ConstantRange CR1 = ConstantRange::makeExactICmpRegion(Pred1, C1);
+  if (Offset1)
+    CR1 = CR1.subtract(*Offset1);
+
   ConstantRange CR2 = ConstantRange::makeExactICmpRegion(Pred2, C2);
+  if (Offset2)
+    CR2 = CR2.subtract(*Offset2);
+
   Optional<ConstantRange> CR =
       IsAnd ? CR1.exactIntersectWith(CR2) : CR1.exactUnionWith(CR2);
   if (!CR)
     return nullptr;
 
   CmpInst::Predicate NewPred;
   APInt NewC, Offset;
   CR->getEquivalentICmp(NewPred, NewC, Offset);
if (PredL == ICmpInst::ICMP_NE && match(LHS1, m_Zero()) &&
     return Builder.CreateICmp(PredL, NewOr,
                               Constant::getNullValue(NewOr->getType()));
   }
 
   // This only handles icmp of constants: (icmp1 A, C1) | (icmp2 B, C2).
   if (!LHSC || !RHSC)
     return nullptr;
 
-  // (icmp ult (X + CA), C1) | (icmp eq X, C2) -> (icmp ule (X + CA), C1)
-  //   iff C2 + CA == C1.
-  if (PredL == ICmpInst::ICMP_ULT && PredR == ICmpInst::ICMP_EQ) {
-    ConstantInt *AddC;
-    if (match(LHS0, m_Add(m_Specific(RHS0), m_ConstantInt(AddC))))
-      if (RHSC->getValue() + AddC->getValue() == LHSC->getValue())
-        return Builder.CreateICmpULE(LHS0, LHSC);
-  }
-
   return foldAndOrOfICmpsUsingRanges(PredL, LHS0, LHSC->getValue(),
                                      PredR, RHS0, RHSC->getValue(),
                                      Builder, /* IsAnd */ false);
 }
 
 // FIXME: We use commutative matchers (m_c_*) for some, but not all, matches
 // here. We should standardize that construct where it is needed or choose some
 // other way to ensure that commutated variants of patterns are not missed.

llvm/test/Transforms/InstCombine/and-or-icmps.ll

;
   call void @use(i1 %c2)
   %r = select i1 %c2, i1 true, i1 %c1
   ret i1 %r
 }
 
 define i1 @or_ranges_overlap(i8 %x) {
 ; CHECK-LABEL: @or_ranges_overlap(
 ; CHECK-NEXT:    [[TMP1:%.*]] = add i8 [[X:%.*]], -5
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp ult i8 [[TMP1]], 6
-; CHECK-NEXT:    [[TMP3:%.*]] = add i8 [[X]], -10
-; CHECK-NEXT:    [[TMP4:%.*]] = icmp ult i8 [[TMP3]], 11
-; CHECK-NEXT:    [[C7:%.*]] = or i1 [[TMP2]], [[TMP4]]
-; CHECK-NEXT:    ret i1 [[C7]]
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp ult i8 [[TMP1]], 16
+; CHECK-NEXT:    ret i1 [[TMP2]]
 ;
   %c1 = icmp uge i8 %x, 5
   %c2 = icmp ule i8 %x, 10
   %c3 = and i1 %c1, %c2
   %c4 = icmp uge i8 %x, 10
   %c5 = icmp ule i8 %x, 20
   %c6 = and i1 %c4, %c5
   %c7 = or i1 %c3, %c6
   ret i1 %c7
 }
 
 define i1 @or_ranges_adjacent(i8 %x) {
 ; CHECK-LABEL: @or_ranges_adjacent(
 ; CHECK-NEXT:    [[TMP1:%.*]] = add i8 [[X:%.*]], -5
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp ult i8 [[TMP1]], 6
-; CHECK-NEXT:    [[TMP3:%.*]] = add i8 [[X]], -11
-; CHECK-NEXT:    [[TMP4:%.*]] = icmp ult i8 [[TMP3]], 10
-; CHECK-NEXT:    [[C7:%.*]] = or i1 [[TMP2]], [[TMP4]]
-; CHECK-NEXT:    ret i1 [[C7]]
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp ult i8 [[TMP1]], 16
+; CHECK-NEXT:    ret i1 [[TMP2]]
 ;
   %c1 = icmp uge i8 %x, 5
   %c2 = icmp ule i8 %x, 10
   %c3 = and i1 %c1, %c2
   %c4 = icmp uge i8 %x, 11
   %c5 = icmp ule i8 %x, 20
   %c6 = and i1 %c4, %c5
   %c7 = or i1 %c3, %c6
;
   %c3 = and i1 %c1, %c2
   %c4 = icmp eq i8 %x, 11
   %c6 = or i1 %c3, %c4
   ret i1 %c6
 }
 
 define i1 @or_ranges_single_elem_left(i8 %x) {
 ; CHECK-LABEL: @or_ranges_single_elem_left(
-; CHECK-NEXT:    [[TMP1:%.*]] = add i8 [[X:%.*]], -5
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp ult i8 [[TMP1]], 6
-; CHECK-NEXT:    [[C4:%.*]] = icmp eq i8 [[X]], 4
-; CHECK-NEXT:    [[C6:%.*]] = or i1 [[TMP2]], [[C4]]
-; CHECK-NEXT:    ret i1 [[C6]]
+; CHECK-NEXT:    [[TMP1:%.*]] = add i8 [[X:%.*]], -4
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp ult i8 [[TMP1]], 7
+; CHECK-NEXT:    ret i1 [[TMP2]]
 ;
   %c1 = icmp uge i8 %x, 5
   %c2 = icmp ule i8 %x, 10
   %c3 = and i1 %c1, %c2
   %c4 = icmp eq i8 %x, 4
   %c6 = or i1 %c3, %c4
   ret i1 %c6
 }
 
 define i1 @and_ranges_overlap(i8 %x) {
 ; CHECK-LABEL: @and_ranges_overlap(
-; CHECK-NEXT:    [[TMP1:%.*]] = add i8 [[X:%.*]], -5
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp ult i8 [[TMP1]], 6
-; CHECK-NEXT:    [[TMP3:%.*]] = add i8 [[X]], -7
-; CHECK-NEXT:    [[TMP4:%.*]] = icmp ult i8 [[TMP3]], 14
-; CHECK-NEXT:    [[C7:%.*]] = and i1 [[TMP2]], [[TMP4]]
-; CHECK-NEXT:    ret i1 [[C7]]
+; CHECK-NEXT:    [[TMP1:%.*]] = add i8 [[X:%.*]], -7
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp ult i8 [[TMP1]], 4
+; CHECK-NEXT:    ret i1 [[TMP2]]
 ;
   %c1 = icmp uge i8 %x, 5
   %c2 = icmp ule i8 %x, 10
   %c3 = and i1 %c1, %c2
   %c4 = icmp uge i8 %x, 7
   %c5 = icmp ule i8 %x, 20
   %c6 = and i1 %c4, %c5
   %c7 = and i1 %c3, %c6
   ret i1 %c7
 }
 
 define i1 @and_ranges_overlap_single(i8 %x) {
 ; CHECK-LABEL: @and_ranges_overlap_single(
-; CHECK-NEXT:    [[TMP1:%.*]] = add i8 [[X:%.*]], -5
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp ult i8 [[TMP1]], 6
-; CHECK-NEXT:    [[TMP3:%.*]] = add i8 [[X]], -10
-; CHECK-NEXT:    [[TMP4:%.*]] = icmp ult i8 [[TMP3]], 11
-; CHECK-NEXT:    [[C7:%.*]] = and i1 [[TMP2]], [[TMP4]]
-; CHECK-NEXT:    ret i1 [[C7]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i8 [[X:%.*]], 10
+; CHECK-NEXT:    ret i1 [[TMP1]]
 ;
   %c1 = icmp uge i8 %x, 5
   %c2 = icmp ule i8 %x, 10
   %c3 = and i1 %c1, %c2
   %c4 = icmp uge i8 %x, 10
   %c5 = icmp ule i8 %x, 20
   %c6 = and i1 %c4, %c5
   %c7 = and i1 %c3, %c6
   ret i1 %c7
 }
 
 define i1 @and_ranges_no_overlap(i8 %x) {
 ; CHECK-LABEL: @and_ranges_no_overlap(
-; CHECK-NEXT:    [[TMP1:%.*]] = add i8 [[X:%.*]], -5
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp ult i8 [[TMP1]], 6
-; CHECK-NEXT:    [[TMP3:%.*]] = add i8 [[X]], -11
-; CHECK-NEXT:    [[TMP4:%.*]] = icmp ult i8 [[TMP3]], 10
-; CHECK-NEXT:    [[C7:%.*]] = and i1 [[TMP2]], [[TMP4]]
-; CHECK-NEXT:    ret i1 [[C7]]
+; CHECK-NEXT:    ret i1 false
 ;
   %c1 = icmp uge i8 %x, 5
   %c2 = icmp ule i8 %x, 10
   %c3 = and i1 %c1, %c2
   %c4 = icmp uge i8 %x, 11
   %c5 = icmp ule i8 %x, 20
   %c6 = and i1 %c4, %c5
   %c7 = and i1 %c3, %c6
   ret i1 %c7
 }
 
 define i1 @and_ranges_signed_pred(i64 %x) {
 ; CHECK-LABEL: @and_ranges_signed_pred(
-; CHECK-NEXT:    [[T1:%.*]] = add i64 [[X:%.*]], 127
-; CHECK-NEXT:    [[T2:%.*]] = icmp slt i64 [[T1]], 1024
-; CHECK-NEXT:    [[T3:%.*]] = add i64 [[X]], 128
-; CHECK-NEXT:    [[T4:%.*]] = icmp slt i64 [[T3]], 256
-; CHECK-NEXT:    [[T5:%.*]] = and i1 [[T2]], [[T4]]
-; CHECK-NEXT:    ret i1 [[T5]]
+; CHECK-NEXT:    [[TMP1:%.*]] = add i64 [[X:%.*]], -9223372036854775681
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp ult i64 [[TMP1]], -9223372036854775553
+; CHECK-NEXT:    ret i1 [[TMP2]]
 ;
   %t1 = add i64 %x, 127
   %t2 = icmp slt i64 %t1, 1024
   %t3 = add i64 %x, 128
   %t4 = icmp slt i64 %t3, 256
   %t5 = and i1 %t2, %t4
   ret i1 %t5
 }

llvm/test/Transforms/InstCombine/or.ll

;
   %cmp1 = icmp ult <2 x i32> %add1, <i32 30, i32 undef>
   %cmp2 = icmp eq <2 x i32> %x, <i32 23, i32 undef>
   %ret1 = or <2 x i1> %cmp1, %cmp2
   ret <2 x i1> %ret1
 }
 
 define i1 @test38(i32 %x) {
 ; CHECK-LABEL: @test38(
-; CHECK-NEXT:    [[ADD1:%.*]] = add i32 [[X:%.*]], 7
-; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i32 [[X]], 23
-; CHECK-NEXT:    [[CMP2:%.*]] = icmp ult i32 [[ADD1]], 30
-; CHECK-NEXT:    [[RET1:%.*]] = or i1 [[CMP1]], [[CMP2]]
-; CHECK-NEXT:    ret i1 [[RET1]]
+; CHECK-NEXT:    [[TMP1:%.*]] = add i32 [[X:%.*]], 7
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp ult i32 [[TMP1]], 31
+; CHECK-NEXT:    ret i1 [[TMP2]]
 ;
   %add1 = add i32 %x, 7
   %cmp1 = icmp eq i32 %x, 23
   %cmp2 = icmp ult i32 %add1, 30
   %ret1 = or i1 %cmp1, %cmp2
   ret i1 %ret1
 }
 
 define i1 @test38_logical(i32 %x) {
 ; CHECK-LABEL: @test38_logical(
-; CHECK-NEXT:    [[ADD1:%.*]] = add i32 [[X:%.*]], 7
-; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i32 [[X]], 23
-; CHECK-NEXT:    [[CMP2:%.*]] = icmp ult i32 [[ADD1]], 30
-; CHECK-NEXT:    [[RET1:%.*]] = or i1 [[CMP1]], [[CMP2]]
-; CHECK-NEXT:    ret i1 [[RET1]]
+; CHECK-NEXT:    [[TMP1:%.*]] = add i32 [[X:%.*]], 7
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp ult i32 [[TMP1]], 31
+; CHECK-NEXT:    ret i1 [[TMP2]]
 ;
   %add1 = add i32 %x, 7
   %cmp1 = icmp eq i32 %x, 23
   %cmp2 = icmp ult i32 %add1, 30
   %ret1 = select i1 %cmp1, i1 true, i1 %cmp2
   ret i1 %ret1
 }
 

llvm/test/Transforms/InstCombine/signed-truncation-check.ll

;
   %t2 = add i32 %arg, 256 ; should be less than 256
   %t3 = icmp ult i32 %t2, 256
   %t4 = select i1 %t1, i1 %t3, i1 false
   ret i1 %t4
 }
 
 define i1 @negative_not_power_of_two(i32 %arg) {
 ; CHECK-LABEL: @negative_not_power_of_two(
-; CHECK-NEXT:    [[T1:%.*]] = icmp sgt i32 [[ARG:%.*]], -1
-; CHECK-NEXT:    [[T2:%.*]] = add i32 [[ARG]], 255
-; CHECK-NEXT:    [[T3:%.*]] = icmp ult i32 [[T2]], 256
-; CHECK-NEXT:    [[T4:%.*]] = and i1 [[T1]], [[T3]]
-; CHECK-NEXT:    ret i1 [[T4]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i32 [[ARG:%.*]], 0
+; CHECK-NEXT:    ret i1 [[TMP1]]
 ;
   %t1 = icmp sgt i32 %arg, -1
   %t2 = add i32 %arg, 255 ; should be power of two
   %t3 = icmp ult i32 %t2, 256
   %t4 = and i1 %t1, %t3
   ret i1 %t4
 }
 
 define i1 @negative_not_power_of_two_logical(i32 %arg) {
 ; CHECK-LABEL: @negative_not_power_of_two_logical(
-; CHECK-NEXT:    [[T1:%.*]] = icmp sgt i32 [[ARG:%.*]], -1
-; CHECK-NEXT:    [[T2:%.*]] = add i32 [[ARG]], 255
-; CHECK-NEXT:    [[T3:%.*]] = icmp ult i32 [[T2]], 256
-; CHECK-NEXT:    [[T4:%.*]] = and i1 [[T1]], [[T3]]
-; CHECK-NEXT:    ret i1 [[T4]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i32 [[ARG:%.*]], 0
+; CHECK-NEXT:    ret i1 [[TMP1]]
 ;
   %t1 = icmp sgt i32 %arg, -1
   %t2 = add i32 %arg, 255 ; should be power of two
   %t3 = icmp ult i32 %t2, 256
   %t4 = select i1 %t1, i1 %t3, i1 false
   ret i1 %t4
 }
 
 define i1 @negative_not_next_power_of_two(i32 %arg) {
 ; CHECK-LABEL: @negative_not_next_power_of_two(
-; CHECK-NEXT:    [[T1:%.*]] = icmp sgt i32 [[ARG:%.*]], -1
-; CHECK-NEXT:    [[T2:%.*]] = add i32 [[ARG]], 64
-; CHECK-NEXT:    [[T3:%.*]] = icmp ult i32 [[T2]], 256
-; CHECK-NEXT:    [[T4:%.*]] = and i1 [[T1]], [[T3]]
-; CHECK-NEXT:    ret i1 [[T4]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ult i32 [[ARG:%.*]], 192
+; CHECK-NEXT:    ret i1 [[TMP1]]
 ;
   %t1 = icmp sgt i32 %arg, -1
   %t2 = add i32 %arg, 64 ; should be 256 >> 1
   %t3 = icmp ult i32 %t2, 256
   %t4 = and i1 %t1, %t3
   ret i1 %t4
 }
 
 define i1 @negative_not_next_power_of_two_logical(i32 %arg) {
 ; CHECK-LABEL: @negative_not_next_power_of_two_logical(
-; CHECK-NEXT:    [[T1:%.*]] = icmp sgt i32 [[ARG:%.*]], -1
-; CHECK-NEXT:    [[T2:%.*]] = add i32 [[ARG]], 64
-; CHECK-NEXT:    [[T3:%.*]] = icmp ult i32 [[T2]], 256
-; CHECK-NEXT:    [[T4:%.*]] = and i1 [[T1]], [[T3]]
-; CHECK-NEXT:    ret i1 [[T4]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ult i32 [[ARG:%.*]], 192
+; CHECK-NEXT:    ret i1 [[TMP1]]
 ;
   %t1 = icmp sgt i32 %arg, -1
   %t2 = add i32 %arg, 64 ; should be 256 >> 1
   %t3 = icmp ult i32 %t2, 256
   %t4 = select i1 %t1, i1 %t3, i1 false
   ret i1 %t4
 }
 
-; I don't think this can be folded, at least not into single instruction.
 define i1 @two_signed_truncation_checks(i32 %arg) {
 ; CHECK-LABEL: @two_signed_truncation_checks(
-; CHECK-NEXT:    [[T1:%.*]] = add i32 [[ARG:%.*]], 512
-; CHECK-NEXT:    [[T2:%.*]] = icmp ult i32 [[T1]], 1024
-; CHECK-NEXT:    [[T3:%.*]] = add i32 [[ARG]], 128
-; CHECK-NEXT:    [[T4:%.*]] = icmp ult i32 [[T3]], 256
-; CHECK-NEXT:    [[T5:%.*]] = and i1 [[T2]], [[T4]]
-; CHECK-NEXT:    ret i1 [[T5]]
+; CHECK-NEXT:    [[TMP1:%.*]] = add i32 [[ARG:%.*]], 128
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp ult i32 [[TMP1]], 256
+; CHECK-NEXT:    ret i1 [[TMP2]]
 ;
   %t1 = add i32 %arg, 512
   %t2 = icmp ult i32 %t1, 1024
   %t3 = add i32 %arg, 128
   %t4 = icmp ult i32 %t3, 256
   %t5 = and i1 %t2, %t4
   ret i1 %t5
 }
 
 define i1 @two_signed_truncation_checks_logical(i32 %arg) {
 ; CHECK-LABEL: @two_signed_truncation_checks_logical(
-; CHECK-NEXT:    [[T1:%.*]] = add i32 [[ARG:%.*]], 512
-; CHECK-NEXT:    [[T2:%.*]] = icmp ult i32 [[T1]], 1024
-; CHECK-NEXT:    [[T3:%.*]] = add i32 [[ARG]], 128
-; CHECK-NEXT:    [[T4:%.*]] = icmp ult i32 [[T3]], 256
-; CHECK-NEXT:    [[T5:%.*]] = and i1 [[T2]], [[T4]]
-; CHECK-NEXT:    ret i1 [[T5]]
+; CHECK-NEXT:    [[TMP1:%.*]] = add i32 [[ARG:%.*]], 128
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp ult i32 [[TMP1]], 256
+; CHECK-NEXT:    ret i1 [[TMP2]]
 ;
   %t1 = add i32 %arg, 512
   %t2 = icmp ult i32 %t1, 1024
   %t3 = add i32 %arg, 128
   %t4 = icmp ult i32 %t3, 256
   %t5 = select i1 %t2, i1 %t4, i1 false
   ret i1 %t5
 }