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 
17 package com.android.dx.ssa;
18 
19 import com.android.dx.util.IntSet;
20 import java.util.ArrayList;
21 import java.util.BitSet;
22 
23 /**
24  * Calculates the dominance-frontiers of a methot's basic blocks.
25  * Algorithm from "A Simple, Fast Dominance Algorithm" by Cooper,
26  * Harvey, and Kennedy; transliterated to Java.
27  */
28 public class DomFront {
29     /** local debug flag */
30     private static 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      */
DomFront(SsaMethod meth)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      */
run()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 
debugPrintDomChildren()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      */
buildDomTree()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      */
calcDomFronts()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