FileDocCategorySizeDatePackage
Dominators.javaAPI DocAndroid 1.5 API8714Wed May 06 22:41:02 BST 2009com.android.dx.ssa

Dominators

public final class Dominators extends Object
This class computes dominator and post-dominator information using the Lengauer-Tarjan method. See A Fast Algorithm for Finding Dominators in a Flowgraph T. Lengauer & R. Tarjan, ACM TOPLAS July 1979, pgs 121-141. This implementation runs in time O(n log n). The time bound could be changed to O(n * ack(n)) with a small change to the link and eval, and an addition of a child field to the DFS info. In reality, the constant overheads are high enough that the current method is faster in all but the strangest artificially constructed examples. The basic idea behind this algorithm is to perform a DFS walk, keeping track of various info about parents. We then use this info to calculate the dominators, using union-find structures to link together the DFS info, then finally evaluate the union-find results to get the dominators. This implementation is m log n because it does not perform union by rank to keep the union-find tree balanced.

Fields Summary
private boolean
postdom
private ArrayList
blocks
private DFSInfo[]
info
Indexed by basic block index
private ArrayList
vertex
private DomFront.DomInfo[]
domInfos
Constructors Summary
public Dominators(DomFront.DomInfo[] domInfos, boolean postdom)

param
postdom true for postdom information, false for normal dom info

        this.domInfos = domInfos;
        this.postdom = postdom;
Methods Summary
private voidcompress(SsaBasicBlock in)
Performs path compress on the DFS info.

param
in Basic block whose DFS info we are path compressing.

        DFSInfo bbInfo = info[in.getIndex()];
        DFSInfo ancestorbbInfo = info[bbInfo.ancestor.getIndex()];

        if (ancestorbbInfo.ancestor != null) {
            ArrayList<SsaBasicBlock> worklist = new ArrayList<SsaBasicBlock>();
            HashSet<SsaBasicBlock> visited = new HashSet<SsaBasicBlock>();
            worklist.add(in);
            
            while (!worklist.isEmpty()) {
                int wsize = worklist.size();
                SsaBasicBlock v = worklist.get(wsize - 1);
                DFSInfo vbbInfo = info[v.getIndex()];
                SsaBasicBlock vAncestor = vbbInfo.ancestor;
                DFSInfo vabbInfo = info[vAncestor.getIndex()];

                // Make sure we process our ancestor before ourselves.
                if (visited.add(vAncestor) && vabbInfo.ancestor != null) {
                    worklist.add(vAncestor);
                    continue;
                }
                worklist.remove(wsize - 1);

                // Update based on ancestor info
                if (vabbInfo.ancestor == null) {
                    continue;
                }
                SsaBasicBlock vAncestorRep = vabbInfo.rep;
                SsaBasicBlock vRep = vbbInfo.rep;
                if (info[vAncestorRep.getIndex()].semidom
                        < info[vRep.getIndex()].semidom) {
                    vbbInfo.rep = vAncestorRep;
                }
                vbbInfo.ancestor = vabbInfo.ancestor;
            }
        }
private SsaBasicBlockeval(SsaBasicBlock v)

        DFSInfo bbInfo = info[v.getIndex()];
        if (bbInfo.ancestor == null) {
            return v;
        }
        compress(v);
        return bbInfo.rep;
private java.util.BitSetgetPreds(SsaBasicBlock block)

        if (postdom) {
            return block.getSuccessors();
        } else {
            return block.getPredecessors();
        }
private java.util.BitSetgetSuccs(SsaBasicBlock block)

        if (postdom) {
            return block.getPredecessors();
        } else {
            return block.getSuccessors();
        }
public voidrun(SsaMethod meth)
Performs dominator/post-dominator calculation for the control flow graph.

param
meth Method to analyze


        this.blocks = meth.getBlocks();
        this.info = new DFSInfo[blocks.size() + 2];
        this.vertex = new ArrayList<SsaBasicBlock>();
        SsaBasicBlock root = postdom
                ? meth.getExitBlock() : meth.getEntryBlock();

        if (root != null) {
            vertex.add(root);
            domInfos[root.getIndex()].idom = root.getIndex();
        }
        
        // First we perform a DFS numbering of the blocks, by numbering the dfs
        // tree roots

        DfsWalker walker = new DfsWalker();
        meth.forEachBlockDepthFirst(postdom, walker);

        // the largest semidom number assigned
        int dfsMax = vertex.size() - 1;

        // Now calculate semidominators.
        for (int i = dfsMax; i >= 2; --i) {
            SsaBasicBlock w = vertex.get(i);
            DFSInfo wInfo = info[w.getIndex()];

            BitSet preds = getPreds(w);
            for (int j = preds.nextSetBit(0);
                    j >= 0;
                    j = preds.nextSetBit(j + 1)) {
                SsaBasicBlock predBlock = blocks.get(j);
                DFSInfo predInfo = info[predBlock.getIndex()];
                // PredInfo may not exist in case the predecessor is not
                // reachable
                if (predInfo != null) {
                    int predSemidom = info[eval(predBlock).getIndex()].semidom;
                    if (predSemidom < wInfo.semidom) {
                        wInfo.semidom = predSemidom;
                    }
                }
            }
            info[vertex.get(wInfo.semidom).getIndex()].bucket.add(w);

            // Normally we would call link here, but in our  m log n
            // implementation this is equivalent to the following single line
            wInfo.ancestor = wInfo.parent;

            // Implicity define idom for each vertex
            ArrayList<SsaBasicBlock> wParentBucket;
            wParentBucket = info[wInfo.parent.getIndex()].bucket;

            while (!wParentBucket.isEmpty()) {
                int lastItem = wParentBucket.size() - 1;
                SsaBasicBlock last = wParentBucket.remove(lastItem);
                SsaBasicBlock U = eval(last);
                if (info[U.getIndex()].semidom
                        < info[last.getIndex()].semidom) {
                    domInfos[last.getIndex()].idom = U.getIndex();
                } else {
                    domInfos[last.getIndex()].idom = wInfo.parent.getIndex();
                }
            }
        }
        // Now explicitly define the immediate dominator of each vertex
        for (int i =  2; i <= dfsMax; ++i) {
            SsaBasicBlock w = vertex.get(i);
            if (domInfos[w.getIndex()].idom
                    != vertex.get(info[w.getIndex()].semidom).getIndex()) {
                domInfos[w.getIndex()].idom
                        = domInfos[domInfos[w.getIndex()].idom].idom;
            }
        }