1/*
2 * Copyright (C) 2007 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17package com.android.dx.ssa;
18
19import com.android.dx.util.IntSet;
20import java.util.ArrayList;
21import java.util.BitSet;
22
23/**
24 * Calculates the dominance-frontiers of a method's basic blocks.
25 * Algorithm from "A Simple, Fast Dominance Algorithm" by Cooper,
26 * Harvey, and Kennedy; transliterated to Java.
27 */
28public class DomFront {
29    /** local debug flag */
30    private static final boolean DEBUG = false;
31
32    /** {@code non-null;} method being processed */
33    private final SsaMethod meth;
34
35    private final ArrayList<SsaBasicBlock> nodes;
36
37    private final DomInfo[] domInfos;
38
39    /**
40     * Dominance-frontier information for a single basic block.
41     */
42    public static class DomInfo {
43        /**
44         * {@code null-ok;} the dominance frontier set indexed by
45         * block index
46         */
47        public IntSet dominanceFrontiers;
48
49        /** {@code >= 0 after run();} the index of the immediate dominator */
50        public int idom = -1;
51    }
52
53    /**
54     * Constructs instance. Call {@link DomFront#run} to process.
55     *
56     * @param meth {@code non-null;} method to process
57     */
58    public DomFront(SsaMethod meth) {
59        this.meth = meth;
60        nodes = meth.getBlocks();
61
62        int szNodes = nodes.size();
63        domInfos = new DomInfo[szNodes];
64
65        for (int i = 0; i < szNodes; i++) {
66            domInfos[i] = new DomInfo();
67        }
68    }
69
70    /**
71     * Calculates the dominance frontier information for the method.
72     *
73     * @return {@code non-null;} an array of DomInfo structures
74     */
75    public DomInfo[] run() {
76        int szNodes = nodes.size();
77
78        if (DEBUG) {
79            for (int i = 0; i < szNodes; i++) {
80                SsaBasicBlock node = nodes.get(i);
81                System.out.println("pred[" + i + "]: "
82                        + node.getPredecessors());
83            }
84        }
85
86        Dominators methDom = Dominators.make(meth, domInfos, false);
87
88        if (DEBUG) {
89            for (int i = 0; i < szNodes; i++) {
90                DomInfo info = domInfos[i];
91                System.out.println("idom[" + i + "]: "
92                        + info.idom);
93            }
94        }
95
96        buildDomTree();
97
98        if (DEBUG) {
99            debugPrintDomChildren();
100        }
101
102        for (int i = 0; i < szNodes; i++) {
103            domInfos[i].dominanceFrontiers
104                    = SetFactory.makeDomFrontSet(szNodes);
105        }
106
107        calcDomFronts();
108
109        if (DEBUG) {
110            for (int i = 0; i < szNodes; i++) {
111                System.out.println("df[" + i + "]: "
112                        + domInfos[i].dominanceFrontiers);
113            }
114        }
115
116        return domInfos;
117    }
118
119    private void debugPrintDomChildren() {
120        int szNodes = nodes.size();
121
122        for (int i = 0; i < szNodes; i++) {
123            SsaBasicBlock node = nodes.get(i);
124            StringBuffer sb = new StringBuffer();
125
126            sb.append('{');
127            boolean comma = false;
128            for (SsaBasicBlock child : node.getDomChildren()) {
129                if (comma) {
130                    sb.append(',');
131                }
132                sb.append(child);
133                comma = true;
134            }
135            sb.append('}');
136
137            System.out.println("domChildren[" + node + "]: "
138                    + sb);
139        }
140    }
141
142    /**
143     * The dominators algorithm leaves us knowing who the immediate dominator
144     * is for each node. This sweeps the node list and builds the proper
145     * dominance tree.
146     */
147    private void buildDomTree() {
148        int szNodes = nodes.size();
149
150        for (int i = 0; i < szNodes; i++) {
151            DomInfo info = domInfos[i];
152
153            if (info.idom == -1) continue;
154
155            SsaBasicBlock domParent = nodes.get(info.idom);
156            domParent.addDomChild(nodes.get(i));
157        }
158    }
159
160    /**
161     * Calculates the dominance-frontier set.
162     * from "A Simple, Fast Dominance Algorithm" by Cooper,
163     * Harvey, and Kennedy; transliterated to Java.
164     */
165    private void calcDomFronts() {
166        int szNodes = nodes.size();
167
168        for (int b = 0; b < szNodes; b++) {
169            SsaBasicBlock nb = nodes.get(b);
170            DomInfo nbInfo = domInfos[b];
171            BitSet pred = nb.getPredecessors();
172
173            if (pred.cardinality() > 1) {
174                for (int i = pred.nextSetBit(0); i >= 0;
175                     i = pred.nextSetBit(i + 1)) {
176
177                    for (int runnerIndex = i;
178                         runnerIndex != nbInfo.idom; /* empty */) {
179                        /*
180                         * We can stop if we hit a block we already
181                         * added label to, since we must be at a part
182                         * of the dom tree we have seen before.
183                         */
184                        if (runnerIndex == -1) break;
185
186                        DomInfo runnerInfo = domInfos[runnerIndex];
187
188                        if (runnerInfo.dominanceFrontiers.has(b)) {
189                            break;
190                        }
191
192                        // Add b to runner's dominance frontier set.
193                        runnerInfo.dominanceFrontiers.add(b);
194                        runnerIndex = runnerInfo.idom;
195                    }
196                }
197            }
198        }
199    }
200}
201