6. Pointer Analysis

Question 1

What is pointer analysis?

Answer 1

How to reason about the flow of non-primitive data e.g., pointers, objects, references.

Question 2

What is pointer aliasing?

Answer 2

Pointer aliasing allows the same address to be referred to in different ways.

Question 3

What is May-Alias analysis?

Answer 3

A May-Alias analysis (aka pointer analysis) tracks whether a pointer variable may alias another pointer. e.g., if we have Circle x = new Circle() and Circle x = new Circle() then this analysis would track that x != z. This allows us to know if x.radius = 1 and z.radius = 2 overwrite. May-Alias and Must-Alias are dual problems. Must-Alias is more advanced, less useful in practice.

Question 4

What is Must-Alias analysis?

Answer 4

A Must-Alias analysis tracks whether a pointer variable must alias another pointer. e.g., if we have Circle x = new Circle() and Circle z = x then this analysis would track that x = z. This allows us to know if x.radius and z.radius overwrite. May-Alias and Must-Alias are dual problems. Must-Alias is more advanced, less useful in practice.

Question 5

What is a Points-to Graph?

Answer 5

A Points-to Graph is the result of heap abstraction.

• Variables are represented by boxes.
• Allocation sites are represented by ovals.
• Edges are represented by arrows.
• Arrows from a variable node to an allocation node are blue. Arros from an allocation node to another allocation node are red.

Question 6

What is flow insensitivity?

Answer 6

A control flow abstraction that is commonly used by pointer analysis

Question 7

How does pointer analysis build a points-to graph? i.e., what algorithm does it use and how does it work?

Answer 7

Question 8

What is a weak update vs a strong update in the context of a points-to graph?

Answer 8

A weak update is when we accumulate points to information. A strong update is when we replace points to information.

Weak updates are a hallmark of flow insensitivity.

Question 9

What is the Object Allocation Sites rule?

i.e., How to we draw “v = new B” on our points-to graph?

Answer 9

For statement “v = new B”:

1. create a new allocation site node B
2. create a variable node v (if doesn’t exist)
3. draw a blue arrow from variable node to allocation site node

NOTE: if there is already an arrow from v to another allocation site node in the points-to graph we just need to add a new arrow from v to B (weak update)

Question 10

What is the Object Copy rule?

i.e., How to we draw “v1 = v2” on our points-to graph?

Answer 10

1. create a variable node v1 (if doesn’t exist)
2. add a blue arrow from variable node v1 to all nodes pointed to by variable node v2

Question 11

What is the Field Writes rule?

i.e., How to we draw “v1.f = v2” or “v1[*] = v2” on our points-to graph?

Answer 11

1. if v1 points to A and v2 points to B, then we add a red arrow from the node for A to the node for B. we label that arrow with the name of the field or [*]

If there isn’t already a node for v1 or v2 then we skip and handle on the next iteration.

If v1 and v2 point to the same node then the arrow we add will be an arrow from the node to itself.

Question 12

What is the Field Reads rule?

i.e., How to we draw “v1 = v2.f” or “v1 = v2[*]” on our points-to graph?

Answer 12

1. if v2 points to B and B points to C via the field f or [*], then we add a blue arrow from the node for v1 to the node for C

if a node for v1 does not already exist, we create it before adding the blue arrow

if there isn’t already a node for v2 or an arrow from B to another node, we skip and try to handle the statement in the next iteration.

Question 13

What are the four classifiers for pointer analysis algorithms?

Answer 13

• Is it flow sensitive?
• Is it context sensitive?
• What kind of heap abstraction scheme does it used?
• How does it model aggregate data types?

Question 14

Explain Flow Sensitivity (in the context of pointer analysis algorithms)

Answer 14

• Models control flow within a procedure
• Two kinds: flow-insensitive vs flow-sensitive
• Flow-insensitive == weak updates (unordered set of statements) only generate new facts (don’t kill previous facts).
  
  • Suffices for may-alias analysis
• Flow-sensitive == strong updates.
  
  • Required for must-alias analysis

Question 15

Explain Context Sensitivity (in the context of pointer analysis algorithms)

Answer 15

• Models control-flow across procedures (aka inter-procedural control-flow)
• Two kinds: context-insensitive vs context-sensitive
• Context-insensitive: analyze each procedure only once
  
  • Imprecise but efficient
• Context-sensitive: analyze each procedure multiple times, once per abstract calling context
  
  • Precise but expensive

Question 16

Explain Heap Abstraction (in the context of pointer analysis algorithms)

Answer 16

• Defines how to partition unbounded set of concrete objects into finitely many abstract objects (oval nodes in points-to graph)
• Ensures that pointer analysis terminates
• Many sound schems, varying in precision and efficiency
  
  • Too few abstract objects => efficient but imprecise
  • Too many abstract objects => expensive but precise

A few schems:

• Allocation-Site Based: one abstract object per allocation site
• Type Based: one abstract object per type
• Heap-Insensitive: Single abstract object representing entire heap
  
  • Good for languages with stack-directed pointers (e.g., C)
  • Bad for languages with only heap-directed pointers (e.g., Java)

Question 17

Explain Aggregate Modeling (in the context of pointer analysis)

Answer 17

Arrays

• Common choice: single field [*] to represent all elements of an array
  
  • Cannot distinguish different elements of an array
• Representations that make distinctions are used by array dependence analyses
  
  • Used to parallelize sequential loops by parallelizing compilers

Records

• Field-insensitive: merge all fields of each record object
• Field-based: merge each field of all record objects
• Field-sensitive: keep each field of each (abstract) record object seperate