Program Analysis Data Flow Analysis
Program Analysis Data Flow Analysis
Outline 工. Program Analysis II.Data Flow Analysis Available Expressions Liveness Analysis Reaching Definitions Very Busy Expressions rrr.Theory Behind IV.Sensitivity v.Summary A
4 Outline I. Program Analysis II. Data Flow Analysis ✓ Available Expressions ✓ Liveness Analysis ✓ Reaching Definitions ✓ Very Busy Expressions III.Theory Behind IV. Sensitivity V. Summary
Program Analysis In computer science,program analysis is the process of automatically analyzing the behavior of computer programs. Two main approaches in program analysis are static program analysis and dynamic program analysis Main applications of program analysis are program correctness (including security)and program optimization. 5
Program Analysis • In computer science, program analysis is the process of automatically analyzing the behavior of computer programs. • Two main approaches in program analysis are static program analysis and dynamic program analysis • Main applications of program analysis are program correctness (including security) and program optimization. 5
Basic Technigues D Techniques related to program analysis include control-flow and data-flow analysis constraint-based analysis abstract interpretation type and effect systems D A technique that is applied for certain kinds of program analysis is program slicing. Related fields include performance analysis and program verification. 6
Basic Techniques Techniques related to program analysis include ✓ control-flow and data-flow analysis ✓ constraint-based analysis ✓ abstract interpretation ✓ type and effect systems A technique that is applied for certain kinds of program analysis is program slicing. Related fields include performance analysis and program verification. 6
Data Flow Analysis Definition: Data-flow analysis is a technique for gathering information about the possible set of values calculated at various points in a computer program. A program's control flow graph(CFG)is used to determine those parts of a program to which a particular value assigned to a variable might propagate. The information gathered is often used by compilers when optimizing a program.A canonical example of a data-flow analysis is reaching definitions
Data Flow Analysis Definition: Data-flow analysis is a technique for gathering information about the possible set of values calculated at various points in a computer program. A program’s control flow graph (CFG) is used to determine those parts of a program to which a particular value assigned to a variable might propagate. The information gathered is often used by compilers when optimizing a program. A canonical example of a data-flow analysis is reaching definitions. 7
Data Flow Analysis Data-flow analysis derives information about the dynamic behavior of a program by only examining the static code Example How many registers do we need for the program on the right Easy bound:the number of variables used a:=0 Better answer is found by 2 L1:b:= :a+1 considering the dynamic 3 :=C+b requirements of the program. 4 a:=b*2 5 if a <9 goto Ll return c 8
Data Flow Analysis • Data-flow analysis derives information about the dynamic behavior of a program by only examining the static code • Example – How many registers do we need for the program on the right ? – Easy bound: the number of variables used ? – Better answer is found by considering the dynamic requirements of the program. 8
Basic Techniques Basic Approaches A simple way to perform data-flow analysis of programs is to set up data-flow equations for each node of the control flow graph and solve them by repeatedly calculating the output from the input locally at each node until the whole system stabilizes,i.e.,it reaches a fixpoint. The above general approach was developed by Gary Kildall while teaching at the Naval Postgraduate School 9
Basic Techniques Basic Approaches A simple way to perform data-flow analysis of programs is to set up data-flow equations for each node of the control flow graph and solve them by repeatedly calculating the output from the input locally at each node until the whole system stabilizes, i.e., it reaches a fixpoint. The above general approach was developed by Gary Kildall while teaching at the Naval Postgraduate School 9
Control Flow Graphs (CFGs) ·Simplification For now,we will use CFG's in which nodes represent program statements rather than basic blocks Example a=0 1 a:=0 2b=a+1 2 L1:b:= a+1 Y 3 c= c+b 3 c :=c+b V 4 a:=b*2 4a=b*2 5 if a <9 goto Ll 7 5 a<9 6 return c No Yes 6 return c 10
Control Flow Graphs (CFGs) • Simplification – For now, we will use CFG’s in which nodes represent program statements rather than basic blocks 10
At Different Program Points At Different Program Points Which assignment statements produced value of variable at this point? Which variables contain values that are no longer used after this program point? What is the range of possible values of variable at this program point? 11
At Different Program Points • At Different Program Points ➢ Which assignment statements produced value of variable at this point? ➢ Which variables contain values that are no longer used after this program point? ➢ What is the range of possible values of variable at this program point? ➢ …… 11
Program Points >One program point before each node ENTRY >One program point after each node B 1=1 >Join point-point with multiple predecessors B2 j=1 >Split point-point with multiple successors 七1=10*1 七2■ ti+j t3■8*七2 t4=t3 -88 j=j+1 if j<=10 goto Ba B4 1=1+1 1f1<=10got0B2 Bs 1=1 t5■1-1 =88*七5 a[t6]=1.0 1=i+1 if i <10 goto Be EXIT 12
Program Points 12