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