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.java; 26 27 import java.util.ArrayList; 28 import java.util.Arrays; 29 30 import org.graalvm.compiler.core.common.type.AbstractPointerStamp; 31 import org.graalvm.compiler.core.common.type.ObjectStamp; 32 import org.graalvm.compiler.core.common.type.Stamp; 33 import org.graalvm.compiler.core.common.type.StampFactory; 34 import org.graalvm.compiler.core.common.type.TypeReference; 35 import org.graalvm.compiler.graph.NodeClass; 36 import org.graalvm.compiler.graph.spi.Simplifiable; 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.ConstantNode; 41 import org.graalvm.compiler.nodes.FixedWithNextNode; 42 import org.graalvm.compiler.nodes.NodeView; 43 import org.graalvm.compiler.nodes.ValueNode; 44 import org.graalvm.compiler.nodes.extended.LoadHubNode; 45 import org.graalvm.compiler.nodes.extended.SwitchNode; 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.Constant; 51 import jdk.vm.ci.meta.ConstantReflectionProvider; 52 import jdk.vm.ci.meta.ResolvedJavaType; 53 54 /** 55 * The {@code TypeSwitchNode} performs a lookup based on the type of the input value. The type 56 * comparison is an exact type comparison, not an instanceof. 57 */ 58 @NodeInfo 59 public final class TypeSwitchNode extends SwitchNode implements LIRLowerable, Simplifiable { 60 61 public static final NodeClass<TypeSwitchNode> TYPE = NodeClass.create(TypeSwitchNode.class); 62 protected final ResolvedJavaType[] keys; 63 protected final Constant[] hubs; 64 65 public TypeSwitchNode(ValueNode value, AbstractBeginNode[] successors, ResolvedJavaType[] keys, double[] keyProbabilities, int[] keySuccessors, ConstantReflectionProvider constantReflection) { 66 super(TYPE, value, successors, keySuccessors, keyProbabilities); 67 assert successors.length <= keys.length + 1; 68 assert keySuccessors.length == keyProbabilities.length; 69 this.keys = keys; 70 assert value.stamp(NodeView.DEFAULT) instanceof AbstractPointerStamp; 71 assert assertKeys(); 72 73 hubs = new Constant[keys.length]; 74 for (int i = 0; i < hubs.length; i++) { 75 hubs[i] = constantReflection.asObjectHub(keys[i]); 76 } 77 } 78 79 /** 80 * Don't allow duplicate keys. 81 */ 82 private boolean assertKeys() { 83 for (int i = 0; i < keys.length; i++) { 84 for (int j = 0; j < keys.length; j++) { 85 if (i == j) { 86 continue; 87 } 88 assert !keys[i].equals(keys[j]); 89 } 90 } 91 return true; 92 } 93 94 @Override 95 public boolean isSorted() { 96 return false; 97 } 98 99 @Override 100 public int keyCount() { 101 return keys.length; 102 } 103 104 @Override 105 public Constant keyAt(int index) { 106 return hubs[index]; 107 } 108 109 @Override 110 public boolean equalKeys(SwitchNode switchNode) { 111 if (!(switchNode instanceof TypeSwitchNode)) { 112 return false; 113 } 114 TypeSwitchNode other = (TypeSwitchNode) switchNode; 115 return Arrays.equals(keys, other.keys); 116 } 117 118 public ResolvedJavaType typeAt(int index) { 119 return keys[index]; 120 } 121 122 @Override 123 public void generate(NodeLIRBuilderTool gen) { 124 gen.emitSwitch(this); 125 } 126 127 @Override 128 public void simplify(SimplifierTool tool) { 129 NodeView view = NodeView.from(tool); 130 if (value() instanceof ConstantNode) { 131 Constant constant = value().asConstant(); 132 133 int survivingEdge = keySuccessorIndex(keyCount()); 134 for (int i = 0; i < keyCount(); i++) { 135 Constant typeHub = keyAt(i); 136 Boolean equal = tool.getConstantReflection().constantEquals(constant, typeHub); 137 if (equal == null) { 138 /* We don't know if this key is a match or not, so we cannot simplify. */ 139 return; 140 } else if (equal.booleanValue()) { 141 survivingEdge = keySuccessorIndex(i); 142 } 143 } 144 killOtherSuccessors(tool, survivingEdge); 145 } 146 if (value() instanceof LoadHubNode && ((LoadHubNode) value()).getValue().stamp(view) instanceof ObjectStamp) { 147 ObjectStamp objectStamp = (ObjectStamp) ((LoadHubNode) value()).getValue().stamp(view); 148 if (objectStamp.type() != null) { 149 int validKeys = 0; 150 for (int i = 0; i < keyCount(); i++) { 151 if (objectStamp.type().isAssignableFrom(keys[i])) { 152 validKeys++; 153 } 154 } 155 if (validKeys == 0) { 156 tool.addToWorkList(defaultSuccessor()); 157 graph().removeSplitPropagate(this, defaultSuccessor()); 158 } else if (validKeys != keys.length) { 159 ArrayList<AbstractBeginNode> newSuccessors = new ArrayList<>(blockSuccessorCount()); 160 ResolvedJavaType[] newKeys = new ResolvedJavaType[validKeys]; 161 int[] newKeySuccessors = new int[validKeys + 1]; 162 double[] newKeyProbabilities = new double[validKeys + 1]; 163 double totalProbability = 0; 164 int current = 0; 165 for (int i = 0; i < keyCount() + 1; i++) { 166 if (i == keyCount() || objectStamp.type().isAssignableFrom(keys[i])) { 167 int index = newSuccessors.indexOf(keySuccessor(i)); 168 if (index == -1) { 169 index = newSuccessors.size(); 170 newSuccessors.add(keySuccessor(i)); 171 } 172 newKeySuccessors[current] = index; 173 if (i < keyCount()) { 174 newKeys[current] = keys[i]; 175 } 176 newKeyProbabilities[current] = keyProbability(i); 177 totalProbability += keyProbability(i); 178 current++; 179 } 180 } 181 if (totalProbability > 0) { 182 for (int i = 0; i < current; i++) { 183 newKeyProbabilities[i] /= totalProbability; 184 } 185 } else { 186 for (int i = 0; i < current; i++) { 187 newKeyProbabilities[i] = 1.0 / current; 188 } 189 } 190 191 ArrayList<AbstractBeginNode> oldSuccessors = new ArrayList<>(); 192 for (int i = 0; i < blockSuccessorCount(); i++) { 193 AbstractBeginNode successor = blockSuccessor(i); 194 oldSuccessors.add(successor); 195 setBlockSuccessor(i, null); 196 } 197 198 AbstractBeginNode[] successorsArray = newSuccessors.toArray(new AbstractBeginNode[newSuccessors.size()]); 199 TypeSwitchNode newSwitch = graph().add(new TypeSwitchNode(value(), successorsArray, newKeys, newKeyProbabilities, newKeySuccessors, tool.getConstantReflection())); 200 ((FixedWithNextNode) predecessor()).setNext(newSwitch); 201 GraphUtil.killWithUnusedFloatingInputs(this); 202 203 for (int i = 0; i < oldSuccessors.size(); i++) { 204 AbstractBeginNode successor = oldSuccessors.get(i); 205 if (!newSuccessors.contains(successor)) { 206 GraphUtil.killCFG(successor); 207 } 208 } 209 } 210 } 211 } 212 } 213 214 @Override 215 public Stamp getValueStampForSuccessor(AbstractBeginNode beginNode) { 216 Stamp result = null; 217 if (beginNode != defaultSuccessor()) { 218 for (int i = 0; i < keyCount(); i++) { 219 if (keySuccessor(i) == beginNode) { 220 if (result == null) { 221 result = StampFactory.objectNonNull(TypeReference.createExactTrusted(typeAt(i))); 222 } else { 223 result = result.meet(StampFactory.objectNonNull(TypeReference.createExactTrusted(typeAt(i)))); 224 } 225 } 226 } 227 } 228 return result; 229 } 230 }