-// set_intersect - Identical to set_intersection, except that it works on
-// set<>'s and is nicer to use. Functionally, this iterates through S1,
-// removing elements that are not contained in S2.
-//
-template <class Ty, class Ty2>
-void set_intersect(set<Ty> &S1, const set<Ty2> &S2) {
- for (typename set<Ty>::iterator I = S1.begin(); I != S1.end();) {
- const Ty &E = *I;
- ++I;
- if (!S2.count(E)) S1.erase(E); // Erase element if not in S2
- }
-}
-
-//===----------------------------------------------------------------------===//
-// DominatorBase Implementation
-//===----------------------------------------------------------------------===//
-
-bool cfg::DominatorBase::isPostDominator() const {
- return Root != Root->getParent()->front();
-}
-
-
-//===----------------------------------------------------------------------===//
-// DominatorSet Implementation
-//===----------------------------------------------------------------------===//
-
-// DominatorSet ctor - Build either the dominator set or the post-dominator
-// set for a method...
-//
-cfg::DominatorSet::DominatorSet(const Method *M) : DominatorBase(M->front()) {
- calcForwardDominatorSet(M);
-}
-
-// calcForwardDominatorSet - This method calculates the forward dominator sets
-// for the specified method.
-//
-void cfg::DominatorSet::calcForwardDominatorSet(const Method *M) {
- assert(Root && M && "Can't build dominator set of null method!");
- bool Changed;
- do {
- Changed = false;
-
- DomSetType WorkingSet;
- df_const_iterator It = df_begin(M), End = df_end(M);
- for ( ; It != End; ++It) {
- const BasicBlock *BB = *It;
- pred_const_iterator PI = pred_begin(BB), PEnd = pred_end(BB);
- if (PI != PEnd) { // Is there SOME predecessor?
- // Loop until we get to a predecessor that has had it's dom set filled
- // in at least once. We are guaranteed to have this because we are
- // traversing the graph in DFO and have handled start nodes specially.
- //
- while (Doms[*PI].size() == 0) ++PI;
- WorkingSet = Doms[*PI];
-
- for (++PI; PI != PEnd; ++PI) { // Intersect all of the predecessor sets
- DomSetType &PredSet = Doms[*PI];
- if (PredSet.size())
- set_intersect(WorkingSet, PredSet);
- }
- }
-
- WorkingSet.insert(BB); // A block always dominates itself
- DomSetType &BBSet = Doms[BB];
- if (BBSet != WorkingSet) {
- BBSet.swap(WorkingSet); // Constant time operation!
- Changed = true; // The sets changed.
- }
- WorkingSet.clear(); // Clear out the set for next iteration
- }
- } while (Changed);
-}