1 /*
2 * Copyright (c) 2009, 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.lsra;
24
25 import static jdk.vm.ci.code.ValueUtil.asRegister;
26 import static jdk.vm.ci.code.ValueUtil.isIllegal;
27 import static jdk.vm.ci.code.ValueUtil.isRegister;
28
29 import java.util.ArrayList;
30
31 import org.graalvm.compiler.core.common.LIRKind;
32 import org.graalvm.compiler.debug.Debug;
33 import org.graalvm.compiler.debug.DebugCounter;
34 import org.graalvm.compiler.debug.GraalError;
35 import org.graalvm.compiler.debug.Indent;
36 import org.graalvm.compiler.lir.LIRInsertionBuffer;
37 import org.graalvm.compiler.lir.LIRInstruction;
38 import org.graalvm.compiler.lir.LIRValueUtil;
39 import org.graalvm.util.Equivalence;
40 import org.graalvm.util.EconomicSet;
41
42 import jdk.vm.ci.meta.AllocatableValue;
43 import jdk.vm.ci.meta.Constant;
44 import jdk.vm.ci.meta.Value;
45
46 /**
47 */
48 public class MoveResolver {
49
50 private static final DebugCounter cycleBreakingSlotsAllocated = Debug.counter("LSRA[cycleBreakingSlotsAllocated]");
51
52 private final LinearScan allocator;
53
54 private int insertIdx;
55 private LIRInsertionBuffer insertionBuffer; // buffer where moves are inserted
56
57 private final ArrayList<Interval> mappingFrom;
58 private final ArrayList<Constant> mappingFromOpr;
59 private final ArrayList<Interval> mappingTo;
60 private boolean multipleReadsAllowed;
61 private final int[] registerBlocked;
62
63 protected void setValueBlocked(Value location, int direction) {
64 assert direction == 1 || direction == -1 : "out of bounds";
65 if (isRegister(location)) {
66 registerBlocked[asRegister(location).number] += direction;
67 } else {
68 throw GraalError.shouldNotReachHere("unhandled value " + location);
69 }
70 }
71
72 protected Interval getMappingFrom(int i) {
73 return mappingFrom.get(i);
74 }
75
76 protected int mappingFromSize() {
77 return mappingFrom.size();
78 }
79
80 protected int valueBlocked(Value location) {
81 if (isRegister(location)) {
82 return registerBlocked[asRegister(location).number];
83 }
84 throw GraalError.shouldNotReachHere("unhandled value " + location);
85 }
86
87 void setMultipleReadsAllowed() {
88 multipleReadsAllowed = true;
89 }
90
91 protected boolean areMultipleReadsAllowed() {
92 return multipleReadsAllowed;
93 }
94
95 boolean hasMappings() {
96 return mappingFrom.size() > 0;
97 }
98
99 protected LinearScan getAllocator() {
100 return allocator;
101 }
102
103 protected MoveResolver(LinearScan allocator) {
104
105 this.allocator = allocator;
106 this.multipleReadsAllowed = false;
107 this.mappingFrom = new ArrayList<>(8);
108 this.mappingFromOpr = new ArrayList<>(8);
109 this.mappingTo = new ArrayList<>(8);
110 this.insertIdx = -1;
111 this.insertionBuffer = new LIRInsertionBuffer();
112 this.registerBlocked = new int[allocator.getRegisters().size()];
113 }
114
115 protected boolean checkEmpty() {
116 assert mappingFrom.size() == 0 && mappingFromOpr.size() == 0 && mappingTo.size() == 0 : "list must be empty before and after processing";
117 for (int i = 0; i < getAllocator().getRegisters().size(); i++) {
118 assert registerBlocked[i] == 0 : "register map must be empty before and after processing";
119 }
120 checkMultipleReads();
121 return true;
122 }
123
124 protected void checkMultipleReads() {
125 assert !areMultipleReadsAllowed() : "must have default value";
126 }
127
128 private boolean verifyBeforeResolve() {
129 assert mappingFrom.size() == mappingFromOpr.size() : "length must be equal";
130 assert mappingFrom.size() == mappingTo.size() : "length must be equal";
131 assert insertIdx != -1 : "insert position not set";
132
133 int i;
134 int j;
135 if (!areMultipleReadsAllowed()) {
136 for (i = 0; i < mappingFrom.size(); i++) {
137 for (j = i + 1; j < mappingFrom.size(); j++) {
138 assert mappingFrom.get(i) == null || mappingFrom.get(i) != mappingFrom.get(j) : "cannot read from same interval twice";
139 }
140 }
141 }
142
143 for (i = 0; i < mappingTo.size(); i++) {
144 for (j = i + 1; j < mappingTo.size(); j++) {
145 assert mappingTo.get(i) != mappingTo.get(j) : "cannot write to same interval twice";
146 }
147 }
148
149 EconomicSet<Value> usedRegs = EconomicSet.create(Equivalence.DEFAULT);
150 if (!areMultipleReadsAllowed()) {
151 for (i = 0; i < mappingFrom.size(); i++) {
152 Interval interval = mappingFrom.get(i);
153 if (interval != null && !isIllegal(interval.location())) {
154 boolean unique = usedRegs.add(interval.location());
155 assert unique : "cannot read from same register twice";
156 }
157 }
158 }
159
160 usedRegs.clear();
161 for (i = 0; i < mappingTo.size(); i++) {
162 Interval interval = mappingTo.get(i);
163 if (isIllegal(interval.location())) {
164 // After insertion the location may become illegal, so don't check it since multiple
165 // intervals might be illegal.
166 continue;
167 }
168 boolean unique = usedRegs.add(interval.location());
169 assert unique : "cannot write to same register twice";
170 }
171
172 verifyStackSlotMapping();
173
174 return true;
175 }
176
177 protected void verifyStackSlotMapping() {
178 EconomicSet<Value> usedRegs = EconomicSet.create(Equivalence.DEFAULT);
179 for (int i = 0; i < mappingFrom.size(); i++) {
180 Interval interval = mappingFrom.get(i);
181 if (interval != null && !isRegister(interval.location())) {
182 usedRegs.add(interval.location());
183 }
184 }
185 for (int i = 0; i < mappingTo.size(); i++) {
186 Interval interval = mappingTo.get(i);
187 assert !usedRegs.contains(interval.location()) ||
188 checkIntervalLocation(mappingFrom.get(i), interval, mappingFromOpr.get(i)) : "stack slots used in mappingFrom must be disjoint to mappingTo";
189 }
190 }
191
192 private static boolean checkIntervalLocation(Interval from, Interval to, Constant fromOpr) {
193 if (from == null) {
194 return fromOpr != null;
195 } else {
196 return to.location().equals(from.location());
197 }
198 }
199
200 // mark assignedReg and assignedRegHi of the interval as blocked
201 private void blockRegisters(Interval interval) {
202 Value location = interval.location();
203 if (mightBeBlocked(location)) {
204 assert areMultipleReadsAllowed() || valueBlocked(location) == 0 : "location already marked as used: " + location;
205 int direction = 1;
206 setValueBlocked(location, direction);
207 Debug.log("block %s", location);
208 }
209 }
210
211 // mark assignedReg and assignedRegHi of the interval as unblocked
212 private void unblockRegisters(Interval interval) {
213 Value location = interval.location();
214 if (mightBeBlocked(location)) {
215 assert valueBlocked(location) > 0 : "location already marked as unused: " + location;
216 setValueBlocked(location, -1);
217 Debug.log("unblock %s", location);
218 }
219 }
220
221 /**
222 * Checks if the {@linkplain Interval#location() location} of {@code to} is not blocked or is
223 * only blocked by {@code from}.
224 */
225 private boolean safeToProcessMove(Interval from, Interval to) {
226 Value fromReg = from != null ? from.location() : null;
227
228 Value location = to.location();
229 if (mightBeBlocked(location)) {
230 if ((valueBlocked(location) > 1 || (valueBlocked(location) == 1 && !isMoveToSelf(fromReg, location)))) {
231 return false;
232 }
233 }
234
235 return true;
236 }
237
238 protected boolean isMoveToSelf(Value from, Value to) {
239 assert to != null;
240 if (to.equals(from)) {
241 return true;
242 }
243 if (from != null && isRegister(from) && isRegister(to) && asRegister(from).equals(asRegister(to))) {
244 assert LIRKind.verifyMoveKinds(to.getValueKind(), from.getValueKind()) : String.format("Same register but Kind mismatch %s <- %s", to, from);
245 return true;
246 }
247 return false;
248 }
249
250 protected boolean mightBeBlocked(Value location) {
251 return isRegister(location);
252 }
253
254 private void createInsertionBuffer(ArrayList<LIRInstruction> list) {
255 assert !insertionBuffer.initialized() : "overwriting existing buffer";
256 insertionBuffer.init(list);
257 }
258
259 private void appendInsertionBuffer() {
260 if (insertionBuffer.initialized()) {
261 insertionBuffer.finish();
262 }
263 assert !insertionBuffer.initialized() : "must be uninitialized now";
264
265 insertIdx = -1;
266 }
267
268 private void insertMove(Interval fromInterval, Interval toInterval) {
269 assert !fromInterval.operand.equals(toInterval.operand) : "from and to interval equal: " + fromInterval;
270 assert LIRKind.verifyMoveKinds(toInterval.kind(), fromInterval.kind()) : "move between different types";
271 assert insertIdx != -1 : "must setup insert position first";
272
273 insertionBuffer.append(insertIdx, createMove(fromInterval.operand, toInterval.operand, fromInterval.location(), toInterval.location()));
274
275 if (Debug.isLogEnabled()) {
276 Debug.log("insert move from %s to %s at %d", fromInterval, toInterval, insertIdx);
277 }
278 }
279
280 /**
281 * @param fromOpr {@link Interval#operand operand} of the {@code from} interval
282 * @param toOpr {@link Interval#operand operand} of the {@code to} interval
283 * @param fromLocation {@link Interval#location() location} of the {@code to} interval
284 * @param toLocation {@link Interval#location() location} of the {@code to} interval
285 */
286 protected LIRInstruction createMove(AllocatableValue fromOpr, AllocatableValue toOpr, AllocatableValue fromLocation, AllocatableValue toLocation) {
287 return getAllocator().getSpillMoveFactory().createMove(toOpr, fromOpr);
288 }
289
290 private void insertMove(Constant fromOpr, Interval toInterval) {
291 assert insertIdx != -1 : "must setup insert position first";
292
293 AllocatableValue toOpr = toInterval.operand;
294 LIRInstruction move = getAllocator().getSpillMoveFactory().createLoad(toOpr, fromOpr);
295 insertionBuffer.append(insertIdx, move);
296
297 if (Debug.isLogEnabled()) {
298 Debug.log("insert move from value %s to %s at %d", fromOpr, toInterval, insertIdx);
299 }
300 }
301
302 @SuppressWarnings("try")
303 private void resolveMappings() {
304 try (Indent indent = Debug.logAndIndent("resolveMapping")) {
305 assert verifyBeforeResolve();
306 if (Debug.isLogEnabled()) {
307 printMapping();
308 }
309
310 // Block all registers that are used as input operands of a move.
311 // When a register is blocked, no move to this register is emitted.
312 // This is necessary for detecting cycles in moves.
313 int i;
314 for (i = mappingFrom.size() - 1; i >= 0; i--) {
315 Interval fromInterval = mappingFrom.get(i);
316 if (fromInterval != null) {
317 blockRegisters(fromInterval);
318 }
319 }
320
321 ArrayList<AllocatableValue> busySpillSlots = null;
322 while (mappingFrom.size() > 0) {
323 boolean processedInterval = false;
324
325 int spillCandidate = -1;
326 for (i = mappingFrom.size() - 1; i >= 0; i--) {
327 Interval fromInterval = mappingFrom.get(i);
328 Interval toInterval = mappingTo.get(i);
329
330 if (safeToProcessMove(fromInterval, toInterval)) {
331 // this interval can be processed because target is free
332 if (fromInterval != null) {
333 insertMove(fromInterval, toInterval);
334 unblockRegisters(fromInterval);
335 } else {
336 insertMove(mappingFromOpr.get(i), toInterval);
337 }
338 if (LIRValueUtil.isStackSlotValue(toInterval.location())) {
339 if (busySpillSlots == null) {
340 busySpillSlots = new ArrayList<>(2);
341 }
342 busySpillSlots.add(toInterval.location());
343 }
344 mappingFrom.remove(i);
345 mappingFromOpr.remove(i);
346 mappingTo.remove(i);
347
348 processedInterval = true;
349 } else if (fromInterval != null && isRegister(fromInterval.location()) &&
350 (busySpillSlots == null || !busySpillSlots.contains(fromInterval.spillSlot()))) {
351 // this interval cannot be processed now because target is not free
352 // it starts in a register, so it is a possible candidate for spilling
353 spillCandidate = i;
354 }
355 }
356
357 if (!processedInterval) {
358 breakCycle(spillCandidate);
359 }
360 }
361 }
362
363 // reset to default value
364 multipleReadsAllowed = false;
365
366 // check that all intervals have been processed
367 assert checkEmpty();
368 }
369
370 protected void breakCycle(int spillCandidate) {
371 // no move could be processed because there is a cycle in the move list
372 // (e.g. r1 . r2, r2 . r1), so one interval must be spilled to memory
373 assert spillCandidate != -1 : "no interval in register for spilling found";
374
375 // create a new spill interval and assign a stack slot to it
376 Interval fromInterval = mappingFrom.get(spillCandidate);
377 // do not allocate a new spill slot for temporary interval, but
378 // use spill slot assigned to fromInterval. Otherwise moves from
379 // one stack slot to another can happen (not allowed by LIRAssembler
380 AllocatableValue spillSlot = fromInterval.spillSlot();
381 if (spillSlot == null) {
382 spillSlot = getAllocator().getFrameMapBuilder().allocateSpillSlot(fromInterval.kind());
383 fromInterval.setSpillSlot(spillSlot);
384 cycleBreakingSlotsAllocated.increment();
385 }
386 spillInterval(spillCandidate, fromInterval, spillSlot);
387 }
388
389 protected void spillInterval(int spillCandidate, Interval fromInterval, AllocatableValue spillSlot) {
390 assert mappingFrom.get(spillCandidate).equals(fromInterval);
391 Interval spillInterval = getAllocator().createDerivedInterval(fromInterval);
392 spillInterval.setKind(fromInterval.kind());
393
394 // add a dummy range because real position is difficult to calculate
395 // Note: this range is a special case when the integrity of the allocation is
396 // checked
397 spillInterval.addRange(1, 2);
398
399 spillInterval.assignLocation(spillSlot);
400
401 if (Debug.isLogEnabled()) {
402 Debug.log("created new Interval for spilling: %s", spillInterval);
403 }
404 blockRegisters(spillInterval);
405
406 // insert a move from register to stack and update the mapping
407 insertMove(fromInterval, spillInterval);
408 mappingFrom.set(spillCandidate, spillInterval);
409 unblockRegisters(fromInterval);
410 }
411
412 @SuppressWarnings("try")
413 private void printMapping() {
414 try (Indent indent = Debug.logAndIndent("Mapping")) {
415 for (int i = mappingFrom.size() - 1; i >= 0; i--) {
416 Interval fromInterval = mappingFrom.get(i);
417 Interval toInterval = mappingTo.get(i);
418 String from;
419 Value to = toInterval.location();
420 if (fromInterval == null) {
421 from = mappingFromOpr.get(i).toString();
422 } else {
423 from = fromInterval.location().toString();
424 }
425 Debug.log("move %s <- %s", from, to);
426 }
427 }
428 }
429
430 void setInsertPosition(ArrayList<LIRInstruction> insertList, int insertIdx) {
431 assert this.insertIdx == -1 : "use moveInsertPosition instead of setInsertPosition when data already set";
432
433 createInsertionBuffer(insertList);
434 this.insertIdx = insertIdx;
435 }
436
437 void moveInsertPosition(ArrayList<LIRInstruction> newInsertList, int newInsertIdx) {
438 if (insertionBuffer.lirList() != null && (insertionBuffer.lirList() != newInsertList || this.insertIdx != newInsertIdx)) {
439 // insert position changed . resolve current mappings
440 resolveMappings();
441 }
442
443 if (insertionBuffer.lirList() != newInsertList) {
444 // block changed . append insertionBuffer because it is
445 // bound to a specific block and create a new insertionBuffer
446 appendInsertionBuffer();
447 createInsertionBuffer(newInsertList);
448 }
449
450 this.insertIdx = newInsertIdx;
451 }
452
453 public void addMapping(Interval fromInterval, Interval toInterval) {
454
455 if (isIllegal(toInterval.location()) && toInterval.canMaterialize()) {
456 if (Debug.isLogEnabled()) {
457 Debug.log("no store to rematerializable interval %s needed", toInterval);
458 }
459 return;
460 }
461 if (isIllegal(fromInterval.location()) && fromInterval.canMaterialize()) {
462 // Instead of a reload, re-materialize the value
463 Constant rematValue = fromInterval.getMaterializedValue();
464 addMapping(rematValue, toInterval);
465 return;
466 }
467 if (Debug.isLogEnabled()) {
468 Debug.log("add move mapping from %s to %s", fromInterval, toInterval);
469 }
470
471 assert !fromInterval.operand.equals(toInterval.operand) : "from and to interval equal: " + fromInterval;
472 assert LIRKind.verifyMoveKinds(toInterval.kind(), fromInterval.kind()) : String.format("Kind mismatch: %s vs. %s, from=%s, to=%s", fromInterval.kind(), toInterval.kind(), fromInterval,
473 toInterval);
474 mappingFrom.add(fromInterval);
475 mappingFromOpr.add(null);
476 mappingTo.add(toInterval);
477 }
478
479 public void addMapping(Constant fromOpr, Interval toInterval) {
480 if (Debug.isLogEnabled()) {
481 Debug.log("add move mapping from %s to %s", fromOpr, toInterval);
482 }
483
484 mappingFrom.add(null);
485 mappingFromOpr.add(fromOpr);
486 mappingTo.add(toInterval);
487 }
488
489 void resolveAndAppendMoves() {
490 if (hasMappings()) {
491 resolveMappings();
492 }
493 appendInsertionBuffer();
494 }
495 }