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;
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.calc.*;
034
035/**
036 * {@code PhiNode}s represent the merging of edges at a control flow merges (
037 * {@link AbstractMergeNode} or {@link LoopBeginNode}). For a {@link AbstractMergeNode}, the order
038 * of the values corresponds to the order of the ends. For {@link LoopBeginNode}s, the first value
039 * corresponds to the loop's predecessor, while the rest of the values correspond to the
040 * {@link LoopEndNode}s.
041 */
042@NodeInfo
043public abstract class PhiNode extends FloatingNode implements Simplifiable {
044
045    public static final NodeClass<PhiNode> TYPE = NodeClass.create(PhiNode.class);
046    @Input(InputType.Association) protected AbstractMergeNode merge;
047
048    protected PhiNode(NodeClass<? extends PhiNode> c, Stamp stamp, AbstractMergeNode merge) {
049        super(c, stamp);
050        this.merge = merge;
051    }
052
053    public abstract NodeInputList<ValueNode> values();
054
055    public AbstractMergeNode merge() {
056        return merge;
057    }
058
059    public void setMerge(AbstractMergeNode x) {
060        updateUsages(merge, x);
061        merge = x;
062    }
063
064    @Override
065    public boolean verify() {
066        assertTrue(merge() != null, "missing merge");
067        assertTrue(merge().phiPredecessorCount() == valueCount(), "mismatch between merge predecessor count and phi value count: %d != %d", merge().phiPredecessorCount(), valueCount());
068        return super.verify();
069    }
070
071    /**
072     * Get the instruction that produces the value associated with the i'th predecessor of the
073     * merge.
074     *
075     * @param i the index of the predecessor
076     * @return the instruction that produced the value in the i'th predecessor
077     */
078    public ValueNode valueAt(int i) {
079        return values().get(i);
080    }
081
082    /**
083     * Sets the value at the given index and makes sure that the values list is large enough.
084     *
085     * @param i the index at which to set the value
086     * @param x the new phi input value for the given location
087     */
088    public void initializeValueAt(int i, ValueNode x) {
089        while (values().size() <= i) {
090            values().add(null);
091        }
092        values().set(i, x);
093    }
094
095    public void setValueAt(int i, ValueNode x) {
096        values().set(i, x);
097    }
098
099    public void setValueAt(AbstractEndNode end, ValueNode x) {
100        setValueAt(merge().phiPredecessorIndex(end), x);
101    }
102
103    public ValueNode valueAt(AbstractEndNode pred) {
104        return valueAt(merge().phiPredecessorIndex(pred));
105    }
106
107    /**
108     * Get the number of inputs to this phi (i.e. the number of predecessors to the merge).
109     *
110     * @return the number of inputs in this phi
111     */
112    public int valueCount() {
113        return values().size();
114    }
115
116    public void clearValues() {
117        values().clear();
118    }
119
120    @Override
121    public String toString(Verbosity verbosity) {
122        if (verbosity == Verbosity.Name) {
123            StringBuilder str = new StringBuilder();
124            for (int i = 0; i < valueCount(); ++i) {
125                if (i != 0) {
126                    str.append(' ');
127                }
128                str.append(valueAt(i) == null ? "-" : valueAt(i).toString(Verbosity.Id));
129            }
130            return super.toString(Verbosity.Name) + "(" + str + ")";
131        } else {
132            return super.toString(verbosity);
133        }
134    }
135
136    public void addInput(ValueNode x) {
137        assert !(x instanceof ValuePhiNode) || ((ValuePhiNode) x).merge() instanceof LoopBeginNode || ((ValuePhiNode) x).merge() != this.merge();
138        assert !(this instanceof ValuePhiNode) || x.stamp().isCompatible(stamp()) || (stamp().getStackKind() == Kind.Int && x.stamp().getStackKind().getBitCount() >= Kind.Int.getBitCount());
139        values().add(x);
140    }
141
142    public void removeInput(int index) {
143        values().remove(index);
144    }
145
146    @NodeInfo
147    static final class MultipleValuesNode extends ValueNode {
148
149        public static final NodeClass<MultipleValuesNode> TYPE = NodeClass.create(MultipleValuesNode.class);
150
151        public MultipleValuesNode() {
152            super(TYPE, null);
153        }
154
155    }
156
157    public static final ValueNode MULTIPLE_VALUES = new MultipleValuesNode();
158
159    /**
160     * If all inputs are the same value, this value is returned, otherwise {@link #MULTIPLE_VALUES}.
161     * Note that {@code null} is a valid return value, since {@link GuardPhiNode}s can have
162     * {@code null} inputs.
163     */
164    public ValueNode singleValue() {
165        ValueNode singleValue = valueAt(0);
166        int count = valueCount();
167        for (int i = 1; i < count; ++i) {
168            ValueNode value = valueAt(i);
169            if (value != this) {
170                if (value != singleValue) {
171                    return MULTIPLE_VALUES;
172                }
173            }
174        }
175        return singleValue;
176    }
177
178    /**
179     * If all inputs (but the first one) are the same value, this value is returned, otherwise
180     * {@link #MULTIPLE_VALUES}. Note that {@code null} is a valid return value, since
181     * {@link GuardPhiNode}s can have {@code null} inputs.
182     */
183    public ValueNode singleBackValue() {
184        assert merge() instanceof LoopBeginNode;
185        Iterator<ValueNode> iterator = values().iterator();
186        iterator.next();
187        ValueNode singleValue = iterator.next();
188        while (iterator.hasNext()) {
189            if (iterator.next() != singleValue) {
190                return MULTIPLE_VALUES;
191            }
192        }
193        return singleValue;
194    }
195
196    @Override
197    public void simplify(SimplifierTool tool) {
198        ValueNode singleValue;
199
200        if (isLoopPhi() && singleBackValue() == this) {
201            singleValue = firstValue();
202        } else {
203            singleValue = singleValue();
204        }
205
206        if (singleValue != MULTIPLE_VALUES) {
207            for (Node node : usages().snapshot()) {
208                if (node instanceof ProxyNode && ((ProxyNode) node).proxyPoint() instanceof LoopExitNode && ((LoopExitNode) ((ProxyNode) node).proxyPoint()).loopBegin() == merge) {
209                    tool.addToWorkList(node.usages());
210                    graph().replaceFloating((FloatingNode) node, singleValue);
211                }
212            }
213            for (Node usage : usages().snapshot()) {
214                if (usage != this) {
215                    usage.replaceFirstInput(this, singleValue);
216                }
217            }
218            clearInputs();
219            safeDelete();
220        }
221    }
222
223    public ValueNode firstValue() {
224        return valueAt(0);
225    }
226
227    public boolean isLoopPhi() {
228        return merge() instanceof LoopBeginNode;
229    }
230
231}