Liveness Based Pointer Analysis

(1)

Liveness Based Pointer Analysis

Uday Khedker

(Joint Work with Alan Mycroft and Prashant Singh Rawat)

Department of Computer Science and Engineering, Indian Institute of Technology, Bombay

October 2012

(2)

IIT Delhi LFCPA: Outline

Outline

• Introduction

• Background

• Formulating LFCPA

(Liveness basedFlow andContextSensitivePoints-toAnalysis)

• Performing interprocedural analysis

• Measurements

• Conclusions Reference:

Uday P. Khedker, Alan Mycroft, Prashant Singh Rawat. Liveness Based Pointer Anaysis. SAS 2012.

(3)

Part 1 Introduction

(4)

IIT Delhi LFCPA: Introduction

Why Pointer Analysis?

• Pointer analysis collects information about indirect accesses in programs

◮ Enables precise data analysis

◮ Enable precise interprocedural control flow analysis

• Needs to scale to large programs for practical usefulness

• Good pointer information could improve many applications of program analysis significantly

(5)

Pointer Analysis Musings

• Two Position Papers

• A Keynote Address

(6)

Pointer Analysis Musings

◮ Which Pointer Analysis should I Use?

Michael Hind and Anthony Pioli, ISTAA 2000

◮ Pointer Analysis: Haven’t we solved this problem yet?

Michael Hind, PASTE 2001

(7)

Pointer Analysis Musings

Michael Hind and Anthony Pioli, ISTAA 2000

◮ Pointer Analysis: Haven’t we solved this problem yet?

Michael Hind, PASTE 2001

◮ “The Worst thing that has happened to Computer Science is C because it brought pointers with it”

Frances Allen, IITK Workshop, 2007

(8)

Pointer Analysis Musings

Michael Hind and Anthony Pioli, ISTAA2000

◮ Pointer Analysis: Haven’t we solved this problemyet?

Michael Hind, PASTE2001

◮ “The Worst thing that has happened to Computer Science is C because it brought pointers with it”

Frances Allen, IITK Workshop,2007

• 2012 . . .

(9)

The Mathematics of Pointer Analysis

In the most general situation

• Alias analysis is undecidable.

Landi-Ryder [POPL 1991], Landi [LOPLAS 1992], Ramalingam [TOPLAS 1994]

• Flow insensitive alias analysis is NP-hard Horwitz [TOPLAS 1997]

• Points-to analysis is undecidable Chakravarty [POPL 2003]

(10)

The Mathematics of Pointer Analysis

In the most general situation

• Alias analysis is undecidable.

Landi-Ryder [POPL 1991], Landi [LOPLAS 1992], Ramalingam [TOPLAS 1994]

• Flow insensitive alias analysis is NP-hard Horwitz [TOPLAS 1997]

• Points-to analysis is undecidable Chakravarty [POPL 2003]

Adjust your expectations suitably to avoid disappointments!

(11)

The Engineering of Pointer Analysis

So what should we expect?

(12)

The Engineering of Pointer Analysis

So what should we expect? To quote Hind [PASTE 2001]

(13)

The Engineering of Pointer Analysis

• “Fortunately many approximations exist”

(14)

The Engineering of Pointer Analysis

• “Unfortunately too manyapproximations exist!”

(15)

The Engineering of Pointer Analysis

• “Unfortunately too manyapproximations exist!”

Engineering of pointer analysis is much more dominant than its science

(16)

Pointer Analysis: Engineering or Science?

• Engineering view

• Science view

(17)

Pointer Analysis: Engineering or Science?

◮ Build quickapproximations

◮ The tyranny of (exclusive) OR!

Precision OR Efficiency?

• Science view

(18)

Pointer Analysis: Engineering or Science?

◮ Build quickapproximations

◮ The tyranny of (exclusive) OR!

Precision OR Efficiency?

• Science view

◮ Build cleanabstractions

◮ Can we harness the Genius of AND?

Precision AND Efficiency?

(19)

The Scope of Our Points-to Analysis

Attribute Range of Options Our Scope

Categories of data pointers

Static (Globals) Stack (Locals, Formals) Heap

Static (Globals) Stack (Locals, Formals)

Level Intraprocedural,

Interprocedural Interprocedural Flow Sensitivity Full, Partial, None Full

Context Sensitivity Full, Partial, None Full

• Heap and address escaping locals are handled conservatively

• Data flow information is safe but may be imprecise

(20)

Part 2 Background

(21)

IIT Delhi

An Example of Flow Insensitive Points-to Analysis (Andersen’s Approach aka Inclusion Based Approach)

n1

x= &y y = &z z = &u

n1

n2 ∗z =y n2 n3 z =y n3

n4

y= &x use u use x

n4

(22)

IIT Delhi

An Example of Flow Insensitive Points-to Analysis (Andersen’s Approach aka Inclusion Based Approach)

n1

x= &y y = &z z = &u

n1

n2 ∗z =y n2 n3 z =y n3

n4

y= &x use u use x

n4

x

Points-to Graph

y z u

• x “points-to” y

• y “points-to” z

• z “points-to” u

Constraints on Points-to Sets

Px ⊇ {y} Py ⊇ {z} Pz ⊇ {u}

(23)

IIT Delhi

An Example of Flow Insensitive Points-to Analysis (Andersen’s Approach aka Inclusion Based Approach)

n1

x= &y y = &z z = &u

n1

n2 ∗z =y n2 n3 z =y n3

n4

y= &x use u use x

n4

x

Points-to Graph

y z u

• Pointees of z should point to pointees of y also

• u should point to z

Px ⊇ {y} Py ⊇ {z} Pz ⊇ {u}

∀w ∈Pz, Pw ⊇Py

(24)

IIT Delhi

An Example of Flow Insensitive Points-to Analysis (Andersen’s Approach aka Inclusion Based Approach)

n1

x= &y y = &z z = &u

n1

n2 ∗z =y n2 n3 z =y n3

n4

y= &x use u use x

n4

x

Points-to Graph

y z u

Px ⊇ {y} Py ⊇ {z} Pz ⊇ {u}

(25)

IIT Delhi

An Example of Flow Insensitive Points-to Analysis (Andersen’s Approach aka Inclusion Based Approach)

n1

x= &y y = &z z = &u

n1

n2 ∗z =y n2 n3 z =y n3

n4

y= &x use u use x

n4

x

Points-to Graph

y z u

• z should point to pointees of y

• z should point to z

Px ⊇ {y} Py ⊇ {z} Pz ⊇ {u}

Pz ⊇Py

(26)

IIT Delhi

An Example of Flow Insensitive Points-to Analysis (Andersen’s Approach aka Inclusion Based Approach)

n1

x= &y y = &z z = &u

n1

n2 ∗z =y n2 n3 z =y n3

n4

y= &x use u use x

n4

x

Points-to Graph

y z u

Px ⊇ {y} Py ⊇ {z} Pz ⊇ {u}

Pz ⊇Py

(27)

IIT Delhi

An Example of Flow Insensitive Points-to Analysis (Andersen’s Approach aka Inclusion Based Approach)

n1

x= &y y = &z z = &u

n1

n2 ∗z =y n2 n3 z =y n3

n4

y= &x use u use x

n4

x

Points-to Graph

y z u

• y should point to x also

Px ⊇ {y} Py ⊇ {z} Pz ⊇ {u}

Pz ⊇Py

Py ⊇ {x}

(28)

IIT Delhi

An Example of Flow Insensitive Points-to Analysis (Andersen’s Approach aka Inclusion Based Approach)

n1

x= &y y = &z z = &u

n1

n2 ∗z =y n2 n3 z =y n3

n4

y= &x use u use x

n4

x

Points-to Graph

y z u

Px ⊇ {y} Py ⊇ {z} Pz ⊇ {u}

Pz ⊇Py

Py ⊇ {x}

(29)

IIT Delhi

An Example of Flow Insensitive Points-to Analysis (Andersen’s Approach aka Inclusion Based Approach)

n1

x= &y y = &z z = &u

n1

n2 ∗z =y n2 n3 z =y n3

n4

y= &x use u use x

n4

x

Points-to Graph

y z u

• z and its pointees should point to new pointee of y also

• u and z should point to x

Px ⊇ {y} Py ⊇ {z} Pz ⊇ {u}

Pz ⊇Py

Py ⊇ {x}

(30)

IIT Delhi

An Example of Flow Insensitive Points-to Analysis (Andersen’s Approach aka Inclusion Based Approach)

n1

x= &y y = &z z = &u

n1

n2 ∗z =y n2 n3 z =y n3

n4

y= &x use u use x

n4

x

Points-to Graph

y z u

Px ⊇ {y} Py ⊇ {z} Pz ⊇ {u}

Pz ⊇Py

Py ⊇ {x}

(31)

IIT Delhi

An Example of Flow Insensitive Points-to Analysis (Andersen’s Approach aka Inclusion Based Approach)

n1

x= &y y = &z z = &u

n1

n2 ∗z =y n2 n3 z =y n3

n4

y= &x use u use x

n4

x

Points-to Graph

y z u

• Pointees of z should point to pointees of y

• x should point to itself and z

Px ⊇ {y} Py ⊇ {z} Pz ⊇ {u}

Pz ⊇Py

Py ⊇ {x}

(32)

IIT Delhi

An Example of Flow Insensitive Points-to Analysis (Andersen’s Approach aka Inclusion Based Approach)

n1

x= &y y = &z z = &u

n1

n2 ∗z =y n2 n3 z =y n3

n4

y= &x use u use x

n4

x

Points-to Graph

y z u

Px ⊇ {y} Py ⊇ {z} Pz ⊇ {u}

Pz ⊇Py

Py ⊇ {x}

(33)

IIT Delhi

An Example of Flow Insensitive Points-to Analysis (Steensgaard’s Approach aka Equality Based Approach)

n1

x= &y y = &z z = &u

n1

n2 ∗z =y n2 n3 z =y n3

n4

y= &x use u use x

n4

• Treat all pointees of a pointer as “equivalent”

locations

• Transitive closure Pointees of all equivalent locations become equivalent

(34)

IIT Delhi

An Example of Flow Insensitive Points-to Analysis (Steensgaard’s Approach aka Equality Based Approach)

n1

x= &y y = &z z = &u

n1

n2 ∗z =y n2 n3 z =y n3

n4

y= &x use u use x

n4

Andersen’s Points-to Graph

x y z u

locations

Effective additional constraints

Unify(x,y) (pointees ofx) Unify(x,z)

(pointees ofy) Unify(x,u)

(pointees ofz)

(35)

IIT Delhi

An Example of Flow Insensitive Points-to Analysis (Steensgaard’s Approach aka Equality Based Approach)

n1

x= &y y = &z z = &u

n1

n2 ∗z =y n2 n3 z =y n3

n4

y= &x use u use x

n4

Andersen’s Points-to Graph

x y z u

locations

(pointees ofz)

⇒x,y,z,uare equivalent

(36)

IIT Delhi

An Example of Flow Insensitive Points-to Analysis (Steensgaard’s Approach aka Equality Based Approach)

n1

x= &y y = &z z = &u

n1

n2 ∗z =y n2 n3 z =y n3

n4

y= &x use u use x

n4

Steensgaard’s Points-to Graph

x y

z u

locations

(pointees ofz)

⇒x,y,z,uare equivalent

⇒Complete graph

(37)

IIT Delhi

An Example of Flow Sensitive Points-to Analysis

n1

x = &y y= &z z = &u

n1

n2 ∗z =y n2 n3 z =y n3

n4

y= &x use u use x

n4

(38)

IIT Delhi

An Example of Flow Sensitive Points-to Analysis

n1

x = &y y= &z z = &u

n1

n2 ∗z =y n2 n3 z =y n3

n4

y= &x use u use x

n4

∅

(39)

IIT Delhi

An Example of Flow Sensitive Points-to Analysis

n1

x = &y y= &z z = &u

n1

n2 ∗z =y n2 n3 z =y n3

n4

y= &x use u use x

n4

∅

x y z u

(40)

IIT Delhi

An Example of Flow Sensitive Points-to Analysis

n1

x = &y y= &z z = &u

n1

n2 ∗z =y n2 n3 z =y n3

n4

y= &x use u use x

n4

∅

x y z u

(41)

IIT Delhi

An Example of Flow Sensitive Points-to Analysis

n1

x = &y y= &z z = &u

n1

n2 ∗z =y n2 n3 z =y n3

n4

y= &x use u use x

n4

∅

x y z u

x y z u x y z u

(42)

IIT Delhi

An Example of Flow Sensitive Points-to Analysis

n1

x = &y y= &z z = &u

n1

n2 ∗z =y n2 n3 z =y n3

n4

y= &x use u use x

n4

∅

x y z u

x y z u x y z u

x y z u

(43)

IIT Delhi

An Example of Flow Sensitive Points-to Analysis

n1

x = &y y= &z z = &u

n1

n2 ∗z =y n2 n3 z =y n3

n4

y= &x use u use x

n4

∅

x y z u

x y z u x y z u

x y z u x y z

(44)

IIT Delhi

An Example of Flow Sensitive Points-to Analysis

n1

x = &y y= &z z = &u

n1

n2 ∗z =y n2 n3 z =y n3

n4

y= &x use u use x

n4

∅

x y z u

x y z u x y z u

x y z u x y z

x y z u

(45)

IIT Delhi

An Example of Flow Sensitive Points-to Analysis

n1

x = &y y= &z z = &u

n1

n2 ∗z =y n2 n3 z =y n3

n4

y= &x use u use x

n4

∅

x y z u

x y z u x y z u

x y z u x y z

x y z u

(46)

IIT Delhi

Flow Sensitive Points-to Analysis: May and Must Variants

a= &b b= &e 1

c= &a

2 3 c= &d

∗c= &d

∗a= &e 4

∗c=e 5

(47)

IIT Delhi

Flow Sensitive Points-to Analysis: May and Must Variants

a= &b b= &e 1

c= &a

2 3 c= &d

∗c= &d

∗a= &e 4

∗c=e 5

• c a b e at the entry of 4

(48)

IIT Delhi

Flow Sensitive Points-to Analysis: May and Must Variants

a= &b b= &e 1

c= &a

2 3 c= &d

∗c= &d

∗a= &e 4

∗c=e 5

• Should a b be killed by assignment

∗c= &d?

(49)

IIT Delhi

Flow Sensitive Points-to Analysis: May and Must Variants

a= &b b= &e 1

c= &a

2 3 c= &d

∗c= &d

∗a= &e 4

∗c=e 5

∗c= &d?

No because c points to a along path 1,2,4 but not along path 1,3,4

(50)

IIT Delhi

Flow Sensitive Points-to Analysis: May and Must Variants

a= &b b= &e 1

c= &a

2 3 c= &d

∗c= &d

∗a= &e 4

∗c=e 5

• c ^MAY a b e at the entry of 4

∗c= &d?

(51)

IIT Delhi

Flow Sensitive Points-to Analysis: May and Must Variants

a= &b b= &e 1

c= &a

2 3 c= &d

∗c= &d

∗a= &e 4

∗c=e 5

• c ^MAY a b e at the entry of 4

∗c= &d?

• Should b e be killed by assignment

∗a= &e?

(52)

IIT Delhi

Flow Sensitive Points-to Analysis: May and Must Variants

a= &b b= &e 1

c= &a

2 3 c= &d

∗c= &d

∗a= &e 4

∗c=e 5

• c ^MAY a^MUSTb e at the entry of 4

∗c= &d?

∗a= &e?

Yes because a points to b along both the paths

(53)

IIT Delhi

Flow Sensitive Points-to Analysis: May and Must Variants

a= &b b= &e 1

c= &a

2 3 c= &d

∗c= &d

∗a= &e 4

∗c=e 5

• c ^MAY a^MUSTb e at the entry of 4

∗c= &d?

∗a= &e?

Yes because a points to b along both the paths

• Must points-to information is required for killing May points-to information

(and vice-versa)

(54)

IIT Delhi

Context Sensitivity in Interprocedural Analysis

Startr

Endr

Starts

a= &b

Ends

Ci

Ri

ci

Startt

c = &d

Endt

Cj

Rj

cj

fr

(55)

IIT Delhi

Context Sensitivity in Interprocedural Analysis

Startr

Endr

Starts

a= &b

Ends

Ci

Ri

ci

Startt

c = &d

Endt

Cj

Rj

cj

fr

a b

(56)

IIT Delhi

Context Sensitivity in Interprocedural Analysis

Startr

Endr

Starts

a= &b

Ends

Ci

Ri

ci

Startt

c = &d

Endt

Cj

Rj

cj

fr

a b

(57)

IIT Delhi

Context Sensitivity in Interprocedural Analysis

Startr

Endr

Starts

a= &b

Ends

Ci

Ri

ci

Startt

c = &d

Endt

Cj

Rj

cj

fr

a b

c d

(58)

IIT Delhi

Context Sensitivity in Interprocedural Analysis

Startr

Endr

Starts

a= &b

Ends

Ci

Ri

ci

Startt

c = &d

Endt

Cj

Rj

cj

fr

a b

c d

(59)

IIT Delhi

Context Sensitivity in Interprocedural Analysis

Startr

Endr

Starts

a= &b

Ends

Ci

Ri

ci

Startt

c = &d

Endt

Cj

Rj

cj

fr

a b

c d

(60)

IIT Delhi

Context Sensitivity in Interprocedural Analysis

Startr

Endr

Starts

a= &b

Ends

Ci

Ri

ci

Startt

c = &d

Endt

Cj

Rj

cj

fr

a b

c d

a b

×

(61)

IIT Delhi

Context Sensitivity in Interprocedural Analysis

Startr

Endr

Starts

a= &b

Ends

Ci

Ri

ci

Startt

c = &d

Endt

Cj

Rj

cj

fr

a b

c d

(62)

IIT Delhi

Context Sensitivity in Interprocedural Analysis

Startr

Endr

Starts

a= &b

Ends

Ci

Ri

ci

Startt

c = &d

Endt

Cj

Rj

cj

fr

a b

c d

× ^×

(63)

IIT Delhi

Context Sensitivity in Interprocedural Analysis

Startr

Endr

Starts

a= &b

Ends

Ci

Ri

ci

Startt

c = &d

Endt

Cj

Rj

cj

fr

a b

c d

a b c d

(64)

IIT Delhi

Context Sensitivity in the Presence of Recursion

Starts

Ci

Ri

Ends

call (c)

return (r) calling (s)stop

(65)

IIT Delhi

Context Sensitivity in the Presence of Recursion

Starts

Ci

Ri

Ends

call (c)

• Paths from Starts toEnds should constitute a context free languagecⁿsrⁿ

(66)

IIT Delhi

Context Sensitivity in the Presence of Recursion

Starts

Ci

Ri

Ends

call (c)

• Many interprocedural analyses treat cycle of recursion as an SCC and approximate paths by a regular language c^∗sr^∗

(67)

IIT Delhi

Context Sensitivity in the Presence of Recursion

Starts

Ci

Ri

Ends

call (c)

• We do not know any practical points-to analysis that is fully context sensitive Most context sensitive approaches

(68)

IIT Delhi

Context Sensitivity in the Presence of Recursion

Starts

Ci

Ri

Ends

call (c)

◮ eitherdo not consider recursion, or

(69)

IIT Delhi

Context Sensitivity in the Presence of Recursion

Starts

Ci

Ri

Ends

call (c)

◮ either do not consider recursion, or

◮ do not consider recursive pointer manipulation(e.g. “p=∗p”), or

(70)

IIT Delhi

Context Sensitivity in the Presence of Recursion

Starts

Ci

Ri

Ends

call (c)

◮ either do not consider recursion, or

◮ do not consider recursive pointer manipulation (e.g. “p=∗p”), or

◮ arecontext insensitive in recursion

(71)

IIT Delhi

Pointer Analysis: An Engineer’s Landscape

FlowSensitivity Increases

Context Sensitivity FI=

FFS

CI FCS

(72)

IIT Delhi

Pointer Analysis: An Engineer’s Landscape

Context Sensitivity

CI FCS

FI=

FI⊆

FISSA

FSNoKill

FFS

(73)

IIT Delhi

Pointer Analysis: An Engineer’s Landscape

FI⊆

FISSA

FSNoKill

FFS

CI CIOS CSK-lim CSRI FCS

(74)

IIT Delhi

Pointer Analysis: An Engineer’s Landscape

FI⊆

FISSA

FSNoKill

FFS

Data Structures: BDDs, probabilistic

(75)

IIT Delhi

Pointer Analysis: An Engineer’s Landscape

FI⊆

FISSA

FSNoKill

FFS

Methods: parallel, on demand, randomized

(76)

IIT Delhi

Pointer Analysis: An Engineer’s Landscape

FI⊆

FISSA

FSNoKill

FFS

Methods: parallel, on demand, randomized Refinement: Levelwise, bootstrapping

(77)

IIT Delhi

Pointer Analysis: An Engineer’s Landscape

FI⊆

FISSA

FSNoKill

FFS

Over Crowed Area

(78)

IIT Delhi

Pointer Analysis: An Engineer’s Landscape

FI⊆

FISSA

FSNoKill

FFS

Over Crowed Area

Still Vacant Data Structures: BDDs, probabilistic

(79)

IIT Delhi

Pointer Analysis: An Engineer’s Landscape

FI⊆

FISSA

FSNoKill

FFS

Over Crowed Area

Still Vacant Data Structures: BDDs, probabilistic

That’s the corner we are trying to

occupy :-)

(80)

Part 3 Formulating LFCPA

(81)

IIT Delhi

Our Motivating Example for Intraprocedural Formulation

n1

x = &y y= &z z = &u

n1

n2 ∗z =y n2 n3 z =y n3

n4

y= &x use u use x

n4

∅

x y z u

x y z u x y z u

x y z u x y z

x y z u

(82)

IIT Delhi

yIs All This Information Useful?y

n1

x = &y y= &z z = &u

n1

n2 ∗z =y n2 n3 z =y n3

n4

y= &x use u use x

n4

∅

x y z u

x y z

x y z u

(83)

IIT Delhi

yIs All This Information Useful?y

n1

x = &y y= &z z = &u

n1

n2 ∗z =y n2 n3 z =y n3

n4

y= &x use u use x

n4

∅

x y z u

x y z

x y z u

(84)

IIT Delhi

yIs All This Information Useful?y

n1

x = &y y= &z z = &u

n1

n2 ∗z =y n2 n3 z =y n3

n4

y= &x use u use x

n4

∅

x y z u

x y z

x y z u

(85)

IIT Delhi

yIs All This Information Useful?y

n1

x = &y y= &z z = &u

n1

n2 ∗z =y n2 n3 z =y n3

n4

y= &x use u use x

n4

∅

x y z u

x y z

x y z u

(86)

IIT Delhi

yIs All This Information Useful?y

n1

x = &y y= &z z = &u

n1

n2 ∗z =y n2 n3 z =y n3

n4

y= &x use u use x

n4

∅

x y z u

x y z

x y z u

(87)

IIT Delhi

yIs All This Information Useful?y

n1

x = &y y= &z z = &u

n1

n2 ∗z =y n2 n3 z =y n3

n4

y= &x use u use x

n4

∅

x y z u

x y z

x y z u

(88)

IIT Delhi

The L and P of LFCPA

Mutual dependence of liveness and points-to information

• Define points-to information only for live pointers

• For pointer indirections, define liveness information using points-to information

(89)

IIT Delhi

The F and C of LFCPA

• Use call strings method for full flow and context sensitivity

• Use value based termination of call strings construction for efficiency [Khedker, Karkare. CC 2008]

(90)

IIT Delhi

Use of Strong Liveness

• Simple liveness considers every use of a variable as useful

• Strong liveness checks the liveness of the result before declaring the operands to be live

(91)

IIT Delhi

Use of Strong Liveness

• Simple liveness considers every use of a variable as useful

• Strong liveness checks the liveness of the result before declaring the operands to be live

• Strong liveness is more precise than simple liveness

(92)

IIT Delhi

Data Flow Equations

Lout

n

=







∅

n is End

_p [

s∈succ(n)

Lin

s

otherwise

Lin

n

=

Lout

n−

Kill

n

∪

Ref

n

Ain

n

=











Lin

_n×{?}

n is Start

_p



 [

p∈pred(n)

Aout

_p





Lin

_n

otherwise

Aout

_n

=

Ain

_n−

Kill

_n ×V

∪

Def

_n ×

Pointee

_n

Lout

_n

•

Lin/Lout: set of Live pointers, Ain/Aout : sets of mAy points-to pairs

(93)

IIT Delhi

Data Flow Equations

Lout

n

=







∅

n is End

_p [

s∈succ(n)

Lin

s

otherwise

Lin

n

=

Lout

n−

Kill

n

∪

Ref

n

Ain

n

=











Lin

_n×{?}

n is Start

_p



 [

p∈pred(n)

Aout

_p





Lin

_n

otherwise

Aout

_n

=

Ain

_n−

Kill

_n ×V

∪

Def

_n ×

Pointee

_n

Lout

_n

•

Lin/Lout: set of Live pointers, Ain/Aout : sets of mAy points-to pairs

(94)

IIT Delhi

Data Flow Equations

Lout

n

=







∅

n is End

_p [

s∈succ(n)

Lin

s

otherwise

Lin

n

=

Lout

n−

Kill

n

∪

Ref

n

Ain

n

=











Lin

_n×{?}

n is Start

_p



 [

p∈pred(n)

Aout

_p





Lin

_n

otherwise

Aout

_n

=

Ain

_n−

Kill

_n ×V

∪

Def

_n ×

Pointee

_n

Lout

_n

•

Lin/Lout: set of Live pointers, Ain/Aout : sets of mAy points-to pairs Ref

_n

is

defined in terms

of Lout

_n

(95)

IIT Delhi

Data Flow Equations

Lout

n

=







∅

n is End

_p [

s∈succ(n)

Lin

s

otherwise

Lin

n

=

Lout

n−

Kill

n

∪

Ref

n

Ain

n

=











Lin

_n×{?}

n is Start

_p



 [

p∈pred(n)

Aout

_p





Lin

_n

otherwise

Aout

_n

=

Ain

_n−

Kill

_n ×V

∪

Def

_n ×

Pointee

_n

Lout

_n

•

Lin/Lout: set of Live pointers, Ain/Aout : sets of mAy points-to pairs

Ain

_n

and Aout

_n

are restricted to

Lin

_n

and Lout

_n

(96)

IIT Delhi

Data Flow Equations

Lout

n

=







∅

n is End

_p [

s∈succ(n)

Lin

s

otherwise

Lin

n

=

Lout

n−

Kill

n

∪

Ref

n

Ain

n

=











Lin

_n×{?}

n is Start

_p



 [

p∈pred(n)

Aout

_p





Lin

_n

otherwise

Aout

_n

=

Ain

_n−

Kill

_n ×V

∪

Def

_n ×

Pointee

_n

Lout

_n

•

Lin/Lout: set of Live pointers, Ain/Aout : sets of mAy points-to pairs

(97)

IIT Delhi

Motivating Example Revisited

•

For convenience, we show complete sweeps of liveness and points-to analysis repeatedly

•

This is not required by the computation

•

The data flow equations define a single fixed point computation

(98)

IIT Delhi

First Round of Liveness Analysis and Points-to Analysis

n1

x = &y y= &z z = &u

n1

n2 ∗z =y n2n3 z =y n3

n4

y= &x use u use x

n4

(99)

IIT Delhi

First Round of Liveness Analysis and Points-to Analysis

n1

x = &y y= &z z = &u

n1

n2 ∗z =y n2n3 z =y n3

n4

y= &x use u use x

n4

LivenessAnalysis

(100)

IIT Delhi

First Round of Liveness Analysis and Points-to Analysis

n1

x = &y y= &z z = &u

n1

n2 ∗z =y n2n3 z =y n3

n4

y= &x use u use x

n4

LivenessAnalysis

{u,x}

(101)

IIT Delhi

First Round of Liveness Analysis and Points-to Analysis

n1

x = &y y= &z z = &u

n1

n2 ∗z =y n2n3 z =y n3

n4

y= &x use u use x

n4

LivenessAnalysis

{u,x}

(102)

IIT Delhi

First Round of Liveness Analysis and Points-to Analysis

n1

x = &y y= &z z = &u

n1

n2 ∗z =y n2n3 z =y n3

n4

y= &x use u use x

n4

LivenessAnalysis

{u,x}

{z} {u,x}

(103)

IIT Delhi

First Round of Liveness Analysis and Points-to Analysis

n1

x = &y y= &z z = &u

n1

n2 ∗z =y n2n3 z =y n3

n4

y= &x use u use x

n4

LivenessAnalysis

{u,x}

{z} {u,x}

Strong liveness:

y is not made live because z is not live

(104)

IIT Delhi

First Round of Liveness Analysis and Points-to Analysis

n1

x = &y y= &z z = &u

n1

n2 ∗z =y n2n3 z =y n3

n4

y= &x use u use x

n4

LivenessAnalysis

{u,x}

{z} {u,x}

{u,x,z}

(105)

IIT Delhi

First Round of Liveness Analysis and Points-to Analysis

n1

x = &y y= &z z = &u

n1

n2 ∗z =y n2n3 z =y n3

n4

y= &x use u use x

n4

LivenessAnalysis

{u,x}

{z} {u,x}

{u,x,z} {u}

(106)

IIT Delhi

First Round of Liveness Analysis and Points-to Analysis

n1

x = &y y= &z z = &u

n1

n2 ∗z =y n2n3 z =y n3

n4

y= &x use u use x

n4

Points-toAnalysis

{u,x}

{z} {u,x}

{u,x,z} {u}

(107)

IIT Delhi

First Round of Liveness Analysis and Points-to Analysis

n1

x = &y y= &z z = &u

n1

n2 ∗z =y n2n3 z =y n3

n4

y= &x use u use x

n4

Points-toAnalysis

{u,x}

{z} {u,x}

{u,x,z} {u} u ?

(108)

IIT Delhi

First Round of Liveness Analysis and Points-to Analysis

n1

x = &y y= &z z = &u

n1

n2 ∗z =y n2n3 z =y n3

n4

y= &x use u use x

n4

Points-toAnalysis

{u,x}

{z} {u,x}

{u,x,z} {u} u ?

x y z u ?

(109)

IIT Delhi

First Round of Liveness Analysis and Points-to Analysis

n1

x = &y y= &z z = &u

n1

n2 ∗z =y n2n3 z =y n3

n4

y= &x use u use x

n4

Points-toAnalysis

{u,x}

{z} {u,x}

{u,x,z} {u} u ?

x y z u ?

x y u ?

(110)

IIT Delhi

First Round of Liveness Analysis and Points-to Analysis

n1

x = &y y= &z z = &u

n1

n2 ∗z =y n2n3 z =y n3

n4

y= &x use u use x

n4

Points-toAnalysis

{u,x}

{z} {u,x}

{u,x,z} {u} u ?

x y z u ?

x y u ?

(111)

IIT Delhi

First Round of Liveness Analysis and Points-to Analysis

n1

x = &y y= &z z = &u

n1

n2 ∗z =y n2n3 z =y n3

n4

y= &x use u use x

n4

Points-toAnalysis

{u,x}

{z} {u,x}

{u,x,z} {u} u ?

x y z u ?

x y u ?

z u

(112)

IIT Delhi

First Round of Liveness Analysis and Points-to Analysis

n1

x = &y y= &z z = &u

n1

n2 ∗z =y n2n3 z =y n3

n4

y= &x use u use x

n4

Points-toAnalysis

{u,x}

{z} {u,x}

{u,x,z} {u} u ?

x y z u ?

x y u ?

z u

??

(113)

IIT Delhi

First Round of Liveness Analysis and Points-to Analysis

n1

x = &y y= &z z = &u

n1

n2 ∗z =y n2n3 z =y n3

n4

y= &x use u use x

n4

Points-toAnalysis

{u,x}

{z} {u,x}

{u,x,z} {u} u ?

x y z u ?

x y u ?

z u

??

x y u ?

(114)

IIT Delhi

Second Round of Liveness Analysis and Points-to Analysis

n1

x = &y y= &z z = &u

n1

n2 ∗z =y n2n3 z =y n3

n4

y= &x use u use x

n4

{u,x}

{u} u ?

x y u ?

{z}

z u

{u,x,z} x y z u ?

x y u ?

(115)

IIT Delhi

Second Round of Liveness Analysis and Points-to Analysis

n1

x = &y y= &z z = &u

n1

n2 ∗z =y n2n3 z =y n3

n4

y= &x use u use x

n4

LivenessAnalysis

{u,x}

{u} u ?

x y u ?

{x,y,z}

{u,x,z} x y z u ?

z u

x y u ?

(116)

IIT Delhi

Second Round of Liveness Analysis and Points-to Analysis

n1

x = &y y= &z z = &u

n1

n2 ∗z =y n2n3 z =y n3

n4

y= &x use u use x

n4

LivenessAnalysis

{u,x}

{u} u ?

x y u ?

{x,y,z}

{u,x,y,z} x y z u ?

z u

x y u ?

(117)

IIT Delhi

Second Round of Liveness Analysis and Points-to Analysis

n1

x = &y y= &z z = &u

n1

n2 ∗z =y n2n3 z =y n3

n4

y= &x use u use x

n4

Points-toAnalysis

{u,x}

{u} u ?

x y u ?

{x,y,z}

{u,x,y,z} x y z u ?

z u

x y u ?

(118)

IIT Delhi

Second Round of Liveness Analysis and Points-to Analysis

n1

x = &y y= &z z = &u

n1

n2 ∗z =y n2n3 z =y n3

n4

y= &x use u use x

n4

Points-toAnalysis

{u,x}

{u} u ?

x y u ?

{x,y,z}

{u,x,y,z} x y z u ?

x y z u

x y u ?

(119)

IIT Delhi

Second Round of Liveness Analysis and Points-to Analysis

n1

x = &y y= &z z = &u

n1

n2 ∗z =y n2n3 z =y n3

n4

y= &x use u use x

n4

Points-toAnalysis

{u,x}

{u} u ?

x y u ?

{x,y,z}

{u,x,y,z} x y z u ?

x y z u

x y u ?

(120)

IIT Delhi

Second Round of Liveness Analysis and Points-to Analysis

n1

x = &y y= &z z = &u

n1

n2 ∗z =y n2n3 z =y n3

n4

y= &x use u use x

n4

Points-toAnalysis

{u,x}

{u} u ?

x y u ?

{x,y,z}

{u,x,y,z} x y z u ?

x y z u

x y z u ?

(121)

IIT Delhi

Discovering Must Points-to Information from May Points-to Information

a= &b b= &e 1

c= &a

2 3 c= &d

∗c= &d

∗a= &e 4

∗c=e 5

(122)

IIT Delhi

Discovering Must Points-to Information from May Points-to Information

a= &b b= &e 1

c= &a

2 3 c= &d

∗c= &d

∗a= &e 4

∗c=e 5

• c is live at program entry

(123)

IIT Delhi

Discovering Must Points-to Information from May Points-to Information

a= &b b= &e 1

c= &a

2 3 c= &d

∗c= &d

∗a= &e 4

∗c=e 5

c ?

• Assume that c points to “?” at program entry

(124)

IIT Delhi

Discovering Must Points-to Information from May Points-to Information

a= &b b= &e 1

c= &a

2 3 c= &d

∗c= &d

∗a= &e 4

∗c=e 5

c ?

a b e • c is live at program entry

• Perform usual may points-to analysis

(125)

IIT Delhi

Discovering Must Points-to Information from May Points-to Information

a= &b b= &e 1

c= &a

2 3 c= &d

∗c= &d

∗a= &e 4

∗c=e 5

c ?

a b e

c ?

a b e • c is live at program entry

(126)

IIT Delhi

Discovering Must Points-to Information from May Points-to Information

a= &b b= &e 1

c= &a

2 3 c= &d

∗c= &d

∗a= &e 4

∗c=e 5

c ?

a b e

c ?

a b e

c a b e

?

(127)

IIT Delhi

Discovering Must Points-to Information from May Points-to Information

a= &b b= &e 1

c= &a

2 3 c= &d

∗c= &d

∗a= &e 4

∗c=e 5

c ?

a b e

c ?

a b e

c a b e

?

• Since c has multiple pointees, it is a MAY relation

Liveness Based Pointer Analysis