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

 /*
  * Copyright (c) 2009, 2015, Oracle and/or its affiliates. All rights reserved.
  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
  *
  * This code is free software; you can redistribute it and/or modify it
  * under the terms of the GNU General Public License version 2 only, as
  * published by the Free Software Foundation.
  *
  * This code is distributed in the hope that it will be useful, but WITHOUT
  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  * version 2 for more details (a copy is included in the LICENSE file that
  * accompanied this code).
  *
  * You should have received a copy of the GNU General Public License version
  * 2 along with this work; if not, write to the Free Software Foundation,
  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  *
  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  * or visit www.oracle.com if you need additional information or have any
  * questions.
  */
 package org.graalvm.compiler.lir.alloc.trace.lsra;

 import org.graalvm.compiler.debug.Debug;
 import org.graalvm.compiler.debug.Indent;
 import org.graalvm.compiler.lir.alloc.trace.lsra.FixedInterval.FixedList;
 import org.graalvm.compiler.lir.alloc.trace.lsra.TraceInterval.AnyList;
 import org.graalvm.compiler.lir.alloc.trace.lsra.TraceInterval.RegisterBinding;
 import org.graalvm.compiler.lir.alloc.trace.lsra.TraceInterval.State;
 import org.graalvm.compiler.lir.alloc.trace.lsra.TraceLinearScanPhase.TraceLinearScan;

 /**
  */
 class TraceIntervalWalker {

     protected final TraceLinearScan allocator;

     /**
      * Sorted list of intervals, not live before the current position.
      */
     protected AnyList unhandledAnyList;

     /**
      * Sorted list of intervals, live at the current position.
      */
     protected AnyList activeAnyList;
     protected FixedList activeFixedList;

     /**
      * Sorted list of intervals in a life time hole at the current position.
      */
     protected FixedList inactiveFixedList;

     /**
      * The current position (intercept point through the intervals).
      */
     protected int currentPosition;

     /**
      * 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 #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(TraceInterval currentInterval) {
         if (Debug.isLogEnabled()) {
             logCurrentStatus();
         }
         return true;
     }

     @SuppressWarnings("try")
     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 static void logList(FixedInterval i) {
         for (FixedInterval interval = i; interval != FixedInterval.EndMarker; interval = interval.next) {
             Debug.log("%s", interval.logString());
         }
     }

     private static void logList(TraceInterval i) {
         for (TraceInterval interval = i; interval != TraceInterval.EndMarker; interval = interval.next) {
             Debug.log("%s", interval.logString());
         }
     }

     void walkBefore(int lirOpId) {
         walkTo(lirOpId - 1);
     }

     void walk() {
         walkTo(Integer.MAX_VALUE);
     }

     /**
      * Creates a new interval walker.
      *
      * @param allocator the register allocator context
      * @param unhandledFixed the list of unhandled {@linkplain RegisterBinding#Fixed fixed}
      *            intervals
      * @param unhandledAny the list of unhandled {@linkplain RegisterBinding#Any non-fixed}
      *            intervals
      */
     TraceIntervalWalker(TraceLinearScan allocator, FixedInterval unhandledFixed, TraceInterval unhandledAny) {
         this.allocator = allocator;

         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) {
         activeAnyList.removeAny(interval);
     }

     /**
      * 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).
      */
     @SuppressWarnings("try")
     private void walkToFixed(State state, int from) {
         assert state == State.Active || state == State.Inactive : "wrong state";
         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);
             }
         }
         while (next.currentFrom() <= from) {
             FixedInterval cur = next;
             next = cur.next;

             boolean rangeHasChanged = false;
             while (cur.currentTo() <= from) {
                 cur.nextRange();
                 rangeHasChanged = true;
             }

             // also handle move from inactive list to active list
             rangeHasChanged = rangeHasChanged || (state == State.Inactive && cur.currentFrom() <= from);

             if (rangeHasChanged) {
                 // remove cur from list
                 if (prevprev == null) {
                     if (state == State.Active) {
                         activeFixedList.setFixed(next);
                     } else {
                         inactiveFixedList.setFixed(next);
                     }
                 } else {
                     prevprev.next = next;
                 }
                 prev = next;
                 TraceInterval.State newState;
                 if (cur.currentAtEnd()) {
                     // move to handled state (not maintained as a list)
                     newState = State.Handled;
                 } else {
                     if (cur.currentFrom() <= from) {
                         // sort into active list
                         activeFixedList.addToListSortedByCurrentFromPositions(cur);
                         newState = State.Active;
                     } else {
                         // sort into inactive list
                         inactiveFixedList.addToListSortedByCurrentFromPositions(cur);
                         newState = State.Inactive;
                     }
                     if (prev == cur) {
                         assert state == newState;
                         prevprev = prev;
                         prev = cur.next;
                     }
                 }
                 intervalMoved(cur, state, newState);
             } else {
                 prevprev = prev;
                 prev = cur.next;
             }
         }
     }

     /**
      * Walks up to {@code from} and updates the state of {@link TraceInterval intervals}.
      *
      * 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.
      */
     @SuppressWarnings("try")
     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.
      *
      * @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) {
         TraceInterval any = unhandledAnyList.getAny();

         if (any != TraceInterval.EndMarker) {
             TraceInterval currentInterval = unhandledAnyList.getAny();
             if (toOpId < currentInterval.from()) {
                 return null;
             }

             unhandledAnyList.setAny(currentInterval.next);
             currentInterval.next = TraceInterval.EndMarker;
             return currentInterval;
         }
         return null;

     }

     /**
      * Walk up to {@code toOpId}.
      *
      * @postcondition {@link #currentPosition} is set to {@code toOpId}, {@link #activeFixedList}
      *                and {@link #inactiveFixedList} are populated.
      */
     @SuppressWarnings("try")
     protected void walkTo(int toOpId) {
         assert currentPosition <= toOpId : "can not walk backwards";
         for (TraceInterval currentInterval = nextInterval(toOpId); currentInterval != null; currentInterval = nextInterval(toOpId)) {
             int opId = currentInterval.from();

             // set currentPosition prior to call of walkTo
             currentPosition = opId;

             // update unhandled stack intervals
             // updateUnhandledStackIntervals(opId);

             // call walkTo even if currentPosition == id
             walkToFixed(State.Active, opId);
             walkToFixed(State.Inactive, opId);
             walkToAny(opId);

             try (Indent indent = Debug.logAndIndent("walk to op %d", opId)) {
                 if (activateCurrent(currentInterval)) {
                     activeAnyList.addToListSortedByFromPositions(currentInterval);
                     intervalMoved(currentInterval, State.Unhandled, State.Active);
                 }
             }
         }
         // set currentPosition prior to call of walkTo
         currentPosition = toOpId;

         if (currentPosition <= allocator.maxOpId()) {
             // update unhandled stack intervals
             // updateUnhandledStackIntervals(toOpId);

             // call walkTo if still in range
             walkToFixed(State.Active, toOpId);
             walkToFixed(State.Inactive, toOpId);
             walkToAny(toOpId);
         }
     }

     private static 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());
         }
     }
 }
	/*
	* Copyright (c) 2009, 2015, Oracle and/or its affiliates. All rights reserved.
	* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
	*
	* This code is free software; you can redistribute it and/or modify it
	* under the terms of the GNU General Public License version 2 only, as
	* published by the Free Software Foundation.
	*
	* This code is distributed in the hope that it will be useful, but WITHOUT
	* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
	* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
	* version 2 for more details (a copy is included in the LICENSE file that
	* accompanied this code).
	*
	* You should have received a copy of the GNU General Public License version
	* 2 along with this work; if not, write to the Free Software Foundation,
	* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
	*
	* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
	* or visit www.oracle.com if you need additional information or have any
	* questions.
	*/
	package org.graalvm.compiler.lir.alloc.trace.lsra;

	import org.graalvm.compiler.debug.Debug;
	import org.graalvm.compiler.debug.Indent;
	import org.graalvm.compiler.lir.alloc.trace.lsra.FixedInterval.FixedList;
	import org.graalvm.compiler.lir.alloc.trace.lsra.TraceInterval.AnyList;
	import org.graalvm.compiler.lir.alloc.trace.lsra.TraceInterval.RegisterBinding;
	import org.graalvm.compiler.lir.alloc.trace.lsra.TraceInterval.State;
	import org.graalvm.compiler.lir.alloc.trace.lsra.TraceLinearScanPhase.TraceLinearScan;

	/**
	*/
	class TraceIntervalWalker {

	protected final TraceLinearScan allocator;

	/**
	* Sorted list of intervals, not live before the current position.
	*/
	protected AnyList unhandledAnyList;

	/**
	* Sorted list of intervals, live at the current position.
	*/
	protected AnyList activeAnyList;
	protected FixedList activeFixedList;

	/**
	* Sorted list of intervals in a life time hole at the current position.
	*/
	protected FixedList inactiveFixedList;

	/**
	* The current position (intercept point through the intervals).
	*/
	protected int currentPosition;

	/**
	* 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 #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(TraceInterval currentInterval) {
	if (Debug.isLogEnabled()) {
	logCurrentStatus();
	}
	return true;
	}

	@SuppressWarnings("try")
	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 static void logList(FixedInterval i) {
	for (FixedInterval interval = i; interval != FixedInterval.EndMarker; interval = interval.next) {
	Debug.log("%s", interval.logString());
	}
	}

	private static void logList(TraceInterval i) {
	for (TraceInterval interval = i; interval != TraceInterval.EndMarker; interval = interval.next) {
	Debug.log("%s", interval.logString());
	}
	}

	void walkBefore(int lirOpId) {
	walkTo(lirOpId - 1);
	}

	void walk() {
	walkTo(Integer.MAX_VALUE);
	}

	/**
	* Creates a new interval walker.
	*
	* @param allocator the register allocator context
	* @param unhandledFixed the list of unhandled {@linkplain RegisterBinding#Fixed fixed}
	* intervals
	* @param unhandledAny the list of unhandled {@linkplain RegisterBinding#Any non-fixed}
	* intervals
	*/
	TraceIntervalWalker(TraceLinearScan allocator, FixedInterval unhandledFixed, TraceInterval unhandledAny) {
	this.allocator = allocator;

	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) {
	activeAnyList.removeAny(interval);
	}

	/**
	* 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).
	*/
	@SuppressWarnings("try")
	private void walkToFixed(State state, int from) {
	assert state == State.Active \|\| state == State.Inactive : "wrong state";
	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);
	}
	}
	while (next.currentFrom() <= from) {
	FixedInterval cur = next;
	next = cur.next;

	boolean rangeHasChanged = false;
	while (cur.currentTo() <= from) {
	cur.nextRange();
	rangeHasChanged = true;
	}

	// also handle move from inactive list to active list
	rangeHasChanged = rangeHasChanged \|\| (state == State.Inactive && cur.currentFrom() <= from);

	if (rangeHasChanged) {
	// remove cur from list
	if (prevprev == null) {
	if (state == State.Active) {
	activeFixedList.setFixed(next);
	} else {
	inactiveFixedList.setFixed(next);
	}
	} else {
	prevprev.next = next;
	}
	prev = next;
	TraceInterval.State newState;
	if (cur.currentAtEnd()) {
	// move to handled state (not maintained as a list)
	newState = State.Handled;
	} else {
	if (cur.currentFrom() <= from) {
	// sort into active list
	activeFixedList.addToListSortedByCurrentFromPositions(cur);
	newState = State.Active;
	} else {
	// sort into inactive list
	inactiveFixedList.addToListSortedByCurrentFromPositions(cur);
	newState = State.Inactive;
	}
	if (prev == cur) {
	assert state == newState;
	prevprev = prev;
	prev = cur.next;
	}
	}
	intervalMoved(cur, state, newState);
	} else {
	prevprev = prev;
	prev = cur.next;
	}
	}
	}

	/**
	* Walks up to {@code from} and updates the state of {@link TraceInterval intervals}.
	*
	* 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.
	*/
	@SuppressWarnings("try")
	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.
	*
	* @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) {
	TraceInterval any = unhandledAnyList.getAny();

	if (any != TraceInterval.EndMarker) {
	TraceInterval currentInterval = unhandledAnyList.getAny();
	if (toOpId < currentInterval.from()) {
	return null;
	}

	unhandledAnyList.setAny(currentInterval.next);
	currentInterval.next = TraceInterval.EndMarker;
	return currentInterval;
	}
	return null;

	}

	/**
	* Walk up to {@code toOpId}.
	*
	* @postcondition {@link #currentPosition} is set to {@code toOpId}, {@link #activeFixedList}
	* and {@link #inactiveFixedList} are populated.
	*/
	@SuppressWarnings("try")
	protected void walkTo(int toOpId) {
	assert currentPosition <= toOpId : "can not walk backwards";
	for (TraceInterval currentInterval = nextInterval(toOpId); currentInterval != null; currentInterval = nextInterval(toOpId)) {
	int opId = currentInterval.from();

	// set currentPosition prior to call of walkTo
	currentPosition = opId;

	// update unhandled stack intervals
	// updateUnhandledStackIntervals(opId);

	// call walkTo even if currentPosition == id
	walkToFixed(State.Active, opId);
	walkToFixed(State.Inactive, opId);
	walkToAny(opId);

	try (Indent indent = Debug.logAndIndent("walk to op %d", opId)) {
	if (activateCurrent(currentInterval)) {
	activeAnyList.addToListSortedByFromPositions(currentInterval);
	intervalMoved(currentInterval, State.Unhandled, State.Active);
	}
	}
	}
	// set currentPosition prior to call of walkTo
	currentPosition = toOpId;

	if (currentPosition <= allocator.maxOpId()) {
	// update unhandled stack intervals
	// updateUnhandledStackIntervals(toOpId);

	// call walkTo if still in range
	walkToFixed(State.Active, toOpId);
	walkToFixed(State.Inactive, toOpId);
	walkToAny(toOpId);
	}
	}

	private static 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());
	}
	}
	}