1 /*
2 * Copyright (c) 2024, 2026, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26 package jdk.incubator.code;
27
28 import java.util.*;
29 import java.util.stream.Collectors;
30
31 /**
32 * A (basic) block containing an ordered sequence of operations, where the last operation is
33 * a {@link Op.Terminating terminating} operation.
34 * <p>
35 * The terminating operation, according to its specification, may branch to other blocks contained in the
36 * same parent body, by way of its {@link Op#successors() successors}, or exit the parent body and optionally
37 * yield a result.
38 * <p>
39 * Blocks declare zero or more block parameters.
40 * <p>
41 * A block is built using a {@link Block.Builder block builder} that is used to append operations to the block
42 * being built.
43 */
44 public final class Block implements CodeElement<Block, Op> {
45
46 /**
47 * A value that is a block parameter
48 */
49 public static final class Parameter extends Value {
50 Parameter(Block block, CodeType type) {
51 super(block, type);
52 }
53
54 @Override
55 public String toString() {
56 return "%param@" + Integer.toHexString(hashCode());
57 }
58
59 @Override
60 public SequencedSet<Value> dependsOn() {
61 return Collections.emptyNavigableSet();
62 }
63
64 /**
65 * Returns the invokable operation associated with this block parameter.
66 * <p>
67 * If this block parameter is declared in an entry block and that
68 * block's ancestor operation (the parent of the entry block's parent body)
69 * is an instance of {@link Op.Invokable}, then that instance is returned,
70 * otherwise {@code null} is returned.
71 * <p>
72 * A non-{@code null} result implies this parameter is an invokable parameter.
73 *
74 * @apiNote
75 * This method may be used to pattern match on the returned result:
76 * {@snippet lang = "java":
77 * if (p.invokableOperation() instanceof CoreOp.FuncOp f) {
78 * assert f.parameters().indexOf(p) == p.index(); // @link substring="parameters()" target="Op.Invokable#parameters()"
79 * }
80 *}
81 *
82 * @return the invokable operation, otherwise {@code null} if the operation
83 * is not an instance of {@link Op.Invokable}.
84 * @see Op.Invokable#parameters()
85 */
86 public Op.Invokable invokableOperation() {
87 if (declaringBlock().isEntryBlock() &&
88 declaringBlock().ancestorOp() instanceof Op.Invokable o) {
89 return o;
90 } else {
91 return null;
92 }
93 }
94
95 /**
96 * {@return the index of this block parameter in the parameters of its declaring block.}
97 * @see Value#declaringBlock()
98 * @see Block#parameters()
99 */
100 public int index() {
101 return declaringBlock().parameters().indexOf(this);
102 }
103 }
104
105 /**
106 * A block reference that refers to a block with arguments.
107 * <p>
108 * A terminating operation may refer, via a block reference, to one or more blocks as its successors.
109 * When control is passed from a block to a successor block the values of the block reference's arguments are
110 * assigned, in order, to the successor block's parameters.
111 * <p>
112 */
113 public static final class Reference implements CodeItem {
114 final Block target;
115 final List<Value> arguments;
116
117 /**
118 * Constructs a block reference for a given target block and arguments.
119 *
120 * @param target the target block.
121 * @param arguments the target block arguments, a copy will be made as needed.
122 */
123 Reference(Block target, List<? extends Value> arguments) {
124 this.target = target;
125 this.arguments = List.copyOf(arguments);
126 }
127
128 /**
129 * {@return the target block.}
130 * @throws IllegalStateException if the target block is being built and is not observable.
131 */
132 public Block targetBlock() {
133 if (!isBuilt()) {
134 throw new IllegalStateException("Target block is being built and is not observable");
135 }
136
137 return target;
138 }
139
140 /**
141 * {@return the block arguments.}
142 */
143 public List<Value> arguments() {
144 return arguments;
145 }
146
147 boolean isBuilt() {
148 return target.isBuilt();
149 }
150 }
151
152 final Body parentBody;
153
154 final List<Parameter> parameters;
155
156 final List<Op> ops;
157
158 // @@@ In topological order
159 // @@@ Create lazily
160 // Can the representation be more efficient e.g. an array?
161 final SequencedSet<Block> predecessors;
162
163 // Reverse postorder index
164 // Set when block's body has sorted its blocks and therefore set when built
165 // Block is inoperable when < 0 i.e., when not built
166 int index = -1;
167
168 Block(Body parentBody) {
169 this(parentBody, List.of());
170 }
171
172 Block(Body parentBody, List<CodeType> parameterTypes) {
173 this.parentBody = parentBody;
174 this.parameters = new ArrayList<>();
175 for (CodeType param : parameterTypes) {
176 parameters.add(new Parameter(this, param));
177 }
178 this.ops = new ArrayList<>();
179 this.predecessors = new LinkedHashSet<>();
180 }
181
182
183 @Override
184 public String toString() {
185 return "^block_" + index + "@" + Integer.toHexString(hashCode());
186 }
187
188 /**
189 * Returns this block's parent body.
190 *
191 * @return this block's parent body.
192 */
193 @Override
194 public Body parent() {
195 return parentBody;
196 }
197
198 @Override
199 public List<Op> children() {
200 return ops();
201 }
202
203 /**
204 * Returns the sequence of operations contained in this block.
205 *
206 * @return returns the sequence operations, as an unmodifiable list.
207 */
208 public List<Op> ops() {
209 return Collections.unmodifiableList(ops);
210 }
211
212 /**
213 * Returns this block's index within the parent body's blocks.
214 * <p>
215 * The following identity holds true:
216 * {@snippet lang = "java" :
217 * this.parentBody().blocks().indexOf(this) == this.index();
218 * }
219 *
220 * @apiNote
221 * The block's index may be used to efficiently track blocks using
222 * bits sets or boolean arrays.
223 *
224 * @return the block index.
225 */
226 public int index() {
227 return index;
228 }
229
230 /**
231 * Returns the block parameters.
232 *
233 * @return the block parameters, as an unmodifiable list.
234 */
235 public List<Parameter> parameters() {
236 return Collections.unmodifiableList(parameters);
237 }
238
239 /**
240 * Returns the block parameter types.
241 *
242 * @return the block parameter types, as am unmodifiable list.
243 */
244 public List<CodeType> parameterTypes() {
245 return parameters.stream().map(Value::type).toList();
246 }
247
248 /**
249 * Returns the first operation in this block.
250 *
251 * @return the first operation in this block.
252 */
253 public Op firstOp() {
254 return ops.getFirst();
255 }
256
257 /**
258 * Returns the last, terminating, operation in this block.
259 * <p>
260 * The terminating operation implements {@link Op.Terminating}.
261 *
262 * @return the last, terminating, operation in this block.
263 */
264 public Op terminatingOp() {
265 Op lop = ops.getLast();
266 assert lop instanceof Op.Terminating;
267 return lop;
268 }
269
270 /**
271 * Returns the next operation after the given operation, otherwise {@code null}
272 * if this operation is the last operation.
273 *
274 * @param op the operation
275 * @return the next operation after the given operation.
276 * @throws IllegalArgumentException if the operation is not a child of this block
277 */
278 public Op nextOp(Op op) {
279 int i = ops.indexOf(op);
280 if (i == -1) {
281 throw new IllegalArgumentException();
282 }
283 return i < ops().size() - 1 ? ops.get(i + 1) : null;
284 }
285
286 /**
287 * Returns the set of predecessors, the set containing each block in the parent
288 * body that refers to this block as a successor.
289 *
290 * @return the set of predecessors, as an unmodifiable sequenced set. The encounter order is unspecified
291 * and determined by the order in which operations are built.
292 * @apiNote A block may refer to itself as a successor and therefore also be its predecessor.
293 */
294 public SequencedSet<Block> predecessors() {
295 return Collections.unmodifiableSequencedSet(predecessors);
296 }
297
298 /**
299 * Returns the list of predecessor references to this block.
300 * <p>
301 * This method behaves is if it returns the result of the following expression:
302 * {@snippet lang = java:
303 * predecessors.stream().flatMap(p -> successors().stream())
304 * .filter(r -> r.targetBlock() == this)
305 * .toList();
306 *}
307 *
308 * @return the list of predecessor references to this block, as an unmodifiable list.
309 * @apiNote A predecessor block may reference it successor block one or more times.
310 */
311 public List<Block.Reference> predecessorReferences() {
312 return predecessors.stream().flatMap(p -> p.successors().stream())
313 .filter(r -> r.targetBlock() == this)
314 .toList();
315 }
316
317 /**
318 * Returns the list of successors referring to other blocks.
319 * <p>
320 * The successors are declared by the terminating operation contained in this block.
321 *
322 * @return the list of successors, as an unmodifiable list.
323 * @apiNote given a block, A say, whose successor targets a block, B say, we can
324 * state that B is a successor block of A and A is a predecessor block of B.
325 */
326 public List<Reference> successors() {
327 return ops.getLast().successors();
328 }
329
330 /**
331 * Returns the set of target blocks referred to by the successors of this block.
332 * <p>
333 * This method behaves is if it returns the result of the following expression:
334 * {@snippet lang = java:
335 * successors().stream()
336 * .map(Block.Reference::targetBlock)
337 * .collect(Collectors.toCollection(LinkedHashSet::new));
338 *}
339 *
340 * @return the set of target blocks, as an unmodifiable set.
341 */
342 public SequencedSet<Block> successorTargets() {
343 return successors().stream().map(Block.Reference::targetBlock)
344 .collect(Collectors.toCollection(LinkedHashSet::new));
345 }
346
347 /**
348 * Returns true if this block is an entry block, the first block occurring
349 * in the parent body's list of blocks.
350 *
351 * @return true if this block is an entry block.
352 */
353 public boolean isEntryBlock() {
354 return parentBody.entryBlock() == this;
355 }
356
357 /**
358 * Returns {@code true} if this block is dominated by the given block {@code dom}.
359 * <p>
360 * A block {@code b} is dominated by {@code dom} if every path from the entry block of {@code dom}'s
361 * parent body to {@code b} passes through {@code dom}.
362 * <p>
363 * If this block and {@code dom} have different parent bodies, this method first
364 * repeatedly replaces this block with its {@link #ancestorBlock() nearest ancestor} block until:
365 * <ul>
366 * <li>{@code null} is reached, in which case this method returns {@code false}; or</li>
367 * <li>both blocks are in the same parent body, in which case
368 * <a href="https://en.wikipedia.org/wiki/Dominator_(graph_theory)">dominance</a> is tested within that body.</li>
369 * </ul>
370 *
371 * @apiNote
372 * The method {@link Body#immediateDominators()} can be used to test for dominance, by repeatedly querying a block's
373 * immediately dominating block until {@code null} or {@code dom} is reached.
374 *
375 * @param dom the dominating block
376 * @return {@code true} if this block is dominated by the given block.
377 * @see Body#immediateDominators()
378 * @see Value#isDominatedBy
379 */
380 public boolean isDominatedBy(Block dom) {
381 Block b = findBlockForDomBody(this, dom.ancestorBody());
382 if (b == null) {
383 return false;
384 }
385
386 // A block non-strictly dominates itself
387 if (b == dom) {
388 return true;
389 }
390
391 // The entry block in b's body dominates all other blocks in the body
392 Block entry = b.ancestorBody().entryBlock();
393 if (dom == entry) {
394 return true;
395 }
396
397 // Traverse the immediate dominators until dom is reached or the entry block
398 Map<Block, Block> idoms = b.ancestorBody().immediateDominators();
399 Block idom = idoms.get(b);
400 while (idom != entry) {
401 if (idom == dom) {
402 return true;
403 }
404
405 idom = idoms.get(idom);
406 }
407
408 return false;
409 }
410
411 /**
412 * Returns the immediate dominator of this block, otherwise {@code null} if this block is the entry block.
413 * Both this block and the immediate dominator (if defined) have the same parent body.
414 * <p>
415 * The immediate dominator is the unique block that strictly dominates this block, but does not strictly dominate
416 * any other block that strictly dominates this block.
417 *
418 * @return the immediate dominator of this block, otherwise {@code null} if this block is the entry block.
419 */
420 public Block immediateDominator() {
421 if (this == ancestorBody().entryBlock()) {
422 return null;
423 }
424
425 Map<Block, Block> idoms = ancestorBody().immediateDominators();
426 return idoms.get(this);
427 }
428
429 /**
430 * Returns the immediate post dominator of this block.
431 * <p>
432 * If this block has no successors then this method returns the synthetic block
433 * {@link Body#IPDOM_EXIT} representing the synthetic exit used to compute
434 * the immediate post dominators.
435 * <p>
436 * Both this block and the immediate post dominator (if defined) have the same parent body,
437 * except for the synthetic block {@link Body#IPDOM_EXIT}.
438 * <p>
439 * The immediate post dominator is the unique block that strictly post dominates this block,
440 * but does not strictly post dominate any other block that strictly post dominates this block.
441 *
442 * @return the immediate post dominator of this block, otherwise {@code Body#IPDOM_EXIT}.
443 */
444 public Block immediatePostDominator() {
445 Map<Block, Block> ipdoms = ancestorBody().immediatePostDominators();
446 Block ipdom = ipdoms.get(this);
447 return ipdom == this ? Body.IPDOM_EXIT : ipdom;
448 }
449
450 // @@@ isPostDominatedBy and immediatePostDominator
451
452 private static Block findBlockForDomBody(Block b, final Body domr) {
453 Body rb = b.ancestorBody();
454 while (domr != rb) {
455 // @@@ What if body is isolated
456
457 b = rb.ancestorBlock();
458 // null when op is top-level (and its body is isolated), or not yet assigned to block
459 if (b == null) {
460 return null;
461 }
462 rb = b.ancestorBody();
463 }
464 return b;
465 }
466
467 /**
468 * A builder of a block.
469 * <p>
470 * A block builder is built when its {@link #parent() parent} body builder is {@link Body.Builder#build(Op) built}.
471 * <p>
472 * A block is not observable while it is being built. Attempts to access a block being built through the block's
473 * parameters, appended operations, their operation results, or created block references, result in an exception.
474 * <p>
475 * If a built builder is operated on to append a block parameter, append an operation, build a sibling block,
476 * then an {@code IllegalStateException} is thrown.
477 */
478 public final class Builder {
479 final Body.Builder parentBody;
480 final CodeContext cc;
481 final CodeTransformer ot;
482
483 Builder(Body.Builder parentBody, CodeContext cc, CodeTransformer ot) {
484 this.parentBody = parentBody;
485 this.cc = cc;
486 this.ot = ot;
487 }
488
489 void check() {
490 parentBody.check();
491 }
492
493 Block target() {
494 return Block.this;
495 }
496
497 /**
498 * {@return the block builder's operation transformer}
499 */
500 public CodeTransformer transformer() {
501 return ot;
502 }
503
504 /**
505 * {@return the block builder's context}
506 */
507 public CodeContext context() {
508 return cc;
509 }
510
511 /**
512 * {@return the parent body builder}
513 */
514 public Body.Builder parentBody() {
515 return parentBody;
516 }
517
518 /**
519 * Returns the entry block builder for parent body.
520 *
521 * <p>The returned block is rebound if necessary to this block builder's
522 * context and transformer.
523 *
524 * @return the entry block builder for parent body builder
525 */
526 public Block.Builder entryBlock() {
527 return parentBody.entryBlock.rebind(cc, ot);
528 }
529
530 /**
531 * {@return true if this block builder is a builder of the entry block}
532 */
533 public boolean isEntryBlock() {
534 return Block.this == parentBody.target().entryBlock();
535 }
536
537 /**
538 * Rebinds this block builder with the given context and operation transformer.
539 *
540 * <p>Either this block builder and the returned block builder may be operated on to build
541 * the same block.
542 * Both are equal to each other, and both are closed when the parent body builder is closed.
543 *
544 * @param cc the context
545 * @param ot the operation transformer
546 * @return the rebound block builder
547 */
548 public Block.Builder rebind(CodeContext cc, CodeTransformer ot) {
549 return this.cc == cc && this.ot == ot
550 ? this
551 : this.target().new Builder(parentBody(), cc, ot);
552 }
553
554 /**
555 * Creates a new sibling block in the same parent body as this block.
556 *
557 * @param params the block's parameter types
558 * @return the new block builder
559 */
560 public Block.Builder block(CodeType... params) {
561 return block(List.of(params));
562 }
563
564 /**
565 * Creates a new sibling block in the same parent body as this block.
566 *
567 * @param params the block's parameter types
568 * @return the new block builder
569 */
570 public Block.Builder block(List<CodeType> params) {
571 return parentBody.block(params, cc, ot);
572 }
573
574 /**
575 * Returns an unmodifiable list of the block's parameters.
576 *
577 * @return the unmodifiable list of the block's parameters
578 */
579 public List<Parameter> parameters() {
580 return Collections.unmodifiableList(parameters);
581 }
582
583 /**
584 * Appends a block parameter to the block's parameters.
585 *
586 * @param p the parameter type
587 * @return the appended block parameter
588 */
589 public Parameter parameter(CodeType p) {
590 check();
591 return appendBlockParameter(p);
592 }
593
594 /**
595 * Creates a block reference to this block that can be used as a successor of a terminating operation.
596 * <p>
597 * A reference can only be constructed with block arguments whose declaring block is being built, otherwise
598 * construction fails with an exception.
599 *
600 * @param args the block arguments
601 * @return the reference to this block
602 * @throws IllegalStateException if this block builder is associated with the entry block.
603 * @throws IllegalArgumentException if a block argument's declaring block is built.
604 */
605 public Reference reference(Value... args) {
606 return reference(List.of(args));
607 }
608
609 /**
610 * Creates a block reference to this block that can be used as a successor of a terminating operation.
611 * <p>
612 * A reference can only be constructed with block arguments whose declaring block is being built, otherwise
613 * construction fails with an exception.
614 *
615 * @param args the block arguments
616 * @return the reference to this block
617 * @throws IllegalStateException if this block builder is associated with the entry block.
618 * @throws IllegalArgumentException if a block argument's declaring block is built.
619 */
620 public Reference reference(List<? extends Value> args) {
621 if (isEntryBlock()) {
622 throw new IllegalStateException("Entry block cannot be referenced and used as a successor");
623 }
624 for (Value operand : args) {
625 if (operand.isBuilt()) {
626 throw new IllegalArgumentException("Argument's declaring block is built: " + operand);
627 }
628 }
629
630 return new Reference(Block.this, List.copyOf(args));
631 }
632
633 /**
634 * Transforms a body starting from this block builder, using a code transformer.
635 * <p>
636 * This method first rebinds this builder with a child context created from
637 * this builder's context and the given operation transformer, and then
638 * transforms the body using the code transformer by
639 * {@link CodeTransformer#acceptBody(Builder, Body, List) accepting}
640 * the rebound builder, the body, and the values.
641 *
642 * @apiNote
643 * Creation of a child context ensures block and value mappings produced by
644 * the transformation do not affect this builder's context.
645 *
646 * @param body the body to transform
647 * @param values the output values to map to the input parameters of the body's entry block
648 * @param ot the operation transformer
649 * @see CodeTransformer#acceptBody(Builder, Body, List)
650 */
651 public void body(Body body, List<? extends Value> values,
652 CodeTransformer ot) {
653 check();
654
655 ot.acceptBody(rebind(CodeContext.create(cc), ot), body, values);
656 }
657
658 /**
659 * Transforms a body starting from this block builder, using a given operation transformer.
660 * <p>
661 * This method first rebinds this builder with the given context
662 * and the given operation transformer, and then
663 * transforms the body using the operation transformer by
664 * {@link CodeTransformer#acceptBody(Builder, Body, List) accepting}
665 * the rebound builder, the body, and the values.
666 *
667 * @apiNote
668 * The passing of a context can ensure block and value mappings produced by
669 * the transformation do not affect this builder's context.
670 *
671 * @param body the body to transform
672 * @param values the output values to map to the input parameters of the body's entry block
673 * @param cc the code context
674 * @param ot the operation transformer
675 * @see CodeTransformer#acceptBody(Builder, Body, List)
676 */
677 public void body(Body body, List<? extends Value> values,
678 CodeContext cc, CodeTransformer ot) {
679 check();
680
681 ot.acceptBody(rebind(cc, ot), body, values);
682 }
683
684 /**
685 * Appends an operation to this block builder, first transforming the operation if it is attached to a block,
686 * or a root operation.
687 * <p>
688 * If the operation is unattached, then the operation is appended and attached to this block, and the operation
689 * is assigned an operation result.
690 * Otherwise, the operation (an attached or root operation) is first
691 * {@link Op#transform(CodeContext, CodeTransformer) transformed} with this builder's context and
692 * code transformer, the resulting transformed and unattached operation is attached and appended, and the
693 * operation's result mapped to the transformed operation's result, using the builder's context.
694 * <p>
695 * If the operation (transformed, or otherwise) is structurally invalid then an
696 * {@code IllegalStateException} is thrown. An operation is structurally invalid if:
697 * <ul>
698 * <li>any of its bodies does not have the same ancestor body as this block's parent body.
699 * <li>any of its operands (values) is not reachable from this block.
700 * <li>any of its successors is not a sibling of this block.
701 * <li>any of its successors arguments (values) is not reachable from this block.
702 * <li>it's a terminating operation and a terminating operation is already appended.
703 * </ul>
704 * A value is reachable from this block if there is a path from this block's parent body,
705 * via its ancestor bodies, to the value's declaring block's parent body. (Note this structural check
706 * ensures values are only used from the same code model tree being built, but it is weaker than a
707 * dominance check that can only be performed when the parent body is built.)
708 *
709 * @param op the operation to append
710 * @return the operation result of the appended operation
711 * @throws IllegalStateException if the operation is structurally invalid
712 */
713 public Op.Result op(Op op) {
714 check();
715
716 final Op.Result oprToTransform = op.result();
717
718 Op transformedOp = op;
719 if (op.isRoot() || oprToTransform != null) {
720 // If operation is assigned to block, or it's sealed, then copy it and transform its contents
721 transformedOp = op.transform(cc, ot);
722 assert transformedOp.result == null;
723 }
724
725 Op.Result transformedOpr = insertOp(transformedOp);
726
727 if (oprToTransform != null) {
728 // Map the result of the first transformation
729 // @@@ If the same operation is transformed more than once then subsequent
730 // transformed ops will not get implicitly mapped
731 // Should this be an error?
732 cc.mapValueIfAbsent(oprToTransform, transformedOpr);
733 }
734
735 return transformedOpr;
736 }
737
738 /**
739 * Returns true if this block builder is equal to the other object.
740 * <p>This block builder is equal if the other object is an instance of a block builder, and they are
741 * associated with the same block (but perhaps bound to different contexts and transformers).
742 *
743 * @param o the other object
744 * @return true if this builder is equal to the other object.
745 */
746 @Override
747 public boolean equals(Object o) {
748 if (this == o) return true;
749 return o instanceof Builder that && Block.this == that.target();
750 }
751
752 @Override
753 public int hashCode() {
754 return Block.this.hashCode();
755 }
756 }
757
758 // Modifying methods
759
760 // Create block parameter associated with this block
761 private Parameter appendBlockParameter(CodeType type) {
762 Parameter blockParameter = new Parameter(this, type);
763 parameters.add(blockParameter);
764
765 return blockParameter;
766 }
767
768 // Create an operation, adding to the end of the list of existing operations
769 private Op.Result insertOp(Op op) {
770 Op.Result opResult = new Op.Result(this, op);
771 bindOp(opResult, op);
772
773 ops.add(op);
774 return opResult;
775 }
776
777 private void bindOp(Op.Result opr, Op op) {
778 // Structural checks
779 if (!ops.isEmpty() && ops.getLast() instanceof Op.Terminating) {
780 throw new IllegalStateException("Operation cannot be appended, the block has a terminal operation");
781 }
782
783 for (Body b : op.bodies()) {
784 if (b.ancestorBody != null && b.ancestorBody != this.parentBody) {
785 throw new IllegalStateException("Body of operation is connected to a different ancestor body: ");
786 }
787 }
788
789 for (Value v : op.operands()) {
790 if (!isReachable(v)) {
791 throw new IllegalStateException(
792 String.format("Operand of operation %s is not defined in tree: %s", op, v));
793 }
794 assert !v.isBuilt();
795 }
796
797 for (Reference s : op.successors()) {
798 if (s.target.parentBody != this.parentBody) {
799 throw new IllegalStateException("Target of block reference is not a sibling of this block");
800 }
801
802 for (Value v : s.arguments()) {
803 if (!isReachable(v)) {
804 throw new IllegalStateException(
805 String.format("Argument of block reference %s of terminating operation %s is not defined in tree: %s", s, op, v));
806 }
807 assert !v.isBuilt();
808 }
809 }
810
811 // State updates after structural checks
812 // @@@ The alternative is to close the body builder on failure, rendering it inoperable,
813 // so checks and updates can be merged
814 for (Value v : op.operands()) {
815 v.uses.add(opr);
816 }
817
818 for (Reference s : op.successors()) {
819 for (Value v : s.arguments()) {
820 v.uses.add(opr);
821 }
822
823 s.target.predecessors.add(Block.this);
824 }
825
826 op.result = opr;
827 }
828
829 // Determine if the parent body of value's block is an ancestor of this block
830 private boolean isReachable(Value v) {
831 Body b = parentBody;
832 while (b != null && b != v.block.parentBody) {
833 b = b.ancestorBody;
834 }
835 return b != null;
836 }
837
838 //
839
840 boolean isBuilt() {
841 return index >= 0;
842 }
843 }