Code optimization in compiler design ppt

the optimized code generation is disabled and windows forms designer optimized code generation
Dr.MasonHanks Profile Pic
Dr.MasonHanks,Germany,Teacher
Published Date:23-07-2017
Your Website URL(Optional)
Comment
Unoptimized Code Generation • Last time we left off on the p procedure abstraction … Saman Amarasinghe 2 6.035 ©MIT Fall 1998 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, % % r8 8 and d % % r9 9 0(%rbp) Previous %rbp -8(%rbp) local 0 … % %b rbp -8m-8(%rbp) local m – marks the beginning 0(%rsp) of of the the current current frame frame Variable size %rsp – marks the end Saman Amarasinghe 3 6.035 ©MIT Fall 2001 Cu urrent Pre vious 33 Q Question: use a stack? Wh • Why y y y not use the heap p or p pre- allocated in the data segment? Saman Amarasinghe 4 6.035 ©MIT Fall 2001 Procedure Linkag ges Pre-call: Standard p p rocedure linkag g e •Sa Sav ve e caller caller-sa sav ve ed r d re egister gisters s •Push arguments procedure p Prolog: prolog procedure q •PPh ush l old f d f rame poii nt ter prolog •Save calle-saved registers •Make room for temporaries pre-call ll Epilog: •Restore callee-saved post-return epilog •P Po op p old fr old frame pointer ame pointer •Store return value Post-return: epilog •Rt Restore l calll er-saved d •Pop arguments Saman Amarasinghe 5 6.035 ©MIT Fall 2001 return address rbp previous frame pointer calliee saved Stack 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 ll er 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 %rdii call foo Saman Amarasinghe 6 6.035 ©MIT Fall 2001 return address rbp previous frame pointer calliee saved Stack registers • Calling: Calliee local variables – Assume %rbx is used in the function and d i is calli lli ee save stack temporaries – Assume 40 bytes are required for locals dynamic area call ller saved d regi i st t ers foo: argument 9 push %rbp argument 8 argument 7 mov mov %rsp %rsp , %rbp %rbp rsp return address enter 48, 0 sub 48, %rsp previous frame pointer mov %rbx, -8(%rbp) calliee saved registers registers local variables stack temporaries dynamic area Saman Amarasinghe 7 6.035 ©MIT Fall 2001 return address previous frame pointer calliee saved Stack • 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 Read-only Data Saman Amarasinghe 8 6.035 ©MIT Fall 2001return address previous frame pointer calliee saved Stack 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 u using sing -8- 8 xx(%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 Read-only Data Saman Amarasinghe 9 6.035 ©MIT Fall 2001return address previous frame pointer calliee saved Stack registers • Returning Calliee local variables – Assume the return value is the first t t emporary 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 – Tear-down 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 Saman Amarasinghe 10 6.035 ©MIT Fall 2001 return address rbp previous frame pointer calliee saved Stack registers • Returning Caller local variables • (Assume the return value goes to the first t) temporary) stack temporaries – Restore the stack to reclaim the dynamic area argument space call ller saved d regi ist ters – Restore the caller save registers argument 9 – Save the return value 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 Read-only Data … Saman Amarasinghe 11 6.035 ©MIT Fall 200147 Q Question: • Do y you need the rbp p? • What are the advantages and disadvantages of having having rbp? rbp? Saman Amarasinghe 12 6.035 ©MIT Fall 2001 So far we covered.. CODE DATA Global Static Variables Procedures Global Global Dynamic Dynamic Data Data Control Flow Local Variables Temporaries Statements Parameter Parameter Passing Passing Data Access Read-only Data Saman Amarasinghe 13 6.035 ©MIT Fall 19988 Outline • Generation of expressions and statements • Generation of control flow • x86-64 Processor • Guidelines in writing a code generator Saman Amarasinghe 14 6.035 ©MIT Fall 1998 Exp pressions •Exp pressions are rep presented as trees – Expression may produce a value – Or,, it may y set the condition codes ( (boolean exp p rs) ) • How do you map expression trees to the machines? – How to arrange the evaluation order? – Wh Wh ere t to k keep th the i i nt t ermedi di at t e val l ues? ? • Two approaches – Stack Model – Flat List Model Saman Amarasinghe 15 6.035 ©MIT Fall 1998 Evaluatingp g expression trees • Stack model – Eval left-sub-tree Put the results on the stack – Eval right-sub-tree OP Put the results on the stack – Get top two values from the stack perform the operation OP put thhl e results on thhe stackk • Very inefficient Saman Amarasinghe 16 6.035 ©MIT Fall 1998Evaluatinggp expression trees • Flat List Model – The idea is to linearize the expression tree – Left to Right Depth-First Traversal of the expression tree • All All ocate temporari ies f for i intermedi diates ( (al ll l th h e nod d es of f th h e tree) ) – New temporary for each intermediate – All the temporaries on the stack (for now) – Each expression is a single 3-addr op • x = y op z • Code Code generation generation for for the the 3 3-addr addr expression expression – Load y into register %r10 – Load z into register %r11 – Perform Perform op op %r10 %r10, %r11 %r11 – Store %r11 to x Saman Amarasinghe 17 6.035 ©MIT Fall 1998 Issues in Loweringgp Expressions • Map intermediates to registers? – registers are limited • when the tree is large, registers may be insufficient ⇒ allocate space in the stack • No machine instruction is available – May need to expand the intermediate operation into multiple machine machine ops ops. • Very inefficient – too manyp y copies – don’t worry, we’ll take care of them in the optimization passes – kkt eep thhd e code generat tor very si impl le Saman Amarasinghe 18 6.035 ©MIT Fall 1998What about statements? • Assig g nment statements are simp ple – Generate code for RHS expression – Store the resulting g value to the LHS address • • But But what what about about conditionals conditionals and and l loops? oops? Saman Amarasinghe 19 6.035 ©MIT Fall 1998 28 Outline • Generation of statements • Generation of control flow • Guidelines in writing g g generator a code Saman Amarasinghe 20 6.035 ©MIT Fall 1998