Docjar: A Java Source and Docuemnt Enginecom.*    java.*    javax.*    org.*    all    new    plug-in

Quick Search    Search Deep

Compil3r.Quad
Class BDDPointerAnalysis  view BDDPointerAnalysis download BDDPointerAnalysis.java

java.lang.Object
  extended byCompil3r.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()