1 /*
2 * Copyright (c) 2014, 2015, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
23 package org.graalvm.compiler.lir.alloc.lsra;
24
25 import static org.graalvm.compiler.lir.LIRValueUtil.isStackSlotValue;
26 import static jdk.vm.ci.code.ValueUtil.asRegister;
27 import static jdk.vm.ci.code.ValueUtil.isRegister;
28
29 import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
30 import org.graalvm.compiler.debug.Debug;
31 import org.graalvm.compiler.debug.Debug.Scope;
32 import org.graalvm.compiler.debug.Indent;
33 import org.graalvm.compiler.lir.alloc.lsra.Interval.RegisterBinding;
34 import org.graalvm.compiler.lir.alloc.lsra.Interval.RegisterBindingLists;
35 import org.graalvm.compiler.lir.alloc.lsra.Interval.RegisterPriority;
36 import org.graalvm.compiler.lir.alloc.lsra.Interval.State;
37 import org.graalvm.compiler.options.Option;
38 import org.graalvm.compiler.options.OptionType;
39 import org.graalvm.compiler.options.OptionKey;
40
41 import jdk.vm.ci.code.Register;
42 import jdk.vm.ci.meta.AllocatableValue;
43
44 public class OptimizingLinearScanWalker extends LinearScanWalker {
45
46 public static class Options {
47 // @formatter:off
48 @Option(help = "Enable LSRA optimization", type = OptionType.Debug)
49 public static final OptionKey<Boolean> LSRAOptimization = new OptionKey<>(false);
50 @Option(help = "LSRA optimization: Only split but do not reassign", type = OptionType.Debug)
51 public static final OptionKey<Boolean> LSRAOptSplitOnly = new OptionKey<>(false);
52 // @formatter:on
53 }
54
55 OptimizingLinearScanWalker(LinearScan allocator, Interval unhandledFixedFirst, Interval unhandledAnyFirst) {
56 super(allocator, unhandledFixedFirst, unhandledAnyFirst);
57 }
58
59 @SuppressWarnings("try")
60 @Override
61 protected void handleSpillSlot(Interval interval) {
62 assert interval.location() != null : "interval not assigned " + interval;
63 if (interval.canMaterialize()) {
64 assert !isStackSlotValue(interval.location()) : "interval can materialize but assigned to a stack slot " + interval;
65 return;
66 }
67 assert isStackSlotValue(interval.location()) : "interval not assigned to a stack slot " + interval;
68 try (Scope s1 = Debug.scope("LSRAOptimization")) {
69 Debug.log("adding stack to unhandled list %s", interval);
70 unhandledLists.addToListSortedByStartAndUsePositions(RegisterBinding.Stack, interval);
71 }
72 }
73
74 @SuppressWarnings("unused")
75 private static void printRegisterBindingList(RegisterBindingLists list, RegisterBinding binding) {
76 for (Interval interval = list.get(binding); !interval.isEndMarker(); interval = interval.next) {
77 Debug.log("%s", interval);
78 }
79 }
80
81 @SuppressWarnings("try")
82 @Override
83 void walk() {
84 try (Scope s = Debug.scope("OptimizingLinearScanWalker")) {
85 for (AbstractBlockBase<?> block : allocator.sortedBlocks()) {
86 optimizeBlock(block);
87 }
88 }
89 super.walk();
90 }
91
92 @SuppressWarnings("try")
93 private void optimizeBlock(AbstractBlockBase<?> block) {
94 if (block.getPredecessorCount() == 1) {
95 int nextBlock = allocator.getFirstLirInstructionId(block);
96 try (Scope s1 = Debug.scope("LSRAOptimization")) {
97 Debug.log("next block: %s (%d)", block, nextBlock);
98 }
99 try (Indent indent0 = Debug.indent()) {
100 walkTo(nextBlock);
101
102 try (Scope s1 = Debug.scope("LSRAOptimization")) {
103 boolean changed = true;
104 // we need to do this because the active lists might change
105 loop: while (changed) {
106 changed = false;
107 try (Indent indent1 = Debug.logAndIndent("Active intervals: (block %s [%d])", block, nextBlock)) {
108 for (Interval active = activeLists.get(RegisterBinding.Any); !active.isEndMarker(); active = active.next) {
109 Debug.log("active (any): %s", active);
110 if (optimize(nextBlock, block, active, RegisterBinding.Any)) {
111 changed = true;
112 break loop;
113 }
114 }
115 for (Interval active = activeLists.get(RegisterBinding.Stack); !active.isEndMarker(); active = active.next) {
116 Debug.log("active (stack): %s", active);
117 if (optimize(nextBlock, block, active, RegisterBinding.Stack)) {
118 changed = true;
119 break loop;
120 }
121 }
122 }
123 }
124 }
125 }
126 }
127 }
128
129 @SuppressWarnings("try")
130 private boolean optimize(int currentPos, AbstractBlockBase<?> currentBlock, Interval currentInterval, RegisterBinding binding) {
131 // BEGIN initialize and sanity checks
132 assert currentBlock != null : "block must not be null";
133 assert currentInterval != null : "interval must not be null";
134
135 assert currentBlock.getPredecessorCount() == 1 : "more than one predecessors -> optimization not possible";
136
137 if (!currentInterval.isSplitChild()) {
138 // interval is not a split child -> no need for optimization
139 return false;
140 }
141
142 if (currentInterval.from() == currentPos) {
143 // the interval starts at the current position so no need for splitting
144 return false;
145 }
146
147 // get current location
148 AllocatableValue currentLocation = currentInterval.location();
149 assert currentLocation != null : "active intervals must have a location assigned!";
150
151 // get predecessor stuff
152 AbstractBlockBase<?> predecessorBlock = currentBlock.getPredecessors()[0];
153 int predEndId = allocator.getLastLirInstructionId(predecessorBlock);
154 Interval predecessorInterval = currentInterval.getIntervalCoveringOpId(predEndId);
155 assert predecessorInterval != null : "variable not live at the end of the only predecessor! " + predecessorBlock + " -> " + currentBlock + " interval: " + currentInterval;
156 AllocatableValue predecessorLocation = predecessorInterval.location();
157 assert predecessorLocation != null : "handled intervals must have a location assigned!";
158
159 // END initialize and sanity checks
160
161 if (currentLocation.equals(predecessorLocation)) {
162 // locations are already equal -> nothing to optimize
163 return false;
164 }
165
166 if (!isStackSlotValue(predecessorLocation) && !isRegister(predecessorLocation)) {
167 assert predecessorInterval.canMaterialize();
168 // value is materialized -> no need for optimization
169 return false;
170 }
171
172 assert isStackSlotValue(currentLocation) || isRegister(currentLocation) : "current location not a register or stack slot " + currentLocation;
173
174 try (Indent indent = Debug.logAndIndent("location differs: %s vs. %s", predecessorLocation, currentLocation)) {
175 // split current interval at current position
176 Debug.log("splitting at position %d", currentPos);
177
178 assert allocator.isBlockBegin(currentPos) && ((currentPos & 1) == 0) : "split pos must be even when on block boundary";
179
180 Interval splitPart = currentInterval.split(currentPos, allocator);
181 activeLists.remove(binding, currentInterval);
182
183 assert splitPart.from() >= currentPosition : "cannot append new interval before current walk position";
184
185 // the currentSplitChild is needed later when moves are inserted for reloading
186 assert splitPart.currentSplitChild() == currentInterval : "overwriting wrong currentSplitChild";
187 splitPart.makeCurrentSplitChild();
188
189 if (Debug.isLogEnabled()) {
190 Debug.log("left interval : %s", currentInterval.logString(allocator));
191 Debug.log("right interval : %s", splitPart.logString(allocator));
192 }
193
194 if (Options.LSRAOptSplitOnly.getValue(allocator.getOptions())) {
195 // just add the split interval to the unhandled list
196 unhandledLists.addToListSortedByStartAndUsePositions(RegisterBinding.Any, splitPart);
197 } else {
198 if (isRegister(predecessorLocation)) {
199 splitRegisterInterval(splitPart, asRegister(predecessorLocation));
200 } else {
201 assert isStackSlotValue(predecessorLocation);
202 Debug.log("assigning interval %s to %s", splitPart, predecessorLocation);
203 splitPart.assignLocation(predecessorLocation);
204 // activate interval
205 activeLists.addToListSortedByCurrentFromPositions(RegisterBinding.Stack, splitPart);
206 splitPart.state = State.Active;
207
208 splitStackInterval(splitPart);
209 }
210 }
211 }
212 return true;
213 }
214
215 @SuppressWarnings("try")
216 private void splitRegisterInterval(Interval interval, Register reg) {
217 // collect current usage of registers
218 initVarsForAlloc(interval);
219 initUseLists(false);
220 spillExcludeActiveFixed();
221 // spillBlockUnhandledFixed(cur);
222 assert unhandledLists.get(RegisterBinding.Fixed).isEndMarker() : "must not have unhandled fixed intervals because all fixed intervals have a use at position 0";
223 spillBlockInactiveFixed(interval);
224 spillCollectActiveAny(RegisterPriority.LiveAtLoopEnd);
225 spillCollectInactiveAny(interval);
226
227 if (Debug.isLogEnabled()) {
228 try (Indent indent2 = Debug.logAndIndent("state of registers:")) {
229 for (Register register : availableRegs) {
230 int i = register.number;
231 try (Indent indent3 = Debug.logAndIndent("reg %d: usePos: %d, blockPos: %d, intervals: ", i, usePos[i], blockPos[i])) {
232 for (int j = 0; j < spillIntervals[i].size(); j++) {
233 Debug.log("%d ", spillIntervals[i].get(j).operandNumber);
234 }
235 }
236 }
237 }
238 }
239
240 // the register must be free at least until this position
241 boolean needSplit = blockPos[reg.number] <= interval.to();
242
243 int splitPos = blockPos[reg.number];
244
245 assert splitPos > 0 : "invalid splitPos";
246 assert needSplit || splitPos > interval.from() : "splitting interval at from";
247
248 Debug.log("assigning interval %s to %s", interval, reg);
249 interval.assignLocation(reg.asValue(interval.kind()));
250 if (needSplit) {
251 // register not available for full interval : so split it
252 splitWhenPartialRegisterAvailable(interval, splitPos);
253 }
254
255 // perform splitting and spilling for all affected intervals
256 splitAndSpillIntersectingIntervals(reg);
257
258 // activate interval
259 activeLists.addToListSortedByCurrentFromPositions(RegisterBinding.Any, interval);
260 interval.state = State.Active;
261
262 }
263 }