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;
27
28 import jdk.incubator.code.dialect.core.CoreOp;
29 import java.util.*;
30 import java.util.function.BiConsumer;
31 import java.util.function.Consumer;
32 import java.util.function.Function;
33 import java.util.stream.Collectors;
34
35 import static jdk.incubator.code.dialect.core.CoreOp.return_;
36 import static jdk.incubator.code.dialect.core.CoreOp.branch;
37
38 /**
39 * A (basic) block containing an ordered sequence of operations, where the last operation is
40 * a {@link Op.Terminating terminating} operation.
41 * <p>
42 * The terminating operation, according to its specification, may branch to other blocks contained in the
43 * same parent body, by way of its {@link Op#successors() successors}, or exit the parent body and optionally
44 * yield a result.
45 * <p>
46 * Blocks may declare one or more block parameters.
47 */
48 public final class Block implements CodeElement<Block, Op> {
49
50 /**
51 * A value that is a block parameter
52 */
53 public static final class Parameter extends Value {
54 Parameter(Block block, TypeElement type) {
55 super(block, type);
56 }
57
58 @Override
59 public String toString() {
60 return "%param@" + Integer.toHexString(hashCode());
61 }
62
63 @Override
64 public Set<Value> dependsOn() {
65 return Set.of();
66 }
67
68 /**
69 * Returns the invokable operation associated with this block parameter.
70 * <p>
71 * If this block parameter is declared in an entry block and that
72 * block's ancestor operation (the parent of the entry block's parent body)
73 * is an instance of {@link Op.Invokable}, then that instance is returned,
74 * otherwise {@code null} is returned.
75 * <p>
76 * A non-{@code null} result implies this parameter is an invokable parameter.
77 *
78 * @apiNote
79 * This method may be used to pattern match on the returned result:
80 * {@snippet lang = "java":
81 * if (p.invokableOperation() instanceof CoreOp.FuncOp f) {
82 * assert f.parameters().indexOf(p) == p.index(); // @link substring="parameters()" target="Op.Invokable#parameters()"
83 * }
84 *}
85 *
86 * @return the invokable operation, otherwise {@code null} if the operation
87 * is not an instance of {@link Op.Invokable}.
88 * @see Op.Invokable#parameters()
89 */
90 public Op.Invokable invokableOperation() {
91 if (declaringBlock().isEntryBlock() &&
92 declaringBlock().parentBody().parentOp() instanceof Op.Invokable o) {
93 return o;
94 } else {
95 return null;
96 }
97 }
98
99 /**
100 * {@return the index of this block parameter in the parameters of its declaring block.}
101 * @see Value#declaringBlock()
102 * @see Block#parameters()
103 */
104 public int index() {
105 return declaringBlock().parameters().indexOf(this);
106 }
107 }
108
109 /**
110 * A block reference that refers to a block with arguments.
111 * <p>
112 * A terminating operation may refer, via a block reference, to one or more blocks as its successors.
113 * When control is passed from a block to a successor block the values of the block reference's arguments are
114 * assigned, in order, to the successor block's parameters.
115 */
116 public static final class Reference {
117 final Block target;
118 final List<Value> arguments;
119
120 /**
121 * Constructs a block reference for a given target block and arguments.
122 *
123 * @param target the target block.
124 * @param arguments the target block arguments, a copy will be made as needed.
125 */
126 Reference(Block target, List<? extends Value> arguments) {
127 this.target = target;
128 this.arguments = List.copyOf(arguments);
129 }
130
131 /**
132 * {@return the target block.}
133 * @throws IllegalStateException if the target block is partially built
134 */
135 public Block targetBlock() {
136 if (!isBound()) {
137 throw new IllegalStateException("Target block is partially built");
138 }
139
140 return target;
141 }
142
143 /**
144 * {@return the block arguments.}
145 */
146 public List<Value> arguments() {
147 return arguments;
148 }
149
150 boolean isBound() {
151 return target.isBound();
152 }
153 }
154
155 final Body parentBody;
156
157 final List<Parameter> parameters;
158
159 final List<Op> ops;
160
161 // @@@ In topological order
162 // @@@ Create lazily
163 // Can the representation be more efficient e.g. an array?
164 final SequencedSet<Block> predecessors;
165
166 // Reverse postorder index
167 // Set when block's body has sorted its blocks and therefore set when built
168 // Block is inoperable when < 0 i.e., when partially built
169 int index = -1;
170
171 Block(Body parentBody) {
172 this(parentBody, List.of());
173 }
174
175 Block(Body parentBody, List<TypeElement> parameterTypes) {
176 this.parentBody = parentBody;
177 this.parameters = new ArrayList<>();
178 for (TypeElement param : parameterTypes) {
179 parameters.add(new Parameter(this, param));
180 }
181 this.ops = new ArrayList<>();
182 this.predecessors = new LinkedHashSet<>();
183 }
184
185
186 @Override
187 public String toString() {
188 return "^block_" + index + "@" + Integer.toHexString(hashCode());
189 }
190
191 /**
192 * Returns this block's parent body.
193 *
194 * @return this block's parent body.
195 */
196 @Override
197 public Body parent() {
198 return parentBody;
199 }
200
201 /**
202 * Returns this block's parent body.
203 *
204 * @return this block's parent body.
205 */
206 public Body parentBody() {
207 return parentBody;
208 }
209
210 @Override
211 public List<Op> children() {
212 return ops();
213 }
214
215 /**
216 * Returns the sequence of operations contained in this block.
217 *
218 * @return returns the sequence operations, as an unmodifiable list.
219 */
220 public List<Op> ops() {
221 return Collections.unmodifiableList(ops);
222 }
223
224 /**
225 * Returns this block's index within the parent body's blocks.
226 * <p>
227 * The following identity holds true:
228 * {@snippet lang = "java" :
229 * this.parentBody().blocks().indexOf(this) == this.index();
230 * }
231 *
232 * @apiNote
233 * The block's index may be used to efficiently track blocks using
234 * bits sets or boolean arrays.
235 *
236 * @return the block index.
237 */
238 public int index() {
239 return index;
240 }
241
242 /**
243 * Returns the block parameters.
244 *
245 * @return the block parameters, as an unmodifiable list.
246 */
247 public List<Parameter> parameters() {
248 return Collections.unmodifiableList(parameters);
249 }
250
251 /**
252 * Returns the block parameter types.
253 *
254 * @return the block parameter types, as am unmodifiable list.
255 */
256 public List<TypeElement> parameterTypes() {
257 return parameters.stream().map(Value::type).toList();
258 }
259
260 /**
261 * Finds the operation in this block that is the ancestor of the given operation.
262 *
263 * @param op the given operation.
264 * @return the operation in this block that is the ancestor of the given operation,
265 * otherwise {@code null}
266 */
267 public Op findAncestorOpInBlock(Op op) {
268 Objects.requireNonNull(op);
269
270 while (op != null && op.parentBlock() != this) {
271 Body encBody = op.ancestorBody();
272 if (encBody == null) {
273 return null;
274 }
275
276 op = encBody.parentOp();
277 }
278
279 return op;
280 }
281
282 /**
283 * Returns the first operation in this block.
284 *
285 * @return the first operation in this block.
286 */
287 public Op firstOp() {
288 return ops.getFirst();
289 }
290
291 /**
292 * Returns the last, terminating, operation in this block.
293 * <p>
294 * The terminating operation implements {@link Op.Terminating}.
295 *
296 * @return the last, terminating, operation in this block.
297 */
298 public Op terminatingOp() {
299 Op lop = ops.getLast();
300 assert lop instanceof Op.Terminating;
301 return lop;
302 }
303
304 /**
305 * Returns the next operation after the given operation, otherwise {@code null}
306 * if this operation is the last operation.
307 *
308 * @param op the operation
309 * @return the next operation after the given operation.
310 */
311 public Op nextOp(Op op) {
312 int i = ops.indexOf(op);
313 if (i == -1) {
314 throw new IllegalArgumentException();
315 }
316 return i < ops().size() - 1 ? ops.get(i + 1) : null;
317 }
318
319 /**
320 * Returns the set of predecessors, the set containing each block in the parent
321 * body that refers to this block as a successor.
322 *
323 * @return the set of predecessors, as an unmodifiable set.
324 * @apiNote A block may refer to itself as a successor and therefore also be its predecessor.
325 */
326 public SequencedSet<Block> predecessors() {
327 return Collections.unmodifiableSequencedSet(predecessors);
328 }
329
330 /**
331 * Returns the list of predecessor references to this block.
332 * <p>
333 * This method behaves is if it returns the result of the following expression:
334 * {@snippet lang = java:
335 * predecessors.stream().flatMap(p->successors().stream())
336 * .filter(r->r.targetBlock() == this)
337 * .toList();
338 *}
339 *
340 * @return the list of predecessor references to this block, as an unmodifiable list.
341 * @apiNote A predecessor block may reference it successor block one or more times.
342 */
343 public List<Block.Reference> predecessorReferences() {
344 return predecessors.stream().flatMap(p -> successors().stream())
345 .filter(r -> r.targetBlock() == this)
346 .toList();
347 }
348
349 /**
350 * Returns the list of successors referring to other blocks.
351 * <p>
352 * The successors are declared by the terminating operation contained in this block.
353 *
354 * @return the list of successors, as an unmodifiable list.
355 * @apiNote given a block, A say, whose successor targets a block, B say, we can
356 * state that B is a successor block of A and A is a predecessor block of B.
357 */
358 public List<Reference> successors() {
359 Op lopr = ops.get(ops.size() - 1);
360 return lopr.successors();
361 }
362
363 /**
364 * Returns the set of target blocks referred to by the successors of this block.
365 * <p>
366 * This method behaves is if it returns the result of the following expression:
367 * {@snippet lang = java:
368 * successors().stream()
369 * .map(Block.Reference::targetBlock)
370 * .toList();
371 *}
372 *
373 * @return the list of target blocks, as an unmodifiable set.
374 */
375 public SequencedSet<Block> successorTargets() {
376 return successors().stream().map(Block.Reference::targetBlock).collect(Collectors.toCollection(LinkedHashSet::new));
377 }
378
379 /**
380 * Returns true if this block is an entry block.
381 *
382 * @return true if this block is an entry block.
383 */
384 public boolean isEntryBlock() {
385 return parentBody.entryBlock() == this;
386 }
387
388 /**
389 * Returns {@code true} if this block is
390 * <a href="https://en.wikipedia.org/wiki/Dominator_(graph_theory)">dominated by</a> the given block {@code dom}.
391 * This block is dominated by {@code dom}, if every path from the root entry block to this block passes through
392 * {@code dom}.
393 * <p>
394 * If this block, {@code b} say, and {@code dom} are not in the same parent body,
395 * then {@code b} becomes the nearest ancestor block, result of {@code b.parentBody().parentOp().parentBlock()},
396 * and so on until either:
397 * {@code b} is {@code null}, therefore {@code b} is <b>not</b> dominated by {@code dom} and this method
398 * returns {@code false}; or
399 * {@code b.parentBody() == dom.parentBody()}, therefore this method returns the result
400 * of {@code b.isDominatedBy(dom)}.
401 * <p>
402 * If this method returns {@code true} then {@code dom.isDominatedBy(this)}
403 * will return {@code false}. However, if this method returns {@code false} then it
404 * does not imply {@code dom.isDominatedBy(this)} returns {@code true}, as neither
405 * block may dominate the other.
406 *
407 * @param dom the dominating block
408 * @return {@code true} if this block is dominated by the given block.
409 */
410 // @@@ Should this be reversed and named dominates(Block b)
411 public boolean isDominatedBy(Block dom) {
412 Block b = findBlockForDomBody(this, dom.parentBody());
413 if (b == null) {
414 return false;
415 }
416
417 // A block non-strictly dominates itself
418 if (b == dom) {
419 return true;
420 }
421
422 // The entry block in b's body dominates all other blocks in the body
423 Block entry = b.parentBody().entryBlock();
424 if (dom == entry) {
425 return true;
426 }
427
428 // Traverse the immediate dominators until dom is reached or the entry block
429 Map<Block, Block> idoms = b.parentBody().immediateDominators();
430 Block idom = idoms.get(b);
431 while (idom != entry) {
432 if (idom == dom) {
433 return true;
434 }
435
436 idom = idoms.get(idom);
437 }
438
439 return false;
440 }
441
442 /**
443 * Returns the immediate dominator of this block, otherwise {@code null} if this block is the entry block.
444 * Both this block and the immediate dominator (if defined) have the same parent body.
445 * <p>
446 * The immediate dominator is the unique block that strictly dominates this block, but does not strictly dominate
447 * any other block that strictly dominates this block.
448 *
449 * @return the immediate dominator of this block, otherwise {@code null} if this block is the entry block.
450 */
451 public Block immediateDominator() {
452 if (this == parentBody().entryBlock()) {
453 return null;
454 }
455
456 Map<Block, Block> idoms = parentBody().immediateDominators();
457 return idoms.get(this);
458 }
459
460 /**
461 * Returns the immediate post dominator of this block, otherwise {@link Body#IPDOM_EXIT} if this block is the
462 * only block with no successors or if this block is one of many blocks that has no successors.
463 * Both this block and the immediate post dominator (if defined) have the same parent body.
464 * <p>
465 * The post immediate dominator is the unique block that strictly post dominates this block, but does not strictly
466 * post dominate any other block that strictly post dominates this block.
467 *
468 * @return the immediate dominator of this block, otherwise {@code null} if this block is the entry block.
469 */
470 public Block immediatePostDominator() {
471 if (this == parentBody().entryBlock()) {
472 return null;
473 }
474
475 Map<Block, Block> ipdoms = parentBody().immediatePostDominators();
476 Block ipdom = ipdoms.get(this);
477 return ipdom == this ? Body.IPDOM_EXIT : ipdom;
478 }
479
480 // @@@ isPostDominatedBy and immediatePostDominator
481
482 private static Block findBlockForDomBody(Block b, final Body domr) {
483 Body rb = b.parentBody();
484 while (domr != rb) {
485 // @@@ What if body is isolated
486
487 b = rb.parentOp().parentBlock();
488 // null when op is top-level (and its body is isolated), or not yet assigned to block
489 if (b == null) {
490 return null;
491 }
492 rb = b.parentBody();
493 }
494 return b;
495 }
496
497 /**
498 * A builder of a block.
499 * <p>
500 * When the parent body builder is built this block builder is also built. If a built builder
501 * is operated on to append a block parameter, append an operation, or add a block, then
502 * an {@code IllegalStateException} is thrown.
503 */
504 public final class Builder implements Function<Op, Op.Result> {
505 final Body.Builder parentBody;
506 final CopyContext cc;
507 final OpTransformer ot;
508
509 Builder(Body.Builder parentBody, CopyContext cc, OpTransformer ot) {
510 this.parentBody = parentBody;
511 this.cc = cc;
512 this.ot = ot;
513 }
514
515 void check() {
516 parentBody.check();
517 }
518
519 Block target() {
520 return Block.this;
521 }
522
523 /**
524 * {@return the block builder's operation transformer}
525 */
526 public OpTransformer transformer() {
527 return ot;
528 }
529
530 /**
531 * {@return the block builder's context}
532 */
533 public CopyContext context() {
534 return cc;
535 }
536
537 /**
538 * {@return the parent body builder}
539 */
540 public Body.Builder parentBody() {
541 return parentBody;
542 }
543
544 /**
545 * Returns the entry block builder for parent body.
546 *
547 * <p>The returned block is rebound if necessary to this block builder's
548 * context and transformer.
549 *
550 * @return the entry block builder for parent body builder
551 */
552 public Block.Builder entryBlock() {
553 return parentBody.entryBlock.rebind(cc, ot);
554 }
555
556 /**
557 * {@return true if this block builder is a builder of the entry block}
558 */
559 public boolean isEntryBlock() {
560 return Block.this == parentBody.target().entryBlock();
561 }
562
563 /**
564 * Rebinds this block builder with the given context and operation transformer.
565 *
566 * <p>Either this block builder and the returned block builder may be operated on to build
567 * the same block.
568 * Both are equal to each other, and both are closed when the parent body builder is closed.
569 *
570 * @param cc the context
571 * @param ot the operation transformer
572 * @return the rebound block builder
573 */
574 public Block.Builder rebind(CopyContext cc, OpTransformer ot) {
575 return this.cc == cc && this.ot == ot
576 ? this
577 : this.target().new Builder(parentBody(), cc, ot);
578 }
579
580 /**
581 * Adds a new block to the parent body.
582 *
583 * @param params the block's parameter types
584 * @return the new block builder
585 */
586 public Block.Builder block(TypeElement... params) {
587 return block(List.of(params));
588 }
589
590 /**
591 * Adds a new block to the parent body.
592 *
593 * @param params the block's parameter types
594 * @return the new block builder
595 */
596 public Block.Builder block(List<TypeElement> params) {
597 return parentBody.block(params, cc, ot);
598 }
599
600 /**
601 * Returns an unmodifiable list of the block's parameters.
602 *
603 * @return the unmodifiable list of the block's parameters
604 */
605 public List<Parameter> parameters() {
606 return Collections.unmodifiableList(parameters);
607 }
608
609 /**
610 * Appends a block parameter to the block's parameters.
611 *
612 * @param p the parameter type
613 * @return the appended block parameter
614 */
615 public Parameter parameter(TypeElement p) {
616 check();
617 return appendBlockParameter(p);
618 }
619
620 /**
621 * Creates a reference to this block that can be used as a successor of a terminating operation.
622 *
623 * @param args the block arguments
624 * @return the reference to this block
625 * @throws IllegalStateException if this block builder is associated with the entry block.
626 */
627 public Reference successor(Value... args) {
628 return successor(List.of(args));
629 }
630
631 /**
632 * Creates a reference to this block that can be used as a successor of a terminating operation.
633 *
634 * @param args the block arguments
635 * @return the reference to this block
636 * @throws IllegalStateException if this block builder is associated with the entry block.
637 */
638 public Reference successor(List<? extends Value> args) {
639 if (isEntryBlock()) {
640 throw new IllegalStateException("Entry block cannot be referred to as a successor");
641 }
642
643 return new Reference(Block.this, List.copyOf(args));
644 }
645
646 /**
647 * An inline consumer that inserts a return operation with a value, if non-null.
648 */
649 public static final BiConsumer<Block.Builder, Value> INLINE_RETURN = (block, value) -> {
650 block.op(value != null ? return_(value) : CoreOp.return_());
651 };
652
653 /**
654 * Inlines the invokable operation into this block and returns the block builder from which to
655 * continue building.
656 * <p>
657 * This method {@link #transformBody(Body, List, CopyContext, OpTransformer) transforms} the body of the
658 * invokable operation with the given arguments, a new context, and an operation transformer that
659 * replaces return operations by applying the given consumer to a block builder and a return value.
660 * <p>
661 * The operation transformer copies all operations except return operations whose nearest invokable operation
662 * ancestor is the given the invokable operation. When such a return operation is encountered, then on
663 * first encounter of its grandparent body a return block builder is computed and used for this return operation
664 * and encounters of subsequent return operations with the same grandparent body.
665 * <p>
666 * If the grandparent body has only one block then operation transformer's block builder is the return
667 * block builder. Otherwise, if the grandparent body has one or more blocks then the return block builder is
668 * created from the operation transformer's block builder. The created return block builder will have a block
669 * parameter whose type corresponds to the return type, or will have no parameter for void return.
670 * The computation finishes by applying the return block builder and a return value to the inlining consumer.
671 * If the grandparent body has only one block then the return value is the value mapped from the return
672 * operation's operand, or is null for void return. Otherwise, if the grandparent body has one or more blocks
673 * then the value is the block parameter of the created return block builder, or is null for void return.
674 * <p>
675 * For every encounter of a return operation the associated return block builder is compared against the
676 * operation transformer's block builder. If they are not equal then a branch operation is added to the
677 * operation transformer's block builder whose successor is the return block builder with a block argument
678 * that is the value mapped from the return operation's operand, or with no block argument for void return.
679 * @apiNote
680 * It is easier to inline an invokable op if its body is in lowered form (there are no operations in the blocks
681 * of the body that are lowerable). This ensures a single exit point can be created (paired with the single
682 * entry point). If there are one or more nested return operations, then there is unlikely to be a single exit.
683 * Transforming the model to create a single exit point while preserving nested structure is in general
684 * non-trivial and outside the scope of this method. In such cases the invokable operation can be transformed
685 * with a lowering transformation after which it can then be inlined.
686 *
687 * @param invokableOp the invokable operation
688 * @param args the arguments to map to the invokable operation's parameters
689 * @param inlineConsumer the consumer applied to process the return from the invokable operation.
690 * This is called once for each grandparent body of a return operation, with a block to
691 * build replacement operations and the return value, or null for void return.
692 * @return the block builder to continue building from
693 * @param <O> The invokable type
694 */
695 public <O extends Op & Op.Invokable> Block.Builder inline(O invokableOp, List<? extends Value> args,
696 BiConsumer<Block.Builder, Value> inlineConsumer) {
697 Map<Body, Block.Builder> returnBlocks = new HashMap<>();
698 // Create new context, ensuring inlining is isolated
699 transformBody(invokableOp.body(), args, CopyContext.create(), (block, op) -> {
700 // If the return operation is associated with the invokable operation
701 if (op instanceof CoreOp.ReturnOp rop && getNearestInvokeableAncestorOp(op) == invokableOp) {
702 // Compute the return block
703 Block.Builder returnBlock = returnBlocks.computeIfAbsent(rop.ancestorBody(), _body -> {
704 Block.Builder rb;
705 // If the body has one block we know there is just one return op declared, otherwise there may
706 // one or more. If so, create a new block that joins all the returns.
707 // Note: we could count all return op in a body to avoid creating a new block for a body
708 // with two or more blocks with only one returnOp is declared.
709 Value r;
710 if (rop.ancestorBody().blocks().size() != 1) {
711 List<TypeElement> param = rop.returnValue() != null
712 ? List.of(invokableOp.invokableType().returnType())
713 : List.of();
714 rb = block.block(param);
715 r = !param.isEmpty()
716 ? rb.parameters().get(0)
717 : null;
718 } else {
719 r = rop.returnValue() != null
720 ? block.context().getValue(rop.returnValue())
721 : null;
722 rb = block;
723 }
724
725 // Inline the return
726 inlineConsumer.accept(rb, r);
727
728 return rb;
729 });
730
731 // Replace the return op with a branch to the return block, if needed
732 if (!returnBlock.equals(block)) {
733 // Replace return op with branch to return block, with given return value
734 List<Value> arg = rop.returnValue() != null
735 ? List.of(block.context().getValue(rop.returnValue()))
736 : List.of();
737 block.apply(branch(returnBlock.successor(arg)));
738 }
739
740 return block;
741 }
742
743 block.apply(op);
744 return block;
745 });
746
747
748 Builder builder = returnBlocks.get(invokableOp.body());
749 return builder != null ? builder : this;
750 }
751
752 private static Op getNearestInvokeableAncestorOp(Op op) {
753 do {
754 op = op.ancestorBody().parentOp();
755 } while (!(op instanceof Op.Invokable));
756 return op;
757 }
758
759 /**
760 * Transforms a body into this block, with this block builder's context.
761 *
762 * @param bodyToTransform the body to transform
763 * @param args the list of output values to map to the input parameters of the body's entry block
764 * @param ot the operation transformer
765 * @see #transformBody(Body, List, CopyContext, OpTransformer)
766 */
767 public void transformBody(Body bodyToTransform, List<? extends Value> args,
768 OpTransformer ot) {
769 transformBody(bodyToTransform, args, cc, ot);
770 }
771
772 /**
773 * Transforms a body into this block.
774 * <p>
775 * First, a new context is created from the given context and that new context is used to map values and
776 * blocks.
777 * <p>
778 * Second, the entry block is mapped to this block builder rebound with the given operation transformer and
779 * copy context, the input block parameters of the body's entry block are mapped to the given arguments.
780 * <p>
781 * Third, for each input block in the body (except the entry block) an output block builder is created with
782 * equivalent parameters as the input block and with the given operation transformer and copy context.
783 * The input block parameters are mapped to the output block parameters, and the input block is mapped to the
784 * output block builder.
785 * <p>
786 * Fourth, for each input block in the body (in order) the input block's operations are transformed
787 * by applying the output block builder and input block to the given operation transformer.
788 * <p>
789 * When the parent body is built any empty non-entry blocks that have no successors will be removed.
790 *
791 * @param bodyToTransform the body to transform
792 * @param args the list of output values to map to the input parameters of the body's entry block
793 * @param cc the copy context, for values captured in the body
794 * @param ot the operation transformer
795 */
796 public void transformBody(Body bodyToTransform, List<? extends Value> args,
797 CopyContext cc, OpTransformer ot) {
798 check();
799
800 // @@@ This might be a new context e.g., when transforming a body
801 cc = CopyContext.create(cc);
802
803 Block entryBlockToTransform = bodyToTransform.entryBlock();
804 List<Block> blocksToTransform = bodyToTransform.blocks();
805
806 // Map entry block
807 // Rebind this block builder to the created context and transformer
808 Block.Builder startingBlock = rebind(cc, ot);
809 cc.mapBlock(entryBlockToTransform, startingBlock);
810 cc.mapValues(entryBlockToTransform.parameters(), args);
811
812 // Map subsequent blocks up front, for forward referencing successors
813 for (int i = 1; i < blocksToTransform.size(); i++) {
814 Block blockToTransform = blocksToTransform.get(i);
815 if (cc.getBlock(blockToTransform) != null) {
816 throw new IllegalStateException("Block is already transformed");
817 }
818
819 // Create block and map block
820 Block.Builder transformedBlock = startingBlock.block(List.of());
821 for (Block.Parameter ba : blockToTransform.parameters()) {
822 transformedBlock.parameter(ba.type());
823 }
824 cc.mapBlock(blockToTransform, transformedBlock);
825 cc.mapValues(blockToTransform.parameters(), transformedBlock.parameters());
826 }
827
828 for (Block blockToTransform : blocksToTransform) {
829 ot.apply(cc.getBlock(blockToTransform), blockToTransform);
830 }
831 }
832
833 /**
834 * Appends operations into the block builder in the scope of the builder as an argument
835 * to the given consumer.
836 *
837 * @param c the consumer.
838 */
839 // @@@ Is this needed?
840 public void ops(Consumer<Builder> c) {
841 c.accept(this);
842 }
843
844 /**
845 * Appends an operation to this block, with no operation result name, and this builder's transformer.
846 *
847 * @param op the operation to append
848 * @return the operation result of the appended operation
849 * @throws IllegalStateException if the operation is structurally invalid
850 * @see #op(Op, OpTransformer)
851 */
852 @Override
853 public Op.Result apply(Op op) {
854 return op(op, ot);
855 }
856
857 /**
858 * Appends an operation to this block, with no operation result name, and this builder's transformer.
859 *
860 * @param op the operation to append
861 * @return the operation result of the appended operation
862 * @throws IllegalStateException if the operation is structurally invalid
863 * @see #op(Op, OpTransformer)
864 */
865 public Op.Result op(Op op) {
866 return op(op, ot);
867 }
868
869 /**
870 * Appends an operation to this block.
871 * <p>
872 * If the operation is not bound to a block, then the operation is appended and bound to this block.
873 * Otherwise, if the operation is bound, the operation is first
874 * {@link Op#transform(CopyContext, OpTransformer) transformed} with this builder's context and the given
875 * operation transformer, the unbound transformed operation is appended, and the operation's result is mapped
876 * to the transformed operation's result (using the builder's context).
877 * <p>
878 * If the unbound operation (transformed, or otherwise) is structurally invalid then an
879 * {@code IllegalStateException} is thrown. An unbound operation is structurally invalid if:
880 * <ul>
881 * <li>any of its bodies does not have the same ancestor body as this block's parent body.
882 * <li>any of its operands (values) is not reachable from this block.
883 * <li>any of its successors is not a sibling of this block.
884 * <li>any of its successors arguments (values) is not reachable from this block.
885 * </ul>
886 * A value is reachable from this block if there is a path from this block's parent body,
887 * via its ancestor bodies, to the value's block's parent body. (Note this structural check
888 * ensures values are only used from the same tree being built, but it is weaker than a
889 * dominance check that may be performed when the parent body is built.)
890 *
891 * @param op the operation to append
892 * @param transformer the transformer to use when appending a bound operation
893 * @return the operation result of the appended operation
894 * @throws IllegalStateException if the operation is structurally invalid
895 */
896 public Op.Result op(Op op, OpTransformer transformer) {
897 check();
898 final Op.Result oprToTransform = op.result();
899
900 Op transformedOp = op;
901 if (oprToTransform != null) {
902 // If operation is assigned to block, then copy it and transform its contents
903 transformedOp = op.transform(cc, transformer);
904 assert transformedOp.result == null;
905 }
906
907 Op.Result transformedOpr = insertOp(transformedOp);
908
909 if (oprToTransform != null) {
910 // Map the result of the first transformation
911 // @@@ If the same operation is transformed more than once then subsequent
912 // transformed ops will not get implicitly mapped
913 // Should this be an error?
914 cc.mapValueIfAbsent(oprToTransform, transformedOpr);
915 }
916
917 return transformedOpr;
918 }
919
920 /**
921 * Returns true if this block builder is equal to the other object.
922 * <p>This block builder is equal if the other object is an instance of a block builder, and they are
923 * associated with the same block (but perhaps bound to different contexts and transformers).
924 *
925 * @param o the other object
926 * @return true if this builder is equal to the other object.
927 */
928 @Override
929 public boolean equals(Object o) {
930 if (this == o) return true;
931 return o instanceof Builder that && Block.this == that.target();
932 }
933
934 @Override
935 public int hashCode() {
936 return Block.this.hashCode();
937 }
938 }
939
940 // Modifying methods
941
942 // Create block parameter associated with this block
943 private Parameter appendBlockParameter(TypeElement type) {
944 Parameter blockParameter = new Parameter(this, type);
945 parameters.add(blockParameter);
946
947 return blockParameter;
948 }
949
950 // Create an operation, adding to the end of the list of existing operations
951 private Op.Result insertOp(Op op) {
952 Op.Result opResult = new Op.Result(this, op);
953 bindOp(opResult, op);
954
955 ops.add(op);
956 return opResult;
957 }
958
959 private void bindOp(Op.Result opr, Op op) {
960 // Structural checks
961 if (!ops.isEmpty() && ops.getLast() instanceof Op.Terminating) {
962 throw new IllegalStateException("Operation cannot be appended, the block has a terminal operation");
963 }
964
965 for (Body b : op.bodies()) {
966 if (b.ancestorBody != null && b.ancestorBody != this.parentBody) {
967 throw new IllegalStateException("Body of operation is bound to a different ancestor body: ");
968 }
969 }
970
971 for (Value v : op.operands()) {
972 if (!isReachable(v)) {
973 throw new IllegalStateException(
974 String.format("Operand of operation %s is not defined in tree: %s", op, v));
975 }
976 assert !v.isBound();
977 }
978
979 for (Reference s : op.successors()) {
980 if (s.target.parentBody != this.parentBody) {
981 throw new IllegalStateException("Target of block reference is not a sibling of this block");
982 }
983
984 for (Value v : s.arguments()) {
985 if (!isReachable(v)) {
986 throw new IllegalStateException(
987 String.format("Argument of block reference %s of terminating operation %s is not defined in tree: %s", s, op, v));
988 }
989 assert !v.isBound();
990 }
991 }
992
993 // State updates after structural checks
994 // @@@ The alternative is to close the body builder on failure, rendering it inoperable,
995 // so checks and updates can be merged
996 for (Value v : op.operands()) {
997 v.uses.add(opr);
998 }
999
1000 for (Reference s : op.successors()) {
1001 for (Value v : s.arguments()) {
1002 v.uses.add(opr);
1003 }
1004
1005 s.target.predecessors.add(Block.this);
1006 }
1007
1008 op.result = opr;
1009 }
1010
1011 // Determine if the parent body of value's block is an ancestor of this block
1012 private boolean isReachable(Value v) {
1013 Body b = parentBody;
1014 while (b != null && b != v.block.parentBody) {
1015 b = b.ancestorBody;
1016 }
1017 return b != null;
1018 }
1019
1020 //
1021
1022 boolean isBound() {
1023 return index >= 0;
1024 }
1025 }