F07 L01

Outline: 

Saman Amarasinghe 2 6.035 ©MIT Fall 1998 Outline Course Administration Information 6.975: Addendum to 6.035 Introduction to computer language engineering Why do we need a compiler? What are compilers? Anatomy of a compiler

Course Administration: 

Saman Amarasinghe 3 6.035 ©MIT Fall 1998 Course Administration Staff Optional Text Course Outline The Project Project Groups Grading

Staff: 

Saman Amarasinghe 4 6.035 ©MIT Fall 1998 Staff Lecturer Prof. Saman Amarasinghe saman@mit.edu 253-8879 32-G778 Prof. Chen Ding cding@cs.rochester.edu 32-G779 Course Secretary Mary McDavit mmcdavit@csail.mit.edu 32-G735 253-9620 Teaching Assistant Michal Karczmarek karczma@mit.edu

Reference Textbooks : 

Reference Textbooks Saman Amarasinghe 5 6.035 ©MIT Fall 1998

The Project: The Five Segments: 

Saman Amarasinghe 6 6.035 ©MIT Fall 1998 The Project: The Five Segments Lexical and Syntax Analysis Semantic Analysis Code Generation Data-flow Analysis Optimizations

Each Segment...: 

Saman Amarasinghe 7 6.035 ©MIT Fall 1998 Each Segment... Segment Start Project Description Lectures 2 to 5 lectures Project Time (Project Checkpoint & Design Document) Project Time Project Due

Project Groups: 

Saman Amarasinghe 8 6.035 ©MIT Fall 1998 Project Groups Each project group consists of 3 to 4 students Grading All group members (mostly) get the same grade

Weekly Group Meeting with the TA: 

Saman Amarasinghe 9 6.035 ©MIT Fall 1998 Weekly Group Meeting with the TA TA will schedule a weekly 30 minute slot The group will get to: Ask questions about the project Review feedback on design documents Discuss design decisions Describe what each person is doing Answer questions the TA has about the project TA will use this to measure individual contribution to the project  be there!

Grades: 

Saman Amarasinghe 10 6.035 ©MIT Fall 1998 Grades Compiler project 70% In-class Quizzes 30% (10% each) In-class mini-quizzes 10% (0.5% each)

Grades for the Project: 

Saman Amarasinghe 11 6.035 ©MIT Fall 1998 Grades for the Project Scanner/Parser 5% Semantic Checking 7.5% Code Generation 10% Data-flow Analysis 7.5% Optimizations 30% 60%

Optimization Segment: 

Saman Amarasinghe 12 6.035 ©MIT Fall 1998 Optimization Segment Making programs run fast We provide a test set of applications Figure-out what will make them run fast Prioritize and implement the optimizations Compiler derby at the end A “similar” application to the test set is provided the day before The compiler that produced the fastest code is the winner Do any optimizations you choose Including parallelization for multicores Grade is divided into: Documentation 6% Justify your optimizations and the selection process Optimization Implementation 12% Producing correct code Derby performance 12% 30%

The Quiz: 

Saman Amarasinghe 13 6.035 ©MIT Fall 1998 The Quiz Three Quizzes In-Class Quiz 50 Minutes (be on time!) Open book, open notes

Mini Quizzes: 

Mini Quizzes Saman Amarasinghe 14 6.035 ©MIT Fall 1998

Outline: 

Saman Amarasinghe 15 6.035 ©MIT Fall 1998 Outline Course Administration Information 6.975: Addendum to 6.035 Introduction to computer language engineering What are compilers? Why should we learn about them? Anatomy of a compiler

6.975 Programming Parallel Systems – A study of the problem and possible solutions to the Multicore Menace : 

6.975 Programming Parallel Systems – A study of the problem and possible solutions to the Multicore Menace Saman Amarasinghe 16 6.035 ©MIT Fall 1998 Joe programmer

Outline: 

Saman Amarasinghe 17 6.035 ©MIT Fall 1998 Outline Course Administration Information 6.975: Addendum to 6.035 Introduction to computer language engineering What are compilers? Why should we learn about them? Anatomy of a compiler

Why Study Compilers?: 

Saman Amarasinghe 18 6.035 ©MIT Fall 1998 Why Study Compilers? Compilers enable programming at a high level language instead of machine instructions. Malleability, Portability, Modularity, Simplicity, Programmer Productivity Also Efficiency and Performance

Compilers Construction touches many topics in Computer Science: 

Saman Amarasinghe 19 6.035 ©MIT Fall 1998 Compilers Construction touches many topics in Computer Science Theory Finite State Automata, Grammars and Parsing, data-flow Algorithms Graph manipulation, dynamic programming Data structures Symbol tables, abstract syntax trees Systems Allocation and naming, multi-pass systems, compiler construction Computer Architecture Memory hierarchy, instruction selection, interlocks and latencies, parallelism Security Detection of and Protection against vulnerabilities Software Engineering Software development environments, debugging Artificial Intelligence Heuristic based search

Power of a Language: 

Saman Amarasinghe 20 6.035 ©MIT Fall 1998 Power of a Language Can use to describe any action Not tied to a “context” Many ways to describe the same action Flexible

How to instruct a computer : 

Saman Amarasinghe 21 6.035 ©MIT Fall 1998 How to instruct a computer How about natural languages? English?? “Open the pod bay doors, Hal.” “I am sorry Dave, I am afraid I cannot do that” We are not there yet!! Natural Languages: Powerful, but… Ambiguous Same expression describes many possible actions

Programming Languages : 

Saman Amarasinghe 22 6.035 ©MIT Fall 1998 Programming Languages Properties need to be precise need to be concise need to be expressive need to be at a high-level (lot of abstractions)

High-level Abstract Descriptionto Low-level Implementation Details : 

Saman Amarasinghe 23 6.035 ©MIT Fall 1998 High-level Abstract Description to Low-level Implementation Details

1. How to instruct the computer: 

Saman Amarasinghe 24 6.035 ©MIT Fall 1998 1. How to instruct the computer Compiler

1. How to instruct the computer: 

Saman Amarasinghe 25 6.035 ©MIT Fall 1998 1. How to instruct the computer Input: High-level programming language Output: Low-level assembly instructions Compiler does the translation: Read and understand the program Precisely determine what actions it require Figure-out how to faithfully carry-out those actions Instruct the computer to carry out those actions

Input to the Compiler: 

Saman Amarasinghe 26 6.035 ©MIT Fall 1998 Input to the Compiler Standard imperative language (Java, C, C++) State Variables, Structures, Arrays Computation Expressions (arithmetic, logical, etc.) Assignment statements Control flow (conditionals, loops) Procedures

Output of the Compiler: 

Saman Amarasinghe 27 6.035 ©MIT Fall 1998 Output of the Compiler State Registers Memory with Flat Address Space Machine code – load/store architecture Load, store instructions Arithmetic, logical operations on registers Branch instructions

Example (input program): 

Saman Amarasinghe 28 6.035 ©MIT Fall 1998 Example (input program) int sumcalc(int a, int b, int N) { int i, x, y; x = 0; y = 0; for(i = 0; i <= N; i++) { x = x + (4*a/b)*i + (i+1)*(i+1); x = x + b*y; } return x; }

Example (Output assembly code): 

Saman Amarasinghe 29 6.035 ©MIT Fall 1998 Example (Output assembly code) sumcalc: pushq %rbp movq %rsp, %rbp movl %edi, -4(%rbp) movl %esi, -8(%rbp) movl %edx, -12(%rbp) movl $0, -20(%rbp) movl $0, -24(%rbp) movl $0, -16(%rbp) .L2: movl -16(%rbp), %eax cmpl -12(%rbp), %eax jg .L3 movl -4(%rbp), %eax leal 0(,%rax,4), %edx leaq -8(%rbp), %rax movq %rax, -40(%rbp) movl %edx, %eax movq -40(%rbp), %rcx cltd idivl (%rcx) movl %eax, -28(%rbp) movl -28(%rbp), %edx imull -16(%rbp), %edx movl -16(%rbp), %eax incl %eax imull %eax, %eax addl %eax, %edx leaq -20(%rbp), %rax addl %edx, (%rax) movl -8(%rbp), %eax movl %eax, %edx imull -24(%rbp), %edx leaq -20(%rbp), %rax addl %edx, (%rax) leaq -16(%rbp), %rax incl (%rax) jmp .L2 .L3: movl -20(%rbp), %eax leave ret .size sumcalc, .-sumcalc .section .Lframe1: .long .LECIE1-.LSCIE1 .LSCIE1:.long 0x0 .byte 0x1 .string "" .uleb128 0x1 .sleb128 -8 .byte 0x10 .byte 0xc .uleb128 0x7 .uleb128 0x8 .byte 0x90 .uleb128 0x1 .align 8 .LECIE1:.long .LEFDE1-.LASFDE1 .long .LASFDE1-.Lframe1 .quad .LFB2 .quad .LFE2-.LFB2 .byte 0x4 .long .LCFI0-.LFB2 .byte 0xe .uleb128 0x10 .byte 0x86 .uleb128 0x2 .byte 0x4 .long .LCFI1-.LCFI0 .byte 0xd .uleb128 0x6 .align 8

Mapping Time Continuum Compilation to Interpretation: 

Mapping Time Continuum Compilation to Interpretation Saman Amarasinghe 30 6.035 ©MIT Fall 1998

Anatomy of a Computer: 

Saman Amarasinghe 31 6.035 ©MIT Fall 1998 Anatomy of a Computer

Anatomy of a Computer: 

Saman Amarasinghe 32 6.035 ©MIT Fall 1998 Anatomy of a Computer Lexical Analyzer (Scanner) Token Stream Program (character stream) Lexical Analyzer (Scanner)

Lexical Analyzer (Scanner): 

Saman Amarasinghe 33 6.035 ©MIT Fall 1998 Lexical Analyzer (Scanner) Num(234) mul_op lpar_op Num(11) add_op rpar_op 2 3 4 * ( 1 1 + - 2 2 ) Num(-22)

Lexical Analyzer (Scanner): 

Saman Amarasinghe 34 6.035 ©MIT Fall 1998 Lexical Analyzer (Scanner) 18..23 + val#ue Num(234) mul_op lpar_op Num(11) add_op rpar_op 2 3 4 * ( 1 1 + - 2 2 ) Num(-22)

Anatomy of a Computer: 

Saman Amarasinghe 35 6.035 ©MIT Fall 1998 Anatomy of a Computer Lexical Analyzer (Scanner) Syntax Analyzer (Parser) Token Stream Parse Tree Program (character stream) Syntax Analyzer (Parser)

Syntax Analyzer (Parser): 

Saman Amarasinghe 36 6.035 ©MIT Fall 1998 Syntax Analyzer (Parser) num num + ( ) * num <expr> <expr> <expr> <expr> <expr> <expr> <op> <op> num ‘*’ ‘(‘ num ‘+’ num ‘)’

Syntax Analyzer (Parser): 

Saman Amarasinghe 37 6.035 ©MIT Fall 1998 Syntax Analyzer (Parser) int * foo(i, j, k)) int i; int j; { for(i=0; i j) { fi(i>j) return j; }

Anatomy of a Computer: 

Saman Amarasinghe 38 6.035 ©MIT Fall 1998 Anatomy of a Computer Intermediate Representation Semantic Analyzer Lexical Analyzer (Scanner) Syntax Analyzer (Parser) Token Stream Parse Tree Program (character stream) Semantic Analyzer

Semantic Analyzer: 

Saman Amarasinghe 39 6.035 ©MIT Fall 1998 Semantic Analyzer int * foo(i, j, k) int i; int j; { int x; x = x + j + N; return j; }

Anatomy of a Computer: 

Saman Amarasinghe 40 6.035 ©MIT Fall 1998 Anatomy of a Computer Code Optimizer Optimized Intermediate Representation Intermediate Representation Semantic Analyzer Lexical Analyzer (Scanner) Syntax Analyzer (Parser) Token Stream Parse Tree Program (character stream) Code Optimizer

Optimizer: 

Saman Amarasinghe 41 6.035 ©MIT Fall 1998 Optimizer int sumcalc(int a, int b, int N) { int i; int x, t, u, v; x = 0; u = ((a<<2)/b); v = 0; for(i = 0; i <= N; i++) { t = i+1; x = x + v + t*t; v = v + u; } return x; } int sumcalc(int a, int b, int N) { int i; int x, y; x = 0; y = 0; for(i = 0; i <= N; i++) { x = x+4*a/b*i+(i+1)*(i+1); x = x + b*y; } return x; }

Anatomy of a Computer: 

Saman Amarasinghe 42 6.035 ©MIT Fall 1998 Anatomy of a Computer Code Optimizer Code Generator Optimized Intermediate Representation Assembly code Intermediate Representation Semantic Analyzer Lexical Analyzer (Scanner) Syntax Analyzer (Parser) Token Stream Parse Tree Program (character stream) Code Generator

Code Generator: 

Saman Amarasinghe 43 6.035 ©MIT Fall 1998 Code Generator sumcalc: xorl %r8d, %r8d xorl %ecx, %ecx movl %edx, %r9d cmpl %edx, %r8d jg .L7 sall $2, %edi .L5: movl %edi, %eax cltd idivl %esi leal 1(%rcx), %edx movl %eax, %r10d imull %ecx, %r10d movl %edx, %ecx imull %edx, %ecx leal (%r10,%rcx), %eax movl %edx, %ecx addl %eax, %r8d cmpl %r9d, %edx jle .L5 .L7: movl %r8d, %eax ret int sumcalc(int a, int b, int N) { int i; int x, t, u, v; x = 0; u = ((a<<2)/b); v = 0; for(i = 0; i <= N; i++) { t = i+1; x = x + v + t*t; v = v + u; } return x; }

Program Translation: 

Saman Amarasinghe 44 6.035 ©MIT Fall 1998 Program Translation Correct The actions requested by the program has to be faithfully executed Efficient Intelligently and efficiently use the available resources to carry out the requests (the word optimization is used loosely in the compiler community – Optimizing compilers are never optimal)

Efficient Execution: 

Saman Amarasinghe 45 6.035 ©MIT Fall 1998 Efficient Execution Sergeant

Efficient Execution: 

Saman Amarasinghe 46 6.035 ©MIT Fall 1998 Efficient Execution Sergeant Where to cross the river? Use the bridge upstream or surprise the enemy by crossing downstream? How do I minimize the casualties??

Efficient Execution: 

Saman Amarasinghe 47 6.035 ©MIT Fall 1998 Efficient Execution President My poll ratings are low, lets invade a small nation General Russia or Bermuda? Or just stall for his poll numbers to go up?

Efficient Execution: 

Saman Amarasinghe 48 6.035 ©MIT Fall 1998 Efficient Execution Mapping from High to Low Simple mapping of a program to assembly language produces inefficient execution Higher the level of abstraction  more inefficiency If not efficient High-level abstractions are useless Need to: provide a high level abstraction with performance of giving low-level instructions

Efficient Execution help increase the level of abstraction: 

Saman Amarasinghe 49 6.035 ©MIT Fall 1998 Efficient Execution help increase the level of abstraction Programming languages From C to OO-languages with garbage collection Even more abstract definitions Microprocessor From simple CISC to RISC to VLIW to ….

The Multicore Dilemma : 

The Multicore Dilemma Saman Amarasinghe 50 6.035 ©MIT Fall 1998 Simple von Neumann Machine High Level Language Hard ware Compiler Multiple exposed cores High Level Language Hard ware Comp iler??

The Multicore Dilemma : 

The Multicore Dilemma Saman Amarasinghe 51 6.035 ©MIT Fall 1998 Simple von Neumann Machine High Level Language Hard ware Compiler Multiple exposed cores Parallel Language Hard ware Compiler

Optimization Example: 

Saman Amarasinghe 52 6.035 ©MIT Fall 1998 Optimization Example int sumcalc(int a, int b, int N) { int i; int x, y; x = 0; y = 0; for(i = 0; i <= N; i++) { x = x + (4*a/b)*i + (i+1)*(i+1); x = x + b*y; } return x; }

Slide53: 

Saman Amarasinghe 53 6.035 ©MIT Fall 1998 45 pushq %rbp movq %rsp, %rbp movl %edi, -4(%rbp) movl %esi, -8(%rbp) movl %edx, -12(%rbp) movl $0, -20(%rbp) movl $0, -24(%rbp) movl $0, -16(%rbp) .L2: movl -16(%rbp), %eax cmpl -12(%rbp), %eax jg .L3 movl -4(%rbp), %eax leal 0(,%rax,4), %edx leaq -8(%rbp), %rax movq %rax, -40(%rbp) movl %edx, %eax movq -40(%rbp), %rcx cltd idivl (%rcx) movl %eax, -28(%rbp) movl -28(%rbp), %edx imull -16(%rbp), %edx movl -16(%rbp), %eax incl %eax imull %eax, %eax addl %eax, %edx leaq -20(%rbp), %rax addl %edx, (%rax) movl -8(%rbp), %eax movl %eax, %edx imull -24(%rbp), %edx leaq -20(%rbp), %rax addl %edx, (%rax) leaq -16(%rbp), %rax incl (%rax) jmp .L2 .L3: movl -20(%rbp), %eax leave ret

Lets Optimize...: 

Saman Amarasinghe 54 6.035 ©MIT Fall 1998 Lets Optimize... int sumcalc(int a, int b, int N) { int i, x, y; x = 0; y = 0; for(i = 0; i <= N; i++) { x = x + (4*a/b)*i + (i+1)*(i+1); x = x + b*y; } return x; }

Constant Propagation: 

Saman Amarasinghe 55 6.035 ©MIT Fall 1998 Constant Propagation int i, x, y; x = 0; y = 0; for(i = 0; i <= N; i++) { x = x + (4*a/b)*i + (i+1)*(i+1); x = x + b*y; } return x;

Constant Propagation: 

Saman Amarasinghe 56 6.035 ©MIT Fall 1998 Constant Propagation int i, x, y; x = 0; y = 0; for(i = 0; i <= N; i++) { x = x + (4*a/b)*i + (i+1)*(i+1); x = x + b*y; } return x;

Constant Propagation: 

Saman Amarasinghe 57 6.035 ©MIT Fall 1998 Constant Propagation int i, x, y; x = 0; y = 0; for(i = 0; i <= N; i++) { x = x + (4*a/b)*i + (i+1)*(i+1); x = x + b*0; } return x;

Algebraic Simplification: 

Saman Amarasinghe 58 6.035 ©MIT Fall 1998 Algebraic Simplification int i, x, y; x = 0; y = 0; for(i = 0; i <= N; i++) { x = x + (4*a/b)*i + (i+1)*(i+1); x = x + b*0; } return x;

Algebraic Simplification: 

Saman Amarasinghe 59 6.035 ©MIT Fall 1998 Algebraic Simplification int i, x, y; x = 0; y = 0; for(i = 0; i <= N; i++) { x = x + (4*a/b)*i + (i+1)*(i+1); x = x + b*0; } return x;

Algebraic Simplification: 

Saman Amarasinghe 60 6.035 ©MIT Fall 1998 Algebraic Simplification int i, x, y; x = 0; y = 0; for(i = 0; i <= N; i++) { x = x + (4*a/b)*i + (i+1)*(i+1); x = x; } return x;

Copy Propagation: 

Saman Amarasinghe 61 6.035 ©MIT Fall 1998 Copy Propagation int i, x, y; x = 0; y = 0; for(i = 0; i <= N; i++) { x = x + (4*a/b)*i + (i+1)*(i+1); x = x; } return x;

Copy Propagation: 

Saman Amarasinghe 62 6.035 ©MIT Fall 1998 Copy Propagation int i, x, y; x = 0; y = 0; for(i = 0; i <= N; i++) { x = x + (4*a/b)*i + (i+1)*(i+1); x = x; } return x;

Copy Propagation: 

Saman Amarasinghe 63 6.035 ©MIT Fall 1998 Copy Propagation int i, x, y; x = 0; y = 0; for(i = 0; i <= N; i++) { x = x + (4*a/b)*i + (i+1)*(i+1); } return x;

Common Subexpression Elimination: 

Saman Amarasinghe 64 6.035 ©MIT Fall 1998 Common Subexpression Elimination int i, x, y; x = 0; y = 0; for(i = 0; i <= N; i++) { x = x + (4*a/b)*i + (i+1)*(i+1); } return x;

Common Subexpression Elimination: 

Saman Amarasinghe 65 6.035 ©MIT Fall 1998 Common Subexpression Elimination int i, x, y; x = 0; y = 0; for(i = 0; i <= N; i++) { x = x + (4*a/b)*i + (i+1)*(i+1); } return x;

Common Subexpression Elimination: 

Saman Amarasinghe 66 6.035 ©MIT Fall 1998 Common Subexpression Elimination int i, x, y, t; x = 0; y = 0; for(i = 0; i <= N; i++) { t = i+1; x = x + (4*a/b)*i + t*t; } return x;

Dead Code Elimination: 

Saman Amarasinghe 67 6.035 ©MIT Fall 1998 Dead Code Elimination int i, x, y, t; x = 0; y = 0; for(i = 0; i <= N; i++) { t = i+1; x = x + (4*a/b)*i + t*t; } return x;

Dead Code Elimination: 

Saman Amarasinghe 68 6.035 ©MIT Fall 1998 Dead Code Elimination int i, x, y, t; x = 0; y = 0; for(i = 0; i <= N; i++) { t = i+1; x = x + (4*a/b)*i + t*t; } return x;

Dead Code Elimination: 

Saman Amarasinghe 69 6.035 ©MIT Fall 1998 Dead Code Elimination int i, x, t; x = 0; for(i = 0; i <= N; i++) { t = i+1; x = x + (4*a/b)*i + t*t; } return x;

Loop Invariant Removal: 

Saman Amarasinghe 70 6.035 ©MIT Fall 1998 Loop Invariant Removal int i, x, t; x = 0; for(i = 0; i <= N; i++) { t = i+1; x = x + (4*a/b)*i + t*t; } return x;

Loop Invariant Removal: 

Saman Amarasinghe 71 6.035 ©MIT Fall 1998 Loop Invariant Removal int i, x, t; x = 0; for(i = 0; i <= N; i++) { t = i+1; x = x + (4*a/b)*i + t*t; } return x;

Loop Invariant Removal: 

Saman Amarasinghe 72 6.035 ©MIT Fall 1998 Loop Invariant Removal int i, x, t, u; x = 0; u = (4*a/b); for(i = 0; i <= N; i++) { t = i+1; x = x + u*i + t*t; } return x;

Strength Reduction: 

Saman Amarasinghe 73 6.035 ©MIT Fall 1998 Strength Reduction int i, x, t, u; x = 0; u = (4*a/b); for(i = 0; i <= N; i++) { t = i+1; x = x + u*i + t*t; } return x;

Strength Reduction: 

Saman Amarasinghe 74 6.035 ©MIT Fall 1998 Strength Reduction int i, x, t, u; x = 0; u = (4*a/b); for(i = 0; i <= N; i++) { t = i+1; x = x + u*i + t*t; } return x;

Strength Reduction: 

Saman Amarasinghe 75 6.035 ©MIT Fall 1998 Strength Reduction int i, x, t, u, v; x = 0; u = ((a<<2)/b); v = 0; for(i = 0; i <= N; i++) { t = i+1; x = x + v + t*t; v = v + u; } return x;

Register Allocation: 

Saman Amarasinghe 76 6.035 ©MIT Fall 1998 Register Allocation

Register Allocation: 

Saman Amarasinghe 77 6.035 ©MIT Fall 1998 Register Allocation $r8d = X $r9d = t $r10d = u $ebx = v $ecx = i fp Local variable X Local variable Y Local variable I

Optimized Example: 

Saman Amarasinghe 78 6.035 ©MIT Fall 1998 Optimized Example int sumcalc(int a, int b, int N) { int i, x, t, u, v; x = 0; u = ((a<<2)/b); v = 0; for(i = 0; i <= N; i++) { t = i+1; x = x + v + t*t; v = v + u; } return x; }

Slide79: 

Saman Amarasinghe 79 6.035 ©MIT Fall 1998 xorl %r8d, %r8d xorl %ecx, %ecx movl %edx, %r9d cmpl %edx, %r8d jg .L7 sall $2, %edi .L5: movl %edi, %eax cltd idivl %esi leal 1(%rcx), %edx movl %eax, %r10d imull %ecx, %r10d movl %edx, %ecx imull %edx, %ecx leal (%r10,%rcx), %eax movl %edx, %ecx addl %eax, %r8d cmpl %r9d, %edx jle .L5 .L7: movl %r8d, %eax ret pushq %rbp movq %rsp, %rbp movl %edi, -4(%rbp) movl %esi, -8(%rbp) movl %edx, -12(%rbp) movl $0, -20(%rbp) movl $0, -24(%rbp) movl $0, -16(%rbp) .L2: movl -16(%rbp), %eax cmpl -12(%rbp), %eax jg .L3 movl -4(%rbp), %eax leal 0(,%rax,4), %edx leaq -8(%rbp), %rax movq %rax, -40(%rbp) movl %edx, %eax movq -40(%rbp), %rcx cltd idivl (%rcx) movl %eax, -28(%rbp) movl -28(%rbp), %edx imull -16(%rbp), %edx movl -16(%rbp), %eax incl %eax imull %eax, %eax addl %eax, %edx leaq -20(%rbp), %rax addl %edx, (%rax) movl -8(%rbp), %eax movl %eax, %edx imull -24(%rbp), %edx leaq -20(%rbp), %rax addl %edx, (%rax) leaq -16(%rbp), %rax incl (%rax) jmp .L2 .L3: movl -20(%rbp), %eax leave ret Unoptimized Code Optimized Code

Compilers Optimize Programs for…: 

Saman Amarasinghe 80 6.035 ©MIT Fall 1998 Compilers Optimize Programs for… Performance/Speed Code Size Power Consumption Fast/Efficient Compilation Security/Reliability Debugging