1 /*
2 * Copyright (c) 2015, 2015, 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.lir.ssi;
24
25 import java.util.Arrays;
26 import java.util.List;
27
28 import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
29 import org.graalvm.compiler.lir.LIR;
30 import org.graalvm.compiler.lir.LIRInstruction;
31 import org.graalvm.compiler.lir.LIRInstruction.OperandMode;
32 import org.graalvm.compiler.lir.StandardOp.BlockEndOp;
33 import org.graalvm.compiler.lir.StandardOp.LabelOp;
34 import org.graalvm.compiler.lir.ValueConsumer;
35 import org.graalvm.compiler.lir.ssa.SSAUtil.PhiValueVisitor;
36
37 import jdk.vm.ci.meta.Value;
38
39 /**
40 * Utilities for working with Static-Single-Information LIR form.
41 *
42 * <h2>Representation of φ and σ</h2>
43 *
44 * There are no explicit φ/σ {@link LIRInstruction}s. Instead, they are implemented as
45 * parallel copy that spans across a control-flow edge.
46 *
47 * The variables introduced by φ/σ of a specific {@linkplain AbstractBlockBase block} are
48 * {@linkplain LabelOp#setIncomingValues attached} to the {@link LabelOp} of the block. The outgoing
49 * values from the predecessor are {@linkplain BlockEndOp#setOutgoingValues input} to the
50 * {@link BlockEndOp} of the predecessor.
51 *
52 * When it does not matter whether we are talking about a φ or a σ we call the values that
53 * are defined by a label {@linkplain LabelOp#setIncomingValues incoming} and the values that are
54 * input to the {@link BlockEndOp} of the predecessor {@linkplain BlockEndOp#setOutgoingValues
55 * outgoing}.
56 *
57 * <h2>Implementation Details</h2>
58 *
59 * For our purposes we want a <em>maximal</em> SSI form, which means that all values that are alive
60 * across basic block boundaries are gated with a φ/σ. In other words the outgoing and
61 * incoming values of the {@link BlockEndOp} and {@link LabelOp} are equivalent to the live-out and
62 * live-in set of the corresponding block.
63 *
64 * As a side effect variables are local to a block. We reuse the name of the predecessor if they
65 * represent the same value (i.e. not a real φ definition).
66 *
67 * <h2>Examples</h2>
68 *
69 * <h3>Merge (φ)</h3>
70 *
71 * <pre>
72 * B0 -> B1
73 * ...
74 * v0|i = ...
75 * JUMP ~[v0|i, int[0|0x0]] destination: B0 -> B1
76 * ________________________________________________
77 *
78 * B2 -> B1
79 * ...
80 * v1|i = ...
81 * v2|i = ...
82 * JUMP ~[v1|i, v2|i] destination: B2 -> B1
83 * ________________________________________________
84 *
85 * B1 <- B0,B2
86 * [v3|i, v4|i] = LABEL
87 * ...
88 * </pre>
89 *
90 * Note: the outgoing values of a block can contain constants (see <code>B0</code>).
91 *
92 * <h3>Split (σ)</h3>
93 *
94 * <pre>
95 * B0 -> B1,B2
96 * ...
97 * v0|i = ...
98 * v1|i = ...
99 * v2|i = ...
100 * TEST (x: v1|i, y: v1|i)
101 * BRANCH ~[v2|i, v0|j] condition: <, true: B1 false: B2
102 * ________________________________________________
103 *
104 * B1 <- B0
105 * [-, v0|j] = LABEL
106 * ...
107 * ________________________________________________
108 *
109 * B2 <- B0
110 * [v2|i, v0|j] = LABEL
111 * ...
112 * </pre>
113 *
114 * Note: If a incoming value is not needed in a branch it is {@link Value#ILLEGAL ignored} (see
115 * <code>B1<code>).
116 */
117 public final class SSIUtil {
118
119 public static BlockEndOp outgoing(LIR lir, AbstractBlockBase<?> block) {
120 return (BlockEndOp) outgoingInst(lir, block);
121 }
122
123 public static LIRInstruction outgoingInst(LIR lir, AbstractBlockBase<?> block) {
124 List<LIRInstruction> instructions = lir.getLIRforBlock(block);
125 int index = instructions.size() - 1;
126 LIRInstruction op = instructions.get(index);
127 return op;
128 }
129
130 public static LabelOp incoming(LIR lir, AbstractBlockBase<?> block) {
131 return (LabelOp) incomingInst(lir, block);
132 }
133
134 private static LIRInstruction incomingInst(LIR lir, AbstractBlockBase<?> block) {
135 return lir.getLIRforBlock(block).get(0);
136 }
137
138 public static void removeIncoming(LIR lir, AbstractBlockBase<?> block) {
139 incoming(lir, block).clearIncomingValues();
140 }
141
142 public static void removeOutgoing(LIR lir, AbstractBlockBase<?> block) {
143 outgoing(lir, block).clearOutgoingValues();
144 }
145
146 /**
147 * Visits each SIGMA/PHI value pair of an edge, i.e. the outgoing value from the predecessor and
148 * the incoming value to the merge block.
149 */
150 public static void forEachValuePair(LIR lir, AbstractBlockBase<?> toBlock, AbstractBlockBase<?> fromBlock, PhiValueVisitor visitor) {
151 assert Arrays.asList(toBlock.getPredecessors()).contains(fromBlock) : String.format("%s not in predecessor list: %s", fromBlock, Arrays.toString(toBlock.getPredecessors()));
152 assert fromBlock.getSuccessorCount() == 1 || toBlock.getPredecessorCount() == 1 : String.format("Critical Edge? %s has %d successors and %s has %d predecessors", fromBlock,
153 fromBlock.getSuccessorCount(), toBlock, toBlock.getPredecessorCount());
154 assert Arrays.asList(fromBlock.getSuccessors()).contains(toBlock) : String.format("Predecessor block %s has wrong successor: %s, should contain: %s", fromBlock,
155 Arrays.toString(fromBlock.getSuccessors()), toBlock);
156
157 BlockEndOp blockEnd = outgoing(lir, fromBlock);
158 LabelOp label = incoming(lir, toBlock);
159
160 assert label.getIncomingSize() == blockEnd.getOutgoingSize() : String.format("In/Out size mismatch: in=%d vs. out=%d, blocks %s vs. %s", label.getIncomingSize(), blockEnd.getOutgoingSize(),
161 toBlock, fromBlock);
162 assert label.getPhiSize() == blockEnd.getPhiSize() : String.format("Phi In/Out size mismatch: in=%d vs. out=%d", label.getPhiSize(), blockEnd.getPhiSize());
163
164 for (int i = 0; i < label.getIncomingSize(); i++) {
165 visitor.visit(label.getIncomingValue(i), blockEnd.getOutgoingValue(i));
166 }
167 }
168
169 public static void forEachRegisterHint(LIR lir, AbstractBlockBase<?> block, LabelOp label, Value targetValue, OperandMode mode, ValueConsumer valueConsumer) {
170 assert mode == OperandMode.DEF : "Wrong operand mode: " + mode;
171 assert lir.getLIRforBlock(block).get(0).equals(label) : String.format("Block %s and Label %s do not match!", block, label);
172
173 if (!label.isPhiIn()) {
174 return;
175 }
176 int idx = indexOfValue(label, targetValue);
177 assert idx >= 0 : String.format("Value %s not in label %s", targetValue, label);
178
179 for (AbstractBlockBase<?> pred : block.getPredecessors()) {
180 BlockEndOp blockEnd = outgoing(lir, pred);
181 Value sourceValue = blockEnd.getOutgoingValue(idx);
182 valueConsumer.visitValue((LIRInstruction) blockEnd, sourceValue, null, null);
183 }
184
185 }
186
187 private static int indexOfValue(LabelOp label, Value value) {
188 for (int i = 0; i < label.getIncomingSize(); i++) {
189 if (label.getIncomingValue(i).equals(value)) {
190 return i;
191 }
192 }
193 return -1;
194 }
195
196 }