1 /*
2 * Copyright (c) 2024, 2026, 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.dialect.core;
27
28 import jdk.incubator.code.*;
29
30 import java.util.*;
31 import java.util.stream.Collectors;
32
33 /**
34 * Functionality to transform a code model into pure SSA form, replacing operations that declare variables and
35 * access them with the use of values they depend on or additional block parameters.
36 */
37 public final class SSA {
38 private SSA() {
39 }
40
41 /**
42 * Applies an SSA transformation to an operation with bodies, replacing operations that declare variables and
43 * access them with the use of values they depend on or additional block parameters.
44 * <p>
45 * The operation should first be in lowered form before applying this transformation.
46 * <p>
47 * Note: this implementation does not currently work correctly when a variable is stored to within an exception
48 * region and read from outside as a result of catching an exception. In such cases a complete transformation may be
49 * not possible and such variables will need to be retained.
50 *
51 * @param nestedOp the operation with bodies
52 * @return the transformed operation
53 * @param <T> the operation type
54 */
55 public static <T extends Op & Op.Nested> T transform(T nestedOp) {
56 // @@@ property is used to test both impls
57 if (!"cytron".equalsIgnoreCase(System.getProperty("babylon.ssa"))) {
58 return SSABraun.transform(nestedOp);
59 } else {
60 return SSACytron.transform(nestedOp);
61 }
62 }
63
64 /**
65 * An implementation of SSA construction based on
66 * <a href="https://doi.org/10.1007/978-3-642-37051-9">
67 * Simple end Efficient Construction of Static Single Assignment Form (pp 102-122)
68 * </a>.
69 * <p>
70 * This implementation contains some adaptions, notably:
71 * <ul>
72 * <li>Adapt to block parameters rather than phi functions.</li>
73 * <li>Adapt to work with multiple bodies.</li>
74 * </ul>
75 */
76 static final class SSABraun implements CodeTransformer {
77 private final Map<CoreOp.VarOp, Map<Block, Val>> currentDef = new HashMap<>();
78 private final Set<Block> sealedBlocks = new HashSet<>();
79 private final Map<Block, Map<CoreOp.VarOp, Phi>> incompletePhis = new HashMap<>();
80
81 // according to the algorithm:
82 // "As only filled blocks may have successors, predecessors are always filled."
83 // In consequence, this means that only filled predecessors should be considered
84 // when recursively searching for a definition
85 private final Map<Block, SequencedSet<Block>> predecessors = new HashMap<>();
86 // as we can't modify the graph at the same time as we analyze it,
87 // we need to store which load op needs to remapped to which value
88 private final Map<CoreOp.VarAccessOp.VarLoadOp, Val> loads = new HashMap<>();
89 private final Map<Block, List<Phi>> additionalParameters = new HashMap<>();
90 // as we look up definitions during the actual transformation again,
91 // we might encounter deleted phis.
92 // we use this set to be able to correct that during transformation
93 private final Set<Phi> deletedPhis = new HashSet<>();
94
95 static <O extends Op & Op.Nested> O transform(O nestedOp) {
96 SSABraun construction = new SSABraun();
97 construction.prepare(nestedOp);
98 @SuppressWarnings("unchecked")
99 O ssaOp = (O) nestedOp.transform(CodeContext.create(), construction);
100 return ssaOp;
101 }
102
103 private SSABraun() {
104 }
105
106 private void prepare(Op nestedOp) {
107 nestedOp.elements().forEach(e -> {
108 switch (e) {
109 case CoreOp.VarAccessOp.VarLoadOp load -> {
110 Val val = readVariable(load.varOp(), load.ancestorBlock());
111 registerLoad(load, val);
112 }
113 case CoreOp.VarAccessOp.VarStoreOp store ->
114 writeVariable(store.varOp(), store.ancestorBlock(), new Holder(store.storeOperand()));
115 case CoreOp.VarOp initialStore -> {
116 Val val = initialStore.isUninitialized()
117 ? Uninitialized.VALUE
118 : new Holder(initialStore.initOperand());
119 writeVariable(initialStore, initialStore.ancestorBlock(), val);
120 }
121 case Op op when op instanceof Op.Terminating -> {
122 Block block = op.ancestorBlock();
123 // handle the sealing, i.e. only now make this block a predecessor of its successors
124 for (Block.Reference successor : block.successors()) {
125 Block successorBlock = successor.targetBlock();
126 Set<Block> blocks = this.predecessors.computeIfAbsent(successorBlock, _ -> new LinkedHashSet<>());
127 blocks.add(block);
128 // if this was the last predecessor added to successorBlock, seal it
129 if (blocks.size() == successorBlock.predecessors().size()) {
130 sealBlock(successorBlock);
131 }
132 }
133 }
134 default -> {
135 }
136 }
137 });
138 }
139
140 private void registerLoad(CoreOp.VarAccessOp.VarLoadOp load, Val val) {
141 this.loads.put(load, val);
142 if (val instanceof Phi phi) {
143 phi.users.add(load);
144 }
145 }
146
147 private void writeVariable(CoreOp.VarOp variable, Block block, Val value) {
148 this.currentDef.computeIfAbsent(variable, _ -> new HashMap<>()).put(block, value);
149 }
150
151 private Val readVariable(CoreOp.VarOp variable, Block block) {
152 Val value = this.currentDef.getOrDefault(variable, Map.of()).get(block);
153 if (value == null
154 // deleted Phi, this is an old reference
155 // due to our 2-step variant of the original algorithm, we might encounter outdated definitions
156 // when we read to prepare block arguments
157 || value instanceof Phi phi && this.deletedPhis.contains(phi)) {
158 return readVariableRecursive(variable, block);
159 }
160 return value;
161 }
162
163 private Val readVariableRecursive(CoreOp.VarOp variable, Block block) {
164 Val value;
165 if (!block.isEntryBlock() && !this.sealedBlocks.contains(block)) {
166 Phi phi = new Phi(variable, block);
167 value = phi;
168 this.incompletePhis.computeIfAbsent(block, _ -> new HashMap<>()).put(variable, phi);
169 this.additionalParameters.computeIfAbsent(block, _ -> new ArrayList<>()).add(phi);
170 } else if (block.isEntryBlock() && variable.ancestorBody() != block.ancestorBody()) {
171 // we are in an entry block but didn't find a definition yet
172 Block enclosingBlock = block.parent().parent().parent();
173 assert enclosingBlock != null : "def not found in entry block, with no enclosing block";
174 value = readVariable(variable, enclosingBlock);
175 } else if (this.predecessors.get(block).size() == 1) {
176 value = readVariable(variable, this.predecessors.get(block).getFirst());
177 } else {
178 Phi param = new Phi(variable, block);
179 writeVariable(variable, block, param);
180 value = addPhiOperands(variable, param);
181 // To go from Phis to block parameters, we remember that we produced a Phi here.
182 // This means that edges to this block need to pass a value via parameter
183 if (value == param) {
184 this.additionalParameters.computeIfAbsent(block, _ -> new ArrayList<>()).add(param);
185 }
186 }
187 writeVariable(variable, block, value); // cache value for this variable + block
188 return value;
189 }
190
191 private Val addPhiOperands(CoreOp.VarOp variable, Phi value) {
192 for (Block pred : this.predecessors.getOrDefault(value.block(), Collections.emptySortedSet())) {
193 value.appendOperand(readVariable(variable, pred));
194 }
195 return tryRemoveTrivialPhi(value);
196 }
197
198 private Val tryRemoveTrivialPhi(Phi phi) {
199 Val same = null;
200 for (Val op : phi.operands()) {
201 if (op == same || op == phi) {
202 continue;
203 }
204 if (same != null) {
205 return phi;
206 }
207 same = op;
208 }
209 // we shouldn't have phis without operands (other than itself)
210 assert same != null : "phi without different operands";
211 List<Phi> phiUsers = phi.replaceBy(same, this);
212 List<Phi> phis = this.additionalParameters.get(phi.block());
213 if (phis != null) {
214 phis.remove(phi);
215 }
216 for (Phi user : phiUsers) {
217 Val res = tryRemoveTrivialPhi(user);
218 if (same == user) {
219 same = res;
220 }
221 }
222 return same;
223 }
224
225 private void sealBlock(Block block) {
226 this.incompletePhis.getOrDefault(block, Map.of()).forEach(this::addPhiOperands);
227 this.sealedBlocks.add(block);
228 }
229
230 // only used during transformation
231
232 private Value resolveValue(CodeContext context, Val val) {
233 return switch (val) {
234 case Uninitialized _ -> throw new IllegalStateException("Uninitialized variable");
235 case Holder holder -> context.queryValue(holder.value()).orElse(holder.value());
236 case Phi phi -> {
237 List<Phi> phis = this.additionalParameters.get(phi.block());
238 int additionalParameterIndex = phis.indexOf(phi);
239 assert additionalParameterIndex >= 0 : "phi not in parameters " + phi;
240 int index = additionalParameterIndex + phi.block().parameters().size();
241 Block.Builder b = context.getBlock(phi.block());
242 yield b.parameters().get(index);
243 }
244 };
245 }
246
247 @Override
248 public Block.Builder acceptOp(Block.Builder block, Op op) {
249 Block originalBlock = op.ancestorBlock();
250 CodeContext context = block.context();
251 switch (op) {
252 case CoreOp.VarAccessOp.VarLoadOp load -> {
253 Val val = this.loads.get(load);
254 context.mapValue(load.result(), resolveValue(context, val));
255 }
256 case CoreOp.VarOp _, CoreOp.VarAccessOp.VarStoreOp _ -> {
257 }
258 case Op.Terminating _ -> {
259 // make sure outgoing branches are corrected
260 for (Block.Reference successor : originalBlock.successors()) {
261 Block successorBlock = successor.targetBlock();
262 List<Phi> successorParams = this.additionalParameters.getOrDefault(successorBlock, List.of());
263 List<Value> additionalParams = successorParams.stream()
264 .map(phi -> readVariable(phi.variable, originalBlock))
265 .map(val -> resolveValue(context, val))
266 .toList();
267 List<Value> values = context.getValues(successor.arguments());
268 values.addAll(additionalParams);
269 Block.Builder successorBlockBuilder = context.getBlock(successorBlock);
270 context.mapReference(successor, successorBlockBuilder.reference(values));
271 }
272 block.add(op);
273 }
274 default -> block.add(op);
275 }
276 return block;
277 }
278
279 @Override
280 public void acceptBlock(Block.Builder block, Block b) {
281 // add the required additional parameters to this block
282 boolean isEntry = b.isEntryBlock();
283 for (Phi phi : this.additionalParameters.getOrDefault(b, List.of())) {
284 if (isEntry) {
285 // Phis in entry blocks denote captured values. Do not add as param but make sure
286 // the original value is used
287 assert phi.operands().size() == 1 : "entry block phi with multiple operands";
288 CodeContext context = block.context();
289 context.mapValue(resolveValue(context, phi), resolveValue(context, phi.operands().getFirst()));
290 } else {
291 block.parameter(phi.variable.varValueType());
292 }
293 }
294
295 // actually visit ops in this block
296 CodeTransformer.super.acceptBlock(block, b);
297 }
298
299 sealed interface Val {
300 }
301
302 record Holder(Value value) implements Val {
303 }
304
305 enum Uninitialized implements Val {
306 VALUE;
307 }
308
309 record Phi(CoreOp.VarOp variable, Block block, List<Val> operands, Set<Object> users) implements Val {
310 Phi(CoreOp.VarOp variable, Block block) {
311 this(variable, block, new ArrayList<>(), new HashSet<>());
312 }
313
314 void appendOperand(Val val) {
315 this.operands.add(val);
316 if (val instanceof Phi phi) { // load op uses are added separately
317 phi.users.add(this);
318 }
319 }
320
321 @Override
322 public boolean equals(Object obj) {
323 return this == obj;
324 }
325
326 @Override
327 public int hashCode() {
328 return Objects.hash(this.variable, this.block);
329 }
330
331 public List<Phi> replaceBy(Val same, SSABraun construction) {
332 List<Phi> usingPhis = new ArrayList<>();
333 for (Object user : this.users) {
334 if (user == this) {
335 continue;
336 }
337 if (same instanceof Phi samePhi) {
338 samePhi.users.add(user);
339 }
340 switch (user) {
341 case Phi phi -> {
342 int i = phi.operands.indexOf(this);
343 assert i >= 0 : "use does not have this as operand";
344 phi.operands.set(i, same);
345 usingPhis.add(phi);
346 }
347 case CoreOp.VarAccessOp.VarLoadOp load -> construction.loads.put(load, same);
348 default -> throw new UnsupportedOperationException(user + ":" + user.getClass());
349 }
350 }
351 if (same instanceof Phi samePhi) {
352 samePhi.users.remove(this);
353 }
354 construction.currentDef.get(this.variable).put(this.block, same);
355 construction.deletedPhis.add(this); // we might not replace all current defs, so mark this phi as deleted
356 this.users.clear();
357 return usingPhis;
358 }
359
360 @Override
361 public String toString() {
362 return "Phi[" + variable.varName() + "(" + block.index() + ")," + "operands: " + operands.size() + "}";
363 }
364 }
365 }
366
367 /**
368 * An implementation of SSA construction based on
369 * "Efficiently Computing Static Single Assignment Form and the Control Dependence Graph" by Ron Cytron et. al.
370 * <p>
371 * This implementation contains some adaptions, notably:
372 * <ul>
373 * <li>Adapt to block parameters rather than phi functions.</li>
374 * <li>Adapt to work with multiple bodies.</li>
375 * </ul>
376 */
377 static final class SSACytron {
378 private SSACytron() {
379 }
380
381 /**
382 * Applies an SSA transformation to an operation with bodies, replacing operations that declare variables and
383 * access them with the use of values they depend on or additional block parameters.
384 * <p>
385 * The operation should first be in lowered form before applying this transformation.
386 * <p>
387 * Note: this implementation does not currently work correctly when a variable is stored to within an exception
388 * region and read from outside as a result of catching an exception. In such cases a complete transformation may be
389 * not possible and such variables will need to be retained.
390 *
391 * @param nestedOp the operation with bodies
392 * @return the transformed operation
393 * @param <T> the operation type
394 */
395 static <T extends Op & Op.Nested> T transform(T nestedOp) {
396 Map<Block, Set<CoreOp.VarOp>> joinPoints = new HashMap<>();
397 Map<CoreOp.VarAccessOp.VarLoadOp, Object> loadValues = new HashMap<>();
398 Map<Block.Reference, List<Object>> joinSuccessorValues = new HashMap<>();
399
400 Map<Body, Boolean> visited = new HashMap<>();
401 Map<Block, Map<CoreOp.VarOp, Block.Parameter>> joinBlockArguments = new HashMap<>();
402 @SuppressWarnings("unchecked")
403 T ssaOp = (T) nestedOp.transform(CodeContext.create(), (block, op) -> {
404 // Compute join points and value mappings for body
405 visited.computeIfAbsent(op.ancestorBody(), b -> {
406 findJoinPoints(b, joinPoints);
407 variableToValue(b, joinPoints, loadValues, joinSuccessorValues);
408 return true;
409 });
410
411 if (op instanceof CoreOp.VarOp || op instanceof CoreOp.VarAccessOp) {
412 // Drop var operations
413 if (op instanceof CoreOp.VarAccessOp.VarLoadOp vl) {
414 // Replace result of load
415 Object loadValue = loadValues.get(vl);
416 CodeContext cc = block.context();
417 Value v = loadValue instanceof VarOpBlockArgument vba
418 ? joinBlockArguments.get(vba.b()).get(vba.vop())
419 : cc.getValue((Value) loadValue);
420 cc.mapValue(op.result(), v);
421 }
422 } else if (op instanceof Op.Terminating) {
423 for (Block.Reference s : op.successors()) {
424 List<Object> joinValues = joinSuccessorValues.get(s);
425 // Successor has join values
426 if (joinValues != null) {
427 CodeContext cc = block.context();
428
429 // Lazily append target block arguments
430 joinBlockArguments.computeIfAbsent(s.targetBlock(), b -> {
431 Block.Builder bb = cc.getBlock(b);
432 return joinPoints.get(b).stream().collect(Collectors.toMap(
433 varOp -> varOp,
434 varOp -> bb.parameter(varOp.varValueType())));
435 });
436
437 // Append successor arguments
438 List<Value> values = new ArrayList<>();
439 for (Object o : joinValues) {
440 Value v = o instanceof VarOpBlockArgument vba
441 ? joinBlockArguments.get(vba.b()).get(vba.vop())
442 : cc.getValue((Value) o);
443 values.add(v);
444 }
445
446 // Map successor with append arguments
447 List<Value> toArgs = cc.getValues(s.arguments());
448 toArgs.addAll(values);
449 Block.Reference toS = cc.getBlock(s.targetBlock()).reference(toArgs);
450 cc.mapReference(s, toS);
451 }
452 }
453
454 block.add(op);
455 } else {
456 block.add(op);
457 }
458
459 return block;
460 });
461 return ssaOp;
462 }
463
464 record VarOpBlockArgument(Block b, CoreOp.VarOp vop) {
465 }
466
467 enum Uninitialized {
468 UNINITIALIZED;
469 }
470
471 // @@@ Check for var uses in exception regions
472 // A variable cannot be converted to SAA form if the variable is stored
473 // to in an exception region and accessed from an associated catch region
474
475 static void variableToValue(Body body,
476 Map<Block, Set<CoreOp.VarOp>> joinPoints,
477 Map<CoreOp.VarAccessOp.VarLoadOp, Object> loadValues,
478 Map<Block.Reference, List<Object>> joinSuccessorValues) {
479 Map<CoreOp.VarOp, Deque<Object>> variableStack = new HashMap<>();
480 Node top = buildDomTree(body.entryBlock(), body.immediateDominators());
481 variableToValue(top, variableStack, joinPoints, loadValues, joinSuccessorValues);
482 }
483
484 /**
485 * Replaces usages of a variable with the corresponding value, from a given block node in the dominator tree.
486 * <p>
487 * The result of a {@code VarLoadOp} for variable, {@code V} say the result of a {@code VarOp} operation,
488 * is replaced with the value passed as an operand to the immediately dominating {@code VarStoreOp} that operates
489 * on {@code V}, or a block argument representing the equivalent of a phi-value of {@code V}.
490 * After which, any related {@code VarOp}, {@code VarLoadOp}, or {@code VarStoreOp} operations are removed.
491 *
492 * @param n the node in the dominator tree
493 * @param variableStack the variable stack
494 * @param joinPoints the join points
495 * @implNote See "Efficiently Computing Static Single Assignment Form and the Control Dependence Graph" by Ron Cytron et. al.
496 * Section 5.2 and Figure 12.
497 */
498 static void variableToValue(Node n,
499 Map<CoreOp.VarOp, Deque<Object>> variableStack,
500 Map<Block, Set<CoreOp.VarOp>> joinPoints,
501 Map<CoreOp.VarAccessOp.VarLoadOp, Object> loadValues,
502 Map<Block.Reference, List<Object>> joinSuccessorValues) {
503 int size = n.b().ops().size();
504
505 // Check if V is associated with block argument (phi)
506 // Push argument onto V's stack
507 {
508 Set<CoreOp.VarOp> varOps = joinPoints.get(n.b());
509 if (varOps != null) {
510 varOps.forEach(v -> {
511 assert variableStack.containsKey(v);
512 variableStack.get(v).push(new VarOpBlockArgument(n.b(), v));
513 });
514 }
515 }
516
517 {
518 for (int i = 0; i < size - 1; i++) {
519 Op op = n.b().ops().get(i);
520
521 if (op instanceof CoreOp.VarOp varOp) {
522 // Initial value assigned to variable
523 Object current = varOp.isUninitialized()
524 ? Uninitialized.UNINITIALIZED
525 : op.operands().get(0);
526 assert !variableStack.containsKey(varOp);
527 variableStack.computeIfAbsent(varOp, _ -> new ArrayDeque<>())
528 .push(current);
529 } else if (op instanceof CoreOp.VarAccessOp.VarStoreOp storeOp) {
530 // Value assigned to variable
531 Value current = op.operands().get(1);
532 variableStack.get(storeOp.varOp()).push(current);
533 } else if (op instanceof CoreOp.VarAccessOp.VarLoadOp loadOp &&
534 loadOp.varOp().ancestorBody() == op.ancestorBody()) {
535 Object to = peekAtCurrentVariable(variableStack, loadOp.varOp());
536 loadValues.put(loadOp, to);
537 } else if (op instanceof Op.Nested) {
538 // Traverse descendant variable loads for variables
539 // declared in the block's parent body
540 op.elements().forEach(ce -> {
541 if (ce instanceof CoreOp.VarAccessOp.VarLoadOp loadOp &&
542 loadOp.varOp().ancestorBody() == op.ancestorBody()) {
543 Object to = peekAtCurrentVariable(variableStack, loadOp.varOp());
544 loadValues.put(loadOp, to);
545 }
546 });
547 }
548 }
549
550 // Add successor args for joint points
551 for (Block.Reference succ : n.b().successors()) {
552 Set<CoreOp.VarOp> varOps = joinPoints.get(succ.targetBlock());
553 if (varOps != null) {
554 List<Object> joinValues = varOps.stream()
555 .map(vop -> peekAtCurrentVariable(variableStack, vop)).toList();
556 joinSuccessorValues.put(succ, joinValues);
557 }
558 }
559
560 // The result of a VarOp, a variable value, can only be used in VarStoreOp and VarLoadOp
561 // therefore there is no need to check existing successor arguments
562 }
563
564 // Traverse children of dom tree
565 for (Node y : n.children()) {
566 variableToValue(y, variableStack, joinPoints, loadValues, joinSuccessorValues);
567 }
568
569 // Pop off values for variables
570 {
571 Set<CoreOp.VarOp> varOps = joinPoints.get(n.b());
572 if (varOps != null) {
573 varOps.forEach(v -> {
574 variableStack.get(v).pop();
575 });
576 }
577
578 for (int i = 0; i < size - 1; i++) {
579 Op op = n.b().ops().get(i);
580
581 if (op instanceof CoreOp.VarOp varOp) {
582 variableStack.get(varOp).pop();
583 } else if (op instanceof CoreOp.VarAccessOp.VarStoreOp storeOp) {
584 variableStack.get(storeOp.varOp()).pop();
585 }
586 }
587 }
588 }
589
590 static Object peekAtCurrentVariable(Map<CoreOp.VarOp, Deque<Object>> variableStack, CoreOp.VarOp vop) {
591 Object to = variableStack.get(vop).peek();
592 return throwIfUninitialized(vop, to);
593 }
594
595 static Object throwIfUninitialized(CoreOp.VarOp vop, Object to) {
596 if (to instanceof Uninitialized) {
597 throw new IllegalStateException("Loading from uninitialized variable: " + vop);
598 }
599 return to;
600 }
601
602 /**
603 * Finds the join points of a body.
604 * <p>
605 * A join point is a block that is in the dominance frontier of one or more predecessors, that make one or more
606 * stores to variables (using the {@code VarStoreOp} operation on the result of a {@code VarOp} operation).
607 * The join point contains the set variables ({@code VarOp} operations) that are stored to.
608 * <p>
609 * A variable of a joint point indicates that a block argument may need to be added to the join point's block
610 * when converting variables to SSA form. Different values of a variable may occur at different control flow
611 * paths at the join point. The block argument represents the convergence of multiple values for the same
612 * variable, where a predecessor assigns to the block argument.
613 * (Block arguments are equivalent to phi-values, or phi-nodes, used in other representations.)
614 *
615 * @param body the body.
616 * @param joinPoints the returned join points.
617 * @implNote See "Efficiently Computing Static Single Assignment Form and the Control Dependence Graph" by Ron Cytron et. al.
618 * Section 5.1 and Figure 11.
619 */
620 static void findJoinPoints(Body body, Map<Block, Set<CoreOp.VarOp>> joinPoints) {
621 Map<Block, Set<Block>> df = body.dominanceFrontier();
622 Map<CoreOp.VarOp, Set<Block>> a = findVarStores(body);
623
624 int iterCount = 0;
625 int[] hasAlready = new int[body.blocks().size()];
626 int[] work = new int[body.blocks().size()];
627
628 Deque<Block> w = new ArrayDeque<>();
629
630 for (CoreOp.VarOp v : a.keySet()) {
631 iterCount++;
632
633 for (Block x : a.get(v)) {
634 work[x.index()] = iterCount;
635 w.push(x);
636 }
637
638 while (!w.isEmpty()) {
639 Block x = w.pop();
640
641 for (Block y : df.getOrDefault(x, Set.of())) {
642 if (hasAlready[y.index()] < iterCount) {
643 // Only add to the join points if y is dominated by the var's block
644 if (y.isDominatedBy(v.ancestorBlock())) {
645 joinPoints.computeIfAbsent(y, _k -> new LinkedHashSet<>()).add(v);
646 }
647 hasAlready[y.index()] = iterCount;
648
649 if (work[y.index()] < iterCount) {
650 work[y.index()] = iterCount;
651 w.push(y);
652 }
653 }
654 }
655 }
656 }
657 }
658
659 // Returns map of variable to blocks that contain stores to the variables declared in the body
660 // Throws ISE if a descendant store operation is encountered
661 // @@@ Compute map for whole tree, then traverse keys with filter
662 static Map<CoreOp.VarOp, Set<Block>> findVarStores(Body r) {
663 LinkedHashMap<CoreOp.VarOp, Set<Block>> stores = new LinkedHashMap<>();
664 r.elements().forEach(e -> {
665 if (e instanceof CoreOp.VarAccessOp.VarStoreOp storeOp) {
666 if (storeOp.varOp().ancestorBody() != storeOp.ancestorBody()) {
667 throw new IllegalStateException("Descendant variable store operation");
668 }
669 if (storeOp.varOp().ancestorBody() == r) {
670 stores.computeIfAbsent(storeOp.varOp(), _v -> new LinkedHashSet<>()).add(storeOp.ancestorBlock());
671 }
672 }
673 });
674 return stores;
675 }
676
677 record Node(Block b, Set<Node> children) {
678 }
679
680 static Node buildDomTree(Block entryBlock, Map<Block, Block> idoms) {
681 Map<Block, Node> tree = new HashMap<>();
682 Node root = new Node(entryBlock, new HashSet<>());
683 tree.put(entryBlock, root);
684 for (Map.Entry<Block, Block> e : idoms.entrySet()) {
685 Block b = e.getKey();
686 Block id = e.getValue();
687 if (id == null) {
688 assert b == entryBlock;
689 continue;
690 }
691
692 Node parent = tree.computeIfAbsent(id, _k -> new Node(_k, new HashSet<>()));
693 Node child = tree.computeIfAbsent(b, _k -> new Node(_k, new HashSet<>()));
694 parent.children.add(child);
695 }
696 return root;
697 }
698 }
699 }