[LVI] Handle any predicate in comparisons like icmp <pred> (add Val, Offset), ...

[apilipenko]

Summary

Currently LVI can only gather value constraints from comparisons like:

• icmp <pred> Val, ...
• icmp ult (add Val, Offset), ...

In fact we can handle any predicate in latter comparisons.

[sanjoy]

lgtm

lib/Analysis/LazyValueInfo.cpp

static LVILatticeVal getValueFromICmpCondition(Value *Val, ICmpInst *ICI,
 
   if (!Val->getType()->isIntegerTy())
     return LVILatticeVal::getOverdefined();
 
   // Use ConstantRange::makeAllowedICmpRegion in order to determine the possible
   // range of Val guaranteed by the condition. Recognize comparisons in the from
   // of:
   //  icmp <pred> Val, ...
-  //  icmp ult (add Val, Offset), ...
+  //  icmp <pred> (add Val, Offset), ...
   // The latter is the range checking idiom that InstCombine produces. Subtract
   // the offset from the allowed range for RHS in this case.
 
   // Val or (add Val, Offset) can be on either hand of the comparison
   if (LHS != Val && !match(LHS, m_Add(m_Specific(Val), m_ConstantInt()))) {
     std::swap(LHS, RHS);
     Predicate = CmpInst::getSwappedPredicate(Predicate);
   }
 
   ConstantInt *Offset = nullptr;
-  if (Predicate == ICmpInst::ICMP_ULT)
+  if (LHS != Val)
     match(LHS, m_Add(m_Specific(Val), m_ConstantInt(Offset)));
 
   if (LHS == Val || Offset) {
     // Calculate the range of values that are allowed by the comparison
     ConstantRange RHSRange(RHS->getType()->getIntegerBitWidth(),
                            /*isFullSet=*/true);
     if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS))
       RHSRange = ConstantRange(CI->getValue());

test/Transforms/CorrelatedValuePropagation/range.ll

then:
   br i1 %dead, label %end, label %else
 
 else:
   ret i32 1
 
 end:
   ret i32 2
 }
+
+define i1 @test14_slt(i32 %a) {
+; CHECK-LABEL: @test14_slt(
+; CHECK: then:
+; CHECK-NEXT: %result = or i1 false, false
+  %a.off = add i32 %a, -8
+  %cmp = icmp slt i32 %a.off, 8
+  br i1 %cmp, label %then, label %else
+
+then:
+  %dead.1 = icmp eq i32 %a, -2147483641
+  %dead.2 = icmp eq i32 %a, 16
+  %result = or i1 %dead.1, %dead.2
+  ret i1 %result
+
+else:
+  ret i1 false
+}
+
+define i1 @test14_sle(i32 %a) {
+; CHECK-LABEL: @test14_sle(
+; CHECK: then:
+; CHECK-NEXT: %alive = icmp eq i32 %a, 16
+; CHECK-NEXT: %result = or i1 false, %alive
+  %a.off = add i32 %a, -8
+  %cmp = icmp sle i32 %a.off, 8
+  br i1 %cmp, label %then, label %else
+
+then:
+  %dead = icmp eq i32 %a, -2147483641
+  %alive = icmp eq i32 %a, 16
+  %result = or i1 %dead, %alive
+  ret i1 %result
+
+else:
+  ret i1 false
+}
+
+define i1 @test14_sgt(i32 %a) {
+; CHECK-LABEL: @test14_sgt(
+; CHECK: then:
+; CHECK-NEXT: %result = or i1 false, false
+  %a.off = add i32 %a, -8
+  %cmp = icmp sgt i32 %a.off, 8
+  br i1 %cmp, label %then, label %else
+
+then:
+  %dead.1 = icmp eq i32 %a, -2147483640
+  %dead.2 = icmp eq i32 %a, 16
+  %result = or i1 %dead.1, %dead.2
+  ret i1 %result
+
+else:
+  ret i1 false
+}
+
+define i1 @test14_sge(i32 %a) {
+; CHECK-LABEL: @test14_sge(
+; CHECK: then:
+; CHECK-NEXT: %alive = icmp eq i32 %a, 16
+; CHECK-NEXT: %result = or i1 false, %alive
+  %a.off = add i32 %a, -8
+  %cmp = icmp sge i32 %a.off, 8
+  br i1 %cmp, label %then, label %else
+
+then:
+  %dead = icmp eq i32 %a, -2147483640
+  %alive = icmp eq i32 %a, 16
+  %result = or i1 %dead, %alive
+  ret i1 %result
+
+else:
+  ret i1 false
+}
+
+define i1 @test14_ule(i32 %a) {
+; CHECK-LABEL: @test14_ule(
+; CHECK: then:
+; CHECK-NEXT: %alive = icmp eq i32 %a, 16
+; CHECK-NEXT: %result = or i1 false, %alive
+  %a.off = add i32 %a, -8
+  %cmp = icmp ule i32 %a.off, 8
+  br i1 %cmp, label %then, label %else
+
+then:
+  %dead = icmp eq i32 %a, 7
+  %alive = icmp eq i32 %a, 16
+  %result = or i1 %dead, %alive
+  ret i1 %result
+
+else:
+  ret i1 false
+}
+
+define i1 @test14_ugt(i32 %a) {
+; CHECK-LABEL: @test14_ugt(
+; CHECK: then:
+; CHECK-NEXT: %result = or i1 false, false
+  %a.off = add i32 %a, -8
+  %cmp = icmp ugt i32 %a.off, 8
+  br i1 %cmp, label %then, label %else
+
+then:
+  %dead.1 = icmp eq i32 %a, 8
+  %dead.2 = icmp eq i32 %a, 16
+  %result = or i1 %dead.1, %dead.2
+  ret i1 %result
+
+else:
+  ret i1 false
+}
+
+define i1 @test14_uge(i32 %a) {
+; CHECK-LABEL: @test14_uge(
+; CHECK: then:
+; CHECK-NEXT: %alive = icmp eq i32 %a, 16
+; CHECK-NEXT: %result = or i1 false, %alive
+  %a.off = add i32 %a, -8
+  %cmp = icmp uge i32 %a.off, 8
+  br i1 %cmp, label %then, label %else
+
+then:
+  %dead = icmp eq i32 %a, 8
+  %alive = icmp eq i32 %a, 16
+  %result = or i1 %dead, %alive
+  ret i1 %result
+
+else:
+  ret i1 false
+}