5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
23 package org.graalvm.compiler.lir.alloc.lsra;
24
25 import org.graalvm.compiler.debug.Debug;
26 import org.graalvm.compiler.debug.Indent;
27 import org.graalvm.compiler.lir.alloc.lsra.Interval.RegisterBinding;
28 import org.graalvm.compiler.lir.alloc.lsra.Interval.RegisterBindingLists;
29 import org.graalvm.compiler.lir.alloc.lsra.Interval.State;
30
31 /**
32 */
33 public class IntervalWalker {
34
35 protected final LinearScan allocator;
36
37 /**
38 * Sorted list of intervals, not live before the current position.
39 */
40 protected RegisterBindingLists unhandledLists;
41
42 /**
43 * Sorted list of intervals, live at the current position.
44 */
45 protected RegisterBindingLists activeLists;
216 * @postcondition {@link #currentPosition} is set to {@code toOpId}, {@link #activeLists} and
217 * {@link #inactiveLists} are populated and {@link Interval#state}s are up to
218 * date.
219 */
220 @SuppressWarnings("try")
221 protected void walkTo(int toOpId) {
222 assert currentPosition <= toOpId : "can not walk backwards";
223 for (Interval currentInterval = nextInterval(toOpId); currentInterval != null; currentInterval = nextInterval(toOpId)) {
224 int opId = currentInterval.from();
225
226 // set currentPosition prior to call of walkTo
227 currentPosition = opId;
228
229 // update unhandled stack intervals
230 updateUnhandledStackIntervals(opId);
231
232 // call walkTo even if currentPosition == id
233 walkTo(State.Active, opId);
234 walkTo(State.Inactive, opId);
235
236 try (Indent indent = Debug.logAndIndent("walk to op %d", opId)) {
237 currentInterval.state = State.Active;
238 if (activateCurrent(currentInterval)) {
239 activeLists.addToListSortedByCurrentFromPositions(currentBinding, currentInterval);
240 intervalMoved(currentInterval, State.Unhandled, State.Active);
241 }
242 }
243 }
244 // set currentPosition prior to call of walkTo
245 currentPosition = toOpId;
246
247 if (currentPosition <= allocator.maxOpId()) {
248 // update unhandled stack intervals
249 updateUnhandledStackIntervals(toOpId);
250
251 // call walkTo if still in range
252 walkTo(State.Active, toOpId);
253 walkTo(State.Inactive, toOpId);
254 }
255 }
256
257 private void intervalMoved(Interval interval, State from, State to) {
258 // intervalMoved() is called whenever an interval moves from one interval list to another.
259 // In the implementation of this method it is prohibited to move the interval to any list.
260 if (Debug.isLogEnabled()) {
261 Debug.log("interval moved from %s to %s: %s", from, to, interval.logString(allocator));
262 }
263 }
264
265 /**
266 * Move {@linkplain #unhandledLists unhandled} stack intervals to
267 * {@linkplain IntervalWalker #activeLists active}.
268 *
269 * Note that for {@linkplain RegisterBinding#Fixed fixed} and {@linkplain RegisterBinding#Any
270 * any} intervals this is done in {@link #nextInterval(int)}.
271 */
272 private void updateUnhandledStackIntervals(int opId) {
273 Interval currentInterval = unhandledLists.get(RegisterBinding.Stack);
274 while (!currentInterval.isEndMarker() && currentInterval.from() <= opId) {
275 Interval next = currentInterval.next;
276 if (currentInterval.to() > opId) {
277 currentInterval.state = State.Active;
278 activeLists.addToListSortedByCurrentFromPositions(RegisterBinding.Stack, currentInterval);
279 intervalMoved(currentInterval, State.Unhandled, State.Active);
280 } else {
281 currentInterval.state = State.Handled;
|
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
23 package org.graalvm.compiler.lir.alloc.lsra;
24
25 import org.graalvm.compiler.debug.DebugContext;
26 import org.graalvm.compiler.debug.Indent;
27 import org.graalvm.compiler.lir.alloc.lsra.Interval.RegisterBinding;
28 import org.graalvm.compiler.lir.alloc.lsra.Interval.RegisterBindingLists;
29 import org.graalvm.compiler.lir.alloc.lsra.Interval.State;
30
31 /**
32 */
33 public class IntervalWalker {
34
35 protected final LinearScan allocator;
36
37 /**
38 * Sorted list of intervals, not live before the current position.
39 */
40 protected RegisterBindingLists unhandledLists;
41
42 /**
43 * Sorted list of intervals, live at the current position.
44 */
45 protected RegisterBindingLists activeLists;
216 * @postcondition {@link #currentPosition} is set to {@code toOpId}, {@link #activeLists} and
217 * {@link #inactiveLists} are populated and {@link Interval#state}s are up to
218 * date.
219 */
220 @SuppressWarnings("try")
221 protected void walkTo(int toOpId) {
222 assert currentPosition <= toOpId : "can not walk backwards";
223 for (Interval currentInterval = nextInterval(toOpId); currentInterval != null; currentInterval = nextInterval(toOpId)) {
224 int opId = currentInterval.from();
225
226 // set currentPosition prior to call of walkTo
227 currentPosition = opId;
228
229 // update unhandled stack intervals
230 updateUnhandledStackIntervals(opId);
231
232 // call walkTo even if currentPosition == id
233 walkTo(State.Active, opId);
234 walkTo(State.Inactive, opId);
235
236 DebugContext debug = allocator.getDebug();
237 try (Indent indent = debug.logAndIndent("walk to op %d", opId)) {
238 currentInterval.state = State.Active;
239 if (activateCurrent(currentInterval)) {
240 activeLists.addToListSortedByCurrentFromPositions(currentBinding, currentInterval);
241 intervalMoved(currentInterval, State.Unhandled, State.Active);
242 }
243 }
244 }
245 // set currentPosition prior to call of walkTo
246 currentPosition = toOpId;
247
248 if (currentPosition <= allocator.maxOpId()) {
249 // update unhandled stack intervals
250 updateUnhandledStackIntervals(toOpId);
251
252 // call walkTo if still in range
253 walkTo(State.Active, toOpId);
254 walkTo(State.Inactive, toOpId);
255 }
256 }
257
258 private void intervalMoved(Interval interval, State from, State to) {
259 // intervalMoved() is called whenever an interval moves from one interval list to another.
260 // In the implementation of this method it is prohibited to move the interval to any list.
261 DebugContext debug = allocator.getDebug();
262 if (debug.isLogEnabled()) {
263 debug.log("interval moved from %s to %s: %s", from, to, interval.logString(allocator));
264 }
265 }
266
267 /**
268 * Move {@linkplain #unhandledLists unhandled} stack intervals to
269 * {@linkplain IntervalWalker #activeLists active}.
270 *
271 * Note that for {@linkplain RegisterBinding#Fixed fixed} and {@linkplain RegisterBinding#Any
272 * any} intervals this is done in {@link #nextInterval(int)}.
273 */
274 private void updateUnhandledStackIntervals(int opId) {
275 Interval currentInterval = unhandledLists.get(RegisterBinding.Stack);
276 while (!currentInterval.isEndMarker() && currentInterval.from() <= opId) {
277 Interval next = currentInterval.next;
278 if (currentInterval.to() > opId) {
279 currentInterval.state = State.Active;
280 activeLists.addToListSortedByCurrentFromPositions(RegisterBinding.Stack, currentInterval);
281 intervalMoved(currentInterval, State.Unhandled, State.Active);
282 } else {
283 currentInterval.state = State.Handled;
|