001: /* Copyright (C) 2004 - 2007 db4objects Inc. http://www.db4o.com
002:
003: This file is part of the db4o open source object database.
004:
005: db4o is free software; you can redistribute it and/or modify it under
006: the terms of version 2 of the GNU General Public License as published
007: by the Free Software Foundation and as clarified by db4objects' GPL
008: interpretation policy, available at
009: http://www.db4o.com/about/company/legalpolicies/gplinterpretation/
010: Alternatively you can write to db4objects, Inc., 1900 S Norfolk Street,
011: Suite 350, San Mateo, CA 94403, USA.
012:
013: db4o is distributed in the hope that it will be useful, but WITHOUT ANY
014: WARRANTY; without even the implied warranty of MERCHANTABILITY or
015: FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
016: for more details.
017:
018: You should have received a copy of the GNU General Public License along
019: with this program; if not, write to the Free Software Foundation, Inc.,
020: 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */
021: package EDU.purdue.cs.bloat.tbaa;
022:
023: import EDU.purdue.cs.bloat.editor.*;
024: import EDU.purdue.cs.bloat.tree.*;
025: import EDU.purdue.cs.bloat.util.*;
026:
027: /**
028: * Performs Type-Based Alias Analysis (TBAA) to determine if one expression can
029: * alias another. An expression may alias another expression if there is the
030: * possibility that they refer to the same location in memory. BLOAT models
031: * expressions that may reference memory locations with <tt>MemRefExpr</tt>s.
032: * There are two kinds of "access expressions" in Java: field accesses (<tt>FieldExpr</tt>
033: * and <tt>StaticFieldExpr</tt>) and array references (<tt>ArrayRefExpr</tt>).
034: * Access paths consist of one or more access expressions. For instance,
035: * <tt>a.b[i].c</tt> is an access expression.
036: *
037: * <p>
038: *
039: * TBAA uses the FieldTypeDecl relation to determine whether or not two access
040: * paths may refer to the same memory location.
041: *
042: * <p>
043: *
044: * <table>
045: * <th>
046: * <td>AP1 </td>
047: * <td>AP2 </td>
048: * <td>FieldTypeDecl(AP1, Ap2)</td>
049: * </th>
050: * <tr>
051: * <Td>p </td>
052: * <Td>p </td>
053: * <td>true </td>
054: * </tr>
055: * <tr>
056: * <td>p.f </td>
057: * <td>q.g </td>
058: * <td>(f = g) && FieldTypeDecl(p, q)</td>
059: * </tr>
060: * <tr>
061: * <td>p.f </td>
062: * <Td>q[i]</td>
063: * <td>false </td>
064: * </tr>
065: * <tr>
066: * <td>p[i]</td>
067: * <td>q[j]</td>
068: * <td>FieldTypeDecl(p, q) </td>
069: * </tr>
070: * <tr>
071: * <td>p </td>
072: * <td>q </td>
073: * <td>TypeDecl(p, q) </td>
074: * </tr>
075: * </table>
076: *
077: * <p>
078: *
079: * The TypeDecl(AP1, AP2) relation is defined as:
080: * <p align=center>
081: * Subtypes(Type(AP1)) INTERSECT Subtypes(Type(AP2)) != EMPTY
082: * </p>
083: *
084: * The subtype relationships are determined by the <tt>ClassHierarchy</tt>.
085: *
086: * @see ClassHierarchy
087: * @see MemRefExpr
088: * @see FieldExpr
089: * @see StaticFieldExpr
090: * @see ArrayRefExpr
091: */
092: public class TBAA {
093:
094: /**
095: * Returns true, if expression <tt>a</tt> can alias expression <tt>b</tt>.
096: */
097: public static boolean canAlias(final EditorContext context,
098: final Expr a, final Expr b) {
099: // Only memory reference expressions can have aliases.
100: if (!(a instanceof MemRefExpr)) {
101: return false;
102: }
103:
104: // Only memory reference expressions can have aliases.
105: if (!(b instanceof MemRefExpr)) {
106: return false;
107: }
108:
109: // Equal expressions can be aliases.
110: if (a.equalsExpr(b)) {
111: return true;
112: }
113:
114: MemberRef af = null; // Field accessed by expression a
115: MemberRef bf = null; // Field accessed by expression b
116:
117: if (a instanceof FieldExpr) {
118: af = ((FieldExpr) a).field();
119: }
120:
121: if (a instanceof StaticFieldExpr) {
122: af = ((StaticFieldExpr) a).field();
123: }
124:
125: if (b instanceof FieldExpr) {
126: bf = ((FieldExpr) b).field();
127: }
128:
129: if (b instanceof StaticFieldExpr) {
130: bf = ((StaticFieldExpr) b).field();
131: }
132:
133: // Arrays and fields cannot alias the same location.
134: if ((a instanceof ArrayRefExpr) && (bf != null)) {
135: return false;
136: }
137:
138: // Arrays and fields cannot alias the same location.
139: if ((b instanceof ArrayRefExpr) && (af != null)) {
140: return false;
141: }
142:
143: final ClassHierarchy hier = context.getHierarchy();
144:
145: // Only type-compatible arrays can alias the same location.
146: if ((a instanceof ArrayRefExpr) && (b instanceof ArrayRefExpr)) {
147: final ArrayRefExpr aa = (ArrayRefExpr) a;
148: final ArrayRefExpr bb = (ArrayRefExpr) b;
149:
150: final Type aaIndexType = aa.index().type();
151: final Type bbIndexType = bb.index().type();
152: final Type aaArrayType = aa.array().type();
153: final Type bbArrayType = bb.array().type();
154:
155: Assert.isTrue(aaIndexType.isIntegral(), aa.index() + " in "
156: + aa + " (" + aaIndexType + ") is not an integer");
157: Assert.isTrue(bbIndexType.isIntegral(), bb.index() + " in "
158: + bb + " (" + bbIndexType + ") is not an integer");
159: Assert.isTrue(aaArrayType.isArray()
160: || aaArrayType.equals(Type.OBJECT)
161: || aaArrayType.equals(Type.SERIALIZABLE)
162: || aaArrayType.equals(Type.CLONEABLE)
163: || aaArrayType.isNull(), aa.array() + " in " + aa
164: + " (" + aaArrayType + ") is not an array");
165: Assert.isTrue(bbArrayType.isArray()
166: || bbArrayType.equals(Type.OBJECT)
167: || bbArrayType.equals(Type.SERIALIZABLE)
168: || bbArrayType.equals(Type.CLONEABLE)
169: || bbArrayType.isNull(), bb.array() + " in " + bb
170: + " (" + bbArrayType + ") is not an array");
171:
172: // Optimization: if constant indices. Only equal indices can
173: // alias the same location.
174: if ((aa.index() instanceof ConstantExpr)
175: && (bb.index() instanceof ConstantExpr)) {
176:
177: final ConstantExpr ai = (ConstantExpr) aa.index();
178: final ConstantExpr bi = (ConstantExpr) bb.index();
179:
180: if ((ai.value() != null) && (bi.value() != null)) {
181: if (!ai.value().equals(bi.value())) {
182: return false;
183: }
184: }
185: }
186:
187: return TBAA.intersects(hier, aaArrayType, bbArrayType);
188: }
189:
190: try {
191: if (af != null) {
192: final FieldEditor e = context.editField(af);
193:
194: if (e.isVolatile()) {
195: context.release(e.fieldInfo());
196: return true;
197: }
198:
199: if (e.isFinal()) {
200: context.release(e.fieldInfo());
201: return false;
202: }
203:
204: context.release(e.fieldInfo());
205: }
206:
207: if (bf != null) {
208: final FieldEditor e = context.editField(bf);
209:
210: if (e.isVolatile()) {
211: context.release(e.fieldInfo());
212: return true;
213: }
214:
215: if (e.isFinal()) {
216: context.release(e.fieldInfo());
217: return false;
218: }
219:
220: context.release(e.fieldInfo());
221: }
222:
223: } catch (final NoSuchFieldException e) {
224: // A field wasn't found. Silently assume there is an alias.
225: return true;
226: }
227:
228: // Only fields with the same name can alias the same location.
229: if ((af != null) && (bf != null)) {
230: return af.equals(bf);
231: }
232:
233: // Default case. This shouldn't happen.
234: return TBAA.intersects(hier, a.type(), b.type());
235: }
236:
237: /**
238: * Returns <tt>true</tt> if type a and type c intersect. That is, the two
239: * types have a non-null intersection.
240: */
241: private static boolean intersects(final ClassHierarchy hier,
242: final Type a, final Type b) {
243: return !hier.intersectType(a, b).isNull();
244: }
245: }
|