Chris Lattner | 1438348 | 2003-04-23 16:23:59 +0000 | [diff] [blame] | 1 | //===- LowerSwitch.cpp - Eliminate Switch instructions --------------------===// |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 2 | // |
John Criswell | b576c94 | 2003-10-20 19:43:21 +0000 | [diff] [blame] | 3 | // The LLVM Compiler Infrastructure |
| 4 | // |
Chris Lattner | 4ee451d | 2007-12-29 20:36:04 +0000 | [diff] [blame^] | 5 | // This file is distributed under the University of Illinois Open Source |
| 6 | // License. See LICENSE.TXT for details. |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 7 | // |
John Criswell | b576c94 | 2003-10-20 19:43:21 +0000 | [diff] [blame] | 8 | //===----------------------------------------------------------------------===// |
Chris Lattner | 1438348 | 2003-04-23 16:23:59 +0000 | [diff] [blame] | 9 | // |
Gordon Henriksen | c86b677 | 2007-11-04 16:15:04 +0000 | [diff] [blame] | 10 | // The LowerSwitch transformation rewrites switch instructions with a sequence |
| 11 | // of branches, which allows targets to get away with not implementing the |
| 12 | // switch instruction until it is convenient. |
Chris Lattner | 1438348 | 2003-04-23 16:23:59 +0000 | [diff] [blame] | 13 | // |
| 14 | //===----------------------------------------------------------------------===// |
| 15 | |
| 16 | #include "llvm/Transforms/Scalar.h" |
Chris Lattner | 8d89e7b | 2006-05-09 04:13:41 +0000 | [diff] [blame] | 17 | #include "llvm/Transforms/Utils/UnifyFunctionExitNodes.h" |
Chris Lattner | ebbc1a5 | 2003-10-07 18:46:23 +0000 | [diff] [blame] | 18 | #include "llvm/Constants.h" |
Chris Lattner | 1438348 | 2003-04-23 16:23:59 +0000 | [diff] [blame] | 19 | #include "llvm/Function.h" |
Misha Brukman | d8e1eea | 2004-07-29 17:05:13 +0000 | [diff] [blame] | 20 | #include "llvm/Instructions.h" |
Chris Lattner | 1438348 | 2003-04-23 16:23:59 +0000 | [diff] [blame] | 21 | #include "llvm/Pass.h" |
Dan Gohman | b61f2f0 | 2007-11-02 22:22:02 +0000 | [diff] [blame] | 22 | #include "llvm/ADT/STLExtras.h" |
Reid Spencer | 551ccae | 2004-09-01 22:55:40 +0000 | [diff] [blame] | 23 | #include "llvm/Support/Debug.h" |
Chris Lattner | a4f0b3a | 2006-08-27 12:54:02 +0000 | [diff] [blame] | 24 | #include "llvm/Support/Compiler.h" |
Alkis Evlogimenos | 20aa474 | 2004-09-03 18:19:51 +0000 | [diff] [blame] | 25 | #include <algorithm> |
Chris Lattner | d745602 | 2004-01-09 06:02:20 +0000 | [diff] [blame] | 26 | using namespace llvm; |
Brian Gaeke | d0fde30 | 2003-11-11 22:41:34 +0000 | [diff] [blame] | 27 | |
Chris Lattner | 1438348 | 2003-04-23 16:23:59 +0000 | [diff] [blame] | 28 | namespace { |
Chris Lattner | 1438348 | 2003-04-23 16:23:59 +0000 | [diff] [blame] | 29 | /// LowerSwitch Pass - Replace all SwitchInst instructions with chained branch |
| 30 | /// instructions. Note that this cannot be a BasicBlock pass because it |
| 31 | /// modifies the CFG! |
Chris Lattner | f4b5461 | 2006-06-28 22:08:15 +0000 | [diff] [blame] | 32 | class VISIBILITY_HIDDEN LowerSwitch : public FunctionPass { |
Chris Lattner | ebbc1a5 | 2003-10-07 18:46:23 +0000 | [diff] [blame] | 33 | public: |
Nick Lewycky | ecd94c8 | 2007-05-06 13:37:16 +0000 | [diff] [blame] | 34 | static char ID; // Pass identification, replacement for typeid |
Devang Patel | 794fd75 | 2007-05-01 21:15:47 +0000 | [diff] [blame] | 35 | LowerSwitch() : FunctionPass((intptr_t) &ID) {} |
| 36 | |
Chris Lattner | 8d89e7b | 2006-05-09 04:13:41 +0000 | [diff] [blame] | 37 | virtual bool runOnFunction(Function &F); |
Chris Lattner | ed96fe8 | 2006-05-17 21:05:27 +0000 | [diff] [blame] | 38 | |
Chris Lattner | 8d89e7b | 2006-05-09 04:13:41 +0000 | [diff] [blame] | 39 | virtual void getAnalysisUsage(AnalysisUsage &AU) const { |
Anton Korobeynikov | bed2946 | 2007-04-16 18:10:23 +0000 | [diff] [blame] | 40 | // This is a cluster of orthogonal Transforms |
Chris Lattner | 8d89e7b | 2006-05-09 04:13:41 +0000 | [diff] [blame] | 41 | AU.addPreserved<UnifyFunctionExitNodes>(); |
| 42 | AU.addPreservedID(PromoteMemoryToRegisterID); |
| 43 | AU.addPreservedID(LowerSelectID); |
Chris Lattner | ed96fe8 | 2006-05-17 21:05:27 +0000 | [diff] [blame] | 44 | AU.addPreservedID(LowerInvokePassID); |
| 45 | AU.addPreservedID(LowerAllocationsID); |
Chris Lattner | 8d89e7b | 2006-05-09 04:13:41 +0000 | [diff] [blame] | 46 | } |
Anton Korobeynikov | e2ff29c | 2007-03-10 16:46:28 +0000 | [diff] [blame] | 47 | |
| 48 | struct CaseRange { |
| 49 | Constant* Low; |
| 50 | Constant* High; |
| 51 | BasicBlock* BB; |
| 52 | |
Jeff Cohen | c4558fd | 2007-03-12 17:56:27 +0000 | [diff] [blame] | 53 | CaseRange() : Low(0), High(0), BB(0) { } |
| 54 | CaseRange(Constant* low, Constant* high, BasicBlock* bb) : |
| 55 | Low(low), High(high), BB(bb) { } |
Anton Korobeynikov | e2ff29c | 2007-03-10 16:46:28 +0000 | [diff] [blame] | 56 | }; |
| 57 | |
| 58 | typedef std::vector<CaseRange> CaseVector; |
| 59 | typedef std::vector<CaseRange>::iterator CaseItr; |
Chris Lattner | ebbc1a5 | 2003-10-07 18:46:23 +0000 | [diff] [blame] | 60 | private: |
Chris Lattner | 1438348 | 2003-04-23 16:23:59 +0000 | [diff] [blame] | 61 | void processSwitchInst(SwitchInst *SI); |
Chris Lattner | ebbc1a5 | 2003-10-07 18:46:23 +0000 | [diff] [blame] | 62 | |
| 63 | BasicBlock* switchConvert(CaseItr Begin, CaseItr End, Value* Val, |
| 64 | BasicBlock* OrigBlock, BasicBlock* Default); |
Anton Korobeynikov | e2ff29c | 2007-03-10 16:46:28 +0000 | [diff] [blame] | 65 | BasicBlock* newLeafBlock(CaseRange& Leaf, Value* Val, |
Chris Lattner | ebbc1a5 | 2003-10-07 18:46:23 +0000 | [diff] [blame] | 66 | BasicBlock* OrigBlock, BasicBlock* Default); |
Anton Korobeynikov | e2ff29c | 2007-03-10 16:46:28 +0000 | [diff] [blame] | 67 | unsigned Clusterify(CaseVector& Cases, SwitchInst *SI); |
Chris Lattner | ebbc1a5 | 2003-10-07 18:46:23 +0000 | [diff] [blame] | 68 | }; |
| 69 | |
| 70 | /// The comparison function for sorting the switch case values in the vector. |
Anton Korobeynikov | e2ff29c | 2007-03-10 16:46:28 +0000 | [diff] [blame] | 71 | /// WARNING: Case ranges should be disjoint! |
Chris Lattner | ebbc1a5 | 2003-10-07 18:46:23 +0000 | [diff] [blame] | 72 | struct CaseCmp { |
Anton Korobeynikov | e2ff29c | 2007-03-10 16:46:28 +0000 | [diff] [blame] | 73 | bool operator () (const LowerSwitch::CaseRange& C1, |
| 74 | const LowerSwitch::CaseRange& C2) { |
Chris Lattner | ebbc1a5 | 2003-10-07 18:46:23 +0000 | [diff] [blame] | 75 | |
Anton Korobeynikov | e2ff29c | 2007-03-10 16:46:28 +0000 | [diff] [blame] | 76 | const ConstantInt* CI1 = cast<const ConstantInt>(C1.Low); |
| 77 | const ConstantInt* CI2 = cast<const ConstantInt>(C2.High); |
| 78 | return CI1->getValue().slt(CI2->getValue()); |
Chris Lattner | ebbc1a5 | 2003-10-07 18:46:23 +0000 | [diff] [blame] | 79 | } |
Chris Lattner | 1438348 | 2003-04-23 16:23:59 +0000 | [diff] [blame] | 80 | }; |
| 81 | |
Devang Patel | 1997473 | 2007-05-03 01:11:54 +0000 | [diff] [blame] | 82 | char LowerSwitch::ID = 0; |
Chris Lattner | 7f8897f | 2006-08-27 22:42:52 +0000 | [diff] [blame] | 83 | RegisterPass<LowerSwitch> |
Chris Lattner | 1438348 | 2003-04-23 16:23:59 +0000 | [diff] [blame] | 84 | X("lowerswitch", "Lower SwitchInst's to branches"); |
| 85 | } |
| 86 | |
Chris Lattner | b3674e4 | 2006-05-02 04:24:36 +0000 | [diff] [blame] | 87 | // Publically exposed interface to pass... |
| 88 | const PassInfo *llvm::LowerSwitchID = X.getPassInfo(); |
Chris Lattner | 1438348 | 2003-04-23 16:23:59 +0000 | [diff] [blame] | 89 | // createLowerSwitchPass - Interface to this file... |
Chris Lattner | d745602 | 2004-01-09 06:02:20 +0000 | [diff] [blame] | 90 | FunctionPass *llvm::createLowerSwitchPass() { |
Chris Lattner | 1438348 | 2003-04-23 16:23:59 +0000 | [diff] [blame] | 91 | return new LowerSwitch(); |
| 92 | } |
| 93 | |
| 94 | bool LowerSwitch::runOnFunction(Function &F) { |
| 95 | bool Changed = false; |
| 96 | |
| 97 | for (Function::iterator I = F.begin(), E = F.end(); I != E; ) { |
| 98 | BasicBlock *Cur = I++; // Advance over block so we don't traverse new blocks |
| 99 | |
| 100 | if (SwitchInst *SI = dyn_cast<SwitchInst>(Cur->getTerminator())) { |
| 101 | Changed = true; |
| 102 | processSwitchInst(SI); |
| 103 | } |
| 104 | } |
| 105 | |
| 106 | return Changed; |
| 107 | } |
| 108 | |
Chris Lattner | ebbc1a5 | 2003-10-07 18:46:23 +0000 | [diff] [blame] | 109 | // operator<< - Used for debugging purposes. |
| 110 | // |
Anton Korobeynikov | e2ff29c | 2007-03-10 16:46:28 +0000 | [diff] [blame] | 111 | static std::ostream& operator<<(std::ostream &O, |
| 112 | const LowerSwitch::CaseVector &C) { |
Chris Lattner | ebbc1a5 | 2003-10-07 18:46:23 +0000 | [diff] [blame] | 113 | O << "["; |
| 114 | |
Anton Korobeynikov | e2ff29c | 2007-03-10 16:46:28 +0000 | [diff] [blame] | 115 | for (LowerSwitch::CaseVector::const_iterator B = C.begin(), |
Chris Lattner | d745602 | 2004-01-09 06:02:20 +0000 | [diff] [blame] | 116 | E = C.end(); B != E; ) { |
Anton Korobeynikov | e2ff29c | 2007-03-10 16:46:28 +0000 | [diff] [blame] | 117 | O << *B->Low << " -" << *B->High; |
Chris Lattner | ebbc1a5 | 2003-10-07 18:46:23 +0000 | [diff] [blame] | 118 | if (++B != E) O << ", "; |
| 119 | } |
| 120 | |
| 121 | return O << "]"; |
| 122 | } |
Anton Korobeynikov | e2ff29c | 2007-03-10 16:46:28 +0000 | [diff] [blame] | 123 | |
| 124 | static OStream& operator<<(OStream &O, const LowerSwitch::CaseVector &C) { |
Bill Wendling | 5c7e326 | 2006-12-17 05:15:13 +0000 | [diff] [blame] | 125 | if (O.stream()) *O.stream() << C; |
| 126 | return O; |
| 127 | } |
Chris Lattner | ebbc1a5 | 2003-10-07 18:46:23 +0000 | [diff] [blame] | 128 | |
| 129 | // switchConvert - Convert the switch statement into a binary lookup of |
| 130 | // the case values. The function recursively builds this tree. |
| 131 | // |
| 132 | BasicBlock* LowerSwitch::switchConvert(CaseItr Begin, CaseItr End, |
| 133 | Value* Val, BasicBlock* OrigBlock, |
| 134 | BasicBlock* Default) |
| 135 | { |
| 136 | unsigned Size = End - Begin; |
| 137 | |
| 138 | if (Size == 1) |
| 139 | return newLeafBlock(*Begin, Val, OrigBlock, Default); |
| 140 | |
| 141 | unsigned Mid = Size / 2; |
Anton Korobeynikov | e2ff29c | 2007-03-10 16:46:28 +0000 | [diff] [blame] | 142 | std::vector<CaseRange> LHS(Begin, Begin + Mid); |
Bill Wendling | 0d45a09 | 2006-11-26 10:17:54 +0000 | [diff] [blame] | 143 | DOUT << "LHS: " << LHS << "\n"; |
Anton Korobeynikov | e2ff29c | 2007-03-10 16:46:28 +0000 | [diff] [blame] | 144 | std::vector<CaseRange> RHS(Begin + Mid, End); |
Bill Wendling | 0d45a09 | 2006-11-26 10:17:54 +0000 | [diff] [blame] | 145 | DOUT << "RHS: " << RHS << "\n"; |
Chris Lattner | ebbc1a5 | 2003-10-07 18:46:23 +0000 | [diff] [blame] | 146 | |
Anton Korobeynikov | e2ff29c | 2007-03-10 16:46:28 +0000 | [diff] [blame] | 147 | CaseRange& Pivot = *(Begin + Mid); |
Reid Spencer | e8391e0 | 2007-03-02 23:15:21 +0000 | [diff] [blame] | 148 | DEBUG( DOUT << "Pivot ==> " |
Anton Korobeynikov | e2ff29c | 2007-03-10 16:46:28 +0000 | [diff] [blame] | 149 | << cast<ConstantInt>(Pivot.Low)->getValue().toStringSigned(10) |
| 150 | << " -" |
| 151 | << cast<ConstantInt>(Pivot.High)->getValue().toStringSigned(10) |
Reid Spencer | e8391e0 | 2007-03-02 23:15:21 +0000 | [diff] [blame] | 152 | << "\n"); |
Chris Lattner | ebbc1a5 | 2003-10-07 18:46:23 +0000 | [diff] [blame] | 153 | |
| 154 | BasicBlock* LBranch = switchConvert(LHS.begin(), LHS.end(), Val, |
| 155 | OrigBlock, Default); |
| 156 | BasicBlock* RBranch = switchConvert(RHS.begin(), RHS.end(), Val, |
| 157 | OrigBlock, Default); |
| 158 | |
| 159 | // Create a new node that checks if the value is < pivot. Go to the |
| 160 | // left branch if it is and right branch if not. |
| 161 | Function* F = OrigBlock->getParent(); |
| 162 | BasicBlock* NewNode = new BasicBlock("NodeBlock"); |
Chris Lattner | 261cdfb | 2007-04-17 18:09:47 +0000 | [diff] [blame] | 163 | Function::iterator FI = OrigBlock; |
| 164 | F->getBasicBlockList().insert(++FI, NewNode); |
Chris Lattner | ebbc1a5 | 2003-10-07 18:46:23 +0000 | [diff] [blame] | 165 | |
Anton Korobeynikov | e2ff29c | 2007-03-10 16:46:28 +0000 | [diff] [blame] | 166 | ICmpInst* Comp = new ICmpInst(ICmpInst::ICMP_SLT, Val, Pivot.Low, "Pivot"); |
Chris Lattner | ebbc1a5 | 2003-10-07 18:46:23 +0000 | [diff] [blame] | 167 | NewNode->getInstList().push_back(Comp); |
Chris Lattner | f8485c6 | 2003-11-20 18:25:24 +0000 | [diff] [blame] | 168 | new BranchInst(LBranch, RBranch, Comp, NewNode); |
Chris Lattner | ebbc1a5 | 2003-10-07 18:46:23 +0000 | [diff] [blame] | 169 | return NewNode; |
| 170 | } |
| 171 | |
| 172 | // newLeafBlock - Create a new leaf block for the binary lookup tree. It |
| 173 | // checks if the switch's value == the case's value. If not, then it |
| 174 | // jumps to the default branch. At this point in the tree, the value |
| 175 | // can't be another valid case value, so the jump to the "default" branch |
| 176 | // is warranted. |
| 177 | // |
Anton Korobeynikov | e2ff29c | 2007-03-10 16:46:28 +0000 | [diff] [blame] | 178 | BasicBlock* LowerSwitch::newLeafBlock(CaseRange& Leaf, Value* Val, |
Chris Lattner | ebbc1a5 | 2003-10-07 18:46:23 +0000 | [diff] [blame] | 179 | BasicBlock* OrigBlock, |
| 180 | BasicBlock* Default) |
| 181 | { |
| 182 | Function* F = OrigBlock->getParent(); |
| 183 | BasicBlock* NewLeaf = new BasicBlock("LeafBlock"); |
Chris Lattner | 261cdfb | 2007-04-17 18:09:47 +0000 | [diff] [blame] | 184 | Function::iterator FI = OrigBlock; |
| 185 | F->getBasicBlockList().insert(++FI, NewLeaf); |
Chris Lattner | ebbc1a5 | 2003-10-07 18:46:23 +0000 | [diff] [blame] | 186 | |
Anton Korobeynikov | e2ff29c | 2007-03-10 16:46:28 +0000 | [diff] [blame] | 187 | // Emit comparison |
| 188 | ICmpInst* Comp = NULL; |
| 189 | if (Leaf.Low == Leaf.High) { |
| 190 | // Make the seteq instruction... |
| 191 | Comp = new ICmpInst(ICmpInst::ICMP_EQ, Val, Leaf.Low, |
| 192 | "SwitchLeaf", NewLeaf); |
| 193 | } else { |
| 194 | // Make range comparison |
| 195 | if (cast<ConstantInt>(Leaf.Low)->isMinValue(true /*isSigned*/)) { |
| 196 | // Val >= Min && Val <= Hi --> Val <= Hi |
| 197 | Comp = new ICmpInst(ICmpInst::ICMP_SLE, Val, Leaf.High, |
| 198 | "SwitchLeaf", NewLeaf); |
| 199 | } else if (cast<ConstantInt>(Leaf.Low)->isZero()) { |
| 200 | // Val >= 0 && Val <= Hi --> Val <=u Hi |
| 201 | Comp = new ICmpInst(ICmpInst::ICMP_ULE, Val, Leaf.High, |
| 202 | "SwitchLeaf", NewLeaf); |
| 203 | } else { |
| 204 | // Emit V-Lo <=u Hi-Lo |
| 205 | Constant* NegLo = ConstantExpr::getNeg(Leaf.Low); |
| 206 | Instruction* Add = BinaryOperator::createAdd(Val, NegLo, |
| 207 | Val->getName()+".off", |
| 208 | NewLeaf); |
| 209 | Constant *UpperBound = ConstantExpr::getAdd(NegLo, Leaf.High); |
| 210 | Comp = new ICmpInst(ICmpInst::ICMP_ULE, Add, UpperBound, |
| 211 | "SwitchLeaf", NewLeaf); |
| 212 | } |
| 213 | } |
Chris Lattner | ebbc1a5 | 2003-10-07 18:46:23 +0000 | [diff] [blame] | 214 | |
| 215 | // Make the conditional branch... |
Anton Korobeynikov | e2ff29c | 2007-03-10 16:46:28 +0000 | [diff] [blame] | 216 | BasicBlock* Succ = Leaf.BB; |
Chris Lattner | f8485c6 | 2003-11-20 18:25:24 +0000 | [diff] [blame] | 217 | new BranchInst(Succ, Default, Comp, NewLeaf); |
Chris Lattner | ebbc1a5 | 2003-10-07 18:46:23 +0000 | [diff] [blame] | 218 | |
| 219 | // If there were any PHI nodes in this successor, rewrite one entry |
| 220 | // from OrigBlock to come from NewLeaf. |
Reid Spencer | 2da5c3d | 2004-09-15 17:06:42 +0000 | [diff] [blame] | 221 | for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) { |
| 222 | PHINode* PN = cast<PHINode>(I); |
Anton Korobeynikov | e2ff29c | 2007-03-10 16:46:28 +0000 | [diff] [blame] | 223 | // Remove all but one incoming entries from the cluster |
| 224 | uint64_t Range = cast<ConstantInt>(Leaf.High)->getSExtValue() - |
| 225 | cast<ConstantInt>(Leaf.Low)->getSExtValue(); |
| 226 | for (uint64_t j = 0; j < Range; ++j) { |
| 227 | PN->removeIncomingValue(OrigBlock); |
| 228 | } |
| 229 | |
Chris Lattner | ebbc1a5 | 2003-10-07 18:46:23 +0000 | [diff] [blame] | 230 | int BlockIdx = PN->getBasicBlockIndex(OrigBlock); |
| 231 | assert(BlockIdx != -1 && "Switch didn't go to this successor??"); |
| 232 | PN->setIncomingBlock((unsigned)BlockIdx, NewLeaf); |
| 233 | } |
| 234 | |
| 235 | return NewLeaf; |
| 236 | } |
| 237 | |
Anton Korobeynikov | e2ff29c | 2007-03-10 16:46:28 +0000 | [diff] [blame] | 238 | // Clusterify - Transform simple list of Cases into list of CaseRange's |
| 239 | unsigned LowerSwitch::Clusterify(CaseVector& Cases, SwitchInst *SI) { |
| 240 | unsigned numCmps = 0; |
| 241 | |
| 242 | // Start with "simple" cases |
| 243 | for (unsigned i = 1; i < SI->getNumSuccessors(); ++i) |
| 244 | Cases.push_back(CaseRange(SI->getSuccessorValue(i), |
| 245 | SI->getSuccessorValue(i), |
| 246 | SI->getSuccessor(i))); |
Dan Gohman | 111c4f8 | 2007-11-02 22:24:01 +0000 | [diff] [blame] | 247 | std::sort(Cases.begin(), Cases.end(), CaseCmp()); |
Anton Korobeynikov | e2ff29c | 2007-03-10 16:46:28 +0000 | [diff] [blame] | 248 | |
| 249 | // Merge case into clusters |
| 250 | if (Cases.size()>=2) |
David Greene | 9dfb11d | 2007-12-17 17:42:03 +0000 | [diff] [blame] | 251 | for (CaseItr I=Cases.begin(), J=next(Cases.begin()); J!=Cases.end(); ) { |
Anton Korobeynikov | e2ff29c | 2007-03-10 16:46:28 +0000 | [diff] [blame] | 252 | int64_t nextValue = cast<ConstantInt>(J->Low)->getSExtValue(); |
| 253 | int64_t currentValue = cast<ConstantInt>(I->High)->getSExtValue(); |
| 254 | BasicBlock* nextBB = J->BB; |
| 255 | BasicBlock* currentBB = I->BB; |
| 256 | |
| 257 | // If the two neighboring cases go to the same destination, merge them |
| 258 | // into a single case. |
| 259 | if ((nextValue-currentValue==1) && (currentBB == nextBB)) { |
| 260 | I->High = J->High; |
| 261 | J = Cases.erase(J); |
| 262 | } else { |
| 263 | I = J++; |
| 264 | } |
| 265 | } |
| 266 | |
| 267 | for (CaseItr I=Cases.begin(), E=Cases.end(); I!=E; ++I, ++numCmps) { |
| 268 | if (I->Low != I->High) |
| 269 | // A range counts double, since it requires two compares. |
| 270 | ++numCmps; |
| 271 | } |
| 272 | |
| 273 | return numCmps; |
| 274 | } |
| 275 | |
Chris Lattner | 1438348 | 2003-04-23 16:23:59 +0000 | [diff] [blame] | 276 | // processSwitchInst - Replace the specified switch instruction with a sequence |
Chris Lattner | ebbc1a5 | 2003-10-07 18:46:23 +0000 | [diff] [blame] | 277 | // of chained if-then insts in a balanced binary search. |
Chris Lattner | 1438348 | 2003-04-23 16:23:59 +0000 | [diff] [blame] | 278 | // |
| 279 | void LowerSwitch::processSwitchInst(SwitchInst *SI) { |
| 280 | BasicBlock *CurBlock = SI->getParent(); |
| 281 | BasicBlock *OrigBlock = CurBlock; |
| 282 | Function *F = CurBlock->getParent(); |
| 283 | Value *Val = SI->getOperand(0); // The value we are switching on... |
Chris Lattner | ebbc1a5 | 2003-10-07 18:46:23 +0000 | [diff] [blame] | 284 | BasicBlock* Default = SI->getDefaultDest(); |
Chris Lattner | 1438348 | 2003-04-23 16:23:59 +0000 | [diff] [blame] | 285 | |
Chris Lattner | 44bb541 | 2003-08-23 22:54:34 +0000 | [diff] [blame] | 286 | // If there is only the default destination, don't bother with the code below. |
| 287 | if (SI->getNumOperands() == 2) { |
Chris Lattner | 108e4ab | 2003-11-21 16:52:05 +0000 | [diff] [blame] | 288 | new BranchInst(SI->getDefaultDest(), CurBlock); |
Chris Lattner | bf9eadd | 2004-03-14 04:14:31 +0000 | [diff] [blame] | 289 | CurBlock->getInstList().erase(SI); |
Chris Lattner | 44bb541 | 2003-08-23 22:54:34 +0000 | [diff] [blame] | 290 | return; |
| 291 | } |
| 292 | |
Chris Lattner | ebbc1a5 | 2003-10-07 18:46:23 +0000 | [diff] [blame] | 293 | // Create a new, empty default block so that the new hierarchy of |
| 294 | // if-then statements go to this and the PHI nodes are happy. |
| 295 | BasicBlock* NewDefault = new BasicBlock("NewDefault"); |
| 296 | F->getBasicBlockList().insert(Default, NewDefault); |
Chris Lattner | 1438348 | 2003-04-23 16:23:59 +0000 | [diff] [blame] | 297 | |
Chris Lattner | 108e4ab | 2003-11-21 16:52:05 +0000 | [diff] [blame] | 298 | new BranchInst(Default, NewDefault); |
Chris Lattner | 1438348 | 2003-04-23 16:23:59 +0000 | [diff] [blame] | 299 | |
Chris Lattner | ebbc1a5 | 2003-10-07 18:46:23 +0000 | [diff] [blame] | 300 | // If there is an entry in any PHI nodes for the default edge, make sure |
| 301 | // to update them as well. |
Reid Spencer | 2da5c3d | 2004-09-15 17:06:42 +0000 | [diff] [blame] | 302 | for (BasicBlock::iterator I = Default->begin(); isa<PHINode>(I); ++I) { |
| 303 | PHINode *PN = cast<PHINode>(I); |
Chris Lattner | ebbc1a5 | 2003-10-07 18:46:23 +0000 | [diff] [blame] | 304 | int BlockIdx = PN->getBasicBlockIndex(OrigBlock); |
| 305 | assert(BlockIdx != -1 && "Switch didn't go to this successor??"); |
| 306 | PN->setIncomingBlock((unsigned)BlockIdx, NewDefault); |
Chris Lattner | 1438348 | 2003-04-23 16:23:59 +0000 | [diff] [blame] | 307 | } |
| 308 | |
Anton Korobeynikov | e2ff29c | 2007-03-10 16:46:28 +0000 | [diff] [blame] | 309 | // Prepare cases vector. |
| 310 | CaseVector Cases; |
| 311 | unsigned numCmps = Clusterify(Cases, SI); |
Chris Lattner | ebbc1a5 | 2003-10-07 18:46:23 +0000 | [diff] [blame] | 312 | |
Anton Korobeynikov | e2ff29c | 2007-03-10 16:46:28 +0000 | [diff] [blame] | 313 | DOUT << "Clusterify finished. Total clusters: " << Cases.size() |
| 314 | << ". Total compares: " << numCmps << "\n"; |
Bill Wendling | 0d45a09 | 2006-11-26 10:17:54 +0000 | [diff] [blame] | 315 | DOUT << "Cases: " << Cases << "\n"; |
Anton Korobeynikov | e2ff29c | 2007-03-10 16:46:28 +0000 | [diff] [blame] | 316 | |
Chris Lattner | ebbc1a5 | 2003-10-07 18:46:23 +0000 | [diff] [blame] | 317 | BasicBlock* SwitchBlock = switchConvert(Cases.begin(), Cases.end(), Val, |
| 318 | OrigBlock, NewDefault); |
| 319 | |
| 320 | // Branch to our shiny new if-then stuff... |
Chris Lattner | 108e4ab | 2003-11-21 16:52:05 +0000 | [diff] [blame] | 321 | new BranchInst(SwitchBlock, OrigBlock); |
Chris Lattner | ebbc1a5 | 2003-10-07 18:46:23 +0000 | [diff] [blame] | 322 | |
Chris Lattner | 1438348 | 2003-04-23 16:23:59 +0000 | [diff] [blame] | 323 | // We are now done with the switch instruction, delete it. |
Chris Lattner | bf9eadd | 2004-03-14 04:14:31 +0000 | [diff] [blame] | 324 | CurBlock->getInstList().erase(SI); |
Chris Lattner | 1438348 | 2003-04-23 16:23:59 +0000 | [diff] [blame] | 325 | } |