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