001/* 002 * Copyright (c) 2009, 2014, Oracle and/or its affiliates. All rights reserved. 003 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 004 * 005 * This code is free software; you can redistribute it and/or modify it 006 * under the terms of the GNU General Public License version 2 only, as 007 * published by the Free Software Foundation. 008 * 009 * This code is distributed in the hope that it will be useful, but WITHOUT 010 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 011 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 012 * version 2 for more details (a copy is included in the LICENSE file that 013 * accompanied this code). 014 * 015 * You should have received a copy of the GNU General Public License version 016 * 2 along with this work; if not, write to the Free Software Foundation, 017 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 018 * 019 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 020 * or visit www.oracle.com if you need additional information or have any 021 * questions. 022 */ 023package com.oracle.graal.nodes.java; 024 025import java.util.*; 026 027import jdk.internal.jvmci.meta.*; 028 029import com.oracle.graal.compiler.common.type.*; 030import com.oracle.graal.graph.*; 031import com.oracle.graal.graph.spi.*; 032import com.oracle.graal.nodeinfo.*; 033import com.oracle.graal.nodes.*; 034import com.oracle.graal.nodes.extended.*; 035import com.oracle.graal.nodes.spi.*; 036import com.oracle.graal.nodes.util.*; 037 038/** 039 * The {@code TypeSwitchNode} performs a lookup based on the type of the input value. The type 040 * comparison is an exact type comparison, not an instanceof. 041 */ 042@NodeInfo 043public final class TypeSwitchNode extends SwitchNode implements LIRLowerable, Simplifiable { 044 045 public static final NodeClass<TypeSwitchNode> TYPE = NodeClass.create(TypeSwitchNode.class); 046 protected final ResolvedJavaType[] keys; 047 048 public TypeSwitchNode(ValueNode value, AbstractBeginNode[] successors, ResolvedJavaType[] keys, double[] keyProbabilities, int[] keySuccessors) { 049 super(TYPE, value, successors, keySuccessors, keyProbabilities); 050 assert successors.length <= keys.length + 1; 051 assert keySuccessors.length == keyProbabilities.length; 052 this.keys = keys; 053 assert value.stamp() instanceof AbstractPointerStamp; 054 assert assertKeys(); 055 } 056 057 /** 058 * Don't allow duplicate keys. 059 */ 060 private boolean assertKeys() { 061 for (int i = 0; i < keys.length; i++) { 062 for (int j = 0; j < keys.length; j++) { 063 if (i == j) { 064 continue; 065 } 066 assert !keys[i].equals(keys[j]); 067 } 068 } 069 return true; 070 } 071 072 @Override 073 public boolean isSorted() { 074 Kind kind = value().getKind(); 075 if (kind.isNumericInteger()) { 076 JavaConstant lastKey = null; 077 for (int i = 0; i < keyCount(); i++) { 078 JavaConstant key = keyAt(i); 079 if (lastKey != null && key.asLong() <= lastKey.asLong()) { 080 return false; 081 } 082 lastKey = key; 083 } 084 return true; 085 } else { 086 return false; 087 } 088 } 089 090 @Override 091 public int keyCount() { 092 return keys.length; 093 } 094 095 @Override 096 public JavaConstant keyAt(int index) { 097 return (JavaConstant) keys[index].getObjectHub(); 098 } 099 100 @Override 101 public boolean equalKeys(SwitchNode switchNode) { 102 if (!(switchNode instanceof TypeSwitchNode)) { 103 return false; 104 } 105 TypeSwitchNode other = (TypeSwitchNode) switchNode; 106 return Arrays.equals(keys, other.keys); 107 } 108 109 public ResolvedJavaType typeAt(int index) { 110 return keys[index]; 111 } 112 113 @Override 114 public void generate(NodeLIRBuilderTool gen) { 115 gen.emitSwitch(this); 116 } 117 118 @Override 119 public void simplify(SimplifierTool tool) { 120 if (value() instanceof ConstantNode) { 121 JavaConstant constant = value().asJavaConstant(); 122 123 int survivingEdge = keySuccessorIndex(keyCount()); 124 for (int i = 0; i < keyCount(); i++) { 125 JavaConstant typeHub = keyAt(i); 126 assert constant.getKind() == typeHub.getKind(); 127 Boolean equal = tool.getConstantReflection().constantEquals(constant, typeHub); 128 if (equal == null) { 129 /* We don't know if this key is a match or not, so we cannot simplify. */ 130 return; 131 } else if (equal.booleanValue()) { 132 survivingEdge = keySuccessorIndex(i); 133 } 134 } 135 killOtherSuccessors(tool, survivingEdge); 136 } 137 if (value() instanceof LoadHubNode && ((LoadHubNode) value()).getValue().stamp() instanceof ObjectStamp) { 138 ObjectStamp objectStamp = (ObjectStamp) ((LoadHubNode) value()).getValue().stamp(); 139 if (objectStamp.type() != null) { 140 int validKeys = 0; 141 for (int i = 0; i < keyCount(); i++) { 142 if (objectStamp.type().isAssignableFrom(keys[i])) { 143 validKeys++; 144 } 145 } 146 if (validKeys == 0) { 147 tool.addToWorkList(defaultSuccessor()); 148 graph().removeSplitPropagate(this, defaultSuccessor()); 149 } else if (validKeys != keys.length) { 150 ArrayList<AbstractBeginNode> newSuccessors = new ArrayList<>(blockSuccessorCount()); 151 ResolvedJavaType[] newKeys = new ResolvedJavaType[validKeys]; 152 int[] newKeySuccessors = new int[validKeys + 1]; 153 double[] newKeyProbabilities = new double[validKeys + 1]; 154 double totalProbability = 0; 155 int current = 0; 156 for (int i = 0; i < keyCount() + 1; i++) { 157 if (i == keyCount() || objectStamp.type().isAssignableFrom(keys[i])) { 158 int index = newSuccessors.indexOf(keySuccessor(i)); 159 if (index == -1) { 160 index = newSuccessors.size(); 161 newSuccessors.add(keySuccessor(i)); 162 } 163 newKeySuccessors[current] = index; 164 if (i < keyCount()) { 165 newKeys[current] = keys[i]; 166 } 167 newKeyProbabilities[current] = keyProbability(i); 168 totalProbability += keyProbability(i); 169 current++; 170 } 171 } 172 if (totalProbability > 0) { 173 for (int i = 0; i < current; i++) { 174 newKeyProbabilities[i] /= totalProbability; 175 } 176 } else { 177 for (int i = 0; i < current; i++) { 178 newKeyProbabilities[i] = 1.0 / current; 179 } 180 } 181 182 for (int i = 0; i < blockSuccessorCount(); i++) { 183 AbstractBeginNode successor = blockSuccessor(i); 184 if (!newSuccessors.contains(successor)) { 185 tool.deleteBranch(successor); 186 } 187 setBlockSuccessor(i, null); 188 } 189 190 AbstractBeginNode[] successorsArray = newSuccessors.toArray(new AbstractBeginNode[newSuccessors.size()]); 191 TypeSwitchNode newSwitch = graph().add(new TypeSwitchNode(value(), successorsArray, newKeys, newKeyProbabilities, newKeySuccessors)); 192 ((FixedWithNextNode) predecessor()).setNext(newSwitch); 193 GraphUtil.killWithUnusedFloatingInputs(this); 194 } 195 } 196 } 197 } 198}