Source code

001/*
002 * Copyright (c) 2009, 2011, 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 static com.oracle.graal.graph.iterators.NodePredicates.*;
026
027import java.util.*;
028
029import com.oracle.graal.debug.*;
030
031import com.oracle.graal.graph.*;
032import com.oracle.graal.graph.iterators.*;
033import com.oracle.graal.graph.spi.*;
034import com.oracle.graal.nodeinfo.*;
035import com.oracle.graal.nodes.spi.*;
036import com.oracle.graal.nodes.util.*;
037
038/**
039 * Denotes the merging of multiple control-flow paths.
040 */
041@NodeInfo(allowedUsageTypes = {InputType.Association})
042public abstract class AbstractMergeNode extends BeginStateSplitNode implements IterableNodeType, LIRLowerable {
043    public static final NodeClass<AbstractMergeNode> TYPE = NodeClass.create(AbstractMergeNode.class);
044
045    protected AbstractMergeNode(NodeClass<? extends AbstractMergeNode> c) {
046        super(c);
047    }
048
049    @Input(InputType.Association) protected NodeInputList<EndNode> ends = new NodeInputList<>(this);
050
051    @Override
052    public void generate(NodeLIRBuilderTool gen) {
053        gen.visitMerge(this);
054    }
055
056    public int forwardEndIndex(EndNode end) {
057        return ends.indexOf(end);
058    }
059
060    public void addForwardEnd(EndNode end) {
061        ends.add(end);
062    }
063
064    public int forwardEndCount() {
065        return ends.size();
066    }
067
068    public EndNode forwardEndAt(int index) {
069        return ends.get(index);
070    }
071
072    @Override
073    public NodeIterable<EndNode> cfgPredecessors() {
074        return ends;
075    }
076
077    /**
078     * Determines if a given node is a phi whose {@linkplain PhiNode#merge() merge} is this node.
079     *
080     * @param value the instruction to test
081     * @return {@code true} if {@code value} is a phi and its merge is {@code this}
082     */
083    public boolean isPhiAtMerge(Node value) {
084        return value instanceof PhiNode && ((PhiNode) value).merge() == this;
085    }
086
087    /**
088     * Removes the given end from the merge, along with the entries corresponding to this end in the
089     * phis connected to the merge.
090     *
091     * @param pred the end to remove
092     */
093    public void removeEnd(AbstractEndNode pred) {
094        int predIndex = phiPredecessorIndex(pred);
095        assert predIndex != -1;
096        deleteEnd(pred);
097        for (PhiNode phi : phis().snapshot()) {
098            if (phi.isDeleted()) {
099                continue;
100            }
101            ValueNode removedValue = phi.valueAt(predIndex);
102            phi.removeInput(predIndex);
103            if (removedValue != null && removedValue.isAlive() && removedValue.hasNoUsages() && GraphUtil.isFloatingNode().apply(removedValue)) {
104                GraphUtil.killWithUnusedFloatingInputs(removedValue);
105            }
106        }
107    }
108
109    protected void deleteEnd(AbstractEndNode end) {
110        ends.remove(end);
111    }
112
113    public void clearEnds() {
114        ends.clear();
115    }
116
117    public NodeInputList<EndNode> forwardEnds() {
118        return ends;
119    }
120
121    public int phiPredecessorCount() {
122        return forwardEndCount();
123    }
124
125    public int phiPredecessorIndex(AbstractEndNode pred) {
126        return forwardEndIndex((EndNode) pred);
127    }
128
129    public AbstractEndNode phiPredecessorAt(int index) {
130        return forwardEndAt(index);
131    }
132
133    public NodeIterable<PhiNode> phis() {
134        return this.usages().filter(PhiNode.class).filter(this::isPhiAtMerge);
135    }
136
137    public NodeIterable<ValuePhiNode> valuePhis() {
138        return this.usages().filter(ValuePhiNode.class).filter(this::isPhiAtMerge);
139    }
140
141    @Override
142    public NodeIterable<Node> anchored() {
143        return super.anchored().filter(n -> !isPhiAtMerge(n));
144    }
145
146    /**
147     * This simplify method can deal with a null value for tool, so that it can be used outside of
148     * canonicalization.
149     */
150    @Override
151    public void simplify(SimplifierTool tool) {
152        FixedNode currentNext = next();
153        if (currentNext instanceof AbstractEndNode) {
154            AbstractEndNode origLoopEnd = (AbstractEndNode) currentNext;
155            AbstractMergeNode merge = origLoopEnd.merge();
156            if (merge instanceof LoopBeginNode && !(origLoopEnd instanceof LoopEndNode)) {
157                return;
158            }
159            // in order to move anchored values to the other merge we would need to check if the
160            // anchors are used by phis of the other merge
161            if (this.anchored().isNotEmpty()) {
162                return;
163            }
164            if (merge.stateAfter() == null && this.stateAfter() != null) {
165                // We hold a state, but the succeeding merge does not => do not combine.
166                return;
167            }
168            for (PhiNode phi : phis()) {
169                if (phi.usages().filter(isNotA(VirtualState.class)).and(node -> !merge.isPhiAtMerge(node)).isNotEmpty()) {
170                    return;
171                }
172            }
173            Debug.log("Split %s into ends for %s.", this, merge);
174            int numEnds = this.forwardEndCount();
175            for (int i = 0; i < numEnds - 1; i++) {
176                AbstractEndNode end = forwardEndAt(numEnds - 1 - i);
177                if (tool != null) {
178                    tool.addToWorkList(end);
179                }
180                AbstractEndNode newEnd;
181                if (merge instanceof LoopBeginNode) {
182                    newEnd = graph().add(new LoopEndNode((LoopBeginNode) merge));
183                } else {
184                    EndNode tmpEnd = graph().add(new EndNode());
185                    merge.addForwardEnd(tmpEnd);
186                    newEnd = tmpEnd;
187                }
188                for (PhiNode phi : merge.phis()) {
189                    ValueNode v = phi.valueAt(origLoopEnd);
190                    ValueNode newInput;
191                    if (isPhiAtMerge(v)) {
192                        PhiNode endPhi = (PhiNode) v;
193                        newInput = endPhi.valueAt(end);
194                    } else {
195                        newInput = v;
196                    }
197                    phi.addInput(newInput);
198                }
199                this.removeEnd(end);
200                end.replaceAtPredecessor(newEnd);
201                end.safeDelete();
202                if (tool != null) {
203                    tool.addToWorkList(newEnd.predecessor());
204                }
205            }
206            graph().reduceTrivialMerge(this);
207        } else if (currentNext instanceof ReturnNode) {
208            ReturnNode returnNode = (ReturnNode) currentNext;
209            if (anchored().isNotEmpty() || returnNode.getMemoryMap() != null) {
210                return;
211            }
212            List<PhiNode> phis = phis().snapshot();
213            for (PhiNode phi : phis) {
214                for (Node usage : phi.usages().filter(isNotA(FrameState.class))) {
215                    if (usage != returnNode) {
216                        return;
217                    }
218                }
219            }
220
221            ValuePhiNode returnValuePhi = returnNode.result() == null || !isPhiAtMerge(returnNode.result()) ? null : (ValuePhiNode) returnNode.result();
222            List<EndNode> endNodes = forwardEnds().snapshot();
223            for (EndNode end : endNodes) {
224                ReturnNode newReturn = graph().add(new ReturnNode(returnValuePhi == null ? returnNode.result() : returnValuePhi.valueAt(end)));
225                if (tool != null) {
226                    tool.addToWorkList(end.predecessor());
227                }
228                end.replaceAtPredecessor(newReturn);
229            }
230            GraphUtil.killCFG(this);
231            for (EndNode end : endNodes) {
232                end.safeDelete();
233            }
234            for (PhiNode phi : phis) {
235                if (tool.allUsagesAvailable() && phi.isAlive() && phi.hasNoUsages()) {
236                    GraphUtil.killWithUnusedFloatingInputs(phi);
237                }
238            }
239        }
240    }
241}