1Mary Jean Harrold Aristotle Research GroupSPARC/CERCSCollege of ComputingGeorgia TechCS 6340Software Analysis and Testing 2Class 1y Introductions; Student Informationy Details (syllabus, etc.)y Shown on T-Square (https://t-square.gatech.edu)y Basic Analyses (1): intermediate representations, control-flow analysis, y Assigny Basic Analyses (1): Be familiar with conceptsy Representation and Analysis of Software (Sections 1-5) (Schedule has link)y Problem Set 1 (Schedule has link): due 8/25/093Course Overview, Syllabusy Motivation for studying program analysis and testingy Course objectivesy Learn traditional, promising analysesy Learn traditional, new applicationsy Explore research areas in analysis, use of artifactsy Apply analyses and applications through homework, semester projecty Means for approaching course objectivesy Class lectures, readings, homework, class presentationsy Semester project (proposal, oral, written report)y Exams4Course Overview, Syllabusy Your responsibilitiesy Arrive on time, attend all classesy Prepare (read papers before class), participate in classy Submit homework, projects, etc. at the beginning of class on thedue datey Course evaluationy Homework: 30%y Semester project (proposal, written, oral): 30%y Exams: 30%y Class participation: 10%y Prerequisitesy CS 4240, graduate-level standing, permission of instructor5Overview of Coursey Static analyses (computed without execution)y Intraprocedural (within a single procedure)y AST, control-flow, control-dependence, data-flow, etc.y Complicating factorsy Interprocedural (across procedure boundaries), recursiony Pointers, references, polymorphism, dynamic binding, etc.y Slicing, analysis by reachability, demand analysisy Applicationsy Dynamic analyses (computed by execution)y Instrumentation, profilingy Dynamic versions of control-flow, etc.y Applications such as testing, debugging,y Combinations of static and dynamic analyses6Overview of Coursey Static analyses (computed without execution)y Intraprocedural (within a single procedure)y AST, control-flow, control-dependence, data-flow, etc.y Complicating factorsy Interprocedural (across procedure boundaries), recursiony Pointers, references, polymorphism, dynamic binding, etc.y Slicing, analysis by reachability, demand analysisy Applicationsy Dynamic analyses (computed by execution)y Instrumentation, profilingy Dynamic versions of control-flow, etc.y Applications such as testing, debugging,y Combinations of static and dynamic analyses7Intermediate Representations9Intermediate Representations (traditional)LexicalanalyzerSource program(stream of char.)Code generation,optimizationTarget codeTokensParserIntermediaterepresentation10Intermediate Representations (traditional)LexicalanalyzerSource program(stream of char.)Code generation,optimizationTarget codeTokensParserIntermediaterepresentationIntermediaterepresentation• Syntax tree, other lower-levelintermediate language• Little information on what theprogram doesÎ Further analysis—e.g.,• Control-flow analysis: flow ofcontrol within procedures• Data-flow analysis: globalinformation on data manipulation• Use for optimization and software engineering tasks11Intermediate Representations (traditional)LexicalanalyzerSource program(stream of char.)Code generation,optimizationTarget codeTokensParserIntermediaterepresentationWhere does Java Bytecodefit in this process?12Abstract Syntax Tree (AST)y Concrete versus abstract syntaxy Concrete shows structure and is language-specificy Abstract shows structurey Representationsy Parse tree represents concrete syntaxy Abstract syntax tree represents abstract syntax13Example: GrammarExamples1. a := b + c 2. a = b + c; Grammar for 1y stmtlist Æ stmt | stmt stmtlisty stmt Æ assign | if-then | …y assign Æ ident “:=“ ident binop identy binop Æ “+” | “-” | …Grammar for 2y stmtlist Æ stmt “;” | stmt”;” stmtlisty stmt Æ assign | if-then | …y assign Æ ident “=“ ident binop identy binop Æ “+” | “-” | …14Example: Parse tree and AST• Example: a := b + c;• Grammar• stmtlist -> stmt “;” | stmt “;” stmtliststmt -> assign | if-then | …assign -> ident “:=” ident binop identbinop -> “+”| “-”…stmtstmtlistidentassignaident“:=“ binopcbident“+”“;”Parse treeassignaaddbcAST15Three Address Codey General form: x := y op zy May include temporary variables (intermediate values)y Types (examples; rest in handout)y Assignmenty Binary x := y op z y Unary x := op yy Copy x := y y Jumps y Unconditional goto L y Conditional if x relop y goto Ly …16Example: Three Address CodeSource codeif a > 10 thenx = y + zelse x = y – z…Corresponding 3-address codey if a > 10 goto 4y x = y – zy goto 5y x = y + zy …17Analysis Levelsy Local: within a single basic block or statementy Global, Intraprocedural: within a single procedure, function, or method (sometimes, intramethod)y Interprocedural: across procedure boundaries, procedure call, shared globals, etc.y Intraclass: within a single classy Interclass: across class boundariesy Intramodule: within a single moduley …18Control-flow Analysis19Computing Control FlowProcedure AVGS1 count = 0S2 fread(fptr, n)S3 while (not EOF) doS4 if (n < 0)S5 return (error)elseS6 nums[count] = nS7 count ++endifS8 fread(fptr, n)endwhileS9 avg = mean(nums,count)S10 return(avg)20Computing Control FlowProcedure AVGS1 count = 0S2 fread(fptr, n)S3 while (not EOF) doS4 if (n < 0)S5 return (error)elseS6 nums[count] = nS7 count ++endifS8 fread(fptr, n)endwhileS9 avg = mean(nums,count)S10 return(avg)Control flow is a relation (i.e., set of ordered pairs) y that represents the possible flow of execution in a programy (a, b) in the relation means that control can flow from node a to node b during execution.21Computing Control FlowProcedure AVGS1 count = 0S2 fread(fptr, n)S3 while (not EOF) doS4 if (n < 0)S5 return (error)elseS6 nums[count] = nS7 count ++endifS8 fread(fptr, n)endwhileS9 avg = mean(nums,count)S10 return(avg)Control flow is a relation (i.e., set of ordered pairs) y that represents the possible flow of execution in a programy (a, b) in the relation means that control can flow from node a to node b during execution.What is the control-flow relation for Procedure AVG?22Computing Control FlowProcedure AVGS1 count = 0S2