[InstCombine] Transform A & (L - 1) u< L --> L != 0

[sanjoy]

Summary

This transform is never a pessimization at the IR level (since it
replaces an icmp with another), and has potentiall payoffs:

1. It may make the icmp fold away or become loop invariant.
2. It may make the A & (L - 1) computation dead.

This shows up in Java, in range checks generated by array accesses of
the form a[i & (a.length - 1)].

[majnemer]

lib/Transforms/InstCombine/InstCombineCompares.cpp

3495–3498 ↗

(On Diff #32730)

Isn't X - 1 always canonicalized to X + -1 ? Your transform is permitted to assume canonicalization occurred earlier.

3504 ↗

(On Diff #32730)

Might be more concise as auto *Zero = Constant::getNullValue(BO0->getType());

[reames]

test/Transforms/InstCombine/ult-and-bitwise-and.ll

5 ↗

(On Diff #32730)

Add a version of this test case with sub 1.

I think you need the fact that %lim is >= 0 for this to hold. Consider %lim with 0x101 and %val of 0x110. The original check fails, yours succeeds.

Also, I think that if the add is nsw, we can infer lim is > 0 and thus directly fold to true.

[majnemer]

Can we add the testcase to icmp.ll?

[sanjoy]

• address review

[sanjoy]

test/Transforms/InstCombine/ult-and-bitwise-and.ll

5 ↗

(On Diff #32730)

Add a version of this test case with sub 1.

Good idea, done (+ moved to icmp.ll as David suggested)

I think you need the fact that %lim is >= 0 for this to hold. Consider %lim with 0x101 and %val of 0x110. The original check fails, yours succeeds.

The original succeeds also -- the check is with val & (lim - 1) == 0x110 & 0x100 = 0x100 u< lim. val & (lim - 1) will always have a lesser or equal number of ones in its binary representation than lim - 1 and hence always will be ULE than lim - 1. lim - 1 is ULT than lim iff lim != 0. Thus val & (lim - 1) ULT lim iff lim != 0.

Also, I think that if the add is nsw, we can infer lim is > 0 and thus directly fold to true.

add nsw i32 0, -1 is not poison. I could do that inference if the instruction was sub nuw %lim, 1, but the sub will get canonicalized to add, and the nuw will then have to be dropped.

In any case, I'd rather not be aggressive about exploiting nuw and nsw unless there is good reason showing that it matters.

[majnemer]

lib/Transforms/InstCombine/InstCombineCompares.cpp

3503 ↗

(On Diff #32742)

I'd use Constant:: instead of ConstantInt:: to make it a little more clear. It is possible to get back a vector constant.

[sanjoy]

• address review

[sanjoy]

• run through clang-format

[majnemer]

LGTM

[chapuni]

Reverted in r245678.

See also; http://bb.pgr.jp/builders/clang-3stage-i686-linux/builds/2992

[escha]

llvm/trunk/lib/Transforms/InstCombine/InstCombineCompares.cpp

3495

Is it just me, or does this never even look at the RHS of the comparison?

It seems to be matching the following, despite the comment: A & (L - 1) ult M -> L != 0 for any M.

[sanjoy]

Yeah, the code is just wrong; I should have been more careful here.

Thanks for reverting, I'll fix this tomorrow.

Sent from a mobile device, please excuse typos.

[sanjoy]

Hi All,

I've checked in a fixed version in http://reviews.llvm.org/rL245753.
I was able to locally do a 3 stage bootstrap of clang with this
change, so hopefully there should be no more issues, but I'll keep an
eye on http://bb.pgr.jp/builders/clang-3stage-i686-linux till it sees
my change.

• Sanjoy

llvm/trunk/lib/Transforms/InstCombine/InstCombineCompares.cpp

if (BO0 && BO1 && BO0->getOpcode() == BO1->getOpcode() &&
           break;
         if (!NSW && I.isSigned())
           break;
         return new ICmpInst(I.getPredicate(), BO0->getOperand(0),
                             BO1->getOperand(0));
       }
       }
     }
+
+    if (BO0) {
+      // Transform  A & (L - 1) `ult` L --> L != 0
+      Value *L;
+      auto LSubOne = m_Add(m_Value(L), m_AllOnes());
+      auto BitwiseAnd =
+          m_CombineOr(m_And(m_Value(), LSubOne), m_And(LSubOne, m_Value()));
+
+      if (match(BO0, BitwiseAnd) && I.getPredicate() == ICmpInst::ICMP_ULT) {
+        auto *Zero = Constant::getNullValue(BO0->getType());
+        return new ICmpInst(ICmpInst::ICMP_NE, L, Zero);
+      }
+    }
   }
 
   { Value *A, *B;
     // Transform (A & ~B) == 0 --> (A & B) != 0
     // and       (A & ~B) != 0 --> (A & B) == 0
     // if A is a power of 2.
     if (match(Op0, m_And(m_Value(A), m_Not(m_Value(B)))) &&
         match(Op1, m_Zero()) &&

llvm/trunk/test/Transforms/InstCombine/icmp.ll

 ; CHECK-NEXT: ret i32 %s
 define i32 @f7(i32 %a, i32 %b) {
   %sext = shl i32 %a, 23
   %sext6 = shl i32 %b, 23
   %cmp = icmp ne i32 %sext, %sext6
   %s = select i1 %cmp, i32 10000, i32 0
   ret i32 %s
 }
+
+; CHECK: @f8(
+; CHECK-NEXT: [[RESULT:%[a-z0-9]+]] = icmp ne i32 %lim, 0
+; CHECK-NEXT: ret i1 [[RESULT]]
+define i1 @f8(i32 %val, i32 %lim) {
+  %lim.sub = add i32 %lim, -1
+  %val.and = and i32 %val, %lim.sub
+  %r = icmp ult i32 %val.and, %lim
+  ret i1 %r
+}
+
+; CHECK: @f9(
+; CHECK-NEXT: [[RESULT:%[a-z0-9]+]] = icmp ne i32 %lim, 0
+; CHECK-NEXT: ret i1 [[RESULT]]
+define i1 @f9(i32 %val, i32 %lim) {
+  %lim.sub = sub i32 %lim, 1
+  %val.and = and i32 %val, %lim.sub
+  %r = icmp ult i32 %val.and, %lim
+  ret i1 %r
+}