Mercurial > hg > truffle

annotate graal/com.oracle.max.graal.alloc/src/com/oracle/graal/alloc/simple/LinearScanAllocator.java @ 5060:4ed4295ce15f

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Update import statements.
author Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
date Thu, 08 Mar 2012 19:11:12 +0100
parents ed559a528128
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
4292
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
1 /*
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
2 * Copyright (c) 2011, 2012, Oracle and/or its affiliates. All rights reserved.
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
4 *
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
5 * This code is free software; you can redistribute it and/or modify it
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
6 * under the terms of the GNU General Public License version 2 only, as
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
7 * published by the Free Software Foundation.
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
8 *
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
9 * This code is distributed in the hope that it will be useful, but WITHOUT
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
12 * version 2 for more details (a copy is included in the LICENSE file that
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
13 * accompanied this code).
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
14 *
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
15 * You should have received a copy of the GNU General Public License version
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
16 * 2 along with this work; if not, write to the Free Software Foundation,
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
18 *
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
20 * or visit www.oracle.com if you need additional information or have any
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
21 * questions.
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
22 */
5060
4ed4295ce15f Update import statements.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 5059
diff changeset
23 package com.oracle.graal.alloc.simple;
4292
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
24
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
25 import static com.oracle.max.cri.ci.CiValueUtil.*;
5060
4ed4295ce15f Update import statements.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 5059
diff changeset
26 import static com.oracle.graal.alloc.util.LocationUtil.*;
4292
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
27
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
28 import java.util.*;
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
29
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
30 import com.oracle.max.cri.ci.*;
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
31 import com.oracle.max.cri.ci.CiRegister.RegisterFlag;
5060
4ed4295ce15f Update import statements.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 5059
diff changeset
32 import com.oracle.graal.alloc.util.*;
4ed4295ce15f Update import statements.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 5059
diff changeset
33 import com.oracle.graal.debug.*;
4ed4295ce15f Update import statements.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 5059
diff changeset
34 import com.oracle.graal.graph.*;
4ed4295ce15f Update import statements.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 5059
diff changeset
35 import com.oracle.graal.lir.*;
4ed4295ce15f Update import statements.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 5059
diff changeset
36 import com.oracle.graal.lir.LIRInstruction.*;
4ed4295ce15f Update import statements.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 5059
diff changeset
37 import com.oracle.graal.lir.cfg.*;
4292
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
38
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
39 public class LinearScanAllocator {
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
40 private final LIR lir;
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
41 private final FrameMap frameMap;
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
42
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
43 private final DataFlowAnalysis dataFlow;
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
44
4359
c66ddad845a4 Merge fixes.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 4295
diff changeset
45 public LinearScanAllocator(LIR lir, FrameMap frameMap) {
4292
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
46 this.lir = lir;
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
47 this.frameMap = frameMap;
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
48
4295
1e3ecb08767d Output of lifetime intervals for new register allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4292
diff changeset
49 this.dataFlow = new DataFlowAnalysis(lir, frameMap.registerConfig);
4292
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
50 this.blockBeginLocations = new LocationMap[lir.linearScanOrder().size()];
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
51 this.blockEndLocations = new LocationMap[lir.linearScanOrder().size()];
4323
df5547057954 Remove LIROpcode and use non-anonymous subclasses of LIRInstruction
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4295
diff changeset
52 this.moveResolver = new MoveResolverImpl(lir, frameMap);
4292
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
53
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
54 this.variableLastUse = new int[lir.numVariables()];
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
55 }
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
56
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
57 private class MoveResolverImpl extends MoveResolver {
4323
df5547057954 Remove LIROpcode and use non-anonymous subclasses of LIRInstruction
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4295
diff changeset
58 public MoveResolverImpl(LIR lir, FrameMap frameMap) {
df5547057954 Remove LIROpcode and use non-anonymous subclasses of LIRInstruction
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4295
diff changeset
59 super(lir, frameMap);
4292
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
60 }
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
61
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
62 @Override
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
63 protected CiValue scratchRegister(Variable spilled) {
4524
dcc8f5c6f394 Refactorings to prepare for LIR project splitting
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4522
diff changeset
64 GraalInternalError.shouldNotReachHere("needs working implementation");
4292
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
65
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
66 EnumMap<RegisterFlag, CiRegister[]> categorizedRegs = frameMap.registerConfig.getCategorizedAllocatableRegisters();
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
67 CiRegister[] availableRegs = categorizedRegs.get(spilled.flag);
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
68 for (CiRegister reg : availableRegs) {
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
69 if (curInRegisterState[reg.number] == null && curOutRegisterState[reg.number] == null) {
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
70 return reg.asValue(spilled.kind);
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
71 }
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
72 }
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
73 throw new CiBailout("No register found");
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
74 }
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
75 }
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
76
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
77 private class ResolveDataFlowImpl extends ResolveDataFlow {
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
78 public ResolveDataFlowImpl(LIR lir, MoveResolver moveResolver, DataFlowAnalysis dataFlow) {
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
79 super(lir, moveResolver, dataFlow);
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
80 }
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
81
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
82 @Override
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4365
diff changeset
83 protected LocationMap locationsForBlockBegin(Block block) {
4292
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
84 return beginLocationsFor(block);
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
85 }
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
86
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
87 @Override
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4365
diff changeset
88 protected LocationMap locationsForBlockEnd(Block block) {
4292
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
89 return endLocationsFor(block);
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
90 }
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
91 }
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
92
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
93 private class AssignRegistersImpl extends AssignRegisters {
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
94 public AssignRegistersImpl(LIR lir, FrameMap frameMap) {
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
95 super(lir, frameMap);
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
96 }
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
97
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
98 @Override
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4365
diff changeset
99 protected LocationMap locationsForBlockEnd(Block block) {
4292
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
100 return endLocationsFor(block);
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
101 }
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
102 }
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
103
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
104
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
105 private int maxRegisterNum() {
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
106 return frameMap.target.arch.registers.length;
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
107 }
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
108
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
109 private boolean isAllocatableRegister(CiValue value) {
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
110 return isRegister(value) && frameMap.registerConfig.getAttributesMap()[asRegister(value).number].isAllocatable;
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
111 }
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
112
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
113
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
114 private final LocationMap[] blockBeginLocations;
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
115
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
116 private LocationMap beginLocationsFor(Block block) {
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4365
diff changeset
117 return blockBeginLocations[block.getId()];
4292
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
118 }
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
119 private void setBeginLocationsFor(Block block, LocationMap locations) {
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4365
diff changeset
120 blockBeginLocations[block.getId()] = locations;
4292
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
121 }
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
122
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
123 private final LocationMap[] blockEndLocations;
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
124
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
125 private LocationMap endLocationsFor(Block block) {
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4365
diff changeset
126 return blockEndLocations[block.getId()];
4292
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
127 }
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
128 private void setEndLocationsFor(Block block, LocationMap locations) {
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4365
diff changeset
129 blockEndLocations[block.getId()] = locations;
4292
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
130 }
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
131
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
132 private final int[] variableLastUse;
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
133
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
134 private int lastUseFor(Variable variable) {
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
135 return variableLastUse[variable.index];
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
136 }
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
137
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
138 private void setLastUseFor(Variable variable, int lastUse) {
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
139 variableLastUse[variable.index] = lastUse;
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
140 }
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
141
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
142 private MoveResolver moveResolver;
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
143 private LocationMap curLocations;
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
144 private CiValue[] curInRegisterState;
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
145 private CiValue[] curOutRegisterState;
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
146 private BitSet curLiveIn;
5007
f8e3ec43b514 Use register hints in new linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4616
diff changeset
147 private LIRInstruction curOp;
4292
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
148
5007
f8e3ec43b514 Use register hints in new linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4616
diff changeset
149 /**
f8e3ec43b514 Use register hints in new linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4616
diff changeset
150 * The spill slot for a variable, if the variable has ever been spilled.
f8e3ec43b514 Use register hints in new linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4616
diff changeset
151 */
4292
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
152 private LocationMap canonicalSpillLocations;
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
153
5007
f8e3ec43b514 Use register hints in new linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4616
diff changeset
154 /**
f8e3ec43b514 Use register hints in new linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4616
diff changeset
155 * The register that a variable got assigned at its definition, and so it should get that register when reloading after spilling.
f8e3ec43b514 Use register hints in new linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4616
diff changeset
156 */
f8e3ec43b514 Use register hints in new linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4616
diff changeset
157 private LocationMap hintRegisterLocations;
f8e3ec43b514 Use register hints in new linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4616
diff changeset
158
4292
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
159 public void execute() {
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
160 assert LIRVerifier.verify(true, lir, frameMap);
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
161
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
162 dataFlow.execute();
4359
c66ddad845a4 Merge fixes.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 4295
diff changeset
163 IntervalPrinter.printBeforeAllocation("Before register allocation", lir, frameMap.registerConfig, dataFlow);
4295
1e3ecb08767d Output of lifetime intervals for new register allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4292
diff changeset
164
4292
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
165 allocate();
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
166
4359
c66ddad845a4 Merge fixes.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 4295
diff changeset
167 IntervalPrinter.printAfterAllocation("After linear scan allocation", lir, frameMap.registerConfig, dataFlow, blockEndLocations);
4292
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
168
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
169 ResolveDataFlow resolveDataFlow = new ResolveDataFlowImpl(lir, moveResolver, dataFlow);
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
170 resolveDataFlow.execute();
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
171 frameMap.finish();
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
172
4359
c66ddad845a4 Merge fixes.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 4295
diff changeset
173 IntervalPrinter.printAfterAllocation("After resolve data flow", lir, frameMap.registerConfig, dataFlow, blockEndLocations);
4292
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
174 assert RegisterVerifier.verify(lir, frameMap);
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
175
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
176 AssignRegisters assignRegisters = new AssignRegistersImpl(lir, frameMap);
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
177 assignRegisters.execute();
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
178
4359
c66ddad845a4 Merge fixes.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 4295
diff changeset
179 Debug.dump(lir, "After register asignment");
4292
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
180 assert LIRVerifier.verify(false, lir, frameMap);
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
181 }
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
182
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
183 private void allocate() {
4522
cf13124efdd9 Restructure phi functions in LIR; Re-enabled C1Visualizer output
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4435
diff changeset
184 ValueProcedure recordUseProc = new ValueProcedure() { @Override public CiValue doValue(CiValue value, OperandMode mode, EnumSet<OperandFlag> flags) { return recordUse(value); } };
cf13124efdd9 Restructure phi functions in LIR; Re-enabled C1Visualizer output
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4435
diff changeset
185 ValueProcedure killNonLiveProc = new ValueProcedure() { @Override public CiValue doValue(CiValue value) { return killNonLive(value); } };
cf13124efdd9 Restructure phi functions in LIR; Re-enabled C1Visualizer output
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4435
diff changeset
186 ValueProcedure unblockProc = new ValueProcedure() { @Override public CiValue doValue(CiValue value) { return unblock(value); } };
cf13124efdd9 Restructure phi functions in LIR; Re-enabled C1Visualizer output
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4435
diff changeset
187 ValueProcedure killProc = new ValueProcedure() { @Override public CiValue doValue(CiValue value) { return kill(value); } };
cf13124efdd9 Restructure phi functions in LIR; Re-enabled C1Visualizer output
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4435
diff changeset
188 ValueProcedure blockProc = new ValueProcedure() { @Override public CiValue doValue(CiValue value) { return block(value); } };
cf13124efdd9 Restructure phi functions in LIR; Re-enabled C1Visualizer output
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4435
diff changeset
189 ValueProcedure useProc = new ValueProcedure() { @Override public CiValue doValue(CiValue value, OperandMode mode, EnumSet<OperandFlag> flags) { return use(value, mode, flags); } };
cf13124efdd9 Restructure phi functions in LIR; Re-enabled C1Visualizer output
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4435
diff changeset
190 ValueProcedure defProc = new ValueProcedure() { @Override public CiValue doValue(CiValue value, OperandMode mode, EnumSet<OperandFlag> flags) { return def(value, mode, flags); } };
4292
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
191
4524
dcc8f5c6f394 Refactorings to prepare for LIR project splitting
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4522
diff changeset
192 Debug.log("==== start linear scan allocation ====");
4292
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
193 canonicalSpillLocations = new LocationMap(lir.numVariables());
5007
f8e3ec43b514 Use register hints in new linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4616
diff changeset
194 hintRegisterLocations = new LocationMap(lir.numVariables());
4292
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
195 curInRegisterState = new CiValue[maxRegisterNum()];
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
196 curOutRegisterState = new CiValue[maxRegisterNum()];
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4365
diff changeset
197 for (Block block : lir.linearScanOrder()) {
4524
dcc8f5c6f394 Refactorings to prepare for LIR project splitting
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4522
diff changeset
198 Debug.log("start block %s %s", block, block.getLoop());
4292
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
199
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
200 Arrays.fill(curOutRegisterState, null);
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4365
diff changeset
201 if (block.getDominator() != null) {
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4365
diff changeset
202 LocationMap dominatorState = endLocationsFor(block.getDominator());
4292
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
203 curLocations = new LocationMap(dominatorState);
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
204 // Clear out all variables that are not live at the begin of this block
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
205 curLiveIn = dataFlow.liveIn(block);
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
206 curLocations.forEachLocation(killNonLiveProc);
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
207 assert checkInputState(block);
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
208 } else {
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
209 curLocations = new LocationMap(lir.numVariables());
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
210 }
4524
dcc8f5c6f394 Refactorings to prepare for LIR project splitting
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4522
diff changeset
211 Debug.log(logCurrentState());
4292
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
212
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4365
diff changeset
213 for (int opIdx = 0; opIdx < block.lir.size(); opIdx++) {
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4365
diff changeset
214 LIRInstruction op = block.lir.get(opIdx);
5007
f8e3ec43b514 Use register hints in new linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4616
diff changeset
215 curOp = op;
4522
cf13124efdd9 Restructure phi functions in LIR; Re-enabled C1Visualizer output
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4435
diff changeset
216
4524
dcc8f5c6f394 Refactorings to prepare for LIR project splitting
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4522
diff changeset
217 Debug.log(" op %d %s", op.id(), op);
4292
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
218
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
219 System.arraycopy(curOutRegisterState, 0, curInRegisterState, 0, curOutRegisterState.length);
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
220
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
221 // Unblock fixed registers that are only used for inputs in curOutRegisterState.
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
222 dataFlow.forEachKilled(op, false, unblockProc);
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
223 // Block fixed registers defined by this instruction in curOutRegisterState.
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
224 op.forEachTemp(blockProc);
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
225 op.forEachOutput(blockProc);
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
226
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
227 op.forEachInput(recordUseProc);
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
228 op.forEachAlive(recordUseProc);
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
229
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4365
diff changeset
230 moveResolver.init(block.lir, opIdx);
4292
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
231 // Process Alive before Input because they are more restricted and the same variable can be Alive and Input.
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
232 op.forEachAlive(useProc);
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
233 op.forEachInput(useProc);
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
234
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
235 dataFlow.forEachKilled(op, false, killProc);
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
236
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
237 if (op.hasCall()) {
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
238 spillCallerSaveRegisters();
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
239 }
5007
f8e3ec43b514 Use register hints in new linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4616
diff changeset
240 if (op instanceof StandardOp.PhiLabelOp) {
f8e3ec43b514 Use register hints in new linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4616
diff changeset
241 assert opIdx == 0;
f8e3ec43b514 Use register hints in new linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4616
diff changeset
242 phiRegisterHints(block);
f8e3ec43b514 Use register hints in new linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4616
diff changeset
243 }
4292
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
244
5007
f8e3ec43b514 Use register hints in new linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4616
diff changeset
245 op.forEachOutput(defProc);
4292
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
246 op.forEachTemp(defProc);
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
247
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
248 // Fixed temp and output registers can evict variables from their assigned register, allocate new location for them.
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
249 fixupEvicted();
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
250 // State values are the least critical and can get the leftover registers (or stack slots if no more register available).
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
251 op.forEachState(useProc);
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
252
4522
cf13124efdd9 Restructure phi functions in LIR; Re-enabled C1Visualizer output
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4435
diff changeset
253 if (opIdx == 0) {
cf13124efdd9 Restructure phi functions in LIR; Re-enabled C1Visualizer output
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4435
diff changeset
254 assert !moveResolver.hasMappings() : "cannot insert spill moves before label";
cf13124efdd9 Restructure phi functions in LIR; Re-enabled C1Visualizer output
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4435
diff changeset
255 setBeginLocationsFor(block, new LocationMap(curLocations));
cf13124efdd9 Restructure phi functions in LIR; Re-enabled C1Visualizer output
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4435
diff changeset
256 }
4292
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
257 moveResolver.resolve();
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
258
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
259 dataFlow.forEachKilled(op, true, unblockProc);
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
260 dataFlow.forEachKilled(op, true, killProc);
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
261
5007
f8e3ec43b514 Use register hints in new linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4616
diff changeset
262 curOp = null;
4292
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
263 }
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
264
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
265 assert endLocationsFor(block) == null;
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
266 setEndLocationsFor(block, curLocations);
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
267
4524
dcc8f5c6f394 Refactorings to prepare for LIR project splitting
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4522
diff changeset
268 logCurrentState();
dcc8f5c6f394 Refactorings to prepare for LIR project splitting
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4522
diff changeset
269 Debug.log("end block %s", block);
4292
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
270 }
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
271
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
272 moveResolver.finish();
4524
dcc8f5c6f394 Refactorings to prepare for LIR project splitting
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4522
diff changeset
273 Debug.log("==== end linear scan allocation ====");
4292
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
274 }
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
275
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
276 private CiValue killNonLive(CiValue value) {
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
277 assert isLocation(value);
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
278 if (!curLiveIn.get(asLocation(value).variable.index)) {
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
279 return null;
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
280
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
281 } else if (isAllocatableRegister(asLocation(value).location)) {
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
282 int regNum = asRegister(asLocation(value).location).number;
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
283 assert curOutRegisterState[regNum] == null;
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
284 curOutRegisterState[regNum] = value;
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
285 }
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
286 return value;
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
287 }
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
288
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
289 private CiValue unblock(CiValue value) {
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
290 if (isAllocatableRegister(value)) {
4524
dcc8f5c6f394 Refactorings to prepare for LIR project splitting
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4522
diff changeset
291 Debug.log(" unblock register %s", value);
4292
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
292 int regNum = asRegister(value).number;
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
293 assert curOutRegisterState[regNum] == value;
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
294 curOutRegisterState[regNum] = null;
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
295 }
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
296 return value;
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
297 }
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
298
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
299 private CiValue kill(CiValue value) {
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
300 if (isVariable(value)) {
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
301 Location location = curLocations.get(asVariable(value));
4524
dcc8f5c6f394 Refactorings to prepare for LIR project splitting
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4522
diff changeset
302 Debug.log(" kill location %s", location);
4292
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
303 if (isRegister(location.location)) {
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
304 int regNum = asRegister(location.location).number;
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
305 if (curOutRegisterState[regNum] == location) {
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
306 curOutRegisterState[regNum] = null;
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
307 }
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
308 }
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
309 curLocations.clear(asVariable(value));
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
310 }
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
311 return value;
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
312 }
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
313
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
314
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
315 private CiValue block(CiValue value) {
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
316 if (isAllocatableRegister(value)) {
4524
dcc8f5c6f394 Refactorings to prepare for LIR project splitting
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4522
diff changeset
317 Debug.log(" block %s", value);
4292
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
318 int regNum = asRegister(value).number;
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
319 assert curOutRegisterState[regNum] == null || curOutRegisterState[regNum] instanceof Location;
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
320 curOutRegisterState[regNum] = value;
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
321 }
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
322 return value;
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
323 }
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
324
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
325 private void spillCallerSaveRegisters() {
4524
dcc8f5c6f394 Refactorings to prepare for LIR project splitting
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4522
diff changeset
326 Debug.log(" spill caller save registers in curInRegisterState %s", Arrays.toString(curInRegisterState));
4292
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
327 for (CiRegister reg : frameMap.registerConfig.getCallerSaveRegisters()) {
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
328 CiValue in = curInRegisterState[reg.number];
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
329 if (in != null && isLocation(in)) {
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
330 spill(asLocation(in));
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
331 }
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
332 }
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
333 }
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
334
4522
cf13124efdd9 Restructure phi functions in LIR; Re-enabled C1Visualizer output
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4435
diff changeset
335 private CiValue recordUse(CiValue value) {
4292
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
336 if (isVariable(value)) {
5007
f8e3ec43b514 Use register hints in new linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4616
diff changeset
337 assert lastUseFor(asVariable(value)) <= curOp.id();
f8e3ec43b514 Use register hints in new linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4616
diff changeset
338 setLastUseFor(asVariable(value), curOp.id());
4292
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
339
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
340 }
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
341 return value;
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
342 }
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
343
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
344 private CiValue use(CiValue value, OperandMode mode, EnumSet<OperandFlag> flags) {
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
345 assert mode == OperandMode.Input || mode == OperandMode.Alive;
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
346 if (isVariable(value)) {
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
347 // State values are not recorded beforehand because it does not matter if they are spilled. Still, it is necessary to record them as used now.
4522
cf13124efdd9 Restructure phi functions in LIR; Re-enabled C1Visualizer output
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4435
diff changeset
348 recordUse(value);
4292
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
349
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
350 Location curLoc = curLocations.get(asVariable(value));
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
351 if (isStackSlot(curLoc.location) && flags.contains(OperandFlag.Stack)) {
4524
dcc8f5c6f394 Refactorings to prepare for LIR project splitting
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4522
diff changeset
352 Debug.log(" use %s %s: use current stack slot %s", mode, value, curLoc.location);
4292
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
353 return curLoc;
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
354 }
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
355 if (isRegister(curLoc.location)) {
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
356 int regNum = asRegister(curLoc.location).number;
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
357 assert curInRegisterState[regNum] == curLoc;
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
358 if (mode == OperandMode.Input || curOutRegisterState[regNum] == curLoc) {
4524
dcc8f5c6f394 Refactorings to prepare for LIR project splitting
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4522
diff changeset
359 Debug.log(" use %s %s: use current register %s", mode, value, curLoc.location);
4292
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
360 return curLoc;
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
361 }
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
362 }
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
363
4524
dcc8f5c6f394 Refactorings to prepare for LIR project splitting
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4522
diff changeset
364 Debug.log(" use %s %s", mode, value);
4292
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
365
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
366 Location newLoc = allocateRegister(asVariable(value), mode, flags);
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
367 if (newLoc != curLoc) {
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
368 moveResolver.add(curLoc, newLoc);
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
369 }
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
370 return newLoc;
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
371 } else {
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
372 assert !isAllocatableRegister(value) || curInRegisterState[asRegister(value).number] == value;
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
373 }
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
374 return value;
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
375 }
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
376
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
377 private static final EnumSet<OperandFlag> SPILL_FLAGS = EnumSet.of(OperandFlag.Register, OperandFlag.Stack);
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
378
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
379 private CiValue def(CiValue value, OperandMode mode, EnumSet<OperandFlag> flags) {
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
380 assert mode == OperandMode.Temp || mode == OperandMode.Output;
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
381 if (isVariable(value)) {
4524
dcc8f5c6f394 Refactorings to prepare for LIR project splitting
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4522
diff changeset
382 Debug.log(" def %s %s", mode, value);
4292
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
383 assert curLocations.get(asVariable(value)) == null;
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
384
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
385 Location newLoc = allocateRegister(asVariable(value), mode, flags);
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
386 return newLoc;
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
387 }
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
388 return value;
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
389 }
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
390
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
391
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
392 private void fixupEvicted() {
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
393 for (int i = 0; i < curInRegisterState.length; i++) {
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
394 CiValue in = curInRegisterState[i];
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
395 CiValue out = curOutRegisterState[i];
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
396
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
397 if (in != null && in != out && isLocation(in) && curLocations.get(asLocation(in).variable) == in) {
4524
dcc8f5c6f394 Refactorings to prepare for LIR project splitting
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4522
diff changeset
398 Debug.log(" %s was evicted by %s, need to allocate new location", in, out);
4292
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
399 Location oldLoc = asLocation(in);
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
400 Location newLoc = allocateRegister(oldLoc.variable, OperandMode.Alive, SPILL_FLAGS);
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
401 assert oldLoc != newLoc;
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
402 moveResolver.add(oldLoc, newLoc);
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
403 }
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
404
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
405
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
406 }
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
407 }
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
408
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
409
5007
f8e3ec43b514 Use register hints in new linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4616
diff changeset
410 private void phiRegisterHints(Block block) {
f8e3ec43b514 Use register hints in new linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4616
diff changeset
411 Debug.log(" phi register hints for %s", block);
f8e3ec43b514 Use register hints in new linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4616
diff changeset
412 CiValue[] phiDefinitions = ((StandardOp.PhiLabelOp) block.lir.get(0)).getPhiDefinitions();
f8e3ec43b514 Use register hints in new linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4616
diff changeset
413 for (Block pred : block.getPredecessors()) {
f8e3ec43b514 Use register hints in new linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4616
diff changeset
414 CiValue[] phiInputs = ((StandardOp.PhiJumpOp) pred.lir.get(pred.lir.size() - 1)).getPhiInputs();
f8e3ec43b514 Use register hints in new linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4616
diff changeset
415
f8e3ec43b514 Use register hints in new linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4616
diff changeset
416 for (int i = 0; i < phiDefinitions.length; i++) {
f8e3ec43b514 Use register hints in new linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4616
diff changeset
417 CiValue phiDefinition = phiDefinitions[i];
f8e3ec43b514 Use register hints in new linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4616
diff changeset
418 CiValue phiInput = phiInputs[i];
f8e3ec43b514 Use register hints in new linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4616
diff changeset
419
f8e3ec43b514 Use register hints in new linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4616
diff changeset
420 if (isVariable(phiDefinition)) {
f8e3ec43b514 Use register hints in new linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4616
diff changeset
421 Location hintResult = processRegisterHint(asVariable(phiDefinition), OperandMode.Output, phiInput);
f8e3ec43b514 Use register hints in new linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4616
diff changeset
422 if (hintResult != null) {
f8e3ec43b514 Use register hints in new linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4616
diff changeset
423 phiDefinitions[i] = hintResult;
f8e3ec43b514 Use register hints in new linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4616
diff changeset
424 }
f8e3ec43b514 Use register hints in new linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4616
diff changeset
425 }
f8e3ec43b514 Use register hints in new linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4616
diff changeset
426 }
f8e3ec43b514 Use register hints in new linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4616
diff changeset
427 }
f8e3ec43b514 Use register hints in new linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4616
diff changeset
428 }
f8e3ec43b514 Use register hints in new linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4616
diff changeset
429
f8e3ec43b514 Use register hints in new linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4616
diff changeset
430 private Location processRegisterHint(Variable variable, OperandMode mode, CiValue registerHint) {
f8e3ec43b514 Use register hints in new linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4616
diff changeset
431 if (registerHint == null) {
f8e3ec43b514 Use register hints in new linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4616
diff changeset
432 return null;
f8e3ec43b514 Use register hints in new linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4616
diff changeset
433 }
f8e3ec43b514 Use register hints in new linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4616
diff changeset
434 Debug.log(" try registerHint for %s %s: %s", mode, variable, registerHint);
f8e3ec43b514 Use register hints in new linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4616
diff changeset
435 CiRegister hint = null;
f8e3ec43b514 Use register hints in new linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4616
diff changeset
436 if (isRegister(registerHint)) {
f8e3ec43b514 Use register hints in new linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4616
diff changeset
437 hint = asRegister(registerHint);
f8e3ec43b514 Use register hints in new linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4616
diff changeset
438 } else if (isLocation(registerHint) && isRegister(asLocation(registerHint).location)) {
f8e3ec43b514 Use register hints in new linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4616
diff changeset
439 hint = asRegister(asLocation(registerHint).location);
f8e3ec43b514 Use register hints in new linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4616
diff changeset
440 }
f8e3ec43b514 Use register hints in new linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4616
diff changeset
441 if (hint != null && hint.isSet(variable.flag) && isFree(hint, mode)) {
f8e3ec43b514 Use register hints in new linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4616
diff changeset
442 return selectRegister(hint, variable, mode);
f8e3ec43b514 Use register hints in new linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4616
diff changeset
443 }
f8e3ec43b514 Use register hints in new linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4616
diff changeset
444 return null;
f8e3ec43b514 Use register hints in new linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4616
diff changeset
445 }
f8e3ec43b514 Use register hints in new linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4616
diff changeset
446
f8e3ec43b514 Use register hints in new linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4616
diff changeset
447 private Location allocateRegister(final Variable variable, final OperandMode mode, EnumSet<OperandFlag> flags) {
f8e3ec43b514 Use register hints in new linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4616
diff changeset
448 if (flags.contains(OperandFlag.RegisterHint)) {
f8e3ec43b514 Use register hints in new linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4616
diff changeset
449 CiValue hintResult = curOp.forEachRegisterHint(variable, mode, new ValueProcedure() {
f8e3ec43b514 Use register hints in new linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4616
diff changeset
450 @Override
f8e3ec43b514 Use register hints in new linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4616
diff changeset
451 public CiValue doValue(CiValue registerHint) {
f8e3ec43b514 Use register hints in new linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4616
diff changeset
452 return processRegisterHint(variable, mode, registerHint);
f8e3ec43b514 Use register hints in new linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4616
diff changeset
453 }
f8e3ec43b514 Use register hints in new linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4616
diff changeset
454 });
f8e3ec43b514 Use register hints in new linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4616
diff changeset
455 if (hintResult != null) {
f8e3ec43b514 Use register hints in new linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4616
diff changeset
456 return asLocation(hintResult);
f8e3ec43b514 Use register hints in new linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4616
diff changeset
457 }
f8e3ec43b514 Use register hints in new linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4616
diff changeset
458 }
f8e3ec43b514 Use register hints in new linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4616
diff changeset
459
f8e3ec43b514 Use register hints in new linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4616
diff changeset
460 CiValue hintResult = processRegisterHint(variable, mode, hintRegisterLocations.get(variable));
f8e3ec43b514 Use register hints in new linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4616
diff changeset
461 if (hintResult != null) {
f8e3ec43b514 Use register hints in new linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4616
diff changeset
462 return asLocation(hintResult);
f8e3ec43b514 Use register hints in new linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4616
diff changeset
463 }
f8e3ec43b514 Use register hints in new linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4616
diff changeset
464
4292
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
465 EnumMap<RegisterFlag, CiRegister[]> categorizedRegs = frameMap.registerConfig.getCategorizedAllocatableRegisters();
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
466 CiRegister[] availableRegs = categorizedRegs.get(variable.flag);
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
467
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
468 Location bestSpillCandidate = null;
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
469 for (CiRegister reg : availableRegs) {
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
470 if (isFree(reg, mode)) {
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
471 return selectRegister(reg, variable, mode);
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
472 } else {
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
473 Location spillCandidate = spillCandidate(reg);
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
474 if (betterSpillCandidate(spillCandidate, bestSpillCandidate)) {
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
475 bestSpillCandidate = spillCandidate;
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
476 }
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
477 }
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
478 }
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
479
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
480 if (flags.contains(OperandFlag.Stack) && betterSpillCandidate(curLocations.get(variable), bestSpillCandidate)) {
4522
cf13124efdd9 Restructure phi functions in LIR; Re-enabled C1Visualizer output
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4435
diff changeset
481 return selectSpillSlot(variable);
4292
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
482 }
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
483
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
484 if (bestSpillCandidate == null) {
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
485 // This should not happen as long as all LIR instructions have fulfillable register constraints. But be safe in product mode and bail out.
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
486 assert false;
4616
53168434d0df Transform some CiBailout into GraalInternalError
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 4525
diff changeset
487 throw new GraalInternalError("No register available");
4292
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
488 }
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
489
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
490 spill(bestSpillCandidate);
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
491
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
492 return selectRegister(asRegister(bestSpillCandidate.location), variable, mode);
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
493 }
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
494
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
495 private void spill(Location value) {
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
496 Location newLoc = spillLocation(value.variable);
4524
dcc8f5c6f394 Refactorings to prepare for LIR project splitting
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4522
diff changeset
497 Debug.log(" spill %s to %s", value, newLoc);
5007
f8e3ec43b514 Use register hints in new linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4616
diff changeset
498 if (!(curOp instanceof StandardOp.PhiLabelOp)) {
4292
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
499 moveResolver.add(value, newLoc);
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
500 }
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
501 curLocations.put(newLoc);
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
502
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
503 CiRegister reg = asRegister(value.location);
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
504 assert curInRegisterState[reg.number] == value;
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
505 curInRegisterState[reg.number] = null;
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
506 if (curOutRegisterState[reg.number] == value) {
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
507 curOutRegisterState[reg.number] = null;
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
508 }
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
509 }
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
510
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
511 private boolean isFree(CiRegister reg, OperandMode mode) {
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
512 switch (mode) {
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
513 case Input: return curInRegisterState[reg.number] == null;
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
514 case Alive: return curInRegisterState[reg.number] == null && curOutRegisterState[reg.number] == null;
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
515 case Temp: return curOutRegisterState[reg.number] == null;
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
516 case Output: return curOutRegisterState[reg.number] == null;
4524
dcc8f5c6f394 Refactorings to prepare for LIR project splitting
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4522
diff changeset
517 default: throw GraalInternalError.shouldNotReachHere();
4292
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
518 }
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
519 }
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
520
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
521 private Location spillCandidate(CiRegister reg) {
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
522 CiValue in = curInRegisterState[reg.number];
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
523 CiValue out = curOutRegisterState[reg.number];
5007
f8e3ec43b514 Use register hints in new linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4616
diff changeset
524 if (in == out && in != null && isLocation(in) && lastUseFor(asLocation(in).variable) < curOp.id()) {
4292
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
525 return asLocation(in);
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
526 }
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
527 return null;
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
528 }
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
529
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
530 private boolean betterSpillCandidate(Location loc, Location compare) {
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
531 if (loc == null) {
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
532 return false;
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
533 }
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
534 if (compare == null) {
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
535 return true;
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
536 }
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
537 if (canonicalSpillLocations.get(loc.variable) != null && canonicalSpillLocations.get(compare.variable) == null) {
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
538 return true;
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
539 }
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
540 return dataFlow.definition(loc.variable) < dataFlow.definition(compare.variable);
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
541 }
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
542
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
543 private Location spillLocation(Variable variable) {
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
544 Location result = canonicalSpillLocations.get(variable);
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
545 if (result == null) {
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
546 result = new Location(variable, frameMap.allocateSpillSlot(variable.kind));
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
547 canonicalSpillLocations.put(result);
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
548 }
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
549 return result;
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
550 }
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
551
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
552 private Location selectRegister(CiRegister reg, Variable variable, OperandMode mode) {
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
553 assert isFree(reg, mode);
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
554
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
555 Location loc = new Location(variable, reg.asValue(variable.kind));
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
556 if (mode == OperandMode.Input || mode == OperandMode.Alive) {
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
557 curInRegisterState[reg.number] = loc;
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
558 }
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
559 curOutRegisterState[reg.number] = loc;
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
560 curLocations.put(loc);
4522
cf13124efdd9 Restructure phi functions in LIR; Re-enabled C1Visualizer output
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4435
diff changeset
561 recordUse(variable);
5007
f8e3ec43b514 Use register hints in new linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4616
diff changeset
562 if (hintRegisterLocations.get(variable) == null) {
f8e3ec43b514 Use register hints in new linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4616
diff changeset
563 hintRegisterLocations.put(loc);
f8e3ec43b514 Use register hints in new linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4616
diff changeset
564 }
4292
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
565
4524
dcc8f5c6f394 Refactorings to prepare for LIR project splitting
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4522
diff changeset
566 Debug.log(" selected register %s", loc);
4292
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
567 return loc;
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
568 }
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
569
4522
cf13124efdd9 Restructure phi functions in LIR; Re-enabled C1Visualizer output
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4435
diff changeset
570 private Location selectSpillSlot(Variable variable) {
4292
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
571 Location loc = spillLocation(variable);
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
572 curLocations.put(loc);
4522
cf13124efdd9 Restructure phi functions in LIR; Re-enabled C1Visualizer output
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4435
diff changeset
573 recordUse(variable);
4292
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
574
4524
dcc8f5c6f394 Refactorings to prepare for LIR project splitting
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4522
diff changeset
575 Debug.log(" selected spill slot %s", loc);
4292
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
576 return loc;
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
577 }
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
578
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4365
diff changeset
579 private boolean checkInputState(final Block block) {
4292
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
580 final BitSet liveState = new BitSet();
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
581 curLocations.forEachLocation(new ValueProcedure() {
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
582 @Override
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
583 public CiValue doValue(CiValue value) {
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
584 liveState.set(asLocation(value).variable.index);
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
585
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
586 for (Block pred : block.getPredecessors()) {
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
587 LocationMap predState = endLocationsFor(pred);
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
588 if (predState != null) {
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
589 assert predState.get(asLocation(value).variable) != null;
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
590 } else {
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
591 assert block.isLoopHeader();
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
592 }
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
593 }
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
594 return value;
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
595 }
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
596 });
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
597 assert liveState.equals(curLiveIn);
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
598 return true;
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
599 }
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
600
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
601
4524
dcc8f5c6f394 Refactorings to prepare for LIR project splitting
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4522
diff changeset
602 private String logCurrentState() {
dcc8f5c6f394 Refactorings to prepare for LIR project splitting
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4522
diff changeset
603 final StringBuilder sb = new StringBuilder();
dcc8f5c6f394 Refactorings to prepare for LIR project splitting
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4522
diff changeset
604 sb.append(" current lcoations: ");
dcc8f5c6f394 Refactorings to prepare for LIR project splitting
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4522
diff changeset
605 curLocations.forEachLocation(new ValueProcedure() {
dcc8f5c6f394 Refactorings to prepare for LIR project splitting
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4522
diff changeset
606 @Override
dcc8f5c6f394 Refactorings to prepare for LIR project splitting
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4522
diff changeset
607 public CiValue doValue(CiValue value) {
dcc8f5c6f394 Refactorings to prepare for LIR project splitting
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4522
diff changeset
608 sb.append(value).append(" ");
dcc8f5c6f394 Refactorings to prepare for LIR project splitting
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4522
diff changeset
609 return value;
dcc8f5c6f394 Refactorings to prepare for LIR project splitting
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4522
diff changeset
610 }
dcc8f5c6f394 Refactorings to prepare for LIR project splitting
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4522
diff changeset
611 });
dcc8f5c6f394 Refactorings to prepare for LIR project splitting
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4522
diff changeset
612 return sb.toString();
4292
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
613 }
48cbd78fa964 First draft of SSA-based linear scan allocator
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
614 }