import java.util.StringTokenizer;
import java.util.Vector;
+import Analysis.SSJava.FlowDownCheck.ComparisonResult;
+import Analysis.SSJava.FlowDownCheck.CompositeLattice;
import IR.AnnotationDescriptor;
import IR.ClassDescriptor;
import IR.Descriptor;
public class FlowDownCheck {
- static State state;
+ State state;
static SSJavaAnalysis ssjava;
HashSet toanalyze;
// mapping from 'descriptor' to 'composite location'
Hashtable<Descriptor, CompositeLocation> d2loc;
+ Hashtable<MethodDescriptor, CompositeLocation> md2ReturnLoc;
+ Hashtable<MethodDescriptor, ReturnLocGenerator> md2ReturnLocGen;
+
// mapping from 'locID' to 'class descriptor'
Hashtable<String, ClassDescriptor> fieldLocName2cd;
this.toanalyze = new HashSet();
this.d2loc = new Hashtable<Descriptor, CompositeLocation>();
this.fieldLocName2cd = new Hashtable<String, ClassDescriptor>();
- init();
+ this.md2ReturnLoc = new Hashtable<MethodDescriptor, CompositeLocation>();
+ this.md2ReturnLocGen = new Hashtable<MethodDescriptor, ReturnLocGenerator>();
}
public void init() {
checkDeclarationInClass(cd);
for (Iterator method_it = cd.getMethods(); method_it.hasNext();) {
MethodDescriptor md = (MethodDescriptor) method_it.next();
- try {
+ if (ssjava.needTobeAnnotated(md)) {
checkDeclarationInMethodBody(cd, md);
- } catch (Error e) {
- System.out.println("Error in " + md);
- throw e;
}
}
}
checkClass(cd);
for (Iterator method_it = cd.getMethods(); method_it.hasNext();) {
MethodDescriptor md = (MethodDescriptor) method_it.next();
- try {
+ if (ssjava.needTobeAnnotated(md)) {
checkMethodBody(cd, md);
- } catch (Error e) {
- System.out.println("Error in " + md);
- throw e;
}
}
}
SSJavaLattice<String> superLattice = ssjava.getClassLattice(superCd);
SSJavaLattice<String> subLattice = ssjava.getClassLattice(cd);
- Set<Pair<String, String>> superPairSet = superLattice.getOrderingPairSet();
- Set<Pair<String, String>> subPairSet = subLattice.getOrderingPairSet();
+ if (superLattice != null) {
+
+ if (subLattice == null) {
+ throw new Error("If a parent class '" + superCd
+ + "' has a ordering lattice, its subclass '" + cd + "' should have one.");
+ }
+
+ Set<Pair<String, String>> superPairSet = superLattice.getOrderingPairSet();
+ Set<Pair<String, String>> subPairSet = subLattice.getOrderingPairSet();
- for (Iterator iterator = superPairSet.iterator(); iterator.hasNext();) {
- Pair<String, String> pair = (Pair<String, String>) iterator.next();
+ for (Iterator iterator = superPairSet.iterator(); iterator.hasNext();) {
+ Pair<String, String> pair = (Pair<String, String>) iterator.next();
- if (!subPairSet.contains(pair)) {
- throw new Error("Subclass '" + cd + "' does not have the relative ordering '"
- + pair.getSecond() + " < " + pair.getFirst() + "' that is defined by its superclass '"
- + superCd + "'.");
+ if (!subPairSet.contains(pair)) {
+ throw new Error("Subclass '" + cd + "' does not have the relative ordering '"
+ + pair.getSecond() + " < " + pair.getFirst()
+ + "' that is defined by its superclass '" + superCd + "'.");
+ }
}
+
}
+ // if super class doesn't define lattice, then we don't need to check its
+ // subclass
}
private void checkDeclarationInMethodBody(ClassDescriptor cd, MethodDescriptor md) {
BlockNode bn = state.getMethodBody(md);
+
+ // parsing returnloc annotation
+ if (ssjava.needTobeAnnotated(md)) {
+
+ Vector<AnnotationDescriptor> methodAnnotations = md.getModifiers().getAnnotations();
+ if (methodAnnotations != null) {
+ for (int i = 0; i < methodAnnotations.size(); i++) {
+ AnnotationDescriptor an = methodAnnotations.elementAt(i);
+ if (an.getMarker().equals(ssjava.RETURNLOC)) {
+ // developer explicitly defines method lattice
+ String returnLocDeclaration = an.getValue();
+ CompositeLocation returnLocComp =
+ parseLocationDeclaration(md, null, returnLocDeclaration);
+ md2ReturnLoc.put(md, returnLocComp);
+ }
+ }
+
+ if (!md.getReturnType().isVoid() && !md2ReturnLoc.containsKey(md)) {
+ throw new Error("Return location is not specified for the method " + md + " at "
+ + cd.getSourceFileName());
+ }
+
+ }
+ }
+
+ List<CompositeLocation> paramList = new ArrayList<CompositeLocation>();
+
+ boolean hasReturnValue = (!md.getReturnType().isVoid());
+ if (hasReturnValue) {
+ MethodLattice<String> methodLattice = ssjava.getMethodLattice(md);
+ String thisLocId = methodLattice.getThisLoc();
+ CompositeLocation thisLoc = new CompositeLocation(new Location(md, thisLocId));
+ paramList.add(thisLoc);
+ }
+
for (int i = 0; i < md.numParameters(); i++) {
// process annotations on method parameters
VarDescriptor vd = (VarDescriptor) md.getParameter(i);
assignLocationOfVarDescriptor(vd, md, md.getParameterTable(), bn);
+ if (hasReturnValue) {
+ paramList.add(d2loc.get(vd));
+ }
+ }
+
+ if (hasReturnValue) {
+ md2ReturnLocGen.put(md, new ReturnLocGenerator(md2ReturnLoc.get(md), paramList));
}
+
checkDeclarationInBlockNode(md, md.getParameterTable(), bn);
}
bn.getVarTable().setParent(nametable);
// it will return the lowest location in the block node
CompositeLocation lowestLoc = null;
+
for (int i = 0; i < bn.size(); i++) {
BlockStatementNode bsn = bn.get(i);
CompositeLocation bLoc = checkLocationFromBlockStatementNode(md, bn.getVarTable(), bsn);
- if (lowestLoc == null) {
- lowestLoc = bLoc;
- } else {
- if (!bLoc.isEmpty()) {
+ if (!bLoc.isEmpty()) {
+ if (lowestLoc == null) {
+ lowestLoc = bLoc;
+ } else {
if (CompositeLattice.isGreaterThan(lowestLoc, bLoc)) {
lowestLoc = bLoc;
}
}
}
+
+ }
+
+ if (lowestLoc == null) {
+ lowestLoc = new CompositeLocation(Location.createBottomLocation(md));
}
+
return lowestLoc;
}
compLoc = checkLocationFromSubBlockNode(md, nametable, (SubBlockNode) bsn);
break;
- // case Kind.ContinueBreakNode:
- // checkLocationFromContinueBreakNode(md, nametable,(ContinueBreakNode)
- // bsn);
- // return null;
+ case Kind.ContinueBreakNode:
+ compLoc = new CompositeLocation();
+ break;
+
}
return compLoc;
}
ExpressionNode returnExp = rn.getReturnExpression();
- CompositeLocation expLoc =
- checkLocationFromExpressionNode(md, nametable, returnExp, new CompositeLocation());
-
- // callee should have a relative ordering in-between parameters and return
- // value, which is required by caller's constraint
- for (int i = 0; i < md.numParameters(); i++) {
- Descriptor calleevd = md.getParameter(i);
- CompositeLocation calleeParamLoc = d2loc.get(calleevd);
+ CompositeLocation expLoc;
+ if (returnExp != null) {
+ expLoc = checkLocationFromExpressionNode(md, nametable, returnExp, new CompositeLocation());
+ // check if return value is equal or higher than RETRUNLOC of method
+ // declaration annotation
+ CompositeLocation returnLocAt = md2ReturnLoc.get(md);
- // here, parameter(input value) should be higher than result(output)
- if ((!expLoc.get(0).isTop()) && !CompositeLattice.isGreaterThan(calleeParamLoc, expLoc)) {
- throw new Error("Callee " + md + " doesn't have the ordering relation between parameter '"
- + calleevd + "' and its return value '" + returnExp.printNode(0) + "'.");
+ if (CompositeLattice.isGreaterThan(returnLocAt, expLoc)) {
+ throw new Error(
+ "Return value location is not equal or higher than the declaraed return location at "
+ + md.getClassDesc().getSourceFileName() + "::" + rn.getNumLine());
}
}
- // by default, return node has "bottom" location
- CompositeLocation loc = new CompositeLocation();
- loc.addLocation(Location.createBottomLocation(md));
- return loc;
+ return new CompositeLocation();
}
private boolean hasOnlyLiteralValue(ExpressionNode en) {
CompositeLocation condLoc =
checkLocationFromExpressionNode(md, nametable, ln.getCondition(), new CompositeLocation());
- addTypeLocation(ln.getCondition().getType(), (condLoc));
+ addLocationType(ln.getCondition().getType(), (condLoc));
CompositeLocation bodyLoc = checkLocationFromBlockNode(md, nametable, ln.getBody());
CompositeLocation condLoc =
checkLocationFromExpressionNode(md, bn.getVarTable(), ln.getCondition(),
new CompositeLocation());
- addTypeLocation(ln.getCondition().getType(), condLoc);
+ addLocationType(ln.getCondition().getType(), condLoc);
CompositeLocation updateLoc =
checkLocationFromBlockNode(md, bn.getVarTable(), ln.getUpdate());
Set<CompositeLocation> glbInputSet = new HashSet<CompositeLocation>();
glbInputSet.add(condLoc);
- glbInputSet.add(updateLoc);
+ // glbInputSet.add(updateLoc);
CompositeLocation glbLocOfForLoopCond = CompositeLattice.calculateGLB(glbInputSet);
// check location of 'forloop' body
CompositeLocation blockLoc = checkLocationFromBlockNode(md, bn.getVarTable(), ln.getBody());
+ // compute glb of body including loop body and update statement
+ glbInputSet.clear();
+
if (blockLoc == null) {
// when there is no statement in the loop body
- return glbLocOfForLoopCond;
+
+ if (updateLoc == null) {
+ // also there is no update statement in the loop body
+ return glbLocOfForLoopCond;
+ }
+ glbInputSet.add(updateLoc);
+
+ } else {
+ glbInputSet.add(blockLoc);
+ glbInputSet.add(updateLoc);
}
- if (!CompositeLattice.isGreaterThan(glbLocOfForLoopCond, blockLoc)) {
+ CompositeLocation loopBodyLoc = CompositeLattice.calculateGLB(glbInputSet);
+
+ if (!CompositeLattice.isGreaterThan(glbLocOfForLoopCond, loopBodyLoc)) {
throw new Error(
"The location of the for-condition statement is lower than the for-loop body at "
+ cd.getSourceFileName() + ":" + ln.getCondition().getNumLine());
CompositeLocation condLoc =
checkLocationFromExpressionNode(md, nametable, isn.getCondition(), new CompositeLocation());
- addTypeLocation(isn.getCondition().getType(), condLoc);
+ addLocationType(isn.getCondition().getType(), condLoc);
glbInputSet.add(condLoc);
CompositeLocation locTrueBlock = checkLocationFromBlockNode(md, nametable, isn.getTrueBlock());
} else {
- // if (destLoc instanceof Location) {
- // CompositeLocation comp = new CompositeLocation();
- // comp.addLocation(destLoc);
- // return comp;
- // } else {
- // return (CompositeLocation) destLoc;
- // }
- return destLoc;
+ return new CompositeLocation();
}
CompositeLocation condLoc =
checkLocationFromExpressionNode(md, nametable, tn.getCond(), new CompositeLocation());
- addTypeLocation(tn.getCond().getType(), condLoc);
+ addLocationType(tn.getCond().getType(), condLoc);
CompositeLocation trueLoc =
checkLocationFromExpressionNode(md, nametable, tn.getTrueExpr(), new CompositeLocation());
- addTypeLocation(tn.getTrueExpr().getType(), trueLoc);
+ addLocationType(tn.getTrueExpr().getType(), trueLoc);
CompositeLocation falseLoc =
checkLocationFromExpressionNode(md, nametable, tn.getFalseExpr(), new CompositeLocation());
- addTypeLocation(tn.getFalseExpr().getType(), falseLoc);
+ addLocationType(tn.getFalseExpr().getType(), falseLoc);
// check if condLoc is higher than trueLoc & falseLoc
if (!CompositeLattice.isGreaterThan(condLoc, trueLoc)) {
checkCalleeConstraints(md, nametable, min);
- // all we need to care about is that
- // method output(return value) should be lower than input values(method
- // parameters)
- Set<CompositeLocation> inputGLBSet = new HashSet<CompositeLocation>();
+ CompositeLocation baseLocation = null;
+ if (min.getExpression() != null) {
+ baseLocation =
+ checkLocationFromExpressionNode(md, nametable, min.getExpression(),
+ new CompositeLocation());
+ } else {
+ String thisLocId = ssjava.getMethodLattice(md).getThisLoc();
+ baseLocation = new CompositeLocation(new Location(md, thisLocId));
+ }
+
+ if (!min.getMethod().getReturnType().isVoid()) {
+ // If method has a return value, compute the highest possible return
+ // location in the caller's perspective
+ CompositeLocation ceilingLoc =
+ computeCeilingLocationForCaller(md, nametable, min, baseLocation);
+ return ceilingLoc;
+ }
+
+ return new CompositeLocation();
+
+ }
+
+ private CompositeLocation computeCeilingLocationForCaller(MethodDescriptor md,
+ SymbolTable nametable, MethodInvokeNode min, CompositeLocation baseLocation) {
+ List<CompositeLocation> argList = new ArrayList<CompositeLocation>();
+
+ // by default, method has a THIS parameter
+ argList.add(baseLocation);
+
for (int i = 0; i < min.numArgs(); i++) {
ExpressionNode en = min.getArg(i);
CompositeLocation callerArg =
checkLocationFromExpressionNode(md, nametable, en, new CompositeLocation());
- inputGLBSet.add(callerArg);
+ argList.add(callerArg);
}
- if (inputGLBSet.size() > 0) {
- return CompositeLattice.calculateGLB(inputGLBSet);
- } else {
- // if there are no arguments, just return TOP location
- CompositeLocation compLoc = new CompositeLocation();
- compLoc.addLocation(Location.createTopLocation(md));
- return compLoc;
- }
+ return md2ReturnLocGen.get(min.getMethod()).computeReturnLocation(argList);
}
VarDescriptor calleevd2 = (VarDescriptor) min.getMethod().getParameter(currentIdx);
CompositeLocation calleeLoc2 = d2loc.get(calleevd2);
- boolean callerResult = CompositeLattice.isGreaterThan(callerArg1, callerArg2);
- boolean calleeResult = CompositeLattice.isGreaterThan(calleeLoc1, calleeLoc2);
-
- if (calleeResult && !callerResult) {
+ int callerResult = CompositeLattice.compare(callerArg1, callerArg2);
+ int calleeResult = CompositeLattice.compare(calleeLoc1, calleeLoc2);
+ if (calleeResult == ComparisonResult.GREATER
+ && callerResult != ComparisonResult.GREATER) {
// If calleeLoc1 is higher than calleeLoc2
// then, caller should have same ordering relation in-bet
// callerLoc1 & callerLoc2
CompositeLocation argLoc =
checkLocationFromExpressionNode(md, nametable, en, new CompositeLocation());
glbInputSet.add(argLoc);
- addTypeLocation(en.getType(), argLoc);
+ addLocationType(en.getType(), argLoc);
}
// check array initializers
ExpressionNode left = fan.getExpression();
loc = checkLocationFromExpressionNode(md, nametable, left, loc);
- // addTypeLocation(left.getType(), loc);
if (!left.getType().isPrimitive()) {
FieldDescriptor fd = fan.getField();
ClassDescriptor cd = md.getClassDesc();
Vector<AnnotationDescriptor> annotationVec = vd.getType().getAnnotationMarkers();
- // currently enforce every variable to have corresponding location
- if (annotationVec.size() == 0) {
- throw new Error("Location is not assigned to variable " + vd.getSymbol() + " in the method "
- + md.getSymbol() + " of the class " + cd.getSymbol());
- }
+ if (!md.getModifiers().isAbstract()) {
+ // currently enforce every variable to have corresponding location
+ if (annotationVec.size() == 0) {
+ throw new Error("Location is not assigned to variable " + vd.getSymbol()
+ + " in the method " + md.getSymbol() + " of the class " + cd.getSymbol());
+ }
- if (annotationVec.size() > 1) { // variable can have at most one location
- throw new Error(vd.getSymbol() + " has more than one location.");
- }
+ if (annotationVec.size() > 1) { // variable can have at most one location
+ throw new Error(vd.getSymbol() + " has more than one location.");
+ }
- AnnotationDescriptor ad = annotationVec.elementAt(0);
+ AnnotationDescriptor ad = annotationVec.elementAt(0);
- if (ad.getType() == AnnotationDescriptor.SINGLE_ANNOTATION) {
+ if (ad.getType() == AnnotationDescriptor.SINGLE_ANNOTATION) {
- if (ad.getMarker().equals(SSJavaAnalysis.LOC)) {
- String locDec = ad.getValue(); // check if location is defined
+ if (ad.getMarker().equals(SSJavaAnalysis.LOC)) {
+ String locDec = ad.getValue(); // check if location is defined
- if (locDec.startsWith(SSJavaAnalysis.DELTA)) {
- DeltaLocation deltaLoc = parseDeltaDeclaration(md, n, locDec);
- d2loc.put(vd, deltaLoc);
- addTypeLocation(vd.getType(), deltaLoc);
- } else {
- CompositeLocation compLoc = parseLocationDeclaration(md, n, locDec);
- d2loc.put(vd, compLoc);
- addTypeLocation(vd.getType(), compLoc);
- }
+ if (locDec.startsWith(SSJavaAnalysis.DELTA)) {
+ DeltaLocation deltaLoc = parseDeltaDeclaration(md, n, locDec);
+ d2loc.put(vd, deltaLoc);
+ addLocationType(vd.getType(), deltaLoc);
+ } else {
+ CompositeLocation compLoc = parseLocationDeclaration(md, n, locDec);
+ Location lastElement = compLoc.get(compLoc.getSize() - 1);
+ if (ssjava.isSharedLocation(lastElement)) {
+ ssjava.mapSharedLocation2Descriptor(lastElement, vd);
+ }
+
+ d2loc.put(vd, compLoc);
+ addLocationType(vd.getType(), compLoc);
+ }
+
+ }
}
}
if (localLattice == null || (!localLattice.containsKey(localLocId))) {
throw new Error("Location " + localLocId
+ " is not defined in the local variable lattice at "
- + md.getClassDesc().getSourceFileName() + "::" + n.getNumLine() + ".");
+ + md.getClassDesc().getSourceFileName() + "::" + (n != null ? n.getNumLine() : "") + ".");
}
compLoc.addLocation(localLoc);
// Check to see that fields are okay
for (Iterator field_it = cd.getFields(); field_it.hasNext();) {
FieldDescriptor fd = (FieldDescriptor) field_it.next();
- checkFieldDeclaration(cd, fd);
+
+ if (!(fd.isFinal() && fd.isStatic())) {
+ checkFieldDeclaration(cd, fd);
+ }
}
}
// currently enforce every field to have corresponding location
if (annotationVec.size() == 0) {
- throw new Error("Location is not assigned to the field " + fd.getSymbol() + " of the class "
- + cd.getSymbol());
+ throw new Error("Location is not assigned to the field '" + fd.getSymbol()
+ + "' of the class " + cd.getSymbol() + " at " + cd.getSourceFileName());
}
if (annotationVec.size() > 1) {
+ cd.getSourceFileName() + ".");
}
Location loc = new Location(cd, locationID);
- // d2loc.put(fd, loc);
- addTypeLocation(fd.getType(), loc);
+
+ if (ssjava.isSharedLocation(loc)) {
+ ssjava.mapSharedLocation2Descriptor(loc, fd);
+ }
+
+ addLocationType(fd.getType(), loc);
}
}
}
- private void addTypeLocation(TypeDescriptor type, CompositeLocation loc) {
+ private void addLocationType(TypeDescriptor type, CompositeLocation loc) {
if (type != null) {
type.setExtension(loc);
}
}
- private void addTypeLocation(TypeDescriptor type, Location loc) {
+ private void addLocationType(TypeDescriptor type, Location loc) {
if (type != null) {
type.setExtension(loc);
}
public static boolean isGreaterThan(CompositeLocation loc1, CompositeLocation loc2) {
- // System.out.println("isGreaterThan= " + loc1 + " " + loc2);
-
- int baseCompareResult = compareBaseLocationSet(loc1, loc2);
+ int baseCompareResult = compareBaseLocationSet(loc1, loc2, true);
if (baseCompareResult == ComparisonResult.EQUAL) {
if (compareDelta(loc1, loc2) == ComparisonResult.GREATER) {
return true;
}
+ public static int compare(CompositeLocation loc1, CompositeLocation loc2) {
+
+ // System.out.println("compare=" + loc1 + " " + loc2);
+ int baseCompareResult = compareBaseLocationSet(loc1, loc2, false);
+
+ if (baseCompareResult == ComparisonResult.EQUAL) {
+ return compareDelta(loc1, loc2);
+ } else {
+ return baseCompareResult;
+ }
+
+ }
+
private static int compareDelta(CompositeLocation dLoc1, CompositeLocation dLoc2) {
int deltaCount1 = 0;
}
- private static int compareBaseLocationSet(CompositeLocation compLoc1, CompositeLocation compLoc2) {
+ private static int compareBaseLocationSet(CompositeLocation compLoc1,
+ CompositeLocation compLoc2, boolean awareSharedLoc) {
// if compLoc1 is greater than compLoc2, return true
// else return false;
// check if the current location is the spinning location
// note that the spinning location only can be appeared in the last
// part of the composite location
- if (numOfTie == compLoc1.getSize()
+ if (awareSharedLoc && numOfTie == compLoc1.getSize()
&& lattice1.getSpinLocSet().contains(loc1.getLocIdentifier())) {
return ComparisonResult.GREATER;
}
// mapping from the priority loc ID to its full representation by the
// composite location
+ int maxTupleSize = 0;
+ CompositeLocation maxCompLoc = null;
+
for (Iterator iterator = inputSet.iterator(); iterator.hasNext();) {
CompositeLocation compLoc = (CompositeLocation) iterator.next();
+ if (compLoc.getSize() > maxTupleSize) {
+ maxTupleSize = compLoc.getSize();
+ maxCompLoc = compLoc;
+ }
Location priorityLoc = compLoc.get(0);
String priorityLocId = priorityLoc.getLocIdentifier();
priorityLocIdentifierSet.add(priorityLocId);
- if (locId2CompLocSet.contains(priorityLocId)) {
+ if (locId2CompLocSet.containsKey(priorityLocId)) {
locId2CompLocSet.get(priorityLocId).add(compLoc);
} else {
Set<CompositeLocation> newSet = new HashSet<CompositeLocation>();
glbCompLoc.addLocation(new Location(priorityDescriptor, glbOfPriorityLoc));
Set<CompositeLocation> compSet = locId2CompLocSet.get(glbOfPriorityLoc);
+ // here find out composite location that has a maximum length tuple
+ // if we have three input set: [A], [A,B], [A,B,C]
+ // maximum length tuple will be [A,B,C]
+ int max = 0;
+ CompositeLocation maxFromCompSet = null;
+ for (Iterator iterator = compSet.iterator(); iterator.hasNext();) {
+ CompositeLocation c = (CompositeLocation) iterator.next();
+ if (c.getSize() > max) {
+ max = c.getSize();
+ maxFromCompSet = c;
+ }
+ }
+
if (compSet == null) {
// when GLB(x1,x2)!=x1 and !=x2 : GLB case 4
// mean that the result is already lower than <x1,y1> and <x2,y2>
// assign TOP to the rest of the location elements
- CompositeLocation inputComp = inputSet.iterator().next();
+
+ // in this case, do not take care about delta
+ // CompositeLocation inputComp = inputSet.iterator().next();
+ CompositeLocation inputComp = maxCompLoc;
for (int i = 1; i < inputComp.getSize(); i++) {
glbCompLoc.addLocation(Location.createTopLocation(inputComp.get(i).getDescriptor()));
}
} else {
if (compSet.size() == 1) {
+
// if GLB(x1,x2)==x1 or x2 : GLB case 2,3
CompositeLocation comp = compSet.iterator().next();
for (int i = 1; i < comp.getSize(); i++) {
glbCompLoc.addLocation(comp.get(i));
}
+
+ // if input location corresponding to glb is a delta, need to apply
+ // delta to glb result
+ if (comp instanceof DeltaLocation) {
+ glbCompLoc = new DeltaLocation(glbCompLoc, 1);
+ }
+
} else {
// when GLB(x1,x2)==x1 and x2 : GLB case 1
// if more than one location shares the same priority GLB
// need to calculate the rest of GLB loc
- int compositeLocSize = compSet.iterator().next().getSize();
+ // int compositeLocSize = compSet.iterator().next().getSize();
+ int compositeLocSize = maxFromCompSet.getSize();
Set<String> glbInputSet = new HashSet<String>();
Descriptor currentD = null;
for (int i = 1; i < compositeLocSize; i++) {
for (Iterator iterator = compSet.iterator(); iterator.hasNext();) {
CompositeLocation compositeLocation = (CompositeLocation) iterator.next();
- Location currentLoc = compositeLocation.get(i);
- currentD = currentLoc.getDescriptor();
- // making set of the current location sharing the same idx
- glbInputSet.add(currentLoc.getLocIdentifier());
+ if (compositeLocation.getSize() > i) {
+ Location currentLoc = compositeLocation.get(i);
+ currentD = currentLoc.getDescriptor();
+ // making set of the current location sharing the same idx
+ glbInputSet.add(currentLoc.getLocIdentifier());
+ }
}
// calculate glb for the current lattice
glbCompLoc.addLocation(new Location(currentD, currentGLBLocId));
}
+ // if input location corresponding to glb is a delta, need to apply
+ // delta to glb result
+
+ for (Iterator iterator = compSet.iterator(); iterator.hasNext();) {
+ CompositeLocation compLoc = (CompositeLocation) iterator.next();
+ if (compLoc instanceof DeltaLocation) {
+ if (glbCompLoc.equals(compLoc)) {
+ glbCompLoc = new DeltaLocation(glbCompLoc, 1);
+ break;
+ }
+ }
+ }
+
}
}
public static final int GREATER = 0;
public static final int EQUAL = 1;
public static final int LESS = 2;
+ public static final int INCOMPARABLE = 3;
int result;
}
}
+
+class ReturnLocGenerator {
+
+ public static final int PARAMISHIGHER = 0;
+ public static final int PARAMISSAME = 1;
+ public static final int IGNORE = 2;
+
+ Hashtable<Integer, Integer> paramIdx2paramType;
+
+ public ReturnLocGenerator(CompositeLocation returnLoc, List<CompositeLocation> params) {
+ // creating mappings
+
+ paramIdx2paramType = new Hashtable<Integer, Integer>();
+ for (int i = 0; i < params.size(); i++) {
+ CompositeLocation param = params.get(i);
+ int compareResult = CompositeLattice.compare(param, returnLoc);
+
+ int type;
+ if (compareResult == ComparisonResult.GREATER) {
+ type = 0;
+ } else if (compareResult == ComparisonResult.EQUAL) {
+ type = 1;
+ } else {
+ type = 2;
+ }
+ paramIdx2paramType.put(new Integer(i), new Integer(type));
+ }
+
+ }
+
+ public CompositeLocation computeReturnLocation(List<CompositeLocation> args) {
+
+ // compute the highest possible location in caller's side
+ assert paramIdx2paramType.keySet().size() == args.size();
+
+ Set<CompositeLocation> inputGLB = new HashSet<CompositeLocation>();
+ for (int i = 0; i < args.size(); i++) {
+ int type = (paramIdx2paramType.get(new Integer(i))).intValue();
+ CompositeLocation argLoc = args.get(i);
+ if (type == PARAMISHIGHER) {
+ // return loc is lower than param
+ DeltaLocation delta = new DeltaLocation(argLoc, 1);
+ inputGLB.add(delta);
+ } else if (type == PARAMISSAME) {
+ // return loc is equal or lower than param
+ inputGLB.add(argLoc);
+ }
+ }
+
+ // compute GLB of arguments subset that are same or higher than return
+ // location
+ CompositeLocation glb = CompositeLattice.calculateGLB(inputGLB);
+ return glb;
+ }
+}