1 /*
2 * Copyright (c) 2015, 2018, 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
24
25 package org.graalvm.compiler.lir.ssa;
26
27 import java.util.ArrayList;
28 import java.util.Arrays;
29
30 import org.graalvm.compiler.core.common.LIRKind;
31 import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
32 import org.graalvm.compiler.lir.LIR;
33 import org.graalvm.compiler.lir.LIRInstruction;
34 import org.graalvm.compiler.lir.LIRInstruction.OperandMode;
35 import org.graalvm.compiler.lir.StandardOp.BlockEndOp;
36 import org.graalvm.compiler.lir.StandardOp.JumpOp;
37 import org.graalvm.compiler.lir.StandardOp.LabelOp;
38 import org.graalvm.compiler.lir.ValueConsumer;
39
40 import jdk.vm.ci.meta.Value;
41
42 /**
43 * Utilities for working with Static-Single-Assignment LIR form.
44 *
45 * <h2>Representation of <code>PHI</code>s</h2>
46 *
47 * There is no explicit <code>PHI</code> {@linkplain LIRInstruction}. Instead, they are implemented
48 * as parallel copy that span across a control-flow edge.
49 *
50 * The variables introduced by <code>PHI</code>s of a specific {@linkplain AbstractBlockBase merge
51 * block} are {@linkplain LabelOp#setIncomingValues attached} to the {@linkplain LabelOp} of the
52 * block. The outgoing values from the predecessor are {@link JumpOp#getOutgoingValue input} to the
53 * {@linkplain BlockEndOp} of the predecessor. Because there are no critical edges we know that the
54 * {@link BlockEndOp} of the predecessor has to be a {@link JumpOp}.
55 *
56 * <h3>Example:</h3>
57 *
58 * <pre>
97 assert pred.getSuccessors()[0] == merge : String.format("Predecessor block %s has wrong successor: %s, should be: %s", pred, pred.getSuccessors()[0], merge);
98
99 JumpOp jump = phiOut(lir, pred);
100 LabelOp label = phiIn(lir, merge);
101
102 assert label.getPhiSize() == jump.getPhiSize() : String.format("Phi In/Out size mismatch: in=%d vs. out=%d", label.getPhiSize(), jump.getPhiSize());
103
104 for (int i = 0; i < label.getPhiSize(); i++) {
105 visitor.visit(label.getIncomingValue(i), jump.getOutgoingValue(i));
106 }
107 }
108
109 public static JumpOp phiOut(LIR lir, AbstractBlockBase<?> block) {
110 assert block.getSuccessorCount() == 1;
111 ArrayList<LIRInstruction> instructions = lir.getLIRforBlock(block);
112 int index = instructions.size() - 1;
113 LIRInstruction op = instructions.get(index);
114 return (JumpOp) op;
115 }
116
117 public static JumpOp phiOutOrNull(LIR lir, AbstractBlockBase<?> block) {
118 if (block.getSuccessorCount() != 1) {
119 return null;
120 }
121 return phiOut(lir, block);
122 }
123
124 public static int phiOutIndex(LIR lir, AbstractBlockBase<?> block) {
125 assert block.getSuccessorCount() == 1;
126 ArrayList<LIRInstruction> instructions = lir.getLIRforBlock(block);
127 int index = instructions.size() - 1;
128 assert instructions.get(index) instanceof JumpOp;
129 return index;
130 }
131
132 public static LabelOp phiIn(LIR lir, AbstractBlockBase<?> block) {
133 assert block.getPredecessorCount() > 1;
134 LabelOp label = (LabelOp) lir.getLIRforBlock(block).get(0);
135 return label;
136 }
137
138 public static void removePhiOut(LIR lir, AbstractBlockBase<?> block) {
139 JumpOp jump = phiOut(lir, block);
140 jump.clearOutgoingValues();
141 }
142
143 public static void removePhiIn(LIR lir, AbstractBlockBase<?> block) {
144 LabelOp label = phiIn(lir, block);
145 label.clearIncomingValues();
146 }
147
148 public static boolean verifySSAForm(LIR lir) {
149 return new SSAVerifier(lir).verify();
150 }
151
152 public static boolean isMerge(AbstractBlockBase<?> block) {
153 return block.getPredecessorCount() > 1;
154 }
155
156 public static void verifyPhi(LIR lir, AbstractBlockBase<?> merge) {
157 assert merge.getPredecessorCount() > 1;
158 for (AbstractBlockBase<?> pred : merge.getPredecessors()) {
159 forEachPhiValuePair(lir, merge, pred, (phiIn, phiOut) -> {
160 assert phiIn.getValueKind().equals(phiOut.getValueKind()) ||
161 (phiIn.getPlatformKind().equals(phiOut.getPlatformKind()) && LIRKind.isUnknownReference(phiIn) && LIRKind.isValue(phiOut));
162 });
163 }
164 }
165
166 public static void forEachPhiRegisterHint(LIR lir, AbstractBlockBase<?> block, LabelOp label, Value targetValue, OperandMode mode, ValueConsumer valueConsumer) {
167 assert mode == OperandMode.DEF : "Wrong operand mode: " + mode;
168 assert lir.getLIRforBlock(block).get(0).equals(label) : String.format("Block %s and Label %s do not match!", block, label);
169
170 if (!label.isPhiIn()) {
171 return;
172 }
173 int idx = indexOfValue(label, targetValue);
174 assert idx >= 0 : String.format("Value %s not in label %s", targetValue, label);
175
176 for (AbstractBlockBase<?> pred : block.getPredecessors()) {
177 JumpOp jump = phiOut(lir, pred);
178 Value sourceValue = jump.getOutgoingValue(idx);
179 valueConsumer.visitValue(jump, sourceValue, null, null);
180 }
181
182 }
183
184 private static int indexOfValue(LabelOp label, Value value) {
185 for (int i = 0; i < label.getIncomingSize(); i++) {
186 if (label.getIncomingValue(i).equals(value)) {
187 return i;
188 }
189 }
190 return -1;
191 }
192
193 public static int numPhiOut(LIR lir, AbstractBlockBase<?> block) {
194 if (block.getSuccessorCount() != 1) {
195 // cannot be a phi_out block
196 return 0;
197 }
198 return numPhiIn(lir, block.getSuccessors()[0]);
199 }
200
201 private static int numPhiIn(LIR lir, AbstractBlockBase<?> block) {
202 if (!isMerge(block)) {
203 return 0;
204 }
205 return phiIn(lir, block).getPhiSize();
206 }
207
208 }
|
1 /*
2 * Copyright (c) 2015, 2019, 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
24
25 package org.graalvm.compiler.lir.ssa;
26
27 import java.util.ArrayList;
28 import java.util.Arrays;
29
30 import org.graalvm.compiler.core.common.LIRKind;
31 import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
32 import org.graalvm.compiler.lir.LIR;
33 import org.graalvm.compiler.lir.LIRInstruction;
34 import org.graalvm.compiler.lir.StandardOp.BlockEndOp;
35 import org.graalvm.compiler.lir.StandardOp.JumpOp;
36 import org.graalvm.compiler.lir.StandardOp.LabelOp;
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#getOutgoingValue 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>
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.getPhiSize() == jump.getPhiSize() : String.format("Phi In/Out size mismatch: in=%d vs. out=%d", label.getPhiSize(), jump.getPhiSize());
101
102 for (int i = 0; i < label.getPhiSize(); i++) {
103 visitor.visit(label.getIncomingValue(i), jump.getOutgoingValue(i));
104 }
105 }
106
107 public static JumpOp phiOut(LIR lir, AbstractBlockBase<?> block) {
108 assert block.getSuccessorCount() == 1;
109 ArrayList<LIRInstruction> instructions = lir.getLIRforBlock(block);
110 int index = instructions.size() - 1;
111 LIRInstruction op = instructions.get(index);
112 return (JumpOp) op;
113 }
114
115 public static int phiOutIndex(LIR lir, AbstractBlockBase<?> block) {
116 assert block.getSuccessorCount() == 1;
117 ArrayList<LIRInstruction> instructions = lir.getLIRforBlock(block);
118 int index = instructions.size() - 1;
119 assert instructions.get(index) instanceof JumpOp;
120 return index;
121 }
122
123 public static LabelOp phiIn(LIR lir, AbstractBlockBase<?> block) {
124 assert block.getPredecessorCount() > 1;
125 LabelOp label = (LabelOp) lir.getLIRforBlock(block).get(0);
126 return label;
127 }
128
129 public static void removePhiOut(LIR lir, AbstractBlockBase<?> block) {
130 JumpOp jump = phiOut(lir, block);
131 jump.clearOutgoingValues();
132 }
133
134 public static void removePhiIn(LIR lir, AbstractBlockBase<?> block) {
135 LabelOp label = phiIn(lir, block);
136 label.clearIncomingValues();
137 }
138
139 public static boolean verifySSAForm(LIR lir) {
140 return new SSAVerifier(lir).verify();
141 }
142
143 public static void verifyPhi(LIR lir, AbstractBlockBase<?> merge) {
144 assert merge.getPredecessorCount() > 1;
145 for (AbstractBlockBase<?> pred : merge.getPredecessors()) {
146 forEachPhiValuePair(lir, merge, pred, (phiIn, phiOut) -> {
147 assert phiIn.getValueKind().equals(phiOut.getValueKind()) ||
148 (phiIn.getPlatformKind().equals(phiOut.getPlatformKind()) && LIRKind.isUnknownReference(phiIn) && LIRKind.isValue(phiOut));
149 });
150 }
151 }
152
153 public static int indexOfValue(LabelOp label, Value value) {
154 for (int i = 0; i < label.getIncomingSize(); i++) {
155 if (label.getIncomingValue(i).equals(value)) {
156 return i;
157 }
158 }
159 return -1;
160 }
161 }
|