# ROSE Compiler Framework/Pointer Analysis
## Aliasing Relations

An access path: the l-value of an expression that is constructed from variables, pointer dereference operators, and structure field selection operators.
* For C: "*" deference, "." field selection, "->" dereference and field selection
Aliasing occurs when there exists more than one access path to a storage location. An access path is the l-value of an expression constructed from variables, pointer indirection operators, and structure field selection operators. For e.g., in C it includes ‘*’ dereference operator, ‘.’, ‘->’ operator etc. Consider the following statement:
After this statement, *p and r refer to the same storage location and thus become aliases of each other, which can be expressed as the relation <*p, r>.
Two access paths are
* a must-alias at a statement S if they refer to the same storage locations in all execution instances of S.
* a may-aliases at S if they refer to the same storage location at some execution instance of S.
Trivial alias <x, x> holds for all access paths x, provided x does not result in a dereference of the null pointer.
* Semantics: x is self aliasing to itself
* if x and y are non-NULL pointers, <x,y> implies <*x, *y>

### Compact representation

A compact representation is used for each alias relation

## Algorithm

The current implementation implements Michael Hind, Michael Burke, Paul Carini, and Jong-Deok Choi. 1999. Interprocedural pointer alias analysis. ACM Trans. Program. Lang. Syst. 21, 4 (July 1999), 848-894. link.
Features
* Intra procedural analysis: summarizes the alias information of each function
** Flow-sensitive: control flow paths are considered
* Inter-procedural analysis: considering call graphs to propagates alias information across the call graph to determine the “type” of the object
** Context in-sensitive: call stack information is ignored
* Complexity: computing pointer aliases is considered an NP-Hard problem; hence this algorithm uses approximation methods to compute aliases.
* Uses compact representation graphs to represent alias information.

## Testing

make check rules:
* [/path/build_rose/tests/roseTests/programAnalysisTests/generalDataFlowAnalysisTests]make verify-pointerAliasAnalysis
We use a primitive way to test the correctness.
* Input test code: we add pragmas to indicate expected results
* Test translator: compare lattices generated by the analysis with the pragma information.

### No exact string match

Exact string match is not used, due to the following reason:

## TODO

List
* move to rose/src.
* creating a temp variable for each new expression may not be necessary since GDF supports temporary expressions as objects.

## References

List of related papers
* David Bacon and Peter Sweeney, “Fast Static Analysis of C++ virtual function calls”, OOPSLA'96
* Michael Burke, Paul Carini, Jong-Deok Choi and Michael Hind, “Interprocedural Pointer Alias Analysis”, TOPLAS ‘99
* Paul Carini Harini Srinivasan, “Flow-Sensitive Interprocedural Type Analysis for C++”, TechReport ’95
* David J. Pearce , Paul H.J. Kelly , Chris Hankin, Efficient field-sensitive pointer analysis of C, ACM Transactions on Programming Languages and Systems (TOPLAS), v.30 n.1, p.4-es, November 2007