import IR.Descriptor;
import IR.FieldDescriptor;
+import IR.VarDescriptor;
public class HierarchyGraph {
Descriptor desc;
String name;
- Map<Descriptor, HNode> mapDescToHNode;
- Map<HNode, Set<Descriptor>> mapHNodeToDescSet;
+
+ // graph structure
Map<HNode, Set<HNode>> mapHNodeToIncomingSet;
Map<HNode, Set<HNode>> mapHNodeToOutgoingSet;
+
+ Map<Descriptor, HNode> mapDescToHNode;
+ Map<HNode, Set<Descriptor>> mapHNodeToDescSet;
+ Map<HNode, HNode> mapHNodeToCurrentHNode; // tracking which node corresponds to the initial node
+ Map<String, HNode> mapHNodeNameToCurrentHNode; // tracking which node corresponds to the initial
+ // node
+ Map<HNode, Set<HNode>> mapMergeNodetoMergingSet;
+
+ // data structures for a combination node
Map<Set<HNode>, HNode> mapSkeletonNodeSetToCombinationNode;
Map<HNode, Set<HNode>> mapCombinationNodeToCombineNodeSet;
Map<Set<HNode>, HNode> mapCombineNodeSetToCombinationNode;
Map<Set<HNode>, Set<HNode>> mapCombineNodeSetToOutgoingNodeSet;
- Map<HNode, String> mapHNodeToLocationName;
Set<HNode> nodeSet;
- public static int seed = 0;
-
// for the lattice generation
Map<HNode, Integer> mapHNodeToUniqueIndex;
Map<HNode, Set<Integer>> mapHNodeToBasis;
mapHNodeToUniqueIndex = new HashMap<HNode, Integer>();
mapHNodeToBasis = new HashMap<HNode, Set<Integer>>();
- mapHNodeToLocationName = new HashMap<HNode, String>();
+ mapMergeNodetoMergingSet = new HashMap<HNode, Set<HNode>>();
+
+ mapHNodeToCurrentHNode = new HashMap<HNode, HNode>();
+
+ mapHNodeNameToCurrentHNode = new HashMap<String, HNode>();
}
this.desc = desc;
}
- public void addMapHNodeToLocationName(HNode node, String locName) {
- mapHNodeToLocationName.put(node, locName);
- }
-
- public String getLocationName(HNode node) {
- return mapHNodeToLocationName.get(node);
- }
-
public String getName() {
return name;
}
mapHNodeToDescSet.putAll(map);
}
+ public Map<HNode, HNode> getMapHNodeToCurrentHNode() {
+ return mapHNodeToCurrentHNode;
+ }
+
+ public Map<String, HNode> getMapHNodeNameToCurrentHNode() {
+ return mapHNodeNameToCurrentHNode;
+ }
+
+ public void setMapHNodeToCurrentHNode(Map<HNode, HNode> mapHNodeToCurrentHNode) {
+ this.mapHNodeToCurrentHNode = mapHNodeToCurrentHNode;
+ }
+
+ public void setMapHNodeNameToCurrentHNode(Map<String, HNode> mapHNodeNameToCurrentHNode) {
+ this.mapHNodeNameToCurrentHNode = mapHNodeNameToCurrentHNode;
+ }
+
public Map<Descriptor, HNode> getMapDescToHNode() {
return mapDescToHNode;
}
if (possibleCycleSet.size() == 1) {
if (dstHNode.isSharedNode()) {
// it has already been assigned shared node.
- return;
+ } else {
+ dstHNode.setSharedNode(true);
}
+ return;
}
HNode newMergeNode = mergeNodes(possibleCycleSet, false);
newMergeNode.setSharedNode(true);
System.out.println("### INTRODUCE A NEW MERGE NODE: " + newMergeNode);
- System.out.println("### CYCLIC VALUE FLOW: " + srcHNode + " -> " + dstHNode);
+ System.out.println("### CYCLIC VALUE FLOW: " + srcHNode + " -> " + dstHNode + "\n");
} else {
getIncomingNodeSet(dstHNode).add(srcHNode);
getOutgoingNodeSet(srcHNode).add(dstHNode);
- System.out.println("add an edge " + srcHNode + " -> " + dstHNode);
+ // System.out.println("add an edge " + srcHNode + " -> " + dstHNode);
}
}
return mapDescToHNode.get(d);
}
+ public HNode getHNode(String name) {
+ for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
+ HNode node = (HNode) iterator.next();
+ if (node.getName().equals(name)) {
+ return node;
+ }
+ }
+ return null;
+ }
+
private void mappingDescriptorToHNode(Descriptor desc, HNode node) {
mapDescToHNode.put(desc, node);
if (!mapHNodeToDescSet.containsKey(node)) {
skeletonGraph.setMapDescToHNode(getMapDescToHNode());
skeletonGraph.setMapHNodeToDescSet(getMapHNodeToDescSet());
+ skeletonGraph.setMapHNodetoMergeSet(getMapHNodetoMergeSet());
+ skeletonGraph.setMapHNodeToCurrentHNode(getMapHNodeToCurrentHNode());
return skeletonGraph;
} while (isUpdated);
}
- private Set<HNode> getIncomingNodeSet(HNode node) {
+ public Set<HNode> getIncomingNodeSet(HNode node) {
if (!mapHNodeToIncomingSet.containsKey(node)) {
mapHNodeToIncomingSet.put(node, new HashSet<HNode>());
}
continue;
}
+ if (!isEligibleForMerging(node1, node2)) {
+ continue;
+ }
+
if (!node1.equals(node2)) {
Set<HNode> incomingNodeSet2 = getIncomingNodeSet(node2);
return false;
}
+ private boolean isEligibleForMerging(HNode node1, HNode node2) {
+
+ System.out.println("********isEligibleForMerging=" + node1 + " " + node2);
+
+ if (node1.isSharedNode() || node2.isSharedNode()) {
+
+ // if either of nodes is a shared node,
+ // all descriptors of node1 & node2 should have a primitive type
+
+ Set<Descriptor> descSet = new HashSet<Descriptor>();
+ descSet.addAll(getDescSetOfNode(node1));
+ descSet.addAll(getDescSetOfNode(node2));
+
+ for (Iterator iterator = descSet.iterator(); iterator.hasNext();) {
+ Descriptor desc = (Descriptor) iterator.next();
+ if (!LocationInference.isPrimitive(desc)) {
+ return false;
+ }
+ }
+ System.out.println("******** true");
+ return true;
+ }
+ return false;
+ }
+
private void addEdgeWithNoCycleCheck(HNode srcHNode, HNode dstHNode) {
getIncomingNodeSet(dstHNode).add(srcHNode);
getOutgoingNodeSet(srcHNode).add(dstHNode);
}
String nodeName;
+ boolean isMergeNode = false;
if (onlyCombinationNodes) {
- nodeName = "Comb" + (seed++);
+ nodeName = "Comb" + (LocationInference.locSeed++);
} else {
- nodeName = "Node" + (seed++);
+ nodeName = "Node" + (LocationInference.locSeed++);
+ isMergeNode = true;
}
HNode newMergeNode = new HNode(nodeName);
+ newMergeNode.setMergeNode(isMergeNode);
nodeSet.add(newMergeNode);
nodeSet.removeAll(set);
}
}
System.out.println("--Set merging node=" + newMergeNode + " as a skeleton=" + set
- + " hasSkeleton=" + hasSkeleton);
+ + " hasSkeleton=" + hasSkeleton + " CUR DESC=" + desc);
newMergeNode.setSkeleton(hasSkeleton);
for (Iterator iterator = set.iterator(); iterator.hasNext();) {
}
}
+ Set<HNode> mergedSkeletonNode = new HashSet<HNode>();
+ for (Iterator<HNode> iter = set.iterator(); iter.hasNext();) {
+ HNode merged = iter.next();
+ if (merged.isSkeleton()) {
+ mergedSkeletonNode.add(merged);
+ }
+ }
+
+ // mapMergeNodetoMergingSet.put(newMergeNode, mergedSkeletonNode);
+ // for (Iterator iterator = set.iterator(); iterator.hasNext();) {
+ mapMergeNodetoMergingSet.put(newMergeNode, set);
+ for (Iterator iterator = set.iterator(); iterator.hasNext();) {
+ HNode mergedNode = (HNode) iterator.next();
+ addMapHNodeToCurrentHNode(mergedNode, newMergeNode);
+ }
+ System.out.println("###mergedSkeletonNode=" + mergedSkeletonNode);
System.out.println("###MERGING NODE=" + set + " new node=" + newMergeNode);
+
+ for (Iterator iterator = set.iterator(); iterator.hasNext();) {
+ HNode hNode = (HNode) iterator.next();
+ System.out.println("old=" + hNode + "----->newNode=" + getCurrentHNode(hNode));
+ }
+
return newMergeNode;
}
- private Set<Descriptor> getDescSetOfNode(HNode node) {
+ private void addMapHNodeToCurrentHNode(HNode curNode, HNode newNode) {
+ if (curNode.isMergeNode()) {
+ Set<HNode> mergingSet = getMergingSet(curNode);
+ mergingSet.add(curNode);
+ System.out.println("addMapHNodeToCurrentHNode curNode=" + curNode + " meringSet="
+ + mergingSet);
+ for (Iterator iterator = mergingSet.iterator(); iterator.hasNext();) {
+ HNode mergingNode = (HNode) iterator.next();
+ mapHNodeToCurrentHNode.put(mergingNode, newNode);
+ mapHNodeNameToCurrentHNode.put(mergingNode.getName(), newNode);
+ }
+ } else {
+ mapHNodeToCurrentHNode.put(curNode, newNode);
+ mapHNodeNameToCurrentHNode.put(curNode.getName(), newNode);
+ }
+ }
+
+ public HNode getCurrentHNode(HNode node) {
+ if (!mapHNodeToCurrentHNode.containsKey(node)) {
+ mapHNodeToCurrentHNode.put(node, node);
+ }
+ return mapHNodeToCurrentHNode.get(node);
+ }
+
+ public HNode getCurrentHNode(String nodeName) {
+ return mapHNodeNameToCurrentHNode.get(nodeName);
+ }
+
+ private Set<HNode> getMergingSet(HNode mergeNode) {
+ Set<HNode> mergingSet = new HashSet<HNode>();
+ Set<HNode> mergedNode = mapMergeNodetoMergingSet.get(mergeNode);
+ for (Iterator iterator = mergedNode.iterator(); iterator.hasNext();) {
+ HNode node = (HNode) iterator.next();
+ if (node.isMergeNode()) {
+ mergingSet.add(node);
+ mergingSet.addAll(getMergingSet(node));
+ } else {
+ mergingSet.add(node);
+ }
+ }
+ return mergingSet;
+ }
+
+ public Set<Descriptor> getDescSetOfNode(HNode node) {
if (!mapHNodeToDescSet.containsKey(node)) {
mapHNodeToDescSet.put(node, new HashSet<Descriptor>());
}
public HNode getCombinationNode(Set<HNode> combineSet) {
if (!mapCombineNodeSetToCombinationNode.containsKey(combineSet)) {
- String name = "COMB" + (seed++);
+ String name = "COMB" + (LocationInference.locSeed++);
HNode node = new HNode(name);
node.setCombinationNode(true);
nodeSet.add(node);
return mapCombineNodeSetToCombinationNode.get(combineSet);
}
+ public Map<Set<HNode>, HNode> getMapCombineNodeSetToCombinationNode() {
+ return mapCombineNodeSetToCombinationNode;
+ }
+
public Set<Set<HNode>> getCombineNodeSet() {
return mapCombineNodeSetToOutgoingNodeSet.keySet();
}
- public void insertCombinationNodesToGraph(HierarchyGraph hierarchyGraph) {
+ public void insertCombinationNodesToGraph(HierarchyGraph simpleHierarchyGraph) {
// add a new combination node where parameter/field flows are actually combined.
- hierarchyGraph.identifyCombinationNodes();
+ simpleHierarchyGraph.identifyCombinationNodes();
- Set<Set<HNode>> keySet = hierarchyGraph.getCombineNodeSet();
+ Set<Set<HNode>> keySet = simpleHierarchyGraph.getCombineNodeSet();
for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
Set<HNode> combineSet = (Set<HNode>) iterator.next();
System.out.println("--combineSet=" + combineSet);
}
// add an edge from the combination node to outgoing nodes
- Set<HNode> outSet = hierarchyGraph.getOutgoingNodeSetByCombineSet(combineSet);
+ Set<HNode> outSet = simpleHierarchyGraph.getOutgoingNodeSetByCombineSet(combineSet);
for (Iterator iterator2 = outSet.iterator(); iterator2.hasNext();) {
HNode curNode = (HNode) iterator2.next();
if (curNode.isCombinationNode()) {
- Set<HNode> combineNode = hierarchyGraph.getCombineSetByCombinationNode(curNode);
+ Set<HNode> combineNode = simpleHierarchyGraph.getCombineSetByCombinationNode(curNode);
HNode outNode = getCombinationNode(combineNode);
addEdgeWithNoCycleCheck(combinationNode, outNode);
} else if (curNode.isSkeleton()) {
- addEdgeWithNoCycleCheck(combinationNode, curNode);
+ // HNode dstNode2 = getHNode(curNode.getDescriptor());
+ HNode dstNode = getCurrentHNode(curNode);
+ // System.out.println("-----curNode=" + curNode + "------->" + dstNode + " dstNode2="
+ // + dstNode2);
+ addEdgeWithNoCycleCheck(combinationNode, dstNode);
}
}
private void addCombinationNode(HNode curNode, Set<HNode> reachToSet, Set<HNode> reachableSet) {
if (!mapSkeletonNodeSetToCombinationNode.containsKey(reachToSet)) {
// need to create a new combination node
- String nodeName = "Comb" + (seed++);
+ String nodeName = "Comb" + (LocationInference.locSeed++);
HNode newCombinationNode = new HNode(nodeName);
newCombinationNode.setCombinationNode(true);
clone.setMapHNodeToOutgoingSet(getMapHNodeToOutgoingSet());
clone.setMapDescToHNode(getMapDescToHNode());
clone.setMapHNodeToDescSet(getMapHNodeToDescSet());
+ clone.setMapHNodetoMergeSet(getMapHNodetoMergeSet());
+ clone.setMapHNodeToCurrentHNode(getMapHNodeToCurrentHNode());
+ clone.setMapHNodeNameToCurrentHNode(getMapHNodeNameToCurrentHNode());
return clone;
}
+ public Map<HNode, Set<HNode>> getMapHNodetoMergeSet() {
+ return mapMergeNodetoMergingSet;
+ }
+
+ public void setMapHNodetoMergeSet(Map<HNode, Set<HNode>> mapHNodetoMergeSet) {
+ this.mapMergeNodetoMergingSet = mapHNodetoMergeSet;
+ }
+
public Set<HNode> getOutgoingNodeSetByCombineSet(Set<HNode> combineSet) {
if (!mapCombineNodeSetToOutgoingNodeSet.containsKey(combineSet)) {
HNode node = (HNode) iterator.next();
if (!node.isSkeleton()) {
Set<HNode> reachToSet = getSkeleteNodeSetReachTo(node);
- // if (reachToSet.size() > 1) {
- if (countSkeletonNodes(reachToSet) > 1) {
+ if (reachToSet.size() > 1) {
+ // if (countSkeletonNodes(reachToSet) > 1) {
System.out.println("-node=" + node + " reachToSet=" + reachToSet);
System.out.println("-set combinationnode=" + node);
node.setCombinationNode(true);
public void assignUniqueIndexToNode() {
int idx = 1;
+ System.out.println("nodeSet=" + nodeSet);
for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
HNode node = (HNode) iterator.next();
mapHNodeToUniqueIndex.put(node, idx);
}
}
- public BasisSet computeBasisSet() {
+ public BasisSet computeBasisSet(Set<HNode> notGenerateSet) {
// assign a unique index to a node
assignUniqueIndexToNode();
for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
HNode node = (HNode) iterator.next();
+ if (notGenerateSet.contains(node)) {
+ System.out.println("%%%SKIP =" + node);
+ continue;
+ }
Set<Integer> basis = new HashSet<Integer>();
basis.addAll(BASISTOPELEMENT);
Set<HNode> reachableNodeSet = getReachableNodeSetFrom(node);
System.out.println("node=" + node + " reachableNodeSet=" + reachableNodeSet);
-
+ System.out.println("mapHNodeToUniqueIndex.get(node)=" + mapHNodeToUniqueIndex.get(node));
// if a node is reachable from the current node
// need to remove the index of the reachable node from the basis
basis.remove(getHNodeIndex(node));
for (Iterator iterator2 = reachableNodeSet.iterator(); iterator2.hasNext();) {
HNode reachableNode = (HNode) iterator2.next();
+ System.out.println("reachableNode=" + reachableNode);
+ System.out.println("getHNodeIndex(reachableNode))="
+ + mapHNodeToUniqueIndex.get(reachableNode));
int idx = getHNodeIndex(reachableNode);
basis.remove(idx);
}
}
}
+ public boolean contains(HNode node) {
+ return nodeSet.contains(node);
+ }
+
+ public boolean isDirectlyConnectedTo(HNode src, HNode dst) {
+ return getOutgoingNodeSet(src).contains(dst);
+ }
+
+ private String convertMergeSetToString(Set<HNode> mergeSet) {
+ String str = "";
+ for (Iterator iterator = mergeSet.iterator(); iterator.hasNext();) {
+ HNode merged = (HNode) iterator.next();
+ if (merged.isMergeNode()) {
+ str += " " + convertMergeSetToString(mapMergeNodetoMergingSet.get(merged));
+ } else {
+ str += " " + merged.getName();
+ }
+ }
+ return str;
+ }
+
private void drawNode(BufferedWriter bw, HNode node) throws IOException {
- String nodeName = node.toString();
- nodeName = nodeName.substring(1, nodeName.length() - 1);
+ String nodeName;
+ if (node.isMergeNode()) {
+ nodeName = node.getNamePropertyString();
+ Set<HNode> mergeSet = mapMergeNodetoMergingSet.get(node);
+ nodeName += ":" + convertMergeSetToString(mergeSet);
+ } else {
+ nodeName = node.getNamePropertyString();
+ }
bw.write(node.getName() + " [label=\"" + nodeName + "\"]" + ";\n");
}
+ public int countHopFromTopLocation(HNode node) {
+
+ Set<HNode> inNodeSet = getIncomingNodeSet(node);
+ int count = 0;
+ if (inNodeSet.size() > 0) {
+ count = recurCountHopFromTopLocation(inNodeSet, 1);
+ }
+
+ return count;
+ }
+
+ private int recurCountHopFromTopLocation(Set<HNode> nodeSet, int curCount) {
+
+ int max = curCount;
+ for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
+ HNode node = (HNode) iterator.next();
+ Set<HNode> inNodeSet = getIncomingNodeSet(node);
+ if (inNodeSet.size() > 0) {
+ int recurCount = recurCountHopFromTopLocation(inNodeSet, curCount + 1);
+ if (max < recurCount) {
+ max = recurCount;
+ }
+ }
+ }
+ return max;
+ }
+
}
projects / IRC.git / blobdiff