From: yeom Date: Sun, 24 Feb 2013 00:41:16 +0000 (+0000) Subject: changes. X-Git-Url: http://plrg.eecs.uci.edu/git/?p=IRC.git;a=commitdiff_plain;h=a7f1174555e6acecd448b544a65898efdc02129a changes. --- diff --git a/Robust/src/Analysis/SSJava/BuildLattice.java b/Robust/src/Analysis/SSJava/BuildLattice.java index 57766ef9..c26b70a8 100644 --- a/Robust/src/Analysis/SSJava/BuildLattice.java +++ b/Robust/src/Analysis/SSJava/BuildLattice.java @@ -269,6 +269,7 @@ public class BuildLattice { int dist; HNode SCNode; + Set combineSkeletonNodeSet = null; if (hNode.isDirectCombinationNode()) { // this node itself is the lowest node m. it is the first node of the chain Set combineSet = hierarchyGraph.getCombineSetByCombinationNode(hNode); @@ -283,8 +284,7 @@ public class BuildLattice { Set aboveSet = new HashSet(); if (hNode.isCombinationNode()) { // the current node is a combination node - Set combineSkeletonNodeSet = - hierarchyGraph.getCombineSetByCombinationNode(hNode); + combineSkeletonNodeSet = hierarchyGraph.getCombineSetByCombinationNode(hNode); System.out.println(" combineSkeletonNodeSet=" + combineSkeletonNodeSet + " combinationNode=" + scGraph.getCombinationNode(combineSkeletonNodeSet)); @@ -310,13 +310,14 @@ public class BuildLattice { } // update above set w.r.t the hierarchy graph with SC nodes - // because the skeleton nodes in the origianl hierarchy graph may merged to a new node + // because the skeleton nodes in the original hierarchy graph may be merged to a new node Set endSet = new HashSet(); for (Iterator iterator2 = aboveSet.iterator(); iterator2.hasNext();) { HNode aboveNode = (HNode) iterator2.next(); - endSet.add(scGraph.getCurrentHNode(aboveNode)); + endSet.add(hierarchyGraph.getCurrentHNode(aboveNode)); } - dist = hierarchyGraph.computeDistance(hNode, endSet); + + dist = hierarchyGraph.computeDistance(hNode, endSet, combineSkeletonNodeSet); System.out.println("##### " + hNode + "::dist=" + dist); // numNonSharedNodes = hierarchyGraph.countNonSharedNode(hNode, endSet); @@ -379,16 +380,6 @@ public class BuildLattice { int dist, boolean isShared) { 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); } @@ -401,17 +392,18 @@ public class BuildLattice { 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"); + // if not, need to insert a new SHARED local location at this point + System.out.println("if not, need to insert a new SHARED local location at this point"); String newLocName = "ILOC" + (LocationInference.locSeed++); Set lowerSet = new HashSet(); lowerSet.addAll(lattice.get(cur)); lattice.insertNewLocationBetween(cur, lowerSet, newLocName); + lattice.addSharedLoc(newLocName); addLocalLocation(lattice, newLocName); - - // assign the new local location to cur - cur = newLocName; + return newLocName; } + // if there exists a non-shared node at distance d + // then try to add a new SHARED loc at distance d+1 Set connectedSet = lattice.get(cur); if (connectedSet == null) { @@ -449,29 +441,20 @@ public class BuildLattice { return cur; } else { + // if the node is not a shared one, + // check if the cur node is a shared node + if (lattice.isSharedLoc(cur)) { + // here, we need to add a new local NONSHARED node above cur - 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; - // } + String newLocName = "ILOC" + (LocationInference.locSeed++); + lattice.insertNewLocationAtOneLevelHigher(cur, newLocName); + addLocalLocation(lattice, newLocName); + System.out.println(" INSERT NEW LOC=" + newLocName + " ABOVE=" + cur); + return newLocName; + } else { + // if cur is not shared, return it! + return cur; + } } } @@ -503,300 +486,6 @@ public class BuildLattice { } - 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) { - 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_getNewLocation2(lattice, start, endSet, dist, isShared); - } - - private String recur_getNewLocation2(SSJavaLattice lattice, String cur, - Set endSet, int dist, boolean isShared) { - Set connectedSet = lattice.get(cur); - if (connectedSet == null) { - connectedSet = new HashSet(); - } - - System.out.println(" recur_getNewLocation::cur=" + cur + " dist=" + dist - + " connectedSet=" + connectedSet + " endSet=" + endSet); - - if (dist == 0 && isShared) { - // if the node is shared, - // check if there already exists a shared node that has distance d + 1 on the chain - if ((cur.equals(lattice.getTopItem()) && connectedSet.containsAll(endSet)) - || connectedSet.equals(endSet)) { - // need to insert a new shared location - // it is done after this if statement - } else { - assert connectedSet.size() == 1; - String below = connectedSet.iterator().next(); - if (lattice.isSharedLoc(below)) { - return below; - } - } - - // need to insert a new shared location - Set newChildSet = new HashSet(); - newChildSet.addAll(connectedSet); - - String newLocName = "ILOC" + (LocationInference.locSeed++); - for (Iterator iterator = newChildSet.iterator(); iterator.hasNext();) { - String outNode = (String) iterator.next(); - lattice.put(newLocName, outNode); - } - lattice.get(cur).clear(); - lattice.put(cur, newLocName); - - System.out.println(" INSERT NEW SHARED NODE=" + newLocName + " above=" + cur - + " below=" + lattice.get(newLocName)); - - lattice.addSharedLoc(newLocName); - - return newLocName; - - } - - String next; - - if (cur.equals(lattice.getTopItem()) || connectedSet.equals(endSet) /* || endSet.isEmpty() */) { - - // if ( (cur.equals(lattice.getTopItem()) && connectedSet.containsAll(endSet)) - // || connectedSet.equals(endSet)) { - - // need to insert a new location - String newLocName = "ILOC" + (LocationInference.locSeed++); - connectedSet.clear(); - lattice.put(cur, newLocName); - - System.out.println("#INSERT NEW RELATION cur=" + cur + " newLocName=" + newLocName + "::" - + lattice.get(cur)); - - for (Iterator iterator = endSet.iterator(); iterator.hasNext();) { - 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) { - return next; - } else { - if (!lattice.isSharedLoc(next)) { - dist--; - } - return recur_getNewLocation2(lattice, next, endSet, dist, isShared); - } - - } - - public SSJavaLattice insertIntermediateNodesToStraightLine2(Descriptor desc, - SSJavaLattice skeletonLattice) { - // copy nodes/edges from the parent method/class if possible - SSJavaLattice lattice = skeletonLattice.clone(); - - Descriptor parentDesc = getParent(desc); - if (parentDesc != null) { - SSJavaLattice parentLattice = infer.getLattice(parentDesc); - - Map> parentMap = parentLattice.getTable(); - Set parentKeySet = parentMap.keySet(); - for (Iterator iterator = parentKeySet.iterator(); iterator.hasNext();) { - String parentKey = (String) iterator.next(); - Set parentValueSet = parentMap.get(parentKey); - for (Iterator iterator2 = parentValueSet.iterator(); iterator2.hasNext();) { - String value = (String) iterator2.next(); - lattice.put(parentKey, value); - } - } - - Set parentSharedLocSet = parentLattice.getSharedLocSet(); - for (Iterator iterator = parentSharedLocSet.iterator(); iterator.hasNext();) { - String parentSharedLoc = (String) iterator.next(); - lattice.addSharedLoc(parentSharedLoc); - } - } - - // //// - - // perform DFS that starts from each skeleton/combination node and ends by another - // skeleton/combination node - - mapSharedNodeToTripleItem.clear(); - - HierarchyGraph simpleGraph = infer.getSimpleHierarchyGraph(desc); - HierarchyGraph scGraph = infer.getSkeletonCombinationHierarchyGraph(desc); - LocationSummary locSummary = infer.getLocationSummary(desc); - - Set visited = new HashSet(); - - Set nodeSet = simpleGraph.getNodeSet(); - - Map mapIntermediateLoc = getIntermediateLocMap(desc); - // Map mapIntermediateLoc = new HashMap(); - - // System.out.println("*insert=" + desc); - // System.out.println("***nodeSet=" + nodeSet); - for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) { - HNode node = (HNode) iterator.next(); - System.out.println("node=" + node); - - if (node.isSkeleton() && (!visited.contains(node))) { - visited.add(node); - - Set outSet = simpleGraph.getOutgoingNodeSet(node); - for (Iterator iterator2 = outSet.iterator(); iterator2.hasNext();) { - HNode outNode = (HNode) iterator2.next(); - - if (!outNode.isSkeleton()) { - if (outNode.isCombinationNode()) { - if (visited.containsAll(simpleGraph.getIncomingNodeSet(outNode))) { - // if (needToExpandCombinationNode(desc, outNode)) { - expandCombinationNode(desc, lattice, visited, mapIntermediateLoc, locSummary, - outNode); - // } - } - } else { - // we have a node that is neither combination or skeleton node - // System.out.println("%%%skeleton node=" + node + " outNode=" + outNode); - HNode startNode = scGraph.getCurrentHNode(node); - - // if (node.getDescriptor() != null) { - // // node is a skeleton node and it might be merged into another node in the SC - // graph. - // startNode = scGraph.getHNode(node.getDescriptor()); - // } else { - // // this node has already been merged before the SC graph. - // startNode = node; - // } - - // TODO - // Set endNodeSetFromSimpleGraph = - // simpleGraph.getDirectlyReachableSkeletonCombinationNodeFrom(outNode, null); - // Set endCombNodeSet = new HashSet(); - // for (Iterator iterator3 = endNodeSetFromSimpleGraph.iterator(); - // iterator3.hasNext();) { - // HNode endNode = (HNode) iterator3.next(); - // endCombNodeSet.add(getCombinationNodeInSCGraph(desc, endNode)); - // } - - Set endCombNodeSet = scGraph.getOutgoingNodeSet(startNode); - - // System.out.println("endCombNodeSet=" + endCombNodeSet); - visited.add(outNode); - if (endCombNodeSet.size() > 0) { - // follows the straight line up to another skeleton/combination node - endCombNodeSet = removeTransitivelyReachToNode(desc, startNode, endCombNodeSet); - } else if (endCombNodeSet.size() == 0) { - // the outNode is (directly/transitively) connected to the bottom node - // therefore, we just add a dummy bottom HNode to the endCombNodeSet. - endCombNodeSet.add(LocationInference.BOTTOMHNODE); - } - - recurDFSNormalNode(desc, lattice, startNode, endCombNodeSet, visited, - mapIntermediateLoc, 1, locSummary, outNode); - } - - } - - } - } else if (!node.isSkeleton() && !node.isCombinationNode() && !node.isMergeNode() - && !visited.contains(node)) { - - System.out.println("n=" + node); - - // an intermediate node 'node' may be located between "TOP" location and a skeleton node - if (simpleGraph.getIncomingNodeSet(node).size() == 0) { - - // this node will be directly connected to the TOP location - // start adding the following nodes from this node - - Set endNodeSetFromSimpleGraph = - simpleGraph.getDirectlyReachableSkeletonCombinationNodeFrom(node, null); - - Set endCombNodeSet = new HashSet(); - for (Iterator iterator3 = endNodeSetFromSimpleGraph.iterator(); iterator3.hasNext();) { - HNode endNode = (HNode) iterator3.next(); - endCombNodeSet.add(getCombinationNodeInSCGraph(desc, endNode)); - } - - System.out.println("endCombNodeSet=" + endCombNodeSet); - HNode startNode = LocationInference.TOPHNODE; - visited.add(startNode); - if (endCombNodeSet.size() > 0) { - // follows the straight line up to another skeleton/combination node - // endCombNodeSet = removeTransitivelyReachToNode(desc, node, endCombNodeSet); - recurDFSNormalNode(desc, lattice, startNode, endCombNodeSet, visited, - mapIntermediateLoc, 1, locSummary, node); - } - - } - - } - } - - // add shared locations - Set sharedNodeSet = mapSharedNodeToTripleItem.keySet(); - for (Iterator iterator = sharedNodeSet.iterator(); iterator.hasNext();) { - HNode sharedNode = (HNode) iterator.next(); - TripleItem item = mapSharedNodeToTripleItem.get(sharedNode); - String nonSharedLocName = mapIntermediateLoc.get(item); - - System.out.println("sharedNode=" + sharedNode + " locName=" + nonSharedLocName); - - String newLocName; - if (locSummary.getHNodeNameSetByLatticeLoationName(nonSharedLocName) != null - && !lattice.isSharedLoc(nonSharedLocName)) { - // need to generate a new shared location in the lattice, which is one level lower than the - // 'locName' location - newLocName = "ILOC" + (LocationInference.locSeed++); - - // Set aboveElementSet = getAboveElementSet(lattice, locName); - Set belowElementSet = new HashSet(); - belowElementSet.addAll(lattice.get(nonSharedLocName)); - - System.out.println("nonSharedLocName=" + nonSharedLocName + " belowElementSet=" - + belowElementSet + " newLocName=" + newLocName); - - lattice.insertNewLocationBetween(nonSharedLocName, belowElementSet, newLocName); - } else { - newLocName = nonSharedLocName; - } - - lattice.addSharedLoc(newLocName); - HierarchyGraph graph = infer.getSimpleHierarchyGraph(desc); - Set descSet = graph.getDescSetOfNode(sharedNode); - for (Iterator iterator2 = descSet.iterator(); iterator2.hasNext();) { - Descriptor d = (Descriptor) iterator2.next(); - locSummary.addMapHNodeNameToLocationName(d.getSymbol(), newLocName); - } - locSummary.addMapHNodeNameToLocationName(sharedNode.getName(), newLocName); - - } - - return lattice; - - } - private Set getAboveElementSet(SSJavaLattice lattice, String loc) { Set aboveSet = new HashSet(); diff --git a/Robust/src/Analysis/SSJava/GlobalFlowGraph.java b/Robust/src/Analysis/SSJava/GlobalFlowGraph.java index 5a2595a4..bd0faa10 100644 --- a/Robust/src/Analysis/SSJava/GlobalFlowGraph.java +++ b/Robust/src/Analysis/SSJava/GlobalFlowGraph.java @@ -349,4 +349,20 @@ public class GlobalFlowGraph { } } + public Set debug_getIncomingNodeSetFromPrefix(GlobalFlowNode node, + NTuple curPrefix) { + + Set result = new HashSet(); + + Set allIncomingNodeSet = getIncomingNodeSet(node); + for (Iterator iterator = allIncomingNodeSet.iterator(); iterator.hasNext();) { + GlobalFlowNode incomingNode = (GlobalFlowNode) iterator.next(); + if (incomingNode.getLocTuple().startsWith(curPrefix)) { + result.add(incomingNode); + } + } + + return result; + } + } diff --git a/Robust/src/Analysis/SSJava/HierarchyGraph.java b/Robust/src/Analysis/SSJava/HierarchyGraph.java index 13264cf1..c14864e7 100644 --- a/Robust/src/Analysis/SSJava/HierarchyGraph.java +++ b/Robust/src/Analysis/SSJava/HierarchyGraph.java @@ -1397,13 +1397,55 @@ public class HierarchyGraph { return max; } - public int computeDistance(HNode startNode, Set endNodeSet) { + public int computeDistance(HNode startNode, Set endNodeSet, Set combineSet) { System.out.println("#####computeDistance startNode=" + startNode + " endNode=" + endNodeSet); - return recur_computeDistance(startNode, startNode, endNodeSet, 0, 0); + return recur_computeDistance(startNode, startNode, endNodeSet, 0, combineSet); } private int recur_computeDistance(HNode startNode, HNode curNode, Set endNodeSet, - int sharedCount, int nonSharedCount) { + int count, Set combineSet) { + + if (!curNode.equals(startNode)) { + // do not count the start node + count++; + } + + if (endNodeSet.contains(curNode)) { + // it reaches to one of endNodeSet + return count; + } + + Set inNodeSet = getIncomingNodeSet(curNode); + + int curMaxDistance = 0; + for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) { + HNode inNode = (HNode) iterator.next(); + // traverse more... + + if (inNode.isCombinationNode() && combineSet != null) { + // check if inNode have the same combination set of the starting node + Set inNodeCombineSet = getCombineSetByCombinationNode(inNode); + if (!inNodeCombineSet.equals(combineSet)) { + continue; + } + } + + System.out.println(" traverse more to" + inNode + " before-count=" + count); + int dist = recur_computeDistance(startNode, inNode, endNodeSet, count, combineSet); + if (dist > curMaxDistance) { + curMaxDistance = dist; + } + } + return curMaxDistance; + } + + public int computeDistance2(HNode startNode, Set endNodeSet, Set combineSet) { + System.out.println("#####computeDistance startNode=" + startNode + " endNode=" + endNodeSet); + return recur_computeDistance2(startNode, startNode, endNodeSet, 0, 0, combineSet); + } + + private int recur_computeDistance2(HNode startNode, HNode curNode, Set endNodeSet, + int sharedCount, int nonSharedCount, Set combineSet) { if (!curNode.equals(startNode)) { // do not count the start node @@ -1429,9 +1471,20 @@ public class HierarchyGraph { for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) { HNode inNode = (HNode) iterator.next(); // traverse more... + + if (inNode.isCombinationNode() && combineSet != null) { + // check if inNode have the same combination set of the starting node + Set inNodeCombineSet = getCombineSetByCombinationNode(inNode); + if (!inNodeCombineSet.equals(combineSet)) { + continue; + } + } + System.out.println(" traverse more to" + inNode + " sC=" + sharedCount + " nC=" + nonSharedCount); - int dist = recur_computeDistance(startNode, inNode, endNodeSet, sharedCount, nonSharedCount); + int dist = + recur_computeDistance2(startNode, inNode, endNodeSet, sharedCount, nonSharedCount, + combineSet); if (dist > curMaxDistance) { curMaxDistance = dist; } diff --git a/Robust/src/Analysis/SSJava/LocationInference.java b/Robust/src/Analysis/SSJava/LocationInference.java index aedd279e..3adfeebe 100644 --- a/Robust/src/Analysis/SSJava/LocationInference.java +++ b/Robust/src/Analysis/SSJava/LocationInference.java @@ -1773,6 +1773,12 @@ public class LocationInference { globalFlowGraph.addMapLocationToInferCompositeLocation(targetLocalLoc, newCompLoc); // } + // if (node.getLocTuple().get(0).getDescriptor().getSymbol().equals("get_scale_factors") + // || node.getLocTuple().get(0).getDescriptor().getSymbol() + // .equals("get_LSF_scale_data")){ + // Set debugInNodeSet = + // globalFlowGraph.debug_getIncomingNodeSetFromPrefix(node, curPrefix); + // } continue next; // }