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:

 p = &r;

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.

Example input code

// test_ptr2.C
int a;

void foo(int* &x)
{
    int b  = 10;  
    x = &b;
   // x has an alias set {b}
    #pragma rose x:Aliases:{b}{}b:Aliases:{}{}  

}
    
void main()
{   
    int *p;
    a = 20;
    foo(p);
   // p has an alias set {b} due to function call. 
    #pragma rose a:Aliases:{}{}p:Aliases:{b}{}  
}

No exact string match

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

The reason I did that is because unlike other analysis whose lattices contain exact information such as constantPropagation 

(Ex: [VarsExprsProductLattice: level=uninitialized
d: ConstantPropagationLattice:[level: constantValue, val = 9]
] ) my analysis contains temporary memory addresses(since it is a per variable lattice) which may be specific only to that run.

For e.g.,: [VarsExprsProductLattice: level=uninitialized
__expression_0x107b80200-SgIntVal: Aliases:{ }{}
__expression_0x107b80268-SgIntVal: Aliases:{ }{}
__expression_0x107b802d0-SgIntVal: Aliases:{ }{}
__expression_0x107b99a00-SgAssignOp: Aliases:{ }{}
__expression_0x107b99a70-SgAssignOp: Aliases:{ }{("p",p,0) ("a",a,-1)}
__expression_0x107b99ae0-SgAssignOp: Aliases:{ }{("p",p,0) ("b",b,-1)}
__expression_0x107b99b50-SgAssignOp: Aliases:{ }{}
__expression_0x107b99bc0-SgAssignOp: Aliases:{ }{("q",q,0) ("p",p,0)}
__expression_0x107bca800-SgAddressOfOp: Aliases:{ }{}
__expression_0x107bca868-SgAddressOfOp: Aliases:{ }{}
__expression_0x107bca8d0-SgAddressOfOp: Aliases:{ }{}
__expression_0x107c20a00-SgCastExp: Aliases:{ }{}
a: Aliases:{ }{}
b: Aliases:{ }{}
c: Aliases:{ }{}
p: Aliases:{ b }{}
q: Aliases:{ b }{}
x: Aliases:{ }{}
]

In order to verify the correctness of this output, all we need to check is the pointer aliases for the pointer variables -->
a: Aliases:{ }{}
b: Aliases:{ }{}
c: Aliases:{ }{}
p: Aliases:{ b }{}
q: Aliases:{ b }{}
x: Aliases:{ }{}

Since this is only the substring of the complete lattice, I used substr find rather than the exact string match.

I hope this clarifies your question. I will put a note in the code too.

Thanks
Akshatha

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