[InstCombine] Fold cmpeq/ne(and(~X,Y),0) --> cmpeq/ne(or(freeze(X),Y),freeze(X)) (PR44136)

[RKSimon]

Summary

Reverse of the backend fold from D100177 (PR44136), this is only valid if we freeze the not source value.

If we require the freeze we're not actually reducing the instruction count - should we limit this to cases where 'X' isGuaranteedNotToBeUndefOrPoison?

https://alive2.llvm.org/ce/z/PgAUx5
https://alive2.llvm.org/ce/z/8uRSz6

https://bugs.llvm.org/show_bug.cgi?id=44136

[nikic]

I'm somewhat doubtful that this fold will be beneficial if it requires inserting freeze. Is there some broader context here for which this is intended?

[xbolva00]

In D100211#2681688, @nikic wrote:

I'm somewhat doubtful that this fold will be beneficial if it requires inserting freeze. Is there some broader context here for which this is intended?

+1. So for now, use isGuaranteedNotToBeUndefOrPoison?

[RKSimon]

The missing middle-end fold was noted on the ticket (PR44136) - this patch is to show what would be necessary.

Limiting this to isGuaranteedNotToBeUndefOrPoison would be safer, although I'm not sure how common the case is tbh. Happy to abandon and close the ticket if this is pointless extra work.

@lebedev.ri any thoughts?

[lebedev.ri]

In D100211#2681777, @RKSimon wrote:

The missing middle-end fold was noted on the ticket (PR44136) - this patch is to show what would be necessary.

Limiting this to isGuaranteedNotToBeUndefOrPoison would be safer, although I'm not sure how common the case is tbh. Happy to abandon and close the ticket if this is pointless extra work.

@lebedev.ri any thoughts?

I'm not sure, which is why i haven't posted any patches after originally replying to the bug.

Right now i don't quite understand why we are so afraid of using freeze.
Can we not teach instcombine to hoist it?

Ignoring the freeze question, i think this is an improvement.

[nikic]

In D100211#2681777, @RKSimon wrote:

The missing middle-end fold was noted on the ticket (PR44136) - this patch is to show what would be necessary.

Limiting this to isGuaranteedNotToBeUndefOrPoison would be safer, although I'm not sure how common the case is tbh. Happy to abandon and close the ticket if this is pointless extra work.

Using isGuaranteedNotTobeUndefOrPoison() will just make the transform apply inconsistently. It seems to me like there is little motivation for doing this change (the report was about the reverse transform in the backend after all), so I'd drop the patch for now. Can be reconsidered when undef goes away or we establish policy to ignore undef optimization bugs.

[aqjune]

If freeze is ignored, this canonicalization helps optimizations like GVN to treat cmpeq (and(~X,Y),0) and cmpeq (or(X,Y),X) as equivalent ones, right?

If we're going to use freeze here, let's leave a comment saying e.g. TODO: if undef is removed, freeze is not needed: https://alive2.llvm.org/ce/z/V2Z4Lz
This will help finding out introduction of redundant freezes after undef is removed.

Regarding when to use freeze, I don't have a very good policy TBH. But, I agree that we cannot infinitely postpone usage of freeze.
There has been progress in SimplifyCFG and JumpThreading to successfully deal with frozen branch conditions.
If InstCombine is also updated to deal with freeze, it will be great.
A question is what kind of rules should we introduce first. It depends on which bug to fix; e.g. if we fix some fcmp bug using freeze, we'll need to update fp related optimizations to recognize freeze.

[RKSimon]

Abandoning for now, we can revisit this if/when people get more relaxed about using freeze()

[xbolva00]

In D100211#2682640, @RKSimon wrote:

Abandoning for now, we can revisit this if/when people get more relaxed about using freeze()

Can you create some umbrella PR for “transformations with freeze” (or something like that) on bugzilla ?
And add this there.

[RKSimon]

In D100211#2682728, @xbolva00 wrote:

In D100211#2682640, @RKSimon wrote:

Abandoning for now, we can revisit this if/when people get more relaxed about using freeze()

Can you create some umbrella PR for “transformations with freeze” (or something like that) on bugzilla ?
And add this there.

https://bugs.llvm.org/show_bug.cgi?id=49930

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

 }
 
 // Handle  icmp pred X, 0
 Instruction *InstCombinerImpl::foldICmpWithZero(ICmpInst &Cmp) {
   CmpInst::Predicate Pred = Cmp.getPredicate();
   if (!match(Cmp.getOperand(1), m_Zero()))
     return nullptr;
 
+  // (icmp eq and(~A, B) 0) -> (icmp eq or(freeze(A), B) A)
+  // (icmp ne and(~A, B) 0) -> (icmp ne or(freeze(A), B) A)
+  if (Pred == ICmpInst::ICMP_EQ || Pred == ICmpInst::ICMP_NE) {
+    Value *A, *B;
+    if (match(Cmp.getOperand(0),
+              m_OneUse(m_c_And(m_Not(m_Value(A)), m_Value(B))))) {
+      Value *NewA = Builder.CreateFreeze(A);
+      Value *NewOr = Builder.CreateOr(NewA, B);
+      return new ICmpInst(Pred, NewOr, NewA);
+    }
+  }
+
   // (icmp sgt smin(PosA, B) 0) -> (icmp sgt B 0)
   if (Pred == ICmpInst::ICMP_SGT) {
     Value *A, *B;
     SelectPatternResult SPR = matchSelectPattern(Cmp.getOperand(0), A, B);
     if (SPR.Flavor == SPF_SMIN) {
       if (isKnownPositive(A, DL, 0, &AC, &Cmp, &DT))
         return new ICmpInst(Pred, B, Cmp.getOperand(1));
       if (isKnownPositive(B, DL, 0, &AC, &Cmp, &DT))

llvm/test/Transforms/InstCombine/2010-11-23-Distributed.ll

;
   %mul = mul nsw i32 %add, %y
   %square = mul nsw i32 %y, %y
   %res = sub i32 %mul, %square
   ret i32 %res
 }
 
 define i1 @bar(i64 %x, i64 %y) {
 ; CHECK-LABEL: @bar(
-; CHECK-NEXT:    [[TMP1:%.*]] = xor i64 [[X:%.*]], -1
-; CHECK-NEXT:    [[B:%.*]] = and i64 [[TMP1]], [[Y:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i64 [[B]], 0
+; CHECK-NEXT:    [[TMP1:%.*]] = freeze i64 [[X:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = or i64 [[TMP1]], [[Y:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = icmp eq i64 [[TMP2]], [[TMP1]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %a = and i64 %y, %x
   %not = xor i64 %a, -1
   %b = and i64 %y, %not
   %r = icmp eq i64 %b, 0
   ret i1 %r
 }

llvm/test/Transforms/InstCombine/icmp.ll

;
   %2 = add nsw i32 %y, -20
   %cmp = icmp sge i32 %1, %2
   ret i1 %cmp
 }
 
 define i1 @icmp_and_shl_neg_ne_0(i32 %A, i32 %B) {
 ; CHECK-LABEL: @icmp_and_shl_neg_ne_0(
 ; CHECK-NEXT:    [[SHL:%.*]] = shl i32 1, [[B:%.*]]
-; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[SHL]], [[A:%.*]]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[TMP1]], 0
+; CHECK-NEXT:    [[TMP1:%.*]] = freeze i32 [[A:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], [[SHL]]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i32 [[TMP2]], [[TMP1]]
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %neg = xor i32 %A, -1
   %shl = shl i32 1, %B
   %and = and i32 %shl, %neg
   %cmp = icmp ne i32 %and, 0
   ret i1 %cmp
 }
 
 define i1 @icmp_and_shl_neg_eq_0(i32 %A, i32 %B) {
 ; CHECK-LABEL: @icmp_and_shl_neg_eq_0(
 ; CHECK-NEXT:    [[SHL:%.*]] = shl i32 1, [[B:%.*]]
-; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[SHL]], [[A:%.*]]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i32 [[TMP1]], 0
+; CHECK-NEXT:    [[TMP1:%.*]] = freeze i32 [[A:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], [[SHL]]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[TMP2]], [[TMP1]]
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %neg = xor i32 %A, -1
   %shl = shl i32 1, %B
   %and = and i32 %shl, %neg
   %cmp = icmp eq i32 %and, 0
   ret i1 %cmp
 }

llvm/test/Transforms/InstCombine/rem.ll

;
   %B = srem <2 x i32> %A, <i32 2147483648, i32 2147483648>
   %C = icmp ne <2 x i32> %B, zeroinitializer
   ret <2 x i1> %C
 }
 
 define i1 @test26(i32 %A, i32 %B) {
 ; CHECK-LABEL: @test26(
 ; CHECK-NEXT:    [[NOTMASK:%.*]] = shl nsw i32 -1, [[B:%.*]]
-; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[NOTMASK]], -1
-; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[A:%.*]]
-; CHECK-NEXT:    [[E:%.*]] = icmp ne i32 [[TMP2]], 0
+; CHECK-NEXT:    [[TMP1:%.*]] = freeze i32 [[NOTMASK]]
+; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], [[A:%.*]]
+; CHECK-NEXT:    [[E:%.*]] = icmp ne i32 [[TMP2]], [[TMP1]]
 ; CHECK-NEXT:    ret i1 [[E]]
 ;
   %C = shl i32 1, %B ; not a constant
   %D = srem i32 %A, %C
   %E = icmp ne i32 %D, 0
   ret i1 %E
 }