Points-to Analysis

This analysis computes the set of objects or components that a pointer can reference to. There are a lot of different categories of methods. The method described here is based on:

• flow-sensitive analysis: control-flow information is considered during analysis;
• context-sensitive analysis: when calling a function, values flow from one call through the function and return to another caller;
• heap modeling: objects named by allocation site
• aggregate modeling: elements of struct/array are distinguished

Definitions

• obj(p): the set of objects that p may reference to;
• obj(e): the set of objects that e may represent, where e has pointer type, or composite type of pointer type (e.g., array of pointers);

• Conditional Object Set of a pointer p:
  • cobj(p)={c0->O0, c1->O1, c2->O2, ...} where O1, O2, ... are all set of objects
  • c0->O0 denotes that when c0 is satisfied the objects set that p could refer to is O0

Expressions

let e be an expression, let le be an left-hand-side expression, let impact(e) be the set of impact memory units of e. letmu(e) be a function to convert an expression, of pointer type or being a left-hand-side expression, to a memory unit.

1. abstract function call: f(e0,e1, ...)

???

2. address-of: &le

obj(&le)={le}

3. array literal: {e0, e1, ...} where e0, .. e1 all have pointer types

obj({e0, e1, ...}) = obj(e0) U obj(e1) ...

4. pointer addition: e0 + e1

obj(e0 + e1) = offset(e0, e1)

5. cast expression: (T)e (where T is pointer type)

obj((T)e)=obj(e)

6. conditional expression: e0 ? e1 : e2

obj(e0 ? e1 : e2) = e0 ? obj(e1) : obj(e2)

7. dereference expression: *e where e has type pointer-to-pointer of T

obj(*e) = **???** the impact memory units of *e include the memory unit refers to by e, and the impact memory units of the sub-expressions of e. e.g., the impact memory units of *(p+i) is {mu(p+5), impact(i)}, because p is of pointer type and sub(p+i) is {i}.

8. dot expression: e.k where e.k has pointer type

obj(e.k) = {e.k}

9. subscript expression: ea[ei]

obj(ea[ei])={ea[ei]}

Questions

1. how about arrays of pointers:

e.g., for int* a[10];, we'll need to have one set for each array element.
how do you deal with:

int *a[10], b[10];

for(int i=0; i<10; i++){
  a[i]=b[i];
}

A precise analysis should say that:

obj(a[0])={b[0]}
obj(a[1])={b[1]}
...
but a less-precise analysis could say that:
obj(a[0])={b[0], b[1], ...}
obj(a[1])={b[0], b[1], ...}
...

A more intersting example:

$parfor(int i: 0 .. 9){
   a[i]=b[i];
}