Mercurial > hg > truffle

annotate graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScan.java @ 21322:73942ac6e650

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
LinearScan: outsource OptimizeSpillPosition.
author Josef Eisl <josef.eisl@jku.at>
date Tue, 12 May 2015 10:57:59 +0200
parents 1d5955a59d47
children 3570b7d1a6f9
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1 /*
16094
c0b8d395368b Introduce LIRKind to accurately track oop references in backend.
Roland Schatz <roland.schatz@oracle.com>
parents: 15927
diff changeset
2 * Copyright (c) 2009, 2014, Oracle and/or its affiliates. All rights reserved.
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
4 *
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
5 * This code is free software; you can redistribute it and/or modify it
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
6 * under the terms of the GNU General Public License version 2 only, as
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
7 * published by the Free Software Foundation.
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
8 *
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
9 * This code is distributed in the hope that it will be useful, but WITHOUT
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
12 * version 2 for more details (a copy is included in the LICENSE file that
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
13 * accompanied this code).
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
14 *
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
15 * You should have received a copy of the GNU General Public License version
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
16 * 2 along with this work; if not, write to the Free Software Foundation,
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
18 *
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
20 * or visit www.oracle.com if you need additional information or have any
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
21 * questions.
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
22 */
19166
39e99cf01468 Move LinearScan to c.o.g.lir.alloc.lsra.
Josef Eisl <josef.eisl@jku.at>
parents: 19165
diff changeset
23 package com.oracle.graal.lir.alloc.lsra;
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
24
5547
b6617d13ea44 Dropping Ci* prefixes. Some additional renamings in the api.code interface.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 5542
diff changeset
25 import static com.oracle.graal.api.code.CodeUtil.*;
5733
141b15521a39 use annotated fields for operands of LIR instructions
Christian Wimmer <christian.wimmer@oracle.com>
parents: 5711
diff changeset
26 import static com.oracle.graal.api.code.ValueUtil.*;
19163
0751ebc54c13 Move DetailedAsserts Option to GraalOptions.
Josef Eisl <josef.eisl@jku.at>
parents: 19162
diff changeset
27 import static com.oracle.graal.compiler.common.GraalOptions.*;
5733
141b15521a39 use annotated fields for operands of LIR instructions
Christian Wimmer <christian.wimmer@oracle.com>
parents: 5711
diff changeset
28 import static com.oracle.graal.lir.LIRValueUtil.*;
141b15521a39 use annotated fields for operands of LIR instructions
Christian Wimmer <christian.wimmer@oracle.com>
parents: 5711
diff changeset
29
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
30 import java.util.*;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
31
5510
426c605c9d3c Move cri.ci to api.code.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 5507
diff changeset
32 import com.oracle.graal.api.code.*;
5507
dc71b06d09f8 Moving classes from cri.ri to api.meta.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 5506
diff changeset
33 import com.oracle.graal.api.meta.*;
15193
96bb07a5d667 Spit up and move GraalInternalError.
Josef Eisl <josef.eisl@jku.at>
parents: 15192
diff changeset
34 import com.oracle.graal.compiler.common.*;
19165
b3b81dfff200 Move ComputeBlockOrder to compiler.common and delete c.o.g.alloc project.
Josef Eisl <josef.eisl@jku.at>
parents: 19164
diff changeset
35 import com.oracle.graal.compiler.common.alloc.*;
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
36 import com.oracle.graal.compiler.common.cfg.*;
5060
4ed4295ce15f Update import statements.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 5059
diff changeset
37 import com.oracle.graal.debug.*;
4ed4295ce15f Update import statements.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 5059
diff changeset
38 import com.oracle.graal.lir.*;
5733
141b15521a39 use annotated fields for operands of LIR instructions
Christian Wimmer <christian.wimmer@oracle.com>
parents: 5711
diff changeset
39 import com.oracle.graal.lir.LIRInstruction.OperandFlag;
141b15521a39 use annotated fields for operands of LIR instructions
Christian Wimmer <christian.wimmer@oracle.com>
parents: 5711
diff changeset
40 import com.oracle.graal.lir.LIRInstruction.OperandMode;
21236
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
41 import com.oracle.graal.lir.StandardOp.LabelOp;
5733
141b15521a39 use annotated fields for operands of LIR instructions
Christian Wimmer <christian.wimmer@oracle.com>
parents: 5711
diff changeset
42 import com.oracle.graal.lir.StandardOp.MoveOp;
19166
39e99cf01468 Move LinearScan to c.o.g.lir.alloc.lsra.
Josef Eisl <josef.eisl@jku.at>
parents: 19165
diff changeset
43 import com.oracle.graal.lir.alloc.lsra.Interval.RegisterBinding;
39e99cf01468 Move LinearScan to c.o.g.lir.alloc.lsra.
Josef Eisl <josef.eisl@jku.at>
parents: 19165
diff changeset
44 import com.oracle.graal.lir.alloc.lsra.Interval.RegisterPriority;
39e99cf01468 Move LinearScan to c.o.g.lir.alloc.lsra.
Josef Eisl <josef.eisl@jku.at>
parents: 19165
diff changeset
45 import com.oracle.graal.lir.alloc.lsra.Interval.SpillState;
18443
1c92d437179b FrameMapBuilder: move into package.
Josef Eisl <josef.eisl@jku.at>
parents: 18441
diff changeset
46 import com.oracle.graal.lir.framemap.*;
18152
ff694c40bdee LIRGenerationResult: add buildFrameMap() and getFrameMap().
Josef Eisl <josef.eisl@jku.at>
parents: 18151
diff changeset
47 import com.oracle.graal.lir.gen.*;
19549
1cf73c50e3dc Move SpillMoveFactory from LIR to LIRGeneratorTool.
Josef Eisl <josef.eisl@jku.at>
parents: 19212
diff changeset
48 import com.oracle.graal.lir.gen.LIRGeneratorTool.SpillMoveFactory;
21312
8ecb442fc864 LinearScan: split into sub-phases.
Josef Eisl <josef.eisl@jku.at>
parents: 21246
diff changeset
49 import com.oracle.graal.lir.phases.*;
8ecb442fc864 LinearScan: split into sub-phases.
Josef Eisl <josef.eisl@jku.at>
parents: 21246
diff changeset
50 import com.oracle.graal.lir.phases.AllocationPhase.AllocationContext;
16362
b100bd079fff LSRA spill optimization: add -G:+LSRAOptimizeSpillPosition option (default: enabled).
Josef Eisl <josef.eisl@jku.at>
parents: 16361
diff changeset
51 import com.oracle.graal.options.*;
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
52
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
53 /**
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7512
diff changeset
54 * An implementation of the linear scan register allocator algorithm described in <a
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7512
diff changeset
55 * href="http://doi.acm.org/10.1145/1064979.1064998"
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7512
diff changeset
56 * >"Optimized Interval Splitting in a Linear Scan Register Allocator"</a> by Christian Wimmer and
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7512
diff changeset
57 * Hanspeter Moessenboeck.
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
58 */
21240
1e9242c9735e Introduce SSALinearScan and SSAMoveResolver.
Josef Eisl <josef.eisl@jku.at>
parents: 21236
diff changeset
59 class LinearScan {
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
60
18152
ff694c40bdee LIRGenerationResult: add buildFrameMap() and getFrameMap().
Josef Eisl <josef.eisl@jku.at>
parents: 18151
diff changeset
61 final LIRGenerationResult res;
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
62 final LIR ir;
18150
22f2e42923de Use FrameMapBuilder in LinearScan (except for location marking).
Josef Eisl <josef.eisl@jku.at>
parents: 18123
diff changeset
63 final FrameMapBuilder frameMapBuilder;
5547
b6617d13ea44 Dropping Ci* prefixes. Some additional renamings in the api.code interface.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 5542
diff changeset
64 final RegisterAttributes[] registerAttributes;
b6617d13ea44 Dropping Ci* prefixes. Some additional renamings in the api.code interface.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 5542
diff changeset
65 final Register[] registers;
20915
916aac9fe6f7 LinearScan: use RegisterAllocationConfig.
Josef Eisl <josef.eisl@jku.at>
parents: 20151
diff changeset
66 final RegisterAllocationConfig regAllocConfig;
21312
8ecb442fc864 LinearScan: split into sub-phases.
Josef Eisl <josef.eisl@jku.at>
parents: 21246
diff changeset
67 private final SpillMoveFactory moveFactory;
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
68
18512
bcf66634c55c Make LinearScan.callKillsRegisters final.
Josef Eisl <josef.eisl@jku.at>
parents: 18446
diff changeset
69 final boolean callKillsRegisters;
10961
d0c9278fe471 move callKillsRegisters to LinearScan
twisti
parents: 9966
diff changeset
70
16380
8057279ec60e LSRA spill optimization: use DOMINATOR_SPILL_MOVE_ID to mark moves.
Josef Eisl <josef.eisl@jku.at>
parents: 16379
diff changeset
71 public static final int DOMINATOR_SPILL_MOVE_ID = -2;
21316
fd18bffefcc1 LinearScan: outsource LifetimeAnalysis.
Josef Eisl <josef.eisl@jku.at>
parents: 21315
diff changeset
72 static final int SPLIT_INTERVALS_CAPACITY_RIGHT_SHIFT = 1;
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
73
16362
b100bd079fff LSRA spill optimization: add -G:+LSRAOptimizeSpillPosition option (default: enabled).
Josef Eisl <josef.eisl@jku.at>
parents: 16361
diff changeset
74 public static class Options {
b100bd079fff LSRA spill optimization: add -G:+LSRAOptimizeSpillPosition option (default: enabled).
Josef Eisl <josef.eisl@jku.at>
parents: 16361
diff changeset
75 // @formatter:off
18674
ecb9d0cedbab First draft of option classification.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18610
diff changeset
76 @Option(help = "Enable spill position optimization", type = OptionType.Debug)
16362
b100bd079fff LSRA spill optimization: add -G:+LSRAOptimizeSpillPosition option (default: enabled).
Josef Eisl <josef.eisl@jku.at>
parents: 16361
diff changeset
77 public static final OptionValue<Boolean> LSRAOptimizeSpillPosition = new OptionValue<>(true);
b100bd079fff LSRA spill optimization: add -G:+LSRAOptimizeSpillPosition option (default: enabled).
Josef Eisl <josef.eisl@jku.at>
parents: 16361
diff changeset
78 // @formatter:on
b100bd079fff LSRA spill optimization: add -G:+LSRAOptimizeSpillPosition option (default: enabled).
Josef Eisl <josef.eisl@jku.at>
parents: 16361
diff changeset
79 }
b100bd079fff LSRA spill optimization: add -G:+LSRAOptimizeSpillPosition option (default: enabled).
Josef Eisl <josef.eisl@jku.at>
parents: 16361
diff changeset
80
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4394
diff changeset
81 public static class BlockData {
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7512
diff changeset
82
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4394
diff changeset
83 /**
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7512
diff changeset
84 * Bit map specifying which operands are live upon entry to this block. These are values
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7512
diff changeset
85 * used in this block or any of its successors where such value are not defined in this
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7512
diff changeset
86 * block. The bit index of an operand is its {@linkplain LinearScan#operandNumber(Value)
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7512
diff changeset
87 * operand number}.
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4394
diff changeset
88 */
5541
b4c406861c33 More renamings to drop Ri* prefix completely. Deleted graph.BitMap class and replaced with java.util.BitSet.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 5540
diff changeset
89 public BitSet liveIn;
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4394
diff changeset
90
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4394
diff changeset
91 /**
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7512
diff changeset
92 * Bit map specifying which operands are live upon exit from this block. These are values
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7512
diff changeset
93 * used in a successor block that are either defined in this block or were live upon entry
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7512
diff changeset
94 * to this block. The bit index of an operand is its
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7512
diff changeset
95 * {@linkplain LinearScan#operandNumber(Value) operand number}.
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4394
diff changeset
96 */
5541
b4c406861c33 More renamings to drop Ri* prefix completely. Deleted graph.BitMap class and replaced with java.util.BitSet.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 5540
diff changeset
97 public BitSet liveOut;
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4394
diff changeset
98
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4394
diff changeset
99 /**
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7512
diff changeset
100 * Bit map specifying which operands are used (before being defined) in this block. That is,
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7512
diff changeset
101 * these are the values that are live upon entry to the block. The bit index of an operand
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7512
diff changeset
102 * is its {@linkplain LinearScan#operandNumber(Value) operand number}.
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4394
diff changeset
103 */
5541
b4c406861c33 More renamings to drop Ri* prefix completely. Deleted graph.BitMap class and replaced with java.util.BitSet.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 5540
diff changeset
104 public BitSet liveGen;
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4394
diff changeset
105
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4394
diff changeset
106 /**
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7512
diff changeset
107 * Bit map specifying which operands are defined/overwritten in this block. The bit index of
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7512
diff changeset
108 * an operand is its {@linkplain LinearScan#operandNumber(Value) operand number}.
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4394
diff changeset
109 */
5541
b4c406861c33 More renamings to drop Ri* prefix completely. Deleted graph.BitMap class and replaced with java.util.BitSet.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 5540
diff changeset
110 public BitSet liveKill;
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4394
diff changeset
111 }
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4394
diff changeset
112
19212
95a7954ea155 Add LinearScanPhase.
Josef Eisl <josef.eisl@jku.at>
parents: 19166
diff changeset
113 final BlockMap<BlockData> blockData;
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4394
diff changeset
114
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
115 /**
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
116 * List of blocks in linear-scan order. This is only correct as long as the CFG does not change.
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
117 */
19560
4d70d150944f Remove AbstractBlock interface.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 19212
diff changeset
118 final List<? extends AbstractBlockBase<?>> sortedBlocks;
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
119
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
120 /**
5539
bc647d8b0080 Renaming RiValue => Value.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 5536
diff changeset
121 * Map from {@linkplain #operandNumber(Value) operand numbers} to intervals.
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
122 */
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
123 Interval[] intervals;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
124
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
125 /**
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
126 * The number of valid entries in {@link #intervals}.
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
127 */
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
128 int intervalsSize;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
129
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
130 /**
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7512
diff changeset
131 * The index of the first entry in {@link #intervals} for a
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7512
diff changeset
132 * {@linkplain #createDerivedInterval(Interval) derived interval}.
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
133 */
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
134 int firstDerivedIntervalIndex = -1;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
135
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
136 /**
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
137 * Intervals sorted by {@link Interval#from()}.
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
138 */
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
139 Interval[] sortedIntervals;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
140
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
141 /**
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7512
diff changeset
142 * Map from an instruction {@linkplain LIRInstruction#id id} to the instruction. Entries should
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7512
diff changeset
143 * be retrieved with {@link #instructionForId(int)} as the id is not simply an index into this
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7512
diff changeset
144 * array.
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
145 */
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
146 LIRInstruction[] opIdToInstructionMap;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
147
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
148 /**
19565
9bb45bec2b1f Run eclipseformat.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 19563
diff changeset
149 * Map from an instruction {@linkplain LIRInstruction#id id} to the
9bb45bec2b1f Run eclipseformat.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 19563
diff changeset
150 * {@linkplain AbstractBlockBase block} containing the instruction. Entries should be retrieved
9bb45bec2b1f Run eclipseformat.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 19563
diff changeset
151 * with {@link #blockForId(int)} as the id is not simply an index into this array.
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
152 */
19560
4d70d150944f Remove AbstractBlock interface.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 19212
diff changeset
153 AbstractBlockBase<?>[] opIdToBlockMap;
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
154
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
155 /**
5711
4d7175cf3526 enabled Eclipse/JDT javadoc checking and fixed resulting warnings
Doug Simon <doug.simon@oracle.com>
parents: 5552
diff changeset
156 * The {@linkplain #operandNumber(Value) number} of the first variable operand allocated.
4206
430b5db3e6f8 Remove CiVariable from the CRI
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4199
diff changeset
157 */
430b5db3e6f8 Remove CiVariable from the CRI
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4199
diff changeset
158 private final int firstVariableNumber;
430b5db3e6f8 Remove CiVariable from the CRI
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4199
diff changeset
159
20915
916aac9fe6f7 LinearScan: use RegisterAllocationConfig.
Josef Eisl <josef.eisl@jku.at>
parents: 20151
diff changeset
160 LinearScan(TargetDescription target, LIRGenerationResult res, SpillMoveFactory spillMoveFactory, RegisterAllocationConfig regAllocConfig) {
18152
ff694c40bdee LIRGenerationResult: add buildFrameMap() and getFrameMap().
Josef Eisl <josef.eisl@jku.at>
parents: 18151
diff changeset
161 this.res = res;
ff694c40bdee LIRGenerationResult: add buildFrameMap() and getFrameMap().
Josef Eisl <josef.eisl@jku.at>
parents: 18151
diff changeset
162 this.ir = res.getLIR();
21312
8ecb442fc864 LinearScan: split into sub-phases.
Josef Eisl <josef.eisl@jku.at>
parents: 21246
diff changeset
163 this.moveFactory = spillMoveFactory;
18152
ff694c40bdee LIRGenerationResult: add buildFrameMap() and getFrameMap().
Josef Eisl <josef.eisl@jku.at>
parents: 18151
diff changeset
164 this.frameMapBuilder = res.getFrameMapBuilder();
7501
799dd373fcb6 Remove caching of sorted blocks in LSRA.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7499
diff changeset
165 this.sortedBlocks = ir.linearScanOrder();
20915
916aac9fe6f7 LinearScan: use RegisterAllocationConfig.
Josef Eisl <josef.eisl@jku.at>
parents: 20151
diff changeset
166 this.registerAttributes = regAllocConfig.getRegisterConfig().getAttributesMap();
916aac9fe6f7 LinearScan: use RegisterAllocationConfig.
Josef Eisl <josef.eisl@jku.at>
parents: 20151
diff changeset
167 this.regAllocConfig = regAllocConfig;
4206
430b5db3e6f8 Remove CiVariable from the CRI
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4199
diff changeset
168
6582
cc32ce37eddc deleted Architecture.twoOperandMode() and encapsulated all public fields in Architecture with getters
Doug Simon <doug.simon@oracle.com>
parents: 6581
diff changeset
169 this.registers = target.arch.getRegisters();
4206
430b5db3e6f8 Remove CiVariable from the CRI
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4199
diff changeset
170 this.firstVariableNumber = registers.length;
14145
4ff08c0366ae Encapsulate LIR class fields.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 14142
diff changeset
171 this.blockData = new BlockMap<>(ir.getControlFlowGraph());
18512
bcf66634c55c Make LinearScan.callKillsRegisters final.
Josef Eisl <josef.eisl@jku.at>
parents: 18446
diff changeset
172
21319
9ddb5a749eab LinearScan: use multiline comments.
Josef Eisl <josef.eisl@jku.at>
parents: 21318
diff changeset
173 /*
9ddb5a749eab LinearScan: use multiline comments.
Josef Eisl <josef.eisl@jku.at>
parents: 21318
diff changeset
174 * If all allocatable registers are caller saved, then no registers are live across a call
9ddb5a749eab LinearScan: use multiline comments.
Josef Eisl <josef.eisl@jku.at>
parents: 21318
diff changeset
175 * site. The register allocator can save time not trying to find a register at a call site.
9ddb5a749eab LinearScan: use multiline comments.
Josef Eisl <josef.eisl@jku.at>
parents: 21318
diff changeset
176 */
20915
916aac9fe6f7 LinearScan: use RegisterAllocationConfig.
Josef Eisl <josef.eisl@jku.at>
parents: 20151
diff changeset
177 this.callKillsRegisters = regAllocConfig.getRegisterConfig().areAllAllocatableRegistersCallerSaved();
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
178 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
179
19560
4d70d150944f Remove AbstractBlock interface.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 19212
diff changeset
180 int getFirstLirInstructionId(AbstractBlockBase<?> block) {
14806
a8723f1ff542 LIR renamed setter and getter functions.
Josef Eisl <josef.eisl@jku.at>
parents: 14789
diff changeset
181 int result = ir.getLIRforBlock(block).get(0).id();
6411
c5afcc2ebd3d change of project structure: separate compiler and LIR, put EA into separate project
Lukas Stadler <lukas.stadler@jku.at>
parents: 6352
diff changeset
182 assert result >= 0;
c5afcc2ebd3d change of project structure: separate compiler and LIR, put EA into separate project
Lukas Stadler <lukas.stadler@jku.at>
parents: 6352
diff changeset
183 return result;
c5afcc2ebd3d change of project structure: separate compiler and LIR, put EA into separate project
Lukas Stadler <lukas.stadler@jku.at>
parents: 6352
diff changeset
184 }
c5afcc2ebd3d change of project structure: separate compiler and LIR, put EA into separate project
Lukas Stadler <lukas.stadler@jku.at>
parents: 6352
diff changeset
185
19560
4d70d150944f Remove AbstractBlock interface.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 19212
diff changeset
186 int getLastLirInstructionId(AbstractBlockBase<?> block) {
14806
a8723f1ff542 LIR renamed setter and getter functions.
Josef Eisl <josef.eisl@jku.at>
parents: 14789
diff changeset
187 List<LIRInstruction> instructions = ir.getLIRforBlock(block);
6411
c5afcc2ebd3d change of project structure: separate compiler and LIR, put EA into separate project
Lukas Stadler <lukas.stadler@jku.at>
parents: 6352
diff changeset
188 int result = instructions.get(instructions.size() - 1).id();
c5afcc2ebd3d change of project structure: separate compiler and LIR, put EA into separate project
Lukas Stadler <lukas.stadler@jku.at>
parents: 6352
diff changeset
189 assert result >= 0;
c5afcc2ebd3d change of project structure: separate compiler and LIR, put EA into separate project
Lukas Stadler <lukas.stadler@jku.at>
parents: 6352
diff changeset
190 return result;
c5afcc2ebd3d change of project structure: separate compiler and LIR, put EA into separate project
Lukas Stadler <lukas.stadler@jku.at>
parents: 6352
diff changeset
191 }
c5afcc2ebd3d change of project structure: separate compiler and LIR, put EA into separate project
Lukas Stadler <lukas.stadler@jku.at>
parents: 6352
diff changeset
192
19549
1cf73c50e3dc Move SpillMoveFactory from LIR to LIRGeneratorTool.
Josef Eisl <josef.eisl@jku.at>
parents: 19212
diff changeset
193 SpillMoveFactory getSpillMoveFactory() {
21312
8ecb442fc864 LinearScan: split into sub-phases.
Josef Eisl <josef.eisl@jku.at>
parents: 21246
diff changeset
194 return moveFactory;
19549
1cf73c50e3dc Move SpillMoveFactory from LIR to LIRGeneratorTool.
Josef Eisl <josef.eisl@jku.at>
parents: 19212
diff changeset
195 }
1cf73c50e3dc Move SpillMoveFactory from LIR to LIRGeneratorTool.
Josef Eisl <josef.eisl@jku.at>
parents: 19212
diff changeset
196
21203
9f45587ad8f5 LinearScan: add createMoveResolver().
Josef Eisl <josef.eisl@jku.at>
parents: 21193
diff changeset
197 protected MoveResolver createMoveResolver() {
21246
b2b3c514a391 MoveResolver: don't call check from constructor.
Josef Eisl <josef.eisl@jku.at>
parents: 21240
diff changeset
198 MoveResolver moveResolver = new MoveResolver(this);
b2b3c514a391 MoveResolver: don't call check from constructor.
Josef Eisl <josef.eisl@jku.at>
parents: 21240
diff changeset
199 assert moveResolver.checkEmpty();
b2b3c514a391 MoveResolver: don't call check from constructor.
Josef Eisl <josef.eisl@jku.at>
parents: 21240
diff changeset
200 return moveResolver;
21203
9f45587ad8f5 LinearScan: add createMoveResolver().
Josef Eisl <josef.eisl@jku.at>
parents: 21193
diff changeset
201 }
9f45587ad8f5 LinearScan: add createMoveResolver().
Josef Eisl <josef.eisl@jku.at>
parents: 21193
diff changeset
202
5539
bc647d8b0080 Renaming RiValue => Value.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 5536
diff changeset
203 public static boolean isVariableOrRegister(Value value) {
4183
9e0c1b4cfef5 Move all isXxx and asXxx out of CiValue and into their own util class.
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4181
diff changeset
204 return isVariable(value) || isRegister(value);
9e0c1b4cfef5 Move all isXxx and asXxx out of CiValue and into their own util class.
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4181
diff changeset
205 }
9e0c1b4cfef5 Move all isXxx and asXxx out of CiValue and into their own util class.
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4181
diff changeset
206
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
207 /**
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7512
diff changeset
208 * Converts an operand (variable or register) to an index in a flat address space covering all
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7512
diff changeset
209 * the {@linkplain Variable variables} and {@linkplain RegisterValue registers} being processed
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7512
diff changeset
210 * by this allocator.
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
211 */
21316
fd18bffefcc1 LinearScan: outsource LifetimeAnalysis.
Josef Eisl <josef.eisl@jku.at>
parents: 21315
diff changeset
212 int operandNumber(Value operand) {
4206
430b5db3e6f8 Remove CiVariable from the CRI
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4199
diff changeset
213 if (isRegister(operand)) {
430b5db3e6f8 Remove CiVariable from the CRI
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4199
diff changeset
214 int number = asRegister(operand).number;
430b5db3e6f8 Remove CiVariable from the CRI
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4199
diff changeset
215 assert number < firstVariableNumber;
430b5db3e6f8 Remove CiVariable from the CRI
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4199
diff changeset
216 return number;
430b5db3e6f8 Remove CiVariable from the CRI
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4199
diff changeset
217 }
430b5db3e6f8 Remove CiVariable from the CRI
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4199
diff changeset
218 assert isVariable(operand) : operand;
430b5db3e6f8 Remove CiVariable from the CRI
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4199
diff changeset
219 return firstVariableNumber + ((Variable) operand).index;
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
220 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
221
4206
430b5db3e6f8 Remove CiVariable from the CRI
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4199
diff changeset
222 /**
430b5db3e6f8 Remove CiVariable from the CRI
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4199
diff changeset
223 * Gets the number of operands. This value will increase by 1 for new variable.
430b5db3e6f8 Remove CiVariable from the CRI
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4199
diff changeset
224 */
21316
fd18bffefcc1 LinearScan: outsource LifetimeAnalysis.
Josef Eisl <josef.eisl@jku.at>
parents: 21315
diff changeset
225 int operandSize() {
4206
430b5db3e6f8 Remove CiVariable from the CRI
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4199
diff changeset
226 return firstVariableNumber + ir.numVariables();
430b5db3e6f8 Remove CiVariable from the CRI
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4199
diff changeset
227 }
430b5db3e6f8 Remove CiVariable from the CRI
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4199
diff changeset
228
430b5db3e6f8 Remove CiVariable from the CRI
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4199
diff changeset
229 /**
430b5db3e6f8 Remove CiVariable from the CRI
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4199
diff changeset
230 * Gets the highest operand number for a register operand. This value will never change.
430b5db3e6f8 Remove CiVariable from the CRI
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4199
diff changeset
231 */
19212
95a7954ea155 Add LinearScanPhase.
Josef Eisl <josef.eisl@jku.at>
parents: 19166
diff changeset
232 int maxRegisterNumber() {
4206
430b5db3e6f8 Remove CiVariable from the CRI
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4199
diff changeset
233 return firstVariableNumber - 1;
430b5db3e6f8 Remove CiVariable from the CRI
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4199
diff changeset
234 }
430b5db3e6f8 Remove CiVariable from the CRI
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4199
diff changeset
235
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7512
diff changeset
236 static final IntervalPredicate IS_PRECOLORED_INTERVAL = new IntervalPredicate() {
4206
430b5db3e6f8 Remove CiVariable from the CRI
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4199
diff changeset
237
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
238 @Override
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
239 public boolean apply(Interval i) {
4183
9e0c1b4cfef5 Move all isXxx and asXxx out of CiValue and into their own util class.
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4181
diff changeset
240 return isRegister(i.operand);
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
241 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
242 };
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
243
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
244 static final IntervalPredicate IS_VARIABLE_INTERVAL = new IntervalPredicate() {
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7512
diff changeset
245
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
246 @Override
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
247 public boolean apply(Interval i) {
4183
9e0c1b4cfef5 Move all isXxx and asXxx out of CiValue and into their own util class.
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4181
diff changeset
248 return isVariable(i.operand);
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
249 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
250 };
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
251
13340
9423a38d6437 added rematerialization of constants in LinearScan, but still disabled
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13339
diff changeset
252 static final IntervalPredicate IS_STACK_INTERVAL = new IntervalPredicate() {
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7512
diff changeset
253
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
254 @Override
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
255 public boolean apply(Interval i) {
13340
9423a38d6437 added rematerialization of constants in LinearScan, but still disabled
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13339
diff changeset
256 return !isRegister(i.operand);
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
257 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
258 };
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
259
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
260 /**
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7512
diff changeset
261 * Gets an object describing the attributes of a given register according to this register
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7512
diff changeset
262 * configuration.
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
263 */
5547
b6617d13ea44 Dropping Ci* prefixes. Some additional renamings in the api.code interface.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 5542
diff changeset
264 RegisterAttributes attributes(Register reg) {
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
265 return registerAttributes[reg.number];
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
266 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
267
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
268 void assignSpillSlot(Interval interval) {
21319
9ddb5a749eab LinearScan: use multiline comments.
Josef Eisl <josef.eisl@jku.at>
parents: 21318
diff changeset
269 /*
9ddb5a749eab LinearScan: use multiline comments.
Josef Eisl <josef.eisl@jku.at>
parents: 21318
diff changeset
270 * Assign the canonical spill slot of the parent (if a part of the interval is already
9ddb5a749eab LinearScan: use multiline comments.
Josef Eisl <josef.eisl@jku.at>
parents: 21318
diff changeset
271 * spilled) or allocate a new spill slot.
9ddb5a749eab LinearScan: use multiline comments.
Josef Eisl <josef.eisl@jku.at>
parents: 21318
diff changeset
272 */
13340
9423a38d6437 added rematerialization of constants in LinearScan, but still disabled
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13339
diff changeset
273 if (interval.canMaterialize()) {
9423a38d6437 added rematerialization of constants in LinearScan, but still disabled
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13339
diff changeset
274 interval.assignLocation(Value.ILLEGAL);
9423a38d6437 added rematerialization of constants in LinearScan, but still disabled
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13339
diff changeset
275 } else if (interval.spillSlot() != null) {
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
276 interval.assignLocation(interval.spillSlot());
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
277 } else {
18425
b856446ff7e0 Introduce StackSlotValue and VirtualStackSlot.
Josef Eisl <josef.eisl@jku.at>
parents: 18420
diff changeset
278 VirtualStackSlot slot = frameMapBuilder.allocateSpillSlot(interval.kind());
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
279 interval.setSpillSlot(slot);
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
280 interval.assignLocation(slot);
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
281 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
282 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
283
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
284 /**
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
285 * Creates a new interval.
14871
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14841
diff changeset
286 *
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
287 * @param operand the operand for the interval
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
288 * @return the created interval
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
289 */
9297
a5f2b9012865 Interval locations can only be AllocatableValues.
Roland Schatz <roland.schatz@oracle.com>
parents: 8402
diff changeset
290 Interval createInterval(AllocatableValue operand) {
4183
9e0c1b4cfef5 Move all isXxx and asXxx out of CiValue and into their own util class.
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4181
diff changeset
291 assert isLegal(operand);
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
292 int operandNumber = operandNumber(operand);
4352
5a84f5548fc4 More work on new debug infrastructure.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 4350
diff changeset
293 Interval interval = new Interval(operand, operandNumber);
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
294 assert operandNumber < intervalsSize;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
295 assert intervals[operandNumber] == null;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
296 intervals[operandNumber] = interval;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
297 return interval;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
298 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
299
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
300 /**
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
301 * Creates an interval as a result of splitting or spilling another interval.
14871
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14841
diff changeset
302 *
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
303 * @param source an interval being split of spilled
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
304 * @return a new interval derived from {@code source}
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
305 */
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
306 Interval createDerivedInterval(Interval source) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
307 if (firstDerivedIntervalIndex == -1) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
308 firstDerivedIntervalIndex = intervalsSize;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
309 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
310 if (intervalsSize == intervals.length) {
15885
4d18c6bb6b3a LinearScan: Improve initialization and resizing of intervals array.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 15884
diff changeset
311 intervals = Arrays.copyOf(intervals, intervals.length + (intervals.length >> SPLIT_INTERVALS_CAPACITY_RIGHT_SHIFT));
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
312 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
313 intervalsSize++;
9425
3ec29630cfb4 Use register categories instead of register flags.
Roland Schatz <roland.schatz@oracle.com>
parents: 9422
diff changeset
314 Variable variable = new Variable(source.kind(), ir.nextVariable());
4206
430b5db3e6f8 Remove CiVariable from the CRI
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4199
diff changeset
315
430b5db3e6f8 Remove CiVariable from the CRI
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4199
diff changeset
316 Interval interval = createInterval(variable);
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
317 assert intervals[intervalsSize - 1] == interval;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
318 return interval;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
319 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
320
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
321 // access to block list (sorted in linear scan order)
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
322 int blockCount() {
7501
799dd373fcb6 Remove caching of sorted blocks in LSRA.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7499
diff changeset
323 return sortedBlocks.size();
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
324 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
325
19560
4d70d150944f Remove AbstractBlock interface.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 19212
diff changeset
326 AbstractBlockBase<?> blockAt(int index) {
7501
799dd373fcb6 Remove caching of sorted blocks in LSRA.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7499
diff changeset
327 return sortedBlocks.get(index);
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
328 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
329
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
330 /**
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7512
diff changeset
331 * Gets the size of the {@link BlockData#liveIn} and {@link BlockData#liveOut} sets for a basic
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7512
diff changeset
332 * block. These sets do not include any operands allocated as a result of creating
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7512
diff changeset
333 * {@linkplain #createDerivedInterval(Interval) derived intervals}.
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
334 */
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
335 int liveSetSize() {
4206
430b5db3e6f8 Remove CiVariable from the CRI
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4199
diff changeset
336 return firstDerivedIntervalIndex == -1 ? operandSize() : firstDerivedIntervalIndex;
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
337 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
338
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
339 int numLoops() {
15107
1bf700e19e84 Make Loop generic.
Josef Eisl <josef.eisl@jku.at>
parents: 15026
diff changeset
340 return ir.getControlFlowGraph().getLoops().size();
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
341 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
342
15884
0e6f83eeb0ab Clean up in LinearScan: Remove the need for a mapping of variable index to variable object.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 15850
diff changeset
343 Interval intervalFor(int operandNumber) {
0e6f83eeb0ab Clean up in LinearScan: Remove the need for a mapping of variable index to variable object.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 15850
diff changeset
344 return intervals[operandNumber];
0e6f83eeb0ab Clean up in LinearScan: Remove the need for a mapping of variable index to variable object.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 15850
diff changeset
345 }
0e6f83eeb0ab Clean up in LinearScan: Remove the need for a mapping of variable index to variable object.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 15850
diff changeset
346
5539
bc647d8b0080 Renaming RiValue => Value.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 5536
diff changeset
347 Interval intervalFor(Value operand) {
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
348 int operandNumber = operandNumber(operand);
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
349 assert operandNumber < intervalsSize;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
350 return intervals[operandNumber];
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
351 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
352
9297
a5f2b9012865 Interval locations can only be AllocatableValues.
Roland Schatz <roland.schatz@oracle.com>
parents: 8402
diff changeset
353 Interval getOrCreateInterval(AllocatableValue operand) {
8220
2c5df42999dd Fix hinting in register allocator.
Roland Schatz <roland.schatz@oracle.com>
parents: 7648
diff changeset
354 Interval ret = intervalFor(operand);
2c5df42999dd Fix hinting in register allocator.
Roland Schatz <roland.schatz@oracle.com>
parents: 7648
diff changeset
355 if (ret == null) {
2c5df42999dd Fix hinting in register allocator.
Roland Schatz <roland.schatz@oracle.com>
parents: 7648
diff changeset
356 return createInterval(operand);
2c5df42999dd Fix hinting in register allocator.
Roland Schatz <roland.schatz@oracle.com>
parents: 7648
diff changeset
357 } else {
2c5df42999dd Fix hinting in register allocator.
Roland Schatz <roland.schatz@oracle.com>
parents: 7648
diff changeset
358 return ret;
2c5df42999dd Fix hinting in register allocator.
Roland Schatz <roland.schatz@oracle.com>
parents: 7648
diff changeset
359 }
2c5df42999dd Fix hinting in register allocator.
Roland Schatz <roland.schatz@oracle.com>
parents: 7648
diff changeset
360 }
2c5df42999dd Fix hinting in register allocator.
Roland Schatz <roland.schatz@oracle.com>
parents: 7648
diff changeset
361
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
362 /**
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
363 * Gets the highest instruction id allocated by this object.
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
364 */
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
365 int maxOpId() {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
366 assert opIdToInstructionMap.length > 0 : "no operations";
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
367 return (opIdToInstructionMap.length - 1) << 1;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
368 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
369
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
370 /**
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7512
diff changeset
371 * Converts an {@linkplain LIRInstruction#id instruction id} to an instruction index. All LIR
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7512
diff changeset
372 * instructions in a method have an index one greater than their linear-scan order predecesor
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
373 * with the first instruction having an index of 0.
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
374 */
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
375 static int opIdToIndex(int opId) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
376 return opId >> 1;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
377 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
378
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
379 /**
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
380 * Retrieves the {@link LIRInstruction} based on its {@linkplain LIRInstruction#id id}.
14871
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14841
diff changeset
381 *
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
382 * @param opId an instruction {@linkplain LIRInstruction#id id}
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
383 * @return the instruction whose {@linkplain LIRInstruction#id} {@code == id}
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
384 */
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
385 LIRInstruction instructionForId(int opId) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
386 assert isEven(opId) : "opId not even";
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
387 LIRInstruction instr = opIdToInstructionMap[opIdToIndex(opId)];
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
388 assert instr.id() == opId;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
389 return instr;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
390 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
391
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
392 /**
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
393 * Gets the block containing a given instruction.
14871
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14841
diff changeset
394 *
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
395 * @param opId an instruction {@linkplain LIRInstruction#id id}
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
396 * @return the block containing the instruction denoted by {@code opId}
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
397 */
19560
4d70d150944f Remove AbstractBlock interface.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 19212
diff changeset
398 AbstractBlockBase<?> blockForId(int opId) {
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
399 assert opIdToBlockMap.length > 0 && opId >= 0 && opId <= maxOpId() + 1 : "opId out of range";
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
400 return opIdToBlockMap[opIdToIndex(opId)];
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
401 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
402
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
403 boolean isBlockBegin(int opId) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
404 return opId == 0 || blockForId(opId) != blockForId(opId - 1);
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
405 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
406
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
407 boolean coversBlockBegin(int opId1, int opId2) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
408 return blockForId(opId1) != blockForId(opId2);
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
409 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
410
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
411 /**
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
412 * Determines if an {@link LIRInstruction} destroys all caller saved registers.
14871
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14841
diff changeset
413 *
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
414 * @param opId an instruction {@linkplain LIRInstruction#id id}
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7512
diff changeset
415 * @return {@code true} if the instruction denoted by {@code id} destroys all caller saved
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7512
diff changeset
416 * registers.
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
417 */
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
418 boolean hasCall(int opId) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
419 assert isEven(opId) : "opId not even";
9454
85a836bcd796 renaming for improved clarity: hasCall -> destroysCallerSavedRegisters
Doug Simon <doug.simon@oracle.com>
parents: 9425
diff changeset
420 return instructionForId(opId).destroysCallerSavedRegisters();
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
421 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
422
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
423 /**
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
424 * Eliminates moves from register to stack if the stack slot is known to be correct.
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
425 */
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
426 void changeSpillDefinitionPos(Interval interval, int defPos) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
427 assert interval.isSplitParent() : "can only be called for split parents";
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
428
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
429 switch (interval.spillState()) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
430 case NoDefinitionFound:
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
431 assert interval.spillDefinitionPos() == -1 : "must no be set before";
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
432 interval.setSpillDefinitionPos(defPos);
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
433 interval.setSpillState(SpillState.NoSpillStore);
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
434 break;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
435
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
436 case NoSpillStore:
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
437 assert defPos <= interval.spillDefinitionPos() : "positions are processed in reverse order when intervals are created";
6462
b3f5dc099f9d removed XIR
Doug Simon <doug.simon@oracle.com>
parents: 6411
diff changeset
438 if (defPos < interval.spillDefinitionPos() - 2) {
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
439 // second definition found, so no spill optimization possible for this interval
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
440 interval.setSpillState(SpillState.NoOptimization);
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
441 } else {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
442 // two consecutive definitions (because of two-operand LIR form)
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
443 assert blockForId(defPos) == blockForId(interval.spillDefinitionPos()) : "block must be equal";
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
444 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
445 break;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
446
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
447 case NoOptimization:
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
448 // nothing to do
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
449 break;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
450
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
451 default:
5547
b6617d13ea44 Dropping Ci* prefixes. Some additional renamings in the api.code interface.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 5542
diff changeset
452 throw new BailoutException("other states not allowed at this time");
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
453 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
454 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
455
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
456 // called during register allocation
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
457 void changeSpillState(Interval interval, int spillPos) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
458 switch (interval.spillState()) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
459 case NoSpillStore: {
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4394
diff changeset
460 int defLoopDepth = blockForId(interval.spillDefinitionPos()).getLoopDepth();
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4394
diff changeset
461 int spillLoopDepth = blockForId(spillPos).getLoopDepth();
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
462
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
463 if (defLoopDepth < spillLoopDepth) {
21319
9ddb5a749eab LinearScan: use multiline comments.
Josef Eisl <josef.eisl@jku.at>
parents: 21318
diff changeset
464 /*
9ddb5a749eab LinearScan: use multiline comments.
Josef Eisl <josef.eisl@jku.at>
parents: 21318
diff changeset
465 * The loop depth of the spilling position is higher then the loop depth at the
9ddb5a749eab LinearScan: use multiline comments.
Josef Eisl <josef.eisl@jku.at>
parents: 21318
diff changeset
466 * definition of the interval. Move write to memory out of loop.
9ddb5a749eab LinearScan: use multiline comments.
Josef Eisl <josef.eisl@jku.at>
parents: 21318
diff changeset
467 */
16362
b100bd079fff LSRA spill optimization: add -G:+LSRAOptimizeSpillPosition option (default: enabled).
Josef Eisl <josef.eisl@jku.at>
parents: 16361
diff changeset
468 if (Options.LSRAOptimizeSpillPosition.getValue()) {
b100bd079fff LSRA spill optimization: add -G:+LSRAOptimizeSpillPosition option (default: enabled).
Josef Eisl <josef.eisl@jku.at>
parents: 16361
diff changeset
469 // find best spill position in dominator the tree
b100bd079fff LSRA spill optimization: add -G:+LSRAOptimizeSpillPosition option (default: enabled).
Josef Eisl <josef.eisl@jku.at>
parents: 16361
diff changeset
470 interval.setSpillState(SpillState.SpillInDominator);
b100bd079fff LSRA spill optimization: add -G:+LSRAOptimizeSpillPosition option (default: enabled).
Josef Eisl <josef.eisl@jku.at>
parents: 16361
diff changeset
471 } else {
b100bd079fff LSRA spill optimization: add -G:+LSRAOptimizeSpillPosition option (default: enabled).
Josef Eisl <josef.eisl@jku.at>
parents: 16361
diff changeset
472 // store at definition of the interval
b100bd079fff LSRA spill optimization: add -G:+LSRAOptimizeSpillPosition option (default: enabled).
Josef Eisl <josef.eisl@jku.at>
parents: 16361
diff changeset
473 interval.setSpillState(SpillState.StoreAtDefinition);
b100bd079fff LSRA spill optimization: add -G:+LSRAOptimizeSpillPosition option (default: enabled).
Josef Eisl <josef.eisl@jku.at>
parents: 16361
diff changeset
474 }
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
475 } else {
21319
9ddb5a749eab LinearScan: use multiline comments.
Josef Eisl <josef.eisl@jku.at>
parents: 21318
diff changeset
476 /*
9ddb5a749eab LinearScan: use multiline comments.
Josef Eisl <josef.eisl@jku.at>
parents: 21318
diff changeset
477 * The interval is currently spilled only once, so for now there is no reason to
9ddb5a749eab LinearScan: use multiline comments.
Josef Eisl <josef.eisl@jku.at>
parents: 21318
diff changeset
478 * store the interval at the definition.
9ddb5a749eab LinearScan: use multiline comments.
Josef Eisl <josef.eisl@jku.at>
parents: 21318
diff changeset
479 */
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
480 interval.setSpillState(SpillState.OneSpillStore);
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
481 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
482 break;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
483 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
484
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
485 case OneSpillStore: {
16362
b100bd079fff LSRA spill optimization: add -G:+LSRAOptimizeSpillPosition option (default: enabled).
Josef Eisl <josef.eisl@jku.at>
parents: 16361
diff changeset
486 if (Options.LSRAOptimizeSpillPosition.getValue()) {
b100bd079fff LSRA spill optimization: add -G:+LSRAOptimizeSpillPosition option (default: enabled).
Josef Eisl <josef.eisl@jku.at>
parents: 16361
diff changeset
487 // the interval is spilled more then once
b100bd079fff LSRA spill optimization: add -G:+LSRAOptimizeSpillPosition option (default: enabled).
Josef Eisl <josef.eisl@jku.at>
parents: 16361
diff changeset
488 interval.setSpillState(SpillState.SpillInDominator);
b100bd079fff LSRA spill optimization: add -G:+LSRAOptimizeSpillPosition option (default: enabled).
Josef Eisl <josef.eisl@jku.at>
parents: 16361
diff changeset
489 } else {
21319
9ddb5a749eab LinearScan: use multiline comments.
Josef Eisl <josef.eisl@jku.at>
parents: 21318
diff changeset
490 // It is better to store it to memory at the definition.
16362
b100bd079fff LSRA spill optimization: add -G:+LSRAOptimizeSpillPosition option (default: enabled).
Josef Eisl <josef.eisl@jku.at>
parents: 16361
diff changeset
491 interval.setSpillState(SpillState.StoreAtDefinition);
b100bd079fff LSRA spill optimization: add -G:+LSRAOptimizeSpillPosition option (default: enabled).
Josef Eisl <josef.eisl@jku.at>
parents: 16361
diff changeset
492 }
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
493 break;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
494 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
495
16359
f686fae77383 LSRA spill optimization: rename SpillInDominator.MultipleSpills to SpillState.SpillInDominator.
Josef Eisl <josef.eisl@jku.at>
parents: 16358
diff changeset
496 case SpillInDominator:
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
497 case StoreAtDefinition:
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
498 case StartInMemory:
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
499 case NoOptimization:
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
500 case NoDefinitionFound:
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
501 // nothing to do
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
502 break;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
503
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
504 default:
5547
b6617d13ea44 Dropping Ci* prefixes. Some additional renamings in the api.code interface.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 5542
diff changeset
505 throw new BailoutException("other states not allowed at this time");
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
506 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
507 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
508
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
509 abstract static class IntervalPredicate {
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7512
diff changeset
510
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
511 abstract boolean apply(Interval i);
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
512 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
513
16379
c5257d58b71a LSRA spill optimization: backout changesets obsoleted by eager spill move placement.
Josef Eisl <josef.eisl@jku.at>
parents: 16378
diff changeset
514 private static final IntervalPredicate mustStoreAtDefinition = new IntervalPredicate() {
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7512
diff changeset
515
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
516 @Override
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
517 public boolean apply(Interval i) {
16379
c5257d58b71a LSRA spill optimization: backout changesets obsoleted by eager spill move placement.
Josef Eisl <josef.eisl@jku.at>
parents: 16378
diff changeset
518 return i.isSplitParent() && i.spillState() == SpillState.StoreAtDefinition;
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
519 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
520 };
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
521
21236
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
522 /**
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
523 * @return the index of the first instruction that is of interest for
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
524 * {@link #eliminateSpillMoves()}
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
525 */
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
526 protected int firstInstructionOfInterest() {
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
527 // skip the first because it is always a label
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
528 return 1;
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
529 }
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
530
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
531 // called once before assignment of register numbers
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
532 void eliminateSpillMoves() {
14871
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14841
diff changeset
533 try (Indent indent = Debug.logAndIndent("Eliminating unnecessary spill moves")) {
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14841
diff changeset
534
21319
9ddb5a749eab LinearScan: use multiline comments.
Josef Eisl <josef.eisl@jku.at>
parents: 21318
diff changeset
535 /*
9ddb5a749eab LinearScan: use multiline comments.
Josef Eisl <josef.eisl@jku.at>
parents: 21318
diff changeset
536 * collect all intervals that must be stored after their definition. The list is sorted
9ddb5a749eab LinearScan: use multiline comments.
Josef Eisl <josef.eisl@jku.at>
parents: 21318
diff changeset
537 * by Interval.spillDefinitionPos.
9ddb5a749eab LinearScan: use multiline comments.
Josef Eisl <josef.eisl@jku.at>
parents: 21318
diff changeset
538 */
14871
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14841
diff changeset
539 Interval interval;
16379
c5257d58b71a LSRA spill optimization: backout changesets obsoleted by eager spill move placement.
Josef Eisl <josef.eisl@jku.at>
parents: 16378
diff changeset
540 interval = createUnhandledLists(mustStoreAtDefinition, null).first;
14871
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14841
diff changeset
541 if (DetailedAsserts.getValue()) {
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14841
diff changeset
542 checkIntervals(interval);
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14841
diff changeset
543 }
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14841
diff changeset
544
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14841
diff changeset
545 LIRInsertionBuffer insertionBuffer = new LIRInsertionBuffer();
19560
4d70d150944f Remove AbstractBlock interface.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 19212
diff changeset
546 for (AbstractBlockBase<?> block : sortedBlocks) {
21236
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
547 try (Indent indent1 = Debug.logAndIndent("Handle %s", block)) {
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
548 List<LIRInstruction> instructions = ir.getLIRforBlock(block);
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
549 int numInst = instructions.size();
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
550
21236
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
551 // iterate all instructions of the block.
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
552 for (int j = firstInstructionOfInterest(); j < numInst; j++) {
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
553 LIRInstruction op = instructions.get(j);
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
554 int opId = op.id();
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
555
21236
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
556 if (opId == -1) {
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
557 MoveOp move = (MoveOp) op;
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
558 /*
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
559 * Remove move from register to stack if the stack slot is guaranteed to
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
560 * be correct. Only moves that have been inserted by LinearScan can be
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
561 * removed.
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
562 */
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
563 if (canEliminateSpillMove(block, move)) {
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
564 /*
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
565 * Move target is a stack slot that is always correct, so eliminate
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
566 * instruction.
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
567 */
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
568 if (Debug.isLogEnabled()) {
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
569 Debug.log("eliminating move from interval %d (%s) to %d (%s) in block %s", operandNumber(move.getInput()), move.getInput(), operandNumber(move.getResult()),
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
570 move.getResult(), block);
14871
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14841
diff changeset
571 }
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
572
21236
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
573 // null-instructions are deleted by assignRegNum
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
574 instructions.set(j, null);
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
575 }
14871
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14841
diff changeset
576
21236
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
577 } else {
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
578 /*
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
579 * Insert move from register to stack just after the beginning of the
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
580 * interval.
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
581 */
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
582 assert interval == Interval.EndMarker || interval.spillDefinitionPos() >= opId : "invalid order";
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
583 assert interval == Interval.EndMarker || (interval.isSplitParent() && interval.spillState() == SpillState.StoreAtDefinition) : "invalid interval";
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
584
21236
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
585 while (interval != Interval.EndMarker && interval.spillDefinitionPos() == opId) {
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
586 if (!interval.canMaterialize()) {
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
587 if (!insertionBuffer.initialized()) {
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
588 /*
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
589 * prepare insertion buffer (appended when all instructions
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
590 * in the block are processed)
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
591 */
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
592 insertionBuffer.init(instructions);
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
593 }
14871
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14841
diff changeset
594
21236
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
595 AllocatableValue fromLocation = interval.location();
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
596 AllocatableValue toLocation = canonicalSpillOpr(interval);
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
597 if (!fromLocation.equals(toLocation)) {
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
598
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
599 assert isRegister(fromLocation) : "from operand must be a register but is: " + fromLocation + " toLocation=" + toLocation + " spillState=" +
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
600 interval.spillState();
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
601 assert isStackSlotValue(toLocation) : "to operand must be a stack slot";
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
602
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
603 LIRInstruction move = getSpillMoveFactory().createMove(toLocation, fromLocation);
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
604 insertionBuffer.append(j + 1, move);
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
605
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
606 if (Debug.isLogEnabled()) {
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
607 Debug.log("inserting move after definition of interval %d to stack slot %s at opId %d", interval.operandNumber, interval.spillSlot(), opId);
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
608 }
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
609 }
20980
abc059cb0acf Guard usages of Debug.log in LinearScan
Tom Rodriguez <tom.rodriguez@oracle.com>
parents: 20979
diff changeset
610 }
21236
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
611 interval = interval.next;
14871
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14841
diff changeset
612 }
13467
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
613 }
21236
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
614 } // end of instruction iteration
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
615
21236
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
616 if (insertionBuffer.initialized()) {
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
617 insertionBuffer.finish();
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
618 }
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
619 }
14871
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14841
diff changeset
620 } // end of block iteration
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
621
14871
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14841
diff changeset
622 assert interval == Interval.EndMarker : "missed an interval";
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14841
diff changeset
623 }
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
624 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
625
21236
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
626 /**
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
627 * @param block The block {@code move} is located in.
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
628 * @param move Spill move.
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
629 */
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
630 protected boolean canEliminateSpillMove(AbstractBlockBase<?> block, MoveOp move) {
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
631 assert isVariable(move.getResult()) : "LinearScan inserts only moves to variables: " + move;
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
632
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
633 Interval curInterval = intervalFor(move.getResult());
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
634
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
635 if (!isRegister(curInterval.location()) && curInterval.alwaysInMemory()) {
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
636 assert isStackSlotValue(curInterval.location()) : "Not a stack slot: " + curInterval.location();
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
637 return true;
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
638 }
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
639 return false;
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
640 }
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
641
13340
9423a38d6437 added rematerialization of constants in LinearScan, but still disabled
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13339
diff changeset
642 private static void checkIntervals(Interval interval) {
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
643 Interval prev = null;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
644 Interval temp = interval;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
645 while (temp != Interval.EndMarker) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
646 assert temp.spillDefinitionPos() > 0 : "invalid spill definition pos";
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
647 if (prev != null) {
16379
c5257d58b71a LSRA spill optimization: backout changesets obsoleted by eager spill move placement.
Josef Eisl <josef.eisl@jku.at>
parents: 16378
diff changeset
648 assert temp.from() >= prev.from() : "intervals not sorted";
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
649 assert temp.spillDefinitionPos() >= prev.spillDefinitionPos() : "when intervals are sorted by from : then they must also be sorted by spillDefinitionPos";
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
650 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
651
13340
9423a38d6437 added rematerialization of constants in LinearScan, but still disabled
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13339
diff changeset
652 assert temp.spillSlot() != null || temp.canMaterialize() : "interval has no spill slot assigned";
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
653 assert temp.spillDefinitionPos() >= temp.from() : "invalid order";
16379
c5257d58b71a LSRA spill optimization: backout changesets obsoleted by eager spill move placement.
Josef Eisl <josef.eisl@jku.at>
parents: 16378
diff changeset
654 assert temp.spillDefinitionPos() <= temp.from() + 2 : "only intervals defined once at their start-pos can be optimized";
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
655
20980
abc059cb0acf Guard usages of Debug.log in LinearScan
Tom Rodriguez <tom.rodriguez@oracle.com>
parents: 20979
diff changeset
656 if (Debug.isLogEnabled()) {
abc059cb0acf Guard usages of Debug.log in LinearScan
Tom Rodriguez <tom.rodriguez@oracle.com>
parents: 20979
diff changeset
657 Debug.log("interval %d (from %d to %d) must be stored at %d", temp.operandNumber, temp.from(), temp.to(), temp.spillDefinitionPos());
abc059cb0acf Guard usages of Debug.log in LinearScan
Tom Rodriguez <tom.rodriguez@oracle.com>
parents: 20979
diff changeset
658 }
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
659
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
660 prev = temp;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
661 temp = temp.next;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
662 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
663 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
664
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
665 /**
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
666 * Determines the register priority for an instruction's output/result operand.
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
667 */
4206
430b5db3e6f8 Remove CiVariable from the CRI
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4199
diff changeset
668 static RegisterPriority registerPriorityOfOutputOperand(LIRInstruction op) {
4323
df5547057954 Remove LIROpcode and use non-anonymous subclasses of LIRInstruction
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4265
diff changeset
669 if (op instanceof MoveOp) {
df5547057954 Remove LIROpcode and use non-anonymous subclasses of LIRInstruction
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4265
diff changeset
670 MoveOp move = (MoveOp) op;
8353
98b90a7bb764 Only stack slots in caller frame are method arguments. Also optimize object arguments when the runtime supports it.
Christian Wimmer <christian.wimmer@oracle.com>
parents: 8222
diff changeset
671 if (optimizeMethodArgument(move.getInput())) {
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
672 return RegisterPriority.None;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
673 }
21236
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
674 } else if (op instanceof LabelOp) {
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
675 LabelOp label = (LabelOp) op;
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
676 if (label.isPhiIn()) {
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
677 return RegisterPriority.None;
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
678 }
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
679 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
680
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
681 // all other operands require a register
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
682 return RegisterPriority.MustHaveRegister;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
683 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
684
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
685 /**
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7512
diff changeset
686 * Determines the priority which with an instruction's input operand will be allocated a
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7512
diff changeset
687 * register.
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
688 */
4245
75c620f90ab9 Support stack-operands and register hints in new register allocator API
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4214
diff changeset
689 static RegisterPriority registerPriorityOfInputOperand(EnumSet<OperandFlag> flags) {
5733
141b15521a39 use annotated fields for operands of LIR instructions
Christian Wimmer <christian.wimmer@oracle.com>
parents: 5711
diff changeset
690 if (flags.contains(OperandFlag.STACK)) {
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
691 return RegisterPriority.ShouldHaveRegister;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
692 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
693 // all other operands require a register
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
694 return RegisterPriority.MustHaveRegister;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
695 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
696
21316
fd18bffefcc1 LinearScan: outsource LifetimeAnalysis.
Josef Eisl <josef.eisl@jku.at>
parents: 21315
diff changeset
697 static boolean optimizeMethodArgument(Value value) {
8402
c0db24536e97 Remove flag and optimization for object method arguments in the register allocator. Needs more investigation of GC impact on HotSpot
Christian Wimmer <christian.wimmer@oracle.com>
parents: 8353
diff changeset
698 /*
c0db24536e97 Remove flag and optimization for object method arguments in the register allocator. Needs more investigation of GC impact on HotSpot
Christian Wimmer <christian.wimmer@oracle.com>
parents: 8353
diff changeset
699 * Object method arguments that are passed on the stack are currently not optimized because
c0db24536e97 Remove flag and optimization for object method arguments in the register allocator. Needs more investigation of GC impact on HotSpot
Christian Wimmer <christian.wimmer@oracle.com>
parents: 8353
diff changeset
700 * this requires that the runtime visits method arguments during stack walking.
c0db24536e97 Remove flag and optimization for object method arguments in the register allocator. Needs more investigation of GC impact on HotSpot
Christian Wimmer <christian.wimmer@oracle.com>
parents: 8353
diff changeset
701 */
c0db24536e97 Remove flag and optimization for object method arguments in the register allocator. Needs more investigation of GC impact on HotSpot
Christian Wimmer <christian.wimmer@oracle.com>
parents: 8353
diff changeset
702 return isStackSlot(value) && asStackSlot(value).isInCallerFrame() && value.getKind() != Kind.Object;
8353
98b90a7bb764 Only stack slots in caller frame are method arguments. Also optimize object arguments when the runtime supports it.
Christian Wimmer <christian.wimmer@oracle.com>
parents: 8222
diff changeset
703 }
98b90a7bb764 Only stack slots in caller frame are method arguments. Also optimize object arguments when the runtime supports it.
Christian Wimmer <christian.wimmer@oracle.com>
parents: 8222
diff changeset
704
21316
fd18bffefcc1 LinearScan: outsource LifetimeAnalysis.
Josef Eisl <josef.eisl@jku.at>
parents: 21315
diff changeset
705 boolean isProcessed(Value operand) {
fd18bffefcc1 LinearScan: outsource LifetimeAnalysis.
Josef Eisl <josef.eisl@jku.at>
parents: 21315
diff changeset
706 return !isRegister(operand) || attributes(asRegister(operand)).isAllocatable();
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
707 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
708
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
709 // * Phase 5: actual register allocation
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
710
4142
bc8527f3071c Adjust code base to new level of warnings.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 3733
diff changeset
711 private static boolean isSorted(Interval[] intervals) {
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
712 int from = -1;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
713 for (Interval interval : intervals) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
714 assert interval != null;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
715 assert from <= interval.from();
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
716 from = interval.from();
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
717 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
718 return true;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
719 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
720
4142
bc8527f3071c Adjust code base to new level of warnings.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 3733
diff changeset
721 static Interval addToList(Interval first, Interval prev, Interval interval) {
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
722 Interval newFirst = first;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
723 if (prev != null) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
724 prev.next = interval;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
725 } else {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
726 newFirst = interval;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
727 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
728 return newFirst;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
729 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
730
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
731 Interval.Pair createUnhandledLists(IntervalPredicate isList1, IntervalPredicate isList2) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
732 assert isSorted(sortedIntervals) : "interval list is not sorted";
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
734 Interval list1 = Interval.EndMarker;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
735 Interval list2 = Interval.EndMarker;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
736
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
737 Interval list1Prev = null;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
738 Interval list2Prev = null;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
739 Interval v;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
740
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
741 int n = sortedIntervals.length;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
742 for (int i = 0; i < n; i++) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
743 v = sortedIntervals[i];
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
744 if (v == null) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
745 continue;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
746 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
747
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
748 if (isList1.apply(v)) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
749 list1 = addToList(list1, list1Prev, v);
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
750 list1Prev = v;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
751 } else if (isList2 == null || isList2.apply(v)) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
752 list2 = addToList(list2, list2Prev, v);
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
753 list2Prev = v;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
754 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
755 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
756
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
757 if (list1Prev != null) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
758 list1Prev.next = Interval.EndMarker;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
759 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
760 if (list2Prev != null) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
761 list2Prev.next = Interval.EndMarker;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
762 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
763
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
764 assert list1Prev == null || list1Prev.next == Interval.EndMarker : "linear list ends not with sentinel";
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
765 assert list2Prev == null || list2Prev.next == Interval.EndMarker : "linear list ends not with sentinel";
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
766
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
767 return new Interval.Pair(list1, list2);
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
768 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
769
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
770 void sortIntervalsBeforeAllocation() {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
771 int sortedLen = 0;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
772 for (Interval interval : intervals) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
773 if (interval != null) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
774 sortedLen++;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
775 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
776 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
777
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
778 Interval[] sortedList = new Interval[sortedLen];
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
779 int sortedIdx = 0;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
780 int sortedFromMax = -1;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
781
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
782 // special sorting algorithm: the original interval-list is almost sorted,
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
783 // only some intervals are swapped. So this is much faster than a complete QuickSort
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
784 for (Interval interval : intervals) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
785 if (interval != null) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
786 int from = interval.from();
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
787
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
788 if (sortedFromMax <= from) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
789 sortedList[sortedIdx++] = interval;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
790 sortedFromMax = interval.from();
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
791 } else {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
792 // the assumption that the intervals are already sorted failed,
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
793 // so this interval must be sorted in manually
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
794 int j;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
795 for (j = sortedIdx - 1; j >= 0 && from < sortedList[j].from(); j--) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
796 sortedList[j + 1] = sortedList[j];
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
797 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
798 sortedList[j + 1] = interval;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
799 sortedIdx++;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
800 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
801 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
802 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
803 sortedIntervals = sortedList;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
804 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
805
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
806 void sortIntervalsAfterAllocation() {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
807 if (firstDerivedIntervalIndex == -1) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
808 // no intervals have been added during allocation, so sorted list is already up to date
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
809 return;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
810 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
811
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
812 Interval[] oldList = sortedIntervals;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
813 Interval[] newList = Arrays.copyOfRange(intervals, firstDerivedIntervalIndex, intervalsSize);
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
814 int oldLen = oldList.length;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
815 int newLen = newList.length;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
816
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
817 // conventional sort-algorithm for new intervals
15886
e5e7d9dfff1a LinearScan: Clean up interval comparator and replace with lambda form.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 15885
diff changeset
818 Arrays.sort(newList, (Interval a, Interval b) -> a.from() - b.from());
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
819
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
820 // merge old and new list (both already sorted) into one combined list
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
821 Interval[] combinedList = new Interval[oldLen + newLen];
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
822 int oldIdx = 0;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
823 int newIdx = 0;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
824
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
825 while (oldIdx + newIdx < combinedList.length) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
826 if (newIdx >= newLen || (oldIdx < oldLen && oldList[oldIdx].from() <= newList[newIdx].from())) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
827 combinedList[oldIdx + newIdx] = oldList[oldIdx];
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
828 oldIdx++;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
829 } else {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
830 combinedList[oldIdx + newIdx] = newList[newIdx];
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
831 newIdx++;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
832 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
833 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
834
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
835 sortedIntervals = combinedList;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
836 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
837
19212
95a7954ea155 Add LinearScanPhase.
Josef Eisl <josef.eisl@jku.at>
parents: 19166
diff changeset
838 void allocateRegisters() {
14871
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14841
diff changeset
839 try (Indent indent = Debug.logAndIndent("allocate registers")) {
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14841
diff changeset
840 Interval precoloredIntervals;
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14841
diff changeset
841 Interval notPrecoloredIntervals;
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
842
14871
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14841
diff changeset
843 Interval.Pair result = createUnhandledLists(IS_PRECOLORED_INTERVAL, IS_VARIABLE_INTERVAL);
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14841
diff changeset
844 precoloredIntervals = result.first;
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14841
diff changeset
845 notPrecoloredIntervals = result.second;
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
846
14871
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14841
diff changeset
847 // allocate cpu registers
15927
96229f219351 LSRA: add OptimizingLinearScanWalker.
Josef Eisl <josef.eisl@jku.at>
parents: 15920
diff changeset
848 LinearScanWalker lsw;
96229f219351 LSRA: add OptimizingLinearScanWalker.
Josef Eisl <josef.eisl@jku.at>
parents: 15920
diff changeset
849 if (OptimizingLinearScanWalker.Options.LSRAOptimization.getValue()) {
96229f219351 LSRA: add OptimizingLinearScanWalker.
Josef Eisl <josef.eisl@jku.at>
parents: 15920
diff changeset
850 lsw = new OptimizingLinearScanWalker(this, precoloredIntervals, notPrecoloredIntervals);
96229f219351 LSRA: add OptimizingLinearScanWalker.
Josef Eisl <josef.eisl@jku.at>
parents: 15920
diff changeset
851 } else {
96229f219351 LSRA: add OptimizingLinearScanWalker.
Josef Eisl <josef.eisl@jku.at>
parents: 15920
diff changeset
852 lsw = new LinearScanWalker(this, precoloredIntervals, notPrecoloredIntervals);
96229f219351 LSRA: add OptimizingLinearScanWalker.
Josef Eisl <josef.eisl@jku.at>
parents: 15920
diff changeset
853 }
14871
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14841
diff changeset
854 lsw.walk();
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14841
diff changeset
855 lsw.finishAllocation();
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14841
diff changeset
856 }
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
857 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
858
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
859 // * Phase 6: resolve data flow
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
860 // (insert moves at edges between blocks if intervals have been split)
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
861
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
862 // wrapper for Interval.splitChildAtOpId that performs a bailout in product mode
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
863 // instead of returning null
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
864 Interval splitChildAtOpId(Interval interval, int opId, LIRInstruction.OperandMode mode) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
865 Interval result = interval.getSplitChildAtOpId(opId, mode, this);
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
866
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
867 if (result != null) {
20980
abc059cb0acf Guard usages of Debug.log in LinearScan
Tom Rodriguez <tom.rodriguez@oracle.com>
parents: 20979
diff changeset
868 if (Debug.isLogEnabled()) {
abc059cb0acf Guard usages of Debug.log in LinearScan
Tom Rodriguez <tom.rodriguez@oracle.com>
parents: 20979
diff changeset
869 Debug.log("Split child at pos %d of interval %s is %s", opId, interval, result);
abc059cb0acf Guard usages of Debug.log in LinearScan
Tom Rodriguez <tom.rodriguez@oracle.com>
parents: 20979
diff changeset
870 }
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
871 return result;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
872 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
873
5547
b6617d13ea44 Dropping Ci* prefixes. Some additional renamings in the api.code interface.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 5542
diff changeset
874 throw new BailoutException("LinearScan: interval is null");
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
875 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
876
21236
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
877 void resolveCollectMappings(AbstractBlockBase<?> fromBlock, AbstractBlockBase<?> toBlock, AbstractBlockBase<?> midBlock, MoveResolver moveResolver) {
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
878 assert moveResolver.checkEmpty();
21236
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
879 assert midBlock == null ||
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
880 (midBlock.getPredecessorCount() == 1 && midBlock.getSuccessorCount() == 1 && midBlock.getPredecessors().get(0).equals(fromBlock) && midBlock.getSuccessors().get(0).equals(
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
881 toBlock));
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
882
20979
65d8d305f9c0 Minor linear scan tweaks
Tom Rodriguez <tom.rodriguez@oracle.com>
parents: 20915
diff changeset
883 int toBlockFirstInstructionId = getFirstLirInstructionId(toBlock);
65d8d305f9c0 Minor linear scan tweaks
Tom Rodriguez <tom.rodriguez@oracle.com>
parents: 20915
diff changeset
884 int fromBlockLastInstructionId = getLastLirInstructionId(fromBlock) + 1;
4206
430b5db3e6f8 Remove CiVariable from the CRI
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4199
diff changeset
885 int numOperands = operandSize();
5541
b4c406861c33 More renamings to drop Ri* prefix completely. Deleted graph.BitMap class and replaced with java.util.BitSet.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 5540
diff changeset
886 BitSet liveAtEdge = blockData.get(toBlock).liveIn;
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
887
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
888 // visit all variables for which the liveAtEdge bit is set
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
889 for (int operandNum = liveAtEdge.nextSetBit(0); operandNum >= 0; operandNum = liveAtEdge.nextSetBit(operandNum + 1)) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
890 assert operandNum < numOperands : "live information set for not exisiting interval";
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4394
diff changeset
891 assert blockData.get(fromBlock).liveOut.get(operandNum) && blockData.get(toBlock).liveIn.get(operandNum) : "interval not live at this edge";
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
892
20979
65d8d305f9c0 Minor linear scan tweaks
Tom Rodriguez <tom.rodriguez@oracle.com>
parents: 20915
diff changeset
893 Interval fromInterval = splitChildAtOpId(intervalFor(operandNum), fromBlockLastInstructionId, LIRInstruction.OperandMode.DEF);
65d8d305f9c0 Minor linear scan tweaks
Tom Rodriguez <tom.rodriguez@oracle.com>
parents: 20915
diff changeset
894 Interval toInterval = splitChildAtOpId(intervalFor(operandNum), toBlockFirstInstructionId, LIRInstruction.OperandMode.DEF);
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
895
9632
97db51025787 Value: use `equals()' instead of object equality
Bernhard Urban <bernhard.urban@jku.at>
parents: 9628
diff changeset
896 if (fromInterval != toInterval && !fromInterval.location().equals(toInterval.location())) {
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
897 // need to insert move instruction
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
898 moveResolver.addMapping(fromInterval, toInterval);
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
899 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
900 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
901 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
902
19560
4d70d150944f Remove AbstractBlock interface.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 19212
diff changeset
903 void resolveFindInsertPos(AbstractBlockBase<?> fromBlock, AbstractBlockBase<?> toBlock, MoveResolver moveResolver) {
7497
0f8c6dbf68be Code clean up and documentation for ComputeBlockOrder class.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 6582
diff changeset
904 if (fromBlock.getSuccessorCount() <= 1) {
20980
abc059cb0acf Guard usages of Debug.log in LinearScan
Tom Rodriguez <tom.rodriguez@oracle.com>
parents: 20979
diff changeset
905 if (Debug.isLogEnabled()) {
abc059cb0acf Guard usages of Debug.log in LinearScan
Tom Rodriguez <tom.rodriguez@oracle.com>
parents: 20979
diff changeset
906 Debug.log("inserting moves at end of fromBlock B%d", fromBlock.getId());
abc059cb0acf Guard usages of Debug.log in LinearScan
Tom Rodriguez <tom.rodriguez@oracle.com>
parents: 20979
diff changeset
907 }
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
908
14806
a8723f1ff542 LIR renamed setter and getter functions.
Josef Eisl <josef.eisl@jku.at>
parents: 14789
diff changeset
909 List<LIRInstruction> instructions = ir.getLIRforBlock(fromBlock);
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
910 LIRInstruction instr = instructions.get(instructions.size() - 1);
4323
df5547057954 Remove LIROpcode and use non-anonymous subclasses of LIRInstruction
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4265
diff changeset
911 if (instr instanceof StandardOp.JumpOp) {
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
912 // insert moves before branch
6411
c5afcc2ebd3d change of project structure: separate compiler and LIR, put EA into separate project
Lukas Stadler <lukas.stadler@jku.at>
parents: 6352
diff changeset
913 moveResolver.setInsertPosition(instructions, instructions.size() - 1);
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
914 } else {
6411
c5afcc2ebd3d change of project structure: separate compiler and LIR, put EA into separate project
Lukas Stadler <lukas.stadler@jku.at>
parents: 6352
diff changeset
915 moveResolver.setInsertPosition(instructions, instructions.size());
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
916 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
917
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
918 } else {
20980
abc059cb0acf Guard usages of Debug.log in LinearScan
Tom Rodriguez <tom.rodriguez@oracle.com>
parents: 20979
diff changeset
919 if (Debug.isLogEnabled()) {
abc059cb0acf Guard usages of Debug.log in LinearScan
Tom Rodriguez <tom.rodriguez@oracle.com>
parents: 20979
diff changeset
920 Debug.log("inserting moves at beginning of toBlock B%d", toBlock.getId());
abc059cb0acf Guard usages of Debug.log in LinearScan
Tom Rodriguez <tom.rodriguez@oracle.com>
parents: 20979
diff changeset
921 }
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
922
9855
6898d8995866 converted more options from GraalOptions to new system (GRAAL-27)
Doug Simon <doug.simon@oracle.com>
parents: 9632
diff changeset
923 if (DetailedAsserts.getValue()) {
14806
a8723f1ff542 LIR renamed setter and getter functions.
Josef Eisl <josef.eisl@jku.at>
parents: 14789
diff changeset
924 assert ir.getLIRforBlock(fromBlock).get(0) instanceof StandardOp.LabelOp : "block does not start with a label";
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
925
21319
9ddb5a749eab LinearScan: use multiline comments.
Josef Eisl <josef.eisl@jku.at>
parents: 21318
diff changeset
926 /*
9ddb5a749eab LinearScan: use multiline comments.
Josef Eisl <josef.eisl@jku.at>
parents: 21318
diff changeset
927 * Because the number of predecessor edges matches the number of successor edges,
9ddb5a749eab LinearScan: use multiline comments.
Josef Eisl <josef.eisl@jku.at>
parents: 21318
diff changeset
928 * blocks which are reached by switch statements may have be more than one
9ddb5a749eab LinearScan: use multiline comments.
Josef Eisl <josef.eisl@jku.at>
parents: 21318
diff changeset
929 * predecessor but it will be guaranteed that all predecessors will be the same.
9ddb5a749eab LinearScan: use multiline comments.
Josef Eisl <josef.eisl@jku.at>
parents: 21318
diff changeset
930 */
19560
4d70d150944f Remove AbstractBlock interface.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 19212
diff changeset
931 for (AbstractBlockBase<?> predecessor : toBlock.getPredecessors()) {
7497
0f8c6dbf68be Code clean up and documentation for ComputeBlockOrder class.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 6582
diff changeset
932 assert fromBlock == predecessor : "all critical edges must be broken";
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
933 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
934 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
935
14806
a8723f1ff542 LIR renamed setter and getter functions.
Josef Eisl <josef.eisl@jku.at>
parents: 14789
diff changeset
936 moveResolver.setInsertPosition(ir.getLIRforBlock(toBlock), 1);
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
937 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
938 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
939
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
940 /**
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
941 * Inserts necessary moves (spilling or reloading) at edges between blocks for intervals that
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
942 * have been split.
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
943 */
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
944 void resolveDataFlow() {
14871
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14841
diff changeset
945 try (Indent indent = Debug.logAndIndent("resolve data flow")) {
13340
9423a38d6437 added rematerialization of constants in LinearScan, but still disabled
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13339
diff changeset
946
14871
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14841
diff changeset
947 int numBlocks = blockCount();
21203
9f45587ad8f5 LinearScan: add createMoveResolver().
Josef Eisl <josef.eisl@jku.at>
parents: 21193
diff changeset
948 MoveResolver moveResolver = createMoveResolver();
14871
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14841
diff changeset
949 BitSet blockCompleted = new BitSet(numBlocks);
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14841
diff changeset
950 BitSet alreadyResolved = new BitSet(numBlocks);
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14841
diff changeset
951
19560
4d70d150944f Remove AbstractBlock interface.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 19212
diff changeset
952 for (AbstractBlockBase<?> block : sortedBlocks) {
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
953
14871
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14841
diff changeset
954 // check if block has only one predecessor and only one successor
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14841
diff changeset
955 if (block.getPredecessorCount() == 1 && block.getSuccessorCount() == 1) {
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14841
diff changeset
956 List<LIRInstruction> instructions = ir.getLIRforBlock(block);
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14841
diff changeset
957 assert instructions.get(0) instanceof StandardOp.LabelOp : "block must start with label";
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14841
diff changeset
958 assert instructions.get(instructions.size() - 1) instanceof StandardOp.JumpOp : "block with successor must end with unconditional jump";
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
959
14871
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14841
diff changeset
960 // check if block is empty (only label and branch)
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14841
diff changeset
961 if (instructions.size() == 2) {
19560
4d70d150944f Remove AbstractBlock interface.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 19212
diff changeset
962 AbstractBlockBase<?> pred = block.getPredecessors().iterator().next();
4d70d150944f Remove AbstractBlock interface.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 19212
diff changeset
963 AbstractBlockBase<?> sux = block.getSuccessors().iterator().next();
14871
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14841
diff changeset
964
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14841
diff changeset
965 // prevent optimization of two consecutive blocks
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14841
diff changeset
966 if (!blockCompleted.get(pred.getLinearScanNumber()) && !blockCompleted.get(sux.getLinearScanNumber())) {
20980
abc059cb0acf Guard usages of Debug.log in LinearScan
Tom Rodriguez <tom.rodriguez@oracle.com>
parents: 20979
diff changeset
967 if (Debug.isLogEnabled()) {
abc059cb0acf Guard usages of Debug.log in LinearScan
Tom Rodriguez <tom.rodriguez@oracle.com>
parents: 20979
diff changeset
968 Debug.log(" optimizing empty block B%d (pred: B%d, sux: B%d)", block.getId(), pred.getId(), sux.getId());
abc059cb0acf Guard usages of Debug.log in LinearScan
Tom Rodriguez <tom.rodriguez@oracle.com>
parents: 20979
diff changeset
969 }
14871
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14841
diff changeset
970
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14841
diff changeset
971 blockCompleted.set(block.getLinearScanNumber());
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
972
21319
9ddb5a749eab LinearScan: use multiline comments.
Josef Eisl <josef.eisl@jku.at>
parents: 21318
diff changeset
973 /*
9ddb5a749eab LinearScan: use multiline comments.
Josef Eisl <josef.eisl@jku.at>
parents: 21318
diff changeset
974 * Directly resolve between pred and sux (without looking at the empty
9ddb5a749eab LinearScan: use multiline comments.
Josef Eisl <josef.eisl@jku.at>
parents: 21318
diff changeset
975 * block between).
9ddb5a749eab LinearScan: use multiline comments.
Josef Eisl <josef.eisl@jku.at>
parents: 21318
diff changeset
976 */
21236
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
977 resolveCollectMappings(pred, sux, block, moveResolver);
14871
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14841
diff changeset
978 if (moveResolver.hasMappings()) {
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14841
diff changeset
979 moveResolver.setInsertPosition(instructions, 1);
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14841
diff changeset
980 moveResolver.resolveAndAppendMoves();
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14841
diff changeset
981 }
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14841
diff changeset
982 }
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14841
diff changeset
983 }
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14841
diff changeset
984 }
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14841
diff changeset
985 }
13467
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
986
19560
4d70d150944f Remove AbstractBlock interface.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 19212
diff changeset
987 for (AbstractBlockBase<?> fromBlock : sortedBlocks) {
14871
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14841
diff changeset
988 if (!blockCompleted.get(fromBlock.getLinearScanNumber())) {
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14841
diff changeset
989 alreadyResolved.clear();
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14841
diff changeset
990 alreadyResolved.or(blockCompleted);
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14841
diff changeset
991
19560
4d70d150944f Remove AbstractBlock interface.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 19212
diff changeset
992 for (AbstractBlockBase<?> toBlock : fromBlock.getSuccessors()) {
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
993
21319
9ddb5a749eab LinearScan: use multiline comments.
Josef Eisl <josef.eisl@jku.at>
parents: 21318
diff changeset
994 /*
9ddb5a749eab LinearScan: use multiline comments.
Josef Eisl <josef.eisl@jku.at>
parents: 21318
diff changeset
995 * Check for duplicate edges between the same blocks (can happen with switch
9ddb5a749eab LinearScan: use multiline comments.
Josef Eisl <josef.eisl@jku.at>
parents: 21318
diff changeset
996 * blocks).
9ddb5a749eab LinearScan: use multiline comments.
Josef Eisl <josef.eisl@jku.at>
parents: 21318
diff changeset
997 */
14871
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14841
diff changeset
998 if (!alreadyResolved.get(toBlock.getLinearScanNumber())) {
20980
abc059cb0acf Guard usages of Debug.log in LinearScan
Tom Rodriguez <tom.rodriguez@oracle.com>
parents: 20979
diff changeset
999 if (Debug.isLogEnabled()) {
abc059cb0acf Guard usages of Debug.log in LinearScan
Tom Rodriguez <tom.rodriguez@oracle.com>
parents: 20979
diff changeset
1000 Debug.log("processing edge between B%d and B%d", fromBlock.getId(), toBlock.getId());
abc059cb0acf Guard usages of Debug.log in LinearScan
Tom Rodriguez <tom.rodriguez@oracle.com>
parents: 20979
diff changeset
1001 }
14871
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14841
diff changeset
1002
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14841
diff changeset
1003 alreadyResolved.set(toBlock.getLinearScanNumber());
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14841
diff changeset
1004
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14841
diff changeset
1005 // collect all intervals that have been split between
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14841
diff changeset
1006 // fromBlock and toBlock
21236
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
1007 resolveCollectMappings(fromBlock, toBlock, null, moveResolver);
14871
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14841
diff changeset
1008 if (moveResolver.hasMappings()) {
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14841
diff changeset
1009 resolveFindInsertPos(fromBlock, toBlock, moveResolver);
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14841
diff changeset
1010 moveResolver.resolveAndAppendMoves();
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14841
diff changeset
1011 }
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1012 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1013 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1014 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1015 }
21236
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
1016
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1017 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1018 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1019
18425
b856446ff7e0 Introduce StackSlotValue and VirtualStackSlot.
Josef Eisl <josef.eisl@jku.at>
parents: 18420
diff changeset
1020 static StackSlotValue canonicalSpillOpr(Interval interval) {
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1021 assert interval.spillSlot() != null : "canonical spill slot not set";
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1022 return interval.spillSlot();
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1023 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1024
13377
40530019af02 enable rematerialization of constants in LinearScan, including a bug fix
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13376
diff changeset
1025 private boolean isMaterialized(AllocatableValue operand, int opId, OperandMode mode) {
40530019af02 enable rematerialization of constants in LinearScan, including a bug fix
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13376
diff changeset
1026 Interval interval = intervalFor(operand);
40530019af02 enable rematerialization of constants in LinearScan, including a bug fix
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13376
diff changeset
1027 assert interval != null : "interval must exist";
40530019af02 enable rematerialization of constants in LinearScan, including a bug fix
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13376
diff changeset
1028
40530019af02 enable rematerialization of constants in LinearScan, including a bug fix
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13376
diff changeset
1029 if (opId != -1) {
21319
9ddb5a749eab LinearScan: use multiline comments.
Josef Eisl <josef.eisl@jku.at>
parents: 21318
diff changeset
1030 /*
9ddb5a749eab LinearScan: use multiline comments.
Josef Eisl <josef.eisl@jku.at>
parents: 21318
diff changeset
1031 * Operands are not changed when an interval is split during allocation, so search the
9ddb5a749eab LinearScan: use multiline comments.
Josef Eisl <josef.eisl@jku.at>
parents: 21318
diff changeset
1032 * right interval here.
9ddb5a749eab LinearScan: use multiline comments.
Josef Eisl <josef.eisl@jku.at>
parents: 21318
diff changeset
1033 */
13377
40530019af02 enable rematerialization of constants in LinearScan, including a bug fix
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13376
diff changeset
1034 interval = splitChildAtOpId(interval, opId, mode);
40530019af02 enable rematerialization of constants in LinearScan, including a bug fix
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13376
diff changeset
1035 }
40530019af02 enable rematerialization of constants in LinearScan, including a bug fix
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13376
diff changeset
1036
40530019af02 enable rematerialization of constants in LinearScan, including a bug fix
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13376
diff changeset
1037 return isIllegal(interval.location()) && interval.canMaterialize();
40530019af02 enable rematerialization of constants in LinearScan, including a bug fix
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13376
diff changeset
1038 }
40530019af02 enable rematerialization of constants in LinearScan, including a bug fix
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13376
diff changeset
1039
13340
9423a38d6437 added rematerialization of constants in LinearScan, but still disabled
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13339
diff changeset
1040 protected IntervalWalker initIntervalWalker(IntervalPredicate predicate) {
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1041 // setup lists of potential oops for walking
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1042 Interval oopIntervals;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1043 Interval nonOopIntervals;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1044
13340
9423a38d6437 added rematerialization of constants in LinearScan, but still disabled
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13339
diff changeset
1045 oopIntervals = createUnhandledLists(predicate, null).first;
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1046
21319
9ddb5a749eab LinearScan: use multiline comments.
Josef Eisl <josef.eisl@jku.at>
parents: 21318
diff changeset
1047 /*
9ddb5a749eab LinearScan: use multiline comments.
Josef Eisl <josef.eisl@jku.at>
parents: 21318
diff changeset
1048 * Intervals that have no oops inside need not to be processed. to ensure a walking until
9ddb5a749eab LinearScan: use multiline comments.
Josef Eisl <josef.eisl@jku.at>
parents: 21318
diff changeset
1049 * the last instruction id, add a dummy interval with a high operation id.
9ddb5a749eab LinearScan: use multiline comments.
Josef Eisl <josef.eisl@jku.at>
parents: 21318
diff changeset
1050 */
6539
2463eb24b644 Cleanup of Graal API: Rename methods so that it follows the getXxx naming convention and so that they are similar to the names of the java.lang.reflect classes. Remove unused methods.
Christian Wimmer <christian.wimmer@oracle.com>
parents: 6529
diff changeset
1051 nonOopIntervals = new Interval(Value.ILLEGAL, -1);
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1052 nonOopIntervals.addRange(Integer.MAX_VALUE - 2, Integer.MAX_VALUE - 1);
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1053
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1054 return new IntervalWalker(this, oopIntervals, nonOopIntervals);
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1055 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1056
5539
bc647d8b0080 Renaming RiValue => Value.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 5536
diff changeset
1057 private boolean isCallerSave(Value operand) {
5552
69a8969dbf40 Reduce public fields in api.code project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 5547
diff changeset
1058 return attributes(asRegister(operand)).isCallerSave();
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1059 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1060
21320
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1061 /** Phase 7: assign register numbers back to LIR */
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1062 private final class AssignLocations extends AllocationPhase {
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1063
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1064 @Override
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1065 protected <B extends AbstractBlockBase<B>> void run(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder,
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1066 SpillMoveFactory spillMoveFactory) {
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1067 assignLocations();
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1068 }
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1069
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1070 /**
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1071 * Assigns the allocated location for an LIR instruction operand back into the instruction.
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1072 *
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1073 * @param operand an LIR instruction operand
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1074 * @param opId the id of the LIR instruction using {@code operand}
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1075 * @param mode the usage mode for {@code operand} by the instruction
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1076 * @return the location assigned for the operand
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1077 */
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1078 private Value colorLirOperand(Variable operand, int opId, OperandMode mode) {
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1079 Interval interval = intervalFor(operand);
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1080 assert interval != null : "interval must exist";
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1081
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1082 if (opId != -1) {
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1083 if (DetailedAsserts.getValue()) {
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1084 AbstractBlockBase<?> block = blockForId(opId);
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1085 if (block.getSuccessorCount() <= 1 && opId == getLastLirInstructionId(block)) {
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1086 /*
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1087 * Check if spill moves could have been appended at the end of this block,
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1088 * but before the branch instruction. So the split child information for
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1089 * this branch would be incorrect.
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1090 */
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1091 LIRInstruction instr = ir.getLIRforBlock(block).get(ir.getLIRforBlock(block).size() - 1);
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1092 if (instr instanceof StandardOp.JumpOp) {
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1093 if (blockData.get(block).liveOut.get(operandNumber(operand))) {
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1094 assert false : String.format(
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1095 "can't get split child for the last branch of a block because the information would be incorrect (moves are inserted before the branch in resolveDataFlow) block=%s, instruction=%s, operand=%s",
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1096 block, instr, operand);
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1097 }
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1098 }
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1099 }
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1100 }
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1101
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1102 /*
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1103 * Operands are not changed when an interval is split during allocation, so search
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1104 * the right interval here.
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1105 */
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1106 interval = splitChildAtOpId(interval, opId, mode);
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1107 }
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1108
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1109 if (isIllegal(interval.location()) && interval.canMaterialize()) {
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1110 assert mode != OperandMode.DEF;
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1111 return interval.getMaterializedValue();
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1112 }
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1113 return interval.location();
18610
6a6291c31657 Add LocationMarker.
Josef Eisl <josef.eisl@jku.at>
parents: 18512
diff changeset
1114 }
21320
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1115
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1116 /**
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1117 * @param op
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1118 * @param operand
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1119 * @param valueMode
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1120 * @param flags
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1121 * @see InstructionValueProcedure#doValue(LIRInstruction, Value, OperandMode, EnumSet)
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1122 */
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1123 private Value debugInfoProcedure(LIRInstruction op, Value operand, OperandMode valueMode, EnumSet<OperandFlag> flags) {
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1124 if (isVirtualStackSlot(operand)) {
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1125 return operand;
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1126 }
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1127 int tempOpId = op.id();
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1128 OperandMode mode = OperandMode.USE;
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1129 AbstractBlockBase<?> block = blockForId(tempOpId);
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1130 if (block.getSuccessorCount() == 1 && tempOpId == getLastLirInstructionId(block)) {
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1131 /*
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1132 * Generating debug information for the last instruction of a block. If this
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1133 * instruction is a branch, spill moves are inserted before this branch and so the
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1134 * wrong operand would be returned (spill moves at block boundaries are not
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1135 * considered in the live ranges of intervals).
21322
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents: 21321
diff changeset
1136 *
21320
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1137 * Solution: use the first opId of the branch target block instead.
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1138 */
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1139 final LIRInstruction instr = ir.getLIRforBlock(block).get(ir.getLIRforBlock(block).size() - 1);
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1140 if (instr instanceof StandardOp.JumpOp) {
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1141 if (blockData.get(block).liveOut.get(operandNumber(operand))) {
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1142 tempOpId = getFirstLirInstructionId(block.getSuccessors().iterator().next());
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1143 mode = OperandMode.DEF;
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1144 }
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1145 }
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1146 }
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1147
21319
9ddb5a749eab LinearScan: use multiline comments.
Josef Eisl <josef.eisl@jku.at>
parents: 21318
diff changeset
1148 /*
21320
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1149 * Get current location of operand. The operand must be live because debug information
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1150 * is considered when building the intervals if the interval is not live,
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1151 * colorLirOperand will cause an assert on failure.
21319
9ddb5a749eab LinearScan: use multiline comments.
Josef Eisl <josef.eisl@jku.at>
parents: 21318
diff changeset
1152 */
21320
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1153 Value result = colorLirOperand((Variable) operand, tempOpId, mode);
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1154 assert !hasCall(tempOpId) || isStackSlotValue(result) || isConstant(result) || !isCallerSave(result) : "cannot have caller-save register operands at calls";
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1155 return result;
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1156 }
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1157
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1158 private void computeDebugInfo(final LIRInstruction op, LIRFrameState info) {
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1159 info.forEachState(op, this::debugInfoProcedure);
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1160 }
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1161
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1162 private void assignLocations(List<LIRInstruction> instructions) {
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1163 int numInst = instructions.size();
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1164 boolean hasDead = false;
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1165
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1166 InstructionValueProcedure assignProc = (op, operand, mode, flags) -> isVariable(operand) ? colorLirOperand((Variable) operand, op.id(), mode) : operand;
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1167 for (int j = 0; j < numInst; j++) {
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1168 final LIRInstruction op = instructions.get(j);
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1169 if (op == null) {
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1170 /*
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1171 * this can happen when spill-moves are removed in eliminateSpillMoves
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1172 */
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1173 hasDead = true;
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1174 continue;
16138
f315b1c0a590 Introduce InstructionValueProcedure.
Josef Eisl <josef.eisl@jku.at>
parents: 16118
diff changeset
1175 }
21320
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1176
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1177 // remove useless moves
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1178 MoveOp move = null;
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1179 if (op instanceof MoveOp) {
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1180 move = (MoveOp) op;
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1181 AllocatableValue result = move.getResult();
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1182 if (isVariable(result) && isMaterialized(result, op.id(), OperandMode.DEF)) {
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1183 /*
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1184 * This happens if a materializable interval is originally not spilled but
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1185 * then kicked out in LinearScanWalker.splitForSpilling(). When kicking out
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1186 * such an interval this move operation was already generated.
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1187 */
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1188 instructions.set(j, null);
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1189 hasDead = true;
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1190 continue;
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1191 }
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1192 }
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1193
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1194 op.forEachInput(assignProc);
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1195 op.forEachAlive(assignProc);
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1196 op.forEachTemp(assignProc);
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1197 op.forEachOutput(assignProc);
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1198
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1199 // compute reference map and debug information
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1200 op.forEachState((inst, state) -> computeDebugInfo(inst, state));
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1201
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1202 // remove useless moves
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1203 if (move != null) {
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1204 if (move.getInput().equals(move.getResult())) {
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1205 instructions.set(j, null);
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1206 hasDead = true;
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1207 }
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1208 }
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1209 }
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1210
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1211 if (hasDead) {
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1212 // Remove null values from the list.
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1213 instructions.removeAll(Collections.singleton(null));
16138
f315b1c0a590 Introduce InstructionValueProcedure.
Josef Eisl <josef.eisl@jku.at>
parents: 16118
diff changeset
1214 }
17298
831e96d0777d Better workaround for the uninitialized variable issue.
Josef Eisl <josef.eisl@jku.at>
parents: 17297
diff changeset
1215 }
17297
07d5cf34b3c5 Work around uninitialized variables problem with javac and lambdas.
Josef Eisl <josef.eisl@jku.at>
parents: 17294
diff changeset
1216
21320
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1217 private void assignLocations() {
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1218 try (Indent indent = Debug.logAndIndent("assign locations")) {
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1219 for (AbstractBlockBase<?> block : sortedBlocks) {
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1220 try (Indent indent2 = Debug.logAndIndent("assign locations in block B%d", block.getId())) {
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1221 assignLocations(ir.getLIRforBlock(block));
26beac81ab2f LinearScan: encapsulate assignLocations().
Josef Eisl <josef.eisl@jku.at>
parents: 21319
diff changeset
1222 }
13467
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1223 }
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1224 }
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1225 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1226 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1227
21315
5f4847feeb69 LinearScan: add createLifetimeAnalysis().
Josef Eisl <josef.eisl@jku.at>
parents: 21314
diff changeset
1228 protected LifetimeAnalysis createLifetimeAnalysis() {
5f4847feeb69 LinearScan: add createLifetimeAnalysis().
Josef Eisl <josef.eisl@jku.at>
parents: 21314
diff changeset
1229 return new LifetimeAnalysis(this);
5f4847feeb69 LinearScan: add createLifetimeAnalysis().
Josef Eisl <josef.eisl@jku.at>
parents: 21314
diff changeset
1230 }
5f4847feeb69 LinearScan: add createLifetimeAnalysis().
Josef Eisl <josef.eisl@jku.at>
parents: 21314
diff changeset
1231
21312
8ecb442fc864 LinearScan: split into sub-phases.
Josef Eisl <josef.eisl@jku.at>
parents: 21246
diff changeset
1232 <B extends AbstractBlockBase<B>> void allocate(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder, SpillMoveFactory spillMoveFactory) {
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1233
13467
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1234 /*
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1235 * This is the point to enable debug logging for the whole register allocation.
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1236 */
14871
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14841
diff changeset
1237 try (Indent indent = Debug.logAndIndent("LinearScan allocate")) {
21312
8ecb442fc864 LinearScan: split into sub-phases.
Josef Eisl <josef.eisl@jku.at>
parents: 21246
diff changeset
1238 AllocationContext context = new AllocationContext(spillMoveFactory);
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1239
21315
5f4847feeb69 LinearScan: add createLifetimeAnalysis().
Josef Eisl <josef.eisl@jku.at>
parents: 21314
diff changeset
1240 createLifetimeAnalysis().apply(target, lirGenRes, codeEmittingOrder, linearScanOrder, context, false);
21313
bb9d3f0616a3 LinearScan: reorganize LIR and Interval dumping.
Josef Eisl <josef.eisl@jku.at>
parents: 21312
diff changeset
1241 new RegisterAllocation().apply(target, lirGenRes, codeEmittingOrder, linearScanOrder, context, false);
bb9d3f0616a3 LinearScan: reorganize LIR and Interval dumping.
Josef Eisl <josef.eisl@jku.at>
parents: 21312
diff changeset
1242
21312
8ecb442fc864 LinearScan: split into sub-phases.
Josef Eisl <josef.eisl@jku.at>
parents: 21246
diff changeset
1243 if (LinearScan.Options.LSRAOptimizeSpillPosition.getValue()) {
21322
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents: 21321
diff changeset
1244 new OptimizeSpillPosition(this).apply(target, lirGenRes, codeEmittingOrder, linearScanOrder, context, false);
14871
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14841
diff changeset
1245 }
21312
8ecb442fc864 LinearScan: split into sub-phases.
Josef Eisl <josef.eisl@jku.at>
parents: 21246
diff changeset
1246 new ResolveDataFlow().apply(target, lirGenRes, codeEmittingOrder, linearScanOrder, context);
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7512
diff changeset
1247
21312
8ecb442fc864 LinearScan: split into sub-phases.
Josef Eisl <josef.eisl@jku.at>
parents: 21246
diff changeset
1248 sortIntervalsAfterAllocation();
8ecb442fc864 LinearScan: split into sub-phases.
Josef Eisl <josef.eisl@jku.at>
parents: 21246
diff changeset
1249
8ecb442fc864 LinearScan: split into sub-phases.
Josef Eisl <josef.eisl@jku.at>
parents: 21246
diff changeset
1250 if (DetailedAsserts.getValue()) {
8ecb442fc864 LinearScan: split into sub-phases.
Josef Eisl <josef.eisl@jku.at>
parents: 21246
diff changeset
1251 verify();
16357
a07492ccaf52 LSRA spill optimization: calculate optimized spill position.
Josef Eisl <josef.eisl@jku.at>
parents: 16355
diff changeset
1252 }
a07492ccaf52 LSRA spill optimization: calculate optimized spill position.
Josef Eisl <josef.eisl@jku.at>
parents: 16355
diff changeset
1253
21312
8ecb442fc864 LinearScan: split into sub-phases.
Josef Eisl <josef.eisl@jku.at>
parents: 21246
diff changeset
1254 new EliminateSpillMove().apply(target, lirGenRes, codeEmittingOrder, linearScanOrder, context);
8ecb442fc864 LinearScan: split into sub-phases.
Josef Eisl <josef.eisl@jku.at>
parents: 21246
diff changeset
1255 new AssignLocations().apply(target, lirGenRes, codeEmittingOrder, linearScanOrder, context);
21236
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
1256
21312
8ecb442fc864 LinearScan: split into sub-phases.
Josef Eisl <josef.eisl@jku.at>
parents: 21246
diff changeset
1257 if (DetailedAsserts.getValue()) {
8ecb442fc864 LinearScan: split into sub-phases.
Josef Eisl <josef.eisl@jku.at>
parents: 21246
diff changeset
1258 verifyIntervals();
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1259 }
14871
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14841
diff changeset
1260 }
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1261 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1262
21312
8ecb442fc864 LinearScan: split into sub-phases.
Josef Eisl <josef.eisl@jku.at>
parents: 21246
diff changeset
1263 private final class RegisterAllocation extends AllocationPhase {
8ecb442fc864 LinearScan: split into sub-phases.
Josef Eisl <josef.eisl@jku.at>
parents: 21246
diff changeset
1264
8ecb442fc864 LinearScan: split into sub-phases.
Josef Eisl <josef.eisl@jku.at>
parents: 21246
diff changeset
1265 @Override
8ecb442fc864 LinearScan: split into sub-phases.
Josef Eisl <josef.eisl@jku.at>
parents: 21246
diff changeset
1266 protected <B extends AbstractBlockBase<B>> void run(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder,
8ecb442fc864 LinearScan: split into sub-phases.
Josef Eisl <josef.eisl@jku.at>
parents: 21246
diff changeset
1267 SpillMoveFactory spillMoveFactory) {
21314
8908ac7d2c86 LinearScan: move call to sortIntervalsBeforeAllocation to RegisterAllocation phase.
Josef Eisl <josef.eisl@jku.at>
parents: 21313
diff changeset
1268 sortIntervalsBeforeAllocation();
21312
8ecb442fc864 LinearScan: split into sub-phases.
Josef Eisl <josef.eisl@jku.at>
parents: 21246
diff changeset
1269 printIntervals("Before register allocation");
8ecb442fc864 LinearScan: split into sub-phases.
Josef Eisl <josef.eisl@jku.at>
parents: 21246
diff changeset
1270 allocateRegisters();
21313
bb9d3f0616a3 LinearScan: reorganize LIR and Interval dumping.
Josef Eisl <josef.eisl@jku.at>
parents: 21312
diff changeset
1271 printIntervals("After register allocation");
21312
8ecb442fc864 LinearScan: split into sub-phases.
Josef Eisl <josef.eisl@jku.at>
parents: 21246
diff changeset
1272 }
8ecb442fc864 LinearScan: split into sub-phases.
Josef Eisl <josef.eisl@jku.at>
parents: 21246
diff changeset
1273
8ecb442fc864 LinearScan: split into sub-phases.
Josef Eisl <josef.eisl@jku.at>
parents: 21246
diff changeset
1274 }
8ecb442fc864 LinearScan: split into sub-phases.
Josef Eisl <josef.eisl@jku.at>
parents: 21246
diff changeset
1275
8ecb442fc864 LinearScan: split into sub-phases.
Josef Eisl <josef.eisl@jku.at>
parents: 21246
diff changeset
1276 private final class ResolveDataFlow extends AllocationPhase {
8ecb442fc864 LinearScan: split into sub-phases.
Josef Eisl <josef.eisl@jku.at>
parents: 21246
diff changeset
1277
8ecb442fc864 LinearScan: split into sub-phases.
Josef Eisl <josef.eisl@jku.at>
parents: 21246
diff changeset
1278 @Override
8ecb442fc864 LinearScan: split into sub-phases.
Josef Eisl <josef.eisl@jku.at>
parents: 21246
diff changeset
1279 protected <B extends AbstractBlockBase<B>> void run(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder,
8ecb442fc864 LinearScan: split into sub-phases.
Josef Eisl <josef.eisl@jku.at>
parents: 21246
diff changeset
1280 SpillMoveFactory spillMoveFactory) {
8ecb442fc864 LinearScan: split into sub-phases.
Josef Eisl <josef.eisl@jku.at>
parents: 21246
diff changeset
1281 resolveDataFlow();
8ecb442fc864 LinearScan: split into sub-phases.
Josef Eisl <josef.eisl@jku.at>
parents: 21246
diff changeset
1282 }
8ecb442fc864 LinearScan: split into sub-phases.
Josef Eisl <josef.eisl@jku.at>
parents: 21246
diff changeset
1283
8ecb442fc864 LinearScan: split into sub-phases.
Josef Eisl <josef.eisl@jku.at>
parents: 21246
diff changeset
1284 }
8ecb442fc864 LinearScan: split into sub-phases.
Josef Eisl <josef.eisl@jku.at>
parents: 21246
diff changeset
1285
8ecb442fc864 LinearScan: split into sub-phases.
Josef Eisl <josef.eisl@jku.at>
parents: 21246
diff changeset
1286 private final class EliminateSpillMove extends AllocationPhase {
8ecb442fc864 LinearScan: split into sub-phases.
Josef Eisl <josef.eisl@jku.at>
parents: 21246
diff changeset
1287
8ecb442fc864 LinearScan: split into sub-phases.
Josef Eisl <josef.eisl@jku.at>
parents: 21246
diff changeset
1288 @Override
8ecb442fc864 LinearScan: split into sub-phases.
Josef Eisl <josef.eisl@jku.at>
parents: 21246
diff changeset
1289 protected <B extends AbstractBlockBase<B>> void run(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder,
8ecb442fc864 LinearScan: split into sub-phases.
Josef Eisl <josef.eisl@jku.at>
parents: 21246
diff changeset
1290 SpillMoveFactory spillMoveFactory) {
8ecb442fc864 LinearScan: split into sub-phases.
Josef Eisl <josef.eisl@jku.at>
parents: 21246
diff changeset
1291 beforeSpillMoveElimination();
8ecb442fc864 LinearScan: split into sub-phases.
Josef Eisl <josef.eisl@jku.at>
parents: 21246
diff changeset
1292 eliminateSpillMoves();
8ecb442fc864 LinearScan: split into sub-phases.
Josef Eisl <josef.eisl@jku.at>
parents: 21246
diff changeset
1293 }
8ecb442fc864 LinearScan: split into sub-phases.
Josef Eisl <josef.eisl@jku.at>
parents: 21246
diff changeset
1294
8ecb442fc864 LinearScan: split into sub-phases.
Josef Eisl <josef.eisl@jku.at>
parents: 21246
diff changeset
1295 }
8ecb442fc864 LinearScan: split into sub-phases.
Josef Eisl <josef.eisl@jku.at>
parents: 21246
diff changeset
1296
21236
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
1297 protected void beforeSpillMoveElimination() {
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
1298 }
8d21d631a82d LinearScan: minor refactoring and comment cleanup.
Josef Eisl <josef.eisl@jku.at>
parents: 21203
diff changeset
1299
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1300 void printIntervals(String label) {
13467
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1301 if (Debug.isLogEnabled()) {
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1302 try (Indent indent = Debug.logAndIndent("intervals %s", label)) {
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1303 for (Interval interval : intervals) {
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1304 if (interval != null) {
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1305 Debug.log("%s", interval.logString(this));
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1306 }
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1307 }
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1308
13467
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1309 try (Indent indent2 = Debug.logAndIndent("Basic Blocks")) {
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1310 for (int i = 0; i < blockCount(); i++) {
19560
4d70d150944f Remove AbstractBlock interface.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 19212
diff changeset
1311 AbstractBlockBase<?> block = blockAt(i);
13467
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1312 Debug.log("B%d [%d, %d, %s] ", block.getId(), getFirstLirInstructionId(block), getLastLirInstructionId(block), block.getLoop());
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1313 }
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1314 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1315 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1316 }
4353
043bec543161 More work on debug framework. Removed concept of GraalContext.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 4352
diff changeset
1317 Debug.dump(Arrays.copyOf(intervals, intervalsSize), label);
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1318 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1319
7556
630ea5001e33 Modified formatter settings to not insert line break after annotation on parameters.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7530
diff changeset
1320 void printLir(String label, @SuppressWarnings("unused") boolean hirValid) {
4353
043bec543161 More work on debug framework. Removed concept of GraalContext.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 4352
diff changeset
1321 Debug.dump(ir, label);
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1322 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1323
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1324 boolean verify() {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1325 // (check that all intervals have a correct register and that no registers are overwritten)
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1326 verifyIntervals();
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1327
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1328 verifyRegisters();
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1329
13467
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1330 Debug.log("no errors found");
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1331
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1332 return true;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1333 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1334
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1335 private void verifyRegisters() {
13467
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1336 // Enable this logging to get output for the verification process.
13546
43bd3d7254d1 don?t explicitly disable debug log output in linear scan and graphbuilder
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13467
diff changeset
1337 try (Indent indent = Debug.logAndIndent("verifying register allocation")) {
13467
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1338 RegisterVerifier verifier = new RegisterVerifier(this);
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1339 verifier.verify(blockAt(0));
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1340 }
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1341 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1342
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1343 void verifyIntervals() {
13467
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1344 try (Indent indent = Debug.logAndIndent("verifying intervals")) {
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1345 int len = intervalsSize;
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1346
13467
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1347 for (int i = 0; i < len; i++) {
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1348 Interval i1 = intervals[i];
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1349 if (i1 == null) {
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1350 continue;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1351 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1352
13467
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1353 i1.checkSplitChildren();
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1354
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1355 if (i1.operandNumber != i) {
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1356 Debug.log("Interval %d is on position %d in list", i1.operandNumber, i);
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1357 Debug.log(i1.logString(this));
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1358 throw new GraalInternalError("");
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1359 }
13467
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1360
16118
5cbaad0b7387 Verify usage of equals method in LIRKind.
Roland Schatz <roland.schatz@oracle.com>
parents: 16094
diff changeset
1361 if (isVariable(i1.operand) && i1.kind().equals(LIRKind.Illegal)) {
13467
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1362 Debug.log("Interval %d has no type assigned", i1.operandNumber);
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1363 Debug.log(i1.logString(this));
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1364 throw new GraalInternalError("");
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1365 }
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1366
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1367 if (i1.location() == null) {
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1368 Debug.log("Interval %d has no register assigned", i1.operandNumber);
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1369 Debug.log(i1.logString(this));
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1370 throw new GraalInternalError("");
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1371 }
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1372
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1373 if (i1.first() == Range.EndMarker) {
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1374 Debug.log("Interval %d has no Range", i1.operandNumber);
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1375 Debug.log(i1.logString(this));
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1376 throw new GraalInternalError("");
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1377 }
13467
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1378
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1379 for (Range r = i1.first(); r != Range.EndMarker; r = r.next) {
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1380 if (r.from >= r.to) {
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1381 Debug.log("Interval %d has zero length range", i1.operandNumber);
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1382 Debug.log(i1.logString(this));
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1383 throw new GraalInternalError("");
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1384 }
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1385 }
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1386
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1387 for (int j = i + 1; j < len; j++) {
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1388 Interval i2 = intervals[j];
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1389 if (i2 == null) {
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1390 continue;
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1391 }
13467
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1392
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1393 // special intervals that are created in MoveResolver
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1394 // . ignore them because the range information has no meaning there
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1395 if (i1.from() == 1 && i1.to() == 2) {
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1396 continue;
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1397 }
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1398 if (i2.from() == 1 && i2.to() == 2) {
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1399 continue;
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1400 }
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1401 Value l1 = i1.location();
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1402 Value l2 = i2.location();
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1403 if (i1.intersects(i2) && !isIllegal(l1) && (l1.equals(l2))) {
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1404 if (DetailedAsserts.getValue()) {
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1405 Debug.log("Intervals %d and %d overlap and have the same register assigned", i1.operandNumber, i2.operandNumber);
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1406 Debug.log(i1.logString(this));
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1407 Debug.log(i2.logString(this));
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1408 }
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1409 throw new BailoutException("");
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1410 }
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1411 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1412 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1413 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1414 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1415
17285
3a834111a632 Make [Instruction]ValueProcedure and [Instruction]ValueConsumer a FunctionalInterface.
Josef Eisl <josef.eisl@jku.at>
parents: 17284
diff changeset
1416 class CheckConsumer implements ValueConsumer {
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7512
diff changeset
1417
4245
75c620f90ab9 Support stack-operands and register hints in new register allocator API
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4214
diff changeset
1418 boolean ok;
75c620f90ab9 Support stack-operands and register hints in new register allocator API
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4214
diff changeset
1419 Interval curInterval;
75c620f90ab9 Support stack-operands and register hints in new register allocator API
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4214
diff changeset
1420
75c620f90ab9 Support stack-operands and register hints in new register allocator API
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4214
diff changeset
1421 @Override
17284
d21962ea9617 Remove ValueConsumer.visitValue(Value).
Josef Eisl <josef.eisl@jku.at>
parents: 17283
diff changeset
1422 public void visitValue(Value operand, OperandMode mode, EnumSet<OperandFlag> flags) {
4245
75c620f90ab9 Support stack-operands and register hints in new register allocator API
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4214
diff changeset
1423 if (isRegister(operand)) {
75c620f90ab9 Support stack-operands and register hints in new register allocator API
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4214
diff changeset
1424 if (intervalFor(operand) == curInterval) {
75c620f90ab9 Support stack-operands and register hints in new register allocator API
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4214
diff changeset
1425 ok = true;
75c620f90ab9 Support stack-operands and register hints in new register allocator API
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4214
diff changeset
1426 }
75c620f90ab9 Support stack-operands and register hints in new register allocator API
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4214
diff changeset
1427 }
75c620f90ab9 Support stack-operands and register hints in new register allocator API
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4214
diff changeset
1428 }
75c620f90ab9 Support stack-operands and register hints in new register allocator API
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4214
diff changeset
1429 }
75c620f90ab9 Support stack-operands and register hints in new register allocator API
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4214
diff changeset
1430
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1431 void verifyNoOopsInFixedIntervals() {
13467
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1432 try (Indent indent = Debug.logAndIndent("verifying that no oops are in fixed intervals *")) {
16801
067dbd8e7114 Use ValueConsumer in LinearScan where possible.
Josef Eisl <josef.eisl@jku.at>
parents: 16796
diff changeset
1433 CheckConsumer checkConsumer = new CheckConsumer();
4245
75c620f90ab9 Support stack-operands and register hints in new register allocator API
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4214
diff changeset
1434
13467
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1435 Interval fixedIntervals;
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1436 Interval otherIntervals;
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1437 fixedIntervals = createUnhandledLists(IS_PRECOLORED_INTERVAL, null).first;
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1438 // to ensure a walking until the last instruction id, add a dummy interval
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1439 // with a high operation id
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1440 otherIntervals = new Interval(Value.ILLEGAL, -1);
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1441 otherIntervals.addRange(Integer.MAX_VALUE - 2, Integer.MAX_VALUE - 1);
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1442 IntervalWalker iw = new IntervalWalker(this, fixedIntervals, otherIntervals);
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1443
19560
4d70d150944f Remove AbstractBlock interface.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 19212
diff changeset
1444 for (AbstractBlockBase<?> block : sortedBlocks) {
14806
a8723f1ff542 LIR renamed setter and getter functions.
Josef Eisl <josef.eisl@jku.at>
parents: 14789
diff changeset
1445 List<LIRInstruction> instructions = ir.getLIRforBlock(block);
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1446
13467
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1447 for (int j = 0; j < instructions.size(); j++) {
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1448 LIRInstruction op = instructions.get(j);
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1449
13467
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1450 if (op.hasState()) {
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1451 iw.walkBefore(op.id());
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1452 boolean checkLive = true;
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1453
21319
9ddb5a749eab LinearScan: use multiline comments.
Josef Eisl <josef.eisl@jku.at>
parents: 21318
diff changeset
1454 /*
9ddb5a749eab LinearScan: use multiline comments.
Josef Eisl <josef.eisl@jku.at>
parents: 21318
diff changeset
1455 * Make sure none of the fixed registers is live across an oopmap since we
9ddb5a749eab LinearScan: use multiline comments.
Josef Eisl <josef.eisl@jku.at>
parents: 21318
diff changeset
1456 * can't handle that correctly.
9ddb5a749eab LinearScan: use multiline comments.
Josef Eisl <josef.eisl@jku.at>
parents: 21318
diff changeset
1457 */
13467
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1458 if (checkLive) {
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1459 for (Interval interval = iw.activeLists.get(RegisterBinding.Fixed); interval != Interval.EndMarker; interval = interval.next) {
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1460 if (interval.currentTo() > op.id() + 1) {
21319
9ddb5a749eab LinearScan: use multiline comments.
Josef Eisl <josef.eisl@jku.at>
parents: 21318
diff changeset
1461 /*
9ddb5a749eab LinearScan: use multiline comments.
Josef Eisl <josef.eisl@jku.at>
parents: 21318
diff changeset
1462 * This interval is live out of this op so make sure that this
9ddb5a749eab LinearScan: use multiline comments.
Josef Eisl <josef.eisl@jku.at>
parents: 21318
diff changeset
1463 * interval represents some value that's referenced by this op
9ddb5a749eab LinearScan: use multiline comments.
Josef Eisl <josef.eisl@jku.at>
parents: 21318
diff changeset
1464 * either as an input or output.
9ddb5a749eab LinearScan: use multiline comments.
Josef Eisl <josef.eisl@jku.at>
parents: 21318
diff changeset
1465 */
16801
067dbd8e7114 Use ValueConsumer in LinearScan where possible.
Josef Eisl <josef.eisl@jku.at>
parents: 16796
diff changeset
1466 checkConsumer.curInterval = interval;
067dbd8e7114 Use ValueConsumer in LinearScan where possible.
Josef Eisl <josef.eisl@jku.at>
parents: 16796
diff changeset
1467 checkConsumer.ok = false;
4245
75c620f90ab9 Support stack-operands and register hints in new register allocator API
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4214
diff changeset
1468
16801
067dbd8e7114 Use ValueConsumer in LinearScan where possible.
Josef Eisl <josef.eisl@jku.at>
parents: 16796
diff changeset
1469 op.visitEachInput(checkConsumer);
067dbd8e7114 Use ValueConsumer in LinearScan where possible.
Josef Eisl <josef.eisl@jku.at>
parents: 16796
diff changeset
1470 op.visitEachAlive(checkConsumer);
067dbd8e7114 Use ValueConsumer in LinearScan where possible.
Josef Eisl <josef.eisl@jku.at>
parents: 16796
diff changeset
1471 op.visitEachTemp(checkConsumer);
067dbd8e7114 Use ValueConsumer in LinearScan where possible.
Josef Eisl <josef.eisl@jku.at>
parents: 16796
diff changeset
1472 op.visitEachOutput(checkConsumer);
4245
75c620f90ab9 Support stack-operands and register hints in new register allocator API
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4214
diff changeset
1473
16801
067dbd8e7114 Use ValueConsumer in LinearScan where possible.
Josef Eisl <josef.eisl@jku.at>
parents: 16796
diff changeset
1474 assert checkConsumer.ok : "fixed intervals should never be live across an oopmap point";
13467
7c694e3e97e5 remove remaining old style TTY debug logging in LinearScan and remove TraceLinearScan option
Erik Eckstein <erik.eckstein@oracle.com>
parents: 13377
diff changeset
1475 }
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1476 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1477 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1478 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1479 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1480 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1481 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1482 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1483
14070
a8a82c6e2981 Remove LIRGenerator from LinearScan.
Josef Eisl <josef.eisl@jku.at>
parents: 14057
diff changeset
1484 /**
a8a82c6e2981 Remove LIRGenerator from LinearScan.
Josef Eisl <josef.eisl@jku.at>
parents: 14057
diff changeset
1485 * Returns a value for a interval definition, which can be used for re-materialization.
14871
667710021ea1 removed methods in Indent that are redundant with those in Debug
Doug Simon <doug.simon@oracle.com>
parents: 14841
diff changeset
1486 *
14070
a8a82c6e2981 Remove LIRGenerator from LinearScan.
Josef Eisl <josef.eisl@jku.at>
parents: 14057
diff changeset
1487 * @param op An instruction which defines a value
a8a82c6e2981 Remove LIRGenerator from LinearScan.
Josef Eisl <josef.eisl@jku.at>
parents: 14057
diff changeset
1488 * @param operand The destination operand of the instruction
a8a82c6e2981 Remove LIRGenerator from LinearScan.
Josef Eisl <josef.eisl@jku.at>
parents: 14057
diff changeset
1489 * @param interval The interval for this defined value.
a8a82c6e2981 Remove LIRGenerator from LinearScan.
Josef Eisl <josef.eisl@jku.at>
parents: 14057
diff changeset
1490 * @return Returns the value which is moved to the instruction and which can be reused at all
a8a82c6e2981 Remove LIRGenerator from LinearScan.
Josef Eisl <josef.eisl@jku.at>
parents: 14057
diff changeset
1491 * reload-locations in case the interval of this instruction is spilled. Currently this
18187
9619ba4daf4c Rename Constant to JavaConstant.
Roland Schatz <roland.schatz@oracle.com>
parents: 18152
diff changeset
1492 * can only be a {@link JavaConstant}.
14070
a8a82c6e2981 Remove LIRGenerator from LinearScan.
Josef Eisl <josef.eisl@jku.at>
parents: 14057
diff changeset
1493 */
18187
9619ba4daf4c Rename Constant to JavaConstant.
Roland Schatz <roland.schatz@oracle.com>
parents: 18152
diff changeset
1494 public static JavaConstant getMaterializedValue(LIRInstruction op, Value operand, Interval interval) {
14070
a8a82c6e2981 Remove LIRGenerator from LinearScan.
Josef Eisl <josef.eisl@jku.at>
parents: 14057
diff changeset
1495 if (op instanceof MoveOp) {
a8a82c6e2981 Remove LIRGenerator from LinearScan.
Josef Eisl <josef.eisl@jku.at>
parents: 14057
diff changeset
1496 MoveOp move = (MoveOp) op;
18187
9619ba4daf4c Rename Constant to JavaConstant.
Roland Schatz <roland.schatz@oracle.com>
parents: 18152
diff changeset
1497 if (move.getInput() instanceof JavaConstant) {
14070
a8a82c6e2981 Remove LIRGenerator from LinearScan.
Josef Eisl <josef.eisl@jku.at>
parents: 14057
diff changeset
1498 /*
a8a82c6e2981 Remove LIRGenerator from LinearScan.
Josef Eisl <josef.eisl@jku.at>
parents: 14057
diff changeset
1499 * Check if the interval has any uses which would accept an stack location (priority
a8a82c6e2981 Remove LIRGenerator from LinearScan.
Josef Eisl <josef.eisl@jku.at>
parents: 14057
diff changeset
1500 * == ShouldHaveRegister). Rematerialization of such intervals can result in a
a8a82c6e2981 Remove LIRGenerator from LinearScan.
Josef Eisl <josef.eisl@jku.at>
parents: 14057
diff changeset
1501 * degradation, because rematerialization always inserts a constant load, even if
a8a82c6e2981 Remove LIRGenerator from LinearScan.
Josef Eisl <josef.eisl@jku.at>
parents: 14057
diff changeset
1502 * the value is not needed in a register.
a8a82c6e2981 Remove LIRGenerator from LinearScan.
Josef Eisl <josef.eisl@jku.at>
parents: 14057
diff changeset
1503 */
a8a82c6e2981 Remove LIRGenerator from LinearScan.
Josef Eisl <josef.eisl@jku.at>
parents: 14057
diff changeset
1504 Interval.UsePosList usePosList = interval.usePosList();
a8a82c6e2981 Remove LIRGenerator from LinearScan.
Josef Eisl <josef.eisl@jku.at>
parents: 14057
diff changeset
1505 int numUsePos = usePosList.size();
a8a82c6e2981 Remove LIRGenerator from LinearScan.
Josef Eisl <josef.eisl@jku.at>
parents: 14057
diff changeset
1506 for (int useIdx = 0; useIdx < numUsePos; useIdx++) {
a8a82c6e2981 Remove LIRGenerator from LinearScan.
Josef Eisl <josef.eisl@jku.at>
parents: 14057
diff changeset
1507 Interval.RegisterPriority priority = usePosList.registerPriority(useIdx);
15920
4b835260c746 backout 88a6017687c9
Josef Eisl <josef.eisl@jku.at>
parents: 15914
diff changeset
1508 if (priority == Interval.RegisterPriority.ShouldHaveRegister) {
14070
a8a82c6e2981 Remove LIRGenerator from LinearScan.
Josef Eisl <josef.eisl@jku.at>
parents: 14057
diff changeset
1509 return null;
a8a82c6e2981 Remove LIRGenerator from LinearScan.
Josef Eisl <josef.eisl@jku.at>
parents: 14057
diff changeset
1510 }
a8a82c6e2981 Remove LIRGenerator from LinearScan.
Josef Eisl <josef.eisl@jku.at>
parents: 14057
diff changeset
1511 }
18187
9619ba4daf4c Rename Constant to JavaConstant.
Roland Schatz <roland.schatz@oracle.com>
parents: 18152
diff changeset
1512 return (JavaConstant) move.getInput();
14070
a8a82c6e2981 Remove LIRGenerator from LinearScan.
Josef Eisl <josef.eisl@jku.at>
parents: 14057
diff changeset
1513 }
a8a82c6e2981 Remove LIRGenerator from LinearScan.
Josef Eisl <josef.eisl@jku.at>
parents: 14057
diff changeset
1514 }
a8a82c6e2981 Remove LIRGenerator from LinearScan.
Josef Eisl <josef.eisl@jku.at>
parents: 14057
diff changeset
1515 return null;
a8a82c6e2981 Remove LIRGenerator from LinearScan.
Josef Eisl <josef.eisl@jku.at>
parents: 14057
diff changeset
1516 }
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1517 }