Optimistic Inter-procedural Dataflow Analysis (original) (raw)

We are currently working on an inter-procedural data flow analysis that computes if a pointer may be defined by an alloca. The analysis should optimistically return true if a pointer may stem from an alloca even if not all callers of a function are known (the existence of a single caller that is known to pass an alloc is sufficient).

We experimented with an AbstractSparseForwardDataFlowAnalysis. The analysis only propagates values to a callee if all callsites are known (and otherwise defaults to the entry state):

This conservative behavior definitely makes sense by default but does not work for us (all our functions have public visibility).

Would it make sense to make this behavior configurable upstream? A possible solution could be to make the visitBlock function overridable? Alternatively, we could add a configuration flag, such as optimisticCallsitePropagation, to control the behavior of the analysis?

+1 on making visitBlock virtual so downstream can override behavior (instead of adding a flag).

gysit May 28, 2025, 2:55pm 3

Just out of curiosity, do you have a specific use case in mind that is not covered by the flag?

Not here, not wrt to this particular extension, but in general I prefer such extension points for downstream users to be able to override upstream behavior when they need to.

j2kun May 29, 2025, 4:52am 5

I also like this idea, though I don’t have a direct use for it. Another option would be to specify the default behavior as its own virtual function (i.e. generalize just the body of the offending if statement), which is not mutually exclusive with making the whole function virtual.

I’ve opened a PR (#142549) that moves the handling of call and callable operations to virtual functions, allowing them to be overridden without much code duplication.

ftynse June 5, 2025, 2:33pm 7

On top of this, I would highly appreciate better documentation about this framework. In particular, the mapping of functions to define/override to the terminology of optimistic/pessimistic.