Algorithm 7.1 Intraprocedural Context-Insensitive Whole-Program Pointer Analysis

Input: Set of statements of the input program $S$ .

Output: Pointer flow graph $PFG$ and point-to set of each pointer $x$ denoted by $pt(x)$ .

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

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

3:for each pointer $x \in S$ do

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

5:end for

7:procedure Solve( $S$ ) // main algorithm

8:for each $i:x = new\ T() \in S$ do

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

10:end for

11:for each $x = y \in S$ do

12:AddEdge( $y, x$ )

13:end for

14:while $WL$ is not empty do

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

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

17:Propagate( $n, \Delta$ )

18:if $n$ represents a variable $x$ then

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

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

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

22:end for

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

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

25:end for

26:end for

27:end if

28:end while

29:end procedure

30:

31:procedure AddEdge( $s, t$ )

32:if $s \to t \notin PFG$ then

33:add $s \to t$ to $PFG$

34:if $pt(s)$ is not empty then

35:add $(t, pt(s))$ to $WL$

36:end if

37:end if

38:end procedure

39:

40:procedure Propagate( $n, pts$ )

41:if $pts$ is not empty then

42: $pt(n) = pt(n) \cup pts$

43:for each $n\to s\in PFG$ do

44:add $(s, pts)$ to $WL$

45:end for

46:end if

47:end procedure