Control Flow Analysis - Part 1 Notes | EduRev

: Control Flow Analysis - Part 1 Notes | EduRev

 Page 1


Control Flow Analysis - Part 1
Y .N. Srikant
Department of Computer Science
Indian Institute of Science
Bangalore 560 012
NPTEL Course on Compiler Design
Y .N. Srikant Control Flow Analysis
Page 2


Control Flow Analysis - Part 1
Y .N. Srikant
Department of Computer Science
Indian Institute of Science
Bangalore 560 012
NPTEL Course on Compiler Design
Y .N. Srikant Control Flow Analysis
Outline of the Lecture
Why control ?ow analysis?
Dominators and natural loops
Intervals and reducibility
T
1
T
2
transformations and graph reduction
Regions
Y .N. Srikant Control Flow Analysis
Page 3


Control Flow Analysis - Part 1
Y .N. Srikant
Department of Computer Science
Indian Institute of Science
Bangalore 560 012
NPTEL Course on Compiler Design
Y .N. Srikant Control Flow Analysis
Outline of the Lecture
Why control ?ow analysis?
Dominators and natural loops
Intervals and reducibility
T
1
T
2
transformations and graph reduction
Regions
Y .N. Srikant Control Flow Analysis
Why Control-Flow Analysis?
Control-?ow analysis (CFA) helps us to understand the
structure of control-?ow graphs (CFG)
To determine the loop structure of CFGs
Formulation of conditions for code motion use dominator
information, which is obtained by CFA
Construction of the static single assignment form (SSA)
requires dominance frontier information from CFA
It is possible to use interval structure obtained from CFA to
carry out data-?ow analysis
Finding Control dependence, which is needed in
parallelization, requires CFA
Y .N. Srikant Control Flow Analysis
Page 4


Control Flow Analysis - Part 1
Y .N. Srikant
Department of Computer Science
Indian Institute of Science
Bangalore 560 012
NPTEL Course on Compiler Design
Y .N. Srikant Control Flow Analysis
Outline of the Lecture
Why control ?ow analysis?
Dominators and natural loops
Intervals and reducibility
T
1
T
2
transformations and graph reduction
Regions
Y .N. Srikant Control Flow Analysis
Why Control-Flow Analysis?
Control-?ow analysis (CFA) helps us to understand the
structure of control-?ow graphs (CFG)
To determine the loop structure of CFGs
Formulation of conditions for code motion use dominator
information, which is obtained by CFA
Construction of the static single assignment form (SSA)
requires dominance frontier information from CFA
It is possible to use interval structure obtained from CFA to
carry out data-?ow analysis
Finding Control dependence, which is needed in
parallelization, requires CFA
Y .N. Srikant Control Flow Analysis
Dominators
We say that a node d in a ?ow graph dominates node n,
written d dom n, if every path from the initial node of the
?ow graph to n goes through d
Initial node is the root, and each node dominates only its
descendents in the tree (including itself)
The node x strictly dominates y, if x dominates y and
x6= y
x is the immediate dominator of y (denoted idom(y)), if x
is the closest strict dominator of y
A dominator tree shows all the immediate dominator
relationships
Principle of the dominator algorithm
If p
1
;p
2
; :::;p
k
, are all the predecessors of n, and d6= n,
then d dom n, iff d dom p
i
for each i
Y .N. Srikant Control Flow Analysis
Page 5


Control Flow Analysis - Part 1
Y .N. Srikant
Department of Computer Science
Indian Institute of Science
Bangalore 560 012
NPTEL Course on Compiler Design
Y .N. Srikant Control Flow Analysis
Outline of the Lecture
Why control ?ow analysis?
Dominators and natural loops
Intervals and reducibility
T
1
T
2
transformations and graph reduction
Regions
Y .N. Srikant Control Flow Analysis
Why Control-Flow Analysis?
Control-?ow analysis (CFA) helps us to understand the
structure of control-?ow graphs (CFG)
To determine the loop structure of CFGs
Formulation of conditions for code motion use dominator
information, which is obtained by CFA
Construction of the static single assignment form (SSA)
requires dominance frontier information from CFA
It is possible to use interval structure obtained from CFA to
carry out data-?ow analysis
Finding Control dependence, which is needed in
parallelization, requires CFA
Y .N. Srikant Control Flow Analysis
Dominators
We say that a node d in a ?ow graph dominates node n,
written d dom n, if every path from the initial node of the
?ow graph to n goes through d
Initial node is the root, and each node dominates only its
descendents in the tree (including itself)
The node x strictly dominates y, if x dominates y and
x6= y
x is the immediate dominator of y (denoted idom(y)), if x
is the closest strict dominator of y
A dominator tree shows all the immediate dominator
relationships
Principle of the dominator algorithm
If p
1
;p
2
; :::;p
k
, are all the predecessors of n, and d6= n,
then d dom n, iff d dom p
i
for each i
Y .N. Srikant Control Flow Analysis
An Algorithm for ?nding Dominators
D(n) = OUT[n] for all n in N (the set of nodes in the ?ow
graph), after the following algorithm terminates
{ /* n
0
= initial node; N = set of all nodes; */
OUT[n
0
] =fn
0
g;
for n in Nfn
0
g do OUT[n] = N;
while (changes to any OUT[n] or IN[n] occur) do
for n in Nfn
0
g do
IN[n] =
\
P a predecessor of n
OUT[P];
OUT[n] = fng[IN[n]
}
Y .N. Srikant Control Flow Analysis
Read More
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!