1CS553 Lecture Midterm Review 2Midterm Review Today– Overview of what we have learned so far– Lattice terminology review– Dominance frontier example– Pessimistic global value numbering– Induction variable identification– PRE exampleCS553 Lecture Midterm Review 3Big 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 4Structure of a Typical Compiler“sentences”Synthesisoptimizationcode generationtarget languageIRIR code generationIRAnalysischaracter streamlexical analysis“words”tokenssemantic analysissyntactic analysisASTannotated ASTinterpreterCS553 Lecture Midterm Review 5Topics I. The Basics– Scanning and parsing– bison and flex as parser generation and lexical analysis generation tools– Dataflow analysis– Examples: reaching definitions, liveness, reaching constants, ...– Theoretic framework built on lattices– 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 variable elimination, strength reduction, global value numbering– Aliases– what induces aliases?– what is the difference between alias pairs and the points-to representation?– how do we characterize alias analysis algorithms?3CS553 Lecture Midterm Review 6 2S = {{v1,v2,v3}, {v1,v2},{v1,v3},{v2,v3}, {v1},{v2},{v3}, ∅} ∪ ⊇ ∅ V {fn(X) = Genn ∪ (X – Killn), ∀n}Example: Liveness analysis with 3 variablesS = {v1, v2, v3}∅ = T{ v1 } { v2 }{ v3 }{ v1,v2 } { v1,v3 }{ v2,v3 }{ v1,v2,v3 } = ⊥– V:– Meet (⊓):– ⊑:– Top(T):– Bottom (⊥):– F:Inferior solutions are lower on the latticeMore conservative solutions are lower on the latticeVisualizing DFA Frameworks as LatticesCS553 Lecture Midterm Review 7Nodes in Dom(5) {4, 5, 12, 13}5Dominance Frontier Example23 6 7891110DF(d) = {n | ∃p∈pred(n), d dom p and d !sdom n}Dom(5) = {5, 6, 7, 8}541312What’s significant about the Dominance Frontier?1In SSA form, definitions must dominate usesDF(5) =4CS553 Lecture Midterm Review 8Pessimistic Global Value Numbering Idea– Initially each variable is in its own congruence class– Consider each assignment statement s (reverse postorder in CFG)– Update LHS value number with hash of RHS– Identical value number ⇒ congruence x #1 x+ 1 #2 i #2 k #2 i*2 *(#2,2) #3 d #3 k*2 *(#2,2) #3 y #3CS553 Lecture Midterm Review 9Induction Variable Identification s = ... j = 0 z = ... d = ... loop: s = s + j d = z + j j = j + 1 if (j<=10) goto loop Derived: function of a basic as well as a loop invariant or itself Results: j is a basic induction variable, d and s are derived5CS553 Lecture Midterm Review 12Global Possible Placement Flow Functionsppout[n] = ∩ s∈succ[n] ppin[s]ppin[n] = anticipated_in[n] ∩ partially_available_in[n] ∩ (locally_anticipated[n] ∪ (ppout[n] ∩ transparent[n]))The placement will create a redundancyWill turn partial redundancy into full redundancyMiddle of chainThis block is at thebeginning of a chainon every edge out of the blockCS553 Lecture Midterm Review 13Updating Blocks Intuition– Perform insertions at top of the chain– Perform deletion at the bottom of the chain Functions– delete[n] = ppin[n] ∩ locally_anticipated[n]– insert[n] = ppout[n] ∩ (¬ppin[n] ∪ ¬ transparent[n]) ∩ ¬available_out[n]Don’t insert it where it’s fully redundant6CS553 Lecture Midterm Review 14Performing Insertions and Deletions Overview– find each delete expression and replace it with a temporary variable, keeptrack of expression mapped to variable– find each statement (x = expr) where expr is an insert expression– insert tempvar = x after the found statement OR– find each delete expression and replace it with a temporary variable, keeptrack of expression mapped to variable– for each delete block, put (tempvar = expr) before first computation of theexpression (have to be careful it really is the same expression)– find each statement (x = expr) where expr is the insert expression andreplace it with (x =
View Full Document
Unlocking...