001: /* Soot - a J*va Optimization Framework
002: * Copyright (C) 2007 Patrick Lam
003: *
004: * This library is free software; you can redistribute it and/or
005: * modify it under the terms of the GNU Lesser General Public
006: * License as published by the Free Software Foundation; either
007: * version 2.1 of the License, or (at your option) any later version.
008: *
009: * This library is distributed in the hope that it will be useful,
010: * but WITHOUT ANY WARRANTY; without even the implied warranty of
011: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
012: * Lesser General Public License for more details.
013: *
014: * You should have received a copy of the GNU Lesser General Public
015: * License along with this library; if not, write to the
016: * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
017: * Boston, MA 02111-1307, USA.
018: */
019: package soot.jimple.toolkits.pointer;
020:
021: import java.util.Collection;
022: import java.util.HashMap;
023: import java.util.HashSet;
024: import java.util.LinkedList;
025: import java.util.List;
026: import java.util.Set;
027:
028: import soot.Local;
029: import soot.RefLikeType;
030: import soot.Value;
031: import soot.jimple.DefinitionStmt;
032: import soot.jimple.NewExpr;
033: import soot.jimple.Stmt;
034: import soot.toolkits.graph.UnitGraph;
035: import soot.toolkits.scalar.ForwardFlowAnalysis;
036:
037: /** LocalNotMayAliasAnalysis attempts to determine if two local
038: * variables (at two potentially different program points) definitely
039: * point to different objects.
040: *
041: * The underlying abstraction is that of definition expressions. When
042: * a local variable gets assigned a new object (unlike LocalMust, only
043: * NewExprs), the analysis tracks the source of the value. If two
044: * variables have different sources, then they are different.
045: *
046: * See Sable TR 2007-8 for details.
047: *
048: * @author Patrick Lam
049: */
050: public class LocalMustNotAliasAnalysis extends ForwardFlowAnalysis {
051: protected static final Object UNKNOWN = new Object() {
052: public String toString() {
053: return "UNKNOWN";
054: }
055: };
056:
057: protected List<Local> locals;
058:
059: public LocalMustNotAliasAnalysis(UnitGraph g) {
060: super (g);
061: locals = new LinkedList<Local>();
062: locals.addAll(g.getBody().getLocals());
063:
064: for (Local l : (Collection<Local>) g.getBody().getLocals()) {
065: if (l.getType() instanceof RefLikeType)
066: locals.add(l);
067: }
068:
069: doAnalysis();
070: }
071:
072: protected void merge(Object in1, Object in2, Object o) {
073: HashMap inMap1 = (HashMap) in1;
074: HashMap inMap2 = (HashMap) in2;
075: HashMap outMap = (HashMap) o;
076:
077: for (Local l : locals) {
078: Set l1 = (Set) inMap1.get(l), l2 = (Set) inMap2.get(l);
079: Set out = (Set) outMap.get(l);
080: out.clear();
081: if (l1.contains(UNKNOWN) || l2.contains(UNKNOWN)) {
082: out.add(UNKNOWN);
083: } else {
084: out.addAll(l1);
085: out.addAll(l2);
086: }
087: }
088: }
089:
090: protected void flowThrough(Object inValue, Object unit,
091: Object outValue) {
092: HashMap in = (HashMap) inValue;
093: HashMap out = (HashMap) outValue;
094: Stmt s = (Stmt) unit;
095:
096: out.clear();
097: out.putAll(in);
098:
099: if (s instanceof DefinitionStmt) {
100: DefinitionStmt ds = (DefinitionStmt) s;
101: Value lhs = ds.getLeftOp();
102: Value rhs = ds.getRightOp();
103: if (lhs instanceof Local) {
104: HashSet lv = new HashSet();
105: out.put(lhs, lv);
106: if (rhs instanceof NewExpr) {
107: lv.add(rhs);
108: } else if (rhs instanceof Local) {
109: lv.addAll((HashSet) in.get(rhs));
110: } else
111: lv.add(UNKNOWN);
112: }
113: }
114: }
115:
116: protected void copy(Object source, Object dest) {
117: HashMap sourceMap = (HashMap) source;
118: HashMap destMap = (HashMap) dest;
119:
120: destMap.putAll(sourceMap);
121: }
122:
123: protected Object entryInitialFlow() {
124: HashMap m = new HashMap();
125: for (Local l : (Collection<Local>) locals) {
126: HashSet s = new HashSet();
127: s.add(UNKNOWN);
128: m.put(l, s);
129: }
130: return m;
131: }
132:
133: protected Object newInitialFlow() {
134: HashMap m = new HashMap();
135: for (Local l : (Collection<Local>) locals) {
136: HashSet s = new HashSet();
137: m.put(l, s);
138: }
139: return m;
140: }
141:
142: /**
143: * Returns true if this analysis has any information about local l
144: * at statement s (i.e. it is not {@link #UNKNOWN}).
145: * In particular, it is safe to pass in locals/statements that are not
146: * even part of the right method. In those cases <code>false</code>
147: * will be returned.
148: * Permits s to be <code>null</code>, in which case <code>false</code> will be returned.
149: */
150: public boolean hasInfoOn(Local l, Stmt s) {
151: HashMap flowBefore = (HashMap) getFlowBefore(s);
152: if (flowBefore == null) {
153: return false;
154: } else {
155: Set info = (Set) flowBefore.get(l);
156: return info != null && !info.contains(UNKNOWN);
157: }
158: }
159:
160: /**
161: * @return true if values of l1 (at s1) and l2 (at s2) are known
162: * to point to different objects
163: */
164: public boolean notMayAlias(Local l1, Stmt s1, Local l2, Stmt s2) {
165: Set l1n = (Set) ((HashMap) getFlowBefore(s1)).get(l1);
166: Set l2n = (Set) ((HashMap) getFlowBefore(s2)).get(l2);
167:
168: if (l1n.contains(UNKNOWN) || l2n.contains(UNKNOWN))
169: return false;
170:
171: Set n = new HashSet();
172: n.addAll(l1n);
173: n.retainAll(l2n);
174: return n.isEmpty();
175: }
176:
177: }
|