[InstCombine] Fold freeze(undef) into a proper constant

[aqjune]

Summary

This is a simple patch that folds freeze(undef) into a proper constant after inspecting its uses.

[nikic]

Do these show up in practice?

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

1803

So, these changes duplicate some undef folds from InstSimplify (here: https://github.com/llvm/llvm-project/blob/9b04fec0021112d913058e81bf864e4f33c33dcc/llvm/lib/Analysis/InstructionSimplify.cpp#L2004-L2006) into InstCombine.

I think it would be legal to instead make the fold in InstSimplify also work for one-use freeze of undef. Per the rules, the InstSimplify result needs to be used for a replacement, which will also remove the freeze. Of course, this will only really be safe in conjunction with D84792 for consumers that don't perform replacements.

Though maybe, if we consider the long-term direction (undef replaced by freeze poison), having it in InstCombine and dropping the InstSimplify folds may make more sense -- because we could also fold the multi-use case here, if we replace the whole freeze instruction.

[aqjune]

Hi, sorry for delay.

In D84948#2185163, @nikic wrote:

Do these show up in practice?

No, the motivation was from example test1_undef of D84818: if A.fr (which is optimized to freeze(undef)) was combined with or/and & used by a conditional branch, opt was still generating a sub-optimal code.
I thought it must appear at least once in real-world code, but my experiments say that it did not fire when compiling SPEC/testsuite with -O3 + LTO, interestingly. :/
However, wouldn't these folds be pretty low-cost? I think this can happen in a larger codebase as well.

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

1803

I think it depends on whether it is valid to replace a portion of uses with InstSimplify-ed value.
For example, even freeze has only one use, if and/or has multiple uses, this can still be problematic:

y = and (freeze undef), x
use(y)
use(y)

If (for some reason) the first use(y) is simplified to 0 but not the second use(y), the two uses will see different values, which is not valid.

If InstCombine isn't enough, we can properly fix each optimization to deal with it, IMO (e.g. JumpThreading). This seems to be a safer way to fix, albeit it may need more engineering.

[nikic]

Just as another possibility, we could simply always fold freeze undef to zeroinitializer in InstCombine (regardless of number of uses). This is not always the optimal fold, but usually a good one. At least at this point, I don't think freeze undef is expected to be common and it's more important to get rid of the freeze than find the best replacement.

[nikic]

In D84948#2197585, @nikic wrote:

Just as another possibility, we could simply always fold freeze undef to zeroinitializer in InstCombine (regardless of number of uses). This is not always the optimal fold, but usually a good one. At least at this point, I don't think freeze undef is expected to be common and it's more important to get rid of the freeze than find the best replacement.

To expand on this, if we want to handle multi-use freeze undef in the future, there's generally two ways that can work:

1. Individual folds for certain operators (as done here), but replacing the freeze itself with an advantageous value rather than just the operator.
2. Walking the uses of the freeze to find the best replacement value and replace all uses. (E.g. by counting for how many uses a certain value is favorable.)

The current patch would be the starting point for 1, my suggestion would be the starting point for 2.

I should say though that I'm also ok with your current patch.

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

1803

I don't think the InstSimplify contract allows replacing only some uses. If you replace your example with

y = and undef, x
use(y)
use(y)

and you replace only the first use with 0, then the second one could later get folded to x still, observing two different values of undef. I don't think the freeze makes a difference here.

Of course, not doing it in InstSimplify is still safer :)

[aqjune]

In D84948#2197854, @nikic wrote:

To expand on this, if we want to handle multi-use freeze undef in the future, there's generally two ways that can work:

1. Individual folds for certain operators (as done here), but replacing the freeze itself with an advantageous value rather than just the operator.
2. Walking the uses of the freeze to find the best replacement value and replace all uses. (E.g. by counting for how many uses a certain value is favorable.)

The current patch would be the starting point for 1, my suggestion would be the starting point for 2.

I should say though that I'm also ok with your current patch.

I think the second option really makes sense, I'll update this patch.

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

1803

In this case, it is fine because seeing different values of an undef is allowed to the users of users transitively.
Since undef represents a set of any value conceptually, and undef, x is a set of value that is a subset of bits of x, and each use can pick a value which one to see.
This allows, e.g. folding y = add undef, 1; use(y); use(y) into use(undef); use(undef).
Anyway, it is true that the behavior of undef is mysterious and hard to reason about..

[aqjune]

Iterate over uses of freeze(undef) and choose the best value

[nikic]

LGTM. There are various ways in which the value choice can be improved, but this looks like a good starting point.

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

3415 ↗

(On Diff #283487)

I would assert(BestValue && "Must have at least one use") here. Dead freeze should be cleaned by the main InstCombine loop already, so there must be at least one use here.

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

 //===- InstCombineAndOrXor.cpp --------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
Instruction *InstCombinerImpl::visitAnd(BinaryOperator &I) {
   // (A|B)&(A|C) -> A|(B&C) etc
   if (Value *V = SimplifyUsingDistributiveLaws(I))
     return replaceInstUsesWith(I, V);
 
   if (Value *V = SimplifyBSwap(I, Builder))
     return replaceInstUsesWith(I, V);
 
   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
+
+  // (freeze undef)&A -> 0
+  if (match(Op0, m_OneUse(m_Freeze(m_Undef()))) ||
+      match(Op1, m_OneUse(m_Freeze(m_Undef()))))
+    return replaceInstUsesWith(I, Constant::getNullValue(Op0->getType()));
+
   const APInt *C;
   if (match(Op1, m_APInt(C))) {
     Value *X, *Y;
     if (match(Op0, m_OneUse(m_LogicalShift(m_One(), m_Value(X)))) &&
         C->isOneValue()) {
       // (1 << X) & 1 --> zext(X == 0)
       // (1 >> X) & 1 --> zext(X == 0)
       Value *IsZero = Builder.CreateICmpEQ(X, ConstantInt::get(I.getType(), 0));
if (match(&I, m_c_Or(m_OneUse(m_Xor(m_Value(X), m_APInt(CV))), m_Value(Y))) &&
     // (X ^ C) | Y -> (X | Y) ^ C iff Y & C == 0
     // The check for a 'not' op is for efficiency (if Y is known zero --> ~X).
     Value *Or = Builder.CreateOr(X, Y);
     return BinaryOperator::CreateXor(Or, ConstantInt::get(I.getType(), *CV));
   }
 
   // (A & C)|(B & D)
   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
+
+  // (freeze undef)|A -> -1
+  if (match(Op0, m_OneUse(m_Freeze(m_Undef()))) ||
+      match(Op1, m_OneUse(m_Freeze(m_Undef()))))
+    return replaceInstUsesWith(I, Constant::getAllOnesValue(Op0->getType()));
+
   Value *A, *B, *C, *D;
   if (match(Op0, m_And(m_Value(A), m_Value(C))) &&
       match(Op1, m_And(m_Value(B), m_Value(D)))) {
     ConstantInt *C1 = dyn_cast<ConstantInt>(C);
     ConstantInt *C2 = dyn_cast<ConstantInt>(D);
     if (C1 && C2) {  // (A & C1)|(B & C2)
       Value *V1 = nullptr, *V2 = nullptr;
       if ((C1->getValue() & C2->getValue()).isNullValue()) {

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

 //===- InstCombineSelect.cpp ----------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
if (llvm::any_of(SI.users(), [&](User *U) {
           if (CI && CI->isEquality())
             return true;
           return false;
         })) {
       return nullptr;
     }
   }
 
+  // select (freeze undef), X, Y -> X
+  if (match(CondVal, m_OneUse(m_Freeze(m_Undef()))))
+    return replaceInstUsesWith(SI,
+                               isa<Constant>(FalseVal) ? FalseVal : TrueVal);
+
   if (Value *V = SimplifySelectInst(CondVal, TrueVal, FalseVal,
                                     SQ.getWithInstruction(&SI)))
     return replaceInstUsesWith(SI, V);
 
   if (Instruction *I = canonicalizeSelectToShuffle(SI))
     return I;
 
   if (Instruction *I = canonicalizeScalarSelectOfVecs(SI, *this))

llvm/test/Transforms/InstCombine/and.ll

 ; CHECK-NEXT:    [[R:%.*]] = lshr <2 x i59> [[TMP1]], <i59 5, i59 5>
 ; CHECK-NEXT:    ret <2 x i59> [[R]]
 ;
   %a = ashr <2 x i47> %x, <i47 5, i47 5>
   %s = sext <2 x i47> %a to <2 x i59>
   %r = and <2 x i59> %s, <i59 18014398509481983, i59 18014398509481983>  ;  -1 u>> 5 == 0x3f_ffff_ffff_ffff
   ret <2 x i59> %r
 }
+
+define i32 @and_freeze_undef(i32 %x) {
+; CHECK-LABEL: @and_freeze_undef(
+; CHECK-NEXT:    ret i32 0
+;
+  %f = freeze i32 undef
+  %res = and i32 %x, %f
+  ret i32 %res
+}
+
+declare void @use_i32(i32)
+
+define i32 @and_freeze_undef_multipleuses(i32 %x) {
+; CHECK-LABEL: @and_freeze_undef_multipleuses(
+; CHECK-NEXT:    [[F:%.*]] = freeze i32 undef
+; CHECK-NEXT:    [[RES:%.*]] = and i32 [[F]], [[X:%.*]]
+; CHECK-NEXT:    call void @use_i32(i32 [[F]])
+; CHECK-NEXT:    ret i32 [[RES]]
+;
+  %f = freeze i32 undef
+  %res = and i32 %x, %f
+  call void @use_i32(i32 %f)
+  ret i32 %res
+}

llvm/test/Transforms/InstCombine/or.ll

true:
   %sel = select i1 %and, i1 false, i1 true
   br label %end
 
 end:
   %t5 = phi i1 [ 0, %entry ], [ %sel, %true ]
   %conv8 = zext i1 %t5 to i32
   ret i32 %conv8
 }
+
+define i32 @or_freeze_undef(i32 %x) {
+; CHECK-LABEL: @or_freeze_undef(
+; CHECK-NEXT:    ret i32 -1
+;
+  %f = freeze i32 undef
+  %res = or i32 %x, %f
+  ret i32 %res
+}
+
+declare void @use_i32(i32)
+
+define i32 @or_freeze_undef_multipleuses(i32 %x) {
+; CHECK-LABEL: @or_freeze_undef_multipleuses(
+; CHECK-NEXT:    [[F:%.*]] = freeze i32 undef
+; CHECK-NEXT:    [[RES:%.*]] = or i32 [[F]], [[X:%.*]]
+; CHECK-NEXT:    call void @use_i32(i32 [[F]])
+; CHECK-NEXT:    ret i32 [[RES]]
+;
+  %f = freeze i32 undef
+  %res = or i32 %x, %f
+  call void @use_i32(i32 %f)
+  ret i32 %res
+}

llvm/test/Transforms/InstCombine/select.ll

 ; CHECK-NEXT:    ret <2 x i32> [[X:%.*]]
 ;
   %s = select i1 %cond, <2 x i32> undef, <2 x i32> %x
   ret <2 x i32> %s
 }
 
 define i8 @cond_freeze(i8 %x, i8 %y) {
 ; CHECK-LABEL: @cond_freeze(
-; CHECK-NEXT:    [[COND_FR:%.*]] = freeze i1 undef
-; CHECK-NEXT:    [[S:%.*]] = select i1 [[COND_FR]], i8 [[X:%.*]], i8 [[Y:%.*]]
-; CHECK-NEXT:    ret i8 [[S]]
+; CHECK-NEXT:    ret i8 [[X:%.*]]
 ;
   %cond.fr = freeze i1 undef
   %s = select i1 %cond.fr, i8 %x, i8 %y
   ret i8 %s
 }
 
 define i8 @cond_freeze2(i8 %x, i8 %y) {
 ; CHECK-LABEL: @cond_freeze2(
-; CHECK-NEXT:    [[COND_FR:%.*]] = freeze i1 undef
-; CHECK-NEXT:    [[S:%.*]] = select i1 [[COND_FR]], i8 [[X:%.*]], i8 1
-; CHECK-NEXT:    ret i8 [[S]]
+; CHECK-NEXT:    ret i8 1
 ;
   %cond.fr = freeze i1 undef
   %s = select i1 %cond.fr, i8 %x, i8 1
   ret i8 %s
 }
 
 declare void @foo2(i8, i8)