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}.<p>
32 *
33 * v = regV <p>
34 * s = insn <p>
35 * M = visitedBlocks <p>
36 */
37public 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     */
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     */
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     */
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     */
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     */
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     */
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     */
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. This is needed since
249     * the dead code remover has allowed through "dead-end phis" whose
250     * results are not used except as local assignments. Without this step,
251     * a the result of a dead-end phi might be assigned the same register
252     * as the result of another phi, and the phi removal move scheduler may
253     * generate moves that over-write the live result.
254     *
255     * @param ssaMeth {@code non-null;} method to pricess
256     * @param interference {@code non-null;} interference graph
257     */
258    private static void coInterferePhis(SsaMethod ssaMeth,
259            InterferenceGraph interference) {
260        for (SsaBasicBlock b : ssaMeth.getBlocks()) {
261            List<SsaInsn> phis = b.getPhiInsns();
262
263            int szPhis = phis.size();
264
265            for (int i = 0; i < szPhis; i++) {
266                for (int j = 0; j < szPhis; j++) {
267                    if (i == j) {
268                        continue;
269                    }
270
271                    interference.add(phis.get(i).getResult().getReg(),
272                        phis.get(j).getResult().getReg());
273                }
274            }
275        }
276    }
277}
278