diff options
| -rw-r--r-- | include/llvm/Analysis/DominatorInternals.h | 13 | ||||
| -rw-r--r-- | include/llvm/Analysis/Dominators.h | 25 | ||||
| -rw-r--r-- | include/llvm/CodeGen/MachineDominators.h | 18 | ||||
| -rw-r--r-- | lib/CodeGen/MachineDominators.cpp | 24 |
4 files changed, 62 insertions, 18 deletions
diff --git a/include/llvm/Analysis/DominatorInternals.h b/include/llvm/Analysis/DominatorInternals.h index c3f81e6649..2adbefba38 100644 --- a/include/llvm/Analysis/DominatorInternals.h +++ b/include/llvm/Analysis/DominatorInternals.h @@ -273,21 +273,24 @@ void Calculate(DominatorTreeBase<typename GraphTraits<NodeT>::NodeType>& DT, // which postdominates all real exits if there are multiple exit blocks. typename GraphT::NodeType* Root = DT.Roots.size() == 1 ? DT.Roots[0] : 0; - DT.DomTreeNodes[Root] = DT.RootNode = new DomTreeNode(Root, 0); + DT.DomTreeNodes[Root] = DT.RootNode = + new DomTreeNodeBase<typename GraphT::NodeType>(Root, 0); // Loop over all of the reachable blocks in the function... - for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) + for (typename FuncT::iterator I = F.begin(), E = F.end(); I != E; ++I) if (typename GraphT::NodeType* ImmDom = DT.getIDom(I)) { // Reachable block. - DomTreeNode *BBNode = DT.DomTreeNodes[I]; + DomTreeNodeBase<typename GraphT::NodeType> *BBNode = DT.DomTreeNodes[I]; if (BBNode) continue; // Haven't calculated this node yet? // Get or calculate the node for the immediate dominator - DomTreeNode *IDomNode = DT.getNodeForBlock(ImmDom); + DomTreeNodeBase<typename GraphT::NodeType> *IDomNode = + DT.getNodeForBlock(ImmDom); // Add a new tree node for this BasicBlock, and link it as a child of // IDomNode - DomTreeNode *C = new DomTreeNode(I, IDomNode); + DomTreeNodeBase<typename GraphT::NodeType> *C = + new DomTreeNodeBase<typename GraphT::NodeType>(I, IDomNode); DT.DomTreeNodes[I] = IDomNode->addChild(C); } diff --git a/include/llvm/Analysis/Dominators.h b/include/llvm/Analysis/Dominators.h index 82ebacb670..53d7e3d01f 100644 --- a/include/llvm/Analysis/Dominators.h +++ b/include/llvm/Analysis/Dominators.h @@ -132,6 +132,7 @@ private: }; EXTERN_TEMPLATE_INSTANTIATION(class DomTreeNodeBase<BasicBlock>); +EXTERN_TEMPLATE_INSTANTIATION(class DomTreeNodeBase<MachineBasicBlock>); template<class NodeT> static std::ostream &operator<<(std::ostream &o, @@ -156,7 +157,6 @@ static void PrintDomTree(const DomTreeNodeBase<NodeT> *N, std::ostream &o, } typedef DomTreeNodeBase<BasicBlock> DomTreeNode; -typedef DomTreeNodeBase<MachineBasicBlock> MachineDomTreeNode; //===----------------------------------------------------------------------===// /// DominatorTree - Calculate the immediate dominator tree for a function. @@ -607,6 +607,12 @@ protected: return I != IDoms.end() ? I->second : 0; } + inline void addRoot(NodeT* BB) { + // Unreachable block is not a root node. + if (!isa<UnreachableInst>(&BB->back())) + this->Roots.push_back(BB); + } + public: /// recalculate - compute a dominator tree for the given function template<class FT> @@ -615,9 +621,9 @@ public: reset(); // Initialize roots - this->Roots.push_back(&F.getEntryBlock()); - this->IDoms[&F.getEntryBlock()] = 0; - this->DomTreeNodes[&F.getEntryBlock()] = 0; + this->Roots.push_back(&F.front()); + this->IDoms[&F.front()] = 0; + this->DomTreeNodes[&F.front()] = 0; this->Vertex.push_back(0); Calculate<FT, NodeT*>(*this, F); @@ -627,13 +633,10 @@ public: reset(); // Reset from the last time we were run... // Initialize the roots list - for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) { - TerminatorInst *Insn = I->getTerminator(); - if (Insn->getNumSuccessors() == 0) { - // Unreachable block is not a root node. - if (!isa<UnreachableInst>(Insn)) - this->Roots.push_back(I); - } + for (typename FT::iterator I = F.begin(), E = F.end(); I != E; ++I) { + if (std::distance(GraphTraits<FT*>::child_begin(I), + GraphTraits<FT*>::child_end(I)) == 0) + addRoot(I); // Prepopulate maps so that we don't get iterator invalidation issues later. this->IDoms[I] = 0; diff --git a/include/llvm/CodeGen/MachineDominators.h b/include/llvm/CodeGen/MachineDominators.h index 621ba2f7a1..353c0e4301 100644 --- a/include/llvm/CodeGen/MachineDominators.h +++ b/include/llvm/CodeGen/MachineDominators.h @@ -24,7 +24,17 @@ namespace llvm { -void WriteAsOperand(std::ostream &, const MachineBasicBlock*, bool t) { } +inline void WriteAsOperand(std::ostream &, const MachineBasicBlock*, bool t) { } + +template<> +inline void DominatorTreeBase<MachineBasicBlock>::addRoot(MachineBasicBlock* MBB) { + this->Roots.push_back(MBB); +} + +EXTERN_TEMPLATE_INSTANTIATION(class DomTreeNodeBase<MachineBasicBlock>); +EXTERN_TEMPLATE_INSTANTIATION(class DominatorTreeBase<MachineBasicBlock>); + +typedef DomTreeNodeBase<MachineBasicBlock> MachineDomTreeNode; //===------------------------------------- /// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to @@ -60,7 +70,11 @@ public: return DT->getRootNode(); } - virtual bool runOnFunction(Function &F); + virtual bool runOnMachineFunction(MachineFunction &F) { + DT->recalculate(F); + + return false; + } virtual void getAnalysisUsage(AnalysisUsage &AU) const { AU.setPreservesAll(); diff --git a/lib/CodeGen/MachineDominators.cpp b/lib/CodeGen/MachineDominators.cpp new file mode 100644 index 0000000000..0a8a81b621 --- /dev/null +++ b/lib/CodeGen/MachineDominators.cpp @@ -0,0 +1,24 @@ +//===- MachineDominators.cpp - Machine Dominator Calculation --------------===// +// +// The LLVM Compiler Infrastructure +// +// This file was developed by the LLVM research group and is distributed under +// the University of Illinois Open Source License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file implements simple dominator construction algorithms for finding +// forward dominators on machine functions. +// +//===----------------------------------------------------------------------===// + +#include "llvm/CodeGen/MachineDominators.h" + +using namespace llvm; + +TEMPLATE_INSTANTIATION(class DomTreeNodeBase<MachineBasicBlock>); +TEMPLATE_INSTANTIATION(class DominatorTreeBase<MachineBasicBlock>); + +char MachineDominatorTree::ID = 0; +static RegisterPass<MachineDominatorTree> +E("machinedomtree", "MachineDominator Tree Construction", true);
\ No newline at end of file |