From 13be5368950a5ce77e6cba02c75bd8fee88e8f31 Mon Sep 17 00:00:00 2001 From: yeom Date: Fri, 22 Feb 2013 06:22:32 +0000 Subject: [PATCH] changes. --- Robust/src/Analysis/SSJava/BuildLattice.java | 273 ++++++++++++------ .../src/Analysis/SSJava/HierarchyGraph.java | 69 ++++- .../Analysis/SSJava/LocationInference.java | 10 +- 3 files changed, 262 insertions(+), 90 deletions(-) diff --git a/Robust/src/Analysis/SSJava/BuildLattice.java b/Robust/src/Analysis/SSJava/BuildLattice.java index 2d65122a..57766ef9 100644 --- a/Robust/src/Analysis/SSJava/BuildLattice.java +++ b/Robust/src/Analysis/SSJava/BuildLattice.java @@ -22,12 +22,15 @@ public class BuildLattice { private Map, Integer> mapItemToHighestIndex; + private Map, Set> mapLatticeToLocalLocSet; + public BuildLattice(LocationInference infer) { this.infer = infer; this.mapSharedNodeToTripleItem = new HashMap(); this.mapHNodeToHighestIndex = new HashMap(); this.mapItemToHighestIndex = new HashMap, Integer>(); this.mapDescToIntermediateLocMap = new HashMap>(); + this.mapLatticeToLocalLocSet = new HashMap, Set>(); } public SSJavaLattice buildLattice(Descriptor desc) { @@ -262,7 +265,8 @@ public class BuildLattice { // 1) find the lowest node m in the lattice that is above hnode in the lattice // 2) count the number of non-shared nodes d between the hnode and the node m - int numNonSharedNodes; + // int numNonSharedNodes; + int dist; HNode SCNode; if (hNode.isDirectCombinationNode()) { @@ -272,7 +276,8 @@ public class BuildLattice { System.out.println(" # direct combine node::combineSkeletonNodeSet=" + combineSet); SCNode = scGraph.getCombinationNode(combineSet); - numNonSharedNodes = -1; + // numNonSharedNodes = -1; + dist = 0; } else { Set aboveSet = new HashSet(); @@ -285,7 +290,7 @@ public class BuildLattice { scGraph.getCombinationNode(combineSkeletonNodeSet); - System.out.println(" firstnode=" + System.out.println(" firstnodeOfSimpleGraph=" + hierarchyGraph.getFirstNodeOfCombinationNodeChainSet(combineSkeletonNodeSet)); aboveSet.addAll(hierarchyGraph .getFirstNodeOfCombinationNodeChainSet(combineSkeletonNodeSet)); @@ -299,6 +304,7 @@ public class BuildLattice { System.out.println(" hierarchyGraph.getSkeleteNodeSetReachTo(" + hNode + ")=" + hierarchyGraph.getSkeleteNodeSetReachTo(hNode)); aboveSet.addAll(hierarchyGraph.getSkeleteNodeSetReachTo(hNode)); + System.out.println(" aboveset of " + hNode + "=" + aboveSet); // assert aboveSet.size() == 1; SCNode = aboveSet.iterator().next(); } @@ -310,33 +316,43 @@ public class BuildLattice { HNode aboveNode = (HNode) iterator2.next(); endSet.add(scGraph.getCurrentHNode(aboveNode)); } - numNonSharedNodes = hierarchyGraph.countNonSharedNode(hNode, endSet); + dist = hierarchyGraph.computeDistance(hNode, endSet); + System.out.println("##### " + hNode + "::dist=" + dist); + + // numNonSharedNodes = hierarchyGraph.countNonSharedNode(hNode, endSet); - System.out.println(" node=" + hNode + " above=" + endSet + " distance=" - + numNonSharedNodes + " SCNode=" + SCNode); + System.out.println(" COUNT-RESULT::node=" + hNode + " above=" + endSet + " distance=" + + dist + " SCNode=" + SCNode); } // 3) convert the node m into a chain of nodes with the last node in the chain having m’s // outgoing edges. Set outgoingSCNodeSet = scGraph.getOutgoingNodeSet(SCNode); - System.out.println(" SCNODE outgoing hnode set=" + outgoingSCNodeSet); + System.out.println(" outgoing scnode set from " + SCNode + "=" + outgoingSCNodeSet); + // convert hnodes to location names + String startLocName = locSummary.getLocationName(SCNode.getName()); Set outgoingLocNameSet = new HashSet(); for (Iterator iterator2 = outgoingSCNodeSet.iterator(); iterator2.hasNext();) { HNode outSCNode = (HNode) iterator2.next(); String locName = locSummary.getLocationName(outSCNode.getName()); - System.out.println(" outSCNode=" + outSCNode + " -> locName=" - + locName); + if (!locName.equals(outSCNode.getName())) { + System.out.println(" outSCNode=" + outSCNode + " -> locName=" + + locName); + } outgoingLocNameSet.add(locName); } + if (outgoingLocNameSet.isEmpty()) { + outgoingLocNameSet.add(lattice.getBottomItem()); + } + // 4) If hnode is not a shared location, check if there already exists a local variable // node that has distance d below m along this chain. If such a node // does not exist, insert it. String locName = - getNewLocation(lattice, SCNode.getName(), outgoingLocNameSet, numNonSharedNodes, - hNode.isSharedNode()); - System.out.println(" locName=" + locName); + getNewLocation(lattice, startLocName, outgoingLocNameSet, dist, hNode.isSharedNode()); + System.out.println(" ###hNode=" + hNode + "---->locName=" + locName); locSummary.addMapHNodeNameToLocationName(hNode.getName(), locName); } @@ -345,25 +361,173 @@ public class BuildLattice { return lattice; } + private void addLocalLocation(SSJavaLattice lattice, String localLoc) { + if (!mapLatticeToLocalLocSet.containsKey(lattice)) { + mapLatticeToLocalLocSet.put(lattice, new HashSet()); + } + mapLatticeToLocalLocSet.get(lattice).add(localLoc); + } + + private boolean isLocalLocation(SSJavaLattice lattice, String localLoc) { + if (mapLatticeToLocalLocSet.containsKey(lattice)) { + return mapLatticeToLocalLocSet.get(lattice).contains(localLoc); + } + return false; + } + public String getNewLocation(SSJavaLattice lattice, String start, Set endSet, int dist, boolean isShared) { - System.out.println(" getNewLocation:: start=" + start + " endSet=" + endSet + " dist=" + System.out.println(" #GETNEWLOCATION:: start=" + start + " endSet=" + endSet + " dist=" + + dist + " isShared=" + isShared); + // if (dist == -1) { + // if (isShared) { + // // if the node is a shared one, check if the next node is shared + // // if not, need to insert a new shared node + // return recur_getNewLocation(lattice, start, endSet, dist + 1, isShared); + // } else { + // return start; + // } + // + // } + return recur_getNewLocation(lattice, start, start, endSet, dist, isShared); + } + + private String recur_getNewLocation(SSJavaLattice lattice, String start, String cur, + Set endSet, int dist, boolean isShared) { + + System.out.println(" recur_getNewLocation cur=" + cur + " dist=" + dist); + + if (dist == 0) { + if (isShared) { + // first check if there already exists a non-shared node at distance d + if (!isLocalLocation(lattice, cur) && !start.equals(cur)) { + // if not, need to insert a new local location at this point + System.out.println("if not, need to insert a new local location at this point"); + String newLocName = "ILOC" + (LocationInference.locSeed++); + Set lowerSet = new HashSet(); + lowerSet.addAll(lattice.get(cur)); + lattice.insertNewLocationBetween(cur, lowerSet, newLocName); + addLocalLocation(lattice, newLocName); + + // assign the new local location to cur + cur = newLocName; + } + + Set connectedSet = lattice.get(cur); + if (connectedSet == null) { + connectedSet = new HashSet(); + } + System.out.println("cur=" + cur + " connectedSet=" + connectedSet); + + // check if there already exists a shared node that has distance d + 1 on the chain + boolean needToInsertSharedNode = false; + if (connectedSet.equals(endSet)) { + needToInsertSharedNode = true; + } else { + // in this case, the current node is in the middle of the chain + assert connectedSet.size() == 1; + String below = connectedSet.iterator().next(); + if (lattice.isSharedLoc(below)) { + return below; + } else { + needToInsertSharedNode = true; + } + } + + if (needToInsertSharedNode) { + // no shared local location at d+1, need to insert it! + String newSharedLocName = "ILOC" + (LocationInference.locSeed++); + Set lowerSet = new HashSet(); + lowerSet.addAll(connectedSet); + lattice.insertNewLocationBetween(cur, lowerSet, newSharedLocName); + lattice.addSharedLoc(newSharedLocName); + addLocalLocation(lattice, newSharedLocName); + System.out.println(" INSERT NEW SHARED LOC=" + newSharedLocName); + cur = newSharedLocName; + } + + return cur; + + } else { + + return cur; + // if the node is not shared, check if a node at distance d is a local or combination node + // Set connectedSet = lattice.get(cur); + // if (connectedSet == null) { + // connectedSet = new HashSet(); + // } + // System.out + // .println("if the node is not shared, check if a node at distance d is a local or combination node connectedSet=" + // + connectedSet); + // // if (!start.equals(cur) && (cur.equals(lattice.getTopItem()) || + // connectedSet.equals(endSet))) { + // // if not, need to insert a new local location at this point + // System.out.println("NEED TO INSERT A NEW LOCAL LOC connectedSet=" + connectedSet); + // String newLocName = "ILOC" + (LocationInference.locSeed++); + // Set lowerSet = new HashSet(); + // lowerSet.addAll(connectedSet); + // lattice.insertNewLocationBetween(cur, lowerSet, newLocName); + // addLocalLocation(lattice, newLocName); + // return newLocName; + // } else { + // return cur; + // } + } + } + + Set connectedSet = lattice.get(cur); + if (connectedSet == null) { + connectedSet = new HashSet(); + } + + System.out.println("cur=" + cur + " connected set=" + connectedSet); + if (cur.equals(lattice.getTopItem()) || connectedSet.equals(endSet)) { + // if not, need to insert a new local location at this point + System.out.println("NEED TO INSERT A NEW LOCAL LOC FOR NEXT connectedSet=" + connectedSet); + String newLocName = "ILOC" + (LocationInference.locSeed++); + Set lowerSet = new HashSet(); + lowerSet.addAll(connectedSet); + lattice.insertNewLocationBetween(cur, lowerSet, newLocName); + addLocalLocation(lattice, newLocName); + cur = newLocName; + } else { + // in this case, the current node is in the middle of the chain + assert connectedSet.size() == 1; + cur = connectedSet.iterator().next(); + } + + if (!lattice.isSharedLoc(cur)) { + dist--; + } + return recur_getNewLocation(lattice, start, cur, endSet, dist, isShared); + + } + + public String getNewLocation2(SSJavaLattice lattice, String start, Set endSet, + int dist, boolean isShared) { + System.out.println(" #GETNEWLOCATION:: start=" + start + " endSet=" + endSet + " dist=" + dist + " isShared=" + isShared); if (dist == -1) { - return start; + if (isShared) { + // if the node is a shared one, check if the next node is shared + // if not, need to insert a new shared node + return recur_getNewLocation2(lattice, start, endSet, dist + 1, isShared); + } else { + return start; + } + } - return recur_getNewLocation(lattice, start, endSet, dist, isShared); + return recur_getNewLocation2(lattice, start, endSet, dist, isShared); } - private String recur_getNewLocation(SSJavaLattice lattice, String cur, + private String recur_getNewLocation2(SSJavaLattice lattice, String cur, Set endSet, int dist, boolean isShared) { - System.out.println("H"); Set connectedSet = lattice.get(cur); if (connectedSet == null) { connectedSet = new HashSet(); } - System.out.println(" recur_getNewLocation cur=" + cur + " dist=" + dist + System.out.println(" recur_getNewLocation::cur=" + cur + " dist=" + dist + " connectedSet=" + connectedSet + " endSet=" + endSet); if (dist == 0 && isShared) { @@ -393,7 +557,7 @@ public class BuildLattice { lattice.get(cur).clear(); lattice.put(cur, newLocName); - System.out.println(" INSERT NEW SHARED NODE=" + newLocName + " above=" + cur + System.out.println(" INSERT NEW SHARED NODE=" + newLocName + " above=" + cur + " below=" + lattice.get(newLocName)); lattice.addSharedLoc(newLocName); @@ -404,7 +568,7 @@ public class BuildLattice { String next; - if (cur.equals(lattice.getTopItem()) || connectedSet.equals(endSet) || endSet.isEmpty()) { + if (cur.equals(lattice.getTopItem()) || connectedSet.equals(endSet) /* || endSet.isEmpty() */) { // if ( (cur.equals(lattice.getTopItem()) && connectedSet.containsAll(endSet)) // || connectedSet.equals(endSet)) { @@ -421,87 +585,28 @@ public class BuildLattice { String endNode = (String) iterator.next(); lattice.put(newLocName, endNode); } + next = newLocName; System.out.println(" INSERT NEW NODE=" + newLocName + " above=" + cur + " below=" + endSet); } else { assert connectedSet.size() == 1; next = connectedSet.iterator().next(); + if (lattice.isSharedLoc(next)) { + return recur_getNewLocation2(lattice, next, endSet, dist, isShared); + } } System.out.println(" next=" + next); - // if (dist == 0) { - - // if (isShared) { - - // // if the node is shared, - // // check if there already exists a shared node that has distance d + 1 on the chain - // - // connectedSet = lattice.get(next); - // - // if (connectedSet.equals(endSet)) { - // // need to insert a new shared location - // } else { - // assert connectedSet.size() != 1; - // String below = connectedSet.iterator().next(); - // if (lattice.isSharedLoc(below)) { - // return below; - // } - // } - // - // // need to insert a new shared location - // String newLocName = "ILOC" + (LocationInference.locSeed++); - // for (Iterator iterator = connectedSet.iterator(); iterator.hasNext();) { - // String outNode = (String) iterator.next(); - // lattice.put(newLocName, outNode); - // } - // connectedSet.clear(); - // lattice.put(next, newLocName); - // - // System.out.println(" INSERT NEW SHARED NODE=" + newLocName + " above=" + next - // + " below=" + lattice.get(newLocName)); - // - // lattice.addSharedLoc(newLocName); - // - // next = newLocName; - // - // } - // - // return next; - - // } else { - if (dist == 0) { return next; } else { if (!lattice.isSharedLoc(next)) { dist--; } - return recur_getNewLocation(lattice, next, endSet, dist, isShared); + return recur_getNewLocation2(lattice, next, endSet, dist, isShared); } - // } - - // /////////////////////////////////////////////// - - // if (dist == 0) { - // return cur; - // } else if (connectedSet.equals(endSet)) { - // // need to insert a new location - // String newLocName = "ILOC" + (LocationInference.locSeed++); - // connectedSet.clear(); - // lattice.put(cur, newLocName); - // for (Iterator iterator = endSet.iterator(); iterator.hasNext();) { - // String endNode = (String) iterator.next(); - // lattice.put(newLocName, endNode); - // } - // return recur_getNewLocation(lattice, newLocName, endSet, --dist, isShared); - // } else { - // assert connectedSet.size() != 1; - // String next = connectedSet.iterator().next(); - // return recur_getNewLocation(lattice, next, endSet, --dist, isShared); - // } - } public SSJavaLattice insertIntermediateNodesToStraightLine2(Descriptor desc, diff --git a/Robust/src/Analysis/SSJava/HierarchyGraph.java b/Robust/src/Analysis/SSJava/HierarchyGraph.java index 4e7c4b57..13264cf1 100644 --- a/Robust/src/Analysis/SSJava/HierarchyGraph.java +++ b/Robust/src/Analysis/SSJava/HierarchyGraph.java @@ -1397,6 +1397,48 @@ public class HierarchyGraph { return max; } + public int computeDistance(HNode startNode, Set endNodeSet) { + System.out.println("#####computeDistance startNode=" + startNode + " endNode=" + endNodeSet); + return recur_computeDistance(startNode, startNode, endNodeSet, 0, 0); + } + + private int recur_computeDistance(HNode startNode, HNode curNode, Set endNodeSet, + int sharedCount, int nonSharedCount) { + + if (!curNode.equals(startNode)) { + // do not count the start node + if (curNode.isSharedNode()) { + sharedCount++; + } else { + nonSharedCount++; + } + } + + if (endNodeSet.contains(curNode)) { + // it reaches to one of endNodeSet + if (sharedCount > nonSharedCount) { + return sharedCount; + } else { + return nonSharedCount; + } + } + + Set inNodeSet = getIncomingNodeSet(curNode); + + int curMaxDistance = 0; + for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) { + HNode inNode = (HNode) iterator.next(); + // traverse more... + System.out.println(" traverse more to" + inNode + " sC=" + sharedCount + " nC=" + + nonSharedCount); + int dist = recur_computeDistance(startNode, inNode, endNodeSet, sharedCount, nonSharedCount); + if (dist > curMaxDistance) { + curMaxDistance = dist; + } + } + return curMaxDistance; + } + public int countNonSharedNode(HNode startNode, Set endNodeSet) { System.out.println("countNonSharedNode startNode=" + startNode + " endNode=" + endNodeSet); return recur_countNonSharedNode(startNode, endNodeSet, 0); @@ -1406,6 +1448,31 @@ public class HierarchyGraph { Set inNodeSet = getIncomingNodeSet(startNode); + for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) { + HNode inNode = (HNode) iterator.next(); + if (endNodeSet.contains(inNode)) { + count++; + return count; + } else { + if (!inNode.isSharedNode()) { + count++; + } + return recur_countNonSharedNode2(inNode, endNodeSet, count); + } + } + + return 0; + } + + public int countNonSharedNode2(HNode startNode, Set endNodeSet) { + System.out.println("countNonSharedNode startNode=" + startNode + " endNode=" + endNodeSet); + return recur_countNonSharedNode2(startNode, endNodeSet, 0); + } + + private int recur_countNonSharedNode2(HNode startNode, Set endNodeSet, int count) { + + Set inNodeSet = getIncomingNodeSet(startNode); + if (inNodeSet.size() == 0) { // it is directly connected to the TOP node } @@ -1418,7 +1485,7 @@ public class HierarchyGraph { if (!inNode.isSharedNode()) { count++; } - return recur_countNonSharedNode(inNode, endNodeSet, count); + return recur_countNonSharedNode2(inNode, endNodeSet, count); } } diff --git a/Robust/src/Analysis/SSJava/LocationInference.java b/Robust/src/Analysis/SSJava/LocationInference.java index a19f725e..aedd279e 100644 --- a/Robust/src/Analysis/SSJava/LocationInference.java +++ b/Robust/src/Analysis/SSJava/LocationInference.java @@ -1030,7 +1030,7 @@ public class LocationInference { while (!methodDescList.isEmpty()) { MethodDescriptor md = methodDescList.removeLast(); - // System.out.println("\n#updateCompositeLocationAssignments=" + md); + System.out.println("\n#updateCompositeLocationAssignments=" + md); FlowGraph flowGraph = getFlowGraph(md); @@ -1039,12 +1039,12 @@ public class LocationInference { Set nodeSet = flowGraph.getNodeSet(); for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) { FlowNode node = (FlowNode) iterator.next(); - // System.out.println("-node=" + node + " node.getDescTuple=" + node.getDescTuple()); + System.out.println("-node=" + node + " node.getDescTuple=" + node.getDescTuple()); if (node.getCompositeLocation() != null) { CompositeLocation compLoc = node.getCompositeLocation(); CompositeLocation updatedCompLoc = updateCompositeLocation(compLoc); node.setCompositeLocation(updatedCompLoc); - // System.out.println("---updatedCompLoc1=" + updatedCompLoc); + System.out.println("---updatedCompLoc1=" + updatedCompLoc); } else { NTuple descTuple = node.getDescTuple(); // System.out.println("update desc=" + descTuple); @@ -1086,8 +1086,8 @@ public class LocationInference { HierarchyGraph scGraph = getSimpleHierarchyGraph(enclosingDesc); if (scGraph != null) { HNode curNode = scGraph.getCurrentHNode(nodeIdentifier); - // System.out.println("nodeID=" + nodeIdentifier + " curNode=" + curNode - // + " enclosingDesc=" + enclosingDesc); + System.out.println(" nodeID=" + nodeIdentifier + " curNode=" + curNode + + " enclosingDesc=" + enclosingDesc); if (curNode != null) { nodeIdentifier = curNode.getName(); } -- 2.34.1