Revert "[InstCombine] Handle undef when pruning unreachable code"

[tsymalla]

Summary

This reverts commit 1fc425380e9860a6beb53fa68d02e7fb14969963.
This is causing some test failures in cases like

for (;;) {
	callIntrinsicStore...
	switch (undef) {
		case 0:
			break;
	}
}

where LLVM is completely optimizing away the loop. The IR in mind is
something like the following.
So, independent of which jump target we take in 10, we will still be
able to reach the final merge block. With the optimization, the loop
body (add) wil be optimized away and we will never reach the merge
block.

entry:
  br label %0

0:
  br label %1, !llvm.loop

1:
  br label %2

2:
  %3 = phi i32 [ 0, %1 ], [ %14, %13 ]
  br label %4, !llvm.loop !3

4:                                                ; preds = %2
  %5 = icmp slt i32 %3, 1
  br i1 %5, label %6, label %15

6:                                                ; preds = %4
  br label %7

7:                                                ; preds = %6
  br label %8, !llvm.loop !4

8:                                                ; preds = %7
  br label %9

9:                                                ; preds = %8

  br label %10

10:                                               ; preds = %9
  br i1 undef, label %11, label %12

11:                                               ; preds = %10

  br label %15

12:                                               ; preds = %10

  br label %13

13:                                               ; preds = %12

  %14 = add i32 %3, 1
  br label %2, !llvm.loop !5

15:                                               ; preds = %11, %4
  br label %17

16:                                               ; No predecessors!
  br label %17

17:                                               ; preds = %15, %16
  call void (...) @write(...)
  ret void

[nikic]

Branch on undef is undefined behavior, see https://llvm.org/docs/LangRef.html#id33:

If ‘cond’ is poison or undef, this instruction has undefined behavior.

Either your source program has undefined behavior, or some optimization incorrectly introduced the branch on undef. If the latter, you may want to look through the print-after-all trace to identify when the br undef first appears. It's possible that some optimization is failing to freeze the condition.

[tsymalla]

In D151691#4380411, @nikic wrote:

Branch on undef is undefined behavior, see https://llvm.org/docs/LangRef.html#id33:

If ‘cond’ is poison or undef, this instruction has undefined behavior.

Either your source program has undefined behavior, or some optimization incorrectly introduced the branch on undef. If the latter, you may want to look through the print-after-all trace to identify when the br undef first appears. It's possible that some optimization is failing to freeze the condition.

I know branching and switching on undefs is undefined behavior, and I know that the undef branch is intended. In no way the whole loop as marked in the pseudo-code should be optimized away. What do you mean by "freezing" the condition?

[nikic]

In D151691#4380422, @tsymalla wrote:

In D151691#4380411, @nikic wrote:

Branch on undef is undefined behavior, see https://llvm.org/docs/LangRef.html#id33:

If ‘cond’ is poison or undef, this instruction has undefined behavior.

Either your source program has undefined behavior, or some optimization incorrectly introduced the branch on undef. If the latter, you may want to look through the print-after-all trace to identify when the br undef first appears. It's possible that some optimization is failing to freeze the condition.

I know branching and switching on undefs is undefined behavior, and I know that the undef branch is intended. In no way the whole loop as marked in the pseudo-code should be optimized away.

I don't understand, why should the loop not be optimized away? Can you maybe provide a failing alive2 proof for the case you have in mind?

What do you mean by "freezing" the condition?

See https://llvm.org/docs/LangRef.html#freeze-instruction. Freezing the condition means that the branch will be non-deterministic rather than undefined.

[tsymalla]

In D151691#4380433, @nikic wrote:

In D151691#4380422, @tsymalla wrote:

In D151691#4380411, @nikic wrote:

Branch on undef is undefined behavior, see https://llvm.org/docs/LangRef.html#id33:

If ‘cond’ is poison or undef, this instruction has undefined behavior.

Either your source program has undefined behavior, or some optimization incorrectly introduced the branch on undef. If the latter, you may want to look through the print-after-all trace to identify when the br undef first appears. It's possible that some optimization is failing to freeze the condition.

I know branching and switching on undefs is undefined behavior, and I know that the undef branch is intended. In no way the whole loop as marked in the pseudo-code should be optimized away.

I don't understand, why should the loop not be optimized away? Can you maybe provide a failing alive2 proof for the case you have in mind?

In the above pseudo-code, which is the input into some of LLVMs generic passes, the store is executed at least once, independent of the inner branching that either breaks or does not break the loop.
That's what the final IR without your patch also resembles - it executes the store and does not loop.

What do you mean by "freezing" the condition?

See https://llvm.org/docs/LangRef.html#freeze-instruction. Freezing the condition means that the branch will be non-deterministic rather than undefined.

Thanks! Makes sense.

[nikic]

In D151691#4380437, @tsymalla wrote:

In D151691#4380433, @nikic wrote:

In D151691#4380422, @tsymalla wrote:

In D151691#4380411, @nikic wrote:

Branch on undef is undefined behavior, see https://llvm.org/docs/LangRef.html#id33:

If ‘cond’ is poison or undef, this instruction has undefined behavior.

Either your source program has undefined behavior, or some optimization incorrectly introduced the branch on undef. If the latter, you may want to look through the print-after-all trace to identify when the br undef first appears. It's possible that some optimization is failing to freeze the condition.

I know branching and switching on undefs is undefined behavior, and I know that the undef branch is intended. In no way the whole loop as marked in the pseudo-code should be optimized away.

I don't understand, why should the loop not be optimized away? Can you maybe provide a failing alive2 proof for the case you have in mind?

In the above pseudo-code, which is the input into some of LLVMs generic passes, the store is executed at least once, independent of the inner branching that either breaks or does not break the loop.
That's what the final IR without your patch also resembles - it executes the store and does not loop.

I see. Whether the store will be dropped should depend on intrinsic attributes -- which intrinsic is doing the store in this case?

If the intrinsic is willreturn, then UB can propagate upwards past the store. The intrinsic needs to be non-willreturn if it should be retained in such a case.

[tsymalla]

Thanks! Closing this revision.

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

for (Instruction &Inst : llvm::make_early_inc_range(*BB)) {
         InstrsForInstructionWorklist.push_back(&Inst);
         SeenAliasScopes.analyse(&Inst);
       }
     }
 
     // Recursively visit successors.  If this is a branch or switch on a
     // constant, only visit the reachable successor.
     Instruction *TI = BB->getTerminator();
-    if (BranchInst *BI = dyn_cast<BranchInst>(TI); BI && BI->isConditional()) {
-      if (isa<UndefValue>(BI->getCondition()))
-        // Branch on undef is UB.
-        continue;
-      if (auto *Cond = dyn_cast<ConstantInt>(BI->getCondition())) {
-        bool CondVal = Cond->getZExtValue();
+    if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
+      if (BI->isConditional() && isa<ConstantInt>(BI->getCondition())) {
+        bool CondVal = cast<ConstantInt>(BI->getCondition())->getZExtValue();
         BasicBlock *ReachableBB = BI->getSuccessor(!CondVal);
         Worklist.push_back(ReachableBB);
         continue;
       }
     } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
-      if (isa<UndefValue>(SI->getCondition()))
-        // Switch on undef is UB.
-        continue;
-      if (auto *Cond = dyn_cast<ConstantInt>(SI->getCondition())) {
+      if (ConstantInt *Cond = dyn_cast<ConstantInt>(SI->getCondition())) {
         Worklist.push_back(SI->findCaseValue(Cond)->getCaseSuccessor());
         continue;
       }
     }
 
     append_range(Worklist, successors(TI));
   } while (!Worklist.empty());
 

llvm/test/Transforms/InstCombine/unreachable-code.ll

else:
   ret void
 }
 
 define void @br_undef(i1 %x) {
 ; CHECK-LABEL: define void @br_undef
 ; CHECK-SAME: (i1 [[X:%.*]]) {
 ; CHECK-NEXT:    br i1 undef, label [[IF:%.*]], label [[ELSE:%.*]]
 ; CHECK:       if:
+; CHECK-NEXT:    call void @dummy()
 ; CHECK-NEXT:    ret void
 ; CHECK:       else:
+; CHECK-NEXT:    call void @dummy()
 ; CHECK-NEXT:    ret void
 ;
   %c = xor i1 %x, undef
   br i1 %c, label %if, label %else
 
 if:
   call void @dummy()
   ret void

 
 define void @switch_undef(i32 %x) {
 ; CHECK-LABEL: define void @switch_undef
 ; CHECK-SAME: (i32 [[X:%.*]]) {
 ; CHECK-NEXT:    switch i32 undef, label [[DEFAULT:%.*]] [
 ; CHECK-NEXT:    i32 0, label [[CASE0:%.*]]
 ; CHECK-NEXT:    ]
 ; CHECK:       case0:
+; CHECK-NEXT:    call void @dummy()
 ; CHECK-NEXT:    ret void
 ; CHECK:       default:
+; CHECK-NEXT:    call void @dummy()
 ; CHECK-NEXT:    ret void
 ;
   %v = xor i32 %x, undef
   switch i32 %v, label %default [
   i32 0, label %case0
   ]
 
 case0:
   call void @dummy()
   ret void
 
 default:
   call void @dummy()
   ret void
 }