View Javadoc
1   /*
2    * Copyright (c) 2010, 2013, Oracle and/or its affiliates. All rights reserved.
3    * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4    *
5    * This code is free software; you can redistribute it and/or modify it
6    * under the terms of the GNU General Public License version 2 only, as
7    * published by the Free Software Foundation.  Oracle designates this
8    * particular file as subject to the "Classpath" exception as provided
9    * by Oracle in the LICENSE file that accompanied this code.
10   *
11   * This code is distributed in the hope that it will be useful, but WITHOUT
12   * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13   * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
14   * version 2 for more details (a copy is included in the LICENSE file that
15   * accompanied this code).
16   *
17   * You should have received a copy of the GNU General Public License version
18   * 2 along with this work; if not, write to the Free Software Foundation,
19   * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20   *
21   * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22   * or visit www.oracle.com if you need additional information or have any
23   * questions.
24   */
25  
26  package jdk.nashorn.internal.codegen.types;
27  
28  import java.util.Arrays;
29  import java.util.Collections;
30  import java.util.List;
31  
32  import jdk.nashorn.internal.runtime.DebugLogger;
33  import jdk.nashorn.internal.runtime.JSType;
34  
35  /**
36   * Represents the value range of a symbol.
37   */
38  public abstract class Range {
39  
40      private static final Range GENERIC_RANGE = new Range() {
41          @Override
42          public Type getType() {
43              return Type.OBJECT;
44          }
45      };
46  
47      private static final Range NUMBER_RANGE = new Range() {
48          @Override
49          public Type getType() {
50              return Type.NUMBER;
51          }
52      };
53  
54      private static final Range UNKNOWN_RANGE = new Range() {
55          @Override
56          public Type getType() {
57              return Type.UNKNOWN;
58          }
59  
60          @Override
61          public boolean isUnknown() {
62              return true;
63          }
64      };
65  
66      private static class IntegerRange extends Range {
67          private final long min;
68          private final long max;
69          private final Type type;
70  
71          private IntegerRange(final long min, final long max) {
72              assert min <= max;
73              this.min  = min;
74              this.max  = max;
75              this.type = typeFromRange(min, max);
76          }
77  
78          private static Type typeFromRange(final long from, final long to) {
79              if (from >= Integer.MIN_VALUE && to <= Integer.MAX_VALUE) {
80                  return Type.INT;
81              }
82              return Type.LONG;
83          }
84  
85          @Override
86          public Type getType() {
87              return type;
88          }
89  
90          public long getMin() {
91              return min;
92          }
93  
94          public long getMax() {
95              return max;
96          }
97  
98          @Override
99          public boolean isIntegerConst() {
100             return getMin() == getMax();
101         }
102 
103         private long getBitMask() {
104             if (min == max) {
105                 return min;
106             }
107 
108             if (min < 0) {
109                 return ~0L;
110             }
111 
112             long mask = 1;
113             while (mask < max) {
114                 mask = (mask << 1) | 1;
115             }
116             return mask;
117         }
118 
119         @Override
120         public boolean equals(final Object obj) {
121             if (obj instanceof IntegerRange) {
122                 final IntegerRange other = (IntegerRange)obj;
123                 return this.type == other.type && this.min == other.min && this.max == other.max;
124             }
125             return false;
126         }
127 
128         @Override
129         public int hashCode() {
130             return Long.hashCode(min) ^ Long.hashCode(max);
131         }
132 
133         @Override
134         public String toString() {
135             return super.toString() + "[" + min +", " + max + "]";
136         }
137     }
138 
139     /**
140      * Get narrowest type for this range
141      * @return type
142      */
143     public abstract Type getType();
144 
145     /**
146      * Is this range unknown
147      * @return true if unknown
148      */
149     public boolean isUnknown() {
150         return false;
151     }
152 
153     /**
154      * Check if an integer is enough to span this range
155      * @return true if integer is enough
156      */
157     public boolean isIntegerType() {
158         return this instanceof IntegerRange;
159     }
160 
161     /**
162      * Check if an integer is enough to span this range
163      * @return true if integer is enough
164      */
165     public boolean isIntegerConst() {
166         return false;
167     }
168 
169     /**
170      * Create an unknown range - this is most likely a singleton object
171      * and it represents "we have no known range information"
172      * @return the range
173      */
174     public static Range createUnknownRange() {
175         return UNKNOWN_RANGE;
176     }
177 
178     /**
179      * Create a constant range: [value, value]
180      * @param value value
181      * @return the range
182      */
183     public static Range createRange(final int value) {
184         return createIntegerRange(value, value);
185     }
186 
187     /**
188      * Create a constant range: [value, value]
189      * @param value value
190      * @return the range
191      */
192     public static Range createRange(final long value) {
193         return createIntegerRange(value, value);
194     }
195 
196     /**
197      * Create a constant range: [value, value]
198      * @param value value
199      * @return the range
200      */
201     public static Range createRange(final double value) {
202         if (isRepresentableAsLong(value)) {
203             return createIntegerRange((long) value, (long) value);
204         }
205         return createNumberRange();
206     }
207 
208     /**
209      * Create a constant range: [value, value]
210      * @param value value
211      * @return the range
212      */
213     public static Range createRange(final Object value) {
214         if (value instanceof Integer) {
215             return createRange((int)value);
216         } else if (value instanceof Long) {
217             return createRange((long)value);
218         } else if (value instanceof Double) {
219             return createRange((double)value);
220         }
221 
222         return createGenericRange();
223     }
224 
225     /**
226      * Create a generic range - object symbol that carries no range
227      * information
228      * @return the range
229      */
230     public static Range createGenericRange() {
231         return GENERIC_RANGE;
232     }
233 
234     /**
235      * Create a number range - number symbol that carries no range
236      * information
237      * @return the range
238      */
239     public static Range createNumberRange() {
240         return NUMBER_RANGE;
241     }
242 
243     /**
244      * Create an integer range [min, max]
245      * @param min minimum value, inclusive
246      * @param max maximum value, inclusive
247      * @return the range
248      */
249     public static IntegerRange createIntegerRange(final long min, final long max) {
250         return new IntegerRange(min, max);
251     }
252 
253     /**
254      * Create an integer range of maximum type width for the given type
255      * @param type the type
256      * @return the range
257      */
258     public static IntegerRange createIntegerRange(final Type type) {
259         assert type.isNumeric() && !type.isNumber();
260         final long min;
261         final long max;
262         if (type.isInteger()) {
263             min = Integer.MIN_VALUE;
264             max = Integer.MAX_VALUE;
265         } else if (type.isLong()) {
266             min = Long.MIN_VALUE;
267             max = Long.MAX_VALUE;
268         } else {
269             throw new AssertionError(); //type incompatible with integer range
270         }
271         return new IntegerRange(min, max);
272     }
273 
274     /**
275      * Create an range of maximum type width for the given type
276      * @param type the type
277      * @return the range
278      */
279     public static Range createTypeRange(final Type type) {
280         if (type.isNumber()) {
281             return createNumberRange();
282         } else if (type.isNumeric()) {
283             return createIntegerRange(type);
284         } else {
285             return createGenericRange();
286         }
287     }
288 
289     // check that add doesn't overflow
290     private static boolean checkAdd(final long a, final long b) {
291         final long result = a + b;
292         return ((a ^ result) & (b ^ result)) >= 0;
293     }
294 
295     // check that sub doesn't overflow
296     private static boolean checkSub(final long a, final long b) {
297         final long result = a - b;
298         return ((a ^ result) & (b ^ result)) >= 0;
299     }
300 
301     private static boolean checkMul(final long a, final long b) {
302         // TODO correct overflow check
303         return a >= Integer.MIN_VALUE && a <= Integer.MAX_VALUE && b >= Integer.MIN_VALUE && b <= Integer.MAX_VALUE;
304     }
305 
306     /**
307      * The range functionality class responsible for merging ranges and drawing
308      * range conclusions from operations executed
309      */
310     public static class Functionality {
311         /** logger */
312         protected final DebugLogger log;
313 
314         /**
315          * Constructor
316          * @param log logger
317          */
318         public Functionality(final DebugLogger log) {
319             this.log = log;
320         }
321 
322         /**
323          * Join two ranges
324          * @param a first range
325          * @param b second range
326          * @return the joined range
327          */
328         public Range join(final Range a, final Range b) {
329             if (a.equals(b)) {
330                 return a;
331             }
332 
333             Type joinedType = a.getType();
334             if (a.getType() != b.getType()) {
335                 if (a.isUnknown()) {
336                     return b;
337                 }
338                 if (b.isUnknown()) {
339                     return a;
340                 }
341 
342                 joinedType = Type.widest(a.getType(), b.getType());
343             }
344 
345             if (joinedType.isInteger() || joinedType.isLong()) {
346                 return createIntegerRange(
347                         Math.min(((IntegerRange) a).getMin(), ((IntegerRange) b).getMin()),
348                         Math.max(((IntegerRange) a).getMax(), ((IntegerRange) b).getMax()));
349             }
350 
351             return createTypeRange(joinedType);
352         }
353 
354         /**
355          * Add operation
356          * @param a range of first symbol to be added
357          * @param b range of second symbol to be added
358          * @return resulting range representing the value range after add
359          */
360         public Range add(final Range a, final Range b) {
361             if (a.isIntegerType() && b.isIntegerType()) {
362                 final IntegerRange lhs = (IntegerRange)a;
363                 final IntegerRange rhs = (IntegerRange)b;
364                 if (checkAdd(lhs.getMin(), rhs.getMin()) && checkAdd(lhs.getMax(), rhs.getMax())) {
365                     return createIntegerRange(lhs.getMin() + rhs.getMin(), lhs.getMax() + rhs.getMax());
366                 }
367             }
368 
369             if (a.getType().isNumeric() && b.getType().isNumeric()) {
370                 return createNumberRange();
371             }
372 
373             return createGenericRange();
374         }
375 
376         /**
377          * Sub operation
378          * @param a range of first symbol to be subtracted
379          * @param b range of second symbol to be subtracted
380          * @return resulting range representing the value range after subtraction
381          */
382         public Range sub(final Range a, final Range b) {
383             if (a.isIntegerType() && b.isIntegerType()) {
384                 final IntegerRange lhs = (IntegerRange)a;
385                 final IntegerRange rhs = (IntegerRange)b;
386                 if (checkSub(lhs.getMin(), rhs.getMax()) && checkSub(lhs.getMax(), rhs.getMin())) {
387                     return createIntegerRange(lhs.getMin() - rhs.getMax(), lhs.getMax() - rhs.getMin());
388                 }
389             }
390 
391             if (a.getType().isNumeric() && b.getType().isNumeric()) {
392                 return createNumberRange();
393             }
394 
395             return createGenericRange();
396         }
397 
398         /**
399          * Mul operation
400          * @param a range of first symbol to be multiplied
401          * @param b range of second symbol to be multiplied
402          * @return resulting range representing the value range after multiplication
403          */
404         public Range mul(final Range a, final Range b) {
405             if (a.isIntegerType() && b.isIntegerType()) {
406                 final IntegerRange lhs = (IntegerRange)a;
407                 final IntegerRange rhs = (IntegerRange)b;
408 
409                 //ensure that nothing ever overflows or underflows
410                 if (checkMul(lhs.getMin(), rhs.getMin()) &&
411                     checkMul(lhs.getMax(), rhs.getMax()) &&
412                     checkMul(lhs.getMin(), rhs.getMax()) &&
413                     checkMul(lhs.getMax(), rhs.getMin())) {
414 
415                     final List<Long> results =
416                         Arrays.asList(
417                             lhs.getMin() * rhs.getMin(),
418                             lhs.getMin() * rhs.getMax(),
419                             lhs.getMax() * rhs.getMin(),
420                             lhs.getMax() * rhs.getMax());
421                     return createIntegerRange(Collections.min(results), Collections.max(results));
422                 }
423             }
424 
425             if (a.getType().isNumeric() && b.getType().isNumeric()) {
426                 return createNumberRange();
427             }
428 
429             return createGenericRange();
430         }
431 
432         /**
433          * Neg operation
434          * @param a range of value symbol to be negated
435          * @return resulting range representing the value range after neg
436          */
437         public Range neg(final Range a) {
438             if (a.isIntegerType()) {
439                 final IntegerRange rhs = (IntegerRange)a;
440                 if (rhs.getMin() != Long.MIN_VALUE && rhs.getMax() != Long.MIN_VALUE) {
441                     return createIntegerRange(-rhs.getMax(), -rhs.getMin());
442                 }
443             }
444 
445             if (a.getType().isNumeric()) {
446                 return createNumberRange();
447             }
448 
449             return createGenericRange();
450         }
451 
452         /**
453          * Bitwise and operation
454          * @param a range of first symbol to be and:ed
455          * @param b range of second symbol to be and:ed
456          * @return resulting range representing the value range after and
457          */
458         public Range and(final Range a, final Range b) {
459             if (a.isIntegerType() && b.isIntegerType()) {
460                 final int resultMask = (int) (((IntegerRange)a).getBitMask() & ((IntegerRange)b).getBitMask());
461                 if (resultMask >= 0) {
462                     return createIntegerRange(0, resultMask);
463                 }
464             } else if (a.isUnknown() && b.isIntegerType()) {
465                 final long operandMask = ((IntegerRange)b).getBitMask();
466                 if (operandMask >= 0) {
467                     return createIntegerRange(0, operandMask);
468                 }
469             } else if (a.isIntegerType() && b.isUnknown()) {
470                 final long operandMask = ((IntegerRange)a).getBitMask();
471                 if (operandMask >= 0) {
472                     return createIntegerRange(0, operandMask);
473                 }
474             }
475 
476             return createTypeRange(Type.INT);
477         }
478 
479         /**
480          * Bitwise or operation
481          * @param a range of first symbol to be or:ed
482          * @param b range of second symbol to be or:ed
483          * @return resulting range representing the value range after or
484          */
485         public Range or(final Range a, final Range b) {
486             if (a.isIntegerType() && b.isIntegerType()) {
487                 final int resultMask = (int)(((IntegerRange)a).getBitMask() | ((IntegerRange)b).getBitMask());
488                 if (resultMask >= 0) {
489                     return createIntegerRange(0, resultMask);
490                 }
491             }
492 
493             return createTypeRange(Type.INT);
494         }
495 
496         /**
497          * Bitwise xor operation
498          * @param a range of first symbol to be xor:ed
499          * @param b range of second symbol to be xor:ed
500          * @return resulting range representing the value range after and
501          */
502         public Range xor(final Range a, final Range b) {
503             if (a.isIntegerConst() && b.isIntegerConst()) {
504                 return createRange(((IntegerRange)a).getMin() ^ ((IntegerRange)b).getMin());
505             }
506 
507             if (a.isIntegerType() && b.isIntegerType()) {
508                 final int resultMask = (int)(((IntegerRange)a).getBitMask() | ((IntegerRange)b).getBitMask());
509                 if (resultMask >= 0) {
510                     return createIntegerRange(0, createIntegerRange(0, resultMask).getBitMask());
511                 }
512             }
513             return createTypeRange(Type.INT);
514         }
515 
516         /**
517          * Bitwise shl operation
518          * @param a range of first symbol to be shl:ed
519          * @param b range of second symbol to be shl:ed
520          * @return resulting range representing the value range after shl
521          */
522         public Range shl(final Range a, final Range b) {
523             if (b.isIntegerType() && b.isIntegerConst()) {
524                 final IntegerRange left  = (IntegerRange)(a.isIntegerType() ? a : createTypeRange(Type.INT));
525                 final int          shift = (int)((IntegerRange) b).getMin() & 0x1f;
526                 final int          min   = (int)left.getMin() << shift;
527                 final int          max   = (int)left.getMax() << shift;
528                 if (min >> shift == left.getMin() && max >> shift == left.getMax()) {
529                     return createIntegerRange(min, max);
530                 }
531             }
532 
533             return createTypeRange(Type.INT);
534         }
535 
536         /**
537          * Bitwise shr operation
538          * @param a range of first symbol to be shr:ed
539          * @param b range of second symbol to be shr:ed
540          * @return resulting range representing the value range after shr
541          */
542         public Range shr(final Range a, final Range b) {
543             if (b.isIntegerType() && b.isIntegerConst()) {
544                 final long         shift = ((IntegerRange) b).getMin() & 0x1f;
545                 final IntegerRange left  = (IntegerRange)(a.isIntegerType() ? a : createTypeRange(Type.INT));
546                 if (left.getMin() >= 0) {
547                     long min = left.getMin() >>> shift;
548                     long max = left.getMax() >>> shift;
549                     return createIntegerRange(min, max);
550                 } else if (shift >= 1) {
551                     return createIntegerRange(0, JSType.MAX_UINT >>> shift);
552                 }
553             }
554 
555             return createTypeRange(Type.INT);
556         }
557 
558         /**
559          * Bitwise sar operation
560          * @param a range of first symbol to be sar:ed
561          * @param b range of second symbol to be sar:ed
562          * @return resulting range representing the value range after sar
563          */
564         public Range sar(final Range a, final Range b) {
565             if (b.isIntegerType() && b.isIntegerConst()) {
566                 final IntegerRange left  = (IntegerRange)(a.isIntegerType() ? a : createTypeRange(Type.INT));
567                 final long         shift = ((IntegerRange) b).getMin() & 0x1f;
568                 final long         min   = left.getMin() >> shift;
569                 final long         max   = left.getMax() >> shift;
570                 return createIntegerRange(min, max);
571             }
572 
573             return createTypeRange(Type.INT);
574         }
575 
576         /**
577          * Modulo operation
578          * @param a range of first symbol to the mod operation
579          * @param b range of second symbol to be mod operation
580          * @return resulting range representing the value range after mod
581          */
582         public Range mod(final Range a, final Range b) {
583             if (a.isIntegerType() && b.isIntegerType()) {
584                 final IntegerRange rhs = (IntegerRange) b;
585                 if (rhs.getMin() > 0 || rhs.getMax() < 0) { // divisor range must not include 0
586                     final long absmax = Math.max(Math.abs(rhs.getMin()), Math.abs(rhs.getMax())) - 1;
587                     return createIntegerRange(rhs.getMin() > 0 ? 0 : -absmax, rhs.getMax() < 0 ? 0 : +absmax);
588                 }
589             }
590             return createTypeRange(Type.NUMBER);
591         }
592 
593         /**
594          * Division operation
595          * @param a range of first symbol to the division
596          * @param b range of second symbol to be division
597          * @return resulting range representing the value range after division
598          */
599         public Range div(final Range a, final Range b) {
600             // TODO
601             return createTypeRange(Type.NUMBER);
602         }
603     }
604 
605     /**
606      * Simple trace functionality that will log range creation
607      */
608     public static class TraceFunctionality extends Functionality {
609         TraceFunctionality(final DebugLogger log) {
610             super(log);
611         }
612 
613         private Range trace(final Range result, final String operation, final Range... operands) {
614             log.fine("range::" + operation + Arrays.toString(operands) + " => " + result);
615             return result;
616         }
617 
618         @Override
619         public Range join(final Range a, final Range b) {
620             final Range result = super.join(a, b);
621             if (!a.equals(b)) {
622                 trace(result, "join", a, b);
623             }
624             return result;
625         }
626 
627         @Override
628         public Range add(final Range a, final Range b) {
629             return trace(super.add(a, b), "add", a, b);
630         }
631 
632         @Override
633         public Range sub(final Range a, final Range b) {
634             return trace(super.sub(a, b), "sub", a, b);
635         }
636 
637         @Override
638         public Range mul(final Range a, final Range b) {
639             return trace(super.mul(a, b), "mul", a, b);
640         }
641 
642         @Override
643         public Range neg(final Range a) {
644             return trace(super.neg(a), "neg", a);
645         }
646 
647         @Override
648         public Range and(final Range a, final Range b) {
649             return trace(super.and(a, b), "and", a, b);
650         }
651 
652         @Override
653         public Range or(final Range a, final Range b) {
654             return trace(super.or(a, b), "or", a, b);
655         }
656 
657         @Override
658         public Range xor(final Range a, final Range b) {
659             return trace(super.xor(a, b), "xor", a, b);
660         }
661 
662         @Override
663         public Range shl(final Range a, final Range b) {
664             return trace(super.shl(a, b), "shl", a, b);
665         }
666 
667         @Override
668         public Range shr(final Range a, final Range b) {
669             return trace(super.shr(a, b), "shr", a, b);
670         }
671 
672         @Override
673         public Range sar(final Range a, final Range b) {
674             return trace(super.sar(a, b), "sar", a, b);
675         }
676 
677         @Override
678         public Range mod(final Range a, final Range b) {
679             return trace(super.mod(a, b), "mod", a, b);
680         }
681 
682         @Override
683         public Range div(final Range a, final Range b) {
684             return trace(super.div(a, b), "div", a, b);
685         }
686     }
687 
688     @Override
689     public String toString() {
690         return String.valueOf(getType());
691     }
692 
693     @SuppressWarnings("unused")
694     private static boolean isRepresentableAsInt(final double number) {
695         return (int)number == number && !isNegativeZero(number);
696     }
697 
698     private static boolean isRepresentableAsLong(final double number) {
699         return (long)number == number && !isNegativeZero(number);
700     }
701 
702     private static boolean isNegativeZero(final double number) {
703         return Double.doubleToLongBits(number) == Double.doubleToLongBits(-0.0);
704     }
705 }