Robust/src/Analysis/OoOJava/ConflictGraph.java

   1 package Analysis.OoOJava;
   2
   3 import java.io.BufferedWriter;
   4 import java.io.FileWriter;
   5 import java.util.Collection;
   6 import java.util.HashSet;
   7 import java.util.Hashtable;
   8 import java.util.Iterator;
   9 import java.util.Map;
  10 import java.util.Set;
  11 import java.util.Map.Entry;
  12
  13 import Analysis.Disjoint.AllocSite;
  14 import Analysis.Disjoint.Effect;
  15 import Analysis.Disjoint.Taint;
  16 import IR.Flat.FlatSESEEnterNode;
  17 import IR.Flat.TempDescriptor;
  18
  19 public class ConflictGraph {
  20
  21   public Hashtable<String, ConflictNode> id2cn;
  22
  23   public static final int NON_WRITE_CONFLICT = 0;
  24   public static final int FINE_GRAIN_EDGE = 1;
  25   public static final int COARSE_GRAIN_EDGE = 2;
  26
  27   public ConflictGraph() {
  28     id2cn = new Hashtable<String, ConflictNode>();
  29   }
  30
  31   public void addLiveInNodeEffect(Taint t, Effect e) {
  32     FlatSESEEnterNode sese = t.getSESE();
  33     TempDescriptor invar = t.getVar();
  34     AllocSite as = t.getAllocSite();
  35
  36     String id = invar + "_" + sese.getIdentifier();
  37
  38     ConflictNode node = id2cn.get(id);
  39     if (node == null) {
  40       node = new ConflictNode(id, ConflictNode.INVAR);
  41     }
  42
  43     if (!id2cn.containsKey(id)) {
  44
  45     } else {
  46       node = id2cn.get(id);
  47     }
  48     node.addEffect(as, e);
  49
  50     id2cn.put(id, node);
  51   }
  52
  53   public void addConflictEdge(int type, ConflictNode nodeU, ConflictNode nodeV) {
  54
  55     // if there are two edges between the same node pair, coarse has a
  56     // priority
  57     Set<ConflictEdge> set = nodeU.getEdgeSet();
  58     ConflictEdge toBeRemoved = null;
  59     for (Iterator iterator = set.iterator(); iterator.hasNext();) {
  60       ConflictEdge conflictEdge = (ConflictEdge) iterator.next();
  61
  62       if ((conflictEdge.getVertexU().equals(nodeU) && conflictEdge.getVertexV().equals(nodeV))
  63           || (conflictEdge.getVertexU().equals(nodeV) && conflictEdge.getVertexV().equals(nodeU))) {
  64         if (conflictEdge.getType() == ConflictGraph.FINE_GRAIN_EDGE
  65             && type == ConflictGraph.COARSE_GRAIN_EDGE) {
  66           toBeRemoved = conflictEdge;
  67           break;
  68         } else if (conflictEdge.getType() == ConflictGraph.COARSE_GRAIN_EDGE
  69             && type == ConflictGraph.FINE_GRAIN_EDGE) {
  70           // ignore
  71           return;
  72         }
  73       }
  74     }
  75
  76     if (toBeRemoved != null) {
  77       nodeU.getEdgeSet().remove(toBeRemoved);
  78       nodeV.getEdgeSet().remove(toBeRemoved);
  79     }
  80
  81     ConflictEdge newEdge = new ConflictEdge(nodeU, nodeV, type);
  82     nodeU.addEdge(newEdge);
  83     nodeV.addEdge(newEdge);
  84
  85   }
  86
  87   public void analyzeConflicts() {
  88
  89     Set<String> keySet = id2cn.keySet();
  90     Set<String> analyzedIDSet = new HashSet<String>();
  91
  92     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
  93       String nodeID = (String) iterator.next();
  94       ConflictNode node = id2cn.get(nodeID);
  95       analyzePossibleConflicts(analyzedIDSet, node);
  96     }
  97
  98   }
  99
 100   private void analyzePossibleConflicts(Set<String> analyzedIDSet, ConflictNode currentNode) {
 101     // compare with all nodes
 102     // examine the case where self-edge exists
 103     if (currentNode.isInVarNode()) {
 104       // LiveInNode liveInNode = (LiveInNode) currentNode;
 105       // int conflictType=calculateSelfConflictType(liveInNode);
 106       // if(conflictType>0){
 107       // addConflictEdge(conflictType, currentNode,
 108       // currentNode);
 109       // }
 110     }
 111
 112     Set<Entry<String, ConflictNode>> set = id2cn.entrySet();
 113     for (Iterator iterator = set.iterator(); iterator.hasNext();) {
 114       Entry<String, ConflictNode> entry = (Entry<String, ConflictNode>) iterator.next();
 115
 116       String entryNodeID = entry.getKey();
 117       ConflictNode entryNode = entry.getValue();
 118
 119       if ((!currentNode.getID().equals(entryNodeID))
 120           && !(analyzedIDSet.contains(currentNode.getID() + entryNodeID) || analyzedIDSet
 121               .contains(entryNodeID + currentNode.getID()))) {
 122
 123         if (currentNode.isStallSiteNode() && entryNode.isInVarNode()) {
 124           /*
 125            * int conflictType = calculateConflictType((StallSiteNode)
 126            * currentNode, (LiveInNode) entryNode); if (conflictType > 0) {
 127            * addConflictEdge(conflictType, currentNode, entryNode); }
 128            *
 129            * analyzedIDSet.add(currentNode.getID() + entryNodeID);
 130            */
 131         } else if (currentNode.isInVarNode() && entryNode.isInVarNode()) {
 132           int conflictType = calculateConflictType(currentNode, entryNode);
 133           if (conflictType > ConflictGraph.NON_WRITE_CONFLICT) {
 134             addConflictEdge(conflictType, currentNode, entryNode);
 135           }
 136           analyzedIDSet.add(currentNode.getID() + entryNodeID);
 137         }
 138       }
 139     }
 140
 141   }
 142
 143   private int calculateConflictType(ConflictNode nodeA, ConflictNode nodeB) {
 144
 145     int conflictType = ConflictGraph.NON_WRITE_CONFLICT;
 146
 147     // if node A has write effects on reading/writing regions of node B
 148     Hashtable<AllocSite, Set<Effect>> alloc2readEffectsA = nodeA.getReadEffectSet();
 149     Hashtable<AllocSite, Set<Effect>> alloc2writeEffectsA = nodeA.getWriteEffectSet();
 150     Hashtable<AllocSite, Set<Effect>> alloc2readEffectsB = nodeB.getReadEffectSet();
 151     Hashtable<AllocSite, Set<Effect>> alloc2writeEffectsB = nodeB.getWriteEffectSet();
 152
 153     conflictType = updateConflictType(conflictType, determineConflictType(alloc2writeEffectsA,
 154         alloc2readEffectsB));
 155     conflictType = updateConflictType(conflictType, determineConflictType(alloc2writeEffectsA,
 156         alloc2writeEffectsB));
 157
 158     // if node B has write effects on reading regions of node A
 159     determineConflictType(alloc2writeEffectsB, alloc2readEffectsA);
 160
 161     return conflictType;
 162   }
 163
 164   private int determineConflictType(Hashtable<AllocSite, Set<Effect>> nodeAtable,
 165       Hashtable<AllocSite, Set<Effect>> nodeBtable) {
 166
 167     int conflictType = ConflictGraph.NON_WRITE_CONFLICT;
 168
 169     Iterator effectItrA = nodeAtable.entrySet().iterator();
 170     while (effectItrA.hasNext()) {
 171       Map.Entry meA = (Map.Entry) effectItrA.next();
 172       AllocSite asA = (AllocSite) meA.getKey();
 173       Set<Effect> esA = (Set<Effect>) meA.getValue();
 174
 175       Iterator effectItrB = nodeBtable.entrySet().iterator();
 176       while (effectItrB.hasNext()) {
 177         Map.Entry meB = (Map.Entry) effectItrB.next();
 178         AllocSite asB = (AllocSite) meA.getKey();
 179         Set<Effect> esB = (Set<Effect>) meA.getValue();
 180
 181         for (Iterator iterator = esA.iterator(); iterator.hasNext();) {
 182           Effect effectA = (Effect) iterator.next();
 183           for (Iterator iterator2 = esB.iterator(); iterator2.hasNext();) {
 184             Effect effectB = (Effect) iterator2.next();
 185
 186             if (effectA.getAffectedAllocSite().equals(effectB.getAffectedAllocSite())
 187                 && effectA.getField().equals(effectB.getField())) {
 188               // possible conflict
 189               /*
 190                * if(og.isReachable(asA, asB, effectA.getAffectedAllocSite())){
 191                * //affected allocation site can be reached from both heap roots
 192                * if(isFineGrainConflict()){
 193                * conflictType=updateConflictType(conflictType
 194                * ,ConflictGraph.FINE_GRAIN_EDGE); }else{
 195                * conflictType=updateConflictType
 196                * (conflictType,ConflictGraph.COARSE_GRAIN_EDGE); } }
 197                */
 198             }
 199           }
 200         }
 201       }
 202     }
 203
 204     return ConflictGraph.FINE_GRAIN_EDGE;
 205     // return conflictType;
 206   }
 207
 208   private int updateConflictType(int current, int newType) {
 209     if (newType > current) {
 210       return newType;
 211     } else {
 212       return current;
 213     }
 214   }
 215
 216   public HashSet<ConflictEdge> getEdgeSet() {
 217
 218     HashSet<ConflictEdge> returnSet = new HashSet<ConflictEdge>();
 219
 220     Collection<ConflictNode> nodes = id2cn.values();
 221     for (Iterator iterator = nodes.iterator(); iterator.hasNext();) {
 222       ConflictNode conflictNode = (ConflictNode) iterator.next();
 223       returnSet.addAll(conflictNode.getEdgeSet());
 224     }
 225
 226     return returnSet;
 227   }
 228
 229   public boolean hasConflictEdge() {
 230
 231     Set<String> keySet = id2cn.keySet();
 232     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 233       String key = (String) iterator.next();
 234       ConflictNode node = id2cn.get(key);
 235       if (node.getEdgeSet().size() > 0) {
 236         return true;
 237       }
 238     }
 239     return false;
 240   }
 241
 242   public void writeGraph(String graphName, boolean filter) throws java.io.IOException {
 243
 244     graphName = graphName.replaceAll("[\\W]", "");
 245
 246     BufferedWriter bw = new BufferedWriter(new FileWriter(graphName + ".dot"));
 247     bw.write("graph " + graphName + " {\n");
 248
 249     // then visit every heap region node
 250     Set<Entry<String, ConflictNode>> s = id2cn.entrySet();
 251     Iterator<Entry<String, ConflictNode>> i = s.iterator();
 252
 253     HashSet<ConflictEdge> addedSet = new HashSet<ConflictEdge>();
 254
 255     while (i.hasNext()) {
 256       Entry<String, ConflictNode> entry = i.next();
 257       ConflictNode node = entry.getValue();
 258
 259       if (filter) {
 260         if (node.getID().startsWith("___dst") || node.getID().startsWith("___srctmp")
 261             || node.getID().startsWith("___neverused") || node.getID().startsWith("___temp")) {
 262
 263           continue;
 264         }
 265       }
 266
 267       String attributes = "[";
 268
 269       attributes += "label=\"ID" + node.getID() + "\\n";
 270
 271       if (node.isStallSiteNode()) {
 272         attributes += "STALL SITE" + "\\n" + "\"]";
 273       } else {
 274         attributes += "LIVE-IN" + "\\n" + "\"]";
 275       }
 276       bw.write(entry.getKey() + attributes + ";\n");
 277
 278       Set<ConflictEdge> edgeSet = node.getEdgeSet();
 279       for (Iterator iterator = edgeSet.iterator(); iterator.hasNext();) {
 280         ConflictEdge conflictEdge = (ConflictEdge) iterator.next();
 281
 282         ConflictNode u = conflictEdge.getVertexU();
 283         ConflictNode v = conflictEdge.getVertexV();
 284
 285         if (filter) {
 286           String uID = u.getID();
 287           String vID = v.getID();
 288           if (uID.startsWith("___dst") || uID.startsWith("___srctmp")
 289               || uID.startsWith("___neverused") || uID.startsWith("___temp")
 290               || vID.startsWith("___dst") || vID.startsWith("___srctmp")
 291               || vID.startsWith("___neverused") || vID.startsWith("___temp")) {
 292             continue;
 293           }
 294         }
 295
 296         if (!addedSet.contains(conflictEdge)) {
 297           bw.write(" " + u.getID() + "--" + v.getID() + "[label="
 298               + conflictEdge.toGraphEdgeString() + ",decorate];\n");
 299           addedSet.add(conflictEdge);
 300         }
 301
 302       }
 303     }
 304
 305     bw.write("  graphTitle[label=\"" + graphName + "\",shape=box];\n");
 306
 307     bw.write("}\n");
 308     bw.close();
 309
 310   }
 311
 312 }