Algorithm 7.2 Interprocedural Context-Insensitive Whole-Program Pointer Analysis

Input: Entry method $m^{entry}$ .

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

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

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

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

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

5: $CG := \{\}$ // 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 $x$ then

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

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

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

17:end for

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

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

20:end for

21:ProcessCall( $x, o_i$ )

22:end for

23:end if

24:end while

25:end procedure

26:

27:procedure AddReachable( $m$ )

28:if $m \notin RM$ then

29:add $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(x) := \{\}$ // poinrt-to set of each pointer, initialized as empty

33:end for

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

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

36:end for

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

38:AddEdge( $y, x$ )

39:end for

40:end if

41:end procedure

42:

43:procedure ProcessCall( $x, o_i$ )

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

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

46:add $(m_{this}, \{o_i\})$ to $WL$

47:if $l \to m \notin CG$ then

48:add $l \to m$ to $CG$

49:AddReachable( $m$ )

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

51:AddEdge( $a_i, p_i$ )

52:end for

53:AddEdge( $m_{ret}, r$ )

54:end if

55:end for

56:end procedure