Source code

001/*
002 * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved.
003 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
004 *
005 * This code is free software; you can redistribute it and/or modify it
006 * under the terms of the GNU General Public License version 2 only, as
007 * published by the Free Software Foundation.
008 *
009 * This code is distributed in the hope that it will be useful, but WITHOUT
010 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
011 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
012 * version 2 for more details (a copy is included in the LICENSE file that
013 * accompanied this code).
014 *
015 * You should have received a copy of the GNU General Public License version
016 * 2 along with this work; if not, write to the Free Software Foundation,
017 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
018 *
019 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
020 * or visit www.oracle.com if you need additional information or have any
021 * questions.
022 */
023package com.oracle.graal.truffle.test;
024
025import java.util.*;
026
027import org.junit.*;
028
029import com.oracle.truffle.api.*;
030import com.oracle.truffle.api.CompilerDirectives.CompilationFinal;
031import com.oracle.truffle.api.frame.*;
032import com.oracle.truffle.api.nodes.*;
033
034public class BytecodeInterpreterPartialEvaluationTest extends PartialEvaluationTest {
035
036    public static class Bytecode {
037        public static final byte CONST = 0;
038        public static final byte RETURN = 1;
039        public static final byte ADD = 2;
040        public static final byte IFZERO = 3;
041        public static final byte POP = 4;
042        public static final byte JMP = 5;
043        public static final byte DUP = 6;
044    }
045
046    public static boolean TRACE = false;
047
048    public static class Program extends RootNode {
049        private final String name;
050        @CompilationFinal private final byte[] bytecodes;
051        @CompilationFinal private final FrameSlot[] locals;
052        @CompilationFinal private final FrameSlot[] stack;
053
054        public Program(String name, byte[] bytecodes, int maxLocals, int maxStack) {
055            super(MockLanguage.class, null, null);
056            this.name = name;
057            this.bytecodes = bytecodes;
058            locals = new FrameSlot[maxLocals];
059            stack = new FrameSlot[maxStack];
060            for (int i = 0; i < maxLocals; ++i) {
061                locals[i] = this.getFrameDescriptor().addFrameSlot("local" + i);
062                locals[i].setKind(FrameSlotKind.Int);
063            }
064            for (int i = 0; i < maxStack; ++i) {
065                stack[i] = this.getFrameDescriptor().addFrameSlot("stack" + i);
066                stack[i].setKind(FrameSlotKind.Int);
067            }
068        }
069
070        protected void setInt(VirtualFrame frame, int stackIndex, int value) {
071            frame.setInt(stack[stackIndex], value);
072        }
073
074        protected int getInt(VirtualFrame frame, int stackIndex) {
075            try {
076                return frame.getInt(stack[stackIndex]);
077            } catch (FrameSlotTypeException e) {
078                throw new IllegalStateException("Error accessing stack slot " + stackIndex);
079            }
080        }
081
082        @Override
083        public String toString() {
084            return name;
085        }
086
087        public void trace(String format, Object... args) {
088            if (CompilerDirectives.inInterpreter() && TRACE) {
089                System.out.println(String.format(format, args));
090            }
091        }
092
093        @Override
094        @ExplodeLoop(merge = true)
095        public Object execute(VirtualFrame frame) {
096            trace("Start program");
097            int topOfStack = -1;
098            int bci = 0;
099            while (true) {
100                CompilerAsserts.partialEvaluationConstant(bci);
101                byte bc = bytecodes[bci];
102                byte value = 0;
103                switch (bc) {
104                    case Bytecode.CONST:
105                        value = bytecodes[bci + 1];
106                        trace("%d (%d): CONST %s", bci, topOfStack, value);
107                        setInt(frame, ++topOfStack, value);
108                        bci = bci + 2;
109                        continue;
110
111                    case Bytecode.RETURN:
112                        trace("%d (%d): RETURN", bci, topOfStack);
113                        return getInt(frame, topOfStack);
114
115                    case Bytecode.ADD: {
116                        int left = getInt(frame, topOfStack);
117                        int right = getInt(frame, topOfStack - 1);
118                        trace("%d (%d): ADD %d %d", bci, topOfStack, left, right);
119                        setInt(frame, topOfStack - 1, left + right);
120                        topOfStack--;
121                        bci = bci + 1;
122                        continue;
123                    }
124
125                    case Bytecode.IFZERO:
126                        trace("%d (%d): IFZERO", bci, topOfStack);
127                        if (getInt(frame, topOfStack--) == 0) {
128                            bci = bytecodes[bci + 1];
129                            continue;
130                        } else {
131                            bci = bci + 2;
132                            continue;
133                        }
134
135                    case Bytecode.POP:
136                        trace("%d (%d): POP", bci, topOfStack);
137                        topOfStack--;
138                        bci++;
139                        continue;
140
141                    case Bytecode.JMP:
142                        trace("%d (%d): JMP", bci, topOfStack);
143                        bci = bytecodes[bci + 1];
144                        continue;
145
146                    case Bytecode.DUP:
147                        trace("%d (%d): DUP", bci, topOfStack);
148                        setInt(frame, topOfStack + 1, getInt(frame, topOfStack));
149                        topOfStack++;
150                        bci++;
151                        continue;
152                }
153            }
154        }
155    }
156
157    public static Object constant42() {
158        return 42;
159    }
160
161    private static void assertReturns42(RootNode program) {
162        Assert.assertEquals(Integer.valueOf(42), Truffle.getRuntime().createCallTarget(program).call());
163    }
164
165    private void assertPartialEvalEqualsAndRunsCorrect(RootNode program) {
166        assertReturns42(program);
167        assertPartialEvalEquals("constant42", program);
168    }
169
170    @Test
171    public void constReturnProgram() {
172        byte[] bytecodes = new byte[]{
173        /* 0: */Bytecode.CONST,
174        /* 1: */42,
175        /* 2: */Bytecode.RETURN};
176        assertPartialEvalEqualsAndRunsCorrect(new Program("constReturnProgram", bytecodes, 0, 2));
177    }
178
179    @Test
180    public void constAddProgram() {
181        byte[] bytecodes = new byte[]{
182        /* 0: */Bytecode.CONST,
183        /* 1: */40,
184        /* 2: */Bytecode.CONST,
185        /* 3: */2,
186        /* 4: */Bytecode.ADD,
187        /* 5: */Bytecode.RETURN};
188        assertPartialEvalEqualsAndRunsCorrect(new Program("constAddProgram", bytecodes, 0, 2));
189    }
190
191    @Test
192    public void simpleIfProgram() {
193        byte[] bytecodes = new byte[]{
194        /* 0: */Bytecode.CONST,
195        /* 1: */40,
196        /* 2: */Bytecode.CONST,
197        /* 3: */1,
198        /* 4: */Bytecode.IFZERO,
199        /* 5: */8,
200        /* 6: */Bytecode.CONST,
201        /* 7: */42,
202        /* 8: */Bytecode.RETURN};
203        assertPartialEvalEqualsAndRunsCorrect(new Program("simpleIfProgram", bytecodes, 0, 3));
204    }
205
206    @Test
207    public void ifAndPopProgram() {
208        byte[] bytecodes = new byte[]{
209        /* 0: */Bytecode.CONST,
210        /* 1: */40,
211        /* 2: */Bytecode.CONST,
212        /* 3: */1,
213        /* 4: */Bytecode.IFZERO,
214        /* 5: */9,
215        /* 6: */Bytecode.POP,
216        /* 7: */Bytecode.CONST,
217        /* 8: */42,
218        /* 9: */Bytecode.RETURN};
219        assertPartialEvalEqualsAndRunsCorrect(new Program("ifAndPopProgram", bytecodes, 0, 3));
220    }
221
222    @Test
223    public void simpleLoopProgram() {
224        byte[] bytecodes = new byte[]{
225        /* 0: */Bytecode.CONST,
226        /* 1: */42,
227        /* 2: */Bytecode.CONST,
228        /* 3: */-12,
229        /* 4: */Bytecode.CONST,
230        /* 5: */1,
231        /* 6: */Bytecode.ADD,
232        /* 7: */Bytecode.DUP,
233        /* 8: */Bytecode.IFZERO,
234        /* 9: */12,
235        /* 10: */Bytecode.JMP,
236        /* 11: */4,
237        /* 12: */Bytecode.POP,
238        /* 13: */Bytecode.RETURN};
239        assertPartialEvalEqualsAndRunsCorrect(new Program("simpleLoopProgram", bytecodes, 0, 3));
240    }
241
242    @Test
243    public void nestedLoopsProgram() {
244        byte[] bytecodes = new byte[]{
245        /* 0: */Bytecode.CONST,
246        /* 1: */42,
247        /* 2: */Bytecode.CONST,
248        /* 3: */-2,
249        /* 4: */Bytecode.CONST,
250        /* 5: */1,
251        /* 6: */Bytecode.ADD,
252        /* 7: */Bytecode.DUP,
253        /* 8: */Bytecode.CONST,
254        /* 9: */-2,
255        /* 10: */Bytecode.CONST,
256        /* 11: */1,
257        /* 12: */Bytecode.ADD,
258        /* 13: */Bytecode.DUP,
259        /* 14: */Bytecode.IFZERO,
260        /* 15: */18,
261        /* 16: */Bytecode.JMP,
262        /* 17: */10,
263        /* 18: */Bytecode.POP,
264        /* 19: */Bytecode.IFZERO,
265        /* 20: */23,
266        /* 21: */Bytecode.JMP,
267        /* 22: */4,
268        /* 23: */Bytecode.POP,
269        /* 24: */Bytecode.RETURN};
270        assertPartialEvalEqualsAndRunsCorrect(new Program("nestedLoopsProgram", bytecodes, 0, 6));
271    }
272
273    @Test(timeout = 2000)
274    public void manyIfsProgram() {
275        byte[] bytecodes = new byte[]{
276        /* 0: */Bytecode.CONST,
277        /* 1: */40,
278        /* 2: */Bytecode.CONST,
279        /* 3: */1,
280        /* 4: */Bytecode.IFZERO,
281        /* 5: */8,
282        /* 6: */Bytecode.CONST,
283        /* 7: */1,
284        /* 8: */Bytecode.IFZERO,
285        /* 9: */12,
286        /* 10: */Bytecode.CONST,
287        /* 11: */1,
288        /* 12: */Bytecode.IFZERO,
289        /* 13: */16,
290        /* 14: */Bytecode.CONST,
291        /* 15: */1,
292        /* 16: */Bytecode.IFZERO,
293        /* 17: */20,
294        /* 18: */Bytecode.CONST,
295        /* 19: */1,
296        /* 20: */Bytecode.IFZERO,
297        /* 21: */24,
298        /* 22: */Bytecode.CONST,
299        /* 23: */1,
300        /* 24: */Bytecode.IFZERO,
301        /* 25: */28,
302        /* 26: */Bytecode.CONST,
303        /* 27: */1,
304        /* 28: */Bytecode.IFZERO,
305        /* 29: */32,
306        /* 30: */Bytecode.CONST,
307        /* 31: */1,
308        /* 32: */Bytecode.IFZERO,
309        /* 33: */36,
310        /* 34: */Bytecode.CONST,
311        /* 35: */1,
312        /* 36: */Bytecode.IFZERO,
313        /* 37: */40,
314        /* 38: */Bytecode.CONST,
315        /* 39: */1,
316        /* 40: */Bytecode.IFZERO,
317        /* 41: */44,
318        /* 42: */Bytecode.CONST,
319        /* 43: */42,
320        /* 44: */Bytecode.RETURN};
321        assertPartialEvalEqualsAndRunsCorrect(new Program("manyIfsProgram", bytecodes, 0, 3));
322    }
323
324    public abstract static class Inst {
325        public abstract boolean execute(VirtualFrame frame);
326
327        public abstract int getTrueSucc();
328
329        public abstract int getFalseSucc();
330
331        public static class Const extends Inst {
332            private final FrameSlot slot;
333            private final int value;
334            private final int next;
335
336            public Const(FrameSlot slot, int value, int next) {
337                this.slot = slot;
338                this.value = value;
339                this.next = next;
340            }
341
342            @Override
343            public boolean execute(VirtualFrame frame) {
344                frame.setInt(slot, value);
345                return true;
346            }
347
348            @Override
349            public int getTrueSucc() {
350                return next;
351            }
352
353            @Override
354            public int getFalseSucc() {
355                return next;
356            }
357        }
358
359        public static class Return extends Inst {
360            public Return() {
361            }
362
363            @Override
364            public boolean execute(VirtualFrame frame) {
365                return true;
366            }
367
368            @Override
369            public int getTrueSucc() {
370                return -1;
371            }
372
373            @Override
374            public int getFalseSucc() {
375                return -1;
376            }
377        }
378
379        public static class IfZero extends Inst {
380            private final FrameSlot slot;
381            private final int thenInst;
382            private final int elseInst;
383
384            public IfZero(FrameSlot slot, int thenInst, int elseInst) {
385                this.slot = slot;
386                this.thenInst = thenInst;
387                this.elseInst = elseInst;
388            }
389
390            @Override
391            public boolean execute(VirtualFrame frame) {
392                return (FrameUtil.getIntSafe(frame, slot) == 0);
393            }
394
395            @Override
396            public int getTrueSucc() {
397                return thenInst;
398            }
399
400            @Override
401            public int getFalseSucc() {
402                return elseInst;
403            }
404        }
405
406        public static class IfLt extends Inst {
407            private final FrameSlot slot1;
408            private final FrameSlot slot2;
409            private final int thenInst;
410            private final int elseInst;
411
412            public IfLt(FrameSlot slot1, FrameSlot slot2, int thenInst, int elseInst) {
413                this.slot1 = slot1;
414                this.slot2 = slot2;
415                this.thenInst = thenInst;
416                this.elseInst = elseInst;
417            }
418
419            @Override
420            public boolean execute(VirtualFrame frame) {
421                return (FrameUtil.getIntSafe(frame, slot1) < FrameUtil.getIntSafe(frame, slot2));
422            }
423
424            @Override
425            public int getTrueSucc() {
426                return thenInst;
427            }
428
429            @Override
430            public int getFalseSucc() {
431                return elseInst;
432            }
433        }
434    }
435
436    public static class InstArrayProgram extends RootNode {
437        private final String name;
438        @CompilationFinal protected final Inst[] inst;
439        protected final FrameSlot returnSlot;
440
441        public InstArrayProgram(String name, Inst[] inst, FrameSlot returnSlot, FrameDescriptor fd) {
442            super(MockLanguage.class, null, fd);
443            this.name = name;
444            this.inst = inst;
445            this.returnSlot = returnSlot;
446        }
447
448        @Override
449        public String toString() {
450            return name;
451        }
452
453        @Override
454        @ExplodeLoop(merge = true)
455        public Object execute(VirtualFrame frame) {
456            int ip = 0;
457            while (ip != -1) {
458                CompilerAsserts.partialEvaluationConstant(ip);
459                if (inst[ip].execute(frame)) {
460                    ip = inst[ip].getTrueSucc();
461                } else {
462                    ip = inst[ip].getFalseSucc();
463                }
464            }
465            return FrameUtil.getIntSafe(frame, returnSlot);
466        }
467    }
468
469    @Test
470    public void instArraySimpleIfProgram() {
471        FrameDescriptor fd = new FrameDescriptor();
472        FrameSlot valueSlot = fd.addFrameSlot("value", FrameSlotKind.Int);
473        FrameSlot returnSlot = fd.addFrameSlot("return", FrameSlotKind.Int);
474        Inst[] inst = new Inst[]{
475        /* 0: */new Inst.Const(valueSlot, 1, 1),
476        /* 1: */new Inst.IfZero(valueSlot, 2, 4),
477        /* 2: */new Inst.Const(returnSlot, 41, 3),
478        /* 3: */new Inst.Return(),
479        /* 4: */new Inst.Const(returnSlot, 42, 5),
480        /* 5: */new Inst.Return()};
481        assertPartialEvalEqualsAndRunsCorrect(new InstArrayProgram("instArraySimpleIfProgram", inst, returnSlot, fd));
482    }
483
484    /**
485     * Slightly modified version to expose a partial evaluation bug with ExplodeLoop(merge=true).
486     */
487    public static class InstArrayProgram2 extends InstArrayProgram {
488        public InstArrayProgram2(String name, Inst[] inst, FrameSlot returnSlot, FrameDescriptor fd) {
489            super(name, inst, returnSlot, fd);
490        }
491
492        @Override
493        @ExplodeLoop(merge = true)
494        public Object execute(VirtualFrame frame) {
495            int ip = 0;
496            while (ip != -1) {
497                CompilerAsserts.partialEvaluationConstant(ip);
498                if (inst[ip].execute(frame)) {
499                    ip = inst[ip].getTrueSucc();
500                } else {
501                    ip = inst[ip].getFalseSucc();
502                }
503            }
504            if (frame.getArguments().length > 0) {
505                return new Random();
506            } else {
507                return FrameUtil.getIntSafe(frame, returnSlot);
508            }
509        }
510    }
511
512    @Ignore("produces a bad graph")
513    @Test
514    public void instArraySimpleIfProgram2() {
515        FrameDescriptor fd = new FrameDescriptor();
516        FrameSlot value1Slot = fd.addFrameSlot("value1", FrameSlotKind.Int);
517        FrameSlot value2Slot = fd.addFrameSlot("value2", FrameSlotKind.Int);
518        FrameSlot returnSlot = fd.addFrameSlot("return", FrameSlotKind.Int);
519        Inst[] inst = new Inst[]{
520        /* 0: */new Inst.Const(value1Slot, 100, 1),
521        /* 1: */new Inst.Const(value2Slot, 100, 2),
522        /* 2: */new Inst.IfLt(value1Slot, value2Slot, 3, 5),
523        /* 3: */new Inst.Const(returnSlot, 41, 4),
524        /* 4: */new Inst.Return(),
525        /* 5: */new Inst.Const(returnSlot, 42, 6),
526        /* 6: */new Inst.Return()};
527        InstArrayProgram program = new InstArrayProgram2("instArraySimpleIfProgram2", inst, returnSlot, fd);
528        program.execute(Truffle.getRuntime().createVirtualFrame(new Object[0], fd));
529        program.execute(Truffle.getRuntime().createVirtualFrame(new Object[1], fd));
530        assertPartialEvalEqualsAndRunsCorrect(program);
531    }
532}