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