Chris Lattner | 18bdbc3 | 2004-03-30 18:41:10 +0000 | [diff] [blame] | 1 | //===- LowerSelect.cpp - Transform select insts to branches ---------------===// |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 2 | // |
Chris Lattner | 18bdbc3 | 2004-03-30 18:41:10 +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 | // |
Chris Lattner | 18bdbc3 | 2004-03-30 18:41:10 +0000 | [diff] [blame] | 8 | //===----------------------------------------------------------------------===// |
| 9 | // |
| 10 | // This pass lowers select instructions into conditional branches for targets |
| 11 | // that do not have conditional moves or that have not implemented the select |
| 12 | // instruction yet. |
| 13 | // |
| 14 | // Note that this pass could be improved. In particular it turns every select |
| 15 | // instruction into a new conditional branch, even though some common cases have |
| 16 | // select instructions on the same predicate next to each other. It would be |
| 17 | // better to use the same branch for the whole group of selects. |
| 18 | // |
| 19 | //===----------------------------------------------------------------------===// |
| 20 | |
| 21 | #include "llvm/Transforms/Scalar.h" |
Chris Lattner | 8d89e7b | 2006-05-09 04:13:41 +0000 | [diff] [blame] | 22 | #include "llvm/Transforms/Utils/UnifyFunctionExitNodes.h" |
Chris Lattner | 18bdbc3 | 2004-03-30 18:41:10 +0000 | [diff] [blame] | 23 | #include "llvm/Function.h" |
| 24 | #include "llvm/Instructions.h" |
| 25 | #include "llvm/Pass.h" |
| 26 | #include "llvm/Type.h" |
Reid Spencer | 9133fe2 | 2007-02-05 23:32:05 +0000 | [diff] [blame] | 27 | #include "llvm/Support/Compiler.h" |
Chris Lattner | 18bdbc3 | 2004-03-30 18:41:10 +0000 | [diff] [blame] | 28 | using namespace llvm; |
| 29 | |
| 30 | namespace { |
Chris Lattner | 18bdbc3 | 2004-03-30 18:41:10 +0000 | [diff] [blame] | 31 | /// LowerSelect - Turn select instructions into conditional branches. |
| 32 | /// |
Reid Spencer | 9133fe2 | 2007-02-05 23:32:05 +0000 | [diff] [blame] | 33 | class VISIBILITY_HIDDEN LowerSelect : public FunctionPass { |
Chris Lattner | 18bdbc3 | 2004-03-30 18:41:10 +0000 | [diff] [blame] | 34 | bool OnlyFP; // Only lower FP select instructions? |
| 35 | public: |
Nick Lewycky | ecd94c8 | 2007-05-06 13:37:16 +0000 | [diff] [blame] | 36 | static char ID; // Pass identification, replacement for typeid |
Dan Gohman | c2bbfc1 | 2007-08-01 15:32:29 +0000 | [diff] [blame] | 37 | explicit LowerSelect(bool onlyfp = false) : FunctionPass((intptr_t)&ID), |
Devang Patel | 794fd75 | 2007-05-01 21:15:47 +0000 | [diff] [blame] | 38 | OnlyFP(onlyfp) {} |
Chris Lattner | 18bdbc3 | 2004-03-30 18:41:10 +0000 | [diff] [blame] | 39 | |
| 40 | virtual void getAnalysisUsage(AnalysisUsage &AU) const { |
Chris Lattner | 8d89e7b | 2006-05-09 04:13:41 +0000 | [diff] [blame] | 41 | // This certainly destroys the CFG. |
Anton Korobeynikov | bed2946 | 2007-04-16 18:10:23 +0000 | [diff] [blame] | 42 | // This is a cluster of orthogonal Transforms: |
Chris Lattner | 8d89e7b | 2006-05-09 04:13:41 +0000 | [diff] [blame] | 43 | AU.addPreserved<UnifyFunctionExitNodes>(); |
| 44 | AU.addPreservedID(PromoteMemoryToRegisterID); |
| 45 | AU.addPreservedID(LowerSwitchID); |
Chris Lattner | ed96fe8 | 2006-05-17 21:05:27 +0000 | [diff] [blame] | 46 | AU.addPreservedID(LowerInvokePassID); |
| 47 | AU.addPreservedID(LowerAllocationsID); |
Chris Lattner | 18bdbc3 | 2004-03-30 18:41:10 +0000 | [diff] [blame] | 48 | } |
| 49 | |
| 50 | bool runOnFunction(Function &F); |
| 51 | }; |
| 52 | |
Devang Patel | 1997473 | 2007-05-03 01:11:54 +0000 | [diff] [blame] | 53 | char LowerSelect::ID = 0; |
Chris Lattner | 7f8897f | 2006-08-27 22:42:52 +0000 | [diff] [blame] | 54 | RegisterPass<LowerSelect> |
Chris Lattner | 18bdbc3 | 2004-03-30 18:41:10 +0000 | [diff] [blame] | 55 | X("lowerselect", "Lower select instructions to branches"); |
| 56 | } |
| 57 | |
Chris Lattner | b3674e4 | 2006-05-02 04:24:36 +0000 | [diff] [blame] | 58 | // Publically exposed interface to pass... |
| 59 | const PassInfo *llvm::LowerSelectID = X.getPassInfo(); |
Chris Lattner | 18bdbc3 | 2004-03-30 18:41:10 +0000 | [diff] [blame] | 60 | //===----------------------------------------------------------------------===// |
| 61 | // This pass converts SelectInst instructions into conditional branch and PHI |
| 62 | // instructions. If the OnlyFP flag is set to true, then only floating point |
| 63 | // select instructions are lowered. |
| 64 | // |
| 65 | FunctionPass *llvm::createLowerSelectPass(bool OnlyFP) { |
| 66 | return new LowerSelect(OnlyFP); |
| 67 | } |
| 68 | |
| 69 | |
| 70 | bool LowerSelect::runOnFunction(Function &F) { |
| 71 | bool Changed = false; |
| 72 | for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) |
| 73 | for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) { |
| 74 | if (SelectInst *SI = dyn_cast<SelectInst>(I)) |
| 75 | if (!OnlyFP || SI->getType()->isFloatingPoint()) { |
| 76 | // Split this basic block in half right before the select instruction. |
| 77 | BasicBlock *NewCont = |
| 78 | BB->splitBasicBlock(I, BB->getName()+".selectcont"); |
| 79 | |
| 80 | // Make the true block, and make it branch to the continue block. |
| 81 | BasicBlock *NewTrue = new BasicBlock(BB->getName()+".selecttrue", |
| 82 | BB->getParent(), NewCont); |
| 83 | new BranchInst(NewCont, NewTrue); |
| 84 | |
| 85 | // Make the unconditional branch in the incoming block be a |
| 86 | // conditional branch on the select predicate. |
| 87 | BB->getInstList().erase(BB->getTerminator()); |
| 88 | new BranchInst(NewTrue, NewCont, SI->getCondition(), BB); |
| 89 | |
| 90 | // Create a new PHI node in the cont block with the entries we need. |
Chris Lattner | 86cc423 | 2007-02-11 01:37:51 +0000 | [diff] [blame] | 91 | PHINode *PN = new PHINode(SI->getType(), "", NewCont->begin()); |
| 92 | PN->takeName(SI); |
Chris Lattner | 18bdbc3 | 2004-03-30 18:41:10 +0000 | [diff] [blame] | 93 | PN->addIncoming(SI->getTrueValue(), NewTrue); |
| 94 | PN->addIncoming(SI->getFalseValue(), BB); |
| 95 | |
| 96 | // Use the PHI instead of the select. |
| 97 | SI->replaceAllUsesWith(PN); |
| 98 | NewCont->getInstList().erase(SI); |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 99 | |
Chris Lattner | 18bdbc3 | 2004-03-30 18:41:10 +0000 | [diff] [blame] | 100 | Changed = true; |
| 101 | break; // This block is done with. |
| 102 | } |
| 103 | } |
| 104 | return Changed; |
| 105 | } |