[Compilers] Alias Analysis

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.