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.ssa;
24
25 import java.util.Arrays;
26 import java.util.List;
27
28 import org.graalvm.compiler.core.common.LIRKind;
29 import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
30 import org.graalvm.compiler.lir.LIR;
31 import org.graalvm.compiler.lir.LIRInstruction;
32 import org.graalvm.compiler.lir.LIRInstruction.OperandMode;
33 import org.graalvm.compiler.lir.StandardOp.BlockEndOp;
34 import org.graalvm.compiler.lir.StandardOp.JumpOp;
35 import org.graalvm.compiler.lir.StandardOp.LabelOp;
36 import org.graalvm.compiler.lir.ValueConsumer;
37
38 import jdk.vm.ci.meta.Value;
39
40 /**
41 * Utilities for working with Static-Single-Assignment LIR form.
42 *
43 * <h2>Representation of <code>PHI</code>s</h2>
44 *
45 * There is no explicit <code>PHI</code> {@linkplain LIRInstruction}. Instead, they are implemented
46 * as parallel copy that span across a control-flow edge.
47 *
48 * The variables introduced by <code>PHI</code>s of a specific {@linkplain AbstractBlockBase merge
49 * block} are {@linkplain LabelOp#setIncomingValues attached} to the {@linkplain LabelOp} of the
50 * block. The outgoing values from the predecessor are {@link JumpOp#setOutgoingValues input} to the
51 * {@linkplain BlockEndOp} of the predecessor. Because there are no critical edges we know that the
52 * {@link BlockEndOp} of the predecessor has to be a {@link JumpOp}.
53 *
54 * <h3>Example:</h3>
55 *
56 * <pre>
57 * B0 -> B1
58 * ...
59 * v0|i = ...
60 * JUMP ~[v0|i, int[0|0x0]] destination: B0 -> B1
61 * ________________________________________________
62 *
63 * B2 -> B1
64 * ...
65 * v1|i = ...
66 * v2|i = ...
67 * JUMP ~[v1|i, v2|i] destination: B2 -> B1
68 * ________________________________________________
69 *
70 * B1 <- B0,B2
71 * [v3|i, v4|i] = LABEL
72 * ...
73 * </pre>
74 */
75 public final class SSAUtil {
76
77 public interface PhiValueVisitor {
78 /**
79 * @param phiIn the incoming value at the merge block
80 * @param phiOut the outgoing value from the predecessor block
81 */
82 void visit(Value phiIn, Value phiOut);
83 }
84
85 /**
86 * Visits each phi value pair of an edge, i.e. the outgoing value from the predecessor and the
87 * incoming value to the merge block.
88 */
89 public static void forEachPhiValuePair(LIR lir, AbstractBlockBase<?> merge, AbstractBlockBase<?> pred, PhiValueVisitor visitor) {
90 if (merge.getPredecessorCount() < 2) {
91 return;
92 }
93 assert Arrays.asList(merge.getPredecessors()).contains(pred) : String.format("%s not in predecessor list: %s", pred, Arrays.toString(merge.getPredecessors()));
94 assert pred.getSuccessorCount() == 1 : String.format("Merge predecessor block %s has more than one successor? %s", pred, Arrays.toString(pred.getSuccessors()));
95 assert pred.getSuccessors()[0] == merge : String.format("Predecessor block %s has wrong successor: %s, should be: %s", pred, pred.getSuccessors()[0], merge);
96
97 JumpOp jump = phiOut(lir, pred);
98 LabelOp label = phiIn(lir, merge);
99
100 assert label.getIncomingSize() == jump.getOutgoingSize() : String.format("Phi In/Out size mismatch: in=%d vs. out=%d", label.getIncomingSize(), jump.getOutgoingSize());
101 assert label.getPhiSize() == jump.getPhiSize() : String.format("Phi In/Out size mismatch: in=%d vs. out=%d", label.getPhiSize(), jump.getPhiSize());
102
103 for (int i = 0; i < label.getPhiSize(); i++) {
104 visitor.visit(label.getIncomingValue(i), jump.getOutgoingValue(i));
105 }
106 }
107
108 private static JumpOp phiOut(LIR lir, AbstractBlockBase<?> block) {
109 assert block.getSuccessorCount() == 1;
110 List<LIRInstruction> instructions = lir.getLIRforBlock(block);
111 int index = instructions.size() - 1;
112 LIRInstruction op = instructions.get(index);
113 return (JumpOp) op;
114 }
115
116 public static int phiOutIndex(LIR lir, AbstractBlockBase<?> block) {
117 assert block.getSuccessorCount() == 1;
118 List<LIRInstruction> instructions = lir.getLIRforBlock(block);
119 int index = instructions.size() - 1;
120 assert instructions.get(index) instanceof JumpOp;
121 return index;
122 }
123
124 private static LabelOp phiIn(LIR lir, AbstractBlockBase<?> block) {
125 assert block.getPredecessorCount() > 1;
126 LabelOp label = (LabelOp) lir.getLIRforBlock(block).get(0);
127 return label;
128 }
129
130 public static void removePhiOut(LIR lir, AbstractBlockBase<?> block) {
131 JumpOp jump = phiOut(lir, block);
132 jump.clearOutgoingValues();
133 }
134
135 public static void removePhiIn(LIR lir, AbstractBlockBase<?> block) {
136 LabelOp label = phiIn(lir, block);
137 label.clearIncomingValues();
138 }
139
140 public static boolean verifySSAForm(LIR lir) {
141 return new SSAVerifier(lir).verify();
142 }
143
144 public static void verifyPhi(LIR lir, AbstractBlockBase<?> merge) {
145 assert merge.getPredecessorCount() > 1;
146 for (AbstractBlockBase<?> pred : merge.getPredecessors()) {
147 forEachPhiValuePair(lir, merge, pred, (phiIn, phiOut) -> {
148 assert phiIn.getValueKind().equals(phiOut.getValueKind()) ||
149 (phiIn.getPlatformKind().equals(phiOut.getPlatformKind()) && LIRKind.isUnknownReference(phiIn) && LIRKind.isValue(phiOut));
150 });
151 }
152 }
153
154 public static void forEachPhiRegisterHint(LIR lir, AbstractBlockBase<?> block, LabelOp label, Value targetValue, OperandMode mode, ValueConsumer valueConsumer) {
155 assert mode == OperandMode.DEF : "Wrong operand mode: " + mode;
156 assert lir.getLIRforBlock(block).get(0).equals(label) : String.format("Block %s and Label %s do not match!", block, label);
157
158 if (!label.isPhiIn()) {
159 return;
160 }
161 int idx = indexOfValue(label, targetValue);
162 assert idx >= 0 : String.format("Value %s not in label %s", targetValue, label);
163
164 for (AbstractBlockBase<?> pred : block.getPredecessors()) {
165 JumpOp jump = phiOut(lir, pred);
166 Value sourceValue = jump.getOutgoingValue(idx);
167 valueConsumer.visitValue(jump, sourceValue, null, null);
168 }
169
170 }
171
172 private static int indexOfValue(LabelOp label, Value value) {
173 for (int i = 0; i < label.getIncomingSize(); i++) {
174 if (label.getIncomingValue(i).equals(value)) {
175 return i;
176 }
177 }
178 return -1;
179 }
180
181 }