1 /* 2 * Copyright (c) 2015, 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.alloc.lsra; 24 25 import static jdk.vm.ci.code.ValueUtil.isRegister; 26 import static org.graalvm.compiler.core.common.GraalOptions.DetailedAsserts; 27 import static org.graalvm.compiler.lir.LIRValueUtil.isStackSlotValue; 28 import static org.graalvm.compiler.lir.LIRValueUtil.isVariable; 29 import static org.graalvm.compiler.lir.phases.LIRPhase.Options.LIROptimization; 30 31 import java.util.ArrayList; 32 33 import org.graalvm.compiler.core.common.cfg.AbstractBlockBase; 34 import org.graalvm.compiler.debug.DebugContext; 35 import org.graalvm.compiler.debug.Indent; 36 import org.graalvm.compiler.lir.LIRInsertionBuffer; 37 import org.graalvm.compiler.lir.LIRInstruction; 38 import org.graalvm.compiler.lir.StandardOp.LoadConstantOp; 39 import org.graalvm.compiler.lir.StandardOp.MoveOp; 40 import org.graalvm.compiler.lir.StandardOp.ValueMoveOp; 41 import org.graalvm.compiler.lir.alloc.lsra.Interval.SpillState; 42 import org.graalvm.compiler.lir.alloc.lsra.LinearScan.IntervalPredicate; 43 import org.graalvm.compiler.lir.gen.LIRGenerationResult; 44 import org.graalvm.compiler.lir.phases.AllocationPhase.AllocationContext; 45 import org.graalvm.compiler.options.NestedBooleanOptionKey; 46 import org.graalvm.compiler.options.Option; 47 import org.graalvm.compiler.options.OptionKey; 48 import org.graalvm.compiler.options.OptionType; 49 50 import jdk.vm.ci.code.TargetDescription; 51 import jdk.vm.ci.meta.AllocatableValue; 52 53 public class LinearScanEliminateSpillMovePhase extends LinearScanAllocationPhase { 54 55 public static class Options { 56 // @formatter:off 57 @Option(help = "Enable spill move elimination.", type = OptionType.Debug) 58 public static final OptionKey<Boolean> LIROptLSRAEliminateSpillMoves = new NestedBooleanOptionKey(LIROptimization, true); 59 // @formatter:on 60 } 61 62 private static final IntervalPredicate mustStoreAtDefinition = new LinearScan.IntervalPredicate() { 63 64 @Override 65 public boolean apply(Interval i) { 66 return i.isSplitParent() && i.spillState() == SpillState.StoreAtDefinition; 67 } 68 }; 69 70 protected final LinearScan allocator; 71 72 protected LinearScanEliminateSpillMovePhase(LinearScan allocator) { 73 this.allocator = allocator; 74 } 75 76 @Override 77 protected void run(TargetDescription target, LIRGenerationResult lirGenRes, AllocationContext context) { 78 eliminateSpillMoves(lirGenRes); 79 } 80 81 /** 82 * @return the index of the first instruction that is of interest for 83 * {@link #eliminateSpillMoves} 84 */ 85 protected int firstInstructionOfInterest() { 86 // skip the first because it is always a label 87 return 1; 88 } 89 90 // called once before assignment of register numbers 91 @SuppressWarnings("try") 92 void eliminateSpillMoves(LIRGenerationResult res) { 93 DebugContext debug = allocator.getDebug(); 94 try (Indent indent = debug.logAndIndent("Eliminating unnecessary spill moves")) { 95 96 /* 97 * collect all intervals that must be stored after their definition. The list is sorted 98 * by Interval.spillDefinitionPos. 99 */ 100 Interval interval; 101 interval = allocator.createUnhandledLists(mustStoreAtDefinition, null).getLeft(); 102 if (DetailedAsserts.getValue(allocator.getOptions())) { 103 checkIntervals(debug, interval); 104 } 105 106 LIRInsertionBuffer insertionBuffer = new LIRInsertionBuffer(); 107 for (AbstractBlockBase<?> block : allocator.sortedBlocks()) { 108 try (Indent indent1 = debug.logAndIndent("Handle %s", block)) { 109 ArrayList<LIRInstruction> instructions = allocator.getLIR().getLIRforBlock(block); 110 int numInst = instructions.size(); 111 112 // iterate all instructions of the block. 113 for (int j = firstInstructionOfInterest(); j < numInst; j++) { 114 LIRInstruction op = instructions.get(j); 115 int opId = op.id(); 116 117 if (opId == -1) { 118 MoveOp move = MoveOp.asMoveOp(op); 119 /* 120 * Remove move from register to stack if the stack slot is guaranteed to 121 * be correct. Only moves that have been inserted by LinearScan can be 122 * removed. 123 */ 124 if (Options.LIROptLSRAEliminateSpillMoves.getValue(allocator.getOptions()) && canEliminateSpillMove(block, move)) { 125 /* 126 * Move target is a stack slot that is always correct, so eliminate 127 * instruction. 128 */ 129 if (debug.isLogEnabled()) { 130 if (ValueMoveOp.isValueMoveOp(op)) { 131 ValueMoveOp vmove = ValueMoveOp.asValueMoveOp(op); 132 debug.log("eliminating move from interval %d (%s) to %d (%s) in block %s", allocator.operandNumber(vmove.getInput()), vmove.getInput(), 133 allocator.operandNumber(vmove.getResult()), vmove.getResult(), block); 134 } else { 135 LoadConstantOp load = LoadConstantOp.asLoadConstantOp(op); 136 debug.log("eliminating constant load from %s to %d (%s) in block %s", load.getConstant(), allocator.operandNumber(load.getResult()), load.getResult(), block); 137 } 138 } 139 140 // null-instructions are deleted by assignRegNum 141 instructions.set(j, null); 142 } 143 144 } else { 145 /* 146 * Insert move from register to stack just after the beginning of the 147 * interval. 148 */ 149 assert interval.isEndMarker() || interval.spillDefinitionPos() >= opId : "invalid order"; 150 assert interval.isEndMarker() || (interval.isSplitParent() && interval.spillState() == SpillState.StoreAtDefinition) : "invalid interval"; 151 152 while (!interval.isEndMarker() && interval.spillDefinitionPos() == opId) { 153 if (!interval.canMaterialize()) { 154 if (!insertionBuffer.initialized()) { 155 /* 156 * prepare insertion buffer (appended when all instructions 157 * in the block are processed) 158 */ 159 insertionBuffer.init(instructions); 160 } 161 162 AllocatableValue fromLocation = interval.location(); 163 AllocatableValue toLocation = LinearScan.canonicalSpillOpr(interval); 164 if (!fromLocation.equals(toLocation)) { 165 166 assert isRegister(fromLocation) : "from operand must be a register but is: " + fromLocation + " toLocation=" + toLocation + " spillState=" + 167 interval.spillState(); 168 assert isStackSlotValue(toLocation) : "to operand must be a stack slot"; 169 170 LIRInstruction move = allocator.getSpillMoveFactory().createMove(toLocation, fromLocation); 171 insertionBuffer.append(j + 1, move); 172 move.setComment(res, "LSRAEliminateSpillMove: store at definition"); 173 174 if (debug.isLogEnabled()) { 175 debug.log("inserting move after definition of interval %d to stack slot %s at opId %d", interval.operandNumber, interval.spillSlot(), opId); 176 } 177 } 178 } 179 interval = interval.next; 180 } 181 } 182 } // end of instruction iteration 183 184 if (insertionBuffer.initialized()) { 185 insertionBuffer.finish(); 186 } 187 } 188 } // end of block iteration 189 190 assert interval.isEndMarker() : "missed an interval"; 191 } 192 } 193 194 /** 195 * @param block The block {@code move} is located in. 196 * @param move Spill move. 197 */ 198 protected boolean canEliminateSpillMove(AbstractBlockBase<?> block, MoveOp move) { 199 assert isVariable(move.getResult()) : "LinearScan inserts only moves to variables: " + move; 200 201 Interval curInterval = allocator.intervalFor(move.getResult()); 202 203 if (!isRegister(curInterval.location()) && curInterval.alwaysInMemory()) { 204 assert isStackSlotValue(curInterval.location()) : "Not a stack slot: " + curInterval.location(); 205 return true; 206 } 207 return false; 208 } 209 210 private static void checkIntervals(DebugContext debug, Interval interval) { 211 Interval prev = null; 212 Interval temp = interval; 213 while (!temp.isEndMarker()) { 214 assert temp.spillDefinitionPos() > 0 : "invalid spill definition pos"; 215 if (prev != null) { 216 assert temp.from() >= prev.from() : "intervals not sorted"; 217 assert temp.spillDefinitionPos() >= prev.spillDefinitionPos() : "when intervals are sorted by from : then they must also be sorted by spillDefinitionPos"; 218 } 219 220 assert temp.spillSlot() != null || temp.canMaterialize() : "interval has no spill slot assigned"; 221 assert temp.spillDefinitionPos() >= temp.from() : "invalid order"; 222 assert temp.spillDefinitionPos() <= temp.from() + 2 : "only intervals defined once at their start-pos can be optimized"; 223 224 if (debug.isLogEnabled()) { 225 debug.log("interval %d (from %d to %d) must be stored at %d", temp.operandNumber, temp.from(), temp.to(), temp.spillDefinitionPos()); 226 } 227 228 prev = temp; 229 temp = temp.next; 230 } 231 } 232 233 }