FileDocCategorySizeDatePackage
DomFront.javaAPI DocAndroid 1.5 API5761Wed May 06 22:41:02 BST 2009com.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
private final SsaMethod
meth
private final ArrayList
nodes
private final DomInfo[]
domInfos
Constructors Summary
public DomFront(SsaMethod meth)
Constructs instance. Call {@link DomFront#run} to process.

param
meth

    

                   
       
        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];
            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
                            ;) {
                        // 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.
                        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
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 = new Dominators(domInfos, false);
        methDom.run(meth);

        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;