Code generation optimization

code optimization in compiler design and code optimization in compiler with example
Dr.MasonHanks Profile Pic
Dr.MasonHanks,Germany,Teacher
Published Date:23-07-2017
Your Website URL(Optional)
Comment
Spring Spring 2010 2010 It Introd duct tii on tto Code Code Optimization Optimization Instruction Scheduling 5 Outline • Modern architectures • Introduction to instruction scheduling • • List List scheduling scheduling • Resource constraints • Scheduling across basic blocks • Trace scheduling g Saman Amarasinghe 2 6.035 ©MIT Fall 1998 Simp ple Machine Model • Instructions are executed in seq quence – Fetch, decode, execute, store results – One instruction at a time • For branch instructions, start fetching from a different different location location i if f needed needed – Check branch condition – Next Next instruction instruction may may come come from from a a new new location location given by the branch instruction Saman Amarasinghe 3 6.035 ©MIT Fall 1998 Simp ple Execution Model •5 Staggp e pipp e-line fetch decode execute memory writeback • Fetch: get the next instruction • Decode: figure-out what that instruction is • Execute: Perform ALU op peration – address calculation in a memory op • Memory: Memory: Do Do the the memory memory access access in in a a mem. mem. Op. Op. • Write Back: write the results back Saman Amarasinghe 4 6.035 ©MIT Fall 1998 Simp ple Execution Model time IF DE EXE MEM WB Inst 1 IF IF DE DE EXE EXE MEM MEM WB WB Inst 2 IF DE EXE MEM WB Inst 1 IF DE EXE MEM WB Inst 2 IF DE EXE MEM WB Inst 3 IF DE EXE MEM WB It Inst 4 4 IF DE EXE MEM WB Inst 5 Saman Amarasinghe 5 6.035 ©MIT Fall 1998 5 Outline • Modern architectures • Introduction to instruction scheduling • • List List scheduling scheduling • Resource constraints • Scheduling across basic blocks • Trace scheduling g Saman Amarasinghe 6 6.035 ©MIT Fall 1998 From a Simple Machine Model t to a R Real l MM achihi ne M Mod dell • Many pipeline stages – Pentium 5 – Pentium Pro 10 – Pentium IV (130nm) 20 – Pentium IV (90nm) 31 – Core Core 2 Duo 2 Duo 14 14 • Different instructions taking different amount of time to to execute execute • • Hardware Hardware to to stall stall the the pipeline pipeline if if an an instruction instruction uses uses a a result that is not ready Saman Amarasinghe 7 6.035 ©MIT Fall 1998Real Machine Model cont. • Most modern p processors have multip p le cores – Will deal with multicores next week • Each Each core core has has multiple multiple execution execution units units (superscalar) – If If the the instruction instruction sequence sequence is is correct correct , multiple multiple operations will happen in the same cycles – Even Even more more important important to to have have the the right right instruction instruction sequence Saman Amarasinghe 8 6.035 ©MIT Fall 1998 Instruction Scheduling g • Reorder instructions so that ppp ipeline stalls are minimized Saman Amarasinghe 9 6.035 ©MIT Fall 1998 Constraints On Scheduling g • Data dep pendencies • Control dependencies • • Resource Resource Constraints Constraints Saman Amarasinghe 10 6.035 ©MIT Fall 1998 Data Dependency between It Instructiti ons • If two instructions access the same variable,, they can be dependent • Kind of dep pendencies – True: write  read – Anti: read  write – Output: write  write • What to do if two instructions are dep pendent. – The order of execution cannot be reversed – Reduce the possibilities for scheduling Saman Amarasinghe 11 6.035 ©MIT Fall 1998 Comp p uting g Dep p endencies • For basic blocks, comp pute dep pendencies by y walking through the instructions • Identifying Identifying register register dependencies dependencies is is s simple imple – is it the same register? • • For For memory memory accesses accesses – simple: base + offset1 ?= base + offset2 – ddt ata d depend dence anal lysi is: a2i 2i ?? = a2i+1 2i+1 – interprocedural analysis: global ?= parameter – poii nter alili as anallysii s: p1f foo ?= p2f foo Saman Amarasinghe 12 6.035 ©MIT Fall 1998 Rep presenting g Dep pendencies • Using g p pendence DAG, one p per basic block a de • Nodes are instructions, edges represent dependencies dependencies Saman Amarasinghe 13 6.035 ©MIT Fall 1998 Rep p resenting g Dep pendencies •Using g p pendence DAG, one p per basic block a de • Nodes are instructions, edges represent dependencies dependencies 1 2 1: r2 = (r1 + 4) 2: 2: r3 r3 =(r1 (r1 + + 8) 8) 2 2 2 3: r4 = r2 + r3 4: 4: r5 r5 = = r2 r2 1 1 4 4 3 3 • Edge is labeled with Latency: – v(i (i  j) j) = d d el lay requi ired d b between i i ni i ti i ati i on ti i mes of f i and j minus the execution time required by i Saman Amarasinghe 14 6.035 ©MIT Fall 1998Examp ple 1: r2 = (r1 + 4) 2: r3 = (r2 + 4) 3: r4 = r2 + r3 4: r5 = r2 - 1 1 2 2 2 2 4 4 3 3 Saman Amarasinghe 15 6.035 ©MIT Fall 1998 Another Examp ple 1: r2 = (r1 + 4) 2: (r1 + 4) = r3 3: r3 = r2 + r3 1 4: r5 = r2 - 1 1 2 2 2 1 4 4 3 3 Saman Amarasinghe 16 6.035 ©MIT Fall 1998 Control Dependencies and R Resource C C onst t rai i nt ts • For now, lets only worry about basic blocks • For For now now , lets lets look look at at simple simple pipelines pipelines Saman Amarasinghe 17 6.035 ©MIT Fall 1998 Examp ple 1: lea var_a, %rax 2: add 4, %rax 3: inc %r11 4: mov 4: mov 4(%rsp), % 4(%rsp), %r10 r10 5: add %r10, 8(%rsp) 6: and 16(%rsp), %rbx 7: imul %rax, %rbx Saman Amarasinghe 18 6.035 ©MIT Fall 1998 Examp ple Results In 1: lea var_a, %rax 1 cycle 2: add 4, %rax 1 cycle 3: inc %r11 1 cycle 4: 4: mov mov 4(%rsp), % 4(%rsp), %r10 r10 3 3 cycles cycles 5: add %r10, 8(%rsp) 6: and 16(%rsp), %rbx 4 cycles 7: imul %rax, %rbx 3 cycles Saman Amarasinghe 19 6.035 ©MIT Fall 1998 Examp ple Results In 1: lea var_a, %rax 1 cycle 2: add 4, %rax 1 cycle 3: inc %r11 1 cycle 4: 4: mov mov 4(%rsp), % 4(%rsp), %r10 r10 3 3 cycles cycles 5: add %r10, 8(%rsp) 6: and 16(%rsp), %rbx 4 cycles 7: imul %rax, %rbx 3 cycles 1 2 3 4 st st 5 6 st st st 7 Saman Amarasinghe 20 6.035 ©MIT Fall 1998