[LVI] Make LVI smarter about comparisons with non-constants

[apilipenko]

Summary

Make LVI smarter about comparisons with a non-constant. For example, a s< b constraints a to be in [INT_MIN, INT_MAX) range. This is a part of https://llvm.org/bugs/show_bug.cgi?id=28620 fix.

Note that this patch is based on D23200 and few minor refactorings in getValueFromICmpCondition (extraction of RHS, LHS, Predicate locals, renaming NegOffset to Offset) which were not included to simplify the review.

[sanjoy]

lib/Analysis/LazyValueInfo.cpp

1205

Do you mean icmp ult Val, ...?

1220–1221

Please make this change to how we implement !isTrueDest separately. IMO it _should_ be NFC, but is tricky enough that it should not go in with other changes.

[edit: I understand that *with your change* this isn't NFC, and actually needed for correctness -- so I think this should go in separately as NFC before this change since given the state of LVI today it is NFC.]

1229

Can you please explicitly pass in /*isFullSet=*/true to the constructor? The fact that RHSRange is the full set is important here.

1232–1233

Minor: a ternary operator for Pred may be more readable here.

[apilipenko]

Address review comments, false dest handling was landed separately as NFC.

[apilipenko]

lib/Analysis/LazyValueInfo.cpp

1205

No, this code can handle any predicate.

The predicate limitation for icmp ult (add Val, Offset), ... conditions is somewhat artificial it comes from the existing code. As a separate change I'm going to support arbitrary predicates for conditions in this form as well.

[sanjoy]

lgtm!

lib/Analysis/LazyValueInfo.cpp

1205

In that case, I think

icmp <pred> Val, ...

will be clearer.

[sanjoy]

lgtm again (forgot to set 'Accept Revision' the last time).

lib/Analysis/LazyValueInfo.cpp

if (ICI->isEquality() && LHS == Val) {
       // We know that V has the RHS constant if this is a true SETEQ or
       // false SETNE.
       if (isTrueDest == (Predicate == ICmpInst::ICMP_EQ))
         Result = LVILatticeVal::get(cast<Constant>(RHS));
       else
         Result = LVILatticeVal::getNot(cast<Constant>(RHS));
       return true;
     }
+  }
+
+  // Use ConstantRange::makeAllowedICmpRegion in order to determine the possible
+  // range of Val guaranteed by the condition. Recognize comparisons in the from
+  // of:
+  //  icmp Val, ...
+  //  icmp ult (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);
+  }
 
-    // Recognize the range checking idiom that InstCombine produces.
-    // (X+C1) u< C2 --> [-C1, C2-C1)
-    ConstantInt *Offset = nullptr;
-    if (Predicate == ICmpInst::ICMP_ULT)
-      match(LHS, m_Add(m_Specific(Val), m_ConstantInt(Offset)));
 
-    ConstantInt *CI = dyn_cast<ConstantInt>(RHS);
-    if (CI && (LHS == Val || Offset)) {
-      // Calculate the range of values that are allowed by the comparison
-      ConstantRange CmpRange(CI->getValue());
+  if (LHS == Val || Offset) {
+    ConstantRange RHSRange(RHS->getType()->getIntegerBitWidth(),
+                           /*isFullSet=*/true);
+    if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS))
+      RHSRange = ConstantRange(CI->getValue());
 
-      // If we're interested in the false dest, invert the condition
-      CmpInst::Predicate Pred =
             isTrueDest ? Predicate : CmpInst::getInversePredicate(Predicate);
-      ConstantRange TrueValues =
-          ConstantRange::makeAllowedICmpRegion(Pred, CmpRange);
+            ConstantRange::makeAllowedICmpRegion(Pred, RHSRange);
 
-      if (Offset) // Apply the offset from above.
-        TrueValues = TrueValues.subtract(Offset->getValue());
 
-      Result = LVILatticeVal::getRange(std::move(TrueValues));
-      return true;
-    }
-  }
 
   return false;
 }
 
 /// \brief Compute the value of Val on the edge BBFrom -> BBTo. Returns false if
 /// Val is not constrained on the edge.  Result is unspecified if return value
 /// is false.
 static bool getEdgeValueLocal(Value *Val, BasicBlock *BBFrom,

test/Transforms/CorrelatedValuePropagation/range.ll

; CHECK: ret i1 true
   %positive = load i32, i32* @g, !range !{i32 1, i32 2048}
   %add = add i32 %positive, 1
   %test = icmp sgt i32 %add, 0
   br label %next
 
 next:
   ret i1 %test
 }
+
+define i32 @test12(i32 %a, i32 %b) {
+; CHECK-LABEL: @test12(
+; CHECK: then:
+; CHECK-NEXT: br i1 false, label %end, label %else
+  %cmp = icmp ult i32 %a, %b
+  br i1 %cmp, label %then, label %else
+
+then:
+  %dead = icmp eq i32 %a, -1
+  br i1 %dead, label %end, label %else
+
+else:
+  ret i32 1
+
+end:
+  ret i32 2
+}
+
+define i32 @test12_swap(i32 %a, i32 %b) {
+; CHECK-LABEL: @test12_swap(
+; CHECK: then:
+; CHECK-NEXT: br i1 false, label %end, label %else
+  %cmp = icmp ugt i32 %b, %a
+  br i1 %cmp, label %then, label %else
+
+then:
+  %dead = icmp eq i32 %a, -1
+  br i1 %dead, label %end, label %else
+
+else:
+  ret i32 1
+
+end:
+  ret i32 2
+}
+
+define i32 @test12_neg(i32 %a, i32 %b) {
+; The same as @test12 but the second check is on the false path
+; CHECK-LABEL: @test12_neg(
+; CHECK: else:
+; CHECK-NEXT: %alive = icmp eq i32 %a, -1
+  %cmp = icmp ult i32 %a, %b
+  br i1 %cmp, label %then, label %else
+
+else:
+  %alive = icmp eq i32 %a, -1
+  br i1 %alive, label %end, label %then
+
+then:
+  ret i32 1
+
+end:
+  ret i32 2
+}
+
+define i32 @test12_signed(i32 %a, i32 %b) {
+; The same as @test12 but with signed comparison
+; CHECK-LABEL: @test12_signed(
+; CHECK: then:
+; CHECK-NEXT: br i1 false, label %end, label %else
+  %cmp = icmp slt i32 %a, %b
+  br i1 %cmp, label %then, label %else
+
+then:
+  %dead = icmp eq i32 %a, 2147483647
+  br i1 %dead, label %end, label %else
+
+else:
+  ret i32 1
+
+end:
+  ret i32 2
+}
+
+define i32 @test13(i32 %a, i32 %b) {
+; CHECK-LABEL: @test13(
+; CHECK: then:
+; CHECK-NEXT: br i1 false, label %end, label %else
+  %a.off = add i32 %a, -8
+  %cmp = icmp ult i32 %a.off, %b
+  br i1 %cmp, label %then, label %else
+
+then:
+  %dead = icmp eq i32 %a, 7
+  br i1 %dead, label %end, label %else
+
+else:
+  ret i32 1
+
+end:
+  ret i32 2
+}
+
+define i32 @test13_swap(i32 %a, i32 %b) {
+; CHECK-LABEL: @test13_swap(
+; CHECK: then:
+; CHECK-NEXT: br i1 false, label %end, label %else
+  %a.off = add i32 %a, -8
+  %cmp = icmp ugt i32 %b, %a.off
+  br i1 %cmp, label %then, label %else
+
+then:
+  %dead = icmp eq i32 %a, 7
+  br i1 %dead, label %end, label %else
+
+else:
+  ret i32 1
+
+end:
+  ret i32 2
+}