[LICM] Replace incoming values with undef if the incoming BB is unreachable

[majnemer]

Summary

Unreachable BBs don't meaningfully contribute to the PHI node, replace
their incoming value with undef.

This fixes PR24013.

[majnemer]

Ping.

[chandlerc]

lib/Transforms/Scalar/LICM.cpp

614–621 ↗

(On Diff #28967)

Why do this here rather than in InstSimplify? Do we form these too late for that to clean it up? If so, should we add it to InstSimplify and call that here?

[majnemer]

lib/Transforms/Scalar/LICM.cpp

614–621 ↗

(On Diff #28967)

I don't know what we could do in InstructionSimplify instead of here.

Running InstructionSimplify on the PHI won't help because it cannot create new instructions, it wouldn't be able to give us a new PHI which had the incoming value replaced with undef.

Running InstructionSimplify on the incoming value won't help because it might not be simplifiable. My trivial test case has a trivial incoming value but we cannot, in the general case, rely on simplification yielding a Constant. For example:

define i32 @f(i1 zeroext %p1) {
entry:
  br label %lbl

lbl.loopexit:                                     ; No predecessors!
  br label %lbl

lbl:                                              ; preds = %lbl.loopexit, %entry
  %phi = phi i32 [ %conv, %lbl.loopexit ], [ undef, %entry ]
  br i1 %p1, label %if.then.5, label %out

if.then.5:                                        ; preds = %if.then.5, %lbl
  %conv = zext i1 %p1 to i32
  br label %if.then.5

out:                                              ; preds = %lbl
  ret i32 %phi
}

[hfinkel]

lib/Transforms/Scalar/LICM.cpp

614–621 ↗

(On Diff #28967)

InstCombine always has a DT now and can create new instructions, why not add this there?

[majnemer]

lib/Transforms/Scalar/LICM.cpp

614–621 ↗

(On Diff #28967)

This fix address a miscompile, not a missed optimization. Sorry for the miscommunication, I'll update the summary to have an in-depth description of the bug and the rationale behind the fix.

[hfinkel]

lib/Transforms/Scalar/LICM.cpp

614–621 ↗

(On Diff #28967)

Okay; I'd rather see a comment in the code explaining why what it is doing is a necessary part of the algorithm.

Assuming you add such a comment, LGTM.

llvm/trunk/lib/Transforms/Scalar/LICM.cpp

#endif
 
   // Clones of this instruction. Don't create more than one per exit block!
   SmallDenseMap<BasicBlock *, Instruction *, 32> SunkCopies;
 
   // If this instruction is only used outside of the loop, then all users are
   // PHI nodes in exit blocks due to LCSSA form. Just RAUW them with clones of
   // the instruction.
   while (!I.use_empty()) {
-    Instruction *User = I.user_back();
+    Value::user_iterator UI = I.user_begin();
+    auto *User = cast<Instruction>(*UI);
     if (!DT->isReachableFromEntry(User->getParent())) {
       User->replaceUsesOfWith(&I, UndefValue::get(I.getType()));
       continue;
     }
     // The user must be a PHI node.
     PHINode *PN = cast<PHINode>(User);
 
+    // Surprisingly, instructions can be used outside of loops without any
+    // exits.  This can only happen in PHI nodes if the incoming block is
+    // unreachable.
+    Use &U = UI.getUse();
+    BasicBlock *BB = PN->getIncomingBlock(U);
+    if (!DT->isReachableFromEntry(BB)) {
+      U = UndefValue::get(I.getType());
+      continue;
+    }
+
     BasicBlock *ExitBlock = PN->getParent();
     assert(ExitBlockSet.count(ExitBlock) &&
            "The LCSSA PHI is not in an exit block!");
 
     Instruction *New;
     auto It = SunkCopies.find(ExitBlock);
     if (It != SunkCopies.end())
       New = It->second;

llvm/trunk/test/Transforms/LICM/PR24013.ll

+; RUN: opt -licm -S < %s | FileCheck %s
+
+define void @f(i1 zeroext %p1) {
+; CHECK-LABEL: @f(
+entry:
+  br label %lbl
+
+lbl.loopexit:                                     ; No predecessors!
+  br label %lbl
+
+lbl:                                              ; preds = %lbl.loopexit, %entry
+  %phi = phi i32 [ %conv, %lbl.loopexit ], [ undef, %entry ]
+; CHECK: phi i32 [ undef, {{.*}} ], [ undef
+  br label %if.then.5
+
+if.then.5:                                        ; preds = %if.then.5, %lbl
+  %conv = zext i1 undef to i32
+  br label %if.then.5
+}