Alias Analysis

Also called points-to analysis (alias: two expressions that denote the same memory location)
Can be used to improve the precision of analysis that require knowing what is modified and referenced (e.g. constant prop, common subexpression elimination)

Intraprocedural analysis

Could build a simple algorithm that just creates list where each node denotes slice in memory… NO
– Lattice infinitely tall
– This is just like running the program, and no guarantee of termination

Introduce summary nodes where each node S denotes locations of all slices in memory allocated by one statement… YES?

Interprocedural analysis

Intraprocedural pointer analysis is not enough
– Sharing data structures across multiple procedures is one of the big benefits of pointers. So, without interprocedural analysis, there needs to be conservative assumptions making the whole analysis too imprecise.
Main difficulty in performing interprocedural pointer analysis is scaling (space and time)

Default… NO

Make it flow-insensitive (default was flow-sensitive)… NO
– Loss of too much information
– Still have to iterate

Do not kill information… Andersen’s algorithm
– Leads to loss of some information
– Uses less memory and runs faster than default

Lets make one successor per node… Steensgaard’s algorithm
– Leads to loss of more information
– But very very fast!!!

Details

Referencing (a = new b): a –> S#
Aliasing (a = b): a –> pts(b)
Dereferencing read (a = *b): a –> pts(pts(b))
Dereferencing write (*a = b): pts(a) –> pts(b)

Andersen’s Points-to Analysis

– Asympotic performance is O(n^3)
– More precise than Steensgaard’s Analysis
– Subset-based (Inclusion-based): just propagates information to the other set (more precise in some cases)

Steensgaard’s Points-to Analysis

– Fast: O(n α (n,n)) over variables in program
– Sacrifices precision
– Equality-based: merges information