Mercurial > hg > graal-compiler

annotate graal/com.oracle.graal.lir/src/com/oracle/graal/lir/RedundantMoveElimination.java @ 18443:1c92d437179b

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
FrameMapBuilder: move into package.
author Josef Eisl <josef.eisl@jku.at>
date Mon, 17 Nov 2014 16:41:44 +0100
parents 04b54406c292
children 220d7f242e57
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
13339
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
1 /*
16094
c0b8d395368b Introduce LIRKind to accurately track oop references in backend.
Roland Schatz <roland.schatz@oracle.com>
parents: 15192
diff changeset
2 * Copyright (c) 2013, 2014, Oracle and/or its affiliates. All rights reserved.
13339
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
4 *
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
5 * This code is free software; you can redistribute it and/or modify it
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
6 * under the terms of the GNU General Public License version 2 only, as
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
7 * published by the Free Software Foundation.
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
8 *
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
9 * This code is distributed in the hope that it will be useful, but WITHOUT
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
12 * version 2 for more details (a copy is included in the LICENSE file that
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
13 * accompanied this code).
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
14 *
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
15 * You should have received a copy of the GNU General Public License version
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
16 * 2 along with this work; if not, write to the Free Software Foundation,
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
18 *
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
20 * or visit www.oracle.com if you need additional information or have any
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
21 * questions.
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
22 */
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
23 package com.oracle.graal.lir;
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
24
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
25 import static com.oracle.graal.api.code.ValueUtil.*;
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
26
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
27 import java.util.*;
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
28
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
29 import com.oracle.graal.api.code.*;
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
30 import com.oracle.graal.api.meta.*;
15192
644dfe49c0f4 Move packages com.oracle.graal.cfg to com.oracle.graal.compiler.common.cfg.
Josef Eisl <josef.eisl@jku.at>
parents: 15157
diff changeset
31 import com.oracle.graal.compiler.common.cfg.*;
13339
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
32 import com.oracle.graal.debug.*;
14991
64dcb92ee75a Truffle: Change signature for Truffle calls from (PackedFrame, Arguments) to (Object[]).
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 14871
diff changeset
33 import com.oracle.graal.lir.LIRInstruction.OperandFlag;
64dcb92ee75a Truffle: Change signature for Truffle calls from (PackedFrame, Arguments) to (Object[]).
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 14871
diff changeset
34 import com.oracle.graal.lir.LIRInstruction.OperandMode;
13339
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
35 import com.oracle.graal.lir.StandardOp.MoveOp;
18443
1c92d437179b FrameMapBuilder: move into package.
Josef Eisl <josef.eisl@jku.at>
parents: 18152
diff changeset
36 import com.oracle.graal.lir.framemap.*;
13339
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
37
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
38 /**
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
39 * Removes move instructions, where the destination value is already in place.
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
40 */
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
41 public final class RedundantMoveElimination {
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
42
18152
04b54406c292 Use FrameMapBuilder in Backend.newLIRGenerationResult().
Josef Eisl <josef.eisl@jku.at>
parents: 18123
diff changeset
43 public static void optimize(LIR lir, FrameMapBuilder frameMapBuilder) {
13339
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
44 RedundantMoveElimination redundantMoveElimination = new RedundantMoveElimination();
18152
04b54406c292 Use FrameMapBuilder in Backend.newLIRGenerationResult().
Josef Eisl <josef.eisl@jku.at>
parents: 18123
diff changeset
45 redundantMoveElimination.doOptimize(lir, frameMapBuilder);
13339
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
46 }
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
47
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
48 /**
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
49 * Holds the entry and exit states for each block for dataflow analysis. The state is an array
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
50 * with an element for each relevant location (register or stack slot). Each element holds the
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
51 * global number of the location's definition. A location definition is simply an output of an
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
52 * instruction. Note that because instructions can have multiple outputs it is not possible to
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
53 * use the instruction id for value numbering. In addition, the result of merging at block
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
54 * entries (= phi values) get unique value numbers.
14871
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
55 *
13339
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
56 * The value numbers also contain information if it is an object kind value or not: if the
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
57 * number is negative it is an object kind value.
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
58 */
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
59 private static class BlockData {
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
60
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
61 BlockData(int stateSize) {
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
62 entryState = new int[stateSize];
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
63 exitState = new int[stateSize];
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
64 }
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
65
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
66 /*
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
67 * The state at block entry for global dataflow analysis. It contains a global value number
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
68 * for each location to optimize.
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
69 */
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
70 int[] entryState;
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
71
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
72 /*
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
73 * The state at block exit for global dataflow analysis. It contains a global value number
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
74 * for each location to optimize.
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
75 */
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
76 int[] exitState;
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
77
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
78 /*
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
79 * The starting number for global value numbering in this block.
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
80 */
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
81 int entryValueNum;
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
82 }
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
83
14786
a6595f1b55b0 Make LIR use AbstractBlock. (errors)
Josef Eisl <josef.eisl@jku.at>
parents: 14142
diff changeset
84 Map<AbstractBlock<?>, BlockData> blockData = new HashMap<>();
13339
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
85
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
86 Register[] callerSaveRegs;
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
87
13516
0b17dd482532 don't optimize moves involving unallocatable registers
Tom Rodriguez <tom.rodriguez@oracle.com>
parents: 13462
diff changeset
88 /**
0b17dd482532 don't optimize moves involving unallocatable registers
Tom Rodriguez <tom.rodriguez@oracle.com>
parents: 13462
diff changeset
89 * Contains the register number for registers which can be optimized and -1 for the others.
0b17dd482532 don't optimize moves involving unallocatable registers
Tom Rodriguez <tom.rodriguez@oracle.com>
parents: 13462
diff changeset
90 */
0b17dd482532 don't optimize moves involving unallocatable registers
Tom Rodriguez <tom.rodriguez@oracle.com>
parents: 13462
diff changeset
91 int[] eligibleRegs;
0b17dd482532 don't optimize moves involving unallocatable registers
Tom Rodriguez <tom.rodriguez@oracle.com>
parents: 13462
diff changeset
92
13339
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
93 Map<StackSlot, Integer> stackIndices = new HashMap<>();
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
94
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
95 int numRegs;
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
96
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
97 /*
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
98 * Pseudo value for a not yet assigned location.
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
99 */
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
100 static final int INIT_VALUE = 0;
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
101
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
102 /**
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
103 * The main method doing the elimination of redundant moves.
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
104 */
18152
04b54406c292 Use FrameMapBuilder in Backend.newLIRGenerationResult().
Josef Eisl <josef.eisl@jku.at>
parents: 18123
diff changeset
105 private void doOptimize(LIR lir, FrameMapBuilder frameMapBuilder) {
13339
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
106
14142
4eac66a9b87d Remove reference to graph in LIRGenerator.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 13516
diff changeset
107 try (Indent indent = Debug.logAndIndent("eliminate redundant moves")) {
13339
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
108
18152
04b54406c292 Use FrameMapBuilder in Backend.newLIRGenerationResult().
Josef Eisl <josef.eisl@jku.at>
parents: 18123
diff changeset
109 callerSaveRegs = frameMapBuilder.getRegisterConfig().getCallerSaveRegisters();
13339
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
110
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
111 initBlockData(lir);
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
112
13516
0b17dd482532 don't optimize moves involving unallocatable registers
Tom Rodriguez <tom.rodriguez@oracle.com>
parents: 13462
diff changeset
113 // Compute a table of the registers which are eligible for move optimization.
0b17dd482532 don't optimize moves involving unallocatable registers
Tom Rodriguez <tom.rodriguez@oracle.com>
parents: 13462
diff changeset
114 // Unallocatable registers should never be optimized.
0b17dd482532 don't optimize moves involving unallocatable registers
Tom Rodriguez <tom.rodriguez@oracle.com>
parents: 13462
diff changeset
115 eligibleRegs = new int[numRegs];
0b17dd482532 don't optimize moves involving unallocatable registers
Tom Rodriguez <tom.rodriguez@oracle.com>
parents: 13462
diff changeset
116 Arrays.fill(eligibleRegs, -1);
18152
04b54406c292 Use FrameMapBuilder in Backend.newLIRGenerationResult().
Josef Eisl <josef.eisl@jku.at>
parents: 18123
diff changeset
117 for (Register reg : frameMapBuilder.getRegisterConfig().getAllocatableRegisters()) {
13516
0b17dd482532 don't optimize moves involving unallocatable registers
Tom Rodriguez <tom.rodriguez@oracle.com>
parents: 13462
diff changeset
118 if (reg.number < numRegs) {
0b17dd482532 don't optimize moves involving unallocatable registers
Tom Rodriguez <tom.rodriguez@oracle.com>
parents: 13462
diff changeset
119 eligibleRegs[reg.number] = reg.number;
0b17dd482532 don't optimize moves involving unallocatable registers
Tom Rodriguez <tom.rodriguez@oracle.com>
parents: 13462
diff changeset
120 }
0b17dd482532 don't optimize moves involving unallocatable registers
Tom Rodriguez <tom.rodriguez@oracle.com>
parents: 13462
diff changeset
121 }
0b17dd482532 don't optimize moves involving unallocatable registers
Tom Rodriguez <tom.rodriguez@oracle.com>
parents: 13462
diff changeset
122
13462
5f54b8a68346 limit complexity of redundant move elimination
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13376
diff changeset
123 if (!solveDataFlow(lir)) {
5f54b8a68346 limit complexity of redundant move elimination
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13376
diff changeset
124 return;
5f54b8a68346 limit complexity of redundant move elimination
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13376
diff changeset
125 }
13339
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
126
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
127 eliminateMoves(lir);
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
128 }
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
129 }
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
130
13462
5f54b8a68346 limit complexity of redundant move elimination
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13376
diff changeset
131 /**
5f54b8a68346 limit complexity of redundant move elimination
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13376
diff changeset
132 * The maximum number of locations * blocks. This is a complexity limit for the inner loop in
5f54b8a68346 limit complexity of redundant move elimination
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13376
diff changeset
133 * {@link #mergeState} (assuming a small number of iterations in {@link #solveDataFlow}.
5f54b8a68346 limit complexity of redundant move elimination
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13376
diff changeset
134 */
5f54b8a68346 limit complexity of redundant move elimination
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13376
diff changeset
135 private static final int COMPLEXITY_LIMIT = 30000;
5f54b8a68346 limit complexity of redundant move elimination
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13376
diff changeset
136
13339
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
137 private void initBlockData(LIR lir) {
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
138
14786
a6595f1b55b0 Make LIR use AbstractBlock. (errors)
Josef Eisl <josef.eisl@jku.at>
parents: 14142
diff changeset
139 List<? extends AbstractBlock<?>> blocks = lir.linearScanOrder();
13339
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
140 numRegs = 0;
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
141
13462
5f54b8a68346 limit complexity of redundant move elimination
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13376
diff changeset
142 int maxStackLocations = COMPLEXITY_LIMIT / blocks.size();
5f54b8a68346 limit complexity of redundant move elimination
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13376
diff changeset
143
13339
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
144 /*
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
145 * Search for relevant locations which can be optimized. These are register or stack slots
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
146 * which occur as destinations of move instructions.
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
147 */
14786
a6595f1b55b0 Make LIR use AbstractBlock. (errors)
Josef Eisl <josef.eisl@jku.at>
parents: 14142
diff changeset
148 for (AbstractBlock<?> block : blocks) {
14806
a8723f1ff542 LIR renamed setter and getter functions.
Josef Eisl <josef.eisl@jku.at>
parents: 14786
diff changeset
149 List<LIRInstruction> instructions = lir.getLIRforBlock(block);
13339
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
150 for (LIRInstruction op : instructions) {
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
151 if (isEligibleMove(op)) {
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
152 Value dest = ((MoveOp) op).getResult();
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
153 if (isRegister(dest)) {
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
154 int regNum = ((RegisterValue) dest).getRegister().number;
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
155 if (regNum >= numRegs) {
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
156 numRegs = regNum + 1;
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
157 }
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
158 } else if (isStackSlot(dest)) {
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
159 StackSlot stackSlot = (StackSlot) dest;
13462
5f54b8a68346 limit complexity of redundant move elimination
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13376
diff changeset
160 if (!stackIndices.containsKey(stackSlot) && stackIndices.size() < maxStackLocations) {
13339
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
161 stackIndices.put(stackSlot, stackIndices.size());
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
162 }
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
163 }
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
164 }
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
165 }
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
166 }
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
167
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
168 /*
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
169 * Now we know the number of locations to optimize, so we can allocate the block states.
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
170 */
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
171 int numLocations = numRegs + stackIndices.size();
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
172 Debug.log("num locations = %d (regs = %d, stack = %d)", numLocations, numRegs, stackIndices.size());
14786
a6595f1b55b0 Make LIR use AbstractBlock. (errors)
Josef Eisl <josef.eisl@jku.at>
parents: 14142
diff changeset
173 for (AbstractBlock<?> block : blocks) {
13339
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
174 BlockData data = new BlockData(numLocations);
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
175 blockData.put(block, data);
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
176 }
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
177 }
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
178
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
179 /**
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
180 * Calculates the entry and exit states for all basic blocks.
14871
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
181 *
13462
5f54b8a68346 limit complexity of redundant move elimination
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13376
diff changeset
182 * @return Returns true on success and false if the the control flow is too complex.
13339
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
183 */
13462
5f54b8a68346 limit complexity of redundant move elimination
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13376
diff changeset
184 private boolean solveDataFlow(LIR lir) {
13339
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
185
14871
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
186 try (Indent indent = Debug.logAndIndent("solve data flow")) {
13339
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
187
14871
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
188 List<? extends AbstractBlock<?>> blocks = lir.linearScanOrder();
13339
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
189
14871
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
190 int numIter = 0;
13462
5f54b8a68346 limit complexity of redundant move elimination
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13376
diff changeset
191
14871
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
192 /*
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
193 * Iterate until there are no more changes.
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
194 */
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
195 int currentValueNum = 1;
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
196 boolean firstRound = true;
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
197 boolean changed;
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
198 do {
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
199 changed = false;
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
200 try (Indent indent2 = Debug.logAndIndent("new iteration")) {
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
201
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
202 for (AbstractBlock<?> block : blocks) {
13339
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
203
14871
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
204 BlockData data = blockData.get(block);
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
205 /*
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
206 * Initialize the number for global value numbering for this block. It is
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
207 * essential that the starting number for a block is consistent at all
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
208 * iterations and also in eliminateMoves().
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
209 */
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
210 if (firstRound) {
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
211 data.entryValueNum = currentValueNum;
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
212 }
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
213 int valueNum = data.entryValueNum;
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
214 assert valueNum > 0;
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
215 boolean newState = false;
13339
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
216
14871
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
217 if (block == blocks.get(0) || block.isExceptionEntry()) {
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
218 /*
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
219 * The entry block has undefined values. And also exception handler
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
220 * blocks: the LinearScan can insert moves at the end of an exception
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
221 * handler predecessor block (after the invoke, which throws the
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
222 * exception), and in reality such moves are not in the control flow in
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
223 * case of an exception. So we assume a save default for exception
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
224 * handler blocks.
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
225 */
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
226 Debug.log("kill all values at entry of block %d", block.getId());
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
227 clearValues(data.entryState, valueNum);
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
228 } else {
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
229 /*
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
230 * Merge the states of predecessor blocks
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
231 */
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
232 for (AbstractBlock<?> predecessor : block.getPredecessors()) {
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
233 BlockData predData = blockData.get(predecessor);
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
234 newState |= mergeState(data.entryState, predData.exitState, valueNum);
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
235 }
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
236 }
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
237 // Advance by the value numbers which are "consumed" by
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
238 // clearValues and mergeState
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
239 valueNum += data.entryState.length;
13339
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
240
14871
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
241 if (newState || firstRound) {
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
242 try (Indent indent3 = Debug.logAndIndent("update block %d", block.getId())) {
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
243
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
244 /*
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
245 * Derive the exit state from the entry state by iterating through
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
246 * all instructions of the block.
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
247 */
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
248 int[] iterState = data.exitState;
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
249 copyState(iterState, data.entryState);
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
250 List<LIRInstruction> instructions = lir.getLIRforBlock(block);
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
251
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
252 for (LIRInstruction op : instructions) {
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
253 valueNum = updateState(iterState, op, valueNum);
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
254 }
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
255 changed = true;
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
256 }
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
257 }
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
258 if (firstRound) {
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
259 currentValueNum = valueNum;
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
260 }
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
261 }
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
262 firstRound = false;
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
263 }
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
264 numIter++;
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
265
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
266 if (numIter > 5) {
13339
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
267 /*
14871
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
268 * This is _very_ seldom.
13339
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
269 */
14871
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
270 return false;
13339
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
271 }
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
272
14871
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
273 } while (changed);
13462
5f54b8a68346 limit complexity of redundant move elimination
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13376
diff changeset
274
14871
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
275 }
13462
5f54b8a68346 limit complexity of redundant move elimination
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13376
diff changeset
276
5f54b8a68346 limit complexity of redundant move elimination
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13376
diff changeset
277 return true;
13339
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
278 }
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
279
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
280 /**
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
281 * Deletes all move instructions where the target location already contains the source value.
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
282 */
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
283 private void eliminateMoves(LIR lir) {
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
284
14871
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
285 try (Indent indent = Debug.logAndIndent("eliminate moves")) {
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
286
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
287 List<? extends AbstractBlock<?>> blocks = lir.linearScanOrder();
13339
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
288
14871
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
289 for (AbstractBlock<?> block : blocks) {
13339
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
290
14871
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
291 try (Indent indent2 = Debug.logAndIndent("eliminate moves in block %d", block.getId())) {
13339
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
292
14871
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
293 List<LIRInstruction> instructions = lir.getLIRforBlock(block);
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
294 BlockData data = blockData.get(block);
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
295 boolean hasDead = false;
13339
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
296
14871
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
297 // Reuse the entry state for iteration, we don't need it later.
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
298 int[] iterState = data.entryState;
13339
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
299
14871
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
300 // Add the values which are "consumed" by clearValues and
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
301 // mergeState in solveDataFlow
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
302 int valueNum = data.entryValueNum + data.entryState.length;
13339
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
303
14871
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
304 int numInsts = instructions.size();
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
305 for (int idx = 0; idx < numInsts; idx++) {
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
306 LIRInstruction op = instructions.get(idx);
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
307 if (isEligibleMove(op)) {
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
308 MoveOp moveOp = (MoveOp) op;
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
309 int sourceIdx = getStateIdx(moveOp.getInput());
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
310 int destIdx = getStateIdx(moveOp.getResult());
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
311 if (sourceIdx >= 0 && destIdx >= 0 && iterState[sourceIdx] == iterState[destIdx]) {
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
312 assert iterState[sourceIdx] != INIT_VALUE;
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
313 Debug.log("delete move %s", op);
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
314 instructions.set(idx, null);
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
315 hasDead = true;
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
316 }
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
317 }
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
318 // It doesn't harm if updateState is also called for a deleted move
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
319 valueNum = updateState(iterState, op, valueNum);
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
320 }
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
321 if (hasDead) {
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
322 instructions.removeAll(Collections.singleton(null));
13339
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
323 }
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
324 }
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
325 }
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
326 }
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
327 }
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
328
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
329 /**
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
330 * Updates the state for one instruction.
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
331 */
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
332 private int updateState(final int[] state, LIRInstruction op, int initValueNum) {
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
333
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
334 try (final Indent indent = Debug.logAndIndent("update state for op %s, initial value num = %d", op, initValueNum)) {
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
335 if (isEligibleMove(op)) {
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
336 /*
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
337 * Handle the special case of a move instruction
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
338 */
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
339 MoveOp moveOp = (MoveOp) op;
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
340 int sourceIdx = getStateIdx(moveOp.getInput());
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
341 int destIdx = getStateIdx(moveOp.getResult());
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
342 if (sourceIdx >= 0 && destIdx >= 0) {
16115
9a595d3f9a2f Handle narrow oops in redundant move elimination.
Roland Schatz <roland.schatz@oracle.com>
parents: 16094
diff changeset
343 assert isObjectValue(state[sourceIdx]) || moveOp.getInput().getLIRKind().isValue() : "move op moves object but input is not defined as object";
13339
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
344 state[destIdx] = state[sourceIdx];
14871
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
345 Debug.log("move value %d from %d to %d", state[sourceIdx], sourceIdx, destIdx);
13339
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
346 return initValueNum;
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
347 }
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
348 }
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
349
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
350 int valueNum = initValueNum;
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
351
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
352 if (op.destroysCallerSavedRegisters()) {
14871
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
353 Debug.log("kill all caller save regs");
13339
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
354
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
355 for (Register reg : callerSaveRegs) {
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
356 if (reg.number < numRegs) {
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
357 // Kind.Object is the save default
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
358 state[reg.number] = encodeValueNum(valueNum++, true);
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
359 }
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
360 }
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
361 }
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
362
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
363 /*
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
364 * Value procedure for the instruction's output and temp values
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
365 */
17285
3a834111a632 Make [Instruction]ValueProcedure and [Instruction]ValueConsumer a FunctionalInterface.
Josef Eisl <josef.eisl@jku.at>
parents: 16806
diff changeset
366 class OutputValueConsumer implements ValueConsumer {
13339
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
367
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
368 int opValueNum;
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
369
16806
47bf3ec2ca61 Use ValueConsumer in RedundantMoveElimination.
Josef Eisl <josef.eisl@jku.at>
parents: 16796
diff changeset
370 OutputValueConsumer(int opValueNum) {
13339
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
371 this.opValueNum = opValueNum;
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
372 }
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
373
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
374 @Override
16806
47bf3ec2ca61 Use ValueConsumer in RedundantMoveElimination.
Josef Eisl <josef.eisl@jku.at>
parents: 16796
diff changeset
375 public void visitValue(Value operand, OperandMode mode, EnumSet<OperandFlag> flags) {
13339
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
376 int stateIdx = getStateIdx(operand);
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
377 if (stateIdx >= 0) {
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
378 /*
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
379 * Assign a unique number to the output or temp location.
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
380 */
16115
9a595d3f9a2f Handle narrow oops in redundant move elimination.
Roland Schatz <roland.schatz@oracle.com>
parents: 16094
diff changeset
381 state[stateIdx] = encodeValueNum(opValueNum++, !operand.getLIRKind().isValue());
14871
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
382 Debug.log("set def %d for register %s(%d): %d", opValueNum, operand, stateIdx, state[stateIdx]);
13339
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
383 }
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
384 }
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
385 }
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
386
16806
47bf3ec2ca61 Use ValueConsumer in RedundantMoveElimination.
Josef Eisl <josef.eisl@jku.at>
parents: 16796
diff changeset
387 OutputValueConsumer outputValueConsumer = new OutputValueConsumer(valueNum);
13376
24ae4e7ecf03 fixed wrong redundant move elimination after loop safepoints, re-enabled redundant move elimination
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13339
diff changeset
388
16806
47bf3ec2ca61 Use ValueConsumer in RedundantMoveElimination.
Josef Eisl <josef.eisl@jku.at>
parents: 16796
diff changeset
389 op.visitEachTemp(outputValueConsumer);
13376
24ae4e7ecf03 fixed wrong redundant move elimination after loop safepoints, re-enabled redundant move elimination
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13339
diff changeset
390 /*
24ae4e7ecf03 fixed wrong redundant move elimination after loop safepoints, re-enabled redundant move elimination
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13339
diff changeset
391 * Semantically the output values are written _after_ the temp values
24ae4e7ecf03 fixed wrong redundant move elimination after loop safepoints, re-enabled redundant move elimination
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13339
diff changeset
392 */
16806
47bf3ec2ca61 Use ValueConsumer in RedundantMoveElimination.
Josef Eisl <josef.eisl@jku.at>
parents: 16796
diff changeset
393 op.visitEachOutput(outputValueConsumer);
13376
24ae4e7ecf03 fixed wrong redundant move elimination after loop safepoints, re-enabled redundant move elimination
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13339
diff changeset
394
16806
47bf3ec2ca61 Use ValueConsumer in RedundantMoveElimination.
Josef Eisl <josef.eisl@jku.at>
parents: 16796
diff changeset
395 valueNum = outputValueConsumer.opValueNum;
13339
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
396
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
397 if (op.hasState()) {
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
398 /*
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
399 * All instructions with framestates (mostly method calls), may do garbage
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
400 * collection. GC will rewrite all object references which are live at this point.
14871
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
401 * So we can't rely on their values. It would be sufficient to just kill all values
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
402 * which are referenced in the state (or all values which are not), but for
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
403 * simplicity we kill all values.
13339
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
404 */
14871
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14806
diff changeset
405 Debug.log("kill all object values");
13339
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
406 clearValuesOfKindObject(state, valueNum);
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
407 valueNum += state.length;
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
408 }
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
409
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
410 return valueNum;
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
411 }
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
412 }
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
413
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
414 /**
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
415 * The state merge function for dataflow joins.
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
416 */
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
417 private static boolean mergeState(int[] dest, int[] source, int defNum) {
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
418 assert dest.length == source.length;
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
419 boolean changed = false;
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
420 for (int idx = 0; idx < source.length; idx++) {
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
421 int phiNum = defNum + idx;
13462
5f54b8a68346 limit complexity of redundant move elimination
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13376
diff changeset
422 int dst = dest[idx];
5f54b8a68346 limit complexity of redundant move elimination
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13376
diff changeset
423 int src = source[idx];
5f54b8a68346 limit complexity of redundant move elimination
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13376
diff changeset
424 if (dst != src && src != INIT_VALUE && dst != encodeValueNum(phiNum, isObjectValue(dst))) {
5f54b8a68346 limit complexity of redundant move elimination
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13376
diff changeset
425 if (dst != INIT_VALUE) {
5f54b8a68346 limit complexity of redundant move elimination
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13376
diff changeset
426 dst = encodeValueNum(phiNum, isObjectValue(dst) || isObjectValue(src));
13339
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
427 } else {
13462
5f54b8a68346 limit complexity of redundant move elimination
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13376
diff changeset
428 dst = src;
13339
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
429 }
13462
5f54b8a68346 limit complexity of redundant move elimination
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13376
diff changeset
430 dest[idx] = dst;
13339
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
431 changed = true;
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
432 }
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
433 }
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
434 return changed;
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
435 }
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
436
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
437 private static void copyState(int[] dest, int[] source) {
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
438 assert dest.length == source.length;
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
439 for (int idx = 0; idx < source.length; idx++) {
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
440 dest[idx] = source[idx];
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
441 }
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
442 }
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
443
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
444 private static void clearValues(int[] state, int defNum) {
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
445 for (int idx = 0; idx < state.length; idx++) {
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
446 int phiNum = defNum + idx;
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
447 // Let the killed values assume to be object references: it's the save default.
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
448 state[idx] = encodeValueNum(phiNum, true);
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
449 }
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
450 }
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
451
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
452 private static void clearValuesOfKindObject(int[] state, int defNum) {
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
453 for (int idx = 0; idx < state.length; idx++) {
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
454 int phiNum = defNum + idx;
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
455 if (isObjectValue(state[idx])) {
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
456 state[idx] = encodeValueNum(phiNum, true);
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
457 }
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
458 }
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
459 }
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
460
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
461 /**
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
462 * Returns the index to the state arrays in BlockData for a specific location.
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
463 */
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
464 private int getStateIdx(Value location) {
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
465 if (isRegister(location)) {
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
466 int regNum = ((RegisterValue) location).getRegister().number;
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
467 if (regNum < numRegs) {
13516
0b17dd482532 don't optimize moves involving unallocatable registers
Tom Rodriguez <tom.rodriguez@oracle.com>
parents: 13462
diff changeset
468 return eligibleRegs[regNum];
13339
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
469 }
13516
0b17dd482532 don't optimize moves involving unallocatable registers
Tom Rodriguez <tom.rodriguez@oracle.com>
parents: 13462
diff changeset
470 return -1;
13339
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
471 }
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
472 if (isStackSlot(location)) {
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
473 StackSlot slot = (StackSlot) location;
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
474 Integer index = stackIndices.get(slot);
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
475 if (index != null) {
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
476 return index.intValue() + numRegs;
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
477 }
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
478 }
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
479 return -1;
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
480 }
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
481
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
482 /**
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
483 * Encodes a value number + the is-object information to a number to be stored in a state.
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
484 */
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
485 private static int encodeValueNum(int valueNum, boolean isObjectKind) {
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
486 assert valueNum > 0;
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
487 if (isObjectKind) {
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
488 return -valueNum;
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
489 }
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
490 return valueNum;
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
491 }
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
492
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
493 /**
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
494 * Returns true if an encoded value number (which is stored in a state) refers to an object
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
495 * reference.
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
496 */
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
497 private static boolean isObjectValue(int encodedValueNum) {
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
498 return encodedValueNum < 0;
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
499 }
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
500
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
501 /**
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
502 * Returns true for a move instruction which is a candidate for elimination.
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
503 */
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
504 private static boolean isEligibleMove(LIRInstruction op) {
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
505 if (op instanceof MoveOp) {
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
506 MoveOp moveOp = (MoveOp) op;
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
507 Value source = moveOp.getInput();
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
508 Value dest = moveOp.getResult();
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
509 /*
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
510 * Moves with mismatching kinds are not moves, but memory loads/stores!
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
511 */
16115
9a595d3f9a2f Handle narrow oops in redundant move elimination.
Roland Schatz <roland.schatz@oracle.com>
parents: 16094
diff changeset
512 return source.getLIRKind().equals(dest.getLIRKind());
13339
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
513 }
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
514 return false;
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
515 }
3603fab248a6 added redundant move elimination as post-pass to LinearScan
Erik Eckstein <erik.eckstein@oracle.com>
parents:
diff changeset
516 }