Introduction to Intermediate Code, virtual machine implementationWhere do we go from here?Details of MJ what the VM must support Details of the VM what IC to generateWhat is Intermediate Code? No single answer…What is Intermediate Code? AdvantagesForms of Intermediate CodeUsing Intermediate CodeReminder of what we are doing.. From a tree representation like our AST..The simplest exampleJust a simple stack machine (oversimplified)It doesn’t have to look like lisp if we write a printing programConsider the file Simple-compiler.faslSome FAQ. 1. Redundant work?FAQ 2. Where do the programs live?FAQ 3: Too many layers?The 2-pass assembler… (50 lines of code?)What does the assembler do?The 1st pass counts up locationsThe 2nd pass resolves labels, makes vectorThe MJ Virtual MachineIt is a stack-based architecture simulated by a Lisp program.It is a stack-based architecture simulated by a Lisp programWe set up an update-program-counter/ execute loopThe outer exception handling controllerList of Opcodes (I)List of Opcodes (II)Architecture for arithmetic is based on underlying lisp arithmetic, e.g. + ´ #’+Machine + assembler in simple-machine.lispProf. Fateman CS 164 Lecture 19 1Introduction to Intermediate Code, virtual machine implementationLecture 19Prof. Fateman CS 164 Lecture 19 2Where do we go from here?AST generationType checkingCleanup? Interpreter intermediate code/ assmblrtestingVirtual machineinoutProf. Fateman CS 164 Lecture 19 3Details of MJ what the VM must support Details of the VM what IC to generateintermediate code/ assmblrVirtual machineinoutProf. Fateman CS 164 Lecture 19 4What is Intermediate Code? No single answer…•Any encoding further from the source and closer to the machine. Possibilities:–Same except remove line/column numbers!–Change all parameter or local NAMES to stack offset counts–Change all global references (vars, methods) to vtable counts–Possible spew out Lisp as an IC. [My favorite: map every language you encounter into Common Lisp. Macro defs make it possible to define an intermediate level language “especially suited to IC” in Lisp. ]•Not (usually) machine code itself•Usually some extra “abstraction” –Imagine you have arbitrary numbers of registers for calculations.–Imagine you have “macro” instructions like x=a[i,j]Prof. Fateman CS 164 Lecture 19 5What is Intermediate Code? Advantages•Generally relatively portable between machines•One IC may support several languages (a typical set might be C, C++, Pascal, Fortran) where the resources needed are similar. (If you can support C, the rest of them are pretty easy.)•Languages with widely-differing semantics will not fit in this restricted set and may require an extended IC. •E.g. Java IC supporting Scheme is hard because Scheme has 1st-class functions. Scheme IC supporting Java is plausible structurally but might not be as efficient.Prof. Fateman CS 164 Lecture 19 6Forms of Intermediate CodeVirtual stack machinesimplified “macro” machine3-address codeA :=B op CRegister machine modelswith unlimited number of registers, mapped to real registers laterTree form (= lisp program, more or less)Prof. Fateman CS 164 Lecture 19 7Using Intermediate Code•We need to make some progress towards the machine we have in mind–Subject to manipulation, “optimization”–Perhaps several passes–Or, we can generate assembler–Or, we could plop down in absolute memory locations the binary instructions needed to execute the program “compile-and-go” system. This was a common “student compiler” technique for Pascal and Fortran.Prof. Fateman CS 164 Lecture 19 8Reminder of what we are doing.. From a tree representation like our AST..•Instead of typechecking or interpreting the code, we are traversing it and putting together a list of instructions… generating IC … that if run on a machine -- would execute the program. •In other words instead of interpreting or typechecking a loop,or going through a loop executing it, we write it out in assembler.Prof. Fateman CS 164 Lecture 19 9The simplest exampleCompiling the MJ program segment … 3+4…The string "3+4" [too simple to have line/column numbers] parses to (Plus (IntegerLiteral 3) (IntegerLiteral 4)) typechecker approves and says it is of type int. A program translating to lisp produces(+ 3 4)Which could be executed… But we don’t really want Lisp, we want machine code. We could startfrom the Lisp or from the AST, i.e. …. (Plus …)…Prof. Fateman CS 164 Lecture 19 10Just a simple stack machine (oversimplified)Compiling(+ 3 4)(some-kind-of-compiler '(+ 3 4)) ;; I made-up name ((pushi 3) (pushi 4) (+))Result is a list of assembly language instructions push immediate constant 3 on stack push immediate constant 4 on stack + = take 2 args off stack and push sum on stackConventions: result is left on top of stack.Location of these instructions unspecified. Lengthy notes in simple-machine file describe virtual machine.Prof. Fateman CS 164 Lecture 19 11It doesn’t have to look like lisp if we write a printing program(pprint-code compiled-vector) ;; prints out… pushi 3 pushi 4 +Prof. Fateman CS 164 Lecture 19 12Consider the file Simple-compiler.faslLoad this file and you have functions for compiling methods, exps, statements. You can trace them.mj-c-method compiles one methodmj-c-exp compiles one expressionmj-c-statement compiles one statementEach program calls “emit” to add to the generated program some sequence of instructions. Typically these are consed on to the front of a list intended to become the “body” of a method. This list which is then reversed, embroidered with other instructions, and is ready to assemble.Prof. Fateman CS 164 Lecture 19 13Some FAQ. 1. Redundant work?•Q: Going back to the AST for compiling, it seems to me that I am re-doing things I already did (or did 95%) for type-checking. •A. You are right. Next time you write a compiler (hehe) you will remember and maybe you will save the information some way. E.g. save the environment / inheritance hierarchy, offsets for variables, type data used to determine assembler instructions, etc.Prof. Fateman CS 164 Lecture 19 14FAQ 2. Where do the programs live?•You might ask this question; how are the methods placed in memory?•For now we do not have to say, but we could let a “loader” determine where to put each code segment in memory. Each method
View Full Document
Unlocking...