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