Source code

001/*
002 * Copyright (c) 2009, 2011, Oracle and/or its affiliates. All rights reserved.
003 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
004 *
005 * This code is free software; you can redistribute it and/or modify it
006 * under the terms of the GNU General Public License version 2 only, as
007 * published by the Free Software Foundation.
008 *
009 * This code is distributed in the hope that it will be useful, but WITHOUT
010 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
011 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
012 * version 2 for more details (a copy is included in the LICENSE file that
013 * accompanied this code).
014 *
015 * You should have received a copy of the GNU General Public License version
016 * 2 along with this work; if not, write to the Free Software Foundation,
017 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
018 *
019 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
020 * or visit www.oracle.com if you need additional information or have any
021 * questions.
022 */
023package com.oracle.graal.lir.alloc.lsra;
024
025import com.oracle.graal.debug.*;
026
027import com.oracle.graal.lir.alloc.lsra.Interval.RegisterBinding;
028import com.oracle.graal.lir.alloc.lsra.Interval.RegisterBindingLists;
029import com.oracle.graal.lir.alloc.lsra.Interval.State;
030
031/**
032 */
033public class IntervalWalker {
034
035    protected final LinearScan allocator;
036
037    /**
038     * Sorted list of intervals, not live before the current position.
039     */
040    protected RegisterBindingLists unhandledLists;
041
042    /**
043     * Sorted list of intervals, live at the current position.
044     */
045    protected RegisterBindingLists activeLists;
046
047    /**
048     * Sorted list of intervals in a life time hole at the current position.
049     */
050    protected RegisterBindingLists inactiveLists;
051
052    /**
053     * The current position (intercept point through the intervals).
054     */
055    protected int currentPosition;
056
057    /**
058     * The binding of the current interval being processed.
059     */
060    protected RegisterBinding currentBinding;
061
062    /**
063     * Processes the {@code currentInterval} interval in an attempt to allocate a physical register
064     * to it and thus allow it to be moved to a list of {@linkplain #activeLists active} intervals.
065     *
066     * @return {@code true} if a register was allocated to the {@code currentInterval} interval
067     */
068    protected boolean activateCurrent(@SuppressWarnings({"unused"}) Interval currentInterval) {
069        return true;
070    }
071
072    void walkBefore(int lirOpId) {
073        walkTo(lirOpId - 1);
074    }
075
076    void walk() {
077        walkTo(Integer.MAX_VALUE);
078    }
079
080    /**
081     * Creates a new interval walker.
082     *
083     * @param allocator the register allocator context
084     * @param unhandledFixed the list of unhandled {@linkplain RegisterBinding#Fixed fixed}
085     *            intervals
086     * @param unhandledAny the list of unhandled {@linkplain RegisterBinding#Any non-fixed}
087     *            intervals
088     */
089    IntervalWalker(LinearScan allocator, Interval unhandledFixed, Interval unhandledAny) {
090        this.allocator = allocator;
091
092        unhandledLists = new RegisterBindingLists(unhandledFixed, unhandledAny, Interval.EndMarker);
093        activeLists = new RegisterBindingLists(Interval.EndMarker, Interval.EndMarker, Interval.EndMarker);
094        inactiveLists = new RegisterBindingLists(Interval.EndMarker, Interval.EndMarker, Interval.EndMarker);
095        currentPosition = -1;
096    }
097
098    protected void removeFromList(Interval interval) {
099        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() || binding == RegisterBinding.Fixed : "if fixed and any-Interval start at same position, fixed must be processed first";
193
194        } else if (fixed != Interval.EndMarker) {
195            binding = RegisterBinding.Fixed;
196        } else {
197            return null;
198        }
199        Interval currentInterval = unhandledLists.get(binding);
200
201        if (toOpId < currentInterval.from()) {
202            return null;
203        }
204
205        currentBinding = binding;
206        unhandledLists.set(binding, currentInterval.next);
207        currentInterval.next = Interval.EndMarker;
208        currentInterval.rewindRange();
209        return currentInterval;
210    }
211
212    /**
213     * Walk up to {@code toOpId}.
214     *
215     * @postcondition {@link #currentPosition} is set to {@code toOpId}, {@link #activeLists} and
216     *                {@link #inactiveLists} are populated and {@link Interval#state}s are up to
217     *                date.
218     */
219    protected void walkTo(int toOpId) {
220        assert currentPosition <= toOpId : "can not walk backwards";
221        for (Interval currentInterval = nextInterval(toOpId); currentInterval != null; currentInterval = nextInterval(toOpId)) {
222            int opId = currentInterval.from();
223
224            // set currentPosition prior to call of walkTo
225            currentPosition = opId;
226
227            // update unhandled stack intervals
228            updateUnhandledStackIntervals(opId);
229
230            // call walkTo even if currentPosition == id
231            walkTo(State.Active, opId);
232            walkTo(State.Inactive, opId);
233
234            try (Indent indent = Debug.logAndIndent("walk to op %d", opId)) {
235                currentInterval.state = State.Active;
236                if (activateCurrent(currentInterval)) {
237                    activeLists.addToListSortedByCurrentFromPositions(currentBinding, currentInterval);
238                    intervalMoved(currentInterval, State.Unhandled, State.Active);
239                }
240            }
241        }
242        // set currentPosition prior to call of walkTo
243        currentPosition = toOpId;
244
245        if (currentPosition <= allocator.maxOpId()) {
246            // update unhandled stack intervals
247            updateUnhandledStackIntervals(toOpId);
248
249            // call walkTo if still in range
250            walkTo(State.Active, toOpId);
251            walkTo(State.Inactive, toOpId);
252        }
253    }
254
255    private void intervalMoved(Interval interval, State from, State to) {
256        // intervalMoved() is called whenever an interval moves from one interval list to another.
257        // In the implementation of this method it is prohibited to move the interval to any list.
258        if (Debug.isLogEnabled()) {
259            Debug.log("interval moved from %s to %s: %s", from, to, interval.logString(allocator));
260        }
261    }
262
263    /**
264     * Move {@linkplain #unhandledLists unhandled} stack intervals to
265     * {@linkplain IntervalWalker #activeLists active}.
266     *
267     * Note that for {@linkplain RegisterBinding#Fixed fixed} and {@linkplain RegisterBinding#Any
268     * any} intervals this is done in {@link #nextInterval(int)}.
269     */
270    private void updateUnhandledStackIntervals(int opId) {
271        Interval currentInterval = unhandledLists.get(RegisterBinding.Stack);
272        while (currentInterval != Interval.EndMarker && currentInterval.from() <= opId) {
273            Interval next = currentInterval.next;
274            if (currentInterval.to() > opId) {
275                currentInterval.state = State.Active;
276                activeLists.addToListSortedByCurrentFromPositions(RegisterBinding.Stack, currentInterval);
277                intervalMoved(currentInterval, State.Unhandled, State.Active);
278            } else {
279                currentInterval.state = State.Handled;
280                intervalMoved(currentInterval, State.Unhandled, State.Handled);
281            }
282            currentInterval = next;
283        }
284        unhandledLists.set(RegisterBinding.Stack, currentInterval);
285    }
286
287}