1 /*
2 * Copyright (c) 2009, 2015, 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;
24
25 import static org.graalvm.compiler.lir.LIRValueUtil.asVariable;
26 import static org.graalvm.compiler.lir.LIRValueUtil.isJavaConstant;
27 import static org.graalvm.compiler.lir.LIRValueUtil.isStackSlotValue;
28 import static org.graalvm.compiler.lir.LIRValueUtil.isVariable;
29 import static jdk.vm.ci.code.ValueUtil.asRegister;
30 import static jdk.vm.ci.code.ValueUtil.isIllegal;
31 import static jdk.vm.ci.code.ValueUtil.isRegister;
32
33 import java.util.Arrays;
34 import java.util.BitSet;
35 import java.util.EnumSet;
36
37 import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
38 import org.graalvm.compiler.debug.GraalError;
39 import org.graalvm.compiler.debug.TTY;
40 import org.graalvm.compiler.lir.LIRInstruction.OperandFlag;
41 import org.graalvm.compiler.lir.LIRInstruction.OperandMode;
42 import org.graalvm.compiler.lir.framemap.FrameMap;
43 import org.graalvm.compiler.lir.ssa.SSAUtil;
44
45 import jdk.vm.ci.code.Register;
46 import jdk.vm.ci.meta.Value;
47
48 public final class LIRVerifier {
49
50 private final LIR lir;
51 private final FrameMap frameMap;
52
53 private final boolean beforeRegisterAllocation;
54
55 private final BitSet[] blockLiveOut;
56 private final Object[] variableDefinitions;
57
58 private BitSet liveOutFor(AbstractBlockBase<?> block) {
59 return blockLiveOut[block.getId()];
60 }
61
62 private void setLiveOutFor(AbstractBlockBase<?> block, BitSet liveOut) {
63 blockLiveOut[block.getId()] = liveOut;
64 }
65
66 private int maxRegisterNum() {
67 return frameMap.getTarget().arch.getRegisters().size();
68 }
69
70 private boolean isAllocatableRegister(Value value) {
71 return isRegister(value) && frameMap.getRegisterConfig().getAttributesMap()[asRegister(value).number].isAllocatable();
72 }
73
74 public static boolean verify(final LIRInstruction op) {
75
76 op.visitEachInput(LIRVerifier::allowed);
77 op.visitEachAlive(LIRVerifier::allowed);
78 op.visitEachState(LIRVerifier::allowed);
79 op.visitEachTemp(LIRVerifier::allowed);
80 op.visitEachOutput(LIRVerifier::allowed);
81
82 op.verify();
83 return true;
84 }
85
86 public static boolean verify(boolean beforeRegisterAllocation, LIR lir, FrameMap frameMap) {
87 LIRVerifier verifier = new LIRVerifier(beforeRegisterAllocation, lir, frameMap);
88 verifier.verify();
89 return true;
90 }
91
92 private LIRVerifier(boolean beforeRegisterAllocation, LIR lir, FrameMap frameMap) {
93 this.beforeRegisterAllocation = beforeRegisterAllocation;
94 this.lir = lir;
95 this.frameMap = frameMap;
96 this.blockLiveOut = new BitSet[lir.linearScanOrder().length];
97 this.variableDefinitions = new Object[lir.numVariables()];
98 }
99
100 private BitSet curVariablesLive;
101 private Value[] curRegistersLive;
102
103 private AbstractBlockBase<?> curBlock;
104 private Object curInstruction;
105 private BitSet curRegistersDefined;
106
107 private void verify() {
108 ValueConsumer useConsumer = new ValueConsumer() {
109
110 @Override
111 public void visitValue(Value value, OperandMode mode, EnumSet<OperandFlag> flags) {
112 use(value, mode, flags);
113 }
114 };
115 ValueConsumer defConsumer = new ValueConsumer() {
116
117 @Override
118 public void visitValue(Value value, OperandMode mode, EnumSet<OperandFlag> flags) {
119 def(value, mode, flags);
120 }
121 };
122
123 int maxRegisterNum = maxRegisterNum();
124 curRegistersDefined = new BitSet();
125 for (AbstractBlockBase<?> block : lir.linearScanOrder()) {
126 curBlock = block;
127 curVariablesLive = new BitSet();
128 curRegistersLive = new Value[maxRegisterNum];
129
130 if (block.getDominator() != null) {
131 curVariablesLive.or(liveOutFor(block.getDominator()));
132 }
133
134 assert lir.getLIRforBlock(block).get(0) instanceof StandardOp.LabelOp : "block must start with label";
135
136 if (block.getSuccessorCount() > 0) {
137 LIRInstruction last = lir.getLIRforBlock(block).get(lir.getLIRforBlock(block).size() - 1);
138 assert last instanceof StandardOp.JumpOp : "block with successor must end with unconditional jump";
139 }
140 if (block.getPredecessorCount() > 1) {
141 SSAUtil.verifyPhi(lir, block);
142 }
143
144 for (LIRInstruction op : lir.getLIRforBlock(block)) {
145 curInstruction = op;
146
147 op.visitEachInput(useConsumer);
148 if (op.destroysCallerSavedRegisters()) {
149 for (Register register : frameMap.getRegisterConfig().getCallerSaveRegisters()) {
150 curRegistersLive[register.number] = null;
151 }
152 }
153 curRegistersDefined.clear();
154 op.visitEachAlive(useConsumer);
155 op.visitEachState(useConsumer);
156 op.visitEachTemp(defConsumer);
157 op.visitEachOutput(defConsumer);
158
159 curInstruction = null;
160 }
161
162 setLiveOutFor(block, curVariablesLive);
163 }
164 }
165
166 private void use(Value value, OperandMode mode, EnumSet<OperandFlag> flags) {
167 allowed(curInstruction, value, mode, flags);
168
169 if (isVariable(value)) {
170 assert beforeRegisterAllocation;
171
172 int variableIdx = asVariable(value).index;
173 if (!curVariablesLive.get(variableIdx)) {
174 TTY.println("block %s instruction %s", curBlock, curInstruction);
175 TTY.println("live variables: %s", curVariablesLive);
176 if (variableDefinitions[variableIdx] != null) {
177 TTY.println("definition of %s: %s", value, variableDefinitions[variableIdx]);
178 }
179 TTY.println("ERROR: Use of variable %s that is not defined in dominator", value);
180 throw GraalError.shouldNotReachHere();
181 }
182
183 } else if (isAllocatableRegister(value)) {
184 int regNum = asRegister(value).number;
185 if (mode == OperandMode.ALIVE) {
186 curRegistersDefined.set(regNum);
187 }
188
189 if (beforeRegisterAllocation && !curRegistersLive[regNum].equals(value)) {
190 TTY.println("block %s instruction %s", curBlock, curInstruction);
191 TTY.println("live registers: %s", Arrays.toString(curRegistersLive));
192 TTY.println("ERROR: Use of fixed register %s that is not defined in this block", value);
193 throw GraalError.shouldNotReachHere();
194 }
195 }
196 }
197
198 private void def(Value value, OperandMode mode, EnumSet<OperandFlag> flags) {
199 allowed(curInstruction, value, mode, flags);
200
201 if (isVariable(value)) {
202 assert beforeRegisterAllocation;
203
204 int variableIdx = asVariable(value).index;
205 if (variableDefinitions[variableIdx] != null) {
206 TTY.println("block %s instruction %s", curBlock, curInstruction);
207 TTY.println("live variables: %s", curVariablesLive);
208 TTY.println("definition of %s: %s", value, variableDefinitions[variableIdx]);
209 TTY.println("ERROR: Variable %s defined multiple times", value);
210 throw GraalError.shouldNotReachHere();
211 }
212 assert curInstruction != null;
213 variableDefinitions[variableIdx] = curInstruction;
214 assert !curVariablesLive.get(variableIdx);
215 if (mode == OperandMode.DEF) {
216 curVariablesLive.set(variableIdx);
217 }
218
219 } else if (isAllocatableRegister(value)) {
220 int regNum = asRegister(value).number;
221 if (curRegistersDefined.get(regNum)) {
222 TTY.println("block %s instruction %s", curBlock, curInstruction);
223 TTY.println("ERROR: Same register defined twice in the same instruction: %s", value);
224 throw GraalError.shouldNotReachHere();
225 }
226 curRegistersDefined.set(regNum);
227
228 if (beforeRegisterAllocation) {
229 if (mode == OperandMode.DEF) {
230 curRegistersLive[regNum] = value;
231 } else {
232 curRegistersLive[regNum] = null;
233 }
234 }
235 }
236 }
237
238 // @formatter:off
239 private static void allowed(Object op, Value value, OperandMode mode, EnumSet<OperandFlag> flags) {
240 if ((isVariable(value) && flags.contains(OperandFlag.REG)) ||
241 (isRegister(value) && flags.contains(OperandFlag.REG)) ||
242 (isStackSlotValue(value) && flags.contains(OperandFlag.STACK)) ||
243 (isJavaConstant(value) && flags.contains(OperandFlag.CONST) && mode != OperandMode.DEF) ||
244 (isIllegal(value) && flags.contains(OperandFlag.ILLEGAL))) {
245 return;
246 }
247 throw new GraalError("Invalid LIR%n Instruction: %s%n Mode: %s%n Flags: %s%n Unexpected value: %s %s",
248 op, mode, flags, value.getClass().getSimpleName(), value);
249 }
250 // @formatter:on
251 }