3 import Analysis.CallGraph.*;
4 import Analysis.OwnershipAnalysis.*;
12 public class MLPAnalysis {
14 // data from the compiler
16 private TypeUtil typeUtil;
17 private CallGraph callGraph;
18 private OwnershipAnalysis ownAnalysis;
20 private FlatSESEEnterNode rootSESE;
21 private Set<FlatSESEEnterNode> allSESEs;
23 private Hashtable< FlatNode, Stack<FlatSESEEnterNode> > seseStacks;
24 private Hashtable< FlatNode, Set<TempDescriptor> > livenessRootView;
25 private Hashtable< FlatNode, Set<TempDescriptor> > livenessVirtualReads;
26 private Hashtable< FlatNode, VarSrcTokTable > variableResults;
27 private Hashtable< FlatNode, Set<TempDescriptor> > notAvailableResults;
28 private Hashtable< FlatNode, CodePlan > codePlans;
30 private Hashtable<FlatEdge, FlatWriteDynamicVarNode> wdvNodesToSpliceIn;
32 public static int maxSESEage = -1;
35 // use these methods in BuildCode to have access to analysis results
36 public FlatSESEEnterNode getRootSESE() {
40 public Set<FlatSESEEnterNode> getAllSESEs() {
44 public int getMaxSESEage() {
49 public CodePlan getCodePlan( FlatNode fn ) {
50 CodePlan cp = codePlans.get( fn );
55 public MLPAnalysis( State state,
58 OwnershipAnalysis ownAnalysis
61 double timeStartAnalysis = (double) System.nanoTime();
65 this.callGraph = callGraph;
66 this.ownAnalysis = ownAnalysis;
67 this.maxSESEage = state.MLP_MAXSESEAGE;
69 // initialize analysis data structures
70 allSESEs = new HashSet<FlatSESEEnterNode>();
72 seseStacks = new Hashtable< FlatNode, Stack<FlatSESEEnterNode> >();
73 livenessVirtualReads = new Hashtable< FlatNode, Set<TempDescriptor> >();
74 variableResults = new Hashtable< FlatNode, VarSrcTokTable >();
75 notAvailableResults = new Hashtable< FlatNode, Set<TempDescriptor> >();
76 codePlans = new Hashtable< FlatNode, CodePlan >();
78 wdvNodesToSpliceIn = new Hashtable<FlatEdge, FlatWriteDynamicVarNode>();
81 FlatMethod fmMain = state.getMethodFlat( tu.getMain() );
83 rootSESE = (FlatSESEEnterNode) fmMain.getNext(0);
84 rootSESE.setfmEnclosing( fmMain );
85 rootSESE.setmdEnclosing( fmMain.getMethod() );
86 rootSESE.setcdEnclosing( fmMain.getMethod().getClassDesc() );
88 if( state.MLPDEBUG ) {
89 System.out.println( "" );
93 // run analysis on each method that is actually called
94 // reachability analysis already computed this so reuse
95 Iterator<Descriptor> methItr = ownAnalysis.descriptorsToAnalyze.iterator();
96 while( methItr.hasNext() ) {
97 Descriptor d = methItr.next();
98 FlatMethod fm = state.getMethodFlat( d );
100 // find every SESE from methods that may be called
101 // and organize them into roots and children
102 buildForestForward( fm );
104 if( state.MLPDEBUG ) {
105 //System.out.println( "\nSESE Hierarchy\n--------------\n" ); printSESEHierarchy();
109 // 2nd pass, results are saved in FlatSESEEnterNode, so
110 // intermediate results, for safety, are discarded
111 livenessAnalysisBackward( rootSESE, true, null, fmMain.getFlatExit() );
115 methItr = ownAnalysis.descriptorsToAnalyze.iterator();
116 while( methItr.hasNext() ) {
117 Descriptor d = methItr.next();
118 FlatMethod fm = state.getMethodFlat( d );
120 // starting from roots do a forward, fixed-point
121 // variable analysis for refinement and stalls
122 variableAnalysisForward( fm );
126 // 4th pass, compute liveness contribution from
127 // virtual reads discovered in variable pass
128 livenessAnalysisBackward( rootSESE, true, null, fmMain.getFlatExit() );
129 if( state.MLPDEBUG ) {
130 //System.out.println( "\nLive-In, SESE View\n-------------\n" ); printSESELiveness();
131 //System.out.println( "\nLive-In, Root View\n------------------\n"+fmMain.printMethod( livenessRootView ) );
136 methItr = ownAnalysis.descriptorsToAnalyze.iterator();
137 while( methItr.hasNext() ) {
138 Descriptor d = methItr.next();
139 FlatMethod fm = state.getMethodFlat( d );
141 // prune variable results in one traversal
142 // by removing reference variables that are not live
143 pruneVariableResultsWithLiveness( fm );
145 if( state.MLPDEBUG ) {
146 System.out.println( "\nVariable Results-Out\n----------------\n"+fmMain.printMethod( variableResults ) );
151 methItr = ownAnalysis.descriptorsToAnalyze.iterator();
152 while( methItr.hasNext() ) {
153 Descriptor d = methItr.next();
154 FlatMethod fm = state.getMethodFlat( d );
156 // compute what is not available at every program
157 // point, in a forward fixed-point pass
158 notAvailableForward( fm );
160 if( state.MLPDEBUG ) {
161 //System.out.println( "\nNot Available Results-Out\n---------------------\n"+fmMain.printMethod( notAvailableResults ) );
166 methItr = ownAnalysis.descriptorsToAnalyze.iterator();
167 while( methItr.hasNext() ) {
168 Descriptor d = methItr.next();
169 FlatMethod fm = state.getMethodFlat( d );
171 // compute a plan for code injections
172 computeStallsForward( fm );
174 if( state.MLPDEBUG ) {
175 //System.out.println( "\nCode Plans\n----------\n"+fmMain.printMethod( codePlans ) );
178 // splice new IR nodes into graph after all
179 // analysis passes are complete
180 Iterator spliceItr = wdvNodesToSpliceIn.entrySet().iterator();
181 while( spliceItr.hasNext() ) {
182 Map.Entry me = (Map.Entry) spliceItr.next();
183 FlatWriteDynamicVarNode fwdvn = (FlatWriteDynamicVarNode) me.getValue();
184 fwdvn.spliceIntoIR();
187 // detailed per-SESE information
188 if( state.MLPDEBUG ) {
189 System.out.println( "\nSESE info\n-------------\n" ); printSESEInfo();
192 double timeEndAnalysis = (double) System.nanoTime();
193 double dt = (timeEndAnalysis - timeStartAnalysis)/(Math.pow( 10.0, 9.0 ) );
194 String treport = String.format( "The mlp analysis took %.3f sec.", dt );
195 System.out.println( treport );
199 private void buildForestForward( FlatMethod fm ) {
201 // start from flat method top, visit every node in
202 // method exactly once, find SESEs and remember
203 // roots and child relationships
204 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
205 flatNodesToVisit.add( fm );
207 Set<FlatNode> visited = new HashSet<FlatNode>();
209 Stack<FlatSESEEnterNode> seseStackFirst = new Stack<FlatSESEEnterNode>();
210 seseStacks.put( fm, seseStackFirst );
212 while( !flatNodesToVisit.isEmpty() ) {
213 Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
214 FlatNode fn = fnItr.next();
216 Stack<FlatSESEEnterNode> seseStack = seseStacks.get( fn );
217 assert seseStack != null;
219 flatNodesToVisit.remove( fn );
222 buildForest_nodeActions( fn, seseStack, fm );
224 for( int i = 0; i < fn.numNext(); i++ ) {
225 FlatNode nn = fn.getNext( i );
227 if( !visited.contains( nn ) ) {
228 flatNodesToVisit.add( nn );
230 // clone stack and send along each analysis path
231 seseStacks.put( nn, (Stack<FlatSESEEnterNode>)seseStack.clone() );
237 private void buildForest_nodeActions( FlatNode fn,
238 Stack<FlatSESEEnterNode> seseStack,
240 switch( fn.kind() ) {
242 case FKind.FlatSESEEnterNode: {
243 FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
245 allSESEs.add( fsen );
246 fsen.setfmEnclosing( fm );
247 fsen.setmdEnclosing( fm.getMethod() );
248 fsen.setcdEnclosing( fm.getMethod().getClassDesc() );
250 if( !seseStack.empty() ) {
251 seseStack.peek().addChild( fsen );
252 fsen.setParent( seseStack.peek() );
255 seseStack.push( fsen );
258 case FKind.FlatSESEExitNode: {
259 FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
260 assert !seseStack.empty();
261 FlatSESEEnterNode fsen = seseStack.pop();
264 case FKind.FlatReturnNode: {
265 FlatReturnNode frn = (FlatReturnNode) fn;
266 if( !seseStack.empty() ) {
267 throw new Error( "Error: return statement enclosed within SESE "+
268 seseStack.peek().getPrettyIdentifier() );
275 private void printSESEHierarchy() {
276 // our forest is actually a tree now that
277 // there is an implicit root SESE
278 printSESEHierarchyTree( rootSESE, 0 );
279 System.out.println( "" );
282 private void printSESEHierarchyTree( FlatSESEEnterNode fsen, int depth ) {
283 for( int i = 0; i < depth; ++i ) {
284 System.out.print( " " );
286 System.out.println( "- "+fsen.getPrettyIdentifier() );
288 Iterator<FlatSESEEnterNode> childItr = fsen.getChildren().iterator();
289 while( childItr.hasNext() ) {
290 FlatSESEEnterNode fsenChild = childItr.next();
291 printSESEHierarchyTree( fsenChild, depth + 1 );
296 private void livenessAnalysisBackward( FlatSESEEnterNode fsen,
298 Hashtable< FlatSESEExitNode, Set<TempDescriptor> > liveout,
301 // start from an SESE exit, visit nodes in reverse up to
302 // SESE enter in a fixed-point scheme, where children SESEs
303 // should already be analyzed and therefore can be skipped
304 // because child SESE enter node has all necessary info
305 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
307 FlatSESEExitNode fsexn = fsen.getFlatExit();
310 flatNodesToVisit.add( fexit );
312 flatNodesToVisit.add( fsexn );
313 Hashtable<FlatNode, Set<TempDescriptor>> livenessResults=new Hashtable<FlatNode, Set<TempDescriptor>>();
316 liveout=new Hashtable<FlatSESEExitNode, Set<TempDescriptor>>();
318 while( !flatNodesToVisit.isEmpty() ) {
319 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
320 flatNodesToVisit.remove( fn );
322 Set<TempDescriptor> prev = livenessResults.get( fn );
324 // merge sets from control flow joins
325 Set<TempDescriptor> u = new HashSet<TempDescriptor>();
326 for( int i = 0; i < fn.numNext(); i++ ) {
327 FlatNode nn = fn.getNext( i );
328 Set<TempDescriptor> s = livenessResults.get( nn );
334 Set<TempDescriptor> curr = liveness_nodeActions( fn, u, fsen, toplevel, liveout);
336 // if a new result, schedule backward nodes for analysis
337 if( !curr.equals( prev ) ) {
338 livenessResults.put( fn, curr );
340 // don't flow backwards past current SESE enter
341 if( !fn.equals( fsen ) ) {
342 for( int i = 0; i < fn.numPrev(); i++ ) {
343 FlatNode nn = fn.getPrev( i );
344 flatNodesToVisit.add( nn );
350 Set<TempDescriptor> s = livenessResults.get( fsen );
352 fsen.addInVarSet( s );
355 // remember liveness per node from the root view as the
356 // global liveness of variables for later passes to use
357 if( toplevel == true ) {
358 livenessRootView = livenessResults;
361 // post-order traversal, so do children first
362 Iterator<FlatSESEEnterNode> childItr = fsen.getChildren().iterator();
363 while( childItr.hasNext() ) {
364 FlatSESEEnterNode fsenChild = childItr.next();
365 livenessAnalysisBackward( fsenChild, false, liveout, null );
369 private Set<TempDescriptor> liveness_nodeActions( FlatNode fn,
370 Set<TempDescriptor> liveIn,
371 FlatSESEEnterNode currentSESE,
373 Hashtable< FlatSESEExitNode, Set<TempDescriptor> > liveout ) {
375 switch( fn.kind() ) {
377 case FKind.FlatSESEExitNode:
378 if (toplevel==true) {
379 FlatSESEExitNode exitn=(FlatSESEExitNode) fn;
380 //update liveout set for FlatSESEExitNode
381 if (!liveout.containsKey(exitn))
382 liveout.put(exitn, new HashSet<TempDescriptor>());
383 liveout.get(exitn).addAll(liveIn);
385 // no break, sese exits should also execute default actions
388 // handle effects of statement in reverse, writes then reads
389 TempDescriptor [] writeTemps = fn.writesTemps();
390 for( int i = 0; i < writeTemps.length; ++i ) {
391 liveIn.remove( writeTemps[i] );
394 FlatSESEExitNode exitnode=currentSESE.getFlatExit();
395 Set<TempDescriptor> livetemps=liveout.get(exitnode);
396 if (livetemps.contains(writeTemps[i])) {
397 //write to a live out temp...
398 //need to put in SESE liveout set
399 currentSESE.addOutVar(writeTemps[i]);
404 TempDescriptor [] readTemps = fn.readsTemps();
405 for( int i = 0; i < readTemps.length; ++i ) {
406 liveIn.add( readTemps[i] );
409 Set<TempDescriptor> virtualReadTemps = livenessVirtualReads.get( fn );
410 if( virtualReadTemps != null ) {
411 Iterator<TempDescriptor> vrItr = virtualReadTemps.iterator();
412 while( vrItr.hasNext() ) {
413 TempDescriptor vrt = vrItr.next();
424 private void printSESELiveness() {
425 // our forest is actually a tree now that
426 // there is an implicit root SESE
427 printSESELivenessTree( rootSESE );
428 System.out.println( "" );
431 private void printSESELivenessTree( FlatSESEEnterNode fsen ) {
433 System.out.println( "SESE "+fsen.getPrettyIdentifier()+" has in-set:" );
434 Iterator<TempDescriptor> tItr = fsen.getInVarSet().iterator();
435 while( tItr.hasNext() ) {
436 System.out.println( " "+tItr.next() );
438 System.out.println( "and out-set:" );
439 tItr = fsen.getOutVarSet().iterator();
440 while( tItr.hasNext() ) {
441 System.out.println( " "+tItr.next() );
443 System.out.println( "" );
446 Iterator<FlatSESEEnterNode> childItr = fsen.getChildren().iterator();
447 while( childItr.hasNext() ) {
448 FlatSESEEnterNode fsenChild = childItr.next();
449 printSESELivenessTree( fsenChild );
453 private void printSESEInfo() {
454 printSESEInfoTree( rootSESE );
455 System.out.println( "" );
458 private void printSESEInfoTree( FlatSESEEnterNode fsen ) {
460 System.out.println( "SESE "+fsen.getPrettyIdentifier()+" {" );
462 System.out.println( " in-set: "+fsen.getInVarSet() );
463 Iterator<TempDescriptor> tItr = fsen.getInVarSet().iterator();
464 while( tItr.hasNext() ) {
465 TempDescriptor inVar = tItr.next();
466 if( fsen.getReadyInVarSet().contains( inVar ) ) {
467 System.out.println( " (ready) "+inVar );
469 if( fsen.getStaticInVarSet().contains( inVar ) ) {
470 System.out.println( " (static) "+inVar );
472 if( fsen.getDynamicInVarSet().contains( inVar ) ) {
473 System.out.println( " (dynamic)"+inVar );
477 System.out.println( " out-set: "+fsen.getOutVarSet() );
480 System.out.println( " static names to track:" );
481 tItr = fsen.getOutVarSet().iterator();
482 while( tItr.hasNext() ) {
483 System.out.println( " "+tItr.next() );
487 System.out.println( "}" );
489 Iterator<FlatSESEEnterNode> childItr = fsen.getChildren().iterator();
490 while( childItr.hasNext() ) {
491 FlatSESEEnterNode fsenChild = childItr.next();
492 printSESEInfoTree( fsenChild );
497 private void variableAnalysisForward( FlatMethod fm ) {
499 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
500 flatNodesToVisit.add( fm );
502 while( !flatNodesToVisit.isEmpty() ) {
503 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
504 flatNodesToVisit.remove( fn );
506 Stack<FlatSESEEnterNode> seseStack = seseStacks.get( fn );
507 assert seseStack != null;
509 VarSrcTokTable prev = variableResults.get( fn );
511 // merge sets from control flow joins
512 VarSrcTokTable curr = new VarSrcTokTable();
513 for( int i = 0; i < fn.numPrev(); i++ ) {
514 FlatNode nn = fn.getPrev( i );
515 VarSrcTokTable incoming = variableResults.get( nn );
516 curr.merge( incoming );
519 if( !seseStack.empty() ) {
520 variable_nodeActions( fn, curr, seseStack.peek() );
523 // if a new result, schedule forward nodes for analysis
524 if( !curr.equals( prev ) ) {
525 variableResults.put( fn, curr );
527 for( int i = 0; i < fn.numNext(); i++ ) {
528 FlatNode nn = fn.getNext( i );
529 flatNodesToVisit.add( nn );
535 private void variable_nodeActions( FlatNode fn,
536 VarSrcTokTable vstTable,
537 FlatSESEEnterNode currentSESE ) {
538 switch( fn.kind() ) {
540 case FKind.FlatSESEEnterNode: {
541 FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
542 assert fsen.equals( currentSESE );
544 vstTable.age( currentSESE );
545 vstTable.assertConsistency();
547 vstTable.ownInSet( currentSESE );
548 vstTable.assertConsistency();
551 case FKind.FlatSESEExitNode: {
552 FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
553 FlatSESEEnterNode fsen = fsexn.getFlatEnter();
554 assert currentSESE.getChildren().contains( fsen );
555 vstTable.remapChildTokens( fsen );
557 Set<TempDescriptor> liveIn = currentSESE.getInVarSet();
558 Set<TempDescriptor> virLiveIn = vstTable.removeParentAndSiblingTokens( fsen, liveIn );
559 Set<TempDescriptor> virLiveInOld = livenessVirtualReads.get( fn );
560 if( virLiveInOld != null ) {
561 virLiveIn.addAll( virLiveInOld );
563 livenessVirtualReads.put( fn, virLiveIn );
564 vstTable.assertConsistency();
566 // then all child out-set tokens are guaranteed
567 // to be filled in, so clobber those entries with
568 // the latest, clean sources
569 Iterator<TempDescriptor> outVarItr = fsen.getOutVarSet().iterator();
570 while( outVarItr.hasNext() ) {
571 TempDescriptor outVar = outVarItr.next();
572 HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
574 VariableSourceToken vst = new VariableSourceToken( ts,
579 vstTable.remove( outVar );
582 vstTable.assertConsistency();
586 case FKind.FlatOpNode: {
587 FlatOpNode fon = (FlatOpNode) fn;
589 if( fon.getOp().getOp() == Operation.ASSIGN ) {
590 TempDescriptor lhs = fon.getDest();
591 TempDescriptor rhs = fon.getLeft();
593 vstTable.remove( lhs );
595 Set<VariableSourceToken> forAddition = new HashSet<VariableSourceToken>();
597 Iterator<VariableSourceToken> itr = vstTable.get( rhs ).iterator();
598 while( itr.hasNext() ) {
599 VariableSourceToken vst = itr.next();
601 HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
604 forAddition.add( new VariableSourceToken( ts,
612 vstTable.addAll( forAddition );
614 // only break if this is an ASSIGN op node,
615 // otherwise fall through to default case
616 vstTable.assertConsistency();
621 // note that FlatOpNode's that aren't ASSIGN
622 // fall through to this default case
624 TempDescriptor [] writeTemps = fn.writesTemps();
625 if( writeTemps.length > 0 ) {
628 // for now, when writeTemps > 1, make sure
629 // its a call node, programmer enforce only
630 // doing stuff like calling a print routine
631 //assert writeTemps.length == 1;
632 if( writeTemps.length > 1 ) {
633 assert fn.kind() == FKind.FlatCall ||
634 fn.kind() == FKind.FlatMethod;
639 vstTable.remove( writeTemps[0] );
641 HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
642 ts.add( writeTemps[0] );
644 vstTable.add( new VariableSourceToken( ts,
652 vstTable.assertConsistency();
659 private void pruneVariableResultsWithLiveness( FlatMethod fm ) {
661 // start from flat method top, visit every node in
662 // method exactly once
663 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
664 flatNodesToVisit.add( fm );
666 Set<FlatNode> visited = new HashSet<FlatNode>();
668 while( !flatNodesToVisit.isEmpty() ) {
669 Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
670 FlatNode fn = fnItr.next();
672 flatNodesToVisit.remove( fn );
675 Set<TempDescriptor> rootLiveSet = livenessRootView.get( fn );
676 VarSrcTokTable vstTable = variableResults.get( fn );
678 // fix later, not working, only wanted it to make tables easier to read
679 //vstTable.pruneByLiveness( rootLiveSet );
681 for( int i = 0; i < fn.numNext(); i++ ) {
682 FlatNode nn = fn.getNext( i );
684 if( !visited.contains( nn ) ) {
685 flatNodesToVisit.add( nn );
692 private void notAvailableForward( FlatMethod fm ) {
694 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
695 flatNodesToVisit.add( fm );
697 while( !flatNodesToVisit.isEmpty() ) {
698 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
699 flatNodesToVisit.remove( fn );
701 Stack<FlatSESEEnterNode> seseStack = seseStacks.get( fn );
702 assert seseStack != null;
704 Set<TempDescriptor> prev = notAvailableResults.get( fn );
706 Set<TempDescriptor> curr = new HashSet<TempDescriptor>();
707 for( int i = 0; i < fn.numPrev(); i++ ) {
708 FlatNode nn = fn.getPrev( i );
709 Set<TempDescriptor> notAvailIn = notAvailableResults.get( nn );
710 if( notAvailIn != null ) {
711 curr.addAll( notAvailIn );
715 if( !seseStack.empty() ) {
716 notAvailable_nodeActions( fn, curr, seseStack.peek() );
719 // if a new result, schedule forward nodes for analysis
720 if( !curr.equals( prev ) ) {
721 notAvailableResults.put( fn, curr );
723 for( int i = 0; i < fn.numNext(); i++ ) {
724 FlatNode nn = fn.getNext( i );
725 flatNodesToVisit.add( nn );
731 private void notAvailable_nodeActions( FlatNode fn,
732 Set<TempDescriptor> notAvailSet,
733 FlatSESEEnterNode currentSESE ) {
735 // any temps that are removed from the not available set
736 // at this node should be marked in this node's code plan
737 // as temps to be grabbed at runtime!
739 switch( fn.kind() ) {
741 case FKind.FlatSESEEnterNode: {
742 FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
743 assert fsen.equals( currentSESE );
747 case FKind.FlatSESEExitNode: {
748 FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
749 FlatSESEEnterNode fsen = fsexn.getFlatEnter();
750 assert currentSESE.getChildren().contains( fsen );
752 Set<TempDescriptor> liveTemps = livenessRootView.get( fn );
753 assert liveTemps != null;
755 notAvailSet.addAll( liveTemps );
758 case FKind.FlatOpNode: {
759 FlatOpNode fon = (FlatOpNode) fn;
761 if( fon.getOp().getOp() == Operation.ASSIGN ) {
762 TempDescriptor lhs = fon.getDest();
763 TempDescriptor rhs = fon.getLeft();
765 // copy makes lhs same availability as rhs
766 if( notAvailSet.contains( rhs ) ) {
767 notAvailSet.add( lhs );
769 notAvailSet.remove( lhs );
772 // only break if this is an ASSIGN op node,
773 // otherwise fall through to default case
778 // note that FlatOpNode's that aren't ASSIGN
779 // fall through to this default case
781 TempDescriptor [] writeTemps = fn.writesTemps();
782 for( int i = 0; i < writeTemps.length; i++ ) {
783 TempDescriptor wTemp = writeTemps[i];
784 notAvailSet.remove( wTemp );
786 TempDescriptor [] readTemps = fn.readsTemps();
787 for( int i = 0; i < readTemps.length; i++ ) {
788 TempDescriptor rTemp = readTemps[i];
789 notAvailSet.remove( rTemp );
791 // if this variable has exactly one source, potentially
792 // get other things from this source as well
793 VarSrcTokTable vstTable = variableResults.get( fn );
796 vstTable.getRefVarSrcType( rTemp,
798 currentSESE.getParent() );
800 if( srcType.equals( VarSrcTokTable.SrcType_STATIC ) ) {
802 VariableSourceToken vst = vstTable.get( rTemp ).iterator().next();
804 Iterator<VariableSourceToken> availItr = vstTable.get( vst.getSESE(),
808 // look through things that are also available from same source
809 while( availItr.hasNext() ) {
810 VariableSourceToken vstAlsoAvail = availItr.next();
812 Iterator<TempDescriptor> refVarItr = vstAlsoAvail.getRefVars().iterator();
813 while( refVarItr.hasNext() ) {
814 TempDescriptor refVarAlso = refVarItr.next();
816 // if a variable is available from the same source, AND it ALSO
817 // only comes from one statically known source, mark it available
818 Integer srcTypeAlso =
819 vstTable.getRefVarSrcType( refVarAlso,
821 currentSESE.getParent() );
822 if( srcTypeAlso.equals( VarSrcTokTable.SrcType_STATIC ) ) {
823 notAvailSet.remove( refVarAlso );
835 private void computeStallsForward( FlatMethod fm ) {
837 // start from flat method top, visit every node in
838 // method exactly once
839 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
840 flatNodesToVisit.add( fm );
842 Set<FlatNode> visited = new HashSet<FlatNode>();
844 while( !flatNodesToVisit.isEmpty() ) {
845 Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
846 FlatNode fn = fnItr.next();
848 flatNodesToVisit.remove( fn );
851 Stack<FlatSESEEnterNode> seseStack = seseStacks.get( fn );
852 assert seseStack != null;
854 // use incoming results as "dot statement" or just
855 // before the current statement
856 VarSrcTokTable dotSTtable = new VarSrcTokTable();
857 for( int i = 0; i < fn.numPrev(); i++ ) {
858 FlatNode nn = fn.getPrev( i );
859 dotSTtable.merge( variableResults.get( nn ) );
862 // find dt-st notAvailableSet also
863 Set<TempDescriptor> dotSTnotAvailSet = new HashSet<TempDescriptor>();
864 for( int i = 0; i < fn.numPrev(); i++ ) {
865 FlatNode nn = fn.getPrev( i );
866 Set<TempDescriptor> notAvailIn = notAvailableResults.get( nn );
867 if( notAvailIn != null ) {
868 dotSTnotAvailSet.addAll( notAvailIn );
872 Set<TempDescriptor> dotSTlive = livenessRootView.get( fn );
874 if( !seseStack.empty() ) {
875 computeStalls_nodeActions( fn,
883 for( int i = 0; i < fn.numNext(); i++ ) {
884 FlatNode nn = fn.getNext( i );
886 if( !visited.contains( nn ) ) {
887 flatNodesToVisit.add( nn );
893 private void computeStalls_nodeActions( FlatNode fn,
894 Set<TempDescriptor> liveSetIn,
895 VarSrcTokTable vstTableIn,
896 Set<TempDescriptor> notAvailSetIn,
897 FlatSESEEnterNode currentSESE ) {
899 CodePlan plan = new CodePlan( currentSESE);
901 switch( fn.kind() ) {
903 case FKind.FlatSESEEnterNode: {
904 FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
906 // track the source types of the in-var set so generated
907 // code at this SESE issue can compute the number of
908 // dependencies properly
909 Iterator<TempDescriptor> inVarItr = fsen.getInVarSet().iterator();
910 while( inVarItr.hasNext() ) {
911 TempDescriptor inVar = inVarItr.next();
913 vstTableIn.getRefVarSrcType( inVar,
917 // the current SESE needs a local space to track the dynamic
918 // variable and the child needs space in its SESE record
919 if( srcType.equals( VarSrcTokTable.SrcType_DYNAMIC ) ) {
920 fsen.addDynamicInVar( inVar );
921 fsen.getParent().addDynamicVar( inVar );
923 } else if( srcType.equals( VarSrcTokTable.SrcType_STATIC ) ) {
924 fsen.addStaticInVar( inVar );
925 VariableSourceToken vst = vstTableIn.get( inVar ).iterator().next();
926 fsen.putStaticInVar2src( inVar, vst );
927 fsen.addStaticInVarSrc( new SESEandAgePair( vst.getSESE(),
933 assert srcType.equals( VarSrcTokTable.SrcType_READY );
934 fsen.addReadyInVar( inVar );
940 case FKind.FlatSESEExitNode: {
941 FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
944 case FKind.FlatOpNode: {
945 FlatOpNode fon = (FlatOpNode) fn;
947 if( fon.getOp().getOp() == Operation.ASSIGN ) {
948 TempDescriptor lhs = fon.getDest();
949 TempDescriptor rhs = fon.getLeft();
951 // if this is an op node, don't stall, copy
952 // source and delay until we need to use value
954 // but check the source type of rhs variable
955 // and if dynamic, lhs becomes dynamic, too,
956 // and we need to keep dynamic sources during
958 = vstTableIn.getRefVarSrcType( rhs,
960 currentSESE.getParent() );
962 if( srcType.equals( VarSrcTokTable.SrcType_DYNAMIC ) ) {
963 plan.addDynAssign( lhs, rhs );
964 currentSESE.addDynamicVar( lhs );
965 currentSESE.addDynamicVar( rhs );
968 // only break if this is an ASSIGN op node,
969 // otherwise fall through to default case
974 // note that FlatOpNode's that aren't ASSIGN
975 // fall through to this default case
978 // a node with no live set has nothing to stall for
979 if( liveSetIn == null ) {
983 TempDescriptor[] readarray = fn.readsTemps();
984 for( int i = 0; i < readarray.length; i++ ) {
985 TempDescriptor readtmp = readarray[i];
987 // ignore temps that are definitely available
988 // when considering to stall on it
989 if( !notAvailSetIn.contains( readtmp ) ) {
993 // check the source type of this variable
995 = vstTableIn.getRefVarSrcType( readtmp,
997 currentSESE.getParent() );
999 if( srcType.equals( VarSrcTokTable.SrcType_DYNAMIC ) ) {
1000 // 1) It is not clear statically where this variable will
1001 // come from statically, so dynamically we must keep track
1002 // along various control paths, and therefore when we stall,
1003 // just stall for the exact thing we need and move on
1004 plan.addDynamicStall( readtmp );
1005 currentSESE.addDynamicVar( readtmp );
1007 } else if( srcType.equals( VarSrcTokTable.SrcType_STATIC ) ) {
1008 // 2) Single token/age pair: Stall for token/age pair, and copy
1009 // all live variables with same token/age pair at the same
1010 // time. This is the same stuff that the notavaialable analysis
1011 // marks as now available.
1013 VariableSourceToken vst = vstTableIn.get( readtmp ).iterator().next();
1015 Iterator<VariableSourceToken> availItr =
1016 vstTableIn.get( vst.getSESE(), vst.getAge() ).iterator();
1018 while( availItr.hasNext() ) {
1019 VariableSourceToken vstAlsoAvail = availItr.next();
1021 // only grab additional stuff that is live
1022 Set<TempDescriptor> copySet = new HashSet<TempDescriptor>();
1024 Iterator<TempDescriptor> refVarItr = vstAlsoAvail.getRefVars().iterator();
1025 while( refVarItr.hasNext() ) {
1026 TempDescriptor refVar = refVarItr.next();
1027 if( liveSetIn.contains( refVar ) ) {
1028 copySet.add( refVar );
1032 if( !copySet.isEmpty() ) {
1033 plan.addStall2CopySet( vstAlsoAvail, copySet );
1038 // the other case for srcs is READY from a parent, however
1039 // since we are only examining variables that come from
1040 // children tokens, this should never occur
1044 // assert that everything being stalled for is in the
1045 // "not available" set coming into this flat node and
1046 // that every VST identified is in the possible "stall set"
1047 // that represents VST's from children SESE's
1055 // identify sese-age pairs that are statically useful
1056 // and should have an associated SESE variable in code
1057 Set<VariableSourceToken> staticSet = vstTableIn.getStaticSet();
1058 Iterator<VariableSourceToken> vstItr = staticSet.iterator();
1059 while( vstItr.hasNext() ) {
1060 VariableSourceToken vst = vstItr.next();
1061 currentSESE.addNeededStaticName(
1062 new SESEandAgePair( vst.getSESE(), vst.getAge() )
1064 currentSESE.mustTrackAtLeastAge( vst.getAge() );
1068 codePlans.put( fn, plan );
1071 // if any variables at this-node-*dot* have a static source (exactly one vst)
1072 // but go to a dynamic source at next-node-*dot*, create a new IR graph
1073 // node on that edge to track the sources dynamically
1074 VarSrcTokTable thisVstTable = variableResults.get( fn );
1075 for( int i = 0; i < fn.numNext(); i++ ) {
1076 FlatNode nn = fn.getNext( i );
1077 VarSrcTokTable nextVstTable = variableResults.get( nn );
1078 Set<TempDescriptor> nextLiveIn = livenessRootView.get( nn );
1080 // the table can be null if it is one of the few IR nodes
1081 // completely outside of the root SESE scope
1082 if( nextVstTable != null && nextLiveIn != null ) {
1084 Hashtable<TempDescriptor, VariableSourceToken> static2dynamicSet =
1085 thisVstTable.getStatic2DynamicSet( nextVstTable, nextLiveIn );
1087 if( !static2dynamicSet.isEmpty() ) {
1089 // either add these results to partial fixed-point result
1090 // or make a new one if we haven't made any here yet
1091 FlatEdge fe = new FlatEdge( fn, nn );
1092 FlatWriteDynamicVarNode fwdvn = wdvNodesToSpliceIn.get( fe );
1094 if( fwdvn == null ) {
1095 fwdvn = new FlatWriteDynamicVarNode( fn,
1100 wdvNodesToSpliceIn.put( fe, fwdvn );
1102 fwdvn.addMoreVar2Src( static2dynamicSet );