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;
27
28 import java.util.*;
29 import java.util.stream.Collectors;
30
31 /**
32 * A block containing an ordered sequence of operations, where the last operation is a
33 * {@link Op.Terminating terminating} operation.
34 * <p>
35 * The terminating operation, according to its specification, may branch to other blocks contained in the same parent
36 * body, by way of its {@link Op#successors() successors}, or exit the parent body and optionally yield a result.
37 * <p>
38 * Blocks declare zero or more block parameters.
39 * <p>
40 * A block is built using a {@link Block.Builder}, as part of the
41 * <a href="Body.Builder.html#body-building-process">process of building</a> its parent body.
42 */
43 public final class Block implements CodeElement<Block, Op> {
44
45 /**
46 * A value that is a block parameter
47 */
48 public static final class Parameter extends Value {
49 Parameter(Block block, CodeType type) {
50 super(block, type);
51 }
52
53 @Override
54 public String toString() {
55 return "%param@" + Integer.toHexString(hashCode());
56 }
57
58 @Override
59 public SequencedSet<Value> dependsOn() {
60 return Collections.emptyNavigableSet();
61 }
62
63 /**
64 * Returns the invokable operation associated with this block parameter.
65 * <p>
66 * If this block parameter is declared in an entry block and that
67 * block's ancestor operation (the parent of the entry block's parent body)
68 * is an instance of {@link Op.Invokable}, then that instance is returned,
69 * otherwise {@code null} is returned.
70 * <p>
71 * A non-{@code null} result implies this parameter is an invokable parameter.
72 *
73 * @apiNote
74 * This method may be used to pattern match on the returned result:
75 * {@snippet lang = "java":
76 * if (p.invokableOperation() instanceof CoreOp.FuncOp f) {
77 * assert f.parameters().indexOf(p) == p.index(); // @link substring="parameters()" target="Op.Invokable#parameters()"
78 * }
79 * }
80 *
81 * @return the invokable operation, otherwise {@code null} if the operation
82 * is not an instance of {@link Op.Invokable}.
83 * @throws IllegalStateException if an <a href="Body.Builder.html#body-building-observability">unobservable</a>
84 * block is encountered
85 * @see Op.Invokable#parameters()
86 */
87 public Op.Invokable invokableOperation() {
88 Block b = declaringBlock();
89 if (b.isEntryBlock() && b.ancestorOp() instanceof Op.Invokable o) {
90 return o;
91 } else {
92 return null;
93 }
94 }
95
96 /**
97 * {@return the index of this block parameter in the parameters of its declaring block.}
98 * @throws IllegalStateException if this parameter's declaring block is
99 * <a href="Body.Builder.html#body-building-observability">unobservable</a>
100 * @see Value#declaringBlock()
101 * @see Block#parameters()
102 */
103 public int index() {
104 return declaringBlock().parameters().indexOf(this);
105 }
106 }
107
108 /**
109 * A block reference that refers to a block with arguments.
110 * <p>
111 * A terminating operation may refer, via a block reference, to one or more blocks as its successors.
112 * When control is passed from a block to a successor block the values of the block reference's arguments are
113 * assigned, in order, to the successor block's parameters.
114 */
115 public static final class Reference implements CodeItem {
116 final Block target;
117 final List<Value> arguments;
118
119 /**
120 * Constructs a block reference for a given target block and arguments.
121 *
122 * @param target the target block.
123 * @param arguments the target block arguments, a copy will be made as needed.
124 */
125 Reference(Block target, List<? extends Value> arguments) {
126 this.target = target;
127 this.arguments = List.copyOf(arguments);
128 }
129
130 /**
131 * {@return the target block.}
132 * @throws IllegalStateException if the target block is
133 * <a href="Body.Builder.html#body-building-observability">unobservable</a>
134 */
135 public Block targetBlock() {
136 if (!isBuilt()) {
137 throw new IllegalStateException("Target block is unobservable");
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 isBuilt() {
151 return target.isBuilt();
152 }
153 }
154
155 final Body parentBody;
156
157 final List<Parameter> parameters;
158
159 final List<Op> ops;
160
161 // In topological order of reverse postorder traversal
162 // @@@ Use bitset of block indexes?
163 final SequencedSet<Block> predecessors;
164
165 // Reverse postorder index
166 // Set when block's body has sorted its blocks and therefore set when built
167 // Block is unobservable when < 0 i.e., when not built
168 static final int UNBUILT_BLOCK_INDEX = -1;
169 int index = UNBUILT_BLOCK_INDEX;
170
171 Block(Body parentBody) {
172 this(parentBody, List.of());
173 }
174
175 Block(Body parentBody, List<CodeType> parameterTypes) {
176 this.parentBody = parentBody;
177 this.parameters = new ArrayList<>();
178 for (CodeType 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 @Override
202 public List<Op> children() {
203 return ops();
204 }
205
206 /**
207 * Returns the sequence of operations contained in this block.
208 *
209 * @return returns the sequence operations, as an unmodifiable list.
210 */
211 public List<Op> ops() {
212 return Collections.unmodifiableList(ops);
213 }
214
215 /**
216 * Returns this block's index within the parent body's blocks.
217 * <p>
218 * The following identity holds true:
219 * {@snippet lang = "java" :
220 * this.parentBody().blocks().indexOf(this) == this.index();
221 * }
222 *
223 * @apiNote
224 * The block's index may be used to efficiently track blocks using
225 * bits sets or boolean arrays.
226 *
227 * @return the block index.
228 */
229 public int index() {
230 return index;
231 }
232
233 /**
234 * Returns the block parameters.
235 *
236 * @return the block parameters, as an unmodifiable list.
237 */
238 public List<Parameter> parameters() {
239 return Collections.unmodifiableList(parameters);
240 }
241
242 /**
243 * Returns the block parameter types.
244 *
245 * @return the block parameter types, as am unmodifiable list.
246 */
247 public List<CodeType> parameterTypes() {
248 return parameters.stream().map(Value::type).toList();
249 }
250
251 /**
252 * Returns the first operation in this block.
253 *
254 * @return the first operation in this block.
255 */
256 public Op firstOp() {
257 return ops.getFirst();
258 }
259
260 /**
261 * Returns the last, terminating, operation in this block.
262 * <p>
263 * The terminating operation implements {@link Op.Terminating}.
264 *
265 * @return the last, terminating, operation in this block.
266 */
267 public Op terminatingOp() {
268 Op lop = ops.getLast();
269 assert lop instanceof Op.Terminating;
270 return lop;
271 }
272
273 /**
274 * Returns the next operation after the given operation, otherwise {@code null}
275 * if this operation is the last operation.
276 *
277 * @param op the operation
278 * @return the next operation after the given operation.
279 * @throws IllegalArgumentException if the operation is not a child of this block
280 */
281 public Op nextOp(Op op) {
282 int i = ops.indexOf(op);
283 if (i == -1) {
284 throw new IllegalArgumentException();
285 }
286 return i < ops().size() - 1 ? ops.get(i + 1) : null;
287 }
288
289 /**
290 * Returns the set of predecessors, the set containing each block in the parent
291 * body that refers to this block as a successor.
292 *
293 * @return the set of predecessors, as an unmodifiable sequenced set. The encounter order is unspecified
294 * and determined by the order in which operations are built.
295 * @apiNote A block may refer to itself as a successor and therefore also be its predecessor.
296 */
297 public SequencedSet<Block> predecessors() {
298 return Collections.unmodifiableSequencedSet(predecessors);
299 }
300
301 /**
302 * Returns the list of predecessor references to this block.
303 * <p>
304 * This method behaves is if it returns the result of the following expression:
305 * {@snippet lang = java:
306 * predecessors.stream().flatMap(p -> successors().stream())
307 * .filter(r -> r.targetBlock() == this)
308 * .toList();
309 *}
310 *
311 * @return the list of predecessor references to this block, as an unmodifiable list.
312 * @apiNote A predecessor block may reference it successor block one or more times.
313 */
314 public List<Block.Reference> predecessorReferences() {
315 return predecessors.stream().flatMap(p -> p.successors().stream())
316 .filter(r -> r.targetBlock() == this)
317 .toList();
318 }
319
320 /**
321 * Returns the list of successors referring to other blocks.
322 * <p>
323 * The successors are declared by the terminating operation contained in this block.
324 *
325 * @return the list of successors, as an unmodifiable list.
326 * @apiNote given a block, A say, whose successor targets a block, B say, we can
327 * state that B is a successor block of A and A is a predecessor block of B.
328 */
329 public List<Reference> successors() {
330 return ops.getLast().successors();
331 }
332
333 /**
334 * Returns the set of target blocks referred to by the successors of this block.
335 * <p>
336 * This method behaves is if it returns the result of the following expression:
337 * {@snippet lang = java:
338 * successors().stream()
339 * .map(Block.Reference::targetBlock)
340 * .collect(Collectors.toCollection(LinkedHashSet::new));
341 *}
342 *
343 * @return the set of target blocks, as an unmodifiable set.
344 */
345 public SequencedSet<Block> successorTargets() {
346 LinkedHashSet<Block> targets = successors().stream().map(Reference::targetBlock)
347 .collect(Collectors.toCollection(LinkedHashSet::new));
348 return Collections.unmodifiableSequencedSet(targets);
349 }
350
351 /**
352 * Returns true if this block is an entry block, the first block occurring
353 * in the parent body's list of blocks.
354 *
355 * @return true if this block is an entry block.
356 */
357 public boolean isEntryBlock() {
358 return parentBody.entryBlock() == this;
359 }
360
361 /**
362 * Returns {@code true} if this block is dominated by the given block {@code dom}.
363 * <p>
364 * A block {@code b} is dominated by {@code dom} if every path from the entry block of {@code dom}'s
365 * parent body to {@code b} passes through {@code dom}.
366 * <p>
367 * If this block and {@code dom} have different parent bodies, this method first
368 * repeatedly replaces this block with its {@link #ancestorBlock() nearest ancestor} block until:
369 * <ul>
370 * <li>{@code null} is reached, in which case this method returns {@code false}; or</li>
371 * <li>both blocks are in the same parent body, in which case
372 * <a href="https://en.wikipedia.org/wiki/Dominator_(graph_theory)">dominance</a> is tested within that body.</li>
373 * </ul>
374 *
375 * @apiNote
376 * The method {@link Body#immediateDominators()} can be used to test for dominance, by repeatedly querying a block's
377 * immediately dominating block until {@code null} or {@code dom} is reached.
378 *
379 * @param dom the dominating block
380 * @return {@code true} if this block is dominated by the given block.
381 * @see Body#immediateDominators()
382 * @see Value#isDominatedBy
383 */
384 public boolean isDominatedBy(Block dom) {
385 Block b = findBlockForDomBody(this, dom.ancestorBody());
386 if (b == null) {
387 return false;
388 }
389
390 // A block non-strictly dominates itself
391 if (b == dom) {
392 return true;
393 }
394
395 // The entry block in b's body dominates all other blocks in the body
396 Block entry = b.ancestorBody().entryBlock();
397 if (dom == entry) {
398 return true;
399 }
400
401 // Traverse the immediate dominators until dom is reached or the entry block
402 Map<Block, Block> idoms = b.ancestorBody().immediateDominators();
403 Block idom = idoms.get(b);
404 while (idom != null) {
405 if (idom == dom) {
406 return true;
407 }
408
409 idom = idoms.get(idom);
410 }
411
412 return false;
413 }
414
415 /**
416 * Returns the immediate dominator of this block, otherwise {@code null} if this block is the entry block.
417 * Both this block and the immediate dominator (if defined) have the same parent body.
418 * <p>
419 * The immediate dominator is the unique block that strictly dominates this block, but does not strictly dominate
420 * any other block that strictly dominates this block.
421 * <p>
422 * The entry block has no immediate dominator, since it is not strictly dominated by any other block.
423 *
424 * @return the immediate dominator of this block, otherwise {@code null} if this block is the entry block.
425 * @see Body#immediateDominators()
426 */
427 public Block immediateDominator() {
428 return ancestorBody().immediateDominators().get(this);
429 }
430
431 /**
432 * Returns the immediate post dominator of this block.
433 * <p>
434 * If this block is one of many block's in the same body with no successors, then there are multiple exit blocks,
435 * and the immediate post dominator of those blocks is the synthetic block {@link Body#IPDOM_EXIT} representing the
436 * single exit block. Otherwise, if this block is the only block in the body with no successors, then that block is
437 * the single exit block, and this method returns {@code null}.
438 * <p>
439 * Both this block and the immediate post dominator (if defined) have the same parent body, except for the
440 * synthetic block {@link Body#IPDOM_EXIT}.
441 * <p>
442 * The immediate post dominator is the unique block that strictly post dominates this block, but does not strictly
443 * post dominate any other block that strictly post dominates this block.
444 * <p>
445 * The exit block has no immediate post dominator, since it is not strictly post dominated by any other block.
446 *
447 * @return the immediate post dominator of this block, {@code Body#IPDOM_EXIT} if the synthetic exit is this block's
448 * immediate post dominator, or {@code null} if this block is the single exit block.
449 * @throws IllegalStateException if there is no single exit block, synthesized or otherwise
450 * @see Body#immediatePostDominators()
451 */
452 public Block immediatePostDominator() {
453 return ancestorBody().immediatePostDominators().get(this);
454 }
455
456 // @@@ isPostDominatedBy
457
458 private static Block findBlockForDomBody(Block b, final Body domr) {
459 Body rb = b.ancestorBody();
460 while (domr != rb) {
461 // @@@ What if body is isolated
462
463 b = rb.ancestorBlock();
464 // null when op is top-level (and its body is isolated), or not yet assigned to block
465 if (b == null) {
466 return null;
467 }
468 rb = b.ancestorBody();
469 }
470 return b;
471 }
472
473 /**
474 * A builder for a block.
475 * <p>
476 * A block builder builds one block as part of the <a href="Body.Builder.html#body-building-process">building process</a>
477 * of building its parent body. The block is not <a href="Body.Builder.html#body-building-observability">observable</a>
478 * until the parent body builder <a href="Body.Builder.html#body-building-finishing">finishes</a>.
479 * After <a href="Body.Builder.html#body-building-finishing">building finishes</a>,
480 * the block becomes observable, and the block builder becomes inoperable,
481 * regardless of whether building succeeds or fails with an exception.
482 * Further attempts to operate on the block builder throws an {@link IllegalStateException}.
483 * <p>
484 * A block builder has a code {@link #context() context} and code {@link #transformer() transformer}. These are used
485 * to perform <i>transform-on-append</i> when {@link #add appending} a placed operation. Any sibling block builder
486 * {@link #block(List) created} from a block builder will have the same code context and code transformer.
487 * <p>
488 * A block builder may be obtained with a different code context and code transformer by calling
489 * {@link #withContextAndTransformer(CodeContext, CodeTransformer)}. Such a block builder builds the same block, and
490 * can be used to apply alternative transformations to placed operations that are appended.
491 * <p>
492 * During {@link CodeTransformer code transformation}, a block builder may also serve as the current output block
493 * builder.
494 * <p>
495 * Block builders are not thread-safe.
496 */
497 public final class Builder {
498 final Body.Builder parentBody;
499 final CodeContext cc;
500 final CodeTransformer ct;
501
502 Builder(Body.Builder parentBody, CodeContext cc, CodeTransformer ct) {
503 this.parentBody = parentBody;
504 this.cc = cc;
505 this.ct = ct;
506 }
507
508 void check() {
509 parentBody.check();
510 }
511
512 Block target() {
513 check();
514 return Block.this;
515 }
516
517 /**
518 * {@return this block builder's code transformer}
519 */
520 public CodeTransformer transformer() {
521 check();
522 return ct;
523 }
524
525 /**
526 * {@return this block builder's code context}
527 */
528 public CodeContext context() {
529 check();
530 return cc;
531 }
532
533 /**
534 * {@return this block builder's parent body builder}
535 */
536 public Body.Builder parentBody() {
537 check();
538 return parentBody;
539 }
540
541 /**
542 * Returns the entry block builder of this builder's parent body builder.
543 * <p>
544 * The returned block builder has this block builder's code context and code transformer.
545 *
546 * @return the entry block builder of this builder's parent body builder
547 */
548 public Block.Builder entryBlock() {
549 check();
550 return parentBody.entryBlock.withContextAndTransformer(cc, ct);
551 }
552
553 /**
554 * {@return true if this block builder builds the entry block of its parent body}
555 */
556 public boolean isEntryBlock() {
557 check();
558 return Block.this == parentBody.target().entryBlock();
559 }
560
561 /**
562 * Returns a block builder for the same block with the given code context and code transformer.
563 * <p>
564 * Both this block builder and the returned block builder may be operated on to build the same block. Both are
565 * equal to each other, and both become inoperable when the parent body builder
566 * <a href="Body.Builder.html#body-building-finishing">finishes</a>.
567 *
568 * @param cc the code context
569 * @param ct the code transformer
570 * @return the block builder with the given code context and code transformer
571 */
572 public Block.Builder withContextAndTransformer(CodeContext cc, CodeTransformer ct) {
573 check();
574 return this.cc == cc && this.ct == ct
575 ? this
576 : this.target().new Builder(parentBody(), cc, ct);
577 }
578
579 /**
580 * Creates a builder for a new sibling block in this builder's parent body.
581 * <p>
582 * The returned builder has the same code context and code transformer as this
583 * block builder.
584 *
585 * @param params the parameter types of the new block
586 * @return the new block builder
587 */
588 public Block.Builder block(CodeType... params) {
589 return block(List.of(params));
590 }
591
592 /**
593 * Creates a builder for a new sibling block in this builder's parent body.
594 * <p>
595 * The returned builder has the same code context and code transformer as this
596 * block builder.
597 *
598 * @param params the parameter types of the new block
599 * @return the new block builder
600 */
601 public Block.Builder block(List<CodeType> params) {
602 check();
603 return parentBody.block(params, cc, ct);
604 }
605
606 /**
607 * Returns an unmodifiable list of this block's parameters.
608 *
609 * @return the unmodifiable list of this block's parameters
610 */
611 public List<Parameter> parameters() {
612 check();
613 return Collections.unmodifiableList(parameters);
614 }
615
616 /**
617 * Appends a parameter of the given type to this block.
618 *
619 * @param p the parameter type
620 * @return the appended block parameter
621 */
622 public Parameter parameter(CodeType p) {
623 check();
624 return appendBlockParameter(p);
625 }
626
627 /**
628 * Creates a reference to this block that can be used as a successor of a terminating operation.
629 * <p>
630 * A reference can only be created with arguments whose declaring block is being built.
631 *
632 * @param args the block arguments
633 * @return a reference to this block
634 * @throws IllegalStateException if this block builder builds the entry block.
635 * @throws IllegalArgumentException if any argument's declaring block is built.
636 */
637 public Reference reference(Value... args) {
638 return reference(List.of(args));
639 }
640
641 /**
642 * Creates a reference to this block that can be used as a successor of a terminating operation.
643 * <p>
644 * A reference can only be created with arguments whose declaring block is being built.
645 *
646 * @param args the block arguments
647 * @return a reference to this block
648 * @throws IllegalStateException if this block builder builds the entry block.
649 * @throws IllegalArgumentException if any argument's declaring block is built.
650 */
651 public Reference reference(List<? extends Value> args) {
652 check();
653
654 if (isEntryBlock()) {
655 throw new IllegalStateException("Entry block cannot be referenced and targeted as a successor");
656 }
657 for (Value operand : args) {
658 if (operand.isBuilt()) {
659 throw new IllegalArgumentException("Argument's declaring block is built: " + operand);
660 }
661 }
662
663 return new Reference(Block.this, List.copyOf(args));
664 }
665
666 /**
667 * Transforms the given body into this block builder's parent body, using this block builder as the current
668 * output block builder, a {@link CodeContext#create(CodeContext) child} of this block builder's code context,
669 * and the given code transformer.
670 * <p>
671 * This method behaves as if invoking {@link #transformBody(Body, List, CodeContext, CodeTransformer)} with the given
672 * body, the given entry values, a child of this block builder's code context, and the given code transformer.
673 *
674 * @param body the body to transform
675 * @param entryValues the output entry values to map, in order, from a prefix of the input body's entry block
676 * parameters
677 * @param ct the code transformer
678 * @throws IllegalArgumentException if there are more output entry values than entry block parameters
679 * @see #transformBody(Body, List, CodeContext, CodeTransformer)
680 */
681 public void transformBody(Body body, List<? extends Value> entryValues,
682 CodeTransformer ct) {
683 check();
684
685 transformBody(body, entryValues, CodeContext.create(cc), ct);
686 }
687
688 /**
689 * Transforms the given body into this block builder's parent body, using this block builder as the current
690 * output block builder, the given code context, and the given code transformer.
691 * <p>
692 * This method first obtains a block builder with the given code context and code transformer by calling
693 * {@link #withContextAndTransformer(CodeContext, CodeTransformer)}, and then transforms the body using the code
694 * transformer by {@link CodeTransformer#acceptBody(Builder, Body, List) accepting} the obtained block builder,
695 * the body, and the entry values.
696 * <p>
697 * A prefix of the input body's entry block parameters is mapped, in order, to the given output entry values.
698 * Any remaining entry block parameters are not mapped.
699 *
700 * @apiNote
701 * Supplying an explicit code context can ensure block and value mappings produced by the transformation do not
702 * affect this builder's code context. The explicit code context can also be used when some of the input body's
703 * entry block parameters have already been mapped prior to transforming the body. This is useful when the
704 * transformation removes some entry block parameters. In such cases an empty list of output entry values can be
705 * given.
706 *
707 * @param body the body to transform
708 * @param entryValues the output entry values to map, in order, from a prefix of the input body's entry block
709 * parameters
710 * @param cc the code context
711 * @param ct the code transformer
712 * @throws IllegalArgumentException if there are more output entry values than entry block parameters
713 * @see #withContextAndTransformer(CodeContext, CodeTransformer)
714 * @see CodeTransformer#acceptBody(Builder, Body, List)
715 */
716 public void transformBody(Body body, List<? extends Value> entryValues,
717 CodeContext cc, CodeTransformer ct) {
718 check();
719
720 ct.acceptBody(withContextAndTransformer(cc, ct), body, entryValues);
721 }
722
723 /**
724 * Appends an operation to the end of this block.
725 * <p>
726 * If the operation is unplaced, it is appended directly to this block.
727 * <p>
728 * If the operation is placed, this method performs <a id="transform-on-append"><i>transform-on-append</i></a>:
729 * the operation is first {@link Op#transform(CodeContext, CodeTransformer) transformed} using this block
730 * builder's code context and code transformer. The resulting unplaced operation is then appended to this block.
731 * If the operation being appended has a result, it is implicitly
732 * {@link CodeContext#mapValue(Value, Value) mapped}, if no such mapping already exists, to the result of the
733 * appended operation in this block builder's code context.
734 * <p>
735 * The appended operation must be structurally valid for this block, requiring:
736 * <ul>
737 * <li>for each child body, the body builder for that child body is
738 * <a href="Body.Builder.html#connected-builder">connected</a> to this block builder's parent
739 * body builder, or is <a href="Body.Builder.html#isolated-builder">isolated</a>.
740 * <li>each operand is reachable from the operation;
741 * <li>each successor argument is reachable from the operation;
742 * <li>each successor target is a sibling of this block; and
743 * <li>this block does not already end with a terminating operation.
744 * </ul>
745 * <a id="reachable-value"></a>A value is reachable if this block builder's {@link #parentBody() parent} body
746 * builder is the same as or is connected, directly or indirectly through its
747 * {@link Body.Builder#connectedAncestorBody() nearest ancestor} body builder and so on, to the body builder for the
748 * value's declaring block's parent body. A value is not reachable if an isolated body builder is encountered
749 * (the isolated body builder's nearest ancestor body builder is {@code null} and therefore there is no
750 * connection, directly or indirectly).
751 * This structural reachable check ensures values are only used from the same code model being built. It is
752 * weaker than the {@link Value#isDominatedBy(Value) dominance} check required for structurally valid use of a
753 * value, that can only be performed when the parent body is built.
754 *
755 * @apiNote
756 * Copying is a special case of transform-on-append when this block builder's code transformer is, or
757 * behaves as a copying transformer, such as {@link CodeTransformer#COPYING_TRANSFORMER}.
758 *
759 * @param op the operation to append
760 * @return the result of the appended operation
761 * @throws IllegalStateException if the operation is structurally invalid
762 * @see Op#transform(CodeContext, CodeTransformer)
763 */
764 public Op.Result add(Op op) {
765 check();
766
767 // Perform transform-on-append for a placed operation
768 Op outputOp = op.isPlacedInBlock() || op.isRoot()
769 ? op.transform(cc, ct)
770 : op;
771 assert ((AbstractOp) outputOp).result == null;
772
773 Op.Result outputResult = insertOp(outputOp);
774
775 Op.Result inputResult = op.result();
776 if (inputResult != null) {
777 // Map the result of the first transformation
778 // @@@ If the same operation is transformed more than once then subsequent
779 // transformed ops will not get implicitly mapped
780 // Should this be an error? Or should last transformation win?
781 if (cc.queryValue(inputResult).isEmpty()) {
782 cc.mapValue(inputResult, outputResult);
783 }
784 }
785
786 return outputResult;
787 }
788
789 /**
790 * Returns true if this block builder is equal to the other object.
791 * <p>This block builder is equal if the other object is an instance of a block builder, and they build
792 * the same block (but maybe bound to different code contexts and code transformers).
793 *
794 * @param o the other object
795 * @return true if this block builder is equal to the other object.
796 */
797 @Override
798 public boolean equals(Object o) {
799 check();
800 if (this == o) return true;
801 return o instanceof Builder that && Block.this == that.target();
802 }
803
804 @Override
805 public int hashCode() {
806 check();
807 return Block.this.hashCode();
808 }
809 }
810
811 // Modifying methods
812
813 // Create block parameter associated with this block
814 private Parameter appendBlockParameter(CodeType type) {
815 Parameter blockParameter = new Parameter(this, type);
816 parameters.add(blockParameter);
817
818 return blockParameter;
819 }
820
821 // Create an operation, adding to the end of the list of existing operations
822 private Op.Result insertOp(Op op) {
823 Op.Result opResult = new Op.Result(this, op);
824 bindOp(opResult, op);
825
826 ops.add(op);
827 return opResult;
828 }
829
830 private void bindOp(Op.Result opr, Op op) {
831 // Structural checks
832 if (!ops.isEmpty() && ops.getLast() instanceof Op.Terminating) {
833 throw new IllegalStateException("Operation cannot be appended, the block has a terminating operation");
834 }
835
836 for (Body b : op.bodies()) {
837 if (b.connectedAncestorBody != null && b.connectedAncestorBody != this.parentBody) {
838 throw new IllegalStateException("Body of operation is connected to a different ancestor body: ");
839 }
840 }
841
842 for (Value v : op.operands()) {
843 if (!isReachable(v)) {
844 throw new IllegalStateException(
845 String.format("Operand of operation %s is not defined in tree: %s", op, v));
846 }
847 assert !v.isBuilt();
848 }
849
850 for (Reference s : op.successors()) {
851 if (s.target.parentBody != this.parentBody) {
852 throw new IllegalStateException("Target of block reference is not a sibling of this block");
853 }
854
855 for (Value v : s.arguments()) {
856 if (!isReachable(v)) {
857 throw new IllegalStateException(
858 String.format("Argument of block reference %s of terminating operation %s is not defined in tree: %s", s, op, v));
859 }
860 assert !v.isBuilt();
861 }
862 }
863
864 // State updates after structural checks
865 // @@@ The alternative is to finish the body builder on failure, rendering it inoperable,
866 // so checks and updates can be merged
867 for (Value v : op.operands()) {
868 v.uses.add(opr);
869 }
870
871 for (Reference s : op.successors()) {
872 for (Value v : s.arguments()) {
873 v.uses.add(opr);
874 }
875 }
876
877 ((AbstractOp) op).result = opr;
878 }
879
880 // Determine if the parent body of value's block is the same as or an ancestor of this block
881 private boolean isReachable(Value v) {
882 Body b = parentBody;
883 while (b != null && b != v.block.parentBody) {
884 b = b.connectedAncestorBody;
885 }
886 return b != null;
887 }
888
889 //
890
891 boolean isBuilt() {
892 return index >= 0;
893 }
894 }