LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

PgmDependenceGraph.cpp

Go to the documentation of this file.
00001 //===- PgmDependenceGraph.cpp - Enumerate PDG for a function ----*- C++ -*-===//
00002 // 
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file was developed by the LLVM research group and is distributed under
00006 // the University of Illinois Open Source License. See LICENSE.TXT for details.
00007 // 
00008 //===----------------------------------------------------------------------===//
00009 // 
00010 // The Program Dependence Graph (PDG) for a single function represents all
00011 // data and control dependences for the function.  This file provides an
00012 // iterator to enumerate all these dependences.  In particular, it enumerates:
00013 // 
00014 // -- Data dependences on memory locations, computed using the
00015 //    MemoryDepAnalysis pass;
00016 // -- Data dependences on SSA registers, directly from Def-Use edges of Values;
00017 // -- Control dependences, computed using postdominance frontiers
00018 //    (NOT YET IMPLEMENTED).
00019 // 
00020 // Note that this file does not create an explicit dependence graph --
00021 // it only provides an iterator to traverse the PDG conceptually.
00022 // The MemoryDepAnalysis does build an explicit graph, which is used internally
00023 // here.  That graph could be augmented with the other dependences above if
00024 // desired, but for most uses there will be little need to do that.
00025 //
00026 //===----------------------------------------------------------------------===//
00027 
00028 #include "PgmDependenceGraph.h"
00029 #include "llvm/Analysis/PostDominators.h"
00030 #include "llvm/Function.h"
00031 #include <iostream>
00032 
00033 namespace llvm {
00034 
00035 //----------------------------------------------------------------------------
00036 // class DepIterState
00037 //----------------------------------------------------------------------------
00038 
00039 const DepIterState::IterStateFlags DepIterState::NoFlag  = 0x0;
00040 const DepIterState::IterStateFlags DepIterState::MemDone = 0x1;
00041 const DepIterState::IterStateFlags DepIterState::SSADone = 0x2;
00042 const DepIterState::IterStateFlags DepIterState::AllDone = 0x4;
00043 const DepIterState::IterStateFlags DepIterState::FirstTimeFlag= 0x8;
00044 
00045 // Find the first memory dependence for the current Mem In/Out iterators.
00046 // Find the first memory dependence for the current Mem In/Out iterators.
00047 // Sets dep to that dependence and returns true if one is found.
00048 // 
00049 bool DepIterState::SetFirstMemoryDep()
00050 {
00051   if (! (depFlags & MemoryDeps))
00052     return false;
00053 
00054   bool doIncomingDeps = dep.getDepType() & IncomingFlag;
00055 
00056   if (( doIncomingDeps && memDepIter == memDepGraph->inDepEnd( *depNode)) ||
00057       (!doIncomingDeps && memDepIter == memDepGraph->outDepEnd(*depNode)))
00058     {
00059       iterFlags |= MemDone;
00060       return false;
00061     }
00062 
00063   dep = *memDepIter;     // simple copy from dependence in memory DepGraph
00064 
00065   return true;
00066 }
00067 
00068 
00069 // Find the first valid data dependence for the current SSA In/Out iterators.
00070 // A valid data dependence is one that is to/from an Instruction.
00071 // E.g., an SSA edge from a formal parameter is not a valid dependence.
00072 // Sets dep to that dependence and returns true if a valid one is found.
00073 // Returns false and leaves dep unchanged otherwise.
00074 // 
00075 bool DepIterState::SetFirstSSADep()
00076 {
00077   if (! (depFlags & SSADeps))
00078     return false;
00079 
00080   bool doIncomingDeps = dep.getDepType() & IncomingFlag;
00081   Instruction* firstTarget = NULL;
00082 
00083   // Increment the In or Out iterator till it runs out or we find a valid dep
00084   if (doIncomingDeps)
00085     for (Instruction::op_iterator E = depNode->getInstr().op_end();
00086          ssaInEdgeIter != E &&
00087            (firstTarget = dyn_cast<Instruction>(ssaInEdgeIter))== NULL; )
00088       ++ssaInEdgeIter;
00089   else
00090     for (Value::use_iterator E = depNode->getInstr().use_end();
00091          ssaOutEdgeIter != E &&
00092            (firstTarget = dyn_cast<Instruction>(*ssaOutEdgeIter)) == NULL; )
00093       ++ssaOutEdgeIter;
00094 
00095   // If the iterator ran out before we found a valid dep, there isn't one.
00096   if (!firstTarget)
00097     {
00098       iterFlags |= SSADone;
00099       return false;
00100     }
00101 
00102   // Create a simple dependence object to represent this SSA dependence.
00103   dep = Dependence(memDepGraph->getNode(*firstTarget, /*create*/ true),
00104                    TrueDependence, doIncomingDeps);
00105 
00106   return true;
00107 }
00108 
00109 
00110 DepIterState::DepIterState(DependenceGraph* _memDepGraph,
00111                            Instruction&     I, 
00112                            bool             incomingDeps,
00113                            PDGIteratorFlags whichDeps)
00114   : memDepGraph(_memDepGraph),
00115     depFlags(whichDeps),
00116     iterFlags(NoFlag)
00117 {
00118   depNode = memDepGraph->getNode(I, /*create*/ true);
00119 
00120   if (incomingDeps)
00121     {
00122       if (whichDeps & MemoryDeps) memDepIter= memDepGraph->inDepBegin(*depNode);
00123       if (whichDeps & SSADeps)    ssaInEdgeIter = I.op_begin();
00124       /* Initialize control dependence iterator here. */
00125     }
00126   else
00127     {
00128       if (whichDeps & MemoryDeps) memDepIter=memDepGraph->outDepBegin(*depNode);
00129       if (whichDeps & SSADeps)    ssaOutEdgeIter = I.use_begin();
00130       /* Initialize control dependence iterator here. */
00131     }
00132 
00133   // Set the dependence to the first of a memory dep or an SSA dep
00134   // and set the done flag if either is found.  Otherwise, set the
00135   // init flag to indicate that the iterators have just been initialized.
00136   // 
00137   if (!SetFirstMemoryDep() && !SetFirstSSADep())
00138     iterFlags |= AllDone;
00139   else
00140     iterFlags |= FirstTimeFlag;
00141 }
00142 
00143 
00144 // Helper function for ++ operator that bumps iterator by 1 (to next
00145 // dependence) and resets the dep field to represent the new dependence.
00146 // 
00147 void DepIterState::Next()
00148 {
00149   // firstMemDone and firstSsaDone are used to indicate when the memory or
00150   // SSA iterators just ran out, or when this is the very first increment.
00151   // In either case, the next iterator (if any) should not be incremented.
00152   // 
00153   bool firstMemDone = iterFlags & FirstTimeFlag;
00154   bool firstSsaDone = iterFlags & FirstTimeFlag;
00155   bool doIncomingDeps = dep.getDepType() & IncomingFlag;
00156 
00157   if (depFlags & MemoryDeps && ! (iterFlags & MemDone))
00158     {
00159       iterFlags &= ~FirstTimeFlag;           // clear "firstTime" flag
00160       ++memDepIter;
00161       if (SetFirstMemoryDep())
00162         return;
00163       firstMemDone = true;              // flags that we _just_ rolled over
00164     }
00165 
00166   if (depFlags & SSADeps && ! (iterFlags & SSADone))
00167     {
00168       // Don't increment the SSA iterator if we either just rolled over from
00169       // the memory dep iterator, or if the SSA iterator is already done.
00170       iterFlags &= ~FirstTimeFlag;           // clear "firstTime" flag
00171       if (! firstMemDone)
00172         if (doIncomingDeps) ++ssaInEdgeIter;
00173         else ++ssaOutEdgeIter;
00174       if (SetFirstSSADep())
00175         return;
00176       firstSsaDone = true;                   // flags if we just rolled over
00177     } 
00178 
00179   if (depFlags & ControlDeps != 0)
00180     {
00181       assert(0 && "Cannot handle control deps");
00182       // iterFlags &= ~FirstTimeFlag;           // clear "firstTime" flag
00183     }
00184 
00185   // This iterator is now complete.
00186   iterFlags |= AllDone;
00187 }
00188 
00189 
00190 //----------------------------------------------------------------------------
00191 // class PgmDependenceGraph
00192 //----------------------------------------------------------------------------
00193 
00194 
00195 // MakeIterator -- Create and initialize an iterator as specified.
00196 // 
00197 PDGIterator PgmDependenceGraph::MakeIterator(Instruction& I,
00198                                              bool incomingDeps,
00199                                              PDGIteratorFlags whichDeps)
00200 {
00201   assert(memDepGraph && "Function not initialized!");
00202   return PDGIterator(new DepIterState(memDepGraph, I, incomingDeps, whichDeps));
00203 }
00204 
00205 
00206 void PgmDependenceGraph::printOutgoingSSADeps(Instruction& I,
00207                                               std::ostream &O)
00208 {
00209   iterator SI = this->outDepBegin(I, SSADeps);
00210   iterator SE = this->outDepEnd(I, SSADeps);
00211   if (SI == SE)
00212     return;
00213 
00214   O << "\n    Outgoing SSA dependences:\n";
00215   for ( ; SI != SE; ++SI)
00216     {
00217       O << "\t";
00218       SI->print(O);
00219       O << " to instruction:";
00220       O << SI->getSink()->getInstr();
00221     }
00222 }
00223 
00224 
00225 void PgmDependenceGraph::print(std::ostream &O) const
00226 {
00227   MemoryDepAnalysis& graphSet = getAnalysis<MemoryDepAnalysis>();
00228 
00229   // TEMPORARY LOOP
00230   for (hash_map<Function*, DependenceGraph*>::iterator
00231          I = graphSet.funcMap.begin(), E = graphSet.funcMap.end();
00232        I != E; ++I)
00233     {
00234       Function* func = I->first;
00235       DependenceGraph* depGraph = I->second;
00236       const_cast<PgmDependenceGraph*>(this)->runOnFunction(*func);
00237 
00238   O << "DEPENDENCE GRAPH FOR FUNCTION " << func->getName() << ":\n";
00239   for (Function::iterator BB=func->begin(), FE=func->end(); BB != FE; ++BB)
00240     for (BasicBlock::iterator II=BB->begin(), IE=BB->end(); II !=IE; ++II)
00241       {
00242         DepGraphNode* dgNode = depGraph->getNode(*II, /*create*/ true);
00243         dgNode->print(O);
00244         const_cast<PgmDependenceGraph*>(this)->printOutgoingSSADeps(*II, O);
00245       }
00246     } // END TEMPORARY LOOP
00247 }
00248 
00249 
00250 void PgmDependenceGraph::dump() const
00251 {
00252   this->print(std::cerr);
00253 }
00254 
00255 static RegisterAnalysis<PgmDependenceGraph>
00256 Z("pgmdep", "Enumerate Program Dependence Graph (data and control)");
00257 
00258 } // End llvm namespace