From 4ce3a02e93d305eed6687a390d9380685fd7c592 Mon Sep 17 00:00:00 2001 From: bdemsky Date: Thu, 3 Mar 2011 01:56:17 +0000 Subject: [PATCH] more changes --- Robust/src/Analysis/Pointer/Delta.java | 5 + Robust/src/Analysis/Pointer/Graph.java | 3 +- Robust/src/Analysis/Pointer/MySet.java | 5 + Robust/src/Analysis/Pointer/Pointer.java | 221 ++++++++++++++++++++++- 4 files changed, 228 insertions(+), 6 deletions(-) diff --git a/Robust/src/Analysis/Pointer/Delta.java b/Robust/src/Analysis/Pointer/Delta.java index 4e114310..4c91420b 100644 --- a/Robust/src/Analysis/Pointer/Delta.java +++ b/Robust/src/Analysis/Pointer/Delta.java @@ -13,6 +13,9 @@ public class Delta { HashMap> basevaredge; HashSet baseNodeAges; HashSet addNodeAges; + HashMap baseOldNodes; + HashMap addOldNodes; + boolean init; PPoint block; @@ -31,6 +34,8 @@ public class Delta { this.varedgeremove=new HashMap>(); this.baseNodeAges=new HashSet(); this.addNodeAges=new HashSet(); + this.baseOldNodes=new HashMap(); + this.addOldNodes=new HashMap(); this.block=block; } diff --git a/Robust/src/Analysis/Pointer/Graph.java b/Robust/src/Analysis/Pointer/Graph.java index 09adf72d..0efc690f 100644 --- a/Robust/src/Analysis/Pointer/Graph.java +++ b/Robust/src/Analysis/Pointer/Graph.java @@ -18,12 +18,13 @@ public class Graph { /* Need this information for mapping in callee results */ HashSet nodeAges; + HashMap oldNodes; public Graph(Graph parent) { nodeMap=new HashMap>(); - backMap=new HashMap>(); varMap=new HashMap>(); nodeAges=new HashSet(); + oldNodes=new HashMap(); this.parent=parent; } diff --git a/Robust/src/Analysis/Pointer/MySet.java b/Robust/src/Analysis/Pointer/MySet.java index 26be393e..3b813f19 100644 --- a/Robust/src/Analysis/Pointer/MySet.java +++ b/Robust/src/Analysis/Pointer/MySet.java @@ -7,6 +7,11 @@ public class MySet extends AbstractSet { map=new HashMap(); } + public MySet(MySet base) { + map=new HashMap(); + addAll(base); + } + public int size() { return map.size(); } diff --git a/Robust/src/Analysis/Pointer/Pointer.java b/Robust/src/Analysis/Pointer/Pointer.java index bb31a9c0..8aa7c7ab 100644 --- a/Robust/src/Analysis/Pointer/Pointer.java +++ b/Robust/src/Analysis/Pointer/Pointer.java @@ -118,6 +118,15 @@ public class Pointer { newDelta.addNodeAges.add(node); else if (graph.parent.nodeAges.contains(node)) newDelta.addNodeAges.add(node); + + /* Compute ages */ + if (graph.oldNodes.containsKey(node)) { + if (graph.oldNodes.get(node).booleanValue()) + newDelta.addOldNodes.put(node, Boolean.TRUE); + } else if (graph.parent.oldNodes.containsKey(node)) { + //parent graphs only contain true...no need to check + newDelta.addOldNodes.put(node, Boolean.TRUE); + } } } @@ -167,10 +176,26 @@ public class Pointer { /* Compute new ages */ newDelta.addNodeAges.addAll(delta.baseNodeAges); newDelta.addNodeAges.addAll(delta.addNodeAges); + HashSet oldNodes=new HashSet(); + + /* Compute whether old nodes survive */ + oldNodes.addAll(delta.baseOldNodes.keySet()); + oldNodes.addAll(delta.addOldNodes.keySet()); + for(AllocNode node:oldNodes) { + if (delta.addOldNodes.containsKey(node)) { + if (delta.addOldNodes.get(node).booleanValue()) { + newDelta.addOldNodes.put(node, Boolean.TRUE); + } + } else { + if (delta.baseOldNodes.get(node).booleanValue()) { + newDelta.addOldNodes.put(node, Boolean.TRUE); + } + } + } } /* Now we need to propagate newdelta */ - if (!newDelta.heapedgeadd.isEmpty()||!newDelta.heapedgeremove.isEmpty()||!newDelta.varedgeadd.isEmpty()||!newDelta.addNodeAges.isEmpty()) { + if (!newDelta.heapedgeadd.isEmpty()||!newDelta.heapedgeremove.isEmpty()||!newDelta.varedgeadd.isEmpty()||!newDelta.addNodeAges.isEmpty()||!newDelta.addOldNodes.isEmpty()) { /* We have a delta to propagate */ Vector blockvector=bblock.next(); for(int i=0;i nodeset, HashSet deltaset, MySet externaledgeset) { + //Do heap edges first + HashSet externalnodes=new HashSet(); + externalnodes.addAll(delta.baseheapedge.keySet()); + externalnodes.addAll(delta.heapedgeadd.keySet()); + externalnodes.addAll(delta.heapedgeremove.keySet()); + //remove allinternal nodes + externalnodes.removeAll(nodeset); + for(AllocNode extNode:externalnodes) { + //Compute set of edges from given node + MySet edges=new MySet(delta.baseheapedge.get(extNode)); + edges.removeAll(delta.heapedgeremove.get(extNode)); + edges.addAll(delta.heapedgeadd.get(extNode)); + + for(Edge e:edges) { + if (nodeset.contains(e.dst)) + externaledgeset.add(e); + } + } + + //Do heap edges first + HashSet temps=new HashSet(); + temps.addAll(delta.basevaredge.keySet()); + temps.addAll(delta.varedgeadd.keySet()); + temps.addAll(delta.varedgeremove.keySet()); + //remove allinternal nodes + temps.removeAll(nodeset); + + for(TempDescriptor tmp:temps) { + //Compute set of edges from given node + MySet edges=new MySet(delta.basevaredge.get(tmp)); + edges.removeAll(delta.varedgeremove.get(tmp)); + edges.addAll(delta.varedgeadd.get(tmp)); + + for(Edge e:edges) { + if (nodeset.contains(e.dst)) + externaledgeset.add(e); + } + } + } + + void removeEdges(Delta delta, HashSet nodeset, MySet edgeset, MySet externaledgeset) { + //Want to remove the set of internal edges + for(Edge e:edgeset) { + if (e.src!=null) { + if (delta.heapedgeadd.containsKey(e.src)&&delta.heapedgeadd.get(e.src).contains(e)) { + //remove edge if it is in the add set + delta.heapedgeadd.get(e.src).remove(e); + } else { + //add edge to to the remove set + if (!delta.heapedgeremove.containsKey(e.src)) + delta.heapedgeremove.put(e.src, new MySet()); + delta.heapedgeremove.get(e.src).add(e); + } + } + } + + //Want to remove the set of external edges + for(Edge e:externaledgeset) { + //want to remove the set of internal edges + if (e.src!=null) { + if (delta.heapedgeadd.containsKey(e.src)&&delta.heapedgeadd.get(e.src).contains(e)) { + //remove edge if it is in the add set + delta.heapedgeadd.get(e.src).remove(e); + } else { + //add edge to to the remove set + if (!delta.heapedgeremove.containsKey(e.src)) + delta.heapedgeremove.put(e.src, new MySet()); + delta.heapedgeremove.get(e.src).add(e); + } + } else { + if (delta.varedgeadd.containsKey(e.srcvar)&&delta.varedgeadd.get(e.srcvar).contains(e)) { + //remove edge if it is in the add set + delta.varedgeadd.get(e.srcvar).remove(e); + } else { + //add edge to to the remove set + if (!delta.varedgeremove.containsKey(e.srcvar)) + delta.varedgeremove.put(e.srcvar,new MySet()); + delta.varedgeremove.get(e.srcvar).add(e); + } + } + } + } Delta processFlatCall(BBlock callblock, int callindex, FlatCall fcall, Delta delta, Graph graph) { @@ -367,6 +478,7 @@ public class Pointer { if (delta.getInit()) { MySet edgeset=new MySet(); + MySet externaledgeset=new MySet(); HashSet nodeset=new HashSet(); HashSet targetSet=new HashSet(); Stack tovisit=new Stack(); @@ -387,13 +499,20 @@ public class Pointer { //Fix mapping fixMapping(fcall, targets, null, newDelta, callblock, callindex); + //Compute edges into region to splice out + computeExternalEdges(graph, delta, nodeset, null, externaledgeset); + + //Splice out internal edges + removeEdges(delta, nodeset, edgeset, externaledgeset); + graph.reachNode=nodeset; graph.reachEdge=edgeset; //Apply diffs to graph - applyDiffs(graph, delta); + applyDiffs(graph, delta, true); } else { MySet edgeset=new MySet(); + MySet externaledgeset=new MySet(); HashSet nodeset=new HashSet(); MySet oldedgeset=graph.reachEdge; HashSet oldnodeset=graph.reachNode; @@ -431,13 +550,45 @@ public class Pointer { //Fix mapping fixMapping(fcall, targets, oldedgeset, newDelta, callblock, callindex); + //Compute edges into region to splice out + computeExternalEdges(graph, delta, oldnodeset, nodeset, externaledgeset); + + //Splice out internal edges + removeEdges(delta, nodeset, edgeset, externaledgeset); + //Apply diffs to graph applyDiffs(graph, delta); } - return newDelta; + return delta; } void applyDiffs(Graph graph, Delta delta) { + applyDiffs(graph, delta, false); + } + + void applyDiffs(Graph graph, Delta delta, boolean genbackwards) { + //build backwards map if requested + if (genbackwards&&graph.backMap==null) { + graph.backMap=new HashMap>(); + if (graph.parent.backMap==null) { + graph.parent.backMap=new HashMap>(); + for(Map.Entry> entry:graph.nodeMap.entrySet()) { + for(Edge e:entry.getValue()) { + if (!graph.parent.backMap.containsKey(e.dst)) + graph.parent.backMap.put(e.dst, new MySet()); + graph.parent.backMap.get(e.dst).add(e); + } + } + for(Map.Entry> entry:graph.varMap.entrySet()) { + for(Edge e:entry.getValue()) { + if (!graph.parent.backMap.containsKey(e.dst)) + graph.parent.backMap.put(e.dst, new MySet()); + graph.parent.backMap.get(e.dst).add(e); + } + } + } + } + //Add hidden base edges for(Map.Entry> e: delta.baseheapedge.entrySet()) { AllocNode node=e.getKey(); @@ -473,6 +624,13 @@ public class Pointer { graph.nodeMap.put(node, (MySet)graph.parent.nodeMap.get(node).clone()); } graph.nodeMap.get(node).addAll(edgestoadd); + if (genbackwards) { + for(Edge eadd:edgestoadd) { + if (!graph.backMap.containsKey(eadd.dst)) + graph.backMap.put(eadd.dst, new MySet()); + graph.backMap.get(eadd.dst).add(eadd); + } + } } //Remove var edges @@ -496,12 +654,25 @@ public class Pointer { TempDescriptor tmp=e.getKey(); MySet edgestoadd=e.getValue(); graph.varMap.put(tmp, (MySet) edgestoadd.clone()); + if (genbackwards) { + for(Edge eadd:edgestoadd) { + if (!graph.backMap.containsKey(eadd.dst)) + graph.backMap.put(eadd.dst, new MySet()); + graph.backMap.get(eadd.dst).add(eadd); + } + } } //Add node additions for(AllocNode node:delta.addNodeAges) { graph.nodeAges.add(node); } + + for(Map.Entry nodeentry:delta.addOldNodes.entrySet()) { + AllocNode node=nodeentry.getKey(); + Boolean ispresent=nodeentry.getValue(); + graph.oldNodes.put(node, ispresent); + } } Delta processSetFieldElementNode(FlatNode node, Delta delta, Graph graph) { @@ -694,7 +865,7 @@ public class Pointer { applyDiffs(graph, delta); return delta; } - + Delta processNewNode(FlatNew node, Delta delta, Graph graph) { AllocNode summary=allocFactory.getAllocNode(node, true); AllocNode single=allocFactory.getAllocNode(node, false); @@ -719,6 +890,10 @@ public class Pointer { applyDiffs(graph, delta); //Note that we create a single node delta.addNodeAges.add(single); + //Kill the old node + if (delta.addOldNodes.containsKey(single)||delta.baseOldNodes.containsKey(single)) { + delta.addOldNodes.put(single, Boolean.FALSE); + } } else { /* 1. Fix up the variable edge additions */ @@ -800,6 +975,11 @@ public class Pointer { delta.addNodeAges.add(summary); } + //Kill the old node if someone tries to add it + if (delta.addOldNodes.containsKey(single)||delta.baseOldNodes.containsKey(single)) { + delta.addOldNodes.put(single, Boolean.FALSE); + } + //Apply incoming diffs to graph applyDiffs(graph, delta); } @@ -883,6 +1063,12 @@ public class Pointer { graph.varMap.putAll(delta.varedgeadd); //Record that this is initial set... graph.nodeAges.addAll(delta.addNodeAges); + //Add old nodes + for(Map.Entry oldentry:delta.addOldNodes.entrySet()) { + if (oldentry.getValue().booleanValue()) { + graph.oldNodes.put(oldentry.getKey(), Boolean.TRUE); + } + } } else { newdelta=new Delta(null, false); //merge in heap edges and variables @@ -901,6 +1087,15 @@ public class Pointer { for(Map.Entry> heapedge:delta.heapedgeadd.entrySet()) { AllocNode nsrc=heapedge.getKey(); MySet edges=heapedge.getValue(); + + if (graph.backMap!=null) { + for(Edge e:edges) { + if (!graph.backMap.containsKey(e.dst)) + graph.backMap.put(e.dst, new MySet()); + graph.backMap.get(e.dst).add(e); + } + } + if (!graph.nodeMap.containsKey(nsrc)) { graph.nodeMap.put(nsrc, new MySet()); } @@ -929,6 +1124,14 @@ public class Pointer { for(Map.Entry> varedge:delta.varedgeadd.entrySet()) { TempDescriptor tmpsrc=varedge.getKey(); MySet edges=varedge.getValue(); + if (graph.backMap!=null) { + for(Edge e:edges) { + if (!graph.backMap.containsKey(e.dst)) + graph.backMap.put(e.dst, new MySet()); + graph.backMap.get(e.dst).add(e); + } + } + if (!graph.varMap.containsKey(tmpsrc)) { graph.varMap.put(tmpsrc, new MySet()); } @@ -957,5 +1160,13 @@ public class Pointer { newDelta.baseNodeAges.add(node); } } + for(Map.Entry oldentry:delta.addOldNodes.entrySet()) { + AllocNode node=oldentry.getKey(); + boolean ispresent=oldentry.getValue().booleanValue(); + if (ispresent&&!graph.oldNodes.containsKey(node)) { + graph.oldNodes.put(node, Boolean.TRUE); + newDelta.baseOldNodes.put(node, Boolean.TRUE); + } + } } } \ No newline at end of file -- 2.34.1