1 //==- DominatorInternals.cpp - Dominator Calculation -------------*- C++ -*-==//
3 // The LLVM Compiler Infrastructure
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.
8 //===----------------------------------------------------------------------===//
10 #include "llvm/Analysis/Dominators.h"
11 #include "llvm/ADT/DenseMap.h"
12 #include "llvm/ADT/SmallPtrSet.h"
13 //===----------------------------------------------------------------------===//
15 // DominatorTree construction - This pass constructs immediate dominator
16 // information for a flow-graph based on the algorithm described in this
19 // A Fast Algorithm for Finding Dominators in a Flowgraph
20 // T. Lengauer & R. Tarjan, ACM TOPLAS July 1979, pgs 121-141.
22 // This implements both the O(n*ack(n)) and the O(n*log(n)) versions of EVAL and
23 // LINK, but it turns out that the theoretically slower O(n*log(n))
24 // implementation is actually faster than the "efficient" algorithm (even for
25 // large CFGs) because the constant overheads are substantially smaller. The
26 // lower-complexity version can be enabled with the following #define:
28 #define BALANCE_IDOM_TREE 0
30 //===----------------------------------------------------------------------===//
34 void Compress(DominatorTreeBase& DT, BasicBlock *VIn) {
36 std::vector<BasicBlock *> Work;
37 SmallPtrSet<BasicBlock *, 32> Visited;
38 BasicBlock *VInAncestor = DT.Info[VIn].Ancestor;
39 DominatorTreeBase::InfoRec &VInVAInfo = DT.Info[VInAncestor];
41 if (VInVAInfo.Ancestor != 0)
44 while (!Work.empty()) {
45 BasicBlock *V = Work.back();
46 DominatorTree::InfoRec &VInfo = DT.Info[V];
47 BasicBlock *VAncestor = VInfo.Ancestor;
48 DominatorTreeBase::InfoRec &VAInfo = DT.Info[VAncestor];
50 // Process Ancestor first
51 if (Visited.insert(VAncestor) &&
52 VAInfo.Ancestor != 0) {
53 Work.push_back(VAncestor);
58 // Update VInfo based on Ancestor info
59 if (VAInfo.Ancestor == 0)
61 BasicBlock *VAncestorLabel = VAInfo.Label;
62 BasicBlock *VLabel = VInfo.Label;
63 if (DT.Info[VAncestorLabel].Semi < DT.Info[VLabel].Semi)
64 VInfo.Label = VAncestorLabel;
65 VInfo.Ancestor = VAInfo.Ancestor;
69 BasicBlock *Eval(DominatorTreeBase& DT, BasicBlock *V) {
70 DominatorTreeBase::InfoRec &VInfo = DT.Info[V];
71 #if !BALANCE_IDOM_TREE
72 // Higher-complexity but faster implementation
73 if (VInfo.Ancestor == 0)
78 // Lower-complexity but slower implementation
79 if (VInfo.Ancestor == 0)
82 BasicBlock *VLabel = VInfo.Label;
84 BasicBlock *VAncestorLabel = DT.Info[VInfo.Ancestor].Label;
85 if (DT.Info[VAncestorLabel].Semi >= DT.Info[VLabel].Semi)
88 return VAncestorLabel;
92 void Link(DominatorTreeBase& DT, BasicBlock *V, BasicBlock *W,
93 DominatorTreeBase::InfoRec &WInfo) {
94 #if !BALANCE_IDOM_TREE
95 // Higher-complexity but faster implementation
98 // Lower-complexity but slower implementation
99 BasicBlock *WLabel = WInfo.Label;
100 unsigned WLabelSemi = DT.Info[WLabel].Semi;
102 InfoRec *SInfo = &DT.Info[S];
104 BasicBlock *SChild = SInfo->Child;
105 InfoRec *SChildInfo = &DT.Info[SChild];
107 while (WLabelSemi < DT.Info[SChildInfo->Label].Semi) {
108 BasicBlock *SChildChild = SChildInfo->Child;
109 if (SInfo->Size+DT.Info[SChildChild].Size >= 2*SChildInfo->Size) {
110 SChildInfo->Ancestor = S;
111 SInfo->Child = SChild = SChildChild;
112 SChildInfo = &DT.Info[SChild];
114 SChildInfo->Size = SInfo->Size;
115 S = SInfo->Ancestor = SChild;
117 SChild = SChildChild;
118 SChildInfo = &DT.Info[SChild];
122 DominatorTreeBase::InfoRec &VInfo = DT.Info[V];
123 SInfo->Label = WLabel;
125 assert(V != W && "The optimization here will not work in this case!");
126 unsigned WSize = WInfo.Size;
127 unsigned VSize = (VInfo.Size += WSize);
130 std::swap(S, VInfo.Child);