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