← Back to branch summary

~ubuntu-branches/ubuntu/vivid/nqp/vivid-proposed

« back to all changes in this revision

Viewing changes to src/vm/jvm/runtime/org/perl6/nqp/jast2bc/AutosplitMethodWriter.java

  • Committer: Package Import Robot
  • Author(s): Alessandro Ghedini
  • Date: 2013-11-01 12:09:18 UTC
  • mfrom: (1.1.4)
  • Revision ID: package-import@ubuntu.com-20131101120918-kx51sl0sxl3exsxi
Tags: 2013.10-1
* New upstream release
* Bump versioned (Build-)Depends on parrot
* Update patches
* Install new README.pod
* Fix vcs-field-not-canonical
* Do not install rubyish examples
* Do not Depends on parrot-devel anymore
* Add 07_disable-serialization-tests.patch

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/vm/jvm/runtime/org/perl6/nqp/jast2bc/AutosplitMethodWriter.java
 
1
package org.perl6.nqp.jast2bc;
 
2
 
 
3
import org.objectweb.asm.ClassVisitor;
 
4
import org.objectweb.asm.Handle;
 
5
import org.objectweb.asm.Label;
 
6
import org.objectweb.asm.MethodVisitor;
 
7
import org.objectweb.asm.Opcodes;
 
8
import org.objectweb.asm.Type;
 
9
import org.objectweb.asm.tree.AbstractInsnNode;
 
10
import org.objectweb.asm.tree.FieldInsnNode;
 
11
import org.objectweb.asm.tree.IincInsnNode;
 
12
import org.objectweb.asm.tree.InsnList;
 
13
import org.objectweb.asm.tree.InsnNode;
 
14
import org.objectweb.asm.tree.IntInsnNode;
 
15
import org.objectweb.asm.tree.InvokeDynamicInsnNode;
 
16
import org.objectweb.asm.tree.JumpInsnNode;
 
17
import org.objectweb.asm.tree.LabelNode;
 
18
import org.objectweb.asm.tree.LdcInsnNode;
 
19
import org.objectweb.asm.tree.LineNumberNode;
 
20
import org.objectweb.asm.tree.LookupSwitchInsnNode;
 
21
import org.objectweb.asm.tree.MethodInsnNode;
 
22
import org.objectweb.asm.tree.MethodNode;
 
23
import org.objectweb.asm.tree.MultiANewArrayInsnNode;
 
24
import org.objectweb.asm.tree.TableSwitchInsnNode;
 
25
import org.objectweb.asm.tree.TryCatchBlockNode;
 
26
import org.objectweb.asm.tree.TypeInsnNode;
 
27
import org.objectweb.asm.tree.VarInsnNode;
 
28
 
 
29
import java.util.ArrayList;
 
30
import java.util.Arrays;
 
31
import java.util.HashMap;
 
32
import java.util.HashSet;
 
33
import java.util.List;
 
34
import java.util.Map;
 
35
import java.util.Set;
 
36
 
 
37
@SuppressWarnings("unchecked") /* our asm is stripped */
 
38
class AutosplitMethodWriter extends MethodNode {
 
39
 
 
40
    /** Maximum size of a method to leave alone. */
 
41
    private static final int MAX_UNSPLIT_METHOD = 65535;
 
42
    private static final int MAX_FRAGMENT = 65535;
 
43
    private static final int MAX_SWITCH = 256;
 
44
 
 
45
    /** True to dump control flow analysis. */
 
46
    private static final boolean DEBUG_CONTROL = false;
 
47
    private static final boolean DEBUG_FRAGMENT = false;
 
48
    private static final boolean TYPE_TRACE = false;
 
49
 
 
50
    /** The real instructions (not branches) in program order.  Filled out by {@link getControlFlow()}. */
 
51
    private AbstractInsnNode[] insnList;
 
52
    private Map<AbstractInsnNode, Integer> insnMap;
 
53
    private int[] lineNumbers;
 
54
 
 
55
    /** Array of (source, target) pairs.  Filled out by {@link getControlFlow()}.  -1 means from-outside. */
 
56
    private ControlEdge[] controlEdges;
 
57
    private ControlEdge[][] successors;
 
58
    private int[] depth;
 
59
    private int[] baselineSize;
 
60
    private Frame[] types;
 
61
 
 
62
    private int nextJumpNo;
 
63
    private int[] jumpNoMap;
 
64
    private List<Integer> firstJump = new ArrayList< >();
 
65
 
 
66
    private static class ControlEdge {
 
67
        public final int from, to;
 
68
        public final String exn; // if non-null, replace the stack with this
 
69
        public ControlEdge(int f, int t, String e) { from = f; to = t; exn = e; }
 
70
    }
 
71
 
 
72
    private int nstack, nlocal;
 
73
 
 
74
    private final ClassVisitor target;
 
75
    private final String tgtype;
 
76
 
 
77
    public AutosplitMethodWriter(ClassVisitor target, String tgtype, int access, String name, String desc, String sig, String[] exn) {
 
78
        super(Opcodes.ASM4, access, name, desc, sig, exn);
 
79
        this.target = target;
 
80
        this.tgtype = tgtype;
 
81
    }
 
82
 
 
83
    @Override
 
84
    public void visitEnd() {
 
85
        super.visitEnd();
 
86
 
 
87
        int maxsize = 0;
 
88
        for (AbstractInsnNode ai = instructions.getFirst(); ai != null; ai = ai.getNext())
 
89
            maxsize += insnSize(ai);
 
90
 
 
91
        if (maxsize <= MAX_UNSPLIT_METHOD) {
 
92
            // hey cool, we don't need to do anything fancy here
 
93
            MethodVisitor mw = target.visitMethod(access, name, desc, signature, ((List<String>)exceptions).toArray(new String[0]));
 
94
            accept(mw);
 
95
            return;
 
96
        }
 
97
 
 
98
        /* we need to split this thing */
 
99
 
 
100
        if (DEBUG_FRAGMENT) System.out.printf("method=%s max=%d\n", name, maxsize);
 
101
 
 
102
        splitSwitches();
 
103
        getInstructions();
 
104
        getControlFlow();
 
105
        if (DEBUG_CONTROL) printControlFlow();
 
106
        getTypes();
 
107
        getBaselineSize();
 
108
 
 
109
        if (DEBUG_CONTROL) {
 
110
            for (int i = 1; i <= insnList.length; i++)
 
111
                System.out.printf("from=%d to=%d frag=%d\n", 0,i,calcFragmentSize(0, i));
 
112
        }
 
113
 
 
114
        jumpNoMap = new int[insnList.length];
 
115
        Arrays.fill(jumpNoMap, -1);
 
116
        List<Integer> fragmentSizes = new ArrayList< >();
 
117
        int taken = 0;
 
118
        while (taken < insnList.length) {
 
119
            if (calcFragmentSize(taken, taken+1) > MAX_FRAGMENT)
 
120
                throw new RuntimeException("cannot take even one more instruction at "+taken);
 
121
            int takeable = bite(taken, 1, insnList.length - taken);
 
122
 
 
123
            if (DEBUG_FRAGMENT) System.out.printf("fragment: %d - %d (max %d bytes)\n", taken, taken + takeable - 1, calcFragmentSize(taken, taken+takeable));
 
124
            fragmentSizes.add(takeable);
 
125
            allocateJumpNrs(taken, taken+takeable);
 
126
            taken += takeable;
 
127
        }
 
128
 
 
129
        taken = 0;
 
130
        int fno = 0;
 
131
        for (int sz : fragmentSizes) {
 
132
            emitFragment(fno++, taken, taken+sz);
 
133
            taken += sz;
 
134
        }
 
135
 
 
136
        becomeWrapper();
 
137
        accept(target);
 
138
    }
 
139
 
 
140
    private int bite(int from, int min_take, int max_take) { /* min_take is known good */
 
141
        while (true) {
 
142
            if (min_take == max_take) return min_take;
 
143
            int mid_take = (min_take + max_take + 1) / 2;
 
144
 
 
145
            if (calcFragmentSize(from, from+mid_take) <= MAX_FRAGMENT) {
 
146
                min_take = mid_take;
 
147
            } else {
 
148
                max_take = mid_take-1;
 
149
            }
 
150
        }
 
151
    }
 
152
 
 
153
    private boolean isRealInsn(AbstractInsnNode node) {
 
154
        switch (node.getType()) {
 
155
            case AbstractInsnNode.LINE:
 
156
            case AbstractInsnNode.LABEL:
 
157
            case AbstractInsnNode.FRAME:
 
158
                return false;
 
159
            default:
 
160
                return true;
 
161
        }
 
162
    }
 
163
 
 
164
    /** Break apart large switch instructions so that they may fit in a fragment. Runs before {@link getInstructions} because it changes instruction sequence. */
 
165
    private void splitSwitches() {
 
166
        AbstractInsnNode ptr = instructions.getFirst();
 
167
 
 
168
        while (ptr != null) {
 
169
            int cutoff = 0;
 
170
            AbstractInsnNode left = null, right = null;
 
171
 
 
172
            switch (ptr.getType()) {
 
173
                case AbstractInsnNode.LOOKUPSWITCH_INSN:
 
174
                    {
 
175
                        LookupSwitchInsnNode lsi = (LookupSwitchInsnNode) ptr;
 
176
                        if (lsi.labels.size() <= MAX_SWITCH) break;
 
177
                        LookupSwitchInsnNode lsl = new LookupSwitchInsnNode(lsi.dflt, new int[0], new LabelNode[0]);
 
178
                        LookupSwitchInsnNode lsr = new LookupSwitchInsnNode(lsi.dflt, new int[0], new LabelNode[0]);
 
179
 
 
180
                        int lsisz = lsi.labels.size();
 
181
                        lsl.keys.addAll(lsi.keys.subList(0, lsisz / 2));
 
182
                        lsr.keys.addAll(lsi.keys.subList(lsisz / 2, lsisz));
 
183
                        lsl.labels.addAll(lsi.labels.subList(0, lsisz / 2));
 
184
                        lsr.labels.addAll(lsi.labels.subList(lsisz / 2, lsisz));
 
185
                        left = lsl;
 
186
                        right = lsr;
 
187
                        cutoff = (Integer)lsr.keys.get(0);
 
188
                    }
 
189
                    break;
 
190
 
 
191
                case AbstractInsnNode.TABLESWITCH_INSN:
 
192
                    {
 
193
                        TableSwitchInsnNode lsi = (TableSwitchInsnNode) ptr;
 
194
                        if (lsi.labels.size() <= MAX_SWITCH) break;
 
195
                        cutoff = (lsi.min + lsi.max) / 2;
 
196
                        TableSwitchInsnNode lsl = new TableSwitchInsnNode(lsi.min, cutoff-1, lsi.dflt);
 
197
                        TableSwitchInsnNode lsr = new TableSwitchInsnNode(cutoff, lsi.max, lsi.dflt);
 
198
 
 
199
                        int lsisz = lsi.labels.size();
 
200
 
 
201
                        lsl.labels.addAll(lsi.labels.subList(0, cutoff - lsi.min));
 
202
                        lsr.labels.addAll(lsi.labels.subList(cutoff - lsi.min, lsi.max + 1 - lsi.min));
 
203
                        left = lsl;
 
204
                        right = lsr;
 
205
                    }
 
206
                    break;
 
207
 
 
208
                default: break;
 
209
            }
 
210
 
 
211
            if (left != null) {
 
212
                if (DEBUG_FRAGMENT) System.out.printf("Breaking switch at %d\n", cutoff);
 
213
 
 
214
                LabelNode high = new LabelNode();
 
215
                instructions.insertBefore(ptr, new InsnNode(Opcodes.DUP));
 
216
                instructions.insertBefore(ptr, intNode(cutoff));
 
217
                instructions.insertBefore(ptr, new JumpInsnNode(Opcodes.IF_ICMPGE, high));
 
218
                instructions.insertBefore(ptr, left);
 
219
                instructions.insertBefore(ptr, high);
 
220
                instructions.insertBefore(ptr, right);
 
221
                instructions.remove(ptr);
 
222
 
 
223
                ptr = left;
 
224
            } else {
 
225
                ptr = ptr.getNext();
 
226
            }
 
227
        }
 
228
    }
 
229
 
 
230
    private AbstractInsnNode intNode(int value) {
 
231
        return (value >= -1   && value <= 5) ? new InsnNode(Opcodes.ICONST_0 + value) :
 
232
               (value >= -128 && value <= 127) ? new IntInsnNode(Opcodes.BIPUSH, value) :
 
233
               (value >= -32768 && value <= 32767) ? new IntInsnNode(Opcodes.SIPUSH, value) :
 
234
               new LdcInsnNode(value);
 
235
    }
 
236
 
 
237
    /** Extract the real instructions from the instruction list. */
 
238
    private void getInstructions() {
 
239
        // munge the linked list of insns we got from ASM into something saner
 
240
        ArrayList<AbstractInsnNode> tempInsnList = new ArrayList< >();
 
241
        insnMap = new HashMap< >();
 
242
        HashMap<AbstractInsnNode, Integer> linesMap = new HashMap< >();
 
243
 
 
244
        for (AbstractInsnNode n = instructions.getFirst(); n != null; n = n.getNext()) {
 
245
            insnMap.put(n, tempInsnList.size());
 
246
            if (isRealInsn(n)) tempInsnList.add(n);
 
247
            if (n.getType() == AbstractInsnNode.LINE) {
 
248
                LineNumberNode nn = (LineNumberNode) n;
 
249
                AbstractInsnNode start = nn.start;
 
250
                while (start != null && !isRealInsn(start)) start = start.getNext();
 
251
                linesMap.put(start, nn.line);
 
252
            }
 
253
        }
 
254
        insnList = tempInsnList.toArray(new AbstractInsnNode[0]);
 
255
 
 
256
        int curLine = 0;
 
257
        lineNumbers = new int[insnList.length];
 
258
 
 
259
        for (int i = 0; i < insnList.length; i++) {
 
260
            Integer ll = linesMap.get(insnList[i]);
 
261
            if (ll != null) curLine = ll.intValue();
 
262
            lineNumbers[i] = curLine;
 
263
        }
 
264
    }
 
265
 
 
266
    /** Build the control flow graph. */
 
267
    private void getControlFlow() {
 
268
        List<ControlEdge> controlTemp = new ArrayList< >();
 
269
        List<ControlEdge>[] succTemps = new List[insnList.length];
 
270
 
 
271
        successors = new ControlEdge[insnList.length][];
 
272
 
 
273
 
 
274
        for (int insnNo = 0; insnNo < insnList.length; insnNo++) {
 
275
            AbstractInsnNode node = insnList[insnNo];
 
276
 
 
277
            List<ControlEdge> succTemp = new ArrayList< >();
 
278
            succTemps[insnNo] = succTemp;
 
279
 
 
280
            switch (node.getType()) {
 
281
                case AbstractInsnNode.JUMP_INSN:
 
282
                    JumpInsnNode ji = (JumpInsnNode) node;
 
283
                    succTemp.add(new ControlEdge(insnNo, insnMap.get(ji.label), null));
 
284
                    if (node.getOpcode() != Opcodes.GOTO)
 
285
                        succTemp.add(new ControlEdge(insnNo, insnNo+1, null));
 
286
                    break;
 
287
 
 
288
                case AbstractInsnNode.TABLESWITCH_INSN:
 
289
                    TableSwitchInsnNode tsi = (TableSwitchInsnNode) node;
 
290
                    succTemp.add(new ControlEdge(insnNo, insnMap.get(tsi.dflt), null));
 
291
                    for (int i = 0; i  < tsi.labels.size(); i++)
 
292
                        succTemp.add(new ControlEdge(insnNo, insnMap.get(tsi.labels.get(i)), null));
 
293
                    break;
 
294
 
 
295
                case AbstractInsnNode.LOOKUPSWITCH_INSN:
 
296
                    LookupSwitchInsnNode lsi = (LookupSwitchInsnNode) node;
 
297
                    succTemp.add(new ControlEdge(insnNo, insnMap.get(lsi.dflt), null));
 
298
                    for (int i = 0; i  < lsi.labels.size(); i++)
 
299
                        succTemp.add(new ControlEdge(insnNo, insnMap.get(lsi.labels.get(i)), null));
 
300
                    break;
 
301
 
 
302
                default:
 
303
                    int opcode = node.getOpcode();
 
304
 
 
305
                    if (! (opcode == Opcodes.ATHROW || opcode >= Opcodes.IRETURN && opcode <= Opcodes.RETURN))
 
306
                        succTemp.add(new ControlEdge(insnNo, insnNo+1, null));
 
307
                    break;
 
308
            }
 
309
        }
 
310
 
 
311
        for (TryCatchBlockNode tcb : (List<TryCatchBlockNode>) tryCatchBlocks) {
 
312
            int start = insnMap.get(tcb.start);
 
313
            int end = insnMap.get(tcb.end);
 
314
            int handler = insnMap.get(tcb.handler);
 
315
            String type = tcb.type == null ? "java/lang/Throwable" : tcb.type;
 
316
 
 
317
            for (int i = start; i < end; i++)
 
318
                succTemps[i].add(new ControlEdge(i, handler, type));
 
319
        }
 
320
 
 
321
        for (int insnNo = 0; insnNo < insnList.length; insnNo++) {
 
322
            successors[insnNo] = succTemps[insnNo].toArray(new ControlEdge[0]);
 
323
            controlTemp.addAll(succTemps[insnNo]);
 
324
        }
 
325
 
 
326
        controlEdges = controlTemp.toArray(new ControlEdge[0]);
 
327
    }
 
328
 
 
329
    private static class StackEffect {
 
330
        public final String[] pop;
 
331
        public final String[] push;
 
332
        public StackEffect(String... ops) {
 
333
            int nul = 0;
 
334
            while (!ops[nul].isEmpty()) nul++;
 
335
            this.pop = Arrays.copyOfRange(ops, 0, nul);
 
336
            this.push = Arrays.copyOfRange(ops, nul+1, ops.length);
 
337
        }
 
338
    }
 
339
 
 
340
    private static final StackEffect[] simpleEffects;
 
341
 
 
342
    static {
 
343
        simpleEffects = new StackEffect[256];
 
344
 
 
345
        simpleEffects[Opcodes.AASTORE] = new StackEffect("L", "I", "L", "");
 
346
        simpleEffects[Opcodes.ACONST_NULL] = new StackEffect("", "0");
 
347
        simpleEffects[Opcodes.ARETURN] = new StackEffect("");
 
348
        simpleEffects[Opcodes.ARRAYLENGTH] = new StackEffect("L", "", "I");
 
349
        simpleEffects[Opcodes.ATHROW] = new StackEffect("");
 
350
        simpleEffects[Opcodes.BALOAD] = new StackEffect("L", "I", "", "I");
 
351
        simpleEffects[Opcodes.BASTORE] = new StackEffect("L", "I", "I", "");
 
352
        simpleEffects[Opcodes.BIPUSH] = new StackEffect("", "I");
 
353
        simpleEffects[Opcodes.CALOAD] = new StackEffect("[C", "I", "", "I");
 
354
        simpleEffects[Opcodes.CASTORE] = new StackEffect("[C", "I", "I", "");
 
355
        simpleEffects[Opcodes.D2F]   = new StackEffect("D", "", "F");
 
356
        simpleEffects[Opcodes.D2I]   = new StackEffect("D", "", "I");
 
357
        simpleEffects[Opcodes.D2L]   = new StackEffect("D", "", "J");
 
358
        simpleEffects[Opcodes.DADD] = new StackEffect("D", "D", "", "D");
 
359
        simpleEffects[Opcodes.DALOAD] = new StackEffect("[D", "I", "", "D");
 
360
        simpleEffects[Opcodes.DASTORE] = new StackEffect("[D", "I", "D", "");
 
361
        simpleEffects[Opcodes.DCMPG] = new StackEffect("D", "D", "", "I");
 
362
        simpleEffects[Opcodes.DCMPL] = new StackEffect("D", "D", "", "I");
 
363
        simpleEffects[Opcodes.DCONST_0] = new StackEffect("", "D");
 
364
        simpleEffects[Opcodes.DCONST_1] = new StackEffect("", "D");
 
365
        simpleEffects[Opcodes.DDIV] = new StackEffect("D", "D", "", "D");
 
366
        simpleEffects[Opcodes.DLOAD] = new StackEffect("", "D");
 
367
        simpleEffects[Opcodes.DMUL] = new StackEffect("D", "D", "", "D");
 
368
        simpleEffects[Opcodes.DNEG] = new StackEffect("D", "", "D");
 
369
        simpleEffects[Opcodes.DREM] = new StackEffect("D", "D", "", "D");
 
370
        simpleEffects[Opcodes.DRETURN] = new StackEffect("");
 
371
        simpleEffects[Opcodes.DSUB] = new StackEffect("D", "D", "", "D");
 
372
        simpleEffects[Opcodes.F2D]   = new StackEffect("F", "", "D");
 
373
        simpleEffects[Opcodes.F2I]   = new StackEffect("F", "", "I");
 
374
        simpleEffects[Opcodes.F2L]   = new StackEffect("F", "", "J");
 
375
        simpleEffects[Opcodes.FADD] = new StackEffect("F", "F", "", "F");
 
376
        simpleEffects[Opcodes.FALOAD] = new StackEffect("[F", "I", "", "F");
 
377
        simpleEffects[Opcodes.FASTORE] = new StackEffect("[F", "I", "F", "");
 
378
        simpleEffects[Opcodes.FCMPG] = new StackEffect("F", "F", "", "I");
 
379
        simpleEffects[Opcodes.FCMPL] = new StackEffect("F", "F", "", "I");
 
380
        simpleEffects[Opcodes.FCONST_0] = new StackEffect("", "F");
 
381
        simpleEffects[Opcodes.FCONST_1] = new StackEffect("", "F");
 
382
        simpleEffects[Opcodes.FCONST_2] = new StackEffect("", "F");
 
383
        simpleEffects[Opcodes.FDIV] = new StackEffect("F", "F", "", "F");
 
384
        simpleEffects[Opcodes.FLOAD] = new StackEffect("", "F");
 
385
        simpleEffects[Opcodes.FMUL] = new StackEffect("F", "F", "", "F");
 
386
        simpleEffects[Opcodes.FNEG] = new StackEffect("F", "", "F");
 
387
        simpleEffects[Opcodes.FREM] = new StackEffect("F", "F", "", "F");
 
388
        simpleEffects[Opcodes.FRETURN] = new StackEffect("");
 
389
        simpleEffects[Opcodes.FSUB] = new StackEffect("F", "F", "", "F");
 
390
        simpleEffects[Opcodes.GOTO] = new StackEffect("");
 
391
        simpleEffects[Opcodes.I2B]   = new StackEffect("I", "", "I");
 
392
        simpleEffects[Opcodes.I2C]   = new StackEffect("I", "", "I");
 
393
        simpleEffects[Opcodes.I2D]   = new StackEffect("I", "", "D");
 
394
        simpleEffects[Opcodes.I2F]   = new StackEffect("I", "", "F");
 
395
        simpleEffects[Opcodes.I2L]   = new StackEffect("I", "", "J");
 
396
        simpleEffects[Opcodes.I2S]   = new StackEffect("I", "", "I");
 
397
        simpleEffects[Opcodes.IADD] = new StackEffect("I", "I", "", "I");
 
398
        simpleEffects[Opcodes.IALOAD] = new StackEffect("[I", "I", "", "I");
 
399
        simpleEffects[Opcodes.IAND]  = new StackEffect("I", "I", "", "I");
 
400
        simpleEffects[Opcodes.IASTORE] = new StackEffect("[I", "I", "I", "");
 
401
        simpleEffects[Opcodes.ICONST_0] = new StackEffect("", "I");
 
402
        simpleEffects[Opcodes.ICONST_1] = new StackEffect("", "I");
 
403
        simpleEffects[Opcodes.ICONST_2] = new StackEffect("", "I");
 
404
        simpleEffects[Opcodes.ICONST_3] = new StackEffect("", "I");
 
405
        simpleEffects[Opcodes.ICONST_4] = new StackEffect("", "I");
 
406
        simpleEffects[Opcodes.ICONST_5] = new StackEffect("", "I");
 
407
        simpleEffects[Opcodes.ICONST_M1] = new StackEffect("", "I");
 
408
        simpleEffects[Opcodes.IDIV] = new StackEffect("I", "I", "", "I");
 
409
        simpleEffects[Opcodes.IFEQ] = new StackEffect("I", "");
 
410
        simpleEffects[Opcodes.IFGE] = new StackEffect("I", "");
 
411
        simpleEffects[Opcodes.IFGT] = new StackEffect("I", "");
 
412
        simpleEffects[Opcodes.IFLE] = new StackEffect("I", "");
 
413
        simpleEffects[Opcodes.IFLT] = new StackEffect("I", "");
 
414
        simpleEffects[Opcodes.IFNE] = new StackEffect("I", "");
 
415
        simpleEffects[Opcodes.IFNONNULL] = new StackEffect("L", "");
 
416
        simpleEffects[Opcodes.IFNULL] = new StackEffect("L", "");
 
417
        simpleEffects[Opcodes.IF_ACMPEQ] = new StackEffect("I", "I", "");
 
418
        simpleEffects[Opcodes.IF_ACMPNE] = new StackEffect("I", "I", "");
 
419
        simpleEffects[Opcodes.IF_ICMPEQ] = new StackEffect("I", "I", "");
 
420
        simpleEffects[Opcodes.IF_ICMPGE] = new StackEffect("I", "I", "");
 
421
        simpleEffects[Opcodes.IF_ICMPGT] = new StackEffect("I", "I", "");
 
422
        simpleEffects[Opcodes.IF_ICMPLE] = new StackEffect("I", "I", "");
 
423
        simpleEffects[Opcodes.IF_ICMPLT] = new StackEffect("I", "I", "");
 
424
        simpleEffects[Opcodes.IF_ICMPNE] = new StackEffect("I", "I", "");
 
425
        simpleEffects[Opcodes.IINC]  = new StackEffect("");
 
426
        simpleEffects[Opcodes.ILOAD] = new StackEffect("", "I");
 
427
        simpleEffects[Opcodes.IMUL] = new StackEffect("I", "I", "", "I");
 
428
        simpleEffects[Opcodes.INEG] = new StackEffect("I", "", "I");
 
429
        simpleEffects[Opcodes.INSTANCEOF] = new StackEffect("L", "", "I");
 
430
        simpleEffects[Opcodes.IOR]   = new StackEffect("I", "I", "", "I");
 
431
        simpleEffects[Opcodes.IREM] = new StackEffect("I", "I", "", "I");
 
432
        simpleEffects[Opcodes.IRETURN] = new StackEffect("");
 
433
        simpleEffects[Opcodes.ISHL]  = new StackEffect("I", "I", "", "I");
 
434
        simpleEffects[Opcodes.ISHR]  = new StackEffect("I", "I", "", "I");
 
435
        simpleEffects[Opcodes.ISUB] = new StackEffect("I", "I", "", "I");
 
436
        simpleEffects[Opcodes.IUSHR] = new StackEffect("I", "I", "", "I");
 
437
        simpleEffects[Opcodes.IXOR]  = new StackEffect("I", "I", "", "I");
 
438
        simpleEffects[Opcodes.L2D]   = new StackEffect("J", "", "D");
 
439
        simpleEffects[Opcodes.L2F]   = new StackEffect("J", "", "F");
 
440
        simpleEffects[Opcodes.L2I]   = new StackEffect("J", "", "I");
 
441
        simpleEffects[Opcodes.LADD] = new StackEffect("J", "J", "", "J");
 
442
        simpleEffects[Opcodes.LALOAD] = new StackEffect("[J", "I", "", "J");
 
443
        simpleEffects[Opcodes.LAND]  = new StackEffect("J", "J", "", "J");
 
444
        simpleEffects[Opcodes.LASTORE] = new StackEffect("[J", "I", "J", "");
 
445
        simpleEffects[Opcodes.LCMP]  = new StackEffect("J", "J", "", "I");
 
446
        simpleEffects[Opcodes.LCONST_0] = new StackEffect("", "J");
 
447
        simpleEffects[Opcodes.LCONST_1] = new StackEffect("", "J");
 
448
        simpleEffects[Opcodes.LDIV] = new StackEffect("J", "J", "", "J");
 
449
        simpleEffects[Opcodes.LLOAD] = new StackEffect("", "J");
 
450
        simpleEffects[Opcodes.LMUL] = new StackEffect("J", "J", "", "J");
 
451
        simpleEffects[Opcodes.LNEG] = new StackEffect("J", "", "J");
 
452
        simpleEffects[Opcodes.LOOKUPSWITCH] = new StackEffect("I", "");
 
453
        simpleEffects[Opcodes.LOR]   = new StackEffect("J", "J", "", "J");
 
454
        simpleEffects[Opcodes.LREM] = new StackEffect("J", "J", "", "J");
 
455
        simpleEffects[Opcodes.LRETURN] = new StackEffect("");
 
456
        simpleEffects[Opcodes.LSHL]  = new StackEffect("J", "I", "", "J");
 
457
        simpleEffects[Opcodes.LSHR]  = new StackEffect("J", "I", "", "J");
 
458
        simpleEffects[Opcodes.LSUB] = new StackEffect("J", "J", "", "J");
 
459
        simpleEffects[Opcodes.LUSHR] = new StackEffect("J", "I", "", "J");
 
460
        simpleEffects[Opcodes.LXOR]  = new StackEffect("J", "J", "", "J");
 
461
        simpleEffects[Opcodes.MONITORENTER] = new StackEffect("L", "");
 
462
        simpleEffects[Opcodes.MONITOREXIT] = new StackEffect("L", "");
 
463
        simpleEffects[Opcodes.NOP] = new StackEffect("");
 
464
        simpleEffects[Opcodes.PUTFIELD] = new StackEffect("X", "");
 
465
        simpleEffects[Opcodes.PUTSTATIC] = new StackEffect("X", "X", "");
 
466
        simpleEffects[Opcodes.RETURN]  = new StackEffect("");
 
467
        simpleEffects[Opcodes.SALOAD] = new StackEffect("[S", "I", "", "I");
 
468
        simpleEffects[Opcodes.SASTORE] = new StackEffect("[S", "I", "I", "");
 
469
        simpleEffects[Opcodes.SIPUSH] = new StackEffect("", "I");
 
470
        simpleEffects[Opcodes.TABLESWITCH] = new StackEffect("I", "");
 
471
 
 
472
    }
 
473
 
 
474
    private void printControlFlow() {
 
475
        for (int i = 0; i < insnList.length; i++) {
 
476
            System.out.printf("%5d: %s\n", i, insnList[i]);
 
477
            for (ControlEdge ce : successors[i])
 
478
                System.out.printf("     %5d -> %d %s\n", ce.from, ce.to, ce.exn == null ? "-" : ce.exn);
 
479
        }
 
480
    }
 
481
 
 
482
    /** Infer types. */
 
483
    private static class Frame {
 
484
        public String[] stack;
 
485
        public int sp;
 
486
        public int sbase;
 
487
 
 
488
        public Frame(String[] stack, int sp, int sbase) {
 
489
            this.stack = stack.clone(); this.sp = sp; this.sbase = sbase;
 
490
        }
 
491
 
 
492
        public Frame clone() {
 
493
            return new Frame(stack, sp, sbase);
 
494
        }
 
495
 
 
496
        public void grow(int len) {
 
497
            if (len <= stack.length) return;
 
498
 
 
499
            int olen = stack.length;
 
500
            stack = Arrays.copyOf(stack, len);
 
501
            Arrays.fill(stack, olen, len, "T");
 
502
        }
 
503
 
 
504
        public String describe() {
 
505
            return String.format("locals=[%s] stack=[%s]", Arrays.toString(Arrays.copyOfRange(stack, 0, sbase)), Arrays.toString(Arrays.copyOfRange(stack, sbase, sp)));
 
506
        }
 
507
 
 
508
        public void thrown(String ex) {
 
509
            sp = sbase;
 
510
            stack[sp++] = ('L'+ex+';').intern();
 
511
        }
 
512
 
 
513
        private void pushReturn(String s) {
 
514
            switch (s.charAt(0)) {
 
515
                case 'V': break;
 
516
                case 'B': case 'Z': case 'S': case 'C': stack[sp++] = "I"; break;
 
517
                default: stack[sp++] = s; break;
 
518
            }
 
519
        }
 
520
 
 
521
        public void execute(int index, AbstractInsnNode anode) {
 
522
            StackEffect simp = simpleEffects[anode.getOpcode()];
 
523
 
 
524
            if (stack.length < sp + 5) grow(sp+8);// room for all fixed effects and a bit to spare
 
525
 
 
526
            if (simp != null) {
 
527
                sp -= simp.pop.length;
 
528
                if (sp < sbase) throw new RuntimeException("stack underflow");
 
529
                if (stack.length < sp + simp.push.length)
 
530
                    stack = Arrays.copyOf(stack, sp + simp.push.length);
 
531
                for (String s : simp.push)
 
532
                    stack[sp++] = s;
 
533
                return;
 
534
            }
 
535
 
 
536
            VarInsnNode vi = null;
 
537
            TypeInsnNode ti = null;
 
538
            FieldInsnNode fi = null;
 
539
            String tidesc = null;
 
540
            MethodInsnNode mi = null;
 
541
            Type midesc = null;
 
542
 
 
543
            switch (anode.getType()) {
 
544
                case AbstractInsnNode.VAR_INSN:
 
545
                    vi = (VarInsnNode) anode;
 
546
                    if (vi.var != 0 && ("D" == stack[vi.var-1] || "J" == stack[vi.var-1]))
 
547
                        stack[vi.var-1] = "T";
 
548
                    break;
 
549
                case AbstractInsnNode.TYPE_INSN:
 
550
                    ti = (TypeInsnNode) anode;
 
551
                    tidesc = ti.desc.charAt(0) == '[' ? ti.desc : ("L" + ti.desc + ";");
 
552
                    break;
 
553
                case AbstractInsnNode.METHOD_INSN:
 
554
                    mi = (MethodInsnNode) anode;
 
555
                    midesc = Type.getMethodType(mi.desc);
 
556
                    break;
 
557
                case AbstractInsnNode.INVOKE_DYNAMIC_INSN:
 
558
                    midesc = Type.getMethodType(((InvokeDynamicInsnNode)anode).desc);
 
559
                    break;
 
560
                case AbstractInsnNode.FIELD_INSN:
 
561
                    fi = (FieldInsnNode) anode;
 
562
                    break;
 
563
            }
 
564
 
 
565
            String a,b,c,d;
 
566
            int opcode = anode.getOpcode();
 
567
            switch (opcode) {
 
568
                case Opcodes.AALOAD:
 
569
                    stack[sp-2] = stack[sp-2].substring(1);
 
570
                    sp--;
 
571
                    break;
 
572
                case Opcodes.ALOAD:
 
573
                    stack[sp++] = stack[vi.var];
 
574
                    break;
 
575
                case Opcodes.ANEWARRAY:
 
576
                    stack[sp-1] = ("[" + tidesc).intern();
 
577
                    break;
 
578
                case Opcodes.ASTORE:
 
579
                    stack[vi.var] = stack[--sp];
 
580
                    break;
 
581
                case Opcodes.CHECKCAST:
 
582
                    stack[sp-1] = tidesc.intern();
 
583
                    break;
 
584
                case Opcodes.DSTORE:
 
585
                    stack[vi.var] = "D";
 
586
                    stack[vi.var+1] = "T";
 
587
                    sp--;
 
588
                    break;
 
589
                case Opcodes.DUP2:
 
590
                    // [b] a -> [b] a [b] a
 
591
                    a = stack[--sp];
 
592
                    b = ("D" == a || "J" == a) ? "X" : stack[--sp];
 
593
 
 
594
                    if (!"X".equals(b)) stack[sp++] = b;
 
595
                    stack[sp++] = a;
 
596
                    if (!"X".equals(b)) stack[sp++] = b;
 
597
                    stack[sp++] = a;
 
598
                    break;
 
599
                case Opcodes.DUP2_X1:
 
600
                    // c [b] a -> [b] a c [b] a
 
601
                    a = stack[--sp];
 
602
                    b = ("D" == a || "J" == a) ? "X" : stack[--sp];
 
603
                    c = stack[--sp];
 
604
 
 
605
                    if ("X" != b) stack[sp++] = b;
 
606
                    stack[sp++] = a;
 
607
                    stack[sp++] = c;
 
608
                    if ("X" != b) stack[sp++] = b;
 
609
                    stack[sp++] = a;
 
610
                    break;
 
611
                case Opcodes.DUP2_X2:
 
612
                    // [d] c [b] a -> b a d c b a
 
613
                    a = stack[--sp];
 
614
                    b = ("D" == a || "J" == a) ? "X" : stack[--sp];
 
615
                    c = stack[--sp];
 
616
                    d = ("D" == c || "J" == c) ? "X" : stack[--sp];
 
617
 
 
618
                    if ("X" != b) stack[sp++] = b;
 
619
                    stack[sp++] = a;
 
620
                    if ("X" != d) stack[sp++] = d;
 
621
                    stack[sp++] = c;
 
622
                    if ("X" != b) stack[sp++] = b;
 
623
                    stack[sp++] = a;
 
624
 
 
625
                    break;
 
626
                case Opcodes.DUP:
 
627
                    // D, J invalid...
 
628
                    stack[sp] = stack[sp-1];
 
629
                    sp++;
 
630
                    break;
 
631
                case Opcodes.DUP_X1:
 
632
                    // b a -> a b a
 
633
                    a = stack[--sp];
 
634
                    b = stack[--sp];
 
635
 
 
636
                    stack[sp++] = a;
 
637
                    stack[sp++] = b;
 
638
                    stack[sp++] = a;
 
639
                    break;
 
640
 
 
641
                case Opcodes.DUP_X2:
 
642
                    // [d] c a -> a [d] c a
 
643
                    a = stack[--sp];
 
644
                    c = stack[--sp];
 
645
                    d = ("D" == c || "J" == c) ? "X" : stack[--sp];
 
646
 
 
647
                    stack[sp++] = a;
 
648
                    if ("X" != d) stack[sp++] = d;
 
649
                    stack[sp++] = c;
 
650
                    stack[sp++] = a;
 
651
                    break;
 
652
                case Opcodes.FSTORE:
 
653
                    stack[vi.var] = "F";
 
654
                    sp--;
 
655
                    break;
 
656
 
 
657
                case Opcodes.GETFIELD:
 
658
                    sp--;
 
659
                    pushReturn(fi.desc.intern());
 
660
                    break;
 
661
 
 
662
                case Opcodes.GETSTATIC:
 
663
                    pushReturn(fi.desc.intern());
 
664
                    break;
 
665
 
 
666
                case Opcodes.INVOKEINTERFACE:
 
667
                case Opcodes.INVOKESPECIAL:
 
668
                case Opcodes.INVOKESTATIC:
 
669
                case Opcodes.INVOKEVIRTUAL:
 
670
                case Opcodes.INVOKEDYNAMIC:
 
671
                    sp -= midesc.getArgumentTypes().length; // pop arguments
 
672
                    if (opcode != Opcodes.INVOKESTATIC && opcode != Opcodes.INVOKEDYNAMIC) {
 
673
                        a = stack[--sp]; // pop this
 
674
                        // initialize
 
675
                        if (a.charAt(0) == 'U') {
 
676
                            b = a.substring(a.indexOf(':')+1).intern();
 
677
                            for (int i = 0; i < stack.length; i++)
 
678
                                if (a == stack[i]) stack[i] = b;
 
679
                        }
 
680
                    }
 
681
                    pushReturn(midesc.getReturnType().getDescriptor().intern());
 
682
                    break;
 
683
 
 
684
                case Opcodes.ISTORE:
 
685
                    stack[vi.var] = "I";
 
686
                    sp--;
 
687
                    break;
 
688
 
 
689
        //simpleEffects[Opcodes.JSR] = new StackEffect(null);
 
690
 
 
691
                case Opcodes.LDC:
 
692
                    {
 
693
                        Object cst = ((LdcInsnNode)anode).cst;
 
694
                        if (cst instanceof Integer)             { stack[sp++] = "I"; break; }
 
695
                        if (cst instanceof Byte)                { stack[sp++] = "I"; break; }
 
696
                        if (cst instanceof Character)           { stack[sp++] = "I"; break; }
 
697
                        if (cst instanceof Short)               { stack[sp++] = "I"; break; }
 
698
                        if (cst instanceof Boolean)             { stack[sp++] = "I"; break; }
 
699
                        if (cst instanceof Float)               { stack[sp++] = "F"; break; }
 
700
                        if (cst instanceof Long)                { stack[sp++] = "J"; break; }
 
701
                        if (cst instanceof Double)              { stack[sp++] = "D"; break; }
 
702
                        if (cst instanceof String)              { stack[sp++] = "Ljava/lang/String;"; break; }
 
703
                        if (cst instanceof Type)                { stack[sp++] = ((Type)cst).getSort() == Type.METHOD ? "Ljava/lang/invoke/MethodType;" : "Ljava/lang/Class;"; break; }
 
704
                        if (cst instanceof Handle)              { stack[sp++] = "Ljava/lang/invoke/MethodHandle;"; break; }
 
705
                        throw new RuntimeException("Unknown constant type "+cst);
 
706
                    }
 
707
 
 
708
                case Opcodes.LSTORE:
 
709
                    stack[vi.var] = "J";
 
710
                    stack[vi.var+1] = "T";
 
711
                    sp--;
 
712
                    break;
 
713
 
 
714
                case Opcodes.MULTIANEWARRAY:
 
715
                    {
 
716
                        MultiANewArrayInsnNode m = (MultiANewArrayInsnNode)anode;
 
717
                        sp -= m.dims;
 
718
                        stack[sp++] = m.desc;
 
719
                    }
 
720
                    break;
 
721
 
 
722
                case Opcodes.NEWARRAY:
 
723
                    {
 
724
                        int type = ((IntInsnNode)anode).operand;
 
725
                        switch (type) {
 
726
                            case Opcodes.T_BOOLEAN: stack[sp++] = "[Z"; break;
 
727
                            case Opcodes.T_CHAR: stack[sp++] = "[C"; break;
 
728
                            case Opcodes.T_FLOAT: stack[sp++] = "[F"; break;
 
729
                            case Opcodes.T_DOUBLE: stack[sp++] = "[D"; break;
 
730
                            case Opcodes.T_BYTE: stack[sp++] = "[B"; break;
 
731
                            case Opcodes.T_SHORT: stack[sp++] = "[S"; break;
 
732
                            case Opcodes.T_INT: stack[sp++] = "[I"; break;
 
733
                            case Opcodes.T_LONG: stack[sp++] = "[J"; break;
 
734
                            default: throw new RuntimeException("NEWARRAY "+type);
 
735
                        }
 
736
                        break;
 
737
                    }
 
738
 
 
739
                case Opcodes.NEW:
 
740
                    stack[sp++] = ("U"+index+':'+tidesc).intern();
 
741
                    break;
 
742
 
 
743
                case Opcodes.POP2:
 
744
                    // [d] c ->
 
745
                    c = stack[--sp];
 
746
                    d = ("D".equals(c) || "J".equals(c)) ? "X" : stack[--sp];
 
747
                    break;
 
748
                case Opcodes.POP:
 
749
                    sp--;
 
750
                    break;
 
751
        //simpleEffects[Opcodes.RET] = new StackEffect(null);
 
752
                case Opcodes.SWAP:
 
753
                    a = stack[--sp];
 
754
                    b = stack[--sp];
 
755
                    stack[sp++] = a;
 
756
                    stack[sp++] = b;
 
757
                    break;
 
758
                default:
 
759
                    throw new RuntimeException("unimplemented opcode " + anode.getOpcode());
 
760
            }
 
761
        }
 
762
    }
 
763
 
 
764
    private static class TypeInference {
 
765
        public Frame[] frames;
 
766
        int[] changedQueue;
 
767
        int changedHead;
 
768
        int changedTail;
 
769
        boolean[] changedVec;
 
770
 
 
771
 
 
772
        public TypeInference(int size) {
 
773
            frames = new Frame[size];
 
774
 
 
775
            changedQueue = new int[size+1];
 
776
            changedVec = new boolean[size];
 
777
        }
 
778
 
 
779
        public int next() {
 
780
            if (changedHead == changedTail) return -1;
 
781
            int n = changedQueue[changedTail++];
 
782
            if (changedTail == changedQueue.length) changedTail = 0;
 
783
            changedVec[n] = false;
 
784
            return n;
 
785
        }
 
786
 
 
787
        public void merge(int index, Frame f) {
 
788
            Frame slot = frames[index];
 
789
            if (slot == null) {
 
790
                frames[index] = f.clone();
 
791
                mark(index);
 
792
                return;
 
793
            }
 
794
            slot.grow(f.stack.length);
 
795
            f.grow(slot.stack.length);
 
796
 
 
797
            if (f.sp != slot.sp) throw new RuntimeException(String.format("Insn %d can be reached with stack sizes of %d and %d", index, f.sp-f.sbase, slot.sp-slot.sbase));
 
798
 
 
799
            boolean changed = false;
 
800
            if (TYPE_TRACE) System.out.printf("MERGE INSN=%d\nOLD=   [%s]\nINPUT= [%s]\n", index, slot.describe(), f.describe());
 
801
            for (int i = 0; i < f.sp; i++) {
 
802
                String a = f.stack[i];
 
803
                String b = slot.stack[i];
 
804
                String c = lub(a,b);
 
805
                if (b != c) {
 
806
                    //System.out.printf("%d.%d %s -> %s\n", index, i, b, c);
 
807
                    if (DEBUG_FRAGMENT && a != c && b != c) System.out.printf("%d.%d  %s | %s => %s\n", index, i, a, b, c);
 
808
                    slot.stack[i] = c;
 
809
                    changed = true;
 
810
                }
 
811
            }
 
812
            if (TYPE_TRACE) System.out.printf("OUTPUT=[%s]\n%s\n", slot.describe(), changed ? "CHANGED" : "");
 
813
 
 
814
            if (changed) mark(index);
 
815
        }
 
816
 
 
817
        void mark(int index) {
 
818
            if (changedVec[index]) return;
 
819
            changedVec[index] = true;
 
820
            changedQueue[changedHead++] = index;
 
821
            if (changedHead == changedQueue.length) changedHead = 0;
 
822
        }
 
823
 
 
824
        // computes the least upper bound of two verification types; we use descriptors, but U44:Lbar; for uninitialized(44), 0 for null, and T for TOP
 
825
        String lub(String a,String b) {
 
826
            // same type?  trivial
 
827
            if (a == b) return a;
 
828
            if (a == "T") return a;
 
829
            if (b == "T") return b;
 
830
 
 
831
            char a0 = a.charAt(0);
 
832
            char b0 = b.charAt(0);
 
833
 
 
834
            // types other than initialized references cannot validly merge with anything
 
835
            if (a0 != '0' && a0 != 'L' && a0 != '[') return "T";
 
836
            if (b0 != '0' && b0 != 'L' && b0 != '[') return "T";
 
837
 
 
838
            // null is the bottom of what remains
 
839
            if (a0 == '0') return b;
 
840
            if (b0 == '0') return a;
 
841
 
 
842
            // an array and a non-array can merge only to Object
 
843
            if (a0 == '[') {
 
844
                if (b0 != '[') return "Ljava/lang/Object;";
 
845
 
 
846
                // array types are covariant
 
847
                String cc = lub(a.substring(1), b.substring(1));
 
848
                if (cc.charAt(0) == 'T') // children are not compatible, but we know we have *some* array, which is an object
 
849
                    return "Ljava/lang/Object;";
 
850
                return ('['+cc).intern();
 
851
            } else {
 
852
                if (b0 != 'L') return "Ljava/lang/Object;";
 
853
 
 
854
                // at this point in a real verifier we would load the named classes and use their common superclass
 
855
                // lub(P6OpaqueInstance, CodeRef) = SixModelObject
 
856
                // punt.
 
857
                if (a == "Lorg/perl6/nqp/runtime/CodeRef;" && b == "Lorg/perl6/nqp/sixmodel/SixModelObject;") return b;
 
858
                if (b == "Lorg/perl6/nqp/runtime/CodeRef;" && a == "Lorg/perl6/nqp/sixmodel/SixModelObject;") return a;
 
859
 
 
860
                return "Ljava/lang/Object;";
 
861
            }
 
862
        }
 
863
    }
 
864
 
 
865
    private void getTypes() {
 
866
        // first, establish a locals size so that we can merge locals and stacks
 
867
        nlocal = Type.getArgumentsAndReturnSizes(desc) >> 2;
 
868
        if ((access & Opcodes.ACC_STATIC) != 0) nlocal--;
 
869
 
 
870
        for (AbstractInsnNode an : insnList) {
 
871
            if (an.getType() != AbstractInsnNode.VAR_INSN) continue;
 
872
            int size = (an.getOpcode() == Opcodes.DSTORE || an.getOpcode() == Opcodes.LSTORE) ? 2 : 1;
 
873
            nlocal = Math.max(nlocal, ((VarInsnNode)an).var + size);
 
874
        }
 
875
 
 
876
        TypeInference state = new TypeInference(insnList.length);
 
877
        Frame initial = new Frame(new String[0], 0, 0);
 
878
        initial.grow(nlocal+10);
 
879
 
 
880
        int locwp = 0;
 
881
 
 
882
        if ((access & Opcodes.ACC_STATIC) == 0) {
 
883
            initial.stack[locwp++] = ('L'+tgtype+';').intern();
 
884
        }
 
885
        for (Type arg : Type.getArgumentTypes(desc)) {
 
886
            initial.stack[locwp] = arg.getDescriptor().intern();
 
887
            locwp += arg.getSize();
 
888
        }
 
889
        initial.sp = initial.sbase = nlocal;
 
890
        state.merge(0, initial);
 
891
 
 
892
        int insn;
 
893
        int step = 0;
 
894
        while ((insn = state.next()) >= 0) {
 
895
            Frame in = state.frames[insn].clone();
 
896
 
 
897
            if (TYPE_TRACE) System.out.printf("INFERENCE STEP: insn=%d [%d] locals=[%s] stack=[%s]\n", insn, insnList[insn].getOpcode(), Arrays.toString(Arrays.copyOfRange(in.stack, 0, nlocal)), Arrays.toString(Arrays.copyOfRange(in.stack, in.sbase, in.sp)));
 
898
            in.execute(insn, insnList[insn]);
 
899
 
 
900
            for (ControlEdge ce : successors[insn]) {
 
901
                // assume exceptions follow non-exceptions
 
902
                if (ce.exn != null) in.thrown(ce.exn);
 
903
                state.merge(ce.to, in);
 
904
            }
 
905
            step++;
 
906
            if (DEBUG_FRAGMENT && (step % 10000) == 0) System.out.printf("Inference step %d\n", step);
 
907
        }
 
908
        types = state.frames;
 
909
 
 
910
        if (DEBUG_FRAGMENT) {
 
911
            Map<String,Integer> histog = new HashMap< >();
 
912
            for (Frame fr : types) {
 
913
                for (int i = 0; i < fr.sp; i++) {
 
914
                    Integer r = histog.get(fr.stack[i]);
 
915
                    histog.put(fr.stack[i], r == null ? 1 : 1+r);
 
916
                }
 
917
            }
 
918
            for (Map.Entry<String,Integer> ent : histog.entrySet())
 
919
                System.out.printf("%s : %d\n", ent.getKey(), ent.getValue());
 
920
        }
 
921
    }
 
922
 
 
923
    private int insnSize(AbstractInsnNode ai) {
 
924
        int opc = ai.getOpcode();
 
925
        switch (ai.getType()) {
 
926
            case AbstractInsnNode.INSN:
 
927
                return 1;
 
928
            case AbstractInsnNode.INT_INSN:
 
929
                return (opc == Opcodes.SIPUSH) ? 3 : 2;
 
930
            case AbstractInsnNode.VAR_INSN:
 
931
                {
 
932
                    int var = ((VarInsnNode)ai).var;
 
933
                    return (var < 4 && opc != Opcodes.RET) ? 1 : (var >= 256) ? 4 : 2;
 
934
                }
 
935
            case AbstractInsnNode.TYPE_INSN:
 
936
                return 3;
 
937
            case AbstractInsnNode.FIELD_INSN:
 
938
                return 3;
 
939
            case AbstractInsnNode.METHOD_INSN:
 
940
                return (opc == Opcodes.INVOKEINTERFACE) ? 5 : 3;
 
941
            case AbstractInsnNode.INVOKE_DYNAMIC_INSN:
 
942
                return 5;
 
943
            case AbstractInsnNode.JUMP_INSN:
 
944
                return (opc == Opcodes.GOTO || opc == Opcodes.JSR) ? 5 : 8;
 
945
            case AbstractInsnNode.LDC_INSN:
 
946
                return 3;
 
947
            case AbstractInsnNode.IINC_INSN:
 
948
                {
 
949
                    IincInsnNode ii = (IincInsnNode) ai;
 
950
                    return (ii.var >= 256 || ii.incr > 127 || ii.incr < -128) ? 6 : 3;
 
951
                }
 
952
            case AbstractInsnNode.TABLESWITCH_INSN:
 
953
                {
 
954
                    TableSwitchInsnNode si = (TableSwitchInsnNode) ai;
 
955
                    return 16 + si.labels.size() * 4;
 
956
                }
 
957
            case AbstractInsnNode.LOOKUPSWITCH_INSN:
 
958
                {
 
959
                    LookupSwitchInsnNode si = (LookupSwitchInsnNode) ai;
 
960
                    return 12 + si.labels.size() * 8;
 
961
                }
 
962
            case AbstractInsnNode.MULTIANEWARRAY_INSN:
 
963
                return 4;
 
964
            default:
 
965
                return 0;
 
966
        }
 
967
    }
 
968
 
 
969
    // loosely based on the codesizeevaluator; 
 
970
    private void getBaselineSize() {
 
971
        baselineSize = new int[insnList.length+1];
 
972
 
 
973
        int accum=0;
 
974
 
 
975
        for (int i = 0; i < insnList.length; i++) {
 
976
            AbstractInsnNode ai = insnList[i];
 
977
            MethodInsnNode mi;
 
978
            int size = insnSize(ai);
 
979
 
 
980
            // some of these require special handling
 
981
            switch (ai.getOpcode()) {
 
982
                case Opcodes.RETURN:
 
983
                    // iconst_m1; ireturn
 
984
                    size = 2;
 
985
                    break;
 
986
                case Opcodes.IRETURN:
 
987
                case Opcodes.FRETURN:
 
988
                case Opcodes.LRETURN:
 
989
                case Opcodes.DRETURN:
 
990
                case Opcodes.ARETURN:
 
991
                    // xstore tmp[0-2]; aload buf; iconst_0; new java/lang/Wrapper; dup; xload tmp; invokespecial; aastore; iconst_m1; ireturn
 
992
                    size = 1+(nlocal >= 254 ? 4 : 2)+1+3+1+1+3+1+1+1;
 
993
                    break;
 
994
                // Opcodes.NEW may be rewritten into aconst_null if a spill is needed, but that doesn't affect the max
 
995
                case Opcodes.INVOKESPECIAL:
 
996
                    mi = (MethodInsnNode) ai;
 
997
                    if ("<init>".equals(mi.name)) {
 
998
                        int skeep = 0;
 
999
                        Frame f1 = types[i];
 
1000
                        Frame f2 = types[i+1];
 
1001
                        String uninit = f1.stack[f2.sp];
 
1002
 
 
1003
                        while (skeep < f1.sp && !uninit.equals(f1.stack[skeep])) skeep++;
 
1004
 
 
1005
                        size = 0;
 
1006
                        int ltmp = nlocal + 2; /*buf*/
 
1007
                        // spill everything relevant above skeep into locals
 
1008
                        for (int j = skeep; j < f1.sp; j++) {
 
1009
                            if (uninit.equals(f1.stack[j])) continue;
 
1010
                            size += (ltmp < 256) ? 2 : 4;
 
1011
                            ltmp += 2;
 
1012
                        }
 
1013
                        ltmp++; // keep a copy of the value
 
1014
 
 
1015
                        int argc = Type.getArgumentTypes(mi.desc).length;
 
1016
 
 
1017
                        // newobj, dup, unspill, invokespecial
 
1018
                        size += 3 + 1 + argc*(ltmp < 256 ? 2 : 4) + 3;
 
1019
 
 
1020
                        // store in locals, including <tmp>
 
1021
                        for (int j = 0; j < nlocal; j++) {
 
1022
                            if (uninit.equals(f1.stack[j]))
 
1023
                                size += 1 + (j < 256 ? 2 : 4);
 
1024
                        }
 
1025
                        size += (ltmp < 256 ? 2 : 4);
 
1026
                        // unspill
 
1027
                        size += (ltmp < 256 ? 2 : 4) * (f2.sp - skeep);
 
1028
                    }
 
1029
                    break;
 
1030
            }
 
1031
 
 
1032
            baselineSize[i] = accum;
 
1033
            accum += size;
 
1034
        }
 
1035
        baselineSize[insnList.length] = accum;
 
1036
 
 
1037
        if (DEBUG_CONTROL) System.out.println(Arrays.toString(baselineSize));
 
1038
    }
 
1039
 
 
1040
    private int[][] nonlocalEntryExit(int from, int to) {
 
1041
        // need to include entry trampolines and exit trampolines
 
1042
        int[] entryPts = new int[to-from];
 
1043
        int entryCt = 0;
 
1044
        boolean[] entryDedup = new boolean[to-from];
 
1045
        int[] exitPts = new int[insnList.length];
 
1046
        int exitCt = 0;
 
1047
        boolean[] exitDedup = new boolean[insnList.length];
 
1048
 
 
1049
        for (ControlEdge ce : controlEdges) {
 
1050
            boolean from_this = (ce.from >= from && ce.from < to);
 
1051
            boolean to_this   = (ce.to >= from && ce.to < to);
 
1052
            if (!from_this && to_this && !entryDedup[ce.to-from]) {
 
1053
                entryDedup[ce.to-from] = true;
 
1054
                entryPts[entryCt++] = ce.to;
 
1055
            }
 
1056
            if (from_this && !to_this && !exitDedup[ce.to]) {
 
1057
                exitDedup[ce.to] = true;
 
1058
                exitPts[exitCt++] = ce.to;
 
1059
            }
 
1060
        }
 
1061
 
 
1062
        if (from == 0 && !entryDedup[0]) {
 
1063
            entryPts[entryCt++] = 0;
 
1064
        }
 
1065
 
 
1066
        entryPts = Arrays.copyOf(entryPts, entryCt);
 
1067
        exitPts = Arrays.copyOf(exitPts, exitCt);
 
1068
        Arrays.sort(entryPts);
 
1069
        Arrays.sort(exitPts);
 
1070
 
 
1071
        if (DEBUG_CONTROL) {
 
1072
            System.out.printf("NONLOCAL ENTRY: %s\n", Arrays.toString(entryPts));
 
1073
            System.out.printf("NONLOCAL EXIT: %s\n", Arrays.toString(exitPts));
 
1074
        }
 
1075
        return new int[][] { entryPts, exitPts };
 
1076
    }
 
1077
 
 
1078
    private int calcFragmentSize(int from, int to) {
 
1079
        // we have to include the instructions
 
1080
        int base = baselineSize[to] - baselineSize[from];
 
1081
 
 
1082
        int[][] ee = nonlocalEntryExit(from, to);
 
1083
        int[] entryPts = ee[0];
 
1084
        int[] exitPts = ee[1];
 
1085
        // factor out commonalities from the trampolines
 
1086
        String[] commonEntry = commonTrampoline(entryPts, null);
 
1087
        String[] commonExit  = commonTrampoline(exitPts, null);
 
1088
 
 
1089
        // common entry code
 
1090
        // iload; aload; {dup; ipush; aaload; UNBOX; xstore; }; swap; tableswitch
 
1091
 
 
1092
        int centry = 2;
 
1093
        for (int i = 0; i < commonEntry.length; i++) {
 
1094
            centry += localEntrySize(i, commonEntry[i]);
 
1095
        }
 
1096
        centry += 13; // swap+tswitch
 
1097
 
 
1098
        // uncommon entry code
 
1099
        int uentry = 0;
 
1100
 
 
1101
        for (int ept : entryPts) {
 
1102
            uentry += 4; // dispatch vector
 
1103
            Frame f = types[ept];
 
1104
            for (int j = 0; j < f.sp; j++) {
 
1105
                if (j < commonEntry.length && commonEntry[j].equals(f.stack[j])) {
 
1106
                    /* no action */
 
1107
                } else if (j < nlocal) {
 
1108
                    uentry += localEntrySize(j, f.stack[j]);
 
1109
                } else {
 
1110
                    uentry += stackEntrySize(j, f.stack[j]);
 
1111
                }
 
1112
            }
 
1113
            uentry += (nlocal <= 255 ? 2 : 4); // astore
 
1114
            uentry += 5; // final jump
 
1115
        }
 
1116
 
 
1117
        // jump insertion
 
1118
        int uexit = 3;
 
1119
 
 
1120
        // uncommon exit code
 
1121
        for (int pt : exitPts) {
 
1122
            Frame f = types[pt];
 
1123
            for (int j = 0; j < f.sp; j++) {
 
1124
                if (j < commonExit.length && commonExit[j].equals(f.stack[j])) {
 
1125
                    /* no action */
 
1126
                } else if (j < nlocal) {
 
1127
                    uexit += localExitSize(j, f.stack[j]);
 
1128
                } else {
 
1129
                    uexit += stackExitSize(j, f.stack[j]);
 
1130
                }
 
1131
            }
 
1132
            uexit += (nlocal <= 255 ? 2 : 4); // aload in middle
 
1133
            uexit += 3; // ipush
 
1134
            uexit += 5; // jump to combiner
 
1135
        }
 
1136
 
 
1137
        // common exit code
 
1138
        int cexit = 1; // swap
 
1139
        for (int i = 0; i < commonExit.length; i++) {
 
1140
            cexit += localExitSize(i, commonExit[i]);
 
1141
        }
 
1142
        cexit += 2; // pop; ireturn
 
1143
 
 
1144
        int total = centry + uentry + base + uexit + cexit;
 
1145
 
 
1146
        if (DEBUG_FRAGMENT) System.out.printf("calcSize: %d-%d : centry(%d) uentry(%d) base(%d) uexit(%d) cexit(%d) total(%d)\n", from, to, centry, uentry, base, uexit, cexit, total);
 
1147
 
 
1148
        return total;
 
1149
    }
 
1150
 
 
1151
    private int localEntrySize(int loc, String desc) {
 
1152
        char c0 = desc.charAt(0);
 
1153
        if (c0 == 'T') return 0; // not loaded
 
1154
        int sz;
 
1155
        switch (c0) {
 
1156
            case '0':
 
1157
            case 'U':
 
1158
                // just load as a null
 
1159
                sz = 1;
 
1160
                break;
 
1161
            case 'L':
 
1162
            case '[':
 
1163
                // dup, ipush, aaload, checkcast
 
1164
                sz = (loc < 128) ? 7 : 8;
 
1165
                break;
 
1166
            default:
 
1167
                // dup, ipush, aaload, checkcast, fooValue
 
1168
                sz = (loc < 128) ? 10 : 11;
 
1169
                break;
 
1170
        }
 
1171
        return sz + ((loc < 256) ? 2 : 4);
 
1172
    }
 
1173
 
 
1174
    private int localExitSize(int loc, String desc) {
 
1175
        char c0 = desc.charAt(0);
 
1176
        if (c0 == 'T' || c0 == '0' || c0 == 'U') return 0; // not saved
 
1177
        int sz = (loc < 256) ? 2 : 4;
 
1178
        switch (c0) {
 
1179
            case 'L':
 
1180
            case '[':
 
1181
                // dup, ipush, xload, aastore
 
1182
                return sz + ((loc < 128) ? 4 : 5);
 
1183
            default:
 
1184
                // dup, ipush, new, dup, xload, invokespecial, aastore
 
1185
                return sz + ((loc < 128) ? 11 : 12);
 
1186
        }
 
1187
    }
 
1188
 
 
1189
    private int stackEntrySize(int loc, String desc) {
 
1190
        char c0 = desc.charAt(0);
 
1191
        switch (c0) {
 
1192
            case '0':
 
1193
            case 'U':
 
1194
                // just load as a null
 
1195
                return 1;
 
1196
            case 'L':
 
1197
            case '[':
 
1198
                // aload, ipush, aaload, checkcast
 
1199
                return (loc < 128) ? 10 : 11;
 
1200
            default:
 
1201
                // aload, ipush, aaload, checkcast, fooValue
 
1202
                return (loc < 128) ? 13 : 14;
 
1203
        }
 
1204
    }
 
1205
 
 
1206
    private int stackExitSize(int loc, String desc) {
 
1207
        char c0 = desc.charAt(0);
 
1208
        if (c0 == 'T' || c0 == '0' || c0 == 'U') return 1; // not saved
 
1209
        switch (c0) {
 
1210
            case 'L':
 
1211
            case '[':
 
1212
                // xstore, aload, ipush, xload, aastore
 
1213
                return (loc < 128) ? 15 : 16;
 
1214
            default:
 
1215
                // xstore, aload, ipush, new, dup, xload, invokespecial, aastore
 
1216
                return (loc < 128) ? 22 : 23;
 
1217
        }
 
1218
    }
 
1219
 
 
1220
    private String[] commonTrampoline(int[] points, Set<String> spills) {
 
1221
        String[] common = null;
 
1222
        for (int i = 0; i < points.length; i++) {
 
1223
            Frame f = types[points[i]];
 
1224
            if (spills != null) {
 
1225
                for (int j = 0; j < f.sp; j++) spills.add(f.stack[j]);
 
1226
            }
 
1227
            if (common == null) {
 
1228
                common = Arrays.copyOf(f.stack, nlocal);
 
1229
            } else {
 
1230
                for (int j = 0; j < common.length; j++) {
 
1231
                    if (j >= f.sp || !f.stack[j].equals(common[j]))
 
1232
                        common[j] = "T";
 
1233
                }
 
1234
            }
 
1235
        }
 
1236
        return common == null ? new String[] { } : common;
 
1237
    }
 
1238
 
 
1239
    private void allocateJumpNrs(int begin, int end) {
 
1240
        int[][] ee = nonlocalEntryExit(begin, end);
 
1241
 
 
1242
        int firstEntry = nextJumpNo;
 
1243
        for (int entry : ee[0]) {
 
1244
            jumpNoMap[entry] = nextJumpNo++;
 
1245
        }
 
1246
        firstJump.add(firstEntry);
 
1247
 
 
1248
        if (DEBUG_FRAGMENT) System.out.printf("Fragment %d-%d has jump numbers %d-%d\n", begin, end, firstEntry, nextJumpNo);
 
1249
    }
 
1250
 
 
1251
    private void emitFragment(int fno, int begin, int end) {
 
1252
 
 
1253
        MethodVisitor v = target.visitMethod(Opcodes.ACC_STATIC | Opcodes.ACC_PRIVATE | Opcodes.ACC_SYNTHETIC, name+"$f"+fno, "(I[Ljava/lang/Object;)I", null, null);
 
1254
        v.visitCode();
 
1255
 
 
1256
        int[][] ee = nonlocalEntryExit(begin, end);
 
1257
        int[] entryPts = ee[0];
 
1258
        int[] exitPts = ee[1];
 
1259
        // factor out commonalities from the trampolines
 
1260
        Set<String> spilledUTypes = new HashSet< >();
 
1261
        String[] commonEntry = commonTrampoline(entryPts, spilledUTypes);
 
1262
        String[] commonExit  = commonTrampoline(exitPts, spilledUTypes);
 
1263
 
 
1264
        Label[] entryTrampolineLabels = new Label[entryPts.length];
 
1265
        for (int i = 0; i < entryPts.length; i++)
 
1266
            entryTrampolineLabels[i] = new Label();
 
1267
 
 
1268
        Map<Integer, Label> exitTrampolineLabels = new HashMap< >();
 
1269
        for (int i = 0; i < exitPts.length; i++)
 
1270
            exitTrampolineLabels.put(exitPts[i], new Label());
 
1271
 
 
1272
        Label[] insnLabels = new Label[end - begin + 1];
 
1273
        for (int i = 0; i < end - begin + 1; i++)
 
1274
            insnLabels[i] = new Label();
 
1275
 
 
1276
        // common entry code
 
1277
        // aload; {dup; ipush; aaload; UNBOX; xstore; }; iload; tableswitch
 
1278
        v.visitVarInsn(Opcodes.ILOAD, 0);
 
1279
        v.visitVarInsn(Opcodes.ALOAD, 1);
 
1280
 
 
1281
        for (int i = 0; i < commonEntry.length; i++) {
 
1282
            localEntryCode(v, i, commonEntry[i]);
 
1283
        }
 
1284
        v.visitInsn(Opcodes.SWAP);
 
1285
        int firstj = firstJump.get(fno);
 
1286
        v.visitTableSwitchInsn(firstj, firstj + entryPts.length - 1, entryTrampolineLabels[0] /*XXX*/, entryTrampolineLabels);
 
1287
 
 
1288
        int stash = nlocal;
 
1289
        int scratch = nlocal+1;
 
1290
 
 
1291
        // emit salient tryblocks
 
1292
        for (TryCatchBlockNode tcbn : (List<TryCatchBlockNode>) tryCatchBlocks) {
 
1293
            int nstart = Math.max(begin, insnMap.get(tcbn.start));
 
1294
            int nend   = Math.min(end, insnMap.get(tcbn.end));
 
1295
            int nhndlr = insnMap.get(tcbn.handler);
 
1296
            if (nstart >= nend) continue;
 
1297
 
 
1298
            v.visitTryCatchBlock(insnLabels[nstart - begin], insnLabels[nend - begin],
 
1299
                    exitTrampolineLabels.containsKey(nhndlr) ? exitTrampolineLabels.get(nhndlr) : insnLabels[nhndlr - begin],
 
1300
                    tcbn.type);
 
1301
        }
 
1302
 
 
1303
        // uncommon entry code
 
1304
        for (int ept : entryPts) {
 
1305
            v.visitLabel(entryTrampolineLabels[jumpNoMap[ept]-firstj]);
 
1306
            Frame f = types[ept];
 
1307
            for (int j = 0; j < nlocal; j++) {
 
1308
                if (j < commonEntry.length && commonEntry[j].equals(f.stack[j]))
 
1309
                    continue;
 
1310
                localEntryCode(v, j, f.stack[j]);
 
1311
            }
 
1312
            v.visitVarInsn(Opcodes.ASTORE, stash);
 
1313
            for (int j = nlocal; j < f.sp; j++) {
 
1314
                stackEntryCode(v, stash, j, f.stack[j]);
 
1315
            }
 
1316
            v.visitJumpInsn(Opcodes.GOTO, insnLabels[ept - begin]);
 
1317
        }
 
1318
 
 
1319
        // we have to include the instructions
 
1320
        for (int iix = begin; iix < end; iix++) {
 
1321
            emitFragmentInsn(v, iix, begin, insnLabels, exitTrampolineLabels, spilledUTypes);
 
1322
        }
 
1323
        v.visitLabel(insnLabels[end - begin]);
 
1324
 
 
1325
        boolean fallthru = false;
 
1326
        for (ControlEdge ce : successors[end-1]) {
 
1327
            if (ce.to == end) {
 
1328
                fallthru = true;
 
1329
                break;
 
1330
            }
 
1331
        }
 
1332
 
 
1333
        if (fallthru)
 
1334
            v.visitJumpInsn(Opcodes.GOTO, exitTrampolineLabels.get(end));
 
1335
 
 
1336
        int lineno = -1;
 
1337
        for (int i = begin; i < end; i++) {
 
1338
            if (lineNumbers[i] != lineno) {
 
1339
                lineno = lineNumbers[i];
 
1340
                v.visitLineNumber(lineno, insnLabels[i-begin]);
 
1341
            }
 
1342
        }
 
1343
 
 
1344
        Label commonExitLabel = new Label();
 
1345
 
 
1346
        // uncommon exit code
 
1347
        for (int pt : exitPts) {
 
1348
            v.visitLabel(exitTrampolineLabels.get(pt));
 
1349
            Frame f = types[pt];
 
1350
            for (int j = f.sp-1; j >= nlocal; j--) {
 
1351
                stackExitCode(v, stash, scratch, j, f.stack[j]);
 
1352
            }
 
1353
            v.visitVarInsn(Opcodes.ALOAD, stash);
 
1354
            for (int j = 0; j < nlocal; j++) {
 
1355
                if (j < commonExit.length && commonExit[j].equals(f.stack[j]))
 
1356
                    continue;
 
1357
 
 
1358
                localExitCode(v, j, f.stack[j]);
 
1359
            }
 
1360
            pushInt(v, jumpNoMap[pt]);
 
1361
            v.visitJumpInsn(Opcodes.GOTO, commonExitLabel);
 
1362
        }
 
1363
 
 
1364
        // common exit code
 
1365
        if (exitPts.length > 0) {
 
1366
            v.visitLabel(commonExitLabel);
 
1367
            v.visitInsn(Opcodes.SWAP);
 
1368
            for (int i = 0; i < commonExit.length; i++) {
 
1369
                localExitCode(v, i, commonExit[i]);
 
1370
            }
 
1371
            v.visitInsn(Opcodes.POP);
 
1372
            v.visitInsn(Opcodes.IRETURN);
 
1373
        }
 
1374
        v.visitMaxs(0,0);
 
1375
        v.visitEnd();
 
1376
    }
 
1377
 
 
1378
    private String[] box_types = new String[] { "java/lang/Integer", "java/lang/Long", "java/lang/Float", "java/lang/Double" };
 
1379
    private String[] box_descs = new String[] { "(I)V", "(J)V", "(F)V", "(D)V" };
 
1380
 
 
1381
    private void emitFragmentInsn(MethodVisitor v, int iix, int begin, Label[] insnLabels, Map<Integer,Label> exitTrampolineLabels, Set<String> spilledUTypes) {
 
1382
        v.visitLabel(insnLabels[iix - begin]);
 
1383
        AbstractInsnNode ai = insnList[iix];
 
1384
 
 
1385
        // some instructions require very special handling
 
1386
        int opc = ai.getOpcode();
 
1387
        if (opc == Opcodes.RETURN) {
 
1388
            v.visitInsn(Opcodes.ICONST_M1);
 
1389
            v.visitInsn(Opcodes.IRETURN);
 
1390
            return;
 
1391
        }
 
1392
 
 
1393
        if (opc >= Opcodes.IRETURN && opc <= Opcodes.ARETURN) {
 
1394
            int t = opc - Opcodes.IRETURN;
 
1395
            v.visitVarInsn(Opcodes.ISTORE + t, nlocal+1);
 
1396
            v.visitVarInsn(Opcodes.ALOAD, nlocal);
 
1397
            v.visitInsn(Opcodes.ICONST_0);
 
1398
            if (opc != Opcodes.ARETURN) {
 
1399
                v.visitTypeInsn(Opcodes.NEW, box_types[t]);
 
1400
                v.visitInsn(Opcodes.DUP);
 
1401
                v.visitVarInsn(Opcodes.ILOAD + t, nlocal+1);
 
1402
                v.visitMethodInsn(Opcodes.INVOKESPECIAL, box_types[t], "<init>", box_descs[t]);
 
1403
            } else {
 
1404
                v.visitVarInsn(Opcodes.ILOAD + t, nlocal+1);
 
1405
            }
 
1406
            v.visitInsn(Opcodes.AASTORE);
 
1407
            v.visitInsn(Opcodes.ICONST_M1);
 
1408
            v.visitInsn(Opcodes.IRETURN);
 
1409
            return;
 
1410
        }
 
1411
 
 
1412
        if (opc == Opcodes.NEW) {
 
1413
            Frame f = types[iix+1];
 
1414
            if (spilledUTypes.contains(f.stack[f.sp-1])) {
 
1415
                v.visitInsn(Opcodes.ACONST_NULL);
 
1416
                return;
 
1417
            }
 
1418
        }
 
1419
 
 
1420
        if (opc == Opcodes.INVOKESPECIAL) {
 
1421
            MethodInsnNode mi = (MethodInsnNode)ai;
 
1422
            Frame f1 = types[iix];
 
1423
            Frame f2 = types[iix+1];
 
1424
            String uninit = f1.stack[f2.sp];
 
1425
            if (mi.name.equals("<init>") && spilledUTypes.contains(uninit)) {
 
1426
                if (!f2.stack[f2.sp-1].equals(uninit)) throw new RuntimeException("general case of INVOKESPECIAL spill not implemented");
 
1427
                for (int i = 0; i < f2.sp-1; i++) if (f2.stack[i].equals(uninit)) throw new RuntimeException("general case of INVOKESPECIAL spill not implemented");
 
1428
 
 
1429
                int ltmp = nlocal+1;
 
1430
                int argc = Type.getArgumentTypes(mi.desc).length;
 
1431
                int[] spillarg = new int[argc];
 
1432
 
 
1433
                for (int d = 0; d < argc; d++) {
 
1434
                    char ty0 = f1.stack[f1.sp-d-1].charAt(0);
 
1435
 
 
1436
                    spillarg[d] = ltmp;
 
1437
                    v.visitVarInsn(ty0 == 'D' ? Opcodes.DSTORE : ty0 == 'J' ? Opcodes.LSTORE : ty0 == 'I' ? Opcodes.ISTORE : ty0 == 'F' ? Opcodes.FSTORE : Opcodes.ASTORE, ltmp);
 
1438
                    ltmp += (ty0 == 'D' || ty0 == 'J') ? 2 : 1;
 
1439
                }
 
1440
                v.visitInsn(Opcodes.POP2);
 
1441
                v.visitTypeInsn(Opcodes.NEW, mi.owner);
 
1442
                v.visitInsn(Opcodes.DUP);
 
1443
 
 
1444
                for (int d = argc-1; d >= 0; d++) {
 
1445
                    char ty0 = f1.stack[f1.sp-d-1].charAt(0);
 
1446
                    v.visitVarInsn(ty0 == 'D' ? Opcodes.DLOAD : ty0 == 'J' ? Opcodes.LLOAD : ty0 == 'I' ? Opcodes.ILOAD : ty0 == 'F' ? Opcodes.FLOAD : Opcodes.ALOAD, spillarg[d]);
 
1447
                }
 
1448
 
 
1449
                v.visitMethodInsn(Opcodes.INVOKESPECIAL, mi.owner, mi.name, mi.desc);
 
1450
                return;
 
1451
            }
 
1452
        }
 
1453
 
 
1454
        // all other instructions can be processed normally, perhaps with some control-flow fudging
 
1455
 
 
1456
        switch (ai.getType()) {
 
1457
            case AbstractInsnNode.JUMP_INSN:
 
1458
                {
 
1459
                    JumpInsnNode ji = (JumpInsnNode)ai;
 
1460
                    v.visitJumpInsn(opc, mapLabel(ji.label, begin, insnLabels, exitTrampolineLabels));
 
1461
                    break;
 
1462
                }
 
1463
            case AbstractInsnNode.TABLESWITCH_INSN:
 
1464
                {
 
1465
                    TableSwitchInsnNode si = (TableSwitchInsnNode)ai;
 
1466
                    Label[] mapped = new Label[si.labels.size()];
 
1467
                    for (int i = 0; i < mapped.length; i++)
 
1468
                        mapped[i] = mapLabel((LabelNode)si.labels.get(i), begin, insnLabels, exitTrampolineLabels);
 
1469
                    v.visitTableSwitchInsn(si.min, si.max, mapLabel(si.dflt, begin, insnLabels, exitTrampolineLabels), mapped);
 
1470
                    break;
 
1471
                }
 
1472
            case AbstractInsnNode.LOOKUPSWITCH_INSN:
 
1473
                {
 
1474
                    LookupSwitchInsnNode si = (LookupSwitchInsnNode)ai;
 
1475
                    Label[] mapped = new Label[si.labels.size()];
 
1476
                    for (int i = 0; i < mapped.length; i++)
 
1477
                        mapped[i] = mapLabel((LabelNode)si.labels.get(i), begin, insnLabels, exitTrampolineLabels);
 
1478
                    int[] keys = new int[si.keys.size()];
 
1479
                    for (int i = 0; i < keys.length; i++)
 
1480
                        keys[i] = (int)si.keys.get(i);
 
1481
                    v.visitLookupSwitchInsn(mapLabel(si.dflt, begin, insnLabels, exitTrampolineLabels), keys, mapped);
 
1482
                    break;
 
1483
                }
 
1484
            default:
 
1485
                ai.accept(v);
 
1486
                break;
 
1487
        }
 
1488
    }
 
1489
 
 
1490
    private Label mapLabel(LabelNode ln, int begin, Label[] insnLabels, Map<Integer,Label> exitTrampolineLabels) {
 
1491
        int lni = insnMap.get(ln);
 
1492
        if (exitTrampolineLabels.containsKey(lni))
 
1493
            return exitTrampolineLabels.get(lni);
 
1494
 
 
1495
        return insnLabels[lni - begin];
 
1496
    }
 
1497
 
 
1498
 
 
1499
    private void localEntryCode(MethodVisitor v, int loc, String desc) {
 
1500
        char c0 = desc.charAt(0);
 
1501
        if (c0 == 'T') return; // not loaded
 
1502
        int sz;
 
1503
        switch (c0) {
 
1504
            case '0':
 
1505
            case 'U':
 
1506
                // just load as a null
 
1507
                v.visitInsn(Opcodes.ACONST_NULL);
 
1508
                break;
 
1509
            case 'L':
 
1510
            case '[':
 
1511
                // dup, ipush, aaload, checkcast
 
1512
                v.visitInsn(Opcodes.DUP);
 
1513
                pushInt(v, loc);
 
1514
                v.visitInsn(Opcodes.AALOAD);
 
1515
                if (!desc.equals("Ljava/lang/Object;")) v.visitTypeInsn(Opcodes.CHECKCAST, c0 == '[' ? desc : desc.substring(1, desc.length()-1));
 
1516
                break;
 
1517
            default:
 
1518
                // dup, ipush, aaload, checkcast, fooValue
 
1519
                v.visitInsn(Opcodes.DUP);
 
1520
                pushInt(v, loc);
 
1521
                v.visitInsn(Opcodes.AALOAD);
 
1522
                unbox(v, c0);
 
1523
                v.visitVarInsn( c0=='I' ? Opcodes.ISTORE : c0=='J' ? Opcodes.LSTORE : c0=='F' ? Opcodes.FSTORE : Opcodes.DSTORE, loc );
 
1524
                return;
 
1525
        }
 
1526
        v.visitVarInsn(Opcodes.ASTORE, loc);
 
1527
    }
 
1528
 
 
1529
    private void pushInt(MethodVisitor v, int value) {
 
1530
        if (value >= -1 && value <= 5)
 
1531
            v.visitInsn(Opcodes.ICONST_0 + value);
 
1532
        else if (value >= -128 && value <= 127)
 
1533
            v.visitIntInsn(Opcodes.BIPUSH, value);
 
1534
        else if (value >= -32768 && value <= 32767)
 
1535
            v.visitIntInsn(Opcodes.SIPUSH, value);
 
1536
        else
 
1537
            v.visitLdcInsn(value);
 
1538
    }
 
1539
 
 
1540
    private void unbox(MethodVisitor v, char c0) {
 
1541
        String c,m,d;
 
1542
        switch (c0) {
 
1543
            case 'I': c = "java/lang/Integer"; m = "intValue";    d = "()I"; break;
 
1544
            case 'J': c = "java/lang/Long";    m = "longValue";   d = "()J"; break;
 
1545
            case 'F': c = "java/lang/Float";   m = "floatValue";  d = "()F"; break;
 
1546
            case 'D': c = "java/lang/Double";  m = "doubleValue"; d = "()D"; break;
 
1547
            default: throw new IllegalArgumentException();
 
1548
        }
 
1549
        v.visitTypeInsn(Opcodes.CHECKCAST, c);
 
1550
        v.visitMethodInsn(Opcodes.INVOKEVIRTUAL, c, m, d);
 
1551
    }
 
1552
 
 
1553
    private void localExitCode(MethodVisitor v, int loc, String desc) {
 
1554
        char c0 = desc.charAt(0);
 
1555
        if (c0 == 'T' || c0 == '0' || c0 == 'U') return; // not saved
 
1556
        switch (c0) {
 
1557
            case 'L':
 
1558
            case '[':
 
1559
                v.visitInsn(Opcodes.DUP);
 
1560
                pushInt(v, loc);
 
1561
                v.visitVarInsn(Opcodes.ALOAD, loc);
 
1562
                v.visitInsn(Opcodes.AASTORE);
 
1563
                break;
 
1564
            default:
 
1565
                v.visitInsn(Opcodes.DUP);
 
1566
                pushInt(v, loc);
 
1567
                {
 
1568
                    String ty;
 
1569
                    int load;
 
1570
                    switch (c0) {
 
1571
                        case 'I': ty = "java/lang/Integer"; load = Opcodes.ILOAD; break;
 
1572
                        case 'J': ty = "java/lang/Long"; load = Opcodes.LLOAD; break;
 
1573
                        case 'F': ty = "java/lang/Float"; load = Opcodes.FLOAD; break;
 
1574
                        case 'D': ty = "java/lang/Double"; load = Opcodes.DLOAD; break;
 
1575
                        default: throw new IllegalArgumentException(desc);
 
1576
                    }
 
1577
 
 
1578
                    v.visitTypeInsn(Opcodes.NEW, ty);
 
1579
                    v.visitInsn(Opcodes.DUP);
 
1580
                    v.visitVarInsn(load, loc);
 
1581
                    v.visitMethodInsn(Opcodes.INVOKESPECIAL, ty, "<init>", "("+c0+")V");
 
1582
                }
 
1583
                v.visitInsn(Opcodes.AASTORE);
 
1584
                break;
 
1585
        }
 
1586
    }
 
1587
 
 
1588
    private void stackEntryCode(MethodVisitor v, int stash, int loc, String desc) {
 
1589
        char c0 = desc.charAt(0);
 
1590
        switch (c0) {
 
1591
            case '0':
 
1592
            case 'U':
 
1593
                v.visitInsn(Opcodes.ACONST_NULL);
 
1594
                break;
 
1595
            case 'L':
 
1596
            case '[':
 
1597
                v.visitVarInsn(Opcodes.ALOAD, stash);
 
1598
                pushInt(v, loc);
 
1599
                v.visitInsn(Opcodes.AALOAD);
 
1600
                if (!desc.equals("Ljava/lang/Object;")) v.visitTypeInsn(Opcodes.CHECKCAST, c0 == '[' ? desc : desc.substring(1, desc.length()-1));
 
1601
                break;
 
1602
            default:
 
1603
                v.visitVarInsn(Opcodes.ALOAD, stash);
 
1604
                pushInt(v, loc);
 
1605
                v.visitInsn(Opcodes.AALOAD);
 
1606
                unbox(v, c0);
 
1607
                break;
 
1608
        }
 
1609
    }
 
1610
 
 
1611
    private void stackExitCode(MethodVisitor v, int stash, int scratch, int loc, String desc) {
 
1612
        char c0 = desc.charAt(0);
 
1613
        if (c0 == 'T' || c0 == '0' || c0 == 'U') {
 
1614
            v.visitInsn(Opcodes.POP);
 
1615
            return;
 
1616
        }
 
1617
        String ty;
 
1618
        int load, store;
 
1619
        switch (c0) {
 
1620
            case 'L':
 
1621
            case '[':
 
1622
                v.visitVarInsn(Opcodes.ASTORE, scratch);
 
1623
                v.visitVarInsn(Opcodes.ALOAD, stash);
 
1624
                pushInt(v, loc);
 
1625
                v.visitVarInsn(Opcodes.ALOAD, scratch);
 
1626
                v.visitInsn(Opcodes.AASTORE);
 
1627
                return;
 
1628
            case 'I': ty = "java/lang/Integer"; load = Opcodes.ILOAD; store = Opcodes.ISTORE; break;
 
1629
            case 'J': ty = "java/lang/Long"; load = Opcodes.LLOAD; store = Opcodes.LSTORE; break;
 
1630
            case 'F': ty = "java/lang/Float"; load = Opcodes.FLOAD; store = Opcodes.FSTORE; break;
 
1631
            case 'D': ty = "java/lang/Double"; load = Opcodes.DLOAD; store = Opcodes.DSTORE; break;
 
1632
            default: throw new IllegalArgumentException(desc);
 
1633
        }
 
1634
 
 
1635
        v.visitVarInsn(store, scratch);
 
1636
        v.visitVarInsn(Opcodes.ALOAD, stash);
 
1637
        pushInt(v, loc);
 
1638
        v.visitTypeInsn(Opcodes.NEW, ty);
 
1639
        v.visitInsn(Opcodes.DUP);
 
1640
        v.visitVarInsn(load, scratch);
 
1641
        v.visitMethodInsn(Opcodes.INVOKESPECIAL, ty, "<init>", "("+c0+")V");
 
1642
        v.visitInsn(Opcodes.AASTORE);
 
1643
    }
 
1644
 
 
1645
    private void becomeWrapper() {
 
1646
        int maxStack = 0;
 
1647
        for (Frame f : types)
 
1648
            maxStack = Math.max(maxStack, f.sp);
 
1649
 
 
1650
        tryCatchBlocks = null;
 
1651
        localVariables = null;
 
1652
        instructions.clear();
 
1653
 
 
1654
        // allocate the scratchpad
 
1655
        instructions.add(intNode(maxStack));
 
1656
        instructions.add(new TypeInsnNode(Opcodes.ANEWARRAY, "java/lang/Object"));
 
1657
        // move the arguments onto the scratchpad
 
1658
        int ltmp = 0;
 
1659
        if ((access & Opcodes.ACC_STATIC) == 0) ltmp += saveArg(instructions, ltmp, Type.getType(Object.class));
 
1660
        for (Type at : Type.getArgumentTypes(desc)) ltmp += saveArg(instructions, ltmp, at);
 
1661
 
 
1662
        instructions.add(new VarInsnNode(Opcodes.ASTORE, 0));
 
1663
        instructions.add(intNode(0));
 
1664
        instructions.add(new VarInsnNode(Opcodes.ISTORE, 1));
 
1665
 
 
1666
        LabelNode loop = new LabelNode();
 
1667
        instructions.add(loop);
 
1668
 
 
1669
        for (int i = firstJump.size() - 1; i >= 0; i--) {
 
1670
            LabelNode not_my_problem = new LabelNode();
 
1671
            instructions.add(new VarInsnNode(Opcodes.ILOAD, 1));
 
1672
            instructions.add(intNode(firstJump.get(i)));
 
1673
            instructions.add(new JumpInsnNode(Opcodes.IF_ICMPLT, not_my_problem));
 
1674
            instructions.add(new VarInsnNode(Opcodes.ILOAD, 1));
 
1675
            instructions.add(new VarInsnNode(Opcodes.ALOAD, 0));
 
1676
            instructions.add(new MethodInsnNode(Opcodes.INVOKESTATIC, tgtype, name + "$f" + i, "(I[Ljava/lang/Object;)I"));
 
1677
            instructions.add(new VarInsnNode(Opcodes.ISTORE, 1));
 
1678
            instructions.add(new JumpInsnNode(Opcodes.GOTO, loop));
 
1679
            instructions.add(not_my_problem);
 
1680
        }
 
1681
 
 
1682
        // time for return
 
1683
        String rty = null, unboxName = null, unboxDesc = null;
 
1684
        int retinst;
 
1685
        Type rtyty = Type.getReturnType(desc);
 
1686
        switch (rtyty.getSort()) {
 
1687
            case Type.VOID:
 
1688
                retinst = Opcodes.RETURN; break;
 
1689
            case Type.BOOLEAN:
 
1690
            case Type.CHAR:
 
1691
            case Type.INT:
 
1692
            case Type.SHORT:
 
1693
            case Type.BYTE:
 
1694
                retinst = Opcodes.IRETURN; rty = "java/lang/Integer"; unboxName = "intValue"; unboxDesc = "()I"; break;
 
1695
            case Type.LONG:
 
1696
                retinst = Opcodes.LRETURN; rty = "java/lang/Long"; unboxName = "longValue"; unboxDesc = "()J"; break;
 
1697
            case Type.FLOAT:
 
1698
                retinst = Opcodes.FRETURN; rty = "java/lang/Float"; unboxName = "floatValue"; unboxDesc = "()F"; break;
 
1699
            case Type.DOUBLE:
 
1700
                retinst = Opcodes.DRETURN; rty = "java/lang/Double"; unboxName = "doubleValue"; unboxDesc = "()D"; break;
 
1701
            default:
 
1702
                retinst = Opcodes.ARETURN; rty = rtyty.getInternalName(); break;
 
1703
        }
 
1704
 
 
1705
        if (rty != null) {
 
1706
            instructions.add(new VarInsnNode(Opcodes.ALOAD, 0));
 
1707
            instructions.add(new InsnNode(Opcodes.ICONST_0));
 
1708
            instructions.add(new InsnNode(Opcodes.AALOAD));
 
1709
            instructions.add(new TypeInsnNode(Opcodes.CHECKCAST, rty));
 
1710
            if (unboxName != null)
 
1711
                instructions.add(new MethodInsnNode(Opcodes.INVOKEVIRTUAL, rty, unboxName, unboxDesc));
 
1712
        }
 
1713
        instructions.add(new InsnNode(retinst));
 
1714
    }
 
1715
 
 
1716
    private int saveArg(InsnList il, int ltmp, Type at) {
 
1717
        il.add(new InsnNode(Opcodes.DUP));
 
1718
        il.add(intNode(ltmp));
 
1719
        int opc;
 
1720
        String ty = null, desc = null;
 
1721
        switch (at.getSort()) {
 
1722
            case Type.BOOLEAN:
 
1723
            case Type.CHAR:
 
1724
            case Type.INT:
 
1725
            case Type.SHORT:
 
1726
            case Type.BYTE:
 
1727
                opc = Opcodes.ILOAD; ty = "java/lang/Integer"; desc = "(I)V"; break;
 
1728
            case Type.LONG:
 
1729
                opc = Opcodes.LLOAD; ty = "java/lang/Long"; desc = "(J)V"; break;
 
1730
            case Type.FLOAT:
 
1731
                opc = Opcodes.FLOAD; ty = "java/lang/Float"; desc = "(F)V"; break;
 
1732
            case Type.DOUBLE:
 
1733
                opc = Opcodes.DLOAD; ty = "java/lang/Double"; desc = "(D)V"; break;
 
1734
            default:
 
1735
                opc = Opcodes.ALOAD; break;
 
1736
        }
 
1737
 
 
1738
        if (ty != null) {
 
1739
            il.add(new TypeInsnNode(Opcodes.NEW, ty));
 
1740
            il.add(new InsnNode(Opcodes.DUP));
 
1741
        }
 
1742
        il.add(new VarInsnNode(opc, ltmp));
 
1743
        if (ty != null) il.add(new MethodInsnNode(Opcodes.INVOKESPECIAL, ty, "<init>", desc));
 
1744
        il.add(new InsnNode(Opcodes.AASTORE));
 
1745
        return at.getSize();
 
1746
    }
 
1747
}