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