001/*
002 * Copyright (c) 2015, 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.lir.ssi;
024
025import java.util.*;
026
027import jdk.internal.jvmci.meta.*;
028
029import com.oracle.graal.compiler.common.cfg.*;
030import com.oracle.graal.lir.*;
031import com.oracle.graal.lir.StandardOp.BlockEndOp;
032import com.oracle.graal.lir.LIRInstruction.*;
033import com.oracle.graal.lir.StandardOp.*;
034import com.oracle.graal.lir.ssa.SSAUtil.*;
035
036/**
037 * Utilities for working with Static-Single-Information LIR form.
038 *
039 * <h2>Representation of &phi; and &sigma;</h2>
040 *
041 * There are no explicit &phi;/&sigma; {@link LIRInstruction}s. Instead, they are implemented as
042 * parallel copy that spans across a control-flow edge.
043 *
044 * The variables introduced by &phi;/&sigma; of a specific {@linkplain AbstractBlockBase block} are
045 * {@linkplain LabelOp#setIncomingValues attached} to the {@link LabelOp} of the block. The outgoing
046 * values from the predecessor are {@linkplain BlockEndOp#setOutgoingValues input} to the
047 * {@link BlockEndOp} of the predecessor.
048 *
049 * When it does not matter whether we are talking about a &phi; or a &sigma; we call the values that
050 * are defined by a label {@linkplain LabelOp#setIncomingValues incoming} and the values that are
051 * input to the {@link BlockEndOp} of the predecessor {@linkplain BlockEndOp#setOutgoingValues
052 * outgoing}.
053 *
054 * <h2>Implementation Details</h2>
055 *
056 * For our purposes we want a <em>maximal</em> SSI form, which means that all values that are alive
057 * across basic block boundaries are gated with a &phi;/&sigma;. In other words the outgoing and
058 * incoming values of the {@link BlockEndOp} and {@link LabelOp} are equivalent to the live-out and
059 * live-in set of the corresponding block.
060 *
061 * As a side effect variables are local to a block. We reuse the name of the predecessor if they
062 * represent the same value (i.e. not a real &phi; definition).
063 *
064 * <h2>Examples</h2>
065 *
066 * <h3>Merge (&phi;)</h3>
067 *
068 * <pre>
069 * B0 -> B1
070 *   ...
071 *   v0|i = ...
072 *   JUMP ~[v0|i, int[0|0x0]] destination: B0 -> B1
073 * ________________________________________________
074 *
075 * B2 -> B1
076 *   ...
077 *   v1|i = ...
078 *   v2|i = ...
079 *   JUMP ~[v1|i, v2|i] destination: B2 -> B1
080 * ________________________________________________
081 *
082 * B1 <- B0,B2
083 *   [v3|i, v4|i] = LABEL
084 *   ...
085 * </pre>
086 *
087 * Note: the outgoing values of a block can contain constants (see <code>B0</code>).
088 *
089 * <h3>Split (&sigma;)</h3>
090 *
091 * <pre>
092 * B0 -> B1,B2
093 *   ...
094 *   v0|i = ...
095 *   v1|i = ...
096 *   v2|i = ...
097 *   TEST (x: v1|i, y: v1|i)
098 *   BRANCH ~[v2|i, v0|j] condition: <, true: B1 false: B2
099 * ________________________________________________
100 *
101 * B1 <- B0
102 *   [-, v0|j] = LABEL
103 *   ...
104 * ________________________________________________
105 *
106 * B2 <- B0
107 *   [v2|i, v0|j] = LABEL
108 *   ...
109 * </pre>
110 *
111 * Note: If a incoming value is not needed in a branch it is {@link Value#ILLEGAL ignored} (see
112 * <code>B1<code>).
113 */
114public final class SSIUtil {
115
116    public static BlockEndOp outgoing(LIR lir, AbstractBlockBase<?> block) {
117        return (BlockEndOp) outgoingInst(lir, block);
118    }
119
120    public static LIRInstruction outgoingInst(LIR lir, AbstractBlockBase<?> block) {
121        List<LIRInstruction> instructions = lir.getLIRforBlock(block);
122        int index = instructions.size() - 1;
123        LIRInstruction op = instructions.get(index);
124        return op;
125    }
126
127    public static LabelOp incoming(LIR lir, AbstractBlockBase<?> block) {
128        return (LabelOp) incomingInst(lir, block);
129    }
130
131    private static LIRInstruction incomingInst(LIR lir, AbstractBlockBase<?> block) {
132        return lir.getLIRforBlock(block).get(0);
133    }
134
135    public static void removeIncoming(LIR lir, AbstractBlockBase<?> block) {
136        incoming(lir, block).clearIncomingValues();
137    }
138
139    public static void removeOutgoing(LIR lir, AbstractBlockBase<?> block) {
140        outgoing(lir, block).clearOutgoingValues();
141    }
142
143    /**
144     * Visits each SIGMA/PHI value pair of an edge, i.e. the outgoing value from the predecessor and
145     * the incoming value to the merge block.
146     */
147    public static void forEachValuePair(LIR lir, AbstractBlockBase<?> toBlock, AbstractBlockBase<?> fromBlock, PhiValueVisitor visitor) {
148        assert toBlock.getPredecessors().contains(fromBlock) : String.format("%s not in predecessor list: %s", fromBlock, toBlock.getPredecessors());
149        assert fromBlock.getSuccessorCount() == 1 || toBlock.getPredecessorCount() == 1 : String.format("Critical Edge? %s has %d successors and %s has %d predecessors", fromBlock,
150                        fromBlock.getSuccessorCount(), toBlock, toBlock.getPredecessorCount());
151        assert fromBlock.getSuccessors().contains(toBlock) : String.format("Predecessor block %s has wrong successor: %s, should contain: %s", fromBlock, fromBlock.getSuccessors(), toBlock);
152
153        BlockEndOp blockEnd = outgoing(lir, fromBlock);
154        LabelOp label = incoming(lir, toBlock);
155
156        assert label.getIncomingSize() == blockEnd.getOutgoingSize() : String.format("In/Out size mismatch: in=%d vs. out=%d, blocks %s vs. %s", label.getIncomingSize(), blockEnd.getOutgoingSize(),
157                        toBlock, fromBlock);
158
159        for (int i = 0; i < label.getIncomingSize(); i++) {
160            visitor.visit(label.getIncomingValue(i), blockEnd.getOutgoingValue(i));
161        }
162    }
163
164    public static void forEachRegisterHint(LIR lir, AbstractBlockBase<?> block, LabelOp label, Value targetValue, OperandMode mode, ValueConsumer valueConsumer) {
165        assert mode == OperandMode.DEF : "Wrong operand mode: " + mode;
166        assert lir.getLIRforBlock(block).get(0).equals(label) : String.format("Block %s and Label %s do not match!", block, label);
167
168        if (!label.isPhiIn()) {
169            return;
170        }
171        int idx = indexOfValue(label, targetValue);
172        assert idx >= 0 : String.format("Value %s not in label %s", targetValue, label);
173
174        for (AbstractBlockBase<?> pred : block.getPredecessors()) {
175            BlockEndOp blockEnd = outgoing(lir, pred);
176            Value sourceValue = blockEnd.getOutgoingValue(idx);
177            valueConsumer.visitValue((LIRInstruction) blockEnd, sourceValue, null, null);
178        }
179
180    }
181
182    private static int indexOfValue(LabelOp label, Value value) {
183        for (int i = 0; i < label.getIncomingSize(); i++) {
184            if (label.getIncomingValue(i).equals(value)) {
185                return i;
186            }
187        }
188        return -1;
189    }
190
191}