[InstCombine] Fold icmp(constants[x]) when the range of x is given

[XChy]

Summary

This patch extends foldCmpLoadFromIndexedGlobal to fold IR below:

define i1 @cmp_load_constant_array0(i64 %x){
entry:
  %cond = icmp ult i64 %x, 2
  br i1 %cond, label %case1, label %case2

case2:
  ret i1 0

case1:
  %isOK_ptr = getelementptr inbounds i32, ptr @CG, i64 %x
  %isOK = load i32, ptr %isOK_ptr
  %cond_inferred = icmp ult i32 %isOK, 3
  ret i1 %cond_inferred
}

Problem still:
Not globally optimized best.
Here I think if D152838 is accepted, that would be better.

Proof:
alive2

Related issue:
issue

[nikic]

This should be handled by the foldCmpLoadFromIndexedGlobal() fold, by first converting the icmp(load(gep(g, idx))) into icmp(idx) and then folding that icmp against the dominating condition.

That fold currently requires a very specific GEP source element type, but should be easy to generalize.

[XChy]

In D156657#4546067, @nikic wrote:

This should be handled by the foldCmpLoadFromIndexedGlobal() fold, by first converting the icmp(load(gep(g, idx))) into icmp(idx) and then folding that icmp against the dominating condition.

That fold currently requires a very specific GEP source element type, but should be easy to generalize.

Sure, I'll have a check.

[XChy]

Extends foldCmpLoadFromIndexedGlobal to fold.

[XChy]

Update tests.

[nikic]

It would be better to base this on collectOffset() and work in offset representation. Especially if you're interested in handling Rust, the type of the global and the GEP / loads will typically not line up (constant globals in Rust are usually i8 arrays, regardless of "real" type.)

[XChy]

In D156657#4547304, @nikic wrote:

It would be better to base this on collectOffset() and work in offset representation. Especially if you're interested in handling Rust, the type of the global and the GEP / loads will typically not line up (constant globals in Rust are usually i8 arrays, regardless of "real" type.)

Yes, such generlization in units of byte is necessary. It seems to be related to ptradd RFC?
Currently, this fold is still in units of array element . I'll try to refactor and generlize it.

llvm/test/Transforms/InstCombine/load-cmp.ll

349 ↗

(On Diff #545637)

Optimized well locally, but not globally.

[XChy]

Complete basically correct fold.

TODOs:

• Multi-variable testcases, Bitwidth-changed testcases
• Comments
• Performance/optimization to improve. When index is ax + by + .... + C, the longest distance we can step by is gcd(a,b,c,d, ....), not just one. Based on this we fold more precisely.

[nikic]

I think to start with, you should limit this to just the case where there is exactly one variable index (i.e. C*x or C*x+C2). Handling complex expressions is unlikely to be useful.

[XChy]

Already limit it to one variable. But I don't know why it is unlikely to be useful. From my perspective For multi-dimensional arrays, it's possible to have more than one index variable.

Besides, there exists miscompilation, I found just now. Current state-machine doesn't emit the CmpInst/Poison to guarrantee the index/offset is always not negative. Lack of such range-check would lead to something triggering UB not to doing so. I need to check it later.

[XChy]

In D156657#4550996, @XChy wrote:

Already limit it to one variable. But I don't know why it is unlikely to be useful. From my perspective For multi-dimensional arrays, it's possible to have more than one index variable.

Besides, there exists miscompilation, I found just now. Current state-machine doesn't emit the CmpInst/Poison to guarrantee the index/offset is always not negative. Lack of such range-check would lead to something triggering UB not to doing so. I need to check it later.

After trying, I don't think there is any way to do boundary-check (let things out of boundary lead to load poison) without modifying CFG. But InstCombine doesn't modify CFG. I haven't better idea here.

[XChy]

Update tests and FIXME: Boundary-check

[nikic]

Besides, there exists miscompilation, I found just now. Current state-machine doesn't emit the CmpInst/Poison to guarrantee the index/offset is always not negative. Lack of such range-check would lead to something triggering UB not to doing so. I need to check it later.

It's okay for transforms to remove UB (this is called "refinement" and done by many transforms). You just can't introduce new UB / poison that did not exist before.

[XChy]

Eliminate boundary-check.

[XChy]

Simplify LazyGetIndex function, and ready to be reviewed.

[XChy]

ping.

[goldstein.w.n]

In D156657#4639543, @XChy wrote:

ping.

nikic is on vacation for the next week, since he requested changes plan to let him get to it when he comes back.
Might have time to review later in the week, however.

[XChy]

In D156657#4639867, @goldstein.w.n wrote:

In D156657#4639543, @XChy wrote:

ping.

nikic is on vacation for the next week, since he requested changes plan to let him get to it when he comes back.
Might have time to review later in the week, however.

Thanks. That's OK. I hope this patch could be finished before the Phabricator shutdowns.

[XChy]

Polish comments.

llvm/lib/Analysis/ValueTracking.cpp

static std::optional<bool> isImpliedCondCommonOperandWithConstants(
   ConstantRange Difference = DomCR.difference(CR);
   if (Intersection.isEmptySet())
     return false;
   if (Difference.isEmptySet())
     return true;
   return std::nullopt;
 }
 
+bool matchLoadConstantArrayWithConstant(const LoadInst *LI,
+                                        const GetElementPtrInst *GEP,
+                                        const Value *Index, Constant *&ConstArray) {
+
+  if (GEP->getOperand(1) != Index || GEP->getNumIndices() != 1)
+    return false;
+
+  auto *GV = dyn_cast<GlobalVariable>(GEP->getOperand(0));
+
+  if (!GV || LI->isVolatile() || LI->getType() != GEP->getResultElementType() ||
+      GV->getValueType()->getArrayElementType() !=
+          GEP->getSourceElementType() ||
+      !GV->isConstant() || !GV->hasDefinitiveInitializer())
+    return false;
+
+  Constant *Init = GV->getInitializer();
+  if (!isa<ConstantArray>(Init) && !isa<ConstantDataArray>(Init))
+    return false;
+
+  ConstArray = Init;
+  return true;
+}
+
+static std::optional<bool> isImpliedCondLoadConstantArrayWithConstant(
+    Value *Index, CmpInst::Predicate LPred, const APInt &LC,
+    GetElementPtrInst *GEP, CmpInst::Predicate RPred, const APInt &RC,
+    Constant *ConstArray) {
+  unsigned BitWidth = GEP->getSourceElementType()->getScalarSizeInBits();
+  ConstantRange IndexCR = ConstantRange::makeExactICmpRegion(LPred, LC);
+  int64_t MinIndex = IndexCR.getSignedMin().getSExtValue();
+  int64_t MaxIndex = IndexCR.getSignedMax().getSExtValue();
+  int64_t ElementCount = ConstArray->getType()->getArrayNumElements();
+  if (MaxIndex >= ElementCount || MinIndex < 0)
+    return std::nullopt;
+
+  ConstantRange DomCR = ConstantRange::getEmpty(BitWidth);
+  for (int64_t i = MinIndex; i <= MaxIndex; ++i) {
+    APInt Element = ConstArray->getAggregateElement(i)->getUniqueInteger();
+    DomCR = DomCR.unionWith(ConstantRange::getNonEmpty(Element, Element + 1));
+  }
+  ConstantRange CR = ConstantRange::makeExactICmpRegion(RPred, RC);
+
+  ConstantRange Intersection = DomCR.intersectWith(CR);
+  ConstantRange Difference = DomCR.difference(CR);
+  if (Intersection.isEmptySet())
+    return false;
+  if (Difference.isEmptySet())
+    return true;
+  return std::nullopt;
+}
+
 /// Return true if LHS implies RHS (expanded to its components as "R0 RPred R1")
 /// is true.  Return false if LHS implies RHS is false. Otherwise, return
 /// std::nullopt if we can't infer anything.
 static std::optional<bool> isImpliedCondICmps(const ICmpInst *LHS,
                                               CmpInst::Predicate RPred,
                                               const Value *R0, const Value *R1,
                                               const DataLayout &DL,
                                               bool LHSIsTrue, unsigned Depth) {
if (areMatchingOperands(L0, L1, R0, R1, AreSwappedOps))
     return isImpliedCondMatchingOperands(LPred, RPred, AreSwappedOps);
 
   // Can we infer anything when the 0-operands match and the 1-operands are
   // constants (not necessarily matching)?
   const APInt *LC, *RC;
   if (L0 == R0 && match(L1, m_APInt(LC)) && match(R1, m_APInt(RC)))
     return isImpliedCondCommonOperandWithConstants(LPred, *LC, RPred, *RC);
 
+  Value *Loaded;
+  Constant* ConstArray;
+  GetElementPtrInst *GEP;
+  if (match(L1, m_APInt(LC)) && match(R1, m_APInt(RC)) &&
+      match(R0, m_Load(m_Value(Loaded))) &&
+      (GEP = dyn_cast<GetElementPtrInst>(Loaded)) &&
+      matchLoadConstantArrayWithConstant(cast<LoadInst>(R0), GEP, L0,
+                                         ConstArray))
+    return isImpliedCondLoadConstantArrayWithConstant(L0, LPred, *LC, GEP,
+                                                      RPred, *RC, ConstArray);
+
   if (LPred == RPred)
     return isImpliedCondOperands(LPred, L0, L1, R0, R1, DL, Depth);
 
   return std::nullopt;
 }
 
 /// Return true if LHS implies RHS is true.  Return false if LHS implies RHS is
 /// false.  Otherwise, return std::nullopt if we can't infer anything.  We

llvm/test/Transforms/InstCombine/load-cmp-index.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 2
 ; RUN: opt -passes=instcombine -S < %s | FileCheck %s
 
 @CG = constant [4 x i32] [i32 1, i32 2, i32 3, i32 4]
 
 define i1 @cmp_load_constant_array0(i64 %x){
 ; CHECK-LABEL: define i1 @cmp_load_constant_array0
 ; CHECK-SAME: (i64 [[X:%.*]]) {
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[COND:%.*]] = icmp ult i64 [[X]], 2
 ; CHECK-NEXT:    br i1 [[COND]], label [[CASE1:%.*]], label [[CASE2:%.*]]
 ; CHECK:       case2:
 ; CHECK-NEXT:    ret i1 false
 ; CHECK:       case1:
-; CHECK-NEXT:    [[ISOK_PTR:%.*]] = getelementptr inbounds i32, ptr @CG, i64 [[X]]
-; CHECK-NEXT:    [[ISOK:%.*]] = load i32, ptr [[ISOK_PTR]], align 4
-; CHECK-NEXT:    [[COND_INFERRED:%.*]] = icmp ult i32 [[ISOK]], 3
-; CHECK-NEXT:    ret i1 [[COND_INFERRED]]
+; CHECK-NEXT:    ret i1 true
 ;
 entry:
   %cond = icmp ult i64 %x, 2
   br i1 %cond, label %case1, label %case2
 
 case2:
   ret i1 0
 
 case1:
   %isOK_ptr = getelementptr inbounds i32, ptr @CG, i64 %x
   %isOK = load i32, ptr %isOK_ptr
   %cond_inferred = icmp ult i32 %isOK, 3
   ret i1 %cond_inferred
 }
 
 define i1 @cmp_load_constant_array1(i64 %x){
 ; CHECK-LABEL: define i1 @cmp_load_constant_array1
 ; CHECK-SAME: (i64 [[X:%.*]]) {
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[COND:%.*]] = icmp ult i64 [[X]], 2
 ; CHECK-NEXT:    br i1 [[COND]], label [[CASE1:%.*]], label [[CASE2:%.*]]
 ; CHECK:       case2:
 ; CHECK-NEXT:    ret i1 false
 ; CHECK:       case1:
-; CHECK-NEXT:    [[ISOK_PTR:%.*]] = getelementptr inbounds i32, ptr @CG, i64 [[X]]
-; CHECK-NEXT:    [[ISOK:%.*]] = load i32, ptr [[ISOK_PTR]], align 4
-; CHECK-NEXT:    [[COND_INFERRED:%.*]] = icmp ugt i32 [[ISOK]], 10
-; CHECK-NEXT:    ret i1 [[COND_INFERRED]]
+; CHECK-NEXT:    ret i1 false
 ;
 entry:
   %cond = icmp ult i64 %x, 2
   br i1 %cond, label %case1, label %case2
 
 case2:
   ret i1 0