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 java.util.ArrayList;
20import java.util.BitSet;
21import java.util.HashSet;
22
23/**
24 * This class computes dominator and post-dominator information using the
25 * Lengauer-Tarjan method.
26 *
27 * See A Fast Algorithm for Finding Dominators in a Flowgraph
28 * T. Lengauer & R. Tarjan, ACM TOPLAS July 1979, pgs 121-141.
29 *
30 * This implementation runs in time O(n log n).  The time bound
31 * could be changed to O(n * ack(n)) with a small change to the link and eval,
32 * and an addition of a child field to the DFS info. In reality, the constant
33 * overheads are high enough that the current method is faster in all but the
34 * strangest artificially constructed examples.
35 *
36 * The basic idea behind this algorithm is to perform a DFS walk, keeping track
37 * of various info about parents.  We then use this info to calculate the
38 * dominators, using union-find structures to link together the DFS info,
39 * then finally evaluate the union-find results to get the dominators.
40 * This implementation is m log n because it does not perform union by
41 * rank to keep the union-find tree balanced.
42 */
43public final class Dominators {
44    /* postdom is true if we want post dominators */
45    private final boolean postdom;
46
47    /* {@code non-null;} method being processed */
48    private final SsaMethod meth;
49
50    /* Method's basic blocks. */
51    private final ArrayList<SsaBasicBlock> blocks;
52
53    /** indexed by basic block index */
54    private final DFSInfo[] info;
55
56    private final ArrayList<SsaBasicBlock> vertex;
57
58    /** {@code non-null;} the raw dominator info */
59    private final DomFront.DomInfo domInfos[];
60
61    /**
62     * Constructs an instance.
63     *
64     * @param meth {@code non-null;} method to process
65     * @param domInfos {@code non-null;} the raw dominator info
66     * @param postdom true for postdom information, false for normal dom info
67     */
68    private Dominators(SsaMethod meth, DomFront.DomInfo[] domInfos,
69            boolean postdom) {
70        this.meth = meth;
71        this.domInfos = domInfos;
72        this.postdom = postdom;
73        this.blocks = meth.getBlocks();
74        this.info = new DFSInfo[blocks.size() + 2];
75        this.vertex = new ArrayList<SsaBasicBlock>();
76    }
77
78    /**
79     * Constructs a fully-initialized instance. (This method exists so as
80     * to avoid calling a large amount of code in the constructor.)
81     *
82     * @param meth {@code non-null;} method to process
83     * @param domInfos {@code non-null;} the raw dominator info
84     * @param postdom true for postdom information, false for normal dom info
85     */
86    public static Dominators make(SsaMethod meth, DomFront.DomInfo[] domInfos,
87            boolean postdom) {
88        Dominators result = new Dominators(meth, domInfos, postdom);
89
90        result.run();
91        return result;
92    }
93
94    private BitSet getSuccs(SsaBasicBlock block) {
95        if (postdom) {
96            return block.getPredecessors();
97        } else {
98            return block.getSuccessors();
99        }
100    }
101
102    private BitSet getPreds(SsaBasicBlock block) {
103        if (postdom) {
104            return block.getSuccessors();
105        } else {
106            return block.getPredecessors();
107        }
108    }
109
110    /**
111     * Performs path compress on the DFS info.
112     *
113     * @param in Basic block whose DFS info we are path compressing.
114     */
115    private void compress(SsaBasicBlock in) {
116        DFSInfo bbInfo = info[in.getIndex()];
117        DFSInfo ancestorbbInfo = info[bbInfo.ancestor.getIndex()];
118
119        if (ancestorbbInfo.ancestor != null) {
120            ArrayList<SsaBasicBlock> worklist = new ArrayList<SsaBasicBlock>();
121            HashSet<SsaBasicBlock> visited = new HashSet<SsaBasicBlock>();
122            worklist.add(in);
123
124            while (!worklist.isEmpty()) {
125                int wsize = worklist.size();
126                SsaBasicBlock v = worklist.get(wsize - 1);
127                DFSInfo vbbInfo = info[v.getIndex()];
128                SsaBasicBlock vAncestor = vbbInfo.ancestor;
129                DFSInfo vabbInfo = info[vAncestor.getIndex()];
130
131                // Make sure we process our ancestor before ourselves.
132                if (visited.add(vAncestor) && vabbInfo.ancestor != null) {
133                    worklist.add(vAncestor);
134                    continue;
135                }
136                worklist.remove(wsize - 1);
137
138                // Update based on ancestor info.
139                if (vabbInfo.ancestor == null) {
140                    continue;
141                }
142                SsaBasicBlock vAncestorRep = vabbInfo.rep;
143                SsaBasicBlock vRep = vbbInfo.rep;
144                if (info[vAncestorRep.getIndex()].semidom
145                        < info[vRep.getIndex()].semidom) {
146                    vbbInfo.rep = vAncestorRep;
147                }
148                vbbInfo.ancestor = vabbInfo.ancestor;
149            }
150        }
151    }
152
153    private SsaBasicBlock eval(SsaBasicBlock v) {
154        DFSInfo bbInfo = info[v.getIndex()];
155
156        if (bbInfo.ancestor == null) {
157            return v;
158        }
159
160        compress(v);
161        return bbInfo.rep;
162    }
163
164    /**
165     * Performs dominator/post-dominator calculation for the control
166     * flow graph.
167     *
168     * @param meth {@code non-null;} method to analyze
169     */
170    private void run() {
171        SsaBasicBlock root = postdom
172                ? meth.getExitBlock() : meth.getEntryBlock();
173
174        if (root != null) {
175            vertex.add(root);
176            domInfos[root.getIndex()].idom = root.getIndex();
177        }
178
179        /*
180         * First we perform a DFS numbering of the blocks, by
181         * numbering the dfs tree roots.
182         */
183
184        DfsWalker walker = new DfsWalker();
185        meth.forEachBlockDepthFirst(postdom, walker);
186
187        // the largest semidom number assigned
188        int dfsMax = vertex.size() - 1;
189
190        // Now calculate semidominators.
191        for (int i = dfsMax; i >= 2; --i) {
192            SsaBasicBlock w = vertex.get(i);
193            DFSInfo wInfo = info[w.getIndex()];
194
195            BitSet preds = getPreds(w);
196            for (int j = preds.nextSetBit(0);
197                 j >= 0;
198                 j = preds.nextSetBit(j + 1)) {
199                SsaBasicBlock predBlock = blocks.get(j);
200                DFSInfo predInfo = info[predBlock.getIndex()];
201
202                /*
203                 * PredInfo may not exist in case the predecessor is
204                 * not reachable.
205                 */
206                if (predInfo != null) {
207                    int predSemidom = info[eval(predBlock).getIndex()].semidom;
208                    if (predSemidom < wInfo.semidom) {
209                        wInfo.semidom = predSemidom;
210                    }
211                }
212            }
213            info[vertex.get(wInfo.semidom).getIndex()].bucket.add(w);
214
215            /*
216             * Normally we would call link here, but in our O(m log n)
217             * implementation this is equivalent to the following
218             * single line.
219             */
220            wInfo.ancestor = wInfo.parent;
221
222            // Implicity define idom for each vertex.
223            ArrayList<SsaBasicBlock> wParentBucket;
224            wParentBucket = info[wInfo.parent.getIndex()].bucket;
225
226            while (!wParentBucket.isEmpty()) {
227                int lastItem = wParentBucket.size() - 1;
228                SsaBasicBlock last = wParentBucket.remove(lastItem);
229                SsaBasicBlock U = eval(last);
230                if (info[U.getIndex()].semidom
231                        < info[last.getIndex()].semidom) {
232                    domInfos[last.getIndex()].idom = U.getIndex();
233                } else {
234                    domInfos[last.getIndex()].idom = wInfo.parent.getIndex();
235                }
236            }
237        }
238
239        // Now explicitly define the immediate dominator of each vertex
240        for (int i =  2; i <= dfsMax; ++i) {
241            SsaBasicBlock w = vertex.get(i);
242            if (domInfos[w.getIndex()].idom
243                    != vertex.get(info[w.getIndex()].semidom).getIndex()) {
244                domInfos[w.getIndex()].idom
245                        = domInfos[domInfos[w.getIndex()].idom].idom;
246            }
247        }
248    }
249
250    /**
251     * Callback for depth-first walk through control flow graph (either
252     * from the entry block or the exit block). Records the traversal order
253     * in the {@code info}list.
254     */
255    private class DfsWalker implements SsaBasicBlock.Visitor {
256        private int dfsNum = 0;
257
258        @Override
259        public void visitBlock(SsaBasicBlock v, SsaBasicBlock parent) {
260            DFSInfo bbInfo = new DFSInfo();
261            bbInfo.semidom = ++dfsNum;
262            bbInfo.rep = v;
263            bbInfo.parent = parent;
264            vertex.add(v);
265            info[v.getIndex()] = bbInfo;
266        }
267    }
268
269    private static final class DFSInfo {
270        public int semidom;
271        public SsaBasicBlock parent;
272
273        /**
274         * rep(resentative) is known as "label" in the paper. It is the node
275         * that our block's DFS info has been unioned to.
276         */
277        public SsaBasicBlock rep;
278
279        public SsaBasicBlock ancestor;
280        public ArrayList<SsaBasicBlock> bucket;
281
282        public DFSInfo() {
283            bucket = new ArrayList<SsaBasicBlock>();
284        }
285    }
286}
287