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);
rtr +=
"\n@RETURNLOC(\"" + generateLocationAnnoatation(methodLocInfo.getReturnLoc()) + "\")";
}
- rtr += "\n@THISLOC(\"this\")\n@GLOBALLOC(\"GLOBALLOC\")";
- if (lattice.containsKey("PCLOC")) {
- rtr += "\n@PCLOC(\"PCLOC\")";
+ rtr += "\n@THISLOC(\"this\")";
+ rtr += "\n@GLOBALLOC(\"GLOBALLOC\")";
+
+ CompositeLocation pcLoc = methodLocInfo.getPCLoc();
+ if ((pcLoc != null) && (!pcLoc.get(0).isTop())) {
+ rtr += "\n@PCLOC(\"" + generateLocationAnnoatation(pcLoc) + "\")";
}
+
}
return rtr;
}
for (Iterator iter = cd.getFields(); iter.hasNext();) {
- Descriptor fieldDesc = (Descriptor) iter.next();
- String locIdentifier = locInfo.getFieldInferLocation(fieldDesc).getLocIdentifier();
- if (!getLattice(cd).containsKey(locIdentifier)) {
- getLattice(cd).put(locIdentifier);
+ FieldDescriptor fieldDesc = (FieldDescriptor) iter.next();
+ if (!(fieldDesc.isStatic() && fieldDesc.isFinal())) {
+ String locIdentifier = locInfo.getFieldInferLocation(fieldDesc).getLocIdentifier();
+ if (!getLattice(cd).getElementSet().contains(locIdentifier)) {
+ getLattice(cd).put(locIdentifier);
+ }
}
}
FieldDescriptor fd = (FieldDescriptor) iter.next();
String locAnnotationStr;
- if (inferLocMap.containsKey(fd)) {
- CompositeLocation inferLoc = inferLocMap.get(fd);
+ CompositeLocation inferLoc = inferLocMap.get(fd);
+
+ if (inferLoc != null) {
+ // infer loc is null if the corresponding field is static and final
locAnnotationStr = "@LOC(\"" + generateLocationAnnoatation(inferLoc) + "\")";
- } else {
- // if the field is not accssed by SS part, just assigns dummy
- // location
- locAnnotationStr = "@LOC(\"LOC\")";
+ int fdLineNum = fd.getLineNum();
+ String orgFieldDeclarationStr = sourceVec.get(fdLineNum);
+ String fieldDeclaration = fd.toString();
+ fieldDeclaration = fieldDeclaration.substring(0, fieldDeclaration.length() - 1);
+ String annoatedStr = locAnnotationStr + " " + orgFieldDeclarationStr;
+ sourceVec.set(fdLineNum, annoatedStr);
}
- int fdLineNum = fd.getLineNum();
- String orgFieldDeclarationStr = sourceVec.get(fdLineNum);
- String fieldDeclaration = fd.toString();
- fieldDeclaration = fieldDeclaration.substring(0, fieldDeclaration.length() - 1);
-
- String annoatedStr = locAnnotationStr + " " + orgFieldDeclarationStr;
- sourceVec.set(fdLineNum, annoatedStr);
}
methodLocInfo.getMapDescToInferLocation();
Set<Descriptor> localVarDescSet = methodInferLocMap.keySet();
+ Set<String> localLocElementSet = methodLattice.getElementSet();
+
for (Iterator iterator = localVarDescSet.iterator(); iterator.hasNext();) {
Descriptor localVarDesc = (Descriptor) iterator.next();
CompositeLocation inferLoc = methodInferLocMap.get(localVarDesc);
+ String localLocIdentifier = inferLoc.get(0).getLocIdentifier();
+ if (!localLocElementSet.contains(localLocIdentifier)) {
+ methodLattice.put(localLocIdentifier);
+ }
+
String locAnnotationStr = "@LOC(\"" + generateLocationAnnoatation(inferLoc) + "\")";
if (!isParameter(md, localVarDesc)) {
}
+ // check if the lattice has to have the location type for the this
+ // reference...
+
+ // boolean needToAddthisRef = hasThisReference(md);
+ if (localLocElementSet.contains("this")) {
+ methodLattice.put("this");
+ }
+
String methodLatticeDefStr = generateLatticeDefinition(md);
String annoatedStr = methodLatticeDefStr + newline + sourceVec.get(methodDefLine);
sourceVec.set(methodDefLine, annoatedStr);
codeGen();
}
+ private boolean hasThisReference(MethodDescriptor md) {
+
+ FlowGraph fg = getFlowGraph(md);
+ Set<FlowNode> nodeSet = fg.getNodeSet();
+ for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
+ FlowNode flowNode = (FlowNode) iterator.next();
+ if (flowNode.getDescTuple().get(0).equals(md.getThis())) {
+ return true;
+ }
+ }
+
+ return false;
+ }
+
private int getParamLocation(String methodStr, String paramStr) {
String pattern = paramStr + ",";
}
Map<Integer, CompositeLocation> mapParamToLoc = methodInfo.getMapParamIdxToInferLoc();
- Set<Integer> keySet = mapParamToLoc.keySet();
+ Set<Integer> paramIdxSet = mapParamToLoc.keySet();
try {
if (!ssjava.getMethodContainingSSJavaLoop().equals(md)) {
// PC location is higher than location types of all parameters
String pcLocSymbol = "PCLOC";
- for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
+ Set<CompositeLocation> paramInFlowSet = new HashSet<CompositeLocation>();
+
+ for (Iterator iterator = paramIdxSet.iterator(); iterator.hasNext();) {
Integer paramIdx = (Integer) iterator.next();
- CompositeLocation inferLoc = mapParamToLoc.get(paramIdx);
- String paramLocLocalSymbol = inferLoc.get(0).getLocIdentifier();
- if (!methodLattice.isGreaterThan(pcLocSymbol, paramLocLocalSymbol)) {
- addRelationHigherToLower(methodLattice, methodInfo, pcLocSymbol, paramLocLocalSymbol);
-
- Set<String> higherLocSet = getHigherLocSymbolThan(methodLattice, paramLocLocalSymbol);
- higherLocSet.remove(pcLocSymbol);
- for (Iterator iterator2 = higherLocSet.iterator(); iterator2.hasNext();) {
- String loc = (String) iterator2.next();
- addRelationHigherToLower(methodLattice, methodInfo, pcLocSymbol, loc);
- }
+
+ FlowNode paramFlowNode = fg.getParamFlowNode(paramIdx);
+
+ if (fg.getIncomingFlowNodeSet(paramFlowNode).size() > 0) {
+ // parameter has in-value flows
+ CompositeLocation inferLoc = mapParamToLoc.get(paramIdx);
+ paramInFlowSet.add(inferLoc);
}
}
- Set<String> locElementSet = methodLattice.getElementSet();
- locElementSet.remove(pcLocSymbol);
- for (Iterator iterator = locElementSet.iterator(); iterator.hasNext();) {
- String loc = (String) iterator.next();
- if (!methodLattice.isGreaterThan(pcLocSymbol, loc)) {
- addRelationHigherToLower(methodLattice, methodInfo, pcLocSymbol, loc);
- }
+ if (paramInFlowSet.size() > 0) {
+ CompositeLocation lowestLoc = getLowest(methodLattice, paramInFlowSet);
+ assert (lowestLoc != null);
+ methodInfo.setPCLoc(lowestLoc);
}
}
}
Set<FlowNode> returnNodeSet = fg.getReturnNodeSet();
+
skip: for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) {
FlowNode returnNode = (FlowNode) iterator.next();
CompositeLocation inferReturnLoc =
if (inferFieldReturnLocSet.size() > 0) {
CompositeLocation returnLoc = getLowest(methodLattice, inferFieldReturnLocSet);
+ if (returnLoc == null) {
+ // in this case, assign <'this',bottom> to the RETURNLOC
+ returnLoc = new CompositeLocation(new Location(md, md.getThis().getSymbol()));
+ returnLoc.addLocation(new Location(md.getClassDesc(), getLattice(md.getClassDesc())
+ .getBottomItem()));
+ }
methodInfo.setReturnLoc(returnLoc);
} else {
new CompositeLocation(new Location(md, returnLocSymbol));
methodInfo.setReturnLoc(returnLocInferLoc);
- for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
+ for (Iterator iterator = paramIdxSet.iterator(); iterator.hasNext();) {
Integer paramIdx = (Integer) iterator.next();
CompositeLocation inferLoc = mapParamToLoc.get(paramIdx);
String paramLocLocalSymbol = inferLoc.get(0).getLocIdentifier();
for (Iterator iterator = set.iterator(); iterator.hasNext();) {
CompositeLocation loc = (CompositeLocation) iterator.next();
- if (isGreaterThan(methodLattice, lowest, loc)) {
+
+ if ((!loc.equals(lowest)) && (!isComparable(methodLattice, lowest, loc))) {
+ // if there is a case where composite locations are incomparable, just
+ // return null
+ return null;
+ }
+
+ if ((!loc.equals(lowest)) && isGreaterThan(methodLattice, lowest, loc)) {
lowest = loc;
}
}
return lowest;
}
+ private boolean isComparable(SSJavaLattice<String> methodLattice, CompositeLocation comp1,
+ CompositeLocation comp2) {
+
+ int size = comp1.getSize() >= comp2.getSize() ? comp2.getSize() : comp1.getSize();
+
+ for (int idx = 0; idx < size; idx++) {
+ Location loc1 = comp1.get(idx);
+ Location loc2 = comp2.get(idx);
+
+ Descriptor desc1 = loc1.getDescriptor();
+ Descriptor desc2 = loc2.getDescriptor();
+
+ if (!desc1.equals(desc2)) {
+ throw new Error("Fail to compare " + comp1 + " and " + comp2);
+ }
+
+ String symbol1 = loc1.getLocIdentifier();
+ String symbol2 = loc2.getLocIdentifier();
+
+ SSJavaLattice<String> lattice;
+ if (idx == 0) {
+ lattice = methodLattice;
+ } else {
+ lattice = getLattice(desc1);
+ }
+
+ if (symbol1.equals(symbol2)) {
+ continue;
+ } else if (!lattice.isComparable(symbol1, symbol2)) {
+ return false;
+ }
+
+ }
+
+ return true;
+ }
+
private boolean isGreaterThan(SSJavaLattice<String> methodLattice, CompositeLocation comp1,
CompositeLocation comp2) {
} else {
lattice = getLattice(desc1);
}
+
if (symbol1.equals(symbol2)) {
continue;
} else if (lattice.isGreaterThan(symbol1, symbol2)) {
MethodDescriptor possibleMdCallee, SSJavaLattice<String> methodLattice,
MethodLocationInfo methodInfo) throws CyclicFlowException {
-
SSJavaLattice<String> calleeLattice = getMethodLattice(possibleMdCallee);
MethodLocationInfo calleeLocInfo = getMethodLocationInfo(possibleMdCallee);
FlowGraph calleeFlowGraph = getFlowGraph(possibleMdCallee);
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));
// 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 =
}
private boolean calculateCompositeLocation(FlowGraph flowGraph,
- SSJavaLattice<String> methodLattice, MethodLocationInfo methodInfo, FlowNode flowNode)
- throws CyclicFlowException {
+ SSJavaLattice<String> methodLattice, MethodLocationInfo methodInfo, FlowNode flowNode,
+ FlowNode srcNode) throws CyclicFlowException {
Descriptor localVarDesc = flowNode.getDescTuple().get(0);
NTuple<Location> flowNodelocTuple = flowGraph.getLocationTuple(flowNode);
}
});
- 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++) {
// 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<Location> 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
analyzeFlowExpressionNode(md, nametable, isn.getCondition(), condTupleNode, null,
implicitFlowTupleSet, false);
+// NTuple<Descriptor> interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple();
+// for (Iterator<NTuple<Descriptor>> idxIter = condTupleNode.iterator(); idxIter.hasNext();) {
+// NTuple<Descriptor> tuple = idxIter.next();
+// addFlowGraphEdge(md, tuple, interTuple);
+// }
+//
+// for (Iterator<NTuple<Descriptor>> idxIter = implicitFlowTupleSet.iterator(); idxIter.hasNext();) {
+// NTuple<Descriptor> 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);
private void analyzeFlowMethodInvokeNode(MethodDescriptor md, SymbolTable nametable,
MethodInvokeNode min, NodeTupleSet nodeSet, NodeTupleSet implicitFlowTupleSet) {
-
if (nodeSet == null) {
nodeSet = new NodeTupleSet();
}
analyzeFlowExpressionNode(md, nametable, min.getExpression(), baseNodeSet, null,
implicitFlowTupleSet, false);
-
if (!min.getMethod().isStatic()) {
addArgIdxMap(min, 0, baseNodeSet);
-
for (Iterator iterator = calleeReturnSet.iterator(); iterator.hasNext();) {
FlowNode returnNode = (FlowNode) iterator.next();
NTuple<Descriptor> returnDescTuple = returnNode.getDescTuple();
ArrayAccessNode aan, NodeTupleSet nodeSet, boolean isLHS) {
NodeTupleSet expNodeTupleSet = new NodeTupleSet();
- analyzeFlowExpressionNode(md, nametable, aan.getExpression(), expNodeTupleSet, isLHS);
+ NTuple<Descriptor> base =
+ analyzeFlowExpressionNode(md, nametable, aan.getExpression(), expNodeTupleSet, isLHS);
NodeTupleSet idxNodeTupleSet = new NodeTupleSet();
analyzeFlowExpressionNode(md, nametable, aan.getIndex(), idxNodeTupleSet, isLHS);
}
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 =
if (an.getOperation().getOp() >= 2 && an.getOperation().getOp() <= 12) {
// if assignment contains OP+EQ operator, creates edges from LHS to LHS
+
for (Iterator<NTuple<Descriptor>> iter = nodeSetLHS.iterator(); iter.hasNext();) {
NTuple<Descriptor> fromTuple = iter.next();
for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
}
// creates edges from RHS to LHS
+ NTuple<Descriptor> interTuple = null;
+ if (nodeSetRHS.size() > 1) {
+ interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple();
+ }
+
for (Iterator<NTuple<Descriptor>> iter = nodeSetRHS.iterator(); iter.hasNext();) {
NTuple<Descriptor> fromTuple = iter.next();
for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
NTuple<Descriptor> toTuple = iter2.next();
- addFlowGraphEdge(md, fromTuple, toTuple);
+ addFlowGraphEdge(md, fromTuple, interTuple, toTuple);
}
}
} else {
// postinc case
+
for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
NTuple<Descriptor> tuple = iter2.next();
addFlowGraphEdge(md, tuple, tuple);
private boolean addFlowGraphEdge(MethodDescriptor md, NTuple<Descriptor> from,
NTuple<Descriptor> 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<Descriptor> from,
+ NTuple<Descriptor> inter, NTuple<Descriptor> 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<MethodDescriptor> keySet = mapMethodDescriptorToFlowGraph.keySet();
class CyclicFlowException extends Exception {
}
+
+class InterDescriptor extends Descriptor {
+
+ public InterDescriptor(String name) {
+ super(name);
+ }
+
+}
projects / IRC.git / blobdiff