FileDocCategorySizeDatePackage
Dominators.javaAPI DocAndroid 5.1 API9870Thu Mar 12 22:18:30 GMT 2015com.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 final boolean
postdom
private final SsaMethod
meth
private final ArrayList
blocks
private final DFSInfo[]
info
indexed by basic block index
private final ArrayList
vertex
private final DomFront.DomInfo[]
domInfos
{@code non-null;} the raw dominator info
Constructors Summary
private Dominators(SsaMethod meth, DomFront.DomInfo[] domInfos, boolean postdom)
Constructs an instance.

param
meth {@code non-null;} method to process
param
domInfos {@code non-null;} the raw dominator info
param
postdom true for postdom information, false for normal dom info

        this.meth = meth;
        this.domInfos = domInfos;
        this.postdom = postdom;
        this.blocks = meth.getBlocks();
        this.info = new DFSInfo[blocks.size() + 2];
        this.vertex = new ArrayList<SsaBasicBlock>();
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 static com.android.dx.ssa.Dominatorsmake(SsaMethod meth, DomFront.DomInfo[] domInfos, boolean postdom)
Constructs a fully-initialized instance. (This method exists so as to avoid calling a large amount of code in the constructor.)

param
meth {@code non-null;} method to process
param
domInfos {@code non-null;} the raw dominator info
param
postdom true for postdom information, false for normal dom info

        Dominators result = new Dominators(meth, domInfos, postdom);

        result.run();
        return result;
private voidrun()
Performs dominator/post-dominator calculation for the control flow graph.

param
meth {@code non-null;} method to analyze

        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 O(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;
            }
        }