Question? Leave a message!




Unoptimized Code Generation

Unoptimized Code Generation
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 Two App pproaches • Temp p late Matching g App pp roach – Peephole Optimization • Algorithmic Approach • Both are based on structural induction – Generate a representation for the sub-parts – Combine them into a representation for the whole Saman Amarasinghe 21 6.035 ©MIT Fall 1998 Generation of control flow: TT empllatte MMattchihi ng AA pproachh • Flatten the control structure – use a template • Put Put unique unique labels labels for for control control join join points points • Now generate the appropriate code Saman Amarasinghe 22 6.035 ©MIT Fall 1998 29 Temp plate for conditionals if (test) t true_bbod dy else false_body false body do the test jjoper lbt lab_true false_body jmp lab_end lab_true: true_body lab ab_ eed nd: : Saman Amarasinghe 23 6.035 ©MIT Fall 1998 Example Program if(ax if(ax bbx) x) dx = ax - bx; else dx = bx - ax; do test joper .L0 Return address previous frame pointer Local variable px (10) Local Local variable variable py py (20) (20) FALSE FALSE BBODY ODY Local variable pz (30) Argument 9: cx (30) jmp .L1 Argument 8: bx (20) .L0: Argument 7: ax (10) Return address rbp previous frame pointer TRUE BODY Local variable dx (??) L Local l vari iabl ble dy d (??) (??) .L1: rsp Local variable dz (??) Saman Amarasinghe 24 6.035 ©MIT Fall 1998Example Program if(ax if(ax bbx) x) dx = ax - bx; else dx = bx - ax; movq 16(%rbp), %r10 movq 24(%rbp), %r11 cmpq cmpq %r10, %r10, %r11 %r11 jg .L0 Return address previous frame pointer Local variable px (10) Local Local variable variable py py (20) (20) FALSE FALSE BBODY ODY Local variable pz (30) Argument 9: cx (30) jmp .L1 Argument 8: bx (20) .L0: Argument 7: ax (10) Return address rbp previous frame pointer TRUE BODY Local variable dx (??) L Local l vari iabl ble dy d (??) (??) .L1: rsp Local variable dz (??) Saman Amarasinghe 25 6.035 ©MIT Fall 1998Example Program if(ax if(ax bbx) x) dx = ax - bx; else dx = bx - ax; movq 16(%rbp), %r10 movq 24(%rbp), %r11 cmpq cmpq %r10, %r10, %r11 %r11 jg .L0 Return address movq 24(%rbp), %r10 previous frame pointer Local variable px (10) movq 16(%rbp), %r11 Local Local variable variable py py (20) (20) sub% bq %r1100, %%r1111 Local variable pz (30) movq %r11, -8(%rbp) Argument 9: cx (30) jmp .L1 Argument 8: bx (20) .L0: Argument 7: ax (10) Return address rbp previous frame pointer TRUE BODY Local variable dx (??) L Local l vari iabl ble dy d (??) (??) .L1: rsp Local variable dz (??) Saman Amarasinghe 26 6.035 ©MIT Fall 1998Example Program if(ax if(ax bbx) x) dx = ax - bx; else dx = bx - ax; movq 16(%rbp), %r10 movq 24(%rbp), %r11 cmpq cmpq %r10, %r10, %r11 %r11 jg .L0 Return address movq 24(%rbp), %r10 previous frame pointer Local variable px (10) movq 16(%rbp), %r11 Local Local variable variable py py (20) (20) sub% bq %r1100, %%r1111 Local variable pz (30) movq %r11, -8(%rbp) Argument 9: cx (30) jmp .L1 Argument 8: bx (20) .L0: Argument 7: ax (10) movq 16(%rbp), %r10 Return address movq 24(%rbp), %r11 rbp previous frame pointer subq %r10, %r11 Local variable dx (??) movq movq %r11, %r11, -8(%rbp) 8(%rbp) L Local l vari iabl ble dy d (??) (??) .L1: rsp Local variable dz (??) Saman Amarasinghe 27 6.035 ©MIT Fall 1998Temp p late for while loop ps while (test) bbd ody Saman Amarasinghe 28 6.035 ©MIT Fall 1998 Temp plate for while loop ps lab_cont: do the test while (test) jjoper oper lab lab_body body bbd ody jmp lab_end lab_body: bbd ody jmp lab_cont lab_end: Saman Amarasinghe 29 6.035 ©MIT Fall 1998 31 Temppp late for while loops lab_cont: do the test while (test) jjoper oper lab lab_body body bd body jmp lab_end lab_body: bbd ody jmp lab_cont lab_end: • An optimized template lab__cont: do the test CODE DATA Global Static Variables Control Flow joper lab_end Global Dynamic Data Procedures bodyy Local Variables Temporaries Statements jmp lab_cont Parameter Passing Data Access Read-only Data lab_end: Saman Amarasinghe 30 6.035 ©MIT Fall 199833 Q Q uestion: • What is the template for? do body body while (test) Saman Amarasinghe 31 6.035 ©MIT Fall 1998 33 Q Question: • What is the template for? do body body while (test) lab__begin: body do test joper lab_begin Saman Amarasinghe 32 6.035 ©MIT Fall 1998 33 Q Q uestion: • What is a drawback of the template based approach? approach? Saman Amarasinghe 33 6.035 ©MIT Fall 1998 Control Flow Grap( ph (CFG)) • Startingp g point: hig gh level intermediate format, symbol tables • Target: Target: CFG CFG – CFG Nodes are Instruction Nodes – CFG CFG Edges Edges Represent Represent Flow Flow of of Control Control – Forks At Conditional Jump Instructions – Merges Merges When When Flow Flow of of Control Control C Can an Reach Reach A A Point Point Multiple Ways – – Entry Entry and and Exit Exit Nodes Nodes Saman Amarasinghe 34 6.035 ©MIT Fall 1998 entry if if (x (x y) y) jl jl xxx xxx a = 0; else cmp p %r10,, %r11 a = 1; mov 0, a mov x, %r10 Mov y, %r11 mov 1, a exit Pattern for if then else Saman Amarasinghe 35 6.035 ©MIT Fall 1998 Short-Circuit Conditionals • In program, conditionals have a condition written as a boolean expression ((i n) && (vi = 0)) i k) • Semantics say should execute only as much as required to determine condition – Evaluate (vi = 0) only if (i n) is true – Evaluate i k only if ((i n) && (vi = 0)) is false false • Use control-flow graph to represent this short- circuit circuit evaluation evaluation Saman Amarasinghe 36 6.035 ©MIT Fall 1998 Short-Circuit Conditionals entry while (i n && vi = 0) i=i i = i+1; +1; jl xxx cmp %r10, %r11 jl yyy cmp %r10, %r11 mov mov % %r1 r11 1, ii exit add 1, %r11 mov i, %r11 Saman Amarasinghe 37 6.035 ©MIT Fall 1998 More Short-Circuit Conditionals if (a b c = 0) entry i=i i = i+1; +1; jl xxx cmp %r10, %r11 jne yyy cmp %r10, %r11 mov %r11, i add dd 1 1 , % % r11 11 mov i, %r11 exit Saman Amarasinghe 38 6.035 ©MIT Fall 1998 Routines for Destructuring Program R R epresent tati tion destruct(n) generates lowered form of structured code represented by n returns (b,e) - b is begin node, e is end node in destructed form shortcircuit(c, t, f) generates generates short short- -circuit circuit form form of of conditional conditional represented represented by by c c if c is true, control flows to t node if c is false,, control flows to f node returns b - b is begin node for condition evaluation new kind of node - nop node Saman Amarasinghe 39 6.035 ©MIT Fall 1998 Destructuring g Seq q Nodes destruct(n) generates lowered form of structured code represented by n returns (b,e) - b is begin node, e is end node in destructed form if if n iif s of thth e fform seq x y seq x y Saman Amarasinghe 40 6.035 ©MIT Fall 1998 Destructuring g Seq q Nodes destruct(n) generates lowered form of structured code represented by n returns (b,e) - b is begin node, e is end node in destructed form if if n iif s of thth e fform seq x y 1: (b ,e ) = destruct(x); x x b x seq e e x x y Saman Amarasinghe 41 6.035 ©MIT Fall 1998 Destructuring g Seq q Nodes destruct(n) generates lowered form of structured code represented by n returns (b,e) - b is begin node, e is end node in destructed form if if n if is of thth e fform seq x y 1: (b ,e ) = destruct(x); 2: (b ,e ) = destruct(y); x x y y b x seq e e x b b x y y e y Saman Amarasinghe 42 6.035 ©MIT Fall 1998 Destructuring g Seq q Nodes destruct(n) generates lowered form of structured code represented by n returns (b,e) - b is begin node, e is end node in destructed form if if n iif s of thth e fform seq x y 1: (b ,e ) = destruct(x); 2: (b ,e ) = destruct(y); x x y y 3: 3: next next(e (e ) ) = b b ; ; x y b x seq e e x b b x y y e y Saman Amarasinghe 43 6.035 ©MIT Fall 1998 Destructuring g Seq q Nodes destruct(n) generates lowered form of structured code represented by n returns (b,e) - b is begin node, e is end node in destructed form if if n iif s of thth e fform seq x y 1: (b ,e ) = destruct(x); 2: (b ,e ) = destruct(y); x x y y 3: 3: next next(e (e ) ) = b b ; ; 4: 4: return return (b (b e e ); ); x y x, y b x seq e e x b b x y y e y Saman Amarasinghe 44 6.035 ©MIT Fall 1998 Destructuring g If Nodes destruct(n) g g enerates lowered form of structured code rep presented by y n returns (b,e) - b is begin node, e is end node in destructed form if n is of the form if c x y if if c y x Saman Amarasinghe 45 6.035 ©MIT Fall 1998 Destructuring g If Nodes destruct(n) g g enerates lowered form of structured code rep p resented by y n returns (b,e) - b is begin node, e is end node in destructed form if n is of the form if c x y 1: (b ,e ) = destruct(x); x x b x e x if if c y x Saman Amarasinghe 46 6.035 ©MIT Fall 1998 Destructuring g If Nodes destruct(n) g g enerates lowered form of structured code rep presented by y n returns (b,e) - b is begin node, e is end node in destructed form if n is of the form if c x y 1: (b ,e ) = destruct(x); 2: (b ,e ) = destruct(y); x x y y b x e x if if c y b y e x y Saman Amarasinghe 47 6.035 ©MIT Fall 1998 Destructuring g If Nodes destruct(n) g g enerates lowered form of structured code rep p resented by y n returns (b,e) - b is begin node, e is end node in destructed form if n is of the form if c x y 1: (b ,e ) = destruct(x); 2: (b ,e ) = destruct(y); x x y y 3: e = new nop; b x e x if if e c y b y e x y Saman Amarasinghe 48 6.035 ©MIT Fall 1998 Destructuring g If Nodes destruct(n) g g enerates lowered form of structured code rep presented by y n returns (b,e) - b is begin node, e is end node in destructed form if n is of the form if c x y 1: (b ,e ) = destruct(x); 2: (b ,e ) = destruct(y); x x y y 3: e = new nop; 4: next(e ) = e; 5: next(e ) = e; x y b x e x if if e c y b y e x y Saman Amarasinghe 49 6.035 ©MIT Fall 1998 Destructuring g If Nodes destruct(n) g generates lowered form of structured code rep p resented by y n returns (b,e) - b is begin node, e is end node in destructed form if n is of the form if c x y 1: (b ,e ) = destruct(x); 2: (b ,e ) = destruct(y); x x y y 3: e = new nop; 4: next(e ) = e; 5: next(e ) = e; x y 6 6: b b = sh h ortci ircui i t((b c, b , b b ) ); c x y b x e x if if b b c e c y b y e x y Saman Amarasinghe 50 6.035 ©MIT Fall 1998 Destructuring g If Nodes destruct(n) g g enerates lowered form of structured code rep p resented by y n returns (b,e) - b is begin node, e is end node in destructed form if n is of the form if c x y 1: (b ,e ) = destruct(x); 2: (b ,e ) = destruct(y); x x y y 3: e = new nop; 4: next(e ) = e; 5: next(e ) = e; x y 6 6: b b = sh h ortci ircui i t(b (c, b , b b ) ) ; 7 7 : return (b (b e) ); c x y c, b x e x if if b b c e c y b y e x y Saman Amarasinghe 51 6.035 ©MIT Fall 1998 Destructuring g While Nodes destruct(n) generates lowered form of structured code represented by n returns (b,e) - b is begin node, e is end node in destructed form if if n if is of thth e ff orm whil hile c x while c x Saman Amarasinghe 52 6.035 ©MIT Fall 1998 Destructuring g While Nodes destruct(n) generates lowered form of structured code represented by n returns (b,e) - b is begin node, e is end node in destructed form if if n if is of thth e ff orm whil hile c x 1: e = new nop; while c x e Saman Amarasinghe 53 6.035 ©MIT Fall 1998 Destructuring g While Nodes destruct(n) generates lowered form of structured code represented by n returns (b,e) - b is begin node, e is end node in destructed form if if n if is of thth e ff orm whil hile c x 1: e = new nop; 2: (b ,e ) = destruct(x); x x while c x b x e e x Saman Amarasinghe 54 6.035 ©MIT Fall 1998 Destructuring g While Nodes destruct(n) generates lowered form of structured code represented by n returns (b,e) - b is begin node, e is end node in destructed form if if n if is of thth e ff orm whil hile c x 1: e = new nop; 2: (b ,e ) = destruct(x); x x 3: 3: b b = shortcircuit shortcircuit(c (c , b b , e); e); c x b while c c x b x e e x Saman Amarasinghe 55 6.035 ©MIT Fall 1998 Destructuring g While Nodes destruct(n) generates lowered form of structured code represented by n returns (b,e) - b is begin node, e is end node in destructed form if if n if is of thth e ff orm whil hile c x 1: e = new nop; 2: (b ,e ) = destruct(x); x x 3: 3: b b = shortcircuit shortcircuit(c (c, b b , e); e); 4: 4: next next(e (e ) ) = b b ; ; c x x c b while c c x b x e e x Saman Amarasinghe 56 6.035 ©MIT Fall 1998 Destructuring g While Nodes destruct(n) generates lowered form of structured code represented by n returns (b,e) - b is begin node, e is end node in destructed form if if n if is of thth e ff orm whil hile c x 1: e = new nop; 2: (b ,e ) = destruct(x); x x 3: 3: b b = shortcircuit shortcircuit(c (c , b b , e); e); 4: 4: next next(e (e ) ) = b b ; ; 5: 5: return return (b (b e); e); c x x c c, b while c c x b x e e x Saman Amarasinghe 57 6.035 ©MIT Fall 1998 Shortcircuiting g And Conditions shortcircuit(c, t, f) generates shortcircuit form of conditional represented by c returns b - b is begin node of shortcircuit form if if c if is of thth e ff orm c && && c 1 2 c && c 1 1 2 2 Saman Amarasinghe 58 6.035 ©MIT Fall 1998 Shortcircuiting g And Conditions shortcircuit(c, t, f) generates shortcircuit form of conditional represented by c returns b - b is begin node of shortcircuit form if if c if is of thth e ff orm c && && c 1 2 1: b = shortcircuit(c , t, f); 2 2 c && c 1 1 2 2 b b 2 f t Saman Amarasinghe 59 6.035 ©MIT Fall 1998 Shortcircuiting g And Conditions shortcircuit(c, t, f) generates shortcircuit form of conditional represented by c returns b - b is begin node of shortcircuit form if if c iif s of thth e ff orm c && && c 1 2 1: b = shortcircuit(c , t, f); 2: b = shortcircuit(c , b , f); 2 2 1 1 2 b b 1 c && c 1 1 2 2 b b 2 f t Saman Amarasinghe 60 6.035 ©MIT Fall 1998 Shortcircuiting g And Conditions shortcircuit(c, t, f) generates shortcircuit form of conditional represented by c returns b - b is begin node of shortcircuit form if if c if is of thth e ff orm c && && c 1 2 1: b = shortcircuit(c , t, f); 2: b = shortcircuit(c , b , f); 2 2 1 1 2 3: 3: return return (b (b ); ); 1 b b 1 c && c 1 1 2 2 b b 2 f t Saman Amarasinghe 61 6.035 ©MIT Fall 1998 Shortcircuiting g Or Conditions shortcircuit(c, t, f) generates shortcircuit form of conditional represented by c returns b - b is begin node of shortcircuit form if if c if is of thth e ff orm c c 1 2 c c 1 1 2 2 Saman Amarasinghe 62 6.035 ©MIT Fall 1998 Shortcircuiting g Or Conditions shortcircuit(c, t, f) generates shortcircuit form of conditional represented by c returns b - b is begin node of shortcircuit form if if c if is of thth e ff orm c c 1 2 1: b = shortcircuit(c , t, f); 2 2 c c 1 1 2 2 b b 2 t f Saman Amarasinghe 63 6.035 ©MIT Fall 1998 Shortcircuiting g Or Conditions shortcircuit(c, t, f) generates shortcircuit form of conditional represented by c returns b - b is begin node of shortcircuit form if if c if is of thth e ff orm c c 1 2 1: b = shortcircuit(c , t, f); 2: b = shortcircuit(c , t, b ); 2 2 1 1 2 b b 1 c c 1 1 2 2 b b 2 t f Saman Amarasinghe 64 6.035 ©MIT Fall 1998 Shortcircuiting g Or Conditions shortcircuit(c, t, f) generates shortcircuit form of conditional represented by c returns b - b is begin node of shortcircuit form if if c if is of thth e ff orm c c 1 2 1: b = shortcircuit(c , t, f); 2: b = shortcircuit(c , t, b ); 2 2 1 1 2 3: 3: return return (b (b ); ); b b 1 1 c c 1 1 2 2 b b 2 t f Saman Amarasinghe 65 6.035 ©MIT Fall 1998 Shortcircuiting g Not Conditions shortcircuit(c, t, f) generates shortcircuit form of conditional represented by c returns b - b is begin node of shortcircuit form if if c if is of thth e ff orm c 1 1: b = shortcircuit(c , f, t); return(b); 1 b c 1 f t Saman Amarasinghe 66 6.035 ©MIT Fall 1998 Comp puted Conditions shortcircuit(c, t, f) generates shortcircuit form of conditional represented by c returns b - b is begin node of shortcircuit form if if c if is of thth e ff orm e e 1 2 1: b = new cbr(e e , t, f); 2: return (b); 1 2 jl e e 1 2 cmp cmp t t f f e e 1 2 Saman Amarasinghe 67 6.035 ©MIT Fall 1998 Nop p s In Destructured Rep presentation entry while (i n && vi = 0) i i=i = i+1; +1; jl xxx cmp %r10, %r11 jl yyy nop cmp %r10, %r11 mov mov % %r1 r11 1, ii exit add 1, %r11 mov i, %r11 Saman Amarasinghe 68 6.035 ©MIT Fall 1998 Eliminating Nops Via Peephole Ot Optii mii zatition ... ... nop Saman Amarasinghe 69 6.035 ©MIT Fall 1998 46 Q Question: • What are the p pros and cons of temp plate matching vs. algorithmic approach? Saman Amarasinghe 70 6.035 ©MIT Fall 1998 49 Outline • Generation of statements • Generation of control flow • x86-64 Processor • Guidelines in writing a code generator Saman Amarasinghe 71 6.035 ©MIT Fall 1998 Guidelines for the code g generator • Lower the abstraction level slowly y – Do many passes, that do few things (or one thing) • Easier to break the project down, generate and debug • Keep the abstraction level consistent – IR IR should should h have ave ‘correct correct ’ semantics semantics at at all all time time • At least you should know the semantics – You You m may ay want want to to run run s some ome o of f t the he optimizations optimizations between the passes. • Use Use assertions assertions liberally liberally – Use an assertion to check your assumption Saman Amarasinghe 72 6.035 ©MIT Fall 1998 Guidelines for the code g generator • Do the simplest but dumb thing – i i t i i s ok k to generate 0 0 + 1 1 x + 0 0y – Code is painful to look at; let optimizations improve it • Make sure y you know want can be done at… – Compile time in the compiler – Runtime using gg generated code Saman Amarasinghe 73 6.035 ©MIT Fall 1998 Guidelines for the code g 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 code accordingly accordingly – Example: Register allocation, algebraic simplification, constant propagation • Setup a good testing infrastructure – regression tests • If a input program creates a bug, use it as a regression test – Learn good bug hunting procedures • Example: binary search , delta debugging Saman Amarasinghe 74 6.035 ©MIT Fall 1998 MIT 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.
Website URL
Comment