Research on flow sensitive demand driven alias analysis

In order to improve the response efficiency of pointer alias queries in the interactive environment, researches are interested in the demand driven strategy to reduce the cost for analyzing the unrelated pointer variables with respect to the objectives. The demand driven alias analysis based on the context free grammar has been proposed. However, its precision is only limited to the flow-insensitivity. The flow-insensitivity pointer alias restricts the precision of overlying analysis, so the bug detection results in more false alarms than the one with flow-sensitive alias analysis. In this paper, we propose a demand driven pointer alias analysis based on the graph reachability and the context free grammar to provide the flow sensitive precision, which has tolerable additional overhead comparing with the flow-insensitive alias analysis. First the updates of pointer variables are discriminated by the partial single static assignment to filter out the unrelated pointer variables as early as possible. Then the sequence of control flow along these assignments is expressed in the form of level linearization code, which is used to construct the assignment flow graph. Finally, the query of alias in demand driven is formalized as the search of reachability of target nodes in the assignment flow graph to achieve the precision of flow sensitivity. The experiments demonstrate that this presented method can improve the flow sensitivity the precision of alias analysis in demand driven with overhead tolerable.