lib/Transforms/Scalar/PiNodeInsertion.cpp

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