1 /*
2 * Copyright (c) 2024, 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. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26 package jdk.incubator.code.analysis;
27
28 import jdk.incubator.code.*;
29 import jdk.incubator.code.op.CoreOp;
30 import java.util.ArrayDeque;
31 import java.util.ArrayList;
32 import java.util.Deque;
33 import java.util.HashMap;
34 import java.util.HashSet;
35 import java.util.LinkedHashMap;
36 import java.util.LinkedHashSet;
37 import java.util.List;
38 import java.util.Map;
39 import java.util.Set;
40 import java.util.stream.Collectors;
41
42 /**
43 * Functionality to transform a code model into pure SSA form, replacing operations that declare variables and
44 * access them with the use of values they depend on or additional block parameters.
45 */
46 public final class SSA {
47 private SSA() {
48 }
49
50 /**
51 * Applies an SSA transformation to an operation with bodies, replacing operations that declare variables and
52 * access them with the use of values they depend on or additional block parameters.
53 * <p>
54 * The operation should first be in lowered form before applying this transformation.
55 * <p>
56 * Note: this implementation does not currently work correctly when a variable is stored to within an exception
57 * region and read from outside as a result of catching an exception. In such cases a complete transformation may be
58 * not possible and such variables will need to be retained.
59 *
60 * @param nestedOp the operation with bodies
61 * @return the transformed operation
62 * @param <T> the operation type
63 */
64 public static <T extends Op & Op.Nested> T transform(T nestedOp) {
65 // @@@ property is used to test both impls
66 if (!"cytron".equalsIgnoreCase(System.getProperty("babylon.ssa"))) {
67 return SSAConstruction.transform(nestedOp);
68 }
69 Map<Block, Set<CoreOp.VarOp>> joinPoints = new HashMap<>();
70 Map<CoreOp.VarAccessOp.VarLoadOp, Object> loadValues = new HashMap<>();
71 Map<Block.Reference, List<Object>> joinSuccessorValues = new HashMap<>();
72
73 Map<Body, Boolean> visited = new HashMap<>();
74 Map<Block, Map<CoreOp.VarOp, Block.Parameter>> joinBlockArguments = new HashMap<>();
75 @SuppressWarnings("unchecked")
76 T ssaOp = (T) nestedOp.transform(CopyContext.create(), (block, op) -> {
77 // Compute join points and value mappings for body
78 visited.computeIfAbsent(op.ancestorBody(), b -> {
79 findJoinPoints(b, joinPoints);
80 variableToValue(b, joinPoints, loadValues, joinSuccessorValues);
81 return true;
82 });
83
84 if (op instanceof CoreOp.VarOp || op instanceof CoreOp.VarAccessOp) {
85 // Drop var operations
86 if (op instanceof CoreOp.VarAccessOp.VarLoadOp vl) {
87 // Replace result of load
88 Object loadValue = loadValues.get(vl);
89 CopyContext cc = block.context();
90 Value v = loadValue instanceof VarOpBlockArgument vba
91 ? joinBlockArguments.get(vba.b()).get(vba.vop())
92 : cc.getValue((Value) loadValue);
93 cc.mapValue(op.result(), v);
94 }
95 } else if (op instanceof Op.Terminating) {
96 for (Block.Reference s : op.successors()) {
97 List<Object> joinValues = joinSuccessorValues.get(s);
98 // Successor has join values
99 if (joinValues != null) {
100 CopyContext cc = block.context();
101
102 // Lazily append target block arguments
103 joinBlockArguments.computeIfAbsent(s.targetBlock(), b -> {
104 Block.Builder bb = cc.getBlock(b);
105 return joinPoints.get(b).stream().collect(Collectors.toMap(
106 varOp -> varOp,
107 varOp -> bb.parameter(varOp.varValueType())));
108 });
109
110 // Append successor arguments
111 List<Value> values = new ArrayList<>();
112 for (Object o : joinValues) {
113 Value v = o instanceof VarOpBlockArgument vba
114 ? joinBlockArguments.get(vba.b()).get(vba.vop())
115 : cc.getValue((Value) o);
116 values.add(v);
117 }
118
119 // Map successor with append arguments
120 List<Value> toArgs = cc.getValues(s.arguments());
121 toArgs.addAll(values);
122 Block.Reference toS = cc.getBlock(s.targetBlock()).successor(toArgs);
123 cc.mapSuccessor(s, toS);
124 }
125 }
126
127 block.apply(op);
128 } else {
129 block.apply(op);
130 }
131
132 return block;
133 });
134 return ssaOp;
135 }
136
137 record VarOpBlockArgument(Block b, CoreOp.VarOp vop) {
138 }
139
140 enum Uninitialized {
141 UNINITIALIZED;
142 }
143
144 // @@@ Check for var uses in exception regions
145 // A variable cannot be converted to SAA form if the variable is stored
146 // to in an exception region and accessed from an associated catch region
147
148 static void variableToValue(Body body,
149 Map<Block, Set<CoreOp.VarOp>> joinPoints,
150 Map<CoreOp.VarAccessOp.VarLoadOp, Object> loadValues,
151 Map<Block.Reference, List<Object>> joinSuccessorValues) {
152 Map<CoreOp.VarOp, Deque<Object>> variableStack = new HashMap<>();
153 Node top = buildDomTree(body.entryBlock(), body.immediateDominators());
154 variableToValue(top, variableStack, joinPoints, loadValues, joinSuccessorValues);
155 }
156
157 /**
158 * Replaces usages of a variable with the corresponding value, from a given block node in the dominator tree.
159 * <p>
160 * The result of a {@code VarLoadOp} for variable, {@code V} say the result of a {@code VarOp} operation,
161 * is replaced with the value passed as an operand to the immediately dominating {@code VarStoreOp} that operates
162 * on {@code V}, or a block argument representing the equivalent of a phi-value of {@code V}.
163 * After which, any related {@code VarOp}, {@code VarLoadOp}, or {@code VarStoreOp} operations are removed.
164 *
165 * @param n the node in the dominator tree
166 * @param variableStack the variable stack
167 * @param joinPoints the join points
168 * @implNote See "Efficiently Computing Static Single Assignment Form and the Control Dependence Graph" by Ron Cytron et. al.
169 * Section 5.2 and Figure 12.
170 */
171 static void variableToValue(Node n,
172 Map<CoreOp.VarOp, Deque<Object>> variableStack,
173 Map<Block, Set<CoreOp.VarOp>> joinPoints,
174 Map<CoreOp.VarAccessOp.VarLoadOp, Object> loadValues,
175 Map<Block.Reference, List<Object>> joinSuccessorValues) {
176 int size = n.b().ops().size();
177
178 // Check if V is associated with block argument (phi)
179 // Push argument onto V's stack
180 {
181 Set<CoreOp.VarOp> varOps = joinPoints.get(n.b());
182 if (varOps != null) {
183 varOps.forEach(v -> {
184 assert variableStack.containsKey(v);
185 variableStack.get(v).push(new VarOpBlockArgument(n.b(), v));
186 });
187 }
188 }
189
190 {
191 for (int i = 0; i < size - 1; i++) {
192 Op op = n.b().ops().get(i);
193
194 if (op instanceof CoreOp.VarOp varOp) {
195 // Initial value assigned to variable
196 Object current = varOp.isUninitialized()
197 ? Uninitialized.UNINITIALIZED
198 : op.operands().get(0);
199 assert !variableStack.containsKey(varOp);
200 variableStack.computeIfAbsent(varOp, _ -> new ArrayDeque<>())
201 .push(current);
202 } else if (op instanceof CoreOp.VarAccessOp.VarStoreOp storeOp) {
203 // Value assigned to variable
204 Value current = op.operands().get(1);
205 variableStack.get(storeOp.varOp()).push(current);
206 } else if (op instanceof CoreOp.VarAccessOp.VarLoadOp loadOp &&
207 loadOp.varOp().ancestorBody() == op.ancestorBody()) {
208 Object to = peekAtCurrentVariable(variableStack, loadOp.varOp());
209 loadValues.put(loadOp, to);
210 } else if (op instanceof Op.Nested) {
211 // Traverse descendant variable loads for variables
212 // declared in the block's parent body
213 op.traverse(null, (_, ce) -> {
214 if (ce instanceof CoreOp.VarAccessOp.VarLoadOp loadOp &&
215 loadOp.varOp().ancestorBody() == op.ancestorBody()) {
216 Object to = peekAtCurrentVariable(variableStack, loadOp.varOp());
217 loadValues.put(loadOp, to);
218 }
219 return null;
220 });
221 }
222 }
223
224 // Add successor args for joint points
225 for (Block.Reference succ : n.b().successors()) {
226 Set<CoreOp.VarOp> varOps = joinPoints.get(succ.targetBlock());
227 if (varOps != null) {
228 List<Object> joinValues = varOps.stream()
229 .map(vop -> peekAtCurrentVariable(variableStack, vop)).toList();
230 joinSuccessorValues.put(succ, joinValues);
231 }
232 }
233
234 // The result of a VarOp, a variable value, can only be used in VarStoreOp and VarLoadOp
235 // therefore there is no need to check existing successor arguments
236 }
237
238 // Traverse children of dom tree
239 for (Node y : n.children()) {
240 variableToValue(y, variableStack, joinPoints, loadValues, joinSuccessorValues);
241 }
242
243 // Pop off values for variables
244 {
245 Set<CoreOp.VarOp> varOps = joinPoints.get(n.b());
246 if (varOps != null) {
247 varOps.forEach(v -> {
248 variableStack.get(v).pop();
249 });
250 }
251
252 for (int i = 0; i < size - 1; i++) {
253 Op op = n.b().ops().get(i);
254
255 if (op instanceof CoreOp.VarOp varOp) {
256 variableStack.get(varOp).pop();
257 } else if (op instanceof CoreOp.VarAccessOp.VarStoreOp storeOp) {
258 variableStack.get(storeOp.varOp()).pop();
259 }
260 }
261 }
262 }
263
264 static Object peekAtCurrentVariable(Map<CoreOp.VarOp, Deque<Object>> variableStack, CoreOp.VarOp vop) {
265 Object to = variableStack.get(vop).peek();
266 return throwIfUninitialized(vop, to);
267 }
268
269 static Object throwIfUninitialized(CoreOp.VarOp vop, Object to) {
270 if (to instanceof Uninitialized) {
271 throw new IllegalStateException("Loading from uninitialized variable: " + vop);
272 }
273 return to;
274 }
275
276 /**
277 * Finds the join points of a body.
278 * <p>
279 * A join point is a block that is in the dominance frontier of one or more predecessors, that make one or more
280 * stores to variables (using the {@code VarStoreOp} operation on the result of a {@code VarOp} operation).
281 * The join point contains the set variables ({@code VarOp} operations) that are stored to.
282 * <p>
283 * A variable of a joint point indicates that a block argument may need to be added to the join point's block
284 * when converting variables to SSA form. Different values of a variable may occur at different control flow
285 * paths at the join point. The block argument represents the convergence of multiple values for the same
286 * variable, where a predecessor assigns to the block argument.
287 * (Block arguments are equivalent to phi-values, or phi-nodes, used in other representations.)
288 *
289 * @param body the body.
290 * @param joinPoints the returned join points.
291 * @implNote See "Efficiently Computing Static Single Assignment Form and the Control Dependence Graph" by Ron Cytron et. al.
292 * Section 5.1 and Figure 11.
293 */
294 public static void findJoinPoints(Body body, Map<Block, Set<CoreOp.VarOp>> joinPoints) {
295 Map<Block, Set<Block>> df = body.dominanceFrontier();
296 Map<CoreOp.VarOp, Set<Block>> a = findVarStores(body);
297
298 int iterCount = 0;
299 int[] hasAlready = new int[body.blocks().size()];
300 int[] work = new int[body.blocks().size()];
301
302 Deque<Block> w = new ArrayDeque<>();
303
304 for (CoreOp.VarOp v : a.keySet()) {
305 iterCount++;
306
307 for (Block x : a.get(v)) {
308 work[x.index()] = iterCount;
309 w.push(x);
310 }
311
312 while (!w.isEmpty()) {
313 Block x = w.pop();
314
315 for (Block y : df.getOrDefault(x, Set.of())) {
316 if (hasAlready[y.index()] < iterCount) {
317 // Only add to the join points if y is dominated by the var's block
318 if (y.isDominatedBy(v.parentBlock())) {
319 joinPoints.computeIfAbsent(y, _k -> new LinkedHashSet<>()).add(v);
320 }
321 hasAlready[y.index()] = iterCount;
322
323 if (work[y.index()] < iterCount) {
324 work[y.index()] = iterCount;
325 w.push(y);
326 }
327 }
328 }
329 }
330 }
331 }
332
333 // Returns map of variable to blocks that contain stores to the variables declared in the body
334 // Throws ISE if a descendant store operation is encountered
335 // @@@ Compute map for whole tree, then traverse keys with filter
336 static Map<CoreOp.VarOp, Set<Block>> findVarStores(Body r) {
337 return r.traverse(new LinkedHashMap<>(), CodeElement.opVisitor((stores, op) -> {
338 if (op instanceof CoreOp.VarAccessOp.VarStoreOp storeOp) {
339 if (storeOp.varOp().ancestorBody() != storeOp.ancestorBody()) {
340 throw new IllegalStateException("Descendant variable store operation");
341 }
342 if (storeOp.varOp().ancestorBody() == r) {
343 stores.computeIfAbsent(storeOp.varOp(), _v -> new LinkedHashSet<>()).add(storeOp.parentBlock());
344 }
345 }
346 return stores;
347 }));
348 }
349
350 record Node(Block b, Set<Node> children) {
351 }
352
353 static Node buildDomTree(Block entryBlock, Map<Block, Block> idoms) {
354 Map<Block, Node> tree = new HashMap<>();
355 for (Map.Entry<Block, Block> e : idoms.entrySet()) {
356 Block id = e.getValue();
357 Block b = e.getKey();
358
359 Node parent = tree.computeIfAbsent(id, _k -> new Node(_k, new HashSet<>()));
360 if (b == entryBlock) {
361 continue;
362 }
363
364 Node child = tree.computeIfAbsent(b, _k -> new Node(_k, new HashSet<>()));
365 parent.children.add(child);
366 }
367 return tree.get(entryBlock);
368 }
369 }