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(DominatorTree& DT, typename GraphT::NodeType* V, unsigned N) {
  25   // This is more understandable as a recursive algorithm, but we can't use the
  26   // recursive algorithm due to stack depth issues.  Keep it here for
  27   // documentation purposes.
  28 #if 0
  29   InfoRec &VInfo = DT.Info[DT.Roots[i]];
  30   VInfo.Semi = ++N;
  31   VInfo.Label = V;
  32
  33   Vertex.push_back(V);        // Vertex[n] = V;
  34   //Info[V].Ancestor = 0;     // Ancestor[n] = 0
  35   //Info[V].Child = 0;        // Child[v] = 0
  36   VInfo.Size = 1;             // Size[v] = 1
  37
  38   for (succ_iterator SI = succ_begin(V), E = succ_end(V); SI != E; ++SI) {
  39     InfoRec &SuccVInfo = DT.Info[*SI];
  40     if (SuccVInfo.Semi == 0) {
  41       SuccVInfo.Parent = V;
  42       N = DTDFSPass(DT, *SI, N);
  43     }
  44   }
  45 #else
  46   std::vector<std::pair<typename GraphT::NodeType*,
  47                         typename GraphT::ChildIteratorType> > Worklist;
  48   Worklist.push_back(std::make_pair(V, GraphT::child_begin(V)));
  49   while (!Worklist.empty()) {
  50     typename GraphT::NodeType* BB = Worklist.back().first;
  51     typename GraphT::ChildIteratorType NextSucc = Worklist.back().second;
  52
  53     // First time we visited this BB?
  54     if (NextSucc == GraphT::child_begin(BB)) {
  55       DominatorTree::InfoRec &BBInfo = DT.Info[BB];
  56       BBInfo.Semi = ++N;
  57       BBInfo.Label = BB;
  58
  59       DT.Vertex.push_back(BB);       // Vertex[n] = V;
  60       //BBInfo[V].Ancestor = 0;   // Ancestor[n] = 0
  61       //BBInfo[V].Child = 0;      // Child[v] = 0
  62       BBInfo.Size = 1;            // Size[v] = 1
  63     }
  64
  65     // If we are done with this block, remove it from the worklist.
  66     if (NextSucc == GraphT::child_end(BB)) {
  67       Worklist.pop_back();
  68       continue;
  69     }
  70
  71     // Increment the successor number for the next time we get to it.
  72     ++Worklist.back().second;
  73
  74     // Visit the successor next, if it isn't already visited.
  75     typename GraphT::NodeType* Succ = *NextSucc;
  76
  77     DominatorTree::InfoRec &SuccVInfo = DT.Info[Succ];
  78     if (SuccVInfo.Semi == 0) {
  79       SuccVInfo.Parent = BB;
  80       Worklist.push_back(std::make_pair(Succ, GraphT::child_begin(Succ)));
  81     }
  82   }
  83 #endif
  84     return N;
  85 }
  86
  87 }
  88
  89 #endif