1CIS570 Lecture 10 Introduction to Alias Analysis 2Introduction to Alias Analysis Last time– Common Subexpression Elimination– Partial Redundancy Elimination Today– Alias analysisCIS570 Lecture 10 Introduction to Alias Analysis 3Alias Analysis Goal: Statically identify aliases– Can memory reference m and n access the same state at program point p?– What program state can memory reference m access? Why is alias analysis important?– Many analyses need to know what storage is read and writtene.g., available expressions (CSE)*p = a + b; y = a + b; Otherwise we must be very conservativeIf *p aliases a or b, the secondexpression is not redundant (CSE fails)2CIS570 Lecture 10 Introduction to Alias Analysis 4 Is x constant here?– Yes, only one value of x reaches this laststatementConstant Propagation Revisited{ int x, y, a; int *p; p = &a; x = 5; y = x + 1;}CIS570 Lecture 10 Introduction to Alias Analysis 5The Importance of Pointer Analysis{ int x, y, a; int *p; p = &a; x = 5; *p = 23; y = x + 1;} Is x constant here?– If p does not point to x, then x = 5– If p definitely points to x, then x = 23– If p might point to x, then we have tworeaching definitions that reach this laststatement, so x is not constant3CIS570 Lecture 10 Introduction to Alias Analysis 6Trivial Pointer Analysis{ int x, y, a; int *p; p = &a; x = 5; *p = 23; y = x + 1;} Is x constant here?– With our trivial analysis, we assume that pmay point to x, so x is not constant No analysis– Assume that nothing must alias– Assume that everything may alias everythingelse– Yuck!– Enhance this with type information?CIS570 Lecture 10 Introduction to Alias Analysis 7A Slightly Better Approach (for C){ int x, y, a; int *p; p = &a; x = 5; *p = 23; y = x + 1;} Is x constant here?– With Address Taken, *p and a mayalias, but neither aliases with x Address Taken– Assume that nothing must alias– Assume that all pointerdereferences may alias each other– Assume that variables whoseaddresses are taken (and globals)may alias all pointer dereferences4CIS570 Lecture 10 Introduction to Alias Analysis 8Address Taken (cont){ int x, y, a; int *p, *q; q = &x; p = &a; x = 5; *p = 23; y = x + 1;} Is x constant here?– With Address Taken, we now assumethat *p, *q, a, and x all aliasCIS570 Lecture 10 Introduction to Alias Analysis 9A Better Points-To Analysis Goal– At each program point, compute set of (p→x) pairs if p points to x Properties– Use dataflow analysis– May information (will look at must information next)5CIS570 Lecture 10 Introduction to Alias Analysis 10May Points-To Analysis Domain: 2var × var Direction: forward Flow functions– s: p = &x;out[s] = {(p→x)} ∪ (in[s] – {(p→y) ∀ y})– s: p = q;out[s] = {(p→t) | (q→t) ∈ in[s]} ∪ (in[s] – {(p→y) ∀y}) Meet function: What if we have pointers to pointers?– e.g., int **q; p = *q;x1p x2x3qx1x2x3 ∪py1y2qx1x2x3p = qCIS570 Lecture 10 Introduction to Alias Analysis 11May Points-To Analysis (Pointers to Pointers) Additional flow functions– s: p = *q;out[s] = {(p→t) | (q→r) ∈ in[s] & (r→t) ∈ in[s]} ∪(in[s] – {(p→x) ∀x})– s: *q = p;out[s] = {(r→t) | (q→r) ∈ in[s] & (p→t) ∈ in[s]} ∪(in[s] – {(r→x) ∀x | (q→r) ∈ inmust[s]})p = *qqr1r2t1t2t3pt1t2t3pt1t2*p = qqr1r2v1r2t1t2v1r1t1t26CIS570 Lecture 10 Introduction to Alias Analysis 12May Points-To Analysis (cont) What is the flow function for the following statement?– s: x = 3; *p = x; out[s] = in[s]*p = xpt1t2t3t3pt1t2CIS570 Lecture 10 Introduction to Alias Analysis 13Dealing with Dynamically Allocated Memory Issue– Each allocation creates a new piece of storagee.g., p = new T Proposal?– Generate (at compile-time) a new “variable” to stand for new storage Flow function– s: p = new T;out[s] = {(p→newvar)} ∪ (in[s] – {(p→x) ∀x}) Problem– Domain is unbounded!– Iterative data-flow analysis may not converge7CIS570 Lecture 10 Introduction to Alias Analysis 14Dynamically Allocated Memory (cont) Simple solution– Create a summary “variable” (node) for each allocation statement– Domain: 2(Var ∪ Stmt) × (Var ∪ Stmt) rather than 2Var × Var– Monotonic flow functions: p = new T;out[s] = {(p→stmts)} ∪ (in[s] – {(p→x) ∀x})– Less precise (but finite) Alternatives– Summary node for entire heap– Summary node for each type– K-limited summary– Maintain distinct nodes up to k links removed from root variablesCIS570 Lecture 10 Introduction to Alias Analysis 15Must Points-To Analysis Meet function: ∩ Analogous flow functions– s: p = &x;outmust[s] = {(p→x)} ∪ (inmust[s] – {(p→x) ∀x})– s: p = q;outmust[s] = {(p→t) | (q→t) ∈ inmust[s]} ∪ (inmust[s] – {(p→x) ∀x)})– s: p = *q;outmust[s] = {(p→t) | (q→r) ∈ inmust[s] & (r→t) ∈ inmust[s]} ∪(inmust [s] – {(p→x) ∀x)})– s: *p = q;outmust[s] = {(r→t) | (p→r) ∈ inmust[s] & (q→t) ∈ inmust [s]} ∪(inmust[s] – {(r→x) ∀x | (p→r) ∈ inmust[s]}) Compute this along with may analysis– Why?8CIS570 Lecture 10 Introduction to Alias Analysis 16*p and i must aliasDefiniteness of Alias Information Often need both– Consider liveness analysiss: *p = *q+4; May (possible) alias information– Indicates what might be truee.g.,if (c) p = &i; Must (definite) alias information– Indicates what is definitely truee.g.,p = &i;*p and i may alias(1) *p must alias v ⇒ def[s] = kill[s] = {v}(2) *q may alias v ⇒ use[s] = gen[s] = {v}Suppose out[s] = {v}Recall: in[s] = use[s] ∪ (out[s] – def[s])CIS570 Lecture 10 Introduction to Alias Analysis 17Using Points-To Information{ int x, y, a; int *p, *q; q = &x; p = &a; x = 5; *p = 23; y = x + 1;} Then run constant propagation– Since *p and x do not alias, x isconstant in this last statement The point– Pointer analysis is an enabling analysis To support constant propagation,first run points-to analysis{(q→x)}{(q→x)}(p→a)}{(q→x)}(p→a)}{(q→x)}(p→a)}{(q→x)}(p→a)}9CIS570 Lecture 10 Introduction to Alias Analysis 18Using Points-To Information (cont) Example: reaching definitions– Compute at each point in the program a set of (v,s) pairs, indicating thatstatement s may define variable v Flow functions– s: x = y;outreach[s] = {(x,s} ∪ (inreach[s] – {(x,t) ∀t}– s: x = *p;outreach[s] = {(x,s} ∪ (inreach[s] –