lib/Transforms/HoistPHIConstants.cpp

   1 //===- llvm/Transforms/HoistPHIConstants.h - Normalize PHI nodes ------------=//
   2 //
   3 // HoistPHIConstants - Remove literal constants that are arguments of PHI nodes
   4 // by inserting cast instructions in the preceeding basic blocks, and changing
   5 // constant references into references of the casted value.
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "llvm/Transforms/HoistPHIConstants.h"
  10 #include "llvm/iPHINode.h"
  11 #include "llvm/iOther.h"
  12 #include "llvm/BasicBlock.h"
  13 #include "llvm/Function.h"
  14 #include "llvm/Pass.h"
  15
  16 typedef std::pair<BasicBlock *, Value*> BBConstTy;
  17 typedef std::map<BBConstTy, CastInst *> CachedCopyMap;
  18
  19 static Value *NormalizePhiOperand(PHINode *PN, Value *CPV,
  20                                   BasicBlock *Pred, CachedCopyMap &CopyCache) {
  21   // Check if we've already inserted a copy for this constant in Pred
  22   // Note that `copyCache[Pred]' will create an empty vector the first time
  23   //
  24   CachedCopyMap::iterator CCI = CopyCache.find(BBConstTy(Pred, CPV));
  25   if (CCI != CopyCache.end()) return CCI->second;
  26
  27   // Create a copy instruction and add it to the cache...
  28   CastInst *Inst = new CastInst(CPV, CPV->getType());
  29   CopyCache.insert(std::make_pair(BBConstTy(Pred, CPV), Inst));
  30
  31   // Insert the copy just before the terminator inst of the predecessor BB
  32   assert(Pred->getTerminator() && "Degenerate BB encountered!");
  33   Pred->getInstList().insert(Pred->getInstList().end()-1, Inst);
  34
  35   return Inst;
  36 }
  37
  38
  39 //---------------------------------------------------------------------------
  40 // Entry point for normalizing constant args in PHIs
  41 //---------------------------------------------------------------------------
  42
  43 static bool doHoistPHIConstants(Function *M) {
  44   CachedCopyMap Cache;
  45   bool Changed = false;
  46
  47   for (Function::iterator BI = M->begin(), BE = M->end(); BI != BE; ++BI) {
  48     std::vector<PHINode*> phis;          // normalizing invalidates BB iterator
  49
  50     for (BasicBlock::iterator II = (*BI)->begin(); II != (*BI)->end(); ++II) {
  51       if (PHINode *PN = dyn_cast<PHINode>(*II))
  52         phis.push_back(PN);
  53       else
  54         break;                      // All PHIs occur at top of BB!
  55     }
  56
  57     for (std::vector<PHINode*>::iterator PI=phis.begin(); PI != phis.end();++PI)
  58       for (unsigned i = 0; i < (*PI)->getNumIncomingValues(); ++i) {
  59         Value *Op = (*PI)->getIncomingValue(i);
  60
  61         if (isa<Constant>(Op)) {
  62           (*PI)->setIncomingValue(i,
  63                     NormalizePhiOperand((*PI),
  64                                         (*PI)->getIncomingValue(i),
  65                                         (*PI)->getIncomingBlock(i), Cache));
  66           Changed = true;
  67         }
  68       }
  69   }
  70
  71   return Changed;
  72 }
  73
  74 namespace {
  75   struct HoistPHIConstants : public FunctionPass {
  76     const char *getPassName() const { return "Hoist Constants from PHI Nodes"; }
  77
  78     virtual bool runOnFunction(Function *F) { return doHoistPHIConstants(F); }
  79
  80     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  81       AU.preservesCFG();
  82     }
  83   };
  84 }
  85
  86 Pass *createHoistPHIConstantsPass() { return new HoistPHIConstants(); }