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.back;
18 
19 import com.android.dx.rop.code.RegisterSpec;
20 import com.android.dx.rop.code.RegisterSpecList;
21 import com.android.dx.ssa.PhiInsn;
22 import com.android.dx.ssa.SsaBasicBlock;
23 import com.android.dx.ssa.SsaInsn;
24 import com.android.dx.ssa.SsaMethod;
25 import java.util.ArrayList;
26 import java.util.BitSet;
27 import java.util.List;
28 
29 /**
30  * From Appel "Modern Compiler Implementation in Java" algorithm 19.17
31  * Calculate the live ranges for register {@code reg}.<p>
32  *
33  * v = regV <p>
34  * s = insn <p>
35  * M = visitedBlocks <p>
36  */
37 public class LivenessAnalyzer {
38     /**
39      * {@code non-null;} index by basic block indexed set of basic blocks
40      * that have already been visited. "M" as written in the original Appel
41      * algorithm.
42      */
43     private final BitSet visitedBlocks;
44 
45     /**
46      * {@code non-null;} set of blocks remaing to visit as "live out as block"
47      */
48     private final BitSet liveOutBlocks;
49 
50     /**
51      * {@code >=0;} SSA register currently being analyzed.
52      * "v" in the original Appel algorithm.
53      */
54     private final int regV;
55 
56     /** method to process */
57     private final SsaMethod ssaMeth;
58 
59     /** interference graph being updated */
60     private final InterferenceGraph interference;
61 
62     /** block "n" in Appel 19.17 */
63     private SsaBasicBlock blockN;
64 
65     /** index of statement {@code s} in {@code blockN} */
66     private int statementIndex;
67 
68     /** the next function to call */
69     private NextFunction nextFunction;
70 
71     /** constants for {@link #nextFunction} */
72     private static enum NextFunction {
73         LIVE_IN_AT_STATEMENT,
74             LIVE_OUT_AT_STATEMENT,
75             LIVE_OUT_AT_BLOCK,
76             DONE;
77     }
78 
79     /**
80      * Runs register liveness algorithm for a method, updating the
81      * live in/out information in {@code SsaBasicBlock} instances and
82      * returning an interference graph.
83      *
84      * @param ssaMeth {@code non-null;} method to process
85      * @return {@code non-null;} interference graph indexed by SSA
86      * registers in both directions
87      */
constructInterferenceGraph( SsaMethod ssaMeth)88     public static InterferenceGraph constructInterferenceGraph(
89             SsaMethod ssaMeth) {
90         int szRegs = ssaMeth.getRegCount();
91         InterferenceGraph interference = new InterferenceGraph(szRegs);
92 
93         for (int i = 0; i < szRegs; i++) {
94             new LivenessAnalyzer(ssaMeth, i, interference).run();
95         }
96 
97         coInterferePhis(ssaMeth, interference);
98 
99         return interference;
100     }
101 
102     /**
103      * Makes liveness analyzer instance for specific register.
104      *
105      * @param ssaMeth {@code non-null;} method to process
106      * @param reg register whose liveness to analyze
107      * @param interference {@code non-null;} indexed by SSA reg in
108      * both dimensions; graph to update
109      *
110      */
LivenessAnalyzer(SsaMethod ssaMeth, int reg, InterferenceGraph interference)111     private LivenessAnalyzer(SsaMethod ssaMeth, int reg,
112             InterferenceGraph interference) {
113         int blocksSz = ssaMeth.getBlocks().size();
114 
115         this.ssaMeth = ssaMeth;
116         this.regV = reg;
117         visitedBlocks = new BitSet(blocksSz);
118         liveOutBlocks = new BitSet(blocksSz);
119         this.interference = interference;
120     }
121 
122     /**
123      * The algorithm in Appel is presented in partial tail-recursion
124      * form. Obviously, that's not efficient in java, so this function
125      * serves as the dispatcher instead.
126      */
handleTailRecursion()127     private void handleTailRecursion() {
128         while (nextFunction != NextFunction.DONE) {
129             switch (nextFunction) {
130                 case LIVE_IN_AT_STATEMENT:
131                     nextFunction = NextFunction.DONE;
132                     liveInAtStatement();
133                     break;
134 
135                 case LIVE_OUT_AT_STATEMENT:
136                     nextFunction = NextFunction.DONE;
137                     liveOutAtStatement();
138                     break;
139 
140                 case LIVE_OUT_AT_BLOCK:
141                     nextFunction = NextFunction.DONE;
142                     liveOutAtBlock();
143                     break;
144 
145                 default:
146             }
147         }
148     }
149 
150     /**
151      * From Appel algorithm 19.17.
152      */
run()153     public void run() {
154         List<SsaInsn> useList = ssaMeth.getUseListForRegister(regV);
155 
156         for (SsaInsn insn : useList) {
157             nextFunction = NextFunction.DONE;
158 
159             if (insn instanceof PhiInsn) {
160                 // If s is a phi-function with V as it's ith argument.
161                 PhiInsn phi = (PhiInsn) insn;
162 
163                 for (SsaBasicBlock pred :
164                          phi.predBlocksForReg(regV, ssaMeth)) {
165                     blockN = pred;
166 
167                     nextFunction = NextFunction.LIVE_OUT_AT_BLOCK;
168                     handleTailRecursion();
169                 }
170             } else {
171                 blockN = insn.getBlock();
172                 statementIndex = blockN.getInsns().indexOf(insn);
173 
174                 if (statementIndex < 0) {
175                     throw new RuntimeException(
176                             "insn not found in it's own block");
177                 }
178 
179                 nextFunction = NextFunction.LIVE_IN_AT_STATEMENT;
180                 handleTailRecursion();
181             }
182         }
183 
184         int nextLiveOutBlock;
185         while ((nextLiveOutBlock = liveOutBlocks.nextSetBit(0)) >= 0) {
186             blockN = ssaMeth.getBlocks().get(nextLiveOutBlock);
187             liveOutBlocks.clear(nextLiveOutBlock);
188             nextFunction = NextFunction.LIVE_OUT_AT_BLOCK;
189             handleTailRecursion();
190         }
191     }
192 
193     /**
194      * "v is live-out at n."
195      */
liveOutAtBlock()196     private void liveOutAtBlock() {
197         if (! visitedBlocks.get(blockN.getIndex())) {
198             visitedBlocks.set(blockN.getIndex());
199 
200             blockN.addLiveOut(regV);
201 
202             ArrayList<SsaInsn> insns;
203 
204             insns = blockN.getInsns();
205 
206             // Live out at last statement in blockN
207             statementIndex = insns.size() - 1;
208             nextFunction = NextFunction.LIVE_OUT_AT_STATEMENT;
209         }
210     }
211 
212     /**
213      * "v is live-in at s."
214      */
liveInAtStatement()215     private void liveInAtStatement() {
216         // if s is the first statement in block N
217         if (statementIndex == 0) {
218             // v is live-in at n
219             blockN.addLiveIn(regV);
220 
221             BitSet preds = blockN.getPredecessors();
222 
223             liveOutBlocks.or(preds);
224         } else {
225             // Let s' be the statement preceeding s
226             statementIndex -= 1;
227             nextFunction = NextFunction.LIVE_OUT_AT_STATEMENT;
228         }
229     }
230 
231     /**
232      * "v is live-out at s."
233      */
liveOutAtStatement()234     private void liveOutAtStatement() {
235         SsaInsn statement = blockN.getInsns().get(statementIndex);
236         RegisterSpec rs = statement.getResult();
237 
238         if (!statement.isResultReg(regV)) {
239             if (rs != null) {
240                 interference.add(regV, rs.getReg());
241             }
242             nextFunction = NextFunction.LIVE_IN_AT_STATEMENT;
243         }
244     }
245 
246     /**
247      * Ensures that all the phi result registers for all the phis in the
248      * same basic block interfere with each other, and also that a phi's source
249      * registers interfere with the result registers from other phis. This is needed since
250      * the dead code remover has allowed through "dead-end phis" whose
251      * results are not used except as local assignments. Without this step,
252      * a the result of a dead-end phi might be assigned the same register
253      * as the result of another phi, and the phi removal move scheduler may
254      * generate moves that over-write the live result.
255      *
256      * @param ssaMeth {@code non-null;} method to process
257      * @param interference {@code non-null;} interference graph
258      */
coInterferePhis(SsaMethod ssaMeth, InterferenceGraph interference)259     private static void coInterferePhis(SsaMethod ssaMeth,
260             InterferenceGraph interference) {
261         for (SsaBasicBlock b : ssaMeth.getBlocks()) {
262             List<SsaInsn> phis = b.getPhiInsns();
263 
264             int szPhis = phis.size();
265 
266             for (int i = 0; i < szPhis; i++) {
267                 for (int j = 0; j < szPhis; j++) {
268                     if (i == j) {
269                         continue;
270                     }
271 
272                     SsaInsn first = phis.get(i);
273                     SsaInsn second = phis.get(j);
274                     coInterferePhiRegisters(interference, first.getResult(), second.getSources());
275                     coInterferePhiRegisters(interference, second.getResult(), first.getSources());
276                     interference.add(first.getResult().getReg(), second.getResult().getReg());
277                 }
278             }
279         }
280     }
281 
coInterferePhiRegisters(InterferenceGraph interference, RegisterSpec result, RegisterSpecList sources)282     private static void coInterferePhiRegisters(InterferenceGraph interference, RegisterSpec result,
283             RegisterSpecList sources) {
284         int resultReg = result.getReg();
285         for (int i = 0; i < sources.size(); ++i) {
286             interference.add(resultReg, sources.get(i).getReg());
287         }
288     }
289 }
290