1 /*
2 * Copyright (c) 2015, 2018, 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
24
25 package org.graalvm.compiler.lir.alloc.lsra;
26
27 import static jdk.vm.ci.code.ValueUtil.asRegister;
28 import static jdk.vm.ci.code.ValueUtil.asStackSlot;
29 import static jdk.vm.ci.code.ValueUtil.isRegister;
30 import static jdk.vm.ci.code.ValueUtil.isStackSlot;
31 import static org.graalvm.compiler.lir.LIRValueUtil.asVariable;
32 import static org.graalvm.compiler.lir.LIRValueUtil.isVariable;
33 import static org.graalvm.compiler.lir.debug.LIRGenerationDebugContext.getSourceForOperandFromDebugContext;
34
35 import java.util.ArrayDeque;
36 import java.util.ArrayList;
37 import java.util.BitSet;
38 import java.util.EnumSet;
39
40 import jdk.internal.vm.compiler.collections.EconomicSet;
41 import jdk.internal.vm.compiler.collections.Equivalence;
42 import org.graalvm.compiler.core.common.LIRKind;
43 import org.graalvm.compiler.core.common.PermanentBailoutException;
44 import org.graalvm.compiler.core.common.alloc.ComputeBlockOrder;
45 import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
46 import org.graalvm.compiler.core.common.util.BitMap2D;
47 import org.graalvm.compiler.debug.Assertions;
48 import org.graalvm.compiler.debug.DebugContext;
49 import org.graalvm.compiler.debug.GraalError;
50 import org.graalvm.compiler.debug.Indent;
51 import org.graalvm.compiler.lir.InstructionValueConsumer;
52 import org.graalvm.compiler.lir.LIRInstruction;
53 import org.graalvm.compiler.lir.LIRInstruction.OperandFlag;
54 import org.graalvm.compiler.lir.LIRInstruction.OperandMode;
55 import org.graalvm.compiler.lir.StandardOp.LoadConstantOp;
56 import org.graalvm.compiler.lir.StandardOp.ValueMoveOp;
57 import org.graalvm.compiler.lir.ValueConsumer;
58 import org.graalvm.compiler.lir.alloc.lsra.Interval.RegisterPriority;
59 import org.graalvm.compiler.lir.alloc.lsra.Interval.SpillState;
60 import org.graalvm.compiler.lir.alloc.lsra.LinearScan.BlockData;
61 import org.graalvm.compiler.lir.gen.LIRGenerationResult;
62 import org.graalvm.compiler.lir.phases.AllocationPhase.AllocationContext;
63
64 import jdk.vm.ci.code.Register;
65 import jdk.vm.ci.code.RegisterArray;
66 import jdk.vm.ci.code.StackSlot;
67 import jdk.vm.ci.code.TargetDescription;
68 import jdk.vm.ci.meta.AllocatableValue;
69 import jdk.vm.ci.meta.Constant;
70 import jdk.vm.ci.meta.JavaConstant;
71 import jdk.vm.ci.meta.Value;
72 import jdk.vm.ci.meta.ValueKind;
73
74 public class LinearScanLifetimeAnalysisPhase extends LinearScanAllocationPhase {
75
76 protected final LinearScan allocator;
77 protected final DebugContext debug;
78
79 /**
80 * @param linearScan
81 */
82 protected LinearScanLifetimeAnalysisPhase(LinearScan linearScan) {
83 allocator = linearScan;
84 debug = allocator.getDebug();
85 }
86
87 @Override
88 protected void run(TargetDescription target, LIRGenerationResult lirGenRes, AllocationContext context) {
89 numberInstructions();
90 debug.dump(DebugContext.VERBOSE_LEVEL, lirGenRes.getLIR(), "Before register allocation");
91 computeLocalLiveSets();
92 computeGlobalLiveSets();
93 buildIntervals(Assertions.detailedAssertionsEnabled(allocator.getOptions()));
94 }
95
96 /**
97 * Bit set for each variable that is contained in each loop.
98 */
99 private BitMap2D intervalInLoop;
100
101 boolean isIntervalInLoop(int interval, int loop) {
102 return intervalInLoop.at(interval, loop);
103 }
104
105 /**
106 * Numbers all instructions in all blocks. The numbering follows the
107 * {@linkplain ComputeBlockOrder linear scan order}.
108 */
109 protected void numberInstructions() {
110
111 allocator.initIntervals();
112
113 ValueConsumer setVariableConsumer = (value, mode, flags) -> {
114 if (isVariable(value)) {
115 allocator.getOrCreateInterval(asVariable(value));
116 }
117 };
118
119 // Assign IDs to LIR nodes and build a mapping, lirOps, from ID to LIRInstruction node.
120 int numInstructions = 0;
121 for (AbstractBlockBase<?> block : allocator.sortedBlocks()) {
122 numInstructions += allocator.getLIR().getLIRforBlock(block).size();
123 }
124
125 // initialize with correct length
126 allocator.initOpIdMaps(numInstructions);
127
128 int opId = 0;
129 int index = 0;
130 for (AbstractBlockBase<?> block : allocator.sortedBlocks()) {
131 allocator.initBlockData(block);
132
133 ArrayList<LIRInstruction> instructions = allocator.getLIR().getLIRforBlock(block);
134
135 int numInst = instructions.size();
136 for (int j = 0; j < numInst; j++) {
137 LIRInstruction op = instructions.get(j);
138 op.setId(opId);
139
140 allocator.putOpIdMaps(index, op, block);
141 assert allocator.instructionForId(opId) == op : "must match";
142
143 op.visitEachTemp(setVariableConsumer);
144 op.visitEachOutput(setVariableConsumer);
145
146 index++;
147 opId += 2; // numbering of lirOps by two
148 }
149 }
150 assert index == numInstructions : "must match";
151 assert (index << 1) == opId : "must match: " + (index << 1);
152 }
153
154 /**
155 * Computes local live sets (i.e. {@link BlockData#liveGen} and {@link BlockData#liveKill})
156 * separately for each block.
157 */
158 @SuppressWarnings("try")
159 void computeLocalLiveSets() {
160 int liveSize = allocator.liveSetSize();
161
162 intervalInLoop = new BitMap2D(allocator.operandSize(), allocator.numLoops());
163
164 try {
165 final BitSet liveGenScratch = new BitSet(liveSize);
166 final BitSet liveKillScratch = new BitSet(liveSize);
167 // iterate all blocks
168 for (final AbstractBlockBase<?> block : allocator.sortedBlocks()) {
169 try (Indent indent = debug.logAndIndent("compute local live sets for block %s", block)) {
170
171 liveGenScratch.clear();
172 liveKillScratch.clear();
173
174 ArrayList<LIRInstruction> instructions = allocator.getLIR().getLIRforBlock(block);
175 int numInst = instructions.size();
176
177 ValueConsumer useConsumer = (operand, mode, flags) -> {
178 if (isVariable(operand)) {
179 int operandNum = getOperandNumber(operand);
180 if (!liveKillScratch.get(operandNum)) {
181 liveGenScratch.set(operandNum);
182 if (debug.isLogEnabled()) {
183 debug.log("liveGen for operand %d(%s)", operandNum, operand);
184 }
185 }
186 if (block.getLoop() != null) {
187 intervalInLoop.setBit(operandNum, block.getLoop().getIndex());
188 }
189 }
190
191 if (allocator.detailedAsserts) {
192 verifyInput(block, liveKillScratch, operand);
193 }
194 };
195 ValueConsumer stateConsumer = (operand, mode, flags) -> {
196 if (LinearScan.isVariableOrRegister(operand)) {
197 int operandNum = getOperandNumber(operand);
198 if (!liveKillScratch.get(operandNum)) {
199 liveGenScratch.set(operandNum);
200 if (debug.isLogEnabled()) {
201 debug.log("liveGen in state for operand %d(%s)", operandNum, operand);
202 }
203 }
204 }
205 };
206 ValueConsumer defConsumer = (operand, mode, flags) -> {
207 if (isVariable(operand)) {
208 int varNum = getOperandNumber(operand);
209 liveKillScratch.set(varNum);
210 if (debug.isLogEnabled()) {
211 debug.log("liveKill for operand %d(%s)", varNum, operand);
212 }
213 if (block.getLoop() != null) {
214 intervalInLoop.setBit(varNum, block.getLoop().getIndex());
215 }
216 }
217
218 if (allocator.detailedAsserts) {
219 /*
220 * Fixed intervals are never live at block boundaries, so they need not
221 * be processed in live sets. Process them only in debug mode so that
222 * this can be checked
223 */
224 verifyTemp(liveKillScratch, operand);
225 }
226 };
227
228 // iterate all instructions of the block
229 for (int j = 0; j < numInst; j++) {
230 final LIRInstruction op = instructions.get(j);
231
232 try (Indent indent2 = debug.logAndIndent("handle op %d: %s", op.id(), op)) {
233 op.visitEachInput(useConsumer);
234 op.visitEachAlive(useConsumer);
235 /*
236 * Add uses of live locals from interpreter's point of view for proper
237 * debug information generation.
238 */
239 op.visitEachState(stateConsumer);
240 op.visitEachTemp(defConsumer);
241 op.visitEachOutput(defConsumer);
242 }
243 } // end of instruction iteration
244
245 BlockData blockSets = allocator.getBlockData(block);
246 blockSets.liveGen = trimClone(liveGenScratch);
247 blockSets.liveKill = trimClone(liveKillScratch);
248 // sticky size, will get non-sticky in computeGlobalLiveSets
249 blockSets.liveIn = new BitSet(0);
250 blockSets.liveOut = new BitSet(0);
251
252 if (debug.isLogEnabled()) {
253 debug.log("liveGen B%d %s", block.getId(), blockSets.liveGen);
254 debug.log("liveKill B%d %s", block.getId(), blockSets.liveKill);
255 }
256
257 }
258 } // end of block iteration
259 } catch (OutOfMemoryError oom) {
260 throw new PermanentBailoutException(oom, "Out-of-memory during live set allocation of size %d", liveSize);
261 }
262 }
263
264 private void verifyTemp(BitSet liveKill, Value operand) {
265 /*
266 * Fixed intervals are never live at block boundaries, so they need not be processed in live
267 * sets. Process them only in debug mode so that this can be checked
268 */
269 if (isRegister(operand)) {
270 if (allocator.isProcessed(operand)) {
271 liveKill.set(getOperandNumber(operand));
272 }
273 }
274 }
275
276 private void verifyInput(AbstractBlockBase<?> block, BitSet liveKill, Value operand) {
277 /*
278 * Fixed intervals are never live at block boundaries, so they need not be processed in live
279 * sets. This is checked by these assertions to be sure about it. The entry block may have
280 * incoming values in registers, which is ok.
281 */
282 if (isRegister(operand) && block != allocator.getLIR().getControlFlowGraph().getStartBlock()) {
283 if (allocator.isProcessed(operand)) {
284 assert liveKill.get(getOperandNumber(operand)) : "using fixed register " + asRegister(operand) + " that is not defined in this block " + block;
285 }
286 }
287 }
288
289 protected int getOperandNumber(Value operand) {
290 return allocator.operandNumber(operand);
291 }
292
293 /**
294 * Performs a backward dataflow analysis to compute global live sets (i.e.
295 * {@link BlockData#liveIn} and {@link BlockData#liveOut}) for each block.
296 */
297 @SuppressWarnings("try")
298 protected void computeGlobalLiveSets() {
299 try (Indent indent = debug.logAndIndent("compute global live sets")) {
300 int numBlocks = allocator.blockCount();
301 boolean changeOccurred;
302 boolean changeOccurredInBlock;
303 int iterationCount = 0;
304 BitSet scratch = new BitSet(allocator.liveSetSize()); // scratch set for calculations
305
306 /*
307 * Perform a backward dataflow analysis to compute liveOut and liveIn for each block.
308 * The loop is executed until a fixpoint is reached (no changes in an iteration).
309 */
310 do {
311 changeOccurred = false;
312
313 try (Indent indent2 = debug.logAndIndent("new iteration %d", iterationCount)) {
314
315 // iterate all blocks in reverse order
316 for (int i = numBlocks - 1; i >= 0; i--) {
317 AbstractBlockBase<?> block = allocator.blockAt(i);
318 BlockData blockSets = allocator.getBlockData(block);
319
320 changeOccurredInBlock = false;
321
322 /*
323 * liveOut(block) is the union of liveIn(sux), for successors sux of block.
324 */
325 int n = block.getSuccessorCount();
326 if (n > 0) {
327 scratch.clear();
328 // block has successors
329 if (n > 0) {
330 for (AbstractBlockBase<?> successor : block.getSuccessors()) {
331 scratch.or(allocator.getBlockData(successor).liveIn);
332 }
333 }
334
335 if (!blockSets.liveOut.equals(scratch)) {
336 blockSets.liveOut = trimClone(scratch);
337
338 changeOccurred = true;
339 changeOccurredInBlock = true;
340 }
341 }
342
343 if (iterationCount == 0 || changeOccurredInBlock) {
344 /*
345 * liveIn(block) is the union of liveGen(block) with (liveOut(block) &
346 * !liveKill(block)).
347 *
348 * Note: liveIn has to be computed only in first iteration or if liveOut
349 * has changed!
350 *
351 * Note: liveIn set can only grow, never shrink. No need to clear it.
352 */
353 BitSet liveIn = blockSets.liveIn;
354 /*
355 * BitSet#or will call BitSet#ensureSize (since the bit set is of length
356 * 0 initially) and set sticky to false
357 */
358 liveIn.or(blockSets.liveOut);
359 liveIn.andNot(blockSets.liveKill);
360 liveIn.or(blockSets.liveGen);
361
362 liveIn.clone(); // trimToSize()
363
364 if (debug.isLogEnabled()) {
365 debug.log("block %d: livein = %s, liveout = %s", block.getId(), liveIn, blockSets.liveOut);
366 }
367 }
368 }
369 iterationCount++;
370
371 if (changeOccurred && iterationCount > 50) {
372 /*
373 * Very unlikely, should never happen: If it happens we cannot guarantee it
374 * won't happen again.
375 */
376 throw new PermanentBailoutException("too many iterations in computeGlobalLiveSets");
377 }
378 }
379 } while (changeOccurred);
380
381 if (Assertions.detailedAssertionsEnabled(allocator.getOptions())) {
382 verifyLiveness();
383 }
384
385 // check that the liveIn set of the first block is empty
386 AbstractBlockBase<?> startBlock = allocator.getLIR().getControlFlowGraph().getStartBlock();
387 if (allocator.getBlockData(startBlock).liveIn.cardinality() != 0) {
388 if (Assertions.detailedAssertionsEnabled(allocator.getOptions())) {
389 reportFailure(numBlocks);
390 }
391 // bailout if this occurs in product mode.
392 throw new GraalError("liveIn set of first block must be empty: " + allocator.getBlockData(startBlock).liveIn);
393 }
394 }
395 }
396
397 /**
398 * Creates a trimmed copy a bit set.
399 *
400 * {@link BitSet#clone()} cannot be used since it will not {@linkplain BitSet#trimToSize trim}
401 * the array if the bit set is {@linkplain BitSet#sizeIsSticky sticky}.
402 */
403 @SuppressWarnings("javadoc")
404 private static BitSet trimClone(BitSet set) {
405 BitSet trimmedSet = new BitSet(0); // zero-length words array, sticky
406 trimmedSet.or(set); // words size ensured to be words-in-use of set,
407 // also makes it non-sticky
408 return trimmedSet;
409 }
410
411 @SuppressWarnings("try")
412 protected void reportFailure(int numBlocks) {
413 try (DebugContext.Scope s = debug.forceLog()) {
414 try (Indent indent = debug.logAndIndent("report failure")) {
415
416 BitSet startBlockLiveIn = allocator.getBlockData(allocator.getLIR().getControlFlowGraph().getStartBlock()).liveIn;
417 try (Indent indent2 = debug.logAndIndent("Error: liveIn set of first block must be empty (when this fails, variables are used before they are defined):")) {
418 for (int operandNum = startBlockLiveIn.nextSetBit(0); operandNum >= 0; operandNum = startBlockLiveIn.nextSetBit(operandNum + 1)) {
419 Interval interval = allocator.intervalFor(operandNum);
420 if (interval != null) {
421 Value operand = interval.operand;
422 debug.log("var %d; operand=%s; node=%s", operandNum, operand, getSourceForOperandFromDebugContext(debug, operand));
423 } else {
424 debug.log("var %d; missing operand", operandNum);
425 }
426 }
427 }
428
429 // print some additional information to simplify debugging
430 for (int operandNum = startBlockLiveIn.nextSetBit(0); operandNum >= 0; operandNum = startBlockLiveIn.nextSetBit(operandNum + 1)) {
431 Interval interval = allocator.intervalFor(operandNum);
432 Value operand = null;
433 Object valueForOperandFromDebugContext = null;
434 if (interval != null) {
435 operand = interval.operand;
436 valueForOperandFromDebugContext = getSourceForOperandFromDebugContext(debug, operand);
437 }
438 try (Indent indent2 = debug.logAndIndent("---- Detailed information for var %d; operand=%s; node=%s ----", operandNum, operand, valueForOperandFromDebugContext)) {
439
440 ArrayDeque<AbstractBlockBase<?>> definedIn = new ArrayDeque<>();
441 EconomicSet<AbstractBlockBase<?>> usedIn = EconomicSet.create(Equivalence.IDENTITY);
442 for (AbstractBlockBase<?> block : allocator.sortedBlocks()) {
443 if (allocator.getBlockData(block).liveGen.get(operandNum)) {
444 usedIn.add(block);
445 try (Indent indent3 = debug.logAndIndent("used in block B%d", block.getId())) {
446 for (LIRInstruction ins : allocator.getLIR().getLIRforBlock(block)) {
447 try (Indent indent4 = debug.logAndIndent("%d: %s", ins.id(), ins)) {
448 ins.forEachState((liveStateOperand, mode, flags) -> {
449 debug.log("operand=%s", liveStateOperand);
450 return liveStateOperand;
451 });
452 }
453 }
454 }
455 }
456 if (allocator.getBlockData(block).liveKill.get(operandNum)) {
457 definedIn.add(block);
458 try (Indent indent3 = debug.logAndIndent("defined in block B%d", block.getId())) {
459 for (LIRInstruction ins : allocator.getLIR().getLIRforBlock(block)) {
460 debug.log("%d: %s", ins.id(), ins);
461 }
462 }
463 }
464 }
465
466 int[] hitCount = new int[numBlocks];
467
468 while (!definedIn.isEmpty()) {
469 AbstractBlockBase<?> block = definedIn.removeFirst();
470 usedIn.remove(block);
471 for (AbstractBlockBase<?> successor : block.getSuccessors()) {
472 if (successor.isLoopHeader()) {
473 if (!block.isLoopEnd()) {
474 definedIn.add(successor);
475 }
476 } else {
477 if (++hitCount[successor.getId()] == successor.getPredecessorCount()) {
478 definedIn.add(successor);
479 }
480 }
481 }
482 }
483 try (Indent indent3 = debug.logAndIndent("**** offending usages are in: ")) {
484 for (AbstractBlockBase<?> block : usedIn) {
485 debug.log("B%d", block.getId());
486 }
487 }
488 }
489 }
490 }
491 } catch (Throwable e) {
492 throw debug.handle(e);
493 }
494 }
495
496 protected void verifyLiveness() {
497 /*
498 * Check that fixed intervals are not live at block boundaries (live set must be empty at
499 * fixed intervals).
500 */
501 for (AbstractBlockBase<?> block : allocator.sortedBlocks()) {
502 for (int j = 0; j <= allocator.maxRegisterNumber(); j++) {
503 assert !allocator.getBlockData(block).liveIn.get(j) : "liveIn set of fixed register must be empty";
504 assert !allocator.getBlockData(block).liveOut.get(j) : "liveOut set of fixed register must be empty";
505 assert !allocator.getBlockData(block).liveGen.get(j) : "liveGen set of fixed register must be empty";
506 }
507 }
508 }
509
510 protected void addUse(AllocatableValue operand, int from, int to, RegisterPriority registerPriority, ValueKind<?> kind, boolean detailedAsserts) {
511 if (!allocator.isProcessed(operand)) {
512 return;
513 }
514
515 Interval interval = allocator.getOrCreateInterval(operand);
516 if (!kind.equals(LIRKind.Illegal)) {
517 interval.setKind(kind);
518 }
519
520 interval.addRange(from, to);
521
522 // Register use position at even instruction id.
523 interval.addUsePos(to & ~1, registerPriority, detailedAsserts);
524
525 if (debug.isLogEnabled()) {
526 debug.log("add use: %s, from %d to %d (%s)", interval, from, to, registerPriority.name());
527 }
528 }
529
530 protected void addTemp(AllocatableValue operand, int tempPos, RegisterPriority registerPriority, ValueKind<?> kind, boolean detailedAsserts) {
531 if (!allocator.isProcessed(operand)) {
532 return;
533 }
534
535 Interval interval = allocator.getOrCreateInterval(operand);
536 if (!kind.equals(LIRKind.Illegal)) {
537 interval.setKind(kind);
538 }
539
540 interval.addRange(tempPos, tempPos + 1);
541 interval.addUsePos(tempPos, registerPriority, detailedAsserts);
542 interval.addMaterializationValue(null);
543
544 if (debug.isLogEnabled()) {
545 debug.log("add temp: %s tempPos %d (%s)", interval, tempPos, RegisterPriority.MustHaveRegister.name());
546 }
547 }
548
549 protected void addDef(AllocatableValue operand, LIRInstruction op, RegisterPriority registerPriority, ValueKind<?> kind, boolean detailedAsserts) {
550 if (!allocator.isProcessed(operand)) {
551 return;
552 }
553 int defPos = op.id();
554
555 Interval interval = allocator.getOrCreateInterval(operand);
556 if (!kind.equals(LIRKind.Illegal)) {
557 interval.setKind(kind);
558 }
559
560 Range r = interval.first();
561 if (r.from <= defPos) {
562 /*
563 * Update the starting point (when a range is first created for a use, its start is the
564 * beginning of the current block until a def is encountered).
565 */
566 r.from = defPos;
567 interval.addUsePos(defPos, registerPriority, detailedAsserts);
568
569 } else {
570 /*
571 * Dead value - make vacuous interval also add register priority for dead intervals
572 */
573 interval.addRange(defPos, defPos + 1);
574 interval.addUsePos(defPos, registerPriority, detailedAsserts);
575 if (debug.isLogEnabled()) {
576 debug.log("Warning: def of operand %s at %d occurs without use", operand, defPos);
577 }
578 }
579
580 changeSpillDefinitionPos(op, operand, interval, defPos);
581 if (registerPriority == RegisterPriority.None && interval.spillState().ordinal() <= SpillState.StartInMemory.ordinal() && isStackSlot(operand)) {
582 // detection of method-parameters and roundfp-results
583 interval.setSpillState(SpillState.StartInMemory);
584 }
585 interval.addMaterializationValue(getMaterializedValue(op, operand, interval));
586
587 if (debug.isLogEnabled()) {
588 debug.log("add def: %s defPos %d (%s)", interval, defPos, registerPriority.name());
589 }
590 }
591
592 /**
593 * Optimizes moves related to incoming stack based arguments. The interval for the destination
594 * of such moves is assigned the stack slot (which is in the caller's frame) as its spill slot.
595 */
596 protected void handleMethodArguments(LIRInstruction op) {
597 if (ValueMoveOp.isValueMoveOp(op)) {
598 ValueMoveOp move = ValueMoveOp.asValueMoveOp(op);
599 if (optimizeMethodArgument(move.getInput())) {
600 StackSlot slot = asStackSlot(move.getInput());
601 if (Assertions.detailedAssertionsEnabled(allocator.getOptions())) {
602 assert op.id() > 0 : "invalid id";
603 assert allocator.blockForId(op.id()).getPredecessorCount() == 0 : "move from stack must be in first block";
604 assert isVariable(move.getResult()) : "result of move must be a variable";
605
606 if (debug.isLogEnabled()) {
607 debug.log("found move from stack slot %s to %s", slot, move.getResult());
608 }
609 }
610
611 Interval interval = allocator.intervalFor(move.getResult());
612 interval.setSpillSlot(slot);
613 interval.assignLocation(slot);
614 }
615 }
616 }
617
618 protected void addRegisterHint(final LIRInstruction op, final Value targetValue, OperandMode mode, EnumSet<OperandFlag> flags, final boolean hintAtDef) {
619 if (flags.contains(OperandFlag.HINT) && LinearScan.isVariableOrRegister(targetValue)) {
620
621 op.forEachRegisterHint(targetValue, mode, (registerHint, valueMode, valueFlags) -> {
622 if (LinearScan.isVariableOrRegister(registerHint)) {
623 Interval from = allocator.getOrCreateInterval((AllocatableValue) registerHint);
624 Interval to = allocator.getOrCreateInterval((AllocatableValue) targetValue);
625
626 /* hints always point from def to use */
627 if (hintAtDef) {
628 to.setLocationHint(from);
629 } else {
630 from.setLocationHint(to);
631 }
632 if (debug.isLogEnabled()) {
633 debug.log("operation at opId %d: added hint from interval %d to %d", op.id(), from.operandNumber, to.operandNumber);
634 }
635
636 return registerHint;
637 }
638 return null;
639 });
640 }
641 }
642
643 /**
644 * Eliminates moves from register to stack if the stack slot is known to be correct.
645 *
646 * @param op
647 * @param operand
648 */
649 protected void changeSpillDefinitionPos(LIRInstruction op, AllocatableValue operand, Interval interval, int defPos) {
650 assert interval.isSplitParent() : "can only be called for split parents";
651
652 switch (interval.spillState()) {
653 case NoDefinitionFound:
654 assert interval.spillDefinitionPos() == -1 : "must no be set before";
655 interval.setSpillDefinitionPos(defPos);
656 interval.setSpillState(SpillState.NoSpillStore);
657 break;
658
659 case NoSpillStore:
660 assert defPos <= interval.spillDefinitionPos() : "positions are processed in reverse order when intervals are created";
661 if (defPos < interval.spillDefinitionPos() - 2) {
662 // second definition found, so no spill optimization possible for this interval
663 interval.setSpillState(SpillState.NoOptimization);
664 } else {
665 // two consecutive definitions (because of two-operand LIR form)
666 assert allocator.blockForId(defPos) == allocator.blockForId(interval.spillDefinitionPos()) : "block must be equal";
667 }
668 break;
669
670 case NoOptimization:
671 // nothing to do
672 break;
673
674 default:
675 throw GraalError.shouldNotReachHere("other states not allowed at this time");
676 }
677 }
678
679 private static boolean optimizeMethodArgument(Value value) {
680 /*
681 * Object method arguments that are passed on the stack are currently not optimized because
682 * this requires that the runtime visits method arguments during stack walking.
683 */
684 return isStackSlot(value) && asStackSlot(value).isInCallerFrame() && LIRKind.isValue(value);
685 }
686
687 /**
688 * Determines the register priority for an instruction's output/result operand.
689 */
690 protected RegisterPriority registerPriorityOfOutputOperand(LIRInstruction op) {
691 if (ValueMoveOp.isValueMoveOp(op)) {
692 ValueMoveOp move = ValueMoveOp.asValueMoveOp(op);
693 if (optimizeMethodArgument(move.getInput())) {
694 return RegisterPriority.None;
695 }
696 }
697
698 // all other operands require a register
699 return RegisterPriority.MustHaveRegister;
700 }
701
702 /**
703 * Determines the priority which with an instruction's input operand will be allocated a
704 * register.
705 */
706 protected static RegisterPriority registerPriorityOfInputOperand(EnumSet<OperandFlag> flags) {
707 if (flags.contains(OperandFlag.STACK)) {
708 return RegisterPriority.ShouldHaveRegister;
709 }
710 // all other operands require a register
711 return RegisterPriority.MustHaveRegister;
712 }
713
714 @SuppressWarnings("try")
715 protected void buildIntervals(boolean detailedAsserts) {
716
717 try (Indent indent = debug.logAndIndent("build intervals")) {
718 InstructionValueConsumer outputConsumer = (op, operand, mode, flags) -> {
719 if (LinearScan.isVariableOrRegister(operand)) {
720 addDef((AllocatableValue) operand, op, registerPriorityOfOutputOperand(op), operand.getValueKind(), detailedAsserts);
721 addRegisterHint(op, operand, mode, flags, true);
722 }
723 };
724
725 InstructionValueConsumer tempConsumer = (op, operand, mode, flags) -> {
726 if (LinearScan.isVariableOrRegister(operand)) {
727 addTemp((AllocatableValue) operand, op.id(), RegisterPriority.MustHaveRegister, operand.getValueKind(), detailedAsserts);
728 addRegisterHint(op, operand, mode, flags, false);
729 }
730 };
731
732 InstructionValueConsumer aliveConsumer = (op, operand, mode, flags) -> {
733 if (LinearScan.isVariableOrRegister(operand)) {
734 RegisterPriority p = registerPriorityOfInputOperand(flags);
735 int opId = op.id();
736 int blockFrom = allocator.getFirstLirInstructionId((allocator.blockForId(opId)));
737 addUse((AllocatableValue) operand, blockFrom, opId + 1, p, operand.getValueKind(), detailedAsserts);
738 addRegisterHint(op, operand, mode, flags, false);
739 }
740 };
741
742 InstructionValueConsumer inputConsumer = (op, operand, mode, flags) -> {
743 if (LinearScan.isVariableOrRegister(operand)) {
744 int opId = op.id();
745 int blockFrom = allocator.getFirstLirInstructionId((allocator.blockForId(opId)));
746 RegisterPriority p = registerPriorityOfInputOperand(flags);
747 addUse((AllocatableValue) operand, blockFrom, opId, p, operand.getValueKind(), detailedAsserts);
748 addRegisterHint(op, operand, mode, flags, false);
749 }
750 };
751
752 InstructionValueConsumer stateProc = (op, operand, mode, flags) -> {
753 if (LinearScan.isVariableOrRegister(operand)) {
754 int opId = op.id();
755 int blockFrom = allocator.getFirstLirInstructionId((allocator.blockForId(opId)));
756 addUse((AllocatableValue) operand, blockFrom, opId + 1, RegisterPriority.None, operand.getValueKind(), detailedAsserts);
757 }
758 };
759
760 // create a list with all caller-save registers (cpu, fpu, xmm)
761 RegisterArray callerSaveRegs = allocator.getRegisterAllocationConfig().getRegisterConfig().getCallerSaveRegisters();
762
763 // iterate all blocks in reverse order
764 for (int i = allocator.blockCount() - 1; i >= 0; i--) {
765
766 AbstractBlockBase<?> block = allocator.blockAt(i);
767 try (Indent indent2 = debug.logAndIndent("handle block %d", block.getId())) {
768
769 ArrayList<LIRInstruction> instructions = allocator.getLIR().getLIRforBlock(block);
770 final int blockFrom = allocator.getFirstLirInstructionId(block);
771 int blockTo = allocator.getLastLirInstructionId(block);
772
773 assert blockFrom == instructions.get(0).id();
774 assert blockTo == instructions.get(instructions.size() - 1).id();
775
776 // Update intervals for operands live at the end of this block;
777 BitSet live = allocator.getBlockData(block).liveOut;
778 for (int operandNum = live.nextSetBit(0); operandNum >= 0; operandNum = live.nextSetBit(operandNum + 1)) {
779 assert live.get(operandNum) : "should not stop here otherwise";
780 AllocatableValue operand = allocator.intervalFor(operandNum).operand;
781 if (debug.isLogEnabled()) {
782 debug.log("live in %d: %s", operandNum, operand);
783 }
784
785 addUse(operand, blockFrom, blockTo + 2, RegisterPriority.None, LIRKind.Illegal, detailedAsserts);
786
787 /*
788 * Add special use positions for loop-end blocks when the interval is used
789 * anywhere inside this loop. It's possible that the block was part of a
790 * non-natural loop, so it might have an invalid loop index.
791 */
792 if (block.isLoopEnd() && block.getLoop() != null && isIntervalInLoop(operandNum, block.getLoop().getIndex())) {
793 allocator.intervalFor(operandNum).addUsePos(blockTo + 1, RegisterPriority.LiveAtLoopEnd, detailedAsserts);
794 }
795 }
796
797 /*
798 * Iterate all instructions of the block in reverse order. definitions of
799 * intervals are processed before uses.
800 */
801 for (int j = instructions.size() - 1; j >= 0; j--) {
802 final LIRInstruction op = instructions.get(j);
803 final int opId = op.id();
804
805 try (Indent indent3 = debug.logAndIndent("handle inst %d: %s", opId, op)) {
806
807 // add a temp range for each register if operation destroys
808 // caller-save registers
809 if (op.destroysCallerSavedRegisters()) {
810 for (Register r : callerSaveRegs) {
811 if (allocator.attributes(r).isAllocatable()) {
812 addTemp(r.asValue(), opId, RegisterPriority.None, LIRKind.Illegal, detailedAsserts);
813 }
814 }
815 if (debug.isLogEnabled()) {
816 debug.log("operation destroys all caller-save registers");
817 }
818 }
819
820 op.visitEachOutput(outputConsumer);
821 op.visitEachTemp(tempConsumer);
822 op.visitEachAlive(aliveConsumer);
823 op.visitEachInput(inputConsumer);
824
825 /*
826 * Add uses of live locals from interpreter's point of view for proper
827 * debug information generation. Treat these operands as temp values (if
828 * the live range is extended to a call site, the value would be in a
829 * register at the call otherwise).
830 */
831 op.visitEachState(stateProc);
832
833 // special steps for some instructions (especially moves)
834 handleMethodArguments(op);
835
836 }
837
838 } // end of instruction iteration
839 }
840 } // end of block iteration
841
842 /*
843 * Add the range [0, 1] to all fixed intervals. the register allocator need not handle
844 * unhandled fixed intervals.
845 */
846 for (Interval interval : allocator.intervals()) {
847 if (interval != null && isRegister(interval.operand)) {
848 interval.addRange(0, 1);
849 }
850 }
851 }
852 }
853
854 /**
855 * Returns a value for a interval definition, which can be used for re-materialization.
856 *
857 * @param op An instruction which defines a value
858 * @param operand The destination operand of the instruction
859 * @param interval The interval for this defined value.
860 * @return Returns the value which is moved to the instruction and which can be reused at all
861 * reload-locations in case the interval of this instruction is spilled. Currently this
862 * can only be a {@link JavaConstant}.
863 */
864 protected Constant getMaterializedValue(LIRInstruction op, Value operand, Interval interval) {
865 if (LoadConstantOp.isLoadConstantOp(op)) {
866 LoadConstantOp move = LoadConstantOp.asLoadConstantOp(op);
867
868 if (!allocator.neverSpillConstants()) {
869 /*
870 * Check if the interval has any uses which would accept an stack location (priority
871 * == ShouldHaveRegister). Rematerialization of such intervals can result in a
872 * degradation, because rematerialization always inserts a constant load, even if
873 * the value is not needed in a register.
874 */
875 Interval.UsePosList usePosList = interval.usePosList();
876 int numUsePos = usePosList.size();
877 for (int useIdx = 0; useIdx < numUsePos; useIdx++) {
878 Interval.RegisterPriority priority = usePosList.registerPriority(useIdx);
879 if (priority == Interval.RegisterPriority.ShouldHaveRegister) {
880 return null;
881 }
882 }
883 }
884 return move.getConstant();
885 }
886 return null;
887 }
888 }