### 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

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.

### Part 1

### Introduction

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

IIT Delhi LFCPA: Introduction

### Pointer Analysis Musings

• Two Position Papers

• A Keynote Address

IIT Delhi LFCPA: Introduction

### Pointer Analysis Musings

• Two Position Papers

◮ 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

• A Keynote Address

IIT Delhi LFCPA: Introduction

### Pointer Analysis Musings

• Two Position Papers

◮ 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

• A Keynote Address

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

Frances Allen, IITK Workshop, 2007

IIT Delhi LFCPA: Introduction

### Pointer Analysis Musings

• Two Position Papers

◮ Which Pointer Analysis should I Use?

Michael Hind and Anthony Pioli, ISTAA2000

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

Michael Hind, PASTE2001

• A Keynote Address

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

Frances Allen, IITK Workshop,2007

• 2012 . . .

IIT Delhi LFCPA: Introduction

### 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]

IIT Delhi LFCPA: Introduction

### 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!

IIT Delhi LFCPA: Introduction

### The Engineering of Pointer Analysis

So what should we expect?

IIT Delhi LFCPA: Introduction

### The Engineering of Pointer Analysis

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

IIT Delhi LFCPA: Introduction

### The Engineering of Pointer Analysis

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

• “Fortunately many approximations exist”

IIT Delhi LFCPA: Introduction

### The Engineering of Pointer Analysis

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

• “Fortunately many approximations exist”

• “Unfortunately too manyapproximations exist!”

IIT Delhi LFCPA: Introduction

### The Engineering of Pointer Analysis

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

• “Fortunately many approximations exist”

• “Unfortunately too manyapproximations exist!”

Engineering of pointer analysis is much more dominant than its science

IIT Delhi LFCPA: Introduction

### Pointer Analysis: Engineering or Science?

• Engineering view

• Science view

IIT Delhi LFCPA: Introduction

### Pointer Analysis: Engineering or Science?

• Engineering view

◮ Build quickapproximations

◮ The tyranny of (exclusive) OR!

Precision OR Efficiency?

• Science view

IIT Delhi LFCPA: Introduction

### Pointer Analysis: Engineering or Science?

• Engineering view

◮ Build quickapproximations

◮ The tyranny of (exclusive) OR!

Precision OR Efficiency?

• Science view

◮ Build cleanabstractions

◮ Can we harness the Genius of AND?

Precision AND Efficiency?

IIT Delhi LFCPA: Introduction

### 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

### Part 2

### Background

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

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}

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

Constraints on Points-to Sets

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

∀w ∈Pz, Pw ⊇Py

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

Constraints on Points-to Sets

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

∀w ∈Pz, Pw ⊇Py

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

Constraints on Points-to Sets

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

∀w ∈Pz, Pw ⊇Py

Pz ⊇Py

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

Constraints on Points-to Sets

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

∀w ∈Pz, Pw ⊇Py

Pz ⊇Py

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

Constraints on Points-to Sets

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

∀w ∈Pz, Pw ⊇Py

Pz ⊇Py

Py ⊇ {x}

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

Constraints on Points-to Sets

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

∀w ∈Pz, Pw ⊇Py

Pz ⊇Py

Py ⊇ {x}

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

Constraints on Points-to Sets

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

∀w ∈Pz, Pw ⊇Py

Pz ⊇Py

Py ⊇ {x}

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

Constraints on Points-to Sets

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

∀w ∈Pz, Pw ⊇Py

Pz ⊇Py

Py ⊇ {x}

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

Constraints on Points-to Sets

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

∀w ∈Pz, Pw ⊇Py

Pz ⊇Py

Py ⊇ {x}

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

Constraints on Points-to Sets

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

∀w ∈Pz, Pw ⊇Py

Pz ⊇Py

Py ⊇ {x}

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

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

• Treat all pointees of a pointer as “equivalent”

locations

• Transitive closure Pointees of all equivalent locations become equivalent

Effective additional constraints

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

(pointees ofy) Unify(x,u)

(pointees ofz)

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

• Treat all pointees of a pointer as “equivalent”

locations

• Transitive closure Pointees of all equivalent locations become equivalent

Effective additional constraints

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

(pointees ofy) Unify(x,u)

(pointees ofz)

⇒x,y,z,uare equivalent

IIT Delhi

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

• Treat all pointees of a pointer as “equivalent”

locations

• Transitive closure Pointees of all equivalent locations become equivalent

Effective additional constraints

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

(pointees ofy) Unify(x,u)

(pointees ofz)

⇒x,y,z,uare equivalent

⇒Complete graph

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

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

∅

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

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

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

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

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

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

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

x y z u

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

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

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

• Should a b be killed by assignment

∗c= &d?

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

• Should a b be killed by assignment

∗c= &d?

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

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

• Should a b be killed by assignment

∗c= &d?

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

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

• Should a b be killed by assignment

∗c= &d?

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

• Should b e be killed by assignment

∗a= &e?

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^{MUST}b e at the entry of 4

• Should a b be killed by assignment

∗c= &d?

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

• Should b e be killed by assignment

∗a= &e?

Yes because a points to b along both the paths

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^{MUST}b e at the entry of 4

• Should a b be killed by assignment

∗c= &d?

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

• Should b e be killed by assignment

∗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)

IIT Delhi

### Context Sensitivity in Interprocedural Analysis

Startr

Endr

Starts

a= &b

Ends

Ci

Ri

ci

Startt

c = &d

Endt

Cj

Rj

cj

fr

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

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

a b

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

a b

c d

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

a b

c d

c d

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

a b

c d

c d

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

a b

c d

c d

a b

## ×

### ×

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

a b

c d

c d

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

a b

c d

c d

c d

## × ^{×}

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

a b

c d

c d

a b c d

IIT Delhi

### Context Sensitivity in the Presence of Recursion

Starts

Ci

Ri

Ends

call (c)

return (r) calling (s)stop

IIT Delhi

### Context Sensitivity in the Presence of Recursion

Starts

Ci

Ri

Ends

call (c)

return (r) calling (s)stop

• Paths from Starts toEnds should
constitute a context free languagec^{n}sr^{n}

IIT Delhi

### Context Sensitivity in the Presence of Recursion

Starts

Ci

Ri

Ends

call (c)

return (r) calling (s)stop

• Paths from Starts toEnds should
constitute a context free languagec^{n}sr^{n}

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

IIT Delhi

### Context Sensitivity in the Presence of Recursion

Starts

Ci

Ri

Ends

call (c)

return (r) calling (s)stop

• Paths from Starts toEnds should
constitute a context free languagec^{n}sr^{n}

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

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

IIT Delhi

### Context Sensitivity in the Presence of Recursion

Starts

Ci

Ri

Ends

call (c)

return (r) calling (s)stop

• Paths from Starts toEnds should
constitute a context free languagec^{n}sr^{n}

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

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

◮ eitherdo not consider recursion, or

IIT Delhi

### Context Sensitivity in the Presence of Recursion

Starts

Ci

Ri

Ends

call (c)

return (r) calling (s)stop

• Paths from Starts toEnds should
constitute a context free languagec^{n}sr^{n}

^{∗}sr^{∗}

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

◮ either do not consider recursion, or

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

IIT Delhi

### Context Sensitivity in the Presence of Recursion

Starts

Ci

Ri

Ends

call (c)

return (r) calling (s)stop

• Paths from Starts toEnds should
constitute a context free languagec^{n}sr^{n}

^{∗}sr^{∗}

◮ either do not consider recursion, or

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

◮ arecontext insensitive in recursion

IIT Delhi

### Pointer Analysis: An Engineer’s Landscape

FlowSensitivity Increases

Context Sensitivity FI=

FFS

CI FCS

IIT Delhi

### Pointer Analysis: An Engineer’s Landscape

FlowSensitivity Increases

Context Sensitivity

CI FCS

FI=

FI⊆

FISSA

FSNoKill

FFS

IIT Delhi

### Pointer Analysis: An Engineer’s Landscape

FlowSensitivity Increases

Context Sensitivity FI=

FI⊆

FISSA

FSNoKill

FFS

CI CIOS CSK-lim CSRI FCS

IIT Delhi

### Pointer Analysis: An Engineer’s Landscape

FlowSensitivity Increases

Context Sensitivity FI=

FI⊆

FISSA

FSNoKill

FFS

CI CIOS CSK-lim CSRI FCS

Data Structures: BDDs, probabilistic

IIT Delhi

### Pointer Analysis: An Engineer’s Landscape

FlowSensitivity Increases

Context Sensitivity FI=

FI⊆

FISSA

FSNoKill

FFS

CI CIOS CSK-lim CSRI FCS

Data Structures: BDDs, probabilistic

Methods: parallel, on demand, randomized

IIT Delhi

### Pointer Analysis: An Engineer’s Landscape

FlowSensitivity Increases

Context Sensitivity FI=

FI⊆

FISSA

FSNoKill

FFS

CI CIOS CSK-lim CSRI FCS

Data Structures: BDDs, probabilistic

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

IIT Delhi

### Pointer Analysis: An Engineer’s Landscape

FlowSensitivity Increases

Context Sensitivity FI=

FI⊆

FISSA

FSNoKill

FFS

CI CIOS CSK-lim CSRI FCS

### Over Crowed Area

Data Structures: BDDs, probabilistic

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

IIT Delhi

### Pointer Analysis: An Engineer’s Landscape

FlowSensitivity Increases

Context Sensitivity FI=

FI⊆

FISSA

FSNoKill

FFS

CI CIOS CSK-lim CSRI FCS

### Over Crowed Area

Still Vacant Data Structures: BDDs, probabilistic

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

IIT Delhi

### Pointer Analysis: An Engineer’s Landscape

FlowSensitivity Increases

Context Sensitivity FI=

FI⊆

FISSA

FSNoKill

FFS

CI CIOS CSK-lim CSRI FCS

### Over Crowed Area

Still Vacant Data Structures: BDDs, probabilistic

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

That’s the corner we are trying to

occupy :-)

### Part 3

### Formulating LFCPA

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

x y z u

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 u

x y z u

x y z u

x y z

x y z u

x y z u

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 u

x y z u

x y z u

x y z

x y z u

x y z u

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 u

x y z u

x y z u

x y z

x y z u

x y z u

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 u

x y z u

x y z u

x y z

x y z u

x y z u

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 u

x y z u

x y z u

x y z

x y z u

x y z u

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 u

x y z u

x y z u

x y z

x y z u

x y z u

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

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]

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

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

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

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

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}

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}

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

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

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

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

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}

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}

{u,x}

{u,x}

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}

{u,x}

{u,x}

{z} {u,x}

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}

{u,x}

{u,x}

{z} {u,x}

Strong liveness:

y is not made live because z is not live

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}

{u,x}

{u,x}

{z} {u,x}

{u,x,z}

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}

{u,x}

{u,x}

{z} {u,x}

{u,x,z} {u}

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}

{u,x}

{u,x}

{z} {u,x}

{u,x,z} {u}

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}

{u,x}

{u,x}

{z} {u,x}

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

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}

{u,x}

{u,x}

{z} {u,x}

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

x y z u ?

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}

{u,x}

{u,x}

{z} {u,x}

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

x y z u ?

x y u ?

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}

{u,x}

{u,x}

{z} {u,x}

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

x y z u ?

x y u ?

x y u ?

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}

{u,x}

{u,x}

{z} {u,x}

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

x y z u ?

x y u ?

x y u ?

z u

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}

{u,x}

{u,x}

{z} {u,x}

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

x y z u ?

x y u ?

x y u ?

z u

??

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}

{u,x}

{u,x}

{z} {u,x}

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

x y z u ?

x y u ?

x y u ?

z u

??

x y u ?

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,x}

{u,x}

{u,x}

{u} u ?

x y u ?

x y u ?

{z}

z u

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

x y u ?

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,x}

{u,x}

{u,x}

{u} u ?

x y u ?

x y u ?

{x,y,z}

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

z u

x y u ?

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,x}

{u,x}

{u,x}

{u} u ?

x y u ?

x y u ?

{x,y,z}

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

z u

x y u ?

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,x}

{u,x}

{u,x}

{u} u ?

x y u ?

x y u ?

{x,y,z}

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

z u

x y u ?

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,x}

{u,x}

{u,x}

{u} u ?

x y u ?

x y u ?

{x,y,z}

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

x y z u

x y u ?

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,x}

{u,x}

{u,x}

{u} u ?

x y u ?

x y u ?

{x,y,z}

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

x y z u

x y z u

x y u ?

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,x}

{u,x}

{u,x}

{u} u ?

x y u ?

x y u ?

{x,y,z}

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

x y z u

x y z u

x y z u ?

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

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

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 ?

• c is live at program entry

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

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 ?

c ?

a b e • c is live at program entry

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

• Perform usual may points-to analysis

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 ?

c ?

a b e

c ?

a b e • c is live at program entry

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

• Perform usual may points-to analysis

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 ?

c ?

a b e

c ?

a b e

c a b e

?

• c is live at program entry

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

• Perform usual may points-to analysis

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 ?

c ?

a b e

c ?

a b e

c a b e

?

• c is live at program entry

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

• Perform usual may points-to analysis

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