lib/Analysis/DataStructure/MemoryDepAnalysis.cpp

   1 //===- MemoryDepAnalysis.cpp - Compute dep graph for memory ops -----------===//
   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 // This file implements a pass (MemoryDepAnalysis) that computes memory-based
  11 // data dependences between instructions for each function in a module.
  12 // Memory-based dependences occur due to load and store operations, but
  13 // also the side-effects of call instructions.
  14 //
  15 // The result of this pass is a DependenceGraph for each function
  16 // representing the memory-based data dependences between instructions.
  17 //
  18 //===----------------------------------------------------------------------===//
  19
  20 #include "llvm/Analysis/MemoryDepAnalysis.h"
  21 #include "llvm/Module.h"
  22 #include "llvm/iMemory.h"
  23 #include "llvm/iOther.h"
  24 #include "llvm/Analysis/IPModRef.h"
  25 #include "llvm/Analysis/DataStructure.h"
  26 #include "llvm/Analysis/DSGraph.h"
  27 #include "llvm/Support/InstVisitor.h"
  28 #include "llvm/Support/CFG.h"
  29 #include "Support/SCCIterator.h"
  30 #include "Support/Statistic.h"
  31 #include "Support/STLExtras.h"
  32 #include "Support/hash_map"
  33 #include "Support/hash_set"
  34
  35 namespace llvm {
  36
  37 ///--------------------------------------------------------------------------
  38 /// struct ModRefTable:
  39 ///
  40 /// A data structure that tracks ModRefInfo for instructions:
  41 ///   -- modRefMap is a map of Instruction* -> ModRefInfo for the instr.
  42 ///   -- definers  is a vector of instructions that define    any node
  43 ///   -- users     is a vector of instructions that reference any node
  44 ///   -- numUsersBeforeDef is a vector indicating that the number of users
  45 ///                seen before definers[i] is numUsersBeforeDef[i].
  46 ///
  47 /// numUsersBeforeDef[] effectively tells us the exact interleaving of
  48 /// definers and users within the ModRefTable.
  49 /// This is only maintained when constructing the table for one SCC, and
  50 /// not copied over from one table to another since it is no longer useful.
  51 ///--------------------------------------------------------------------------
  52
  53 struct ModRefTable {
  54   typedef hash_map<Instruction*, ModRefInfo> ModRefMap;
  55   typedef ModRefMap::const_iterator                 const_map_iterator;
  56   typedef ModRefMap::      iterator                        map_iterator;
  57   typedef std::vector<Instruction*>::const_iterator const_ref_iterator;
  58   typedef std::vector<Instruction*>::      iterator       ref_iterator;
  59
  60   ModRefMap                 modRefMap;
  61   std::vector<Instruction*> definers;
  62   std::vector<Instruction*> users;
  63   std::vector<unsigned>     numUsersBeforeDef;
  64
  65   // Iterators to enumerate all the defining instructions
  66   const_ref_iterator defsBegin()  const {  return definers.begin(); }
  67         ref_iterator defsBegin()        {  return definers.begin(); }
  68   const_ref_iterator defsEnd()    const {  return definers.end(); }
  69         ref_iterator defsEnd()          {  return definers.end(); }
  70
  71   // Iterators to enumerate all the user instructions
  72   const_ref_iterator usersBegin() const {  return users.begin(); }
  73         ref_iterator usersBegin()       {  return users.begin(); }
  74   const_ref_iterator usersEnd()   const {  return users.end(); }
  75         ref_iterator usersEnd()         {  return users.end(); }
  76
  77   // Iterator identifying the last user that was seen *before* a
  78   // specified def.  In particular, all users in the half-closed range
  79   //    [ usersBegin(), usersBeforeDef_End(defPtr) )
  80   // were seen *before* the specified def.  All users in the half-closed range
  81   //    [ usersBeforeDef_End(defPtr), usersEnd() )
  82   // were seen *after* the specified def.
  83   //
  84   ref_iterator usersBeforeDef_End(const_ref_iterator defPtr) {
  85     unsigned defIndex = (unsigned) (defPtr - defsBegin());
  86     assert(defIndex < numUsersBeforeDef.size());
  87     assert(usersBegin() + numUsersBeforeDef[defIndex] <= usersEnd());
  88     return usersBegin() + numUsersBeforeDef[defIndex];
  89   }
  90   const_ref_iterator usersBeforeDef_End(const_ref_iterator defPtr) const {
  91     return const_cast<ModRefTable*>(this)->usersBeforeDef_End(defPtr);
  92   }
  93
  94   //
  95   // Modifier methods
  96   //
  97   void AddDef(Instruction* D) {
  98     definers.push_back(D);
  99     numUsersBeforeDef.push_back(users.size());
 100   }
 101   void AddUse(Instruction* U) {
 102     users.push_back(U);
 103   }
 104   void Insert(const ModRefTable& fromTable) {
 105     modRefMap.insert(fromTable.modRefMap.begin(), fromTable.modRefMap.end());
 106     definers.insert(definers.end(),
 107                     fromTable.definers.begin(), fromTable.definers.end());
 108     users.insert(users.end(),
 109                  fromTable.users.begin(), fromTable.users.end());
 110     numUsersBeforeDef.clear(); /* fromTable.numUsersBeforeDef is ignored */
 111   }
 112 };
 113
 114
 115 ///--------------------------------------------------------------------------
 116 /// class ModRefInfoBuilder:
 117 ///
 118 /// A simple InstVisitor<> class that retrieves the Mod/Ref info for
 119 /// Load/Store/Call instructions and inserts this information in
 120 /// a ModRefTable.  It also records all instructions that Mod any node
 121 /// and all that use any node.
 122 ///--------------------------------------------------------------------------
 123
 124 class ModRefInfoBuilder : public InstVisitor<ModRefInfoBuilder> {
 125   const DSGraph&            funcGraph;
 126   const FunctionModRefInfo& funcModRef;
 127   struct ModRefTable&       modRefTable;
 128
 129   ModRefInfoBuilder();                         // DO NOT IMPLEMENT
 130   ModRefInfoBuilder(const ModRefInfoBuilder&); // DO NOT IMPLEMENT
 131   void operator=(const ModRefInfoBuilder&);    // DO NOT IMPLEMENT
 132
 133 public:
 134   /*ctor*/      ModRefInfoBuilder(const DSGraph&  _funcGraph,
 135                                   const FunctionModRefInfo& _funcModRef,
 136                                   ModRefTable&    _modRefTable)
 137     : funcGraph(_funcGraph), funcModRef(_funcModRef), modRefTable(_modRefTable)
 138   {
 139   }
 140
 141   // At a call instruction, retrieve the ModRefInfo using IPModRef results.
 142   // Add the call to the defs list if it modifies any nodes and to the uses
 143   // list if it refs any nodes.
 144   //
 145   void          visitCallInst   (CallInst& callInst) {
 146     ModRefInfo safeModRef(funcGraph.getGraphSize());
 147     const ModRefInfo* callModRef = funcModRef.getModRefInfo(callInst);
 148     if (callModRef == NULL)
 149       { // call to external/unknown function: mark all nodes as Mod and Ref
 150         safeModRef.getModSet().set();
 151         safeModRef.getRefSet().set();
 152         callModRef = &safeModRef;
 153       }
 154
 155     modRefTable.modRefMap.insert(std::make_pair(&callInst,
 156                                                 ModRefInfo(*callModRef)));
 157     if (callModRef->getModSet().any())
 158       modRefTable.AddDef(&callInst);
 159     if (callModRef->getRefSet().any())
 160       modRefTable.AddUse(&callInst);
 161   }
 162
 163   // At a store instruction, add to the mod set the single node pointed to
 164   // by the pointer argument of the store.  Interestingly, if there is no
 165   // such node, that would be a null pointer reference!
 166   void          visitStoreInst  (StoreInst& storeInst) {
 167     const DSNodeHandle& ptrNode =
 168       funcGraph.getNodeForValue(storeInst.getPointerOperand());
 169     if (const DSNode* target = ptrNode.getNode())
 170       {
 171         unsigned nodeId = funcModRef.getNodeId(target);
 172         ModRefInfo& minfo =
 173           modRefTable.modRefMap.insert(
 174             std::make_pair(&storeInst,
 175                            ModRefInfo(funcGraph.getGraphSize()))).first->second;
 176         minfo.setNodeIsMod(nodeId);
 177         modRefTable.AddDef(&storeInst);
 178       }
 179     else
 180       std::cerr << "Warning: Uninitialized pointer reference!\n";
 181   }
 182
 183   // At a load instruction, add to the ref set the single node pointed to
 184   // by the pointer argument of the load.  Interestingly, if there is no
 185   // such node, that would be a null pointer reference!
 186   void          visitLoadInst  (LoadInst& loadInst) {
 187     const DSNodeHandle& ptrNode =
 188       funcGraph.getNodeForValue(loadInst.getPointerOperand());
 189     if (const DSNode* target = ptrNode.getNode())
 190       {
 191         unsigned nodeId = funcModRef.getNodeId(target);
 192         ModRefInfo& minfo =
 193           modRefTable.modRefMap.insert(
 194             std::make_pair(&loadInst,
 195                            ModRefInfo(funcGraph.getGraphSize()))).first->second;
 196         minfo.setNodeIsRef(nodeId);
 197         modRefTable.AddUse(&loadInst);
 198       }
 199     else
 200       std::cerr << "Warning: Uninitialized pointer reference!\n";
 201   }
 202 };
 203
 204
 205 //----------------------------------------------------------------------------
 206 // class MemoryDepAnalysis: A dep. graph for load/store/call instructions
 207 //----------------------------------------------------------------------------
 208
 209
 210 /// getAnalysisUsage - This does not modify anything.  It uses the Top-Down DS
 211 /// Graph and IPModRef.
 212 ///
 213 void MemoryDepAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
 214   AU.setPreservesAll();
 215   AU.addRequired<TDDataStructures>();
 216   AU.addRequired<IPModRef>();
 217 }
 218
 219
 220 /// Basic dependence gathering algorithm, using scc_iterator on CFG:
 221 ///
 222 /// for every SCC S in the CFG in PostOrder on the SCC DAG
 223 ///     {
 224 ///       for every basic block BB in S in *postorder*
 225 ///         for every instruction I in BB in reverse
 226 ///           Add (I, ModRef[I]) to ModRefCurrent
 227 ///           if (Mod[I] != NULL)
 228 ///               Add I to DefSetCurrent:  { I \in S : Mod[I] != NULL }
 229 ///           if (Ref[I] != NULL)
 230 ///               Add I to UseSetCurrent:  { I       : Ref[I] != NULL }
 231 ///
 232 ///       for every def D in DefSetCurrent
 233 ///
 234 ///           // NOTE: D comes after itself iff S contains a loop
 235 ///           if (HasLoop(S) && D & D)
 236 ///               Add output-dep: D -> D2
 237 ///
 238 ///           for every def D2 *after* D in DefSetCurrent
 239 ///               // NOTE: D2 comes before D in execution order
 240 ///               if (D & D2)
 241 ///                   Add output-dep: D2 -> D
 242 ///                   if (HasLoop(S))
 243 ///                       Add output-dep: D -> D2
 244 ///
 245 ///           for every use U in UseSetCurrent that was seen *before* D
 246 ///               // NOTE: U comes after D in execution order
 247 ///               if (U & D)
 248 ///                   if (U != D || HasLoop(S))
 249 ///                       Add true-dep: D -> U
 250 ///                   if (HasLoop(S))
 251 ///                       Add anti-dep: U -> D
 252 ///
 253 ///           for every use U in UseSetCurrent that was seen *after* D
 254 ///               // NOTE: U comes before D in execution order
 255 ///               if (U & D)
 256 ///                   if (U != D || HasLoop(S))
 257 ///                       Add anti-dep: U -> D
 258 ///                   if (HasLoop(S))
 259 ///                       Add true-dep: D -> U
 260 ///
 261 ///           for every def Dnext in DefSetAfter
 262 ///               // NOTE: Dnext comes after D in execution order
 263 ///               if (Dnext & D)
 264 ///                   Add output-dep: D -> Dnext
 265 ///
 266 ///           for every use Unext in UseSetAfter
 267 ///               // NOTE: Unext comes after D in execution order
 268 ///               if (Unext & D)
 269 ///                   Add true-dep: D -> Unext
 270 ///
 271 ///       for every use U in UseSetCurrent
 272 ///           for every def Dnext in DefSetAfter
 273 ///               // NOTE: Dnext comes after U in execution order
 274 ///               if (Dnext & D)
 275 ///                   Add anti-dep: U -> Dnext
 276 ///
 277 ///       Add ModRefCurrent to ModRefAfter: { (I, ModRef[I] ) }
 278 ///       Add DefSetCurrent to DefSetAfter: { I : Mod[I] != NULL }
 279 ///       Add UseSetCurrent to UseSetAfter: { I : Ref[I] != NULL }
 280 ///     }
 281 ///
 282 ///
 283 void MemoryDepAnalysis::ProcessSCC(std::vector<BasicBlock*> &S,
 284                                    ModRefTable& ModRefAfter, bool hasLoop) {
 285   ModRefTable ModRefCurrent;
 286   ModRefTable::ModRefMap& mapCurrent = ModRefCurrent.modRefMap;
 287   ModRefTable::ModRefMap& mapAfter   = ModRefAfter.modRefMap;
 288
 289   // Builder class fills out a ModRefTable one instruction at a time.
 290   // To use it, we just invoke it's visit function for each basic block:
 291   //
 292   //   for each basic block BB in the SCC in *postorder*
 293   //       for each instruction  I in BB in *reverse*
 294   //           ModRefInfoBuilder::visit(I)
 295   //           : Add (I, ModRef[I]) to ModRefCurrent.modRefMap
 296   //           : Add I  to ModRefCurrent.definers if it defines any node
 297   //           : Add I  to ModRefCurrent.users    if it uses any node
 298   //
 299   ModRefInfoBuilder builder(*funcGraph, *funcModRef, ModRefCurrent);
 300   for (std::vector<BasicBlock*>::iterator BI = S.begin(), BE = S.end();
 301        BI != BE; ++BI)
 302     // Note: BBs in the SCC<> created by scc_iterator are in postorder.
 303     for (BasicBlock::reverse_iterator II=(*BI)->rbegin(), IE=(*BI)->rend();
 304          II != IE; ++II)
 305       builder.visit(*II);
 306
 307   ///       for every def D in DefSetCurrent
 308   ///
 309   for (ModRefTable::ref_iterator II=ModRefCurrent.defsBegin(),
 310          IE=ModRefCurrent.defsEnd(); II != IE; ++II)
 311     {
 312       ///           // NOTE: D comes after itself iff S contains a loop
 313       ///           if (HasLoop(S))
 314       ///               Add output-dep: D -> D2
 315       if (hasLoop)
 316         funcDepGraph->AddSimpleDependence(**II, **II, OutputDependence);
 317
 318       ///           for every def D2 *after* D in DefSetCurrent
 319       ///               // NOTE: D2 comes before D in execution order
 320       ///               if (D2 & D)
 321       ///                   Add output-dep: D2 -> D
 322       ///                   if (HasLoop(S))
 323       ///                       Add output-dep: D -> D2
 324       for (ModRefTable::ref_iterator JI=II+1; JI != IE; ++JI)
 325         if (!Disjoint(mapCurrent.find(*II)->second.getModSet(),
 326                       mapCurrent.find(*JI)->second.getModSet()))
 327           {
 328             funcDepGraph->AddSimpleDependence(**JI, **II, OutputDependence);
 329             if (hasLoop)
 330               funcDepGraph->AddSimpleDependence(**II, **JI, OutputDependence);
 331           }
 332
 333       ///           for every use U in UseSetCurrent that was seen *before* D
 334       ///               // NOTE: U comes after D in execution order
 335       ///               if (U & D)
 336       ///                   if (U != D || HasLoop(S))
 337       ///                       Add true-dep: U -> D
 338       ///                   if (HasLoop(S))
 339       ///                       Add anti-dep: D -> U
 340       ModRefTable::ref_iterator JI=ModRefCurrent.usersBegin();
 341       ModRefTable::ref_iterator JE = ModRefCurrent.usersBeforeDef_End(II);
 342       for ( ; JI != JE; ++JI)
 343         if (!Disjoint(mapCurrent.find(*II)->second.getModSet(),
 344                       mapCurrent.find(*JI)->second.getRefSet()))
 345           {
 346             if (*II != *JI || hasLoop)
 347               funcDepGraph->AddSimpleDependence(**II, **JI, TrueDependence);
 348             if (hasLoop)
 349               funcDepGraph->AddSimpleDependence(**JI, **II, AntiDependence);
 350           }
 351
 352       ///           for every use U in UseSetCurrent that was seen *after* D
 353       ///               // NOTE: U comes before D in execution order
 354       ///               if (U & D)
 355       ///                   if (U != D || HasLoop(S))
 356       ///                       Add anti-dep: U -> D
 357       ///                   if (HasLoop(S))
 358       ///                       Add true-dep: D -> U
 359       for (/*continue JI*/ JE = ModRefCurrent.usersEnd(); JI != JE; ++JI)
 360         if (!Disjoint(mapCurrent.find(*II)->second.getModSet(),
 361                       mapCurrent.find(*JI)->second.getRefSet()))
 362           {
 363             if (*II != *JI || hasLoop)
 364               funcDepGraph->AddSimpleDependence(**JI, **II, AntiDependence);
 365             if (hasLoop)
 366               funcDepGraph->AddSimpleDependence(**II, **JI, TrueDependence);
 367           }
 368
 369       ///           for every def Dnext in DefSetPrev
 370       ///               // NOTE: Dnext comes after D in execution order
 371       ///               if (Dnext & D)
 372       ///                   Add output-dep: D -> Dnext
 373       for (ModRefTable::ref_iterator JI=ModRefAfter.defsBegin(),
 374              JE=ModRefAfter.defsEnd(); JI != JE; ++JI)
 375         if (!Disjoint(mapCurrent.find(*II)->second.getModSet(),
 376                       mapAfter.find(*JI)->second.getModSet()))
 377           funcDepGraph->AddSimpleDependence(**II, **JI, OutputDependence);
 378
 379       ///           for every use Unext in UseSetAfter
 380       ///               // NOTE: Unext comes after D in execution order
 381       ///               if (Unext & D)
 382       ///                   Add true-dep: D -> Unext
 383       for (ModRefTable::ref_iterator JI=ModRefAfter.usersBegin(),
 384              JE=ModRefAfter.usersEnd(); JI != JE; ++JI)
 385         if (!Disjoint(mapCurrent.find(*II)->second.getModSet(),
 386                       mapAfter.find(*JI)->second.getRefSet()))
 387           funcDepGraph->AddSimpleDependence(**II, **JI, TrueDependence);
 388     }
 389
 390   ///
 391   ///       for every use U in UseSetCurrent
 392   ///           for every def Dnext in DefSetAfter
 393   ///               // NOTE: Dnext comes after U in execution order
 394   ///               if (Dnext & D)
 395   ///                   Add anti-dep: U -> Dnext
 396   for (ModRefTable::ref_iterator II=ModRefCurrent.usersBegin(),
 397          IE=ModRefCurrent.usersEnd(); II != IE; ++II)
 398     for (ModRefTable::ref_iterator JI=ModRefAfter.defsBegin(),
 399            JE=ModRefAfter.defsEnd(); JI != JE; ++JI)
 400       if (!Disjoint(mapCurrent.find(*II)->second.getRefSet(),
 401                     mapAfter.find(*JI)->second.getModSet()))
 402         funcDepGraph->AddSimpleDependence(**II, **JI, AntiDependence);
 403
 404   ///       Add ModRefCurrent to ModRefAfter: { (I, ModRef[I] ) }
 405   ///       Add DefSetCurrent to DefSetAfter: { I : Mod[I] != NULL }
 406   ///       Add UseSetCurrent to UseSetAfter: { I : Ref[I] != NULL }
 407   ModRefAfter.Insert(ModRefCurrent);
 408 }
 409
 410
 411 /// Debugging support methods
 412 ///
 413 void MemoryDepAnalysis::print(std::ostream &O) const
 414 {
 415   // TEMPORARY LOOP
 416   for (hash_map<Function*, DependenceGraph*>::const_iterator
 417          I = funcMap.begin(), E = funcMap.end(); I != E; ++I)
 418     {
 419       Function* func = I->first;
 420       DependenceGraph* depGraph = I->second;
 421
 422   O << "\n================================================================\n";
 423   O << "DEPENDENCE GRAPH FOR MEMORY OPERATIONS IN FUNCTION " << func->getName();
 424   O << "\n================================================================\n\n";
 425   depGraph->print(*func, O);
 426
 427     }
 428 }
 429
 430
 431 ///
 432 /// Run the pass on a function
 433 ///
 434 bool MemoryDepAnalysis::runOnFunction(Function &F) {
 435   assert(!F.isExternal());
 436
 437   // Get the FunctionModRefInfo holding IPModRef results for this function.
 438   // Use the TD graph recorded within the FunctionModRefInfo object, which
 439   // may not be the same as the original TD graph computed by DS analysis.
 440   //
 441   funcModRef = &getAnalysis<IPModRef>().getFunctionModRefInfo(F);
 442   funcGraph  = &funcModRef->getFuncGraph();
 443
 444   // TEMPORARY: ptr to depGraph (later just becomes "this").
 445   assert(!funcMap.count(&F) && "Analyzing function twice?");
 446   funcDepGraph = funcMap[&F] = new DependenceGraph();
 447
 448   ModRefTable ModRefAfter;
 449
 450   for (scc_iterator<Function*> I = scc_begin(&F), E = scc_end(&F); I != E; ++I)
 451     ProcessSCC(*I, ModRefAfter, I.hasLoop());
 452
 453   return true;
 454 }
 455
 456
 457 //-------------------------------------------------------------------------
 458 // TEMPORARY FUNCTIONS TO MAKE THIS A MODULE PASS ---
 459 // These functions will go away once this class becomes a FunctionPass.
 460 //
 461
 462 // Driver function to compute dependence graphs for every function.
 463 // This is temporary and will go away once this is a FunctionPass.
 464 //
 465 bool MemoryDepAnalysis::run(Module& M)
 466 {
 467   for (Module::iterator FI = M.begin(), FE = M.end(); FI != FE; ++FI)
 468     if (! FI->isExternal())
 469       runOnFunction(*FI); // automatically inserts each depGraph into funcMap
 470   return true;
 471 }
 472
 473 // Release all the dependence graphs in the map.
 474 void MemoryDepAnalysis::releaseMemory()
 475 {
 476   for (hash_map<Function*, DependenceGraph*>::const_iterator
 477          I = funcMap.begin(), E = funcMap.end(); I != E; ++I)
 478     delete I->second;
 479   funcMap.clear();
 480
 481   // Clear pointers because the pass constructor will not be invoked again.
 482   funcDepGraph = NULL;
 483   funcGraph = NULL;
 484   funcModRef = NULL;
 485 }
 486
 487 MemoryDepAnalysis::~MemoryDepAnalysis()
 488 {
 489   releaseMemory();
 490 }
 491
 492 //----END TEMPORARY FUNCTIONS----------------------------------------------
 493
 494
 495 void MemoryDepAnalysis::dump() const
 496 {
 497   this->print(std::cerr);
 498 }
 499
 500 static RegisterAnalysis<MemoryDepAnalysis>
 501 Z("memdep", "Memory Dependence Analysis");
 502
 503
 504 } // End llvm namespace