1 /* 2 * Copyright (c) 2012, 2016, 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.type; 26 27 import java.util.Iterator; 28 29 import org.graalvm.compiler.core.common.type.AbstractObjectStamp; 30 import org.graalvm.compiler.core.common.type.AbstractPointerStamp; 31 import org.graalvm.compiler.core.common.type.IntegerStamp; 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.nodes.NodeView; 36 import org.graalvm.compiler.nodes.ValueNode; 37 38 import jdk.vm.ci.code.CodeUtil; 39 import jdk.vm.ci.meta.JavaKind; 40 import jdk.vm.ci.meta.MetaAccessProvider; 41 import jdk.vm.ci.meta.ResolvedJavaType; 42 43 /** 44 * Helper class that is used to keep all stamp-related operations in one place. 45 */ 46 public class StampTool { 47 meet(Iterable<? extends ValueNode> values)48 public static Stamp meet(Iterable<? extends ValueNode> values) { 49 Stamp stamp = meetOrNull(values, null); 50 if (stamp == null) { 51 return StampFactory.forVoid(); 52 } 53 return stamp; 54 } 55 56 /** 57 * Meet a collection of {@link ValueNode}s optionally excluding {@code selfValue}. If no values 58 * are encountered then return {@code null}. 59 */ meetOrNull(Iterable<? extends ValueNode> values, ValueNode selfValue)60 public static Stamp meetOrNull(Iterable<? extends ValueNode> values, ValueNode selfValue) { 61 Iterator<? extends ValueNode> iterator = values.iterator(); 62 Stamp stamp = null; 63 while (iterator.hasNext()) { 64 ValueNode nextValue = iterator.next(); 65 if (nextValue != selfValue) { 66 if (stamp == null) { 67 stamp = nextValue.stamp(NodeView.DEFAULT); 68 } else { 69 stamp = stamp.meet(nextValue.stamp(NodeView.DEFAULT)); 70 } 71 } 72 } 73 return stamp; 74 } 75 76 /** 77 * Compute the stamp resulting from the unsigned comparison being true. 78 * 79 * @return null if it's can't be true or it nothing useful can be encoded. 80 */ unsignedCompare(Stamp stamp, Stamp stamp2)81 public static Stamp unsignedCompare(Stamp stamp, Stamp stamp2) { 82 IntegerStamp x = (IntegerStamp) stamp; 83 IntegerStamp y = (IntegerStamp) stamp2; 84 if (x.isUnrestricted() && y.isUnrestricted()) { 85 // Don't know anything. 86 return null; 87 } 88 // c <| n, where c is a constant and n is known to be positive. 89 if (x.lowerBound() == x.upperBound()) { 90 if (y.isPositive()) { 91 if (x.lowerBound() == (1 << x.getBits()) - 1) { 92 // Constant is MAX_VALUE which must fail. 93 return null; 94 } 95 if (x.lowerBound() <= y.lowerBound()) { 96 // Test will fail. Return illegalStamp instead? 97 return null; 98 } 99 // If the test succeeds then this proves that n is at greater than c so the bounds 100 // are [c+1..-n.upperBound)]. 101 return StampFactory.forInteger(x.getBits(), x.lowerBound() + 1, y.upperBound()); 102 } 103 return null; 104 } 105 // n <| c, where c is a strictly positive constant 106 if (y.lowerBound() == y.upperBound() && y.isStrictlyPositive()) { 107 // The test proves that n is positive and less than c, [0..c-1] 108 return StampFactory.forInteger(y.getBits(), 0, y.lowerBound() - 1); 109 } 110 return null; 111 } 112 stampForLeadingZeros(IntegerStamp valueStamp)113 public static Stamp stampForLeadingZeros(IntegerStamp valueStamp) { 114 long mask = CodeUtil.mask(valueStamp.getBits()); 115 // Don't count zeros from the mask in the result. 116 int adjust = Long.numberOfLeadingZeros(mask); 117 assert adjust == 0 || adjust == 32; 118 int min = Long.numberOfLeadingZeros(valueStamp.upMask() & mask) - adjust; 119 int max = Long.numberOfLeadingZeros(valueStamp.downMask() & mask) - adjust; 120 return StampFactory.forInteger(JavaKind.Int, min, max); 121 } 122 stampForTrailingZeros(IntegerStamp valueStamp)123 public static Stamp stampForTrailingZeros(IntegerStamp valueStamp) { 124 long mask = CodeUtil.mask(valueStamp.getBits()); 125 int min = Long.numberOfTrailingZeros(valueStamp.upMask() & mask); 126 int max = Long.numberOfTrailingZeros(valueStamp.downMask() & mask); 127 return StampFactory.forInteger(JavaKind.Int, min, max); 128 } 129 130 /** 131 * Checks whether this {@link ValueNode} represents a {@linkplain Stamp#hasValues() legal} 132 * pointer value which is known to be always null. 133 * 134 * @param node the node to check 135 * @return true if this node represents a legal object value which is known to be always null 136 */ isPointerAlwaysNull(ValueNode node)137 public static boolean isPointerAlwaysNull(ValueNode node) { 138 return isPointerAlwaysNull(node.stamp(NodeView.DEFAULT)); 139 } 140 141 /** 142 * Checks whether this {@link Stamp} represents a {@linkplain Stamp#hasValues() legal} pointer 143 * stamp whose values are known to be always null. 144 * 145 * @param stamp the stamp to check 146 * @return true if this stamp represents a legal object stamp whose values are known to be 147 * always null 148 */ isPointerAlwaysNull(Stamp stamp)149 public static boolean isPointerAlwaysNull(Stamp stamp) { 150 if (stamp instanceof AbstractPointerStamp && stamp.hasValues()) { 151 return ((AbstractPointerStamp) stamp).alwaysNull(); 152 } 153 return false; 154 } 155 156 /** 157 * Checks whether this {@link ValueNode} represents a {@linkplain Stamp#hasValues() legal} 158 * pointer value which is known to never be null. 159 * 160 * @param node the node to check 161 * @return true if this node represents a legal object value which is known to never be null 162 */ isPointerNonNull(ValueNode node)163 public static boolean isPointerNonNull(ValueNode node) { 164 return isPointerNonNull(node.stamp(NodeView.DEFAULT)); 165 } 166 167 /** 168 * Checks whether this {@link Stamp} represents a {@linkplain Stamp#hasValues() legal} pointer 169 * stamp whose values are known to never be null. 170 * 171 * @param stamp the stamp to check 172 * @return true if this stamp represents a legal object stamp whose values are known to be 173 * always null 174 */ isPointerNonNull(Stamp stamp)175 public static boolean isPointerNonNull(Stamp stamp) { 176 if (stamp instanceof AbstractPointerStamp) { 177 return ((AbstractPointerStamp) stamp).nonNull(); 178 } 179 return false; 180 } 181 182 /** 183 * Returns the {@linkplain ResolvedJavaType Java type} this {@linkplain ValueNode} has if it is 184 * a {@linkplain Stamp#hasValues() legal} Object value. 185 * 186 * @param node the node to check 187 * @return the Java type this value has if it is a legal Object type, null otherwise 188 */ typeReferenceOrNull(ValueNode node)189 public static TypeReference typeReferenceOrNull(ValueNode node) { 190 return typeReferenceOrNull(node.stamp(NodeView.DEFAULT)); 191 } 192 typeOrNull(ValueNode node)193 public static ResolvedJavaType typeOrNull(ValueNode node) { 194 return typeOrNull(node.stamp(NodeView.DEFAULT)); 195 } 196 typeOrNull(Stamp stamp)197 public static ResolvedJavaType typeOrNull(Stamp stamp) { 198 TypeReference type = typeReferenceOrNull(stamp); 199 return type == null ? null : type.getType(); 200 } 201 typeOrNull(Stamp stamp, MetaAccessProvider metaAccess)202 public static ResolvedJavaType typeOrNull(Stamp stamp, MetaAccessProvider metaAccess) { 203 if (stamp instanceof AbstractObjectStamp && stamp.hasValues()) { 204 AbstractObjectStamp abstractObjectStamp = (AbstractObjectStamp) stamp; 205 ResolvedJavaType type = abstractObjectStamp.type(); 206 if (type == null) { 207 return metaAccess.lookupJavaType(Object.class); 208 } else { 209 return type; 210 } 211 } 212 return null; 213 } 214 typeOrNull(ValueNode node, MetaAccessProvider metaAccess)215 public static ResolvedJavaType typeOrNull(ValueNode node, MetaAccessProvider metaAccess) { 216 return typeOrNull(node.stamp(NodeView.DEFAULT), metaAccess); 217 } 218 219 /** 220 * Returns the {@linkplain ResolvedJavaType Java type} this {@linkplain Stamp} has if it is a 221 * {@linkplain Stamp#hasValues() legal} Object stamp. 222 * 223 * @param stamp the stamp to check 224 * @return the Java type this stamp has if it is a legal Object stamp, null otherwise 225 */ typeReferenceOrNull(Stamp stamp)226 public static TypeReference typeReferenceOrNull(Stamp stamp) { 227 if (stamp instanceof AbstractObjectStamp && stamp.hasValues()) { 228 AbstractObjectStamp abstractObjectStamp = (AbstractObjectStamp) stamp; 229 if (abstractObjectStamp.isExactType()) { 230 return TypeReference.createExactTrusted(abstractObjectStamp.type()); 231 } else { 232 return TypeReference.createTrustedWithoutAssumptions(abstractObjectStamp.type()); 233 } 234 } 235 return null; 236 } 237 238 /** 239 * Checks whether this {@link ValueNode} represents a {@linkplain Stamp#hasValues() legal} 240 * Object value whose Java type is known exactly. If this method returns true then the 241 * {@linkplain ResolvedJavaType Java type} returned by {@link #typeReferenceOrNull(ValueNode)} 242 * is the concrete dynamic/runtime Java type of this value. 243 * 244 * @param node the node to check 245 * @return true if this node represents a legal object value whose Java type is known exactly 246 */ isExactType(ValueNode node)247 public static boolean isExactType(ValueNode node) { 248 return isExactType(node.stamp(NodeView.DEFAULT)); 249 } 250 251 /** 252 * Checks whether this {@link Stamp} represents a {@linkplain Stamp#hasValues() legal} Object 253 * stamp whose {@linkplain ResolvedJavaType Java type} is known exactly. If this method returns 254 * true then the Java type returned by {@link #typeReferenceOrNull(Stamp)} is the only concrete 255 * dynamic/runtime Java type possible for values of this stamp. 256 * 257 * @param stamp the stamp to check 258 * @return true if this node represents a legal object stamp whose Java type is known exactly 259 */ isExactType(Stamp stamp)260 public static boolean isExactType(Stamp stamp) { 261 if (stamp instanceof AbstractObjectStamp && stamp.hasValues()) { 262 return ((AbstractObjectStamp) stamp).isExactType(); 263 } 264 return false; 265 } 266 } 267