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