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 }