6. Pointer Analysis

Question 1

Pointer Analysis

Answer 1

flow of non primitive things

Question 2

pointer aliasing

Answer 2

Expressions built using pointers, such as x.radius, allow the same memory address to be referred to in
different ways

Question 3

pointer aliasing circle example

Answer 3

Circle x = new Circle()
Circle z = ?
x. radius = 1
z.radius = 2
y = x.radius 
assert(y==1) 

Because we don’t know if z represents the same circle as x or not, the analysis is unable to continue past z.radius =2 since we’d be unsure if x.radius still equaled 1

Question 4

May-Alias Analysis

Answer 4

An analysis that is dedicated to proving facts of the form “x may-alias z?” is called
a MAY-alias analysis.

Question 5

Is pointer analysis must-alias or may-alias analysis?

Answer 5

may-alias

Question 6

May-Alias circle example

Answer 6

Circle x = new Circle()
Circle z = new Circle()
x. radius = 1
z.radius = 2
y = x.radius 
assert(y==1) 

We know now in this case that x!=z so after z.radius=2 is done, we can confidently say that x.radius is still 1.

Question 7

Must-Alias circle example

Answer 7

Circle x = new Circle()
Circle z = x
x. radius = 1
z.radius = 2
y = x.radius 
assert(y==1) 

after the assignment to z, we know that x == z. x.radius =1 makes the x radius 1. z.radius=2 makes x.radius=2 since we previously established that x == z.
x and z MUST Alias in this case.

Question 8

May alias vs must alias

Answer 8

Must alias is more advance, but it is less useful in practice.
May alias analysis is useful for more practical dataflow analysis than must alias.

Question 9

Why is pointer analysis hard?

Answer 9

you have to keep track of everything. In the case of a doubly linked list, you could refer to h.data in a number of ways:
h.next.prev.data, h.next.next.prev.prev.data, etc
cycles are hard yo

Question 10

Pointer analysis problem is undecidable. T/F

Answer 10

True. We must sacrifice some combination of Soundness, Completeness, Termination.

Question 11

what does pointer analysis sacrifice to become decidable?

Answer 11

completeness. This means that we can expect false positives, but no false negatives.

Question 12

False positive

Answer 12

If the answer is no, but yes is the returned answer.

Question 13

How can a false positive manifest in the circle example?

Answer 13

Circle x = new Circle()
Circle z = new Circle()
x. radius = 1
z.radius = 2
y = x.radius 
assert(y==1) 

x May-Alias z returns YES. 
means that after z=new Circle() our analysis cannot determine that x!=z, but that x==z or x!=z. So going down the remaining analysis we reach the conclusion that y==1 or y==2

Question 14

Approximate algorithms for pointer analysis have varying levels of precision. These algorithms differ in two key aspects:

Answer 14

1. How to abstract the heap (ie dynamically allocated data)

2. How to abstract control-flow

Question 15

Abstracting the heap (Elevator example): Abstract object based on site they are allocated

Answer 15

Basically take the levels of the program and combine all those things into a single node in the graph. all objects allocated within a for loop are represented by a single node.
Creates a Points to graph http://imgur.com/a/nXlBb

Question 16

Abstracting the control flow (Elevator example)

Answer 16

only a single points to graph for entire program, so we abstract the control flow.

remember how the Points to graph looked before? Instead of changing the graph representation, change the code itself to create that graph. http://imgur.com/a/a18LY

Question 17

flow insensitivity

Answer 17

http://imgur.com/a/a18LY idk man
all constructs such as for loops are removed
; are removed as well
all statements that do not affect pointers removed
indices replaced with nondeterministic *s
no order to these statements now even though they are still in rough order

Question 18

Chaotic Iteration Algorithm

Answer 18

Start with empty point to graph
go through each statement s in set
while applying rule corresponding to s on graph
until graph stops changing.

Question 19

Statement types

Answer 19

v = new
v = v2 object copy
v2 = v.f field read statement
v.f = v2 field write statement
v2 = v[*] field read 
v[*] = v2 field write

Question 20

Convert v.events = new Object[] to the statement grammar or whatever its called

Answer 20

tmp = new Object[]
v.events = tmp

Question 21

convert

v.events[*] = e

Answer 21

tmp = v.events
tmp[*] = e

Question 22

convert

v1.f = v2.f

Answer 22

tmp = v2.f
v1.f = tmp

Question 23

convert

v1.f.g = v2.h

Answer 23

tmp1 = v1.f
tmp2 = v2.h
tmp1.g=tmp2

Question 24

Rule for object allocation sites: Weak update

Answer 24

if there is already an arrow from v to another allocation site node and we just need to add another.

Question 25

Rule for object allocation sites: Strong update

Answer 25

replace the points-to information

Question 26

Rule for Object Copy

Answer 26

v1 = v2
create variable node for v1
add blue arrow from v1 to all nodes pointed to by v2

Question 27

Rule for field writes

Answer 27

v1.f=v2
if v1 points to A and v2 points to B
we add a red arrow from A to B and label it by name for field or by * if its an index

Question 28

rule for field reads

Answer 28

v1 = v2.f
if v2 points to B and B points to C by f or *
we add a blue arrow from v1 to C

Question 29

Classifying Pointer Analysis Algorithms

Answer 29

Flow sensitive
Context Sensitive
What heap abstraction scheme
how are aggregate data types modeled

Question 30

flow sensitivity

Answer 30

how to model control flow within a procedure

either flow insensitive or flow sensitive

Question 31

flow insensitive

Answer 31

weak updates
only generate new facts, doesn’t kill any old facts
suffice for may-alias analysis

Question 32

flow sensitive

Answer 32

strong updates - killing and generating facts

must-alias analysis

Question 33

Inpractical for a must alias analysis to have a low false positive rate by being flow insensitive

Answer 33

true

Question 34

Context sensitivity

Answer 34

how to model control flow across procedures
context insensitive
context sensitive

Question 35

context insensitive

Answer 35

only analyze each procedure once despite how many times its called in the program
inprecise but efficient

Question 36

context sensitive

Answer 36

analyze each procedure possibly multiple times, once per abstract calling context

Question 37

heap abstraction scheme

Answer 37

scheme to partition unbounded set of concrete objects into finitely many abstract objects (oval nodes)
Ensures pointer analysis terminates
Many sound schemes exist

Question 38

Heap abstraction scheme: too few abstract objects ==

Answer 38

efficient but imprecise

Question 39

Heap abstraction scheme: too many abstract objects ==

Answer 39

expensive but precise

Question 40

Heap abstraction scheme #1: Allocation-Site Based

Answer 40

one abstract object per allocation site
Allocation site identified by: “new” keyword in Java/C++, malloc() call in C
Finitely many allocation sites in program, so guaranteed finitely many abstract objects

Question 41

Allocation site based downsides

Answer 41

costly
large programs
clients needing quick turnaround time
overly fine granularity of sites

Question 42

Heap abstraction scheme #2: Type Based

Answer 42

one abstract object per type

finitely many types in program, so finitely many abstract objects

Question 43

Heap abstraction scheme #3: Heap Insensitive

Answer 43

Single abstract object representing the entire heap.

highly imprecise, but sound

Question 44

When is heap insensitive scheme useful

Answer 44

popular for languages with primarily stack-directed pointers (C)

Question 45

Do quiz #31 in lesson 6

Answer 45

dumbass

Question 46

Modeling Aggregate Data Types: Arrays

Answer 46

Common choice: single [*] field to represent all array elements

Question 47

Modeling Aggregate Data Types: Records

Answer 47

structs or objects
Three common choices:
1. field insensitive - merge all fields of each record object
2. field based - merge each field of all record objects
3, field sensitive - keep each field of each record object separate