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 AnalysisRead More

Offer running on EduRev: __Apply code STAYHOME200__ to get INR 200 off on our premium plan EduRev Infinity!