Question: Why are pointer flow edges stored in Pointer instead of PointerFlowGraph?

[lollipop190]

📝 Overall Description

Hi, thank you for developing Tai-e. Recently I have a design question about the implementation of the PointerFlowGraph for pointer analysis.

From the current implementation, the out edges and successors of a pointer are stored directly inside each Pointer object (implemented in class AbstractPointer) rather than being managed uniformally in class PointerFlowGraph (for example using something like MultiMap<Pointer, PointerFlowEdge>).

I am a bit curious about the rationale behind this design choice. Thanks for reply!

🎯 Expected Behavior

🐛 Current Behavior

🔄 Reproducible Example

No response

⚙️ Tai-e Arguments

No response

📜 Tai-e Log

No response

ℹ️ Additional Information

No response

[zhangt2333]

Pointer edges and successor relationships are stored within the Pointer objects (via AbstractPointer implementations), rather than being centrally managed by PointerFlowGraph (e.g., using MultiMap<Pointer, PointerFlowEdge>), for the following reasons:

1. Hot-path performance: The propagation loop frequently calls p.getOutEdges(). Storing edges directly in the pointer maximizes cache locality and reduces memory indirection.
2. O(1) deduplication: Successors are stored in an IndexableSet backed by a bitmap, enabling efficient, constant-time deduplication — a capability only possible when the set is maintained locally within the Pointer.
3. No need for reverse edges: The analysis only traverses forward, so reverse edges are unnecessary. Centralized management of all edges would be redundant and wasteful.
4. Clear responsibility separation: CSManager manages pointer lifetimes and creation, while each Pointer autonomously manages its own state — including its outgoing edges, successor sets, and filtering logic. This keeps concerns well-separated.

Crucially, PointerFlowGraph is not the source of truth — it exists solely as a view of the underlying pointer flow relationships. It aggregates and exposes the data stored in the Pointer objects, providing a high-level, queryable representation of the flow graph without owning or managing the edges directly.

[lollipop190]

Thanks for the rapid and detailed reply, very useful and insightful, thanks a lot!