[SCCP] Fix crash when trying to constant-fold terminators multiple times.

[fhahn]

Summary

If we fold a branch/switch to an unconditional branch to another dead block we
replace the branch with unreachable, to avoid attempting to fold the
unconditional branch.

[fhahn]

ping

[jdoerfert]

Do we need to "repair" the folded branch or could we also determine earlier that the current block is dead (it will have an unconditional branch to a dead block, right?) and avoid folding?
It might make sense to fold due to the DT update though.

llvm/lib/Transforms/Scalar/SCCP.cpp

2087 ↗

(On Diff #197284)

now BB

[fhahn]

In D61300#1493707, @jdoerfert wrote:

Do we need to "repair" the folded branch or could we also determine earlier that the current block is dead (it will have an unconditional branch to a dead block, right?) and avoid folding?
It might make sense to fold due to the DT update though.

We could skip calling forceIndeterminateEdge and ConstantFoldTerminator, if all successors are not executable. But I think it is better to keep the current structure, because the assertion that we managed to fold the terminator has been helpful in catching inconsistencies in the past and it is probably also quicker e.g. if you have switch statements with a large number of successors.

llvm/lib/Transforms/Scalar/SCCP.cpp

2087 ↗

(On Diff #197284)

Do you mean omitting the * with auto? There's no reason to use auto here, I'll change it to BasicBlock.

[jdoerfert]

In D61300#1493814, @fhahn wrote:

In D61300#1493707, @jdoerfert wrote:

Do we need to "repair" the folded branch or could we also determine earlier that the current block is dead (it will have an unconditional branch to a dead block, right?) and avoid folding?
It might make sense to fold due to the DT update though.

We could skip calling forceIndeterminateEdge and ConstantFoldTerminator, if all successors are not executable. But I think it is better to keep the current structure, because the assertion that we managed to fold the terminator has been helpful in catching inconsistencies in the past and it is probably also quicker e.g. if you have switch statements with a large number of successors.

Now that we thought about it, I think it's fine to do it this way :)

See the comment but otherwise LGTM

llvm/lib/Transforms/Scalar/SCCP.cpp

2087 ↗

(On Diff #197284)

I mean I->getParent() in 2087 should now be BB. Also, BasicBlock seems reasonable.

[fhahn]

Use InstBB instead of I->getParent(). Thanks, I was looking at the wrong line :)

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

for (BasicBlock *DeadBB : BlocksToErase) {
         do { ++UI; } while (UI != UE && *UI == I);
 
         // Ignore blockaddress users; BasicBlock's dtor will handle them.
         if (!I) continue;
 
         // If we have forced an edge for an indeterminate value, then force the
         // terminator to fold to that edge.
         forceIndeterminateEdge(I, Solver);
-        bool Folded = ConstantFoldTerminator(I->getParent(),
+        BasicBlock *InstBB = I->getParent();
+        bool Folded = ConstantFoldTerminator(InstBB,
                                              /*DeleteDeadConditions=*/false,
                                              /*TLI=*/nullptr, &DTU);
         assert(Folded &&
               "Expect TermInst on constantint or blockaddress to be folded");
         (void) Folded;
+        // If we folded the terminator to an unconditional branch to another
+        // dead block, replace it with Unreachable, to avoid trying to fold that
+        // branch again.
+        BranchInst *BI = cast<BranchInst>(InstBB->getTerminator());
+        if (BI && BI->isUnconditional() &&
+            !Solver.isBlockExecutable(BI->getSuccessor(0))) {
+          InstBB->getTerminator()->eraseFromParent();
+          new UnreachableInst(InstBB->getContext(), InstBB);
+        }
       }
       // Mark dead BB for deletion.
       DTU.deleteBB(DeadBB);
     }
 
     for (BasicBlock &BB : F) {
       for (BasicBlock::iterator BI = BB.begin(), E = BB.end(); BI != E;) {
         Instruction *Inst = &*BI++;

llvm/trunk/test/Transforms/SCCP/switch-constantfold-crash.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -ipsccp < %s -S | FileCheck %s
+; RUN: opt -passes=ipsccp < %s -S | FileCheck %s
+
+define void @barney() {
+; CHECK-LABEL: @barney(
+; CHECK-NEXT:  bb:
+; CHECK-NEXT:    br label %bb9
+; CHECK:       bb6:
+; CHECK-NEXT:    unreachable
+; CHECK:       bb9:
+; CHECK-NEXT:    unreachable
+;
+bb:
+  br label %bb9
+
+bb6:                                              ; preds = %bb9
+  unreachable
+
+bb7:                                              ; preds = %bb9
+  unreachable
+
+bb9:                                              ; preds = %bb
+  switch i16 0, label %bb6 [
+  i16 61, label %bb7
+  ]
+}
+
+define void @blam() {
+; CHECK-LABEL: @blam(
+; CHECK-NEXT:  bb:
+; CHECK-NEXT:    br label %bb16
+; CHECK:       bb16:
+; CHECK-NEXT:    br label %bb38
+; CHECK:       bb38:
+; CHECK-NEXT:    unreachable
+;
+bb:
+  br label %bb16
+
+bb16:                                             ; preds = %bb
+  switch i32 0, label %bb38 [
+  i32 66, label %bb17
+  i32 63, label %bb18
+  i32 86, label %bb19
+  ]
+
+bb17:                                             ; preds = %bb16
+  unreachable
+
+bb18:                                             ; preds = %bb16
+  unreachable
+
+bb19:                                             ; preds = %bb16
+  unreachable
+
+bb38:                                             ; preds = %bb16
+  unreachable
+}
+
+
+define void @hoge() {
+; CHECK-LABEL: @hoge(
+; CHECK-NEXT:  bb:
+; CHECK-NEXT:    br label %bb2
+; CHECK:       bb2:
+; CHECK-NEXT:    unreachable
+; CHECK:       bb3:
+; CHECK-NEXT:    unreachable
+;
+bb:
+  switch i16 undef, label %bb1 [
+  i16 135, label %bb2
+  i16 66, label %bb2
+  ]
+
+bb1:                                              ; preds = %bb
+  ret void
+
+bb2:                                              ; preds = %bb, %bb
+  switch i16 0, label %bb3 [
+  i16 61, label %bb4
+  i16 54, label %bb4
+  i16 49, label %bb4
+  ]
+
+bb3:                                              ; preds = %bb2
+  unreachable
+
+bb4:                                              ; preds = %bb2, %bb2, %bb2
+  unreachable
+}