Dataflow Analysis

Lecture on data-flow analysis for Compiler Construction course at TU Delft

1. Challenge the future
Delft
University of
Technology
Course IN4303, 2016-2017
Compiler Construction
Guido Wachsmuth, Eelco Visser
Dataflow Analysis

2. today’s lecture
Dataflow Analysis
Overview
Control flow graphs
•intermediate representation
2

3. today’s lecture
Dataflow Analysis
Overview
Control flow graphs
•intermediate representation
Non-local optimizations
•dead code elimination
•constant & copy propagation
•common subexpression elimination
2

4. today’s lecture
Dataflow Analysis
Overview
Control flow graphs
•intermediate representation
Non-local optimizations
•dead code elimination
•constant & copy propagation
•common subexpression elimination
Data flow analyses
•liveness analysis
•reaching definitions
•available expressions
2

5. today’s lecture
Dataflow Analysis
Overview
Control flow graphs
•intermediate representation
Non-local optimizations
•dead code elimination
•constant & copy propagation
•common subexpression elimination
Data flow analyses
•liveness analysis
•reaching definitions
•available expressions
Optimizations (again)
2

6. Term Rewriting
Optimizations
I
3

7. optimization
Dataflow Analysis
Optimizing Compilers
Fully optimizing compiler
•Opt(P) produces smallest program with same I/O behavior
•smallest program for non-terminating programs without I/O:

Loop = (L : goto L)
•solves halting problem: Opt(Q) = Loop iff Q halts
Optimizing compiler
•produces program with same I/O behavior
•that is smaller or faster
Full employment theorem for compiler writers
•there is always a better optimizing compiler
4

8. optimization
Dataflow Analysis
Local vs Non-Local Optimizations
Local optimizations
•peephole optimization
•constant folding
•pattern match + rewrite
Non-local optimizations
•constant propagation
•dead-code elimination
•require information from different parts of program
5
iload 1
iload 1
mul
iload 1
dup
mul
(3 + 4) * x 7 * x

9. optimization
Dataflow Analysis
Program Optimizations
Register allocation
•keep non-overlapping temporaries in same register
Common-subexpression elimination
•if expression is computed more than once, eliminate one computation
Dead-code elimination
•delete computation whose result will never be used
Constant folding
•if operands of expression are constant, do computation at compile-time
And many more possible optimizations
6

10. example
Dataflow Analysis
Dead Code Elimination
7
delete computation whose result will never be used
a ← 0
b ← a + 1
c ← c + b
a ← 2 * b
return c

11. example
Dataflow Analysis
Dead Code Elimination
7
a ← 0
b ← a + 1
c ← c + b
return c
delete computation whose result will never be used
a ← 0
b ← a + 1
c ← c + b
a ← 2 * b
return c

12. example
Dataflow Analysis
Constant Propagation
8
a ← 0
b ← a + 1
c ← c + b
a ← 2 * b
return c
substitute reference to constant valued variable

13. example
Dataflow Analysis
Constant Propagation
8
a ← 0
b ← 0 + 1
c ← c + b
a ← 2 * b
return c
a ← 0
b ← a + 1
c ← c + b
a ← 2 * b
return c
substitute reference to constant valued variable

14. example
Dataflow Analysis
Constant Propagation + Folding
9
a ← 1
b ← a + 1
c ← c + b
a ← 2 * b
return c

15. example
Dataflow Analysis
Constant Propagation + Folding
9
a ← 0
b ← 2
c ← c + 2
a ← 4
return c
a ← 1
b ← a + 1
c ← c + b
a ← 2 * b
return c

16. example
Dataflow Analysis
Copy Propagation
10
a ← e
b ← a + 1
c ← c + b
a ← 2 * b
return c

17. example
Dataflow Analysis
Copy Propagation
10
a ← e
b ← e + 1
c ← c + b
a ← 2 * b
return c
a ← e
b ← a + 1
c ← c + b
a ← 2 * b
return c

18. example
Dataflow Analysis
Common Subexpression Elimination
11
c ← a + b
d ← 1
e ← a + b
if expression is computed more than once, eliminate one computation

19. example
Dataflow Analysis
Common Subexpression Elimination
11
c ← a + b
d ← 1
e ← a + b
x ← a + b
c ← x
d ← 1
e ← x
if expression is computed more than once, eliminate one computation

20. optimization
Dataflow Analysis
Intraprocedural Global Optimization
Terminology
•Intraprocedural: within a single procedure or function
•Global: spans all statements with procedure
•Interprocedural: operating on several procedures at once
Recipe
•Dataflow analysis: traverse flow graph, gather information
•Transformation: modify program using information from analysis
12

21. Dataflow Analysis
Control-flow Graphs
II
13

22. quadruples
Dataflow Analysis
Intermediate Language
Store
a ← b ⊕ c
a ← b
Memory access
a ← M[b]
M[a] ← b
Functions
f(a1, …, an)
b ← f(a1, …, an)
Jumps
L:
goto L
if a ⊗ b
goto L1
else
goto L2
14

23. example
Dataflow Analysis
Control-Flow Graphs
15
a ← 0
L1: b ← a + 1
c ← c + b
a ← 2 * b
if a < N
goto L1
else
goto L2
L2: return c

24. example
Dataflow Analysis
Control-Flow Graphs
15
a ← 0
b ← a + 1
c ← c + b
a ← 2 * b
if a < N
return c
a ← 0
L1: b ← a + 1
c ← c + b
a ← 2 * b
if a < N
goto L1
else
goto L2
L2: return c

25. terminology
Dataflow Analysis
Control-Flow Graphs
16
a ← 0
b ← a + 1
c ← c + b
a ← 2 * b
if a < N
return c

26. terminology
Dataflow Analysis
Control-Flow Graphs
16
a ← 0
b ← a + 1
c ← c + b
a ← 2 * b
if a < N
return c
node

27. terminology
Dataflow Analysis
Control-Flow Graphs
16
a ← 0
b ← a + 1
c ← c + b
a ← 2 * b
if a < N
return c
node
in-edge

28. terminology
Dataflow Analysis
Control-Flow Graphs
16
a ← 0
b ← a + 1
c ← c + b
a ← 2 * b
if a < N
return c
node
in-edge
in-edge

29. terminology
Dataflow Analysis
Control-Flow Graphs
16
a ← 0
b ← a + 1
c ← c + b
a ← 2 * b
if a < N
return c
node
predecessor
predecessor
in-edge
in-edge

30. terminology
Dataflow Analysis
Control-Flow Graphs
16
a ← 0
b ← a + 1
c ← c + b
a ← 2 * b
if a < N
return c
node
predecessor
predecessor
in-edge
out-edge
in-edge

31. terminology
Dataflow Analysis
Control-Flow Graphs
16
a ← 0
b ← a + 1
c ← c + b
a ← 2 * b
if a < N
return c
node
predecessor
predecessor
successor
in-edge
out-edge
in-edge

32. Dataflow Analysis
Liveness Analysis
III
17

33. definition
Dataflow Analysis
Liveness Analysis
Motivation: register allocation
•intermediate code with unbounded number of temporary variables
•map to bounded number of registers
•if two variables are not ‘live’ at the same time, store in same register
Liveness
•a variable is live if it holds a value that may be needed in the future
18

34. example
Dataflow Analysis
Register Allocation
19
a ← 0
b ← a + 1
c ← c + b
a ← 2 * b
if a < N
return c

35. example
Dataflow Analysis
Register Allocation
19
a ← 0
b ← a + 1
c ← c + b
a ← 2 * b
if a < N
return c
{a, b} ! r
{c} ! q

36. example
Dataflow Analysis
Register Allocation
19
r ← 0
r ← r + 1
q ← q + r
r ← 2 * r
if r < N
return q
a ← 0
b ← a + 1
c ← c + b
a ← 2 * b
if a < N
return c
{a, b} ! r
{c} ! q

37. a ← 0
return c
if a < N
b ← a + 1
a ← 2 * b
c ← c + b
example
Dataflow Analysis
Liveness Analysis
20

38. a ← 0
return c
if a < N
b ← a + 1
a ← 2 * b
c ← c + b
example
Dataflow Analysis
Liveness Analysis
20

39. a ← 0
return c
if a < N
b ← a + 1
a ← 2 * b
c ← c + b
example
Dataflow Analysis
Liveness Analysis
20

40. a ← 0
return c
if a < N
b ← a + 1
a ← 2 * b
c ← c + b
example
Dataflow Analysis
Liveness Analysis
20

41. a ← 0
return c
if a < N
b ← a + 1
a ← 2 * b
c ← c + b
example
Dataflow Analysis
Liveness Analysis
20

42. a ← 0
return c
if a < N
b ← a + 1
a ← 2 * b
c ← c + b
example
Dataflow Analysis
Liveness Analysis
20

43. a ← 0
return c
if a < N
b ← a + 1
a ← 2 * b
c ← c + b
example
Dataflow Analysis
Liveness Analysis
20

44. a ← 0
return c
if a < N
b ← a + 1
a ← 2 * b
c ← c + b
example
Dataflow Analysis
Liveness Analysis
20

45. a ← 0
return c
if a < N
b ← a + 1
a ← 2 * b
c ← c + b
example
Dataflow Analysis
Liveness Analysis
20

46. a ← 0
return c
if a < N
b ← a + 1
a ← 2 * b
c ← c + b
example
Dataflow Analysis
Liveness Analysis
20

47. a ← 0
return c
if a < N
b ← a + 1
a ← 2 * b
c ← c + b
example
Dataflow Analysis
Liveness Analysis
20

48. definitions
Dataflow Analysis
Liveness Analysis
Def and use
•an assignment to a variable defines a variable
•an occurrence of a variable in an expression uses that variable
•def[x] = {n | n defines x}, def[n] = {x | n defines x}
•use[x] = {n | n uses x}, use[n] = {x | n uses x}
A variable is live on an edge if
•there is a directed path from that edge to a use of the variable
•that does not go through any def
A variable is live in/out at a node
•live-in: it is live on any of the in-edges of that node
•live-out: it is live on any of the out-edges of the node
21

49. terminology
Dataflow Analysis
Liveness Analysis
22
a ← 0
b ← a + 1
c ← c + b
a ← 2 * b
if a < N
return c

50. terminology
Dataflow Analysis
Liveness Analysis
22
definition a ← 0
b ← a + 1
c ← c + b
a ← 2 * b
if a < N
return c

51. terminology
Dataflow Analysis
Liveness Analysis
22
usage
definition a ← 0
b ← a + 1
c ← c + b
a ← 2 * b
if a < N
return c

52. terminology
Dataflow Analysis
Liveness Analysis
22
usage
definition
definition
a ← 0
b ← a + 1
c ← c + b
a ← 2 * b
if a < N
return c

53. terminology
Dataflow Analysis
Liveness Analysis
22
usage
definition
usage
definition
a ← 0
b ← a + 1
c ← c + b
a ← 2 * b
if a < N
return c

54. terminology
Dataflow Analysis
Liveness Analysis
22
usage
definition
usage
definition
live-in
a ← 0
b ← a + 1
c ← c + b
a ← 2 * b
if a < N
return c

55. terminology
Dataflow Analysis
Liveness Analysis
22
usage
definition
usage
definition
live-in
live-out
a ← 0
b ← a + 1
c ← c + b
a ← 2 * b
if a < N
return c

56. terminology
Dataflow Analysis
Liveness Analysis
22
usage
definition
usage
definition
live-in
live-in
live-out
a ← 0
b ← a + 1
c ← c + b
a ← 2 * b
if a < N
return c

57. terminology
Dataflow Analysis
Liveness Analysis
22
usage
definition
usage
definition
live-in
live-out
live-in
live-out
a ← 0
b ← a + 1
c ← c + b
a ← 2 * b
if a < N
return c

58. terminology
Dataflow Analysis
Liveness Analysis
22
usage
definition
usage
definition
live-in
live-out
live-out
live-in
live-out
a ← 0
b ← a + 1
c ← c + b
a ← 2 * b
if a < N
return c

59. formalization
Dataflow Analysis
Liveness Analysis
in[n] = use[n] ∪ (out[n] - def[n])
out[n] = ∪s∈succ[n] in[s]
1. If a variable is used at node n, then it is live-in at n
2. If a variable is live-out but not defined at node n, it is live-in at n
3. If a variable is live-in at node n, then it is live-out at its predecessors
23

60. algorithm
Dataflow Analysis
Liveness Analysis
for each n
in[n] ← {} ; out[n] ← {}
repeat
for each n
in'[n] = in[n] ; out'[n] = out[n]
in[n] = use[n] ∪ ( out[n] - def[n])
for each s in succ[n]
out[n] = out[n] ∪ in[s]
until
for all n: in[n] = in'[n] and out[n] = out'[n]
24

61. example
Dataflow Analysis
Liveness Analysis
25
a ← 0
b ← a + 1
c ← c + b
a ← 2 * b
if a < N
return c
1
2
3
4
5
6
1
2
3
4
5
6
u
a
bc
b
a
c

62. example
Dataflow Analysis
Liveness Analysis
25
a ← 0
b ← a + 1
c ← c + b
a ← 2 * b
if a < N
return c
1
2
3
4
5
6
1
2
3
4
5
6
u
a
bc
b
a
c
d
a
b
c
a

63. example
Dataflow Analysis
Liveness Analysis
25
a ← 0
b ← a + 1
c ← c + b
a ← 2 * b
if a < N
return c
1
2
3
4
5
6
1
2
3
4
5
6
u
a
bc
b
a
c
d
a
b
c
a
1
i
a
bc
b
a
c
o
a

64. example
Dataflow Analysis
Liveness Analysis
25
a ← 0
b ← a + 1
c ← c + b
a ← 2 * b
if a < N
return c
1
2
3
4
5
6
1
2
3
4
5
6
u
a
bc
b
a
c
d
a
b
c
a
1
i
a
bc
b
a
c
o
a
2
i
a
bc
b
a
c
o
a
bc
b
a
ac

65. example
Dataflow Analysis
Liveness Analysis
25
a ← 0
b ← a + 1
c ← c + b
a ← 2 * b
if a < N
return c
1
2
3
4
5
6
1
2
3
4
5
6
u
a
bc
b
a
c
d
a
b
c
a
1
i
a
bc
b
a
c
o
a
2
i
a
bc
b
a
c
o
a
bc
b
a
ac
3
i
ac
bc
b
ac
c
o
a
bc
b
a
ac

66. example
Dataflow Analysis
Liveness Analysis
25
a ← 0
b ← a + 1
c ← c + b
a ← 2 * b
if a < N
return c
1
2
3
4
5
6
1
2
3
4
5
6
u
a
bc
b
a
c
d
a
b
c
a
1
i
a
bc
b
a
c
o
a
2
i
a
bc
b
a
c
o
a
bc
b
a
ac
3
i
ac
bc
b
ac
c
o
a
bc
b
a
ac
4
i
ac
bc
b
ac
c
o
ac
bc
b
ac
ac

67. example
Dataflow Analysis
Liveness Analysis
25
a ← 0
b ← a + 1
c ← c + b
a ← 2 * b
if a < N
return c
1
2
3
4
5
6
1
2
3
4
5
6
u
a
bc
b
a
c
d
a
b
c
a
1
i
a
bc
b
a
c
o
a
2
i
a
bc
b
a
c
o
a
bc
b
a
ac
3
i
ac
bc
b
ac
c
o
a
bc
b
a
ac
4
i
ac
bc
b
ac
c
o
ac
bc
b
ac
ac
5
i
c
ac
bc
bc
ac
c
o
ac
bc
b
ac
ac

68. example
Dataflow Analysis
Liveness Analysis
25
a ← 0
b ← a + 1
c ← c + b
a ← 2 * b
if a < N
return c
1
2
3
4
5
6
1
2
3
4
5
6
u
a
bc
b
a
c
d
a
b
c
a
1
i
a
bc
b
a
c
o
a
2
i
a
bc
b
a
c
o
a
bc
b
a
ac
3
i
ac
bc
b
ac
c
o
a
bc
b
a
ac
4
i
ac
bc
b
ac
c
o
ac
bc
b
ac
ac
5
i
c
ac
bc
bc
ac
c
o
ac
bc
b
ac
ac
6
i
c
ac
bc
bc
ac
c
o
ac
bc
bc
ac
ac

69. example
Dataflow Analysis
Liveness Analysis
25
a ← 0
b ← a + 1
c ← c + b
a ← 2 * b
if a < N
return c
1
2
3
4
5
6
1
2
3
4
5
6
u
a
bc
b
a
c
d
a
b
c
a
1
i
a
bc
b
a
c
o
a
2
i
a
bc
b
a
c
o
a
bc
b
a
ac
3
i
ac
bc
b
ac
c
o
a
bc
b
a
ac
4
i
ac
bc
b
ac
c
o
ac
bc
b
ac
ac
5
i
c
ac
bc
bc
ac
c
o
ac
bc
b
ac
ac
6
i
c
ac
bc
bc
ac
c
o
ac
bc
bc
ac
ac
7
i
c
ac
bc
bc
ac
c
o
ac
bc
bc
ac
ac

70. optimization
Dataflow Analysis
Liveness Analysis
26
a ← 0
b ← a + 1
c ← c + b
a ← 2 * b
if a < N
return c
1
2
3
4
5
6
6
5
4
3
2
1
u
c
a
b
bc
a

71. optimization
Dataflow Analysis
Liveness Analysis
26
a ← 0
b ← a + 1
c ← c + b
a ← 2 * b
if a < N
return c
1
2
3
4
5
6
6
5
4
3
2
1
u
c
a
b
bc
a
d
a
c
b
a

72. optimization
Dataflow Analysis
Liveness Analysis
26
a ← 0
b ← a + 1
c ← c + b
a ← 2 * b
if a < N
return c
1
2
3
4
5
6
6
5
4
3
2
1
u
c
a
b
bc
a
d
a
c
b
a
1
o
c
ac
bc
bc
ac
i
c
ac
bc
bc
ac
a

73. optimization
Dataflow Analysis
Liveness Analysis
26
a ← 0
b ← a + 1
c ← c + b
a ← 2 * b
if a < N
return c
1
2
3
4
5
6
6
5
4
3
2
1
u
c
a
b
bc
a
d
a
c
b
a
1
o
c
ac
bc
bc
ac
i
c
ac
bc
bc
ac
a
2
o
ac
ac
bc
bc
ac
i
c
ac
bc
bc
ac
c

74. optimization
Dataflow Analysis
Liveness Analysis
26
a ← 0
b ← a + 1
c ← c + b
a ← 2 * b
if a < N
return c
1
2
3
4
5
6
6
5
4
3
2
1
u
c
a
b
bc
a
d
a
c
b
a
1
o
c
ac
bc
bc
ac
i
c
ac
bc
bc
ac
a
2
o
ac
ac
bc
bc
ac
i
c
ac
bc
bc
ac
c
3
o
ac
ac
bc
bc
ac
i
c
ac
bc
bc
ac
c

75. generalisation
Dataflow Analysis
Liveness Analysis
27
a ← 0
b ← a + 1
c ← c + b
a ← 2 * b
if a < N
return c

76. generalisation
Dataflow Analysis
Liveness Analysis
27
kill a ← 0
b ← a + 1
c ← c + b
a ← 2 * b
if a < N
return c

77. generalisation
Dataflow Analysis
Liveness Analysis
27
gen
kill a ← 0
b ← a + 1
c ← c + b
a ← 2 * b
if a < N
return c

78. generalisation
Dataflow Analysis
Liveness Analysis
27
gen
kill
kill
a ← 0
b ← a + 1
c ← c + b
a ← 2 * b
if a < N
return c

79. generalisation
Dataflow Analysis
Liveness Analysis
27
gen
kill
gen
kill
a ← 0
b ← a + 1
c ← c + b
a ← 2 * b
if a < N
return c

80. generalisation
Dataflow Analysis
Liveness Analysis
27
gen
kill
gen
kill
in
a ← 0
b ← a + 1
c ← c + b
a ← 2 * b
if a < N
return c

81. generalisation
Dataflow Analysis
Liveness Analysis
27
gen
kill
gen
kill
in
out
a ← 0
b ← a + 1
c ← c + b
a ← 2 * b
if a < N
return c

82. generalisation
Dataflow Analysis
Liveness Analysis
27
gen
kill
gen
kill
in
out
out
a ← 0
b ← a + 1
c ← c + b
a ← 2 * b
if a < N
return c

83. generalisation
Dataflow Analysis
Liveness Analysis
27
gen
kill
gen
kill
in
out
out
in
a ← 0
b ← a + 1
c ← c + b
a ← 2 * b
if a < N
return c

84. generalisation
Dataflow Analysis
Liveness Analysis
27
gen
kill
gen
kill
in
out
out
in
out
a ← 0
b ← a + 1
c ← c + b
a ← 2 * b
if a < N
return c

85. gen & kill
Dataflow Analysis
Liveness Analysis
28
a ← b ⊕ c
a ← b
a ← M[b]
M[a] ← b
f(a1, …, an)
a ← f(a1, …, an)
goto L
if a ⊗ b
gen
{b,c}
{b}
{b}
{a,b}
{a1,…,an}
{a1,…,an}
{a,b}

86. gen & kill
Dataflow Analysis
Liveness Analysis
28
a ← b ⊕ c
a ← b
a ← M[b]
M[a] ← b
f(a1, …, an)
a ← f(a1, …, an)
goto L
if a ⊗ b
gen
{b,c}
{b}
{b}
{a,b}
{a1,…,an}
{a1,…,an}
{a,b}
kill
{a}
{a}
{a}
{a}

87. generalisation
Dataflow Analysis
Liveness Analysis
in[n] = gen[n] ∪ (out[n] - kill[n])
out[n] = ∪s∈succ[n] in[s]
29

88. Dataflow Analysis
More Analyses
IV
30

89. definition
Dataflow Analysis
Reaching Definitions
Unambiguous definition of a
•a statement of the form (d : a ← b ⊕ c) or (d : a ← M[x])
Definition d reaches statement u if
•there is some path in control-flow graph from d to u
•that does not contain an unambiguous definition of a
Used in
•constant propagation
31

90. example
Dataflow Analysis
Reaching Definitions
32
a ← 5
c ← 1
if c > a
c ← c + c
goto 3
a ← c - a
1
2
3
4
5
6

91. gen & kill
Dataflow Analysis
Reaching Definitions
33
d: a ← b ⊕ c
d: a ← b
d: a ← M[b]
M[a] ← b
f(a1, …, an)
d: a ← f(a1, …, an)
goto L
if a ⊗ b
gen
{d}
{d}
{d}
{d}
defs(a) : all definitions of a

92. gen & kill
Dataflow Analysis
Reaching Definitions
33
d: a ← b ⊕ c
d: a ← b
d: a ← M[b]
M[a] ← b
f(a1, …, an)
d: a ← f(a1, …, an)
goto L
if a ⊗ b
gen
{d}
{d}
{d}
{d}
kill
defs(a)-{d}
defs(a)-{d}
defs(a)-{d}
defs(a)-{d}
defs(a) : all definitions of a

93. formalisation
Dataflow Analysis
Reaching Definitions
in[n] = ∪p∈pred[n] out[p]
out[n] = gen[n] ∪ (in[n] - kill[n])
34

94. definition
Dataflow Analysis
Available Expressions
An expression (b ⊕ c) is available at node n if
•on every path from the entry node to node n
•(b ⊕ c) is computed at least once, and
•there are no definitions of b or c since most recent occurrence 

of (b ⊕ c) on that path
Used in
•common-subexpression elimination
35

95. example
Dataflow Analysis
Available Expressions
36
c ← a + b
d ← 1
e ← a + b
1
2
3

96. gen & kill
Dataflow Analysis
Available Expressions
37
d: a ← b ⊕ c
d: a ← b
d: a ← M[b]
M[a] ← b
f(a1, …, an)
d: a ← f(a1, …, an)
goto L
if a ⊗ b
gen
{b⊕c}-kill
{M[b]}-kill

97. gen & kill
Dataflow Analysis
Available Expressions
37
d: a ← b ⊕ c
d: a ← b
d: a ← M[b]
M[a] ← b
f(a1, …, an)
d: a ← f(a1, …, an)
goto L
if a ⊗ b
gen
{b⊕c}-kill
{M[b]}-kill
kill
exps(a)
exps(a)
exps(M[_])
exps(M[_])
exps(M[_]) ∪ exps(a)

98. formalisation
Dataflow Analysis
Available Expressions
in[n] = ∩p∈pred[n] out[p]
out[n] = gen[n] ∪ (in[n] - kill[n])
38

99. definition
Dataflow Analysis
Reaching Expressions
An expression (s : a ← b ⊕ c) reaches node n if
•there is a path from s to n
•that does not go through assignment to b or c
•or through any computation of (b ⊕ c)
Used in
•common-subexpression elimination
39

100. Dataflow Analysis
Optimizations
V
40

101. example
Dataflow Analysis
Dead Code Elimination
41
a ← 0
b ← a + 1
c ← c + b
return c
a ← 0
b ← a + 1
c ← c + b
a ← 2 * b
return c
consider:
(s : a ← b ⊕ c) or (s : a ← M[x])
if a is not live-out at s
transform:
remove s

102. example
Dataflow Analysis
Common Subexpression Elimination
42
c ← a + b
d ← 1
e ← a + b
x ← a + b
c ← x
d ← 1
e ← x
consider:
(n : a ← b ⊕ c) reaches (s : d ← b ⊕ c)
path from n to s does not compute b ⊕ c or define b or c
e is a fresh variable
transform:
n : a ← b ⊕ c
n’ : e ← a
…
s : d ← e

103. example
Dataflow Analysis
Constant Propagation
43
a ← 0
b ← 0 + 1
c ← c + b
a ← 2 * b
return c
a ← 0
b ← a + 1
c ← c + b
a ← 2 * b
return c
consider: (d : a ← c) & (n : e ← a ⊕ b)
if c is constant
& (d reaches n)
& (no other def of a reaches n )
transform:
(n : e ← a ⊕ b) => (n : e ← c ⊕ b)

104. example
Dataflow Analysis
Copy Propagation
44
a ← e
b ← e + 1
c ← c + b
a ← 2 * b
return c
a ← e
b ← a + 1
c ← c + b
a ← 2 * b
return c
consider: (d : a ← z) & (n : e ← a ⊕ b)
if z is a variable
& (d reaches n)
& (no other def of a reaches n )
& (no def of z on path from d to n)
transform:
(n : e ← a ⊕ b) => (n : e ← z ⊕ b)

105. Term Rewriting
Summary
V
45

106. Dataflow Analysis
Summary
Liveness analysis
•intermediate language
•control-flow graphs
•definition & algorithm
More dataflow analyses
•reaching definitions
•available expressions
Optimizations
46

107. learn more
Dataflow Analysis
Literature
Andrew W. Appel, Jens Palsberg: Modern Compiler Implementation in
Java, 2nd edition. 2002
47

108. Dataflow Analysis
Copyrights & Credits
48

109. Dataflow Analysis49

110. copyrights
Dataflow Analysis
Pictures
Slide 1:
ink swirl by Graham Richardson, some rights reserved
Slide 25:
Seattle's Best Coffee by Dominica Williamson, some rights reserved
Slide 32:
Animal Ark Reno by Joel Riley, some rights reserved
50