[InstCombine] replace phi values from unreachable blocks with 'undef'

[spatel]

Summary

The test (currently crashing) is reduced from the example provided in the post-commit discussion in D87149.
Here we replace with undef because we can't remove the operand completely (because InstCombine preserves the CFG).
We used to do something similar for branches, but we changed that to use a fixed constant value rather than undef because branching on undef became poison/UB.

I'm not sure what the cost/implications of this approach are. If we want to fix the crash more directly, we could just add a clause for uses and restrict the transform from D87149.

[nikic]

I don't think this fully addresses the problem, in that this relies on the phi getting processed before the unreachable, which is not a given. This would have to happen prior to the main InstCombine run, at the same time we remove instructions in unreachable blocks. It's probably not worth it. I think we should fix this the direct way, by performing a replaceInstUsesWith(*Prev, UndefValue(Prev->getType()) before the eraseInstFromFunction() in the unreachable transform.

[nlopes]

llvm/test/Transforms/InstCombine/phi.ll

1207

The patch LGTM. Just a side comment: we should avoid tests with br undef as we define that as UB, and therefore it makes any transformation correct. Which in turn essentially disables verification by Alive2.
(I know we still have many such tests. I think we talked in the past of writing a script to do a mass change of these to use input variables)

[spatel]

Patch updated:

1. Use the direct approach to fix the bug - replace with undef before trying to delete.
2. Avoid branch on undef in crashing test case.

[lebedev.ri]

lg

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

2816 ↗

(On Diff #293018)

This needs a motivational comment

[spatel]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

2816 ↗

(On Diff #293018)

Thanks! Will add comment and change the patch title/description on commit.

[aqjune]

llvm/test/Transforms/InstCombine/phi.ll

1207

I remember bugpoint was the culprit who inserted a lot of br undef.
I tried to fix it in the past, but it wasn't trivial.

llvm/lib/Transforms/InstCombine/InstCombinePHI.cpp

 //
 Instruction *InstCombinerImpl::visitPHINode(PHINode &PN) {
   if (Value *V = SimplifyInstruction(&PN, SQ.getWithInstruction(&PN)))
     return replaceInstUsesWith(PN, V);
 
   if (Instruction *Result = foldPHIArgZextsIntoPHI(PN))
     return Result;
 
+  // Replace values from unreachable incoming blocks with undef.
+  for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) {
+    if (!DT.isReachableFromEntry(PN.getIncomingBlock(i)))
+      PN.setIncomingValue(i, UndefValue::get(PN.getType()));
+  }
+
   // If all PHI operands are the same operation, pull them through the PHI,
   // reducing code size.
   if (isa<Instruction>(PN.getIncomingValue(0)) &&
       isa<Instruction>(PN.getIncomingValue(1)) &&
       cast<Instruction>(PN.getIncomingValue(0))->getOpcode() ==
           cast<Instruction>(PN.getIncomingValue(1))->getOpcode() &&
       PN.getIncomingValue(0)->hasOneUser())
     if (Instruction *Result = foldPHIArgOpIntoPHI(PN))

llvm/test/Transforms/InstCombine/phi.ll

if.else:                                          ; preds = %entry
   %1 = select i1 %cmp, i32 1, i32 2
   br label %if.end
 
 if.end:                                           ; preds = %entry, %if.then
   %a.0 = phi i32 [ %1,  %if.else], [ %n, %entry ], [2, %if.then]
   %cmp1 = icmp ne i32 %a.0, 0
   ret i1  %cmp1
 }
+
+; This would crash trying to delete an instruction (conv)
+; that still had uses because the user (the phi) was not
+; updated to remove a use from an unreachable block (g.exit).
+
+define void @main(i16 %x) {
+; CHECK-LABEL: @main(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[FOR_COND:%.*]]
+; CHECK:       for.cond:
+; CHECK-NEXT:    br i1 undef, label [[FOR_END:%.*]], label [[FOR_BODY:%.*]]
+; CHECK:       for.body:
+; CHECK-NEXT:    unreachable
+; CHECK:       g.exit:
+; CHECK-NEXT:    br label [[FOR_COND]]
+; CHECK:       for.end:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %for.cond
+
+for.cond:
+  %p = phi double [ %conv, %g.exit ], [ undef, %entry ]
+  br i1 undef, label %for.end, label %for.body
+
+for.body:
+  %conv = sitofp i16 %x to double
+  unreachable
+
+g.exit:
+  br label %for.cond
+
+for.end:
+  store double %p, double* undef
+  ret void
+}

llvm/test/Transforms/InstCombine/zext-or-icmp.ll

 
 define i32 @dont_widen_undef() {
 ; CHECK-LABEL: @dont_widen_undef(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[BLOCK2:%.*]]
 ; CHECK:       block1:
 ; CHECK-NEXT:    br label [[BLOCK2]]
 ; CHECK:       block2:
-; CHECK-NEXT:    [[CMP_I:%.*]] = phi i1 [ false, [[BLOCK1:%.*]] ], [ true, [[ENTRY:%.*]] ]
-; CHECK-NEXT:    [[M_011:%.*]] = phi i32 [ 0, [[BLOCK1]] ], [ 33, [[ENTRY]] ]
-; CHECK-NEXT:    [[M_1_OP:%.*]] = lshr i32 1, [[M_011]]
-; CHECK-NEXT:    [[SEXT_MASK:%.*]] = and i32 [[M_1_OP]], 65535
-; CHECK-NEXT:    [[CMP115:%.*]] = icmp ne i32 [[SEXT_MASK]], 0
-; CHECK-NEXT:    [[CMP1:%.*]] = or i1 [[CMP_I]], [[CMP115]]
-; CHECK-NEXT:    [[CONV2:%.*]] = zext i1 [[CMP1]] to i32
-; CHECK-NEXT:    ret i32 [[CONV2]]
+; CHECK-NEXT:    ret i32 1
 ;
 entry:
   br label %block2
 
 block1:
   br label %block2
 
 block2: