6. Pointer Analysis Flashcards
What is pointer analysis?
How to reason about the flow of non-primitive data e.g., pointers, objects, references.
What is pointer aliasing?
Pointer aliasing allows the same address to be referred to in different ways.
What is May-Alias analysis?
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.
What is Must-Alias analysis?
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.
What is a Points-to Graph?
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.
What is flow insensitivity?
A control flow abstraction that is commonly used by pointer analysis
How does pointer analysis build a points-to graph? i.e., what algorithm does it use and how does it work?
What is a weak update vs a strong update in the context of a points-to graph?
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.
What is the Object Allocation Sites rule?
i.e., How to we draw “v = new B” on our points-to graph?
For statement “v = new B”:
- create a new allocation site node B
- create a variable node v (if doesn’t exist)
- 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)
What is the Object Copy rule?
i.e., How to we draw “v1 = v2” on our points-to graph?
- create a variable node v1 (if doesn’t exist)
- add a blue arrow from variable node v1 to all nodes pointed to by variable node v2
What is the Field Writes rule?
i.e., How to we draw “v1.f = v2” or “v1[*] = v2” on our points-to graph?
- 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.
What is the Field Reads rule?
i.e., How to we draw “v1 = v2.f” or “v1 = v2[*]” on our points-to graph?
- 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.
What are the four classifiers for pointer analysis algorithms?
- Is it flow sensitive?
- Is it context sensitive?
- What kind of heap abstraction scheme does it used?
- How does it model aggregate data types?
Explain Flow Sensitivity (in the context of pointer analysis algorithms)
- 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
Explain Context Sensitivity (in the context of pointer analysis algorithms)
- 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
Explain Heap Abstraction (in the context of pointer analysis algorithms)
- 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)
Explain Aggregate Modeling (in the context of pointer analysis)
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
