1 /* 2 * Copyright (c) 2009, 2015, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. 8 * 9 * This code is distributed in the hope that it will be useful, but WITHOUT 10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 12 * version 2 for more details (a copy is included in the LICENSE file that 13 * accompanied this code). 14 * 15 * You should have received a copy of the GNU General Public License version 16 * 2 along with this work; if not, write to the Free Software Foundation, 17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 18 * 19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 20 * or visit www.oracle.com if you need additional information or have any 21 * questions. 22 */ 23 24 25 package org.graalvm.compiler.lir.alloc.trace; 26 27 import static jdk.vm.ci.code.ValueUtil.asAllocatableValue; 28 import static jdk.vm.ci.code.ValueUtil.asRegister; 29 import static jdk.vm.ci.code.ValueUtil.asStackSlot; 30 import static jdk.vm.ci.code.ValueUtil.isIllegal; 31 import static jdk.vm.ci.code.ValueUtil.isRegister; 32 import static jdk.vm.ci.code.ValueUtil.isStackSlot; 33 import static org.graalvm.compiler.lir.LIRValueUtil.asVirtualStackSlot; 34 import static org.graalvm.compiler.lir.LIRValueUtil.isStackSlotValue; 35 import static org.graalvm.compiler.lir.LIRValueUtil.isVirtualStackSlot; 36 import static org.graalvm.compiler.lir.alloc.trace.TraceUtil.asShadowedRegisterValue; 37 import static org.graalvm.compiler.lir.alloc.trace.TraceUtil.isShadowedRegisterValue; 38 39 import java.util.ArrayList; 40 import java.util.Arrays; 41 import java.util.HashSet; 42 43 import org.graalvm.compiler.core.common.LIRKind; 44 import org.graalvm.compiler.core.common.alloc.RegisterAllocationConfig; 45 import org.graalvm.compiler.debug.CounterKey; 46 import org.graalvm.compiler.debug.DebugContext; 47 import org.graalvm.compiler.debug.GraalError; 48 import org.graalvm.compiler.debug.Indent; 49 import org.graalvm.compiler.lir.LIR; 50 import org.graalvm.compiler.lir.LIRInsertionBuffer; 51 import org.graalvm.compiler.lir.LIRInstruction; 52 import org.graalvm.compiler.lir.VirtualStackSlot; 53 import org.graalvm.compiler.lir.framemap.FrameMap; 54 import org.graalvm.compiler.lir.framemap.FrameMapBuilder; 55 import org.graalvm.compiler.lir.framemap.FrameMapBuilderTool; 56 import org.graalvm.compiler.lir.gen.LIRGenerationResult; 57 import org.graalvm.compiler.lir.gen.LIRGeneratorTool.MoveFactory; 58 import org.graalvm.compiler.options.OptionValues; 59 60 import jdk.vm.ci.code.Architecture; 61 import jdk.vm.ci.code.RegisterArray; 62 import jdk.vm.ci.code.StackSlot; 63 import jdk.vm.ci.meta.AllocatableValue; 64 import jdk.vm.ci.meta.Value; 65 66 /** 67 */ 68 public final class TraceGlobalMoveResolver extends TraceGlobalMoveResolutionPhase.MoveResolver { 69 70 private static final CounterKey cycleBreakingSlotsAllocated = DebugContext.counter("TraceRA[cycleBreakingSlotsAllocated(global)]"); 71 private static final CounterKey cycleBreakingSlotsReused = DebugContext.counter("TraceRA[cycleBreakingSlotsReused(global)]"); 72 73 private int insertIdx; 74 private LIRInsertionBuffer insertionBuffer; // buffer where moves are inserted 75 76 private final ArrayList<Value> mappingFrom; 77 private final ArrayList<Value> mappingFromStack; 78 private final ArrayList<AllocatableValue> mappingTo; 79 private final int[] registerBlocked; 80 private static final int STACK_SLOT_IN_CALLER_FRAME_IDX = -1; 81 private int[] stackBlocked; 82 private final int firstVirtualStackIndex; 83 private final MoveFactory spillMoveFactory; 84 private final FrameMapBuilder frameMapBuilder; 85 private final OptionValues options; 86 private final RegisterAllocationConfig registerAllocationConfig; 87 private final LIRGenerationResult res; 88 private final DebugContext debug; 89 setValueBlocked(Value location, int direction)90 private void setValueBlocked(Value location, int direction) { 91 assert direction == 1 || direction == -1 : "out of bounds"; 92 if (isStackSlotValue(location)) { 93 int stackIdx = getStackArrayIndex(location); 94 if (stackIdx == STACK_SLOT_IN_CALLER_FRAME_IDX) { 95 // incoming stack arguments can be ignored 96 return; 97 } 98 if (stackIdx >= stackBlocked.length) { 99 stackBlocked = Arrays.copyOf(stackBlocked, stackIdx + 1); 100 } 101 stackBlocked[stackIdx] += direction; 102 } else { 103 assert direction == 1 || direction == -1 : "out of bounds"; 104 if (isRegister(location)) { 105 registerBlocked[asRegister(location).number] += direction; 106 } else { 107 throw GraalError.shouldNotReachHere("unhandled value " + location); 108 } 109 } 110 } 111 valueBlocked(Value location)112 private int valueBlocked(Value location) { 113 if (isStackSlotValue(location)) { 114 int stackIdx = getStackArrayIndex(location); 115 if (stackIdx == STACK_SLOT_IN_CALLER_FRAME_IDX) { 116 // incoming stack arguments are always blocked (aka they can not be written) 117 return 1; 118 } 119 if (stackIdx >= stackBlocked.length) { 120 return 0; 121 } 122 return stackBlocked[stackIdx]; 123 } 124 if (isRegister(location)) { 125 return registerBlocked[asRegister(location).number]; 126 } 127 throw GraalError.shouldNotReachHere("unhandled value " + location); 128 } 129 areMultipleReadsAllowed()130 private static boolean areMultipleReadsAllowed() { 131 return true; 132 } 133 hasMappings()134 private boolean hasMappings() { 135 return mappingFrom.size() > 0; 136 } 137 getSpillMoveFactory()138 private MoveFactory getSpillMoveFactory() { 139 return spillMoveFactory; 140 } 141 getRegisters()142 private RegisterArray getRegisters() { 143 return frameMapBuilder.getRegisterConfig().getAllocatableRegisters(); 144 } 145 TraceGlobalMoveResolver(LIRGenerationResult res, MoveFactory spillMoveFactory, RegisterAllocationConfig registerAllocationConfig, Architecture arch)146 public TraceGlobalMoveResolver(LIRGenerationResult res, MoveFactory spillMoveFactory, RegisterAllocationConfig registerAllocationConfig, Architecture arch) { 147 148 this.mappingFrom = new ArrayList<>(8); 149 this.mappingFromStack = new ArrayList<>(8); 150 this.mappingTo = new ArrayList<>(8); 151 this.insertIdx = -1; 152 this.insertionBuffer = new LIRInsertionBuffer(); 153 154 this.frameMapBuilder = res.getFrameMapBuilder(); 155 this.spillMoveFactory = spillMoveFactory; 156 this.registerBlocked = new int[arch.getRegisters().size()]; 157 this.registerAllocationConfig = registerAllocationConfig; 158 159 FrameMapBuilderTool frameMapBuilderTool = (FrameMapBuilderTool) frameMapBuilder; 160 this.stackBlocked = new int[frameMapBuilderTool.getNumberOfStackSlots()]; 161 162 FrameMap frameMap = frameMapBuilderTool.getFrameMap(); 163 this.firstVirtualStackIndex = !frameMap.frameNeedsAllocating() ? 0 : frameMap.currentFrameSize() + 1; 164 this.res = res; 165 LIR lir = res.getLIR(); 166 this.options = lir.getOptions(); 167 this.debug = lir.getDebug(); 168 } 169 checkEmpty()170 private boolean checkEmpty() { 171 for (int i = 0; i < stackBlocked.length; i++) { 172 assert stackBlocked[i] == 0 : "stack map must be empty before and after processing"; 173 } 174 assert mappingFrom.size() == 0 && mappingTo.size() == 0 && mappingFromStack.size() == 0 : "list must be empty before and after processing"; 175 for (int i = 0; i < getRegisters().size(); i++) { 176 assert registerBlocked[i] == 0 : "register map must be empty before and after processing"; 177 } 178 return true; 179 } 180 verifyBeforeResolve()181 private boolean verifyBeforeResolve() { 182 assert mappingFrom.size() == mappingTo.size() && mappingFrom.size() == mappingFromStack.size() : "length must be equal"; 183 assert insertIdx != -1 : "insert position not set"; 184 185 int i; 186 int j; 187 if (!areMultipleReadsAllowed()) { 188 for (i = 0; i < mappingFrom.size(); i++) { 189 for (j = i + 1; j < mappingFrom.size(); j++) { 190 assert mappingFrom.get(i) == null || mappingFrom.get(i) != mappingFrom.get(j) : "cannot read from same interval twice"; 191 } 192 } 193 } 194 195 for (i = 0; i < mappingTo.size(); i++) { 196 for (j = i + 1; j < mappingTo.size(); j++) { 197 assert mappingTo.get(i) != mappingTo.get(j) : "cannot write to same interval twice"; 198 } 199 } 200 201 for (i = 0; i < mappingTo.size(); i++) { 202 Value to = mappingTo.get(i); 203 assert !isStackSlotValue(to) || getStackArrayIndex(to) != STACK_SLOT_IN_CALLER_FRAME_IDX : "Cannot move to in argument: " + to; 204 } 205 206 HashSet<Value> usedRegs = new HashSet<>(); 207 if (!areMultipleReadsAllowed()) { 208 for (i = 0; i < mappingFrom.size(); i++) { 209 Value from = mappingFrom.get(i); 210 if (from != null && !isIllegal(from)) { 211 boolean unique = usedRegs.add(from); 212 assert unique : "cannot read from same register twice"; 213 } 214 } 215 } 216 217 usedRegs.clear(); 218 for (i = 0; i < mappingTo.size(); i++) { 219 Value to = mappingTo.get(i); 220 if (isIllegal(to)) { 221 // After insertion the location may become illegal, so don't check it since multiple 222 // intervals might be illegal. 223 continue; 224 } 225 boolean unique = usedRegs.add(to); 226 assert unique : "cannot write to same register twice"; 227 } 228 229 return true; 230 } 231 232 // mark assignedReg and assignedRegHi of the interval as blocked block(Value location)233 private void block(Value location) { 234 if (mightBeBlocked(location)) { 235 assert areMultipleReadsAllowed() || valueBlocked(location) == 0 : "location already marked as used: " + location; 236 setValueBlocked(location, 1); 237 debug.log("block %s", location); 238 } 239 } 240 241 // mark assignedReg and assignedRegHi of the interval as unblocked unblock(Value location)242 private void unblock(Value location) { 243 if (mightBeBlocked(location)) { 244 assert valueBlocked(location) > 0 : "location already marked as unused: " + location; 245 setValueBlocked(location, -1); 246 debug.log("unblock %s", location); 247 } 248 } 249 250 /** 251 * Checks if {@code to} is not blocked or is only blocked by {@code from}. 252 */ safeToProcessMove(Value fromLocation, Value toLocation)253 private boolean safeToProcessMove(Value fromLocation, Value toLocation) { 254 if (mightBeBlocked(toLocation)) { 255 if ((valueBlocked(toLocation) > 1 || (valueBlocked(toLocation) == 1 && !isMoveToSelf(fromLocation, toLocation)))) { 256 return false; 257 } 258 } 259 260 return true; 261 } 262 isMoveToSelf(Value from, Value to)263 public static boolean isMoveToSelf(Value from, Value to) { 264 assert to != null; 265 if (to.equals(from)) { 266 return true; 267 } 268 if (from == null) { 269 return false; 270 } 271 if (isShadowedRegisterValue(from)) { 272 /* From is a shadowed register. */ 273 if (isShadowedRegisterValue(to)) { 274 // both shadowed but not equal 275 return false; 276 } 277 ShadowedRegisterValue shadowed = asShadowedRegisterValue(from); 278 if (isRegisterToRegisterMoveToSelf(shadowed.getRegister(), to)) { 279 return true; 280 } 281 if (isStackSlotValue(to)) { 282 return to.equals(shadowed.getStackSlot()); 283 } 284 } else { 285 /* 286 * A shadowed destination value is never a self move it both values are not equal. Fall 287 * through. 288 */ 289 // if (isShadowedRegisterValue(to)) return false; 290 291 return isRegisterToRegisterMoveToSelf(from, to); 292 } 293 return false; 294 } 295 isRegisterToRegisterMoveToSelf(Value from, Value to)296 private static boolean isRegisterToRegisterMoveToSelf(Value from, Value to) { 297 if (to.equals(from)) { 298 return true; 299 } 300 if (isRegister(from) && isRegister(to) && asRegister(from).equals(asRegister(to))) { 301 // Values differ but Registers are the same 302 return true; 303 } 304 return false; 305 } 306 mightBeBlocked(Value location)307 private static boolean mightBeBlocked(Value location) { 308 return isRegister(location) || isStackSlotValue(location); 309 } 310 createInsertionBuffer(ArrayList<LIRInstruction> list)311 private void createInsertionBuffer(ArrayList<LIRInstruction> list) { 312 assert !insertionBuffer.initialized() : "overwriting existing buffer"; 313 insertionBuffer.init(list); 314 } 315 appendInsertionBuffer()316 private void appendInsertionBuffer() { 317 if (insertionBuffer.initialized()) { 318 insertionBuffer.finish(); 319 } 320 assert !insertionBuffer.initialized() : "must be uninitialized now"; 321 322 insertIdx = -1; 323 } 324 insertMove(Value fromOperand, AllocatableValue toOperand)325 private LIRInstruction insertMove(Value fromOperand, AllocatableValue toOperand) { 326 assert !fromOperand.equals(toOperand) : "from and to are equal: " + fromOperand + " vs. " + toOperand; 327 assert LIRKind.verifyMoveKinds(fromOperand.getValueKind(), fromOperand.getValueKind(), registerAllocationConfig) : "move between different types"; 328 assert insertIdx != -1 : "must setup insert position first"; 329 330 LIRInstruction move = createMove(fromOperand, toOperand); 331 insertionBuffer.append(insertIdx, move); 332 333 if (debug.isLogEnabled()) { 334 debug.log("insert move from %s to %s at %d", fromOperand, toOperand, insertIdx); 335 } 336 return move; 337 } 338 339 /** 340 * @param fromOpr Operand of the {@code from} interval 341 * @param toOpr Operand of the {@code to} interval 342 */ createMove(Value fromOpr, AllocatableValue toOpr)343 private LIRInstruction createMove(Value fromOpr, AllocatableValue toOpr) { 344 if (isStackSlotValue(toOpr) && isStackSlotValue(fromOpr)) { 345 return getSpillMoveFactory().createStackMove(toOpr, asAllocatableValue(fromOpr)); 346 } 347 return getSpillMoveFactory().createMove(toOpr, fromOpr); 348 } 349 350 @SuppressWarnings("try") resolveMappings()351 private void resolveMappings() { 352 try (Indent indent = debug.logAndIndent("resolveMapping")) { 353 assert verifyBeforeResolve(); 354 if (debug.isLogEnabled()) { 355 printMapping(); 356 } 357 358 // Block all registers that are used as input operands of a move. 359 // When a register is blocked, no move to this register is emitted. 360 // This is necessary for detecting cycles in moves. 361 for (int i = mappingFrom.size() - 1; i >= 0; i--) { 362 Value from = mappingFrom.get(i); 363 block(from); 364 } 365 366 ArrayList<AllocatableValue> busySpillSlots = null; 367 while (mappingFrom.size() > 0) { 368 boolean processedInterval = false; 369 370 int spillCandidate = -1; 371 for (int i = mappingFrom.size() - 1; i >= 0; i--) { 372 Value fromLocation = mappingFrom.get(i); 373 AllocatableValue toLocation = mappingTo.get(i); 374 if (safeToProcessMove(fromLocation, toLocation)) { 375 // this interval can be processed because target is free 376 LIRInstruction move = insertMove(fromLocation, toLocation); 377 move.setComment(res, "TraceGlobalMoveResolver: resolveMapping"); 378 unblock(fromLocation); 379 if (isStackSlotValue(toLocation)) { 380 if (busySpillSlots == null) { 381 busySpillSlots = new ArrayList<>(2); 382 } 383 busySpillSlots.add(toLocation); 384 } 385 mappingFrom.remove(i); 386 mappingFromStack.remove(i); 387 mappingTo.remove(i); 388 389 processedInterval = true; 390 } else if (fromLocation != null) { 391 if (isRegister(fromLocation) && (busySpillSlots == null || !busySpillSlots.contains(mappingFromStack.get(i)))) { 392 // this interval cannot be processed now because target is not free 393 // it starts in a register, so it is a possible candidate for spilling 394 spillCandidate = i; 395 } else if (isStackSlotValue(fromLocation) && spillCandidate == -1) { 396 // fall back to spill a stack slot in case no other candidate is found 397 spillCandidate = i; 398 } 399 } 400 } 401 402 if (!processedInterval) { 403 breakCycle(spillCandidate); 404 } 405 } 406 } 407 408 // check that all intervals have been processed 409 assert checkEmpty(); 410 } 411 412 @SuppressWarnings("try") breakCycle(int spillCandidate)413 private void breakCycle(int spillCandidate) { 414 // no move could be processed because there is a cycle in the move list 415 // (e.g. r1 . r2, r2 . r1), so one interval must be spilled to memory 416 assert spillCandidate != -1 : "no interval in register for spilling found"; 417 418 // create a new spill interval and assign a stack slot to it 419 Value from = mappingFrom.get(spillCandidate); 420 try (Indent indent = debug.logAndIndent("BreakCycle: %s", from)) { 421 AllocatableValue spillSlot = null; 422 if (TraceRegisterAllocationPhase.Options.TraceRAreuseStackSlotsForMoveResolutionCycleBreaking.getValue(options) && !isStackSlotValue(from)) { 423 // don't use the stack slot if from is already the stack slot 424 Value fromStack = mappingFromStack.get(spillCandidate); 425 if (fromStack != null) { 426 spillSlot = (AllocatableValue) fromStack; 427 cycleBreakingSlotsReused.increment(debug); 428 debug.log("reuse slot for spilling: %s", spillSlot); 429 } 430 } 431 if (spillSlot == null) { 432 spillSlot = frameMapBuilder.allocateSpillSlot(from.getValueKind()); 433 cycleBreakingSlotsAllocated.increment(debug); 434 debug.log("created new slot for spilling: %s", spillSlot); 435 // insert a move from register to stack and update the mapping 436 LIRInstruction move = insertMove(from, spillSlot); 437 move.setComment(res, "TraceGlobalMoveResolver: breakCycle"); 438 } 439 block(spillSlot); 440 mappingFrom.set(spillCandidate, spillSlot); 441 unblock(from); 442 } 443 } 444 445 @SuppressWarnings("try") printMapping()446 private void printMapping() { 447 try (Indent indent = debug.logAndIndent("Mapping")) { 448 for (int i = mappingFrom.size() - 1; i >= 0; i--) { 449 debug.log("move %s <- %s (%s)", mappingTo.get(i), mappingFrom.get(i), mappingFromStack.get(i)); 450 } 451 } 452 } 453 setInsertPosition(ArrayList<LIRInstruction> insertList, int insertIdx)454 public void setInsertPosition(ArrayList<LIRInstruction> insertList, int insertIdx) { 455 assert this.insertIdx == -1 : "use moveInsertPosition instead of setInsertPosition when data already set"; 456 457 createInsertionBuffer(insertList); 458 this.insertIdx = insertIdx; 459 } 460 461 @Override addMapping(Value from, AllocatableValue to, Value fromStack)462 public void addMapping(Value from, AllocatableValue to, Value fromStack) { 463 if (debug.isLogEnabled()) { 464 debug.log("add move mapping from %s to %s", from, to); 465 } 466 467 assert !from.equals(to) : "from and to interval equal: " + from; 468 assert LIRKind.verifyMoveKinds(to.getValueKind(), from.getValueKind(), registerAllocationConfig) : String.format("Kind mismatch: %s vs. %s, from=%s, to=%s", from.getValueKind(), 469 to.getValueKind(), from, to); 470 assert fromStack == null || LIRKind.verifyMoveKinds(to.getValueKind(), fromStack.getValueKind(), registerAllocationConfig) : String.format("Kind mismatch: %s vs. %s, fromStack=%s, to=%s", 471 fromStack.getValueKind(), 472 to.getValueKind(), fromStack, to); 473 mappingFrom.add(from); 474 mappingFromStack.add(fromStack); 475 mappingTo.add(to); 476 } 477 resolveAndAppendMoves()478 public void resolveAndAppendMoves() { 479 if (hasMappings()) { 480 resolveMappings(); 481 } 482 appendInsertionBuffer(); 483 } 484 getStackArrayIndex(Value stackSlotValue)485 private int getStackArrayIndex(Value stackSlotValue) { 486 if (isStackSlot(stackSlotValue)) { 487 return getStackArrayIndex(asStackSlot(stackSlotValue)); 488 } 489 if (isVirtualStackSlot(stackSlotValue)) { 490 return getStackArrayIndex(asVirtualStackSlot(stackSlotValue)); 491 } 492 throw GraalError.shouldNotReachHere("value is not a stack slot: " + stackSlotValue); 493 } 494 getStackArrayIndex(StackSlot stackSlot)495 private int getStackArrayIndex(StackSlot stackSlot) { 496 int stackIdx; 497 if (stackSlot.isInCallerFrame()) { 498 // incoming stack arguments can be ignored 499 stackIdx = STACK_SLOT_IN_CALLER_FRAME_IDX; 500 } else { 501 assert stackSlot.getRawAddFrameSize() : "Unexpected stack slot: " + stackSlot; 502 int offset = -stackSlot.getRawOffset(); 503 assert 0 <= offset && offset < firstVirtualStackIndex : String.format("Wrong stack slot offset: %d (first virtual stack slot index: %d", offset, firstVirtualStackIndex); 504 stackIdx = offset; 505 } 506 return stackIdx; 507 } 508 509 private int getStackArrayIndex(VirtualStackSlot virtualStackSlot) { 510 return firstVirtualStackIndex + virtualStackSlot.getId(); 511 } 512 513 } 514