001/*
002 * Copyright (c) 2013, Oracle and/or its affiliates. All rights reserved.
003 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
004 *
005 * This code is free software; you can redistribute it and/or modify it
006 * under the terms of the GNU General Public License version 2 only, as
007 * published by the Free Software Foundation.
008 *
009 * This code is distributed in the hope that it will be useful, but WITHOUT
010 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
011 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
012 * version 2 for more details (a copy is included in the LICENSE file that
013 * accompanied this code).
014 *
015 * You should have received a copy of the GNU General Public License version
016 * 2 along with this work; if not, write to the Free Software Foundation,
017 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
018 *
019 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
020 * or visit www.oracle.com if you need additional information or have any
021 * questions.
022 */
023package com.oracle.graal.truffle;
024
025import java.util.*;
026
027import com.oracle.truffle.api.*;
028import com.oracle.truffle.api.nodes.*;
029
030public final class DefaultTruffleStamp {
031
032    private static final Object NO_TYPE = new Object();
033    private static final Class<?> NO_CLASS = new Object[]{}.getClass();
034    private static final Object NO_INSTANCE = new Object();
035
036    private DefaultTruffleStamp() {
037        // do not instantiate
038    }
039
040    public static TruffleStamp getInstance() {
041        return UninitializedStamp.INSTANCE;
042    }
043
044    private static TruffleStamp createStamp(Object value) {
045        if (value instanceof Object[]) {
046            return ArrayStamp.INSTANCE.joinValue(value);
047        } else if (!useInstanceStamps(value)) {
048            Object type = getTypeIdentifier(value);
049            assert value != null;
050            if (type != NO_TYPE) {
051                return new TypeStamp(value.getClass(), type);
052            } else {
053                return new ClassStamp(value.getClass());
054            }
055        } else {
056            return new InstanceStamp(value);
057        }
058    }
059
060    private static boolean useInstanceStamps(Object value) {
061        if (value == null) {
062            return true;
063        }
064        if (TruffleCompilerOptions.TruffleSplittingTypeInstanceStamps.getValue()) {
065            if (value instanceof TypedObject) {
066                return true;
067            }
068        }
069        if (TruffleCompilerOptions.TruffleSplittingClassInstanceStamps.getValue()) {
070            return true;
071        }
072        return false;
073    }
074
075    private static Object getTypeIdentifier(Object value) {
076        if (value instanceof TypedObject) {
077            return ((TypedObject) value).getTypeIdentifier();
078        }
079        return NO_TYPE;
080    }
081
082    private abstract static class ValueStamp implements TruffleStamp {
083
084        Class<?> getClazz() {
085            return NO_CLASS;
086        }
087
088        Object getType() {
089            return NO_TYPE;
090        }
091
092        Object getInstance() {
093            return NO_INSTANCE;
094        }
095
096        @Override
097        public final TruffleStamp joinValue(Object value) {
098            return join(createStamp(value));
099        }
100
101        public final String toStringShort() {
102            return getClass().getAnnotation(NodeInfo.class).shortName();
103        }
104
105        @Override
106        public String toString() {
107            return toStringShort();
108        }
109
110    }
111
112    @NodeInfo(shortName = "U")
113    private static final class UninitializedStamp extends ValueStamp {
114        private static final UninitializedStamp INSTANCE = new UninitializedStamp();
115
116        @Override
117        public TruffleStamp join(TruffleStamp p) {
118            return p;
119        }
120
121        @Override
122        public boolean isCompatible(Object value) {
123            return false;
124        }
125
126        @Override
127        public boolean equals(Object obj) {
128            return obj == INSTANCE;
129        }
130
131        @Override
132        public int hashCode() {
133            return 1;
134        }
135
136    }
137
138    @NodeInfo(shortName = "I")
139    private static final class InstanceStamp extends ValueStamp {
140
141        private final Object instance;
142        private final Class<?> clazz;
143        private final Object type;
144
145        public InstanceStamp(Object instance) {
146            this.instance = instance;
147            this.type = instance != null ? getTypeIdentifier(instance) : NO_TYPE;
148            this.clazz = instance != null ? instance.getClass() : NO_CLASS;
149        }
150
151        @Override
152        public TruffleStamp join(TruffleStamp p) {
153            if (p instanceof ValueStamp) {
154                ValueStamp ap = ((ValueStamp) p);
155                if (ap.getInstance() != NO_INSTANCE) {
156                    if (isCompatible(ap.getInstance())) {
157                        return this;
158                    }
159                }
160                if (ap.getType() != NO_TYPE) {
161                    if (type == ap.getType()) {
162                        return new TypeStamp(clazz, type);
163                    }
164                }
165                if (ap.getClazz() != NO_CLASS) {
166                    if (clazz == ap.getClazz()) {
167                        return new ClassStamp(clazz);
168                    }
169                }
170            }
171            return GenericStamp.INSTANCE;
172        }
173
174        @Override
175        public boolean isCompatible(Object value) {
176            return instance == value;
177        }
178
179        @Override
180        Object getInstance() {
181            return instance;
182        }
183
184        @Override
185        Object getType() {
186            return type;
187        }
188
189        @Override
190        Class<?> getClazz() {
191            return clazz;
192        }
193
194        @Override
195        public boolean equals(Object obj) {
196            return obj instanceof InstanceStamp && ((InstanceStamp) obj).instance == instance;
197        }
198
199        @Override
200        public int hashCode() {
201            if (instance != null) {
202                return instance.hashCode();
203            } else {
204                return 31;
205            }
206        }
207
208        @Override
209        public String toString() {
210            return String.format("%s=0x%8h", toStringShort(), System.identityHashCode(instance));
211        }
212
213    }
214
215    @NodeInfo(shortName = "T")
216    private static final class TypeStamp extends ValueStamp {
217
218        private final Class<?> clazz;
219        private final Object type;
220
221        public TypeStamp(Class<?> clazz, Object type) {
222            this.clazz = clazz;
223            this.type = type;
224            assert type != NO_TYPE;
225        }
226
227        @Override
228        public TruffleStamp join(TruffleStamp p) {
229            if (p instanceof ValueStamp) {
230                ValueStamp ap = ((ValueStamp) p);
231
232                if (ap.getType() != NO_TYPE) {
233                    if (type == ap.getType()) {
234                        return this;
235                    }
236                }
237                if (ap.getClazz() != NO_CLASS) {
238                    if (clazz == ap.getClazz()) {
239                        return new ClassStamp(clazz);
240                    }
241                }
242
243            }
244            return GenericStamp.INSTANCE;
245        }
246
247        @Override
248        public boolean isCompatible(Object value) {
249            return getTypeIdentifier(value) == type;
250        }
251
252        @Override
253        Class<?> getClazz() {
254            return clazz;
255        }
256
257        @Override
258        Object getType() {
259            return type;
260        }
261
262        @Override
263        public boolean equals(Object obj) {
264            return obj instanceof TypeStamp && ((TypeStamp) obj).type == type;
265        }
266
267        @Override
268        public int hashCode() {
269            return type.hashCode();
270        }
271
272        @Override
273        public String toString() {
274            return String.format("%s=0x%8h", toStringShort(), System.identityHashCode(type));
275        }
276
277    }
278
279    @NodeInfo(shortName = "C")
280    private static final class ClassStamp extends ValueStamp {
281
282        private final Class<?> clazz;
283
284        public ClassStamp(Class<?> clazz) {
285            this.clazz = clazz;
286        }
287
288        @Override
289        public boolean isCompatible(Object value) {
290            return value.getClass() == clazz;
291        }
292
293        @Override
294        public TruffleStamp join(TruffleStamp p) {
295            if (p instanceof ValueStamp) {
296                ValueStamp ap = ((ValueStamp) p);
297                if (ap.getClazz() != NO_CLASS) {
298                    if (clazz == ap.getClazz()) {
299                        return this;
300                    }
301                }
302            }
303            return GenericStamp.INSTANCE;
304        }
305
306        @Override
307        public boolean equals(Object obj) {
308            return obj instanceof ClassStamp && ((ClassStamp) obj).clazz == clazz;
309        }
310
311        @Override
312        public int hashCode() {
313            return clazz.hashCode();
314        }
315
316        @Override
317        Class<?> getClazz() {
318            return clazz;
319        }
320
321        @Override
322        public String toString() {
323            return String.format("%s=%-10s", toStringShort(), clazz.getSimpleName());
324        }
325
326    }
327
328    private static final class ArrayStamp implements TruffleStamp {
329
330        private static final ArrayStamp INSTANCE = new ArrayStamp(getInstance());
331
332        private static final int MAX_STAMPED_ARGUMENTS = 10;
333        private static final int GENERIC_LENGTH = -1;
334        private static final int UNINITIALIZED_LENGTH = -2;
335
336        private final TruffleStamp[] stampArray;
337        private final int length;
338
339        public ArrayStamp(TruffleStamp stamp) {
340            this.stampArray = new TruffleStamp[MAX_STAMPED_ARGUMENTS];
341            Arrays.fill(this.stampArray, stamp);
342            this.length = UNINITIALIZED_LENGTH;
343        }
344
345        public ArrayStamp(TruffleStamp[] profiledTypes, int length) {
346            this.stampArray = profiledTypes;
347            this.length = length;
348        }
349
350        public boolean isCompatible(Object value) {
351            if (!(value instanceof Object[])) {
352                return false;
353            }
354            Object[] array = (Object[]) value;
355            if ((length != array.length && length != GENERIC_LENGTH) || length == UNINITIALIZED_LENGTH) {
356                return false;
357            }
358            TruffleStamp[] currentArray = this.stampArray;
359            for (int i = 0; i < Math.min(array.length, currentArray.length); i++) {
360                if (!currentArray[i].isCompatible(array[i])) {
361                    return false;
362                }
363            }
364            return true;
365        }
366
367        public TruffleStamp join(TruffleStamp p) {
368            if (!(p instanceof ArrayStamp)) {
369                return GenericStamp.INSTANCE;
370            }
371            ArrayStamp other = (ArrayStamp) p;
372            int newLength = profileLength(other.length);
373
374            TruffleStamp[] newArray = this.stampArray;
375            TruffleStamp[] otherArray = other.stampArray;
376            assert newArray.length == otherArray.length;
377
378            for (int i = 0; i < newArray.length; i++) {
379                TruffleStamp thisStamp = newArray[i];
380                TruffleStamp newStamp = thisStamp.join(otherArray[i]);
381
382                if (thisStamp != newStamp) {
383                    if (newArray == this.stampArray) {
384                        newArray = Arrays.copyOf(newArray, newArray.length);
385                    }
386                    newArray[i] = newStamp;
387                }
388            }
389            return create(newArray, newLength);
390        }
391
392        public TruffleStamp joinValue(Object value) {
393            if (!(value instanceof Object[])) {
394                return GenericStamp.INSTANCE;
395            }
396            Object[] array = (Object[]) value;
397            int newLength = profileLength(array.length);
398            TruffleStamp[] newArray = this.stampArray;
399            for (int i = 0; i < Math.min(array.length, newArray.length); i++) {
400                TruffleStamp oldStamp = newArray[i];
401                Object newValue = array[i];
402                if (!oldStamp.isCompatible(newValue)) {
403                    if (newArray == this.stampArray) {
404                        newArray = Arrays.copyOf(newArray, newArray.length);
405                    }
406                    newArray[i] = oldStamp.joinValue(newValue);
407                }
408            }
409            return create(newArray, newLength);
410        }
411
412        private TruffleStamp create(TruffleStamp[] newArray, int newLength) {
413            if (newLength != this.length || newArray != this.stampArray) {
414                return new ArrayStamp(newArray != null ? newArray : stampArray, newLength);
415            } else {
416                return this;
417            }
418        }
419
420        private int profileLength(int arrayLength) {
421            int nextLength = this.length;
422            switch (nextLength) {
423                case UNINITIALIZED_LENGTH:
424                    return arrayLength;
425                case GENERIC_LENGTH:
426                    return nextLength;
427                default:
428                    if (nextLength != arrayLength) {
429                        if (arrayLength == UNINITIALIZED_LENGTH) {
430                            return nextLength;
431                        } else {
432                            return GENERIC_LENGTH;
433                        }
434                    } else {
435                        return nextLength;
436                    }
437            }
438
439        }
440
441        @Override
442        public int hashCode() {
443            return 31 * (31 + length) + Arrays.hashCode(stampArray);
444        }
445
446        @Override
447        public boolean equals(Object obj) {
448            if (!(obj instanceof ArrayStamp)) {
449                return false;
450            }
451            ArrayStamp a = (ArrayStamp) obj;
452            if (a.length != length) {
453                return false;
454            }
455            return Arrays.equals(a.stampArray, stampArray);
456        }
457
458        public String toStringShort() {
459            if (length == 0) {
460                return "[]";
461            }
462            StringBuilder b = new StringBuilder("[");
463            for (TruffleStamp stamp : stampArray) {
464                if (stamp instanceof UninitializedStamp) {
465                    continue;
466                }
467                if (stamp instanceof ValueStamp) {
468                    b.append(((ValueStamp) stamp).toStringShort());
469                } else if (stamp instanceof ArrayStamp) {
470                    b.append(((ArrayStamp) stamp).toStringShort());
471                } else {
472                    b.append("?");
473                }
474            }
475            b.append("]");
476
477            b.append(".").append(formatLength());
478            return b.toString();
479        }
480
481        @Override
482        public String toString() {
483            return "Array(length=" + formatLength() + ", " + Arrays.toString(stampArray) + ")";
484        }
485
486        private String formatLength() {
487            String lengthString;
488            if (length == GENERIC_LENGTH) {
489                lengthString = "G";
490            } else if (length == UNINITIALIZED_LENGTH) {
491                lengthString = "U";
492            } else {
493                lengthString = String.valueOf(this.length);
494            }
495            return lengthString;
496        }
497
498    }
499
500    @NodeInfo(shortName = "G")
501    private static final class GenericStamp extends ValueStamp {
502
503        private static final GenericStamp INSTANCE = new GenericStamp();
504
505        @Override
506        public boolean isCompatible(Object value) {
507            return true;
508        }
509
510        @Override
511        public TruffleStamp join(TruffleStamp p) {
512            return this;
513        }
514
515        @Override
516        public boolean equals(Object obj) {
517            return obj == INSTANCE;
518        }
519
520        @Override
521        public int hashCode() {
522            return 31;
523        }
524
525    }
526
527}