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