Mercurial > hg > graal-compiler
changeset 22591:c8faebfb7aed
TraceRA: clean-up and simplify.
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/FixedInterval.java Mon Sep 07 16:03:02 2015 +0200 @@ -0,0 +1,308 @@ +/* + * Copyright (c) 2015, 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 jdk.internal.jvmci.code.ValueUtil.*; +import jdk.internal.jvmci.meta.*; + +import com.oracle.graal.lir.*; + +/** + * Represents a fixed interval. + */ +public final class FixedInterval extends IntervalHint { + + static final class FixedList { + + public FixedInterval fixed; + + public FixedList(FixedInterval fixed) { + this.fixed = fixed; + } + + /** + * Gets the fixed list. + */ + public FixedInterval getFixed() { + return fixed; + } + + /** + * Sets the fixed list. + */ + public void setFixed(FixedInterval list) { + fixed = list; + } + + /** + * Adds an interval to a list sorted by {@linkplain FixedInterval#currentFrom() current + * from} positions. + * + * @param interval the interval to add + */ + public void addToListSortedByCurrentFromPositions(FixedInterval interval) { + FixedInterval list = getFixed(); + FixedInterval prev = null; + FixedInterval cur = list; + while (cur.currentFrom() < interval.currentFrom()) { + prev = cur; + cur = cur.next; + } + FixedInterval result = list; + if (prev == null) { + // add to head of list + result = interval; + } else { + // add before 'cur' + prev.next = interval; + } + interval.next = cur; + setFixed(result); + } + + } + + /** + * The fixed operand of this interval. + */ + public final AllocatableValue operand; + + /** + * The head of the list of ranges describing this interval. This list is sorted by + * {@linkplain LIRInstruction#id instruction ids}. + */ + private FixedRange first; + + /** + * Iterator used to traverse the ranges of an interval. + */ + private FixedRange current; + + /** + * Link to next interval in a sorted list of intervals that ends with {@link #EndMarker}. + */ + FixedInterval next; + + private int cachedTo; // cached value: to of last range (-1: not cached) + + public FixedRange first() { + return first; + } + + @Override + public int from() { + return first.from; + } + + public int to() { + if (cachedTo == -1) { + cachedTo = calcTo(); + } + assert cachedTo == calcTo() : "invalid cached value"; + return cachedTo; + } + + // test intersection + boolean intersects(TraceInterval i) { + return first.intersects(i); + } + + int intersectsAt(TraceInterval i) { + return first.intersectsAt(i); + } + + // 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 == FixedRange.EndMarker; + } + + boolean currentIntersects(TraceInterval it) { + return current.intersects(it); + } + + int currentIntersectsAt(TraceInterval it) { + return current.intersectsAt(it); + } + + // range creation + public void setFrom(int from) { + assert !isEmpty(); + first().from = from; + } + + private boolean isEmpty() { + return first() == FixedRange.EndMarker; + } + + public void addRange(int from, int to) { + if (isEmpty()) { + first = new FixedRange(from, to, first()); + return; + } + if (to <= to() && from >= from()) { + return; + } + if (from() == to) { + first().from = from; + } else { + first = new FixedRange(from, to, first()); + } + } + + @Override + public AllocatableValue location() { + return operand; + } + + /** + * Sentinel interval to denote the end of an interval list. + */ + static final FixedInterval EndMarker = new FixedInterval(Value.ILLEGAL); + + FixedInterval(AllocatableValue operand) { + assert operand != null; + this.operand = operand; + this.first = FixedRange.EndMarker; + this.current = FixedRange.EndMarker; + this.next = FixedInterval.EndMarker; + this.cachedTo = -1; + } + + int calcTo() { + assert first != FixedRange.EndMarker : "interval has no range"; + + FixedRange r = first; + while (r.next != FixedRange.EndMarker) { + r = r.next; + } + return r.to; + } + + // returns true if the opId is inside the interval + boolean covers(int opId, LIRInstruction.OperandMode mode) { + FixedRange cur = first; + + while (cur != FixedRange.EndMarker && cur.to < opId) { + cur = cur.next; + } + if (cur != FixedRange.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"; + + FixedRange cur = first; + while (cur != FixedRange.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 != FixedRange.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.operand; + return asRegister(operand).number + ":" + operand + (isRegister(operand) ? "" : locationString) + "[" + from + "," + to + "]"; + } + + /** + * Gets a single line string for logging the details of this interval to a log stream. + */ + @Override + public String logString(TraceLinearScan allocator) { + StringBuilder buf = new StringBuilder(100); + buf.append("fix ").append(asRegister(operand).number).append(':').append(operand).append(' '); + + buf.append(" ranges{"); + + // print ranges + FixedRange cur = first; + while (cur != FixedRange.EndMarker) { + if (cur != first) { + buf.append(", "); + } + buf.append(cur); + cur = cur.next; + assert cur != null : "range list not closed with range sentinel"; + } + buf.append("}"); + return buf.toString(); + } + +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/FixedRange.java Mon Sep 07 16:03:02 2015 +0200 @@ -0,0 +1,109 @@ +/* + * Copyright (c) 2015, 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; + +/** + * Represents a range of integers from a start (inclusive) to an end (exclusive). + */ +public final class FixedRange { + + public static final FixedRange EndMarker = new FixedRange(Integer.MAX_VALUE, Integer.MAX_VALUE, null); + + /** + * The start of the range, inclusive. + */ + public int from; + + /** + * The end of the range, exclusive. + */ + public int to; + + /** + * A link to allow the range to be put into a singly linked list. + */ + public FixedRange next; + + boolean intersects(TraceInterval i) { + return intersectsAt(i) != -1; + } + + /** + * Creates a new range. + * + * @param from the start of the range, inclusive + * @param to the end of the range, exclusive + * @param next link to the next range in a linked list + */ + FixedRange(int from, int to, FixedRange next) { + this.from = from; + this.to = to; + this.next = next; + } + + int intersectsAt(TraceInterval other) { + FixedRange range = this; + assert other != null : "null ranges not allowed"; + assert range != EndMarker && other != TraceInterval.EndMarker : "empty ranges not allowed"; + int intervalFrom = other.from(); + int intervalTo = other.to(); + + do { + if (range.from < intervalFrom) { + if (range.to <= intervalFrom) { + range = range.next; + if (range == EndMarker) { + return -1; + } + } else { + return intervalFrom; + } + } else { + if (intervalFrom < range.from) { + if (intervalTo <= range.from) { + return -1; + } + return range.from; + } else { + assert range.from == intervalFrom; + if (range.from == range.to) { + range = range.next; + if (range == EndMarker) { + return -1; + } + } else { + if (intervalFrom == intervalTo) { + return -1; + } + return range.from; + } + } + } + } while (true); + } + + @Override + public String toString() { + return "[" + from + ", " + to + "]"; + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/IntervalHint.java Mon Sep 07 16:03:02 2015 +0200 @@ -0,0 +1,37 @@ +/* + * Copyright (c) 2015, 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 jdk.internal.jvmci.meta.*; + +/** + * An interval that is a hint for an {@code TraceInterval interval}. + */ +abstract class IntervalHint { + + public abstract AllocatableValue location(); + + public abstract int from(); + + public abstract String logString(TraceLinearScan allocator); +}
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/Range.java Thu Sep 03 19:01:59 2015 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,116 +0,0 @@ -/* - * Copyright (c) 2009, 2011, 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; - -/** - * Represents a range of integers from a start (inclusive) to an end (exclusive. - */ -final class Range { - - public static final Range EndMarker = new Range(Integer.MAX_VALUE, Integer.MAX_VALUE, null); - - /** - * The start of the range, inclusive. - */ - public int from; - - /** - * The end of the range, exclusive. - */ - public int to; - - /** - * A link to allow the range to be put into a singly linked list. - */ - public Range next; - - boolean intersects(Range r) { - return intersectsAt(r) != -1; - } - - /** - * Creates a new range. - * - * @param from the start of the range, inclusive - * @param to the end of the range, exclusive - * @param next link to the next range in a linked list - */ - Range(int from, int to, Range next) { - this.from = from; - this.to = to; - this.next = next; - } - - int intersectsAt(Range other) { - Range r1 = this; - Range r2 = other; - - assert r2 != null : "null ranges not allowed"; - assert r1 != EndMarker && r2 != EndMarker : "empty ranges not allowed"; - - do { - if (r1.from < r2.from) { - if (r1.to <= r2.from) { - r1 = r1.next; - if (r1 == EndMarker) { - return -1; - } - } else { - return r2.from; - } - } else { - if (r2.from < r1.from) { - if (r2.to <= r1.from) { - r2 = r2.next; - if (r2 == EndMarker) { - return -1; - } - } else { - return r1.from; - } - } else { // r1.from() == r2.from() - if (r1.from == r1.to) { - r1 = r1.next; - if (r1 == EndMarker) { - return -1; - } - } else { - if (r2.from == r2.to) { - r2 = r2.next; - if (r2 == EndMarker) { - return -1; - } - } else { - return r1.from; - } - } - } - } - } while (true); - } - - @Override - public String toString() { - return "[" + from + ", " + to + "]"; - } -}
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/RegisterVerifier.java Thu Sep 03 19:01:59 2015 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/RegisterVerifier.java Mon Sep 07 16:03:02 2015 +0200 @@ -53,7 +53,7 @@ // currently, only registers are processed int stateSize() { - return allocator.maxRegisterNumber() + 1; + return allocator.numRegisters(); } // accessors
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceInterval.java Thu Sep 03 19:01:59 2015 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceInterval.java Mon Sep 07 16:03:02 2015 +0200 @@ -39,99 +39,44 @@ /** * 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; +final class TraceInterval extends IntervalHint { - 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; + static final class AnyList { /** * 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; + public AnyList(TraceInterval any) { 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} + * Gets the any list. */ - public TraceInterval get(RegisterBinding binding) { - switch (binding) { - case Any: - return any; - case Fixed: - return fixed; - case Stack: - return stack; - } - throw JVMCIError.shouldNotReachHere(); + public TraceInterval getAny() { + return any; } /** - * 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} + * Sets the any list. */ - 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; - } + public void setAny(TraceInterval list) { + any = list; } /** - * Adds an interval to a list sorted by {@linkplain TraceInterval#currentFrom() current - * from} positions. + * Adds an interval to a list sorted by {@linkplain TraceInterval#from() 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); + public void addToListSortedByFromPositions(TraceInterval interval) { + TraceInterval list = getAny(); TraceInterval prev = null; TraceInterval cur = list; - while (cur.currentFrom() < interval.currentFrom()) { + while (cur.from() < interval.from()) { prev = cur; cur = cur.next; } @@ -144,18 +89,17 @@ prev.next = interval; } interval.next = cur; - set(binding, result); + setAny(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); + public void addToListSortedByStartAndUsePositions(TraceInterval interval) { + TraceInterval list = getAny(); TraceInterval prev = null; TraceInterval cur = list; while (cur.from() < interval.from() || (cur.from() == interval.from() && cur.firstUsage(RegisterPriority.None) < interval.firstUsage(RegisterPriority.None))) { @@ -168,17 +112,16 @@ prev.next = interval; } interval.next = cur; - set(binding, list); + setAny(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); + public void removeAny(TraceInterval i) { + TraceInterval list = getAny(); TraceInterval prev = null; TraceInterval cur = list; while (cur != i) { @@ -187,7 +130,7 @@ cur = cur.next; } if (prev == null) { - set(binding, cur.next); + setAny(cur.next); } else { prev.next = cur.next; } @@ -235,6 +178,10 @@ public boolean lessThan(RegisterPriority other) { return ordinal() < other.ordinal(); } + + public CharSequence shortName() { + return name().subSequence(0, 1); + } } /** @@ -334,105 +281,6 @@ } /** - * 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. */ @@ -461,10 +309,14 @@ private LIRKind kind; /** - * The head of the list of ranges describing this interval. This list is sorted by - * {@linkplain LIRInstruction#id instruction ids}. + * The start of the range, inclusive. */ - private Range first; + public int intFrom; + + /** + * The end of the range, exclusive. + */ + public int intTo; /** * List of (use-positions, register-priorities) pairs, sorted by use-positions. @@ -472,11 +324,6 @@ 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; @@ -486,8 +333,6 @@ */ 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. @@ -524,7 +369,7 @@ /** * This interval should be assigned the same location as the hint interval. */ - private TraceInterval locationHint; + private IntervalHint locationHint; /** * The value with which a spilled child interval can be re-materialized. Currently this must be @@ -559,6 +404,7 @@ * Gets the {@linkplain RegisterValue register} or {@linkplain StackSlot spill slot} assigned to * this interval. */ + @Override public AllocatableValue location() { return location; } @@ -573,27 +419,28 @@ this.kind = kind; } - public Range first() { - return first; + public boolean isEmpty() { + return intFrom == Integer.MAX_VALUE && intTo == Integer.MAX_VALUE; } + public void setFrom(int pos) { + intFrom = pos; + } + + @Override public int from() { - return first.from; + return intFrom; } int to() { - if (cachedTo == -1) { - cachedTo = calcTo(); - } - assert cachedTo == calcTo() : "invalid cached value"; - return cachedTo; + return intTo; } int numUsePositions() { return usePosList.size(); } - public void setLocationHint(TraceInterval interval) { + public void setLocationHint(IntervalHint interval) { locationHint = interval; } @@ -672,41 +519,25 @@ // test intersection boolean intersects(TraceInterval i) { - return first.intersects(i.first); + return intersectsAt(i) != -1; } 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; - } + TraceInterval i1; + TraceInterval i2; + if (i.from() < this.from()) { + i1 = i; + i2 = this; + } else { + i1 = this; + i2 = i; + } + assert i1.from() <= i2.from(); - 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); + if (i1.to() <= i2.from()) { + return -1; + } + return i2.from(); } /** @@ -724,11 +555,10 @@ assert isIllegal(operand) || isVariable(operand); } this.kind = LIRKind.Illegal; - this.first = Range.EndMarker; + this.intFrom = Integer.MAX_VALUE; + this.intTo = Integer.MAX_VALUE; this.usePosList = new UsePosList(4); - this.current = Range.EndMarker; this.next = EndMarker; - this.cachedTo = -1; this.spillState = SpillState.NoDefinitionFound; this.spillDefinitionPos = -1; splitParent = this; @@ -763,16 +593,6 @@ 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()) { @@ -803,23 +623,26 @@ return true; } - public TraceInterval locationHint(boolean searchSplitChild) { + public IntervalHint locationHint(boolean searchSplitChild) { if (!searchSplitChild) { return locationHint; } if (locationHint != null) { - assert locationHint.isSplitParent() : "ony split parents are valid hint registers"; + assert !(locationHint instanceof TraceInterval) || ((TraceInterval) locationHint).isSplitParent() : "ony split parents are valid hint registers"; - if (locationHint.location != null && isRegister(locationHint.location)) { + 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; + } else if (locationHint instanceof TraceInterval) { + TraceInterval hint = (TraceInterval) locationHint; + if (!hint.splitChildren.isEmpty()) { + // search the first split child that has a register assigned + int len = hint.splitChildren.size(); + for (int i = 0; i < len; i++) { + TraceInterval interval = hint.splitChildren.get(i); + if (interval.location != null && isRegister(interval.location)) { + return interval; + } } } } @@ -1026,7 +849,7 @@ } 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); + assert isEmpty() || 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)) { @@ -1053,17 +876,12 @@ 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()); + if (from < intFrom) { + intFrom = from; + } + if (intTo == Integer.MAX_VALUE || intTo < to) { + intTo = to; } } @@ -1110,26 +928,9 @@ 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 + result.intTo = intTo; + result.intFrom = splitPos; + intTo = splitPos; // split list of use positions result.usePosList = usePosList.splitAt(splitPos); @@ -1145,97 +946,21 @@ 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; - } + if (mode == LIRInstruction.OperandMode.DEF) { + return from() <= opId && opId < 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; + return from() <= opId && opId <= to(); } @Override public String toString() { String from = "?"; String to = "?"; - if (first != null && first != Range.EndMarker) { + if (!isEmpty()) { 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()); + to = String.valueOf(to()); } String locationString = this.location == null ? "" : "@" + this.location; return operandNumber + ":" + operand + (isRegister(operand) ? "" : locationString) + "[" + from + "," + to + "]"; @@ -1253,9 +978,10 @@ * * @param allocator the register allocator context */ + @Override public String logString(TraceLinearScan allocator) { StringBuilder buf = new StringBuilder(100); - buf.append(operandNumber).append(':').append(operand).append(' '); + buf.append("any ").append(operandNumber).append(':').append(operand).append(' '); if (!isRegister(operand)) { if (location != null) { buf.append("location{").append(location).append("} "); @@ -1263,22 +989,14 @@ } buf.append("hints{").append(splitParent.operandNumber); - TraceInterval hint = locationHint(false); - if (hint != null && hint.operandNumber != splitParent.operandNumber) { - buf.append(", ").append(hint.operandNumber); + IntervalHint hint = locationHint(false); + if (hint != null) { + buf.append(", ").append(hint.location()); } 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"; - } + // print range + buf.append("[" + from() + ", " + to() + "]"); buf.append("} uses{"); // print use positions @@ -1288,7 +1006,7 @@ if (i != usePosList.size() - 1) { buf.append(", "); } - buf.append(usePosList.usePos(i)).append(':').append(usePosList.registerPriority(i)); + buf.append(usePosList.usePos(i)).append(':').append(usePosList.registerPriority(i).shortName()); prev = usePosList.usePos(i); } buf.append("} spill-state{").append(spillState()).append("}"); @@ -1301,4 +1019,57 @@ List<TraceInterval> getSplitChildren() { return Collections.unmodifiableList(splitChildren); } + + boolean isFixedInterval() { + return isRegister(operand); + } + + private static boolean isDefinitionPosition(int usePos) { + return (usePos & 1) == 1; + } + + int currentFrom(int currentPosition) { + assert isFixedInterval(); + for (int i = 0; i < usePosList.size(); i++) { + int usePos = usePosList.usePos(i); + if (usePos <= currentPosition && isDefinitionPosition(usePos)) { + return usePos; + } + + } + return Integer.MAX_VALUE; + } + + int currentIntersectsAt(int currentPosition, TraceInterval current) { + assert isFixedInterval(); + assert !current.isFixedInterval(); + int from = Integer.MAX_VALUE; + int to = Integer.MIN_VALUE; + + for (int i = 0; i < usePosList.size(); i++) { + int usePos = usePosList.usePos(i); + if (isDefinitionPosition(usePos)) { + if (usePos <= currentPosition) { + from = usePos; + break; + } + to = Integer.MIN_VALUE; + } else { + if (to < usePos) { + to = usePos; + } + } + } + if (from < current.from()) { + if (to <= current.from()) { + return -1; + } + return current.from(); + } else { + if (current.to() <= from) { + return -1; + } + return from; + } + } }
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceIntervalDumper.java Mon Sep 07 16:03:02 2015 +0200 @@ -0,0 +1,92 @@ +/* + * Copyright (c) 2015, 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 jdk.internal.jvmci.code.ValueUtil.*; +import jdk.internal.jvmci.meta.*; + +import com.oracle.graal.lir.debug.*; + +final class TraceIntervalDumper implements IntervalDumper { + private final FixedInterval[] fixedIntervals; + private final TraceInterval[] intervals; + + public TraceIntervalDumper(FixedInterval[] fixedIntervals, TraceInterval[] intervals) { + this.fixedIntervals = fixedIntervals; + this.intervals = intervals; + } + + public void visitIntervals(IntervalVisitor visitor) { + for (FixedInterval interval : fixedIntervals) { + if (interval != null) { + printFixedInterval(interval, visitor); + } + } + for (TraceInterval interval : intervals) { + if (interval != null) { + printInterval(interval, visitor); + } + } + } + + private static void printFixedInterval(FixedInterval interval, IntervalVisitor visitor) { + Value hint = null; + AllocatableValue operand = interval.operand; + String type = "fixed"; + char typeChar = operand.getKind().getTypeChar(); + visitor.visitIntervalStart(operand, operand, operand, hint, type, typeChar); + + // print ranges + for (FixedRange range = interval.first(); range != FixedRange.EndMarker; range = range.next) { + visitor.visitRange(range.from, range.to); + } + + // no use positions + + visitor.visitIntervalEnd("NOT_SUPPORTED"); + + } + + private static void printInterval(TraceInterval interval, IntervalVisitor visitor) { + Value hint = interval.locationHint(false) != null ? interval.locationHint(false).location() : null; + AllocatableValue operand = interval.operand; + String type = isRegister(operand) ? "fixed" : operand.getLIRKind().getPlatformKind().toString(); + char typeChar = operand.getKind().getTypeChar(); + visitor.visitIntervalStart(interval.splitParent().operand, operand, interval.location(), hint, type, typeChar); + + // print ranges + visitor.visitRange(interval.from(), interval.to()); + + // print use positions + int prev = -1; + UsePosList usePosList = interval.usePosList(); + for (int i = usePosList.size() - 1; i >= 0; --i) { + assert prev < usePosList.usePos(i) : "use positions not sorted"; + visitor.visitUsePos(usePosList.usePos(i), usePosList.registerPriority(i)); + prev = usePosList.usePos(i); + } + + visitor.visitIntervalEnd(interval.spillState()); + } + +}
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceIntervalWalker.java Thu Sep 03 19:01:59 2015 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceIntervalWalker.java Mon Sep 07 16:03:02 2015 +0200 @@ -22,10 +22,12 @@ */ package com.oracle.graal.lir.alloc.trace; -import com.oracle.graal.debug.*; +import jdk.internal.jvmci.common.*; +import com.oracle.graal.debug.*; +import com.oracle.graal.lir.alloc.trace.FixedInterval.FixedList; +import com.oracle.graal.lir.alloc.trace.TraceInterval.AnyList; 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; /** @@ -37,17 +39,18 @@ /** * Sorted list of intervals, not live before the current position. */ - protected RegisterBindingLists unhandledLists; + protected AnyList unhandledAnyList; /** * Sorted list of intervals, live at the current position. */ - protected RegisterBindingLists activeLists; + protected AnyList activeAnyList; + protected FixedList activeFixedList; /** * Sorted list of intervals in a life time hole at the current position. */ - protected RegisterBindingLists inactiveLists; + protected FixedList inactiveFixedList; /** * The current position (intercept point through the intervals). @@ -55,20 +58,43 @@ protected int currentPosition; /** - * The binding of the current interval being processed. - */ - protected RegisterBinding currentBinding; - - /** * Processes the {@code currentInterval} interval in an attempt to allocate a physical register - * to it and thus allow it to be moved to a list of {@linkplain #activeLists active} intervals. + * to it and thus allow it to be moved to a list of {@linkplain #activeAnyList active} + * intervals. + * + * @param currentInterval The interval to be activated. * * @return {@code true} if a register was allocated to the {@code currentInterval} interval */ - protected boolean activateCurrent(@SuppressWarnings({"unused"}) TraceInterval currentInterval) { + protected boolean activateCurrent(TraceInterval currentInterval) { + if (Debug.isLogEnabled()) { + logCurrentStatus(); + } return true; } + protected void logCurrentStatus() { + try (Indent i = Debug.logAndIndent("active:")) { + logList(activeFixedList.getFixed()); + logList(activeAnyList.getAny()); + } + try (Indent i = Debug.logAndIndent("inactive(fixed):")) { + logList(inactiveFixedList.getFixed()); + } + } + + private void logList(FixedInterval i) { + for (FixedInterval interval = i; interval != FixedInterval.EndMarker; interval = interval.next) { + Debug.log("%s", interval.logString(allocator)); + } + } + + private void logList(TraceInterval i) { + for (TraceInterval interval = i; interval != TraceInterval.EndMarker; interval = interval.next) { + Debug.log("%s", interval.logString(allocator)); + } + } + void walkBefore(int lirOpId) { walkTo(lirOpId - 1); } @@ -86,37 +112,46 @@ * @param unhandledAny the list of unhandled {@linkplain RegisterBinding#Any non-fixed} * intervals */ - TraceIntervalWalker(TraceLinearScan allocator, TraceInterval unhandledFixed, TraceInterval unhandledAny) { + TraceIntervalWalker(TraceLinearScan allocator, FixedInterval unhandledFixed, TraceInterval unhandledAny) { this.allocator = allocator; - 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); + unhandledAnyList = new AnyList(unhandledAny); + activeAnyList = new AnyList(TraceInterval.EndMarker); + activeFixedList = new FixedList(FixedInterval.EndMarker); + // we don't need a separate unhandled list for fixed. + inactiveFixedList = new FixedList(unhandledFixed); currentPosition = -1; } protected void removeFromList(TraceInterval interval) { if (interval.state == State.Active) { - activeLists.remove(RegisterBinding.Any, interval); + activeAnyList.removeAny(interval); } else { assert interval.state == State.Inactive : "invalid state"; - inactiveLists.remove(RegisterBinding.Any, interval); + // inactiveAnyLists.removeAny(interval); + throw JVMCIError.shouldNotReachHere(); } } - private void walkTo(State state, int from) { + /** + * Walks up to {@code from} and updates the state of {@link FixedInterval fixed intervals}. + * + * Fixed intervals can switch back and forth between the states {@link State#Active} and + * {@link State#Inactive} (and eventually to {@link State#Handled} but handled intervals are not + * managed). + */ + private void walkToFixed(State state, int from) { assert state == State.Active || state == State.Inactive : "wrong state"; - for (RegisterBinding binding : RegisterBinding.VALUES) { - walkTo(state, from, binding); + FixedInterval prevprev = null; + FixedInterval prev = (state == State.Active) ? activeFixedList.getFixed() : inactiveFixedList.getFixed(); + FixedInterval next = prev; + if (Debug.isLogEnabled()) { + try (Indent i = Debug.logAndIndent("walkToFixed(%s, %d):", state, from)) { + logList(next); + } } - } - - private void walkTo(State state, int from, RegisterBinding binding) { - TraceInterval prevprev = null; - TraceInterval prev = (state == State.Active) ? activeLists.get(binding) : inactiveLists.get(binding); - TraceInterval next = prev; while (next.currentFrom() <= from) { - TraceInterval cur = next; + FixedInterval cur = next; next = cur.next; boolean rangeHasChanged = false; @@ -132,9 +167,9 @@ // remove cur from list if (prevprev == null) { if (state == State.Active) { - activeLists.set(binding, next); + activeFixedList.setFixed(next); } else { - inactiveLists.set(binding, next); + inactiveFixedList.setFixed(next); } } else { prevprev.next = next; @@ -144,18 +179,16 @@ if (cur.currentAtEnd()) { // move to handled state (not maintained as a list) newState = State.Handled; - cur.state = newState; } else { if (cur.currentFrom() <= from) { // sort into active list - activeLists.addToListSortedByCurrentFromPositions(binding, cur); + activeFixedList.addToListSortedByCurrentFromPositions(cur); newState = State.Active; } else { // sort into inactive list - inactiveLists.addToListSortedByCurrentFromPositions(binding, cur); + inactiveFixedList.addToListSortedByCurrentFromPositions(cur); newState = State.Inactive; } - cur.state = newState; if (prev == cur) { assert state == newState; prevprev = prev; @@ -171,50 +204,71 @@ } /** - * Get the next interval from {@linkplain #unhandledLists} which starts before or at - * {@code toOpId}. The returned interval is removed and {@link #currentBinding} is set. + * Walks up to {@code from} and updates the state of {@link TraceInterval intervals}. * - * @postcondition all intervals in {@linkplain #unhandledLists} start after {@code toOpId}. + * Trace intervals can switch once from {@link State#Unhandled} to {@link State#Active} and then + * to {@link State#Handled} but handled intervals are not managed. + */ + private void walkToAny(int from) { + TraceInterval prevprev = null; + TraceInterval prev = activeAnyList.getAny(); + TraceInterval next = prev; + if (Debug.isLogEnabled()) { + try (Indent i = Debug.logAndIndent("walkToAny(%d):", from)) { + logList(next); + } + } + while (next.from() <= from) { + TraceInterval cur = next; + next = cur.next; + + if (cur.to() <= from) { + // remove cur from list + if (prevprev == null) { + activeAnyList.setAny(next); + } else { + prevprev.next = next; + } + intervalMoved(cur, State.Active, State.Handled); + } else { + prevprev = prev; + } + prev = next; + } + } + + /** + * Get the next interval from {@linkplain #unhandledAnyList} which starts before or at + * {@code toOpId}. The returned interval is removed. * - * @return The next interval or null if there is no {@linkplain #unhandledLists unhandled} + * @postcondition all intervals in {@linkplain #unhandledAnyList} start after {@code toOpId}. + * + * @return The next interval or null if there is no {@linkplain #unhandledAnyList unhandled} * interval at position {@code toOpId}. */ private TraceInterval nextInterval(int toOpId) { - RegisterBinding binding; - TraceInterval any = unhandledLists.any; - TraceInterval fixed = unhandledLists.fixed; + TraceInterval any = unhandledAnyList.getAny(); if (any != TraceInterval.EndMarker) { - // intervals may start at same position . prefer fixed interval - binding = fixed != TraceInterval.EndMarker && fixed.from() <= any.from() ? RegisterBinding.Fixed : RegisterBinding.Any; + TraceInterval currentInterval = unhandledAnyList.getAny(); + if (toOpId < currentInterval.from()) { + return null; + } - assert binding == RegisterBinding.Fixed && fixed.from() <= any.from() || binding == RegisterBinding.Any && any.from() <= fixed.from() : "wrong interval!!!"; - 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 != TraceInterval.EndMarker) { - binding = RegisterBinding.Fixed; - } else { - return null; + unhandledAnyList.setAny(currentInterval.next); + currentInterval.next = TraceInterval.EndMarker; + return currentInterval; } - TraceInterval currentInterval = unhandledLists.get(binding); - - if (toOpId < currentInterval.from()) { - return null; - } + return null; - currentBinding = binding; - unhandledLists.set(binding, currentInterval.next); - currentInterval.next = TraceInterval.EndMarker; - currentInterval.rewindRange(); - return currentInterval; } /** * Walk up to {@code toOpId}. * - * @postcondition {@link #currentPosition} is set to {@code toOpId}, {@link #activeLists} and - * {@link #inactiveLists} are populated and {@link TraceInterval#state}s are up - * to date. + * @postcondition {@link #currentPosition} is set to {@code toOpId}, {@link #activeFixedList} + * and {@link #inactiveFixedList} are populated and {@link TraceInterval#state}s + * are up to date. */ @SuppressWarnings("try") protected void walkTo(int toOpId) { @@ -226,16 +280,17 @@ currentPosition = opId; // update unhandled stack intervals - updateUnhandledStackIntervals(opId); + // updateUnhandledStackIntervals(opId); // call walkTo even if currentPosition == id - walkTo(State.Active, opId); - walkTo(State.Inactive, opId); + walkToFixed(State.Active, opId); + walkToFixed(State.Inactive, opId); + walkToAny(opId); try (Indent indent = Debug.logAndIndent("walk to op %d", opId)) { currentInterval.state = State.Active; if (activateCurrent(currentInterval)) { - activeLists.addToListSortedByCurrentFromPositions(currentBinding, currentInterval); + activeAnyList.addToListSortedByFromPositions(currentInterval); intervalMoved(currentInterval, State.Unhandled, State.Active); } } @@ -245,44 +300,20 @@ if (currentPosition <= allocator.maxOpId()) { // update unhandled stack intervals - updateUnhandledStackIntervals(toOpId); + // updateUnhandledStackIntervals(toOpId); // call walkTo if still in range - walkTo(State.Active, toOpId); - walkTo(State.Inactive, toOpId); + walkToFixed(State.Active, toOpId); + walkToFixed(State.Inactive, toOpId); + walkToAny(toOpId); } } - private void intervalMoved(TraceInterval interval, State from, State to) { + private void intervalMoved(IntervalHint 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()) { Debug.log("interval moved from %s to %s: %s", from, to, interval.logString(allocator)); } } - - /** - * Move {@linkplain #unhandledLists unhandled} stack intervals to - * {@linkplain TraceIntervalWalker #activeLists active}. - * - * Note that for {@linkplain RegisterBinding#Fixed fixed} and {@linkplain RegisterBinding#Any - * any} intervals this is done in {@link #nextInterval(int)}. - */ - private void updateUnhandledStackIntervals(int opId) { - 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); - intervalMoved(currentInterval, State.Unhandled, State.Active); - } else { - currentInterval.state = State.Handled; - intervalMoved(currentInterval, State.Unhandled, State.Handled); - } - currentInterval = next; - } - unhandledLists.set(RegisterBinding.Stack, currentInterval); - } - }
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScan.java Thu Sep 03 19:01:59 2015 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScan.java Mon Sep 07 16:03:02 2015 +0200 @@ -32,7 +32,6 @@ import jdk.internal.jvmci.code.*; import jdk.internal.jvmci.common.*; import jdk.internal.jvmci.meta.*; -import jdk.internal.jvmci.options.*; import com.oracle.graal.compiler.common.alloc.*; import com.oracle.graal.compiler.common.alloc.TraceBuilder.TraceBuilderResult; @@ -42,7 +41,6 @@ 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.TraceInterval.RegisterBinding; import com.oracle.graal.lir.framemap.*; import com.oracle.graal.lir.gen.*; import com.oracle.graal.lir.gen.LIRGeneratorTool.SpillMoveFactory; @@ -56,13 +54,6 @@ */ final class TraceLinearScan { - public static class Options { - // @formatter:off - @Option(help = "Use simplified lifetime analysis.", type = OptionType.Debug) - public static final OptionValue<Boolean> TraceRAsimpleLifetimeAnalysis = new OptionValue<>(true); - // @formatter:on - } - public static class BlockData { /** @@ -112,6 +103,9 @@ */ private final List<? extends AbstractBlockBase<?>> sortedBlocks; + /** @see #fixedIntervals() */ + private final FixedInterval[] fixedIntervals; + /** @see #intervals() */ private TraceInterval[] intervals; @@ -132,6 +126,11 @@ private TraceInterval[] sortedIntervals; /** + * Fixed intervals sorted by {@link FixedInterval#from()}. + */ + private FixedInterval[] sortedFixedIntervals; + + /** * Map from an instruction {@linkplain LIRInstruction#id id} to the instruction. Entries should * be retrieved with {@link #instructionForId(int)} as the id is not simply an index into this * array. @@ -145,10 +144,6 @@ */ private AbstractBlockBase<?>[] opIdToBlockMap; - /** - * The {@linkplain #operandNumber(Value) number} of the first variable operand allocated. - */ - private final int firstVariableNumber; protected final TraceBuilderResult<?> traceBuilderResult; protected TraceLinearScan(TargetDescription target, LIRGenerationResult res, SpillMoveFactory spillMoveFactory, RegisterAllocationConfig regAllocConfig, @@ -161,7 +156,7 @@ this.regAllocConfig = regAllocConfig; this.registers = target.arch.getRegisters(); - this.firstVariableNumber = getRegisters().length; + this.fixedIntervals = new FixedInterval[registers.length]; this.blockData = new BlockMap<>(ir.getControlFlowGraph()); this.traceBuilderResult = traceBuilderResult; } @@ -198,28 +193,25 @@ * the {@linkplain Variable variables} and {@linkplain RegisterValue registers} being processed * by this allocator. */ + @SuppressWarnings("static-method") int operandNumber(Value operand) { - if (isRegister(operand)) { - int number = asRegister(operand).number; - assert number < firstVariableNumber; - return number; - } - assert isVariable(operand) : operand; - return firstVariableNumber + ((Variable) operand).index; + assert !isRegister(operand) : "Register do not have operand numbers: " + operand; + assert isVariable(operand) : "Unsupported Value " + operand; + return ((Variable) operand).index; } /** * Gets the number of operands. This value will increase by 1 for new variable. */ int operandSize() { - return firstVariableNumber + ir.numVariables(); + return ir.numVariables(); } /** - * Gets the highest operand number for a register operand. This value will never change. + * Gets the number of registers. This value will never change. */ - int maxRegisterNumber() { - return firstVariableNumber - 1; + int numRegisters() { + return registers.length; } public BlockData getBlockData(AbstractBlockBase<?> block) { @@ -285,12 +277,33 @@ return intervals; } + /** + * Map from {@linkplain #operandNumber(Value) operand numbers} to intervals. + */ + public FixedInterval[] fixedIntervals() { + return fixedIntervals; + } + void initIntervals() { intervalsSize = operandSize(); intervals = new TraceInterval[intervalsSize + (intervalsSize >> SPLIT_INTERVALS_CAPACITY_RIGHT_SHIFT)]; } /** + * Creates a new fixed interval. + * + * @param reg the operand for the interval + * @return the created interval + */ + FixedInterval createFixedInterval(RegisterValue reg) { + FixedInterval interval = new FixedInterval(reg); + int operandNumber = reg.getRegister().number; + assert fixedIntervals[operandNumber] == null; + fixedIntervals[operandNumber] = interval; + return interval; + } + + /** * Creates a new interval. * * @param operand the operand for the interval @@ -349,6 +362,19 @@ return ir.getControlFlowGraph().getLoops().size(); } + public FixedInterval fixedIntervalFor(RegisterValue reg) { + return fixedIntervals[reg.getRegister().number]; + } + + public FixedInterval getOrCreateFixedInterval(RegisterValue reg) { + FixedInterval ret = fixedIntervalFor(reg); + if (ret == null) { + return createFixedInterval(reg); + } else { + return ret; + } + } + TraceInterval intervalFor(int operandNumber) { return intervals[operandNumber]; } @@ -450,9 +476,9 @@ // * Phase 5: actual register allocation - private static boolean isSorted(TraceInterval[] intervals) { + private static <T extends IntervalHint> boolean isSorted(T[] intervals) { int from = -1; - for (TraceInterval interval : intervals) { + for (T interval : intervals) { assert interval != null; assert from <= interval.from(); from = interval.from(); @@ -460,7 +486,7 @@ return true; } - static TraceInterval addToList(TraceInterval first, TraceInterval prev, TraceInterval interval) { + private static TraceInterval addToList(TraceInterval first, TraceInterval prev, TraceInterval interval) { TraceInterval newFirst = first; if (prev != null) { prev.next = interval; @@ -470,14 +496,12 @@ return newFirst; } - TraceInterval.Pair createUnhandledLists(IntervalPredicate isList1, IntervalPredicate isList2) { + TraceInterval createUnhandledList(IntervalPredicate isList1) { assert isSorted(sortedIntervals) : "interval list is not sorted"; TraceInterval list1 = TraceInterval.EndMarker; - TraceInterval list2 = TraceInterval.EndMarker; TraceInterval list1Prev = null; - TraceInterval list2Prev = null; TraceInterval v; int n = sortedIntervals.length; @@ -490,25 +514,59 @@ if (isList1.apply(v)) { list1 = addToList(list1, list1Prev, v); list1Prev = v; - } else if (isList2 == null || isList2.apply(v)) { - list2 = addToList(list2, list2Prev, v); - list2Prev = v; } } if (list1Prev != null) { list1Prev.next = TraceInterval.EndMarker; } - if (list2Prev != null) { - list2Prev.next = TraceInterval.EndMarker; - } 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 list1; + } + + private static FixedInterval addToList(FixedInterval first, FixedInterval prev, FixedInterval interval) { + FixedInterval newFirst = first; + if (prev != null) { + prev.next = interval; + } else { + newFirst = interval; + } + return newFirst; + } + + FixedInterval createFixedUnhandledList() { + assert isSorted(sortedFixedIntervals) : "interval list is not sorted"; + + FixedInterval list1 = FixedInterval.EndMarker; + + FixedInterval list1Prev = null; + FixedInterval v; - return new TraceInterval.Pair(list1, list2); + int n = sortedFixedIntervals.length; + for (int i = 0; i < n; i++) { + v = sortedFixedIntervals[i]; + if (v == null) { + continue; + } + + v.rewindRange(); + list1 = addToList(list1, list1Prev, v); + list1Prev = v; + } + + if (list1Prev != null) { + list1Prev.next = FixedInterval.EndMarker; + } + + assert list1Prev == null || list1Prev.next == FixedInterval.EndMarker : "linear list ends not with sentinel"; + + return list1; } + // SORTING + protected void sortIntervalsBeforeAllocation() { int sortedLen = 0; for (TraceInterval interval : intervals) { @@ -516,14 +574,26 @@ sortedLen++; } } + sortedIntervals = sortIntervalsBeforeAllocation(intervals, new TraceInterval[sortedLen]); + } - TraceInterval[] sortedList = new TraceInterval[sortedLen]; + protected void sortFixedIntervalsBeforeAllocation() { + int sortedLen = 0; + for (FixedInterval interval : fixedIntervals) { + if (interval != null) { + sortedLen++; + } + } + sortedFixedIntervals = sortIntervalsBeforeAllocation(fixedIntervals, new FixedInterval[sortedLen]); + } + + private static <T extends IntervalHint> T[] sortIntervalsBeforeAllocation(T[] intervals, T[] sortedList) { 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 (TraceInterval interval : intervals) { + for (T interval : intervals) { if (interval != null) { int from = interval.from(); @@ -542,7 +612,7 @@ } } } - sortedIntervals = sortedList; + return sortedList; } void sortIntervalsAfterAllocation() { @@ -630,12 +700,10 @@ try (Scope s = Debug.scope("AfterLifetimeAnalysis", (Object) intervals())) { sortIntervalsBeforeAllocation(); + sortFixedIntervalsBeforeAllocation(); createRegisterAllocationPhase().apply(target, lirGenRes, codeEmittingOrder, linearScanOrder, context, false); - if (com.oracle.graal.lir.alloc.lsra.LinearScan.Options.LIROptLSRAOptimizeSpillPosition.getValue()) { - createOptimizeSpillPositionPhase().apply(target, lirGenRes, codeEmittingOrder, linearScanOrder, context, false); - } // resolve intra-trace data-flow TraceLinearScanResolveDataFlowPhase dataFlowPhase = createResolveDataFlowPhase(); dataFlowPhase.apply(target, lirGenRes, codeEmittingOrder, linearScanOrder, context, false); @@ -654,9 +722,6 @@ } protected TraceLinearScanLifetimeAnalysisPhase createLifetimeAnalysisPhase() { - if (Options.TraceRAsimpleLifetimeAnalysis.getValue()) { - return new TraceSimpleLifetimeAnalysisPhase(this, traceBuilderResult); - } return new TraceLinearScanLifetimeAnalysisPhase(this, traceBuilderResult); } @@ -679,15 +744,17 @@ return new TraceLinearScanRegisterAllocationPhase(this); } - protected TraceLinearScanOptimizeSpillPositionPhase createOptimizeSpillPositionPhase() { - return new TraceLinearScanOptimizeSpillPositionPhase(this); - } - @SuppressWarnings("try") public void printIntervals(String label) { if (Debug.isDumpEnabled(TraceRegisterAllocationPhase.TRACE_DUMP_LEVEL)) { if (Debug.isLogEnabled()) { try (Indent indent = Debug.logAndIndent("intervals %s", label)) { + for (FixedInterval interval : fixedIntervals) { + if (interval != null) { + Debug.log("%s", interval.logString(this)); + } + } + for (TraceInterval interval : intervals) { if (interval != null) { Debug.log("%s", interval.logString(this)); @@ -702,7 +769,7 @@ } } } - Debug.dump(Arrays.copyOf(intervals, intervalsSize), label); + Debug.dump(new TraceIntervalDumper(Arrays.copyOf(fixedIntervals, fixedIntervals.length), Arrays.copyOf(intervals, intervalsSize)), label); } } @@ -738,7 +805,7 @@ int len = intervalsSize; for (int i = 0; i < len; i++) { - TraceInterval i1 = intervals[i]; + final TraceInterval i1 = intervals[i]; if (i1 == null) { continue; } @@ -763,39 +830,59 @@ throw new JVMCIError(""); } - if (i1.first() == Range.EndMarker) { + if (i1.isEmpty()) { Debug.log("Interval %d has no Range", i1.operandNumber); Debug.log(i1.logString(this)); throw new JVMCIError(""); } - for (Range r = i1.first(); r != Range.EndMarker; r = r.next) { - if (r.from >= r.to) { - Debug.log("Interval %d has zero length range", i1.operandNumber); - Debug.log(i1.logString(this)); - throw new JVMCIError(""); - } + if (i1.from() >= i1.to()) { + Debug.log("Interval %d has zero length range", i1.operandNumber); + Debug.log(i1.logString(this)); + throw new JVMCIError(""); } + // special intervals that are created in MoveResolver + // . ignore them because the range information has no meaning there + if (i1.from() == 1 && i1.to() == 2) { + continue; + } + // check any intervals for (int j = i + 1; j < len; j++) { - TraceInterval i2 = intervals[j]; + final TraceInterval i2 = intervals[j]; if (i2 == null) { continue; } // special intervals that are created in MoveResolver // . ignore them because the range information has no meaning there - if (i1.from() == 1 && i1.to() == 2) { - continue; - } if (i2.from() == 1 && i2.to() == 2) { continue; } Value l1 = i1.location(); Value l2 = i2.location(); - if (i1.intersects(i2) && !isIllegal(l1) && (l1.equals(l2))) { + boolean intersects = i1.intersects(i2); + if (intersects && !isIllegal(l1) && (l1.equals(l2))) { if (DetailedAsserts.getValue()) { - Debug.log("Intervals %d and %d overlap and have the same register assigned", i1.operandNumber, i2.operandNumber); + Debug.log("Intervals %s and %s overlap and have the same register assigned", i1, i2); + Debug.log(i1.logString(this)); + Debug.log(i2.logString(this)); + } + throw new BailoutException(""); + } + } + // check fixed intervals + for (FixedInterval i2 : fixedIntervals) { + if (i2 == null) { + continue; + } + + Value l1 = i1.location(); + Value l2 = i2.location(); + boolean intersects = i2.intersects(i1); + if (intersects && !isIllegal(l1) && (l1.equals(l2))) { + if (DetailedAsserts.getValue()) { + Debug.log("Intervals %s and %s overlap and have the same register assigned", i1, i2); Debug.log(i1.logString(this)); Debug.log(i2.logString(this)); } @@ -809,12 +896,12 @@ class CheckConsumer implements ValueConsumer { boolean ok; - TraceInterval curInterval; + FixedInterval curInterval; @Override public void visitValue(Value operand, OperandMode mode, EnumSet<OperandFlag> flags) { if (isRegister(operand)) { - if (intervalFor(operand) == curInterval) { + if (fixedIntervalFor(asRegisterValue(operand)) == curInterval) { ok = true; } } @@ -826,14 +913,13 @@ try (Indent indent = Debug.logAndIndent("verifying that no oops are in fixed intervals *")) { CheckConsumer checkConsumer = new CheckConsumer(); - TraceInterval fixedIntervals; TraceInterval otherIntervals; - fixedIntervals = createUnhandledLists(IS_PRECOLORED_INTERVAL, null).first; + FixedInterval fixedInts = createFixedUnhandledList(); // to ensure a walking until the last instruction id, add a dummy interval // with a high operation id otherIntervals = new TraceInterval(Value.ILLEGAL, -1); otherIntervals.addRange(Integer.MAX_VALUE - 2, Integer.MAX_VALUE - 1); - TraceIntervalWalker iw = new TraceIntervalWalker(this, fixedIntervals, otherIntervals); + TraceIntervalWalker iw = new TraceIntervalWalker(this, fixedInts, otherIntervals); for (AbstractBlockBase<?> block : sortedBlocks) { List<LIRInstruction> instructions = ir.getLIRforBlock(block); @@ -850,8 +936,8 @@ * can't handle that correctly. */ if (checkLive) { - for (TraceInterval interval = iw.activeLists.get(RegisterBinding.Fixed); interval != TraceInterval.EndMarker; interval = interval.next) { - if (interval.currentTo() > op.id() + 1) { + for (FixedInterval interval = iw.activeFixedList.getFixed(); interval != FixedInterval.EndMarker; interval = interval.next) { + if (interval.to() > op.id() + 1) { /* * This interval is live out of this op so make sure that this * interval represents some value that's referenced by this op
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanEliminateSpillMovePhase.java Thu Sep 03 19:01:59 2015 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanEliminateSpillMovePhase.java Mon Sep 07 16:03:02 2015 +0200 @@ -83,8 +83,7 @@ * collect all intervals that must be stored after their definition. The list is sorted * by Interval.spillDefinitionPos. */ - TraceInterval interval; - interval = allocator.createUnhandledLists(mustStoreAtDefinition, null).first; + TraceInterval interval = allocator.createUnhandledList(mustStoreAtDefinition); if (DetailedAsserts.getValue()) { checkIntervals(interval); } @@ -183,16 +182,6 @@ protected static boolean canEliminateSpillMove(AbstractBlockBase<?> block, MoveOp move) { // TODO (je) do not eliminate spill moves yet! return false; - /* - * assert isVariable(move.getResult()) : "LinearScan inserts only moves to variables: " + - * move; - * - * Interval curInterval = allocator.intervalFor(move.getResult()); - * - * if (!isRegister(curInterval.location()) && curInterval.alwaysInMemory()) { assert - * isStackSlotValue(curInterval.location()) : "Not a stack slot: " + curInterval.location(); - * return true; } return false; - */ } private static void checkIntervals(TraceInterval interval) {
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanLifetimeAnalysisPhase.java Thu Sep 03 19:01:59 2015 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanLifetimeAnalysisPhase.java Mon Sep 07 16:03:02 2015 +0200 @@ -24,6 +24,7 @@ import static com.oracle.graal.compiler.common.GraalOptions.*; import static com.oracle.graal.lir.LIRValueUtil.*; +import static com.oracle.graal.lir.alloc.trace.TraceLinearScan.*; import static com.oracle.graal.lir.alloc.trace.TraceRegisterAllocationPhase.Options.*; import static com.oracle.graal.lir.debug.LIRGenerationDebugContext.*; import static jdk.internal.jvmci.code.ValueUtil.*; @@ -56,7 +57,7 @@ import com.oracle.graal.lir.phases.*; import com.oracle.graal.lir.ssi.*; -class TraceLinearScanLifetimeAnalysisPhase extends AllocationPhase { +final class TraceLinearScanLifetimeAnalysisPhase extends AllocationPhase { protected final TraceLinearScan allocator; private final TraceBuilderResult<?> traceBuilderResult; @@ -75,8 +76,6 @@ RegisterAllocationConfig registerAllocationConfig) { numberInstructions(); allocator.printLir("Before register allocation", true); - computeLocalLiveSets(); - computeGlobalLiveSets(); buildIntervals(); } @@ -88,16 +87,16 @@ return traceBuilderResult.getTraceForBlock(other) <= traceBuilderResult.getTraceForBlock(currentBlock); } - static void setHint(final LIRInstruction op, TraceInterval target, TraceInterval source) { - TraceInterval currentHint = target.locationHint(false); - if (currentHint == null || currentHint.from() > target.from()) { + static void setHint(final LIRInstruction op, TraceInterval to, IntervalHint from) { + IntervalHint currentHint = to.locationHint(false); + if (currentHint == null) { /* * Update hint if there was none or if the hint interval starts after the hinted * interval. */ - target.setLocationHint(source); + to.setLocationHint(from); if (Debug.isLogEnabled()) { - Debug.log("operation at opId %d: added hint from interval %d (%s) to %d (%s)", op.id(), source.operandNumber, source, target.operandNumber, target); + Debug.log("operation at opId %d: added hint from interval %s to %s", op.id(), from, to); } } } @@ -478,7 +477,7 @@ * fixed intervals). */ for (AbstractBlockBase<?> block : allocator.sortedBlocks()) { - for (int j = 0; j <= allocator.maxRegisterNumber(); j++) { + for (int j = 0; j < allocator.numRegisters(); j++) { assert !allocator.getBlockData(block).liveIn.get(j) : "liveIn set of fixed register must be empty"; assert !allocator.getBlockData(block).liveOut.get(j) : "liveOut set of fixed register must be empty"; assert !allocator.getBlockData(block).liveGen.get(j) : "liveGen set of fixed register must be empty"; @@ -490,8 +489,25 @@ if (!allocator.isProcessed(operand)) { return; } + if (isRegister(operand)) { + addFixedUse(asRegisterValue(operand), from, to); + } else { + assert isVariable(operand) : operand; + addVariableUse(asVariable(operand), from, to, registerPriority, kind); + } + } + private void addFixedUse(RegisterValue reg, int from, int to) { + FixedInterval interval = allocator.getOrCreateFixedInterval(reg); + interval.addRange(from, to); + if (Debug.isLogEnabled()) { + Debug.log("add fixed use: %s, at %d", interval, to); + } + } + + private void addVariableUse(Variable operand, int from, int to, RegisterPriority registerPriority, LIRKind kind) { TraceInterval interval = allocator.getOrCreateInterval(operand); + if (!kind.equals(LIRKind.Illegal)) { interval.setKind(kind); } @@ -502,7 +518,7 @@ interval.addUsePos(to & ~1, registerPriority); if (Debug.isLogEnabled()) { - Debug.log("add use: %s, from %d to %d (%s)", interval, from, to, registerPriority.name()); + Debug.log("add use: %s, at %d (%s)", interval, to, registerPriority.name()); } } @@ -510,13 +526,35 @@ if (!allocator.isProcessed(operand)) { return; } + if (isRegister(operand)) { + addFixedTemp(asRegisterValue(operand), tempPos); + } else { + assert isVariable(operand) : operand; + addVariableTemp(asVariable(operand), tempPos, registerPriority, kind); + } + } + private void addFixedTemp(RegisterValue reg, int tempPos) { + FixedInterval interval = allocator.getOrCreateFixedInterval(reg); + interval.addRange(tempPos, tempPos + 1); + if (Debug.isLogEnabled()) { + Debug.log("add fixed temp: %s, at %d", interval, tempPos); + } + } + + private void addVariableTemp(Variable operand, int tempPos, RegisterPriority registerPriority, LIRKind kind) { TraceInterval interval = allocator.getOrCreateInterval(operand); + if (!kind.equals(LIRKind.Illegal)) { interval.setKind(kind); } - interval.addRange(tempPos, tempPos + 1); + if (interval.isEmpty()) { + interval.addRange(tempPos, tempPos + 1); + } else if (interval.from() > tempPos) { + interval.setFrom(tempPos); + } + interval.addUsePos(tempPos, registerPriority); interval.addMaterializationValue(null); @@ -529,23 +567,48 @@ if (!allocator.isProcessed(operand)) { return; } + if (isRegister(operand)) { + addFixedDef(asRegisterValue(operand), op); + } else { + assert isVariable(operand) : operand; + addVariableDef(asVariable(operand), op, registerPriority, kind); + } + } + + private void addFixedDef(RegisterValue reg, LIRInstruction op) { + FixedInterval interval = allocator.getOrCreateFixedInterval(reg); + int defPos = op.id(); + if (interval.from() <= defPos) { + /* + * Update the starting point (when a range is first created for a use, its start is the + * beginning of the current block until a def is encountered). + */ + interval.setFrom(defPos); + + } else { + /* + * Dead value - make vacuous interval also add register priority for dead intervals + */ + interval.addRange(defPos, defPos + 1); + if (Debug.isLogEnabled()) { + Debug.log("Warning: def of operand %s at %d occurs without use", reg, defPos); + } + } + if (Debug.isLogEnabled()) { + Debug.log("add fixed def: %s, at %d", interval, defPos); + } + } + + private void addVariableDef(Variable operand, LIRInstruction op, RegisterPriority registerPriority, LIRKind kind) { int defPos = op.id(); TraceInterval interval = allocator.getOrCreateInterval(operand); + if (!kind.equals(LIRKind.Illegal)) { interval.setKind(kind); } - Range r = interval.first(); - if (r.from <= defPos) { - /* - * Update the starting point (when a range is first created for a use, its start is the - * beginning of the current block until a def is encountered). - */ - r.from = defPos; - interval.addUsePos(defPos, registerPriority); - - } else { + if (interval.isEmpty()) { /* * Dead value - make vacuous interval also add register priority for dead intervals */ @@ -554,6 +617,13 @@ if (Debug.isLogEnabled()) { Debug.log("Warning: def of operand %s at %d occurs without use", operand, defPos); } + } else { + /* + * Update the starting point (when a range is first created for a use, its start is the + * beginning of the current block until a def is encountered). + */ + interval.setFrom(defPos); + interval.addUsePos(defPos, registerPriority); } changeSpillDefinitionPos(op, operand, interval, defPos); @@ -587,17 +657,27 @@ op.forEachRegisterHint(targetValue, mode, (registerHint, valueMode, valueFlags) -> { if (TraceLinearScan.isVariableOrRegister(registerHint)) { - TraceInterval from = allocator.getOrCreateInterval((AllocatableValue) registerHint); - TraceInterval to = allocator.getOrCreateInterval((AllocatableValue) targetValue); - + AllocatableValue fromValue; + AllocatableValue toValue; /* hints always point from def to use */ if (hintAtDef) { - to.setLocationHint(from); + fromValue = (AllocatableValue) registerHint; + toValue = (AllocatableValue) targetValue; } else { - from.setLocationHint(to); + fromValue = (AllocatableValue) targetValue; + toValue = (AllocatableValue) registerHint; + } + if (isRegister(toValue)) { + /* fixed register: no need for a hint */ + return null; } + + TraceInterval to = allocator.getOrCreateInterval(toValue); + IntervalHint from = getIntervalHint(fromValue); + + to.setLocationHint(from); if (Debug.isLogEnabled()) { - Debug.log("operation at opId %d: added hint from interval %d to %d", op.id(), from.operandNumber, to.operandNumber); + Debug.log("operation at opId %d: added hint from interval %s to %s", op.id(), from, to); } return registerHint; @@ -607,6 +687,13 @@ } } + private IntervalHint getIntervalHint(AllocatableValue from) { + if (isRegister(from)) { + return allocator.getOrCreateFixedInterval(asRegisterValue(from)); + } + return allocator.getOrCreateInterval(from); + } + /** * Eliminates moves from register to stack if the stack slot is known to be correct. * @@ -657,7 +744,7 @@ /** * Determines the register priority for an instruction's output/result operand. */ - protected RegisterPriority registerPriorityOfOutputOperand(LIRInstruction op) { + protected static RegisterPriority registerPriorityOfOutputOperand(LIRInstruction op) { if (op instanceof LabelOp) { // skip method header return RegisterPriority.None; @@ -718,8 +805,8 @@ InstructionValueConsumer inputConsumer = (op, operand, mode, flags) -> { if (TraceLinearScan.isVariableOrRegister(operand)) { int opId = op.id(); + RegisterPriority p = registerPriorityOfInputOperand(flags); int blockFrom = allocator.getFirstLirInstructionId((allocator.blockForId(opId))); - RegisterPriority p = registerPriorityOfInputOperand(flags); addUse((AllocatableValue) operand, blockFrom, opId, p, operand.getLIRKind()); addRegisterHint(op, operand, mode, flags, false); } @@ -740,35 +827,12 @@ for (int i = allocator.blockCount() - 1; i >= 0; i--) { AbstractBlockBase<?> block = allocator.blockAt(i); + // TODO (je) make empty bitset - remove + allocator.getBlockData(block).liveIn = new BitSet(); + allocator.getBlockData(block).liveOut = new BitSet(); try (Indent indent2 = Debug.logAndIndent("handle block %d", block.getId())) { List<LIRInstruction> instructions = allocator.getLIR().getLIRforBlock(block); - final int blockFrom = allocator.getFirstLirInstructionId(block); - int blockTo = allocator.getLastLirInstructionId(block); - - assert blockFrom == instructions.get(0).id(); - assert blockTo == instructions.get(instructions.size() - 1).id(); - - // Update intervals for operands live at the end of this block; - BitSet live = allocator.getBlockData(block).liveOut; - for (int operandNum = live.nextSetBit(0); operandNum >= 0; operandNum = live.nextSetBit(operandNum + 1)) { - assert live.get(operandNum) : "should not stop here otherwise"; - AllocatableValue operand = allocator.intervalFor(operandNum).operand; - if (Debug.isLogEnabled()) { - Debug.log("live in %d: %s", operandNum, operand); - } - - addUse(operand, blockFrom, blockTo + 2, RegisterPriority.None, LIRKind.Illegal); - - /* - * Add special use positions for loop-end blocks when the interval is used - * anywhere inside this loop. It's possible that the block was part of a - * non-natural loop, so it might have an invalid loop index. - */ - if (block.isLoopEnd() && block.getLoop() != null && isIntervalInLoop(operandNum, block.getLoop().getIndex())) { - allocator.intervalFor(operandNum).addUsePos(blockTo + 1, RegisterPriority.LiveAtLoopEnd); - } - } /* * Iterate all instructions of the block in reverse order. definitions of @@ -813,31 +877,29 @@ } // end of instruction iteration } + allocator.printIntervals("After Block " + block); } // end of block iteration - /* - * Add the range [0, 1] to all fixed intervals. the register allocator need not handle - * unhandled fixed intervals. - */ + // fix spill state for phi/sigma intervals for (TraceInterval interval : allocator.intervals()) { - if (interval != null && isRegister(interval.operand)) { - interval.addRange(0, 1); + if (interval != null && interval.spillState().equals(SpillState.NoDefinitionFound) && interval.spillDefinitionPos() != -1) { + // there was a definition in a phi/sigma + interval.setSpillState(SpillState.NoSpillStore); } } - } - postBuildIntervals(); - } - - protected void postBuildIntervals() { - // fix spill state for phi/sigma 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); + if (TraceRAuseInterTraceHints.getValue()) { + addInterTraceHints(); } - } - if (TraceRAuseInterTraceHints.getValue()) { - addInterTraceHints(); + /* + * Add the range [-1, 0] to all fixed intervals. the register allocator need not handle + * unhandled fixed intervals. + */ + for (FixedInterval interval : allocator.fixedIntervals()) { + if (interval != null) { + /* We use [-1, 0] to avoid intersection with incoming values. */ + interval.addRange(-1, 0); + } + } } } @@ -851,17 +913,17 @@ BlockEndOp outgoing = SSIUtil.outgoing(lir, pred); for (int i = 0; i < outgoing.getOutgoingSize(); i++) { Value toValue = label.getIncomingValue(i); - if (!isIllegal(toValue)) { + if (!isIllegal(toValue) && !isRegister(toValue)) { Value fromValue = outgoing.getOutgoingValue(i); assert sameTrace(block, pred) || !isVariable(fromValue) : "Unallocated variable: " + fromValue; - if (isRegister(fromValue) || isVariable(fromValue)) { - TraceInterval from = allocator.getOrCreateInterval((AllocatableValue) fromValue); + if (isVariableOrRegister(fromValue)) { + IntervalHint from = getIntervalHint((AllocatableValue) fromValue); TraceInterval to = allocator.getOrCreateInterval((AllocatableValue) toValue); setHint(label, to, from); } else if (TraceRAshareSpillInformation.getValue() && TraceUtil.isShadowedRegisterValue(fromValue)) { ShadowedRegisterValue shadowedRegisterValue = TraceUtil.asShadowedRegisterValue(fromValue); - TraceInterval from = allocator.getOrCreateInterval(shadowedRegisterValue.getRegister()); + IntervalHint from = getIntervalHint(shadowedRegisterValue.getRegister()); TraceInterval to = allocator.getOrCreateInterval((AllocatableValue) toValue); setHint(label, to, from); to.setSpillSlot(shadowedRegisterValue.getStackSlot()); @@ -872,21 +934,6 @@ } } } - /* - * Set the first range for fixed intervals to [-1, 0] to avoid intersection with incoming - * values. - */ - for (TraceInterval interval : allocator.intervals()) { - if (interval != null && isRegister(interval.operand)) { - Range range = interval.first(); - if (range == Range.EndMarker) { - interval.addRange(-1, 0); - } else if (range.from == 0 && range.to == 1) { - range.from = -1; - range.to = 0; - } - } - } } /** @@ -909,7 +956,7 @@ * degradation, because rematerialization always inserts a constant load, even if * the value is not needed in a register. */ - TraceInterval.UsePosList usePosList = interval.usePosList(); + UsePosList usePosList = interval.usePosList(); int numUsePos = usePosList.size(); for (int useIdx = 0; useIdx < numUsePos; useIdx++) { TraceInterval.RegisterPriority priority = usePosList.registerPriority(useIdx);
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanOptimizeSpillPositionPhase.java Thu Sep 03 19:01:59 2015 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,234 +0,0 @@ -/* - * Copyright (c) 2015, 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.cfg.AbstractControlFlowGraph.*; -import static jdk.internal.jvmci.code.ValueUtil.*; - -import java.util.*; - -import jdk.internal.jvmci.code.*; -import com.oracle.graal.debug.*; -import jdk.internal.jvmci.meta.*; - -import com.oracle.graal.compiler.common.alloc.*; -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.TraceInterval.SpillState; -import com.oracle.graal.lir.gen.*; -import com.oracle.graal.lir.gen.LIRGeneratorTool.SpillMoveFactory; -import com.oracle.graal.lir.phases.*; - -final class TraceLinearScanOptimizeSpillPositionPhase extends AllocationPhase { - - private static final DebugMetric betterSpillPos = Debug.metric("BetterSpillPosition"); - private static final DebugMetric betterSpillPosWithLowerProbability = Debug.metric("BetterSpillPositionWithLowerProbability"); - - private final TraceLinearScan allocator; - - TraceLinearScanOptimizeSpillPositionPhase(TraceLinearScan allocator) { - this.allocator = allocator; - } - - @Override - protected <B extends AbstractBlockBase<B>> void run(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder, SpillMoveFactory spillMoveFactory, - RegisterAllocationConfig registerAllocationConfig) { - optimizeSpillPosition(); - allocator.printIntervals("After optimize spill position"); - } - - @SuppressWarnings("try") - private void optimizeSpillPosition() { - try (Indent indent0 = Debug.logAndIndent("OptimizeSpillPositions")) { - LIRInsertionBuffer[] insertionBuffers = new LIRInsertionBuffer[allocator.getLIR().linearScanOrder().size()]; - for (TraceInterval interval : allocator.intervals()) { - optimizeInterval(insertionBuffers, interval); - } - for (LIRInsertionBuffer insertionBuffer : insertionBuffers) { - if (insertionBuffer != null) { - assert insertionBuffer.initialized() : "Insertion buffer is nonnull but not initialized!"; - insertionBuffer.finish(); - } - } - } - } - - @SuppressWarnings("try") - 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; - TraceInterval firstSpillChild = null; - try (Indent indent = Debug.logAndIndent("interval %s (%s)", interval, defBlock)) { - for (TraceInterval splitChild : interval.getSplitChildren()) { - if (isStackSlotValue(splitChild.location())) { - if (firstSpillChild == null || splitChild.from() < firstSpillChild.from()) { - firstSpillChild = splitChild; - } else { - assert firstSpillChild.from() < splitChild.from(); - } - // iterate all blocks where the interval has use positions - for (AbstractBlockBase<?> splitBlock : blocksForInterval(splitChild)) { - if (dominates(defBlock, splitBlock)) { - Debug.log("Split interval %s, block %s", splitChild, splitBlock); - if (spillBlock == null) { - spillBlock = splitBlock; - } else { - spillBlock = commonDominator(spillBlock, splitBlock); - assert spillBlock != null; - } - } - } - } - } - if (spillBlock == null) { - Debug.log("not spill interval found"); - // no spill interval - interval.setSpillState(SpillState.StoreAtDefinition); - return; - } - Debug.log(3, "Spill block candidate (initial): %s", spillBlock); - // move out of loops - if (defBlock.getLoopDepth() < spillBlock.getLoopDepth()) { - spillBlock = moveSpillOutOfLoop(defBlock, spillBlock); - } - Debug.log(3, "Spill block candidate (after loop optimizaton): %s", spillBlock); - - /* - * The spill block is the begin of the first split child (aka the value is on the - * stack). - * - * The problem is that if spill block has more than one predecessor, the values at the - * end of the predecessors might differ. Therefore, we would need a spill move in all - * predecessors. To avoid this we spill in the dominator. - */ - assert firstSpillChild != null; - if (!defBlock.equals(spillBlock) && spillBlock.equals(allocator.blockForId(firstSpillChild.from()))) { - AbstractBlockBase<?> dom = spillBlock.getDominator(); - if (Debug.isLogEnabled()) { - Debug.log("Spill block (%s) is the beginning of a spill child -> use dominator (%s)", spillBlock, dom); - } - spillBlock = dom; - } - if (defBlock.equals(spillBlock)) { - Debug.log(3, "Definition is the best choice: %s", defBlock); - // definition is the best choice - interval.setSpillState(SpillState.StoreAtDefinition); - return; - } - assert dominates(defBlock, spillBlock); - betterSpillPos.increment(); - if (Debug.isLogEnabled()) { - Debug.log("Better spill position found (Block %s)", spillBlock); - } - - if (defBlock.probability() <= spillBlock.probability()) { - Debug.log(3, "Definition has lower probability %s (%f) is lower than spill block %s (%f)", defBlock, defBlock.probability(), spillBlock, spillBlock.probability()); - // better spill block has the same probability -> do nothing - interval.setSpillState(SpillState.StoreAtDefinition); - return; - } - - LIRInsertionBuffer insertionBuffer = insertionBuffers[spillBlock.getId()]; - if (insertionBuffer == null) { - insertionBuffer = new LIRInsertionBuffer(); - insertionBuffers[spillBlock.getId()] = insertionBuffer; - insertionBuffer.init(allocator.getLIR().getLIRforBlock(spillBlock)); - } - int spillOpId = allocator.getFirstLirInstructionId(spillBlock); - // insert spill move - AllocatableValue fromLocation = interval.getSplitChildAtOpId(spillOpId, OperandMode.DEF, allocator).location(); - AllocatableValue toLocation = TraceLinearScan.canonicalSpillOpr(interval); - LIRInstruction move = allocator.getSpillMoveFactory().createMove(toLocation, fromLocation); - Debug.log(3, "Insert spill move %s", move); - move.setId(TraceLinearScan.DOMINATOR_SPILL_MOVE_ID); - /* - * We can use the insertion buffer directly because we always insert at position 1. - */ - insertionBuffer.append(1, move); - - betterSpillPosWithLowerProbability.increment(); - interval.setSpillDefinitionPos(spillOpId); - } - } - - /** - * Iterate over all {@link AbstractBlockBase blocks} of an interval. - */ - private class IntervalBlockIterator implements Iterator<AbstractBlockBase<?>> { - - Range range; - AbstractBlockBase<?> block; - - public IntervalBlockIterator(TraceInterval interval) { - range = interval.first(); - block = allocator.blockForId(range.from); - } - - public AbstractBlockBase<?> next() { - AbstractBlockBase<?> currentBlock = block; - int nextBlockIndex = block.getLinearScanNumber() + 1; - if (nextBlockIndex < allocator.sortedBlocks().size()) { - block = allocator.sortedBlocks().get(nextBlockIndex); - if (range.to <= allocator.getFirstLirInstructionId(block)) { - range = range.next; - if (range == Range.EndMarker) { - block = null; - } else { - block = allocator.blockForId(range.from); - } - } - } else { - block = null; - } - return currentBlock; - } - - public boolean hasNext() { - return block != null; - } - } - - private Iterable<AbstractBlockBase<?>> blocksForInterval(TraceInterval interval) { - return new Iterable<AbstractBlockBase<?>>() { - public Iterator<AbstractBlockBase<?>> iterator() { - return new IntervalBlockIterator(interval); - } - }; - } - - private static AbstractBlockBase<?> moveSpillOutOfLoop(AbstractBlockBase<?> defBlock, AbstractBlockBase<?> spillBlock) { - int defLoopDepth = defBlock.getLoopDepth(); - for (AbstractBlockBase<?> block = spillBlock.getDominator(); !defBlock.equals(block); block = block.getDominator()) { - assert block != null : "spill block not dominated by definition block?"; - if (block.getLoopDepth() <= defLoopDepth) { - assert block.getLoopDepth() == defLoopDepth : "Cannot spill an interval outside of the loop where it is defined!"; - return block; - } - } - return defBlock; - } -}
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanRegisterAllocationPhase.java Thu Sep 03 19:01:59 2015 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanRegisterAllocationPhase.java Mon Sep 07 16:03:02 2015 +0200 @@ -25,8 +25,8 @@ import java.util.*; import jdk.internal.jvmci.code.*; + import com.oracle.graal.debug.*; - import com.oracle.graal.compiler.common.alloc.*; import com.oracle.graal.compiler.common.cfg.*; import com.oracle.graal.lir.gen.*; @@ -52,12 +52,8 @@ @SuppressWarnings("try") void allocateRegisters() { try (Indent indent = Debug.logAndIndent("allocate registers")) { - TraceInterval precoloredIntervals; - TraceInterval notPrecoloredIntervals; - - TraceInterval.Pair result = allocator.createUnhandledLists(TraceLinearScan.IS_PRECOLORED_INTERVAL, TraceLinearScan.IS_VARIABLE_INTERVAL); - precoloredIntervals = result.first; - notPrecoloredIntervals = result.second; + FixedInterval precoloredIntervals = allocator.createFixedUnhandledList(); + TraceInterval notPrecoloredIntervals = allocator.createUnhandledList(TraceLinearScan.IS_VARIABLE_INTERVAL); // allocate cpu registers TraceLinearScanWalker lsw = new TraceLinearScanWalker(allocator, precoloredIntervals, notPrecoloredIntervals);
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanWalker.java Thu Sep 03 19:01:59 2015 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanWalker.java Mon Sep 07 16:03:02 2015 +0200 @@ -29,6 +29,7 @@ import java.util.*; import jdk.internal.jvmci.code.*; +import jdk.internal.jvmci.common.*; import jdk.internal.jvmci.meta.*; import com.oracle.graal.compiler.common.alloc.RegisterAllocationConfig.AllocatableRegisters; @@ -38,7 +39,6 @@ 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.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; @@ -47,12 +47,12 @@ */ final class TraceLinearScanWalker extends TraceIntervalWalker { - protected Register[] availableRegs; + private Register[] availableRegs; - protected final int[] usePos; - protected final int[] blockPos; + private final int[] usePos; + private final int[] blockPos; - protected List<TraceInterval>[] spillIntervals; + private List<TraceInterval>[] spillIntervals; private TraceLocalMoveResolver moveResolver; // for ordering spill moves @@ -69,19 +69,20 @@ private static final List<TraceInterval> EMPTY_LIST = new ArrayList<>(0); // accessors mapped to same functions in class LinearScan - int blockCount() { + private int blockCount() { return allocator.blockCount(); } - AbstractBlockBase<?> blockAt(int idx) { + private AbstractBlockBase<?> blockAt(int idx) { return allocator.blockAt(idx); } - AbstractBlockBase<?> blockOfOpWithId(int opId) { + @SuppressWarnings("unused") + private AbstractBlockBase<?> blockOfOpWithId(int opId) { return allocator.blockForId(opId); } - TraceLinearScanWalker(TraceLinearScan allocator, TraceInterval unhandledFixedFirst, TraceInterval unhandledAnyFirst) { + TraceLinearScanWalker(TraceLinearScan allocator, FixedInterval unhandledFixedFirst, TraceInterval unhandledAnyFirst) { super(allocator, unhandledFixedFirst, unhandledAnyFirst); moveResolver = allocator.createMoveResolver(); @@ -93,7 +94,7 @@ blockPos = new int[allocator.getRegisters().length]; } - void initUseLists(boolean onlyProcessUsePos) { + private void initUseLists(boolean onlyProcessUsePos) { for (Register register : availableRegs) { int i = register.number; usePos[i] = Integer.MAX_VALUE; @@ -105,19 +106,19 @@ } } - int maxRegisterNumber() { + private int maxRegisterNumber() { return maxReg; } - int minRegisterNumber() { + private int minRegisterNumber() { return minReg; } - boolean isRegisterInRange(int reg) { + private boolean isRegisterInRange(int reg) { return reg >= minRegisterNumber() && reg <= maxRegisterNumber(); } - void excludeFromUse(TraceInterval i) { + private void excludeFromUse(IntervalHint i) { Value location = i.location(); int i1 = asRegister(location).number; if (isRegisterInRange(i1)) { @@ -125,7 +126,7 @@ } } - void setUsePos(TraceInterval interval, int usePos, boolean onlyProcessUsePos) { + private 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; @@ -145,7 +146,20 @@ } } - void setBlockPos(TraceInterval i, int blockPos) { + private void setUsePos(FixedInterval interval, int usePos, boolean onlyProcessUsePos) { + assert onlyProcessUsePos; + if (usePos != -1) { + assert usePos != 0 : "must use excludeFromUse to set usePos to 0"; + int i = asRegister(interval.location()).number; + if (isRegisterInRange(i)) { + if (this.usePos[i] > usePos) { + this.usePos[i] = usePos; + } + } + } + } + + private void setBlockPos(IntervalHint i, int blockPos) { if (blockPos != -1) { int reg = asRegister(i.location()).number; if (isRegisterInRange(reg)) { @@ -159,8 +173,17 @@ } } - void freeExcludeActiveFixed() { - TraceInterval interval = activeLists.get(RegisterBinding.Fixed); + private void freeExcludeActiveFixed() { + FixedInterval interval = activeFixedList.getFixed(); + while (interval != FixedInterval.EndMarker) { + assert isRegister(interval.location()) : "active interval must have a register assigned"; + excludeFromUse(interval); + interval = interval.next; + } + } + + private void freeExcludeActiveAny() { + TraceInterval interval = activeAnyList.getAny(); while (interval != TraceInterval.EndMarker) { assert isRegister(interval.location()) : "active interval must have a register assigned"; excludeFromUse(interval); @@ -168,21 +191,12 @@ } } - void freeExcludeActiveAny() { - 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(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); + private void freeCollectInactiveFixed(TraceInterval current) { + FixedInterval interval = inactiveFixedList.getFixed(); + while (interval != FixedInterval.EndMarker) { + if (current.to() <= interval.from()) { + assert interval.intersectsAt(current) == -1 : "must not intersect"; + setUsePos(interval, interval.from(), true); } else { setUsePos(interval, interval.currentIntersectsAt(current), true); } @@ -190,44 +204,17 @@ } } - 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, 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); - } - interval = interval.next; - } - } - - void spillExcludeActiveFixed() { - TraceInterval interval = activeLists.get(RegisterBinding.Fixed); - while (interval != TraceInterval.EndMarker) { + private void spillExcludeActiveFixed() { + FixedInterval interval = activeFixedList.getFixed(); + while (interval != FixedInterval.EndMarker) { excludeFromUse(interval); interval = interval.next; } } - void spillBlockUnhandledFixed(TraceInterval current) { - TraceInterval interval = unhandledLists.get(RegisterBinding.Fixed); - while (interval != TraceInterval.EndMarker) { - setBlockPos(interval, interval.intersectsAt(current)); - interval = interval.next; - } - } - - void spillBlockInactiveFixed(TraceInterval current) { - TraceInterval interval = inactiveLists.get(RegisterBinding.Fixed); - while (interval != TraceInterval.EndMarker) { + private void spillBlockInactiveFixed(TraceInterval current) { + FixedInterval interval = inactiveFixedList.getFixed(); + while (interval != FixedInterval.EndMarker) { if (current.to() > interval.currentFrom()) { setBlockPos(interval, interval.currentIntersectsAt(current)); } else { @@ -238,25 +225,15 @@ } } - void spillCollectActiveAny(RegisterPriority registerPriority) { - TraceInterval interval = activeLists.get(RegisterBinding.Any); + private void spillCollectActiveAny(RegisterPriority registerPriority) { + TraceInterval interval = activeAnyList.getAny(); while (interval != TraceInterval.EndMarker) { setUsePos(interval, Math.min(interval.nextUsage(registerPriority, currentPosition), interval.to()), false); interval = interval.next; } } - 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); - } - interval = interval.next; - } - } - - void insertMove(int operandId, TraceInterval srcIt, TraceInterval dstIt) { + private 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 @@ -285,7 +262,8 @@ moveResolver.addMapping(srcIt, dstIt); } - int findOptimalSplitPos(AbstractBlockBase<?> minBlock, AbstractBlockBase<?> maxBlock, int maxSplitPos) { + @SuppressWarnings("unused") + private int findOptimalSplitPos(AbstractBlockBase<?> minBlock, AbstractBlockBase<?> maxBlock, int maxSplitPos) { int fromBlockNr = minBlock.getLinearScanNumber(); int toBlockNr = maxBlock.getLinearScanNumber(); @@ -315,108 +293,13 @@ return optimalSplitPos; } - int findOptimalSplitPos(TraceInterval interval, int minSplitPos, int maxSplitPos, boolean doLoopOptimization) { - int optimalSplitPos = -1; - if (minSplitPos == maxSplitPos) { - // trivial case, no optimization of split position possible - if (Debug.isLogEnabled()) { - Debug.log("min-pos and max-pos are equal, no optimization possible"); - } - optimalSplitPos = minSplitPos; - - } else { - assert minSplitPos < maxSplitPos : "must be true then"; - assert minSplitPos > 0 : "cannot access minSplitPos - 1 otherwise"; - - // reason for using minSplitPos - 1: when the minimal split pos is exactly at the - // beginning of a block, then minSplitPos is also a possible split position. - // Use the block before as minBlock, because then minBlock.lastLirInstructionId() + 2 == - // minSplitPos - AbstractBlockBase<?> minBlock = allocator.blockForId(minSplitPos - 1); - - // reason for using maxSplitPos - 1: otherwise there would be an assert on failure - // when an interval ends at the end of the last block of the method - // (in this case, maxSplitPos == allocator().maxLirOpId() + 2, and there is no - // block at this opId) - AbstractBlockBase<?> maxBlock = allocator.blockForId(maxSplitPos - 1); - - assert minBlock.getLinearScanNumber() <= maxBlock.getLinearScanNumber() : "invalid order"; - if (minBlock == maxBlock) { - // split position cannot be moved to block boundary : so split as late as possible - if (Debug.isLogEnabled()) { - Debug.log("cannot move split pos to block boundary because minPos and maxPos are in same block"); - } - optimalSplitPos = maxSplitPos; - - } else { - if (interval.hasHoleBetween(maxSplitPos - 1, maxSplitPos) && !allocator.isBlockBegin(maxSplitPos)) { - // Do not move split position if the interval has a hole before maxSplitPos. - // Intervals resulting from Phi-Functions have more than one definition (marked - // as mustHaveRegister) with a hole before each definition. When the register is - // needed - // for the second definition : an earlier reloading is unnecessary. - if (Debug.isLogEnabled()) { - Debug.log("interval has hole just before maxSplitPos, so splitting at maxSplitPos"); - } - optimalSplitPos = maxSplitPos; - - } else { - // seach optimal block boundary between minSplitPos and maxSplitPos - if (Debug.isLogEnabled()) { - Debug.log("moving split pos to optimal block boundary between block B%d and B%d", minBlock.getId(), maxBlock.getId()); - } - - if (doLoopOptimization) { - // Loop optimization: if a loop-end marker is found between min- and - // max-position : - // then split before this loop - int loopEndPos = interval.nextUsageExact(RegisterPriority.LiveAtLoopEnd, allocator.getLastLirInstructionId(minBlock) + 2); - if (Debug.isLogEnabled()) { - Debug.log("loop optimization: loop end found at pos %d", loopEndPos); - } - - assert loopEndPos > minSplitPos : "invalid order"; - if (loopEndPos < maxSplitPos) { - // loop-end marker found between min- and max-position - // if it is not the end marker for the same loop as the min-position : - // then move - // the max-position to this loop block. - // Desired result: uses tagged as shouldHaveRegister inside a loop cause - // a reloading - // of the interval (normally, only mustHaveRegister causes a reloading) - AbstractBlockBase<?> loopBlock = allocator.blockForId(loopEndPos); - - if (Debug.isLogEnabled()) { - Debug.log("interval is used in loop that ends in block B%d, so trying to move maxBlock back from B%d to B%d", loopBlock.getId(), maxBlock.getId(), loopBlock.getId()); - } - assert loopBlock != minBlock : "loopBlock and minBlock must be different because block boundary is needed between"; - - int maxSpillPos = allocator.getLastLirInstructionId(loopBlock) + 2; - optimalSplitPos = findOptimalSplitPos(minBlock, loopBlock, maxSpillPos); - if (optimalSplitPos == maxSpillPos) { - optimalSplitPos = -1; - if (Debug.isLogEnabled()) { - Debug.log("loop optimization not necessary"); - } - } else { - if (Debug.isLogEnabled()) { - Debug.log("loop optimization successful"); - } - } - } - } - - if (optimalSplitPos == -1) { - // not calculated by loop optimization - optimalSplitPos = findOptimalSplitPos(minBlock, maxBlock, maxSplitPos); - } - } - } - } + @SuppressWarnings({"static-method", "unused"}) + private int findOptimalSplitPos(TraceInterval interval, int minSplitPos, int maxSplitPos, boolean doLoopOptimization) { + // TODO (je) implement + int optimalSplitPos = maxSplitPos; if (Debug.isLogEnabled()) { Debug.log("optimal split position: %d", optimalSplitPos); } - return optimalSplitPos; } @@ -425,7 +308,7 @@ // 1) the left part has already a location assigned // 2) the right part is sorted into to the unhandled-list @SuppressWarnings("try") - void splitBeforeUsage(TraceInterval interval, int minSplitPos, int maxSplitPos) { + private void splitBeforeUsage(TraceInterval interval, int minSplitPos, int maxSplitPos) { try (Indent indent = Debug.logAndIndent("splitting interval %s between %d and %d", interval, minSplitPos, maxSplitPos)) { @@ -451,9 +334,10 @@ // must calculate this before the actual split is performed and before split position is // moved to odd opId - boolean moveNecessary = !allocator.isBlockBegin(optimalSplitPos) && !interval.hasHoleBetween(optimalSplitPos - 1, optimalSplitPos); + boolean isBlockBegin = allocator.isBlockBegin(optimalSplitPos); + boolean moveNecessary = !isBlockBegin; - if (!allocator.isBlockBegin(optimalSplitPos)) { + if (!isBlockBegin) { // move position before actual instruction (odd opId) optimalSplitPos = (optimalSplitPos - 1) | 1; } @@ -462,15 +346,15 @@ Debug.log("splitting at position %d", optimalSplitPos); } - 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"; + assert isBlockBegin || ((optimalSplitPos & 1) == 1) : "split pos must be odd when not on block boundary"; + assert !isBlockBegin || ((optimalSplitPos & 1) == 0) : "split pos must be even on block boundary"; TraceInterval splitPart = interval.split(optimalSplitPos, allocator); splitPart.setInsertMoveWhenActivated(moveNecessary); assert splitPart.from() >= currentPosition : "cannot append new interval before current walk position"; - unhandledLists.addToListSortedByStartAndUsePositions(RegisterBinding.Any, splitPart); + unhandledAnyList.addToListSortedByStartAndUsePositions(splitPart); if (Debug.isLogEnabled()) { Debug.log("left interval %s: %s", moveNecessary ? " " : "", interval.logString(allocator)); @@ -484,7 +368,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 @SuppressWarnings("try") - void splitForSpilling(TraceInterval interval) { + private void splitForSpilling(TraceInterval interval) { // calculate allowed range of splitting position int maxSplitPos = currentPosition; int previousUsage = interval.previousUsage(RegisterPriority.ShouldHaveRegister, maxSplitPos); @@ -640,24 +524,24 @@ /** * This is called for every interval that is assigned to a stack slot. */ - protected static void handleSpillSlot(TraceInterval interval) { + private 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(TraceInterval interval) { + private void splitStackInterval(TraceInterval interval) { int minSplitPos = currentPosition + 1; int maxSplitPos = Math.min(interval.firstUsage(RegisterPriority.ShouldHaveRegister), interval.to()); splitBeforeUsage(interval, minSplitPos, maxSplitPos); } - void splitWhenPartialRegisterAvailable(TraceInterval interval, int registerAvailableUntil) { + private void splitWhenPartialRegisterAvailable(TraceInterval interval, int registerAvailableUntil) { int minSplitPos = Math.max(interval.previousUsage(RegisterPriority.ShouldHaveRegister, registerAvailableUntil), interval.from() + 1); splitBeforeUsage(interval, minSplitPos, registerAvailableUntil); } - void splitAndSpillInterval(TraceInterval interval) { + private void splitAndSpillInterval(TraceInterval interval) { assert interval.state == State.Active || interval.state == State.Inactive : "other states not allowed"; int currentPos = currentPosition; @@ -665,8 +549,7 @@ // the interval is currently inactive, so no spill slot is needed for now. // when the split part is activated, the interval has a new chance to get a register, // so in the best case no stack slot is necessary - assert interval.hasHoleBetween(currentPos - 1, currentPos + 1) : "interval can not be inactive otherwise"; - splitBeforeUsage(interval, currentPos + 1, currentPos + 1); + throw JVMCIError.shouldNotReachHere("TraceIntervals can not be inactive!"); } else { // search the position where the interval must have a register and split @@ -684,16 +567,14 @@ } @SuppressWarnings("try") - boolean allocFreeRegister(TraceInterval interval) { + private boolean allocFreeRegister(TraceInterval interval) { try (Indent indent = Debug.logAndIndent("trying to find free register for %s", interval)) { initUseLists(true); freeExcludeActiveFixed(); + freeCollectInactiveFixed(interval); freeExcludeActiveAny(); - freeCollectInactiveFixed(interval); - freeCollectInactiveAny(interval); // freeCollectUnhandled(fixedKind, cur); - 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) @@ -704,17 +585,17 @@ try (Indent indent2 = Debug.logAndIndent("state of registers:")) { for (Register register : availableRegs) { int i = register.number; - Debug.log("reg %d: usePos: %d", register.number, usePos[i]); + Debug.log("reg %d (%s): usePos: %d", register.number, register, usePos[i]); } } } Register hint = null; - TraceInterval locationHint = interval.locationHint(true); + IntervalHint locationHint = interval.locationHint(true); if (locationHint != null && locationHint.location() != null && isRegister(locationHint.location())) { hint = asRegister(locationHint.location()); if (Debug.isLogEnabled()) { - Debug.log("hint register %d from interval %s", hint.number, locationHint); + Debug.log("hint register %3d (%4s) from interval %s", hint.number, hint, locationHint); } } assert interval.location() == null : "register already assigned to interval"; @@ -757,7 +638,7 @@ splitPos = usePos[reg.number]; interval.assignLocation(reg.asValue(interval.kind())); if (Debug.isLogEnabled()) { - Debug.log("selected register %d", reg.number); + Debug.log("selected register %d (%s)", reg.number, reg); } assert splitPos > 0 : "invalid splitPos"; @@ -770,7 +651,7 @@ } } - void splitAndSpillIntersectingIntervals(Register reg) { + private void splitAndSpillIntersectingIntervals(Register reg) { assert reg != null : "no register assigned"; for (int i = 0; i < spillIntervals[reg.number].size(); i++) { @@ -782,7 +663,7 @@ // Split an Interval and spill it to memory so that cur can be placed in a register @SuppressWarnings("try") - void allocLockedRegister(TraceInterval interval) { + private 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 @@ -805,10 +686,8 @@ initUseLists(false); spillExcludeActiveFixed(); // spillBlockUnhandledFixed(cur); - 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); if (Debug.isLogEnabled()) { printRegisterState(); } @@ -884,7 +763,7 @@ } @SuppressWarnings("try") - void printRegisterState() { + private void printRegisterState() { try (Indent indent2 = Debug.logAndIndent("state of registers:")) { for (Register reg : availableRegs) { int i = reg.number; @@ -897,7 +776,7 @@ } } - boolean noAllocationPossible(TraceInterval interval) { + private 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 @@ -914,7 +793,8 @@ } // safety check that there is really no register available - assert !allocFreeRegister(interval) : "found a register for this interval"; + // TODO (je): fix + // assert !allocFreeRegister(interval) : "found a register for this interval"; return true; } } @@ -922,14 +802,14 @@ return false; } - void initVarsForAlloc(TraceInterval interval) { + private 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, TraceInterval from, TraceInterval to) { + private static boolean isMove(LIRInstruction op, TraceInterval from, TraceInterval to) { if (op instanceof ValueMoveOp) { ValueMoveOp move = (ValueMoveOp) op; if (isVariable(move.getInput()) && isVariable(move.getResult())) { @@ -941,17 +821,17 @@ // optimization (especially for phi functions of nested loops): // assign same spill slot to non-intersecting intervals - void combineSpilledIntervals(TraceInterval interval) { + private void combineSpilledIntervals(TraceInterval interval) { if (interval.isSplitChild()) { // optimization is only suitable for split parents return; } - TraceInterval registerHint = interval.locationHint(false); - if (registerHint == null) { - // cur is not the target of a move : otherwise registerHint would be set + IntervalHint locationHint = interval.locationHint(false); + if (locationHint == null || !(locationHint instanceof TraceInterval)) { return; } + TraceInterval registerHint = (TraceInterval) locationHint; assert registerHint.isSplitParent() : "register hint must be split parent"; if (interval.spillState() != SpillState.NoOptimization || registerHint.spillState() != SpillState.NoOptimization) { @@ -1002,6 +882,9 @@ @Override @SuppressWarnings("try") protected boolean activateCurrent(TraceInterval interval) { + if (Debug.isLogEnabled()) { + logCurrentStatus(); + } boolean result = true; try (Indent indent = Debug.logAndIndent("activating interval %s, splitParent: %d", interval, interval.splitParent().operandNumber)) { @@ -1060,7 +943,7 @@ return result; // true = interval is moved to active list } - public void finishAllocation() { + void finishAllocation() { // must be called when all intervals are allocated moveResolver.resolveAndAppendMoves(); }
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceSimpleLifetimeAnalysisPhase.java Thu Sep 03 19:01:59 2015 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,282 +0,0 @@ -/* - * Copyright (c) 2015, 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 jdk.internal.jvmci.code.ValueUtil.*; - -import java.util.*; - -import jdk.internal.jvmci.code.*; -import jdk.internal.jvmci.meta.*; - -import com.oracle.graal.compiler.common.alloc.*; -import com.oracle.graal.compiler.common.alloc.TraceBuilder.TraceBuilderResult; -import com.oracle.graal.compiler.common.cfg.*; -import com.oracle.graal.debug.*; -import com.oracle.graal.lir.*; -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; - -final class TraceSimpleLifetimeAnalysisPhase extends TraceLinearScanLifetimeAnalysisPhase { - - public TraceSimpleLifetimeAnalysisPhase(TraceLinearScan allocator, TraceBuilderResult<?> traceBuilderResult) { - super(allocator, traceBuilderResult); - } - - @Override - protected <B extends AbstractBlockBase<B>> void run(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder, SpillMoveFactory spillMoveFactory, - RegisterAllocationConfig registerAllocationConfig) { - numberInstructions(); - allocator.printLir("Before register allocation", true); - buildIntervals(); - } - - @Override - protected void addUse(AllocatableValue operand, int from, int to, RegisterPriority registerPriority, LIRKind kind) { - if (!allocator.isProcessed(operand)) { - return; - } - if (isRegister(operand)) { - super.addUse(operand, from, to, registerPriority, kind); - return; - } - - TraceInterval interval = allocator.getOrCreateInterval(operand); - if (!kind.equals(LIRKind.Illegal)) { - interval.setKind(kind); - } - - Range r = interval.first(); - if (r == Range.EndMarker) { - interval.addRange(from, to); - } else if (r.from > from) { - r.from = from; - } - - // Register use position at even instruction id. - interval.addUsePos(to & ~1, registerPriority); - - if (Debug.isLogEnabled()) { - Debug.log("add use: %s, at %d (%s)", interval, to, registerPriority.name()); - } - } - - @Override - protected void addTemp(AllocatableValue operand, int tempPos, RegisterPriority registerPriority, LIRKind kind) { - if (!allocator.isProcessed(operand)) { - return; - } - if (isRegister(operand)) { - super.addTemp(operand, tempPos, registerPriority, kind); - return; - } - - TraceInterval interval = allocator.getOrCreateInterval(operand); - if (!kind.equals(LIRKind.Illegal)) { - interval.setKind(kind); - } - - Range r = interval.first(); - if (r == Range.EndMarker) { - interval.addRange(tempPos, tempPos + 1); - } else if (r.from > tempPos) { - r.from = tempPos; - } - interval.addUsePos(tempPos, registerPriority); - interval.addMaterializationValue(null); - - if (Debug.isLogEnabled()) { - Debug.log("add temp: %s tempPos %d (%s)", interval, tempPos, RegisterPriority.MustHaveRegister.name()); - } - } - - @Override - protected void addDef(AllocatableValue operand, LIRInstruction op, RegisterPriority registerPriority, LIRKind kind) { - if (!allocator.isProcessed(operand)) { - return; - } - if (isRegister(operand)) { - super.addDef(operand, op, registerPriority, kind); - return; - } - int defPos = op.id(); - - TraceInterval interval = allocator.getOrCreateInterval(operand); - if (!kind.equals(LIRKind.Illegal)) { - interval.setKind(kind); - } - - Range r = interval.first(); - if (r == Range.EndMarker) { - /* - * Dead value - make vacuous interval also add register priority for dead intervals - */ - interval.addRange(defPos, defPos + 1); - interval.addUsePos(defPos, registerPriority); - if (Debug.isLogEnabled()) { - Debug.log("Warning: def of operand %s at %d occurs without use", operand, defPos); - } - } else { - /* - * Update the starting point (when a range is first created for a use, its start is the - * beginning of the current block until a def is encountered). - */ - r.from = defPos; - interval.addUsePos(defPos, registerPriority); - - } - - changeSpillDefinitionPos(op, operand, interval, defPos); - if (registerPriority == RegisterPriority.None && interval.spillState().ordinal() <= SpillState.StartInMemory.ordinal() && isStackSlot(operand)) { - // detection of method-parameters and roundfp-results - interval.setSpillState(SpillState.StartInMemory); - } - interval.addMaterializationValue(getMaterializedValue(op, operand, interval)); - - if (Debug.isLogEnabled()) { - Debug.log("add def: %s defPos %d (%s)", interval, defPos, registerPriority.name()); - } - } - - @Override - @SuppressWarnings("try") - protected void buildIntervals() { - - try (Indent indent = Debug.logAndIndent("build intervals")) { - InstructionValueConsumer outputConsumer = (op, operand, mode, flags) -> { - if (TraceLinearScan.isVariableOrRegister(operand)) { - addDef((AllocatableValue) operand, op, registerPriorityOfOutputOperand(op), operand.getLIRKind()); - addRegisterHint(op, operand, mode, flags, true); - } - }; - - InstructionValueConsumer tempConsumer = (op, operand, mode, flags) -> { - if (TraceLinearScan.isVariableOrRegister(operand)) { - addTemp((AllocatableValue) operand, op.id(), RegisterPriority.MustHaveRegister, operand.getLIRKind()); - addRegisterHint(op, operand, mode, flags, false); - } - }; - - InstructionValueConsumer aliveConsumer = (op, operand, mode, flags) -> { - if (TraceLinearScan.isVariableOrRegister(operand)) { - RegisterPriority p = registerPriorityOfInputOperand(flags); - int opId = op.id(); - int blockFrom = allocator.getFirstLirInstructionId((allocator.blockForId(opId))); - addUse((AllocatableValue) operand, blockFrom, opId + 1, p, operand.getLIRKind()); - addRegisterHint(op, operand, mode, flags, false); - } - }; - - InstructionValueConsumer inputConsumer = (op, operand, mode, flags) -> { - if (TraceLinearScan.isVariableOrRegister(operand)) { - int opId = op.id(); - RegisterPriority p = registerPriorityOfInputOperand(flags); - int blockFrom = allocator.getFirstLirInstructionId((allocator.blockForId(opId))); - addUse((AllocatableValue) operand, blockFrom, opId, p, operand.getLIRKind()); - addRegisterHint(op, operand, mode, flags, false); - } - }; - - InstructionValueConsumer stateProc = (op, operand, mode, flags) -> { - if (TraceLinearScan.isVariableOrRegister(operand)) { - int opId = op.id(); - int blockFrom = allocator.getFirstLirInstructionId((allocator.blockForId(opId))); - addUse((AllocatableValue) operand, blockFrom, opId + 1, RegisterPriority.None, operand.getLIRKind()); - } - }; - - // create a list with all caller-save registers (cpu, fpu, xmm) - Register[] callerSaveRegs = allocator.getRegisterAllocationConfig().getRegisterConfig().getCallerSaveRegisters(); - - // iterate all blocks in reverse order - for (int i = allocator.blockCount() - 1; i >= 0; i--) { - - AbstractBlockBase<?> block = allocator.blockAt(i); - // TODO (je) make empty bitset - remove - allocator.getBlockData(block).liveIn = new BitSet(); - allocator.getBlockData(block).liveOut = new BitSet(); - try (Indent indent2 = Debug.logAndIndent("handle block %d", block.getId())) { - - List<LIRInstruction> instructions = allocator.getLIR().getLIRforBlock(block); - - /* - * Iterate all instructions of the block in reverse order. definitions of - * intervals are processed before uses. - */ - for (int j = instructions.size() - 1; j >= 0; j--) { - final LIRInstruction op = instructions.get(j); - final int opId = op.id(); - - try (Indent indent3 = Debug.logAndIndent("handle inst %d: %s", opId, op)) { - - // add a temp range for each register if operation destroys - // caller-save registers - if (op.destroysCallerSavedRegisters()) { - for (Register r : callerSaveRegs) { - if (allocator.attributes(r).isAllocatable()) { - addTemp(r.asValue(), opId, RegisterPriority.None, LIRKind.Illegal); - } - } - if (Debug.isLogEnabled()) { - Debug.log("operation destroys all caller-save registers"); - } - } - - op.visitEachOutput(outputConsumer); - op.visitEachTemp(tempConsumer); - op.visitEachAlive(aliveConsumer); - op.visitEachInput(inputConsumer); - - /* - * Add uses of live locals from interpreter's point of view for proper - * debug information generation. Treat these operands as temp values (if - * the live range is extended to a call site, the value would be in a - * register at the call otherwise). - */ - op.visitEachState(stateProc); - - // special steps for some instructions (especially moves) - handleMethodArguments(op); - - } - - } // end of instruction iteration - } - allocator.printIntervals("After Block " + block); - } // end of block iteration - - /* - * Add the range [0, 1] to all fixed intervals. the register allocator need not handle - * unhandled fixed intervals. - */ - for (TraceInterval interval : allocator.intervals()) { - if (interval != null && isRegister(interval.operand)) { - interval.addRange(0, 1); - } - } - } - postBuildIntervals(); - } -}
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceTrivialAllocator.java Thu Sep 03 19:01:59 2015 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceTrivialAllocator.java Mon Sep 07 16:03:02 2015 +0200 @@ -22,30 +22,34 @@ */ package com.oracle.graal.lir.alloc.trace; -import static com.oracle.graal.lir.LIRValueUtil.*; -import static com.oracle.graal.lir.alloc.trace.TraceRegisterAllocationPhase.*; - -import java.util.*; +import static com.oracle.graal.lir.LIRValueUtil.asVariable; +import static com.oracle.graal.lir.LIRValueUtil.isVariable; +import static com.oracle.graal.lir.alloc.trace.TraceRegisterAllocationPhase.isTrivialTrace; -import jdk.internal.jvmci.code.*; -import jdk.internal.jvmci.meta.*; +import java.util.List; -import com.oracle.graal.compiler.common.alloc.*; +import jdk.internal.jvmci.code.TargetDescription; +import jdk.internal.jvmci.meta.Value; + +import com.oracle.graal.compiler.common.alloc.RegisterAllocationConfig; import com.oracle.graal.compiler.common.alloc.TraceBuilder.TraceBuilderResult; -import com.oracle.graal.compiler.common.cfg.*; -import com.oracle.graal.lir.*; +import com.oracle.graal.compiler.common.cfg.AbstractBlockBase; +import com.oracle.graal.lir.LIR; +import com.oracle.graal.lir.LIRInstruction; import com.oracle.graal.lir.LIRInstruction.OperandFlag; -import com.oracle.graal.lir.StandardOp.BlockEndOp; +import com.oracle.graal.lir.StandardOp.JumpOp; import com.oracle.graal.lir.StandardOp.LabelOp; -import com.oracle.graal.lir.gen.*; +import com.oracle.graal.lir.ValueProcedure; +import com.oracle.graal.lir.Variable; +import com.oracle.graal.lir.gen.LIRGenerationResult; import com.oracle.graal.lir.gen.LIRGeneratorTool.SpillMoveFactory; -import com.oracle.graal.lir.phases.*; -import com.oracle.graal.lir.ssi.*; -import com.oracle.graal.lir.util.*; +import com.oracle.graal.lir.phases.AllocationPhase; +import com.oracle.graal.lir.ssi.SSIUtil; +import com.oracle.graal.lir.util.VariableVirtualStackValueMap; /** * Allocates a trivial trace i.e. a trace consisting of a single block with no instructions other - * than the {@link LabelOp} and the {@link BlockEndOp}. + * than the {@link LabelOp} and the {@link JumpOp}. */ final class TraceTrivialAllocator extends AllocationPhase {
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/UsePosList.java Mon Sep 07 16:03:02 2015 +0200 @@ -0,0 +1,125 @@ +/* + * Copyright (c) 2015, 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 com.oracle.graal.compiler.common.util.*; +import com.oracle.graal.lir.alloc.trace.TraceInterval.*; + +/** + * 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 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(); + } +}