1 /*
2 * Copyright (c) 2009, 2011, 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_0;
28
29 import java.util.List;
30
31 import org.graalvm.compiler.debug.Debug;
32 import org.graalvm.compiler.graph.IterableNodeType;
33 import org.graalvm.compiler.graph.Node;
34 import org.graalvm.compiler.graph.NodeClass;
35 import org.graalvm.compiler.graph.NodeInputList;
36 import org.graalvm.compiler.graph.iterators.NodeIterable;
37 import org.graalvm.compiler.graph.spi.Simplifiable;
38 import org.graalvm.compiler.graph.spi.SimplifierTool;
39 import org.graalvm.compiler.nodeinfo.NodeInfo;
40 import org.graalvm.compiler.nodes.spi.LIRLowerable;
41 import org.graalvm.compiler.nodes.spi.NodeLIRBuilderTool;
42 import org.graalvm.compiler.nodes.util.GraphUtil;
43
44 /**
45 * Denotes the merging of multiple control-flow paths.
46 */
47 @NodeInfo(allowedUsageTypes = Association, cycles = CYCLES_0, size = SIZE_0)
48 public abstract class AbstractMergeNode extends BeginStateSplitNode implements IterableNodeType, Simplifiable, LIRLowerable {
49 public static final NodeClass<AbstractMergeNode> TYPE = NodeClass.create(AbstractMergeNode.class);
50
51 protected AbstractMergeNode(NodeClass<? extends AbstractMergeNode> c) {
52 super(c);
53 }
54
55 @Input(Association) protected NodeInputList<EndNode> ends = new NodeInputList<>(this);
56
57 @Override
58 public void generate(NodeLIRBuilderTool gen) {
59 gen.visitMerge(this);
60 }
61
62 public int forwardEndIndex(EndNode end) {
63 return ends.indexOf(end);
64 }
65
66 public void addForwardEnd(EndNode end) {
67 ends.add(end);
68 }
69
70 public final int forwardEndCount() {
71 return ends.size();
72 }
73
74 public final EndNode forwardEndAt(int index) {
75 return ends.get(index);
76 }
77
78 @Override
79 public NodeIterable<EndNode> cfgPredecessors() {
80 return ends;
81 }
82
83 /**
84 * Determines if a given node is a phi whose {@linkplain PhiNode#merge() merge} is this node.
85 *
86 * @param value the instruction to test
87 * @return {@code true} if {@code value} is a phi and its merge is {@code this}
88 */
89 public boolean isPhiAtMerge(Node value) {
90 return value instanceof PhiNode && ((PhiNode) value).merge() == this;
91 }
92
93 /**
94 * Removes the given end from the merge, along with the entries corresponding to this end in the
95 * phis connected to the merge.
96 *
97 * @param pred the end to remove
98 */
99 public void removeEnd(AbstractEndNode pred) {
100 int predIndex = phiPredecessorIndex(pred);
101 assert predIndex != -1;
102 deleteEnd(pred);
103 for (PhiNode phi : phis().snapshot()) {
104 if (phi.isDeleted()) {
105 continue;
106 }
107 ValueNode removedValue = phi.valueAt(predIndex);
108 phi.removeInput(predIndex);
109 if (removedValue != null && removedValue.isAlive() && removedValue.hasNoUsages() && GraphUtil.isFloatingNode(removedValue)) {
110 GraphUtil.killWithUnusedFloatingInputs(removedValue);
111 }
112 }
113 }
114
115 protected void deleteEnd(AbstractEndNode end) {
116 ends.remove(end);
117 }
118
119 public void clearEnds() {
120 ends.clear();
121 }
122
123 public NodeInputList<EndNode> forwardEnds() {
124 return ends;
125 }
126
127 public int phiPredecessorCount() {
128 return forwardEndCount();
129 }
130
131 public int phiPredecessorIndex(AbstractEndNode pred) {
132 return forwardEndIndex((EndNode) pred);
133 }
134
135 public AbstractEndNode phiPredecessorAt(int index) {
136 return forwardEndAt(index);
137 }
138
139 public NodeIterable<PhiNode> phis() {
140 return this.usages().filter(PhiNode.class).filter(this::isPhiAtMerge);
141 }
142
143 public NodeIterable<ValuePhiNode> valuePhis() {
144 return this.usages().filter(ValuePhiNode.class).filter(this::isPhiAtMerge);
145 }
146
147 @Override
148 public NodeIterable<Node> anchored() {
149 return super.anchored().filter(n -> !isPhiAtMerge(n));
150 }
151
152 /**
153 * This simplify method can deal with a null value for tool, so that it can be used outside of
154 * canonicalization.
155 */
156 @Override
157 public void simplify(SimplifierTool tool) {
158 FixedNode currentNext = next();
159 if (currentNext instanceof AbstractEndNode) {
160 AbstractEndNode origLoopEnd = (AbstractEndNode) currentNext;
161 AbstractMergeNode merge = origLoopEnd.merge();
162 if (merge instanceof LoopBeginNode && !(origLoopEnd instanceof LoopEndNode)) {
163 return;
164 }
165 // in order to move anchored values to the other merge we would need to check if the
166 // anchors are used by phis of the other merge
167 if (this.anchored().isNotEmpty()) {
168 return;
169 }
170 if (merge.stateAfter() == null && this.stateAfter() != null) {
171 // We hold a state, but the succeeding merge does not => do not combine.
172 return;
173 }
174 for (PhiNode phi : phis()) {
175 for (Node usage : phi.usages()) {
176 if (!(usage instanceof VirtualState) && !merge.isPhiAtMerge(usage)) {
177 return;
178 }
179 }
180 }
181 Debug.log("Split %s into ends for %s.", this, merge);
182 int numEnds = this.forwardEndCount();
183 for (int i = 0; i < numEnds - 1; i++) {
184 AbstractEndNode end = forwardEndAt(numEnds - 1 - i);
185 if (tool != null) {
186 tool.addToWorkList(end);
187 }
188 AbstractEndNode newEnd;
189 if (merge instanceof LoopBeginNode) {
190 newEnd = graph().add(new LoopEndNode((LoopBeginNode) merge));
191 } else {
192 EndNode tmpEnd = graph().add(new EndNode());
193 merge.addForwardEnd(tmpEnd);
194 newEnd = tmpEnd;
195 }
196 for (PhiNode phi : merge.phis()) {
197 ValueNode v = phi.valueAt(origLoopEnd);
198 ValueNode newInput;
199 if (isPhiAtMerge(v)) {
200 PhiNode endPhi = (PhiNode) v;
201 newInput = endPhi.valueAt(end);
202 } else {
203 newInput = v;
204 }
205 phi.addInput(newInput);
206 }
207 this.removeEnd(end);
208 end.replaceAtPredecessor(newEnd);
209 end.safeDelete();
210 if (tool != null) {
211 tool.addToWorkList(newEnd.predecessor());
212 }
213 }
214 graph().reduceTrivialMerge(this);
215 } else if (currentNext instanceof ReturnNode) {
216 ReturnNode returnNode = (ReturnNode) currentNext;
217 if (anchored().isNotEmpty() || returnNode.getMemoryMap() != null) {
218 return;
219 }
220 List<PhiNode> phis = phis().snapshot();
221 for (PhiNode phi : phis) {
222 for (Node usage : phi.usages()) {
223 if (usage != returnNode && !(usage instanceof FrameState)) {
224 return;
225 }
226 }
227 }
228
229 ValuePhiNode returnValuePhi = returnNode.result() == null || !isPhiAtMerge(returnNode.result()) ? null : (ValuePhiNode) returnNode.result();
230 List<EndNode> endNodes = forwardEnds().snapshot();
231 for (EndNode end : endNodes) {
232 ReturnNode newReturn = graph().add(new ReturnNode(returnValuePhi == null ? returnNode.result() : returnValuePhi.valueAt(end)));
233 if (tool != null) {
234 tool.addToWorkList(end.predecessor());
235 }
236 end.replaceAtPredecessor(newReturn);
237 }
238 GraphUtil.killCFG(this);
239 for (EndNode end : endNodes) {
240 end.safeDelete();
241 }
242 for (PhiNode phi : phis) {
243 if (tool.allUsagesAvailable() && phi.isAlive() && phi.hasNoUsages()) {
244 GraphUtil.killWithUnusedFloatingInputs(phi);
245 }
246 }
247 }
248 }
249 }