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