Thu, 25 Sep 2014 15:53:47 +0200
8025435: Optimistic builtins support, implemented initial optimistic versions of push, pop, and charCodeAt
Reviewed-by: hannesw, attila, 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.io.PrintWriter;
29 import java.util.HashSet;
30 import java.util.Set;
31 import java.util.StringTokenizer;
32 import jdk.nashorn.internal.codegen.types.Type;
33 import jdk.nashorn.internal.runtime.Context;
34 import jdk.nashorn.internal.runtime.Debug;
35 import jdk.nashorn.internal.runtime.options.Options;
37 /**
38 * Symbol is a symbolic address for a value ("variable" if you wish). Identifiers in JavaScript source, as well as
39 * certain synthetic variables created by the compiler are represented by Symbol objects. Symbols can address either
40 * local variable slots in bytecode ("slotted symbol"), or properties in scope objects ("scoped symbol"). A symbol can
41 * also end up being defined but then not used during symbol assignment calculations; such symbol will be neither
42 * scoped, nor slotted; it represents a dead variable (it might be written to, but is never read). Finally, a symbol can
43 * be both slotted and in scope. This special case can only occur with bytecode method parameters. They all come in as
44 * slotted, but if they are used by a nested function (or eval) then they will be copied into the scope object, and used
45 * from there onwards. Two further special cases are parameters stored in {@code NativeArguments} objects and parameters
46 * stored in {@code Object[]} parameter to variable-arity functions. Those use the {@code #getFieldIndex()} property to
47 * refer to their location.
48 */
50 public final class Symbol implements Comparable<Symbol> {
51 /** Is this Global */
52 public static final int IS_GLOBAL = 1;
53 /** Is this a variable */
54 public static final int IS_VAR = 2;
55 /** Is this a parameter */
56 public static final int IS_PARAM = 3;
57 /** Mask for kind flags */
58 public static final int KINDMASK = (1 << 2) - 1; // Kinds are represented by lower two bits
60 /** Is this symbol in scope */
61 public static final int IS_SCOPE = 1 << 2;
62 /** Is this a this symbol */
63 public static final int IS_THIS = 1 << 3;
64 /** Is this a let */
65 public static final int IS_LET = 1 << 4;
66 /** Is this a const */
67 public static final int IS_CONST = 1 << 5;
68 /** Is this an internal symbol, never represented explicitly in source code */
69 public static final int IS_INTERNAL = 1 << 6;
70 /** Is this a function self-reference symbol */
71 public static final int IS_FUNCTION_SELF = 1 << 7;
72 /** Is this a function declaration? */
73 public static final int IS_FUNCTION_DECLARATION = 1 << 8;
74 /** Is this a program level symbol? */
75 public static final int IS_PROGRAM_LEVEL = 1 << 9;
76 /** Are this symbols' values stored in local variable slots? */
77 public static final int HAS_SLOT = 1 << 10;
78 /** Is this symbol known to store an int value ? */
79 public static final int HAS_INT_VALUE = 1 << 11;
80 /** Is this symbol known to store a long value ? */
81 public static final int HAS_LONG_VALUE = 1 << 12;
82 /** Is this symbol known to store a double value ? */
83 public static final int HAS_DOUBLE_VALUE = 1 << 13;
84 /** Is this symbol known to store an object value ? */
85 public static final int HAS_OBJECT_VALUE = 1 << 14;
86 /** Is this symbol seen a declaration? Used for block scoped LET and CONST symbols only. */
87 public static final int HAS_BEEN_DECLARED = 1 << 15;
89 /** Null or name identifying symbol. */
90 private final String name;
92 /** Symbol flags. */
93 private int flags;
95 /** First bytecode method local variable slot for storing the value(s) of this variable. -1 indicates the variable
96 * is not stored in local variable slots or it is not yet known. */
97 private int firstSlot = -1;
99 /** Field number in scope or property; array index in varargs when not using arguments object. */
100 private int fieldIndex;
102 /** Number of times this symbol is used in code */
103 private int useCount;
105 /** Debugging option - dump info and stack trace when symbols with given names are manipulated */
106 private static final Set<String> TRACE_SYMBOLS;
107 private static final Set<String> TRACE_SYMBOLS_STACKTRACE;
109 static {
110 final String stacktrace = Options.getStringProperty("nashorn.compiler.symbol.stacktrace", null);
111 final String trace;
112 if (stacktrace != null) {
113 trace = stacktrace; //stacktrace always implies trace as well
114 TRACE_SYMBOLS_STACKTRACE = new HashSet<>();
115 for (final StringTokenizer st = new StringTokenizer(stacktrace, ","); st.hasMoreTokens(); ) {
116 TRACE_SYMBOLS_STACKTRACE.add(st.nextToken());
117 }
118 } else {
119 trace = Options.getStringProperty("nashorn.compiler.symbol.trace", null);
120 TRACE_SYMBOLS_STACKTRACE = null;
121 }
123 if (trace != null) {
124 TRACE_SYMBOLS = new HashSet<>();
125 for (final StringTokenizer st = new StringTokenizer(trace, ","); st.hasMoreTokens(); ) {
126 TRACE_SYMBOLS.add(st.nextToken());
127 }
128 } else {
129 TRACE_SYMBOLS = null;
130 }
131 }
133 /**
134 * Constructor
135 *
136 * @param name name of symbol
137 * @param flags symbol flags
138 * @param slot bytecode slot for this symbol
139 */
140 protected Symbol(final String name, final int flags, final int slot) {
141 this.name = name;
142 this.flags = flags;
143 this.firstSlot = slot;
144 this.fieldIndex = -1;
145 if(shouldTrace()) {
146 trace("CREATE SYMBOL " + name);
147 }
148 }
150 /**
151 * Constructor
152 *
153 * @param name name of symbol
154 * @param flags symbol flags
155 */
156 public Symbol(final String name, final int flags) {
157 this(name, flags, -1);
158 }
160 private static String align(final String string, final int max) {
161 final StringBuilder sb = new StringBuilder();
162 sb.append(string.substring(0, Math.min(string.length(), max)));
164 while (sb.length() < max) {
165 sb.append(' ');
166 }
167 return sb.toString();
168 }
170 /**
171 * Debugging .
172 *
173 * @param stream Stream to print to.
174 */
176 void print(final PrintWriter stream) {
177 final StringBuilder sb = new StringBuilder();
179 sb.append(align(name, 20)).
180 append(": ").
181 append(", ").
182 append(align(firstSlot == -1 ? "none" : "" + firstSlot, 10));
184 switch (flags & KINDMASK) {
185 case IS_GLOBAL:
186 sb.append(" global");
187 break;
188 case IS_VAR:
189 if (isConst()) {
190 sb.append(" const");
191 } else if (isLet()) {
192 sb.append(" let");
193 } else {
194 sb.append(" var");
195 }
196 break;
197 case IS_PARAM:
198 sb.append(" param");
199 break;
200 default:
201 break;
202 }
204 if (isScope()) {
205 sb.append(" scope");
206 }
208 if (isInternal()) {
209 sb.append(" internal");
210 }
212 if (isThis()) {
213 sb.append(" this");
214 }
216 if (isProgramLevel()) {
217 sb.append(" program");
218 }
220 sb.append('\n');
222 stream.print(sb.toString());
223 }
225 /**
226 * Compare the the symbol kind with another.
227 *
228 * @param other Other symbol's flags.
229 * @return True if symbol has less kind.
230 */
231 public boolean less(final int other) {
232 return (flags & KINDMASK) < (other & KINDMASK);
233 }
235 /**
236 * Allocate a slot for this symbol.
237 *
238 * @param needsSlot True if symbol needs a slot.
239 * @return the symbol
240 */
241 public Symbol setNeedsSlot(final boolean needsSlot) {
242 if(needsSlot) {
243 assert !isScope();
244 flags |= HAS_SLOT;
245 } else {
246 flags &= ~HAS_SLOT;
247 }
248 return this;
249 }
251 /**
252 * Return the number of slots required for the symbol.
253 *
254 * @return Number of slots.
255 */
256 public int slotCount() {
257 return ((flags & HAS_INT_VALUE) == 0 ? 0 : 1) +
258 ((flags & HAS_LONG_VALUE) == 0 ? 0 : 2) +
259 ((flags & HAS_DOUBLE_VALUE) == 0 ? 0 : 2) +
260 ((flags & HAS_OBJECT_VALUE) == 0 ? 0 : 1);
261 }
263 private boolean isSlotted() {
264 return firstSlot != -1 && ((flags & HAS_SLOT) != 0);
265 }
267 @Override
268 public String toString() {
269 final StringBuilder sb = new StringBuilder();
271 sb.append(name).
272 append(' ');
274 if (hasSlot()) {
275 sb.append(' ').
276 append('(').
277 append("slot=").
278 append(firstSlot).append(' ');
279 if((flags & HAS_INT_VALUE) != 0) { sb.append('I'); }
280 if((flags & HAS_LONG_VALUE) != 0) { sb.append('J'); }
281 if((flags & HAS_DOUBLE_VALUE) != 0) { sb.append('D'); }
282 if((flags & HAS_OBJECT_VALUE) != 0) { sb.append('O'); }
283 sb.append(')');
284 }
286 if (isScope()) {
287 if(isGlobal()) {
288 sb.append(" G");
289 } else {
290 sb.append(" S");
291 }
292 }
294 return sb.toString();
295 }
297 @Override
298 public int compareTo(final Symbol other) {
299 return name.compareTo(other.name);
300 }
302 /**
303 * Does this symbol have an allocated bytecode slot? Note that having an allocated bytecode slot doesn't necessarily
304 * mean the symbol's value will be stored in it. Namely, a function parameter can have a bytecode slot, but if it is
305 * in scope, then the bytecode slot will not be used. See {@link #isBytecodeLocal()}.
306 *
307 * @return true if this symbol has a local bytecode slot
308 */
309 public boolean hasSlot() {
310 return (flags & HAS_SLOT) != 0;
311 }
313 /**
314 * Is this symbol a local variable stored in bytecode local variable slots? This is true for a slotted variable that
315 * is not in scope. (E.g. a parameter that is in scope is slotted, but it will not be a local variable).
316 * @return true if this symbol is using bytecode local slots for its storage.
317 */
318 public boolean isBytecodeLocal() {
319 return hasSlot() && !isScope();
320 }
322 /**
323 * Returns true if this symbol is dead (it is a local variable that is statically proven to never be read in any type).
324 * @return true if this symbol is dead
325 */
326 public boolean isDead() {
327 return (flags & (HAS_SLOT | IS_SCOPE)) == 0;
328 }
330 /**
331 * Check if this is a symbol in scope. Scope symbols cannot, for obvious reasons
332 * be stored in byte code slots on the local frame
333 *
334 * @return true if this is scoped
335 */
336 public boolean isScope() {
337 assert (flags & KINDMASK) != IS_GLOBAL || (flags & IS_SCOPE) == IS_SCOPE : "global without scope flag";
338 return (flags & IS_SCOPE) != 0;
339 }
341 /**
342 * Check if this symbol is a function declaration
343 * @return true if a function declaration
344 */
345 public boolean isFunctionDeclaration() {
346 return (flags & IS_FUNCTION_DECLARATION) != 0;
347 }
349 /**
350 * Flag this symbol as scope as described in {@link Symbol#isScope()}
351 * @return the symbol
352 */
353 public Symbol setIsScope() {
354 if (!isScope()) {
355 if(shouldTrace()) {
356 trace("SET IS SCOPE");
357 }
358 flags |= IS_SCOPE;
359 if(!isParam()) {
360 flags &= ~HAS_SLOT;
361 }
362 }
363 return this;
364 }
366 /**
367 * Mark this symbol as a function declaration.
368 */
369 public void setIsFunctionDeclaration() {
370 if (!isFunctionDeclaration()) {
371 if(shouldTrace()) {
372 trace("SET IS FUNCTION DECLARATION");
373 }
374 flags |= IS_FUNCTION_DECLARATION;
375 }
376 }
378 /**
379 * Check if this symbol is a variable
380 * @return true if variable
381 */
382 public boolean isVar() {
383 return (flags & KINDMASK) == IS_VAR;
384 }
386 /**
387 * Check if this symbol is a global (undeclared) variable
388 * @return true if global
389 */
390 public boolean isGlobal() {
391 return (flags & KINDMASK) == IS_GLOBAL;
392 }
394 /**
395 * Check if this symbol is a function parameter
396 * @return true if parameter
397 */
398 public boolean isParam() {
399 return (flags & KINDMASK) == IS_PARAM;
400 }
402 /**
403 * Check if this is a program (script) level definition
404 * @return true if program level
405 */
406 public boolean isProgramLevel() {
407 return (flags & IS_PROGRAM_LEVEL) != 0;
408 }
410 /**
411 * Check if this symbol is a constant
412 * @return true if a constant
413 */
414 public boolean isConst() {
415 return (flags & IS_CONST) != 0;
416 }
418 /**
419 * Check if this is an internal symbol, without an explicit JavaScript source
420 * code equivalent
421 * @return true if internal
422 */
423 public boolean isInternal() {
424 return (flags & IS_INTERNAL) != 0;
425 }
427 /**
428 * Check if this symbol represents {@code this}
429 * @return true if this
430 */
431 public boolean isThis() {
432 return (flags & IS_THIS) != 0;
433 }
435 /**
436 * Check if this symbol is a let
437 * @return true if let
438 */
439 public boolean isLet() {
440 return (flags & IS_LET) != 0;
441 }
443 /**
444 * Flag this symbol as a function's self-referencing symbol.
445 * @return true if this symbol as a function's self-referencing symbol.
446 */
447 public boolean isFunctionSelf() {
448 return (flags & IS_FUNCTION_SELF) != 0;
449 }
451 /**
452 * Is this a block scoped symbol
453 * @return true if block scoped
454 */
455 public boolean isBlockScoped() {
456 return isLet() || isConst();
457 }
459 /**
460 * Has this symbol been declared
461 * @return true if declared
462 */
463 public boolean hasBeenDeclared() {
464 return (flags & HAS_BEEN_DECLARED) != 0;
465 }
467 /**
468 * Mark this symbol as declared
469 */
470 public void setHasBeenDeclared() {
471 if (!hasBeenDeclared()) {
472 flags |= HAS_BEEN_DECLARED;
473 }
474 }
476 /**
477 * Get the index of the field used to store this symbol, should it be an AccessorProperty
478 * and get allocated in a JO-prefixed ScriptObject subclass.
479 *
480 * @return field index
481 */
482 public int getFieldIndex() {
483 assert fieldIndex != -1 : "fieldIndex must be initialized " + fieldIndex;
484 return fieldIndex;
485 }
487 /**
488 * Set the index of the field used to store this symbol, should it be an AccessorProperty
489 * and get allocated in a JO-prefixed ScriptObject subclass.
490 *
491 * @param fieldIndex field index - a positive integer
492 * @return the symbol
493 */
494 public Symbol setFieldIndex(final int fieldIndex) {
495 if (this.fieldIndex != fieldIndex) {
496 this.fieldIndex = fieldIndex;
497 }
498 return this;
499 }
501 /**
502 * Get the symbol flags
503 * @return flags
504 */
505 public int getFlags() {
506 return flags;
507 }
509 /**
510 * Set the symbol flags
511 * @param flags flags
512 * @return the symbol
513 */
514 public Symbol setFlags(final int flags) {
515 if (this.flags != flags) {
516 this.flags = flags;
517 }
518 return this;
519 }
521 /**
522 * Set a single symbol flag
523 * @param flag flag to set
524 * @return the symbol
525 */
526 public Symbol setFlag(final int flag) {
527 if ((this.flags & flag) == 0) {
528 this.flags |= flag;
529 }
530 return this;
531 }
533 /**
534 * Clears a single symbol flag
535 * @param flag flag to set
536 * @return the symbol
537 */
538 public Symbol clearFlag(final int flag) {
539 if ((this.flags & flag) != 0) {
540 this.flags &= ~flag;
541 }
542 return this;
543 }
545 /**
546 * Get the name of this symbol
547 * @return symbol name
548 */
549 public String getName() {
550 return name;
551 }
553 /**
554 * Get the index of the first bytecode slot for this symbol
555 * @return byte code slot
556 */
557 public int getFirstSlot() {
558 assert isSlotted();
559 return firstSlot;
560 }
562 /**
563 * Get the index of the bytecode slot for this symbol for storing a value of the specified type.
564 * @param type the requested type
565 * @return byte code slot
566 */
567 public int getSlot(final Type type) {
568 assert isSlotted();
569 int typeSlot = firstSlot;
570 if(type.isBoolean() || type.isInteger()) {
571 assert (flags & HAS_INT_VALUE) != 0;
572 return typeSlot;
573 }
574 typeSlot += ((flags & HAS_INT_VALUE) == 0 ? 0 : 1);
575 if(type.isLong()) {
576 assert (flags & HAS_LONG_VALUE) != 0;
577 return typeSlot;
578 }
579 typeSlot += ((flags & HAS_LONG_VALUE) == 0 ? 0 : 2);
580 if(type.isNumber()) {
581 assert (flags & HAS_DOUBLE_VALUE) != 0;
582 return typeSlot;
583 }
584 assert type.isObject();
585 assert (flags & HAS_OBJECT_VALUE) != 0 : name;
586 return typeSlot + ((flags & HAS_DOUBLE_VALUE) == 0 ? 0 : 2);
587 }
589 /**
590 * Returns true if this symbol has a local variable slot for storing a value of specific type.
591 * @param type the type
592 * @return true if this symbol has a local variable slot for storing a value of specific type.
593 */
594 public boolean hasSlotFor(final Type type) {
595 if(type.isBoolean() || type.isInteger()) {
596 return (flags & HAS_INT_VALUE) != 0;
597 } else if(type.isLong()) {
598 return (flags & HAS_LONG_VALUE) != 0;
599 } else if(type.isNumber()) {
600 return (flags & HAS_DOUBLE_VALUE) != 0;
601 }
602 assert type.isObject();
603 return (flags & HAS_OBJECT_VALUE) != 0;
604 }
606 /**
607 * Marks this symbol as having a local variable slot for storing a value of specific type.
608 * @param type the type
609 */
610 public void setHasSlotFor(final Type type) {
611 if(type.isBoolean() || type.isInteger()) {
612 setFlag(HAS_INT_VALUE);
613 } else if(type.isLong()) {
614 setFlag(HAS_LONG_VALUE);
615 } else if(type.isNumber()) {
616 setFlag(HAS_DOUBLE_VALUE);
617 } else {
618 assert type.isObject();
619 setFlag(HAS_OBJECT_VALUE);
620 }
621 }
623 /**
624 * Increase the symbol's use count by one.
625 * @return the symbol
626 */
627 public Symbol increaseUseCount() {
628 useCount++;
629 return this;
630 }
632 /**
633 * Get the symbol's use count
634 * @return the number of times the symbol is used in code.
635 */
636 public int getUseCount() {
637 return useCount;
638 }
640 /**
641 * Set the bytecode slot for this symbol
642 * @param firstSlot valid bytecode slot
643 * @return the symbol
644 */
645 public Symbol setFirstSlot(final int firstSlot) {
646 assert firstSlot >= 0 && firstSlot <= 65535;
647 if (firstSlot != this.firstSlot) {
648 if(shouldTrace()) {
649 trace("SET SLOT " + firstSlot);
650 }
651 this.firstSlot = firstSlot;
652 }
653 return this;
654 }
656 /**
657 * From a lexical context, set this symbol as needing scope, which
658 * will set flags for the defining block that will be written when
659 * block is popped from the lexical context stack, used by codegen
660 * when flags need to be tagged, but block is in the
661 * middle of evaluation and cannot be modified.
662 *
663 * @param lc lexical context
664 * @param symbol symbol
665 * @return the symbol
666 */
667 public static Symbol setSymbolIsScope(final LexicalContext lc, final Symbol symbol) {
668 symbol.setIsScope();
669 if (!symbol.isGlobal()) {
670 lc.setBlockNeedsScope(lc.getDefiningBlock(symbol));
671 }
672 return symbol;
673 }
675 private boolean shouldTrace() {
676 return TRACE_SYMBOLS != null && (TRACE_SYMBOLS.isEmpty() || TRACE_SYMBOLS.contains(name));
677 }
679 private void trace(final String desc) {
680 Context.err(Debug.id(this) + " SYMBOL: '" + name + "' " + desc);
681 if (TRACE_SYMBOLS_STACKTRACE != null && (TRACE_SYMBOLS_STACKTRACE.isEmpty() || TRACE_SYMBOLS_STACKTRACE.contains(name))) {
682 new Throwable().printStackTrace(Context.getCurrentErr());
683 }
684 }
685 }