From 62a2967c91d8fffea940af63eb4867206539cc0d Mon Sep 17 00:00:00 2001 From: bdemsky Date: Wed, 26 Jan 2011 09:48:53 +0000 Subject: [PATCH] changes --- Robust/src/Analysis/Pointer/AllocFactory.java | 4 + Robust/src/Analysis/Pointer/GraphManip.java | 115 ++++++++++ Robust/src/Analysis/Pointer/Pointer.java | 211 +++++++++++++----- Robust/src/Analysis/Pointer/Util.java | 11 + 4 files changed, 283 insertions(+), 58 deletions(-) create mode 100644 Robust/src/Analysis/Pointer/GraphManip.java diff --git a/Robust/src/Analysis/Pointer/AllocFactory.java b/Robust/src/Analysis/Pointer/AllocFactory.java index 29b8d445..3ef8e8f7 100644 --- a/Robust/src/Analysis/Pointer/AllocFactory.java +++ b/Robust/src/Analysis/Pointer/AllocFactory.java @@ -15,6 +15,10 @@ public class AllocFactory { this.summary=summary; this.type=type; } + + public boolean isSummary() { + return summary; + } public int hashCode() { return allocsite<<1^(summary?0:1); diff --git a/Robust/src/Analysis/Pointer/GraphManip.java b/Robust/src/Analysis/Pointer/GraphManip.java new file mode 100644 index 00000000..dcd5c29c --- /dev/null +++ b/Robust/src/Analysis/Pointer/GraphManip.java @@ -0,0 +1,115 @@ +package Analysis.Pointer; + +public class GraphManip { + static HashSet genEdges(TempDescriptor tmp, HashSet dstSet) { + HashSet edgeset=new HashSet(); + for(AllocNode node:dstSet) { + edgeset.add(new Edge(tmp, node)); + } + return edgeset; + } + + static HashSet genEdges(HashSet srcSet, FieldDescriptor fd, HashSet dstSet) { + HashSet edgeset=new HashSet(); + for(AllocNode srcnode:srcSet) { + for(AllocNode dstnode:dstSet) { + edgeset.add(new Edge(srcnode, fd, dstnode)); + } + } + return edgeset; + } + + static HashSet getDiffEdges(Delta delta, TempDescriptor tmp) { + HashSet edges=new HashSet(); + HashSet removeedges=delta.varedgeremove.get(tmp); + + for(Edge e:delta.basevaredge.get(tmp)) { + if (removeedges==null||!removeedges.contains(e)) + edges.add(e); + } + if (delta.varedgeadd.containsKey(tmp)) + for(Edge e:delta.varedgeadd.get(tmp)) { + edges.add(e); + } + return edges; + } + + static HashSet getEdges(Graph graph, Delta delta, TempDescriptor tmp) { + HashSet edges=new HashSet(); + HashSet removeedges=delta.varedgeremove.get(tmp); + + for(Edge e:graph.getEdges(tmp)) { + if (removeedges==null||!removeedges.contains(e)) + edges.add(e); + } + if (delta.varedgeadd.containsKey(tmp)) + for(Edge e:delta.varedgeadd.get(tmp)) { + edges.add(e); + } + return edges; + } + + static HashSet getDiffNodes(Delta delta, TempDescriptor tmp) { + HashSet nodes=new HashSet(); + HashSet removeedges=delta.varedgeremove.get(tmp); + + for(Edge e:delta.basevaredge.get(tmp)) { + if (removeedges==null||!removeedges.contains(e)) + nodes.add(e.dst); + } + if (delta.varedgeadd.containsKey(tmp)) + for(Edge e:delta.varedgeadd.get(tmp)) { + nodes.add(e.dst); + } + return nodes; + } + + static HashSet getNodes(Graph graph, Delta delta, TempDescriptor tmp) { + HashSet nodes=new HashSet(); + HashSet removeedges=delta.varedgeremove.get(tmp); + + for(Edge e:graph.getEdges(tmp)) { + if (removeedges==null||!removeedges.contains(e)) + nodes.add(e.dst); + } + if (delta.varedgeadd.containsKey(tmp)) + for(Edge e:delta.varedgeadd.get(tmp)) { + nodes.add(e.dst); + } + return nodes; + } + + static HashSet getDiffNodes(Delta delta, HashSet srcNodes, FieldDescriptor fd) { + HashSet nodes=new HashSet(); + for(AllocNode node:srcNodes) { + HashSet removeedges=delta.heapedgeremove.get(node); + for(Edge e:delta.baseheapedge.get(node)) { + if (e.fd==fd&&(removeedges==null||!removeedges.contains(e))) + nodes.add(e.dst); + } + if (delta.heapedgeadd.containsKey(node)) + for(Edge e:delta.heapedgeadd.get(node)) { + if (e.fd==fd) + nodes.add(e.dst); + } + } + return nodes; + } + + static HashSet getNodes(Graph graph, Delta delta, HashSet srcNodes, FieldDescriptor fd) { + HashSet nodes=new HashSet(); + for(AllocNode node:srcNodes) { + HashSet removeedges=delta.heapedgeremove.get(node); + for(Edge e:graph.getEdges(node)) { + if (e.fd==fd&&(removeedges==null||!removeedges.contains(e))) + nodes.add(e.dst); + } + if (delta.heapedgeadd.containsKey(node)) + for(Edge e:delta.heapedgeadd.get(node)) { + if (e.fd==fd) + nodes.add(e.dst); + } + } + return nodes; + } +} \ No newline at end of file diff --git a/Robust/src/Analysis/Pointer/Pointer.java b/Robust/src/Analysis/Pointer/Pointer.java index cd474145..8d0488fb 100644 --- a/Robust/src/Analysis/Pointer/Pointer.java +++ b/Robust/src/Analysis/Pointer/Pointer.java @@ -75,18 +75,21 @@ public class Pointer { case FKind.FlatNew: return processNewNode((FlatNew)node, delta, newgraph); case FKind.FlatFieldNode: - return processFieldNode((FlatFieldNode)node, delta, newgraph); - case FKind.FlatCall: + case FKind.FlatElementNode: + return processFieldElementNode(node, delta, newgraph); + case FKind.FlatCastNode: + case FKind.FlatOpNode: + return processCopyNode(node, delta, newgraph); case FKind.FlatSetFieldNode: + return processSetFieldElementNode(node, delta, newgraph); + case FKind.FlatMethod: + case FKind.FlatCall: case FKind.FlatReturnNode: - case FKind.FlatElementNode: case FKind.FlatSetElementNode: - case FKind.FlatMethod: case FKind.FlatExit: case FKind.FlatSESEEnterNode: case FKind.FlatSESEExitNode: - case FKind.FlatCastNode: - case FKind.FlatOpNode: + throw new Error("Unimplemented node:"+node); default: throw new Error("Unrecognized node:"+node); @@ -155,36 +158,157 @@ public class Pointer { } } - HashSet getTemps(Graph graph, Delta delta, TempDescriptor tmp) { - HashSet nodes=new HashSet(); - HashSet removeedges=delta.varedgeremove.get(tmp); - - for(Edge e:graph.getEdges(tmp)) { - if (removeedges==null||!removeedges.contains(e)) - nodes.add(e.dst); + Delta processSetFieldElementNode(FlatNode node, Delta delta, Graph graph) { + TempDescriptor src; + FieldDescriptor fd; + TempDescriptor dst; + if (node.kind()==FKind.FlatSetElementNode) { + FlatSetElementNode fen=(FlatSetElementNode) node; + src=fen.getSrc(); + fd=null; + dst=fen.getDst(); + } else { + FlatSetFieldNode ffn=(FlatSetFieldNode) node; + src=ffn.getSrc(); + fd=ffn.getField(); + dst=ffn.getDst(); } - if (delta.varedgeadd.containsKey(tmp)) - for(Edge e:delta.varedgeadd.get(tmp)) { - nodes.add(e.dst); + if (delta.getInit()) { + HashSet srcNodes=GraphManip.getNodes(graph, delta, src); + HashSet dstNodes=GraphManip.getNodes(graph, delta, dst); + HashSet edgesToAdd=GraphManip.genEdges(srcNodes, fd, dstNodes); + if (dstNodes.size()==1&&!dstNodes.iterator().next().isSummary()) { + /* Can do a strong update */ + + } - return nodes; + } else { + + + } } - Delta processFieldNode(FlatFieldNode node, Delta delta, Graph graph) { - TempDescriptor src=node.getSrc(); - FieldDescriptor fd=node.getField(); - TempDescriptor dst=node.getDst(); + Delta processCopyNode(FlatNode node, Delta delta, Graph graph) { + TempDescriptor src; + TempDescriptor dst; + if (node.kind()==FKind.FlatOpNode) { + FlatOpNode fon=(FlatOpNode) node; + src=fcn.getLeft(); + dst=fcn.getDst(); + } else { + FlatCastNode fcn=(FlatCastNode) node; + src=fcn.getSrc(); + dst=fcn.getDst(); + } if (delta.getInit()) { - HashSet nodes=getTemps(graph, delta, src); - + HashSet srcnodes=GraphManip.getNodes(graph, delta, src); + HashSet edgesToAdd=GraphManip.genEdges(src, srcnodes); + HashSet edgesToRemove=GraphManip.getEdges(graph, delta, dst); + updateVarDelta(graph, delta, dst, edgesToAdd, edgesToRemove); + applyDiffs(graph, delta); + } else { + /* First compute new src nodes */ + HashSet newSrcNodes=GraphManip.getDiffNodes(delta, src); + + /* Compute the union, and then the set of edges */ + HashSet edgesToAdd=GraphManip.genEdges(src, newSrcNodes); + /* Compute set of edges to remove */ + HashSet edgesToRemove=GraphManip.getDiffEdges(delta, dst); + + /* Update diff */ + updateVarDelta(graph, delta, dst, edgesToAdd, edgesToRemove); applyDiffs(graph, delta); + } + return delta; + } + + Delta processFieldElementNode(FlatNode node, Delta delta, Graph graph) { + TempDescriptor src; + FieldDescriptor fd; + TempDescriptor dst; + if (node.kind()==FKind.FlatElementNode) { + FlatElementNode fen=(FlatElementNode) node; + src=fen.getSrc(); + fd=null; + dst=fen.getDst(); } else { + FlatFieldNode ffn=(FlatFieldNode) node; + src=ffn.getSrc(); + fd=ffn.getField(); + dst=ffn.getDst(); + } + if (delta.getInit()) { + HashSet srcnodes=GraphManip.getNodes(graph, delta, src); + HashSet fdnodes=GraphManip.getNodes(graph, delta, srcnodes, fd); + HashSet edgesToAdd=GraphManip.genEdges(src, fdnodes); + HashSet edgesToRemove=GraphManip.getEdges(graph, delta, dst); + updateVarDelta(graph, delta, dst, edgesToAdd, edgesToRemove); + applyDiffs(graph, delta); + } else { + /* First compute new objects we read fields of */ + HashSet allsrcnodes=GraphManip.getNodes(graph, delta, src); + HashSet difffdnodes=GraphManip.getDiffNodes(delta, allsrcnodes, fd); + /* Next compute new targets of fields */ + HashSet newsrcnodes=GraphManip.getDiffNodes(delta, src); + HashSet newfdnodes=GraphManip.getNodes(graph, delta, newsrcnodes, fd); + /* Compute the union, and then the set of edges */ + HashSet newTargets=new HashSet(); + newTargets.addAll(newfdnodes); + newTargets.addAll(difffdnodes); + HashSet edgesToAdd=GraphManip.genEdges(src, newTargets); + + /* Compute set of edges to remove */ + HashSet edgesToRemove=GraphManip.getDiffEdges(delta, dst); + /* Update diff */ + updateVarDelta(graph, delta, dst, edgesToAdd, edgesToRemove); + applyDiffs(graph, delta); } return delta; } + static void updateVarDelta(Graph graph, Delta delta, TempDescriptor tmp, HashSet edgestoAdd, HashSet edgestoRemove) { + HashSet edgeAdd=delta.varedgeadd.get(tmp); + HashSet edgeRemove=delta.varedgeremove.get(tmp); + HashSet existingEdges=graph.getEdges(tmp); + for(Edge e: edgestoRemove) { + //remove edge from delta + edgeAdd.remove(e); + //if the edge is already in the graph, add an explicit remove to the delta + if (existingEdges.contains(e)) + edgeRemove.add(e); + } + for(Edge e: edgestoAdd) { + //Remove the edge from the remove set + edgeRemove.remove(e); + //Explicitly add it to the add set unless it is already in the graph + if (!existingEdges.contains(e)) + edgeAdd.add(e); + } + } + + static void updateHeapDelta(Graph graph, Delta delta, HashSet edgestoAdd, HashSet edgestoRemove) { + /* Fix all of this */ + HashSet edgeAdd=delta.varedgeadd.get(tmp); + HashSet edgeRemove=delta.varedgeremove.get(tmp); + HashSet existingEdges=graph.getEdges(tmp); + for(Edge e: edgestoRemove) { + //remove edge from delta + edgeAdd.remove(e); + //if the edge is already in the graph, add an explicit remove to the delta + if (existingEdges.contains(e)) + edgeRemove.add(e); + } + for(Edge e: edgestoAdd) { + //Remove the edge from the remove set + edgeRemove.remove(e); + //Explicitly add it to the add set unless it is already in the graph + if (!existingEdges.contains(e)) + edgeAdd.add(e); + } + } + Delta processNewNode(FlatNew node, Delta delta, Graph graph) { AllocNode summary=allocFactory.getAllocNode(node, true); AllocNode single=allocFactory.getAllocNode(node, false); @@ -224,30 +348,13 @@ public class Pointer { TempDescriptor entrytmp=entry.getKey(); if (entrytmp==tmp) { /* Check is this is the tmp we overwrite, if so add to remove set */ - if (delta.varedgeremove.containsKey(tmp)) - delta.varedgeremove.get(tmp).addAll(entry.getValue()); - else - delta.varedgeremove.put(tmp, entry.getValue()); + Util.relationUpdate(delta.varedgeremove, tmp, null, entry.getValue()); } else { /* Check if the target of the edge is changed */ HashSet newset=(HashSet)entry.getValue().clone(); HashSet removeset=shrinkSet(newset, graph.varMap.get(entrytmp), single, summary); - if (delta.varedgeremove.containsKey(entrytmp)) { - /* Make sure we do not remove the newly created edges. */ - delta.varedgeremove.get(entrytmp).removeAll(newset); - /* Remove the old edges to the single node */ - delta.varedgeremove.get(entrytmp).addAll(removeset); - } else { - /* Remove the old edges to the single node */ - delta.varedgeremove.put(entrytmp, removeset); - } - if (delta.varedgeadd.containsKey(entrytmp)) { - /* Create the new edges */ - delta.varedgeadd.get(entrytmp).addAll(newset); - } else { - /* Create the new edges */ - delta.varedgeadd.put(entrytmp, newset); - } + Util.relationUpdate(delta.varedgeremove, entrytmp, newset, removeset); + Util.relationUpdate(delta.varedgeadd, entrytmp, null, newset); } } @@ -272,11 +379,7 @@ public class Pointer { for(Map.Entry> entry:addheapedge.entrySet()) { AllocNode allocnode=entry.getKey(); - if (delta.heapedgeadd.containsKey(allocnode)) { - delta.heapedgeadd.get(allocnode).addAll(entry.getValue()); - } else { - delta.heapedgeadd.put(allocnode, entry.getValue()); - } + Util.relationUpdate(delta.heapedgeadd, allocnode, null. entry.getValue()); } /* 4. Fix up the base heap edges */ @@ -292,16 +395,8 @@ public class Pointer { HashSet newset=(HashSet) edgeset.clone(); HashSet removeset=shrinkSet(newset, graph.nodeMap.get(addnode), single, summary); - if (delta.heapedgeadd.containsKey(addnode)) { - delta.heapedgeadd.get(addnode).addAll(newset); - } else { - delta.heapedgeadd.put(addnode, newset); - } - if (delta.heapedgeremove.containsKey(allocnode)) { - delta.heapedgeremove.get(allocnode).addAll(removeset); - } else { - delta.heapedgeremove.put(allocnode, removeset); - } + Util.relationUpdate(delta.heapedgeadd, addnode, null, newset); + Util.relationUpdate(delta.heapedgeremove, allocnode, null, removeset); } //Apply incoming diffs to graph diff --git a/Robust/src/Analysis/Pointer/Util.java b/Robust/src/Analysis/Pointer/Util.java index d9746dad..57a44829 100644 --- a/Robust/src/Analysis/Pointer/Util.java +++ b/Robust/src/Analysis/Pointer/Util.java @@ -1,5 +1,6 @@ package Analysis.Pointer; import java.util.HashSet; +import java.util.HashMap; import java.util.Set; public class Util { @@ -12,4 +13,14 @@ public class Util { return newset; } + public static void relationUpdate(HashMap> map, K key, HashSet toremove, HashSet toadd) { + if (map.containsKey(key)) { + if (toremove!=null) + map.get(key).removeAll(toremove); + map.get(key).addAll(toadd); + } else { + map.put(key, (HashSet) toadd.clone()); + } + } + } \ No newline at end of file -- 2.34.1