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.extended;
26
27 import static org.graalvm.compiler.nodeinfo.NodeCycles.CYCLES_2;
28 import static org.graalvm.compiler.nodeinfo.NodeCycles.CYCLES_64;
29 import static org.graalvm.compiler.nodeinfo.NodeCycles.CYCLES_8;
30 import static org.graalvm.compiler.nodeinfo.NodeCycles.CYCLES_UNKNOWN;
31 import static org.graalvm.compiler.nodeinfo.NodeSize.SIZE_2;
32 import static org.graalvm.compiler.nodeinfo.NodeSize.SIZE_64;
33 import static org.graalvm.compiler.nodeinfo.NodeSize.SIZE_8;
34 import static org.graalvm.compiler.nodeinfo.NodeSize.SIZE_UNKNOWN;
35
36 import java.util.Arrays;
37
38 import org.graalvm.compiler.core.common.type.AbstractPointerStamp;
39 import org.graalvm.compiler.core.common.type.Stamp;
40 import org.graalvm.compiler.core.common.type.StampFactory;
41 import org.graalvm.compiler.debug.GraalError;
42 import org.graalvm.compiler.graph.Node;
43 import org.graalvm.compiler.graph.NodeClass;
44 import org.graalvm.compiler.graph.NodeSuccessorList;
45 import org.graalvm.compiler.graph.spi.SimplifierTool;
46 import org.graalvm.compiler.nodeinfo.NodeCycles;
47 import org.graalvm.compiler.nodeinfo.NodeInfo;
48 import org.graalvm.compiler.nodeinfo.NodeSize;
49 import org.graalvm.compiler.nodes.AbstractBeginNode;
50 import org.graalvm.compiler.nodes.ControlSplitNode;
51 import org.graalvm.compiler.nodes.NodeView;
52 import org.graalvm.compiler.nodes.ValueNode;
53
54 import jdk.vm.ci.meta.Constant;
55
56 /**
57 * The {@code SwitchNode} class is the base of both lookup and table switches.
58 */
59 // @formatter:off
60 @NodeInfo(cycles = CYCLES_UNKNOWN,
61 cyclesRationale = "We cannot estimate the runtime cost of a switch statement without knowing the number" +
62 "of case statements and the involved keys.",
63 size = SIZE_UNKNOWN,
64 sizeRationale = "We cannot estimate the code size of a switch statement without knowing the number" +
65 "of case statements.")
66 // @formatter:on
67 public abstract class SwitchNode extends ControlSplitNode {
68
69 public static final NodeClass<SwitchNode> TYPE = NodeClass.create(SwitchNode.class);
70 @Successor protected NodeSuccessorList<AbstractBeginNode> successors;
71 @Input protected ValueNode value;
72
73 // do not change the contents of these arrays:
74 protected final double[] keyProbabilities;
75 protected final int[] keySuccessors;
76
77 /**
78 * Constructs a new Switch.
79 *
80 * @param value the instruction that provides the value to be switched over
81 * @param successors the list of successors of this switch
82 */
83 protected SwitchNode(NodeClass<? extends SwitchNode> c, ValueNode value, AbstractBeginNode[] successors, int[] keySuccessors, double[] keyProbabilities) {
84 super(c, StampFactory.forVoid());
85 assert value.stamp(NodeView.DEFAULT).getStackKind().isNumericInteger() || value.stamp(NodeView.DEFAULT) instanceof AbstractPointerStamp : value.stamp(NodeView.DEFAULT) +
86 " key not supported by SwitchNode";
87 assert keySuccessors.length == keyProbabilities.length;
88 this.successors = new NodeSuccessorList<>(this, successors);
89 this.value = value;
90 this.keySuccessors = keySuccessors;
91 this.keyProbabilities = keyProbabilities;
92 assert assertProbabilities();
93 }
94
95 private boolean assertProbabilities() {
96 double total = 0;
97 for (double d : keyProbabilities) {
98 total += d;
99 assert d >= 0.0 : "Cannot have negative probabilities in switch node: " + d;
100 }
101 assert total > 0.999 && total < 1.001 : "Total " + total;
102 return true;
103 }
104
105 @Override
106 public int getSuccessorCount() {
107 return successors.count();
108 }
109
110 @Override
111 public double probability(AbstractBeginNode successor) {
112 double sum = 0;
113 for (int i = 0; i < keySuccessors.length; i++) {
114 if (successors.get(keySuccessors[i]) == successor) {
115 sum += keyProbabilities[i];
116 }
117 }
118 return sum;
119 }
120
121 @Override
122 public boolean setProbability(AbstractBeginNode successor, double value) {
123 assert value <= 1.0 && value >= 0.0 : value;
124 assert assertProbabilities();
125
126 double sum = 0;
127 double otherSum = 0;
128 for (int i = 0; i < keySuccessors.length; i++) {
129 if (successors.get(keySuccessors[i]) == successor) {
130 sum += keyProbabilities[i];
131 } else {
132 otherSum += keyProbabilities[i];
133 }
134 }
135
136 if (otherSum == 0 || sum == 0) {
137 // Cannot correctly adjust probabilities.
138 return false;
139 }
140
141 double delta = value - sum;
142
143 for (int i = 0; i < keySuccessors.length; i++) {
144 if (successors.get(keySuccessors[i]) == successor) {
145 keyProbabilities[i] = Math.max(0.0, keyProbabilities[i] + (delta * keyProbabilities[i]) / sum);
146 } else {
147 keyProbabilities[i] = Math.max(0.0, keyProbabilities[i] - (delta * keyProbabilities[i]) / otherSum);
148 }
149 }
150 assert assertProbabilities();
151 return true;
152 }
153
154 public ValueNode value() {
155 return value;
156 }
157
158 public abstract boolean isSorted();
159
160 /**
161 * The number of distinct keys in this switch.
162 */
163 public abstract int keyCount();
164
165 /**
166 * The key at the specified position, encoded in a Constant.
167 */
168 public abstract Constant keyAt(int i);
169
170 public boolean structureEquals(SwitchNode switchNode) {
171 return Arrays.equals(keySuccessors, switchNode.keySuccessors) && equalKeys(switchNode);
172 }
173
174 /**
175 * Returns true if the switch has the same keys in the same order as this switch.
176 */
177 public abstract boolean equalKeys(SwitchNode switchNode);
178
179 /**
180 * Returns the index of the successor belonging to the key at the specified index.
181 */
182 public int keySuccessorIndex(int i) {
183 return keySuccessors[i];
184 }
185
186 /**
187 * Returns the successor for the key at the given index.
188 */
189 public AbstractBeginNode keySuccessor(int i) {
190 return successors.get(keySuccessors[i]);
191 }
192
193 /**
194 * Returns the probability of the key at the given index.
195 */
196 public double keyProbability(int i) {
197 return keyProbabilities[i];
198 }
199
200 /**
201 * Returns the probability of taking the default branch.
202 */
203 public double defaultProbability() {
204 return keyProbabilities[keyProbabilities.length - 1];
205 }
206
207 /**
208 * Returns the index of the default (fall through) successor of this switch.
209 */
210 public int defaultSuccessorIndex() {
211 return keySuccessors[keySuccessors.length - 1];
212 }
213
214 public AbstractBeginNode blockSuccessor(int i) {
215 return successors.get(i);
216 }
217
218 public void setBlockSuccessor(int i, AbstractBeginNode s) {
219 successors.set(i, s);
220 }
221
222 public int blockSuccessorCount() {
223 return successors.count();
224 }
225
226 /**
227 * Gets the successor corresponding to the default (fall through) case.
228 *
229 * @return the default successor
230 */
231 public AbstractBeginNode defaultSuccessor() {
232 if (defaultSuccessorIndex() == -1) {
233 throw new GraalError("unexpected");
234 }
235 return successors.get(defaultSuccessorIndex());
236 }
237
238 @Override
239 public AbstractBeginNode getPrimarySuccessor() {
240 return null;
241 }
242
243 /**
244 * Delete all other successors except for the one reached by {@code survivingEdge}.
245 *
246 * @param tool
247 * @param survivingEdge index of the edge in the {@link SwitchNode#successors} list
248 */
249 protected void killOtherSuccessors(SimplifierTool tool, int survivingEdge) {
250 for (Node successor : successors()) {
251 /*
252 * Deleting a branch change change the successors so reload the surviving successor each
253 * time.
254 */
255 if (successor != blockSuccessor(survivingEdge)) {
256 tool.deleteBranch(successor);
257 }
258 }
259 tool.addToWorkList(blockSuccessor(survivingEdge));
260 graph().removeSplit(this, blockSuccessor(survivingEdge));
261 }
262
263 public abstract Stamp getValueStampForSuccessor(AbstractBeginNode beginNode);
264
265 @Override
266 public NodeCycles estimatedNodeCycles() {
267 if (keyCount() == 1) {
268 // if
269 return CYCLES_2;
270 } else if (isSorted()) {
271 // good heuristic
272 return CYCLES_8;
273 } else {
274 // not so good
275 return CYCLES_64;
276 }
277 }
278
279 @Override
280 public NodeSize estimatedNodeSize() {
281 if (keyCount() == 1) {
282 // if
283 return SIZE_2;
284 } else if (isSorted()) {
285 // good heuristic
286 return SIZE_8;
287 } else {
288 // not so good
289 return SIZE_64;
290 }
291 }
292
293 }