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 }