blob: 14d3027b918f50228fc2f314a6bf947a9ab16d7b [file] [log] [blame]
Chris Lattner1b094a02003-04-23 16:23:59 +00001//===- LowerSwitch.cpp - Eliminate Switch instructions --------------------===//
Misha Brukmanb1c93172005-04-21 23:48:37 +00002//
John Criswell482202a2003-10-20 19:43:21 +00003// 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 Brukmanb1c93172005-04-21 23:48:37 +00007//
John Criswell482202a2003-10-20 19:43:21 +00008//===----------------------------------------------------------------------===//
Chris Lattner1b094a02003-04-23 16:23:59 +00009//
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 Lattner4fe87d62006-05-09 04:13:41 +000017#include "llvm/Transforms/Utils/UnifyFunctionExitNodes.h"
Chris Lattnered922162003-10-07 18:46:23 +000018#include "llvm/Constants.h"
Chris Lattner1b094a02003-04-23 16:23:59 +000019#include "llvm/Function.h"
Misha Brukman2b3387a2004-07-29 17:05:13 +000020#include "llvm/Instructions.h"
Chris Lattner1b094a02003-04-23 16:23:59 +000021#include "llvm/Pass.h"
Reid Spencer7c16caa2004-09-01 22:55:40 +000022#include "llvm/Support/Debug.h"
23#include "llvm/ADT/Statistic.h"
Alkis Evlogimenosa5c04ee2004-09-03 18:19:51 +000024#include <algorithm>
Chris Lattnerc597b8a2006-01-22 23:32:06 +000025#include <iostream>
Chris Lattner49525f82004-01-09 06:02:20 +000026using namespace llvm;
Brian Gaeke960707c2003-11-11 22:41:34 +000027
Chris Lattner1b094a02003-04-23 16:23:59 +000028namespace {
29 Statistic<> NumLowered("lowerswitch", "Number of SwitchInst's replaced");
30
31 /// LowerSwitch Pass - Replace all SwitchInst instructions with chained branch
32 /// instructions. Note that this cannot be a BasicBlock pass because it
33 /// modifies the CFG!
Chris Lattnered922162003-10-07 18:46:23 +000034 class LowerSwitch : public FunctionPass {
35 public:
Chris Lattner4fe87d62006-05-09 04:13:41 +000036 virtual bool runOnFunction(Function &F);
37
38 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
39 // This is a cluster of orthogonal Transforms
40 AU.addPreserved<UnifyFunctionExitNodes>();
41 AU.addPreservedID(PromoteMemoryToRegisterID);
42 AU.addPreservedID(LowerSelectID);
43 }
44
Chris Lattnered922162003-10-07 18:46:23 +000045 typedef std::pair<Constant*, BasicBlock*> Case;
46 typedef std::vector<Case>::iterator CaseItr;
47 private:
Chris Lattner1b094a02003-04-23 16:23:59 +000048 void processSwitchInst(SwitchInst *SI);
Chris Lattnered922162003-10-07 18:46:23 +000049
50 BasicBlock* switchConvert(CaseItr Begin, CaseItr End, Value* Val,
51 BasicBlock* OrigBlock, BasicBlock* Default);
52 BasicBlock* newLeafBlock(Case& Leaf, Value* Val,
53 BasicBlock* OrigBlock, BasicBlock* Default);
54 };
55
56 /// The comparison function for sorting the switch case values in the vector.
57 struct CaseCmp {
58 bool operator () (const LowerSwitch::Case& C1,
59 const LowerSwitch::Case& C2) {
60 if (const ConstantUInt* U1 = dyn_cast<const ConstantUInt>(C1.first))
61 return U1->getValue() < cast<const ConstantUInt>(C2.first)->getValue();
62
63 const ConstantSInt* S1 = dyn_cast<const ConstantSInt>(C1.first);
64 return S1->getValue() < cast<const ConstantSInt>(C2.first)->getValue();
65 }
Chris Lattner1b094a02003-04-23 16:23:59 +000066 };
67
68 RegisterOpt<LowerSwitch>
69 X("lowerswitch", "Lower SwitchInst's to branches");
70}
71
Chris Lattner2d3a0272006-05-02 04:24:36 +000072// Publically exposed interface to pass...
73const PassInfo *llvm::LowerSwitchID = X.getPassInfo();
Chris Lattner1b094a02003-04-23 16:23:59 +000074// createLowerSwitchPass - Interface to this file...
Chris Lattner49525f82004-01-09 06:02:20 +000075FunctionPass *llvm::createLowerSwitchPass() {
Chris Lattner1b094a02003-04-23 16:23:59 +000076 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
Chris Lattnered922162003-10-07 18:46:23 +000094// operator<< - Used for debugging purposes.
95//
Chris Lattner49525f82004-01-09 06:02:20 +000096std::ostream& operator<<(std::ostream &O,
97 const std::vector<LowerSwitch::Case> &C) {
Chris Lattnered922162003-10-07 18:46:23 +000098 O << "[";
99
Chris Lattner49525f82004-01-09 06:02:20 +0000100 for (std::vector<LowerSwitch::Case>::const_iterator B = C.begin(),
101 E = C.end(); B != E; ) {
Chris Lattnered922162003-10-07 18:46:23 +0000102 O << *B->first;
103 if (++B != E) O << ", ";
104 }
105
106 return O << "]";
107}
108
109// switchConvert - Convert the switch statement into a binary lookup of
110// the case values. The function recursively builds this tree.
111//
112BasicBlock* LowerSwitch::switchConvert(CaseItr Begin, CaseItr End,
113 Value* Val, BasicBlock* OrigBlock,
114 BasicBlock* Default)
115{
116 unsigned Size = End - Begin;
117
118 if (Size == 1)
119 return newLeafBlock(*Begin, Val, OrigBlock, Default);
120
121 unsigned Mid = Size / 2;
122 std::vector<Case> LHS(Begin, Begin + Mid);
123 DEBUG(std::cerr << "LHS: " << LHS << "\n");
124 std::vector<Case> RHS(Begin + Mid, End);
125 DEBUG(std::cerr << "RHS: " << RHS << "\n");
126
127 Case& Pivot = *(Begin + Mid);
128 DEBUG(std::cerr << "Pivot ==> "
Chris Lattner9c6833c2004-02-25 15:15:04 +0000129 << (int64_t)cast<ConstantInt>(Pivot.first)->getRawValue()
130 << "\n");
Chris Lattnered922162003-10-07 18:46:23 +0000131
132 BasicBlock* LBranch = switchConvert(LHS.begin(), LHS.end(), Val,
133 OrigBlock, Default);
134 BasicBlock* RBranch = switchConvert(RHS.begin(), RHS.end(), Val,
135 OrigBlock, Default);
136
137 // Create a new node that checks if the value is < pivot. Go to the
138 // left branch if it is and right branch if not.
139 Function* F = OrigBlock->getParent();
140 BasicBlock* NewNode = new BasicBlock("NodeBlock");
141 F->getBasicBlockList().insert(OrigBlock->getNext(), NewNode);
142
143 SetCondInst* Comp = new SetCondInst(Instruction::SetLT, Val, Pivot.first,
144 "Pivot");
145 NewNode->getInstList().push_back(Comp);
Chris Lattner2af51722003-11-20 18:25:24 +0000146 new BranchInst(LBranch, RBranch, Comp, NewNode);
Chris Lattnered922162003-10-07 18:46:23 +0000147 return NewNode;
148}
149
150// newLeafBlock - Create a new leaf block for the binary lookup tree. It
151// checks if the switch's value == the case's value. If not, then it
152// jumps to the default branch. At this point in the tree, the value
153// can't be another valid case value, so the jump to the "default" branch
154// is warranted.
155//
156BasicBlock* LowerSwitch::newLeafBlock(Case& Leaf, Value* Val,
157 BasicBlock* OrigBlock,
158 BasicBlock* Default)
159{
160 Function* F = OrigBlock->getParent();
161 BasicBlock* NewLeaf = new BasicBlock("LeafBlock");
162 F->getBasicBlockList().insert(OrigBlock->getNext(), NewLeaf);
163
164 // Make the seteq instruction...
165 SetCondInst* Comp = new SetCondInst(Instruction::SetEQ, Val,
166 Leaf.first, "SwitchLeaf");
167 NewLeaf->getInstList().push_back(Comp);
168
169 // Make the conditional branch...
170 BasicBlock* Succ = Leaf.second;
Chris Lattner2af51722003-11-20 18:25:24 +0000171 new BranchInst(Succ, Default, Comp, NewLeaf);
Chris Lattnered922162003-10-07 18:46:23 +0000172
173 // If there were any PHI nodes in this successor, rewrite one entry
174 // from OrigBlock to come from NewLeaf.
Reid Spencer66149462004-09-15 17:06:42 +0000175 for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) {
176 PHINode* PN = cast<PHINode>(I);
Chris Lattnered922162003-10-07 18:46:23 +0000177 int BlockIdx = PN->getBasicBlockIndex(OrigBlock);
178 assert(BlockIdx != -1 && "Switch didn't go to this successor??");
179 PN->setIncomingBlock((unsigned)BlockIdx, NewLeaf);
180 }
181
182 return NewLeaf;
183}
184
Chris Lattner1b094a02003-04-23 16:23:59 +0000185// processSwitchInst - Replace the specified switch instruction with a sequence
Chris Lattnered922162003-10-07 18:46:23 +0000186// of chained if-then insts in a balanced binary search.
Chris Lattner1b094a02003-04-23 16:23:59 +0000187//
188void LowerSwitch::processSwitchInst(SwitchInst *SI) {
189 BasicBlock *CurBlock = SI->getParent();
190 BasicBlock *OrigBlock = CurBlock;
191 Function *F = CurBlock->getParent();
192 Value *Val = SI->getOperand(0); // The value we are switching on...
Chris Lattnered922162003-10-07 18:46:23 +0000193 BasicBlock* Default = SI->getDefaultDest();
Chris Lattner1b094a02003-04-23 16:23:59 +0000194
Chris Lattnerf1b1c5e2003-08-23 22:54:34 +0000195 // If there is only the default destination, don't bother with the code below.
196 if (SI->getNumOperands() == 2) {
Chris Lattnera2960002003-11-21 16:52:05 +0000197 new BranchInst(SI->getDefaultDest(), CurBlock);
Chris Lattnerb6865952004-03-14 04:14:31 +0000198 CurBlock->getInstList().erase(SI);
Chris Lattnerf1b1c5e2003-08-23 22:54:34 +0000199 return;
200 }
201
Chris Lattnered922162003-10-07 18:46:23 +0000202 // Create a new, empty default block so that the new hierarchy of
203 // if-then statements go to this and the PHI nodes are happy.
204 BasicBlock* NewDefault = new BasicBlock("NewDefault");
205 F->getBasicBlockList().insert(Default, NewDefault);
Chris Lattner1b094a02003-04-23 16:23:59 +0000206
Chris Lattnera2960002003-11-21 16:52:05 +0000207 new BranchInst(Default, NewDefault);
Chris Lattner1b094a02003-04-23 16:23:59 +0000208
Chris Lattnered922162003-10-07 18:46:23 +0000209 // If there is an entry in any PHI nodes for the default edge, make sure
210 // to update them as well.
Reid Spencer66149462004-09-15 17:06:42 +0000211 for (BasicBlock::iterator I = Default->begin(); isa<PHINode>(I); ++I) {
212 PHINode *PN = cast<PHINode>(I);
Chris Lattnered922162003-10-07 18:46:23 +0000213 int BlockIdx = PN->getBasicBlockIndex(OrigBlock);
214 assert(BlockIdx != -1 && "Switch didn't go to this successor??");
215 PN->setIncomingBlock((unsigned)BlockIdx, NewDefault);
Chris Lattner1b094a02003-04-23 16:23:59 +0000216 }
217
Chris Lattnered922162003-10-07 18:46:23 +0000218 std::vector<Case> Cases;
219
220 // Expand comparisons for all of the non-default cases...
221 for (unsigned i = 1; i < SI->getNumSuccessors(); ++i)
222 Cases.push_back(Case(SI->getSuccessorValue(i), SI->getSuccessor(i)));
223
224 std::sort(Cases.begin(), Cases.end(), CaseCmp());
225 DEBUG(std::cerr << "Cases: " << Cases << "\n");
226 BasicBlock* SwitchBlock = switchConvert(Cases.begin(), Cases.end(), Val,
227 OrigBlock, NewDefault);
228
229 // Branch to our shiny new if-then stuff...
Chris Lattnera2960002003-11-21 16:52:05 +0000230 new BranchInst(SwitchBlock, OrigBlock);
Chris Lattnered922162003-10-07 18:46:23 +0000231
Chris Lattner1b094a02003-04-23 16:23:59 +0000232 // We are now done with the switch instruction, delete it.
Chris Lattnerb6865952004-03-14 04:14:31 +0000233 CurBlock->getInstList().erase(SI);
Chris Lattner1b094a02003-04-23 16:23:59 +0000234}