changes.
authoryeom <yeom>
Fri, 22 Feb 2013 06:22:32 +0000 (06:22 +0000)
committeryeom <yeom>
Fri, 22 Feb 2013 06:22:32 +0000 (06:22 +0000)
Robust/src/Analysis/SSJava/BuildLattice.java
Robust/src/Analysis/SSJava/HierarchyGraph.java
Robust/src/Analysis/SSJava/LocationInference.java

index 2d65122..57766ef 100644 (file)
@@ -22,12 +22,15 @@ public class BuildLattice {
 
   private Map<Pair<HNode, HNode>, Integer> mapItemToHighestIndex;
 
+  private Map<SSJavaLattice<String>, Set<String>> mapLatticeToLocalLocSet;
+
   public BuildLattice(LocationInference infer) {
     this.infer = infer;
     this.mapSharedNodeToTripleItem = new HashMap<HNode, TripleItem>();
     this.mapHNodeToHighestIndex = new HashMap<HNode, Integer>();
     this.mapItemToHighestIndex = new HashMap<Pair<HNode, HNode>, Integer>();
     this.mapDescToIntermediateLocMap = new HashMap<Descriptor, Map<TripleItem, String>>();
+    this.mapLatticeToLocalLocSet = new HashMap<SSJavaLattice<String>, Set<String>>();
   }
 
   public SSJavaLattice<String> 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<HNode> aboveSet = new HashSet<HNode>();
@@ -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<HNode> 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<String> outgoingLocNameSet = new HashSet<String>();
         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<String> lattice, String localLoc) {
+    if (!mapLatticeToLocalLocSet.containsKey(lattice)) {
+      mapLatticeToLocalLocSet.put(lattice, new HashSet<String>());
+    }
+    mapLatticeToLocalLocSet.get(lattice).add(localLoc);
+  }
+
+  private boolean isLocalLocation(SSJavaLattice<String> lattice, String localLoc) {
+    if (mapLatticeToLocalLocSet.containsKey(lattice)) {
+      return mapLatticeToLocalLocSet.get(lattice).contains(localLoc);
+    }
+    return false;
+  }
+
   public String getNewLocation(SSJavaLattice<String> lattice, String start, Set<String> 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<String> lattice, String start, String cur,
+      Set<String> 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<String> lowerSet = new HashSet<String>();
+          lowerSet.addAll(lattice.get(cur));
+          lattice.insertNewLocationBetween(cur, lowerSet, newLocName);
+          addLocalLocation(lattice, newLocName);
+
+          // assign the new local location to cur
+          cur = newLocName;
+        }
+
+        Set<String> connectedSet = lattice.get(cur);
+        if (connectedSet == null) {
+          connectedSet = new HashSet<String>();
+        }
+        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<String> lowerSet = new HashSet<String>();
+          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<String> connectedSet = lattice.get(cur);
+        // if (connectedSet == null) {
+        // connectedSet = new HashSet<String>();
+        // }
+        // 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<String> lowerSet = new HashSet<String>();
+        // lowerSet.addAll(connectedSet);
+        // lattice.insertNewLocationBetween(cur, lowerSet, newLocName);
+        // addLocalLocation(lattice, newLocName);
+        // return newLocName;
+        // } else {
+        // return cur;
+        // }
+      }
+    }
+
+    Set<String> connectedSet = lattice.get(cur);
+    if (connectedSet == null) {
+      connectedSet = new HashSet<String>();
+    }
+
+    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<String> lowerSet = new HashSet<String>();
+      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<String> lattice, String start, Set<String> 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<String> lattice, String cur,
+  private String recur_getNewLocation2(SSJavaLattice<String> lattice, String cur,
       Set<String> endSet, int dist, boolean isShared) {
-    System.out.println("H");
     Set<String> connectedSet = lattice.get(cur);
     if (connectedSet == null) {
       connectedSet = new HashSet<String>();
     }
 
-    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<String> insertIntermediateNodesToStraightLine2(Descriptor desc,
index 4e7c4b5..13264cf 100644 (file)
@@ -1397,6 +1397,48 @@ public class HierarchyGraph {
     return max;
   }
 
+  public int computeDistance(HNode startNode, Set<HNode> 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<HNode> 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<HNode> 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<HNode> endNodeSet) {
     System.out.println("countNonSharedNode startNode=" + startNode + " endNode=" + endNodeSet);
     return recur_countNonSharedNode(startNode, endNodeSet, 0);
@@ -1406,6 +1448,31 @@ public class HierarchyGraph {
 
     Set<HNode> 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<HNode> endNodeSet) {
+    System.out.println("countNonSharedNode startNode=" + startNode + " endNode=" + endNodeSet);
+    return recur_countNonSharedNode2(startNode, endNodeSet, 0);
+  }
+
+  private int recur_countNonSharedNode2(HNode startNode, Set<HNode> endNodeSet, int count) {
+
+    Set<HNode> 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);
       }
     }
 
index a19f725..aedd279 100644 (file)
@@ -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<FlowNode> 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<Descriptor> 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();
           }