MachineDominators.h revision 791102fb1192ac9483274e54cbc42480c9b1af10
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 26inline void WriteAsOperand(raw_ostream &, const MachineBasicBlock*, bool t) { } 27 28template<> 29inline void DominatorTreeBase<MachineBasicBlock>::addRoot(MachineBasicBlock* MBB) { 30 this->Roots.push_back(MBB); 31} 32 33EXTERN_TEMPLATE_INSTANTIATION(class DomTreeNodeBase<MachineBasicBlock>); 34EXTERN_TEMPLATE_INSTANTIATION(class DominatorTreeBase<MachineBasicBlock>); 35 36typedef DomTreeNodeBase<MachineBasicBlock> MachineDomTreeNode; 37 38//===------------------------------------- 39/// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to 40/// compute a normal dominator tree. 41/// 42class MachineDominatorTree : public MachineFunctionPass { 43public: 44 static char ID; // Pass ID, replacement for typeid 45 DominatorTreeBase<MachineBasicBlock>* DT; 46 47 MachineDominatorTree(); 48 49 ~MachineDominatorTree(); 50 51 DominatorTreeBase<MachineBasicBlock>& getBase() { return *DT; } 52 53 virtual void getAnalysisUsage(AnalysisUsage &AU) const; 54 55 /// getRoots - Return the root blocks of the current CFG. This may include 56 /// multiple blocks if we are computing post dominators. For forward 57 /// dominators, this will always be a single block (the entry node). 58 /// 59 inline const std::vector<MachineBasicBlock*> &getRoots() const { 60 return DT->getRoots(); 61 } 62 63 inline MachineBasicBlock *getRoot() const { 64 return DT->getRoot(); 65 } 66 67 inline MachineDomTreeNode *getRootNode() const { 68 return DT->getRootNode(); 69 } 70 71 virtual bool runOnMachineFunction(MachineFunction &F); 72 73 inline bool dominates(MachineDomTreeNode* A, MachineDomTreeNode* B) const { 74 return DT->dominates(A, B); 75 } 76 77 inline bool dominates(MachineBasicBlock* A, 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(MachineInstr *A, MachineInstr *B) const { 84 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::iterator I = BBA->begin(); 89 for (; &*I != A && &*I != B; ++I) /*empty*/; 90 91 //if(!DT.IsPostDominators) { 92 // A dominates B if it is found first in the basic block. 93 return &*I == A; 94 //} else { 95 // // A post-dominates B if B is found first in the basic block. 96 // return &*I == B; 97 //} 98 } 99 100 inline bool properlyDominates(const MachineDomTreeNode* A, 101 MachineDomTreeNode* B) const { 102 return DT->properlyDominates(A, B); 103 } 104 105 inline bool properlyDominates(MachineBasicBlock* A, 106 MachineBasicBlock* B) const { 107 return DT->properlyDominates(A, B); 108 } 109 110 /// findNearestCommonDominator - Find nearest common dominator basic block 111 /// for basic block A and B. If there is no such block then return NULL. 112 inline MachineBasicBlock *findNearestCommonDominator(MachineBasicBlock *A, 113 MachineBasicBlock *B) { 114 return DT->findNearestCommonDominator(A, B); 115 } 116 117 inline MachineDomTreeNode *operator[](MachineBasicBlock *BB) const { 118 return DT->getNode(BB); 119 } 120 121 /// getNode - return the (Post)DominatorTree node for the specified basic 122 /// block. This is the same as using operator[] on this class. 123 /// 124 inline MachineDomTreeNode *getNode(MachineBasicBlock *BB) const { 125 return DT->getNode(BB); 126 } 127 128 /// addNewBlock - Add a new node to the dominator tree information. This 129 /// creates a new node as a child of DomBB dominator node,linking it into 130 /// the children list of the immediate dominator. 131 inline MachineDomTreeNode *addNewBlock(MachineBasicBlock *BB, 132 MachineBasicBlock *DomBB) { 133 return DT->addNewBlock(BB, DomBB); 134 } 135 136 /// changeImmediateDominator - This method is used to update the dominator 137 /// tree information when a node's immediate dominator changes. 138 /// 139 inline void changeImmediateDominator(MachineBasicBlock *N, 140 MachineBasicBlock* NewIDom) { 141 DT->changeImmediateDominator(N, NewIDom); 142 } 143 144 inline void changeImmediateDominator(MachineDomTreeNode *N, 145 MachineDomTreeNode* NewIDom) { 146 DT->changeImmediateDominator(N, NewIDom); 147 } 148 149 /// eraseNode - Removes a node from the dominator tree. Block must not 150 /// domiante any other blocks. Removes node from its immediate dominator's 151 /// children list. Deletes dominator node associated with basic block BB. 152 inline void eraseNode(MachineBasicBlock *BB) { 153 DT->eraseNode(BB); 154 } 155 156 /// splitBlock - BB is split and now it has one successor. Update dominator 157 /// tree to reflect this change. 158 inline void splitBlock(MachineBasicBlock* NewBB) { 159 DT->splitBlock(NewBB); 160 } 161 162 163 virtual void releaseMemory(); 164 165 virtual void print(std::ostream &OS, const Module*) const; 166}; 167 168//===------------------------------------- 169/// DominatorTree GraphTraits specialization so the DominatorTree can be 170/// iterable by generic graph iterators. 171/// 172 173template<class T> struct GraphTraits; 174 175template <> struct GraphTraits<MachineDomTreeNode *> { 176 typedef MachineDomTreeNode NodeType; 177 typedef NodeType::iterator ChildIteratorType; 178 179 static NodeType *getEntryNode(NodeType *N) { 180 return N; 181 } 182 static inline ChildIteratorType child_begin(NodeType* N) { 183 return N->begin(); 184 } 185 static inline ChildIteratorType child_end(NodeType* N) { 186 return N->end(); 187 } 188}; 189 190template <> struct GraphTraits<MachineDominatorTree*> 191 : public GraphTraits<MachineDomTreeNode *> { 192 static NodeType *getEntryNode(MachineDominatorTree *DT) { 193 return DT->getRootNode(); 194 } 195}; 196 197} 198 199#endif 200