0001: /* Soot - a J*va Optimization Framework
0002: * Copyright (C) 2007 Manu Sridharan
0003: *
0004: * This library is free software; you can redistribute it and/or
0005: * modify it under the terms of the GNU Lesser General Public
0006: * License as published by the Free Software Foundation; either
0007: * version 2.1 of the License, or (at your option) any later version.
0008: *
0009: * This library is distributed in the hope that it will be useful,
0010: * but WITHOUT ANY WARRANTY; without even the implied warranty of
0011: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
0012: * Lesser General Public License for more details.
0013: *
0014: * You should have received a copy of the GNU Lesser General Public
0015: * License along with this library; if not, write to the
0016: * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
0017: * Boston, MA 02111-1307, USA.
0018: */
0019: package soot.jimple.spark.ondemand;
0020:
0021: import java.util.ArrayList;
0022: import java.util.Arrays;
0023: import java.util.Collection;
0024: import java.util.Collections;
0025: import java.util.HashMap;
0026: import java.util.HashSet;
0027: import java.util.List;
0028: import java.util.Map;
0029: import java.util.Set;
0030:
0031: import soot.AnySubType;
0032: import soot.ArrayType;
0033: import soot.Context;
0034: import soot.G;
0035: import soot.Local;
0036: import soot.PointsToAnalysis;
0037: import soot.PointsToSet;
0038: import soot.RefType;
0039: import soot.Scene;
0040: import soot.SootField;
0041: import soot.SootMethod;
0042: import soot.Type;
0043: import soot.jimple.spark.ondemand.genericutil.ArraySet;
0044: import soot.jimple.spark.ondemand.genericutil.HashSetMultiMap;
0045: import soot.jimple.spark.ondemand.genericutil.ImmutableStack;
0046: import soot.jimple.spark.ondemand.genericutil.Predicate;
0047: import soot.jimple.spark.ondemand.genericutil.Propagator;
0048: import soot.jimple.spark.ondemand.genericutil.Stack;
0049: import soot.jimple.spark.ondemand.pautil.AssignEdge;
0050: import soot.jimple.spark.ondemand.pautil.ContextSensitiveInfo;
0051: import soot.jimple.spark.ondemand.pautil.OTFMethodSCCManager;
0052: import soot.jimple.spark.ondemand.pautil.SootUtil;
0053: import soot.jimple.spark.ondemand.pautil.ValidMatches;
0054: import soot.jimple.spark.ondemand.pautil.SootUtil.FieldToEdgesMap;
0055: import soot.jimple.spark.pag.AllocNode;
0056: import soot.jimple.spark.pag.FieldRefNode;
0057: import soot.jimple.spark.pag.GlobalVarNode;
0058: import soot.jimple.spark.pag.LocalVarNode;
0059: import soot.jimple.spark.pag.Node;
0060: import soot.jimple.spark.pag.PAG;
0061: import soot.jimple.spark.pag.SparkField;
0062: import soot.jimple.spark.pag.VarNode;
0063: import soot.jimple.spark.sets.EmptyPointsToSet;
0064: import soot.jimple.spark.sets.EqualsSupportingPointsToSet;
0065: import soot.jimple.spark.sets.HybridPointsToSet;
0066: import soot.jimple.spark.sets.P2SetVisitor;
0067: import soot.jimple.spark.sets.PointsToSetEqualsWrapper;
0068: import soot.jimple.spark.sets.PointsToSetInternal;
0069: import soot.jimple.toolkits.callgraph.VirtualCalls;
0070: import soot.toolkits.scalar.Pair;
0071: import soot.util.NumberedString;
0072:
0073: /**
0074: * Tries to find imprecision in points-to sets from a previously run analysis.
0075: * Requires that all sub-results of previous analysis were cached.
0076: *
0077: * @author Manu Sridharan
0078: *
0079: */
0080: public final class DemandCSPointsTo implements PointsToAnalysis {
0081:
0082: @SuppressWarnings("serial")
0083: protected static final class AllocAndContextCache extends
0084: HashMap<AllocAndContext, Map<VarNode, CallingContextSet>> {
0085: }
0086:
0087: protected static final class CallingContextSet extends
0088: ArraySet<ImmutableStack<Integer>> {
0089: }
0090:
0091: protected final static class CallSiteAndContext extends
0092: Pair<Integer, ImmutableStack<Integer>> {
0093:
0094: public CallSiteAndContext(Integer callSite,
0095: ImmutableStack<Integer> callingContext) {
0096: super (callSite, callingContext);
0097: }
0098: }
0099:
0100: protected static final class CallSiteToTargetsMap extends
0101: HashSetMultiMap<CallSiteAndContext, SootMethod> {
0102: }
0103:
0104: protected static abstract class IncomingEdgeHandler {
0105:
0106: public abstract void handleAlloc(AllocNode allocNode,
0107: VarAndContext origVarAndContext);
0108:
0109: public abstract void handleMatchSrc(VarNode matchSrc,
0110: PointsToSetInternal intersection, VarNode loadBase,
0111: VarNode storeBase, VarAndContext origVarAndContext,
0112: SparkField field, boolean refine);
0113:
0114: abstract Object getResult();
0115:
0116: abstract void handleAssignSrc(VarAndContext newVarAndContext,
0117: VarAndContext origVarAndContext, AssignEdge assignEdge);
0118:
0119: abstract boolean shouldHandleSrc(VarNode src);
0120:
0121: boolean terminate() {
0122: return false;
0123: }
0124:
0125: }
0126:
0127: protected static class VarAndContext {
0128:
0129: final ImmutableStack<Integer> context;
0130:
0131: final VarNode var;
0132:
0133: public VarAndContext(VarNode var,
0134: ImmutableStack<Integer> context) {
0135: assert var != null;
0136: assert context != null;
0137: this .var = var;
0138: this .context = context;
0139: }
0140:
0141: public boolean equals(Object o) {
0142: if (o != null && o.getClass() == VarAndContext.class) {
0143: VarAndContext other = (VarAndContext) o;
0144: return var.equals(other.var)
0145: && context.equals(other.context);
0146: }
0147: return false;
0148: }
0149:
0150: public int hashCode() {
0151: return var.hashCode() + context.hashCode();
0152: }
0153:
0154: public String toString() {
0155: return var + " " + context;
0156: }
0157: }
0158:
0159: protected final static class VarContextAndUp extends VarAndContext {
0160:
0161: final ImmutableStack<Integer> upContext;
0162:
0163: public VarContextAndUp(VarNode var,
0164: ImmutableStack<Integer> context,
0165: ImmutableStack<Integer> upContext) {
0166: super (var, context);
0167: this .upContext = upContext;
0168: }
0169:
0170: public boolean equals(Object o) {
0171: if (o != null && o.getClass() == VarContextAndUp.class) {
0172: VarContextAndUp other = (VarContextAndUp) o;
0173: return var.equals(other.var)
0174: && context.equals(other.context)
0175: && upContext.equals(other.upContext);
0176: }
0177:
0178: return false;
0179: }
0180:
0181: public int hashCode() {
0182: return var.hashCode() + context.hashCode()
0183: + upContext.hashCode();
0184: }
0185:
0186: public String toString() {
0187: return var + " " + context + " up " + upContext;
0188: }
0189: }
0190:
0191: public static boolean DEBUG = false;
0192:
0193: protected static final int DEBUG_NESTING = 15;
0194:
0195: protected static final int DEBUG_PASS = -1;
0196:
0197: protected static final boolean DEBUG_VIRT = DEBUG && true;
0198:
0199: protected static final int DEFAULT_MAX_PASSES = 10;
0200:
0201: protected static final int DEFAULT_MAX_TRAVERSAL = 75000;
0202:
0203: /**
0204: * if <code>true</code>, refine the pre-computed call graph
0205: */
0206: private boolean refineCallGraph = true;
0207:
0208: protected static final ImmutableStack<Integer> EMPTY_CALLSTACK = ImmutableStack
0209: .<Integer> emptyStack();
0210:
0211: /**
0212: * Make a default analysis. Assumes Spark has already run.
0213: *
0214: * @return
0215: */
0216: public static DemandCSPointsTo makeDefault() {
0217: return makeWithBudget(DEFAULT_MAX_TRAVERSAL, DEFAULT_MAX_PASSES);
0218: }
0219:
0220: public static DemandCSPointsTo makeWithBudget(int maxTraversal,
0221: int maxPasses) {
0222: PAG pag = (PAG) Scene.v().getPointsToAnalysis();
0223: ContextSensitiveInfo csInfo = new ContextSensitiveInfo(pag);
0224: return new DemandCSPointsTo(csInfo, pag, maxTraversal,
0225: maxPasses);
0226: }
0227:
0228: protected final AllocAndContextCache allocAndContextCache = new AllocAndContextCache();
0229:
0230: protected Stack<Pair<Integer, ImmutableStack<Integer>>> callGraphStack = new Stack<Pair<Integer, ImmutableStack<Integer>>>();
0231:
0232: protected final CallSiteToTargetsMap callSiteToResolvedTargets = new CallSiteToTargetsMap();
0233:
0234: protected HashMap<List<Object>, Set<SootMethod>> callTargetsArgCache = new HashMap<List<Object>, Set<SootMethod>>();
0235:
0236: protected final Stack<VarAndContext> contextForAllocsStack = new Stack<VarAndContext>();
0237:
0238: protected Map<VarAndContext, Pair<PointsToSetInternal, AllocAndContextSet>> contextsForAllocsCache = new HashMap<VarAndContext, Pair<PointsToSetInternal, AllocAndContextSet>>();
0239:
0240: protected final ContextSensitiveInfo csInfo;
0241:
0242: /**
0243: * if <code>true</code>, compute full points-to set for queried
0244: * variable
0245: */
0246: protected boolean doPointsTo;
0247:
0248: protected FieldCheckHeuristic fieldCheckHeuristic;
0249:
0250: protected HeuristicType heuristicType;
0251:
0252: protected final FieldToEdgesMap fieldToLoads;
0253:
0254: protected final FieldToEdgesMap fieldToStores;
0255:
0256: protected final int maxNodesPerPass;
0257:
0258: protected final int maxPasses;
0259:
0260: protected int nesting = 0;
0261:
0262: protected int numNodesTraversed;
0263:
0264: protected int numPasses = 0;
0265:
0266: protected final PAG pag;
0267:
0268: protected AllocAndContextSet pointsTo = null;
0269:
0270: protected final Set<CallSiteAndContext> queriedCallSites = new HashSet<CallSiteAndContext>();
0271:
0272: protected int recursionDepth = -1;
0273:
0274: protected boolean refiningCallSite = false;
0275:
0276: protected OTFMethodSCCManager sccManager;
0277:
0278: protected Map<VarContextAndUp, Map<AllocAndContext, CallingContextSet>> upContextCache = new HashMap<VarContextAndUp, Map<AllocAndContext, CallingContextSet>>();
0279:
0280: protected final ValidMatches vMatches;
0281:
0282: protected Map<Local, PointsToSet> reachingObjectsCache,
0283: reachingObjectsCacheNoCGRefinement;
0284:
0285: protected boolean useCache;
0286:
0287: public DemandCSPointsTo(ContextSensitiveInfo csInfo, PAG pag) {
0288: this (csInfo, pag, DEFAULT_MAX_TRAVERSAL, DEFAULT_MAX_PASSES);
0289: }
0290:
0291: public DemandCSPointsTo(ContextSensitiveInfo csInfo, PAG pag,
0292: int maxTraversal, int maxPasses) {
0293: this .csInfo = csInfo;
0294: this .pag = pag;
0295: this .fieldToStores = SootUtil.storesOnField(pag);
0296: this .fieldToLoads = SootUtil.loadsOnField(pag);
0297: this .vMatches = new ValidMatches(pag, fieldToStores);
0298: this .maxPasses = maxPasses;
0299: this .maxNodesPerPass = maxTraversal / maxPasses;
0300: this .heuristicType = HeuristicType.INCR;
0301: this .reachingObjectsCache = new HashMap<Local, PointsToSet>();
0302: this .reachingObjectsCacheNoCGRefinement = new HashMap<Local, PointsToSet>();
0303: this .useCache = true;
0304: }
0305:
0306: /**
0307: * {@inheritDoc}
0308: */
0309: public PointsToSet reachingObjects(Local l) {
0310: PointsToSet result;
0311: Map<Local, PointsToSet> cache;
0312: if (refineCallGraph) { //we use different caches for different settings
0313: cache = reachingObjectsCache;
0314: } else {
0315: cache = reachingObjectsCacheNoCGRefinement;
0316: }
0317: result = cache.get(l);
0318: if (result == null) {
0319: result = computeReachingObjects(l);
0320: if (useCache) {
0321: cache.put(l, result);
0322: }
0323: }
0324: assert consistentResult(l, result);
0325: return result;
0326: }
0327:
0328: /**
0329: * Returns <code>false</code> if an inconsistent computation occurred, i.e. if result
0330: * differs from the result computed by {@link #computeReachingObjects(Local)} on l.
0331: */
0332: private boolean consistentResult(Local l, PointsToSet result) {
0333: PointsToSet result2 = computeReachingObjects(l);
0334: if (!(result instanceof EqualsSupportingPointsToSet)
0335: || !(result2 instanceof EqualsSupportingPointsToSet)) {
0336: //cannot compare, assume everything is fine
0337: return true;
0338: }
0339: EqualsSupportingPointsToSet eq1 = (EqualsSupportingPointsToSet) result;
0340: EqualsSupportingPointsToSet eq2 = (EqualsSupportingPointsToSet) result2;
0341: return new PointsToSetEqualsWrapper(eq1)
0342: .equals(new PointsToSetEqualsWrapper(eq2));
0343: }
0344:
0345: /**
0346: * Computes the possibly refined set of reaching objects for l.
0347: */
0348: protected PointsToSet computeReachingObjects(Local l) {
0349: VarNode v = pag.findLocalVarNode(l);
0350: if (v == null) {
0351: //no reaching objects
0352: return EmptyPointsToSet.v();
0353: }
0354: PointsToSet contextSensitiveResult = computeRefinedReachingObjects(v);
0355: if (contextSensitiveResult == null) {
0356: //had to abort; return Spark's points-to set in a wrapper
0357: return new WrappedPointsToSet(v.getP2Set());
0358: } else {
0359: return contextSensitiveResult;
0360: }
0361: }
0362:
0363: /**
0364: * Computes the refined set of reaching objects for l.
0365: * Returns <code>null</code> if refinement failed.
0366: */
0367: protected PointsToSet computeRefinedReachingObjects(VarNode v) {
0368: // must reset the refinement heuristic for each query
0369: this .fieldCheckHeuristic = HeuristicType.getHeuristic(
0370: heuristicType, pag.getTypeManager(), getMaxPasses());
0371: doPointsTo = true;
0372: numPasses = 0;
0373: PointsToSet contextSensitiveResult = null;
0374: while (true) {
0375: numPasses++;
0376: if (DEBUG_PASS != -1 && numPasses > DEBUG_PASS) {
0377: break;
0378: }
0379: if (numPasses > maxPasses) {
0380: break;
0381: }
0382: if (DEBUG) {
0383: G.v().out.println("PASS " + numPasses);
0384: G.v().out.println(fieldCheckHeuristic);
0385: }
0386: clearState();
0387: pointsTo = new AllocAndContextSet();
0388: try {
0389: refineP2Set(new VarAndContext(v, EMPTY_CALLSTACK), null);
0390: contextSensitiveResult = pointsTo;
0391: } catch (TerminateEarlyException e) {
0392: }
0393: if (!fieldCheckHeuristic.runNewPass()) {
0394: break;
0395: }
0396: }
0397: return contextSensitiveResult;
0398: }
0399:
0400: protected boolean callEdgeInSCC(AssignEdge assignEdge) {
0401: boolean sameSCCAlready = false;
0402: assert assignEdge.isCallEdge();
0403: // assert assignEdge.getSrc() instanceof LocalVarNode :
0404: // assignEdge.getSrc() + " not LocalVarNode";
0405: if (!(assignEdge.getSrc() instanceof LocalVarNode)
0406: || !(assignEdge.getDst() instanceof LocalVarNode)) {
0407: return false;
0408: }
0409: LocalVarNode src = (LocalVarNode) assignEdge.getSrc();
0410: LocalVarNode dst = (LocalVarNode) assignEdge.getDst();
0411: if (sccManager.inSameSCC(src.getMethod(), dst.getMethod())) {
0412: sameSCCAlready = true;
0413: }
0414: return sameSCCAlready;
0415: }
0416:
0417: protected CallingContextSet checkAllocAndContextCache(
0418: AllocAndContext allocAndContext, VarNode targetVar) {
0419: if (allocAndContextCache.containsKey(allocAndContext)) {
0420: Map<VarNode, CallingContextSet> m = allocAndContextCache
0421: .get(allocAndContext);
0422: if (m.containsKey(targetVar)) {
0423: return m.get(targetVar);
0424: }
0425: } else {
0426: allocAndContextCache.put(allocAndContext,
0427: new HashMap<VarNode, CallingContextSet>());
0428: }
0429: return null;
0430: }
0431:
0432: protected PointsToSetInternal checkContextsForAllocsCache(
0433: VarAndContext varAndContext, AllocAndContextSet ret,
0434: PointsToSetInternal locs) {
0435: PointsToSetInternal retSet = null;
0436: if (contextsForAllocsCache.containsKey(varAndContext)) {
0437: for (AllocAndContext allocAndContext : contextsForAllocsCache
0438: .get(varAndContext).getO2()) {
0439: if (locs.contains(allocAndContext.alloc)) {
0440: ret.add(allocAndContext);
0441: }
0442: }
0443: final PointsToSetInternal oldLocs = contextsForAllocsCache
0444: .get(varAndContext).getO1();
0445: final PointsToSetInternal tmpSet = new HybridPointsToSet(
0446: locs.getType(), pag);
0447: locs.forall(new P2SetVisitor() {
0448:
0449: @Override
0450: public void visit(Node n) {
0451: if (!oldLocs.contains(n)) {
0452: tmpSet.add(n);
0453: }
0454: }
0455: });
0456: retSet = tmpSet;
0457: oldLocs.addAll(tmpSet, null);
0458: } else {
0459: PointsToSetInternal storedSet = new HybridPointsToSet(locs
0460: .getType(), pag);
0461: storedSet.addAll(locs, null);
0462: contextsForAllocsCache.put(varAndContext,
0463: new Pair<PointsToSetInternal, AllocAndContextSet>(
0464: storedSet, new AllocAndContextSet()));
0465: retSet = locs;
0466: }
0467: return retSet;
0468: }
0469:
0470: /**
0471: * check the computed points-to set of a variable against some predicate
0472: *
0473: * @param v
0474: * the variable
0475: * @param heuristic
0476: * how to refine match edges
0477: * @param p2setPred
0478: * the predicate on the points-to set
0479: * @return true if the p2setPred holds for the computed points-to set, or if
0480: * a points-to set cannot be computed in the budget; false otherwise
0481: */
0482: protected boolean checkP2Set(VarNode v, HeuristicType heuristic,
0483: Predicate<Set<AllocAndContext>> p2setPred) {
0484: doPointsTo = true;
0485: // DEBUG = v.getNumber() == 150;
0486: this .fieldCheckHeuristic = HeuristicType.getHeuristic(
0487: heuristic, pag.getTypeManager(), getMaxPasses());
0488: numPasses = 0;
0489: while (true) {
0490: numPasses++;
0491: if (DEBUG_PASS != -1 && numPasses > DEBUG_PASS) {
0492: return true;
0493: }
0494: if (numPasses > maxPasses) {
0495: return true;
0496: }
0497: if (DEBUG) {
0498: G.v().out.println("PASS " + numPasses);
0499: G.v().out.println(fieldCheckHeuristic);
0500: }
0501: clearState();
0502: pointsTo = new AllocAndContextSet();
0503: boolean success = false;
0504: try {
0505: success = refineP2Set(new VarAndContext(v,
0506: EMPTY_CALLSTACK), null);
0507: } catch (TerminateEarlyException e) {
0508: success = false;
0509: }
0510: if (success) {
0511: if (p2setPred.test(pointsTo)) {
0512: return false;
0513: }
0514: } else {
0515: if (!fieldCheckHeuristic.runNewPass()) {
0516: return true;
0517: }
0518: }
0519: }
0520:
0521: }
0522:
0523: // protected boolean upContextsSane(CallingContextSet ret, AllocAndContext
0524: // allocAndContext, VarContextAndUp varContextAndUp) {
0525: // for (ImmutableStack<Integer> context : ret) {
0526: // ImmutableStack<Integer> fixedContext = fixUpContext(context,
0527: // allocAndContext, varContextAndUp);
0528: // if (!context.equals(fixedContext)) {
0529: // return false;
0530: // }
0531: // }
0532: // return true;
0533: // }
0534: //
0535: // protected CallingContextSet fixAllUpContexts(CallingContextSet contexts,
0536: // AllocAndContext allocAndContext, VarContextAndUp varContextAndUp) {
0537: // if (DEBUG) {
0538: // debugPrint("fixing up contexts");
0539: // }
0540: // CallingContextSet ret = new CallingContextSet();
0541: // for (ImmutableStack<Integer> context : contexts) {
0542: // ret.add(fixUpContext(context, allocAndContext, varContextAndUp));
0543: // }
0544: // return ret;
0545: // }
0546: //
0547: // protected ImmutableStack<Integer> fixUpContext(ImmutableStack<Integer>
0548: // context, AllocAndContext allocAndContext, VarContextAndUp
0549: // varContextAndUp) {
0550: //
0551: // return null;
0552: // }
0553:
0554: protected CallingContextSet checkUpContextCache(
0555: VarContextAndUp varContextAndUp,
0556: AllocAndContext allocAndContext) {
0557: if (upContextCache.containsKey(varContextAndUp)) {
0558: Map<AllocAndContext, CallingContextSet> allocAndContextMap = upContextCache
0559: .get(varContextAndUp);
0560: if (allocAndContextMap.containsKey(allocAndContext)) {
0561: return allocAndContextMap.get(allocAndContext);
0562: }
0563: } else {
0564: upContextCache.put(varContextAndUp,
0565: new HashMap<AllocAndContext, CallingContextSet>());
0566: }
0567: return null;
0568: }
0569:
0570: protected void clearState() {
0571: allocAndContextCache.clear();
0572: callGraphStack.clear();
0573: callSiteToResolvedTargets.clear();
0574: queriedCallSites.clear();
0575: contextsForAllocsCache.clear();
0576: contextForAllocsStack.clear();
0577: upContextCache.clear();
0578: callTargetsArgCache.clear();
0579: sccManager = new OTFMethodSCCManager();
0580: numNodesTraversed = 0;
0581: nesting = 0;
0582: recursionDepth = -1;
0583: }
0584:
0585: /**
0586: * compute a flows-to set for an allocation site. for now, we use a simple
0587: * refinement strategy; just refine as much as possible, maintaining the
0588: * smallest set of flows-to vars
0589: *
0590: * @param alloc
0591: * @param heuristic
0592: * @return
0593: */
0594: protected Set<VarNode> computeFlowsTo(AllocNode alloc,
0595: HeuristicType heuristic) {
0596: this .fieldCheckHeuristic = HeuristicType.getHeuristic(
0597: heuristic, pag.getTypeManager(), getMaxPasses());
0598: numPasses = 0;
0599: Set<VarNode> smallest = null;
0600: while (true) {
0601: numPasses++;
0602: if (DEBUG_PASS != -1 && numPasses > DEBUG_PASS) {
0603: return smallest;
0604: }
0605: if (numPasses > maxPasses) {
0606: return smallest;
0607: }
0608: if (DEBUG) {
0609: G.v().out.println("PASS " + numPasses);
0610: G.v().out.println(fieldCheckHeuristic);
0611: }
0612: clearState();
0613: Set<VarNode> result = null;
0614: try {
0615: result = getFlowsToHelper(new AllocAndContext(alloc,
0616: EMPTY_CALLSTACK));
0617: } catch (TerminateEarlyException e) {
0618:
0619: }
0620: if (result != null) {
0621: if (smallest == null || result.size() < smallest.size()) {
0622: smallest = result;
0623: }
0624: }
0625: if (!fieldCheckHeuristic.runNewPass()) {
0626: return smallest;
0627: }
0628: }
0629: }
0630:
0631: protected void debugPrint(String str) {
0632: if (nesting <= DEBUG_NESTING) {
0633: if (DEBUG_PASS == -1 || DEBUG_PASS == numPasses) {
0634: G.v().out.println(":" + nesting + " " + str);
0635: }
0636: }
0637: }
0638:
0639: /*
0640: * (non-Javadoc)
0641: *
0642: * @see AAA.summary.Refiner#dumpPathForBadLoc(soot.jimple.spark.pag.VarNode,
0643: * soot.jimple.spark.pag.AllocNode)
0644: */
0645: protected void dumpPathForLoc(VarNode v, final AllocNode badLoc,
0646: String filePrefix) {
0647: final HashSet<VarNode> visited = new HashSet<VarNode>();
0648: final DotPointerGraph dotGraph = new DotPointerGraph();
0649: final class Helper {
0650: boolean handle(VarNode curNode) {
0651: assert curNode.getP2Set().contains(badLoc);
0652: visited.add(curNode);
0653: Node[] newEdges = pag.allocInvLookup(curNode);
0654: for (int i = 0; i < newEdges.length; i++) {
0655: AllocNode alloc = (AllocNode) newEdges[i];
0656: if (alloc.equals(badLoc)) {
0657: dotGraph.addNew(alloc, curNode);
0658: return true;
0659: }
0660: }
0661: for (AssignEdge assignEdge : csInfo
0662: .getAssignEdges(curNode)) {
0663: VarNode other = assignEdge.getSrc();
0664: if (other.getP2Set().contains(badLoc)
0665: && !visited.contains(other)
0666: && handle(other)) {
0667: if (assignEdge.isCallEdge()) {
0668: dotGraph.addCall(other, curNode, assignEdge
0669: .getCallSite());
0670: } else {
0671: dotGraph.addAssign(other, curNode);
0672: }
0673: return true;
0674: }
0675: }
0676: Node[] loadEdges = pag.loadInvLookup(curNode);
0677: for (int i = 0; i < loadEdges.length; i++) {
0678: FieldRefNode frNode = (FieldRefNode) loadEdges[i];
0679: SparkField field = frNode.getField();
0680: VarNode base = frNode.getBase();
0681: PointsToSetInternal baseP2Set = base.getP2Set();
0682: for (Pair<VarNode, VarNode> store : fieldToStores
0683: .get(field)) {
0684: if (store.getO2().getP2Set()
0685: .hasNonEmptyIntersection(baseP2Set)) {
0686: VarNode matchSrc = store.getO1();
0687: if (matchSrc.getP2Set().contains(badLoc)
0688: && !visited.contains(matchSrc)
0689: && handle(matchSrc)) {
0690: dotGraph.addMatch(matchSrc, curNode);
0691: return true;
0692: }
0693: }
0694: }
0695: }
0696: return false;
0697: }
0698: }
0699: Helper h = new Helper();
0700: h.handle(v);
0701: // G.v().out.println(dotGraph.numEdges() + " edges on path");
0702: dotGraph.dump("tmp/" + filePrefix + v.getNumber() + "_"
0703: + badLoc.getNumber() + ".dot");
0704: }
0705:
0706: protected Collection<AssignEdge> filterAssigns(final VarNode v,
0707: final ImmutableStack<Integer> callingContext,
0708: boolean forward, boolean refineVirtCalls) {
0709: Set<AssignEdge> assigns = forward ? csInfo.getAssignEdges(v)
0710: : csInfo.getAssignBarEdges(v);
0711: Collection<AssignEdge> realAssigns;
0712: boolean exitNode = forward ? SootUtil.isParamNode(v) : SootUtil
0713: .isRetNode(v);
0714: final boolean backward = !forward;
0715: if (exitNode && !callingContext.isEmpty()) {
0716: Integer topCallSite = callingContext.peek();
0717: realAssigns = new ArrayList<AssignEdge>();
0718: for (AssignEdge assignEdge : assigns) {
0719: assert (forward && assignEdge.isParamEdge())
0720: || (backward && assignEdge.isReturnEdge()) : assignEdge;
0721:
0722: Integer assignEdgeCallSite = assignEdge.getCallSite();
0723: assert csInfo.getCallSiteTargets(assignEdgeCallSite)
0724: .contains(((LocalVarNode) v).getMethod()) : assignEdge;
0725: if (topCallSite.equals(assignEdgeCallSite)
0726: || callEdgeInSCC(assignEdge)) {
0727: realAssigns.add(assignEdge);
0728: }
0729: }
0730: // assert realAssigns.size() == 1;
0731: } else {
0732: if (assigns.size() > 1) {
0733: realAssigns = new ArrayList<AssignEdge>();
0734: for (AssignEdge assignEdge : assigns) {
0735: boolean enteringCall = forward ? assignEdge
0736: .isReturnEdge() : assignEdge.isParamEdge();
0737: if (enteringCall) {
0738: Integer callSite = assignEdge.getCallSite();
0739: if (csInfo.isVirtCall(callSite)
0740: && refineVirtCalls) {
0741: Set<SootMethod> targets = refineCallSite(
0742: assignEdge.getCallSite(),
0743: callingContext);
0744: LocalVarNode nodeInTargetMethod = forward ? (LocalVarNode) assignEdge
0745: .getSrc()
0746: : (LocalVarNode) assignEdge
0747: .getDst();
0748: if (targets.contains(nodeInTargetMethod
0749: .getMethod())) {
0750: realAssigns.add(assignEdge);
0751: }
0752: } else {
0753: realAssigns.add(assignEdge);
0754: }
0755: } else {
0756: realAssigns.add(assignEdge);
0757: }
0758: }
0759: } else {
0760: realAssigns = assigns;
0761: }
0762: }
0763: return realAssigns;
0764: }
0765:
0766: protected AllocAndContextSet findContextsForAllocs(
0767: final VarAndContext varAndContext, PointsToSetInternal locs) {
0768: if (contextForAllocsStack.contains(varAndContext)) {
0769: // recursion; check depth
0770: // we're fine for x = x.next
0771: int oldIndex = contextForAllocsStack.indexOf(varAndContext);
0772: if (oldIndex != contextForAllocsStack.size() - 1) {
0773: if (recursionDepth == -1) {
0774: recursionDepth = oldIndex + 1;
0775: if (DEBUG) {
0776: debugPrint("RECURSION depth = "
0777: + recursionDepth);
0778: }
0779: } else if (contextForAllocsStack.size() - oldIndex > 5) {
0780: // just give up
0781: throw new TerminateEarlyException();
0782: }
0783: }
0784: }
0785: contextForAllocsStack.push(varAndContext);
0786: final AllocAndContextSet ret = new AllocAndContextSet();
0787: final PointsToSetInternal realLocs = checkContextsForAllocsCache(
0788: varAndContext, ret, locs);
0789: if (realLocs.isEmpty()) {
0790: if (DEBUG) {
0791: debugPrint("cached result " + ret);
0792: }
0793: contextForAllocsStack.pop();
0794: return ret;
0795: }
0796: nesting++;
0797: if (DEBUG) {
0798: debugPrint("finding alloc contexts for " + varAndContext);
0799: }
0800: try {
0801: final Set<VarAndContext> marked = new HashSet<VarAndContext>();
0802: final Stack<VarAndContext> worklist = new Stack<VarAndContext>();
0803: final Propagator<VarAndContext> p = new Propagator<VarAndContext>(
0804: marked, worklist);
0805: p.prop(varAndContext);
0806: IncomingEdgeHandler edgeHandler = new IncomingEdgeHandler() {
0807:
0808: @Override
0809: public void handleAlloc(AllocNode allocNode,
0810: VarAndContext origVarAndContext) {
0811: if (realLocs.contains(allocNode)) {
0812: if (DEBUG) {
0813: debugPrint("found alloc " + allocNode);
0814: }
0815: ret.add(new AllocAndContext(allocNode,
0816: origVarAndContext.context));
0817: }
0818: }
0819:
0820: @Override
0821: public void handleMatchSrc(final VarNode matchSrc,
0822: PointsToSetInternal intersection,
0823: VarNode loadBase, VarNode storeBase,
0824: VarAndContext origVarAndContext,
0825: SparkField field, boolean refine) {
0826: if (DEBUG) {
0827: debugPrint("handling src " + matchSrc);
0828: debugPrint("intersection " + intersection);
0829: }
0830: if (!refine) {
0831: p.prop(new VarAndContext(matchSrc,
0832: EMPTY_CALLSTACK));
0833: return;
0834: }
0835: AllocAndContextSet allocContexts = findContextsForAllocs(
0836: new VarAndContext(loadBase,
0837: origVarAndContext.context),
0838: intersection);
0839: if (DEBUG) {
0840: debugPrint("alloc contexts " + allocContexts);
0841: }
0842: for (AllocAndContext allocAndContext : allocContexts) {
0843: if (DEBUG) {
0844: debugPrint("alloc and context "
0845: + allocAndContext);
0846: }
0847: CallingContextSet matchSrcContexts;
0848: if (fieldCheckHeuristic
0849: .validFromBothEnds(field)) {
0850: matchSrcContexts = findUpContextsForVar(
0851: allocAndContext,
0852: new VarContextAndUp(storeBase,
0853: EMPTY_CALLSTACK,
0854: EMPTY_CALLSTACK));
0855: } else {
0856: matchSrcContexts = findVarContextsFromAlloc(
0857: allocAndContext, storeBase);
0858: }
0859: for (ImmutableStack<Integer> matchSrcContext : matchSrcContexts) {
0860: // ret
0861: // .add(new Pair<AllocNode,
0862: // ImmutableStack<Integer>>(
0863: // (AllocNode) n,
0864: // matchSrcContext));
0865: // ret.addAll(findContextsForAllocs(matchSrc,
0866: // matchSrcContext, locs));
0867: p.prop(new VarAndContext(matchSrc,
0868: matchSrcContext));
0869: }
0870:
0871: }
0872:
0873: }
0874:
0875: @Override
0876: Object getResult() {
0877: return ret;
0878: }
0879:
0880: @Override
0881: void handleAssignSrc(VarAndContext newVarAndContext,
0882: VarAndContext origVarAndContext,
0883: AssignEdge assignEdge) {
0884: p.prop(newVarAndContext);
0885: }
0886:
0887: @Override
0888: boolean shouldHandleSrc(VarNode src) {
0889: return realLocs.hasNonEmptyIntersection(src
0890: .getP2Set());
0891: }
0892:
0893: };
0894: processIncomingEdges(edgeHandler, worklist);
0895: // update the cache
0896: if (recursionDepth != -1) {
0897: // if we're beyond recursion, don't cache anything
0898: if (contextForAllocsStack.size() > recursionDepth) {
0899: if (DEBUG) {
0900: debugPrint("REMOVING " + varAndContext);
0901: debugPrint(contextForAllocsStack.toString());
0902: }
0903: contextsForAllocsCache.remove(varAndContext);
0904: } else {
0905: assert contextForAllocsStack.size() == recursionDepth : recursionDepth
0906: + " " + contextForAllocsStack;
0907: recursionDepth = -1;
0908: if (contextsForAllocsCache
0909: .containsKey(varAndContext)) {
0910: contextsForAllocsCache.get(varAndContext)
0911: .getO2().addAll(ret);
0912: } else {
0913: PointsToSetInternal storedSet = new HybridPointsToSet(
0914: locs.getType(), pag);
0915: storedSet.addAll(locs, null);
0916: contextsForAllocsCache
0917: .put(
0918: varAndContext,
0919: new Pair<PointsToSetInternal, AllocAndContextSet>(
0920: storedSet, ret));
0921:
0922: }
0923: }
0924: } else {
0925: if (contextsForAllocsCache.containsKey(varAndContext)) {
0926: contextsForAllocsCache.get(varAndContext).getO2()
0927: .addAll(ret);
0928: } else {
0929: PointsToSetInternal storedSet = new HybridPointsToSet(
0930: locs.getType(), pag);
0931: storedSet.addAll(locs, null);
0932: contextsForAllocsCache
0933: .put(
0934: varAndContext,
0935: new Pair<PointsToSetInternal, AllocAndContextSet>(
0936: storedSet, ret));
0937:
0938: }
0939: }
0940: nesting--;
0941: return ret;
0942: } catch (CallSiteException e) {
0943: contextsForAllocsCache.remove(varAndContext);
0944: throw e;
0945: } finally {
0946: contextForAllocsStack.pop();
0947: }
0948: }
0949:
0950: protected CallingContextSet findUpContextsForVar(
0951: AllocAndContext allocAndContext,
0952: VarContextAndUp varContextAndUp) {
0953: final AllocNode alloc = allocAndContext.alloc;
0954: final ImmutableStack<Integer> allocContext = allocAndContext.context;
0955: CallingContextSet tmpSet = checkUpContextCache(varContextAndUp,
0956: allocAndContext);
0957: if (tmpSet != null) {
0958: return tmpSet;
0959: }
0960: final CallingContextSet ret = new CallingContextSet();
0961: upContextCache.get(varContextAndUp).put(allocAndContext, ret);
0962: nesting++;
0963: if (DEBUG) {
0964: debugPrint("finding up context for " + varContextAndUp
0965: + " to " + alloc + " " + allocContext);
0966: }
0967: try {
0968: final Set<VarAndContext> marked = new HashSet<VarAndContext>();
0969: final Stack<VarAndContext> worklist = new Stack<VarAndContext>();
0970: final Propagator<VarAndContext> p = new Propagator<VarAndContext>(
0971: marked, worklist);
0972: p.prop(varContextAndUp);
0973: class UpContextEdgeHandler extends IncomingEdgeHandler {
0974:
0975: @Override
0976: public void handleAlloc(AllocNode allocNode,
0977: VarAndContext origVarAndContext) {
0978: VarContextAndUp contextAndUp = (VarContextAndUp) origVarAndContext;
0979: if (allocNode == alloc) {
0980: if (allocContext
0981: .topMatches(contextAndUp.context)) {
0982: ImmutableStack<Integer> reverse = contextAndUp.upContext
0983: .reverse();
0984: ImmutableStack<Integer> toAdd = allocContext
0985: .popAll(contextAndUp.context)
0986: .pushAll(reverse);
0987: if (DEBUG) {
0988: debugPrint("found up context " + toAdd);
0989: }
0990: ret.add(toAdd);
0991: } else if (contextAndUp.context
0992: .topMatches(allocContext)) {
0993: ImmutableStack<Integer> toAdd = contextAndUp.upContext
0994: .reverse();
0995: if (DEBUG) {
0996: debugPrint("found up context " + toAdd);
0997: }
0998: ret.add(toAdd);
0999: }
1000: }
1001: }
1002:
1003: @Override
1004: public void handleMatchSrc(VarNode matchSrc,
1005: PointsToSetInternal intersection,
1006: VarNode loadBase, VarNode storeBase,
1007: VarAndContext origVarAndContext,
1008: SparkField field, boolean refine) {
1009: VarContextAndUp contextAndUp = (VarContextAndUp) origVarAndContext;
1010: if (DEBUG) {
1011: debugPrint("CHECKING " + alloc);
1012: }
1013: PointsToSetInternal tmp = new HybridPointsToSet(
1014: alloc.getType(), pag);
1015: tmp.add(alloc);
1016: AllocAndContextSet allocContexts = findContextsForAllocs(
1017: new VarAndContext(matchSrc, EMPTY_CALLSTACK),
1018: tmp);
1019: // Set allocContexts = Collections.singleton(new Object());
1020: if (!refine) {
1021: if (!allocContexts.isEmpty()) {
1022: ret.add(contextAndUp.upContext.reverse());
1023: }
1024: } else {
1025: if (!allocContexts.isEmpty()) {
1026: for (AllocAndContext t : allocContexts) {
1027: ImmutableStack<Integer> discoveredAllocContext = t.context;
1028: if (!allocContext
1029: .topMatches(discoveredAllocContext)) {
1030: continue;
1031: }
1032: ImmutableStack<Integer> trueAllocContext = allocContext
1033: .popAll(discoveredAllocContext);
1034: AllocAndContextSet allocAndContexts = findContextsForAllocs(
1035: new VarAndContext(storeBase,
1036: trueAllocContext),
1037: intersection);
1038: for (AllocAndContext allocAndContext : allocAndContexts) {
1039: // if (DEBUG)
1040: // G.v().out.println("alloc context "
1041: // + newAllocContext);
1042: // CallingContextSet upContexts;
1043: if (fieldCheckHeuristic
1044: .validFromBothEnds(field)) {
1045: ret
1046: .addAll(findUpContextsForVar(
1047: allocAndContext,
1048: new VarContextAndUp(
1049: loadBase,
1050: contextAndUp.context,
1051: contextAndUp.upContext)));
1052: } else {
1053: CallingContextSet tmpContexts = findVarContextsFromAlloc(
1054: allocAndContext,
1055: loadBase);
1056: // upContexts = new CallingContextSet();
1057: for (ImmutableStack<Integer> tmpContext : tmpContexts) {
1058: if (tmpContext
1059: .topMatches(contextAndUp.context)) {
1060: ImmutableStack<Integer> reverse = contextAndUp.upContext
1061: .reverse();
1062: ImmutableStack<Integer> toAdd = tmpContext
1063: .popAll(
1064: contextAndUp.context)
1065: .pushAll(
1066: reverse);
1067: ret.add(toAdd);
1068: }
1069:
1070: }
1071: }
1072: }
1073: }
1074: }
1075: }
1076:
1077: }
1078:
1079: @Override
1080: Object getResult() {
1081: return ret;
1082: }
1083:
1084: @Override
1085: void handleAssignSrc(VarAndContext newVarAndContext,
1086: VarAndContext origVarAndContext,
1087: AssignEdge assignEdge) {
1088: VarContextAndUp contextAndUp = (VarContextAndUp) origVarAndContext;
1089: ImmutableStack<Integer> upContext = contextAndUp.upContext;
1090: ImmutableStack<Integer> newUpContext = upContext;
1091: if (assignEdge.isParamEdge()
1092: && contextAndUp.context.isEmpty()) {
1093: if (upContext.size() < ImmutableStack
1094: .getMaxSize()) {
1095: newUpContext = pushWithRecursionCheck(
1096: upContext, assignEdge);
1097: }
1098: ;
1099: }
1100: p.prop(new VarContextAndUp(newVarAndContext.var,
1101: newVarAndContext.context, newUpContext));
1102: }
1103:
1104: @Override
1105: boolean shouldHandleSrc(VarNode src) {
1106: if (src instanceof GlobalVarNode) {
1107: // TODO properly handle case of global here; rare
1108: // but possible
1109: // reachedGlobal = true;
1110: // // for now, just give up
1111: throw new TerminateEarlyException();
1112: }
1113: return src.getP2Set().contains(alloc);
1114: }
1115:
1116: }
1117: ;
1118: UpContextEdgeHandler edgeHandler = new UpContextEdgeHandler();
1119: processIncomingEdges(edgeHandler, worklist);
1120: nesting--;
1121: // if (edgeHandler.reachedGlobal) {
1122: // return fixAllUpContexts(ret, allocAndContext, varContextAndUp);
1123: // } else {
1124: // assert upContextsSane(ret, allocAndContext, varContextAndUp);
1125: // return ret;
1126: // }
1127: return ret;
1128: } catch (CallSiteException e) {
1129: upContextCache.remove(varContextAndUp);
1130: throw e;
1131: }
1132: }
1133:
1134: protected CallingContextSet findVarContextsFromAlloc(
1135: AllocAndContext allocAndContext, VarNode targetVar) {
1136:
1137: CallingContextSet tmpSet = checkAllocAndContextCache(
1138: allocAndContext, targetVar);
1139: if (tmpSet != null) {
1140: return tmpSet;
1141: }
1142: CallingContextSet ret = new CallingContextSet();
1143: allocAndContextCache.get(allocAndContext).put(targetVar, ret);
1144: try {
1145: HashSet<VarAndContext> marked = new HashSet<VarAndContext>();
1146: Stack<VarAndContext> worklist = new Stack<VarAndContext>();
1147: Propagator<VarAndContext> p = new Propagator<VarAndContext>(
1148: marked, worklist);
1149: AllocNode alloc = allocAndContext.alloc;
1150: ImmutableStack<Integer> allocContext = allocAndContext.context;
1151: Node[] newBarNodes = pag.allocLookup(alloc);
1152: for (int i = 0; i < newBarNodes.length; i++) {
1153: VarNode v = (VarNode) newBarNodes[i];
1154: p.prop(new VarAndContext(v, allocContext));
1155: }
1156: while (!worklist.isEmpty()) {
1157: incrementNodesTraversed();
1158: VarAndContext curVarAndContext = worklist.pop();
1159: if (DEBUG) {
1160: debugPrint("looking at " + curVarAndContext);
1161: }
1162: VarNode curVar = curVarAndContext.var;
1163: ImmutableStack<Integer> curContext = curVarAndContext.context;
1164: if (curVar == targetVar) {
1165: ret.add(curContext);
1166: }
1167: // assign
1168: Collection<AssignEdge> assignEdges = filterAssigns(
1169: curVar, curContext, false, true);
1170: for (AssignEdge assignEdge : assignEdges) {
1171: VarNode dst = assignEdge.getDst();
1172: ImmutableStack<Integer> newContext = curContext;
1173: if (assignEdge.isReturnEdge()) {
1174: if (!curContext.isEmpty()) {
1175: if (!callEdgeInSCC(assignEdge)) {
1176: assert assignEdge.getCallSite().equals(
1177: curContext.peek()) : assignEdge
1178: + " " + curContext;
1179: newContext = curContext.pop();
1180: } else {
1181: newContext = popRecursiveCallSites(curContext);
1182: }
1183: }
1184: } else if (assignEdge.isParamEdge()) {
1185: if (DEBUG)
1186: debugPrint("entering call site "
1187: + assignEdge.getCallSite());
1188: // if (!isRecursive(curContext, assignEdge)) {
1189: // newContext = curContext.push(assignEdge
1190: // .getCallSite());
1191: // }
1192: newContext = pushWithRecursionCheck(curContext,
1193: assignEdge);
1194: }
1195: if (assignEdge.isReturnEdge()
1196: && curContext.isEmpty()
1197: && csInfo.isVirtCall(assignEdge
1198: .getCallSite())) {
1199: Set<SootMethod> targets = refineCallSite(
1200: assignEdge.getCallSite(), newContext);
1201: if (!targets
1202: .contains(((LocalVarNode) assignEdge
1203: .getDst()).getMethod())) {
1204: continue;
1205: }
1206: }
1207: if (dst instanceof GlobalVarNode) {
1208: newContext = EMPTY_CALLSTACK;
1209: }
1210: p.prop(new VarAndContext(dst, newContext));
1211: }
1212: // putfield_bars
1213: Set<VarNode> matchTargets = vMatches
1214: .vMatchLookup(curVar);
1215: Node[] pfTargets = pag.storeLookup(curVar);
1216: for (int i = 0; i < pfTargets.length; i++) {
1217: FieldRefNode frNode = (FieldRefNode) pfTargets[i];
1218: final VarNode storeBase = frNode.getBase();
1219: SparkField field = frNode.getField();
1220: // Pair<VarNode, FieldRefNode> putfield = new Pair<VarNode,
1221: // FieldRefNode>(curVar, frNode);
1222: for (Pair<VarNode, VarNode> load : fieldToLoads
1223: .get(field)) {
1224: final VarNode loadBase = load.getO2();
1225: final PointsToSetInternal loadBaseP2Set = loadBase
1226: .getP2Set();
1227: final PointsToSetInternal storeBaseP2Set = storeBase
1228: .getP2Set();
1229: final VarNode matchTgt = load.getO1();
1230: if (matchTargets.contains(matchTgt)) {
1231: if (DEBUG) {
1232: debugPrint("match source " + matchTgt);
1233: }
1234: PointsToSetInternal intersection = SootUtil
1235: .constructIntersection(
1236: storeBaseP2Set,
1237: loadBaseP2Set, pag);
1238:
1239: boolean checkField = fieldCheckHeuristic
1240: .validateMatchesForField(field);
1241: if (checkField) {
1242: AllocAndContextSet sharedAllocContexts = findContextsForAllocs(
1243: new VarAndContext(storeBase,
1244: curContext),
1245: intersection);
1246: for (AllocAndContext curAllocAndContext : sharedAllocContexts) {
1247: CallingContextSet upContexts;
1248: if (fieldCheckHeuristic
1249: .validFromBothEnds(field)) {
1250: upContexts = findUpContextsForVar(
1251: curAllocAndContext,
1252: new VarContextAndUp(
1253: loadBase,
1254: EMPTY_CALLSTACK,
1255: EMPTY_CALLSTACK));
1256: } else {
1257: upContexts = findVarContextsFromAlloc(
1258: curAllocAndContext,
1259: loadBase);
1260: }
1261: for (ImmutableStack<Integer> upContext : upContexts) {
1262: p.prop(new VarAndContext(
1263: matchTgt, upContext));
1264: }
1265: }
1266: } else {
1267: p.prop(new VarAndContext(matchTgt,
1268: EMPTY_CALLSTACK));
1269: }
1270: // h.handleMatchSrc(matchSrc, intersection,
1271: // storeBase,
1272: // loadBase, varAndContext, checkGetfield);
1273: // if (h.terminate())
1274: // return;
1275: }
1276: }
1277:
1278: }
1279: }
1280: return ret;
1281: } catch (CallSiteException e) {
1282: allocAndContextCache.remove(allocAndContext);
1283: throw e;
1284: }
1285: }
1286:
1287: @SuppressWarnings("unchecked")
1288: protected Set<SootMethod> getCallTargets(PointsToSetInternal p2Set,
1289: NumberedString methodStr, Type receiverType,
1290: Set<SootMethod> possibleTargets) {
1291: List<Object> args = Arrays.asList(p2Set, methodStr,
1292: receiverType, possibleTargets);
1293: if (callTargetsArgCache.containsKey(args)) {
1294: return callTargetsArgCache.get(args);
1295: }
1296: Set<Type> types = p2Set.possibleTypes();
1297: Set<SootMethod> ret = new HashSet<SootMethod>();
1298: for (Type type : types) {
1299: ret.addAll(getCallTargetsForType(type, methodStr,
1300: receiverType, possibleTargets));
1301: }
1302: callTargetsArgCache.put(args, ret);
1303: return ret;
1304: }
1305:
1306: protected Set<SootMethod> getCallTargetsForType(Type type,
1307: NumberedString methodStr, Type receiverType,
1308: Set<SootMethod> possibleTargets) {
1309: if (!pag.getTypeManager().castNeverFails(type, receiverType))
1310: return Collections.<SootMethod> emptySet();
1311: if (type instanceof AnySubType) {
1312: AnySubType any = (AnySubType) type;
1313: RefType refType = any.getBase();
1314: if (pag.getTypeManager().getFastHierarchy().canStoreType(
1315: receiverType, refType)
1316: || pag.getTypeManager().getFastHierarchy()
1317: .canStoreType(refType, receiverType)) {
1318: return possibleTargets;
1319: } else {
1320: return Collections.<SootMethod> emptySet();
1321: }
1322: }
1323: if (type instanceof ArrayType) {
1324: // we'll invoke the java.lang.Object method in this
1325: // case
1326: // Assert.chk(varNodeType.toString().equals("java.lang.Object"));
1327: type = Scene.v().getSootClass("java.lang.Object").getType();
1328: }
1329: RefType refType = (RefType) type;
1330: SootMethod targetMethod = null;
1331: targetMethod = VirtualCalls.v().resolveNonSpecial(refType,
1332: methodStr);
1333: return Collections.<SootMethod> singleton(targetMethod);
1334:
1335: }
1336:
1337: protected Set<VarNode> getFlowsToHelper(
1338: AllocAndContext allocAndContext) {
1339: Set<VarNode> ret = new ArraySet<VarNode>();
1340:
1341: try {
1342: HashSet<VarAndContext> marked = new HashSet<VarAndContext>();
1343: Stack<VarAndContext> worklist = new Stack<VarAndContext>();
1344: Propagator<VarAndContext> p = new Propagator<VarAndContext>(
1345: marked, worklist);
1346: AllocNode alloc = allocAndContext.alloc;
1347: ImmutableStack<Integer> allocContext = allocAndContext.context;
1348: Node[] newBarNodes = pag.allocLookup(alloc);
1349: for (int i = 0; i < newBarNodes.length; i++) {
1350: VarNode v = (VarNode) newBarNodes[i];
1351: ret.add(v);
1352: p.prop(new VarAndContext(v, allocContext));
1353: }
1354: while (!worklist.isEmpty()) {
1355: incrementNodesTraversed();
1356: VarAndContext curVarAndContext = worklist.pop();
1357: if (DEBUG) {
1358: debugPrint("looking at " + curVarAndContext);
1359: }
1360: VarNode curVar = curVarAndContext.var;
1361: ImmutableStack<Integer> curContext = curVarAndContext.context;
1362: ret.add(curVar);
1363: // assign
1364: Collection<AssignEdge> assignEdges = filterAssigns(
1365: curVar, curContext, false, true);
1366: for (AssignEdge assignEdge : assignEdges) {
1367: VarNode dst = assignEdge.getDst();
1368: ImmutableStack<Integer> newContext = curContext;
1369: if (assignEdge.isReturnEdge()) {
1370: if (!curContext.isEmpty()) {
1371: if (!callEdgeInSCC(assignEdge)) {
1372: assert assignEdge.getCallSite().equals(
1373: curContext.peek()) : assignEdge
1374: + " " + curContext;
1375: newContext = curContext.pop();
1376: } else {
1377: newContext = popRecursiveCallSites(curContext);
1378: }
1379: }
1380: } else if (assignEdge.isParamEdge()) {
1381: if (DEBUG)
1382: debugPrint("entering call site "
1383: + assignEdge.getCallSite());
1384: // if (!isRecursive(curContext, assignEdge)) {
1385: // newContext = curContext.push(assignEdge
1386: // .getCallSite());
1387: // }
1388: newContext = pushWithRecursionCheck(curContext,
1389: assignEdge);
1390: }
1391: if (assignEdge.isReturnEdge()
1392: && curContext.isEmpty()
1393: && csInfo.isVirtCall(assignEdge
1394: .getCallSite())) {
1395: Set<SootMethod> targets = refineCallSite(
1396: assignEdge.getCallSite(), newContext);
1397: if (!targets
1398: .contains(((LocalVarNode) assignEdge
1399: .getDst()).getMethod())) {
1400: continue;
1401: }
1402: }
1403: if (dst instanceof GlobalVarNode) {
1404: newContext = EMPTY_CALLSTACK;
1405: }
1406: p.prop(new VarAndContext(dst, newContext));
1407: }
1408: // putfield_bars
1409: Set<VarNode> matchTargets = vMatches
1410: .vMatchLookup(curVar);
1411: Node[] pfTargets = pag.storeLookup(curVar);
1412: for (int i = 0; i < pfTargets.length; i++) {
1413: FieldRefNode frNode = (FieldRefNode) pfTargets[i];
1414: final VarNode storeBase = frNode.getBase();
1415: SparkField field = frNode.getField();
1416: // Pair<VarNode, FieldRefNode> putfield = new Pair<VarNode,
1417: // FieldRefNode>(curVar, frNode);
1418: for (Pair<VarNode, VarNode> load : fieldToLoads
1419: .get(field)) {
1420: final VarNode loadBase = load.getO2();
1421: final PointsToSetInternal loadBaseP2Set = loadBase
1422: .getP2Set();
1423: final PointsToSetInternal storeBaseP2Set = storeBase
1424: .getP2Set();
1425: final VarNode matchTgt = load.getO1();
1426: if (matchTargets.contains(matchTgt)) {
1427: if (DEBUG) {
1428: debugPrint("match source " + matchTgt);
1429: }
1430: PointsToSetInternal intersection = SootUtil
1431: .constructIntersection(
1432: storeBaseP2Set,
1433: loadBaseP2Set, pag);
1434:
1435: boolean checkField = fieldCheckHeuristic
1436: .validateMatchesForField(field);
1437: if (checkField) {
1438: AllocAndContextSet sharedAllocContexts = findContextsForAllocs(
1439: new VarAndContext(storeBase,
1440: curContext),
1441: intersection);
1442: for (AllocAndContext curAllocAndContext : sharedAllocContexts) {
1443: CallingContextSet upContexts;
1444: if (fieldCheckHeuristic
1445: .validFromBothEnds(field)) {
1446: upContexts = findUpContextsForVar(
1447: curAllocAndContext,
1448: new VarContextAndUp(
1449: loadBase,
1450: EMPTY_CALLSTACK,
1451: EMPTY_CALLSTACK));
1452: } else {
1453: upContexts = findVarContextsFromAlloc(
1454: curAllocAndContext,
1455: loadBase);
1456: }
1457: for (ImmutableStack<Integer> upContext : upContexts) {
1458: p.prop(new VarAndContext(
1459: matchTgt, upContext));
1460: }
1461: }
1462: } else {
1463: p.prop(new VarAndContext(matchTgt,
1464: EMPTY_CALLSTACK));
1465: }
1466: // h.handleMatchSrc(matchSrc, intersection,
1467: // storeBase,
1468: // loadBase, varAndContext, checkGetfield);
1469: // if (h.terminate())
1470: // return;
1471: }
1472: }
1473:
1474: }
1475: }
1476: return ret;
1477: } catch (CallSiteException e) {
1478: allocAndContextCache.remove(allocAndContext);
1479: throw e;
1480: }
1481: }
1482:
1483: protected int getMaxPasses() {
1484: return maxPasses;
1485: }
1486:
1487: protected void incrementNodesTraversed() {
1488: numNodesTraversed++;
1489: if (numNodesTraversed > maxNodesPerPass) {
1490: throw new TerminateEarlyException();
1491: }
1492: }
1493:
1494: @SuppressWarnings("unused")
1495: protected boolean isRecursive(ImmutableStack<Integer> context,
1496: AssignEdge assignEdge) {
1497: boolean sameSCCAlready = callEdgeInSCC(assignEdge);
1498: if (sameSCCAlready) {
1499: return true;
1500: }
1501: Integer callSite = assignEdge.getCallSite();
1502: if (context.contains(callSite)) {
1503: Set<SootMethod> toBeCollapsed = new ArraySet<SootMethod>();
1504: int callSiteInd = 0;
1505: for (; callSiteInd < context.size()
1506: && !context.get(callSiteInd).equals(callSite); callSiteInd++)
1507: ;
1508: for (; callSiteInd < context.size(); callSiteInd++) {
1509: toBeCollapsed.add(csInfo.getInvokingMethod(context
1510: .get(callSiteInd)));
1511: }
1512: sccManager.makeSameSCC(toBeCollapsed);
1513: return true;
1514: }
1515: return false;
1516: }
1517:
1518: protected boolean isRecursiveCallSite(Integer callSite) {
1519: SootMethod invokingMethod = csInfo.getInvokingMethod(callSite);
1520: SootMethod invokedMethod = csInfo.getInvokedMethod(callSite);
1521: return sccManager.inSameSCC(invokingMethod, invokedMethod);
1522: }
1523:
1524: @SuppressWarnings("unused")
1525: protected Set<VarNode> nodesPropagatedThrough(final VarNode source,
1526: final PointsToSetInternal allocs) {
1527: final Set<VarNode> marked = new HashSet<VarNode>();
1528: final Stack<VarNode> worklist = new Stack<VarNode>();
1529: Propagator<VarNode> p = new Propagator<VarNode>(marked,
1530: worklist);
1531: p.prop(source);
1532: while (!worklist.isEmpty()) {
1533: VarNode curNode = worklist.pop();
1534: Node[] assignSources = pag.simpleInvLookup(curNode);
1535: for (int i = 0; i < assignSources.length; i++) {
1536: VarNode assignSrc = (VarNode) assignSources[i];
1537: if (assignSrc.getP2Set()
1538: .hasNonEmptyIntersection(allocs)) {
1539: p.prop(assignSrc);
1540: }
1541: }
1542: Set<VarNode> matchSources = vMatches
1543: .vMatchInvLookup(curNode);
1544: for (VarNode matchSrc : matchSources) {
1545: if (matchSrc.getP2Set().hasNonEmptyIntersection(allocs)) {
1546: p.prop(matchSrc);
1547: }
1548: }
1549: }
1550: return marked;
1551: }
1552:
1553: protected ImmutableStack<Integer> popRecursiveCallSites(
1554: ImmutableStack<Integer> context) {
1555: ImmutableStack<Integer> ret = context;
1556: while (!ret.isEmpty() && isRecursiveCallSite(ret.peek())) {
1557: ret = ret.pop();
1558: }
1559: return ret;
1560: }
1561:
1562: protected void processIncomingEdges(IncomingEdgeHandler h,
1563: Stack<VarAndContext> worklist) {
1564: while (!worklist.isEmpty()) {
1565: incrementNodesTraversed();
1566: VarAndContext varAndContext = worklist.pop();
1567: if (DEBUG) {
1568: debugPrint("looking at " + varAndContext);
1569: }
1570: VarNode v = varAndContext.var;
1571: ImmutableStack<Integer> callingContext = varAndContext.context;
1572: Node[] newEdges = pag.allocInvLookup(v);
1573: for (int i = 0; i < newEdges.length; i++) {
1574: AllocNode allocNode = (AllocNode) newEdges[i];
1575: h.handleAlloc(allocNode, varAndContext);
1576: if (h.terminate()) {
1577: return;
1578: }
1579: }
1580: Collection<AssignEdge> assigns = filterAssigns(v,
1581: callingContext, true, true);
1582: for (AssignEdge assignEdge : assigns) {
1583: VarNode src = assignEdge.getSrc();
1584: // if (DEBUG) {
1585: // G.v().out.println("assign src " + src);
1586: // }
1587: if (h.shouldHandleSrc(src)) {
1588: ImmutableStack<Integer> newContext = callingContext;
1589: if (assignEdge.isParamEdge()) {
1590: if (!callingContext.isEmpty()) {
1591: if (!callEdgeInSCC(assignEdge)) {
1592: assert assignEdge.getCallSite().equals(
1593: callingContext.peek()) : assignEdge
1594: + " " + callingContext;
1595: newContext = callingContext.pop();
1596: } else {
1597: newContext = popRecursiveCallSites(callingContext);
1598: }
1599: }
1600: // } else if (refiningCallSite) {
1601: // if (!fieldCheckHeuristic.aggressiveVirtCallRefine())
1602: // {
1603: // // throw new CallSiteException();
1604: // }
1605: // }
1606: } else if (assignEdge.isReturnEdge()) {
1607: if (DEBUG)
1608: debugPrint("entering call site "
1609: + assignEdge.getCallSite());
1610: // if (!isRecursive(callingContext, assignEdge)) {
1611: // newContext = callingContext.push(assignEdge
1612: // .getCallSite());
1613: // }
1614: newContext = pushWithRecursionCheck(
1615: callingContext, assignEdge);
1616: }
1617: if (assignEdge.isParamEdge()) {
1618: Integer callSite = assignEdge.getCallSite();
1619: if (csInfo.isVirtCall(callSite)
1620: && !weirdCall(callSite)) {
1621: Set<SootMethod> targets = refineCallSite(
1622: callSite, newContext);
1623: if (DEBUG) {
1624: debugPrint(targets.toString());
1625: }
1626: SootMethod targetMethod = ((LocalVarNode) assignEdge
1627: .getDst()).getMethod();
1628: if (!targets.contains(targetMethod)) {
1629: if (DEBUG) {
1630: debugPrint("skipping call because of call graph");
1631: }
1632: continue;
1633: }
1634: }
1635: }
1636: if (src instanceof GlobalVarNode) {
1637: newContext = EMPTY_CALLSTACK;
1638: }
1639: h.handleAssignSrc(
1640: new VarAndContext(src, newContext),
1641: varAndContext, assignEdge);
1642: if (h.terminate()) {
1643: return;
1644: }
1645:
1646: }
1647: }
1648: Set<VarNode> matchSources = vMatches.vMatchInvLookup(v);
1649: Node[] loads = pag.loadInvLookup(v);
1650: for (int i = 0; i < loads.length; i++) {
1651: FieldRefNode frNode = (FieldRefNode) loads[i];
1652: final VarNode loadBase = frNode.getBase();
1653: SparkField field = frNode.getField();
1654: // Pair<VarNode, FieldRefNode> getfield = new Pair<VarNode,
1655: // FieldRefNode>(v, frNode);
1656: for (Pair<VarNode, VarNode> store : fieldToStores
1657: .get(field)) {
1658: final VarNode storeBase = store.getO2();
1659: final PointsToSetInternal storeBaseP2Set = storeBase
1660: .getP2Set();
1661: final PointsToSetInternal loadBaseP2Set = loadBase
1662: .getP2Set();
1663: final VarNode matchSrc = store.getO1();
1664: if (matchSources.contains(matchSrc)) {
1665: if (h.shouldHandleSrc(matchSrc)) {
1666: if (DEBUG) {
1667: debugPrint("match source " + matchSrc);
1668: }
1669: PointsToSetInternal intersection = SootUtil
1670: .constructIntersection(
1671: storeBaseP2Set,
1672: loadBaseP2Set, pag);
1673:
1674: boolean checkGetfield = fieldCheckHeuristic
1675: .validateMatchesForField(field);
1676:
1677: h.handleMatchSrc(matchSrc, intersection,
1678: loadBase, storeBase, varAndContext,
1679: field, checkGetfield);
1680: if (h.terminate())
1681: return;
1682: }
1683: }
1684: }
1685: }
1686: }
1687: }
1688:
1689: protected ImmutableStack<Integer> pushWithRecursionCheck(
1690: ImmutableStack<Integer> context, AssignEdge assignEdge) {
1691: boolean foundRecursion = callEdgeInSCC(assignEdge);
1692: if (!foundRecursion) {
1693: Integer callSite = assignEdge.getCallSite();
1694: if (context.contains(callSite)) {
1695: foundRecursion = true;
1696: if (DEBUG) {
1697: debugPrint("RECURSION!!!");
1698: }
1699: // TODO properly collapse recursive methods
1700: if (true) {
1701: throw new TerminateEarlyException();
1702: }
1703: Set<SootMethod> toBeCollapsed = new ArraySet<SootMethod>();
1704: int callSiteInd = 0;
1705: for (; callSiteInd < context.size()
1706: && !context.get(callSiteInd).equals(callSite); callSiteInd++)
1707: ;
1708: // int numToPop = 0;
1709: for (; callSiteInd < context.size(); callSiteInd++) {
1710: toBeCollapsed.add(csInfo.getInvokingMethod(context
1711: .get(callSiteInd)));
1712: // numToPop++;
1713: }
1714: sccManager.makeSameSCC(toBeCollapsed);
1715: // ImmutableStack<Integer> poppedContext = context;
1716: // for (int i = 0; i < numToPop; i++) {
1717: // poppedContext = poppedContext.pop();
1718: // }
1719: // if (DEBUG) {
1720: // debugPrint("new stack " + poppedContext);
1721: // }
1722: // return poppedContext;
1723: }
1724: }
1725: if (foundRecursion) {
1726: ImmutableStack<Integer> popped = popRecursiveCallSites(context);
1727: if (DEBUG) {
1728: debugPrint("popped stack " + popped);
1729: }
1730: return popped;
1731: } else {
1732: return context.push(assignEdge.getCallSite());
1733: }
1734: }
1735:
1736: protected boolean refineAlias(VarNode v1, VarNode v2,
1737: PointsToSetInternal intersection, HeuristicType heuristic) {
1738: if (refineAliasInternal(v1, v2, intersection, heuristic))
1739: return true;
1740: if (refineAliasInternal(v2, v1, intersection, heuristic))
1741: return true;
1742: return false;
1743: }
1744:
1745: protected boolean refineAliasInternal(VarNode v1, VarNode v2,
1746: PointsToSetInternal intersection, HeuristicType heuristic) {
1747: this .fieldCheckHeuristic = HeuristicType.getHeuristic(
1748: heuristic, pag.getTypeManager(), getMaxPasses());
1749: numPasses = 0;
1750: while (true) {
1751: numPasses++;
1752: if (DEBUG_PASS != -1 && numPasses > DEBUG_PASS) {
1753: return false;
1754: }
1755: if (numPasses > maxPasses) {
1756: return false;
1757: }
1758: if (DEBUG) {
1759: G.v().out.println("PASS " + numPasses);
1760: G.v().out.println(fieldCheckHeuristic);
1761: }
1762: clearState();
1763: boolean success = false;
1764: try {
1765: AllocAndContextSet allocAndContexts = findContextsForAllocs(
1766: new VarAndContext(v1, EMPTY_CALLSTACK),
1767: intersection);
1768: boolean emptyIntersection = true;
1769: for (AllocAndContext allocAndContext : allocAndContexts) {
1770: CallingContextSet upContexts = findUpContextsForVar(
1771: allocAndContext, new VarContextAndUp(v2,
1772: EMPTY_CALLSTACK, EMPTY_CALLSTACK));
1773: if (!upContexts.isEmpty()) {
1774: emptyIntersection = false;
1775: break;
1776: }
1777: }
1778: success = emptyIntersection;
1779: } catch (TerminateEarlyException e) {
1780: success = false;
1781: }
1782: if (success) {
1783: G.v().out.println("took " + numPasses + " passes");
1784: return true;
1785: } else {
1786: if (!fieldCheckHeuristic.runNewPass()) {
1787: return false;
1788: }
1789: }
1790: }
1791: }
1792:
1793: protected Set<SootMethod> refineCallSite(Integer callSite,
1794: ImmutableStack<Integer> origContext) {
1795: CallSiteAndContext callSiteAndContext = new CallSiteAndContext(
1796: callSite, origContext);
1797: if (queriedCallSites.contains(callSiteAndContext)) {
1798: // if (DEBUG_VIRT) {
1799: // final SootMethod invokedMethod =
1800: // csInfo.getInvokedMethod(callSite);
1801: // final VarNode receiver =
1802: // csInfo.getReceiverForVirtCallSite(callSite);
1803: // debugPrint("call of " + invokedMethod + " on " + receiver + " "
1804: // + origContext + " goes to "
1805: // + callSiteToResolvedTargets.get(callSiteAndContext));
1806: // }
1807: return callSiteToResolvedTargets.get(callSiteAndContext);
1808: }
1809: if (callGraphStack.contains(callSiteAndContext)) {
1810: return Collections.<SootMethod> emptySet();
1811: } else {
1812: callGraphStack.push(callSiteAndContext);
1813: }
1814: final VarNode receiver = csInfo
1815: .getReceiverForVirtCallSite(callSite);
1816: final Type receiverType = receiver.getType();
1817: final SootMethod invokedMethod = csInfo
1818: .getInvokedMethod(callSite);
1819: final NumberedString methodSig = invokedMethod
1820: .getNumberedSubSignature();
1821: final Set<SootMethod> allTargets = csInfo
1822: .getCallSiteTargets(callSite);
1823: if (!refineCallGraph) {
1824: callGraphStack.pop();
1825: return allTargets;
1826: }
1827: if (DEBUG_VIRT) {
1828: debugPrint("refining call to " + invokedMethod + " on "
1829: + receiver + " " + origContext);
1830: }
1831: final HashSet<VarAndContext> marked = new HashSet<VarAndContext>();
1832: final Stack<VarAndContext> worklist = new Stack<VarAndContext>();
1833: final class Helper {
1834:
1835: void prop(VarAndContext varAndContext) {
1836: if (marked.add(varAndContext)) {
1837: worklist.push(varAndContext);
1838: }
1839: }
1840: }
1841: ;
1842: final Helper h = new Helper();
1843: h.prop(new VarAndContext(receiver, origContext));
1844: while (!worklist.isEmpty()) {
1845: incrementNodesTraversed();
1846: VarAndContext curVarAndContext = worklist.pop();
1847: if (DEBUG_VIRT) {
1848: debugPrint("virt looking at " + curVarAndContext);
1849: }
1850: VarNode curVar = curVarAndContext.var;
1851: ImmutableStack<Integer> curContext = curVarAndContext.context;
1852: // Set<SootMethod> curVarTargets = getCallTargets(curVar.getP2Set(),
1853: // methodSig, receiverType, allTargets);
1854: // if (curVarTargets.size() <= 1) {
1855: // for (SootMethod method : curVarTargets) {
1856: // callSiteToResolvedTargets.put(callSiteAndContext, method);
1857: // }
1858: // continue;
1859: // }
1860: Node[] newNodes = pag.allocInvLookup(curVar);
1861: for (int i = 0; i < newNodes.length; i++) {
1862: AllocNode allocNode = (AllocNode) newNodes[i];
1863: for (SootMethod method : getCallTargetsForType(
1864: allocNode.getType(), methodSig, receiverType,
1865: allTargets)) {
1866: callSiteToResolvedTargets.put(callSiteAndContext,
1867: method);
1868: }
1869: }
1870: Collection<AssignEdge> assigns = filterAssigns(curVar,
1871: curContext, true, true);
1872: for (AssignEdge assignEdge : assigns) {
1873: VarNode src = assignEdge.getSrc();
1874: ImmutableStack<Integer> newContext = curContext;
1875: if (assignEdge.isParamEdge()) {
1876: if (!curContext.isEmpty()) {
1877: if (!callEdgeInSCC(assignEdge)) {
1878: assert assignEdge.getCallSite().equals(
1879: curContext.peek());
1880: newContext = curContext.pop();
1881: } else {
1882: newContext = popRecursiveCallSites(curContext);
1883: }
1884: } else {
1885: callSiteToResolvedTargets.putAll(
1886: callSiteAndContext, allTargets);
1887: // if (DEBUG) {
1888: // debugPrint("giving up on virt");
1889: // }
1890: continue;
1891: }
1892: } else if (assignEdge.isReturnEdge()) {
1893: // if (DEBUG)
1894: // G.v().out.println("entering call site "
1895: // + assignEdge.getCallSite());
1896: // if (!isRecursive(curContext, assignEdge)) {
1897: // newContext = curContext.push(assignEdge.getCallSite());
1898: // }
1899: newContext = pushWithRecursionCheck(curContext,
1900: assignEdge);
1901: } else if (src instanceof GlobalVarNode) {
1902: newContext = EMPTY_CALLSTACK;
1903: }
1904: h.prop(new VarAndContext(src, newContext));
1905: }
1906: // TODO respect heuristic
1907: Set<VarNode> matchSources = vMatches
1908: .vMatchInvLookup(curVar);
1909: final boolean oneMatch = matchSources.size() == 1;
1910: Node[] loads = pag.loadInvLookup(curVar);
1911: for (int i = 0; i < loads.length; i++) {
1912: FieldRefNode frNode = (FieldRefNode) loads[i];
1913: final VarNode loadBase = frNode.getBase();
1914: SparkField field = frNode.getField();
1915: for (Pair<VarNode, VarNode> store : fieldToStores
1916: .get(field)) {
1917: final VarNode storeBase = store.getO2();
1918: final PointsToSetInternal storeBaseP2Set = storeBase
1919: .getP2Set();
1920: final PointsToSetInternal loadBaseP2Set = loadBase
1921: .getP2Set();
1922: final VarNode matchSrc = store.getO1();
1923: if (matchSources.contains(matchSrc)) {
1924: // optimize for common case of constructor init
1925: boolean skipMatch = false;
1926: if (oneMatch) {
1927: PointsToSetInternal matchSrcPTo = matchSrc
1928: .getP2Set();
1929: Set<SootMethod> matchSrcCallTargets = getCallTargets(
1930: matchSrcPTo, methodSig,
1931: receiverType, allTargets);
1932: if (matchSrcCallTargets.size() <= 1) {
1933: skipMatch = true;
1934: for (SootMethod method : matchSrcCallTargets) {
1935: callSiteToResolvedTargets.put(
1936: callSiteAndContext, method);
1937: }
1938: }
1939: }
1940: if (!skipMatch) {
1941: final PointsToSetInternal intersection = SootUtil
1942: .constructIntersection(
1943: storeBaseP2Set,
1944: loadBaseP2Set, pag);
1945: AllocAndContextSet allocContexts = null;
1946: boolean oldRefining = refiningCallSite;
1947: int oldNesting = nesting;
1948: try {
1949: refiningCallSite = true;
1950: allocContexts = findContextsForAllocs(
1951: new VarAndContext(loadBase,
1952: curContext),
1953: intersection);
1954: } catch (CallSiteException e) {
1955: callSiteToResolvedTargets.putAll(
1956: callSiteAndContext, allTargets);
1957: continue;
1958: } finally {
1959: refiningCallSite = oldRefining;
1960: nesting = oldNesting;
1961: }
1962: for (AllocAndContext allocAndContext : allocContexts) {
1963: CallingContextSet matchSrcContexts;
1964: if (fieldCheckHeuristic
1965: .validFromBothEnds(field)) {
1966: matchSrcContexts = findUpContextsForVar(
1967: allocAndContext,
1968: new VarContextAndUp(
1969: storeBase,
1970: EMPTY_CALLSTACK,
1971: EMPTY_CALLSTACK));
1972: } else {
1973: matchSrcContexts = findVarContextsFromAlloc(
1974: allocAndContext, storeBase);
1975: }
1976: for (ImmutableStack<Integer> matchSrcContext : matchSrcContexts) {
1977: VarAndContext newVarAndContext = new VarAndContext(
1978: matchSrc, matchSrcContext);
1979: h.prop(newVarAndContext);
1980: }
1981: }
1982:
1983: }
1984:
1985: }
1986: }
1987: }
1988:
1989: }
1990: if (DEBUG_VIRT) {
1991: debugPrint("call of " + invokedMethod + " on " + receiver
1992: + " " + origContext + " goes to "
1993: + callSiteToResolvedTargets.get(callSiteAndContext));
1994: }
1995: callGraphStack.pop();
1996: queriedCallSites.add(callSiteAndContext);
1997: return callSiteToResolvedTargets.get(callSiteAndContext);
1998:
1999: }
2000:
2001: protected boolean refineP2Set(VarAndContext varAndContext,
2002: final PointsToSetInternal badLocs) {
2003: nesting++;
2004: if (DEBUG) {
2005: debugPrint("refining " + varAndContext);
2006: }
2007: final Set<VarAndContext> marked = new HashSet<VarAndContext>();
2008: final Stack<VarAndContext> worklist = new Stack<VarAndContext>();
2009: final Propagator<VarAndContext> p = new Propagator<VarAndContext>(
2010: marked, worklist);
2011: p.prop(varAndContext);
2012: IncomingEdgeHandler edgeHandler = new IncomingEdgeHandler() {
2013:
2014: boolean success = true;
2015:
2016: @Override
2017: public void handleAlloc(AllocNode allocNode,
2018: VarAndContext origVarAndContext) {
2019: if (doPointsTo && pointsTo != null) {
2020: pointsTo.add(new AllocAndContext(allocNode,
2021: origVarAndContext.context));
2022: } else {
2023: if (badLocs.contains(allocNode)) {
2024: success = false;
2025: }
2026: }
2027: }
2028:
2029: @Override
2030: public void handleMatchSrc(VarNode matchSrc,
2031: PointsToSetInternal intersection, VarNode loadBase,
2032: VarNode storeBase, VarAndContext origVarAndContext,
2033: SparkField field, boolean refine) {
2034: AllocAndContextSet allocContexts = findContextsForAllocs(
2035: new VarAndContext(loadBase,
2036: origVarAndContext.context),
2037: intersection);
2038: for (AllocAndContext allocAndContext : allocContexts) {
2039: if (DEBUG) {
2040: debugPrint("alloc and context "
2041: + allocAndContext);
2042: }
2043: CallingContextSet matchSrcContexts;
2044: if (fieldCheckHeuristic.validFromBothEnds(field)) {
2045: matchSrcContexts = findUpContextsForVar(
2046: allocAndContext, new VarContextAndUp(
2047: storeBase, EMPTY_CALLSTACK,
2048: EMPTY_CALLSTACK));
2049: } else {
2050: matchSrcContexts = findVarContextsFromAlloc(
2051: allocAndContext, storeBase);
2052: }
2053: for (ImmutableStack<Integer> matchSrcContext : matchSrcContexts) {
2054: if (DEBUG)
2055: debugPrint("match source context "
2056: + matchSrcContext);
2057: VarAndContext newVarAndContext = new VarAndContext(
2058: matchSrc, matchSrcContext);
2059: p.prop(newVarAndContext);
2060: }
2061: }
2062: }
2063:
2064: Object getResult() {
2065: return Boolean.valueOf(success);
2066: }
2067:
2068: @Override
2069: void handleAssignSrc(VarAndContext newVarAndContext,
2070: VarAndContext origVarAndContext,
2071: AssignEdge assignEdge) {
2072: p.prop(newVarAndContext);
2073: }
2074:
2075: @Override
2076: boolean shouldHandleSrc(VarNode src) {
2077: if (doPointsTo) {
2078: return true;
2079: } else {
2080: return src.getP2Set().hasNonEmptyIntersection(
2081: badLocs);
2082: }
2083: }
2084:
2085: boolean terminate() {
2086: return !success;
2087: }
2088: };
2089: processIncomingEdges(edgeHandler, worklist);
2090: nesting--;
2091: return (Boolean) edgeHandler.getResult();
2092: }
2093:
2094: /*
2095: * (non-Javadoc)
2096: *
2097: * @see AAA.summary.Refiner#refineP2Set(soot.jimple.spark.pag.VarNode,
2098: * soot.jimple.spark.sets.PointsToSetInternal)
2099: */
2100: protected boolean refineP2Set(VarNode v,
2101: PointsToSetInternal badLocs, HeuristicType heuristic) {
2102: // G.v().out.println(badLocs);
2103: this .doPointsTo = false;
2104: this .fieldCheckHeuristic = HeuristicType.getHeuristic(
2105: heuristic, pag.getTypeManager(), getMaxPasses());
2106: try {
2107: numPasses = 0;
2108: while (true) {
2109: numPasses++;
2110: if (DEBUG_PASS != -1 && numPasses > DEBUG_PASS) {
2111: return false;
2112: }
2113: if (numPasses > maxPasses) {
2114: return false;
2115: }
2116: if (DEBUG) {
2117: G.v().out.println("PASS " + numPasses);
2118: G.v().out.println(fieldCheckHeuristic);
2119: }
2120: clearState();
2121: boolean success = false;
2122: try {
2123: success = refineP2Set(new VarAndContext(v,
2124: EMPTY_CALLSTACK), badLocs);
2125: } catch (TerminateEarlyException e) {
2126: success = false;
2127: }
2128: if (success) {
2129:
2130: return true;
2131: } else {
2132: if (!fieldCheckHeuristic.runNewPass()) {
2133: return false;
2134: }
2135: }
2136: }
2137: } finally {
2138: }
2139: }
2140:
2141: protected boolean weirdCall(Integer callSite) {
2142: SootMethod invokedMethod = csInfo.getInvokedMethod(callSite);
2143: return SootUtil.isThreadStartMethod(invokedMethod)
2144: || SootUtil.isNewInstanceMethod(invokedMethod);
2145: }
2146:
2147: /**
2148: * Currently not implemented.
2149: *
2150: * @throws UnsupportedOperationException
2151: * always
2152: */
2153: public PointsToSet reachingObjects(Context c, Local l) {
2154: throw new UnsupportedOperationException();
2155: }
2156:
2157: /**
2158: * Currently not implemented.
2159: *
2160: * @throws UnsupportedOperationException
2161: * always
2162: */
2163: public PointsToSet reachingObjects(Context c, Local l, SootField f) {
2164: throw new UnsupportedOperationException();
2165: }
2166:
2167: /**
2168: * Currently not implemented.
2169: *
2170: * @throws UnsupportedOperationException
2171: * always
2172: */
2173: public PointsToSet reachingObjects(Local l, SootField f) {
2174: throw new UnsupportedOperationException();
2175: }
2176:
2177: /**
2178: * Currently not implemented.
2179: *
2180: * @throws UnsupportedOperationException
2181: * always
2182: */
2183: public PointsToSet reachingObjects(PointsToSet s, SootField f) {
2184: throw new UnsupportedOperationException();
2185: }
2186:
2187: /**
2188: * Currently not implemented.
2189: *
2190: * @throws UnsupportedOperationException
2191: * always
2192: */
2193: public PointsToSet reachingObjects(SootField f) {
2194: throw new UnsupportedOperationException();
2195: }
2196:
2197: /**
2198: * Currently not implemented.
2199: *
2200: * @throws UnsupportedOperationException
2201: * always
2202: */
2203: public PointsToSet reachingObjectsOfArrayElement(PointsToSet s) {
2204: throw new UnsupportedOperationException();
2205: }
2206:
2207: /**
2208: * @return returns the (SPARK) pointer assignment graph
2209: */
2210: public PAG getPAG() {
2211: return pag;
2212: }
2213:
2214: /**
2215: * @return <code>true</code> is caching is enabled
2216: */
2217: public boolean usesCache() {
2218: return useCache;
2219: }
2220:
2221: /**
2222: * enables caching
2223: */
2224: public void enableCache() {
2225: useCache = true;
2226: }
2227:
2228: /**
2229: * disables caching
2230: */
2231: public void disableCache() {
2232: useCache = false;
2233: }
2234:
2235: /**
2236: * clears the cache
2237: */
2238: public void clearCache() {
2239: reachingObjectsCache.clear();
2240: reachingObjectsCacheNoCGRefinement.clear();
2241: }
2242:
2243: public boolean isRefineCallGraph() {
2244: return refineCallGraph;
2245: }
2246:
2247: public void setRefineCallGraph(boolean refineCallGraph) {
2248: this .refineCallGraph = refineCallGraph;
2249: }
2250:
2251: public HeuristicType getHeuristicType() {
2252: return heuristicType;
2253: }
2254:
2255: public void setHeuristicType(HeuristicType heuristicType) {
2256: this.heuristicType = heuristicType;
2257: clearCache();
2258: }
2259: }
|