lib/Analysis/IPA/PgmDependenceGraph.cpp

   1 //===- PgmDependenceGraph.cpp - Enumerate PDG for a function ----*- C++ -*-===//
   2 //
   3 // The Program Dependence Graph (PDG) for a single function represents all
   4 // data and control dependences for the function.  This file provides an
   5 // iterator to enumerate all these dependences.  In particular, it enumerates:
   6 //
   7 // -- Data dependences on memory locations, computed using the
   8 //    MemoryDepAnalysis pass;
   9 // -- Data dependences on SSA registers, directly from Def-Use edges of Values;
  10 // -- Control dependences, computed using postdominance frontiers
  11 //    (NOT YET IMPLEMENTED).
  12 //
  13 // Note that this file does not create an explicit dependence graph --
  14 // it only provides an iterator to traverse the PDG conceptually.
  15 // The MemoryDepAnalysis does build an explicit graph, which is used internally
  16 // here.  That graph could be augmented with the other dependences above if
  17 // desired, but for most uses there will be little need to do that.
  18 //
  19 //===----------------------------------------------------------------------===//
  20
  21 #include "llvm/Analysis/PgmDependenceGraph.h"
  22 #include "llvm/Analysis/MemoryDepAnalysis.h"
  23 #include "llvm/Analysis/PostDominators.h"
  24 #include "llvm/Function.h"
  25
  26
  27 //----------------------------------------------------------------------------
  28 // class DepIterState
  29 //----------------------------------------------------------------------------
  30
  31 const DepIterState::IterStateFlags DepIterState::NoFlag  = 0x0;
  32 const DepIterState::IterStateFlags DepIterState::MemDone = 0x1;
  33 const DepIterState::IterStateFlags DepIterState::SSADone = 0x2;
  34 const DepIterState::IterStateFlags DepIterState::AllDone = 0x4;
  35 const DepIterState::IterStateFlags DepIterState::FirstTimeFlag= 0x8;
  36
  37 // Find the first memory dependence for the current Mem In/Out iterators.
  38 // Find the first memory dependence for the current Mem In/Out iterators.
  39 // Sets dep to that dependence and returns true if one is found.
  40 //
  41 bool DepIterState::SetFirstMemoryDep()
  42 {
  43   if (! (depFlags & MemoryDeps))
  44     return false;
  45
  46   bool doIncomingDeps = dep.getDepType() & IncomingFlag;
  47
  48   if (( doIncomingDeps && memDepIter == memDepGraph->inDepEnd( *depNode)) ||
  49       (!doIncomingDeps && memDepIter == memDepGraph->outDepEnd(*depNode)))
  50     {
  51       iterFlags |= MemDone;
  52       return false;
  53     }
  54
  55   dep = *memDepIter;     // simple copy from dependence in memory DepGraph
  56
  57   return true;
  58 }
  59
  60
  61 // Find the first valid data dependence for the current SSA In/Out iterators.
  62 // A valid data dependence is one that is to/from an Instruction.
  63 // E.g., an SSA edge from a formal parameter is not a valid dependence.
  64 // Sets dep to that dependence and returns true if a valid one is found.
  65 // Returns false and leaves dep unchanged otherwise.
  66 //
  67 bool DepIterState::SetFirstSSADep()
  68 {
  69   if (! (depFlags & SSADeps))
  70     return false;
  71
  72   bool doIncomingDeps = dep.getDepType() & IncomingFlag;
  73   Instruction* firstTarget = NULL;
  74
  75   // Increment the In or Out iterator till it runs out or we find a valid dep
  76   if (doIncomingDeps)
  77     for (Instruction::op_iterator E = depNode->getInstr().op_end();
  78          ssaInEdgeIter != E &&
  79            (firstTarget = dyn_cast<Instruction>(ssaInEdgeIter))== NULL; )
  80       ++ssaInEdgeIter;
  81   else
  82     for (Value::use_iterator E = depNode->getInstr().use_end();
  83          ssaOutEdgeIter != E &&
  84            (firstTarget = dyn_cast<Instruction>(*ssaOutEdgeIter)) == NULL; )
  85       ++ssaOutEdgeIter;
  86
  87   // If the iterator ran out before we found a valid dep, there isn't one.
  88   if (!firstTarget)
  89     {
  90       iterFlags |= SSADone;
  91       return false;
  92     }
  93
  94   // Create a simple dependence object to represent this SSA dependence.
  95   dep = Dependence(memDepGraph->getNode(*firstTarget, /*create*/ true),
  96                    TrueDependence, doIncomingDeps);
  97
  98   return true;
  99 }
 100
 101
 102 DepIterState::DepIterState(DependenceGraph* _memDepGraph,
 103                            Instruction&     I,
 104                            bool             incomingDeps,
 105                            PDGIteratorFlags whichDeps)
 106   : memDepGraph(_memDepGraph),
 107     depFlags(whichDeps),
 108     iterFlags(NoFlag)
 109 {
 110   depNode = memDepGraph->getNode(I, /*create*/ true);
 111
 112   if (incomingDeps)
 113     {
 114       if (whichDeps & MemoryDeps) memDepIter= memDepGraph->inDepBegin(*depNode);
 115       if (whichDeps & SSADeps)    ssaInEdgeIter = I.op_begin();
 116       /* Initialize control dependence iterator here. */
 117     }
 118   else
 119     {
 120       if (whichDeps & MemoryDeps) memDepIter=memDepGraph->outDepBegin(*depNode);
 121       if (whichDeps & SSADeps)    ssaOutEdgeIter = I.use_begin();
 122       /* Initialize control dependence iterator here. */
 123     }
 124
 125   // Set the dependence to the first of a memory dep or an SSA dep
 126   // and set the done flag if either is found.  Otherwise, set the
 127   // init flag to indicate that the iterators have just been initialized.
 128   //
 129   if (!SetFirstMemoryDep() && !SetFirstSSADep())
 130     iterFlags |= AllDone;
 131   else
 132     iterFlags |= FirstTimeFlag;
 133 }
 134
 135
 136 // Helper function for ++ operator that bumps iterator by 1 (to next
 137 // dependence) and resets the dep field to represent the new dependence.
 138 //
 139 void DepIterState::Next()
 140 {
 141   // firstMemDone and firstSsaDone are used to indicate when the memory or
 142   // SSA iterators just ran out, or when this is the very first increment.
 143   // In either case, the next iterator (if any) should not be incremented.
 144   //
 145   bool firstMemDone = iterFlags & FirstTimeFlag;
 146   bool firstSsaDone = iterFlags & FirstTimeFlag;
 147   bool doIncomingDeps = dep.getDepType() & IncomingFlag;
 148
 149   if (depFlags & MemoryDeps && ! (iterFlags & MemDone))
 150     {
 151       iterFlags &= ~FirstTimeFlag;           // clear "firstTime" flag
 152       ++memDepIter;
 153       if (SetFirstMemoryDep())
 154         return;
 155       firstMemDone = true;              // flags that we _just_ rolled over
 156     }
 157
 158   if (depFlags & SSADeps && ! (iterFlags & SSADone))
 159     {
 160       // Don't increment the SSA iterator if we either just rolled over from
 161       // the memory dep iterator, or if the SSA iterator is already done.
 162       iterFlags &= ~FirstTimeFlag;           // clear "firstTime" flag
 163       if (! firstMemDone)
 164         if (doIncomingDeps) ++ssaInEdgeIter;
 165         else ++ssaOutEdgeIter;
 166       if (SetFirstSSADep())
 167         return;
 168       firstSsaDone = true;                   // flags if we just rolled over
 169     }
 170
 171   if (depFlags & ControlDeps != 0)
 172     {
 173       assert(0 && "Cannot handle control deps");
 174       // iterFlags &= ~FirstTimeFlag;           // clear "firstTime" flag
 175     }
 176
 177   // This iterator is now complete.
 178   iterFlags |= AllDone;
 179 }
 180
 181
 182 //----------------------------------------------------------------------------
 183 // class PgmDependenceGraph
 184 //----------------------------------------------------------------------------
 185
 186
 187 // MakeIterator -- Create and initialize an iterator as specified.
 188 //
 189 PDGIterator PgmDependenceGraph::MakeIterator(Instruction& I,
 190                                              bool incomingDeps,
 191                                              PDGIteratorFlags whichDeps)
 192 {
 193   assert(memDepGraph && "Function not initialized!");
 194   return PDGIterator(new DepIterState(memDepGraph, I, incomingDeps, whichDeps));
 195 }
 196
 197
 198 void PgmDependenceGraph::printOutgoingSSADeps(Instruction& I,
 199                                               std::ostream &O)
 200 {
 201   iterator SI = this->outDepBegin(I, SSADeps);
 202   iterator SE = this->outDepEnd(I, SSADeps);
 203   if (SI == SE)
 204     return;
 205
 206   O << "\n    Outgoing SSA dependences:\n";
 207   for ( ; SI != SE; ++SI)
 208     {
 209       O << "\t";
 210       SI->print(O);
 211       O << " to instruction:";
 212       O << SI->getSink()->getInstr();
 213     }
 214 }
 215
 216
 217 void PgmDependenceGraph::print(std::ostream &O) const
 218 {
 219   MemoryDepAnalysis& graphSet = getAnalysis<MemoryDepAnalysis>();
 220
 221   // TEMPORARY LOOP
 222   for (hash_map<Function*, DependenceGraph*>::iterator
 223          I = graphSet.funcMap.begin(), E = graphSet.funcMap.end();
 224        I != E; ++I)
 225     {
 226       Function* func = I->first;
 227       DependenceGraph* depGraph = I->second;
 228       const_cast<PgmDependenceGraph*>(this)->runOnFunction(*func);
 229
 230   O << "DEPENDENCE GRAPH FOR FUNCTION " << func->getName() << ":\n";
 231   for (Function::iterator BB=func->begin(), FE=func->end(); BB != FE; ++BB)
 232     for (BasicBlock::iterator II=BB->begin(), IE=BB->end(); II !=IE; ++II)
 233       {
 234         DepGraphNode* dgNode = depGraph->getNode(*II, /*create*/ true);
 235         dgNode->print(O);
 236         const_cast<PgmDependenceGraph*>(this)->printOutgoingSSADeps(*II, O);
 237       }
 238     } // END TEMPORARY LOOP
 239 }
 240
 241
 242 void PgmDependenceGraph::dump() const
 243 {
 244   this->print(std::cerr);
 245 }
 246
 247 static RegisterAnalysis<PgmDependenceGraph>
 248 Z("pgmdep", "Enumerate Program Dependence Graph (data and control)");