1CS553 Lecture Midterm Review 1Final Review Today– Overview of what we have learned so far– data-flow analysis review– pointer and alias analysis– interprocedural analysis– register allocation– loop skewing Studying– make sure to review terminology– (i.e. what does flow-sensitive mean?)CS553 Lecture Midterm Review 2Big Picture: Traditional View of Compilers Compiling down– Translate high-level language to machine code High-level programming languages– Increase programmer productivity– Improve program maintenance– Improve portability Low-level architectural details– Instruction set– Addressing modes– Pipelines– Registers, cache, and the rest of the memory hierarchy– Instruction-level parallelism2CS553 Lecture Midterm Review 3Structure of a Typical Compiler“sentences”Synthesisoptimizationcode generationtarget languageIRIR code generationIRAnalysischaracter streamlexical analysis“words”tokenssemantic analysissyntactic analysisASTannotated ASTinterpreterCS553 Lecture Midterm Review 4Topics I. The Basics– Scanning and parsing– Dataflow analysis (review the projects, especially project 2)– Theoretic framework built on lattices– How might we improve the performance of iterative data-flow analysis byusing a worklist-based algorithm?– Control flow analysis: control-flow graphs, dominators, dominance frontiers,irreducibility II. Analyses and Representations– SSA Form: types of data dependencies, how to translate to minimal SSA– Program optimizations– dead-code elimination, constant propagation (simple constants), CSE, loop-invariant code motion, PRE, copy propagation, induction variableelimination, strength reduction, global value numbering– Aliases– how do data-flow analysis algorithms use aliasing information?– how do we characterize alias analysis algorithms?– Interprocedural Analysis– how do different levels of context information affect analysis results?3CS553 Lecture Midterm Review 5Topics (cont) III. Low-Level Optimizations– Register allocation– difference between Briggs and Chaitin– heuristics to determine spilling will be provided– Instruction scheduling– list scheduling– Profile-guided and dynamic optimizations– what types of profiling information can we collect and how is ituseful?– when are dynamic optimizations (or run-time reorderingtransformations) profitable?– Predication and speculation– what HW features do these techniques attempt to deal with?CS553 Lecture Midterm Review 6Topics (cont) IV. High-Level Optimizations– Dependence analysis– is this problem decidable? can we formulate it as decidable?– Loop transformations– unimodular transformation framework– generating a schedule based on schedule constraints– Tiling– what is it used for?– Object-oriented optimizations– how does the compiler handle dynamic binding?4CS553 Lecture Midterm Review 7Topics (cont) V. Emerging Topics– Garbage collection– pros and cons between explicit and implicit garbage collection– reference counting, mark and sweep, generational collection, etc.– Run-time reordering transformations– data reordering improves ?? locality– iteration reordering improves ?? locality– Security and program checking– four different overall strategiesCS553 Lecture Midterm Review 8 out[n] = ∪ in[s] in[n] = gen[n] ∪ (out[n] – kill[n]) in[n] = ∪ out[s] out[n] = gen[n] ∪ (in[n] – kill[n])=xnentryIs x def’d alongthis path?Use of xLive VariablesReaching Definitionsx= nentryDef of xIs x def’d alongthis path? Symmetry between reaching definitions and liveness– Swap in[] and out[] and swap the directions of the arcss ∈ succ[n]Data-flow Equations for Reaching Definitionsp ∈ pred[n]5CS553 Lecture Midterm Review 9Reality Check! Some definitions and uses are ambiguous– We can’t tell whether or what variable is involvede.g., *p = x; /* what variable are we assigning?! */– Unambiguous assignments are called strong updates– Ambiguous assignments are called weak updates Solutions– Be conservative– Sometimes we assume that it could be everythinge.g., Defining *p (generating reaching definitions)– Sometimes we assume that it is nothinge.g., Defining *p (killing reaching definitions)– Try to figure it out: alias/pointer analysis (more later)CS553 Lecture Midterm Review 10Using Alias Information Example: reaching definitions– Compute at each point in the program a set of (s,v) pairs, indicating thatstatement s may define variable v Flow functions– s: *p = x;outreach[s] = {(s,z) | (p→z) ∈ inmay-pt[s]} ∪(inreach[s] – {(t,y) ∀t | (p→y) ∈ inmust-pt[s]}– s: x = *p;outreach[s] = {(s,x)} ∪ (inreach[s] – {(t,x) ∀t}– . . .6CS553 Lecture Midterm Review 11 Track information that flows into a procedure– Sometimes known as propagation problemse.g., What formals are constant?e.g., Which formals are aliased to globals? Track information that flows out of a procedure– Sometimes known as side effect problemse.g., Which globals are def’d/used by a procedure?e.g., Which locals are def’d/used by a procedure?e.g., Which actual parameters are def’d by a procedure?Interprocedural Analysis: Two Types of Information proc (x,y) { . . . } CS553 Lecture Midterm Review 12Examples Propagation Summaries– MAY-ALIAS: The set of formals that may be aliased to globals and eachother– MUST-ALIAS: The set of formals that are definitely aliased to globalsand each other– CONSTANT: The set of formals that must be constant Side-effect Summaries– MOD: The set of variables possibly modified (defined) by a call to aprocedure– REF: The set of variables possibly read (used) by a call to a procedure– KILL: The set of variables that are definitely killed by a procedure (e.g.,in the liveness sense)7CS553 Lecture Midterm Review 13Computing Interprocedural Summaries Top-down– Summarize information about the caller (MAY-ALIAS, MUST-ALIAS)– Use this information inside the procedure body int a; void foo(int &b, &c){ . . . } foo(a,a); Bottom-up– Summarize the effects of a call (MOD, REF, KILL)– Use this information around procedure calls x = 7; foo(x); y = x + 3;CS553 Lecture Midterm Review 14Side-Effect Analysismain() { int *a,*b,c,d; a = &c; b = &d; foo(&a,&a); foo(&b,&a);}void foo(int** x, int **y){ *x = *y; **x = 3;}8CS553 Lecture Midterm Review 15Register Allocation: Spilling If we can’t find a k-coloring of the interference