[LowerSwitch] Skip dead blocks for processSwitchInst()

[• chenli]

Summary

This patch adds check for dead blocks and skip them for processSwitchInst(). This will help reduce compilation time.

[hans]

lib/Transforms/Utils/LowerSwitch.cpp

127 ↗

(On Diff #31842)

Seems we're ending up with both the DeleteList and checking for dead blocks in the loop? It would be nice if we only had to check in one place.

Perhaps one solution would be to make DeleteList a SmallPtrSet instead, and in the loop we could do "if (DeleteSet.contains(Cur)) continue;"

[• chenli]

Update w.r.t. Hans' comments.

[hans]

lgtm with style comments.

lib/Transforms/Utils/LowerSwitch.cpp

126 ↗

(On Diff #31849)

nit: I would probably skip the braces around this one-line if body.

411 ↗

(On Diff #31849)

This line is over the 80 column limit.

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, SmallVectorImpl<BasicBlock*> &DeleteList);
+    void processSwitchInst(SwitchInst *SI, SmallPtrSetImpl<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;
+  SmallPtrSet<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 the block is a dead Default block that will be deleted later, don't
+    // waste time processing it.
+    if (DeleteList.count(Cur))
+      continue;
+
     if (SwitchInst *SI = dyn_cast<SwitchInst>(Cur->getTerminator())) {
       Changed = true;
       processSwitchInst(SI, DeleteList);
     }
   }
 
   for (BasicBlock* BB: DeleteList) {
     DeleteDeadBlock(BB);
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, SmallVectorImpl<BasicBlock*> &DeleteList) {
+void LowerSwitch::processSwitchInst(SwitchInst *SI,
+                                    SmallPtrSetImpl<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
   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 add it to DeleteList.
   if (pred_begin(OldDefault) == pred_end(OldDefault))
-    DeleteList.push_back(OldDefault);
+    DeleteList.insert(OldDefault);
 }