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.Debug;
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 = Debug.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 for (int i = blocks.length - 1; i >= 0; i--) {
144 final AbstractBlockBase<?> block = blocks[i];
145 try (Indent indent = Debug.logAndIndent(LOG_LEVEL, "compute local live sets for block %s", block)) {
146
147 final BitSet liveIn = mergeLiveSets(block);
148 setLiveOut(block, (BitSet) liveIn.clone());
149
150 InstructionValueConsumer useConsumer = new InstructionValueConsumer() {
151 @Override
152 public void visitValue(LIRInstruction op, Value operand, OperandMode mode, EnumSet<OperandFlag> flags) {
153 processUse(liveIn, operand);
154 }
155 };
156 InstructionValueConsumer defConsumer = new InstructionValueConsumer() {
157 @Override
158 public void visitValue(LIRInstruction op, Value operand, OperandMode mode, EnumSet<OperandFlag> flags) {
159 processDef(liveIn, op, operand);
160 }
161 };
162 if (Debug.isLogEnabled()) {
163 Debug.log(LOG_LEVEL, "liveOut B%d %s", block.getId(), getLiveOut(block));
164 }
165
166 // iterate all instructions of the block
167 ArrayList<LIRInstruction> instructions = getLIR().getLIRforBlock(block);
168 for (int j = instructions.size() - 1; j >= 0; j--) {
169 final LIRInstruction op = instructions.get(j);
170
171 try (Indent indent2 = Debug.logAndIndent(LOG_LEVEL, "handle op %d: %s", op.id(), op)) {
172 op.visitEachOutput(defConsumer);
173 op.visitEachTemp(defConsumer);
174 op.visitEachState(useConsumer);
175 op.visitEachAlive(useConsumer);
176 op.visitEachInput(useConsumer);
177 }
178 } // end of instruction iteration
179
180 setLiveIn(block, liveIn);
181 if (block.isLoopHeader()) {
182 handleLoopHeader(block.getLoop(), liveIn);
183 }
184
185 if (Debug.isLogEnabled()) {
186 Debug.log(LOG_LEVEL, "liveIn B%d %s", block.getId(), getLiveIn(block));
187 }
188
189 }
190 } // end of block iteration
191 }
192
193 /**
194 * All variables live at the beginning of a loop are live throughout the loop.
195 */
196 private void handleLoopHeader(Loop<?> loop, BitSet live) {
197 for (AbstractBlockBase<?> block : loop.getBlocks()) {
198 getLiveIn(block).or(live);
199 getLiveOut(block).or(live);
200 }
201 }
202
203 private BitSet mergeLiveSets(final AbstractBlockBase<?> block) {
204 assert block != null;
205 final BitSet liveOut = new BitSet(liveSetSize());
206 for (AbstractBlockBase<?> successor : block.getSuccessors()) {
207 BitSet succLiveIn = getLiveIn(successor);
208 if (succLiveIn != null) {
209 liveOut.or(succLiveIn);
210 } else {
211 assert successor.isLoopHeader() : "Successor of " + block + " not yet processed and not loop header: " + successor;
212 }
213 }
214 return liveOut;
215 }
216
217 private void processUse(final BitSet liveGen, Value operand) {
218 if (isVariable(operand)) {
219 int operandNum = operandNumber(operand);
220 liveGen.set(operandNum);
221 if (Debug.isLogEnabled()) {
222 Debug.log(LOG_LEVEL, "liveGen for operand %d(%s)", operandNum, operand);
223 }
224 }
225 }
226
227 private void processDef(final BitSet liveGen, LIRInstruction op, Value operand) {
228 if (isVariable(operand)) {
229 recordVariable(op, asVariable(operand));
230 int operandNum = operandNumber(operand);
231 if (operands[operandNum] == null) {
232 operands[operandNum] = operand;
233 }
234 liveGen.clear(operandNum);
235 if (Debug.isLogEnabled()) {
236 Debug.log(LOG_LEVEL, "liveKill for operand %d(%s)", operandNum, operand);
237 }
238 }
239 }
240
241 private LIR getLIR() {
242 return lir;
243 }
244
245 public void build() {
246 buildIntern();
247 // check that the liveIn set of the first block is empty
248 AbstractBlockBase<?> startBlock = getLIR().getControlFlowGraph().getStartBlock();
249 if (getLiveIn(startBlock).cardinality() != 0) {
250 // bailout if this occurs in product mode.
251 throw new GraalError("liveIn set of first block must be empty: " + getLiveIn(startBlock));
252 }
253 }
254
255 @SuppressWarnings("try")
256 public void finish() {
257 // iterate all blocks in reverse order
258 for (AbstractBlockBase<?> block : (AbstractBlockBase<?>[]) lir.getControlFlowGraph().getBlocks()) {
259 try (Indent indent = Debug.logAndIndent(LOG_LEVEL, "Finish Block %s", block)) {
260 buildIncoming(block);
261 buildOutgoing(block);
262 }
263 }
264 }
265
266 public GlobalLivenessInfo getLivenessInfo() {
267 assert livenessInfoBuilder != null : "No liveness info collected";
268 return livenessInfoBuilder.createLivenessInfo();
269 }
270
271 private void buildIncoming(AbstractBlockBase<?> block) {
272 if (!GlobalLivenessInfo.storesIncoming(block)) {
273 assert block.getPredecessorCount() == 1;
274 assert GlobalLivenessInfo.storesOutgoing(block.getPredecessors()[0]) : "No incoming liveness info: " + block;
275 return;
276 }
277
278 final int[] liveInArray;
279 if (block.getPredecessorCount() == 0) {
280 // start block
281 assert getLiveIn(block).isEmpty() : "liveIn for start block is not empty? " + getLiveIn(block);
282 liveInArray = livenessInfoBuilder.emptySet;
283 } else {
284 /*
285 * Collect live out of predecessors since there might be values not used in this
286 * block which might cause out/in mismatch. Per construction the live sets of all
287 * predecessors are equal.
288 */
289 BitSet predLiveOut = getLiveOut(block.getPredecessors()[0]);
290 liveInArray = predLiveOut.isEmpty() ? livenessInfoBuilder.emptySet : bitSetToIntArray(predLiveOut);
291 }
292
293 livenessInfoBuilder.setIncoming(block, liveInArray);
294 // reuse the same array for outgoing variables in predecessors
295 for (AbstractBlockBase<?> pred : block.getPredecessors()) {
296 livenessInfoBuilder.setOutgoing(pred, liveInArray);
297 }
298 }
299
300 private void buildOutgoing(AbstractBlockBase<?> block) {
301 BitSet liveOut = getLiveOut(block);
302 if (!GlobalLivenessInfo.storesOutgoing(block)) {
303 assert GlobalLivenessInfo.storesOutgoing(block) || block.getSuccessorCount() == 1;
304 assert GlobalLivenessInfo.storesOutgoing(block) || GlobalLivenessInfo.storesIncoming(block.getSuccessors()[0]) : "No outgoing liveness info: " + block;
305 return;
306 }
307 int[] liveOutArray = liveOut.isEmpty() ? livenessInfoBuilder.emptySet : bitSetToIntArray(liveOut);
308
309 livenessInfoBuilder.setOutgoing(block, liveOutArray);
310 // reuse the same array for incoming variables in successors
311 for (AbstractBlockBase<?> succ : block.getSuccessors()) {
312 livenessInfoBuilder.setIncoming(succ, liveOutArray);
313 }
314 }
315
316 private int[] bitSetToIntArray(BitSet live) {
317 int[] vars = new int[live.cardinality()];
318 int cnt = 0;
319 for (int i = live.nextSetBit(0); i >= 0; i = live.nextSetBit(i + 1), cnt++) {
320 vars[cnt] = i;
321 }
322 return vars;
323 }
324
325 private void recordVariable(LIRInstruction op, Variable var) {
326 livenessInfoBuilder.addVariable(op, var);
327 }
328 }
329
330 }