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.Debug;
37 import org.graalvm.compiler.debug.DebugCounter;
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.util.Equivalence;
46 import org.graalvm.util.EconomicSet;
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 EconomicSet<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 = 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]);
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 ArrayList<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 %s to %s", 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 }
|
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]);
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 }
|