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 java.util.Arrays;
26 import java.util.BitSet;
27 import java.util.EnumSet;
28
29 import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
30 import org.graalvm.compiler.debug.Debug;
31 import org.graalvm.compiler.debug.Debug.Scope;
32 import org.graalvm.compiler.lir.LIR;
33 import org.graalvm.compiler.lir.LIRInstruction;
34 import org.graalvm.compiler.lir.LIRInstruction.OperandFlag;
35 import org.graalvm.compiler.lir.LIRInstruction.OperandMode;
36 import org.graalvm.compiler.lir.LIRValueUtil;
37 import org.graalvm.compiler.lir.ValueConsumer;
38 import org.graalvm.compiler.lir.Variable;
39
40 import jdk.vm.ci.meta.Value;
41
42 /**
43 * Stores live in/live out variables and locations for each basic block.
44 *
45 * <em>Live variable information</em> is stored as an integer array containing <em>variable
46 * indices</em>. The information is only stored once per <em>control-flow split</em> or
47 * <em>control-merge</em>. In other words the live sets at the end of the source block and the
48 * beginning of the target block of an edge are the same.
49 */
50 public final class GlobalLivenessInfo {
51
139 public static boolean storesIncoming(AbstractBlockBase<?> block) {
140 assert block.getPredecessorCount() >= 0;
141 return block.getPredecessorCount() != 1;
142 }
143
144 public static boolean storesOutgoing(AbstractBlockBase<?> block) {
145 assert block.getSuccessorCount() >= 0;
146 /*
147 * The second condition handles non-critical empty blocks, introduced, e.g., by two
148 * consecutive loop-exits.
149 */
150 return block.getSuccessorCount() != 1 || block.getSuccessors()[0].getPredecessorCount() == 1;
151 }
152
153 /**
154 * Verifies that the local liveness information is correct, i.e., that all variables used in a
155 * block {@code b} are either defined in {@code b} or in the incoming live set.
156 */
157 @SuppressWarnings("try")
158 public boolean verify(LIR lir) {
159 try (Scope s = Debug.scope("Verify GlobalLivenessInfo", this)) {
160 for (AbstractBlockBase<?> block : lir.getControlFlowGraph().getBlocks()) {
161 assert verifyBlock(block, lir);
162 }
163 } catch (Throwable e) {
164 throw Debug.handle(e);
165 }
166 return true;
167 }
168
169 private boolean verifyBlock(AbstractBlockBase<?> block, LIR lir) {
170 BitSet liveSet = new BitSet(lir.numVariables());
171 int[] liveIn = getBlockIn(block);
172 for (int varNum : liveIn) {
173 liveSet.set(varNum);
174 }
175 ValueConsumer proc = new ValueConsumer() {
176
177 @Override
178 public void visitValue(Value value, OperandMode mode, EnumSet<OperandFlag> flags) {
179 if (LIRValueUtil.isVariable(value)) {
180 Variable var = LIRValueUtil.asVariable(value);
181 if (mode == OperandMode.DEF) {
182 liveSet.set(var.index);
183 } else {
184 assert liveSet.get(var.index) : String.format("Variable %s but not defined in block %s (liveIn: %s)", var, block, Arrays.toString(liveIn));
|
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 java.util.Arrays;
26 import java.util.BitSet;
27 import java.util.EnumSet;
28
29 import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
30 import org.graalvm.compiler.debug.DebugContext;
31 import org.graalvm.compiler.lir.LIR;
32 import org.graalvm.compiler.lir.LIRInstruction;
33 import org.graalvm.compiler.lir.LIRInstruction.OperandFlag;
34 import org.graalvm.compiler.lir.LIRInstruction.OperandMode;
35 import org.graalvm.compiler.lir.LIRValueUtil;
36 import org.graalvm.compiler.lir.ValueConsumer;
37 import org.graalvm.compiler.lir.Variable;
38
39 import jdk.vm.ci.meta.Value;
40
41 /**
42 * Stores live in/live out variables and locations for each basic block.
43 *
44 * <em>Live variable information</em> is stored as an integer array containing <em>variable
45 * indices</em>. The information is only stored once per <em>control-flow split</em> or
46 * <em>control-merge</em>. In other words the live sets at the end of the source block and the
47 * beginning of the target block of an edge are the same.
48 */
49 public final class GlobalLivenessInfo {
50
138 public static boolean storesIncoming(AbstractBlockBase<?> block) {
139 assert block.getPredecessorCount() >= 0;
140 return block.getPredecessorCount() != 1;
141 }
142
143 public static boolean storesOutgoing(AbstractBlockBase<?> block) {
144 assert block.getSuccessorCount() >= 0;
145 /*
146 * The second condition handles non-critical empty blocks, introduced, e.g., by two
147 * consecutive loop-exits.
148 */
149 return block.getSuccessorCount() != 1 || block.getSuccessors()[0].getPredecessorCount() == 1;
150 }
151
152 /**
153 * Verifies that the local liveness information is correct, i.e., that all variables used in a
154 * block {@code b} are either defined in {@code b} or in the incoming live set.
155 */
156 @SuppressWarnings("try")
157 public boolean verify(LIR lir) {
158 DebugContext debug = lir.getDebug();
159 try (DebugContext.Scope s = debug.scope("Verify GlobalLivenessInfo", this)) {
160 for (AbstractBlockBase<?> block : lir.getControlFlowGraph().getBlocks()) {
161 assert verifyBlock(block, lir);
162 }
163 } catch (Throwable e) {
164 throw debug.handle(e);
165 }
166 return true;
167 }
168
169 private boolean verifyBlock(AbstractBlockBase<?> block, LIR lir) {
170 BitSet liveSet = new BitSet(lir.numVariables());
171 int[] liveIn = getBlockIn(block);
172 for (int varNum : liveIn) {
173 liveSet.set(varNum);
174 }
175 ValueConsumer proc = new ValueConsumer() {
176
177 @Override
178 public void visitValue(Value value, OperandMode mode, EnumSet<OperandFlag> flags) {
179 if (LIRValueUtil.isVariable(value)) {
180 Variable var = LIRValueUtil.asVariable(value);
181 if (mode == OperandMode.DEF) {
182 liveSet.set(var.index);
183 } else {
184 assert liveSet.get(var.index) : String.format("Variable %s but not defined in block %s (liveIn: %s)", var, block, Arrays.toString(liveIn));
|