From 59eb36a554086a0d557aecefbf6a84ee261125d0 Mon Sep 17 00:00:00 2001 From: bdemsky Date: Tue, 15 Mar 2011 09:53:19 +0000 Subject: [PATCH] bug fixes for the day....lots of them --- Robust/src/Analysis/Pointer/Delta.java | 10 +- Robust/src/Analysis/Pointer/Graph.java | 2 + Robust/src/Analysis/Pointer/Pointer.java | 266 +++++++++++++++++------ 3 files changed, 205 insertions(+), 73 deletions(-) diff --git a/Robust/src/Analysis/Pointer/Delta.java b/Robust/src/Analysis/Pointer/Delta.java index f4806045..c02cc6c5 100644 --- a/Robust/src/Analysis/Pointer/Delta.java +++ b/Robust/src/Analysis/Pointer/Delta.java @@ -199,6 +199,12 @@ public class Delta { varedgeadd.get(e.srcvar).add(e); } + public void removeEdges(MySet eset) { + for(Edge e:eset) { + removeEdge(e); + } + } + public void removeEdge(Edge e) { if (e.src!=null) { removeHeapEdge(e); @@ -218,8 +224,8 @@ public class Delta { } public void removeVarEdge(Edge e) { - if (varedgeadd.containsKey(e.src)&&varedgeadd.get(e.src).contains(e)) - varedgeadd.get(e.src).remove(e); + if (varedgeadd.containsKey(e.srcvar)&&varedgeadd.get(e.srcvar).contains(e)) + varedgeadd.get(e.srcvar).remove(e); if (!varedgeremove.containsKey(e.srcvar)) varedgeremove.put(e.srcvar, new MySet(e)); else diff --git a/Robust/src/Analysis/Pointer/Graph.java b/Robust/src/Analysis/Pointer/Graph.java index 1dbeec35..d4c5fb9a 100644 --- a/Robust/src/Analysis/Pointer/Graph.java +++ b/Robust/src/Analysis/Pointer/Graph.java @@ -39,6 +39,8 @@ public class Graph { MySet reachEdge; HashSet reachNode; MySet externalEdgeSet; + /* These edges were created by the caller */ + MySet callerEdges; /* Need this information for mapping in callee results */ HashSet nodeAges; diff --git a/Robust/src/Analysis/Pointer/Pointer.java b/Robust/src/Analysis/Pointer/Pointer.java index a801f12d..f52dedec 100644 --- a/Robust/src/Analysis/Pointer/Pointer.java +++ b/Robust/src/Analysis/Pointer/Pointer.java @@ -84,19 +84,19 @@ public class Pointer { if (ppoint.getIndex()==-1) { //Build base graph for entrance to this basic block - //System.out.println("Processing "+bblock.nodes.get(0).toString().replace(' ','_')); - //delta.print(); + System.out.println("Processing "+bblock.nodes.get(0).toString().replace(' ','_')); + delta.print(); delta=applyInitDelta(delta, bblock); - //System.out.println("Generating:"); - //delta.print(); + System.out.println("Generating:"); + delta.print(); } else { - //System.out.println("Processing Call "+bblock.nodes.get(ppoint.getIndex()).toString().replace(' ','_')); - //delta.print(); + System.out.println("Processing Call "+bblock.nodes.get(ppoint.getIndex()).toString().replace(' ','_')); + delta.print(); startindex=ppoint.getIndex()+1; delta=applyCallDelta(delta, bblock); - //System.out.println("Generating:"); - //delta.print(); + System.out.println("Generating:"); + delta.print(); } Graph graph=bbgraphMap.get(bblock); Graph nodeGraph=null; @@ -107,14 +107,14 @@ public class Pointer { //Compute delta at exit of each node for(int i=startindex; i e:graphMap.entrySet()) { FlatNode fn=e.getKey(); Graph g=e.getValue(); @@ -185,21 +186,28 @@ public class Pointer { edgeSet.addAll(graph.parent.nodeMap.get(node)); newDelta.heapedgeadd.put(node, edgeSet); - /* Compute ages */ - if (graph.nodeAges.contains(node)) - 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); } } + + for(AllocNode node:graph.oldNodes.keySet()) { + if (graph.oldNodes.get(node).booleanValue()) + newDelta.addOldNodes.put(node, Boolean.TRUE); + } + + for(AllocNode node:graph.parent.oldNodes.keySet()) { + //make sure child doesn't override + if (!graph.oldNodes.containsKey(node)) + newDelta.addOldNodes.put(node, Boolean.TRUE); + } + + newDelta.addNodeAges.addAll(graph.nodeAges); + newDelta.addNodeAges.addAll(graph.parent.nodeAges); } /* This function build the delta for the exit of a basic block. */ @@ -284,8 +292,8 @@ public class Pointer { boolean first=true; for(PPoint caller:returnMap.get(bblock)) { - //System.out.println("Sending Return BBlock to "+caller.getBBlock().nodes.get(caller.getIndex()).toString().replace(' ','_')); - //newDelta.print(); + System.out.println("Sending Return BBlock to "+caller.getBBlock().nodes.get(caller.getIndex()).toString().replace(' ','_')); + newDelta.print(); if (first) { newDelta.setBlock(caller); toprocess.add(newDelta); @@ -299,8 +307,8 @@ public class Pointer { //normal block Vector blockvector=bblock.next(); for(int i=0;i nodeset, HashSet deltaset, MySet externaledgeset) { //Do heap edges first @@ -535,7 +544,7 @@ public class Pointer { } } - //Do heap edges first + //Do var edges now HashSet temps=new HashSet(); temps.addAll(delta.basevaredge.keySet()); temps.addAll(delta.varedgeadd.keySet()); @@ -560,10 +569,10 @@ public class Pointer { /* This function removes the caller reachable edges from the * callee's heap. */ - void removeEdges(Delta delta, HashSet nodeset, MySet edgeset, MySet externaledgeset) { + void removeEdges(Graph graph, 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 (e.src!=null&&!graph.callerEdges.contains(e)) { delta.removeHeapEdge(e); } } @@ -571,7 +580,8 @@ public class Pointer { //Want to remove the set of external edges for(Edge e:externaledgeset) { //want to remove the set of internal edges - delta.removeEdge(e); + if (!graph.callerEdges.contains(e)) + delta.removeEdge(e); } } @@ -585,6 +595,7 @@ public class Pointer { HashSet targetSet=new HashSet(); Stack tovisit=new Stack(); TempDescriptor tmpthis=fcall.getThis(); + graph.callerEdges=new MySet(); //Handle the this temp processThisTargets(targetSet, graph, delta, newDelta, nodeset, tovisit, edgeset, tmpthis, null); @@ -605,7 +616,7 @@ public class Pointer { computeExternalEdges(graph, delta, nodeset, null, externaledgeset); //Splice out internal edges - removeEdges(delta, nodeset, edgeset, externaledgeset); + removeEdges(graph, delta, nodeset, edgeset, externaledgeset); //store data structures graph.externalEdgeSet=externaledgeset; @@ -628,7 +639,24 @@ public class Pointer { HashSet targetSet=new HashSet(); Stack tovisit=new Stack(); TempDescriptor tmpthis=fcall.getThis(); + //Fix up delta to get rid of unnecessary heap edge removals + for(Map.Entry> entry:delta.heapedgeremove.entrySet()) { + for(Iterator eit=entry.getValue().iterator();eit.hasNext();) { + Edge e=eit.next(); + if (graph.callerEdges.contains(e)) + eit.remove(); + } + } + //Fix up delta to get rid of unnecessary var edge removals + for(Map.Entry> entry:delta.varedgeremove.entrySet()) { + for(Iterator eit=entry.getValue().iterator();eit.hasNext();) { + Edge e=eit.next(); + if (graph.callerEdges.contains(e)) + eit.remove(); + } + } + //Handle the this temp processThisTargets(targetSet, graph, delta, newDelta, nodeset, tovisit, edgeset, tmpthis, oldnodeset); @@ -662,8 +690,16 @@ public class Pointer { fixMapping(fcall, graph.callTargets, 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); + removeEdges(graph, delta, nodeset, edgeset, externaledgeset); + + //Add external edges back in + processCallExternal(graph, delta, externaledgeset); + + //Move new edges that should be summarized + processSummarization(graph, delta); + //Add in new external edges graph.externalEdgeSet.addAll(externaledgeset); //Apply diffs to graph @@ -672,6 +708,101 @@ public class Pointer { return delta; } + void processSummarization(Graph graph, Delta delta) { + processSumHeapEdgeSet(delta.heapedgeadd, delta, graph); + processSumHeapEdgeSet(delta.baseheapedge, delta, graph); + processSumVarEdgeSet(delta.varedgeadd, delta, graph); + processSumVarEdgeSet(delta.basevaredge, delta, graph); + } + + void processSumVarEdgeSet(HashMap> map, Delta delta, Graph graph) { + MySet edgestoadd=new MySet(); + MySet edgestoremove=new MySet(); + for(Iterator>> eit=map.entrySet().iterator();eit.hasNext();) { + Map.Entry> entry=eit.next(); + MySet edgeset=entry.getValue(); + + for(Edge e:edgeset) { + Edge copy=e.copy(); + boolean rewrite=false; + if (copy.dst!=null&&graph.callNodeAges.contains(copy.dst)) { + copy.dst=allocFactory.getAllocNode(copy.dst, true); + rewrite=true; + } + if (rewrite) { + edgestoremove.add(e); + edgestoadd.add(copy); + } + } + } + for(Edge e:edgestoremove) { + delta.removeVarEdge(e); + } + for(Edge e:edgestoadd) { + delta.addVarEdge(e); + } + } + + void processSumHeapEdgeSet(HashMap> map, Delta delta, Graph graph) { + MySet edgestoadd=new MySet(); + MySet edgestoremove=new MySet(); + for(Iterator>> eit=map.entrySet().iterator();eit.hasNext();) { + Map.Entry> entry=eit.next(); + AllocNode node=entry.getKey(); + MySet edgeset=entry.getValue(); + + for(Edge e:edgeset) { + Edge copy=e.copy(); + boolean rewrite=false; + if (copy.src!=null&&graph.callNodeAges.contains(copy.src)) { + copy.src=allocFactory.getAllocNode(copy.src, true); + rewrite=true; + } + if (copy.dst!=null&&graph.callNodeAges.contains(copy.dst)) { + copy.dst=allocFactory.getAllocNode(copy.dst, true); + rewrite=true; + } + if (rewrite) { + edgestoremove.add(e); + edgestoadd.add(copy); + } + } + } + for(Edge e:edgestoremove) { + delta.removeHeapEdge(e); + } + for(Edge e:edgestoadd) { + delta.addHeapEdge(e); + } + } + + //Handle external edges + void processCallExternal(Graph graph, Delta newDelta, MySet externalEdgeSet) { + //Add external edges in + for(Edge e:externalEdgeSet) { + //First did we age the source + Edge newedge=e.copy(); + if (newedge.src!=null&&!e.src.isSummary()&&graph.callNodeAges.contains(e.src)) { + AllocNode summaryNode=allocFactory.getAllocNode(newedge.src, true); + newedge.src=summaryNode; + } + //Compute target + if (graph.callNodeAges.contains(e.dst)&&!e.dst.isSummary()) { + if (graph.callOldNodes.contains(e.dst)) { + //Need two edges + Edge copy=newedge.copy(); + mergeEdge(graph, newDelta, copy); + } + //Now add summarized node + newedge.dst=allocFactory.getAllocNode(newedge.dst, true); + mergeCallEdge(graph, newDelta, newedge); + } else { + //Add edge to single node + mergeEdge(graph, newDelta, newedge); + } + } + } + /* This function applies callee deltas to the caller heap. */ Delta applyCallDelta(Delta delta, BBlock bblock) { @@ -689,8 +820,7 @@ public class Pointer { AllocNode node=nodeit.next(); if (!graph.callNodeAges.contains(node)) { graph.callNodeAges.add(node); - } else { - nodeit.remove(); + newDelta.addNodeAges.add(node); } if (!graph.reachNode.contains(node)&&!node.isSummary()) { /* Need to age node in existing graph*/ @@ -714,32 +844,12 @@ public class Pointer { edgetoadd=origEdgeKey; } } - mergeEdge(graph, newDelta, edgetoadd); - } - } - //Add external edges in - for(Edge e:graph.externalEdgeSet) { - //First did we age the source - Edge newedge=e.copy(); - if (newedge.src!=null&&!e.src.isSummary()&&graph.callNodeAges.contains(e.src)) { - AllocNode summaryNode=allocFactory.getAllocNode(newedge.src, true); - newedge.src=summaryNode; - } - //Compute target - if (graph.callNodeAges.contains(e.dst)&&!e.dst.isSummary()) { - if (graph.callOldNodes.contains(e.dst)) { - //Need two edges - Edge copy=newedge.copy(); - mergeEdge(graph, newDelta, copy); - } - //Now add summarized node - newedge.dst=allocFactory.getAllocNode(newedge.dst, true); - mergeEdge(graph, newDelta, newedge); - } else { - //Add edge to single node - mergeEdge(graph, newDelta, newedge); + mergeCallEdge(graph, newDelta, edgetoadd); } } + + processCallExternal(graph, newDelta, graph.externalEdgeSet); + //Add edge for return value if (fcall.getReturnTemp()!=null) { MySet returnedge=delta.varedgeadd.get(returntmp); @@ -766,6 +876,21 @@ public class Pointer { } } + /* This is a call produced edge...need to remember this */ + + public void mergeCallEdge(Graph graph, Delta newDelta, Edge edgetoadd) { + if (edgetoadd!=null) { + Edge match=graph.getMatch(edgetoadd); + + if (match==null||!match.subsumes(edgetoadd)) { + Edge mergededge=edgetoadd.merge(match); + newDelta.addEdge(mergededge); + graph.callerEdges.add(mergededge); + System.out.println("ADDING: "+ mergededge); + } + } + } + /* Summarizes out of context nodes in graph */ void summarizeInGraph(Graph graph, Delta newDelta, AllocNode singleNode) { @@ -778,7 +903,7 @@ public class Pointer { Edge rewrite=e.rewrite(singleNode, summaryNode); //Remove old edge newDelta.removeHeapEdge(e); - mergeEdge(graph, newDelta, rewrite); + mergeCallEdge(graph, newDelta, rewrite); } //Handle incoming edges @@ -789,7 +914,7 @@ public class Pointer { Edge match=graph.getMatch(e); Edge rewrite=match.rewrite(singleNode, summaryNode); newDelta.removeEdge(match); - mergeEdge(graph, newDelta, rewrite); + mergeCallEdge(graph, newDelta, rewrite); } } } @@ -1122,7 +1247,7 @@ public class Pointer { if (edgeRemove!=null) edgeRemove.remove(e); //Explicitly add it to the add set unless it is already in the graph - if ((!existingEdges.contains(e)||!existingEdges.get(e).isNew())&&(e.fd==null||typeUtil.isSuperorType(e.fd.getType(), e.dst.getType()))) { + if (!existingEdges.contains(e)||!existingEdges.get(e).isNew()) { delta.addHeapEdge(e); } } @@ -1380,7 +1505,6 @@ public class Pointer { MySet dstedges=graph.nodeMap.get(nsrc); MySet diffedges=new MySet(); for(Edge e:edges) { - if (!dstedges.contains(e)) { //We have a new edge diffedges.add(e); -- 2.34.1