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