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));
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 }
|
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.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]);
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 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));
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(ArrayList<LIRInstruction> instructions) {
310 return instructions.get(0).id();
311 }
312
313 private static int getBlockEnd(ArrayList<LIRInstruction> instructions) {
314 return instructions.get(instructions.size() - 1).id() + 1;
315 }
316
317 }
|