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 final byte I2L = 1 << 0; 276 private static final byte I2D = 1 << 1; 277 private static final byte I2O = 1 << 2; 278 private static final byte L2D = 1 << 3; 279 private static final byte L2O = 1 << 4; 280 private static final 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 }