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 java.util.ArrayList;
28 import java.util.Arrays;
29
30 import org.graalvm.compiler.core.common.type.AbstractPointerStamp;
31 import org.graalvm.compiler.core.common.type.ObjectStamp;
32 import org.graalvm.compiler.core.common.type.Stamp;
33 import org.graalvm.compiler.core.common.type.StampFactory;
34 import org.graalvm.compiler.core.common.type.TypeReference;
35 import org.graalvm.compiler.graph.NodeClass;
36 import org.graalvm.compiler.graph.spi.Simplifiable;
37 import org.graalvm.compiler.graph.spi.SimplifierTool;
38 import org.graalvm.compiler.nodeinfo.NodeInfo;
39 import org.graalvm.compiler.nodes.AbstractBeginNode;
40 import org.graalvm.compiler.nodes.ConstantNode;
41 import org.graalvm.compiler.nodes.FixedWithNextNode;
42 import org.graalvm.compiler.nodes.NodeView;
43 import org.graalvm.compiler.nodes.ValueNode;
44 import org.graalvm.compiler.nodes.extended.LoadHubNode;
45 import org.graalvm.compiler.nodes.extended.SwitchNode;
46 import org.graalvm.compiler.nodes.spi.LIRLowerable;
47 import org.graalvm.compiler.nodes.spi.NodeLIRBuilderTool;
48 import org.graalvm.compiler.nodes.util.GraphUtil;
49
50 import jdk.vm.ci.meta.Constant;
51 import jdk.vm.ci.meta.ConstantReflectionProvider;
52 import jdk.vm.ci.meta.ResolvedJavaType;
53
54 /**
55 * The {@code TypeSwitchNode} performs a lookup based on the type of the input value. The type
56 * comparison is an exact type comparison, not an instanceof.
57 */
58 @NodeInfo
59 public final class TypeSwitchNode extends SwitchNode implements LIRLowerable, Simplifiable {
60
61 public static final NodeClass<TypeSwitchNode> TYPE = NodeClass.create(TypeSwitchNode.class);
62 protected final ResolvedJavaType[] keys;
63 protected final Constant[] hubs;
64
65 public TypeSwitchNode(ValueNode value, AbstractBeginNode[] successors, ResolvedJavaType[] keys, double[] keyProbabilities, int[] keySuccessors, ConstantReflectionProvider constantReflection) {
66 super(TYPE, value, successors, keySuccessors, keyProbabilities);
67 assert successors.length <= keys.length + 1;
68 assert keySuccessors.length == keyProbabilities.length;
69 this.keys = keys;
70 assert value.stamp(NodeView.DEFAULT) instanceof AbstractPointerStamp;
71 assert assertKeys();
72
73 hubs = new Constant[keys.length];
74 for (int i = 0; i < hubs.length; i++) {
75 hubs[i] = constantReflection.asObjectHub(keys[i]);
76 }
77 }
78
79 /**
80 * Don't allow duplicate keys.
81 */
82 private boolean assertKeys() {
83 for (int i = 0; i < keys.length; i++) {
84 for (int j = 0; j < keys.length; j++) {
85 if (i == j) {
86 continue;
87 }
88 assert !keys[i].equals(keys[j]);
89 }
90 }
91 return true;
92 }
93
94 @Override
95 public boolean isSorted() {
96 return false;
97 }
98
99 @Override
100 public int keyCount() {
101 return keys.length;
102 }
103
104 @Override
105 public Constant keyAt(int index) {
106 return hubs[index];
107 }
108
109 @Override
110 public boolean equalKeys(SwitchNode switchNode) {
111 if (!(switchNode instanceof TypeSwitchNode)) {
112 return false;
113 }
114 TypeSwitchNode other = (TypeSwitchNode) switchNode;
115 return Arrays.equals(keys, other.keys);
116 }
117
118 public ResolvedJavaType typeAt(int index) {
119 return keys[index];
120 }
121
122 @Override
123 public void generate(NodeLIRBuilderTool gen) {
124 gen.emitSwitch(this);
125 }
126
127 @Override
128 public void simplify(SimplifierTool tool) {
129 NodeView view = NodeView.from(tool);
130 if (value() instanceof ConstantNode) {
131 Constant constant = value().asConstant();
132
133 int survivingEdge = keySuccessorIndex(keyCount());
134 for (int i = 0; i < keyCount(); i++) {
135 Constant typeHub = keyAt(i);
136 Boolean equal = tool.getConstantReflection().constantEquals(constant, typeHub);
137 if (equal == null) {
138 /* We don't know if this key is a match or not, so we cannot simplify. */
139 return;
140 } else if (equal.booleanValue()) {
141 survivingEdge = keySuccessorIndex(i);
142 }
143 }
144 killOtherSuccessors(tool, survivingEdge);
145 }
146 if (value() instanceof LoadHubNode && ((LoadHubNode) value()).getValue().stamp(view) instanceof ObjectStamp) {
147 ObjectStamp objectStamp = (ObjectStamp) ((LoadHubNode) value()).getValue().stamp(view);
148 if (objectStamp.type() != null) {
149 int validKeys = 0;
150 for (int i = 0; i < keyCount(); i++) {
151 if (objectStamp.type().isAssignableFrom(keys[i])) {
152 validKeys++;
153 }
154 }
155 if (validKeys == 0) {
156 tool.addToWorkList(defaultSuccessor());
157 graph().removeSplitPropagate(this, defaultSuccessor());
158 } else if (validKeys != keys.length) {
159 ArrayList<AbstractBeginNode> newSuccessors = new ArrayList<>(blockSuccessorCount());
160 ResolvedJavaType[] newKeys = new ResolvedJavaType[validKeys];
161 int[] newKeySuccessors = new int[validKeys + 1];
162 double[] newKeyProbabilities = new double[validKeys + 1];
163 double totalProbability = 0;
164 int current = 0;
165 for (int i = 0; i < keyCount() + 1; i++) {
166 if (i == keyCount() || objectStamp.type().isAssignableFrom(keys[i])) {
167 int index = newSuccessors.indexOf(keySuccessor(i));
168 if (index == -1) {
169 index = newSuccessors.size();
170 newSuccessors.add(keySuccessor(i));
171 }
172 newKeySuccessors[current] = index;
173 if (i < keyCount()) {
174 newKeys[current] = keys[i];
175 }
176 newKeyProbabilities[current] = keyProbability(i);
177 totalProbability += keyProbability(i);
178 current++;
179 }
180 }
181 if (totalProbability > 0) {
182 for (int i = 0; i < current; i++) {
183 newKeyProbabilities[i] /= totalProbability;
184 }
185 } else {
186 for (int i = 0; i < current; i++) {
187 newKeyProbabilities[i] = 1.0 / current;
188 }
189 }
190
191 ArrayList<AbstractBeginNode> oldSuccessors = new ArrayList<>();
192 for (int i = 0; i < blockSuccessorCount(); i++) {
193 AbstractBeginNode successor = blockSuccessor(i);
194 oldSuccessors.add(successor);
195 setBlockSuccessor(i, null);
196 }
197
198 AbstractBeginNode[] successorsArray = newSuccessors.toArray(new AbstractBeginNode[newSuccessors.size()]);
199 TypeSwitchNode newSwitch = graph().add(new TypeSwitchNode(value(), successorsArray, newKeys, newKeyProbabilities, newKeySuccessors, tool.getConstantReflection()));
200 ((FixedWithNextNode) predecessor()).setNext(newSwitch);
201 GraphUtil.killWithUnusedFloatingInputs(this);
202
203 for (int i = 0; i < oldSuccessors.size(); i++) {
204 AbstractBeginNode successor = oldSuccessors.get(i);
205 if (!newSuccessors.contains(successor)) {
206 GraphUtil.killCFG(successor);
207 }
208 }
209 }
210 }
211 }
212 }
213
214 @Override
215 public Stamp getValueStampForSuccessor(AbstractBeginNode beginNode) {
216 Stamp result = null;
217 if (beginNode != defaultSuccessor()) {
218 for (int i = 0; i < keyCount(); i++) {
219 if (keySuccessor(i) == beginNode) {
220 if (result == null) {
221 result = StampFactory.objectNonNull(TypeReference.createExactTrusted(typeAt(i)));
222 } else {
223 result = result.meet(StampFactory.objectNonNull(TypeReference.createExactTrusted(typeAt(i))));
224 }
225 }
226 }
227 }
228 return result;
229 }
230 }