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
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) {
|
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.CounterKey;
36 import org.graalvm.compiler.debug.DebugContext;
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.EconomicMap;
46 import org.graalvm.util.Equivalence;
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 CounterKey deletedMoves = DebugContext.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
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 DebugContext debug = lir.getDebug();
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 DebugContext debug = lir.getDebug();
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 DebugContext debug = lir.getDebug();
226 try (Indent indent = debug.logAndIndent("solve data flow")) {
227
228 AbstractBlockBase<?>[] blocks = lir.linearScanOrder();
229
230 int numIter = 0;
231
232 /*
233 * Iterate until there are no more changes.
234 */
235 int currentValueNum = 1;
236 boolean firstRound = true;
237 boolean changed;
238 do {
239 changed = false;
240 try (Indent indent2 = debug.logAndIndent("new iteration")) {
241
242 for (AbstractBlockBase<?> block : blocks) {
243
244 BlockData data = blockData.get(block);
245 /*
246 * Initialize the number for global value numbering for this block. It
247 * is essential that the starting number for a block is consistent at
248 * all iterations and also in eliminateMoves().
249 */
250 if (firstRound) {
251 data.entryValueNum = currentValueNum;
252 }
253 int valueNum = data.entryValueNum;
254 assert valueNum > 0;
255 boolean newState = false;
256
257 if (block == blocks[0] || block.isExceptionEntry()) {
258 /*
259 * The entry block has undefined values. And also exception handler
260 * blocks: the LinearScan can insert moves at the end of an
261 * exception handler predecessor block (after the invoke, which
262 * throws the exception), and in reality such moves are not in the
263 * control flow in case of an exception. So we assume a save default
264 * for exception handler blocks.
265 */
266 debug.log("kill all values at entry of block %d", block.getId());
267 clearValues(data.entryState, valueNum);
268 } else {
269 /*
270 * Merge the states of predecessor blocks
271 */
272 for (AbstractBlockBase<?> predecessor : block.getPredecessors()) {
273 BlockData predData = blockData.get(predecessor);
274 newState |= mergeState(data.entryState, predData.exitState, valueNum);
275 }
276 }
277 // Advance by the value numbers which are "consumed" by
278 // clearValues and mergeState
279 valueNum += data.entryState.length;
280
281 if (newState || firstRound) {
282 try (Indent indent3 = debug.logAndIndent("update block %d", block.getId())) {
283
284 /*
285 * Derive the exit state from the entry state by iterating
286 * through all instructions of the block.
287 */
288 int[] iterState = data.exitState;
289 copyState(iterState, data.entryState);
290 ArrayList<LIRInstruction> instructions = lir.getLIRforBlock(block);
291
292 for (LIRInstruction op : instructions) {
293 valueNum = updateState(debug, iterState, op, valueNum);
294 }
295 changed = true;
296 }
297 }
298 if (firstRound) {
299 currentValueNum = valueNum;
300 }
301 }
302 firstRound = false;
303 }
304 numIter++;
305
306 if (numIter > 5) {
307 /*
308 * This is _very_ seldom.
309 */
310 return false;
311 }
312
313 } while (changed);
314
315 }
316
317 return true;
318 }
319
320 /**
321 * Deletes all move instructions where the target location already contains the source
322 * value.
323 */
324 @SuppressWarnings("try")
325 private void eliminateMoves(LIR lir) {
326 DebugContext debug = lir.getDebug();
327
328 try (Indent indent = debug.logAndIndent("eliminate moves")) {
329
330 AbstractBlockBase<?>[] blocks = lir.linearScanOrder();
331
332 for (AbstractBlockBase<?> block : blocks) {
333
334 try (Indent indent2 = debug.logAndIndent("eliminate moves in block %d", block.getId())) {
335
336 ArrayList<LIRInstruction> instructions = lir.getLIRforBlock(block);
337 BlockData data = blockData.get(block);
338 boolean hasDead = false;
339
340 // Reuse the entry state for iteration, we don't need it later.
341 int[] iterState = data.entryState;
342
343 // Add the values which are "consumed" by clearValues and
344 // mergeState in solveDataFlow
345 int valueNum = data.entryValueNum + data.entryState.length;
346
347 int numInsts = instructions.size();
348 for (int idx = 0; idx < numInsts; idx++) {
349 LIRInstruction op = instructions.get(idx);
350 if (isEligibleMove(op)) {
351 ValueMoveOp moveOp = ValueMoveOp.asValueMoveOp(op);
352 int sourceIdx = getStateIdx(moveOp.getInput());
353 int destIdx = getStateIdx(moveOp.getResult());
354 if (sourceIdx >= 0 && destIdx >= 0 && iterState[sourceIdx] == iterState[destIdx]) {
355 assert iterState[sourceIdx] != INIT_VALUE;
356 debug.log("delete move %s", op);
357 instructions.set(idx, null);
358 hasDead = true;
359 deletedMoves.increment(debug);
360 }
361 }
362 // It doesn't harm if updateState is also called for a deleted move
363 valueNum = updateState(debug, 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(DebugContext debug, 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) {
|