LocalVariableTypesCalculator.java revision 1137:81752184ec8a
1216295Ssyrinx/* 2216295Ssyrinx * Copyright (c) 2010, 2013, Oracle and/or its affiliates. All rights reserved. 3216295Ssyrinx * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4216295Ssyrinx * 5216295Ssyrinx * This code is free software; you can redistribute it and/or modify it 6216295Ssyrinx * under the terms of the GNU General Public License version 2 only, as 7216295Ssyrinx * published by the Free Software Foundation. Oracle designates this 8216295Ssyrinx * particular file as subject to the "Classpath" exception as provided 9216295Ssyrinx * by Oracle in the LICENSE file that accompanied this code. 10216295Ssyrinx * 11216295Ssyrinx * This code is distributed in the hope that it will be useful, but WITHOUT 12216295Ssyrinx * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13216295Ssyrinx * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14216295Ssyrinx * version 2 for more details (a copy is included in the LICENSE file that 15216295Ssyrinx * accompanied this code). 16216295Ssyrinx * 17216295Ssyrinx * You should have received a copy of the GNU General Public License version 18216295Ssyrinx * 2 along with this work; if not, write to the Free Software Foundation, 19216295Ssyrinx * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 20216295Ssyrinx * 21216295Ssyrinx * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 22216295Ssyrinx * or visit www.oracle.com if you need additional information or have any 23216295Ssyrinx * questions. 24216295Ssyrinx */ 25216295Ssyrinx 26216295Ssyrinxpackage jdk.nashorn.internal.codegen; 27216295Ssyrinx 28216295Ssyrinximport static jdk.nashorn.internal.codegen.CompilerConstants.RETURN; 29216295Ssyrinximport static jdk.nashorn.internal.ir.Expression.isAlwaysFalse; 30216295Ssyrinximport static jdk.nashorn.internal.ir.Expression.isAlwaysTrue; 31216295Ssyrinx 32216295Ssyrinximport java.util.ArrayDeque; 33216295Ssyrinximport java.util.ArrayList; 34216295Ssyrinximport java.util.Collections; 35216295Ssyrinximport java.util.Deque; 36216295Ssyrinximport java.util.HashSet; 37216295Ssyrinximport java.util.IdentityHashMap; 38216295Ssyrinximport java.util.Iterator; 39216295Ssyrinximport java.util.LinkedList; 40216295Ssyrinximport java.util.List; 41216295Ssyrinximport java.util.Map; 42216295Ssyrinximport java.util.Set; 43216295Ssyrinximport java.util.function.Function; 44216295Ssyrinximport jdk.nashorn.internal.codegen.types.Type; 45216295Ssyrinximport jdk.nashorn.internal.ir.AccessNode; 46216295Ssyrinximport jdk.nashorn.internal.ir.BaseNode; 47216295Ssyrinximport jdk.nashorn.internal.ir.BinaryNode; 48216295Ssyrinximport jdk.nashorn.internal.ir.Block; 49216295Ssyrinximport jdk.nashorn.internal.ir.BreakNode; 50229933Ssyrinximport jdk.nashorn.internal.ir.BreakableNode; 51229933Ssyrinximport jdk.nashorn.internal.ir.CaseNode; 52216295Ssyrinximport jdk.nashorn.internal.ir.CatchNode; 53216295Ssyrinximport jdk.nashorn.internal.ir.ContinueNode; 54216295Ssyrinximport jdk.nashorn.internal.ir.Expression; 55216295Ssyrinximport jdk.nashorn.internal.ir.ForNode; 56216295Ssyrinximport jdk.nashorn.internal.ir.FunctionNode; 57216295Ssyrinximport jdk.nashorn.internal.ir.FunctionNode.CompilationState; 58216295Ssyrinximport jdk.nashorn.internal.ir.IdentNode; 59216295Ssyrinximport jdk.nashorn.internal.ir.IfNode; 60216295Ssyrinximport jdk.nashorn.internal.ir.IndexNode; 61216295Ssyrinximport jdk.nashorn.internal.ir.JoinPredecessor; 62216295Ssyrinximport jdk.nashorn.internal.ir.JoinPredecessorExpression; 63216295Ssyrinximport jdk.nashorn.internal.ir.JumpStatement; 64216295Ssyrinximport jdk.nashorn.internal.ir.LabelNode; 65216295Ssyrinximport jdk.nashorn.internal.ir.LexicalContext; 66216295Ssyrinximport jdk.nashorn.internal.ir.LexicalContextNode; 67216295Ssyrinximport jdk.nashorn.internal.ir.LiteralNode; 68216295Ssyrinximport jdk.nashorn.internal.ir.LocalVariableConversion; 69216295Ssyrinximport jdk.nashorn.internal.ir.LoopNode; 70216295Ssyrinximport jdk.nashorn.internal.ir.Node; 71216295Ssyrinximport jdk.nashorn.internal.ir.PropertyNode; 72216295Ssyrinximport jdk.nashorn.internal.ir.ReturnNode; 73216295Ssyrinximport jdk.nashorn.internal.ir.RuntimeNode; 74216295Ssyrinximport jdk.nashorn.internal.ir.RuntimeNode.Request; 75216295Ssyrinximport jdk.nashorn.internal.ir.SplitReturn; 76216295Ssyrinximport jdk.nashorn.internal.ir.Statement; 77216295Ssyrinximport jdk.nashorn.internal.ir.SwitchNode; 78216295Ssyrinximport jdk.nashorn.internal.ir.Symbol; 79216295Ssyrinximport jdk.nashorn.internal.ir.TernaryNode; 80216295Ssyrinximport jdk.nashorn.internal.ir.ThrowNode; 81216295Ssyrinximport jdk.nashorn.internal.ir.TryNode; 82216295Ssyrinximport jdk.nashorn.internal.ir.UnaryNode; 83216295Ssyrinximport jdk.nashorn.internal.ir.VarNode; 84216295Ssyrinximport jdk.nashorn.internal.ir.WhileNode; 85216295Ssyrinximport jdk.nashorn.internal.ir.visitor.NodeVisitor; 86216295Ssyrinximport jdk.nashorn.internal.parser.TokenType; 87216295Ssyrinx 88216295Ssyrinx/** 89216295Ssyrinx * Calculates types for local variables. For purposes of local variable type calculation, the only types used are 90216295Ssyrinx * Undefined, boolean, int, long, double, and Object. The calculation eagerly widens types of local variable to their 91216295Ssyrinx * widest at control flow join points. 92216295Ssyrinx * TODO: investigate a more sophisticated solution that uses use/def information to only widens the type of a local 93216295Ssyrinx * variable to its widest used type after the join point. That would eliminate some widenings of undefined variables to 94216295Ssyrinx * object, most notably those used only in loops. We need a full liveness analysis for that. Currently, we can establish 95216295Ssyrinx * per-type liveness, which eliminates most of unwanted dead widenings. 96216295Ssyrinx * NOTE: the way this class is implemented, it actually processes the AST in two passes. The first pass is top-down and 97216295Ssyrinx * implemented in {@code enterXxx} methods. This pass does not mutate the AST (except for one occurrence, noted below), 98216295Ssyrinx * as being able to find relevant labels for control flow joins is sensitive to their reference identity, and mutated 99216295Ssyrinx * label-carrying nodes will create copies of their labels. A second bottom-up pass applying the changes is implemented 100216295Ssyrinx * in the separate visitor sitting in {@link #leaveFunctionNode(FunctionNode)}. This visitor will also instantiate new 101216295Ssyrinx * instances of the calculator to be run on nested functions (when not lazy compiling). 102216295Ssyrinx * 103216295Ssyrinx */ 104216295Ssyrinxfinal class LocalVariableTypesCalculator extends NodeVisitor<LexicalContext>{ 105216295Ssyrinx 106216295Ssyrinx private static class JumpOrigin { 107216295Ssyrinx final JoinPredecessor node; 108216295Ssyrinx final Map<Symbol, LvarType> types; 109216295Ssyrinx 110216295Ssyrinx JumpOrigin(final JoinPredecessor node, final Map<Symbol, LvarType> types) { 111216295Ssyrinx this.node = node; 112216295Ssyrinx this.types = types; 113216295Ssyrinx } 114216295Ssyrinx } 115216295Ssyrinx 116216295Ssyrinx private static class JumpTarget { 117216295Ssyrinx private final List<JumpOrigin> origins = new LinkedList<>(); 118216295Ssyrinx private Map<Symbol, LvarType> types = Collections.emptyMap(); 119216295Ssyrinx 120216295Ssyrinx void addOrigin(final JoinPredecessor originNode, final Map<Symbol, LvarType> originTypes) { 121216295Ssyrinx origins.add(new JumpOrigin(originNode, originTypes)); 122216295Ssyrinx this.types = getUnionTypes(this.types, originTypes); 123216295Ssyrinx } 124216295Ssyrinx } 125216295Ssyrinx private enum LvarType { 126216295Ssyrinx UNDEFINED(Type.UNDEFINED), 127216295Ssyrinx BOOLEAN(Type.BOOLEAN), 128216295Ssyrinx INT(Type.INT), 129216295Ssyrinx LONG(Type.LONG), 130216295Ssyrinx DOUBLE(Type.NUMBER), 131216295Ssyrinx OBJECT(Type.OBJECT); 132216295Ssyrinx 133216295Ssyrinx private final Type type; 134216295Ssyrinx private LvarType(final Type type) { 135216295Ssyrinx this.type = type; 136216295Ssyrinx } 137216295Ssyrinx } 138216295Ssyrinx 139216295Ssyrinx private static final Map<Type, LvarType> TO_LVAR_TYPE = new IdentityHashMap<>(); 140216295Ssyrinx 141216295Ssyrinx static { 142216295Ssyrinx for(final LvarType lvarType: LvarType.values()) { 143216295Ssyrinx TO_LVAR_TYPE.put(lvarType.type, lvarType); 144216295Ssyrinx } 145216295Ssyrinx } 146216295Ssyrinx 147216295Ssyrinx @SuppressWarnings("unchecked") 148216295Ssyrinx private static IdentityHashMap<Symbol, LvarType> cloneMap(final Map<Symbol, LvarType> map) { 149216295Ssyrinx return (IdentityHashMap<Symbol, LvarType>)((IdentityHashMap<?,?>)map).clone(); 150216295Ssyrinx } 151216295Ssyrinx 152216295Ssyrinx private LocalVariableConversion createConversion(final Symbol symbol, final LvarType branchLvarType, 153216295Ssyrinx final Map<Symbol, LvarType> joinLvarTypes, final LocalVariableConversion next) { 154216295Ssyrinx final LvarType targetType = joinLvarTypes.get(symbol); 155216295Ssyrinx assert targetType != null; 156216295Ssyrinx if(targetType == branchLvarType) { 157216295Ssyrinx return next; 158216295Ssyrinx } 159216295Ssyrinx // NOTE: we could naively just use symbolIsUsed(symbol, branchLvarType) here, but that'd be wrong. While 160216295Ssyrinx // technically a conversion will read the value of the symbol with that type, but it will also write it to a new 161216295Ssyrinx // type, and that type might be dead (we can't know yet). For this reason, we don't treat conversion reads as 162216295Ssyrinx // real uses until we know their target type is live. If we didn't do this, and just did a symbolIsUsed here, 163216295Ssyrinx // we'd introduce false live variables which could nevertheless turn into dead ones in a subsequent 164216295Ssyrinx // deoptimization, causing a shift in the list of live locals that'd cause erroneous restoration of 165216295Ssyrinx // continuations (since RewriteException's byteCodeSlots carries an array and not a name-value map). 166216295Ssyrinx 167216295Ssyrinx symbolIsConverted(symbol, branchLvarType, targetType); 168216295Ssyrinx //symbolIsUsed(symbol, branchLvarType); 169216295Ssyrinx return new LocalVariableConversion(symbol, branchLvarType.type, targetType.type, next); 170216295Ssyrinx } 171216295Ssyrinx 172216295Ssyrinx private static Map<Symbol, LvarType> getUnionTypes(final Map<Symbol, LvarType> types1, final Map<Symbol, LvarType> types2) { 173216295Ssyrinx if(types1 == types2 || types1.isEmpty()) { 174216295Ssyrinx return types2; 175216295Ssyrinx } else if(types2.isEmpty()) { 176216295Ssyrinx return types1; 177216295Ssyrinx } 178216295Ssyrinx final Set<Symbol> commonSymbols = new HashSet<>(types1.keySet()); 179216295Ssyrinx commonSymbols.retainAll(types2.keySet()); 180216295Ssyrinx // We have a chance of returning an unmodified set if both sets have the same keys and one is strictly wider 181216295Ssyrinx // than the other. 182216295Ssyrinx final int commonSize = commonSymbols.size(); 183216295Ssyrinx final int types1Size = types1.size(); 184216295Ssyrinx final int types2Size = types2.size(); 185216295Ssyrinx if(commonSize == types1Size && commonSize == types2Size) { 186216295Ssyrinx boolean matches1 = true, matches2 = true; 187216295Ssyrinx Map<Symbol, LvarType> union = null; 188216295Ssyrinx for(final Symbol symbol: commonSymbols) { 189216295Ssyrinx final LvarType type1 = types1.get(symbol); 190228990Suqs final LvarType type2 = types2.get(symbol); 191216295Ssyrinx final LvarType widest = widestLvarType(type1, type2); 192216295Ssyrinx if(widest != type1 && matches1) { 193216295Ssyrinx matches1 = false; 194216295Ssyrinx if(!matches2) { 195228990Suqs union = cloneMap(types1); 196216295Ssyrinx } 197228990Suqs } 198216295Ssyrinx if (widest != type2 && matches2) { 199216295Ssyrinx matches2 = false; 200216295Ssyrinx if(!matches1) { 201216295Ssyrinx union = cloneMap(types2); 202216295Ssyrinx } 203216295Ssyrinx } 204216295Ssyrinx if(!(matches1 || matches2) && union != null) { //remove overly enthusiastic "union can be null" warning 205216295Ssyrinx assert union != null; 206216295Ssyrinx union.put(symbol, widest); 207216295Ssyrinx } 208216295Ssyrinx } 209216295Ssyrinx return matches1 ? types1 : matches2 ? types2 : union; 210216295Ssyrinx } 211216295Ssyrinx // General case 212216295Ssyrinx final Map<Symbol, LvarType> union; 213216295Ssyrinx if(types1Size > types2Size) { 214216295Ssyrinx union = cloneMap(types1); 215216295Ssyrinx union.putAll(types2); 216216295Ssyrinx } else { 217216295Ssyrinx union = cloneMap(types2); 218216295Ssyrinx union.putAll(types1); 219216295Ssyrinx } 220216295Ssyrinx for(final Symbol symbol: commonSymbols) { 221216295Ssyrinx final LvarType type1 = types1.get(symbol); 222216295Ssyrinx final LvarType type2 = types2.get(symbol); 223216295Ssyrinx union.put(symbol, widestLvarType(type1, type2)); 224216295Ssyrinx } 225216295Ssyrinx return union; 226216295Ssyrinx } 227216295Ssyrinx 228216295Ssyrinx private static void symbolIsUsed(final Symbol symbol, final LvarType type) { 229216295Ssyrinx if(type != LvarType.UNDEFINED) { 230216295Ssyrinx symbol.setHasSlotFor(type.type); 231216295Ssyrinx } 232216295Ssyrinx } 233216295Ssyrinx 234216295Ssyrinx private static class SymbolConversions { 235216295Ssyrinx private static byte I2L = 1 << 0; 236216295Ssyrinx private static byte I2D = 1 << 1; 237216295Ssyrinx private static byte I2O = 1 << 2; 238216295Ssyrinx private static byte L2D = 1 << 3; 239216295Ssyrinx private static byte L2O = 1 << 4; 240216295Ssyrinx private static byte D2O = 1 << 5; 241216295Ssyrinx 242216295Ssyrinx private byte conversions; 243216295Ssyrinx 244216295Ssyrinx void recordConversion(final LvarType from, final LvarType to) { 245216295Ssyrinx switch (from) { 246216295Ssyrinx case UNDEFINED: 247216295Ssyrinx return; 248216295Ssyrinx case INT: 249216295Ssyrinx case BOOLEAN: 250216295Ssyrinx switch (to) { 251216295Ssyrinx case LONG: 252216295Ssyrinx recordConversion(I2L); 253216295Ssyrinx return; 254216295Ssyrinx case DOUBLE: 255216295Ssyrinx recordConversion(I2D); 256216295Ssyrinx return; 257216295Ssyrinx case OBJECT: 258216295Ssyrinx recordConversion(I2O); 259216295Ssyrinx return; 260216295Ssyrinx default: 261216295Ssyrinx illegalConversion(from, to); 262216295Ssyrinx return; 263216295Ssyrinx } 264216295Ssyrinx case LONG: 265216295Ssyrinx switch (to) { 266216295Ssyrinx case DOUBLE: 267216295Ssyrinx recordConversion(L2D); 268216295Ssyrinx return; 269216295Ssyrinx case OBJECT: 270216295Ssyrinx recordConversion(L2O); 271216295Ssyrinx return; 272216295Ssyrinx default: 273216295Ssyrinx illegalConversion(from, to); 274216295Ssyrinx return; 275216295Ssyrinx } 276216295Ssyrinx case DOUBLE: 277216295Ssyrinx if(to == LvarType.OBJECT) { 278216295Ssyrinx recordConversion(D2O); 279216295Ssyrinx } 280216295Ssyrinx return; 281216295Ssyrinx default: 282216295Ssyrinx illegalConversion(from, to); 283216295Ssyrinx } 284216295Ssyrinx } 285216295Ssyrinx 286216295Ssyrinx private static void illegalConversion(final LvarType from, final LvarType to) { 287216295Ssyrinx throw new AssertionError("Invalid conversion from " + from + " to " + to); 288216295Ssyrinx } 289216295Ssyrinx 290216295Ssyrinx void recordConversion(final byte convFlag) { 291216295Ssyrinx conversions = (byte)(conversions | convFlag); 292216295Ssyrinx } 293216295Ssyrinx 294216295Ssyrinx boolean hasConversion(final byte convFlag) { 295216295Ssyrinx return (conversions & convFlag) != 0; 296216295Ssyrinx } 297216295Ssyrinx 298216295Ssyrinx void calculateTypeLiveness(final Symbol symbol) { 299216295Ssyrinx if(symbol.hasSlotFor(Type.OBJECT)) { 300216295Ssyrinx if(hasConversion(D2O)) { 301216295Ssyrinx symbol.setHasSlotFor(Type.NUMBER); 302216295Ssyrinx } 303216295Ssyrinx if(hasConversion(L2O)) { 304216295Ssyrinx symbol.setHasSlotFor(Type.LONG); 305216295Ssyrinx } 306216295Ssyrinx if(hasConversion(I2O)) { 307216295Ssyrinx symbol.setHasSlotFor(Type.INT); 308216295Ssyrinx } 309216295Ssyrinx } 310216295Ssyrinx if(symbol.hasSlotFor(Type.NUMBER)) { 311216295Ssyrinx if(hasConversion(L2D)) { 312216295Ssyrinx symbol.setHasSlotFor(Type.LONG); 313216295Ssyrinx } 314216295Ssyrinx if(hasConversion(I2D)) { 315216295Ssyrinx symbol.setHasSlotFor(Type.INT); 316216295Ssyrinx } 317216295Ssyrinx } 318216295Ssyrinx if(symbol.hasSlotFor(Type.LONG)) { 319216295Ssyrinx if(hasConversion(I2L)) { 320216295Ssyrinx symbol.setHasSlotFor(Type.INT); 321216295Ssyrinx } 322216295Ssyrinx } 323216295Ssyrinx } 324216295Ssyrinx } 325216295Ssyrinx 326216295Ssyrinx private void symbolIsConverted(final Symbol symbol, final LvarType from, final LvarType to) { 327216295Ssyrinx SymbolConversions conversions = symbolConversions.get(symbol); 328229933Ssyrinx if(conversions == null) { 329216295Ssyrinx conversions = new SymbolConversions(); 330216295Ssyrinx symbolConversions.put(symbol, conversions); 331216295Ssyrinx } 332216295Ssyrinx conversions.recordConversion(from, to); 333216295Ssyrinx } 334 335 private static LvarType toLvarType(final Type type) { 336 assert type != null; 337 final LvarType lvarType = TO_LVAR_TYPE.get(type); 338 if(lvarType != null) { 339 return lvarType; 340 } 341 assert type.isObject(); 342 return LvarType.OBJECT; 343 } 344 private static LvarType widestLvarType(final LvarType t1, final LvarType t2) { 345 if(t1 == t2) { 346 return t1; 347 } 348 // Undefined or boolean to anything always widens to object. 349 if(t1.ordinal() < LvarType.INT.ordinal() || t2.ordinal() < LvarType.INT.ordinal()) { 350 return LvarType.OBJECT; 351 } 352 // NOTE: we allow "widening" of long to double even though it can lose precision. ECMAScript doesn't have an 353 // Int64 type anyway, so this loss of precision is actually more conformant to the specification... 354 return LvarType.values()[Math.max(t1.ordinal(), t2.ordinal())]; 355 } 356 private final Compiler compiler; 357 private final Map<Label, JumpTarget> jumpTargets = new IdentityHashMap<>(); 358 // Local variable type mapping at the currently evaluated point. No map instance is ever modified; setLvarType() always 359 // allocates a new map. Immutability of maps allows for cheap snapshots by just keeping the reference to the current 360 // value. 361 private Map<Symbol, LvarType> localVariableTypes = new IdentityHashMap<>(); 362 363 // Whether the current point in the AST is reachable code 364 private boolean reachable = true; 365 // Return type of the function 366 private Type returnType = Type.UNKNOWN; 367 // Synthetic return node that we must insert at the end of the function if it's end is reachable. 368 private ReturnNode syntheticReturn; 369 370 private boolean alreadyEnteredTopLevelFunction; 371 372 // LvarType and conversion information gathered during the top-down pass; applied to nodes in the bottom-up pass. 373 private final Map<JoinPredecessor, LocalVariableConversion> localVariableConversions = new IdentityHashMap<>(); 374 375 private final Map<IdentNode, LvarType> identifierLvarTypes = new IdentityHashMap<>(); 376 private final Map<Symbol, SymbolConversions> symbolConversions = new IdentityHashMap<>(); 377 378 private SymbolToType symbolToType = new SymbolToType(); 379 380 // Stack of open labels for starts of catch blocks, one for every currently traversed try block; for inserting 381 // control flow edges to them. Note that we currently don't insert actual control flow edges, but instead edges that 382 // help us with type calculations. This means that some operations that can result in an exception being thrown 383 // aren't considered (function calls, side effecting property getters and setters etc.), while some operations that 384 // don't result in control flow transfers do originate an edge to the catch blocks (namely, assignments to local 385 // variables). 386 private final Deque<Label> catchLabels = new ArrayDeque<>(); 387 388 LocalVariableTypesCalculator(final Compiler compiler) { 389 super(new LexicalContext()); 390 this.compiler = compiler; 391 } 392 393 private JumpTarget createJumpTarget(final Label label) { 394 assert !jumpTargets.containsKey(label); 395 final JumpTarget jumpTarget = new JumpTarget(); 396 jumpTargets.put(label, jumpTarget); 397 return jumpTarget; 398 } 399 400 private void doesNotContinueSequentially() { 401 reachable = false; 402 localVariableTypes = Collections.emptyMap(); 403 } 404 405 406 @Override 407 public boolean enterBinaryNode(final BinaryNode binaryNode) { 408 // NOTE: regardless of operator's lexical associativity, lhs is always evaluated first. 409 final Expression lhs = binaryNode.lhs(); 410 final boolean isAssignment = binaryNode.isAssignment(); 411 LvarType lhsTypeOnLoad = null; 412 if(isAssignment) { 413 if(lhs instanceof BaseNode) { 414 ((BaseNode)lhs).getBase().accept(this); 415 if(lhs instanceof IndexNode) { 416 ((IndexNode)lhs).getIndex().accept(this); 417 } else { 418 assert lhs instanceof AccessNode; 419 } 420 } else { 421 assert lhs instanceof IdentNode; 422 if(binaryNode.isSelfModifying()) { 423 final IdentNode ident = ((IdentNode)lhs); 424 ident.accept(this); 425 // Self-assignment can cause a change in the type of the variable. For purposes of evaluating 426 // the type of the operation, we must use its type as it was when it was loaded. If we didn't 427 // do this, some awkward expressions would end up being calculated incorrectly, e.g. 428 // "var x; x += x = 0;". In this case we have undefined+int so the result type is double (NaN). 429 // However, if we used the type of "x" on LHS after we evaluated RHS, we'd see int+int, so the 430 // result type would be either optimistic int or pessimistic long, which would be wrong. 431 lhsTypeOnLoad = getLocalVariableTypeIfBytecode(ident.getSymbol()); 432 } 433 } 434 } else { 435 lhs.accept(this); 436 } 437 438 final boolean isLogical = binaryNode.isLogical(); 439 assert !(isAssignment && isLogical); // there are no logical assignment operators in JS 440 final Label joinLabel = isLogical ? new Label("") : null; 441 if(isLogical) { 442 jumpToLabel((JoinPredecessor)lhs, joinLabel); 443 } 444 445 final Expression rhs = binaryNode.rhs(); 446 rhs.accept(this); 447 if(isLogical) { 448 jumpToLabel((JoinPredecessor)rhs, joinLabel); 449 } 450 joinOnLabel(joinLabel); 451 452 if(isAssignment && lhs instanceof IdentNode) { 453 if(binaryNode.isSelfModifying()) { 454 onSelfAssignment((IdentNode)lhs, binaryNode, lhsTypeOnLoad); 455 } else { 456 onAssignment((IdentNode)lhs, rhs); 457 } 458 } 459 return false; 460 } 461 462 @Override 463 public boolean enterBlock(final Block block) { 464 for(final Symbol symbol: block.getSymbols()) { 465 if(symbol.isBytecodeLocal() && getLocalVariableTypeOrNull(symbol) == null) { 466 setType(symbol, LvarType.UNDEFINED); 467 } 468 } 469 return true; 470 } 471 472 @Override 473 public boolean enterBreakNode(final BreakNode breakNode) { 474 return enterJumpStatement(breakNode); 475 } 476 477 @Override 478 public boolean enterContinueNode(final ContinueNode continueNode) { 479 return enterJumpStatement(continueNode); 480 } 481 482 private boolean enterJumpStatement(final JumpStatement jump) { 483 if(!reachable) { 484 return false; 485 } 486 final BreakableNode target = jump.getTarget(lc); 487 jumpToLabel(jump, jump.getTargetLabel(target), getBreakTargetTypes(target)); 488 doesNotContinueSequentially(); 489 return false; 490 } 491 492 @Override 493 protected boolean enterDefault(final Node node) { 494 return reachable; 495 } 496 497 private void enterDoWhileLoop(final WhileNode loopNode) { 498 final JoinPredecessorExpression test = loopNode.getTest(); 499 final Block body = loopNode.getBody(); 500 final Label continueLabel = loopNode.getContinueLabel(); 501 final Label breakLabel = loopNode.getBreakLabel(); 502 final Map<Symbol, LvarType> beforeLoopTypes = localVariableTypes; 503 final Label repeatLabel = new Label(""); 504 for(;;) { 505 jumpToLabel(loopNode, repeatLabel, beforeLoopTypes); 506 final Map<Symbol, LvarType> beforeRepeatTypes = localVariableTypes; 507 body.accept(this); 508 if(reachable) { 509 jumpToLabel(body, continueLabel); 510 } 511 joinOnLabel(continueLabel); 512 if(!reachable) { 513 break; 514 } 515 test.accept(this); 516 jumpToLabel(test, breakLabel); 517 if(isAlwaysFalse(test)) { 518 break; 519 } 520 jumpToLabel(test, repeatLabel); 521 joinOnLabel(repeatLabel); 522 if(localVariableTypes.equals(beforeRepeatTypes)) { 523 break; 524 } 525 resetJoinPoint(continueLabel); 526 resetJoinPoint(breakLabel); 527 resetJoinPoint(repeatLabel); 528 } 529 530 if(isAlwaysTrue(test)) { 531 doesNotContinueSequentially(); 532 } 533 534 leaveBreakable(loopNode); 535 } 536 537 @Override 538 public boolean enterForNode(final ForNode forNode) { 539 if(!reachable) { 540 return false; 541 } 542 543 final Expression init = forNode.getInit(); 544 if(forNode.isForIn()) { 545 final JoinPredecessorExpression iterable = forNode.getModify(); 546 iterable.accept(this); 547 enterTestFirstLoop(forNode, null, init, 548 // If we're iterating over property names, and we can discern from the runtime environment 549 // of the compilation that the object being iterated over must use strings for property 550 // names (e.g., it is a native JS object or array), then we'll not bother trying to treat 551 // the property names optimistically. 552 !compiler.useOptimisticTypes() || (!forNode.isForEach() && compiler.hasStringPropertyIterator(iterable.getExpression()))); 553 } else { 554 if(init != null) { 555 init.accept(this); 556 } 557 enterTestFirstLoop(forNode, forNode.getModify(), null, false); 558 } 559 return false; 560 } 561 562 @Override 563 public boolean enterFunctionNode(final FunctionNode functionNode) { 564 if(alreadyEnteredTopLevelFunction) { 565 return false; 566 } 567 int pos = 0; 568 if(!functionNode.isVarArg()) { 569 for (final IdentNode param : functionNode.getParameters()) { 570 final Symbol symbol = param.getSymbol(); 571 // Parameter is not necessarily bytecode local as it can be scoped due to nested context use, but it 572 // must have a slot if we aren't in a function with vararg signature. 573 assert symbol.hasSlot(); 574 final Type callSiteParamType = compiler.getParamType(functionNode, pos); 575 final LvarType paramType = callSiteParamType == null ? LvarType.OBJECT : toLvarType(callSiteParamType); 576 setType(symbol, paramType); 577 // Make sure parameter slot for its incoming value is not marked dead. NOTE: this is a heuristic. Right 578 // now, CodeGenerator.expandParameters() relies on the fact that every parameter's final slot width will 579 // be at least the same as incoming width, therefore even if a parameter is never read, we'll still keep 580 // its slot. 581 symbolIsUsed(symbol); 582 setIdentifierLvarType(param, paramType); 583 pos++; 584 } 585 } 586 setCompilerConstantAsObject(functionNode, CompilerConstants.THIS); 587 588 // TODO: coarse-grained. If we wanted to solve it completely precisely, 589 // we'd also need to push/pop its type when handling WithNode (so that 590 // it can go back to undefined after a 'with' block. 591 if(functionNode.hasScopeBlock() || functionNode.needsParentScope()) { 592 setCompilerConstantAsObject(functionNode, CompilerConstants.SCOPE); 593 } 594 if(functionNode.needsCallee()) { 595 setCompilerConstantAsObject(functionNode, CompilerConstants.CALLEE); 596 } 597 if(functionNode.needsArguments()) { 598 setCompilerConstantAsObject(functionNode, CompilerConstants.ARGUMENTS); 599 } 600 601 alreadyEnteredTopLevelFunction = true; 602 return true; 603 } 604 605 @Override 606 public boolean enterIdentNode(final IdentNode identNode) { 607 final Symbol symbol = identNode.getSymbol(); 608 if(symbol.isBytecodeLocal()) { 609 symbolIsUsed(symbol); 610 setIdentifierLvarType(identNode, getLocalVariableType(symbol)); 611 } 612 return false; 613 } 614 615 @Override 616 public boolean enterIfNode(final IfNode ifNode) { 617 if(!reachable) { 618 return false; 619 } 620 621 final Expression test = ifNode.getTest(); 622 final Block pass = ifNode.getPass(); 623 final Block fail = ifNode.getFail(); 624 625 test.accept(this); 626 627 final Map<Symbol, LvarType> afterTestLvarTypes = localVariableTypes; 628 if(!isAlwaysFalse(test)) { 629 pass.accept(this); 630 } 631 final Map<Symbol, LvarType> passLvarTypes = localVariableTypes; 632 final boolean reachableFromPass = reachable; 633 634 reachable = true; 635 localVariableTypes = afterTestLvarTypes; 636 if(!isAlwaysTrue(test) && fail != null) { 637 fail.accept(this); 638 final boolean reachableFromFail = reachable; 639 reachable |= reachableFromPass; 640 if(!reachable) { 641 return false; 642 } 643 644 if(reachableFromFail) { 645 if(reachableFromPass) { 646 final Map<Symbol, LvarType> failLvarTypes = localVariableTypes; 647 localVariableTypes = getUnionTypes(passLvarTypes, failLvarTypes); 648 setConversion(pass, passLvarTypes, localVariableTypes); 649 setConversion(fail, failLvarTypes, localVariableTypes); 650 } 651 return false; 652 } 653 } 654 655 if(reachableFromPass) { 656 localVariableTypes = getUnionTypes(afterTestLvarTypes, passLvarTypes); 657 // IfNode itself is associated with conversions that might need to be performed after the test if there's no 658 // else branch. E.g. 659 // if(x = 1, cond) { x = 1.0 } must widen "x = 1" to a double. 660 setConversion(pass, passLvarTypes, localVariableTypes); 661 setConversion(ifNode, afterTestLvarTypes, localVariableTypes); 662 } else { 663 localVariableTypes = afterTestLvarTypes; 664 } 665 666 return false; 667 } 668 669 @Override 670 public boolean enterPropertyNode(final PropertyNode propertyNode) { 671 // Avoid falsely adding property keys to the control flow graph 672 if(propertyNode.getValue() != null) { 673 propertyNode.getValue().accept(this); 674 } 675 return false; 676 } 677 678 @Override 679 public boolean enterReturnNode(final ReturnNode returnNode) { 680 if(!reachable) { 681 return false; 682 } 683 684 final Expression returnExpr = returnNode.getExpression(); 685 final Type returnExprType; 686 if(returnExpr != null) { 687 returnExpr.accept(this); 688 returnExprType = getType(returnExpr); 689 } else { 690 returnExprType = Type.UNDEFINED; 691 } 692 returnType = Type.widestReturnType(returnType, returnExprType); 693 doesNotContinueSequentially(); 694 return false; 695 } 696 697 @Override 698 public boolean enterSplitReturn(final SplitReturn splitReturn) { 699 doesNotContinueSequentially(); 700 return false; 701 } 702 703 @Override 704 public boolean enterSwitchNode(final SwitchNode switchNode) { 705 if(!reachable) { 706 return false; 707 } 708 709 final Expression expr = switchNode.getExpression(); 710 expr.accept(this); 711 712 final List<CaseNode> cases = switchNode.getCases(); 713 if(cases.isEmpty()) { 714 return false; 715 } 716 717 // Control flow is different for all-integer cases where we dispatch by switch table, and for all other cases 718 // where we do sequential comparison. Note that CaseNode objects act as join points. 719 final boolean isInteger = switchNode.isUniqueInteger(); 720 final Label breakLabel = switchNode.getBreakLabel(); 721 final boolean hasDefault = switchNode.getDefaultCase() != null; 722 723 boolean tagUsed = false; 724 for(final CaseNode caseNode: cases) { 725 final Expression test = caseNode.getTest(); 726 if(!isInteger && test != null) { 727 test.accept(this); 728 if(!tagUsed) { 729 symbolIsUsed(switchNode.getTag(), LvarType.OBJECT); 730 tagUsed = true; 731 } 732 } 733 // CaseNode carries the conversions that need to be performed on its entry from the test. 734 // CodeGenerator ensures these are only emitted when arriving on the branch and not through a 735 // fallthrough. 736 jumpToLabel(caseNode, caseNode.getBody().getEntryLabel()); 737 } 738 if(!hasDefault) { 739 // No default case means we can arrive at the break label without entering any cases. In that case 740 // SwitchNode will carry the conversions that need to be performed before it does that jump. 741 jumpToLabel(switchNode, breakLabel); 742 } 743 744 // All cases are arrived at through jumps 745 doesNotContinueSequentially(); 746 747 Block previousBlock = null; 748 for(final CaseNode caseNode: cases) { 749 final Block body = caseNode.getBody(); 750 final Label entryLabel = body.getEntryLabel(); 751 if(previousBlock != null && reachable) { 752 jumpToLabel(previousBlock, entryLabel); 753 } 754 joinOnLabel(entryLabel); 755 assert reachable == true; 756 body.accept(this); 757 previousBlock = body; 758 } 759 if(previousBlock != null && reachable) { 760 jumpToLabel(previousBlock, breakLabel); 761 } 762 leaveBreakable(switchNode); 763 return false; 764 } 765 766 @Override 767 public boolean enterTernaryNode(final TernaryNode ternaryNode) { 768 final Expression test = ternaryNode.getTest(); 769 final Expression trueExpr = ternaryNode.getTrueExpression(); 770 final Expression falseExpr = ternaryNode.getFalseExpression(); 771 772 test.accept(this); 773 774 final Map<Symbol, LvarType> testExitLvarTypes = localVariableTypes; 775 if(!isAlwaysFalse(test)) { 776 trueExpr.accept(this); 777 } 778 final Map<Symbol, LvarType> trueExitLvarTypes = localVariableTypes; 779 localVariableTypes = testExitLvarTypes; 780 if(!isAlwaysTrue(test)) { 781 falseExpr.accept(this); 782 } 783 final Map<Symbol, LvarType> falseExitLvarTypes = localVariableTypes; 784 localVariableTypes = getUnionTypes(trueExitLvarTypes, falseExitLvarTypes); 785 setConversion((JoinPredecessor)trueExpr, trueExitLvarTypes, localVariableTypes); 786 setConversion((JoinPredecessor)falseExpr, falseExitLvarTypes, localVariableTypes); 787 return false; 788 } 789 790 private void enterTestFirstLoop(final LoopNode loopNode, final JoinPredecessorExpression modify, 791 final Expression iteratorValues, final boolean iteratorValuesAreObject) { 792 final JoinPredecessorExpression test = loopNode.getTest(); 793 if(isAlwaysFalse(test)) { 794 test.accept(this); 795 return; 796 } 797 798 final Label continueLabel = loopNode.getContinueLabel(); 799 final Label breakLabel = loopNode.getBreakLabel(); 800 801 final Label repeatLabel = modify == null ? continueLabel : new Label(""); 802 final Map<Symbol, LvarType> beforeLoopTypes = localVariableTypes; 803 for(;;) { 804 jumpToLabel(loopNode, repeatLabel, beforeLoopTypes); 805 final Map<Symbol, LvarType> beforeRepeatTypes = localVariableTypes; 806 if(test != null) { 807 test.accept(this); 808 } 809 if(!isAlwaysTrue(test)) { 810 jumpToLabel(test, breakLabel); 811 } 812 if(iteratorValues instanceof IdentNode) { 813 final IdentNode ident = (IdentNode)iteratorValues; 814 // Receives iterator values; the optimistic type of the iterator values is tracked on the 815 // identifier, but we override optimism if it's known that the object being iterated over will 816 // never have primitive property names. 817 onAssignment(ident, iteratorValuesAreObject ? LvarType.OBJECT : 818 toLvarType(compiler.getOptimisticType(ident))); 819 } 820 final Block body = loopNode.getBody(); 821 body.accept(this); 822 if(reachable) { 823 jumpToLabel(body, continueLabel); 824 } 825 joinOnLabel(continueLabel); 826 if(!reachable) { 827 break; 828 } 829 if(modify != null) { 830 modify.accept(this); 831 jumpToLabel(modify, repeatLabel); 832 joinOnLabel(repeatLabel); 833 } 834 if(localVariableTypes.equals(beforeRepeatTypes)) { 835 break; 836 } 837 // Reset the join points and repeat the analysis 838 resetJoinPoint(continueLabel); 839 resetJoinPoint(breakLabel); 840 resetJoinPoint(repeatLabel); 841 } 842 843 if(isAlwaysTrue(test) && iteratorValues == null) { 844 doesNotContinueSequentially(); 845 } 846 847 leaveBreakable(loopNode); 848 } 849 850 @Override 851 public boolean enterThrowNode(final ThrowNode throwNode) { 852 if(!reachable) { 853 return false; 854 } 855 856 throwNode.getExpression().accept(this); 857 jumpToCatchBlock(throwNode); 858 doesNotContinueSequentially(); 859 return false; 860 } 861 862 @Override 863 public boolean enterTryNode(final TryNode tryNode) { 864 if(!reachable) { 865 return false; 866 } 867 868 // This is the label for the join point at the entry of the catch blocks. 869 final Label catchLabel = new Label(""); 870 catchLabels.push(catchLabel); 871 872 // Presume that even the start of the try block can immediately go to the catch 873 jumpToLabel(tryNode, catchLabel); 874 875 final Block body = tryNode.getBody(); 876 body.accept(this); 877 catchLabels.pop(); 878 879 // Final exit label for the whole try/catch construct (after the try block and after all catches). 880 final Label endLabel = new Label(""); 881 882 boolean canExit = false; 883 if(reachable) { 884 jumpToLabel(body, endLabel); 885 canExit = true; 886 } 887 doesNotContinueSequentially(); 888 889 joinOnLabel(catchLabel); 890 for(final CatchNode catchNode: tryNode.getCatches()) { 891 final IdentNode exception = catchNode.getException(); 892 onAssignment(exception, LvarType.OBJECT); 893 final Expression condition = catchNode.getExceptionCondition(); 894 if(condition != null) { 895 condition.accept(this); 896 } 897 final Map<Symbol, LvarType> afterConditionTypes = localVariableTypes; 898 final Block catchBody = catchNode.getBody(); 899 // TODO: currently, we consider that the catch blocks are always reachable from the try block as currently 900 // we lack enough analysis to prove that no statement before a break/continue/return in the try block can 901 // throw an exception. 902 reachable = true; 903 catchBody.accept(this); 904 final Symbol exceptionSymbol = exception.getSymbol(); 905 if(reachable) { 906 localVariableTypes = cloneMap(localVariableTypes); 907 localVariableTypes.remove(exceptionSymbol); 908 jumpToLabel(catchBody, endLabel); 909 canExit = true; 910 } 911 localVariableTypes = cloneMap(afterConditionTypes); 912 localVariableTypes.remove(exceptionSymbol); 913 } 914 // NOTE: if we had one or more conditional catch blocks with no unconditional catch block following them, then 915 // there will be an unconditional rethrow, so the join point can never be reached from the last 916 // conditionExpression. 917 doesNotContinueSequentially(); 918 919 if(canExit) { 920 joinOnLabel(endLabel); 921 } 922 923 return false; 924 } 925 926 927 @Override 928 public boolean enterUnaryNode(final UnaryNode unaryNode) { 929 final Expression expr = unaryNode.getExpression(); 930 expr.accept(this); 931 932 if(unaryNode.isSelfModifying()) { 933 if(expr instanceof IdentNode) { 934 final IdentNode ident = (IdentNode)expr; 935 onSelfAssignment(ident, unaryNode, getLocalVariableTypeIfBytecode(ident.getSymbol())); 936 } 937 } 938 return false; 939 } 940 941 @Override 942 public boolean enterVarNode(final VarNode varNode) { 943 if (!reachable) { 944 return false; 945 } 946 final Expression init = varNode.getInit(); 947 if(init != null) { 948 init.accept(this); 949 onAssignment(varNode.getName(), init); 950 } 951 return false; 952 } 953 954 @Override 955 public boolean enterWhileNode(final WhileNode whileNode) { 956 if(!reachable) { 957 return false; 958 } 959 if(whileNode.isDoWhile()) { 960 enterDoWhileLoop(whileNode); 961 } else { 962 enterTestFirstLoop(whileNode, null, null, false); 963 } 964 return false; 965 } 966 967 private Map<Symbol, LvarType> getBreakTargetTypes(final BreakableNode target) { 968 // Remove symbols defined in the the blocks that are being broken out of. 969 Map<Symbol, LvarType> types = localVariableTypes; 970 for(final Iterator<LexicalContextNode> it = lc.getAllNodes(); it.hasNext();) { 971 final LexicalContextNode node = it.next(); 972 if(node instanceof Block) { 973 for(final Symbol symbol: ((Block)node).getSymbols()) { 974 if(localVariableTypes.containsKey(symbol)) { 975 if(types == localVariableTypes) { 976 types = cloneMap(localVariableTypes); 977 } 978 types.remove(symbol); 979 } 980 } 981 } 982 if(node == target) { 983 break; 984 } 985 } 986 return types; 987 } 988 989 /** 990 * Returns the current type of the local variable represented by the symbol. This is the most strict of all 991 * {@code getLocalVariableType*} methods, as it will throw an assertion if the type is null. Therefore, it is only 992 * safe to be invoked on symbols known to be bytecode locals, and only after they have been initialized. 993 * Regardless, it is recommended to use this method in majority of cases, as because of its strictness it is the 994 * best suited for catching missing type calculation bugs early. 995 * @param symbol a symbol representing a bytecode local variable. 996 * @return the current type of the local variable represented by the symbol 997 */ 998 private LvarType getLocalVariableType(final Symbol symbol) { 999 final LvarType type = getLocalVariableTypeOrNull(symbol); 1000 assert type != null; 1001 return type; 1002 } 1003 1004 /** 1005 * Gets the type for a local variable if it is a bytecode local, otherwise null. Can be used in circumstances where 1006 * the type is irrelevant if the symbol is not a bytecode local. Note that for bytecode locals, it delegates to 1007 * {@link #getLocalVariableType(Symbol)}, so it will still assert that the type for such variable is already 1008 * defined (that is, not null). 1009 * @param symbol the symbol representing the variable. 1010 * @return the current variable type, if it is a bytecode local, otherwise null. 1011 */ 1012 private LvarType getLocalVariableTypeIfBytecode(final Symbol symbol) { 1013 return symbol.isBytecodeLocal() ? getLocalVariableType(symbol) : null; 1014 } 1015 1016 /** 1017 * Gets the type for a variable represented by a symbol, or null if the type is not know. This is the least strict 1018 * of all local variable type getters, and as such its use is discouraged except in initialization scenarios (where 1019 * a just-defined symbol might still be null). 1020 * @param symbol the symbol 1021 * @return the current type for the symbol, or null if the type is not known either because the symbol has not been 1022 * initialized, or because the symbol does not represent a bytecode local variable. 1023 */ 1024 private LvarType getLocalVariableTypeOrNull(final Symbol symbol) { 1025 return localVariableTypes.get(symbol); 1026 } 1027 1028 private JumpTarget getOrCreateJumpTarget(final Label label) { 1029 JumpTarget jumpTarget = jumpTargets.get(label); 1030 if(jumpTarget == null) { 1031 jumpTarget = createJumpTarget(label); 1032 } 1033 return jumpTarget; 1034 } 1035 1036 1037 /** 1038 * If there's a join point associated with a label, insert the join point into the flow. 1039 * @param label the label to insert a join point for. 1040 */ 1041 private void joinOnLabel(final Label label) { 1042 final JumpTarget jumpTarget = jumpTargets.remove(label); 1043 if(jumpTarget == null) { 1044 return; 1045 } 1046 assert !jumpTarget.origins.isEmpty(); 1047 reachable = true; 1048 localVariableTypes = getUnionTypes(jumpTarget.types, localVariableTypes); 1049 for(final JumpOrigin jumpOrigin: jumpTarget.origins) { 1050 setConversion(jumpOrigin.node, jumpOrigin.types, localVariableTypes); 1051 } 1052 } 1053 1054 /** 1055 * If we're in a try/catch block, add an edge from the specified node to the try node's pre-catch label. 1056 */ 1057 private void jumpToCatchBlock(final JoinPredecessor jumpOrigin) { 1058 final Label currentCatchLabel = catchLabels.peek(); 1059 if(currentCatchLabel != null) { 1060 jumpToLabel(jumpOrigin, currentCatchLabel); 1061 } 1062 } 1063 1064 private void jumpToLabel(final JoinPredecessor jumpOrigin, final Label label) { 1065 jumpToLabel(jumpOrigin, label, localVariableTypes); 1066 } 1067 1068 private void jumpToLabel(final JoinPredecessor jumpOrigin, final Label label, final Map<Symbol, LvarType> types) { 1069 getOrCreateJumpTarget(label).addOrigin(jumpOrigin, types); 1070 } 1071 1072 @Override 1073 public Node leaveBlock(final Block block) { 1074 if(lc.isFunctionBody()) { 1075 if(reachable) { 1076 // reachable==true means we can reach the end of the function without an explicit return statement. We 1077 // need to insert a synthetic one then. This logic used to be in Lower.leaveBlock(), but Lower's 1078 // reachability analysis (through Terminal.isTerminal() flags) is not precise enough so 1079 // Lower$BlockLexicalContext.afterSetStatements will sometimes think the control flow terminates even 1080 // when it didn't. Example: function() { switch((z)) { default: {break; } throw x; } }. 1081 createSyntheticReturn(block); 1082 assert !reachable; 1083 } 1084 // We must calculate the return type here (and not in leaveFunctionNode) as it can affect the liveness of 1085 // the :return symbol and thus affect conversion type liveness calculations for it. 1086 calculateReturnType(); 1087 } 1088 1089 boolean cloned = false; 1090 for(final Symbol symbol: block.getSymbols()) { 1091 // Undefine the symbol outside the block 1092 if(localVariableTypes.containsKey(symbol)) { 1093 if(!cloned) { 1094 localVariableTypes = cloneMap(localVariableTypes); 1095 cloned = true; 1096 } 1097 localVariableTypes.remove(symbol); 1098 } 1099 1100 if(symbol.hasSlot()) { 1101 final SymbolConversions conversions = symbolConversions.get(symbol); 1102 if(conversions != null) { 1103 // Potentially make some currently dead types live if they're needed as a source of a type 1104 // conversion at a join. 1105 conversions.calculateTypeLiveness(symbol); 1106 } 1107 if(symbol.slotCount() == 0) { 1108 // This is a local variable that is never read. It won't need a slot. 1109 symbol.setNeedsSlot(false); 1110 } 1111 } 1112 } 1113 1114 if(reachable) { 1115 // TODO: this is totally backwards. Block should not be breakable, LabelNode should be breakable. 1116 final LabelNode labelNode = lc.getCurrentBlockLabelNode(); 1117 if(labelNode != null) { 1118 jumpToLabel(labelNode, block.getBreakLabel()); 1119 } 1120 } 1121 leaveBreakable(block); 1122 return block; 1123 } 1124 1125 private void calculateReturnType() { 1126 // NOTE: if return type is unknown, then the function does not explicitly return a value. Such a function under 1127 // ECMAScript rules returns Undefined, which has Type.OBJECT. We might consider an optimization in the future 1128 // where we can return void functions. 1129 if(returnType.isUnknown()) { 1130 returnType = Type.OBJECT; 1131 } 1132 } 1133 1134 private void createSyntheticReturn(final Block body) { 1135 final FunctionNode functionNode = lc.getCurrentFunction(); 1136 final long token = functionNode.getToken(); 1137 final int finish = functionNode.getFinish(); 1138 final List<Statement> statements = body.getStatements(); 1139 final int lineNumber = statements.isEmpty() ? functionNode.getLineNumber() : statements.get(statements.size() - 1).getLineNumber(); 1140 final IdentNode returnExpr; 1141 if(functionNode.isProgram()) { 1142 returnExpr = new IdentNode(token, finish, RETURN.symbolName()).setSymbol(getCompilerConstantSymbol(functionNode, RETURN)); 1143 } else { 1144 returnExpr = null; 1145 } 1146 syntheticReturn = new ReturnNode(lineNumber, token, finish, returnExpr); 1147 syntheticReturn.accept(this); 1148 } 1149 1150 /** 1151 * Leave a breakable node. If there's a join point associated with its break label (meaning there was at least one 1152 * break statement to the end of the node), insert the join point into the flow. 1153 * @param breakable the breakable node being left. 1154 */ 1155 private void leaveBreakable(final BreakableNode breakable) { 1156 joinOnLabel(breakable.getBreakLabel()); 1157 } 1158 1159 @Override 1160 public Node leaveFunctionNode(final FunctionNode functionNode) { 1161 // Sets the return type of the function and also performs the bottom-up pass of applying type and conversion 1162 // information to nodes as well as doing the calculation on nested functions as required. 1163 FunctionNode newFunction = functionNode; 1164 final NodeVisitor<LexicalContext> applyChangesVisitor = new NodeVisitor<LexicalContext>(new LexicalContext()) { 1165 private boolean inOuterFunction = true; 1166 private final Deque<JoinPredecessor> joinPredecessors = new ArrayDeque<>(); 1167 1168 @Override 1169 protected boolean enterDefault(final Node node) { 1170 if(!inOuterFunction) { 1171 return false; 1172 } 1173 if(node instanceof JoinPredecessor) { 1174 joinPredecessors.push((JoinPredecessor)node); 1175 } 1176 return inOuterFunction; 1177 } 1178 1179 @Override 1180 public boolean enterFunctionNode(final FunctionNode fn) { 1181 if(compiler.isOnDemandCompilation()) { 1182 // Only calculate nested function local variable types if we're doing eager compilation 1183 return false; 1184 } 1185 inOuterFunction = false; 1186 return true; 1187 } 1188 1189 @SuppressWarnings("fallthrough") 1190 @Override 1191 public Node leaveBinaryNode(final BinaryNode binaryNode) { 1192 if(binaryNode.isComparison()) { 1193 final Expression lhs = binaryNode.lhs(); 1194 final Expression rhs = binaryNode.rhs(); 1195 1196 Type cmpWidest = Type.widest(lhs.getType(), rhs.getType()); 1197 boolean newRuntimeNode = false, finalized = false; 1198 final TokenType tt = binaryNode.tokenType(); 1199 switch (tt) { 1200 case EQ_STRICT: 1201 case NE_STRICT: 1202 // Specialize comparison with undefined 1203 final Expression undefinedNode = createIsUndefined(binaryNode, lhs, rhs, 1204 tt == TokenType.EQ_STRICT ? Request.IS_UNDEFINED : Request.IS_NOT_UNDEFINED); 1205 if(undefinedNode != binaryNode) { 1206 return undefinedNode; 1207 } 1208 // Specialize comparison of boolean with non-boolean 1209 if (lhs.getType().isBoolean() != rhs.getType().isBoolean()) { 1210 newRuntimeNode = true; 1211 cmpWidest = Type.OBJECT; 1212 finalized = true; 1213 } 1214 // fallthrough 1215 default: 1216 if (newRuntimeNode || cmpWidest.isObject()) { 1217 return new RuntimeNode(binaryNode).setIsFinal(finalized); 1218 } 1219 } 1220 } else if(binaryNode.isOptimisticUndecidedType()) { 1221 // At this point, we can assign a static type to the optimistic binary ADD operator as now we know 1222 // the types of its operands. 1223 return binaryNode.decideType(); 1224 } 1225 return binaryNode; 1226 } 1227 1228 @Override 1229 protected Node leaveDefault(final Node node) { 1230 if(node instanceof JoinPredecessor) { 1231 final JoinPredecessor original = joinPredecessors.pop(); 1232 assert original.getClass() == node.getClass() : original.getClass().getName() + "!=" + node.getClass().getName(); 1233 return (Node)setLocalVariableConversion(original, (JoinPredecessor)node); 1234 } 1235 return node; 1236 } 1237 1238 @Override 1239 public Node leaveBlock(final Block block) { 1240 if(inOuterFunction && syntheticReturn != null && lc.isFunctionBody()) { 1241 final ArrayList<Statement> stmts = new ArrayList<>(block.getStatements()); 1242 stmts.add((ReturnNode)syntheticReturn.accept(this)); 1243 return block.setStatements(lc, stmts); 1244 } 1245 return super.leaveBlock(block); 1246 } 1247 1248 @Override 1249 public Node leaveFunctionNode(final FunctionNode nestedFunctionNode) { 1250 inOuterFunction = true; 1251 final FunctionNode newNestedFunction = (FunctionNode)nestedFunctionNode.accept( 1252 new LocalVariableTypesCalculator(compiler)); 1253 lc.replace(nestedFunctionNode, newNestedFunction); 1254 return newNestedFunction; 1255 } 1256 1257 @Override 1258 public Node leaveIdentNode(final IdentNode identNode) { 1259 final IdentNode original = (IdentNode)joinPredecessors.pop(); 1260 final Symbol symbol = identNode.getSymbol(); 1261 if(symbol == null) { 1262 assert identNode.isPropertyName(); 1263 return identNode; 1264 } else if(symbol.hasSlot()) { 1265 assert !symbol.isScope() || symbol.isParam(); // Only params can be slotted and scoped. 1266 assert original.getName().equals(identNode.getName()); 1267 final LvarType lvarType = identifierLvarTypes.remove(original); 1268 if(lvarType != null) { 1269 return setLocalVariableConversion(original, identNode.setType(lvarType.type)); 1270 } 1271 // If there's no type, then the identifier must've been in unreachable code. In that case, it can't 1272 // have assigned conversions either. 1273 assert localVariableConversions.get(original) == null; 1274 } else { 1275 assert identIsDeadAndHasNoLiveConversions(original); 1276 } 1277 return identNode; 1278 } 1279 1280 @Override 1281 public Node leaveLiteralNode(final LiteralNode<?> literalNode) { 1282 //for e.g. ArrayLiteralNodes the initial types may have been narrowed due to the 1283 //introduction of optimistic behavior - hence ensure that all literal nodes are 1284 //reinitialized 1285 return literalNode.initialize(lc); 1286 } 1287 1288 @Override 1289 public Node leaveRuntimeNode(final RuntimeNode runtimeNode) { 1290 final Request request = runtimeNode.getRequest(); 1291 final boolean isEqStrict = request == Request.EQ_STRICT; 1292 if(isEqStrict || request == Request.NE_STRICT) { 1293 return createIsUndefined(runtimeNode, runtimeNode.getArgs().get(0), runtimeNode.getArgs().get(1), 1294 isEqStrict ? Request.IS_UNDEFINED : Request.IS_NOT_UNDEFINED); 1295 } 1296 return runtimeNode; 1297 } 1298 1299 @SuppressWarnings("unchecked") 1300 private <T extends JoinPredecessor> T setLocalVariableConversion(final JoinPredecessor original, final T jp) { 1301 // NOTE: can't use Map.remove() as our copy-on-write AST semantics means some nodes appear twice (in 1302 // finally blocks), so we need to be able to access conversions for them multiple times. 1303 return (T)jp.setLocalVariableConversion(lc, localVariableConversions.get(original)); 1304 } 1305 }; 1306 1307 newFunction = newFunction.setBody(lc, (Block)newFunction.getBody().accept(applyChangesVisitor)); 1308 newFunction = newFunction.setReturnType(lc, returnType); 1309 1310 1311 newFunction = newFunction.setState(lc, CompilationState.LOCAL_VARIABLE_TYPES_CALCULATED); 1312 newFunction = newFunction.setParameters(lc, newFunction.visitParameters(applyChangesVisitor)); 1313 return newFunction; 1314 } 1315 1316 private static Expression createIsUndefined(final Expression parent, final Expression lhs, final Expression rhs, final Request request) { 1317 if (isUndefinedIdent(lhs) || isUndefinedIdent(rhs)) { 1318 return new RuntimeNode(parent, request, lhs, rhs); 1319 } 1320 return parent; 1321 } 1322 1323 private static boolean isUndefinedIdent(final Expression expr) { 1324 return expr instanceof IdentNode && "undefined".equals(((IdentNode)expr).getName()); 1325 } 1326 1327 private boolean identIsDeadAndHasNoLiveConversions(final IdentNode identNode) { 1328 final LocalVariableConversion conv = localVariableConversions.get(identNode); 1329 return conv == null || !conv.isLive(); 1330 } 1331 1332 private void onAssignment(final IdentNode identNode, final Expression rhs) { 1333 onAssignment(identNode, toLvarType(getType(rhs))); 1334 } 1335 1336 private void onAssignment(final IdentNode identNode, final LvarType type) { 1337 final Symbol symbol = identNode.getSymbol(); 1338 assert symbol != null : identNode.getName(); 1339 if(!symbol.isBytecodeLocal()) { 1340 return; 1341 } 1342 assert type != null; 1343 final LvarType finalType; 1344 if(type == LvarType.UNDEFINED && getLocalVariableType(symbol) != LvarType.UNDEFINED) { 1345 // Explicit assignment of a known undefined local variable to a local variable that is not undefined will 1346 // materialize that undefined in the assignment target. Note that assigning known undefined to known 1347 // undefined will *not* initialize the variable, e.g. "var x; var y = x;" compiles to no-op. 1348 finalType = LvarType.OBJECT; 1349 symbol.setFlag(Symbol.HAS_OBJECT_VALUE); 1350 } else { 1351 finalType = type; 1352 } 1353 setType(symbol, finalType); 1354 // Explicit assignment of an undefined value. Make sure the variable can store an object 1355 // TODO: if we communicated the fact to codegen with a flag on the IdentNode that the value was already 1356 // undefined before the assignment, we could just ignore it. In general, we could ignore an assignment if we 1357 // know that the value assigned is the same as the current value of the variable, but we'd need constant 1358 // propagation for that. 1359 setIdentifierLvarType(identNode, finalType); 1360 // For purposes of type calculation, we consider an assignment to a local variable to be followed by 1361 // the catch nodes of the current (if any) try block. This will effectively enforce that narrower 1362 // assignments to a local variable in a try block will also have to store a widened value as well. Code 1363 // within the try block will be able to keep loading the narrower value, but after the try block only 1364 // the widest value will remain live. 1365 // Rationale for this is that if there's an use for that variable in any of the catch blocks, or 1366 // following the catch blocks, they must use the widest type. 1367 // Example: 1368 /* 1369 Originally: 1370 =========== 1371 var x; 1372 try { 1373 x = 1; <-- stores into int slot for x 1374 f(x); <-- loads the int slot for x 1375 x = 3.14 <-- stores into the double slot for x 1376 f(x); <-- loads the double slot for x 1377 x = 1; <-- stores into int slot for x 1378 f(x); <-- loads the int slot for x 1379 } finally { 1380 f(x); <-- loads the double slot for x, but can be reached by a path where x is int, so we need 1381 to go back and ensure that double values are also always stored along with int 1382 values. 1383 } 1384 1385 After correction: 1386 ================= 1387 1388 var x; 1389 try { 1390 x = 1; <-- stores into both int and double slots for x 1391 f(x); <-- loads the int slot for x 1392 x = 3.14 <-- stores into the double slot for x 1393 f(x); <-- loads the double slot for x 1394 x = 1; <-- stores into both int and double slots for x 1395 f(x); <-- loads the int slot for x 1396 } finally { 1397 f(x); <-- loads the double slot for x 1398 } 1399 */ 1400 jumpToCatchBlock(identNode); 1401 } 1402 1403 private void onSelfAssignment(final IdentNode identNode, final Expression assignment, final LvarType typeOnLoad) { 1404 final Symbol symbol = identNode.getSymbol(); 1405 assert symbol != null : identNode.getName(); 1406 if(!symbol.isBytecodeLocal()) { 1407 return; 1408 } 1409 final LvarType type = toLvarType(getType(assignment, symbol, typeOnLoad.type)); 1410 // Self-assignment never produce either a boolean or undefined 1411 assert type != null && type != LvarType.UNDEFINED && type != LvarType.BOOLEAN; 1412 setType(symbol, type); 1413 jumpToCatchBlock(identNode); 1414 } 1415 1416 private void resetJoinPoint(final Label label) { 1417 jumpTargets.remove(label); 1418 } 1419 1420 private void setCompilerConstantAsObject(final FunctionNode functionNode, final CompilerConstants cc) { 1421 final Symbol symbol = getCompilerConstantSymbol(functionNode, cc); 1422 setType(symbol, LvarType.OBJECT); 1423 // never mark compiler constants as dead 1424 symbolIsUsed(symbol); 1425 } 1426 1427 private static Symbol getCompilerConstantSymbol(final FunctionNode functionNode, final CompilerConstants cc) { 1428 return functionNode.getBody().getExistingSymbol(cc.symbolName()); 1429 } 1430 1431 private void setConversion(final JoinPredecessor node, final Map<Symbol, LvarType> branchLvarTypes, final Map<Symbol, LvarType> joinLvarTypes) { 1432 if(node == null) { 1433 return; 1434 } 1435 if(branchLvarTypes.isEmpty() || joinLvarTypes.isEmpty()) { 1436 localVariableConversions.remove(node); 1437 } 1438 1439 LocalVariableConversion conversion = null; 1440 if(node instanceof IdentNode) { 1441 // conversions on variable assignment in try block are special cases, as they only apply to the variable 1442 // being assigned and all other conversions should be ignored. 1443 final Symbol symbol = ((IdentNode)node).getSymbol(); 1444 conversion = createConversion(symbol, branchLvarTypes.get(symbol), joinLvarTypes, null); 1445 } else { 1446 for(final Map.Entry<Symbol, LvarType> entry: branchLvarTypes.entrySet()) { 1447 final Symbol symbol = entry.getKey(); 1448 final LvarType branchLvarType = entry.getValue(); 1449 conversion = createConversion(symbol, branchLvarType, joinLvarTypes, conversion); 1450 } 1451 } 1452 if(conversion != null) { 1453 localVariableConversions.put(node, conversion); 1454 } else { 1455 localVariableConversions.remove(node); 1456 } 1457 } 1458 1459 private void setIdentifierLvarType(final IdentNode identNode, final LvarType type) { 1460 assert type != null; 1461 identifierLvarTypes.put(identNode, type); 1462 } 1463 1464 /** 1465 * Marks a local variable as having a specific type from this point onward. Invoked by stores to local variables. 1466 * @param symbol the symbol representing the variable 1467 * @param type the type 1468 */ 1469 @SuppressWarnings("unused") 1470 private void setType(final Symbol symbol, final LvarType type) { 1471 if(getLocalVariableTypeOrNull(symbol) == type) { 1472 return; 1473 } 1474 assert symbol.hasSlot(); 1475 assert !symbol.isGlobal(); 1476 localVariableTypes = localVariableTypes.isEmpty() ? new IdentityHashMap<Symbol, LvarType>() : cloneMap(localVariableTypes); 1477 localVariableTypes.put(symbol, type); 1478 } 1479 1480 /** 1481 * Set a flag in the symbol marking it as needing to be able to store a value of a particular type. Every symbol for 1482 * a local variable will be assigned between 1 and 6 local variable slots for storing all types it is known to need 1483 * to store. 1484 * @param symbol the symbol 1485 */ 1486 private void symbolIsUsed(final Symbol symbol) { 1487 symbolIsUsed(symbol, getLocalVariableType(symbol)); 1488 } 1489 1490 /** 1491 * Gets the type of the expression, dependent on the current types of the local variables. 1492 * 1493 * @param expr the expression 1494 * @return the current type of the expression dependent on the current types of the local variables. 1495 */ 1496 private Type getType(final Expression expr) { 1497 return expr.getType(getSymbolToType()); 1498 } 1499 1500 /** 1501 * Returns a function object from symbols to their types, used by the expressions to evaluate their type. 1502 * {@link BinaryNode} specifically uses identity of the function to cache type calculations. This method makes 1503 * sure to return the same function object while the local variable types don't change, and create a new function 1504 * object if the local variable types have been changed. 1505 * @return a function object representing a mapping from symbols to their types. 1506 */ 1507 private Function<Symbol, Type> getSymbolToType() { 1508 if(symbolToType.isStale()) { 1509 symbolToType = new SymbolToType(); 1510 } 1511 return symbolToType; 1512 } 1513 1514 private class SymbolToType implements Function<Symbol, Type> { 1515 private final Object boundTypes = localVariableTypes; 1516 @Override 1517 public Type apply(final Symbol t) { 1518 return getLocalVariableType(t).type; 1519 } 1520 1521 boolean isStale() { 1522 return boundTypes != localVariableTypes; 1523 } 1524 } 1525 1526 /** 1527 * Gets the type of the expression, dependent on the current types of the local variables and a single overridden 1528 * symbol type. Used by type calculation on compound operators to ensure the type of the LHS at the time it was 1529 * loaded (which can potentially be different after RHS evaluation, e.g. "var x; x += x = 0;") is preserved for 1530 * the calculation. 1531 * 1532 * @param expr the expression 1533 * @param overriddenSymbol the overridden symbol 1534 * @param overriddenType the overridden type 1535 * @return the current type of the expression dependent on the current types of the local variables and the single 1536 * potentially overridden type. 1537 */ 1538 private Type getType(final Expression expr, final Symbol overriddenSymbol, final Type overriddenType) { 1539 return expr.getType(getSymbolToType(overriddenSymbol, overriddenType)); 1540 } 1541 1542 private Function<Symbol, Type> getSymbolToType(final Symbol overriddenSymbol, final Type overriddenType) { 1543 return getLocalVariableType(overriddenSymbol).type == overriddenType ? getSymbolToType() : 1544 new SymbolToTypeOverride(overriddenSymbol, overriddenType); 1545 } 1546 1547 private class SymbolToTypeOverride implements Function<Symbol, Type> { 1548 private final Function<Symbol, Type> originalSymbolToType = getSymbolToType(); 1549 private final Symbol overriddenSymbol; 1550 private final Type overriddenType; 1551 1552 SymbolToTypeOverride(final Symbol overriddenSymbol, final Type overriddenType) { 1553 this.overriddenSymbol = overriddenSymbol; 1554 this.overriddenType = overriddenType; 1555 } 1556 1557 @Override 1558 public Type apply(final Symbol symbol) { 1559 return symbol == overriddenSymbol ? overriddenType : originalSymbolToType.apply(symbol); 1560 } 1561 } 1562} 1563