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