1 /*
2 * Copyright (c) 2017, 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 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
52 public static final class Builder {
53 private GlobalLivenessInfo info;
54 public final int[] emptySet;
55
56 public Builder(LIR lir) {
57 info = new GlobalLivenessInfo(lir);
58 emptySet = new int[0];
59 }
60
61 public GlobalLivenessInfo createLivenessInfo() {
62 GlobalLivenessInfo livenessInfo = info;
63 info = null;
64 return livenessInfo;
65 }
66
67 public void setIncoming(AbstractBlockBase<?> block, int[] varsIn) {
68 assert info.blockToVarIn[block.getId()] == null;
69 assert verifyVars(varsIn);
70 assert storesIncoming(block) || info.blockToVarOut[block.getPredecessors()[0].getId()] == varsIn;
71 info.blockToVarIn[block.getId()] = varsIn;
72 }
73
74 public void setOutgoing(AbstractBlockBase<?> block, int[] varsOut) {
75 assert info.blockToVarOut[block.getId()] == null;
76 assert verifyVars(varsOut);
77 assert storesOutgoing(block) || info.blockToVarIn[block.getSuccessors()[0].getId()] == varsOut;
78 info.blockToVarOut[block.getId()] = varsOut;
79 }
80
81 private static boolean verifyVars(int[] vars) {
82 for (int var : vars) {
83 assert var >= 0;
84 }
85 return true;
86 }
87
88 @SuppressWarnings("unused")
89 public void addVariable(LIRInstruction op, Variable var) {
90 info.variables[var.index] = var;
91 }
92
93 }
94
95 private final Variable[] variables;
96 private final int[][] blockToVarIn;
97 private final int[][] blockToVarOut;
98 private final Value[][] blockToLocIn;
99 private final Value[][] blockToLocOut;
100
101 private GlobalLivenessInfo(LIR lir) {
102 int numVariables = lir.numVariables();
103 variables = new Variable[numVariables];
104 int numBlocks = lir.getControlFlowGraph().getBlocks().length;
105 blockToVarIn = new int[numBlocks][];
106 blockToVarOut = new int[numBlocks][];
107 blockToLocIn = new Value[numBlocks][];
108 blockToLocOut = new Value[numBlocks][];
109 }
110
111 public Variable getVariable(int varNum) {
112 return variables[varNum];
113 }
114
115 public int[] getBlockOut(AbstractBlockBase<?> block) {
116 return blockToVarOut[block.getId()];
117 }
118
119 public int[] getBlockIn(AbstractBlockBase<?> block) {
120 return blockToVarIn[block.getId()];
121 }
122
123 public void setInLocations(AbstractBlockBase<?> block, Value[] values) {
124 blockToLocIn[block.getId()] = values;
125 }
126
127 public void setOutLocations(AbstractBlockBase<?> block, Value[] values) {
128 blockToLocOut[block.getId()] = values;
129 }
130
131 public Value[] getInLocation(AbstractBlockBase<?> block) {
132 return blockToLocIn[block.getId()];
133 }
134
135 public Value[] getOutLocation(AbstractBlockBase<?> block) {
136 return blockToLocOut[block.getId()];
137 }
138
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));
185 }
186 }
187 }
188
189 };
190 for (LIRInstruction op : lir.getLIRforBlock(block)) {
191 op.visitEachInput(proc);
192 op.visitEachAlive(proc);
193 op.visitEachState(proc);
194 op.visitEachOutput(proc);
195 // no need for checking temp
196 }
197 return true;
198 }
199 }