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