private CallGraph callGraph;
private OwnershipAnalysis ownAnalysis;
- private FlatSESEEnterNode rootSESE;
+
+ // an implicit SESE is automatically spliced into
+ // the IR graph around the C main before this analysis--it
+ // is nothing special except that we can make assumptions
+ // about it, such as the whole program ends when it ends
+ private FlatSESEEnterNode mainSESE;
+
+ // SESEs that are the root of an SESE tree belong to this
+ // set--the main SESE is always a root, statically SESEs
+ // inside methods are a root because we don't know how they
+ // will fit into the runtime tree of SESEs
+ private Set<FlatSESEEnterNode> rootSESEs;
+
+ // simply a set of every reachable SESE in the program, not
+ // including caller placeholder SESEs
private Set<FlatSESEEnterNode> allSESEs;
+
+ // A mapping of flat nodes to the stack of SESEs for that node, where
+ // an SESE is the child of the SESE directly below it on the stack.
+ // These stacks do not reflect the heirarchy over methods calls--whenever
+ // there is an empty stack it means all variables are available.
private Hashtable< FlatNode, Stack<FlatSESEEnterNode> > seseStacks;
+
private Hashtable< FlatNode, Set<TempDescriptor> > livenessRootView;
private Hashtable< FlatNode, Set<TempDescriptor> > livenessVirtualReads;
private Hashtable< FlatNode, VarSrcTokTable > variableResults;
private Hashtable< FlatNode, Set<TempDescriptor> > notAvailableResults;
private Hashtable< FlatNode, CodePlan > codePlans;
- private Hashtable<FlatEdge, FlatWriteDynamicVarNode> wdvNodesToSpliceIn;
+ private Hashtable< FlatEdge, FlatWriteDynamicVarNode > wdvNodesToSpliceIn;
+
+ private Hashtable< MethodContext, HashSet<AllocationSite>> mapMethodContextToLiveInAllocationSiteSet;
public static int maxSESEage = -1;
// use these methods in BuildCode to have access to analysis results
- public FlatSESEEnterNode getRootSESE() {
- return rootSESE;
+ public FlatSESEEnterNode getMainSESE() {
+ return mainSESE;
+ }
+
+ public Set<FlatSESEEnterNode> getRootSESEs() {
+ return rootSESEs;
}
public Set<FlatSESEEnterNode> getAllSESEs() {
this.ownAnalysis = ownAnalysis;
this.maxSESEage = state.MLP_MAXSESEAGE;
- // initialize analysis data structures
- allSESEs = new HashSet<FlatSESEEnterNode>();
+ rootSESEs = new HashSet<FlatSESEEnterNode>();
+ allSESEs = new HashSet<FlatSESEEnterNode>();
- seseStacks = new Hashtable< FlatNode, Stack<FlatSESEEnterNode> >();
+ seseStacks = new Hashtable< FlatNode, Stack<FlatSESEEnterNode> >();
+ livenessRootView = new Hashtable< FlatNode, Set<TempDescriptor> >();
livenessVirtualReads = new Hashtable< FlatNode, Set<TempDescriptor> >();
variableResults = new Hashtable< FlatNode, VarSrcTokTable >();
notAvailableResults = new Hashtable< FlatNode, Set<TempDescriptor> >();
codePlans = new Hashtable< FlatNode, CodePlan >();
+ wdvNodesToSpliceIn = new Hashtable< FlatEdge, FlatWriteDynamicVarNode >();
+
+ mapMethodContextToLiveInAllocationSiteSet = new Hashtable< MethodContext, HashSet<AllocationSite>>();
+
- wdvNodesToSpliceIn = new Hashtable<FlatEdge, FlatWriteDynamicVarNode>();
-
-
- FlatMethod fmMain = state.getMethodFlat( tu.getMain() );
+ FlatMethod fmMain = state.getMethodFlat( typeUtil.getMain() );
- rootSESE = (FlatSESEEnterNode) fmMain.getNext(0);
- rootSESE.setfmEnclosing( fmMain );
- rootSESE.setmdEnclosing( fmMain.getMethod() );
- rootSESE.setcdEnclosing( fmMain.getMethod().getClassDesc() );
+ mainSESE = (FlatSESEEnterNode) fmMain.getNext(0);
+ mainSESE.setfmEnclosing( fmMain );
+ mainSESE.setmdEnclosing( fmMain.getMethod() );
+ mainSESE.setcdEnclosing( fmMain.getMethod().getClassDesc() );
- if( state.MLPDEBUG ) {
- System.out.println( "" );
- }
// 1st pass
// run analysis on each method that is actually called
// and organize them into roots and children
buildForestForward( fm );
}
- if( state.MLPDEBUG ) {
- //System.out.println( "\nSESE Hierarchy\n--------------\n" ); printSESEHierarchy();
- }
// 2nd pass, results are saved in FlatSESEEnterNode, so
// intermediate results, for safety, are discarded
- livenessAnalysisBackward( rootSESE, true, null, fmMain.getFlatExit() );
+ Iterator<FlatSESEEnterNode> rootItr = rootSESEs.iterator();
+ while( rootItr.hasNext() ) {
+ FlatSESEEnterNode root = rootItr.next();
+ livenessAnalysisBackward( root,
+ true,
+ null );
+ }
// 3rd pass
variableAnalysisForward( fm );
}
-
// 4th pass, compute liveness contribution from
// virtual reads discovered in variable pass
- livenessAnalysisBackward( rootSESE, true, null, fmMain.getFlatExit() );
- if( state.MLPDEBUG ) {
- //System.out.println( "\nLive-In, SESE View\n-------------\n" ); printSESELiveness();
- //System.out.println( "\nLive-In, Root View\n------------------\n"+fmMain.printMethod( livenessRootView ) );
+ rootItr = rootSESEs.iterator();
+ while( rootItr.hasNext() ) {
+ FlatSESEEnterNode root = rootItr.next();
+ livenessAnalysisBackward( root,
+ true,
+ null );
}
+ /*
+ SOMETHING IS WRONG WITH THIS, DON'T USE IT UNTIL IT CAN BE FIXED
+
// 5th pass
methItr = ownAnalysis.descriptorsToAnalyze.iterator();
while( methItr.hasNext() ) {
// by removing reference variables that are not live
pruneVariableResultsWithLiveness( fm );
}
- if( state.MLPDEBUG ) {
- //System.out.println( "\nVariable Results-Out\n----------------\n"+fmMain.printMethod( variableResults ) );
- }
-
+ */
+
// 6th pass
methItr = ownAnalysis.descriptorsToAnalyze.iterator();
// point, in a forward fixed-point pass
notAvailableForward( fm );
}
- if( state.MLPDEBUG ) {
- //System.out.println( "\nNot Available Results-Out\n---------------------\n"+fmMain.printMethod( notAvailableResults ) );
+
+ // new pass
+ methItr = ownAnalysis.descriptorsToAnalyze.iterator();
+ JavaCallGraph javaCallGraph = new JavaCallGraph(state,tu);
+ while( methItr.hasNext() ) {
+ Descriptor d = methItr.next();
+ FlatMethod fm = state.getMethodFlat( d );
+ methodEffects(fm,javaCallGraph);
}
+
+ // disjoint analysis with a set of flagged allocation sites of live-in variable
+ try {
+ OwnershipAnalysis oa2 = new OwnershipAnalysis(state, tu, callGraph,
+ state.OWNERSHIPALLOCDEPTH, false,
+ false, state.OWNERSHIPALIASFILE,
+ state.METHODEFFECTS,
+ mapMethodContextToLiveInAllocationSiteSet);
+ // debug
+ methItr = oa2.descriptorsToAnalyze.iterator();
+ while (methItr.hasNext()) {
+ Descriptor d = methItr.next();
+ FlatMethod fm = state.getMethodFlat(d);
+ debugFunction(oa2, fm);
+ }
+ //
+ } catch (IOException e) {
+ System.err.println(e);
+ }
+
// 7th pass
FlatMethod fm = state.getMethodFlat( d );
// compute a plan for code injections
- computeStallsForward( fm );
- }
- if( state.MLPDEBUG ) {
- //System.out.println( "\nCode Plans\n----------\n"+fmMain.printMethod( codePlans ) );
+ codePlansForward( fm );
}
double dt = (timeEndAnalysis - timeStartAnalysis)/(Math.pow( 10.0, 9.0 ) );
String treport = String.format( "The mlp analysis took %.3f sec.", dt );
System.out.println( treport );
+
+ if( state.MLPDEBUG ) {
+ try {
+ writeReports( treport );
+ } catch( IOException e ) {}
+ }
}
case FKind.FlatSESEEnterNode: {
FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
- allSESEs.add( fsen );
+ if( !fsen.getIsCallerSESEplaceholder() ) {
+ allSESEs.add( fsen );
+ }
+
fsen.setfmEnclosing( fm );
fsen.setmdEnclosing( fm.getMethod() );
fsen.setcdEnclosing( fm.getMethod().getClassDesc() );
- if( !seseStack.empty() ) {
+ if( seseStack.empty() ) {
+ rootSESEs.add( fsen );
+ fsen.setParent( null );
+ } else {
seseStack.peek().addChild( fsen );
fsen.setParent( seseStack.peek() );
}
case FKind.FlatReturnNode: {
FlatReturnNode frn = (FlatReturnNode) fn;
- if( !seseStack.empty() ) {
+ if( !seseStack.empty() &&
+ !seseStack.peek().getIsCallerSESEplaceholder()
+ ) {
throw new Error( "Error: return statement enclosed within SESE "+
seseStack.peek().getPrettyIdentifier() );
}
}
}
- private void printSESEHierarchy() {
- // our forest is actually a tree now that
- // there is an implicit root SESE
- printSESEHierarchyTree( rootSESE, 0 );
- System.out.println( "" );
- }
-
- private void printSESEHierarchyTree( FlatSESEEnterNode fsen, int depth ) {
- for( int i = 0; i < depth; ++i ) {
- System.out.print( " " );
- }
- System.out.println( "- "+fsen.getPrettyIdentifier() );
-
- Iterator<FlatSESEEnterNode> childItr = fsen.getChildren().iterator();
- while( childItr.hasNext() ) {
- FlatSESEEnterNode fsenChild = childItr.next();
- printSESEHierarchyTree( fsenChild, depth + 1 );
- }
- }
-
private void livenessAnalysisBackward( FlatSESEEnterNode fsen,
boolean toplevel,
- Hashtable< FlatSESEExitNode, Set<TempDescriptor> > liveout,
- FlatExit fexit ) {
+ Hashtable< FlatSESEExitNode, Set<TempDescriptor> > liveout ) {
// start from an SESE exit, visit nodes in reverse up to
// SESE enter in a fixed-point scheme, where children SESEs
// because child SESE enter node has all necessary info
Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
- FlatSESEExitNode fsexn = fsen.getFlatExit();
- if (toplevel) {
- //handle root SESE
- flatNodesToVisit.add( fexit );
- } else
- flatNodesToVisit.add( fsexn );
- Hashtable<FlatNode, Set<TempDescriptor>> livenessResults=new Hashtable<FlatNode, Set<TempDescriptor>>();
+ if( toplevel ) {
+ flatNodesToVisit.add( fsen.getfmEnclosing().getFlatExit() );
+ } else {
+ flatNodesToVisit.add( fsen.getFlatExit() );
+ }
+
+ Hashtable<FlatNode, Set<TempDescriptor>> livenessResults =
+ new Hashtable< FlatNode, Set<TempDescriptor> >();
+
+ if( toplevel ) {
+ liveout = new Hashtable< FlatSESEExitNode, Set<TempDescriptor> >();
+ }
- if (toplevel==true)
- liveout=new Hashtable<FlatSESEExitNode, Set<TempDescriptor>>();
-
while( !flatNodesToVisit.isEmpty() ) {
FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
flatNodesToVisit.remove( fn );
// remember liveness per node from the root view as the
// global liveness of variables for later passes to use
- if( toplevel == true ) {
- livenessRootView = livenessResults;
+ if( toplevel ) {
+ livenessRootView.putAll( livenessResults );
}
// post-order traversal, so do children first
Iterator<FlatSESEEnterNode> childItr = fsen.getChildren().iterator();
while( childItr.hasNext() ) {
FlatSESEEnterNode fsenChild = childItr.next();
- livenessAnalysisBackward( fsenChild, false, liveout, null );
+ livenessAnalysisBackward( fsenChild, false, liveout );
}
}
Set<TempDescriptor> liveIn,
FlatSESEEnterNode currentSESE,
boolean toplevel,
- Hashtable< FlatSESEExitNode, Set<TempDescriptor> > liveout ) {
-
+ Hashtable< FlatSESEExitNode, Set<TempDescriptor> > liveout
+ ) {
switch( fn.kind() ) {
-
+
case FKind.FlatSESEExitNode:
- if (toplevel==true) {
- FlatSESEExitNode exitn=(FlatSESEExitNode) fn;
- //update liveout set for FlatSESEExitNode
- if (!liveout.containsKey(exitn))
- liveout.put(exitn, new HashSet<TempDescriptor>());
- liveout.get(exitn).addAll(liveIn);
+ if( toplevel ) {
+ FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
+ if( !liveout.containsKey( fsexn ) ) {
+ liveout.put( fsexn, new HashSet<TempDescriptor>() );
+ }
+ liveout.get( fsexn ).addAll( liveIn );
}
// no break, sese exits should also execute default actions
TempDescriptor [] writeTemps = fn.writesTemps();
for( int i = 0; i < writeTemps.length; ++i ) {
liveIn.remove( writeTemps[i] );
-
- if (!toplevel) {
- FlatSESEExitNode exitnode=currentSESE.getFlatExit();
- Set<TempDescriptor> livetemps=liveout.get(exitnode);
- if (livetemps.contains(writeTemps[i])) {
- //write to a live out temp...
- //need to put in SESE liveout set
- currentSESE.addOutVar(writeTemps[i]);
- }
+
+ if( !toplevel ) {
+ FlatSESEExitNode fsexn = currentSESE.getFlatExit();
+ Set<TempDescriptor> livetemps = liveout.get( fsexn );
+ if( livetemps != null &&
+ livetemps.contains( writeTemps[i] ) ) {
+ // write to a live out temp...
+ // need to put in SESE liveout set
+ currentSESE.addOutVar( writeTemps[i] );
+ }
}
}
for( int i = 0; i < readTemps.length; ++i ) {
liveIn.add( readTemps[i] );
}
-
+
Set<TempDescriptor> virtualReadTemps = livenessVirtualReads.get( fn );
if( virtualReadTemps != null ) {
- Iterator<TempDescriptor> vrItr = virtualReadTemps.iterator();
- while( vrItr.hasNext() ) {
- TempDescriptor vrt = vrItr.next();
- liveIn.add( vrt );
- }
- }
+ liveIn.addAll( virtualReadTemps );
+ }
+
} break;
} // end switch
return liveIn;
}
- private void printSESELiveness() {
- // our forest is actually a tree now that
- // there is an implicit root SESE
- printSESELivenessTree( rootSESE );
- System.out.println( "" );
- }
-
- private void printSESELivenessTree( FlatSESEEnterNode fsen ) {
-
- System.out.println( "SESE "+fsen.getPrettyIdentifier()+" has in-set:" );
- Iterator<TempDescriptor> tItr = fsen.getInVarSet().iterator();
- while( tItr.hasNext() ) {
- System.out.println( " "+tItr.next() );
- }
- System.out.println( "and out-set:" );
- tItr = fsen.getOutVarSet().iterator();
- while( tItr.hasNext() ) {
- System.out.println( " "+tItr.next() );
- }
- System.out.println( "" );
-
-
- Iterator<FlatSESEEnterNode> childItr = fsen.getChildren().iterator();
- while( childItr.hasNext() ) {
- FlatSESEEnterNode fsenChild = childItr.next();
- printSESELivenessTree( fsenChild );
- }
- }
-
private void variableAnalysisForward( FlatMethod fm ) {
-
+
Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
flatNodesToVisit.add( fm );
vstTable.age( currentSESE );
vstTable.assertConsistency();
-
- vstTable.ownInSet( currentSESE );
- vstTable.assertConsistency();
} break;
case FKind.FlatSESEExitNode: {
FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
FlatSESEEnterNode fsen = fsexn.getFlatEnter();
assert currentSESE.getChildren().contains( fsen );
- vstTable.remapChildTokens( fsen );
- Set<TempDescriptor> liveIn = currentSESE.getInVarSet();
- Set<TempDescriptor> virLiveIn = vstTable.removeParentAndSiblingTokens( fsen, liveIn );
- Set<TempDescriptor> virLiveInOld = livenessVirtualReads.get( fn );
- if( virLiveInOld != null ) {
- virLiveIn.addAll( virLiveInOld );
+ vstTable.remapChildTokens( fsen );
+
+ // liveness virtual reads are things that might be
+ // written by an SESE and should be added to the in-set
+ // anything virtually read by this SESE should be pruned
+ // of parent or sibling sources
+ Set<TempDescriptor> liveVars = livenessRootView.get( fn );
+ Set<TempDescriptor> fsenVirtReads = vstTable.calcVirtReadsAndPruneParentAndSiblingTokens( fsen, liveVars );
+ Set<TempDescriptor> fsenVirtReadsOld = livenessVirtualReads.get( fn );
+ if( fsenVirtReadsOld != null ) {
+ fsenVirtReads.addAll( fsenVirtReadsOld );
}
- livenessVirtualReads.put( fn, virLiveIn );
- vstTable.assertConsistency();
+ livenessVirtualReads.put( fn, fsenVirtReads );
+
// then all child out-set tokens are guaranteed
// to be filled in, so clobber those entries with
TempDescriptor outVar = outVarItr.next();
HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
ts.add( outVar );
- VariableSourceToken vst = new VariableSourceToken( ts,
- fsen,
- new Integer( 0 ),
- outVar
- );
+ VariableSourceToken vst =
+ new VariableSourceToken( ts,
+ fsen,
+ new Integer( 0 ),
+ outVar
+ );
vstTable.remove( outVar );
vstTable.add( vst );
}
HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
ts.add( lhs );
- forAddition.add( new VariableSourceToken( ts,
- vst.getSESE(),
- vst.getAge(),
- vst.getAddrVar()
- )
- );
+ if( currentSESE.getChildren().contains( vst.getSESE() ) ) {
+ // if the source comes from a child, copy it over
+ forAddition.add( new VariableSourceToken( ts,
+ vst.getSESE(),
+ vst.getAge(),
+ vst.getAddrVar()
+ )
+ );
+ } else {
+ // otherwise, stamp it as us as the source
+ forAddition.add( new VariableSourceToken( ts,
+ currentSESE,
+ new Integer( 0 ),
+ lhs
+ )
+ );
+ }
}
vstTable.addAll( forAddition );
break;
}
-
vstTable.remove( writeTemps[0] );
HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
Set<TempDescriptor> rootLiveSet = livenessRootView.get( fn );
VarSrcTokTable vstTable = variableResults.get( fn );
- // fix later, not working, only wanted it to make tables easier to read
- //vstTable.pruneByLiveness( rootLiveSet );
+ vstTable.pruneByLiveness( rootLiveSet );
for( int i = 0; i < fn.numNext(); i++ ) {
FlatNode nn = fn.getNext( i );
FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
FlatSESEEnterNode fsen = fsexn.getFlatEnter();
assert currentSESE.getChildren().contains( fsen );
-
- Set<TempDescriptor> liveTemps = livenessRootView.get( fn );
- assert liveTemps != null;
-
- notAvailSet.addAll( liveTemps );
+ notAvailSet.addAll( fsen.getOutVarSet() );
} break;
+ case FKind.FlatMethod: {
+ notAvailSet.clear();
+ }
+
case FKind.FlatOpNode: {
FlatOpNode fon = (FlatOpNode) fn;
} // end switch
}
+
+ private void debugFunction(OwnershipAnalysis oa2, FlatMethod fm) {
+
+ String methodName="doSomeWork";
+
+ MethodDescriptor md=fm.getMethod();
+ HashSet<MethodContext> mcSet=oa2.getAllMethodContextSetByDescriptor(md);
+ Iterator<MethodContext> mcIter=mcSet.iterator();
+
+ while(mcIter.hasNext()){
+ MethodContext mc=mcIter.next();
+
+ OwnershipGraph og=oa2.getOwnvershipGraphByMethodContext(mc);
+
+ if(fm.toString().indexOf(methodName)>0){
+ try {
+ og.writeGraph(methodName + "SECONDGRAPH", true, true, true, true, false);
+ } catch (IOException e) {
+ System.out.println("Error writing debug capture.");
+ System.exit(0);
+ }
+ }
+
+
+
+ }
+
+ }
+
+ private void methodEffects(FlatMethod fm, CallGraph callGraph) {
+
+ MethodDescriptor md=fm.getMethod();
+ HashSet<MethodContext> mcSet=ownAnalysis.getAllMethodContextSetByDescriptor(md);
+ Iterator<MethodContext> mcIter=mcSet.iterator();
+
+ while(mcIter.hasNext()){
+ MethodContext mc=mcIter.next();
+
+ Set<FlatNode> visited = new HashSet<FlatNode>();
+
+ Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
+ flatNodesToVisit.add(fm);
+
+ while (!flatNodesToVisit.isEmpty()) {
+ FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
+ flatNodesToVisit.remove(fn);
+
+ Stack<FlatSESEEnterNode> seseStack = seseStacks.get(fn);
+ assert seseStack != null;
+
+ if (!seseStack.empty()) {
+ effects_nodeActions(mc, fn, seseStack.peek(), callGraph);
+ }
+
+ flatNodesToVisit.remove(fn);
+ visited.add(fn);
+
+ for (int i = 0; i < fn.numNext(); i++) {
+ FlatNode nn = fn.getNext(i);
+ if (!visited.contains(nn)) {
+ flatNodesToVisit.add(nn);
+ }
+ }
+
+ }
+
+
+ }
+
+ }
+
+ private void analyzeRelatedAllocationSite(MethodDescriptor callerMD,
+ MethodContext calleeMC, HashSet<Integer> paramIndexSet) {
+
+ HashSet<MethodContext> mcSet = ownAnalysis
+ .getAllMethodContextSetByDescriptor(callerMD);
+ Iterator<MethodContext> mcIter = mcSet.iterator();
+
+ FlatMethod callerFM = state.getMethodFlat(callerMD);
+
+ while (mcIter.hasNext()) {
+ MethodContext mc = mcIter.next();
+
+ Set<FlatNode> visited = new HashSet<FlatNode>();
+ Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
+ flatNodesToVisit.add(callerFM);
+
+ while (!flatNodesToVisit.isEmpty()) {
+ FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
+ flatNodesToVisit.remove(fn);
+
+ analyzeRelatedAllocationSite_NodeAction(fn, mc, calleeMC, paramIndexSet);
+
+ flatNodesToVisit.remove(fn);
+ visited.add(fn);
+
+ for (int i = 0; i < fn.numNext(); i++) {
+ FlatNode nn = fn.getNext(i);
+ if (!visited.contains(nn)) {
+ flatNodesToVisit.add(nn);
+ }
+ }
+ }
+
+ }
+
+ }
+
+ private void analyzeRelatedAllocationSite_NodeAction(FlatNode fn, MethodContext callerMC,
+ MethodContext calleeMC, HashSet<Integer> paramIndexSet) {
+
+ OwnershipGraph og = ownAnalysis
+ .getOwnvershipGraphByMethodContext(callerMC);
+
+ switch (fn.kind()) {
+
+ case FKind.FlatCall: {
+
+ FlatCall fc = (FlatCall) fn;
+
+ MethodContext calleeMCfromOG = ownAnalysis.getCalleeMethodContext(
+ callerMC, fc);
+
+ if (calleeMC.equals(calleeMCfromOG)) {
+ // in this case, this method context calls corresponding callee.
+ int base;
+ if (((MethodDescriptor) calleeMC.getDescriptor()).isStatic()) {
+ base = 0;
+ } else {
+ base = 1;
+ }
+
+ for (Iterator iterator = paramIndexSet.iterator(); iterator
+ .hasNext();) {
+ Integer integer = (Integer) iterator.next();
+
+ int paramIdx=integer-base;
+ if(paramIdx>=0){
+ // if paramIdx is less than 0, assumes that it is related with wrong method contexts.
+ TempDescriptor arg = fc.getArg(paramIdx );
+ LabelNode argLN = og.td2ln.get(arg);
+ if (argLN != null) {
+ Iterator<ReferenceEdge> iterEdge = argLN
+ .iteratorToReferencees();
+ while (iterEdge.hasNext()) {
+ ReferenceEdge referenceEdge = (ReferenceEdge) iterEdge
+ .next();
+
+ HeapRegionNode dstHRN=referenceEdge.getDst();
+ if(dstHRN.isParameter()){
+ setupRelatedAllocSiteAnalysis(og,callerMC,dstHRN);
+ }else{
+ addLiveInAllocationSite(callerMC, dstHRN
+ .getAllocationSite());
+ }
+ }
+ }
+ }
+ }
+ }
+
+ }
+ break;
+
+ }
+ }
+
+ private void setupRelatedAllocSiteAnalysis(OwnershipGraph og,
+ MethodContext mc, HeapRegionNode dstHRN) {
+
+ HashSet<Integer> paramIndexSet = new HashSet<Integer>();
+
+ // collect corresponding param index
+ Set<Integer> pIndexSet = og.idPrimary2paramIndexSet.get(dstHRN.getID());
+ if (pIndexSet != null) {
+ for (Iterator iterator = pIndexSet.iterator(); iterator.hasNext();) {
+ Integer integer = (Integer) iterator.next();
+ paramIndexSet.add(integer);
+ }
+ }
+
+ Set<Integer> sIndexSet = og.idSecondary2paramIndexSet.get(dstHRN
+ .getID());
+ if (sIndexSet != null) {
+ for (Iterator iterator = sIndexSet.iterator(); iterator.hasNext();) {
+ Integer integer = (Integer) iterator.next();
+ paramIndexSet.add(integer);
+ }
+ }
+
+ if (mc.getDescriptor() instanceof MethodDescriptor) {
+ Set callerSet = callGraph.getCallerSet((MethodDescriptor) mc
+ .getDescriptor());
+ for (Iterator iterator = callerSet.iterator(); iterator.hasNext();) {
+ Object obj = (Object) iterator.next();
+ if (obj instanceof MethodDescriptor) {
+ MethodDescriptor callerMD = (MethodDescriptor) obj;
+
+ analyzeRelatedAllocationSite(callerMD, mc, paramIndexSet);
+
+ }
+ }
+ }
+ }
+
+ private void effects_nodeActions(MethodContext mc, FlatNode fn,
+ FlatSESEEnterNode currentSESE, CallGraph callGraph) {
+
+ OwnershipGraph og = ownAnalysis.getOwnvershipGraphByMethodContext(mc);
+
+ switch (fn.kind()) {
+
+ case FKind.FlatSESEEnterNode: {
+
+ FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
+ assert fsen.equals(currentSESE);
+
+ // uniquely taint each live-in variable
+ Set<TempDescriptor> set = fsen.getInVarSet();
+ Iterator<TempDescriptor> iter = set.iterator();
+ int idx = 0;
+ while (iter.hasNext()) {
+ TempDescriptor td = iter.next();
+ LabelNode ln = og.td2ln.get(td);
+ if (ln != null) {
+ int taint = (int) Math.pow(2, idx);
+ taintLabelNode(ln, taint);
+
+ // collects related allocation sites
+ Iterator<ReferenceEdge> referenceeIter = ln
+ .iteratorToReferencees();
+ while (referenceeIter.hasNext()) {
+ ReferenceEdge referenceEdge = (ReferenceEdge) referenceeIter
+ .next();
+ HeapRegionNode dstHRN = referenceEdge.getDst();
+ if (dstHRN.isParameter()) {
+
+ setupRelatedAllocSiteAnalysis(og,mc,dstHRN);
+
+ } else {
+ addLiveInAllocationSite(mc, dstHRN
+ .getAllocationSite());
+ }
+ }
+
+ }
+
+ idx++;
+ }
+
+ }
+ break;
+
+ case FKind.FlatSESEExitNode: {
+ FlatSESEExitNode fsexit = (FlatSESEExitNode) fn;
+
+ FlatSESEEnterNode enterNode = fsexit.getFlatEnter();
+ FlatSESEEnterNode parent = enterNode.getParent();
+ if (parent != null) {
+
+ SESEEffectsSet set = enterNode.getSeseEffectsSet();
+ Hashtable<TempDescriptor, HashSet<SESEEffectsKey>> readTable = set
+ .getReadTable();
+ Hashtable<TempDescriptor, HashSet<SESEEffectsKey>> parentReadTable = parent
+ .getSeseEffectsSet().getReadTable();
+ Set<TempDescriptor> keys = readTable.keySet();
+ Iterator<TempDescriptor> keyIter = keys.iterator();
+ while (keyIter.hasNext()) {
+ TempDescriptor td = (TempDescriptor) keyIter.next();
+ HashSet<SESEEffectsKey> effectsSet = readTable.get(td);
+ HashSet<SESEEffectsKey> parentEffectsSet = parentReadTable
+ .get(td);
+ if (parentEffectsSet == null) {
+ parentEffectsSet = new HashSet<SESEEffectsKey>();
+ }
+
+ for (Iterator iterator = effectsSet.iterator(); iterator
+ .hasNext();) {
+ SESEEffectsKey seseKey = (SESEEffectsKey) iterator
+ .next();
+ parentEffectsSet.add(new SESEEffectsKey(seseKey
+ .getFieldDescriptor(), seseKey
+ .getTypeDescriptor(), seseKey.getHRNId()));
+ }
+
+ parentReadTable.put(td, parentEffectsSet);
+ }
+
+ Hashtable<TempDescriptor, HashSet<SESEEffectsKey>> writeTable = set
+ .getWriteTable();
+ Hashtable<TempDescriptor, HashSet<SESEEffectsKey>> parentWriteTable = parent
+ .getSeseEffectsSet().getWriteTable();
+ keys = writeTable.keySet();
+ keyIter = keys.iterator();
+ while (keyIter.hasNext()) {
+ TempDescriptor td = (TempDescriptor) keyIter.next();
+ HashSet<SESEEffectsKey> effectsSet = writeTable.get(td);
+ HashSet<SESEEffectsKey> parentEffectsSet = parentWriteTable
+ .get(td);
+ if (parentEffectsSet == null) {
+ parentEffectsSet = new HashSet<SESEEffectsKey>();
+ }
+
+ for (Iterator iterator = effectsSet.iterator(); iterator
+ .hasNext();) {
+ SESEEffectsKey seseKey = (SESEEffectsKey) iterator
+ .next();
+ parentEffectsSet.add(new SESEEffectsKey(seseKey
+ .getFieldDescriptor(), seseKey
+ .getTypeDescriptor(), seseKey.getHRNId()));
+ }
+
+ parentWriteTable.put(td, parentEffectsSet);
+ }
+
+ Hashtable<TempDescriptor, HashSet<SESEEffectsKey>> strongUpdateTable = set
+ .getStrongUpdateTable();
+ Hashtable<TempDescriptor, HashSet<SESEEffectsKey>> parentstrongUpdateTable = parent
+ .getSeseEffectsSet().getStrongUpdateTable();
+ keys = strongUpdateTable.keySet();
+ keyIter = keys.iterator();
+ while (keyIter.hasNext()) {
+ TempDescriptor td = (TempDescriptor) keyIter.next();
+ HashSet<SESEEffectsKey> effectsSet = strongUpdateTable
+ .get(td);
+ HashSet<SESEEffectsKey> parentEffectsSet = parentstrongUpdateTable
+ .get(td);
+ if (parentEffectsSet == null) {
+ parentEffectsSet = new HashSet<SESEEffectsKey>();
+ }
+
+ for (Iterator iterator = effectsSet.iterator(); iterator
+ .hasNext();) {
+ SESEEffectsKey seseKey = (SESEEffectsKey) iterator
+ .next();
+ parentEffectsSet.add(new SESEEffectsKey(seseKey
+ .getFieldDescriptor(), seseKey
+ .getTypeDescriptor(), seseKey.getHRNId()));
+ }
+
+ parentstrongUpdateTable.put(td, parentEffectsSet);
+ }
+
+ }
+
+ }
+ break;
+
+ case FKind.FlatFieldNode: {
+
+ FlatFieldNode ffn = (FlatFieldNode) fn;
+ TempDescriptor src = ffn.getSrc();
+ FieldDescriptor field = ffn.getField();
+
+ LabelNode srcLN = og.td2ln.get(src);
+ if (srcLN != null) {
+ HashSet<TempDescriptor> affectedTDSet = getAccessedTaintNodeSet(srcLN);
+ Iterator<TempDescriptor> affectedIter = affectedTDSet
+ .iterator();
+ while (affectedIter.hasNext()) {
+ TempDescriptor affectedTD = affectedIter.next();
+
+ if (currentSESE.getInVarSet().contains(affectedTD)) {
+
+ HashSet<HeapRegionNode> hrnSet = getReferenceHeapIDSet(
+ og, affectedTD);
+ Iterator<HeapRegionNode> hrnIter = hrnSet.iterator();
+ while (hrnIter.hasNext()) {
+ HeapRegionNode hrn = hrnIter.next();
+
+ Iterator<ReferenceEdge> referencers = hrn
+ .iteratorToReferencers();
+ while (referencers.hasNext()) {
+ ReferenceEdge referenceEdge = (ReferenceEdge) referencers
+ .next();
+ if (field.getSymbol().equals(
+ referenceEdge.getField())) {
+ currentSESE.readEffects(affectedTD, field
+ .getSymbol(), src.getType(),
+ referenceEdge.getDst().getID());
+ }
+ }
+
+ }
+ }
+ }
+
+ // handle tainted case
+
+ Iterator<ReferenceEdge> edgeIter = srcLN
+ .iteratorToReferencees();
+ while (edgeIter.hasNext()) {
+ ReferenceEdge edge = edgeIter.next();
+ HeapRegionNode accessHRN = edge.getDst();
+ // / follow the chain of reference to identify possible
+ // accesses
+ Iterator<ReferenceEdge> referIter = accessHRN
+ .iteratorToReferencers();
+ while (referIter.hasNext()) {
+ ReferenceEdge referEdge = (ReferenceEdge) referIter
+ .next();
+
+ // if (referEdge.getTaintIdentifier() >0 ||
+ // referEdge.getSESETaintIdentifier()>0 ) {
+ HashSet<TempDescriptor> referSet = new HashSet<TempDescriptor>();
+ followReference(accessHRN, referSet,
+ new HashSet<HeapRegionNode>(), currentSESE);
+
+ Iterator<TempDescriptor> referSetIter = referSet
+ .iterator();
+ while (referSetIter.hasNext()) {
+ TempDescriptor tempDescriptor = (TempDescriptor) referSetIter
+ .next();
+ currentSESE.readEffects(tempDescriptor, field
+ .getSymbol(), src.getType(), accessHRN
+ .getID());
+ }
+ // }
+ }
+ // /
+ if (edge.getTaintIdentifier() > 0
+ || edge.getSESETaintIdentifier() > 0) {
+
+ affectedTDSet = getReferenceNodeSet(accessHRN);
+ affectedIter = affectedTDSet.iterator();
+ while (affectedIter.hasNext()) {
+ TempDescriptor affectedTD = affectedIter.next();
+
+ if (currentSESE.getInVarSet().contains(affectedTD)) {
+
+ HashSet<HeapRegionNode> hrnSet = getReferenceHeapIDSet(
+ og, affectedTD);
+ Iterator<HeapRegionNode> hrnIter = hrnSet
+ .iterator();
+ while (hrnIter.hasNext()) {
+ HeapRegionNode hrn = hrnIter.next();
+ currentSESE.readEffects(affectedTD, field
+ .getSymbol(), src.getType(), hrn
+ .getID());
+ }
+
+ }
+
+ }
+ }
+ }
+ }
+
+ }
+ break;
+
+ case FKind.FlatSetFieldNode: {
+
+ FlatSetFieldNode fsen = (FlatSetFieldNode) fn;
+ TempDescriptor dst = fsen.getDst();
+ FieldDescriptor field = fsen.getField();
+
+ LabelNode dstLN = og.td2ln.get(dst);
+ if (dstLN != null) {
+ // check possible strong updates
+ boolean strongUpdate = false;
+
+ if (!field.getType().isImmutable() || field.getType().isArray()) {
+ Iterator<ReferenceEdge> itrXhrn = dstLN
+ .iteratorToReferencees();
+ while (itrXhrn.hasNext()) {
+ ReferenceEdge edgeX = itrXhrn.next();
+ HeapRegionNode hrnX = edgeX.getDst();
+
+ // we can do a strong update here if one of two cases
+ // holds
+ if (field != null
+ && field != OwnershipAnalysis
+ .getArrayField(field.getType())
+ && ((hrnX.getNumReferencers() == 1) || // case 1
+ (hrnX.isSingleObject() && dstLN
+ .getNumReferencees() == 1) // case 2
+ )) {
+ strongUpdate = true;
+ }
+ }
+ }
+
+ HashSet<TempDescriptor> affectedTDSet = getAccessedTaintNodeSet(dstLN);
+
+ Iterator<TempDescriptor> affectedIter = affectedTDSet
+ .iterator();
+
+ while (affectedIter.hasNext()) {
+ TempDescriptor affectedTD = affectedIter.next();
+ if (currentSESE.getInVarSet().contains(affectedTD)) {
+
+ HashSet<HeapRegionNode> hrnSet = getReferenceHeapIDSet(
+ og, affectedTD);
+ Iterator<HeapRegionNode> hrnIter = hrnSet.iterator();
+ while (hrnIter.hasNext()) {
+ HeapRegionNode hrn = hrnIter.next();
+
+ Iterator<ReferenceEdge> referencers = hrn
+ .iteratorToReferencers();
+ while (referencers.hasNext()) {
+ ReferenceEdge referenceEdge = (ReferenceEdge) referencers
+ .next();
+ if (field.getSymbol().equals(
+ referenceEdge.getField())) {
+ currentSESE.writeEffects(affectedTD, field
+ .getSymbol(), dst.getType(),
+ referenceEdge.getDst().getID(),
+ strongUpdate);
+ }
+ }
+
+ }
+ }
+ }
+
+ // handle tainted case
+ Iterator<ReferenceEdge> edgeIter = dstLN
+ .iteratorToReferencees();
+ while (edgeIter.hasNext()) {
+ ReferenceEdge edge = edgeIter.next();
+
+ HeapRegionNode accessHRN = edge.getDst();
+ // / follow the chain of reference to identify possible
+ // accesses
+ Iterator<ReferenceEdge> referIter = accessHRN
+ .iteratorToReferencers();
+ while (referIter.hasNext()) {
+ ReferenceEdge referEdge = (ReferenceEdge) referIter
+ .next();
+
+ // if (referEdge.getTaintIdentifier() > 0 ||
+ // referEdge.getSESETaintIdentifier() > 0 ) {
+ HashSet<TempDescriptor> referSet = new HashSet<TempDescriptor>();
+ followReference(accessHRN, referSet,
+ new HashSet<HeapRegionNode>(), currentSESE);
+ Iterator<TempDescriptor> referSetIter = referSet
+ .iterator();
+ while (referSetIter.hasNext()) {
+ TempDescriptor tempDescriptor = (TempDescriptor) referSetIter
+ .next();
+ currentSESE.writeEffects(tempDescriptor, field
+ .getSymbol(), dst.getType(), accessHRN
+ .getID(), strongUpdate);
+ }
+ // }
+ }
+ // /
+ if (edge.getTaintIdentifier() > 0
+ || edge.getSESETaintIdentifier() > 0) {
+ affectedTDSet = getReferenceNodeSet(accessHRN);
+ affectedIter = affectedTDSet.iterator();
+ while (affectedIter.hasNext()) {
+ TempDescriptor affectedTD = affectedIter.next();
+ if (currentSESE.getInVarSet().contains(affectedTD)) {
+
+ HashSet<HeapRegionNode> hrnSet = getReferenceHeapIDSet(
+ og, affectedTD);
+ Iterator<HeapRegionNode> hrnIter = hrnSet
+ .iterator();
+ while (hrnIter.hasNext()) {
+ HeapRegionNode hrn = hrnIter.next();
+ currentSESE.writeEffects(affectedTD, field
+ .getSymbol(), dst.getType(), hrn
+ .getID(), strongUpdate);
+
+ }
+
+ }
+
+ }
+ }
+ }
+
+ }
+
+ }
+ break;
+
+ case FKind.FlatCall: {
+ FlatCall fc = (FlatCall) fn;
+
+ MethodContext calleeMC = ownAnalysis.getCalleeMethodContext(mc, fc);
+
+ MethodEffects me = ownAnalysis.getMethodEffectsAnalysis()
+ .getMethodEffectsByMethodContext(calleeMC);
+
+ OwnershipGraph calleeOG = ownAnalysis
+ .getOwnvershipGraphByMethodContext(calleeMC);
+
+ FlatMethod fm = state.getMethodFlat(fc.getMethod());
+ ParameterDecomposition decomp = new ParameterDecomposition(
+ ownAnalysis, fc, fm, calleeMC, calleeOG, og);
+
+ int base;
+ if (((MethodDescriptor) calleeMC.getDescriptor()).isStatic()) {
+ base = 0;
+ } else {
+ base = 1;
+ }
+
+ for (int i = 0; i < fc.numArgs(); i++) {
+
+ TempDescriptor arg = fc.getArg(i);
+ Set<EffectsKey> readSet = me.getEffects().getReadingSet(
+ i + base);
+ Set<EffectsKey> writeSet = me.getEffects().getWritingSet(
+ i + base);
+
+ Set<EffectsKey> strongUpdateSet = me.getEffects()
+ .getStrongUpdateSet(i + base);
+
+ LabelNode argLN = og.td2ln.get(arg);
+ if (argLN != null) {
+ HashSet<TempDescriptor> affectedTDSet = getAccessedTaintNodeSet(argLN);
+ Iterator<TempDescriptor> affectedIter = affectedTDSet
+ .iterator();
+
+ while (affectedIter.hasNext()) {
+
+ TempDescriptor affectedTD = affectedIter.next();
+ if (currentSESE.getInVarSet().contains(affectedTD)) {
+
+ if (readSet != null) {
+ Iterator<EffectsKey> readIter = readSet
+ .iterator();
+ while (readIter.hasNext()) {
+ EffectsKey key = readIter.next();
+ Set<Integer> hrnSet = getCallerHRNId(
+ new Integer(i + base), calleeOG,
+ key.getHRNId(), decomp);
+ Iterator<Integer> hrnIter = hrnSet
+ .iterator();
+ while (hrnIter.hasNext()) {
+ Integer hrnID = (Integer) hrnIter
+ .next();
+ currentSESE.readEffects(affectedTD, key
+ .getFieldDescriptor(), key
+ .getTypeDescriptor(), hrnID);
+ }
+ }
+ }
+
+ if (writeSet != null) {
+ Iterator<EffectsKey> writeIter = writeSet
+ .iterator();
+ while (writeIter.hasNext()) {
+ EffectsKey key = writeIter.next();
+
+ Set<Integer> hrnSet = getCallerHRNId(
+ new Integer(i + base), calleeOG,
+ key.getHRNId(), decomp);
+ Iterator<Integer> hrnIter = hrnSet
+ .iterator();
+ while (hrnIter.hasNext()) {
+ Integer hrnID = (Integer) hrnIter
+ .next();
+ currentSESE.writeEffects(affectedTD,
+ key.getFieldDescriptor(), key
+ .getTypeDescriptor(),
+ hrnID, false);
+ }
+
+ }
+ }
+
+ if (strongUpdateSet != null) {
+ Iterator<EffectsKey> strongUpdateIter = strongUpdateSet
+ .iterator();
+ while (strongUpdateIter.hasNext()) {
+ EffectsKey key = strongUpdateIter.next();
+
+ Set<Integer> hrnSet = getCallerHRNId(
+ new Integer(i + base), calleeOG,
+ key.getHRNId(), decomp);
+ Iterator<Integer> hrnIter = hrnSet
+ .iterator();
+ while (hrnIter.hasNext()) {
+ Integer hrnID = (Integer) hrnIter
+ .next();
+ currentSESE.writeEffects(affectedTD,
+ key.getFieldDescriptor(), key
+ .getTypeDescriptor(),
+ hrnID, true);
+ }
+
+ }
+ }
+
+ }
+
+ }
+
+ }
+
+ }
+
+ }
+ break;
+
+ }
+ }
+
+ private void addLiveInAllocationSite(MethodContext mc, AllocationSite ac){
+ HashSet<AllocationSite> set=mapMethodContextToLiveInAllocationSiteSet.get(mc);
+ if(set==null){
+ set=new HashSet<AllocationSite>();
+ }
+ set.add(ac);
+ mapMethodContextToLiveInAllocationSiteSet.put(mc, set);
+ }
+
+ private void followReference(HeapRegionNode hrn,HashSet<TempDescriptor> tdSet, HashSet<HeapRegionNode> visited, FlatSESEEnterNode currentSESE){
+
+ Iterator<ReferenceEdge> referIter=hrn.iteratorToReferencers();
+ // check whether hrn is referenced by TD
+ while (referIter.hasNext()) {
+ ReferenceEdge referEdge = (ReferenceEdge) referIter.next();
+ if(referEdge.getSrc() instanceof LabelNode){
+ LabelNode ln=(LabelNode)referEdge.getSrc();
+ if(currentSESE.getInVarSet().contains(ln.getTempDescriptor())){
+ tdSet.add(ln.getTempDescriptor());
+ }
+ }else if(referEdge.getSrc() instanceof HeapRegionNode){
+ HeapRegionNode nextHRN=(HeapRegionNode)referEdge.getSrc();
+ if(!visited.contains(nextHRN)){
+ visited.add(nextHRN);
+ followReference(nextHRN,tdSet,visited,currentSESE);
+ }
+
+ }
+ }
+
+ }
+
+ private Set<Integer> getCallerHRNId(Integer paramIdx,
+ OwnershipGraph calleeOG, Integer calleeHRNId,
+ ParameterDecomposition paramDecom) {
+
+ Integer hrnPrimaryID = calleeOG.paramIndex2idPrimary.get(paramIdx);
+ Integer hrnSecondaryID = calleeOG.paramIndex2idSecondary.get(paramIdx);
+
+ if (calleeHRNId.equals(hrnPrimaryID)) {
+ // it references to primary param heap region
+ return paramDecom.getParamObject_hrnIDs(paramIdx);
+ } else if (calleeHRNId.equals(hrnSecondaryID)) {
+ // it references to secondary param heap region
+ return paramDecom.getParamReachable_hrnIDs(paramIdx);
+ }
+
+ return new HashSet<Integer>();
+ }
+
+ private void taintLabelNode(LabelNode ln, int identifier) {
+
+ Iterator<ReferenceEdge> edgeIter = ln.iteratorToReferencees();
+ while (edgeIter.hasNext()) {
+ ReferenceEdge edge = edgeIter.next();
+ HeapRegionNode hrn = edge.getDst();
+
+ Iterator<ReferenceEdge> edgeReferencerIter = hrn
+ .iteratorToReferencers();
+ while (edgeReferencerIter.hasNext()) {
+ ReferenceEdge referencerEdge = edgeReferencerIter.next();
+ OwnershipNode node = referencerEdge.getSrc();
+ if (node instanceof LabelNode) {
+ referencerEdge.unionSESETaintIdentifier(identifier);
+ }else if(node instanceof HeapRegionNode){
+ referencerEdge.unionSESETaintIdentifier(identifier);
+ }
+ }
+
+ }
+
+ }
+
+ private HashSet<TempDescriptor> getReferenceNodeSet(HeapRegionNode hrn){
+
+ HashSet<TempDescriptor> returnSet=new HashSet<TempDescriptor>();
+
+ Iterator<ReferenceEdge> edgeIter=hrn.iteratorToReferencers();
+ while(edgeIter.hasNext()){
+ ReferenceEdge edge=edgeIter.next();
+ if(edge.getSrc() instanceof LabelNode){
+ LabelNode ln=(LabelNode)edge.getSrc();
+ returnSet.add(ln.getTempDescriptor());
+ }
+ }
+
+ return returnSet;
+
+ }
+
+
+ private HashSet<HeapRegionNode> getReferenceHeapIDSet(OwnershipGraph og, TempDescriptor td){
+
+ HashSet<HeapRegionNode> returnSet=new HashSet<HeapRegionNode>();
+
+ LabelNode ln=og.td2ln.get(td);
+ Iterator<ReferenceEdge> edgeIter=ln.iteratorToReferencees();
+ while(edgeIter.hasNext()){
+ ReferenceEdge edge=edgeIter.next();
+ HeapRegionNode hrn=edge.getDst();
+ returnSet.add(hrn);
+ }
+ return returnSet;
+ }
+
+
+ private HashSet<TempDescriptor> getAccessedTaintNodeSet(LabelNode ln) {
+
+ HashSet<TempDescriptor> returnSet = new HashSet<TempDescriptor>();
+
+ Iterator<ReferenceEdge> edgeIter = ln.iteratorToReferencees();
+ while (edgeIter.hasNext()) {
+ ReferenceEdge edge = edgeIter.next();
+ HeapRegionNode hrn = edge.getDst();
+
+ Iterator<ReferenceEdge> edgeReferencerIter = hrn
+ .iteratorToReferencers();
+ while (edgeReferencerIter.hasNext()) {
+ ReferenceEdge referencerEdge = edgeReferencerIter.next();
+
+ if (referencerEdge.getSrc() instanceof LabelNode) {
+ if (!((LabelNode) referencerEdge.getSrc()).equals(ln)) {
+
+ if (referencerEdge.getSESETaintIdentifier() > 0) {
+ TempDescriptor td = ((LabelNode) referencerEdge
+ .getSrc()).getTempDescriptor();
+ returnSet.add(td);
+ }
+ }
+ }
+ }
+
+ }
+ return returnSet;
- private void computeStallsForward( FlatMethod fm ) {
+ }
+
+
+ private void codePlansForward( FlatMethod fm ) {
// start from flat method top, visit every node in
// method exactly once
Set<TempDescriptor> dotSTlive = livenessRootView.get( fn );
if( !seseStack.empty() ) {
- computeStalls_nodeActions( fn,
- dotSTlive,
- dotSTtable,
- dotSTnotAvailSet,
- seseStack.peek()
- );
+ codePlans_nodeActions( fn,
+ dotSTlive,
+ dotSTtable,
+ dotSTnotAvailSet,
+ seseStack.peek()
+ );
}
for( int i = 0; i < fn.numNext(); i++ ) {
}
}
- private void computeStalls_nodeActions( FlatNode fn,
- Set<TempDescriptor> liveSetIn,
- VarSrcTokTable vstTableIn,
- Set<TempDescriptor> notAvailSetIn,
- FlatSESEEnterNode currentSESE ) {
-
+ private void codePlans_nodeActions( FlatNode fn,
+ Set<TempDescriptor> liveSetIn,
+ VarSrcTokTable vstTableIn,
+ Set<TempDescriptor> notAvailSetIn,
+ FlatSESEEnterNode currentSESE ) {
+
CodePlan plan = new CodePlan( currentSESE);
switch( fn.kind() ) {
// if this is an op node, don't stall, copy
// source and delay until we need to use value
- // but check the source type of rhs variable
- // and if dynamic, lhs becomes dynamic, too,
- // and we need to keep dynamic sources during
- Integer srcType
+ // ask whether lhs and rhs sources are dynamic, static, etc.
+ Integer lhsSrcType
+ = vstTableIn.getRefVarSrcType( lhs,
+ currentSESE,
+ currentSESE.getParent() );
+
+ Integer rhsSrcType
= vstTableIn.getRefVarSrcType( rhs,
currentSESE,
currentSESE.getParent() );
- if( srcType.equals( VarSrcTokTable.SrcType_DYNAMIC ) ) {
+ if( rhsSrcType.equals( VarSrcTokTable.SrcType_DYNAMIC ) ) {
+ // if rhs is dynamic going in, lhs will definitely be dynamic
+ // going out of this node, so track that here
plan.addDynAssign( lhs, rhs );
currentSESE.addDynamicVar( lhs );
currentSESE.addDynamicVar( rhs );
- }
+
+ } else if( lhsSrcType.equals( VarSrcTokTable.SrcType_DYNAMIC ) ) {
+ // otherwise, if the lhs is dynamic, but the rhs is not, we
+ // need to update the variable's dynamic source as "current SESE"
+ plan.addDynAssign( lhs );
+ }
// only break if this is an ASSIGN op node,
// otherwise fall through to default case
// check the source type of this variable
Integer srcType
= vstTableIn.getRefVarSrcType( readtmp,
- currentSESE,
- currentSESE.getParent() );
+ currentSESE,
+ currentSESE.getParent() );
if( srcType.equals( VarSrcTokTable.SrcType_DYNAMIC ) ) {
// 1) It is not clear statically where this variable will
// along various control paths, and therefore when we stall,
// just stall for the exact thing we need and move on
plan.addDynamicStall( readtmp );
- currentSESE.addDynamicVar( readtmp );
-
+ currentSESE.addDynamicVar( readtmp );
+
} else if( srcType.equals( VarSrcTokTable.SrcType_STATIC ) ) {
// 2) Single token/age pair: Stall for token/age pair, and copy
// all live variables with same token/age pair at the same
}
} else {
- // the other case for srcs is READY from a parent, however
- // since we are only examining variables that come from
- // children tokens, this should never occur
- assert false;
+ // the other case for srcs is READY, so do nothing
}
// assert that everything being stalled for is in the
// identify sese-age pairs that are statically useful
// and should have an associated SESE variable in code
- Set<VariableSourceToken> staticSet = vstTableIn.getStaticSet();
+ // JUST GET ALL SESE/AGE NAMES FOR NOW, PRUNE LATER,
+ // AND ALWAYS GIVE NAMES TO PARENTS
+ Set<VariableSourceToken> staticSet = vstTableIn.get();
Iterator<VariableSourceToken> vstItr = staticSet.iterator();
while( vstItr.hasNext() ) {
VariableSourceToken vst = vstItr.next();
- currentSESE.addNeededStaticName(
- new SESEandAgePair( vst.getSESE(), vst.getAge() )
- );
- currentSESE.mustTrackAtLeastAge( vst.getAge() );
+
+ // placeholder source tokens are useful results, but
+ // the placeholder static name is never needed
+ if( vst.getSESE().getIsCallerSESEplaceholder() ) {
+ continue;
+ }
+
+ FlatSESEEnterNode sese = currentSESE;
+ while( sese != null ) {
+ sese.addNeededStaticName(
+ new SESEandAgePair( vst.getSESE(), vst.getAge() )
+ );
+ sese.mustTrackAtLeastAge( vst.getAge() );
+
+ sese = sese.getParent();
+ }
}
if( nextVstTable != null && nextLiveIn != null ) {
Hashtable<TempDescriptor, VariableSourceToken> static2dynamicSet =
- thisVstTable.getStatic2DynamicSet( nextVstTable, nextLiveIn );
+ thisVstTable.getStatic2DynamicSet( nextVstTable,
+ nextLiveIn,
+ currentSESE,
+ currentSESE.getParent()
+ );
if( !static2dynamicSet.isEmpty() ) {
}
}
}
+
+
+ public void writeReports( String timeReport ) throws java.io.IOException {
+
+ BufferedWriter bw = new BufferedWriter( new FileWriter( "mlpReport_summary.txt" ) );
+ bw.write( "MLP Analysis Results\n\n" );
+ bw.write( timeReport+"\n\n" );
+ printSESEHierarchy( bw );
+ bw.write( "\n" );
+ printSESEInfo( bw );
+ bw.close();
+
+ Iterator<Descriptor> methItr = ownAnalysis.descriptorsToAnalyze.iterator();
+ while( methItr.hasNext() ) {
+ MethodDescriptor md = (MethodDescriptor) methItr.next();
+ FlatMethod fm = state.getMethodFlat( md );
+ bw = new BufferedWriter( new FileWriter( "mlpReport_"+
+ md.getClassMethodName()+
+ md.getSafeMethodDescriptor()+
+ ".txt" ) );
+ bw.write( "MLP Results for "+md+"\n-------------------\n");
+ bw.write( "\n\nLive-In, Root View\n------------------\n" +fm.printMethod( livenessRootView ) );
+ bw.write( "\n\nVariable Results-Out\n----------------\n" +fm.printMethod( variableResults ) );
+ bw.write( "\n\nNot Available Results-Out\n---------------------\n"+fm.printMethod( notAvailableResults ) );
+ bw.write( "\n\nCode Plans\n----------\n" +fm.printMethod( codePlans ) );
+ bw.write("\n\nSESE Effects\n----------------------\n"+printSESEEffects());
+ bw.close();
+ }
+ }
+
+ private String printSESEEffects() {
+
+ StringWriter writer = new StringWriter();
+
+ Iterator<FlatSESEEnterNode> keyIter = allSESEs.iterator();
+
+ while (keyIter.hasNext()) {
+ FlatSESEEnterNode seseEnter = keyIter.next();
+ String result = seseEnter.getSeseEffectsSet().printSet();
+ if (result.length() > 0) {
+ writer.write("\nSESE " + seseEnter + "\n");
+ writer.write(result);
+ }
+ }
+ keyIter = rootSESEs.iterator();
+ while (keyIter.hasNext()) {
+ FlatSESEEnterNode seseEnter = keyIter.next();
+ if (seseEnter.getIsCallerSESEplaceholder()) {
+ if (!seseEnter.getChildren().isEmpty()) {
+ String result = seseEnter.getSeseEffectsSet().printSet();
+ if (result.length() > 0) {
+ writer.write("\nSESE " + seseEnter + "\n");
+ writer.write(result);
+ }
+ }
+ }
+ }
+
+ return writer.toString();
+
+ }
+
+ private void printSESEHierarchy( BufferedWriter bw ) throws java.io.IOException {
+ bw.write( "SESE Hierarchy\n--------------\n" );
+ Iterator<FlatSESEEnterNode> rootItr = rootSESEs.iterator();
+ while( rootItr.hasNext() ) {
+ FlatSESEEnterNode root = rootItr.next();
+ if( root.getIsCallerSESEplaceholder() ) {
+ if( !root.getChildren().isEmpty() ) {
+ printSESEHierarchyTree( bw, root, 0 );
+ }
+ } else {
+ printSESEHierarchyTree( bw, root, 0 );
+ }
+ }
+ }
+
+ private void printSESEHierarchyTree( BufferedWriter bw,
+ FlatSESEEnterNode fsen,
+ int depth
+ ) throws java.io.IOException {
+ for( int i = 0; i < depth; ++i ) {
+ bw.write( " " );
+ }
+ bw.write( "- "+fsen.getPrettyIdentifier()+"\n" );
+
+ Iterator<FlatSESEEnterNode> childItr = fsen.getChildren().iterator();
+ while( childItr.hasNext() ) {
+ FlatSESEEnterNode fsenChild = childItr.next();
+ printSESEHierarchyTree( bw, fsenChild, depth + 1 );
+ }
+ }
+
+
+ private void printSESEInfo( BufferedWriter bw ) throws java.io.IOException {
+ bw.write("\nSESE info\n-------------\n" );
+ Iterator<FlatSESEEnterNode> rootItr = rootSESEs.iterator();
+ while( rootItr.hasNext() ) {
+ FlatSESEEnterNode root = rootItr.next();
+ if( root.getIsCallerSESEplaceholder() ) {
+ if( !root.getChildren().isEmpty() ) {
+ printSESEInfoTree( bw, root );
+ }
+ } else {
+ printSESEInfoTree( bw, root );
+ }
+ }
+ }
+
+ private void printSESEInfoTree( BufferedWriter bw,
+ FlatSESEEnterNode fsen
+ ) throws java.io.IOException {
+
+ if( !fsen.getIsCallerSESEplaceholder() ) {
+ bw.write( "SESE "+fsen.getPrettyIdentifier()+" {\n" );
+
+ bw.write( " in-set: "+fsen.getInVarSet()+"\n" );
+ Iterator<TempDescriptor> tItr = fsen.getInVarSet().iterator();
+ while( tItr.hasNext() ) {
+ TempDescriptor inVar = tItr.next();
+ if( fsen.getReadyInVarSet().contains( inVar ) ) {
+ bw.write( " (ready) "+inVar+"\n" );
+ }
+ if( fsen.getStaticInVarSet().contains( inVar ) ) {
+ bw.write( " (static) "+inVar+"\n" );
+ }
+ if( fsen.getDynamicInVarSet().contains( inVar ) ) {
+ bw.write( " (dynamic)"+inVar+"\n" );
+ }
+ }
+
+ bw.write( " out-set: "+fsen.getOutVarSet()+"\n" );
+ bw.write( "}\n" );
+ }
+
+ Iterator<FlatSESEEnterNode> childItr = fsen.getChildren().iterator();
+ while( childItr.hasNext() ) {
+ FlatSESEEnterNode fsenChild = childItr.next();
+ printSESEInfoTree( bw, fsenChild );
+ }
+ }
}
projects / IRC.git / blobdiff