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.common.*;
028import jdk.internal.jvmci.meta.*;
029
030import com.oracle.graal.compiler.common.type.*;
031import com.oracle.graal.graph.*;
032import com.oracle.graal.graph.spi.*;
033import com.oracle.graal.nodeinfo.*;
034import com.oracle.graal.nodes.*;
035
036/**
037 * The {@code SwitchNode} class is the base of both lookup and table switches.
038 */
039@NodeInfo
040public abstract class SwitchNode extends ControlSplitNode {
041
042    public static final NodeClass<SwitchNode> TYPE = NodeClass.create(SwitchNode.class);
043    @Successor protected NodeSuccessorList<AbstractBeginNode> successors;
044    @Input protected ValueNode value;
045
046    // do not change the contents of these arrays:
047    protected final double[] keyProbabilities;
048    protected final int[] keySuccessors;
049
050    /**
051     * Constructs a new Switch.
052     *
053     * @param value the instruction that provides the value to be switched over
054     * @param successors the list of successors of this switch
055     */
056    protected SwitchNode(NodeClass<? extends SwitchNode> c, ValueNode value, AbstractBeginNode[] successors, int[] keySuccessors, double[] keyProbabilities) {
057        super(c, StampFactory.forVoid());
058        assert value.stamp().getStackKind().isNumericInteger() || value.stamp() instanceof AbstractPointerStamp : value.stamp() + " key not supported by SwitchNode";
059        assert keySuccessors.length == keyProbabilities.length;
060        this.successors = new NodeSuccessorList<>(this, successors);
061        this.value = value;
062        this.keySuccessors = keySuccessors;
063        this.keyProbabilities = keyProbabilities;
064        assert assertProbabilities();
065    }
066
067    private boolean assertProbabilities() {
068        double total = 0;
069        for (double d : keyProbabilities) {
070            total += d;
071            assert d >= 0.0 : "Cannot have negative probabilities in switch node: " + d;
072        }
073        assert total > 0.999 && total < 1.001 : "Total " + total;
074        return true;
075    }
076
077    @Override
078    public double probability(AbstractBeginNode successor) {
079        double sum = 0;
080        for (int i = 0; i < keySuccessors.length; i++) {
081            if (successors.get(keySuccessors[i]) == successor) {
082                sum += keyProbabilities[i];
083            }
084        }
085        return sum;
086    }
087
088    public ValueNode value() {
089        return value;
090    }
091
092    public abstract boolean isSorted();
093
094    /**
095     * The number of distinct keys in this switch.
096     */
097    public abstract int keyCount();
098
099    /**
100     * The key at the specified position, encoded in a Constant.
101     */
102    public abstract JavaConstant keyAt(int i);
103
104    public boolean structureEquals(SwitchNode switchNode) {
105        return Arrays.equals(keySuccessors, switchNode.keySuccessors) && equalKeys(switchNode);
106    }
107
108    /**
109     * Returns true if the switch has the same keys in the same order as this switch.
110     */
111    public abstract boolean equalKeys(SwitchNode switchNode);
112
113    /**
114     * Returns the index of the successor belonging to the key at the specified index.
115     */
116    public int keySuccessorIndex(int i) {
117        return keySuccessors[i];
118    }
119
120    /**
121     * Returns the successor for the key at the given index.
122     */
123    public AbstractBeginNode keySuccessor(int i) {
124        return successors.get(keySuccessors[i]);
125    }
126
127    /**
128     * Returns the probability of the key at the given index.
129     */
130    public double keyProbability(int i) {
131        return keyProbabilities[i];
132    }
133
134    /**
135     * Returns the index of the default (fall through) successor of this switch.
136     */
137    public int defaultSuccessorIndex() {
138        return keySuccessors[keySuccessors.length - 1];
139    }
140
141    public AbstractBeginNode blockSuccessor(int i) {
142        return successors.get(i);
143    }
144
145    public void setBlockSuccessor(int i, AbstractBeginNode s) {
146        successors.set(i, s);
147    }
148
149    public int blockSuccessorCount() {
150        return successors.count();
151    }
152
153    /**
154     * Gets the successor corresponding to the default (fall through) case.
155     *
156     * @return the default successor
157     */
158    public AbstractBeginNode defaultSuccessor() {
159        if (defaultSuccessorIndex() == -1) {
160            throw new JVMCIError("unexpected");
161        }
162        return successors.get(defaultSuccessorIndex());
163    }
164
165    @Override
166    public AbstractBeginNode getPrimarySuccessor() {
167        return this.defaultSuccessor();
168    }
169
170    /**
171     * Delete all other successors except for the one reached by {@code survivingEdge}.
172     *
173     * @param tool
174     * @param survivingEdge index of the edge in the {@link SwitchNode#successors} list
175     */
176    protected void killOtherSuccessors(SimplifierTool tool, int survivingEdge) {
177        for (Node successor : successors()) {
178            /*
179             * Deleting a branch change change the successors so reload the surviving successor each
180             * time.
181             */
182            if (successor != blockSuccessor(survivingEdge)) {
183                tool.deleteBranch(successor);
184            }
185        }
186        tool.addToWorkList(blockSuccessor(survivingEdge));
187        graph().removeSplit(this, blockSuccessor(survivingEdge));
188    }
189}