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.nodes.java;
26
27 import static org.graalvm.compiler.nodeinfo.InputType.Anchor;
28 import static org.graalvm.compiler.nodeinfo.NodeCycles.CYCLES_8;
29 import static org.graalvm.compiler.nodeinfo.NodeSize.SIZE_8;
30
31 import java.util.Objects;
32
33 import org.graalvm.compiler.core.common.type.ObjectStamp;
34 import org.graalvm.compiler.core.common.type.Stamp;
35 import org.graalvm.compiler.core.common.type.StampFactory;
36 import org.graalvm.compiler.core.common.type.TypeReference;
37 import org.graalvm.compiler.graph.NodeClass;
38 import org.graalvm.compiler.graph.spi.CanonicalizerTool;
39 import org.graalvm.compiler.nodeinfo.NodeInfo;
40 import org.graalvm.compiler.nodes.LogicConstantNode;
41 import org.graalvm.compiler.nodes.LogicNegationNode;
42 import org.graalvm.compiler.nodes.LogicNode;
43 import org.graalvm.compiler.nodes.NodeView;
44 import org.graalvm.compiler.nodes.UnaryOpLogicNode;
45 import org.graalvm.compiler.nodes.ValueNode;
46 import org.graalvm.compiler.nodes.calc.ConditionalNode;
47 import org.graalvm.compiler.nodes.calc.IsNullNode;
48 import org.graalvm.compiler.nodes.extended.AnchoringNode;
49 import org.graalvm.compiler.nodes.graphbuilderconf.GraphBuilderContext;
50 import org.graalvm.compiler.nodes.spi.Lowerable;
51 import org.graalvm.compiler.nodes.spi.LoweringTool;
52 import org.graalvm.compiler.nodes.spi.Virtualizable;
53 import org.graalvm.compiler.nodes.spi.VirtualizerTool;
54 import org.graalvm.compiler.nodes.type.StampTool;
55
56 import jdk.vm.ci.meta.JavaKind;
57 import jdk.vm.ci.meta.JavaTypeProfile;
58 import jdk.vm.ci.meta.ResolvedJavaMethod;
59 import jdk.vm.ci.meta.ResolvedJavaType;
60 import jdk.vm.ci.meta.TriState;
61
62 /**
63 * The {@code InstanceOfNode} represents an instanceof test.
64 */
65 @NodeInfo(cycles = CYCLES_8, size = SIZE_8)
66 public class InstanceOfNode extends UnaryOpLogicNode implements Lowerable, Virtualizable {
67 public static final NodeClass<InstanceOfNode> TYPE = NodeClass.create(InstanceOfNode.class);
68
69 private final ObjectStamp checkedStamp;
70
71 private JavaTypeProfile profile;
72 @OptionalInput(Anchor) protected AnchoringNode anchor;
73
74 private InstanceOfNode(ObjectStamp checkedStamp, ValueNode object, JavaTypeProfile profile, AnchoringNode anchor) {
75 this(TYPE, checkedStamp, object, profile, anchor);
76 }
77
78 protected InstanceOfNode(NodeClass<? extends InstanceOfNode> c, ObjectStamp checkedStamp, ValueNode object, JavaTypeProfile profile, AnchoringNode anchor) {
79 super(c, object);
80 this.checkedStamp = checkedStamp;
81 this.profile = profile;
82 this.anchor = anchor;
83 assert (profile == null) || (anchor != null) : "profiles must be anchored";
84 assert checkedStamp != null;
85 assert type() != null;
86 }
87
88 public static LogicNode createAllowNull(TypeReference type, ValueNode object, JavaTypeProfile profile, AnchoringNode anchor) {
89 if (StampTool.isPointerNonNull(object)) {
90 return create(type, object, profile, anchor);
91 }
92 return createHelper(StampFactory.object(type), object, profile, anchor);
93 }
94
95 public static LogicNode create(TypeReference type, ValueNode object) {
96 return create(type, object, null, null);
97 }
98
99 public static LogicNode create(TypeReference type, ValueNode object, JavaTypeProfile profile, AnchoringNode anchor) {
100 return createHelper(StampFactory.objectNonNull(type), object, profile, anchor);
101 }
102
103 public static LogicNode createHelper(ObjectStamp checkedStamp, ValueNode object, JavaTypeProfile profile, AnchoringNode anchor) {
104 LogicNode synonym = findSynonym(checkedStamp, object, NodeView.DEFAULT);
105 if (synonym != null) {
106 return synonym;
107 } else {
108 return new InstanceOfNode(checkedStamp, object, profile, anchor);
109 }
110 }
111
112 @Override
113 public void lower(LoweringTool tool) {
114 tool.getLowerer().lower(this, tool);
115 }
116
117 @Override
118 public ValueNode canonical(CanonicalizerTool tool, ValueNode forValue) {
119 NodeView view = NodeView.from(tool);
120 LogicNode synonym = findSynonym(checkedStamp, forValue, view);
121 if (synonym != null) {
122 return synonym;
123 } else {
124 return this;
125 }
126 }
127
128 public static LogicNode findSynonym(ObjectStamp checkedStamp, ValueNode object, NodeView view) {
129 ObjectStamp inputStamp = (ObjectStamp) object.stamp(view);
130 ObjectStamp joinedStamp = (ObjectStamp) checkedStamp.join(inputStamp);
131
132 if (joinedStamp.isEmpty()) {
133 // The check can never succeed, the intersection of the two stamps is empty.
134 return LogicConstantNode.contradiction();
135 } else {
136 ObjectStamp meetStamp = (ObjectStamp) checkedStamp.meet(inputStamp);
137 if (checkedStamp.equals(meetStamp)) {
138 // The check will always succeed, the union of the two stamps is equal to the
139 // checked stamp.
140 return LogicConstantNode.tautology();
141 } else if (checkedStamp.alwaysNull()) {
142 return IsNullNode.create(object);
143 } else if (Objects.equals(checkedStamp.type(), meetStamp.type()) && checkedStamp.isExactType() == meetStamp.isExactType() && checkedStamp.alwaysNull() == meetStamp.alwaysNull()) {
144 assert checkedStamp.nonNull() != inputStamp.nonNull();
145 // The only difference makes the null-ness of the value => simplify the check.
146 if (checkedStamp.nonNull()) {
147 return LogicNegationNode.create(IsNullNode.create(object));
148 } else {
149 return IsNullNode.create(object);
150 }
151 }
152 assert checkedStamp.type() != null;
153 }
154 return null;
155 }
156
157 /**
158 * Gets the type being tested.
159 */
160 public TypeReference type() {
161 return StampTool.typeReferenceOrNull(checkedStamp);
162 }
163
164 public JavaTypeProfile profile() {
165 return profile;
166 }
167
168 @Override
169 public void virtualize(VirtualizerTool tool) {
170 ValueNode alias = tool.getAlias(getValue());
171 TriState fold = tryFold(alias.stamp(NodeView.DEFAULT));
172 if (fold != TriState.UNKNOWN) {
173 tool.replaceWithValue(LogicConstantNode.forBoolean(fold.isTrue(), graph()));
174 }
175 }
176
177 @Override
178 public Stamp getSucceedingStampForValue(boolean negated) {
179 if (negated) {
180 return null;
181 } else {
182 return checkedStamp;
183 }
184 }
185
186 @Override
187 public TriState tryFold(Stamp valueStamp) {
188 if (valueStamp instanceof ObjectStamp) {
189 ObjectStamp inputStamp = (ObjectStamp) valueStamp;
190 ObjectStamp joinedStamp = (ObjectStamp) checkedStamp.join(inputStamp);
191
192 if (joinedStamp.isEmpty()) {
193 // The check can never succeed, the intersection of the two stamps is empty.
194 return TriState.FALSE;
195 } else {
196 ObjectStamp meetStamp = (ObjectStamp) checkedStamp.meet(inputStamp);
197 if (checkedStamp.equals(meetStamp)) {
198 // The check will always succeed, the union of the two stamps is equal to the
199 // checked stamp.
200 return TriState.TRUE;
201 }
202 }
203 }
204 return TriState.UNKNOWN;
205 }
206
207 public boolean allowsNull() {
208 return !checkedStamp.nonNull();
209 }
210
211 public void setProfile(JavaTypeProfile typeProfile, AnchoringNode anchor) {
212 this.profile = typeProfile;
213 updateUsagesInterface(this.anchor, anchor);
214 this.anchor = anchor;
215 assert (profile == null) || (anchor != null) : "profiles must be anchored";
216 }
217
218 public AnchoringNode getAnchor() {
219 return anchor;
220 }
221
222 public ObjectStamp getCheckedStamp() {
223 return checkedStamp;
224 }
225
226 @NodeIntrinsic
227 public static native boolean doInstanceof(@ConstantNodeParameter ResolvedJavaType type, Object object);
228
229 @SuppressWarnings("unused")
230 static boolean intrinsify(GraphBuilderContext b, ResolvedJavaMethod method, ResolvedJavaType type, ValueNode object) {
231 InstanceOfNode node = new InstanceOfNode(StampFactory.objectNonNull(TypeReference.create(b.getAssumptions(), type)), object, null, null);
232 node = b.add(node);
233 b.addPush(JavaKind.Int, ConditionalNode.create(node, NodeView.DEFAULT));
234 return true;
235 }
236
237 @Override
238 public TriState implies(boolean thisNegated, LogicNode other) {
239 if (other instanceof InstanceOfNode) {
240 InstanceOfNode instanceOfNode = (InstanceOfNode) other;
241 if (instanceOfNode.getValue() == getValue()) {
242 if (thisNegated) {
243 // !X => Y
244 if (this.getCheckedStamp().meet(instanceOfNode.getCheckedStamp()).equals(this.getCheckedStamp())) {
245 return TriState.get(false);
246 }
247 } else {
248 // X => Y
249 if (instanceOfNode.getCheckedStamp().meet(this.getCheckedStamp()).equals(instanceOfNode.getCheckedStamp())) {
250 return TriState.get(true);
251 }
252 }
253 }
254 }
255 return super.implies(thisNegated, other);
256 }
257 }