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;
21 // an implicit SESE is automatically spliced into
22 // the IR graph around the C main before this analysis--it
23 // is nothing special except that we can make assumptions
24 // about it, such as the whole program ends when it ends
25 private FlatSESEEnterNode mainSESE;
27 // SESEs that are the root of an SESE tree belong to this
28 // set--the main SESE is always a root, statically SESEs
29 // inside methods are a root because we don't know how they
30 // will fit into the runtime tree of SESEs
31 private Set<FlatSESEEnterNode> rootSESEs;
33 // simply a set of every reachable SESE in the program, not
34 // including caller placeholder SESEs
35 private Set<FlatSESEEnterNode> allSESEs;
38 // A mapping of flat nodes to the stack of SESEs for that node, where
39 // an SESE is the child of the SESE directly below it on the stack.
40 // These stacks do not reflect the heirarchy over methods calls--whenever
41 // there is an empty stack it means all variables are available.
42 private Hashtable< FlatNode, Stack<FlatSESEEnterNode> > seseStacks;
44 private Hashtable< FlatNode, Set<TempDescriptor> > livenessRootView;
45 private Hashtable< FlatNode, Set<TempDescriptor> > livenessVirtualReads;
46 private Hashtable< FlatNode, VarSrcTokTable > variableResults;
47 private Hashtable< FlatNode, Set<TempDescriptor> > notAvailableResults;
48 private Hashtable< FlatNode, CodePlan > codePlans;
50 private Hashtable< FlatEdge, FlatWriteDynamicVarNode > wdvNodesToSpliceIn;
52 public static int maxSESEage = -1;
55 // use these methods in BuildCode to have access to analysis results
56 public FlatSESEEnterNode getMainSESE() {
60 public Set<FlatSESEEnterNode> getRootSESEs() {
64 public Set<FlatSESEEnterNode> getAllSESEs() {
68 public int getMaxSESEage() {
73 public CodePlan getCodePlan( FlatNode fn ) {
74 CodePlan cp = codePlans.get( fn );
79 public MLPAnalysis( State state,
82 OwnershipAnalysis ownAnalysis
85 double timeStartAnalysis = (double) System.nanoTime();
89 this.callGraph = callGraph;
90 this.ownAnalysis = ownAnalysis;
91 this.maxSESEage = state.MLP_MAXSESEAGE;
93 rootSESEs = new HashSet<FlatSESEEnterNode>();
94 allSESEs = new HashSet<FlatSESEEnterNode>();
96 seseStacks = new Hashtable< FlatNode, Stack<FlatSESEEnterNode> >();
97 livenessRootView = new Hashtable< FlatNode, Set<TempDescriptor> >();
98 livenessVirtualReads = new Hashtable< FlatNode, Set<TempDescriptor> >();
99 variableResults = new Hashtable< FlatNode, VarSrcTokTable >();
100 notAvailableResults = new Hashtable< FlatNode, Set<TempDescriptor> >();
101 codePlans = new Hashtable< FlatNode, CodePlan >();
102 wdvNodesToSpliceIn = new Hashtable< FlatEdge, FlatWriteDynamicVarNode >();
105 FlatMethod fmMain = state.getMethodFlat( typeUtil.getMain() );
107 mainSESE = (FlatSESEEnterNode) fmMain.getNext(0);
108 mainSESE.setfmEnclosing( fmMain );
109 mainSESE.setmdEnclosing( fmMain.getMethod() );
110 mainSESE.setcdEnclosing( fmMain.getMethod().getClassDesc() );
114 // run analysis on each method that is actually called
115 // reachability analysis already computed this so reuse
116 Iterator<Descriptor> methItr = ownAnalysis.descriptorsToAnalyze.iterator();
117 while( methItr.hasNext() ) {
118 Descriptor d = methItr.next();
119 FlatMethod fm = state.getMethodFlat( d );
121 // find every SESE from methods that may be called
122 // and organize them into roots and children
123 buildForestForward( fm );
127 // 2nd pass, results are saved in FlatSESEEnterNode, so
128 // intermediate results, for safety, are discarded
129 Iterator<FlatSESEEnterNode> rootItr = rootSESEs.iterator();
130 while( rootItr.hasNext() ) {
131 FlatSESEEnterNode root = rootItr.next();
132 livenessAnalysisBackward( root,
139 methItr = ownAnalysis.descriptorsToAnalyze.iterator();
140 while( methItr.hasNext() ) {
141 Descriptor d = methItr.next();
142 FlatMethod fm = state.getMethodFlat( d );
144 // starting from roots do a forward, fixed-point
145 // variable analysis for refinement and stalls
146 variableAnalysisForward( fm );
149 // 4th pass, compute liveness contribution from
150 // virtual reads discovered in variable pass
151 rootItr = rootSESEs.iterator();
152 while( rootItr.hasNext() ) {
153 FlatSESEEnterNode root = rootItr.next();
154 livenessAnalysisBackward( root,
161 SOMETHING IS WRONG WITH THIS, DON'T USE IT UNTIL IT CAN BE FIXED
164 methItr = ownAnalysis.descriptorsToAnalyze.iterator();
165 while( methItr.hasNext() ) {
166 Descriptor d = methItr.next();
167 FlatMethod fm = state.getMethodFlat( d );
169 // prune variable results in one traversal
170 // by removing reference variables that are not live
171 pruneVariableResultsWithLiveness( fm );
177 methItr = ownAnalysis.descriptorsToAnalyze.iterator();
178 while( methItr.hasNext() ) {
179 Descriptor d = methItr.next();
180 FlatMethod fm = state.getMethodFlat( d );
182 // compute what is not available at every program
183 // point, in a forward fixed-point pass
184 notAvailableForward( fm );
189 methItr = ownAnalysis.descriptorsToAnalyze.iterator();
190 while( methItr.hasNext() ) {
191 Descriptor d = methItr.next();
192 FlatMethod fm = state.getMethodFlat( d );
194 // compute a plan for code injections
195 codePlansForward( fm );
199 // splice new IR nodes into graph after all
200 // analysis passes are complete
201 Iterator spliceItr = wdvNodesToSpliceIn.entrySet().iterator();
202 while( spliceItr.hasNext() ) {
203 Map.Entry me = (Map.Entry) spliceItr.next();
204 FlatWriteDynamicVarNode fwdvn = (FlatWriteDynamicVarNode) me.getValue();
205 fwdvn.spliceIntoIR();
209 double timeEndAnalysis = (double) System.nanoTime();
210 double dt = (timeEndAnalysis - timeStartAnalysis)/(Math.pow( 10.0, 9.0 ) );
211 String treport = String.format( "The mlp analysis took %.3f sec.", dt );
212 System.out.println( treport );
214 if( state.MLPDEBUG ) {
216 writeReports( treport );
217 } catch( IOException e ) {}
222 private void buildForestForward( FlatMethod fm ) {
224 // start from flat method top, visit every node in
225 // method exactly once, find SESEs and remember
226 // roots and child relationships
227 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
228 flatNodesToVisit.add( fm );
230 Set<FlatNode> visited = new HashSet<FlatNode>();
232 Stack<FlatSESEEnterNode> seseStackFirst = new Stack<FlatSESEEnterNode>();
233 seseStacks.put( fm, seseStackFirst );
235 while( !flatNodesToVisit.isEmpty() ) {
236 Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
237 FlatNode fn = fnItr.next();
239 Stack<FlatSESEEnterNode> seseStack = seseStacks.get( fn );
240 assert seseStack != null;
242 flatNodesToVisit.remove( fn );
245 buildForest_nodeActions( fn, seseStack, fm );
247 for( int i = 0; i < fn.numNext(); i++ ) {
248 FlatNode nn = fn.getNext( i );
250 if( !visited.contains( nn ) ) {
251 flatNodesToVisit.add( nn );
253 // clone stack and send along each analysis path
254 seseStacks.put( nn, (Stack<FlatSESEEnterNode>)seseStack.clone() );
260 private void buildForest_nodeActions( FlatNode fn,
261 Stack<FlatSESEEnterNode> seseStack,
263 switch( fn.kind() ) {
265 case FKind.FlatSESEEnterNode: {
266 FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
268 if( !fsen.getIsCallerSESEplaceholder() ) {
269 allSESEs.add( fsen );
272 fsen.setfmEnclosing( fm );
273 fsen.setmdEnclosing( fm.getMethod() );
274 fsen.setcdEnclosing( fm.getMethod().getClassDesc() );
276 if( seseStack.empty() ) {
277 rootSESEs.add( fsen );
278 fsen.setParent( null );
280 seseStack.peek().addChild( fsen );
281 fsen.setParent( seseStack.peek() );
284 seseStack.push( fsen );
287 case FKind.FlatSESEExitNode: {
288 FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
289 assert !seseStack.empty();
290 FlatSESEEnterNode fsen = seseStack.pop();
293 case FKind.FlatReturnNode: {
294 FlatReturnNode frn = (FlatReturnNode) fn;
295 if( !seseStack.empty() &&
296 !seseStack.peek().getIsCallerSESEplaceholder()
298 throw new Error( "Error: return statement enclosed within SESE "+
299 seseStack.peek().getPrettyIdentifier() );
307 private void livenessAnalysisBackward( FlatSESEEnterNode fsen,
309 Hashtable< FlatSESEExitNode, Set<TempDescriptor> > liveout ) {
311 // start from an SESE exit, visit nodes in reverse up to
312 // SESE enter in a fixed-point scheme, where children SESEs
313 // should already be analyzed and therefore can be skipped
314 // because child SESE enter node has all necessary info
315 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
318 flatNodesToVisit.add( fsen.getfmEnclosing().getFlatExit() );
320 flatNodesToVisit.add( fsen.getFlatExit() );
323 Hashtable<FlatNode, Set<TempDescriptor>> livenessResults =
324 new Hashtable< FlatNode, Set<TempDescriptor> >();
327 liveout = new Hashtable< FlatSESEExitNode, Set<TempDescriptor> >();
330 while( !flatNodesToVisit.isEmpty() ) {
331 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
332 flatNodesToVisit.remove( fn );
334 Set<TempDescriptor> prev = livenessResults.get( fn );
336 // merge sets from control flow joins
337 Set<TempDescriptor> u = new HashSet<TempDescriptor>();
338 for( int i = 0; i < fn.numNext(); i++ ) {
339 FlatNode nn = fn.getNext( i );
340 Set<TempDescriptor> s = livenessResults.get( nn );
346 Set<TempDescriptor> curr = liveness_nodeActions( fn, u, fsen, toplevel, liveout);
348 // if a new result, schedule backward nodes for analysis
349 if( !curr.equals( prev ) ) {
350 livenessResults.put( fn, curr );
352 // don't flow backwards past current SESE enter
353 if( !fn.equals( fsen ) ) {
354 for( int i = 0; i < fn.numPrev(); i++ ) {
355 FlatNode nn = fn.getPrev( i );
356 flatNodesToVisit.add( nn );
362 Set<TempDescriptor> s = livenessResults.get( fsen );
364 fsen.addInVarSet( s );
367 // remember liveness per node from the root view as the
368 // global liveness of variables for later passes to use
370 livenessRootView.putAll( livenessResults );
373 // post-order traversal, so do children first
374 Iterator<FlatSESEEnterNode> childItr = fsen.getChildren().iterator();
375 while( childItr.hasNext() ) {
376 FlatSESEEnterNode fsenChild = childItr.next();
377 livenessAnalysisBackward( fsenChild, false, liveout );
381 private Set<TempDescriptor> liveness_nodeActions( FlatNode fn,
382 Set<TempDescriptor> liveIn,
383 FlatSESEEnterNode currentSESE,
385 Hashtable< FlatSESEExitNode, Set<TempDescriptor> > liveout
387 switch( fn.kind() ) {
389 case FKind.FlatSESEExitNode:
391 FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
392 if( !liveout.containsKey( fsexn ) ) {
393 liveout.put( fsexn, new HashSet<TempDescriptor>() );
395 liveout.get( fsexn ).addAll( liveIn );
397 // no break, sese exits should also execute default actions
400 // handle effects of statement in reverse, writes then reads
401 TempDescriptor [] writeTemps = fn.writesTemps();
402 for( int i = 0; i < writeTemps.length; ++i ) {
403 liveIn.remove( writeTemps[i] );
406 FlatSESEExitNode fsexn = currentSESE.getFlatExit();
407 Set<TempDescriptor> livetemps = liveout.get( fsexn );
408 if( livetemps != null &&
409 livetemps.contains( writeTemps[i] ) ) {
410 // write to a live out temp...
411 // need to put in SESE liveout set
412 currentSESE.addOutVar( writeTemps[i] );
417 TempDescriptor [] readTemps = fn.readsTemps();
418 for( int i = 0; i < readTemps.length; ++i ) {
419 liveIn.add( readTemps[i] );
422 Set<TempDescriptor> virtualReadTemps = livenessVirtualReads.get( fn );
423 if( virtualReadTemps != null ) {
424 liveIn.addAll( virtualReadTemps );
435 private void variableAnalysisForward( FlatMethod fm ) {
437 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
438 flatNodesToVisit.add( fm );
440 while( !flatNodesToVisit.isEmpty() ) {
441 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
442 flatNodesToVisit.remove( fn );
444 Stack<FlatSESEEnterNode> seseStack = seseStacks.get( fn );
445 assert seseStack != null;
447 VarSrcTokTable prev = variableResults.get( fn );
449 // merge sets from control flow joins
450 VarSrcTokTable curr = new VarSrcTokTable();
451 for( int i = 0; i < fn.numPrev(); i++ ) {
452 FlatNode nn = fn.getPrev( i );
453 VarSrcTokTable incoming = variableResults.get( nn );
454 curr.merge( incoming );
457 if( !seseStack.empty() ) {
458 variable_nodeActions( fn, curr, seseStack.peek() );
461 // if a new result, schedule forward nodes for analysis
462 if( !curr.equals( prev ) ) {
463 variableResults.put( fn, curr );
465 for( int i = 0; i < fn.numNext(); i++ ) {
466 FlatNode nn = fn.getNext( i );
467 flatNodesToVisit.add( nn );
473 private void variable_nodeActions( FlatNode fn,
474 VarSrcTokTable vstTable,
475 FlatSESEEnterNode currentSESE ) {
476 switch( fn.kind() ) {
478 case FKind.FlatSESEEnterNode: {
479 FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
480 assert fsen.equals( currentSESE );
482 vstTable.age( currentSESE );
483 vstTable.assertConsistency();
486 case FKind.FlatSESEExitNode: {
487 FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
488 FlatSESEEnterNode fsen = fsexn.getFlatEnter();
489 assert currentSESE.getChildren().contains( fsen );
491 vstTable.remapChildTokens( fsen );
493 // liveness virtual reads are things that might be
494 // written by an SESE and should be added to the in-set
495 // anything virtually read by this SESE should be pruned
496 // of parent or sibling sources
497 Set<TempDescriptor> liveVars = livenessRootView.get( fn );
498 Set<TempDescriptor> fsenVirtReads = vstTable.calcVirtReadsAndPruneParentAndSiblingTokens( fsen, liveVars );
499 Set<TempDescriptor> fsenVirtReadsOld = livenessVirtualReads.get( fn );
500 if( fsenVirtReadsOld != null ) {
501 fsenVirtReads.addAll( fsenVirtReadsOld );
503 livenessVirtualReads.put( fn, fsenVirtReads );
506 // then all child out-set tokens are guaranteed
507 // to be filled in, so clobber those entries with
508 // the latest, clean sources
509 Iterator<TempDescriptor> outVarItr = fsen.getOutVarSet().iterator();
510 while( outVarItr.hasNext() ) {
511 TempDescriptor outVar = outVarItr.next();
512 HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
514 VariableSourceToken vst =
515 new VariableSourceToken( ts,
520 vstTable.remove( outVar );
523 vstTable.assertConsistency();
527 case FKind.FlatOpNode: {
528 FlatOpNode fon = (FlatOpNode) fn;
530 if( fon.getOp().getOp() == Operation.ASSIGN ) {
531 TempDescriptor lhs = fon.getDest();
532 TempDescriptor rhs = fon.getLeft();
534 vstTable.remove( lhs );
536 Set<VariableSourceToken> forAddition = new HashSet<VariableSourceToken>();
538 Iterator<VariableSourceToken> itr = vstTable.get( rhs ).iterator();
539 while( itr.hasNext() ) {
540 VariableSourceToken vst = itr.next();
542 HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
545 if( currentSESE.getChildren().contains( vst.getSESE() ) ) {
546 // if the source comes from a child, copy it over
547 forAddition.add( new VariableSourceToken( ts,
554 // otherwise, stamp it as us as the source
555 forAddition.add( new VariableSourceToken( ts,
564 vstTable.addAll( forAddition );
566 // only break if this is an ASSIGN op node,
567 // otherwise fall through to default case
568 vstTable.assertConsistency();
573 // note that FlatOpNode's that aren't ASSIGN
574 // fall through to this default case
576 TempDescriptor [] writeTemps = fn.writesTemps();
577 if( writeTemps.length > 0 ) {
580 // for now, when writeTemps > 1, make sure
581 // its a call node, programmer enforce only
582 // doing stuff like calling a print routine
583 //assert writeTemps.length == 1;
584 if( writeTemps.length > 1 ) {
585 assert fn.kind() == FKind.FlatCall ||
586 fn.kind() == FKind.FlatMethod;
590 vstTable.remove( writeTemps[0] );
592 HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
593 ts.add( writeTemps[0] );
595 vstTable.add( new VariableSourceToken( ts,
603 vstTable.assertConsistency();
610 private void pruneVariableResultsWithLiveness( FlatMethod fm ) {
612 // start from flat method top, visit every node in
613 // method exactly once
614 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
615 flatNodesToVisit.add( fm );
617 Set<FlatNode> visited = new HashSet<FlatNode>();
619 while( !flatNodesToVisit.isEmpty() ) {
620 Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
621 FlatNode fn = fnItr.next();
623 flatNodesToVisit.remove( fn );
626 Set<TempDescriptor> rootLiveSet = livenessRootView.get( fn );
627 VarSrcTokTable vstTable = variableResults.get( fn );
629 vstTable.pruneByLiveness( rootLiveSet );
631 for( int i = 0; i < fn.numNext(); i++ ) {
632 FlatNode nn = fn.getNext( i );
634 if( !visited.contains( nn ) ) {
635 flatNodesToVisit.add( nn );
642 private void notAvailableForward( FlatMethod fm ) {
644 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
645 flatNodesToVisit.add( fm );
647 while( !flatNodesToVisit.isEmpty() ) {
648 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
649 flatNodesToVisit.remove( fn );
651 Stack<FlatSESEEnterNode> seseStack = seseStacks.get( fn );
652 assert seseStack != null;
654 Set<TempDescriptor> prev = notAvailableResults.get( fn );
656 Set<TempDescriptor> curr = new HashSet<TempDescriptor>();
657 for( int i = 0; i < fn.numPrev(); i++ ) {
658 FlatNode nn = fn.getPrev( i );
659 Set<TempDescriptor> notAvailIn = notAvailableResults.get( nn );
660 if( notAvailIn != null ) {
661 curr.addAll( notAvailIn );
665 if( !seseStack.empty() ) {
666 notAvailable_nodeActions( fn, curr, seseStack.peek() );
669 // if a new result, schedule forward nodes for analysis
670 if( !curr.equals( prev ) ) {
671 notAvailableResults.put( fn, curr );
673 for( int i = 0; i < fn.numNext(); i++ ) {
674 FlatNode nn = fn.getNext( i );
675 flatNodesToVisit.add( nn );
681 private void notAvailable_nodeActions( FlatNode fn,
682 Set<TempDescriptor> notAvailSet,
683 FlatSESEEnterNode currentSESE ) {
685 // any temps that are removed from the not available set
686 // at this node should be marked in this node's code plan
687 // as temps to be grabbed at runtime!
689 switch( fn.kind() ) {
691 case FKind.FlatSESEEnterNode: {
692 FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
693 assert fsen.equals( currentSESE );
697 case FKind.FlatSESEExitNode: {
698 FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
699 FlatSESEEnterNode fsen = fsexn.getFlatEnter();
700 assert currentSESE.getChildren().contains( fsen );
701 notAvailSet.addAll( fsen.getOutVarSet() );
704 case FKind.FlatMethod: {
708 case FKind.FlatOpNode: {
709 FlatOpNode fon = (FlatOpNode) fn;
711 if( fon.getOp().getOp() == Operation.ASSIGN ) {
712 TempDescriptor lhs = fon.getDest();
713 TempDescriptor rhs = fon.getLeft();
715 // copy makes lhs same availability as rhs
716 if( notAvailSet.contains( rhs ) ) {
717 notAvailSet.add( lhs );
719 notAvailSet.remove( lhs );
722 // only break if this is an ASSIGN op node,
723 // otherwise fall through to default case
728 // note that FlatOpNode's that aren't ASSIGN
729 // fall through to this default case
731 TempDescriptor [] writeTemps = fn.writesTemps();
732 for( int i = 0; i < writeTemps.length; i++ ) {
733 TempDescriptor wTemp = writeTemps[i];
734 notAvailSet.remove( wTemp );
736 TempDescriptor [] readTemps = fn.readsTemps();
737 for( int i = 0; i < readTemps.length; i++ ) {
738 TempDescriptor rTemp = readTemps[i];
739 notAvailSet.remove( rTemp );
741 // if this variable has exactly one source, potentially
742 // get other things from this source as well
743 VarSrcTokTable vstTable = variableResults.get( fn );
746 vstTable.getRefVarSrcType( rTemp,
748 currentSESE.getParent() );
750 if( srcType.equals( VarSrcTokTable.SrcType_STATIC ) ) {
752 VariableSourceToken vst = vstTable.get( rTemp ).iterator().next();
754 Iterator<VariableSourceToken> availItr = vstTable.get( vst.getSESE(),
758 // look through things that are also available from same source
759 while( availItr.hasNext() ) {
760 VariableSourceToken vstAlsoAvail = availItr.next();
762 Iterator<TempDescriptor> refVarItr = vstAlsoAvail.getRefVars().iterator();
763 while( refVarItr.hasNext() ) {
764 TempDescriptor refVarAlso = refVarItr.next();
766 // if a variable is available from the same source, AND it ALSO
767 // only comes from one statically known source, mark it available
768 Integer srcTypeAlso =
769 vstTable.getRefVarSrcType( refVarAlso,
771 currentSESE.getParent() );
772 if( srcTypeAlso.equals( VarSrcTokTable.SrcType_STATIC ) ) {
773 notAvailSet.remove( refVarAlso );
785 private void codePlansForward( FlatMethod fm ) {
787 // start from flat method top, visit every node in
788 // method exactly once
789 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
790 flatNodesToVisit.add( fm );
792 Set<FlatNode> visited = new HashSet<FlatNode>();
794 while( !flatNodesToVisit.isEmpty() ) {
795 Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
796 FlatNode fn = fnItr.next();
798 flatNodesToVisit.remove( fn );
801 Stack<FlatSESEEnterNode> seseStack = seseStacks.get( fn );
802 assert seseStack != null;
804 // use incoming results as "dot statement" or just
805 // before the current statement
806 VarSrcTokTable dotSTtable = new VarSrcTokTable();
807 for( int i = 0; i < fn.numPrev(); i++ ) {
808 FlatNode nn = fn.getPrev( i );
809 dotSTtable.merge( variableResults.get( nn ) );
812 // find dt-st notAvailableSet also
813 Set<TempDescriptor> dotSTnotAvailSet = new HashSet<TempDescriptor>();
814 for( int i = 0; i < fn.numPrev(); i++ ) {
815 FlatNode nn = fn.getPrev( i );
816 Set<TempDescriptor> notAvailIn = notAvailableResults.get( nn );
817 if( notAvailIn != null ) {
818 dotSTnotAvailSet.addAll( notAvailIn );
822 Set<TempDescriptor> dotSTlive = livenessRootView.get( fn );
824 if( !seseStack.empty() ) {
825 codePlans_nodeActions( fn,
833 for( int i = 0; i < fn.numNext(); i++ ) {
834 FlatNode nn = fn.getNext( i );
836 if( !visited.contains( nn ) ) {
837 flatNodesToVisit.add( nn );
843 private void codePlans_nodeActions( FlatNode fn,
844 Set<TempDescriptor> liveSetIn,
845 VarSrcTokTable vstTableIn,
846 Set<TempDescriptor> notAvailSetIn,
847 FlatSESEEnterNode currentSESE ) {
849 CodePlan plan = new CodePlan( currentSESE);
851 switch( fn.kind() ) {
853 case FKind.FlatSESEEnterNode: {
854 FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
856 // track the source types of the in-var set so generated
857 // code at this SESE issue can compute the number of
858 // dependencies properly
859 Iterator<TempDescriptor> inVarItr = fsen.getInVarSet().iterator();
860 while( inVarItr.hasNext() ) {
861 TempDescriptor inVar = inVarItr.next();
863 vstTableIn.getRefVarSrcType( inVar,
867 // the current SESE needs a local space to track the dynamic
868 // variable and the child needs space in its SESE record
869 if( srcType.equals( VarSrcTokTable.SrcType_DYNAMIC ) ) {
870 fsen.addDynamicInVar( inVar );
871 fsen.getParent().addDynamicVar( inVar );
873 } else if( srcType.equals( VarSrcTokTable.SrcType_STATIC ) ) {
874 fsen.addStaticInVar( inVar );
875 VariableSourceToken vst = vstTableIn.get( inVar ).iterator().next();
876 fsen.putStaticInVar2src( inVar, vst );
877 fsen.addStaticInVarSrc( new SESEandAgePair( vst.getSESE(),
883 assert srcType.equals( VarSrcTokTable.SrcType_READY );
884 fsen.addReadyInVar( inVar );
890 case FKind.FlatSESEExitNode: {
891 FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
894 case FKind.FlatOpNode: {
895 FlatOpNode fon = (FlatOpNode) fn;
897 if( fon.getOp().getOp() == Operation.ASSIGN ) {
898 TempDescriptor lhs = fon.getDest();
899 TempDescriptor rhs = fon.getLeft();
901 // if this is an op node, don't stall, copy
902 // source and delay until we need to use value
904 // ask whether lhs and rhs sources are dynamic, static, etc.
906 = vstTableIn.getRefVarSrcType( lhs,
908 currentSESE.getParent() );
911 = vstTableIn.getRefVarSrcType( rhs,
913 currentSESE.getParent() );
915 if( rhsSrcType.equals( VarSrcTokTable.SrcType_DYNAMIC ) ) {
916 // if rhs is dynamic going in, lhs will definitely be dynamic
917 // going out of this node, so track that here
918 plan.addDynAssign( lhs, rhs );
919 currentSESE.addDynamicVar( lhs );
920 currentSESE.addDynamicVar( rhs );
922 } else if( lhsSrcType.equals( VarSrcTokTable.SrcType_DYNAMIC ) ) {
923 // otherwise, if the lhs is dynamic, but the rhs is not, we
924 // need to update the variable's dynamic source as "current SESE"
925 plan.addDynAssign( lhs );
928 // only break if this is an ASSIGN op node,
929 // otherwise fall through to default case
934 // note that FlatOpNode's that aren't ASSIGN
935 // fall through to this default case
938 // a node with no live set has nothing to stall for
939 if( liveSetIn == null ) {
943 TempDescriptor[] readarray = fn.readsTemps();
944 for( int i = 0; i < readarray.length; i++ ) {
945 TempDescriptor readtmp = readarray[i];
947 // ignore temps that are definitely available
948 // when considering to stall on it
949 if( !notAvailSetIn.contains( readtmp ) ) {
953 // check the source type of this variable
955 = vstTableIn.getRefVarSrcType( readtmp,
957 currentSESE.getParent() );
959 if( srcType.equals( VarSrcTokTable.SrcType_DYNAMIC ) ) {
960 // 1) It is not clear statically where this variable will
961 // come from statically, so dynamically we must keep track
962 // along various control paths, and therefore when we stall,
963 // just stall for the exact thing we need and move on
964 plan.addDynamicStall( readtmp );
965 currentSESE.addDynamicVar( readtmp );
967 } else if( srcType.equals( VarSrcTokTable.SrcType_STATIC ) ) {
968 // 2) Single token/age pair: Stall for token/age pair, and copy
969 // all live variables with same token/age pair at the same
970 // time. This is the same stuff that the notavaialable analysis
971 // marks as now available.
973 VariableSourceToken vst = vstTableIn.get( readtmp ).iterator().next();
975 Iterator<VariableSourceToken> availItr =
976 vstTableIn.get( vst.getSESE(), vst.getAge() ).iterator();
978 while( availItr.hasNext() ) {
979 VariableSourceToken vstAlsoAvail = availItr.next();
981 // only grab additional stuff that is live
982 Set<TempDescriptor> copySet = new HashSet<TempDescriptor>();
984 Iterator<TempDescriptor> refVarItr = vstAlsoAvail.getRefVars().iterator();
985 while( refVarItr.hasNext() ) {
986 TempDescriptor refVar = refVarItr.next();
987 if( liveSetIn.contains( refVar ) ) {
988 copySet.add( refVar );
992 if( !copySet.isEmpty() ) {
993 plan.addStall2CopySet( vstAlsoAvail, copySet );
998 // the other case for srcs is READY, so do nothing
1001 // assert that everything being stalled for is in the
1002 // "not available" set coming into this flat node and
1003 // that every VST identified is in the possible "stall set"
1004 // that represents VST's from children SESE's
1012 // identify sese-age pairs that are statically useful
1013 // and should have an associated SESE variable in code
1014 // JUST GET ALL SESE/AGE NAMES FOR NOW, PRUNE LATER,
1015 // AND ALWAYS GIVE NAMES TO PARENTS
1016 Set<VariableSourceToken> staticSet = vstTableIn.get();
1017 Iterator<VariableSourceToken> vstItr = staticSet.iterator();
1018 while( vstItr.hasNext() ) {
1019 VariableSourceToken vst = vstItr.next();
1021 // placeholder source tokens are useful results, but
1022 // the placeholder static name is never needed
1023 if( vst.getSESE().getIsCallerSESEplaceholder() ) {
1027 FlatSESEEnterNode sese = currentSESE;
1028 while( sese != null ) {
1029 sese.addNeededStaticName(
1030 new SESEandAgePair( vst.getSESE(), vst.getAge() )
1032 sese.mustTrackAtLeastAge( vst.getAge() );
1034 sese = sese.getParent();
1039 codePlans.put( fn, plan );
1042 // if any variables at this-node-*dot* have a static source (exactly one vst)
1043 // but go to a dynamic source at next-node-*dot*, create a new IR graph
1044 // node on that edge to track the sources dynamically
1045 VarSrcTokTable thisVstTable = variableResults.get( fn );
1046 for( int i = 0; i < fn.numNext(); i++ ) {
1047 FlatNode nn = fn.getNext( i );
1048 VarSrcTokTable nextVstTable = variableResults.get( nn );
1049 Set<TempDescriptor> nextLiveIn = livenessRootView.get( nn );
1051 // the table can be null if it is one of the few IR nodes
1052 // completely outside of the root SESE scope
1053 if( nextVstTable != null && nextLiveIn != null ) {
1055 Hashtable<TempDescriptor, VariableSourceToken> static2dynamicSet =
1056 thisVstTable.getStatic2DynamicSet( nextVstTable,
1059 currentSESE.getParent()
1062 if( !static2dynamicSet.isEmpty() ) {
1064 // either add these results to partial fixed-point result
1065 // or make a new one if we haven't made any here yet
1066 FlatEdge fe = new FlatEdge( fn, nn );
1067 FlatWriteDynamicVarNode fwdvn = wdvNodesToSpliceIn.get( fe );
1069 if( fwdvn == null ) {
1070 fwdvn = new FlatWriteDynamicVarNode( fn,
1075 wdvNodesToSpliceIn.put( fe, fwdvn );
1077 fwdvn.addMoreVar2Src( static2dynamicSet );
1085 public void writeReports( String timeReport ) throws java.io.IOException {
1087 BufferedWriter bw = new BufferedWriter( new FileWriter( "mlpReport_summary.txt" ) );
1088 bw.write( "MLP Analysis Results\n\n" );
1089 bw.write( timeReport+"\n\n" );
1090 printSESEHierarchy( bw );
1092 printSESEInfo( bw );
1095 Iterator<Descriptor> methItr = ownAnalysis.descriptorsToAnalyze.iterator();
1096 while( methItr.hasNext() ) {
1097 MethodDescriptor md = (MethodDescriptor) methItr.next();
1098 FlatMethod fm = state.getMethodFlat( md );
1099 bw = new BufferedWriter( new FileWriter( "mlpReport_"+
1100 md.getClassMethodName()+
1101 md.getSafeMethodDescriptor()+
1103 bw.write( "MLP Results for "+md+"\n-------------------\n");
1104 bw.write( "\n\nLive-In, Root View\n------------------\n" +fm.printMethod( livenessRootView ) );
1105 bw.write( "\n\nVariable Results-Out\n----------------\n" +fm.printMethod( variableResults ) );
1106 bw.write( "\n\nNot Available Results-Out\n---------------------\n"+fm.printMethod( notAvailableResults ) );
1107 bw.write( "\n\nCode Plans\n----------\n" +fm.printMethod( codePlans ) );
1112 private void printSESEHierarchy( BufferedWriter bw ) throws java.io.IOException {
1113 bw.write( "SESE Hierarchy\n--------------\n" );
1114 Iterator<FlatSESEEnterNode> rootItr = rootSESEs.iterator();
1115 while( rootItr.hasNext() ) {
1116 FlatSESEEnterNode root = rootItr.next();
1117 if( root.getIsCallerSESEplaceholder() ) {
1118 if( !root.getChildren().isEmpty() ) {
1119 printSESEHierarchyTree( bw, root, 0 );
1122 printSESEHierarchyTree( bw, root, 0 );
1127 private void printSESEHierarchyTree( BufferedWriter bw,
1128 FlatSESEEnterNode fsen,
1130 ) throws java.io.IOException {
1131 for( int i = 0; i < depth; ++i ) {
1134 bw.write( "- "+fsen.getPrettyIdentifier()+"\n" );
1136 Iterator<FlatSESEEnterNode> childItr = fsen.getChildren().iterator();
1137 while( childItr.hasNext() ) {
1138 FlatSESEEnterNode fsenChild = childItr.next();
1139 printSESEHierarchyTree( bw, fsenChild, depth + 1 );
1144 private void printSESEInfo( BufferedWriter bw ) throws java.io.IOException {
1145 bw.write("\nSESE info\n-------------\n" );
1146 Iterator<FlatSESEEnterNode> rootItr = rootSESEs.iterator();
1147 while( rootItr.hasNext() ) {
1148 FlatSESEEnterNode root = rootItr.next();
1149 if( root.getIsCallerSESEplaceholder() ) {
1150 if( !root.getChildren().isEmpty() ) {
1151 printSESEInfoTree( bw, root );
1154 printSESEInfoTree( bw, root );
1159 private void printSESEInfoTree( BufferedWriter bw,
1160 FlatSESEEnterNode fsen
1161 ) throws java.io.IOException {
1163 if( !fsen.getIsCallerSESEplaceholder() ) {
1164 bw.write( "SESE "+fsen.getPrettyIdentifier()+" {\n" );
1166 bw.write( " in-set: "+fsen.getInVarSet()+"\n" );
1167 Iterator<TempDescriptor> tItr = fsen.getInVarSet().iterator();
1168 while( tItr.hasNext() ) {
1169 TempDescriptor inVar = tItr.next();
1170 if( fsen.getReadyInVarSet().contains( inVar ) ) {
1171 bw.write( " (ready) "+inVar+"\n" );
1173 if( fsen.getStaticInVarSet().contains( inVar ) ) {
1174 bw.write( " (static) "+inVar+"\n" );
1176 if( fsen.getDynamicInVarSet().contains( inVar ) ) {
1177 bw.write( " (dynamic)"+inVar+"\n" );
1181 bw.write( " out-set: "+fsen.getOutVarSet()+"\n" );
1185 Iterator<FlatSESEEnterNode> childItr = fsen.getChildren().iterator();
1186 while( childItr.hasNext() ) {
1187 FlatSESEEnterNode fsenChild = childItr.next();
1188 printSESEInfoTree( bw, fsenChild );