TraceLocalMoveResolver.java revision 13264:48566d838608
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 */ 23package org.graalvm.compiler.lir.alloc.trace.lsra; 24 25import static jdk.vm.ci.code.ValueUtil.asRegister; 26import static jdk.vm.ci.code.ValueUtil.asStackSlot; 27import static jdk.vm.ci.code.ValueUtil.isIllegal; 28import static jdk.vm.ci.code.ValueUtil.isRegister; 29import static jdk.vm.ci.code.ValueUtil.isStackSlot; 30import static org.graalvm.compiler.lir.LIRValueUtil.asVirtualStackSlot; 31import static org.graalvm.compiler.lir.LIRValueUtil.isStackSlotValue; 32import static org.graalvm.compiler.lir.LIRValueUtil.isVirtualStackSlot; 33 34import java.util.ArrayList; 35import java.util.Arrays; 36import java.util.HashSet; 37import java.util.List; 38 39import org.graalvm.compiler.core.common.LIRKind; 40import org.graalvm.compiler.debug.CounterKey; 41import org.graalvm.compiler.debug.DebugContext; 42import org.graalvm.compiler.debug.GraalError; 43import org.graalvm.compiler.debug.Indent; 44import org.graalvm.compiler.lir.LIRInsertionBuffer; 45import org.graalvm.compiler.lir.LIRInstruction; 46import org.graalvm.compiler.lir.VirtualStackSlot; 47import org.graalvm.compiler.lir.alloc.trace.lsra.TraceLinearScanPhase.TraceLinearScan; 48import org.graalvm.compiler.lir.framemap.FrameMap; 49import org.graalvm.compiler.lir.framemap.FrameMapBuilderTool; 50 51import jdk.vm.ci.code.StackSlot; 52import jdk.vm.ci.meta.AllocatableValue; 53import jdk.vm.ci.meta.Constant; 54import jdk.vm.ci.meta.JavaConstant; 55import jdk.vm.ci.meta.Value; 56 57final class TraceLocalMoveResolver { 58 59 private static final CounterKey cycleBreakingSlotsAllocated = DebugContext.counter("TraceRA[cycleBreakingSlotsAllocated(local)]"); 60 61 private static final int STACK_SLOT_IN_CALLER_FRAME_IDX = -1; 62 private final TraceLinearScan allocator; 63 64 private int insertIdx; 65 private LIRInsertionBuffer insertionBuffer; // buffer where moves are inserted 66 67 private final ArrayList<TraceInterval> mappingFrom; 68 private final ArrayList<Constant> mappingFromOpr; 69 private final ArrayList<TraceInterval> mappingTo; 70 private final int[] registerBlocked; 71 72 private int[] stackBlocked; 73 private final int firstVirtualStackIndex; 74 75 private final DebugContext debug; 76 77 private int getStackArrayIndex(Value stackSlotValue) { 78 if (isStackSlot(stackSlotValue)) { 79 return getStackArrayIndex(asStackSlot(stackSlotValue)); 80 } 81 if (isVirtualStackSlot(stackSlotValue)) { 82 return getStackArrayIndex(asVirtualStackSlot(stackSlotValue)); 83 } 84 throw GraalError.shouldNotReachHere("value is not a stack slot: " + stackSlotValue); 85 } 86 87 private int getStackArrayIndex(StackSlot stackSlot) { 88 int stackIdx; 89 if (stackSlot.isInCallerFrame()) { 90 // incoming stack arguments can be ignored 91 stackIdx = STACK_SLOT_IN_CALLER_FRAME_IDX; 92 } else { 93 assert stackSlot.getRawAddFrameSize() : "Unexpected stack slot: " + stackSlot; 94 int offset = -stackSlot.getRawOffset(); 95 assert 0 <= offset && offset < firstVirtualStackIndex : String.format("Wrong stack slot offset: %d (first virtual stack slot index: %d", offset, firstVirtualStackIndex); 96 stackIdx = offset; 97 } 98 return stackIdx; 99 } 100 101 private int getStackArrayIndex(VirtualStackSlot virtualStackSlot) { 102 return firstVirtualStackIndex + virtualStackSlot.getId(); 103 } 104 105 protected void setValueBlocked(Value location, int direction) { 106 assert direction == 1 || direction == -1 : "out of bounds"; 107 if (isStackSlotValue(location)) { 108 int stackIdx = getStackArrayIndex(location); 109 if (stackIdx == STACK_SLOT_IN_CALLER_FRAME_IDX) { 110 // incoming stack arguments can be ignored 111 return; 112 } 113 if (stackIdx >= stackBlocked.length) { 114 stackBlocked = Arrays.copyOf(stackBlocked, stackIdx + 1); 115 } 116 stackBlocked[stackIdx] += direction; 117 } else { 118 assert direction == 1 || direction == -1 : "out of bounds"; 119 if (isRegister(location)) { 120 registerBlocked[asRegister(location).number] += direction; 121 } else { 122 throw GraalError.shouldNotReachHere("unhandled value " + location); 123 } 124 } 125 } 126 127 protected TraceInterval getMappingFrom(int i) { 128 return mappingFrom.get(i); 129 } 130 131 protected int mappingFromSize() { 132 return mappingFrom.size(); 133 } 134 135 protected int valueBlocked(Value location) { 136 if (isStackSlotValue(location)) { 137 int stackIdx = getStackArrayIndex(location); 138 if (stackIdx == STACK_SLOT_IN_CALLER_FRAME_IDX) { 139 // incoming stack arguments are always blocked (aka they can not be written) 140 return 1; 141 } 142 if (stackIdx >= stackBlocked.length) { 143 return 0; 144 } 145 return stackBlocked[stackIdx]; 146 } 147 if (isRegister(location)) { 148 return registerBlocked[asRegister(location).number]; 149 } 150 throw GraalError.shouldNotReachHere("unhandled value " + location); 151 } 152 153 /* 154 * TODO (je) remove? 155 */ 156 protected static boolean areMultipleReadsAllowed() { 157 return true; 158 } 159 160 boolean hasMappings() { 161 return mappingFrom.size() > 0; 162 } 163 164 protected TraceLinearScan getAllocator() { 165 return allocator; 166 } 167 168 protected TraceLocalMoveResolver(TraceLinearScan allocator) { 169 170 this.allocator = allocator; 171 this.debug = allocator.getDebug(); 172 this.mappingFrom = new ArrayList<>(8); 173 this.mappingFromOpr = new ArrayList<>(8); 174 this.mappingTo = new ArrayList<>(8); 175 this.insertIdx = -1; 176 this.insertionBuffer = new LIRInsertionBuffer(); 177 this.registerBlocked = new int[allocator.getRegisters().size()]; 178 FrameMapBuilderTool frameMapBuilderTool = (FrameMapBuilderTool) allocator.getFrameMapBuilder(); 179 FrameMap frameMap = frameMapBuilderTool.getFrameMap(); 180 this.stackBlocked = new int[frameMapBuilderTool.getNumberOfStackSlots()]; 181 this.firstVirtualStackIndex = !frameMap.frameNeedsAllocating() ? 0 : frameMap.currentFrameSize() + 1; 182 } 183 184 protected boolean checkEmpty() { 185 assert mappingFrom.size() == 0 && mappingFromOpr.size() == 0 && mappingTo.size() == 0 : "list must be empty before and after processing"; 186 for (int i = 0; i < stackBlocked.length; i++) { 187 assert stackBlocked[i] == 0 : "stack map must be empty before and after processing"; 188 } 189 for (int i = 0; i < getAllocator().getRegisters().size(); i++) { 190 assert registerBlocked[i] == 0 : "register map must be empty before and after processing"; 191 } 192 checkMultipleReads(); 193 return true; 194 } 195 196 protected void checkMultipleReads() { 197 // multiple reads are allowed in SSA LSRA 198 } 199 200 private boolean verifyBeforeResolve() { 201 assert mappingFrom.size() == mappingFromOpr.size() : "length must be equal"; 202 assert mappingFrom.size() == mappingTo.size() : "length must be equal"; 203 assert insertIdx != -1 : "insert position not set"; 204 205 int i; 206 int j; 207 if (!areMultipleReadsAllowed()) { 208 for (i = 0; i < mappingFrom.size(); i++) { 209 for (j = i + 1; j < mappingFrom.size(); j++) { 210 assert mappingFrom.get(i) == null || mappingFrom.get(i) != mappingFrom.get(j) : "cannot read from same interval twice"; 211 } 212 } 213 } 214 215 for (i = 0; i < mappingTo.size(); i++) { 216 for (j = i + 1; j < mappingTo.size(); j++) { 217 assert mappingTo.get(i) != mappingTo.get(j) : "cannot write to same interval twice"; 218 } 219 } 220 221 HashSet<Value> usedRegs = new HashSet<>(); 222 if (!areMultipleReadsAllowed()) { 223 for (i = 0; i < mappingFrom.size(); i++) { 224 TraceInterval interval = mappingFrom.get(i); 225 if (interval != null && !isIllegal(interval.location())) { 226 boolean unique = usedRegs.add(interval.location()); 227 assert unique : "cannot read from same register twice"; 228 } 229 } 230 } 231 232 usedRegs.clear(); 233 for (i = 0; i < mappingTo.size(); i++) { 234 TraceInterval interval = mappingTo.get(i); 235 if (isIllegal(interval.location())) { 236 // After insertion the location may become illegal, so don't check it since multiple 237 // intervals might be illegal. 238 continue; 239 } 240 boolean unique = usedRegs.add(interval.location()); 241 assert unique : "cannot write to same register twice"; 242 } 243 244 verifyStackSlotMapping(); 245 246 return true; 247 } 248 249 protected void verifyStackSlotMapping() { 250 // relax disjoint stack maps invariant 251 } 252 253 // mark assignedReg and assignedRegHi of the interval as blocked 254 private void blockRegisters(TraceInterval interval) { 255 Value location = interval.location(); 256 if (mightBeBlocked(location)) { 257 assert areMultipleReadsAllowed() || valueBlocked(location) == 0 : "location already marked as used: " + location; 258 int direction = 1; 259 setValueBlocked(location, direction); 260 debug.log("block %s", location); 261 } 262 } 263 264 // mark assignedReg and assignedRegHi of the interval as unblocked 265 private void unblockRegisters(TraceInterval interval) { 266 Value location = interval.location(); 267 if (mightBeBlocked(location)) { 268 assert valueBlocked(location) > 0 : "location already marked as unused: " + location; 269 setValueBlocked(location, -1); 270 debug.log("unblock %s", location); 271 } 272 } 273 274 /** 275 * Checks if the {@linkplain TraceInterval#location() location} of {@code to} is not blocked or 276 * is only blocked by {@code from}. 277 */ 278 private boolean safeToProcessMove(TraceInterval from, TraceInterval to) { 279 Value fromReg = from != null ? from.location() : null; 280 281 Value location = to.location(); 282 if (mightBeBlocked(location)) { 283 if ((valueBlocked(location) > 1 || (valueBlocked(location) == 1 && !isMoveToSelf(fromReg, location)))) { 284 return false; 285 } 286 } 287 288 return true; 289 } 290 291 protected static boolean isMoveToSelf(Value from, Value to) { 292 assert to != null; 293 if (to.equals(from)) { 294 return true; 295 } 296 if (from != null && isRegister(from) && isRegister(to) && asRegister(from).equals(asRegister(to))) { 297 return true; 298 } 299 return false; 300 } 301 302 protected static boolean mightBeBlocked(Value location) { 303 if (isRegister(location)) { 304 return true; 305 } 306 if (isStackSlotValue(location)) { 307 return true; 308 } 309 return false; 310 } 311 312 private void createInsertionBuffer(List<LIRInstruction> list) { 313 assert !insertionBuffer.initialized() : "overwriting existing buffer"; 314 insertionBuffer.init(list); 315 } 316 317 private void appendInsertionBuffer() { 318 if (insertionBuffer.initialized()) { 319 insertionBuffer.finish(); 320 } 321 assert !insertionBuffer.initialized() : "must be uninitialized now"; 322 323 insertIdx = -1; 324 } 325 326 private void insertMove(TraceInterval fromInterval, TraceInterval toInterval) { 327 assert fromInterval.operandNumber != toInterval.operandNumber : "from and to interval equal: " + fromInterval; 328 assert LIRKind.verifyMoveKinds(allocator.getKind(toInterval), allocator.getKind(fromInterval), allocator.getRegisterAllocationConfig()) : "move between different types"; 329 assert insertIdx != -1 : "must setup insert position first"; 330 331 insertionBuffer.append(insertIdx, createMove(allocator.getOperand(fromInterval), allocator.getOperand(toInterval), fromInterval.location(), toInterval.location())); 332 333 if (debug.isLogEnabled()) { 334 debug.log("insert move from %s to %s at %d", fromInterval, toInterval, insertIdx); 335 } 336 } 337 338 /** 339 * @param fromOpr {@link TraceInterval operand} of the {@code from} interval 340 * @param toOpr {@link TraceInterval operand} of the {@code to} interval 341 * @param fromLocation {@link TraceInterval#location() location} of the {@code to} interval 342 * @param toLocation {@link TraceInterval#location() location} of the {@code to} interval 343 */ 344 protected LIRInstruction createMove(AllocatableValue fromOpr, AllocatableValue toOpr, AllocatableValue fromLocation, AllocatableValue toLocation) { 345 if (isStackSlotValue(toLocation) && isStackSlotValue(fromLocation)) { 346 return getAllocator().getSpillMoveFactory().createStackMove(toOpr, fromOpr); 347 } 348 return getAllocator().getSpillMoveFactory().createMove(toOpr, fromOpr); 349 } 350 351 private void insertMove(Constant fromOpr, TraceInterval toInterval) { 352 assert insertIdx != -1 : "must setup insert position first"; 353 354 AllocatableValue toOpr = allocator.getOperand(toInterval); 355 LIRInstruction move = getAllocator().getSpillMoveFactory().createLoad(toOpr, fromOpr); 356 insertionBuffer.append(insertIdx, move); 357 358 if (debug.isLogEnabled()) { 359 debug.log("insert move from value %s to %s at %d", fromOpr, toInterval, insertIdx); 360 } 361 } 362 363 @SuppressWarnings("try") 364 private void resolveMappings() { 365 try (Indent indent = debug.logAndIndent("resolveMapping")) { 366 assert verifyBeforeResolve(); 367 if (debug.isLogEnabled()) { 368 printMapping(); 369 } 370 371 // Block all registers that are used as input operands of a move. 372 // When a register is blocked, no move to this register is emitted. 373 // This is necessary for detecting cycles in moves. 374 int i; 375 for (i = mappingFrom.size() - 1; i >= 0; i--) { 376 TraceInterval fromInterval = mappingFrom.get(i); 377 if (fromInterval != null) { 378 blockRegisters(fromInterval); 379 } 380 } 381 382 ArrayList<AllocatableValue> busySpillSlots = null; 383 while (mappingFrom.size() > 0) { 384 boolean processedInterval = false; 385 386 int spillCandidate = -1; 387 for (i = mappingFrom.size() - 1; i >= 0; i--) { 388 TraceInterval fromInterval = mappingFrom.get(i); 389 TraceInterval toInterval = mappingTo.get(i); 390 391 if (safeToProcessMove(fromInterval, toInterval)) { 392 // this interval can be processed because target is free 393 if (fromInterval != null) { 394 insertMove(fromInterval, toInterval); 395 unblockRegisters(fromInterval); 396 } else { 397 insertMove(mappingFromOpr.get(i), toInterval); 398 } 399 if (isStackSlotValue(toInterval.location())) { 400 if (busySpillSlots == null) { 401 busySpillSlots = new ArrayList<>(2); 402 } 403 busySpillSlots.add(toInterval.location()); 404 } 405 mappingFrom.remove(i); 406 mappingFromOpr.remove(i); 407 mappingTo.remove(i); 408 409 processedInterval = true; 410 } else if (fromInterval != null && isRegister(fromInterval.location()) && (busySpillSlots == null || !busySpillSlots.contains(fromInterval.spillSlot()))) { 411 // this interval cannot be processed now because target is not free 412 // it starts in a register, so it is a possible candidate for spilling 413 spillCandidate = i; 414 } 415 } 416 417 if (!processedInterval) { 418 breakCycle(spillCandidate); 419 } 420 } 421 } 422 423 // check that all intervals have been processed 424 assert checkEmpty(); 425 } 426 427 protected void breakCycle(int spillCandidate) { 428 if (spillCandidate != -1) { 429 // no move could be processed because there is a cycle in the move list 430 // (e.g. r1 . r2, r2 . r1), so one interval must be spilled to memory 431 assert spillCandidate != -1 : "no interval in register for spilling found"; 432 433 // create a new spill interval and assign a stack slot to it 434 TraceInterval fromInterval1 = mappingFrom.get(spillCandidate); 435 // do not allocate a new spill slot for temporary interval, but 436 // use spill slot assigned to fromInterval. Otherwise moves from 437 // one stack slot to another can happen (not allowed by LIRAssembler 438 AllocatableValue spillSlot1 = fromInterval1.spillSlot(); 439 if (spillSlot1 == null) { 440 spillSlot1 = getAllocator().getFrameMapBuilder().allocateSpillSlot(allocator.getKind(fromInterval1)); 441 fromInterval1.setSpillSlot(spillSlot1); 442 cycleBreakingSlotsAllocated.increment(debug); 443 } 444 spillInterval(spillCandidate, fromInterval1, spillSlot1); 445 return; 446 } 447 assert mappingFromSize() > 1; 448 // Arbitrarily select the first entry for spilling. 449 int stackSpillCandidate = 0; 450 TraceInterval fromInterval = getMappingFrom(stackSpillCandidate); 451 // allocate new stack slot 452 VirtualStackSlot spillSlot = getAllocator().getFrameMapBuilder().allocateSpillSlot(allocator.getKind(fromInterval)); 453 spillInterval(stackSpillCandidate, fromInterval, spillSlot); 454 } 455 456 protected void spillInterval(int spillCandidate, TraceInterval fromInterval, AllocatableValue spillSlot) { 457 assert mappingFrom.get(spillCandidate).equals(fromInterval); 458 TraceInterval spillInterval = getAllocator().createDerivedInterval(fromInterval); 459 460 // add a dummy range because real position is difficult to calculate 461 // Note: this range is a special case when the integrity of the allocation is 462 // checked 463 spillInterval.addRange(1, 2); 464 465 spillInterval.assignLocation(spillSlot); 466 467 if (debug.isLogEnabled()) { 468 debug.log("created new Interval for spilling: %s", spillInterval); 469 } 470 blockRegisters(spillInterval); 471 472 // insert a move from register to stack and update the mapping 473 insertMove(fromInterval, spillInterval); 474 mappingFrom.set(spillCandidate, spillInterval); 475 unblockRegisters(fromInterval); 476 } 477 478 @SuppressWarnings("try") 479 private void printMapping() { 480 try (Indent indent = debug.logAndIndent("Mapping")) { 481 for (int i = mappingFrom.size() - 1; i >= 0; i--) { 482 TraceInterval fromInterval = mappingFrom.get(i); 483 TraceInterval toInterval = mappingTo.get(i); 484 String from; 485 Value to = toInterval.location(); 486 if (fromInterval == null) { 487 from = mappingFromOpr.get(i).toString(); 488 } else { 489 from = fromInterval.location().toString(); 490 } 491 debug.log("move %s <- %s", from, to); 492 } 493 } 494 } 495 496 void setInsertPosition(List<LIRInstruction> insertList, int insertIdx) { 497 assert this.insertIdx == -1 : "use moveInsertPosition instead of setInsertPosition when data already set"; 498 499 createInsertionBuffer(insertList); 500 this.insertIdx = insertIdx; 501 } 502 503 void moveInsertPosition(List<LIRInstruction> newInsertList, int newInsertIdx) { 504 if (insertionBuffer.lirList() != null && (insertionBuffer.lirList() != newInsertList || this.insertIdx != newInsertIdx)) { 505 // insert position changed . resolve current mappings 506 resolveMappings(); 507 } 508 509 assert insertionBuffer.lirList() != newInsertList || newInsertIdx >= insertIdx : String.format("Decreasing insert index: old=%d new=%d", insertIdx, newInsertIdx); 510 511 if (insertionBuffer.lirList() != newInsertList) { 512 // block changed . append insertionBuffer because it is 513 // bound to a specific block and create a new insertionBuffer 514 appendInsertionBuffer(); 515 createInsertionBuffer(newInsertList); 516 } 517 518 this.insertIdx = newInsertIdx; 519 } 520 521 public void addMapping(TraceInterval fromInterval, TraceInterval toInterval) { 522 523 if (isIllegal(toInterval.location()) && toInterval.canMaterialize()) { 524 if (debug.isLogEnabled()) { 525 debug.log("no store to rematerializable interval %s needed", toInterval); 526 } 527 return; 528 } 529 if (isIllegal(fromInterval.location()) && fromInterval.canMaterialize()) { 530 // Instead of a reload, re-materialize the value 531 JavaConstant rematValue = fromInterval.getMaterializedValue(); 532 addMapping(rematValue, toInterval); 533 return; 534 } 535 if (debug.isLogEnabled()) { 536 debug.log("add move mapping from %s to %s", fromInterval, toInterval); 537 } 538 539 assert fromInterval.operandNumber != toInterval.operandNumber : "from and to interval equal: " + fromInterval; 540 assert LIRKind.verifyMoveKinds(allocator.getKind(toInterval), allocator.getKind(fromInterval), allocator.getRegisterAllocationConfig()) : String.format( 541 "Kind mismatch: %s vs. %s, from=%s, to=%s", allocator.getKind(fromInterval), allocator.getKind(toInterval), fromInterval, toInterval); 542 mappingFrom.add(fromInterval); 543 mappingFromOpr.add(null); 544 mappingTo.add(toInterval); 545 } 546 547 public void addMapping(Constant fromOpr, TraceInterval toInterval) { 548 if (debug.isLogEnabled()) { 549 debug.log("add move mapping from %s to %s", fromOpr, toInterval); 550 } 551 552 mappingFrom.add(null); 553 mappingFromOpr.add(fromOpr); 554 mappingTo.add(toInterval); 555 } 556 557 void resolveAndAppendMoves() { 558 if (hasMappings()) { 559 resolveMappings(); 560 } 561 appendInsertionBuffer(); 562 } 563} 564