114383485ac546e369b11797b42bc20831b6db57bChris Lattner//===- LowerSwitch.cpp - Eliminate Switch instructions --------------------===// 2fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 3b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// The LLVM Compiler Infrastructure 4b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 54ee451de366474b9c228b4e5fa573795a715216dChris Lattner// This file is distributed under the University of Illinois Open Source 64ee451de366474b9c228b4e5fa573795a715216dChris Lattner// License. See LICENSE.TXT for details. 7fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 8b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell//===----------------------------------------------------------------------===// 914383485ac546e369b11797b42bc20831b6db57bChris Lattner// 10c86b67742a3298c0a5a715b57a64f11107b8a3f2Gordon Henriksen// The LowerSwitch transformation rewrites switch instructions with a sequence 11c86b67742a3298c0a5a715b57a64f11107b8a3f2Gordon Henriksen// of branches, which allows targets to get away with not implementing the 12c86b67742a3298c0a5a715b57a64f11107b8a3f2Gordon Henriksen// switch instruction until it is convenient. 1314383485ac546e369b11797b42bc20831b6db57bChris Lattner// 1414383485ac546e369b11797b42bc20831b6db57bChris Lattner//===----------------------------------------------------------------------===// 1514383485ac546e369b11797b42bc20831b6db57bChris Lattner 1614383485ac546e369b11797b42bc20831b6db57bChris Lattner#include "llvm/Transforms/Scalar.h" 17cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines#include "llvm/Transforms/Utils/BasicBlockUtils.h" 18d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/STLExtras.h" 190b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Constants.h" 200b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Function.h" 210b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Instructions.h" 220b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/LLVMContext.h" 23cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines#include "llvm/IR/CFG.h" 2414383485ac546e369b11797b42bc20831b6db57bChris Lattner#include "llvm/Pass.h" 25a4f0b3a084d120cfc5b5bb06f64b222f5cb72740Chris Lattner#include "llvm/Support/Compiler.h" 26f5a86f45e75ec744c203270ffa03659eb0a220c1Nick Lewycky#include "llvm/Support/Debug.h" 27944fac71e082cc2664cc71b4d3f6c72bab7143fbChris Lattner#include "llvm/Support/raw_ostream.h" 28d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Transforms/Utils/UnifyFunctionExitNodes.h" 2920aa474f8fbebde588edc101b90e834df28ce4ceAlkis Evlogimenos#include <algorithm> 30d7456026629fc1760a45e6e955e9834246493147Chris Lattnerusing namespace llvm; 31d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 32dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#define DEBUG_TYPE "lower-switch" 33dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 3414383485ac546e369b11797b42bc20831b6db57bChris Lattnernamespace { 3514383485ac546e369b11797b42bc20831b6db57bChris Lattner /// LowerSwitch Pass - Replace all SwitchInst instructions with chained branch 36473fc96889ff8d0862a8fea16c4a5b9252e2d44dChris Lattner /// instructions. 376726b6d75a8b679068a58cb954ba97cf9d1690baNick Lewycky class LowerSwitch : public FunctionPass { 38ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner public: 39ecd94c804a563f2a86572dcf1d2e81f397e19daaNick Lewycky static char ID; // Pass identification, replacement for typeid 40081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson LowerSwitch() : FunctionPass(ID) { 41081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeLowerSwitchPass(*PassRegistry::getPassRegistry()); 42081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson } 43794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 4436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool runOnFunction(Function &F) override; 4536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 4636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void getAnalysisUsage(AnalysisUsage &AU) const override { 47bed2946a96ecb15b0b636fa74cb26ce61b1c648eAnton Korobeynikov // This is a cluster of orthogonal Transforms 488d89e7bdbcea38fe2ab3c85d91359712cd45714bChris Lattner AU.addPreserved<UnifyFunctionExitNodes>(); 4960493c3f4ff9b20f43a3abc605bc64642de75b59Dan Gohman AU.addPreserved("mem2reg"); 50ed96fe8c79b36a38bd9280438656ee539276fb41Chris Lattner AU.addPreservedID(LowerInvokePassID); 518d89e7bdbcea38fe2ab3c85d91359712cd45714bChris Lattner } 52e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov 53e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov struct CaseRange { 54e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov Constant* Low; 55e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov Constant* High; 56e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov BasicBlock* BB; 57e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov 58dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines CaseRange(Constant *low = nullptr, Constant *high = nullptr, 59dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines BasicBlock *bb = nullptr) : 60c4558fde76bdb17bff28375fe20ee02e027095b8Jeff Cohen Low(low), High(high), BB(bb) { } 61e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov }; 62e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov 63cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines typedef std::vector<CaseRange> CaseVector; 64e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov typedef std::vector<CaseRange>::iterator CaseItr; 65ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner private: 6614383485ac546e369b11797b42bc20831b6db57bChris Lattner void processSwitchInst(SwitchInst *SI); 67ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner 68cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines BasicBlock *switchConvert(CaseItr Begin, CaseItr End, 69cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines ConstantInt *LowerBound, ConstantInt *UpperBound, 70cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines Value *Val, BasicBlock *OrigBlock, 71cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines BasicBlock *Default); 72cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines BasicBlock *newLeafBlock(CaseRange &Leaf, Value *Val, BasicBlock *OrigBlock, 73cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines BasicBlock *Default); 74cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines unsigned Clusterify(CaseVector &Cases, SwitchInst *SI); 75ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner }; 76db3a9e64f856e3a233a427da1f3969fd3a65a438Bob Wilson 77db3a9e64f856e3a233a427da1f3969fd3a65a438Bob Wilson /// The comparison function for sorting the switch case values in the vector. 78db3a9e64f856e3a233a427da1f3969fd3a65a438Bob Wilson /// WARNING: Case ranges should be disjoint! 79db3a9e64f856e3a233a427da1f3969fd3a65a438Bob Wilson struct CaseCmp { 80db3a9e64f856e3a233a427da1f3969fd3a65a438Bob Wilson bool operator () (const LowerSwitch::CaseRange& C1, 81db3a9e64f856e3a233a427da1f3969fd3a65a438Bob Wilson const LowerSwitch::CaseRange& C2) { 82db3a9e64f856e3a233a427da1f3969fd3a65a438Bob Wilson 83db3a9e64f856e3a233a427da1f3969fd3a65a438Bob Wilson const ConstantInt* CI1 = cast<const ConstantInt>(C1.Low); 84db3a9e64f856e3a233a427da1f3969fd3a65a438Bob Wilson const ConstantInt* CI2 = cast<const ConstantInt>(C2.High); 85db3a9e64f856e3a233a427da1f3969fd3a65a438Bob Wilson return CI1->getValue().slt(CI2->getValue()); 86db3a9e64f856e3a233a427da1f3969fd3a65a438Bob Wilson } 87db3a9e64f856e3a233a427da1f3969fd3a65a438Bob Wilson }; 8814383485ac546e369b11797b42bc20831b6db57bChris Lattner} 8914383485ac546e369b11797b42bc20831b6db57bChris Lattner 90844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanchar LowerSwitch::ID = 0; 9102dd53e1c5b941ca5f60fca1b95ebcaf9ccd1dfcOwen AndersonINITIALIZE_PASS(LowerSwitch, "lowerswitch", 92ce665bd2e2b581ab0858d1afe359192bac96b868Owen Anderson "Lower SwitchInst's to branches", false, false) 93844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 947a2bdde0a0eebcd2125055e0eacaca040f0b766cChris Lattner// Publicly exposed interface to pass... 9590c579de5a383cee278acc3f7e7b9d0a656e6a35Owen Andersonchar &llvm::LowerSwitchID = LowerSwitch::ID; 9614383485ac546e369b11797b42bc20831b6db57bChris Lattner// createLowerSwitchPass - Interface to this file... 97d7456026629fc1760a45e6e955e9834246493147Chris LattnerFunctionPass *llvm::createLowerSwitchPass() { 9814383485ac546e369b11797b42bc20831b6db57bChris Lattner return new LowerSwitch(); 9914383485ac546e369b11797b42bc20831b6db57bChris Lattner} 10014383485ac546e369b11797b42bc20831b6db57bChris Lattner 10114383485ac546e369b11797b42bc20831b6db57bChris Lattnerbool LowerSwitch::runOnFunction(Function &F) { 10214383485ac546e369b11797b42bc20831b6db57bChris Lattner bool Changed = false; 10314383485ac546e369b11797b42bc20831b6db57bChris Lattner 10414383485ac546e369b11797b42bc20831b6db57bChris Lattner for (Function::iterator I = F.begin(), E = F.end(); I != E; ) { 10514383485ac546e369b11797b42bc20831b6db57bChris Lattner BasicBlock *Cur = I++; // Advance over block so we don't traverse new blocks 10614383485ac546e369b11797b42bc20831b6db57bChris Lattner 10714383485ac546e369b11797b42bc20831b6db57bChris Lattner if (SwitchInst *SI = dyn_cast<SwitchInst>(Cur->getTerminator())) { 10814383485ac546e369b11797b42bc20831b6db57bChris Lattner Changed = true; 10914383485ac546e369b11797b42bc20831b6db57bChris Lattner processSwitchInst(SI); 11014383485ac546e369b11797b42bc20831b6db57bChris Lattner } 11114383485ac546e369b11797b42bc20831b6db57bChris Lattner } 11214383485ac546e369b11797b42bc20831b6db57bChris Lattner 11314383485ac546e369b11797b42bc20831b6db57bChris Lattner return Changed; 11414383485ac546e369b11797b42bc20831b6db57bChris Lattner} 11514383485ac546e369b11797b42bc20831b6db57bChris Lattner 116ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner// operator<< - Used for debugging purposes. 117ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner// 1181cd1d98232c3c3a0bd3810c3bf6c2572ea02f208Daniel Dunbarstatic raw_ostream& operator<<(raw_ostream &O, 119100c267249d1d03c4f96eede9877a4f9f54f2247Chandler Carruth const LowerSwitch::CaseVector &C) 120100c267249d1d03c4f96eede9877a4f9f54f2247Chandler Carruth LLVM_ATTRIBUTE_USED; 12166ad89cebaecd7d88d9e723170c2b55fadd76b71Mike Stumpstatic raw_ostream& operator<<(raw_ostream &O, 1221cd1d98232c3c3a0bd3810c3bf6c2572ea02f208Daniel Dunbar const LowerSwitch::CaseVector &C) { 123ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner O << "["; 124ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner 125e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov for (LowerSwitch::CaseVector::const_iterator B = C.begin(), 126d7456026629fc1760a45e6e955e9834246493147Chris Lattner E = C.end(); B != E; ) { 127e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov O << *B->Low << " -" << *B->High; 128ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner if (++B != E) O << ", "; 129ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner } 130ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner 131ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner return O << "]"; 132ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner} 133e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov 134ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner// switchConvert - Convert the switch statement into a binary lookup of 135ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner// the case values. The function recursively builds this tree. 136cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines// LowerBound and UpperBound are used to keep track of the bounds for Val 137cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines// that have already been checked by a block emitted by one of the previous 138cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines// calls to switchConvert in the call stack. 139cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen HinesBasicBlock *LowerSwitch::switchConvert(CaseItr Begin, CaseItr End, 140cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines ConstantInt *LowerBound, 141cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines ConstantInt *UpperBound, Value *Val, 142cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines BasicBlock *OrigBlock, 143cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines BasicBlock *Default) { 144ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner unsigned Size = End - Begin; 145ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner 146cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (Size == 1) { 147cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // Check if the Case Range is perfectly squeezed in between 148cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // already checked Upper and Lower bounds. If it is then we can avoid 149cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // emitting the code that checks if the value actually falls in the range 150cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // because the bounds already tell us so. 151cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (Begin->Low == LowerBound && Begin->High == UpperBound) { 152cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines return Begin->BB; 153cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines } 154ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner return newLeafBlock(*Begin, Val, OrigBlock, Default); 155cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines } 156ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner 157ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner unsigned Mid = Size / 2; 158e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov std::vector<CaseRange> LHS(Begin, Begin + Mid); 1590f4c988a27d5723d723b7c8e7c4ca9fc6777f20dDavid Greene DEBUG(dbgs() << "LHS: " << LHS << "\n"); 160e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov std::vector<CaseRange> RHS(Begin + Mid, End); 1610f4c988a27d5723d723b7c8e7c4ca9fc6777f20dDavid Greene DEBUG(dbgs() << "RHS: " << RHS << "\n"); 162ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner 163cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines CaseRange &Pivot = *(Begin + Mid); 164cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines DEBUG(dbgs() << "Pivot ==> " 165cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines << cast<ConstantInt>(Pivot.Low)->getValue() 166cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines << " -" << cast<ConstantInt>(Pivot.High)->getValue() << "\n"); 167cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 168cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // NewLowerBound here should never be the integer minimal value. 169cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // This is because it is computed from a case range that is never 170cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // the smallest, so there is always a case range that has at least 171cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // a smaller value. 172cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines ConstantInt *NewLowerBound = cast<ConstantInt>(Pivot.Low); 173cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines ConstantInt *NewUpperBound; 174cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 175cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // If we don't have a Default block then it means that we can never 176cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // have a value outside of a case range, so set the UpperBound to the highest 177cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // value in the LHS part of the case ranges. 178cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (Default != nullptr) { 179cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // Because NewLowerBound is never the smallest representable integer 180cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // it is safe here to subtract one. 181cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines NewUpperBound = ConstantInt::get(NewLowerBound->getContext(), 182cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines NewLowerBound->getValue() - 1); 183cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines } else { 184cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines CaseItr LastLHS = LHS.begin() + LHS.size() - 1; 185cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines NewUpperBound = cast<ConstantInt>(LastLHS->High); 186cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines } 187ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner 188cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines DEBUG(dbgs() << "LHS Bounds ==> "; 189cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (LowerBound) { 190cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines dbgs() << cast<ConstantInt>(LowerBound)->getSExtValue(); 191cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines } else { 192cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines dbgs() << "NONE"; 193cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines } 194cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines dbgs() << " - " << NewUpperBound->getSExtValue() << "\n"; 195cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines dbgs() << "RHS Bounds ==> "; 196cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines dbgs() << NewLowerBound->getSExtValue() << " - "; 197cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (UpperBound) { 198cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines dbgs() << cast<ConstantInt>(UpperBound)->getSExtValue() << "\n"; 199cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines } else { 200cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines dbgs() << "NONE\n"; 201cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines }); 202cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 203cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines BasicBlock *LBranch = switchConvert(LHS.begin(), LHS.end(), LowerBound, 204cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines NewUpperBound, Val, OrigBlock, Default); 205cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines BasicBlock *RBranch = switchConvert(RHS.begin(), RHS.end(), NewLowerBound, 206cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines UpperBound, Val, OrigBlock, Default); 207ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner 208ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner // Create a new node that checks if the value is < pivot. Go to the 209ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner // left branch if it is and right branch if not. 210ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner Function* F = OrigBlock->getParent(); 2111d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson BasicBlock* NewNode = BasicBlock::Create(Val->getContext(), "NodeBlock"); 212261cdfbe5e6e11d56ca1c49a75f26fece3b139c8Chris Lattner Function::iterator FI = OrigBlock; 213261cdfbe5e6e11d56ca1c49a75f26fece3b139c8Chris Lattner F->getBasicBlockList().insert(++FI, NewNode); 214ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner 215db3a9e64f856e3a233a427da1f3969fd3a65a438Bob Wilson ICmpInst* Comp = new ICmpInst(ICmpInst::ICMP_SLT, 216333c40096561218bc3597cf153c0a3895274414cOwen Anderson Val, Pivot.Low, "Pivot"); 217ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner NewNode->getInstList().push_back(Comp); 218051a950000e21935165db56695e35bade668193bGabor Greif BranchInst::Create(LBranch, RBranch, Comp, NewNode); 219ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner return NewNode; 220ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner} 221ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner 222ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner// newLeafBlock - Create a new leaf block for the binary lookup tree. It 223ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner// checks if the switch's value == the case's value. If not, then it 224ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner// jumps to the default branch. At this point in the tree, the value 225ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner// can't be another valid case value, so the jump to the "default" branch 226ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner// is warranted. 227ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner// 228e2ff29c17c1a7c121e22789cf1654d923467b472Anton KorobeynikovBasicBlock* LowerSwitch::newLeafBlock(CaseRange& Leaf, Value* Val, 229ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner BasicBlock* OrigBlock, 230ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner BasicBlock* Default) 231ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner{ 232ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner Function* F = OrigBlock->getParent(); 2331d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson BasicBlock* NewLeaf = BasicBlock::Create(Val->getContext(), "LeafBlock"); 234261cdfbe5e6e11d56ca1c49a75f26fece3b139c8Chris Lattner Function::iterator FI = OrigBlock; 235261cdfbe5e6e11d56ca1c49a75f26fece3b139c8Chris Lattner F->getBasicBlockList().insert(++FI, NewLeaf); 236ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner 237e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov // Emit comparison 238dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines ICmpInst* Comp = nullptr; 239e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov if (Leaf.Low == Leaf.High) { 240e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov // Make the seteq instruction... 241333c40096561218bc3597cf153c0a3895274414cOwen Anderson Comp = new ICmpInst(*NewLeaf, ICmpInst::ICMP_EQ, Val, 242333c40096561218bc3597cf153c0a3895274414cOwen Anderson Leaf.Low, "SwitchLeaf"); 243e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov } else { 244e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov // Make range comparison 245e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov if (cast<ConstantInt>(Leaf.Low)->isMinValue(true /*isSigned*/)) { 246e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov // Val >= Min && Val <= Hi --> Val <= Hi 247333c40096561218bc3597cf153c0a3895274414cOwen Anderson Comp = new ICmpInst(*NewLeaf, ICmpInst::ICMP_SLE, Val, Leaf.High, 248333c40096561218bc3597cf153c0a3895274414cOwen Anderson "SwitchLeaf"); 249e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov } else if (cast<ConstantInt>(Leaf.Low)->isZero()) { 250e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov // Val >= 0 && Val <= Hi --> Val <=u Hi 251333c40096561218bc3597cf153c0a3895274414cOwen Anderson Comp = new ICmpInst(*NewLeaf, ICmpInst::ICMP_ULE, Val, Leaf.High, 252333c40096561218bc3597cf153c0a3895274414cOwen Anderson "SwitchLeaf"); 253e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov } else { 254e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov // Emit V-Lo <=u Hi-Lo 255baf3c404409d5e47b13984a7f95bfbd6d1f2e79eOwen Anderson Constant* NegLo = ConstantExpr::getNeg(Leaf.Low); 2567cbd8a3e92221437048b484d5ef9c0a22d0f8c58Gabor Greif Instruction* Add = BinaryOperator::CreateAdd(Val, NegLo, 257e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov Val->getName()+".off", 258e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov NewLeaf); 259baf3c404409d5e47b13984a7f95bfbd6d1f2e79eOwen Anderson Constant *UpperBound = ConstantExpr::getAdd(NegLo, Leaf.High); 260333c40096561218bc3597cf153c0a3895274414cOwen Anderson Comp = new ICmpInst(*NewLeaf, ICmpInst::ICMP_ULE, Add, UpperBound, 261333c40096561218bc3597cf153c0a3895274414cOwen Anderson "SwitchLeaf"); 262e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov } 263e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov } 264ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner 265ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner // Make the conditional branch... 266e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov BasicBlock* Succ = Leaf.BB; 267051a950000e21935165db56695e35bade668193bGabor Greif BranchInst::Create(Succ, Default, Comp, NewLeaf); 268ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner 269ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner // If there were any PHI nodes in this successor, rewrite one entry 270ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner // from OrigBlock to come from NewLeaf. 2712da5c3dda6f5b9c4ec6d55008d33327764364bd4Reid Spencer for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) { 2722da5c3dda6f5b9c4ec6d55008d33327764364bd4Reid Spencer PHINode* PN = cast<PHINode>(I); 273e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov // Remove all but one incoming entries from the cluster 274e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov uint64_t Range = cast<ConstantInt>(Leaf.High)->getSExtValue() - 275e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov cast<ConstantInt>(Leaf.Low)->getSExtValue(); 276e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov for (uint64_t j = 0; j < Range; ++j) { 277e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov PN->removeIncomingValue(OrigBlock); 278e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov } 279e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov 280ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner int BlockIdx = PN->getBasicBlockIndex(OrigBlock); 281ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner assert(BlockIdx != -1 && "Switch didn't go to this successor??"); 282ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner PN->setIncomingBlock((unsigned)BlockIdx, NewLeaf); 283ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner } 284ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner 285ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner return NewLeaf; 286ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner} 287ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner 288e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov// Clusterify - Transform simple list of Cases into list of CaseRange's 289e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikovunsigned LowerSwitch::Clusterify(CaseVector& Cases, SwitchInst *SI) { 290db3a9e64f856e3a233a427da1f3969fd3a65a438Bob Wilson unsigned numCmps = 0; 291e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov 292e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov // Start with "simple" cases 293db3a9e64f856e3a233a427da1f3969fd3a65a438Bob Wilson for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end(); i != e; ++i) 294db3a9e64f856e3a233a427da1f3969fd3a65a438Bob Wilson Cases.push_back(CaseRange(i.getCaseValue(), i.getCaseValue(), 295db3a9e64f856e3a233a427da1f3969fd3a65a438Bob Wilson i.getCaseSuccessor())); 296e98a88957ea0c16ec49ff33bff564604255c024fStepan Dyatkovskiy 297db3a9e64f856e3a233a427da1f3969fd3a65a438Bob Wilson std::sort(Cases.begin(), Cases.end(), CaseCmp()); 298db3a9e64f856e3a233a427da1f3969fd3a65a438Bob Wilson 299db3a9e64f856e3a233a427da1f3969fd3a65a438Bob Wilson // Merge case into clusters 300db3a9e64f856e3a233a427da1f3969fd3a65a438Bob Wilson if (Cases.size()>=2) 30136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (CaseItr I = Cases.begin(), J = std::next(Cases.begin()); 30236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines J != Cases.end();) { 303db3a9e64f856e3a233a427da1f3969fd3a65a438Bob Wilson int64_t nextValue = cast<ConstantInt>(J->Low)->getSExtValue(); 304db3a9e64f856e3a233a427da1f3969fd3a65a438Bob Wilson int64_t currentValue = cast<ConstantInt>(I->High)->getSExtValue(); 305db3a9e64f856e3a233a427da1f3969fd3a65a438Bob Wilson BasicBlock* nextBB = J->BB; 306db3a9e64f856e3a233a427da1f3969fd3a65a438Bob Wilson BasicBlock* currentBB = I->BB; 307db3a9e64f856e3a233a427da1f3969fd3a65a438Bob Wilson 308db3a9e64f856e3a233a427da1f3969fd3a65a438Bob Wilson // If the two neighboring cases go to the same destination, merge them 309db3a9e64f856e3a233a427da1f3969fd3a65a438Bob Wilson // into a single case. 310db3a9e64f856e3a233a427da1f3969fd3a65a438Bob Wilson if ((nextValue-currentValue==1) && (currentBB == nextBB)) { 311db3a9e64f856e3a233a427da1f3969fd3a65a438Bob Wilson I->High = J->High; 312db3a9e64f856e3a233a427da1f3969fd3a65a438Bob Wilson J = Cases.erase(J); 313db3a9e64f856e3a233a427da1f3969fd3a65a438Bob Wilson } else { 314db3a9e64f856e3a233a427da1f3969fd3a65a438Bob Wilson I = J++; 315db3a9e64f856e3a233a427da1f3969fd3a65a438Bob Wilson } 316db3a9e64f856e3a233a427da1f3969fd3a65a438Bob Wilson } 317db3a9e64f856e3a233a427da1f3969fd3a65a438Bob Wilson 318db3a9e64f856e3a233a427da1f3969fd3a65a438Bob Wilson for (CaseItr I=Cases.begin(), E=Cases.end(); I!=E; ++I, ++numCmps) { 319db3a9e64f856e3a233a427da1f3969fd3a65a438Bob Wilson if (I->Low != I->High) 320e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov // A range counts double, since it requires two compares. 321e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov ++numCmps; 322e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov } 323e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov 324db3a9e64f856e3a233a427da1f3969fd3a65a438Bob Wilson return numCmps; 325e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov} 326e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov 32714383485ac546e369b11797b42bc20831b6db57bChris Lattner// processSwitchInst - Replace the specified switch instruction with a sequence 328ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner// of chained if-then insts in a balanced binary search. 32914383485ac546e369b11797b42bc20831b6db57bChris Lattner// 33014383485ac546e369b11797b42bc20831b6db57bChris Lattnervoid LowerSwitch::processSwitchInst(SwitchInst *SI) { 33114383485ac546e369b11797b42bc20831b6db57bChris Lattner BasicBlock *CurBlock = SI->getParent(); 33214383485ac546e369b11797b42bc20831b6db57bChris Lattner BasicBlock *OrigBlock = CurBlock; 33314383485ac546e369b11797b42bc20831b6db57bChris Lattner Function *F = CurBlock->getParent(); 334bb5a7442e362776621112dc9453e546a55878e79Eli Friedman Value *Val = SI->getCondition(); // The value we are switching on... 335ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner BasicBlock* Default = SI->getDefaultDest(); 33614383485ac546e369b11797b42bc20831b6db57bChris Lattner 33744bb541c011bcae84759ed194ec7cb4139775fcbChris Lattner // If there is only the default destination, don't bother with the code below. 33824473120a253a05f3601cd3373403b47e6d03d41Stepan Dyatkovskiy if (!SI->getNumCases()) { 339051a950000e21935165db56695e35bade668193bGabor Greif BranchInst::Create(SI->getDefaultDest(), CurBlock); 340bf9eaddfb0642e49bc2f3835765a9782ff48c76eChris Lattner CurBlock->getInstList().erase(SI); 34144bb541c011bcae84759ed194ec7cb4139775fcbChris Lattner return; 34244bb541c011bcae84759ed194ec7cb4139775fcbChris Lattner } 34344bb541c011bcae84759ed194ec7cb4139775fcbChris Lattner 344cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines const bool DefaultIsUnreachable = 345cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines Default->size() == 1 && isa<UnreachableInst>(Default->getTerminator()); 346ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner // Create a new, empty default block so that the new hierarchy of 347ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner // if-then statements go to this and the PHI nodes are happy. 348cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // if the default block is set as an unreachable we avoid creating one 349cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // because will never be a valid target. 350cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines BasicBlock *NewDefault = nullptr; 351cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (!DefaultIsUnreachable) { 352cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines NewDefault = BasicBlock::Create(SI->getContext(), "NewDefault"); 353cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines F->getBasicBlockList().insert(Default, NewDefault); 354cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 355cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines BranchInst::Create(Default, NewDefault); 356cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines } 357ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner // If there is an entry in any PHI nodes for the default edge, make sure 358ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner // to update them as well. 3592da5c3dda6f5b9c4ec6d55008d33327764364bd4Reid Spencer for (BasicBlock::iterator I = Default->begin(); isa<PHINode>(I); ++I) { 3602da5c3dda6f5b9c4ec6d55008d33327764364bd4Reid Spencer PHINode *PN = cast<PHINode>(I); 361ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner int BlockIdx = PN->getBasicBlockIndex(OrigBlock); 362ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner assert(BlockIdx != -1 && "Switch didn't go to this successor??"); 363ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner PN->setIncomingBlock((unsigned)BlockIdx, NewDefault); 36414383485ac546e369b11797b42bc20831b6db57bChris Lattner } 36514383485ac546e369b11797b42bc20831b6db57bChris Lattner 366e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov // Prepare cases vector. 367e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov CaseVector Cases; 368e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov unsigned numCmps = Clusterify(Cases, SI); 369ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner 3700f4c988a27d5723d723b7c8e7c4ca9fc6777f20dDavid Greene DEBUG(dbgs() << "Clusterify finished. Total clusters: " << Cases.size() 3716c1980b3357207c4d756255bc5e32323eac278dcDan Gohman << ". Total compares: " << numCmps << "\n"); 3720f4c988a27d5723d723b7c8e7c4ca9fc6777f20dDavid Greene DEBUG(dbgs() << "Cases: " << Cases << "\n"); 37302efa786d40fabae6dbbb3de5ab057359701e337Mike Stump (void)numCmps; 374e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov 375cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines ConstantInt *UpperBound = nullptr; 376cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines ConstantInt *LowerBound = nullptr; 377cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 378cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // Optimize the condition where Default is an unreachable block. In this case 379cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // we can make the bounds tightly fitted around the case value ranges, 380cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // because we know that the value passed to the switch should always be 381cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // exactly one of the case values. 382cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (DefaultIsUnreachable) { 383cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines CaseItr LastCase = Cases.begin() + Cases.size() - 1; 384cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines UpperBound = cast<ConstantInt>(LastCase->High); 385cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines LowerBound = cast<ConstantInt>(Cases.begin()->Low); 386cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines } 387cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines BasicBlock *SwitchBlock = 388cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines switchConvert(Cases.begin(), Cases.end(), LowerBound, UpperBound, Val, 389cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines OrigBlock, NewDefault); 390ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner 391ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner // Branch to our shiny new if-then stuff... 392051a950000e21935165db56695e35bade668193bGabor Greif BranchInst::Create(SwitchBlock, OrigBlock); 393ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner 39414383485ac546e369b11797b42bc20831b6db57bChris Lattner // We are now done with the switch instruction, delete it. 395bf9eaddfb0642e49bc2f3835765a9782ff48c76eChris Lattner CurBlock->getInstList().erase(SI); 396cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 397cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines pred_iterator PI = pred_begin(Default), E = pred_end(Default); 398cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // If the Default block has no more predecessors just remove it 399cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (PI == E) { 400cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines DeleteDeadBlock(Default); 401cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines } 40214383485ac546e369b11797b42bc20831b6db57bChris Lattner} 403