LivenessAnalyzer.java revision f6c387128427e121477c1b32ad35cdcaa5101ba3 
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.back;
18
19import com.android.dx.ssa.SsaMethod;
20import com.android.dx.ssa.SsaBasicBlock;
21import com.android.dx.ssa.SsaInsn;
22import com.android.dx.ssa.PhiInsn;
23import com.android.dx.rop.code.RegisterSpec;
24
25import java.util.BitSet;
26import java.util.List;
27import java.util.ArrayList;
28
29/**
30 * From Appel "Modern Compiler Implementation in Java" algorithm 19.17
31 * Calculate the live ranges for register <code>reg</code>.<p>
32 *
33 * v = regV <p>
34 * s = insn <p>
35 * M = visitedBlocks <p>
36 */
37public class LivenessAnalyzer {
38
39    /**
40     * non-null; index by basic block indexed set of basic blocks
41     * that have already been visited. "M" as written in the original Appel
42     * algorithm.
43     */
44    private final BitSet visitedBlocks;
45
46    /**
47     * non-null; set of blocks remaing to visit as "live out as block"
48     */
49    private final BitSet liveOutBlocks;
50
51    /**
52     * &gt;=0; SSA register currently being analyzed.
53     * "v" in the original Appel algorithm.
54     */
55    private final int regV;
56
57    /** method to process */
58    private final SsaMethod ssaMeth;
59
60    /** interference graph being updated */
61    private final InterferenceGraph interference;
62
63    /** block "n" in Appel 19.17 */
64    SsaBasicBlock blockN;
65
66    /** index of statement <code>s</code> in <code>blockN</code>*/
67    private int statementIndex;
68
69    /** the next function to call. one of the four constants below */
70    private int nextFunction;
71
72    /** constants for nextFunction */
73    static final int LIVE_IN_AT_STATEMENT = 1;
74    static final int LIVE_OUT_AT_STATEMENT = 2;
75    static final int LIVE_OUT_AT_BLOCK = 3;
76    static final int DONE = 4;
77
78    /**
79     * Runs register liveness algorithm for a method, updating the
80     * live in/out information in <code>SsaBasicBlock</code> instances and
81     * returning an interference graph.
82     *
83     * @param ssaMeth non-null; Method to process.
84     * @return non-null; interference graph indexed by SSA registers in both
85     * directions.
86     */
87    public static InterferenceGraph constructInterferenceGraph(
88            SsaMethod ssaMeth) {
89        int szRegs = ssaMeth.getRegCount();
90
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 non-null; method to process
106     * @param reg register whose liveness to analyze
107     * @param interference non-null; indexed by SSA reg in both dimensions;
108     * graph to update
109     *
110     */
111    private LivenessAnalyzer(final SsaMethod ssaMeth, final int reg,
112            InterferenceGraph interference) {
113        this.ssaMeth = ssaMeth;
114        this.regV = reg;
115        visitedBlocks = new BitSet(ssaMeth.getBlocks().size());
116        liveOutBlocks = new BitSet(ssaMeth.getBlocks().size());
117        this.interference = interference;
118    }
119
120    /**
121     * The algorithm in Appel is presented in
122     * partial tail-recursion form. Obviously, that's not
123     * efficient in java, so this function serves
124     * as the dispatcher instead.
125     */
126    private void handleTailRecursion() {
127        while (nextFunction != DONE) {
128            switch (nextFunction) {
129                case LIVE_IN_AT_STATEMENT:
130                    nextFunction = DONE;
131                    liveInAtStatement();
132                    break;
133
134                case LIVE_OUT_AT_STATEMENT:
135                    nextFunction = DONE;
136                    liveOutAtStatement();
137                    break;
138
139                case LIVE_OUT_AT_BLOCK:
140                    nextFunction = DONE;
141                    liveOutAtBlock();
142                    break;
143
144                default:
145            }
146        }
147    }
148
149    /**
150     * From Appel algorithm 19.17
151     */
152    public void run() {
153        List<SsaInsn> useList = ssaMeth.getUseListForRegister(regV);
154
155        for (SsaInsn insn: useList) {
156            nextFunction = DONE;
157
158            if (insn instanceof PhiInsn) {
159                // If s is a phi-function with V as it's ith argument
160                PhiInsn phi = (PhiInsn) insn;
161
162                for (SsaBasicBlock pred: phi.predBlocksForReg(regV, ssaMeth)) {
163
164                    blockN = pred;
165
166                    nextFunction = LIVE_OUT_AT_BLOCK;
167                    handleTailRecursion();
168                }
169            } else {
170                blockN = insn.getBlock();
171                statementIndex = blockN.getInsns().indexOf(insn);
172
173                if (statementIndex < 0) {
174                    throw new RuntimeException(
175                            "insn not found in it's own block");
176                }
177
178                nextFunction = LIVE_IN_AT_STATEMENT;
179                handleTailRecursion();
180            }
181        }
182
183        int nextLiveOutBlock;
184        while ((nextLiveOutBlock = liveOutBlocks.nextSetBit(0)) >= 0) {
185            blockN = ssaMeth.getBlocks().get(nextLiveOutBlock);
186            liveOutBlocks.clear(nextLiveOutBlock);
187            nextFunction = LIVE_OUT_AT_BLOCK;
188            handleTailRecursion();
189        }
190    }
191
192    /**
193     * "v is live-out at n"
194     */
195    private void liveOutAtBlock() {
196        if (! visitedBlocks.get(blockN.getIndex())) {
197            visitedBlocks.set(blockN.getIndex());
198
199            blockN.addLiveOut(regV);
200
201            ArrayList<SsaInsn> insns;
202
203            insns = blockN.getInsns();
204
205            // Live out at last statement in blockN
206            statementIndex = insns.size() - 1;
207            nextFunction = LIVE_OUT_AT_STATEMENT;
208        }
209    }
210
211    /**
212     * "v is live-in at s"
213     */
214    private void liveInAtStatement() {
215
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 = LIVE_OUT_AT_STATEMENT;
228        }
229    }
230
231    /**
232     * "v is live-out at s"
233     */
234    private void liveOutAtStatement() {
235
236        SsaInsn statement = blockN.getInsns().get(statementIndex);
237        RegisterSpec rs = statement.getResult();
238
239        if (!statement.isResultReg(regV)) {
240            if(rs != null) {
241                interference.add(regV, rs.getReg());
242            }
243            nextFunction = LIVE_IN_AT_STATEMENT;
244        }
245    }
246
247    /**
248     * Ensures that all the phi result registers for all the phis in the
249     * same basic block interfere with each other. 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 non-null; method to pricess
257     * @param interference non-null; interference graph
258     */
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                    interference.add(phis.get(i).getResult().getReg(),
273                        phis.get(j).getResult().getReg());
274                }
275            }
276        }
277    }
278}
279