# HG changeset patch # User Lukas Stadler # Date 1331744133 -3600 # Node ID 77aa8141ba416983b9eb8f27bd7cf46ccfbc83b1 # Parent 1093243c09ad44f3581618078a4de34a3b90f92e experimental type storage/query infrastructure, part 4: type cache, stamp changes diff -r 1093243c09ad -r 77aa8141ba41 graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/types/NegateObjectTypeFeedback.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/types/NegateObjectTypeFeedback.java Wed Mar 14 17:55:33 2012 +0100 @@ -0,0 +1,70 @@ +/* + * Copyright (c) 2012, 2012, 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 com.oracle.graal.compiler.types; + +import com.oracle.max.cri.ci.*; +import com.oracle.max.cri.ri.*; +import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.calc.*; +import com.oracle.graal.nodes.spi.types.*; + + +public class NegateObjectTypeFeedback implements ObjectTypeFeedbackTool { + + private final ObjectTypeFeedbackTool delegate; + + public NegateObjectTypeFeedback(ObjectTypeFeedbackTool delegate) { + this.delegate = delegate; + } + + @Override + public void constantBound(Condition condition, CiConstant constant) { + delegate.constantBound(condition.negate(), constant); + } + + @Override + public void valueBound(Condition condition, ValueNode otherValue) { + delegate.valueBound(condition.negate(), otherValue); + } + + @Override + public void declaredType(RiResolvedType type, boolean nonNull) { + delegate.notDeclaredType(type, nonNull); + } + + @Override + public void exactType(RiResolvedType type) { + delegate.notExactType(type); + } + + @Override + public void notDeclaredType(RiResolvedType type, boolean includesNull) { + delegate.declaredType(type, includesNull); + } + + @Override + public void notExactType(RiResolvedType type) { + delegate.exactType(type); + } + +} diff -r 1093243c09ad -r 77aa8141ba41 graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/types/NegateScalarTypeFeedback.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/types/NegateScalarTypeFeedback.java Wed Mar 14 17:55:33 2012 +0100 @@ -0,0 +1,53 @@ +/* + * Copyright (c) 2012, 2012, 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 com.oracle.graal.compiler.types; + +import com.oracle.max.cri.ci.*; +import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.calc.*; +import com.oracle.graal.nodes.spi.types.*; + + +public class NegateScalarTypeFeedback implements ScalarTypeFeedbackTool { + + private final ScalarTypeFeedbackTool delegate; + + public NegateScalarTypeFeedback(ScalarTypeFeedbackTool delegate) { + this.delegate = delegate; + } + + @Override + public void constantBound(Condition condition, CiConstant constant) { + delegate.constantBound(condition.negate(), constant); + } + + @Override + public void valueBound(Condition condition, ValueNode otherValue, ScalarTypeQuery type) { + delegate.valueBound(condition.negate(), otherValue, type); + } + + @Override + public void setTranslated(CiConstant delta, ScalarTypeQuery old) { + throw new UnsupportedOperationException(); + } +} diff -r 1093243c09ad -r 77aa8141ba41 graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/types/TypeFeedbackCache.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/types/TypeFeedbackCache.java Wed Mar 14 17:55:33 2012 +0100 @@ -0,0 +1,239 @@ +/* + * Copyright (c) 2012, 2012, 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 com.oracle.graal.compiler.types; + +import java.util.*; +import java.util.Map.Entry; + +import com.oracle.max.cri.ci.*; +import com.oracle.max.cri.ri.*; +import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.spi.types.*; +import com.oracle.graal.nodes.type.*; + +public class TypeFeedbackCache implements TypeFeedbackTool, Cloneable { + + public static final boolean NO_OBJECT_TYPES = false; + public static final boolean NO_SCALAR_TYPES = false; + + private final RiRuntime runtime; + private final StructuredGraph graph; + private final HashMap scalarTypeFeedback; + private final HashMap objectTypeFeedback; + private final TypeFeedbackChanged changed; + private final boolean negated; + + public TypeFeedbackCache(RiRuntime runtime, StructuredGraph graph, TypeFeedbackChanged changed) { + this.runtime = runtime; + this.graph = graph; + scalarTypeFeedback = new HashMap<>(); + objectTypeFeedback = new HashMap<>(); + negated = false; + this.changed = changed; + } + + public TypeFeedbackCache(RiRuntime runtime, StructuredGraph graph, HashMap scalarTypeFeedback, HashMap objectTypeFeedback, boolean negated, TypeFeedbackChanged changed) { + this.runtime = runtime; + this.graph = graph; + this.scalarTypeFeedback = scalarTypeFeedback; + this.objectTypeFeedback = objectTypeFeedback; + this.negated = negated; + this.changed = changed; + } + + @Override + public ScalarTypeFeedbackTool addScalar(ValueNode value) { + assert value.kind() == CiKind.Int || value.kind() == CiKind.Long || value.kind() == CiKind.Float || value.kind() == CiKind.Double; + ScalarTypeFeedbackStore result = scalarTypeFeedback.get(value); + if (result == null) { + if (value.stamp().scalarType() != null) { + result = value.stamp().scalarType().store().clone(); + } else { + result = new ScalarTypeFeedbackStore(value.kind(), changed); + } + scalarTypeFeedback.put(value, result); + } + return negated ? new NegateScalarTypeFeedback(result) : result; + } + + @Override + public ObjectTypeFeedbackTool addObject(ValueNode value) { + assert value.kind() == CiKind.Object; + ObjectTypeFeedbackStore result = objectTypeFeedback.get(value); + if (result == null) { + if (value.stamp().objectType() != null) { + result = value.stamp().objectType().store().clone(); + } else { + result = new ObjectTypeFeedbackStore(changed); + } + objectTypeFeedback.put(value, result); + } + return negated ? new NegateObjectTypeFeedback(result) : result; + } + + @Override + public TypeFeedbackTool negate() { + return new TypeFeedbackCache(runtime, graph, scalarTypeFeedback, objectTypeFeedback, !negated, changed); + } + + @Override + public RiRuntime runtime() { + return runtime; + } + + @Override + public TypeFeedbackCache clone() { + return new TypeFeedbackCache(runtime, graph, deepClone(scalarTypeFeedback), deepClone(objectTypeFeedback), negated, changed); + } + + @SuppressWarnings("unchecked") + private static HashMap deepClone(HashMap map) { + HashMap result = new HashMap<>(); + for (Map.Entry entry : map.entrySet()) { + if (entry.getValue() == null) { + System.out.println(entry.getKey()); + } else { + result.put(entry.getKey(), (ValueT) entry.getValue().clone()); + } + } + return result; + } + + @Override + public String toString() { + StringBuilder str = new StringBuilder().append("types [\n"); + for (Map.Entry entry : scalarTypeFeedback.entrySet()) { + if (!entry.getValue().isEmpty()) { + str.append(" ").append(entry.getKey()).append(": ").append(entry.getValue()).append("\n"); + } + } + for (Map.Entry entry : objectTypeFeedback.entrySet()) { + if (!entry.getValue().isEmpty()) { + str.append(" ").append(entry.getKey()).append(": ").append(entry.getValue()).append("\n"); + } + } + str.setLength(str.length() - 1); + return str.append(" ]").toString(); + } + + public static TypeFeedbackCache meet(TypeFeedbackCache[] cacheList, Iterable phis) { + TypeFeedbackCache result = new TypeFeedbackCache(cacheList[0].runtime, cacheList[0].graph, cacheList[0].changed); + + for (int i = 1; i < cacheList.length; i++) { + assert result.runtime == cacheList[i].runtime; + assert !result.negated && !cacheList[i].negated : "cannot meet negated type feedback caches"; + } + + // meet the scalar types + for (Entry entry : cacheList[0].scalarTypeFeedback.entrySet()) { + ScalarTypeFeedbackStore[] types = new ScalarTypeFeedbackStore[cacheList.length]; + for (int i = 0; i < cacheList.length; i++) { + types[i] = cacheList[i].scalarTypeFeedback.get(entry.getKey()); + } + ScalarTypeFeedbackStore scalar = ScalarTypeFeedbackStore.meet(types); + if (scalar != null && !scalar.isEmpty()) { + result.scalarTypeFeedback.put(entry.getKey(), scalar); + } + } + // meet the object types + for (Entry entry : cacheList[0].objectTypeFeedback.entrySet()) { + ObjectTypeFeedbackStore[] types = new ObjectTypeFeedbackStore[cacheList.length]; + for (int i = 0; i < cacheList.length; i++) { + types[i] = cacheList[i].objectTypeFeedback.get(entry.getKey()); + } + ObjectTypeFeedbackStore object = ObjectTypeFeedbackStore.meet(types); + if (object != null && !object.isEmpty()) { + result.objectTypeFeedback.put(entry.getKey(), object); + } + } + // meet the phi nodes + for (PhiNode phi : phis) { + assert phi.valueCount() == cacheList.length; + if (phi.kind() == CiKind.Int || phi.kind() == CiKind.Long) { + ScalarTypeFeedbackStore[] types = new ScalarTypeFeedbackStore[phi.valueCount()]; + for (int i = 0; i < phi.valueCount(); i++) { + ScalarTypeFeedbackStore other = cacheList[i].scalarTypeFeedback.get(phi.valueAt(i)); + if (other == null && phi.valueAt(i).stamp().scalarType() != null) { + other = phi.valueAt(i).stamp().scalarType().store(); + } + types[i] = other; + } + ScalarTypeFeedbackStore scalar = ScalarTypeFeedbackStore.meet(types); + if (scalar != null && !scalar.isEmpty()) { + result.scalarTypeFeedback.put(phi, scalar); + phi.setStamp(StampFactory.forKind(phi.kind(), scalar.query(), null)); + } + } else if (phi.kind() == CiKind.Object) { + ObjectTypeFeedbackStore[] types = new ObjectTypeFeedbackStore[phi.valueCount()]; + for (int i = 0; i < phi.valueCount(); i++) { + ObjectTypeFeedbackStore other = cacheList[i].objectTypeFeedback.get(phi.valueAt(i)); + if (other == null && phi.valueAt(i).stamp().objectType() != null) { + other = phi.valueAt(i).stamp().objectType().store(); + } + types[i] = other; + } + ObjectTypeFeedbackStore object = ObjectTypeFeedbackStore.meet(types); + if (object != null && !object.isEmpty()) { + result.objectTypeFeedback.put(phi, object); + phi.setStamp(StampFactory.forKind(phi.kind(), null, object.query())); + } + } + } + return result; + } + + @Override + public ScalarTypeQuery queryScalar(ValueNode value) { + assert value.kind() == CiKind.Int || value.kind() == CiKind.Long || value.kind() == CiKind.Float || value.kind() == CiKind.Double; + if (NO_SCALAR_TYPES) { + return new ScalarTypeFeedbackStore(value.kind(), changed).query(); + } + ScalarTypeFeedbackStore result = scalarTypeFeedback.get(value); + if (result == null) { + if (value.stamp().scalarType() != null) { + return value.stamp().scalarType(); + } + result = new ScalarTypeFeedbackStore(value.kind(), changed); + scalarTypeFeedback.put(value, result); + } + return result.query(); + } + + @Override + public ObjectTypeQuery queryObject(ValueNode value) { + assert value != null; + assert value.kind() == CiKind.Object; + if (NO_OBJECT_TYPES) { + return new ObjectTypeFeedbackStore(changed).query(); + } + ObjectTypeFeedbackStore result = objectTypeFeedback.get(value); + if (result == null) { + if (value.stamp().objectType() != null) { + return value.stamp().objectType(); + } + result = new ObjectTypeFeedbackStore(changed); + objectTypeFeedback.put(value, result); + } + return result.query(); + } +} diff -r 1093243c09ad -r 77aa8141ba41 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/type/Stamp.java --- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/type/Stamp.java Wed Mar 14 17:50:59 2012 +0100 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/type/Stamp.java Wed Mar 14 17:55:33 2012 +0100 @@ -24,6 +24,7 @@ import com.oracle.max.cri.ci.*; import com.oracle.max.cri.ri.*; +import com.oracle.graal.nodes.spi.types.*; public interface Stamp { @@ -32,4 +33,7 @@ RiResolvedType exactType(); CiKind kind(); boolean alwaysDistinct(Stamp other); + + ScalarTypeQuery scalarType(); + ObjectTypeQuery objectType(); } diff -r 1093243c09ad -r 77aa8141ba41 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/type/StampFactory.java --- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/type/StampFactory.java Wed Mar 14 17:50:59 2012 +0100 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/type/StampFactory.java Wed Mar 14 17:55:33 2012 +0100 @@ -26,6 +26,9 @@ import com.oracle.max.cri.ci.*; import com.oracle.max.cri.ri.*; +import com.oracle.graal.graph.*; +import com.oracle.graal.nodes.calc.*; +import com.oracle.graal.nodes.spi.types.*; public class StampFactory { @@ -36,16 +39,24 @@ private final boolean nonNull; private RiResolvedType declaredType; private RiResolvedType exactType; + private final ScalarTypeQuery scalarType; + private final ObjectTypeQuery objectType; public BasicValueStamp(CiKind kind) { this(kind, false, null, null); } public BasicValueStamp(CiKind kind, boolean nonNull, RiResolvedType declaredType, RiResolvedType exactType) { + this(kind, nonNull, declaredType, exactType, null, null); + } + + public BasicValueStamp(CiKind kind, boolean nonNull, RiResolvedType declaredType, RiResolvedType exactType, ScalarTypeQuery scalarType, ObjectTypeQuery objectType) { this.kind = kind; this.nonNull = nonNull; this.declaredType = declaredType; this.exactType = exactType; + this.scalarType = scalarType; + this.objectType = objectType; } @Override @@ -87,7 +98,18 @@ @Override public String toString() { - return String.format("%c%s %s %s", kind().typeChar, nonNull ? "!" : "", declaredType == null ? "-" : declaredType.name(), exactType == null ? "-" : exactType.name()); + StringBuilder str = new StringBuilder(); + str.append(kind().typeChar); + if (nonNull || declaredType != null || exactType != null) { + str.append(nonNull ? "!" : "").append(' ').append(declaredType == null ? "-" : declaredType.name()).append(' ').append(exactType == null ? "-" : exactType.name()); + } + if (scalarType != null) { + str.append(' ').append(scalarType); + } + if (objectType != null) { + str.append(' ').append(objectType); + } + return str.toString(); } @Override @@ -107,6 +129,16 @@ return false; } } + + @Override + public ScalarTypeQuery scalarType() { + return scalarType; + } + + @Override + public ObjectTypeQuery objectType() { + return objectType; + } } private static final Stamp[] stampCache = new Stamp[CiKind.values().length]; @@ -128,17 +160,68 @@ return stampCache[kind.stackKind().ordinal()]; } + public static Stamp forKind(CiKind kind, ScalarTypeQuery scalarTypeFeedback, ObjectTypeQuery objectTypeFeedback) { + if (scalarTypeFeedback == null && objectTypeFeedback == null) { + return forKind(kind); + } else { + return new BasicValueStamp(kind, false, null, null, scalarTypeFeedback, objectTypeFeedback); + } + } + + public static final Stamp positiveInt = forInt(0, Integer.MAX_VALUE); + + public static Stamp positiveInt() { + return positiveInt; + } + + public static Stamp forInt(int lowerBound, int upperBound) { + ScalarTypeFeedbackStore scalarType = new ScalarTypeFeedbackStore(CiKind.Int, new TypeFeedbackChanged()); + scalarType.constantBound(Condition.GE, CiConstant.forInt(lowerBound)); + scalarType.constantBound(Condition.LE, CiConstant.forInt(upperBound)); + + return new BasicValueStamp(CiKind.Int, false, null, null, scalarType.query(), null); + } + + public static Stamp forLong(long lowerBound, long upperBound) { + ScalarTypeFeedbackStore scalarType = new ScalarTypeFeedbackStore(CiKind.Long, new TypeFeedbackChanged()); + scalarType.constantBound(Condition.GE, CiConstant.forLong(lowerBound)); + scalarType.constantBound(Condition.LE, CiConstant.forLong(upperBound)); + + return new BasicValueStamp(CiKind.Long, false, null, null, scalarType.query(), null); + } + public static Stamp exactNonNull(final RiResolvedType type) { // (cwimmer) type can be null for certain Maxine-internal objects such as the static hub. Is this a problem here? assert type == null || type.kind(false) == CiKind.Object; - return new BasicValueStamp(CiKind.Object, true, type, type); + ObjectTypeFeedbackStore objectType = new ObjectTypeFeedbackStore(new TypeFeedbackChanged()); + objectType.constantBound(Condition.NE, CiConstant.NULL_OBJECT); + objectType.exactType(type); + return new BasicValueStamp(CiKind.Object, true, type, type, null, objectType.query()); + } + + public static Stamp forConstant(CiConstant value) { + assert value.kind != CiKind.Object; + if (value.kind == CiKind.Object) { + throw new GraalInternalError("unexpected kind: %s", value.kind); + } else { + if (value.kind == CiKind.Int) { + return forInt(value.asInt(), value.asInt()); + } else if (value.kind == CiKind.Long) { + return forLong(value.asLong(), value.asLong()); + } + return forKind(value.kind.stackKind()); + } } public static Stamp forConstant(CiConstant value, RiRuntime runtime) { - if (runtime != null && value.kind == CiKind.Object && !value.isNull()) { - return exactNonNull(runtime.getTypeOf(value)); + assert value.kind == CiKind.Object; + if (value.kind == CiKind.Object) { + ObjectTypeFeedbackStore objectType = new ObjectTypeFeedbackStore(new TypeFeedbackChanged()); + objectType.constantBound(Condition.EQ, value); + RiResolvedType type = value.isNull() ? null : runtime.getTypeOf(value); + return new BasicValueStamp(CiKind.Object, value.isNonNull(), type, type, null, objectType.query()); } else { - return forKind(value.kind.stackKind()); + throw new GraalInternalError("CiKind.Object expected, actual kind: %s", value.kind); } }