src/jdk.internal.vm.compiler/share/classes/org.graalvm.compiler.lir/src/org/graalvm/compiler/lir/RedundantMoveElimination.java
Index Unified diffs Context diffs Sdiffs Patch New Old Previous File Next File hotspot Sdiff src/jdk.internal.vm.compiler/share/classes/org.graalvm.compiler.lir/src/org/graalvm/compiler/lir

src/jdk.internal.vm.compiler/share/classes/org.graalvm.compiler.lir/src/org/graalvm/compiler/lir/RedundantMoveElimination.java

Print this page




   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.Arrays;
  29 import java.util.Collections;
  30 import java.util.EnumSet;
  31 import java.util.List;
  32 import java.util.Map;
  33 
  34 import org.graalvm.compiler.core.common.CollectionsFactory;
  35 import org.graalvm.compiler.core.common.LIRKind;
  36 import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
  37 import org.graalvm.compiler.debug.Debug;
  38 import org.graalvm.compiler.debug.DebugCounter;
  39 import org.graalvm.compiler.debug.Indent;
  40 import org.graalvm.compiler.lir.LIRInstruction.OperandFlag;
  41 import org.graalvm.compiler.lir.LIRInstruction.OperandMode;
  42 import org.graalvm.compiler.lir.StandardOp.MoveOp;
  43 import org.graalvm.compiler.lir.StandardOp.ValueMoveOp;
  44 import org.graalvm.compiler.lir.framemap.FrameMap;
  45 import org.graalvm.compiler.lir.gen.LIRGenerationResult;
  46 import org.graalvm.compiler.lir.phases.PostAllocationOptimizationPhase;


  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 DebugCounter deletedMoves = Debug.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     }


  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         Map<AbstractBlockBase<?>, BlockData> blockData = CollectionsFactory.newMap();
 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         Map<Integer, Integer> stackIndices = CollectionsFactory.newMap();
 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 


 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 
 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                 List<LIRInstruction> instructions = lir.getLIRforBlock(block);
 183                 for (LIRInstruction op : instructions) {
 184                     if (isEligibleMove(op)) {
 185                         Value dest = ((MoveOp) 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             /*


 269                                  * Merge the states of predecessor blocks
 270                                  */
 271                                 for (AbstractBlockBase<?> predecessor : block.getPredecessors()) {
 272                                     BlockData predData = blockData.get(predecessor);
 273                                     newState |= mergeState(data.entryState, predData.exitState, valueNum);
 274                                 }
 275                             }
 276                             // Advance by the value numbers which are "consumed" by
 277                             // clearValues and mergeState
 278                             valueNum += data.entryState.length;
 279 
 280                             if (newState || firstRound) {
 281                                 try (Indent indent3 = Debug.logAndIndent("update block %d", block.getId())) {
 282 
 283                                     /*
 284                                      * Derive the exit state from the entry state by iterating
 285                                      * through all instructions of the block.
 286                                      */
 287                                     int[] iterState = data.exitState;
 288                                     copyState(iterState, data.entryState);
 289                                     List<LIRInstruction> instructions = lir.getLIRforBlock(block);
 290 
 291                                     for (LIRInstruction op : instructions) {
 292                                         valueNum = updateState(iterState, op, valueNum);
 293                                     }
 294                                     changed = true;
 295                                 }
 296                             }
 297                             if (firstRound) {
 298                                 currentValueNum = valueNum;
 299                             }
 300                         }
 301                         firstRound = false;
 302                     }
 303                     numIter++;
 304 
 305                     if (numIter > 5) {
 306                         /*
 307                          * This is _very_ seldom.
 308                          */
 309                         return false;


 314             }
 315 
 316             return true;
 317         }
 318 
 319         /**
 320          * Deletes all move instructions where the target location already contains the source
 321          * value.
 322          */
 323         @SuppressWarnings("try")
 324         private void eliminateMoves(LIR lir) {
 325 
 326             try (Indent indent = Debug.logAndIndent("eliminate moves")) {
 327 
 328                 AbstractBlockBase<?>[] blocks = lir.linearScanOrder();
 329 
 330                 for (AbstractBlockBase<?> block : blocks) {
 331 
 332                     try (Indent indent2 = Debug.logAndIndent("eliminate moves in block %d", block.getId())) {
 333 
 334                         List<LIRInstruction> instructions = lir.getLIRforBlock(block);
 335                         BlockData data = blockData.get(block);
 336                         boolean hasDead = false;
 337 
 338                         // Reuse the entry state for iteration, we don't need it later.
 339                         int[] iterState = data.entryState;
 340 
 341                         // Add the values which are "consumed" by clearValues and
 342                         // mergeState in solveDataFlow
 343                         int valueNum = data.entryValueNum + data.entryState.length;
 344 
 345                         int numInsts = instructions.size();
 346                         for (int idx = 0; idx < numInsts; idx++) {
 347                             LIRInstruction op = instructions.get(idx);
 348                             if (isEligibleMove(op)) {
 349                                 ValueMoveOp moveOp = (ValueMoveOp) op;
 350                                 int sourceIdx = getStateIdx(moveOp.getInput());
 351                                 int destIdx = getStateIdx(moveOp.getResult());
 352                                 if (sourceIdx >= 0 && destIdx >= 0 && iterState[sourceIdx] == iterState[destIdx]) {
 353                                     assert iterState[sourceIdx] != INIT_VALUE;
 354                                     Debug.log("delete move %s", op);


 368                     }
 369                 }
 370             }
 371         }
 372 
 373         /**
 374          * Updates the state for one instruction.
 375          */
 376         @SuppressWarnings("try")
 377         private int updateState(final int[] state, LIRInstruction op, int initValueNum) {
 378 
 379             try (final 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) 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";
 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                 /*




   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.Debug;
  36 import org.graalvm.compiler.debug.DebugCounter;
  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.Equivalence;
  46 import org.graalvm.util.EconomicMap;
  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 DebugCounter deletedMoves = Debug.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     }


  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 


 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 
 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) 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             /*


 269                                  * Merge the states of predecessor blocks
 270                                  */
 271                                 for (AbstractBlockBase<?> predecessor : block.getPredecessors()) {
 272                                     BlockData predData = blockData.get(predecessor);
 273                                     newState |= mergeState(data.entryState, predData.exitState, valueNum);
 274                                 }
 275                             }
 276                             // Advance by the value numbers which are "consumed" by
 277                             // clearValues and mergeState
 278                             valueNum += data.entryState.length;
 279 
 280                             if (newState || firstRound) {
 281                                 try (Indent indent3 = Debug.logAndIndent("update block %d", block.getId())) {
 282 
 283                                     /*
 284                                      * Derive the exit state from the entry state by iterating
 285                                      * through all instructions of the block.
 286                                      */
 287                                     int[] iterState = data.exitState;
 288                                     copyState(iterState, data.entryState);
 289                                     ArrayList<LIRInstruction> instructions = lir.getLIRforBlock(block);
 290 
 291                                     for (LIRInstruction op : instructions) {
 292                                         valueNum = updateState(iterState, op, valueNum);
 293                                     }
 294                                     changed = true;
 295                                 }
 296                             }
 297                             if (firstRound) {
 298                                 currentValueNum = valueNum;
 299                             }
 300                         }
 301                         firstRound = false;
 302                     }
 303                     numIter++;
 304 
 305                     if (numIter > 5) {
 306                         /*
 307                          * This is _very_ seldom.
 308                          */
 309                         return false;


 314             }
 315 
 316             return true;
 317         }
 318 
 319         /**
 320          * Deletes all move instructions where the target location already contains the source
 321          * value.
 322          */
 323         @SuppressWarnings("try")
 324         private void eliminateMoves(LIR lir) {
 325 
 326             try (Indent indent = Debug.logAndIndent("eliminate moves")) {
 327 
 328                 AbstractBlockBase<?>[] blocks = lir.linearScanOrder();
 329 
 330                 for (AbstractBlockBase<?> block : blocks) {
 331 
 332                     try (Indent indent2 = Debug.logAndIndent("eliminate moves in block %d", block.getId())) {
 333 
 334                         ArrayList<LIRInstruction> instructions = lir.getLIRforBlock(block);
 335                         BlockData data = blockData.get(block);
 336                         boolean hasDead = false;
 337 
 338                         // Reuse the entry state for iteration, we don't need it later.
 339                         int[] iterState = data.entryState;
 340 
 341                         // Add the values which are "consumed" by clearValues and
 342                         // mergeState in solveDataFlow
 343                         int valueNum = data.entryValueNum + data.entryState.length;
 344 
 345                         int numInsts = instructions.size();
 346                         for (int idx = 0; idx < numInsts; idx++) {
 347                             LIRInstruction op = instructions.get(idx);
 348                             if (isEligibleMove(op)) {
 349                                 ValueMoveOp moveOp = (ValueMoveOp) op;
 350                                 int sourceIdx = getStateIdx(moveOp.getInput());
 351                                 int destIdx = getStateIdx(moveOp.getResult());
 352                                 if (sourceIdx >= 0 && destIdx >= 0 && iterState[sourceIdx] == iterState[destIdx]) {
 353                                     assert iterState[sourceIdx] != INIT_VALUE;
 354                                     Debug.log("delete move %s", op);


 368                     }
 369                 }
 370             }
 371         }
 372 
 373         /**
 374          * Updates the state for one instruction.
 375          */
 376         @SuppressWarnings("try")
 377         private int updateState(final int[] state, LIRInstruction op, int initValueNum) {
 378 
 379             try (final 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) 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                 /*


src/jdk.internal.vm.compiler/share/classes/org.graalvm.compiler.lir/src/org/graalvm/compiler/lir/RedundantMoveElimination.java
Index Unified diffs Context diffs Sdiffs Patch New Old Previous File Next File