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