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 }