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