| /* |
| * Copyright (c) 2009, 2015, Oracle and/or its affiliates. All rights reserved. |
| * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
| * |
| * This code is free software; you can redistribute it and/or modify it |
| * under the terms of the GNU General Public License version 2 only, as |
| * published by the Free Software Foundation. |
| * |
| * This code is distributed in the hope that it will be useful, but WITHOUT |
| * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
| * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
| * version 2 for more details (a copy is included in the LICENSE file that |
| * accompanied this code). |
| * |
| * You should have received a copy of the GNU General Public License version |
| * 2 along with this work; if not, write to the Free Software Foundation, |
| * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. |
| * |
| * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
| * or visit www.oracle.com if you need additional information or have any |
| * questions. |
| */ |
| package org.graalvm.compiler.nodes.java; |
| |
| import java.util.ArrayList; |
| import java.util.Arrays; |
| |
| import org.graalvm.compiler.core.common.type.AbstractPointerStamp; |
| import org.graalvm.compiler.core.common.type.ObjectStamp; |
| import org.graalvm.compiler.core.common.type.Stamp; |
| import org.graalvm.compiler.core.common.type.StampFactory; |
| import org.graalvm.compiler.core.common.type.TypeReference; |
| import org.graalvm.compiler.graph.NodeClass; |
| import org.graalvm.compiler.graph.spi.Simplifiable; |
| import org.graalvm.compiler.graph.spi.SimplifierTool; |
| import org.graalvm.compiler.nodeinfo.NodeInfo; |
| import org.graalvm.compiler.nodes.AbstractBeginNode; |
| import org.graalvm.compiler.nodes.ConstantNode; |
| import org.graalvm.compiler.nodes.FixedWithNextNode; |
| import org.graalvm.compiler.nodes.ValueNode; |
| import org.graalvm.compiler.nodes.extended.LoadHubNode; |
| import org.graalvm.compiler.nodes.extended.SwitchNode; |
| import org.graalvm.compiler.nodes.spi.LIRLowerable; |
| import org.graalvm.compiler.nodes.spi.NodeLIRBuilderTool; |
| import org.graalvm.compiler.nodes.util.GraphUtil; |
| |
| import jdk.vm.ci.meta.Constant; |
| import jdk.vm.ci.meta.ConstantReflectionProvider; |
| import jdk.vm.ci.meta.ResolvedJavaType; |
| |
| /** |
| * The {@code TypeSwitchNode} performs a lookup based on the type of the input value. The type |
| * comparison is an exact type comparison, not an instanceof. |
| */ |
| @NodeInfo |
| public final class TypeSwitchNode extends SwitchNode implements LIRLowerable, Simplifiable { |
| |
| public static final NodeClass<TypeSwitchNode> TYPE = NodeClass.create(TypeSwitchNode.class); |
| protected final ResolvedJavaType[] keys; |
| protected final Constant[] hubs; |
| |
| public TypeSwitchNode(ValueNode value, AbstractBeginNode[] successors, ResolvedJavaType[] keys, double[] keyProbabilities, int[] keySuccessors, ConstantReflectionProvider constantReflection) { |
| super(TYPE, value, successors, keySuccessors, keyProbabilities); |
| assert successors.length <= keys.length + 1; |
| assert keySuccessors.length == keyProbabilities.length; |
| this.keys = keys; |
| assert value.stamp() instanceof AbstractPointerStamp; |
| assert assertKeys(); |
| |
| hubs = new Constant[keys.length]; |
| for (int i = 0; i < hubs.length; i++) { |
| hubs[i] = constantReflection.asObjectHub(keys[i]); |
| } |
| } |
| |
| /** |
| * Don't allow duplicate keys. |
| */ |
| private boolean assertKeys() { |
| for (int i = 0; i < keys.length; i++) { |
| for (int j = 0; j < keys.length; j++) { |
| if (i == j) { |
| continue; |
| } |
| assert !keys[i].equals(keys[j]); |
| } |
| } |
| return true; |
| } |
| |
| @Override |
| public boolean isSorted() { |
| return false; |
| } |
| |
| @Override |
| public int keyCount() { |
| return keys.length; |
| } |
| |
| @Override |
| public Constant keyAt(int index) { |
| return hubs[index]; |
| } |
| |
| @Override |
| public boolean equalKeys(SwitchNode switchNode) { |
| if (!(switchNode instanceof TypeSwitchNode)) { |
| return false; |
| } |
| TypeSwitchNode other = (TypeSwitchNode) switchNode; |
| return Arrays.equals(keys, other.keys); |
| } |
| |
| public ResolvedJavaType typeAt(int index) { |
| return keys[index]; |
| } |
| |
| @Override |
| public void generate(NodeLIRBuilderTool gen) { |
| gen.emitSwitch(this); |
| } |
| |
| @Override |
| public void simplify(SimplifierTool tool) { |
| if (value() instanceof ConstantNode) { |
| Constant constant = value().asConstant(); |
| |
| int survivingEdge = keySuccessorIndex(keyCount()); |
| for (int i = 0; i < keyCount(); i++) { |
| Constant typeHub = keyAt(i); |
| Boolean equal = tool.getConstantReflection().constantEquals(constant, typeHub); |
| if (equal == null) { |
| /* We don't know if this key is a match or not, so we cannot simplify. */ |
| return; |
| } else if (equal.booleanValue()) { |
| survivingEdge = keySuccessorIndex(i); |
| } |
| } |
| killOtherSuccessors(tool, survivingEdge); |
| } |
| if (value() instanceof LoadHubNode && ((LoadHubNode) value()).getValue().stamp() instanceof ObjectStamp) { |
| ObjectStamp objectStamp = (ObjectStamp) ((LoadHubNode) value()).getValue().stamp(); |
| if (objectStamp.type() != null) { |
| int validKeys = 0; |
| for (int i = 0; i < keyCount(); i++) { |
| if (objectStamp.type().isAssignableFrom(keys[i])) { |
| validKeys++; |
| } |
| } |
| if (validKeys == 0) { |
| tool.addToWorkList(defaultSuccessor()); |
| graph().removeSplitPropagate(this, defaultSuccessor()); |
| } else if (validKeys != keys.length) { |
| ArrayList<AbstractBeginNode> newSuccessors = new ArrayList<>(blockSuccessorCount()); |
| ResolvedJavaType[] newKeys = new ResolvedJavaType[validKeys]; |
| int[] newKeySuccessors = new int[validKeys + 1]; |
| double[] newKeyProbabilities = new double[validKeys + 1]; |
| double totalProbability = 0; |
| int current = 0; |
| for (int i = 0; i < keyCount() + 1; i++) { |
| if (i == keyCount() || objectStamp.type().isAssignableFrom(keys[i])) { |
| int index = newSuccessors.indexOf(keySuccessor(i)); |
| if (index == -1) { |
| index = newSuccessors.size(); |
| newSuccessors.add(keySuccessor(i)); |
| } |
| newKeySuccessors[current] = index; |
| if (i < keyCount()) { |
| newKeys[current] = keys[i]; |
| } |
| newKeyProbabilities[current] = keyProbability(i); |
| totalProbability += keyProbability(i); |
| current++; |
| } |
| } |
| if (totalProbability > 0) { |
| for (int i = 0; i < current; i++) { |
| newKeyProbabilities[i] /= totalProbability; |
| } |
| } else { |
| for (int i = 0; i < current; i++) { |
| newKeyProbabilities[i] = 1.0 / current; |
| } |
| } |
| |
| for (int i = 0; i < blockSuccessorCount(); i++) { |
| AbstractBeginNode successor = blockSuccessor(i); |
| if (!newSuccessors.contains(successor)) { |
| tool.deleteBranch(successor); |
| } |
| setBlockSuccessor(i, null); |
| } |
| |
| AbstractBeginNode[] successorsArray = newSuccessors.toArray(new AbstractBeginNode[newSuccessors.size()]); |
| TypeSwitchNode newSwitch = graph().add(new TypeSwitchNode(value(), successorsArray, newKeys, newKeyProbabilities, newKeySuccessors, tool.getConstantReflection())); |
| ((FixedWithNextNode) predecessor()).setNext(newSwitch); |
| GraphUtil.killWithUnusedFloatingInputs(this); |
| } |
| } |
| } |
| } |
| |
| @Override |
| public Stamp getValueStampForSuccessor(AbstractBeginNode beginNode) { |
| Stamp result = null; |
| if (beginNode != defaultSuccessor()) { |
| for (int i = 0; i < keyCount(); i++) { |
| if (keySuccessor(i) == beginNode) { |
| if (result == null) { |
| result = StampFactory.objectNonNull(TypeReference.createExactTrusted(typeAt(i))); |
| } else { |
| result = result.meet(StampFactory.objectNonNull(TypeReference.createExactTrusted(typeAt(i)))); |
| } |
| } |
| } |
| } |
| return result; |
| } |
| } |