| /* |
| * Copyright (c) 2010, 2013, Oracle and/or its affiliates. All rights reserved. |
| * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
| * |
| * This code is free software; you can redistribute it and/or modify it |
| * under the terms of the GNU General Public License version 2 only, as |
| * published by the Free Software Foundation. Oracle designates this |
| * particular file as subject to the "Classpath" exception as provided |
| * by Oracle in the LICENSE file that accompanied this code. |
| * |
| * This code is distributed in the hope that it will be useful, but WITHOUT |
| * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
| * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
| * version 2 for more details (a copy is included in the LICENSE file that |
| * accompanied this code). |
| * |
| * You should have received a copy of the GNU General Public License version |
| * 2 along with this work; if not, write to the Free Software Foundation, |
| * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. |
| * |
| * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
| * or visit www.oracle.com if you need additional information or have any |
| * questions. |
| */ |
| package jdk.nashorn.internal.codegen; |
| |
| import java.io.Serializable; |
| import java.util.ArrayList; |
| import java.util.Arrays; |
| import java.util.BitSet; |
| import java.util.Iterator; |
| import java.util.List; |
| import java.util.ListIterator; |
| import jdk.nashorn.internal.codegen.types.Type; |
| |
| /** |
| * Abstraction for labels, separating a label from the underlying |
| * byte code emitter. Also augmenting label with e.g. a name |
| * for easier debugging and reading code |
| * |
| * see -Dnashorn.codegen.debug, --log=codegen |
| */ |
| public final class Label implements Serializable { |
| private static final long serialVersionUID = 1L; |
| |
| //byte code generation evaluation type stack for consistency check |
| //and correct opcode selection. one per label as a label may be a |
| //join point |
| static final class Stack implements Cloneable { |
| static final int NON_LOAD = -1; |
| |
| Type[] data; |
| int[] localLoads; |
| int sp; |
| |
| List<Type> localVariableTypes; |
| int firstTemp; // index of the first temporary local variable |
| // Bitmap marking last slot belonging to a single symbol. |
| BitSet symbolBoundary; |
| |
| Stack() { |
| data = new Type[8]; |
| localLoads = new int[8]; |
| localVariableTypes = new ArrayList<>(8); |
| symbolBoundary = new BitSet(); |
| } |
| |
| boolean isEmpty() { |
| return sp == 0; |
| } |
| |
| int size() { |
| return sp; |
| } |
| |
| void clear() { |
| sp = 0; |
| } |
| |
| void push(final Type type) { |
| if (data.length == sp) { |
| final Type[] newData = new Type[sp * 2]; |
| final int[] newLocalLoad = new int[sp * 2]; |
| System.arraycopy(data, 0, newData, 0, sp); |
| System.arraycopy(localLoads, 0, newLocalLoad, 0, sp); |
| data = newData; |
| localLoads = newLocalLoad; |
| } |
| data[sp] = type; |
| localLoads[sp] = NON_LOAD; |
| sp++; |
| } |
| |
| Type peek() { |
| return peek(0); |
| } |
| |
| Type peek(final int n) { |
| final int pos = sp - 1 - n; |
| return pos < 0 ? null : data[pos]; |
| } |
| |
| /** |
| * Retrieve the top <tt>count</tt> types on the stack without modifying it. |
| * |
| * @param count number of types to return |
| * @return array of Types |
| */ |
| Type[] getTopTypes(final int count) { |
| final Type[] topTypes = new Type[count]; |
| System.arraycopy(data, sp - count, topTypes, 0, count); |
| return topTypes; |
| } |
| |
| int[] getLocalLoads(final int from, final int to) { |
| final int count = to - from; |
| final int[] topLocalLoads = new int[count]; |
| System.arraycopy(localLoads, from, topLocalLoads, 0, count); |
| return topLocalLoads; |
| } |
| |
| /** |
| * Returns the number of used local variable slots, including all live stack-store temporaries. |
| * @return the number of used local variable slots, including all live stack-store temporaries. |
| */ |
| int getUsedSlotsWithLiveTemporaries() { |
| // There are at least as many as are declared by the current blocks. |
| int usedSlots = firstTemp; |
| // Look at every load on the stack, and bump the number of used slots up by the temporaries seen there. |
| for(int i = sp; i-->0;) { |
| final int slot = localLoads[i]; |
| if(slot != Label.Stack.NON_LOAD) { |
| final int afterSlot = slot + localVariableTypes.get(slot).getSlots(); |
| if(afterSlot > usedSlots) { |
| usedSlots = afterSlot; |
| } |
| } |
| } |
| return usedSlots; |
| } |
| |
| /** |
| * |
| * @param joinOrigin the stack from the other branch. |
| */ |
| void joinFrom(final Stack joinOrigin, final boolean breakTarget) { |
| assert isStackCompatible(joinOrigin); |
| if(breakTarget) { |
| // As we're joining labels that can jump across block boundaries, the number of local variables can |
| // differ, and we should always respect the one having less variables. |
| firstTemp = Math.min(firstTemp, joinOrigin.firstTemp); |
| } else { |
| assert firstTemp == joinOrigin.firstTemp; |
| } |
| final int[] otherLoads = joinOrigin.localLoads; |
| int firstDeadTemp = firstTemp; |
| for(int i = 0; i < sp; ++i) { |
| final int localLoad = localLoads[i]; |
| if(localLoad != otherLoads[i]) { |
| localLoads[i] = NON_LOAD; |
| } else if(localLoad >= firstDeadTemp) { |
| firstDeadTemp = localLoad + localVariableTypes.get(localLoad).getSlots(); |
| } |
| } |
| // Eliminate dead temporaries |
| undefineLocalVariables(firstDeadTemp, false); |
| assert isVariablePartitioningEqual(joinOrigin, firstDeadTemp); |
| mergeVariableTypes(joinOrigin, firstDeadTemp); |
| } |
| |
| private void mergeVariableTypes(final Stack joinOrigin, final int toSlot) { |
| final ListIterator<Type> it1 = localVariableTypes.listIterator(); |
| final Iterator<Type> it2 = joinOrigin.localVariableTypes.iterator(); |
| |
| for(int i = 0; i < toSlot; ++i) { |
| final Type thisType = it1.next(); |
| final Type otherType = it2.next(); |
| if(otherType == Type.UNKNOWN) { |
| // Variables that are <unknown> on the other branch will become <unknown> here too. |
| it1.set(Type.UNKNOWN); |
| } else if (thisType != otherType) { |
| if(thisType.isObject() && otherType.isObject()) { |
| // different object types are merged into Object. |
| // TODO: maybe find most common superclass? |
| it1.set(Type.OBJECT); |
| } else { |
| assert thisType == Type.UNKNOWN; |
| } |
| } |
| } |
| } |
| |
| void joinFromTry(final Stack joinOrigin) { |
| // As we're joining labels that can jump across block boundaries, the number of local variables can |
| // differ, and we should always respect the one having less variables. |
| firstTemp = Math.min(firstTemp, joinOrigin.firstTemp); |
| assert isVariablePartitioningEqual(joinOrigin, firstTemp); |
| mergeVariableTypes(joinOrigin, firstTemp); |
| } |
| |
| private int getFirstDeadLocal(final List<Type> types) { |
| int i = types.size(); |
| for(final ListIterator<Type> it = types.listIterator(i); |
| it.hasPrevious() && it.previous() == Type.UNKNOWN; |
| --i) { |
| // no body |
| } |
| |
| // Respect symbol boundaries; we never chop off half a symbol's storage |
| while(!symbolBoundary.get(i - 1)) { |
| ++i; |
| } |
| return i; |
| } |
| |
| private boolean isStackCompatible(final Stack other) { |
| if (sp != other.sp) { |
| return false; |
| } |
| for (int i = 0; i < sp; i++) { |
| if (!data[i].isEquivalentTo(other.data[i])) { |
| return false; |
| } |
| } |
| return true; |
| } |
| |
| private boolean isVariablePartitioningEqual(final Stack other, final int toSlot) { |
| // No difference in the symbol boundaries before the toSlot |
| final BitSet diff = other.getSymbolBoundaryCopy(); |
| diff.xor(symbolBoundary); |
| return diff.previousSetBit(toSlot - 1) == -1; |
| } |
| |
| void markDeadLocalVariables(final int fromSlot, final int slotCount) { |
| final int localCount = localVariableTypes.size(); |
| if(fromSlot >= localCount) { |
| return; |
| } |
| final int toSlot = Math.min(fromSlot + slotCount, localCount); |
| invalidateLocalLoadsOnStack(fromSlot, toSlot); |
| for(int i = fromSlot; i < toSlot; ++i) { |
| localVariableTypes.set(i, Type.UNKNOWN); |
| } |
| } |
| |
| @SuppressWarnings("unchecked") |
| List<Type> getLocalVariableTypesCopy() { |
| return (List<Type>)((ArrayList<Type>)localVariableTypes).clone(); |
| } |
| |
| BitSet getSymbolBoundaryCopy() { |
| return (BitSet)symbolBoundary.clone(); |
| } |
| |
| /** |
| * Returns a list of local variable slot types, but for those symbols that have multiple values, only the slot |
| * holding the widest type is marked as live. |
| * @return a list of widest local variable slot types. |
| */ |
| List<Type> getWidestLiveLocals(final List<Type> lvarTypes) { |
| final List<Type> widestLiveLocals = new ArrayList<>(lvarTypes); |
| boolean keepNextValue = true; |
| final int size = widestLiveLocals.size(); |
| for(int i = size - 1; i-- > 0;) { |
| if(symbolBoundary.get(i)) { |
| keepNextValue = true; |
| } |
| final Type t = widestLiveLocals.get(i); |
| if(t != Type.UNKNOWN) { |
| if(keepNextValue) { |
| if(t != Type.SLOT_2) { |
| keepNextValue = false; |
| } |
| } else { |
| widestLiveLocals.set(i, Type.UNKNOWN); |
| } |
| } |
| } |
| widestLiveLocals.subList(Math.max(getFirstDeadLocal(widestLiveLocals), firstTemp), widestLiveLocals.size()).clear(); |
| return widestLiveLocals; |
| } |
| |
| String markSymbolBoundariesInLvarTypesDescriptor(final String lvarDescriptor) { |
| final char[] chars = lvarDescriptor.toCharArray(); |
| int j = 0; |
| for(int i = 0; i < chars.length; ++i) { |
| final char c = chars[i]; |
| final int nextj = j + CodeGeneratorLexicalContext.getTypeForSlotDescriptor(c).getSlots(); |
| if(!symbolBoundary.get(nextj - 1)) { |
| chars[i] = Character.toLowerCase(c); |
| } |
| j = nextj; |
| } |
| return new String(chars); |
| } |
| |
| Type pop() { |
| assert sp > 0; |
| return data[--sp]; |
| } |
| |
| @Override |
| public Stack clone() { |
| try { |
| final Stack clone = (Stack)super.clone(); |
| clone.data = data.clone(); |
| clone.localLoads = localLoads.clone(); |
| clone.symbolBoundary = getSymbolBoundaryCopy(); |
| clone.localVariableTypes = getLocalVariableTypesCopy(); |
| return clone; |
| } catch(final CloneNotSupportedException e) { |
| throw new AssertionError("", e); |
| } |
| } |
| |
| private Stack cloneWithEmptyStack() { |
| final Stack stack = clone(); |
| stack.sp = 0; |
| return stack; |
| } |
| |
| int getTopLocalLoad() { |
| return localLoads[sp - 1]; |
| } |
| |
| void markLocalLoad(final int slot) { |
| localLoads[sp - 1] = slot; |
| } |
| |
| /** |
| * Performs various bookeeping when a value is stored in a local variable slot. |
| * @param slot the slot written to |
| * @param onlySymbolLiveValue if true, this is the symbol's only live value, and other values of the symbol |
| * should be marked dead |
| * @param type the type written to the slot |
| */ |
| void onLocalStore(final Type type, final int slot, final boolean onlySymbolLiveValue) { |
| if(onlySymbolLiveValue) { |
| final int fromSlot = slot == 0 ? 0 : (symbolBoundary.previousSetBit(slot - 1) + 1); |
| final int toSlot = symbolBoundary.nextSetBit(slot) + 1; |
| for(int i = fromSlot; i < toSlot; ++i) { |
| localVariableTypes.set(i, Type.UNKNOWN); |
| } |
| invalidateLocalLoadsOnStack(fromSlot, toSlot); |
| } else { |
| invalidateLocalLoadsOnStack(slot, slot + type.getSlots()); |
| } |
| |
| localVariableTypes.set(slot, type); |
| if(type.isCategory2()) { |
| localVariableTypes.set(slot + 1, Type.SLOT_2); |
| } |
| } |
| |
| /** |
| * Given a slot range, invalidate knowledge about local loads on stack from these slots (because they're being |
| * killed). |
| * @param fromSlot first slot, inclusive. |
| * @param toSlot last slot, exclusive. |
| */ |
| private void invalidateLocalLoadsOnStack(final int fromSlot, final int toSlot) { |
| for(int i = 0; i < sp; ++i) { |
| final int localLoad = localLoads[i]; |
| if(localLoad >= fromSlot && localLoad < toSlot) { |
| localLoads[i] = NON_LOAD; |
| } |
| } |
| } |
| |
| /** |
| * Marks a range of slots as belonging to a defined local variable. The slots will start out with no live value |
| * in them. |
| * @param fromSlot first slot, inclusive. |
| * @param toSlot last slot, exclusive. |
| */ |
| void defineBlockLocalVariable(final int fromSlot, final int toSlot) { |
| defineLocalVariable(fromSlot, toSlot); |
| assert firstTemp < toSlot; |
| firstTemp = toSlot; |
| } |
| |
| /** |
| * Defines a new temporary local variable and returns its allocated index. |
| * @param width the required width (in slots) for the new variable. |
| * @return the bytecode slot index where the newly allocated local begins. |
| */ |
| int defineTemporaryLocalVariable(final int width) { |
| final int fromSlot = getUsedSlotsWithLiveTemporaries(); |
| defineLocalVariable(fromSlot, fromSlot + width); |
| return fromSlot; |
| } |
| |
| /** |
| * Marks a range of slots as belonging to a defined temporary local variable. The slots will start out with no |
| * live value in them. |
| * @param fromSlot first slot, inclusive. |
| * @param toSlot last slot, exclusive. |
| */ |
| void defineTemporaryLocalVariable(final int fromSlot, final int toSlot) { |
| defineLocalVariable(fromSlot, toSlot); |
| } |
| |
| private void defineLocalVariable(final int fromSlot, final int toSlot) { |
| assert !hasLoadsOnStack(fromSlot, toSlot); |
| assert fromSlot < toSlot; |
| symbolBoundary.clear(fromSlot, toSlot - 1); |
| symbolBoundary.set(toSlot - 1); |
| final int lastExisting = Math.min(toSlot, localVariableTypes.size()); |
| for(int i = fromSlot; i < lastExisting; ++i) { |
| localVariableTypes.set(i, Type.UNKNOWN); |
| } |
| for(int i = lastExisting; i < toSlot; ++i) { |
| localVariableTypes.add(i, Type.UNKNOWN); |
| } |
| } |
| |
| /** |
| * Undefines all local variables past the specified slot. |
| * @param fromSlot the first slot to be undefined |
| * @param canTruncateSymbol if false, the fromSlot must be either the first slot of a symbol, or the first slot |
| * after the last symbol. If true, the fromSlot can be in the middle of the storage area for a symbol. This |
| * should be used with care - it is only meant for use in optimism exception handlers. |
| */ |
| void undefineLocalVariables(final int fromSlot, final boolean canTruncateSymbol) { |
| final int lvarCount = localVariableTypes.size(); |
| assert lvarCount == symbolBoundary.length(); |
| assert !hasLoadsOnStack(fromSlot, lvarCount); |
| if(canTruncateSymbol) { |
| if(fromSlot > 0) { |
| symbolBoundary.set(fromSlot - 1); |
| } |
| } else { |
| assert fromSlot == 0 || symbolBoundary.get(fromSlot - 1); |
| } |
| if(fromSlot < lvarCount) { |
| symbolBoundary.clear(fromSlot, lvarCount); |
| localVariableTypes.subList(fromSlot, lvarCount).clear(); |
| } |
| firstTemp = Math.min(fromSlot, firstTemp); |
| assert symbolBoundary.length() == localVariableTypes.size(); |
| assert symbolBoundary.length() == fromSlot; |
| } |
| |
| private void markAsOptimisticCatchHandler(final int liveLocalCount) { |
| // Live temporaries that are no longer on stack are undefined |
| undefineLocalVariables(liveLocalCount, true); |
| // Temporaries are promoted |
| firstTemp = liveLocalCount; |
| // No trailing undefined values |
| localVariableTypes.subList(firstTemp, localVariableTypes.size()).clear(); |
| assert symbolBoundary.length() == firstTemp; |
| // Generalize all reference types to Object, and promote boolean to int |
| for(final ListIterator<Type> it = localVariableTypes.listIterator(); it.hasNext();) { |
| final Type type = it.next(); |
| if(type == Type.BOOLEAN) { |
| it.set(Type.INT); |
| } else if(type.isObject() && type != Type.OBJECT) { |
| it.set(Type.OBJECT); |
| } |
| } |
| } |
| |
| /** |
| * Returns true if any loads on the stack come from the specified slot range. |
| * @param fromSlot start of the range (inclusive) |
| * @param toSlot end of the range (exclusive) |
| * @return true if any loads on the stack come from the specified slot range. |
| */ |
| boolean hasLoadsOnStack(final int fromSlot, final int toSlot) { |
| for(int i = 0; i < sp; ++i) { |
| final int load = localLoads[i]; |
| if(load >= fromSlot && load < toSlot) { |
| return true; |
| } |
| } |
| return false; |
| } |
| |
| @Override |
| public String toString() { |
| return "stack=" + Arrays.toString(Arrays.copyOf(data, sp)) |
| + ", symbolBoundaries=" + String.valueOf(symbolBoundary) |
| + ", firstTemp=" + firstTemp |
| + ", localTypes=" + String.valueOf(localVariableTypes) |
| ; |
| } |
| } |
| |
| /** Next id for debugging purposes, remove if footprint becomes unmanageable */ |
| private static int nextId = 0; |
| |
| /** Name of this label */ |
| private final String name; |
| |
| /** Type stack at this label */ |
| private transient Label.Stack stack; |
| |
| /** ASM representation of this label */ |
| private transient jdk.internal.org.objectweb.asm.Label label; |
| |
| /** Id for debugging purposes, remove if footprint becomes unmanageable */ |
| private final int id; |
| |
| /** Is this label reachable (anything ever jumped to it)? */ |
| private transient boolean reachable; |
| |
| private transient boolean breakTarget; |
| |
| /** |
| * Constructor |
| * |
| * @param name name of this label |
| */ |
| public Label(final String name) { |
| super(); |
| this.name = name; |
| this.id = nextId++; |
| } |
| |
| /** |
| * Copy constructor |
| * |
| * @param label a label to clone |
| */ |
| public Label(final Label label) { |
| super(); |
| this.name = label.name; |
| this.id = label.id; |
| } |
| |
| jdk.internal.org.objectweb.asm.Label getLabel() { |
| if (this.label == null) { |
| this.label = new jdk.internal.org.objectweb.asm.Label(); |
| } |
| return label; |
| } |
| |
| Label.Stack getStack() { |
| return stack; |
| } |
| |
| void joinFrom(final Label.Stack joinOrigin) { |
| this.reachable = true; |
| if(stack == null) { |
| stack = joinOrigin.clone(); |
| } else { |
| stack.joinFrom(joinOrigin, breakTarget); |
| } |
| } |
| |
| void joinFromTry(final Label.Stack joinOrigin, final boolean isOptimismHandler) { |
| this.reachable = true; |
| if (stack == null) { |
| if(!isOptimismHandler) { |
| stack = joinOrigin.cloneWithEmptyStack(); |
| // Optimism handler needs temporaries to remain live, others don't. |
| stack.undefineLocalVariables(stack.firstTemp, false); |
| } |
| } else { |
| assert !isOptimismHandler; |
| stack.joinFromTry(joinOrigin); |
| } |
| } |
| |
| void markAsBreakTarget() { |
| breakTarget = true; |
| } |
| |
| boolean isBreakTarget() { |
| return breakTarget; |
| } |
| |
| void onCatch() { |
| if(stack != null) { |
| stack = stack.cloneWithEmptyStack(); |
| } |
| } |
| void markAsOptimisticCatchHandler(final Label.Stack currentStack, final int liveLocalCount) { |
| stack = currentStack.cloneWithEmptyStack(); |
| stack.markAsOptimisticCatchHandler(liveLocalCount); |
| } |
| |
| void markAsOptimisticContinuationHandlerFor(final Label afterConsumeStackLabel) { |
| stack = afterConsumeStackLabel.stack.cloneWithEmptyStack(); |
| } |
| |
| boolean isReachable() { |
| return reachable; |
| } |
| |
| boolean isAfter(final Label other) { |
| return label.getOffset() > other.label.getOffset(); |
| } |
| |
| private String str; |
| |
| @Override |
| public String toString() { |
| if (str == null) { |
| str = name + '_' + id; |
| } |
| return str; |
| } |
| } |