3 import java.io.BufferedWriter;
4 import java.io.FileWriter;
5 import java.io.IOException;
6 import java.io.StringWriter;
7 import java.util.Enumeration;
8 import java.util.HashSet;
9 import java.util.Hashtable;
10 import java.util.Iterator;
11 import java.util.LinkedList;
14 import java.util.Stack;
15 import java.util.Map.Entry;
16 import Analysis.CallGraph.CallGraph;
17 import Analysis.CallGraph.JavaCallGraph;
18 import Analysis.OwnershipAnalysis.AllocationSite;
19 import Analysis.OwnershipAnalysis.EffectsKey;
20 import Analysis.OwnershipAnalysis.HeapRegionNode;
21 import Analysis.OwnershipAnalysis.LabelNode;
22 import Analysis.OwnershipAnalysis.MethodContext;
23 import Analysis.OwnershipAnalysis.MethodEffects;
24 import Analysis.OwnershipAnalysis.OwnershipAnalysis;
25 import Analysis.OwnershipAnalysis.OwnershipGraph;
26 import Analysis.OwnershipAnalysis.OwnershipNode;
27 import Analysis.OwnershipAnalysis.ParameterDecomposition;
28 import Analysis.OwnershipAnalysis.ReachabilitySet;
29 import Analysis.OwnershipAnalysis.ReferenceEdge;
30 import Analysis.OwnershipAnalysis.TokenTuple;
31 import Analysis.OwnershipAnalysis.TokenTupleSet;
33 import IR.FieldDescriptor;
34 import IR.MethodDescriptor;
37 import IR.TypeDescriptor;
40 import IR.Flat.FlatCall;
41 import IR.Flat.FlatCondBranch;
42 import IR.Flat.FlatEdge;
43 import IR.Flat.FlatElementNode;
44 import IR.Flat.FlatFieldNode;
45 import IR.Flat.FlatMethod;
46 import IR.Flat.FlatNew;
47 import IR.Flat.FlatNode;
48 import IR.Flat.FlatOpNode;
49 import IR.Flat.FlatReturnNode;
50 import IR.Flat.FlatSESEEnterNode;
51 import IR.Flat.FlatSESEExitNode;
52 import IR.Flat.FlatSetElementNode;
53 import IR.Flat.FlatSetFieldNode;
54 import IR.Flat.FlatWriteDynamicVarNode;
55 import IR.Flat.TempDescriptor;
58 public class MLPAnalysis {
60 // data from the compiler
62 private TypeUtil typeUtil;
63 private CallGraph callGraph;
64 private OwnershipAnalysis ownAnalysis;
67 // an implicit SESE is automatically spliced into
68 // the IR graph around the C main before this analysis--it
69 // is nothing special except that we can make assumptions
70 // about it, such as the whole program ends when it ends
71 private FlatSESEEnterNode mainSESE;
73 // SESEs that are the root of an SESE tree belong to this
74 // set--the main SESE is always a root, statically SESEs
75 // inside methods are a root because we don't know how they
76 // will fit into the runtime tree of SESEs
77 private Set<FlatSESEEnterNode> rootSESEs;
79 // simply a set of every reachable SESE in the program, not
80 // including caller placeholder SESEs
81 private Set<FlatSESEEnterNode> allSESEs;
84 // A mapping of flat nodes to the stack of SESEs for that node, where
85 // an SESE is the child of the SESE directly below it on the stack.
86 // These stacks do not reflect the heirarchy over methods calls--whenever
87 // there is an empty stack it means all variables are available.
88 private Hashtable< FlatNode, Stack<FlatSESEEnterNode> > seseStacks;
90 private Hashtable< FlatNode, Set<TempDescriptor> > livenessRootView;
91 private Hashtable< FlatNode, Set<TempDescriptor> > livenessVirtualReads;
92 private Hashtable< FlatNode, VarSrcTokTable > variableResults;
93 private Hashtable< FlatNode, Set<TempDescriptor> > notAvailableResults;
94 private Hashtable< FlatNode, CodePlan > codePlans;
96 private Hashtable< FlatSESEEnterNode, Set<TempDescriptor> > notAvailableIntoSESE;
98 private Hashtable< FlatEdge, FlatWriteDynamicVarNode > wdvNodesToSpliceIn;
100 private Hashtable< MethodContext, HashSet<AllocationSite>> mapMethodContextToLiveInAllocationSiteSet;
102 private Hashtable < FlatNode, ParentChildConflictsMap > conflictsResults;
103 private Hashtable< FlatMethod, MethodSummary > methodSummaryResults;
104 private OwnershipAnalysis ownAnalysisForSESEConflicts;
105 private Hashtable <FlatNode, ConflictGraph> conflictGraphResults;
107 // temporal data structures to track analysis progress.
108 private MethodSummary currentMethodSummary;
109 private HashSet<PreEffectsKey> preeffectsSet;
110 private Hashtable<FlatNode, Boolean> isAfterChildSESEIndicatorMap;
111 private Hashtable<FlatNode, SESESummary> seseSummaryMap;
112 private Hashtable<ConflictGraph, HashSet<SESELock>> conflictGraphLockMap;
113 static private int uniqueLockSetId = 0;
115 public static int maxSESEage = -1;
118 // use these methods in BuildCode to have access to analysis results
119 public FlatSESEEnterNode getMainSESE() {
123 public Set<FlatSESEEnterNode> getRootSESEs() {
127 public Set<FlatSESEEnterNode> getAllSESEs() {
131 public int getMaxSESEage() {
136 public CodePlan getCodePlan( FlatNode fn ) {
137 CodePlan cp = codePlans.get( fn );
142 public MLPAnalysis( State state,
145 OwnershipAnalysis ownAnalysis
148 double timeStartAnalysis = (double) System.nanoTime();
152 this.callGraph = callGraph;
153 this.ownAnalysis = ownAnalysis;
154 this.maxSESEage = state.MLP_MAXSESEAGE;
156 rootSESEs = new HashSet<FlatSESEEnterNode>();
157 allSESEs = new HashSet<FlatSESEEnterNode>();
159 seseStacks = new Hashtable< FlatNode, Stack<FlatSESEEnterNode> >();
160 livenessRootView = new Hashtable< FlatNode, Set<TempDescriptor> >();
161 livenessVirtualReads = new Hashtable< FlatNode, Set<TempDescriptor> >();
162 variableResults = new Hashtable< FlatNode, VarSrcTokTable >();
163 notAvailableResults = new Hashtable< FlatNode, Set<TempDescriptor> >();
164 codePlans = new Hashtable< FlatNode, CodePlan >();
165 wdvNodesToSpliceIn = new Hashtable< FlatEdge, FlatWriteDynamicVarNode >();
167 notAvailableIntoSESE = new Hashtable< FlatSESEEnterNode, Set<TempDescriptor> >();
169 mapMethodContextToLiveInAllocationSiteSet = new Hashtable< MethodContext, HashSet<AllocationSite>>();
171 conflictsResults = new Hashtable < FlatNode, ParentChildConflictsMap >();
172 methodSummaryResults=new Hashtable<FlatMethod, MethodSummary>();
173 conflictGraphResults=new Hashtable<FlatNode, ConflictGraph>();
175 seseSummaryMap= new Hashtable<FlatNode, SESESummary>();
176 isAfterChildSESEIndicatorMap= new Hashtable<FlatNode, Boolean>();
177 conflictGraphLockMap=new Hashtable<ConflictGraph, HashSet<SESELock>>();
179 FlatMethod fmMain = state.getMethodFlat( typeUtil.getMain() );
181 mainSESE = (FlatSESEEnterNode) fmMain.getNext(0);
182 mainSESE.setfmEnclosing( fmMain );
183 mainSESE.setmdEnclosing( fmMain.getMethod() );
184 mainSESE.setcdEnclosing( fmMain.getMethod().getClassDesc() );
188 // run analysis on each method that is actually called
189 // reachability analysis already computed this so reuse
190 Iterator<Descriptor> methItr = ownAnalysis.descriptorsToAnalyze.iterator();
191 while( methItr.hasNext() ) {
192 Descriptor d = methItr.next();
193 FlatMethod fm = state.getMethodFlat( d );
195 // find every SESE from methods that may be called
196 // and organize them into roots and children
197 buildForestForward( fm );
201 // 2nd pass, results are saved in FlatSESEEnterNode, so
202 // intermediate results, for safety, are discarded
203 Iterator<FlatSESEEnterNode> rootItr = rootSESEs.iterator();
204 while( rootItr.hasNext() ) {
205 FlatSESEEnterNode root = rootItr.next();
206 livenessAnalysisBackward( root,
213 methItr = ownAnalysis.descriptorsToAnalyze.iterator();
214 while( methItr.hasNext() ) {
215 Descriptor d = methItr.next();
216 FlatMethod fm = state.getMethodFlat( d );
218 // starting from roots do a forward, fixed-point
219 // variable analysis for refinement and stalls
220 variableAnalysisForward( fm );
223 // 4th pass, compute liveness contribution from
224 // virtual reads discovered in variable pass
225 rootItr = rootSESEs.iterator();
226 while( rootItr.hasNext() ) {
227 FlatSESEEnterNode root = rootItr.next();
228 livenessAnalysisBackward( root,
235 SOMETHING IS WRONG WITH THIS, DON'T USE IT UNTIL IT CAN BE FIXED
238 methItr = ownAnalysis.descriptorsToAnalyze.iterator();
239 while( methItr.hasNext() ) {
240 Descriptor d = methItr.next();
241 FlatMethod fm = state.getMethodFlat( d );
243 // prune variable results in one traversal
244 // by removing reference variables that are not live
245 pruneVariableResultsWithLiveness( fm );
251 methItr = ownAnalysis.descriptorsToAnalyze.iterator();
252 while( methItr.hasNext() ) {
253 Descriptor d = methItr.next();
254 FlatMethod fm = state.getMethodFlat( d );
256 // compute what is not available at every program
257 // point, in a forward fixed-point pass
258 notAvailableForward( fm );
261 if(state.METHODEFFECTS){
262 // new pass, sese effects analysis
263 methItr = ownAnalysis.descriptorsToAnalyze.iterator();
264 JavaCallGraph javaCallGraph = new JavaCallGraph(state,tu);
265 while( methItr.hasNext() ) {
266 Descriptor d = methItr.next();
267 FlatMethod fm = state.getMethodFlat( d );
268 methodEffects(fm,javaCallGraph);
271 // Parent/child memory conflicts analysis
272 seseConflictsForward(javaCallGraph);
274 Set<MethodContext> keySet=mapMethodContextToLiveInAllocationSiteSet.keySet();
275 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
276 MethodContext methodContext = (MethodContext) iterator.next();
277 HashSet<AllocationSite> asSet=mapMethodContextToLiveInAllocationSiteSet.get(methodContext);
278 for (Iterator iterator2 = asSet.iterator(); iterator2.hasNext();) {
279 AllocationSite allocationSite = (AllocationSite) iterator2.next();
283 // disjoint analysis with a set of flagged allocation sites of live-in variables & stall sites
285 ownAnalysisForSESEConflicts = new OwnershipAnalysis(state,
288 ownAnalysis.liveness,
289 ownAnalysis.arrayReferencees,
290 state.OWNERSHIPALLOCDEPTH, false,
291 false, state.OWNERSHIPALIASFILE,
293 mapMethodContextToLiveInAllocationSiteSet);
295 methItr = ownAnalysisForSESEConflicts.descriptorsToAnalyze.iterator();
296 while (methItr.hasNext()) {
297 Descriptor d = methItr.next();
298 FlatMethod fm = state.getMethodFlat(d);
299 debugFunction(ownAnalysisForSESEConflicts, fm);
302 } catch (IOException e) {
303 System.err.println(e);
306 // postSESEConflictsForward(javaCallGraph);
307 // another pass for making graph
313 methItr = ownAnalysis.descriptorsToAnalyze.iterator();
314 while (methItr.hasNext()) {
315 Descriptor d = methItr.next();
316 FlatMethod fm = state.getMethodFlat(d);
317 makeConflictGraph2(fm);
320 Enumeration<FlatNode> keyEnum1=conflictGraphResults.keys();
321 while (keyEnum1.hasMoreElements()) {
322 FlatNode flatNode = (FlatNode) keyEnum1.nextElement();
323 ConflictGraph conflictGraph=conflictGraphResults.get(flatNode);
324 conflictGraph.analyzeConflicts();
325 conflictGraphResults.put(flatNode, conflictGraph);
329 Enumeration<FlatNode> keyEnum=conflictGraphResults.keys();
330 while (keyEnum.hasMoreElements()) {
331 FlatNode key = (FlatNode) keyEnum.nextElement();
332 ConflictGraph cg=conflictGraphResults.get(key);
334 if(cg.hasConflictEdge()){
335 cg.writeGraph("ConflictGraphFor"+key, false);
337 } catch (IOException e) {
338 System.out.println("Error writing");
346 methItr = ownAnalysis.descriptorsToAnalyze.iterator();
347 while( methItr.hasNext() ) {
348 Descriptor d = methItr.next();
349 FlatMethod fm = state.getMethodFlat( d );
351 // compute a plan for code injections
352 codePlansForward( fm );
356 // splice new IR nodes into graph after all
357 // analysis passes are complete
358 Iterator spliceItr = wdvNodesToSpliceIn.entrySet().iterator();
359 while( spliceItr.hasNext() ) {
360 Map.Entry me = (Map.Entry) spliceItr.next();
361 FlatWriteDynamicVarNode fwdvn = (FlatWriteDynamicVarNode) me.getValue();
362 fwdvn.spliceIntoIR();
366 double timeEndAnalysis = (double) System.nanoTime();
367 double dt = (timeEndAnalysis - timeStartAnalysis)/(Math.pow( 10.0, 9.0 ) );
368 String treport = String.format( "The mlp analysis took %.3f sec.", dt );
369 System.out.println( treport );
371 if( state.MLPDEBUG ) {
373 writeReports( treport );
374 } catch( IOException e ) {}
379 private void buildForestForward( FlatMethod fm ) {
381 // start from flat method top, visit every node in
382 // method exactly once, find SESEs and remember
383 // roots and child relationships
384 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
385 flatNodesToVisit.add( fm );
387 Set<FlatNode> visited = new HashSet<FlatNode>();
389 Stack<FlatSESEEnterNode> seseStackFirst = new Stack<FlatSESEEnterNode>();
390 seseStacks.put( fm, seseStackFirst );
392 while( !flatNodesToVisit.isEmpty() ) {
393 Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
394 FlatNode fn = fnItr.next();
396 Stack<FlatSESEEnterNode> seseStack = seseStacks.get( fn );
397 assert seseStack != null;
399 flatNodesToVisit.remove( fn );
402 buildForest_nodeActions( fn, seseStack, fm );
404 for( int i = 0; i < fn.numNext(); i++ ) {
405 FlatNode nn = fn.getNext( i );
407 if( !visited.contains( nn ) ) {
408 flatNodesToVisit.add( nn );
410 // clone stack and send along each analysis path
411 seseStacks.put( nn, (Stack<FlatSESEEnterNode>)seseStack.clone() );
417 private void buildForest_nodeActions( FlatNode fn,
418 Stack<FlatSESEEnterNode> seseStack,
420 switch( fn.kind() ) {
422 case FKind.FlatSESEEnterNode: {
423 FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
425 if( !fsen.getIsCallerSESEplaceholder() ) {
426 allSESEs.add( fsen );
429 fsen.setfmEnclosing( fm );
430 fsen.setmdEnclosing( fm.getMethod() );
431 fsen.setcdEnclosing( fm.getMethod().getClassDesc() );
433 if( seseStack.empty() ) {
434 rootSESEs.add( fsen );
435 fsen.setParent( null );
437 seseStack.peek().addChild( fsen );
438 fsen.setParent( seseStack.peek() );
441 seseStack.push( fsen );
444 case FKind.FlatSESEExitNode: {
445 FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
446 assert !seseStack.empty();
447 FlatSESEEnterNode fsen = seseStack.pop();
450 case FKind.FlatReturnNode: {
451 FlatReturnNode frn = (FlatReturnNode) fn;
452 if( !seseStack.empty() &&
453 !seseStack.peek().getIsCallerSESEplaceholder()
455 throw new Error( "Error: return statement enclosed within SESE "+
456 seseStack.peek().getPrettyIdentifier() );
464 private void livenessAnalysisBackward( FlatSESEEnterNode fsen,
466 Hashtable< FlatSESEExitNode, Set<TempDescriptor> > liveout ) {
468 // start from an SESE exit, visit nodes in reverse up to
469 // SESE enter in a fixed-point scheme, where children SESEs
470 // should already be analyzed and therefore can be skipped
471 // because child SESE enter node has all necessary info
472 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
475 flatNodesToVisit.add( fsen.getfmEnclosing().getFlatExit() );
477 flatNodesToVisit.add( fsen.getFlatExit() );
480 Hashtable<FlatNode, Set<TempDescriptor>> livenessResults =
481 new Hashtable< FlatNode, Set<TempDescriptor> >();
484 liveout = new Hashtable< FlatSESEExitNode, Set<TempDescriptor> >();
487 while( !flatNodesToVisit.isEmpty() ) {
488 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
489 flatNodesToVisit.remove( fn );
491 Set<TempDescriptor> prev = livenessResults.get( fn );
493 // merge sets from control flow joins
494 Set<TempDescriptor> u = new HashSet<TempDescriptor>();
495 for( int i = 0; i < fn.numNext(); i++ ) {
496 FlatNode nn = fn.getNext( i );
497 Set<TempDescriptor> s = livenessResults.get( nn );
503 Set<TempDescriptor> curr = liveness_nodeActions( fn, u, fsen, toplevel, liveout);
505 // if a new result, schedule backward nodes for analysis
506 if( !curr.equals( prev ) ) {
507 livenessResults.put( fn, curr );
509 // don't flow backwards past current SESE enter
510 if( !fn.equals( fsen ) ) {
511 for( int i = 0; i < fn.numPrev(); i++ ) {
512 FlatNode nn = fn.getPrev( i );
513 flatNodesToVisit.add( nn );
519 Set<TempDescriptor> s = livenessResults.get( fsen );
521 fsen.addInVarSet( s );
524 // remember liveness per node from the root view as the
525 // global liveness of variables for later passes to use
527 livenessRootView.putAll( livenessResults );
530 // post-order traversal, so do children first
531 Iterator<FlatSESEEnterNode> childItr = fsen.getChildren().iterator();
532 while( childItr.hasNext() ) {
533 FlatSESEEnterNode fsenChild = childItr.next();
534 livenessAnalysisBackward( fsenChild, false, liveout );
538 private Set<TempDescriptor> liveness_nodeActions( FlatNode fn,
539 Set<TempDescriptor> liveIn,
540 FlatSESEEnterNode currentSESE,
542 Hashtable< FlatSESEExitNode, Set<TempDescriptor> > liveout
544 switch( fn.kind() ) {
546 case FKind.FlatSESEExitNode:
548 FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
549 if( !liveout.containsKey( fsexn ) ) {
550 liveout.put( fsexn, new HashSet<TempDescriptor>() );
552 liveout.get( fsexn ).addAll( liveIn );
554 // no break, sese exits should also execute default actions
557 // handle effects of statement in reverse, writes then reads
558 TempDescriptor [] writeTemps = fn.writesTemps();
559 for( int i = 0; i < writeTemps.length; ++i ) {
560 liveIn.remove( writeTemps[i] );
563 FlatSESEExitNode fsexn = currentSESE.getFlatExit();
564 Set<TempDescriptor> livetemps = liveout.get( fsexn );
565 if( livetemps != null &&
566 livetemps.contains( writeTemps[i] ) ) {
567 // write to a live out temp...
568 // need to put in SESE liveout set
569 currentSESE.addOutVar( writeTemps[i] );
574 TempDescriptor [] readTemps = fn.readsTemps();
575 for( int i = 0; i < readTemps.length; ++i ) {
576 liveIn.add( readTemps[i] );
579 Set<TempDescriptor> virtualReadTemps = livenessVirtualReads.get( fn );
580 if( virtualReadTemps != null ) {
581 liveIn.addAll( virtualReadTemps );
592 private void variableAnalysisForward( FlatMethod fm ) {
594 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
595 flatNodesToVisit.add( fm );
597 while( !flatNodesToVisit.isEmpty() ) {
598 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
599 flatNodesToVisit.remove( fn );
601 Stack<FlatSESEEnterNode> seseStack = seseStacks.get( fn );
602 assert seseStack != null;
604 VarSrcTokTable prev = variableResults.get( fn );
606 // merge sets from control flow joins
607 VarSrcTokTable curr = new VarSrcTokTable();
608 for( int i = 0; i < fn.numPrev(); i++ ) {
609 FlatNode nn = fn.getPrev( i );
610 VarSrcTokTable incoming = variableResults.get( nn );
611 curr.merge( incoming );
614 if( !seseStack.empty() ) {
615 variable_nodeActions( fn, curr, seseStack.peek() );
618 // if a new result, schedule forward nodes for analysis
619 if( !curr.equals( prev ) ) {
620 variableResults.put( fn, curr );
622 for( int i = 0; i < fn.numNext(); i++ ) {
623 FlatNode nn = fn.getNext( i );
624 flatNodesToVisit.add( nn );
630 private void variable_nodeActions( FlatNode fn,
631 VarSrcTokTable vstTable,
632 FlatSESEEnterNode currentSESE ) {
633 switch( fn.kind() ) {
635 case FKind.FlatSESEEnterNode: {
636 FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
637 assert fsen.equals( currentSESE );
639 vstTable.age( currentSESE );
640 vstTable.assertConsistency();
643 case FKind.FlatSESEExitNode: {
644 FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
645 FlatSESEEnterNode fsen = fsexn.getFlatEnter();
646 assert currentSESE.getChildren().contains( fsen );
648 // remap all of this child's children tokens to be
649 // from this child as the child exits
650 vstTable.remapChildTokens( fsen );
652 // liveness virtual reads are things that might be
653 // written by an SESE and should be added to the in-set
654 // anything virtually read by this SESE should be pruned
655 // of parent or sibling sources
656 Set<TempDescriptor> liveVars = livenessRootView.get( fn );
657 Set<TempDescriptor> fsenVirtReads = vstTable.calcVirtReadsAndPruneParentAndSiblingTokens( fsen, liveVars );
658 Set<TempDescriptor> fsenVirtReadsOld = livenessVirtualReads.get( fn );
659 if( fsenVirtReadsOld != null ) {
660 fsenVirtReads.addAll( fsenVirtReadsOld );
662 livenessVirtualReads.put( fn, fsenVirtReads );
665 // then all child out-set tokens are guaranteed
666 // to be filled in, so clobber those entries with
667 // the latest, clean sources
668 Iterator<TempDescriptor> outVarItr = fsen.getOutVarSet().iterator();
669 while( outVarItr.hasNext() ) {
670 TempDescriptor outVar = outVarItr.next();
671 HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
673 VariableSourceToken vst =
674 new VariableSourceToken( ts,
679 vstTable.remove( outVar );
682 vstTable.assertConsistency();
686 case FKind.FlatOpNode: {
687 FlatOpNode fon = (FlatOpNode) fn;
689 if( fon.getOp().getOp() == Operation.ASSIGN ) {
690 TempDescriptor lhs = fon.getDest();
691 TempDescriptor rhs = fon.getLeft();
693 vstTable.remove( lhs );
695 Set<VariableSourceToken> forAddition = new HashSet<VariableSourceToken>();
697 Iterator<VariableSourceToken> itr = vstTable.get( rhs ).iterator();
698 while( itr.hasNext() ) {
699 VariableSourceToken vst = itr.next();
701 HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
704 if( currentSESE.getChildren().contains( vst.getSESE() ) ) {
705 // if the source comes from a child, copy it over
706 forAddition.add( new VariableSourceToken( ts,
713 // otherwise, stamp it as us as the source
714 forAddition.add( new VariableSourceToken( ts,
723 vstTable.addAll( forAddition );
725 // only break if this is an ASSIGN op node,
726 // otherwise fall through to default case
727 vstTable.assertConsistency();
732 // note that FlatOpNode's that aren't ASSIGN
733 // fall through to this default case
735 TempDescriptor [] writeTemps = fn.writesTemps();
736 if( writeTemps.length > 0 ) {
739 // for now, when writeTemps > 1, make sure
740 // its a call node, programmer enforce only
741 // doing stuff like calling a print routine
742 //assert writeTemps.length == 1;
743 if( writeTemps.length > 1 ) {
744 assert fn.kind() == FKind.FlatCall ||
745 fn.kind() == FKind.FlatMethod;
749 vstTable.remove( writeTemps[0] );
751 HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
752 ts.add( writeTemps[0] );
754 vstTable.add( new VariableSourceToken( ts,
762 vstTable.assertConsistency();
769 private void pruneVariableResultsWithLiveness( FlatMethod fm ) {
771 // start from flat method top, visit every node in
772 // method exactly once
773 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
774 flatNodesToVisit.add( fm );
776 Set<FlatNode> visited = new HashSet<FlatNode>();
778 while( !flatNodesToVisit.isEmpty() ) {
779 Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
780 FlatNode fn = fnItr.next();
782 flatNodesToVisit.remove( fn );
785 Set<TempDescriptor> rootLiveSet = livenessRootView.get( fn );
786 VarSrcTokTable vstTable = variableResults.get( fn );
788 vstTable.pruneByLiveness( rootLiveSet );
790 for( int i = 0; i < fn.numNext(); i++ ) {
791 FlatNode nn = fn.getNext( i );
793 if( !visited.contains( nn ) ) {
794 flatNodesToVisit.add( nn );
801 private void notAvailableForward( FlatMethod fm ) {
803 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
804 flatNodesToVisit.add( fm );
806 while( !flatNodesToVisit.isEmpty() ) {
807 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
808 flatNodesToVisit.remove( fn );
810 Stack<FlatSESEEnterNode> seseStack = seseStacks.get( fn );
811 assert seseStack != null;
813 Set<TempDescriptor> prev = notAvailableResults.get( fn );
815 Set<TempDescriptor> curr = new HashSet<TempDescriptor>();
816 for( int i = 0; i < fn.numPrev(); i++ ) {
817 FlatNode nn = fn.getPrev( i );
818 Set<TempDescriptor> notAvailIn = notAvailableResults.get( nn );
819 if( notAvailIn != null ) {
820 curr.addAll( notAvailIn );
824 if( !seseStack.empty() ) {
825 notAvailable_nodeActions( fn, curr, seseStack.peek() );
828 // if a new result, schedule forward nodes for analysis
829 if( !curr.equals( prev ) ) {
830 notAvailableResults.put( fn, curr );
832 for( int i = 0; i < fn.numNext(); i++ ) {
833 FlatNode nn = fn.getNext( i );
834 flatNodesToVisit.add( nn );
840 private void notAvailable_nodeActions( FlatNode fn,
841 Set<TempDescriptor> notAvailSet,
842 FlatSESEEnterNode currentSESE ) {
844 // any temps that are removed from the not available set
845 // at this node should be marked in this node's code plan
846 // as temps to be grabbed at runtime!
848 switch( fn.kind() ) {
850 case FKind.FlatSESEEnterNode: {
851 FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
852 assert fsen.equals( currentSESE );
854 // keep a copy of what's not available into the SESE
855 // and restore it at the matching exit node
856 Set<TempDescriptor> notAvailCopy = new HashSet<TempDescriptor>();
857 Iterator<TempDescriptor> tdItr = notAvailSet.iterator();
858 while( tdItr.hasNext() ) {
859 notAvailCopy.add( tdItr.next() );
861 notAvailableIntoSESE.put( fsen, notAvailCopy );
866 case FKind.FlatSESEExitNode: {
867 FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
868 FlatSESEEnterNode fsen = fsexn.getFlatEnter();
869 assert currentSESE.getChildren().contains( fsen );
871 notAvailSet.addAll( fsen.getOutVarSet() );
873 Set<TempDescriptor> notAvailIn = notAvailableIntoSESE.get( fsen );
874 assert notAvailIn != null;
875 notAvailSet.addAll( notAvailIn );
879 case FKind.FlatMethod: {
883 case FKind.FlatOpNode: {
884 FlatOpNode fon = (FlatOpNode) fn;
886 if( fon.getOp().getOp() == Operation.ASSIGN ) {
887 TempDescriptor lhs = fon.getDest();
888 TempDescriptor rhs = fon.getLeft();
890 // copy makes lhs same availability as rhs
891 if( notAvailSet.contains( rhs ) ) {
892 notAvailSet.add( lhs );
894 notAvailSet.remove( lhs );
897 // only break if this is an ASSIGN op node,
898 // otherwise fall through to default case
903 // note that FlatOpNode's that aren't ASSIGN
904 // fall through to this default case
906 TempDescriptor [] writeTemps = fn.writesTemps();
907 for( int i = 0; i < writeTemps.length; i++ ) {
908 TempDescriptor wTemp = writeTemps[i];
909 notAvailSet.remove( wTemp );
911 TempDescriptor [] readTemps = fn.readsTemps();
912 for( int i = 0; i < readTemps.length; i++ ) {
913 TempDescriptor rTemp = readTemps[i];
914 notAvailSet.remove( rTemp );
916 // if this variable has exactly one source, potentially
917 // get other things from this source as well
918 VarSrcTokTable vstTable = variableResults.get( fn );
920 VSTWrapper vstIfStatic = new VSTWrapper();
922 vstTable.getRefVarSrcType( rTemp,
927 if( srcType.equals( VarSrcTokTable.SrcType_STATIC ) ) {
929 VariableSourceToken vst = vstIfStatic.vst;
931 Iterator<VariableSourceToken> availItr = vstTable.get( vst.getSESE(),
935 // look through things that are also available from same source
936 while( availItr.hasNext() ) {
937 VariableSourceToken vstAlsoAvail = availItr.next();
939 Iterator<TempDescriptor> refVarItr = vstAlsoAvail.getRefVars().iterator();
940 while( refVarItr.hasNext() ) {
941 TempDescriptor refVarAlso = refVarItr.next();
943 // if a variable is available from the same source, AND it ALSO
944 // only comes from one statically known source, mark it available
945 VSTWrapper vstIfStaticNotUsed = new VSTWrapper();
946 Integer srcTypeAlso =
947 vstTable.getRefVarSrcType( refVarAlso,
951 if( srcTypeAlso.equals( VarSrcTokTable.SrcType_STATIC ) ) {
952 notAvailSet.remove( refVarAlso );
963 private void debugFunction(OwnershipAnalysis oa2, FlatMethod fm) {
965 String methodName="SomeWork";
967 MethodDescriptor md=fm.getMethod();
968 HashSet<MethodContext> mcSet=oa2.getAllMethodContextSetByDescriptor(md);
969 Iterator<MethodContext> mcIter=mcSet.iterator();
971 while(mcIter.hasNext()){
972 MethodContext mc=mcIter.next();
974 OwnershipGraph og=oa2.getOwnvershipGraphByMethodContext(mc);
976 if(fm.toString().indexOf(methodName)>0){
978 og.writeGraph("SECONDGRAPH"+fm.toString(),
979 true, // write labels (variables)
980 true, // selectively hide intermediate temp vars
981 true, // prune unreachable heap regions
982 false, // show back edges to confirm graph validity
983 false, // show parameter indices (unmaintained!)
984 true, // hide subset reachability states
985 false);// hide edge taints
986 } catch (IOException e) {
987 System.out.println("Error writing debug capture.");
995 private void methodEffects(FlatMethod fm, CallGraph callGraph) {
997 MethodDescriptor md=fm.getMethod();
998 HashSet<MethodContext> mcSet=ownAnalysis.getAllMethodContextSetByDescriptor(md);
999 Iterator<MethodContext> mcIter=mcSet.iterator();
1001 while(mcIter.hasNext()){
1002 MethodContext mc=mcIter.next();
1004 Set<FlatNode> visited = new HashSet<FlatNode>();
1006 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
1007 flatNodesToVisit.add(fm);
1009 Hashtable<TempDescriptor, TempDescriptor> invarMap=new Hashtable<TempDescriptor,TempDescriptor>();
1011 while (!flatNodesToVisit.isEmpty()) {
1012 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
1013 flatNodesToVisit.remove(fn);
1015 Stack<FlatSESEEnterNode> seseStack = seseStacks.get(fn);
1016 assert seseStack != null;
1018 if (!seseStack.empty()) {
1019 effects_nodeActions(mc, fn, seseStack.peek(), callGraph,invarMap);
1022 flatNodesToVisit.remove(fn);
1025 for (int i = 0; i < fn.numNext(); i++) {
1026 FlatNode nn = fn.getNext(i);
1027 if (!visited.contains(nn)) {
1028 flatNodesToVisit.add(nn);
1039 private void analyzeRelatedAllocationSite(MethodDescriptor callerMD,
1040 MethodContext calleeMC, HashSet<Integer> paramIndexSet,
1041 HashSet<HeapRegionNode> visitedHRN) {
1043 HashSet<MethodContext> mcSet = ownAnalysis
1044 .getAllMethodContextSetByDescriptor(callerMD);
1046 if (mcSet != null) {
1048 Iterator<MethodContext> mcIter = mcSet.iterator();
1050 FlatMethod callerFM = state.getMethodFlat(callerMD);
1052 while (mcIter.hasNext()) {
1053 MethodContext mc = mcIter.next();
1055 Set<FlatNode> visited = new HashSet<FlatNode>();
1056 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
1057 flatNodesToVisit.add(callerFM);
1059 while (!flatNodesToVisit.isEmpty()) {
1060 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
1061 flatNodesToVisit.remove(fn);
1063 analyzeRelatedAllocationSite_NodeAction(fn, mc, calleeMC,
1064 paramIndexSet,visitedHRN);
1066 flatNodesToVisit.remove(fn);
1069 for (int i = 0; i < fn.numNext(); i++) {
1070 FlatNode nn = fn.getNext(i);
1071 if (!visited.contains(nn)) {
1072 flatNodesToVisit.add(nn);
1081 private void analyzeRelatedAllocationSite_NodeAction(FlatNode fn, MethodContext callerMC,
1082 MethodContext calleeMC,
1083 HashSet<Integer> paramIndexSet, HashSet<HeapRegionNode> visitedHRN) {
1085 OwnershipGraph og = ownAnalysis
1086 .getOwnvershipGraphByMethodContext(callerMC);
1088 switch (fn.kind()) {
1090 case FKind.FlatCall: {
1092 FlatCall fc = (FlatCall) fn;
1095 if(fc.numArgs()>0 && fc.getMethod().equals(calleeMC.getDescriptor())){
1096 MethodContext calleeMCfromOG = ownAnalysis.getCalleeMethodContext(
1099 // disable below condition. currently collect all possible
1100 // allocation sites without regarding method context
1102 // if (calleeMC.equals(calleeMCfromOG)) { // in this case, this
1103 // method context calls corresponding callee.
1106 if (((MethodDescriptor) calleeMC.getDescriptor()).isStatic()) {
1112 for (Iterator iterator = paramIndexSet.iterator(); iterator
1114 Integer integer = (Integer) iterator.next();
1116 int paramIdx = integer - base;
1117 if (paramIdx >= 0) {
1118 // if paramIdx is less than 0, assumes that it is
1119 // related with wrong method contexts.
1120 TempDescriptor arg = fc.getArg(paramIdx);
1121 LabelNode argLN = og.td2ln.get(arg);
1122 if (argLN != null) {
1123 Iterator<ReferenceEdge> iterEdge = argLN
1124 .iteratorToReferencees();
1125 while (iterEdge.hasNext()) {
1126 ReferenceEdge referenceEdge = (ReferenceEdge) iterEdge
1129 HeapRegionNode dstHRN = referenceEdge.getDst();
1130 if (dstHRN.isParameter()) {
1131 if (!visitedHRN.contains(dstHRN)) {
1132 setupRelatedAllocSiteAnalysis(og, callerMC,
1133 dstHRN, visitedHRN);
1136 // System.out.println("FLAGGED "+callerMC+":fc="+fc+":arg="+arg+" , paramIdx="+paramIdx);
1137 flagAllocationSite(callerMC, dstHRN
1138 .getAllocationSite());
1155 private void setupRelatedAllocSiteAnalysis(OwnershipGraph og,
1156 MethodContext mc, HeapRegionNode dstHRN,
1157 HashSet<HeapRegionNode> visitedHRN) {
1159 HashSet<Integer> paramIndexSet = new HashSet<Integer>();
1161 // collect corresponding param index
1162 Set<Integer> pIndexSet = og.idPrimary2paramIndexSet.get(dstHRN.getID());
1163 if (pIndexSet != null) {
1164 for (Iterator iterator = pIndexSet.iterator(); iterator.hasNext();) {
1165 Integer integer = (Integer) iterator.next();
1166 paramIndexSet.add(integer);
1170 Set<Integer> sIndexSet = og.idSecondary2paramIndexSet.get(dstHRN
1172 if (sIndexSet != null) {
1173 for (Iterator iterator = sIndexSet.iterator(); iterator.hasNext();) {
1174 Integer integer = (Integer) iterator.next();
1175 paramIndexSet.add(integer);
1179 if (mc.getDescriptor() instanceof MethodDescriptor) {
1180 Set callerSet = callGraph.getCallerSet((MethodDescriptor) mc
1182 for (Iterator iterator = callerSet.iterator(); iterator.hasNext();) {
1183 Object obj = (Object) iterator.next();
1184 if (obj instanceof MethodDescriptor) {
1185 MethodDescriptor callerMD = (MethodDescriptor) obj;
1187 if(callerMD.equals(mc.getDescriptor())){
1190 analyzeRelatedAllocationSite(callerMD, mc, paramIndexSet,visitedHRN);
1197 private void effects_nodeActions(MethodContext mc, FlatNode fn,
1198 FlatSESEEnterNode currentSESE, CallGraph callGraph,Hashtable<TempDescriptor, TempDescriptor> invarMap) {
1200 OwnershipGraph og = ownAnalysis.getOwnvershipGraphByMethodContext(mc);
1202 switch (fn.kind()) {
1204 case FKind.FlatSESEEnterNode: {
1206 FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
1207 assert fsen.equals(currentSESE);
1209 if (!fsen.getIsCallerSESEplaceholder()) {
1210 // uniquely taint each live-in variable
1211 Set<TempDescriptor> set = fsen.getInVarSet();
1212 Iterator<TempDescriptor> iter = set.iterator();
1214 while (iter.hasNext()) {
1215 TempDescriptor td = iter.next();
1216 LabelNode ln = og.td2ln.get(td);
1218 if(currentSESE.getSeseEffectsSet().getMapTempDescToInVarIdx().containsKey(td)){
1219 idx=currentSESE.getSeseEffectsSet().getInVarIdx(td);
1223 int taint = (int) Math.pow(2, idx);
1224 taintLabelNode(ln, taint,currentSESE.getSeseEffectsSet());
1225 currentSESE.getSeseEffectsSet().setInVarIdx(idx, td);
1227 // collects related allocation sites
1228 Iterator<ReferenceEdge> referenceeIter = ln
1229 .iteratorToReferencees();
1230 while (referenceeIter.hasNext()) {
1231 ReferenceEdge referenceEdge = (ReferenceEdge) referenceeIter
1233 HeapRegionNode dstHRN = referenceEdge.getDst();
1234 if (dstHRN.isParameter()) {
1236 HashSet<HeapRegionNode> visitedHRN = new HashSet<HeapRegionNode>();
1237 visitedHRN.add(dstHRN);
1238 setupRelatedAllocSiteAnalysis(og, mc, dstHRN,
1242 // System.out.println("FLAGGED "+fsen+":"+td);
1243 flagAllocationSite(mc, dstHRN
1244 .getAllocationSite());
1257 case FKind.FlatSESEExitNode: {
1258 FlatSESEExitNode fsexit = (FlatSESEExitNode) fn;
1260 if (!fsexit.getFlatEnter().getIsCallerSESEplaceholder()) {
1262 // clear taint information of live-in variables
1263 Set<Integer> keySet=og.id2hrn.keySet();
1264 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1265 Integer hrnID = (Integer) iterator.next();
1266 HeapRegionNode hrn=og.id2hrn.get(hrnID);
1267 Iterator<ReferenceEdge> edgeIter=hrn.iteratorToReferencers();
1268 while (edgeIter.hasNext()) {
1269 ReferenceEdge refEdge = (ReferenceEdge) edgeIter
1271 refEdge.setSESETaintIdentifier(0);
1275 FlatSESEEnterNode enterNode = fsexit.getFlatEnter();
1276 FlatSESEEnterNode parent = enterNode.getParent();
1277 if (parent != null) {
1279 SESEEffectsSet set = enterNode.getSeseEffectsSet();
1280 Hashtable<TempDescriptor, HashSet<SESEEffectsKey>> readTable = set
1282 Hashtable<TempDescriptor, HashSet<SESEEffectsKey>> parentReadTable = parent
1283 .getSeseEffectsSet().getReadTable();
1284 Set<TempDescriptor> keys = readTable.keySet();
1285 Iterator<TempDescriptor> keyIter = keys.iterator();
1286 while (keyIter.hasNext()) {
1287 TempDescriptor td = (TempDescriptor) keyIter.next();
1288 HashSet<SESEEffectsKey> effectsSet = readTable.get(td);
1289 HashSet<SESEEffectsKey> parentEffectsSet = parentReadTable
1291 if (parentEffectsSet == null) {
1292 parentEffectsSet = new HashSet<SESEEffectsKey>();
1295 for (Iterator iterator = effectsSet.iterator(); iterator
1297 SESEEffectsKey seseKey = (SESEEffectsKey) iterator
1299 parentEffectsSet.add(new SESEEffectsKey(seseKey
1300 .getFieldDescriptor(), seseKey
1301 .getTypeDescriptor(), seseKey.getHRNId(),
1302 seseKey.getHRNUniqueId()));
1305 parentReadTable.put(td, parentEffectsSet);
1308 Hashtable<TempDescriptor, HashSet<SESEEffectsKey>> writeTable = set
1310 Hashtable<TempDescriptor, HashSet<SESEEffectsKey>> parentWriteTable = parent
1311 .getSeseEffectsSet().getWriteTable();
1312 keys = writeTable.keySet();
1313 keyIter = keys.iterator();
1314 while (keyIter.hasNext()) {
1315 TempDescriptor td = (TempDescriptor) keyIter.next();
1316 HashSet<SESEEffectsKey> effectsSet = writeTable.get(td);
1317 HashSet<SESEEffectsKey> parentEffectsSet = parentWriteTable
1319 if (parentEffectsSet == null) {
1320 parentEffectsSet = new HashSet<SESEEffectsKey>();
1323 for (Iterator iterator = effectsSet.iterator(); iterator
1325 SESEEffectsKey seseKey = (SESEEffectsKey) iterator
1327 parentEffectsSet.add(new SESEEffectsKey(seseKey
1328 .getFieldDescriptor(), seseKey
1329 .getTypeDescriptor(), seseKey.getHRNId(),
1330 seseKey.getHRNUniqueId()));
1333 parentWriteTable.put(td, parentEffectsSet);
1336 Hashtable<TempDescriptor, HashSet<SESEEffectsKey>> strongUpdateTable = set
1337 .getStrongUpdateTable();
1338 Hashtable<TempDescriptor, HashSet<SESEEffectsKey>> parentstrongUpdateTable = parent
1339 .getSeseEffectsSet().getStrongUpdateTable();
1340 keys = strongUpdateTable.keySet();
1341 keyIter = keys.iterator();
1342 while (keyIter.hasNext()) {
1343 TempDescriptor td = (TempDescriptor) keyIter.next();
1344 HashSet<SESEEffectsKey> effectsSet = strongUpdateTable
1346 HashSet<SESEEffectsKey> parentEffectsSet = parentstrongUpdateTable
1348 if (parentEffectsSet == null) {
1349 parentEffectsSet = new HashSet<SESEEffectsKey>();
1352 for (Iterator iterator = effectsSet.iterator(); iterator
1354 SESEEffectsKey seseKey = (SESEEffectsKey) iterator
1356 parentEffectsSet.add(new SESEEffectsKey(seseKey
1357 .getFieldDescriptor(), seseKey
1358 .getTypeDescriptor(), seseKey.getHRNId(),
1359 seseKey.getHRNUniqueId()));
1362 parentstrongUpdateTable.put(td, parentEffectsSet);
1372 case FKind.FlatFieldNode: {
1374 FlatFieldNode ffn = (FlatFieldNode) fn;
1375 TempDescriptor dst = ffn.getDst();
1376 TempDescriptor src = ffn.getSrc();
1377 FieldDescriptor field = ffn.getField();
1379 LabelNode srcLN = og.td2ln.get(src);
1381 Iterator<ReferenceEdge> edgeIter=srcLN.iteratorToReferencees();
1382 int taintIdentifier=0;
1383 while (edgeIter.hasNext()) {
1384 ReferenceEdge referenceEdge = (ReferenceEdge) edgeIter
1386 HeapRegionNode refHRN=referenceEdge.getDst();
1387 taintIdentifier=currentSESE.getSeseEffectsSet().getTaint(referenceEdge);
1388 // taintIdentifier=referenceEdge.getSESETaintIdentifier();
1390 // figure out which invar has related effects
1391 Hashtable<TempDescriptor, Integer> map=currentSESE.getSeseEffectsSet().getMapTempDescToInVarIdx();
1392 Set<TempDescriptor> keySet=map.keySet();
1393 for (Iterator iterator = keySet.iterator(); iterator
1395 TempDescriptor inVarTD = (TempDescriptor) iterator
1397 int inVarMask=(int) Math.pow(2, map.get(inVarTD).intValue());
1398 if((inVarMask&taintIdentifier)>0){
1399 // found related invar, contribute effects
1400 currentSESE.readEffects(inVarTD, field.getSymbol(),src.getType(), refHRN);
1406 if(!field.getType().isImmutable()){
1407 LabelNode dstLN = og.td2ln.get(dst);
1408 edgeIter=dstLN.iteratorToReferencees();
1409 while (edgeIter.hasNext()) {
1410 ReferenceEdge referenceEdge = (ReferenceEdge) edgeIter
1412 currentSESE.getSeseEffectsSet().mapEdgeToTaint(referenceEdge, taintIdentifier);
1413 // referenceEdge.unionSESETaintIdentifier(taintIdentifier);
1422 case FKind.FlatOpNode:{
1424 FlatOpNode fon=(FlatOpNode)fn;
1425 TempDescriptor dest=fon.getDest();
1426 TempDescriptor src=fon.getLeft();
1428 if(currentSESE.getInVarSet().contains(src)){
1429 int idx=currentSESE.getSeseEffectsSet().getInVarIdx(src);
1434 //mark dest's edges for corresponding sese live in-var.
1435 LabelNode srcLN = og.td2ln.get(dest);
1436 if (srcLN != null) {
1437 Iterator<ReferenceEdge> refEdgeIter=srcLN.iteratorToReferencees();
1438 while (refEdgeIter.hasNext()) {
1439 ReferenceEdge edge = refEdgeIter.next();
1440 int newTaint = (int) Math.pow(2, idx);
1441 // System.out.println("fon="+fon);
1442 // System.out.println(currentSESE+" src:"+src+"->"+"dest:"+dest+" with taint="+newTaint);
1443 // System.out.println("referenceEdge="+edge);
1444 currentSESE.getSeseEffectsSet().mapEdgeToTaint(edge, newTaint);
1445 // System.out.println("after tainting="+edge.getSESETaintIdentifier());
1451 case FKind.FlatElementNode:{
1453 FlatElementNode fsen=(FlatElementNode)fn;
1454 TempDescriptor src = fsen.getSrc();
1455 TempDescriptor dst = fsen.getDst();
1456 String field="___element_";
1458 LabelNode srcLN = og.td2ln.get(src);
1459 int taintIdentifier=0;
1461 Iterator<ReferenceEdge> edgeIter=srcLN.iteratorToReferencees();
1462 while (edgeIter.hasNext()) {
1463 ReferenceEdge referenceEdge = (ReferenceEdge) edgeIter
1465 HeapRegionNode dstHRN=referenceEdge.getDst();
1466 taintIdentifier=currentSESE.getSeseEffectsSet().getTaint(referenceEdge);
1467 // taintIdentifier=referenceEdge.getSESETaintIdentifier();
1469 // figure out which invar has related effects
1470 Hashtable<TempDescriptor, Integer> map=currentSESE.getSeseEffectsSet().getMapTempDescToInVarIdx();
1471 Set<TempDescriptor> keySet=map.keySet();
1472 for (Iterator iterator = keySet.iterator(); iterator
1474 TempDescriptor inVarTD = (TempDescriptor) iterator
1476 int inVarMask=(int) Math.pow(2, map.get(inVarTD).intValue());
1477 if((inVarMask&taintIdentifier)>0){
1478 // found related invar, contribute effects
1479 currentSESE.readEffects(inVarTD, field,src.getType(), dstHRN);
1487 LabelNode dstLN = og.td2ln.get(dst);
1489 Iterator<ReferenceEdge> edgeIter=dstLN.iteratorToReferencees();
1490 while (edgeIter.hasNext()) {
1491 ReferenceEdge referenceEdge = (ReferenceEdge) edgeIter
1493 currentSESE.getSeseEffectsSet().mapEdgeToTaint(referenceEdge, taintIdentifier);
1494 // referenceEdge.unionSESETaintIdentifier(taintIdentifier);
1500 case FKind.FlatSetElementNode: {
1502 FlatSetElementNode fsen = (FlatSetElementNode) fn;
1503 TempDescriptor dst = fsen.getDst();
1504 TypeDescriptor tdElement = dst.getType().dereference();
1506 String field = "___element_";
1508 LabelNode dstLN=og.td2ln.get(dst);
1511 Iterator<ReferenceEdge> edgeIter=dstLN.iteratorToReferencees();
1512 while (edgeIter.hasNext()) {
1513 ReferenceEdge referenceEdge = (ReferenceEdge) edgeIter
1515 HeapRegionNode dstHRN=referenceEdge.getDst();
1516 int edgeTaint=currentSESE.getSeseEffectsSet().getTaint(referenceEdge);
1517 // int edgeTaint=referenceEdge.getSESETaintIdentifier();
1519 // we can do a strong update here if one of two cases
1521 boolean strongUpdate=false;
1522 if (field != null && !dst.getType().isImmutable()
1523 && ((dstHRN.getNumReferencers() == 1) || // case 1
1524 (dstHRN.isSingleObject() && dstLN
1525 .getNumReferencees() == 1) // case 2
1527 strongUpdate = true;
1531 // figure out which invar has related effects
1532 Hashtable<TempDescriptor, Integer> map=currentSESE.getSeseEffectsSet().getMapTempDescToInVarIdx();
1533 Set<TempDescriptor> keySet=map.keySet();
1534 for (Iterator iterator = keySet.iterator(); iterator
1536 TempDescriptor inVarTD = (TempDescriptor) iterator
1538 int inVarMask=(int) Math.pow(2, map.get(inVarTD).intValue());
1539 if((inVarMask&edgeTaint)>0){
1540 // found related invar, contribute effects
1541 currentSESE.writeEffects(inVarTD, field, dst.getType(),dstHRN, strongUpdate);
1552 case FKind.FlatSetFieldNode: {
1554 FlatSetFieldNode fsen = (FlatSetFieldNode) fn;
1555 TempDescriptor dst = fsen.getDst();
1556 FieldDescriptor field = fsen.getField();
1558 LabelNode dstLN = og.td2ln.get(dst);
1561 Iterator<ReferenceEdge> edgeIter=dstLN.iteratorToReferencees();
1562 while (edgeIter.hasNext()) {
1563 ReferenceEdge referenceEdge = (ReferenceEdge) edgeIter
1565 HeapRegionNode dstHRN=referenceEdge.getDst();
1566 int edgeTaint=currentSESE.getSeseEffectsSet().getTaint(referenceEdge);
1567 // int edgeTaint=referenceEdge.getSESETaintIdentifier();
1569 // we can do a strong update here if one of two cases
1571 boolean strongUpdate=false;
1572 if (field != null && !field.getType().isImmutable()
1573 && field != OwnershipAnalysis
1574 .getArrayField(field.getType())
1575 && ((dstHRN.getNumReferencers() == 1) || // case 1
1576 (dstHRN.isSingleObject() && dstLN
1577 .getNumReferencees() == 1) // case 2
1579 strongUpdate = true;
1583 // figure out which invar has related effects
1584 Hashtable<TempDescriptor, Integer> map = currentSESE
1585 .getSeseEffectsSet().getMapTempDescToInVarIdx();
1586 Set<TempDescriptor> keySet = map.keySet();
1587 for (Iterator iterator = keySet.iterator(); iterator
1589 TempDescriptor inVarTD = (TempDescriptor) iterator
1591 int inVarMask = (int) Math.pow(2, map.get(inVarTD)
1593 if ((inVarMask & edgeTaint) > 0) {
1594 // found related invar, contribute effects
1595 currentSESE.writeEffects(inVarTD,
1596 field.getSymbol(), dst.getType(), dstHRN,
1607 case FKind.FlatCall: {
1608 FlatCall fc = (FlatCall) fn;
1610 MethodContext calleeMC = ownAnalysis.getCalleeMethodContext(mc, fc);
1612 MethodEffects me = ownAnalysis.getMethodEffectsAnalysis()
1613 .getMethodEffectsByMethodContext(calleeMC);
1615 OwnershipGraph calleeOG = ownAnalysis
1616 .getOwnvershipGraphByMethodContext(calleeMC);
1619 FlatMethod fm = state.getMethodFlat(fc.getMethod());
1620 ParameterDecomposition decomp = new ParameterDecomposition(
1621 ownAnalysis, fc, fm, calleeMC, calleeOG, og);
1624 if (((MethodDescriptor) calleeMC.getDescriptor()).isStatic()) {
1630 for (int i = 0; i < fc.numArgs()+base; i++) {
1632 TempDescriptor arg ;
1633 Set<EffectsKey> readSet;
1634 Set<EffectsKey> writeSet;
1635 Set<EffectsKey> strongUpdateSet;
1639 boolean isThis=false;
1640 if(i==fc.numArgs()){
1643 Integer hrnPrimaryID = calleeOG.paramIndex2idPrimary.get(paramIdx);
1644 Integer hrnSecondaryID = calleeOG.paramIndex2idSecondary.get(paramIdx);
1645 readSet = me.getEffects().getReadingSet(
1647 writeSet = me.getEffects().getWritingSet(
1649 strongUpdateSet = me.getEffects()
1650 .getStrongUpdateSet(0);
1655 readSet = me.getEffects().getReadingSet(
1657 writeSet = me.getEffects().getWritingSet(
1659 strongUpdateSet = me.getEffects()
1660 .getStrongUpdateSet(i + base);
1663 LabelNode argLN = og.td2ln.get(arg);
1665 Iterator<ReferenceEdge> edgeIter=argLN.iteratorToReferencees();
1666 while (edgeIter.hasNext()) {
1667 ReferenceEdge referenceEdge = (ReferenceEdge) edgeIter
1669 HeapRegionNode dstHRN=referenceEdge.getDst();
1670 int edgeTaint=currentSESE.getSeseEffectsSet().getTaint(referenceEdge);
1671 // int edgeTaint=referenceEdge.getSESETaintIdentifier();
1673 // figure out which invar has related effects
1674 Hashtable<TempDescriptor, Integer> map = currentSESE
1675 .getSeseEffectsSet().getMapTempDescToInVarIdx();
1676 Set<TempDescriptor> keySet = map.keySet();
1677 for (Iterator iterator = keySet.iterator(); iterator
1679 TempDescriptor inVarTD = (TempDescriptor) iterator
1681 int inVarMask = (int) Math.pow(2, map.get(inVarTD)
1684 if ((inVarMask & edgeTaint) > 0) {
1685 // found related invar, contribute effects
1687 if (readSet != null) {
1688 Iterator<EffectsKey> readIter = readSet
1690 while (readIter.hasNext()) {
1691 EffectsKey key = readIter.next();
1692 Set<Integer> hrnSet = getCallerHRNId(
1693 new Integer(paramIdx), calleeOG,
1694 key.getHRNId(), decomp);
1695 Iterator<Integer> hrnIter = hrnSet
1697 while (hrnIter.hasNext()) {
1698 Integer hrnID = (Integer) hrnIter
1701 HeapRegionNode refHRN = og.id2hrn
1704 currentSESE.readEffects(inVarTD, key
1705 .getFieldDescriptor(), key
1706 .getTypeDescriptor(), refHRN);
1712 if (writeSet != null) {
1713 Iterator<EffectsKey> writeIter = writeSet
1715 while (writeIter.hasNext()) {
1716 EffectsKey key = writeIter.next();
1718 Set<Integer> hrnSet = getCallerHRNId(
1719 new Integer(paramIdx), calleeOG,
1720 key.getHRNId(), decomp);
1721 Iterator<Integer> hrnIter = hrnSet
1723 while (hrnIter.hasNext()) {
1724 Integer hrnID = (Integer) hrnIter
1727 HeapRegionNode refHRN = og.id2hrn
1730 currentSESE.writeEffects(inVarTD,
1731 key.getFieldDescriptor(), key
1732 .getTypeDescriptor(),
1739 if (strongUpdateSet != null) {
1740 Iterator<EffectsKey> strongUpdateIter = strongUpdateSet
1742 while (strongUpdateIter.hasNext()) {
1743 EffectsKey key = strongUpdateIter
1746 Set<Integer> hrnSet = getCallerHRNId(
1747 new Integer(paramIdx),
1748 calleeOG, key.getHRNId(),
1750 Iterator<Integer> hrnIter = hrnSet
1752 while (hrnIter.hasNext()) {
1753 Integer hrnID = (Integer) hrnIter
1756 HeapRegionNode refHRN = og.id2hrn
1759 currentSESE.writeEffects(inVarTD,
1760 key.getFieldDescriptor(),
1761 key.getTypeDescriptor(),
1765 } // end of if (strongUpdateSet != null)
1767 } // end of if ((inVarMask & edgeTaint) > 0)
1781 private void flagAllocationSite(MethodContext mc, AllocationSite ac){
1782 HashSet<AllocationSite> set=mapMethodContextToLiveInAllocationSiteSet.get(mc);
1784 set=new HashSet<AllocationSite>();
1787 mapMethodContextToLiveInAllocationSiteSet.put(mc, set);
1790 private void followReference(HeapRegionNode hrn,HashSet<TempDescriptor> tdSet, HashSet<HeapRegionNode> visited, FlatSESEEnterNode currentSESE){
1792 Iterator<ReferenceEdge> referIter=hrn.iteratorToReferencers();
1793 // check whether hrn is referenced by TD
1794 while (referIter.hasNext()) {
1795 ReferenceEdge referEdge = (ReferenceEdge) referIter.next();
1796 if(referEdge.getSrc() instanceof LabelNode){
1797 LabelNode ln=(LabelNode)referEdge.getSrc();
1798 if(currentSESE.getInVarSet().contains(ln.getTempDescriptor())){
1799 tdSet.add(ln.getTempDescriptor());
1801 }else if(referEdge.getSrc() instanceof HeapRegionNode){
1802 HeapRegionNode nextHRN=(HeapRegionNode)referEdge.getSrc();
1803 if(!visited.contains(nextHRN)){
1804 visited.add(nextHRN);
1805 followReference(nextHRN,tdSet,visited,currentSESE);
1813 private Set<Integer> getCallerHRNId(Integer paramIdx,
1814 OwnershipGraph calleeOG, Integer calleeHRNId,
1815 ParameterDecomposition paramDecom) {
1817 Integer hrnPrimaryID = calleeOG.paramIndex2idPrimary.get(paramIdx);
1818 Integer hrnSecondaryID = calleeOG.paramIndex2idSecondary.get(paramIdx);
1820 if (calleeHRNId.equals(hrnPrimaryID)) {
1821 // it references to primary param heap region
1822 return paramDecom.getParamObject_hrnIDs(paramIdx);
1823 } else if (calleeHRNId.equals(hrnSecondaryID)) {
1824 // it references to secondary param heap region
1825 return paramDecom.getParamReachable_hrnIDs(paramIdx);
1828 return new HashSet<Integer>();
1831 private void taintLabelNode(LabelNode ln, int identifier, SESEEffectsSet effectSet) {
1833 Iterator<ReferenceEdge> edgeIter = ln.iteratorToReferencees();
1834 while (edgeIter.hasNext()) {
1835 ReferenceEdge edge = edgeIter.next();
1836 effectSet.mapEdgeToTaint(edge, identifier);
1841 private HashSet<HeapRegionNode> getReferenceHeapIDSet(OwnershipGraph og, TempDescriptor td){
1843 HashSet<HeapRegionNode> returnSet=new HashSet<HeapRegionNode>();
1845 LabelNode ln=og.td2ln.get(td);
1847 Iterator<ReferenceEdge> edgeIter=ln.iteratorToReferencees();
1848 while(edgeIter.hasNext()){
1849 ReferenceEdge edge=edgeIter.next();
1850 HeapRegionNode hrn=edge.getDst();
1858 private HashSet<ReferenceEdge> getRefEdgeSetReferenceToSameHRN(
1859 OwnershipGraph og, TempDescriptor td) {
1861 HashSet<ReferenceEdge> returnSet = new HashSet<ReferenceEdge>();
1863 HashSet<HeapRegionNode> heapIDs = getReferenceHeapIDSet(og, td);
1864 for (Iterator<HeapRegionNode> iterator = heapIDs.iterator(); iterator
1866 HeapRegionNode heapRegionNode = (HeapRegionNode) iterator.next();
1867 Iterator<ReferenceEdge> referenceeIter = heapRegionNode
1868 .iteratorToReferencees();
1869 while (referenceeIter.hasNext()) {
1870 ReferenceEdge edge = (ReferenceEdge) referenceeIter.next();
1871 if (edge.getSrc() instanceof HeapRegionNode) {
1872 returnSet.add(edge);
1879 private HashSet<TempDescriptor> getTempDescSetReferenceToSameHRN(
1880 OwnershipGraph og, TempDescriptor td) {
1882 HashSet<TempDescriptor> returnSet = new HashSet<TempDescriptor>();
1884 HashSet<HeapRegionNode> heapIDs = getReferenceHeapIDSet(og, td);
1885 for (Iterator<HeapRegionNode> iterator = heapIDs.iterator(); iterator
1887 HeapRegionNode heapRegionNode = (HeapRegionNode) iterator.next();
1888 Iterator<ReferenceEdge> referencerIter = heapRegionNode
1889 .iteratorToReferencers();
1890 while (referencerIter.hasNext()) {
1891 ReferenceEdge edge = (ReferenceEdge) referencerIter.next();
1892 if (edge.getSrc() instanceof LabelNode) {
1893 LabelNode ln = (LabelNode) edge.getSrc();
1894 returnSet.add(ln.getTempDescriptor());
1901 private void DFSVisit( MethodDescriptor md,
1902 LinkedList<MethodDescriptor> sorted,
1903 HashSet<MethodDescriptor> discovered, JavaCallGraph javaCallGraph) {
1907 Iterator itr = javaCallGraph.getCallerSet(md).iterator();
1908 while (itr.hasNext()) {
1909 MethodDescriptor mdCaller = (MethodDescriptor) itr.next();
1911 if (!discovered.contains(mdCaller)) {
1912 DFSVisit(mdCaller, sorted, discovered, javaCallGraph);
1916 sorted.addFirst(md);
1920 private LinkedList<MethodDescriptor> topologicalSort(Set set,
1921 JavaCallGraph javaCallGraph) {
1922 HashSet<MethodDescriptor> discovered = new HashSet<MethodDescriptor>();
1923 LinkedList<MethodDescriptor> sorted = new LinkedList<MethodDescriptor>();
1925 Iterator<MethodDescriptor> itr = set.iterator();
1926 while (itr.hasNext()) {
1927 MethodDescriptor md = itr.next();
1929 if (!discovered.contains(md)) {
1930 DFSVisit(md, sorted, discovered, javaCallGraph);
1937 private void calculateCovering(ConflictGraph conflictGraph){
1938 uniqueLockSetId=0; // reset lock counter for every new conflict graph
1939 HashSet<ConflictEdge> fineToCover = new HashSet<ConflictEdge>();
1940 HashSet<ConflictEdge> coarseToCover = new HashSet<ConflictEdge>();
1941 HashSet<SESELock> lockSet=new HashSet<SESELock>();
1943 HashSet<ConflictEdge> tempCover = conflictGraph.getEdgeSet();
1944 for (Iterator iterator = tempCover.iterator(); iterator.hasNext();) {
1945 ConflictEdge conflictEdge = (ConflictEdge) iterator.next();
1946 if(conflictEdge.getType()==ConflictEdge.FINE_GRAIN_EDGE){
1947 fineToCover.add(conflictEdge);
1948 }else if(conflictEdge.getType()==ConflictEdge.COARSE_GRAIN_EDGE){
1949 coarseToCover.add(conflictEdge);
1953 HashSet<ConflictEdge> toCover=new HashSet<ConflictEdge>();
1954 toCover.addAll(fineToCover);
1955 toCover.addAll(coarseToCover);
1957 while (!toCover.isEmpty()) {
1959 SESELock seseLock = new SESELock();
1960 seseLock.setID(uniqueLockSetId++);
1964 do{ // fine-grained edge
1968 for (Iterator iterator = fineToCover.iterator(); iterator
1972 ConflictEdge edge = (ConflictEdge) iterator.next();
1973 if(seseLock.getConflictNodeSet().size()==0){
1975 if(seseLock.isWriteNode(edge.getVertexU())){
1976 // mark as fine_write
1977 if(edge.getVertexU() instanceof StallSiteNode){
1978 type=ConflictNode.PARENT_WRITE;
1980 type=ConflictNode.FINE_WRITE;
1982 seseLock.addConflictNode(edge.getVertexU(), type);
1984 // mark as fine_read
1985 if(edge.getVertexU() instanceof StallSiteNode){
1986 type=ConflictNode.PARENT_READ;
1988 type=ConflictNode.FINE_READ;
1990 seseLock.addConflictNode(edge.getVertexU(), type);
1992 if(edge.getVertexV()!=edge.getVertexU()){
1993 if(seseLock.isWriteNode(edge.getVertexV())){
1994 // mark as fine_write
1995 if(edge.getVertexV() instanceof StallSiteNode){
1996 type=ConflictNode.PARENT_WRITE;
1998 type=ConflictNode.FINE_WRITE;
2000 seseLock.addConflictNode(edge.getVertexV(), type);
2002 // mark as fine_read
2003 if(edge.getVertexV() instanceof StallSiteNode){
2004 type=ConflictNode.PARENT_READ;
2006 type=ConflictNode.FINE_READ;
2008 seseLock.addConflictNode(edge.getVertexV(), type);
2012 seseLock.addConflictEdge(edge);
2013 fineToCover.remove(edge);
2014 break;// exit iterator loop
2015 }// end of initial setup
2017 ConflictNode newNode;
2018 if((newNode=seseLock.getNewNodeConnectedWithGroup(edge))!=null){
2019 // new node has a fine-grained edge to all current node
2020 // If there is a coarse grained edge where need a fine edge, it's okay to add the node
2021 // but the edge must remain uncovered.
2025 if(seseLock.isWriteNode(newNode)){
2026 if(newNode instanceof StallSiteNode){
2027 type=ConflictNode.PARENT_WRITE;
2029 type=ConflictNode.FINE_WRITE;
2031 seseLock.setNodeType(newNode,type);
2033 if(newNode instanceof StallSiteNode){
2034 type=ConflictNode.PARENT_READ;
2036 type=ConflictNode.FINE_READ;
2038 seseLock.setNodeType(newNode,type);
2041 seseLock.addEdge(edge);
2042 HashSet<ConflictEdge> edgeSet=newNode.getEdgeSet();
2043 for (Iterator iterator2 = edgeSet.iterator(); iterator2
2045 ConflictEdge conflictEdge = (ConflictEdge) iterator2
2049 // mark all fine edges between new node and nodes in the group as covered
2050 if(!conflictEdge.getVertexU().equals(newNode)){
2051 if(seseLock.containsConflictNode(conflictEdge.getVertexU())){
2053 seseLock.addConflictEdge(conflictEdge);
2054 fineToCover.remove(conflictEdge);
2056 }else if(!conflictEdge.getVertexV().equals(newNode)){
2057 if(seseLock.containsConflictNode(conflictEdge.getVertexV())){
2059 seseLock.addConflictEdge(conflictEdge);
2060 fineToCover.remove(conflictEdge);
2066 break;// exit iterator loop
2074 for (Iterator iterator = coarseToCover.iterator(); iterator
2077 ConflictEdge edge = (ConflictEdge) iterator.next();
2079 if(seseLock.getConflictNodeSet().size()==0){
2081 if(seseLock.hasSelfCoarseEdge(edge.getVertexU())){
2082 // node has a coarse-grained edge with itself
2083 if(!(edge.getVertexU() instanceof StallSiteNode)){
2084 // and it is not parent
2085 type=ConflictNode.SCC;
2087 type=ConflictNode.PARENT_COARSE;
2089 seseLock.addConflictNode(edge.getVertexU(), type);
2091 if(edge.getVertexU() instanceof StallSiteNode){
2092 type=ConflictNode.PARENT_COARSE;
2094 type=ConflictNode.COARSE;
2096 seseLock.addConflictNode(edge.getVertexU(), type);
2098 if(seseLock.hasSelfCoarseEdge(edge.getVertexV())){
2099 // node has a coarse-grained edge with itself
2100 if(!(edge.getVertexV() instanceof StallSiteNode)){
2101 // and it is not parent
2102 type=ConflictNode.SCC;
2104 type=ConflictNode.PARENT_COARSE;
2106 seseLock.addConflictNode(edge.getVertexV(), type);
2108 if(edge.getVertexV() instanceof StallSiteNode){
2109 type=ConflictNode.PARENT_COARSE;
2111 type=ConflictNode.COARSE;
2113 seseLock.addConflictNode(edge.getVertexV(), type);
2116 coarseToCover.remove(edge);
2117 seseLock.addConflictEdge(edge);
2118 break;// exit iterator loop
2119 }// end of initial setup
2122 ConflictNode newNode;
2123 if((newNode=seseLock.getNewNodeConnectedWithGroup(edge))!=null){
2124 // new node has a coarse-grained edge to all fine-read, fine-write, parent
2127 if(seseLock.hasSelfCoarseEdge(newNode)){
2129 if(newNode instanceof StallSiteNode){
2130 type=ConflictNode.PARENT_COARSE;
2132 type=ConflictNode.SCC;
2134 seseLock.setNodeType(newNode, type);
2136 if(newNode instanceof StallSiteNode){
2137 type=ConflictNode.PARENT_COARSE;
2139 type=ConflictNode.COARSE;
2141 seseLock.setNodeType(newNode, type);
2144 seseLock.addEdge(edge);
2145 HashSet<ConflictEdge> edgeSet=newNode.getEdgeSet();
2146 for (Iterator iterator2 = edgeSet.iterator(); iterator2
2148 ConflictEdge conflictEdge = (ConflictEdge) iterator2
2150 // mark all coarse edges between new node and nodes in the group as covered
2151 if(!conflictEdge.getVertexU().equals(newNode)){
2152 if(seseLock.containsConflictNode(conflictEdge.getVertexU())){
2154 seseLock.addConflictEdge(conflictEdge);
2155 coarseToCover.remove(conflictEdge);
2157 }else if(!conflictEdge.getVertexV().equals(newNode)){
2158 if(seseLock.containsConflictNode(conflictEdge.getVertexV())){
2160 seseLock.addConflictEdge(conflictEdge);
2161 coarseToCover.remove(conflictEdge);
2166 break;// exit iterator loop
2172 lockSet.add(seseLock);
2175 toCover.addAll(fineToCover);
2176 toCover.addAll(coarseToCover);
2180 conflictGraphLockMap.put(conflictGraph, lockSet);
2183 private void synthesizeLocks(){
2184 Set<Entry<FlatNode,ConflictGraph>> graphEntrySet=conflictGraphResults.entrySet();
2185 for (Iterator iterator = graphEntrySet.iterator(); iterator.hasNext();) {
2186 Entry<FlatNode, ConflictGraph> graphEntry = (Entry<FlatNode, ConflictGraph>) iterator
2188 FlatNode sese=graphEntry.getKey();
2189 ConflictGraph conflictGraph=graphEntry.getValue();
2190 calculateCovering(conflictGraph);
2194 private void makeConflictGraph() {
2195 Iterator<Descriptor> methItr = ownAnalysis.descriptorsToAnalyze
2197 while (methItr.hasNext()) {
2198 Descriptor d = methItr.next();
2199 FlatMethod fm = state.getMethodFlat(d);
2201 HashSet<MethodContext> mcSet = ownAnalysisForSESEConflicts
2202 .getAllMethodContextSetByDescriptor(fm.getMethod());
2203 Iterator<MethodContext> mcIter = mcSet.iterator();
2205 while (mcIter.hasNext()) {
2206 MethodContext mc = mcIter.next();
2207 OwnershipGraph og=ownAnalysisForSESEConflicts.getOwnvershipGraphByMethodContext(mc);
2209 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
2210 flatNodesToVisit.add(fm);
2212 Set<FlatNode> visited = new HashSet<FlatNode>();
2214 SESESummary summary = new SESESummary(null, fm);
2215 seseSummaryMap.put(fm, summary);
2217 Hashtable<TempDescriptor, TempDescriptor> invarMap=new Hashtable<TempDescriptor,TempDescriptor>();
2219 while (!flatNodesToVisit.isEmpty()) {
2220 Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
2221 FlatNode fn = fnItr.next();
2223 flatNodesToVisit.remove(fn);
2226 // Adding Stall Node of current program statement
2227 ParentChildConflictsMap currentConflictsMap = conflictsResults
2230 Hashtable<TempDescriptor, StallSite> stallMap = currentConflictsMap
2233 Set<Entry<TempDescriptor, StallSite>> entrySet = stallMap
2236 SESESummary seseSummary = seseSummaryMap.get(fn);
2238 ConflictGraph conflictGraph = null;
2239 conflictGraph = conflictGraphResults.get(seseSummary
2242 if (conflictGraph == null) {
2243 conflictGraph = new ConflictGraph(og);
2245 for (Iterator<Entry<TempDescriptor, StallSite>> iterator2 = entrySet
2246 .iterator(); iterator2.hasNext();) {
2247 Entry<TempDescriptor, StallSite> entry = iterator2
2249 TempDescriptor td = entry.getKey();
2250 StallSite stallSite = entry.getValue();
2253 og = ownAnalysisForSESEConflicts
2254 .getOwnvershipGraphByMethodContext(mc);
2255 Set<Set> reachabilitySet = calculateReachabilitySet(og,
2257 conflictGraph.addStallNode(td, fm, stallSite,
2262 if (conflictGraph.id2cn.size() > 0) {
2263 conflictGraphResults.put(seseSummary.getCurrentSESE(),
2267 conflictGraph_nodeAction(mc, fm, fn,invarMap);
2269 for (int i = 0; i < fn.numNext(); i++) {
2270 FlatNode nn = fn.getNext(i);
2271 if (!visited.contains(nn)) {
2272 flatNodesToVisit.add(nn);
2275 } // end of while(flatNodesToVisit)
2277 } // end of while(mcIter)
2281 // decide fine-grain edge or coarse-grain edge among all vertexes by pair-wise comparison
2282 Enumeration<FlatNode> keyEnum1=conflictGraphResults.keys();
2283 while (keyEnum1.hasMoreElements()) {
2284 FlatNode flatNode = (FlatNode) keyEnum1.nextElement();
2285 ConflictGraph conflictGraph=conflictGraphResults.get(flatNode);
2286 conflictGraph.analyzeConflicts();
2287 conflictGraphResults.put(flatNode, conflictGraph);
2292 private Set<Set> calculateReachabilitySet(OwnershipGraph og,
2293 TempDescriptor tempDescriptor) {
2295 Set<Set> reachabilitySet = new HashSet();
2296 LabelNode ln = og.td2ln.get(tempDescriptor);
2298 Iterator<ReferenceEdge> refEdgeIter = ln.iteratorToReferencees();
2299 while (refEdgeIter.hasNext()) {
2300 ReferenceEdge referenceEdge = (ReferenceEdge) refEdgeIter.next();
2302 ReachabilitySet set = referenceEdge.getBeta();
2303 Iterator<TokenTupleSet> ttsIter = set.iterator();
2304 while (ttsIter.hasNext()) {
2305 TokenTupleSet tokenTupleSet = (TokenTupleSet) ttsIter.next();
2307 HashSet<GloballyUniqueTokenTuple> newTokenTupleSet = new HashSet<GloballyUniqueTokenTuple>();
2308 // reachabilitySet.add(tokenTupleSet);
2310 Iterator iter = tokenTupleSet.iterator();
2311 while (iter.hasNext()) {
2312 TokenTuple tt = (TokenTuple) iter.next();
2313 int token = tt.getToken();
2314 String uniqueID = og.id2hrn.get(new Integer(token))
2315 .getGloballyUniqueIdentifier();
2316 GloballyUniqueTokenTuple gtt = new GloballyUniqueTokenTuple(
2318 newTokenTupleSet.add(gtt);
2321 reachabilitySet.add(newTokenTupleSet);
2326 return reachabilitySet;
2329 private ReachabilitySet packupStates(OwnershipGraph og, HeapRegionNode hrn) {
2331 ReachabilitySet betaSet = new ReachabilitySet().makeCanonical();
2333 Iterator<ReferenceEdge> itrEdge = hrn.iteratorToReferencers();
2334 while (itrEdge.hasNext()) {
2335 ReferenceEdge edge = itrEdge.next();
2336 betaSet = betaSet.union(edge.getBeta());
2343 private ReachabilitySet packupStates(OwnershipGraph og, AllocationSite as) {
2345 ReachabilitySet betaSet = new ReachabilitySet().makeCanonical();
2347 HeapRegionNode hrnSummary = og.id2hrn.get(as.getSummary());
2348 if(hrnSummary!=null){
2349 Iterator<ReferenceEdge> itrEdge = hrnSummary.iteratorToReferencers();
2350 while (itrEdge.hasNext()) {
2351 ReferenceEdge edge = itrEdge.next();
2352 betaSet = betaSet.union(edge.getBeta());
2356 // check for other nodes
2357 for (int i = 0; i < as.getAllocationDepth(); ++i) {
2359 HeapRegionNode hrnIthOldest = og.id2hrn.get(as.getIthOldest(i));
2360 // betaSet = new ReachabilitySet().makeCanonical();
2361 // itrEdge = hrnIthOldest.iteratorToReferencees();
2362 Iterator<ReferenceEdge> itrEdge = hrnIthOldest.iteratorToReferencers();
2363 while (itrEdge.hasNext()) {
2364 ReferenceEdge edge = itrEdge.next();
2365 betaSet = betaSet.union(edge.getBeta());
2369 Iterator<TokenTupleSet> ttSetIter = betaSet.iterator();
2370 while (ttSetIter.hasNext()) {
2371 TokenTupleSet tokenTupleSet = (TokenTupleSet) ttSetIter.next();
2372 Iterator iter = tokenTupleSet.iterator();
2373 while (iter.hasNext()) {
2374 TokenTuple tt = (TokenTuple) iter.next();
2375 int token = tt.getToken();
2376 String uniqueID = og.id2hrn.get(new Integer(token))
2377 .getGloballyUniqueIdentifier();
2378 GloballyUniqueTokenTuple gtt = new GloballyUniqueTokenTuple(
2385 private void conflictGraph_nodeAction(MethodContext mc, FlatMethod fm,
2386 FlatNode fn,Hashtable<TempDescriptor, TempDescriptor> invarMap) {
2388 switch (fn.kind()) {
2390 case FKind.FlatSESEEnterNode: {
2392 FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
2393 OwnershipGraph og = ownAnalysisForSESEConflicts
2394 .getOwnvershipGraphByMethodContext(mc);
2396 if (!fsen.getIsCallerSESEplaceholder()) {
2397 Set<TempDescriptor> invar_set = fsen.getInVarSet();
2399 SESESummary seseSummary=seseSummaryMap.get(fsen);
2400 ConflictGraph conflictGraph=null;
2401 conflictGraph=conflictGraphResults.get(seseSummary.getCurrentParent());
2403 if(conflictGraph==null){
2404 conflictGraph = new ConflictGraph(og);
2408 for (Iterator iterator = invar_set.iterator(); iterator
2410 TempDescriptor tempDescriptor = (TempDescriptor) iterator
2413 if(!tempDescriptor.getType().isArray() && tempDescriptor.getType().isImmutable()){
2418 SESEEffectsSet seseEffectsSet = fsen.getSeseEffectsSet();
2419 Set<SESEEffectsKey> readEffectsSet = seseEffectsSet
2420 .getReadingSet(tempDescriptor);
2422 if (readEffectsSet != null) {
2423 for (Iterator iterator2 = readEffectsSet.iterator(); iterator2
2425 SESEEffectsKey seseEffectsKey = (SESEEffectsKey) iterator2
2427 String uniqueID = seseEffectsKey.getHRNUniqueId();
2428 HeapRegionNode node = og.gid2hrn.get(uniqueID);
2429 if(node.isParameter()){
2430 seseEffectsKey.setRSet(packupStates(og,node));
2432 AllocationSite as = node.getAllocationSite();
2433 seseEffectsKey.setRSet(packupStates(og,as));
2438 if (readEffectsSet != null) {
2439 for (Iterator iterator2 = readEffectsSet.iterator(); iterator2
2441 SESEEffectsKey seseEffectsKey = (SESEEffectsKey) iterator2
2445 Set<SESEEffectsKey> writeEffectsSet = seseEffectsSet
2446 .getWritingSet(tempDescriptor);
2448 if (writeEffectsSet != null) {
2449 for (Iterator iterator2 = writeEffectsSet.iterator(); iterator2
2451 SESEEffectsKey seseEffectsKey = (SESEEffectsKey) iterator2
2453 String uniqueID = seseEffectsKey.getHRNUniqueId();
2454 HeapRegionNode node = og.gid2hrn.get(uniqueID);
2456 if(node.isParameter()){
2457 seseEffectsKey.setRSet(packupStates(og,node));
2459 AllocationSite as = node.getAllocationSite();
2460 seseEffectsKey.setRSet(packupStates(og,as));
2465 Set<SESEEffectsKey> strongUpdateSet = seseEffectsSet.getStrongUpdateSet(tempDescriptor);
2467 Set<Set> reachabilitySet = calculateReachabilitySet(og,
2470 // add new live-in node
2472 OwnershipGraph lastOG = ownAnalysis
2473 .getOwnvershipGraphByMethodContext(mc);
2474 LabelNode ln = lastOG.td2ln.get(tempDescriptor);
2477 Set<HeapRegionNode> hrnSet = new HashSet<HeapRegionNode>();
2478 Iterator<ReferenceEdge> refIter = ln
2479 .iteratorToReferencees();
2480 while (refIter.hasNext()) {
2481 ReferenceEdge referenceEdge = (ReferenceEdge) refIter
2484 SESEEffectsSet seseEffects=fsen.getSeseEffectsSet();
2485 int taintIdentifier=fsen.getSeseEffectsSet().getTaint(referenceEdge);
2486 int invarIdx=fsen.getSeseEffectsSet().getInVarIdx(tempDescriptor);
2487 int inVarMask=(int) Math.pow(2,invarIdx);
2488 if((inVarMask&taintIdentifier)>0){
2489 // find tainted edge, add heap root to live-in node
2490 hrnSet.add(referenceEdge.getDst());
2495 conflictGraph.addLiveInNode(tempDescriptor, hrnSet, fsen,
2496 readEffectsSet, writeEffectsSet, strongUpdateSet, reachabilitySet);
2500 if(conflictGraph.id2cn.size()>0){
2501 conflictGraphResults.put(seseSummary.getCurrentParent(),conflictGraph);
2514 private void seseConflictsForward(JavaCallGraph javaCallGraph) {
2516 Set methodCallSet = javaCallGraph.getAllMethods(typeUtil.getMain());
2518 // topologically sort java call chain so that leaf calls are ordered
2520 LinkedList<MethodDescriptor> sortedMethodCalls = topologicalSort(
2521 methodCallSet, javaCallGraph);
2523 for (Iterator iterator = sortedMethodCalls.iterator(); iterator
2526 MethodDescriptor md = (MethodDescriptor) iterator.next();
2528 FlatMethod fm = state.getMethodFlat(md);
2530 HashSet<MethodContext> mcSet = ownAnalysis
2531 .getAllMethodContextSetByDescriptor(md);
2532 Iterator<MethodContext> mcIter = mcSet.iterator();
2534 currentMethodSummary = new MethodSummary();
2535 preeffectsSet = new HashSet<PreEffectsKey>();
2537 // iterates over all possible method context
2538 while (mcIter.hasNext()) {
2539 MethodContext mc = mcIter.next();
2541 LinkedList<FlatNode> flatNodesToVisit=new LinkedList<FlatNode>();
2542 flatNodesToVisit.add(fm);
2544 SESESummary summary = new SESESummary(null, fm);
2545 seseSummaryMap.put(fm, summary);
2547 Hashtable<TempDescriptor, TempDescriptor> invarMap=new Hashtable<TempDescriptor,TempDescriptor>();
2549 while (!flatNodesToVisit.isEmpty()) {
2550 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
2551 flatNodesToVisit.remove(fn);
2552 ParentChildConflictsMap prevResult = conflictsResults
2555 // merge sets from control flow
2556 Boolean prevSESE=null;
2557 ParentChildConflictsMap currentConflictsMap = new ParentChildConflictsMap();
2558 for (int i = 0; i < fn.numPrev(); i++) {
2559 FlatNode prevFlatNode = fn.getPrev(i);
2560 ParentChildConflictsMap incoming = conflictsResults
2562 if (incoming != null) {
2563 currentConflictsMap.merge(incoming);
2566 if(prevFlatNode instanceof FlatCondBranch){
2567 prevSESE=isAfterChildSESEIndicatorMap.get(prevFlatNode);
2570 SESESummary currentSummary = seseSummaryMap.get(fn);
2571 //if (currentSummary == null) {
2572 if(!(fn instanceof FlatMethod)){
2573 FlatNode current = null;
2574 FlatNode currentParent = null;
2575 // calculate sese summary info from previous flat nodes
2577 for (int i = 0; i < fn.numPrev(); i++) {
2578 FlatNode prevFlatNode = fn.getPrev(i);
2579 SESESummary prevSummary = seseSummaryMap
2581 if (prevSummary != null) {
2582 if (prevFlatNode instanceof FlatSESEExitNode
2583 && !((FlatSESEExitNode) prevFlatNode)
2585 .getIsCallerSESEplaceholder()) {
2586 current = prevSummary.getCurrentParent();
2587 SESESummary temp = seseSummaryMap
2589 currentParent = temp.getCurrentParent();
2591 current = prevSummary.getCurrentSESE();
2592 currentParent = prevSummary
2593 .getCurrentParent();
2600 currentSummary = new SESESummary(currentParent, current);
2601 seseSummaryMap.put(fn, currentSummary);
2605 if(fn instanceof FlatSESEEnterNode){
2606 isAfterChildSESEIndicatorMap.put(currentSummary.getCurrentSESE(), currentConflictsMap.isAfterSESE());
2608 isAfterChildSESEIndicatorMap.put(currentSummary.getCurrentSESE(), prevSESE);
2612 Boolean b=isAfterChildSESEIndicatorMap.get(currentSummary.getCurrentSESE());;
2614 currentConflictsMap.setIsAfterSESE(false);
2616 currentConflictsMap.setIsAfterSESE(b.booleanValue());
2619 FlatNode tempP=currentSummary.getCurrentParent();
2620 FlatNode tempS=currentSummary.getCurrentSESE();
2622 conflicts_nodeAction(mc, fn, callGraph, preeffectsSet,
2623 currentConflictsMap, currentSummary,invarMap);
2626 // if we have a new result, schedule forward nodes for
2628 if (!currentConflictsMap.equals(prevResult)) {
2629 seseSummaryMap.put(fn, currentSummary);
2630 conflictsResults.put(fn, currentConflictsMap);
2631 for (int i = 0; i < fn.numNext(); i++) {
2632 FlatNode nn = fn.getNext(i);
2633 flatNodesToVisit.addFirst(nn);
2646 private void conflicts_nodeAction(MethodContext mc, FlatNode fn,
2647 CallGraph callGraph, HashSet<PreEffectsKey> preeffectsSet,
2648 ParentChildConflictsMap currentConflictsMap,
2649 SESESummary currentSummary,
2650 Hashtable<TempDescriptor, TempDescriptor> invarMap) {
2652 OwnershipGraph og = ownAnalysis.getOwnvershipGraphByMethodContext(mc);
2654 currentConflictsMap.clearStallMap();
2656 switch (fn.kind()) {
2658 case FKind.FlatSESEEnterNode: {
2660 FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
2662 if (!fsen.getIsCallerSESEplaceholder()) {
2663 FlatNode parentNode = currentSummary.getCurrentSESE();
2664 currentSummary.setCurrentParent(parentNode);
2665 currentSummary.setCurrentSESE(fsen);
2666 // seseSummaryMap.put(fsen, currentSummary);
2669 if (!fsen.getIsCallerSESEplaceholder()) {
2670 currentMethodSummary.increaseChildSESECount();
2672 if (currentMethodSummary.getChildSESECount() == 1) {
2673 // need to store pre-effects
2674 currentMethodSummary.getEffectsSet().addAll(preeffectsSet);
2675 for (Iterator iterator = currentMethodSummary.getEffectsSet()
2676 .iterator(); iterator.hasNext();) {
2677 PreEffectsKey preEffectsKey = (PreEffectsKey) iterator
2680 preeffectsSet.clear();
2685 case FKind.FlatSESEExitNode: {
2687 FlatSESEExitNode fsen = (FlatSESEExitNode) fn;
2689 if (!fsen.getFlatEnter().getIsCallerSESEplaceholder()) {
2690 // all object variables are inaccessible.
2691 isAfterChildSESEIndicatorMap.put(currentSummary
2692 .getCurrentParent(), new Boolean(true));
2694 // currentConflictsMap = new ParentChildConflictsMap();
2695 currentConflictsMap.clear();
2700 case FKind.FlatCondBranch: {
2701 boolean isAfterChildSESE = false;
2702 FlatNode current = currentSummary.getCurrentSESE();
2703 Boolean isAfter = isAfterChildSESEIndicatorMap.get(current);
2704 if (isAfter != null && isAfter.booleanValue()) {
2705 isAfterChildSESE = true;
2707 isAfterChildSESEIndicatorMap.put(fn, new Boolean(isAfterChildSESE));
2711 case FKind.FlatNew: {
2713 FlatNew fnew = (FlatNew) fn;
2715 boolean isAfterChildSESE = false;
2716 FlatNode current = currentSummary.getCurrentSESE();
2717 Boolean isAfter = isAfterChildSESEIndicatorMap.get(current);
2718 if (isAfter != null && isAfter.booleanValue()) {
2719 isAfterChildSESE = true;
2722 if (isAfterChildSESE) {
2723 TempDescriptor dst = fnew.getDst();
2724 currentConflictsMap.addAccessibleVar(dst);
2730 case FKind.FlatElementNode:{
2733 FlatElementNode fen = (FlatElementNode) fn;
2734 TempDescriptor src=fen.getSrc();
2736 boolean isAfterChildSESE = false;
2737 FlatNode current = currentSummary.getCurrentSESE();
2738 Boolean isAfter = isAfterChildSESEIndicatorMap.get(current);
2739 if (isAfter != null && isAfter.booleanValue()) {
2740 isAfterChildSESE = true;
2743 if(isAfterChildSESE){
2745 if (!currentConflictsMap.isAccessible(src)) {
2746 if(invarMap.containsKey(src)){
2747 currentConflictsMap.addStallSite(src, new HashSet<HeapRegionNode>(),
2748 new StallTag(fn),invarMap.get(src));
2750 currentConflictsMap.addStallSite(src, new HashSet<HeapRegionNode>(),
2751 new StallTag(fn),null);
2754 currentConflictsMap.addAccessibleVar(src);
2756 // contribute read effect on source's stall site
2757 currentConflictsMap.contributeEffect(src, "", "",
2758 StallSite.READ_EFFECT);
2762 if (currentMethodSummary.getChildSESECount() == 0) {
2763 // analyze preeffects
2764 preEffectAnalysis(og, src, null, PreEffectsKey.READ_EFFECT);
2770 case FKind.FlatFieldNode: {
2772 FlatFieldNode ffn = (FlatFieldNode) fn;
2773 TempDescriptor dst = ffn.getDst();
2774 TempDescriptor src = ffn.getSrc();
2775 FieldDescriptor field = ffn.getField();
2777 boolean isAfterChildSESE = false;
2778 FlatNode current = currentSummary.getCurrentSESE();
2779 Boolean isAfter = isAfterChildSESEIndicatorMap.get(current);
2780 if (isAfter != null && isAfter.booleanValue()) {
2781 isAfterChildSESE = true;
2784 if (isAfterChildSESE) {
2786 if (!currentConflictsMap.isAccessible(src)) {
2787 HashSet<HeapRegionNode> refHRN = getReferenceHeapIDSet(
2789 currentConflictsMap.addStallSite(src, refHRN,
2790 new StallTag(fn),null);
2792 // flag stall site for disjoint analysis
2793 for (Iterator iterator2 = refHRN.iterator(); iterator2
2795 HeapRegionNode hrn = (HeapRegionNode) iterator2
2797 if (hrn.isParameter()) {
2798 // if stall site is paramter heap region, need
2799 // to decompose into caller's
2800 HashSet<HeapRegionNode> visitedHRN = new HashSet<HeapRegionNode>();
2801 visitedHRN.add(hrn);
2802 setupRelatedAllocSiteAnalysis(og, mc, hrn,
2805 // System.out.println("FLAGGED "+mc+":"+ffn);
2806 flagAllocationSite(mc, hrn.getAllocationSite());
2811 currentConflictsMap.addAccessibleVar(src);
2813 // contribute read effect on source's stall site
2814 currentConflictsMap.contributeEffect(src, field
2815 .getType().getSafeSymbol(), field.getSymbol(),
2816 StallSite.READ_EFFECT);
2818 if(field.getType().isImmutable()){
2819 currentConflictsMap.addAccessibleVar(dst);
2824 if (currentMethodSummary.getChildSESECount() == 0) {
2825 // analyze preeffects
2826 preEffectAnalysis(og, src, field, PreEffectsKey.READ_EFFECT);
2832 case FKind.FlatSetElementNode:{
2834 FlatSetElementNode fsen=(FlatSetElementNode)fn;
2835 TempDescriptor dst = fsen.getDst();
2836 TempDescriptor src = fsen.getSrc();
2838 boolean isAfterChildSESE = false;
2839 FlatNode current = currentSummary.getCurrentSESE();
2840 Boolean isAfter = isAfterChildSESEIndicatorMap.get(current);
2841 if (isAfter != null && isAfter.booleanValue()) {
2842 isAfterChildSESE = true;
2845 if (isAfterChildSESE) {
2847 if (!currentConflictsMap.isAccessible(src)) {
2848 HashSet<HeapRegionNode> refHRN = getReferenceHeapIDSet(og,
2850 currentConflictsMap.addStallSite(src, refHRN , new StallTag(
2853 currentConflictsMap.addAccessibleVar(src);
2855 if (!currentConflictsMap.isAccessible(dst)) {
2856 if(invarMap.containsKey(dst)){
2857 currentConflictsMap.addStallSite(dst, new HashSet<HeapRegionNode>(),
2858 new StallTag(fn),invarMap.get(dst));
2860 currentConflictsMap.addStallSite(dst, new HashSet<HeapRegionNode>(),
2861 new StallTag(fn),null);
2864 currentConflictsMap.addAccessibleVar(dst);
2865 // contribute write effect on destination's stall site
2866 currentConflictsMap.contributeEffect(dst, "","",
2867 StallSite.WRITE_EFFECT);
2871 if (currentMethodSummary.getChildSESECount() == 0) {
2872 // analyze preeffects
2873 preEffectAnalysis(og, dst, null, PreEffectsKey.WRITE_EFFECT);
2878 case FKind.FlatSetFieldNode: {
2880 FlatSetFieldNode fsen = (FlatSetFieldNode) fn;
2881 TempDescriptor dst = fsen.getDst();
2882 FieldDescriptor field = fsen.getField();
2883 TempDescriptor src = fsen.getSrc();
2885 boolean isAfterChildSESE = false;
2886 FlatNode current = currentSummary.getCurrentSESE();
2887 Boolean isAfter = isAfterChildSESEIndicatorMap.get(current);
2888 if (isAfter != null && isAfter.booleanValue()) {
2889 isAfterChildSESE = true;
2892 if (isAfterChildSESE) {
2894 if (!currentConflictsMap.isAccessible(src)) {
2895 HashSet<HeapRegionNode> refHRN = getReferenceHeapIDSet(og,
2897 currentConflictsMap.addStallSite(src, refHRN, new StallTag(
2900 // flag stall site for disjoint analysis
2901 for (Iterator iterator2 = refHRN.iterator(); iterator2
2903 HeapRegionNode hrn = (HeapRegionNode) iterator2.next();
2905 if (hrn.isParameter()) {
2906 // if stall site is paramter heap region, need
2907 // to decompose into caller's
2908 HashSet<HeapRegionNode> visitedHRN = new HashSet<HeapRegionNode>();
2909 visitedHRN.add(hrn);
2910 setupRelatedAllocSiteAnalysis(og, mc, hrn,
2913 flagAllocationSite(mc, hrn.getAllocationSite());
2919 currentConflictsMap.addAccessibleVar(src);
2922 if (!currentConflictsMap.isAccessible(dst)) {
2923 HashSet<HeapRegionNode> refHRN = getReferenceHeapIDSet(
2925 currentConflictsMap.addStallSite(dst, refHRN,
2926 new StallTag(fn),null);
2928 // flag stall site for disjoint analysis
2929 for (Iterator iterator2 = refHRN.iterator(); iterator2
2931 HeapRegionNode hrn = (HeapRegionNode) iterator2
2933 if (hrn.isParameter()) {
2934 // if stall site is paramter heap region, need
2935 // to decompose into caller's
2936 HashSet<HeapRegionNode> visitedHRN = new HashSet<HeapRegionNode>();
2937 visitedHRN.add(hrn);
2938 setupRelatedAllocSiteAnalysis(og, mc, hrn,
2941 flagAllocationSite(mc, hrn.getAllocationSite());
2946 currentConflictsMap.addAccessibleVar(dst);
2947 // contribute write effect on destination's stall site
2948 currentConflictsMap.contributeEffect(dst, field
2949 .getType().getSafeSymbol(), field.getSymbol(),
2950 StallSite.WRITE_EFFECT);
2953 // TODO need to create edge mapping for newly created edge
2954 HashSet<ReferenceEdge> edges = getRefEdgeSetReferenceToSameHRN(
2957 StallSite ss = currentConflictsMap.getStallMap().get(dst);
2959 for (Iterator iterator = edges.iterator(); iterator
2961 ReferenceEdge referenceEdge = (ReferenceEdge) iterator
2963 if (!(referenceEdge.getSrc() instanceof LabelNode)) {
2964 currentConflictsMap.addStallEdge(referenceEdge,
2971 if (currentMethodSummary.getChildSESECount() == 0) {
2972 // analyze preeffects
2973 preEffectAnalysis(og, dst, field, PreEffectsKey.WRITE_EFFECT);
2979 case FKind.FlatOpNode: {
2981 FlatOpNode fon = (FlatOpNode) fn;
2983 boolean isAfterChildSESE = false;
2984 FlatNode current = currentSummary.getCurrentSESE();
2985 Boolean isAfter = isAfterChildSESEIndicatorMap.get(current);
2988 if( fon.getOp().getOp() ==Operation.ASSIGN){
2989 invarMap.put(fon.getDest(), fon.getLeft());
2992 if (isAfter != null && isAfter.booleanValue()) {
2993 isAfterChildSESE = true;
2996 if (isAfterChildSESE) {
2998 // destination variable gets the status of source.
3000 if (fon.getOp().getOp() == Operation.ASSIGN) {
3002 TempDescriptor dst = fon.getDest();
3003 TempDescriptor src = fon.getLeft();
3005 Integer sourceStatus = currentConflictsMap
3006 .getAccessibleMap().get(src);
3007 if (sourceStatus == null) {
3008 sourceStatus = ParentChildConflictsMap.INACCESSIBLE;
3011 HashSet<TempDescriptor> dstTempSet = getTempDescSetReferenceToSameHRN(
3014 for (Iterator<TempDescriptor> iterator = dstTempSet
3015 .iterator(); iterator.hasNext();) {
3016 TempDescriptor possibleDst = iterator.next();
3019 .equals(ParentChildConflictsMap.ACCESSIBLE)) {
3020 currentConflictsMap.addAccessibleVar(possibleDst);
3022 currentConflictsMap.addInaccessibleVar(possibleDst);
3033 case FKind.FlatCall: {
3035 FlatCall fc = (FlatCall) fn;
3037 boolean isAfterChildSESE = false;
3038 FlatNode current = currentSummary.getCurrentSESE();
3039 Boolean isAfter = isAfterChildSESEIndicatorMap.get(current);
3040 if (isAfter != null && isAfter.booleanValue()) {
3041 isAfterChildSESE = true;
3045 if (!fc.getMethod().isStatic()) {
3049 FlatMethod calleeFM = state.getMethodFlat(fc.getMethod());
3051 // retrieve callee's method summary
3052 MethodSummary calleeMethodSummary = methodSummaryResults
3055 if (calleeMethodSummary != null
3056 && calleeMethodSummary.getChildSESECount() > 0) {
3058 // when parameter variable is accessible,
3059 // use callee's preeffects to figure out about how it affects
3060 // caller's stall site
3062 for (int i = 0; i < fc.numArgs(); i++) {
3063 TempDescriptor paramTemp = fc.getArg(i);
3065 if (isAfterChildSESE) {
3066 if (currentConflictsMap.isAccessible(paramTemp)
3067 && currentConflictsMap.hasStallSite(paramTemp)) {
3068 // preeffect contribute its effect to caller's stall
3072 if (!fc.getMethod().isStatic()) {
3076 HashSet<PreEffectsKey> preeffectSet = calleeMethodSummary
3077 .getEffectsSetByParamIdx(i + offset);
3079 for (Iterator iterator = preeffectSet.iterator(); iterator
3081 PreEffectsKey preEffectsKey = (PreEffectsKey) iterator
3083 currentConflictsMap.contributeEffect(paramTemp,
3084 preEffectsKey.getType(), preEffectsKey
3085 .getField(), preEffectsKey
3090 // in other cases, child SESE has not been discovered,
3091 // assumes that all variables are accessible
3095 // If callee has at least one child sese, all parent object
3096 // is going to be inaccessible.
3097 // currentConflictsMap = new ParentChildConflictsMap();
3098 currentConflictsMap.makeAllInaccessible();
3099 isAfterChildSESEIndicatorMap.put(currentSummary
3100 .getCurrentSESE(), new Boolean(true));
3102 TempDescriptor returnTemp = fc.getReturnTemp();
3104 if (calleeMethodSummary.getReturnValueAccessibility().equals(
3105 MethodSummary.ACCESSIBLE)) {
3106 // when return value is accessible, associate with its
3108 currentConflictsMap.addAccessibleVar(returnTemp);
3110 StallSite returnStallSite = calleeMethodSummary
3111 .getReturnStallSite().copy();
3112 // handling parameter regions
3113 HashSet<Integer> stallParamIdx = returnStallSite
3114 .getCallerParamIdxSet();
3115 for (Iterator iterator = stallParamIdx.iterator(); iterator
3117 Integer idx = (Integer) iterator.next();
3119 int paramIdx = idx.intValue() - base;
3120 TempDescriptor paramTD = fc.getArg(paramIdx);
3122 // TODO: resolve callee's parameter heap regions by
3123 // following call chain
3127 // flag stall site's allocation sites for disjointness
3129 HashSet<HeapRegionNode> hrnSet = returnStallSite
3131 for (Iterator iterator = hrnSet.iterator(); iterator
3133 HeapRegionNode hrn = (HeapRegionNode) iterator.next();
3134 if (hrn.isParameter()) {
3135 // if stall site is paramter heap region, need to
3136 // decompose into caller's
3137 HashSet<HeapRegionNode> visitedHRN = new HashSet<HeapRegionNode>();
3138 visitedHRN.add(hrn);
3139 setupRelatedAllocSiteAnalysis(og, mc, hrn,
3142 flagAllocationSite(mc, hrn.getAllocationSite());
3146 currentConflictsMap.addStallSite(returnTemp,
3149 } else if (calleeMethodSummary.getReturnValueAccessibility()
3150 .equals(MethodSummary.INACCESSIBLE)) {
3151 // when return value is inaccessible
3152 currentConflictsMap.addInaccessibleVar(returnTemp);
3155 // TODO: need to handle edge mappings from callee
3156 Set<Integer> stallParamIdx = calleeMethodSummary
3157 .getStallParamIdxSet();
3158 for (Iterator iterator = stallParamIdx.iterator(); iterator
3160 Integer paramIdx = (Integer) iterator.next();
3161 HashSet<StallTag> stallTagSet = calleeMethodSummary
3162 .getStallTagByParamIdx(paramIdx);
3164 int argIdx = paramIdx.intValue() - base;
3165 TempDescriptor argTD = fc.getArg(argIdx);
3167 putStallTagOnReferenceEdges(og, argTD, stallTagSet,
3168 currentConflictsMap);
3176 * do we need this case? case FKind.FlatLiteralNode: {
3178 * if (currentConflictsMap.isAfterChildSESE()) { FlatLiteralNode fln =
3179 * (FlatLiteralNode) fn; TempDescriptor dst = fln.getDst();
3180 * currentConflictsMap.addAccessibleVar(dst); }
3185 case FKind.FlatReturnNode: {
3187 FlatReturnNode frn = (FlatReturnNode) fn;
3188 TempDescriptor returnTD = frn.getReturnTemp();
3190 boolean isAfterChildSESE = false;
3191 FlatNode current = currentSummary.getCurrentSESE();
3192 Boolean isAfter = isAfterChildSESEIndicatorMap.get(current);
3193 if (isAfter != null && isAfter.booleanValue()) {
3194 isAfterChildSESE = true;
3197 if (returnTD != null) {
3198 if (!isAfterChildSESE) {
3199 // in this case, all variables are accessible. There are no
3202 if (currentConflictsMap.isAccessible(returnTD)) {
3204 currentMethodSummary
3205 .setReturnValueAccessibility(MethodSummary.ACCESSIBLE);
3206 StallSite returnStallSite = currentConflictsMap
3207 .getStallMap().get(returnTD);
3209 HashSet<HeapRegionNode> stallSiteHRNSet = returnStallSite
3211 for (Iterator iterator = stallSiteHRNSet.iterator(); iterator
3213 HeapRegionNode stallSiteHRN = (HeapRegionNode) iterator
3215 Set<Integer> paramSet = og.idPrimary2paramIndexSet
3216 .get(stallSiteHRN.getID());
3217 returnStallSite.addCallerParamIdxSet(paramSet);
3218 paramSet = og.idSecondary2paramIndexSet
3219 .get(stallSiteHRN.getID());
3220 returnStallSite.addCallerParamIdxSet(paramSet);
3223 currentMethodSummary
3224 .setReturnStallSite(returnStallSite);
3227 currentMethodSummary
3228 .setReturnValueAccessibility(MethodSummary.INACCESSIBLE);
3235 case FKind.FlatExit: {
3237 // store method summary when it has at least one child SESE
3238 if (currentMethodSummary.getChildSESECount() > 0) {
3239 // current flat method
3240 FlatMethod fm = state.getMethodFlat(mc.getDescriptor());
3241 Set<TempDescriptor> stallTempSet = currentConflictsMap
3242 .getStallMap().keySet();
3243 for (Iterator iterator = stallTempSet.iterator(); iterator
3245 TempDescriptor stallTD = (TempDescriptor) iterator.next();
3246 StallSite stallSite = currentConflictsMap.getStallMap()
3249 HashSet<HeapRegionNode> stallSiteHRNSet = stallSite
3251 for (Iterator iterator2 = stallSiteHRNSet.iterator(); iterator2
3253 HeapRegionNode stallSiteHRN = (HeapRegionNode) iterator2
3256 if (stallSiteHRN.isParameter()) {
3258 Set<Integer> paramSet = og.idPrimary2paramIndexSet
3259 .get(stallSiteHRN.getID());
3260 currentMethodSummary.addStallParamIdxSet(paramSet,
3261 stallSite.getStallTagSet());
3263 paramSet = og.idSecondary2paramIndexSet
3264 .get(stallSiteHRN.getID());
3265 currentMethodSummary.addStallParamIdxSet(paramSet,
3266 stallSite.getStallTagSet());
3272 methodSummaryResults.put(fm, currentMethodSummary);
3279 // seseSummaryMap.put(fn, currentSummary);
3283 private void putStallTagOnReferenceEdges(OwnershipGraph og,
3284 TempDescriptor argTD, HashSet stallTagSet,
3285 ParentChildConflictsMap currentConflictsMap) {
3287 LabelNode ln=og.td2ln.get(argTD);
3290 Iterator<ReferenceEdge> refrenceeIter=ln.iteratorToReferencees();
3291 while (refrenceeIter.hasNext()) {
3292 ReferenceEdge refEdge = (ReferenceEdge) refrenceeIter.next();
3293 HeapRegionNode stallHRN=refEdge.getDst();
3295 Iterator<ReferenceEdge> referencerIter=stallHRN.iteratorToReferencers();
3296 while (referencerIter.hasNext()) {
3297 ReferenceEdge referencer = (ReferenceEdge) referencerIter
3299 for (Iterator iterator = stallTagSet.iterator(); iterator
3301 StallTag stallTag = (StallTag) iterator.next();
3302 currentConflictsMap.addStallEdge(referencer, stallTag);
3309 private void preEffectAnalysis(OwnershipGraph og, TempDescriptor td,
3310 FieldDescriptor field, Integer effectType) {
3312 // analyze preeffects
3313 HashSet<HeapRegionNode> hrnSet = getReferenceHeapIDSet(og, td);
3314 for (Iterator iterator = hrnSet.iterator(); iterator.hasNext();) {
3315 HeapRegionNode hrn = (HeapRegionNode) iterator.next();
3316 if (hrn.isParameter()) {
3317 // effects on param heap region
3319 Set<Integer> paramSet = og.idPrimary2paramIndexSet.get(hrn
3322 if (paramSet != null) {
3323 Iterator<Integer> paramIter = paramSet.iterator();
3324 while (paramIter.hasNext()) {
3325 Integer paramID = paramIter.next();
3326 PreEffectsKey effectKey=null;
3328 effectKey = new PreEffectsKey(paramID,
3329 field.getSymbol(), field.getType()
3330 .getSafeSymbol(), effectType);
3332 effectKey = new PreEffectsKey(paramID,
3333 "", "", effectType);
3335 preeffectsSet.add(effectKey);
3339 // check weather this heap region is parameter
3342 paramSet = og.idSecondary2paramIndexSet.get(hrn.getID());
3343 if (paramSet != null) {
3344 Iterator<Integer> paramIter = paramSet.iterator();
3346 while (paramIter.hasNext()) {
3347 Integer paramID = paramIter.next();
3348 PreEffectsKey effectKey=null;
3350 effectKey = new PreEffectsKey(paramID,
3351 field.getSymbol(), field.getType()
3352 .getSafeSymbol(), effectType);
3354 effectKey = new PreEffectsKey(paramID,
3355 "", "", effectType);
3357 preeffectsSet.add(effectKey);
3365 private void codePlansForward( FlatMethod fm ) {
3367 // start from flat method top, visit every node in
3368 // method exactly once
3369 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
3370 flatNodesToVisit.add( fm );
3372 Set<FlatNode> visited = new HashSet<FlatNode>();
3374 while( !flatNodesToVisit.isEmpty() ) {
3375 Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
3376 FlatNode fn = fnItr.next();
3378 flatNodesToVisit.remove( fn );
3381 Stack<FlatSESEEnterNode> seseStack = seseStacks.get( fn );
3382 assert seseStack != null;
3384 // use incoming results as "dot statement" or just
3385 // before the current statement
3386 VarSrcTokTable dotSTtable = new VarSrcTokTable();
3387 for( int i = 0; i < fn.numPrev(); i++ ) {
3388 FlatNode nn = fn.getPrev( i );
3389 dotSTtable.merge( variableResults.get( nn ) );
3392 // find dt-st notAvailableSet also
3393 Set<TempDescriptor> dotSTnotAvailSet = new HashSet<TempDescriptor>();
3394 for( int i = 0; i < fn.numPrev(); i++ ) {
3395 FlatNode nn = fn.getPrev( i );
3396 Set<TempDescriptor> notAvailIn = notAvailableResults.get( nn );
3397 if( notAvailIn != null ) {
3398 dotSTnotAvailSet.addAll( notAvailIn );
3402 Set<TempDescriptor> dotSTlive = livenessRootView.get( fn );
3404 if( !seseStack.empty() ) {
3405 codePlans_nodeActions( fn,
3413 for( int i = 0; i < fn.numNext(); i++ ) {
3414 FlatNode nn = fn.getNext( i );
3416 if( !visited.contains( nn ) ) {
3417 flatNodesToVisit.add( nn );
3423 private void codePlans_nodeActions( FlatNode fn,
3424 Set<TempDescriptor> liveSetIn,
3425 VarSrcTokTable vstTableIn,
3426 Set<TempDescriptor> notAvailSetIn,
3427 FlatSESEEnterNode currentSESE ) {
3429 CodePlan plan = new CodePlan( currentSESE);
3431 switch( fn.kind() ) {
3433 case FKind.FlatSESEEnterNode: {
3434 FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
3435 assert fsen.equals( currentSESE );
3437 // track the source types of the in-var set so generated
3438 // code at this SESE issue can compute the number of
3439 // dependencies properly
3440 Iterator<TempDescriptor> inVarItr = fsen.getInVarSet().iterator();
3441 while( inVarItr.hasNext() ) {
3442 TempDescriptor inVar = inVarItr.next();
3444 // when we get to an SESE enter node we change the
3445 // currentSESE variable of this analysis to the
3446 // child that is declared by the enter node, so
3447 // in order to classify in-vars correctly, pass
3448 // the parent SESE in--at other FlatNode types just
3449 // use the currentSESE
3450 VSTWrapper vstIfStatic = new VSTWrapper();
3452 vstTableIn.getRefVarSrcType( inVar,
3457 // the current SESE needs a local space to track the dynamic
3458 // variable and the child needs space in its SESE record
3459 if( srcType.equals( VarSrcTokTable.SrcType_DYNAMIC ) ) {
3460 fsen.addDynamicInVar( inVar );
3461 fsen.getParent().addDynamicVar( inVar );
3463 } else if( srcType.equals( VarSrcTokTable.SrcType_STATIC ) ) {
3464 fsen.addStaticInVar( inVar );
3465 VariableSourceToken vst = vstIfStatic.vst;
3466 fsen.putStaticInVar2src( inVar, vst );
3467 fsen.addStaticInVarSrc( new SESEandAgePair( vst.getSESE(),
3472 assert srcType.equals( VarSrcTokTable.SrcType_READY );
3473 fsen.addReadyInVar( inVar );
3479 case FKind.FlatSESEExitNode: {
3480 FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
3483 case FKind.FlatOpNode: {
3484 FlatOpNode fon = (FlatOpNode) fn;
3486 if( fon.getOp().getOp() == Operation.ASSIGN ) {
3487 TempDescriptor lhs = fon.getDest();
3488 TempDescriptor rhs = fon.getLeft();
3490 // if this is an op node, don't stall, copy
3491 // source and delay until we need to use value
3493 // ask whether lhs and rhs sources are dynamic, static, etc.
3494 VSTWrapper vstIfStatic = new VSTWrapper();
3496 = vstTableIn.getRefVarSrcType( lhs,
3501 = vstTableIn.getRefVarSrcType( rhs,
3506 if( rhsSrcType.equals( VarSrcTokTable.SrcType_DYNAMIC ) ) {
3507 // if rhs is dynamic going in, lhs will definitely be dynamic
3508 // going out of this node, so track that here
3509 plan.addDynAssign( lhs, rhs );
3510 currentSESE.addDynamicVar( lhs );
3511 currentSESE.addDynamicVar( rhs );
3513 } else if( lhsSrcType.equals( VarSrcTokTable.SrcType_DYNAMIC ) ) {
3514 // otherwise, if the lhs is dynamic, but the rhs is not, we
3515 // need to update the variable's dynamic source as "current SESE"
3516 plan.addDynAssign( lhs );
3519 // only break if this is an ASSIGN op node,
3520 // otherwise fall through to default case
3525 // note that FlatOpNode's that aren't ASSIGN
3526 // fall through to this default case
3529 // a node with no live set has nothing to stall for
3530 if( liveSetIn == null ) {
3534 TempDescriptor[] readarray = fn.readsTemps();
3535 for( int i = 0; i < readarray.length; i++ ) {
3536 TempDescriptor readtmp = readarray[i];
3538 // ignore temps that are definitely available
3539 // when considering to stall on it
3540 if( !notAvailSetIn.contains( readtmp ) ) {
3544 // check the source type of this variable
3545 VSTWrapper vstIfStatic = new VSTWrapper();
3547 = vstTableIn.getRefVarSrcType( readtmp,
3552 if( srcType.equals( VarSrcTokTable.SrcType_DYNAMIC ) ) {
3553 // 1) It is not clear statically where this variable will
3554 // come from, so dynamically we must keep track
3555 // along various control paths, and therefore when we stall,
3556 // just stall for the exact thing we need and move on
3557 plan.addDynamicStall( readtmp );
3558 currentSESE.addDynamicVar( readtmp );
3560 } else if( srcType.equals( VarSrcTokTable.SrcType_STATIC ) ) {
3561 // 2) Single token/age pair: Stall for token/age pair, and copy
3562 // all live variables with same token/age pair at the same
3563 // time. This is the same stuff that the notavaialable analysis
3564 // marks as now available.
3565 VariableSourceToken vst = vstIfStatic.vst;
3567 Iterator<VariableSourceToken> availItr =
3568 vstTableIn.get( vst.getSESE(), vst.getAge() ).iterator();
3570 while( availItr.hasNext() ) {
3571 VariableSourceToken vstAlsoAvail = availItr.next();
3573 // only grab additional stuff that is live
3574 Set<TempDescriptor> copySet = new HashSet<TempDescriptor>();
3576 Iterator<TempDescriptor> refVarItr = vstAlsoAvail.getRefVars().iterator();
3577 while( refVarItr.hasNext() ) {
3578 TempDescriptor refVar = refVarItr.next();
3579 if( liveSetIn.contains( refVar ) ) {
3580 copySet.add( refVar );
3584 if( !copySet.isEmpty() ) {
3585 plan.addStall2CopySet( vstAlsoAvail, copySet );
3590 // the other case for srcs is READY, so do nothing
3593 // assert that everything being stalled for is in the
3594 // "not available" set coming into this flat node and
3595 // that every VST identified is in the possible "stall set"
3596 // that represents VST's from children SESE's
3604 // identify sese-age pairs that are statically useful
3605 // and should have an associated SESE variable in code
3606 // JUST GET ALL SESE/AGE NAMES FOR NOW, PRUNE LATER,
3607 // AND ALWAYS GIVE NAMES TO PARENTS
3608 Set<VariableSourceToken> staticSet = vstTableIn.get();
3609 Iterator<VariableSourceToken> vstItr = staticSet.iterator();
3610 while( vstItr.hasNext() ) {
3611 VariableSourceToken vst = vstItr.next();
3613 // placeholder source tokens are useful results, but
3614 // the placeholder static name is never needed
3615 if( vst.getSESE().getIsCallerSESEplaceholder() ) {
3619 FlatSESEEnterNode sese = currentSESE;
3620 while( sese != null ) {
3621 sese.addNeededStaticName(
3622 new SESEandAgePair( vst.getSESE(), vst.getAge() )
3624 sese.mustTrackAtLeastAge( vst.getAge() );
3626 sese = sese.getParent();
3631 codePlans.put( fn, plan );
3634 // if any variables at this-node-*dot* have a static source (exactly one vst)
3635 // but go to a dynamic source at next-node-*dot*, create a new IR graph
3636 // node on that edge to track the sources dynamically
3637 VarSrcTokTable thisVstTable = variableResults.get( fn );
3638 for( int i = 0; i < fn.numNext(); i++ ) {
3639 FlatNode nn = fn.getNext( i );
3640 VarSrcTokTable nextVstTable = variableResults.get( nn );
3641 Set<TempDescriptor> nextLiveIn = livenessRootView.get( nn );
3643 // the table can be null if it is one of the few IR nodes
3644 // completely outside of the root SESE scope
3645 if( nextVstTable != null && nextLiveIn != null ) {
3647 Hashtable<TempDescriptor, VSTWrapper> readyOrStatic2dynamicSet =
3648 thisVstTable.getReadyOrStatic2DynamicSet( nextVstTable,
3653 if( !readyOrStatic2dynamicSet.isEmpty() ) {
3655 // either add these results to partial fixed-point result
3656 // or make a new one if we haven't made any here yet
3657 FlatEdge fe = new FlatEdge( fn, nn );
3658 FlatWriteDynamicVarNode fwdvn = wdvNodesToSpliceIn.get( fe );
3660 if( fwdvn == null ) {
3661 fwdvn = new FlatWriteDynamicVarNode( fn,
3663 readyOrStatic2dynamicSet,
3666 wdvNodesToSpliceIn.put( fe, fwdvn );
3668 fwdvn.addMoreVar2Src( readyOrStatic2dynamicSet );
3676 public void writeReports( String timeReport ) throws java.io.IOException {
3678 BufferedWriter bw = new BufferedWriter( new FileWriter( "mlpReport_summary.txt" ) );
3679 bw.write( "MLP Analysis Results\n\n" );
3680 bw.write( timeReport+"\n\n" );
3681 printSESEHierarchy( bw );
3683 printSESEInfo( bw );
3686 Iterator<Descriptor> methItr = ownAnalysis.descriptorsToAnalyze.iterator();
3687 while( methItr.hasNext() ) {
3688 MethodDescriptor md = (MethodDescriptor) methItr.next();
3689 FlatMethod fm = state.getMethodFlat( md );
3690 bw = new BufferedWriter( new FileWriter( "mlpReport_"+
3691 md.getClassMethodName()+
3692 md.getSafeMethodDescriptor()+
3694 bw.write( "MLP Results for "+md+"\n-------------------\n");
3696 FlatSESEEnterNode implicitSESE = (FlatSESEEnterNode) fm.getNext(0);
3697 if( !implicitSESE.getIsCallerSESEplaceholder() &&
3698 implicitSESE != mainSESE
3700 System.out.println( implicitSESE+" is not implicit?!" );
3703 bw.write( "Dynamic vars to manage:\n "+implicitSESE.getDynamicVarSet());
3705 bw.write( "\n\nLive-In, Root View\n------------------\n" +fm.printMethod( livenessRootView ) );
3706 bw.write( "\n\nVariable Results-Out\n----------------\n" +fm.printMethod( variableResults ) );
3707 bw.write( "\n\nNot Available Results-Out\n---------------------\n"+fm.printMethod( notAvailableResults ) );
3708 bw.write( "\n\nCode Plans\n----------\n" +fm.printMethod( codePlans ) );
3709 bw.write("\n\nSESE Effects\n----------------------\n"+printSESEEffects());
3714 private String printSESEEffects() {
3716 StringWriter writer = new StringWriter();
3718 Iterator<FlatSESEEnterNode> keyIter = allSESEs.iterator();
3720 while (keyIter.hasNext()) {
3721 FlatSESEEnterNode seseEnter = keyIter.next();
3722 String result = seseEnter.getSeseEffectsSet().printSet();
3723 if (result.length() > 0) {
3724 writer.write("\nSESE " + seseEnter + "\n");
3725 writer.write(result);
3728 keyIter = rootSESEs.iterator();
3729 while (keyIter.hasNext()) {
3730 FlatSESEEnterNode seseEnter = keyIter.next();
3731 if (seseEnter.getIsCallerSESEplaceholder()) {
3732 if (!seseEnter.getChildren().isEmpty()) {
3733 String result = seseEnter.getSeseEffectsSet().printSet();
3734 if (result.length() > 0) {
3735 writer.write("\nSESE " + seseEnter + "\n");
3736 writer.write(result);
3742 return writer.toString();
3746 private void printSESEHierarchy( BufferedWriter bw ) throws java.io.IOException {
3747 bw.write( "SESE Hierarchy\n--------------\n" );
3748 Iterator<FlatSESEEnterNode> rootItr = rootSESEs.iterator();
3749 while( rootItr.hasNext() ) {
3750 FlatSESEEnterNode root = rootItr.next();
3751 if( root.getIsCallerSESEplaceholder() ) {
3752 if( !root.getChildren().isEmpty() ) {
3753 printSESEHierarchyTree( bw, root, 0 );
3756 printSESEHierarchyTree( bw, root, 0 );
3761 private void printSESEHierarchyTree( BufferedWriter bw,
3762 FlatSESEEnterNode fsen,
3764 ) throws java.io.IOException {
3765 for( int i = 0; i < depth; ++i ) {
3768 bw.write( "- "+fsen.getPrettyIdentifier()+"\n" );
3770 Iterator<FlatSESEEnterNode> childItr = fsen.getChildren().iterator();
3771 while( childItr.hasNext() ) {
3772 FlatSESEEnterNode fsenChild = childItr.next();
3773 printSESEHierarchyTree( bw, fsenChild, depth + 1 );
3778 private void printSESEInfo( BufferedWriter bw ) throws java.io.IOException {
3779 bw.write("\nSESE info\n-------------\n" );
3780 Iterator<FlatSESEEnterNode> rootItr = rootSESEs.iterator();
3781 while( rootItr.hasNext() ) {
3782 FlatSESEEnterNode root = rootItr.next();
3783 if( root.getIsCallerSESEplaceholder() ) {
3784 if( !root.getChildren().isEmpty() ) {
3785 printSESEInfoTree( bw, root );
3788 printSESEInfoTree( bw, root );
3793 private void printSESEInfoTree( BufferedWriter bw,
3794 FlatSESEEnterNode fsen
3795 ) throws java.io.IOException {
3797 if( !fsen.getIsCallerSESEplaceholder() ) {
3798 bw.write( "SESE "+fsen.getPrettyIdentifier()+" {\n" );
3800 bw.write( " in-set: "+fsen.getInVarSet()+"\n" );
3801 Iterator<TempDescriptor> tItr = fsen.getInVarSet().iterator();
3802 while( tItr.hasNext() ) {
3803 TempDescriptor inVar = tItr.next();
3804 if( fsen.getReadyInVarSet().contains( inVar ) ) {
3805 bw.write( " (ready) "+inVar+"\n" );
3807 if( fsen.getStaticInVarSet().contains( inVar ) ) {
3808 bw.write( " (static) "+inVar+" from "+
3809 fsen.getStaticInVarSrc( inVar )+"\n" );
3811 if( fsen.getDynamicInVarSet().contains( inVar ) ) {
3812 bw.write( " (dynamic)"+inVar+"\n" );
3816 bw.write( " Dynamic vars to manage: "+fsen.getDynamicVarSet()+"\n");
3818 bw.write( " out-set: "+fsen.getOutVarSet()+"\n" );
3822 Iterator<FlatSESEEnterNode> childItr = fsen.getChildren().iterator();
3823 while( childItr.hasNext() ) {
3824 FlatSESEEnterNode fsenChild = childItr.next();
3825 printSESEInfoTree( bw, fsenChild );
3829 public Hashtable <FlatNode, ConflictGraph> getConflictGraphResults(){
3830 return conflictGraphResults;
3833 public Hashtable < FlatNode, ParentChildConflictsMap > getConflictsResults(){
3834 return conflictsResults;
3837 public Hashtable<FlatNode, SESESummary> getSeseSummaryMap(){
3838 return seseSummaryMap;
3841 public Hashtable<ConflictGraph, HashSet<SESELock>> getConflictGraphLockMap(){
3842 return conflictGraphLockMap;