Pointer Analysis

(1)

CS618: Program Analysis 2016-17 I

^st

Semester

Pointer Analysis

Amey Karkare

karkare@cse.iitk.ac.in karkare@cse.iitb.ac.in

Department of CSE, IIT Kanpur/Bombay

(2)

Why Pointer Analysis?

Static analysis of pointers & references

S1. . . .

S2. q=p;

S3. do{

S4. q=q.next; S5. }while(. . .) S6. p.data=r1;

S7. q.data=q.data+r2;

S8. p.data=r1;

S9. r3=p.data+r2;

S10. . . .

p q

m1 m2 m3 mk

p next next

q q

q

Stack Heap

Superimposition of memory graphs afterdo-whileloop

pandqare definitely not aliases statement S6 onwards.

Statement S8 isredundant.

(3)

Static analysis of pointers & references

S1. . . .

S2. q=p;

S3. while(. . .){ S4. q=q.next; S5. }

S6. p.data=r1;

S7. q.data=q.data+r2;

S8. p.data=r1;

S9. r3=p.data+r2;

S10. . . .

p q

m1 m2 m3 mk

p next next

q q q

q

Stack Heap

Superimposition of memory graphs afterwhileloop

pandqmay be aliases statement S6 onwards.

Statement S8 is notredundant.

(4)

x = &a;

a = 5; *x = 15;

c = a + 1;

Reaching definitions analysis

(5)

x = &a;

a = 5; *x = 15;

c = a + 1;

Reaching definitions analysis

Which defs ofareach here?

(6)

Flow Sensitivity in Data Flow Analysis

Flow Sensitive Analysis

(7)

Order of execution: Determined by the semantics of language

(8)

Point-specific information computed at each program point within a procedure

(9)

A statement can “override” information computed by a previous statement

(10)

A statement can “override” information computed by a previous statement

Killcomponent in the flow function

(11)

Flow Insensitive Analysis

(12)

Order of execution: Statements are assumed to execute in any order

(13)

As a result, all the program points in a procedure receive identical data flow information.

(14)

“Summary” for the procedure

(15)

Safe approximation of flow-sensitive point-specific information for any point, for any given execution order

(16)

Safe approximation of flow-sensitive point-specific information for any point, for any given execution order A statement can not “override” information computed by another statement

(17)

NOKill component in the flow function

(18)

NOKill component in the flow function

If statementskills some data flow information, there is an alternate path that excludess

(19)

Examples of Flow Insensitive Analyses

Type checking, Type inferencing

(20)

Compute/Verify type of a variable/expression

(21)

Compute/Verify type of a variable/expression Address taken analysis

(22)

Which variables have their addresses taken?

(23)

A very simple form of pointer analysis

(24)

A very simple form of pointer analysis Side effects analysis

(25)

A very simple form of pointer analysis Side effects analysis

Does a procedure modify address / global variable / reference parameter / . . . ?

(26)

Realizing Flow Insensitivity

b₀

b₁

b₂ b3

b4

b5

(27)

b₀

b₁

b₂ b3

b4

b5

ENTRY

b0 b₁ b₂ b3 b₄ b5

EXIT

(28)

b₀

b₁

b₂ b3

b4

b5

ENTRY

b0 b₁ b₂ b3 b₄ b5

EXIT

Allows arbitrary compositions of flow functions in any order⇒ Flow insensitivity

(29)

b₀

b₁

b₂ b3

b4

b5

ENTRY

b0 b₁ b₂ b3 b₄ b5

EXIT

In practice, dependent constraints are collected in a global repository in one pass and solved independently

(30)

Alias Analysis vs. Points-to Analysis

Points-to Analysis Alias Analysis

x = &a x = a

x points-to a x and a are aliases

(31)

x = &a x = a

x→a x≡a

(32)

x = &a x = a

x→a x≡a

Reflexive?

(33)

x = &a x = a

x→a x≡a

Reflexive? No Yes

(34)

x = &a x = a

x→a x≡a

Reflexive? No Yes

Symmetric?

(35)

x = &a x = a

x→a x≡a

Reflexive? No Yes

Symmetric? No Yes

(36)

x = &a x = a

x→a x≡a

Reflexive? No Yes

Symmetric? No Yes

Transitive?

(37)

x = &a x = a

x→a x≡a

Reflexive? No Yes

Symmetric? No Yes

Transitive? No

(38)

x = &a x = a

x→a x≡a

Reflexive? No Yes

Symmetric? No Yes

Transitive? No Must alias: Yes,

May alias: No

(39)

Andersen’s Flow Insensitive Points-to Analysis

Subset based analysis

Program Constraints Points-to Graph

1 a = &b

2 c = a

3 a = &d 4 a = &e

5 b = a

# Constraint

(40)

Subset based analysis P_lhs ⊇P_rhs

1 a = &b

2 c = a

3 a = &d 4 a = &e

5 b = a

# Constraint

(41)

1 a = &b

2 c = a

3 a = &d 4 a = &e

5 b = a

# Constraint

1 Pa⊇ {b} a b

(42)

1 a = &b

2 c = a

3 a = &d 4 a = &e

5 b = a

# Constraint 1 Pa⊇ {b}

2 Pc⊇Pa

a

c

b

(43)

1 a = &b

2 c = a

3 a = &d 4 a = &e

5 b = a

2 Pc⊇Pa

3 Pa⊇ {d}

a

c

b d

(44)

1 a = &b

2 c = a

3 a = &d 4 a = &e

5 b = a

2 Pc⊇Pa

3 Pa⊇ {d} 4 Pa⊇ {e}

a

c

b d e

(45)

1 a = &b

2 c = a

3 a = &d 4 a = &e

5 b = a

2 Pc⊇Pa

3 Pa⊇ {d} 4 Pa⊇ {e}

5 Pb⊇Pa

a

c

b d e b

(46)

1 a = &b

2 c = a

3 a = &d 4 a = &e

5 b = a

2 Pc⊇Pa

3 Pa⊇ {d} 4 Pa⊇ {e}

5 Pb⊇Pa

a

c

b d

e

(47)

Steensgaard’s Flow Insensitive Points-to Analysis

Equality based analysis:Plhs ≡Prhs

Only one Points-to successor at any time, merge (potential) multiple successors

Program Constraints Points-to Graph 1 a = &b

2 c = a

3 a = &d 4 a = &e 5 b = a

# Constraint

(48)

Program Constraints Points-to Graph 1 a = &b

2 c = a

3 a = &d 4 a = &e 5 b = a

# Constraint 1 P_a⊇ {b}

a b

(49)

1 a = &b 2 c = a

3 a = &d 4 a = &e 5 b = a

2 MERGE(P_c,P_a)

a

c

b

(50)

1 a = &b 2 c = a

3 a = &d 4 a = &e 5 b = a

2 MERGE(P_c,P_a) 3 Pa⊇ {d}

a

c

b d

(51)

1 a = &b 2 c = a

3 a = &d 4 a = &e 5 b = a

4 P_a⊇ {e}

a

c

b d e

(52)

1 a = &b 2 c = a

3 a = &d 4 a = &e 5 b = a

4 P_a⊇ {e}

5 MERGE(P_b,P_a)

a

c

b d e

(53)

1 a = &b 2 c = a

3 a = &d 4 a = &e 5 b = a

4 P_a⊇ {e}

5 MERGE(P_b,P_a)

a

c

b d

e

(54)

Comparing Anderson’s and Steensgaard’s Analyses

Program Subset based Equality based Points-to Graph Points-to Graph a = &b

c = a

a = &d a = &e b = a

a

c

b d

e a

c

b d

e

(55)

a = &b;

(56)

a = &b;

a b

(57)

a = &b;

a b

b = &c;

(58)

a = &b;

a b

b = &c;

a b c

(59)

a = &b;

a b

b = &c;

a b c

d = &e;

(60)

a = &b;

a b

b = &c;

a b c

d = &e;

a b c

d e

(61)

a = &b;

a b

b = &c;

a b c

d = &e;

a b c

d e

a = &d;

(62)

a = &b;

a b

b = &c;

a b c

d = &e;

a b c

d e

a = &d;

Subset based Equality based

a

b c

d e

a b,c d,e

(63)

Pointer Indirection Constraints

Stmt Subset based Equality based a = *b Pa⊇Pc,∀c ∈Pb MERGE(Pa,Pc),∀c∈Pb

*a = b Pc ⊇Pb,∀c ∈Pa MERGE(Pb,Pc),∀c∈Pa

(64)

Must Points-to Analysis

1 x = &a;

2 3

4

x definitelypoints-toaat various points in the program x →^D a

(65)

May Points-to Analysis

1 x = &a;

2 x = &b; 3

4

At OUT of 2,x definitely points-tob At OUT of 3,x definitely points-toa At IN of 4,x possiblypoints-toa(orb)

x →^P a,x →^P b

(66)

May Points-to Analysis

1 x = &a;

2 x = &b; 3

4

At OUT of 2,x definitely points-tob At OUT of 3,x definitely points-toa At IN of 4,x possiblypoints-toa(orb)

x → {a,^P b}

(67)

Must Alias Analysis

1 x =a;

2 3

4 y =a;

x andaalways refer to same memory location x ≡^Da

(68)

Must Alias Analysis

1 x =a;

2 3

4 y =a;

x andaalways refer to same memory location x ≡^Da

x,y andarefer to same location at OUT of 4.

x ≡^Dy ≡^Da

(69)

May Alias Analysis

1 x =a;

2 x =b; 3

4

At OUT of 2,x andbare must aliases At OUT of 3,x andaare must aliases

At IN of 4,x canpossiblybe aliased with eithera(orb) x ≡^Pa,x ≡^Pb

(70)

1 x =a;

2 x =b; 3

4

At IN of 4,x canpossiblybe aliased with eithera(orb) (x,a),(x,b)

(71)

1 x =a;

2 x =b; 3

4

If we say: (x,a,b), Is itPrecise?

(72)

1 x =a;

2 x =b; 3

4

If we say: (x,a,b), Is itPrecise? Safe?

(73)

Must Pointer Analysis

Makes sense only for Flow Sensitive analysis

(74)

Makes sense only for Flow Sensitive analysis Why?

(75)

Must analysis⇒Flow sensitive analysis

(76)

Must analysis⇒Flow sensitive analysis Flow insensitive analysis⇒May analysis

(77)

Must analysis⇒Flow sensitive analysis Flow insensitive analysis⇒May analysis Why?

(78)

Updating Information: When Can WeKill?

Never if flow insensitive analysis

(79)

Never if flow insensitive analysis For flow sensitive

1x= &a;

2 y= &b;

w= &c;

3z= &x; 4z= &y;

5 ∗z=NULL;

∗w=NULL;

(80)

1x= &a;

2 y= &b;

w= &c;

3z= &x; 4z= &y;

5 ∗z=NULL;

∗w=NULL;

x,y may or may not get modified in 5: Weakupdate

(81)

1x= &a;

2 y= &b;

w= &c;

3z= &x; 4z= &y;

5 ∗z=NULL;

∗w=NULL;

x,y may or may not get modified in 5: Weakupdate c definitely gets modified in 5:Strong update

(82)

1x= &a;

2 y= &b;

w= &c;

3z= &x; 4z= &y;

5 ∗z=NULL;

∗w=NULL;

Must information is killed by Strong and Weak updates

(83)

1x= &a;

2 y= &b;

w= &c;

3z= &x; 4z= &y;

5 ∗z=NULL;

∗w=NULL;

Must information is killed by Strong and Weak updates May information is killed only by Strong updates

(84)

Flow Functions for Points-to Analysis

Basic statements for pointer manipulation

(85)

Basic statements for pointer manipulation x = y

(86)

x = &y

(87)

x = &y x = *y

(88)

x = &y x = *y

*x = y

(89)

x = &y x = *y

*x = y

Other statements can be rewritten in terms of above

(90)

x = &y x = *y

*x = y

*x = *y⇒t = *y, *x = t

(91)

x = &y x = *y

*x = y

*x = *y⇒t = *y, *x = t

x = NULL⇒treat NULL as a special variable

(92)

x = &y x = *y

*x = y

*x = *y⇒t = *y, *x = t

x = NULL⇒treat NULL as a special variable OUT =IN−kill∪gen

(93)

x = &y x = *y

*x = y

*x = *y⇒t = *y, *x = t

x = NULL⇒treat NULL as a special variable OUT =IN−kill∪gen

with a twist!

(94)

Flow Function: x = y

May_gen = {x →p|y →p∈May_IN} May_kill = [

p∈Vars

{x →p}

(95)

Flow Function: x = y

May_gen = {x →p|y →p∈May_IN} May_kill = [

p∈Vars

{x →p}

Mustgen = {x →p|y →p∈Must_IN} Mustkill = [

p∈Vars

{x →p}

(96)

Flow Function: x = &y

May_gen = {x →y} May_kill = [

p∈Vars

{x →p}

(97)

Flow Function: x = &y

May_gen = {x →y} May_kill = [

p∈Vars

{x →p}

Mustgen = {x →y}

Mustkill = [

p∈Vars

{x →p}

(98)

Flow Function: x = *y

May_gen = {x →p|y →p^′ ∈May_IN andp^′ →p∈May_IN} May_kill = [

p∈Vars

{x →p}

(99)

Flow Function: x = *y

May_gen = {x →p|y →p^′ ∈May_IN andp^′ →p∈May_IN} May_kill = [

p∈Vars

{x →p}

May_gen = {x →p|y →p^′∈MustIN andp^′ →p∈tin}

May_kill = [

p∈Vars

{x →p}

(100)

Flow Function: *x = y

May_gen = {p→p^′ |x →p∈May_IN,y →p^′∈May_IN} May_kill = [

p^′∈Vars

{p→p^′ |x →p ∈Must_IN}

(101)

May_gen = {p→p^′ |x →p∈May_IN,y →p^′∈May_IN} May_kill = [

p^′∈Vars

{p→p^′ |x →p ∈Must_IN}

Mustgen = {p→p^′ |x →p∈Must_IN,y →p^′ ∈Must_IN} Mustkill = [

p^′∈Vars

{p→p^′ |x →p∈May_IN}

(102)

May_gen = {p→p^′ |x →p∈May_IN,y →p^′ ∈May_IN} May_kill = [

p^′∈Vars

{p→p^′|x →p∈MustIN} Strong update!!

Mustgen = {p→p^′ |x →p∈Must_IN,y →p^′ ∈Must_IN} Mustkill = [

p^′∈Vars

{p→p^′ |x →p∈May_IN} Weak update!!

(103)

Summarizing Flow Functions

May Points-To analysis

(104)

A points-to pair should be removed only if it must be removed along all paths

(105)

⇒should remove only strong updates

(106)

⇒should kill using Must Points-To information

(107)

⇒should kill using Must Points-To information Must Points-To analysis

(108)

A points-to pair should be removed if it can be removed along some path

(109)

⇒should remove all weak updates

(110)

⇒should kill using May Points-To information

(111)

⇒should kill using May Points-To information Must Points-To⊆May Points-To

(112)

Safe Approximations for May and Must Points-to

A pointer variable

May Must

Points-to points to every possible location

points to nothing Alias aliased to every other

pointer variable

only to itself

(113)

Non-Distributivity of Points-to Analysis

May Information Must Information 1

2 x = &z 3y = &w

4 ∗x =y

1 x =a;

2 b= &c

c = &d 3 b = &e e= &d

4 a=∗b

(114)

2 x = &z 3y = &w

4 ∗x =y

1 x =a;

2 b= &c

c = &d 3 b = &e e= &d

4 a=∗b z →w is spurious

(115)

2 x = &z 3y = &w

4 ∗x =y

1 x =a;

2 b= &c

c = &d 3 b = &e e= &d

4 a=∗b z →w is spurious a→d is missing