xref: /dalvik/dx/src/com/android/dx/ssa/DomFront.java

/*
 * Copyright (C) 2007 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package com.android.dx.ssa;

import com.android.dx.util.IntSet;
import com.android.dx.util.BitIntSet;
import com.android.dx.util.ListIntSet;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.BitSet;

/**
 * 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.
 */
public class DomFront {
    /** local debug flag */
    private static boolean DEBUG = false;

    /** {@code non-null;} method being processed */
    private final SsaMethod meth;

    private final ArrayList<SsaBasicBlock> nodes;

    private final DomInfo[] domInfos;

    /**
     * Dominance-frontier information for a single basic block.
     */
    public static class DomInfo {
        /**
         * {@code null-ok;} the dominance frontier set indexed by
         * block index
         */
        public IntSet dominanceFrontiers;

        /** {@code >= 0 after run();} the index of the immediate dominator */
        public int idom = -1;
    }

    /**
     * Constructs instance. Call {@link DomFront#run} to process.
     *
     * @param meth {@code non-null;} method to process
     */
    public DomFront(SsaMethod 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();
        }
    }

    /**
     * Calculates the dominance frontier information for the method.
     *
     * @return {@code non-null;} an array of DomInfo structures
     */
    public DomInfo[] run() {
        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;
    }

    private void debugPrintDomChildren() {
        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);
        }
    }

    /**
     * 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.
     */
    private void buildDomTree() {
        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));
        }
    }

    /**
     * Calculates the dominance-frontier set.
     * from "A Simple, Fast Dominance Algorithm" by Cooper,
     * Harvey, and Kennedy; transliterated to Java.
     */
    private void calcDomFronts() {
        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;
                    }
                }
            }
        }
    }
}