Lecture #21: Code GenerationIntermediate Languages and Machine LanguagesStack Machines as Virtual MachinesStack Machine with AccumulatorExample: Full computation of 7+5A Point of OrderTranslating from AST to Stack MachineVirtual Register Machines and Three-Address CodeThree-Address Code, continuedTranslating from AST into Three-Address CodeA Larger ExampleSimple Cases: Literals and SequencesIdentifiersCallsControl Expressions: ifCode generation for `def'A Sample TranslationLecture #21: Code Generation[This lecture adopted in part from notes by R. Bodik]Administrivia• Test #2 next Tuesday (14 April).Last modified: Mon May 4 00:49:57 2009 CS164: Lecture #21 1Intermediate Languages and Machine Languages• From trees such as output from project #2, could produce machinelanguage directly.• However, it is often convenient to first generate some kind ofinter-mediate language (IL):a “high-level machine language” for a “virtualmachine.”• Advantages:– Separates problem of extracting the operational meaning (thedynamic semantics) of a program from the problem of producinggood machine code from it, because it. . .– Gives a clean target for code generation from the AST.– By choosing IL judiciously, we can make the conversion of IL →machine language easier than the direct conversion of AST → ma-chine language. Helpful when we want to target several differentarchitectures (e.g., gcc).– Likewise, if we can use the same IL for multiple languages, we canre-use the IL → machine language implementation (e.g., gcc, CILfrom Microsoft’s Common Language Infrastructure).Last modified: Mon May 4 00:49:57 2009 CS164: Lecture #21 2Stack Machines as Virtual Machines• A simple evaluation model: instead of registers, a stack of valuesfor intermediate results.• Examples: The Java Virtual Machine, the Postscript interpreter.• Each operation (1) pops its operands from the top of the stack, (2)computes the required operation on them, and (3) pushes the resulton the stack.• A program to compute 7 + 5:push 7 # Push constant 7 on stackpush 5add # Pop two 5 and 7 from stack, add, and push result.• Advantages– Uniform compilation scheme: Each operation takes operands fromthe same place and puts results in the same place.– Fewer explict operands in instructions means smaller encoding ofinstructions and more compact programs.– Meshes nicely with subroutine calling conventions that push argu-ments on stack.Last modified: Mon May 4 00:49:57 2009 CS164: Lecture #21 3Stack Machine with Accumulator• Theadd instruction does 3 memory operations: Two reads and onewrite of the stack.• The top of the stack is frequently accessed• Idea: keep most recently computed value in a register (called theaccumulator) since register accesses are faster.• For an operation op(e1, . . . , en):– compute each of e1, . . . , en−1into acc and then push on the stack;– compute eninto the accumulator;– performop computation, with result in acc.– pop e1, . . . , en−1off stack.• Theadd instruction is nowacc := acc + top_of_stackpop one item off the stackand uses just one memory operation (popping just means adding con-stant to stack-pointer register).• After computing an expression the stack is as it was before com-puting the operands.Last modified: Mon May 4 00:49:57 2009 CS164: Lecture #21 4Example: Full computation of 7+5acc := 7push accacc := 5acc := acc + top_of_stackpop stackLast modified: Mon May 4 00:49:57 2009 CS164: Lecture #21 5A Point of Order• Often more convenient to push operands inreverseorder, so right-most operand pushed first.• This is a common convention for pushing function arguments, and isespecially natural when stack grows toward lower addresses.• Also nice for non-commutative operations on architectures such asthe ia32.• Example: compute x - y. We show assembly code on the rightacc := y movl y, %eaxpush acc pushl %eaxacc := x movl x, %eaxacc := acc - top_of_stack subl (%esp), %eaxpop stack addl $4, %espLast modified: Mon May 4 00:49:57 2009 CS164: Lecture #21 6Translating from AST to Stack Machine• A simple recursive pattern usually serves for expressions.• At the top level, our trees might have an expression-code method:class AST {.../** Generate code for me, leaving my value on the stack. */virtual void cgen (VM* machine);}• Implementations of cgen then obey this general comment, and eachassumes that its children will as well. E.g.,class BinopNode : public AST {...void cgen (VM* machine) {getRight ()->cgen (machine);getLeft ()->cgen (machine);machine->emitInst (translateToInst (getOp ()));}}We assume here a VM is some abstraction of the virtual machinewe’re producing code for. emitInst adds machine instructions tothe program, and translateToInst converts, e.g., a’+’toadd.Last modified: Mon May 4 00:49:57 2009 CS164: Lecture #21 7Virtual Register Machines and Three-Address Code• Another common kind of virtual machine has an infinite supply ofregisters, each capable of holding a scalar value or address, in addi-tion to ordinary memory.• A common IL in this case is some form ofthree-address code, socalled because the typical “working” instruction has the formtarget := operand1⊕ operand2where there are two source “addresses,” one destination “address”and an operation (⊕).• Often, we require that the operands in the full three-address formdenote (virtual) registers or immediate (literal) values.Last modified: Mon May 4 00:49:57 2009 CS164: Lecture #21 8Three-Address Code, continued• A few other forms deal with memory and other kinds of operation:memory_operand := register_or_immediate_operandregister_operand := memory_operandgoto labelif operand1 ≺ operand2 then goto labelparam operand ; Push parameter for call.call operand, # of parameters ; Call, put return in specific register• Here, ≺ stands for some kind of comparison. Memory operandsmight be labels of static locations, or indexed operands such as (inC-like notation) *(r1+4) or *(r1+r2).Last modified: Mon May 4 00:49:57 2009 CS164: Lecture #21 9Translating from AST into Three-Address Code• This time, we’ll have the cgen routine return where it has put itsresult:class AST {.../** Generate code to compute my value, returning the location* of the result. */virtual Operand* cgen (VM* machine);}• Where an Operand denotes some abstract place holding a value.• Once again, we rely on our children to obey this general comment:class BinopNode : public AST
View Full Document
Unlocking...