Label.java revision 1068:34ef988d5959
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 */ 25package jdk.nashorn.internal.codegen; 26 27import java.io.Serializable; 28import java.util.ArrayList; 29import java.util.Arrays; 30import java.util.BitSet; 31import java.util.Iterator; 32import java.util.List; 33import java.util.ListIterator; 34import jdk.nashorn.internal.codegen.types.Type; 35 36/** 37 * Abstraction for labels, separating a label from the underlying 38 * byte code emitter. Also augmenting label with e.g. a name 39 * for easier debugging and reading code 40 * 41 * see -Dnashorn.codegen.debug, --log=codegen 42 */ 43public final class Label implements Serializable { 44 private static final long serialVersionUID = 1L; 45 46 //byte code generation evaluation type stack for consistency check 47 //and correct opcode selection. one per label as a label may be a 48 //join point 49 static final class Stack implements Cloneable { 50 static final int NON_LOAD = -1; 51 52 Type[] data; 53 int[] localLoads; 54 int sp; 55 56 List<Type> localVariableTypes; 57 int firstTemp; // index of the first temporary local variable 58 // Bitmap marking last slot belonging to a single symbol. 59 BitSet symbolBoundary; 60 61 Stack() { 62 data = new Type[8]; 63 localLoads = new int[8]; 64 localVariableTypes = new ArrayList<>(8); 65 symbolBoundary = new BitSet(); 66 } 67 68 boolean isEmpty() { 69 return sp == 0; 70 } 71 72 int size() { 73 return sp; 74 } 75 76 void clear() { 77 sp = 0; 78 } 79 80 void push(final Type type) { 81 if (data.length == sp) { 82 final Type[] newData = new Type[sp * 2]; 83 final int[] newLocalLoad = new int[sp * 2]; 84 System.arraycopy(data, 0, newData, 0, sp); 85 System.arraycopy(localLoads, 0, newLocalLoad, 0, sp); 86 data = newData; 87 localLoads = newLocalLoad; 88 } 89 data[sp] = type; 90 localLoads[sp] = NON_LOAD; 91 sp++; 92 } 93 94 Type peek() { 95 return peek(0); 96 } 97 98 Type peek(final int n) { 99 final int pos = sp - 1 - n; 100 return pos < 0 ? null : data[pos]; 101 } 102 103 /** 104 * Retrieve the top <tt>count</tt> types on the stack without modifying it. 105 * 106 * @param count number of types to return 107 * @return array of Types 108 */ 109 Type[] getTopTypes(final int count) { 110 final Type[] topTypes = new Type[count]; 111 System.arraycopy(data, sp - count, topTypes, 0, count); 112 return topTypes; 113 } 114 115 int[] getLocalLoads(final int from, final int to) { 116 final int count = to - from; 117 final int[] topLocalLoads = new int[count]; 118 System.arraycopy(localLoads, from, topLocalLoads, 0, count); 119 return topLocalLoads; 120 } 121 122 /** 123 * Returns the number of used local variable slots, including all live stack-store temporaries. 124 * @return the number of used local variable slots, including all live stack-store temporaries. 125 */ 126 int getUsedSlotsWithLiveTemporaries() { 127 // There are at least as many as are declared by the current blocks. 128 int usedSlots = firstTemp; 129 // Look at every load on the stack, and bump the number of used slots up by the temporaries seen there. 130 for(int i = sp; i-->0;) { 131 final int slot = localLoads[i]; 132 if(slot != Label.Stack.NON_LOAD) { 133 final int afterSlot = slot + localVariableTypes.get(slot).getSlots(); 134 if(afterSlot > usedSlots) { 135 usedSlots = afterSlot; 136 } 137 } 138 } 139 return usedSlots; 140 } 141 142 /** 143 * 144 * @param joinOrigin the stack from the other branch. 145 */ 146 void joinFrom(final Stack joinOrigin, final boolean breakTarget) { 147 assert isStackCompatible(joinOrigin); 148 if(breakTarget) { 149 // As we're joining labels that can jump across block boundaries, the number of local variables can 150 // differ, and we should always respect the one having less variables. 151 firstTemp = Math.min(firstTemp, joinOrigin.firstTemp); 152 } else { 153 assert firstTemp == joinOrigin.firstTemp; 154 } 155 final int[] otherLoads = joinOrigin.localLoads; 156 int firstDeadTemp = firstTemp; 157 for(int i = 0; i < sp; ++i) { 158 final int localLoad = localLoads[i]; 159 if(localLoad != otherLoads[i]) { 160 localLoads[i] = NON_LOAD; 161 } else if(localLoad >= firstDeadTemp) { 162 firstDeadTemp = localLoad + localVariableTypes.get(localLoad).getSlots(); 163 } 164 } 165 // Eliminate dead temporaries 166 undefineLocalVariables(firstDeadTemp, false); 167 assert isVariablePartitioningEqual(joinOrigin, firstDeadTemp); 168 mergeVariableTypes(joinOrigin, firstDeadTemp); 169 } 170 171 private void mergeVariableTypes(final Stack joinOrigin, final int toSlot) { 172 final ListIterator<Type> it1 = localVariableTypes.listIterator(); 173 final Iterator<Type> it2 = joinOrigin.localVariableTypes.iterator(); 174 175 for(int i = 0; i < toSlot; ++i) { 176 final Type thisType = it1.next(); 177 final Type otherType = it2.next(); 178 if(otherType == Type.UNKNOWN) { 179 // Variables that are <unknown> on the other branch will become <unknown> here too. 180 it1.set(Type.UNKNOWN); 181 } else if (thisType != otherType) { 182 if(thisType.isObject() && otherType.isObject()) { 183 // different object types are merged into Object. 184 // TODO: maybe find most common superclass? 185 it1.set(Type.OBJECT); 186 } else { 187 assert thisType == Type.UNKNOWN; 188 } 189 } 190 } 191 } 192 193 void joinFromTry(final Stack joinOrigin) { 194 // As we're joining labels that can jump across block boundaries, the number of local variables can 195 // differ, and we should always respect the one having less variables. 196 firstTemp = Math.min(firstTemp, joinOrigin.firstTemp); 197 assert isVariablePartitioningEqual(joinOrigin, firstTemp); 198 mergeVariableTypes(joinOrigin, firstTemp); 199 } 200 201 private int getFirstDeadLocal(final List<Type> types) { 202 int i = types.size(); 203 for(final ListIterator<Type> it = types.listIterator(i); 204 it.hasPrevious() && it.previous() == Type.UNKNOWN; 205 --i) { 206 // no body 207 } 208 209 // Respect symbol boundaries; we never chop off half a symbol's storage 210 while(!symbolBoundary.get(i - 1)) { 211 ++i; 212 } 213 return i; 214 } 215 216 private boolean isStackCompatible(final Stack other) { 217 if (sp != other.sp) { 218 return false; 219 } 220 for (int i = 0; i < sp; i++) { 221 if (!data[i].isEquivalentTo(other.data[i])) { 222 return false; 223 } 224 } 225 return true; 226 } 227 228 private boolean isVariablePartitioningEqual(final Stack other, final int toSlot) { 229 // No difference in the symbol boundaries before the toSlot 230 final BitSet diff = other.getSymbolBoundaryCopy(); 231 diff.xor(symbolBoundary); 232 return diff.previousSetBit(toSlot - 1) == -1; 233 } 234 235 void markDeadLocalVariables(final int fromSlot, final int slotCount) { 236 final int localCount = localVariableTypes.size(); 237 if(fromSlot >= localCount) { 238 return; 239 } 240 final int toSlot = Math.min(fromSlot + slotCount, localCount); 241 invalidateLocalLoadsOnStack(fromSlot, toSlot); 242 for(int i = fromSlot; i < toSlot; ++i) { 243 localVariableTypes.set(i, Type.UNKNOWN); 244 } 245 } 246 247 @SuppressWarnings("unchecked") 248 List<Type> getLocalVariableTypesCopy() { 249 return (List<Type>)((ArrayList<Type>)localVariableTypes).clone(); 250 } 251 252 BitSet getSymbolBoundaryCopy() { 253 return (BitSet)symbolBoundary.clone(); 254 } 255 256 /** 257 * Returns a list of local variable slot types, but for those symbols that have multiple values, only the slot 258 * holding the widest type is marked as live. 259 * @return a list of widest local variable slot types. 260 */ 261 List<Type> getWidestLiveLocals(final List<Type> lvarTypes) { 262 final List<Type> widestLiveLocals = new ArrayList<>(lvarTypes); 263 boolean keepNextValue = true; 264 final int size = widestLiveLocals.size(); 265 for(int i = size - 1; i-- > 0;) { 266 if(symbolBoundary.get(i)) { 267 keepNextValue = true; 268 } 269 final Type t = widestLiveLocals.get(i); 270 if(t != Type.UNKNOWN) { 271 if(keepNextValue) { 272 if(t != Type.SLOT_2) { 273 keepNextValue = false; 274 } 275 } else { 276 widestLiveLocals.set(i, Type.UNKNOWN); 277 } 278 } 279 } 280 widestLiveLocals.subList(Math.max(getFirstDeadLocal(widestLiveLocals), firstTemp), widestLiveLocals.size()).clear(); 281 return widestLiveLocals; 282 } 283 284 String markSymbolBoundariesInLvarTypesDescriptor(final String lvarDescriptor) { 285 final char[] chars = lvarDescriptor.toCharArray(); 286 int j = 0; 287 for(int i = 0; i < chars.length; ++i) { 288 final char c = chars[i]; 289 final int nextj = j + CodeGeneratorLexicalContext.getTypeForSlotDescriptor(c).getSlots(); 290 if(!symbolBoundary.get(nextj - 1)) { 291 chars[i] = Character.toLowerCase(c); 292 } 293 j = nextj; 294 } 295 return new String(chars); 296 } 297 298 Type pop() { 299 assert sp > 0; 300 return data[--sp]; 301 } 302 303 @Override 304 public Stack clone() { 305 try { 306 final Stack clone = (Stack)super.clone(); 307 clone.data = data.clone(); 308 clone.localLoads = localLoads.clone(); 309 clone.symbolBoundary = getSymbolBoundaryCopy(); 310 clone.localVariableTypes = getLocalVariableTypesCopy(); 311 return clone; 312 } catch(final CloneNotSupportedException e) { 313 throw new AssertionError("", e); 314 } 315 } 316 317 private Stack cloneWithEmptyStack() { 318 final Stack stack = clone(); 319 stack.sp = 0; 320 return stack; 321 } 322 323 int getTopLocalLoad() { 324 return localLoads[sp - 1]; 325 } 326 327 void markLocalLoad(final int slot) { 328 localLoads[sp - 1] = slot; 329 } 330 331 /** 332 * Performs various bookeeping when a value is stored in a local variable slot. 333 * @param slot the slot written to 334 * @param onlySymbolLiveValue if true, this is the symbol's only live value, and other values of the symbol 335 * should be marked dead 336 * @param Type the type written to the slot 337 */ 338 void onLocalStore(final Type type, final int slot, final boolean onlySymbolLiveValue) { 339 if(onlySymbolLiveValue) { 340 final int fromSlot = slot == 0 ? 0 : (symbolBoundary.previousSetBit(slot - 1) + 1); 341 final int toSlot = symbolBoundary.nextSetBit(slot) + 1; 342 for(int i = fromSlot; i < toSlot; ++i) { 343 localVariableTypes.set(i, Type.UNKNOWN); 344 } 345 invalidateLocalLoadsOnStack(fromSlot, toSlot); 346 } else { 347 invalidateLocalLoadsOnStack(slot, slot + type.getSlots()); 348 } 349 350 localVariableTypes.set(slot, type); 351 if(type.isCategory2()) { 352 localVariableTypes.set(slot + 1, Type.SLOT_2); 353 } 354 } 355 356 /** 357 * Given a slot range, invalidate knowledge about local loads on stack from these slots (because they're being 358 * killed). 359 * @param fromSlot first slot, inclusive. 360 * @param toSlot last slot, exclusive. 361 */ 362 private void invalidateLocalLoadsOnStack(final int fromSlot, final int toSlot) { 363 for(int i = 0; i < sp; ++i) { 364 final int localLoad = localLoads[i]; 365 if(localLoad >= fromSlot && localLoad < toSlot) { 366 localLoads[i] = NON_LOAD; 367 } 368 } 369 } 370 371 /** 372 * Marks a range of slots as belonging to a defined local variable. The slots will start out with no live value 373 * in them. 374 * @param fromSlot first slot, inclusive. 375 * @param toSlot last slot, exclusive. 376 */ 377 void defineBlockLocalVariable(final int fromSlot, final int toSlot) { 378 defineLocalVariable(fromSlot, toSlot); 379 assert firstTemp < toSlot; 380 firstTemp = toSlot; 381 } 382 383 /** 384 * Defines a new temporary local variable and returns its allocated index. 385 * @param width the required width (in slots) for the new variable. 386 * @return the bytecode slot index where the newly allocated local begins. 387 */ 388 int defineTemporaryLocalVariable(final int width) { 389 final int fromSlot = getUsedSlotsWithLiveTemporaries(); 390 defineLocalVariable(fromSlot, fromSlot + width); 391 return fromSlot; 392 } 393 394 /** 395 * Marks a range of slots as belonging to a defined temporary local variable. The slots will start out with no 396 * live value in them. 397 * @param fromSlot first slot, inclusive. 398 * @param toSlot last slot, exclusive. 399 */ 400 void defineTemporaryLocalVariable(final int fromSlot, final int toSlot) { 401 defineLocalVariable(fromSlot, toSlot); 402 } 403 404 private void defineLocalVariable(final int fromSlot, final int toSlot) { 405 assert !hasLoadsOnStack(fromSlot, toSlot); 406 assert fromSlot < toSlot; 407 symbolBoundary.clear(fromSlot, toSlot - 1); 408 symbolBoundary.set(toSlot - 1); 409 final int lastExisting = Math.min(toSlot, localVariableTypes.size()); 410 for(int i = fromSlot; i < lastExisting; ++i) { 411 localVariableTypes.set(i, Type.UNKNOWN); 412 } 413 for(int i = lastExisting; i < toSlot; ++i) { 414 localVariableTypes.add(i, Type.UNKNOWN); 415 } 416 } 417 418 /** 419 * Undefines all local variables past the specified slot. 420 * @param fromSlot the first slot to be undefined 421 * @param canTruncateSymbol if false, the fromSlot must be either the first slot of a symbol, or the first slot 422 * after the last symbol. If true, the fromSlot can be in the middle of the storage area for a symbol. This 423 * should be used with care - it is only meant for use in optimism exception handlers. 424 */ 425 void undefineLocalVariables(final int fromSlot, final boolean canTruncateSymbol) { 426 final int lvarCount = localVariableTypes.size(); 427 assert lvarCount == symbolBoundary.length(); 428 assert !hasLoadsOnStack(fromSlot, lvarCount); 429 if(canTruncateSymbol) { 430 if(fromSlot > 0) { 431 symbolBoundary.set(fromSlot - 1); 432 } 433 } else { 434 assert fromSlot == 0 || symbolBoundary.get(fromSlot - 1); 435 } 436 if(fromSlot < lvarCount) { 437 symbolBoundary.clear(fromSlot, lvarCount); 438 localVariableTypes.subList(fromSlot, lvarCount).clear(); 439 } 440 firstTemp = Math.min(fromSlot, firstTemp); 441 assert symbolBoundary.length() == localVariableTypes.size(); 442 assert symbolBoundary.length() == fromSlot; 443 } 444 445 private void markAsOptimisticCatchHandler(final int liveLocalCount) { 446 // Live temporaries that are no longer on stack are undefined 447 undefineLocalVariables(liveLocalCount, true); 448 // Temporaries are promoted 449 firstTemp = liveLocalCount; 450 // No trailing undefineds 451 localVariableTypes.subList(firstTemp, localVariableTypes.size()).clear(); 452 assert symbolBoundary.length() == firstTemp; 453 // Generalize all reference types to Object, and promote boolean to int 454 for(final ListIterator<Type> it = localVariableTypes.listIterator(); it.hasNext();) { 455 final Type type = it.next(); 456 if(type == Type.BOOLEAN) { 457 it.set(Type.INT); 458 } else if(type.isObject() && type != Type.OBJECT) { 459 it.set(Type.OBJECT); 460 } 461 } 462 } 463 464 /** 465 * Returns true if any loads on the stack come from the specified slot range. 466 * @param fromSlot start of the range (inclusive) 467 * @param toSlot end of the range (exclusive) 468 * @return true if any loads on the stack come from the specified slot range. 469 */ 470 boolean hasLoadsOnStack(final int fromSlot, final int toSlot) { 471 for(int i = 0; i < sp; ++i) { 472 final int load = localLoads[i]; 473 if(load >= fromSlot && load < toSlot) { 474 return true; 475 } 476 } 477 return false; 478 } 479 480 @Override 481 public String toString() { 482 return "stack=" + Arrays.toString(Arrays.copyOf(data, sp)) 483 + ", symbolBoundaries=" + String.valueOf(symbolBoundary) 484 + ", firstTemp=" + firstTemp 485 + ", localTypes=" + String.valueOf(localVariableTypes) 486 ; 487 } 488 } 489 490 /** Next id for debugging purposes, remove if footprint becomes unmanageable */ 491 private static int nextId = 0; 492 493 /** Name of this label */ 494 private final String name; 495 496 /** Type stack at this label */ 497 private transient Label.Stack stack; 498 499 /** ASM representation of this label */ 500 private jdk.internal.org.objectweb.asm.Label label; 501 502 /** Id for debugging purposes, remove if footprint becomes unmanageable */ 503 private final int id; 504 505 /** Is this label reachable (anything ever jumped to it)? */ 506 private transient boolean reachable; 507 508 private transient boolean breakTarget; 509 510 /** 511 * Constructor 512 * 513 * @param name name of this label 514 */ 515 public Label(final String name) { 516 super(); 517 this.name = name; 518 this.id = nextId++; 519 } 520 521 /** 522 * Copy constructor 523 * 524 * @param label a label to clone 525 */ 526 public Label(final Label label) { 527 super(); 528 this.name = label.name; 529 this.id = label.id; 530 } 531 532 jdk.internal.org.objectweb.asm.Label getLabel() { 533 if (this.label == null) { 534 this.label = new jdk.internal.org.objectweb.asm.Label(); 535 } 536 return label; 537 } 538 539 Label.Stack getStack() { 540 return stack; 541 } 542 543 void joinFrom(final Label.Stack joinOrigin) { 544 this.reachable = true; 545 if(stack == null) { 546 stack = joinOrigin.clone(); 547 } else { 548 stack.joinFrom(joinOrigin, breakTarget); 549 } 550 } 551 552 void joinFromTry(final Label.Stack joinOrigin, final boolean isOptimismHandler) { 553 this.reachable = true; 554 if (stack == null) { 555 if(!isOptimismHandler) { 556 stack = joinOrigin.cloneWithEmptyStack(); 557 // Optimism handler needs temporaries to remain live, others don't. 558 stack.undefineLocalVariables(stack.firstTemp, false); 559 } 560 } else { 561 assert !isOptimismHandler; 562 stack.joinFromTry(joinOrigin); 563 } 564 } 565 566 void markAsBreakTarget() { 567 breakTarget = true; 568 } 569 570 boolean isBreakTarget() { 571 return breakTarget; 572 } 573 574 void onCatch() { 575 if(stack != null) { 576 stack = stack.cloneWithEmptyStack(); 577 } 578 } 579 void markAsOptimisticCatchHandler(final Label.Stack currentStack, final int liveLocalCount) { 580 stack = currentStack.cloneWithEmptyStack(); 581 stack.markAsOptimisticCatchHandler(liveLocalCount); 582 } 583 584 void markAsOptimisticContinuationHandlerFor(final Label afterConsumeStackLabel) { 585 stack = afterConsumeStackLabel.stack.cloneWithEmptyStack(); 586 } 587 588 boolean isReachable() { 589 return reachable; 590 } 591 592 boolean isAfter(final Label other) { 593 return label.getOffset() > other.label.getOffset(); 594 } 595 596 private String str; 597 598 @Override 599 public String toString() { 600 if (str == null) { 601 str = name + '_' + id; 602 } 603 return str; 604 } 605} 606