Package com.tonic.analysis.simulation.heap

Class SimHeap

java.lang.Object

com.tonic.analysis.simulation.heap.SimHeap

public final class SimHeap
extends Object

Abstract heap of objects, arrays, and static fields keyed by allocation site - mutated in place in MUTABLE mode, copied on every write otherwise.

Constructor Summary

Constructors

Constructor	Description
SimHeap(HeapMode mode)	Creates an empty heap.

Method Summary

Modifier and Type	Method	Description
SimHeap	allocate(AllocationSite site)	Records a fresh object at an allocation site, replacing any object already recorded there.
SimHeap	allocateArray(AllocationSite site, IRType elementType, SimValue length)	Records a fresh array at an allocation site, replacing any array already recorded there.
Set<SimValue>	arrayLoad(AllocationSite site, SimValue index)	Reads every value an element of one array may hold.
Set<SimValue>	arrayLoadForRef(Set<AllocationSite> sites, SimValue index)	Reads an element across every array a reference may point to.
SimHeap	arrayStore(AllocationSite site, SimValue index, SimValue value)	Adds a value to an element of one array; no-op if nothing was allocated at the site.
SimHeap	arrayStoreForRef(Set<AllocationSite> sites, SimValue index, SimValue value)	Weakly updates an element across every array a reference may point to.
SimHeap	copy()
Set<AllocationSite>	getAllArraySites()
Set<AllocationSite>	getAllObjectSites()
Set<AllocationSite>	getAllSites()
SimArray	getArray(AllocationSite site)
int	getArrayCount()
Set<SimValue>	getField(AllocationSite site, FieldKey field)	Reads every value a field of one object may hold.
Set<SimValue>	getFieldForRef(Set<AllocationSite> sites, FieldKey field)	Reads a field across every object a reference may point to.
HeapMode	getMode()
SimObject	getObject(AllocationSite site)
int	getObjectCount()
Set<SimValue>	getStatic(FieldKey field)
Set<AllocationSite>	getStaticRoots()	The allocation sites any static field may point at.
boolean	hasArray(AllocationSite site)
boolean	hasEscaped(AllocationSite site)
boolean	hasObject(AllocationSite site)
boolean	isEmpty()
SimHeap	markEscaped(AllocationSite site)	Marks the object and array at a site as escaping; no-op if neither exists.
boolean	mayAlias(Set<AllocationSite> sites1, Set<AllocationSite> sites2)	Tests whether two points-to sets overlap.
SimHeap	merge(SimHeap other)	Joins two heaps at a control flow merge, unioning the values held per site and per static field.
boolean	mustAlias(Set<AllocationSite> sites1, Set<AllocationSite> sites2)	Tests whether two points-to sets are both singletons naming the same site.
SimHeap	putField(AllocationSite site, FieldKey field, SimValue value)	Adds a value to a field of one object; no-op if nothing was allocated at the site.
SimHeap	putFieldForRef(Set<AllocationSite> sites, FieldKey field, SimValue value)	Weakly updates a field across every object a reference may point to.
SimHeap	putStatic(FieldKey field, SimValue value)	Adds a value to a static field, keeping the values already recorded for it.
String	toString()

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

SimHeap

public SimHeap(HeapMode mode)

Creates an empty heap.

Parameters:

mode - whether writes mutate this heap or produce a copy

Method Detail

getMode

public HeapMode getMode()

Returns:

the mode

allocate

public SimHeap allocate(AllocationSite site)

Records a fresh object at an allocation site, replacing any object already recorded there.

Parameters:

site - the allocating instruction

Returns:

this heap in MUTABLE mode, otherwise a copy holding the new object

allocateArray

public SimHeap allocateArray(AllocationSite site,
                             IRType elementType,
                             SimValue length)

Records a fresh array at an allocation site, replacing any array already recorded there.

Parameters:

site - the allocating instruction

elementType - the component type

length - the abstract length

Returns:

this heap in MUTABLE mode, otherwise a copy holding the new array

getObject

public SimObject getObject(AllocationSite site)

Parameters:

site - the allocation site

Returns:

the object at a site, or null if none was allocated there

getArray

public SimArray getArray(AllocationSite site)

Parameters:

site - the allocation site

Returns:

the array at a site, or null if none was allocated there

hasObject

public boolean hasObject(AllocationSite site)

Parameters:

site - the allocation site

Returns:

true if an object was allocated at the site

hasArray

public boolean hasArray(AllocationSite site)

Parameters:

site - the allocation site

Returns:

true if an array was allocated at the site

putField

public SimHeap putField(AllocationSite site,
                        FieldKey field,
                        SimValue value)

Adds a value to a field of one object; no-op if nothing was allocated at the site.

Parameters:

site - the object's allocation site

field - the field written

value - the value stored

Returns:

this heap in MUTABLE mode, otherwise a copy holding the write

putFieldForRef

public SimHeap putFieldForRef(Set<AllocationSite> sites,
                              FieldKey field,
                              SimValue value)

Weakly updates a field across every object a reference may point to.

Parameters:

sites - the points-to set of the receiver

field - the field written

value - the value stored

Returns:

this heap in MUTABLE mode, otherwise a copy holding the writes

getField

public Set<SimValue> getField(AllocationSite site,
                              FieldKey field)

Reads every value a field of one object may hold.

Parameters:

site - the object's allocation site

field - the field read

Returns:

the possible values, empty if nothing was allocated at the site

getFieldForRef

public Set<SimValue> getFieldForRef(Set<AllocationSite> sites,
                                    FieldKey field)

Reads a field across every object a reference may point to.

Parameters:

sites - the points-to set of the receiver

field - the field read

Returns:

the union of the possible values

arrayStore

public SimHeap arrayStore(AllocationSite site,
                          SimValue index,
                          SimValue value)

Adds a value to an element of one array; no-op if nothing was allocated at the site.

Parameters:

site - the array's allocation site

index - the abstract index

value - the value stored

Returns:

this heap in MUTABLE mode, otherwise a copy holding the write

arrayStoreForRef

public SimHeap arrayStoreForRef(Set<AllocationSite> sites,
                                SimValue index,
                                SimValue value)

Weakly updates an element across every array a reference may point to.

Parameters:

sites - the points-to set of the array reference

index - the abstract index

value - the value stored

Returns:

this heap in MUTABLE mode, otherwise a copy holding the writes

arrayLoad

public Set<SimValue> arrayLoad(AllocationSite site,
                               SimValue index)

Reads every value an element of one array may hold.

Parameters:

site - the array's allocation site

index - the abstract index

Returns:

the possible values, empty if nothing was allocated at the site

arrayLoadForRef

public Set<SimValue> arrayLoadForRef(Set<AllocationSite> sites,
                                     SimValue index)

Reads an element across every array a reference may point to.

Parameters:

sites - the points-to set of the array reference

index - the abstract index

Returns:

the union of the possible values

putStatic

public SimHeap putStatic(FieldKey field,
                         SimValue value)

Adds a value to a static field, keeping the values already recorded for it.

Parameters:

field - the static field written

value - the value stored

Returns:

this heap in MUTABLE mode, otherwise a copy holding the write

getStatic

public Set<SimValue> getStatic(FieldKey field)

Parameters:

field - the static field to read

Returns:

an unmodifiable view of the values a static field may hold, empty if it was never written

getStaticRoots

public Set<AllocationSite> getStaticRoots()

The allocation sites any static field may point at. A static is a global root, so everything these sites reach is reachable from outside its allocating method.

Returns:

the sites referenced by static fields, empty if none were ever written

markEscaped

public SimHeap markEscaped(AllocationSite site)

Marks the object and array at a site as escaping; no-op if neither exists.

Parameters:

site - the allocation site

Returns:

this heap in MUTABLE mode, otherwise a copy holding the mark

hasEscaped

public boolean hasEscaped(AllocationSite site)

Parameters:

site - the allocation site

Returns:

true if the object or array allocated at the site is marked as escaping

mayAlias

public boolean mayAlias(Set<AllocationSite> sites1,
                        Set<AllocationSite> sites2)

Tests whether two points-to sets overlap.

Parameters:

sites1 - the first points-to set

sites2 - the second points-to set

Returns:

true if they share a site

mustAlias

public boolean mustAlias(Set<AllocationSite> sites1,
                         Set<AllocationSite> sites2)

Tests whether two points-to sets are both singletons naming the same site.

Parameters:

sites1 - the first points-to set

sites2 - the second points-to set

Returns:

true if the references necessarily denote the same allocation

merge

public SimHeap merge(SimHeap other)

Joins two heaps at a control flow merge, unioning the values held per site and per static field.

Parameters:

other - the heap arriving on the other path

Returns:

a new heap, COPY_ON_MERGE if either input was

copy

public SimHeap copy()

Returns:

a heap with the same mode and fresh maps sharing the same objects, arrays, and value sets

getAllObjectSites

public Set<AllocationSite> getAllObjectSites()

Returns:

an unmodifiable view of the sites that allocated objects

getAllArraySites

public Set<AllocationSite> getAllArraySites()

Returns:

an unmodifiable view of the sites that allocated arrays

getAllSites

public Set<AllocationSite> getAllSites()

Returns:

a new set of every object and array allocation site

getObjectCount

public int getObjectCount()

Returns:

the number of allocated objects

getArrayCount

public int getArrayCount()

Returns:

the number of allocated arrays

isEmpty

public boolean isEmpty()

Returns:

true if no objects, arrays, or static fields are recorded

toString

public String toString()

Overrides:

toString in class Object