Mercurial > hg > truffle
changeset 5081:3e21269ee901
experimental type storage/query infrastructure, part 1
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/spi/types/CloneableTypeFeedback.java Wed Mar 14 17:42:41 2012 +0100 @@ -0,0 +1,28 @@ +/* + * 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.nodes.spi.types; + +public interface CloneableTypeFeedback { + + Object clone(); +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/spi/types/ObjectTypeFeedbackStore.java Wed Mar 14 17:42:41 2012 +0100 @@ -0,0 +1,773 @@ +/* + * 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.nodes.spi.types; + +import java.util.*; + +import com.oracle.max.cri.ci.*; +import com.oracle.max.cri.ri.*; +import com.oracle.graal.graph.*; +import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.calc.*; + +public class ObjectTypeFeedbackStore extends TypeFeedbackStore<ObjectTypeFeedbackStore> implements ObjectTypeFeedbackTool, CloneableTypeFeedback { + + private abstract static class BooleanPredicate <T> { + public abstract boolean evaluate(T element); + } + + public static class Query implements ObjectTypeQuery { + + private final ObjectTypeFeedbackStore store; + + public Query(ObjectTypeFeedbackStore store) { + this.store = store; + } + + @Override + public boolean constantBound(Condition condition, final CiConstant constant) { + assert condition == Condition.EQ || condition == Condition.NE; + if (condition == Condition.EQ) { + return store.prove(Equals.class, new BooleanPredicate<Equals>() { + @Override + public boolean evaluate(Equals element) { + return element.constant.equals(constant); + } + }); + } else if (condition == Condition.NE) { + boolean result = store.prove(Equals.class, new BooleanPredicate<Equals>() { + @Override + public boolean evaluate(Equals element) { + return !element.constant.equals(constant); + } + }); + if (result) { + return true; + } + return store.prove(NotEquals.class, new BooleanPredicate<NotEquals>() { + @Override + public boolean evaluate(NotEquals element) { + return element.constant.equals(constant); + } + }); + } + return false; + } + + @Override + public boolean valueBound(Condition condition, ValueNode otherValue) { + Condition cond = store.valueBounds == null ? null : store.valueBounds.get(otherValue); + if (cond == null) { + return false; + } else { + return cond.implies(condition); + } + } + + @Override + public boolean declaredType(final RiResolvedType type) { + return store.prove(Info.class, new BooleanPredicate<Info>() { + @Override + public boolean evaluate(Info element) { + if (element instanceof ObjectType) { + return ((ObjectType) element).type.isSubtypeOf(type); + } else { + return (element instanceof Equals) && ((Equals) element).constant.isNull(); + } + } + }); + } + + @Override + public boolean exactType(final RiResolvedType type) { + return store.prove(ObjectTypeExact.class, new BooleanPredicate<ObjectTypeExact>() { + @Override + public boolean evaluate(ObjectTypeExact element) { + return type == element.type; + } + }); + } + + @Override + public boolean notDeclaredType(RiResolvedType type) { + return false; + } + + @Override + public boolean notExactType(RiResolvedType type) { + return false; + } + + @Override + public String toString() { + return store.toString(); + } + + @Override + public ObjectTypeFeedbackStore store() { + return store; + } + + @Override + public Node dependency() { + return store.dependency; + } + } + + private static final Info[] EMPTY_INFO_ARRAY = new Info[0]; + + private static class Info { + + } + + private static final class Equals extends Info { + public final CiConstant constant; + + public Equals(CiConstant constant) { + this.constant = constant; + } + + @Override + public String toString() { + return "== " + constant.asObject(); + } + } + + private static final class NotEquals extends Info { + public final CiConstant constant; + + public NotEquals(CiConstant constant) { + this.constant = constant; + } + + @Override + public String toString() { + return "!= " + constant.asObject(); + } + } + + private static class ObjectType extends Info { + public final RiResolvedType type; + + public ObjectType(RiResolvedType type) { + this.type = type; + } + } + + private static final class ObjectTypeDeclared extends ObjectType { + + public ObjectTypeDeclared(RiResolvedType type) { + super(type); + } + + @Override + public String toString() { + return "instanceof " + type; + } + } + + private static final class ObjectTypeExact extends ObjectType { + + public ObjectTypeExact(RiResolvedType type) { + super(type); + } + + @Override + public String toString() { + return "exact " + type; + } + } + + private static final class MergedTypeInfo extends Info { + public final Info[][] mergedInfos; + + public MergedTypeInfo(Info[][] infos) { + mergedInfos = infos; + } + + @Override + public String toString() { + return "merged type: [" + Arrays.deepToString(mergedInfos) + "]"; + } + } + + private final LinkedList<Info> infos = new LinkedList<>(); + private HashMap<ValueNode, Condition> valueBounds; + + private final TypeFeedbackChanged changed; + + private Node dependency; + + private void updateDependency() { + dependency = changed.node; + } + + private static <T extends Info> boolean prove(Info[] infos, Class<T> clazz, IdentityHashMap<MergedTypeInfo, Boolean> cache, BooleanPredicate<T> predicate) { + for (Info info : infos) { + if (clazz.isAssignableFrom(info.getClass())) { + if (predicate.evaluate(clazz.cast(info))) { + return true; + } + } + if (info instanceof MergedTypeInfo) { + if (cache.get(info) != null) { + return cache.get(info); + } + for (Info[] subInfos : ((MergedTypeInfo) info).mergedInfos) { + if (!prove(subInfos, clazz, cache, predicate)) { + cache.put((MergedTypeInfo) info, false); + return false; + } + } + cache.put((MergedTypeInfo) info, true); + return true; + } + } + return false; + } + + public <T extends Info> boolean prove(Class<T> clazz, BooleanPredicate<T> predicate) { + for (Info info : infos) { + if (clazz.isAssignableFrom(info.getClass())) { + if (predicate.evaluate(clazz.cast(info))) { + return true; + } + } + if (info instanceof MergedTypeInfo) { + IdentityHashMap<MergedTypeInfo, Boolean> cache = new IdentityHashMap<>(); + for (Info[] subInfos : ((MergedTypeInfo) info).mergedInfos) { + if (!prove(subInfos, clazz, cache, predicate)) { + return false; + } + } + return true; + } + } + return false; + } + + public ObjectTypeFeedbackStore(TypeFeedbackChanged changed) { + this.changed = changed; + this.dependency = null; + } + + private ObjectTypeFeedbackStore(ObjectTypeFeedbackStore other) { + this.changed = other.changed; + if (other.valueBounds != null && !other.valueBounds.isEmpty()) { + valueBounds = new HashMap<>(other.valueBounds.size()); + valueBounds.putAll(other.valueBounds); + } + infos.addAll(other.infos); + this.dependency = other.dependency; + } + + @Override + public void constantBound(Condition condition, CiConstant constant) { + assert condition == Condition.EQ || condition == Condition.NE; + + if (condition == Condition.EQ) { + if (infos.size() == 1 && infos.element() instanceof Equals && ((Equals) infos.element()).constant.equals(constant)) { + return; + } + infos.clear(); + infos.add(new Equals(constant)); + updateDependency(); + } else if (condition == Condition.NE) { + for (ListIterator<Info> iter = infos.listIterator(); iter.hasNext();) { + int index = iter.nextIndex(); + Info info = iter.next(); + if (info instanceof NotEquals && ((NotEquals) info).constant.equals(constant)) { + if (index == 0) { + return; + } else { + iter.remove(); + } + } + } + infos.add(new NotEquals(constant)); + updateDependency(); + } else { + throw new GraalInternalError("unexpected condition: %s", condition); + } + } + + @Override + public void valueBound(Condition condition, ValueNode otherValue) { + assert condition == Condition.EQ || condition == Condition.NE; + + if (otherValue != null) { + if (valueBounds == null) { + valueBounds = new HashMap<>(); + } + Condition cond = valueBounds.get(otherValue); + if (cond == null) { + valueBounds.put(otherValue, condition); + updateDependency(); + } else { + Condition newCondition = cond.join(condition); + if (newCondition == null) { + valueBounds.remove(otherValue); + } else { + if (cond != newCondition) { + valueBounds.put(otherValue, newCondition); + updateDependency(); + } + } + } + } + } + + @Override + public void declaredType(RiResolvedType type, boolean nonNull) { + assert type != null; + + for (ListIterator<Info> iter = infos.listIterator(); iter.hasNext();) { + int index = iter.nextIndex(); + Info info = iter.next(); + if (info instanceof ObjectTypeDeclared) { + ObjectTypeDeclared typeInfo = (ObjectTypeDeclared) info; + if (typeInfo.type == type && index == 0) { + if (index == 0) { + if (nonNull) { + constantBound(Condition.NE, CiConstant.NULL_OBJECT); + } + return; + } else { + iter.remove(); + } + } + } + } + infos.add(new ObjectTypeDeclared(type)); + updateDependency(); + if (nonNull) { + constantBound(Condition.NE, CiConstant.NULL_OBJECT); + } + } + + @Override + public void exactType(RiResolvedType type) { + assert type != null; + + for (ListIterator<Info> iter = infos.listIterator(); iter.hasNext();) { + int index = iter.nextIndex(); + Info info = iter.next(); + if (info instanceof ObjectTypeExact) { + ObjectTypeExact typeInfo = (ObjectTypeExact) info; + if (typeInfo.type == type && index == 0) { + if (index == 0) { + constantBound(Condition.NE, CiConstant.NULL_OBJECT); + return; + } else { + iter.remove(); + } + } + } + } + infos.add(new ObjectTypeExact(type)); + updateDependency(); + constantBound(Condition.NE, CiConstant.NULL_OBJECT); + } + + @Override + public void notDeclaredType(RiResolvedType type, boolean includesNull) { + } + + @Override + public void notExactType(RiResolvedType type) { + } + + public static ObjectTypeFeedbackStore meet(ObjectTypeFeedbackStore[] others) { + boolean emptyValueBounds = false; + for (int i = 0; i < others.length; i++) { + if (others[i] == null) { + return null; + } + if (others[i].valueBounds == null || others[i].valueBounds.isEmpty()) { + emptyValueBounds = true; + } + } + + ObjectTypeFeedbackStore first = others[0]; + ObjectTypeFeedbackStore result = new ObjectTypeFeedbackStore(first.changed); + + if (!emptyValueBounds) { + for (Map.Entry<ValueNode, Condition> entry : first.valueBounds.entrySet()) { + Condition condition = entry.getValue(); + for (int i = 1; i < others.length; i++) { + Condition otherCond = others[i].valueBounds.get(entry.getKey()); + if (otherCond != null) { + condition = null; + break; + } + condition = condition.meet(otherCond); + if (condition == null) { + break; + } + } + if (condition != null) { + if (result.valueBounds == null) { + result.valueBounds = new HashMap<>(first.valueBounds.size()); + } + result.valueBounds.put(entry.getKey(), condition); + } + } + } + + boolean simpleMerge = true; + for (int i = 1; i < others.length; i++) { + if (!others[i].infos.equals(others[i - 1].infos)) { + simpleMerge = false; + break; + } + } + if (simpleMerge) { + result.infos.addAll(others[0].infos); + } else { + Info[][] infos = new Info[others.length][]; + for (int i = 0; i < others.length; i++) { + infos[i] = others[i].infos.toArray(EMPTY_INFO_ARRAY); + } + MergedTypeInfo merged = new MergedTypeInfo(infos); + result.infos.add(merged); + } + return result; + } + + @Override + public ObjectTypeFeedbackStore clone() { + return new ObjectTypeFeedbackStore(this); + } + + public ObjectTypeQuery query() { + return new Query(this); + } + + public boolean isEmpty() { + return infos.isEmpty() && (valueBounds == null || valueBounds.isEmpty()); + } + + @Override + public String toString() { + StringBuilder str = new StringBuilder(); + for (Info info : infos) { + str.append(info).append(", "); + } + if (valueBounds != null) { + for (Map.Entry<ValueNode, Condition> entry : valueBounds.entrySet()) { + str.append(entry.getValue().operator).append(' ').append(entry.getKey()).append(", "); + } + } + if (str.length() > 1) { + str.setLength(str.length() - 2); + } + if (dependency != null) { + str.append(" @ ").append(dependency); + } + return str.toString(); + } + + /* +// equals contains all the values that might happen to be in this variable. If it is null then there is no information about possible values. +// If it is empty, then we're currently in a branch that will be removed by canonicalization later on. + private Set<CiConstant> equals; +// notEquals contains all the values that cannot be in this variable. + private Set<CiConstant> notEquals; + + private HashMap<ValueNode, Condition> valueBounds; + + private Set<RiResolvedType> exactTypes; + + private Set<RiResolvedType> declaredTypes; + private final TypeFeedbackChanged changed; + + private Node dependency; + + private void updateDependency() { + dependency = changed.node; + } + + public ObjectTypeFeedbackStore(TypeFeedbackChanged changed) { + this.changed = changed; + this.dependency = null; + } + + private ObjectTypeFeedbackStore(ObjectTypeFeedbackStore other) { + this.changed = other.changed; + if (other.valueBounds != null && !other.valueBounds.isEmpty()) { + valueBounds = new HashMap<>(other.valueBounds.size()); + valueBounds.putAll(other.valueBounds); + } + if (other.equals != null) { + equals = new HashSet<>(other.equals); + } + if (other.notEquals != null && !other.notEquals.isEmpty()) { + notEquals = new HashSet<>(other.notEquals); + } + this.dependency = other.dependency; + } + + @Override + public void constantBound(Condition condition, CiConstant constant) { + assert condition == Condition.EQ || condition == Condition.NE; + + if (condition == Condition.EQ) { + if (equals == null) { + equals = new HashSet<>(); + equals.add(constant); + updateDependency(); + } else { + if (equals.contains(constant)) { + equals.clear(); + equals.add(constant); + updateDependency(); + } else { + // join with a value that cannot exist: we're in a branch that will hopefully be canonicalized away + equals.clear(); + } + } + } else if (condition == Condition.NE) { + if (notEquals == null) { + notEquals = new HashSet<>(); + } + if (equals != null && equals.contains(constant)) { + equals.remove(constant); + } + if (notEquals.add(constant)) { + updateDependency(); + } + } + } + + @Override + public void valueBound(Condition condition, ValueNode otherValue) { + assert condition == Condition.EQ || condition == Condition.NE; + + if (otherValue != null) { + if (valueBounds == null) { + valueBounds = new HashMap<>(); + } + Condition cond = valueBounds.get(otherValue); + if (cond == null) { + valueBounds.put(otherValue, condition); + updateDependency(); + } else { + Condition newCondition = cond.join(condition); + if (newCondition == null) { + valueBounds.remove(otherValue); + } else { + if (cond != newCondition) { + valueBounds.put(otherValue, newCondition); + updateDependency(); + } + } + } + } + } + + @Override + public void declaredType(RiResolvedType type, boolean nonNull) { + if (declaredTypes == null) { + declaredTypes = new HashSet<>(); + declaredTypes.add(type); + updateDependency(); + } else { + if (type.isInterface()) { + for (Iterator<RiResolvedType> iter = declaredTypes.iterator(); iter.hasNext();) { + RiResolvedType declaredType = iter.next(); + if (declaredType.isInterface()) { + if (type.isSubtypeOf(declaredType)) { + iter.remove(); + } else if (declaredType.isSubtypeOf(type)) { + // some more specific type is already in the list - nothing to do + return; + } + } + } + if (declaredTypes.add(type)) { + updateDependency(); + } + } else { + for (Iterator<RiResolvedType> iter = declaredTypes.iterator(); iter.hasNext();) { + RiResolvedType declaredType = iter.next(); + if (!declaredType.isInterface()) { + if (type.isSubtypeOf(declaredType)) { + iter.remove(); + } else if (declaredType.isSubtypeOf(type)) { + // some more specific type is already in the list - nothing to do + return; + } + } + } + if (declaredTypes.add(type)) { + updateDependency(); + } + } + } + if (nonNull) { + constantBound(Condition.NE, CiConstant.NULL_OBJECT); + } + } + + @Override + public void exactType(RiResolvedType type) { + if (exactTypes == null) { + exactTypes = new HashSet<>(); + exactTypes.add(type); + updateDependency(); + } else { + if (exactTypes.contains(type)) { + exactTypes.clear(); + exactTypes.add(type); + updateDependency(); + } else { + // join with a value that cannot exist: we're in a branch that will hopefully be canonicalized away + exactTypes.clear(); + } + } + constantBound(Condition.NE, CiConstant.NULL_OBJECT); + } + + @Override + public void notDeclaredType(RiResolvedType type, boolean nonNull) { + } + + @Override + public void notExactType(RiResolvedType type) { + } + + @Override + public void meet(ObjectTypeFeedbackStore other) { + dependency = null; + if (equals != null && other.equals != null) { + equals.addAll(other.equals); + } else { + equals = null; + } + if (notEquals != null && !notEquals.isEmpty() && other.notEquals != null && !other.notEquals.isEmpty()) { + for (Iterator<CiConstant> iter = notEquals.iterator(); iter.hasNext();) { + CiConstant constant = iter.next(); + if (!other.notEquals.contains(constant)) { + iter.remove(); + } + } + } else { + notEquals = null; + } + if (valueBounds != null && !valueBounds.isEmpty() && other.valueBounds != null && !other.valueBounds.isEmpty()) { + HashMap<ValueNode, Condition> newBounds = new HashMap<>(valueBounds.size()); + for (Map.Entry<ValueNode, Condition> entry : valueBounds.entrySet()) { + Condition otherCond = other.valueBounds.get(entry.getKey()); + if (otherCond != null) { + Condition newCondition = entry.getValue().meet(otherCond); + if (newCondition != null) { + newBounds.put(entry.getKey(), newCondition); + } + } + } + if (newBounds.isEmpty()) { + valueBounds = null; + } else { + valueBounds = newBounds; + } + } else { + valueBounds = null; + } + declaredTypes = null; + exactTypes = null; + } + + @Override + public ObjectTypeFeedbackStore clone() { + return new ObjectTypeFeedbackStore(this); + } + + public ObjectTypeQuery query() { + return new Query(this); + } + + public boolean isEmpty() { + return equals == null && (notEquals == null || notEquals.isEmpty()) && (valueBounds == null || valueBounds.isEmpty()); + } + + @Override + public String toString() { + StringBuilder str = new StringBuilder(); + if (equals != null && !equals.isEmpty()) { + str.append("== "); + if (equals.size() == 1) { + str.append(equals.iterator().next()); + } else { + str.append("("); + for (CiConstant constant : equals) { + str.append(constant).append(','); + } + str.setLength(str.length() - 1); + str.append(')'); + } + str.append(", "); + } + if (notEquals != null && !notEquals.isEmpty()) { + str.append("!= "); + if (notEquals.size() == 1) { + str.append(notEquals.iterator().next()); + } else { + str.append("("); + for (CiConstant constant : notEquals) { + str.append(constant).append(','); + } + str.setLength(str.length() - 1); + str.append(')'); + } + str.append(", "); + } + if (valueBounds != null) { + for (Map.Entry<ValueNode, Condition> entry : valueBounds.entrySet()) { + str.append(entry.getValue().operator).append(' ').append(entry.getKey()).append(", "); + } + } + if (declaredTypes != null) { + str.append("declared ("); + for (RiResolvedType type: declaredTypes) { + str.append(type).append(','); + } + str.setLength(str.length() - 1); + str.append("), "); + } + if (exactTypes != null) { + str.append("exact ("); + for (RiResolvedType type: exactTypes) { + str.append(type).append(','); + } + str.setLength(str.length() - 1); + str.append("), "); + } + if (str.length() > 1) { + str.setLength(str.length() - 2); + } + if (dependency != null) { + str.append(" @ ").append(dependency); + } + return str.toString(); + }*/ +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/spi/types/ObjectTypeFeedbackTool.java Wed Mar 14 17:42:41 2012 +0100 @@ -0,0 +1,43 @@ +/* + * 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.nodes.spi.types; + +import com.oracle.max.cri.ci.*; +import com.oracle.max.cri.ri.*; +import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.calc.*; + +public interface ObjectTypeFeedbackTool { + + void constantBound(Condition condition, CiConstant constant); + + void valueBound(Condition condition, ValueNode otherValue); + + void declaredType(RiResolvedType type, boolean nonNull); + + void exactType(RiResolvedType type); + + void notDeclaredType(RiResolvedType type, boolean includesNull); + + void notExactType(RiResolvedType type); +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/spi/types/ObjectTypeQuery.java Wed Mar 14 17:42:41 2012 +0100 @@ -0,0 +1,45 @@ +/* + * 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.nodes.spi.types; + +import com.oracle.max.cri.ci.*; +import com.oracle.max.cri.ri.*; +import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.calc.*; + +public interface ObjectTypeQuery extends TypeQuery { + + boolean constantBound(Condition condition, CiConstant constant); + + boolean valueBound(Condition condition, ValueNode otherValue); + + boolean declaredType(RiResolvedType type); + + boolean exactType(RiResolvedType type); + + boolean notDeclaredType(RiResolvedType type); + + boolean notExactType(RiResolvedType type); + + ObjectTypeFeedbackStore store(); +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/spi/types/ScalarTypeFeedbackStore.java Wed Mar 14 17:42:41 2012 +0100 @@ -0,0 +1,409 @@ +/* + * 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.nodes.spi.types; + +import java.util.*; + +import com.oracle.graal.nodes.calc.*; +import com.oracle.max.cri.ci.*; +import com.oracle.graal.graph.*; +import com.oracle.graal.nodes.*; + +public class ScalarTypeFeedbackStore extends TypeFeedbackStore<ScalarTypeFeedbackStore> implements ScalarTypeFeedbackTool, CloneableTypeFeedback { + + public static class Query implements ScalarTypeQuery { + + private final ScalarTypeFeedbackStore store; + + public Query(ScalarTypeFeedbackStore store) { + this.store = store; + } + + @Override + public boolean constantBound(Condition condition, CiConstant constant) { + if (constant.kind == CiKind.Int || constant.kind == CiKind.Long) { + switch (condition) { + case EQ: + return store.constantBounds.lowerBound == constant.asLong() && store.constantBounds.upperBound == constant.asLong(); + case NE: + return store.constantBounds.lowerBound > constant.asLong() || store.constantBounds.upperBound < constant.asLong(); + case LT: + return store.constantBounds.upperBound < constant.asLong(); + case LE: + return store.constantBounds.upperBound <= constant.asLong(); + case GT: + return store.constantBounds.lowerBound > constant.asLong(); + case GE: + return store.constantBounds.lowerBound >= constant.asLong(); + case BT: + return constant.asLong() >= 0 && store.constantBounds.upperBound < constant.asLong() && store.constantBounds.lowerBound >= 0; + case BE: + return constant.asLong() >= 0 && store.constantBounds.upperBound <= constant.asLong() && store.constantBounds.lowerBound >= 0; + case AT: + return constant.asLong() < 0 && store.constantBounds.lowerBound > constant.asLong() && store.constantBounds.upperBound < 0; + case AE: + return constant.asLong() < 0 && store.constantBounds.lowerBound >= constant.asLong() && store.constantBounds.upperBound < 0; + } + } + return false; + } + + @Override + public boolean valueBound(Condition condition, ValueNode otherValue) { + Condition cond = store.valueBounds == null ? null : store.valueBounds.get(otherValue); + if (cond == null) { + return false; + } else { + return cond.implies(condition); + } + } + + @Override + public String toString() { + return store.toString(); + } + + @Override + public ScalarTypeFeedbackStore store() { + return store; + } + + @Override + public Node dependency() { + return store.dependency; + } + } + + private static class ConstantBound { + + public long lowerBound; + public long upperBound; + + public ConstantBound(long lowerBound, long upperBound) { + this.lowerBound = lowerBound; + this.upperBound = upperBound; + } + + public void meet(ConstantBound other) { + lowerBound = Math.min(lowerBound, other.lowerBound); + upperBound = Math.max(upperBound, other.upperBound); + } + + public boolean join(ConstantBound other) { + long oldLower = lowerBound; + long oldUpper = upperBound; + lowerBound = Math.max(lowerBound, other.lowerBound); + upperBound = Math.min(upperBound, other.upperBound); + return oldLower != lowerBound || oldUpper != upperBound; + } + } + + private final CiKind kind; + private final ConstantBound constantBounds; + private final TypeFeedbackChanged changed; + private Node dependency; + private HashMap<ValueNode, Condition> valueBounds; + + private void updateDependency() { + dependency = changed.node; + } + + public ScalarTypeFeedbackStore(CiKind kind, TypeFeedbackChanged changed) { + this.kind = kind; + if (kind == CiKind.Int) { + constantBounds = new ConstantBound(Integer.MIN_VALUE, Integer.MAX_VALUE); + } else if (kind == CiKind.Long) { + constantBounds = new ConstantBound(Long.MIN_VALUE, Long.MAX_VALUE); + } else { + constantBounds = null; + } + this.changed = changed; + this.dependency = null; + } + + private ScalarTypeFeedbackStore(ScalarTypeFeedbackStore other) { + this.kind = other.kind; + if (other.constantBounds == null) { + constantBounds = null; + } else { + constantBounds = new ConstantBound(other.constantBounds.lowerBound, other.constantBounds.upperBound); + } + if (other.valueBounds != null && !other.valueBounds.isEmpty()) { + valueBounds = new HashMap<>(other.valueBounds.size()); + valueBounds.putAll(other.valueBounds); + } + this.changed = other.changed; + this.dependency = other.dependency; + } + + @Override + public void constantBound(Condition condition, CiConstant constant) { + ConstantBound newBound = createBounds(condition, constant); + if (newBound != null) { + if (constantBounds.join(newBound)) { + updateDependency(); + } + } + } + + private static ConstantBound createBounds(Condition condition, CiConstant constant) { + ConstantBound newBound; + if (constant.kind == CiKind.Int || constant.kind == CiKind.Long) { + switch (condition) { + case EQ: + newBound = new ConstantBound(constant.asLong(), constant.asLong()); + break; + case NE: + newBound = null; + break; + case GT: + newBound = new ConstantBound(constant.asLong() + 1, Long.MAX_VALUE); + break; + case GE: + newBound = new ConstantBound(constant.asLong(), Long.MAX_VALUE); + break; + case LT: + newBound = new ConstantBound(Long.MIN_VALUE, constant.asLong() - 1); + break; + case LE: + newBound = new ConstantBound(Long.MIN_VALUE, constant.asLong()); + break; + default: + newBound = null; + break; + } + } else { + newBound = null; + } + return newBound; + } + + private void simpleValueBound(Condition condition, ValueNode otherValue) { + if (otherValue != null) { + if (valueBounds == null) { + valueBounds = new HashMap<>(); + } + Condition cond = valueBounds.get(otherValue); + if (cond == null) { + valueBounds.put(otherValue, condition); + updateDependency(); + } else { + Condition newCondition = cond.join(condition); + if (newCondition == null) { + valueBounds.remove(otherValue); + } else { + if (cond != newCondition) { + valueBounds.put(otherValue, newCondition); + updateDependency(); + } + } + } + } + } + + @Override + public void valueBound(Condition condition, ValueNode otherValue, ScalarTypeQuery type) { + ScalarTypeFeedbackStore other = type.store(); + switch (condition) { + case EQ: + simpleValueBound(condition, otherValue); + if (constantBounds.join(other.constantBounds)) { + updateDependency(); + } + break; + case NE: + simpleValueBound(condition, otherValue); + break; + case LE: + case LT: + simpleValueBound(condition, otherValue); + constantBound(condition, new CiConstant(kind, other.constantBounds.upperBound)); + break; + case GE: + case GT: + simpleValueBound(condition, otherValue); + constantBound(condition, new CiConstant(kind, other.constantBounds.lowerBound)); + break; + case BT: + if (other.constantBounds.lowerBound >= 0) { + simpleValueBound(Condition.LT, otherValue); + constantBound(Condition.GE, new CiConstant(kind, 0)); + constantBound(Condition.LT, new CiConstant(kind, other.constantBounds.upperBound)); + } + break; + case BE: + if (other.constantBounds.lowerBound >= 0) { + simpleValueBound(Condition.LE, otherValue); + constantBound(Condition.GE, new CiConstant(kind, 0)); + constantBound(Condition.LE, new CiConstant(kind, other.constantBounds.upperBound)); + } + break; + case AT: + if (other.constantBounds.upperBound < 0) { + simpleValueBound(Condition.GT, otherValue); + constantBound(Condition.LT, new CiConstant(kind, 0)); + constantBound(Condition.GT, new CiConstant(kind, other.constantBounds.lowerBound)); + } + break; + case AE: + if (other.constantBounds.upperBound < 0) { + simpleValueBound(Condition.GE, otherValue); + constantBound(Condition.LT, new CiConstant(kind, 0)); + constantBound(Condition.GE, new CiConstant(kind, other.constantBounds.lowerBound)); + } + break; + } + } + + public ScalarTypeQuery query() { + return new Query(this); + } + + public static ScalarTypeFeedbackStore meet(ScalarTypeFeedbackStore[] others) { + boolean emptyValueBounds = false; + for (int i = 0; i < others.length; i++) { + if (others[i] == null) { + return null; + } + if (others[i].valueBounds == null || others[i].valueBounds.isEmpty()) { + emptyValueBounds = true; + } + } + + ScalarTypeFeedbackStore first = others[0]; + ScalarTypeFeedbackStore result = new ScalarTypeFeedbackStore(first.kind, first.changed); + + if (!emptyValueBounds) { + for (Map.Entry<ValueNode, Condition> entry : first.valueBounds.entrySet()) { + Condition condition = entry.getValue(); + for (int i = 1; i < others.length; i++) { + Condition otherCond = others[i].valueBounds.get(entry.getKey()); + if (otherCond != null) { + condition = null; + break; + } + condition = condition.meet(otherCond); + if (condition == null) { + break; + } + } + if (condition != null) { + if (result.valueBounds == null) { + result.valueBounds = new HashMap<>(first.valueBounds.size()); + } + result.valueBounds.put(entry.getKey(), condition); + } + } + } + + result.constantBounds.lowerBound = first.constantBounds.lowerBound; + result.constantBounds.upperBound = first.constantBounds.upperBound; + + for (int i = 1; i < others.length; i++) { + result.constantBounds.meet(others[i].constantBounds); + } + return result; + } + + @Override + public ScalarTypeFeedbackStore clone() { + return new ScalarTypeFeedbackStore(this); + } + + @Override + public String toString() { + StringBuilder str = new StringBuilder().append('('); + if (constantBounds.lowerBound == minValue(kind)) { + str.append('-'); + } else { + str.append(constantBounds.lowerBound); + } + str.append(','); + if (constantBounds.upperBound == maxValue(kind)) { + str.append('-'); + } else { + str.append(constantBounds.upperBound); + } + str.append(')'); + + if (valueBounds != null) { + for (Map.Entry<ValueNode, Condition> entry : valueBounds.entrySet()) { + str.append(", ").append(entry.getValue().operator).append(' ').append(entry.getKey()); + } + } + if (dependency != null) { + str.append(" @ ").append(dependency); + } + return str.toString(); + } + + @Override + public void setTranslated(CiConstant deltaConstant, ScalarTypeQuery old) { + assert deltaConstant.kind == kind; + ScalarTypeFeedbackStore other = old.store(); + assert other.kind == kind; + long lower = other.constantBounds.lowerBound; + long upper = other.constantBounds.upperBound; + if (kind == CiKind.Int) { + int delta = deltaConstant.asInt(); + int newLower = (int) lower + delta; + int newUpper = (int) upper + delta; + if ((newLower <= lower && newUpper <= upper) || (newLower > lower && newUpper > upper)) { + constantBounds.join(new ConstantBound(newLower, newUpper)); + } + } else if (kind == CiKind.Long) { + long delta = deltaConstant.asLong(); + long newLower = lower + delta; + long newUpper = upper + delta; + if ((newLower <= lower && newUpper <= upper) || (newLower > lower && newUpper > upper)) { + constantBounds.join(new ConstantBound(newLower, newUpper)); + } + } else { + // nothing yet + } + } + + public boolean isEmpty() { + return constantBounds.lowerBound == minValue(kind) && constantBounds.upperBound == maxValue(kind) && (valueBounds == null || valueBounds.isEmpty()); + } + + private static long minValue(CiKind kind) { + if (kind == CiKind.Int) { + return Integer.MIN_VALUE; + } else if (kind == CiKind.Long) { + return Long.MIN_VALUE; + } else { + throw new UnsupportedOperationException(); + } + } + + private static long maxValue(CiKind kind) { + if (kind == CiKind.Int) { + return Integer.MAX_VALUE; + } else if (kind == CiKind.Long) { + return Long.MAX_VALUE; + } else { + throw new UnsupportedOperationException(); + } + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/spi/types/ScalarTypeFeedbackTool.java Wed Mar 14 17:42:41 2012 +0100 @@ -0,0 +1,36 @@ +/* + * 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.nodes.spi.types; + +import com.oracle.max.cri.ci.*; +import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.calc.*; + +public interface ScalarTypeFeedbackTool { + + void constantBound(Condition condition, CiConstant constant); + + void valueBound(Condition condition, ValueNode otherValue, ScalarTypeQuery type); + + void setTranslated(CiConstant delta, ScalarTypeQuery old); +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/spi/types/ScalarTypeQuery.java Wed Mar 14 17:42:41 2012 +0100 @@ -0,0 +1,36 @@ +/* + * 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.nodes.spi.types; + +import com.oracle.max.cri.ci.*; +import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.calc.*; + +public interface ScalarTypeQuery extends TypeQuery { + + boolean constantBound(Condition condition, CiConstant constant); + + boolean valueBound(Condition condition, ValueNode otherValue); + + ScalarTypeFeedbackStore store(); +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/spi/types/TypeFeedbackChanged.java Wed Mar 14 17:42:41 2012 +0100 @@ -0,0 +1,31 @@ +/* + * 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.nodes.spi.types; + +import com.oracle.graal.graph.*; + +public class TypeFeedbackChanged { + + public Node node; + +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/spi/types/TypeFeedbackStore.java Wed Mar 14 17:42:41 2012 +0100 @@ -0,0 +1,28 @@ +/* + * 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.nodes.spi.types; + + +public abstract class TypeFeedbackStore<T> { + +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/spi/types/TypeQuery.java Wed Mar 14 17:42:41 2012 +0100 @@ -0,0 +1,31 @@ +/* + * 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.nodes.spi.types; + +import com.oracle.graal.graph.*; + +public interface TypeQuery { + + Node dependency(); +} +