1CS553 Lecture Alias Analysis I 2Alias Analysis Last time– Midterm Today– Alias analysis (pointer analysis) Next time– More alias analysis (pointer analysis)CS553 Lecture Alias Analysis I 3Aliasing What is aliasing?– When two expressions denote the same mutable memory location– e.g., p = new Object; q = p; ⇒ *p and *q alias How do aliases arise?– Pointers– Call by reference (parameters can alias each other or non-locals)– Array indexing– C union, Pascal variant records, Fortran EQUIVALENCE and COMMONblocksCS553 Lecture Alias Analysis I 4Aliasing Examples Pointers (e.g., in C)int *p, i;p = &i;*p and i alias Parameter passing by reference (e.g., in Pascal)procedure proc1(var a:integer; var b:integer);. . .proc1(x,x);proc1(x,glob);a and b alias in body of proc1b and glob alias in body of proc1 Array indexing (e.g., in C)int i,j, a[128];i = j;a[i] and a[j] aliasCS553 Lecture Alias Analysis I 5What Can Alias? Stack storage and globalsvoid fun(int p1) {int i, j, temp;...} Heap allocated objectsn = new Node;n->data = x;n->next = new Node;...do i, j, or temp alias?do n and n->next alias?2CS553 Lecture Alias Analysis I 6What Can Alias? (cont) Arraysfor (i=1; i<=n; i++) { b[c[i]] = a[i];}do b[c[i1]] andb[c[i2]] alias for any twointerations i1 and i2?Can c[i1] and c[i2] alias?Javacc 7 1 4 2 3 1 9 0FortranCS553 Lecture Alias Analysis I 7Alias 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;– e.g., Reaching definitions (constant propagation)d1: x = 3;d2: *p = 4;d3: y = x; Otherwise we must be very conservativeIf *p aliases a or b, the secondexpression is not redundant (CSE fails)If *p aliases x, d2 reaches this point;otherwise, both d1 and d2 reachCS553 Lecture Alias Analysis I 8How hard is this problem? Undecidable– Landi 1992– Ramalingan 1994 All solutions are conservative approximations Is this problem solved?– Why haven’t we solved this problem? [Hind 2001]– Next week we will look at some open issuesCS553 Lecture Alias Analysis I 9Trivial Alias Analyses Easiest approach– Assume that nothing must alias– Assume that everything may alias everything else– Yuck! Address taken: A slightly better approach (for C)– Assume that nothing must alias– Assume that all pointer dereferences may alias each other– Assume that variables whose addresses are taken (and globals) may alias allpointer dereferencese.g.,p = &a;. . .a = 3; b = 4;*q = 5; Enhance with type information?*q and a may alias, so a may be 3 or 5, but*q does not alias b, so b is 43CS553 Lecture Alias Analysis I 10Properties of Alias Analysis Scope: Intraprocedural (per procedure) or Interprocedural (whole program) Representation– Alias pairs?– Points-to sets?– Others. . .? Flow sensitivity: Sensitive versus insensitive? Context sensitivity: Sensitive versus insensitive? Definiteness: May versus must? Heap Modeling? Aggregate Modeling?CS553 Lecture Alias Analysis I 11Representations of Aliasing Equivalence sets– All memory references in the same set are aliases– e.g., {*a,b}, {*b,c,**a}  Alias pairs– Pairs that refer to the same memorye.g., (*a,b), (*b,c), (**a,c)– Completely general Points-to pairs [Emami94]– Pairs where the first member points to the seconde.g., (a -> b), (b -> c)– Possibly more compact than alias pairs[Shapiro & Horwitz 97]int **a, *b, c, *d, e;1: a = &b;2: b = &c;CS553 Lecture Alias Analysis I 12Flow Sensitivity of Alias Analysis Flow-sensitive alias analysis– Compute aliasing information at each program pointe.g.,p = &x;...p = &y; Flow-insensitive alias analysis– Compute aliasing information for entire proceduree.g.,p = &x;...p = &y;*p and x alias here*p and y alias here*p may alias x or yin this procedureCS553 Lecture Alias Analysis I 13*p and i must aliasDefiniteness of Alias Information 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; Often need both– e.g., Consider liveness analysiss: *p = *q+4;*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])4CS553 Lecture Alias Analysis I 14Flow-sensitive May Points-To Analysis Analogous flow functions– ⊓ is ∪– 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)})– s: p = *q;out[s] = {(p→t) | (q→ r) ∈ in[s] & (r→t) ∈ in[s]} ∪(in[s] –{(p→x) ∀x})– s: *p = q;out[s] = {(r→t) | (p→ r) ∈ in[s] & (q→t) ∈ in[s]} ∪(in[s] – {(r→x) ∀x | (p→r) ∈ inmust[s]})CS553 Lecture Alias Analysis I 15Must Points-To Analysis Analogous flow functions– ⊓ is ∩– 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→*) | (p→r) ∈ inmust[s]}) Compute along with may analysisCS553 Lecture Alias Analysis I 16Other Issues (Modeling the Heap) 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– newvar: Creates a new variable 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 convergeCS553 Lecture Alias Analysis I 17Modeling the Heap (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 variables5CS553 Lecture Alias Analysis I 18Using