|PREV PACKAGE NEXT PACKAGE||FRAMES NO FRAMES|
|FlowAnalysis||A simple flow analysis framework.|
|AliasAnalysis||Alias analysis performed on a set of methods.|
|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
|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.|
|AliasStatus||Describes the known aliasing status between two variables.|
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
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
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.
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.
|PREV PACKAGE NEXT PACKAGE||FRAMES NO FRAMES|