1 /*
2 * Copyright (c) 2009, 2015, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
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.trace.lsra;
24
25 import org.graalvm.compiler.debug.Debug;
26 import org.graalvm.compiler.debug.Indent;
27 import org.graalvm.compiler.lir.alloc.trace.lsra.FixedInterval.FixedList;
28 import org.graalvm.compiler.lir.alloc.trace.lsra.TraceInterval.AnyList;
29 import org.graalvm.compiler.lir.alloc.trace.lsra.TraceInterval.RegisterBinding;
30 import org.graalvm.compiler.lir.alloc.trace.lsra.TraceInterval.State;
31 import org.graalvm.compiler.lir.alloc.trace.lsra.TraceLinearScanPhase.TraceLinearScan;
32
33 /**
34 */
35 class TraceIntervalWalker {
36
37 protected final TraceLinearScan allocator;
38
39 /**
40 * Sorted list of intervals, not live before the current position.
41 */
42 protected AnyList unhandledAnyList;
43
44 /**
45 * Sorted list of intervals, live at the current position.
46 */
47 protected AnyList activeAnyList;
48 protected FixedList activeFixedList;
49
50 /**
51 * Sorted list of intervals in a life time hole at the current position.
52 */
53 protected FixedList inactiveFixedList;
54
55 /**
56 * The current position (intercept point through the intervals).
57 */
58 protected int currentPosition;
59
60 /**
61 * Processes the {@code currentInterval} interval in an attempt to allocate a physical register
62 * to it and thus allow it to be moved to a list of {@linkplain #activeAnyList active}
63 * intervals.
64 *
65 * @param currentInterval The interval to be activated.
66 *
67 * @return {@code true} if a register was allocated to the {@code currentInterval} interval
68 */
69 protected boolean activateCurrent(TraceInterval currentInterval) {
70 if (Debug.isLogEnabled()) {
71 logCurrentStatus();
72 }
73 return true;
74 }
75
76 @SuppressWarnings("try")
77 protected void logCurrentStatus() {
78 try (Indent i = Debug.logAndIndent("active:")) {
79 logList(activeFixedList.getFixed());
80 logList(activeAnyList.getAny());
81 }
82 try (Indent i = Debug.logAndIndent("inactive(fixed):")) {
83 logList(inactiveFixedList.getFixed());
84 }
85 }
86
87 private static void logList(FixedInterval i) {
88 for (FixedInterval interval = i; interval != FixedInterval.EndMarker; interval = interval.next) {
89 Debug.log("%s", interval.logString());
90 }
91 }
92
93 private static void logList(TraceInterval i) {
94 for (TraceInterval interval = i; interval != TraceInterval.EndMarker; interval = interval.next) {
95 Debug.log("%s", interval.logString());
96 }
97 }
98
99 void walkBefore(int lirOpId) {
100 walkTo(lirOpId - 1);
101 }
102
103 void walk() {
104 walkTo(Integer.MAX_VALUE);
105 }
106
107 /**
108 * Creates a new interval walker.
109 *
110 * @param allocator the register allocator context
111 * @param unhandledFixed the list of unhandled {@linkplain RegisterBinding#Fixed fixed}
112 * intervals
113 * @param unhandledAny the list of unhandled {@linkplain RegisterBinding#Any non-fixed}
114 * intervals
115 */
116 TraceIntervalWalker(TraceLinearScan allocator, FixedInterval unhandledFixed, TraceInterval unhandledAny) {
117 this.allocator = allocator;
118
119 unhandledAnyList = new AnyList(unhandledAny);
120 activeAnyList = new AnyList(TraceInterval.EndMarker);
121 activeFixedList = new FixedList(FixedInterval.EndMarker);
122 // we don't need a separate unhandled list for fixed.
123 inactiveFixedList = new FixedList(unhandledFixed);
124 currentPosition = -1;
125 }
126
127 protected void removeFromList(TraceInterval interval) {
128 activeAnyList.removeAny(interval);
129 }
130
131 /**
132 * Walks up to {@code from} and updates the state of {@link FixedInterval fixed intervals}.
133 *
134 * Fixed intervals can switch back and forth between the states {@link State#Active} and
135 * {@link State#Inactive} (and eventually to {@link State#Handled} but handled intervals are not
136 * managed).
137 */
138 @SuppressWarnings("try")
139 private void walkToFixed(State state, int from) {
140 assert state == State.Active || state == State.Inactive : "wrong state";
141 FixedInterval prevprev = null;
142 FixedInterval prev = (state == State.Active) ? activeFixedList.getFixed() : inactiveFixedList.getFixed();
143 FixedInterval next = prev;
144 if (Debug.isLogEnabled()) {
145 try (Indent i = Debug.logAndIndent("walkToFixed(%s, %d):", state, from)) {
146 logList(next);
147 }
148 }
149 while (next.currentFrom() <= from) {
150 FixedInterval cur = next;
151 next = cur.next;
152
153 boolean rangeHasChanged = false;
154 while (cur.currentTo() <= from) {
155 cur.nextRange();
156 rangeHasChanged = true;
157 }
158
159 // also handle move from inactive list to active list
160 rangeHasChanged = rangeHasChanged || (state == State.Inactive && cur.currentFrom() <= from);
161
162 if (rangeHasChanged) {
163 // remove cur from list
164 if (prevprev == null) {
165 if (state == State.Active) {
166 activeFixedList.setFixed(next);
167 } else {
168 inactiveFixedList.setFixed(next);
169 }
170 } else {
171 prevprev.next = next;
172 }
173 prev = next;
174 TraceInterval.State newState;
175 if (cur.currentAtEnd()) {
176 // move to handled state (not maintained as a list)
177 newState = State.Handled;
178 } else {
179 if (cur.currentFrom() <= from) {
180 // sort into active list
181 activeFixedList.addToListSortedByCurrentFromPositions(cur);
182 newState = State.Active;
183 } else {
184 // sort into inactive list
185 inactiveFixedList.addToListSortedByCurrentFromPositions(cur);
186 newState = State.Inactive;
187 }
188 if (prev == cur) {
189 assert state == newState;
190 prevprev = prev;
191 prev = cur.next;
192 }
193 }
194 intervalMoved(cur, state, newState);
195 } else {
196 prevprev = prev;
197 prev = cur.next;
198 }
199 }
200 }
201
202 /**
203 * Walks up to {@code from} and updates the state of {@link TraceInterval intervals}.
204 *
205 * Trace intervals can switch once from {@link State#Unhandled} to {@link State#Active} and then
206 * to {@link State#Handled} but handled intervals are not managed.
207 */
208 @SuppressWarnings("try")
209 private void walkToAny(int from) {
210 TraceInterval prevprev = null;
211 TraceInterval prev = activeAnyList.getAny();
212 TraceInterval next = prev;
213 if (Debug.isLogEnabled()) {
214 try (Indent i = Debug.logAndIndent("walkToAny(%d):", from)) {
215 logList(next);
216 }
217 }
218 while (next.from() <= from) {
219 TraceInterval cur = next;
220 next = cur.next;
221
222 if (cur.to() <= from) {
223 // remove cur from list
224 if (prevprev == null) {
225 activeAnyList.setAny(next);
226 } else {
227 prevprev.next = next;
228 }
229 intervalMoved(cur, State.Active, State.Handled);
230 } else {
231 prevprev = prev;
232 }
233 prev = next;
234 }
235 }
236
237 /**
238 * Get the next interval from {@linkplain #unhandledAnyList} which starts before or at
239 * {@code toOpId}. The returned interval is removed.
240 *
241 * @postcondition all intervals in {@linkplain #unhandledAnyList} start after {@code toOpId}.
242 *
243 * @return The next interval or null if there is no {@linkplain #unhandledAnyList unhandled}
244 * interval at position {@code toOpId}.
245 */
246 private TraceInterval nextInterval(int toOpId) {
247 TraceInterval any = unhandledAnyList.getAny();
248
249 if (any != TraceInterval.EndMarker) {
250 TraceInterval currentInterval = unhandledAnyList.getAny();
251 if (toOpId < currentInterval.from()) {
252 return null;
253 }
254
255 unhandledAnyList.setAny(currentInterval.next);
256 currentInterval.next = TraceInterval.EndMarker;
257 return currentInterval;
258 }
259 return null;
260
261 }
262
263 /**
264 * Walk up to {@code toOpId}.
265 *
266 * @postcondition {@link #currentPosition} is set to {@code toOpId}, {@link #activeFixedList}
267 * and {@link #inactiveFixedList} are populated.
268 */
269 @SuppressWarnings("try")
270 protected void walkTo(int toOpId) {
271 assert currentPosition <= toOpId : "can not walk backwards";
272 for (TraceInterval currentInterval = nextInterval(toOpId); currentInterval != null; currentInterval = nextInterval(toOpId)) {
273 int opId = currentInterval.from();
274
275 // set currentPosition prior to call of walkTo
276 currentPosition = opId;
277
278 // update unhandled stack intervals
279 // updateUnhandledStackIntervals(opId);
280
281 // call walkTo even if currentPosition == id
282 walkToFixed(State.Active, opId);
283 walkToFixed(State.Inactive, opId);
284 walkToAny(opId);
285
286 try (Indent indent = Debug.logAndIndent("walk to op %d", opId)) {
287 if (activateCurrent(currentInterval)) {
288 activeAnyList.addToListSortedByFromPositions(currentInterval);
289 intervalMoved(currentInterval, State.Unhandled, State.Active);
290 }
291 }
292 }
293 // set currentPosition prior to call of walkTo
294 currentPosition = toOpId;
295
296 if (currentPosition <= allocator.maxOpId()) {
297 // update unhandled stack intervals
298 // updateUnhandledStackIntervals(toOpId);
299
300 // call walkTo if still in range
301 walkToFixed(State.Active, toOpId);
302 walkToFixed(State.Inactive, toOpId);
303 walkToAny(toOpId);
304 }
305 }
306
307 private static void intervalMoved(IntervalHint interval, State from, State to) {
308 // intervalMoved() is called whenever an interval moves from one interval list to another.
309 // In the implementation of this method it is prohibited to move the interval to any list.
310 if (Debug.isLogEnabled()) {
311 Debug.log("interval moved from %s to %s: %s", from, to, interval.logString());
312 }
313 }
314 }