<aside> 🔑 Key Points

• Understand pointer analysis rules
• Understand pointer flow graph
• Understand pointer analysis algorithms
• Understand pointer analysis rule for method call
• Understand inter-procedural pointer analysis algorithm
• Understand on-the-fly call graph construction </aside>

I. Pointer Analysis: Rules

1. Domain and Notations

• Variables
• Fields
• Objects (Allocation sites)
• Instance fields
• Pointers

$x,y\in V$

$f,g \in F$

$o_i,o_j\in O$

$o_i.f,o_j.g\in O\times F$

$\text{Pointer}=V\cup(O\times F)$

• Points-to relations
  • $P(O)$ power set of $O$
  • $pt(p)$: points-to set of $p$

$pt=\text{Pointer}\rightarrow P(O)$

2. Rules

$$ \rm \frac{Premises}{Conclusion} $$

• New: $\tt i:x=new~T()$

  $$ \frac{}{o_i\in pt(x)} $$

• Assign: $\tt x=y$

  $$ \frac{o_i\in pt(y)}{o_i \in pt(x)} $$

• Store: $\tt x.f=y$

  $$ \frac{o_i\in pt(x),~o_j\in pt(y)}{o_j\in pt(o_i. f)} $$

• Load: $\tt y=x.f$

  $$ \frac{o_i\in pt(x),~o_j\in pt(o_i. f)}{o_j\in pt(y)} $$

3. Extended Rules

• Static Store: $\tt T.f=y$

  PFG Edge: $T.f \leftarrow y$

$$ \frac{o_i\in pt(y)}{o_i \in pt(T.f)} $$

• Static Load: $\tt y = T.f$

  PFG Edge: $y ← T.f$

$$ \frac{o_i \in pt(T.f)}{o_i \in pt(y)} $$

$o_u[*]$: the pointer which points to all elements that are stored in any indexes of the array

• Array Store: $\tt x[i]=y$

  PFG Edge: $o_u[*] \leftarrow y$

$$ \frac{o_u\in pt(x),~o_v\in pt(y)}{o_v\in pt(o_u[*])} $$

• Array Store: $\tt y = x[i]$

  PFG Edge: $y \leftarrow o_u[*]$

$$ \frac{o_u\in pt(x),~o_v\in pt(o_u[*])}{o_v\in pt(y)} $$

II. How to Implement Pointer Analysis