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