1 /*
2 * Copyright (c) 2015, 2016, 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.stackslotalloc;
24
25 import static org.graalvm.compiler.lir.LIRValueUtil.asVirtualStackSlot;
26 import static org.graalvm.compiler.lir.LIRValueUtil.isVirtualStackSlot;
27
28 import java.util.ArrayDeque;
29 import java.util.ArrayList;
30 import java.util.BitSet;
31 import java.util.Deque;
32 import java.util.EnumSet;
33
34 import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
35 import org.graalvm.compiler.core.common.cfg.BlockMap;
36 import org.graalvm.compiler.debug.CounterKey;
37 import org.graalvm.compiler.debug.DebugContext;
38 import org.graalvm.compiler.debug.Indent;
39 import org.graalvm.compiler.lir.InstructionValueConsumer;
40 import org.graalvm.compiler.lir.InstructionValueProcedure;
41 import org.graalvm.compiler.lir.LIR;
42 import org.graalvm.compiler.lir.LIRInstruction;
43 import org.graalvm.compiler.lir.LIRInstruction.OperandFlag;
44 import org.graalvm.compiler.lir.LIRInstruction.OperandMode;
45 import org.graalvm.compiler.lir.VirtualStackSlot;
46 import org.graalvm.util.EconomicSet;
47 import org.graalvm.util.Equivalence;
48
49 import jdk.vm.ci.meta.Value;
50
51 /**
52 * Calculates the stack intervals using a worklist-based backwards data-flow analysis.
53 */
54 final class FixPointIntervalBuilder {
55 private final BlockMap<BitSet> liveInMap;
56 private final BlockMap<BitSet> liveOutMap;
57 private final LIR lir;
58 private final int maxOpId;
59 private final StackInterval[] stackSlotMap;
60 private final EconomicSet<LIRInstruction> usePos;
61
62 /**
63 * The number of allocated stack slots.
64 */
65 private static final CounterKey uninitializedSlots = DebugContext.counter("StackSlotAllocator[uninitializedSlots]");
66
67 FixPointIntervalBuilder(LIR lir, StackInterval[] stackSlotMap, int maxOpId) {
68 this.lir = lir;
69 this.stackSlotMap = stackSlotMap;
70 this.maxOpId = maxOpId;
71 liveInMap = new BlockMap<>(lir.getControlFlowGraph());
72 liveOutMap = new BlockMap<>(lir.getControlFlowGraph());
73 this.usePos = EconomicSet.create(Equivalence.IDENTITY);
74 }
75
76 /**
77 * Builds the lifetime intervals for {@link VirtualStackSlot virtual stack slots}, sets up
78 * {@link #stackSlotMap} and returns a set of use positions, i.e. instructions that contain
79 * virtual stack slots.
80 */
81 EconomicSet<LIRInstruction> build() {
82 Deque<AbstractBlockBase<?>> worklist = new ArrayDeque<>();
83 AbstractBlockBase<?>[] blocks = lir.getControlFlowGraph().getBlocks();
84 for (int i = blocks.length - 1; i >= 0; i--) {
85 worklist.add(blocks[i]);
86 }
87 for (AbstractBlockBase<?> block : lir.getControlFlowGraph().getBlocks()) {
88 liveInMap.put(block, new BitSet(stackSlotMap.length));
89 }
90 while (!worklist.isEmpty()) {
91 AbstractBlockBase<?> block = worklist.poll();
92 processBlock(block, worklist);
93 }
94 return usePos;
95 }
96
97 /**
98 * Merge outSet with in-set of successors.
99 */
100 private boolean updateOutBlock(AbstractBlockBase<?> block) {
101 BitSet union = new BitSet(stackSlotMap.length);
102 for (AbstractBlockBase<?> succ : block.getSuccessors()) {
103 union.or(liveInMap.get(succ));
104 }
105 BitSet outSet = liveOutMap.get(block);
106 // check if changed
107 if (outSet == null || !union.equals(outSet)) {
108 liveOutMap.put(block, union);
109 return true;
110 }
111 return false;
112 }
113
114 @SuppressWarnings("try")
115 private void processBlock(AbstractBlockBase<?> block, Deque<AbstractBlockBase<?>> worklist) {
116 DebugContext debug = lir.getDebug();
117 if (updateOutBlock(block)) {
118 try (Indent indent = debug.logAndIndent("handle block %s", block)) {
119 ArrayList<LIRInstruction> instructions = lir.getLIRforBlock(block);
120 // get out set and mark intervals
121 BitSet outSet = liveOutMap.get(block);
122 markOutInterval(outSet, getBlockEnd(instructions));
123 printLiveSet("liveOut", outSet);
124
125 // process instructions
126 BlockClosure closure = new BlockClosure((BitSet) outSet.clone());
127 for (int i = instructions.size() - 1; i >= 0; i--) {
128 LIRInstruction inst = instructions.get(i);
129 closure.processInstructionBottomUp(inst);
130 }
131
132 // add predecessors to work list
133 for (AbstractBlockBase<?> b : block.getPredecessors()) {
134 worklist.add(b);
135 }
136 // set in set and mark intervals
137 BitSet inSet = closure.getCurrentSet();
138 liveInMap.put(block, inSet);
139 markInInterval(inSet, getBlockBegin(instructions));
140 printLiveSet("liveIn", inSet);
141 }
142 }
143 }
144
145 @SuppressWarnings("try")
146 private void printLiveSet(String label, BitSet liveSet) {
147 DebugContext debug = lir.getDebug();
148 if (debug.isLogEnabled()) {
149 try (Indent indent = debug.logAndIndent(label)) {
150 debug.log("%s", liveSetToString(liveSet));
151 }
152 }
153 }
154
155 private String liveSetToString(BitSet liveSet) {
156 StringBuilder sb = new StringBuilder();
157 for (int i = liveSet.nextSetBit(0); i >= 0; i = liveSet.nextSetBit(i + 1)) {
158 StackInterval interval = getIntervalFromStackId(i);
159 sb.append(interval.getOperand()).append(" ");
160 }
161 return sb.toString();
162 }
163
164 private void markOutInterval(BitSet outSet, int blockEndOpId) {
165 DebugContext debug = lir.getDebug();
166 for (int i = outSet.nextSetBit(0); i >= 0; i = outSet.nextSetBit(i + 1)) {
167 StackInterval interval = getIntervalFromStackId(i);
168 debug.log("mark live operand: %s", interval.getOperand());
169 interval.addTo(blockEndOpId);
170 }
171 }
172
173 private void markInInterval(BitSet inSet, int blockFirstOpId) {
174 DebugContext debug = lir.getDebug();
175 for (int i = inSet.nextSetBit(0); i >= 0; i = inSet.nextSetBit(i + 1)) {
176 StackInterval interval = getIntervalFromStackId(i);
177 debug.log("mark live operand: %s", interval.getOperand());
178 interval.addFrom(blockFirstOpId);
179 }
180 }
181
182 private final class BlockClosure {
183 private final BitSet currentSet;
184
185 private BlockClosure(BitSet set) {
186 currentSet = set;
187 }
188
189 private BitSet getCurrentSet() {
190 return currentSet;
191 }
192
193 /**
194 * Process all values of an instruction bottom-up, i.e. definitions before usages. Values
195 * that start or end at the current operation are not included.
196 */
197 @SuppressWarnings("try")
198 private void processInstructionBottomUp(LIRInstruction op) {
199 DebugContext debug = lir.getDebug();
200 try (Indent indent = debug.logAndIndent("handle op %d, %s", op.id(), op)) {
201 // kills
202 op.visitEachTemp(defConsumer);
203 op.visitEachOutput(defConsumer);
204
205 // gen - values that are considered alive for this state
206 op.visitEachAlive(useConsumer);
207 op.visitEachState(useConsumer);
208 // mark locations
209 // gen
210 op.visitEachInput(useConsumer);
211 }
212 }
213
214 InstructionValueConsumer useConsumer = new InstructionValueConsumer() {
215 @Override
216 public void visitValue(LIRInstruction inst, Value operand, OperandMode mode, EnumSet<OperandFlag> flags) {
217 if (isVirtualStackSlot(operand)) {
218 DebugContext debug = lir.getDebug();
219 VirtualStackSlot vslot = asVirtualStackSlot(operand);
220 addUse(vslot, inst, flags);
221 addRegisterHint(inst, vslot, mode, flags, false);
222 usePos.add(inst);
223 debug.log("set operand: %s", operand);
224 currentSet.set(vslot.getId());
225 }
226 }
227 };
228
229 InstructionValueConsumer defConsumer = new InstructionValueConsumer() {
230 @Override
231 public void visitValue(LIRInstruction inst, Value operand, OperandMode mode, EnumSet<OperandFlag> flags) {
232 if (isVirtualStackSlot(operand)) {
233 DebugContext debug = lir.getDebug();
234 VirtualStackSlot vslot = asVirtualStackSlot(operand);
235 addDef(vslot, inst);
236 addRegisterHint(inst, vslot, mode, flags, true);
237 usePos.add(inst);
238 debug.log("clear operand: %s", operand);
239 currentSet.clear(vslot.getId());
240 }
241
242 }
243 };
244
245 private void addUse(VirtualStackSlot stackSlot, LIRInstruction inst, EnumSet<OperandFlag> flags) {
246 StackInterval interval = getOrCreateInterval(stackSlot);
247 if (flags.contains(OperandFlag.UNINITIALIZED)) {
248 // Stack slot is marked uninitialized so we have to assume it is live all
249 // the time.
250 DebugContext debug = lir.getDebug();
251 if (debug.isCountEnabled() && !(interval.from() == 0 && interval.to() == maxOpId)) {
252 uninitializedSlots.increment(debug);
253 }
254 interval.addFrom(0);
255 interval.addTo(maxOpId);
256 } else {
257 interval.addTo(inst.id());
258 }
259 }
260
261 private void addDef(VirtualStackSlot stackSlot, LIRInstruction inst) {
262 StackInterval interval = getOrCreateInterval(stackSlot);
263 interval.addFrom(inst.id());
264 }
265
266 void addRegisterHint(final LIRInstruction op, VirtualStackSlot targetValue, OperandMode mode, EnumSet<OperandFlag> flags, final boolean hintAtDef) {
267 if (flags.contains(OperandFlag.HINT)) {
268 InstructionValueProcedure proc = new InstructionValueProcedure() {
269 @Override
270 public Value doValue(LIRInstruction instruction, Value registerHint, OperandMode vaueMode, EnumSet<OperandFlag> valueFlags) {
271 if (isVirtualStackSlot(registerHint)) {
272 StackInterval from = getOrCreateInterval((VirtualStackSlot) registerHint);
273 StackInterval to = getOrCreateInterval(targetValue);
274
275 // hints always point from def to use
276 if (hintAtDef) {
277 to.setLocationHint(from);
278 } else {
279 from.setLocationHint(to);
280 }
281 DebugContext debug = lir.getDebug();
282 if (debug.isLogEnabled()) {
283 debug.log("operation %s at opId %d: added hint from interval %s to %s", op, op.id(), from, to);
284 }
285
286 return registerHint;
287 }
288 return null;
289 }
290 };
291 op.forEachRegisterHint(targetValue, mode, proc);
292 }
293 }
294
295 }
296
297 private StackInterval get(VirtualStackSlot stackSlot) {
298 return stackSlotMap[stackSlot.getId()];
299 }
300
301 private void put(VirtualStackSlot stackSlot, StackInterval interval) {
302 stackSlotMap[stackSlot.getId()] = interval;
303 }
304
305 private StackInterval getOrCreateInterval(VirtualStackSlot stackSlot) {
306 StackInterval interval = get(stackSlot);
307 if (interval == null) {
308 interval = new StackInterval(stackSlot, stackSlot.getValueKind());
309 put(stackSlot, interval);
310 }
311 return interval;
312 }
313
314 private StackInterval getIntervalFromStackId(int id) {
315 return stackSlotMap[id];
316 }
317
318 private static int getBlockBegin(ArrayList<LIRInstruction> instructions) {
319 return instructions.get(0).id();
320 }
321
322 private static int getBlockEnd(ArrayList<LIRInstruction> instructions) {
323 return instructions.get(instructions.size() - 1).id() + 1;
324 }
325
326 }