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