diff options
Diffstat (limited to 'include/llvm/Analysis/DominanceFrontierImpl.h')
| -rw-r--r-- | include/llvm/Analysis/DominanceFrontierImpl.h | 226 |
1 files changed, 226 insertions, 0 deletions
diff --git a/include/llvm/Analysis/DominanceFrontierImpl.h b/include/llvm/Analysis/DominanceFrontierImpl.h new file mode 100644 index 0000000..735bfb8 --- /dev/null +++ b/include/llvm/Analysis/DominanceFrontierImpl.h @@ -0,0 +1,226 @@ +//===- llvm/Analysis/DominanceFrontier.h - Dominator Frontiers --*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This is the generic implementation of the DominanceFrontier class, which +// calculate and holds the dominance frontier for a function for. +// +// This should be considered deprecated, don't add any more uses of this data +// structure. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ANALYSIS_DOMINANCEFRONTIERIMPL_H +#define LLVM_ANALYSIS_DOMINANCEFRONTIERIMPL_H + +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/Support/Debug.h" + +namespace llvm { + +namespace { +template <class BlockT> +class DFCalculateWorkObject { +public: + typedef DomTreeNodeBase<BlockT> DomTreeNodeT; + + DFCalculateWorkObject(BlockT *B, BlockT *P, const DomTreeNodeT *N, + const DomTreeNodeT *PN) + : currentBB(B), parentBB(P), Node(N), parentNode(PN) {} + BlockT *currentBB; + BlockT *parentBB; + const DomTreeNodeT *Node; + const DomTreeNodeT *parentNode; +}; +} + +template <class BlockT> +void DominanceFrontierBase<BlockT>::removeBlock(BlockT *BB) { + assert(find(BB) != end() && "Block is not in DominanceFrontier!"); + for (iterator I = begin(), E = end(); I != E; ++I) + I->second.erase(BB); + Frontiers.erase(BB); +} + +template <class BlockT> +void DominanceFrontierBase<BlockT>::addToFrontier(iterator I, + BlockT *Node) { + assert(I != end() && "BB is not in DominanceFrontier!"); + assert(I->second.count(Node) && "Node is not in DominanceFrontier of BB"); + I->second.erase(Node); +} + +template <class BlockT> +void DominanceFrontierBase<BlockT>::removeFromFrontier(iterator I, + BlockT *Node) { + assert(I != end() && "BB is not in DominanceFrontier!"); + assert(I->second.count(Node) && "Node is not in DominanceFrontier of BB"); + I->second.erase(Node); +} + +template <class BlockT> +bool DominanceFrontierBase<BlockT>::compareDomSet(DomSetType &DS1, + const DomSetType &DS2) const { + std::set<BlockT *> tmpSet; + for (BlockT *BB : DS2) + tmpSet.insert(BB); + + for (typename DomSetType::const_iterator I = DS1.begin(), E = DS1.end(); + I != E;) { + BlockT *Node = *I++; + + if (tmpSet.erase(Node) == 0) + // Node is in DS1 but tnot in DS2. + return true; + } + + if (!tmpSet.empty()) { + // There are nodes that are in DS2 but not in DS1. + return true; + } + + // DS1 and DS2 matches. + return false; +} + +template <class BlockT> +bool DominanceFrontierBase<BlockT>::compare( + DominanceFrontierBase<BlockT> &Other) const { + DomSetMapType tmpFrontiers; + for (typename DomSetMapType::const_iterator I = Other.begin(), + E = Other.end(); + I != E; ++I) + tmpFrontiers.insert(std::make_pair(I->first, I->second)); + + for (typename DomSetMapType::iterator I = tmpFrontiers.begin(), + E = tmpFrontiers.end(); + I != E;) { + BlockT *Node = I->first; + const_iterator DFI = find(Node); + if (DFI == end()) + return true; + + if (compareDomSet(I->second, DFI->second)) + return true; + + ++I; + tmpFrontiers.erase(Node); + } + + if (!tmpFrontiers.empty()) + return true; + + return false; +} + +template <class BlockT> +void DominanceFrontierBase<BlockT>::print(raw_ostream &OS) const { + for (const_iterator I = begin(), E = end(); I != E; ++I) { + OS << " DomFrontier for BB "; + if (I->first) + I->first->printAsOperand(OS, false); + else + OS << " <<exit node>>"; + OS << " is:\t"; + + const std::set<BlockT *> &BBs = I->second; + + for (const BlockT *BB : BBs) { + OS << ' '; + if (BB) + BB->printAsOperand(OS, false); + else + OS << "<<exit node>>"; + } + OS << '\n'; + } +} + +#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) +template <class BlockT> +void DominanceFrontierBase<BlockT>::dump() const { + print(dbgs()); +} +#endif + +template <class BlockT> +const typename ForwardDominanceFrontierBase<BlockT>::DomSetType & +ForwardDominanceFrontierBase<BlockT>::calculate(const DomTreeT &DT, + const DomTreeNodeT *Node) { + BlockT *BB = Node->getBlock(); + DomSetType *Result = nullptr; + + std::vector<DFCalculateWorkObject<BlockT>> workList; + SmallPtrSet<BlockT *, 32> visited; + + workList.push_back(DFCalculateWorkObject<BlockT>(BB, nullptr, Node, nullptr)); + do { + DFCalculateWorkObject<BlockT> *currentW = &workList.back(); + assert(currentW && "Missing work object."); + + BlockT *currentBB = currentW->currentBB; + BlockT *parentBB = currentW->parentBB; + const DomTreeNodeT *currentNode = currentW->Node; + const DomTreeNodeT *parentNode = currentW->parentNode; + assert(currentBB && "Invalid work object. Missing current Basic Block"); + assert(currentNode && "Invalid work object. Missing current Node"); + DomSetType &S = this->Frontiers[currentBB]; + + // Visit each block only once. + if (visited.insert(currentBB).second) { + // Loop over CFG successors to calculate DFlocal[currentNode] + for (auto SI = BlockTraits::child_begin(currentBB), + SE = BlockTraits::child_end(currentBB); + SI != SE; ++SI) { + // Does Node immediately dominate this successor? + if (DT[*SI]->getIDom() != currentNode) + S.insert(*SI); + } + } + + // At this point, S is DFlocal. Now we union in DFup's of our children... + // Loop through and visit the nodes that Node immediately dominates (Node's + // children in the IDomTree) + bool visitChild = false; + for (typename DomTreeNodeT::const_iterator NI = currentNode->begin(), + NE = currentNode->end(); + NI != NE; ++NI) { + DomTreeNodeT *IDominee = *NI; + BlockT *childBB = IDominee->getBlock(); + if (visited.count(childBB) == 0) { + workList.push_back(DFCalculateWorkObject<BlockT>( + childBB, currentBB, IDominee, currentNode)); + visitChild = true; + } + } + + // If all children are visited or there is any child then pop this block + // from the workList. + if (!visitChild) { + if (!parentBB) { + Result = &S; + break; + } + + typename DomSetType::const_iterator CDFI = S.begin(), CDFE = S.end(); + DomSetType &parentSet = this->Frontiers[parentBB]; + for (; CDFI != CDFE; ++CDFI) { + if (!DT.properlyDominates(parentNode, DT[*CDFI])) + parentSet.insert(*CDFI); + } + workList.pop_back(); + } + + } while (!workList.empty()); + + return *Result; +} + +} // End llvm namespace + +#endif |