From dbc671bc1c6957945000ca681aa9c0af4c0b9515 Mon Sep 17 00:00:00 2001 From: yeom Date: Tue, 29 Jun 2010 17:05:53 +0000 Subject: [PATCH] changes. --- .../Analysis/Disjoint/EffectsAnalysis.java | 56 ++++++ .../src/Analysis/OoOJava/ConflictGraph.java | 189 ++++++++++++++++-- Robust/src/Analysis/OoOJava/ConflictNode.java | 24 +-- .../src/Analysis/OoOJava/OoOJavaAnalysis.java | 74 ++++--- 4 files changed, 282 insertions(+), 61 deletions(-) diff --git a/Robust/src/Analysis/Disjoint/EffectsAnalysis.java b/Robust/src/Analysis/Disjoint/EffectsAnalysis.java index 4d3b851e..52244a53 100644 --- a/Robust/src/Analysis/Disjoint/EffectsAnalysis.java +++ b/Robust/src/Analysis/Disjoint/EffectsAnalysis.java @@ -1,11 +1,13 @@ package Analysis.Disjoint; import java.util.*; +import java.util.Map.Entry; import java.io.*; import IR.FieldDescriptor; import IR.Flat.FlatCall; import IR.Flat.FlatMethod; +import IR.Flat.FlatNode; import IR.Flat.TempDescriptor; import IR.Flat.FlatSESEEnterNode; @@ -47,6 +49,60 @@ public class EffectsAnalysis { public Iterator iteratorTaintEffectPairs() { return taint2effects.entrySet().iterator(); } + + public Hashtable> getSESEEffects(FlatSESEEnterNode sese){ + + Hashtable> taint2Effects = new Hashtable>(); + Iterator iter=iteratorTaintEffectPairs(); + while (iter.hasNext()) { + Entry entry = (Entry) iter.next(); + Taint taint = (Taint) entry.getKey(); + Set effects = (Set) entry.getValue(); + if (taint.getSESE().equals(sese)) { + Iterator eIter = effects.iterator(); + while (eIter.hasNext()) { + Effect effect = eIter.next(); + if (taint.getSESE().equals(sese)) { + Set effectSet = taint2Effects.get(taint); + if (effectSet == null) { + effectSet = new HashSet(); + } + effectSet.add(effect); + taint2Effects.put(taint, effectSet); + } + } + } + } + + return taint2Effects; + + } + + public Hashtable> getStallSiteEffects(FlatNode fn, TempDescriptor td){ + + Hashtable> taint2Effects = new Hashtable>(); + Iterator iter=iteratorTaintEffectPairs(); + while(iter.hasNext()){ + Entry entry=(Entry)iter.next(); + Taint taint=(Taint)entry.getKey(); + Set effects=(Set)entry.getValue(); + if(taint.getStallSite().equals(fn)){ + Iterator eIter=effects.iterator(); + while (eIter.hasNext()) { + Effect effect = eIter.next(); + if( taint.getStallSite().equals(fn) && taint.getVar().equals(td) ){ + Set effectSet=taint2Effects.get(taint); + if(effectSet==null){ + effectSet=new HashSet(); + } + effectSet.add(effect); + taint2Effects.put(taint, effectSet); + } + } + } + } + return taint2Effects; + } protected void add(Taint t, Effect e) { diff --git a/Robust/src/Analysis/OoOJava/ConflictGraph.java b/Robust/src/Analysis/OoOJava/ConflictGraph.java index 35017612..45b1cec6 100644 --- a/Robust/src/Analysis/OoOJava/ConflictGraph.java +++ b/Robust/src/Analysis/OoOJava/ConflictGraph.java @@ -13,6 +13,7 @@ import java.util.Map.Entry; import Analysis.Disjoint.AllocSite; import Analysis.Disjoint.Effect; import Analysis.Disjoint.Taint; +import IR.Flat.FlatNode; import IR.Flat.FlatSESEEnterNode; import IR.Flat.TempDescriptor; @@ -27,6 +28,60 @@ public class ConflictGraph { public ConflictGraph() { id2cn = new Hashtable(); } + + public void addLiveIn(Hashtable> taint2Effects) { + Iterator entryIter = taint2Effects.entrySet().iterator(); + while (entryIter.hasNext()) { + Entry entry = (Entry) entryIter.next(); + Taint taint = (Taint) entry.getKey(); + Set effectSet = (Set) entry.getValue(); + if (!effectSet.isEmpty()) { + Iterator effectIter = effectSet.iterator(); + while (effectIter.hasNext()) { + Effect effect = (Effect) effectIter.next(); + addLiveInNodeEffect(taint, effect); + } + } + } + } + + public void addStallSite(Hashtable> taint2Effects) { + Iterator entryIter = taint2Effects.entrySet().iterator(); + while (entryIter.hasNext()) { + Entry entry = (Entry) entryIter.next(); + Taint taint = (Taint) entry.getKey(); + Set effectSet = (Set) entry.getValue(); + if (!effectSet.isEmpty()) { + Iterator effectIter = effectSet.iterator(); + while (effectIter.hasNext()) { + Effect effect = (Effect) effectIter.next(); + addStallSiteEffect(taint, effect); + } + } + } + } + + public void addStallSiteEffect(Taint t, Effect e) { + FlatNode fn = t.getStallSite(); + TempDescriptor var = t.getVar(); + AllocSite as = t.getAllocSite(); + + String id = var + "_" + fn; + 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 addLiveInNodeEffect(Taint t, Effect e) { FlatSESEEnterNode sese = t.getSESE(); @@ -100,13 +155,13 @@ public class ConflictGraph { private void analyzePossibleConflicts(Set analyzedIDSet, ConflictNode currentNode) { // compare with all nodes // examine the case where self-edge exists + + int conflictType; if (currentNode.isInVarNode()) { - // LiveInNode liveInNode = (LiveInNode) currentNode; - // int conflictType=calculateSelfConflictType(liveInNode); - // if(conflictType>0){ - // addConflictEdge(conflictType, currentNode, - // currentNode); - // } + conflictType = calculateConflictType(currentNode); + if (conflictType > ConflictGraph.NON_WRITE_CONFLICT) { + addConflictEdge(conflictType, currentNode, currentNode); + } } Set> set = id2cn.entrySet(); @@ -129,7 +184,7 @@ public class ConflictGraph { * analyzedIDSet.add(currentNode.getID() + entryNodeID); */ } else if (currentNode.isInVarNode() && entryNode.isInVarNode()) { - int conflictType = calculateConflictType(currentNode, entryNode); + conflictType = calculateConflictType(currentNode, entryNode); if (conflictType > ConflictGraph.NON_WRITE_CONFLICT) { addConflictEdge(conflictType, currentNode, entryNode); } @@ -140,27 +195,134 @@ public class ConflictGraph { } + private int calculateConflictType(ConflictNode node) { + + int conflictType = ConflictGraph.NON_WRITE_CONFLICT; + Hashtable> alloc2readEffects = node.getReadEffectSet(); + Hashtable> alloc2writeEffects = node.getWriteEffectSet(); + Hashtable> alloc2SUEffects = node.getStrongUpdateEffectSet(); + + conflictType = + updateConflictType(conflictType, determineConflictType(alloc2writeEffects, + alloc2writeEffects)); + + conflictType = + updateConflictType(conflictType, hasStrongUpdateConflicts(alloc2SUEffects, + alloc2readEffects, alloc2writeEffects)); + + return conflictType; + } + private int calculateConflictType(ConflictNode nodeA, ConflictNode nodeB) { int conflictType = ConflictGraph.NON_WRITE_CONFLICT; Hashtable> alloc2readEffectsA = nodeA.getReadEffectSet(); Hashtable> alloc2writeEffectsA = nodeA.getWriteEffectSet(); + Hashtable> alloc2SUEffectsA = nodeA.getStrongUpdateEffectSet(); Hashtable> alloc2readEffectsB = nodeB.getReadEffectSet(); Hashtable> alloc2writeEffectsB = nodeB.getWriteEffectSet(); + Hashtable> alloc2SUEffectsB = nodeB.getStrongUpdateEffectSet(); // if node A has write effects on reading/writing regions of node B - conflictType = updateConflictType(conflictType, determineConflictType(alloc2writeEffectsA, - alloc2readEffectsB)); - conflictType = updateConflictType(conflictType, determineConflictType(alloc2writeEffectsA, - alloc2writeEffectsB)); + 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); + // strong udpate effects conflict with all effects + // on objects that are reachable from the same heap roots + // if node A has SU on regions of node B + if (!alloc2SUEffectsA.isEmpty()) { + conflictType = + updateConflictType(conflictType, hasStrongUpdateConflicts(alloc2SUEffectsA, + alloc2readEffectsB, alloc2writeEffectsB)); + } + + // if node B has SU on regions of node A + if (!alloc2SUEffectsB.isEmpty()) { + conflictType = + updateConflictType(conflictType, hasStrongUpdateConflicts(alloc2SUEffectsB, + alloc2readEffectsA, alloc2writeEffectsA)); + } + return conflictType; } + private int hasStrongUpdateConflicts(Hashtable> SUEffectsTableA, + Hashtable> readTableB, Hashtable> writeTableB) { + + int conflictType = ConflictGraph.NON_WRITE_CONFLICT; + + Iterator effectItrA = SUEffectsTableA.entrySet().iterator(); + while (effectItrA.hasNext()) { + Map.Entry meA = (Map.Entry) effectItrA.next(); + AllocSite asA = (AllocSite) meA.getKey(); + Set strongUpdateSetA = (Set) meA.getValue(); + + Iterator effectItrB = readTableB.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 = strongUpdateSetA.iterator(); iterator.hasNext();) { + Effect strongUpdateA = (Effect) iterator.next(); + for (Iterator iterator2 = esB.iterator(); iterator2.hasNext();) { + Effect effectB = (Effect) iterator2.next(); + + if (strongUpdateA.getAffectedAllocSite().equals(effectB.getAffectedAllocSite()) + && strongUpdateA.getField().equals(effectB.getField())) { + // possible conflict + // check affected allocation site can be reached from both heap + // roots + // if(og.isReachable(asA, asB, + // strongUpdateA.getAffectedAllocSite()){ + // return ConflictGraph.COARSE_GRAIN_EDGE; + // } + } + + } + } + } + + effectItrB = writeTableB.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 = strongUpdateSetA.iterator(); iterator.hasNext();) { + Effect strongUpdateA = (Effect) iterator.next(); + for (Iterator iterator2 = esB.iterator(); iterator2.hasNext();) { + Effect effectB = (Effect) iterator2.next(); + + if (strongUpdateA.getAffectedAllocSite().equals(effectB.getAffectedAllocSite()) + && strongUpdateA.getField().equals(effectB.getField())) { + // possible conflict + // check affected allocation site can be reached from both heap + // roots + // if(og.isReachable(asA, asB, + // strongUpdateA.getAffectedAllocSite()){ + // return ConflictGraph.COARSE_GRAIN_EDGE; + // } + } + + } + } + } + + } + + return conflictType; + + } + private int determineConflictType(Hashtable> nodeAtable, Hashtable> nodeBtable) { @@ -184,7 +346,7 @@ public class ConflictGraph { Effect effectB = (Effect) iterator2.next(); if (effectA.getAffectedAllocSite().equals(effectB.getAffectedAllocSite()) - && effectA.getField().equals(effectB.getField())) { + && effectA.getField().equals(effectB.getField())) { // possible conflict /* * if(og.isReachable(asA, asB, effectA.getAffectedAllocSite())){ @@ -201,8 +363,7 @@ public class ConflictGraph { } } - return ConflictGraph.FINE_GRAIN_EDGE; - // return conflictType; + return conflictType; } private int updateConflictType(int current, int newType) { diff --git a/Robust/src/Analysis/OoOJava/ConflictNode.java b/Robust/src/Analysis/OoOJava/ConflictNode.java index c45841ad..3df327e6 100644 --- a/Robust/src/Analysis/OoOJava/ConflictNode.java +++ b/Robust/src/Analysis/OoOJava/ConflictNode.java @@ -6,7 +6,6 @@ import java.util.Set; import Analysis.Disjoint.AllocSite; import Analysis.Disjoint.Effect; -import Analysis.MLP.LiveInNode; public class ConflictNode { @@ -85,11 +84,11 @@ public class ConflictNode { public Hashtable> getReadEffectSet() { return alloc2readEffectSet; } - + public Hashtable> getWriteEffectSet() { return alloc2writeEffectSet; } - + public Hashtable> getStrongUpdateEffectSet() { return alloc2strongUpdateEffectSet; } @@ -104,8 +103,8 @@ public class ConflictNode { public boolean isStallSiteNode() { return !isInVarNode(); } - - public Set getEdgeSet(){ + + public Set getEdgeSet() { return edgeSet; } @@ -113,18 +112,6 @@ public class ConflictNode { edgeSet.add(edge); } - // public Set getReadEffectSet() { - // return readEffectSet; - // } - // - // public Set getWriteEffectSet() { - // return writeEffectSet; - // } - // - // public Set getStrongUpdateEffectSet() { - // return strongUpdateEffectSet; - // } - public int getType() { return type; } @@ -132,7 +119,7 @@ public class ConflictNode { public String getID() { return id; } - + public boolean equals(Object o) { if (o == null) { @@ -152,7 +139,6 @@ public class ConflictNode { } } - public String toString() { diff --git a/Robust/src/Analysis/OoOJava/OoOJavaAnalysis.java b/Robust/src/Analysis/OoOJava/OoOJavaAnalysis.java index e20b95db..61886d1c 100644 --- a/Robust/src/Analysis/OoOJava/OoOJavaAnalysis.java +++ b/Robust/src/Analysis/OoOJava/OoOJavaAnalysis.java @@ -23,11 +23,13 @@ import IR.State; import IR.TypeUtil; import IR.Flat.FKind; import IR.Flat.FlatEdge; +import IR.Flat.FlatFieldNode; import IR.Flat.FlatMethod; import IR.Flat.FlatNode; import IR.Flat.FlatOpNode; import IR.Flat.FlatSESEEnterNode; import IR.Flat.FlatSESEExitNode; +import IR.Flat.FlatSetFieldNode; import IR.Flat.FlatWriteDynamicVarNode; import IR.Flat.TempDescriptor; @@ -657,6 +659,7 @@ public class OoOJavaAnalysis { if (!seseStack.isEmpty()) { // Add Stall Node of current program statement + // disjointAnalysisTaints.getEffectsAnalysis().getEffects(t); ConflictGraph conflictGraph = sese2conflictGraph.get(seseStack.peek()); if (conflictGraph == null) { @@ -682,6 +685,12 @@ public class OoOJavaAnalysis { private void conflictGraph_nodeAction(FlatNode fn, FlatSESEEnterNode currentSESE) { + EffectsAnalysis effectsAnalysis = disjointAnalysisTaints.getEffectsAnalysis(); + ConflictGraph conflictGraph = sese2conflictGraph.get(currentSESE.getParent()); + if (conflictGraph == null) { + conflictGraph = new ConflictGraph(); + } + switch (fn.kind()) { case FKind.FlatSESEEnterNode: { @@ -689,39 +698,48 @@ public class OoOJavaAnalysis { 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); - } + // collects effects set of invar set and generates invar node + Hashtable> taint2Effects=effectsAnalysis.getSESEEffects(currentSESE); + conflictGraph.addLiveIn(taint2Effects); } } break; + + case FKind.FlatFieldNode: + case FKind.FlatElementNode: { + + FlatFieldNode ffn = (FlatFieldNode) fn; + TempDescriptor rhs = ffn.getSrc(); + + // add stall site + Hashtable> taint2Effects=effectsAnalysis.getStallSiteEffects(fn, rhs); + conflictGraph.addStallSite(taint2Effects); + + } + break; + + case FKind.FlatSetFieldNode: + case FKind.FlatSetElementNode: { + + FlatSetFieldNode fsfn = (FlatSetFieldNode) fn; + TempDescriptor lhs = fsfn.getDst(); + TempDescriptor rhs = fsfn.getSrc(); + + // collects effects of stall site and generates stall site node + Hashtable> taint2Effects=effectsAnalysis.getStallSiteEffects(fn, rhs); + conflictGraph.addStallSite(taint2Effects); + + taint2Effects=effectsAnalysis.getStallSiteEffects(fn, lhs); + conflictGraph.addStallSite(taint2Effects); + + } + break; } + if (conflictGraph.id2cn.size() > 0) { + sese2conflictGraph.put(currentSESE.getParent(), conflictGraph); + } + } private void calculateConflicts() { -- 2.34.1