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