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.Debug;
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
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 try (Indent indent = Debug.logAndIndent("Eliminating unnecessary spill moves")) {
94
95 /*
96 * collect all intervals that must be stored after their definition. The list is sorted
97 * by Interval.spillDefinitionPos.
98 */
99 Interval interval;
100 interval = allocator.createUnhandledLists(mustStoreAtDefinition, null).getLeft();
101 if (DetailedAsserts.getValue(allocator.getOptions())) {
102 checkIntervals(interval);
103 }
104
105 LIRInsertionBuffer insertionBuffer = new LIRInsertionBuffer();
106 for (AbstractBlockBase<?> block : allocator.sortedBlocks()) {
107 try (Indent indent1 = Debug.logAndIndent("Handle %s", block)) {
108 ArrayList<LIRInstruction> instructions = allocator.getLIR().getLIRforBlock(block);
109 int numInst = instructions.size();
110
111 // iterate all instructions of the block.
112 for (int j = firstInstructionOfInterest(); j < numInst; j++) {
113 LIRInstruction op = instructions.get(j);
114 int opId = op.id();
115
116 if (opId == -1) {
117 MoveOp move = MoveOp.asMoveOp(op);
118 /*
119 * Remove move from register to stack if the stack slot is guaranteed to
120 * be correct. Only moves that have been inserted by LinearScan can be
121 * removed.
122 */
123 if (Options.LIROptLSRAEliminateSpillMoves.getValue(allocator.getOptions()) && canEliminateSpillMove(block, move)) {
124 /*
125 * Move target is a stack slot that is always correct, so eliminate
126 * instruction.
127 */
128 if (Debug.isLogEnabled()) {
129 if (ValueMoveOp.isValueMoveOp(op)) {
130 ValueMoveOp vmove = ValueMoveOp.asValueMoveOp(op);
131 Debug.log("eliminating move from interval %d (%s) to %d (%s) in block %s", allocator.operandNumber(vmove.getInput()), vmove.getInput(),
132 allocator.operandNumber(vmove.getResult()), vmove.getResult(), block);
133 } else {
134 LoadConstantOp load = LoadConstantOp.asLoadConstantOp(op);
135 Debug.log("eliminating constant load from %s to %d (%s) in block %s", load.getConstant(), allocator.operandNumber(load.getResult()), load.getResult(), block);
136 }
137 }
138
139 // null-instructions are deleted by assignRegNum
140 instructions.set(j, null);
141 }
142
143 } else {
144 /*
145 * Insert move from register to stack just after the beginning of the
146 * interval.
147 */
148 assert interval.isEndMarker() || interval.spillDefinitionPos() >= opId : "invalid order";
149 assert interval.isEndMarker() || (interval.isSplitParent() && interval.spillState() == SpillState.StoreAtDefinition) : "invalid interval";
150
151 while (!interval.isEndMarker() && interval.spillDefinitionPos() == opId) {
152 if (!interval.canMaterialize()) {
153 if (!insertionBuffer.initialized()) {
154 /*
155 * prepare insertion buffer (appended when all instructions
156 * in the block are processed)
157 */
158 insertionBuffer.init(instructions);
159 }
160
161 AllocatableValue fromLocation = interval.location();
162 AllocatableValue toLocation = LinearScan.canonicalSpillOpr(interval);
163 if (!fromLocation.equals(toLocation)) {
164
165 assert isRegister(fromLocation) : "from operand must be a register but is: " + fromLocation + " toLocation=" + toLocation + " spillState=" +
166 interval.spillState();
167 assert isStackSlotValue(toLocation) : "to operand must be a stack slot";
168
169 LIRInstruction move = allocator.getSpillMoveFactory().createMove(toLocation, fromLocation);
170 insertionBuffer.append(j + 1, move);
171 move.setComment(res, "LSRAEliminateSpillMove: store at definition");
172
173 if (Debug.isLogEnabled()) {
174 Debug.log("inserting move after definition of interval %d to stack slot %s at opId %d", interval.operandNumber, interval.spillSlot(), opId);
175 }
176 }
177 }
178 interval = interval.next;
179 }
180 }
181 } // end of instruction iteration
182
183 if (insertionBuffer.initialized()) {
184 insertionBuffer.finish();
185 }
186 }
187 } // end of block iteration
188
189 assert interval.isEndMarker() : "missed an interval";
190 }
191 }
192
193 /**
194 * @param block The block {@code move} is located in.
195 * @param move Spill move.
196 */
197 protected boolean canEliminateSpillMove(AbstractBlockBase<?> block, MoveOp move) {
198 assert isVariable(move.getResult()) : "LinearScan inserts only moves to variables: " + move;
199
200 Interval curInterval = allocator.intervalFor(move.getResult());
201
202 if (!isRegister(curInterval.location()) && curInterval.alwaysInMemory()) {
203 assert isStackSlotValue(curInterval.location()) : "Not a stack slot: " + curInterval.location();
204 return true;
205 }
206 return false;
207 }
208
209 private static void checkIntervals(Interval interval) {
210 Interval prev = null;
211 Interval temp = interval;
212 while (!temp.isEndMarker()) {
213 assert temp.spillDefinitionPos() > 0 : "invalid spill definition pos";
214 if (prev != null) {
215 assert temp.from() >= prev.from() : "intervals not sorted";
216 assert temp.spillDefinitionPos() >= prev.spillDefinitionPos() : "when intervals are sorted by from : then they must also be sorted by spillDefinitionPos";
217 }
218
219 assert temp.spillSlot() != null || temp.canMaterialize() : "interval has no spill slot assigned";
220 assert temp.spillDefinitionPos() >= temp.from() : "invalid order";
221 assert temp.spillDefinitionPos() <= temp.from() + 2 : "only intervals defined once at their start-pos can be optimized";
222
223 if (Debug.isLogEnabled()) {
224 Debug.log("interval %d (from %d to %d) must be stored at %d", temp.operandNumber, temp.from(), temp.to(), temp.spillDefinitionPos());
225 }
226
227 prev = temp;
228 temp = temp.next;
229 }
230 }
231
232 }
|
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
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 }
|