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.rop.code.RegisterSpec;
20import com.android.dx.ssa.PhiInsn;
21import com.android.dx.ssa.SsaBasicBlock;
22import com.android.dx.ssa.SsaInsn;
23import com.android.dx.ssa.SsaMethod;
24import java.util.ArrayList;
25import java.util.BitSet;
26import java.util.List;
27
28/**
29 * From Appel "Modern Compiler Implementation in Java" algorithm 19.17
30 * Calculate the live ranges for register {@code reg}.<p>
31 *
32 * v = regV <p>
33 * s = insn <p>
34 * M = visitedBlocks <p>
35 */
36public class LivenessAnalyzer {
37    /**
38     * {@code non-null;} index by basic block indexed set of basic blocks
39     * that have already been visited. "M" as written in the original Appel
40     * algorithm.
41     */
42    private final BitSet visitedBlocks;
43
44    /**
45     * {@code non-null;} set of blocks remaing to visit as "live out as block"
46     */
47    private final BitSet liveOutBlocks;
48
49    /**
50     * {@code >=0;} SSA register currently being analyzed.
51     * "v" in the original Appel algorithm.
52     */
53    private final int regV;
54
55    /** method to process */
56    private final SsaMethod ssaMeth;
57
58    /** interference graph being updated */
59    private final InterferenceGraph interference;
60
61    /** block "n" in Appel 19.17 */
62    private SsaBasicBlock blockN;
63
64    /** index of statement {@code s} in {@code blockN} */
65    private int statementIndex;
66
67    /** the next function to call */
68    private NextFunction nextFunction;
69
70    /** constants for {@link #nextFunction} */
71    private static enum NextFunction {
72        LIVE_IN_AT_STATEMENT,
73            LIVE_OUT_AT_STATEMENT,
74            LIVE_OUT_AT_BLOCK,
75            DONE;
76    }
77
78    /**
79     * Runs register liveness algorithm for a method, updating the
80     * live in/out information in {@code SsaBasicBlock} instances and
81     * returning an interference graph.
82     *
83     * @param ssaMeth {@code non-null;} method to process
84     * @return {@code non-null;} interference graph indexed by SSA
85     * registers in both directions
86     */
87    public static InterferenceGraph constructInterferenceGraph(
88            SsaMethod ssaMeth) {
89        int szRegs = ssaMeth.getRegCount();
90        InterferenceGraph interference = new InterferenceGraph(szRegs);
91
92        for (int i = 0; i < szRegs; i++) {
93            new LivenessAnalyzer(ssaMeth, i, interference).run();
94        }
95
96        coInterferePhis(ssaMeth, interference);
97
98        return interference;
99    }
100
101    /**
102     * Makes liveness analyzer instance for specific register.
103     *
104     * @param ssaMeth {@code non-null;} method to process
105     * @param reg register whose liveness to analyze
106     * @param interference {@code non-null;} indexed by SSA reg in
107     * both dimensions; graph to update
108     *
109     */
110    private LivenessAnalyzer(SsaMethod ssaMeth, int reg,
111            InterferenceGraph interference) {
112        int blocksSz = ssaMeth.getBlocks().size();
113
114        this.ssaMeth = ssaMeth;
115        this.regV = reg;
116        visitedBlocks = new BitSet(blocksSz);
117        liveOutBlocks = new BitSet(blocksSz);
118        this.interference = interference;
119    }
120
121    /**
122     * The algorithm in Appel is presented in partial tail-recursion
123     * form. Obviously, that's not efficient in java, so this function
124     * serves as the dispatcher instead.
125     */
126    private void handleTailRecursion() {
127        while (nextFunction != NextFunction.DONE) {
128            switch (nextFunction) {
129                case LIVE_IN_AT_STATEMENT:
130                    nextFunction = NextFunction.DONE;
131                    liveInAtStatement();
132                    break;
133
134                case LIVE_OUT_AT_STATEMENT:
135                    nextFunction = NextFunction.DONE;
136                    liveOutAtStatement();
137                    break;
138
139                case LIVE_OUT_AT_BLOCK:
140                    nextFunction = 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 = 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 :
163                         phi.predBlocksForReg(regV, ssaMeth)) {
164                    blockN = pred;
165
166                    nextFunction = 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 = 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 = 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 = NextFunction.LIVE_OUT_AT_STATEMENT;
208        }
209    }
210
211    /**
212     * "v is live-in at s."
213     */
214    private void liveInAtStatement() {
215        // if s is the first statement in block N
216        if (statementIndex == 0) {
217            // v is live-in at n
218            blockN.addLiveIn(regV);
219
220            BitSet preds = blockN.getPredecessors();
221
222            liveOutBlocks.or(preds);
223        } else {
224            // Let s' be the statement preceeding s
225            statementIndex -= 1;
226            nextFunction = NextFunction.LIVE_OUT_AT_STATEMENT;
227        }
228    }
229
230    /**
231     * "v is live-out at s."
232     */
233    private void liveOutAtStatement() {
234        SsaInsn statement = blockN.getInsns().get(statementIndex);
235        RegisterSpec rs = statement.getResult();
236
237        if (!statement.isResultReg(regV)) {
238            if (rs != null) {
239                interference.add(regV, rs.getReg());
240            }
241            nextFunction = NextFunction.LIVE_IN_AT_STATEMENT;
242        }
243    }
244
245    /**
246     * Ensures that all the phi result registers for all the phis in the
247     * same basic block interfere with each other. This is needed since
248     * the dead code remover has allowed through "dead-end phis" whose
249     * results are not used except as local assignments. Without this step,
250     * a the result of a dead-end phi might be assigned the same register
251     * as the result of another phi, and the phi removal move scheduler may
252     * generate moves that over-write the live result.
253     *
254     * @param ssaMeth {@code non-null;} method to pricess
255     * @param interference {@code non-null;} interference graph
256     */
257    private static void coInterferePhis(SsaMethod ssaMeth,
258            InterferenceGraph interference) {
259        for (SsaBasicBlock b : ssaMeth.getBlocks()) {
260            List<SsaInsn> phis = b.getPhiInsns();
261
262            int szPhis = phis.size();
263
264            for (int i = 0; i < szPhis; i++) {
265                for (int j = 0; j < szPhis; j++) {
266                    if (i == j) {
267                        continue;
268                    }
269
270                    interference.add(phis.get(i).getResult().getReg(),
271                        phis.get(j).getResult().getReg());
272                }
273            }
274        }
275    }
276}
277