Dataflow Analysis for Available Expressions in Compiler Construction
Utilizing dataflow analysis techniques, the concept of available expressions is discussed in the context of compiler construction. The goal is to identify common subexpressions that span basic blocks by calculating their availability at the beginning of each block. The process involves determining when expressions are already available, avoiding redundant re-evaluation, and understanding the definitions, kills, and availability of expressions within the flowgraph.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
CSE P501 Compiler Construction Available Expressions Dataflow Analysis Aliasing Spring 2014 Jim Hogg - UW - CSE - P501 R-1
The Story So Far Redundant expression elimination Local Value Numbering (LVN) Super-local Value Numbering (SVN) Extends LVN to EBBs SSA-like namespace Dominator Value Numbering (DVN) All of these propagate along forward edges None are global In particular, none can handle back edges and loops Spring 2014 Jim Hogg - UW - CSE - P501 R-2
Dominator Value Numbering A m0 = a0 + b0 n0 = a0 + b0 B C p0 = c0 + d0 r0 = c0 + d0 q0 = a0 + b0 r1 = c0 + d0 D E e0 = b0 + 18 s0 = a0 + b0 u0 = e0 + f0 e1 = a0 + 17 t0 = c0 + d0 u1 = e1 + f0 Most sophisticated algorithm so far Still misses some opportunities Can t handle loops F e2 = (e0,e1) u2 = (u0,u1) v0 = a0 + b0 w0 = c0 + d0 x0 = e2 + f0 G r2 = (r0,r1) y0 = a0 + b0 z0 = c0 + d0 Missed opportunities Spring 2014 Jim Hogg - UW - CSE - P501 R-3
Available Expressions Goal: use dataflow analysis to find CSEs that span basic blocks Idea: calculate available expressions at beginning of each block (rather than just the Value-Numbers for variables) Having found an expression that is already available, there's no need to re-evaluate it: use a copy instead Spring 2014 Jim Hogg - UW - CSE - P501 R-4
Available Expressions: It's Simple! a=b+c d=e+f f=a+c b+c is available here g=a+d h=b+c g=a+c b+c was calculated earlier neither b nor c has been assigned-to since so replace h=b+c with h=a j=a+b+c+d No Value Numbers (super-scripts) ie: trying to work out whether two variables hold same value No SSA Numbers (sub-scripts) ie: recording the life or instantiation of each variable Spring 2014 Jim Hogg - UW - CSE - P501 R-5
Available and Other Terms An expression e is defined at point p in the flowgraph if its value is computed at p Sometimes called definition site, or simply "def" eg: x = a+b ; expression a+b is defined here An expression e is killed at point p if one of its operands is defined at p Sometimes called kill site, or simply "kill" eg: x = a+b ; def site b = 7 ; kill site ; kills every expression involving b ! An expression e is available at point p if every path leading to p contains a prior definition of e and e is not killed between that definition and p Simply: an available expression is one you don't need to re-calculate Spring 2014 Jim Hogg - UW - CSE - P501 R-6
Available Expressions - Intuition =a+b =a+b =a+b =a+b =a+b a= a+b? a+b? a+b? a+b? a+b must reach a+b? So, every path from start to a+b? must include a def for a+b. Any assignment to a or b kills that available expression, throughout the procedure! Spring 2014 Jim Hogg - UW - CSE - P501 R-7
Available Expressions: Flowgraph a=b+c d=e+f f=a+c g=a+d h=b+c g=a+c j=a+b Spring 2014 Jim Hogg - UW - CSE - P501 R-8
Number the Expressions a=b+c 1 d=e+f 2 f=a+c 3 g=a+d 5 h=b+c 6 g=a+c 4 Start by assigning (arbitrary) numbers to every expression in the function j=a+b 7 Pay no attention to what each expression is, just number it! Implementation: a map between expression number and location - eg, expression #6 = instruction#3 in basic-block #4 Spring 2014 Jim Hogg - UW - CSE - P501 R-9
def & kill for each Instruction def kill a=b+c 1 d=e+f 2 f=a+c 3 {1} {2} {3} {3,4,5,7} {5} {} g=a+d 5 h=b+c 6 g=a+c 4 j=a+b 7 Eg: a = b + c defs the expression b+c kills every expression that uses a Spring 2014 Jim Hogg - UW - CSE - P501 R-10
Summarize DEF & KILL for Basic Block def kill {1} {2} {3} {1,2} {3,4,5,7} {5} {} {3,4,5,7} a=b+c 1 d=e+f 2 f=a+c 3 KILL = {} foreach instruction KILL = killi g=a+d 5 h=b+c 6 g=a+c 4 DEF= {} foreach instruction DEF= (DEF geni ) - killi j=a+b 7 Union all the defs: {1,2,3}. Remove any which appear in KILL => {1,2} def and kill ~ instruction DEF and KILL ~ basic block Spring 2014 Jim Hogg - UW - CSE - P501 R-11
Summarize DEF & KILL for Flowgraph def kill {1} {2} {3} {1,2} {3,4,5,7} {5} {} {3,4,5,7} a=b+c 1 d=e+f 2 f=a+c 3 {5} {6} {5,6} {} {} {} g=a+d 5 h=b+c 6 {4} {4} {} {} g=a+c 4 j=a+b 7 Spring 2014 Jim Hogg - UW - CSE - P501 R-12
Available Expression Sets For each block b, define DEF(b) the set of expressions defined in b and not subsequently killed in b ie: defined in b and survives to its end can construct this by inspecting b in isolation - never changes KILL(b) the set of all expressions in the entire procedure that is killed in b can construct this by inspecting b in isolation - never changes AVAIL(b) the set of expressions available on entry to b find by solving a set of equations Implementation: assign a number to each expression and track its availability via one bit in a (large) bit-vector representing the set of all expressions in the function Spring 2014 Jim Hogg - UW - CSE - P501 R-13
Computing Available Expressions AVAIL(b) = DEF(p) ( AVAIL(p) - KILL(p) ) p preds(b) preds(b) is the set of b s predecessors in the flowgraph works for all flows, including loops defines a system of simultaneous equations a dataflow problem AVAILb = Intersectp DEFp (AVAILp - KILLp) AVAIL(p) GEN(p) predecessors p1 p2 p3 AVAIL(b) KILL(p) b Spring 2014 R-14
Computing Available Expressions Given DEFb and KILLb for each basic block, b, in the procedure: foreach block b { set AVAILb = {all expressions in function} = U } worklist = {all blocks in function} while (worklist {}) remove a block b from worklist recompute AVAILb if AVAILb changed worklist = = successorsb } } Spring 2014 Jim Hogg - UW - CSE - P501 R-15
Name Space? In previous value-numbering algorithms, we used an SSA-like renaming to keep track of versions In global dataflow problems, we use the original namespace we require that a+b have the same value along all paths to its use if a or b is updated along any path to its use, then a+b has the 'wrong' value, so must recalculate its value so original names are exactly what we want KILL captures when an expression becomes no longer "available" Spring 2014 Jim Hogg - UW - CSE - P501 R-16
Global CSE using Available Expressions Phase I Number each expression in procedure For each block b, compute DEFb and KILLb - once off Initialize AVAILb = {all expressions in procedure} = U For each block b, compute AVAILb, by iterating until fixed point Phase II For each block b, value-number the block starting with AVAILb Replace expressions in AVAILb with references to the previously computed values Also called "Global Redundancy Elimination" or GRE Spring 2014 Jim Hogg - UW - CSE - P501 R-17
Comparing Algorithms A m = a + b n = a + b B C p = c + d r = c + d q = a + b r = c + d D E e = b + 18 s = a + b u = e + f e = a + 17 t = c + d u = e + f LVN Local Value Numbering SVN Superlocal Value Numbering DVN Dominator-based Value Numbering GRE Global Redundancy Elimination F v = a + b w = c + d x = e + f G y = a + b z = c + d Spring 2014 Jim Hogg - UW - CSE - P501 R-18
Comparing Algorithms (2) LVN <= SVN <= DVN form a strict hierarchy later algorithms find a superset of previous information Global Redundancy Elimination, via Available Expressions, finds a different set Discovers e+f in F (computed in both D and E) Misses identical values if they have different names eg: a+b and c+d when a=c and b=d Value Numbering catches this D E e = b + 18 s = a + b u = e + f e = a + 17 t = c + d u = e + f F v = a + b w = c + d x = e + f Spring 2014 Jim Hogg - UW - CSE - P501 R-19
Scope of Analysis Larger context (EBBs, regions, global, inter-proc) may help More opportunities for optimizations But not always Introduces uncertainties about flow of control Usually only allows weaker analysis Sometimes has unwanted side effects Can create additional pressure on registers, for example Spring 2014 Jim Hogg - UW - CSE - P501 R-20
Code Replication Sometimes replicating code increases opportunities modify code to create larger regions with simple control flow Two examples Cloning Inline substitution Spring 2014 Jim Hogg - UW - CSE - P501 R-21
Cloning: Before & After Cloned m = a + b n = a + b A Original C B A p = c + d r = c + d q = a + b r = c + d C B G y = a + b z = c + d D E e = b + 18 s = a + b u = e + f e = a + 17 t = c + d u = e + f E D F F v = a + b w = c + d x = e + f y = a + b z = c + d v = a + b w = c + d x = e + f F G G y = a + b z = c + d G Even LVN can optimize these larger basic blocks Larger code size => increased I-cache pressure Spring 2014 Jim Hogg - UW - CSE - P501 R-22
Inline Substitution ("inlining") Calling a function can be expensive! Global optimizer must assume the callee can modify all reachable data: In MiniJava, all fields of all objects In C/C++, additionally all "global" data So the call kills many available expressions Must save/restore caller registers across call Calling the function imposes its own overhead Solution Inlining: replace each call with a copy of the callee Introduces more opportunities for optimization Spring 2014 Jim Hogg - UW - CSE - P501 R-23
Inline Substitution - "inlining" Class with trivial getter class C { int x; int getx() { return x; } } Compiler inlines body of getx into f class X { void f() { C c = new C(); int total = c.x + 42; } } Method f calls getx class X { void f() { C c = new C(); int total = c.getx() + 42; } } Eliminates call overhead Opens opportunities for more optimizations Can be applied to large method bodies too Aggressive optimizer will inline 2 or more deep Increases total code size With care, is a huge win for OO code Recompile if caller or callee changes! Spring 2014 Jim Hogg - UW - CSE - P501 R-24
Dataflow Analysis "Available Expressions" is a first example of dataflow analysis It supports the optimization called "Global Redundancy Elimination", or GRE Many similar problems can be expressed in same framework No limit to the number of execution paths thru a function No limit to the length of an execution path And yet, Dataflow Analysis infers a finite number of facts about the function Dataflow Analysis does not distinguish among the paths taken to any point eg: it assumes both arms of an IF-THEN-ELSE can be taken We then use these facts to transform and optimize the IR Example facts about a single function Variable x has the constant value 42 at every point At point p, variable x has same value as variable y At point p, value of x could have been defined only at point q At point p, the value of x is no longer required Spring 2014 Jim Hogg - UW - CSE - P501 R-25
Dataflow Equations - Overview Available Expressions AVAILINb = Intersectp DEFp ( AVAILINp - KILLp ) Live Variables LIVEINb = USEb ( LIVEOUTb - DEFb ) Reaching Defs REACHESb = Unionp DEFOUTp ( REACHESp SURVIVESp ) Anticipatable (Very Busy) Expressions ANTICb = Intersects USEDs ( ANTICs - KILLEDs ) Generic OUTb = GENb ( INb - KILLb ) Spring 2014 Jim Hogg - UW - CSE - P501 R-26
Dataflow Analysis Set of techniques for compile-time reasoning about runtime values Need to build a graph Trivial for basic blocks Flowgraph for whole-function (global) analysis Callgraph for whole-program analysis Limitations Assumes all paths are taken (eg: both arms of IF-THEN-ELSE) Infers facts about a function, rather than actual runtime values eg: x+y is redundant Arrays treats array as one variable eg: don't know, in general, whether a[i] == a[j] Pointers difficult, expensive to analyze eg: *p = 1; *q = 2; return *p; // same as return 1? Spring 2014 Jim Hogg - UW - CSE - P501 R-27
Recap: Available Expressions Same analysis we did earlier to eliminate redundant expressions AVAILb = Intersectp DEFp ( AVAILp - KILLp ) AVAILp DEFp predecessors p1 p2 p3 AVAILb KILLp b Spring 2014 R-28
Characterizing Dataflow Analysis All dataflow algorithms involve sets of facts about each block b INb facts true on entry to b OUTb facts true on exit from b GENb facts created and not killed in b KILLb facts killed in b These are related by the equation OUTb = GENb ( INb KILLb ) Solve this iteratively for all blocks Sometimes facts propagate forward (eg: available expressions) Sometimes facts propagate backward (eg: reaching defs) INb GENb b KILLb OUTb Spring 2014 R-29
Live Variables (or "liveness") A variable v is live at point p if there is any path from p to a use of v along which v is not redefined ie: a variable is live here if some later code uses its value there Some uses: Register allocation only live variables need a register Only live variables need be stored back to memory Detect use of uninitialized variables - how? Improve SSA construction only need -function for variables that are live in a block (later) Spring 2014 Jim Hogg - UW - CSE - P501 R-30
Liveness Analysis Sets For each block b, define the sets: USEb = variables used (ie, read-from) in b before any def DEFb = variables defined (ie, assigned-to) in b & not subsequently killed in b INb = variables live on entry to b OUTb = variables live on exit from b Spring 2014 Jim Hogg - UW - CSE - P501 R-31
Liveness - Intuition B DEFB = {x} x= x is "liveout" C USEC = {x} =x B x= DEFB = {x} x is not "liveout" B USEB = {x} C =x DEFC = {x} x= x is "livein" Spring 2014 Jim Hogg - UW - CSE - P501 R-32
Liveness Equations OUTb = Unions INs INb = USEb ( OUTb - DEFb ) Set INb = OUTb = {} Update IN and OUT until no change "backwards" dataflow analysis INb OUTb USEb b DEFb INs2 INs1 s2 s1 successors Spring 2014 T-33
Liveness Calculation INb = USEb (OUTb DEFb) OUTb = Unions INs 1: a = 0 block 1 2 3 4 5 6 USE - a b c b a c DEF a b c a - - 2: b = a + 1 3: c = c + b 4: a = b * 2 5: a < N Work backwards from 6 to 1 6: return c Spring 2014 Jim Hogg - UW - CSE - P501 R-34
Liveness Calculation INb = USEb (OUTb DEFb) OUTb = Unions INs 1: a = 0 block 1 2 3 4 5 6 USE - a b c b a c DEF a b c a - - OUT a c b c b c a c c - IN c a c b c b c a c c 2: b = a + 1 3: c = c + b 4: a = b * 2 5: a < N Work backwards from 6 to 1 Note c is livein for block 1 - uninitialized! 6: return c Spring 2014 Jim Hogg - UW - CSE - P501 R-35
Liveness Calculation INb = USEb (OUTb DEFb) OUTb = Unions INs 1: a = 0 block 1 2 3 4 5 6 USE - a b c b a c DEF a b c a - - OUT a c b c b c a c c - IN c a c b c b c a c c OUT a c b c b c a c a c - IN c a c b c b c a c c 2: b = a + 1 3: c = c + b 4: a = b * 2 5: a < N Work backwards from 6 to 1 Only change in iteration 2 - a is ivein for block 5 Stops changing after 2 iterations 6: return c Spring 2014 Jim Hogg - UW - CSE - P501 R-36
Liveness Calculation INb = USEb (OUTb DEFb) OUTb = Unions INs 1: a = 0 block 1 2 3 4 5 6 USE - a b c b a c DEF a b c a - - OUT a c b c b c a c c - IN c a c b c b c a c c OUT a c b c b c a c a c - IN c a c b c b c a c c 2: b = a + 1 3: c = c + b 4: a = b * 2 5: a < N Work backwards from 6 to 1 Stops changing after 2 iterations 6: return c Spring 2014 Jim Hogg - UW - CSE - P501 R-37
Alternate Liveness Equations Many problems have more than one formulation Different books use different sets: USED[b] NOTDEF[b] LIVE[b] variables used in b before being defined in b variables not defined in b variables live on exit from b Equation LIVE[b] = s succ(b) USED[s] ( LIVE[s] NOTDEF[s] ) Spring 2014 Jim Hogg - UW - CSE - P501 R-38
Reaching Defs A definition of variable v at L1 reaches instruction at L2 if that instruction uses v and there is a path from L1 to L2 that does not re- define v Use: Find all possible defs for a variable in an expression - great debugger plugin when looking for 'culprit' Spring 2014 Jim Hogg - UW - CSE - P501 R-39
Equations for Reaching Defs Sets DEFOUTb set of defs in b that reach the end of b SURVIVEDb set of all defs not killed by a re-def in b REACHb set of defs that reach b Equation REACHb = Unionp DEFOUTp ( REACHp SURVIVEDp ) Spring 2014 Jim Hogg - UW - CSE - P501 R-40
Anticipated Expressions Also known as "Very Busy" Expressions Expression x+y is anticipated at point p if all paths from p eventually compute x+y, using values of x and y as they exist at p Use: Code hoisting move x+y to p reduces code size; no effect on execution time Spring 2014 Jim Hogg - UW - CSE - P501 R-41
Equations for: Anticipated Expressions Sets USEDb KILLEDb ANTICb expressions used in b before they are killed expressions def'd in b before they are used anticipated expressions on exit from b Equation ANTICb = Intersects USEDs ( ANTICs - KILLEDs ) Spring 2014 Jim Hogg - UW - CSE - P501 R-42
Dataflow Equations - Recap Available Expressions AVAILINb = Intersectp DEFp ( AVAILINp - KILLp ) Live Variables LIVEINb = USEb ( LIVEOUTb - DEFb ) Reaching Defs REACHESb = Unionp DEFOUTp ( REACHESp SURVIVESp ) Anticipated Expressions ANTICb = Intersects USEDs ( ANTICs - KILLEDs ) Generic OUTb = GENb ( INb - KILLb ) Spring 2014 Jim Hogg - UW - CSE - P501 R-43
Efficiency of Dataflow Analysis The algorithms eventually terminate but reduce time-needed by picking a good order to visit nodes in the flowgraph depends on how information flows Forward problems reverse post-order Backward problems - post-order Spring 2014 Jim Hogg - UW - CSE - P501 R-44
Using Dataflow Facts Some possible Tranformations/Optimizations ... Spring 2014 Jim Hogg - UW - CSE - P501 R-45
CSE Elimination x+y is defined at L1 and available at L2 ie: x nor y is re-defined between L1 and L2 after before L1: = x+y L1: = x+y t = a Save calculation into temp t L2: = x+y L2: = t Use t, rather than re-calculate Analysis: Available Expressions Code runs faster by not re-calculating x+y Spring 2014 Jim Hogg - UW - CSE - P501 R-46
Constant Prop. c is a constant a reaches L2 (a is not re-defined between L1 and L2) after before L1: a = c L1: a = c L2: = a L2: = c Propagate c, not a Analysis: Reaching Defs Code runs faster because c is embedded into the instruction Spring 2014 Jim Hogg - UW - CSE - P501 R-47
Copy Prop. x is a variable a reaches L2 (a is not re-defined between L1 and L2), and is the only def of a to reach L2 after before L1: a = x L1: a = x L2: = a L2: = x Propagate x, not a Analysis: Reaching Defs Code runs faster because c is embedded into the instruction Spring 2014 Jim Hogg - UW - CSE - P501 R-48
Copy Prop. Tradeoffs Downside: can lengthen lifetime of variable x => more register pressure or memory traffic thru spilling not worth doing if only reason is to eliminate copies let the register allocate deal with that Upside: may expose other optimizations. Eg: before after a = y + z u = y c = u + z a = y + z u = y c = y + z Now reveals CSE y+z Spring 2014 Jim Hogg - UW - CSE - P501 R-49
Dead Code Elimination (DCE) a is dead after L1 statement at L1 has no side-effects (output, exceptions, etc) after before Delete statement at L1 L1: a = x Analysis: Liveness Code runs faster because one less statement Spring 2014 Jim Hogg - UW - CSE - P501 R-50
