Package dk.brics.string.intermediate.operations

Operations on intermediate representation, in particular conversion to flow graphs.


Interface Summary
FlowAnalysis A simple flow analysis framework.

Class Summary
AliasAnalysis Alias analysis performed on a set of methods.
AliasAssertionAnalysis Analyses AssertAliases statements to determine which are valid assertions.
AliasInfo Alias and corruption information for a specific program point.
AliasTable Represents the aliasing status between a set of variables.
DefinesVisitor A statement visitor for querying the set of local variables and fields written to by a statement, including aliases if provided.
FieldUsageAnalysis Finds the set of fields that each method reads and/or modifies.
FlowGraphEdgeCreator Creates all flow graph edges for a flow graph created by a FlowGraphNodeCreator.
FlowGraphNodeCreator Translates a set of methods into a flow graph with no edges.
HandleFieldAssignment To get a sound analysis for fields containing mutable types, we must use a flow insensitive analysis or use the hack implemented by this class.
Intermediate2Dot Constructs Graphviz dot representation of intermediate representation.
Intermediate2FlowGraph Converter from intermediate representation to flow graphs.
LivenessAnalysis Intra-procedural liveness analysis performed on a set of methods.
OperationAssertionAnalysis Determines which assertions are "safe".
ReachingDefinitions Intra-procedural reaching definitions analysis performed on a set of methods.
ToStringVisitor Visitor for producing string representations of statements.
UsesVisitor A statement visitor for querying the set of variables read by a statement.
WorkList A worklist algorithm for performing flow analyses on a set of methods.

Enum Summary
AliasStatus Describes the known aliasing status between two variables.

Package dk.brics.string.intermediate.operations Description

Operations on intermediate representation, in particular conversion to flow graphs.

The main obstacle to producing a flow graph from the IR is the presence of mutable string values in the form of StringBuffers, StringBuilders, and String arrays. We need to calculate the def-use relationships between the individual string operations in a way that takes the possible aliasing between variables of type StringBuffer, StringBuilder, or String array into account. Furthermore, we must handle escapes of such values properly. An escaped value is corrupted and can from that point onward contain any value, no matter which operations are performed on it.

The first step in the preparation procedure is to perform an alias analysis on these pointer variables to determine which variables may point to the same object. This analysis also determines which variables might have escaped and should be corrupt. The alias analysis we employ is a variable-pair-based may/must alias analysis (as opposed to points-to based approaches). The analysis is semi-interprocedural. From the caller to the callee flows information about the aliasing relationships between the arguments, and from the callee to the caller flows the aliasing information between the arguments and the return value and whether each of the arguments and the return value escape during the method. Methods are analyzed context-insensitively. To boost the efficiency of the analysis and the subsequent transformations, a liveness analysis is performed prior to the alias analysis and only live variables are treated in the analysis.

The second preparation step is a reaching definitions analysis that uses the alias information. Every StringBuffer/StringBuilder operation performed on some variable x is characterized as a strong definition of every variable that is definitely aliased with x at that point and a weak definition of all variables possibly aliased with x. An array store operation is a weak definition of the array variable. Based on these characterizations, a reaching definitions analysis is performed where both strong and weak definitions are regarded as definitions but only a strong definition can kill another definition. The result is, for each string operation and every variable that could potentially point to the affected string, which other string operations could possibly have been the immediately preceding one performed on the string pointed to by that variable.

The information obtained from the reaching definitions analysis is precisely what is needed to construct the flow graph. One node is created for every strong or weak definition (that is, one node per possibly affected live variable in the presence of aliasing). These nodes are connected according to the calculated def-use relationships. If a variable was marked corrupt by the alias analysis, its node will represent the language of all strings, regardless of what operation was performed on it. The result is a flow graph that conservatively models the original Java program.

This code may be used under the terms of the GNU General Public License.

Anders Møller <>, Aske Simon Christensen <>, Asger Feldthaus <>

Copyright © 2003-2009 Anders Møller, Aske Simon Christensen, Asger Feldthaus.