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