Fri, 05 Jul 2013 14:36:54 +0200
8017084: Use spill properties for large object literals
Reviewed-by: lagergren, sundar
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 */
26 package jdk.nashorn.internal.ir;
28 import java.util.Arrays;
29 import java.util.Collections;
30 import java.util.List;
31 import jdk.nashorn.internal.codegen.CompileUnit;
32 import jdk.nashorn.internal.codegen.types.Type;
33 import jdk.nashorn.internal.ir.annotations.Immutable;
34 import jdk.nashorn.internal.ir.visitor.NodeVisitor;
35 import jdk.nashorn.internal.parser.Lexer.LexerToken;
36 import jdk.nashorn.internal.parser.Token;
37 import jdk.nashorn.internal.parser.TokenType;
38 import jdk.nashorn.internal.runtime.JSType;
39 import jdk.nashorn.internal.runtime.ScriptRuntime;
40 import jdk.nashorn.internal.runtime.Undefined;
42 /**
43 * Literal nodes represent JavaScript values.
44 *
45 * @param <T> the literal type
46 */
47 @Immutable
48 public abstract class LiteralNode<T> extends Node implements PropertyKey {
49 /** Literal value */
50 protected final T value;
52 /** Marker for values that must be computed at runtime */
53 public static final Object POSTSET_MARKER = new Object();
55 /**
56 * Constructor
57 *
58 * @param token token
59 * @param finish finish
60 * @param value the value of the literal
61 */
62 protected LiteralNode(final long token, final int finish, final T value) {
63 super(token, finish);
64 this.value = value;
65 }
67 /**
68 * Copy constructor
69 *
70 * @param literalNode source node
71 */
72 protected LiteralNode(final LiteralNode<T> literalNode) {
73 this(literalNode, literalNode.value);
74 }
76 /**
77 * A copy constructor with value change.
78 * @param literalNode the original literal node
79 * @param newValue new value for this node
80 */
81 protected LiteralNode(final LiteralNode<T> literalNode, final T newValue) {
82 super(literalNode);
83 this.value = newValue;
84 }
86 @Override
87 public boolean isAtom() {
88 return true;
89 }
91 /**
92 * Check if the literal value is null
93 * @return true if literal value is null
94 */
95 public boolean isNull() {
96 return value == null;
97 }
99 /**
100 * Check if the literal value is boolean true
101 * @return true if literal value is boolean true
102 */
103 public boolean isTrue() {
104 return JSType.toBoolean(value);
105 }
107 @Override
108 public Type getType() {
109 return Type.typeFor(value.getClass());
110 }
112 @Override
113 public String getPropertyName() {
114 return JSType.toString(getObject());
115 }
117 /**
118 * Fetch boolean value of node.
119 *
120 * @return boolean value of node.
121 */
122 public boolean getBoolean() {
123 return JSType.toBoolean(value);
124 }
126 /**
127 * Fetch int32 value of node.
128 *
129 * @return Int32 value of node.
130 */
131 public int getInt32() {
132 return JSType.toInt32(value);
133 }
135 /**
136 * Fetch uint32 value of node.
137 *
138 * @return uint32 value of node.
139 */
140 public long getUint32() {
141 return JSType.toUint32(value);
142 }
144 /**
145 * Fetch long value of node
146 *
147 * @return long value of node
148 */
149 public long getLong() {
150 return JSType.toLong(value);
151 }
153 /**
154 * Fetch double value of node.
155 *
156 * @return double value of node.
157 */
158 public double getNumber() {
159 return JSType.toNumber(value);
160 }
162 /**
163 * Get the array value of the node
164 *
165 * @return the array value
166 */
167 public Node[] getArray() {
168 assert false : "not an array node";
169 return null;
170 }
172 /**
173 * Fetch String value of node.
174 *
175 * @return String value of node.
176 */
177 public String getString() {
178 return JSType.toString(value);
179 }
181 /**
182 * Fetch Object value of node.
183 *
184 * @return Object value of node.
185 */
186 public Object getObject() {
187 return value;
188 }
190 /**
191 * Test if the value is a string.
192 *
193 * @return True if value is a string.
194 */
195 public boolean isString() {
196 return value instanceof String;
197 }
199 /**
200 * Test if tha value is a number
201 *
202 * @return True if value is a number
203 */
204 public boolean isNumeric() {
205 return value instanceof Number;
206 }
208 /**
209 * Assist in IR navigation.
210 *
211 * @param visitor IR navigating visitor.
212 */
213 @Override
214 public Node accept(final NodeVisitor<? extends LexicalContext> visitor) {
215 if (visitor.enterLiteralNode(this)) {
216 return visitor.leaveLiteralNode(this);
217 }
219 return this;
220 }
222 @Override
223 public void toString(final StringBuilder sb) {
224 if (value == null) {
225 sb.append("null");
226 } else {
227 sb.append(value.toString());
228 }
229 }
231 /**
232 * Get the literal node value
233 * @return the value
234 */
235 public T getValue() {
236 return value;
237 }
239 /**
240 * Create a new null literal
241 *
242 * @param token token
243 * @param finish finish
244 *
245 * @return the new literal node
246 */
247 public static LiteralNode<Object> newInstance(final long token, final int finish) {
248 return new NullLiteralNode(token, finish);
249 }
251 /**
252 * Create a new null literal based on a parent node (source, token, finish)
253 *
254 * @param parent parent node
255 *
256 * @return the new literal node
257 */
258 public static LiteralNode<Object> newInstance(final Node parent) {
259 return new NullLiteralNode(parent.getToken(), parent.getFinish());
260 }
262 @Immutable
263 private static final class BooleanLiteralNode extends LiteralNode<Boolean> {
265 private BooleanLiteralNode(final long token, final int finish, final boolean value) {
266 super(Token.recast(token, value ? TokenType.TRUE : TokenType.FALSE), finish, value);
267 }
269 private BooleanLiteralNode(final BooleanLiteralNode literalNode) {
270 super(literalNode);
271 }
273 @Override
274 public boolean isTrue() {
275 return value;
276 }
278 @Override
279 public Type getType() {
280 return Type.BOOLEAN;
281 }
283 @Override
284 public Type getWidestOperationType() {
285 return Type.BOOLEAN;
286 }
287 }
289 /**
290 * Create a new boolean literal
291 *
292 * @param token token
293 * @param finish finish
294 * @param value true or false
295 *
296 * @return the new literal node
297 */
298 public static LiteralNode<Boolean> newInstance(final long token, final int finish, final boolean value) {
299 return new BooleanLiteralNode(token, finish, value);
300 }
302 /**
303 * Create a new boolean literal based on a parent node (source, token, finish)
304 *
305 * @param parent parent node
306 * @param value true or false
307 *
308 * @return the new literal node
309 */
310 public static LiteralNode<?> newInstance(final Node parent, final boolean value) {
311 return new BooleanLiteralNode(parent.getToken(), parent.getFinish(), value);
312 }
314 @Immutable
315 private static final class NumberLiteralNode extends LiteralNode<Number> {
317 private final Type type = numberGetType(value);
319 private NumberLiteralNode(final long token, final int finish, final Number value) {
320 super(Token.recast(token, TokenType.DECIMAL), finish, value);
321 }
323 private NumberLiteralNode(final NumberLiteralNode literalNode) {
324 super(literalNode);
325 }
327 private static Type numberGetType(final Number number) {
328 if (number instanceof Integer) {
329 return Type.INT;
330 } else if (number instanceof Long) {
331 return Type.LONG;
332 } else if (number instanceof Double) {
333 return Type.NUMBER;
334 } else {
335 assert false;
336 }
338 return null;
339 }
341 @Override
342 public Type getType() {
343 return type;
344 }
346 @Override
347 public Type getWidestOperationType() {
348 return getType();
349 }
351 }
352 /**
353 * Create a new number literal
354 *
355 * @param token token
356 * @param finish finish
357 * @param value literal value
358 *
359 * @return the new literal node
360 */
361 public static LiteralNode<Number> newInstance(final long token, final int finish, final Number value) {
362 return new NumberLiteralNode(token, finish, value);
363 }
365 /**
366 * Create a new number literal based on a parent node (source, token, finish)
367 *
368 * @param parent parent node
369 * @param value literal value
370 *
371 * @return the new literal node
372 */
373 public static LiteralNode<?> newInstance(final Node parent, final Number value) {
374 return new NumberLiteralNode(parent.getToken(), parent.getFinish(), value);
375 }
377 private static class UndefinedLiteralNode extends LiteralNode<Undefined> {
378 private UndefinedLiteralNode(final long token, final int finish) {
379 super(Token.recast(token, TokenType.OBJECT), finish, ScriptRuntime.UNDEFINED);
380 }
382 private UndefinedLiteralNode(final UndefinedLiteralNode literalNode) {
383 super(literalNode);
384 }
385 }
387 /**
388 * Create a new undefined literal
389 *
390 * @param token token
391 * @param finish finish
392 * @param value undefined value, passed only for polymorphisism discrimination
393 *
394 * @return the new literal node
395 */
396 public static LiteralNode<Undefined> newInstance(final long token, final int finish, final Undefined value) {
397 return new UndefinedLiteralNode(token, finish);
398 }
400 /**
401 * Create a new null literal based on a parent node (source, token, finish)
402 *
403 * @param parent parent node
404 * @param value undefined value
405 *
406 * @return the new literal node
407 */
408 public static LiteralNode<?> newInstance(final Node parent, final Undefined value) {
409 return new UndefinedLiteralNode(parent.getToken(), parent.getFinish());
410 }
412 @Immutable
413 private static class StringLiteralNode extends LiteralNode<String> {
414 private StringLiteralNode(final long token, final int finish, final String value) {
415 super(Token.recast(token, TokenType.STRING), finish, value);
416 }
418 private StringLiteralNode(final StringLiteralNode literalNode) {
419 super(literalNode);
420 }
422 @Override
423 public void toString(final StringBuilder sb) {
424 sb.append('\"');
425 sb.append(value);
426 sb.append('\"');
427 }
428 }
430 /**
431 * Create a new string literal
432 *
433 * @param token token
434 * @param finish finish
435 * @param value string value
436 *
437 * @return the new literal node
438 */
439 public static LiteralNode<String> newInstance(final long token, final int finish, final String value) {
440 return new StringLiteralNode(token, finish, value);
441 }
443 /**
444 * Create a new String literal based on a parent node (source, token, finish)
445 *
446 * @param parent parent node
447 * @param value string value
448 *
449 * @return the new literal node
450 */
451 public static LiteralNode<?> newInstance(final Node parent, final String value) {
452 return new StringLiteralNode(parent.getToken(), parent.getFinish(), value);
453 }
455 @Immutable
456 private static class LexerTokenLiteralNode extends LiteralNode<LexerToken> {
457 private LexerTokenLiteralNode(final long token, final int finish, final LexerToken value) {
458 super(Token.recast(token, TokenType.STRING), finish, value); //TODO is string the correct token type here?
459 }
461 private LexerTokenLiteralNode(final LexerTokenLiteralNode literalNode) {
462 super(literalNode);
463 }
465 @Override
466 public Type getType() {
467 return Type.OBJECT;
468 }
470 @Override
471 public void toString(final StringBuilder sb) {
472 sb.append(value.toString());
473 }
474 }
476 /**
477 * Create a new literal node for a lexer token
478 *
479 * @param token token
480 * @param finish finish
481 * @param value lexer token value
482 *
483 * @return the new literal node
484 */
485 public static LiteralNode<LexerToken> newInstance(final long token, final int finish, final LexerToken value) {
486 return new LexerTokenLiteralNode(token, finish, value);
487 }
489 /**
490 * Create a new lexer token literal based on a parent node (source, token, finish)
491 *
492 * @param parent parent node
493 * @param value lexer token
494 *
495 * @return the new literal node
496 */
497 public static LiteralNode<?> newInstance(final Node parent, final LexerToken value) {
498 return new LexerTokenLiteralNode(parent.getToken(), parent.getFinish(), value);
499 }
501 /**
502 * Get the constant value for an object, or {@link #POSTSET_MARKER} if the value can't be statically computed.
503 *
504 * @param object a node or value object
505 * @return the constant value or {@code POSTSET_MARKER}
506 */
507 public static Object objectAsConstant(final Object object) {
508 if (object == null) {
509 return null;
510 } else if (object instanceof Number || object instanceof String || object instanceof Boolean) {
511 return object;
512 } else if (object instanceof LiteralNode) {
513 return objectAsConstant(((LiteralNode<?>)object).getValue());
514 } else if (object instanceof UnaryNode) {
515 final UnaryNode unaryNode = (UnaryNode)object;
517 if (unaryNode.isTokenType(TokenType.CONVERT) && unaryNode.getType().isObject()) {
518 return objectAsConstant(unaryNode.rhs());
519 }
520 }
522 return POSTSET_MARKER;
523 }
525 private static final class NullLiteralNode extends LiteralNode<Object> {
527 private NullLiteralNode(final long token, final int finish) {
528 super(Token.recast(token, TokenType.OBJECT), finish, null);
529 }
531 @Override
532 public Node accept(final NodeVisitor<? extends LexicalContext> visitor) {
533 if (visitor.enterLiteralNode(this)) {
534 return visitor.leaveLiteralNode(this);
535 }
537 return this;
538 }
540 @Override
541 public Type getType() {
542 return Type.OBJECT;
543 }
545 @Override
546 public Type getWidestOperationType() {
547 return Type.OBJECT;
548 }
549 }
551 /**
552 * Array literal node class.
553 */
554 public static final class ArrayLiteralNode extends LiteralNode<Node[]> {
556 /** Array element type. */
557 private Type elementType;
559 /** Preset constant array. */
560 private Object presets;
562 /** Indices of array elements requiring computed post sets. */
563 private int[] postsets;
565 private List<ArrayUnit> units;
567 /**
568 * An ArrayUnit is a range in an ArrayLiteral. ArrayLiterals can
569 * be split if they are too large, for bytecode generation reasons
570 */
571 public static class ArrayUnit {
572 /** Compile unit associated with the postsets range. */
573 private final CompileUnit compileUnit;
575 /** postsets range associated with the unit (hi not inclusive). */
576 private final int lo, hi;
578 /**
579 * Constructor
580 * @param compileUnit compile unit
581 * @param lo lowest array index in unit
582 * @param hi highest array index in unit + 1
583 */
584 public ArrayUnit(final CompileUnit compileUnit, final int lo, final int hi) {
585 this.compileUnit = compileUnit;
586 this.lo = lo;
587 this.hi = hi;
588 }
590 /**
591 * Get the high index position of the ArrayUnit (non inclusive)
592 * @return high index position
593 */
594 public int getHi() {
595 return hi;
596 }
598 /**
599 * Get the low index position of the ArrayUnit (inclusive)
600 * @return low index position
601 */
602 public int getLo() {
603 return lo;
604 }
606 /**
607 * The array compile unit
608 * @return array compile unit
609 */
610 public CompileUnit getCompileUnit() {
611 return compileUnit;
612 }
613 }
615 /**
616 * Constructor
617 *
618 * @param token token
619 * @param finish finish
620 * @param value array literal value, a Node array
621 */
622 protected ArrayLiteralNode(final long token, final int finish, final Node[] value) {
623 super(Token.recast(token, TokenType.ARRAY), finish, value);
624 this.elementType = Type.UNKNOWN;
625 }
627 /**
628 * Copy constructor
629 * @param node source array literal node
630 */
631 private ArrayLiteralNode(final ArrayLiteralNode node, final Node[] value) {
632 super(node, value);
633 this.elementType = node.elementType;
634 this.presets = node.presets;
635 this.postsets = node.postsets;
636 this.units = node.units;
637 }
639 /**
640 * Compute things like widest element type needed. Internal use from compiler only
641 */
642 public void analyze() {
643 elementType = Type.INT;
644 analyzeElements();
646 if (elementType.isInteger()) {
647 presetIntArray();
648 } else if (elementType.isLong()) {
649 presetLongArray();
650 } else if (elementType.isNumeric()) {
651 presetNumberArray();
652 } else {
653 presetObjectArray();
654 }
655 }
657 private void presetIntArray() {
658 final int[] array = new int[value.length];
659 final int[] computed = new int[value.length];
660 int nComputed = 0;
662 for (int i = 0; i < value.length; i++) {
663 final Object element = objectAsConstant(value[i]);
665 if (element instanceof Number) {
666 array[i] = ((Number)element).intValue();
667 } else {
668 computed[nComputed++] = i;
669 }
670 }
672 presets = array;
673 postsets = Arrays.copyOf(computed, nComputed);
674 }
676 private void presetLongArray() {
677 final long[] array = new long[value.length];
678 final int[] computed = new int[value.length];
679 int nComputed = 0;
681 for (int i = 0; i < value.length; i++) {
682 final Object element = objectAsConstant(value[i]);
684 if (element instanceof Number) {
685 array[i] = ((Number)element).longValue();
686 } else {
687 computed[nComputed++] = i;
688 }
689 }
691 presets = array;
692 postsets = Arrays.copyOf(computed, nComputed);
693 }
695 private void presetNumberArray() {
696 final double[] array = new double[value.length];
697 final int[] computed = new int[value.length];
698 int nComputed = 0;
700 for (int i = 0; i < value.length; i++) {
701 final Object element = objectAsConstant(value[i]);
703 if (element instanceof Number) {
704 array[i] = ((Number)element).doubleValue();
705 } else {
706 computed[nComputed++] = i;
707 }
708 }
710 presets = array;
711 postsets = Arrays.copyOf(computed, nComputed);
712 }
714 private void presetObjectArray() {
715 final Object[] array = new Object[value.length];
716 final int[] computed = new int[value.length];
717 int nComputed = 0;
719 for (int i = 0; i < value.length; i++) {
720 final Node node = value[i];
722 if (node == null) {
723 computed[nComputed++] = i;
724 } else {
725 final Object element = objectAsConstant(node);
727 if (element != POSTSET_MARKER) {
728 array[i] = element;
729 } else {
730 computed[nComputed++] = i;
731 }
732 }
733 }
735 presets = array;
736 postsets = Arrays.copyOf(computed, nComputed);
737 }
739 private void analyzeElements() {
740 for (final Node node : value) {
741 if (node == null) {
742 elementType = elementType.widest(Type.OBJECT); //no way to represent undefined as number
743 break;
744 }
746 assert node.getSymbol() != null; //don't run this on unresolved nodes or you are in trouble
747 Type symbolType = node.getSymbol().getSymbolType();
748 if (symbolType.isUnknown()) {
749 symbolType = Type.OBJECT;
750 }
752 if (symbolType.isBoolean()) {
753 elementType = elementType.widest(Type.OBJECT);
754 break;
755 }
757 elementType = elementType.widest(symbolType);
759 if (elementType.isObject()) {
760 break;
761 }
762 }
763 }
765 @Override
766 public Node[] getArray() {
767 return value;
768 }
770 @Override
771 public Type getType() {
772 if (elementType.isInteger()) {
773 return Type.INT_ARRAY;
774 } else if (elementType.isLong()) {
775 return Type.LONG_ARRAY;
776 } else if (elementType.isNumeric()) {
777 return Type.NUMBER_ARRAY;
778 } else {
779 return Type.OBJECT_ARRAY;
780 }
781 }
783 /**
784 * Get the element type of this array literal
785 * @return element type
786 */
787 public Type getElementType() {
788 return elementType;
789 }
791 /**
792 * Get indices of arrays containing computed post sets. post sets
793 * are things like non literals e.g. "x+y" instead of i or 17
794 * @return post set indices
795 */
796 public int[] getPostsets() {
797 return postsets;
798 }
800 /**
801 * Get presets constant array
802 * @return presets array, always returns an array type
803 */
804 public Object getPresets() {
805 return presets;
806 }
808 /**
809 * Get the array units that make up this ArrayLiteral
810 * @see ArrayUnit
811 * @return list of array units
812 */
813 public List<ArrayUnit> getUnits() {
814 return units == null ? null : Collections.unmodifiableList(units);
815 }
817 /**
818 * Set the ArrayUnits that make up this ArrayLiteral
819 * @see ArrayUnit
820 * @param units list of array units
821 */
822 public void setUnits(final List<ArrayUnit> units) {
823 this.units = units;
824 }
826 @Override
827 public Node accept(final NodeVisitor<? extends LexicalContext> visitor) {
828 if (visitor.enterLiteralNode(this)) {
829 final List<Node> oldValue = Arrays.asList(value);
830 final List<Node> newValue = Node.accept(visitor, Node.class, oldValue);
831 return visitor.leaveLiteralNode(oldValue != newValue ? setValue(newValue) : this);
832 }
833 return this;
834 }
836 private ArrayLiteralNode setValue(final List<Node> value) {
837 return new ArrayLiteralNode(this, value.toArray(new Node[value.size()]));
838 }
840 @Override
841 public void toString(final StringBuilder sb) {
842 sb.append('[');
843 boolean first = true;
844 for (final Node node : value) {
845 if (!first) {
846 sb.append(',');
847 sb.append(' ');
848 }
849 if (node == null) {
850 sb.append("undefined");
851 } else {
852 node.toString(sb);
853 }
854 first = false;
855 }
856 sb.append(']');
857 }
858 }
860 /**
861 * Create a new array literal of Nodes from a list of Node values
862 *
863 * @param token token
864 * @param finish finish
865 * @param value literal value list
866 *
867 * @return the new literal node
868 */
869 public static LiteralNode<Node[]> newInstance(final long token, final int finish, final List<Node> value) {
870 return new ArrayLiteralNode(token, finish, value.toArray(new Node[value.size()]));
871 }
874 /**
875 * Create a new array literal based on a parent node (source, token, finish)
876 *
877 * @param parent parent node
878 * @param value literal value list
879 *
880 * @return the new literal node
881 */
882 public static LiteralNode<?> newInstance(final Node parent, final List<Node> value) {
883 return new ArrayLiteralNode(parent.getToken(), parent.getFinish(), value.toArray(new Node[value.size()]));
884 }
886 /**
887 * Create a new array literal of Nodes
888 *
889 * @param token token
890 * @param finish finish
891 * @param value literal value array
892 *
893 * @return the new literal node
894 */
895 public static LiteralNode<Node[]> newInstance(final long token, final int finish, final Node[] value) {
896 return new ArrayLiteralNode(token, finish, value);
897 }
898 }