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.extended;
24
25 import java.util.ArrayList;
26 import java.util.Arrays;
27 import java.util.HashMap;
28 import java.util.List;
29 import java.util.Map;
30
31 import org.graalvm.compiler.core.common.spi.ConstantFieldProvider;
32 import org.graalvm.compiler.core.common.type.IntegerStamp;
33 import org.graalvm.compiler.core.common.type.PrimitiveStamp;
34 import org.graalvm.compiler.graph.NodeClass;
35 import org.graalvm.compiler.graph.spi.Simplifiable;
36 import org.graalvm.compiler.graph.spi.SimplifierTool;
37 import org.graalvm.compiler.nodeinfo.NodeInfo;
38 import org.graalvm.compiler.nodes.AbstractBeginNode;
39 import org.graalvm.compiler.nodes.ConstantNode;
40 import org.graalvm.compiler.nodes.FixedGuardNode;
41 import org.graalvm.compiler.nodes.FixedWithNextNode;
42 import org.graalvm.compiler.nodes.LogicNode;
43 import org.graalvm.compiler.nodes.ValueNode;
44 import org.graalvm.compiler.nodes.calc.IntegerBelowNode;
45 import org.graalvm.compiler.nodes.java.LoadIndexedNode;
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.DeoptimizationAction;
51 import jdk.vm.ci.meta.DeoptimizationReason;
52 import jdk.vm.ci.meta.JavaConstant;
53 import jdk.vm.ci.meta.JavaKind;
54
55 /**
56 * The {@code IntegerSwitchNode} represents a switch on integer keys, with a sorted array of key
57 * values. The actual implementation of the switch will be decided by the backend.
58 */
59 @NodeInfo
60 public final class IntegerSwitchNode extends SwitchNode implements LIRLowerable, Simplifiable {
61 public static final NodeClass<IntegerSwitchNode> TYPE = NodeClass.create(IntegerSwitchNode.class);
62
63 protected final int[] keys;
64
65 public IntegerSwitchNode(ValueNode value, AbstractBeginNode[] successors, int[] keys, double[] keyProbabilities, int[] keySuccessors) {
66 super(TYPE, value, successors, keySuccessors, keyProbabilities);
67 assert keySuccessors.length == keys.length + 1;
68 assert keySuccessors.length == keyProbabilities.length;
69 this.keys = keys;
70 assert value.stamp() instanceof PrimitiveStamp && value.stamp().getStackKind().isNumericInteger();
71 assert assertSorted();
72 }
73
74 private boolean assertSorted() {
75 for (int i = 1; i < keys.length; i++) {
76 assert keys[i - 1] < keys[i];
77 }
78 return true;
79 }
80
81 public IntegerSwitchNode(ValueNode value, int successorCount, int[] keys, double[] keyProbabilities, int[] keySuccessors) {
82 this(value, new AbstractBeginNode[successorCount], keys, keyProbabilities, keySuccessors);
83 }
84
85 @Override
86 public boolean isSorted() {
87 return true;
88 }
89
90 /**
91 * Gets the key at the specified index.
92 *
93 * @param i the index
94 * @return the key at that index
95 */
96 @Override
97 public JavaConstant keyAt(int i) {
98 return JavaConstant.forInt(keys[i]);
99 }
100
101 @Override
102 public int keyCount() {
103 return keys.length;
104 }
105
106 @Override
107 public boolean equalKeys(SwitchNode switchNode) {
108 if (!(switchNode instanceof IntegerSwitchNode)) {
109 return false;
110 }
111 IntegerSwitchNode other = (IntegerSwitchNode) switchNode;
112 return Arrays.equals(keys, other.keys);
113 }
114
115 @Override
116 public void generate(NodeLIRBuilderTool gen) {
117 gen.emitSwitch(this);
118 }
119
120 public AbstractBeginNode successorAtKey(int key) {
121 return blockSuccessor(successorIndexAtKey(key));
122 }
123
124 public int successorIndexAtKey(int key) {
125 for (int i = 0; i < keyCount(); i++) {
126 if (keys[i] == key) {
127 return keySuccessorIndex(i);
128 }
129 }
130 return keySuccessorIndex(keyCount());
131 }
132
133 @Override
134 public void simplify(SimplifierTool tool) {
135 if (blockSuccessorCount() == 1) {
136 tool.addToWorkList(defaultSuccessor());
137 graph().removeSplitPropagate(this, defaultSuccessor());
138 } else if (value() instanceof ConstantNode) {
139 killOtherSuccessors(tool, successorIndexAtKey(value().asJavaConstant().asInt()));
140 } else if (tryOptimizeEnumSwitch(tool)) {
141 return;
142 } else if (tryRemoveUnreachableKeys(tool)) {
143 return;
144 }
145 }
146
147 static final class KeyData {
148 final int key;
149 final double keyProbability;
150 final int keySuccessor;
151
152 KeyData(int key, double keyProbability, int keySuccessor) {
153 this.key = key;
154 this.keyProbability = keyProbability;
155 this.keySuccessor = keySuccessor;
156 }
157 }
158
159 /**
160 * Remove unreachable keys from the switch based on the stamp of the value, i.e., based on the
161 * known range of the switch value.
162 */
163 private boolean tryRemoveUnreachableKeys(SimplifierTool tool) {
164 if (!(value().stamp() instanceof IntegerStamp)) {
165 return false;
166 }
167 IntegerStamp integerStamp = (IntegerStamp) value().stamp();
168 if (integerStamp.isUnrestricted()) {
169 return false;
170 }
171
172 List<KeyData> newKeyDatas = new ArrayList<>(keys.length);
173 ArrayList<AbstractBeginNode> newSuccessors = new ArrayList<>(blockSuccessorCount());
174 for (int i = 0; i < keys.length; i++) {
175 if (integerStamp.contains(keys[i])) {
176 newKeyDatas.add(new KeyData(keys[i], keyProbabilities[i], addNewSuccessor(keySuccessor(i), newSuccessors)));
177 }
178 }
179
180 if (newKeyDatas.size() == keys.length) {
181 /* All keys are reachable. */
182 return false;
183
184 } else if (newKeyDatas.size() == 0) {
185 tool.addToWorkList(defaultSuccessor());
186 graph().removeSplitPropagate(this, defaultSuccessor());
187 return true;
188
189 } else {
190 int newDefaultSuccessor = addNewSuccessor(defaultSuccessor(), newSuccessors);
191 double newDefaultProbability = keyProbabilities[keyProbabilities.length - 1];
192 doReplace(tool, value(), newKeyDatas, newSuccessors, newDefaultSuccessor, newDefaultProbability);
193 return true;
194 }
195 }
196
197 /**
198 * For switch statements on enum values, the Java compiler has to generate complicated code:
199 * because {@link Enum#ordinal()} can change when recompiling an enum, it cannot be used
200 * directly as the value that is switched on. An intermediate int[] array, which is initialized
201 * once at run time based on the actual {@link Enum#ordinal()} values, is used.
202 *
203 * The {@link ConstantFieldProvider} of Graal already detects the int[] arrays and marks them as
204 * {@link ConstantNode#isDefaultStable() stable}, i.e., the array elements are constant. The
205 * code in this method detects array loads from such a stable array and re-wires the switch to
206 * use the keys from the array elements, so that the array load is unnecessary.
207 */
208 private boolean tryOptimizeEnumSwitch(SimplifierTool tool) {
209 if (!(value() instanceof LoadIndexedNode)) {
210 /* Not the switch pattern we are looking for. */
211 return false;
212 }
213 LoadIndexedNode loadIndexed = (LoadIndexedNode) value();
214 if (loadIndexed.usages().count() > 1) {
215 /*
216 * The array load is necessary for other reasons too, so there is no benefit optimizing
217 * the switch.
218 */
219 return false;
220 }
221 assert loadIndexed.usages().first() == this;
222
223 ValueNode newValue = loadIndexed.index();
224 JavaConstant arrayConstant = loadIndexed.array().asJavaConstant();
225 if (arrayConstant == null || ((ConstantNode) loadIndexed.array()).getStableDimension() != 1 || !((ConstantNode) loadIndexed.array()).isDefaultStable()) {
226 /*
227 * The array is a constant that we can optimize. We require the array elements to be
228 * constant too, since we put them as literal constants into the switch keys.
229 */
230 return false;
231 }
232
233 Integer optionalArrayLength = tool.getConstantReflection().readArrayLength(arrayConstant);
234 if (optionalArrayLength == null) {
235 /* Loading a constant value can be denied by the VM. */
236 return false;
237 }
238 int arrayLength = optionalArrayLength;
239
240 Map<Integer, List<Integer>> reverseArrayMapping = new HashMap<>();
241 for (int i = 0; i < arrayLength; i++) {
242 JavaConstant elementConstant = tool.getConstantReflection().readArrayElement(arrayConstant, i);
243 if (elementConstant == null || elementConstant.getJavaKind() != JavaKind.Int) {
244 /* Loading a constant value can be denied by the VM. */
245 return false;
246 }
247 int element = elementConstant.asInt();
248
249 /*
250 * The value loaded from the array is the old switch key, the index into the array is
251 * the new switch key. We build a mapping from the old switch key to new keys.
252 */
253 reverseArrayMapping.computeIfAbsent(element, e -> new ArrayList<>()).add(i);
254 }
255
256 /* Build high-level representation of new switch keys. */
257 List<KeyData> newKeyDatas = new ArrayList<>(arrayLength);
258 ArrayList<AbstractBeginNode> newSuccessors = new ArrayList<>(blockSuccessorCount());
259 for (int i = 0; i < keys.length; i++) {
260 List<Integer> newKeys = reverseArrayMapping.get(keys[i]);
261 if (newKeys == null || newKeys.size() == 0) {
262 /* The switch case is unreachable, we can ignore it. */
263 continue;
264 }
265
266 /*
267 * We do not have detailed profiling information about the individual new keys, so we
268 * have to assume they split the probability of the old key.
269 */
270 double newKeyProbability = keyProbabilities[i] / newKeys.size();
271 int newKeySuccessor = addNewSuccessor(keySuccessor(i), newSuccessors);
272
273 for (int newKey : newKeys) {
274 newKeyDatas.add(new KeyData(newKey, newKeyProbability, newKeySuccessor));
275 }
276 }
277
278 int newDefaultSuccessor = addNewSuccessor(defaultSuccessor(), newSuccessors);
279 double newDefaultProbability = keyProbabilities[keyProbabilities.length - 1];
280
281 /*
282 * We remove the array load, but we still need to preserve exception semantics by keeping
283 * the bounds check. Fortunately the array length is a constant.
284 */
285 LogicNode boundsCheck = graph().unique(new IntegerBelowNode(newValue, ConstantNode.forInt(arrayLength, graph())));
286 graph().addBeforeFixed(this, graph().add(new FixedGuardNode(boundsCheck, DeoptimizationReason.BoundsCheckException, DeoptimizationAction.InvalidateReprofile)));
287
288 /*
289 * Build the low-level representation of the new switch keys and replace ourself with a new
290 * node.
291 */
292 doReplace(tool, newValue, newKeyDatas, newSuccessors, newDefaultSuccessor, newDefaultProbability);
293
294 /* The array load is now unnecessary. */
295 assert loadIndexed.hasNoUsages();
296 GraphUtil.removeFixedWithUnusedInputs(loadIndexed);
297
298 return true;
299 }
300
301 private static int addNewSuccessor(AbstractBeginNode newSuccessor, ArrayList<AbstractBeginNode> newSuccessors) {
302 int index = newSuccessors.indexOf(newSuccessor);
303 if (index == -1) {
304 index = newSuccessors.size();
305 newSuccessors.add(newSuccessor);
306 }
307 return index;
308 }
309
310 private void doReplace(SimplifierTool tool, ValueNode newValue, List<KeyData> newKeyDatas, ArrayList<AbstractBeginNode> newSuccessors, int newDefaultSuccessor, double newDefaultProbability) {
311 /* Sort the new keys (invariant of the IntegerSwitchNode). */
312 newKeyDatas.sort((k1, k2) -> k1.key - k2.key);
313
314 /* Create the final data arrays. */
315 int newKeyCount = newKeyDatas.size();
316 int[] newKeys = new int[newKeyCount];
317 double[] newKeyProbabilities = new double[newKeyCount + 1];
318 int[] newKeySuccessors = new int[newKeyCount + 1];
319
320 for (int i = 0; i < newKeyCount; i++) {
321 KeyData keyData = newKeyDatas.get(i);
322 newKeys[i] = keyData.key;
323 newKeyProbabilities[i] = keyData.keyProbability;
324 newKeySuccessors[i] = keyData.keySuccessor;
325 }
326
327 newKeySuccessors[newKeyCount] = newDefaultSuccessor;
328 newKeyProbabilities[newKeyCount] = newDefaultProbability;
329
330 /* Normalize new probabilities so that they sum up to 1. */
331 double totalProbability = 0;
332 for (double probability : newKeyProbabilities) {
333 totalProbability += probability;
334 }
335 if (totalProbability > 0) {
336 for (int i = 0; i < newKeyProbabilities.length; i++) {
337 newKeyProbabilities[i] /= totalProbability;
338 }
339 } else {
340 for (int i = 0; i < newKeyProbabilities.length; i++) {
341 newKeyProbabilities[i] = 1.0 / newKeyProbabilities.length;
342 }
343 }
344
345 /* Remove dead successors. */
346 for (int i = 0; i < blockSuccessorCount(); i++) {
347 AbstractBeginNode successor = blockSuccessor(i);
348 if (!newSuccessors.contains(successor)) {
349 tool.deleteBranch(successor);
350 }
351 setBlockSuccessor(i, null);
352 }
353
354 /* Create the new switch node and replace ourself with it. */
355 AbstractBeginNode[] successorsArray = newSuccessors.toArray(new AbstractBeginNode[newSuccessors.size()]);
356 SwitchNode newSwitch = graph().add(new IntegerSwitchNode(newValue, successorsArray, newKeys, newKeyProbabilities, newKeySuccessors));
357 ((FixedWithNextNode) predecessor()).setNext(newSwitch);
358 GraphUtil.killWithUnusedFloatingInputs(this);
359 }
360 }