lib/Analysis/DataStructure/PgmDependenceGraph.cpp

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