From 339cff2b21bc2b95b6a7321800e25a45d3ddf632 Mon Sep 17 00:00:00 2001 From: bdemsky Date: Wed, 26 Jan 2011 23:04:52 +0000 Subject: [PATCH] more work towards new points to analysis --- Robust/src/Analysis/Pointer/Graph.java | 2 +- Robust/src/Analysis/Pointer/GraphManip.java | 21 ++++++++ Robust/src/Analysis/Pointer/Pointer.java | 59 ++++++++++++++++----- 3 files changed, 67 insertions(+), 15 deletions(-) diff --git a/Robust/src/Analysis/Pointer/Graph.java b/Robust/src/Analysis/Pointer/Graph.java index 9b801573..a835e911 100644 --- a/Robust/src/Analysis/Pointer/Graph.java +++ b/Robust/src/Analysis/Pointer/Graph.java @@ -5,7 +5,6 @@ import Analysis.Pointer.AllocFactory.AllocNode; import IR.Flat.*; public class Graph { - /* This is field is set is this Graph is just a delta on the parent * graph. */ @@ -13,6 +12,7 @@ public class Graph { HashMap> nodeMap; HashMap> varMap; HashMap> backMap; + HashSet strongUpdateSet; public Graph(Graph parent) { nodeMap=new HashMap>(); diff --git a/Robust/src/Analysis/Pointer/GraphManip.java b/Robust/src/Analysis/Pointer/GraphManip.java index dcd5c29c..2dbb449a 100644 --- a/Robust/src/Analysis/Pointer/GraphManip.java +++ b/Robust/src/Analysis/Pointer/GraphManip.java @@ -1,4 +1,8 @@ package Analysis.Pointer; +import IR.Flat.*; +import IR.*; +import Analysis.Pointer.AllocFactory.AllocNode; +import java.util.*; public class GraphManip { static HashSet genEdges(TempDescriptor tmp, HashSet dstSet) { @@ -49,6 +53,23 @@ public class GraphManip { return edges; } + static HashSet getEdges(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); + } + if (delta.heapedgeadd.containsKey(node)) + for(Edge e:delta.heapedgeadd.get(node)) { + if (e.fd==fd) + nodes.add(e); + } + } + return nodes; + } + static HashSet getDiffNodes(Delta delta, TempDescriptor tmp) { HashSet nodes=new HashSet(); HashSet removeedges=delta.varedgeremove.get(tmp); diff --git a/Robust/src/Analysis/Pointer/Pointer.java b/Robust/src/Analysis/Pointer/Pointer.java index 8d0488fb..de72c898 100644 --- a/Robust/src/Analysis/Pointer/Pointer.java +++ b/Robust/src/Analysis/Pointer/Pointer.java @@ -176,16 +176,41 @@ public class Pointer { if (delta.getInit()) { HashSet srcNodes=GraphManip.getNodes(graph, delta, src); HashSet dstNodes=GraphManip.getNodes(graph, delta, dst); - HashSet edgesToAdd=GraphManip.genEdges(srcNodes, fd, dstNodes); + HashSet edgesToAdd=GraphManip.genEdges(srcNodes, fd, dstNodes); + HashSet edgesToRemove=null; if (dstNodes.size()==1&&!dstNodes.iterator().next().isSummary()) { /* Can do a strong update */ - - + edgesToRemove=GraphManip.getEdges(graph, delta, dstNodes, fd); } + /* Update diff */ + updateHeapDelta(graph, delta, edgesToAdd, edgesToRemove); + applyDiffs(graph, delta); } else { - - + /* First look at new sources */ + HashSet edgesToAdd=new HashSet(); + HashSet newSrcNodes=GraphManip.getDiffNodes(delta, src); + HashSet dstNodes=GraphManip.getDiffNodes(delta, dst); + edgesToAdd.addAll(GraphManip.genEdges(newSrcNodes, fd, dstNodes)); + HashSet newDstNodes=GraphManip.getDiffNodes(delta, dst); + HashSet edgesToRemove=null; + if (newDstNodes.size()!=0) { + if (dstNodes.size()==1&&!dstNodes.iterator().next().isSummary()) { + /* Need to undo strong update */ + if (graph.strongUpdateSet!=null) { + edgesToAdd.addAll(graph.strongUpdateSet); + graph.strongUpdateSet.clear(); + } + } else if (dstNodes.size()==0&&newDstNodes.size()==1&&!newDstNodes.iterator().next().isSummary()&&graph.strongUpdateSet==null) { + edgesToRemove=GraphManip.getEdges(graph, delta, dstNodes, fd); + } + HashSet srcNodes=GraphManip.getDiffNodes(delta, src); + edgesToAdd.addAll(GraphManip.genEdges(srcNodes, fd, newDstNodes)); + } + /* Update diff */ + updateHeapDelta(graph, delta, edgesToAdd, edgesToRemove); + applyDiffs(graph, delta); } + return delta; } Delta processCopyNode(FlatNode node, Delta delta, Graph graph) { @@ -193,8 +218,8 @@ public class Pointer { TempDescriptor dst; if (node.kind()==FKind.FlatOpNode) { FlatOpNode fon=(FlatOpNode) node; - src=fcn.getLeft(); - dst=fcn.getDst(); + src=fon.getLeft(); + dst=fon.getDest(); } else { FlatCastNode fcn=(FlatCastNode) node; src=fcn.getSrc(); @@ -289,23 +314,29 @@ public class Pointer { } 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) { + AllocNode src=e.src; + HashSet edgeAdd=delta.heapedgeadd.get(src); + HashSet existingEdges=graph.getEdges(src); //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)) + if (existingEdges.contains(e)) { + HashSet edgeRemove=delta.heapedgeremove.get(src); edgeRemove.add(e); + } } for(Edge e: edgestoAdd) { + AllocNode src=e.src; + HashSet edgeRemove=delta.heapedgeremove.get(src); + HashSet existingEdges=graph.getEdges(src); //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)) + if (!existingEdges.contains(e)) { + HashSet edgeAdd=delta.heapedgeadd.get(src); edgeAdd.add(e); + } } } @@ -379,7 +410,7 @@ public class Pointer { for(Map.Entry> entry:addheapedge.entrySet()) { AllocNode allocnode=entry.getKey(); - Util.relationUpdate(delta.heapedgeadd, allocnode, null. entry.getValue()); + Util.relationUpdate(delta.heapedgeadd, allocnode, null, entry.getValue()); } /* 4. Fix up the base heap edges */ -- 2.34.1