1 /*
2 * Copyright (c) 2009, 2016, 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 */
23 package org.graalvm.compiler.nodes;
24
25 import static org.graalvm.compiler.nodeinfo.InputType.Association;
26 import static org.graalvm.compiler.nodeinfo.NodeCycles.CYCLES_0;
27 import static org.graalvm.compiler.nodeinfo.NodeSize.SIZE_1;
28
29 import java.util.Iterator;
30
31 import org.graalvm.compiler.core.common.type.Stamp;
32 import org.graalvm.compiler.graph.Node;
33 import org.graalvm.compiler.graph.NodeClass;
34 import org.graalvm.compiler.graph.NodeInputList;
35 import org.graalvm.compiler.graph.iterators.NodeIterable;
36 import org.graalvm.compiler.graph.spi.Canonicalizable;
37 import org.graalvm.compiler.graph.spi.CanonicalizerTool;
38 import org.graalvm.compiler.nodeinfo.NodeInfo;
39 import org.graalvm.compiler.nodeinfo.Verbosity;
40 import org.graalvm.compiler.nodes.calc.FloatingNode;
41
42 /**
43 * {@code PhiNode}s represent the merging of edges at a control flow merges (
44 * {@link AbstractMergeNode} or {@link LoopBeginNode}). For a {@link AbstractMergeNode}, the order
45 * of the values corresponds to the order of the ends. For {@link LoopBeginNode}s, the first value
46 * corresponds to the loop's predecessor, while the rest of the values correspond to the
47 * {@link LoopEndNode}s.
48 */
49 @NodeInfo(cycles = CYCLES_0, size = SIZE_1)
50 public abstract class PhiNode extends FloatingNode implements Canonicalizable {
51
52 public static final NodeClass<PhiNode> TYPE = NodeClass.create(PhiNode.class);
53 @Input(Association) protected AbstractMergeNode merge;
54
55 protected PhiNode(NodeClass<? extends PhiNode> c, Stamp stamp, AbstractMergeNode merge) {
56 super(c, stamp);
57 this.merge = merge;
58 }
59
60 public abstract NodeInputList<ValueNode> values();
61
62 public AbstractMergeNode merge() {
63 return merge;
64 }
65
66 public void setMerge(AbstractMergeNode x) {
67 updateUsages(merge, x);
68 merge = x;
69 }
70
71 @Override
72 public boolean verify() {
73 assertTrue(merge() != null, "missing merge");
74 assertTrue(merge().phiPredecessorCount() == valueCount(), "mismatch between merge predecessor count and phi value count: %d != %d", merge().phiPredecessorCount(), valueCount());
75 return super.verify();
76 }
77
78 /**
79 * Get the instruction that produces the value associated with the i'th predecessor of the
80 * merge.
81 *
82 * @param i the index of the predecessor
83 * @return the instruction that produced the value in the i'th predecessor
84 */
85 public ValueNode valueAt(int i) {
86 return values().get(i);
87 }
88
89 /**
90 * Sets the value at the given index and makes sure that the values list is large enough.
91 *
92 * @param i the index at which to set the value
93 * @param x the new phi input value for the given location
94 */
95 public void initializeValueAt(int i, ValueNode x) {
96 while (values().size() <= i) {
97 values().add(null);
98 }
99 values().set(i, x);
100 }
101
102 public void setValueAt(int i, ValueNode x) {
103 values().set(i, x);
104 }
105
106 public void setValueAt(AbstractEndNode end, ValueNode x) {
107 setValueAt(merge().phiPredecessorIndex(end), x);
108 }
109
110 public ValueNode valueAt(AbstractEndNode pred) {
111 return valueAt(merge().phiPredecessorIndex(pred));
112 }
113
114 /**
115 * Get the number of inputs to this phi (i.e. the number of predecessors to the merge).
116 *
117 * @return the number of inputs in this phi
118 */
119 public int valueCount() {
120 return values().size();
121 }
122
123 public void clearValues() {
124 values().clear();
125 }
126
127 @Override
128 public String toString(Verbosity verbosity) {
129 if (verbosity == Verbosity.Name) {
130 StringBuilder str = new StringBuilder();
131 for (int i = 0; i < valueCount(); ++i) {
132 if (i != 0) {
133 str.append(' ');
134 }
135 str.append(valueAt(i) == null ? "-" : valueAt(i).toString(Verbosity.Id));
136 }
137 return super.toString(Verbosity.Name) + "(" + str + ")";
138 } else {
139 return super.toString(verbosity);
140 }
141 }
142
143 public void addInput(ValueNode x) {
144 assert !(x instanceof ValuePhiNode) || ((ValuePhiNode) x).merge() instanceof LoopBeginNode || ((ValuePhiNode) x).merge() != this.merge();
145 assert !(this instanceof ValuePhiNode) || x.stamp().isCompatible(stamp());
146 values().add(x);
147 }
148
149 public void removeInput(int index) {
150 values().remove(index);
151 }
152
153 public NodeIterable<ValueNode> backValues() {
154 return values().subList(merge().forwardEndCount());
155 }
156
157 @NodeInfo
158 static final class MultipleValuesNode extends ValueNode {
159
160 public static final NodeClass<MultipleValuesNode> TYPE = NodeClass.create(MultipleValuesNode.class);
161
162 protected MultipleValuesNode() {
163 super(TYPE, null);
164 }
165
166 }
167
168 public static final ValueNode MULTIPLE_VALUES = new MultipleValuesNode();
169
170 /**
171 * If all inputs are the same value, this value is returned, otherwise {@link #MULTIPLE_VALUES}.
172 * Note that {@code null} is a valid return value, since {@link GuardPhiNode}s can have
173 * {@code null} inputs.
174 */
175 public ValueNode singleValue() {
176 ValueNode singleValue = valueAt(0);
177 int count = valueCount();
178 for (int i = 1; i < count; ++i) {
179 ValueNode value = valueAt(i);
180 if (value != this) {
181 if (value != singleValue) {
182 return MULTIPLE_VALUES;
183 }
184 }
185 }
186 return singleValue;
187 }
188
189 /**
190 * If all inputs (but the first one) are the same value, this value is returned, otherwise
191 * {@link #MULTIPLE_VALUES}. Note that {@code null} is a valid return value, since
192 * {@link GuardPhiNode}s can have {@code null} inputs.
193 */
194 public ValueNode singleBackValue() {
195 assert merge() instanceof LoopBeginNode;
196 Iterator<ValueNode> iterator = values().iterator();
197 iterator.next();
198 ValueNode singleValue = iterator.next();
199 while (iterator.hasNext()) {
200 if (iterator.next() != singleValue) {
201 return MULTIPLE_VALUES;
202 }
203 }
204 return singleValue;
205 }
206
207 @Override
208 public ValueNode canonical(CanonicalizerTool tool) {
209
210 if (isLoopPhi()) {
211 if (singleBackValue() == this) {
212 return firstValue();
213 }
214
215 boolean onlySelfUsage = true;
216 for (Node n : this.usages()) {
217 if (n != this) {
218 onlySelfUsage = false;
219 break;
220 }
221 }
222
223 if (onlySelfUsage) {
224 return null;
225 }
226 }
227
228 ValueNode singleValue = singleValue();
229 if (singleValue != MULTIPLE_VALUES) {
230 return singleValue;
231 }
232 return this;
233 }
234
235 public ValueNode firstValue() {
236 return valueAt(0);
237 }
238
239 public boolean isLoopPhi() {
240 return merge() instanceof LoopBeginNode;
241 }
242
243 public boolean hasValidInput() {
244 for (ValueNode n : values()) {
245 if (n != null) {
246 return true;
247 }
248 }
249 return false;
250 }
251 }