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 * <p>
480 * A block builder has a code {@link #context() context} and code {@link #transformer() transformer}. These are used
481 * to perform <i>transform-on-append</i> when {@link #add appending} a placed operation. Any sibling block builder
482 * {@link #block(List) created} from a block builder will have the same code context and code transformer.
483 * <p>
484 * A block builder may be obtained with a different code context and code transformer by calling
485 * {@link #withContextAndTransformer(CodeContext, CodeTransformer)}. Such a block builder builds the same block, and
486 * can be used to apply alternative transformations to placed operations that are appended.
487 * <p>
488 * During {@link CodeTransformer code transformation}, a block builder may also serve as the current output block
489 * builder.
490 * <p>
491 * Block builders are not thread-safe.
492 */
493 public final class Builder {
494 final Body.Builder parentBody;
495 final CodeContext cc;
496 final CodeTransformer ct;
497
498 Builder(Body.Builder parentBody, CodeContext cc, CodeTransformer ct) {
499 this.parentBody = parentBody;
500 this.cc = cc;
501 this.ct = ct;
502 }
503
504 void check() {
505 parentBody.check();
506 }
507
508 Block target() {
509 return Block.this;
510 }
511
512 /**
513 * {@return this block builder's code transformer}
514 */
515 public CodeTransformer transformer() {
516 return ct;
517 }
518
519 /**
520 * {@return this block builder's code context}
521 */
522 public CodeContext context() {
523 return cc;
524 }
525
526 /**
527 * {@return this block builder's parent body builder}
528 */
529 public Body.Builder parentBody() {
530 return parentBody;
531 }
532
533 /**
534 * Returns the entry block builder of this builder's parent body builder.
535 * <p>
536 * The returned block builder has this block builder's code context and code transformer.
537 *
538 * @return the entry block builder of this builder's parent body builder
539 */
540 public Block.Builder entryBlock() {
541 return parentBody.entryBlock.withContextAndTransformer(cc, ct);
542 }
543
544 /**
545 * {@return true if this block builder builds the entry block of its parent body}
546 */
547 public boolean isEntryBlock() {
548 return Block.this == parentBody.target().entryBlock();
549 }
550
551 /**
552 * Returns a block builder for the same block with the given code context and code transformer.
553 * <p>
554 * Both this block builder and the returned block builder may be operated on to build the same block. Both are
555 * equal to each other, and both become inoperable when the parent body builder
556 * <a href="Body.Builder.html#body-building-finishing">finishes</a>.
557 *
558 * @param cc the code context
559 * @param ct the code transformer
560 * @return the block builder with the given code context and code transformer
561 */
562 public Block.Builder withContextAndTransformer(CodeContext cc, CodeTransformer ct) {
563 return this.cc == cc && this.ct == ct
564 ? this
565 : this.target().new Builder(parentBody(), cc, ct);
566 }
567
568 /**
569 * Creates a builder for a new sibling block in this builder's parent body.
570 * <p>
571 * The returned builder has the same code context and code transformer as this
572 * block builder.
573 *
574 * @param params the parameter types of the new block
575 * @return the new block builder
576 */
577 public Block.Builder block(CodeType... params) {
578 return block(List.of(params));
579 }
580
581 /**
582 * Creates a builder for a new sibling block in this builder's parent body.
583 * <p>
584 * The returned builder has the same code context and code transformer as this
585 * block builder.
586 *
587 * @param params the parameter types of the new block
588 * @return the new block builder
589 */
590 public Block.Builder block(List<CodeType> params) {
591 return parentBody.block(params, cc, ct);
592 }
593
594 /**
595 * Returns an unmodifiable list of this block's parameters.
596 *
597 * @return the unmodifiable list of this block's parameters
598 */
599 public List<Parameter> parameters() {
600 return Collections.unmodifiableList(parameters);
601 }
602
603 /**
604 * Appends a parameter of the given type to this block.
605 *
606 * @param p the parameter type
607 * @return the appended block parameter
608 */
609 public Parameter parameter(CodeType p) {
610 check();
611 return appendBlockParameter(p);
612 }
613
614 /**
615 * Creates a reference to this block that can be used as a successor of a terminating operation.
616 * <p>
617 * A reference can only be created with arguments whose declaring block is being built.
618 *
619 * @param args the block arguments
620 * @return a reference to this block
621 * @throws IllegalStateException if this block builder builds the entry block.
622 * @throws IllegalArgumentException if any argument's declaring block is built.
623 */
624 public Reference reference(Value... args) {
625 return reference(List.of(args));
626 }
627
628 /**
629 * Creates a reference to this block that can be used as a successor of a terminating operation.
630 * <p>
631 * A reference can only be created with arguments whose declaring block is being built.
632 *
633 * @param args the block arguments
634 * @return a reference to this block
635 * @throws IllegalStateException if this block builder builds the entry block.
636 * @throws IllegalArgumentException if any argument's declaring block is built.
637 */
638 public Reference reference(List<? extends Value> args) {
639 if (isEntryBlock()) {
640 throw new IllegalStateException("Entry block cannot be referenced and targeted as a successor");
641 }
642 for (Value operand : args) {
643 if (operand.isBuilt()) {
644 throw new IllegalArgumentException("Argument's declaring block is built: " + operand);
645 }
646 }
647
648 return new Reference(Block.this, List.copyOf(args));
649 }
650
651 /**
652 * Transforms the given body into this block builder's parent body, using this block builder as the current
653 * output block builder, a {@link CodeContext#create(CodeContext) child} of this block builder's code context,
654 * and the given code transformer.
655 * <p>
656 * This method behaves as if invoking {@link #transformBody(Body, List, CodeContext, CodeTransformer)} with the given
657 * body, the given entry values, a child of this block builder's code context, and the given code transformer.
658 *
659 * @param body the body to transform
660 * @param entryValues the output entry values to map, in order, from a prefix of the input body's entry block
661 * parameters
662 * @param ct the code transformer
663 * @throws IllegalArgumentException if there are more output entry values than entry block parameters
664 * @see #transformBody(Body, List, CodeContext, CodeTransformer)
665 */
666 public void transformBody(Body body, List<? extends Value> entryValues,
667 CodeTransformer ct) {
668 check();
669
670 transformBody(body, entryValues, CodeContext.create(cc), ct);
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, the given code context, and the given code transformer.
676 * <p>
677 * This method first obtains a block builder with the given code context and code transformer by calling
678 * {@link #withContextAndTransformer(CodeContext, CodeTransformer)}, and then transforms the body using the code
679 * transformer by {@link CodeTransformer#acceptBody(Builder, Body, List) accepting} the obtained block builder,
680 * the body, and the entry values.
681 * <p>
682 * A prefix of the input body's entry block parameters is mapped, in order, to the given output entry values.
683 * Any remaining entry block parameters are not mapped.
684 *
685 * @apiNote
686 * Supplying an explicit code context can ensure block and value mappings produced by the transformation do not
687 * affect this builder's code context. The explicit code context can also be used when some of the input body's
688 * entry block parameters have already been mapped prior to transforming the body. This is useful when the
689 * transformation removes some entry block parameters. In such cases an empty list of output entry values can be
690 * given.
691 *
692 * @param body the body to transform
693 * @param entryValues the output entry values to map, in order, from a prefix of the input body's entry block
694 * parameters
695 * @param cc the code context
696 * @param ct the code transformer
697 * @throws IllegalArgumentException if there are more output entry values than entry block parameters
698 * @see #withContextAndTransformer(CodeContext, CodeTransformer)
699 * @see CodeTransformer#acceptBody(Builder, Body, List)
700 */
701 public void transformBody(Body body, List<? extends Value> entryValues,
702 CodeContext cc, CodeTransformer ct) {
703 check();
704
705 ct.acceptBody(withContextAndTransformer(cc, ct), body, entryValues);
706 }
707
708 /**
709 * Appends an operation to the end of this block.
710 * <p>
711 * If the operation is unplaced, it is appended directly to this block.
712 * <p>
713 * If the operation is placed, this method performs <a id="transform-on-append"><i>transform-on-append</i></a>:
714 * the operation is first {@link Op#transform(CodeContext, CodeTransformer) transformed} using this block
715 * builder's code context and code transformer. The resulting unplaced operation is then 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 add(Op op) {
750 check();
751
752 // Perform transform-on-append for a placed operation
753 Op outputOp = op.isPlacedInBlock() || 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
860 op.result = opr;
861 }
862
863 // Determine if the parent body of value's block is the same as or an ancestor of this block
864 private boolean isReachable(Value v) {
865 Body b = parentBody;
866 while (b != null && b != v.block.parentBody) {
867 b = b.connectedAncestorBody;
868 }
869 return b != null;
870 }
871
872 //
873
874 boolean isBuilt() {
875 return index >= 0;
876 }
877 }