From 2e579e40f20a086e38dff23ac2b46fdd28f6f435 Mon Sep 17 00:00:00 2001 From: yeom Date: Tue, 16 Oct 2012 01:44:22 +0000 Subject: [PATCH] fixes on PCLOC generation, intermediate node insertion, etc... --- Robust/src/Analysis/SSJava/BuildLattice.java | 95 +++++++++++++++++-- Robust/src/Analysis/SSJava/FlowDownCheck.java | 7 +- .../src/Analysis/SSJava/HierarchyGraph.java | 3 - .../Analysis/SSJava/LocationInference.java | 19 +++- .../src/Analysis/SSJava/SSJavaAnalysis.java | 2 +- 5 files changed, 104 insertions(+), 22 deletions(-) diff --git a/Robust/src/Analysis/SSJava/BuildLattice.java b/Robust/src/Analysis/SSJava/BuildLattice.java index 780819f4..79c0ce95 100644 --- a/Robust/src/Analysis/SSJava/BuildLattice.java +++ b/Robust/src/Analysis/SSJava/BuildLattice.java @@ -175,9 +175,7 @@ public class BuildLattice { if (!outNode.isSkeleton()) { if (outNode.isCombinationNode()) { - 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); @@ -206,12 +204,15 @@ public class BuildLattice { visited.add(outNode); if (endCombNodeSet.size() > 0) { // follows the straight line up to another skeleton/combination node - endCombNodeSet = removeTransitivelyReachToNode(desc, startNode, endCombNodeSet); + // 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(bottomNode); } + + startNode = refineStartNode(desc, startNode, endCombNodeSet); + recurDFSNormalNode(desc, lattice, startNode, endCombNodeSet, visited, mapIntermediateLoc, 1, locSummary, outNode); } @@ -219,10 +220,6 @@ public class BuildLattice { } } - } else if (!node.isSkeleton() && node.isCombinationNode()) { - - expandCombinationNode(desc, lattice, visited, mapIntermediateLoc, locSummary, node); - } else if (!node.isSkeleton() && !node.isCombinationNode() && !node.isMergeNode() && !visited.contains(node)) { @@ -293,14 +290,39 @@ public class BuildLattice { // follows the straight line up to another skeleton/combination node if (endCombNodeSet.size() > 0) { - endCombNodeSet = - removeTransitivelyReachToNode(desc, combinationNodeInSCGraph, endCombNodeSet); + System.out.println("---endCombNodeSet=" + endCombNodeSet); + // endCombNodeSet = + // removeTransitivelyReachToNode(desc, combinationNodeInSCGraph, endCombNodeSet); + + combinationNodeInSCGraph = refineStartNode(desc, combinationNodeInSCGraph, endCombNodeSet); + + recurDFS(desc, lattice, combinationNodeInSCGraph, endCombNodeSet, visited, + mapIntermediateLoc, 1, locSummary, cnode); + } else { + endCombNodeSet.add(bottomNode); + System.out.println("---endCombNodeSet is zero"); + System.out.println("---endNodeSetFromSimpleGraph=" + endNodeSetFromSimpleGraph); + System.out.println("---incoming=" + simpleGraph.getIncomingNodeSet(cnode)); recurDFS(desc, lattice, combinationNodeInSCGraph, endCombNodeSet, visited, mapIntermediateLoc, 1, locSummary, cnode); + } } + private HNode refineStartNode(Descriptor desc, HNode startNode, Set endNodeSet) { + + HierarchyGraph scGraph = infer.getSkeletonCombinationHierarchyGraph(desc); + + HNode newStartNode = getDirectlyReachableSCNodeFromEndNode(scGraph, startNode, endNodeSet); + + System.out.println("---removeTransitivelyReachToNode2 startNode=" + startNode + " old=" + + endNodeSet + " newStartNode=" + newStartNode); + + return newStartNode; + + } + private Set removeTransitivelyReachToNode(Descriptor desc, HNode startNode, Set endNodeSet) { @@ -308,8 +330,8 @@ public class BuildLattice { // replace it with a directly connected one which transitively reaches to it. HierarchyGraph scGraph = infer.getSkeletonCombinationHierarchyGraph(desc); - Set newEndNodeSet = new HashSet(); + Set newEndNodeSet = new HashSet(); for (Iterator iterator = endNodeSet.iterator(); iterator.hasNext();) { HNode endNode = (HNode) iterator.next(); if (scGraph.isDirectlyConnectedTo(startNode, endNode)) { @@ -329,6 +351,53 @@ public class BuildLattice { } + private HNode getDirectlyReachableSCNodeFromEndNode(HierarchyGraph scGraph, HNode startNode, + Set endNodeSet) { + + System.out.println("getDirectlyReachableSCNodeFromEndNode start=" + startNode + " endNodeSet=" + + endNodeSet); + Set newStartNodeSet = new HashSet(); + + for (Iterator iterator = endNodeSet.iterator(); iterator.hasNext();) { + HNode endNode = (HNode) iterator.next(); + Set connectedToEndNodeSet = scGraph.getIncomingNodeSet(endNode); + + for (Iterator iterator2 = connectedToEndNodeSet.iterator(); iterator2.hasNext();) { + HNode curNode = (HNode) iterator2.next(); + if (recurConnectedFromStartNode(scGraph, startNode, curNode, new HashSet())) { + newStartNodeSet.add(curNode); + } + } + } + + System.out.println("newStartNodeSet=" + newStartNodeSet); + + if (newStartNodeSet.size() == 0) { + newStartNodeSet.add(startNode); + } + + return newStartNodeSet.iterator().next(); + } + + private boolean recurConnectedFromStartNode(HierarchyGraph scGraph, HNode startNode, + HNode curNode, Set visited) { + // return true if curNode is transitively connected from the startNode + + boolean isConnected = false; + Set inNodeSet = scGraph.getIncomingNodeSet(curNode); + for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) { + HNode in = (HNode) iterator.next(); + if (in.equals(startNode)) { + return true; + } else { + visited.add(in); + isConnected |= recurConnectedFromStartNode(scGraph, startNode, in, visited); + } + } + + return isConnected; + } + private HNode getDirectlyReachableNodeFromStartNodeReachToEndNode(HierarchyGraph scGraph, HNode startNode, HNode endNode) { System.out.println("getDirectlyReachableNodeFromStartNodeReachToEndNode start=" + startNode @@ -398,6 +467,12 @@ public class BuildLattice { } locSummary.addMapHNodeNameToLocationName(curNode.getName(), locName); + if (curNode.isSharedNode()) { + lattice.addSharedLoc(locName); + } + + System.out.println("-TripleItem=" + item); + System.out.println("-curNode=" + curNode.getName() + " locName=" + locName); Set outSet = graph.getOutgoingNodeSet(curNode); for (Iterator iterator2 = outSet.iterator(); iterator2.hasNext();) { diff --git a/Robust/src/Analysis/SSJava/FlowDownCheck.java b/Robust/src/Analysis/SSJava/FlowDownCheck.java index 32c6abda..502bedad 100644 --- a/Robust/src/Analysis/SSJava/FlowDownCheck.java +++ b/Robust/src/Analysis/SSJava/FlowDownCheck.java @@ -332,7 +332,7 @@ public class FlowDownCheck { } // second, check return location annotation - if (!md.getReturnType().isVoid()) { + if (!md.getReturnType().isVoid() && !ssjava.getMethodContainingSSJavaLoop().equals(md)) { if (!hasReturnLocDeclaration) { // if developer does not define method lattice // search return location in the method default lattice @@ -351,7 +351,7 @@ public class FlowDownCheck { } - if (!md.getReturnType().isVoid()) { + if (!md.getReturnType().isVoid() && !ssjava.getMethodContainingSSJavaLoop().equals(md)) { MethodLattice methodLattice = ssjava.getMethodLattice(md); String thisLocId = methodLattice.getThisLoc(); if ((!md.isStatic()) && thisLocId == null) { @@ -546,10 +546,9 @@ public class FlowDownCheck { ReturnNode rn, CompositeLocation constraint) { ExpressionNode returnExp = rn.getReturnExpression(); - + CompositeLocation declaredReturnLoc = md2ReturnLoc.get(md); - CompositeLocation returnValueLoc; if (returnExp != null) { returnValueLoc = diff --git a/Robust/src/Analysis/SSJava/HierarchyGraph.java b/Robust/src/Analysis/SSJava/HierarchyGraph.java index 6a12849f..e0fa16fc 100644 --- a/Robust/src/Analysis/SSJava/HierarchyGraph.java +++ b/Robust/src/Analysis/SSJava/HierarchyGraph.java @@ -355,8 +355,6 @@ public class HierarchyGraph { 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, @@ -372,7 +370,6 @@ public class HierarchyGraph { return false; } } - System.out.println("******** true"); return true; } return false; diff --git a/Robust/src/Analysis/SSJava/LocationInference.java b/Robust/src/Analysis/SSJava/LocationInference.java index dbcc415d..03de37f3 100644 --- a/Robust/src/Analysis/SSJava/LocationInference.java +++ b/Robust/src/Analysis/SSJava/LocationInference.java @@ -1730,7 +1730,6 @@ public class LocationInference { NTuple srcCurTuple = srcNode.getCurrentDescTuple(); NTuple dstCurTuple = dstNode.getCurrentDescTuple(); - if ((srcCurTuple.size() > 1 && dstCurTuple.size() > 1) && srcCurTuple.get(0).equals(dstCurTuple.get(0))) { @@ -2345,21 +2344,23 @@ public class LocationInference { // PC location is higher than location types of parameters which has incoming flows. Set> paramLocTupleHavingInFlowSet = new HashSet>(); + Set> paramLocTupleNOTHavingInFlowSet = new HashSet>(); int numParams = fg.getNumParameters(); for (int i = 0; i < numParams; i++) { FlowNode paramFlowNode = fg.getParamFlowNode(i); Descriptor prefix = paramFlowNode.getDescTuple().get(0); + NTuple paramDescTuple = paramFlowNode.getCurrentDescTuple(); + NTuple paramLocTuple = translateToLocTuple(md, paramDescTuple); if (fg.getIncomingNodeSetByPrefix(prefix).size() > 0) { // parameter has in-value flows - NTuple paramDescTuple = paramFlowNode.getCurrentDescTuple(); - NTuple paramLocTuple = translateToLocTuple(md, paramDescTuple); paramLocTupleHavingInFlowSet.add(paramLocTuple); + } else { + paramLocTupleNOTHavingInFlowSet.add(paramLocTuple); } } - System.out.println("paramLocTupleHavingInFlowSet=" + paramLocTupleHavingInFlowSet); if (paramLocTupleHavingInFlowSet.size() > 0 && !coversAllParamters(md, fg, paramLocTupleHavingInFlowSet)) { @@ -2378,6 +2379,8 @@ public class LocationInference { HNode pcNode = hierarchyGraph.getHNode(pcDesc); pcNode.setSkeleton(true); + // add ordering relations s.t. PCLOC is higher than all of parameters with incoming flows + // and lower than paramters which do not have any incoming flows for (Iterator iterator = paramLocTupleHavingInFlowSet.iterator(); iterator.hasNext();) { NTuple paramLocTuple = (NTuple) iterator.next(); if (paramLocTuple.size() > pcLocTupleIdx) { @@ -2386,6 +2389,14 @@ public class LocationInference { } } + for (Iterator iterator = paramLocTupleNOTHavingInFlowSet.iterator(); iterator.hasNext();) { + NTuple paramLocTuple = (NTuple) iterator.next(); + if (paramLocTuple.size() > pcLocTupleIdx) { + Descriptor higherDesc = paramLocTuple.get(pcLocTupleIdx).getLocDescriptor(); + hierarchyGraph.addEdge(higherDesc, pcDesc); + } + } + System.out.println("pcLoc=" + pcLoc); methodSummary.setPCLoc(new CompositeLocation(pcLocTuple)); diff --git a/Robust/src/Analysis/SSJava/SSJavaAnalysis.java b/Robust/src/Analysis/SSJava/SSJavaAnalysis.java index afc629cf..adf303d5 100644 --- a/Robust/src/Analysis/SSJava/SSJavaAnalysis.java +++ b/Robust/src/Analysis/SSJava/SSJavaAnalysis.java @@ -465,7 +465,7 @@ public class SSJavaAnalysis { locOrder.put(higherLoc, lowerLoc); if (locOrder.isIntroducingCycle(higherLoc)) { throw new Error("Error: the order relation " + lowerLoc + " < " + higherLoc - + " introduces a cycle."); + + " introduces a cycle in the class lattice " + cd); } } else if (orderElement.contains("*")) { // spin loc definition -- 2.34.1