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 | // |
| 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. |
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 | // |
| 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" |
Chris Lattner | ebbc1a5 | 2003-10-07 18:46:23 +0000 | [diff] [blame] | 17 | #include "llvm/Constants.h" |
Chris Lattner | 1438348 | 2003-04-23 16:23:59 +0000 | [diff] [blame] | 18 | #include "llvm/Function.h" |
Misha Brukman | d8e1eea | 2004-07-29 17:05:13 +0000 | [diff] [blame] | 19 | #include "llvm/Instructions.h" |
Chris Lattner | 1438348 | 2003-04-23 16:23:59 +0000 | [diff] [blame] | 20 | #include "llvm/Pass.h" |
Reid Spencer | 551ccae | 2004-09-01 22:55:40 +0000 | [diff] [blame] | 21 | #include "llvm/Support/Debug.h" |
| 22 | #include "llvm/ADT/Statistic.h" |
Alkis Evlogimenos | 20aa474 | 2004-09-03 18:19:51 +0000 | [diff] [blame] | 23 | #include <algorithm> |
Chris Lattner | dac58ad | 2006-01-22 23:32:06 +0000 | [diff] [blame^] | 24 | #include <iostream> |
Chris Lattner | d745602 | 2004-01-09 06:02:20 +0000 | [diff] [blame] | 25 | using namespace llvm; |
Brian Gaeke | d0fde30 | 2003-11-11 22:41:34 +0000 | [diff] [blame] | 26 | |
Chris Lattner | 1438348 | 2003-04-23 16:23:59 +0000 | [diff] [blame] | 27 | namespace { |
| 28 | Statistic<> NumLowered("lowerswitch", "Number of SwitchInst's replaced"); |
| 29 | |
| 30 | /// LowerSwitch Pass - Replace all SwitchInst instructions with chained branch |
| 31 | /// instructions. Note that this cannot be a BasicBlock pass because it |
| 32 | /// modifies the CFG! |
Chris Lattner | ebbc1a5 | 2003-10-07 18:46:23 +0000 | [diff] [blame] | 33 | class LowerSwitch : public FunctionPass { |
| 34 | public: |
Chris Lattner | 1438348 | 2003-04-23 16:23:59 +0000 | [diff] [blame] | 35 | bool runOnFunction(Function &F); |
Chris Lattner | ebbc1a5 | 2003-10-07 18:46:23 +0000 | [diff] [blame] | 36 | typedef std::pair<Constant*, BasicBlock*> Case; |
| 37 | typedef std::vector<Case>::iterator CaseItr; |
| 38 | private: |
Chris Lattner | 1438348 | 2003-04-23 16:23:59 +0000 | [diff] [blame] | 39 | void processSwitchInst(SwitchInst *SI); |
Chris Lattner | ebbc1a5 | 2003-10-07 18:46:23 +0000 | [diff] [blame] | 40 | |
| 41 | BasicBlock* switchConvert(CaseItr Begin, CaseItr End, Value* Val, |
| 42 | BasicBlock* OrigBlock, BasicBlock* Default); |
| 43 | BasicBlock* newLeafBlock(Case& Leaf, Value* Val, |
| 44 | BasicBlock* OrigBlock, BasicBlock* Default); |
| 45 | }; |
| 46 | |
| 47 | /// The comparison function for sorting the switch case values in the vector. |
| 48 | struct CaseCmp { |
| 49 | bool operator () (const LowerSwitch::Case& C1, |
| 50 | const LowerSwitch::Case& C2) { |
| 51 | if (const ConstantUInt* U1 = dyn_cast<const ConstantUInt>(C1.first)) |
| 52 | return U1->getValue() < cast<const ConstantUInt>(C2.first)->getValue(); |
| 53 | |
| 54 | const ConstantSInt* S1 = dyn_cast<const ConstantSInt>(C1.first); |
| 55 | return S1->getValue() < cast<const ConstantSInt>(C2.first)->getValue(); |
| 56 | } |
Chris Lattner | 1438348 | 2003-04-23 16:23:59 +0000 | [diff] [blame] | 57 | }; |
| 58 | |
| 59 | RegisterOpt<LowerSwitch> |
| 60 | X("lowerswitch", "Lower SwitchInst's to branches"); |
| 61 | } |
| 62 | |
| 63 | // createLowerSwitchPass - Interface to this file... |
Chris Lattner | d745602 | 2004-01-09 06:02:20 +0000 | [diff] [blame] | 64 | FunctionPass *llvm::createLowerSwitchPass() { |
Chris Lattner | 1438348 | 2003-04-23 16:23:59 +0000 | [diff] [blame] | 65 | return new LowerSwitch(); |
| 66 | } |
| 67 | |
| 68 | bool LowerSwitch::runOnFunction(Function &F) { |
| 69 | bool Changed = false; |
| 70 | |
| 71 | for (Function::iterator I = F.begin(), E = F.end(); I != E; ) { |
| 72 | BasicBlock *Cur = I++; // Advance over block so we don't traverse new blocks |
| 73 | |
| 74 | if (SwitchInst *SI = dyn_cast<SwitchInst>(Cur->getTerminator())) { |
| 75 | Changed = true; |
| 76 | processSwitchInst(SI); |
| 77 | } |
| 78 | } |
| 79 | |
| 80 | return Changed; |
| 81 | } |
| 82 | |
Chris Lattner | ebbc1a5 | 2003-10-07 18:46:23 +0000 | [diff] [blame] | 83 | // operator<< - Used for debugging purposes. |
| 84 | // |
Chris Lattner | d745602 | 2004-01-09 06:02:20 +0000 | [diff] [blame] | 85 | std::ostream& operator<<(std::ostream &O, |
| 86 | const std::vector<LowerSwitch::Case> &C) { |
Chris Lattner | ebbc1a5 | 2003-10-07 18:46:23 +0000 | [diff] [blame] | 87 | O << "["; |
| 88 | |
Chris Lattner | d745602 | 2004-01-09 06:02:20 +0000 | [diff] [blame] | 89 | for (std::vector<LowerSwitch::Case>::const_iterator B = C.begin(), |
| 90 | E = C.end(); B != E; ) { |
Chris Lattner | ebbc1a5 | 2003-10-07 18:46:23 +0000 | [diff] [blame] | 91 | O << *B->first; |
| 92 | if (++B != E) O << ", "; |
| 93 | } |
| 94 | |
| 95 | return O << "]"; |
| 96 | } |
| 97 | |
| 98 | // switchConvert - Convert the switch statement into a binary lookup of |
| 99 | // the case values. The function recursively builds this tree. |
| 100 | // |
| 101 | BasicBlock* LowerSwitch::switchConvert(CaseItr Begin, CaseItr End, |
| 102 | Value* Val, BasicBlock* OrigBlock, |
| 103 | BasicBlock* Default) |
| 104 | { |
| 105 | unsigned Size = End - Begin; |
| 106 | |
| 107 | if (Size == 1) |
| 108 | return newLeafBlock(*Begin, Val, OrigBlock, Default); |
| 109 | |
| 110 | unsigned Mid = Size / 2; |
| 111 | std::vector<Case> LHS(Begin, Begin + Mid); |
| 112 | DEBUG(std::cerr << "LHS: " << LHS << "\n"); |
| 113 | std::vector<Case> RHS(Begin + Mid, End); |
| 114 | DEBUG(std::cerr << "RHS: " << RHS << "\n"); |
| 115 | |
| 116 | Case& Pivot = *(Begin + Mid); |
| 117 | DEBUG(std::cerr << "Pivot ==> " |
Chris Lattner | 940ff56 | 2004-02-25 15:15:04 +0000 | [diff] [blame] | 118 | << (int64_t)cast<ConstantInt>(Pivot.first)->getRawValue() |
| 119 | << "\n"); |
Chris Lattner | ebbc1a5 | 2003-10-07 18:46:23 +0000 | [diff] [blame] | 120 | |
| 121 | BasicBlock* LBranch = switchConvert(LHS.begin(), LHS.end(), Val, |
| 122 | OrigBlock, Default); |
| 123 | BasicBlock* RBranch = switchConvert(RHS.begin(), RHS.end(), Val, |
| 124 | OrigBlock, Default); |
| 125 | |
| 126 | // Create a new node that checks if the value is < pivot. Go to the |
| 127 | // left branch if it is and right branch if not. |
| 128 | Function* F = OrigBlock->getParent(); |
| 129 | BasicBlock* NewNode = new BasicBlock("NodeBlock"); |
| 130 | F->getBasicBlockList().insert(OrigBlock->getNext(), NewNode); |
| 131 | |
| 132 | SetCondInst* Comp = new SetCondInst(Instruction::SetLT, Val, Pivot.first, |
| 133 | "Pivot"); |
| 134 | NewNode->getInstList().push_back(Comp); |
Chris Lattner | f8485c6 | 2003-11-20 18:25:24 +0000 | [diff] [blame] | 135 | new BranchInst(LBranch, RBranch, Comp, NewNode); |
Chris Lattner | ebbc1a5 | 2003-10-07 18:46:23 +0000 | [diff] [blame] | 136 | return NewNode; |
| 137 | } |
| 138 | |
| 139 | // newLeafBlock - Create a new leaf block for the binary lookup tree. It |
| 140 | // checks if the switch's value == the case's value. If not, then it |
| 141 | // jumps to the default branch. At this point in the tree, the value |
| 142 | // can't be another valid case value, so the jump to the "default" branch |
| 143 | // is warranted. |
| 144 | // |
| 145 | BasicBlock* LowerSwitch::newLeafBlock(Case& Leaf, Value* Val, |
| 146 | BasicBlock* OrigBlock, |
| 147 | BasicBlock* Default) |
| 148 | { |
| 149 | Function* F = OrigBlock->getParent(); |
| 150 | BasicBlock* NewLeaf = new BasicBlock("LeafBlock"); |
| 151 | F->getBasicBlockList().insert(OrigBlock->getNext(), NewLeaf); |
| 152 | |
| 153 | // Make the seteq instruction... |
| 154 | SetCondInst* Comp = new SetCondInst(Instruction::SetEQ, Val, |
| 155 | Leaf.first, "SwitchLeaf"); |
| 156 | NewLeaf->getInstList().push_back(Comp); |
| 157 | |
| 158 | // Make the conditional branch... |
| 159 | BasicBlock* Succ = Leaf.second; |
Chris Lattner | f8485c6 | 2003-11-20 18:25:24 +0000 | [diff] [blame] | 160 | new BranchInst(Succ, Default, Comp, NewLeaf); |
Chris Lattner | ebbc1a5 | 2003-10-07 18:46:23 +0000 | [diff] [blame] | 161 | |
| 162 | // If there were any PHI nodes in this successor, rewrite one entry |
| 163 | // from OrigBlock to come from NewLeaf. |
Reid Spencer | 2da5c3d | 2004-09-15 17:06:42 +0000 | [diff] [blame] | 164 | for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) { |
| 165 | PHINode* PN = cast<PHINode>(I); |
Chris Lattner | ebbc1a5 | 2003-10-07 18:46:23 +0000 | [diff] [blame] | 166 | int BlockIdx = PN->getBasicBlockIndex(OrigBlock); |
| 167 | assert(BlockIdx != -1 && "Switch didn't go to this successor??"); |
| 168 | PN->setIncomingBlock((unsigned)BlockIdx, NewLeaf); |
| 169 | } |
| 170 | |
| 171 | return NewLeaf; |
| 172 | } |
| 173 | |
Chris Lattner | 1438348 | 2003-04-23 16:23:59 +0000 | [diff] [blame] | 174 | // processSwitchInst - Replace the specified switch instruction with a sequence |
Chris Lattner | ebbc1a5 | 2003-10-07 18:46:23 +0000 | [diff] [blame] | 175 | // of chained if-then insts in a balanced binary search. |
Chris Lattner | 1438348 | 2003-04-23 16:23:59 +0000 | [diff] [blame] | 176 | // |
| 177 | void LowerSwitch::processSwitchInst(SwitchInst *SI) { |
| 178 | BasicBlock *CurBlock = SI->getParent(); |
| 179 | BasicBlock *OrigBlock = CurBlock; |
| 180 | Function *F = CurBlock->getParent(); |
| 181 | Value *Val = SI->getOperand(0); // The value we are switching on... |
Chris Lattner | ebbc1a5 | 2003-10-07 18:46:23 +0000 | [diff] [blame] | 182 | BasicBlock* Default = SI->getDefaultDest(); |
Chris Lattner | 1438348 | 2003-04-23 16:23:59 +0000 | [diff] [blame] | 183 | |
Chris Lattner | 44bb541 | 2003-08-23 22:54:34 +0000 | [diff] [blame] | 184 | // If there is only the default destination, don't bother with the code below. |
| 185 | if (SI->getNumOperands() == 2) { |
Chris Lattner | 108e4ab | 2003-11-21 16:52:05 +0000 | [diff] [blame] | 186 | new BranchInst(SI->getDefaultDest(), CurBlock); |
Chris Lattner | bf9eadd | 2004-03-14 04:14:31 +0000 | [diff] [blame] | 187 | CurBlock->getInstList().erase(SI); |
Chris Lattner | 44bb541 | 2003-08-23 22:54:34 +0000 | [diff] [blame] | 188 | return; |
| 189 | } |
| 190 | |
Chris Lattner | ebbc1a5 | 2003-10-07 18:46:23 +0000 | [diff] [blame] | 191 | // Create a new, empty default block so that the new hierarchy of |
| 192 | // if-then statements go to this and the PHI nodes are happy. |
| 193 | BasicBlock* NewDefault = new BasicBlock("NewDefault"); |
| 194 | F->getBasicBlockList().insert(Default, NewDefault); |
Chris Lattner | 1438348 | 2003-04-23 16:23:59 +0000 | [diff] [blame] | 195 | |
Chris Lattner | 108e4ab | 2003-11-21 16:52:05 +0000 | [diff] [blame] | 196 | new BranchInst(Default, NewDefault); |
Chris Lattner | 1438348 | 2003-04-23 16:23:59 +0000 | [diff] [blame] | 197 | |
Chris Lattner | ebbc1a5 | 2003-10-07 18:46:23 +0000 | [diff] [blame] | 198 | // If there is an entry in any PHI nodes for the default edge, make sure |
| 199 | // to update them as well. |
Reid Spencer | 2da5c3d | 2004-09-15 17:06:42 +0000 | [diff] [blame] | 200 | for (BasicBlock::iterator I = Default->begin(); isa<PHINode>(I); ++I) { |
| 201 | PHINode *PN = cast<PHINode>(I); |
Chris Lattner | ebbc1a5 | 2003-10-07 18:46:23 +0000 | [diff] [blame] | 202 | int BlockIdx = PN->getBasicBlockIndex(OrigBlock); |
| 203 | assert(BlockIdx != -1 && "Switch didn't go to this successor??"); |
| 204 | PN->setIncomingBlock((unsigned)BlockIdx, NewDefault); |
Chris Lattner | 1438348 | 2003-04-23 16:23:59 +0000 | [diff] [blame] | 205 | } |
| 206 | |
Chris Lattner | ebbc1a5 | 2003-10-07 18:46:23 +0000 | [diff] [blame] | 207 | std::vector<Case> Cases; |
| 208 | |
| 209 | // Expand comparisons for all of the non-default cases... |
| 210 | for (unsigned i = 1; i < SI->getNumSuccessors(); ++i) |
| 211 | Cases.push_back(Case(SI->getSuccessorValue(i), SI->getSuccessor(i))); |
| 212 | |
| 213 | std::sort(Cases.begin(), Cases.end(), CaseCmp()); |
| 214 | DEBUG(std::cerr << "Cases: " << Cases << "\n"); |
| 215 | BasicBlock* SwitchBlock = switchConvert(Cases.begin(), Cases.end(), Val, |
| 216 | OrigBlock, NewDefault); |
| 217 | |
| 218 | // Branch to our shiny new if-then stuff... |
Chris Lattner | 108e4ab | 2003-11-21 16:52:05 +0000 | [diff] [blame] | 219 | new BranchInst(SwitchBlock, OrigBlock); |
Chris Lattner | ebbc1a5 | 2003-10-07 18:46:23 +0000 | [diff] [blame] | 220 | |
Chris Lattner | 1438348 | 2003-04-23 16:23:59 +0000 | [diff] [blame] | 221 | // We are now done with the switch instruction, delete it. |
Chris Lattner | bf9eadd | 2004-03-14 04:14:31 +0000 | [diff] [blame] | 222 | CurBlock->getInstList().erase(SI); |
Chris Lattner | 1438348 | 2003-04-23 16:23:59 +0000 | [diff] [blame] | 223 | } |