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.ArrayList;
29 import java.util.Arrays;
30 import java.util.BitSet;
31 import java.util.EnumSet;
32
33 import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
34 import org.graalvm.compiler.core.common.cfg.Loop;
35 import org.graalvm.compiler.debug.Debug;
36 import org.graalvm.compiler.debug.GraalError;
37 import org.graalvm.compiler.debug.Indent;
38 import org.graalvm.compiler.lir.InstructionValueConsumer;
39 import org.graalvm.compiler.lir.LIR;
40 import org.graalvm.compiler.lir.LIRInstruction;
41 import org.graalvm.compiler.lir.LIRInstruction.OperandFlag;
42 import org.graalvm.compiler.lir.LIRInstruction.OperandMode;
43
44 import jdk.vm.ci.meta.Value;
45
46 public final class FastSSIBuilder extends SSIBuilderBase {
47
48 /**
49 * Bit map specifying which operands are live upon entry to this block. These are values used in
50 * this block or any of its successors where such value are not defined in this block. The bit
51 * index of an operand is its {@linkplain #operandNumber operand number}.
52 */
53 private final BitSet[] liveIns;
54
55 /**
56 * Bit map specifying which operands are live upon exit from this block. These are values used
57 * in a successor block that are either defined in this block or were live upon entry to this
58 * block. The bit index of an operand is its {@linkplain #operandNumber operand number}.
59 */
60 private final BitSet[] liveOuts;
61
62 private final AbstractBlockBase<?>[] blocks;
63
64 protected FastSSIBuilder(LIR lir) {
65 super(lir);
66 int numBlocks = lir.getControlFlowGraph().getBlocks().length;
67 this.liveIns = new BitSet[numBlocks];
68 this.liveOuts = new BitSet[numBlocks];
69 this.blocks = lir.getControlFlowGraph().getBlocks();
70 }
71
72 @Override
73 BitSet getLiveIn(final AbstractBlockBase<?> block) {
74 return liveIns[block.getId()];
75 }
76
77 @Override
78 BitSet getLiveOut(final AbstractBlockBase<?> block) {
79 return liveOuts[block.getId()];
80 }
81
82 private void setLiveIn(final AbstractBlockBase<?> block, final BitSet liveIn) {
83 liveIns[block.getId()] = liveIn;
84 }
85
86 private void setLiveOut(final AbstractBlockBase<?> block, final BitSet liveOut) {
87 liveOuts[block.getId()] = liveOut;
88 }
89
90 @Override
91 protected void buildIntern() {
92 Debug.log(1, "SSIConstruction block order: %s", Arrays.asList(blocks));
93 computeLiveness();
94 }
95
96 /**
97 * Gets the size of the {@link #liveIns} and {@link #liveOuts} sets for a basic block.
98 */
99 private int liveSetSize() {
100 return lir.numVariables();
101 }
102
103 private static int operandNumber(Value operand) {
104 if (isVariable(operand)) {
105 return asVariable(operand).index;
106 }
107 throw GraalError.shouldNotReachHere("Can only handle Variables: " + operand);
108 }
109
110 /**
111 * Computes live sets for each block.
112 */
113 @SuppressWarnings("try")
114 private void computeLiveness() {
115 // iterate all blocks
116 for (int i = blocks.length - 1; i >= 0; i--) {
117 final AbstractBlockBase<?> block = blocks[i];
118 try (Indent indent = Debug.logAndIndent(LOG_LEVEL, "compute local live sets for block %s", block)) {
119
120 final BitSet liveIn = mergeLiveSets(block);
121 setLiveOut(block, (BitSet) liveIn.clone());
122
123 InstructionValueConsumer useConsumer = new InstructionValueConsumer() {
124 @Override
125 public void visitValue(LIRInstruction op, Value operand, OperandMode mode, EnumSet<OperandFlag> flags) {
126 processUse(liveIn, operand);
127 }
128 };
129 InstructionValueConsumer defConsumer = new InstructionValueConsumer() {
130 @Override
131 public void visitValue(LIRInstruction op, Value operand, OperandMode mode, EnumSet<OperandFlag> flags) {
132 processDef(liveIn, operand, operands);
133 }
134 };
135 if (Debug.isLogEnabled()) {
136 Debug.log(LOG_LEVEL, "liveOut B%d %s", block.getId(), getLiveOut(block));
137 }
138
139 // iterate all instructions of the block
140 ArrayList<LIRInstruction> instructions = getLIR().getLIRforBlock(block);
141 for (int j = instructions.size() - 1; j >= 0; j--) {
142 final LIRInstruction op = instructions.get(j);
143
144 try (Indent indent2 = Debug.logAndIndent(LOG_LEVEL, "handle op %d: %s", op.id(), op)) {
145 op.visitEachOutput(defConsumer);
146 op.visitEachTemp(defConsumer);
147 op.visitEachState(useConsumer);
148 op.visitEachAlive(useConsumer);
149 op.visitEachInput(useConsumer);
150 }
151 } // end of instruction iteration
152
153 setLiveIn(block, liveIn);
154 if (block.isLoopHeader()) {
155 handleLoopHeader(block.getLoop(), liveIn);
156 }
157
158 if (Debug.isLogEnabled()) {
159 Debug.log(LOG_LEVEL, "liveIn B%d %s", block.getId(), getLiveIn(block));
160 }
161
162 }
163 } // end of block iteration
164 }
165
166 /**
167 * All variables live at the beginning of a loop are live throughout the loop.
168 */
169 private void handleLoopHeader(Loop<?> loop, BitSet live) {
170 for (AbstractBlockBase<?> block : loop.getBlocks()) {
171 getLiveIn(block).or(live);
172 getLiveOut(block).or(live);
173 }
174 }
175
176 private BitSet mergeLiveSets(final AbstractBlockBase<?> block) {
177 assert block != null;
178 final BitSet liveOut = new BitSet(liveSetSize());
179 for (AbstractBlockBase<?> successor : block.getSuccessors()) {
180 BitSet succLiveIn = getLiveIn(successor);
181 if (succLiveIn != null) {
182 liveOut.or(succLiveIn);
183 } else {
184 assert successor.isLoopHeader() : "Successor of " + block + " not yet processed and not loop header: " + successor;
185 }
186 }
187 return liveOut;
188 }
189
190 private static void processUse(final BitSet liveGen, Value operand) {
191 if (isVariable(operand)) {
192 int operandNum = operandNumber(operand);
193 liveGen.set(operandNum);
194 if (Debug.isLogEnabled()) {
195 Debug.log(LOG_LEVEL, "liveGen for operand %d(%s)", operandNum, operand);
196 }
197 }
198 }
199
200 private static void processDef(final BitSet liveGen, Value operand, Value[] operands) {
201 if (isVariable(operand)) {
202 int operandNum = operandNumber(operand);
203 if (operands[operandNum] == null) {
204 operands[operandNum] = operand;
205 }
206 liveGen.clear(operandNum);
207 if (Debug.isLogEnabled()) {
208 Debug.log(LOG_LEVEL, "liveKill for operand %d(%s)", operandNum, operand);
209 }
210 }
211 }
212 }