1 /* 2 * Copyright (c) 2012, 2019, 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 int bits = valueStamp.getBits(); 125 long mask = CodeUtil.mask(bits); 126 int min = Math.min(Long.numberOfTrailingZeros(valueStamp.upMask() & mask), bits); 127 int max = Math.min(Long.numberOfTrailingZeros(valueStamp.downMask() & mask), bits); 128 return StampFactory.forInteger(JavaKind.Int, min, max); 129 } 130 131 /** 132 * Checks whether this {@link ValueNode} represents a {@linkplain Stamp#hasValues() legal} 133 * pointer value which is known to be always null. 134 * 135 * @param node the node to check 136 * @return true if this node represents a legal object value which is known to be always null 137 */ isPointerAlwaysNull(ValueNode node)138 public static boolean isPointerAlwaysNull(ValueNode node) { 139 return isPointerAlwaysNull(node.stamp(NodeView.DEFAULT)); 140 } 141 142 /** 143 * Checks whether this {@link Stamp} represents a {@linkplain Stamp#hasValues() legal} pointer 144 * stamp whose values are known to be always null. 145 * 146 * @param stamp the stamp to check 147 * @return true if this stamp represents a legal object stamp whose values are known to be 148 * always null 149 */ isPointerAlwaysNull(Stamp stamp)150 public static boolean isPointerAlwaysNull(Stamp stamp) { 151 if (stamp instanceof AbstractPointerStamp && stamp.hasValues()) { 152 return ((AbstractPointerStamp) stamp).alwaysNull(); 153 } 154 return false; 155 } 156 157 /** 158 * Checks whether this {@link ValueNode} represents a {@linkplain Stamp#hasValues() legal} 159 * pointer value which is known to never be null. 160 * 161 * @param node the node to check 162 * @return true if this node represents a legal object value which is known to never be null 163 */ isPointerNonNull(ValueNode node)164 public static boolean isPointerNonNull(ValueNode node) { 165 return isPointerNonNull(node.stamp(NodeView.DEFAULT)); 166 } 167 168 /** 169 * Checks whether this {@link Stamp} represents a {@linkplain Stamp#hasValues() legal} pointer 170 * stamp whose values are known to never be null. 171 * 172 * @param stamp the stamp to check 173 * @return true if this stamp represents a legal object stamp whose values are known to be 174 * always null 175 */ isPointerNonNull(Stamp stamp)176 public static boolean isPointerNonNull(Stamp stamp) { 177 if (stamp instanceof AbstractPointerStamp) { 178 return ((AbstractPointerStamp) stamp).nonNull(); 179 } 180 return false; 181 } 182 183 /** 184 * Returns the {@linkplain ResolvedJavaType Java type} this {@linkplain ValueNode} has if it is 185 * a {@linkplain Stamp#hasValues() legal} Object value. 186 * 187 * @param node the node to check 188 * @return the Java type this value has if it is a legal Object type, null otherwise 189 */ typeReferenceOrNull(ValueNode node)190 public static TypeReference typeReferenceOrNull(ValueNode node) { 191 return typeReferenceOrNull(node.stamp(NodeView.DEFAULT)); 192 } 193 typeOrNull(ValueNode node)194 public static ResolvedJavaType typeOrNull(ValueNode node) { 195 return typeOrNull(node.stamp(NodeView.DEFAULT)); 196 } 197 typeOrNull(Stamp stamp)198 public static ResolvedJavaType typeOrNull(Stamp stamp) { 199 TypeReference type = typeReferenceOrNull(stamp); 200 return type == null ? null : type.getType(); 201 } 202 typeOrNull(Stamp stamp, MetaAccessProvider metaAccess)203 public static ResolvedJavaType typeOrNull(Stamp stamp, MetaAccessProvider metaAccess) { 204 if (stamp instanceof AbstractObjectStamp && stamp.hasValues()) { 205 AbstractObjectStamp abstractObjectStamp = (AbstractObjectStamp) stamp; 206 ResolvedJavaType type = abstractObjectStamp.type(); 207 if (type == null) { 208 return metaAccess.lookupJavaType(Object.class); 209 } else { 210 return type; 211 } 212 } 213 return null; 214 } 215 typeOrNull(ValueNode node, MetaAccessProvider metaAccess)216 public static ResolvedJavaType typeOrNull(ValueNode node, MetaAccessProvider metaAccess) { 217 return typeOrNull(node.stamp(NodeView.DEFAULT), metaAccess); 218 } 219 220 /** 221 * Returns the {@linkplain ResolvedJavaType Java type} this {@linkplain Stamp} has if it is a 222 * {@linkplain Stamp#hasValues() legal} Object stamp. 223 * 224 * @param stamp the stamp to check 225 * @return the Java type this stamp has if it is a legal Object stamp, null otherwise 226 */ typeReferenceOrNull(Stamp stamp)227 public static TypeReference typeReferenceOrNull(Stamp stamp) { 228 if (stamp instanceof AbstractObjectStamp && stamp.hasValues()) { 229 AbstractObjectStamp abstractObjectStamp = (AbstractObjectStamp) stamp; 230 if (abstractObjectStamp.isExactType()) { 231 return TypeReference.createExactTrusted(abstractObjectStamp.type()); 232 } else { 233 return TypeReference.createTrustedWithoutAssumptions(abstractObjectStamp.type()); 234 } 235 } 236 return null; 237 } 238 239 /** 240 * Checks whether this {@link ValueNode} represents a {@linkplain Stamp#hasValues() legal} 241 * Object value whose Java type is known exactly. If this method returns true then the 242 * {@linkplain ResolvedJavaType Java type} returned by {@link #typeReferenceOrNull(ValueNode)} 243 * is the concrete dynamic/runtime Java type of this value. 244 * 245 * @param node the node to check 246 * @return true if this node represents a legal object value whose Java type is known exactly 247 */ isExactType(ValueNode node)248 public static boolean isExactType(ValueNode node) { 249 return isExactType(node.stamp(NodeView.DEFAULT)); 250 } 251 252 /** 253 * Checks whether this {@link Stamp} represents a {@linkplain Stamp#hasValues() legal} Object 254 * stamp whose {@linkplain ResolvedJavaType Java type} is known exactly. If this method returns 255 * true then the Java type returned by {@link #typeReferenceOrNull(Stamp)} is the only concrete 256 * dynamic/runtime Java type possible for values of this stamp. 257 * 258 * @param stamp the stamp to check 259 * @return true if this node represents a legal object stamp whose Java type is known exactly 260 */ isExactType(Stamp stamp)261 public static boolean isExactType(Stamp stamp) { 262 if (stamp instanceof AbstractObjectStamp && stamp.hasValues()) { 263 return ((AbstractObjectStamp) stamp).isExactType(); 264 } 265 return false; 266 } 267 } 268