1 /*
2 * Copyright (c) 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.ssi;
24
25 import static org.graalvm.compiler.lir.LIRValueUtil.asVariable;
26 import static org.graalvm.compiler.lir.LIRValueUtil.isVariable;
27
28 import java.util.BitSet;
29 import java.util.EnumSet;
30 import java.util.List;
31 import java.util.ListIterator;
32
33 import org.graalvm.compiler.common.PermanentBailoutException;
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.GraalError;
38 import org.graalvm.compiler.debug.Indent;
39 import org.graalvm.compiler.lir.InstructionValueConsumer;
40 import org.graalvm.compiler.lir.LIR;
41 import org.graalvm.compiler.lir.LIRInstruction;
42 import org.graalvm.compiler.lir.LIRInstruction.OperandFlag;
43 import org.graalvm.compiler.lir.LIRInstruction.OperandMode;
44
45 import jdk.vm.ci.meta.Value;
46
47 public final class SSIBuilder extends SSIBuilderBase {
48
49 private static class BlockData {
50
51 /**
52 * Bit map specifying which operands are live upon entry to this block. These are values
53 * used in this block or any of its successors where such value are not defined in this
54 * block. The bit index of an operand is its {@linkplain #operandNumber operand number}.
55 */
56 public BitSet liveIn;
57
58 /**
59 * Bit map specifying which operands are live upon exit from this block. These are values
60 * used in a successor block that are either defined in this block or were live upon entry
61 * to this block. The bit index of an operand is its {@linkplain #operandNumber operand
62 * number}.
63 */
64 public BitSet liveOut;
65
66 /**
67 * Bit map specifying which operands are used (before being defined) in this block. That is,
68 * these are the values that are live upon entry to the block. The bit index of an operand
69 * is its {@linkplain #operandNumber operand number}.
70 */
71 public BitSet liveGen;
72
73 /**
74 * Bit map specifying which operands are defined/overwritten in this block. The bit index of
75 * an operand is its {@linkplain #operandNumber operand number}.
76 */
77 public BitSet liveKill;
78 }
79
80 private final BlockMap<SSIBuilder.BlockData> blockData;
81
82 protected SSIBuilder(LIR lir) {
83 super(lir);
84 this.blockData = new BlockMap<>(lir.getControlFlowGraph());
85 }
86
87 @Override
88 protected void buildIntern() {
89 init();
90 computeLocalLiveSets();
91 computeGlobalLiveSets();
92 }
93
94 /**
95 * Gets the size of the {@link BlockData#liveIn} and {@link BlockData#liveOut} sets for a basic
96 * block.
97 */
98 private int liveSetSize() {
99 return getLIR().numVariables();
100 }
101
102 AbstractBlockBase<?>[] getBlocks() {
103 return getLIR().getControlFlowGraph().getBlocks();
104 }
105
106 static int operandNumber(Value operand) {
107 if (isVariable(operand)) {
108 return asVariable(operand).index;
109 }
110 throw GraalError.shouldNotReachHere("Can only handle Variables: " + operand);
111 }
112
113 private SSIBuilder.BlockData getBlockData(AbstractBlockBase<?> block) {
114 return blockData.get(block);
115 }
116
117 private void initBlockData(AbstractBlockBase<?> block) {
118 blockData.put(block, new SSIBuilder.BlockData());
119 }
120
121 private void init() {
122 for (AbstractBlockBase<?> block : getBlocks()) {
123 initBlockData(block);
124 }
125 }
126
127 /**
128 * Computes local live sets (i.e. {@link BlockData#liveGen} and {@link BlockData#liveKill})
129 * separately for each block.
130 */
131 @SuppressWarnings("try")
132 private void computeLocalLiveSets() {
133 int liveSize = liveSetSize();
134
135 // iterate all blocks
136 AbstractBlockBase<?>[] blocks = getBlocks();
137 for (int i = blocks.length - 1; i >= 0; i--) {
138 final AbstractBlockBase<?> block = blocks[i];
139 try (Indent indent = Debug.logAndIndent(LOG_LEVEL, "compute local live sets for block %s", block)) {
140
141 final BitSet liveGen = new BitSet(liveSize);
142 final BitSet liveKill = new BitSet(liveSize);
143
144 InstructionValueConsumer useConsumer = new InstructionValueConsumer() {
145 @Override
146 public void visitValue(LIRInstruction op, Value operand, OperandMode mode, EnumSet<OperandFlag> flags) {
147 processLocalUse(liveGen, operand);
148 }
149 };
150 InstructionValueConsumer aliveConsumer = new InstructionValueConsumer() {
151 @Override
152 public void visitValue(LIRInstruction op, Value operand, OperandMode mode, EnumSet<OperandFlag> flags) {
153 processLocalUse(liveGen, operand);
154 }
155 };
156 InstructionValueConsumer stateConsumer = new InstructionValueConsumer() {
157 @Override
158 public void visitValue(LIRInstruction op, Value operand, OperandMode mode, EnumSet<OperandFlag> flags) {
159 if (isVariable(operand)) {
160 int operandNum = operandNumber(operand);
161 if (!liveKill.get(operandNum)) {
162 liveGen.set(operandNum);
163 if (Debug.isLogEnabled()) {
164 Debug.log(LOG_LEVEL, "liveGen in state for operand %d(%s)", operandNum, operand);
165 }
166 }
167 }
168 }
169 };
170 InstructionValueConsumer defConsumer = new InstructionValueConsumer() {
171 @Override
172 public void visitValue(LIRInstruction op, Value operand, OperandMode mode, EnumSet<OperandFlag> flags) {
173 processLocalDef(liveGen, liveKill, operand, operands);
174 }
175 };
176 InstructionValueConsumer tempConsumer = new InstructionValueConsumer() {
177 @Override
178 public void visitValue(LIRInstruction op, Value operand, OperandMode mode, EnumSet<OperandFlag> flags) {
179 processLocalDef(liveGen, liveKill, operand, operands);
180 }
181 };
182
183 // iterate all instructions of the block
184 List<LIRInstruction> instructions = getLIR().getLIRforBlock(block);
185 ListIterator<LIRInstruction> instIt = instructions.listIterator(instructions.size());
186 while (instIt.hasPrevious()) {
187 final LIRInstruction op = instIt.previous();
188
189 try (Indent indent2 = Debug.logAndIndent(LOG_LEVEL, "handle op %d: %s", op.id(), op)) {
190 op.visitEachOutput(defConsumer);
191 op.visitEachTemp(tempConsumer);
192 op.visitEachState(stateConsumer);
193 op.visitEachAlive(aliveConsumer);
194 op.visitEachInput(useConsumer);
195 }
196 } // end of instruction iteration
197
198 SSIBuilder.BlockData blockSets = getBlockData(block);
199 blockSets.liveGen = liveGen;
200 blockSets.liveKill = liveKill;
201 blockSets.liveIn = new BitSet(liveSize);
202 blockSets.liveOut = new BitSet(liveSize);
203
204 if (Debug.isLogEnabled()) {
205 Debug.log(LOG_LEVEL, "liveGen B%d %s", block.getId(), blockSets.liveGen);
206 Debug.log(LOG_LEVEL, "liveKill B%d %s", block.getId(), blockSets.liveKill);
207 }
208
209 }
210 } // end of block iteration
211 }
212
213 private static void processLocalUse(final BitSet liveGen, Value operand) {
214 if (isVariable(operand)) {
215 int operandNum = operandNumber(operand);
216 liveGen.set(operandNum);
217 if (Debug.isLogEnabled()) {
218 Debug.log(LOG_LEVEL, "liveGen for operand %d(%s)", operandNum, operand);
219 }
220 }
221 }
222
223 private static void processLocalDef(final BitSet liveGen, final BitSet liveKill, Value operand, Value[] operands) {
224 if (isVariable(operand)) {
225 int operandNum = operandNumber(operand);
226 if (operands[operandNum] == null) {
227 operands[operandNum] = operand;
228 }
229 liveKill.set(operandNum);
230 liveGen.clear(operandNum);
231 if (Debug.isLogEnabled()) {
232 Debug.log(LOG_LEVEL, "liveKill for operand %d(%s)", operandNum, operand);
233 }
234 }
235 }
236
237 /**
238 * Performs a backward dataflow analysis to compute global live sets (i.e.
239 * {@link BlockData#liveIn} and {@link BlockData#liveOut}) for each block.
240 */
241 @SuppressWarnings("try")
242 private void computeGlobalLiveSets() {
243 try (Indent indent = Debug.logAndIndent(LOG_LEVEL, "compute global live sets")) {
244 boolean changeOccurred;
245 boolean changeOccurredInBlock;
246 int iterationCount = 0;
247 BitSet liveOut = new BitSet(liveSetSize()); // scratch set for
248 // calculations
249
250 /*
251 * Perform a backward dataflow analysis to compute liveOut and liveIn for each block.
252 * The loop is executed until a fixpoint is reached (no changes in an iteration).
253 */
254 do {
255 changeOccurred = false;
256
257 try (Indent indent2 = Debug.logAndIndent(LOG_LEVEL, "new iteration %d", iterationCount)) {
258
259 // iterate all blocks in reverse order
260 AbstractBlockBase<?>[] blocks = getBlocks();
261 for (int i = blocks.length - 1; i >= 0; i--) {
262 final AbstractBlockBase<?> block = blocks[i];
263 SSIBuilder.BlockData blockSets = getBlockData(block);
264
265 changeOccurredInBlock = false;
266
267 /*
268 * liveOut(block) is the union of liveIn(sux), for successors sux of block.
269 */
270 int n = block.getSuccessorCount();
271 if (n > 0) {
272 // block has successors
273 liveOut.clear();
274 for (AbstractBlockBase<?> successor : block.getSuccessors()) {
275 liveOut.or(getBlockData(successor).liveIn);
276 }
277
278 if (!blockSets.liveOut.equals(liveOut)) {
279 /*
280 * A change occurred. Swap the old and new live out sets to avoid
281 * copying.
282 */
283 BitSet temp = blockSets.liveOut;
284 blockSets.liveOut = liveOut;
285 liveOut = temp;
286
287 changeOccurred = true;
288 changeOccurredInBlock = true;
289 }
290 }
291
292 if (iterationCount == 0 || changeOccurredInBlock) {
293 /*
294 * liveIn(block) is the union of liveGen(block) with (liveOut(block) &
295 * !liveKill(block)).
296 *
297 * Note: liveIn has to be computed only in first iteration or if liveOut
298 * has changed!
299 */
300 BitSet liveIn = blockSets.liveIn;
301 liveIn.clear();
302 liveIn.or(blockSets.liveOut);
303 liveIn.andNot(blockSets.liveKill);
304 liveIn.or(blockSets.liveGen);
305
306 if (Debug.isLogEnabled()) {
307 Debug.log(LOG_LEVEL, "block %d: livein = %s, liveout = %s", block.getId(), liveIn, blockSets.liveOut);
308 }
309 }
310 }
311 iterationCount++;
312
313 if (changeOccurred && iterationCount > 50) {
314 /*
315 * Very unlikely should never happen: If it happens we cannot guarantee it
316 * won't happen again.
317 */
318 throw new PermanentBailoutException("too many iterations in computeGlobalLiveSets");
319 }
320 }
321 } while (changeOccurred);
322 }
323 }
324
325 @Override
326 BitSet getLiveIn(final AbstractBlockBase<?> block) {
327 return getBlockData(block).liveIn;
328 }
329
330 @Override
331 BitSet getLiveOut(final AbstractBlockBase<?> block) {
332 return getBlockData(block).liveOut;
333 }
334 }