From 80d82987862f927ddcc63a4358011c1bcbad49d2 Mon Sep 17 00:00:00 2001 From: yeom Date: Thu, 1 Jul 2010 04:50:00 +0000 Subject: [PATCH] incorporated OoOJava into build code + fixed a couple of small bugs --- Robust/src/Analysis/OoOJava/CodePlan.java | 108 --- .../src/Analysis/OoOJava/ConflictGraph.java | 10 +- Robust/src/Analysis/OoOJava/ConflictNode.java | 4 + .../src/Analysis/OoOJava/OoOJavaAnalysis.java | 417 ++++++++- Robust/src/Analysis/OoOJava/SVKey.java | 50 - Robust/src/Analysis/OoOJava/VSTWrapper.java | 17 - .../src/Analysis/OoOJava/VarSrcTokTable.java | 884 ------------------ .../Analysis/OoOJava/VariableSourceToken.java | 82 -- Robust/src/IR/Flat/BuildCode.java | 759 ++++++++++----- Robust/src/Main/Main.java | 9 +- Robust/src/buildscript | 8 + 11 files changed, 919 insertions(+), 1429 deletions(-) delete mode 100644 Robust/src/Analysis/OoOJava/CodePlan.java delete mode 100644 Robust/src/Analysis/OoOJava/SVKey.java delete mode 100644 Robust/src/Analysis/OoOJava/VSTWrapper.java delete mode 100644 Robust/src/Analysis/OoOJava/VarSrcTokTable.java delete mode 100644 Robust/src/Analysis/OoOJava/VariableSourceToken.java diff --git a/Robust/src/Analysis/OoOJava/CodePlan.java b/Robust/src/Analysis/OoOJava/CodePlan.java deleted file mode 100644 index efb82ca0..00000000 --- a/Robust/src/Analysis/OoOJava/CodePlan.java +++ /dev/null @@ -1,108 +0,0 @@ -package Analysis.OoOJava; - -import IR.*; -import IR.Flat.*; -import java.util.*; -import java.io.*; - - -// a code plan contains information based on analysis results -// for injecting code before and/or after a flat node -public class CodePlan { - - private Hashtable< VariableSourceToken, Set > stall2copySet; - private Set dynamicStallSet; - private Hashtable dynAssign_lhs2rhs; - private Set dynAssign_lhs2curr; - private FlatSESEEnterNode currentSESE; - - public CodePlan( FlatSESEEnterNode fsen ) { - stall2copySet = new Hashtable< VariableSourceToken, Set >(); - dynamicStallSet = new HashSet(); - dynAssign_lhs2rhs = new Hashtable(); - dynAssign_lhs2curr = new HashSet(); - currentSESE = fsen; - } - - public FlatSESEEnterNode getCurrentSESE() { - return currentSESE; - } - - public void addStall2CopySet( VariableSourceToken stallToken, - Set copySet ) { - - if( stall2copySet.containsKey( stallToken ) ) { - Set priorCopySet = stall2copySet.get( stallToken ); - priorCopySet.addAll( copySet ); - } else { - stall2copySet.put( stallToken, copySet ); - } - } - - public Set getStallTokens() { - return stall2copySet.keySet(); - } - - public Set getCopySet( VariableSourceToken stallToken ) { - return stall2copySet.get( stallToken ); - } - - - public void addDynamicStall( TempDescriptor var ) { - dynamicStallSet.add( var ); - } - - public Set getDynamicStallSet() { - return dynamicStallSet; - } - - public void addDynAssign( TempDescriptor lhs, - TempDescriptor rhs ) { - dynAssign_lhs2rhs.put( lhs, rhs ); - } - - public Hashtable getDynAssigns() { - return dynAssign_lhs2rhs; - } - - public void addDynAssign( TempDescriptor lhs ) { - dynAssign_lhs2curr.add( lhs ); - } - - public Set getDynAssignCurr() { - return dynAssign_lhs2curr; - } - - public String toString() { - String s = " PLAN: "; - - if( !stall2copySet.entrySet().isEmpty() ) { - s += "[STATIC STALLS:"; - } - Iterator cpsItr = stall2copySet.entrySet().iterator(); - while( cpsItr.hasNext() ) { - Map.Entry me = (Map.Entry) cpsItr.next(); - VariableSourceToken stallToken = (VariableSourceToken) me.getKey(); - Set copySet = (Set) me.getValue(); - - s += "("+stallToken+"->"+copySet+")"; - } - if( !stall2copySet.entrySet().isEmpty() ) { - s += "]"; - } - - if( !dynamicStallSet.isEmpty() ) { - s += "[DYN STALLS:"+dynamicStallSet+"]"; - } - - if( !dynAssign_lhs2rhs.isEmpty() ) { - s += "[DYN ASSIGNS:"+dynAssign_lhs2rhs+"]"; - } - - if( !dynAssign_lhs2curr.isEmpty() ) { - s += "[DYN ASS2CURR:"+dynAssign_lhs2curr+"]"; - } - - return s; - } -} diff --git a/Robust/src/Analysis/OoOJava/ConflictGraph.java b/Robust/src/Analysis/OoOJava/ConflictGraph.java index f889a799..b34c7aa0 100644 --- a/Robust/src/Analysis/OoOJava/ConflictGraph.java +++ b/Robust/src/Analysis/OoOJava/ConflictGraph.java @@ -184,11 +184,15 @@ public class ConflictGraph { String entryNodeID = entry.getKey(); ConflictNode entryNode = entry.getValue(); + + if(currentNode.isStallSiteNode() && entryNode.isStallSiteNode()){ + continue; + } if ((!currentNode.getID().equals(entryNodeID)) && !(analyzedIDSet.contains(currentNode.getID() + entryNodeID) || analyzedIDSet .contains(entryNodeID + currentNode.getID()))) { - + conflictType = calculateConflictType(currentNode, entryNode, useReachInfo); if (conflictType > ConflictGraph.NON_WRITE_CONFLICT) { addConflictEdge(conflictType, currentNode, entryNode); @@ -448,7 +452,7 @@ public class ConflictGraph { } public SESEWaitingQueue getWaitingElementSetBySESEID(int seseID, - HashSet seseLockSet) { + Set seseLockSet) { HashSet waitingElementSet = new HashSet(); @@ -583,7 +587,7 @@ public class ConflictGraph { } public Set getStallSiteWaitingElementSet(FlatNode stallSite, - HashSet seseLockSet) { + Set seseLockSet) { HashSet waitingElementSet = new HashSet(); Iterator iter = id2cn.entrySet().iterator(); diff --git a/Robust/src/Analysis/OoOJava/ConflictNode.java b/Robust/src/Analysis/OoOJava/ConflictNode.java index 7c7a24f0..69338635 100644 --- a/Robust/src/Analysis/OoOJava/ConflictNode.java +++ b/Robust/src/Analysis/OoOJava/ConflictNode.java @@ -203,4 +203,8 @@ public class ConflictNode { return str; } + public String toString(){ + return id; + } + } diff --git a/Robust/src/Analysis/OoOJava/OoOJavaAnalysis.java b/Robust/src/Analysis/OoOJava/OoOJavaAnalysis.java index e687d61a..0f1016ea 100644 --- a/Robust/src/Analysis/OoOJava/OoOJavaAnalysis.java +++ b/Robust/src/Analysis/OoOJava/OoOJavaAnalysis.java @@ -7,6 +7,7 @@ import java.util.Enumeration; import java.util.HashSet; import java.util.Hashtable; import java.util.Iterator; +import java.util.Map; import java.util.Set; import java.util.Stack; import java.util.Map.Entry; @@ -18,6 +19,11 @@ import Analysis.Disjoint.DisjointAnalysis; import Analysis.Disjoint.Effect; import Analysis.Disjoint.EffectsAnalysis; import Analysis.Disjoint.Taint; +import Analysis.MLP.CodePlan; +import Analysis.MLP.SESEandAgePair; +import Analysis.MLP.VSTWrapper; +import Analysis.MLP.VarSrcTokTable; +import Analysis.MLP.VariableSourceToken; import IR.Descriptor; import IR.MethodDescriptor; import IR.Operation; @@ -25,13 +31,15 @@ import IR.State; import IR.TypeUtil; import IR.Flat.FKind; import IR.Flat.FlatEdge; +import IR.Flat.FlatElementNode; import IR.Flat.FlatFieldNode; import IR.Flat.FlatMethod; +import IR.Flat.FlatNew; import IR.Flat.FlatNode; import IR.Flat.FlatOpNode; -import IR.Flat.FlatNew; import IR.Flat.FlatSESEEnterNode; import IR.Flat.FlatSESEExitNode; +import IR.Flat.FlatSetElementNode; import IR.Flat.FlatSetFieldNode; import IR.Flat.FlatWriteDynamicVarNode; import IR.Flat.TempDescriptor; @@ -64,15 +72,6 @@ public class OoOJavaAnalysis { // mapping of a sese block to its conflict graph private Hashtable sese2conflictGraph; - - - - // private Hashtable conflictsResults; - // private Hashtable methodSummaryResults; - // private OwnershipAnalysis ownAnalysisForSESEConflicts; - - // static private int uniqueLockSetId = 0; - public static int maxSESEage = -1; public int getMaxSESEage() { @@ -116,17 +115,9 @@ public class OoOJavaAnalysis { descriptorsToAnalyze.add(mdSourceEntry); - // conflictsResults = new Hashtable(); - // methodSummaryResults = new Hashtable(); - // conflictGraphResults = new Hashtable(); - - // seseSummaryMap = new Hashtable(); - // isAfterChildSESEIndicatorMap = new Hashtable(); - // conflictGraphLockMap = new Hashtable>(); - - // 1st pass, find basic rblock relations - rblockRel = new RBlockRelationAnalysis(state, typeUtil, callGraph); + // 1st pass, find basic rblock relations & status + rblockRel = new RBlockRelationAnalysis(state, typeUtil, callGraph); rblockStatus = new RBlockStatusAnalysis(state, typeUtil, callGraph, rblockRel); @@ -179,7 +170,7 @@ public class OoOJavaAnalysis { // point, in a forward fixed-point pass notAvailableForward(fm); } - + // 7th pass, make conflict graph // conflict graph is maintained by each parent sese, Iterator descItr=disjointAnalysisTaints.getDescriptorsToAnalyze().iterator(); @@ -191,6 +182,7 @@ public class OoOJavaAnalysis { } // debug routine + /* Iterator iter = sese2conflictGraph.entrySet().iterator(); while (iter.hasNext()) { Entry e = (Entry) iter.next(); @@ -205,6 +197,7 @@ public class OoOJavaAnalysis { System.out.println("key=" + key + " \n" + node.toStringAllEffects()); } } + */ // 8th pass, calculate all possible conflicts without using reachability info // and identify set of FlatNew that next disjoint reach. analysis should flag @@ -225,17 +218,30 @@ public class OoOJavaAnalysis { null, // don't do effects analysis again! null // don't do effects analysis again! ); - //writeConflictGraph(); // 10th pass, calculate conflicts with reachability info - calculateConflicts(null, true); - - /* + calculateConflicts(null, true); + // 11th pass, compiling locks synthesizeLocks(); - - // #th pass, writing conflict graph - writeConflictGraph(); - */ + + // 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 ); + } + + // 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(); + FlatWriteDynamicVarNode fwdvn = (FlatWriteDynamicVarNode) me.getValue(); + fwdvn.spliceIntoIR(); + } + if( state.OOODEBUG ) { try { @@ -682,6 +688,317 @@ public class OoOJavaAnalysis { } // end switch } + +private void codePlansForward( FlatMethod fm ) { + + // start from flat method top, visit every node in + // method exactly once + Set flatNodesToVisit = new HashSet(); + flatNodesToVisit.add( fm ); + + Set visited = new HashSet(); + + while( !flatNodesToVisit.isEmpty() ) { + Iterator fnItr = flatNodesToVisit.iterator(); + FlatNode fn = fnItr.next(); + + flatNodesToVisit.remove( fn ); + visited.add( fn ); + + Stack seseStack = rblockRel.getRBlockStacks(fm, fn); + assert seseStack != null; + + // use incoming results as "dot statement" or just + // before the current statement + VarSrcTokTable dotSTtable = new VarSrcTokTable(); + for( int i = 0; i < fn.numPrev(); i++ ) { + FlatNode nn = fn.getPrev( i ); + dotSTtable.merge( variableResults.get( nn ) ); + } + + // find dt-st notAvailableSet also + Set dotSTnotAvailSet = new HashSet(); + for( int i = 0; i < fn.numPrev(); i++ ) { + FlatNode nn = fn.getPrev( i ); + Set notAvailIn = notAvailableResults.get( nn ); + if( notAvailIn != null ) { + dotSTnotAvailSet.addAll( notAvailIn ); + } + } + + Set dotSTlive = livenessRootView.get( fn ); + + if( !seseStack.empty() ) { + codePlans_nodeActions( fn, + dotSTlive, + dotSTtable, + dotSTnotAvailSet, + seseStack.peek() + ); + } + + for( int i = 0; i < fn.numNext(); i++ ) { + FlatNode nn = fn.getNext( i ); + + if( !visited.contains( nn ) ) { + flatNodesToVisit.add( nn ); + } + } + } + } + + private void codePlans_nodeActions( FlatNode fn, + Set liveSetIn, + VarSrcTokTable vstTableIn, + Set notAvailSetIn, + FlatSESEEnterNode currentSESE ) { + + CodePlan plan = new CodePlan( currentSESE); + + switch( fn.kind() ) { + + case FKind.FlatSESEEnterNode: { + FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn; + assert fsen.equals( currentSESE ); + + // track the source types of the in-var set so generated + // code at this SESE issue can compute the number of + // dependencies properly + Iterator inVarItr = fsen.getInVarSet().iterator(); + while( inVarItr.hasNext() ) { + TempDescriptor inVar = inVarItr.next(); + + // when we get to an SESE enter node we change the + // currentSESE variable of this analysis to the + // child that is declared by the enter node, so + // in order to classify in-vars correctly, pass + // the parent SESE in--at other FlatNode types just + // use the currentSESE + VSTWrapper vstIfStatic = new VSTWrapper(); + Integer srcType = + vstTableIn.getRefVarSrcType( inVar, + fsen.getParent(), + vstIfStatic + ); + + // the current SESE needs a local space to track the dynamic + // variable and the child needs space in its SESE record + if( srcType.equals( VarSrcTokTable.SrcType_DYNAMIC ) ) { + fsen.addDynamicInVar( inVar ); + fsen.getParent().addDynamicVar( 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; + + case FKind.FlatSESEExitNode: { + FlatSESEExitNode fsexn = (FlatSESEExitNode) fn; + } break; + + case FKind.FlatOpNode: { + FlatOpNode fon = (FlatOpNode) fn; + + if( fon.getOp().getOp() == Operation.ASSIGN ) { + TempDescriptor lhs = fon.getDest(); + TempDescriptor rhs = fon.getLeft(); + + // if this is an op node, don't stall, copy + // source and delay until we need to use value + + // ask whether lhs and rhs sources are dynamic, static, etc. + VSTWrapper vstIfStatic = new VSTWrapper(); + Integer lhsSrcType + = vstTableIn.getRefVarSrcType( lhs, + currentSESE, + vstIfStatic + ); + Integer rhsSrcType + = vstTableIn.getRefVarSrcType( rhs, + currentSESE, + vstIfStatic + ); + + 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 ); + currentSESE.addDynamicVar( lhs ); + currentSESE.addDynamicVar( rhs ); + + } else if( lhsSrcType.equals( VarSrcTokTable.SrcType_DYNAMIC ) ) { + // otherwise, if the lhs is dynamic, but the rhs is not, we + // need to update the variable's dynamic source as "current SESE" + plan.addDynAssign( lhs ); + } + + // only break if this is an ASSIGN op node, + // otherwise fall through to default case + break; + } + } + + // 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 + if( liveSetIn == null ) { + break; + } + + TempDescriptor[] readarray = fn.readsTemps(); + for( int i = 0; i < readarray.length; i++ ) { + TempDescriptor readtmp = readarray[i]; + + // ignore temps that are definitely available + // when considering to stall on it + if( !notAvailSetIn.contains( readtmp ) ) { + continue; + } + + // check the source type of this variable + VSTWrapper vstIfStatic = new VSTWrapper(); + Integer srcType + = vstTableIn.getRefVarSrcType( readtmp, + currentSESE, + vstIfStatic + ); + + if( srcType.equals( VarSrcTokTable.SrcType_DYNAMIC ) ) { + // 1) It is not clear statically where this variable will + // 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 ); + currentSESE.addDynamicVar( readtmp ); + + } else if( srcType.equals( VarSrcTokTable.SrcType_STATIC ) ) { + // 2) Single token/age pair: Stall for token/age pair, and copy + // all live variables with same token/age pair at the same + // time. This is the same stuff that the notavaialable analysis + // marks as now available. + VariableSourceToken vst = vstIfStatic.vst; + + Iterator availItr = + vstTableIn.get( vst.getSESE(), vst.getAge() ).iterator(); + + while( availItr.hasNext() ) { + VariableSourceToken vstAlsoAvail = availItr.next(); + + // only grab additional stuff that is live + Set copySet = new HashSet(); + + Iterator refVarItr = vstAlsoAvail.getRefVars().iterator(); + while( refVarItr.hasNext() ) { + TempDescriptor refVar = refVarItr.next(); + if( liveSetIn.contains( refVar ) ) { + copySet.add( refVar ); + } + } + + if( !copySet.isEmpty() ) { + plan.addStall2CopySet( vstAlsoAvail, copySet ); + } + } + + } else { + // the other case for srcs is READY, so do nothing + } + + // assert that everything being stalled for is in the + // "not available" set coming into this flat node and + // that every VST identified is in the possible "stall set" + // that represents VST's from children SESE's + + } + } break; + + } // end switch + + + // identify sese-age pairs that are statically useful + // and should have an associated SESE variable in code + // JUST GET ALL SESE/AGE NAMES FOR NOW, PRUNE LATER, + // AND ALWAYS GIVE NAMES TO PARENTS + Set staticSet = vstTableIn.get(); + Iterator vstItr = staticSet.iterator(); + while( vstItr.hasNext() ) { + VariableSourceToken vst = vstItr.next(); + + // placeholder source tokens are useful results, but + // the placeholder static name is never needed + if( vst.getSESE().getIsCallerSESEplaceholder() ) { + continue; + } + + FlatSESEEnterNode sese = currentSESE; + while( sese != null ) { + sese.addNeededStaticName( + new SESEandAgePair( vst.getSESE(), vst.getAge() ) + ); + sese.mustTrackAtLeastAge( vst.getAge() ); + + sese = sese.getParent(); + } + } + + + codePlans.put( fn, plan ); + + + // if any variables at this-node-*dot* have a static source (exactly one 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 + VarSrcTokTable thisVstTable = variableResults.get( fn ); + for( int i = 0; i < fn.numNext(); i++ ) { + FlatNode nn = fn.getNext( i ); + VarSrcTokTable nextVstTable = variableResults.get( nn ); + Set nextLiveIn = livenessRootView.get( 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 + ); + + if( !readyOrStatic2dynamicSet.isEmpty() ) { + + // either add these results to partial fixed-point result + // or make a new one if we haven't made any here yet + FlatEdge fe = new FlatEdge( fn, nn ); + FlatWriteDynamicVarNode fwdvn = wdvNodesToSpliceIn.get( fe ); + + if( fwdvn == null ) { + fwdvn = new FlatWriteDynamicVarNode( fn, + nn, + readyOrStatic2dynamicSet, + currentSESE + ); + wdvNodesToSpliceIn.put( fe, fwdvn ); + } else { + fwdvn.addMoreVar2Src( readyOrStatic2dynamicSet ); + } + } + } + } + } + private void makeConflictGraph(FlatMethod fm) { Set flatNodesToVisit = new HashSet(); @@ -723,6 +1040,9 @@ public class OoOJavaAnalysis { private void conflictGraph_nodeAction(FlatNode fn, FlatSESEEnterNode currentSESE) { ConflictGraph conflictGraph; + TempDescriptor lhs; + TempDescriptor rhs; + EffectsAnalysis effectsAnalysis = disjointAnalysisTaints.getEffectsAnalysis(); switch (fn.kind()) { @@ -760,8 +1080,13 @@ public class OoOJavaAnalysis { conflictGraph = new ConflictGraph(); } - FlatFieldNode ffn = (FlatFieldNode) fn; - TempDescriptor rhs = ffn.getSrc(); + if( fn instanceof FlatFieldNode){ + FlatFieldNode ffn = (FlatFieldNode)fn; + rhs = ffn.getSrc(); + }else{ + FlatElementNode fen = (FlatElementNode)fn; + rhs = fen.getSrc(); + } // add stall site Hashtable> taint2Effects = effectsAnalysis.get(fn); @@ -781,10 +1106,16 @@ public class OoOJavaAnalysis { conflictGraph = new ConflictGraph(); } - FlatSetFieldNode fsfn = (FlatSetFieldNode) fn; - TempDescriptor lhs = fsfn.getDst(); - TempDescriptor rhs = fsfn.getSrc(); - + if( fn instanceof FlatSetFieldNode){ + FlatSetFieldNode fsfn = (FlatSetFieldNode) fn; + lhs = fsfn.getDst(); + rhs = fsfn.getSrc(); + }else{ + FlatSetElementNode fsen = (FlatSetElementNode) fn; + lhs = fsen.getDst(); + rhs = fsen.getSrc(); + } + // collects effects of stall site and generates stall site node Hashtable> taint2Effects = effectsAnalysis.get(fn); conflictGraph.addStallSite(taint2Effects, rhs); @@ -1085,6 +1416,22 @@ public class OoOJavaAnalysis { conflictGraph2SESELock.put(conflictGraph, lockSet); } + public ConflictGraph getConflictGraph(FlatNode sese){ + return sese2conflictGraph.get(sese); + } + + public Set getLockMappings(ConflictGraph graph){ + return conflictGraph2SESELock.get(graph); + } + + public Set getAllSESEs() { + return rblockRel.getAllSESEs(); + } + + public FlatSESEEnterNode getMainSESE() { + return rblockRel.getMainSESE(); + } + public void writeReports( String timeReport ) throws java.io.IOException { BufferedWriter bw = new BufferedWriter( new FileWriter( "mlpReport_summary.txt" ) ); diff --git a/Robust/src/Analysis/OoOJava/SVKey.java b/Robust/src/Analysis/OoOJava/SVKey.java deleted file mode 100644 index e98ff31e..00000000 --- a/Robust/src/Analysis/OoOJava/SVKey.java +++ /dev/null @@ -1,50 +0,0 @@ -package Analysis.OoOJava; - -import IR.*; -import IR.Flat.*; -import java.util.*; -import java.io.*; - -public class SVKey { - - private FlatSESEEnterNode sese; - private TempDescriptor var; - - public SVKey( FlatSESEEnterNode sese, - TempDescriptor var ) { - this.sese = sese; - this.var = var; - } - - public FlatSESEEnterNode getSESE() { - return sese; - } - - public TempDescriptor getVar() { - return var; - } - - public boolean equals( Object o ) { - if( o == null ) { - return false; - } - - if( !(o instanceof SVKey) ) { - return false; - } - - SVKey k = (SVKey) o; - - return var.equals( k.var ) && - sese.equals( k.sese ); - } - - public int hashCode() { - return (sese.hashCode() << 2)*(var.hashCode() << 5); - } - - - public String toString() { - return "key["+sese.getPrettyIdentifier()+", "+var+"]"; - } -} diff --git a/Robust/src/Analysis/OoOJava/VSTWrapper.java b/Robust/src/Analysis/OoOJava/VSTWrapper.java deleted file mode 100644 index 6f17610a..00000000 --- a/Robust/src/Analysis/OoOJava/VSTWrapper.java +++ /dev/null @@ -1,17 +0,0 @@ -package Analysis.OoOJava; - -import IR.*; -import IR.Flat.*; -import java.util.*; -import java.io.*; - -// the reason for this class is to allow a VariableSourceToken -// to be null in some circumstances - -public class VSTWrapper { - public VariableSourceToken vst; - - public VSTWrapper() { - vst = null; - } -} diff --git a/Robust/src/Analysis/OoOJava/VarSrcTokTable.java b/Robust/src/Analysis/OoOJava/VarSrcTokTable.java deleted file mode 100644 index 782d45e0..00000000 --- a/Robust/src/Analysis/OoOJava/VarSrcTokTable.java +++ /dev/null @@ -1,884 +0,0 @@ -package Analysis.OoOJava; - -import IR.*; -import IR.Flat.*; -import java.util.*; -import java.io.*; - -// This class formerly had lazy consistency properties, but -// it is being changed so that the full set and the extra -// hash tables to access the full set efficiently by different -// elements will be consistent after EVERY operation. Also, -// a consistent assert method allows a debugger to ask whether -// an operation has produced an inconsistent VarSrcTokTable. - -// in an effort to make sure operations keep the table consistent, -// all public methods that are also used by other methods for -// intermediate results (add and remove are used in other methods) -// there should be a public version that calls the private version -// so consistency is checked after public ops, but not private ops -public class VarSrcTokTable { - - // a set of every token in the table - private HashSet trueSet; - - // these hashtables provide an efficient retreival from the true set - private Hashtable< TempDescriptor, Set > var2vst; - private Hashtable< FlatSESEEnterNode, Set > sese2vst; - private Hashtable< SVKey, Set > sv2vst; - - // maximum age from aging operation - private static final Integer MAX_AGE = new Integer( 2 ); - - public static final Integer SrcType_READY = new Integer( 34 ); - public static final Integer SrcType_STATIC = new Integer( 35 ); - public static final Integer SrcType_DYNAMIC = new Integer( 36 ); - - - public VarSrcTokTable() { - trueSet = new HashSet(); - - sese2vst = new Hashtable< FlatSESEEnterNode, Set >(); - var2vst = new Hashtable< TempDescriptor, Set >(); - sv2vst = new Hashtable< SVKey, Set >(); - - assertConsistency(); - } - - - // make a deep copy of the in table - public VarSrcTokTable( VarSrcTokTable in ) { - this(); - merge( in ); - assertConsistency(); - } - - - public void add( VariableSourceToken vst ) { - addPrivate( vst ); - assertConsistency(); - } - - private void addPrivate( VariableSourceToken vst ) { - - // make sure we aren't clobbering anything! - if( trueSet.contains( vst ) ) { - // if something with the same hashcode is in the true set, they might - // have different reference variable sets because that set is not considered - // in a token's equality, so make sure we smooth that out right here - Iterator vstItr = trueSet.iterator(); - while( vstItr.hasNext() ) { - VariableSourceToken vstAlready = vstItr.next(); - - if( vstAlready.equals( vst ) ) { - - // take out the one that is in (we dont' want collisions in - // any of the other hash map sets either) - removePrivate( vstAlready ); - - // combine reference variable sets - vst.getRefVars().addAll( vstAlready.getRefVars() ); - - // now jump back as we are adding in a brand new token - break; - } - } - } - - trueSet.add( vst ); - - Set s; - - s = sese2vst.get( vst.getSESE() ); - if( s == null ) { - s = new HashSet(); - } - s.add( vst ); - sese2vst.put( vst.getSESE(), s ); - - Iterator refVarItr = vst.getRefVars().iterator(); - while( refVarItr.hasNext() ) { - TempDescriptor refVar = refVarItr.next(); - s = var2vst.get( refVar ); - if( s == null ) { - s = new HashSet(); - } - s.add( vst ); - var2vst.put( refVar, s ); - - SVKey key = new SVKey( vst.getSESE(), refVar ); - s = sv2vst.get( key ); - if( s == null ) { - s = new HashSet(); - } - s.add( vst ); - sv2vst.put( key, s ); - } - } - - public void addAll( Set s ) { - Iterator itr = s.iterator(); - while( itr.hasNext() ) { - addPrivate( itr.next() ); - } - assertConsistency(); - } - - - public Set get() { - return trueSet; - } - - public Set get( FlatSESEEnterNode sese ) { - Set s = sese2vst.get( sese ); - if( s == null ) { - s = new HashSet(); - sese2vst.put( sese, s ); - } - return s; - } - - public Set get( TempDescriptor refVar ) { - Set s = var2vst.get( refVar ); - if( s == null ) { - s = new HashSet(); - var2vst.put( refVar, s ); - } - return s; - } - - public Set get( FlatSESEEnterNode sese, - TempDescriptor refVar ) { - SVKey key = new SVKey( sese, refVar ); - Set s = sv2vst.get( key ); - if( s == null ) { - s = new HashSet(); - sv2vst.put( key, s ); - } - return s; - } - - public Set get( FlatSESEEnterNode sese, - Integer age ) { - - HashSet s0 = (HashSet) sese2vst.get( sese ); - if( s0 == null ) { - s0 = new HashSet(); - sese2vst.put( sese, s0 ); - } - - Set s = (Set) s0.clone(); - Iterator sItr = s.iterator(); - while( sItr.hasNext() ) { - VariableSourceToken vst = sItr.next(); - if( !vst.getAge().equals( age ) ) { - s.remove( vst ); - } - } - - return s; - } - - - // merge now makes a deep copy of incoming stuff because tokens may - // be modified (reference var sets) by later ops that change more - // than one table, causing inconsistency - public void merge( VarSrcTokTable in ) { - - if( in == null ) { - return; - } - - Iterator vstItr = in.trueSet.iterator(); - while( vstItr.hasNext() ) { - VariableSourceToken vst = vstItr.next(); - this.addPrivate( vst.copy() ); - } - - assertConsistency(); - } - - - // remove operations must leave the trueSet - // and the hash maps consistent - public void remove( VariableSourceToken vst ) { - removePrivate( vst ); - assertConsistency(); - } - - private void removePrivate( VariableSourceToken vst ) { - trueSet.remove( vst ); - - Set s; - - s = get( vst.getSESE() ); - if( s != null ) { s.remove( vst ); } - - Iterator refVarItr = vst.getRefVars().iterator(); - while( refVarItr.hasNext() ) { - TempDescriptor refVar = refVarItr.next(); - - s = get( refVar ); - if( s != null ) { - s.remove( vst ); - if( s.isEmpty() ) { - var2vst.remove( refVar ); - } - } - - s = get( vst.getSESE(), refVar ); - if( s != null ) { - s.remove( vst ); - if( s.isEmpty() ) { - sv2vst.remove( new SVKey( vst.getSESE(), refVar ) ); - } - } - } - } - - - public void remove( FlatSESEEnterNode sese ) { - removePrivate( sese ); - assertConsistency(); - } - - public void removePrivate( FlatSESEEnterNode sese ) { - Set s = sese2vst.get( sese ); - if( s == null ) { - return; - } - - Iterator itr = s.iterator(); - while( itr.hasNext() ) { - VariableSourceToken vst = itr.next(); - removePrivate( vst ); - } - - sese2vst.remove( sese ); - } - - - public void remove( TempDescriptor refVar ) { - removePrivate( refVar ); - assertConsistency(); - } - - private void removePrivate( TempDescriptor refVar ) { - Set s = var2vst.get( refVar ); - if( s == null ) { - return; - } - - Set forRemoval = new HashSet(); - - // iterate over tokens that this temp can reference, make a set - // of tokens that need this temp stripped out of them - Iterator itr = s.iterator(); - while( itr.hasNext() ) { - VariableSourceToken vst = itr.next(); - Set refVars = vst.getRefVars(); - assert refVars.contains( refVar ); - forRemoval.add( vst ); - } - - itr = forRemoval.iterator(); - while( itr.hasNext() ) { - - // here's a token marked for removal - VariableSourceToken vst = itr.next(); - Set refVars = vst.getRefVars(); - - // if there was only one one variable - // referencing this token, just take it - // out of the table all together - if( refVars.size() == 1 ) { - removePrivate( vst ); - } - - sv2vst.remove( new SVKey( vst.getSESE(), refVar ) ); - - refVars.remove( refVar ); - } - - var2vst.remove( refVar ); - } - - - public void remove( FlatSESEEnterNode sese, - TempDescriptor var ) { - - // don't seem to need this, don't bother maintaining - // until its clear we need it - assert false; - } - - - // age tokens with respect to SESE curr, where - // any curr tokens increase age by 1 - public void age( FlatSESEEnterNode curr ) { - - Set forRemoval = - new HashSet(); - - Set forAddition = - new HashSet(); - - Iterator itr = trueSet.iterator(); - while( itr.hasNext() ) { - VariableSourceToken vst = itr.next(); - - if( vst.getSESE().equals( curr ) ) { - - // only age if the token isn't already the maximum age - if( vst.getAge() < MAX_AGE ) { - - forRemoval.add( vst ); - - forAddition.add( new VariableSourceToken( vst.getRefVars(), - curr, - vst.getAge() + 1, - vst.getAddrVar() - ) - ); - } - } - } - - itr = forRemoval.iterator(); - while( itr.hasNext() ) { - VariableSourceToken vst = itr.next(); - remove( vst ); - } - - itr = forRemoval.iterator(); - while( itr.hasNext() ) { - VariableSourceToken vst = itr.next(); - add( vst ); - } - - assertConsistency(); - } - - - // at an SESE enter node, all ref vars in the SESE's in-set will - // be copied into the SESE's local scope, change source to itself - public void ownInSet( FlatSESEEnterNode curr ) { - Iterator inVarItr = curr.getInVarSet().iterator(); - while( inVarItr.hasNext() ) { - TempDescriptor inVar = inVarItr.next(); - - remove( inVar ); - assertConsistency(); - - Set refVars = new HashSet(); - refVars.add( inVar ); - add( new VariableSourceToken( refVars, - curr, - new Integer( 0 ), - inVar - ) - ); - assertConsistency(); - } - } - - - // for the given SESE, change child tokens into this parent - public void remapChildTokens( FlatSESEEnterNode curr ) { - - Iterator childItr = curr.getChildren().iterator(); - if( childItr.hasNext() ) { - FlatSESEEnterNode child = childItr.next(); - - // set of VSTs for removal - HashSet removalSet=new HashSet(); - // set of VSTs for additon - HashSet additionSet=new HashSet(); - - Iterator vstItr = get( child ).iterator(); - while( vstItr.hasNext() ) { - VariableSourceToken vst = vstItr.next(); - removalSet.add(vst); - additionSet.add(new VariableSourceToken( vst.getRefVars(), - curr, - new Integer( 0 ), - vst.getAddrVar() - )); - } - - // remove( eah item in forremoval ) - vstItr = removalSet.iterator(); - while( vstItr.hasNext() ) { - VariableSourceToken vst = vstItr.next(); - remove( vst ); - } - // add( each ite inm for additon _ - vstItr = additionSet.iterator(); - while( vstItr.hasNext() ) { - VariableSourceToken vst = vstItr.next(); - add( vst ); - } - } - - assertConsistency(); - } - - - // this method is called at the SESE exit of SESE 'curr' - // if the sources for a variable written by curr can also - // come from curr's parent or curr's siblings then we're not - // sure that curr will actually modify the variable. There are - // many ways to handle this, but for now, mark the variable as - // virtually read so curr insists on having ownership of it - // whether it ends up writing to it or not. It will always, then, - // appear in curr's out-set. - public Set - calcVirtReadsAndPruneParentAndSiblingTokens( FlatSESEEnterNode exiter, - Set liveVars ) { - - Set virtReadSet = new HashSet(); - - FlatSESEEnterNode parent = exiter.getParent(); - if( parent == null ) { - // having no parent means no siblings, too - return virtReadSet; - } - - Set alternateSESEs = new HashSet(); - alternateSESEs.add( parent ); - Iterator childItr = parent.getChildren().iterator(); - while( childItr.hasNext() ) { - FlatSESEEnterNode sibling = childItr.next(); - if( !sibling.equals( exiter ) ) { - alternateSESEs.add( sibling ); - } - } - - // VSTs to remove if they are alternate sources for exiter VSTs - // whose variables will become virtual reads - Set forRemoval = new HashSet(); - - // look at all of this SESE's VSTs at exit... - Iterator vstItr = get( exiter ).iterator(); - while( vstItr.hasNext() ) { - VariableSourceToken vstExiterSrc = vstItr.next(); - - // only interested in tokens that come from our current instance - if( vstExiterSrc.getAge() != 0 ) { - continue; - } - - // for each variable that might come from those sources... - Iterator refVarItr = vstExiterSrc.getRefVars().iterator(); - while( refVarItr.hasNext() ) { - TempDescriptor refVar = refVarItr.next(); - - // only matters for live variables at SESE exit program point - if( !liveVars.contains( refVar ) ) { - continue; - } - - // examine other sources for a variable... - Iterator srcItr = get( refVar ).iterator(); - while( srcItr.hasNext() ) { - VariableSourceToken vstPossibleOtherSrc = srcItr.next(); - - if( vstPossibleOtherSrc.getSESE().equals( exiter ) && - vstPossibleOtherSrc.getAge() > 0 - ) { - // this is an alternate source if its - // an older instance of this SESE - virtReadSet.add( refVar ); - forRemoval.add( vstPossibleOtherSrc ); - - } else if( alternateSESEs.contains( vstPossibleOtherSrc.getSESE() ) ) { - // this is an alternate source from parent or sibling - virtReadSet.add( refVar ); - forRemoval.add( vstPossibleOtherSrc ); - - } else { - assert vstPossibleOtherSrc.getSESE().equals( exiter ); - assert vstPossibleOtherSrc.getAge().equals( 0 ); - } - } - } - } - - vstItr = forRemoval.iterator(); - while( vstItr.hasNext() ) { - VariableSourceToken vst = vstItr.next(); - remove( vst ); - } - assertConsistency(); - - return virtReadSet; - } - - - // get the set of VST's that come from a child - public Set getChildrenVSTs( FlatSESEEnterNode curr ) { - - Set out = new HashSet(); - - Iterator cItr = curr.getChildren().iterator(); - while( cItr.hasNext() ) { - FlatSESEEnterNode child = cItr.next(); - out.addAll( get( child ) ); - } - - return out; - } - - - // given a table from a subsequent program point, decide - // which variables are going from a non-dynamic to a - // dynamic source and return them - public Hashtable - getReadyOrStatic2DynamicSet( VarSrcTokTable nextTable, - Set nextLiveIn, - FlatSESEEnterNode current - ) { - - Hashtable out = - new Hashtable(); - - Iterator itr = var2vst.entrySet().iterator(); - while( itr.hasNext() ) { - Map.Entry me = (Map.Entry) itr.next(); - TempDescriptor var = (TempDescriptor) me.getKey(); - HashSet s1 = (HashSet) me.getValue(); - - // only worth tracking if live - if( nextLiveIn.contains( var ) ) { - - VSTWrapper vstIfStaticBefore = new VSTWrapper(); - VSTWrapper vstIfStaticAfter = new VSTWrapper(); - - Integer srcTypeBefore = this.getRefVarSrcType( var, current, vstIfStaticBefore ); - Integer srcTypeAfter = nextTable.getRefVarSrcType( var, current, vstIfStaticAfter ); - - if( !srcTypeBefore.equals( SrcType_DYNAMIC ) && - srcTypeAfter.equals( SrcType_DYNAMIC ) - ) { - // remember the variable and a source - // it had before crossing the transition - // 1) if it was ready, vstIfStatic.vst is null - // 2) if is was static, use vstIfStatic.vst - out.put( var, vstIfStaticBefore ); - } - } - } - - return out; - } - - - // for some reference variable, return the type of source - // it might have in this table, which might be: - // 1. Ready -- this variable is - // definitely available when you are issued. - // 2. Static -- there is definitely one child SESE with - // a known age that will produce the value - // 3. Dynamic -- we don't know where the value will come - // from statically, so we'll track it dynamically - public Integer getRefVarSrcType( TempDescriptor refVar, - FlatSESEEnterNode current, - VSTWrapper vstIfStatic ) { - assert refVar != null; - assert vstIfStatic != null; - - vstIfStatic.vst = null; - - // when the current SESE is null, that simply means it is - // an unknown placeholder, in which case the system will - // ensure that any variables are READY - if( current == null ) { - return SrcType_READY; - } - - // if there appear to be no sources, it means this variable - // comes from outside of any statically-known SESE scope, - // which means the system guarantees its READY, so jump over - // while loop - Set srcs = get( refVar ); - Iterator itrSrcs = srcs.iterator(); - while( itrSrcs.hasNext() ) { - VariableSourceToken vst = itrSrcs.next(); - - // to make the refVar non-READY we have to find at least - // one child token - if( current.getChildren().contains( vst.getSESE() ) ) { - - // if we ever have at least one child source with an - // unknown age, have to treat var as dynamic - if( vst.getAge().equals( OoOJavaAnalysis.maxSESEage ) ) { - return SrcType_DYNAMIC; - } - - // if we have a known-age child source, this var is - // either static or dynamic now: it's static if this - // source is the only source, otherwise dynamic - if( srcs.size() > 1 ) { - return SrcType_DYNAMIC; - } - - vstIfStatic.vst = vst; - return SrcType_STATIC; - } - } - - // if we never found a child source, all other - // sources must be READY before we could even - // begin executing! - return SrcType_READY; - } - - - // any reference variables that are not live can be pruned - // from the table, and if any VSTs are then no longer - // referenced, they can be dropped as well - // THIS CAUSES INCONSISTENCY, FIX LATER, NOT REQUIRED - public void pruneByLiveness( Set rootLiveSet ) { - - // the set of reference variables in the table minus the - // live set gives the set of reference variables to remove - Set deadRefVars = new HashSet(); - deadRefVars.addAll( var2vst.keySet() ); - - if( rootLiveSet != null ) { - deadRefVars.removeAll( rootLiveSet ); - } - - // just use the remove operation to prune the table now - Iterator deadItr = deadRefVars.iterator(); - while( deadItr.hasNext() ) { - TempDescriptor dead = deadItr.next(); - removePrivate( dead ); - } - - assertConsistency(); - } - - - - // use as an aid for debugging, where true-set is checked - // against the alternate mappings: assert that nothing is - // missing or extra in the alternates - public void assertConsistency() { - - Iterator itr; - Set s; - - Set trueSetByAlts = new HashSet(); - itr = sese2vst.entrySet().iterator(); - while( itr.hasNext() ) { - Map.Entry me = (Map.Entry) itr.next(); - FlatSESEEnterNode sese = (FlatSESEEnterNode) me.getKey(); - HashSet s1 = (HashSet) me.getValue(); - assert s1 != null; - - // the trueSet should have all entries in s1 - assert trueSet.containsAll( s1 ); - - // s1 should not have anything that doesn't appear in trueset - Set sInt = (Set) s1.clone(); - sInt.removeAll( trueSet ); - - assert sInt.isEmpty(); - - // add s1 to a running union--at the end check if trueSet has extra - trueSetByAlts.addAll( s1 ); - } - // make sure trueSet isn't too big - assert trueSetByAlts.containsAll( trueSet ); - - - trueSetByAlts = new HashSet(); - itr = var2vst.entrySet().iterator(); - while( itr.hasNext() ) { - Map.Entry me = (Map.Entry) itr.next(); - TempDescriptor var = (TempDescriptor) me.getKey(); - HashSet s1 = (HashSet) me.getValue(); - assert s1 != null; - - // the trueSet should have all entries in s1 - assert trueSet.containsAll( s1 ); - - // s1 should not have anything that doesn't appear in trueset - Set sInt = (Set) s1.clone(); - sInt.removeAll( trueSet ); - - assert sInt.isEmpty(); - - // add s1 to a running union--at the end check if trueSet has extra - trueSetByAlts.addAll( s1 ); - } - // make sure trueSet isn't too big - assert trueSetByAlts.containsAll( trueSet ); - - - trueSetByAlts = new HashSet(); - itr = sv2vst.entrySet().iterator(); - while( itr.hasNext() ) { - Map.Entry me = (Map.Entry) itr.next(); - SVKey key = (SVKey) me.getKey(); - HashSet s1 = (HashSet) me.getValue(); - assert s1 != null; - - // the trueSet should have all entries in s1 - assert trueSet.containsAll( s1 ); - - // s1 should not have anything that doesn't appear in trueset - Set sInt = (Set) s1.clone(); - sInt.removeAll( trueSet ); - - assert sInt.isEmpty(); - - // add s1 to a running union--at the end check if trueSet has extra - trueSetByAlts.addAll( s1 ); - } - // make sure trueSet isn't too big - assert trueSetByAlts.containsAll( trueSet ); - - - // also check that the reference var sets are consistent - Hashtable > vst2refVars = - new Hashtable >(); - itr = var2vst.entrySet().iterator(); - while( itr.hasNext() ) { - Map.Entry me = (Map.Entry) itr.next(); - TempDescriptor refVar = (TempDescriptor) me.getKey(); - HashSet s1 = (HashSet) me.getValue(); - Iterator vstItr = s1.iterator(); - while( vstItr.hasNext() ) { - VariableSourceToken vst = vstItr.next(); - assert vst.getRefVars().contains( refVar ); - - Set refVarsPart = vst2refVars.get( vst ); - if( refVarsPart == null ) { - refVarsPart = new HashSet(); - } - refVarsPart.add( refVar ); - vst2refVars.put( vst, refVarsPart ); - } - } - itr = vst2refVars.entrySet().iterator(); - while( itr.hasNext() ) { - Map.Entry me = (Map.Entry) itr.next(); - VariableSourceToken vst = (VariableSourceToken) me.getKey(); - Set s1 = (Set) me.getValue(); - - assert vst.getRefVars().equals( s1 ); - } - } - - - public boolean equals( Object o ) { - if( o == null ) { - return false; - } - - if( !(o instanceof VarSrcTokTable) ) { - return false; - } - - VarSrcTokTable table = (VarSrcTokTable) o; - return trueSet.equals( table.trueSet ); - } - - public int hashCode() { - return trueSet.hashCode(); - } - - public Iterator iterator() { - return trueSet.iterator(); - } - - public String toString() { - return toStringPretty(); - } - - public String toStringVerbose() { - return "trueSet ="+trueSet.toString()+"\n"+ - "sese2vst="+sese2vst.toString()+"\n"+ - "var2vst ="+var2vst.toString()+"\n"+ - "sv2vst ="+sv2vst.toString(); - } - - public String toStringPretty() { - String tokHighlighter = "o"; - - String str = "VarSrcTokTable\n"; - Iterator vstItr = trueSet.iterator(); - while( vstItr.hasNext() ) { - str += " "+tokHighlighter+" "+vstItr.next()+"\n"; - } - return str; - } - - public String toStringPrettyVerbose() { - String tokHighlighter = "o"; - - String str = "VarSrcTokTable\n"; - - Set s; - Iterator itr; - Iterator vstItr; - - str += " trueSet\n"; - vstItr = trueSet.iterator(); - while( vstItr.hasNext() ) { - str += " "+tokHighlighter+" "+vstItr.next()+"\n"; - } - - str += " sese2vst\n"; - itr = sese2vst.entrySet().iterator(); - while( itr.hasNext() ) { - Map.Entry me = (Map.Entry) itr.next(); - FlatSESEEnterNode sese = (FlatSESEEnterNode) me.getKey(); - HashSet s1 = (HashSet) me.getValue(); - assert s1 != null; - - str += " "+sese.getPrettyIdentifier()+" -> \n"; - - vstItr = s1.iterator(); - while( vstItr.hasNext() ) { - str += " "+tokHighlighter+" "+vstItr.next()+"\n"; - } - } - - str += " var2vst\n"; - itr = var2vst.entrySet().iterator(); - while( itr.hasNext() ) { - Map.Entry me = (Map.Entry) itr.next(); - TempDescriptor var = (TempDescriptor) me.getKey(); - Set s1 = (Set) me.getValue(); - assert s1 != null; - - str += " "+var+" -> \n"; - - vstItr = s1.iterator(); - while( vstItr.hasNext() ) { - str += " "+tokHighlighter+" "+vstItr.next()+"\n"; - } - } - - str += " sv2vst\n"; - itr = sv2vst.entrySet().iterator(); - while( itr.hasNext() ) { - Map.Entry me = (Map.Entry) itr.next(); - SVKey key = (SVKey) me.getKey(); - Set s1 = (Set) me.getValue(); - assert s1 != null; - - str += " "+key+" -> \n"; - - vstItr = s1.iterator(); - while( vstItr.hasNext() ) { - str += " "+tokHighlighter+" "+vstItr.next()+"\n"; - } - } - - return str; - } -} diff --git a/Robust/src/Analysis/OoOJava/VariableSourceToken.java b/Robust/src/Analysis/OoOJava/VariableSourceToken.java deleted file mode 100644 index 1d845074..00000000 --- a/Robust/src/Analysis/OoOJava/VariableSourceToken.java +++ /dev/null @@ -1,82 +0,0 @@ -package Analysis.OoOJava; - -import IR.*; -import IR.Flat.*; -import java.util.*; -import java.io.*; - -public class VariableSourceToken { - - private Set refVars; - private FlatSESEEnterNode sese; - private Integer seseAge; - private TempDescriptor addrVar; - - public VariableSourceToken( Set refVars, - FlatSESEEnterNode sese, - Integer seseAge, - TempDescriptor addrVar - ) { - this.refVars = refVars; - this.sese = sese; - this.seseAge = seseAge; - this.addrVar = addrVar; - } - - public Set getRefVars() { - return refVars; - } - - public FlatSESEEnterNode getSESE() { - return sese; - } - - public Integer getAge() { - return seseAge; - } - - public TempDescriptor getAddrVar() { - return addrVar; - } - - public VariableSourceToken copy() { - Set refVarsCopy = new HashSet(); - - Iterator rvItr = refVars.iterator(); - while( rvItr.hasNext() ) { - refVarsCopy.add( rvItr.next() ); - } - - return new VariableSourceToken( refVarsCopy, - sese, - new Integer( seseAge ), - addrVar ); - } - - public boolean equals( Object o ) { - if( o == null ) { - return false; - } - - if( !(o instanceof VariableSourceToken) ) { - return false; - } - - VariableSourceToken vst = (VariableSourceToken) o; - - // the reference vars have no bearing on equality - return sese.equals( vst.sese ) && - addrVar.equals( vst.addrVar ) && - seseAge.equals( vst.seseAge ); - } - - public int hashCode() { - // the reference vars have no bearing on hashCode - return (sese.hashCode() << 3) * (addrVar.hashCode() << 4) ^ seseAge.intValue(); - } - - - public String toString() { - return refVars+"\tref "+addrVar+"\t@"+sese.toPrettyString()+"("+seseAge+")"; - } -} diff --git a/Robust/src/IR/Flat/BuildCode.java b/Robust/src/IR/Flat/BuildCode.java index d8801fdd..887f0ee6 100644 --- a/Robust/src/IR/Flat/BuildCode.java +++ b/Robust/src/IR/Flat/BuildCode.java @@ -23,6 +23,7 @@ import Analysis.Locality.DCWrapper; import Analysis.Locality.DelayComputation; import Analysis.Locality.BranchAnalysis; import Analysis.CallGraph.CallGraph; +import Analysis.OoOJava.OoOJavaAnalysis; import Analysis.Prefetch.*; import Analysis.Loops.WriteBarrier; import Analysis.Loops.GlobalFieldType; @@ -71,6 +72,7 @@ public class BuildCode { SafetyAnalysis sa; PrefetchAnalysis pa; MLPAnalysis mlpa; + OoOJavaAnalysis oooa; String mlperrstr = "if(status != 0) { "+ "sprintf(errmsg, \"MLP error at %s:%d\", __FILE__, __LINE__); "+ "perror(errmsg); exit(-1); }"; @@ -83,21 +85,22 @@ public class BuildCode { public BuildCode(State st, Hashtable temptovar, TypeUtil typeutil, SafetyAnalysis sa, PrefetchAnalysis pa) { - this(st, temptovar, typeutil, null, sa, pa, null); + this(st, temptovar, typeutil, null, sa, pa, null, null); } - public BuildCode(State st, Hashtable temptovar, TypeUtil typeutil, SafetyAnalysis sa, PrefetchAnalysis pa, MLPAnalysis mlpa) { - this(st, temptovar, typeutil, null, sa, pa, mlpa); + public BuildCode(State st, Hashtable temptovar, TypeUtil typeutil, SafetyAnalysis sa, PrefetchAnalysis pa, MLPAnalysis mlpa, OoOJavaAnalysis oooa) { + this(st, temptovar, typeutil, null, sa, pa, mlpa, oooa); } - public BuildCode(State st, Hashtable temptovar, TypeUtil typeutil, LocalityAnalysis locality, PrefetchAnalysis pa, MLPAnalysis mlpa) { - this(st, temptovar, typeutil, locality, null, pa, mlpa); + public BuildCode(State st, Hashtable temptovar, TypeUtil typeutil, LocalityAnalysis locality, PrefetchAnalysis pa, MLPAnalysis mlpa, OoOJavaAnalysis oooa) { + this(st, temptovar, typeutil, locality, null, pa, mlpa, oooa); } - public BuildCode(State st, Hashtable temptovar, TypeUtil typeutil, LocalityAnalysis locality, SafetyAnalysis sa, PrefetchAnalysis pa, MLPAnalysis mlpa) { + public BuildCode(State st, Hashtable temptovar, TypeUtil typeutil, LocalityAnalysis locality, SafetyAnalysis sa, PrefetchAnalysis pa, MLPAnalysis mlpa, OoOJavaAnalysis oooa) { this.sa=sa; this.pa=pa; this.mlpa=mlpa; + this.oooa=oooa; state=st; callgraph=new CallGraph(state); if (state.SINGLETM) @@ -199,7 +202,7 @@ public class BuildCode { outmethodheader.println("#include \"abortreaders.h\""); outmethodheader.println("#include "); } - if (state.MLP) { + if (state.MLP || state.OOOJAVA) { outmethodheader.println("#include "); outmethodheader.println("#include "); outmethodheader.println("#include "); @@ -238,28 +241,43 @@ public class BuildCode { outputTaskTypes(outtask); } - if( state.MLP ) { + if( state.MLP || state.OOOJAVA) { // have to initialize some SESE compiler data before // analyzing normal methods, which must happen before // generating SESE internal code - for(Iterator seseit=mlpa.getAllSESEs().iterator();seseit.hasNext();) { - FlatSESEEnterNode fsen = seseit.next(); - initializeSESE( fsen ); + + Iterator seseit; + if(state.MLP){ + seseit=mlpa.getAllSESEs().iterator(); + }else{ + seseit=oooa.getAllSESEs().iterator(); + } + while(seseit.hasNext()){ + FlatSESEEnterNode fsen = seseit.next(); + initializeSESE( fsen ); } + } /* Build the actual methods */ outputMethods(outmethod); // Output function prototypes and structures for SESE's and code - if( state.MLP ) { + if( state.MLP || state.OOOJAVA ) { // used to differentiate, during code generation, whether we are // passing over SESE body code, or non-SESE code nonSESEpass = false; - // first generate code for each sese's internals - for(Iterator seseit=mlpa.getAllSESEs().iterator();seseit.hasNext();) { + // first generate code for each sese's internals + Iterator seseit; + if(state.MLP){ + seseit=mlpa.getAllSESEs().iterator(); + }else{ + seseit=oooa.getAllSESEs().iterator(); + } + + while(seseit.hasNext()) { FlatSESEEnterNode fsen = seseit.next(); generateMethodSESE(fsen, null, outstructs, outmethodheader, outmethod); } @@ -309,7 +327,7 @@ public class BuildCode { outmethod.println("int main(int argc, const char *argv[]) {"); outmethod.println(" int i;"); - if (state.MLP) { + if (state.MLP || state.OOOJAVA) { //outmethod.println(" pthread_once( &mlpOnceObj, mlpInitOncePerThread );"); outmethod.println(" workScheduleInit( "+state.MLP_NUMCORES+", invokeSESEmethod );"); } @@ -430,7 +448,7 @@ public class BuildCode { if (state.THREAD||state.SINGLETM) outmethod.println("pthread_exit(NULL);"); - if (state.MLP) { + if (state.MLP || state.OOOJAVA ) { outmethod.println(" workScheduleBegin();"); } @@ -500,7 +518,7 @@ public class BuildCode { if (state.CONSCHECK) { outmethod.println("#include \"checkers.h\""); } - if (state.MLP) { + if (state.MLP || state.OOOJAVA ) { outmethod.println("#include "); outmethod.println("#include "); outmethod.println("#include \"mlp_runtime.h\""); @@ -557,7 +575,7 @@ public class BuildCode { outstructs.println("#define INTPTR int"); outstructs.println("#endif"); outstructs.println("#endif"); - if( state.MLP ) { + if( state.MLP || state.OOOJAVA ) { outstructs.println("#include \"mlp_runtime.h\""); outstructs.println("#include \"psemaphore.h\""); } @@ -638,7 +656,7 @@ public class BuildCode { //Print out definition for array type outclassdefs.println("struct "+arraytype+" {"); outclassdefs.println(" int type;"); - if(state.MLP){ + if(state.MLP || state.OOOJAVA ){ outclassdefs.println(" int oid;"); } if (state.EVENTMONITOR) { @@ -983,7 +1001,7 @@ public class BuildCode { outclassdefs.print("#endif\n"); outclassdefs.print("int numprefetchsites = " + pa.prefetchsiteid + ";\n"); - if(this.state.MLP){ + if(this.state.MLP || state.OOOJAVA ){ outclassdefs.print("extern __thread int oid;\n"); outclassdefs.print("extern int numWorkers;\n"); } @@ -1383,7 +1401,7 @@ public class BuildCode { /* Output class structure */ classdefout.println("struct "+cn.getSafeSymbol()+" {"); classdefout.println(" int type;"); - if(state.MLP){ + if(state.MLP || state.OOOJAVA){ classdefout.println(" int oid;"); } if (state.EVENTMONITOR) { @@ -1760,10 +1778,12 @@ public class BuildCode { } - if( state.MLP ) { + if( state.MLP || state.OOOJAVA ) { if( fm.getNext(0) instanceof FlatSESEEnterNode ) { FlatSESEEnterNode callerSESEplaceholder = (FlatSESEEnterNode) fm.getNext( 0 ); - if( callerSESEplaceholder != mlpa.getMainSESE() ) { + if( (state.MLP && callerSESEplaceholder != mlpa.getMainSESE()) || + (state.OOOJAVA && callerSESEplaceholder != oooa.getMainSESE()) + ) { // declare variables for naming static SESE's output.println(" /* static SESE names */"); Iterator pItr = callerSESEplaceholder.getNeededStaticNames().iterator(); @@ -1785,38 +1805,67 @@ public class BuildCode { // set up related allocation sites's waiting queues // eom - ConflictGraph graph = null; - graph = mlpa.getConflictGraphResults().get(fm); - if (graph != null && graph.hasConflictEdge()) { - output.println(" /* set up waiting queues */"); - output.println(" int numMemoryQueue=0;"); - output.println(" int memoryQueueItemID=0;"); - HashSet lockSet = mlpa.getConflictGraphLockMap().get( - graph); - System.out.println("#lockSet="+lockSet.hashCode()); - System.out.println("lockset="+lockSet); - for (Iterator iterator = lockSet.iterator(); iterator.hasNext();) { - SESELock seseLock = (SESELock) iterator.next(); - System.out.println("id="+seseLock.getID()); - System.out.println("#="+seseLock); - } - System.out.println("size="+lockSet.size()); - if (lockSet.size() > 0) { - output.println(" numMemoryQueue=" + lockSet.size() + ";"); - output - .println(" seseCaller->numMemoryQueue=numMemoryQueue;"); - output - .println(" seseCaller->memoryQueueArray=mlpCreateMemoryQueueArray(numMemoryQueue);"); - output.println(); - } - } + if(state.MLP){ + ConflictGraph graph = null; + graph = mlpa.getConflictGraphResults().get(fm); + if (graph != null && graph.hasConflictEdge()) { + output.println(" /* set up waiting queues */"); + output.println(" int numMemoryQueue=0;"); + output.println(" int memoryQueueItemID=0;"); + HashSet lockSet = mlpa.getConflictGraphLockMap().get( + graph); + System.out.println("#lockSet="+lockSet.hashCode()); + System.out.println("lockset="+lockSet); + for (Iterator iterator = lockSet.iterator(); iterator.hasNext();) { + SESELock seseLock = (SESELock) iterator.next(); + System.out.println("id="+seseLock.getID()); + System.out.println("#="+seseLock); + } + System.out.println("size="+lockSet.size()); + if (lockSet.size() > 0) { + output.println(" numMemoryQueue=" + lockSet.size() + ";"); + output + .println(" seseCaller->numMemoryQueue=numMemoryQueue;"); + output + .println(" seseCaller->memoryQueueArray=mlpCreateMemoryQueueArray(numMemoryQueue);"); + output.println(); + } + } + }else{ + FlatSESEEnterNode callerSESEplaceholder = (FlatSESEEnterNode) fm.getNext( 0 ); + Analysis.OoOJava.ConflictGraph graph = oooa.getConflictGraph(callerSESEplaceholder); + if (graph != null && graph.hasConflictEdge()) { + output.println(" /* set up waiting queues */"); + output.println(" int numMemoryQueue=0;"); + output.println(" int memoryQueueItemID=0;"); + Set lockSet = oooa.getLockMappings(graph); + System.out.println("#lockSet="+lockSet.hashCode()); + System.out.println("lockset="+lockSet); + for (Iterator iterator = lockSet.iterator(); iterator.hasNext();) { + Analysis.OoOJava.SESELock seseLock = (Analysis.OoOJava.SESELock) iterator.next(); + System.out.println("id="+seseLock.getID()); + System.out.println("#="+seseLock); + } + System.out.println("size="+lockSet.size()); + if (lockSet.size() > 0) { + output.println(" numMemoryQueue=" + lockSet.size() + ";"); + output + .println(" seseCaller->numMemoryQueue=numMemoryQueue;"); + output + .println(" seseCaller->memoryQueueArray=mlpCreateMemoryQueueArray(numMemoryQueue);"); + output.println(); + } + } + + } + } /* Check to see if we need to do a GC if this is a * multi-threaded program...*/ - if (((state.MLP||state.THREAD||state.DSM||state.SINGLETM)&&GENERATEPRECISEGC) + if (((state.MLP||state.OOOJAVA||state.THREAD||state.DSM||state.SINGLETM)&&GENERATEPRECISEGC) || this.state.MULTICOREGC) { //Don't bother if we aren't in recursive methods...The loops case will catch it if (callgraph.getAllMethods(md).contains(md)) { @@ -2114,19 +2163,17 @@ public class BuildCode { // setup memory queue // eom + if(state.OOOJAVA){ output.println(" // set up memory queues "); output.println(" int numMemoryQueue=0;"); output.println(" int memoryQueueItemID=0;"); - ConflictGraph graph = null; - graph = mlpa.getConflictGraphResults().get(fsen); + Analysis.OoOJava.ConflictGraph graph = oooa.getConflictGraph(fsen); if (graph != null && graph.hasConflictEdge()) { output.println(" {"); output .println(" SESEcommon* parentCommon = &(___params___->common);"); - HashSet lockSet = mlpa.getConflictGraphLockMap().get( - graph); + Set lockSet = oooa.getLockMappings(graph); System.out.println("#lockSet="+lockSet); - if (lockSet.size() > 0) { output.println(" numMemoryQueue=" + lockSet.size() + ";"); output @@ -2137,6 +2184,32 @@ public class BuildCode { } output.println(" }"); } + }else{ + output.println(" // set up memory queues "); + output.println(" int numMemoryQueue=0;"); + output.println(" int memoryQueueItemID=0;"); + ConflictGraph graph = null; + graph = mlpa.getConflictGraphResults().get(fsen); + if (graph != null && graph.hasConflictEdge()) { + output.println(" {"); + output + .println(" SESEcommon* parentCommon = &(___params___->common);"); + HashSet lockSet = mlpa.getConflictGraphLockMap().get( + graph); + System.out.println("#lockSet="+lockSet); + + if (lockSet.size() > 0) { + output.println(" numMemoryQueue=" + lockSet.size() + ";"); + output + .println(" parentCommon->numMemoryQueue=numMemoryQueue;"); + output + .println(" parentCommon->memoryQueueArray=mlpCreateMemoryQueueArray(numMemoryQueue);"); + output.println(); + } + output.println(" }"); + } + + } // copy in-set into place, ready vars were already @@ -2251,14 +2324,22 @@ public class BuildCode { // generate a case for each SESE class that can be invoked outmethod.println( " switch( *((int*)seseRecord) ) {"); outmethod.println( " "); - for(Iterator seseit=mlpa.getAllSESEs().iterator();seseit.hasNext();) { + Iterator seseit; + if(state.MLP){ + seseit=mlpa.getAllSESEs().iterator(); + }else{ + seseit=oooa.getAllSESEs().iterator(); + } + while(seseit.hasNext()){ FlatSESEEnterNode fsen = seseit.next(); outmethod.println( " /* "+fsen.getPrettyIdentifier()+" */"); outmethod.println( " case "+fsen.getIdentifier()+":"); outmethod.println( " "+fsen.getSESEmethodName()+"( seseRecord );"); - if( fsen.equals( mlpa.getMainSESE() ) ) { + if( (state.MLP && fsen.equals( mlpa.getMainSESE() )) || + (state.OOOJAVA && fsen.equals( oooa.getMainSESE() )) + ) { outmethod.println( " /* work scheduler works forever, explicitly exit */"); outmethod.println( " exit( 0 );"); } @@ -2361,7 +2442,7 @@ public class BuildCode { output.println("primitives->"+tmp.getSafeSymbol()+"="+tmp.getSafeSymbol()+";"); } } - if (state.MLP && stopset!=null) { + if ((state.MLP || state.OOOJAVA) && stopset!=null) { assert first.getPrev( 0 ) instanceof FlatSESEEnterNode; assert current_node instanceof FlatSESEExitNode; FlatSESEEnterNode fsen = (FlatSESEEnterNode) first.getPrev( 0 ); @@ -2375,7 +2456,7 @@ public class BuildCode { current_node=null; } else if(current_node.numNext()==1) { FlatNode nextnode; - if (state.MLP && + if ((state.MLP|| state.OOOJAVA) && current_node.kind()==FKind.FlatSESEEnterNode && !((FlatSESEEnterNode)current_node).getIsCallerSESEplaceholder() ) { @@ -2660,9 +2741,15 @@ public class BuildCode { protected void generateFlatNode(FlatMethod fm, LocalityBinding lb, FlatNode fn, PrintWriter output) { // insert pre-node actions from the code plan - if( state.MLP ) { + if( state.MLP|| state.OOOJAVA ) { - CodePlan cp = mlpa.getCodePlan( fn ); + CodePlan cp; + if(state.MLP){ + cp = mlpa.getCodePlan( fn ); + }else{ + cp = oooa.getCodePlan(fn); + } + if( cp != null ) { FlatSESEEnterNode currentSESE = cp.getCurrentSESE(); @@ -2762,49 +2849,84 @@ public class BuildCode { output.println(" "+dynVar+"_srcSESE = NULL;"); } - // eom + // eom // handling stall site - ParentChildConflictsMap conflictsMap = mlpa.getConflictsResults().get(fn); - if (conflictsMap != null) { - Set allocSet = conflictsMap.getAllocationSiteIDSetofStallSite(); - if (allocSet.size() > 0) { - FlatNode enclosingFlatNode=null; - if( currentSESE.getIsCallerSESEplaceholder() && currentSESE.getParent()==null){ - enclosingFlatNode=currentSESE.getfmEnclosing(); - }else{ - enclosingFlatNode=currentSESE; - } - ConflictGraph graph=mlpa.getConflictGraphResults().get(enclosingFlatNode); - HashSet seseLockSet=mlpa.getConflictGraphLockMap().get(graph); - Set waitingElementSet=graph.getStallSiteWaitingElementSet(conflictsMap, seseLockSet); - - if(waitingElementSet.size()>0){ - output.println("// stall on parent's stall sites "); - output.println(" {"); - output.println(" REntry* rentry;"); - - for (Iterator iterator = waitingElementSet.iterator(); iterator.hasNext();) { - WaitingElement waitingElement = (WaitingElement) iterator.next(); - - if( waitingElement.getStatus() >= ConflictNode.COARSE ){ - output.println(" rentry=mlpCreateREntry("+ waitingElement.getStatus()+ ", seseCaller);"); - }else{ - output.println(" rentry=mlpCreateFineREntry("+ waitingElement.getStatus()+ ", seseCaller, (void*)&___locals___."+ waitingElement.getDynID() + ");"); -// output.println(" rentry=mlpCreateFineREntry("+ waitingElement.getStatus()+ ", seseCaller, ___locals___."+ waitingElement.getDynID() + "->oid);"); - } - output.println(" psem_init( &(rentry->parentStallSem) );"); - output.println(" rentry->queue=seseCaller->memoryQueueArray["+ waitingElement.getQueueID()+ "];"); - output - .println(" if(ADDRENTRY(seseCaller->memoryQueueArray["+ waitingElement.getQueueID() - + "],rentry)==NOTREADY){"); - output.println(" psem_take( &(rentry->parentStallSem) );"); - output.println(" } "); - } - output.println(" }"); - } - } - } + if (state.OOOJAVA) { + Analysis.OoOJava.ConflictGraph graph = oooa.getConflictGraph(currentSESE); + if(graph!=null){ + Set seseLockSet = oooa.getLockMappings(graph); + Set waitingElementSet = + graph.getStallSiteWaitingElementSet(fn, seseLockSet); + + if(waitingElementSet.size()>0){ + output.println("// stall on parent's stall sites "); + output.println(" {"); + output.println(" REntry* rentry;"); + + for (Iterator iterator = waitingElementSet.iterator(); iterator.hasNext();) { + Analysis.OoOJava.WaitingElement waitingElement = (Analysis.OoOJava.WaitingElement) iterator.next(); + + if( waitingElement.getStatus() >= ConflictNode.COARSE ){ + output.println(" rentry=mlpCreateREntry("+ waitingElement.getStatus()+ ", seseCaller);"); + }else{ + output.println(" rentry=mlpCreateFineREntry("+ waitingElement.getStatus()+ ", seseCaller, (void*)&___locals___."+ waitingElement.getDynID() + ");"); + // output.println(" rentry=mlpCreateFineREntry("+ waitingElement.getStatus()+ ", seseCaller, ___locals___."+ waitingElement.getDynID() + "->oid);"); + } + output.println(" psem_init( &(rentry->parentStallSem) );"); + output.println(" rentry->queue=seseCaller->memoryQueueArray["+ waitingElement.getQueueID()+ "];"); + output + .println(" if(ADDRENTRY(seseCaller->memoryQueueArray["+ waitingElement.getQueueID() + + "],rentry)==NOTREADY){"); + output.println(" psem_take( &(rentry->parentStallSem) );"); + output.println(" } "); + } + output.println(" }"); + } + } + }else{ + ParentChildConflictsMap conflictsMap = mlpa.getConflictsResults().get(fn); + if (conflictsMap != null) { + Set allocSet = conflictsMap.getAllocationSiteIDSetofStallSite(); + if (allocSet.size() > 0) { + FlatNode enclosingFlatNode=null; + if( currentSESE.getIsCallerSESEplaceholder() && currentSESE.getParent()==null){ + enclosingFlatNode=currentSESE.getfmEnclosing(); + }else{ + enclosingFlatNode=currentSESE; + } + ConflictGraph graph=mlpa.getConflictGraphResults().get(enclosingFlatNode); + HashSet seseLockSet=mlpa.getConflictGraphLockMap().get(graph); + Set waitingElementSet=graph.getStallSiteWaitingElementSet(conflictsMap, seseLockSet); + + if(waitingElementSet.size()>0){ + output.println("// stall on parent's stall sites "); + output.println(" {"); + output.println(" REntry* rentry;"); + + for (Iterator iterator = waitingElementSet.iterator(); iterator.hasNext();) { + WaitingElement waitingElement = (WaitingElement) iterator.next(); + + if( waitingElement.getStatus() >= ConflictNode.COARSE ){ + output.println(" rentry=mlpCreateREntry("+ waitingElement.getStatus()+ ", seseCaller);"); + }else{ + output.println(" rentry=mlpCreateFineREntry("+ waitingElement.getStatus()+ ", seseCaller, (void*)&___locals___."+ waitingElement.getDynID() + ");"); + // output.println(" rentry=mlpCreateFineREntry("+ waitingElement.getStatus()+ ", seseCaller, ___locals___."+ waitingElement.getDynID() + "->oid);"); + } + output.println(" psem_init( &(rentry->parentStallSem) );"); + output.println(" rentry->queue=seseCaller->memoryQueueArray["+ waitingElement.getQueueID()+ "];"); + output + .println(" if(ADDRENTRY(seseCaller->memoryQueueArray["+ waitingElement.getQueueID() + + "],rentry)==NOTREADY){"); + output.println(" psem_take( &(rentry->parentStallSem) );"); + output.println(" } "); + } + output.println(" }"); + } + } + } + } + } } @@ -2896,7 +3018,7 @@ public class BuildCode { if(state.DSM&&state.SANDBOX&&(locality.getAtomic(lb).get(fn).intValue()>0)) { output.println("if (unlikely((--transaction_check_counter)<=0)) checkObjects();"); } - if (((state.MLP||state.THREAD||state.DSM||state.SINGLETM)&&GENERATEPRECISEGC) + if (((state.MLP|| state.OOOJAVA||state.THREAD||state.DSM||state.SINGLETM)&&GENERATEPRECISEGC) || (this.state.MULTICOREGC)) { if(state.DSM&&locality.getAtomic(lb).get(fn).intValue()>0) { output.println("if (needtocollect) checkcollect2("+localsprefixaddr+");"); @@ -2929,13 +3051,15 @@ public class BuildCode { throw new Error(); } - // insert post-node actions from the code-plan - if( state.MLP ) { + // insert post-node actions from the code-plan + /* + if( state.MLP) { CodePlan cp = mlpa.getCodePlan( fn ); if( cp != null ) { } - } + } + */ } public void generateFlatOffsetNode(FlatMethod fm, LocalityBinding lb, FlatOffsetNode fofn, PrintWriter output) { @@ -3315,15 +3439,15 @@ public class BuildCode { FlatSESEEnterNode fsen, PrintWriter output ) { - // if MLP flag is off, okay that SESE nodes are in IR graph, // just skip over them and code generates exactly the same - if( !state.MLP ) { + if( !(state.MLP || state.OOOJAVA) ) { return; } - // there may be an SESE in an unreachable method, skip over - if( !mlpa.getAllSESEs().contains( fsen ) ) { + if( (state.MLP && !mlpa.getAllSESEs().contains( fsen )) || + (state.OOOJAVA && !oooa.getAllSESEs().contains(fsen)) + ) { return; } @@ -3335,7 +3459,9 @@ public class BuildCode { output.println(" {"); // set up the parent - if( fsen == mlpa.getMainSESE() ) { + if( (state.MLP && fsen == mlpa.getMainSESE()) || + (state.OOOJAVA && fsen == oooa.getMainSESE()) + ) { output.println(" SESEcommon* parentCommon = NULL;"); } else { if( fsen.getParent() == null ) { @@ -3351,7 +3477,9 @@ public class BuildCode { } // before doing anything, lock your own record and increment the running children - if( fsen != mlpa.getMainSESE() ) { + if( (state.MLP && fsen != mlpa.getMainSESE()) || + (state.OOOJAVA && fsen != oooa.getMainSESE()) + ) { output.println(" atomic_inc(&parentCommon->numRunningChildren);"); } @@ -3401,7 +3529,9 @@ public class BuildCode { // otherwise use the parent's enclosing method as the context boolean useParentContext = false; - if( fsen != mlpa.getMainSESE() ) { + if( (state.MLP && fsen != mlpa.getMainSESE()) || + (state.OOOJAVA && fsen != oooa.getMainSESE()) + ) { assert fsen.getParent() != null; if( !fsen.getParent().getIsCallerSESEplaceholder() ) { useParentContext = true; @@ -3422,7 +3552,9 @@ public class BuildCode { output.println(" pthread_mutex_init( &(seseToIssue->common.lock), NULL );"); // output.println(" pthread_mutex_lock( &(seseToIssue->common.lock) );"); - if( fsen != mlpa.getMainSESE() ) { + if( (state.MLP && fsen != mlpa.getMainSESE()) || + (state.OOOJAVA && fsen != oooa.getMainSESE()) + ) { // count up outstanding dependencies, static first, then dynamic Iterator staticSrcsItr = fsen.getStaticInVarSrcs().iterator(); while( staticSrcsItr.hasNext() ) { @@ -3488,7 +3620,9 @@ public class BuildCode { output.println(" } else {"); boolean useParentContext = false; - if( fsen != mlpa.getMainSESE() ) { + if( (state.MLP && fsen != mlpa.getMainSESE()) || + (state.OOOJAVA && fsen != oooa.getMainSESE()) + ) { assert fsen.getParent() != null; if( !fsen.getParent().getIsCallerSESEplaceholder() ) { useParentContext = true; @@ -3529,130 +3663,251 @@ public class BuildCode { //////////////// // count up memory conflict dependencies, // eom - ConflictGraph graph = null; - FlatSESEEnterNode parent = fsen.getParent(); - if (parent != null) { - if (parent.isCallerSESEplaceholder) { - graph = mlpa.getConflictGraphResults().get(parent.getfmEnclosing()); - } else { - graph = mlpa.getConflictGraphResults().get(parent); - } - } - if (graph != null && graph.hasConflictEdge()) { - HashSet seseLockSet = mlpa.getConflictGraphLockMap() - .get(graph); - output.println(); - output.println(" //add memory queue element"); - SESEWaitingQueue seseWaitingQueue=graph.getWaitingElementSetBySESEID(fsen.getIdentifier(), - seseLockSet); - if(seseWaitingQueue.getWaitingElementSize()>0){ - output.println(" {"); - output.println(" REntry* rentry=NULL;"); - output.println(" INTPTR* pointer=NULL;"); - output.println(" seseToIssue->common.rentryIdx=0;"); - - Set queueIDSet=seseWaitingQueue.getQueueIDSet(); - for (Iterator iterator = queueIDSet.iterator(); iterator - .hasNext();) { - Integer key = (Integer) iterator.next(); - int queueID=key.intValue(); - Set waitingQueueSet = seseWaitingQueue.getWaitingElementSet(queueID); - int enqueueType=seseWaitingQueue.getType(queueID); - if(enqueueType==SESEWaitingQueue.EXCEPTION){ - output.println(" INITIALIZEBUF(parentCommon->memoryQueueArray[" - + queueID+ "]);"); - } - for (Iterator iterator2 = waitingQueueSet.iterator(); iterator2 - .hasNext();) { - WaitingElement waitingElement = (WaitingElement) iterator2 - .next(); - if (waitingElement.getStatus() >= ConflictNode.COARSE) { - output.println(" rentry=mlpCreateREntry(" - + waitingElement.getStatus() - + ", seseToIssue);"); - } else { - TempDescriptor td = waitingElement - .getTempDesc(); - // decide whether waiting element is dynamic or - // static - if (fsen.getDynamicInVarSet().contains(td)) { - // dynamic in-var case - output.println(" pointer=seseToIssue->" - + waitingElement.getDynID() - + "_srcSESE+seseToIssue->" - + waitingElement.getDynID() - + "_srcOffset;"); - output - .println(" rentry=mlpCreateFineREntry(" - + waitingElement - .getStatus() - + ", seseToIssue, pointer );"); - } else if (fsen.getStaticInVarSet() - .contains(td)) { - // static in-var case - VariableSourceToken vst = fsen - .getStaticInVarSrc(td); - if (vst != null) { - - String srcId = "SESE_" - + vst.getSESE() - .getPrettyIdentifier() - + vst.getSESE().getIdentifier() - + "_" + vst.getAge(); - output - .println(" pointer=(void*)&seseToIssue->" - + srcId - + "->" - + waitingElement - .getDynID() - + ";"); - output - .println(" rentry=mlpCreateFineREntry(" - + waitingElement - .getStatus() - + ", seseToIssue, pointer );"); - - } - } else { - output - .println(" rentry=mlpCreateFineREntry(" - + waitingElement - .getStatus() - + ", seseToIssue, (void*)&seseToIssue->" - + waitingElement.getDynID() - + ");"); - } - } - output - .println(" rentry->queue=parentCommon->memoryQueueArray[" - + waitingElement.getQueueID() - + "];"); - - if(enqueueType==SESEWaitingQueue.NORMAL){ - output - .println(" seseToIssue->common.rentryArray[seseToIssue->common.rentryIdx++]=rentry;"); - output - .println(" if(ADDRENTRY(parentCommon->memoryQueueArray[" - + waitingElement.getQueueID() - + "],rentry)==NOTREADY){"); - output.println(" ++(localCount);"); - output.println(" } "); - }else{ - output - .println(" ADDRENTRYTOBUF(parentCommon->memoryQueueArray[" - + waitingElement.getQueueID() - + "],rentry);"); - } - } - if(enqueueType!=SESEWaitingQueue.NORMAL){ - output.println(" localCount+=RESOLVEBUF(parentCommon->memoryQueueArray[" - + queueID+ "],&seseToIssue->common);"); - } - } - output.println(" }"); - } - output.println(); - } + if(state.OOOJAVA){ + + FlatSESEEnterNode parent = fsen.getParent(); + Analysis.OoOJava.ConflictGraph graph = oooa.getConflictGraph(parent); + if (graph != null && graph.hasConflictEdge()) { + Set seseLockSet = oooa.getLockMappings(graph); + output.println(); + output.println(" //add memory queue element"); + Analysis.OoOJava.SESEWaitingQueue seseWaitingQueue= + graph.getWaitingElementSetBySESEID(fsen.getIdentifier(), seseLockSet); + if(seseWaitingQueue.getWaitingElementSize()>0){ + output.println(" {"); + output.println(" REntry* rentry=NULL;"); + output.println(" INTPTR* pointer=NULL;"); + output.println(" seseToIssue->common.rentryIdx=0;"); + + Set queueIDSet=seseWaitingQueue.getQueueIDSet(); + for (Iterator iterator = queueIDSet.iterator(); iterator + .hasNext();) { + Integer key = (Integer) iterator.next(); + int queueID=key.intValue(); + Set waitingQueueSet = + seseWaitingQueue.getWaitingElementSet(queueID); + int enqueueType=seseWaitingQueue.getType(queueID); + if(enqueueType==SESEWaitingQueue.EXCEPTION){ + output.println(" INITIALIZEBUF(parentCommon->memoryQueueArray[" + + queueID+ "]);"); + } + for (Iterator iterator2 = waitingQueueSet.iterator(); iterator2 + .hasNext();) { + Analysis.OoOJava.WaitingElement waitingElement + = (Analysis.OoOJava.WaitingElement) iterator2.next(); + if (waitingElement.getStatus() >= ConflictNode.COARSE) { + output.println(" rentry=mlpCreateREntry(" + + waitingElement.getStatus() + + ", seseToIssue);"); + } else { + TempDescriptor td = waitingElement + .getTempDesc(); + // decide whether waiting element is dynamic or static + if (fsen.getDynamicInVarSet().contains(td)) { + // dynamic in-var case + output.println(" pointer=seseToIssue->" + + waitingElement.getDynID() + + "_srcSESE+seseToIssue->" + + waitingElement.getDynID() + + "_srcOffset;"); + output + .println(" rentry=mlpCreateFineREntry(" + + waitingElement + .getStatus() + + ", seseToIssue, pointer );"); + } else if (fsen.getStaticInVarSet() + .contains(td)) { + // static in-var case + VariableSourceToken vst = fsen + .getStaticInVarSrc(td); + if (vst != null) { + + String srcId = "SESE_" + + vst.getSESE() + .getPrettyIdentifier() + + vst.getSESE().getIdentifier() + + "_" + vst.getAge(); + output + .println(" pointer=(void*)&seseToIssue->" + + srcId + + "->" + + waitingElement + .getDynID() + + ";"); + output + .println(" rentry=mlpCreateFineREntry(" + + waitingElement + .getStatus() + + ", seseToIssue, pointer );"); + + } + } else { + output + .println(" rentry=mlpCreateFineREntry(" + + waitingElement + .getStatus() + + ", seseToIssue, (void*)&seseToIssue->" + + waitingElement.getDynID() + + ");"); + } + } + output + .println(" rentry->queue=parentCommon->memoryQueueArray[" + + waitingElement.getQueueID() + + "];"); + + if(enqueueType==SESEWaitingQueue.NORMAL){ + output + .println(" seseToIssue->common.rentryArray[seseToIssue->common.rentryIdx++]=rentry;"); + output + .println(" if(ADDRENTRY(parentCommon->memoryQueueArray[" + + waitingElement.getQueueID() + + "],rentry)==NOTREADY){"); + output.println(" ++(localCount);"); + output.println(" }"); + }else{ + output + .println(" ADDRENTRYTOBUF(parentCommon->memoryQueueArray[" + + waitingElement.getQueueID() + + "],rentry);"); + } + } + if(enqueueType!=SESEWaitingQueue.NORMAL){ + output.println(" localCount+=RESOLVEBUF(parentCommon->memoryQueueArray[" + + queueID+ "],&seseToIssue->common);"); + } + } + output.println(" }"); + } + output.println(); + } + + }else{ + ConflictGraph graph = null; + FlatSESEEnterNode parent = fsen.getParent(); + if (parent != null) { + if (parent.isCallerSESEplaceholder) { + graph = mlpa.getConflictGraphResults().get(parent.getfmEnclosing()); + } else { + graph = mlpa.getConflictGraphResults().get(parent); + } + } + if (graph != null && graph.hasConflictEdge()) { + HashSet seseLockSet = mlpa.getConflictGraphLockMap() + .get(graph); + output.println(); + output.println(" //add memory queue element"); + SESEWaitingQueue seseWaitingQueue=graph.getWaitingElementSetBySESEID(fsen.getIdentifier(), + seseLockSet); + if(seseWaitingQueue.getWaitingElementSize()>0){ + output.println(" {"); + output.println(" REntry* rentry=NULL;"); + output.println(" INTPTR* pointer=NULL;"); + output.println(" seseToIssue->common.rentryIdx=0;"); + + Set queueIDSet=seseWaitingQueue.getQueueIDSet(); + for (Iterator iterator = queueIDSet.iterator(); iterator + .hasNext();) { + Integer key = (Integer) iterator.next(); + int queueID=key.intValue(); + Set waitingQueueSet = seseWaitingQueue.getWaitingElementSet(queueID); + int enqueueType=seseWaitingQueue.getType(queueID); + if(enqueueType==SESEWaitingQueue.EXCEPTION){ + output.println(" INITIALIZEBUF(parentCommon->memoryQueueArray[" + + queueID+ "]);"); + } + for (Iterator iterator2 = waitingQueueSet.iterator(); iterator2 + .hasNext();) { + WaitingElement waitingElement = (WaitingElement) iterator2 + .next(); + if (waitingElement.getStatus() >= ConflictNode.COARSE) { + output.println(" rentry=mlpCreateREntry(" + + waitingElement.getStatus() + + ", seseToIssue);"); + } else { + TempDescriptor td = waitingElement + .getTempDesc(); + // decide whether waiting element is dynamic or + // static + if (fsen.getDynamicInVarSet().contains(td)) { + // dynamic in-var case + output.println(" pointer=seseToIssue->" + + waitingElement.getDynID() + + "_srcSESE+seseToIssue->" + + waitingElement.getDynID() + + "_srcOffset;"); + output + .println(" rentry=mlpCreateFineREntry(" + + waitingElement + .getStatus() + + ", seseToIssue, pointer );"); + } else if (fsen.getStaticInVarSet() + .contains(td)) { + // static in-var case + VariableSourceToken vst = fsen + .getStaticInVarSrc(td); + if (vst != null) { + + String srcId = "SESE_" + + vst.getSESE() + .getPrettyIdentifier() + + vst.getSESE().getIdentifier() + + "_" + vst.getAge(); + output + .println(" pointer=(void*)&seseToIssue->" + + srcId + + "->" + + waitingElement + .getDynID() + + ";"); + output + .println(" rentry=mlpCreateFineREntry(" + + waitingElement + .getStatus() + + ", seseToIssue, pointer );"); + + } + } else { + output + .println(" rentry=mlpCreateFineREntry(" + + waitingElement + .getStatus() + + ", seseToIssue, (void*)&seseToIssue->" + + waitingElement.getDynID() + + ");"); + } + } + output + .println(" rentry->queue=parentCommon->memoryQueueArray[" + + waitingElement.getQueueID() + + "];"); + + if(enqueueType==SESEWaitingQueue.NORMAL){ + output + .println(" seseToIssue->common.rentryArray[seseToIssue->common.rentryIdx++]=rentry;"); + output + .println(" if(ADDRENTRY(parentCommon->memoryQueueArray[" + + waitingElement.getQueueID() + + "],rentry)==NOTREADY){"); + output.println(" ++(localCount);"); + output.println(" } "); + }else{ + output + .println(" ADDRENTRYTOBUF(parentCommon->memoryQueueArray[" + + waitingElement.getQueueID() + + "],rentry);"); + } + } + if(enqueueType!=SESEWaitingQueue.NORMAL){ + output.println(" localCount+=RESOLVEBUF(parentCommon->memoryQueueArray[" + + queueID+ "],&seseToIssue->common);"); + } + } + output.println(" }"); + } + output.println(); + } + } //////////////// } @@ -3684,7 +3939,7 @@ public class BuildCode { // if MLP flag is off, okay that SESE nodes are in IR graph, // just skip over them and code generates exactly the same - if( !state.MLP ) { + if( ! (state.MLP || state.OOOJAVA) ) { return; } @@ -3692,7 +3947,9 @@ public class BuildCode { FlatSESEEnterNode fsen = fsexn.getFlatEnter(); // there may be an SESE in an unreachable method, skip over - if( !mlpa.getAllSESEs().contains( fsen ) ) { + if( (state.MLP && !mlpa.getAllSESEs().contains( fsen )) || + (state.OOOJAVA && !oooa.getAllSESEs().contains( fsen )) + ) { return; } @@ -3743,7 +4000,9 @@ public class BuildCode { // have to determine the context enclosing this sese boolean useParentContext = false; - if( fsen != mlpa.getMainSESE() ) { + if( (state.MLP &&fsen != mlpa.getMainSESE()) || + (state.OOOJAVA &&fsen != oooa.getMainSESE()) + ) { assert fsen.getParent() != null; if( !fsen.getParent().getIsCallerSESEplaceholder() ) { useParentContext = true; @@ -3793,7 +4052,9 @@ public class BuildCode { // eom // clean up its lock element from waiting queue, and decrement dependency count for next SESE block - if( fsen != mlpa.getMainSESE() ) { + if( (state.MLP && fsen != mlpa.getMainSESE()) || + (state.OOOJAVA && fsen != oooa.getMainSESE()) + ) { output.println(); output.println(" /* check memory dependency*/"); @@ -3808,7 +4069,9 @@ public class BuildCode { } // if parent is stalling on you, let them know you're done - if( fsexn.getFlatEnter() != mlpa.getMainSESE() ) { + if( (state.MLP && fsexn.getFlatEnter() != mlpa.getMainSESE()) || + (state.OOOJAVA && fsexn.getFlatEnter() != oooa.getMainSESE()) + ) { output.println(" psem_give( &("+paramsprefix+"->common.stallSem) );"); } @@ -3839,7 +4102,7 @@ public class BuildCode { FlatWriteDynamicVarNode fwdvn, PrintWriter output ) { - if( !state.MLP ) { + if( !(state.MLP || state.OOOJAVA) ) { // should node should not be in an IR graph if the // MLP flag is not set throw new Error("Unexpected presence of FlatWriteDynamicVarNode"); @@ -3906,7 +4169,9 @@ public class BuildCode { private void generateFlatCall(FlatMethod fm, LocalityBinding lb, FlatCall fc, PrintWriter output) { - if( state.MLP && !nonSESEpass ) { + if( (state.MLP && !nonSESEpass) || + (state.OOOJAVA && !nonSESEpass) + ) { output.println(" seseCaller = (SESEcommon*)"+paramsprefix+";"); } @@ -4431,7 +4696,7 @@ public class BuildCode { if (fn.isGlobal()&&(state.DSM||state.SINGLETM)) { output.println(generateTemp(fm,fn.getDst(),lb)+"=allocate_newarrayglobal("+arrayid+", "+generateTemp(fm, fn.getSize(),lb)+");"); } else if ((GENERATEPRECISEGC) || (this.state.MULTICOREGC)) { - if(this.state.MLP){ + if(this.state.MLP || state.OOOJAVA){ output.println(generateTemp(fm,fn.getDst(),lb)+"=allocate_newarray_oid("+localsprefixaddr+", "+arrayid+", "+generateTemp(fm, fn.getSize(),lb)+", oid);"); output.println(" oid += numWorkers;"); }else{ @@ -4444,7 +4709,7 @@ public class BuildCode { if (fn.isGlobal()&&(state.DSM||state.SINGLETM)) { output.println(generateTemp(fm,fn.getDst(),lb)+"=allocate_newglobal("+fn.getType().getClassDesc().getId()+");"); } else if ((GENERATEPRECISEGC) || (this.state.MULTICOREGC)) { - if (this.state.MLP){ + if (this.state.MLP || state.OOOJAVA){ output.println(generateTemp(fm,fn.getDst(),lb)+"=allocate_new_oid("+localsprefixaddr+", "+fn.getType().getClassDesc().getId()+", oid);"); output.println(" oid += numWorkers;"); } else { diff --git a/Robust/src/Main/Main.java b/Robust/src/Main/Main.java index cef1023a..1e4d3ed6 100644 --- a/Robust/src/Main/Main.java +++ b/Robust/src/Main/Main.java @@ -324,6 +324,8 @@ public class Main { } else if (option.equals("-ooojava")) { state.OOOJAVA = true; state.DISJOINT = true; + state.MLP_NUMCORES = Integer.parseInt( args[++i] ); + state.MLP_MAXSESEAGE = Integer.parseInt( args[++i] ); } else if (option.equals("-ooodebug") ){ state.OOODEBUG = true; @@ -414,6 +416,7 @@ public class Main { SafetyAnalysis sa=null; PrefetchAnalysis pa=null; MLPAnalysis mlpa=null; + OoOJavaAnalysis oooa=null; if (state.INLINEATOMIC) { Iterator classit=state.getClassSymbolTable().getDescriptorsIterator(); while(classit.hasNext()) { @@ -514,7 +517,7 @@ public class Main { CallGraph cg = new CallGraph(state); Liveness l = new Liveness(); ArrayReferencees ar = new ArrayReferencees(state); - OoOJavaAnalysis oa = new OoOJavaAnalysis(state, tu, cg, l, ar); + oooa = new OoOJavaAnalysis(state, tu, cg, l, ar); } @@ -611,10 +614,10 @@ public class Main { } LocalityAnalysis la=new LocalityAnalysis(state, callgraph, tu); GenerateConversions gc=new GenerateConversions(la, state); - BuildCode bc=new BuildCode(state, bf.getMap(), tu, la, pa, mlpa); + BuildCode bc=new BuildCode(state, bf.getMap(), tu, la, pa, mlpa,oooa); bc.buildCode(); } else { - BuildCode bc=new BuildCode(state, bf.getMap(), tu, sa, pa, mlpa); + BuildCode bc=new BuildCode(state, bf.getMap(), tu, sa, pa, mlpa,oooa); bc.buildCode(); } } diff --git a/Robust/src/buildscript b/Robust/src/buildscript index fb03f76a..f1f1111e 100755 --- a/Robust/src/buildscript +++ b/Robust/src/buildscript @@ -386,6 +386,14 @@ elif [[ $1 = '-minimize' ]] then JAVAOPTS="$JAVAOPTS -minimize" +elif [[ $1 = '-ooojava' ]] +then +MLP_ON=true +JAVAOPTS="$JAVAOPTS -ooojava $2 $3" +EXTRAOPTIONS="$EXTRAOPTIONS -DPRECISE_GC -lpthread -DMLP" +shift +shift + elif [[ $1 = '-mlp' ]] then MLP_ON=true -- 2.34.1