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