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