lib/Transforms/Utils/LowerSelect.cpp

   1 //===- LowerSelect.cpp - Transform select insts to branches ---------------===//
   2 //
   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.
   7 //
   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"
  22 #include "llvm/Transforms/Utils/UnifyFunctionExitNodes.h"
  23 #include "llvm/Function.h"
  24 #include "llvm/Instructions.h"
  25 #include "llvm/Pass.h"
  26 #include "llvm/Type.h"
  27 #include "llvm/Support/Compiler.h"
  28 using namespace llvm;
  29
  30 namespace {
  31   /// LowerSelect - Turn select instructions into conditional branches.
  32   ///
  33   class VISIBILITY_HIDDEN LowerSelect : public FunctionPass {
  34     bool OnlyFP;   // Only lower FP select instructions?
  35   public:
  36     static const char ID; // Pass identifcation, replacement for typeid
  37     LowerSelect(bool onlyfp = false) : FunctionPass((intptr_t)&ID),
  38       OnlyFP(onlyfp) {}
  39
  40     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  41       // This certainly destroys the CFG.
  42       // This is a cluster of orthogonal Transforms:
  43       AU.addPreserved<UnifyFunctionExitNodes>();
  44       AU.addPreservedID(PromoteMemoryToRegisterID);
  45       AU.addPreservedID(LowerSwitchID);
  46       AU.addPreservedID(LowerInvokePassID);
  47       AU.addPreservedID(LowerAllocationsID);
  48     }
  49
  50     bool runOnFunction(Function &F);
  51   };
  52
  53   const char LowerSelect::ID = 0;
  54   RegisterPass<LowerSelect>
  55   X("lowerselect", "Lower select instructions to branches");
  56 }
  57
  58 // Publically exposed interface to pass...
  59 const PassInfo *llvm::LowerSelectID = X.getPassInfo();
  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.
  91           PHINode *PN = new PHINode(SI->getType(), "", NewCont->begin());
  92           PN->takeName(SI);
  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);
  99
 100           Changed = true;
 101           break; // This block is done with.
 102         }
 103     }
 104   return Changed;
 105 }