The paths in which “returns” are matched with corresponding “calls”.
A path is considered to connect two nodes A and B, or B is reachable from A, only if the concatenation of the labels on the edges of the path is a word in a specified context-free language.
“Precise Interprocedural Dataflow Analysis via Graph Reachability”--Thomas Reps, Susan Horwitz, and Mooly Sagiv, POPL’95
Path function for path p, denoted as, is a composition of flow functions for all edges (sometimes nodes) on p
For each node n, MOP n provides a “meet-over-all-paths” solution where Paths(start, n) denotes the set of paths in CFG from the start node to n.
For each node n, MRP n provides a “meet-over-all-realizable-paths” solution where RPaths(start, n) denotes the set of realizable paths (the path’s word is in the language L(realizable)) from the start node to n.
For each node n ∈ N*, determine the set of variables that may be uninitialized before execution reaches n.
Note: If we want to obtain alias information in IFDS, say alias(x,y), to produce correct outputs, we need to consider multiple input data facts, x and y, which cannot be done in standard IFDS as flow functions handle input facts independently (one fact per time). Thus pointer analysis is non-distributive.