| /* |
| * 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 org.graalvm.compiler.lir.alloc.trace.lsra; |
| |
| import static jdk.vm.ci.code.ValueUtil.asRegister; |
| import static jdk.vm.ci.code.ValueUtil.isRegister; |
| |
| import org.graalvm.compiler.lir.LIRInstruction; |
| |
| import jdk.vm.ci.meta.AllocatableValue; |
| import jdk.vm.ci.meta.Value; |
| |
| /** |
| * Represents a fixed interval. |
| */ |
| final class FixedInterval extends IntervalHint { |
| |
| static final class FixedList { |
| |
| public FixedInterval fixed; |
| |
| 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() { |
| if (this == EndMarker) { |
| return "EndMarker [?,?]"; |
| } |
| 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() { |
| 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(); |
| } |
| |
| } |