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 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 }
67
68 /**
69 * Holds the entry and exit states for each block for dataflow analysis. The state is an array
70 * with an element for each relevant location (register or stack slot). Each element holds the
71 * global number of the location's definition. A location definition is simply an output of an
72 * instruction. Note that because instructions can have multiple outputs it is not possible to
73 * use the instruction id for value numbering. In addition, the result of merging at block
74 * entries (= phi values) get unique value numbers.
75 *
76 * The value numbers also contain information if it is an object kind value or not: if the
77 * number is negative it is an object kind value.
78 */
79 private static final class BlockData {
80
81 BlockData(int stateSize) {
82 entryState = new int[stateSize];
83 exitState = new int[stateSize];
84 }
85
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
140 try (Indent indent = Debug.logAndIndent("eliminate redundant moves")) {
141
142 callerSaveRegs = frameMap.getRegisterConfig().getCallerSaveRegisters();
143
144 initBlockData(lir);
145
146 // Compute a table of the registers which are eligible for move optimization.
147 // Unallocatable registers should never be optimized.
148 eligibleRegs = new int[numRegs];
149 Arrays.fill(eligibleRegs, -1);
150 for (Register reg : frameMap.getRegisterConfig().getAllocatableRegisters()) {
151 if (reg.number < numRegs) {
152 eligibleRegs[reg.number] = reg.number;
153 }
154 }
155
156 if (!solveDataFlow(lir)) {
157 return;
158 }
159
160 eliminateMoves(lir);
161 }
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.asMoveOp(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 /*
203 * Now we know the number of locations to optimize, so we can allocate the block states.
204 */
205 int numLocations = numRegs + stackIndices.size();
206 Debug.log("num locations = %d (regs = %d, stack = %d)", numLocations, numRegs, stackIndices.size());
207 for (AbstractBlockBase<?> block : blocks) {
208 BlockData data = new BlockData(numLocations);
209 blockData.put(block, data);
210 }
211 }
212
213 private int getOffset(StackSlot stackSlot) {
214 return stackSlot.getOffset(frameMap.totalFrameSize());
215 }
216
217 /**
218 * Calculates the entry and exit states for all basic blocks.
219 *
220 * @return Returns true on success and false if the control flow is too complex.
221 */
222 @SuppressWarnings("try")
223 private boolean solveDataFlow(LIR lir) {
224
225 try (Indent indent = Debug.logAndIndent("solve data flow")) {
226
227 AbstractBlockBase<?>[] blocks = lir.linearScanOrder();
228
229 int numIter = 0;
230
231 /*
232 * Iterate until there are no more changes.
233 */
234 int currentValueNum = 1;
235 boolean firstRound = true;
236 boolean changed;
237 do {
238 changed = false;
239 try (Indent indent2 = Debug.logAndIndent("new iteration")) {
240
241 for (AbstractBlockBase<?> block : blocks) {
242
243 BlockData data = blockData.get(block);
244 /*
245 * Initialize the number for global value numbering for this block. It
246 * is essential that the starting number for a block is consistent at
247 * all iterations and also in eliminateMoves().
248 */
249 if (firstRound) {
250 data.entryValueNum = currentValueNum;
251 }
252 int valueNum = data.entryValueNum;
253 assert valueNum > 0;
254 boolean newState = false;
255
256 if (block == blocks[0] || block.isExceptionEntry()) {
257 /*
258 * The entry block has undefined values. And also exception handler
259 * blocks: the LinearScan can insert moves at the end of an
260 * exception handler predecessor block (after the invoke, which
261 * throws the exception), and in reality such moves are not in the
262 * control flow in case of an exception. So we assume a save default
263 * for exception handler blocks.
264 */
265 Debug.log("kill all values at entry of block %d", block.getId());
266 clearValues(data.entryState, valueNum);
267 } else {
268 /*
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;
310 }
311
312 } while (changed);
313
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.asValueMoveOp(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);
355 instructions.set(idx, null);
356 hasDead = true;
357 if (deletedMoves.isEnabled()) {
358 deletedMoves.increment();
359 }
360 }
361 }
362 // It doesn't harm if updateState is also called for a deleted move
363 valueNum = updateState(iterState, op, valueNum);
364 }
365 if (hasDead) {
366 instructions.removeAll(Collections.singleton(null));
367 }
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 (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.asValueMoveOp(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 /*
409 * Value procedure for the instruction's output and temp values
410 */
411 class OutputValueConsumer implements ValueConsumer {
412
413 int opValueNum;
414
415 OutputValueConsumer(int opValueNum) {
416 this.opValueNum = opValueNum;
417 }
418
419 @Override
420 public void visitValue(Value operand, OperandMode mode, EnumSet<OperandFlag> flags) {
421 int stateIdx = getStateIdx(operand);
422 if (stateIdx >= 0) {
423 /*
424 * Assign a unique number to the output or temp location.
425 */
426 state[stateIdx] = encodeValueNum(opValueNum++, !LIRKind.isValue(operand));
427 Debug.log("set def %d for register %s(%d): %d", opValueNum, operand, stateIdx, state[stateIdx]);
428 }
429 }
430 }
431
432 OutputValueConsumer outputValueConsumer = new OutputValueConsumer(valueNum);
433
434 op.visitEachTemp(outputValueConsumer);
435 /*
436 * Semantically the output values are written _after_ the temp values
437 */
438 op.visitEachOutput(outputValueConsumer);
439
440 valueNum = outputValueConsumer.opValueNum;
441
442 if (op.hasState()) {
443 /*
444 * All instructions with framestates (mostly method calls), may do garbage
445 * collection. GC will rewrite all object references which are live at this
446 * point. So we can't rely on their values. It would be sufficient to just kill
447 * all values which are referenced in the state (or all values which are not),
448 * but for simplicity we kill all values.
449 */
450 Debug.log("kill all object values");
451 clearValuesOfKindObject(state, valueNum);
452 valueNum += state.length;
453 }
454
455 return valueNum;
456 }
457 }
458
459 /**
460 * The state merge function for dataflow joins.
461 */
462 private static boolean mergeState(int[] dest, int[] source, int defNum) {
463 assert dest.length == source.length;
464 boolean changed = false;
465 for (int idx = 0; idx < source.length; idx++) {
466 int phiNum = defNum + idx;
467 int dst = dest[idx];
468 int src = source[idx];
469 if (dst != src && src != INIT_VALUE && dst != encodeValueNum(phiNum, isObjectValue(dst))) {
470 if (dst != INIT_VALUE) {
471 dst = encodeValueNum(phiNum, isObjectValue(dst) || isObjectValue(src));
472 } else {
473 dst = src;
474 }
475 dest[idx] = dst;
476 changed = true;
477 }
478 }
479 return changed;
480 }
481
482 private static void copyState(int[] dest, int[] source) {
483 assert dest.length == source.length;
484 for (int idx = 0; idx < source.length; idx++) {
485 dest[idx] = source[idx];
486 }
487 }
488
489 private static void clearValues(int[] state, int defNum) {
490 for (int idx = 0; idx < state.length; idx++) {
491 int phiNum = defNum + idx;
492 // Let the killed values assume to be object references: it's the save default.
493 state[idx] = encodeValueNum(phiNum, true);
494 }
495 }
496
497 private static void clearValuesOfKindObject(int[] state, int defNum) {
498 for (int idx = 0; idx < state.length; idx++) {
499 int phiNum = defNum + idx;
500 if (isObjectValue(state[idx])) {
501 state[idx] = encodeValueNum(phiNum, true);
502 }
503 }
504 }
505
506 /**
507 * Returns the index to the state arrays in BlockData for a specific location.
508 */
509 private int getStateIdx(Value location) {
510 if (isRegister(location)) {
511 int regNum = ((RegisterValue) location).getRegister().number;
512 if (regNum < numRegs) {
513 return eligibleRegs[regNum];
514 }
515 return -1;
516 }
517 if (isStackSlot(location)) {
518 StackSlot slot = (StackSlot) location;
519 Integer index = stackIndices.get(getOffset(slot));
520 if (index != null) {
521 return index.intValue() + numRegs;
522 }
523 }
524 return -1;
525 }
526
527 /**
528 * Encodes a value number + the is-object information to a number to be stored in a state.
529 */
530 private static int encodeValueNum(int valueNum, boolean isObjectKind) {
531 assert valueNum > 0;
532 if (isObjectKind) {
533 return -valueNum;
534 }
535 return valueNum;
536 }
537
538 /**
539 * Returns true if an encoded value number (which is stored in a state) refers to an object
540 * reference.
541 */
542 private static boolean isObjectValue(int encodedValueNum) {
543 return encodedValueNum < 0;
544 }
545
546 /**
547 * Returns true for a move instruction which is a candidate for elimination.
548 */
549 private static boolean isEligibleMove(LIRInstruction op) {
550 if (ValueMoveOp.isValueMoveOp(op)) {
551 ValueMoveOp moveOp = ValueMoveOp.asValueMoveOp(op);
552 Value source = moveOp.getInput();
553 Value dest = moveOp.getResult();
554 /*
555 * Moves with mismatching kinds are not moves, but memory loads/stores!
556 */
557 return source.getValueKind().equals(dest.getValueKind());
558 }
559 return false;
560 }
561 }
562 }