From: stephey Date: Thu, 5 Aug 2010 23:17:23 +0000 (+0000) Subject: Completed version before tying in with system and debug X-Git-Url: http://plrg.eecs.uci.edu/git/?p=IRC.git;a=commitdiff_plain;h=33d3a119eb3c0a2d0fc09beac1f96722c987b992 Completed version before tying in with system and debug --- diff --git a/Robust/src/IR/Flat/RuntimeConflictResolver.java b/Robust/src/IR/Flat/RuntimeConflictResolver.java index 3206dc8d..59cd527f 100644 --- a/Robust/src/IR/Flat/RuntimeConflictResolver.java +++ b/Robust/src/IR/Flat/RuntimeConflictResolver.java @@ -1,5 +1,7 @@ package IR.Flat; +import java.io.File; +import java.io.FileNotFoundException; import java.io.PrintWriter; import java.util.ArrayList; import java.util.HashSet; @@ -8,410 +10,399 @@ import java.util.Iterator; import java.util.Set; import Analysis.Disjoint.*; +/* + * How to Use: + * 1) Instantiate object + * 2) Call void traverse(FlatSESEEnterNode rblock, Hashtable> effects, Hashtable> conflicts, ReachGraph rg) + * as many times as needed + * 3) Call void close() + */ public class RuntimeConflictResolver { - private static final String outputFile = "RuntimeConflictResolver.c"; - - private static final String getAllocSiteInC = "->allocsite"; - private static final String queryAndQueryHashTableInC = "t_chashInsert("; - private static final String addToQueueInC = "enqueueRCRQueue("; - private static final String dequeueFromQueueInC = "dequeueRCRQueue()"; - - /* - * Basic steps: - * 1) Create pruned data structures from givens - * 1a) Use effects sets to verify if we can access something (reads) - * 1b) Mark all conflicts with a special flag (perhaps create wrapper) - * 2) Traverse again and build code output structure (as Objects) - * 3) printout - */ - public void traverse(FlatSESEEnterNode rblock, - Hashtable> effects, - Hashtable> conflicts, - ReachGraph rg) - { - Set inVars = rblock.getInVarSet(); - Hashtable created = new Hashtable(); - - - //Is this even needed? - if(inVars.size() == 0) - return; - - createTree(rblock, inVars, conflicts, rg, created); - if(!created.isEmpty()) - printCCode(created); - } - - //I'll assume that I'll get a pointer to the first data element named ptr - private void printHeader(StringBuilder out) - { - //TODO includes - //TODO initialize hashset/hashtable - //TODO initialize Queue - //TODO start do/while loop - System.out.println("PrintHeader not yet implemented."); - } - private void printFooter(StringBuilder out) - { - //TODO End the while loops and such - //TODO free stuff we've used??? - System.out.println("PrintFooter not yet implemented."); - } - - private StringBuilder generateCPrintoutStructure(Hashtable created) - { - HashSet done = new HashSet(); - StringBuilder out = new StringBuilder(); - - - //TODO add the first item to hashtable in header before start - printHeader(out); - for(Node node: created.values()) - { - //If we haven't seen it and it's a node with more than 1 parent - //Note: a node with 0 parents is a root node (i.e. inset variable) - if(!done.contains(new Integer(node.getAllocationSite())) && node.numOfParents != 1 && node.decendentsConflict) - addChecker(node, done, out, "ptr"); - } - printFooter(out); - - return out; - } - - private void addChecker(Node node, - HashSet done, - StringBuilder out, - String prefix) - { - //We don't need a case statement for things with either 1 incoming or 0 out going edges. - if(node.numOfParents != 1 && node.decendentsConflict) { - assert prefix.equals("ptr"); - out.append("case " + node.getAllocationSite() + ":\n"); - } - - for(Reference ref: node.references) - { - //Will only process it if there is some sort of conflict with Child - if(ref.child.decendentsConflict || ref.child.myConflict){ - String childPtr = prefix + "->" + ref.field; - - //Checks if the child exists and is correct - out.append("if(" + childPtr + " != NULL && " + childPtr + getAllocSiteInC + - "==" + ref.allocSite + ") { "); - - //Prints out Conflict of child - if(ref.child.myConflict) - handleConflict(out, childPtr); - - //Checks if we have visited the child before - out.append("if(!" + queryAndQueryHashTableInC + childPtr + ") {"); - - //If there are out going edges then add to queue - if(ref.child.decendentsConflict) { - if(ref.child.numOfParents == 1) - addChecker(ref.child, done, out, childPtr); - else - out.append(addToQueueInC + childPtr+ ");"); - } - //TODO check # of } on output - out.append(" }} "); - } - } - - if(node.numOfParents != 1 && node.decendentsConflict) - out.append("break;\n"); - - done.add(new Integer(node.getAllocationSite())); - } - - private void handleConflict(StringBuilder out, String childPtr) - { - out.append("printf(\"Conflict detected at %p with allocation site %u\n\"," + childPtr + - "," + childPtr + getAllocSiteInC + ");"); - } - - //I'll assume that I'll be just given a pointer named ptr in my function. - private void printCCode(Hashtable created) { - try { - PrintWriter p = new PrintWriter(outputFile); - String outputString = generateCPrintoutStructure(created).toString(); - p.append(outputString); - p.close(); - } - catch (java.io.FileNotFoundException e) - { - System.out.println("Output file for RuntimeConflictResolver is nonexistant."); - } - - } - - private void createTree(FlatSESEEnterNode rblock, - Set inVars, - Hashtable> conflicts, - ReachGraph rg, - Hashtable created) { - for(TempDescriptor invar: inVars) { - VariableNode varNode = rg.getVariableNodeNoMutation(invar); - Hashtable table = generateHashtable(rblock, varNode ,conflicts, conflicts); - - //if table is null that means there's no conflicts, therefore we need not create a traversal - if(table != null) { - Iterator possibleRootNodes = varNode.iteratorToReferencees(); - - while(possibleRootNodes.hasNext()) { - RefEdge edge = possibleRootNodes.next(); - assert edge != null; - - //always assumed to be a conflict on the root variables. - Node singleRoot = new Node(edge.getDst(), true); - NodeKey rootKey = new NodeKey(singleRoot.allocSite); - - if(!created.contains(rootKey)) { - created.put(rootKey, singleRoot); - createHelper(singleRoot, edge.getDst().iteratorToReferencees(), created, table); - } - } - } - } - } - - /* - * Plan is to add stuff to the tree depth-first sort of way. That way, we can propogate up conflicts. - */ - private void createHelper(Node parent, Iterator edges, Hashtable created, Hashtable table) { - assert table != null; - while(edges.hasNext()) { - RefEdge edge = edges.next(); - String field = edge.getField(); - HeapRegionNode childHRN = edge.getDst(); - - EffectsKey lookup = new EffectsKey(childHRN.getAllocSite(), field); - EffectsHashPair effect = table.get(lookup); - - //if there's no effect, we don't traverse this edge. - if(effect != null) { - NodeKey key = new NodeKey(childHRN.getAllocSite()); - boolean isNewChild = !created.contains(key); - Node child; - - if(isNewChild) - child = new Node(childHRN, effect.conflict); - else { - child = created.get(key); - child.myConflict = effect.conflict; - } - - parent.addChild(field, child); - if(effect.conflict) - propogateConflictFlag(parent); - - if(effect.type == Effect.read && isNewChild) - createHelper(child, childHRN.iteratorToReferencees(), created, table); - } - } - } - - - //This will propagate the conflict up the tree. - private void propogateConflictFlag(Node node) { - Node curr = node; - - while(curr != null && curr.decendentsConflict != true) { - curr.decendentsConflict = true; - curr = curr.lastParent; - } - } - - - - - private Hashtable generateHashtable(FlatSESEEnterNode rblock, - VariableNode var, - Hashtable> effects, - Hashtable> conflicts) { - //we search effects since conflicts is only a subset of effects - Taint taint = getProperTaint(rblock, var, effects); - assert taint !=null; - - Set localEffects = effects.get(taint); - Set localConflicts = conflicts.get(taint); - - if(localEffects == null || localEffects.isEmpty() || conflicts == null || conflicts.isEmpty()) - return null; - - Hashtable table = new Hashtable(); - - for(Effect e: localEffects) { - EffectsKey key = new EffectsKey(e); - EffectsHashPair element = new EffectsHashPair(e, localConflicts.contains(e)); - table.put(key, element); - } - - return table; - } - - private Taint getProperTaint(FlatSESEEnterNode rblock, - VariableNode var, - Hashtable> effects) - { - Set taints = effects.keySet(); - for(Taint t: taints) - if(t.getSESE().equals(rblock) && t.getVar().equals(var.getTempDescriptor())) - return t; - - return null; - } - - private class EffectsKey - { - AllocSite allocsite; - String field; - - public EffectsKey(AllocSite a, String f) - { - allocsite = a; - field = f; - } - - public EffectsKey(Effect e) - { - allocsite = e.getAffectedAllocSite(); - field = e.getField().getSymbol(); - } - - //Hashcode only hashes the object based on AllocationSite and Field - public int hashCode() - { - return allocsite.hashCode() ^ field.hashCode(); - } - - //Equals ONLY compares object based on AllocationSite and Field - public boolean equals(Object o) - { - if (o == null) - return false; - - if (!(o instanceof EffectsKey)) - return false; - - EffectsKey other = (EffectsKey) o; - - return (other.allocsite.equals(this.allocsite) && - other.field.equals(this.field)); - } - } - - private class EffectsHashPair - { - Effect originalEffect; - int type; - boolean conflict; - - public EffectsHashPair(Effect e, boolean conflict) - { - originalEffect = e; - type = e.getType(); - this.conflict = conflict; - } - - //Hashcode only hashes the object based on AllocationSite and Field - public int hashCode() - { - return originalEffect.hashCode(); - } - - //Equals ONLY compares object based on AllocationSite and Field - public boolean equals(Object o) - { - if (o == null) - return false; - - if (!(o instanceof EffectsHashPair)) - return false; - - EffectsHashPair other = (EffectsHashPair) o; - - return (other.originalEffect.getAffectedAllocSite().equals(originalEffect.getAffectedAllocSite()) && - other.originalEffect.getField().equals(originalEffect.getField())); - } - } - - private class Reference - { - String field; - int allocSite; - Node child; - - public Reference(String fieldname, Node ref) - { - field = fieldname; - allocSite = ref.getAllocationSite(); - child = ref; - } - } - - private class NodeKey - { - int allocsite; - - public NodeKey(AllocSite site) - { - allocsite = site.hashCodeSpecific(); - } - - public int hashCode() - { - return allocsite; - } - } - - -private class Node -{ - ArrayList references; - Node lastParent; - int numOfParents; - boolean myConflict; - boolean decendentsConflict; - AllocSite allocSite; - HeapRegionNode original; - - public Node(HeapRegionNode me, boolean conflict) - { - references = new ArrayList(); - lastParent = null; - numOfParents = 0; - allocSite = me.getAllocSite(); - original = me; - this.myConflict = conflict; - decendentsConflict = false; - } - - @Override - public int hashCode() - { - //This gets allocsite number - return allocSite.hashCodeSpecific(); - } - - @Override - public boolean equals(Object obj) - { - return original.equals(obj); - } - - public int getAllocationSite() - { - return allocSite.hashCodeSpecific(); - } - - public void addChild(String field, Node child) - { - child.lastParent = this; - child.numOfParents++; - Reference ref = new Reference(field, child); - references.add(ref); - } -} + private static final String outputFile = "RuntimeConflictResolver.c"; + private PrintWriter out; + private static final String hashAndQueueCFileDir = ""; + + // initializing variables can be found in printHeader() + + private static final String getAllocSiteInC = "->allocsite"; + private static final String queryAndAddHashTableInC = "hashRCRInsert("; + private static final String addToQueueInC = "enqueueRCRQueue("; + private static final String dequeueFromQueueInC = "dequeueRCRQueue()"; + + private static final String clearQueue = "resetRCRQueue()"; + // Make hashtable; hashRCRCreate(unsigned int size, double loadfactor) + private static final String mallocHashTable = "hashRCRCreate(1024, 0.25)"; + private static final String deallocHashTable = "hashRCRDelete()"; + private static final String resetHashTable = "hashRCRreset()"; + + public RuntimeConflictResolver() throws FileNotFoundException { + out = new PrintWriter(new File(outputFile)); + out.append("#include \"" + hashAndQueueCFileDir + "hashRCR.h\"\n#include \"" + + hashAndQueueCFileDir + "Queue_RCR.h\"\n"); + } + + /* + * Basic steps: 1) Create pruned data structures from givens 1a) Use effects + * sets to verify if we can access something (reads) 1b) Mark conflicts with 2 + * flags (one for self, one for children) 2)build code output structure 3) + * printout + */ + public void traverse(FlatSESEEnterNode rblock, Hashtable> effects, + Hashtable> conflicts, ReachGraph rg) { + Set inVars = rblock.getInVarSet(); + + // Is this even needed? + if (inVars.size() == 0) + return; + + // For every inVariable, generate unique method + for (TempDescriptor invar : inVars) { + Hashtable created = new Hashtable(); + + createTree(rblock, invar, conflicts, rg, created); + if (!created.isEmpty()) + // TODO check if this returns the correct name for rblock + printCMethod(created, invar.getSymbol(), rblock.getSESErecordName()); + } + } + + public void close() { + // appends file + out.append("void initializeStructsRCR() { " + mallocHashTable + "; " + clearQueue + "; }"); + out.append("void destroyRCR() { " + deallocHashTable + "; }\n"); + + out.close(); + } + + private void createTree(FlatSESEEnterNode rblock, TempDescriptor invar, + Hashtable> conflicts, ReachGraph rg, Hashtable created) { + + VariableNode varNode = rg.getVariableNodeNoMutation(invar); + Hashtable table = + generateHashtable(rblock, varNode, conflicts, conflicts); + + // if table is null that means there's no conflicts, therefore we need not + // create a traversal + if (table == null) + return; + + Iterator possibleHRN = varNode.iteratorToReferencees(); + + while (possibleHRN.hasNext()) { + RefEdge edge = possibleHRN.next(); + assert edge != null; + + // always assumed to be a conflict on the root variables. + Node singleRoot = new Node(edge.getDst(), true); + NodeKey rootKey = new NodeKey(singleRoot.allocSite); + + if (!created.contains(rootKey)) { + created.put(rootKey, singleRoot); + createHelper(singleRoot, edge.getDst().iteratorToReferencees(), created, table); + } + } + + } + + private void addChecker(Node node, HashSet done, String prefix) { + // We don't need a case statement for things with either 1 incoming or 0 out + // going edges. + if (node.numOfConflictParents != 1 && node.decendentsConflict) { + assert prefix.equals("ptr"); + out.append("case " + node.getAllocationSite() + ":\n"); + } + + for (Reference ref : node.references) { + // Will only process edge if there is some sort of conflict with the Child + if (ref.child.decendentsConflict || ref.child.myConflict) { + String childPtr = prefix + "->" + ref.field; + + // Checks if the child exists and is correct + out.append("if(" + childPtr + " != NULL && " + childPtr + getAllocSiteInC + "==" + + ref.allocSite + ") { "); + + // Prints out Conflict of child + if (ref.child.myConflict) + handleConflict(childPtr); + + // Checks if we have visited the child before + out.append("if(!" + queryAndAddHashTableInC + childPtr + ") { "); + + // If there are out going edges then add to queue + if (ref.child.decendentsConflict) { + if (ref.child.getNumOfReachableParents() == 1) + addChecker(ref.child, done, childPtr); + else + out.append(addToQueueInC + childPtr + ");"); + } + out.append(" }} "); + } + } + + if (node.numOfConflictParents != 1 && node.decendentsConflict) + out.println("break; "); + + done.add(new Integer(node.getAllocationSite())); + } + + private void handleConflict(String childPtr) { + out.append("printf(\"Conflict detected at %p with allocation site %u\n\"," + childPtr + "," + + childPtr + getAllocSiteInC + ");"); + } + + // I'll assume that I'll be just given a pointer named ptr in my function. + private void printCMethod(Hashtable created, String inVar, String rBlock) { + HashSet done = new HashSet(); + + out.append("void traverse___" + inVar + rBlock + "___(void * InVar) {\n"); + out.append("void * ptr = InVar; if(InVar != NULL) { " + queryAndAddHashTableInC + + "ptr); do { "); + for (Node node : created.values()) { + // If we haven't seen it and it's a node with more than 1 parent + // Note: a node with 0 parents is a root node (i.e. inset variable) + if (!done.contains(new Integer(node.getAllocationSite())) && node.numOfConflictParents != 1 + && node.decendentsConflict) + addChecker(node, done, "ptr"); + } + out.append("} while( (ptr = " + dequeueFromQueueInC + ") != NULL); "); + out.append(clearQueue + "; " + resetHashTable + "; }}\n"); + } + + // Plan is to add stuff to the tree depth-first sort of way. That way, we can + // propagate up conflicts + private void createHelper(Node parent, Iterator edges, Hashtable created, + Hashtable table) { + assert table != null; + while (edges.hasNext()) { + RefEdge edge = edges.next(); + String field = edge.getField(); + HeapRegionNode childHRN = edge.getDst(); + + EffectsKey lookup = new EffectsKey(childHRN.getAllocSite(), field); + EffectsHashPair effect = table.get(lookup); + + // if there's no effect, we don't traverse this edge. + if (effect != null) { + NodeKey key = new NodeKey(childHRN.getAllocSite()); + boolean isNewChild = !created.contains(key); + Node child; + + if (isNewChild) + child = new Node(childHRN, effect.conflict); + else { + child = created.get(key); + child.myConflict = effect.conflict || child.myConflict; + } + + parent.addChild(field, child); + if (effect.conflict) + propogateConflictFlag(parent); + + if (effect.type == Effect.read && isNewChild) + createHelper(child, childHRN.iteratorToReferencees(), created, table); + } + } + } + + // This will propagate the conflict up the tree. + private void propogateConflictFlag(Node node) { + Node curr = node; + + while (curr != null && curr.decendentsConflict != true) { + curr.decendentsConflict = true; + curr = curr.lastParent; + } + } + + private Hashtable generateHashtable(FlatSESEEnterNode rblock, + VariableNode var, Hashtable> effects, + Hashtable> conflicts) { + // we search effects since conflicts is only a subset of effects + Taint taint = getProperTaint(rblock, var, effects); + assert taint != null; + + Set localEffects = effects.get(taint); + Set localConflicts = conflicts.get(taint); + + if (localEffects == null || localEffects.isEmpty() || conflicts == null || conflicts.isEmpty()) + return null; + + Hashtable table = new Hashtable(); + + for (Effect e : localEffects) { + EffectsKey key = new EffectsKey(e); + EffectsHashPair element = new EffectsHashPair(e, localConflicts.contains(e)); + table.put(key, element); + } + + return table; + } + + private Taint getProperTaint(FlatSESEEnterNode rblock, VariableNode var, + Hashtable> effects) { + Set taints = effects.keySet(); + for (Taint t : taints) + if (t.getSESE().equals(rblock) && t.getVar().equals(var.getTempDescriptor())) + return t; + + return null; + } + + private class EffectsKey { + AllocSite allocsite; + String field; + + public EffectsKey(AllocSite a, String f) { + allocsite = a; + field = f; + } + + public EffectsKey(Effect e) { + allocsite = e.getAffectedAllocSite(); + field = e.getField().getSymbol(); + } + + // Hashcode only hashes the object based on AllocationSite and Field + public int hashCode() { + return allocsite.hashCode() ^ field.hashCode(); + } + + // Equals ONLY compares object based on AllocationSite and Field + public boolean equals(Object o) { + if (o == null) + return false; + + if (!(o instanceof EffectsKey)) + return false; + + EffectsKey other = (EffectsKey) o; + + return (other.allocsite.equals(this.allocsite) && other.field.equals(this.field)); + } + } + + private class EffectsHashPair { + Effect originalEffect; + int type; + boolean conflict; + + public EffectsHashPair(Effect e, boolean conflict) { + originalEffect = e; + type = e.getType(); + this.conflict = conflict; + } + + // Hashcode only hashes the object based on AllocationSite and Field + public int hashCode() { + return originalEffect.hashCode(); + } + + // Equals ONLY compares object based on AllocationSite and Field + public boolean equals(Object o) { + if (o == null) + return false; + + if (!(o instanceof EffectsHashPair)) + return false; + + EffectsHashPair other = (EffectsHashPair) o; + + return (other.originalEffect.getAffectedAllocSite().equals( + originalEffect.getAffectedAllocSite()) && other.originalEffect.getField().equals( + originalEffect.getField())); + } + } + + private class Reference { + String field; + int allocSite; + Node child; + + public Reference(String fieldname, Node ref) { + field = fieldname; + allocSite = ref.getAllocationSite(); + child = ref; + } + } + + private class NodeKey { + int allocsite; + + public NodeKey(AllocSite site) { + allocsite = site.hashCodeSpecific(); + } + + public int hashCode() { + return allocsite; + } + + public boolean equals(Object obj) { + if (obj == null) + return false; + + if (!(obj instanceof NodeKey)) + return false; + + if (((NodeKey) obj).allocsite == allocsite) + return true; + + return false; + } + + } + + private class Node { + ArrayList references; + ArrayList parents; + Node lastParent; + int numOfConflictParents; + boolean myConflict; + boolean decendentsConflict; + AllocSite allocSite; + HeapRegionNode original; + + public Node(HeapRegionNode me, boolean conflict) { + references = new ArrayList(); + parents = new ArrayList(); + lastParent = null; + numOfConflictParents = -1; + allocSite = me.getAllocSite(); + original = me; + this.myConflict = conflict; + decendentsConflict = false; + } + + @Override + public int hashCode() { + // This gets allocsite number + return allocSite.hashCodeSpecific(); + } + + @Override + public boolean equals(Object obj) { + return original.equals(obj); + } + + public int getAllocationSite() { + return allocSite.hashCodeSpecific(); + } + + public int getNumOfReachableParents() { + if (numOfConflictParents == -1) { + numOfConflictParents = 0; + for (Node parent : parents) + if (parent.decendentsConflict) + numOfConflictParents++; + } + + return numOfConflictParents; + } + + public void addChild(String field, Node child) { + child.lastParent = this; + Reference ref = new Reference(field, child); + references.add(ref); + } + } }