[LowerSwitch] Fix a bug when LowerSwitch deletes the default block

[• chenli]

Summary

LowerSwitch crashed with the attached test case after deleting the default block. This happened because the current implementation of deleting dead blocks is wrong. After the default block being deleted, it contains no instruction or terminator, and it should no be traversed anymore. However, since the iterator is advanced before processSwitchInst() function is executed, the block advanced to could be deleted inside processSwitchInst(). The deleted block would then be visited next and crash dyn_cast<SwitchInst>(Cur->getTerminator()) because Cur->getTerminator() returns a nullptr. This patch fixes this problem by recording dead default blocks into a list, and delete them after all processSwitchInst() has been done. It still possible to visit dead default blocks and waste time process them. But it is a compile time issue, and I plan to have another patch to add support to skip dead blocks.

[hans]

lib/Transforms/Utils/LowerSwitch.cpp

526–527

I don't think maintaining a DeleteList is very nice, and as you say it has the problem that we might call processSwitchInst on a block even if it's dead.

How about we remove the DeleteDeadBlock call here, and in the loop in runOnFunction(), we add something like:

if (block has no predecessors) {
  delete it
  continue
}

[• chenli]

lib/Transforms/Utils/LowerSwitch.cpp

526–527

Yes, I think that should work too. Though we need to handle carefully with entry block, which also has no predecessors.

[• chenli]

Update patch w.r.t Hans' comments.

[hans]

Looks good to me.

[reames]

The revised patch is strictly less powerful than the current code and the previous patch. If a block occurs earlier in the iteration order than the only block which reaches it and we then delete the reaching edge, we will now fail to remove the unreachable block. I would prefer the first patch posted over the revised one.

[• chenli]

In D11852#221321, @reames wrote:

The revised patch is strictly less powerful than the current code and the previous patch. If a block occurs earlier in the iteration order than the only block which reaches it and we then delete the reaching edge, we will now fail to remove the unreachable block. I would prefer the first patch posted over the revised one.

Yes, you are correct. I didn't think about this case. I will submit the initial patch if Hans is ok with that.

[hans]

In D11852#221347, @chenli wrote:

In D11852#221321, @reames wrote:

The revised patch is strictly less powerful than the current code and the previous patch. If a block occurs earlier in the iteration order than the only block which reaches it and we then delete the reaching edge, we will now fail to remove the unreachable block. I would prefer the first patch posted over the revised one.

Yes, you are correct. I didn't think about this case. I will submit the initial patch if Hans is ok with that.

Sure.

lib/Transforms/Utils/LowerSwitch.cpp

 }
 
 bool LowerSwitch::runOnFunction(Function &F) {
   bool Changed = false;
 
   for (Function::iterator I = F.begin(), E = F.end(); I != E; ) {
     BasicBlock *Cur = I++; // Advance over block so we don't traverse new blocks
 
+    // If the block has no more predecessors, it should be a Default block which
+    // was erased in the previous processSwitchInst() or dead block resulted from
+    // other passes. Delete it and move on to the next iteration.
+    if (Cur != &F.getEntryBlock() && pred_begin(Cur) == pred_end(Cur)) {
+      DeleteDeadBlock(Cur);
+      continue;
+    }
+
     if (SwitchInst *SI = dyn_cast<SwitchInst>(Cur->getTerminator())) {
       Changed = true;
       processSwitchInst(SI);
     }
   }
 
   return Changed;
 }
#endif
   BasicBlock *SwitchBlock =
       switchConvert(Cases.begin(), Cases.end(), LowerBound, UpperBound, Val,
                     OrigBlock, OrigBlock, NewDefault, UnreachableRanges);
 
   // Branch to our shiny new if-then stuff...
   BranchInst::Create(SwitchBlock, OrigBlock);
 
   // We are now done with the switch instruction, delete it.
-  BasicBlock *OldDefault = SI->getDefaultDest();
   CurBlock->getInstList().erase(SI);
-
-  // If the Default block has no more predecessors just remove it.
-  if (pred_begin(OldDefault) == pred_end(OldDefault))
-    DeleteDeadBlock(OldDefault);
 }

test/Transforms/LowerSwitch/delete-default-block-crash.ll

+; RUN: opt < %s -lowerswitch -disable-output
+
+; This test verify -lowerswitch does not crash after deleting the default block.
+
+declare i32 @f(i32)
+
+define i32 @unreachable(i32 %x) {
+
+entry:
+  switch i32 %x, label %unreachable [
+    i32 5, label %a
+    i32 6, label %a
+    i32 7, label %a
+    i32 10, label %b
+    i32 20, label %b
+    i32 30, label %b
+    i32 40, label %b
+  ]
+unreachable:
+  unreachable
+a:
+  %0 = call i32 @f(i32 0)
+  ret i32 %0
+b:
+  %1 = call i32 @f(i32 1)
+  ret i32 %1
+}