001/*
002 * Copyright (c) 2009, 2015, Oracle and/or its affiliates. All rights reserved.
003 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
004 *
005 * This code is free software; you can redistribute it and/or modify it
006 * under the terms of the GNU General Public License version 2 only, as
007 * published by the Free Software Foundation.
008 *
009 * This code is distributed in the hope that it will be useful, but WITHOUT
010 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
011 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
012 * version 2 for more details (a copy is included in the LICENSE file that
013 * accompanied this code).
014 *
015 * You should have received a copy of the GNU General Public License version
016 * 2 along with this work; if not, write to the Free Software Foundation,
017 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
018 *
019 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
020 * or visit www.oracle.com if you need additional information or have any
021 * questions.
022 */
023package com.oracle.graal.nodes.java;
024
025import jdk.internal.jvmci.meta.*;
026import jdk.internal.jvmci.meta.Assumptions.*;
027
028import com.oracle.graal.compiler.common.type.*;
029import com.oracle.graal.graph.*;
030import com.oracle.graal.graph.spi.*;
031import com.oracle.graal.nodeinfo.*;
032import com.oracle.graal.nodes.*;
033import com.oracle.graal.nodes.calc.*;
034import com.oracle.graal.nodes.spi.*;
035
036/**
037 * The {@code InstanceOfNode} represents an instanceof test.
038 */
039@NodeInfo
040public class InstanceOfNode extends UnaryOpLogicNode implements Lowerable, Virtualizable {
041    public static final NodeClass<InstanceOfNode> TYPE = NodeClass.create(InstanceOfNode.class);
042
043    protected final ResolvedJavaType type;
044    protected JavaTypeProfile profile;
045
046    private InstanceOfNode(ResolvedJavaType type, ValueNode object, JavaTypeProfile profile) {
047        this(TYPE, type, object, profile);
048    }
049
050    protected InstanceOfNode(NodeClass<? extends InstanceOfNode> c, ResolvedJavaType type, ValueNode object, JavaTypeProfile profile) {
051        super(c, object);
052        this.type = type;
053        this.profile = profile;
054        assert type != null;
055    }
056
057    public static LogicNode create(ResolvedJavaType type, ValueNode object, JavaTypeProfile profile) {
058        ObjectStamp objectStamp = (ObjectStamp) object.stamp();
059        LogicNode constantValue = findSynonym(object, type, objectStamp.type(), objectStamp.nonNull(), objectStamp.isExactType());
060        if (constantValue != null) {
061            return constantValue;
062        } else {
063            return new InstanceOfNode(type, object, profile);
064        }
065    }
066
067    @Override
068    public void lower(LoweringTool tool) {
069        tool.getLowerer().lower(this, tool);
070    }
071
072    @Override
073    public ValueNode canonical(CanonicalizerTool tool, ValueNode forValue) {
074        if (!(forValue.stamp() instanceof ObjectStamp)) {
075            return this;
076        }
077        ObjectStamp objectStamp = (ObjectStamp) forValue.stamp();
078        if (objectStamp.alwaysNull()) {
079            return LogicConstantNode.contradiction();
080        }
081
082        ResolvedJavaType stampType = objectStamp.type();
083        if (stampType != null) {
084            ValueNode result = checkInstanceOf(forValue, stampType, objectStamp.nonNull(), objectStamp.isExactType());
085            if (result != null) {
086                return result;
087            }
088            Assumptions assumptions = graph() == null ? null : graph().getAssumptions();
089            if (assumptions != null) {
090                AssumptionResult<ResolvedJavaType> leafConcreteSubtype = stampType.findLeafConcreteSubtype();
091                if (leafConcreteSubtype != null) {
092                    result = checkInstanceOf(forValue, leafConcreteSubtype.getResult(), objectStamp.nonNull(), true);
093                    if (result != null) {
094                        assumptions.record(leafConcreteSubtype);
095                        return result;
096                    }
097                }
098            }
099        }
100        return this;
101    }
102
103    private ValueNode checkInstanceOf(ValueNode forValue, ResolvedJavaType inputType, boolean nonNull, boolean exactType) {
104        ValueNode result = findSynonym(forValue, type(), inputType, nonNull, exactType);
105        if (result != null) {
106            return result;
107        }
108        if (type().isAssignableFrom(inputType)) {
109            if (!nonNull) {
110                // the instanceof matches if the object is non-null, so return true
111                // depending on the null-ness.
112                return LogicNegationNode.create(new IsNullNode(forValue));
113            }
114        }
115        return null;
116    }
117
118    public static LogicNode findSynonym(ValueNode object, ResolvedJavaType type, ResolvedJavaType inputType, boolean nonNull, boolean exactType) {
119        if (inputType == null) {
120            return null;
121        }
122        boolean subType = type.isAssignableFrom(inputType);
123        if (subType) {
124            if (nonNull) {
125                // the instanceOf matches, so return true
126                return LogicConstantNode.tautology();
127            }
128        } else {
129            if (exactType) {
130                // since this type check failed for an exact type we know that it can never
131                // succeed at run time. we also don't care about null values, since they will
132                // also make the check fail.
133                return LogicConstantNode.contradiction();
134            } else {
135                boolean superType = inputType.isAssignableFrom(type);
136                if (!superType && (type.asExactType() != null || (!isInterfaceOrArrayOfInterface(inputType) && !isInterfaceOrArrayOfInterface(type)))) {
137                    return LogicConstantNode.contradiction();
138                }
139                // since the subtype comparison was only performed on a declared type we don't
140                // really know if it might be true at run time...
141            }
142        }
143
144        if (type.isLeaf() && nonNull) {
145            return TypeCheckNode.create(type, object);
146        }
147        return null;
148    }
149
150    /**
151     * Gets the type being tested.
152     */
153    public ResolvedJavaType type() {
154        return type;
155    }
156
157    public JavaTypeProfile profile() {
158        return profile;
159    }
160
161    public void setProfile(JavaTypeProfile profile) {
162        this.profile = profile;
163    }
164
165    @Override
166    public void virtualize(VirtualizerTool tool) {
167        ValueNode alias = tool.getAlias(getValue());
168        TriState fold = tryFold(alias.stamp());
169        if (fold != TriState.UNKNOWN) {
170            tool.replaceWithValue(LogicConstantNode.forBoolean(fold.isTrue(), graph()));
171        }
172    }
173
174    @Override
175    public Stamp getSucceedingStampForValue(boolean negated) {
176        if (negated) {
177            return null;
178        } else {
179            return StampFactory.declaredTrustedNonNull(type);
180        }
181    }
182
183    @Override
184    public TriState tryFold(Stamp valueStamp) {
185        if (valueStamp instanceof ObjectStamp) {
186            ObjectStamp objectStamp = (ObjectStamp) valueStamp;
187            if (objectStamp.alwaysNull()) {
188                return TriState.FALSE;
189            }
190
191            ResolvedJavaType objectType = objectStamp.type();
192            if (objectType != null) {
193                ResolvedJavaType instanceofType = type;
194                if (instanceofType.isAssignableFrom(objectType)) {
195                    if (objectStamp.nonNull()) {
196                        return TriState.TRUE;
197                    }
198                } else {
199                    if (objectStamp.isExactType()) {
200                        return TriState.FALSE;
201                    } else {
202                        boolean superType = objectType.isAssignableFrom(instanceofType);
203                        if (!superType && !objectType.isInterface() && !instanceofType.isInterface()) {
204                            return TriState.FALSE;
205                        }
206                    }
207                }
208            }
209        }
210        return TriState.UNKNOWN;
211    }
212
213    private static boolean isInterfaceOrArrayOfInterface(ResolvedJavaType t) {
214        return t.isInterface() || (t.isArray() && t.getElementalType().isInterface());
215    }
216}