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