LowerSwitch.cpp revision d216e8ba60494caacf919cbf5fef110d48f0d162
1//===- LowerSwitch.cpp - Eliminate Switch instructions --------------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file was developed by the LLVM research group and is distributed under 6// the University of Illinois Open Source License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// The LowerSwitch transformation rewrites switch statements with a sequence of 11// branches, which allows targets to get away with not implementing the switch 12// statement until it is convenient. 13// 14//===----------------------------------------------------------------------===// 15 16#include "llvm/Transforms/Scalar.h" 17#include "llvm/Transforms/Utils/UnifyFunctionExitNodes.h" 18#include "llvm/Constants.h" 19#include "llvm/Function.h" 20#include "llvm/Instructions.h" 21#include "llvm/Pass.h" 22#include "llvm/Support/Debug.h" 23#include "llvm/Support/Compiler.h" 24#include <algorithm> 25using namespace llvm; 26 27namespace { 28 /// LowerSwitch Pass - Replace all SwitchInst instructions with chained branch 29 /// instructions. Note that this cannot be a BasicBlock pass because it 30 /// modifies the CFG! 31 class VISIBILITY_HIDDEN LowerSwitch : public FunctionPass { 32 public: 33 virtual bool runOnFunction(Function &F); 34 35 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 36 // This is a cluster of orthogonal Transforms 37 AU.addPreserved<UnifyFunctionExitNodes>(); 38 AU.addPreservedID(PromoteMemoryToRegisterID); 39 AU.addPreservedID(LowerSelectID); 40 AU.addPreservedID(LowerInvokePassID); 41 AU.addPreservedID(LowerAllocationsID); 42 } 43 44 typedef std::pair<Constant*, BasicBlock*> Case; 45 typedef std::vector<Case>::iterator CaseItr; 46 private: 47 void processSwitchInst(SwitchInst *SI); 48 49 BasicBlock* switchConvert(CaseItr Begin, CaseItr End, Value* Val, 50 BasicBlock* OrigBlock, BasicBlock* Default); 51 BasicBlock* newLeafBlock(Case& Leaf, Value* Val, 52 BasicBlock* OrigBlock, BasicBlock* Default); 53 }; 54 55 /// The comparison function for sorting the switch case values in the vector. 56 struct CaseCmp { 57 bool operator () (const LowerSwitch::Case& C1, 58 const LowerSwitch::Case& C2) { 59 60 const ConstantInt* CI1 = cast<const ConstantInt>(C1.first); 61 const ConstantInt* CI2 = cast<const ConstantInt>(C2.first); 62 if (CI1->getType()->isUnsigned()) 63 return CI1->getZExtValue() < CI2->getZExtValue(); 64 return CI1->getSExtValue() < CI2->getSExtValue(); 65 } 66 }; 67 68 RegisterPass<LowerSwitch> 69 X("lowerswitch", "Lower SwitchInst's to branches"); 70} 71 72// Publically exposed interface to pass... 73const PassInfo *llvm::LowerSwitchID = X.getPassInfo(); 74// createLowerSwitchPass - Interface to this file... 75FunctionPass *llvm::createLowerSwitchPass() { 76 return new LowerSwitch(); 77} 78 79bool LowerSwitch::runOnFunction(Function &F) { 80 bool Changed = false; 81 82 for (Function::iterator I = F.begin(), E = F.end(); I != E; ) { 83 BasicBlock *Cur = I++; // Advance over block so we don't traverse new blocks 84 85 if (SwitchInst *SI = dyn_cast<SwitchInst>(Cur->getTerminator())) { 86 Changed = true; 87 processSwitchInst(SI); 88 } 89 } 90 91 return Changed; 92} 93 94// operator<< - Used for debugging purposes. 95// 96std::ostream& operator<<(std::ostream &O, 97 const std::vector<LowerSwitch::Case> &C) { 98 O << "["; 99 100 for (std::vector<LowerSwitch::Case>::const_iterator B = C.begin(), 101 E = C.end(); B != E; ) { 102 O << *B->first; 103 if (++B != E) O << ", "; 104 } 105 106 return O << "]"; 107} 108OStream& operator<<(OStream &O, const std::vector<LowerSwitch::Case> &C) { 109 if (O.stream()) *O.stream() << C; 110 return O; 111} 112 113// switchConvert - Convert the switch statement into a binary lookup of 114// the case values. The function recursively builds this tree. 115// 116BasicBlock* LowerSwitch::switchConvert(CaseItr Begin, CaseItr End, 117 Value* Val, BasicBlock* OrigBlock, 118 BasicBlock* Default) 119{ 120 unsigned Size = End - Begin; 121 122 if (Size == 1) 123 return newLeafBlock(*Begin, Val, OrigBlock, Default); 124 125 unsigned Mid = Size / 2; 126 std::vector<Case> LHS(Begin, Begin + Mid); 127 DOUT << "LHS: " << LHS << "\n"; 128 std::vector<Case> RHS(Begin + Mid, End); 129 DOUT << "RHS: " << RHS << "\n"; 130 131 Case& Pivot = *(Begin + Mid); 132 DOUT << "Pivot ==> " 133 << cast<ConstantInt>(Pivot.first)->getSExtValue() << "\n"; 134 135 BasicBlock* LBranch = switchConvert(LHS.begin(), LHS.end(), Val, 136 OrigBlock, Default); 137 BasicBlock* RBranch = switchConvert(RHS.begin(), RHS.end(), Val, 138 OrigBlock, Default); 139 140 // Create a new node that checks if the value is < pivot. Go to the 141 // left branch if it is and right branch if not. 142 Function* F = OrigBlock->getParent(); 143 BasicBlock* NewNode = new BasicBlock("NodeBlock"); 144 F->getBasicBlockList().insert(OrigBlock->getNext(), NewNode); 145 146 SetCondInst* Comp = new SetCondInst(Instruction::SetLT, Val, Pivot.first, 147 "Pivot"); 148 NewNode->getInstList().push_back(Comp); 149 new BranchInst(LBranch, RBranch, Comp, NewNode); 150 return NewNode; 151} 152 153// newLeafBlock - Create a new leaf block for the binary lookup tree. It 154// checks if the switch's value == the case's value. If not, then it 155// jumps to the default branch. At this point in the tree, the value 156// can't be another valid case value, so the jump to the "default" branch 157// is warranted. 158// 159BasicBlock* LowerSwitch::newLeafBlock(Case& Leaf, Value* Val, 160 BasicBlock* OrigBlock, 161 BasicBlock* Default) 162{ 163 Function* F = OrigBlock->getParent(); 164 BasicBlock* NewLeaf = new BasicBlock("LeafBlock"); 165 F->getBasicBlockList().insert(OrigBlock->getNext(), NewLeaf); 166 167 // Make the seteq instruction... 168 SetCondInst* Comp = new SetCondInst(Instruction::SetEQ, Val, 169 Leaf.first, "SwitchLeaf"); 170 NewLeaf->getInstList().push_back(Comp); 171 172 // Make the conditional branch... 173 BasicBlock* Succ = Leaf.second; 174 new BranchInst(Succ, Default, Comp, NewLeaf); 175 176 // If there were any PHI nodes in this successor, rewrite one entry 177 // from OrigBlock to come from NewLeaf. 178 for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) { 179 PHINode* PN = cast<PHINode>(I); 180 int BlockIdx = PN->getBasicBlockIndex(OrigBlock); 181 assert(BlockIdx != -1 && "Switch didn't go to this successor??"); 182 PN->setIncomingBlock((unsigned)BlockIdx, NewLeaf); 183 } 184 185 return NewLeaf; 186} 187 188// processSwitchInst - Replace the specified switch instruction with a sequence 189// of chained if-then insts in a balanced binary search. 190// 191void LowerSwitch::processSwitchInst(SwitchInst *SI) { 192 BasicBlock *CurBlock = SI->getParent(); 193 BasicBlock *OrigBlock = CurBlock; 194 Function *F = CurBlock->getParent(); 195 Value *Val = SI->getOperand(0); // The value we are switching on... 196 BasicBlock* Default = SI->getDefaultDest(); 197 198 // If there is only the default destination, don't bother with the code below. 199 if (SI->getNumOperands() == 2) { 200 new BranchInst(SI->getDefaultDest(), CurBlock); 201 CurBlock->getInstList().erase(SI); 202 return; 203 } 204 205 // Create a new, empty default block so that the new hierarchy of 206 // if-then statements go to this and the PHI nodes are happy. 207 BasicBlock* NewDefault = new BasicBlock("NewDefault"); 208 F->getBasicBlockList().insert(Default, NewDefault); 209 210 new BranchInst(Default, NewDefault); 211 212 // If there is an entry in any PHI nodes for the default edge, make sure 213 // to update them as well. 214 for (BasicBlock::iterator I = Default->begin(); isa<PHINode>(I); ++I) { 215 PHINode *PN = cast<PHINode>(I); 216 int BlockIdx = PN->getBasicBlockIndex(OrigBlock); 217 assert(BlockIdx != -1 && "Switch didn't go to this successor??"); 218 PN->setIncomingBlock((unsigned)BlockIdx, NewDefault); 219 } 220 221 std::vector<Case> Cases; 222 223 // Expand comparisons for all of the non-default cases... 224 for (unsigned i = 1; i < SI->getNumSuccessors(); ++i) 225 Cases.push_back(Case(SI->getSuccessorValue(i), SI->getSuccessor(i))); 226 227 std::sort(Cases.begin(), Cases.end(), CaseCmp()); 228 DOUT << "Cases: " << Cases << "\n"; 229 BasicBlock* SwitchBlock = switchConvert(Cases.begin(), Cases.end(), Val, 230 OrigBlock, NewDefault); 231 232 // Branch to our shiny new if-then stuff... 233 new BranchInst(SwitchBlock, OrigBlock); 234 235 // We are now done with the switch instruction, delete it. 236 CurBlock->getInstList().erase(SI); 237} 238