[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

528 ↗

(On Diff #31553)

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

528 ↗

(On Diff #31553)

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.

llvm/trunk/lib/Transforms/Utils/LowerSwitch.cpp

struct CaseRange {
 
       CaseRange(ConstantInt *low, ConstantInt *high, BasicBlock *bb)
           : Low(low), High(high), BB(bb) {}
     };
 
     typedef std::vector<CaseRange> CaseVector;
     typedef std::vector<CaseRange>::iterator CaseItr;
   private:
-    void processSwitchInst(SwitchInst *SI);
+    void processSwitchInst(SwitchInst *SI, SmallVectorImpl<BasicBlock*> &DeleteList);
 
     BasicBlock *switchConvert(CaseItr Begin, CaseItr End,
                               ConstantInt *LowerBound, ConstantInt *UpperBound,
                               Value *Val, BasicBlock *Predecessor,
                               BasicBlock *OrigBlock, BasicBlock *Default,
                               const std::vector<IntRange> &UnreachableRanges);
     BasicBlock *newLeafBlock(CaseRange &Leaf, Value *Val, BasicBlock *OrigBlock,
                              BasicBlock *Default);

 char &llvm::LowerSwitchID = LowerSwitch::ID;
 // createLowerSwitchPass - Interface to this file...
 FunctionPass *llvm::createLowerSwitchPass() {
   return new LowerSwitch();
 }
 
 bool LowerSwitch::runOnFunction(Function &F) {
   bool Changed = false;
+  SmallVector<BasicBlock*, 8> DeleteList;
 
   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 (SwitchInst *SI = dyn_cast<SwitchInst>(Cur->getTerminator())) {
       Changed = true;
-      processSwitchInst(SI);
+      processSwitchInst(SI, DeleteList);
     }
   }
 
+  for (BasicBlock* BB: DeleteList) {
+    DeleteDeadBlock(BB);
+  }
+
   return Changed;
 }
 
 // operator<< - Used for debugging purposes.
 //
 static raw_ostream& operator<<(raw_ostream &O,
                                const LowerSwitch::CaseVector &C)
     LLVM_ATTRIBUTE_USED;
unsigned LowerSwitch::Clusterify(CaseVector& Cases, SwitchInst *SI) {
   }
 
   return numCmps;
 }
 
 // processSwitchInst - Replace the specified switch instruction with a sequence
 // of chained if-then insts in a balanced binary search.
 //
-void LowerSwitch::processSwitchInst(SwitchInst *SI) {
+void LowerSwitch::processSwitchInst(SwitchInst *SI, SmallVectorImpl<BasicBlock*> &DeleteList) {
   BasicBlock *CurBlock = SI->getParent();
   BasicBlock *OrigBlock = CurBlock;
   Function *F = CurBlock->getParent();
   Value *Val = SI->getCondition();  // The value we are switching on...
   BasicBlock* Default = SI->getDefaultDest();
 
   // If there is only the default destination, just branch.
   if (!SI->getNumCases()) {
#endif
 
   // 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 the Default block has no more predecessors just add it to DeleteList.
   if (pred_begin(OldDefault) == pred_end(OldDefault))
-    DeleteDeadBlock(OldDefault);
+    DeleteList.push_back(OldDefault);
 }

llvm/trunk/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
+}