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