From 98bc69de0d44f8c7b7e4ce2e11f398e8a0e0a1e7 Mon Sep 17 00:00:00 2001 From: yeom Date: Fri, 17 Aug 2012 10:55:17 +0000 Subject: [PATCH] changes. --- Robust/src/Analysis/SSJava/FlowDownCheck.java | 41 +++++-- Robust/src/Analysis/SSJava/FlowGraph.java | 24 +++- Robust/src/Analysis/SSJava/FlowNode.java | 10 ++ .../Analysis/SSJava/LocationInference.java | 107 ++++++++++++++++-- Robust/src/Analysis/SSJava/NodeTupleSet.java | 4 + 5 files changed, 165 insertions(+), 21 deletions(-) diff --git a/Robust/src/Analysis/SSJava/FlowDownCheck.java b/Robust/src/Analysis/SSJava/FlowDownCheck.java index 85b36731..d01e094e 100644 --- a/Robust/src/Analysis/SSJava/FlowDownCheck.java +++ b/Robust/src/Analysis/SSJava/FlowDownCheck.java @@ -668,7 +668,6 @@ public class FlowDownCheck { constraint, false); // addLocationType(isn.getCondition().getType(), condLoc); - constraint = generateNewConstraint(constraint, condLoc); checkLocationFromBlockNode(md, nametable, isn.getTrueBlock(), constraint); @@ -1021,6 +1020,10 @@ public class FlowDownCheck { // location in the caller's perspective CompositeLocation ceilingLoc = computeCeilingLocationForCaller(md, nametable, min, baseLocation, constraint); + + if (ceilingLoc == null) { + return new CompositeLocation(Location.createTopLocation(md)); + } return ceilingLoc; } } @@ -1140,7 +1143,9 @@ public class FlowDownCheck { List argList = new ArrayList(); // by default, method has a THIS parameter - argList.add(baseLocation); + if (!md.isStatic()) { + argList.add(baseLocation); + } for (int i = 0; i < min.numArgs(); i++) { ExpressionNode en = min.getArg(i); @@ -1565,7 +1570,6 @@ public class FlowDownCheck { private CompositeLocation checkLocationFromAssignmentNode(MethodDescriptor md, SymbolTable nametable, AssignmentNode an, CompositeLocation loc, CompositeLocation constraint) { - ClassDescriptor cd = md.getClassDesc(); Set inputGLBSet = new HashSet(); @@ -1605,9 +1609,16 @@ public class FlowDownCheck { } if (constraint != null) { - inputGLBSet.add(srcLocation); - inputGLBSet.add(constraint); - srcLocation = CompositeLattice.calculateGLB(inputGLBSet, generateErrorMessage(cd, an)); + + if (!CompositeLattice.isGreaterThan(constraint, destLocation, generateErrorMessage(cd, an))) { + throw new Error("The value flow from " + constraint + " to " + destLocation + + " does not respect location hierarchy on the assignment " + an.printNode(0) + + " at " + cd.getSourceFileName() + "::" + an.getNumLine()); + } + // inputGLBSet.add(srcLocation); + // inputGLBSet.add(constraint); + // srcLocation = CompositeLattice.calculateGLB(inputGLBSet, + // generateErrorMessage(cd, an)); } if (!CompositeLattice.isGreaterThan(srcLocation, destLocation, generateErrorMessage(cd, an))) { @@ -1639,9 +1650,17 @@ public class FlowDownCheck { constraint, false); if (constraint != null) { - inputGLBSet.add(rhsLocation); - inputGLBSet.add(constraint); - srcLocation = CompositeLattice.calculateGLB(inputGLBSet, generateErrorMessage(cd, an)); + + if (!CompositeLattice.isGreaterThan(constraint, destLocation, generateErrorMessage(cd, an))) { + throw new Error("The value flow from " + constraint + " to " + destLocation + + " does not respect location hierarchy on the assignment " + an.printNode(0) + + " at " + cd.getSourceFileName() + "::" + an.getNumLine()); + } + // inputGLBSet.add(rhsLocation); + // inputGLBSet.add(constraint); + // srcLocation = CompositeLattice.calculateGLB(inputGLBSet, + // generateErrorMessage(cd, an)); + srcLocation = rhsLocation; } else { srcLocation = rhsLocation; } @@ -2084,7 +2103,6 @@ public class FlowDownCheck { SSJavaLattice locOrder = getLatticeByDescriptor(priorityDescriptor); String glbOfPriorityLoc = locOrder.getGLB(priorityLocIdentifierSet); - glbCompLoc.addLocation(new Location(priorityDescriptor, glbOfPriorityLoc)); Set compSet = locId2CompLocSet.get(glbOfPriorityLoc); @@ -2346,6 +2364,9 @@ class ReturnLocGenerator { // compute GLB of arguments subset that are same or higher than return // location if (inputGLB.isEmpty()) { + if (args.size() == 0) { + return null; + } CompositeLocation rtr = new CompositeLocation(Location.createTopLocation(args.get(0).get(0).getDescriptor())); return rtr; diff --git a/Robust/src/Analysis/SSJava/FlowGraph.java b/Robust/src/Analysis/SSJava/FlowGraph.java index 39d70614..8dbecd3c 100644 --- a/Robust/src/Analysis/SSJava/FlowGraph.java +++ b/Robust/src/Analysis/SSJava/FlowGraph.java @@ -13,6 +13,7 @@ import IR.ClassDescriptor; import IR.Descriptor; import IR.FieldDescriptor; import IR.MethodDescriptor; +import IR.NameDescriptor; import IR.VarDescriptor; public class FlowGraph { @@ -37,6 +38,8 @@ public class FlowGraph { Map mapIdxToFlowNode; + public static int interseed = 0; + boolean debug = true; public FlowGraph(MethodDescriptor md, Map mapParamDescToIdx) { @@ -66,6 +69,15 @@ public class FlowGraph { } + public FlowNode createIntermediateNode() { + NTuple tuple = new NTuple(); + Descriptor interDesc = new InterDescriptor(LocationInference.INTERLOC + interseed); + tuple.add(interDesc); + interseed++; + FlowNode node = createNewFlowNode(tuple, true); + return node; + } + private void setupMapIdxToDesc() { Set descSet = mapParamDescToIdx.keySet(); @@ -194,9 +206,14 @@ public class FlowGraph { } public FlowNode createNewFlowNode(NTuple tuple) { + return createNewFlowNode(tuple, false); + } + + public FlowNode createNewFlowNode(NTuple tuple, boolean isIntermediate) { if (!mapDescTupleToInferNode.containsKey(tuple)) { FlowNode node = new FlowNode(tuple, isParameter(tuple)); + node.setIntermediate(isIntermediate); mapDescTupleToInferNode.put(tuple, node); nodeSet.add(node); @@ -285,7 +302,12 @@ public class FlowGraph { ClassDescriptor cd = null; Descriptor localDesc = fn.getDescTuple().get(0); - if (localDesc.getSymbol().equals(LocationInference.TOPLOC)) { + + if (fn.isIntermediate()) { + Location interLoc = new Location(md, localDesc.getSymbol()); + interLoc.setLocDescriptor(localDesc); + locTuple.add(interLoc); + } else if (localDesc.getSymbol().equals(LocationInference.TOPLOC)) { Location topLoc = new Location(md, Location.TOP); topLoc.setLocDescriptor(LocationInference.TOPDESC); locTuple.add(topLoc); diff --git a/Robust/src/Analysis/SSJava/FlowNode.java b/Robust/src/Analysis/SSJava/FlowNode.java index c24d5776..7aea5dea 100644 --- a/Robust/src/Analysis/SSJava/FlowNode.java +++ b/Robust/src/Analysis/SSJava/FlowNode.java @@ -25,6 +25,16 @@ public class FlowNode { private boolean isDeclarationNode = false; + private boolean isIntermediate; + + public boolean isIntermediate() { + return isIntermediate; + } + + public void setIntermediate(boolean isIntermediate) { + this.isIntermediate = isIntermediate; + } + public Set getFieldNodeSet() { return fieldNodeSet; } diff --git a/Robust/src/Analysis/SSJava/LocationInference.java b/Robust/src/Analysis/SSJava/LocationInference.java index cd5a58d3..9eea1427 100644 --- a/Robust/src/Analysis/SSJava/LocationInference.java +++ b/Robust/src/Analysis/SSJava/LocationInference.java @@ -95,6 +95,8 @@ public class LocationInference { public static final String TOPLOC = "TOPLOC"; + public static final String INTERLOC = "INTERLOC"; + public static final Descriptor GLOBALDESC = new NameDescriptor(GLOBALLOC); public static final Descriptor TOPDESC = new NameDescriptor(TOPLOC); @@ -325,7 +327,7 @@ public class LocationInference { rtr += "\n@GLOBALLOC(\"GLOBALLOC\")"; CompositeLocation pcLoc = methodLocInfo.getPCLoc(); - if (pcLoc != null) { + if ((pcLoc != null) && (!pcLoc.get(0).isTop())) { rtr += "\n@PCLOC(\"" + generateLocationAnnoatation(pcLoc) + "\")"; } @@ -1393,7 +1395,7 @@ public class LocationInference { FlowGraph flowGraph = getFlowGraph(md); try { System.out.println("***** src composite case::"); - calculateCompositeLocation(flowGraph, methodLattice, methodInfo, srcNode); + calculateCompositeLocation(flowGraph, methodLattice, methodInfo, srcNode, null); CompositeLocation srcInferLoc = generateInferredCompositeLocation(methodInfo, flowGraph.getLocationTuple(srcNode)); @@ -1404,7 +1406,7 @@ public class LocationInference { // there is a cyclic value flow... try to calculate a composite location // for the destination node System.out.println("***** dst composite case::"); - calculateCompositeLocation(flowGraph, methodLattice, methodInfo, dstNode); + calculateCompositeLocation(flowGraph, methodLattice, methodInfo, dstNode, srcNode); CompositeLocation srcInferLoc = generateInferredCompositeLocation(methodInfo, flowGraph.getLocationTuple(srcNode)); CompositeLocation dstInferLoc = @@ -1488,8 +1490,8 @@ public class LocationInference { } private boolean calculateCompositeLocation(FlowGraph flowGraph, - SSJavaLattice methodLattice, MethodLocationInfo methodInfo, FlowNode flowNode) - throws CyclicFlowException { + SSJavaLattice methodLattice, MethodLocationInfo methodInfo, FlowNode flowNode, + FlowNode srcNode) throws CyclicFlowException { Descriptor localVarDesc = flowNode.getDescTuple().get(0); NTuple flowNodelocTuple = flowGraph.getLocationTuple(flowNode); @@ -1538,8 +1540,8 @@ public class LocationInference { } }); - System.out.println("prefixList=" + prefixList); - System.out.println("reachableNodeSet=" + reachableNodeSet); + // System.out.println("prefixList=" + prefixList); + // System.out.println("reachableNodeSet=" + reachableNodeSet); // find out reachable nodes that have the longest common prefix for (int i = 0; i < prefixList.size(); i++) { @@ -1585,6 +1587,43 @@ public class LocationInference { // the same infer location is already existed. no need to do // anything System.out.println("NO ATTEMPT TO MAKE A COMPOSITE LOCATION curPrefix=" + curPrefix); + + // TODO: refactoring! + if (srcNode != null) { + CompositeLocation newLoc = new CompositeLocation(); + String newLocSymbol = "Loc" + (SSJavaLattice.seed++); + for (int locIdx = 0; locIdx < curPrefix.size(); locIdx++) { + newLoc.addLocation(curPrefix.get(locIdx)); + } + Location newLocationElement = new Location(desc, newLocSymbol); + newLoc.addLocation(newLocationElement); + + Descriptor srcLocalVar = srcNode.getDescTuple().get(0); + methodInfo.mapDescriptorToLocation(srcLocalVar, newLoc.clone()); + addMapLocSymbolToInferredLocation(methodInfo.getMethodDesc(), srcLocalVar, newLoc); + methodInfo.removeMaplocalVarToLocSet(srcLocalVar); + + // add the field/var descriptor to the set of the location symbol + int lastIdx = srcNode.getDescTuple().size() - 1; + Descriptor lastFlowNodeDesc = srcNode.getDescTuple().get(lastIdx); + NTuple srcNodelocTuple = flowGraph.getLocationTuple(srcNode); + Descriptor enclosinglastLastFlowNodeDesc = srcNodelocTuple.get(lastIdx).getDescriptor(); + + CompositeLocation newlyInferredLocForFlowNode = + generateInferredCompositeLocation(methodInfo, srcNodelocTuple); + Location lastInferLocElement = + newlyInferredLocForFlowNode.get(newlyInferredLocForFlowNode.getSize() - 1); + Descriptor enclosingLastInferLocElement = lastInferLocElement.getDescriptor(); + + // getLocationInfo(enclosingLastInferLocElement).addMapLocSymbolToDescSet( + // lastInferLocElement.getLocIdentifier(), lastFlowNodeDesc); + getLocationInfo(enclosingLastInferLocElement).addMapLocSymbolToRelatedInferLoc( + lastInferLocElement.getLocIdentifier(), enclosinglastLastFlowNodeDesc, + lastFlowNodeDesc); + + System.out.println("@@@@@@@ ASSIGN " + newLoc + " to SRC=" + srcNode); + } + return true; } else { // assign a new composite location @@ -2115,6 +2154,25 @@ public class LocationInference { analyzeFlowExpressionNode(md, nametable, isn.getCondition(), condTupleNode, null, implicitFlowTupleSet, false); +// NTuple interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple(); +// for (Iterator> idxIter = condTupleNode.iterator(); idxIter.hasNext();) { +// NTuple tuple = idxIter.next(); +// addFlowGraphEdge(md, tuple, interTuple); +// } +// +// for (Iterator> idxIter = implicitFlowTupleSet.iterator(); idxIter.hasNext();) { +// NTuple tuple = idxIter.next(); +// addFlowGraphEdge(md, tuple, interTuple); +// } +// +// NodeTupleSet newImplicitSet = new NodeTupleSet(); +// newImplicitSet.addTuple(interTuple); +// analyzeFlowBlockNode(md, nametable, isn.getTrueBlock(), newImplicitSet); +// +// if (isn.getFalseBlock() != null) { +// analyzeFlowBlockNode(md, nametable, isn.getFalseBlock(), newImplicitSet); +// } + // add edges from condNodeTupleSet to all nodes of conditional nodes condTupleNode.addTupleSet(implicitFlowTupleSet); analyzeFlowBlockNode(md, nametable, isn.getTrueBlock(), condTupleNode); @@ -2641,12 +2699,14 @@ public class LocationInference { } NodeTupleSet idxNodeTupleSet = new NodeTupleSet(); + if (left instanceof ArrayAccessNode) { ArrayAccessNode aan = (ArrayAccessNode) left; left = aan.getExpression(); analyzeFlowExpressionNode(md, nametable, aan.getIndex(), idxNodeTupleSet, base, implicitFlowTupleSet, isLHS); + nodeSet.addTupleSet(idxNodeTupleSet); } base = @@ -2720,6 +2780,7 @@ public class LocationInference { if (an.getOperation().getOp() >= 2 && an.getOperation().getOp() <= 12) { // if assignment contains OP+EQ operator, creates edges from LHS to LHS + for (Iterator> iter = nodeSetLHS.iterator(); iter.hasNext();) { NTuple fromTuple = iter.next(); for (Iterator> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) { @@ -2730,11 +2791,16 @@ public class LocationInference { } // creates edges from RHS to LHS + NTuple interTuple = null; + if (nodeSetRHS.size() > 1) { + interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple(); + } + for (Iterator> iter = nodeSetRHS.iterator(); iter.hasNext();) { NTuple fromTuple = iter.next(); for (Iterator> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) { NTuple toTuple = iter2.next(); - addFlowGraphEdge(md, fromTuple, toTuple); + addFlowGraphEdge(md, fromTuple, interTuple, toTuple); } } @@ -2749,6 +2815,7 @@ public class LocationInference { } else { // postinc case + for (Iterator> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) { NTuple tuple = iter2.next(); addFlowGraphEdge(md, tuple, tuple); @@ -2776,13 +2843,25 @@ public class LocationInference { private boolean addFlowGraphEdge(MethodDescriptor md, NTuple from, NTuple to) { - // TODO - // return true if it adds a new edge FlowGraph graph = getFlowGraph(md); graph.addValueFlowEdge(from, to); return true; } + private void addFlowGraphEdge(MethodDescriptor md, NTuple from, + NTuple inter, NTuple to) { + + FlowGraph graph = getFlowGraph(md); + + if (inter != null) { + graph.addValueFlowEdge(from, inter); + graph.addValueFlowEdge(inter, to); + } else { + graph.addValueFlowEdge(from, to); + } + + } + public void _debug_printGraph() { Set keySet = mapMethodDescriptorToFlowGraph.keySet(); @@ -2803,3 +2882,11 @@ public class LocationInference { class CyclicFlowException extends Exception { } + +class InterDescriptor extends Descriptor { + + public InterDescriptor(String name) { + super(name); + } + +} diff --git a/Robust/src/Analysis/SSJava/NodeTupleSet.java b/Robust/src/Analysis/SSJava/NodeTupleSet.java index eaa0e6e9..805a210d 100644 --- a/Robust/src/Analysis/SSJava/NodeTupleSet.java +++ b/Robust/src/Analysis/SSJava/NodeTupleSet.java @@ -54,4 +54,8 @@ public class NodeTupleSet { } } } + + public int size() { + return list.size(); + } } -- 2.34.1