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