1 /*
2 * Copyright (c) 2016, 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.alloc.trace;
24
25 import static org.graalvm.compiler.lir.LIRValueUtil.asVariable;
26 import static org.graalvm.compiler.lir.LIRValueUtil.isVariable;
27
28 import java.util.ArrayList;
29 import java.util.BitSet;
30 import java.util.EnumSet;
31
32 import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
33 import org.graalvm.compiler.core.common.cfg.Loop;
34 import org.graalvm.compiler.debug.DebugContext;
35 import org.graalvm.compiler.debug.GraalError;
36 import org.graalvm.compiler.debug.Indent;
37 import org.graalvm.compiler.lir.InstructionValueConsumer;
38 import org.graalvm.compiler.lir.LIR;
39 import org.graalvm.compiler.lir.LIRInstruction;
40 import org.graalvm.compiler.lir.LIRInstruction.OperandFlag;
41 import org.graalvm.compiler.lir.LIRInstruction.OperandMode;
42 import org.graalvm.compiler.lir.Variable;
43 import org.graalvm.compiler.lir.gen.LIRGenerationResult;
44 import org.graalvm.compiler.lir.phases.AllocationPhase;
45 import org.graalvm.compiler.lir.ssa.SSAUtil;
46
47 import jdk.vm.ci.code.TargetDescription;
48 import jdk.vm.ci.meta.Value;
49
50 /**
51 * Constructs {@link GlobalLivenessInfo global liveness information}.
52 */
53 public final class GlobalLivenessAnalysisPhase extends AllocationPhase {
54
55 @Override
56 protected void run(TargetDescription target, LIRGenerationResult lirGenRes, AllocationContext context) {
57 assert SSAUtil.verifySSAForm(lirGenRes.getLIR());
58 Analyser ssiBuilder = new Analyser(lirGenRes.getLIR());
59 ssiBuilder.build();
60 ssiBuilder.finish();
61 GlobalLivenessInfo livenessInfo = ssiBuilder.getLivenessInfo();
62 assert livenessInfo.verify(lirGenRes.getLIR());
63 context.contextAdd(livenessInfo);
64 }
65
66 private final class Analyser {
67
68 private static final int LOG_LEVEL = DebugContext.INFO_LEVEL;
69
70 /**
71 * Bit map specifying which operands are live upon entry to this block. These are values
72 * used in this block or any of its successors where such value are not defined in this
73 * block. The bit index of an operand is its {@linkplain #operandNumber operand number}.
74 */
75 private final BitSet[] liveIns;
76
77 /**
78 * Bit map specifying which operands are live upon exit from this block. These are values
79 * used in a successor block that are either defined in this block or were live upon entry
80 * to this block. The bit index of an operand is its {@linkplain #operandNumber operand
81 * number}.
82 */
83 private final BitSet[] liveOuts;
84
85 private final AbstractBlockBase<?>[] blocks;
86
87 private final Value[] operands;
88
89 private final LIR lir;
90
91 private final GlobalLivenessInfo.Builder livenessInfoBuilder;
92
93 Analyser(LIR lir) {
94 int numBlocks = lir.getControlFlowGraph().getBlocks().length;
95 this.liveIns = new BitSet[numBlocks];
96 this.liveOuts = new BitSet[numBlocks];
97 this.blocks = lir.getControlFlowGraph().getBlocks();
98 this.lir = lir;
99 this.operands = new Value[lir.numVariables()];
100 this.livenessInfoBuilder = new GlobalLivenessInfo.Builder(lir);
101 }
102
103 private BitSet getLiveIn(final AbstractBlockBase<?> block) {
104 return liveIns[block.getId()];
105 }
106
107 private BitSet getLiveOut(final AbstractBlockBase<?> block) {
108 return liveOuts[block.getId()];
109 }
110
111 private void setLiveIn(final AbstractBlockBase<?> block, final BitSet liveIn) {
112 liveIns[block.getId()] = liveIn;
113 }
114
115 private void setLiveOut(final AbstractBlockBase<?> block, final BitSet liveOut) {
116 liveOuts[block.getId()] = liveOut;
117 }
118
119 private void buildIntern() {
120 computeLiveness();
121 }
122
123 /**
124 * Gets the size of the {@link #liveIns} and {@link #liveOuts} sets for a basic block.
125 */
126 private int liveSetSize() {
127 return lir.numVariables();
128 }
129
130 private int operandNumber(Value operand) {
131 if (isVariable(operand)) {
132 return asVariable(operand).index;
133 }
134 throw GraalError.shouldNotReachHere("Can only handle Variables: " + operand);
135 }
136
137 /**
138 * Computes live sets for each block.
139 */
140 @SuppressWarnings("try")
141 private void computeLiveness() {
142 // iterate all blocks
143 DebugContext debug = lir.getDebug();
144 for (int i = blocks.length - 1; i >= 0; i--) {
145 final AbstractBlockBase<?> block = blocks[i];
146 try (Indent indent = debug.logAndIndent(LOG_LEVEL, "compute local live sets for block %s", block)) {
147
148 final BitSet liveIn = mergeLiveSets(block);
149 setLiveOut(block, (BitSet) liveIn.clone());
150
151 InstructionValueConsumer useConsumer = new InstructionValueConsumer() {
152 @Override
153 public void visitValue(LIRInstruction op, Value operand, OperandMode mode, EnumSet<OperandFlag> flags) {
154 processUse(liveIn, operand);
155 }
156 };
157 InstructionValueConsumer defConsumer = new InstructionValueConsumer() {
158 @Override
159 public void visitValue(LIRInstruction op, Value operand, OperandMode mode, EnumSet<OperandFlag> flags) {
160 processDef(liveIn, op, operand);
161 }
162 };
163 if (debug.isLogEnabled()) {
164 debug.log(LOG_LEVEL, "liveOut B%d %s", block.getId(), getLiveOut(block));
165 }
166
167 // iterate all instructions of the block
168 ArrayList<LIRInstruction> instructions = getLIR().getLIRforBlock(block);
169 for (int j = instructions.size() - 1; j >= 0; j--) {
170 final LIRInstruction op = instructions.get(j);
171
172 try (Indent indent2 = debug.logAndIndent(LOG_LEVEL, "handle op %d: %s", op.id(), op)) {
173 op.visitEachOutput(defConsumer);
174 op.visitEachTemp(defConsumer);
175 op.visitEachState(useConsumer);
176 op.visitEachAlive(useConsumer);
177 op.visitEachInput(useConsumer);
178 }
179 } // end of instruction iteration
180
181 setLiveIn(block, liveIn);
182 if (block.isLoopHeader()) {
183 handleLoopHeader(block.getLoop(), liveIn);
184 }
185
186 if (debug.isLogEnabled()) {
187 debug.log(LOG_LEVEL, "liveIn B%d %s", block.getId(), getLiveIn(block));
188 }
189
190 }
191 } // end of block iteration
192 }
193
194 /**
195 * All variables live at the beginning of a loop are live throughout the loop.
196 */
197 private void handleLoopHeader(Loop<?> loop, BitSet live) {
198 for (AbstractBlockBase<?> block : loop.getBlocks()) {
199 getLiveIn(block).or(live);
200 getLiveOut(block).or(live);
201 }
202 }
203
204 private BitSet mergeLiveSets(final AbstractBlockBase<?> block) {
205 assert block != null;
206 final BitSet liveOut = new BitSet(liveSetSize());
207 for (AbstractBlockBase<?> successor : block.getSuccessors()) {
208 BitSet succLiveIn = getLiveIn(successor);
209 if (succLiveIn != null) {
210 liveOut.or(succLiveIn);
211 } else {
212 assert successor.isLoopHeader() : "Successor of " + block + " not yet processed and not loop header: " + successor;
213 }
214 }
215 return liveOut;
216 }
217
218 private void processUse(final BitSet liveGen, Value operand) {
219 if (isVariable(operand)) {
220 int operandNum = operandNumber(operand);
221 liveGen.set(operandNum);
222 DebugContext debug = lir.getDebug();
223 if (debug.isLogEnabled()) {
224 debug.log(LOG_LEVEL, "liveGen for operand %d(%s)", operandNum, operand);
225 }
226 }
227 }
228
229 private void processDef(final BitSet liveGen, LIRInstruction op, Value operand) {
230 if (isVariable(operand)) {
231 recordVariable(op, asVariable(operand));
232 int operandNum = operandNumber(operand);
233 if (operands[operandNum] == null) {
234 operands[operandNum] = operand;
235 }
236 liveGen.clear(operandNum);
237 DebugContext debug = lir.getDebug();
238 if (debug.isLogEnabled()) {
239 debug.log(LOG_LEVEL, "liveKill for operand %d(%s)", operandNum, operand);
240 }
241 }
242 }
243
244 private LIR getLIR() {
245 return lir;
246 }
247
248 public void build() {
249 buildIntern();
250 // check that the liveIn set of the first block is empty
251 AbstractBlockBase<?> startBlock = getLIR().getControlFlowGraph().getStartBlock();
252 if (getLiveIn(startBlock).cardinality() != 0) {
253 // bailout if this occurs in product mode.
254 throw new GraalError("liveIn set of first block must be empty: " + getLiveIn(startBlock));
255 }
256 }
257
258 @SuppressWarnings("try")
259 public void finish() {
260 // iterate all blocks in reverse order
261 for (AbstractBlockBase<?> block : (AbstractBlockBase<?>[]) lir.getControlFlowGraph().getBlocks()) {
262 try (Indent indent = lir.getDebug().logAndIndent(LOG_LEVEL, "Finish Block %s", block)) {
263 buildIncoming(block);
264 buildOutgoing(block);
265 }
266 }
267 }
268
269 public GlobalLivenessInfo getLivenessInfo() {
270 assert livenessInfoBuilder != null : "No liveness info collected";
271 return livenessInfoBuilder.createLivenessInfo();
272 }
273
274 private void buildIncoming(AbstractBlockBase<?> block) {
275 if (!GlobalLivenessInfo.storesIncoming(block)) {
276 assert block.getPredecessorCount() == 1;
277 assert GlobalLivenessInfo.storesOutgoing(block.getPredecessors()[0]) : "No incoming liveness info: " + block;
278 return;
279 }
280
281 final int[] liveInArray;
282 if (block.getPredecessorCount() == 0) {
283 // start block
284 assert getLiveIn(block).isEmpty() : "liveIn for start block is not empty? " + getLiveIn(block);
285 liveInArray = livenessInfoBuilder.emptySet;
286 } else {
287 /*
288 * Collect live out of predecessors since there might be values not used in this
289 * block which might cause out/in mismatch. Per construction the live sets of all
290 * predecessors are equal.
291 */
292 BitSet predLiveOut = getLiveOut(block.getPredecessors()[0]);
293 liveInArray = predLiveOut.isEmpty() ? livenessInfoBuilder.emptySet : bitSetToIntArray(predLiveOut);
294 }
295
296 livenessInfoBuilder.setIncoming(block, liveInArray);
297 // reuse the same array for outgoing variables in predecessors
298 for (AbstractBlockBase<?> pred : block.getPredecessors()) {
299 livenessInfoBuilder.setOutgoing(pred, liveInArray);
300 }
301 }
302
303 private void buildOutgoing(AbstractBlockBase<?> block) {
304 BitSet liveOut = getLiveOut(block);
305 if (!GlobalLivenessInfo.storesOutgoing(block)) {
306 assert GlobalLivenessInfo.storesOutgoing(block) || block.getSuccessorCount() == 1;
307 assert GlobalLivenessInfo.storesOutgoing(block) || GlobalLivenessInfo.storesIncoming(block.getSuccessors()[0]) : "No outgoing liveness info: " + block;
308 return;
309 }
310 int[] liveOutArray = liveOut.isEmpty() ? livenessInfoBuilder.emptySet : bitSetToIntArray(liveOut);
311
312 livenessInfoBuilder.setOutgoing(block, liveOutArray);
313 // reuse the same array for incoming variables in successors
314 for (AbstractBlockBase<?> succ : block.getSuccessors()) {
315 livenessInfoBuilder.setIncoming(succ, liveOutArray);
316 }
317 }
318
319 private int[] bitSetToIntArray(BitSet live) {
320 int[] vars = new int[live.cardinality()];
321 int cnt = 0;
322 for (int i = live.nextSetBit(0); i >= 0; i = live.nextSetBit(i + 1), cnt++) {
323 vars[cnt] = i;
324 }
325 return vars;
326 }
327
328 private void recordVariable(LIRInstruction op, Variable var) {
329 livenessInfoBuilder.addVariable(op, var);
330 }
331 }
332
333 }