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