lib/Transforms/Scalar/PiNodeInsertion.cpp

   1 //===- PiNodeInsertion.cpp - Insert Pi nodes into a program ---------------===//
   2 //
   3 // PiNodeInsertion - This pass inserts single entry Phi nodes into basic blocks
   4 // that are preceeded by a conditional branch, where the branch gives
   5 // information about the operands of the condition.  For example, this C code:
   6 //   if (x == 0) { ... = x + 4;
   7 // becomes:
   8 //   if (x == 0) {
   9 //     x2 = phi(x);    // Node that can hold data flow information about X
  10 //     ... = x2 + 4;
  11 //
  12 // Since the direction of the condition branch gives information about X itself
  13 // (whether or not it is zero), some passes (like value numbering or ABCD) can
  14 // use the inserted Phi/Pi nodes as a place to attach information, in this case
  15 // saying that X has a value of 0 in this scope.  The power of this analysis
  16 // information is that "in the scope" translates to "for all uses of x2".
  17 //
  18 // This special form of Phi node is refered to as a Pi node, following the
  19 // terminology defined in the "Array Bounds Checks on Demand" paper.
  20 //
  21 // As a really trivial example of what the Pi nodes are good for, this pass
  22 // replaces values compared for equality with direct constants with the constant
  23 // itself in the branch it's equal to the constant.  In the case above, it would
  24 // change the body to be "... = 0 + 4;"  Real value numbering can do much more.
  25 //
  26 //===----------------------------------------------------------------------===//
  27
  28 #include "llvm/Transforms/Scalar.h"
  29 #include "llvm/Analysis/Dominators.h"
  30 #include "llvm/Pass.h"
  31 #include "llvm/Function.h"
  32 #include "llvm/BasicBlock.h"
  33 #include "llvm/iTerminators.h"
  34 #include "llvm/iOperators.h"
  35 #include "llvm/iPHINode.h"
  36 #include "llvm/Support/CFG.h"
  37 #include "Support/StatisticReporter.h"
  38
  39 static Statistic<> NumInserted("pinodes\t\t- Number of Pi nodes inserted");
  40
  41 namespace {
  42   struct PiNodeInserter : public FunctionPass {
  43     const char *getPassName() const { return "Pi Node Insertion"; }
  44
  45     virtual bool runOnFunction(Function *F);
  46
  47     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  48       AU.preservesCFG();
  49       AU.addRequired(DominatorSet::ID);
  50     }
  51
  52     // insertPiNodeFor - Insert a Pi node for V in the successors of BB if our
  53     // conditions hold.  If Rep is not null, fill in a value of 'Rep' instead of
  54     // creating a new Pi node itself because we know that the value is a simple
  55     // constant.
  56     //
  57     bool insertPiNodeFor(Value *V, BasicBlock *BB, Value *Rep = 0);
  58   };
  59 }
  60
  61 Pass *createPiNodeInsertionPass() { return new PiNodeInserter(); }
  62
  63
  64 bool PiNodeInserter::runOnFunction(Function *F) {
  65   bool Changed = false;
  66   for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) {
  67     BasicBlock *BB = *I;
  68     TerminatorInst *TI = BB->getTerminator();
  69
  70     // FIXME: Insert PI nodes for switch statements too
  71
  72     // Look for conditional branch instructions... that branch on a setcc test
  73     if (BranchInst *BI = dyn_cast<BranchInst>(TI))
  74       if (BI->isConditional())
  75         // TODO: we could in theory support logical operations here too...
  76         if (SetCondInst *SCI = dyn_cast<SetCondInst>(BI->getCondition())) {
  77           // Calculate replacement values if this is an obvious constant == or
  78           // != comparison...
  79           Value *TrueRep = 0, *FalseRep = 0;
  80
  81           // Make sure the the constant is the second operand if there is one...
  82           // This fits with our cannonicalization patterns used elsewhere in the
  83           // compiler, without depending on instcombine running before us.
  84           //
  85           if (isa<Constant>(SCI->getOperand(0)) &&
  86               !isa<Constant>(SCI->getOperand(1))) {
  87             SCI->swapOperands();
  88             Changed = true;
  89           }
  90
  91           if (isa<Constant>(SCI->getOperand(1))) {
  92             if (SCI->getOpcode() == Instruction::SetEQ)
  93               TrueRep = SCI->getOperand(1);
  94             else if (SCI->getOpcode() == Instruction::SetNE)
  95               FalseRep = SCI->getOperand(1);
  96           }
  97
  98           BasicBlock *TB = BI->getSuccessor(0);  // True block
  99           BasicBlock *FB = BI->getSuccessor(1);  // False block
 100
 101           // Insert the Pi nodes for the first operand to the comparison...
 102           Changed |= insertPiNodeFor(SCI->getOperand(0), TB, TrueRep);
 103           Changed |= insertPiNodeFor(SCI->getOperand(0), FB, FalseRep);
 104
 105           // Insert the Pi nodes for the second operand to the comparison...
 106           Changed |= insertPiNodeFor(SCI->getOperand(1), TB);
 107           Changed |= insertPiNodeFor(SCI->getOperand(1), FB);
 108         }
 109   }
 110
 111   return Changed;
 112 }
 113
 114
 115 // alreadyHasPiNodeFor - Return true if there is already a Pi node in BB for
 116 // V.
 117 static bool alreadyHasPiNodeFor(Value *V, BasicBlock *BB) {
 118   for (Value::use_iterator I = V->use_begin(), E = V->use_end(); I != E; ++I)
 119     if (PHINode *PN = dyn_cast<PHINode>(*I))
 120       if (PN->getParent() == BB)
 121         return true;
 122   return false;
 123 }
 124
 125
 126 // insertPiNodeFor - Insert a Pi node for V in the successors of BB if our
 127 // conditions hold.  If Rep is not null, fill in a value of 'Rep' instead of
 128 // creating a new Pi node itself because we know that the value is a simple
 129 // constant.
 130 //
 131 bool PiNodeInserter::insertPiNodeFor(Value *V, BasicBlock *Succ, Value *Rep) {
 132   // Do not insert Pi nodes for constants!
 133   if (isa<Constant>(V)) return false;
 134
 135   // Check to make sure that there is not already a PI node inserted...
 136   if (alreadyHasPiNodeFor(V, Succ) && Rep == 0)
 137     return false;
 138
 139   // Insert Pi nodes only into successors that the conditional branch dominates.
 140   // In this simple case, we know that BB dominates a successor as long there
 141   // are no other incoming edges to the successor.
 142   //
 143
 144   // Check to make sure that the successor only has a single predecessor...
 145   pred_iterator PI = pred_begin(Succ);
 146   BasicBlock *Pred = *PI;
 147   if (++PI != pred_end(Succ)) return false;   // Multiple predecessor?  Bail...
 148
 149   // It seems to be safe to insert the Pi node.  Do so now...
 150
 151   // Create the Pi node...
 152   Value *Pi = Rep;
 153   if (Rep == 0) {
 154     PHINode *Phi = new PHINode(V->getType(), V->getName() + ".pi");
 155
 156     // Insert the Pi node in the successor basic block...
 157     Succ->getInstList().push_front(Phi);
 158     Pi = Phi;
 159   }
 160
 161   // Loop over all of the uses of V, replacing ones that the Pi node
 162   // dominates with references to the Pi node itself.
 163   //
 164   DominatorSet &DS = getAnalysis<DominatorSet>();
 165   for (unsigned i = 0; i < V->use_size(); ) {
 166     if (Instruction *U = dyn_cast<Instruction>(*(V->use_begin()+i)))
 167       if (U->getParent()->getParent() == Succ->getParent() &&
 168           DS.dominates(Succ, U->getParent())) {
 169         // This instruction is dominated by the Pi node, replace reference to V
 170         // with a reference to the Pi node.
 171         //
 172         U->replaceUsesOfWith(V, Pi);
 173         continue;           // Do not skip the next use...
 174       }
 175
 176     // This use is not dominated by the Pi node, skip it...
 177     ++i;
 178   }
 179
 180   // Set up the incoming value for the Pi node... do this after uses have been
 181   // replaced, because we don't want the Pi node to refer to itself.
 182   //
 183   if (Rep == 0)
 184     cast<PHINode>(Pi)->addIncoming(V, Pred);
 185
 186
 187   ++NumInserted;
 188   return true;
 189 }
 190