Algorithm 8.1 Interprocedural Context-Sensitive Whole-Program Pointer Analysis

Input: Entry method $m^{entry}$ and a context generator Select( $c, l, c':o_i$ ).

Output: Pointer flow graph $PFG$ and point-to set of $pt(x)$ and call graph $CG$ , all context-sensitive.

1: $WL := []$ // work list, initialized as empty

2: $PFG := \{\}$ // context-sensitive pointer flow graph, initialized as empty

3: $S := \{\}$ // set of reachable statements, initialized as empty

4: $RM := \{\}$ // set of context-sensitive reachable methods, initialized as empty

5: $CG := \{\}$ // context-sensitive call graph, initialized as empty

7:procedure Solve( $m^{entry}$ ) // main algorithm

8:AddReachable( $[]:m^{entry}$ )

9:while $WL$ is not empty do

10:remove $(n, pts)$ from $WL$

11: $\Delta := pts - pt(n)$

12:Propagate( $n, \Delta$ )

13:if $n$ represents a variable $c:x$ then

14:for each $c':o_i \in \Delta$ do

15:for each $x.f = y \in S$ do

16:AddEdge( $c:y, c':o_i.f$ )

17:end for

18:for each $y = x.f \in S$ do

19:AddEdge( $c':o_i.f, c:y$ )

20:end for

21:ProcessCall( $c:x, c':o_i$ )

22:end for

23:end if

24:end while

25:end procedure

26:

27:procedure AddReachable( $c:m$ )

28:if $c:m \notin RM$ then

29:add $c:m$ to $RM$

30: $S = S \cup S_{m}$ // $S_m$ is the set of statements in method $m$ .

31:for each pointer $x \in S_{m}$ do

32: $pt(c:x) := \{\}$ // point-to set of each context-sensitive pointer, initialized as empty

33:end for

34:for each $i:x=new\ T()\in S_{m}$ do

35:add $(c:x, \{c:o_i\})$ to $WL$

36:end for

37:for each $x=y\in S_{m}$ do

38:AddEdge( $c:y, c:x$ )

39:end for

40:end if

41:end procedure

42:

43:procedure ProcessCall( $c:x, c':o_i$ )

44:for each $l: r = x.k(a_1, ..., a_n) \in S$ do

45: $m :=$ Dispatch( $o_i, k$ )

46: $c^t :=$ Select( $c, l, c':o_i$ )

47:add $(c^t: m_{this}, \{c':o_i\})$ to $WL$

48:if $c:l \to c^t:m \notin CG$ then

49:add $c:l \to c^t:m$ to $CG$

50:AddReachable( $c^t:m$ )

51:for each parameter $p_i$ of $m$ do

52:AddEdge( $c:a_i, c^t:p_i$ )

53:end for

54:AddEdge( $c^t:m_{ret}, c:r$ )

55:end if

56:end for

57:end procedure