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