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