001/*
002 * Copyright (c) 2009, 2014, 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 java.util.*;
026
027import jdk.internal.jvmci.meta.*;
028
029import com.oracle.graal.compiler.common.type.*;
030import com.oracle.graal.graph.*;
031import com.oracle.graal.graph.spi.*;
032import com.oracle.graal.nodeinfo.*;
033import com.oracle.graal.nodes.*;
034import com.oracle.graal.nodes.extended.*;
035import com.oracle.graal.nodes.spi.*;
036import com.oracle.graal.nodes.util.*;
037
038/**
039 * The {@code TypeSwitchNode} performs a lookup based on the type of the input value. The type
040 * comparison is an exact type comparison, not an instanceof.
041 */
042@NodeInfo
043public final class TypeSwitchNode extends SwitchNode implements LIRLowerable, Simplifiable {
044
045    public static final NodeClass<TypeSwitchNode> TYPE = NodeClass.create(TypeSwitchNode.class);
046    protected final ResolvedJavaType[] keys;
047
048    public TypeSwitchNode(ValueNode value, AbstractBeginNode[] successors, ResolvedJavaType[] keys, double[] keyProbabilities, int[] keySuccessors) {
049        super(TYPE, value, successors, keySuccessors, keyProbabilities);
050        assert successors.length <= keys.length + 1;
051        assert keySuccessors.length == keyProbabilities.length;
052        this.keys = keys;
053        assert value.stamp() instanceof AbstractPointerStamp;
054        assert assertKeys();
055    }
056
057    /**
058     * Don't allow duplicate keys.
059     */
060    private boolean assertKeys() {
061        for (int i = 0; i < keys.length; i++) {
062            for (int j = 0; j < keys.length; j++) {
063                if (i == j) {
064                    continue;
065                }
066                assert !keys[i].equals(keys[j]);
067            }
068        }
069        return true;
070    }
071
072    @Override
073    public boolean isSorted() {
074        Kind kind = value().getKind();
075        if (kind.isNumericInteger()) {
076            JavaConstant lastKey = null;
077            for (int i = 0; i < keyCount(); i++) {
078                JavaConstant key = keyAt(i);
079                if (lastKey != null && key.asLong() <= lastKey.asLong()) {
080                    return false;
081                }
082                lastKey = key;
083            }
084            return true;
085        } else {
086            return false;
087        }
088    }
089
090    @Override
091    public int keyCount() {
092        return keys.length;
093    }
094
095    @Override
096    public JavaConstant keyAt(int index) {
097        return (JavaConstant) keys[index].getObjectHub();
098    }
099
100    @Override
101    public boolean equalKeys(SwitchNode switchNode) {
102        if (!(switchNode instanceof TypeSwitchNode)) {
103            return false;
104        }
105        TypeSwitchNode other = (TypeSwitchNode) switchNode;
106        return Arrays.equals(keys, other.keys);
107    }
108
109    public ResolvedJavaType typeAt(int index) {
110        return keys[index];
111    }
112
113    @Override
114    public void generate(NodeLIRBuilderTool gen) {
115        gen.emitSwitch(this);
116    }
117
118    @Override
119    public void simplify(SimplifierTool tool) {
120        if (value() instanceof ConstantNode) {
121            JavaConstant constant = value().asJavaConstant();
122
123            int survivingEdge = keySuccessorIndex(keyCount());
124            for (int i = 0; i < keyCount(); i++) {
125                JavaConstant typeHub = keyAt(i);
126                assert constant.getKind() == typeHub.getKind();
127                Boolean equal = tool.getConstantReflection().constantEquals(constant, typeHub);
128                if (equal == null) {
129                    /* We don't know if this key is a match or not, so we cannot simplify. */
130                    return;
131                } else if (equal.booleanValue()) {
132                    survivingEdge = keySuccessorIndex(i);
133                }
134            }
135            killOtherSuccessors(tool, survivingEdge);
136        }
137        if (value() instanceof LoadHubNode && ((LoadHubNode) value()).getValue().stamp() instanceof ObjectStamp) {
138            ObjectStamp objectStamp = (ObjectStamp) ((LoadHubNode) value()).getValue().stamp();
139            if (objectStamp.type() != null) {
140                int validKeys = 0;
141                for (int i = 0; i < keyCount(); i++) {
142                    if (objectStamp.type().isAssignableFrom(keys[i])) {
143                        validKeys++;
144                    }
145                }
146                if (validKeys == 0) {
147                    tool.addToWorkList(defaultSuccessor());
148                    graph().removeSplitPropagate(this, defaultSuccessor());
149                } else if (validKeys != keys.length) {
150                    ArrayList<AbstractBeginNode> newSuccessors = new ArrayList<>(blockSuccessorCount());
151                    ResolvedJavaType[] newKeys = new ResolvedJavaType[validKeys];
152                    int[] newKeySuccessors = new int[validKeys + 1];
153                    double[] newKeyProbabilities = new double[validKeys + 1];
154                    double totalProbability = 0;
155                    int current = 0;
156                    for (int i = 0; i < keyCount() + 1; i++) {
157                        if (i == keyCount() || objectStamp.type().isAssignableFrom(keys[i])) {
158                            int index = newSuccessors.indexOf(keySuccessor(i));
159                            if (index == -1) {
160                                index = newSuccessors.size();
161                                newSuccessors.add(keySuccessor(i));
162                            }
163                            newKeySuccessors[current] = index;
164                            if (i < keyCount()) {
165                                newKeys[current] = keys[i];
166                            }
167                            newKeyProbabilities[current] = keyProbability(i);
168                            totalProbability += keyProbability(i);
169                            current++;
170                        }
171                    }
172                    if (totalProbability > 0) {
173                        for (int i = 0; i < current; i++) {
174                            newKeyProbabilities[i] /= totalProbability;
175                        }
176                    } else {
177                        for (int i = 0; i < current; i++) {
178                            newKeyProbabilities[i] = 1.0 / current;
179                        }
180                    }
181
182                    for (int i = 0; i < blockSuccessorCount(); i++) {
183                        AbstractBeginNode successor = blockSuccessor(i);
184                        if (!newSuccessors.contains(successor)) {
185                            tool.deleteBranch(successor);
186                        }
187                        setBlockSuccessor(i, null);
188                    }
189
190                    AbstractBeginNode[] successorsArray = newSuccessors.toArray(new AbstractBeginNode[newSuccessors.size()]);
191                    TypeSwitchNode newSwitch = graph().add(new TypeSwitchNode(value(), successorsArray, newKeys, newKeyProbabilities, newKeySuccessors));
192                    ((FixedWithNextNode) predecessor()).setNext(newSwitch);
193                    GraphUtil.killWithUnusedFloatingInputs(this);
194                }
195            }
196        }
197    }
198}