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; 24 25 import java.util.ArrayList; 26 import java.util.List; 27 28 import org.graalvm.compiler.core.common.cfg.AbstractBlockBase; 29 import org.graalvm.compiler.lir.StandardOp.LoadConstantOp; 30 import org.graalvm.compiler.lir.StandardOp.MoveOp; 31 import org.graalvm.compiler.lir.StandardOp.ValueMoveOp; 32 import org.graalvm.compiler.lir.gen.LIRGenerationResult; 33 import org.graalvm.compiler.lir.phases.PostAllocationOptimizationPhase; 34 35 import jdk.vm.ci.code.TargetDescription; 36 37 /** 38 * This class optimizes moves, particularly those that result from eliminating SSA form. 39 * <p> 40 * When a block has more than one predecessor, and all predecessors end with the 41 * {@linkplain Optimizer#same(LIRInstruction, LIRInstruction) same} sequence of {@linkplain MoveOp 42 * move} instructions, then these sequences can be replaced with a single copy of the sequence at 43 * the beginning of the block. 44 * <p> 45 * Similarly, when a block has more than one successor, then same sequences of moves at the 46 * beginning of the successors can be placed once at the end of the block. But because the moves 47 * must be inserted before all branch instructions, this works only when there is exactly one 48 * conditional branch at the end of the block (because the moves must be inserted before all 49 * branches, but after all compares). 50 * <p> 51 * This optimization affects all kind of moves (reg->reg, reg->stack and stack->reg). 52 * Because this optimization works best when a block contains only a few moves, it has a huge impact 53 * on the number of blocks that are totally empty. 54 */ 55 public final class EdgeMoveOptimizer extends PostAllocationOptimizationPhase { 56 57 @Override 58 protected void run(TargetDescription target, LIRGenerationResult lirGenRes, PostAllocationOptimizationContext context) { 59 LIR ir = lirGenRes.getLIR(); 60 Optimizer optimizer = new Optimizer(ir); 61 62 AbstractBlockBase<?>[] blockList = ir.linearScanOrder(); 63 // ignore the first block in the list (index 0 is not processed) 64 for (int i = blockList.length - 1; i >= 1; i--) { 65 AbstractBlockBase<?> block = blockList[i]; 66 67 if (block.getPredecessorCount() > 1) { 68 optimizer.optimizeMovesAtBlockEnd(block); 69 } 70 if (block.getSuccessorCount() == 2) { 71 optimizer.optimizeMovesAtBlockBegin(block); 72 } 73 } 74 } 75 76 private static final class Optimizer { 77 private final List<List<LIRInstruction>> edgeInstructionSeqences; 78 private LIR ir; 79 80 Optimizer(LIR ir) { 81 this.ir = ir; 82 edgeInstructionSeqences = new ArrayList<>(4); 83 } 84 85 /** 86 * Determines if two operations are both {@linkplain MoveOp moves} that have the same source 87 * and {@linkplain MoveOp#getResult() destination} operands. 88 * 89 * @param op1 the first instruction to compare 90 * @param op2 the second instruction to compare 91 * @return {@code true} if {@code op1} and {@code op2} are the same by the above algorithm 92 */ 93 private static boolean same(LIRInstruction op1, LIRInstruction op2) { 94 assert op1 != null; 95 assert op2 != null; 96 97 if (op1 instanceof ValueMoveOp && op2 instanceof ValueMoveOp) { 98 ValueMoveOp move1 = (ValueMoveOp) op1; 99 ValueMoveOp move2 = (ValueMoveOp) op2; 100 if (move1.getInput().equals(move2.getInput()) && move1.getResult().equals(move2.getResult())) { 101 // these moves are exactly equal and can be optimized 102 return true; 103 } 104 } else if (op1 instanceof LoadConstantOp && op2 instanceof LoadConstantOp) { 105 LoadConstantOp move1 = (LoadConstantOp) op1; 106 LoadConstantOp move2 = (LoadConstantOp) op2; 107 if (move1.getConstant().equals(move2.getConstant()) && move1.getResult().equals(move2.getResult())) { 108 // these moves are exactly equal and can be optimized 109 return true; 110 } 111 } 112 return false; 113 } 114 115 /** 116 * Moves the longest {@linkplain #same common} subsequence at the end all predecessors of 117 * {@code block} to the start of {@code block}. 118 */ 119 private void optimizeMovesAtBlockEnd(AbstractBlockBase<?> block) { 120 for (AbstractBlockBase<?> pred : block.getPredecessors()) { 121 if (pred == block) { 122 // currently we can't handle this correctly. 123 return; 124 } 125 } 126 127 // clear all internal data structures 128 edgeInstructionSeqences.clear(); 129 130 int numPreds = block.getPredecessorCount(); 131 assert numPreds > 1 : "do not call otherwise"; 132 133 // setup a list with the LIR instructions of all predecessors 134 for (AbstractBlockBase<?> pred : block.getPredecessors()) { 135 assert pred != null; 136 assert ir.getLIRforBlock(pred) != null; 137 List<LIRInstruction> predInstructions = ir.getLIRforBlock(pred); 138 139 if (pred.getSuccessorCount() != 1) { 140 // this can happen with switch-statements where multiple edges are between 141 // the same blocks. 142 return; 143 } 144 145 assert pred.getSuccessors()[0] == block : "invalid control flow"; 146 assert predInstructions.get(predInstructions.size() - 1) instanceof StandardOp.JumpOp : "block must end with unconditional jump"; 147 148 if (predInstructions.get(predInstructions.size() - 1).hasState()) { 149 // can not optimize instructions that have debug info 150 return; 151 } 152 153 // ignore the unconditional branch at the end of the block 154 List<LIRInstruction> seq = predInstructions.subList(0, predInstructions.size() - 1); 155 edgeInstructionSeqences.add(seq); 156 } 157 158 // process lir-instructions while all predecessors end with the same instruction 159 while (true) { 160 List<LIRInstruction> seq = edgeInstructionSeqences.get(0); 161 if (seq.isEmpty()) { 162 return; 163 } 164 165 LIRInstruction op = last(seq); 166 for (int i = 1; i < numPreds; ++i) { 167 List<LIRInstruction> otherSeq = edgeInstructionSeqences.get(i); 168 if (otherSeq.isEmpty() || !same(op, last(otherSeq))) { 169 return; 170 } 171 } 172 173 // insert the instruction at the beginning of the current block 174 ir.getLIRforBlock(block).add(1, op); 175 176 // delete the instruction at the end of all predecessors 177 for (int i = 0; i < numPreds; i++) { 178 seq = edgeInstructionSeqences.get(i); 179 removeLast(seq); 180 } 181 } 182 } 183 184 /** 185 * Moves the longest {@linkplain #same common} subsequence at the start of all successors of 186 * {@code block} to the end of {@code block} just prior to the branch instruction ending 187 * {@code block}. 188 */ 189 private void optimizeMovesAtBlockBegin(AbstractBlockBase<?> block) { 190 191 edgeInstructionSeqences.clear(); 192 int numSux = block.getSuccessorCount(); 193 194 List<LIRInstruction> instructions = ir.getLIRforBlock(block); 195 196 assert numSux == 2 : "method should not be called otherwise"; 197 198 LIRInstruction lastInstruction = instructions.get(instructions.size() - 1); 199 if (lastInstruction.hasState()) { 200 // cannot optimize instructions when debug info is needed 201 return; 202 } 203 204 LIRInstruction branch = lastInstruction; 205 if (!(branch instanceof StandardOp.BranchOp) || branch.hasOperands()) { 206 // Only blocks that end with a conditional branch are optimized. 207 // In addition, a conditional branch with operands (including state) cannot 208 // be optimized. Moving a successor instruction before such a branch may 209 // interfere with the operands of the branch. For example, a successive move 210 // instruction may redefine an input operand of the branch. 211 return; 212 } 213 214 // Now it is guaranteed that the block ends with a conditional branch. 215 // The instructions are inserted at the end of the block before the branch. 216 int insertIdx = instructions.size() - 1; 217 218 // setup a list with the lir-instructions of all successors 219 for (AbstractBlockBase<?> sux : block.getSuccessors()) { 220 List<LIRInstruction> suxInstructions = ir.getLIRforBlock(sux); 221 222 assert suxInstructions.get(0) instanceof StandardOp.LabelOp : "block must start with label"; 223 224 if (sux.getPredecessorCount() != 1) { 225 // this can happen with switch-statements where multiple edges are between 226 // the same blocks. 227 return; 228 } 229 assert sux.getPredecessors()[0] == block : "invalid control flow"; 230 231 // ignore the label at the beginning of the block 232 List<LIRInstruction> seq = suxInstructions.subList(1, suxInstructions.size()); 233 edgeInstructionSeqences.add(seq); 234 } 235 236 // process LIR instructions while all successors begin with the same instruction 237 while (true) { 238 List<LIRInstruction> seq = edgeInstructionSeqences.get(0); 239 if (seq.isEmpty()) { 240 return; 241 } 242 243 LIRInstruction op = first(seq); 244 for (int i = 1; i < numSux; i++) { 245 List<LIRInstruction> otherSeq = edgeInstructionSeqences.get(i); 246 if (otherSeq.isEmpty() || !same(op, first(otherSeq))) { 247 // these instructions are different and cannot be optimized . 248 // no further optimization possible 249 return; 250 } 251 } 252 253 // insert instruction at end of current block 254 ir.getLIRforBlock(block).add(insertIdx, op); 255 insertIdx++; 256 257 // delete the instructions at the beginning of all successors 258 for (int i = 0; i < numSux; i++) { 259 seq = edgeInstructionSeqences.get(i); 260 removeFirst(seq); 261 } 262 } 263 } 264 265 /** 266 * Gets the first element from a LIR instruction sequence. 267 */ 268 private static LIRInstruction first(List<LIRInstruction> seq) { 269 return seq.get(0); 270 } 271 272 /** 273 * Gets the last element from a LIR instruction sequence. 274 */ 275 private static LIRInstruction last(List<LIRInstruction> seq) { 276 return seq.get(seq.size() - 1); 277 } 278 279 /** 280 * Removes the first element from a LIR instruction sequence. 281 */ 282 private static void removeFirst(List<LIRInstruction> seq) { 283 seq.remove(0); 284 } 285 286 /** 287 * Removes the last element from a LIR instruction sequence. 288 */ 289 private static void removeLast(List<LIRInstruction> seq) { 290 seq.remove(seq.size() - 1); 291 } 292 293 } 294 }