1 /*
2 * Copyright (c) 2009, 2011, 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.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;
46
47 /**
48 * Sorted list of intervals in a life time hole at the current position.
49 */
50 protected RegisterBindingLists inactiveLists;
51
52 /**
53 * The current position (intercept point through the intervals).
54 */
55 protected int currentPosition;
56
57 /**
58 * The binding of the current interval being processed.
59 */
60 protected RegisterBinding currentBinding;
61
62 /**
63 * Processes the {@code currentInterval} interval in an attempt to allocate a physical register
64 * to it and thus allow it to be moved to a list of {@linkplain #activeLists active} intervals.
65 *
66 * @return {@code true} if a register was allocated to the {@code currentInterval} interval
67 */
68 protected boolean activateCurrent(@SuppressWarnings({"unused"}) Interval currentInterval) {
69 return true;
70 }
71
72 void walkBefore(int lirOpId) {
73 walkTo(lirOpId - 1);
74 }
75
76 void walk() {
77 walkTo(Integer.MAX_VALUE);
78 }
79
80 /**
81 * Creates a new interval walker.
82 *
83 * @param allocator the register allocator context
84 * @param unhandledFixed the list of unhandled {@linkplain RegisterBinding#Fixed fixed}
85 * intervals
86 * @param unhandledAny the list of unhandled {@linkplain RegisterBinding#Any non-fixed}
87 * intervals
88 */
89 IntervalWalker(LinearScan allocator, Interval unhandledFixed, Interval unhandledAny) {
90 this.allocator = allocator;
91
92 unhandledLists = new RegisterBindingLists(unhandledFixed, unhandledAny, Interval.EndMarker);
93 activeLists = new RegisterBindingLists(Interval.EndMarker, Interval.EndMarker, Interval.EndMarker);
94 inactiveLists = new RegisterBindingLists(Interval.EndMarker, Interval.EndMarker, Interval.EndMarker);
95 currentPosition = -1;
96 }
97
98 protected void removeFromList(Interval interval) {
99 if (interval.state == State.Active) {
100 activeLists.remove(RegisterBinding.Any, interval);
101 } else {
102 assert interval.state == State.Inactive : "invalid state";
103 inactiveLists.remove(RegisterBinding.Any, interval);
104 }
105 }
106
107 private void walkTo(State state, int from) {
108 assert state == State.Active || state == State.Inactive : "wrong state";
109 for (RegisterBinding binding : RegisterBinding.VALUES) {
110 walkTo(state, from, binding);
111 }
112 }
113
114 private void walkTo(State state, int from, RegisterBinding binding) {
115 Interval prevprev = null;
116 Interval prev = (state == State.Active) ? activeLists.get(binding) : inactiveLists.get(binding);
117 Interval next = prev;
118 while (next.currentFrom() <= from) {
119 Interval cur = next;
120 next = cur.next;
121
122 boolean rangeHasChanged = false;
123 while (cur.currentTo() <= from) {
124 cur.nextRange();
125 rangeHasChanged = true;
126 }
127
128 // also handle move from inactive list to active list
129 rangeHasChanged = rangeHasChanged || (state == State.Inactive && cur.currentFrom() <= from);
130
131 if (rangeHasChanged) {
132 // remove cur from list
133 if (prevprev == null) {
134 if (state == State.Active) {
135 activeLists.set(binding, next);
136 } else {
137 inactiveLists.set(binding, next);
138 }
139 } else {
140 prevprev.next = next;
141 }
142 prev = next;
143 Interval.State newState;
144 if (cur.currentAtEnd()) {
145 // move to handled state (not maintained as a list)
146 newState = State.Handled;
147 cur.state = newState;
148 } else {
149 if (cur.currentFrom() <= from) {
150 // sort into active list
151 activeLists.addToListSortedByCurrentFromPositions(binding, cur);
152 newState = State.Active;
153 } else {
154 // sort into inactive list
155 inactiveLists.addToListSortedByCurrentFromPositions(binding, cur);
156 newState = State.Inactive;
157 }
158 cur.state = newState;
159 if (prev == cur) {
160 assert state == newState;
161 prevprev = prev;
162 prev = cur.next;
163 }
164 }
165 intervalMoved(cur, state, newState);
166 } else {
167 prevprev = prev;
168 prev = cur.next;
169 }
170 }
171 }
172
173 /**
174 * Get the next interval from {@linkplain #unhandledLists} which starts before or at
175 * {@code toOpId}. The returned interval is removed and {@link #currentBinding} is set.
176 *
177 * @postcondition all intervals in {@linkplain #unhandledLists} start after {@code toOpId}.
178 *
179 * @return The next interval or null if there is no {@linkplain #unhandledLists unhandled}
180 * interval at position {@code toOpId}.
181 */
182 private Interval nextInterval(int toOpId) {
183 RegisterBinding binding;
184 Interval any = unhandledLists.any;
185 Interval fixed = unhandledLists.fixed;
186
187 if (any != Interval.EndMarker) {
188 // intervals may start at same position . prefer fixed interval
189 binding = fixed != Interval.EndMarker && fixed.from() <= any.from() ? RegisterBinding.Fixed : RegisterBinding.Any;
190
191 assert binding == RegisterBinding.Fixed && fixed.from() <= any.from() || binding == RegisterBinding.Any && any.from() <= fixed.from() : "wrong interval!!!";
192 assert any == Interval.EndMarker || fixed == Interval.EndMarker || any.from() != fixed.from() ||
193 binding == RegisterBinding.Fixed : "if fixed and any-Interval start at same position, fixed must be processed first";
194
195 } else if (fixed != Interval.EndMarker) {
196 binding = RegisterBinding.Fixed;
197 } else {
198 return null;
199 }
200 Interval currentInterval = unhandledLists.get(binding);
201
202 if (toOpId < currentInterval.from()) {
203 return null;
204 }
205
206 currentBinding = binding;
207 unhandledLists.set(binding, currentInterval.next);
208 currentInterval.next = Interval.EndMarker;
209 currentInterval.rewindRange();
210 return currentInterval;
211 }
212
213 /**
214 * Walk up to {@code toOpId}.
215 *
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 != Interval.EndMarker && 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;
282 intervalMoved(currentInterval, State.Unhandled, State.Handled);
283 }
284 currentInterval = next;
285 }
286 unhandledLists.set(RegisterBinding.Stack, currentInterval);
287 }
288
289 }