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