-// Postdominator set construction. This converts the specified function to only
-// have a single exit node (return stmt), then calculates the post dominance
-// sets for the function.
-//
-bool PostDominatorSet::runOnFunction(Function &F) {
- Doms.clear(); // Reset from the last time we were run...
- // Since we require that the unify all exit nodes pass has been run, we know
- // that there can be at most one return instruction in the function left.
- // Get it.
- //
- Root = getAnalysis<UnifyFunctionExitNodes>().getExitNode();
-
- if (Root == 0) { // No exit node for the function? Postdomsets are all empty
- for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI)
- Doms[FI] = DomSetType();
- return false;
- }
-
- bool Changed;
- do {
- Changed = false;
-
- set<const BasicBlock*> Visited;
- DomSetType WorkingSet;
- idf_iterator<BasicBlock*> It = idf_begin(Root), End = idf_end(Root);
- for ( ; It != End; ++It) {
- BasicBlock *BB = *It;
- succ_iterator PI = succ_begin(BB), PEnd = succ_end(BB);
- if (PI != PEnd) { // Is there SOME predecessor?
- // Loop until we get to a successor 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 successor sets
- DomSetType &PredSet = Doms[*PI];
- if (PredSet.size())
- set_intersect(WorkingSet, PredSet);
- }
- } else if (BB != Root) {
- // If this isn't the root basic block and it has no successors, it must
- // be an non-returning block. Fib a bit by saying that the root node
- // postdominates this unreachable node. This isn't exactly true,
- // because there is no path from this node to the root node, but it is
- // sorta true because any paths to the exit node would have to go
- // through this node.
- //
- // This allows for postdominator properties to be built for code that
- // doesn't return in a reasonable manner.
- //
- WorkingSet = Doms[Root];
- }
-
- 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);