Improving Flow-Insensitive Solutions for Non-Separable Dataflow Problems

Flow-insensitive solutions to dataflow problems have been known to be highly scalable; however also hugely imprecise. For non-separable dataflow problems this solution is further degraded due to spurious facts generated as a result of dependence among the dataflow facts. We propose an improvement to the standard flow-insensitive analysis by creating a generalized version of the dominator relation that reduces the number of spurious facts generated. In addition, the solution obtained contains extra information to facilitate the extraction of a better solution at any program point, very close to the flow-sensitive solution. To improve the solution further, we propose the use of an intra-block variable renaming scheme. We illustrate these concepts using two classic non-separable dataflow problems --- points-to analysis and constant propagation.