From: yeom Date: Sat, 26 Jun 2010 23:27:12 +0000 (+0000) Subject: working on the remaining procedures of OoOJava analysis. X-Git-Url: http://plrg.eecs.uci.edu/git/?p=IRC.git;a=commitdiff_plain;h=3b30672ca80e2627484e71b1b8dce54fe6e0eda1;ds=sidebyside working on the remaining procedures of OoOJava analysis. --- diff --git a/Robust/src/Analysis/Disjoint/DisjointAnalysis.java b/Robust/src/Analysis/Disjoint/DisjointAnalysis.java index 5f02861f..9cde75ff 100644 --- a/Robust/src/Analysis/Disjoint/DisjointAnalysis.java +++ b/Robust/src/Analysis/Disjoint/DisjointAnalysis.java @@ -2242,6 +2242,9 @@ getFlaggedAllocationSitesReachableFromTaskPRIVATE(TaskDescriptor td) { return descriptorsToAnalyze; } + public EffectsAnalysis getEffectsAnalysis(){ + return effectsAnalysis; + } // get successive captures of the analysis state, use compiler diff --git a/Robust/src/Analysis/OoOJava/ConflictEdge.java b/Robust/src/Analysis/OoOJava/ConflictEdge.java new file mode 100644 index 00000000..60c610f8 --- /dev/null +++ b/Robust/src/Analysis/OoOJava/ConflictEdge.java @@ -0,0 +1,47 @@ +package Analysis.OoOJava; + +public class ConflictEdge { + + private ConflictNode u; + private ConflictNode v; + private int type; + + public ConflictEdge(ConflictNode u, ConflictNode v, int type) { + this.u = u; + this.v = v; + this.type = type; + } + + public String toGraphEdgeString() { + if (type == ConflictGraph.FINE_GRAIN_EDGE) { + return "\"F_CONFLICT\""; + } else if (type == ConflictGraph.COARSE_GRAIN_EDGE) { + return "\"C_CONFLICT\""; + } else { + return "CONFLICT\""; + } + } + + public ConflictNode getVertexU() { + return u; + } + + public ConflictNode getVertexV() { + return v; + } + public int getType() { + return type; + } + + public boolean isCoarseEdge(){ + if(type==ConflictGraph.COARSE_GRAIN_EDGE){ + return true; + } + return false; + } + + public String toString() { + return getVertexU() + "-" + getVertexV(); + } + +} diff --git a/Robust/src/Analysis/OoOJava/ConflictGraph.java b/Robust/src/Analysis/OoOJava/ConflictGraph.java new file mode 100644 index 00000000..224790a0 --- /dev/null +++ b/Robust/src/Analysis/OoOJava/ConflictGraph.java @@ -0,0 +1,312 @@ +package Analysis.OoOJava; + +import java.io.BufferedWriter; +import java.io.FileWriter; +import java.util.Collection; +import java.util.HashSet; +import java.util.Hashtable; +import java.util.Iterator; +import java.util.Map; +import java.util.Set; +import java.util.Map.Entry; + +import Analysis.Disjoint.AllocSite; +import Analysis.Disjoint.Effect; +import Analysis.Disjoint.Taint; +import IR.Flat.FlatSESEEnterNode; +import IR.Flat.TempDescriptor; + +public class ConflictGraph { + + public Hashtable id2cn; + + public static final int NON_WRITE_CONFLICT = 0; + public static final int FINE_GRAIN_EDGE = 1; + public static final int COARSE_GRAIN_EDGE = 2; + + public ConflictGraph() { + id2cn = new Hashtable(); + } + + public void addLiveInNodeEffect(Taint t, Effect e) { + FlatSESEEnterNode sese = t.getSESE(); + TempDescriptor invar = t.getVar(); + AllocSite as = t.getAllocSite(); + + String id = invar + "_" + sese.getIdentifier(); + + ConflictNode node = id2cn.get(id); + if (node == null) { + node = new ConflictNode(id, ConflictNode.INVAR); + } + + if (!id2cn.containsKey(id)) { + + } else { + node = id2cn.get(id); + } + node.addEffect(as, e); + + id2cn.put(id, node); + } + + public void addConflictEdge(int type, ConflictNode nodeU, ConflictNode nodeV) { + + // if there are two edges between the same node pair, coarse has a + // priority + Set set = nodeU.getEdgeSet(); + ConflictEdge toBeRemoved = null; + for (Iterator iterator = set.iterator(); iterator.hasNext();) { + ConflictEdge conflictEdge = (ConflictEdge) iterator.next(); + + if ((conflictEdge.getVertexU().equals(nodeU) && conflictEdge.getVertexV().equals(nodeV)) + || (conflictEdge.getVertexU().equals(nodeV) && conflictEdge.getVertexV().equals(nodeU))) { + if (conflictEdge.getType() == ConflictGraph.FINE_GRAIN_EDGE + && type == ConflictGraph.COARSE_GRAIN_EDGE) { + toBeRemoved = conflictEdge; + break; + } else if (conflictEdge.getType() == ConflictGraph.COARSE_GRAIN_EDGE + && type == ConflictGraph.FINE_GRAIN_EDGE) { + // ignore + return; + } + } + } + + if (toBeRemoved != null) { + nodeU.getEdgeSet().remove(toBeRemoved); + nodeV.getEdgeSet().remove(toBeRemoved); + } + + ConflictEdge newEdge = new ConflictEdge(nodeU, nodeV, type); + nodeU.addEdge(newEdge); + nodeV.addEdge(newEdge); + + } + + public void analyzeConflicts() { + + Set keySet = id2cn.keySet(); + Set analyzedIDSet = new HashSet(); + + for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { + String nodeID = (String) iterator.next(); + ConflictNode node = id2cn.get(nodeID); + analyzePossibleConflicts(analyzedIDSet, node); + } + + } + + private void analyzePossibleConflicts(Set analyzedIDSet, ConflictNode currentNode) { + // compare with all nodes + // examine the case where self-edge exists + if (currentNode.isInVarNode()) { + // LiveInNode liveInNode = (LiveInNode) currentNode; + // int conflictType=calculateSelfConflictType(liveInNode); + // if(conflictType>0){ + // addConflictEdge(conflictType, currentNode, + // currentNode); + // } + } + + Set> set = id2cn.entrySet(); + for (Iterator iterator = set.iterator(); iterator.hasNext();) { + Entry entry = (Entry) iterator.next(); + + String entryNodeID = entry.getKey(); + ConflictNode entryNode = entry.getValue(); + + if ((!currentNode.getID().equals(entryNodeID)) + && !(analyzedIDSet.contains(currentNode.getID() + entryNodeID) || analyzedIDSet + .contains(entryNodeID + currentNode.getID()))) { + + if (currentNode.isStallSiteNode() && entryNode.isInVarNode()) { + /* + * int conflictType = calculateConflictType((StallSiteNode) + * currentNode, (LiveInNode) entryNode); if (conflictType > 0) { + * addConflictEdge(conflictType, currentNode, entryNode); } + * + * analyzedIDSet.add(currentNode.getID() + entryNodeID); + */ + } else if (currentNode.isInVarNode() && entryNode.isInVarNode()) { + int conflictType = calculateConflictType(currentNode, entryNode); + if (conflictType > ConflictGraph.NON_WRITE_CONFLICT) { + addConflictEdge(conflictType, currentNode, entryNode); + } + analyzedIDSet.add(currentNode.getID() + entryNodeID); + } + } + } + + } + + private int calculateConflictType(ConflictNode nodeA, ConflictNode nodeB) { + + int conflictType = ConflictGraph.NON_WRITE_CONFLICT; + + // if node A has write effects on reading/writing regions of node B + Hashtable> alloc2readEffectsA = nodeA.getReadEffectSet(); + Hashtable> alloc2writeEffectsA = nodeA.getWriteEffectSet(); + Hashtable> alloc2readEffectsB = nodeB.getReadEffectSet(); + Hashtable> alloc2writeEffectsB = nodeB.getWriteEffectSet(); + + conflictType = updateConflictType(conflictType, determineConflictType(alloc2writeEffectsA, + alloc2readEffectsB)); + conflictType = updateConflictType(conflictType, determineConflictType(alloc2writeEffectsA, + alloc2writeEffectsB)); + + // if node B has write effects on reading regions of node A + determineConflictType(alloc2writeEffectsB, alloc2readEffectsA); + + return conflictType; + } + + private int determineConflictType(Hashtable> nodeAtable, + Hashtable> nodeBtable) { + + int conflictType = ConflictGraph.NON_WRITE_CONFLICT; + + Iterator effectItrA = nodeAtable.entrySet().iterator(); + while (effectItrA.hasNext()) { + Map.Entry meA = (Map.Entry) effectItrA.next(); + AllocSite asA = (AllocSite) meA.getKey(); + Set esA = (Set) meA.getValue(); + + Iterator effectItrB = nodeBtable.entrySet().iterator(); + while (effectItrB.hasNext()) { + Map.Entry meB = (Map.Entry) effectItrB.next(); + AllocSite asB = (AllocSite) meA.getKey(); + Set esB = (Set) meA.getValue(); + + for (Iterator iterator = esA.iterator(); iterator.hasNext();) { + Effect effectA = (Effect) iterator.next(); + for (Iterator iterator2 = esB.iterator(); iterator2.hasNext();) { + Effect effectB = (Effect) iterator2.next(); + + if (effectA.getAffectedAllocSite().equals(effectB.getAffectedAllocSite()) + && effectA.getField().equals(effectB.getField())) { + // possible conflict + /* + * if(og.isReachable(asA, asB, effectA.getAffectedAllocSite())){ + * //affected allocation site can be reached from both heap roots + * if(isFineGrainConflict()){ + * conflictType=updateConflictType(conflictType + * ,ConflictGraph.FINE_GRAIN_EDGE); }else{ + * conflictType=updateConflictType + * (conflictType,ConflictGraph.COARSE_GRAIN_EDGE); } } + */ + } + } + } + } + } + + return ConflictGraph.FINE_GRAIN_EDGE; + // return conflictType; + } + + private int updateConflictType(int current, int newType) { + if (newType > current) { + return newType; + } else { + return current; + } + } + + public HashSet getEdgeSet() { + + HashSet returnSet = new HashSet(); + + Collection nodes = id2cn.values(); + for (Iterator iterator = nodes.iterator(); iterator.hasNext();) { + ConflictNode conflictNode = (ConflictNode) iterator.next(); + returnSet.addAll(conflictNode.getEdgeSet()); + } + + return returnSet; + } + + public boolean hasConflictEdge() { + + Set keySet = id2cn.keySet(); + for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { + String key = (String) iterator.next(); + ConflictNode node = id2cn.get(key); + if (node.getEdgeSet().size() > 0) { + return true; + } + } + return false; + } + + public void writeGraph(String graphName, boolean filter) throws java.io.IOException { + + graphName = graphName.replaceAll("[\\W]", ""); + + BufferedWriter bw = new BufferedWriter(new FileWriter(graphName + ".dot")); + bw.write("graph " + graphName + " {\n"); + + // then visit every heap region node + Set> s = id2cn.entrySet(); + Iterator> i = s.iterator(); + + HashSet addedSet = new HashSet(); + + while (i.hasNext()) { + Entry entry = i.next(); + ConflictNode node = entry.getValue(); + + if (filter) { + if (node.getID().startsWith("___dst") || node.getID().startsWith("___srctmp") + || node.getID().startsWith("___neverused") || node.getID().startsWith("___temp")) { + + continue; + } + } + + String attributes = "["; + + attributes += "label=\"ID" + node.getID() + "\\n"; + + if (node.isStallSiteNode()) { + attributes += "STALL SITE" + "\\n" + "\"]"; + } else { + attributes += "LIVE-IN" + "\\n" + "\"]"; + } + bw.write(entry.getKey() + attributes + ";\n"); + + Set edgeSet = node.getEdgeSet(); + for (Iterator iterator = edgeSet.iterator(); iterator.hasNext();) { + ConflictEdge conflictEdge = (ConflictEdge) iterator.next(); + + ConflictNode u = conflictEdge.getVertexU(); + ConflictNode v = conflictEdge.getVertexV(); + + if (filter) { + String uID = u.getID(); + String vID = v.getID(); + if (uID.startsWith("___dst") || uID.startsWith("___srctmp") + || uID.startsWith("___neverused") || uID.startsWith("___temp") + || vID.startsWith("___dst") || vID.startsWith("___srctmp") + || vID.startsWith("___neverused") || vID.startsWith("___temp")) { + continue; + } + } + + if (!addedSet.contains(conflictEdge)) { + bw.write(" " + u.getID() + "--" + v.getID() + "[label=" + + conflictEdge.toGraphEdgeString() + ",decorate];\n"); + addedSet.add(conflictEdge); + } + + } + } + + bw.write(" graphTitle[label=\"" + graphName + "\",shape=box];\n"); + + bw.write("}\n"); + bw.close(); + + } + +} diff --git a/Robust/src/Analysis/OoOJava/ConflictNode.java b/Robust/src/Analysis/OoOJava/ConflictNode.java new file mode 100644 index 00000000..c45841ad --- /dev/null +++ b/Robust/src/Analysis/OoOJava/ConflictNode.java @@ -0,0 +1,176 @@ +package Analysis.OoOJava; + +import java.util.HashSet; +import java.util.Hashtable; +import java.util.Set; + +import Analysis.Disjoint.AllocSite; +import Analysis.Disjoint.Effect; +import Analysis.MLP.LiveInNode; + +public class ConflictNode { + + protected HashSet edgeSet; + + protected Hashtable> alloc2readEffectSet; + protected Hashtable> alloc2writeEffectSet; + protected Hashtable> alloc2strongUpdateEffectSet; + + protected int nodeType; + protected int type; + protected String id; + + public static final int FINE_READ = 0; + public static final int FINE_WRITE = 1; + public static final int PARENT_READ = 2; + public static final int PARENT_WRITE = 3; + public static final int COARSE = 4; + public static final int PARENT_COARSE = 5; + public static final int SCC = 6; + + public static final int INVAR = 0; + public static final int STALLSITE = 1; + + public ConflictNode(String id, int nodeType) { + edgeSet = new HashSet(); + + alloc2readEffectSet = new Hashtable>(); + alloc2writeEffectSet = new Hashtable>(); + alloc2strongUpdateEffectSet = new Hashtable>(); + + this.id = id; + this.nodeType = nodeType; + } + + public void addEffect(AllocSite as, Effect e) { + if (e.getType() == Effect.read) { + addReadEffect(as, e); + } else if (e.getType() == Effect.write) { + addWriteEffect(as, e); + } else { + addStrongUpdateEffect(as, e); + } + } + + public void addReadEffect(AllocSite as, Effect e) { + Set effectSet = alloc2readEffectSet.get(as); + if (effectSet == null) { + effectSet = new HashSet(); + } + effectSet.add(e); + + alloc2readEffectSet.put(as, effectSet); + } + + public void addWriteEffect(AllocSite as, Effect e) { + Set effectSet = alloc2writeEffectSet.get(as); + if (effectSet == null) { + effectSet = new HashSet(); + } + effectSet.add(e); + + alloc2writeEffectSet.put(as, effectSet); + } + + public void addStrongUpdateEffect(AllocSite as, Effect e) { + Set effectSet = alloc2strongUpdateEffectSet.get(as); + if (effectSet == null) { + effectSet = new HashSet(); + } + effectSet.add(e); + + alloc2strongUpdateEffectSet.put(as, effectSet); + } + + public Hashtable> getReadEffectSet() { + return alloc2readEffectSet; + } + + public Hashtable> getWriteEffectSet() { + return alloc2writeEffectSet; + } + + public Hashtable> getStrongUpdateEffectSet() { + return alloc2strongUpdateEffectSet; + } + + public boolean isInVarNode() { + if (nodeType == ConflictNode.INVAR) { + return true; + } + return false; + } + + public boolean isStallSiteNode() { + return !isInVarNode(); + } + + public Set getEdgeSet(){ + return edgeSet; + } + + public void addEdge(ConflictEdge edge) { + edgeSet.add(edge); + } + + // public Set getReadEffectSet() { + // return readEffectSet; + // } + // + // public Set getWriteEffectSet() { + // return writeEffectSet; + // } + // + // public Set getStrongUpdateEffectSet() { + // return strongUpdateEffectSet; + // } + + public int getType() { + return type; + } + + public String getID() { + return id; + } + + public boolean equals(Object o) { + + if (o == null) { + return false; + } + + if (!(o instanceof ConflictNode)) { + return false; + } + + ConflictNode in = (ConflictNode) o; + + if (id.equals(in.id)) { + return true; + } else { + return false; + } + + } + + + public String toString() { + + String str = ""; + + if (!alloc2readEffectSet.isEmpty()) { + str += "read effect= " + alloc2readEffectSet.toString() + "\n"; + } + + if (!alloc2writeEffectSet.isEmpty()) { + str += "write effect = " + alloc2writeEffectSet.toString() + "\n"; + } + + if (!alloc2strongUpdateEffectSet.isEmpty()) { + str += "SU effect = " + alloc2strongUpdateEffectSet.toString() + "\n"; + } + + return str; + } + +} diff --git a/Robust/src/Analysis/OoOJava/OoOJavaAnalysis.java b/Robust/src/Analysis/OoOJava/OoOJavaAnalysis.java index a8dac553..81021b1a 100644 --- a/Robust/src/Analysis/OoOJava/OoOJavaAnalysis.java +++ b/Robust/src/Analysis/OoOJava/OoOJavaAnalysis.java @@ -1,16 +1,22 @@ package Analysis.OoOJava; +import java.io.IOException; +import java.util.Enumeration; import java.util.HashSet; import java.util.Hashtable; import java.util.Iterator; import java.util.Set; import java.util.Stack; +import java.util.Map.Entry; -import Analysis.CallGraph.CallGraph; import Analysis.ArrayReferencees; import Analysis.Liveness; import Analysis.RBlockRelationAnalysis; +import Analysis.CallGraph.CallGraph; import Analysis.Disjoint.DisjointAnalysis; +import Analysis.Disjoint.Effect; +import Analysis.Disjoint.EffectsAnalysis; +import Analysis.Disjoint.Taint; import IR.Descriptor; import IR.MethodDescriptor; import IR.Operation; @@ -21,7 +27,6 @@ import IR.Flat.FlatEdge; import IR.Flat.FlatMethod; import IR.Flat.FlatNode; import IR.Flat.FlatOpNode; -import IR.Flat.FlatReturnNode; import IR.Flat.FlatSESEEnterNode; import IR.Flat.FlatSESEExitNode; import IR.Flat.FlatWriteDynamicVarNode; @@ -47,12 +52,21 @@ public class OoOJavaAnalysis { private Hashtable wdvNodesToSpliceIn; -// private Hashtable conflictsResults; -// private Hashtable methodSummaryResults; -// private OwnershipAnalysis ownAnalysisForSESEConflicts; -// private Hashtable conflictGraphResults; + // temporal data structures to track analysis progress. + static private int uniqueLockSetId = 0; + // mapping of a conflict graph to its compiled lock + private Hashtable> conflictGraph2SESELock; + // 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; + // static private int uniqueLockSetId = 0; public static int maxSESEage = -1; @@ -66,11 +80,8 @@ public class OoOJavaAnalysis { return cp; } - public OoOJavaAnalysis(State state, - TypeUtil typeUtil, - CallGraph callGraph, - Liveness liveness, - ArrayReferencees arrayReferencees) { + public OoOJavaAnalysis(State state, TypeUtil typeUtil, CallGraph callGraph, Liveness liveness, + ArrayReferencees arrayReferencees) { double timeStartAnalysis = (double) System.nanoTime(); @@ -88,20 +99,21 @@ public class OoOJavaAnalysis { notAvailableIntoSESE = new Hashtable>(); + sese2conflictGraph = new Hashtable(); + conflictGraph2SESELock = new Hashtable>(); + // add all methods transitively reachable from the - // source's main to set for analysis + // source's main to set for analysis MethodDescriptor mdSourceEntry = typeUtil.getMain(); - FlatMethod fmMain = state.getMethodFlat( mdSourceEntry ); - - Set descriptorsToAnalyze = - callGraph.getAllMethods( mdSourceEntry ); - - descriptorsToAnalyze.add( mdSourceEntry ); - + FlatMethod fmMain = state.getMethodFlat(mdSourceEntry); -// conflictsResults = new Hashtable(); -// methodSummaryResults = new Hashtable(); -// conflictGraphResults = new Hashtable(); + Set descriptorsToAnalyze = callGraph.getAllMethods(mdSourceEntry); + + descriptorsToAnalyze.add(mdSourceEntry); + + // conflictsResults = new Hashtable(); + // methodSummaryResults = new Hashtable(); + // conflictGraphResults = new Hashtable(); // seseSummaryMap = new Hashtable(); // isAfterChildSESEIndicatorMap = new Hashtable(); @@ -109,16 +121,15 @@ public class OoOJavaAnalysis { // 1st pass, find basic rblock relations rblockRel = new RBlockRelationAnalysis(state, typeUtil, callGraph); - + // 2nd pass, liveness, in-set out-set (no virtual reads yet!) - Iterator rootItr = - rblockRel.getRootSESEs().iterator(); + Iterator rootItr = rblockRel.getRootSESEs().iterator(); while (rootItr.hasNext()) { FlatSESEEnterNode root = rootItr.next(); livenessAnalysisBackward(root, true, null); } - // 3rd pass, variable analysis + // 3rd pass, variable analysis Iterator methItr = descriptorsToAnalyze.iterator(); while (methItr.hasNext()) { Descriptor d = methItr.next(); @@ -136,17 +147,12 @@ public class OoOJavaAnalysis { FlatSESEEnterNode root = rootItr.next(); livenessAnalysisBackward(root, true, null); } - + // 5th pass, use disjointness with NO FLAGGED REGIONS // to compute taints and effects - disjointAnalysisTaints = - new DisjointAnalysis(state, - typeUtil, - callGraph, - liveness, - arrayReferencees, - rblockRel); - + disjointAnalysisTaints = new DisjointAnalysis(state, typeUtil, callGraph, liveness, + arrayReferencees, rblockRel); + // 6th pass, not available analysis FOR VARIABLES! methItr = descriptorsToAnalyze.iterator(); while (methItr.hasNext()) { @@ -158,11 +164,42 @@ public class OoOJavaAnalysis { notAvailableForward(fm); } - // MORE PASSES? + /* + // #th pass, make conflict graph + // conflict graph is maintained by each parent sese + methItr = descriptorsToAnalyze.iterator(); + while (methItr.hasNext()) { + Descriptor d = methItr.next(); + FlatMethod fm = state.getMethodFlat(d); + makeConflictGraph(fm); + } + + // 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("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.toString()); + } + } + // #th pass, calculate conflicts + calculateConflicts(); - } + // #th pass, compiling locks + synthesizeLocks(); + // #th pass, writing conflict graph + writeConflictGraph(); + */ + + } private void livenessAnalysisBackward(FlatSESEEnterNode fsen, boolean toplevel, Hashtable> liveout) { @@ -297,7 +334,7 @@ public class OoOJavaAnalysis { Stack seseStack = rblockRel.getRBlockStacks(fm, fn); assert seseStack != null; - + VarSrcTokTable prev = variableResults.get(fn); // merge sets from control flow joins @@ -599,4 +636,370 @@ public class OoOJavaAnalysis { } // end switch } + private void makeConflictGraph(FlatMethod fm) { + + Set flatNodesToVisit = new HashSet(); + flatNodesToVisit.add(fm); + + Set visited = new HashSet(); + + while (!flatNodesToVisit.isEmpty()) { + FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next(); + flatNodesToVisit.remove(fn); + visited.add(fn); + + Stack seseStack = rblockRel.getRBlockStacks(fm, fn); + assert seseStack != null; + + if (!seseStack.isEmpty()) { + + // Add Stall Node of current program statement + + ConflictGraph conflictGraph = sese2conflictGraph.get(seseStack.peek()); + if (conflictGraph == null) { + conflictGraph = new ConflictGraph(); + } + + conflictGraph_nodeAction(fn, seseStack.peek()); + + } + + // 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); + } + } + + } + + } + + + private void conflictGraph_nodeAction(FlatNode fn, FlatSESEEnterNode currentSESE) { + + switch (fn.kind()) { + + case FKind.FlatSESEEnterNode: { + + FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn; + + if (!fsen.getIsCallerSESEplaceholder() && currentSESE.getParent() != null) { + Set invar_set = fsen.getInVarSet(); + ConflictGraph conflictGraph = sese2conflictGraph.get(currentSESE.getParent()); + if (conflictGraph == null) { + conflictGraph = new ConflictGraph(); + } + + // collects effects set + EffectsAnalysis effectsAnalysis = disjointAnalysisTaints.getEffectsAnalysis(); + Iterator iter=effectsAnalysis.iteratorTaintEffectPairs(); + while(iter.hasNext()){ + Entry entry=(Entry)iter.next(); + Taint taint=(Taint)entry.getKey(); + Set effects=(Set)entry.getValue(); + if(taint.getSESE().equals(currentSESE)){ + Iterator eIter=effects.iterator(); + while (eIter.hasNext()) { + Effect effect = eIter.next(); + if (taint.getSESE().equals(currentSESE)) { + conflictGraph.addLiveInNodeEffect(taint, effect); + } + } + } + + } + + if (conflictGraph.id2cn.size() > 0) { + sese2conflictGraph.put(currentSESE.getParent(), conflictGraph); + } + } + } + break; + } + + } + + private void calculateConflicts() { + // decide fine-grain edge or coarse-grain edge among all vertexes by + // pair-wise comparison + + Iterator seseIter = sese2conflictGraph.keySet().iterator(); + while (seseIter.hasNext()) { + FlatNode sese = seseIter.next(); + ConflictGraph conflictGraph = sese2conflictGraph.get(sese); + conflictGraph.analyzeConflicts(); + sese2conflictGraph.put(sese, conflictGraph); + } + } + + private void writeConflictGraph() { + Enumeration keyEnum = sese2conflictGraph.keys(); + while (keyEnum.hasMoreElements()) { + FlatNode key = (FlatNode) keyEnum.nextElement(); + ConflictGraph cg = sese2conflictGraph.get(key); + try { + if (cg.hasConflictEdge()) { + cg.writeGraph("ConflictGraphFor" + key, false); + } + } catch (IOException e) { + System.out.println("Error writing"); + System.exit(0); + } + } + } + + private void synthesizeLocks() { + Set> graphEntrySet = sese2conflictGraph.entrySet(); + for (Iterator iterator = graphEntrySet.iterator(); iterator.hasNext();) { + Entry graphEntry = (Entry) iterator.next(); + FlatNode sese = graphEntry.getKey(); + ConflictGraph conflictGraph = graphEntry.getValue(); + calculateCovering(conflictGraph); + } + } + + private void calculateCovering(ConflictGraph conflictGraph) { + uniqueLockSetId = 0; // reset lock counter for every new conflict graph + HashSet fineToCover = new HashSet(); + HashSet coarseToCover = new HashSet(); + HashSet lockSet = new HashSet(); + + Set tempCover = conflictGraph.getEdgeSet(); + for (Iterator iterator = tempCover.iterator(); iterator.hasNext();) { + ConflictEdge conflictEdge = (ConflictEdge) iterator.next(); + if (conflictEdge.isCoarseEdge()) { + coarseToCover.add(conflictEdge); + } else { + fineToCover.add(conflictEdge); + } + } + + HashSet toCover = new HashSet(); + toCover.addAll(fineToCover); + toCover.addAll(coarseToCover); + + while (!toCover.isEmpty()) { + + SESELock seseLock = new SESELock(); + seseLock.setID(uniqueLockSetId++); + + boolean changed; + + do { // fine-grained edge + + changed = false; + + for (Iterator iterator = fineToCover.iterator(); iterator.hasNext();) { + + int type; + ConflictEdge edge = (ConflictEdge) iterator.next(); + if (seseLock.getConflictNodeSet().size() == 0) { + // initial setup + if (seseLock.isWriteNode(edge.getVertexU())) { + // mark as fine_write + if (edge.getVertexU().isStallSiteNode()) { + type = ConflictNode.PARENT_WRITE; + } else { + type = ConflictNode.FINE_WRITE; + } + seseLock.addConflictNode(edge.getVertexU(), type); + } else { + // mark as fine_read + if (edge.getVertexU().isStallSiteNode()) { + type = ConflictNode.PARENT_READ; + } else { + type = ConflictNode.FINE_READ; + } + seseLock.addConflictNode(edge.getVertexU(), type); + } + if (edge.getVertexV() != edge.getVertexU()) { + if (seseLock.isWriteNode(edge.getVertexV())) { + // mark as fine_write + if (edge.getVertexV().isStallSiteNode()) { + type = ConflictNode.PARENT_WRITE; + } else { + type = ConflictNode.FINE_WRITE; + } + seseLock.addConflictNode(edge.getVertexV(), type); + } else { + // mark as fine_read + if (edge.getVertexV().isStallSiteNode()) { + type = ConflictNode.PARENT_READ; + } else { + type = ConflictNode.FINE_READ; + } + seseLock.addConflictNode(edge.getVertexV(), type); + } + } + changed = true; + seseLock.addConflictEdge(edge); + fineToCover.remove(edge); + break;// exit iterator loop + }// end of initial setup + + ConflictNode newNode; + if ((newNode = seseLock.getNewNodeConnectedWithGroup(edge)) != null) { + // new node has a fine-grained edge to all current node + // If there is a coarse grained edge where need a fine edge, it's + // okay to add the node + // but the edge must remain uncovered. + + changed = true; + + if (seseLock.isWriteNode(newNode)) { + if (newNode.isStallSiteNode()) { + type = ConflictNode.PARENT_WRITE; + } else { + type = ConflictNode.FINE_WRITE; + } + seseLock.setNodeType(newNode, type); + } else { + if (newNode.isStallSiteNode()) { + type = ConflictNode.PARENT_READ; + } else { + type = ConflictNode.FINE_READ; + } + seseLock.setNodeType(newNode, type); + } + + seseLock.addEdge(edge); + Set edgeSet = newNode.getEdgeSet(); + 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 + // covered + if (!conflictEdge.getVertexU().equals(newNode)) { + if (seseLock.containsConflictNode(conflictEdge.getVertexU())) { + changed = true; + seseLock.addConflictEdge(conflictEdge); + fineToCover.remove(conflictEdge); + } + } else if (!conflictEdge.getVertexV().equals(newNode)) { + if (seseLock.containsConflictNode(conflictEdge.getVertexV())) { + changed = true; + seseLock.addConflictEdge(conflictEdge); + fineToCover.remove(conflictEdge); + } + } + + } + + break;// exit iterator loop + } + } + + } while (changed); + do { // coarse + changed = false; + int type; + for (Iterator iterator = coarseToCover.iterator(); iterator.hasNext();) { + + ConflictEdge edge = (ConflictEdge) iterator.next(); + + if (seseLock.getConflictNodeSet().size() == 0) { + // initial setup + if (seseLock.hasSelfCoarseEdge(edge.getVertexU())) { + // node has a coarse-grained edge with itself + if (!(edge.getVertexU().isStallSiteNode())) { + // and it is not parent + type = ConflictNode.SCC; + } else { + type = ConflictNode.PARENT_COARSE; + } + seseLock.addConflictNode(edge.getVertexU(), type); + } else { + if (edge.getVertexU().isStallSiteNode()) { + type = ConflictNode.PARENT_COARSE; + } else { + type = ConflictNode.COARSE; + } + seseLock.addConflictNode(edge.getVertexU(), type); + } + if (seseLock.hasSelfCoarseEdge(edge.getVertexV())) { + // node has a coarse-grained edge with itself + if (!(edge.getVertexV().isStallSiteNode())) { + // and it is not parent + type = ConflictNode.SCC; + } else { + type = ConflictNode.PARENT_COARSE; + } + seseLock.addConflictNode(edge.getVertexV(), type); + } else { + if (edge.getVertexV().isStallSiteNode()) { + type = ConflictNode.PARENT_COARSE; + } else { + type = ConflictNode.COARSE; + } + seseLock.addConflictNode(edge.getVertexV(), type); + } + changed = true; + coarseToCover.remove(edge); + seseLock.addConflictEdge(edge); + 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 (seseLock.hasSelfCoarseEdge(newNode)) { + // SCC + if (newNode.isStallSiteNode()) { + type = ConflictNode.PARENT_COARSE; + } else { + type = ConflictNode.SCC; + } + seseLock.setNodeType(newNode, type); + } else { + if (newNode.isStallSiteNode()) { + type = ConflictNode.PARENT_COARSE; + } else { + type = ConflictNode.COARSE; + } + seseLock.setNodeType(newNode, type); + } + + seseLock.addEdge(edge); + Set edgeSet = newNode.getEdgeSet(); + 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 + if (!conflictEdge.getVertexU().equals(newNode)) { + if (seseLock.containsConflictNode(conflictEdge.getVertexU())) { + changed = true; + seseLock.addConflictEdge(conflictEdge); + coarseToCover.remove(conflictEdge); + } + } else if (!conflictEdge.getVertexV().equals(newNode)) { + if (seseLock.containsConflictNode(conflictEdge.getVertexV())) { + changed = true; + seseLock.addConflictEdge(conflictEdge); + coarseToCover.remove(conflictEdge); + } + } + + } + break;// exit iterator loop + } + + } + + } while (changed); + lockSet.add(seseLock); + + toCover.clear(); + toCover.addAll(fineToCover); + toCover.addAll(coarseToCover); + + } + + conflictGraph2SESELock.put(conflictGraph, lockSet); + } + } diff --git a/Robust/src/Analysis/OoOJava/SESELock.java b/Robust/src/Analysis/OoOJava/SESELock.java new file mode 100644 index 00000000..5891bb0c --- /dev/null +++ b/Robust/src/Analysis/OoOJava/SESELock.java @@ -0,0 +1,206 @@ +package Analysis.OoOJava; + +import java.util.HashMap; +import java.util.HashSet; +import java.util.Iterator; +import java.util.Set; + +public class SESELock { + + private HashSet conflictNodeSet; + private HashSet conflictEdgeSet; + private HashMap nodeTypeMap; + private int id; + + public SESELock() { + conflictNodeSet = new HashSet(); + conflictEdgeSet = new HashSet(); + nodeTypeMap = new HashMap(); + } + + public void addConflictNode(ConflictNode node, int type) { + conflictNodeSet.add(node); + setNodeType(node, type); + } + + public void setNodeType(ConflictNode node, int type) { + nodeTypeMap.put(node, new Integer(type)); + } + + public int getNodeType(ConflictNode node) { + return nodeTypeMap.get(node).intValue(); + } + + public void addConflictEdge(ConflictEdge e) { + conflictEdgeSet.add(e); + } + + public boolean containsConflictEdge(ConflictEdge e) { + return conflictEdgeSet.contains(e); + } + + public HashSet getConflictNodeSet() { + return conflictNodeSet; + } + + public boolean isWriteNode(ConflictNode node) { + if (node.getWriteEffectSet().isEmpty()) { + return false; + } else { + return true; + } + } + + public boolean hasSelfCoarseEdge(ConflictNode node) { + + Set set = node.getEdgeSet(); + for (Iterator iterator = set.iterator(); iterator.hasNext();) { + ConflictEdge conflictEdge = (ConflictEdge) iterator.next(); + + if (conflictEdge.isCoarseEdge() && conflictEdge.getVertexU() == conflictEdge.getVertexV()) { + return true; + } + } + return false; + } + + private boolean isFineNode(ConflictNode node) { + + if (node.getType() < 4) { + return true; + } + + return false; + + } + + public ConflictNode getNewNodeCoarseConnectedWithGroup(ConflictEdge newEdge) { + + // check whether or not the new node has a fine-grained edges to all + // current nodes. + + ConflictNode newNode; + if (conflictNodeSet.contains(newEdge.getVertexU())) { + newNode = newEdge.getVertexV(); + } else if (conflictNodeSet.contains(newEdge.getVertexV())) { + newNode = newEdge.getVertexU(); + } else { + return null; + } + + int count = 0; + Set edgeSet = newNode.getEdgeSet(); + for (Iterator iterator = edgeSet.iterator(); iterator.hasNext();) { + ConflictEdge conflictEdge = (ConflictEdge) iterator.next(); + if (!conflictEdge.getVertexU().equals(newNode) + && conflictNodeSet.contains(conflictEdge.getVertexU()) + && isFineNode(conflictEdge.getVertexU())) { + count++; + } else if (!conflictEdge.getVertexV().equals(newNode) + && conflictNodeSet.contains(conflictEdge.getVertexV()) + && isFineNode(conflictEdge.getVertexU())) { + count++; + } + } + + if (count == conflictNodeSet.size()) { + // connected to all current nodes in group + return newNode; + } + + return null; + + } + + public ConflictNode getNewNodeConnectedWithGroup(ConflictEdge newEdge) { + + // check whether or not the new node has a fine-grained edges to all + // current nodes. + + ConflictNode newNode; + if (conflictNodeSet.contains(newEdge.getVertexU())) { + newNode = newEdge.getVertexV(); + } else if (conflictNodeSet.contains(newEdge.getVertexV())) { + newNode = newEdge.getVertexU(); + } else { + return null; + } + + int count = 0; + Set edgeSet = newNode.getEdgeSet(); + for (Iterator iterator = edgeSet.iterator(); iterator.hasNext();) { + ConflictEdge conflictEdge = (ConflictEdge) iterator.next(); + if (!conflictEdge.getVertexU().equals(newNode) + && conflictNodeSet.contains(conflictEdge.getVertexU())) { + count++; + } else if (!conflictEdge.getVertexV().equals(newNode) + && conflictNodeSet.contains(conflictEdge.getVertexV())) { + count++; + } + } + + if (count == conflictNodeSet.size()) { + // connected to all current nodes in group + return newNode; + } + + return null; + + } + + public void addEdge(ConflictEdge edge) { + conflictNodeSet.add(edge.getVertexU()); + conflictNodeSet.add(edge.getVertexV()); + } + + public int getID() { + return id; + } + + public void setID(int id) { + this.id = id; + } + + public boolean containsConflictNode(ConflictNode node) { + + return conflictNodeSet.contains(node); + + } + + public boolean testEdge(ConflictEdge newEdge) { + + if (!conflictNodeSet.contains(newEdge.getVertexU()) + && !conflictNodeSet.contains(newEdge.getVertexV())) { + return false; + } + + ConflictNode nodeToAdd = conflictNodeSet.contains(newEdge.getVertexU()) ? newEdge.getVertexV() + : newEdge.getVertexU(); + + HashSet nodeSet = new HashSet(conflictNodeSet); + + for (Iterator edgeIter = nodeToAdd.getEdgeSet().iterator(); edgeIter.hasNext();) { + ConflictEdge edge = (ConflictEdge) edgeIter.next(); + if (nodeSet.contains(edge.getVertexU())) { + nodeSet.remove(edge.getVertexU()); + } else if (nodeSet.contains(edge.getVertexV())) { + nodeSet.remove(edge.getVertexV()); + } + } + + return nodeSet.isEmpty(); + + } + + public String toString() { + String rtr = ""; + + for (Iterator iterator = conflictNodeSet.iterator(); iterator.hasNext();) { + ConflictNode node = (ConflictNode) iterator.next(); + rtr += " " + node + "::" + getNodeType(node); + } + + return rtr; + } + +}