LLVM API Documentation
00001 //=- llvm/CodeGen/MachineDominators.h - Machine Dom Calculation --*- C++ -*-==// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file defines classes mirroring those in llvm/Analysis/Dominators.h, 00011 // but for target-specific code rather than target-independent IR. 00012 // 00013 //===----------------------------------------------------------------------===// 00014 00015 #ifndef LLVM_CODEGEN_MACHINEDOMINATORS_H 00016 #define LLVM_CODEGEN_MACHINEDOMINATORS_H 00017 00018 #include "llvm/CodeGen/MachineBasicBlock.h" 00019 #include "llvm/CodeGen/MachineFunction.h" 00020 #include "llvm/CodeGen/MachineFunctionPass.h" 00021 #include "llvm/Analysis/Dominators.h" 00022 #include "llvm/Analysis/DominatorInternals.h" 00023 00024 namespace llvm { 00025 00026 inline void WriteAsOperand(std::ostream &, const MachineBasicBlock*, bool t) { } 00027 00028 template<> 00029 inline void DominatorTreeBase<MachineBasicBlock>::addRoot(MachineBasicBlock* MBB) { 00030 this->Roots.push_back(MBB); 00031 } 00032 00033 EXTERN_TEMPLATE_INSTANTIATION(class DomTreeNodeBase<MachineBasicBlock>); 00034 EXTERN_TEMPLATE_INSTANTIATION(class DominatorTreeBase<MachineBasicBlock>); 00035 00036 typedef DomTreeNodeBase<MachineBasicBlock> MachineDomTreeNode; 00037 00038 //===------------------------------------- 00039 /// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to 00040 /// compute a normal dominator tree. 00041 /// 00042 class MachineDominatorTree : public MachineFunctionPass { 00043 public: 00044 static char ID; // Pass ID, replacement for typeid 00045 DominatorTreeBase<MachineBasicBlock>* DT; 00046 00047 MachineDominatorTree(); 00048 00049 ~MachineDominatorTree(); 00050 00051 DominatorTreeBase<MachineBasicBlock>& getBase() { return *DT; } 00052 00053 virtual void getAnalysisUsage(AnalysisUsage &AU) const; 00054 00055 /// getRoots - Return the root blocks of the current CFG. This may include 00056 /// multiple blocks if we are computing post dominators. For forward 00057 /// dominators, this will always be a single block (the entry node). 00058 /// 00059 inline const std::vector<MachineBasicBlock*> &getRoots() const { 00060 return DT->getRoots(); 00061 } 00062 00063 inline MachineBasicBlock *getRoot() const { 00064 return DT->getRoot(); 00065 } 00066 00067 inline MachineDomTreeNode *getRootNode() const { 00068 return DT->getRootNode(); 00069 } 00070 00071 virtual bool runOnMachineFunction(MachineFunction &F); 00072 00073 inline bool dominates(MachineDomTreeNode* A, MachineDomTreeNode* B) const { 00074 return DT->dominates(A, B); 00075 } 00076 00077 inline bool dominates(MachineBasicBlock* A, MachineBasicBlock* B) const { 00078 return DT->dominates(A, B); 00079 } 00080 00081 // dominates - Return true if A dominates B. This performs the 00082 // special checks necessary if A and B are in the same basic block. 00083 bool dominates(MachineInstr *A, MachineInstr *B) const { 00084 MachineBasicBlock *BBA = A->getParent(), *BBB = B->getParent(); 00085 if (BBA != BBB) return DT->dominates(BBA, BBB); 00086 00087 // Loop through the basic block until we find A or B. 00088 MachineBasicBlock::iterator I = BBA->begin(); 00089 for (; &*I != A && &*I != B; ++I) /*empty*/; 00090 00091 //if(!DT.IsPostDominators) { 00092 // A dominates B if it is found first in the basic block. 00093 return &*I == A; 00094 //} else { 00095 // // A post-dominates B if B is found first in the basic block. 00096 // return &*I == B; 00097 //} 00098 } 00099 00100 inline bool properlyDominates(const MachineDomTreeNode* A, 00101 MachineDomTreeNode* B) const { 00102 return DT->properlyDominates(A, B); 00103 } 00104 00105 inline bool properlyDominates(MachineBasicBlock* A, 00106 MachineBasicBlock* B) const { 00107 return DT->properlyDominates(A, B); 00108 } 00109 00110 /// findNearestCommonDominator - Find nearest common dominator basic block 00111 /// for basic block A and B. If there is no such block then return NULL. 00112 inline MachineBasicBlock *findNearestCommonDominator(MachineBasicBlock *A, 00113 MachineBasicBlock *B) { 00114 return DT->findNearestCommonDominator(A, B); 00115 } 00116 00117 inline MachineDomTreeNode *operator[](MachineBasicBlock *BB) const { 00118 return DT->getNode(BB); 00119 } 00120 00121 /// getNode - return the (Post)DominatorTree node for the specified basic 00122 /// block. This is the same as using operator[] on this class. 00123 /// 00124 inline MachineDomTreeNode *getNode(MachineBasicBlock *BB) const { 00125 return DT->getNode(BB); 00126 } 00127 00128 /// addNewBlock - Add a new node to the dominator tree information. This 00129 /// creates a new node as a child of DomBB dominator node,linking it into 00130 /// the children list of the immediate dominator. 00131 inline MachineDomTreeNode *addNewBlock(MachineBasicBlock *BB, 00132 MachineBasicBlock *DomBB) { 00133 return DT->addNewBlock(BB, DomBB); 00134 } 00135 00136 /// changeImmediateDominator - This method is used to update the dominator 00137 /// tree information when a node's immediate dominator changes. 00138 /// 00139 inline void changeImmediateDominator(MachineBasicBlock *N, 00140 MachineBasicBlock* NewIDom) { 00141 DT->changeImmediateDominator(N, NewIDom); 00142 } 00143 00144 inline void changeImmediateDominator(MachineDomTreeNode *N, 00145 MachineDomTreeNode* NewIDom) { 00146 DT->changeImmediateDominator(N, NewIDom); 00147 } 00148 00149 /// eraseNode - Removes a node from the dominator tree. Block must not 00150 /// domiante any other blocks. Removes node from its immediate dominator's 00151 /// children list. Deletes dominator node associated with basic block BB. 00152 inline void eraseNode(MachineBasicBlock *BB) { 00153 DT->eraseNode(BB); 00154 } 00155 00156 /// splitBlock - BB is split and now it has one successor. Update dominator 00157 /// tree to reflect this change. 00158 inline void splitBlock(MachineBasicBlock* NewBB) { 00159 DT->splitBlock(NewBB); 00160 } 00161 00162 00163 virtual void releaseMemory(); 00164 00165 virtual void print(std::ostream &OS, const Module* M= 0) const { 00166 DT->print(OS, M); 00167 } 00168 }; 00169 00170 //===------------------------------------- 00171 /// DominatorTree GraphTraits specialization so the DominatorTree can be 00172 /// iterable by generic graph iterators. 00173 /// 00174 00175 template<class T> struct GraphTraits; 00176 00177 template <> struct GraphTraits<MachineDomTreeNode *> { 00178 typedef MachineDomTreeNode NodeType; 00179 typedef NodeType::iterator ChildIteratorType; 00180 00181 static NodeType *getEntryNode(NodeType *N) { 00182 return N; 00183 } 00184 static inline ChildIteratorType child_begin(NodeType* N) { 00185 return N->begin(); 00186 } 00187 static inline ChildIteratorType child_end(NodeType* N) { 00188 return N->end(); 00189 } 00190 }; 00191 00192 template <> struct GraphTraits<MachineDominatorTree*> 00193 : public GraphTraits<MachineDomTreeNode *> { 00194 static NodeType *getEntryNode(MachineDominatorTree *DT) { 00195 return DT->getRootNode(); 00196 } 00197 }; 00198 00199 } 00200 00201 #endif