1 /* 2 * Copyright (c) 2013, 2016, 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; 24 25 import static jdk.vm.ci.code.ValueUtil.isRegister; 26 import static jdk.vm.ci.code.ValueUtil.isStackSlot; 27 28 import java.util.ArrayList; 29 import java.util.Arrays; 30 import java.util.Collections; 31 import java.util.EnumSet; 32 33 import org.graalvm.compiler.core.common.LIRKind; 34 import org.graalvm.compiler.core.common.cfg.AbstractBlockBase; 35 import org.graalvm.compiler.debug.CounterKey; 36 import org.graalvm.compiler.debug.DebugContext; 37 import org.graalvm.compiler.debug.Indent; 38 import org.graalvm.compiler.lir.LIRInstruction.OperandFlag; 39 import org.graalvm.compiler.lir.LIRInstruction.OperandMode; 40 import org.graalvm.compiler.lir.StandardOp.MoveOp; 41 import org.graalvm.compiler.lir.StandardOp.ValueMoveOp; 42 import org.graalvm.compiler.lir.framemap.FrameMap; 43 import org.graalvm.compiler.lir.gen.LIRGenerationResult; 44 import org.graalvm.compiler.lir.phases.PostAllocationOptimizationPhase; 45 import org.graalvm.util.EconomicMap; 46 import org.graalvm.util.Equivalence; 47 48 import jdk.vm.ci.code.Register; 49 import jdk.vm.ci.code.RegisterArray; 50 import jdk.vm.ci.code.RegisterValue; 51 import jdk.vm.ci.code.StackSlot; 52 import jdk.vm.ci.code.TargetDescription; 53 import jdk.vm.ci.meta.Value; 54 55 /** 56 * Removes move instructions, where the destination value is already in place. 57 */ 58 public final class RedundantMoveElimination extends PostAllocationOptimizationPhase { 59 60 private static final CounterKey deletedMoves = DebugContext.counter("RedundantMovesEliminated"); 61 62 @Override 63 protected void run(TargetDescription target, LIRGenerationResult lirGenRes, PostAllocationOptimizationContext context) { 64 Optimization redundantMoveElimination = new Optimization(lirGenRes.getFrameMap()); 65 redundantMoveElimination.doOptimize(lirGenRes.getLIR()); 66 } 67 68 /** 69 * Holds the entry and exit states for each block for dataflow analysis. The state is an array 70 * with an element for each relevant location (register or stack slot). Each element holds the 71 * global number of the location's definition. A location definition is simply an output of an 72 * instruction. Note that because instructions can have multiple outputs it is not possible to 73 * use the instruction id for value numbering. In addition, the result of merging at block 74 * entries (= phi values) get unique value numbers. 75 * 76 * The value numbers also contain information if it is an object kind value or not: if the 77 * number is negative it is an object kind value. 78 */ 79 private static final class BlockData { 80 81 BlockData(int stateSize) { 82 entryState = new int[stateSize]; 83 exitState = new int[stateSize]; 84 } 85 86 /* 87 * The state at block entry for global dataflow analysis. It contains a global value number 88 * for each location to optimize. 89 */ 90 int[] entryState; 91 92 /* 93 * The state at block exit for global dataflow analysis. It contains a global value number 94 * for each location to optimize. 95 */ 96 int[] exitState; 97 98 /* 99 * The starting number for global value numbering in this block. 100 */ 101 int entryValueNum; 102 } 103 104 private static final class Optimization { 105 106 EconomicMap<AbstractBlockBase<?>, BlockData> blockData = EconomicMap.create(Equivalence.IDENTITY); 107 108 RegisterArray callerSaveRegs; 109 110 /** 111 * Contains the register number for registers which can be optimized and -1 for the others. 112 */ 113 int[] eligibleRegs; 114 115 /** 116 * A map from the {@link StackSlot} {@link #getOffset offset} to an index into the state. 117 * StackSlots of different kinds that map to the same location will map to the same index. 118 */ 119 EconomicMap<Integer, Integer> stackIndices = EconomicMap.create(Equivalence.DEFAULT); 120 121 int numRegs; 122 123 private final FrameMap frameMap; 124 125 /* 126 * Pseudo value for a not yet assigned location. 127 */ 128 static final int INIT_VALUE = 0; 129 130 Optimization(FrameMap frameMap) { 131 this.frameMap = frameMap; 132 } 133 134 /** 135 * The main method doing the elimination of redundant moves. 136 */ 137 @SuppressWarnings("try") 138 private void doOptimize(LIR lir) { 139 DebugContext debug = lir.getDebug(); 140 try (Indent indent = debug.logAndIndent("eliminate redundant moves")) { 141 142 callerSaveRegs = frameMap.getRegisterConfig().getCallerSaveRegisters(); 143 144 initBlockData(lir); 145 146 // Compute a table of the registers which are eligible for move optimization. 147 // Unallocatable registers should never be optimized. 148 eligibleRegs = new int[numRegs]; 149 Arrays.fill(eligibleRegs, -1); 150 for (Register reg : frameMap.getRegisterConfig().getAllocatableRegisters()) { 151 if (reg.number < numRegs) { 152 eligibleRegs[reg.number] = reg.number; 153 } 154 } 155 156 if (!solveDataFlow(lir)) { 157 return; 158 } 159 160 eliminateMoves(lir); 161 } 162 } 163 164 /** 165 * The maximum number of locations * blocks. This is a complexity limit for the inner loop 166 * in {@link #mergeState} (assuming a small number of iterations in {@link #solveDataFlow}. 167 */ 168 private static final int COMPLEXITY_LIMIT = 30000; 169 170 private void initBlockData(LIR lir) { 171 DebugContext debug = lir.getDebug(); 172 AbstractBlockBase<?>[] blocks = lir.linearScanOrder(); 173 numRegs = 0; 174 175 int maxStackLocations = COMPLEXITY_LIMIT / blocks.length; 176 177 /* 178 * Search for relevant locations which can be optimized. These are register or stack 179 * slots which occur as destinations of move instructions. 180 */ 181 for (AbstractBlockBase<?> block : blocks) { 182 ArrayList<LIRInstruction> instructions = lir.getLIRforBlock(block); 183 for (LIRInstruction op : instructions) { 184 if (isEligibleMove(op)) { 185 Value dest = MoveOp.asMoveOp(op).getResult(); 186 if (isRegister(dest)) { 187 int regNum = ((RegisterValue) dest).getRegister().number; 188 if (regNum >= numRegs) { 189 numRegs = regNum + 1; 190 } 191 } else if (isStackSlot(dest)) { 192 StackSlot stackSlot = (StackSlot) dest; 193 Integer offset = getOffset(stackSlot); 194 if (!stackIndices.containsKey(offset) && stackIndices.size() < maxStackLocations) { 195 stackIndices.put(offset, stackIndices.size()); 196 } 197 } 198 } 199 } 200 } 201 202 /* 203 * Now we know the number of locations to optimize, so we can allocate the block states. 204 */ 205 int numLocations = numRegs + stackIndices.size(); 206 debug.log("num locations = %d (regs = %d, stack = %d)", numLocations, numRegs, stackIndices.size()); 207 for (AbstractBlockBase<?> block : blocks) { 208 BlockData data = new BlockData(numLocations); 209 blockData.put(block, data); 210 } 211 } 212 213 private int getOffset(StackSlot stackSlot) { 214 return stackSlot.getOffset(frameMap.totalFrameSize()); 215 } 216 217 /** 218 * Calculates the entry and exit states for all basic blocks. 219 * 220 * @return Returns true on success and false if the control flow is too complex. 221 */ 222 @SuppressWarnings("try") 223 private boolean solveDataFlow(LIR lir) { 224 225 DebugContext debug = lir.getDebug(); 226 try (Indent indent = debug.logAndIndent("solve data flow")) { 227 228 AbstractBlockBase<?>[] blocks = lir.linearScanOrder(); 229 230 int numIter = 0; 231 232 /* 233 * Iterate until there are no more changes. 234 */ 235 int currentValueNum = 1; 236 boolean firstRound = true; 237 boolean changed; 238 do { 239 changed = false; 240 try (Indent indent2 = debug.logAndIndent("new iteration")) { 241 242 for (AbstractBlockBase<?> block : blocks) { 243 244 BlockData data = blockData.get(block); 245 /* 246 * Initialize the number for global value numbering for this block. It 247 * is essential that the starting number for a block is consistent at 248 * all iterations and also in eliminateMoves(). 249 */ 250 if (firstRound) { 251 data.entryValueNum = currentValueNum; 252 } 253 int valueNum = data.entryValueNum; 254 assert valueNum > 0; 255 boolean newState = false; 256 257 if (block == blocks[0] || block.isExceptionEntry()) { 258 /* 259 * The entry block has undefined values. And also exception handler 260 * blocks: the LinearScan can insert moves at the end of an 261 * exception handler predecessor block (after the invoke, which 262 * throws the exception), and in reality such moves are not in the 263 * control flow in case of an exception. So we assume a save default 264 * for exception handler blocks. 265 */ 266 debug.log("kill all values at entry of block %d", block.getId()); 267 clearValues(data.entryState, valueNum); 268 } else { 269 /* 270 * Merge the states of predecessor blocks 271 */ 272 for (AbstractBlockBase<?> predecessor : block.getPredecessors()) { 273 BlockData predData = blockData.get(predecessor); 274 newState |= mergeState(data.entryState, predData.exitState, valueNum); 275 } 276 } 277 // Advance by the value numbers which are "consumed" by 278 // clearValues and mergeState 279 valueNum += data.entryState.length; 280 281 if (newState || firstRound) { 282 try (Indent indent3 = debug.logAndIndent("update block %d", block.getId())) { 283 284 /* 285 * Derive the exit state from the entry state by iterating 286 * through all instructions of the block. 287 */ 288 int[] iterState = data.exitState; 289 copyState(iterState, data.entryState); 290 ArrayList<LIRInstruction> instructions = lir.getLIRforBlock(block); 291 292 for (LIRInstruction op : instructions) { 293 valueNum = updateState(debug, iterState, op, valueNum); 294 } 295 changed = true; 296 } 297 } 298 if (firstRound) { 299 currentValueNum = valueNum; 300 } 301 } 302 firstRound = false; 303 } 304 numIter++; 305 306 if (numIter > 5) { 307 /* 308 * This is _very_ seldom. 309 */ 310 return false; 311 } 312 313 } while (changed); 314 315 } 316 317 return true; 318 } 319 320 /** 321 * Deletes all move instructions where the target location already contains the source 322 * value. 323 */ 324 @SuppressWarnings("try") 325 private void eliminateMoves(LIR lir) { 326 DebugContext debug = lir.getDebug(); 327 328 try (Indent indent = debug.logAndIndent("eliminate moves")) { 329 330 AbstractBlockBase<?>[] blocks = lir.linearScanOrder(); 331 332 for (AbstractBlockBase<?> block : blocks) { 333 334 try (Indent indent2 = debug.logAndIndent("eliminate moves in block %d", block.getId())) { 335 336 ArrayList<LIRInstruction> instructions = lir.getLIRforBlock(block); 337 BlockData data = blockData.get(block); 338 boolean hasDead = false; 339 340 // Reuse the entry state for iteration, we don't need it later. 341 int[] iterState = data.entryState; 342 343 // Add the values which are "consumed" by clearValues and 344 // mergeState in solveDataFlow 345 int valueNum = data.entryValueNum + data.entryState.length; 346 347 int numInsts = instructions.size(); 348 for (int idx = 0; idx < numInsts; idx++) { 349 LIRInstruction op = instructions.get(idx); 350 if (isEligibleMove(op)) { 351 ValueMoveOp moveOp = ValueMoveOp.asValueMoveOp(op); 352 int sourceIdx = getStateIdx(moveOp.getInput()); 353 int destIdx = getStateIdx(moveOp.getResult()); 354 if (sourceIdx >= 0 && destIdx >= 0 && iterState[sourceIdx] == iterState[destIdx]) { 355 assert iterState[sourceIdx] != INIT_VALUE; 356 debug.log("delete move %s", op); 357 instructions.set(idx, null); 358 hasDead = true; 359 deletedMoves.increment(debug); 360 } 361 } 362 // It doesn't harm if updateState is also called for a deleted move 363 valueNum = updateState(debug, iterState, op, valueNum); 364 } 365 if (hasDead) { 366 instructions.removeAll(Collections.singleton(null)); 367 } 368 } 369 } 370 } 371 } 372 373 /** 374 * Updates the state for one instruction. 375 */ 376 @SuppressWarnings("try") 377 private int updateState(DebugContext debug, final int[] state, LIRInstruction op, int initValueNum) { 378 379 try (Indent indent = debug.logAndIndent("update state for op %s, initial value num = %d", op, initValueNum)) { 380 if (isEligibleMove(op)) { 381 /* 382 * Handle the special case of a move instruction 383 */ 384 ValueMoveOp moveOp = ValueMoveOp.asValueMoveOp(op); 385 int sourceIdx = getStateIdx(moveOp.getInput()); 386 int destIdx = getStateIdx(moveOp.getResult()); 387 if (sourceIdx >= 0 && destIdx >= 0) { 388 assert isObjectValue(state[sourceIdx]) || LIRKind.isValue(moveOp.getInput()) : "move op moves object but input is not defined as object " + moveOp; 389 state[destIdx] = state[sourceIdx]; 390 debug.log("move value %d from %d to %d", state[sourceIdx], sourceIdx, destIdx); 391 return initValueNum; 392 } 393 } 394 395 int valueNum = initValueNum; 396 397 if (op.destroysCallerSavedRegisters()) { 398 debug.log("kill all caller save regs"); 399 400 for (Register reg : callerSaveRegs) { 401 if (reg.number < numRegs) { 402 // Kind.Object is the save default 403 state[reg.number] = encodeValueNum(valueNum++, true); 404 } 405 } 406 } 407 408 /* 409 * Value procedure for the instruction's output and temp values 410 */ 411 class OutputValueConsumer implements ValueConsumer { 412 413 int opValueNum; 414 415 OutputValueConsumer(int opValueNum) { 416 this.opValueNum = opValueNum; 417 } 418 419 @Override 420 public void visitValue(Value operand, OperandMode mode, EnumSet<OperandFlag> flags) { 421 int stateIdx = getStateIdx(operand); 422 if (stateIdx >= 0) { 423 /* 424 * Assign a unique number to the output or temp location. 425 */ 426 state[stateIdx] = encodeValueNum(opValueNum++, !LIRKind.isValue(operand)); 427 debug.log("set def %d for register %s(%d): %d", opValueNum, operand, stateIdx, state[stateIdx]); 428 } 429 } 430 } 431 432 OutputValueConsumer outputValueConsumer = new OutputValueConsumer(valueNum); 433 434 op.visitEachTemp(outputValueConsumer); 435 /* 436 * Semantically the output values are written _after_ the temp values 437 */ 438 op.visitEachOutput(outputValueConsumer); 439 440 valueNum = outputValueConsumer.opValueNum; 441 442 if (op.hasState()) { 443 /* 444 * All instructions with framestates (mostly method calls), may do garbage 445 * collection. GC will rewrite all object references which are live at this 446 * point. So we can't rely on their values. It would be sufficient to just kill 447 * all values which are referenced in the state (or all values which are not), 448 * but for simplicity we kill all values. 449 */ 450 debug.log("kill all object values"); 451 clearValuesOfKindObject(state, valueNum); 452 valueNum += state.length; 453 } 454 455 return valueNum; 456 } 457 } 458 459 /** 460 * The state merge function for dataflow joins. 461 */ 462 private static boolean mergeState(int[] dest, int[] source, int defNum) { 463 assert dest.length == source.length; 464 boolean changed = false; 465 for (int idx = 0; idx < source.length; idx++) { 466 int phiNum = defNum + idx; 467 int dst = dest[idx]; 468 int src = source[idx]; 469 if (dst != src && src != INIT_VALUE && dst != encodeValueNum(phiNum, isObjectValue(dst))) { 470 if (dst != INIT_VALUE) { 471 dst = encodeValueNum(phiNum, isObjectValue(dst) || isObjectValue(src)); 472 } else { 473 dst = src; 474 } 475 dest[idx] = dst; 476 changed = true; 477 } 478 } 479 return changed; 480 } 481 482 private static void copyState(int[] dest, int[] source) { 483 assert dest.length == source.length; 484 for (int idx = 0; idx < source.length; idx++) { 485 dest[idx] = source[idx]; 486 } 487 } 488 489 private static void clearValues(int[] state, int defNum) { 490 for (int idx = 0; idx < state.length; idx++) { 491 int phiNum = defNum + idx; 492 // Let the killed values assume to be object references: it's the save default. 493 state[idx] = encodeValueNum(phiNum, true); 494 } 495 } 496 497 private static void clearValuesOfKindObject(int[] state, int defNum) { 498 for (int idx = 0; idx < state.length; idx++) { 499 int phiNum = defNum + idx; 500 if (isObjectValue(state[idx])) { 501 state[idx] = encodeValueNum(phiNum, true); 502 } 503 } 504 } 505 506 /** 507 * Returns the index to the state arrays in BlockData for a specific location. 508 */ 509 private int getStateIdx(Value location) { 510 if (isRegister(location)) { 511 int regNum = ((RegisterValue) location).getRegister().number; 512 if (regNum < numRegs) { 513 return eligibleRegs[regNum]; 514 } 515 return -1; 516 } 517 if (isStackSlot(location)) { 518 StackSlot slot = (StackSlot) location; 519 Integer index = stackIndices.get(getOffset(slot)); 520 if (index != null) { 521 return index.intValue() + numRegs; 522 } 523 } 524 return -1; 525 } 526 527 /** 528 * Encodes a value number + the is-object information to a number to be stored in a state. 529 */ 530 private static int encodeValueNum(int valueNum, boolean isObjectKind) { 531 assert valueNum > 0; 532 if (isObjectKind) { 533 return -valueNum; 534 } 535 return valueNum; 536 } 537 538 /** 539 * Returns true if an encoded value number (which is stored in a state) refers to an object 540 * reference. 541 */ 542 private static boolean isObjectValue(int encodedValueNum) { 543 return encodedValueNum < 0; 544 } 545 546 /** 547 * Returns true for a move instruction which is a candidate for elimination. 548 */ 549 private static boolean isEligibleMove(LIRInstruction op) { 550 if (ValueMoveOp.isValueMoveOp(op)) { 551 ValueMoveOp moveOp = ValueMoveOp.asValueMoveOp(op); 552 Value source = moveOp.getInput(); 553 Value dest = moveOp.getResult(); 554 /* 555 * Moves with mismatching kinds are not moves, but memory loads/stores! 556 */ 557 return source.getValueKind().equals(dest.getValueKind()); 558 } 559 return false; 560 } 561 } 562 }