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 }