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;
27
28 import static jdk.nashorn.internal.codegen.CompilerConstants.RETURN;
29 import static jdk.nashorn.internal.ir.Expression.isAlwaysFalse;
30 import static jdk.nashorn.internal.ir.Expression.isAlwaysTrue;
31
32 import java.util.ArrayDeque;
33 import java.util.ArrayList;
34 import java.util.Collections;
35 import java.util.Deque;
36 import java.util.HashSet;
37 import java.util.IdentityHashMap;
38 import java.util.Iterator;
39 import java.util.LinkedList;
40 import java.util.List;
41 import java.util.Map;
42 import java.util.Set;
43 import jdk.nashorn.internal.codegen.types.Type;
44 import jdk.nashorn.internal.ir.AccessNode;
45 import jdk.nashorn.internal.ir.BinaryNode;
46 import jdk.nashorn.internal.ir.Block;
47 import jdk.nashorn.internal.ir.BreakNode;
48 import jdk.nashorn.internal.ir.BreakableNode;
49 import jdk.nashorn.internal.ir.CallNode;
50 import jdk.nashorn.internal.ir.CaseNode;
51 import jdk.nashorn.internal.ir.CatchNode;
52 import jdk.nashorn.internal.ir.ContinueNode;
53 import jdk.nashorn.internal.ir.Expression;
54 import jdk.nashorn.internal.ir.ExpressionStatement;
55 import jdk.nashorn.internal.ir.ForNode;
56 import jdk.nashorn.internal.ir.FunctionNode;
57 import jdk.nashorn.internal.ir.GetSplitState;
58 import jdk.nashorn.internal.ir.IdentNode;
59 import jdk.nashorn.internal.ir.IfNode;
60 import jdk.nashorn.internal.ir.IndexNode;
61 import jdk.nashorn.internal.ir.JoinPredecessor;
62 import jdk.nashorn.internal.ir.JoinPredecessorExpression;
63 import jdk.nashorn.internal.ir.JumpStatement;
64 import jdk.nashorn.internal.ir.JumpToInlinedFinally;
65 import jdk.nashorn.internal.ir.LabelNode;
66 import jdk.nashorn.internal.ir.LexicalContext;
67 import jdk.nashorn.internal.ir.LexicalContextNode;
68 import jdk.nashorn.internal.ir.LiteralNode;
69 import jdk.nashorn.internal.ir.LiteralNode.ArrayLiteralNode;
70 import jdk.nashorn.internal.ir.LocalVariableConversion;
71 import jdk.nashorn.internal.ir.LoopNode;
72 import jdk.nashorn.internal.ir.Node;
73 import jdk.nashorn.internal.ir.ObjectNode;
74 import jdk.nashorn.internal.ir.PropertyNode;
75 import jdk.nashorn.internal.ir.ReturnNode;
76 import jdk.nashorn.internal.ir.RuntimeNode;
77 import jdk.nashorn.internal.ir.RuntimeNode.Request;
78 import jdk.nashorn.internal.ir.SplitReturn;
79 import jdk.nashorn.internal.ir.Statement;
80 import jdk.nashorn.internal.ir.SwitchNode;
81 import jdk.nashorn.internal.ir.Symbol;
82 import jdk.nashorn.internal.ir.TernaryNode;
83 import jdk.nashorn.internal.ir.ThrowNode;
84 import jdk.nashorn.internal.ir.TryNode;
85 import jdk.nashorn.internal.ir.UnaryNode;
86 import jdk.nashorn.internal.ir.VarNode;
87 import jdk.nashorn.internal.ir.WhileNode;
88 import jdk.nashorn.internal.ir.WithNode;
89 import jdk.nashorn.internal.ir.visitor.NodeVisitor;
90 import jdk.nashorn.internal.ir.visitor.SimpleNodeVisitor;
91 import jdk.nashorn.internal.parser.TokenType;
92
93 /**
94 * Calculates types for local variables. For purposes of local variable type calculation, the only types used are
95 * Undefined, boolean, int, long, double, and Object. The calculation eagerly widens types of local variable to their
96 * widest at control flow join points.
97 * TODO: investigate a more sophisticated solution that uses use/def information to only widens the type of a local
98 * variable to its widest used type after the join point. That would eliminate some widenings of undefined variables to
99 * object, most notably those used only in loops. We need a full liveness analysis for that. Currently, we can establish
100 * per-type liveness, which eliminates most of unwanted dead widenings.
101 * NOTE: the way this class is implemented, it actually processes the AST in two passes. The first pass is top-down and
102 * implemented in {@code enterXxx} methods. This pass does not mutate the AST (except for one occurrence, noted below),
103 * as being able to find relevant labels for control flow joins is sensitive to their reference identity, and mutated
104 * label-carrying nodes will create copies of their labels. A second bottom-up pass applying the changes is implemented
105 * in the separate visitor sitting in {@link #leaveFunctionNode(FunctionNode)}. This visitor will also instantiate new
106 * instances of the calculator to be run on nested functions (when not lazy compiling).
107 *
108 */
109 final class LocalVariableTypesCalculator extends SimpleNodeVisitor {
110
111 private static class JumpOrigin {
112 final JoinPredecessor node;
113 final Map<Symbol, LvarType> types;
114
115 JumpOrigin(final JoinPredecessor node, final Map<Symbol, LvarType> types) {
116 this.node = node;
117 this.types = types;
118 }
119 }
120
121 private static class JumpTarget {
122 private final List<JumpOrigin> origins = new LinkedList<>();
123 private Map<Symbol, LvarType> types = Collections.emptyMap();
124
125 void addOrigin(final JoinPredecessor originNode, final Map<Symbol, LvarType> originTypes) {
126 origins.add(new JumpOrigin(originNode, originTypes));
127 this.types = getUnionTypes(this.types, originTypes);
128 }
129 }
130 private enum LvarType {
131 UNDEFINED(Type.UNDEFINED),
132 BOOLEAN(Type.BOOLEAN),
133 INT(Type.INT),
134 DOUBLE(Type.NUMBER),
135 OBJECT(Type.OBJECT);
136
137 private final Type type;
138 private final TypeHolderExpression typeExpression;
139
140 private LvarType(final Type type) {
141 this.type = type;
142 this.typeExpression = new TypeHolderExpression(type);
143 }
144 }
145
146 /**
147 * A bogus Expression subclass that only reports its type. Used to interrogate BinaryNode and UnaryNode about their
148 * types by creating temporary copies of them and replacing their operands with instances of these. An alternative
149 * solution would be to add BinaryNode.getType(Type lhsType, Type rhsType) and UnaryNode.getType(Type exprType)
150 * methods. For the time being though, this is easier to implement and is in fact fairly clean. It does result in
151 * generation of higher number of temporary short lived nodes, though.
152 */
153 private static class TypeHolderExpression extends Expression {
154 private static final long serialVersionUID = 1L;
155
156 private final Type type;
157
158 TypeHolderExpression(final Type type) {
159 super(0L, 0, 0);
160 this.type = type;
161 }
162
163 @Override
164 public Node accept(final NodeVisitor<? extends LexicalContext> visitor) {
165 throw new AssertionError();
166 }
167
168 @Override
169 public Type getType() {
170 return type;
171 }
172
173 @Override
174 public void toString(final StringBuilder sb, final boolean printType) {
175 throw new AssertionError();
176 }
177 }
178
179 private static final Map<Type, LvarType> TO_LVAR_TYPE = new IdentityHashMap<>();
180
181 static {
182 for(final LvarType lvarType: LvarType.values()) {
183 TO_LVAR_TYPE.put(lvarType.type, lvarType);
184 }
185 }
186
187 @SuppressWarnings("unchecked")
188 private static IdentityHashMap<Symbol, LvarType> cloneMap(final Map<Symbol, LvarType> map) {
189 return (IdentityHashMap<Symbol, LvarType>)((IdentityHashMap<?,?>)map).clone();
190 }
191
192 private LocalVariableConversion createConversion(final Symbol symbol, final LvarType branchLvarType,
193 final Map<Symbol, LvarType> joinLvarTypes, final LocalVariableConversion next) {
194 final LvarType targetType = joinLvarTypes.get(symbol);
195 assert targetType != null;
196 if(targetType == branchLvarType) {
197 return next;
198 }
199 // NOTE: we could naively just use symbolIsUsed(symbol, branchLvarType) here, but that'd be wrong. While
200 // technically a conversion will read the value of the symbol with that type, but it will also write it to a new
201 // type, and that type might be dead (we can't know yet). For this reason, we don't treat conversion reads as
202 // real uses until we know their target type is live. If we didn't do this, and just did a symbolIsUsed here,
203 // we'd introduce false live variables which could nevertheless turn into dead ones in a subsequent
204 // deoptimization, causing a shift in the list of live locals that'd cause erroneous restoration of
205 // continuations (since RewriteException's byteCodeSlots carries an array and not a name-value map).
206
207 symbolIsConverted(symbol, branchLvarType, targetType);
208 return new LocalVariableConversion(symbol, branchLvarType.type, targetType.type, next);
209 }
210
211 private static Map<Symbol, LvarType> getUnionTypes(final Map<Symbol, LvarType> types1, final Map<Symbol, LvarType> types2) {
212 if(types1 == types2 || types1.isEmpty()) {
213 return types2;
214 } else if(types2.isEmpty()) {
215 return types1;
216 }
217 final Set<Symbol> commonSymbols = new HashSet<>(types1.keySet());
218 commonSymbols.retainAll(types2.keySet());
219 // We have a chance of returning an unmodified set if both sets have the same keys and one is strictly wider
220 // than the other.
221 final int commonSize = commonSymbols.size();
222 final int types1Size = types1.size();
223 final int types2Size = types2.size();
224 if(commonSize == types1Size && commonSize == types2Size) {
225 boolean matches1 = true, matches2 = true;
226 Map<Symbol, LvarType> union = null;
227 for(final Symbol symbol: commonSymbols) {
228 final LvarType type1 = types1.get(symbol);
229 final LvarType type2 = types2.get(symbol);
230 final LvarType widest = widestLvarType(type1, type2);
231 if(widest != type1 && matches1) {
232 matches1 = false;
233 if(!matches2) {
234 union = cloneMap(types1);
235 }
236 }
237 if (widest != type2 && matches2) {
238 matches2 = false;
239 if(!matches1) {
240 union = cloneMap(types2);
241 }
242 }
243 if(!(matches1 || matches2)) {
244 assert union != null;
245 union.put(symbol, widest);
246 }
247 }
248 return matches1 ? types1 : matches2 ? types2 : union;
249 }
250 // General case
251 final Map<Symbol, LvarType> union;
252 if(types1Size > types2Size) {
253 union = cloneMap(types1);
254 union.putAll(types2);
255 } else {
256 union = cloneMap(types2);
257 union.putAll(types1);
258 }
259 for(final Symbol symbol: commonSymbols) {
260 final LvarType type1 = types1.get(symbol);
261 final LvarType type2 = types2.get(symbol);
262 union.put(symbol, widestLvarType(type1, type2));
263 }
264 return union;
265 }
266
267 private static void symbolIsUsed(final Symbol symbol, final LvarType type) {
268 if(type != LvarType.UNDEFINED) {
269 symbol.setHasSlotFor(type.type);
270 }
271 }
272
273 private static class SymbolConversions {
274 private static final byte I2D = 1 << 0;
275 private static final byte I2O = 1 << 1;
276 private static final byte D2O = 1 << 2;
277
278 private byte conversions;
279
280 void recordConversion(final LvarType from, final LvarType to) {
281 switch (from) {
282 case UNDEFINED:
283 return;
284 case INT:
285 case BOOLEAN:
286 switch (to) {
287 case DOUBLE:
288 recordConversion(I2D);
289 return;
290 case OBJECT:
291 recordConversion(I2O);
292 return;
293 default:
294 illegalConversion(from, to);
295 return;
296 }
297 case DOUBLE:
298 if(to == LvarType.OBJECT) {
299 recordConversion(D2O);
300 }
301 return;
302 default:
303 illegalConversion(from, to);
304 }
305 }
306
307 private static void illegalConversion(final LvarType from, final LvarType to) {
308 throw new AssertionError("Invalid conversion from " + from + " to " + to);
309 }
310
311 void recordConversion(final byte convFlag) {
312 conversions = (byte)(conversions | convFlag);
313 }
314
315 boolean hasConversion(final byte convFlag) {
316 return (conversions & convFlag) != 0;
317 }
318
319 void calculateTypeLiveness(final Symbol symbol) {
320 if(symbol.hasSlotFor(Type.OBJECT)) {
321 if(hasConversion(D2O)) {
322 symbol.setHasSlotFor(Type.NUMBER);
323 }
324 if(hasConversion(I2O)) {
325 symbol.setHasSlotFor(Type.INT);
326 }
327 }
328 if(symbol.hasSlotFor(Type.NUMBER)) {
329 if(hasConversion(I2D)) {
330 symbol.setHasSlotFor(Type.INT);
331 }
332 }
333 }
334 }
335
336 private void symbolIsConverted(final Symbol symbol, final LvarType from, final LvarType to) {
337 SymbolConversions conversions = symbolConversions.get(symbol);
338 if(conversions == null) {
339 conversions = new SymbolConversions();
340 symbolConversions.put(symbol, conversions);
341 }
342 conversions.recordConversion(from, to);
343 }
344
345 private static LvarType toLvarType(final Type type) {
346 assert type != null;
347 final LvarType lvarType = TO_LVAR_TYPE.get(type);
348 if(lvarType != null) {
349 return lvarType;
350 }
351 assert type.isObject() : "Unsupported primitive type: " + type;
352 return LvarType.OBJECT;
353 }
354 private static LvarType widestLvarType(final LvarType t1, final LvarType t2) {
355 if(t1 == t2) {
356 return t1;
357 }
358 // Undefined or boolean to anything always widens to object.
359 if(t1.ordinal() < LvarType.INT.ordinal() || t2.ordinal() < LvarType.INT.ordinal()) {
360 return LvarType.OBJECT;
361 }
362 // NOTE: we allow "widening" of long to double even though it can lose precision. ECMAScript doesn't have an
363 // Int64 type anyway, so this loss of precision is actually more conformant to the specification...
364 return LvarType.values()[Math.max(t1.ordinal(), t2.ordinal())];
365 }
366 private final Compiler compiler;
367 private final Map<Label, JumpTarget> jumpTargets = new IdentityHashMap<>();
368 // Local variable type mapping at the currently evaluated point. No map instance is ever modified; setLvarType() always
369 // allocates a new map. Immutability of maps allows for cheap snapshots by just keeping the reference to the current
370 // value.
371 private Map<Symbol, LvarType> localVariableTypes = new IdentityHashMap<>();
372 // Stack for evaluated expression types.
373 private final Deque<LvarType> typeStack = new ArrayDeque<>();
374
375 // Whether the current point in the AST is reachable code
376 private boolean reachable = true;
377 // Return type of the function
378 private Type returnType = Type.UNKNOWN;
379 // Synthetic return node that we must insert at the end of the function if it's end is reachable.
380 private ReturnNode syntheticReturn;
381
382 private boolean alreadyEnteredTopLevelFunction;
383
384 // LvarType and conversion information gathered during the top-down pass; applied to nodes in the bottom-up pass.
385 private final Map<JoinPredecessor, LocalVariableConversion> localVariableConversions = new IdentityHashMap<>();
386
387 private final Map<IdentNode, LvarType> identifierLvarTypes = new IdentityHashMap<>();
388 private final Map<Symbol, SymbolConversions> symbolConversions = new IdentityHashMap<>();
389
390 // Stack of open labels for starts of catch blocks, one for every currently traversed try block; for inserting
391 // control flow edges to them. Note that we currently don't insert actual control flow edges, but instead edges that
392 // help us with type calculations. This means that some operations that can result in an exception being thrown
393 // aren't considered (function calls, side effecting property getters and setters etc.), while some operations that
394 // don't result in control flow transfers do originate an edge to the catch blocks (namely, assignments to local
395 // variables).
396 private final Deque<Label> catchLabels = new ArrayDeque<>();
397
398 LocalVariableTypesCalculator(final Compiler compiler) {
399 this.compiler = compiler;
400 }
401
402 private JumpTarget createJumpTarget(final Label label) {
403 assert !jumpTargets.containsKey(label);
404 final JumpTarget jumpTarget = new JumpTarget();
405 jumpTargets.put(label, jumpTarget);
406 return jumpTarget;
407 }
408
409 private void doesNotContinueSequentially() {
410 reachable = false;
411 localVariableTypes = Collections.emptyMap();
412 assertTypeStackIsEmpty();
413 }
414
415 private boolean pushExpressionType(final Expression expr) {
416 typeStack.push(toLvarType(expr.getType()));
417 return false;
418 }
419
420 @Override
421 public boolean enterAccessNode(final AccessNode accessNode) {
422 visitExpression(accessNode.getBase());
423 return pushExpressionType(accessNode);
424 }
425
426 @Override
427 public boolean enterBinaryNode(final BinaryNode binaryNode) {
428 // NOTE: regardless of operator's lexical associativity, lhs is always evaluated first.
429 final Expression lhs = binaryNode.lhs();
430 final LvarType lhsType;
431 if (!(lhs instanceof IdentNode && binaryNode.isTokenType(TokenType.ASSIGN))) {
432 lhsType = visitExpression(lhs);
433 } else {
434 // Can't visit IdentNode on LHS of a simple assignment, as visits imply use, and this is def.
435 // The type is irrelevant, as only RHS is used to determine the type anyway.
436 lhsType = LvarType.UNDEFINED;
437 }
438
439 final boolean isLogical = binaryNode.isLogical();
440 final Label joinLabel = isLogical ? new Label("") : null;
441 if(isLogical) {
442 jumpToLabel((JoinPredecessor)lhs, joinLabel);
443 }
444
445 final Expression rhs = binaryNode.rhs();
446 final LvarType rhsType = visitExpression(rhs);
447 if(isLogical) {
448 jumpToLabel((JoinPredecessor)rhs, joinLabel);
449 }
450 joinOnLabel(joinLabel);
451
452 final LvarType type = toLvarType(binaryNode.setOperands(lhsType.typeExpression, rhsType.typeExpression).getType());
453
454 if(binaryNode.isAssignment() && lhs instanceof IdentNode) {
455 if(binaryNode.isSelfModifying()) {
456 onSelfAssignment((IdentNode)lhs, type);
457 } else {
458 onAssignment((IdentNode)lhs, type);
459 }
460 }
461 typeStack.push(type);
462 return false;
463 }
464
465 @Override
466 public boolean enterBlock(final Block block) {
467 for(final Symbol symbol: block.getSymbols()) {
468 if(symbol.isBytecodeLocal() && getLocalVariableTypeOrNull(symbol) == null) {
469 setType(symbol, LvarType.UNDEFINED);
470 }
471 }
472 return true;
473 }
474
475 @Override
476 public boolean enterBreakNode(final BreakNode breakNode) {
477 return enterJumpStatement(breakNode);
478 }
479
480 @Override
481 public boolean enterCallNode(final CallNode callNode) {
482 visitExpression(callNode.getFunction());
483 visitExpressions(callNode.getArgs());
484 final CallNode.EvalArgs evalArgs = callNode.getEvalArgs();
485 if (evalArgs != null) {
486 visitExpressions(evalArgs.getArgs());
487 }
488 return pushExpressionType(callNode);
489 }
490
491 @Override
492 public boolean enterContinueNode(final ContinueNode continueNode) {
493 return enterJumpStatement(continueNode);
494 }
495
496 private boolean enterJumpStatement(final JumpStatement jump) {
497 if(!reachable) {
498 return false;
499 }
500 assertTypeStackIsEmpty();
501 jumpToLabel(jump, jump.getTargetLabel(lc), getBreakTargetTypes(jump.getPopScopeLimit(lc)));
502 doesNotContinueSequentially();
503 return false;
504 }
505
506 @Override
507 protected boolean enterDefault(final Node node) {
508 return reachable;
509 }
510
511 private void enterDoWhileLoop(final WhileNode loopNode) {
512 assertTypeStackIsEmpty();
513 final JoinPredecessorExpression test = loopNode.getTest();
514 final Block body = loopNode.getBody();
515 final Label continueLabel = loopNode.getContinueLabel();
516 final Label breakLabel = loopNode.getBreakLabel();
517 final Map<Symbol, LvarType> beforeLoopTypes = localVariableTypes;
518 final Label repeatLabel = new Label("");
519 for(;;) {
520 jumpToLabel(loopNode, repeatLabel, beforeLoopTypes);
521 final Map<Symbol, LvarType> beforeRepeatTypes = localVariableTypes;
522 body.accept(this);
523 if(reachable) {
524 jumpToLabel(body, continueLabel);
525 }
526 joinOnLabel(continueLabel);
527 if(!reachable) {
528 break;
529 }
530 visitExpressionOnEmptyStack(test);
531 jumpToLabel(test, breakLabel);
532 if(isAlwaysFalse(test)) {
533 break;
534 }
535 jumpToLabel(test, repeatLabel);
536 joinOnLabel(repeatLabel);
537 if(localVariableTypes.equals(beforeRepeatTypes)) {
538 break;
539 }
540 resetJoinPoint(continueLabel);
541 resetJoinPoint(breakLabel);
542 resetJoinPoint(repeatLabel);
543 }
544
545 if(isAlwaysTrue(test)) {
546 doesNotContinueSequentially();
547 }
548
549 leaveBreakable(loopNode);
550 }
551
552 @Override
553 public boolean enterExpressionStatement(final ExpressionStatement expressionStatement) {
554 if (reachable) {
555 visitExpressionOnEmptyStack(expressionStatement.getExpression());
556 }
557 return false;
558 }
559
560 private void assertTypeStackIsEmpty() {
561 assert typeStack.isEmpty();
562 }
563
564 @Override
565 protected Node leaveDefault(final Node node) {
566 assert !(node instanceof Expression); // All expressions were handled
567 assert !(node instanceof Statement) || typeStack.isEmpty(); // No statements leave with a non-empty stack
568 return node;
569 }
570
571 private LvarType visitExpressionOnEmptyStack(final Expression expr) {
572 assertTypeStackIsEmpty();
573 return visitExpression(expr);
574 }
575
576 private LvarType visitExpression(final Expression expr) {
577 final int stackSize = typeStack.size();
578 expr.accept(this);
579 assert typeStack.size() == stackSize + 1;
580 return typeStack.pop();
581 }
582
583 private void visitExpressions(final List<Expression> exprs) {
584 for(final Expression expr: exprs) {
585 if (expr != null) {
586 visitExpression(expr);
587 }
588 }
589 }
590
591 @Override
592 public boolean enterForNode(final ForNode forNode) {
593 if(!reachable) {
594 return false;
595 }
596
597 final Expression init = forNode.getInit();
598 if(forNode.isForInOrOf()) {
599 final JoinPredecessorExpression iterable = forNode.getModify();
600 visitExpression(iterable);
601 enterTestFirstLoop(forNode, null, init,
602 // If we're iterating over property names, and we can discern from the runtime environment
603 // of the compilation that the object being iterated over must use strings for property
604 // names (e.g., it is a native JS object or array), then we'll not bother trying to treat
605 // the property names optimistically.
606 !compiler.useOptimisticTypes() || (!forNode.isForEach() && compiler.hasStringPropertyIterator(iterable.getExpression())));
607 } else {
608 if(init != null) {
609 visitExpressionOnEmptyStack(init);
610 }
611 enterTestFirstLoop(forNode, forNode.getModify(), null, false);
612 }
613 assertTypeStackIsEmpty();
614 return false;
615 }
616
617 @Override
618 public boolean enterFunctionNode(final FunctionNode functionNode) {
619 if(alreadyEnteredTopLevelFunction) {
620 typeStack.push(LvarType.OBJECT);
621 return false;
622 }
623 int pos = 0;
624 if(!functionNode.isVarArg()) {
625 for (final IdentNode param : functionNode.getParameters()) {
626 final Symbol symbol = param.getSymbol();
627 // Parameter is not necessarily bytecode local as it can be scoped due to nested context use, but it
628 // must have a slot if we aren't in a function with vararg signature.
629 assert symbol.hasSlot();
630 final Type callSiteParamType = compiler.getParamType(functionNode, pos);
631 final LvarType paramType = callSiteParamType == null ? LvarType.OBJECT : toLvarType(callSiteParamType);
632 setType(symbol, paramType);
633 // Make sure parameter slot for its incoming value is not marked dead. NOTE: this is a heuristic. Right
634 // now, CodeGenerator.expandParameters() relies on the fact that every parameter's final slot width will
635 // be at least the same as incoming width, therefore even if a parameter is never read, we'll still keep
636 // its slot.
637 symbolIsUsed(symbol);
638 setIdentifierLvarType(param, paramType);
639 pos++;
640 }
641 }
642 setCompilerConstantAsObject(functionNode, CompilerConstants.THIS);
643
644 // TODO: coarse-grained. If we wanted to solve it completely precisely,
645 // we'd also need to push/pop its type when handling WithNode (so that
646 // it can go back to undefined after a 'with' block.
647 if(functionNode.hasScopeBlock() || functionNode.needsParentScope()) {
648 setCompilerConstantAsObject(functionNode, CompilerConstants.SCOPE);
649 }
650 if(functionNode.needsCallee()) {
651 setCompilerConstantAsObject(functionNode, CompilerConstants.CALLEE);
652 }
653 if(functionNode.needsArguments()) {
654 setCompilerConstantAsObject(functionNode, CompilerConstants.ARGUMENTS);
655 }
656
657 alreadyEnteredTopLevelFunction = true;
658 return true;
659 }
660
661 @Override
662 public boolean enterGetSplitState(final GetSplitState getSplitState) {
663 return pushExpressionType(getSplitState);
664 }
665
666 @Override
667 public boolean enterIdentNode(final IdentNode identNode) {
668 final Symbol symbol = identNode.getSymbol();
669 if(symbol.isBytecodeLocal()) {
670 symbolIsUsed(symbol);
671 final LvarType type = getLocalVariableType(symbol);
672 setIdentifierLvarType(identNode, type);
673 typeStack.push(type);
674 } else {
675 pushExpressionType(identNode);
676 }
677 return false;
678 }
679
680 @Override
681 public boolean enterIfNode(final IfNode ifNode) {
682 processIfNode(ifNode);
683 return false;
684 }
685
686 private void processIfNode(final IfNode ifNode) {
687 if(!reachable) {
688 return;
689 }
690
691 final Expression test = ifNode.getTest();
692 final Block pass = ifNode.getPass();
693 final Block fail = ifNode.getFail();
694
695 visitExpressionOnEmptyStack(test);
696
697 final Map<Symbol, LvarType> passLvarTypes;
698 final boolean reachableFromPass;
699 final boolean isTestAlwaysTrue = isAlwaysTrue(test);
700 if(isAlwaysFalse(test)) {
701 passLvarTypes = null;
702 reachableFromPass = false;
703 } else {
704 final Map<Symbol, LvarType> afterTestLvarTypes = localVariableTypes;
705 pass.accept(this);
706 assertTypeStackIsEmpty();
707 if (isTestAlwaysTrue) {
708 return;
709 }
710 passLvarTypes = localVariableTypes;
711 reachableFromPass = reachable;
712 localVariableTypes = afterTestLvarTypes;
713 reachable = true;
714 }
715
716 // If we get here, then we need to consider the case where pass block is not executed
717 assert !isTestAlwaysTrue;
718
719 if (fail != null) {
720 fail.accept(this);
721 assertTypeStackIsEmpty();
722 }
723
724 if(reachable) {
725 if(reachableFromPass) {
726 final Map<Symbol, LvarType> failLvarTypes = localVariableTypes;
727 localVariableTypes = getUnionTypes(passLvarTypes, failLvarTypes);
728 setConversion(pass, passLvarTypes, localVariableTypes);
729 // IfNode itself is associated with conversions that might need to be performed after the test if
730 // there's no else branch. E.g.
731 // if(x = 1, cond) { x = 1.0 } must widen "x = 1" to a double.
732 setConversion(fail != null ? fail : ifNode, failLvarTypes, localVariableTypes);
733 }
734 } else if (reachableFromPass) {
735 assert passLvarTypes != null;
736 localVariableTypes = passLvarTypes;
737 reachable = true;
738 }
739 }
740
741 @Override
742 public boolean enterIndexNode(final IndexNode indexNode) {
743 visitExpression(indexNode.getBase());
744 visitExpression(indexNode.getIndex());
745 return pushExpressionType(indexNode);
746 }
747
748 @Override
749 public boolean enterJoinPredecessorExpression(final JoinPredecessorExpression joinExpr) {
750 final Expression expr = joinExpr.getExpression();
751 if (expr != null) {
752 expr.accept(this);
753 } else {
754 typeStack.push(LvarType.UNDEFINED);
755 }
756 return false;
757 }
758
759 @Override
760 public boolean enterJumpToInlinedFinally(final JumpToInlinedFinally jumpToInlinedFinally) {
761 return enterJumpStatement(jumpToInlinedFinally);
762 }
763
764 @Override
765 public boolean enterLiteralNode(final LiteralNode<?> literalNode) {
766 if (literalNode instanceof ArrayLiteralNode) {
767 final List<Expression> expressions = ((ArrayLiteralNode)literalNode).getElementExpressions();
768 if (expressions != null) {
769 visitExpressions(expressions);
770 }
771 }
772 pushExpressionType(literalNode);
773 return false;
774 }
775
776 @Override
777 public boolean enterObjectNode(final ObjectNode objectNode) {
778 for(final PropertyNode propertyNode: objectNode.getElements()) {
779 // Avoid falsely adding property keys to the control flow graph
780 final Expression value = propertyNode.getValue();
781 if (value != null) {
782 visitExpression(value);
783 }
784 }
785 return pushExpressionType(objectNode);
786 }
787
788 @Override
789 public boolean enterPropertyNode(final PropertyNode propertyNode) {
790 // Property nodes are only accessible through object literals, and we handled that case above
791 throw new AssertionError();
792 }
793
794 @Override
795 public boolean enterReturnNode(final ReturnNode returnNode) {
796 if(!reachable) {
797 return false;
798 }
799
800 final Expression returnExpr = returnNode.getExpression();
801 final Type returnExprType;
802 if(returnExpr != null) {
803 returnExprType = visitExpressionOnEmptyStack(returnExpr).type;
804 } else {
805 assertTypeStackIsEmpty();
806 returnExprType = Type.UNDEFINED;
807 }
808 returnType = Type.widestReturnType(returnType, returnExprType);
809 doesNotContinueSequentially();
810 return false;
811 }
812
813 @Override
814 public boolean enterRuntimeNode(final RuntimeNode runtimeNode) {
815 visitExpressions(runtimeNode.getArgs());
816 return pushExpressionType(runtimeNode);
817 }
818
819 @Override
820 public boolean enterSplitReturn(final SplitReturn splitReturn) {
821 doesNotContinueSequentially();
822 return false;
823 }
824
825 @Override
826 public boolean enterSwitchNode(final SwitchNode switchNode) {
827 if(!reachable) {
828 return false;
829 }
830
831 visitExpressionOnEmptyStack(switchNode.getExpression());
832
833 final List<CaseNode> cases = switchNode.getCases();
834 if(cases.isEmpty()) {
835 return false;
836 }
837
838 // Control flow is different for all-integer cases where we dispatch by switch table, and for all other cases
839 // where we do sequential comparison. Note that CaseNode objects act as join points.
840 final boolean isInteger = switchNode.isUniqueInteger();
841 final Label breakLabel = switchNode.getBreakLabel();
842 final boolean hasDefault = switchNode.getDefaultCase() != null;
843
844 boolean tagUsed = false;
845 for(final CaseNode caseNode: cases) {
846 final Expression test = caseNode.getTest();
847 if(!isInteger && test != null) {
848 visitExpressionOnEmptyStack(test);
849 if(!tagUsed) {
850 symbolIsUsed(switchNode.getTag(), LvarType.OBJECT);
851 tagUsed = true;
852 }
853 }
854 // CaseNode carries the conversions that need to be performed on its entry from the test.
855 // CodeGenerator ensures these are only emitted when arriving on the branch and not through a
856 // fallthrough.
857 jumpToLabel(caseNode, caseNode.getBody().getEntryLabel());
858 }
859 if(!hasDefault) {
860 // No default case means we can arrive at the break label without entering any cases. In that case
861 // SwitchNode will carry the conversions that need to be performed before it does that jump.
862 jumpToLabel(switchNode, breakLabel);
863 }
864
865 // All cases are arrived at through jumps
866 doesNotContinueSequentially();
867
868 Block previousBlock = null;
869 for(final CaseNode caseNode: cases) {
870 final Block body = caseNode.getBody();
871 final Label entryLabel = body.getEntryLabel();
872 if(previousBlock != null && reachable) {
873 jumpToLabel(previousBlock, entryLabel);
874 }
875 joinOnLabel(entryLabel);
876 assert reachable == true;
877 body.accept(this);
878 previousBlock = body;
879 }
880 if(previousBlock != null && reachable) {
881 jumpToLabel(previousBlock, breakLabel);
882 }
883 leaveBreakable(switchNode);
884 return false;
885 }
886
887 @Override
888 public boolean enterTernaryNode(final TernaryNode ternaryNode) {
889 final Expression test = ternaryNode.getTest();
890 final Expression trueExpr = ternaryNode.getTrueExpression();
891 final Expression falseExpr = ternaryNode.getFalseExpression();
892
893 visitExpression(test);
894
895 final Map<Symbol, LvarType> testExitLvarTypes = localVariableTypes;
896 final LvarType trueType;
897 if(!isAlwaysFalse(test)) {
898 trueType = visitExpression(trueExpr);
899 } else {
900 trueType = null;
901 }
902 final Map<Symbol, LvarType> trueExitLvarTypes = localVariableTypes;
903 localVariableTypes = testExitLvarTypes;
904 final LvarType falseType;
905 if(!isAlwaysTrue(test)) {
906 falseType = visitExpression(falseExpr);
907 } else {
908 falseType = null;
909 }
910 final Map<Symbol, LvarType> falseExitLvarTypes = localVariableTypes;
911 localVariableTypes = getUnionTypes(trueExitLvarTypes, falseExitLvarTypes);
912 setConversion((JoinPredecessor)trueExpr, trueExitLvarTypes, localVariableTypes);
913 setConversion((JoinPredecessor)falseExpr, falseExitLvarTypes, localVariableTypes);
914
915 typeStack.push(trueType != null ? falseType != null ? widestLvarType(trueType, falseType) : trueType : assertNotNull(falseType));
916 return false;
917 }
918
919 private static <T> T assertNotNull(final T t) {
920 assert t != null;
921 return t;
922 }
923
924 private void enterTestFirstLoop(final LoopNode loopNode, final JoinPredecessorExpression modify,
925 final Expression iteratorValues, final boolean iteratorValuesAreObject) {
926 final JoinPredecessorExpression test = loopNode.getTest();
927 if(isAlwaysFalse(test)) {
928 visitExpressionOnEmptyStack(test);
929 return;
930 }
931
932 final Label continueLabel = loopNode.getContinueLabel();
933 final Label breakLabel = loopNode.getBreakLabel();
934
935 final Label repeatLabel = modify == null ? continueLabel : new Label("");
936 final Map<Symbol, LvarType> beforeLoopTypes = localVariableTypes;
937 for(;;) {
938 jumpToLabel(loopNode, repeatLabel, beforeLoopTypes);
939 final Map<Symbol, LvarType> beforeRepeatTypes = localVariableTypes;
940 if(test != null) {
941 visitExpressionOnEmptyStack(test);
942 }
943 if(!isAlwaysTrue(test)) {
944 jumpToLabel(test, breakLabel);
945 }
946 if(iteratorValues instanceof IdentNode) {
947 final IdentNode ident = (IdentNode)iteratorValues;
948 // Receives iterator values; the optimistic type of the iterator values is tracked on the
949 // identifier, but we override optimism if it's known that the object being iterated over will
950 // never have primitive property names.
951 onAssignment(ident, iteratorValuesAreObject ? LvarType.OBJECT :
952 toLvarType(compiler.getOptimisticType(ident)));
953 }
954 final Block body = loopNode.getBody();
955 body.accept(this);
956 if(reachable) {
957 jumpToLabel(body, continueLabel);
958 }
959 joinOnLabel(continueLabel);
960 if(!reachable) {
961 break;
962 }
963 if(modify != null) {
964 visitExpressionOnEmptyStack(modify);
965 jumpToLabel(modify, repeatLabel);
966 joinOnLabel(repeatLabel);
967 }
968 if(localVariableTypes.equals(beforeRepeatTypes)) {
969 break;
970 }
971 // Reset the join points and repeat the analysis
972 resetJoinPoint(continueLabel);
973 resetJoinPoint(breakLabel);
974 resetJoinPoint(repeatLabel);
975 }
976
977 if(isAlwaysTrue(test) && iteratorValues == null) {
978 doesNotContinueSequentially();
979 }
980
981 leaveBreakable(loopNode);
982 }
983
984 @Override
985 public boolean enterThrowNode(final ThrowNode throwNode) {
986 if(!reachable) {
987 return false;
988 }
989
990 visitExpressionOnEmptyStack(throwNode.getExpression());
991 jumpToCatchBlock(throwNode);
992 doesNotContinueSequentially();
993 return false;
994 }
995
996 @Override
997 public boolean enterTryNode(final TryNode tryNode) {
998 if(!reachable) {
999 return false;
1000 }
1001
1002 // This is the label for the join point at the entry of the catch blocks.
1003 final Label catchLabel = new Label("");
1004 catchLabels.push(catchLabel);
1005
1006 // Presume that even the start of the try block can immediately go to the catch
1007 jumpToLabel(tryNode, catchLabel);
1008
1009 final Block body = tryNode.getBody();
1010 body.accept(this);
1011 catchLabels.pop();
1012
1013 // Final exit label for the whole try/catch construct (after the try block and after all catches).
1014 final Label endLabel = new Label("");
1015
1016 boolean canExit = false;
1017 if(reachable) {
1018 jumpToLabel(body, endLabel);
1019 canExit = true;
1020 }
1021 doesNotContinueSequentially();
1022
1023 for (final Block inlinedFinally : tryNode.getInlinedFinallies()) {
1024 final Block finallyBody = TryNode.getLabelledInlinedFinallyBlock(inlinedFinally);
1025 joinOnLabel(finallyBody.getEntryLabel());
1026 // NOTE: the jump to inlined finally can end up in dead code, so it is not necessarily reachable.
1027 if (reachable) {
1028 finallyBody.accept(this);
1029 // All inlined finallies end with a jump or a return
1030 assert !reachable;
1031 }
1032 }
1033
1034 joinOnLabel(catchLabel);
1035 for(final CatchNode catchNode: tryNode.getCatches()) {
1036 final IdentNode exception = catchNode.getException();
1037 onAssignment(exception, LvarType.OBJECT);
1038 final Expression condition = catchNode.getExceptionCondition();
1039 if(condition != null) {
1040 visitExpression(condition);
1041 }
1042 final Map<Symbol, LvarType> afterConditionTypes = localVariableTypes;
1043 final Block catchBody = catchNode.getBody();
1044 // TODO: currently, we consider that the catch blocks are always reachable from the try block as currently
1045 // we lack enough analysis to prove that no statement before a break/continue/return in the try block can
1046 // throw an exception.
1047 reachable = true;
1048 catchBody.accept(this);
1049 final Symbol exceptionSymbol = exception.getSymbol();
1050 if(reachable) {
1051 localVariableTypes = cloneMap(localVariableTypes);
1052 localVariableTypes.remove(exceptionSymbol);
1053 jumpToLabel(catchBody, endLabel);
1054 canExit = true;
1055 }
1056 localVariableTypes = cloneMap(afterConditionTypes);
1057 localVariableTypes.remove(exceptionSymbol);
1058 }
1059 // NOTE: if we had one or more conditional catch blocks with no unconditional catch block following them, then
1060 // there will be an unconditional rethrow, so the join point can never be reached from the last
1061 // conditionExpression.
1062 doesNotContinueSequentially();
1063
1064 if(canExit) {
1065 joinOnLabel(endLabel);
1066 }
1067
1068 return false;
1069 }
1070
1071
1072 @Override
1073 public boolean enterUnaryNode(final UnaryNode unaryNode) {
1074 final Expression expr = unaryNode.getExpression();
1075 final LvarType unaryType = toLvarType(unaryNode.setExpression(visitExpression(expr).typeExpression).getType());
1076 if(unaryNode.isSelfModifying() && expr instanceof IdentNode) {
1077 onSelfAssignment((IdentNode)expr, unaryType);
1078 }
1079 typeStack.push(unaryType);
1080 return false;
1081 }
1082
1083 @Override
1084 public boolean enterVarNode(final VarNode varNode) {
1085 if (!reachable) {
1086 return false;
1087 }
1088 final Expression init = varNode.getInit();
1089 if(init != null) {
1090 onAssignment(varNode.getName(), visitExpression(init));
1091 }
1092 return false;
1093 }
1094
1095 @Override
1096 public boolean enterWhileNode(final WhileNode whileNode) {
1097 if(!reachable) {
1098 return false;
1099 }
1100 if(whileNode.isDoWhile()) {
1101 enterDoWhileLoop(whileNode);
1102 } else {
1103 enterTestFirstLoop(whileNode, null, null, false);
1104 }
1105 return false;
1106 }
1107
1108 @Override
1109 public boolean enterWithNode(final WithNode withNode) {
1110 if (reachable) {
1111 visitExpression(withNode.getExpression());
1112 withNode.getBody().accept(this);
1113 }
1114 return false;
1115 };
1116
1117 private Map<Symbol, LvarType> getBreakTargetTypes(final LexicalContextNode target) {
1118 // Remove symbols defined in the the blocks that are being broken out of.
1119 Map<Symbol, LvarType> types = localVariableTypes;
1120 for(final Iterator<LexicalContextNode> it = lc.getAllNodes(); it.hasNext();) {
1121 final LexicalContextNode node = it.next();
1122 if(node instanceof Block) {
1123 for(final Symbol symbol: ((Block)node).getSymbols()) {
1124 if(localVariableTypes.containsKey(symbol)) {
1125 if(types == localVariableTypes) {
1126 types = cloneMap(localVariableTypes);
1127 }
1128 types.remove(symbol);
1129 }
1130 }
1131 }
1132 if(node == target) {
1133 break;
1134 }
1135 }
1136 return types;
1137 }
1138
1139 /**
1140 * Returns the current type of the local variable represented by the symbol. This is the most strict of all
1141 * {@code getLocalVariableType*} methods, as it will throw an assertion if the type is null. Therefore, it is only
1142 * safe to be invoked on symbols known to be bytecode locals, and only after they have been initialized.
1143 * Regardless, it is recommended to use this method in majority of cases, as because of its strictness it is the
1144 * best suited for catching missing type calculation bugs early.
1145 * @param symbol a symbol representing a bytecode local variable.
1146 * @return the current type of the local variable represented by the symbol
1147 */
1148 private LvarType getLocalVariableType(final Symbol symbol) {
1149 final LvarType type = getLocalVariableTypeOrNull(symbol);
1150 assert type != null;
1151 return type;
1152 }
1153
1154 /**
1155 * Gets the type for a variable represented by a symbol, or null if the type is not know. This is the least strict
1156 * of all local variable type getters, and as such its use is discouraged except in initialization scenarios (where
1157 * a just-defined symbol might still be null).
1158 * @param symbol the symbol
1159 * @return the current type for the symbol, or null if the type is not known either because the symbol has not been
1160 * initialized, or because the symbol does not represent a bytecode local variable.
1161 */
1162 private LvarType getLocalVariableTypeOrNull(final Symbol symbol) {
1163 return localVariableTypes.get(symbol);
1164 }
1165
1166 private JumpTarget getOrCreateJumpTarget(final Label label) {
1167 JumpTarget jumpTarget = jumpTargets.get(label);
1168 if(jumpTarget == null) {
1169 jumpTarget = createJumpTarget(label);
1170 }
1171 return jumpTarget;
1172 }
1173
1174
1175 /**
1176 * If there's a join point associated with a label, insert the join point into the flow.
1177 * @param label the label to insert a join point for.
1178 */
1179 private void joinOnLabel(final Label label) {
1180 final JumpTarget jumpTarget = jumpTargets.remove(label);
1181 if(jumpTarget == null) {
1182 return;
1183 }
1184 assert !jumpTarget.origins.isEmpty();
1185 reachable = true;
1186 localVariableTypes = getUnionTypes(jumpTarget.types, localVariableTypes);
1187 for(final JumpOrigin jumpOrigin: jumpTarget.origins) {
1188 setConversion(jumpOrigin.node, jumpOrigin.types, localVariableTypes);
1189 }
1190 }
1191
1192 /**
1193 * If we're in a try/catch block, add an edge from the specified node to the try node's pre-catch label.
1194 */
1195 private void jumpToCatchBlock(final JoinPredecessor jumpOrigin) {
1196 final Label currentCatchLabel = catchLabels.peek();
1197 if(currentCatchLabel != null) {
1198 jumpToLabel(jumpOrigin, currentCatchLabel);
1199 }
1200 }
1201
1202 private void jumpToLabel(final JoinPredecessor jumpOrigin, final Label label) {
1203 jumpToLabel(jumpOrigin, label, localVariableTypes);
1204 }
1205
1206 private void jumpToLabel(final JoinPredecessor jumpOrigin, final Label label, final Map<Symbol, LvarType> types) {
1207 getOrCreateJumpTarget(label).addOrigin(jumpOrigin, types);
1208 }
1209
1210 @Override
1211 public Node leaveBlock(final Block block) {
1212 if(lc.isFunctionBody()) {
1213 if(reachable) {
1214 // reachable==true means we can reach the end of the function without an explicit return statement. We
1215 // need to insert a synthetic one then. This logic used to be in Lower.leaveBlock(), but Lower's
1216 // reachability analysis (through Terminal.isTerminal() flags) is not precise enough so
1217 // Lower$BlockLexicalContext.afterSetStatements will sometimes think the control flow terminates even
1218 // when it didn't. Example: function() { switch((z)) { default: {break; } throw x; } }.
1219 createSyntheticReturn(block);
1220 assert !reachable;
1221 }
1222 // We must calculate the return type here (and not in leaveFunctionNode) as it can affect the liveness of
1223 // the :return symbol and thus affect conversion type liveness calculations for it.
1224 calculateReturnType();
1225 }
1226
1227 boolean cloned = false;
1228 for(final Symbol symbol: block.getSymbols()) {
1229 // Undefine the symbol outside the block
1230 if(localVariableTypes.containsKey(symbol)) {
1231 if(!cloned) {
1232 localVariableTypes = cloneMap(localVariableTypes);
1233 cloned = true;
1234 }
1235 localVariableTypes.remove(symbol);
1236 }
1237
1238 if(symbol.hasSlot()) {
1239 final SymbolConversions conversions = symbolConversions.get(symbol);
1240 if(conversions != null) {
1241 // Potentially make some currently dead types live if they're needed as a source of a type
1242 // conversion at a join.
1243 conversions.calculateTypeLiveness(symbol);
1244 }
1245 if(symbol.slotCount() == 0) {
1246 // This is a local variable that is never read. It won't need a slot.
1247 symbol.setNeedsSlot(false);
1248 }
1249 }
1250 }
1251
1252 if(reachable) {
1253 // TODO: this is totally backwards. Block should not be breakable, LabelNode should be breakable.
1254 final LabelNode labelNode = lc.getCurrentBlockLabelNode();
1255 if(labelNode != null) {
1256 jumpToLabel(labelNode, block.getBreakLabel());
1257 }
1258 }
1259 leaveBreakable(block);
1260 return block;
1261 }
1262
1263 private void calculateReturnType() {
1264 // NOTE: if return type is unknown, then the function does not explicitly return a value. Such a function under
1265 // ECMAScript rules returns Undefined, which has Type.OBJECT. We might consider an optimization in the future
1266 // where we can return void functions.
1267 if(returnType.isUnknown()) {
1268 returnType = Type.OBJECT;
1269 }
1270 }
1271
1272 private void createSyntheticReturn(final Block body) {
1273 final FunctionNode functionNode = lc.getCurrentFunction();
1274 final long token = functionNode.getToken();
1275 final int finish = functionNode.getFinish();
1276 final List<Statement> statements = body.getStatements();
1277 final int lineNumber = statements.isEmpty() ? functionNode.getLineNumber() : statements.get(statements.size() - 1).getLineNumber();
1278 final IdentNode returnExpr;
1279 if(functionNode.isProgram()) {
1280 returnExpr = new IdentNode(token, finish, RETURN.symbolName()).setSymbol(getCompilerConstantSymbol(functionNode, RETURN));
1281 } else {
1282 returnExpr = null;
1283 }
1284 syntheticReturn = new ReturnNode(lineNumber, token, finish, returnExpr);
1285 syntheticReturn.accept(this);
1286 }
1287
1288 /**
1289 * Leave a breakable node. If there's a join point associated with its break label (meaning there was at least one
1290 * break statement to the end of the node), insert the join point into the flow.
1291 * @param breakable the breakable node being left.
1292 */
1293 private void leaveBreakable(final BreakableNode breakable) {
1294 joinOnLabel(breakable.getBreakLabel());
1295 assertTypeStackIsEmpty();
1296 }
1297
1298 @Override
1299 public Node leaveFunctionNode(final FunctionNode functionNode) {
1300 // Sets the return type of the function and also performs the bottom-up pass of applying type and conversion
1301 // information to nodes as well as doing the calculation on nested functions as required.
1302 FunctionNode newFunction = functionNode;
1303 final SimpleNodeVisitor applyChangesVisitor = new SimpleNodeVisitor() {
1304 private boolean inOuterFunction = true;
1305 private final Deque<JoinPredecessor> joinPredecessors = new ArrayDeque<>();
1306
1307 @Override
1308 protected boolean enterDefault(final Node node) {
1309 if(!inOuterFunction) {
1310 return false;
1311 }
1312 if(node instanceof JoinPredecessor) {
1313 joinPredecessors.push((JoinPredecessor)node);
1314 }
1315 return inOuterFunction;
1316 }
1317
1318 @Override
1319 public boolean enterFunctionNode(final FunctionNode fn) {
1320 if(compiler.isOnDemandCompilation()) {
1321 // Only calculate nested function local variable types if we're doing eager compilation
1322 return false;
1323 }
1324 inOuterFunction = false;
1325 return true;
1326 }
1327
1328 @SuppressWarnings("fallthrough")
1329 @Override
1330 public Node leaveBinaryNode(final BinaryNode binaryNode) {
1331 if(binaryNode.isComparison()) {
1332 final Expression lhs = binaryNode.lhs();
1333 final Expression rhs = binaryNode.rhs();
1334
1335 final TokenType tt = binaryNode.tokenType();
1336 switch (tt) {
1337 case EQ_STRICT:
1338 case NE_STRICT:
1339 // Specialize comparison with undefined
1340 final Expression undefinedNode = createIsUndefined(binaryNode, lhs, rhs,
1341 tt == TokenType.EQ_STRICT ? Request.IS_UNDEFINED : Request.IS_NOT_UNDEFINED);
1342 if(undefinedNode != binaryNode) {
1343 return undefinedNode;
1344 }
1345 // Specialize comparison of boolean with non-boolean
1346 if (lhs.getType().isBoolean() != rhs.getType().isBoolean()) {
1347 return new RuntimeNode(binaryNode);
1348 }
1349 // fallthrough
1350 default:
1351 if (lhs.getType().isObject() && rhs.getType().isObject()) {
1352 return new RuntimeNode(binaryNode);
1353 }
1354 }
1355 } else if(binaryNode.isOptimisticUndecidedType()) {
1356 // At this point, we can assign a static type to the optimistic binary ADD operator as now we know
1357 // the types of its operands.
1358 return binaryNode.decideType();
1359 }
1360 return binaryNode;
1361 }
1362
1363 @Override
1364 protected Node leaveDefault(final Node node) {
1365 if(node instanceof JoinPredecessor) {
1366 final JoinPredecessor original = joinPredecessors.pop();
1367 assert original.getClass() == node.getClass() : original.getClass().getName() + "!=" + node.getClass().getName();
1368 final JoinPredecessor newNode = setLocalVariableConversion(original, (JoinPredecessor)node);
1369 if (newNode instanceof LexicalContextNode) {
1370 lc.replace((LexicalContextNode)node, (LexicalContextNode)newNode);
1371 }
1372 return (Node)newNode;
1373 }
1374 return node;
1375 }
1376
1377 @Override
1378 public Node leaveBlock(final Block block) {
1379 if(inOuterFunction && syntheticReturn != null && lc.isFunctionBody()) {
1380 final ArrayList<Statement> stmts = new ArrayList<>(block.getStatements());
1381 stmts.add((ReturnNode)syntheticReturn.accept(this));
1382 return block.setStatements(lc, stmts);
1383 }
1384 return super.leaveBlock(block);
1385 }
1386
1387 @Override
1388 public Node leaveFunctionNode(final FunctionNode nestedFunctionNode) {
1389 inOuterFunction = true;
1390 final FunctionNode newNestedFunction = (FunctionNode)nestedFunctionNode.accept(
1391 new LocalVariableTypesCalculator(compiler));
1392 lc.replace(nestedFunctionNode, newNestedFunction);
1393 return newNestedFunction;
1394 }
1395
1396 @Override
1397 public Node leaveIdentNode(final IdentNode identNode) {
1398 final IdentNode original = (IdentNode)joinPredecessors.pop();
1399 final Symbol symbol = identNode.getSymbol();
1400 if(symbol == null) {
1401 assert identNode.isPropertyName();
1402 return identNode;
1403 } else if(symbol.hasSlot()) {
1404 assert !symbol.isScope() || symbol.isParam(); // Only params can be slotted and scoped.
1405 assert original.getName().equals(identNode.getName());
1406 final LvarType lvarType = identifierLvarTypes.remove(original);
1407 if(lvarType != null) {
1408 return setLocalVariableConversion(original, identNode.setType(lvarType.type));
1409 }
1410 // If there's no type, then the identifier must've been in unreachable code. In that case, it can't
1411 // have assigned conversions either.
1412 assert localVariableConversions.get(original) == null;
1413 } else {
1414 assert identIsDeadAndHasNoLiveConversions(original);
1415 }
1416 return identNode;
1417 }
1418
1419 @Override
1420 public Node leaveLiteralNode(final LiteralNode<?> literalNode) {
1421 //for e.g. ArrayLiteralNodes the initial types may have been narrowed due to the
1422 //introduction of optimistic behavior - hence ensure that all literal nodes are
1423 //reinitialized
1424 return literalNode.initialize(lc);
1425 }
1426
1427 @Override
1428 public Node leaveRuntimeNode(final RuntimeNode runtimeNode) {
1429 final Request request = runtimeNode.getRequest();
1430 final boolean isEqStrict = request == Request.EQ_STRICT;
1431 if(isEqStrict || request == Request.NE_STRICT) {
1432 return createIsUndefined(runtimeNode, runtimeNode.getArgs().get(0), runtimeNode.getArgs().get(1),
1433 isEqStrict ? Request.IS_UNDEFINED : Request.IS_NOT_UNDEFINED);
1434 }
1435 return runtimeNode;
1436 }
1437
1438 @SuppressWarnings("unchecked")
1439 private <T extends JoinPredecessor> T setLocalVariableConversion(final JoinPredecessor original, final T jp) {
1440 // NOTE: can't use Map.remove() as our copy-on-write AST semantics means some nodes appear twice (in
1441 // finally blocks), so we need to be able to access conversions for them multiple times.
1442 return (T)jp.setLocalVariableConversion(lc, localVariableConversions.get(original));
1443 }
1444 };
1445
1446 newFunction = newFunction.setBody(lc, (Block)newFunction.getBody().accept(applyChangesVisitor));
1447 newFunction = newFunction.setReturnType(lc, returnType);
1448
1449
1450 newFunction = newFunction.setParameters(lc, newFunction.visitParameters(applyChangesVisitor));
1451 return newFunction;
1452 }
1453
1454 private static Expression createIsUndefined(final Expression parent, final Expression lhs, final Expression rhs, final Request request) {
1455 if (isUndefinedIdent(lhs) || isUndefinedIdent(rhs)) {
1456 return new RuntimeNode(parent, request, lhs, rhs);
1457 }
1458 return parent;
1459 }
1460
1461 private static boolean isUndefinedIdent(final Expression expr) {
1462 return expr instanceof IdentNode && "undefined".equals(((IdentNode)expr).getName());
1463 }
1464
1465 private boolean identIsDeadAndHasNoLiveConversions(final IdentNode identNode) {
1466 final LocalVariableConversion conv = localVariableConversions.get(identNode);
1467 return conv == null || !conv.isLive();
1468 }
1469
1470 private void onAssignment(final IdentNode identNode, final LvarType type) {
1471 final Symbol symbol = identNode.getSymbol();
1472 assert symbol != null : identNode.getName();
1473 if(!symbol.isBytecodeLocal()) {
1474 return;
1475 }
1476 assert type != null;
1477 final LvarType finalType;
1478 if(type == LvarType.UNDEFINED && getLocalVariableType(symbol) != LvarType.UNDEFINED) {
1479 // Explicit assignment of a known undefined local variable to a local variable that is not undefined will
1480 // materialize that undefined in the assignment target. Note that assigning known undefined to known
1481 // undefined will *not* initialize the variable, e.g. "var x; var y = x;" compiles to no-op.
1482 finalType = LvarType.OBJECT;
1483 symbol.setFlag(Symbol.HAS_OBJECT_VALUE);
1484 } else {
1485 finalType = type;
1486 }
1487 setType(symbol, finalType);
1488 // Explicit assignment of an undefined value. Make sure the variable can store an object
1489 // TODO: if we communicated the fact to codegen with a flag on the IdentNode that the value was already
1490 // undefined before the assignment, we could just ignore it. In general, we could ignore an assignment if we
1491 // know that the value assigned is the same as the current value of the variable, but we'd need constant
1492 // propagation for that.
1493 setIdentifierLvarType(identNode, finalType);
1494 // For purposes of type calculation, we consider an assignment to a local variable to be followed by
1495 // the catch nodes of the current (if any) try block. This will effectively enforce that narrower
1496 // assignments to a local variable in a try block will also have to store a widened value as well. Code
1497 // within the try block will be able to keep loading the narrower value, but after the try block only
1498 // the widest value will remain live.
1499 // Rationale for this is that if there's an use for that variable in any of the catch blocks, or
1500 // following the catch blocks, they must use the widest type.
1501 // Example:
1502 /*
1503 Originally:
1504 ===========
1505 var x;
1506 try {
1507 x = 1; <-- stores into int slot for x
1508 f(x); <-- loads the int slot for x
1509 x = 3.14 <-- stores into the double slot for x
1510 f(x); <-- loads the double slot for x
1511 x = 1; <-- stores into int slot for x
1512 f(x); <-- loads the int slot for x
1513 } finally {
1514 f(x); <-- loads the double slot for x, but can be reached by a path where x is int, so we need
1515 to go back and ensure that double values are also always stored along with int
1516 values.
1517 }
1518
1519 After correction:
1520 =================
1521
1522 var x;
1523 try {
1524 x = 1; <-- stores into both int and double slots for x
1525 f(x); <-- loads the int slot for x
1526 x = 3.14 <-- stores into the double slot for x
1527 f(x); <-- loads the double slot for x
1528 x = 1; <-- stores into both int and double slots for x
1529 f(x); <-- loads the int slot for x
1530 } finally {
1531 f(x); <-- loads the double slot for x
1532 }
1533 */
1534 jumpToCatchBlock(identNode);
1535 }
1536
1537 private void onSelfAssignment(final IdentNode identNode, final LvarType type) {
1538 final Symbol symbol = identNode.getSymbol();
1539 assert symbol != null : identNode.getName();
1540 if(!symbol.isBytecodeLocal()) {
1541 return;
1542 }
1543 // Self-assignment never produce either a boolean or undefined
1544 assert type != null && type != LvarType.UNDEFINED && type != LvarType.BOOLEAN;
1545 setType(symbol, type);
1546 jumpToCatchBlock(identNode);
1547 }
1548
1549 private void resetJoinPoint(final Label label) {
1550 jumpTargets.remove(label);
1551 }
1552
1553 private void setCompilerConstantAsObject(final FunctionNode functionNode, final CompilerConstants cc) {
1554 final Symbol symbol = getCompilerConstantSymbol(functionNode, cc);
1555 setType(symbol, LvarType.OBJECT);
1556 // never mark compiler constants as dead
1557 symbolIsUsed(symbol);
1558 }
1559
1560 private static Symbol getCompilerConstantSymbol(final FunctionNode functionNode, final CompilerConstants cc) {
1561 return functionNode.getBody().getExistingSymbol(cc.symbolName());
1562 }
1563
1564 private void setConversion(final JoinPredecessor node, final Map<Symbol, LvarType> branchLvarTypes, final Map<Symbol, LvarType> joinLvarTypes) {
1565 if(node == null) {
1566 return;
1567 }
1568 if(branchLvarTypes.isEmpty() || joinLvarTypes.isEmpty()) {
1569 localVariableConversions.remove(node);
1570 }
1571
1572 LocalVariableConversion conversion = null;
1573 if(node instanceof IdentNode) {
1574 // conversions on variable assignment in try block are special cases, as they only apply to the variable
1575 // being assigned and all other conversions should be ignored.
1576 final Symbol symbol = ((IdentNode)node).getSymbol();
1577 conversion = createConversion(symbol, branchLvarTypes.get(symbol), joinLvarTypes, null);
1578 } else {
1579 for(final Map.Entry<Symbol, LvarType> entry: branchLvarTypes.entrySet()) {
1580 final Symbol symbol = entry.getKey();
1581 final LvarType branchLvarType = entry.getValue();
1582 conversion = createConversion(symbol, branchLvarType, joinLvarTypes, conversion);
1583 }
1584 }
1585 if(conversion != null) {
1586 localVariableConversions.put(node, conversion);
1587 } else {
1588 localVariableConversions.remove(node);
1589 }
1590 }
1591
1592 private void setIdentifierLvarType(final IdentNode identNode, final LvarType type) {
1593 assert type != null;
1594 identifierLvarTypes.put(identNode, type);
1595 }
1596
1597 /**
1598 * Marks a local variable as having a specific type from this point onward. Invoked by stores to local variables.
1599 * @param symbol the symbol representing the variable
1600 * @param type the type
1601 */
1602 private void setType(final Symbol symbol, final LvarType type) {
1603 if(getLocalVariableTypeOrNull(symbol) == type) {
1604 return;
1605 }
1606 assert symbol.hasSlot();
1607 assert !symbol.isGlobal();
1608 localVariableTypes = localVariableTypes.isEmpty() ? new IdentityHashMap<Symbol, LvarType>() : cloneMap(localVariableTypes);
1609 localVariableTypes.put(symbol, type);
1610 }
1611
1612 /**
1613 * Set a flag in the symbol marking it as needing to be able to store a value of a particular type. Every symbol for
1614 * a local variable will be assigned between 1 and 6 local variable slots for storing all types it is known to need
1615 * to store.
1616 * @param symbol the symbol
1617 */
1618 private void symbolIsUsed(final Symbol symbol) {
1619 symbolIsUsed(symbol, getLocalVariableType(symbol));
1620 }
1621 }