[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 ↗

(On Diff #281923)

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 ↗

(On Diff #281923)

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 ↗

(On Diff #281923)

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 ↗

(On Diff #281923)

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

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/InstructionCombining.cpp

if (Value *V = SimplifyFreezeInst(Op0, SQ.getWithInstruction(&I)))
     return replaceInstUsesWith(I, V);
 
   // freeze (phi const, x) --> phi const, (freeze x)
   if (auto *PN = dyn_cast<PHINode>(Op0)) {
     if (Instruction *NV = foldOpIntoPhi(I, PN))
       return NV;
   }
 
+  if (match(Op0, m_Undef())) {
+    // If I is freeze(undef), see its uses and fold it to the best constant.
+    // - or: pick -1
+    // - select's condition: pick the value that leads to choosing a constant
+    // - other ops: pick 0
+    Constant *BestValue = nullptr;
+    Constant *NullValue = Constant::getNullValue(I.getType());
+    for (const auto *U : I.users()) {
+      Constant *C = NullValue;
+
+      if (match(U, m_Or(m_Value(), m_Value())))
+        C = Constant::getAllOnesValue(I.getType());
+      else if (const auto *SI = dyn_cast<SelectInst>(U)) {
+        if (SI->getCondition() == &I) {
+          APInt CondVal(1, isa<Constant>(SI->getFalseValue()) ? 0 : 1);
+          C = Constant::getIntegerValue(I.getType(), CondVal);
+        }
+      }
+
+      if (!BestValue)
+        BestValue = C;
+      else if (BestValue != C)
+        BestValue = NullValue;
+    }
+
+    return replaceInstUsesWith(I, BestValue);
+  }
+
   return nullptr;
 }
 
 /// Try to move the specified instruction from its current block into the
 /// beginning of DestBlock, which can only happen if it's safe to move the
 /// instruction past all of the instructions between it and the end of its
 /// block.
 static bool TryToSinkInstruction(Instruction *I, BasicBlock *DestBlock) {

llvm/test/Transforms/InstCombine/freeze-phi.ll

 
 define i32 @one_undef(i8 %cond) {
 ; CHECK-LABEL: @one_undef(
 ; CHECK-NEXT:    switch i8 [[COND:%.*]], label [[A:%.*]] [
 ; CHECK-NEXT:    i8 0, label [[B:%.*]]
 ; CHECK-NEXT:    i8 1, label [[C:%.*]]
 ; CHECK-NEXT:    ]
 ; CHECK:       A:
-; CHECK-NEXT:    [[PHI_FR:%.*]] = freeze i32 undef
 ; CHECK-NEXT:    br label [[D:%.*]]
 ; CHECK:       B:
 ; CHECK-NEXT:    br label [[D]]
 ; CHECK:       C:
 ; CHECK-NEXT:    br label [[D]]
 ; CHECK:       D:
-; CHECK-NEXT:    [[Y:%.*]] = phi i32 [ [[PHI_FR]], [[A]] ], [ 32, [[B]] ], [ 0, [[C]] ]
+; CHECK-NEXT:    [[Y:%.*]] = phi i32 [ 0, [[A]] ], [ 32, [[B]] ], [ 0, [[C]] ]
 ; CHECK-NEXT:    ret i32 [[Y]]
 ;
   switch i8 %cond, label %A [
   i8 0, label %B
   i8 1, label %C
   ]
 A:
   br label %D

llvm/test/Transforms/InstCombine/freeze.ll

 ; CHECK-NEXT:    ret i32 10
 ;
   %x = freeze i32 10
   ret i32 %x
 }
 
 define i32 @and_freeze_undef(i32 %x) {
 ; CHECK-LABEL: @and_freeze_undef(
-; CHECK-NEXT:    [[F:%.*]] = freeze i32 undef
-; CHECK-NEXT:    [[RES:%.*]] = and i32 [[F]], [[X:%.*]]
-; CHECK-NEXT:    ret i32 [[RES]]
+; 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]]
+; CHECK-NEXT:    call void @use_i32(i32 0)
+; CHECK-NEXT:    ret i32 0
 ;
   %f = freeze i32 undef
   %res = and i32 %x, %f
   call void @use_i32(i32 %f)
   ret i32 %res
 }
 
 define i32 @or_freeze_undef(i32 %x) {
 ; CHECK-LABEL: @or_freeze_undef(
-; CHECK-NEXT:    [[F:%.*]] = freeze i32 undef
-; CHECK-NEXT:    [[RES:%.*]] = or i32 [[F]], [[X:%.*]]
-; CHECK-NEXT:    ret i32 [[RES]]
+; CHECK-NEXT:    ret i32 -1
 ;
   %f = freeze i32 undef
   %res = or i32 %x, %f
   ret i32 %res
 }
 
 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]]
+; CHECK-NEXT:    call void @use_i32(i32 0)
+; CHECK-NEXT:    ret i32 [[X:%.*]]
 ;
   %f = freeze i32 undef
   %res = or i32 %x, %f
   call void @use_i32(i32 %f)
   ret i32 %res
 }
 
 declare void @use_i32_i1(i32, i1)
 
 define void @or_select_multipleuses(i32 %x, i1 %y) {
 ; CHECK-LABEL: @or_select_multipleuses(
-; CHECK-NEXT:    [[F:%.*]] = freeze i1 undef
-; CHECK-NEXT:    [[A:%.*]] = select i1 [[F]], i32 [[X:%.*]], i32 32
-; CHECK-NEXT:    [[B:%.*]] = or i1 [[F]], [[Y:%.*]]
-; CHECK-NEXT:    call void @use_i32_i1(i32 [[A]], i1 [[B]])
+; CHECK-NEXT:    call void @use_i32_i1(i32 32, i1 [[Y:%.*]])
 ; CHECK-NEXT:    ret void
 ;
   %f = freeze i1 undef
   %a = select i1 %f, i32 %x, i32 32 ; prefers %f to be false
   %b = or i1 %f, %y ; prefers %f to be true
   call void @use_i32_i1(i32 %a, i1 %b)
   ret void
 }

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
 }
 
 define i8 @cond_freeze3(i8 %x) {
 ; CHECK-LABEL: @cond_freeze3(
-; CHECK-NEXT:    [[COND_FR:%.*]] = freeze i1 undef
-; CHECK-NEXT:    [[S:%.*]] = select i1 [[COND_FR]], i8 1, i8 [[X:%.*]]
-; CHECK-NEXT:    ret i8 [[S]]
+; CHECK-NEXT:    ret i8 1
 ;
   %cond.fr = freeze i1 undef
   %s = select i1 %cond.fr, i8 1, i8 %x
   ret i8 %s
 }
 
 define <2 x i8> @cond_freeze_vec(<2 x i8> %x) {
 ; CHECK-LABEL: @cond_freeze_vec(
-; CHECK-NEXT:    [[COND_FR:%.*]] = freeze <2 x i1> undef
-; CHECK-NEXT:    [[S:%.*]] = select <2 x i1> [[COND_FR]], <2 x i8> <i8 1, i8 2>, <2 x i8> [[X:%.*]]
-; CHECK-NEXT:    ret <2 x i8> [[S]]
+; CHECK-NEXT:    ret <2 x i8> <i8 1, i8 2>
 ;
   %cond.fr = freeze <2 x i1> <i1 undef, i1 undef>
   %s = select <2 x i1> %cond.fr, <2 x i8> <i8 1, i8 2>, <2 x i8> %x
   ret <2 x i8> %s
 }
 
 declare void @foo2(i8, i8)
 
 define void @cond_freeze_multipleuses(i8 %x, i8 %y) {
 ; CHECK-LABEL: @cond_freeze_multipleuses(
-; CHECK-NEXT:    [[COND_FR:%.*]] = freeze i1 undef
-; CHECK-NEXT:    [[S:%.*]] = select i1 [[COND_FR]], i8 [[X:%.*]], i8 [[Y:%.*]]
-; CHECK-NEXT:    [[S2:%.*]] = select i1 [[COND_FR]], i8 [[Y]], i8 [[X]]
-; CHECK-NEXT:    call void @foo2(i8 [[S]], i8 [[S2]])
+; CHECK-NEXT:    call void @foo2(i8 [[X:%.*]], i8 [[Y:%.*]])
 ; CHECK-NEXT:    ret void
 ;
   %cond.fr = freeze i1 undef
   %s = select i1 %cond.fr, i8 %x, i8 %y
   %s2 = select i1 %cond.fr, i8 %y, i8 %x
   call void @foo2(i8 %s, i8 %s2)
   ret void
 }