CSc 453Compilers and Systems Software18 : InterpretersDepartment of Computer ScienceUniversity of [email protected]° 2009 Christian CollbergASTSemanticAnalyserInterm.Code GenIRASTLexertokenssourceVMParserCompilerGenVM CodeInterpreterGet NextInstructionExecuteInstructionAn interpreter is like a CPU, only in software.The compiler generates virtual machine (VM) code ratherthan native machine code.The interpreter executes VM instructions rather than nativemachine code.Interpreters areslow Often 10–100 times slower than executing machinecode directly.portable The virtual machine code is not tied to any particulararchitecture.Interpreters work well withvery high-level, dynamic languages(APL,Prolog,ICON) where a lot is unknown atcompile-time (array bounds, etc).Kinds of Interpreters"APL/Prolog−style (load−and−go/interactive) interpreter"Read, lex,parse,semanticsSourceCodeVMCodereadevalprintInterpretRead, lex,parse,semanticsSourceCodeVMCodeCodeFile.vmreadevalprintInterpretReadVMCodeFile.vm"Java−style interpreter"Kinds of Interpreters. . .Just−In−Time (JIT,Dynamic) CompilerCodeRead, lex,parse,semanticsSourceCodeCodeFile.vmCompileCodeNativeExecuteCodeFile.vmVMActions in an InterpreterInternally, an interpreter consists of1The interpreter engine, which executes the VM instructions.2Memory for storing user data. Often separated as a heap and astack.3A stream of VM instructions.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!"StaticDataStack-Based Instruction SetsMany virtual machine instruction sets (e.g. Java bytecode,Forth) are stack based.add pop the two top elements off the stack, addthem together, and push the result on the stack.push X push the value of variable X .pusha X push the address of variable X .store pop a value V , and an address A off the stack.Store V at memory address A.Stack-Based Instruction Sets. . .Here’s an example of a small program and the correspondingstack code:Source CodeVM CodeVAR X,Y,Z : INTEGER;BEGINX := Y + Z;END;pusha Xpush Ypush ZaddstoreRegister-Based Instruction SetsStack 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 VMregister R1.load R1, X R1:= value of variable X .loada R1, X R1:= address of variable X .store R1, R2Store value R2at address R1.Register-Based Instruction Sets. . .Here’s an example of a small program and the correspondingregister code:Source CodeVM CodeVAR X,Y,Z : INTEGER;BEGINX := Y + Z;END;load R1, Yload R2, Zadd R3, R1, R2loada R4, Xstore R4, R3Source Code VM 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 4Stack Machine Example (a)VM Code Stack 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 10Stack Machine Example (b)VM Code Stack 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 4Switch ThreadingInstructions are stored as an array of integer tokens. A switchselects the right code for each instruction.typedef 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;}}}Switch threading exampleSwitch Threading in JavaLet’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 256integers, numbered 0–255. The LOAD, STORE, ALOAD, andASTORE instructions access these memory cells.Bytecode semanticsmnemonic opcode 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]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]Example programsThis program prints a newline character and then exits:PRINTLNEXITOr, in binary: h8, 9i This program prints the number 10, then anewline character, and then exits:PUSHB 10PRINTPRINTLNEXITOr, in binary: h6, 10, 7, 8, 9iExample programs. . .This program pushes two values on the stack, then performs anADD instruction which pops these two values off the stack, addsthem, and pushes the result. PRINT then pops this value off thestack and prints it:PUSHB 10PUSHB 20ADDPRINTPRINTLNEXITOr, in binary: h6, 10, 6, 20, 0, 7, 8, 9iExample program. . .This program uses the LOAD and STORE instructions to store avalue in memory cell number 7:PUSHB 10STORE 7PUSHB 10LOAD 7MULPRINTPRINTLNEXITOr, in binary: h6, 10, 5, 7, 6, 10, 4, 7, 2, 7, 8, 9i# 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 loopEXITBytecode DescriptionADD : Pop the two top integers A and B off the stack, thenpush 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.Bytecode Description. . .LOAD X : Push the contents of memory cell number X on thestack.STORE X : Pop the top integer off the stack and store this valuein memory cell number X .ALOAD : Pop the address of memory cell number X off thestack and push the value of X .ASTORE : Pop the address