In heap-based languages, knowing that a variable x points to an acyclic data structure is useful for analyzing termination: this information guarantees that the depth of the data structure to which x points is greater than the depth of the structure pointed to by x.fld, and allows bounding the number of iterations of a loop which traverses the data structure on fld. In general, proving termination needs acyclicity, unless program-specific or non-automated reasoning is performed. However, recent work could prove that certain loops terminate even without inferring acyclicity, because they traverse data structures "acyclically". Consider a double-linked list: if it is possible to demonstrate that every cycle involves both the "next" and the "prev" field, then a traversal on "next" terminates since no cycle will be traversed completely. This paper develops a static analysis inferring field-sensitive reachability and cyclicity information, which is more general than existing approaches. Propositional formulae are computed, which describe which fields may or may not be traversed by paths in the heap. Consider a tree with edges "left" and "right" to the left and right sub-trees, and "parent" to the parent node: termination of a loop traversing leaf-up cannot be guaranteed by state-of-the-art analyses. Instead, propositional formulae computed by this analysis indicate that cycles must traverse "parent" and at least one between "left" and "right": termination is guaranteed as no cycle is traversed completely. This paper defines the necessary abstract domains and builds an abstract semantics on them. A prototypical implementation provides the expected result on relevant examples.
The oldest notion of reachability dates back to @cite_33 : his is supposed to tell if a heap location reaches another one in a linear list. A reachability-based acyclicity analysis for C programs was developed by @cite_35 . That analysis was presented as a analysis, and the terms direction'' and interference'', were used for, respectively, reachability and sharing. Analyses which compute basically the same information were presented in more recent work. @cite_30 @cite_1 describe a formalization of the analysis proposed by @cite_35 in the framework of , based on a Java-like Object-Oriented language and provided with soundness proofs. The same analysis has been also formalized by means of Abstract Interpretation by @cite_36 , which efficiently implement it in the Julia analyzer for Java (bytecode) and Android http: www.juliasoft.com . As already discussed in the introduction, the analysis proposed by @cite_28 is less precise since it does not consider reachability in order to detect cycles. The present work also builds upon the results presented in @cite_4 @cite_19 . The relation with such works was explained in the introduction, and will be made even more clear in the rest of the paper, especially in Section .
@cite_30 @cite_35 @cite_4 @cite_33 @cite_36 @cite_28 @cite_1 @cite_19
2139356751 2030101147 1995268059 1529156240 2061213370
This paper reports on the design and implementation of a practical shape analysis for C. The purpose of the analysis is to aid in the disambiguation of heap-allocated data structures by estimating the shape (Tree, DAG, or Cyclic Graph) of the data structure accessible from each heap-directed pointer. This shape information can be used to improve dependence testing and in parallelization, and to guide the choice of more complex heap analyses.The method has been implemented as a context-sensitive interprocedural analysis in the McCAT conlpiler. Experimental results and observations are given for 16 benchmark programs. These results show that the analysis gives accurate and useful results for an important group of applications. The paper introduces a reachability predicate for linear lists, develops the elementary axiomatic theory of the predicate, and illustrates its application to program verification with a formal proof of correctness for a short program that traverses and splices linear lists. Reachability from a program variable v to a program variable w states that from v, it is possible to follow a path of memory locations that leads to the object bound to w. We present a new abstract domain for the static analysis of possible reachability between program variables or, equivalently, definite unreachability between them. This information is important for improving the precision of other static analyses, such as side-effects, field initialization, cyclicity and path-length analysis, as well as more complex analyses built upon them, such as nullness and termination analysis. We define and prove correct our reachability analysis for Java bytecode, defined as a constraint-based analysis, where the constraint is a graph whose nodes are the program points and whose arcs propagate reachability information in accordance to the abstract semantics of each bytecode instruction. For each program point p, our reachability analysis produces an overapproximation of the ordered pairs of variables 〈v, w〉 such that v might reach w at p. Seen the other way around, if a pair 〈v, w〉 is not present in the overapproximation at p, then v definitely does not reach w at p. We have implemented the analysis inside the Julia static analyzer. Our experiments of analysis of nontrivial Java and Android programs show the improvement of precision due to the presence of reachability information. Moreover, reachability analysis actually reduces the overall cost of nullness and termination analysis. Programming languages such as C, C++ and Java bind variables to dynamically-allocated data-structures held in memory. This lets programs build cyclical data at run-time, which complicates termination analysis and garbage collection. It is hence desirable to spot those variables which are only bound to non-cyclical data at run-time. We solve this problem by using abstract interpretation to define the abstract domain NC representing those variables. We relate NC through a Galois insertion to the concrete domain of program states. Hence NC is not redundant. We define a correct abstract denotational semantics over NC, which uses preliminary sharing information between variables to get more precise results. We apply it to a simple example of analysis. We use a Boolean representation for the abstract denotations over NC, which leads to an efficient implementation in terms of binary decision diagrams and to the elegant and efficient use of abstract compilation. In programming languages with dynamic use of memory, such as Java, knowing that a reference variable x points to an acyclic data structure is valuable for the analysis of termination and resource usage (e.g., execution time or memory consumption). For instance, this information guarantees that the depth of the data structure to which x points is greater than the depth of the data structure pointed to by x.f for any field f of x. This, in turn, allows bounding the number of iterations of a loop which traverses the structure by its depth, which is essential in order to prove the termination or infer the resource usage of the loop. The present paper provides an Abstract-Interpretation-based formalization of a static analysis for inferring acyclicity, which works on the reduced product of two abstract domains: reachability, which models the property that the location pointed to by a variable w can be reached by dereferencing another variable v (in this case, v is said to reach w); and cyclicity, modeling the property that v can point to a cyclic data structure. The analysis is proven to be sound and optimal with respect to the chosen abstraction.