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 );
150 // 4th pass, compute liveness contribution from
151 // virtual reads discovered in variable pass
152 rootItr = rootSESEs.iterator();
153 while( rootItr.hasNext() ) {
154 FlatSESEEnterNode root = rootItr.next();
155 livenessAnalysisBackward( root,
162 methItr = ownAnalysis.descriptorsToAnalyze.iterator();
163 while( methItr.hasNext() ) {
164 Descriptor d = methItr.next();
165 FlatMethod fm = state.getMethodFlat( d );
167 // prune variable results in one traversal
168 // by removing reference variables that are not live
169 pruneVariableResultsWithLiveness( fm );
174 methItr = ownAnalysis.descriptorsToAnalyze.iterator();
175 while( methItr.hasNext() ) {
176 Descriptor d = methItr.next();
177 FlatMethod fm = state.getMethodFlat( d );
179 // compute what is not available at every program
180 // point, in a forward fixed-point pass
181 notAvailableForward( fm );
186 methItr = ownAnalysis.descriptorsToAnalyze.iterator();
187 while( methItr.hasNext() ) {
188 Descriptor d = methItr.next();
189 FlatMethod fm = state.getMethodFlat( d );
191 // compute a plan for code injections
192 codePlansForward( fm );
196 // splice new IR nodes into graph after all
197 // analysis passes are complete
198 Iterator spliceItr = wdvNodesToSpliceIn.entrySet().iterator();
199 while( spliceItr.hasNext() ) {
200 Map.Entry me = (Map.Entry) spliceItr.next();
201 FlatWriteDynamicVarNode fwdvn = (FlatWriteDynamicVarNode) me.getValue();
202 fwdvn.spliceIntoIR();
206 double timeEndAnalysis = (double) System.nanoTime();
207 double dt = (timeEndAnalysis - timeStartAnalysis)/(Math.pow( 10.0, 9.0 ) );
208 String treport = String.format( "The mlp analysis took %.3f sec.", dt );
209 System.out.println( treport );
211 if( state.MLPDEBUG ) {
213 writeReports( treport );
214 } catch( IOException e ) {}
219 private void buildForestForward( FlatMethod fm ) {
221 // start from flat method top, visit every node in
222 // method exactly once, find SESEs and remember
223 // roots and child relationships
224 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
225 flatNodesToVisit.add( fm );
227 Set<FlatNode> visited = new HashSet<FlatNode>();
229 Stack<FlatSESEEnterNode> seseStackFirst = new Stack<FlatSESEEnterNode>();
230 seseStacks.put( fm, seseStackFirst );
232 while( !flatNodesToVisit.isEmpty() ) {
233 Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
234 FlatNode fn = fnItr.next();
236 Stack<FlatSESEEnterNode> seseStack = seseStacks.get( fn );
237 assert seseStack != null;
239 flatNodesToVisit.remove( fn );
242 buildForest_nodeActions( fn, seseStack, fm );
244 for( int i = 0; i < fn.numNext(); i++ ) {
245 FlatNode nn = fn.getNext( i );
247 if( !visited.contains( nn ) ) {
248 flatNodesToVisit.add( nn );
250 // clone stack and send along each analysis path
251 seseStacks.put( nn, (Stack<FlatSESEEnterNode>)seseStack.clone() );
257 private void buildForest_nodeActions( FlatNode fn,
258 Stack<FlatSESEEnterNode> seseStack,
260 switch( fn.kind() ) {
262 case FKind.FlatSESEEnterNode: {
263 FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
265 if( !fsen.getIsCallerSESEplaceholder() ) {
266 allSESEs.add( fsen );
269 fsen.setfmEnclosing( fm );
270 fsen.setmdEnclosing( fm.getMethod() );
271 fsen.setcdEnclosing( fm.getMethod().getClassDesc() );
273 if( seseStack.empty() ) {
274 rootSESEs.add( fsen );
275 fsen.setParent( null );
277 seseStack.peek().addChild( fsen );
278 fsen.setParent( seseStack.peek() );
281 seseStack.push( fsen );
284 case FKind.FlatSESEExitNode: {
285 FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
286 assert !seseStack.empty();
287 FlatSESEEnterNode fsen = seseStack.pop();
290 case FKind.FlatReturnNode: {
291 FlatReturnNode frn = (FlatReturnNode) fn;
292 if( !seseStack.empty() &&
293 !seseStack.peek().getIsCallerSESEplaceholder()
295 throw new Error( "Error: return statement enclosed within SESE "+
296 seseStack.peek().getPrettyIdentifier() );
304 private void livenessAnalysisBackward( FlatSESEEnterNode fsen,
306 Hashtable< FlatSESEExitNode, Set<TempDescriptor> > liveout ) {
308 // start from an SESE exit, visit nodes in reverse up to
309 // SESE enter in a fixed-point scheme, where children SESEs
310 // should already be analyzed and therefore can be skipped
311 // because child SESE enter node has all necessary info
312 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
315 flatNodesToVisit.add( fsen.getfmEnclosing().getFlatExit() );
317 flatNodesToVisit.add( fsen.getFlatExit() );
320 Hashtable<FlatNode, Set<TempDescriptor>> livenessResults =
321 new Hashtable< FlatNode, Set<TempDescriptor> >();
324 liveout = new Hashtable< FlatSESEExitNode, Set<TempDescriptor> >();
327 while( !flatNodesToVisit.isEmpty() ) {
328 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
329 flatNodesToVisit.remove( fn );
331 Set<TempDescriptor> prev = livenessResults.get( fn );
333 // merge sets from control flow joins
334 Set<TempDescriptor> u = new HashSet<TempDescriptor>();
335 for( int i = 0; i < fn.numNext(); i++ ) {
336 FlatNode nn = fn.getNext( i );
337 Set<TempDescriptor> s = livenessResults.get( nn );
343 Set<TempDescriptor> curr = liveness_nodeActions( fn, u, fsen, toplevel, liveout);
345 // if a new result, schedule backward nodes for analysis
346 if( !curr.equals( prev ) ) {
347 livenessResults.put( fn, curr );
349 // don't flow backwards past current SESE enter
350 if( !fn.equals( fsen ) ) {
351 for( int i = 0; i < fn.numPrev(); i++ ) {
352 FlatNode nn = fn.getPrev( i );
353 flatNodesToVisit.add( nn );
359 Set<TempDescriptor> s = livenessResults.get( fsen );
361 fsen.addInVarSet( s );
364 // remember liveness per node from the root view as the
365 // global liveness of variables for later passes to use
367 livenessRootView.putAll( livenessResults );
370 // post-order traversal, so do children first
371 Iterator<FlatSESEEnterNode> childItr = fsen.getChildren().iterator();
372 while( childItr.hasNext() ) {
373 FlatSESEEnterNode fsenChild = childItr.next();
374 livenessAnalysisBackward( fsenChild, false, liveout );
378 private Set<TempDescriptor> liveness_nodeActions( FlatNode fn,
379 Set<TempDescriptor> liveIn,
380 FlatSESEEnterNode currentSESE,
382 Hashtable< FlatSESEExitNode, Set<TempDescriptor> > liveout
384 switch( fn.kind() ) {
386 case FKind.FlatSESEExitNode:
388 FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
389 if( !liveout.containsKey( fsexn ) ) {
390 liveout.put( fsexn, new HashSet<TempDescriptor>() );
392 liveout.get( fsexn ).addAll( liveIn );
394 // no break, sese exits should also execute default actions
397 // handle effects of statement in reverse, writes then reads
398 TempDescriptor [] writeTemps = fn.writesTemps();
399 for( int i = 0; i < writeTemps.length; ++i ) {
400 liveIn.remove( writeTemps[i] );
403 FlatSESEExitNode fsexn = currentSESE.getFlatExit();
404 Set<TempDescriptor> livetemps = liveout.get( fsexn );
405 if( livetemps != null &&
406 livetemps.contains( writeTemps[i] ) ) {
407 // write to a live out temp...
408 // need to put in SESE liveout set
409 currentSESE.addOutVar( writeTemps[i] );
414 TempDescriptor [] readTemps = fn.readsTemps();
415 for( int i = 0; i < readTemps.length; ++i ) {
416 liveIn.add( readTemps[i] );
419 Set<TempDescriptor> virtualReadTemps = livenessVirtualReads.get( fn );
420 if( virtualReadTemps != null ) {
421 liveIn.addAll( virtualReadTemps );
432 private void variableAnalysisForward( FlatMethod fm ) {
434 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
435 flatNodesToVisit.add( fm );
437 while( !flatNodesToVisit.isEmpty() ) {
438 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
439 flatNodesToVisit.remove( fn );
441 Stack<FlatSESEEnterNode> seseStack = seseStacks.get( fn );
442 assert seseStack != null;
444 VarSrcTokTable prev = variableResults.get( fn );
446 // merge sets from control flow joins
447 VarSrcTokTable curr = new VarSrcTokTable();
448 for( int i = 0; i < fn.numPrev(); i++ ) {
449 FlatNode nn = fn.getPrev( i );
450 VarSrcTokTable incoming = variableResults.get( nn );
451 curr.merge( incoming );
454 if( !seseStack.empty() ) {
455 variable_nodeActions( fn, curr, seseStack.peek() );
458 // if a new result, schedule forward nodes for analysis
459 if( !curr.equals( prev ) ) {
460 variableResults.put( fn, curr );
462 for( int i = 0; i < fn.numNext(); i++ ) {
463 FlatNode nn = fn.getNext( i );
464 flatNodesToVisit.add( nn );
470 private void variable_nodeActions( FlatNode fn,
471 VarSrcTokTable vstTable,
472 FlatSESEEnterNode currentSESE ) {
473 switch( fn.kind() ) {
475 case FKind.FlatSESEEnterNode: {
476 FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
477 assert fsen.equals( currentSESE );
479 vstTable.age( currentSESE );
480 vstTable.assertConsistency();
483 case FKind.FlatSESEExitNode: {
484 FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
485 FlatSESEEnterNode fsen = fsexn.getFlatEnter();
486 assert currentSESE.getChildren().contains( fsen );
488 vstTable.remapChildTokens( fsen );
490 // liveness virtual reads are things that might be
491 // written by an SESE and should be added to the in-set
492 // anything virtually read by this SESE should be pruned
493 // of parent or sibling sources
494 Set<TempDescriptor> liveVars = livenessRootView.get( fn );
495 Set<TempDescriptor> fsenVirtReads = vstTable.calcVirtReadsAndPruneParentAndSiblingTokens( fsen, liveVars );
496 Set<TempDescriptor> fsenVirtReadsOld = livenessVirtualReads.get( fn );
497 if( fsenVirtReadsOld != null ) {
498 fsenVirtReads.addAll( fsenVirtReadsOld );
500 livenessVirtualReads.put( fn, fsenVirtReads );
503 // then all child out-set tokens are guaranteed
504 // to be filled in, so clobber those entries with
505 // the latest, clean sources
506 Iterator<TempDescriptor> outVarItr = fsen.getOutVarSet().iterator();
507 while( outVarItr.hasNext() ) {
508 TempDescriptor outVar = outVarItr.next();
509 HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
511 VariableSourceToken vst =
512 new VariableSourceToken( ts,
517 vstTable.remove( outVar );
520 vstTable.assertConsistency();
524 case FKind.FlatOpNode: {
525 FlatOpNode fon = (FlatOpNode) fn;
527 if( fon.getOp().getOp() == Operation.ASSIGN ) {
528 TempDescriptor lhs = fon.getDest();
529 TempDescriptor rhs = fon.getLeft();
531 vstTable.remove( lhs );
533 Set<VariableSourceToken> forAddition = new HashSet<VariableSourceToken>();
535 Iterator<VariableSourceToken> itr = vstTable.get( rhs ).iterator();
536 while( itr.hasNext() ) {
537 VariableSourceToken vst = itr.next();
539 HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
542 if( currentSESE.getChildren().contains( vst.getSESE() ) ) {
543 // if the source comes from a child, copy it over
544 forAddition.add( new VariableSourceToken( ts,
551 // otherwise, stamp it as us as the source
552 forAddition.add( new VariableSourceToken( ts,
561 vstTable.addAll( forAddition );
563 // only break if this is an ASSIGN op node,
564 // otherwise fall through to default case
565 vstTable.assertConsistency();
570 // note that FlatOpNode's that aren't ASSIGN
571 // fall through to this default case
573 TempDescriptor [] writeTemps = fn.writesTemps();
574 if( writeTemps.length > 0 ) {
577 // for now, when writeTemps > 1, make sure
578 // its a call node, programmer enforce only
579 // doing stuff like calling a print routine
580 //assert writeTemps.length == 1;
581 if( writeTemps.length > 1 ) {
582 assert fn.kind() == FKind.FlatCall ||
583 fn.kind() == FKind.FlatMethod;
587 vstTable.remove( writeTemps[0] );
589 HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
590 ts.add( writeTemps[0] );
592 vstTable.add( new VariableSourceToken( ts,
600 vstTable.assertConsistency();
607 private void pruneVariableResultsWithLiveness( FlatMethod fm ) {
609 // start from flat method top, visit every node in
610 // method exactly once
611 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
612 flatNodesToVisit.add( fm );
614 Set<FlatNode> visited = new HashSet<FlatNode>();
616 while( !flatNodesToVisit.isEmpty() ) {
617 Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
618 FlatNode fn = fnItr.next();
620 flatNodesToVisit.remove( fn );
623 Set<TempDescriptor> rootLiveSet = livenessRootView.get( fn );
624 VarSrcTokTable vstTable = variableResults.get( fn );
626 // fix later, not working, only wanted it to make tables easier to read
627 vstTable.pruneByLiveness( rootLiveSet );
629 for( int i = 0; i < fn.numNext(); i++ ) {
630 FlatNode nn = fn.getNext( i );
632 if( !visited.contains( nn ) ) {
633 flatNodesToVisit.add( nn );
640 private void notAvailableForward( FlatMethod fm ) {
642 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
643 flatNodesToVisit.add( fm );
645 while( !flatNodesToVisit.isEmpty() ) {
646 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
647 flatNodesToVisit.remove( fn );
649 Stack<FlatSESEEnterNode> seseStack = seseStacks.get( fn );
650 assert seseStack != null;
652 Set<TempDescriptor> prev = notAvailableResults.get( fn );
654 Set<TempDescriptor> curr = new HashSet<TempDescriptor>();
655 for( int i = 0; i < fn.numPrev(); i++ ) {
656 FlatNode nn = fn.getPrev( i );
657 Set<TempDescriptor> notAvailIn = notAvailableResults.get( nn );
658 if( notAvailIn != null ) {
659 curr.addAll( notAvailIn );
663 if( !seseStack.empty() ) {
664 notAvailable_nodeActions( fn, curr, seseStack.peek() );
667 // if a new result, schedule forward nodes for analysis
668 if( !curr.equals( prev ) ) {
669 notAvailableResults.put( fn, curr );
671 for( int i = 0; i < fn.numNext(); i++ ) {
672 FlatNode nn = fn.getNext( i );
673 flatNodesToVisit.add( nn );
679 private void notAvailable_nodeActions( FlatNode fn,
680 Set<TempDescriptor> notAvailSet,
681 FlatSESEEnterNode currentSESE ) {
683 // any temps that are removed from the not available set
684 // at this node should be marked in this node's code plan
685 // as temps to be grabbed at runtime!
687 switch( fn.kind() ) {
689 case FKind.FlatSESEEnterNode: {
690 FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
691 assert fsen.equals( currentSESE );
695 case FKind.FlatSESEExitNode: {
696 FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
697 FlatSESEEnterNode fsen = fsexn.getFlatEnter();
698 assert currentSESE.getChildren().contains( fsen );
699 notAvailSet.addAll( fsen.getOutVarSet() );
702 case FKind.FlatMethod: {
706 case FKind.FlatOpNode: {
707 FlatOpNode fon = (FlatOpNode) fn;
709 if( fon.getOp().getOp() == Operation.ASSIGN ) {
710 TempDescriptor lhs = fon.getDest();
711 TempDescriptor rhs = fon.getLeft();
713 // copy makes lhs same availability as rhs
714 if( notAvailSet.contains( rhs ) ) {
715 notAvailSet.add( lhs );
717 notAvailSet.remove( lhs );
720 // only break if this is an ASSIGN op node,
721 // otherwise fall through to default case
726 // note that FlatOpNode's that aren't ASSIGN
727 // fall through to this default case
729 TempDescriptor [] writeTemps = fn.writesTemps();
730 for( int i = 0; i < writeTemps.length; i++ ) {
731 TempDescriptor wTemp = writeTemps[i];
732 notAvailSet.remove( wTemp );
734 TempDescriptor [] readTemps = fn.readsTemps();
735 for( int i = 0; i < readTemps.length; i++ ) {
736 TempDescriptor rTemp = readTemps[i];
737 notAvailSet.remove( rTemp );
739 // if this variable has exactly one source, potentially
740 // get other things from this source as well
741 VarSrcTokTable vstTable = variableResults.get( fn );
744 vstTable.getRefVarSrcType( rTemp,
746 currentSESE.getParent() );
748 if( srcType.equals( VarSrcTokTable.SrcType_STATIC ) ) {
750 VariableSourceToken vst = vstTable.get( rTemp ).iterator().next();
752 Iterator<VariableSourceToken> availItr = vstTable.get( vst.getSESE(),
756 // look through things that are also available from same source
757 while( availItr.hasNext() ) {
758 VariableSourceToken vstAlsoAvail = availItr.next();
760 Iterator<TempDescriptor> refVarItr = vstAlsoAvail.getRefVars().iterator();
761 while( refVarItr.hasNext() ) {
762 TempDescriptor refVarAlso = refVarItr.next();
764 // if a variable is available from the same source, AND it ALSO
765 // only comes from one statically known source, mark it available
766 Integer srcTypeAlso =
767 vstTable.getRefVarSrcType( refVarAlso,
769 currentSESE.getParent() );
770 if( srcTypeAlso.equals( VarSrcTokTable.SrcType_STATIC ) ) {
771 notAvailSet.remove( refVarAlso );
783 private void codePlansForward( FlatMethod fm ) {
785 // start from flat method top, visit every node in
786 // method exactly once
787 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
788 flatNodesToVisit.add( fm );
790 Set<FlatNode> visited = new HashSet<FlatNode>();
792 while( !flatNodesToVisit.isEmpty() ) {
793 Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
794 FlatNode fn = fnItr.next();
796 flatNodesToVisit.remove( fn );
799 Stack<FlatSESEEnterNode> seseStack = seseStacks.get( fn );
800 assert seseStack != null;
802 // use incoming results as "dot statement" or just
803 // before the current statement
804 VarSrcTokTable dotSTtable = new VarSrcTokTable();
805 for( int i = 0; i < fn.numPrev(); i++ ) {
806 FlatNode nn = fn.getPrev( i );
807 dotSTtable.merge( variableResults.get( nn ) );
810 // find dt-st notAvailableSet also
811 Set<TempDescriptor> dotSTnotAvailSet = new HashSet<TempDescriptor>();
812 for( int i = 0; i < fn.numPrev(); i++ ) {
813 FlatNode nn = fn.getPrev( i );
814 Set<TempDescriptor> notAvailIn = notAvailableResults.get( nn );
815 if( notAvailIn != null ) {
816 dotSTnotAvailSet.addAll( notAvailIn );
820 Set<TempDescriptor> dotSTlive = livenessRootView.get( fn );
822 if( !seseStack.empty() ) {
823 codePlans_nodeActions( fn,
831 for( int i = 0; i < fn.numNext(); i++ ) {
832 FlatNode nn = fn.getNext( i );
834 if( !visited.contains( nn ) ) {
835 flatNodesToVisit.add( nn );
841 private void codePlans_nodeActions( FlatNode fn,
842 Set<TempDescriptor> liveSetIn,
843 VarSrcTokTable vstTableIn,
844 Set<TempDescriptor> notAvailSetIn,
845 FlatSESEEnterNode currentSESE ) {
847 CodePlan plan = new CodePlan( currentSESE);
849 switch( fn.kind() ) {
851 case FKind.FlatSESEEnterNode: {
852 FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
854 // track the source types of the in-var set so generated
855 // code at this SESE issue can compute the number of
856 // dependencies properly
857 Iterator<TempDescriptor> inVarItr = fsen.getInVarSet().iterator();
858 while( inVarItr.hasNext() ) {
859 TempDescriptor inVar = inVarItr.next();
861 vstTableIn.getRefVarSrcType( inVar,
865 // the current SESE needs a local space to track the dynamic
866 // variable and the child needs space in its SESE record
867 if( srcType.equals( VarSrcTokTable.SrcType_DYNAMIC ) ) {
868 fsen.addDynamicInVar( inVar );
869 fsen.getParent().addDynamicVar( inVar );
871 } else if( srcType.equals( VarSrcTokTable.SrcType_STATIC ) ) {
872 fsen.addStaticInVar( inVar );
873 VariableSourceToken vst = vstTableIn.get( inVar ).iterator().next();
874 fsen.putStaticInVar2src( inVar, vst );
875 fsen.addStaticInVarSrc( new SESEandAgePair( vst.getSESE(),
881 assert srcType.equals( VarSrcTokTable.SrcType_READY );
882 fsen.addReadyInVar( inVar );
888 case FKind.FlatSESEExitNode: {
889 FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
892 case FKind.FlatOpNode: {
893 FlatOpNode fon = (FlatOpNode) fn;
895 if( fon.getOp().getOp() == Operation.ASSIGN ) {
896 TempDescriptor lhs = fon.getDest();
897 TempDescriptor rhs = fon.getLeft();
899 // if this is an op node, don't stall, copy
900 // source and delay until we need to use value
902 // but check the source type of rhs variable
903 // and if dynamic, lhs becomes dynamic, too,
904 // and we need to keep dynamic sources during
906 = vstTableIn.getRefVarSrcType( rhs,
908 currentSESE.getParent() );
910 if( srcType.equals( VarSrcTokTable.SrcType_DYNAMIC ) ) {
911 plan.addDynAssign( lhs, rhs );
912 currentSESE.addDynamicVar( lhs );
913 currentSESE.addDynamicVar( rhs );
916 // only break if this is an ASSIGN op node,
917 // otherwise fall through to default case
922 // note that FlatOpNode's that aren't ASSIGN
923 // fall through to this default case
926 // a node with no live set has nothing to stall for
927 if( liveSetIn == null ) {
931 TempDescriptor[] readarray = fn.readsTemps();
932 for( int i = 0; i < readarray.length; i++ ) {
933 TempDescriptor readtmp = readarray[i];
935 // ignore temps that are definitely available
936 // when considering to stall on it
937 if( !notAvailSetIn.contains( readtmp ) ) {
941 // check the source type of this variable
943 = vstTableIn.getRefVarSrcType( readtmp,
945 currentSESE.getParent() );
947 if( srcType.equals( VarSrcTokTable.SrcType_DYNAMIC ) ) {
948 // 1) It is not clear statically where this variable will
949 // come from statically, so dynamically we must keep track
950 // along various control paths, and therefore when we stall,
951 // just stall for the exact thing we need and move on
952 plan.addDynamicStall( readtmp );
953 currentSESE.addDynamicVar( readtmp );
955 } else if( srcType.equals( VarSrcTokTable.SrcType_STATIC ) ) {
956 // 2) Single token/age pair: Stall for token/age pair, and copy
957 // all live variables with same token/age pair at the same
958 // time. This is the same stuff that the notavaialable analysis
959 // marks as now available.
961 VariableSourceToken vst = vstTableIn.get( readtmp ).iterator().next();
963 Iterator<VariableSourceToken> availItr =
964 vstTableIn.get( vst.getSESE(), vst.getAge() ).iterator();
966 while( availItr.hasNext() ) {
967 VariableSourceToken vstAlsoAvail = availItr.next();
969 // only grab additional stuff that is live
970 Set<TempDescriptor> copySet = new HashSet<TempDescriptor>();
972 Iterator<TempDescriptor> refVarItr = vstAlsoAvail.getRefVars().iterator();
973 while( refVarItr.hasNext() ) {
974 TempDescriptor refVar = refVarItr.next();
975 if( liveSetIn.contains( refVar ) ) {
976 copySet.add( refVar );
980 if( !copySet.isEmpty() ) {
981 plan.addStall2CopySet( vstAlsoAvail, copySet );
986 // the other case for srcs is READY, so do nothing
989 // assert that everything being stalled for is in the
990 // "not available" set coming into this flat node and
991 // that every VST identified is in the possible "stall set"
992 // that represents VST's from children SESE's
1000 // identify sese-age pairs that are statically useful
1001 // and should have an associated SESE variable in code
1002 // JUST GET ALL SESE/AGE NAMES FOR NOW, PRUNE LATER,
1003 // AND ALWAYS GIVE NAMES TO PARENTS
1004 Set<VariableSourceToken> staticSet = vstTableIn.get();
1005 Iterator<VariableSourceToken> vstItr = staticSet.iterator();
1006 while( vstItr.hasNext() ) {
1007 VariableSourceToken vst = vstItr.next();
1009 // placeholder source tokens are useful results, but
1010 // the placeholder static name is never needed
1011 if( vst.getSESE().getIsCallerSESEplaceholder() ) {
1015 FlatSESEEnterNode sese = currentSESE;
1016 while( sese != null ) {
1017 sese.addNeededStaticName(
1018 new SESEandAgePair( vst.getSESE(), vst.getAge() )
1020 sese.mustTrackAtLeastAge( vst.getAge() );
1022 sese = sese.getParent();
1027 codePlans.put( fn, plan );
1030 // if any variables at this-node-*dot* have a static source (exactly one vst)
1031 // but go to a dynamic source at next-node-*dot*, create a new IR graph
1032 // node on that edge to track the sources dynamically
1033 VarSrcTokTable thisVstTable = variableResults.get( fn );
1034 for( int i = 0; i < fn.numNext(); i++ ) {
1035 FlatNode nn = fn.getNext( i );
1036 VarSrcTokTable nextVstTable = variableResults.get( nn );
1037 Set<TempDescriptor> nextLiveIn = livenessRootView.get( nn );
1039 // the table can be null if it is one of the few IR nodes
1040 // completely outside of the root SESE scope
1041 if( nextVstTable != null && nextLiveIn != null ) {
1043 Hashtable<TempDescriptor, VariableSourceToken> static2dynamicSet =
1044 thisVstTable.getStatic2DynamicSet( nextVstTable,
1047 currentSESE.getParent()
1050 if( !static2dynamicSet.isEmpty() ) {
1052 // either add these results to partial fixed-point result
1053 // or make a new one if we haven't made any here yet
1054 FlatEdge fe = new FlatEdge( fn, nn );
1055 FlatWriteDynamicVarNode fwdvn = wdvNodesToSpliceIn.get( fe );
1057 if( fwdvn == null ) {
1058 fwdvn = new FlatWriteDynamicVarNode( fn,
1063 wdvNodesToSpliceIn.put( fe, fwdvn );
1065 fwdvn.addMoreVar2Src( static2dynamicSet );
1073 public void writeReports( String timeReport ) throws java.io.IOException {
1075 BufferedWriter bw = new BufferedWriter( new FileWriter( "mlpReport_summary.txt" ) );
1076 bw.write( "MLP Analysis Results\n\n" );
1077 bw.write( timeReport+"\n\n" );
1078 printSESEHierarchy( bw );
1080 printSESEInfo( bw );
1083 Iterator<Descriptor> methItr = ownAnalysis.descriptorsToAnalyze.iterator();
1084 while( methItr.hasNext() ) {
1085 MethodDescriptor md = (MethodDescriptor) methItr.next();
1086 FlatMethod fm = state.getMethodFlat( md );
1087 bw = new BufferedWriter( new FileWriter( "mlpReport_"+
1088 md.getClassMethodName()+
1089 md.getSafeMethodDescriptor()+
1091 bw.write( "MLP Results for "+md+"\n-------------------\n");
1092 bw.write( "\n\nLive-In, Root View\n------------------\n" +fm.printMethod( livenessRootView ) );
1093 bw.write( "\n\nVariable Results-Out\n----------------\n" +fm.printMethod( variableResults ) );
1094 bw.write( "\n\nNot Available Results-Out\n---------------------\n"+fm.printMethod( notAvailableResults ) );
1095 bw.write( "\n\nCode Plans\n----------\n" +fm.printMethod( codePlans ) );
1100 private void printSESEHierarchy( BufferedWriter bw ) throws java.io.IOException {
1101 bw.write( "SESE Hierarchy\n--------------\n" );
1102 Iterator<FlatSESEEnterNode> rootItr = rootSESEs.iterator();
1103 while( rootItr.hasNext() ) {
1104 FlatSESEEnterNode root = rootItr.next();
1105 if( root.getIsCallerSESEplaceholder() ) {
1106 if( !root.getChildren().isEmpty() ) {
1107 printSESEHierarchyTree( bw, root, 0 );
1110 printSESEHierarchyTree( bw, root, 0 );
1115 private void printSESEHierarchyTree( BufferedWriter bw,
1116 FlatSESEEnterNode fsen,
1118 ) throws java.io.IOException {
1119 for( int i = 0; i < depth; ++i ) {
1122 bw.write( "- "+fsen.getPrettyIdentifier()+"\n" );
1124 Iterator<FlatSESEEnterNode> childItr = fsen.getChildren().iterator();
1125 while( childItr.hasNext() ) {
1126 FlatSESEEnterNode fsenChild = childItr.next();
1127 printSESEHierarchyTree( bw, fsenChild, depth + 1 );
1132 private void printSESEInfo( BufferedWriter bw ) throws java.io.IOException {
1133 bw.write("\nSESE info\n-------------\n" );
1134 Iterator<FlatSESEEnterNode> rootItr = rootSESEs.iterator();
1135 while( rootItr.hasNext() ) {
1136 FlatSESEEnterNode root = rootItr.next();
1137 if( root.getIsCallerSESEplaceholder() ) {
1138 if( !root.getChildren().isEmpty() ) {
1139 printSESEInfoTree( bw, root );
1142 printSESEInfoTree( bw, root );
1147 private void printSESEInfoTree( BufferedWriter bw,
1148 FlatSESEEnterNode fsen
1149 ) throws java.io.IOException {
1151 if( !fsen.getIsCallerSESEplaceholder() ) {
1152 bw.write( "SESE "+fsen.getPrettyIdentifier()+" {\n" );
1154 bw.write( " in-set: "+fsen.getInVarSet()+"\n" );
1155 Iterator<TempDescriptor> tItr = fsen.getInVarSet().iterator();
1156 while( tItr.hasNext() ) {
1157 TempDescriptor inVar = tItr.next();
1158 if( fsen.getReadyInVarSet().contains( inVar ) ) {
1159 bw.write( " (ready) "+inVar+"\n" );
1161 if( fsen.getStaticInVarSet().contains( inVar ) ) {
1162 bw.write( " (static) "+inVar+"\n" );
1164 if( fsen.getDynamicInVarSet().contains( inVar ) ) {
1165 bw.write( " (dynamic)"+inVar+"\n" );
1169 bw.write( " out-set: "+fsen.getOutVarSet()+"\n" );
1173 Iterator<FlatSESEEnterNode> childItr = fsen.getChildren().iterator();
1174 while( childItr.hasNext() ) {
1175 FlatSESEEnterNode fsenChild = childItr.next();
1176 printSESEInfoTree( bw, fsenChild );