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.Arrays;
29 import java.util.Collections;
30 import java.util.EnumSet;
31 import java.util.List;
32 import java.util.Map;
33
34 import org.graalvm.compiler.core.common.CollectionsFactory;
35 import org.graalvm.compiler.core.common.LIRKind;
36 import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
37 import org.graalvm.compiler.debug.Debug;
38 import org.graalvm.compiler.debug.DebugCounter;
39 import org.graalvm.compiler.debug.Indent;
40 import org.graalvm.compiler.lir.LIRInstruction.OperandFlag;
41 import org.graalvm.compiler.lir.LIRInstruction.OperandMode;
42 import org.graalvm.compiler.lir.StandardOp.MoveOp;
43 import org.graalvm.compiler.lir.StandardOp.ValueMoveOp;
44 import org.graalvm.compiler.lir.framemap.FrameMap;
45 import org.graalvm.compiler.lir.gen.LIRGenerationResult;
46 import org.graalvm.compiler.lir.phases.PostAllocationOptimizationPhase;
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 }
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 Map<AbstractBlockBase<?>, BlockData> blockData = CollectionsFactory.newMap();
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 Map<Integer, Integer> stackIndices = CollectionsFactory.newMap();
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
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 List<LIRInstruction> instructions = lir.getLIRforBlock(block);
183 for (LIRInstruction op : instructions) {
184 if (isEligibleMove(op)) {
185 Value dest = ((MoveOp) 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 /*
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 List<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;
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 List<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) 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);
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 (final 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) 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";
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 /*
|
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 }
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
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) 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 /*
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;
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) 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);
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 (final 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) 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 /*
|