hotspot/src/jdk.vm.compiler/share/classes/org.graalvm.compiler.lir/src/org/graalvm/compiler/lir/alloc/trace/lsra/FixedInterval.java - platform/libcore - Git at Google

 /*
  * 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();
     }

 }
	/*
	* 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();
	}

	}