IntervalWalker.java revision 13264:48566d838608
1194763Smarius/* 2194763Smarius * Copyright (c) 2009, 2011, Oracle and/or its affiliates. All rights reserved. 3194763Smarius * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4194763Smarius * 5194763Smarius * This code is free software; you can redistribute it and/or modify it 6194763Smarius * under the terms of the GNU General Public License version 2 only, as 7194763Smarius * published by the Free Software Foundation. 8194763Smarius * 9194763Smarius * This code is distributed in the hope that it will be useful, but WITHOUT 10194763Smarius * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 11194763Smarius * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 12194763Smarius * version 2 for more details (a copy is included in the LICENSE file that 13194763Smarius * accompanied this code). 14194763Smarius * 15194763Smarius * You should have received a copy of the GNU General Public License version 16194763Smarius * 2 along with this work; if not, write to the Free Software Foundation, 17194763Smarius * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 18194763Smarius * 19194763Smarius * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 20194763Smarius * or visit www.oracle.com if you need additional information or have any 21194763Smarius * questions. 22194763Smarius */ 23194763Smariuspackage org.graalvm.compiler.lir.alloc.lsra; 24194763Smarius 25194763Smariusimport org.graalvm.compiler.debug.DebugContext; 26194763Smariusimport org.graalvm.compiler.debug.Indent; 27194763Smariusimport org.graalvm.compiler.lir.alloc.lsra.Interval.RegisterBinding; 28194763Smariusimport org.graalvm.compiler.lir.alloc.lsra.Interval.RegisterBindingLists; 29194763Smariusimport org.graalvm.compiler.lir.alloc.lsra.Interval.State; 30194763Smarius 31194763Smarius/** 32194763Smarius */ 33194763Smariuspublic class IntervalWalker { 34194763Smarius 35194763Smarius protected final LinearScan allocator; 36194763Smarius 37194763Smarius /** 38194763Smarius * Sorted list of intervals, not live before the current position. 39194763Smarius */ 40194763Smarius protected RegisterBindingLists unhandledLists; 41194763Smarius 42194763Smarius /** 43194763Smarius * Sorted list of intervals, live at the current position. 44194763Smarius */ 45194763Smarius protected RegisterBindingLists activeLists; 46194763Smarius 47194763Smarius /** 48194763Smarius * Sorted list of intervals in a life time hole at the current position. 49194763Smarius */ 50194763Smarius protected RegisterBindingLists inactiveLists; 51194763Smarius 52194763Smarius /** 53194763Smarius * The current position (intercept point through the intervals). 54194763Smarius */ 55194763Smarius protected int currentPosition; 56194763Smarius 57194763Smarius /** 58194763Smarius * The binding of the current interval being processed. 59194763Smarius */ 60194763Smarius protected RegisterBinding currentBinding; 61194763Smarius 62194763Smarius /** 63194763Smarius * Processes the {@code currentInterval} interval in an attempt to allocate a physical register 64194763Smarius * to it and thus allow it to be moved to a list of {@linkplain #activeLists active} intervals. 65194763Smarius * 66194763Smarius * @return {@code true} if a register was allocated to the {@code currentInterval} interval 67194763Smarius */ 68194763Smarius protected boolean activateCurrent(@SuppressWarnings({"unused"}) Interval currentInterval) { 69194763Smarius return true; 70194763Smarius } 71194763Smarius 72194763Smarius void walkBefore(int lirOpId) { 73194763Smarius walkTo(lirOpId - 1); 74194763Smarius } 75194763Smarius 76194763Smarius void walk() { 77194763Smarius walkTo(Integer.MAX_VALUE); 78194763Smarius } 79194763Smarius 80194763Smarius /** 81194763Smarius * Creates a new interval walker. 82194763Smarius * 83194763Smarius * @param allocator the register allocator context 84194763Smarius * @param unhandledFixed the list of unhandled {@linkplain RegisterBinding#Fixed fixed} 85194763Smarius * intervals 86227843Smarius * @param unhandledAny the list of unhandled {@linkplain RegisterBinding#Any non-fixed} 87194763Smarius * intervals 88194763Smarius */ 89194763Smarius IntervalWalker(LinearScan allocator, Interval unhandledFixed, Interval unhandledAny) { 90194763Smarius this.allocator = allocator; 91194763Smarius 92194763Smarius unhandledLists = new RegisterBindingLists(unhandledFixed, unhandledAny, allocator.intervalEndMarker); 93194763Smarius activeLists = new RegisterBindingLists(allocator.intervalEndMarker, allocator.intervalEndMarker, allocator.intervalEndMarker); 94194763Smarius inactiveLists = new RegisterBindingLists(allocator.intervalEndMarker, allocator.intervalEndMarker, allocator.intervalEndMarker); 95194763Smarius currentPosition = -1; 96194763Smarius } 97194763Smarius 98194763Smarius protected void removeFromList(Interval interval) { 99194763Smarius if (interval.state == State.Active) { 100194763Smarius activeLists.remove(RegisterBinding.Any, interval); 101194763Smarius } else { 102194763Smarius assert interval.state == State.Inactive : "invalid state"; 103194763Smarius inactiveLists.remove(RegisterBinding.Any, interval); 104194763Smarius } 105194763Smarius } 106194763Smarius 107194763Smarius private void walkTo(State state, int from) { 108194763Smarius assert state == State.Active || state == State.Inactive : "wrong state"; 109194763Smarius for (RegisterBinding binding : RegisterBinding.VALUES) { 110194763Smarius walkTo(state, from, binding); 111194763Smarius } 112194763Smarius } 113194763Smarius 114194763Smarius private void walkTo(State state, int from, RegisterBinding binding) { 115194763Smarius Interval prevprev = null; 116194763Smarius Interval prev = (state == State.Active) ? activeLists.get(binding) : inactiveLists.get(binding); 117194763Smarius Interval next = prev; 118194763Smarius while (next.currentFrom() <= from) { 119194763Smarius Interval cur = next; 120194763Smarius next = cur.next; 121194763Smarius 122194763Smarius boolean rangeHasChanged = false; 123194763Smarius while (cur.currentTo() <= from) { 124194763Smarius cur.nextRange(); 125194763Smarius rangeHasChanged = true; 126194763Smarius } 127194763Smarius 128194763Smarius // also handle move from inactive list to active list 129194763Smarius rangeHasChanged = rangeHasChanged || (state == State.Inactive && cur.currentFrom() <= from); 130212725Smarius 131212725Smarius if (rangeHasChanged) { 132194763Smarius // remove cur from list 133194763Smarius if (prevprev == null) { 134194763Smarius if (state == State.Active) { 135194763Smarius activeLists.set(binding, next); 136194763Smarius } else { 137194763Smarius inactiveLists.set(binding, next); 138194763Smarius } 139194763Smarius } else { 140194763Smarius prevprev.next = next; 141194763Smarius } 142194763Smarius prev = next; 143194763Smarius Interval.State newState; 144194763Smarius if (cur.currentAtEnd()) { 145194763Smarius // move to handled state (not maintained as a list) 146194763Smarius newState = State.Handled; 147194763Smarius cur.state = newState; 148194763Smarius } else { 149194763Smarius if (cur.currentFrom() <= from) { 150194763Smarius // sort into active list 151194763Smarius activeLists.addToListSortedByCurrentFromPositions(binding, cur); 152194763Smarius newState = State.Active; 153194763Smarius } else { 154194763Smarius // sort into inactive list 155194763Smarius inactiveLists.addToListSortedByCurrentFromPositions(binding, cur); 156194763Smarius newState = State.Inactive; 157194763Smarius } 158194763Smarius cur.state = newState; 159194763Smarius if (prev == cur) { 160194763Smarius assert state == newState; 161194763Smarius prevprev = prev; 162194763Smarius prev = cur.next; 163194763Smarius } 164194763Smarius } 165194763Smarius intervalMoved(cur, state, newState); 166194763Smarius } else { 167194763Smarius prevprev = prev; 168194763Smarius prev = cur.next; 169194763Smarius } 170194763Smarius } 171194763Smarius } 172194763Smarius 173194763Smarius /** 174194763Smarius * Get the next interval from {@linkplain #unhandledLists} which starts before or at 175194763Smarius * {@code toOpId}. The returned interval is removed and {@link #currentBinding} is set. 176194763Smarius * 177194763Smarius * @postcondition all intervals in {@linkplain #unhandledLists} start after {@code toOpId}. 178194763Smarius * 179194763Smarius * @return The next interval or null if there is no {@linkplain #unhandledLists unhandled} 180194763Smarius * interval at position {@code toOpId}. 181194763Smarius */ 182194763Smarius private Interval nextInterval(int toOpId) { 183194763Smarius RegisterBinding binding; 184194763Smarius Interval any = unhandledLists.any; 185194763Smarius Interval fixed = unhandledLists.fixed; 186194763Smarius 187194763Smarius if (!any.isEndMarker()) { 188194763Smarius // intervals may start at same position . prefer fixed interval 189194763Smarius binding = !fixed.isEndMarker() && fixed.from() <= any.from() ? RegisterBinding.Fixed : RegisterBinding.Any; 190194763Smarius 191194763Smarius assert binding == RegisterBinding.Fixed && fixed.from() <= any.from() || binding == RegisterBinding.Any && any.from() <= fixed.from() : "wrong interval!!!"; 192194763Smarius assert any.isEndMarker() || fixed.isEndMarker() || any.from() != fixed.from() || 193194763Smarius binding == RegisterBinding.Fixed : "if fixed and any-Interval start at same position, fixed must be processed first"; 194194763Smarius 195194763Smarius } else if (!fixed.isEndMarker()) { 196194763Smarius binding = RegisterBinding.Fixed; 197194763Smarius } else { 198194763Smarius return null; 199194763Smarius } 200194763Smarius Interval currentInterval = unhandledLists.get(binding); 201194763Smarius 202194763Smarius if (toOpId < currentInterval.from()) { 203194763Smarius return null; 204194763Smarius } 205194763Smarius 206194763Smarius currentBinding = binding; 207194763Smarius unhandledLists.set(binding, currentInterval.next); 208194763Smarius currentInterval.next = allocator.intervalEndMarker; 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 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; 284 intervalMoved(currentInterval, State.Unhandled, State.Handled); 285 } 286 currentInterval = next; 287 } 288 unhandledLists.set(RegisterBinding.Stack, currentInterval); 289 } 290 291} 292