From f0aec2e998d39bd8474da2e98da70bbf7a4f5b15 Mon Sep 17 00:00:00 2001 From: yeom Date: Fri, 29 Jun 2012 00:34:27 +0000 Subject: [PATCH] implemented a fixed point based interprocedural analysis that analyzes flow-graphs and construct a lattice for each method. --- Robust/src/Analysis/SSJava/FlowGraph.java | 31 ++++ .../Analysis/SSJava/LocationInference.java | 170 +++++++++--------- .../src/Analysis/SSJava/SSJavaAnalysis.java | 17 +- 3 files changed, 129 insertions(+), 89 deletions(-) diff --git a/Robust/src/Analysis/SSJava/FlowGraph.java b/Robust/src/Analysis/SSJava/FlowGraph.java index c1181a5b..fb051631 100644 --- a/Robust/src/Analysis/SSJava/FlowGraph.java +++ b/Robust/src/Analysis/SSJava/FlowGraph.java @@ -58,6 +58,17 @@ public class FlowGraph { return nodeSet; } + public Set getParameterNodeSet() { + Set paramNodeSet = new HashSet(); + for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) { + FlowNode fn = (FlowNode) iterator.next(); + if (fn.isParameter()) { + paramNodeSet.add(fn); + } + } + return paramNodeSet; + } + public void addNeighbor(FlowNode node, FlowNode neighbor) { Set set = mapNodeToNeighborSet.get(node); if (set == null) { @@ -68,6 +79,26 @@ public class FlowGraph { System.out.println("add a new neighbor " + neighbor + " to " + node); } + public boolean hasEdge(NTuple fromDescTuple, NTuple toDescTuple) { + + FlowNode fromNode = mapDescTupleToInferNode.get(fromDescTuple); + FlowNode toNode = mapDescTupleToInferNode.get(toDescTuple); + + Set fromNodeOutEdgeSet = fromNode.getOutEdgeSet(); + for (Iterator iterator = fromNodeOutEdgeSet.iterator(); iterator.hasNext();) { + FlowEdge flowEdge = (FlowEdge) iterator.next(); + if (flowEdge.getDst().equals(toNode)) { + return true; + } else { + if (hasEdge(flowEdge.getDst().getDescTuple(), toDescTuple)) { + return true; + } + } + } + + return false; + } + public void addValueFlowEdge(NTuple fromDescTuple, NTuple toDescTuple) { FlowNode fromNode = mapDescTupleToInferNode.get(fromDescTuple); diff --git a/Robust/src/Analysis/SSJava/LocationInference.java b/Robust/src/Analysis/SSJava/LocationInference.java index 66dadfa7..daa435f0 100644 --- a/Robust/src/Analysis/SSJava/LocationInference.java +++ b/Robust/src/Analysis/SSJava/LocationInference.java @@ -170,7 +170,7 @@ public class LocationInference { SSJavaLattice classLattice = cd2lattice.get(cd); if (classLattice != null) { - ssjava.writeLatticeDotFile(cd, classLattice); + ssjava.writeLatticeDotFile(cd, null, classLattice); } while (!toAnalyzeMethodIsEmpty()) { @@ -178,7 +178,7 @@ public class LocationInference { if (ssjava.needTobeAnnotated(md)) { SSJavaLattice methodLattice = md2lattice.get(md); if (methodLattice != null) { - ssjava.writeLatticeDotFile(cd, methodLattice); + ssjava.writeLatticeDotFile(cd, md, methodLattice); } } } @@ -212,16 +212,16 @@ public class LocationInference { while (!methodDescriptorsToVisitStack.isEmpty()) { // start to analyze leaf node MethodDescriptor md = methodDescriptorsToVisitStack.pop(); - FlatMethod fm = state.getMethodFlat(md); SSJavaLattice methodLattice = new SSJavaLattice(SSJavaLattice.TOP, SSJavaLattice.BOTTOM); + System.out.println(); System.out.println("SSJAVA: Inferencing the lattice from " + md); analyzeMethodLattice(md, methodLattice); - SSJavaLattice prevMethodLattice = md2lattice.get(md); + SSJavaLattice prevMethodLattice = getMethodLattice(md); if (!methodLattice.equals(prevMethodLattice)) { md2lattice.put(md, methodLattice); @@ -248,16 +248,12 @@ public class LocationInference { return desc.getSymbol(); } - private void addMappingDescriptorToLocationIdentifer(MethodDescriptor methodDesc, - VarDescriptor varDesc, String identifier) { - if (!md2LatticeMapping.containsKey(methodDesc)) { - md2LatticeMapping.put(methodDesc, new HashMap()); - } - - } - private void analyzeMethodLattice(MethodDescriptor md, SSJavaLattice methodLattice) { + // first take a look at method invocation nodes to newly added relations + // from the callee + analyzeLatticeMethodInvocationNode(md); + // visit each node of method flow graph FlowGraph fg = getFlowGraph(md); @@ -265,7 +261,6 @@ public class LocationInference { // for the method lattice, we need to look at the first element of // NTuple - for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) { FlowNode srcNode = (FlowNode) iterator.next(); @@ -277,112 +272,116 @@ public class LocationInference { addRelationToLattice(md, methodLattice, srcNode, dstNode); - // second, take a look at all nodes that are reachable from the source - // node - recursiveVisitNodes(md, srcNode, dstNode); - } } } - private void addRelationToLattice(MethodDescriptor md, SSJavaLattice methodLattice, - FlowNode srcNode, FlowNode dstNode) { - if ((srcNode.getDescTuple().size() > 1 && dstNode.getDescTuple().size() > 1) - && srcNode.getDescTuple().get(0).equals(dstNode.getDescTuple().get(0))) { - // value flow between fields: we don't need to add a binary relation - // for this case - - VarDescriptor varDesc = (VarDescriptor) srcNode.getDescTuple().get(0); - ClassDescriptor varClassDesc = varDesc.getType().getClassDesc(); + private void analyzeLatticeMethodInvocationNode(MethodDescriptor mdCaller) { - extractRelationFromFieldFlows(varClassDesc, srcNode, dstNode, 1); - return; - } + // the transformation for a call site propagates all relations between + // parameters from the callee + // if the method is virtual, it also grab all relations from any possible + // callees - // add a new binary relation of dstNode < srcNode + Set setMethodInvokeNode = + mapMethodDescriptorToMethodInvokeNodeSet.get(mdCaller); + if (setMethodInvokeNode != null) { - String srcSymbol = getSymbol(0, srcNode); - String dstSymbol = getSymbol(0, dstNode); + for (Iterator iterator = setMethodInvokeNode.iterator(); iterator.hasNext();) { + MethodInvokeNode min = (MethodInvokeNode) iterator.next(); + MethodDescriptor mdCallee = min.getMethod(); + Set setPossibleCallees = new HashSet(); + if (mdCallee.isStatic()) { + setPossibleCallees.add(mdCallee); + } else { + setPossibleCallees.addAll(ssjava.getCallGraph().getMethods(mdCallee)); + } - methodLattice.addRelationHigherToLower(srcSymbol, dstSymbol); + for (Iterator iterator2 = setPossibleCallees.iterator(); iterator2.hasNext();) { + MethodDescriptor possibleMdCallee = (MethodDescriptor) iterator2.next(); + propagateRelationToCaller(min, mdCaller, possibleMdCallee); + } - if (srcNode.isParameter() && dstNode.isParameter()) { - propagateRelationToCaller(md, srcNode, dstNode); + } } - } - private SSJavaLattice getMethodLattice(MethodDescriptor md) { - - if (!md2lattice.containsKey(md)) { - md2lattice.put(md, new SSJavaLattice(SSJavaLattice.TOP, SSJavaLattice.BOTTOM)); - } - return md2lattice.get(md); } - private void propagateRelationToCaller(MethodDescriptor calleeMethodDesc, FlowNode srcNode, - FlowNode newVisitNode) { + private void propagateRelationToCaller(MethodInvokeNode min, MethodDescriptor mdCaller, + MethodDescriptor possibleMdCallee) { - FlowGraph calleeFlowGraph = getFlowGraph(calleeMethodDesc); + SSJavaLattice calleeLattice = getMethodLattice(possibleMdCallee); - int higherLocIdxCallee = calleeFlowGraph.getParamIdx(srcNode.getDescTuple()); - int lowerLocIdxCallee = calleeFlowGraph.getParamIdx(newVisitNode.getDescTuple()); + FlowGraph calleeFlowGraph = getFlowGraph(possibleMdCallee); - System.out.println(" ssjava.getDependents(md)=" + ssjava.getDependents(calleeMethodDesc)); - Iterator depsItr = ssjava.getDependents(calleeMethodDesc).iterator(); - while (depsItr.hasNext()) { - MethodDescriptor callerMethodDesc = depsItr.next(); + // find parameter node + Set paramNodeSet = calleeFlowGraph.getParameterNodeSet(); - SSJavaLattice callerMethodLattice = md2lattice.get(callerMethodDesc); + for (Iterator iterator = paramNodeSet.iterator(); iterator.hasNext();) { + FlowNode paramFlowNode1 = (FlowNode) iterator.next(); - Set minSet = mapMethodDescriptorToMethodInvokeNodeSet.get(callerMethodDesc); - for (Iterator iterator = minSet.iterator(); iterator.hasNext();) { - MethodInvokeNode methodInvokeNode = (MethodInvokeNode) iterator.next(); - if (methodInvokeNode.getMethod().equals(calleeMethodDesc)) { - // need to propagate a relation from the callee to the caller - // TODO + for (Iterator iterator2 = paramNodeSet.iterator(); iterator2.hasNext();) { + FlowNode paramFlowNode2 = (FlowNode) iterator2.next(); - System.out.println("higherLocIdxCallee=" + higherLocIdxCallee); - System.out.println("lowerLocIdxCallee=" + lowerLocIdxCallee); - - NTuple higherArg = getArgTupleByArgIdx(methodInvokeNode, higherLocIdxCallee); - NTuple lowerArg = getArgTupleByArgIdx(methodInvokeNode, lowerLocIdxCallee); + String paramSymbol1 = getSymbol(0, paramFlowNode1); + String paramSymbol2 = getSymbol(0, paramFlowNode2); + // if two parameters have relation, we need to propagate this relation + // to the caller + if (calleeLattice.isComparable(paramSymbol1, paramSymbol2)) { + int higherLocIdxCallee; + int lowerLocIdxCallee; + if (calleeLattice.isGreaterThan(paramSymbol1, paramSymbol2)) { + higherLocIdxCallee = calleeFlowGraph.getParamIdx(paramFlowNode1.getDescTuple()); + lowerLocIdxCallee = calleeFlowGraph.getParamIdx(paramFlowNode2.getDescTuple()); + } else { + higherLocIdxCallee = calleeFlowGraph.getParamIdx(paramFlowNode2.getDescTuple()); + lowerLocIdxCallee = calleeFlowGraph.getParamIdx(paramFlowNode1.getDescTuple()); + } - FlowNode callerHigherFlowNode = getFlowGraph(callerMethodDesc).getFlowNode(higherArg); - FlowNode calleeHigherFlowNode = getFlowGraph(callerMethodDesc).getFlowNode(lowerArg); + NTuple higherArg = getArgTupleByArgIdx(min, higherLocIdxCallee); + NTuple lowerArg = getArgTupleByArgIdx(min, lowerLocIdxCallee); - addRelationToLattice(callerMethodDesc, getMethodLattice(callerMethodDesc), - callerHigherFlowNode, calleeHigherFlowNode); + addFlowGraphEdge(mdCaller, higherArg, lowerArg); } + } } + } - private void recursiveVisitNodes(MethodDescriptor md, FlowNode srcNode, FlowNode currentVisitNode) { + private void addRelationToLattice(MethodDescriptor md, SSJavaLattice methodLattice, + FlowNode srcNode, FlowNode dstNode) { + if ((srcNode.getDescTuple().size() > 1 && dstNode.getDescTuple().size() > 1) + && srcNode.getDescTuple().get(0).equals(dstNode.getDescTuple().get(0))) { + // value flow between fields: we don't need to add a binary relation + // for this case + + VarDescriptor varDesc = (VarDescriptor) srcNode.getDescTuple().get(0); + ClassDescriptor varClassDesc = varDesc.getType().getClassDesc(); + + extractRelationFromFieldFlows(varClassDesc, srcNode, dstNode, 1); + return; + } - NTuple srcTuple = srcNode.getDescTuple(); + // add a new binary relation of dstNode < srcNode - for (Iterator outEdgeIter = currentVisitNode.getOutEdgeSet().iterator(); outEdgeIter - .hasNext();) { + String srcSymbol = getSymbol(0, srcNode); + String dstSymbol = getSymbol(0, dstNode); - FlowEdge outEdge = outEdgeIter.next(); - FlowNode newVisitNode = outEdge.getDst(); + methodLattice.addRelationHigherToLower(srcSymbol, dstSymbol); - NTuple newVisitTuple = newVisitNode.getDescTuple(); + } - // if both the source node and the newly visit node are parameters, - // need to keep this relation, then later add a new relation between - // corresponding arguments in the caller's lattice. - if (srcNode.isParameter() && newVisitNode.isParameter()) { - System.out.println("src=" + srcNode + " newVisitNode=" + newVisitNode); - propagateRelationToCaller(md, srcNode, newVisitNode); - } + private SSJavaLattice getMethodLattice(MethodDescriptor md) { + if (!md2lattice.containsKey(md)) { + md2lattice.put(md, new SSJavaLattice(SSJavaLattice.TOP, SSJavaLattice.BOTTOM)); } - + return md2lattice.get(md); } private void extractRelationFromFieldFlows(ClassDescriptor cd, FlowNode srcNode, @@ -509,7 +508,6 @@ public class LocationInference { private void analyzeSwitchStatementNode(MethodDescriptor md, SymbolTable nametable, SwitchStatementNode bsn) { // TODO Auto-generated method stub - } private void analyzeFlowSubBlockNode(MethodDescriptor md, SymbolTable nametable, @@ -1124,9 +1122,13 @@ public class LocationInference { return mapMethodDescriptorToFlowGraph.get(md); } - public void addFlowGraphEdge(MethodDescriptor md, NTuple from, NTuple to) { + public 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; } public void _debug_printGraph() { diff --git a/Robust/src/Analysis/SSJava/SSJavaAnalysis.java b/Robust/src/Analysis/SSJava/SSJavaAnalysis.java index 344dd83b..b72f077a 100644 --- a/Robust/src/Analysis/SSJava/SSJavaAnalysis.java +++ b/Robust/src/Analysis/SSJava/SSJavaAnalysis.java @@ -283,7 +283,7 @@ public class SSJavaAnalysis { if (state.SSJAVADEBUG) { // generate lattice dot file - writeLatticeDotFile(cd, locOrder); + writeLatticeDotFile(cd, null, locOrder); } } else if (marker.equals(METHODDEFAULT)) { @@ -327,16 +327,23 @@ public class SSJavaAnalysis { } } - public void writeLatticeDotFile(ClassDescriptor cd, SSJavaLattice locOrder) { + public void writeLatticeDotFile(ClassDescriptor cd, MethodDescriptor md, + SSJavaLattice locOrder) { - String className = cd.getSymbol().replaceAll("[\\W_]", ""); + String fileName = "lattice_"; + if (md != null) { + fileName += + cd.getSymbol().replaceAll("[\\W_]", "") + "_" + md.getSymbol().replaceAll("[\\W_]", ""); + } else { + fileName += cd.getSymbol().replaceAll("[\\W_]", ""); + } Set> pairSet = locOrder.getOrderingPairSet(); try { - BufferedWriter bw = new BufferedWriter(new FileWriter(className + ".dot")); + BufferedWriter bw = new BufferedWriter(new FileWriter(fileName + ".dot")); - bw.write("digraph " + className + " {\n"); + bw.write("digraph " + fileName + " {\n"); for (Iterator iterator = pairSet.iterator(); iterator.hasNext();) { // pair is in the form of -- 2.34.1