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