43972
|
1 |
/*
|
58299
|
2 |
* Copyright (c) 2009, 2019, Oracle and/or its affiliates. All rights reserved.
|
43972
|
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 |
*/
|
50858
|
23 |
|
|
24 |
|
43972
|
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;
|
46344
|
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;
|
43972
|
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;
|
48190
|
42 |
import org.graalvm.compiler.nodes.NodeView;
|
43972
|
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;
|
48190
|
70 |
assert value.stamp(NodeView.DEFAULT) instanceof AbstractPointerStamp;
|
43972
|
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) {
|
48190
|
129 |
NodeView view = NodeView.from(tool);
|
43972
|
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 |
}
|
48190
|
146 |
if (value() instanceof LoadHubNode && ((LoadHubNode) value()).getValue().stamp(view) instanceof ObjectStamp) {
|
|
147 |
ObjectStamp objectStamp = (ObjectStamp) ((LoadHubNode) value()).getValue().stamp(view);
|
43972
|
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 |
|
54601
|
191 |
ArrayList<AbstractBeginNode> oldSuccessors = new ArrayList<>();
|
43972
|
192 |
for (int i = 0; i < blockSuccessorCount(); i++) {
|
|
193 |
AbstractBeginNode successor = blockSuccessor(i);
|
54601
|
194 |
oldSuccessors.add(successor);
|
43972
|
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);
|
54601
|
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 |
}
|
43972
|
209 |
}
|
|
210 |
}
|
|
211 |
}
|
|
212 |
}
|
46344
|
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 |
}
|
43972
|
230 |
}
|