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