harpoon.Analysis.PointerAnalysis
Class PointerAnalysis

java.lang.Object
  harpoon.Analysis.PointerAnalysis.PointerAnalysis

All Implemented Interfaces:

Serializable

public class PointerAnalysis
extends Object
implements Serializable

PointerAnalysis is the main class of the Pointer Analysis package. It is designed to act as a query-object: after being initialized, it can be asked to provide the Parallel Interaction Graph valid at the end of a specific method.

Version:

$Id: PointerAnalysis.java,v 1.25 2005/12/10 17:26:39 salcianu Exp $

Author:

Alexandru SALCIANU <salcianu@retezat.lcs.mit.edu>

See Also:

Serialized Form

Field Summary

static boolean	AGGRESSIVE_COMPRESS_LOST_NODES Same as COMPRESS_LOST_NODES, but done at the end of the analysis of each method.
static String	ARRAY_CONTENT Array elements are modeled as fields of the array object, all of them with the same name since the analysis is not able to make the distinction between the fields.
static boolean	CALL_CONTEXT_SENSITIVE Activates the calling context sensitivity.
static boolean	COMPRESS_LOST_NODES If true, compress all load nodes that escape into an unanalyzed method and/or a static field into the single summar node NodeRepository.LOST_SUMMARY (currently, this is done only at the end of a method, when producing the external version of the ParIntGraph).
static boolean	CONDENSED_ESCAPE_INFO If false, do not keep track of all un-analyzed methods where a node escapes.
static boolean	CONSIDER_TYPES If true, then we do not introduce edges about which we can infer that they violate the type declarations: e.g., an edge on the field "foo" from an inside node for new Integer.
static boolean	DEBUG
static boolean	DEBUG_INTRA
static boolean	DEBUG_SCC
static boolean	DEBUG2
static boolean	DETAILS2
static boolean	DETERMINISTIC Makes the pointer analysis deterministic to make the debug easier.
static boolean	DO_INTRA_PROC_TRIMMING
static boolean	FINE_TIMING
static boolean	IGNORE_EO Hack to speed it up: it appears to me that the edge ordering relation is not extremely important: in recursive methods or in methods with loops, it tends to be just a cartesian product between I and O.
static boolean	IGNORE_LOADS_FROM_NATIVES Ignore what is load from a RETURN/EXCEPT node.
Linker	linker
static boolean	LOOP_SENSITIVE Activates the loop sensitivity.
static int	MAX_SPEC_DEPTH The specialization limit.
static boolean	MEGA_DEBUG crazy, isn't it?
static boolean	MEGA_DEBUG2
static boolean	RECORD_ACTIONS Turns on the recording of the actions done by the program.
static boolean	REUSE_LOAD_NODES If true, then each time we try to load something from an escaped node that already has a few load nodes (for the field we load), we reuse the smallest existent node, instead of generating a node for that LOAD instruction.
static boolean	SAVE_MEMORY Turns on the save memory mode.
static boolean	SHOW_NODES
static boolean	STATS
static boolean	THREAD_SENSITIVE Activates the full thread sensitivity.
static boolean	TIMING Turns on the printing of some timing info.
static boolean	TOPLAS_PAPER
static boolean	TREAT_CONST Controls whether the analysis models references to constant Strings by edges to the special node CONST, or simply ignores them.
static boolean	TREAT_NULL Controls whether the analysis models the null references by edges to the special node NULL, or simply ignores them.
static boolean	WEAKLY_THREAD_SENSITIVE Activates the weak thread sensitivity.

Constructor Summary

PointerAnalysis(MetaCallGraph mcg, CachingSCCLBBFactory caching_scc_lbb_factory, Linker linker, ClassHierarchy ch)
Creates a PointerAnalysis object.

Method Summary

static boolean	analyzable(HMethod hm) Check if hm can be analyzed by the pointer analysis.
CachingSCCLBBFactory	getCachingSCCLBBFactory() Returns the SCC LBB factory used by this PointerAnalysis object.
ParIntGraph	getExtParIntGraph(HMethod hm)
ParIntGraph	getExtParIntGraph(MetaMethod mm) Returns the simplified (external) ParIntGraph attached to the method hm i.e. the graph at the end of the method.
ParIntGraph	getExtThreadInteraction(MetaMethod mm)
ParIntGraph	getIntParIntGraph(HMethod hm) That's what you probably want: equivalent to getIntParIntGraph(new MetaMethod(hm, true)).
ParIntGraph	getIntParIntGraph(MetaMethod mm) Equivalent to getIntParIntGraph(mm,true).
ParIntGraph	getIntParIntGraph(MetaMethod mm, boolean analyze) Returns the full (internal) ParIntGraph attached to the method hm i.e. the graph at the end of the method.
ParIntGraph	getIntThreadInteraction(MetaMethod mm)
Linker	getLinker()
Set	getLostNodes(MetaMethod mm)
MetaAllCallers	getMetaAllCallers() Returns the all callers graph used by this PointerAnalysis object.
MetaCallGraph	getMetaCallGraph() Returns the call graph graph used by this PointerAnalysis object.
NodeRepository	getNodeRepository()
PANode[]	getParamNodes(MetaMethod mm) Returns the parameter nodes of the method hm.
ParIntGraph	getPigAfterQuad(MetaMethod mm, Quad q) Returns the parallel interaction graph attached to the program point right after q in the body of meta-method mm.
ParIntGraph	getPIGAtQuad(HMethod hm, Quad q)
ParIntGraph	getPIGAtQuad(MetaMethod mm, Quad q) Returns the parallel interaction graph attached to the program point right after q in the body of meta-method mm.
ParIntGraph	getPigBeforeQuad(MetaMethod mm, Quad q) Returns the parallel interaction graph attached to the program point right before q in the body of meta-method mm.
ParIntGraph	getPigForQuad(MetaMethod mm, Quad q, int moment)
Set	pointedNodes(MetaMethod mm, Quad q, Temp l) Returns the set of the nodes pointed by the temporary t at the point right before executing instruction q from the body of meta-method mm.
Set	pointedNodes(Quad q, Temp l)
void	print_stats() Prints some statistics.
ParIntGraph	threadInteraction(MetaMethod mm) Returns the parallel interaction graph for the end of the method hm.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

DEBUG

public static final boolean DEBUG

See Also:

Constant Field Values

DEBUG2

public static final boolean DEBUG2

See Also:

Constant Field Values

DEBUG_SCC

public static final boolean DEBUG_SCC

See Also:

Constant Field Values

DEBUG_INTRA

public static final boolean DEBUG_INTRA

See Also:

Constant Field Values

MEGA_DEBUG

public static boolean MEGA_DEBUG

crazy, isn't it?

MEGA_DEBUG2

public static boolean MEGA_DEBUG2

RECORD_ACTIONS

public static boolean RECORD_ACTIONS

Turns on the recording of the actions done by the program.

IGNORE_EO

public static final boolean IGNORE_EO

Hack to speed it up: it appears to me that the edge ordering relation is not extremely important: in recursive methods or in methods with loops, it tends to be just a cartesian product between I and O.

See Also:

Constant Field Values

IGNORE_LOADS_FROM_NATIVES

public static boolean IGNORE_LOADS_FROM_NATIVES

Ignore what is load from a RETURN/EXCEPT node. Anyway, we cannot determine what is load from there.

CONDENSED_ESCAPE_INFO

public static boolean CONDENSED_ESCAPE_INFO

If false, do not keep track of all un-analyzed methods where a node escapes. Instead, just record the fact whether a node escapes (or not) in some un-analyzed method.

COMPRESS_LOST_NODES

public static boolean COMPRESS_LOST_NODES

If true, compress all load nodes that escape into an unanalyzed method and/or a static field into the single summar node NodeRepository.LOST_SUMMARY (currently, this is done only at the end of a method, when producing the external version of the ParIntGraph). This compression is applied to the external versions of the parallel interaction graphs, after the end of the fixed point computation for a SCC of methods.

TOPLAS_PAPER

public static boolean TOPLAS_PAPER

AGGRESSIVE_COMPRESS_LOST_NODES

public static boolean AGGRESSIVE_COMPRESS_LOST_NODES

Same as COMPRESS_LOST_NODES, but done at the end of the analysis of each method. BREAKS MONOTONICITY!

REUSE_LOAD_NODES

public static boolean REUSE_LOAD_NODES

If true, then each time we try to load something from an escaped node that already has a few load nodes (for the field we load), we reuse the smallest existent node, instead of generating a node for that LOAD instruction. BREAKS MONOTONICITY!

TREAT_NULL

public static boolean TREAT_NULL

Controls whether the analysis models the null references by edges to the special node NULL, or simply ignores them.

TREAT_CONST

public static boolean TREAT_CONST

Controls whether the analysis models references to constant Strings by edges to the special node CONST, or simply ignores them.

CONSIDER_TYPES

public static boolean CONSIDER_TYPES

If true, then we do not introduce edges about which we can infer that they violate the type declarations: e.g., an edge on the field "foo" from an inside node for new Integer.

SAVE_MEMORY

public static final boolean SAVE_MEMORY

Turns on the save memory mode. In this mode, some of the speed is sacrified for the sake of the memory consumption. More specifically, the Interior, large version of the Parallel Interaction Graph at the end of a method is no longer cached.

See Also:

Constant Field Values

DETERMINISTIC

public static final boolean DETERMINISTIC

Makes the pointer analysis deterministic to make the debug easier. The main source of undeterminism in our code is the intensive use of Sets which doesn't offer any guarantee about the order in which they iterate over their elements.

See Also:

Constant Field Values

TIMING

public static boolean TIMING

Turns on the printing of some timing info.

FINE_TIMING

public static boolean FINE_TIMING

STATS

public static final boolean STATS

See Also:

Constant Field Values

SHOW_NODES

public static boolean SHOW_NODES

DETAILS2

public static final boolean DETAILS2

See Also:

Constant Field Values

CALL_CONTEXT_SENSITIVE

public static boolean CALL_CONTEXT_SENSITIVE

Activates the calling context sensitivity. When this flag is on, the nodes from the graph of the callee are specialized for each call site (up to MAX_SPEC_DEPTH times). This increases the precision of the analysis but requires more time and memory.

MAX_SPEC_DEPTH

public static int MAX_SPEC_DEPTH

The specialization limit. This puts a limit to the otherwise exponential growth of the number of nodes in the analysis.

THREAD_SENSITIVE

public static boolean THREAD_SENSITIVE

Activates the full thread sensitivity. When this flag is on, the analysis makes the distinction not only between the nodes allocated by the current thread and those allocated by all the others but also between the nodes allocated by threads with different run methods (for the time being, we cannot make the distinction between two threads with the same thread node).

WEAKLY_THREAD_SENSITIVE

public static boolean WEAKLY_THREAD_SENSITIVE

Activates the weak thread sensitivity. When this flag is on, the precision of the interthread analysis is increased: the nodes from the graph of the run method of the thread whose interactions with the current thread are analyzed are specialized to differenciate between the nodes created by that thread and the nodes created by the current one. This increases the precision of the analysis but requires more time and memory.

LOOP_SENSITIVE

public static boolean LOOP_SENSITIVE

Activates the loop sensitivity. When this flag is on, the precision of the intra-method analysis is increased by making the difference between the last object allocated at a specific object creation site inside a loop and the objects allocated at the same object creation site but in the previous iterations. This enambles some strong optimizations but requires more time and memory.

ARRAY_CONTENT

public static final String ARRAY_CONTENT

Array elements are modeled as fields of the array object, all of them with the same name since the analysis is not able to make the distinction between the fields. this name is supposed to be "as impossible as possible", so that we don't have any conflict with real fields.

See Also:

Constant Field Values

DO_INTRA_PROC_TRIMMING

public static final boolean DO_INTRA_PROC_TRIMMING

See Also:

Constant Field Values

linker

public Linker linker

Constructor Detail

PointerAnalysis

public PointerAnalysis(MetaCallGraph mcg,
                       CachingSCCLBBFactory caching_scc_lbb_factory,
                       Linker linker,
                       ClassHierarchy ch)

Creates a PointerAnalysis object.

Parameters:

mcg - The (meta) Call Graph that models the caller-callee relation between methods.

lbbconv - The producer of the (Light) Basic Block representation of a method body.

Method Detail

getMetaCallGraph

public final MetaCallGraph getMetaCallGraph()

Returns the call graph graph used by this PointerAnalysis object.

getMetaAllCallers

public final MetaAllCallers getMetaAllCallers()

Returns the all callers graph used by this PointerAnalysis object.

getCachingSCCLBBFactory

public final CachingSCCLBBFactory getCachingSCCLBBFactory()

Returns the SCC LBB factory used by this PointerAnalysis object.

getLinker

public final Linker getLinker()

getIntParIntGraph

public ParIntGraph getIntParIntGraph(MetaMethod mm,
                                     boolean analyze)

Returns the full (internal) ParIntGraph attached to the method hm i.e. the graph at the end of the method. If mm was not analyzed yet and analyze is true, analyze mm (and store the result of the analysis in the internal cache). May return null if mm is unanalyzable, or if it has not been analyzed yet and analyze is false.

getIntParIntGraph

public ParIntGraph getIntParIntGraph(MetaMethod mm)

Equivalent to getIntParIntGraph(mm,true).

getIntParIntGraph

public ParIntGraph getIntParIntGraph(HMethod hm)

That's what you probably want: equivalent to getIntParIntGraph(new MetaMethod(hm, true)).

getExtParIntGraph

public ParIntGraph getExtParIntGraph(MetaMethod mm)

Returns the simplified (external) ParIntGraph attached to the method hm i.e. the graph at the end of the method. of which only the parts reachable from the exterior (via parameters, returned objects or static classes) have been preserved. The escape function do not consider the parameters of the function (anyway, this graph is supposed to be inlined into the graph of the caller, so the parameters will disappear anyway). Returns null if no such graph is available.

getExtParIntGraph

public ParIntGraph getExtParIntGraph(HMethod hm)

getParamNodes

public PANode[] getParamNodes(MetaMethod mm)

Returns the parameter nodes of the method hm. This is useful for the understanding of the ParIntGraph attached to hm

threadInteraction

public ParIntGraph threadInteraction(MetaMethod mm)

Returns the parallel interaction graph for the end of the method hm. The interactions between hm and the threads it (transitively) starts are analyzed in order to "recover" some of the escaped nodes.
See Section 10 Inter-thread Analysis in the original paper of Martin and John Whaley for more details.

getExtThreadInteraction

public ParIntGraph getExtThreadInteraction(MetaMethod mm)

getIntThreadInteraction

public ParIntGraph getIntThreadInteraction(MetaMethod mm)

getNodeRepository

public final NodeRepository getNodeRepository()

getLostNodes

public Set getLostNodes(MetaMethod mm)

Returns:

set of inside nodes that are merged into LOST during the analysis of mm. These are nodes that do not appear in the pig for the method, but clearly escape.

analyzable

public static final boolean analyzable(HMethod hm)

Check if hm can be analyzed by the pointer analysis.

print_stats

public final void print_stats()

Prints some statistics.

getPIGAtQuad

public final ParIntGraph getPIGAtQuad(MetaMethod mm,
                                      Quad q)

Returns the parallel interaction graph attached to the program point right after q in the body of meta-method mm.

getPIGAtQuad

public final ParIntGraph getPIGAtQuad(HMethod hm,
                                      Quad q)

getPigAfterQuad

public final ParIntGraph getPigAfterQuad(MetaMethod mm,
                                         Quad q)

Returns the parallel interaction graph attached to the program point right after q in the body of meta-method mm.

getPigBeforeQuad

public final ParIntGraph getPigBeforeQuad(MetaMethod mm,
                                          Quad q)

Returns the parallel interaction graph attached to the program point right before q in the body of meta-method mm.

getPigForQuad

public final ParIntGraph getPigForQuad(MetaMethod mm,
                                       Quad q,
                                       int moment)

pointedNodes

public final Set pointedNodes(MetaMethod mm,
                              Quad q,
                              Temp l)

Returns the set of the nodes pointed by the temporary t at the point right before executing instruction q from the body of meta-method mm.

pointedNodes

public final Set pointedNodes(Quad q,
                              Temp l)