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