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.extended;
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.spi.*;
035import com.oracle.graal.nodes.util.*;
036
037/**
038 * The {@code IntegerSwitchNode} represents a switch on integer keys, with a sorted array of key
039 * values. The actual implementation of the switch will be decided by the backend.
040 */
041@NodeInfo
042public final class IntegerSwitchNode extends SwitchNode implements LIRLowerable, Simplifiable {
043    public static final NodeClass<IntegerSwitchNode> TYPE = NodeClass.create(IntegerSwitchNode.class);
044
045    protected final int[] keys;
046
047    public IntegerSwitchNode(ValueNode value, AbstractBeginNode[] successors, int[] keys, double[] keyProbabilities, int[] keySuccessors) {
048        super(TYPE, value, successors, keySuccessors, keyProbabilities);
049        assert keySuccessors.length == keys.length + 1;
050        assert keySuccessors.length == keyProbabilities.length;
051        this.keys = keys;
052        assert value.stamp() instanceof PrimitiveStamp && value.stamp().getStackKind().isNumericInteger();
053        assert assertSorted();
054    }
055
056    private boolean assertSorted() {
057        for (int i = 1; i < keys.length; i++) {
058            assert keys[i - 1] < keys[i];
059        }
060        return true;
061    }
062
063    public IntegerSwitchNode(ValueNode value, int successorCount, int[] keys, double[] keyProbabilities, int[] keySuccessors) {
064        this(value, new AbstractBeginNode[successorCount], keys, keyProbabilities, keySuccessors);
065    }
066
067    @Override
068    public boolean isSorted() {
069        return true;
070    }
071
072    /**
073     * Gets the key at the specified index.
074     *
075     * @param i the index
076     * @return the key at that index
077     */
078    @Override
079    public JavaConstant keyAt(int i) {
080        return JavaConstant.forInt(keys[i]);
081    }
082
083    @Override
084    public int keyCount() {
085        return keys.length;
086    }
087
088    @Override
089    public boolean equalKeys(SwitchNode switchNode) {
090        if (!(switchNode instanceof IntegerSwitchNode)) {
091            return false;
092        }
093        IntegerSwitchNode other = (IntegerSwitchNode) switchNode;
094        return Arrays.equals(keys, other.keys);
095    }
096
097    @Override
098    public void generate(NodeLIRBuilderTool gen) {
099        gen.emitSwitch(this);
100    }
101
102    public AbstractBeginNode successorAtKey(int key) {
103        return blockSuccessor(successorIndexAtKey(key));
104    }
105
106    public int successorIndexAtKey(int key) {
107        for (int i = 0; i < keyCount(); i++) {
108            if (keys[i] == key) {
109                return keySuccessorIndex(i);
110            }
111        }
112        return keySuccessorIndex(keyCount());
113    }
114
115    @Override
116    public void simplify(SimplifierTool tool) {
117        if (blockSuccessorCount() == 1) {
118            tool.addToWorkList(defaultSuccessor());
119            graph().removeSplitPropagate(this, defaultSuccessor());
120        } else if (value() instanceof ConstantNode) {
121            killOtherSuccessors(tool, successorIndexAtKey(value().asJavaConstant().asInt()));
122        } else if (value().stamp() instanceof IntegerStamp) {
123            IntegerStamp integerStamp = (IntegerStamp) value().stamp();
124            if (!integerStamp.isUnrestricted()) {
125                int validKeys = 0;
126                for (int i = 0; i < keyCount(); i++) {
127                    if (integerStamp.contains(keys[i])) {
128                        validKeys++;
129                    }
130                }
131                if (validKeys == 0) {
132                    tool.addToWorkList(defaultSuccessor());
133                    graph().removeSplitPropagate(this, defaultSuccessor());
134                } else if (validKeys != keys.length) {
135                    ArrayList<AbstractBeginNode> newSuccessors = new ArrayList<>(blockSuccessorCount());
136                    int[] newKeys = new int[validKeys];
137                    int[] newKeySuccessors = new int[validKeys + 1];
138                    double[] newKeyProbabilities = new double[validKeys + 1];
139                    double totalProbability = 0;
140                    int current = 0;
141                    for (int i = 0; i < keyCount() + 1; i++) {
142                        if (i == keyCount() || integerStamp.contains(keys[i])) {
143                            int index = newSuccessors.indexOf(keySuccessor(i));
144                            if (index == -1) {
145                                index = newSuccessors.size();
146                                newSuccessors.add(keySuccessor(i));
147                            }
148                            newKeySuccessors[current] = index;
149                            if (i < keyCount()) {
150                                newKeys[current] = keys[i];
151                            }
152                            newKeyProbabilities[current] = keyProbability(i);
153                            totalProbability += keyProbability(i);
154                            current++;
155                        }
156                    }
157                    if (totalProbability > 0) {
158                        for (int i = 0; i < current; i++) {
159                            newKeyProbabilities[i] /= totalProbability;
160                        }
161                    } else {
162                        for (int i = 0; i < current; i++) {
163                            newKeyProbabilities[i] = 1.0 / current;
164                        }
165                    }
166
167                    for (int i = 0; i < blockSuccessorCount(); i++) {
168                        AbstractBeginNode successor = blockSuccessor(i);
169                        if (!newSuccessors.contains(successor)) {
170                            tool.deleteBranch(successor);
171                        }
172                        setBlockSuccessor(i, null);
173                    }
174
175                    AbstractBeginNode[] successorsArray = newSuccessors.toArray(new AbstractBeginNode[newSuccessors.size()]);
176                    SwitchNode newSwitch = graph().add(new IntegerSwitchNode(value(), successorsArray, newKeys, newKeyProbabilities, newKeySuccessors));
177                    ((FixedWithNextNode) predecessor()).setNext(newSwitch);
178                    GraphUtil.killWithUnusedFloatingInputs(this);
179                }
180            }
181        }
182    }
183}