# HG changeset patch # User Josef Eisl # Date 1441101794 -7200 # Node ID d988ba58a53546ae2bc71d5454db0b4ae435f183 # Parent 71ca282ae653c130ac7a678010d291a65b50a643 TraceRA: rename trace.Interval to trace.TraceInterval. diff -r 71ca282ae653 -r d988ba58a535 graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/Interval.java --- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/Interval.java Tue Sep 01 11:49:35 2015 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,1304 +0,0 @@ -/* - * Copyright (c) 2009, 2014, 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. - * - * 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 com.oracle.graal.lir.alloc.trace; - -import static com.oracle.graal.compiler.common.GraalOptions.*; -import static com.oracle.graal.lir.LIRValueUtil.*; -import static jdk.internal.jvmci.code.ValueUtil.*; - -import java.util.*; - -import jdk.internal.jvmci.code.*; -import jdk.internal.jvmci.common.*; -import jdk.internal.jvmci.meta.*; - -import com.oracle.graal.compiler.common.util.*; -import com.oracle.graal.debug.*; -import com.oracle.graal.lir.*; - -/** - * Represents an interval in the {@linkplain TraceLinearScan linear scan register allocator}. - */ -final class Interval { - - /** - * A pair of intervals. - */ - static final class Pair { - - public final Interval first; - public final Interval second; - - public Pair(Interval first, Interval second) { - this.first = first; - this.second = second; - } - } - - /** - * A set of interval lists, one per {@linkplain RegisterBinding binding} type. - */ - static final class RegisterBindingLists { - - /** - * List of intervals whose binding is currently {@link RegisterBinding#Fixed}. - */ - public Interval fixed; - - /** - * List of intervals whose binding is currently {@link RegisterBinding#Any}. - */ - public Interval any; - - /** - * List of intervals whose binding is currently {@link RegisterBinding#Stack}. - */ - public Interval stack; - - public RegisterBindingLists(Interval fixed, Interval any, Interval stack) { - this.fixed = fixed; - this.any = any; - this.stack = stack; - } - - /** - * Gets the list for a specified binding. - * - * @param binding specifies the list to be returned - * @return the list of intervals whose binding is {@code binding} - */ - public Interval get(RegisterBinding binding) { - switch (binding) { - case Any: - return any; - case Fixed: - return fixed; - case Stack: - return stack; - } - throw JVMCIError.shouldNotReachHere(); - } - - /** - * Sets the list for a specified binding. - * - * @param binding specifies the list to be replaced - * @param list a list of intervals whose binding is {@code binding} - */ - public void set(RegisterBinding binding, Interval list) { - assert list != null; - switch (binding) { - case Any: - any = list; - break; - case Fixed: - fixed = list; - break; - case Stack: - stack = list; - break; - } - } - - /** - * Adds an interval to a list sorted by {@linkplain Interval#currentFrom() current from} - * positions. - * - * @param binding specifies the list to be updated - * @param interval the interval to add - */ - public void addToListSortedByCurrentFromPositions(RegisterBinding binding, Interval interval) { - Interval list = get(binding); - Interval prev = null; - Interval cur = list; - while (cur.currentFrom() < interval.currentFrom()) { - prev = cur; - cur = cur.next; - } - Interval result = list; - if (prev == null) { - // add to head of list - result = interval; - } else { - // add before 'cur' - prev.next = interval; - } - interval.next = cur; - set(binding, result); - } - - /** - * Adds an interval to a list sorted by {@linkplain Interval#from() start} positions and - * {@linkplain Interval#firstUsage(RegisterPriority) first usage} positions. - * - * @param binding specifies the list to be updated - * @param interval the interval to add - */ - public void addToListSortedByStartAndUsePositions(RegisterBinding binding, Interval interval) { - Interval list = get(binding); - Interval prev = null; - Interval cur = list; - while (cur.from() < interval.from() || (cur.from() == interval.from() && cur.firstUsage(RegisterPriority.None) < interval.firstUsage(RegisterPriority.None))) { - prev = cur; - cur = cur.next; - } - if (prev == null) { - list = interval; - } else { - prev.next = interval; - } - interval.next = cur; - set(binding, list); - } - - /** - * Removes an interval from a list. - * - * @param binding specifies the list to be updated - * @param i the interval to remove - */ - public void remove(RegisterBinding binding, Interval i) { - Interval list = get(binding); - Interval prev = null; - Interval cur = list; - while (cur != i) { - assert cur != null && cur != Interval.EndMarker : "interval has not been found in list: " + i; - prev = cur; - cur = cur.next; - } - if (prev == null) { - set(binding, cur.next); - } else { - prev.next = cur.next; - } - } - } - - /** - * Constants denoting the register usage priority for an interval. The constants are declared in - * increasing order of priority are are used to optimize spilling when multiple overlapping - * intervals compete for limited registers. - */ - public enum RegisterPriority { - /** - * No special reason for an interval to be allocated a register. - */ - None, - - /** - * Priority level for intervals live at the end of a loop. - */ - LiveAtLoopEnd, - - /** - * Priority level for intervals that should be allocated to a register. - */ - ShouldHaveRegister, - - /** - * Priority level for intervals that must be allocated to a register. - */ - MustHaveRegister; - - public static final RegisterPriority[] VALUES = values(); - - /** - * Determines if this priority is higher than or equal to a given priority. - */ - public boolean greaterEqual(RegisterPriority other) { - return ordinal() >= other.ordinal(); - } - - /** - * Determines if this priority is lower than a given priority. - */ - public boolean lessThan(RegisterPriority other) { - return ordinal() < other.ordinal(); - } - } - - /** - * Constants denoting whether an interval is bound to a specific register. This models platform - * dependencies on register usage for certain instructions. - */ - enum RegisterBinding { - /** - * Interval is bound to a specific register as required by the platform. - */ - Fixed, - - /** - * Interval has no specific register requirements. - */ - Any, - - /** - * Interval is bound to a stack slot. - */ - Stack; - - public static final RegisterBinding[] VALUES = values(); - } - - /** - * Constants denoting the linear-scan states an interval may be in with respect to the - * {@linkplain Interval#from() start} {@code position} of the interval being processed. - */ - enum State { - /** - * An interval that starts after {@code position}. - */ - Unhandled, - - /** - * An interval that {@linkplain Interval#covers covers} {@code position} and has an assigned - * register. - */ - Active, - - /** - * An interval that starts before and ends after {@code position} but does not - * {@linkplain Interval#covers cover} it due to a lifetime hole. - */ - Inactive, - - /** - * An interval that ends before {@code position} or is spilled to memory. - */ - Handled; - } - - /** - * Constants used in optimization of spilling of an interval. - */ - public enum SpillState { - /** - * Starting state of calculation: no definition found yet. - */ - NoDefinitionFound, - - /** - * One definition has already been found. Two consecutive definitions are treated as one - * (e.g. a consecutive move and add because of two-operand LIR form). The position of this - * definition is given by {@link Interval#spillDefinitionPos()}. - */ - NoSpillStore, - - /** - * One spill move has already been inserted. - */ - OneSpillStore, - - /** - * The interval is spilled multiple times or is spilled in a loop. Place the store somewhere - * on the dominator path between the definition and the usages. - */ - SpillInDominator, - - /** - * The interval should be stored immediately after its definition to prevent multiple - * redundant stores. - */ - StoreAtDefinition, - - /** - * The interval starts in memory (e.g. method parameter), so a store is never necessary. - */ - StartInMemory, - - /** - * The interval has more than one definition (e.g. resulting from phi moves), so stores to - * memory are not optimized. - */ - NoOptimization - } - - /** - * List of use positions. Each entry in the list records the use position and register priority - * associated with the use position. The entries in the list are in descending order of use - * position. - * - */ - public static final class UsePosList { - - private IntList list; - - /** - * Creates a use list. - * - * @param initialCapacity the initial capacity of the list in terms of entries - */ - public UsePosList(int initialCapacity) { - list = new IntList(initialCapacity * 2); - } - - private UsePosList(IntList list) { - this.list = list; - } - - /** - * Splits this list around a given position. All entries in this list with a use position - * greater or equal than {@code splitPos} are removed from this list and added to the - * returned list. - * - * @param splitPos the position for the split - * @return a use position list containing all entries removed from this list that have a use - * position greater or equal than {@code splitPos} - */ - public UsePosList splitAt(int splitPos) { - int i = size() - 1; - int len = 0; - while (i >= 0 && usePos(i) < splitPos) { - --i; - len += 2; - } - int listSplitIndex = (i + 1) * 2; - IntList childList = list; - list = IntList.copy(this.list, listSplitIndex, len); - childList.setSize(listSplitIndex); - UsePosList child = new UsePosList(childList); - return child; - } - - /** - * Gets the use position at a specified index in this list. - * - * @param index the index of the entry for which the use position is returned - * @return the use position of entry {@code index} in this list - */ - public int usePos(int index) { - return list.get(index << 1); - } - - /** - * Gets the register priority for the use position at a specified index in this list. - * - * @param index the index of the entry for which the register priority is returned - * @return the register priority of entry {@code index} in this list - */ - public RegisterPriority registerPriority(int index) { - return RegisterPriority.VALUES[list.get((index << 1) + 1)]; - } - - public void add(int usePos, RegisterPriority registerPriority) { - assert list.size() == 0 || usePos(size() - 1) > usePos; - list.add(usePos); - list.add(registerPriority.ordinal()); - } - - public int size() { - return list.size() >> 1; - } - - public void removeLowestUsePos() { - list.setSize(list.size() - 2); - } - - public void setRegisterPriority(int index, RegisterPriority registerPriority) { - list.set((index << 1) + 1, registerPriority.ordinal()); - } - - @Override - public String toString() { - StringBuilder buf = new StringBuilder("["); - for (int i = size() - 1; i >= 0; --i) { - if (buf.length() != 1) { - buf.append(", "); - } - RegisterPriority prio = registerPriority(i); - buf.append(usePos(i)).append(" -> ").append(prio.ordinal()).append(':').append(prio); - } - return buf.append("]").toString(); - } - } - - /** - * The {@linkplain RegisterValue register} or {@linkplain Variable variable} for this interval - * prior to register allocation. - */ - public final AllocatableValue operand; - - /** - * The operand number for this interval's {@linkplain #operand operand}. - */ - public final int operandNumber; - - /** - * The {@linkplain RegisterValue register} or {@linkplain StackSlot spill slot} assigned to this - * interval. In case of a spilled interval which is re-materialized this is - * {@link Value#ILLEGAL}. - */ - private AllocatableValue location; - - /** - * The stack slot to which all splits of this interval are spilled if necessary. - */ - private StackSlotValue spillSlot; - - /** - * The kind of this interval. - */ - private LIRKind kind; - - /** - * The head of the list of ranges describing this interval. This list is sorted by - * {@linkplain LIRInstruction#id instruction ids}. - */ - private Range first; - - /** - * List of (use-positions, register-priorities) pairs, sorted by use-positions. - */ - private UsePosList usePosList; - - /** - * Iterator used to traverse the ranges of an interval. - */ - private Range current; - - /** - * Link to next interval in a sorted list of intervals that ends with {@link #EndMarker}. - */ - Interval next; - - /** - * The linear-scan state of this interval. - */ - State state; - - private int cachedTo; // cached value: to of last range (-1: not cached) - - /** - * The interval from which this one is derived. If this is a {@linkplain #isSplitParent() split - * parent}, it points to itself. - */ - private Interval splitParent; - - /** - * List of all intervals that are split off from this interval. This is only used if this is a - * {@linkplain #isSplitParent() split parent}. - */ - private List splitChildren = Collections.emptyList(); - - /** - * Current split child that has been active or inactive last (always stored in split parents). - */ - private Interval currentSplitChild; - - /** - * Specifies if move is inserted between currentSplitChild and this interval when interval gets - * active the first time. - */ - private boolean insertMoveWhenActivated; - - /** - * For spill move optimization. - */ - private SpillState spillState; - - /** - * Position where this interval is defined (if defined only once). - */ - private int spillDefinitionPos; - - /** - * This interval should be assigned the same location as the hint interval. - */ - private Interval locationHint; - - /** - * The value with which a spilled child interval can be re-materialized. Currently this must be - * a Constant. - */ - private JavaConstant materializedValue; - - /** - * The number of times {@link #addMaterializationValue(JavaConstant)} is called. - */ - private int numMaterializationValuesAdded; - - void assignLocation(AllocatableValue newLocation) { - if (isRegister(newLocation)) { - assert this.location == null : "cannot re-assign location for " + this; - if (newLocation.getLIRKind().equals(LIRKind.Illegal) && !kind.equals(LIRKind.Illegal)) { - this.location = asRegister(newLocation).asValue(kind); - return; - } - } else if (isIllegal(newLocation)) { - assert canMaterialize(); - } else { - assert this.location == null || isRegister(this.location) || (isVirtualStackSlot(this.location) && isStackSlot(newLocation)) : "cannot re-assign location for " + this; - assert isStackSlotValue(newLocation); - assert !newLocation.getLIRKind().equals(LIRKind.Illegal); - assert newLocation.getLIRKind().equals(this.kind); - } - this.location = newLocation; - } - - /** - * Gets the {@linkplain RegisterValue register} or {@linkplain StackSlot spill slot} assigned to - * this interval. - */ - public AllocatableValue location() { - return location; - } - - public LIRKind kind() { - assert !isRegister(operand) : "cannot access type for fixed interval"; - return kind; - } - - public void setKind(LIRKind kind) { - assert isRegister(operand) || this.kind().equals(LIRKind.Illegal) || this.kind().equals(kind) : "overwriting existing type"; - this.kind = kind; - } - - public Range first() { - return first; - } - - public int from() { - return first.from; - } - - int to() { - if (cachedTo == -1) { - cachedTo = calcTo(); - } - assert cachedTo == calcTo() : "invalid cached value"; - return cachedTo; - } - - int numUsePositions() { - return usePosList.size(); - } - - public void setLocationHint(Interval interval) { - locationHint = interval; - } - - public boolean isSplitParent() { - return splitParent == this; - } - - boolean isSplitChild() { - return splitParent != this; - } - - /** - * Gets the split parent for this interval. - */ - public Interval splitParent() { - assert splitParent.isSplitParent() : "not a split parent: " + this; - return splitParent; - } - - /** - * Gets the canonical spill slot for this interval. - */ - public StackSlotValue spillSlot() { - return splitParent().spillSlot; - } - - public void setSpillSlot(StackSlotValue slot) { - assert splitParent().spillSlot == null || (isVirtualStackSlot(splitParent().spillSlot) && isStackSlot(slot)) : "connot overwrite existing spill slot"; - splitParent().spillSlot = slot; - } - - Interval currentSplitChild() { - return splitParent().currentSplitChild; - } - - void makeCurrentSplitChild() { - splitParent().currentSplitChild = this; - } - - boolean insertMoveWhenActivated() { - return insertMoveWhenActivated; - } - - void setInsertMoveWhenActivated(boolean b) { - insertMoveWhenActivated = b; - } - - // for spill optimization - public SpillState spillState() { - return splitParent().spillState; - } - - public int spillDefinitionPos() { - return splitParent().spillDefinitionPos; - } - - public void setSpillState(SpillState state) { - assert state.ordinal() >= spillState().ordinal() : "state cannot decrease"; - splitParent().spillState = state; - } - - public void setSpillDefinitionPos(int pos) { - assert spillState() == SpillState.SpillInDominator || spillState() == SpillState.NoDefinitionFound || spillDefinitionPos() == -1 : "cannot set the position twice"; - splitParent().spillDefinitionPos = pos; - } - - // returns true if this interval has a shadow copy on the stack that is always correct - public boolean alwaysInMemory() { - return (splitParent().spillState == SpillState.SpillInDominator || splitParent().spillState == SpillState.StoreAtDefinition || splitParent().spillState == SpillState.StartInMemory) && - !canMaterialize(); - } - - void removeFirstUsePos() { - usePosList.removeLowestUsePos(); - } - - // test intersection - boolean intersects(Interval i) { - return first.intersects(i.first); - } - - int intersectsAt(Interval i) { - return first.intersectsAt(i.first); - } - - // range iteration - void rewindRange() { - current = first; - } - - void nextRange() { - assert this != EndMarker : "not allowed on sentinel"; - current = current.next; - } - - int currentFrom() { - return current.from; - } - - int currentTo() { - return current.to; - } - - boolean currentAtEnd() { - return current == Range.EndMarker; - } - - boolean currentIntersects(Interval it) { - return current.intersects(it.current); - } - - int currentIntersectsAt(Interval it) { - return current.intersectsAt(it.current); - } - - /** - * Sentinel interval to denote the end of an interval list. - */ - static final Interval EndMarker = new Interval(Value.ILLEGAL, -1); - - Interval(AllocatableValue operand, int operandNumber) { - assert operand != null; - this.operand = operand; - this.operandNumber = operandNumber; - if (isRegister(operand)) { - location = operand; - } else { - assert isIllegal(operand) || isVariable(operand); - } - this.kind = LIRKind.Illegal; - this.first = Range.EndMarker; - this.usePosList = new UsePosList(4); - this.current = Range.EndMarker; - this.next = EndMarker; - this.cachedTo = -1; - this.spillState = SpillState.NoDefinitionFound; - this.spillDefinitionPos = -1; - splitParent = this; - currentSplitChild = this; - } - - /** - * Sets the value which is used for re-materialization. - */ - public void addMaterializationValue(JavaConstant value) { - if (numMaterializationValuesAdded == 0) { - materializedValue = value; - } else { - // Interval is defined on multiple places -> no materialization is possible. - materializedValue = null; - } - numMaterializationValuesAdded++; - } - - /** - * Returns true if this interval can be re-materialized when spilled. This means that no - * spill-moves are needed. Instead of restore-moves the {@link #materializedValue} is restored. - */ - public boolean canMaterialize() { - return getMaterializedValue() != null; - } - - /** - * Returns a value which can be moved to a register instead of a restore-move from stack. - */ - public JavaConstant getMaterializedValue() { - return splitParent().materializedValue; - } - - int calcTo() { - assert first != Range.EndMarker : "interval has no range"; - - Range r = first; - while (r.next != Range.EndMarker) { - r = r.next; - } - return r.to; - } - - // consistency check of split-children - boolean checkSplitChildren() { - if (!splitChildren.isEmpty()) { - assert isSplitParent() : "only split parents can have children"; - - for (int i = 0; i < splitChildren.size(); i++) { - Interval i1 = splitChildren.get(i); - - assert i1.splitParent() == this : "not a split child of this interval"; - assert i1.kind().equals(kind()) : "must be equal for all split children"; - assert (i1.spillSlot() == null && spillSlot == null) || i1.spillSlot().equals(spillSlot()) : "must be equal for all split children"; - - for (int j = i + 1; j < splitChildren.size(); j++) { - Interval i2 = splitChildren.get(j); - - assert !i1.operand.equals(i2.operand) : "same register number"; - - if (i1.from() < i2.from()) { - assert i1.to() <= i2.from() && i1.to() < i2.to() : "intervals overlapping"; - } else { - assert i2.from() < i1.from() : "intervals start at same opId"; - assert i2.to() <= i1.from() && i2.to() < i1.to() : "intervals overlapping"; - } - } - } - } - - return true; - } - - public Interval locationHint(boolean searchSplitChild) { - if (!searchSplitChild) { - return locationHint; - } - - if (locationHint != null) { - assert locationHint.isSplitParent() : "ony split parents are valid hint registers"; - - if (locationHint.location != null && isRegister(locationHint.location)) { - return locationHint; - } else if (!locationHint.splitChildren.isEmpty()) { - // search the first split child that has a register assigned - int len = locationHint.splitChildren.size(); - for (int i = 0; i < len; i++) { - Interval interval = locationHint.splitChildren.get(i); - if (interval.location != null && isRegister(interval.location)) { - return interval; - } - } - } - } - - // no hint interval found that has a register assigned - return null; - } - - Interval getSplitChildAtOpId(int opId, LIRInstruction.OperandMode mode, TraceLinearScan allocator) { - assert isSplitParent() : "can only be called for split parents"; - assert opId >= 0 : "invalid opId (method cannot be called for spill moves)"; - - if (splitChildren.isEmpty()) { - assert this.covers(opId, mode) : this + " does not cover " + opId; - return this; - } else { - Interval result = null; - int len = splitChildren.size(); - - // in outputMode, the end of the interval (opId == cur.to()) is not valid - int toOffset = (mode == LIRInstruction.OperandMode.DEF ? 0 : 1); - - int i; - for (i = 0; i < len; i++) { - Interval cur = splitChildren.get(i); - if (cur.from() <= opId && opId < cur.to() + toOffset) { - if (i > 0) { - // exchange current split child to start of list (faster access for next - // call) - Util.atPutGrow(splitChildren, i, splitChildren.get(0), null); - Util.atPutGrow(splitChildren, 0, cur, null); - } - - // interval found - result = cur; - break; - } - } - - assert checkSplitChild(result, opId, allocator, toOffset, mode); - return result; - } - } - - private boolean checkSplitChild(Interval result, int opId, TraceLinearScan allocator, int toOffset, LIRInstruction.OperandMode mode) { - if (result == null) { - // this is an error - StringBuilder msg = new StringBuilder(this.toString()).append(" has no child at ").append(opId); - if (!splitChildren.isEmpty()) { - Interval firstChild = splitChildren.get(0); - Interval lastChild = splitChildren.get(splitChildren.size() - 1); - msg.append(" (first = ").append(firstChild).append(", last = ").append(lastChild).append(")"); - } - throw new JVMCIError("Linear Scan Error: %s", msg); - } - - if (!splitChildren.isEmpty()) { - for (Interval interval : splitChildren) { - if (interval != result && interval.from() <= opId && opId < interval.to() + toOffset) { - TTY.println(String.format("two valid result intervals found for opId %d: %d and %d", opId, result.operandNumber, interval.operandNumber)); - TTY.println(result.logString(allocator)); - TTY.println(interval.logString(allocator)); - throw new BailoutException("two valid result intervals found"); - } - } - } - assert result.covers(opId, mode) : "opId not covered by interval"; - return true; - } - - // returns the interval that covers the given opId or null if there is none - Interval getIntervalCoveringOpId(int opId) { - assert opId >= 0 : "invalid opId"; - assert opId < to() : "can only look into the past"; - - if (opId >= from()) { - return this; - } - - Interval parent = splitParent(); - Interval result = null; - - assert !parent.splitChildren.isEmpty() : "no split children available"; - int len = parent.splitChildren.size(); - - for (int i = len - 1; i >= 0; i--) { - Interval cur = parent.splitChildren.get(i); - if (cur.from() <= opId && opId < cur.to()) { - assert result == null : "covered by multiple split children " + result + " and " + cur; - result = cur; - } - } - - return result; - } - - // returns the last split child that ends before the given opId - Interval getSplitChildBeforeOpId(int opId) { - assert opId >= 0 : "invalid opId"; - - Interval parent = splitParent(); - Interval result = null; - - assert !parent.splitChildren.isEmpty() : "no split children available"; - int len = parent.splitChildren.size(); - - for (int i = len - 1; i >= 0; i--) { - Interval cur = parent.splitChildren.get(i); - if (cur.to() <= opId && (result == null || result.to() < cur.to())) { - result = cur; - } - } - - assert result != null : "no split child found"; - return result; - } - - // checks if opId is covered by any split child - boolean splitChildCovers(int opId, LIRInstruction.OperandMode mode) { - assert isSplitParent() : "can only be called for split parents"; - assert opId >= 0 : "invalid opId (method can not be called for spill moves)"; - - if (splitChildren.isEmpty()) { - // simple case if interval was not split - return covers(opId, mode); - - } else { - // extended case: check all split children - int len = splitChildren.size(); - for (int i = 0; i < len; i++) { - Interval cur = splitChildren.get(i); - if (cur.covers(opId, mode)) { - return true; - } - } - return false; - } - } - - private RegisterPriority adaptPriority(RegisterPriority priority) { - /* - * In case of re-materialized values we require that use-operands are registers, because we - * don't have the value in a stack location. (Note that ShouldHaveRegister means that the - * operand can also be a StackSlot). - */ - if (priority == RegisterPriority.ShouldHaveRegister && canMaterialize()) { - return RegisterPriority.MustHaveRegister; - } - return priority; - } - - // Note: use positions are sorted descending . first use has highest index - int firstUsage(RegisterPriority minRegisterPriority) { - assert isVariable(operand) : "cannot access use positions for fixed intervals"; - - for (int i = usePosList.size() - 1; i >= 0; --i) { - RegisterPriority registerPriority = adaptPriority(usePosList.registerPriority(i)); - if (registerPriority.greaterEqual(minRegisterPriority)) { - return usePosList.usePos(i); - } - } - return Integer.MAX_VALUE; - } - - int nextUsage(RegisterPriority minRegisterPriority, int from) { - assert isVariable(operand) : "cannot access use positions for fixed intervals"; - - for (int i = usePosList.size() - 1; i >= 0; --i) { - int usePos = usePosList.usePos(i); - if (usePos >= from && adaptPriority(usePosList.registerPriority(i)).greaterEqual(minRegisterPriority)) { - return usePos; - } - } - return Integer.MAX_VALUE; - } - - int nextUsageExact(RegisterPriority exactRegisterPriority, int from) { - assert isVariable(operand) : "cannot access use positions for fixed intervals"; - - for (int i = usePosList.size() - 1; i >= 0; --i) { - int usePos = usePosList.usePos(i); - if (usePos >= from && adaptPriority(usePosList.registerPriority(i)) == exactRegisterPriority) { - return usePos; - } - } - return Integer.MAX_VALUE; - } - - int previousUsage(RegisterPriority minRegisterPriority, int from) { - assert isVariable(operand) : "cannot access use positions for fixed intervals"; - - int prev = -1; - for (int i = usePosList.size() - 1; i >= 0; --i) { - int usePos = usePosList.usePos(i); - if (usePos > from) { - return prev; - } - if (adaptPriority(usePosList.registerPriority(i)).greaterEqual(minRegisterPriority)) { - prev = usePos; - } - } - return prev; - } - - public void addUsePos(int pos, RegisterPriority registerPriority) { - assert covers(pos, LIRInstruction.OperandMode.USE) : String.format("use position %d not covered by live range of interval %s", pos, this); - - // do not add use positions for precolored intervals because they are never used - if (registerPriority != RegisterPriority.None && isVariable(operand)) { - if (DetailedAsserts.getValue()) { - for (int i = 0; i < usePosList.size(); i++) { - assert pos <= usePosList.usePos(i) : "already added a use-position with lower position"; - if (i > 0) { - assert usePosList.usePos(i) < usePosList.usePos(i - 1) : "not sorted descending"; - } - } - } - - // Note: addUse is called in descending order, so list gets sorted - // automatically by just appending new use positions - int len = usePosList.size(); - if (len == 0 || usePosList.usePos(len - 1) > pos) { - usePosList.add(pos, registerPriority); - } else if (usePosList.registerPriority(len - 1).lessThan(registerPriority)) { - assert usePosList.usePos(len - 1) == pos : "list not sorted correctly"; - usePosList.setRegisterPriority(len - 1, registerPriority); - } - } - } - - public void addRange(int from, int to) { - assert from < to : "invalid range"; - assert first() == Range.EndMarker || to < first().next.from : "not inserting at begin of interval"; - assert from <= first().to : "not inserting at begin of interval"; - - if (first.from <= to) { - assert first != Range.EndMarker; - // join intersecting ranges - first.from = Math.min(from, first().from); - first.to = Math.max(to, first().to); - } else { - // insert new range - first = new Range(from, to, first()); - } - } - - Interval newSplitChild(TraceLinearScan allocator) { - // allocate new interval - Interval parent = splitParent(); - Interval result = allocator.createDerivedInterval(parent); - result.setKind(kind()); - - result.splitParent = parent; - result.setLocationHint(parent); - - // insert new interval in children-list of parent - if (parent.splitChildren.isEmpty()) { - assert isSplitParent() : "list must be initialized at first split"; - - // Create new non-shared list - parent.splitChildren = new ArrayList<>(4); - parent.splitChildren.add(this); - } - parent.splitChildren.add(result); - - return result; - } - - /** - * Splits this interval at a specified position and returns the remainder as a new child - * interval of this interval's {@linkplain #splitParent() parent} interval. - *

- * When an interval is split, a bi-directional link is established between the original - * parent interval and the children intervals that are split off this interval. - * When a split child is split again, the new created interval is a direct child of the original - * parent. That is, there is no tree of split children stored, just a flat list. All split - * children are spilled to the same {@linkplain #spillSlot spill slot}. - * - * @param splitPos the position at which to split this interval - * @param allocator the register allocator context - * @return the child interval split off from this interval - */ - Interval split(int splitPos, TraceLinearScan allocator) { - assert isVariable(operand) : "cannot split fixed intervals"; - - // allocate new interval - Interval result = newSplitChild(allocator); - - // split the ranges - Range prev = null; - Range cur = first; - while (cur != Range.EndMarker && cur.to <= splitPos) { - prev = cur; - cur = cur.next; - } - assert cur != Range.EndMarker : "split interval after end of last range"; - - if (cur.from < splitPos) { - result.first = new Range(splitPos, cur.to, cur.next); - cur.to = splitPos; - cur.next = Range.EndMarker; - - } else { - assert prev != null : "split before start of first range"; - result.first = cur; - prev.next = Range.EndMarker; - } - result.current = result.first; - cachedTo = -1; // clear cached value - - // split list of use positions - result.usePosList = usePosList.splitAt(splitPos); - - if (DetailedAsserts.getValue()) { - for (int i = 0; i < usePosList.size(); i++) { - assert usePosList.usePos(i) < splitPos; - } - for (int i = 0; i < result.usePosList.size(); i++) { - assert result.usePosList.usePos(i) >= splitPos; - } - } - return result; - } - - /** - * Splits this interval at a specified position and returns the head as a new interval (this - * interval is the tail). - * - * Currently, only the first range can be split, and the new interval must not have split - * positions - */ - Interval splitFromStart(int splitPos, TraceLinearScan allocator) { - assert isVariable(operand) : "cannot split fixed intervals"; - assert splitPos > from() && splitPos < to() : "can only split inside interval"; - assert splitPos > first.from && splitPos <= first.to : "can only split inside first range"; - assert firstUsage(RegisterPriority.None) > splitPos : "can not split when use positions are present"; - - // allocate new interval - Interval result = newSplitChild(allocator); - - // the new interval has only one range (checked by assertion above, - // so the splitting of the ranges is very simple - result.addRange(first.from, splitPos); - - if (splitPos == first.to) { - assert first.next != Range.EndMarker : "must not be at end"; - first = first.next; - } else { - first.from = splitPos; - } - - return result; - } - - // returns true if the opId is inside the interval - boolean covers(int opId, LIRInstruction.OperandMode mode) { - Range cur = first; - - while (cur != Range.EndMarker && cur.to < opId) { - cur = cur.next; - } - if (cur != Range.EndMarker) { - assert cur.to != cur.next.from : "ranges not separated"; - - if (mode == LIRInstruction.OperandMode.DEF) { - return cur.from <= opId && opId < cur.to; - } else { - return cur.from <= opId && opId <= cur.to; - } - } - return false; - } - - // returns true if the interval has any hole between holeFrom and holeTo - // (even if the hole has only the length 1) - boolean hasHoleBetween(int holeFrom, int holeTo) { - assert holeFrom < holeTo : "check"; - assert from() <= holeFrom && holeTo <= to() : "index out of interval"; - - Range cur = first; - while (cur != Range.EndMarker) { - assert cur.to < cur.next.from : "no space between ranges"; - - // hole-range starts before this range . hole - if (holeFrom < cur.from) { - return true; - - // hole-range completely inside this range . no hole - } else { - if (holeTo <= cur.to) { - return false; - - // overlapping of hole-range with this range . hole - } else { - if (holeFrom <= cur.to) { - return true; - } - } - } - - cur = cur.next; - } - - return false; - } - - @Override - public String toString() { - String from = "?"; - String to = "?"; - if (first != null && first != Range.EndMarker) { - from = String.valueOf(from()); - // to() may cache a computed value, modifying the current object, which is a bad idea - // for a printing function. Compute it directly instead. - to = String.valueOf(calcTo()); - } - String locationString = this.location == null ? "" : "@" + this.location; - return operandNumber + ":" + operand + (isRegister(operand) ? "" : locationString) + "[" + from + "," + to + "]"; - } - - /** - * Gets the use position information for this interval. - */ - public UsePosList usePosList() { - return usePosList; - } - - /** - * Gets a single line string for logging the details of this interval to a log stream. - * - * @param allocator the register allocator context - */ - public String logString(TraceLinearScan allocator) { - StringBuilder buf = new StringBuilder(100); - buf.append(operandNumber).append(':').append(operand).append(' '); - if (!isRegister(operand)) { - if (location != null) { - buf.append("location{").append(location).append("} "); - } - } - - buf.append("hints{").append(splitParent.operandNumber); - Interval hint = locationHint(false); - if (hint != null && hint.operandNumber != splitParent.operandNumber) { - buf.append(", ").append(hint.operandNumber); - } - buf.append("} ranges{"); - - // print ranges - Range cur = first; - while (cur != Range.EndMarker) { - if (cur != first) { - buf.append(", "); - } - buf.append(cur); - cur = cur.next; - assert cur != null : "range list not closed with range sentinel"; - } - buf.append("} uses{"); - - // print use positions - int prev = -1; - for (int i = usePosList.size() - 1; i >= 0; --i) { - assert prev < usePosList.usePos(i) : "use positions not sorted"; - if (i != usePosList.size() - 1) { - buf.append(", "); - } - buf.append(usePosList.usePos(i)).append(':').append(usePosList.registerPriority(i)); - prev = usePosList.usePos(i); - } - buf.append("} spill-state{").append(spillState()).append("}"); - if (canMaterialize()) { - buf.append(" (remat:").append(getMaterializedValue().toString()).append(")"); - } - return buf.toString(); - } - - List getSplitChildren() { - return Collections.unmodifiableList(splitChildren); - } -} diff -r 71ca282ae653 -r d988ba58a535 graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/IntervalWalker.java --- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/IntervalWalker.java Tue Sep 01 11:49:35 2015 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/IntervalWalker.java Tue Sep 01 12:03:14 2015 +0200 @@ -24,9 +24,9 @@ import com.oracle.graal.debug.*; -import com.oracle.graal.lir.alloc.trace.Interval.RegisterBinding; -import com.oracle.graal.lir.alloc.trace.Interval.RegisterBindingLists; -import com.oracle.graal.lir.alloc.trace.Interval.State; +import com.oracle.graal.lir.alloc.trace.TraceInterval.RegisterBinding; +import com.oracle.graal.lir.alloc.trace.TraceInterval.RegisterBindingLists; +import com.oracle.graal.lir.alloc.trace.TraceInterval.State; /** */ @@ -65,7 +65,7 @@ * * @return {@code true} if a register was allocated to the {@code currentInterval} interval */ - protected boolean activateCurrent(@SuppressWarnings({"unused"}) Interval currentInterval) { + protected boolean activateCurrent(@SuppressWarnings({"unused"}) TraceInterval currentInterval) { return true; } @@ -86,16 +86,16 @@ * @param unhandledAny the list of unhandled {@linkplain RegisterBinding#Any non-fixed} * intervals */ - IntervalWalker(TraceLinearScan allocator, Interval unhandledFixed, Interval unhandledAny) { + IntervalWalker(TraceLinearScan allocator, TraceInterval unhandledFixed, TraceInterval unhandledAny) { this.allocator = allocator; - unhandledLists = new RegisterBindingLists(unhandledFixed, unhandledAny, Interval.EndMarker); - activeLists = new RegisterBindingLists(Interval.EndMarker, Interval.EndMarker, Interval.EndMarker); - inactiveLists = new RegisterBindingLists(Interval.EndMarker, Interval.EndMarker, Interval.EndMarker); + unhandledLists = new RegisterBindingLists(unhandledFixed, unhandledAny, TraceInterval.EndMarker); + activeLists = new RegisterBindingLists(TraceInterval.EndMarker, TraceInterval.EndMarker, TraceInterval.EndMarker); + inactiveLists = new RegisterBindingLists(TraceInterval.EndMarker, TraceInterval.EndMarker, TraceInterval.EndMarker); currentPosition = -1; } - protected void removeFromList(Interval interval) { + protected void removeFromList(TraceInterval interval) { if (interval.state == State.Active) { activeLists.remove(RegisterBinding.Any, interval); } else { @@ -112,11 +112,11 @@ } private void walkTo(State state, int from, RegisterBinding binding) { - Interval prevprev = null; - Interval prev = (state == State.Active) ? activeLists.get(binding) : inactiveLists.get(binding); - Interval next = prev; + TraceInterval prevprev = null; + TraceInterval prev = (state == State.Active) ? activeLists.get(binding) : inactiveLists.get(binding); + TraceInterval next = prev; while (next.currentFrom() <= from) { - Interval cur = next; + TraceInterval cur = next; next = cur.next; boolean rangeHasChanged = false; @@ -140,7 +140,7 @@ prevprev.next = next; } prev = next; - Interval.State newState; + TraceInterval.State newState; if (cur.currentAtEnd()) { // move to handled state (not maintained as a list) newState = State.Handled; @@ -179,24 +179,24 @@ * @return The next interval or null if there is no {@linkplain #unhandledLists unhandled} * interval at position {@code toOpId}. */ - private Interval nextInterval(int toOpId) { + private TraceInterval nextInterval(int toOpId) { RegisterBinding binding; - Interval any = unhandledLists.any; - Interval fixed = unhandledLists.fixed; + TraceInterval any = unhandledLists.any; + TraceInterval fixed = unhandledLists.fixed; - if (any != Interval.EndMarker) { + if (any != TraceInterval.EndMarker) { // intervals may start at same position . prefer fixed interval - binding = fixed != Interval.EndMarker && fixed.from() <= any.from() ? RegisterBinding.Fixed : RegisterBinding.Any; + binding = fixed != TraceInterval.EndMarker && fixed.from() <= any.from() ? RegisterBinding.Fixed : RegisterBinding.Any; assert binding == RegisterBinding.Fixed && fixed.from() <= any.from() || binding == RegisterBinding.Any && any.from() <= fixed.from() : "wrong interval!!!"; - assert any == Interval.EndMarker || fixed == Interval.EndMarker || any.from() != fixed.from() || binding == RegisterBinding.Fixed : "if fixed and any-Interval start at same position, fixed must be processed first"; + assert any == TraceInterval.EndMarker || fixed == TraceInterval.EndMarker || any.from() != fixed.from() || binding == RegisterBinding.Fixed : "if fixed and any-Interval start at same position, fixed must be processed first"; - } else if (fixed != Interval.EndMarker) { + } else if (fixed != TraceInterval.EndMarker) { binding = RegisterBinding.Fixed; } else { return null; } - Interval currentInterval = unhandledLists.get(binding); + TraceInterval currentInterval = unhandledLists.get(binding); if (toOpId < currentInterval.from()) { return null; @@ -204,7 +204,7 @@ currentBinding = binding; unhandledLists.set(binding, currentInterval.next); - currentInterval.next = Interval.EndMarker; + currentInterval.next = TraceInterval.EndMarker; currentInterval.rewindRange(); return currentInterval; } @@ -213,12 +213,12 @@ * Walk up to {@code toOpId}. * * @postcondition {@link #currentPosition} is set to {@code toOpId}, {@link #activeLists} and - * {@link #inactiveLists} are populated and {@link Interval#state}s are up to + * {@link #inactiveLists} are populated and {@link TraceInterval#state}s are up to * date. */ protected void walkTo(int toOpId) { assert currentPosition <= toOpId : "can not walk backwards"; - for (Interval currentInterval = nextInterval(toOpId); currentInterval != null; currentInterval = nextInterval(toOpId)) { + for (TraceInterval currentInterval = nextInterval(toOpId); currentInterval != null; currentInterval = nextInterval(toOpId)) { int opId = currentInterval.from(); // set currentPosition prior to call of walkTo @@ -252,7 +252,7 @@ } } - private void intervalMoved(Interval interval, State from, State to) { + private void intervalMoved(TraceInterval interval, State from, State to) { // intervalMoved() is called whenever an interval moves from one interval list to another. // In the implementation of this method it is prohibited to move the interval to any list. if (Debug.isLogEnabled()) { @@ -268,9 +268,9 @@ * any} intervals this is done in {@link #nextInterval(int)}. */ private void updateUnhandledStackIntervals(int opId) { - Interval currentInterval = unhandledLists.get(RegisterBinding.Stack); - while (currentInterval != Interval.EndMarker && currentInterval.from() <= opId) { - Interval next = currentInterval.next; + TraceInterval currentInterval = unhandledLists.get(RegisterBinding.Stack); + while (currentInterval != TraceInterval.EndMarker && currentInterval.from() <= opId) { + TraceInterval next = currentInterval.next; if (currentInterval.to() > opId) { currentInterval.state = State.Active; activeLists.addToListSortedByCurrentFromPositions(RegisterBinding.Stack, currentInterval); diff -r 71ca282ae653 -r d988ba58a535 graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/LinearScanAssignLocationsPhase.java --- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/LinearScanAssignLocationsPhase.java Tue Sep 01 11:49:35 2015 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/LinearScanAssignLocationsPhase.java Tue Sep 01 12:03:14 2015 +0200 @@ -70,7 +70,7 @@ */ protected Value colorLirOperand(LIRInstruction op, Variable operand, OperandMode mode) { int opId = op.id(); - Interval interval = allocator.intervalFor(operand); + TraceInterval interval = allocator.intervalFor(operand); assert interval != null : "interval must exist"; if (opId != -1) { diff -r 71ca282ae653 -r d988ba58a535 graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/LinearScanWalker.java --- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/LinearScanWalker.java Tue Sep 01 11:49:35 2015 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/LinearScanWalker.java Tue Sep 01 12:03:14 2015 +0200 @@ -38,10 +38,10 @@ import com.oracle.graal.lir.*; import com.oracle.graal.lir.StandardOp.ValueMoveOp; import com.oracle.graal.lir.alloc.lsra.*; -import com.oracle.graal.lir.alloc.trace.Interval.RegisterBinding; -import com.oracle.graal.lir.alloc.trace.Interval.RegisterPriority; -import com.oracle.graal.lir.alloc.trace.Interval.SpillState; -import com.oracle.graal.lir.alloc.trace.Interval.State; +import com.oracle.graal.lir.alloc.trace.TraceInterval.RegisterBinding; +import com.oracle.graal.lir.alloc.trace.TraceInterval.RegisterPriority; +import com.oracle.graal.lir.alloc.trace.TraceInterval.SpillState; +import com.oracle.graal.lir.alloc.trace.TraceInterval.State; /** */ @@ -52,7 +52,7 @@ protected final int[] usePos; protected final int[] blockPos; - protected List[] spillIntervals; + protected List[] spillIntervals; private TraceLocalMoveResolver moveResolver; // for ordering spill moves @@ -66,7 +66,7 @@ * bootstrap run of Graal). Therefore, we initialize {@link #spillIntervals} with this marker * value, and allocate a "real" list only on demand in {@link #setUsePos}. */ - private static final List EMPTY_LIST = new ArrayList<>(0); + private static final List EMPTY_LIST = new ArrayList<>(0); // accessors mapped to same functions in class LinearScan int blockCount() { @@ -81,7 +81,7 @@ return allocator.blockForId(opId); } - LinearScanWalker(TraceLinearScan allocator, Interval unhandledFixedFirst, Interval unhandledAnyFirst) { + LinearScanWalker(TraceLinearScan allocator, TraceInterval unhandledFixedFirst, TraceInterval unhandledAnyFirst) { super(allocator, unhandledFixedFirst, unhandledAnyFirst); moveResolver = allocator.createMoveResolver(); @@ -117,7 +117,7 @@ return reg >= minRegisterNumber() && reg <= maxRegisterNumber(); } - void excludeFromUse(Interval i) { + void excludeFromUse(TraceInterval i) { Value location = i.location(); int i1 = asRegister(location).number; if (isRegisterInRange(i1)) { @@ -125,7 +125,7 @@ } } - void setUsePos(Interval interval, int usePos, boolean onlyProcessUsePos) { + void setUsePos(TraceInterval interval, int usePos, boolean onlyProcessUsePos) { if (usePos != -1) { assert usePos != 0 : "must use excludeFromUse to set usePos to 0"; int i = asRegister(interval.location()).number; @@ -134,7 +134,7 @@ this.usePos[i] = usePos; } if (!onlyProcessUsePos) { - List list = spillIntervals[i]; + List list = spillIntervals[i]; if (list == EMPTY_LIST) { list = new ArrayList<>(2); spillIntervals[i] = list; @@ -145,7 +145,7 @@ } } - void setBlockPos(Interval i, int blockPos) { + void setBlockPos(TraceInterval i, int blockPos) { if (blockPos != -1) { int reg = asRegister(i.location()).number; if (isRegisterInRange(reg)) { @@ -160,8 +160,8 @@ } void freeExcludeActiveFixed() { - Interval interval = activeLists.get(RegisterBinding.Fixed); - while (interval != Interval.EndMarker) { + TraceInterval interval = activeLists.get(RegisterBinding.Fixed); + while (interval != TraceInterval.EndMarker) { assert isRegister(interval.location()) : "active interval must have a register assigned"; excludeFromUse(interval); interval = interval.next; @@ -169,17 +169,17 @@ } void freeExcludeActiveAny() { - Interval interval = activeLists.get(RegisterBinding.Any); - while (interval != Interval.EndMarker) { + TraceInterval interval = activeLists.get(RegisterBinding.Any); + while (interval != TraceInterval.EndMarker) { assert isRegister(interval.location()) : "active interval must have a register assigned"; excludeFromUse(interval); interval = interval.next; } } - void freeCollectInactiveFixed(Interval current) { - Interval interval = inactiveLists.get(RegisterBinding.Fixed); - while (interval != Interval.EndMarker) { + void freeCollectInactiveFixed(TraceInterval current) { + TraceInterval interval = inactiveLists.get(RegisterBinding.Fixed); + while (interval != TraceInterval.EndMarker) { if (current.to() <= interval.currentFrom()) { assert interval.currentIntersectsAt(current) == -1 : "must not intersect"; setUsePos(interval, interval.currentFrom(), true); @@ -190,17 +190,17 @@ } } - void freeCollectInactiveAny(Interval current) { - Interval interval = inactiveLists.get(RegisterBinding.Any); - while (interval != Interval.EndMarker) { + void freeCollectInactiveAny(TraceInterval current) { + TraceInterval interval = inactiveLists.get(RegisterBinding.Any); + while (interval != TraceInterval.EndMarker) { setUsePos(interval, interval.currentIntersectsAt(current), true); interval = interval.next; } } - void freeCollectUnhandled(RegisterBinding kind, Interval current) { - Interval interval = unhandledLists.get(kind); - while (interval != Interval.EndMarker) { + void freeCollectUnhandled(RegisterBinding kind, TraceInterval current) { + TraceInterval interval = unhandledLists.get(kind); + while (interval != TraceInterval.EndMarker) { setUsePos(interval, interval.intersectsAt(current), true); if (kind == RegisterBinding.Fixed && current.to() <= interval.from()) { setUsePos(interval, interval.from(), true); @@ -210,24 +210,24 @@ } void spillExcludeActiveFixed() { - Interval interval = activeLists.get(RegisterBinding.Fixed); - while (interval != Interval.EndMarker) { + TraceInterval interval = activeLists.get(RegisterBinding.Fixed); + while (interval != TraceInterval.EndMarker) { excludeFromUse(interval); interval = interval.next; } } - void spillBlockUnhandledFixed(Interval current) { - Interval interval = unhandledLists.get(RegisterBinding.Fixed); - while (interval != Interval.EndMarker) { + void spillBlockUnhandledFixed(TraceInterval current) { + TraceInterval interval = unhandledLists.get(RegisterBinding.Fixed); + while (interval != TraceInterval.EndMarker) { setBlockPos(interval, interval.intersectsAt(current)); interval = interval.next; } } - void spillBlockInactiveFixed(Interval current) { - Interval interval = inactiveLists.get(RegisterBinding.Fixed); - while (interval != Interval.EndMarker) { + void spillBlockInactiveFixed(TraceInterval current) { + TraceInterval interval = inactiveLists.get(RegisterBinding.Fixed); + while (interval != TraceInterval.EndMarker) { if (current.to() > interval.currentFrom()) { setBlockPos(interval, interval.currentIntersectsAt(current)); } else { @@ -239,16 +239,16 @@ } void spillCollectActiveAny(RegisterPriority registerPriority) { - Interval interval = activeLists.get(RegisterBinding.Any); - while (interval != Interval.EndMarker) { + TraceInterval interval = activeLists.get(RegisterBinding.Any); + while (interval != TraceInterval.EndMarker) { setUsePos(interval, Math.min(interval.nextUsage(registerPriority, currentPosition), interval.to()), false); interval = interval.next; } } - void spillCollectInactiveAny(Interval current) { - Interval interval = inactiveLists.get(RegisterBinding.Any); - while (interval != Interval.EndMarker) { + void spillCollectInactiveAny(TraceInterval current) { + TraceInterval interval = inactiveLists.get(RegisterBinding.Any); + while (interval != TraceInterval.EndMarker) { if (interval.currentIntersects(current)) { setUsePos(interval, Math.min(interval.nextUsage(RegisterPriority.LiveAtLoopEnd, currentPosition), interval.to()), false); } @@ -256,7 +256,7 @@ } } - void insertMove(int operandId, Interval srcIt, Interval dstIt) { + void insertMove(int operandId, TraceInterval srcIt, TraceInterval dstIt) { // output all moves here. When source and target are equal, the move is // optimized away later in assignRegNums @@ -315,7 +315,7 @@ return optimalSplitPos; } - int findOptimalSplitPos(Interval interval, int minSplitPos, int maxSplitPos, boolean doLoopOptimization) { + int findOptimalSplitPos(TraceInterval interval, int minSplitPos, int maxSplitPos, boolean doLoopOptimization) { int optimalSplitPos = -1; if (minSplitPos == maxSplitPos) { // trivial case, no optimization of split position possible @@ -424,7 +424,7 @@ // maxSplitPos in two parts: // 1) the left part has already a location assigned // 2) the right part is sorted into to the unhandled-list - void splitBeforeUsage(Interval interval, int minSplitPos, int maxSplitPos) { + void splitBeforeUsage(TraceInterval interval, int minSplitPos, int maxSplitPos) { try (Indent indent = Debug.logAndIndent("splitting interval %s between %d and %d", interval, minSplitPos, maxSplitPos)) { @@ -464,7 +464,7 @@ assert allocator.isBlockBegin(optimalSplitPos) || ((optimalSplitPos & 1) == 1) : "split pos must be odd when not on block boundary"; assert !allocator.isBlockBegin(optimalSplitPos) || ((optimalSplitPos & 1) == 0) : "split pos must be even on block boundary"; - Interval splitPart = interval.split(optimalSplitPos, allocator); + TraceInterval splitPart = interval.split(optimalSplitPos, allocator); splitPart.setInsertMoveWhenActivated(moveNecessary); @@ -483,7 +483,7 @@ // 1) the left part has already a location assigned // 2) the right part is always on the stack and therefore ignored in further processing - void splitForSpilling(Interval interval) { + void splitForSpilling(TraceInterval interval) { // calculate allowed range of splitting position int maxSplitPos = currentPosition; int previousUsage = interval.previousUsage(RegisterPriority.ShouldHaveRegister, maxSplitPos); @@ -520,7 +520,7 @@ // Also kick parent intervals out of register to memory when they have no use // position. This avoids short interval in register surrounded by intervals in // memory . avoid useless moves from memory to register and back - Interval parent = interval; + TraceInterval parent = interval; while (parent != null && parent.isSplitChild()) { parent = parent.getSplitChildBeforeOpId(parent.from()); @@ -558,7 +558,7 @@ assert allocator.isBlockBegin(optimalSplitPos) || ((optimalSplitPos & 1) == 1) : "split pos must be odd when not on block boundary"; assert !allocator.isBlockBegin(optimalSplitPos) || ((optimalSplitPos & 1) == 0) : "split pos must be even on block boundary"; - Interval spilledPart = interval.split(optimalSplitPos, allocator); + TraceInterval spilledPart = interval.split(optimalSplitPos, allocator); allocator.assignSpillSlot(spilledPart); handleSpillSlot(spilledPart); changeSpillState(spilledPart, optimalSplitPos); @@ -584,7 +584,7 @@ } // called during register allocation - private void changeSpillState(Interval interval, int spillPos) { + private void changeSpillState(TraceInterval interval, int spillPos) { switch (interval.spillState()) { case NoSpillStore: { int defLoopDepth = allocator.blockForId(interval.spillDefinitionPos()).getLoopDepth(); @@ -639,24 +639,24 @@ /** * This is called for every interval that is assigned to a stack slot. */ - protected static void handleSpillSlot(Interval interval) { + protected static void handleSpillSlot(TraceInterval interval) { assert interval.location() != null && (interval.canMaterialize() || isStackSlotValue(interval.location())) : "interval not assigned to a stack slot " + interval; // Do nothing. Stack slots are not processed in this implementation. } - void splitStackInterval(Interval interval) { + void splitStackInterval(TraceInterval interval) { int minSplitPos = currentPosition + 1; int maxSplitPos = Math.min(interval.firstUsage(RegisterPriority.ShouldHaveRegister), interval.to()); splitBeforeUsage(interval, minSplitPos, maxSplitPos); } - void splitWhenPartialRegisterAvailable(Interval interval, int registerAvailableUntil) { + void splitWhenPartialRegisterAvailable(TraceInterval interval, int registerAvailableUntil) { int minSplitPos = Math.max(interval.previousUsage(RegisterPriority.ShouldHaveRegister, registerAvailableUntil), interval.from() + 1); splitBeforeUsage(interval, minSplitPos, registerAvailableUntil); } - void splitAndSpillInterval(Interval interval) { + void splitAndSpillInterval(TraceInterval interval) { assert interval.state == State.Active || interval.state == State.Inactive : "other states not allowed"; int currentPos = currentPosition; @@ -682,7 +682,7 @@ } } - boolean allocFreeRegister(Interval interval) { + boolean allocFreeRegister(TraceInterval interval) { try (Indent indent = Debug.logAndIndent("trying to find free register for %s", interval)) { initUseLists(true); @@ -691,7 +691,7 @@ freeCollectInactiveFixed(interval); freeCollectInactiveAny(interval); // freeCollectUnhandled(fixedKind, cur); - assert unhandledLists.get(RegisterBinding.Fixed) == Interval.EndMarker : "must not have unhandled fixed intervals because all fixed intervals have a use at position 0"; + assert unhandledLists.get(RegisterBinding.Fixed) == TraceInterval.EndMarker : "must not have unhandled fixed intervals because all fixed intervals have a use at position 0"; // usePos contains the start of the next interval that has this register assigned // (either as a fixed register or a normal allocated register in the past) @@ -708,7 +708,7 @@ } Register hint = null; - Interval locationHint = interval.locationHint(true); + TraceInterval locationHint = interval.locationHint(true); if (locationHint != null && locationHint.location() != null && isRegister(locationHint.location())) { hint = asRegister(locationHint.location()); if (Debug.isLogEnabled()) { @@ -772,14 +772,14 @@ assert reg != null : "no register assigned"; for (int i = 0; i < spillIntervals[reg.number].size(); i++) { - Interval interval = spillIntervals[reg.number].get(i); + TraceInterval interval = spillIntervals[reg.number].get(i); removeFromList(interval); splitAndSpillInterval(interval); } } // Split an Interval and spill it to memory so that cur can be placed in a register - void allocLockedRegister(Interval interval) { + void allocLockedRegister(TraceInterval interval) { try (Indent indent = Debug.logAndIndent("alloc locked register: need to split and spill to get register for %s", interval)) { // the register must be free at least until this position @@ -802,7 +802,7 @@ initUseLists(false); spillExcludeActiveFixed(); // spillBlockUnhandledFixed(cur); - assert unhandledLists.get(RegisterBinding.Fixed) == Interval.EndMarker : "must not have unhandled fixed intervals because all fixed intervals have a use at position 0"; + assert unhandledLists.get(RegisterBinding.Fixed) == TraceInterval.EndMarker : "must not have unhandled fixed intervals because all fixed intervals have a use at position 0"; spillBlockInactiveFixed(interval); spillCollectActiveAny(registerPriority); spillCollectInactiveAny(interval); @@ -893,7 +893,7 @@ } } - boolean noAllocationPossible(Interval interval) { + boolean noAllocationPossible(TraceInterval interval) { if (allocator.callKillsRegisters()) { // fast calculation of intervals that can never get a register because the // the next instruction is a call that blocks all registers @@ -918,14 +918,14 @@ return false; } - void initVarsForAlloc(Interval interval) { + void initVarsForAlloc(TraceInterval interval) { AllocatableRegisters allocatableRegisters = allocator.getRegisterAllocationConfig().getAllocatableRegisters(interval.kind().getPlatformKind()); availableRegs = allocatableRegisters.allocatableRegisters; minReg = allocatableRegisters.minRegisterNumber; maxReg = allocatableRegisters.maxRegisterNumber; } - static boolean isMove(LIRInstruction op, Interval from, Interval to) { + static boolean isMove(LIRInstruction op, TraceInterval from, TraceInterval to) { if (op instanceof ValueMoveOp) { ValueMoveOp move = (ValueMoveOp) op; if (isVariable(move.getInput()) && isVariable(move.getResult())) { @@ -937,13 +937,13 @@ // optimization (especially for phi functions of nested loops): // assign same spill slot to non-intersecting intervals - void combineSpilledIntervals(Interval interval) { + void combineSpilledIntervals(TraceInterval interval) { if (interval.isSplitChild()) { // optimization is only suitable for split parents return; } - Interval registerHint = interval.locationHint(false); + TraceInterval registerHint = interval.locationHint(false); if (registerHint == null) { // cur is not the target of a move : otherwise registerHint would be set return; @@ -968,8 +968,8 @@ return; } - Interval beginHint = registerHint.getSplitChildAtOpId(beginPos, LIRInstruction.OperandMode.USE, allocator); - Interval endHint = registerHint.getSplitChildAtOpId(endPos, LIRInstruction.OperandMode.DEF, allocator); + TraceInterval beginHint = registerHint.getSplitChildAtOpId(beginPos, LIRInstruction.OperandMode.USE, allocator); + TraceInterval endHint = registerHint.getSplitChildAtOpId(endPos, LIRInstruction.OperandMode.DEF, allocator); if (beginHint == endHint || beginHint.to() != beginPos || endHint.from() != endPos) { // registerHint must be split : otherwise the re-writing of use positions does not work return; @@ -996,7 +996,7 @@ // allocate a physical register or memory location to an interval @Override - protected boolean activateCurrent(Interval interval) { + protected boolean activateCurrent(TraceInterval interval) { boolean result = true; try (Indent indent = Debug.logAndIndent("activating interval %s, splitParent: %d", interval, interval.splitParent().operandNumber)) { diff -r 71ca282ae653 -r d988ba58a535 graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/RegisterVerifier.java --- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/RegisterVerifier.java Tue Sep 01 11:49:35 2015 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/RegisterVerifier.java Tue Sep 01 12:03:14 2015 +0200 @@ -44,10 +44,10 @@ TraceLinearScan allocator; List> workList; // all blocks that must be processed - ArrayMap savedStates; // saved information of previous check + ArrayMap savedStates; // saved information of previous check // simplified access to methods of LinearScan - Interval intervalAt(Value operand) { + TraceInterval intervalAt(Value operand) { return allocator.intervalFor(operand); } @@ -57,11 +57,11 @@ } // accessors - Interval[] stateForBlock(AbstractBlockBase block) { + TraceInterval[] stateForBlock(AbstractBlockBase block) { return savedStates.get(block.getId()); } - void setStateForBlock(AbstractBlockBase block, Interval[] savedState) { + void setStateForBlock(AbstractBlockBase block, TraceInterval[] savedState) { savedStates.put(block.getId(), savedState); } @@ -81,7 +81,7 @@ void verify(AbstractBlockBase start) { try (Scope s = Debug.scope("RegisterVerifier")) { // setup input registers (method arguments) for first block - Interval[] inputState = new Interval[stateSize()]; + TraceInterval[] inputState = new TraceInterval[stateSize()]; setStateForBlock(start, inputState); addToWorkList(start); @@ -98,7 +98,7 @@ private void processBlock(AbstractBlockBase block) { try (Indent indent = Debug.logAndIndent("processBlock B%d", block.getId())) { // must copy state because it is modified - Interval[] inputState = copy(stateForBlock(block)); + TraceInterval[] inputState = copy(stateForBlock(block)); try (Indent indent2 = Debug.logAndIndent("Input-State of intervals:")) { printState(inputState); @@ -118,7 +118,7 @@ } } - protected void printState(Interval[] inputState) { + protected void printState(TraceInterval[] inputState) { for (int i = 0; i < stateSize(); i++) { Register reg = allocator.getRegisters()[i]; assert reg.number == i; @@ -130,8 +130,8 @@ } } - private void processSuccessor(AbstractBlockBase block, Interval[] inputState) { - Interval[] savedState = stateForBlock(block); + private void processSuccessor(AbstractBlockBase block, TraceInterval[] inputState) { + TraceInterval[] savedState = stateForBlock(block); if (savedState != null) { // this block was already processed before. @@ -172,11 +172,11 @@ } } - static Interval[] copy(Interval[] inputState) { + static TraceInterval[] copy(TraceInterval[] inputState) { return inputState.clone(); } - static void statePut(Interval[] inputState, Value location, Interval interval) { + static void statePut(TraceInterval[] inputState, Value location, TraceInterval interval) { if (location != null && isRegister(location)) { Register reg = asRegister(location); int regNum = reg.number; @@ -190,7 +190,7 @@ } } - static boolean checkState(AbstractBlockBase block, LIRInstruction op, Interval[] inputState, Value operand, Value reg, Interval interval) { + static boolean checkState(AbstractBlockBase block, LIRInstruction op, TraceInterval[] inputState, Value operand, Value reg, TraceInterval interval) { if (reg != null && isRegister(reg)) { if (inputState[asRegister(reg).number] != interval) { throw new JVMCIError( @@ -201,7 +201,7 @@ return true; } - void processOperations(AbstractBlockBase block, final Interval[] inputState) { + void processOperations(AbstractBlockBase block, final TraceInterval[] inputState) { List ops = allocator.getLIR().getLIRforBlock(block); InstructionValueConsumer useConsumer = new InstructionValueConsumer() { @@ -209,7 +209,7 @@ public void visitValue(LIRInstruction op, Value operand, OperandMode mode, EnumSet flags) { // we skip spill moves inserted by the spill position optimization if (TraceLinearScan.isVariableOrRegister(operand) && allocator.isProcessed(operand) && op.id() != TraceLinearScan.DOMINATOR_SPILL_MOVE_ID) { - Interval interval = intervalAt(operand); + TraceInterval interval = intervalAt(operand); if (op.id() != -1) { interval = interval.getSplitChildAtOpId(op.id(), mode, allocator); } @@ -221,7 +221,7 @@ InstructionValueConsumer defConsumer = (op, operand, mode, flags) -> { if (TraceLinearScan.isVariableOrRegister(operand) && allocator.isProcessed(operand)) { - Interval interval = intervalAt(operand); + TraceInterval interval = intervalAt(operand); if (op.id() != -1) { interval = interval.getSplitChildAtOpId(op.id(), mode, allocator); } diff -r 71ca282ae653 -r d988ba58a535 graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceGlobalMoveResolver.java --- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceGlobalMoveResolver.java Tue Sep 01 11:49:35 2015 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceGlobalMoveResolver.java Tue Sep 01 12:03:14 2015 +0200 @@ -208,7 +208,7 @@ } /** - * Checks if the {@linkplain Interval#location() location} of {@code to} is not blocked or is + * Checks if the {@linkplain TraceInterval#location() location} of {@code to} is not blocked or is * only blocked by {@code from}. */ private boolean safeToProcessMove(Value fromLocation, Value toLocation) { @@ -275,8 +275,8 @@ } /** - * @param fromOpr {@link Interval#operand operand} of the {@code from} interval - * @param toOpr {@link Interval#operand operand} of the {@code to} interval + * @param fromOpr {@link TraceInterval#operand operand} of the {@code from} interval + * @param toOpr {@link TraceInterval#operand operand} of the {@code to} interval */ private LIRInstruction createMove(Value fromOpr, AllocatableValue toOpr) { if (isStackSlotValue(toOpr) && isStackSlotValue(fromOpr)) { diff -r 71ca282ae653 -r d988ba58a535 graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceInterval.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceInterval.java Tue Sep 01 12:03:14 2015 +0200 @@ -0,0 +1,1304 @@ +/* + * Copyright (c) 2009, 2015, 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. + * + * 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 com.oracle.graal.lir.alloc.trace; + +import static com.oracle.graal.compiler.common.GraalOptions.*; +import static com.oracle.graal.lir.LIRValueUtil.*; +import static jdk.internal.jvmci.code.ValueUtil.*; + +import java.util.*; + +import jdk.internal.jvmci.code.*; +import jdk.internal.jvmci.common.*; +import jdk.internal.jvmci.meta.*; + +import com.oracle.graal.compiler.common.util.*; +import com.oracle.graal.debug.*; +import com.oracle.graal.lir.*; + +/** + * Represents an interval in the {@linkplain TraceLinearScan linear scan register allocator}. + */ +final class TraceInterval { + + /** + * A pair of intervals. + */ + static final class Pair { + + public final TraceInterval first; + public final TraceInterval second; + + public Pair(TraceInterval first, TraceInterval second) { + this.first = first; + this.second = second; + } + } + + /** + * A set of interval lists, one per {@linkplain RegisterBinding binding} type. + */ + static final class RegisterBindingLists { + + /** + * List of intervals whose binding is currently {@link RegisterBinding#Fixed}. + */ + public TraceInterval fixed; + + /** + * List of intervals whose binding is currently {@link RegisterBinding#Any}. + */ + public TraceInterval any; + + /** + * List of intervals whose binding is currently {@link RegisterBinding#Stack}. + */ + public TraceInterval stack; + + public RegisterBindingLists(TraceInterval fixed, TraceInterval any, TraceInterval stack) { + this.fixed = fixed; + this.any = any; + this.stack = stack; + } + + /** + * Gets the list for a specified binding. + * + * @param binding specifies the list to be returned + * @return the list of intervals whose binding is {@code binding} + */ + public TraceInterval get(RegisterBinding binding) { + switch (binding) { + case Any: + return any; + case Fixed: + return fixed; + case Stack: + return stack; + } + throw JVMCIError.shouldNotReachHere(); + } + + /** + * Sets the list for a specified binding. + * + * @param binding specifies the list to be replaced + * @param list a list of intervals whose binding is {@code binding} + */ + public void set(RegisterBinding binding, TraceInterval list) { + assert list != null; + switch (binding) { + case Any: + any = list; + break; + case Fixed: + fixed = list; + break; + case Stack: + stack = list; + break; + } + } + + /** + * Adds an interval to a list sorted by {@linkplain TraceInterval#currentFrom() current + * from} positions. + * + * @param binding specifies the list to be updated + * @param interval the interval to add + */ + public void addToListSortedByCurrentFromPositions(RegisterBinding binding, TraceInterval interval) { + TraceInterval list = get(binding); + TraceInterval prev = null; + TraceInterval cur = list; + while (cur.currentFrom() < interval.currentFrom()) { + prev = cur; + cur = cur.next; + } + TraceInterval result = list; + if (prev == null) { + // add to head of list + result = interval; + } else { + // add before 'cur' + prev.next = interval; + } + interval.next = cur; + set(binding, result); + } + + /** + * Adds an interval to a list sorted by {@linkplain TraceInterval#from() start} positions + * and {@linkplain TraceInterval#firstUsage(RegisterPriority) first usage} positions. + * + * @param binding specifies the list to be updated + * @param interval the interval to add + */ + public void addToListSortedByStartAndUsePositions(RegisterBinding binding, TraceInterval interval) { + TraceInterval list = get(binding); + TraceInterval prev = null; + TraceInterval cur = list; + while (cur.from() < interval.from() || (cur.from() == interval.from() && cur.firstUsage(RegisterPriority.None) < interval.firstUsage(RegisterPriority.None))) { + prev = cur; + cur = cur.next; + } + if (prev == null) { + list = interval; + } else { + prev.next = interval; + } + interval.next = cur; + set(binding, list); + } + + /** + * Removes an interval from a list. + * + * @param binding specifies the list to be updated + * @param i the interval to remove + */ + public void remove(RegisterBinding binding, TraceInterval i) { + TraceInterval list = get(binding); + TraceInterval prev = null; + TraceInterval cur = list; + while (cur != i) { + assert cur != null && cur != TraceInterval.EndMarker : "interval has not been found in list: " + i; + prev = cur; + cur = cur.next; + } + if (prev == null) { + set(binding, cur.next); + } else { + prev.next = cur.next; + } + } + } + + /** + * Constants denoting the register usage priority for an interval. The constants are declared in + * increasing order of priority are are used to optimize spilling when multiple overlapping + * intervals compete for limited registers. + */ + public enum RegisterPriority { + /** + * No special reason for an interval to be allocated a register. + */ + None, + + /** + * Priority level for intervals live at the end of a loop. + */ + LiveAtLoopEnd, + + /** + * Priority level for intervals that should be allocated to a register. + */ + ShouldHaveRegister, + + /** + * Priority level for intervals that must be allocated to a register. + */ + MustHaveRegister; + + public static final RegisterPriority[] VALUES = values(); + + /** + * Determines if this priority is higher than or equal to a given priority. + */ + public boolean greaterEqual(RegisterPriority other) { + return ordinal() >= other.ordinal(); + } + + /** + * Determines if this priority is lower than a given priority. + */ + public boolean lessThan(RegisterPriority other) { + return ordinal() < other.ordinal(); + } + } + + /** + * Constants denoting whether an interval is bound to a specific register. This models platform + * dependencies on register usage for certain instructions. + */ + enum RegisterBinding { + /** + * Interval is bound to a specific register as required by the platform. + */ + Fixed, + + /** + * Interval has no specific register requirements. + */ + Any, + + /** + * Interval is bound to a stack slot. + */ + Stack; + + public static final RegisterBinding[] VALUES = values(); + } + + /** + * Constants denoting the linear-scan states an interval may be in with respect to the + * {@linkplain TraceInterval#from() start} {@code position} of the interval being processed. + */ + enum State { + /** + * An interval that starts after {@code position}. + */ + Unhandled, + + /** + * An interval that {@linkplain TraceInterval#covers covers} {@code position} and has an + * assigned register. + */ + Active, + + /** + * An interval that starts before and ends after {@code position} but does not + * {@linkplain TraceInterval#covers cover} it due to a lifetime hole. + */ + Inactive, + + /** + * An interval that ends before {@code position} or is spilled to memory. + */ + Handled; + } + + /** + * Constants used in optimization of spilling of an interval. + */ + public enum SpillState { + /** + * Starting state of calculation: no definition found yet. + */ + NoDefinitionFound, + + /** + * One definition has already been found. Two consecutive definitions are treated as one + * (e.g. a consecutive move and add because of two-operand LIR form). The position of this + * definition is given by {@link TraceInterval#spillDefinitionPos()}. + */ + NoSpillStore, + + /** + * One spill move has already been inserted. + */ + OneSpillStore, + + /** + * The interval is spilled multiple times or is spilled in a loop. Place the store somewhere + * on the dominator path between the definition and the usages. + */ + SpillInDominator, + + /** + * The interval should be stored immediately after its definition to prevent multiple + * redundant stores. + */ + StoreAtDefinition, + + /** + * The interval starts in memory (e.g. method parameter), so a store is never necessary. + */ + StartInMemory, + + /** + * The interval has more than one definition (e.g. resulting from phi moves), so stores to + * memory are not optimized. + */ + NoOptimization + } + + /** + * List of use positions. Each entry in the list records the use position and register priority + * associated with the use position. The entries in the list are in descending order of use + * position. + * + */ + public static final class UsePosList { + + private IntList list; + + /** + * Creates a use list. + * + * @param initialCapacity the initial capacity of the list in terms of entries + */ + public UsePosList(int initialCapacity) { + list = new IntList(initialCapacity * 2); + } + + private UsePosList(IntList list) { + this.list = list; + } + + /** + * Splits this list around a given position. All entries in this list with a use position + * greater or equal than {@code splitPos} are removed from this list and added to the + * returned list. + * + * @param splitPos the position for the split + * @return a use position list containing all entries removed from this list that have a use + * position greater or equal than {@code splitPos} + */ + public UsePosList splitAt(int splitPos) { + int i = size() - 1; + int len = 0; + while (i >= 0 && usePos(i) < splitPos) { + --i; + len += 2; + } + int listSplitIndex = (i + 1) * 2; + IntList childList = list; + list = IntList.copy(this.list, listSplitIndex, len); + childList.setSize(listSplitIndex); + UsePosList child = new UsePosList(childList); + return child; + } + + /** + * Gets the use position at a specified index in this list. + * + * @param index the index of the entry for which the use position is returned + * @return the use position of entry {@code index} in this list + */ + public int usePos(int index) { + return list.get(index << 1); + } + + /** + * Gets the register priority for the use position at a specified index in this list. + * + * @param index the index of the entry for which the register priority is returned + * @return the register priority of entry {@code index} in this list + */ + public RegisterPriority registerPriority(int index) { + return RegisterPriority.VALUES[list.get((index << 1) + 1)]; + } + + public void add(int usePos, RegisterPriority registerPriority) { + assert list.size() == 0 || usePos(size() - 1) > usePos; + list.add(usePos); + list.add(registerPriority.ordinal()); + } + + public int size() { + return list.size() >> 1; + } + + public void removeLowestUsePos() { + list.setSize(list.size() - 2); + } + + public void setRegisterPriority(int index, RegisterPriority registerPriority) { + list.set((index << 1) + 1, registerPriority.ordinal()); + } + + @Override + public String toString() { + StringBuilder buf = new StringBuilder("["); + for (int i = size() - 1; i >= 0; --i) { + if (buf.length() != 1) { + buf.append(", "); + } + RegisterPriority prio = registerPriority(i); + buf.append(usePos(i)).append(" -> ").append(prio.ordinal()).append(':').append(prio); + } + return buf.append("]").toString(); + } + } + + /** + * The {@linkplain RegisterValue register} or {@linkplain Variable variable} for this interval + * prior to register allocation. + */ + public final AllocatableValue operand; + + /** + * The operand number for this interval's {@linkplain #operand operand}. + */ + public final int operandNumber; + + /** + * The {@linkplain RegisterValue register} or {@linkplain StackSlot spill slot} assigned to this + * interval. In case of a spilled interval which is re-materialized this is + * {@link Value#ILLEGAL}. + */ + private AllocatableValue location; + + /** + * The stack slot to which all splits of this interval are spilled if necessary. + */ + private StackSlotValue spillSlot; + + /** + * The kind of this interval. + */ + private LIRKind kind; + + /** + * The head of the list of ranges describing this interval. This list is sorted by + * {@linkplain LIRInstruction#id instruction ids}. + */ + private Range first; + + /** + * List of (use-positions, register-priorities) pairs, sorted by use-positions. + */ + private UsePosList usePosList; + + /** + * Iterator used to traverse the ranges of an interval. + */ + private Range current; + + /** + * Link to next interval in a sorted list of intervals that ends with {@link #EndMarker}. + */ + TraceInterval next; + + /** + * The linear-scan state of this interval. + */ + State state; + + private int cachedTo; // cached value: to of last range (-1: not cached) + + /** + * The interval from which this one is derived. If this is a {@linkplain #isSplitParent() split + * parent}, it points to itself. + */ + private TraceInterval splitParent; + + /** + * List of all intervals that are split off from this interval. This is only used if this is a + * {@linkplain #isSplitParent() split parent}. + */ + private List splitChildren = Collections.emptyList(); + + /** + * Current split child that has been active or inactive last (always stored in split parents). + */ + private TraceInterval currentSplitChild; + + /** + * Specifies if move is inserted between currentSplitChild and this interval when interval gets + * active the first time. + */ + private boolean insertMoveWhenActivated; + + /** + * For spill move optimization. + */ + private SpillState spillState; + + /** + * Position where this interval is defined (if defined only once). + */ + private int spillDefinitionPos; + + /** + * This interval should be assigned the same location as the hint interval. + */ + private TraceInterval locationHint; + + /** + * The value with which a spilled child interval can be re-materialized. Currently this must be + * a Constant. + */ + private JavaConstant materializedValue; + + /** + * The number of times {@link #addMaterializationValue(JavaConstant)} is called. + */ + private int numMaterializationValuesAdded; + + void assignLocation(AllocatableValue newLocation) { + if (isRegister(newLocation)) { + assert this.location == null : "cannot re-assign location for " + this; + if (newLocation.getLIRKind().equals(LIRKind.Illegal) && !kind.equals(LIRKind.Illegal)) { + this.location = asRegister(newLocation).asValue(kind); + return; + } + } else if (isIllegal(newLocation)) { + assert canMaterialize(); + } else { + assert this.location == null || isRegister(this.location) || (isVirtualStackSlot(this.location) && isStackSlot(newLocation)) : "cannot re-assign location for " + this; + assert isStackSlotValue(newLocation); + assert !newLocation.getLIRKind().equals(LIRKind.Illegal); + assert newLocation.getLIRKind().equals(this.kind); + } + this.location = newLocation; + } + + /** + * Gets the {@linkplain RegisterValue register} or {@linkplain StackSlot spill slot} assigned to + * this interval. + */ + public AllocatableValue location() { + return location; + } + + public LIRKind kind() { + assert !isRegister(operand) : "cannot access type for fixed interval"; + return kind; + } + + public void setKind(LIRKind kind) { + assert isRegister(operand) || this.kind().equals(LIRKind.Illegal) || this.kind().equals(kind) : "overwriting existing type"; + this.kind = kind; + } + + public Range first() { + return first; + } + + public int from() { + return first.from; + } + + int to() { + if (cachedTo == -1) { + cachedTo = calcTo(); + } + assert cachedTo == calcTo() : "invalid cached value"; + return cachedTo; + } + + int numUsePositions() { + return usePosList.size(); + } + + public void setLocationHint(TraceInterval interval) { + locationHint = interval; + } + + public boolean isSplitParent() { + return splitParent == this; + } + + boolean isSplitChild() { + return splitParent != this; + } + + /** + * Gets the split parent for this interval. + */ + public TraceInterval splitParent() { + assert splitParent.isSplitParent() : "not a split parent: " + this; + return splitParent; + } + + /** + * Gets the canonical spill slot for this interval. + */ + public StackSlotValue spillSlot() { + return splitParent().spillSlot; + } + + public void setSpillSlot(StackSlotValue slot) { + assert splitParent().spillSlot == null || (isVirtualStackSlot(splitParent().spillSlot) && isStackSlot(slot)) : "connot overwrite existing spill slot"; + splitParent().spillSlot = slot; + } + + TraceInterval currentSplitChild() { + return splitParent().currentSplitChild; + } + + void makeCurrentSplitChild() { + splitParent().currentSplitChild = this; + } + + boolean insertMoveWhenActivated() { + return insertMoveWhenActivated; + } + + void setInsertMoveWhenActivated(boolean b) { + insertMoveWhenActivated = b; + } + + // for spill optimization + public SpillState spillState() { + return splitParent().spillState; + } + + public int spillDefinitionPos() { + return splitParent().spillDefinitionPos; + } + + public void setSpillState(SpillState state) { + assert state.ordinal() >= spillState().ordinal() : "state cannot decrease"; + splitParent().spillState = state; + } + + public void setSpillDefinitionPos(int pos) { + assert spillState() == SpillState.SpillInDominator || spillState() == SpillState.NoDefinitionFound || spillDefinitionPos() == -1 : "cannot set the position twice"; + splitParent().spillDefinitionPos = pos; + } + + // returns true if this interval has a shadow copy on the stack that is always correct + public boolean alwaysInMemory() { + return (splitParent().spillState == SpillState.SpillInDominator || splitParent().spillState == SpillState.StoreAtDefinition || splitParent().spillState == SpillState.StartInMemory) && + !canMaterialize(); + } + + void removeFirstUsePos() { + usePosList.removeLowestUsePos(); + } + + // test intersection + boolean intersects(TraceInterval i) { + return first.intersects(i.first); + } + + int intersectsAt(TraceInterval i) { + return first.intersectsAt(i.first); + } + + // range iteration + void rewindRange() { + current = first; + } + + void nextRange() { + assert this != EndMarker : "not allowed on sentinel"; + current = current.next; + } + + int currentFrom() { + return current.from; + } + + int currentTo() { + return current.to; + } + + boolean currentAtEnd() { + return current == Range.EndMarker; + } + + boolean currentIntersects(TraceInterval it) { + return current.intersects(it.current); + } + + int currentIntersectsAt(TraceInterval it) { + return current.intersectsAt(it.current); + } + + /** + * Sentinel interval to denote the end of an interval list. + */ + static final TraceInterval EndMarker = new TraceInterval(Value.ILLEGAL, -1); + + TraceInterval(AllocatableValue operand, int operandNumber) { + assert operand != null; + this.operand = operand; + this.operandNumber = operandNumber; + if (isRegister(operand)) { + location = operand; + } else { + assert isIllegal(operand) || isVariable(operand); + } + this.kind = LIRKind.Illegal; + this.first = Range.EndMarker; + this.usePosList = new UsePosList(4); + this.current = Range.EndMarker; + this.next = EndMarker; + this.cachedTo = -1; + this.spillState = SpillState.NoDefinitionFound; + this.spillDefinitionPos = -1; + splitParent = this; + currentSplitChild = this; + } + + /** + * Sets the value which is used for re-materialization. + */ + public void addMaterializationValue(JavaConstant value) { + if (numMaterializationValuesAdded == 0) { + materializedValue = value; + } else { + // Interval is defined on multiple places -> no materialization is possible. + materializedValue = null; + } + numMaterializationValuesAdded++; + } + + /** + * Returns true if this interval can be re-materialized when spilled. This means that no + * spill-moves are needed. Instead of restore-moves the {@link #materializedValue} is restored. + */ + public boolean canMaterialize() { + return getMaterializedValue() != null; + } + + /** + * Returns a value which can be moved to a register instead of a restore-move from stack. + */ + public JavaConstant getMaterializedValue() { + return splitParent().materializedValue; + } + + int calcTo() { + assert first != Range.EndMarker : "interval has no range"; + + Range r = first; + while (r.next != Range.EndMarker) { + r = r.next; + } + return r.to; + } + + // consistency check of split-children + boolean checkSplitChildren() { + if (!splitChildren.isEmpty()) { + assert isSplitParent() : "only split parents can have children"; + + for (int i = 0; i < splitChildren.size(); i++) { + TraceInterval i1 = splitChildren.get(i); + + assert i1.splitParent() == this : "not a split child of this interval"; + assert i1.kind().equals(kind()) : "must be equal for all split children"; + assert (i1.spillSlot() == null && spillSlot == null) || i1.spillSlot().equals(spillSlot()) : "must be equal for all split children"; + + for (int j = i + 1; j < splitChildren.size(); j++) { + TraceInterval i2 = splitChildren.get(j); + + assert !i1.operand.equals(i2.operand) : "same register number"; + + if (i1.from() < i2.from()) { + assert i1.to() <= i2.from() && i1.to() < i2.to() : "intervals overlapping"; + } else { + assert i2.from() < i1.from() : "intervals start at same opId"; + assert i2.to() <= i1.from() && i2.to() < i1.to() : "intervals overlapping"; + } + } + } + } + + return true; + } + + public TraceInterval locationHint(boolean searchSplitChild) { + if (!searchSplitChild) { + return locationHint; + } + + if (locationHint != null) { + assert locationHint.isSplitParent() : "ony split parents are valid hint registers"; + + if (locationHint.location != null && isRegister(locationHint.location)) { + return locationHint; + } else if (!locationHint.splitChildren.isEmpty()) { + // search the first split child that has a register assigned + int len = locationHint.splitChildren.size(); + for (int i = 0; i < len; i++) { + TraceInterval interval = locationHint.splitChildren.get(i); + if (interval.location != null && isRegister(interval.location)) { + return interval; + } + } + } + } + + // no hint interval found that has a register assigned + return null; + } + + TraceInterval getSplitChildAtOpId(int opId, LIRInstruction.OperandMode mode, TraceLinearScan allocator) { + assert isSplitParent() : "can only be called for split parents"; + assert opId >= 0 : "invalid opId (method cannot be called for spill moves)"; + + if (splitChildren.isEmpty()) { + assert this.covers(opId, mode) : this + " does not cover " + opId; + return this; + } else { + TraceInterval result = null; + int len = splitChildren.size(); + + // in outputMode, the end of the interval (opId == cur.to()) is not valid + int toOffset = (mode == LIRInstruction.OperandMode.DEF ? 0 : 1); + + int i; + for (i = 0; i < len; i++) { + TraceInterval cur = splitChildren.get(i); + if (cur.from() <= opId && opId < cur.to() + toOffset) { + if (i > 0) { + // exchange current split child to start of list (faster access for next + // call) + Util.atPutGrow(splitChildren, i, splitChildren.get(0), null); + Util.atPutGrow(splitChildren, 0, cur, null); + } + + // interval found + result = cur; + break; + } + } + + assert checkSplitChild(result, opId, allocator, toOffset, mode); + return result; + } + } + + private boolean checkSplitChild(TraceInterval result, int opId, TraceLinearScan allocator, int toOffset, LIRInstruction.OperandMode mode) { + if (result == null) { + // this is an error + StringBuilder msg = new StringBuilder(this.toString()).append(" has no child at ").append(opId); + if (!splitChildren.isEmpty()) { + TraceInterval firstChild = splitChildren.get(0); + TraceInterval lastChild = splitChildren.get(splitChildren.size() - 1); + msg.append(" (first = ").append(firstChild).append(", last = ").append(lastChild).append(")"); + } + throw new JVMCIError("Linear Scan Error: %s", msg); + } + + if (!splitChildren.isEmpty()) { + for (TraceInterval interval : splitChildren) { + if (interval != result && interval.from() <= opId && opId < interval.to() + toOffset) { + TTY.println(String.format("two valid result intervals found for opId %d: %d and %d", opId, result.operandNumber, interval.operandNumber)); + TTY.println(result.logString(allocator)); + TTY.println(interval.logString(allocator)); + throw new BailoutException("two valid result intervals found"); + } + } + } + assert result.covers(opId, mode) : "opId not covered by interval"; + return true; + } + + // returns the interval that covers the given opId or null if there is none + TraceInterval getIntervalCoveringOpId(int opId) { + assert opId >= 0 : "invalid opId"; + assert opId < to() : "can only look into the past"; + + if (opId >= from()) { + return this; + } + + TraceInterval parent = splitParent(); + TraceInterval result = null; + + assert !parent.splitChildren.isEmpty() : "no split children available"; + int len = parent.splitChildren.size(); + + for (int i = len - 1; i >= 0; i--) { + TraceInterval cur = parent.splitChildren.get(i); + if (cur.from() <= opId && opId < cur.to()) { + assert result == null : "covered by multiple split children " + result + " and " + cur; + result = cur; + } + } + + return result; + } + + // returns the last split child that ends before the given opId + TraceInterval getSplitChildBeforeOpId(int opId) { + assert opId >= 0 : "invalid opId"; + + TraceInterval parent = splitParent(); + TraceInterval result = null; + + assert !parent.splitChildren.isEmpty() : "no split children available"; + int len = parent.splitChildren.size(); + + for (int i = len - 1; i >= 0; i--) { + TraceInterval cur = parent.splitChildren.get(i); + if (cur.to() <= opId && (result == null || result.to() < cur.to())) { + result = cur; + } + } + + assert result != null : "no split child found"; + return result; + } + + // checks if opId is covered by any split child + boolean splitChildCovers(int opId, LIRInstruction.OperandMode mode) { + assert isSplitParent() : "can only be called for split parents"; + assert opId >= 0 : "invalid opId (method can not be called for spill moves)"; + + if (splitChildren.isEmpty()) { + // simple case if interval was not split + return covers(opId, mode); + + } else { + // extended case: check all split children + int len = splitChildren.size(); + for (int i = 0; i < len; i++) { + TraceInterval cur = splitChildren.get(i); + if (cur.covers(opId, mode)) { + return true; + } + } + return false; + } + } + + private RegisterPriority adaptPriority(RegisterPriority priority) { + /* + * In case of re-materialized values we require that use-operands are registers, because we + * don't have the value in a stack location. (Note that ShouldHaveRegister means that the + * operand can also be a StackSlot). + */ + if (priority == RegisterPriority.ShouldHaveRegister && canMaterialize()) { + return RegisterPriority.MustHaveRegister; + } + return priority; + } + + // Note: use positions are sorted descending . first use has highest index + int firstUsage(RegisterPriority minRegisterPriority) { + assert isVariable(operand) : "cannot access use positions for fixed intervals"; + + for (int i = usePosList.size() - 1; i >= 0; --i) { + RegisterPriority registerPriority = adaptPriority(usePosList.registerPriority(i)); + if (registerPriority.greaterEqual(minRegisterPriority)) { + return usePosList.usePos(i); + } + } + return Integer.MAX_VALUE; + } + + int nextUsage(RegisterPriority minRegisterPriority, int from) { + assert isVariable(operand) : "cannot access use positions for fixed intervals"; + + for (int i = usePosList.size() - 1; i >= 0; --i) { + int usePos = usePosList.usePos(i); + if (usePos >= from && adaptPriority(usePosList.registerPriority(i)).greaterEqual(minRegisterPriority)) { + return usePos; + } + } + return Integer.MAX_VALUE; + } + + int nextUsageExact(RegisterPriority exactRegisterPriority, int from) { + assert isVariable(operand) : "cannot access use positions for fixed intervals"; + + for (int i = usePosList.size() - 1; i >= 0; --i) { + int usePos = usePosList.usePos(i); + if (usePos >= from && adaptPriority(usePosList.registerPriority(i)) == exactRegisterPriority) { + return usePos; + } + } + return Integer.MAX_VALUE; + } + + int previousUsage(RegisterPriority minRegisterPriority, int from) { + assert isVariable(operand) : "cannot access use positions for fixed intervals"; + + int prev = -1; + for (int i = usePosList.size() - 1; i >= 0; --i) { + int usePos = usePosList.usePos(i); + if (usePos > from) { + return prev; + } + if (adaptPriority(usePosList.registerPriority(i)).greaterEqual(minRegisterPriority)) { + prev = usePos; + } + } + return prev; + } + + public void addUsePos(int pos, RegisterPriority registerPriority) { + assert covers(pos, LIRInstruction.OperandMode.USE) : String.format("use position %d not covered by live range of interval %s", pos, this); + + // do not add use positions for precolored intervals because they are never used + if (registerPriority != RegisterPriority.None && isVariable(operand)) { + if (DetailedAsserts.getValue()) { + for (int i = 0; i < usePosList.size(); i++) { + assert pos <= usePosList.usePos(i) : "already added a use-position with lower position"; + if (i > 0) { + assert usePosList.usePos(i) < usePosList.usePos(i - 1) : "not sorted descending"; + } + } + } + + // Note: addUse is called in descending order, so list gets sorted + // automatically by just appending new use positions + int len = usePosList.size(); + if (len == 0 || usePosList.usePos(len - 1) > pos) { + usePosList.add(pos, registerPriority); + } else if (usePosList.registerPriority(len - 1).lessThan(registerPriority)) { + assert usePosList.usePos(len - 1) == pos : "list not sorted correctly"; + usePosList.setRegisterPriority(len - 1, registerPriority); + } + } + } + + public void addRange(int from, int to) { + assert from < to : "invalid range"; + assert first() == Range.EndMarker || to < first().next.from : "not inserting at begin of interval"; + assert from <= first().to : "not inserting at begin of interval"; + + if (first.from <= to) { + assert first != Range.EndMarker; + // join intersecting ranges + first.from = Math.min(from, first().from); + first.to = Math.max(to, first().to); + } else { + // insert new range + first = new Range(from, to, first()); + } + } + + TraceInterval newSplitChild(TraceLinearScan allocator) { + // allocate new interval + TraceInterval parent = splitParent(); + TraceInterval result = allocator.createDerivedInterval(parent); + result.setKind(kind()); + + result.splitParent = parent; + result.setLocationHint(parent); + + // insert new interval in children-list of parent + if (parent.splitChildren.isEmpty()) { + assert isSplitParent() : "list must be initialized at first split"; + + // Create new non-shared list + parent.splitChildren = new ArrayList<>(4); + parent.splitChildren.add(this); + } + parent.splitChildren.add(result); + + return result; + } + + /** + * Splits this interval at a specified position and returns the remainder as a new child + * interval of this interval's {@linkplain #splitParent() parent} interval. + *

+ * When an interval is split, a bi-directional link is established between the original + * parent interval and the children intervals that are split off this interval. + * When a split child is split again, the new created interval is a direct child of the original + * parent. That is, there is no tree of split children stored, just a flat list. All split + * children are spilled to the same {@linkplain #spillSlot spill slot}. + * + * @param splitPos the position at which to split this interval + * @param allocator the register allocator context + * @return the child interval split off from this interval + */ + TraceInterval split(int splitPos, TraceLinearScan allocator) { + assert isVariable(operand) : "cannot split fixed intervals"; + + // allocate new interval + TraceInterval result = newSplitChild(allocator); + + // split the ranges + Range prev = null; + Range cur = first; + while (cur != Range.EndMarker && cur.to <= splitPos) { + prev = cur; + cur = cur.next; + } + assert cur != Range.EndMarker : "split interval after end of last range"; + + if (cur.from < splitPos) { + result.first = new Range(splitPos, cur.to, cur.next); + cur.to = splitPos; + cur.next = Range.EndMarker; + + } else { + assert prev != null : "split before start of first range"; + result.first = cur; + prev.next = Range.EndMarker; + } + result.current = result.first; + cachedTo = -1; // clear cached value + + // split list of use positions + result.usePosList = usePosList.splitAt(splitPos); + + if (DetailedAsserts.getValue()) { + for (int i = 0; i < usePosList.size(); i++) { + assert usePosList.usePos(i) < splitPos; + } + for (int i = 0; i < result.usePosList.size(); i++) { + assert result.usePosList.usePos(i) >= splitPos; + } + } + return result; + } + + /** + * Splits this interval at a specified position and returns the head as a new interval (this + * interval is the tail). + * + * Currently, only the first range can be split, and the new interval must not have split + * positions + */ + TraceInterval splitFromStart(int splitPos, TraceLinearScan allocator) { + assert isVariable(operand) : "cannot split fixed intervals"; + assert splitPos > from() && splitPos < to() : "can only split inside interval"; + assert splitPos > first.from && splitPos <= first.to : "can only split inside first range"; + assert firstUsage(RegisterPriority.None) > splitPos : "can not split when use positions are present"; + + // allocate new interval + TraceInterval result = newSplitChild(allocator); + + // the new interval has only one range (checked by assertion above, + // so the splitting of the ranges is very simple + result.addRange(first.from, splitPos); + + if (splitPos == first.to) { + assert first.next != Range.EndMarker : "must not be at end"; + first = first.next; + } else { + first.from = splitPos; + } + + return result; + } + + // returns true if the opId is inside the interval + boolean covers(int opId, LIRInstruction.OperandMode mode) { + Range cur = first; + + while (cur != Range.EndMarker && cur.to < opId) { + cur = cur.next; + } + if (cur != Range.EndMarker) { + assert cur.to != cur.next.from : "ranges not separated"; + + if (mode == LIRInstruction.OperandMode.DEF) { + return cur.from <= opId && opId < cur.to; + } else { + return cur.from <= opId && opId <= cur.to; + } + } + return false; + } + + // returns true if the interval has any hole between holeFrom and holeTo + // (even if the hole has only the length 1) + boolean hasHoleBetween(int holeFrom, int holeTo) { + assert holeFrom < holeTo : "check"; + assert from() <= holeFrom && holeTo <= to() : "index out of interval"; + + Range cur = first; + while (cur != Range.EndMarker) { + assert cur.to < cur.next.from : "no space between ranges"; + + // hole-range starts before this range . hole + if (holeFrom < cur.from) { + return true; + + // hole-range completely inside this range . no hole + } else { + if (holeTo <= cur.to) { + return false; + + // overlapping of hole-range with this range . hole + } else { + if (holeFrom <= cur.to) { + return true; + } + } + } + + cur = cur.next; + } + + return false; + } + + @Override + public String toString() { + String from = "?"; + String to = "?"; + if (first != null && first != Range.EndMarker) { + from = String.valueOf(from()); + // to() may cache a computed value, modifying the current object, which is a bad idea + // for a printing function. Compute it directly instead. + to = String.valueOf(calcTo()); + } + String locationString = this.location == null ? "" : "@" + this.location; + return operandNumber + ":" + operand + (isRegister(operand) ? "" : locationString) + "[" + from + "," + to + "]"; + } + + /** + * Gets the use position information for this interval. + */ + public UsePosList usePosList() { + return usePosList; + } + + /** + * Gets a single line string for logging the details of this interval to a log stream. + * + * @param allocator the register allocator context + */ + public String logString(TraceLinearScan allocator) { + StringBuilder buf = new StringBuilder(100); + buf.append(operandNumber).append(':').append(operand).append(' '); + if (!isRegister(operand)) { + if (location != null) { + buf.append("location{").append(location).append("} "); + } + } + + buf.append("hints{").append(splitParent.operandNumber); + TraceInterval hint = locationHint(false); + if (hint != null && hint.operandNumber != splitParent.operandNumber) { + buf.append(", ").append(hint.operandNumber); + } + buf.append("} ranges{"); + + // print ranges + Range cur = first; + while (cur != Range.EndMarker) { + if (cur != first) { + buf.append(", "); + } + buf.append(cur); + cur = cur.next; + assert cur != null : "range list not closed with range sentinel"; + } + buf.append("} uses{"); + + // print use positions + int prev = -1; + for (int i = usePosList.size() - 1; i >= 0; --i) { + assert prev < usePosList.usePos(i) : "use positions not sorted"; + if (i != usePosList.size() - 1) { + buf.append(", "); + } + buf.append(usePosList.usePos(i)).append(':').append(usePosList.registerPriority(i)); + prev = usePosList.usePos(i); + } + buf.append("} spill-state{").append(spillState()).append("}"); + if (canMaterialize()) { + buf.append(" (remat:").append(getMaterializedValue().toString()).append(")"); + } + return buf.toString(); + } + + List getSplitChildren() { + return Collections.unmodifiableList(splitChildren); + } +} diff -r 71ca282ae653 -r d988ba58a535 graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScan.java --- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScan.java Tue Sep 01 11:49:35 2015 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScan.java Tue Sep 01 12:03:14 2015 +0200 @@ -42,7 +42,7 @@ import com.oracle.graal.lir.*; import com.oracle.graal.lir.LIRInstruction.OperandFlag; import com.oracle.graal.lir.LIRInstruction.OperandMode; -import com.oracle.graal.lir.alloc.trace.Interval.RegisterBinding; +import com.oracle.graal.lir.alloc.trace.TraceInterval.RegisterBinding; import com.oracle.graal.lir.framemap.*; import com.oracle.graal.lir.gen.*; import com.oracle.graal.lir.gen.LIRGeneratorTool.SpillMoveFactory; @@ -113,7 +113,7 @@ private final List> sortedBlocks; /** @see #intervals() */ - private Interval[] intervals; + private TraceInterval[] intervals; /** * The number of valid entries in {@link #intervals}. @@ -122,14 +122,14 @@ /** * The index of the first entry in {@link #intervals} for a - * {@linkplain #createDerivedInterval(Interval) derived interval}. + * {@linkplain #createDerivedInterval(TraceInterval) derived interval}. */ private int firstDerivedIntervalIndex = -1; /** - * Intervals sorted by {@link Interval#from()}. + * Intervals sorted by {@link TraceInterval#from()}. */ - private Interval[] sortedIntervals; + private TraceInterval[] sortedIntervals; /** * Map from an instruction {@linkplain LIRInstruction#id id} to the instruction. Entries should @@ -233,7 +233,7 @@ static final IntervalPredicate IS_PRECOLORED_INTERVAL = new IntervalPredicate() { @Override - public boolean apply(Interval i) { + public boolean apply(TraceInterval i) { return isRegister(i.operand); } }; @@ -241,7 +241,7 @@ static final IntervalPredicate IS_VARIABLE_INTERVAL = new IntervalPredicate() { @Override - public boolean apply(Interval i) { + public boolean apply(TraceInterval i) { return isVariable(i.operand); } }; @@ -249,7 +249,7 @@ static final IntervalPredicate IS_STACK_INTERVAL = new IntervalPredicate() { @Override - public boolean apply(Interval i) { + public boolean apply(TraceInterval i) { return !isRegister(i.operand); } }; @@ -262,7 +262,7 @@ return registerAttributes[reg.number]; } - void assignSpillSlot(Interval interval) { + void assignSpillSlot(TraceInterval interval) { /* * Assign the canonical spill slot of the parent (if a part of the interval is already * spilled) or allocate a new spill slot. @@ -281,13 +281,13 @@ /** * Map from {@linkplain #operandNumber(Value) operand numbers} to intervals. */ - public Interval[] intervals() { + public TraceInterval[] intervals() { return intervals; } void initIntervals() { intervalsSize = operandSize(); - intervals = new Interval[intervalsSize + (intervalsSize >> SPLIT_INTERVALS_CAPACITY_RIGHT_SHIFT)]; + intervals = new TraceInterval[intervalsSize + (intervalsSize >> SPLIT_INTERVALS_CAPACITY_RIGHT_SHIFT)]; } /** @@ -296,10 +296,10 @@ * @param operand the operand for the interval * @return the created interval */ - Interval createInterval(AllocatableValue operand) { + TraceInterval createInterval(AllocatableValue operand) { assert isLegal(operand); int operandNumber = operandNumber(operand); - Interval interval = new Interval(operand, operandNumber); + TraceInterval interval = new TraceInterval(operand, operandNumber); assert operandNumber < intervalsSize; assert intervals[operandNumber] == null; intervals[operandNumber] = interval; @@ -312,7 +312,7 @@ * @param source an interval being split of spilled * @return a new interval derived from {@code source} */ - Interval createDerivedInterval(Interval source) { + TraceInterval createDerivedInterval(TraceInterval source) { if (firstDerivedIntervalIndex == -1) { firstDerivedIntervalIndex = intervalsSize; } @@ -322,7 +322,7 @@ intervalsSize++; Variable variable = new Variable(source.kind(), ir.nextVariable()); - Interval interval = createInterval(variable); + TraceInterval interval = createInterval(variable); assert intervals[intervalsSize - 1] == interval; return interval; } @@ -339,7 +339,7 @@ /** * Gets the size of the {@link BlockData#liveIn} and {@link BlockData#liveOut} sets for a basic * block. These sets do not include any operands allocated as a result of creating - * {@linkplain #createDerivedInterval(Interval) derived intervals}. + * {@linkplain #createDerivedInterval(TraceInterval) derived intervals}. */ public int liveSetSize() { return firstDerivedIntervalIndex == -1 ? operandSize() : firstDerivedIntervalIndex; @@ -349,18 +349,18 @@ return ir.getControlFlowGraph().getLoops().size(); } - Interval intervalFor(int operandNumber) { + TraceInterval intervalFor(int operandNumber) { return intervals[operandNumber]; } - public Interval intervalFor(Value operand) { + public TraceInterval intervalFor(Value operand) { int operandNumber = operandNumber(operand); assert operandNumber < intervalsSize; return intervals[operandNumber]; } - public Interval getOrCreateInterval(AllocatableValue operand) { - Interval ret = intervalFor(operand); + public TraceInterval getOrCreateInterval(AllocatableValue operand) { + TraceInterval ret = intervalFor(operand); if (ret == null) { return createInterval(operand); } else { @@ -441,7 +441,7 @@ abstract static class IntervalPredicate { - abstract boolean apply(Interval i); + abstract boolean apply(TraceInterval i); } public boolean isProcessed(Value operand) { @@ -450,9 +450,9 @@ // * Phase 5: actual register allocation - private static boolean isSorted(Interval[] intervals) { + private static boolean isSorted(TraceInterval[] intervals) { int from = -1; - for (Interval interval : intervals) { + for (TraceInterval interval : intervals) { assert interval != null; assert from <= interval.from(); from = interval.from(); @@ -460,8 +460,8 @@ return true; } - static Interval addToList(Interval first, Interval prev, Interval interval) { - Interval newFirst = first; + static TraceInterval addToList(TraceInterval first, TraceInterval prev, TraceInterval interval) { + TraceInterval newFirst = first; if (prev != null) { prev.next = interval; } else { @@ -470,15 +470,15 @@ return newFirst; } - Interval.Pair createUnhandledLists(IntervalPredicate isList1, IntervalPredicate isList2) { + TraceInterval.Pair createUnhandledLists(IntervalPredicate isList1, IntervalPredicate isList2) { assert isSorted(sortedIntervals) : "interval list is not sorted"; - Interval list1 = Interval.EndMarker; - Interval list2 = Interval.EndMarker; + TraceInterval list1 = TraceInterval.EndMarker; + TraceInterval list2 = TraceInterval.EndMarker; - Interval list1Prev = null; - Interval list2Prev = null; - Interval v; + TraceInterval list1Prev = null; + TraceInterval list2Prev = null; + TraceInterval v; int n = sortedIntervals.length; for (int i = 0; i < n; i++) { @@ -497,33 +497,33 @@ } if (list1Prev != null) { - list1Prev.next = Interval.EndMarker; + list1Prev.next = TraceInterval.EndMarker; } if (list2Prev != null) { - list2Prev.next = Interval.EndMarker; + list2Prev.next = TraceInterval.EndMarker; } - assert list1Prev == null || list1Prev.next == Interval.EndMarker : "linear list ends not with sentinel"; - assert list2Prev == null || list2Prev.next == Interval.EndMarker : "linear list ends not with sentinel"; + assert list1Prev == null || list1Prev.next == TraceInterval.EndMarker : "linear list ends not with sentinel"; + assert list2Prev == null || list2Prev.next == TraceInterval.EndMarker : "linear list ends not with sentinel"; - return new Interval.Pair(list1, list2); + return new TraceInterval.Pair(list1, list2); } protected void sortIntervalsBeforeAllocation() { int sortedLen = 0; - for (Interval interval : intervals) { + for (TraceInterval interval : intervals) { if (interval != null) { sortedLen++; } } - Interval[] sortedList = new Interval[sortedLen]; + TraceInterval[] sortedList = new TraceInterval[sortedLen]; int sortedIdx = 0; int sortedFromMax = -1; // special sorting algorithm: the original interval-list is almost sorted, // only some intervals are swapped. So this is much faster than a complete QuickSort - for (Interval interval : intervals) { + for (TraceInterval interval : intervals) { if (interval != null) { int from = interval.from(); @@ -551,16 +551,16 @@ return; } - Interval[] oldList = sortedIntervals; - Interval[] newList = Arrays.copyOfRange(intervals, firstDerivedIntervalIndex, intervalsSize); + TraceInterval[] oldList = sortedIntervals; + TraceInterval[] newList = Arrays.copyOfRange(intervals, firstDerivedIntervalIndex, intervalsSize); int oldLen = oldList.length; int newLen = newList.length; // conventional sort-algorithm for new intervals - Arrays.sort(newList, (Interval a, Interval b) -> a.from() - b.from()); + Arrays.sort(newList, (TraceInterval a, TraceInterval b) -> a.from() - b.from()); // merge old and new list (both already sorted) into one combined list - Interval[] combinedList = new Interval[oldLen + newLen]; + TraceInterval[] combinedList = new TraceInterval[oldLen + newLen]; int oldIdx = 0; int newIdx = 0; @@ -579,8 +579,8 @@ // wrapper for Interval.splitChildAtOpId that performs a bailout in product mode // instead of returning null - public Interval splitChildAtOpId(Interval interval, int opId, LIRInstruction.OperandMode mode) { - Interval result = interval.getSplitChildAtOpId(opId, mode, this); + public TraceInterval splitChildAtOpId(TraceInterval interval, int opId, LIRInstruction.OperandMode mode) { + TraceInterval result = interval.getSplitChildAtOpId(opId, mode, this); if (result != null) { if (Debug.isLogEnabled()) { @@ -592,13 +592,13 @@ throw new BailoutException("LinearScan: interval is null"); } - static StackSlotValue canonicalSpillOpr(Interval interval) { + static StackSlotValue canonicalSpillOpr(TraceInterval interval) { assert interval.spillSlot() != null : "canonical spill slot not set"; return interval.spillSlot(); } boolean isMaterialized(AllocatableValue operand, int opId, OperandMode mode) { - Interval interval = intervalFor(operand); + TraceInterval interval = intervalFor(operand); assert interval != null : "interval must exist"; if (opId != -1) { @@ -686,7 +686,7 @@ if (Debug.isDumpEnabled(TraceRegisterAllocationPhase.TRACE_DUMP_LEVEL)) { if (Debug.isLogEnabled()) { try (Indent indent = Debug.logAndIndent("intervals %s", label)) { - for (Interval interval : intervals) { + for (TraceInterval interval : intervals) { if (interval != null) { Debug.log("%s", interval.logString(this)); } @@ -734,7 +734,7 @@ int len = intervalsSize; for (int i = 0; i < len; i++) { - Interval i1 = intervals[i]; + TraceInterval i1 = intervals[i]; if (i1 == null) { continue; } @@ -774,7 +774,7 @@ } for (int j = i + 1; j < len; j++) { - Interval i2 = intervals[j]; + TraceInterval i2 = intervals[j]; if (i2 == null) { continue; } @@ -805,7 +805,7 @@ class CheckConsumer implements ValueConsumer { boolean ok; - Interval curInterval; + TraceInterval curInterval; @Override public void visitValue(Value operand, OperandMode mode, EnumSet flags) { @@ -821,12 +821,12 @@ try (Indent indent = Debug.logAndIndent("verifying that no oops are in fixed intervals *")) { CheckConsumer checkConsumer = new CheckConsumer(); - Interval fixedIntervals; - Interval otherIntervals; + TraceInterval fixedIntervals; + TraceInterval otherIntervals; fixedIntervals = createUnhandledLists(IS_PRECOLORED_INTERVAL, null).first; // to ensure a walking until the last instruction id, add a dummy interval // with a high operation id - otherIntervals = new Interval(Value.ILLEGAL, -1); + otherIntervals = new TraceInterval(Value.ILLEGAL, -1); otherIntervals.addRange(Integer.MAX_VALUE - 2, Integer.MAX_VALUE - 1); IntervalWalker iw = new IntervalWalker(this, fixedIntervals, otherIntervals); @@ -845,7 +845,7 @@ * can't handle that correctly. */ if (checkLive) { - for (Interval interval = iw.activeLists.get(RegisterBinding.Fixed); interval != Interval.EndMarker; interval = interval.next) { + for (TraceInterval interval = iw.activeLists.get(RegisterBinding.Fixed); interval != TraceInterval.EndMarker; interval = interval.next) { if (interval.currentTo() > op.id() + 1) { /* * This interval is live out of this op so make sure that this diff -r 71ca282ae653 -r d988ba58a535 graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanAssignLocationsPhase.java --- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanAssignLocationsPhase.java Tue Sep 01 11:49:35 2015 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanAssignLocationsPhase.java Tue Sep 01 12:03:14 2015 +0200 @@ -77,7 +77,7 @@ */ protected Value colorLirOperand(LIRInstruction op, Variable operand, OperandMode mode) { int opId = op.id(); - Interval interval = allocator.intervalFor(operand); + TraceInterval interval = allocator.intervalFor(operand); assert interval != null : "interval must exist"; if (opId != -1) { @@ -241,7 +241,7 @@ public Value doValue(LIRInstruction instruction, Value value, OperandMode mode, EnumSet flags) { if (isRegister(value) || isVariable(value)) { - Interval interval = allocator.intervalFor(value); + TraceInterval interval = allocator.intervalFor(value); assert interval != null : "interval must exist"; interval = allocator.splitChildAtOpId(interval, instruction.id(), mode); diff -r 71ca282ae653 -r d988ba58a535 graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanEliminateSpillMovePhase.java --- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanEliminateSpillMovePhase.java Tue Sep 01 11:49:35 2015 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanEliminateSpillMovePhase.java Tue Sep 01 12:03:14 2015 +0200 @@ -37,7 +37,7 @@ import com.oracle.graal.lir.StandardOp.LoadConstantOp; import com.oracle.graal.lir.StandardOp.MoveOp; import com.oracle.graal.lir.StandardOp.ValueMoveOp; -import com.oracle.graal.lir.alloc.trace.Interval.SpillState; +import com.oracle.graal.lir.alloc.trace.TraceInterval.SpillState; import com.oracle.graal.lir.alloc.trace.TraceLinearScan.IntervalPredicate; import com.oracle.graal.lir.gen.*; import com.oracle.graal.lir.gen.LIRGeneratorTool.SpillMoveFactory; @@ -48,7 +48,7 @@ private static final IntervalPredicate mustStoreAtDefinition = new TraceLinearScan.IntervalPredicate() { @Override - public boolean apply(Interval i) { + public boolean apply(TraceInterval i) { return i.isSplitParent() && i.spillState() == SpillState.StoreAtDefinition; } }; @@ -82,7 +82,7 @@ * collect all intervals that must be stored after their definition. The list is sorted * by Interval.spillDefinitionPos. */ - Interval interval; + TraceInterval interval; interval = allocator.createUnhandledLists(mustStoreAtDefinition, null).first; if (DetailedAsserts.getValue()) { checkIntervals(interval); @@ -131,10 +131,10 @@ * Insert move from register to stack just after the beginning of the * interval. */ - assert interval == Interval.EndMarker || interval.spillDefinitionPos() >= opId : "invalid order"; - assert interval == Interval.EndMarker || (interval.isSplitParent() && interval.spillState() == SpillState.StoreAtDefinition) : "invalid interval"; + assert interval == TraceInterval.EndMarker || interval.spillDefinitionPos() >= opId : "invalid order"; + assert interval == TraceInterval.EndMarker || (interval.isSplitParent() && interval.spillState() == SpillState.StoreAtDefinition) : "invalid interval"; - while (interval != Interval.EndMarker && interval.spillDefinitionPos() == opId) { + while (interval != TraceInterval.EndMarker && interval.spillDefinitionPos() == opId) { if (!interval.canMaterialize()) { if (!insertionBuffer.initialized()) { /* @@ -171,7 +171,7 @@ } } // end of block iteration - assert interval == Interval.EndMarker : "missed an interval"; + assert interval == TraceInterval.EndMarker : "missed an interval"; } } @@ -194,10 +194,10 @@ */ } - private static void checkIntervals(Interval interval) { - Interval prev = null; - Interval temp = interval; - while (temp != Interval.EndMarker) { + private static void checkIntervals(TraceInterval interval) { + TraceInterval prev = null; + TraceInterval temp = interval; + while (temp != TraceInterval.EndMarker) { assert temp.spillDefinitionPos() > 0 : "invalid spill definition pos"; if (prev != null) { assert temp.from() >= prev.from() : "intervals not sorted"; diff -r 71ca282ae653 -r d988ba58a535 graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanLifetimeAnalysisPhase.java --- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanLifetimeAnalysisPhase.java Tue Sep 01 11:49:35 2015 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanLifetimeAnalysisPhase.java Tue Sep 01 12:03:14 2015 +0200 @@ -48,8 +48,8 @@ import com.oracle.graal.lir.StandardOp.LoadConstantOp; import com.oracle.graal.lir.StandardOp.StackStoreOp; import com.oracle.graal.lir.StandardOp.ValueMoveOp; -import com.oracle.graal.lir.alloc.trace.Interval.RegisterPriority; -import com.oracle.graal.lir.alloc.trace.Interval.SpillState; +import com.oracle.graal.lir.alloc.trace.TraceInterval.RegisterPriority; +import com.oracle.graal.lir.alloc.trace.TraceInterval.SpillState; import com.oracle.graal.lir.alloc.trace.TraceLinearScan.BlockData; import com.oracle.graal.lir.gen.*; import com.oracle.graal.lir.gen.LIRGeneratorTool.SpillMoveFactory; @@ -88,8 +88,8 @@ return traceBuilderResult.getTraceForBlock(other) <= traceBuilderResult.getTraceForBlock(currentBlock); } - static void setHint(final LIRInstruction op, Interval target, Interval source) { - Interval currentHint = target.locationHint(false); + static void setHint(final LIRInstruction op, TraceInterval target, TraceInterval source) { + TraceInterval currentHint = target.locationHint(false); if (currentHint == null || currentHint.from() > target.from()) { /* * Update hint if there was none or if the hint interval starts after the hinted @@ -392,7 +392,7 @@ BitSet startBlockLiveIn = allocator.getBlockData(allocator.getLIR().getControlFlowGraph().getStartBlock()).liveIn; try (Indent indent2 = Debug.logAndIndent("Error: liveIn set of first block must be empty (when this fails, variables are used before they are defined):")) { for (int operandNum = startBlockLiveIn.nextSetBit(0); operandNum >= 0; operandNum = startBlockLiveIn.nextSetBit(operandNum + 1)) { - Interval interval = allocator.intervalFor(operandNum); + TraceInterval interval = allocator.intervalFor(operandNum); if (interval != null) { Value operand = interval.operand; Debug.log("var %d; operand=%s; node=%s", operandNum, operand, getSourceForOperandFromDebugContext(operand)); @@ -404,7 +404,7 @@ // print some additional information to simplify debugging for (int operandNum = startBlockLiveIn.nextSetBit(0); operandNum >= 0; operandNum = startBlockLiveIn.nextSetBit(operandNum + 1)) { - Interval interval = allocator.intervalFor(operandNum); + TraceInterval interval = allocator.intervalFor(operandNum); Value operand = null; Object valueForOperandFromDebugContext = null; if (interval != null) { @@ -488,7 +488,7 @@ return; } - Interval interval = allocator.getOrCreateInterval(operand); + TraceInterval interval = allocator.getOrCreateInterval(operand); if (!kind.equals(LIRKind.Illegal)) { interval.setKind(kind); } @@ -508,7 +508,7 @@ return; } - Interval interval = allocator.getOrCreateInterval(operand); + TraceInterval interval = allocator.getOrCreateInterval(operand); if (!kind.equals(LIRKind.Illegal)) { interval.setKind(kind); } @@ -528,7 +528,7 @@ } int defPos = op.id(); - Interval interval = allocator.getOrCreateInterval(operand); + TraceInterval interval = allocator.getOrCreateInterval(operand); if (!kind.equals(LIRKind.Illegal)) { interval.setKind(kind); } @@ -573,7 +573,7 @@ if (op instanceof StackStoreOp) { StackStoreOp store = (StackStoreOp) op; StackSlot slot = asStackSlot(store.getStackSlot()); - Interval interval = allocator.intervalFor(store.getResult()); + TraceInterval interval = allocator.intervalFor(store.getResult()); interval.setSpillSlot(slot); interval.setSpillState(SpillState.StartInMemory); } @@ -584,8 +584,8 @@ op.forEachRegisterHint(targetValue, mode, (registerHint, valueMode, valueFlags) -> { if (TraceLinearScan.isVariableOrRegister(registerHint)) { - Interval from = allocator.getOrCreateInterval((AllocatableValue) registerHint); - Interval to = allocator.getOrCreateInterval((AllocatableValue) targetValue); + TraceInterval from = allocator.getOrCreateInterval((AllocatableValue) registerHint); + TraceInterval to = allocator.getOrCreateInterval((AllocatableValue) targetValue); /* hints always point from def to use */ if (hintAtDef) { @@ -610,7 +610,7 @@ * @param op * @param operand */ - protected void changeSpillDefinitionPos(LIRInstruction op, AllocatableValue operand, Interval interval, int defPos) { + protected void changeSpillDefinitionPos(LIRInstruction op, AllocatableValue operand, TraceInterval interval, int defPos) { assert interval.isSplitParent() : "can only be called for split parents"; switch (interval.spillState()) { @@ -815,7 +815,7 @@ * Add the range [0, 1] to all fixed intervals. the register allocator need not handle * unhandled fixed intervals. */ - for (Interval interval : allocator.intervals()) { + for (TraceInterval interval : allocator.intervals()) { if (interval != null && isRegister(interval.operand)) { interval.addRange(0, 1); } @@ -826,7 +826,7 @@ protected void postBuildIntervals() { // fix spill state for phi/sigma intervals - for (Interval interval : allocator.intervals()) { + for (TraceInterval interval : allocator.intervals()) { if (interval != null && interval.spillState().equals(SpillState.NoDefinitionFound) && interval.spillDefinitionPos() != -1) { // there was a definition in a phi/sigma interval.setSpillState(SpillState.NoSpillStore); @@ -852,13 +852,13 @@ assert sameTrace(block, pred) || !isVariable(fromValue) : "Unallocated variable: " + fromValue; if (isRegister(fromValue) || isVariable(fromValue)) { - Interval from = allocator.getOrCreateInterval((AllocatableValue) fromValue); - Interval to = allocator.getOrCreateInterval((AllocatableValue) toValue); + TraceInterval from = allocator.getOrCreateInterval((AllocatableValue) fromValue); + TraceInterval to = allocator.getOrCreateInterval((AllocatableValue) toValue); setHint(label, to, from); } else if (TraceRAshareSpillInformation.getValue() && TraceUtil.isShadowedRegisterValue(fromValue)) { ShadowedRegisterValue shadowedRegisterValue = TraceUtil.asShadowedRegisterValue(fromValue); - Interval from = allocator.getOrCreateInterval(shadowedRegisterValue.getRegister()); - Interval to = allocator.getOrCreateInterval((AllocatableValue) toValue); + TraceInterval from = allocator.getOrCreateInterval(shadowedRegisterValue.getRegister()); + TraceInterval to = allocator.getOrCreateInterval((AllocatableValue) toValue); setHint(label, to, from); to.setSpillSlot(shadowedRegisterValue.getStackSlot()); to.setSpillState(SpillState.StartInMemory); @@ -872,7 +872,7 @@ * Set the first range for fixed intervals to [-1, 0] to avoid intersection with incoming * values. */ - for (Interval interval : allocator.intervals()) { + for (TraceInterval interval : allocator.intervals()) { if (interval != null && isRegister(interval.operand)) { Range range = interval.first(); if (range == Range.EndMarker) { @@ -895,7 +895,7 @@ * reload-locations in case the interval of this instruction is spilled. Currently this * can only be a {@link JavaConstant}. */ - protected static JavaConstant getMaterializedValue(LIRInstruction op, Value operand, Interval interval) { + protected static JavaConstant getMaterializedValue(LIRInstruction op, Value operand, TraceInterval interval) { if (op instanceof LoadConstantOp) { LoadConstantOp move = (LoadConstantOp) op; if (move.getConstant() instanceof JavaConstant) { @@ -905,11 +905,11 @@ * degradation, because rematerialization always inserts a constant load, even if * the value is not needed in a register. */ - Interval.UsePosList usePosList = interval.usePosList(); + TraceInterval.UsePosList usePosList = interval.usePosList(); int numUsePos = usePosList.size(); for (int useIdx = 0; useIdx < numUsePos; useIdx++) { - Interval.RegisterPriority priority = usePosList.registerPriority(useIdx); - if (priority == Interval.RegisterPriority.ShouldHaveRegister) { + TraceInterval.RegisterPriority priority = usePosList.registerPriority(useIdx); + if (priority == TraceInterval.RegisterPriority.ShouldHaveRegister) { return null; } } diff -r 71ca282ae653 -r d988ba58a535 graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanOptimizeSpillPositionPhase.java --- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanOptimizeSpillPositionPhase.java Tue Sep 01 11:49:35 2015 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanOptimizeSpillPositionPhase.java Tue Sep 01 12:03:14 2015 +0200 @@ -35,7 +35,7 @@ import com.oracle.graal.compiler.common.cfg.*; import com.oracle.graal.lir.*; import com.oracle.graal.lir.LIRInstruction.OperandMode; -import com.oracle.graal.lir.alloc.trace.Interval.SpillState; +import com.oracle.graal.lir.alloc.trace.TraceInterval.SpillState; import com.oracle.graal.lir.gen.*; import com.oracle.graal.lir.gen.LIRGeneratorTool.SpillMoveFactory; import com.oracle.graal.lir.phases.*; @@ -61,7 +61,7 @@ private void optimizeSpillPosition() { try (Indent indent0 = Debug.logAndIndent("OptimizeSpillPositions")) { LIRInsertionBuffer[] insertionBuffers = new LIRInsertionBuffer[allocator.getLIR().linearScanOrder().size()]; - for (Interval interval : allocator.intervals()) { + for (TraceInterval interval : allocator.intervals()) { optimizeInterval(insertionBuffers, interval); } for (LIRInsertionBuffer insertionBuffer : insertionBuffers) { @@ -73,15 +73,15 @@ } } - private void optimizeInterval(LIRInsertionBuffer[] insertionBuffers, Interval interval) { + private void optimizeInterval(LIRInsertionBuffer[] insertionBuffers, TraceInterval interval) { if (interval == null || !interval.isSplitParent() || interval.spillState() != SpillState.SpillInDominator) { return; } AbstractBlockBase defBlock = allocator.blockForId(interval.spillDefinitionPos()); AbstractBlockBase spillBlock = null; - Interval firstSpillChild = null; + TraceInterval firstSpillChild = null; try (Indent indent = Debug.logAndIndent("interval %s (%s)", interval, defBlock)) { - for (Interval splitChild : interval.getSplitChildren()) { + for (TraceInterval splitChild : interval.getSplitChildren()) { if (isStackSlotValue(splitChild.location())) { if (firstSpillChild == null || splitChild.from() < firstSpillChild.from()) { firstSpillChild = splitChild; @@ -181,7 +181,7 @@ Range range; AbstractBlockBase block; - public IntervalBlockIterator(Interval interval) { + public IntervalBlockIterator(TraceInterval interval) { range = interval.first(); block = allocator.blockForId(range.from); } @@ -210,7 +210,7 @@ } } - private Iterable> blocksForInterval(Interval interval) { + private Iterable> blocksForInterval(TraceInterval interval) { return new Iterable>() { public Iterator> iterator() { return new IntervalBlockIterator(interval); diff -r 71ca282ae653 -r d988ba58a535 graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanRegisterAllocationPhase.java --- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanRegisterAllocationPhase.java Tue Sep 01 11:49:35 2015 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanRegisterAllocationPhase.java Tue Sep 01 12:03:14 2015 +0200 @@ -51,10 +51,10 @@ void allocateRegisters() { try (Indent indent = Debug.logAndIndent("allocate registers")) { - Interval precoloredIntervals; - Interval notPrecoloredIntervals; + TraceInterval precoloredIntervals; + TraceInterval notPrecoloredIntervals; - Interval.Pair result = allocator.createUnhandledLists(TraceLinearScan.IS_PRECOLORED_INTERVAL, TraceLinearScan.IS_VARIABLE_INTERVAL); + TraceInterval.Pair result = allocator.createUnhandledLists(TraceLinearScan.IS_PRECOLORED_INTERVAL, TraceLinearScan.IS_VARIABLE_INTERVAL); precoloredIntervals = result.first; notPrecoloredIntervals = result.second; diff -r 71ca282ae653 -r d988ba58a535 graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanResolveDataFlowPhase.java --- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanResolveDataFlowPhase.java Tue Sep 01 11:49:35 2015 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanResolveDataFlowPhase.java Tue Sep 01 12:03:14 2015 +0200 @@ -76,8 +76,8 @@ assert operandNum < numOperands : "live information set for not exisiting interval"; assert allocator.getBlockData(fromBlock).liveOut.get(operandNum) && allocator.getBlockData(toBlock).liveIn.get(operandNum) : "interval not live at this edge"; - Interval fromInterval = allocator.splitChildAtOpId(allocator.intervalFor(operandNum), fromBlockLastInstructionId, LIRInstruction.OperandMode.DEF); - Interval toInterval = allocator.splitChildAtOpId(allocator.intervalFor(operandNum), toBlockFirstInstructionId, LIRInstruction.OperandMode.DEF); + TraceInterval fromInterval = allocator.splitChildAtOpId(allocator.intervalFor(operandNum), fromBlockLastInstructionId, LIRInstruction.OperandMode.DEF); + TraceInterval toInterval = allocator.splitChildAtOpId(allocator.intervalFor(operandNum), toBlockFirstInstructionId, LIRInstruction.OperandMode.DEF); if (fromInterval != toInterval && !fromInterval.location().equals(toInterval.location())) { // need to insert move instruction @@ -185,8 +185,8 @@ assert operandNum < numOperands : "live information set for not exisiting interval"; assert allocator.getBlockData(fromBlock).liveOut.get(operandNum) && allocator.getBlockData(toBlock).liveIn.get(operandNum) : "interval not live at this edge"; - Interval fromInterval = allocator.splitChildAtOpId(allocator.intervalFor(operandNum), fromBlockLastInstructionId, LIRInstruction.OperandMode.DEF); - Interval toInterval = allocator.splitChildAtOpId(allocator.intervalFor(operandNum), toBlockFirstInstructionId, LIRInstruction.OperandMode.DEF); + TraceInterval fromInterval = allocator.splitChildAtOpId(allocator.intervalFor(operandNum), fromBlockLastInstructionId, LIRInstruction.OperandMode.DEF); + TraceInterval toInterval = allocator.splitChildAtOpId(allocator.intervalFor(operandNum), toBlockFirstInstructionId, LIRInstruction.OperandMode.DEF); if (fromInterval != toInterval && !fromInterval.location().equals(toInterval.location())) { // need to insert move instruction @@ -228,12 +228,12 @@ // no need to handle virtual stack slots return; } - Interval toInterval = allocator.splitChildAtOpId(allocator.intervalFor(phiIn), toId, LIRInstruction.OperandMode.DEF); + TraceInterval toInterval = allocator.splitChildAtOpId(allocator.intervalFor(phiIn), toId, LIRInstruction.OperandMode.DEF); if (isConstantValue(phiOut)) { numSSIResolutionMoves.increment(); moveResolver.addMapping(asConstant(phiOut), toInterval); } else { - Interval fromInterval = allocator.splitChildAtOpId(allocator.intervalFor(phiOut), fromId, LIRInstruction.OperandMode.DEF); + TraceInterval fromInterval = allocator.splitChildAtOpId(allocator.intervalFor(phiOut), fromId, LIRInstruction.OperandMode.DEF); if (fromInterval != toInterval) { numSSIResolutionMoves.increment(); if (!(isStackSlotValue(toInterval.location()) && isStackSlotValue(fromInterval.location()))) { diff -r 71ca282ae653 -r d988ba58a535 graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLocalMoveResolver.java --- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLocalMoveResolver.java Tue Sep 01 11:49:35 2015 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLocalMoveResolver.java Tue Sep 01 12:03:14 2015 +0200 @@ -44,9 +44,9 @@ private int insertIdx; private LIRInsertionBuffer insertionBuffer; // buffer where moves are inserted - private final List mappingFrom; + private final List mappingFrom; private final List mappingFromOpr; - private final List mappingTo; + private final List mappingTo; private final int[] registerBlocked; private int[] stackBlocked; @@ -102,7 +102,7 @@ } } - protected Interval getMappingFrom(int i) { + protected TraceInterval getMappingFrom(int i) { return mappingFrom.get(i); } @@ -195,7 +195,7 @@ HashSet usedRegs = new HashSet<>(); if (!areMultipleReadsAllowed()) { for (i = 0; i < mappingFrom.size(); i++) { - Interval interval = mappingFrom.get(i); + TraceInterval interval = mappingFrom.get(i); if (interval != null && !isIllegal(interval.location())) { boolean unique = usedRegs.add(interval.location()); assert unique : "cannot read from same register twice"; @@ -205,7 +205,7 @@ usedRegs.clear(); for (i = 0; i < mappingTo.size(); i++) { - Interval interval = mappingTo.get(i); + TraceInterval interval = mappingTo.get(i); if (isIllegal(interval.location())) { // After insertion the location may become illegal, so don't check it since multiple // intervals might be illegal. @@ -225,7 +225,7 @@ } // mark assignedReg and assignedRegHi of the interval as blocked - private void blockRegisters(Interval interval) { + private void blockRegisters(TraceInterval interval) { Value location = interval.location(); if (mightBeBlocked(location)) { assert areMultipleReadsAllowed() || valueBlocked(location) == 0 : "location already marked as used: " + location; @@ -236,7 +236,7 @@ } // mark assignedReg and assignedRegHi of the interval as unblocked - private void unblockRegisters(Interval interval) { + private void unblockRegisters(TraceInterval interval) { Value location = interval.location(); if (mightBeBlocked(location)) { assert valueBlocked(location) > 0 : "location already marked as unused: " + location; @@ -246,10 +246,10 @@ } /** - * Checks if the {@linkplain Interval#location() location} of {@code to} is not blocked or is + * Checks if the {@linkplain TraceInterval#location() location} of {@code to} is not blocked or is * only blocked by {@code from}. */ - private boolean safeToProcessMove(Interval from, Interval to) { + private boolean safeToProcessMove(TraceInterval from, TraceInterval to) { Value fromReg = from != null ? from.location() : null; Value location = to.location(); @@ -298,7 +298,7 @@ insertIdx = -1; } - private void insertMove(Interval fromInterval, Interval toInterval) { + private void insertMove(TraceInterval fromInterval, TraceInterval toInterval) { assert !fromInterval.operand.equals(toInterval.operand) : "from and to interval equal: " + fromInterval; assert LIRKind.verifyMoveKinds(toInterval.kind(), fromInterval.kind()) : "move between different types"; assert insertIdx != -1 : "must setup insert position first"; @@ -311,10 +311,10 @@ } /** - * @param fromOpr {@link Interval#operand operand} of the {@code from} interval - * @param toOpr {@link Interval#operand operand} of the {@code to} interval - * @param fromLocation {@link Interval#location() location} of the {@code to} interval - * @param toLocation {@link Interval#location() location} of the {@code to} interval + * @param fromOpr {@link TraceInterval#operand operand} of the {@code from} interval + * @param toOpr {@link TraceInterval#operand operand} of the {@code to} interval + * @param fromLocation {@link TraceInterval#location() location} of the {@code to} interval + * @param toLocation {@link TraceInterval#location() location} of the {@code to} interval */ protected LIRInstruction createMove(AllocatableValue fromOpr, AllocatableValue toOpr, AllocatableValue fromLocation, AllocatableValue toLocation) { if (isStackSlotValue(toLocation) && isStackSlotValue(fromLocation)) { @@ -323,7 +323,7 @@ return getAllocator().getSpillMoveFactory().createMove(toOpr, fromOpr); } - private void insertMove(Constant fromOpr, Interval toInterval) { + private void insertMove(Constant fromOpr, TraceInterval toInterval) { assert insertIdx != -1 : "must setup insert position first"; AllocatableValue toOpr = toInterval.operand; @@ -347,7 +347,7 @@ // This is necessary for detecting cycles in moves. int i; for (i = mappingFrom.size() - 1; i >= 0; i--) { - Interval fromInterval = mappingFrom.get(i); + TraceInterval fromInterval = mappingFrom.get(i); if (fromInterval != null) { blockRegisters(fromInterval); } @@ -358,8 +358,8 @@ boolean processedInterval = false; for (i = mappingFrom.size() - 1; i >= 0; i--) { - Interval fromInterval = mappingFrom.get(i); - Interval toInterval = mappingTo.get(i); + TraceInterval fromInterval = mappingFrom.get(i); + TraceInterval toInterval = mappingTo.get(i); if (safeToProcessMove(fromInterval, toInterval)) { // this interval can be processed because target is free @@ -398,7 +398,7 @@ assert spillCandidate != -1 : "no interval in register for spilling found"; // create a new spill interval and assign a stack slot to it - Interval fromInterval1 = mappingFrom.get(spillCandidate); + TraceInterval fromInterval1 = mappingFrom.get(spillCandidate); // do not allocate a new spill slot for temporary interval, but // use spill slot assigned to fromInterval. Otherwise moves from // one stack slot to another can happen (not allowed by LIRAssembler @@ -413,16 +413,16 @@ assert mappingFromSize() > 1; // Arbitrarily select the first entry for spilling. int stackSpillCandidate = 0; - Interval fromInterval = getMappingFrom(stackSpillCandidate); + TraceInterval fromInterval = getMappingFrom(stackSpillCandidate); assert isStackSlotValue(fromInterval.location()); // allocate new stack slot StackSlotValue spillSlot = getAllocator().getFrameMapBuilder().allocateSpillSlot(fromInterval.kind()); spillInterval(stackSpillCandidate, fromInterval, spillSlot); } - protected void spillInterval(int spillCandidate, Interval fromInterval, StackSlotValue spillSlot) { + protected void spillInterval(int spillCandidate, TraceInterval fromInterval, StackSlotValue spillSlot) { assert mappingFrom.get(spillCandidate).equals(fromInterval); - Interval spillInterval = getAllocator().createDerivedInterval(fromInterval); + TraceInterval spillInterval = getAllocator().createDerivedInterval(fromInterval); spillInterval.setKind(fromInterval.kind()); // add a dummy range because real position is difficult to calculate @@ -446,8 +446,8 @@ private void printMapping() { try (Indent indent = Debug.logAndIndent("Mapping")) { for (int i = mappingFrom.size() - 1; i >= 0; i--) { - Interval fromInterval = mappingFrom.get(i); - Interval toInterval = mappingTo.get(i); + TraceInterval fromInterval = mappingFrom.get(i); + TraceInterval toInterval = mappingTo.get(i); String from; Value to = toInterval.location(); if (fromInterval == null) { @@ -483,7 +483,7 @@ this.insertIdx = newInsertIdx; } - public void addMapping(Interval fromInterval, Interval toInterval) { + public void addMapping(TraceInterval fromInterval, TraceInterval toInterval) { if (isIllegal(toInterval.location()) && toInterval.canMaterialize()) { if (Debug.isLogEnabled()) { @@ -509,7 +509,7 @@ mappingTo.add(toInterval); } - public void addMapping(Constant fromOpr, Interval toInterval) { + public void addMapping(Constant fromOpr, TraceInterval toInterval) { if (Debug.isLogEnabled()) { Debug.log("add move mapping from %s to %s", fromOpr, toInterval); } diff -r 71ca282ae653 -r d988ba58a535 graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceSimpleLifetimeAnalysisPhase.java --- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceSimpleLifetimeAnalysisPhase.java Tue Sep 01 11:49:35 2015 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceSimpleLifetimeAnalysisPhase.java Tue Sep 01 12:03:14 2015 +0200 @@ -34,8 +34,8 @@ import com.oracle.graal.compiler.common.cfg.*; import com.oracle.graal.debug.*; import com.oracle.graal.lir.*; -import com.oracle.graal.lir.alloc.trace.Interval.RegisterPriority; -import com.oracle.graal.lir.alloc.trace.Interval.SpillState; +import com.oracle.graal.lir.alloc.trace.TraceInterval.RegisterPriority; +import com.oracle.graal.lir.alloc.trace.TraceInterval.SpillState; import com.oracle.graal.lir.gen.*; import com.oracle.graal.lir.gen.LIRGeneratorTool.SpillMoveFactory; @@ -63,7 +63,7 @@ return; } - Interval interval = allocator.getOrCreateInterval(operand); + TraceInterval interval = allocator.getOrCreateInterval(operand); if (!kind.equals(LIRKind.Illegal)) { interval.setKind(kind); } @@ -93,7 +93,7 @@ return; } - Interval interval = allocator.getOrCreateInterval(operand); + TraceInterval interval = allocator.getOrCreateInterval(operand); if (!kind.equals(LIRKind.Illegal)) { interval.setKind(kind); } @@ -123,7 +123,7 @@ } int defPos = op.id(); - Interval interval = allocator.getOrCreateInterval(operand); + TraceInterval interval = allocator.getOrCreateInterval(operand); if (!kind.equals(LIRKind.Illegal)) { interval.setKind(kind); } @@ -270,7 +270,7 @@ * Add the range [0, 1] to all fixed intervals. the register allocator need not handle * unhandled fixed intervals. */ - for (Interval interval : allocator.intervals()) { + for (TraceInterval interval : allocator.intervals()) { if (interval != null && isRegister(interval.operand)) { interval.addRange(0, 1); }