MachineDominators.h revision 2a085c34933a6c76e5a86f2680d93c16b0438801
1//=- llvm/CodeGen/MachineDominators.h - Machine Dom Calculation --*- C++ -*-==// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file defines classes mirroring those in llvm/Analysis/Dominators.h, 11// but for target-specific code rather than target-independent IR. 12// 13//===----------------------------------------------------------------------===// 14 15#ifndef LLVM_CODEGEN_MACHINEDOMINATORS_H 16#define LLVM_CODEGEN_MACHINEDOMINATORS_H 17 18#include "llvm/CodeGen/MachineBasicBlock.h" 19#include "llvm/CodeGen/MachineFunction.h" 20#include "llvm/CodeGen/MachineFunctionPass.h" 21#include "llvm/Analysis/Dominators.h" 22#include "llvm/Analysis/DominatorInternals.h" 23 24namespace llvm { 25 26template<> 27inline void DominatorTreeBase<MachineBasicBlock>::addRoot(MachineBasicBlock* MBB) { 28 this->Roots.push_back(MBB); 29} 30 31EXTERN_TEMPLATE_INSTANTIATION(class DomTreeNodeBase<MachineBasicBlock>); 32EXTERN_TEMPLATE_INSTANTIATION(class DominatorTreeBase<MachineBasicBlock>); 33 34typedef DomTreeNodeBase<MachineBasicBlock> MachineDomTreeNode; 35 36//===------------------------------------- 37/// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to 38/// compute a normal dominator tree. 39/// 40class MachineDominatorTree : public MachineFunctionPass { 41public: 42 static char ID; // Pass ID, replacement for typeid 43 DominatorTreeBase<MachineBasicBlock>* DT; 44 45 MachineDominatorTree(); 46 47 ~MachineDominatorTree(); 48 49 DominatorTreeBase<MachineBasicBlock>& getBase() { return *DT; } 50 51 virtual void getAnalysisUsage(AnalysisUsage &AU) const; 52 53 /// getRoots - Return the root blocks of the current CFG. This may include 54 /// multiple blocks if we are computing post dominators. For forward 55 /// dominators, this will always be a single block (the entry node). 56 /// 57 inline const std::vector<MachineBasicBlock*> &getRoots() const { 58 return DT->getRoots(); 59 } 60 61 inline MachineBasicBlock *getRoot() const { 62 return DT->getRoot(); 63 } 64 65 inline MachineDomTreeNode *getRootNode() const { 66 return DT->getRootNode(); 67 } 68 69 virtual bool runOnMachineFunction(MachineFunction &F); 70 71 inline bool dominates(MachineDomTreeNode* A, MachineDomTreeNode* B) const { 72 return DT->dominates(A, B); 73 } 74 75 inline bool dominates(MachineBasicBlock* A, MachineBasicBlock* B) const { 76 return DT->dominates(A, B); 77 } 78 79 // dominates - Return true if A dominates B. This performs the 80 // special checks necessary if A and B are in the same basic block. 81 bool dominates(MachineInstr *A, MachineInstr *B) const { 82 MachineBasicBlock *BBA = A->getParent(), *BBB = B->getParent(); 83 if (BBA != BBB) return DT->dominates(BBA, BBB); 84 85 // Loop through the basic block until we find A or B. 86 MachineBasicBlock::iterator I = BBA->begin(); 87 for (; &*I != A && &*I != B; ++I) /*empty*/; 88 89 //if(!DT.IsPostDominators) { 90 // A dominates B if it is found first in the basic block. 91 return &*I == A; 92 //} else { 93 // // A post-dominates B if B is found first in the basic block. 94 // return &*I == B; 95 //} 96 } 97 98 inline bool properlyDominates(const MachineDomTreeNode* A, 99 MachineDomTreeNode* B) const { 100 return DT->properlyDominates(A, B); 101 } 102 103 inline bool properlyDominates(MachineBasicBlock* A, 104 MachineBasicBlock* B) const { 105 return DT->properlyDominates(A, B); 106 } 107 108 /// findNearestCommonDominator - Find nearest common dominator basic block 109 /// for basic block A and B. If there is no such block then return NULL. 110 inline MachineBasicBlock *findNearestCommonDominator(MachineBasicBlock *A, 111 MachineBasicBlock *B) { 112 return DT->findNearestCommonDominator(A, B); 113 } 114 115 inline MachineDomTreeNode *operator[](MachineBasicBlock *BB) const { 116 return DT->getNode(BB); 117 } 118 119 /// getNode - return the (Post)DominatorTree node for the specified basic 120 /// block. This is the same as using operator[] on this class. 121 /// 122 inline MachineDomTreeNode *getNode(MachineBasicBlock *BB) const { 123 return DT->getNode(BB); 124 } 125 126 /// addNewBlock - Add a new node to the dominator tree information. This 127 /// creates a new node as a child of DomBB dominator node,linking it into 128 /// the children list of the immediate dominator. 129 inline MachineDomTreeNode *addNewBlock(MachineBasicBlock *BB, 130 MachineBasicBlock *DomBB) { 131 return DT->addNewBlock(BB, DomBB); 132 } 133 134 /// changeImmediateDominator - This method is used to update the dominator 135 /// tree information when a node's immediate dominator changes. 136 /// 137 inline void changeImmediateDominator(MachineBasicBlock *N, 138 MachineBasicBlock* NewIDom) { 139 DT->changeImmediateDominator(N, NewIDom); 140 } 141 142 inline void changeImmediateDominator(MachineDomTreeNode *N, 143 MachineDomTreeNode* NewIDom) { 144 DT->changeImmediateDominator(N, NewIDom); 145 } 146 147 /// eraseNode - Removes a node from the dominator tree. Block must not 148 /// domiante any other blocks. Removes node from its immediate dominator's 149 /// children list. Deletes dominator node associated with basic block BB. 150 inline void eraseNode(MachineBasicBlock *BB) { 151 DT->eraseNode(BB); 152 } 153 154 /// splitBlock - BB is split and now it has one successor. Update dominator 155 /// tree to reflect this change. 156 inline void splitBlock(MachineBasicBlock* NewBB) { 157 DT->splitBlock(NewBB); 158 } 159 160 161 virtual void releaseMemory(); 162 163 virtual void print(raw_ostream &OS, const Module*) const; 164}; 165 166//===------------------------------------- 167/// DominatorTree GraphTraits specialization so the DominatorTree can be 168/// iterable by generic graph iterators. 169/// 170 171template<class T> struct GraphTraits; 172 173template <> struct GraphTraits<MachineDomTreeNode *> { 174 typedef MachineDomTreeNode NodeType; 175 typedef NodeType::iterator ChildIteratorType; 176 177 static NodeType *getEntryNode(NodeType *N) { 178 return N; 179 } 180 static inline ChildIteratorType child_begin(NodeType* N) { 181 return N->begin(); 182 } 183 static inline ChildIteratorType child_end(NodeType* N) { 184 return N->end(); 185 } 186}; 187 188template <> struct GraphTraits<MachineDominatorTree*> 189 : public GraphTraits<MachineDomTreeNode *> { 190 static NodeType *getEntryNode(MachineDominatorTree *DT) { 191 return DT->getRootNode(); 192 } 193}; 194 195} 196 197#endif 198