1/*
2 * Copyright (c) 2009, 2015, 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 */
23package org.graalvm.compiler.nodes.java;
24
25import java.util.ArrayList;
26import java.util.Arrays;
27
28import org.graalvm.compiler.core.common.type.AbstractPointerStamp;
29import org.graalvm.compiler.core.common.type.ObjectStamp;
30import org.graalvm.compiler.core.common.type.Stamp;
31import org.graalvm.compiler.core.common.type.StampFactory;
32import org.graalvm.compiler.core.common.type.TypeReference;
33import org.graalvm.compiler.graph.NodeClass;
34import org.graalvm.compiler.graph.spi.Simplifiable;
35import org.graalvm.compiler.graph.spi.SimplifierTool;
36import org.graalvm.compiler.nodeinfo.NodeInfo;
37import org.graalvm.compiler.nodes.AbstractBeginNode;
38import org.graalvm.compiler.nodes.ConstantNode;
39import org.graalvm.compiler.nodes.FixedWithNextNode;
40import org.graalvm.compiler.nodes.ValueNode;
41import org.graalvm.compiler.nodes.extended.LoadHubNode;
42import org.graalvm.compiler.nodes.extended.SwitchNode;
43import org.graalvm.compiler.nodes.spi.LIRLowerable;
44import org.graalvm.compiler.nodes.spi.NodeLIRBuilderTool;
45import org.graalvm.compiler.nodes.util.GraphUtil;
46
47import jdk.vm.ci.meta.Constant;
48import jdk.vm.ci.meta.ConstantReflectionProvider;
49import jdk.vm.ci.meta.ResolvedJavaType;
50
51/**
52 * The {@code TypeSwitchNode} performs a lookup based on the type of the input value. The type
53 * comparison is an exact type comparison, not an instanceof.
54 */
55@NodeInfo
56public final class TypeSwitchNode extends SwitchNode implements LIRLowerable, Simplifiable {
57
58    public static final NodeClass<TypeSwitchNode> TYPE = NodeClass.create(TypeSwitchNode.class);
59    protected final ResolvedJavaType[] keys;
60    protected final Constant[] hubs;
61
62    public TypeSwitchNode(ValueNode value, AbstractBeginNode[] successors, ResolvedJavaType[] keys, double[] keyProbabilities, int[] keySuccessors, ConstantReflectionProvider constantReflection) {
63        super(TYPE, value, successors, keySuccessors, keyProbabilities);
64        assert successors.length <= keys.length + 1;
65        assert keySuccessors.length == keyProbabilities.length;
66        this.keys = keys;
67        assert value.stamp() instanceof AbstractPointerStamp;
68        assert assertKeys();
69
70        hubs = new Constant[keys.length];
71        for (int i = 0; i < hubs.length; i++) {
72            hubs[i] = constantReflection.asObjectHub(keys[i]);
73        }
74    }
75
76    /**
77     * Don't allow duplicate keys.
78     */
79    private boolean assertKeys() {
80        for (int i = 0; i < keys.length; i++) {
81            for (int j = 0; j < keys.length; j++) {
82                if (i == j) {
83                    continue;
84                }
85                assert !keys[i].equals(keys[j]);
86            }
87        }
88        return true;
89    }
90
91    @Override
92    public boolean isSorted() {
93        return false;
94    }
95
96    @Override
97    public int keyCount() {
98        return keys.length;
99    }
100
101    @Override
102    public Constant keyAt(int index) {
103        return hubs[index];
104    }
105
106    @Override
107    public boolean equalKeys(SwitchNode switchNode) {
108        if (!(switchNode instanceof TypeSwitchNode)) {
109            return false;
110        }
111        TypeSwitchNode other = (TypeSwitchNode) switchNode;
112        return Arrays.equals(keys, other.keys);
113    }
114
115    public ResolvedJavaType typeAt(int index) {
116        return keys[index];
117    }
118
119    @Override
120    public void generate(NodeLIRBuilderTool gen) {
121        gen.emitSwitch(this);
122    }
123
124    @Override
125    public void simplify(SimplifierTool tool) {
126        if (value() instanceof ConstantNode) {
127            Constant constant = value().asConstant();
128
129            int survivingEdge = keySuccessorIndex(keyCount());
130            for (int i = 0; i < keyCount(); i++) {
131                Constant typeHub = keyAt(i);
132                Boolean equal = tool.getConstantReflection().constantEquals(constant, typeHub);
133                if (equal == null) {
134                    /* We don't know if this key is a match or not, so we cannot simplify. */
135                    return;
136                } else if (equal.booleanValue()) {
137                    survivingEdge = keySuccessorIndex(i);
138                }
139            }
140            killOtherSuccessors(tool, survivingEdge);
141        }
142        if (value() instanceof LoadHubNode && ((LoadHubNode) value()).getValue().stamp() instanceof ObjectStamp) {
143            ObjectStamp objectStamp = (ObjectStamp) ((LoadHubNode) value()).getValue().stamp();
144            if (objectStamp.type() != null) {
145                int validKeys = 0;
146                for (int i = 0; i < keyCount(); i++) {
147                    if (objectStamp.type().isAssignableFrom(keys[i])) {
148                        validKeys++;
149                    }
150                }
151                if (validKeys == 0) {
152                    tool.addToWorkList(defaultSuccessor());
153                    graph().removeSplitPropagate(this, defaultSuccessor());
154                } else if (validKeys != keys.length) {
155                    ArrayList<AbstractBeginNode> newSuccessors = new ArrayList<>(blockSuccessorCount());
156                    ResolvedJavaType[] newKeys = new ResolvedJavaType[validKeys];
157                    int[] newKeySuccessors = new int[validKeys + 1];
158                    double[] newKeyProbabilities = new double[validKeys + 1];
159                    double totalProbability = 0;
160                    int current = 0;
161                    for (int i = 0; i < keyCount() + 1; i++) {
162                        if (i == keyCount() || objectStamp.type().isAssignableFrom(keys[i])) {
163                            int index = newSuccessors.indexOf(keySuccessor(i));
164                            if (index == -1) {
165                                index = newSuccessors.size();
166                                newSuccessors.add(keySuccessor(i));
167                            }
168                            newKeySuccessors[current] = index;
169                            if (i < keyCount()) {
170                                newKeys[current] = keys[i];
171                            }
172                            newKeyProbabilities[current] = keyProbability(i);
173                            totalProbability += keyProbability(i);
174                            current++;
175                        }
176                    }
177                    if (totalProbability > 0) {
178                        for (int i = 0; i < current; i++) {
179                            newKeyProbabilities[i] /= totalProbability;
180                        }
181                    } else {
182                        for (int i = 0; i < current; i++) {
183                            newKeyProbabilities[i] = 1.0 / current;
184                        }
185                    }
186
187                    for (int i = 0; i < blockSuccessorCount(); i++) {
188                        AbstractBeginNode successor = blockSuccessor(i);
189                        if (!newSuccessors.contains(successor)) {
190                            tool.deleteBranch(successor);
191                        }
192                        setBlockSuccessor(i, null);
193                    }
194
195                    AbstractBeginNode[] successorsArray = newSuccessors.toArray(new AbstractBeginNode[newSuccessors.size()]);
196                    TypeSwitchNode newSwitch = graph().add(new TypeSwitchNode(value(), successorsArray, newKeys, newKeyProbabilities, newKeySuccessors, tool.getConstantReflection()));
197                    ((FixedWithNextNode) predecessor()).setNext(newSwitch);
198                    GraphUtil.killWithUnusedFloatingInputs(this);
199                }
200            }
201        }
202    }
203
204    @Override
205    public Stamp getValueStampForSuccessor(AbstractBeginNode beginNode) {
206        Stamp result = null;
207        if (beginNode != defaultSuccessor()) {
208            for (int i = 0; i < keyCount(); i++) {
209                if (keySuccessor(i) == beginNode) {
210                    if (result == null) {
211                        result = StampFactory.objectNonNull(TypeReference.createExactTrusted(typeAt(i)));
212                    } else {
213                        result = result.meet(StampFactory.objectNonNull(TypeReference.createExactTrusted(typeAt(i))));
214                    }
215                }
216            }
217        }
218        return result;
219    }
220}
221