...

Spring 2009 Lecture 9: Introduction to Program Analysis and Optimization

by user

on
Category: Documents
34

views

Report

Comments

Transcript

Spring 2009 Lecture 9: Introduction to Program Analysis and Optimization
Spring 2009
Lecture 9: Introduction to
Program Analysis and
Optimization
Outline
• Introduction
• Basic Blocks
• Common Subexpression Elimination
• Copy
C
Propagation
P
ti
• Dead
ead Code Elimination
at o
• Algebraic Simplification
• Summary
Program
g
Analysis
y
• Compile-time reasoning about run-time behavior
of program
– Can discover things that are always true:
• “x
“ is
i always
l
1 in
i the
th statement
t t
t y = x + z””
• “the pointer p always points into array a”
• “the statement return 5 can never execute”
– Can infer things that are likely to be true:
• “the reference r usually refers to an object of class C”
• “the
the statement a = b + c appears to execute more frequently
than the statement x = y + z”
– Distinction between data and control-flow properties
Saman Amarasinghe
3
6.035
©MIT Fall 1998
Transformations
• Use analysis results to transform program
• Overall goal: improve some aspect of program
• Traditional goals:
–R
Reduce
d
number
b off executed
d instructions
i
i
– Reduce overall code size
• Other goals emerge as space becomes more complex
– Reduce number of cycles
• Use vector or DSP instructions
• Improve instruction or data cache hit rate
– Reduce power consumption
– Reduce memory usage
Saman Amarasinghe
4
6.035
©MIT Fall 1998
Outline
• Introduction
• Basic Blocks
• Common Subexpression Elimination
• Copy
C
Propagation
P
ti
• Dead
ead Code Elimination
at o
• Algebraic Simplification
• Summary
Control Flow Graph
p
• Nodes Represent
p
Computation
p
– Each Node is a Basic Block
a Block
o is a Sequence
qu
of
o Instructions
u o with
– Basic
• No Branches Out Of Middle of Basic Block
• No Branches Into Middle of Basic Block
• Basic Blocks should be maximal
– Execution of basic block starts with first
instruction
– Includes all instructions in basic block
• Edges Represent Control Flow
Saman Amarasinghe
6
6.035
©MIT Fall 1998
Control Flow Graph
p
into add(n, k) {
s = 0; a = 4; i = 0;
if (k == 0)
b = 1;
1
else
b = 2;
while (i < n) {
s = s + a*b;;
i = i + 1;
}
return s;
}Saman Amarasinghe
s = 0;
a = 4;
i = 0;
k == 0
b = 2;
b = 1;
i<n
s = s + a*b;
*b
i = i + 1;
7
return s;
6.035
©MIT Fall 1998
Basic Block Construction
• Start with instruction control-flow graph
g p
• Visit all edges in graph
• Merge adjacent nodes if
– Only one edge from first node
– Only one edge into second node
s = 0;
s = 0;
a = 4;
a = 4;
Saman Amarasinghe
8
6.035
©MIT Fall 1998
s = 0;
s = 0;
a = 4;
a = 4;
i = 0;
k == 0
b = 2;
b = 1;
i<n
s = s + a*b;
return s;
i = i + 1;
Saman Amarasinghe
9
6.035
©MIT Fall 2006
s = 0;
s = 0;
a = 4;
i = 0;
a = 4;
i = 0;
k == 0
b = 2;
b = 1;
i<n
s = s + a*b;
return s;
i = i + 1;
Saman Amarasinghe
10
6.035
©MIT Fall 2006
s = 0;
s = 0;
a = 4;
i = 0;
k == 0
a = 4;
i = 0;
k == 0
b = 2;
b = 1;
i<n
s = s + a*b;
return s;
i = i + 1;
Saman Amarasinghe
11
6.035
©MIT Fall 2006
s = 0;
a = 4;
i = 0;
k == 0
s = 0;
a = 4;
i = 0;
k == 0
b = 2;
b = 2;
b = 1;
i<n
s = s + a*b;
return s;
i = i + 1;
Saman Amarasinghe
12
6.035
©MIT Fall 2006
s = 0;
a = 4;
i = 0;
k == 0
s = 0;
a = 4;
i = 0;
k == 0
b = 2;
b = 2;
b = 1;
i<n
i<n
s = s + a*b;
return s;
i = i + 1;
Saman Amarasinghe
13
6.035
©MIT Fall 2006
s = 0;
a = 4;
i = 0;
k == 0
s = 0;
a = 4;
i = 0;
k == 0
b = 2;
b = 2;
b = 1;
i<n
i<n
s = s + a*b;
s = s + a*b;
return s;
i = i + 1;
Saman Amarasinghe
14
6.035
©MIT Fall 2006
s = 0;
a = 4;
i = 0;
k == 0
s = 0;
a = 4;
i = 0;
k == 0
b = 2;
b = 2;
b = 1;
i<n
i<n
s = s + a*b;
s = s + a*b;
i = i + 1;
return s;
i = i + 1;
Saman Amarasinghe
15
6.035
©MIT Fall 2006
s = 0;
a = 4;
i = 0;
k == 0
s = 0;
a = 4;
i = 0;
k == 0
b = 2;
b = 2;
b = 1;
i<n
i<n
s = s + a*b;
s = s + a*b;
i = i + 1;
return s;
i = i + 1;
Saman Amarasinghe
16
6.035
©MIT Fall 2006
s = 0;
a = 4;
i = 0;
k == 0
s = 0;
a = 4;
i = 0;
k == 0
b = 2;
b = 2;
b = 1;
i<n
i<n
s = s + a*b;
s = s + a*b;
i = i + 1;
return s;
return s;
i = i + 1;
Saman Amarasinghe
17
6.035
©MIT Fall 2006
s = 0;
a = 4;
i = 0;
k == 0
s = 0;
a = 4;
i = 0;
k == 0
b = 2;
b = 2;
b = 1;
i<n
i<n
s = s + a*b;
b = 1;
s = s + a*b;
i = i + 1;
return s;
return s;
i = i + 1;
Saman Amarasinghe
18
6.035
©MIT Fall 2006
s = 0;
a = 4;
i = 0;
k == 0
s = 0;
a = 4;
i = 0;
k == 0
b = 2;
b = 2;
b = 1;
i<n
i<n
s = s + a*b;
b = 1;
s = s + a*b;
i = i + 1;
return s;
return s;
i = i + 1;
Saman Amarasinghe
19
6.035
©MIT Fall 2006
s = 0;
a = 4;
i = 0;
k == 0
s = 0;
a = 4;
i = 0;
k == 0
b = 2;
b = 2;
b = 1;
i<n
i<n
s = s + a*b;
b = 1;
s = s + a*b;
i = i + 1;
return s;
return s;
i = i + 1;
Saman Amarasinghe
20
6.035
©MIT Fall 2006
Program Points, Split and Join
Points
Points
• One program point before and after each
statement in program
• Split point has multiple successors – conditional
branch statements only split points
• Merge point has multiple predecessors
• Each basic block
– Either starts with a merge point or its predecessor ends with a split point
– Either ends with a split point or its successor
starts
t t with
ith a merge point
i t
Saman Amarasinghe
21
6.035
©MIT Fall 1998
Basic Block Optimizations
p
• Common SubSubExpression Elimination
– a=(x+y)+z;
( y)
b=x+y;
y
– t=x+y; a=t+z; b=t;
• Constant Propagation
P opagation
– x=5; b=x+y;
– x=5;; b=5+y;
y;
– a=x+y; b=a; c=b+z;
– a=x+y; b=a; c=a+z;
• Dead Code Elimination
– a=x+y; b=a; b=a+z;
– a=x+y;
b=a+z
• Strength Reduction
• Algebraic Identities
– t=i*4;
t i*4
– t=i<<2;
– a=x*1;
– a=x;
Saman Amarasinghe
• Copy Propagation
22
6.035
©MIT Fall 1998
Basic Block Analysis
y Approach
pp
• Assume normalized basic block - all statements
are of the form
– var = var op var (where op is a binary operator)
– var = op var (where op is a unary operator)
– var = var
• Simulate a symbolic execution of basic block
– Reason about values of variables (or other
aspects of computation)
– Derive property of interest
Saman Amarasinghe
23
6.035
©MIT Fall 1998
Two Kinds of Variables
• Temporaries
p
Introduced Byy Compiler
p
– Transfer values only within basic block
odu d as
a part
pa of
o instruction
u o flattening
a
g
– Introduced
– Introduced by optimizations/transformations
– Typically assigned to only once
• Program Variables
– Declared in original program
– May be assigned to multiple times
– May
M transfer
t
f values
l
between
b t
basic
b i blocks
bl k
Saman Amarasinghe
24
6.035
©MIT Fall 1998
Outline
• Introduction
• Basic Blocks
• Common Subexpression Elimination
• Copy
C
Propagation
P
ti
• Dead
ead Code Elimination
at o
• Algebraic Simplification
• Summary
Value Numbering
• Reason about values of variables and expressions
in the program
– Simulate execution of basic block
– Assign virtual value to each variable and expression
• Discovered property: which variables and expressions
have the same value
• Stand
dard
duse:
– Common subexpression elimination
– Typically combined with transformation that
• Saves computed values in temporaries
• Replaces expressions with temporaries when value
off expressiion previiouslly computted
d
Saman Amarasinghe
26
6.035
©MIT Fall 1998
New Basic
Block
Original Basic
Block
a = x+y
t1 = a
b = a+z
t2 = b
b = b+y
t3 = b
c = t2
a = x+y
b=a
a+zz
b = b+y
c = a+z
Var to Val
x  v1
y  v2
a  v3
z  v4
4
b  v5
v6
c  v5
Saman Amarasinghe
Exp to Val
v1+v2  v3
v3+v4  v5
v5+v2  v6
27
Exp to Tmp
v1+v2  t1
v3+v4  t2
v5+v2  t6
6.035
©MIT Fall 1998
Value Numbering
g Summaryy
• Forward symbolic execution of basic block
• Each new value assigned to temporary
– a=x+y; becomes a=x+y; t=a;
– Temporary preserves value for use later in program even
if original variable rewritten
• a=x+y;
a=a+z; b=x+y becomes
• a=x+y; t=a; a=a+z; b=t;
• Maps
–V
Var to
t Vall – specifi
ifies symb
bolilic vallue for each
hvar iable
bl
– Exp to Val – specifies value of each evaluated expression
– Exp to Tmp – specifies tmp that holds value of each
evaluated expression
Saman Amarasinghe
28
6.035
©MIT Fall 1998
Map
p Usage
g
• Var to Val
– Used to compute symbolic value of y and z when
processing statement off fform x = y + z
• Exp
p to Tmp
p
– Used to determine which tmp to use if value(y) +
value(z) previously computed when processing
statement of form x = y + z
• Exp to Val
– Used
d to update
d
Var to Vall when
h
• processing statement of the form x = y + z, and
• value(y) + value(z) previously computed
Saman Amarasinghe
29
6.035
©MIT Fall 1998
Interesting
g Properties
p
• Finds common subexpressions even if they use
diff
different
t variables
i bl in
i expressions
i
– y=a+b;
x=b; z=a+x becomes
– y=a+b;
y a+b; t=y;
t y; x=b;
x b; z=t
z t
– Why? Because computes with symbolic values
• Finds common subexpressions even if variable
that originally held the value was overwritten
a+b;
yy=1;
1; zz=a+b
a+b becomes
– yy=a+b;
– y=a+b; t=y; y=1; z=t
y Because saves values awayy in
– Why?
temporaries
Saman Amarasinghe
30
6.035
©MIT Fall 1998
One More Interesting
g Property
p y
• Flattening and CSE combine to capture partial and
arbitrarily complex common subexpressions
w=(a+b)+c;
– After flattening:
t1=a+b;
t1
a+b; w
w=t1+c;
t1+c; x=b;
y=(a+x)+c; z=a+b;
x=b;
b; t2=a+x;
t2 a+x; yy=t2+c;
t2+c;
zz=a+b;
a+b;
– CSE algorithm notices that
• t1
1+c and
dt 2+c compute same vallue
• In the statement z = a+b, a+b has already been computed so
generated code can reuse the result
t1=a+b; w=t1+c; t3=w; x=b; t2=t1; y=t3;
Saman Amarasinghe
31
6.035
z=t1;
©MIT Fall 1998
Problems I
• Algorithm has a temporary for each new value
– a=x+y; t1=a;
• Introduces
– lots of temporaries
– lots of copy statements to temporaries
• In many cases, temporaries and copy statements
are unnecessary
• So
S we eliminate
li i t them
th
with
ith copy propagation
ti and
d
dead code elimination
Saman Amarasinghe
32
6.035
©MIT Fall 1998
Problems II
• Expressions have to be identical
– a=x+y+z; b=y+z+x; c=x*2+y+2*z–(x+z)
• We use canonicalization
• We use algebraic simplification
Saman Amarasinghe
33
6.035
©MIT Fall 1998
Copy
py Propagation
p g
• Once again, simulate execution of program
• If can, use original variable instead of temporary
– a=x+y; b=x+y;
– After CSE becomes a=x+y; t=a; b=t;
– After CP becomes a=x+y; t=a; b=a;
– After
Aft DCE b
becomes a=x+y;
b=a;
b
• Key idea:
–d
determine
t
i when
h original
i i l variable
i bl is
i NOT overwritten
itt
between its assignment statement and the use of the
computed value
– If not overwritten, use original variable
Saman Amarasinghe
34
6.035
©MIT Fall 1998
Outline
• Introduction
• Basic Blocks
• Common Subexpression Elimination
• Copy
C
Propagation
P
ti
• Dead
ead Code Elimination
at o
• Algebraic Simplification
• Summary
Copy
py Propagation
p g
Maps
p
• Maintain two maps
p
– tmp to var: tells which variable to use instead
of a given temporary variable
– var to set: inverse of tmp to var. tells which
temps are mapped to a given variable by tmp
to var
Saman Amarasinghe
36
6.035
©MIT Fall 1998
Copy
py Propagation
p g
Example
p
• Original
• After CSE and Copy
Propagation
a = x+y
x+y
b = a+z
c = x+y
a=b
a = x+y
t1 = a
b = a+z
t2 = b
c=a
a=b
a
• After CSE
a = x+y
t1 = a
b = a+z
t2 = b
c = t1
t1
a = b
Saman Amarasinghe
37
6.035
©MIT Fall 2006
Copy
py Propagation
p g
Example
p
Basic Block
Aft CSE
After
Basic Block After
CSE and
d Copy
C
Prop
a = x+y
t1 = a
a = x+y
t1 = a
t1
tmp to var
var to set
t1  a
a {t1}
Saman Amarasinghe
38
6.035
©MIT Fall 2006
Copy
py Propagation
p g
Example
p
Basic Block
Af
After
CSE
Basic Block After
CSE and
d Copy
C
Prop
a = x+y
t1 = a
b = a+z
t2 = b
a = x+y
t1 = a
t1
b = a+z
t2 = b
tmp to var
var to set
t1  a
t2  b
Saman Amarasinghe
a {t1}
b {t2}
t2}
39
6.035
©MIT Fall 2006
Copy
py Propagation
p g
Example
p
Basic Block
Aft CSE
After
Basic Block After
CSE and
d Copy
C
Prop
a = x+y
t1 = a
b = a+z
t2 = b
c = t1
a = x+y
t1 = a
t1
b = a+z
t2 = b
tmp to var
var to set
t1  a
t2  b
Saman Amarasinghe
a {t1}
b {t2}
t2}
40
6.035
©MIT Fall 2006
Copy
py Propagation
p g
Example
p
Basic Block
Aft CSE
After
Basic Block After
CSE and
d Copy
C
Prop
a = x+y
t1 = a
b = a+z
t2 = b
c = t1
a = x+y
t1 = a
t1
b = a+z
t2 = b
c=a
tmp to var
var to set
t1  a
t2  b
Saman Amarasinghe
a {t1}
b {t2}
t2}
41
6.035
©MIT Fall 2006
Copy
py Propagation
p g
Example
p
Basic Block
Aft CSE
After
Basic Block After
CSE and
d Copy
C
Prop
a = x+y
t1 = a
b = a+z
t2 = b
c = t1
a=b
a = x+y
t1 = a
t1
b = a+z
t2 = b
c=a
a=b
tmp to var
var to set
t1  a
t2  b
Saman Amarasinghe
a {t1}
b {t2}
t2}
42
6.035
©MIT Fall 2006
Copy
py Propagation
p g
Example
p
Basic Block
Aft CSE
After
Basic Block After
CSE and
d Copy
C
Prop
a = x+y
t1 = a
b = a+z
t2 = b
c = t1
a=b
a = x+y
t1 = a
t1
b = a+z
t2 = b
c=a
a=b
tmp to var
var to set
t1  t1
t2  b
Saman Amarasinghe
a {}
b {t2}
t2}
43
6.035
©MIT Fall 2006
Outline
• Introduction
• Basic Blocks
• Common Subexpression Elimination
• Copy
C
Propagation
P
ti
• Dead
ead Code Elimination
at o
• Algebraic Simplification
• Summary
Dead Code Elimination
• Copy
py propagation
p p g
keeps
p all temps
p around
• May be temps that are never read
• Dead Code Elimination removes them
Basic Block After
CSE and CP
Basic Block After
CSE CP and DCE
CSE,
a = x+y
t1 = a
b = a+z
t2 = b
c=a
a=b
Saman Amarasinghe
a = x+y
b = a+z
c=a
a=b
45
6.035
©MIT Fall 1998
Dead Code Elimination
• Basic Idea
– Process Code In Reverse Execution Order
a a a set of
o variables
a ab
that
a are
a needed
d d
– Maintain
later in computation
g
to a temporary
p
y
– If encounter an assignment
that is not needed, remove assignment
Saman Amarasinghe
46
6.035
©MIT Fall 1998
Basic Block After
CSE and Copy Prop
a = x+y
t1 = a
b = a+z
t2 = b
c=a
a=b
Needed Set
{ }
{b}
Saman Amarasinghe
47
6.035
©MIT Fall 2006
Basic Block After
CSE and Copy Prop
a = x+y
t1 = a
b = a+z
t2 = b
c=a
a=b
Needed Set
{{a,, b}}
Saman Amarasinghe
48
6.035
©MIT Fall 2006
Basic Block After
CSE and Copy Prop
a = x+y
t1 = a
b = a+z
t2 = b
c=a
a=b
Needed Set
{{a,, b}}
Saman Amarasinghe
49
6.035
©MIT Fall 2006
Basic Block After
CSE and Copy Prop
a = x+y
t1 = a
b = a+z
c=a
a=b
Needed Set
{{a,, b}}
Saman Amarasinghe
50
6.035
©MIT Fall 2006
Basic Block After
CSE and Copy Prop
a = x+y
t1 = a
b = a+z
c=a
a=b
Needed Set
{{a,, b,, z}}
Saman Amarasinghe
51
6.035
©MIT Fall 2006
Basic Block After
CSE and Copy Prop
a = x+y
t1 = a
b = a+z
c=a
a=b
Needed Set
{{a,, b,, z}}
Saman Amarasinghe
52
6.035
©MIT Fall 2006
Basic Block After
CSE and Copy Prop
a = x+y
b = a+z
c=a
a=b
Needed Set
{{a,, b,, z}}
Saman Amarasinghe
53
6.035
©MIT Fall 2006
Basic Block After , CSE Copy Propagation,
and Dead Code Elimination
a = x+y
b = a+z
c=a
a=b
Needed Set
{{a,, b,, z}}
Saman Amarasinghe
54
6.035
©MIT Fall 2006
Basic Block After , CSE Copy Propagation,
and Dead Code Elimination
a = x+y
b = a+z
c=a
a = b
Needed Set
{{a,, b,, z}} Saman Amarasinghe
55
6.035
©MIT Fall 2006
Outline
• Introduction
• Basic Blocks
• Common Subexpression Elimination
• Copy
C
Propagation
P
ti
• Dead
ead Code Elimination
at o
• Algebraic Simplification
• Summary
Algebraic
g
Simplification
p
• Apply
pp y our knowledge
g
from alg
gebra,, number
theory etc. to simplify expressions
Saman Amarasinghe
57
6.035
©MIT Fall 1998
Algebraic
g
Simplification
p
• Apply
pp y our knowledge
g from algebra,
g
, number
theory etc. to simplify expressions
• Example
–a+0
–a*1
–a/1
–a*0
–0-a
– a + (-b)
– -(-a)
( a)
Saman Amarasinghe







a
a
a
0
-a
a-b
a
58
6.035
©MIT Fall 1998
Algebraic
g
Simplification
p
• Apply
pp y our knowledge
g
from alg
gebra,, number
theory etc. to simplify expressions
• Example
Example
–a
–a
–a
–a




Saman Amarasinghe
true
false
true
false




59
a
false
true
a
6.035
©MIT Fall 1998
Algebraic
g
Simplification
p
• Apply
pp y our knowledge
g
from alg
gebra,, number
theory etc. to simplify expressions
• Example
Example
–a^2
–a*2
–a*8
Saman Amarasinghe
 a*a
 a+a
 a << 3
60
6.035
©MIT Fall 1998
Opportunities for
Algebraic Simplification
Simplification
• In the code
– Programmers are lazy to simplify expressions
– Programs are more readable with full expressions
• After compiler expansion
– Example: Array read A[8][12] will get expanded to
– *(Abase + 4*(12 + 8*256)) which can be simplified
• After other optimizations
Saman Amarasinghe
61
6.035
©MIT Fall 1998
Usefulness of Algebraic
g
Simplification
p
•R
Reduces
d
the
th number
b off instructions
i t ti
• Uses less expensive instructions
• Enable other optimizations
Saman Amarasinghe
62
6.035
©MIT Fall 1998
Implementation
p
• Not a data-flow optimization!
p
• Find candidates that matches the
simplification rules and simplify the
expression trees
• Candidates may not be obvious
Saman Amarasinghe
63
6.035
©MIT Fall 1998
Implementation
p
• Not a data-flow optimization!
p
• Find candidates that matches the
simplification rules and simplify the
expression trees
• Candidates may not be obvious
– Example
a+b-a
+
-
a
b
Saman Amarasinghe
64
a
6.035
©MIT Fall 1998
Use knowledge
g about operators
p
• Commutative operators
– a op b = b op a
–
• Associative operators
– ((a op
p b)) op
p c = b op
p (a op
p c))
Saman Amarasinghe
65
6.035
©MIT Fall 1998
Canonical Format
• Put expression
p
trees into a canonical
format
– Sum of multiplicands
p
– Variables/terms in a canonical order
– Example
(a+3)*(a+8)*4  4*a*a+44*a+96
– Section 12.3.1 of whale book talks about this
Saman Amarasinghe
66
6.035
©MIT Fall 1998
Effects on the Numerical Stabilityy
• Some alg
gebraic simp
plifications mayy produce
p
incorrect results
Saman Amarasinghe
67
6.035
©MIT Fall 1998
Effects on the Numerical Stabilityy
• Some alg
gebraic simp
plifications mayy produce
p
incorrect results
• Example
– (a / b)*0 + c
Saman Amarasinghe
68
6.035
©MIT Fall 1998
Effects on the Numerical Stabilityy
• Some alg
gebraic simp
plifications mayy produce
p
incorrect results
• Example
– (a / b)*0 + c
– we can simplify this to c
Saman Amarasinghe
69
6.035
©MIT Fall 1998
Effects on the Numerical Stabilityy
• Some alg
gebraic simp
plifications mayy produce
p
incorrect results
• Example
– (a / b)*0 + c
– we can simplify this to c
– But what about when b = 0
should be a exception, but we
we’llll get a result!
Saman Amarasinghe
70
6.035
©MIT Fall 1998
Outline
• Introduction
• Basic Blocks
• Common Subexpression Elimination
• Copy
C
Propagation
P
ti
• Dead
ead Code Elimination
at o
• Algebraic Simplification
• Summary
Interesting
g Properties
p
• Analysis and Transformation Algorithms S b li ll Simulate
Symbolically
Si l t Execution
E
ti off Program
P
– CSE and Copy Propagation go forward
– Dead Code Elimination goes backwards
• Transformations stacked
– Group of basic transformations work together
– Often, one transformation creates inefficient code that
is cleaned up by following transformations
– Transformations can be useful even if original code
may not benefit from transformation
Saman Amarasinghe
72
6.035
©MIT Fall 1998
Other Basic Block Transformations
• Constant Propagation
p g
• Strength Reduction
– a<<2 = a
a*4;
4; a+a+a = 3
3*a;
a;
• Do these in unified transformation
framework not in earlier or later phases
framework,
Saman Amarasinghe
73
6.035
©MIT Fall 1998
Summaryy
• Basic block analyses and transformations
• Symb
bolilicalllly siimullate
t executi
tion offprogram
– Forward (CSE, copy prop, constant prop)
– Backward (Dead code elimination)
• Stacked groups of analyses and transformations that work
together
– CSE introduces excess temp
poraries and copy
pystatements
– Copy propagation often eliminates need to keep temporary
variables around
– Dead code elimination removes useless code
• Similar in spirit to many analyses and transformations that
operate across basic blocks
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.
Fly UP