<aside> 💡 Key Points

• Concept of context sensitivity (C.S.)
• Concept of context-sensitive heap (C.S. heap)
• Why C.S. and C.S. heap improve precision
• Context-sensitive pointer analysis rules
• Algorithm for context-sensitive pointer analysis
• Common context sensitivity variants
• Differences and relationship among common context sensitivity variants </aside>

I. Introduction

1. Imprecision of Context Insensitivity, C.I.

A method may be called multiple times under different calling contexts during execution, and therefore, the variables of the method may also point to different objects.

In C.I. pointer analysis, objects under different contexts are mixed and propagated to other parts of program (through return values or side-effects), causing spurious data flows

2. Context Sensitivity

Context sensitivity models calling contexts by distinguishing different data flows of different contexts to improve precision

The oldest and best-known context sensitivity strategy is call-site sensitivity (call-string)

• Which represents each context of a method as a chain of call sites
• Is an abstract model of call stacks in dynamic execution

Cloning-Based Context Sensitivity

The most straightforward approach to implement context sensitivity

• In cloning-based context-sensitive pointer analysis, each method is qualified by one or more contexts
• The variables are also qualified by contexts (inherited from the method they are declared in)
• Essentially each method and its variables are cloned, one clone per context

3. Context-Sensitive Heap

• OO programs (e.g., Java) are typically heap-intensive
• In practice, to improve precision, context sensitivity should also be applied to heap abstraction
• The abstract objects are also qualified by contexts (called heap contexts)

The most common choice is to inherit contexts from the method where the object is allocated.

e.g.: x() { var a = new A() } a will inherit contexts from x()