Compiler PhasesInterpretationInterpretationldots Kinds of InterpretersKinds of Interpretersldots Actions in an InterpreterActions in an Interpreterldots Stack-Based Instruction SetsStack-Based Instruction Setsldots Register-Based Instruction SetsRegister-Based Instruction Setsldots Stack Machine Example IStack Machine Example (a)Stack Machine Example (b)Switch ThreadingSwitch ThreadingSwitch Threading in JavaBytecode semanticsBytecode semanticsldots Example programsExample programsldots Example programldots Example programsldots Bytecode DescriptionBytecode Descriptionldots Bytecode Descriptionldots Switch Threading in JavaSwitch Threadingldots Faster Operator DispatchDirect Call ThreadingDirect Call Threadingldots Direct Call Threadingldots Direct Call Threadingldots Direct ThreadingDirect Threadingldots Direct Threadingldots Indirect ThreadingIndirect Threadingldots Indirect Threadingldots Other OptimizationsMinimizing Stack AccessesInstruction Sets RevisitedJust-In-Time CompilationReadings and ReferencesSummarySummaryldots520—Spring 2005—44CSc 520Principles of ProgrammingLanguages44: InterpretersChristian [email protected] of Computer ScienceUniversity of ArizonaCopyrightc 2005 Christian Collberg[1]520—Spring 2005—44Compiler PhasesASTSemanticAnalyserInterm.Code GenIRASTLexertokenssourceVMInterpreterParserCompilerGenVM CodeGet NextInstructionExecuteInstruction[2]520—Spring 2005—44InterpretationAn interpreter is like a CPU, only in software.The compiler generates virtual machine (VM) coderather than native machine code.The interpreter executes VM instructions rather thannative machine code.Interpreters areslow Often 10–100 times slower than executing machinecode directly.portable The virtual machine code is not tied to anyparticular architecture.[3]520—Spring 2005—44Interpretation...Interpreters areslow Often 10–100 times slower than executing machinecode directly.portable The virtual machine code is not tied to anyparticular architecture.Interpreters work well withvery high-level, dynamic languages (APL,Prolog,ICON)where a lot is unknown at compile-time (array bounds,etc).[4]520—Spring 2005—44Kinds of InterpretersRead, lex,parse,semanticsSourceCodeVMCodereadevalprintInterpretRead, lex,parse,semanticsSourceCodeVMCodeCodeFile.vmreadevalprintInterpretReadVMCodeFile.vm"Java−style interpreter""APL/Prolog−style (load−and−go/interactive) interpreter"[5]520—Spring 2005—44Kinds of Interpreters...VMCodeRead, lex,parse,semanticsSourceCodeCodeFile.vmCompileCodeNativeExecuteCodeFile.vmJust−In−Time (JIT,Dynamic) Compiler[6]520—Spring 2005—44Actions in an InterpreterInternally, an interpreter consists of1. The interpreter engine, which executes the VMinstructions.2. Memory for storing user data. Often separated as aheap and a stack.3. A stream of VM instructions.[7]520—Spring 2005—44Actions in an Interpreter...Decode the instruction.Op := the opcodeArg1 := 1st argumentArg2 := 2nd argument....Perform the functionof the opcode.Instruct−addstoremulionstream........HeapStackMemory"Hello!"StaticDataI := Get next instruction.[8]520—Spring 2005—44Stack-Based Instruction SetsMany virtual machine instruction sets (e.g. Javabytecode, Forth) are stack based.add pop the two top elements off the stack, add themtogether, 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.StoreV at memory address A.[9]520—Spring 2005—44Stack-Based Instruction Sets...Here’s an example of a small program and thecorresponding stack code:Source CodeVM CodeVAR X,Y,Z : INTEGER;BEGINX := Y + Z;END;pusha Xpush Ypush Zaddstore[10]520—Spring 2005—44Register-Based Instruction SetsStack codes are compact. If we don’t worry about codesize, we can use any intermediate code (tuples, trees).Example: RISC-like VM code with∞ number of virtualregistersR1, · · ·:add R1, R2, R3Add VM registers R2and R3and store inVM registerR1.load R1, X R1:= value of variable X.loada R1, X R1:= address of variable X.store R1, R2Store value R2at address R1.[11]520—Spring 2005—44Register-Based Instruction Sets...Here’s an example of a small program and thecorresponding register code:Source CodeVM CodeVAR X,Y,Z : INTEGER;BEGINX := Y + Z;END;load R1, Yload R2, Zadd R3, R1, R2loada R4, Xstore R4, R3[12]520—Spring 2005—44Stack Machine Example ISource 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 4[13]520—Spring 2005—44Stack Machine Example (a)VM Code Stack Memory[1] pusha X[2] push 1[3] store&X1&X[1] [2] [3]X 1Y 5Z 10[4] push X[5] push 10[6] GE[7] BrTrue 141[4]110[5]0[6][7]X 1Y 5Z 10[14]520—Spring 2005—44Stack Machine Example (b)VM Code Stack Memory[8] pusha X[9] push Y[10] push Z[11] add[12] store&X[8]&X5[9]&X510[10]15&X[11][12]X 15Y 5Z 10[13] jump 4[15]520—Spring 2005—44Switch Threading[16]520—Spring 2005—44Switch ThreadingInstructions are stored as an array of integer tokens. Aswitch selects 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;}}}[17]520—Spring 2005—44Switch Threading in JavaLet’s look at a simple Java switch interpreter.We have a stack of integers stack and a stack pointersp.There’s an array of bytecodes prog and a programcounterpc.There is a small memory area memory, an array of 256integers, numbered 0–255. TheLOAD, STORE, ALOAD,andASTORE instructions access these memory cells.[18]520—Spring 2005—44Bytecode 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][19]520—Spring 2005—44Bytecode 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]
View Full Document
Unlocking...