CSc 453 — Compilers and Systems Software18 : InterpretersChristian CollbergDepartment of Computer ScienceUniversity of [email protected]° 2009 Christian CollbergOctober 25, 20091ASTSemanticAnalyserInterm.Code GenIRASTLexertokenssourceVMParserCompilerGenVM CodeInterpreterGet NextInstructionExecuteInstruction2• An interpreter is like a CPU, only in software.• The compiler generates virtual machine (VM) code rather than native machine code.• The interpreter executes VM instructions rather than native machine code.Interpreters areslow Often 10–100 times slower than executing machine code directly.portable The virtual machine code is not tied to any particular architecture.Interpreters work well withvery high-level, dynamic languages (APL,Prolog,ICON) where a lot is unknown at compile-time (arraybounds, etc).13 Kinds of Interpreters"APL/Prolog−style (load−and−go/interactive) interpreter"Read, lex,parse,semanticsSourceCodeVMCodereadevalprintInterpretRead, lex,parse,semanticsSourceCodeVMCodeCodeFile.vmreadevalprintInterpretReadVMCodeFile.vm"Java−style interpreter"4 Kinds of Interpreters. . .Just−In−Time (JIT,Dynamic) CompilerCodeRead, lex,parse,semanticsSourceCodeCodeFile.vmCompileCodeNativeExecuteCodeFile.vmVM5 Actions in an Interpreter• Internally, an interpreter consists of1. The interpreter engine, which executes the VM instructions.2. Memory for storing user data. Often separated as a heap and a stack.3. A stream of VM instructions.6 Actions in an Interpreter. . .I := Get next instruction.Decode the instruction.Op := the opcodeArg1 := 1st argumentArg2 := 2nd argument....Perform the functionof the opcode.Instruct−addstoremulionstream........HeapStackMemory"Hello!"StaticData27 Stack-Based Instruction Sets• Many virtual machine instruction sets (e.g. Java bytecode, Forth) are stack based.addpop the two top elements off the stack, add them together, and push the result on the stack.push X push the value of variable X.pusha Xpush the address of variable X.storepop a value V , and an address A off the stack. Store V at memory address A.8 Stack-Based Instruction Sets. . .• Here’s an example of a small program and the corresponding stack code:Source Code VM CodeVAR X,Y,Z : INTEGER;BEGINX := Y + Z;END;pusha Xpush Ypush Zaddstore9 Register-Based Instruction Sets• Stack codes are compact. If we don’t worry about code size, we can use any intermediate code (tuples,trees). Example: RISC-like VM code with ∞ number of virtual registers R1, · · · :add R1, R2, R3Add VM registers R2and R3and store in VM register R1.load R1, XR1:= value of variable X.loada R1, XR1:= address of variable X.store R1, R2Store value R2at address R1.10 Register-Based Instruction Sets. . .• Here’s an example of a small program and the corresponding register code:Source Code VM CodeVAR X,Y,Z : INTEGER;BEGINX := Y + Z;END;load R1, Yload R2, Zadd R3, R1, R2loada R4, Xstore R4, R3311Source CodeVM CodeVAR X,Y,Z : INTEGER;BEGINX := 1;WHILE X < 10 DOX := Y + Z;ENDDOEND;[1] pusha X[2] push 1[3] store[4] push X[5] push 10[6] GE[7] BrTrue 14[8] pusha X[9] push Y[10] push Z[11] add[12] store[13] jump 412 Stack Machine Example (a)VM CodeStack Memory[1] pusha X[2] push 1[3] store[3]&X1&X[1] [2]X 1Y 5Z 10[4] push X[5] push 10[6] GE[7] BrTrue 14[7]1[4]110[5]0[6]X 1Y 5Z 1013 Stack Machine Example (b)VM CodeStack Memory[8] pusha X[9] push Y[10] push Z[11] add[12] store[12]&X[8]&X5[9]&X510[10]15&X[11]X 15Y 5Z 10[13] jump 414 Switch Threading• Instructions are stored as an array of integer tokens. A switch selects the right code for each instruction.4typedef enum {add,load,store,· · · } Inst;void engine () {static Inst prog[] = {load,add,· · · };Inst *pc = &prog;int Stack[100]; int sp = 0;for (;;)switch (*pc++) {case add: Stack[sp-1]=Stack[sp-1]+Stack[sp];sp--; break;}}}15Switch threading example16 Switch Threading in Java• Let’s look at a simple Java switch interpreter.• We have a stack of integers stack and a stack pointer sp.• There’s an array of bytecodes prog and a program counter pc.• There is a small memory area memory, an array of 256 integers, numbered 0–255. The LOAD, STORE,ALOAD, and ASTORE instructions access these memory cells.17 Bytecode semanticsmnemonicopcode stack-pre stack-post side-effectsADD 0 [A,B] [A+B]SUB 1 [A,B] [A-B]MUL 2 [A,B] [A*B]DIV 3 [A,B] [A-B]LOAD X 4 [] [Memory[X]]STORE X 5 [A] [] Memory[X] = APUSHB X 6 [] [X]PRINT 7 [A] [] Print APRINTLN 8 [] [] Print a newlineEXIT 9 [] [] The interpreter exitsPUSHW X 11 [] [X]518 Bytecode semantics. . .mnemonic opcode stack-pre stack-post side-effectsBEQ L 12 [A,B] [] if A=B then PC+=LBNE L 13 [A,B] [] if A!=B then PC+=LBLT L 14 [A,B] [] if A<B then PC+=LBGT L 15 [A,B] [] if A>B then PC+=LBLE L 16 [A,B] [] if A<=B then PC+=LBGE L 17 [A,B] [] if A>=B then PC+=LBRA L 18 [] [] PC+=LALOAD 19 [X] [Memory[X]]ASTORE 20 [A,X] [] Memory[X] = ASWAP 21 [A,B] [B,A]19 Example programsThis program prints a newline character and then exits:PRINTLNEXITOr, in binary: h8, 9i This program prints the number 10, then a newline character, and then exits:PUSHB 10PRINTPRINTLNEXITOr, in binary: h6, 10, 7, 8, 9i20 Example programs. . .This program pushes two values on the stack, then performs an ADD instruction which pops these two valuesoff the stack, adds them, and pushes the result. PRINT then pops this value off the stack and prints it:PUSHB 10PUSHB 20ADDPRINTPRINTLNEXITOr, in binary: h6, 10, 6, 20, 0, 7, 8, 9i21 Example program. . .This program uses the LOAD and STORE instructions to store a value in memory cell number 7:PUSHB 10STORE 7PUSHB 10LOAD 76MULPRINTPRINTLNEXITOr, in binary: h6, 10, 5, 7, 6, 10, 4, 7, 2, 7, 8, 9i22# Print the numbers 1 through 9.# i = 1; while (i < 10) do {print i; println; i++;}PUSHB 1 # mem[1] = 1;STORE 1LOAD 1 # if mem[1] < 10 goto exitPUSHB 10BGELOAD 1 # print mem[i] valuePRINTPRINTLNPUSHB 1 # mem[1]++LOAD 1ADDSTORE 1BRA # goto top of loopEXIT23 Bytecode DescriptionADD: Pop the two top integers A and B off the stack, then push A + B.SUB : As above, but push A − B.MUL : As above, but push A ∗ B.DIV : As above, but push A/B.PUSHB X: Push X, a signed, byte-size, value, on the stack.PUSHW X: Push X, a signed, word-size, value, on the stack.PRINT : Pop the top integer off the stack and print it.PRINTLN : Print a newline character.EXIT : Exit the interpreter.24 Bytecode Description. . .LOAD X: Push the contents of memory cell number X on the stack.STORE X: Pop the top integer off