import Analysis.CallGraph.*;
import Analysis.Liveness;
import Analysis.ArrayReferencees;
+import Analysis.OoOJava.RBlockRelationAnalysis;
+import Analysis.OoOJava.RBlockStatusAnalysis;
import IR.*;
import IR.Flat.*;
import IR.Tree.Modifiers;
public class DisjointAnalysis {
- ///////////////////////////////////////////
- //
- // Public interface to discover possible
- // aliases in the program under analysis
- //
- ///////////////////////////////////////////
-
- public HashSet<AllocSite>
- getFlaggedAllocationSitesReachableFromTask(TaskDescriptor td) {
- checkAnalysisComplete();
- return getFlaggedAllocationSitesReachableFromTaskPRIVATE(td);
- }
+ ///////////////////////////////////////////
+ //
+ // Public interface to discover possible
+ // sharing in the program under analysis
+ //
+ ///////////////////////////////////////////
+
+ // if an object allocated at the target site may be
+ // reachable from both an object from root1 and an
+ // object allocated at root2, return TRUE
+ public boolean mayBothReachTarget( FlatMethod fm,
+ FlatNew fnRoot1,
+ FlatNew fnRoot2,
+ FlatNew fnTarget ) {
+
+ AllocSite asr1 = getAllocationSiteFromFlatNew( fnRoot1 );
+ AllocSite asr2 = getAllocationSiteFromFlatNew( fnRoot2 );
+ assert asr1.isFlagged();
+ assert asr2.isFlagged();
+
+ AllocSite ast = getAllocationSiteFromFlatNew( fnTarget );
+ ReachGraph rg = getPartial( fm.getMethod() );
+
+ return rg.mayBothReachTarget( asr1, asr2, ast );
+ }
+
+ // similar to the method above, return TRUE if ever
+ // more than one object from the root allocation site
+ // may reach an object from the target site
+ public boolean mayManyReachTarget( FlatMethod fm,
+ FlatNew fnRoot,
+ FlatNew fnTarget ) {
+
+ AllocSite asr = getAllocationSiteFromFlatNew( fnRoot );
+ assert asr.isFlagged();
+
+ AllocSite ast = getAllocationSiteFromFlatNew( fnTarget );
+ ReachGraph rg = getPartial( fm.getMethod() );
+
+ return rg.mayManyReachTarget( asr, ast );
+ }
+
+
+
+
+ public HashSet<AllocSite>
+ getFlaggedAllocationSitesReachableFromTask(TaskDescriptor td) {
+ checkAnalysisComplete();
+ return getFlaggedAllocationSitesReachableFromTaskPRIVATE(td);
+ }
- public AllocSite getAllocationSiteFromFlatNew(FlatNew fn) {
- checkAnalysisComplete();
- return getAllocSiteFromFlatNewPRIVATE(fn);
- }
+ public AllocSite getAllocationSiteFromFlatNew(FlatNew fn) {
+ checkAnalysisComplete();
+ return getAllocSiteFromFlatNewPRIVATE(fn);
+ }
- public AllocSite getAllocationSiteFromHeapRegionNodeID(Integer id) {
- checkAnalysisComplete();
- return mapHrnIdToAllocSite.get(id);
- }
+ public AllocSite getAllocationSiteFromHeapRegionNodeID(Integer id) {
+ checkAnalysisComplete();
+ return mapHrnIdToAllocSite.get(id);
+ }
- public Set<HeapRegionNode> hasPotentialSharing(Descriptor taskOrMethod,
- int paramIndex1,
- int paramIndex2) {
- checkAnalysisComplete();
- ReachGraph rg=mapDescriptorToCompleteReachGraph.get(taskOrMethod);
- FlatMethod fm=state.getMethodFlat(taskOrMethod);
- assert(rg != null);
- return rg.mayReachSharedObjects(fm, paramIndex1, paramIndex2);
- }
+ public Set<HeapRegionNode> hasPotentialSharing(Descriptor taskOrMethod,
+ int paramIndex1,
+ int paramIndex2) {
+ checkAnalysisComplete();
+ ReachGraph rg=mapDescriptorToCompleteReachGraph.get(taskOrMethod);
+ FlatMethod fm=state.getMethodFlat(taskOrMethod);
+ assert(rg != null);
+ return rg.mayReachSharedObjects(fm, paramIndex1, paramIndex2);
+ }
- public Set<HeapRegionNode> hasPotentialSharing(Descriptor taskOrMethod,
- int paramIndex, AllocSite alloc) {
- checkAnalysisComplete();
- ReachGraph rg = mapDescriptorToCompleteReachGraph.get(taskOrMethod);
- FlatMethod fm=state.getMethodFlat(taskOrMethod);
- assert (rg != null);
- return rg.mayReachSharedObjects(fm, paramIndex, alloc);
- }
+ public Set<HeapRegionNode> hasPotentialSharing(Descriptor taskOrMethod,
+ int paramIndex, AllocSite alloc) {
+ checkAnalysisComplete();
+ ReachGraph rg = mapDescriptorToCompleteReachGraph.get(taskOrMethod);
+ FlatMethod fm=state.getMethodFlat(taskOrMethod);
+ assert (rg != null);
+ return rg.mayReachSharedObjects(fm, paramIndex, alloc);
+ }
- public Set<HeapRegionNode> hasPotentialSharing(Descriptor taskOrMethod,
- AllocSite alloc, int paramIndex) {
- checkAnalysisComplete();
- ReachGraph rg = mapDescriptorToCompleteReachGraph.get(taskOrMethod);
- FlatMethod fm=state.getMethodFlat(taskOrMethod);
- assert (rg != null);
- return rg.mayReachSharedObjects(fm, paramIndex, alloc);
- }
+ public Set<HeapRegionNode> hasPotentialSharing(Descriptor taskOrMethod,
+ AllocSite alloc, int paramIndex) {
+ checkAnalysisComplete();
+ ReachGraph rg = mapDescriptorToCompleteReachGraph.get(taskOrMethod);
+ FlatMethod fm=state.getMethodFlat(taskOrMethod);
+ assert (rg != null);
+ return rg.mayReachSharedObjects(fm, paramIndex, alloc);
+ }
- public Set<HeapRegionNode> hasPotentialSharing(Descriptor taskOrMethod,
- AllocSite alloc1, AllocSite alloc2) {
- checkAnalysisComplete();
- ReachGraph rg = mapDescriptorToCompleteReachGraph.get(taskOrMethod);
- assert (rg != null);
- return rg.mayReachSharedObjects(alloc1, alloc2);
- }
+ public Set<HeapRegionNode> hasPotentialSharing(Descriptor taskOrMethod,
+ AllocSite alloc1, AllocSite alloc2) {
+ checkAnalysisComplete();
+ ReachGraph rg = mapDescriptorToCompleteReachGraph.get(taskOrMethod);
+ assert (rg != null);
+ return rg.mayReachSharedObjects(alloc1, alloc2);
+ }
- public String prettyPrintNodeSet(Set<HeapRegionNode> s) {
- checkAnalysisComplete();
+ public String prettyPrintNodeSet(Set<HeapRegionNode> s) {
+ checkAnalysisComplete();
- String out = "{\n";
+ String out = "{\n";
- Iterator<HeapRegionNode> i = s.iterator();
- while (i.hasNext()) {
- HeapRegionNode n = i.next();
+ Iterator<HeapRegionNode> i = s.iterator();
+ while (i.hasNext()) {
+ HeapRegionNode n = i.next();
- AllocSite as = n.getAllocSite();
- if (as == null) {
- out += " " + n.toString() + ",\n";
- } else {
- out += " " + n.toString() + ": " + as.toStringVerbose()
- + ",\n";
- }
- }
+ AllocSite as = n.getAllocSite();
+ if (as == null) {
+ out += " " + n.toString() + ",\n";
+ } else {
+ out += " " + n.toString() + ": " + as.toStringVerbose()
+ + ",\n";
+ }
+ }
- out += "}\n";
- return out;
- }
+ out += "}\n";
+ return out;
+ }
// use the methods given above to check every possible sharing class
// between task parameters and flagged allocation sites reachable
bw.close();
}
+
+
// this version of writeAllSharing is for Java programs that have no tasks
+ // ***********************************
+ // WARNING: THIS DOES NOT DO THE RIGHT THING, REPORTS 0 ALWAYS!
+ // It should use mayBothReachTarget and mayManyReachTarget like
+ // OoOJava does to query analysis results
+ // ***********************************
public void writeAllSharingJava(String outputFile,
String timeReport,
String justTime,
//
///////////////////////////////////////////
+
+
protected void checkAnalysisComplete() {
if( !analysisComplete ) {
throw new Error("Warning: public interface method called while analysis is running.");
}
+
+
+
+
// run in faster mode, only when bugs wrung out!
public static boolean releaseMode;
// should attempt to be deterministic
public static boolean determinismDesired;
+ // when we want to enforce determinism in the
+ // analysis we need to sort descriptors rather
+ // than toss them in efficient sets, use this
+ public static DescriptorComparator dComp =
+ new DescriptorComparator();
+
+
// data from the compiler
public State state;
public CallGraph callGraph;
public Liveness liveness;
public ArrayReferencees arrayReferencees;
+ public RBlockRelationAnalysis rblockRel;
+ public RBlockStatusAnalysis rblockStatus;
public TypeUtil typeUtil;
public int allocationDepth;
+
+ protected boolean doEffectsAnalysis = false;
+ protected EffectsAnalysis effectsAnalysis;
// data structure for public interface
- private Hashtable<Descriptor, HashSet<AllocSite> > mapDescriptorToAllocSiteSet;
+ private Hashtable< Descriptor, HashSet<AllocSite> >
+ mapDescriptorToAllocSiteSet;
// for public interface methods to warn that they
protected Hashtable< Descriptor, Set<Descriptor> >
mapDescriptorToSetDependents;
+ // if the analysis client wants to flag allocation sites
+ // programmatically, it should provide a set of FlatNew
+ // statements--this may be null if unneeded
+ protected Set<FlatNew> sitesToFlag;
+
// maps each flat new to one analysis abstraction
// allocate site object, these exist outside reach graphs
protected Hashtable<FlatNew, AllocSite>
static protected Hashtable<FlatNode, ReachGraph> fn2rg =
new Hashtable<FlatNode, ReachGraph>();
+ private Hashtable<FlatCall, Descriptor> fc2enclosing;
+
// allocate various structures that are not local
// to a single class method--should be done once
if( determinismDesired ) {
// use an ordered set
- descriptorsToAnalyze
- = new TreeSet<Descriptor>( new DescriptorComparator() );
-
+ descriptorsToAnalyze = new TreeSet<Descriptor>( dComp );
} else {
// otherwise use a speedy hashset
descriptorsToAnalyze = new HashSet<Descriptor>();
mapBackEdgeToMonotone =
new Hashtable<FlatNode, ReachGraph>();
-
+
mapHrnIdToAllocSite =
new Hashtable<Integer, AllocSite>();
new Hashtable<Descriptor, ReachGraph>();
pm = new PointerMethod();
+
+ fc2enclosing = new Hashtable<FlatCall, Descriptor>();
}
TypeUtil tu,
CallGraph cg,
Liveness l,
- ArrayReferencees ar
- ) throws java.io.IOException {
- init( s, tu, cg, l, ar );
+ ArrayReferencees ar,
+ Set<FlatNew> sitesToFlag,
+ RBlockRelationAnalysis rra,
+ RBlockStatusAnalysis rsa
+ ) {
+ init( s, tu, cg, l, ar, sitesToFlag, rra, rsa, false );
+ }
+
+ public DisjointAnalysis( State s,
+ TypeUtil tu,
+ CallGraph cg,
+ Liveness l,
+ ArrayReferencees ar,
+ Set<FlatNew> sitesToFlag,
+ RBlockRelationAnalysis rra,
+ RBlockStatusAnalysis rsa,
+ boolean suppressOutput
+ ) {
+ init( s, tu, cg, l, ar, sitesToFlag, rra, rsa, suppressOutput );
}
protected void init( State state,
TypeUtil typeUtil,
CallGraph callGraph,
Liveness liveness,
- ArrayReferencees arrayReferencees
- ) throws java.io.IOException {
+ ArrayReferencees arrayReferencees,
+ Set<FlatNew> sitesToFlag,
+ RBlockRelationAnalysis rra,
+ RBlockStatusAnalysis rsa,
+ boolean suppressOutput
+ ) {
analysisComplete = false;
- this.state = state;
- this.typeUtil = typeUtil;
- this.callGraph = callGraph;
- this.liveness = liveness;
- this.arrayReferencees = arrayReferencees;
+ this.state = state;
+ this.typeUtil = typeUtil;
+ this.callGraph = callGraph;
+ this.liveness = liveness;
+ this.arrayReferencees = arrayReferencees;
+ this.sitesToFlag = sitesToFlag;
+ this.rblockRel = rra;
+ this.rblockStatus = rsa;
+
+ if( rblockRel != null ) {
+ doEffectsAnalysis = true;
+ effectsAnalysis = new EffectsAnalysis();
+ }
+
this.allocationDepth = state.DISJOINTALLOCDEPTH;
this.releaseMode = state.DISJOINTRELEASEMODE;
this.determinismDesired = state.DISJOINTDETERMINISM;
- this.writeFinalDOTs = state.DISJOINTWRITEDOTS && !state.DISJOINTWRITEALL;
- this.writeAllIncrementalDOTs = state.DISJOINTWRITEDOTS && state.DISJOINTWRITEALL;
+ this.writeFinalDOTs = state.DISJOINTWRITEDOTS && !state.DISJOINTWRITEALL && !suppressOutput;
+ this.writeAllIncrementalDOTs = state.DISJOINTWRITEDOTS && state.DISJOINTWRITEALL && !suppressOutput;
this.takeDebugSnapshots = state.DISJOINTSNAPSYMBOL != null;
this.descSymbolDebug = state.DISJOINTSNAPSYMBOL;
double timeStartAnalysis = (double) System.nanoTime();
// start interprocedural fixed-point computation
- analyzeMethods();
+ try {
+ analyzeMethods();
+ } catch( IOException e ) {
+ throw new Error( "IO Exception while writing disjointness analysis output." );
+ }
+
analysisComplete=true;
+
double timeEndAnalysis = (double) System.nanoTime();
double dt = (timeEndAnalysis - timeStartAnalysis)/(Math.pow( 10.0, 9.0 ) );
- String treport = String.format( "The reachability analysis took %.3f sec.", dt );
+
+ String treport;
+ if( sitesToFlag != null ) {
+ treport = String.format( "Disjoint reachability analysis flagged %d sites and took %.3f sec.", sitesToFlag.size(), dt );
+ } else {
+ treport = String.format( "Disjoint reachability analysis took %.3f sec.", dt );
+ }
String justtime = String.format( "%.2f", dt );
System.out.println( treport );
- if( writeFinalDOTs && !writeAllIncrementalDOTs ) {
- writeFinalGraphs();
- }
- if( state.DISJOINTWRITEIHMS ) {
- writeFinalIHMs();
- }
+ try {
+ if( writeFinalDOTs && !writeAllIncrementalDOTs ) {
+ writeFinalGraphs();
+ }
- if( state.DISJOINTALIASFILE != null ) {
- if( state.TASK ) {
- writeAllSharing(state.DISJOINTALIASFILE, treport, justtime, state.DISJOINTALIASTAB, state.lines);
- } else {
- writeAllSharingJava(state.DISJOINTALIASFILE,
- treport,
- justtime,
- state.DISJOINTALIASTAB,
- state.lines
- );
+ if( state.DISJOINTWRITEIHMS && !suppressOutput ) {
+ writeFinalIHMs();
+ }
+
+ if( state.DISJOINTWRITEINITCONTEXTS && !suppressOutput ) {
+ writeInitialContexts();
}
+
+ if( state.DISJOINTALIASFILE != null && !suppressOutput ) {
+ if( state.TASK ) {
+ writeAllSharing(state.DISJOINTALIASFILE, treport, justtime, state.DISJOINTALIASTAB, state.lines);
+ } else {
+ writeAllSharingJava(state.DISJOINTALIASFILE,
+ treport,
+ justtime,
+ state.DISJOINTALIASTAB,
+ state.lines
+ );
+ }
+ }
+ } catch( IOException e ) {
+ throw new Error( "IO Exception while writing disjointness analysis output." );
}
+
}
System.out.println( " "+dNext );
}
}
+ }
- if( state.DISJOINTDVISITSTACKEESONTOP ) {
-
- if( state.DISJOINTDEBUGSCHEDULING ) {
- System.out.println( " contexts changed, scheduling callees for analysis:" );
- }
-
- depsItr = calleesToEnqueue.iterator();
- while( depsItr.hasNext() ) {
- Descriptor dNext = depsItr.next();
- enqueue( dNext );
-
- if( state.DISJOINTDEBUGSCHEDULING ) {
- System.out.println( " "+dNext );
- }
- }
- calleesToEnqueue.clear();
+ // whether or not the method under analysis changed,
+ // we may have some callees that are scheduled for
+ // more analysis, and they should go on the top of
+ // the stack now (in other method-visiting modes they
+ // are already enqueued at this point
+ if( state.DISJOINTDVISITSTACKEESONTOP ) {
+ Iterator<Descriptor> depsItr = calleesToEnqueue.iterator();
+ while( depsItr.hasNext() ) {
+ Descriptor dNext = depsItr.next();
+ enqueue( dNext );
}
+ calleesToEnqueue.clear();
+ }
- } else {
- // we got the result result as the last visit
- // to this method, but we might need to clean
- // something up
- if( state.DISJOINTDVISITSTACKEESONTOP ) {
- calleesToEnqueue.clear();
- }
- }
-
- }
+ }
}
protected ReachGraph analyzeMethod( Descriptor d )
rg.merge( rgParent );
}
}
-
+
if( takeDebugSnapshots &&
d.getSymbol().equals( descSymbolDebug )
// nullified in the graph to reduce edges
//rg.nullifyDeadVars( liveness.getLiveInTemps( fmContaining, fn ) );
-
- TempDescriptor lhs;
- TempDescriptor rhs;
- FieldDescriptor fld;
+ TempDescriptor lhs;
+ TempDescriptor rhs;
+ FieldDescriptor fld;
+ TypeDescriptor tdElement;
+ FieldDescriptor fdElement;
+ FlatSESEEnterNode sese;
+ FlatSESEExitNode fsexn;
// use node type to decide what transfer function
// to apply to the reachability graph
if( fon.getOp().getOp() == Operation.ASSIGN ) {
lhs = fon.getDest();
rhs = fon.getLeft();
- rg.assignTempXEqualToTempY( lhs, rhs );
+
+ // before transfer, do effects analysis support
+ if( doEffectsAnalysis && fmContaining != fmAnalysisEntry ) {
+ if(rblockStatus.isInCriticalRegion(fmContaining, fn)){
+ // x gets status of y
+ if(!rg.isAccessible(rhs)){
+ rg.makeInaccessible(lhs);
+ }
+ }
+ }
+
+ // transfer func
+ rg.assignTempXEqualToTempY( lhs, rhs );
}
break;
TypeDescriptor td = fcn.getType();
assert td != null;
+
+ // before transfer, do effects analysis support
+ if( doEffectsAnalysis && fmContaining != fmAnalysisEntry ) {
+ if(rblockStatus.isInCriticalRegion(fmContaining, fn)){
+ // x gets status of y
+ if(!rg.isAccessible(rhs)){
+ rg.makeInaccessible(lhs);
+ }
+ }
+ }
+ // transfer func
rg.assignTempXEqualToCastedTempY( lhs, rhs, td );
break;
case FKind.FlatFieldNode:
FlatFieldNode ffn = (FlatFieldNode) fn;
+
lhs = ffn.getDst();
rhs = ffn.getSrc();
fld = ffn.getField();
- if( shouldAnalysisTrack( fld.getType() ) ) {
+
+ // before graph transform, possible inject
+ // a stall-site taint
+ if( doEffectsAnalysis && fmContaining != fmAnalysisEntry ) {
+
+ if(rblockStatus.isInCriticalRegion(fmContaining, fn)){
+ // x=y.f, stall y if not accessible
+ // contributes read effects on stall site of y
+ if(!rg.isAccessible(rhs)) {
+ rg.taintStallSite(fn, rhs);
+ }
+
+ // after this, x and y are accessbile.
+ rg.makeAccessible(lhs);
+ rg.makeAccessible(rhs);
+ }
+ }
+
+ if( shouldAnalysisTrack( fld.getType() ) ) {
+ // transfer func
rg.assignTempXEqualToTempYFieldF( lhs, rhs, fld );
}
+
+ // after transfer, use updated graph to
+ // do effects analysis
+ if( doEffectsAnalysis && fmContaining != fmAnalysisEntry ) {
+ effectsAnalysis.analyzeFlatFieldNode( rg, rhs, fld );
+ }
break;
case FKind.FlatSetFieldNode:
FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
+
lhs = fsfn.getDst();
fld = fsfn.getField();
rhs = fsfn.getSrc();
+
+ boolean strongUpdate = false;
+
+ // before transfer func, possibly inject
+ // stall-site taints
+ if( doEffectsAnalysis && fmContaining != fmAnalysisEntry ) {
+
+ if(rblockStatus.isInCriticalRegion(fmContaining, fn)){
+ // x.y=f , stall x and y if they are not accessible
+ // also contribute write effects on stall site of x
+ if(!rg.isAccessible(lhs)) {
+ rg.taintStallSite(fn, lhs);
+ }
+
+ if(!rg.isAccessible(rhs)) {
+ rg.taintStallSite(fn, rhs);
+ }
+
+ // accessible status update
+ rg.makeAccessible(lhs);
+ rg.makeAccessible(rhs);
+ }
+ }
+
if( shouldAnalysisTrack( fld.getType() ) ) {
- rg.assignTempXFieldFEqualToTempY( lhs, fld, rhs );
+ // transfer func
+ strongUpdate = rg.assignTempXFieldFEqualToTempY( lhs, fld, rhs );
}
+
+ // use transformed graph to do effects analysis
+ if( doEffectsAnalysis && fmContaining != fmAnalysisEntry ) {
+ effectsAnalysis.analyzeFlatSetFieldNode( rg, lhs, fld, strongUpdate );
+ }
break;
case FKind.FlatElementNode:
FlatElementNode fen = (FlatElementNode) fn;
+
lhs = fen.getDst();
rhs = fen.getSrc();
- if( shouldAnalysisTrack( lhs.getType() ) ) {
- assert rhs.getType() != null;
- assert rhs.getType().isArray();
-
- TypeDescriptor tdElement = rhs.getType().dereference();
- FieldDescriptor fdElement = getArrayField( tdElement );
-
+ assert rhs.getType() != null;
+ assert rhs.getType().isArray();
+
+ tdElement = rhs.getType().dereference();
+ fdElement = getArrayField( tdElement );
+
+ // before transfer func, possibly inject
+ // stall-site taint
+ if( doEffectsAnalysis && fmContaining != fmAnalysisEntry ) {
+
+ if(rblockStatus.isInCriticalRegion(fmContaining, fn)){
+ // x=y.f, stall y if not accessible
+ // contributes read effects on stall site of y
+ // after this, x and y are accessbile.
+ if(!rg.isAccessible(rhs)) {
+ rg.taintStallSite(fn, rhs);
+ }
+
+ rg.makeAccessible(lhs);
+ rg.makeAccessible(rhs);
+ }
+ }
+
+ if( shouldAnalysisTrack( lhs.getType() ) ) {
+ // transfer func
rg.assignTempXEqualToTempYFieldF( lhs, rhs, fdElement );
}
+
+ // use transformed graph to do effects analysis
+ if( doEffectsAnalysis && fmContaining != fmAnalysisEntry ) {
+ effectsAnalysis.analyzeFlatFieldNode( rg, rhs, fdElement );
+ }
break;
case FKind.FlatSetElementNode:
FlatSetElementNode fsen = (FlatSetElementNode) fn;
- if( arrayReferencees.doesNotCreateNewReaching( fsen ) ) {
- // skip this node if it cannot create new reachability paths
- break;
- }
-
lhs = fsen.getDst();
rhs = fsen.getSrc();
- if( shouldAnalysisTrack( rhs.getType() ) ) {
- assert lhs.getType() != null;
- assert lhs.getType().isArray();
-
- TypeDescriptor tdElement = lhs.getType().dereference();
- FieldDescriptor fdElement = getArrayField( tdElement );
+ assert lhs.getType() != null;
+ assert lhs.getType().isArray();
+
+ tdElement = lhs.getType().dereference();
+ fdElement = getArrayField( tdElement );
+
+ // before transfer func, possibly inject
+ // stall-site taints
+ if( doEffectsAnalysis && fmContaining != fmAnalysisEntry ) {
+
+ if(rblockStatus.isInCriticalRegion(fmContaining, fn)){
+ // x.y=f , stall x and y if they are not accessible
+ // also contribute write effects on stall site of x
+ if(!rg.isAccessible(lhs)) {
+ rg.taintStallSite(fn, lhs);
+ }
+
+ if(!rg.isAccessible(rhs)) {
+ rg.taintStallSite(fn, rhs);
+ }
+
+ // accessible status update
+ rg.makeAccessible(lhs);
+ rg.makeAccessible(rhs);
+ }
+ }
- rg.assignTempXFieldFEqualToTempY( lhs, fdElement, rhs );
+ if( shouldAnalysisTrack( rhs.getType() ) ) {
+ // transfer func, BUT
+ // skip this node if it cannot create new reachability paths
+ if( !arrayReferencees.doesNotCreateNewReaching( fsen ) ) {
+ rg.assignTempXFieldFEqualToTempY( lhs, fdElement, rhs );
+ }
+ }
+
+ // use transformed graph to do effects analysis
+ if( doEffectsAnalysis && fmContaining != fmAnalysisEntry ) {
+ effectsAnalysis.analyzeFlatSetFieldNode( rg, lhs, fdElement,
+ false );
}
break;
lhs = fnn.getDst();
if( shouldAnalysisTrack( lhs.getType() ) ) {
AllocSite as = getAllocSiteFromFlatNewPRIVATE( fnn );
- rg.assignTempEqualToNewAlloc( lhs, as );
+
+ // before transform, support effects analysis
+ if (doEffectsAnalysis && fmContaining != fmAnalysisEntry) {
+ if (rblockStatus.isInCriticalRegion(fmContaining, fn)) {
+ // after creating new object, lhs is accessible
+ rg.makeAccessible(lhs);
+ }
+ }
+
+ // transfer func
+ rg.assignTempEqualToNewAlloc( lhs, as );
+ }
+ break;
+
+ case FKind.FlatSESEEnterNode:
+ sese = (FlatSESEEnterNode) fn;
+
+ if( sese.getIsCallerSESEplaceholder() ) {
+ // ignore these dummy rblocks!
+ break;
+ }
+
+ if( doEffectsAnalysis && fmContaining != fmAnalysisEntry ) {
+
+ // always remove ALL stall site taints at enter
+ rg.removeAllStallSiteTaints();
+
+ // inject taints for in-set vars
+ rg.taintInSetVars( sese );
+
+ }
+ break;
+
+ case FKind.FlatSESEExitNode:
+ fsexn = (FlatSESEExitNode) fn;
+ sese = fsexn.getFlatEnter();
+
+ if( doEffectsAnalysis && fmContaining != fmAnalysisEntry ) {
+
+ // @ sese exit make all live variables
+ // inaccessible to later parent statements
+ rg.makeInaccessible( liveness.getLiveInTemps( fmContaining, fn ) );
+
+ // always remove ALL stall site taints at exit
+ rg.removeAllStallSiteTaints();
+
+ // remove in-set var taints for the exiting rblock
+ rg.removeInContextTaints( sese );
}
break;
+
case FKind.FlatCall: {
Descriptor mdCaller;
if( fmContaining.getMethod() != null ){
FlatCall fc = (FlatCall) fn;
MethodDescriptor mdCallee = fc.getMethod();
FlatMethod fmCallee = state.getMethodFlat( mdCallee );
-
-
+
boolean debugCallSite =
mdCaller.getSymbol().equals( state.DISJOINTDEBUGCALLER ) &&
mdCallee.getSymbol().equals( state.DISJOINTDEBUGCALLEE );
// and reschedule the callee for analysis
addIHMcontribution( mdCallee, fc, heapForThisCall_cur );
+ // map a FlatCall to its enclosing method/task descriptor
+ // so we can write that info out later
+ fc2enclosing.put( fc, mdCaller );
+
+ if( state.DISJOINTDEBUGSCHEDULING ) {
+ System.out.println( " context changed, scheduling callee: "+mdCallee );
+ }
+
if( state.DISJOINTDVISITSTACKEESONTOP ) {
calleesToEnqueue.add( mdCallee );
} else {
enqueue( mdCallee );
-
- if( state.DISJOINTDEBUGSCHEDULING ) {
- System.out.println( " context changed, scheduling callee: "+mdCallee );
- }
-
}
}
-
// the transformation for a call site should update the
// current heap abstraction with any effects from the callee,
// or if the method is virtual, the effects from any possible
// callees, so find the set of callees...
- Set<MethodDescriptor> setPossibleCallees =
- new HashSet<MethodDescriptor>();
+ Set<MethodDescriptor> setPossibleCallees;
+ if( determinismDesired ) {
+ // use an ordered set
+ setPossibleCallees = new TreeSet<MethodDescriptor>( dComp );
+ } else {
+ // otherwise use a speedy hashset
+ setPossibleCallees = new HashSet<MethodDescriptor>();
+ }
if( mdCallee.isStatic() ) {
setPossibleCallees.add( mdCallee );
);
}
- ReachGraph rgMergeOfEffects = new ReachGraph();
+ ReachGraph rgMergeOfPossibleCallers = new ReachGraph();
Iterator<MethodDescriptor> mdItr = setPossibleCallees.iterator();
while( mdItr.hasNext() ) {
// don't alter the working graph (rg) until we compute a
// result for every possible callee, merge them all together,
// then set rg to that
- ReachGraph rgCopy = new ReachGraph();
- rgCopy.merge( rg );
+ ReachGraph rgPossibleCaller = new ReachGraph();
+ rgPossibleCaller.merge( rg );
- ReachGraph rgEffect = getPartial( mdPossible );
+ ReachGraph rgPossibleCallee = getPartial( mdPossible );
- if( rgEffect == null ) {
+ if( rgPossibleCallee == null ) {
// if this method has never been analyzed just schedule it
// for analysis and skip over this call site for now
if( state.DISJOINTDVISITSTACKEESONTOP ) {
calleesToEnqueue.add( mdPossible );
} else {
enqueue( mdPossible );
+ }
+
+ if( state.DISJOINTDEBUGSCHEDULING ) {
+ System.out.println( " callee hasn't been analyzed, scheduling: "+mdPossible );
+ }
- if( state.DISJOINTDEBUGSCHEDULING ) {
- System.out.println( " callee hasn't been analyzed, scheduling: "+mdPossible );
+
+ } else {
+ // calculate the method call transform
+ rgPossibleCaller.resolveMethodCall( fc,
+ fmPossible,
+ rgPossibleCallee,
+ callerNodeIDsCopiedToCallee,
+ writeDebugDOTs
+ );
+
+ if( doEffectsAnalysis && fmContaining != fmAnalysisEntry ) {
+ if( !rgPossibleCallee.isAccessible( ReachGraph.tdReturn ) ) {
+ rgPossibleCaller.makeInaccessible( fc.getReturnTemp() );
}
}
- } else {
- rgCopy.resolveMethodCall( fc,
- fmPossible,
- rgEffect,
- callerNodeIDsCopiedToCallee,
- writeDebugDOTs
- );
}
- rgMergeOfEffects.merge( rgCopy );
+ rgMergeOfPossibleCallers.merge( rgPossibleCaller );
}
// now that we've taken care of building heap models for
// callee analysis, finish this transformation
- rg = rgMergeOfEffects;
+ rg = rgMergeOfPossibleCallers;
} break;
case FKind.FlatReturnNode:
FlatReturnNode frn = (FlatReturnNode) fn;
rhs = frn.getReturnTemp();
+
+ // before transfer, do effects analysis support
+ if( doEffectsAnalysis && fmContaining != fmAnalysisEntry ) {
+ if(!rg.isAccessible(rhs)){
+ rg.makeInaccessible(ReachGraph.tdReturn);
+ }
+ }
+
if( rhs != null && shouldAnalysisTrack( rhs.getType() ) ) {
rg.assignReturnEqualToTemp( rhs );
}
+
setRetNodes.add( frn );
break;
ReachGraph rg = (ReachGraph) me.getValue();
rg.writeGraph( "COMPLETE"+d,
- true, // write labels (variables)
- true, // selectively hide intermediate temp vars
- true, // prune unreachable heap regions
- false, // hide subset reachability states
- true ); // hide edge taints
+ true, // write labels (variables)
+ true, // selectively hide intermediate temp vars
+ true, // prune unreachable heap regions
+ false, // hide reachability altogether
+ true, // hide subset reachability states
+ true, // hide predicates
+ false ); // hide edge taints
}
}
FlatCall fc = (FlatCall) me2.getKey();
ReachGraph rg = (ReachGraph) me2.getValue();
- rg.writeGraph( "IHMPARTFOR"+d+"FROM"+fc,
+ rg.writeGraph( "IHMPARTFOR"+d+"FROM"+fc2enclosing.get( fc )+fc,
true, // write labels (variables)
true, // selectively hide intermediate temp vars
+ true, // hide reachability altogether
true, // prune unreachable heap regions
- false, // hide subset reachability states
+ true, // hide subset reachability states
+ false, // hide predicates
true ); // hide edge taints
}
}
}
+
+ private void writeInitialContexts() {
+ Set entrySet = mapDescriptorToInitialContext.entrySet();
+ Iterator itr = entrySet.iterator();
+ while( itr.hasNext() ) {
+ Map.Entry me = (Map.Entry) itr.next();
+ Descriptor d = (Descriptor) me.getKey();
+ ReachGraph rg = (ReachGraph) me.getValue();
+
+ rg.writeGraph( "INITIAL"+d,
+ true, // write labels (variables)
+ true, // selectively hide intermediate temp vars
+ true, // prune unreachable heap regions
+ false, // hide all reachability
+ true, // hide subset reachability states
+ true, // hide predicates
+ false );// hide edge taints
+ }
+ }
protected ReachGraph getPartial( Descriptor d ) {
true, // write labels (variables)
true, // selectively hide intermediate temp vars
true, // prune unreachable heap regions
- false, // hide subset reachability states
- true ); // hide edge taints
+ false, // hide all reachability
+ true, // hide subset reachability states
+ false, // hide predicates
+ false); // hide edge taints
mapDescriptorToNumUpdates.put( d, n + 1 );
}
// return just the allocation site associated with one FlatNew node
protected AllocSite getAllocSiteFromFlatNewPRIVATE( FlatNew fnew ) {
+ boolean flagProgrammatically = false;
+ if( sitesToFlag != null && sitesToFlag.contains( fnew ) ) {
+ flagProgrammatically = true;
+ }
+
if( !mapFlatNewToAllocSite.containsKey( fnew ) ) {
AllocSite as = AllocSite.factory( allocationDepth,
fnew,
- fnew.getDisjointId()
+ fnew.getDisjointId(),
+ flagProgrammatically
);
// the newest nodes are single objects
if( determinismDesired ) {
// use an ordered set
- discovered
- = new TreeSet<Descriptor>( new DescriptorComparator() );
-
+ discovered = new TreeSet<Descriptor>( dComp );
} else {
// otherwise use a speedy hashset
discovered = new HashSet<Descriptor>();
getIHMcontributions( d );
if( !heapsFromCallers.containsKey( fc ) ) {
- heapsFromCallers.put( fc, new ReachGraph() );
+ return null;
}
return heapsFromCallers.get( fc );
}
+
public void addIHMcontribution( Descriptor d,
FlatCall fc,
ReachGraph rg
heapsFromCallers.put( fc, rg );
}
+
private AllocSite createParameterAllocSite( ReachGraph rg,
TempDescriptor tempDesc,
boolean flagRegions
// create allocation site
AllocSite as = AllocSite.factory( allocationDepth,
flatNew,
- flatNew.getDisjointId()
+ flatNew.getDisjointId(),
+ false
);
for (int i = 0; i < allocationDepth; ++i) {
Integer id = generateUniqueHeapRegionNodeID();
if(prevNode==null){
// make a new reference between new summary node and source
- RefEdge edgeToSummary = new RefEdge(srcHRN, // source
+ RefEdge edgeToSummary = new RefEdge(srcHRN, // source
hrnSummary, // dest
typeDesc, // type
fd.getSymbol(), // field name
alpha, // beta
- ExistPredSet.factory(rg.predTrue) // predicates
+ ExistPredSet.factory(rg.predTrue), // predicates
+ null
);
rg.addRefEdge(srcHRN, hrnSummary, edgeToSummary);
typeDesc, // type
arrayElementFieldName, // field name
alpha, // beta
- ExistPredSet.factory(rg.predTrue) // predicates
+ ExistPredSet.factory(rg.predTrue), // predicates
+ null
);
rg.addRefEdge(prevNode, hrnSummary, edgeToSummary);
typeDesc, // type
arrayElementFieldName, // field name
alpha, // beta
- ExistPredSet.factory(rg.predTrue) // predicates
+ ExistPredSet.factory(rg.predTrue), // predicates
+ null
);
rg.addRefEdge(prevNode, hrnSummary, edgeToSummary);
prevNode=hrnSummary;
}else{
- HeapRegionNode hrnSummary=mapToExistingNode.get(typeDesc);
+ HeapRegionNode hrnSummary=mapToExistingNode.get(typeDesc);
if(prevNode.getReferenceTo(hrnSummary, typeDesc, arrayElementFieldName)==null){
RefEdge edgeToSummary = new RefEdge(prevNode, // source
hrnSummary, // dest
typeDesc, // type
arrayElementFieldName, // field name
alpha, // beta
- ExistPredSet.factory(rg.predTrue) // predicates
+ ExistPredSet.factory(rg.predTrue), // predicates
+ null
);
rg.addRefEdge(prevNode, hrnSummary, edgeToSummary);
}
taskDesc.getParamType(idx), // type
null, // field name
hrnNewest.getAlpha(), // beta
- ExistPredSet.factory(rg.predTrue) // predicates
+ ExistPredSet.factory(rg.predTrue), // predicates
+ null
);
rg.addRefEdge(lnX, hrnNewest, edgeNew);
type, // type
fd.getSymbol(), // field name
hrnNewest.getAlpha(), // beta
- ExistPredSet.factory(rg.predTrue) // predicates
+ ExistPredSet.factory(rg.predTrue), // predicates
+ null
);
rg.addRefEdge(srcHRN, hrnSummary, edgeToSummary);
fd.getType(), // type
fd.getSymbol(), // field name
srcHRN.getAlpha(), // beta
- ExistPredSet.factory(rg.predTrue) // predicates
+ ExistPredSet.factory(rg.predTrue), // predicates
+ null
);
rg.addRefEdge(srcHRN, hrnDst, edgeToSummary);
return asSetTotal;
}
+ public Set<Descriptor> getDescriptorsToAnalyze() {
+ return descriptorsToAnalyze;
+ }
+ public EffectsAnalysis getEffectsAnalysis(){
+ return effectsAnalysis;
+ }
+
+ public ReachGraph getReachGraph(Descriptor d){
+ return mapDescriptorToCompleteReachGraph.get(d);
+ }
// get successive captures of the analysis state, use compiler
" @@@" );
String graphName;
if( in ) {
- graphName = String.format( "snap%02d_%04din",
+ graphName = String.format( "snap%03d_%04din",
snapVisitCounter,
snapNodeCounter );
} else {
- graphName = String.format( "snap%02d_%04dout",
+ graphName = String.format( "snap%03d_%04dout",
snapVisitCounter,
snapNodeCounter );
}
graphName = graphName + fn;
}
rg.writeGraph( graphName,
- true, // write labels (variables)
- true, // selectively hide intermediate temp vars
- true, // prune unreachable heap regions
- false, // hide subset reachability states
- true );// hide edge taints
+ true, // write labels (variables)
+ true, // selectively hide intermediate temp vars
+ true, // prune unreachable heap regions
+ false, // hide reachability
+ true, // hide subset reachability states
+ true, // hide predicates
+ false );// hide edge taints
}
}
projects / IRC.git / blobdiff