X-Git-Url: http://plrg.eecs.uci.edu/git/?p=IRC.git;a=blobdiff_plain;f=Robust%2Fsrc%2FAnalysis%2FOoOJava%2FOoOJavaAnalysis.java;h=4a5283d57b4a1135d48e4184ff089b5d8089b28a;hp=a68d0cf53667cea08720873e141d02a2e5e5d5f5;hb=4c0d447e6e01694c4bc2aaa7e9edcc6c8d22f109;hpb=2cc492f9fc540cbc306beab14acc3b7f9477b632 diff --git a/Robust/src/Analysis/OoOJava/OoOJavaAnalysis.java b/Robust/src/Analysis/OoOJava/OoOJavaAnalysis.java index a68d0cf5..4a5283d5 100644 --- a/Robust/src/Analysis/OoOJava/OoOJavaAnalysis.java +++ b/Robust/src/Analysis/OoOJava/OoOJavaAnalysis.java @@ -7,6 +7,7 @@ import Analysis.*; import Analysis.CallGraph.*; import Analysis.Disjoint.*; import Analysis.Pointer.*; +import Util.*; import IR.*; import IR.Flat.*; @@ -16,6 +17,7 @@ public class OoOJavaAnalysis { private State state; private TypeUtil typeUtil; private CallGraph callGraph; + private Liveness liveness; private RBlockRelationAnalysis rblockRel; private HeapAnalysis disjointAnalysisTaints; private DisjointAnalysis disjointAnalysisReach; @@ -61,29 +63,29 @@ public class OoOJavaAnalysis { return codePlans.keySet(); } - public ContextTaskNames getContextTaskNames( FlatMethod fm ) { - ContextTaskNames out = fn2contextTaskNames.get( fm ); - if( out == null ) { + public ContextTaskNames getContextTaskNames(FlatMethod fm) { + ContextTaskNames out = fn2contextTaskNames.get(fm); + if (out == null) { out = new ContextTaskNames(); } return out; } - public ContextTaskNames getContextTaskNames( FlatSESEEnterNode fsen ) { - ContextTaskNames out = fn2contextTaskNames.get( fsen ); - if( out == null ) { + public ContextTaskNames getContextTaskNames(FlatSESEEnterNode fsen) { + ContextTaskNames out = fn2contextTaskNames.get(fsen); + if (out == null) { out = new ContextTaskNames(); } return out; } - public FlatMethod getContainingFlatMethod( FlatNode fn ) { - FlatMethod fm = fn2fm.get( fn ); + public FlatMethod getContainingFlatMethod(FlatNode fn) { + FlatMethod fm = fn2fm.get(fn); assert fm != null; return fm; } - public HeapAnalysis getDisjointAnalysis() { + public HeapAnalysis getHeapAnalysis() { return disjointAnalysisTaints; } @@ -91,33 +93,31 @@ public class OoOJavaAnalysis { return buildStateMachines; } - public OoOJavaAnalysis( State state, - TypeUtil typeUtil, - CallGraph callGraph, - Liveness liveness, - ArrayReferencees arrayReferencees ) { + public OoOJavaAnalysis(State state, TypeUtil typeUtil, CallGraph callGraph, Liveness liveness, + ArrayReferencees arrayReferencees) { State.logEvent("Starting OoOJavaAnalysis"); this.state = state; this.typeUtil = typeUtil; this.callGraph = callGraph; + this.liveness = liveness; this.maxSESEage = state.OOO_MAXSESEAGE; - livenessGlobalView = new Hashtable>(); - livenessVirtualReads = new Hashtable>(); - variableResults = new Hashtable(); - notAvailableResults = new Hashtable>(); - codePlans = new Hashtable(); - wdvNodesToSpliceIn = new Hashtable(); - notAvailableIntoSESE = new Hashtable>(); - sese2conflictGraph = new Hashtable(); + livenessGlobalView = new Hashtable>(); + livenessVirtualReads = new Hashtable>(); + variableResults = new Hashtable(); + notAvailableResults = new Hashtable>(); + codePlans = new Hashtable(); + wdvNodesToSpliceIn = new Hashtable(); + notAvailableIntoSESE = new Hashtable>(); + sese2conflictGraph = new Hashtable(); conflictGraph2SESELock = new Hashtable>(); - fn2contextTaskNames = new Hashtable(); - fn2fm = new Hashtable(); + fn2contextTaskNames = new Hashtable(); + fn2fm = new Hashtable(); // state machines support heap examiners with // state transitions to improve precision - if( state.RCR ) { + if (state.RCR) { buildStateMachines = new BuildStateMachines(); } @@ -130,14 +130,13 @@ public class OoOJavaAnalysis { descriptorsToAnalyze.add(mdSourceEntry); - // 0th pass, setup a useful mapping of any flat node to the // flat method it is a part of Iterator methItr = descriptorsToAnalyze.iterator(); while (methItr.hasNext()) { Descriptor d = methItr.next(); - FlatMethod fm = state.getMethodFlat( d ); - buildFlatNodeToFlatMethod( fm ); + FlatMethod fm = state.getMethodFlat(d); + buildFlatNodeToFlatMethod(fm); } State.logEvent("OoOJavaAnalysis Oth pass completed"); @@ -147,14 +146,13 @@ public class OoOJavaAnalysis { State.logEvent("OoOJavaAnalysis 1st pass completed"); - // 2nd pass, liveness, in-set out-set (no virtual reads yet!) - Iterator seseItr = rblockRel.getLocalRootSESEs().iterator(); + // run liveness analysis for each sese blocks + Iterator seseItr = rblockRel.getAllSESEs().iterator(); while (seseItr.hasNext()) { FlatSESEEnterNode sese = seseItr.next(); - livenessAnalysisBackward(sese,liveness); - } - + livenessAnalysisBackward(sese); + } State.logEvent("OoOJavaAnalysis 2nd pass completed"); @@ -162,35 +160,37 @@ public class OoOJavaAnalysis { methItr = rblockRel.getMethodsWithSESEs().iterator(); while (methItr.hasNext()) { Descriptor d = methItr.next(); - FlatMethod fm = state.getMethodFlat(d); - // starting from roots do a forward, fixed-point - // variable analysis for refinement and stalls - variableAnalysisForward(fm); + FlatMethod fm = state.getMethodFlat(d); + // starting from roots do a forward, fixed-point + // variable analysis for refinement and stalls + variableAnalysisForward(fm); } - + State.logEvent("OoOJavaAnalysis 3rd pass completed"); - + // 4th pass, compute liveness contribution from // virtual reads discovered in variable pass seseItr = rblockRel.getLocalRootSESEs().iterator(); while (seseItr.hasNext()) { FlatSESEEnterNode sese = seseItr.next(); - livenessAnalysisBackward(sese,liveness); + livenessAnalysisBackward(sese); } - + State.logEvent("OoOJavaAnalysis 4th pass completed"); // 5th pass, use disjointness with NO FLAGGED REGIONS // to compute taints and effects if (state.POINTER) { - disjointAnalysisTaints = new Pointer(state, typeUtil, callGraph, rblockRel, liveness, buildStateMachines); - ((Pointer)disjointAnalysisTaints).doAnalysis(); - } else disjointAnalysisTaints = - new DisjointAnalysis(state, typeUtil, callGraph, liveness, arrayReferencees, null, - rblockRel, buildStateMachines, - true ); // suppress output--this is an intermediate pass - + new Pointer(state, typeUtil, callGraph, rblockRel, liveness, buildStateMachines); + ((Pointer) disjointAnalysisTaints).doAnalysis(); + } else { + disjointAnalysisTaints = + new DisjointAnalysis(state, typeUtil, callGraph, liveness, arrayReferencees, null, + rblockRel, buildStateMachines, + !state.OOODEBUG // only print out in OoOJava debug mode + ); + } State.logEvent("OoOJavaAnalysis 5th pass completed"); // 6th pass, not available analysis FOR VARIABLES! @@ -206,29 +206,28 @@ public class OoOJavaAnalysis { // 7th pass, start conflict graphs where a parent's graph has a // node for possibly conflicting children and its own stall sites startConflictGraphs(); - State.logEvent("OoOJavaAnalysis 7th pass completed"); + State.logEvent("OoOJavaAnalysis 7th pass completed"); // 8th pass, calculate all possible conflicts without using // reachability info and identify set of FlatNew that next // disjoint reach. analysis should flag Set sitesToFlag = new HashSet(); calculateConflicts(sitesToFlag, false); - State.logEvent("OoOJavaAnalysis 8th pass completed"); + State.logEvent("OoOJavaAnalysis 8th pass completed"); if (!state.RCR) { // 9th pass, ask disjoint analysis to compute reachability // for objects that may cause heap conflicts so the most // efficient method to deal with conflict can be computed - // later + // later disjointAnalysisReach = - new DisjointAnalysis(state, typeUtil, callGraph, liveness, - arrayReferencees, sitesToFlag, - null, // don't do effects analysis again! + new DisjointAnalysis(state, typeUtil, callGraph, liveness, arrayReferencees, sitesToFlag, + null, // don't do effects analysis again! null, // no BuildStateMachines needed - false // don't suppress progress output - ); - State.logEvent("OoOJavaAnalysis 9th pass completed"); + !state.OOODEBUG // only print out in OoOJava debug mode + ); + State.logEvent("OoOJavaAnalysis 9th pass completed"); // 10th pass, calculate conflicts with reachability info calculateConflicts(null, true); - State.logEvent("OoOJavaAnalysis 10th pass completed"); + State.logEvent("OoOJavaAnalysis 10th pass completed"); } else { // in RCR/DFJ we want to do some extra processing on the // state machines before they get handed off to code gen, @@ -236,91 +235,86 @@ public class OoOJavaAnalysis { // to identify heap examiners that are weakly connected, so // accomplish both at the same time pruneMachinesAndFindWeaklyConnectedExaminers(); - State.logEvent("OoOJavaAnalysis RCR pruneMachines pass completed"); + State.logEvent("OoOJavaAnalysis RCR pruneMachines pass completed"); } - // 11th pass, compiling memory Qs! The name "lock" is a legacy + // 11th pass, compiling memory Qs! The name "lock" is a legacy // term for the heap dependence queue, or memQ as the runtime calls it synthesizeLocks(); - State.logEvent("OoOJavaAnalysis 11th pass completed"); + State.logEvent("OoOJavaAnalysis 11th pass completed"); // 12th pass, compute a plan for code injections methItr = descriptorsToAnalyze.iterator(); while (methItr.hasNext()) { Descriptor d = methItr.next(); FlatMethod fm = state.getMethodFlat(d); - codePlansForward(fm,liveness); + codePlansForward(fm); } - State.logEvent("OoOJavaAnalysis 12th pass completed"); + State.logEvent("OoOJavaAnalysis 12th pass completed"); // 13th pass, // splice new IR nodes into graph after all // analysis passes are complete Iterator spliceItr = wdvNodesToSpliceIn.entrySet().iterator(); while (spliceItr.hasNext()) { - Map.Entry me = (Map.Entry) spliceItr.next(); + Map.Entry me = (Map.Entry)spliceItr.next(); FlatWriteDynamicVarNode fwdvn = (FlatWriteDynamicVarNode) me.getValue(); fwdvn.spliceIntoIR(); } - State.logEvent("OoOJavaAnalysis 13th pass completed"); + State.logEvent("OoOJavaAnalysis 13th pass completed"); if (state.OOODEBUG) { try { writeReports(""); - disjointAnalysisTaints.getEffectsAnalysis().writeEffects("effects.txt"); + disjointAnalysisTaints.getEffectsAnalysis().writeEffects("effects.txt"); writeConflictGraph(); - } catch (IOException e) {} + } catch (IOException e) { + } } - State.logEvent("OoOJavaAnalysis completed"); + State.logEvent("OoOJavaAnalysis completed"); } - - private void buildFlatNodeToFlatMethod( FlatMethod fm ) { + private void buildFlatNodeToFlatMethod(FlatMethod fm) { Set flatNodesToVisit = new HashSet(); - flatNodesToVisit.add( fm ); + flatNodesToVisit.add(fm); Set flatNodesVisited = new HashSet(); - while( !flatNodesToVisit.isEmpty() ) { + while (!flatNodesToVisit.isEmpty()) { FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next(); - flatNodesToVisit.remove( fn ); - flatNodesVisited.add( fn ); + flatNodesToVisit.remove(fn); + flatNodesVisited.add(fn); - fn2fm.put( fn, fm ); + fn2fm.put(fn, fm); - for( int i = 0; i < fn.numNext(); i++ ) { - FlatNode nn = fn.getNext( i ); - if( !flatNodesVisited.contains( nn ) ) { - flatNodesToVisit.add( nn ); + for (int i = 0; i < fn.numNext(); i++) { + FlatNode nn = fn.getNext(i); + if (!flatNodesVisited.contains(nn)) { + flatNodesToVisit.add(nn); } } } } - - // debug routine - /* - * Iterator iter = sese2conflictGraph.entrySet().iterator(); while - * (iter.hasNext()) { Entry e = (Entry) iter.next(); FlatNode fn = - * (FlatNode) e.getKey(); ConflictGraph conflictGraph = (ConflictGraph) - * e.getValue(); - * System.out.println("---------------------------------------"); - * System.out.println("CONFLICT GRAPH for " + fn); Set keySet = - * conflictGraph.id2cn.keySet(); for (Iterator iterator = keySet.iterator(); - * iterator.hasNext();) { String key = (String) iterator.next(); - * ConflictNode node = conflictGraph.id2cn.get(key); - * System.out.println("key=" + key + " \n" + node.toStringAllEffects()); } } - */ - - - + // debug routine + /* + * Iterator iter = sese2conflictGraph.entrySet().iterator(); while + * (iter.hasNext()) { Entry e = (Entry) iter.next(); FlatNode fn = (FlatNode) + * e.getKey(); ConflictGraph conflictGraph = (ConflictGraph) e.getValue(); + * System.out.println("---------------------------------------"); + * System.out.println("CONFLICT GRAPH for " + fn); Set keySet = + * conflictGraph.id2cn.keySet(); for (Iterator iterator = keySet.iterator(); + * iterator.hasNext();) { String key = (String) iterator.next(); ConflictNode + * node = conflictGraph.id2cn.get(key); System.out.println("key=" + key + + * " \n" + node.toStringAllEffects()); } } + */ private void writeFile(Set sitesToFlag) { try { BufferedWriter bw = new BufferedWriter(new FileWriter("sitesToFlag.txt")); - for (Iterator iterator = sitesToFlag.iterator(); iterator.hasNext();) { + for (Iterator iterator = sitesToFlag.iterator(); iterator.hasNext(); ) { FlatNew fn = (FlatNew) iterator.next(); bw.write(fn + "\n"); } @@ -332,101 +326,113 @@ public class OoOJavaAnalysis { } - private void livenessAnalysisBackward(FlatSESEEnterNode fsen,Liveness liveness) { + private void livenessAnalysisBackward(FlatSESEEnterNode fsen) { + + // each task maintains a local liveness result + Hashtable> livenessLocalView = + new Hashtable>(); - // flow backward across nodes to compute liveness, and - // take special care with sese enter/exit nodes that - // alter this from normal liveness analysis + // flow backward across nodes to compute liveness. + // it contributes liveness results to the global view + // only if the current flat node belongs directly to the currently analyzing + // sese. Set flatNodesToVisit = new HashSet(); -// flatNodesToVisit.add( fm.getFlatExit() ); flatNodesToVisit.add(fsen.getFlatExit()); - while( !flatNodesToVisit.isEmpty() ) { + while (!flatNodesToVisit.isEmpty()) { FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next(); - flatNodesToVisit.remove( fn ); + flatNodesToVisit.remove(fn); - Set prev = livenessGlobalView.get( fn ); + Set prev = livenessLocalView.get(fn); // merge sets from control flow joins Set livein = new HashSet(); for (int i = 0; i < fn.numNext(); i++) { - FlatNode nn = fn.getNext( i ); - Set s = livenessGlobalView.get( nn ); - if( s != null ) { - livein.addAll( s ); + FlatNode nn = fn.getNext(i); + Set s = livenessLocalView.get(nn); + if (s != null) { + livein.addAll(s); } } - - Set curr = liveness_nodeActions( fn, livein, liveness ); + + Set curr = liveness_nodeActions(fsen, fn, livein); // if a new result, schedule backward nodes for analysis - if( !curr.equals( prev ) ) { + if (!curr.equals(prev)) { - if(fn!=fsen){ - livenessGlobalView.put( fn, curr ); - for( int i = 0; i < fn.numPrev(); i++ ) { - FlatNode nn = fn.getPrev( i ); - flatNodesToVisit.add( nn ); + if (fn != fsen) { + livenessLocalView.put(fn, curr); + + if (rblockRel.getLocalInnerRBlock(fn).equals(fsen)) { + // the current flat node belongs to the currently analyzing sese + // store its liveness in the gloval view + livenessGlobalView.put(fn, curr); } - } + + for (int i = 0; i < fn.numPrev(); i++) { + FlatNode nn = fn.getPrev(i); + flatNodesToVisit.add(nn); + } + } } } } - private Set liveness_nodeActions( FlatNode fn, - Set liveIn, Liveness liveness - ) { - switch( fn.kind() ) { + private Set liveness_nodeActions(FlatSESEEnterNode currSESE, FlatNode fn, + Set liveIn) { + + switch (fn.kind()) { case FKind.FlatSESEEnterNode: { // add whatever is live-in at a task enter to that // task's in-var set - FlatSESEEnterNode fsen = (FlatSESEEnterNode)fn; - if( liveIn != null ) { - fsen.addInVarSet( liveIn ); + FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn; + if (currSESE.equals(fsen)) { + if (liveIn != null) { + fsen.addInVarSet(liveIn); + } + // no break, should also execute default actions } - // no break, should also execute default actions } default: { // handle effects of statement in reverse, writes then reads TempDescriptor[] writeTemps = fn.writesTemps(); - for( int i = 0; i < writeTemps.length; ++i ) { - liveIn.remove( writeTemps[i] ); + for (int i = 0; i < writeTemps.length; ++i) { + liveIn.remove(writeTemps[i]); // if we are analyzing code declared directly in a task, - FlatSESEEnterNode fsen = rblockRel.getLocalInnerRBlock( fn ); - if( fsen != null ) { + FlatSESEEnterNode fsen = rblockRel.getLocalInnerRBlock(fn); + if (fsen != null) { // check to see if we are writing to variables that will // be live-out at the task's exit (and therefore should // go in the task's out-var set) FlatSESEExitNode fsexn = fsen.getFlatExit(); - //note: liveness analysis can have corresponding decisions - Set livetemps= liveness.getLiveInTemps(fsen.getfmEnclosing(), fsexn); -// Set livetemps = livenessGlobalView.get( fsexn ); - if( livetemps != null && livetemps.contains( writeTemps[i] ) ) { - fsen.addOutVar( writeTemps[i] ); - } + // note: liveness analysis can have corresponding decisions + Set livetemps = liveness.getLiveInTemps(fsen.getfmEnclosing(), fsexn); + if (livetemps != null && livetemps.contains(writeTemps[i])) { + fsen.addOutVar(writeTemps[i]); + } } } TempDescriptor[] readTemps = fn.readsTemps(); - for( int i = 0; i < readTemps.length; ++i ) { - liveIn.add( readTemps[i] ); + for (int i = 0; i < readTemps.length; ++i) { + liveIn.add(readTemps[i]); } - Set virtualReadTemps = livenessVirtualReads.get( fn ); - if( virtualReadTemps != null ) { - liveIn.addAll( virtualReadTemps ); - } - } break; + Set virtualReadTemps = livenessVirtualReads.get(fn); + if (virtualReadTemps != null) { + liveIn.addAll(virtualReadTemps); + } + } + break; } // end switch return liveIn; } - private void variableAnalysisForward(FlatMethod fm) { Set flatNodesToVisit = new HashSet(); @@ -446,11 +452,11 @@ public class OoOJavaAnalysis { curr.merge(incoming); } - FlatSESEEnterNode currentSESE = rblockRel.getLocalInnerRBlock( fn ); - if( currentSESE == null ) { + FlatSESEEnterNode currentSESE = rblockRel.getLocalInnerRBlock(fn); + if (currentSESE == null) { currentSESE = rblockRel.getCallerProxySESE(); } - + variable_nodeActions(fn, curr, currentSESE); // if a new result, schedule forward nodes for analysis @@ -465,12 +471,10 @@ public class OoOJavaAnalysis { } } - private void variable_nodeActions(FlatNode fn, - VarSrcTokTable vstTable, + private void variable_nodeActions(FlatNode fn, VarSrcTokTable vstTable, FlatSESEEnterNode currentSESE) { switch (fn.kind()) { - case FKind.FlatSESEEnterNode: { FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn; // ignore currently executing SESE, at this point @@ -478,8 +482,8 @@ public class OoOJavaAnalysis { // the current SESE vstTable.age(fsen); vstTable.assertConsistency(); - } break; - + } + break; case FKind.FlatSESEExitNode: { FlatSESEExitNode fsexn = (FlatSESEExitNode) fn; @@ -495,10 +499,11 @@ public class OoOJavaAnalysis { // written by an SESE and should be added to the in-set // anything virtually read by this SESE should be pruned // of parent or sibling sources + // Set liveVars = liveness.getLiveInTemps(fsen.getfmEnclosing(), fn); Set liveVars = livenessGlobalView.get(fn); + Set fsenVirtReads = - vstTable.calcVirtReadsAndPruneParentAndSiblingTokens(fsen, - liveVars); + vstTable.calcVirtReadsAndPruneParentAndSiblingTokens(fsen, liveVars); Set fsenVirtReadsOld = livenessVirtualReads.get(fn); if (fsenVirtReadsOld != null) { @@ -506,6 +511,9 @@ public class OoOJavaAnalysis { } livenessVirtualReads.put(fn, fsenVirtReads); + // virtual reads are forced in-vars! + fsen.addInVarSet(fsenVirtReads); + // then all child out-set tokens are guaranteed // to be filled in, so clobber those entries with // the latest, clean sources @@ -519,8 +527,8 @@ public class OoOJavaAnalysis { vstTable.add(vst); } vstTable.assertConsistency(); - } break; - + } + break; case FKind.FlatOpNode: { FlatOpNode fon = (FlatOpNode) fn; @@ -542,34 +550,26 @@ public class OoOJavaAnalysis { // when we do x = y for variables, just copy over from a child, // there are two cases: - // 1. if the current task is the caller proxy, any local root is a child - boolean case1 = - currentSESE.getIsCallerProxySESE() && - rblockRel.getLocalRootSESEs().contains( vst.getSESE() ); - - // 2. if the child task is a locally-defined child of the current task - boolean case2 = currentSESE.getLocalChildren().contains( vst.getSESE() ); - - if( case1 || case2 ) { + // 1. if the current task is the caller proxy, any local root is a + // child + boolean case1 = + currentSESE.getIsCallerProxySESE() + && rblockRel.getLocalRootSESEs().contains(vst.getSESE()); + + // 2. if the child task is a locally-defined child of the current task + boolean case2 = currentSESE.getLocalChildren().contains(vst.getSESE()); + + if (case1 || case2) { // if the source comes from a child, copy it over - forAddition.add( new VariableSourceToken( ts, - vst.getSESE(), - vst.getAge(), - vst.getAddrVar() - ) - ); + forAddition.add(new VariableSourceToken(ts, vst.getSESE(), vst.getAge(), vst + .getAddrVar())); } else { // otherwise, stamp it as us as the source - forAddition.add( new VariableSourceToken( ts, - currentSESE, - new Integer( 0 ), - lhs - ) - ); + forAddition.add(new VariableSourceToken(ts, currentSESE, new Integer(0), lhs)); } } - vstTable.addAll( forAddition ); + vstTable.addAll(forAddition); // only break if this is an ASSIGN op node, // otherwise fall through to default case @@ -578,40 +578,35 @@ public class OoOJavaAnalysis { } } - // note that FlatOpNode's that aren't ASSIGN - // fall through to this default case + // note that FlatOpNode's that aren't ASSIGN + // fall through to this default case default: { TempDescriptor[] writeTemps = fn.writesTemps(); - if( writeTemps.length > 0 ) { + if (writeTemps.length > 0) { // for now, when writeTemps > 1, make sure // its a call node, programmer enforce only // doing stuff like calling a print routine - if( writeTemps.length > 1 ) { + if (writeTemps.length > 1) { assert fn.kind() == FKind.FlatCall || fn.kind() == FKind.FlatMethod; break; } - vstTable.remove( writeTemps[0] ); + vstTable.remove(writeTemps[0]); HashSet ts = new HashSet(); - ts.add( writeTemps[0] ); - - vstTable.add( new VariableSourceToken( ts, - currentSESE, - new Integer( 0 ), - writeTemps[0] - ) - ); + ts.add(writeTemps[0]); + + vstTable.add(new VariableSourceToken(ts, currentSESE, new Integer(0), writeTemps[0])); } vstTable.assertConsistency(); - } break; + } + break; } // end switch } - private void notAvailableForward(FlatMethod fm) { Set flatNodesToVisit = new HashSet(); @@ -632,8 +627,8 @@ public class OoOJavaAnalysis { } } - FlatSESEEnterNode currentSESE = rblockRel.getLocalInnerRBlock( fn ); - if( currentSESE == null ) { + FlatSESEEnterNode currentSESE = rblockRel.getLocalInnerRBlock(fn); + if (currentSESE == null) { currentSESE = rblockRel.getCallerProxySESE(); } @@ -651,10 +646,8 @@ public class OoOJavaAnalysis { } } - private void notAvailable_nodeActions(FlatNode fn, - Set notAvailSet, - FlatSESEEnterNode currentSESE - ) { + private void notAvailable_nodeActions(FlatNode fn, Set notAvailSet, + FlatSESEEnterNode currentSESE) { // any temps that are removed from the not available set // at this node should be marked in this node's code plan @@ -675,7 +668,8 @@ public class OoOJavaAnalysis { notAvailableIntoSESE.put(fsen, notAvailCopy); notAvailSet.clear(); - } break; + } + break; case FKind.FlatSESEExitNode: { FlatSESEExitNode fsexn = (FlatSESEExitNode) fn; @@ -686,11 +680,13 @@ public class OoOJavaAnalysis { Set notAvailIn = notAvailableIntoSESE.get(fsen); assert notAvailIn != null; notAvailSet.addAll(notAvailIn); - } break; + } + break; case FKind.FlatMethod: { notAvailSet.clear(); - } break; + } + break; case FKind.FlatOpNode: { FlatOpNode fon = (FlatOpNode) fn; @@ -712,8 +708,8 @@ public class OoOJavaAnalysis { } } - // note that FlatOpNode's that aren't ASSIGN - // fall through to this default case + // note that FlatOpNode's that aren't ASSIGN + // fall through to this default case default: { TempDescriptor[] writeTemps = fn.writesTemps(); for (int i = 0; i < writeTemps.length; i++) { @@ -737,7 +733,7 @@ public class OoOJavaAnalysis { VariableSourceToken vst = vstIfStatic.vst; Iterator availItr = - vstTable.get(vst.getSESE(), vst.getAge()).iterator(); + vstTable.get(vst.getSESE(), vst.getAge()).iterator(); // look through things that are also available from same source while (availItr.hasNext()) { @@ -751,7 +747,7 @@ public class OoOJavaAnalysis { // only comes from one statically known source, mark it available VSTWrapper vstIfStaticNotUsed = new VSTWrapper(); Integer srcTypeAlso = - vstTable.getRefVarSrcType(refVarAlso, currentSESE, vstIfStaticNotUsed); + vstTable.getRefVarSrcType(refVarAlso, currentSESE, vstIfStaticNotUsed); if (srcTypeAlso.equals(VarSrcTokTable.SrcType_STATIC)) { notAvailSet.remove(refVarAlso); } @@ -759,13 +755,13 @@ public class OoOJavaAnalysis { } } } - } break; + } + break; } // end switch } - - private void codePlansForward(FlatMethod fm, Liveness liveness) { + private void codePlansForward(FlatMethod fm) { // start from flat method top, visit every node in // method exactly once @@ -801,14 +797,12 @@ public class OoOJavaAnalysis { Set dotSTlive = livenessGlobalView.get(fn); - FlatSESEEnterNode currentSESE = rblockRel.getLocalInnerRBlock( fn ); - if( currentSESE == null ) { + FlatSESEEnterNode currentSESE = rblockRel.getLocalInnerRBlock(fn); + if (currentSESE == null) { currentSESE = rblockRel.getCallerProxySESE(); } - codePlans_nodeActions(fm, fn, - /*dotSTlive*/liveness, dotSTtable, dotSTnotAvailSet, - currentSESE); + codePlans_nodeActions(fm, fn, dotSTtable, dotSTnotAvailSet, currentSESE); for (int i = 0; i < fn.numNext(); i++) { FlatNode nn = fn.getNext(i); @@ -819,14 +813,9 @@ public class OoOJavaAnalysis { } } } - - private void codePlans_nodeActions(FlatMethod fm, - FlatNode fn, -// Set liveSetIn, - Liveness liveness, - VarSrcTokTable vstTableIn, - Set notAvailSetIn, - FlatSESEEnterNode currentSESE) { + + private void codePlans_nodeActions(FlatMethod fm, FlatNode fn, VarSrcTokTable vstTableIn, + Set notAvailSetIn, FlatSESEEnterNode currentSESE) { CodePlan plan = new CodePlan(currentSESE); @@ -848,11 +837,11 @@ public class OoOJavaAnalysis { // in order to classify in-vars correctly, pass // the parent SESE in--at other FlatNode types just // use the currentSESE - FlatSESEEnterNode parent = rblockRel.getLocalInnerRBlock( fn ); - if( parent == null ) { + FlatSESEEnterNode parent = rblockRel.getLocalInnerRBlock(fn); + if (parent == null) { parent = rblockRel.getCallerProxySESE(); } - + VSTWrapper vstIfStatic = new VSTWrapper(); Integer srcType = vstTableIn.getRefVarSrcType(inVar, parent, vstIfStatic); @@ -860,28 +849,57 @@ public class OoOJavaAnalysis { // variable and the child needs space in its SESE record if (srcType.equals(VarSrcTokTable.SrcType_DYNAMIC)) { fsen.addDynamicInVar(inVar); - addDynamicVar( fsen, fm, inVar ); + addDynamicVar(parent, fm, inVar); } else if (srcType.equals(VarSrcTokTable.SrcType_STATIC)) { fsen.addStaticInVar(inVar); VariableSourceToken vst = vstIfStatic.vst; fsen.putStaticInVar2src(inVar, vst); fsen.addStaticInVarSrc(new SESEandAgePair(vst.getSESE(), vst.getAge())); + } else { assert srcType.equals(VarSrcTokTable.SrcType_READY); fsen.addReadyInVar(inVar); } } - } break; + } + break; case FKind.FlatSESEExitNode: { FlatSESEExitNode fsexn = (FlatSESEExitNode) fn; - //TODO! Shouldn't there be a code plan for task exit - // where the exiting task calculates whether its own - // siblings need variables from its children, so the - // exiter should copy those variables into its own out-set - // and make the available? - } break; + + // Classify the sources of out-set variables so code + // gen can acquire them from children if necessary + // before this task exits + FlatSESEEnterNode exiter = fsexn.getFlatEnter(); + + Iterator outVarItr = exiter.getOutVarSet().iterator(); + while (outVarItr.hasNext()) { + TempDescriptor outVar = outVarItr.next(); + + VSTWrapper vstIfStatic = new VSTWrapper(); + Integer srcType = vstTableIn.getRefVarSrcType(outVar, exiter, vstIfStatic); + + if (srcType.equals(VarSrcTokTable.SrcType_DYNAMIC)) { + // if the out-var is dynamic, put it in the set of dyn out vars + // so exiting code gen knows to look for the value, but also put + // it in the set of dynamic vars the exiter must track! + exiter.addDynamicOutVar(outVar); + addDynamicVar(exiter, fm, outVar); + + } else if (srcType.equals(VarSrcTokTable.SrcType_STATIC)) { + exiter.addStaticOutVar(outVar); + VariableSourceToken vst = vstIfStatic.vst; + exiter.putStaticOutVar2src(outVar, vst); + exiter.addStaticOutVarSrc(new SESEandAgePair(vst.getSESE(), vst.getAge())); + + } else { + assert srcType.equals(VarSrcTokTable.SrcType_READY); + exiter.addReadyOutVar(outVar); + } + } + } + break; case FKind.FlatOpNode: { FlatOpNode fon = (FlatOpNode) fn; @@ -901,9 +919,9 @@ public class OoOJavaAnalysis { if (rhsSrcType.equals(VarSrcTokTable.SrcType_DYNAMIC)) { // if rhs is dynamic going in, lhs will definitely be dynamic // going out of this node, so track that here - plan.addDynAssign( lhs, rhs ); - addDynamicVar( currentSESE, fm, lhs ); - addDynamicVar( currentSESE, fm, rhs ); + plan.addDynAssign(lhs, rhs); + addDynamicVar(currentSESE, fm, lhs); + addDynamicVar(currentSESE, fm, rhs); } else if (lhsSrcType.equals(VarSrcTokTable.SrcType_DYNAMIC)) { // otherwise, if the lhs is dynamic, but the rhs is not, we @@ -917,15 +935,15 @@ public class OoOJavaAnalysis { } } - // note that FlatOpNode's that aren't ASSIGN - // fall through to this default case + // note that FlatOpNode's that aren't ASSIGN + // fall through to this default case default: { // a node with no live set has nothing to stall for // note: no reason to check here, remove this.... -// if (liveSetIn == null) { -// break; -// } + // if (liveSetIn == null) { + // break; + // } TempDescriptor[] readarray = fn.readsTemps(); for (int i = 0; i < readarray.length; i++) { @@ -946,8 +964,8 @@ public class OoOJavaAnalysis { // come from, so dynamically we must keep track // along various control paths, and therefore when we stall, // just stall for the exact thing we need and move on - plan.addDynamicStall( readtmp ); - addDynamicVar( currentSESE, fm, readtmp ); + plan.addDynamicStall(readtmp); + addDynamicVar(currentSESE, fm, readtmp); } else if (srcType.equals(VarSrcTokTable.SrcType_STATIC)) { // 2) Single token/age pair: Stall for token/age pair, and copy @@ -957,7 +975,7 @@ public class OoOJavaAnalysis { VariableSourceToken vst = vstIfStatic.vst; Iterator availItr = - vstTableIn.get(vst.getSESE(), vst.getAge()).iterator(); + vstTableIn.get(vst.getSESE(), vst.getAge()).iterator(); while (availItr.hasNext()) { VariableSourceToken vstAlsoAvail = availItr.next(); @@ -966,16 +984,14 @@ public class OoOJavaAnalysis { Set copySet = new HashSet(); Iterator refVarItr = vstAlsoAvail.getRefVars().iterator(); - + while (refVarItr.hasNext()) { TempDescriptor refVar = refVarItr.next(); - //note: this should just use normal liveness in...only want to copy live variables... -// if (liveSetIn.contains(refVar)) { -// copySet.add(refVar); -// } - if(liveness.getLiveInTemps(fm, fn).contains(refVar)){ - copySet.add(refVar); - } + // note: this should just use normal liveness in...only want to + // copy live variables... + if (liveness.getLiveInTemps(fm, fn).contains(refVar)) { + copySet.add(refVar); + } } if (!copySet.isEmpty()) { @@ -994,7 +1010,7 @@ public class OoOJavaAnalysis { } } - break; + break; } // end switch @@ -1010,16 +1026,16 @@ public class OoOJavaAnalysis { // the caller proxy generates useful analysis facts, but we // never need to generate another name for it in code (it is // ALWAYS the task executing the local method context) - if( vst.getSESE().getIsCallerProxySESE() ) { + if (vst.getSESE().getIsCallerProxySESE()) { continue; } - SESEandAgePair sap = new SESEandAgePair( vst.getSESE(), vst.getAge() ); - sap.getSESE().mustTrackAtLeastAge( sap.getAge() ); + SESEandAgePair sap = new SESEandAgePair(vst.getSESE(), vst.getAge()); + sap.getSESE().mustTrackAtLeastAge(sap.getAge()); FlatSESEEnterNode sese = currentSESE; - while( sese != null ) { - addNeededStaticName( sese, fm, sap ); + while (sese != null) { + addNeededStaticName(sese, fm, sap); sese = sese.getLocalParent(); } } @@ -1030,20 +1046,45 @@ public class OoOJavaAnalysis { // vst) // but go to a dynamic source at next-node-*dot*, create a new IR graph // node on that edge to track the sources dynamically + // NOTE: for this calculation use the currentSESE variable, except when the + // FlatNode fn is an Exit--in that case currentSESE is for the exiting task, + // be we want to consider that the parent is tracking a variable coming out + // of the exiting task + FlatSESEEnterNode fsenDoingTracking; + if (fn instanceof FlatSESEExitNode) { + fsenDoingTracking = currentSESE.getLocalParent(); + + if (fsenDoingTracking == null) { + // if there is no local parent, there are one of two cases + // 1) the current task is main, in which case this FlatNode + // is the main's exit, and doesn't need to do any of the + // following dynamic tracking + // 2) the current task is defined in a method, so use the + // caller proxy in the variable source calcs below + if (currentSESE.equals(rblockRel.getMainSESE())) { + return; + } else { + fsenDoingTracking = rblockRel.getCallerProxySESE(); + } + } + } else { + fsenDoingTracking = currentSESE; + } + VarSrcTokTable thisVstTable = variableResults.get(fn); for (int i = 0; i < fn.numNext(); i++) { FlatNode nn = fn.getNext(i); VarSrcTokTable nextVstTable = variableResults.get(nn); - // note: using the result of liveness analysis regardless of task structures - // Set nextLiveIn = livenessGlobalView.get(nn); - Set nextLiveIn=liveness.getLiveInTemps(fm, nn); + // note: using the result of liveness analysis regardless of task + // structures + Set nextLiveIn = liveness.getLiveInTemps(fm, nn); // the table can be null if it is one of the few IR nodes // completely outside of the root SESE scope if (nextVstTable != null && nextLiveIn != null) { Hashtable readyOrStatic2dynamicSet = - thisVstTable.getReadyOrStatic2DynamicSet(nextVstTable, nextLiveIn, currentSESE); + thisVstTable.getReadyOrStatic2DynamicSet(nextVstTable, nextLiveIn, fsenDoingTracking); if (!readyOrStatic2dynamicSet.isEmpty()) { @@ -1053,7 +1094,8 @@ public class OoOJavaAnalysis { FlatWriteDynamicVarNode fwdvn = wdvNodesToSpliceIn.get(fe); if (fwdvn == null) { - fwdvn = new FlatWriteDynamicVarNode(fn, nn, readyOrStatic2dynamicSet, currentSESE); + fwdvn = + new FlatWriteDynamicVarNode(fn, nn, readyOrStatic2dynamicSet, fsenDoingTracking); wdvNodesToSpliceIn.put(fe, fwdvn); } else { fwdvn.addMoreVar2Src(readyOrStatic2dynamicSet); @@ -1063,39 +1105,36 @@ public class OoOJavaAnalysis { } } - private void addDynamicVar( FlatSESEEnterNode fsen, - FlatMethod fm, - TempDescriptor var ) { + private void addDynamicVar(FlatSESEEnterNode fsen, FlatMethod fm, TempDescriptor var) { FlatNode fnContext; - - // note: dynamic variable declarations are always located in the flat method that encloses task block + + // note: dynamic variable declarations are always located in the flat method + // that encloses task block // there is no need to set fnContext to fsen -// if( fsen.getIsCallerProxySESE() ) { -// // attach the dynamic variable to track to -// // the flat method, so it can be declared at entry -// fnContext = fm; -// } else { -// // otherwise the code context is a task body -// fnContext = fsen; -// } - fnContext=fm; - - ContextTaskNames ctn = fn2contextTaskNames.get( fnContext ); - if( ctn == null ) { + if (fsen.getIsCallerProxySESE()) { + // attach the dynamic variable to track to + // the flat method, so it can be declared at entry + fnContext = fm; + } else { + // otherwise the code context is a task body + fnContext = fsen; + } + // fnContext=fm; + + ContextTaskNames ctn = fn2contextTaskNames.get(fnContext); + if (ctn == null) { ctn = new ContextTaskNames(); } - ctn.addDynamicVar( var ); - fn2contextTaskNames.put( fnContext, ctn ); - + ctn.addDynamicVar(var); + fn2contextTaskNames.put(fnContext, ctn); + } - private void addNeededStaticName( FlatSESEEnterNode fsen, - FlatMethod fm, - SESEandAgePair sap ) { + private void addNeededStaticName(FlatSESEEnterNode fsen, FlatMethod fm, SESEandAgePair sap) { FlatNode fnContext; - if( fsen.getIsCallerProxySESE() ) { + if (fsen.getIsCallerProxySESE()) { // attach the dynamic variable to track to // the flat method, so it can be declared at entry fnContext = fm; @@ -1104,116 +1143,111 @@ public class OoOJavaAnalysis { fnContext = fsen; } - ContextTaskNames ctn = fn2contextTaskNames.get( fnContext ); - if( ctn == null ) { + ContextTaskNames ctn = fn2contextTaskNames.get(fnContext); + if (ctn == null) { ctn = new ContextTaskNames(); } - ctn.addNeededStaticName( sap ); + ctn.addNeededStaticName(sap); - fn2contextTaskNames.put( fnContext, ctn ); + fn2contextTaskNames.put(fnContext, ctn); } - private void startConflictGraphs() { // first, for each task, consider whether it has any children, and if // effects analysis says they should be a conflict node in the that // parent's conflict graph Set allSESEs = rblockRel.getAllSESEs(); - for( Iterator iterator = allSESEs.iterator(); iterator.hasNext(); ) { + for (Iterator iterator = allSESEs.iterator(); iterator.hasNext(); ) { FlatSESEEnterNode parent = (FlatSESEEnterNode) iterator.next(); - if( parent.getIsLeafSESE() ) { + if (parent.getIsLeafSESE()) { continue; } EffectsAnalysis effectsAnalysis = disjointAnalysisTaints.getEffectsAnalysis(); - ConflictGraph conflictGraph = sese2conflictGraph.get( parent ); + ConflictGraph conflictGraph = sese2conflictGraph.get(parent); assert conflictGraph == null; - conflictGraph = new ConflictGraph( state ); + conflictGraph = new ConflictGraph(state); Set children = parent.getChildren(); - for( Iterator iterator2 = children.iterator(); iterator2.hasNext(); ) { + for (Iterator iterator2 = children.iterator(); iterator2.hasNext(); ) { FlatSESEEnterNode child = (FlatSESEEnterNode) iterator2.next(); - Hashtable> taint2Effects = effectsAnalysis.get( child ); - conflictGraph.addLiveIn( taint2Effects ); + Hashtable> taint2Effects = effectsAnalysis.get(child); + conflictGraph.addLiveIn(taint2Effects); } - sese2conflictGraph.put( parent, conflictGraph ); + sese2conflictGraph.put(parent, conflictGraph); } // then traverse all methods looking for potential stall sites, and // add those stall sites as nodes in any task's conflict graph that // might be executing at the point of the stall site Iterator descItr = descriptorsToAnalyze.iterator(); - while( descItr.hasNext() ) { + while (descItr.hasNext()) { MethodDescriptor md = descItr.next(); - FlatMethod fm = state.getMethodFlat( md ); - if( fm != null ) { - addStallSitesToConflictGraphs( fm ); + FlatMethod fm = state.getMethodFlat(md); + if (fm != null) { + addStallSitesToConflictGraphs(fm); } - } + } } - private void addStallSitesToConflictGraphs( FlatMethod fm ) { + private void addStallSitesToConflictGraphs(FlatMethod fm) { Set flatNodesToVisit = new HashSet(); - flatNodesToVisit.add( fm ); + flatNodesToVisit.add(fm); Set visited = new HashSet(); - while( !flatNodesToVisit.isEmpty() ) { + while (!flatNodesToVisit.isEmpty()) { FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next(); - flatNodesToVisit.remove( fn ); - visited.add( fn ); + flatNodesToVisit.remove(fn); + visited.add(fn); - Set currentSESEs = - rblockRel.getPossibleExecutingRBlocks( fn ); + Set currentSESEs = rblockRel.getPossibleExecutingRBlocks(fn); - conflictGraph_nodeAction( fn, currentSESEs ); + conflictGraph_nodeAction(fn, currentSESEs, fm.getMethod().getClassDesc()); // schedule forward nodes for analysis - for( int i = 0; i < fn.numNext(); i++ ) { - FlatNode nn = fn.getNext( i ); - if( !visited.contains( nn ) ) { - flatNodesToVisit.add( nn ); + for (int i = 0; i < fn.numNext(); i++) { + FlatNode nn = fn.getNext(i); + if (!visited.contains(nn)) { + flatNodesToVisit.add(nn); } } } } - private void conflictGraph_nodeAction( FlatNode fn, - Set currentSESEs - ) { + private void conflictGraph_nodeAction(FlatNode fn, Set currentSESEs, + ClassDescriptor cd) { EffectsAnalysis effectsAnalysis = disjointAnalysisTaints.getEffectsAnalysis(); - Hashtable> taint2Effects = effectsAnalysis.get( fn ); - + Hashtable> taint2Effects = effectsAnalysis.get(fn); // repeat the process of adding a stall site to a conflict graph // for each task that might be executing at a possible stall site Iterator seseItr = currentSESEs.iterator(); - while( seseItr.hasNext() ) { + while (seseItr.hasNext()) { FlatSESEEnterNode currentSESE = seseItr.next(); - ConflictGraph conflictGraph = sese2conflictGraph.get( currentSESE ); - if( conflictGraph == null ) { + ConflictGraph conflictGraph = sese2conflictGraph.get(currentSESE); + if (conflictGraph == null) { assert currentSESE.getIsLeafSESE(); continue; } TempDescriptor lhs; TempDescriptor rhs; - - switch( fn.kind() ) { + switch (fn.kind()) { case FKind.FlatFieldNode: case FKind.FlatElementNode: { - if( fn instanceof FlatFieldNode ) { + if (fn instanceof FlatFieldNode) { FlatFieldNode ffn = (FlatFieldNode) fn; rhs = ffn.getSrc(); } else { @@ -1221,14 +1255,14 @@ public class OoOJavaAnalysis { rhs = fen.getSrc(); } - conflictGraph.addStallSite( taint2Effects, rhs ); - } break; - + conflictGraph.addStallSite(taint2Effects, rhs, cd); + } + break; case FKind.FlatSetFieldNode: case FKind.FlatSetElementNode: { - if( fn instanceof FlatSetFieldNode ) { + if (fn instanceof FlatSetFieldNode) { FlatSetFieldNode fsfn = (FlatSetFieldNode) fn; lhs = fsfn.getDst(); rhs = fsfn.getSrc(); @@ -1238,29 +1272,28 @@ public class OoOJavaAnalysis { rhs = fsen.getSrc(); } - conflictGraph.addStallSite( taint2Effects, rhs ); - conflictGraph.addStallSite( taint2Effects, lhs ); - } break; - + conflictGraph.addStallSite(taint2Effects, rhs, cd); + conflictGraph.addStallSite(taint2Effects, lhs, cd); + } + break; case FKind.FlatCall: { FlatCall fc = (FlatCall) fn; lhs = fc.getThis(); - conflictGraph.addStallSite( taint2Effects, lhs ); - } break; + conflictGraph.addStallSite(taint2Effects, lhs, cd); + } + break; } - - if( conflictGraph.id2cn.size() > 0 ) { - sese2conflictGraph.put( currentSESE, conflictGraph ); + + if (conflictGraph.id2cn.size() > 0) { + sese2conflictGraph.put(currentSESE, conflictGraph); } } } - - private void calculateConflicts( Set sitesToFlag, - boolean useReachInfo ) { + private void calculateConflicts(Set sitesToFlag, boolean useReachInfo) { // decide fine-grain edge or coarse-grain edge among all vertexes by // pair-wise comparison @@ -1280,7 +1313,6 @@ public class OoOJavaAnalysis { } } - private void writeConflictGraph() { Enumeration keyEnum = sese2conflictGraph.keys(); while (keyEnum.hasMoreElements()) { @@ -1297,25 +1329,23 @@ public class OoOJavaAnalysis { } } - // the traversal for pruning state machines and finding // machines that are weakly connected BOTH consider conflicting // effects between heap roots, so it is smart to compute all of // this together public void pruneMachinesAndFindWeaklyConnectedExaminers() { - ProcessStateMachines psm=new ProcessStateMachines(buildStateMachines, rblockRel); + ProcessStateMachines psm = new ProcessStateMachines(buildStateMachines, rblockRel); psm.doProcess(); buildStateMachines.writeStateMachines("pruned"); } - - private void synthesizeLocks() { // for every conflict graph, generate a set of memory queues // (called SESELock in this code!) to cover the graph Set> graphEntrySet = sese2conflictGraph.entrySet(); - for (Iterator iterator = graphEntrySet.iterator(); iterator.hasNext();) { - Map.Entry graphEntry = (Map.Entry) iterator.next(); + for (Iterator iterator = graphEntrySet.iterator(); iterator.hasNext(); ) { + Map.Entry graphEntry = + (Map.Entry)iterator.next(); FlatNode sese = graphEntry.getKey(); ConflictGraph conflictGraph = graphEntry.getValue(); calculateCovering(conflictGraph); @@ -1329,7 +1359,7 @@ public class OoOJavaAnalysis { HashSet lockSet = new HashSet(); Set tempCover = conflictGraph.getEdgeSet(); - for (Iterator iterator = tempCover.iterator(); iterator.hasNext();) { + for (Iterator iterator = tempCover.iterator(); iterator.hasNext(); ) { ConflictEdge conflictEdge = (ConflictEdge) iterator.next(); if (conflictEdge.isCoarseEdge()) { coarseToCover.add(conflictEdge); @@ -1353,7 +1383,7 @@ public class OoOJavaAnalysis { changed = false; - for (Iterator iterator = fineToCover.iterator(); iterator.hasNext();) { + for (Iterator iterator = fineToCover.iterator(); iterator.hasNext(); ) { int type; ConflictEdge edge = (ConflictEdge) iterator.next(); @@ -1398,8 +1428,8 @@ public class OoOJavaAnalysis { changed = true; seseLock.addConflictEdge(edge); fineToCover.remove(edge); - break;// exit iterator loop - }// end of initial setup + break; // exit iterator loop + } // end of initial setup ConflictNode newNode; if ((newNode = seseLock.getNewNodeConnectedWithGroup(edge)) != null) { @@ -1434,7 +1464,7 @@ public class OoOJavaAnalysis { seseLock.addEdge(edge); Set edgeSet = newNode.getEdgeSet(); - for (Iterator iterator2 = edgeSet.iterator(); iterator2.hasNext();) { + for (Iterator iterator2 = edgeSet.iterator(); iterator2.hasNext(); ) { ConflictEdge conflictEdge = (ConflictEdge) iterator2.next(); // mark all fine edges between new node and nodes in the group as @@ -1455,16 +1485,16 @@ public class OoOJavaAnalysis { } - break;// exit iterator loop + break; // exit iterator loop } } } while (changed); - HashSet notCovered=new HashSet(); + HashSet notCovered = new HashSet(); do { // coarse changed = false; int type; - for (Iterator iterator = coarseToCover.iterator(); iterator.hasNext();) { + for (Iterator iterator = coarseToCover.iterator(); iterator.hasNext(); ) { ConflictEdge edge = (ConflictEdge) iterator.next(); if (seseLock.getConflictNodeSet().size() == 0) { @@ -1475,18 +1505,18 @@ public class OoOJavaAnalysis { // and it is not parent type = ConflictNode.SCC; } else { - if(state.RCR){ + if (state.RCR) { type = ConflictNode.PARENT_COARSE; - }else{ + } else { type = ConflictNode.PARENT_WRITE; } } seseLock.addConflictNode(edge.getVertexU(), type); } else { if (edge.getVertexU().isStallSiteNode()) { - if(state.RCR){ + if (state.RCR) { type = ConflictNode.PARENT_COARSE; - }else{ + } else { if (edge.getVertexU().getWriteEffectSet().isEmpty()) { type = ConflictNode.PARENT_READ; } else { @@ -1504,18 +1534,18 @@ public class OoOJavaAnalysis { // and it is not parent type = ConflictNode.SCC; } else { - if(state.RCR){ + if (state.RCR) { type = ConflictNode.PARENT_COARSE; - }else{ + } else { type = ConflictNode.PARENT_WRITE; } } seseLock.addConflictNode(edge.getVertexV(), type); } else { if (edge.getVertexV().isStallSiteNode()) { - if(state.RCR){ + if (state.RCR) { type = ConflictNode.PARENT_COARSE; - }else{ + } else { if (edge.getVertexV().getWriteEffectSet().isEmpty()) { type = ConflictNode.PARENT_READ; } else { @@ -1530,15 +1560,15 @@ public class OoOJavaAnalysis { changed = true; coarseToCover.remove(edge); seseLock.addConflictEdge(edge); - break;// exit iterator loop - }// end of initial setup + break; // exit iterator loop + } // end of initial setup ConflictNode newNode; if ((newNode = seseLock.getNewNodeConnectedWithGroup(edge)) != null) { // new node has a coarse-grained edge to all fine-read, fine-write, // parent changed = true; - + if (newNode.isInVarNode() && (!seseLock.hasSelfCoarseEdge(newNode)) && seseLock.hasCoarseEdgeWithParentCoarse(newNode)) { // this case can't be covered by this queue @@ -1552,7 +1582,7 @@ public class OoOJavaAnalysis { coarseToCover.remove(edge); break; } - + if (seseLock.hasSelfCoarseEdge(newNode)) { // SCC if (newNode.isStallSiteNode()) { @@ -1572,7 +1602,7 @@ public class OoOJavaAnalysis { seseLock.addEdge(edge); Set edgeSet = newNode.getEdgeSet(); - for (Iterator iterator2 = edgeSet.iterator(); iterator2.hasNext();) { + for (Iterator iterator2 = edgeSet.iterator(); iterator2.hasNext(); ) { ConflictEdge conflictEdge = (ConflictEdge) iterator2.next(); // mark all coarse edges between new node and nodes in the group // as covered @@ -1591,7 +1621,7 @@ public class OoOJavaAnalysis { } } - break;// exit iterator loop + break; // exit iterator loop } } @@ -1629,11 +1659,10 @@ public class OoOJavaAnalysis { return rblockRel.getCallerProxySESE(); } - public Set getPossibleExecutingRBlocks( FlatNode fn ) { - return rblockRel.getPossibleExecutingRBlocks( fn ); + public Set getPossibleExecutingRBlocks(FlatNode fn) { + return rblockRel.getPossibleExecutingRBlocks(fn); } - public void writeReports(String timeReport) throws java.io.IOException { BufferedWriter bw = new BufferedWriter(new FileWriter("ooojReport_summary.txt")); @@ -1649,17 +1678,18 @@ public class OoOJavaAnalysis { MethodDescriptor md = methItr.next(); FlatMethod fm = state.getMethodFlat(md); if (fm != null) { - bw = new BufferedWriter(new FileWriter("ooojReport_" + - md.getClassMethodName() + - md.getSafeMethodDescriptor() + - ".txt")); + bw = + new BufferedWriter(new FileWriter("ooojReport_" + md.getClassMethodName() + + md.getSafeMethodDescriptor() + ".txt")); bw.write("OoOJava Results for " + md + "\n-------------------\n"); - bw.write("Dynamic vars to manage:\n " + getContextTaskNames( fm ).getDynamicVarSet() ); + bw.write("Dynamic vars to manage:\n " + getContextTaskNames(fm).getDynamicVarSet()); - bw.write("\n\nLive-In, Root View\n------------------\n" + fm.printMethod(livenessGlobalView)); + bw.write("\n\nLive-In, Root View\n------------------\n" + + fm.printMethod(livenessGlobalView)); bw.write("\n\nVariable Results-Out\n----------------\n" + fm.printMethod(variableResults)); - bw.write("\n\nNot Available Results-Out\n---------------------\n" + fm.printMethod(notAvailableResults)); + bw.write("\n\nNot Available Results-Out\n---------------------\n" + + fm.printMethod(notAvailableResults)); bw.write("\n\nCode Plans\n----------\n" + fm.printMethod(codePlans)); bw.close(); } @@ -1671,14 +1701,12 @@ public class OoOJavaAnalysis { Iterator rootItr = rblockRel.getLocalRootSESEs().iterator(); while (rootItr.hasNext()) { FlatSESEEnterNode root = rootItr.next(); - printSESEHierarchyTree(bw, root, 0); + printSESEHierarchyTree(bw, root, 0); } } - private void printSESEHierarchyTree(BufferedWriter bw, - FlatSESEEnterNode fsen, - int depth - ) throws java.io.IOException { + private void printSESEHierarchyTree(BufferedWriter bw, FlatSESEEnterNode fsen, int depth) + throws java.io.IOException { for (int i = 0; i < depth; ++i) { bw.write(" "); } @@ -1694,11 +1722,11 @@ public class OoOJavaAnalysis { private void printSESEInfo(BufferedWriter bw) throws java.io.IOException { bw.write("\nSESE info\n-------------\n"); Iterator fsenItr = rblockRel.getAllSESEs().iterator(); - while( fsenItr.hasNext() ) { + while (fsenItr.hasNext()) { FlatSESEEnterNode fsen = fsenItr.next(); bw.write("SESE " + fsen.getPrettyIdentifier()); - if( fsen.getIsLeafSESE() ) { + if (fsen.getIsLeafSESE()) { bw.write(" (leaf)"); } bw.write(" {\n"); @@ -1718,9 +1746,22 @@ public class OoOJavaAnalysis { } } - bw.write(" Dynamic vars to manage: " + getContextTaskNames( fsen ).getDynamicVarSet() + "\n"); + bw.write(" Dynamic vars to manage: " + getContextTaskNames(fsen).getDynamicVarSet() + "\n"); bw.write(" out-set: " + fsen.getOutVarSet() + "\n"); + tItr = fsen.getOutVarSet().iterator(); + while (tItr.hasNext()) { + TempDescriptor outVar = tItr.next(); + if (fsen.getReadyOutVarSet().contains(outVar)) { + bw.write(" (ready) " + outVar + "\n"); + } + if (fsen.getStaticOutVarSet().contains(outVar)) { + bw.write(" (static) " + outVar + " from " + fsen.getStaticOutVarSrc(outVar) + "\n"); + } + if (fsen.getDynamicOutVarSet().contains(outVar)) { + bw.write(" (dynamic)" + outVar + "\n"); + } + } bw.write(" local parent: " + fsen.getLocalParent() + "\n"); bw.write(" local children: " + fsen.getLocalChildren() + "\n");