1 /*
2 * Copyright (c) 2015, 2015, 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.trace.lsra;
24
25 import static jdk.vm.ci.code.ValueUtil.asRegister;
26 import static jdk.vm.ci.code.ValueUtil.isRegister;
27
28 import org.graalvm.compiler.lir.LIRInstruction;
29
30 import jdk.vm.ci.meta.AllocatableValue;
31 import jdk.vm.ci.meta.Value;
32
33 /**
34 * Represents a fixed interval.
35 */
36 final class FixedInterval extends IntervalHint {
37
38 static final class FixedList {
39
40 public FixedInterval fixed;
41
42 FixedList(FixedInterval fixed) {
43 this.fixed = fixed;
44 }
45
46 /**
47 * Gets the fixed list.
48 */
49 public FixedInterval getFixed() {
50 return fixed;
51 }
52
53 /**
54 * Sets the fixed list.
55 */
56 public void setFixed(FixedInterval list) {
57 fixed = list;
58 }
59
60 /**
61 * Adds an interval to a list sorted by {@linkplain FixedInterval#currentFrom() current
62 * from} positions.
63 *
64 * @param interval the interval to add
65 */
66 public void addToListSortedByCurrentFromPositions(FixedInterval interval) {
67 FixedInterval list = getFixed();
68 FixedInterval prev = null;
69 FixedInterval cur = list;
70 while (cur.currentFrom() < interval.currentFrom()) {
71 prev = cur;
72 cur = cur.next;
73 }
74 FixedInterval result = list;
75 if (prev == null) {
76 // add to head of list
77 result = interval;
78 } else {
79 // add before 'cur'
80 prev.next = interval;
81 }
82 interval.next = cur;
83 setFixed(result);
84 }
85
86 }
87
88 /**
89 * The fixed operand of this interval.
90 */
91 public final AllocatableValue operand;
92
93 /**
94 * The head of the list of ranges describing this interval. This list is sorted by
95 * {@linkplain LIRInstruction#id instruction ids}.
96 */
97 private FixedRange first;
98
99 /**
100 * Iterator used to traverse the ranges of an interval.
101 */
102 private FixedRange current;
103
104 /**
105 * Link to next interval in a sorted list of intervals that ends with {@link #EndMarker}.
106 */
107 FixedInterval next;
108
109 private int cachedTo; // cached value: to of last range (-1: not cached)
110
111 public FixedRange first() {
112 return first;
113 }
114
115 @Override
116 public int from() {
117 return first.from;
118 }
119
120 public int to() {
121 if (cachedTo == -1) {
122 cachedTo = calcTo();
123 }
124 assert cachedTo == calcTo() : "invalid cached value";
125 return cachedTo;
126 }
127
128 // test intersection
129 boolean intersects(TraceInterval i) {
130 return first.intersects(i);
131 }
132
133 int intersectsAt(TraceInterval i) {
134 return first.intersectsAt(i);
135 }
136
137 // range iteration
138 void rewindRange() {
139 current = first;
140 }
141
142 void nextRange() {
143 assert this != EndMarker : "not allowed on sentinel";
144 current = current.next;
145 }
146
147 int currentFrom() {
148 return current.from;
149 }
150
151 int currentTo() {
152 return current.to;
153 }
154
155 boolean currentAtEnd() {
156 return current == FixedRange.EndMarker;
157 }
158
159 boolean currentIntersects(TraceInterval it) {
160 return current.intersects(it);
161 }
162
163 int currentIntersectsAt(TraceInterval it) {
164 return current.intersectsAt(it);
165 }
166
167 // range creation
168 public void setFrom(int from) {
169 assert !isEmpty();
170 first().from = from;
171 }
172
173 private boolean isEmpty() {
174 return first() == FixedRange.EndMarker;
175 }
176
177 public void addRange(int from, int to) {
178 if (isEmpty()) {
179 first = new FixedRange(from, to, first());
180 return;
181 }
182 if (to <= to() && from >= from()) {
183 return;
184 }
185 if (from() == to) {
186 first().from = from;
187 } else {
188 first = new FixedRange(from, to, first());
189 }
190 }
191
192 @Override
193 public AllocatableValue location() {
194 return operand;
195 }
196
197 /**
198 * Sentinel interval to denote the end of an interval list.
199 */
200 static final FixedInterval EndMarker = new FixedInterval(Value.ILLEGAL);
201
202 FixedInterval(AllocatableValue operand) {
203 assert operand != null;
204 this.operand = operand;
205 this.first = FixedRange.EndMarker;
206 this.current = FixedRange.EndMarker;
207 this.next = FixedInterval.EndMarker;
208 this.cachedTo = -1;
209 }
210
211 int calcTo() {
212 assert first != FixedRange.EndMarker : "interval has no range";
213
214 FixedRange r = first;
215 while (r.next != FixedRange.EndMarker) {
216 r = r.next;
217 }
218 return r.to;
219 }
220
221 // returns true if the opId is inside the interval
222 boolean covers(int opId, LIRInstruction.OperandMode mode) {
223 FixedRange cur = first;
224
225 while (cur != FixedRange.EndMarker && cur.to < opId) {
226 cur = cur.next;
227 }
228 if (cur != FixedRange.EndMarker) {
229 assert cur.to != cur.next.from : "ranges not separated";
230
231 if (mode == LIRInstruction.OperandMode.DEF) {
232 return cur.from <= opId && opId < cur.to;
233 } else {
234 return cur.from <= opId && opId <= cur.to;
235 }
236 }
237 return false;
238 }
239
240 // returns true if the interval has any hole between holeFrom and holeTo
241 // (even if the hole has only the length 1)
242 boolean hasHoleBetween(int holeFrom, int holeTo) {
243 assert holeFrom < holeTo : "check";
244 assert from() <= holeFrom && holeTo <= to() : "index out of interval";
245
246 FixedRange cur = first;
247 while (cur != FixedRange.EndMarker) {
248 assert cur.to < cur.next.from : "no space between ranges";
249
250 // hole-range starts before this range . hole
251 if (holeFrom < cur.from) {
252 return true;
253
254 // hole-range completely inside this range . no hole
255 } else {
256 if (holeTo <= cur.to) {
257 return false;
258
259 // overlapping of hole-range with this range . hole
260 } else {
261 if (holeFrom <= cur.to) {
262 return true;
263 }
264 }
265 }
266
267 cur = cur.next;
268 }
269
270 return false;
271 }
272
273 @Override
274 public String toString() {
275 if (this == EndMarker) {
276 return "EndMarker [?,?]";
277 }
278 String from = "?";
279 String to = "?";
280 if (first != null && first != FixedRange.EndMarker) {
281 from = String.valueOf(from());
282 // to() may cache a computed value, modifying the current object, which is a bad idea
283 // for a printing function. Compute it directly instead.
284 to = String.valueOf(calcTo());
285 }
286 String locationString = "@" + this.operand;
287 return asRegister(operand).number + ":" + operand + (isRegister(operand) ? "" : locationString) + "[" + from + "," + to + "]";
288 }
289
290 /**
291 * Gets a single line string for logging the details of this interval to a log stream.
292 */
293 @Override
294 public String logString() {
295 StringBuilder buf = new StringBuilder(100);
296 buf.append("fix ").append(asRegister(operand).number).append(':').append(operand).append(' ');
297
298 buf.append(" ranges{");
299
300 // print ranges
301 FixedRange cur = first;
302 while (cur != FixedRange.EndMarker) {
303 if (cur != first) {
304 buf.append(", ");
305 }
306 buf.append(cur);
307 cur = cur.next;
308 assert cur != null : "range list not closed with range sentinel";
309 }
310 buf.append("}");
311 return buf.toString();
312 }
313
314 }