[IPSCCP] Change dead blocks to unreachable after visiting all executable blocks.

[fhahn]

Summary

changeToUnreachable may remove PHI nodes from executable blocks we found values
for and we would fail to replace them. By changing dead blocks to unreachable after
we replaced constants in all executable blocks, we ensure such PHI nodes are replaced
by their known value before.

Fixes PR37780.

[uabelho]

This indeed solves the problem I saw in PR37780. Thanks!

[efriedma]

lib/Transforms/Scalar/SCCP.cpp

1944

The "PN.getNumIncomingValues() != 2" won't work correctly in all cases.

Instead of adding this extra loop, can you just delay the call to changeToUnreachable until after we've iterated over all the blocks?

[fhahn]

Thanks Eli, I've updated the patch as suggested.

[efriedma]

LGTM

lib/Transforms/Scalar/SCCP.cpp

if (Solver.isBlockExecutable(&F.front()))
 
         if (!AI->use_empty() && tryToReplaceWithConstantRange(Solver, &*AI))
           ++IPNumRangeInfoUsed;
       }
 
     for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) {
       if (!Solver.isBlockExecutable(&*BB)) {
         LLVM_DEBUG(dbgs() << "  BasicBlock Dead:" << *BB);
-
         ++NumDeadBlocks;
-        NumInstRemoved +=
-            changeToUnreachable(BB->getFirstNonPHI(), /*UseLLVMTrap=*/false);
 
         MadeChanges = true;
 
         if (&*BB != &F.front())
           BlocksToErase.push_back(&*BB);
         continue;
       }
 
       for (BasicBlock::iterator BI = BB->begin(), E = BB->end(); BI != E; ) {
         Instruction *Inst = &*BI++;
         if (Inst->getType()->isVoidTy())
           continue;
         if (tryToReplaceWithConstant(Solver, Inst)) {
           if (Inst->isSafeToRemove())
             Inst->eraseFromParent();
           // Hey, we just changed something!
           MadeChanges = true;
           ++IPNumInstRemoved;
         }
       }
     }
 
+    // Change dead blocks to unreachable. We do it after replacing constants in
+    // all executable blocks, because changeToUnreachable may remove PHI nodes
+    // in executable blocks we found values for. The function's entry block is
+    // not part of BlocksToErase, so we have to handle it separately.
+    for (BasicBlock *BB : BlocksToErase)
+      NumInstRemoved +=
+          changeToUnreachable(BB->getFirstNonPHI(), /*UseLLVMTrap=*/false);
+    if (!Solver.isBlockExecutable(&F.front()))
+      NumInstRemoved += changeToUnreachable(F.front().getFirstNonPHI(),
+                                            /*UseLLVMTrap=*/false);
+
     // Now that all instructions in the function are constant folded, erase dead
     // blocks, because we can now use ConstantFoldTerminator to get rid of
     // in-edges.
     for (unsigned i = 0, e = BlocksToErase.size(); i != e; ++i) {
       // If there are any PHI nodes in this successor, drop entries for BB now.
       BasicBlock *DeadBB = BlocksToErase[i];
       for (Value::user_iterator UI = DeadBB->user_begin(),
                                 UE = DeadBB->user_end();

test/Transforms/SCCP/ipsccp-phi-one-pred-dead.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -S -ipsccp | FileCheck %s
+target triple = "x86_64-unknown-linux-gnu"
+
+define void @test() {
+; CHECK-LABEL: @test(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label %Flow5.pre
+; CHECK:       Flow6:
+; CHECK-NEXT:    br label %end2
+; CHECK:       Flow5.pre:
+; CHECK-NEXT:    br label %Flow5
+; CHECK:       Flow5:
+; CHECK-NEXT:    br label %Flow6
+; CHECK:       end2:
+; CHECK-NEXT:    unreachable
+;
+entry:
+  br i1 true, label %Flow5.pre, label %Flow5.pre.unreachable
+
+Flow5.pre.unreachable:
+  br label %Flow5
+
+Flow6:
+  br i1 %0, label %end1, label %end2
+
+Flow5.pre:
+  br label %Flow5
+
+Flow5:
+  %0 = phi i1 [ undef, %Flow5.pre ], [ false, %Flow5.pre.unreachable ]
+  br label %Flow6
+
+end1:
+  unreachable
+
+end2:
+  unreachable
+}