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