Dominators.java revision 2ad60cfc28e14ee8f0bb038720836a4696c478ad 
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 boolean postdom;
46    /* Method's basic blocks. */
47    private ArrayList<SsaBasicBlock> blocks;
48
49    private static final class DFSInfo {
50        int semidom;
51        SsaBasicBlock parent;
52        // rep(resentative) is known as "label" in the paper. It is the node
53        // that our block's DFS info has been unioned to.
54        SsaBasicBlock rep;
55        SsaBasicBlock ancestor;
56        ArrayList<SsaBasicBlock> bucket;
57
58        public DFSInfo() {
59            bucket = new ArrayList<SsaBasicBlock>();
60        }
61
62    }
63
64    /** Indexed by basic block index */
65    private DFSInfo[] info;
66    private ArrayList<SsaBasicBlock> vertex;
67
68    private DomFront.DomInfo domInfos[];
69
70    private BitSet getSuccs(SsaBasicBlock block) {
71        if (postdom) {
72            return block.getPredecessors();
73        } else {
74            return block.getSuccessors();
75        }
76    }
77
78    private BitSet getPreds(SsaBasicBlock block) {
79        if (postdom) {
80            return block.getSuccessors();
81        } else {
82            return block.getPredecessors();
83        }
84    }
85
86    /**
87     * Performs path compress on the DFS info.
88     * @param in Basic block whose DFS info we are path compressing.
89     */
90    private void compress(SsaBasicBlock in) {
91        DFSInfo bbInfo = info[in.getIndex()];
92        DFSInfo ancestorbbInfo = info[bbInfo.ancestor.getIndex()];
93
94        if (ancestorbbInfo.ancestor != null) {
95            ArrayList<SsaBasicBlock> worklist = new ArrayList<SsaBasicBlock>();
96            HashSet<SsaBasicBlock> visited = new HashSet<SsaBasicBlock>();
97            worklist.add(in);
98
99            while (!worklist.isEmpty()) {
100                int wsize = worklist.size();
101                SsaBasicBlock v = worklist.get(wsize - 1);
102                DFSInfo vbbInfo = info[v.getIndex()];
103                SsaBasicBlock vAncestor = vbbInfo.ancestor;
104                DFSInfo vabbInfo = info[vAncestor.getIndex()];
105
106                // Make sure we process our ancestor before ourselves.
107                if (visited.add(vAncestor) && vabbInfo.ancestor != null) {
108                    worklist.add(vAncestor);
109                    continue;
110                }
111                worklist.remove(wsize - 1);
112
113                // Update based on ancestor info
114                if (vabbInfo.ancestor == null) {
115                    continue;
116                }
117                SsaBasicBlock vAncestorRep = vabbInfo.rep;
118                SsaBasicBlock vRep = vbbInfo.rep;
119                if (info[vAncestorRep.getIndex()].semidom
120                        < info[vRep.getIndex()].semidom) {
121                    vbbInfo.rep = vAncestorRep;
122                }
123                vbbInfo.ancestor = vabbInfo.ancestor;
124            }
125        }
126    }
127    private SsaBasicBlock eval(SsaBasicBlock v) {
128        DFSInfo bbInfo = info[v.getIndex()];
129        if (bbInfo.ancestor == null) {
130            return v;
131        }
132        compress(v);
133        return bbInfo.rep;
134    }
135
136    /**
137     * Callback for depth-first walk through control flow graph (either
138     * from the entry block or the exit block). Records the traversal order
139     * in the <code>info</code>list.
140     */
141    private class DfsWalker implements SsaBasicBlock.Visitor {
142        int dfsNum = 0;
143
144        public void visitBlock (SsaBasicBlock v, SsaBasicBlock parent) {
145            DFSInfo bbInfo = new DFSInfo();
146            bbInfo.semidom = ++dfsNum;
147            bbInfo.rep = v;
148            bbInfo.parent = parent;
149            vertex.add(v);
150            info[v.getIndex()] = bbInfo;
151        }
152    }
153
154    /**
155     * Performs dominator/post-dominator calculation for the control flow graph.
156     * @param meth Method to analyze
157     */
158    public void run(SsaMethod meth) {
159
160        this.blocks = meth.getBlocks();
161        this.info = new DFSInfo[blocks.size() + 2];
162        this.vertex = new ArrayList<SsaBasicBlock>();
163        SsaBasicBlock root = postdom
164                ? meth.getExitBlock() : meth.getEntryBlock();
165
166        if (root != null) {
167            vertex.add(root);
168            domInfos[root.getIndex()].idom = root.getIndex();
169        }
170
171        // First we perform a DFS numbering of the blocks, by numbering the dfs
172        // tree roots
173
174        DfsWalker walker = new DfsWalker();
175        meth.forEachBlockDepthFirst(postdom, walker);
176
177        // the largest semidom number assigned
178        int dfsMax = vertex.size() - 1;
179
180        // Now calculate semidominators.
181        for (int i = dfsMax; i >= 2; --i) {
182            SsaBasicBlock w = vertex.get(i);
183            DFSInfo wInfo = info[w.getIndex()];
184
185            BitSet preds = getPreds(w);
186            for (int j = preds.nextSetBit(0);
187                    j >= 0;
188                    j = preds.nextSetBit(j + 1)) {
189                SsaBasicBlock predBlock = blocks.get(j);
190                DFSInfo predInfo = info[predBlock.getIndex()];
191                // PredInfo may not exist in case the predecessor is not
192                // reachable
193                if (predInfo != null) {
194                    int predSemidom = info[eval(predBlock).getIndex()].semidom;
195                    if (predSemidom < wInfo.semidom) {
196                        wInfo.semidom = predSemidom;
197                    }
198                }
199            }
200            info[vertex.get(wInfo.semidom).getIndex()].bucket.add(w);
201
202            // Normally we would call link here, but in our  m log n
203            // implementation this is equivalent to the following single line
204            wInfo.ancestor = wInfo.parent;
205
206            // Implicity define idom for each vertex
207            ArrayList<SsaBasicBlock> wParentBucket;
208            wParentBucket = info[wInfo.parent.getIndex()].bucket;
209
210            while (!wParentBucket.isEmpty()) {
211                int lastItem = wParentBucket.size() - 1;
212                SsaBasicBlock last = wParentBucket.remove(lastItem);
213                SsaBasicBlock U = eval(last);
214                if (info[U.getIndex()].semidom
215                        < info[last.getIndex()].semidom) {
216                    domInfos[last.getIndex()].idom = U.getIndex();
217                } else {
218                    domInfos[last.getIndex()].idom = wInfo.parent.getIndex();
219                }
220            }
221        }
222        // Now explicitly define the immediate dominator of each vertex
223        for (int i =  2; i <= dfsMax; ++i) {
224            SsaBasicBlock w = vertex.get(i);
225            if (domInfos[w.getIndex()].idom
226                    != vertex.get(info[w.getIndex()].semidom).getIndex()) {
227                domInfos[w.getIndex()].idom
228                        = domInfos[domInfos[w.getIndex()].idom].idom;
229            }
230        }
231    }
232
233    /**
234     * @param postdom true for postdom information, false for normal dom info
235     */
236    public Dominators(DomFront.DomInfo[] domInfos, boolean postdom) {
237        this.domInfos = domInfos;
238        this.postdom = postdom;
239    }
240}
241