Mercurial > hg > graal-jvmci-8
comparison graal/Compiler/src/com/sun/c1x/alloc/IntervalWalker.java @ 2507:9ec15d6914ca
Pull over of compiler from maxine repository.
author | Thomas Wuerthinger <thomas@wuerthinger.net> |
---|---|
date | Wed, 27 Apr 2011 11:43:22 +0200 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
2506:4a3bf8a5bf41 | 2507:9ec15d6914ca |
---|---|
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 com.sun.c1x.alloc; | |
24 | |
25 import com.sun.c1x.*; | |
26 import com.sun.c1x.alloc.Interval.*; | |
27 import com.sun.c1x.debug.*; | |
28 | |
29 /** | |
30 * | |
31 * @author Thomas Wuerthinger | |
32 */ | |
33 public class IntervalWalker { | |
34 | |
35 protected final C1XCompilation compilation; | |
36 protected final LinearScan allocator; | |
37 | |
38 /** | |
39 * Sorted list of intervals, not live before the current position. | |
40 */ | |
41 RegisterBindingLists unhandledLists; | |
42 | |
43 /** | |
44 * Sorted list of intervals, live at the current position. | |
45 */ | |
46 RegisterBindingLists activeLists; | |
47 | |
48 /** | |
49 * Sorted list of intervals in a life time hole at the current position. | |
50 */ | |
51 RegisterBindingLists inactiveLists; | |
52 | |
53 /** | |
54 * The current interval (taken from the unhandled list) being processed. | |
55 */ | |
56 protected Interval current; | |
57 | |
58 /** | |
59 * The current position (intercept point through the intervals). | |
60 */ | |
61 protected int currentPosition; | |
62 | |
63 /** | |
64 * The binding of the current interval being processed. | |
65 */ | |
66 protected RegisterBinding currentBinding; | |
67 | |
68 /** | |
69 * Processes the {@linkplain #current} interval in an attempt to allocate a physical | |
70 * register to it and thus allow it to be moved to a list of {@linkplain #activeLists active} intervals. | |
71 * | |
72 * @return {@code true} if a register was allocated to the {@linkplain #current} interval | |
73 */ | |
74 boolean activateCurrent() { | |
75 return true; | |
76 } | |
77 | |
78 void walkBefore(int lirOpId) { | |
79 walkTo(lirOpId - 1); | |
80 } | |
81 | |
82 void walk() { | |
83 walkTo(Integer.MAX_VALUE); | |
84 } | |
85 | |
86 /** | |
87 * Creates a new interval walker. | |
88 * | |
89 * @param allocator the register allocator context | |
90 * @param unhandledFixed the list of unhandled {@linkplain RegisterBinding#Fixed fixed} intervals | |
91 * @param unhandledAny the list of unhandled {@linkplain RegisterBinding#Any non-fixed} intervals | |
92 */ | |
93 IntervalWalker(LinearScan allocator, Interval unhandledFixed, Interval unhandledAny) { | |
94 this.compilation = allocator.compilation; | |
95 this.allocator = allocator; | |
96 | |
97 unhandledLists = new RegisterBindingLists(unhandledFixed, unhandledAny); | |
98 activeLists = new RegisterBindingLists(Interval.EndMarker, Interval.EndMarker); | |
99 inactiveLists = new RegisterBindingLists(Interval.EndMarker, Interval.EndMarker); | |
100 currentPosition = -1; | |
101 current = null; | |
102 nextInterval(); | |
103 } | |
104 | |
105 void removeFromList(Interval interval) { | |
106 if (interval.state == State.Active) { | |
107 activeLists.remove(RegisterBinding.Any, interval); | |
108 } else { | |
109 assert interval.state == State.Inactive : "invalid state"; | |
110 inactiveLists.remove(RegisterBinding.Any, interval); | |
111 } | |
112 } | |
113 | |
114 void walkTo(State state, int from) { | |
115 assert state == State.Active || state == State.Inactive : "wrong state"; | |
116 for (RegisterBinding binding : RegisterBinding.VALUES) { | |
117 Interval prevprev = null; | |
118 Interval prev = (state == State.Active) ? activeLists.get(binding) : inactiveLists.get(binding); | |
119 Interval next = prev; | |
120 while (next.currentFrom() <= from) { | |
121 Interval cur = next; | |
122 next = cur.next; | |
123 | |
124 boolean rangeHasChanged = false; | |
125 while (cur.currentTo() <= from) { | |
126 cur.nextRange(); | |
127 rangeHasChanged = true; | |
128 } | |
129 | |
130 // also handle move from inactive list to active list | |
131 rangeHasChanged = rangeHasChanged || (state == State.Inactive && cur.currentFrom() <= from); | |
132 | |
133 if (rangeHasChanged) { | |
134 // remove cur from list | |
135 if (prevprev == null) { | |
136 if (state == State.Active) { | |
137 activeLists.set(binding, next); | |
138 } else { | |
139 inactiveLists.set(binding, next); | |
140 } | |
141 } else { | |
142 prevprev.next = next; | |
143 } | |
144 prev = next; | |
145 if (cur.currentAtEnd()) { | |
146 // move to handled state (not maintained as a list) | |
147 cur.state = State.Handled; | |
148 intervalMoved(cur, binding, state, State.Handled); | |
149 } else if (cur.currentFrom() <= from) { | |
150 // sort into active list | |
151 activeLists.addToListSortedByCurrentFromPositions(binding, cur); | |
152 cur.state = State.Active; | |
153 if (prev == cur) { | |
154 assert state == State.Active : "check"; | |
155 prevprev = prev; | |
156 prev = cur.next; | |
157 } | |
158 intervalMoved(cur, binding, state, State.Active); | |
159 } else { | |
160 // sort into inactive list | |
161 inactiveLists.addToListSortedByCurrentFromPositions(binding, cur); | |
162 cur.state = State.Inactive; | |
163 if (prev == cur) { | |
164 assert state == State.Inactive : "check"; | |
165 prevprev = prev; | |
166 prev = cur.next; | |
167 } | |
168 intervalMoved(cur, binding, state, State.Inactive); | |
169 } | |
170 } else { | |
171 prevprev = prev; | |
172 prev = cur.next; | |
173 } | |
174 } | |
175 } | |
176 } | |
177 | |
178 void nextInterval() { | |
179 RegisterBinding binding; | |
180 Interval any = unhandledLists.any; | |
181 Interval fixed = unhandledLists.fixed; | |
182 | |
183 if (any != Interval.EndMarker) { | |
184 // intervals may start at same position . prefer fixed interval | |
185 binding = fixed != Interval.EndMarker && fixed.from() <= any.from() ? RegisterBinding.Fixed : RegisterBinding.Any; | |
186 | |
187 assert binding == RegisterBinding.Fixed && fixed.from() <= any.from() || binding == RegisterBinding.Any && any.from() <= fixed.from() : "wrong interval!!!"; | |
188 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"; | |
189 | |
190 } else if (fixed != Interval.EndMarker) { | |
191 binding = RegisterBinding.Fixed; | |
192 } else { | |
193 current = null; | |
194 return; | |
195 } | |
196 currentBinding = binding; | |
197 current = unhandledLists.get(binding); | |
198 unhandledLists.set(binding, current.next); | |
199 current.next = Interval.EndMarker; | |
200 current.rewindRange(); | |
201 } | |
202 | |
203 void walkTo(int toOpId) { | |
204 assert currentPosition <= toOpId : "can not walk backwards"; | |
205 while (current != null) { | |
206 boolean isActive = current.from() <= toOpId; | |
207 int opId = isActive ? current.from() : toOpId; | |
208 | |
209 if (C1XOptions.TraceLinearScanLevel >= 2 && !TTY.isSuppressed()) { | |
210 if (currentPosition < opId) { | |
211 TTY.println(); | |
212 TTY.println("walkTo(%d) *", opId); | |
213 } | |
214 } | |
215 | |
216 // set currentPosition prior to call of walkTo | |
217 currentPosition = opId; | |
218 | |
219 // call walkTo even if currentPosition == id | |
220 walkTo(State.Active, opId); | |
221 walkTo(State.Inactive, opId); | |
222 | |
223 if (isActive) { | |
224 current.state = State.Active; | |
225 if (activateCurrent()) { | |
226 activeLists.addToListSortedByCurrentFromPositions(currentBinding, current); | |
227 intervalMoved(current, currentBinding, State.Unhandled, State.Active); | |
228 } | |
229 | |
230 nextInterval(); | |
231 } else { | |
232 return; | |
233 } | |
234 } | |
235 } | |
236 | |
237 private void intervalMoved(Interval interval, RegisterBinding kind, State from, State to) { | |
238 // intervalMoved() is called whenever an interval moves from one interval list to another. | |
239 // In the implementation of this method it is prohibited to move the interval to any list. | |
240 if (C1XOptions.TraceLinearScanLevel >= 4 && !TTY.isSuppressed()) { | |
241 TTY.print(from.toString() + " to " + to.toString()); | |
242 TTY.fillTo(23); | |
243 TTY.out().println(interval.logString(allocator)); | |
244 } | |
245 } | |
246 } |