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