From 986c8afba41ed5565f65b1e3ea15233d0dafc910 Mon Sep 17 00:00:00 2001 From: bdemsky Date: Mon, 14 Mar 2011 02:26:34 +0000 Subject: [PATCH] lots of bugs --- Robust/src/Analysis/Pointer/BasicBlock.java | 23 ++- Robust/src/Analysis/Pointer/Delta.java | 20 +- Robust/src/Analysis/Pointer/Graph.java | 2 + Robust/src/Analysis/Pointer/GraphManip.java | 28 +++ Robust/src/Analysis/Pointer/Pointer.java | 202 +++++++++++++------- 5 files changed, 200 insertions(+), 75 deletions(-) diff --git a/Robust/src/Analysis/Pointer/BasicBlock.java b/Robust/src/Analysis/Pointer/BasicBlock.java index 80e122c4..6e78ce62 100644 --- a/Robust/src/Analysis/Pointer/BasicBlock.java +++ b/Robust/src/Analysis/Pointer/BasicBlock.java @@ -6,10 +6,16 @@ import IR.Flat.*; public class BasicBlock { public BBlock start; public BBlock exit; + public Set blockset; - public BasicBlock(BBlock start, BBlock exit) { + public BasicBlock(BBlock start, BBlock exit, Set blockset) { this.start=start; this.exit=exit; + this.blockset=blockset; + } + + public Set getBlocks() { + return blockset; } public BBlock getStart() { @@ -48,9 +54,12 @@ public class BasicBlock { Stack toprocess=new Stack(); HashMap map=new HashMap(); PointerMethod pm=new PointerMethod(); + HashSet blockset=new HashSet(); pm.analyzeMethod(fm); toprocess.add(fm); - map.put(fm, new BBlock()); + BBlock b=new BBlock(); + blockset.add(b); + map.put(fm, b); while(!toprocess.isEmpty()) { FlatNode fn=toprocess.pop(); @@ -63,7 +72,9 @@ public class BasicBlock { for(int i=0;i1) { //new basic block if (!map.containsKey(fn)) { - map.put(fn, new BBlock()); + BBlock newb=new BBlock(); + blockset.add(newb); + map.put(fn, newb); toprocess.add(fn); } //link block in @@ -93,6 +106,6 @@ public class BasicBlock { exit=block; } while(true); } - return new BasicBlock(map.get(fm), exit); + return new BasicBlock(map.get(fm), exit, blockset); } } diff --git a/Robust/src/Analysis/Pointer/Delta.java b/Robust/src/Analysis/Pointer/Delta.java index 38f69c67..f4806045 100644 --- a/Robust/src/Analysis/Pointer/Delta.java +++ b/Robust/src/Analysis/Pointer/Delta.java @@ -37,7 +37,6 @@ public class Delta { return this; } - boolean init; PPoint block; boolean callStart; @@ -60,8 +59,13 @@ public class Delta { this.block=block; } + public boolean isEmpty() { + return baseheapedge.isEmpty()&&basevaredge.isEmpty()&&heapedgeadd.isEmpty()&&heapedgeremove.isEmpty()&&varedgeadd.isEmpty()&&(varedgeremove==null||varedgeremove.isEmpty())&&baseNodeAges.isEmpty()&&addNodeAges.isEmpty()&&baseOldNodes.isEmpty()&&addOldNodes.isEmpty(); + } + public void print() { System.out.println("----------------------------------------------"); + System.out.println("init:"+init); System.out.println("baseheapedge:"+baseheapedge); System.out.println("basevaredge:"+basevaredge); System.out.println("heapedgeadd:"+heapedgeadd); @@ -120,13 +124,23 @@ public class Delta { Delta newdelta=new Delta(); newdelta.baseheapedge=baseheapedge; newdelta.basevaredge=basevaredge; - newdelta.heapedgeadd=heapedgeadd; newdelta.heapedgeremove=heapedgeremove; - newdelta.varedgeadd=varedgeadd; + newdelta.heapedgeadd=new HashMap>(); + newdelta.varedgeadd=new HashMap>(); newdelta.addNodeAges=addNodeAges; newdelta.baseNodeAges=baseNodeAges; newdelta.addOldNodes=addOldNodes; newdelta.baseOldNodes=baseOldNodes; + + for (Map.Entry> entry:heapedgeadd.entrySet()) { + newdelta.heapedgeadd.put(entry.getKey(), new MySet(entry.getValue())); + } + + for (Map.Entry> entry:varedgeadd.entrySet()) { + newdelta.varedgeadd.put(entry.getKey(), new MySet(entry.getValue())); + } + + for(Edge e:edges) { if (e.srcvar!=null) { if (!newdelta.varedgeadd.containsKey(e.srcvar)) { diff --git a/Robust/src/Analysis/Pointer/Graph.java b/Robust/src/Analysis/Pointer/Graph.java index 3fcfdab2..1dbeec35 100644 --- a/Robust/src/Analysis/Pointer/Graph.java +++ b/Robust/src/Analysis/Pointer/Graph.java @@ -3,6 +3,7 @@ import java.util.*; import Analysis.Disjoint.PointerMethod; import Analysis.Pointer.AllocFactory.AllocNode; import IR.Flat.*; +import IR.MethodDescriptor; import java.io.PrintWriter; public class Graph { @@ -46,6 +47,7 @@ public class Graph { /* Need this information for mapping in callee results */ HashSet callNodeAges; HashSet callOldNodes; + HashSet callTargets; public Graph(Graph parent) { nodeMap=new HashMap>(); diff --git a/Robust/src/Analysis/Pointer/GraphManip.java b/Robust/src/Analysis/Pointer/GraphManip.java index 73fde38b..ad41bf82 100644 --- a/Robust/src/Analysis/Pointer/GraphManip.java +++ b/Robust/src/Analysis/Pointer/GraphManip.java @@ -164,6 +164,34 @@ public class GraphManip { return newedges; } + + static MySet getDiffEdges(Delta delta, HashSet srcNodes, FieldDescriptor fd) { + MySet newedges=new MySet(); + for(Map.Entry> entry:delta.baseheapedge.entrySet()) { + AllocNode node=entry.getKey(); + if (srcNodes.contains(node)) { + MySet edges=entry.getValue(); + MySet removeedges=delta.heapedgeremove.get(node); + for(Edge e:edges) { + if ((removeedges==null||!removeedges.contains(e))&&(e.fd==fd)) { + newedges.add(e); + } + } + } + } + for(Map.Entry> entry:delta.heapedgeadd.entrySet()) { + AllocNode node=entry.getKey(); + if (srcNodes.contains(node)) { + MySet edges=entry.getValue(); + for(Edge e:edges) { + if (e.fd==fd) + newedges.add(e); + } + } + } + return newedges; + } + static MySet makeOld(MySet edgesin) { MySet edgeset=new MySet(); for(Edge e:edgesin) { diff --git a/Robust/src/Analysis/Pointer/Pointer.java b/Robust/src/Analysis/Pointer/Pointer.java index 98e0512a..a801f12d 100644 --- a/Robust/src/Analysis/Pointer/Pointer.java +++ b/Robust/src/Analysis/Pointer/Pointer.java @@ -2,6 +2,7 @@ package Analysis.Pointer; import java.util.*; import IR.Flat.*; import IR.*; +import Analysis.Liveness; import Analysis.Pointer.BasicBlock.BBlock; import Analysis.Pointer.AllocFactory.AllocNode; import java.io.*; @@ -12,6 +13,7 @@ public class Pointer { HashMap graphMap; HashMap> callMap; HashMap> returnMap; + HashMap> bblivetemps; State state; TypeUtil typeUtil; @@ -23,6 +25,7 @@ public class Pointer { this.state=state; this.blockMap=new HashMap(); this.bbgraphMap=new HashMap(); + this.bblivetemps=new HashMap>(); this.graphMap=new HashMap(); this.callMap=new HashMap>(); this.returnMap=new HashMap>(); @@ -34,8 +37,22 @@ public class Pointer { } public BasicBlock getBBlock(FlatMethod fm) { - if (!blockMap.containsKey(fm)) + if (!blockMap.containsKey(fm)) { blockMap.put(fm, BasicBlock.getBBlock(fm)); + Hashtable> livemap=Liveness.computeLiveTemps(fm); + for(BBlock bblock:blockMap.get(fm).getBlocks()) { + FlatNode fn=bblock.nodes.get(0); + if (fn==fm) { + HashSet fmset=new HashSet(); + fmset.addAll((List)Arrays.asList(fm.writesTemps())); + bblivetemps.put(bblock, fmset); + } else { + Set livetemps=livemap.get(fn); + bblivetemps.put(bblock, livetemps); + livetemps.add(returntmp); + } + } + } return blockMap.get(fm); } @@ -57,6 +74,7 @@ public class Pointer { public void doAnalysis() { toprocess.add(buildInitialContext()); + nextdelta: while(!toprocess.isEmpty()) { Delta delta=toprocess.remove(); PPoint ppoint=delta.getBlock(); @@ -66,44 +84,58 @@ 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(); delta=applyInitDelta(delta, bblock); + //System.out.println("Generating:"); + //delta.print(); } else { + //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(); } Graph graph=bbgraphMap.get(bblock); Graph nodeGraph=null; + boolean init=delta.getInit(); + if (!init&&delta.isEmpty()) + continue nextdelta; + //Compute delta at exit of each node for(int i=startindex; i e:bbgraphMap.entrySet()) { Graph g=e.getValue(); - plotGraph(g,"BB"+debugindex); + plotGraph(g,"BB"+e.getKey().nodes.get(0).toString().replace(' ','_')); debugindex++; } - + for(FlatMethod fm:blockMap.keySet()) { + System.out.println(fm.printMethod()); + } for(Map.Entry e:graphMap.entrySet()) { FlatNode fn=e.getKey(); Graph g=e.getValue(); plotGraph(g,"FN"+fn.toString()+debugindex); debugindex++; - } - for(FlatMethod fm:blockMap.keySet()) { - fm.printMethod(); - } + } } } @@ -252,6 +284,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(); if (first) { newDelta.setBlock(caller); toprocess.add(newDelta); @@ -265,6 +299,8 @@ public class Pointer { //normal block Vector blockvector=bblock.next(); for(int i=0;i edges=GraphManip.getEdges(graph, delta, node); - newDelta.heapedgeadd.put(node, edges); - edgeset.addAll(edges); - for(Edge e:edges) { - if (!nodeset.contains(e.dst)&&(oldnodeset==null||!oldnodeset.contains(e.dst))) { - nodeset.add(e.dst); - tovisit.add(e.dst); + if (!edges.isEmpty()) { + newDelta.heapedgeadd.put(node, edges); + edgeset.addAll(edges); + for(Edge e:edges) { + if (!nodeset.contains(e.dst)&&(oldnodeset==null||!oldnodeset.contains(e.dst))) { + nodeset.add(e.dst); + tovisit.add(e.dst); + } } } } @@ -378,7 +422,8 @@ public class Pointer { AllocNode node=e.dst; ClassDescriptor cd=node.getType().getClassDesc(); //Figure out exact method called and add to set - targets.add(cd.getCalledMethod(md)); + MethodDescriptor calledmd=cd.getCalledMethod(md); + targets.add(calledmd); } } return targets; @@ -445,6 +490,8 @@ public class Pointer { //First build of this graph //Build and enqueue delta...safe to just use existing delta Delta d=newDelta.changeParams(tmpMap, new PPoint(block.getStart())); + //System.out.println("AProcessing "+block.getStart().nodes.get(0).toString().replace(' ','_')); + //d.print(); toprocess.add(d); } else if (newmethod) { if (basedelta==null) { @@ -452,10 +499,14 @@ public class Pointer { } //Build and enqueue delta Delta d=basedelta.changeParams(tmpMap, new PPoint(block.getStart())); + //System.out.println("BProcessing "+block.getStart().nodes.get(0).toString().replace(' ','_')); + //d.print(); toprocess.add(d); } else { //Build and enqueue delta Delta d=newDelta.changeParams(tmpMap, new PPoint(block.getStart())); + //System.out.println("CProcessing "+block.getStart().nodes.get(0).toString().replace(' ','_')); + //d.print(); toprocess.add(d); } } @@ -545,10 +596,10 @@ public class Pointer { computeReachableNodes(graph, delta, newDelta, nodeset, tovisit, edgeset, null); //Compute call targets - HashSet targets=computeTargets(fcall, newDelta); + HashSet newtargets=computeTargets(fcall, newDelta); //Fix mapping - fixMapping(fcall, targets, null, newDelta, callblock, callindex); + fixMapping(fcall, newtargets, null, newDelta, callblock, callindex); //Compute edges into region to splice out computeExternalEdges(graph, delta, nodeset, null, externaledgeset); @@ -561,6 +612,7 @@ public class Pointer { graph.reachNode=nodeset; graph.reachEdge=edgeset; + graph.callTargets=newtargets; graph.callNodeAges=new HashSet(); graph.callOldNodes=new HashSet(); @@ -582,39 +634,38 @@ public class Pointer { //Go through each temp processParams(graph, delta, newDelta, nodeset, tovisit, edgeset, fcall, true); - //Go through each new heap edge that starts from old node MySet newedges=GraphManip.getDiffEdges(delta, oldnodeset); edgeset.addAll(newedges); for(Edge e:newedges) { + //Add new edges that start from old node to newDelta + AllocNode src=e.src; + if (!newDelta.heapedgeadd.containsKey(src)) { + newDelta.heapedgeadd.put(src, new MySet()); + } + newDelta.heapedgeadd.get(src).add(e); if (!nodeset.contains(e.dst)&&!oldnodeset.contains(e.dst)) { nodeset.add(e.dst); tovisit.add(e.dst); } } - + //Traverse all reachable nodes computeReachableNodes(graph, delta, newDelta, nodeset, tovisit, edgeset, oldnodeset); - //Compute call targets - HashSet targets=computeTargets(fcall, newDelta); - + HashSet newtargets=computeTargets(fcall, newDelta); + graph.callTargets.addAll(newtargets); //add in new nodeset and edgeset oldnodeset.addAll(nodeset); oldedgeset.addAll(edgeset); - //Fix mapping - fixMapping(fcall, targets, oldedgeset, newDelta, callblock, callindex); - + 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); - //Add in new external edges graph.externalEdgeSet.addAll(externaledgeset); - //Apply diffs to graph applyDiffs(graph, delta); } @@ -839,7 +890,10 @@ public class Pointer { for(Map.Entry> e: delta.varedgeadd.entrySet()) { TempDescriptor tmp=e.getKey(); MySet edgestoadd=e.getValue(); - graph.varMap.put(tmp, (MySet) edgestoadd.clone()); + if (graph.varMap.containsKey(tmp)) { + graph.varMap.get(tmp).addAll(edgestoadd); + } else + graph.varMap.put(tmp, (MySet) edgestoadd.clone()); if (genbackwards) { for(Edge eadd:edgestoadd) { if (!graph.backMap.containsKey(eadd.dst)) @@ -916,7 +970,7 @@ public class Pointer { //Kill new edges if (graph.strongUpdateSet!=null&&fd!=null) { - MySet otherEdgesToRemove=GraphManip.getDiffEdges(delta, dstNodes); + MySet otherEdgesToRemove=GraphManip.getDiffEdges(delta, dstNodes, fd); if (edgesToRemove!=null) edgesToRemove.addAll(otherEdgesToRemove); else @@ -1023,7 +1077,7 @@ public class Pointer { return delta; } - static void updateVarDelta(Graph graph, Delta delta, TempDescriptor tmp, MySet edgestoAdd, MySet edgestoRemove) { + void updateVarDelta(Graph graph, Delta delta, TempDescriptor tmp, MySet edgestoAdd, MySet edgestoRemove) { MySet edgeAdd=delta.varedgeadd.get(tmp); MySet edgeRemove=delta.varedgeremove.get(tmp); MySet existingEdges=graph.getEdges(tmp); @@ -1040,12 +1094,12 @@ 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)) + if (!existingEdges.contains(e)&&typeUtil.isSuperorType(tmp.getType(),e.dst.getType())) delta.addVarEdge(e); } } - static void updateHeapDelta(Graph graph, Delta delta, MySet edgestoAdd, MySet edgestoRemove) { + void updateHeapDelta(Graph graph, Delta delta, MySet edgestoAdd, MySet edgestoRemove) { if (edgestoRemove!=null) for(Edge e: edgestoRemove) { AllocNode src=e.src; @@ -1068,7 +1122,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()) { + if ((!existingEdges.contains(e)||!existingEdges.get(e).isNew())&&(e.fd==null||typeUtil.isSuperorType(e.fd.getType(), e.dst.getType()))) { delta.addHeapEdge(e); } } @@ -1098,7 +1152,9 @@ public class Pointer { //Add it into the diffs delta.varedgeadd.put(tmp, newedges); //Remove the old edges - delta.varedgeremove.put(tmp, (MySet) graph.getEdges(tmp).clone()); + MySet oldedges=graph.getEdges(tmp); + if (!oldedges.isEmpty()) + delta.varedgeremove.put(tmp, (MySet) oldedges); //Apply incoming diffs to graph applyDiffs(graph, delta); //Note that we create a single node @@ -1266,15 +1322,22 @@ public class Pointer { bbgraphMap.put(block, new Graph(null)); newGraph=true; } - Delta newdelta; Graph graph=bbgraphMap.get(block); if (newGraph) { - newdelta=new Delta(null, true); + Delta newdelta=new Delta(null, true); //Add in heap edges and throw away original diff - graph.nodeMap.putAll(delta.heapedgeadd); + + for(Map.Entry> entry:delta.heapedgeadd.entrySet()) { + graph.nodeMap.put(entry.getKey(), new MySet(entry.getValue())); + } //Add in var edges and throw away original diff - graph.varMap.putAll(delta.varedgeadd); + Set livetemps=bblivetemps.get(block); + + for(Map.Entry> entry:delta.varedgeadd.entrySet()) { + if (livetemps.contains(entry.getKey())) + graph.varMap.put(entry.getKey(), new MySet(entry.getValue())); + } //Record that this is initial set... graph.nodeAges.addAll(delta.addNodeAges); //Add old nodes @@ -1283,15 +1346,15 @@ public class Pointer { graph.oldNodes.put(oldentry.getKey(), Boolean.TRUE); } } + return newdelta; } else { - newdelta=new Delta(null, false); + Delta newdelta=new Delta(null, false); //merge in heap edges and variables mergeHeapEdges(graph, delta, newdelta); - mergeVarEdges(graph, delta, newdelta); + mergeVarEdges(graph, delta, newdelta, block); mergeAges(graph, delta, newdelta); + return newdelta; } - - return newdelta; } /* This function merges in the heap edges. It updates delta to be @@ -1317,6 +1380,7 @@ 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); @@ -1341,36 +1405,40 @@ public class Pointer { /* This function merges in the var edges. It updates delta to be * the difference */ - void mergeVarEdges(Graph graph, Delta delta, Delta newdelta) { + void mergeVarEdges(Graph graph, Delta delta, Delta newdelta, BBlock block) { //Merge in edges + Set livetemps=bblivetemps.get(block); + for(Map.Entry> varedge:delta.varedgeadd.entrySet()) { TempDescriptor tmpsrc=varedge.getKey(); - MySet edges=varedge.getValue(); - if (graph.backMap!=null) { + if (livetemps.contains(tmpsrc)) { + 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()); + } + MySet dstedges=graph.varMap.get(tmpsrc); + MySet diffedges=new MySet(); 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 (!dstedges.contains(e)) { + //We have a new edge + diffedges.add(e); + dstedges.add(e); + } } - } - - if (!graph.varMap.containsKey(tmpsrc)) { - graph.varMap.put(tmpsrc, new MySet()); - } - MySet dstedges=graph.varMap.get(tmpsrc); - MySet diffedges=new MySet(); - for(Edge e:edges) { - if (!dstedges.contains(e)) { - //We have a new edge - diffedges.add(e); - dstedges.add(e); + //Done with edge set... + if (diffedges.size()>0) { + //completely new + newdelta.basevaredge.put(tmpsrc,diffedges); } } - //Done with edge set... - if (diffedges.size()>0) { - //completely new - newdelta.basevaredge.put(tmpsrc,diffedges); - } } } -- 2.34.1