Overview  Package   Class  Use  Deprecated  Index
Home >> All >> Compil3r >> [ Quad overview ]	PREV CLASS  NEXT CLASS
SUMMARY:  JAVADOC |  SOURCE |  DOWNLOAD | NESTED | FIELD | CONSTR | METHOD	DETAIL: FIELD | CONSTR | METHOD

---

Compil3r.Quad
Class BDDPointerAnalysis  

java.lang.Object
  Compil3r.Quad.BDDPointerAnalysis

---

public class BDDPointerAnalysis

extends java.lang.Object

This is an implementation of the "Points-to Analysis using BDDs" algorithm described in the PLDI 2003 paper by Berndl, Lhotak, Qian, Hendren and Umanee. This code is based on their original implementation available at: http://www.sable.mcgill.ca/bdd/. This version has been rewritten in Java and requires the open-source JavaBDD library, available at http://javabdd.sf.net. This implementation extends Berndl et al.'s algorithm to support on-the-fly computation of the call graph using BDDs. See the handleVirtualCalls() method.

Version:

$Id: BDDPointerAnalysis.java,v 1.31 2003/07/16 09:00:32 joewhaley Exp $

---

Nested Class Summary
class	BDDPointerAnalysis.BDDCallGraph

 

Field Summary
(package private)  org.sf.javabdd.BDD	aC
static boolean	ALL_CONCRETE
private  org.sf.javabdd.BDDFactory	bdd           Singleton BDD object that provides access to BDD functions.
(package private)  java.util.HashSet	callGraphEdges
(package private)  java.util.HashMap	callSiteToTargets
(package private)  org.sf.javabdd.BDD	cC
(package private)  boolean	change
(package private)  java.util.Set	class_initializers
(package private)  org.sf.javabdd.BDD	cTypes
static int	DEFAULT_CACHE_SIZE           The absolute maximum number of variables that we will ever use in the BDD.
static int	DEFAULT_NODE_COUNT           The default initial node count.
(package private)  int[]	domainBits
(package private)  int[]	domainSpos
(package private)  org.sf.javabdd.BDD	edgeSet
(package private)  org.sf.javabdd.BDDDomain	FD
(package private)  Util.Collections.IndexMap	fieldIndexMap
(package private)  org.sf.javabdd.BDD	fieldPt
static boolean	FORCE_GC
(package private)  org.sf.javabdd.BDDDomain	H1
(package private)  org.sf.javabdd.BDD	H1andFDset
(package private)  org.sf.javabdd.BDD	H1andT3set
(package private)  org.sf.javabdd.BDDPairing	H1ToH2
(package private)  org.sf.javabdd.BDDDomain	H2
(package private)  org.sf.javabdd.BDDPairing	H2ToH1
(package private)  Util.Collections.IndexMap	heapobjIndexMap
static boolean	IGNORE_CLINIT
static boolean	IGNORE_THREADS
static boolean	INCREMENTAL_ITERATION
static boolean	INCREMENTAL_POINTSTO
(package private)  int	last_heapobjIndex
(package private)  int	last_methodIndex
(package private)  int	last_typeIndex
(package private)  int	last_vcalls
(package private)  org.sf.javabdd.BDD	loadAss
(package private)  org.sf.javabdd.BDD	loadPt
(package private)  org.sf.javabdd.BDD	loads
(package private)  int[][]	localOrders
(package private)  long	method_summary_time
(package private)  Util.Collections.IndexMap	methodIndexMap
static boolean	NO_HEAP
static boolean	NO_TYPE_FILTERING
(package private)  org.sf.javabdd.BDD	oldPointsTo
(package private)  org.sf.javabdd.BDD	pointsTo
(package private)  org.sf.javabdd.BDD	storePt
(package private)  org.sf.javabdd.BDD	stores
(package private)  org.sf.javabdd.BDDDomain	T1
(package private)  org.sf.javabdd.BDD	T1set
(package private)  org.sf.javabdd.BDDDomain	T2
(package private)  org.sf.javabdd.BDD	T2set
(package private)  org.sf.javabdd.BDDPairing	T2ToT1
(package private)  org.sf.javabdd.BDDDomain	T3
(package private)  org.sf.javabdd.BDDDomain	T4
(package private)  Util.Collections.IndexMap	targetIndexMap
(package private)  java.util.Set	thread_runs
static boolean	TRACE
static boolean	TRACE_INST
static boolean	TRACE_VIRTUAL
(package private)  org.sf.javabdd.BDD	typeFilter
(package private)  Util.Collections.IndexMap	typeIndexMap
(package private)  org.sf.javabdd.BDDDomain	V1
(package private)  org.sf.javabdd.BDD	V1set
(package private)  org.sf.javabdd.BDDPairing	V1ToV2
(package private)  org.sf.javabdd.BDDDomain	V2
(package private)  org.sf.javabdd.BDDPairing	V2ToV1
(package private)  Util.Collections.IndexMap	variableIndexMap
(package private)  org.sf.javabdd.BDD	vC
(package private)  java.util.List	virtualCallMethods
(package private)  java.util.List	virtualCallReceivers
(package private)  java.util.List	virtualCallSites
(package private)  java.util.HashSet	visitedMethods
(package private)  org.sf.javabdd.BDD	vtable_bdd

 

Constructor Summary

BDDPointerAnalysis()

BDDPointerAnalysis(java.lang.String bddpackage, int nodeCount, int cacheSize)

 

Method Summary
void	addAllocType(MethodSummary.Node site, Clazz.jq_Reference type)
void	addClassInit(Clazz.jq_Type t)
void	addClassType(Clazz.jq_Reference type)
void	addDirectAssignment(MethodSummary.Node dest, MethodSummary.Node src)
void	addDirectAssignment(MethodSummary.Node dest, java.util.Set srcs)
void	addFieldStore(MethodSummary.Node base, Clazz.jq_Field f, MethodSummary.Node src)
void	addFieldStore(MethodSummary.Node base, Clazz.jq_Field f, java.util.Set srcs)
void	addLoadField(MethodSummary.Node dest, MethodSummary.Node base, Clazz.jq_Field f)
void	addLoadField(java.util.Set dests, MethodSummary.Node base, Clazz.jq_Field f)
void	addObjectAllocation(MethodSummary.Node dest, MethodSummary.Node site)
void	addThreadRun(MethodSummary.Node n, Clazz.jq_Class c)
void	addVarType(MethodSummary.Node var, Clazz.jq_Reference type)
void	bindParameters_native(MethodSummary caller, ProgramLocation mc)
void	bindParameters(MethodSummary caller, ProgramLocation mc, MethodSummary callee)
void	calculateTypeFilter()
(package private)  void	calculateTypeHierarchy()
void	calculateVTables()
(package private)  void	done()
void	dumpNode(MethodSummary.Node n)
void	dumpResults(CallGraph cg)
(package private)  int	fillInVarIndices(int start, int[] varorder, int numdoms, org.sf.javabdd.BDDDomain[] doms)
(package private)  Clazz.jq_Field	getField(int index)
(package private)  int	getFieldIndex(Clazz.jq_Field f)
(package private)  MethodSummary.Node	getHeapobj(int index)
(package private)  int	getHeapobjIndex(MethodSummary.Node site)
(package private)  Util.Collections.IndexMap	getIndexMap(org.sf.javabdd.BDDDomain d)
(package private)  Clazz.jq_InstanceMethod	getMethod(int index)
(package private)  int	getMethodIndex(Clazz.jq_InstanceMethod f)
java.util.Set	getPointsTo(MethodSummary.Node n)
(package private)  Clazz.jq_InstanceMethod	getTarget(int index)
(package private)  int	getTargetIndex(Clazz.jq_InstanceMethod f)
(package private)  Clazz.jq_Reference	getType(int index)
(package private)  int	getTypeIndex(Clazz.jq_Reference f)
(package private)  MethodSummary.Node	getVariable(int index)
(package private)  int	getVariableIndex(MethodSummary.Node dest)
(package private)  void	getVariableMap(int[] map, org.sf.javabdd.BDDDomain[] doms, int domnum)
CallGraph	goIncremental(java.util.Collection roots)
CallGraph	goNonincremental(java.util.Collection roots)
void	handleMethodSummary(MethodSummary ms)
void	handleNode(MethodSummary.Node n)
void	handleVirtualCalls(org.sf.javabdd.BDD newPointsTo)
static void	main(java.lang.String[] args)
(package private)  void	makeVarOrdering(int[] varorder)
(package private)  void	printSet(java.lang.String desc, org.sf.javabdd.BDD b)
(package private)  void	remapping(int[] varorder, int[] maps)
(package private)  void	reset()
void	solveIncremental()
void	solveNonincremental()

 

Methods inherited from class java.lang.Object

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

 

Field Detail

TRACE

public static final boolean TRACE

See Also:

Constant Field Values

---

TRACE_INST

public static final boolean TRACE_INST

See Also:

Constant Field Values

---

TRACE_VIRTUAL

public static final boolean TRACE_VIRTUAL

See Also:

Constant Field Values

---

DEFAULT_NODE_COUNT

public static final int DEFAULT_NODE_COUNT

The default initial node count. Smaller values save memory for smaller problems, larger values save the time to grow the node tables on larger problems.

---

DEFAULT_CACHE_SIZE

public static final int DEFAULT_CACHE_SIZE

The absolute maximum number of variables that we will ever use in the BDD. Smaller numbers will be more efficient, larger numbers will allow larger programs to be analyzed.

See Also:

Constant Field Values

---

bdd

private final org.sf.javabdd.BDDFactory bdd

Singleton BDD object that provides access to BDD functions.

---

domainBits

int[] domainBits

---

domainSpos

int[] domainSpos

---

V1

org.sf.javabdd.BDDDomain V1

---

V2

org.sf.javabdd.BDDDomain V2

---

FD

org.sf.javabdd.BDDDomain FD

---

H1

org.sf.javabdd.BDDDomain H1

---

H2

org.sf.javabdd.BDDDomain H2

---

T1

org.sf.javabdd.BDDDomain T1

---

T2

org.sf.javabdd.BDDDomain T2

---

T3

org.sf.javabdd.BDDDomain T3

---

T4

org.sf.javabdd.BDDDomain T4

---

V1ToV2

org.sf.javabdd.BDDPairing V1ToV2

---

V2ToV1

org.sf.javabdd.BDDPairing V2ToV1

---

H1ToH2

org.sf.javabdd.BDDPairing H1ToH2

---

H2ToH1

org.sf.javabdd.BDDPairing H2ToH1

---

T2ToT1

org.sf.javabdd.BDDPairing T2ToT1

---

pointsTo

org.sf.javabdd.BDD pointsTo

---

edgeSet

org.sf.javabdd.BDD edgeSet

---

typeFilter

org.sf.javabdd.BDD typeFilter

---

stores

org.sf.javabdd.BDD stores

---

loads

org.sf.javabdd.BDD loads

---

storePt

org.sf.javabdd.BDD storePt

---

fieldPt

org.sf.javabdd.BDD fieldPt

---

loadAss

org.sf.javabdd.BDD loadAss

---

loadPt

org.sf.javabdd.BDD loadPt

---

V1set

org.sf.javabdd.BDD V1set

---

T1set

org.sf.javabdd.BDD T1set

---

T2set

org.sf.javabdd.BDD T2set

---

H1andFDset

org.sf.javabdd.BDD H1andFDset

---

H1andT3set

org.sf.javabdd.BDD H1andT3set

---

localOrders

int[][] localOrders

---

INCREMENTAL_POINTSTO

public static boolean INCREMENTAL_POINTSTO

---

INCREMENTAL_ITERATION

public static boolean INCREMENTAL_ITERATION

---

FORCE_GC

public static boolean FORCE_GC

---

change

boolean change

---

cTypes

org.sf.javabdd.BDD cTypes

---

IGNORE_CLINIT

public static final boolean IGNORE_CLINIT

See Also:

Constant Field Values

---

class_initializers

java.util.Set class_initializers

---

IGNORE_THREADS

public static final boolean IGNORE_THREADS

See Also:

Constant Field Values

---

thread_runs

java.util.Set thread_runs

---

visitedMethods

java.util.HashSet visitedMethods

---

NO_HEAP

public static boolean NO_HEAP

---

callSiteToTargets

java.util.HashMap callSiteToTargets

---

virtualCallSites

java.util.List virtualCallSites

---

virtualCallReceivers

java.util.List virtualCallReceivers

---

virtualCallMethods

java.util.List virtualCallMethods

---

last_vcalls

int last_vcalls

---

method_summary_time

long method_summary_time

---

callGraphEdges

java.util.HashSet callGraphEdges

---

variableIndexMap

Util.Collections.IndexMap variableIndexMap

---

heapobjIndexMap

Util.Collections.IndexMap heapobjIndexMap

---

fieldIndexMap

Util.Collections.IndexMap fieldIndexMap

---

typeIndexMap

Util.Collections.IndexMap typeIndexMap

---

methodIndexMap

Util.Collections.IndexMap methodIndexMap

---

targetIndexMap

Util.Collections.IndexMap targetIndexMap

---

aC

org.sf.javabdd.BDD aC

---

vC

org.sf.javabdd.BDD vC

---

cC

org.sf.javabdd.BDD cC

---

last_typeIndex

int last_typeIndex

---

NO_TYPE_FILTERING

public static boolean NO_TYPE_FILTERING

---

vtable_bdd

org.sf.javabdd.BDD vtable_bdd

---

last_methodIndex

int last_methodIndex

---

last_heapobjIndex

int last_heapobjIndex

---

ALL_CONCRETE

public static final boolean ALL_CONCRETE

See Also:

Constant Field Values

---

oldPointsTo

org.sf.javabdd.BDD oldPointsTo

Constructor Detail

BDDPointerAnalysis

public BDDPointerAnalysis()

---

BDDPointerAnalysis

public BDDPointerAnalysis(java.lang.String bddpackage,
                          int nodeCount,
                          int cacheSize)

Method Detail

makeVarOrdering

void makeVarOrdering(int[] varorder)

---

fillInVarIndices

int fillInVarIndices(int start,
                     int[] varorder,
                     int numdoms,
                     org.sf.javabdd.BDDDomain[] doms)

---

getVariableMap

void getVariableMap(int[] map,
                    org.sf.javabdd.BDDDomain[] doms,
                    int domnum)

---

remapping

void remapping(int[] varorder,
               int[] maps)

---

reset

void reset()

---

done

void done()

---

main

public static void main(java.lang.String[] args)

---

goNonincremental

public CallGraph goNonincremental(java.util.Collection roots)

---

goIncremental

public CallGraph goIncremental(java.util.Collection roots)

---

getIndexMap

Util.Collections.IndexMap getIndexMap(org.sf.javabdd.BDDDomain d)

---

printSet

void printSet(java.lang.String desc,
              org.sf.javabdd.BDD b)

---

dumpResults

public void dumpResults(CallGraph cg)

---

getPointsTo

public java.util.Set getPointsTo(MethodSummary.Node n)

---

dumpNode

public void dumpNode(MethodSummary.Node n)

---

addClassInit

public void addClassInit(Clazz.jq_Type t)

---

addThreadRun

public void addThreadRun(MethodSummary.Node n,
                         Clazz.jq_Class c)

---

handleNode

public void handleNode(MethodSummary.Node n)

---

handleMethodSummary

public void handleMethodSummary(MethodSummary ms)

---

handleVirtualCalls

public void handleVirtualCalls(org.sf.javabdd.BDD newPointsTo)

---

bindParameters

public void bindParameters(MethodSummary caller,
                           ProgramLocation mc,
                           MethodSummary callee)

---

bindParameters_native

public void bindParameters_native(MethodSummary caller,
                                  ProgramLocation mc)

---

getVariableIndex

int getVariableIndex(MethodSummary.Node dest)

---

getHeapobjIndex

int getHeapobjIndex(MethodSummary.Node site)

---

getFieldIndex

int getFieldIndex(Clazz.jq_Field f)

---

getTypeIndex

int getTypeIndex(Clazz.jq_Reference f)

---

getMethodIndex

int getMethodIndex(Clazz.jq_InstanceMethod f)

---

getTargetIndex

int getTargetIndex(Clazz.jq_InstanceMethod f)

---

getVariable

MethodSummary.Node getVariable(int index)

---

getHeapobj

MethodSummary.Node getHeapobj(int index)

---

getField

Clazz.jq_Field getField(int index)

---

getType

Clazz.jq_Reference getType(int index)

---

getMethod

Clazz.jq_InstanceMethod getMethod(int index)

---

getTarget

Clazz.jq_InstanceMethod getTarget(int index)

---

addObjectAllocation

public void addObjectAllocation(MethodSummary.Node dest,
                                MethodSummary.Node site)

---

addDirectAssignment

public void addDirectAssignment(MethodSummary.Node dest,
                                java.util.Set srcs)

---

addDirectAssignment

public void addDirectAssignment(MethodSummary.Node dest,
                                MethodSummary.Node src)

---

addLoadField

public void addLoadField(MethodSummary.Node dest,
                         MethodSummary.Node base,
                         Clazz.jq_Field f)

---

addLoadField

public void addLoadField(java.util.Set dests,
                         MethodSummary.Node base,
                         Clazz.jq_Field f)

---

addFieldStore

public void addFieldStore(MethodSummary.Node base,
                          Clazz.jq_Field f,
                          MethodSummary.Node src)

---

addFieldStore

public void addFieldStore(MethodSummary.Node base,
                          Clazz.jq_Field f,
                          java.util.Set srcs)

---

addClassType

public void addClassType(Clazz.jq_Reference type)

---

addAllocType

public void addAllocType(MethodSummary.Node site,
                         Clazz.jq_Reference type)

---

addVarType

public void addVarType(MethodSummary.Node var,
                       Clazz.jq_Reference type)

---

calculateTypeHierarchy

void calculateTypeHierarchy()

---

calculateTypeFilter

public void calculateTypeFilter()

---

calculateVTables

public void calculateVTables()

---

solveNonincremental

public void solveNonincremental()

---

solveIncremental

public void solveIncremental()

---

Overview  Package   Class  Use  Deprecated  Index
Home >> All >> Compil3r >> [ Quad overview ]	PREV CLASS  NEXT CLASS
SUMMARY:  JAVADOC |  SOURCE |  DOWNLOAD | NESTED | FIELD | CONSTR | METHOD	DETAIL: FIELD | CONSTR | METHOD

---