FileDocCategorySizeDatePackage
DomFront.javaAPI DocAndroid 5.1 API5916Thu Mar 12 22:18:30 GMT 2015com.android.dx.ssa

DomFront

public class DomFront extends Object
Calculates the dominance-frontiers of a methot's basic blocks. Algorithm from "A Simple, Fast Dominance Algorithm" by Cooper, Harvey, and Kennedy; transliterated to Java.

Fields Summary
private static boolean
DEBUG
local debug flag
private final SsaMethod
meth
{@code non-null;} method being processed
private final ArrayList
nodes
private final DomInfo[]
domInfos
Constructors Summary
public DomFront(SsaMethod meth)
Constructs instance. Call {@link DomFront#run} to process.

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

    

                       
       
        this.meth = meth;
        nodes = meth.getBlocks();

        int szNodes = nodes.size();
        domInfos = new DomInfo[szNodes];

        for (int i = 0; i < szNodes; i++) {
            domInfos[i] = new DomInfo();
        }
Methods Summary
private voidbuildDomTree()
The dominators algorithm leaves us knowing who the immediate dominator is for each node. This sweeps the node list and builds the proper dominance tree.

        int szNodes = nodes.size();

        for (int i = 0; i < szNodes; i++) {
            DomInfo info = domInfos[i];

            if (info.idom == -1) continue;

            SsaBasicBlock domParent = nodes.get(info.idom);
            domParent.addDomChild(nodes.get(i));
        }
private voidcalcDomFronts()
Calculates the dominance-frontier set. from "A Simple, Fast Dominance Algorithm" by Cooper, Harvey, and Kennedy; transliterated to Java.

        int szNodes = nodes.size();

        for (int b = 0; b < szNodes; b++) {
            SsaBasicBlock nb = nodes.get(b);
            DomInfo nbInfo = domInfos[b];
            BitSet pred = nb.getPredecessors();

            if (pred.cardinality() > 1) {
                for (int i = pred.nextSetBit(0); i >= 0;
                     i = pred.nextSetBit(i + 1)) {

                    for (int runnerIndex = i;
                         runnerIndex != nbInfo.idom; /* empty */) {
                        /*
                         * We can stop if we hit a block we already
                         * added label to, since we must be at a part
                         * of the dom tree we have seen before.
                         */
                        if (runnerIndex == -1) break;

                        DomInfo runnerInfo = domInfos[runnerIndex];

                        if (runnerInfo.dominanceFrontiers.has(b)) {
                            break;
                        }

                        // Add b to runner's dominance frontier set.
                        runnerInfo.dominanceFrontiers.add(b);
                        runnerIndex = runnerInfo.idom;
                    }
                }
            }
        }
private voiddebugPrintDomChildren()

        int szNodes = nodes.size();

        for (int i = 0; i < szNodes; i++) {
            SsaBasicBlock node = nodes.get(i);
            StringBuffer sb = new StringBuffer();

            sb.append('{");
            boolean comma = false;
            for (SsaBasicBlock child : node.getDomChildren()) {
                if (comma) {
                    sb.append(',");
                }
                sb.append(child);
                comma = true;
            }
            sb.append('}");

            System.out.println("domChildren[" + node + "]: "
                    + sb);
        }
public com.android.dx.ssa.DomFront$DomInfo[]run()
Calculates the dominance frontier information for the method.

return
{@code non-null;} an array of DomInfo structures

        int szNodes = nodes.size();

        if (DEBUG) {
            for (int i = 0; i < szNodes; i++) {
                SsaBasicBlock node = nodes.get(i);
                System.out.println("pred[" + i + "]: "
                        + node.getPredecessors());
            }
        }

        Dominators methDom = Dominators.make(meth, domInfos, false);

        if (DEBUG) {
            for (int i = 0; i < szNodes; i++) {
                DomInfo info = domInfos[i];
                System.out.println("idom[" + i + "]: "
                        + info.idom);
            }
        }

        buildDomTree();

        if (DEBUG) {
            debugPrintDomChildren();
        }

        for (int i = 0; i < szNodes; i++) {
            domInfos[i].dominanceFrontiers
                    = SetFactory.makeDomFrontSet(szNodes);
        }

        calcDomFronts();

        if (DEBUG) {
            for (int i = 0; i < szNodes; i++) {
                System.out.println("df[" + i + "]: "
                        + domInfos[i].dominanceFrontiers);
            }
        }

        return domInfos;