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 jdk.incubator.code.dialect.core.CoreType;
29 import jdk.incubator.code.dialect.core.FunctionType;
30 import java.util.*;
31
32 /**
33 * A body containing a sequence of (basic) blocks.
34 * <p>
35 * The sequence of blocks form a graph topologically sorted in reverse postorder.
36 * The first block in the sequence is the entry block, and no other blocks refer to it as a successor.
37 * The last operation in a block, a terminating operation, may refer to other blocks in the sequence as successors,
38 * thus forming the graph. Otherwise, the last operation defines how the body passes control back to the parent
39 * operation, and in doing so may optionally yield a value.
40 * <p>
41 * A body has a signature, a function type, whose return type is the body's yield type and whose parameter types are the
42 * entry block's parameters types, in order.
43 * The signature describes the sequence of input parameters types for arguments that are passed to the
44 * body when control is passed to it, and describes the return type of values that are yielded when the body passes
45 * control back to its parent operation.
46 * <p>
47 * A body is either open or isolated. An open body may {@link #capturedValues() capture} values, depending on how the
48 * body's descendant operations use values. An {@link #isIsolated() isolated} body is guaranteed to never capture
49 * values.
50 * <p>
51 * A body is built using a {@link Body.Builder}, which specifies the
52 * <a href="Body.Builder.html#body-building-process">building process</a>. An open body is built by a
53 * <a href="Body.Builder.html#connected-builder">connected</a> body builder. An isolated body is built by an
54 * <a href="Body.Builder.html#isolated-builder">isolated</a> body builder.
55 */
56 public final class Body implements CodeElement<Body, Block> {
57 // @Stable?
58 // Parent operation
59 // Non-null when body is built, and therefore child of an operation
60 Op parentOp;
61
62 // The connected ancestor body
63 // When non-null the body is open and when built/observable, connectedAncestorBody == this.ancestorBody()
64 // When null the body is isolated, and cannot refer to values defined outside
65 final Body connectedAncestorBody;
66
67 final CodeType yieldType;
68
69 // Sorted in reverse postorder
70 final List<Block> blocks;
71
72 // Lazily computed map of a block to its immediate dominator
73 // Computed after body is built
74 // @@@ when dominance checks are implemented, may be computed and used in build method
75 LazyConstant<Map<Block, Block>> idoms = LazyConstant.of(this::computeImmediateDominators);
76
77 /**
78 * Constructs a body, whose connected ancestor body is the given ancestor body.
79 */
80 Body(Body connectedAncestorBody, CodeType yieldType) {
81 this.connectedAncestorBody = connectedAncestorBody;
82 this.yieldType = yieldType;
83 this.blocks = new ArrayList<>();
84 }
85
86 @Override
87 public String toString() {
88 return "body@" + Integer.toHexString(hashCode());
89 }
90
91 /**
92 * {@return the body's parent operation.}
93 */
94 @Override
95 public Op parent() {
96 return parentOp;
97 }
98
99 @Override
100 public List<Block> children() {
101 return blocks();
102 }
103
104 /**
105 * Returns body's blocks in reverse-postorder as an unmodifiable list.
106 *
107 * @return the body's blocks in reverse-postorder.
108 */
109 public List<Block> blocks() {
110 return Collections.unmodifiableList(blocks);
111 }
112
113 /**
114 * {@return the yield type of this body}
115 */
116 public CodeType yieldType() {
117 return yieldType;
118 }
119
120 /**
121 * Returns the body's signature, represented as a function type.
122 * <p>
123 * The signature's return type is the body's yield type and its parameter types are the
124 * body's entry block parameter types, in order.
125 *
126 * @return the body's signature.
127 */
128 public FunctionType bodySignature() {
129 Block entryBlock = entryBlock();
130 return CoreType.functionType(yieldType, entryBlock.parameterTypes());
131 }
132
133 /**
134 * Returns this body's entry block.
135 * <p>
136 * The entry block is the first block in the sequence. No other blocks refer to it as a successor.
137 *
138 * @return the body's entry block
139 */
140 public Block entryBlock() {
141 return blocks.getFirst();
142 }
143
144 /**
145 * Returns a map of block to its immediate dominator.
146 *
147 * @return a map of block to its immediate dominator, as an unmodifiable map
148 */
149 public Map<Block, Block> immediateDominators() {
150 return idoms.get();
151 }
152
153 // Called by LazyConstant field
154 private Map<Block, Block> computeImmediateDominators() {
155 /*
156 * Compute dominators of blocks in a body.
157 * <p>
158 * https://www.cs.rice.edu/~keith/EMBED/dom.pdf
159 * A Simple, Fast Dominance Algorithm
160 * Keith D. Cooper, Timothy J. Harvey, and Ken Kennedy
161 */
162
163 // @@@ Compute the idoms as a block index mapping using int[]
164 // and wrap and a specific map implementation
165
166 Map<Block, Block> doms = new HashMap<>();
167 doms.put(entryBlock(), entryBlock());
168
169 // Blocks are sorted in reverse postorder
170 boolean changed;
171 do {
172 changed = false;
173 // Iterate through blocks in reverse postorder, except for entry block
174 for (int i = 1; i < blocks.size(); i++) {
175 Block b = blocks.get(i);
176
177 // Find first processed predecessor of b
178 Block newIdom = null;
179 for (Block p : b.predecessors()) {
180 if (doms.containsKey(p)) {
181 newIdom = p;
182 break;
183 }
184 }
185 assert b.predecessors().isEmpty() || newIdom != null : b;
186
187 // For all other predecessors, p, of b
188 for (Block p : b.predecessors()) {
189 if (p == newIdom) {
190 continue;
191 }
192
193 if (doms.containsKey(p)) {
194 // If already calculated
195 newIdom = intersect(doms, p, newIdom);
196 }
197 }
198
199 if (doms.get(b) != newIdom) {
200 doms.put(b, newIdom);
201 changed = true;
202 }
203 }
204 } while (changed);
205
206 return Collections.unmodifiableMap(doms);
207 }
208
209 static Block intersect(Map<Block, Block> doms, Block b1, Block b2) {
210 while (b1 != b2) {
211 while (b1.index > b2.index) {
212 b1 = doms.get(b1);
213 }
214
215 while (b2.index > b1.index) {
216 b2 = doms.get(b2);
217 }
218 }
219
220 return b1;
221 }
222
223 /**
224 * Returns the dominance frontier of each block in the body.
225 * <p>
226 * The dominance frontier of block, {@code B} say, is the set of all blocks, {@code C} say,
227 * such that {@code B} dominates a predecessor of {@code C} but does not strictly dominate
228 * {@code C}.
229 *
230 * @return the dominance frontier of each block in the body, as a modifiable map
231 */
232 public Map<Block, Set<Block>> dominanceFrontier() {
233 // @@@ cache result?
234 Map<Block, Block> idoms = immediateDominators();
235 Map<Block, Set<Block>> df = new HashMap<>();
236
237 for (Block b : blocks) {
238 Set<Block> preds = b.predecessors();
239
240 if (preds.size() > 1) {
241 for (Block p : preds) {
242 Block runner = p;
243 while (runner != idoms.get(b)) {
244 df.computeIfAbsent(runner, _ -> new LinkedHashSet<>()).add(b);
245 runner = idoms.get(runner);
246 }
247 }
248 }
249 }
250
251 return df;
252 }
253
254 /**
255 * A synthetic exit block used when computing immediate post dominators.
256 * It represents the post dominator of all blocks when two or more blocks
257 * in the body have no successors.
258 * <p>
259 * Computing the immediate post dominators requires a single exit point,
260 * one block with no successors. When a body has two or more blocks
261 * with no successors then this block acts as the single exit point.
262 */
263 public static final Block IPDOM_EXIT;
264 static {
265 IPDOM_EXIT = new Block(null);
266 IPDOM_EXIT.index = Integer.MAX_VALUE;
267 }
268
269 /**
270 * Returns a map of block to its immediate post dominator.
271 * <p>
272 * If there are two or more blocks with no successors then
273 * a single exit point is synthesized using the {@link #IPDOM_EXIT}
274 * block, which represents the immediate post dominator of those blocks.
275 *
276 * @return a map of block to its immediate post dominator, as an unmodifiable map
277 */
278 public Map<Block, Block> immediatePostDominators() {
279 Map<Block, Block> pdoms = new HashMap<>();
280
281 // If there are multiple exit blocks (those with zero successors)
282 // then use the block IPDOM_EXIT that is the synthetic successor of
283 // the exit blocks
284 boolean nSuccessors = blocks.stream().filter(b -> b.successors().isEmpty()).count() > 1;
285
286 if (nSuccessors) {
287 pdoms.put(IPDOM_EXIT, IPDOM_EXIT);
288 } else {
289 Block exit = blocks.getLast();
290 assert blocks.stream().filter(b -> b.successors().isEmpty()).findFirst().orElseThrow() == exit;
291 pdoms.put(exit, exit);
292 }
293
294 // Blocks are sorted in reverse postorder
295 boolean changed;
296 do {
297 changed = false;
298 // Iterate in reverse through blocks in reverse postorder, except for exit block
299 for (int i = blocks.size() - (nSuccessors ? 1 : 2); i >= 0; i--) {
300 Block b = blocks.get(i);
301
302 // Find first processed successor of b
303 Block newIpdom = null;
304 Collection<Block> targets = b.successorTargets();
305 for (Block s : nSuccessors && targets.isEmpty() ? List.of(IPDOM_EXIT) : targets) {
306 if (pdoms.containsKey(s)) {
307 newIpdom = s;
308 break;
309 }
310 }
311
312 if (newIpdom == null) {
313 // newIpdom can be null if all successors reference
314 // prior blocks (back branch) yet to be encountered
315 // in the dominator treee
316 continue;
317 }
318
319 // For all other successors, s, of b
320 for (Block s : b.successorTargets()) {
321 if (s == newIpdom) {
322 continue;
323 }
324
325 if (pdoms.containsKey(s)) {
326 // If already calculated
327 newIpdom = postIntersect(pdoms, s, newIpdom, blocks.size());
328 }
329 }
330
331 if (pdoms.get(b) != newIpdom) {
332 pdoms.put(b, newIpdom);
333 changed = true;
334 }
335 }
336 } while (changed);
337
338 return Collections.unmodifiableMap(pdoms);
339 }
340
341 static Block postIntersect(Map<Block, Block> doms, Block b1, Block b2, int exitIndex) {
342 while (b1 != b2) {
343 while (b1.index() < b2.index()) {
344 b1 = doms.get(b1);
345 }
346
347 while (b2.index() < b1.index()) {
348 b2 = doms.get(b2);
349 }
350 }
351
352 return b1;
353 }
354
355 /**
356 * Returns the post dominance frontier of each block in the body.
357 * <p>
358 * The post dominance frontier of block, {@code B} say, is the set of all blocks, {@code C} say,
359 * such that {@code B} post dominates a successor of {@code C} but does not strictly post dominate
360 * {@code C}.
361 *
362 * @return the post dominance frontier of each block in the body, as a modifiable map
363 */
364 public Map<Block, Set<Block>> postDominanceFrontier() {
365 // @@@ cache result?
366 Map<Block, Block> idoms = immediatePostDominators();
367 Map<Block, Set<Block>> df = new HashMap<>();
368
369 for (Block b : blocks) {
370 Set<Block> succs = b.successorTargets();
371
372 if (succs.size() > 1) {
373 for (Block s : succs) {
374 Block runner = s;
375 while (runner != idoms.get(b)) {
376 df.computeIfAbsent(runner, _ -> new LinkedHashSet<>()).add(b);
377 runner = idoms.get(runner);
378 }
379 }
380 }
381 }
382
383 return df;
384 }
385
386 /**
387 * {@return true if this body is isolated}
388 * <p>
389 * An isolated body, built by an <a href="Body.Builder.html#isolated-builder">isolated</a> body builder, is
390 * guaranteed to never {@link #capturedValues() capture} values. Conversely, an open body, built by a
391 * <a href="Body.Builder.html#connected-builder">connected</a> body builder, may or may not capture values,
392 * depending on how the body's descendant operations use values.
393 *
394 * @see #capturedValues()
395 */
396 public boolean isIsolated() {
397 return connectedAncestorBody == null;
398 }
399
400 /**
401 * Computes values captured by this body. A captured value is a value that is used
402 * but not declared by any descendant block or operation of this body.
403 * <p>
404 * The order of the captured values is first use encountered in depth
405 * first search of this body's descendant operations.
406 *
407 * @return the list of captured values, modifiable
408 */
409 public List<Value> capturedValues() {
410 Set<Value> cvs = new LinkedHashSet<>();
411
412 capturedValues(cvs, new ArrayDeque<>(), this);
413 return new ArrayList<>(cvs);
414 }
415
416 static void capturedValues(Set<Value> capturedValues, Deque<Body> bodyStack, Body body) {
417 bodyStack.push(body);
418
419 for (Block b : body.blocks()) {
420 for (Op op : b.ops()) {
421 for (Body childBody : op.bodies()) {
422 capturedValues(capturedValues, bodyStack, childBody);
423 }
424
425 for (Value a : op.operands()) {
426 if (!bodyStack.contains(a.declaringBlock().ancestorBody())) {
427 capturedValues.add(a);
428 }
429 }
430
431 for (Block.Reference s : op.successors()) {
432 for (Value a : s.arguments()) {
433 if (!bodyStack.contains(a.declaringBlock().ancestorBody())) {
434 capturedValues.add(a);
435 }
436 }
437 }
438 }
439 }
440
441 bodyStack.pop();
442 }
443
444 /**
445 * A builder for a body.
446 * <p>
447 * <a id="body-building-process"></a>
448 * The process of building a body starts with the {@link Builder#of(Builder, FunctionType, CodeContext, CodeTransformer) creation}
449 * of a body builder, which {@link Builder#entryBlock exposes} a {@link Block.Builder block builder} for the body's
450 * entry block.
451 * <p>
452 * Building then progresses with the building of the body's structure, where:
453 * <ul>
454 * <li>
455 * the entry block builder is used to {@link Block.Builder#block(List) create} block builders for sibling blocks,
456 * and likewise those block builders can also be used to create block builders for additional sibling blocks and so
457 * on;
458 * <li>
459 * a block builder is used to {@link Block.Builder#op(Op) append} operations to the block,
460 * {@link Block.Builder#parameter(CodeType) append} parameters to the block's parameters, and
461 * {@link Block.Builder#reference(List) create} references to the block, which can be used as successors of a
462 * terminating operation that is the last operation that is appended to the block or a sibling block; and
463 * <li>
464 * <a id="body-building-observability"></a>
465 * the body and its child blocks are not observable; attempts to observe them through appended operations, their
466 * operation results, block parameters, or block references, throw an {@link IllegalStateException}.
467 * </ul>
468 * <p>
469 * Building finishes by invoking {@link #build(Op)}, with a given operation that becomes the body's
470 * parent.
471 * <p>
472 * <a id="body-building-finishing"></a>
473 * After building finishes, the body and its child blocks become observable, and the body builder and its block
474 * builders all become inoperable, regardless of whether building succeeds or fails with an exception.
475 * Further attempts to operate on the builders throw an exception.
476 * <p>
477 * A body builder may be connected to its {@link #connectedAncestorBody() nearest ancestor} body builder. This
478 * connection constrains the order in which the connected builders can finish building, ancestors cannot finish
479 * before their descendants, and determines the <a href="Block.Builder.html#reachable-value">reachability</a> of
480 * values used by appended operations.
481 * <p>
482 * Body builders are not thread-safe. Block builders associated with a body builder are also not thread-safe.
483 */
484 public final class Builder {
485 /**
486 * Creates a body builder, with an entry block {@link #entryBlock builder} that has a
487 * {@link CodeContext#create() new} code context and a {@link CodeTransformer#COPYING_TRANSFORMER copying}
488 * code transformer.
489 *
490 * @param connectedAncestorBody the nearest ancestor body builder if the created body builder is connected, or
491 * {@code null} if the created body builder is isolated
492 * @param bodySignature the initial body signature
493 * @return the body builder
494 * @throws IllegalStateException if the ancestor body builder is finished
495 * @see #of(Builder, FunctionType, CodeContext, CodeTransformer)
496 */
497 public static Builder of(Builder connectedAncestorBody, FunctionType bodySignature) {
498 // @@@ Creation of CodeContext
499 return of(connectedAncestorBody, bodySignature, CodeContext.create(), CodeTransformer.COPYING_TRANSFORMER);
500 }
501
502 /**
503 * Creates a body builder, with an entry block {@link #entryBlock builder} that has the given code context
504 * and a {@link CodeTransformer#COPYING_TRANSFORMER copying} code transformer.
505 *
506 * @param connectedAncestorBody the nearest ancestor body builder if the created body builder is connected, or
507 * {@code null} if the created body builder is isolated
508 * @param bodySignature the initial body signature
509 * @param cc the code context
510 * @return the body builder
511 * @throws IllegalStateException if the ancestor body builder is finished
512 * @see #of(Builder, FunctionType, CodeContext, CodeTransformer)
513 */
514 public static Builder of(Builder connectedAncestorBody, FunctionType bodySignature, CodeContext cc) {
515 return of(connectedAncestorBody, bodySignature, cc, CodeTransformer.COPYING_TRANSFORMER);
516 }
517
518 /**
519 * Creates a body builder whose entry block {@link #entryBlock builder} uses the given code context and code
520 * transformer.
521 * <p>
522 * If {@code connectedAncestorBody} is non-{@code null}, the created body builder is
523 * <a id="connected-builder"><i>connected</i></a> to {@code connectedAncestorBody} as the
524 * {@link #connectedAncestorBody() nearest ancestor} body builder, builds an <i>open</i> body, and the following
525 * apply:
526 * <ul>
527 * <li>
528 * the created body builder must finish before the nearest ancestor body builder finishes, which implies the
529 * ancestor body builder cannot finish until all body builders connected to it finish; and
530 * <li>
531 * the body built by the created body builder must have, as its nearest {@link Body#ancestorBody() ancestor body},
532 * the body built by the nearest ancestor body builder.
533 * </ul>
534 * If {@code connectedAncestorBody} is {@code null}, the created body builder is
535 * <a id="isolated-builder"><i>isolated</i></a>, it has no nearest ancestor body builder, builds an
536 * <i>isolated</i> body, and the following applies:
537 * <ul>
538 * <li>
539 * the scope of <a href="Block.Builder.html#reachable-value">reachable</a> values used by operations is
540 * reduced to that up to and including the created body builder.
541 * </ul>
542 * <p>
543 * One or more body builders can be connected to the created body builder, as their nearest ancestor body
544 * builder, whether the created body builder be connected or isolated, which implies the created body builder
545 * cannot finish until all of its connected body builders finish.
546 * <p>
547 * The initial body signature's return type defines the body's yield type, and its parameter types are used,
548 * in order, to create the initial parameters of the entry block builder.
549 *
550 * @param connectedAncestorBody the nearest ancestor body builder if the created body builder is connected, or
551 * {@code null} if the created body builder is isolated
552 * @param bodySignature the initial body signature
553 * @param cc the code context for the entry block builder
554 * @param ct the code transformer for the entry block builder
555 * @return the body builder
556 * @throws IllegalStateException if the connected ancestor body builder is finished
557 */
558 public static Builder of(Builder connectedAncestorBody, FunctionType bodySignature,
559 CodeContext cc, CodeTransformer ct) {
560 Body body = new Body(connectedAncestorBody != null ? connectedAncestorBody.target() : null,
561 bodySignature.returnType());
562 return body.new Builder(connectedAncestorBody, bodySignature, cc, ct);
563 }
564
565 // The connected nearest ancestor body, may be null
566 final Builder connectedAncestorBody;
567
568 // The entry block of this body, whose parameters are given by the body's function type
569 final Block.Builder entryBlock;
570
571 // When non-null contains one or more great-grandchildren
572 List<Builder> greatgrandchildren;
573
574 // True when finished
575 boolean finished;
576
577 Builder(Builder connectedAncestorBody, FunctionType bodySignature,
578 CodeContext cc, CodeTransformer ct) {
579 // Structural check
580 // The connected ancestor body should not be built before this body is built
581 if (connectedAncestorBody != null) {
582 connectedAncestorBody.check();
583 connectedAncestorBody.addGreatgrandchild(this);
584 }
585
586 this.connectedAncestorBody = connectedAncestorBody;
587 // Create entry block from the body's function type
588 Block eb = Body.this.createBlock(bodySignature.parameterTypes());
589 this.entryBlock = eb.new Builder(this, cc, ct);
590 }
591
592 void addGreatgrandchild(Builder greatgrandchild) {
593 var l = greatgrandchildren == null
594 ? (greatgrandchildren = new ArrayList<>()) : greatgrandchildren;
595 l.add(greatgrandchild);
596 }
597
598 /**
599 * Finishes building the body and its child blocks, associating the body with a parent operation.
600 * <p>
601 * The parent operation must report the built body as one of its child bodies.
602 * <p>
603 * After building finishes, the body builder and its block builders all become inoperable, regardless of whether
604 * building succeeds or fails with an exception. Further attempts to operate on the builders throw an exception.
605 * <p>
606 * Body builders connected to this body builder must finish building before this body builder finishes.
607 * <p>
608 * Any unreferenced empty blocks are ignored and do not become children of the body. An unreferenced block is
609 * a non-entry block with no predecessors.
610 *
611 * @apiNote
612 * This method is commonly called from the parent operation's constructor, which holds a reference to the built
613 * body so it can report it as one of its child bodies.
614 *
615 * @param op the parent operation
616 * @return the built body
617 * @throws IllegalStateException if this body builder has finished
618 * @throws IllegalStateException if any connected body builder is not finished
619 * @throws IllegalStateException if a block has no terminating operation, unless unreferenced and empty
620 */
621 // @@@ Check every operand dominates the operation result.
622 // An operation in block B that uses a value declared in block B requires no special checks, since an
623 // operation result does not exist until an operation is appended to a block, and B's parameters always
624 // occur before any of its operations.
625 // Similarly, when an operation uses a value declared in an ancestor no special checks are required due to
626 // structural checks and reachability checks when building.
627 // Therefore, a body with only one entry block requires no special checks when building.
628 // A body with two or more blocks requires dominance checks. An operation in block C that uses a value
629 // declared in block B, where C and B are siblings, requires that B dominates C.
630 // Since blocks are already sorted in reverse postorder the work to compute the immediate dominator map
631 // is incremental and can it be represented efficiently as an integer array of block indexes.
632 public Body build(Op op) {
633 Objects.requireNonNull(op);
634
635 // Structural check
636 // This body builder should not be finished
637 check();
638 finished = true;
639
640 // Structural check
641 // All great-grandchildren bodies should be built
642 if (greatgrandchildren != null) {
643 for (Builder greatgrandchild : greatgrandchildren) {
644 if (!greatgrandchild.finished) {
645 throw new IllegalStateException("Descendant body builder is not built");
646 }
647 }
648 }
649
650 Iterator<Block> i = blocks.iterator();
651 while (i.hasNext()) {
652 Block block = i.next();
653
654 // Structural check
655 // All referenced blocks should have a terminating operation as the last operation
656 if (block.ops.isEmpty()) {
657 if (block.isEntryBlock() || !block.predecessors.isEmpty()) {
658 throw noTerminatingOperation();
659 }
660
661 // Remove unreferenced empty block
662 assert !block.isEntryBlock() && block.predecessors.isEmpty();
663 i.remove();
664 } else if (!(block.ops.getLast() instanceof Op.Terminating)) {
665 throw noTerminatingOperation();
666 }
667 }
668
669 sortReversePostorder();
670
671 Body.this.parentOp = op;
672 return Body.this;
673 }
674
675 static IllegalStateException noTerminatingOperation() {
676 return new IllegalStateException("Block has no terminating operation as the last operation");
677 }
678
679 /**
680 * Returns this body builder's signature, represented as a function type.
681 * <p>
682 * The signature's return type is the body builder's yield type and parameter types are
683 * the currently built entry block's parameter types, in order.
684 *
685 * @return the body builder's signature
686 */
687 public FunctionType bodySignature() {
688 CodeType returnType = Body.this.yieldType();
689 Block eb = Body.this.entryBlock();
690 return CoreType.functionType(returnType, eb.parameterTypes());
691 }
692
693 /**
694 * {@return this body builder's connected ancestor body builder if this body builder is
695 * <a href="#connected-builder">connected</a>, otherwise {@code null} if this body builder is isolated}
696 */
697 public Builder connectedAncestorBody() {
698 return connectedAncestorBody;
699 }
700
701 /**
702 * {@return this body builder's entry block builder}
703 */
704 public Block.Builder entryBlock() {
705 return entryBlock;
706 }
707
708 @Override
709 public boolean equals(Object o) {
710 if (this == o) return true;
711 return o instanceof Builder that && Body.this == that.target();
712 }
713
714 @Override
715 public int hashCode() {
716 return Body.this.hashCode();
717 }
718
719 void check() {
720 if (finished) {
721 throw new IllegalStateException("Builder is finished");
722 }
723 }
724
725 Body target() {
726 return Body.this;
727 }
728
729 // Build new block in body
730 Block.Builder block(List<CodeType> params, CodeContext cc, CodeTransformer ct) {
731 check();
732 Block block = Body.this.createBlock(params);
733
734 return block.new Builder(this, cc, ct);
735 }
736 }
737
738 /**
739 * Transforms this body, returning an output body builder containing the transformed body.
740 * <p>
741 * This method creates an output body builder for this input body's {@link #bodySignature() signature}, with a
742 * {@link CodeContext#create(CodeContext) child} of the given parent code context, and the given code transformer.
743 * <p>
744 * The output body builder is <a href="Body.Builder.html#connected-builder">connected</a> to a body builder, as its
745 * nearest ancestor body builder, if that builder can be determined from this input body and the given parent code
746 * context. Otherwise, the output body builder is <a href="Body.Builder.html#isolated-builder">isolated</a>.
747 * <p>
748 * This method then transforms this input body by invoking
749 * {@link CodeTransformer#acceptBody(Block.Builder, Body, List)} with the created output body builder's
750 * {@link Body.Builder#entryBlock() entry} block builder, this input body, and that entry block builder's
751 * parameters.
752 *
753 * @apiNote
754 * To copy a body use the {@link CodeTransformer#COPYING_TRANSFORMER copying transformer}.
755 * <p>
756 * The body builder connected to the output body builder can be explicitly determined when this
757 * input body's {@link Body#ancestorBody() nearest ancestor} body is present and observable, and the given parent
758 * code context can be used to {@link CodeContext#queryBody(Body) query} the present body builder for that ancestor
759 * body. For example, in such cases:
760 * {@snippet lang = "java":
761 * Body nearestAncestorBody = this.ancestorBody(); // @link substring="ancestorBody" target="jdk.incubator.code.CodeElement#ancestorBody"
762 * Body.Builder connectedBodyBuilder = cc.queryBody(nearestAncestorBody).orElseThrow(); // @link substring="queryBody" target="jdk.incubator.code.CodeContext#queryBody"
763 * }
764 *
765 * @param cc the parent code context
766 * @param ct the code transformer
767 * @return a body builder containing the transformed body
768 */
769 public Builder transform(CodeContext cc, CodeTransformer ct) {
770 Builder connectedAncestorBodyBuilder = connectedAncestorBody != null
771 ? cc.queryBody(connectedAncestorBody).orElse(null)
772 : null;
773 Builder bodyBuilder = Builder.of(connectedAncestorBodyBuilder,
774 bodySignature(),
775 // Create child context for mapped code items contained in this body
776 // thereby not polluting the given context
777 CodeContext.create(cc), ct);
778
779 // Transform body starting from the entry block builder
780 ct.acceptBody(bodyBuilder.entryBlock, this, bodyBuilder.entryBlock.parameters());
781 return bodyBuilder;
782 }
783
784 // Sort blocks in reverse post order
785 // After sorting the following holds for a block
786 // block.parentBody().blocks().indexOf(block) == block.index()
787 private void sortReversePostorder() {
788 if (blocks.size() < 2) {
789 for (int i = 0; i < blocks.size(); i++) {
790 blocks.get(i).index = i;
791 }
792 return;
793 }
794
795 // Reset block indexes
796 // Also ensuring blocks with no predecessors occur last
797 for (Block b : blocks) {
798 b.index = Integer.MAX_VALUE;
799 }
800
801 Deque<Block> stack = new ArrayDeque<>();
802 stack.push(blocks.get(0));
803
804 // Postorder iteration
805 int index = blocks.size();
806 while (!stack.isEmpty()) {
807 Block n = stack.peek();
808 if (n.index == Integer.MIN_VALUE) {
809 // If n's successor has been processed then add n
810 stack.pop();
811 n.index = --index;
812 } else if (n.index < Integer.MAX_VALUE) {
813 // If n has already been processed then ignore
814 stack.pop();
815 } else {
816 // Mark before processing successors, a successor may refer back to n
817 n.index = Integer.MIN_VALUE;
818 for (Block.Reference s : n.successors()) {
819 if (s.target.index < Integer.MAX_VALUE) {
820 continue;
821 }
822
823 stack.push(s.target);
824 }
825 }
826 }
827
828 blocks.sort(Comparator.comparingInt(b -> b.index));
829 if (blocks.get(0).index > 0) {
830 // There are blocks with no predecessors
831 // Reassign indexes to their natural indexes, sort order is preserved
832 for (int i = 0; i < blocks.size(); i++) {
833 blocks.get(i).index = i;
834 }
835 }
836 }
837
838 // Modifying methods
839
840 // Create block
841 private Block createBlock(List<CodeType> params) {
842 Block b = new Block(this, params);
843 blocks.add(b);
844 return b;
845 }
846 }