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/Support/GenericDomTree.h" 22#include "llvm/Support/GenericDomTreeConstruction.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 void getAnalysisUsage(AnalysisUsage &AU) const override; 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 bool runOnMachineFunction(MachineFunction &F) override; 70 71 inline bool dominates(const MachineDomTreeNode* A, 72 const MachineDomTreeNode* B) const { 73 return DT->dominates(A, B); 74 } 75 76 inline bool dominates(const MachineBasicBlock* A, 77 const MachineBasicBlock* B) const { 78 return DT->dominates(A, B); 79 } 80 81 // dominates - Return true if A dominates B. This performs the 82 // special checks necessary if A and B are in the same basic block. 83 bool dominates(const MachineInstr *A, const MachineInstr *B) const { 84 const MachineBasicBlock *BBA = A->getParent(), *BBB = B->getParent(); 85 if (BBA != BBB) return DT->dominates(BBA, BBB); 86 87 // Loop through the basic block until we find A or B. 88 MachineBasicBlock::const_iterator I = BBA->begin(); 89 for (; &*I != A && &*I != B; ++I) 90 /*empty*/ ; 91 92 //if(!DT.IsPostDominators) { 93 // A dominates B if it is found first in the basic block. 94 return &*I == A; 95 //} else { 96 // // A post-dominates B if B is found first in the basic block. 97 // return &*I == B; 98 //} 99 } 100 101 inline bool properlyDominates(const MachineDomTreeNode* A, 102 const MachineDomTreeNode* B) const { 103 return DT->properlyDominates(A, B); 104 } 105 106 inline bool properlyDominates(const MachineBasicBlock* A, 107 const MachineBasicBlock* B) const { 108 return DT->properlyDominates(A, B); 109 } 110 111 /// findNearestCommonDominator - Find nearest common dominator basic block 112 /// for basic block A and B. If there is no such block then return NULL. 113 inline MachineBasicBlock *findNearestCommonDominator(MachineBasicBlock *A, 114 MachineBasicBlock *B) { 115 return DT->findNearestCommonDominator(A, B); 116 } 117 118 inline MachineDomTreeNode *operator[](MachineBasicBlock *BB) const { 119 return DT->getNode(BB); 120 } 121 122 /// getNode - return the (Post)DominatorTree node for the specified basic 123 /// block. This is the same as using operator[] on this class. 124 /// 125 inline MachineDomTreeNode *getNode(MachineBasicBlock *BB) const { 126 return DT->getNode(BB); 127 } 128 129 /// addNewBlock - Add a new node to the dominator tree information. This 130 /// creates a new node as a child of DomBB dominator node,linking it into 131 /// the children list of the immediate dominator. 132 inline MachineDomTreeNode *addNewBlock(MachineBasicBlock *BB, 133 MachineBasicBlock *DomBB) { 134 return DT->addNewBlock(BB, DomBB); 135 } 136 137 /// changeImmediateDominator - This method is used to update the dominator 138 /// tree information when a node's immediate dominator changes. 139 /// 140 inline void changeImmediateDominator(MachineBasicBlock *N, 141 MachineBasicBlock* NewIDom) { 142 DT->changeImmediateDominator(N, NewIDom); 143 } 144 145 inline void changeImmediateDominator(MachineDomTreeNode *N, 146 MachineDomTreeNode* NewIDom) { 147 DT->changeImmediateDominator(N, NewIDom); 148 } 149 150 /// eraseNode - Removes a node from the dominator tree. Block must not 151 /// dominate any other blocks. Removes node from its immediate dominator's 152 /// children list. Deletes dominator node associated with basic block BB. 153 inline void eraseNode(MachineBasicBlock *BB) { 154 DT->eraseNode(BB); 155 } 156 157 /// splitBlock - BB is split and now it has one successor. Update dominator 158 /// tree to reflect this change. 159 inline void splitBlock(MachineBasicBlock* NewBB) { 160 DT->splitBlock(NewBB); 161 } 162 163 /// isReachableFromEntry - Return true if A is dominated by the entry 164 /// block of the function containing it. 165 bool isReachableFromEntry(const MachineBasicBlock *A) { 166 return DT->isReachableFromEntry(A); 167 } 168 169 void releaseMemory() override; 170 171 void print(raw_ostream &OS, const Module*) const override; 172}; 173 174//===------------------------------------- 175/// DominatorTree GraphTraits specialization so the DominatorTree can be 176/// iterable by generic graph iterators. 177/// 178 179template<class T> struct GraphTraits; 180 181template <> struct GraphTraits<MachineDomTreeNode *> { 182 typedef MachineDomTreeNode NodeType; 183 typedef NodeType::iterator ChildIteratorType; 184 185 static NodeType *getEntryNode(NodeType *N) { 186 return N; 187 } 188 static inline ChildIteratorType child_begin(NodeType* N) { 189 return N->begin(); 190 } 191 static inline ChildIteratorType child_end(NodeType* N) { 192 return N->end(); 193 } 194}; 195 196template <> struct GraphTraits<MachineDominatorTree*> 197 : public GraphTraits<MachineDomTreeNode *> { 198 static NodeType *getEntryNode(MachineDominatorTree *DT) { 199 return DT->getRootNode(); 200 } 201}; 202 203} 204 205#endif 206