-//===----------------------------------------------------------------------===//
-/// DominanceFrontierBase - Common base class for computing forward and inverse
-/// dominance frontiers for a function.
-///
-class DominanceFrontierBase : public FunctionPass {
-public:
- typedef std::set<BasicBlock*> DomSetType; // Dom set for a bb
- typedef std::map<BasicBlock*, DomSetType> DomSetMapType; // Dom set map
-protected:
- DomSetMapType Frontiers;
- std::vector<BasicBlock*> Roots;
- const bool IsPostDominators;
-
-public:
- DominanceFrontierBase(void *ID, bool isPostDom)
- : FunctionPass(ID), IsPostDominators(isPostDom) {}
-
- /// getRoots - Return the root blocks of the current CFG. This may include
- /// multiple blocks if we are computing post dominators. For forward
- /// dominators, this will always be a single block (the entry node).
- ///
- inline const std::vector<BasicBlock*> &getRoots() const { return Roots; }
-
- /// isPostDominator - Returns true if analysis based of postdoms
- ///
- bool isPostDominator() const { return IsPostDominators; }
-
- virtual void releaseMemory() { Frontiers.clear(); }
-
- // Accessor interface:
- typedef DomSetMapType::iterator iterator;
- typedef DomSetMapType::const_iterator const_iterator;
- iterator begin() { return Frontiers.begin(); }
- const_iterator begin() const { return Frontiers.begin(); }
- iterator end() { return Frontiers.end(); }
- const_iterator end() const { return Frontiers.end(); }
- iterator find(BasicBlock *B) { return Frontiers.find(B); }
- const_iterator find(BasicBlock *B) const { return Frontiers.find(B); }
-
- iterator addBasicBlock(BasicBlock *BB, const DomSetType &frontier) {
- assert(find(BB) == end() && "Block already in DominanceFrontier!");
- return Frontiers.insert(std::make_pair(BB, frontier)).first;
- }
-
- /// removeBlock - Remove basic block BB's frontier.
- void removeBlock(BasicBlock *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);
- }
-
- void addToFrontier(iterator I, BasicBlock *Node) {
- assert(I != end() && "BB is not in DominanceFrontier!");
- I->second.insert(Node);
- }
-
- void removeFromFrontier(iterator I, BasicBlock *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);
- }
-
- /// compareDomSet - Return false if two domsets match. Otherwise
- /// return true;
- bool compareDomSet(DomSetType &DS1, const DomSetType &DS2) const {
- std::set<BasicBlock *> tmpSet;
- for (DomSetType::const_iterator I = DS2.begin(),
- E = DS2.end(); I != E; ++I)
- tmpSet.insert(*I);
-
- for (DomSetType::const_iterator I = DS1.begin(),
- E = DS1.end(); I != E; ) {
- BasicBlock *Node = *I++;
-
- if (tmpSet.erase(Node) == 0)
- // Node is in DS1 but not 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;
- }
-
- /// compare - Return true if the other dominance frontier base matches
- /// this dominance frontier base. Otherwise return false.
- bool compare(DominanceFrontierBase &Other) const {
- DomSetMapType tmpFrontiers;
- for (DomSetMapType::const_iterator I = Other.begin(),
- E = Other.end(); I != E; ++I)
- tmpFrontiers.insert(std::make_pair(I->first, I->second));
-
- for (DomSetMapType::iterator I = tmpFrontiers.begin(),
- E = tmpFrontiers.end(); I != E; ) {
- BasicBlock *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;
- }
-
- /// print - Convert to human readable form
- ///
- virtual void print(raw_ostream &OS, const Module* = 0) const;
-};
-
-
-//===-------------------------------------
-/// DominanceFrontier Class - Concrete subclass of DominanceFrontierBase that is
-/// used to compute a forward dominator frontiers.
-///
-class DominanceFrontier : public DominanceFrontierBase {
-public:
- static char ID; // Pass ID, replacement for typeid
- DominanceFrontier() :
- DominanceFrontierBase(&ID, false) {}
-
- BasicBlock *getRoot() const {
- assert(Roots.size() == 1 && "Should always have entry node!");
- return Roots[0];
- }
-
- virtual bool runOnFunction(Function &) {
- Frontiers.clear();
- DominatorTree &DT = getAnalysis<DominatorTree>();
- Roots = DT.getRoots();
- assert(Roots.size() == 1 && "Only one entry block for forward domfronts!");
- calculate(DT, DT[Roots[0]]);
- return false;
- }
-
- virtual void verifyAnalysis() const;
-
- virtual void getAnalysisUsage(AnalysisUsage &AU) const {
- AU.setPreservesAll();
- AU.addRequired<DominatorTree>();
- }
-
- /// splitBlock - BB is split and now it has one successor. Update dominance
- /// frontier to reflect this change.
- void splitBlock(BasicBlock *BB);
-
- /// BasicBlock BB's new dominator is NewBB. Update BB's dominance frontier
- /// to reflect this change.
- void changeImmediateDominator(BasicBlock *BB, BasicBlock *NewBB,
- DominatorTree *DT) {
- // NewBB is now dominating BB. Which means BB's dominance
- // frontier is now part of NewBB's dominance frontier. However, BB
- // itself is not member of NewBB's dominance frontier.
- DominanceFrontier::iterator NewDFI = find(NewBB);
- DominanceFrontier::iterator DFI = find(BB);
- // If BB was an entry block then its frontier is empty.
- if (DFI == end())
- return;
- DominanceFrontier::DomSetType BBSet = DFI->second;
- for (DominanceFrontier::DomSetType::iterator BBSetI = BBSet.begin(),
- BBSetE = BBSet.end(); BBSetI != BBSetE; ++BBSetI) {
- BasicBlock *DFMember = *BBSetI;
- // Insert only if NewBB dominates DFMember.
- if (!DT->dominates(NewBB, DFMember))
- NewDFI->second.insert(DFMember);
- }
- NewDFI->second.erase(BB);
- }
-
- const DomSetType &calculate(const DominatorTree &DT,
- const DomTreeNode *Node);
-};
-
-