1 /*
2 * Copyright (c) 2015, 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.ssi;
24
25 import static org.graalvm.compiler.lir.LIRValueUtil.isConstantValue;
26 import static org.graalvm.compiler.lir.LIRValueUtil.isStackSlotValue;
27 import static org.graalvm.compiler.lir.LIRValueUtil.isVirtualStackSlot;
28 import static jdk.vm.ci.code.ValueUtil.isRegister;
29
30 import java.util.EnumSet;
31 import java.util.HashMap;
32 import java.util.List;
33
34 import org.graalvm.compiler.core.common.LIRKind;
35 import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
36 import org.graalvm.compiler.debug.Debug;
37 import org.graalvm.compiler.debug.Debug.Scope;
38 import org.graalvm.compiler.lir.InstructionValueConsumer;
39 import org.graalvm.compiler.lir.LIR;
40 import org.graalvm.compiler.lir.LIRInstruction;
41 import org.graalvm.compiler.lir.LIRInstruction.OperandFlag;
42 import org.graalvm.compiler.lir.LIRInstruction.OperandMode;
43 import org.graalvm.compiler.lir.StandardOp.BlockEndOp;
44 import org.graalvm.compiler.lir.StandardOp.LabelOp;
45
46 import jdk.vm.ci.meta.Value;
47 import jdk.vm.ci.meta.ValueKind;
48
49 public final class SSIVerifier {
50
51 public static boolean verify(LIR lir) {
52 return new SSIVerifier(lir).verify();
53 }
54
55 private final LIR lir;
56
57 private SSIVerifier(LIR lir) {
58 this.lir = lir;
59 }
60
61 @SuppressWarnings("try")
62 private boolean verify() {
63 try (Scope s = Debug.scope("SSIVerifier", lir)) {
64 for (AbstractBlockBase<?> block : lir.getControlFlowGraph().getBlocks()) {
65 doBlock(block);
66 }
67 } catch (Throwable e) {
68 throw Debug.handle(e);
69 }
70 return true;
71 }
72
73 private void doBlock(AbstractBlockBase<?> block) {
74 for (AbstractBlockBase<?> succ : block.getSuccessors()) {
75 verifyEdge(block, succ);
76 }
77 verifyInstructions(block);
78 }
79
80 private void verifyEdge(AbstractBlockBase<?> from, AbstractBlockBase<?> to) {
81 BlockEndOp out = SSIUtil.outgoing(lir, from);
82 LabelOp in = SSIUtil.incoming(lir, to);
83 int outgoingSize = out.getOutgoingSize();
84 int incomingSize = in.getIncomingSize();
85 assert outgoingSize == incomingSize : String.format("Outgoing size %d and incoming size %d do not match", outgoingSize, incomingSize);
86
87 for (int i = 0; i < outgoingSize; i++) {
88 Value incomingValue = in.getIncomingValue(i);
89 Value outgoingValue = out.getOutgoingValue(i);
90 ValueKind<?> inLIRKind = incomingValue.getValueKind();
91 ValueKind<?> outLIRKind = outgoingValue.getValueKind();
92 assert LIRKind.verifyMoveKinds(inLIRKind, outLIRKind) || incomingValue.equals(Value.ILLEGAL) : String.format("Outgoing LIRKind %s (%s) an and incoming LIRKind %s (%s) do not match",
93 outgoingValue, outLIRKind, incomingValue, inLIRKind);
94 }
95 }
96
97 private void verifyInstructions(AbstractBlockBase<?> block) {
98 List<LIRInstruction> instructions = lir.getLIRforBlock(block);
99 HashMap<Value, LIRInstruction> defined = new HashMap<>();
100
101 InstructionValueConsumer useConsumer = new InstructionValueConsumer() {
102 @Override
103 public void visitValue(LIRInstruction instruction, Value value, OperandMode mode, EnumSet<OperandFlag> flags) {
104 if (checkUsage(value)) {
105 assert defined.containsKey(value) || flags.contains(OperandFlag.UNINITIALIZED) : String.format("Value %s is used by instruction %s in block %s but not defined.", value,
106 instruction, block);
107 }
108 }
109 };
110 InstructionValueConsumer stateConsumer = new InstructionValueConsumer() {
111 @Override
112 public void visitValue(LIRInstruction instruction, Value value, OperandMode mode, EnumSet<OperandFlag> flags) {
113 if (checkUsage(value)) {
114 /*
115 * TODO (je): There are undefined stack values used for locks. Ignore them for
116 * the time being.
117 */
118 assert defined.containsKey(value) || isVirtualStackSlot(value) : String.format("Value %s is used in state of instruction %s in block %s but not defined.", value, instruction,
119 block);
120 }
121 }
122 };
123
124 InstructionValueConsumer defConsumer = new InstructionValueConsumer() {
125 @Override
126 public void visitValue(LIRInstruction instruction, Value value, OperandMode mode, EnumSet<OperandFlag> flags) {
127 if (trackDefinition(value)) {
128 assert !defined.containsKey(value) : String.format("Value %s is redefined by instruction %s in block %s but already defined by %s.", value, instruction, block, defined.get(value));
129 defined.put(value, instruction);
130 }
131 }
132 };
133
134 for (LIRInstruction op : instructions) {
135 op.visitEachAlive(useConsumer);
136 op.visitEachInput(useConsumer);
137 op.visitEachState(stateConsumer);
138
139 op.visitEachTemp(defConsumer);
140 op.visitEachOutput(defConsumer);
141 }
142 }
143
144 private static boolean trackDefinition(Value value) {
145 if (isRegister(value)) {
146 // registers can be redefined
147 return false;
148 }
149 if (isStackSlotValue(value) && !isVirtualStackSlot(value)) {
150 // non-virtual stack slots can be redefined
151 return false;
152 }
153 if (value.equals(Value.ILLEGAL)) {
154 // Don't care about illegal values
155 return false;
156 }
157 return true;
158 }
159
160 private static boolean checkUsage(Value value) {
161 if (isConstantValue(value)) {
162 // Constants do not need to be defined
163 return false;
164 }
165 if (isRegister(value)) {
166 // Assume fixed registers are correct
167 return false;
168 }
169 if (isStackSlotValue(value)) {
170 // stack slots are assumed to be correct
171 return false;
172 }
173 if (value.equals(Value.ILLEGAL)) {
174 // Don't care about illegal values
175 return false;
176 }
177 return true;
178 }
179 }