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