Code GenerationThe remote testing experiment. It works!Remote testingFrom the cs164 newsgroup The moralLecture OutlineStack MachinesExample of a Stack Machine ProgramStack Machine. ExampleWhy Use a Stack Machine ?Slide 11Optimizing the Stack MachineStack Machine with AccumulatorStack Machine with Accumulator. ExampleA Bigger Example: 3 + (7 + 5)NotesFrom Stack Machines to MIPSMIPS assembly vs. x86 assemblySimulating a Stack Machine…MIPS AssemblyA Sample of MIPS Instructionsx86 Assemblyx86 assemblySample x86 instructions (gcc order of operands)MIPS to x86 translationx86 vs. MIPS registersMIPS Assembly. Example.Some Useful MacrosA Small LanguageA Small Language (Cont.)Code Generation StrategyCode Generation for ConstantsCode Generation for AddCode Generation for Add. Wrong!Code Generation NotesCode Generation for Sub and ConstantsCode Generation for ConditionalCode Generation for If (Cont.)The Activation RecordThe Activation Record (Cont.)Slide 41Code Generation for Function CallCode Generation for Function Call (Cont.)Code Generation for Function DefinitionCalling Sequence. Example for f(x,y).Code Generation for VariablesCode Generation for Variables (Cont.)Slide 48SummarySlide 50Allocating Temporaries in the ARReviewReview (Cont.)A Better WayExampleHow Many Temporaries?The EquationsThe Revised ARPictureRevised Code GenerationCode Generation for + (original)Code Generation for + (revised)Slide 63Code Generation for Object-Oriented LanguagesObject LayoutTwo IssuesObject Layout ExampleObject Layout (Cont.)Slide 69Slide 70Slide 71SubclassesLayout PictureSubclasses (Cont.)Dynamic DispatchDynamic Dispatch ExampleDispatch TablesDispatch Table ExampleUsing Dispatch TablesUsing Dispatch Tables (Cont.)CS 164 Lecture 14 Fall 2004 1Code GenerationLecture 12CS 164 Lecture 14 Fall 2004 2The remote testing experiment. It works!Coverage - Score plot00.10.20.30.40.50.60.70.80.90 10 20 30 40 50ScoreCoverageSeries1Poly. (Series1)CS 164 Lecture 14 Fall 2004 3Remote testing•In PA1, if you achieved best coverage, you also got best score!44 0.81428644 0.81428644 0.81428644 0.81428643 0.843 0.843 0.843 0.844 0.841 0.838 0.844 0.8CS 164 Lecture 14 Fall 2004 4From the cs164 newsgroup > I need a small website made. I'm willing to pay for the work too. > So... if anyone is interested e-mail me at [deleted]@berkeley.edu.CS164's guide to create a website:1) Write a lexer2) Write a lexer spec for some unknown, obscure language3) Write a parser4) Write the grammar for that obscure language5) Write a code generator that generates HTML6) ...7) Profit! Now only you can maintain that website!CS 164 Lecture 14 Fall 2004 5The moral•Essentially, the recommended strategy is to–goal: no one can maintain your programs–means: develop an obscure language for your programs•But if this is your goal, why a new language?–tons of unmaintainable Java programs written–some even submitted as cs164 projects –I am sure you can succeed with just Java, too.•A better road to profit–develop a language: can be obscure, even horrible, but make sure it’s horibly useful, too (ex.: perl, C++, Visual Basic, latex)–then publish books on this language CS 164 Lecture 14 Fall 2004 6Lecture Outline•Stack machines•The MIPS assembly language•The x86 assembly language•A simple source language•Stack-machine implementation of the simple languageCS 164 Lecture 14 Fall 2004 7Stack Machines•A simple evaluation model•No variables or registers•A stack of values for intermediate resultsCS 164 Lecture 14 Fall 2004 8Example of a Stack Machine Program•Consider two instructions–push i - place the integer i on top of the stack–add - pop two elements, add them and put the result back on the stack•A program to compute 7 + 5: push 7 push 5 addCS 164 Lecture 14 Fall 2004 9Stack Machine. Example•Each instruction:–Takes its operands from the top of the stack –Removes those operands from the stack–Computes the required operation on them–Pushes the result on the stack…stack57… push 512……push 77 addCS 164 Lecture 14 Fall 2004 10Why Use a Stack Machine ?•Each operation takes operands from the same place and puts results in the same place•This means a uniform compilation scheme•And therefore a simpler compilerCS 164 Lecture 14 Fall 2004 11Why Use a Stack Machine ?•Location of the operands is implicit–Always on the top of the stack•No need to specify operands explicitly•No need to specify the location of the result•Instruction “add” as opposed to “add r1, r2” Smaller encoding of instructions More compact programs•This is one reason why Java Bytecodes use a stack evaluation modelCS 164 Lecture 14 Fall 2004 12Optimizing the Stack Machine•The add instruction does 3 memory operations–Two reads and one write to the stack–The top of the stack is frequently accessed•Idea: keep the top of the stack in a register (called accumulator)–Register accesses are faster•The “add” instruction is now acc acc + top_of_stack–Only one memory operation!CS 164 Lecture 14 Fall 2004 13Stack Machine with AccumulatorInvariants•The result of computing an expression is always in the accumulator•For an operation op(e1,…,en) push the accumulator on the stack after computing each of e1,…,en-1–The result of en is in the accumulator before op–After the operation pop n-1 values•After computing an expression the stack is as beforeCS 164 Lecture 14 Fall 2004 14Stack Machine with Accumulator. Example•Compute 7 + 5 using an accumulator…accstack57…acc 512…acc acc + top_of_stackpop…7acc 7push acc7CS 164 Lecture 14 Fall 2004 15A Bigger Example: 3 + (7 + 5) Code Acc Stackacc 3 3 <init>push acc 3 3, <init>acc 7 7 3, <init>push acc 7 7, 3, <init>acc 5 5 7, 3, <init>acc acc + top_of_stack 12 7, 3, <init>pop 12 3, <init>acc acc + top_of_stack 15 3, <init>pop 15 <init>CS 164 Lecture 14 Fall 2004 16Notes•It is very important that the stack is preserved across the evaluation of a subexpression–Stack before the evaluation of 7 + 5 is 3, <init>–Stack after the evaluation of 7 + 5 is 3, <init>–The first operand is on top of the stackCS 164 Lecture 14 Fall 2004 17From Stack Machines to
View Full Document
Unlocking...