Question? Leave a message!




Anatomy of a compiler Lexical

Anatomy of a compiler Lexical
U Unopti ti mi i zed C d C od de Generation From From the the intermediate intermediate representation to the machine code code5 Outline • Introduction • Machine Language • Overview of a modern p processor • Memory Layout • Procedure Procedure A Abstraction bstraction • Procedure Linkage • • Guidelines Guidelines in in Creating Creating a a C Code ode Generator Generator Anatomy of a compiler Program (character stream) Lexical Analy( yzer (Scanner) ) Token Stream Syyy ntax Analyzer ((Parser)) Parse Tree Semantic Analy yzer Intermediate Representation Intermediate Code Op ptimizer Optimized Intermediate Representation Code Generator Assembly codeAnatomy of a compiler Program (character stream) Lexical Analy( yzer (Scanner) ) Token Stream Syy yntax Analyzer ((Parser)) Parse Tree Semantic Analy yzer Highlevel IR Low Lowlevel level IR IR Intermediate Representation Code Generator Assembly codeComponents of a High Level Language Language CODE DATA Global Static Variables Procedures Global Global Dynamic Dynamic Data Data Control Flow Local Variables Temporaries Statements Parameter Parameter Passing Passing Data Access Readonly DataMachine Code Generator Should Should... • Translate all the instructions in the intermediate representation to assembly language language • Allocate space for the variables, arrays etc. • Adhere to calling conventions • Create the necessaryyy symbolic information7 Outline • Introduction • Machine Language • Overview of a modern p processor • Memory Layout • Procedure Procedure A Abstraction bstraction • Procedure Linkage • • Guidelines Guidelines in in Creating Creating a a C Code ode Generator Generator Machines understand... LOCATION DATA 0046 8B45FC 0049 4863F0 004c 8B45FC 004f 4863D0 0052 0052 8B45FC 8B45FC 0055 4898 0057 8B048500 000000 005e 8B149500 000000 000000 0065 01C2 0067 8B45FC 006a 4898 006c 89D7 006e 033C8500 000000 0075 8B45FC 0078 4863C8 007b 007b 8B45F8 8B45F8 007e 4898 0080 8B148500 000000 Machines understand... LOCATION DATA ASSEMBLY INSTRUCTION 0046 8B45FC 4(rbp), eax 0049 4863F0 eax,rsi 004c 8B45FC 4(rbp), eax 004f 4863D0 eax,rdx 0052 0052 8B45FC 8B45FC movl movl 4(rbp), 4(rbp), eax eax 0055 4898 0057 8B048500 B(,rax,4), eax 000000 movl 005e 8B149500 A(,rdx,4), edx movslq 000000 000000 movl 0065 01C2 eax, edx movslq 0067 8B45FC 4(rbp), eax 006a 4898 movl 006c 89D7 addl ,, edi cltq 006e 033C8500 C(,rax,4), edi movl edx 000000 0075 8B45FC movl 4(rbp), eax 0078 4863C8 eax,rcx 007b 007b 8B45F8 8B45F8 movl movl 8(rbp) 8(rbp), eax eax movl 007e 4898 0080 8B148500 B(,rax,4), edx cltqaddl movl movslq movl cltqProgram (character stream) Lexical Analyzer (Scanner) Token Stream Syntax Syntax Analyzer Analyzer (Parser) (Parser) Parse Tree Intermediate Code Generator Highlevel IR Lowlevel IR Intermediate Representation Code Generator Assembly Assembly code codeProgram (character stream) Lexical Analyzer (Scanner) Token Stream Syntax Syntax Analyzer Analyzer (Parser) (Parser) Parse Tree Intermediate Code Generator Highlevel IR Lowlevel IR Intermediate Representation Code Generator Assembly Assembly code code Assembler linker Binary executable ProcessorAssembly y lang g uag g e • Advantages – Simplifies Simplifies code code generation generation due due to to use use o of f symbolic symbolic instructions and symbolic names – Logical Logical abstraction abstraction llayer ayer – Multiple Architectures can describe by a single assembly assembly language language ⇒ can modify the implementation • macro assembly y instructions • Disadvantages – Additional Additional process process o of f a assembling ssembling and and linking linking – Assembler adds overhead Assembly y lang guag g e • Relocatable machine language (object modules) – all locations(addresses) represented by symbols – Mapped to memory addresses at link and load time – Flexibility of separate compilation • Absolute machine language – add ddresses are h hard dcodd ded – simple and straightforward implementation – inflexible inflexible hard hard to to reload reload generated generated code code – Used in interrupt handlers and device drivers 11 Assembly example .section .LC0 LC0 : 0000 6572726F7200 .string "error" .text .globl fact .rodata fact: 0000 55 p pushq q rbpp 0001 4889E5 rsp, rbp 0004 4883EC10 16, rsp 0008 897DFC edi, 4(rbp) 000b 837DFC00 000f 7911 0, 4(rbp) 0011 0011 BF00000000 BF00000000 movl movl .LC0, .LC0, edi edi 0016 B800000000 .L2 001b E800000000 jns 0, eax 0020 EB22 printf .L2: subq movq 0022 837DFC00 .L3 0026 0026 7509 7509 jne jne L4 L4 cmpl movl jmp 0, 4(rbp) 0028 C745F801000000 movl . 002f EB13 call 1, 8(rbp) .L4: 0031 8B7DFC 4(rbp), edi .L3 0034 FFCF movl jmp 0036 0036 E800000000 E800000000 ll ll f factt edi 003b 0FAF45FC 4(rbp), eax cmpl 003f 8945F8 eax, 8(rbp) 0042 EB00 decl .L3: 0044 8B45F8 8(( rbp), p), eax .L1 0047 C9 ca jmp 0048 C3 movl imull movl movl leave ret Comp position of an Objj ect File .file • We use the ELF file format "test2.c" .section .LC0: .LC0: .string "error d" • The object file has: .rodata .section .text – Multiple Segments .globl fact fact: – – Symbol Symbol Information Information pushq rbp movq rsp, rbp – Relocation Information subq 16, rsp movl 8(rbp), eax leave • Segments Segments ret ret . – Global Offset Table .comm bar,4,4 .comm a,1,1 – Procedure Linkage Table .comm b,1,1 – Text Text (code) (code) .section –Data .long .LECIE1.LSCIE1 .long 0x0 .ehframe,"a",progbits – Read Only Data .byte 0x1 .string "" .uleb128 0x1 11 Outline • Introduction • Machine Language • Overview of a modern p processor • Memory Layout • Procedure Procedure A Abstraction bstraction • Procedure Linkage • • Guidelines Guidelines in in Creating Creating a a C Code ode Generator Generator Overview of a modern processor processor • ALU Memory Memory • Control Registers ALU • Memory • Registers Registers ControlArithmetic and Log gic Unit • Performs most of the data Memory Memory operations operations • Has the form: OP oprnd , oprnd 1 2 – oprnd oprnd = oprnd oprnd OP OP oprnd oprnd 2 2 1 1 2 2 Registers ALU Or OP oprnd 1 Control • Operands Operands are: are: – Immediate Value 25 –Register rax – Memory Memory 4(rbp) 4(rbp) • Operations are: – Arithmetic operations (add, sub, imul) – Logical Logical operations operations (and (and, sal) sal) – Unitary operations (inc, dec)Arithmetic and Log gic Unit • Many arithmetic operations can cause an exception Memory Memory – overflow and underflow • Can operate on different data types Registers ALU – addb 8 bits – addw 16 bits Control – addl 32 bits – addq 64 bits (Decaf is all 64 bit) – signed signed and and unsigned unsigned arithmetic arithmetic – Floatingpoint operations ((p separate ALU))Control • Handles the instruction seqqg uencing Memory Memory • Executing instructions – All All instructions instructions are are in in memory memory Registers ALU – Fetch the instruction pointed by the PC PC and and execute execute it it Control – For general instructions, increment the PC to p point to the next location in memoryControl • Unconditional Branches Memory Memory –Ft Fetchh tthhe nextt iinsttructition ffrom a different location – – Unconditional Unconditional jump jump to to an an address address Registers ALU jmp .L32 – Unconditional jp jump to an address Control in a register jmp rax –Th To handldle proceddure calllls call fact call r11Control • All arithmetic operations update the condition codes (() rFLAGS) Memory Memory • Compare explicitly sets the rFLAGS Registers ALU – cmp 0, rax • Conditional jumps on the rFLAGS Control – Jxx .L32 Jxx 4(rbp) – Examples: • JO JO JO Jump Overffllow • JC Jump Carry • JAE Jump if above or equal • JZ Jump is Zero • JNE Jump if not equalControl • Control transfer in special (rare) Memory Memory cases cases – traps and exceptions – Mechanism Mechanism Registers ALU • Save the next(or current) instruction location Control • find the address to jump to (from an exception vector) • jump jump to to that that location location18 When to use what • Give an examp ple where each of the branch instructions can be used 1. jp jmp L0 2. call L1 3. 3. jmp jmp rax rax 4. jz 4(rbp) 5 5 . jne jne L L1 1 Memoryy • Flat Address Sp pace Memory Memory – composed of words – by yte addressable Registers ALU • Need to store – Program Program Control – Local variables – Global Global variables variables and and data data –Stack – H HeapMemory y Memory Memory Heap p Dynamic Dynamic 0x800 0000 0000 Registers ALU Stack Stack Control Globals/ Data Data Readonly data Program Program Te Tex xt t 0x40 0000 Unmapp pped 0x0 Reg gisters • Instructions allow only limited memory Memory Memory operati tions – add 4(rbp), 8(rbp) add add r10 r10, 8( 8(rbp rbp) ) Registers ALU •Impp portant for performance Control – limited in number •Si Speciall regiistters – rbp base pointer – – rsp rsp stack stack pointer pointerMoving g Data Memory Memory – mov source d dest • Moves data – from from one one register register to to another another – from registers to memory Registers ALU – from memory to registers Control – push source • Pushes data into the stack – pop dest • Pops data from the stack to destOther interactions • Other op perations Memory Memory – Input/Output – Privilegp ge / secure operations Registers ALU – Handling special hardware •TLBs,, Caches etc. Control • Mostly Mostly via via system system calls calls – handcoded in assembly – compiler compiler can can treat treat them them as as a a normal normal function function call call22 Outline • Introduction • Machine Language • Overview of a modern p processor • Memory Layout • Procedure Procedure A Abstraction bstraction • Procedure Linkage • • Guidelines Guidelines in in Creating Creating a a C Code ode Generator Generator Components of a High Level Language Language CODE DATA Global Static Variables Control Flow Global Dynamic Data Procedures Local Variables Temporaries Statements Parameter Passing Data Access Readonly DataMemoryy y Layout •Heappg management Heap p Dynamic Dynamic – free lists 0x800 0000 0000 Stack Stack • starting location in Globals/ the text seg gment Data Data RRd eadonl ly data Program Program Te Tex xt t CODE DATA Global Static Variables 0x40 0000 Control Flow Global Dynamic Data Procedures Unmapp pped Local Variables Temporaries 0x0 Statements Parameter Passing Data Access Readonly DataAllocating g ReadOnly y Data • All ReadOnly data in the text .section .text seg gment .globl main .globl main main: • Integers enter 0, 0 – use load immediate movqq 5, x(ripp) • St Striings push x(rip) – use the .string macro push .msg call printf035 add 16, rsp leave ret CODE DATA .msg: Global Static Variables Control Flow Global Dynamic Data .string "Five: d\n" Procedures Local Variables Temporaries Statements Parameter Passing Data Access Readonly DataGlobal Variables .section .text .globl main • Allocation: Use the assembler's main: .comm directive enter enter 0 0, 0 0 movq 5, x(rip) • Use PC relative addressing push x(rip) – rip is the current instruction call printf035 address add 16, rsp – X(rip) will add the offset from leave the current instruction location to ret the space for x in the data segment segment to to rip rip .comm x, 8 – Creates easily recolatable binaries .comm name, size, alignment Th The .comm di directiive all llocates storage iin CODE DATA the data section. The storage is referenced Global Static Variables by the identifier name. Size is measured in Control Flow Global Dynamic Data bytes and must be a positive integer. Procedures Name cannot be predefined. Alignment is Local Variables optiil onal. IfIf alilignmentii is specifified d, th he Temporaries Statements address of name is aligned to a multiple of Parameter Passing alignment Data Access Readonly Data22 Outline • Introduction • Machine Language • Overview of a modern p processor • Memory Layout • Procedure Procedure A Abstraction bstraction • Procedure Linkage • • Guidelines Guidelines in in Creating Creating a a C Code ode Generator Generator Procedure Abstraction • Requires systemwide compact – Broad ag greement on memory y lay yout, p protection, resource allocation calling sequences, error handling – Must involve architecture (ISA), OS, compiler • • Provides Provides shared shared access access to to system systemwide wide facilities facilities – Storage management, flow of control, interrupts – Interface to inp put/outp put devices, , p protection facilities, , timers, , synchronization flags, counters, … • Establishes the need for a private context – C C reate pri ivate storage f for each h proced dure i invocatiion – Encapsulate information about control flow data abstractions The procedure abstraction is a social contract (Rousseau) Procedure Abstraction • In practical terms it leads to... – multiple procedures – library calls – compiled by many compilers, written in different languages, handwritten assembly • FFt or thh e projj ect t, we need d t to worry abb outt – Parameter passing – Ri Registters –Stack – Calling Calling c convention onventionParameter p passing g discip plines • Many y different methods – call by reference – call by y value – call by valueresult (copyin/copyout) 25 Parameter Passing g Discip plines Program int A; foo(int foo(int B) B) B = B + 1 B = B + A Main() A = 10; foo(A); • Call by value A is • Call by reference A is • Call Call by by value value result result A A iis s 25 Parameter Passing g Discip plines Program int A; foo(int foo(int B) B) B = B + 1 B = B + A Main() A = 10; foo(A); • Call by value A is 10 • Call by reference A is 22 • Call Call by by value value result result A Aiis s2 21 1 Parameter p passing g disci p plines • Many different methods – call by reference – call by value – – call call by by value value result result • How do you pass the parameters – via. the stack – via. the registers – or a combination • IIn th he D Decaf f lli lling conventiion, th he fi first 6 6 ca parameters are passed in registers. – – The The rest rest are are passed passed iin n tthe he stack stack Reg gisters • What to do with live reg gisters across a procedure call – Caller Saved – Calliee Saved 30 Question: • What are the advantag ges/disadvantag ges of: – Calliee saving of registers – Caller saving g of reg gisters • What registers should be used at the caller and and calliee calliee if if half half is is caller caller saved saved and and the the other half is callieesaved Reg gisters • What to do with live registers across a procedure call call – Caller Saved – Calliee Saved • In this segment, use registers only as shortlived temporaries temporaries mov 4(rbp), r10 mov 8(rbp), r11 add add r10, r10, r11 r11 mov r11, 8(rbp) – Should not be live across procedure calls – Will Will start start k keeping eeping data data iin n tthe he registers registers ffor or performance performance iin n Segment V The Stack 8n+16(rbp) argument n • Arguments 0 to 6 … are in: 16(rbp) argument 7 – rdi, rsi, rdx, 8(rbp) Return address rcx rcx, r8 r8 and and r9 r9 0(rbp) Previous rbp 8(rbp) local 0 … 8m8(rbp) local m 0(rsp) Variable size Cu urrent Pre vious 33 Question: •Why y use a stack Why y not use the heap p or preallocated in the data segment 34 Outline • Introduction • Machine Language • Overview of a modern p processor • Memory Layout • Procedure Procedure A Abstraction bstraction • Procedure Linkage • • Guidelines Guidelines in in Creating Creating a a C Code ode Generator Generator Procedure Linkag ges Standard p p rocedure linkag ge Procedure has procedure p • standard prolog prolog procedure q • standard epilog prolog Eac Each h call call in inv vo olv lves a es a precall ll • precall sequence postreturn epilog • post post r re eturn sequence turn sequence epilog return address rbp previous frame pointer Stack calliee saved registers • Calling: Caller local variables – Assume rcx is live and is caller save stack temporaries – Call foo(A, B, C, D, E, F, G, H, I) dynamic area • A to I are at 8(rbp) to 72(rbp) rsp call ller saved d regi i st t ers push rcx argument 9 argument 8 push 72(rbp) argument 7 push push 64(rbp) 64(rbp) return address push 56(rbp) mov 48(rbp), r9 mov 40(rbp), r8 mov 32(rbp), rcx mov 24(rbp), rdx mov 16(rbp), rsi mov 8( 8(b) rbp), d rdi i call foo return address rbp previous frame pointer Stack calliee saved registers • Calling: Calliee local variables – Assume rbx is used in the function and and is is calliee calliee s save ave stack temporaries – Assume 40 bytes are required for dynamic area locals call ll er saved d regi i st t ers argument 9 foo: argument 8 argument 7 push push rbp rbp rsp return address enter 48, 0 mov rsp, rbp previous frame pointer sub 48, rsp calliee saved registers registers mov b rbx, 8( 8( rb bp) ) local variables stack temporaries dynamic area return address previous frame pointer Stack calliee saved • Arguments registers • Call foo(A, B, C, D, E, F, G, H, I) local variables – Passed in by pushing before the call push 72(rbp) stack temporaries push 64(rbp) push 56(rbp) mov 48(rbp), r9 dynamic area mov 40(rbp), r8 mov 32(rbp), rcx mov 24(rbp), rdx call ller saved d regi ist ters mov 16(rbp), rsi argument 9 mov 8(rbp), rdi call foo argument 8 – Access A to F via registers argument 7 • or put them in local memory return address – Access rest using 16+xx(rbp) rbp previous frame pointer mov 16(rbp), rax calliee saved mov 24((rbp), p), r10 registers registers CODE DATA local variables Global Static Variables Control Flow Global Dynamic Data stack temporaries Procedures Local Variables rsp rsp Temporaries Statements dynamic area Parameter Passing Data Access Readonly Datareturn address previous frame pointer Stack calliee saved registers • Locals and Temporaries local variables – Calculate the size and allocate stack temporaries space on the stack dynamic area sub 48, rsp call ller saved d regi ist ters or enter 48, 48 00 argument 9 argument 8 argument 7 – Access Access using using 8 8xx(rbp) xx(rbp) return address rbp mov 28(rbp), r10 previous frame pointer calliee saved mov r11, 20(rbp) registers registers CODE DATA local variables Global Static Variables Control Flow Global Dynamic Data stack temporaries Procedures Local Variables rsp rsp Temporaries Statements dynamic area Parameter Passing Data Access Readonly Datareturn address previous frame pointer Stack calliee saved registers • Returning Calliee local variables – Assume the return value is the first temporary temporary stack temporaries dynamic area – Restore the caller saved register call ll er saved d regi i st t ers – Put the return value in rax argument 9 argument 8 – Teardown the call stack argument 7 return address rbp mov 8(rbp), rbx previous frame pointer calliee saved mov 16(rbp), rax registers registers mov rbp, rsp local variables leave pop rbp stack temporaries ret rsp rsp dynamic area return address rbp previous frame pointer Stack calliee saved registers • Returning Caller local variables – Assume the return value goes to the first first ttemporary emporary stack temporaries dynamic area – Restore the stack to reclaim the call ller saved d regi ist ters argument space argument 9 – Restore the caller save registers argument 8 rsp argument 7 call foo CODE DATA Global Static Variables Procedures add 24, rsp Global Dynamic Data Control Flow Local Variables pop rcx Temporaries Statements mov rax, 8(rbpp) Parameter Passing g Data Access Readonly Data …47 Question: •Do y you need the rbp p • What are the advantages and disadvantages of of having having rbp rbp 49 Outline • Introduction • Machine Language • Overview of a modern p processor • Memory Layout • Procedure Procedure A Abstraction bstraction • Procedure Linkage • • Guidelines Guidelines in in Creating Creating a a Code Code Generator Generator What We Covered Today y.. CODE DATA Global Static Variables Procedures Global Global Dynamic Dynamic Data Data Control Flow Local Variables Temporaries Statements Parameter Parameter Passing Passing Data Access Readonly DataGuidelines for the code generator generator • Lower the abstraction level slowly – Do many passes, that do few things (or one thing) • Easier to break the project down, generate and debug • K Keep tthh e ab bsttracttii on llevel l iisttentt cons – IR should have ‘correct’ semantics at all time • • At At least least y you ou should should k know now the the s semantics emantics – You may want to run some of the optimizations between the passes. • Use assertions liberally – Use an assertion to check your assumption Guidelines for the code generator generator • Do the simplest but dumb thing – it is ok to generate 0 + 1x + 0y – Code is painful to look at, but will help optimizations • Make Make sure sure you you k know now want want can can b be e done done at… at… – Compile time in the compiler – Runtime Runtime using using generated generated code code Guidelines for the code generator generator • Remember that optimizations will come later – Let Let the the optimizer optimizer do do the the optimizations optimizations – Think about what optimizer will need and structure your code accordingly – Example: Register allocation, algebraic simplification, constant propagation • Setup a good testing infrastructure – reg gression tests • If a input program creates a bug, use it as a regression test – Learn good bug hunting procedures • Example: Example: binary binary search searchMIT OpenCourseWare http://ocw.mit.edu 6.035 Computer Language Engineering Spring 2010 For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms.
sharer
Presentations
Free
Document Information
Category:
Presentations
User Name:
Dr.MasonHanks
User Type:
Teacher
Country:
Germany
Uploaded Date:
23-07-2017