1 /*
2 * Copyright (c) 2015, 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
24
25 package org.graalvm.compiler.lir.alloc.lsra;
26
27 import static org.graalvm.compiler.core.common.cfg.AbstractControlFlowGraph.commonDominator;
28 import static org.graalvm.compiler.core.common.cfg.AbstractControlFlowGraph.dominates;
29 import static org.graalvm.compiler.lir.LIRValueUtil.isStackSlotValue;
30
31 import java.util.Iterator;
32
33 import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
34 import org.graalvm.compiler.debug.CounterKey;
35 import org.graalvm.compiler.debug.DebugContext;
36 import org.graalvm.compiler.debug.Indent;
37 import org.graalvm.compiler.lir.LIRInsertionBuffer;
38 import org.graalvm.compiler.lir.LIRInstruction;
39 import org.graalvm.compiler.lir.LIRInstruction.OperandMode;
40 import org.graalvm.compiler.lir.alloc.lsra.Interval.SpillState;
41 import org.graalvm.compiler.lir.gen.LIRGenerationResult;
42 import org.graalvm.compiler.lir.phases.AllocationPhase.AllocationContext;
43
44 import jdk.vm.ci.code.TargetDescription;
45 import jdk.vm.ci.meta.AllocatableValue;
46
47 public final class LinearScanOptimizeSpillPositionPhase extends LinearScanAllocationPhase {
48
49 private static final CounterKey betterSpillPos = DebugContext.counter("BetterSpillPosition");
50 private static final CounterKey betterSpillPosWithLowerProbability = DebugContext.counter("BetterSpillPositionWithLowerProbability");
51
52 private final LinearScan allocator;
53 private DebugContext debug;
54
55 LinearScanOptimizeSpillPositionPhase(LinearScan allocator) {
56 this.allocator = allocator;
57 this.debug = allocator.getDebug();
58 }
59
60 @Override
61 protected void run(TargetDescription target, LIRGenerationResult lirGenRes, AllocationContext context) {
62 optimizeSpillPosition(lirGenRes);
63 allocator.printIntervals("After optimize spill position");
64 }
65
66 @SuppressWarnings("try")
67 private void optimizeSpillPosition(LIRGenerationResult res) {
68 try (Indent indent0 = debug.logAndIndent("OptimizeSpillPositions")) {
69 LIRInsertionBuffer[] insertionBuffers = new LIRInsertionBuffer[allocator.getLIR().linearScanOrder().length];
70 for (Interval interval : allocator.intervals()) {
71 optimizeInterval(insertionBuffers, interval, res);
72 }
73 for (LIRInsertionBuffer insertionBuffer : insertionBuffers) {
74 if (insertionBuffer != null) {
75 assert insertionBuffer.initialized() : "Insertion buffer is nonnull but not initialized!";
76 insertionBuffer.finish();
77 }
78 }
79 }
80 }
81
82 @SuppressWarnings("try")
83 private void optimizeInterval(LIRInsertionBuffer[] insertionBuffers, Interval interval, LIRGenerationResult res) {
84 if (interval == null || !interval.isSplitParent() || interval.spillState() != SpillState.SpillInDominator) {
85 return;
86 }
87 AbstractBlockBase<?> defBlock = allocator.blockForId(interval.spillDefinitionPos());
88 AbstractBlockBase<?> spillBlock = null;
89 Interval firstSpillChild = null;
90 try (Indent indent = debug.logAndIndent("interval %s (%s)", interval, defBlock)) {
91 for (Interval splitChild : interval.getSplitChildren()) {
92 if (isStackSlotValue(splitChild.location())) {
93 if (firstSpillChild == null || splitChild.from() < firstSpillChild.from()) {
94 firstSpillChild = splitChild;
95 } else {
96 assert firstSpillChild.from() < splitChild.from();
97 }
98 // iterate all blocks where the interval has use positions
99 for (AbstractBlockBase<?> splitBlock : blocksForInterval(splitChild)) {
100 if (dominates(defBlock, splitBlock)) {
101 debug.log("Split interval %s, block %s", splitChild, splitBlock);
102 if (spillBlock == null) {
103 spillBlock = splitBlock;
104 } else {
105 spillBlock = commonDominator(spillBlock, splitBlock);
106 assert spillBlock != null;
107 }
108 }
109 }
110 }
111 }
112 if (spillBlock == null) {
113 debug.log("not spill interval found");
114 // no spill interval
115 interval.setSpillState(SpillState.StoreAtDefinition);
116 return;
117 }
118 debug.log(DebugContext.VERBOSE_LEVEL, "Spill block candidate (initial): %s", spillBlock);
119 // move out of loops
120 if (defBlock.getLoopDepth() < spillBlock.getLoopDepth()) {
121 spillBlock = moveSpillOutOfLoop(defBlock, spillBlock);
122 }
123 debug.log(DebugContext.VERBOSE_LEVEL, "Spill block candidate (after loop optimizaton): %s", spillBlock);
124
125 /*
126 * The spill block is the begin of the first split child (aka the value is on the
127 * stack).
128 *
129 * The problem is that if spill block has more than one predecessor, the values at the
130 * end of the predecessors might differ. Therefore, we would need a spill move in all
131 * predecessors. To avoid this we spill in the dominator.
132 */
133 assert firstSpillChild != null;
134 if (!defBlock.equals(spillBlock) && spillBlock.equals(allocator.blockForId(firstSpillChild.from()))) {
135 AbstractBlockBase<?> dom = spillBlock.getDominator();
136 if (debug.isLogEnabled()) {
137 debug.log("Spill block (%s) is the beginning of a spill child -> use dominator (%s)", spillBlock, dom);
138 }
139 spillBlock = dom;
140 }
141 if (defBlock.equals(spillBlock)) {
142 debug.log(DebugContext.VERBOSE_LEVEL, "Definition is the best choice: %s", defBlock);
143 // definition is the best choice
144 interval.setSpillState(SpillState.StoreAtDefinition);
145 return;
146 }
147 assert dominates(defBlock, spillBlock);
148 betterSpillPos.increment(debug);
149 if (debug.isLogEnabled()) {
150 debug.log("Better spill position found (Block %s)", spillBlock);
151 }
152
153 if (defBlock.probability() <= spillBlock.probability()) {
154 debug.log(DebugContext.VERBOSE_LEVEL, "Definition has lower probability %s (%f) is lower than spill block %s (%f)", defBlock, defBlock.probability(), spillBlock,
155 spillBlock.probability());
156 // better spill block has the same probability -> do nothing
157 interval.setSpillState(SpillState.StoreAtDefinition);
158 return;
159 }
160
161 LIRInsertionBuffer insertionBuffer = insertionBuffers[spillBlock.getId()];
162 if (insertionBuffer == null) {
163 insertionBuffer = new LIRInsertionBuffer();
164 insertionBuffers[spillBlock.getId()] = insertionBuffer;
165 insertionBuffer.init(allocator.getLIR().getLIRforBlock(spillBlock));
166 }
167 int spillOpId = allocator.getFirstLirInstructionId(spillBlock);
168 // insert spill move
169 AllocatableValue fromLocation = interval.getSplitChildAtOpId(spillOpId, OperandMode.DEF, allocator).location();
170 AllocatableValue toLocation = LinearScan.canonicalSpillOpr(interval);
171 LIRInstruction move = allocator.getSpillMoveFactory().createMove(toLocation, fromLocation);
172 move.setComment(res, "LSRAOptimizeSpillPos: optimize spill pos");
173 debug.log(DebugContext.VERBOSE_LEVEL, "Insert spill move %s", move);
174 move.setId(LinearScan.DOMINATOR_SPILL_MOVE_ID);
175 /*
176 * We can use the insertion buffer directly because we always insert at position 1.
177 */
178 insertionBuffer.append(1, move);
179
180 betterSpillPosWithLowerProbability.increment(debug);
181 interval.setSpillDefinitionPos(spillOpId);
182 }
183 }
184
185 /**
186 * Iterate over all {@link AbstractBlockBase blocks} of an interval.
187 */
188 private class IntervalBlockIterator implements Iterator<AbstractBlockBase<?>> {
189
190 Range range;
191 AbstractBlockBase<?> block;
192
193 IntervalBlockIterator(Interval interval) {
194 range = interval.first();
195 block = allocator.blockForId(range.from);
196 }
197
198 @Override
199 public AbstractBlockBase<?> next() {
200 AbstractBlockBase<?> currentBlock = block;
201 int nextBlockIndex = block.getLinearScanNumber() + 1;
202 if (nextBlockIndex < allocator.sortedBlocks().length) {
203 block = allocator.sortedBlocks()[nextBlockIndex];
204 if (range.to <= allocator.getFirstLirInstructionId(block)) {
205 range = range.next;
206 if (range.isEndMarker()) {
207 block = null;
208 } else {
209 block = allocator.blockForId(range.from);
210 }
211 }
212 } else {
213 block = null;
214 }
215 return currentBlock;
216 }
217
218 @Override
219 public boolean hasNext() {
220 return block != null;
221 }
222 }
223
224 private Iterable<AbstractBlockBase<?>> blocksForInterval(Interval interval) {
225 return new Iterable<AbstractBlockBase<?>>() {
226 @Override
227 public Iterator<AbstractBlockBase<?>> iterator() {
228 return new IntervalBlockIterator(interval);
229 }
230 };
231 }
232
233 private static AbstractBlockBase<?> moveSpillOutOfLoop(AbstractBlockBase<?> defBlock, AbstractBlockBase<?> spillBlock) {
234 int defLoopDepth = defBlock.getLoopDepth();
235 for (AbstractBlockBase<?> block = spillBlock.getDominator(); !defBlock.equals(block); block = block.getDominator()) {
236 assert block != null : "spill block not dominated by definition block?";
237 if (block.getLoopDepth() <= defLoopDepth) {
238 assert block.getLoopDepth() == defLoopDepth : "Cannot spill an interval outside of the loop where it is defined!";
239 return block;
240 }
241 }
242 return defBlock;
243 }
244 }