include/llvm/Analysis/DominatorInternals.h

   1 //=== llvm/Analysis/DominatorInternals.h - Dominator Calculation -*- C++ -*-==//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by Owen Anderson and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file defines shared implementation details of dominator and
  11 // postdominator calculation.  This file SHOULD NOT BE INCLUDED outside
  12 // of the dominator and postdominator implementation files.
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #ifndef LLVM_ANALYSIS_DOMINATOR_INTERNALS_H
  17 #define LLVM_ANALYSIS_DOMINATOR_INTERNALS_H
  18
  19 #include "llvm/Analysis/Dominators.h"
  20
  21 namespace llvm {
  22
  23 template<class GraphT>
  24 unsigned DFSPass(DominatorTreeBase& DT, typename GraphT::NodeType* V,
  25                  unsigned N) {
  26   // This is more understandable as a recursive algorithm, but we can't use the
  27   // recursive algorithm due to stack depth issues.  Keep it here for
  28   // documentation purposes.
  29 #if 0
  30   InfoRec &VInfo = DT.Info[DT.Roots[i]];
  31   VInfo.Semi = ++N;
  32   VInfo.Label = V;
  33
  34   Vertex.push_back(V);        // Vertex[n] = V;
  35   //Info[V].Ancestor = 0;     // Ancestor[n] = 0
  36   //Info[V].Child = 0;        // Child[v] = 0
  37   VInfo.Size = 1;             // Size[v] = 1
  38
  39   for (succ_iterator SI = succ_begin(V), E = succ_end(V); SI != E; ++SI) {
  40     InfoRec &SuccVInfo = DT.Info[*SI];
  41     if (SuccVInfo.Semi == 0) {
  42       SuccVInfo.Parent = V;
  43       N = DTDFSPass(DT, *SI, N);
  44     }
  45   }
  46 #else
  47   std::vector<std::pair<typename GraphT::NodeType*,
  48                         typename GraphT::ChildIteratorType> > Worklist;
  49   Worklist.push_back(std::make_pair(V, GraphT::child_begin(V)));
  50   while (!Worklist.empty()) {
  51     typename GraphT::NodeType* BB = Worklist.back().first;
  52     typename GraphT::ChildIteratorType NextSucc = Worklist.back().second;
  53
  54     // First time we visited this BB?
  55     if (NextSucc == GraphT::child_begin(BB)) {
  56       DominatorTree::InfoRec &BBInfo = DT.Info[BB];
  57       BBInfo.Semi = ++N;
  58       BBInfo.Label = BB;
  59
  60       DT.Vertex.push_back(BB);       // Vertex[n] = V;
  61       //BBInfo[V].Ancestor = 0;   // Ancestor[n] = 0
  62       //BBInfo[V].Child = 0;      // Child[v] = 0
  63       BBInfo.Size = 1;            // Size[v] = 1
  64     }
  65
  66     // If we are done with this block, remove it from the worklist.
  67     if (NextSucc == GraphT::child_end(BB)) {
  68       Worklist.pop_back();
  69       continue;
  70     }
  71
  72     // Increment the successor number for the next time we get to it.
  73     ++Worklist.back().second;
  74
  75     // Visit the successor next, if it isn't already visited.
  76     typename GraphT::NodeType* Succ = *NextSucc;
  77
  78     DominatorTree::InfoRec &SuccVInfo = DT.Info[Succ];
  79     if (SuccVInfo.Semi == 0) {
  80       SuccVInfo.Parent = BB;
  81       Worklist.push_back(std::make_pair(Succ, GraphT::child_begin(Succ)));
  82     }
  83   }
  84 #endif
  85     return N;
  86 }
  87
  88 }
  89
  90 #endif