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.BitSet;
30 import java.util.Deque;
31 import java.util.EnumSet;
32 import java.util.HashSet;
33 import java.util.List;
34 import java.util.Set;
35
36 import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
37 import org.graalvm.compiler.core.common.cfg.BlockMap;
38 import org.graalvm.compiler.debug.Debug;
39 import org.graalvm.compiler.debug.DebugCounter;
40 import org.graalvm.compiler.debug.Indent;
41 import org.graalvm.compiler.lir.InstructionValueConsumer;
42 import org.graalvm.compiler.lir.InstructionValueProcedure;
43 import org.graalvm.compiler.lir.LIR;
44 import org.graalvm.compiler.lir.LIRInstruction;
45 import org.graalvm.compiler.lir.LIRInstruction.OperandFlag;
46 import org.graalvm.compiler.lir.LIRInstruction.OperandMode;
47 import org.graalvm.compiler.lir.VirtualStackSlot;
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 HashSet<LIRInstruction> usePos;
61
62 /**
63 * The number of allocated stack slots.
64 */
65 private static final DebugCounter uninitializedSlots = Debug.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 = new HashSet<>();
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 Set<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 if (updateOutBlock(block)) {
117 try (Indent indent = Debug.logAndIndent("handle block %s", block)) {
118 List<LIRInstruction> instructions = lir.getLIRforBlock(block);
119 // get out set and mark intervals
120 BitSet outSet = liveOutMap.get(block);
121 markOutInterval(outSet, getBlockEnd(instructions));
122 printLiveSet("liveOut", outSet);
123
124 // process instructions
125 BlockClosure closure = new BlockClosure((BitSet) outSet.clone());
126 for (int i = instructions.size() - 1; i >= 0; i--) {
127 LIRInstruction inst = instructions.get(i);
128 closure.processInstructionBottomUp(inst);
129 }
130
131 // add predecessors to work list
132 for (AbstractBlockBase<?> b : block.getPredecessors()) {
133 worklist.add(b);
134 }
135 // set in set and mark intervals
136 BitSet inSet = closure.getCurrentSet();
137 liveInMap.put(block, inSet);
138 markInInterval(inSet, getBlockBegin(instructions));
139 printLiveSet("liveIn", inSet);
140 }
141 }
142 }
143
144 @SuppressWarnings("try")
145 private void printLiveSet(String label, BitSet liveSet) {
146 if (Debug.isLogEnabled()) {
147 try (Indent indent = Debug.logAndIndent(label)) {
148 Debug.log("%s", liveSetToString(liveSet));
149 }
150 }
151 }
152
153 private String liveSetToString(BitSet liveSet) {
154 StringBuilder sb = new StringBuilder();
155 for (int i = liveSet.nextSetBit(0); i >= 0; i = liveSet.nextSetBit(i + 1)) {
156 StackInterval interval = getIntervalFromStackId(i);
157 sb.append(interval.getOperand()).append(" ");
158 }
159 return sb.toString();
160 }
161
162 private void markOutInterval(BitSet outSet, int blockEndOpId) {
163 for (int i = outSet.nextSetBit(0); i >= 0; i = outSet.nextSetBit(i + 1)) {
164 StackInterval interval = getIntervalFromStackId(i);
165 Debug.log("mark live operand: %s", interval.getOperand());
166 interval.addTo(blockEndOpId);
167 }
168 }
169
170 private void markInInterval(BitSet inSet, int blockFirstOpId) {
171 for (int i = inSet.nextSetBit(0); i >= 0; i = inSet.nextSetBit(i + 1)) {
172 StackInterval interval = getIntervalFromStackId(i);
173 Debug.log("mark live operand: %s", interval.getOperand());
174 interval.addFrom(blockFirstOpId);
175 }
176 }
177
178 private final class BlockClosure {
179 private final BitSet currentSet;
180
181 private BlockClosure(BitSet set) {
182 currentSet = set;
183 }
184
185 private BitSet getCurrentSet() {
186 return currentSet;
187 }
188
189 /**
190 * Process all values of an instruction bottom-up, i.e. definitions before usages. Values
191 * that start or end at the current operation are not included.
192 */
193 @SuppressWarnings("try")
194 private void processInstructionBottomUp(LIRInstruction op) {
195 try (Indent indent = Debug.logAndIndent("handle op %d, %s", op.id(), op)) {
196 // kills
197 op.visitEachTemp(defConsumer);
198 op.visitEachOutput(defConsumer);
199
200 // gen - values that are considered alive for this state
201 op.visitEachAlive(useConsumer);
202 op.visitEachState(useConsumer);
203 // mark locations
204 // gen
205 op.visitEachInput(useConsumer);
206 }
207 }
208
209 InstructionValueConsumer useConsumer = new InstructionValueConsumer() {
210 @Override
211 public void visitValue(LIRInstruction inst, Value operand, OperandMode mode, EnumSet<OperandFlag> flags) {
212 if (isVirtualStackSlot(operand)) {
213 VirtualStackSlot vslot = asVirtualStackSlot(operand);
214 addUse(vslot, inst, flags);
215 addRegisterHint(inst, vslot, mode, flags, false);
216 usePos.add(inst);
217 Debug.log("set operand: %s", operand);
218 currentSet.set(vslot.getId());
219 }
220 }
221 };
222
223 InstructionValueConsumer defConsumer = new InstructionValueConsumer() {
224 @Override
225 public void visitValue(LIRInstruction inst, Value operand, OperandMode mode, EnumSet<OperandFlag> flags) {
226 if (isVirtualStackSlot(operand)) {
227 VirtualStackSlot vslot = asVirtualStackSlot(operand);
228 addDef(vslot, inst);
229 addRegisterHint(inst, vslot, mode, flags, true);
230 usePos.add(inst);
231 Debug.log("clear operand: %s", operand);
232 currentSet.clear(vslot.getId());
233 }
234
235 }
236 };
237
238 private void addUse(VirtualStackSlot stackSlot, LIRInstruction inst, EnumSet<OperandFlag> flags) {
239 StackInterval interval = getOrCreateInterval(stackSlot);
240 if (flags.contains(OperandFlag.UNINITIALIZED)) {
241 // Stack slot is marked uninitialized so we have to assume it is live all
242 // the time.
243 if (Debug.isCountEnabled() && !(interval.from() == 0 && interval.to() == maxOpId)) {
244 uninitializedSlots.increment();
245 }
246 interval.addFrom(0);
247 interval.addTo(maxOpId);
248 } else {
249 interval.addTo(inst.id());
250 }
251 }
252
253 private void addDef(VirtualStackSlot stackSlot, LIRInstruction inst) {
254 StackInterval interval = getOrCreateInterval(stackSlot);
255 interval.addFrom(inst.id());
256 }
257
258 void addRegisterHint(final LIRInstruction op, VirtualStackSlot targetValue, OperandMode mode, EnumSet<OperandFlag> flags, final boolean hintAtDef) {
259 if (flags.contains(OperandFlag.HINT)) {
260 InstructionValueProcedure proc = new InstructionValueProcedure() {
261 @Override
262 public Value doValue(LIRInstruction instruction, Value registerHint, OperandMode vaueMode, EnumSet<OperandFlag> valueFlags) {
263 if (isVirtualStackSlot(registerHint)) {
264 StackInterval from = getOrCreateInterval((VirtualStackSlot) registerHint);
265 StackInterval to = getOrCreateInterval(targetValue);
266
267 // hints always point from def to use
268 if (hintAtDef) {
269 to.setLocationHint(from);
270 } else {
271 from.setLocationHint(to);
272 }
273 if (Debug.isLogEnabled()) {
274 Debug.log("operation %s at opId %d: added hint from interval %d to %d", op, op.id(), from, to);
275 }
276
277 return registerHint;
278 }
279 return null;
280 }
281 };
282 op.forEachRegisterHint(targetValue, mode, proc);
283 }
284 }
285
286 }
287
288 private StackInterval get(VirtualStackSlot stackSlot) {
289 return stackSlotMap[stackSlot.getId()];
290 }
291
292 private void put(VirtualStackSlot stackSlot, StackInterval interval) {
293 stackSlotMap[stackSlot.getId()] = interval;
294 }
295
296 private StackInterval getOrCreateInterval(VirtualStackSlot stackSlot) {
297 StackInterval interval = get(stackSlot);
298 if (interval == null) {
299 interval = new StackInterval(stackSlot, stackSlot.getValueKind());
300 put(stackSlot, interval);
301 }
302 return interval;
303 }
304
305 private StackInterval getIntervalFromStackId(int id) {
306 return stackSlotMap[id];
307 }
308
309 private static int getBlockBegin(List<LIRInstruction> instructions) {
310 return instructions.get(0).id();
311 }
312
313 private static int getBlockEnd(List<LIRInstruction> instructions) {
314 return instructions.get(instructions.size() - 1).id() + 1;
315 }
316
317 }