1/*
2 * Javassist, a Java-bytecode translator toolkit.
3 * Copyright (C) 1999-2007 Shigeru Chiba. All Rights Reserved.
4 *
5 * The contents of this file are subject to the Mozilla Public License Version
6 * 1.1 (the "License"); you may not use this file except in compliance with
7 * the License.  Alternatively, the contents of this file may be used under
8 * the terms of the GNU Lesser General Public License Version 2.1 or later.
9 *
10 * Software distributed under the License is distributed on an "AS IS" basis,
11 * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
12 * for the specific language governing rights and limitations under the
13 * License.
14 */
15
16 package javassist.bytecode.stackmap;
17
18import javassist.bytecode.*;
19
20public class Liveness {
21    protected static final byte UNKNOWN = 0;
22    protected static final byte READ = 1;
23    protected static final byte UPDATED = 2;
24    protected byte[] localsUsage;
25
26    /**
27     * If true, all the arguments become alive within the whole method body.
28     *
29     * To correctly compute a stack map table, all the arguments must
30     * be alive (localsUsage[?] must be READ) at least in the first block.
31     */
32    public static boolean useArgs = true;
33
34    public void compute(CodeIterator ci, TypedBlock[] blocks, int maxLocals,
35                        TypeData[] args)
36        throws BadBytecode
37    {
38        computeUsage(ci, blocks, maxLocals);
39        if (useArgs)
40            useAllArgs(blocks, args);
41
42        computeLiveness1(blocks[0]);
43        while (hasChanged(blocks))
44            computeLiveness2(blocks[0]);
45    }
46
47    private void useAllArgs(TypedBlock[] blocks, TypeData[] args) {
48        for (int k = 0; k < blocks.length; k++) {
49            byte[] usage = blocks[k].localsUsage;
50            for (int i = 0; i < args.length; i++)
51                if (args[i] != TypeTag.TOP)
52                    usage[i] = READ;
53        }
54    }
55
56    static final int NOT_YET = 0;
57    static final int CHANGED_LAST = 1;
58    static final int DONE = 2;
59    static final int CHANGED_NOW = 3;
60
61    private void computeLiveness1(TypedBlock tb) {
62        if (tb.updating) {
63            // a loop was detected.
64            computeLiveness1u(tb);
65            return;
66        }
67
68        if (tb.inputs != null)
69            return;
70
71        tb.updating = true;
72        byte[] usage = tb.localsUsage;
73        int n = usage.length;
74        boolean[] in = new boolean[n];
75        for (int i = 0; i < n; i++)
76            in[i] = usage[i] == READ;
77
78        BasicBlock.Catch handlers = tb.toCatch;
79        while (handlers != null) {
80            TypedBlock h = (TypedBlock)handlers.body;
81            computeLiveness1(h);
82            for (int k = 0; k < n; k++)
83                if (h.inputs[k])
84                    in[k] = true;
85
86            handlers = handlers.next;
87        }
88
89        if (tb.exit != null) {
90            for (int i = 0; i < tb.exit.length; i++) {
91                TypedBlock e = (TypedBlock)tb.exit[i];
92                computeLiveness1(e);
93                for (int k = 0; k < n; k++)
94                    if (!in[k])
95                        in[k] = usage[k] == UNKNOWN && e.inputs[k];
96            }
97        }
98
99        tb.updating = false;
100        if (tb.inputs == null) {
101            tb.inputs = in;
102            tb.status = DONE;
103        }
104        else {
105            for (int i = 0; i < n; i++)
106                if (in[i] && !tb.inputs[i]) {
107                    tb.inputs[i] = true;
108                    tb.status = CHANGED_NOW;
109                }
110        }
111    }
112
113    private void computeLiveness1u(TypedBlock tb) {
114        if (tb.inputs == null) {
115            byte[] usage = tb.localsUsage;
116            int n = usage.length;
117            boolean[] in = new boolean[n];
118            for (int i = 0; i < n; i++)
119                in[i] = usage[i] == READ;
120
121            tb.inputs = in;
122            tb.status = DONE;
123        }
124    }
125
126    private void computeLiveness2(TypedBlock tb) {
127        if (tb.updating || tb.status >= DONE)
128            return;
129
130        tb.updating = true;
131        if (tb.exit == null)
132            tb.status = DONE;
133        else {
134            boolean changed = false;
135            for (int i = 0; i < tb.exit.length; i++) {
136                TypedBlock e = (TypedBlock)tb.exit[i];
137                computeLiveness2(e);
138                if (e.status != DONE)
139                    changed = true;
140            }
141
142            if (changed) {
143                changed = false;
144                byte[] usage = tb.localsUsage;
145                int n = usage.length;
146                for (int i = 0; i < tb.exit.length; i++) {
147                    TypedBlock e = (TypedBlock)tb.exit[i];
148                    if (e.status != DONE)
149                        for (int k = 0; k < n; k++)
150                            if (!tb.inputs[k]) {
151                                if (usage[k] == UNKNOWN && e.inputs[k]) {
152                                    tb.inputs[k] = true;
153                                    changed = true;
154                                }
155                            }
156                }
157
158                tb.status = changed ? CHANGED_NOW : DONE;
159            }
160            else
161                tb.status = DONE;
162        }
163
164        if (computeLiveness2except(tb))
165            tb.status = CHANGED_NOW;
166
167        tb.updating = false;
168    }
169
170    private boolean computeLiveness2except(TypedBlock tb) {
171        BasicBlock.Catch handlers = tb.toCatch;
172        boolean changed = false;
173        while (handlers != null) {
174            TypedBlock h = (TypedBlock)handlers.body;
175            computeLiveness2(h);
176            if (h.status != DONE) {
177                boolean[] in = tb.inputs;
178                int n = in.length;
179                for (int k = 0; k < n; k++)
180                    if (!in[k] && h.inputs[k]) {
181                        in[k] = true;
182                        changed = true;
183                    }
184            }
185
186            handlers = handlers.next;
187        }
188
189        return changed;
190    }
191
192    private boolean hasChanged(TypedBlock[] blocks) {
193        int n = blocks.length;
194        boolean changed = false;
195        for (int i = 0; i < n; i++) {
196            TypedBlock tb = blocks[i];
197            if (tb.status == CHANGED_NOW) {
198                tb.status = CHANGED_LAST;
199                changed = true;
200            }
201            else
202                tb.status = NOT_YET;
203        }
204
205        return changed;
206    }
207
208    private void computeUsage(CodeIterator ci, TypedBlock[] blocks, int maxLocals)
209        throws BadBytecode
210    {
211        int n = blocks.length;
212        for (int i = 0; i < n; i++) {
213            TypedBlock tb = blocks[i];
214            localsUsage = tb.localsUsage = new byte[maxLocals];
215            int pos = tb.position;
216            analyze(ci, pos, pos + tb.length);
217            localsUsage = null;
218        }
219    }
220
221    protected final void readLocal(int reg) {
222        if (localsUsage[reg] == UNKNOWN)
223            localsUsage[reg] = READ;
224    }
225
226    protected final void writeLocal(int reg) {
227        if (localsUsage[reg] == UNKNOWN)
228            localsUsage[reg] = UPDATED;
229    }
230
231    protected void analyze(CodeIterator ci, int begin, int end)
232        throws BadBytecode
233    {
234        ci.begin();
235        ci.move(begin);
236        while (ci.hasNext()) {
237            int index = ci.next();
238            if (index >= end)
239                break;
240
241            int op = ci.byteAt(index);
242            if (op < 96)
243                if (op < 54)
244                    doOpcode0_53(ci, index, op);
245                else
246                    doOpcode54_95(ci, index, op);
247            else
248                if (op == Opcode.IINC) {
249                    // this does not call writeLocal().
250                    readLocal(ci.byteAt(index + 1));
251                }
252                else if (op == Opcode.WIDE)
253                    doWIDE(ci, index);
254        }
255    }
256
257    private void doOpcode0_53(CodeIterator ci, int pos, int op) {
258        switch (op) {
259        case Opcode.ILOAD :
260        case Opcode.LLOAD :
261        case Opcode.FLOAD :
262        case Opcode.DLOAD :
263        case Opcode.ALOAD :
264            readLocal(ci.byteAt(pos + 1));
265            break;
266        case Opcode.ILOAD_0 :
267        case Opcode.ILOAD_1 :
268        case Opcode.ILOAD_2 :
269        case Opcode.ILOAD_3 :
270            readLocal(op - Opcode.ILOAD_0);
271            break;
272        case Opcode.LLOAD_0 :
273        case Opcode.LLOAD_1 :
274        case Opcode.LLOAD_2 :
275        case Opcode.LLOAD_3 :
276            readLocal(op - Opcode.LLOAD_0);
277            break;
278        case Opcode.FLOAD_0 :
279        case Opcode.FLOAD_1 :
280        case Opcode.FLOAD_2 :
281        case Opcode.FLOAD_3 :
282            readLocal(op - Opcode.FLOAD_0);
283            break;
284        case Opcode.DLOAD_0 :
285        case Opcode.DLOAD_1 :
286        case Opcode.DLOAD_2 :
287        case Opcode.DLOAD_3 :
288            readLocal(op - Opcode.DLOAD_0);
289            break;
290        case Opcode.ALOAD_0 :
291        case Opcode.ALOAD_1 :
292        case Opcode.ALOAD_2 :
293        case Opcode.ALOAD_3 :
294            readLocal(op - Opcode.ALOAD_0);
295            break;
296        }
297    }
298
299    private void doOpcode54_95(CodeIterator ci, int pos, int op) {
300        switch (op) {
301        case Opcode.ISTORE :
302        case Opcode.LSTORE :
303        case Opcode.FSTORE :
304        case Opcode.DSTORE :
305        case Opcode.ASTORE :
306            writeLocal(ci.byteAt(pos + 1));
307            break;
308        case Opcode.ISTORE_0 :
309        case Opcode.ISTORE_1 :
310        case Opcode.ISTORE_2 :
311        case Opcode.ISTORE_3 :
312            writeLocal(op - Opcode.ISTORE_0);
313            break;
314        case Opcode.LSTORE_0 :
315        case Opcode.LSTORE_1 :
316        case Opcode.LSTORE_2 :
317        case Opcode.LSTORE_3 :
318            writeLocal(op - Opcode.LSTORE_0);
319            break;
320        case Opcode.FSTORE_0 :
321        case Opcode.FSTORE_1 :
322        case Opcode.FSTORE_2 :
323        case Opcode.FSTORE_3 :
324            writeLocal(op - Opcode.FSTORE_0);
325            break;
326        case Opcode.DSTORE_0 :
327        case Opcode.DSTORE_1 :
328        case Opcode.DSTORE_2 :
329        case Opcode.DSTORE_3 :
330            writeLocal(op - Opcode.DSTORE_0);
331            break;
332        case Opcode.ASTORE_0 :
333        case Opcode.ASTORE_1 :
334        case Opcode.ASTORE_2 :
335        case Opcode.ASTORE_3 :
336            writeLocal(op - Opcode.ASTORE_0);
337            break;
338        }
339    }
340
341    private void doWIDE(CodeIterator ci, int pos) throws BadBytecode {
342        int op = ci.byteAt(pos + 1);
343        int var = ci.u16bitAt(pos + 2);
344        switch (op) {
345        case Opcode.ILOAD :
346        case Opcode.LLOAD :
347        case Opcode.FLOAD :
348        case Opcode.DLOAD :
349        case Opcode.ALOAD :
350            readLocal(var);
351            break;
352        case Opcode.ISTORE :
353        case Opcode.LSTORE :
354        case Opcode.FSTORE :
355        case Opcode.DSTORE :
356        case Opcode.ASTORE :
357            writeLocal(var);
358            break;
359        case Opcode.IINC :
360            readLocal(var);
361            // this does not call writeLocal().
362            break;
363        }
364    }
365}
366