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