1 /*
2 * Copyright (c) 2016, 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.bu;
24
25 import static jdk.vm.ci.code.ValueUtil.asAllocatableValue;
26 import static jdk.vm.ci.code.ValueUtil.asRegister;
27 import static jdk.vm.ci.code.ValueUtil.isIllegal;
28 import static jdk.vm.ci.code.ValueUtil.isRegister;
29 import static org.graalvm.compiler.core.common.GraalOptions.DetailedAsserts;
30 import static org.graalvm.compiler.lir.LIRValueUtil.asVariable;
31 import static org.graalvm.compiler.lir.LIRValueUtil.isConstantValue;
32 import static org.graalvm.compiler.lir.LIRValueUtil.isStackSlotValue;
33 import static org.graalvm.compiler.lir.LIRValueUtil.isVariable;
34
35 import java.util.ArrayList;
36 import java.util.BitSet;
37 import java.util.Collections;
38 import java.util.EnumSet;
39
40 import org.graalvm.compiler.core.common.alloc.RegisterAllocationConfig;
41 import org.graalvm.compiler.core.common.alloc.RegisterAllocationConfig.AllocatableRegisters;
42 import org.graalvm.compiler.core.common.alloc.Trace;
43 import org.graalvm.compiler.core.common.alloc.TraceBuilderResult;
44 import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
45 import org.graalvm.compiler.debug.Debug;
46 import org.graalvm.compiler.debug.Debug.Scope;
47 import org.graalvm.compiler.debug.Indent;
48 import org.graalvm.compiler.lir.InstructionValueProcedure;
49 import org.graalvm.compiler.lir.LIR;
50 import org.graalvm.compiler.lir.LIRInstruction;
51 import org.graalvm.compiler.lir.LIRInstruction.OperandFlag;
52 import org.graalvm.compiler.lir.LIRInstruction.OperandMode;
53 import org.graalvm.compiler.lir.LIRValueUtil;
54 import org.graalvm.compiler.lir.RedundantMoveElimination;
55 import org.graalvm.compiler.lir.StandardOp;
56 import org.graalvm.compiler.lir.StandardOp.BlockEndOp;
57 import org.graalvm.compiler.lir.StandardOp.JumpOp;
58 import org.graalvm.compiler.lir.StandardOp.LabelOp;
59 import org.graalvm.compiler.lir.Variable;
60 import org.graalvm.compiler.lir.VirtualStackSlot;
61 import org.graalvm.compiler.lir.alloc.OutOfRegistersException;
62 import org.graalvm.compiler.lir.alloc.trace.GlobalLivenessInfo;
63 import org.graalvm.compiler.lir.alloc.trace.TraceAllocationPhase;
64 import org.graalvm.compiler.lir.alloc.trace.TraceAllocationPhase.TraceAllocationContext;
65 import org.graalvm.compiler.lir.alloc.trace.TraceGlobalMoveResolutionPhase;
66 import org.graalvm.compiler.lir.alloc.trace.TraceGlobalMoveResolver;
67 import org.graalvm.compiler.lir.alloc.trace.TraceRegisterAllocationPhase;
68 import org.graalvm.compiler.lir.gen.LIRGenerationResult;
69 import org.graalvm.compiler.lir.gen.LIRGeneratorTool.MoveFactory;
70 import org.graalvm.compiler.lir.ssa.SSAUtil;
71
72 import jdk.vm.ci.code.Register;
73 import jdk.vm.ci.code.RegisterArray;
74 import jdk.vm.ci.code.RegisterAttributes;
75 import jdk.vm.ci.code.RegisterValue;
76 import jdk.vm.ci.code.TargetDescription;
77 import jdk.vm.ci.common.JVMCIError;
78 import jdk.vm.ci.meta.AllocatableValue;
79 import jdk.vm.ci.meta.PlatformKind;
80 import jdk.vm.ci.meta.Value;
81
82 /**
83 * Allocates registers within a trace in a greedy, bottom-up fashion. The liveness information is
84 * computed on the fly as the instructions are traversed instead of computing it in a separate pass.
85 * The goal of this allocator is to provide a simple and fast algorithm for situations where code
86 * quality is not the primary target.
87 *
88 * This implementation does not (yet) exploit hinting information and might introduce multiple spill
89 * moves to the same stack slot (which are likely to be remove by {@link RedundantMoveElimination}.
90 *
91 * The current implementation cannot deal with {@link AbstractBlockBase blocks} with edges to
92 * compiled exception handlers since it might introduce spill code after the {@link LIRInstruction
93 * instruction} that triggers the exception.
94 */
95 public final class BottomUpAllocator extends TraceAllocationPhase<TraceAllocationContext> {
96 private final TargetDescription target;
97 private final LIRGenerationResult lirGenRes;
98 private final MoveFactory spillMoveFactory;
99 private final RegisterAllocationConfig registerAllocationConfig;
100 private final RegisterArray callerSaveRegs;
101 private final RegisterAttributes[] registerAttributes;
102 private final BitSet allocatedBlocks;
103 private final TraceBuilderResult resultTraces;
104 private final TraceGlobalMoveResolver moveResolver;
105
106 /**
107 * Maps from {@link Variable#index} to a spill stack slot. If
108 * {@linkplain org.graalvm.compiler.lir.alloc.trace.TraceRegisterAllocationPhase.Options#TraceRACacheStackSlots
109 * enabled} a {@link Variable} is always assigned to the same stack slot.
110 */
111 private final AllocatableValue[] stackSlots;
112
113 private final ArrayList<LIRInstruction> insertInstructionsBefore;
114 private final ArrayList<LIRInstruction> insertInstructionsAfter;
115 private final boolean neverSpillConstants;
116
117 private final GlobalLivenessInfo livenessInfo;
118
119 public BottomUpAllocator(TargetDescription target, LIRGenerationResult lirGenRes, MoveFactory spillMoveFactory, RegisterAllocationConfig registerAllocationConfig,
120 AllocatableValue[] cachedStackSlots, TraceBuilderResult resultTraces, boolean neverSpillConstant, GlobalLivenessInfo livenessInfo) {
121 this.target = target;
122 this.lirGenRes = lirGenRes;
123 this.spillMoveFactory = spillMoveFactory;
124 this.registerAllocationConfig = registerAllocationConfig;
125 this.callerSaveRegs = registerAllocationConfig.getRegisterConfig().getCallerSaveRegisters();
126 this.registerAttributes = registerAllocationConfig.getRegisterConfig().getAttributesMap();
127 this.allocatedBlocks = new BitSet(lirGenRes.getLIR().getControlFlowGraph().getBlocks().length);
128 this.resultTraces = resultTraces;
129 this.moveResolver = new TraceGlobalMoveResolver(lirGenRes, spillMoveFactory, registerAllocationConfig, target.arch);
130 this.neverSpillConstants = neverSpillConstant;
131 this.livenessInfo = livenessInfo;
132
133 this.insertInstructionsBefore = new ArrayList<>(4);
134 this.insertInstructionsAfter = new ArrayList<>(4);
135
136 if (TraceRegisterAllocationPhase.Options.TraceRACacheStackSlots.getValue(lirGenRes.getLIR().getOptions())) {
137 this.stackSlots = cachedStackSlots;
138 } else {
139 this.stackSlots = new AllocatableValue[lirGenRes.getLIR().numVariables()];
140 }
141
142 }
143
144 private LIR getLIR() {
145 return lirGenRes.getLIR();
146 }
147
148 /**
149 * Gets an object describing the attributes of a given register according to this register
150 * configuration.
151 */
152 private RegisterAttributes attributes(Register reg) {
153 return registerAttributes[reg.number];
154 }
155
156 /**
157 * Returns a new spill slot or a cached entry if there is already one for the variable.
158 */
159 private AllocatableValue allocateSpillSlot(Variable var) {
160 int variableIndex = var.index;
161 AllocatableValue cachedStackSlot = stackSlots[variableIndex];
162 if (cachedStackSlot != null) {
163 TraceRegisterAllocationPhase.globalStackSlots.increment();
164 assert cachedStackSlot.getValueKind().equals(var.getValueKind()) : "CachedStackSlot: kind mismatch? " + var.getValueKind() + " vs. " + cachedStackSlot.getValueKind();
165 return cachedStackSlot;
166 }
167 VirtualStackSlot slot = lirGenRes.getFrameMapBuilder().allocateSpillSlot(var.getValueKind());
168 stackSlots[variableIndex] = slot;
169 TraceRegisterAllocationPhase.allocatedStackSlots.increment();
170 return slot;
171 }
172
173 @Override
174 protected void run(@SuppressWarnings("hiding") TargetDescription target, @SuppressWarnings("hiding") LIRGenerationResult lirGenRes, Trace trace, TraceAllocationContext context) {
175 allocate(trace);
176 }
177
178 private void allocate(Trace trace) {
179 if (neverSpillConstants) {
180 throw JVMCIError.unimplemented("NeverSpillConstant not supported!");
181 }
182 new Allocator().allocateTrace(trace);
183 assert verify(trace);
184 }
185
186 private boolean verify(Trace trace) {
187 for (AbstractBlockBase<?> block : trace.getBlocks()) {
188 assert LIR.verifyBlock(lirGenRes.getLIR(), block);
189 }
190 return true;
191 }
192
193 private static boolean requiresRegisters(LIRInstruction instruction, Value value, OperandMode mode, EnumSet<OperandFlag> flags) {
194 assert isVariable(value) : "Not a variable " + value;
195 if (instruction instanceof LabelOp) {
196 // phi and incoming values do not require a register
197 return false;
198 }
199 if (mode == OperandMode.DEF || mode == OperandMode.TEMP) {
200 return true;
201 }
202 return !flags.contains(OperandFlag.STACK);
203 }
204
205 private void resolveFindInsertPos(AbstractBlockBase<?> fromBlock, AbstractBlockBase<?> toBlock) {
206 LIR lir = lirGenRes.getLIR();
207 if (fromBlock.getSuccessorCount() <= 1) {
208 if (Debug.isLogEnabled()) {
209 Debug.log("inserting moves at end of fromBlock B%d", fromBlock.getId());
210 }
211
212 ArrayList<LIRInstruction> instructions = lir.getLIRforBlock(fromBlock);
213 LIRInstruction instr = instructions.get(instructions.size() - 1);
214 if (instr instanceof StandardOp.JumpOp) {
215 // insert moves before branch
216 moveResolver.setInsertPosition(instructions, instructions.size() - 1);
217 } else {
218 moveResolver.setInsertPosition(instructions, instructions.size());
219 }
220
221 } else {
222 if (Debug.isLogEnabled()) {
223 Debug.log("inserting moves at beginning of toBlock B%d", toBlock.getId());
224 }
225
226 if (DetailedAsserts.getValue(getLIR().getOptions())) {
227 assert lir.getLIRforBlock(fromBlock).get(0) instanceof StandardOp.LabelOp : "block does not start with a label";
228
229 /*
230 * Because the number of predecessor edges matches the number of successor edges,
231 * blocks which are reached by switch statements may have be more than one
232 * predecessor but it will be guaranteed that all predecessors will be the same.
233 */
234 for (AbstractBlockBase<?> predecessor : toBlock.getPredecessors()) {
235 assert fromBlock == predecessor : "all critical edges must be broken";
236 }
237 }
238
239 moveResolver.setInsertPosition(lir.getLIRforBlock(toBlock), 1);
240 }
241 }
242
243 private final class Allocator {
244
245 /**
246 * Maps from {@linkplain Register#number register} to the current {@linkplain Variable
247 * variable}.
248 */
249 private final AllocatableValue[] currentRegisterMapping;
250 /**
251 * Maps from {@linkplain Variable#index variable} to its current location.
252 */
253 private final AllocatableValue[] locations;
254
255 private final int[] lastRegisterUsage;
256 private final int[] lastRegisterKill;
257
258 private ArrayList<LIRInstruction> currentInstructions;
259 private int currentInstructionIndex;
260 private int currentOpId;
261
262 private Allocator() {
263 RegisterArray registers = target.arch.getRegisters();
264 int numRegs = registers.size();
265 int numVar = getLIR().numVariables();
266 currentRegisterMapping = new AllocatableValue[numRegs];
267 lastRegisterUsage = new int[numRegs];
268 lastRegisterKill = new int[numRegs];
269 locations = new AllocatableValue[numVar];
270 // we start at offset 2 to distinguish if from the default value
271 currentOpId = 2;
272 }
273
274 private void setCurrentValue(Register reg, AllocatableValue val) {
275 currentRegisterMapping[reg.number] = val;
276 }
277
278 private AllocatableValue getCurrentValue(Register reg) {
279 return currentRegisterMapping[reg.number];
280 }
281
282 private int getLastRegisterUsage(Register reg) {
283 return lastRegisterUsage[reg.number];
284 }
285
286 private void setLastRegisterUsage(Register reg, int pos) {
287 Debug.log("Register %s last used %d", reg, pos);
288 lastRegisterUsage[reg.number] = pos;
289 }
290
291 private int getLastRegisterKill(Register reg) {
292 return lastRegisterKill[reg.number];
293 }
294
295 private void setLastRegisterKill(Register reg, int pos) {
296 Debug.log("Register %s killed %d", reg, pos);
297 lastRegisterKill[reg.number] = pos;
298 }
299
300 private void setCurrentLocation(Variable var, AllocatableValue location) {
301 locations[var.index] = location;
302 }
303
304 private AllocatableValue getCurrentLocation(Variable var) {
305 return locations[var.index];
306 }
307
308 private void insertSpillMoveBefore(AllocatableValue dst, Value src) {
309 LIRInstruction move = spillMoveFactory.createMove(dst, src);
310 insertInstructionsBefore.add(move);
311 move.setComment(lirGenRes, "BottomUp: spill move before");
312 Debug.log("insert before %s", move);
313 }
314
315 private void insertSpillMoveAfter(AllocatableValue dst, Value src) {
316 LIRInstruction inst = currentInstructions.get(currentInstructionIndex);
317 if (!(inst instanceof BlockEndOp)) {
318 LIRInstruction move = spillMoveFactory.createMove(dst, src);
319 insertInstructionsAfter.add(move);
320 move.setComment(lirGenRes, "BottomUp: spill move after");
321 Debug.log("insert after %s", move);
322 } else {
323 Debug.log("Block end op. No from %s to %s necessary.", src, dst);
324 requireResolution = true;
325 }
326 }
327
328 private void insertInstructions() {
329 // TODO (je) this is can probably be improved
330 currentInstructions.ensureCapacity(currentInstructions.size() + insertInstructionsBefore.size() + insertInstructionsAfter.size());
331 LIRInstruction inst = currentInstructions.get(currentInstructionIndex);
332 // insert after
333 if (insertInstructionsAfter.size() != 0) {
334 Collections.reverse(insertInstructionsAfter);
335 assert !(inst instanceof BlockEndOp) : "Cannot insert instruction after the block end op: " + inst;
336 currentInstructions.addAll(currentInstructionIndex + 1, insertInstructionsAfter);
337 insertInstructionsAfter.clear();
338 }
339 // insert before
340 if (insertInstructionsBefore.size() != 0) {
341 assert !(inst instanceof LabelOp) : "Cannot insert instruction before the label op: " + inst;
342 currentInstructions.addAll(currentInstructionIndex, insertInstructionsBefore);
343 insertInstructionsBefore.clear();
344 }
345 }
346
347 @SuppressWarnings("try")
348 private void allocateTrace(Trace trace) {
349 try (Scope s = Debug.scope("BottomUpAllocator", trace.getBlocks()); Indent indent = Debug.logAndIndent("%s (Trace%d)", trace, trace.getId())) {
350 AbstractBlockBase<?>[] blocks = trace.getBlocks();
351 int lastBlockIdx = blocks.length - 1;
352 AbstractBlockBase<?> successorBlock = blocks[lastBlockIdx];
353 // handle last block
354 allocateBlock(successorBlock);
355 // handle remaining blocks
356 for (int i = lastBlockIdx - 1; i >= 0; i--) {
357 AbstractBlockBase<?> block = blocks[i];
358 // handle PHIs
359 resolvePhis(block, successorBlock);
360 boolean needResolution = allocateBlock(block);
361
362 if (needResolution) {
363 // resolve local data flow
364 resolveIntraTraceEdge(block, successorBlock);
365 }
366 successorBlock = block;
367 }
368 resolveLoopBackEdge(trace);
369 } catch (Throwable e) {
370 throw Debug.handle(e);
371 }
372 }
373
374 private final ArrayList<LIRInstruction> phiResolutionMoves = new ArrayList<>();
375
376 /**
377 * Resolve phi values, i.e., set the current location of values in the predecessors block
378 * (which is not yet allocated) to the location of the variable defined by the phi in the
379 * successor (which is already allocated). For constant inputs we insert moves.
380 */
381 private void resolvePhis(AbstractBlockBase<?> from, AbstractBlockBase<?> to) {
382 if (SSAUtil.isMerge(to)) {
383 JumpOp jump = SSAUtil.phiOut(getLIR(), from);
384 LabelOp label = SSAUtil.phiIn(getLIR(), to);
385
386 assert phiResolutionMoves.isEmpty();
387
388 for (int i = 0; i < label.getPhiSize(); i++) {
389 visitPhiValuePair(jump.getOutgoingValue(i), label.getIncomingValue(i));
390 }
391 if (!phiResolutionMoves.isEmpty()) {
392 ArrayList<LIRInstruction> instructions = getLIR().getLIRforBlock(from);
393 instructions.addAll(instructions.size() - 1, phiResolutionMoves);
394 phiResolutionMoves.clear();
395 }
396 }
397 }
398
399 private void visitPhiValuePair(Value phiOut, Value phiIn) {
400 assert isStackSlotValue(phiIn) || isRegister(phiIn) : "PHI defined values is not a register or stack slot: " + phiIn;
401 AllocatableValue in = asAllocatableValue(phiIn);
402
403 AllocatableValue dest = isRegister(in) ? getCurrentValue(asRegister(in)) : in;
404 final LIRInstruction move;
405 if (isConstantValue(phiOut)) {
406 // insert move from constant
407 move = spillMoveFactory.createLoad(dest, LIRValueUtil.asConstant(phiOut));
408 } else {
409 assert isVariable(phiOut) : "Not a variable or constant: " + phiOut;
410 // insert move from variable
411 move = spillMoveFactory.createMove(dest, asVariable(phiOut));
412 }
413 Debug.log("Inserting load %s", move);
414 move.setComment(lirGenRes, "BottomUp: phi resolution");
415 phiResolutionMoves.add(move);
416 }
417
418 private boolean requireResolution;
419
420 /**
421 * Intra-trace edges, i.e., edge where both, the source and the target block are in the same
422 * trace, are either
423 * <ul>
424 * <li><em>immediate forward edges</em>, i.e., an edge from {@code i}th block of the trace
425 * to the {@code (i+1)}th block, or
426 * <li>a <em>loop back-edge</em> from the last block of the trace to the loop header.
427 * </ul>
428 * This property is guaranteed due to splitting of <em>critical edge</em>.
429 *
430 * Since forward edges are handled locally during bottom-up allocation we only need to check
431 * for the second case.
432 */
433 private void resolveLoopBackEdge(Trace trace) {
434 AbstractBlockBase<?>[] blocks = trace.getBlocks();
435 AbstractBlockBase<?> endBlock = blocks[blocks.length - 1];
436 if (endBlock.isLoopEnd()) {
437 assert endBlock.getSuccessorCount() == 1;
438 AbstractBlockBase<?> targetBlock = endBlock.getSuccessors()[0];
439 assert targetBlock.isLoopHeader() : String.format("Successor %s or loop end %s is not a loop header?", targetBlock, endBlock);
440 if (resultTraces.getTraceForBlock(targetBlock).equals(trace)) {
441 resolveLoopBackEdge(endBlock, targetBlock);
442 }
443 }
444 }
445
446 private void resolveLoopBackEdge(AbstractBlockBase<?> from, AbstractBlockBase<?> to) {
447 assert resultTraces.getTraceForBlock(from).equals(resultTraces.getTraceForBlock(to)) : "Not on the same trace? " + from + " -> " + to;
448 resolveFindInsertPos(from, to);
449 LIR lir = getLIR();
450
451 if (SSAUtil.isMerge(to)) {
452 JumpOp blockEnd = SSAUtil.phiOut(lir, from);
453 LabelOp label = SSAUtil.phiIn(lir, to);
454
455 for (int i = 0; i < label.getPhiSize(); i++) {
456 Value incomingValue = label.getIncomingValue(i);
457 Value outgoingValue = blockEnd.getOutgoingValue(i);
458 resolveValuePair(incomingValue, outgoingValue);
459 }
460 }
461 resolveTraceEdge(from, to);
462 moveResolver.resolveAndAppendMoves();
463 }
464
465 private void resolveIntraTraceEdge(AbstractBlockBase<?> from, AbstractBlockBase<?> to) {
466 assert resultTraces.getTraceForBlock(from).equals(resultTraces.getTraceForBlock(to)) : "Not on the same trace? " + from + " -> " + to;
467 resolveFindInsertPos(from, to);
468 resolveTraceEdge(from, to);
469 moveResolver.resolveAndAppendMoves();
470 }
471
472 private void resolveTraceEdge(AbstractBlockBase<?> from, AbstractBlockBase<?> to) {
473 Value[] out = livenessInfo.getOutLocation(from);
474 Value[] in = livenessInfo.getInLocation(to);
475
476 assert out != null;
477 assert in != null;
478 assert out.length == in.length;
479
480 for (int i = 0; i < out.length; i++) {
481 Value incomingValue = in[i];
482 Value outgoingValue = out[i];
483 resolveValuePair(incomingValue, outgoingValue);
484 }
485 }
486
487 private void resolveValuePair(Value incomingValue, Value outgoingValue) {
488 if (!isIllegal(incomingValue) && !TraceGlobalMoveResolver.isMoveToSelf(outgoingValue, incomingValue)) {
489 TraceGlobalMoveResolutionPhase.addMapping(moveResolver, outgoingValue, incomingValue);
490 }
491 }
492
493 /**
494 * @return {@code true} if the block requires data-flow resolution.
495 */
496 @SuppressWarnings("try")
497 private boolean allocateBlock(AbstractBlockBase<?> block) {
498 // might be set in insertSpillMoveAfter
499 requireResolution = false;
500
501 try (Indent indent = Debug.logAndIndent("handle block %s", block)) {
502 currentInstructions = getLIR().getLIRforBlock(block);
503 for (currentInstructionIndex = currentInstructions.size() - 1; currentInstructionIndex >= 0; currentInstructionIndex--) {
504 LIRInstruction inst = currentInstructions.get(currentInstructionIndex);
505 if (inst != null) {
506 inst.setId(currentOpId);
507 allocateInstruction(inst, block);
508 }
509 }
510 allocatedBlocks.set(block.getId());
511 }
512 return requireResolution;
513 }
514
515 @SuppressWarnings("try")
516 private void allocateInstruction(LIRInstruction op, AbstractBlockBase<?> block) {
517 assert op != null && op.id() == currentOpId;
518 try (Indent indent = Debug.logAndIndent("handle inst: %d: %s", op.id(), op)) {
519 try (Indent indent1 = Debug.logAndIndent("output pos")) {
520 // spill caller saved registers
521 if (op.destroysCallerSavedRegisters()) {
522 spillCallerSavedRegisters();
523 }
524
525 // fixed
526 op.forEachOutput(allocFixedRegisterProcedure);
527 op.forEachTemp(allocFixedRegisterProcedure);
528 op.forEachAlive(allocFixedRegisterProcedure);
529 // variable
530 op.forEachOutput(allocRegisterProcedure);
531 op.forEachTemp(allocRegisterProcedure);
532 op.forEachAlive(allocRegisterProcedure);
533 /* state do never require a register */
534 // op.forEachState(allocRegisterProcedure);
535
536 // should have
537 op.forEachTemp(allocStackOrRegisterProcedure);
538 op.forEachOutput(allocStackOrRegisterProcedure);
539 if (op instanceof LabelOp) {
540 processIncoming(block, op);
541 }
542 }
543 try (Indent indent1 = Debug.logAndIndent("input pos")) {
544
545 currentOpId++;
546
547 // fixed
548 op.forEachInput(allocFixedRegisterProcedure);
549 // variable
550 op.forEachInput(allocRegisterProcedure);
551
552 op.forEachAlive(allocStackOrRegisterProcedure);
553 if (op instanceof BlockEndOp) {
554 processOutgoing(block, op);
555 }
556 op.forEachState(allocStackOrRegisterProcedure);
557 op.forEachInput(allocStackOrRegisterProcedure);
558 }
559
560 // insert spill/load instructions
561 insertInstructions();
562 currentOpId++;
563 }
564 }
565
566 private void processIncoming(AbstractBlockBase<?> block, LIRInstruction instruction) {
567 int[] vars = livenessInfo.getBlockIn(block);
568 Value[] locs = new Value[vars.length];
569 for (int i = 0; i < vars.length; i++) {
570 int varNum = vars[i];
571 if (varNum >= 0) {
572 locs[i] = allocStackOrRegister(instruction, livenessInfo.getVariable(varNum), OperandMode.DEF, LabelOp.incomingFlags);
573 }
574 }
575 livenessInfo.setInLocations(block, locs);
576 }
577
578 private void processOutgoing(AbstractBlockBase<?> block, LIRInstruction instruction) {
579 int[] vars = livenessInfo.getBlockOut(block);
580 Value[] locs = new Value[vars.length];
581 for (int i = 0; i < vars.length; i++) {
582 locs[i] = allocStackOrRegister(instruction, livenessInfo.getVariable(vars[i]), OperandMode.ALIVE, JumpOp.outgoingFlags);
583 }
584 livenessInfo.setOutLocations(block, locs);
585 }
586
587 private void spillCallerSavedRegisters() {
588 for (Register reg : callerSaveRegs) {
589 if (attributes(reg).isAllocatable()) {
590 evacuateRegisterAndSpill(reg);
591 assert checkRegisterUsage(reg);
592 setLastRegisterUsage(reg, currentOpId);
593 }
594 }
595 if (Debug.isLogEnabled()) {
596 Debug.log("operation destroys all caller-save registers");
597 }
598 }
599
600 private final InstructionValueProcedure allocFixedRegisterProcedure = new InstructionValueProcedure() {
601 @Override
602 public Value doValue(LIRInstruction instruction, Value value, OperandMode mode, EnumSet<OperandFlag> flags) {
603 return allocFixedRegister(value);
604 }
605 };
606 private final InstructionValueProcedure allocRegisterProcedure = new InstructionValueProcedure() {
607 @Override
608 public Value doValue(LIRInstruction instruction, Value value, OperandMode mode, EnumSet<OperandFlag> flags) {
609 return allocRegister(instruction, value, mode, flags);
610 }
611 };
612 private final InstructionValueProcedure allocStackOrRegisterProcedure = new InstructionValueProcedure() {
613 @Override
614 public Value doValue(LIRInstruction instruction, Value value, OperandMode mode, EnumSet<OperandFlag> flags) {
615 return allocStackOrRegister(instruction, value, mode, flags);
616 }
617 };
618
619 private Value allocFixedRegister(Value value) {
620 if (isRegister(value)) {
621 Register reg = asRegister(value);
622 assert checkRegisterUsage(reg);
623 evacuateRegisterAndSpill(reg);
624 setRegisterUsage(reg, asAllocatableValue(value));
625 }
626 return value;
627 }
628
629 private Value allocRegister(LIRInstruction instruction, Value value, OperandMode mode, EnumSet<OperandFlag> flags) {
630 if (isVariable(value) && requiresRegisters(instruction, value, mode, flags)) {
631 Variable var = asVariable(value);
632 // check if available
633 AllocatableValue currentLocation = getCurrentLocation(var);
634 if (currentLocation == null) {
635 // nothing yet assigned
636 return allocRegister(var, mode);
637 }
638 // already a location assigned
639 if (isRegister(currentLocation)) {
640 // register assigned -> nothing todo
641 setLastRegisterUsage(asRegister(currentLocation), currentOpId);
642 return currentLocation;
643 }
644 assert isStackSlotValue(currentLocation);
645 // stackSlot assigned but need register -> spill
646 Value allocatedRegister = allocRegister(var, mode);
647 if (mode == OperandMode.USE) {
648 // input might be destroyed at the def position
649 // but it must be available before the instruction
650 insertSpillMoveBefore(currentLocation, allocatedRegister);
651 } else {
652 insertSpillMoveAfter(currentLocation, allocatedRegister);
653 }
654 return allocatedRegister;
655 }
656 return value;
657 }
658
659 private Value allocRegister(Variable var, OperandMode mode) {
660 PlatformKind platformKind = var.getPlatformKind();
661 Register freeRegister = findFreeRegister(platformKind, mode);
662 if (freeRegister == null) {
663 // no free register found, looking for a blocked one
664 freeRegister = findLockedRegister(platformKind, mode);
665 if (freeRegister == null) {
666 throw new OutOfRegistersException("TraceRA[BottomUp]: no register found");
667 }
668 }
669 // found a register
670 setRegisterUsage(freeRegister, var);
671 RegisterValue registerValue = freeRegister.asValue(var.getValueKind());
672 setCurrentLocation(var, registerValue);
673 Debug.log("AllocateRegister[%5s] %s for %s", mode, freeRegister, var);
674 return registerValue;
675 }
676
677 private Value allocStackOrRegister(LIRInstruction instruction, Value value, OperandMode mode, EnumSet<OperandFlag> flags) {
678 if (isRegister(value)) {
679 if ((mode == OperandMode.DEF || mode == OperandMode.TEMP) && !(instruction instanceof LabelOp)) {
680 freeRegister(asRegister(value));
681 }
682 return value;
683 }
684 if (isVariable(value)) {
685 assert !requiresRegisters(instruction, value, mode, flags) : "Should have a register already: " + value;
686 Variable var = asVariable(value);
687 // check if available
688 AllocatableValue currentLocation = getCurrentLocation(var);
689 if (currentLocation != null) {
690 // already a location assigned -> nothing todo
691 if (isRegister(currentLocation)) {
692 Register reg = asRegister(currentLocation);
693 if (mode == OperandMode.ALIVE && killedAtDef(reg)) {
694 AllocatableValue spillSlot = allocateSpillSlot(var);
695 insertSpillMoveBefore(spillSlot, currentLocation);
696 Debug.log("AllocateStackOrReg[%5s] temporary use %s for %s since current location %s is destroyed at def", mode, spillSlot, var, currentLocation);
697 return spillSlot;
698 }
699 // update register usage
700 setLastRegisterUsage(reg, currentOpId);
701 }
702 Debug.log(3, "AllocateStackOrReg[%5s] %s already in %s", mode, var, currentLocation);
703 return currentLocation;
704 }
705 // no location available
706 PlatformKind platformKind = var.getPlatformKind();
707 Register freeRegister = findFreeRegister(platformKind, mode);
708 if (freeRegister == null) {
709 // no free register available -> either spill current or free a register
710 AllocatableValue spillSlot = allocateSpillSlot(var);
711 setCurrentLocation(var, spillSlot);
712 return spillSlot;
713 }
714 assert freeRegister != null;
715 // found a register
716 setRegisterUsage(freeRegister, var);
717 RegisterValue registerValue = freeRegister.asValue(var.getValueKind());
718 setCurrentLocation(var, registerValue);
719 Debug.log("AllocateStackOrReg[%5s] %s for %s", mode, freeRegister, var);
720 return registerValue;
721 }
722 return value;
723 }
724
725 private boolean killedAtDef(Register reg) {
726 return getLastRegisterKill(reg) == currentOpId - 1;
727 }
728
729 /**
730 * Searches for a free register.
731 */
732 @SuppressWarnings("try")
733 private Register findFreeRegister(PlatformKind kind, OperandMode mode) {
734 AllocatableRegisters allocatableRegisters = registerAllocationConfig.getAllocatableRegisters(kind);
735 Register[] availableRegs = allocatableRegisters.allocatableRegisters;
736 for (Register reg : availableRegs) {
737 AllocatableValue currentVal = getCurrentValue(reg);
738 if (currentVal == null && !isCurrentlyUsed(reg, mode)) {
739 return reg;
740 }
741 }
742 if (Debug.isLogEnabled()) {
743 try (Indent i = Debug.logAndIndent("All Registers occupied:")) {
744 for (Register reg : availableRegs) {
745 Debug.log("%6s: last used %4d %s", reg, getLastRegisterUsage(reg), getCurrentValue(reg));
746 }
747 }
748 }
749 return null;
750 }
751
752 /**
753 * Searches for a occupied register to spill.
754 */
755 @SuppressWarnings("try")
756 private Register findLockedRegister(PlatformKind kind, OperandMode mode) {
757 AllocatableRegisters allocatableRegisters = registerAllocationConfig.getAllocatableRegisters(kind);
758 Register[] availableRegs = allocatableRegisters.allocatableRegisters;
759 // TODO (je): better strategies for spilling
760 // TODO (je): we need to ensure that we do not use the register in the current
761 // instruction!
762 Register lockedReg = null;
763 for (Register reg : availableRegs) {
764 if (!isCurrentlyUsed(reg, mode) && !isActiveFixedRegister(reg)) {
765 lockedReg = reg;
766 break;
767 }
768 }
769 if (lockedReg == null) {
770 return null;
771 }
772 evacuateRegisterAndSpill(lockedReg);
773 return lockedReg;
774 }
775
776 private boolean isActiveFixedRegister(Register reg) {
777 return isRegister(getCurrentValue(reg));
778 }
779
780 private boolean isCurrentlyUsed(Register reg, OperandMode mode) {
781 int lastRegUsage = getLastRegisterUsage(reg);
782 if (lastRegUsage == currentOpId) {
783 return true;
784 }
785 return mode == OperandMode.ALIVE && lastRegUsage == (currentOpId & ~1);
786 }
787
788 private void freeRegister(Register reg) {
789 AllocatableValue val = getCurrentValue(reg);
790 setCurrentValue(reg, null);
791 setLastRegisterKill(reg, currentOpId);
792 if (val != null && isVariable(val)) {
793 Variable var = asVariable(val);
794 setCurrentLocation(var, null);
795 Debug.log("Free Registers %s (was %s)", reg, var);
796 } else {
797 Debug.log("Free Registers %s", reg);
798 }
799 }
800
801 private void setRegisterUsage(Register reg, AllocatableValue currentValue) {
802 assert checkRegisterUsage(reg);
803 setCurrentValue(reg, currentValue);
804 setLastRegisterUsage(reg, currentOpId);
805 }
806
807 private boolean checkRegisterUsage(Register reg) {
808 AllocatableValue currentValue = getCurrentValue(reg);
809 assert getLastRegisterUsage(reg) < currentOpId || currentValue == null || isRegister(currentValue) && asRegister(currentValue).equals(reg) : String.format("Register %s is occupied", reg);
810 return true;
811 }
812
813 /**
814 * Frees a registers and spill the variable that is currently occupying it.
815 *
816 * @return The value that currently occupies the register or {@code null} if there is none.
817 */
818 private AllocatableValue evacuateRegisterAndSpill(Register reg) {
819 AllocatableValue val = evacuateRegister(reg);
820 spillVariable(val, reg);
821 return val;
822 }
823
824 /**
825 * Frees a registers. The variable that is currently occupying it is <em>not</em> spilled.
826 *
827 * @return The value that currently occupies the register or {@code null} if there is none.
828 */
829 private AllocatableValue evacuateRegister(Register reg) {
830 AllocatableValue val = getCurrentValue(reg);
831 if (val == null) {
832 return null;
833 }
834 setCurrentValue(reg, null);
835 return val;
836 }
837
838 private void spillVariable(AllocatableValue val, Register reg) {
839 if (val != null && isVariable(val)) {
840 Variable var = asVariable(val);
841 Debug.log("Spill Variable %s from %s", var, reg);
842 // insert reload
843 AllocatableValue spillSlot = allocateSpillSlot(var);
844 setCurrentLocation(var, spillSlot);
845 insertSpillMoveAfter(reg.asValue(var.getValueKind()), spillSlot);
846 }
847 }
848 }
849 }