1 /*
2 * Copyright (c) 2024, 2026, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26 package jdk.incubator.code;
27
28 import jdk.incubator.code.dialect.core.CoreType;
29 import jdk.incubator.code.dialect.core.FunctionType;
30
31 import java.util.*;
32 import java.util.stream.IntStream;
33
34 /**
35 * A body containing a sequence of blocks.
36 * <p>
37 * The sequence of blocks form a control-flow graph topologically sorted in reverse postorder.
38 * The first block in the sequence is the entry block, and no other blocks refer to it as a successor.
39 * The last operation in a block, a terminating operation, may refer to other blocks in the sequence as successors,
40 * thus forming the graph. Otherwise, the last operation defines how the body passes control back to the parent
41 * operation, and in doing so may optionally yield a value.
42 * <p>
43 * A body has a signature, a function type, whose return type is the body's yield type and whose parameter types are the
44 * entry block's parameters types, in order.
45 * The signature describes the sequence of input parameters types for arguments that are passed to the
46 * body when control is passed to it, and describes the return type of values that are yielded when the body passes
47 * control back to its parent operation.
48 * <p>
49 * A body is either open or isolated. An open body may {@link #capturedValues() capture} values, depending on how the
50 * body's descendant operations use values. An {@link #isIsolated() isolated} body is guaranteed to never capture
51 * values.
52 * <p>
53 * A body is built using a {@link Body.Builder}, which specifies the
54 * <a href="Body.Builder.html#body-building-process">building process</a>. An open body is built by a
55 * <a href="Body.Builder.html#connected-builder">connected</a> body builder. An isolated body is built by an
56 * <a href="Body.Builder.html#isolated-builder">isolated</a> body builder.
57 */
58 public final class Body implements CodeElement<Body, Block> {
59 // @Stable?
60 // Parent operation
61 // Non-null when body is built, and therefore child of an operation
62 Op parentOp;
63
64 // The connected ancestor body
65 // When non-null the body is open and when built/observable, connectedAncestorBody == this.ancestorBody()
66 // When null the body is isolated, and cannot refer to values defined outside
67 final Body connectedAncestorBody;
68
69 final CodeType yieldType;
70
71 // Sorted in reverse postorder
72 final List<Block> blocks;
73
74 // Lazily computed map of a block to its immediate dominator
75 // Computed after body is built
76 // @@@ when dominance checks are implemented, may be computed and used in build method
77 LazyConstant<Map<Block, Block>> idoms = LazyConstant.of(this::computeImmediateDominators);
78
79 /**
80 * Constructs a body, whose connected ancestor body is the given ancestor body.
81 */
82 Body(Body connectedAncestorBody, CodeType yieldType) {
83 this.connectedAncestorBody = connectedAncestorBody;
84 this.yieldType = yieldType;
85 this.blocks = new ArrayList<>();
86 }
87
88 @Override
89 public String toString() {
90 return "body@" + Integer.toHexString(hashCode());
91 }
92
93 /**
94 * {@return the body's parent operation.}
95 */
96 @Override
97 public Op parent() {
98 return parentOp;
99 }
100
101 @Override
102 public List<Block> children() {
103 return blocks();
104 }
105
106 /**
107 * Returns body's blocks in reverse-postorder as an unmodifiable list.
108 *
109 * @return the body's blocks in reverse-postorder.
110 */
111 public List<Block> blocks() {
112 return Collections.unmodifiableList(blocks);
113 }
114
115 /**
116 * {@return the yield type of this body}
117 */
118 public CodeType yieldType() {
119 return yieldType;
120 }
121
122 /**
123 * Returns the body's signature, represented as a function type.
124 * <p>
125 * The signature's return type is the body's yield type and its parameter types are the
126 * body's entry block parameter types, in order.
127 *
128 * @return the body's signature.
129 */
130 public FunctionType bodySignature() {
131 Block entryBlock = entryBlock();
132 return CoreType.functionType(yieldType, entryBlock.parameterTypes());
133 }
134
135 /**
136 * Returns this body's entry block.
137 * <p>
138 * The entry block is the first block in the sequence. No other blocks refer to it as a successor.
139 *
140 * @return the body's entry block
141 */
142 public Block entryBlock() {
143 return blocks.getFirst();
144 }
145
146 /**
147 * Returns a map of block to its immediate dominator, for all blocks in this body.
148 * <p>
149 * A block's immediate dominator is the unique block that strictly dominates that block, but does not strictly
150 * dominate any other block that strictly dominates that block.
151 * <p>
152 * The entry block has no immediate dominator, since it is not strictly dominated by any other block. Its
153 * corresponding entry in the map has a {@code null} value.
154 *
155 * @return a map of block to its immediate dominator, as an unmodifiable map
156 * @see Block#immediateDominator()
157 */
158 public Map<Block, Block> immediateDominators() {
159 return idoms.get();
160 }
161
162 // Called by LazyConstant field
163 private Map<Block, Block> computeImmediateDominators() {
164 /*
165 * Compute dominators of blocks in a body.
166 * <p>
167 * https://www.cs.rice.edu/~keith/EMBED/dom.pdf
168 * A Simple, Fast Dominance Algorithm
169 * Keith D. Cooper, Timothy J. Harvey, and Ken Kennedy
170 */
171
172 // @@@ Compute the idoms as a block index mapping using int[]
173 // and wrap and a specific map implementation
174
175 Map<Block, Block> doms = new HashMap<>();
176 doms.put(entryBlock(), null);
177
178 // Blocks are sorted in reverse postorder
179 boolean changed;
180 do {
181 changed = false;
182 // Iterate through blocks in reverse postorder, except for entry block
183 for (int i = 1; i < blocks.size(); i++) {
184 Block b = blocks.get(i);
185
186 // Find first processed predecessor of b
187 Block newIdom = null;
188 for (Block p : b.predecessors()) {
189 if (doms.containsKey(p)) {
190 newIdom = p;
191 break;
192 }
193 }
194 assert newIdom != null : b;
195
196 // For all other predecessors, p, of b
197 for (Block p : b.predecessors()) {
198 if (p == newIdom) {
199 continue;
200 }
201
202 if (doms.containsKey(p)) {
203 // If already calculated
204 newIdom = intersect(doms, p, newIdom);
205 }
206 }
207
208 if (doms.get(b) != newIdom) {
209 doms.put(b, newIdom);
210 changed = true;
211 }
212 }
213 } while (changed);
214
215 return Collections.unmodifiableMap(doms);
216 }
217
218 static Block intersect(Map<Block, Block> doms, Block b1, Block b2) {
219 while (b1 != b2) {
220 while (b1.index > b2.index) {
221 b1 = doms.get(b1);
222 }
223
224 while (b2.index > b1.index) {
225 b2 = doms.get(b2);
226 }
227 }
228
229 return b1;
230 }
231
232 /**
233 * Returns the dominance frontier of each block in the body.
234 * <p>
235 * The dominance frontier of block, {@code B} say, is the set of all blocks, {@code C} say,
236 * such that {@code B} dominates a predecessor of {@code C} but does not strictly dominate
237 * {@code C}.
238 *
239 * @return the dominance frontier of each block in the body, as a modifiable map
240 */
241 public Map<Block, Set<Block>> dominanceFrontier() {
242 // @@@ cache result?
243 Map<Block, Block> idoms = immediateDominators();
244 Map<Block, Set<Block>> df = new HashMap<>();
245
246 for (Block b : blocks) {
247 Set<Block> preds = b.predecessors();
248
249 if (preds.size() > 1) {
250 for (Block p : preds) {
251 Block runner = p;
252 while (runner != idoms.get(b)) {
253 df.computeIfAbsent(runner, _ -> new LinkedHashSet<>()).add(b);
254 runner = idoms.get(runner);
255 }
256 }
257 }
258 }
259
260 return df;
261 }
262
263 /**
264 * A synthetic exit block used when computing immediate post dominators.
265 * It represents the post dominator of all blocks when two or more blocks
266 * in the body have no successors.
267 * <p>
268 * Computing the immediate post dominators requires a single exit point,
269 * one block with no successors. When a body has two or more blocks
270 * with no successors then this block acts as the single exit point.
271 */
272 public static final Block IPDOM_EXIT;
273 static {
274 IPDOM_EXIT = new Block(null);
275 IPDOM_EXIT.index = Integer.MAX_VALUE;
276 }
277
278 /**
279 * Returns a map of block to its immediate post dominator, for all blocks in this body.
280 * <p>
281 * If there are two or more blocks with no successors then a single exit block is synthesized using the
282 * {@link #IPDOM_EXIT} block, which represents the immediate post dominator of those blocks. The returned map
283 * will contain an entry mapping {@code IPDOM_EXIT} to {@code null}.
284 * <p>
285 * A block's immediate post dominator is the unique block that strictly post dominates that block, but does not
286 * strictly post dominate any other block that strictly post dominates that block.
287 * <p>
288 * The exit block has no immediate post dominator, since it is not strictly post dominated by any other block. Its
289 * corresponding entry in the map has a {@code null} value.
290 *
291 * @return a map of block to its immediate post dominator, as an unmodifiable map
292 * @throws IllegalStateException if there is no single exit block, synthesized or otherwise
293 * @see Block#immediatePostDominator()
294 */
295 public Map<Block, Block> immediatePostDominators() {
296 Map<Block, Block> pdoms = new HashMap<>();
297
298 // If there are multiple exit blocks (those with zero successors)
299 // then use the block IPDOM_EXIT that is the synthetic successor of
300 // the exit blocks
301 boolean nSuccessors = blocks.stream().filter(b -> b.successors().isEmpty()).count() > 1;
302
303 List<Block> exits = blocks.stream().filter(b -> b.successors().isEmpty()).toList();
304 switch (exits.size()) {
305 case 0 -> throw new IllegalStateException();
306 case 1 -> pdoms.put(exits.getFirst(), null);
307 default -> pdoms.put(IPDOM_EXIT, null);
308 }
309
310 // Blocks are sorted in reverse postorder
311 boolean changed;
312 do {
313 changed = false;
314 // Iterate in reverse through blocks in reverse postorder, except for exit block
315 for (int i = blocks.size() - (nSuccessors ? 1 : 2); i >= 0; i--) {
316 Block b = blocks.get(i);
317
318 // Find first processed successor of b
319 Block newIpdom = null;
320 Collection<Block> targets = b.successorTargets();
321 for (Block s : nSuccessors && targets.isEmpty() ? List.of(IPDOM_EXIT) : targets) {
322 if (pdoms.containsKey(s)) {
323 newIpdom = s;
324 break;
325 }
326 }
327
328 if (newIpdom == null) {
329 // newIpdom can be null if all successors reference
330 // prior blocks (back branch) yet to be encountered
331 // in the dominator treee
332 continue;
333 }
334
335 // For all other successors, s, of b
336 for (Block s : b.successorTargets()) {
337 if (s == newIpdom) {
338 continue;
339 }
340
341 if (pdoms.containsKey(s)) {
342 // If already calculated
343 newIpdom = postIntersect(pdoms, s, newIpdom, blocks.size());
344 }
345 }
346
347 if (pdoms.get(b) != newIpdom) {
348 pdoms.put(b, newIpdom);
349 changed = true;
350 }
351 }
352 } while (changed);
353
354 return Collections.unmodifiableMap(pdoms);
355 }
356
357 static Block postIntersect(Map<Block, Block> doms, Block b1, Block b2, int exitIndex) {
358 while (b1 != b2) {
359 while (b1.index() < b2.index()) {
360 b1 = doms.get(b1);
361 }
362
363 while (b2.index() < b1.index()) {
364 b2 = doms.get(b2);
365 }
366 }
367
368 return b1;
369 }
370
371 /**
372 * Returns the post dominance frontier of each block in the body.
373 * <p>
374 * The post dominance frontier of block, {@code B} say, is the set of all blocks, {@code C} say,
375 * such that {@code B} post dominates a successor of {@code C} but does not strictly post dominate
376 * {@code C}.
377 *
378 * @return the post dominance frontier of each block in the body, as a modifiable map
379 */
380 public Map<Block, Set<Block>> postDominanceFrontier() {
381 // @@@ cache result?
382 Map<Block, Block> idoms = immediatePostDominators();
383 Map<Block, Set<Block>> df = new HashMap<>();
384
385 for (Block b : blocks) {
386 Set<Block> succs = b.successorTargets();
387
388 if (succs.size() > 1) {
389 for (Block s : succs) {
390 Block runner = s;
391 while (runner != idoms.get(b)) {
392 df.computeIfAbsent(runner, _ -> new LinkedHashSet<>()).add(b);
393 runner = idoms.get(runner);
394 }
395 }
396 }
397 }
398
399 return df;
400 }
401
402 /**
403 * {@return true if this body is isolated}
404 * <p>
405 * An isolated body, built by an <a href="Body.Builder.html#isolated-builder">isolated</a> body builder, is
406 * guaranteed to never {@link #capturedValues() capture} values. Conversely, an open body, built by a
407 * <a href="Body.Builder.html#connected-builder">connected</a> body builder, may or may not capture values,
408 * depending on how the body's descendant operations use values.
409 *
410 * @see #capturedValues()
411 */
412 public boolean isIsolated() {
413 return connectedAncestorBody == null;
414 }
415
416 /**
417 * Computes values captured by this body. A captured value is a value that is used
418 * but not declared by any descendant block or operation of this body.
419 * <p>
420 * The order of the captured values is first use encountered in depth
421 * first search of this body's descendant operations.
422 *
423 * @return the list of captured values, modifiable
424 */
425 public List<Value> capturedValues() {
426 Set<Value> cvs = new LinkedHashSet<>();
427
428 capturedValues(cvs, new ArrayDeque<>(), this);
429 return new ArrayList<>(cvs);
430 }
431
432 static void capturedValues(Set<Value> capturedValues, Deque<Body> bodyStack, Body body) {
433 bodyStack.push(body);
434
435 for (Block b : body.blocks()) {
436 for (Op op : b.ops()) {
437 for (Body childBody : op.bodies()) {
438 capturedValues(capturedValues, bodyStack, childBody);
439 }
440
441 for (Value a : op.operands()) {
442 if (!bodyStack.contains(a.declaringBlock().ancestorBody())) {
443 capturedValues.add(a);
444 }
445 }
446
447 for (Block.Reference s : op.successors()) {
448 for (Value a : s.arguments()) {
449 if (!bodyStack.contains(a.declaringBlock().ancestorBody())) {
450 capturedValues.add(a);
451 }
452 }
453 }
454 }
455 }
456
457 bodyStack.pop();
458 }
459
460 /**
461 * A builder for a body.
462 * <p>
463 * <a id="body-building-process"></a>
464 * The process of building a body starts with the {@link Builder#of(Builder, FunctionType, CodeContext, CodeTransformer) creation}
465 * of a body builder, which {@link Builder#entryBlock exposes} a {@link Block.Builder block builder} for the body's
466 * entry block.
467 * <p>
468 * Building then progresses with the building of the body's structure, where:
469 * <ul>
470 * <li>
471 * the entry block builder is used to {@link Block.Builder#block(List) create} block builders for sibling blocks,
472 * and likewise those block builders can also be used to create block builders for additional sibling blocks and so
473 * on;
474 * <li>
475 * a block builder is used to {@link Block.Builder#add(Op) append} operations to the block,
476 * {@link Block.Builder#parameter(CodeType) append} parameters to the block's parameters, and
477 * {@link Block.Builder#reference(List) create} references to the block, which can be used as successors of a
478 * terminating operation that is the last operation that is appended to the block or a sibling block; and
479 * <li>
480 * <a id="body-building-observability"></a>
481 * the body and its child blocks are not observable; attempts to observe them through appended operations, their
482 * operation results, block parameters, or block references, throw an {@link IllegalStateException}.
483 * </ul>
484 * <p>
485 * Building finishes by invoking {@link #build(Op)}, with a given operation that becomes the body's
486 * parent.
487 * <p>
488 * <a id="body-building-finishing"></a>
489 * After building finishes, the body and its child blocks become observable, and the body builder and its block
490 * builders all become inoperable, regardless of whether building succeeds or fails with an exception.
491 * Further attempts to operate on the builders throw an {@link IllegalStateException}.
492 * <p>
493 * A body builder may be connected to its {@link #connectedAncestorBody() nearest ancestor} body builder. This
494 * connection constrains the order in which the connected builders can finish building, ancestors cannot finish
495 * before their descendants, and determines the <a href="Block.Builder.html#reachable-value">reachability</a> of
496 * values used by appended operations.
497 * <p>
498 * Body builders are not thread-safe. Block builders associated with a body builder are also not thread-safe.
499 */
500 public final class Builder {
501 /**
502 * Creates a body builder, with an entry block {@link #entryBlock builder} that has a code context and code
503 * transformer derived from {@code connectedAncestorBody}.
504 * <p>
505 * If {@code connectedAncestorBody} is {@code null} then the entry block builder has a
506 * {@link CodeContext#create() new} code context and a {@link CodeTransformer#COPYING_TRANSFORMER copying}
507 * code transformer.
508 * If {@code connectedAncestorBody} is {@code non-null} then the entry block builder has a
509 * {@link CodeContext#create(CodeContext) child} of {@code connectedAncestorBody}'s entry block builder's code
510 * context and the same code transformer as {@code connectedAncestorBody}'s entry block builder.
511 *
512 * @param connectedAncestorBody the nearest ancestor body builder if the created body builder is connected, or
513 * {@code null} if the created body builder is isolated
514 * @param bodySignature the initial body signature
515 * @return the body builder
516 * @throws IllegalStateException if the ancestor body builder is finished
517 * @see #of(Builder, FunctionType, CodeContext, CodeTransformer)
518 */
519 public static Builder of(Builder connectedAncestorBody, FunctionType bodySignature) {
520 Block.Builder connectedEntryBlockBuilder = connectedAncestorBody != null
521 ? connectedAncestorBody.entryBlock()
522 : null;
523 CodeContext cc = connectedEntryBlockBuilder != null
524 ? CodeContext.create(connectedEntryBlockBuilder.context())
525 : CodeContext.create();
526 CodeTransformer ct = connectedEntryBlockBuilder != null
527 ? connectedEntryBlockBuilder.transformer()
528 : CodeTransformer.COPYING_TRANSFORMER;
529 return of(connectedAncestorBody, bodySignature, cc, ct);
530 }
531
532 /**
533 * Creates a body builder, with an entry block {@link #entryBlock builder} that has a code context derived
534 * from {@code connectedAncestorBody} and the given code transformer.
535 * <p>
536 * If {@code connectedAncestorBody} is {@code null}, then the entry block builder has a
537 * {@link CodeContext#create() new} code context.
538 * If {@code connectedAncestorBody} is {@code non-null} then the entry block builder has a
539 * {@link CodeContext#create(CodeContext) child} of {@code connectedAncestorBody}'s entry block builder's code
540 * context.
541 *
542 * If {@code connectedAncestorBody} is {@code non-null}, then the entry block builder has the same code context
543 * as {@code connectedAncestorBody}'s entry block builder.
544 *
545 * @param connectedAncestorBody the nearest ancestor body builder if the created body builder is connected, or
546 * {@code null} if the created body builder is isolated
547 * @param bodySignature the initial body signature
548 * @param ct the code transformer for the entry block builder
549 * @return the body builder
550 * @throws IllegalStateException if the ancestor body builder is finished
551 * @see #of(Builder, FunctionType, CodeContext, CodeTransformer)
552 */
553 public static Builder of(Builder connectedAncestorBody, FunctionType bodySignature, CodeTransformer ct) {
554 Block.Builder connectedEntryBlockBuilder = connectedAncestorBody != null
555 ? connectedAncestorBody.entryBlock()
556 : null;
557 CodeContext cc = connectedEntryBlockBuilder != null
558 ? CodeContext.create(connectedEntryBlockBuilder.context())
559 : CodeContext.create();
560 return of(connectedAncestorBody, bodySignature, cc, ct);
561 }
562
563 /**
564 * Creates a body builder, with an entry block {@link #entryBlock builder} that has the given code context and
565 * code transformer.
566 * <p>
567 * If {@code connectedAncestorBody} is non-{@code null}, the created body builder is
568 * <a id="connected-builder"><i>connected</i></a> to {@code connectedAncestorBody} as the
569 * {@link #connectedAncestorBody() nearest ancestor} body builder, builds an <i>open</i> body, and the following
570 * apply:
571 * <ul>
572 * <li>
573 * the created body builder must finish before the nearest ancestor body builder finishes, which implies the
574 * ancestor body builder cannot finish until all body builders connected to it finish; and
575 * <li>
576 * the body built by the created body builder must have, as its nearest {@link Body#ancestorBody() ancestor body},
577 * the body built by the nearest ancestor body builder.
578 * </ul>
579 * If {@code connectedAncestorBody} is {@code null}, the created body builder is
580 * <a id="isolated-builder"><i>isolated</i></a>, it has no nearest ancestor body builder, builds an
581 * <i>isolated</i> body, and the following applies:
582 * <ul>
583 * <li>
584 * the scope of <a href="Block.Builder.html#reachable-value">reachable</a> values used by operations is
585 * reduced to that up to and including the created body builder.
586 * </ul>
587 * <p>
588 * One or more body builders can be connected to the created body builder, as their nearest ancestor body
589 * builder, whether the created body builder be connected or isolated, which implies the created body builder
590 * cannot finish until all of its connected body builders finish.
591 * <p>
592 * The initial body signature's return type defines the body's yield type, and its parameter types are used,
593 * in order, to create the initial parameters of the entry block builder.
594 *
595 * @param connectedAncestorBody the nearest ancestor body builder if the created body builder is connected, or
596 * {@code null} if the created body builder is isolated
597 * @param bodySignature the initial body signature
598 * @param cc the code context for the entry block builder
599 * @param ct the code transformer for the entry block builder
600 * @return the body builder
601 * @throws IllegalStateException if the connected ancestor body builder is finished
602 */
603 public static Builder of(Builder connectedAncestorBody, FunctionType bodySignature,
604 CodeContext cc, CodeTransformer ct) {
605 Body body = new Body(connectedAncestorBody != null ? connectedAncestorBody.target() : null,
606 bodySignature.returnType());
607 return body.new Builder(connectedAncestorBody, bodySignature, cc, ct);
608 }
609
610 // The connected nearest ancestor body, may be null
611 final Builder connectedAncestorBody;
612
613 // The entry block of this body, whose parameters are given by the body's function type
614 final Block.Builder entryBlock;
615
616 // When non-null contains one or more great-grandchildren
617 List<Builder> greatgrandchildren;
618
619 // True when finished
620 boolean finished;
621
622 Builder(Builder connectedAncestorBody, FunctionType bodySignature,
623 CodeContext cc, CodeTransformer ct) {
624
625 // Structural check
626 // The connected ancestor body should not be built before this body is built
627 if (connectedAncestorBody != null) {
628 connectedAncestorBody.check();
629 connectedAncestorBody.addGreatgrandchild(this);
630 }
631
632 this.connectedAncestorBody = connectedAncestorBody;
633 // Create entry block from the body's function type
634 Block eb = Body.this.createBlock(bodySignature.parameterTypes());
635 this.entryBlock = eb.new Builder(this, cc, ct);
636 }
637
638 void addGreatgrandchild(Builder greatgrandchild) {
639 var l = greatgrandchildren == null
640 ? (greatgrandchildren = new ArrayList<>()) : greatgrandchildren;
641 l.add(greatgrandchild);
642 }
643
644 /**
645 * Finishes building the body and its child blocks, associating the body with a parent operation.
646 * <p>
647 * The parent operation must report the built body as one of its child bodies.
648 * <p>
649 * After building finishes, the body builder and its block builders all become inoperable, regardless of whether
650 * building succeeds or fails with an exception. Further attempts to operate on the builders throw an exception.
651 * <p>
652 * Body builders connected to this body builder must finish building before this body builder finishes.
653 * <p>
654 * The entry block and all blocks reachable from it, by following successors, become children of the body. The
655 * reachable blocks are sorted in reverse postorder and form a control-flow graph. In that graph, the entry
656 * block dominates every other block. Any block not reached from the entry block is unreachable, does not become
657 * a child of the body, and remains unobservable after building finishes. An unreachable block may have a
658 * successor whose target is a reachable block, and may use a value declared in a reachable block or an ancestor
659 * block being built.
660 *
661 * @apiNote
662 * This method is commonly called from the parent operation's constructor, which holds a reference to the built
663 * body so it can report it as one of its child bodies.
664 *
665 * @param op the parent operation
666 * @return the built body
667 * @throws IllegalStateException if this body builder has finished
668 * @throws IllegalStateException if any connected body builder finishes unsuccessfully
669 * @throws IllegalStateException if any connected body builder finishes successfully and its body's parent
670 * operation is unplaced
671 * @throws IllegalStateException if a reachable block has no terminating operation
672 * @throws IllegalStateException if a reachable block has a successor whose number of arguments is not equal to
673 * the number of parameters of the successor's target block
674 * @throws IllegalStateException if an operation result or block parameter declared in an unreachable block is
675 * used by an operation in a reachable block or a descendant block of a reachable block.
676 * @throws IllegalStateException if an operation result or block parameter declared in a reachable block does
677 * not {@link Value#isDominatedBy(Value) dominate} a use of that value
678 */
679 public Body build(Op op) {
680 // Structural check
681 // This body builder should not be finished
682 check();
683 Objects.requireNonNull(op);
684 finished = true;
685
686 // Structural check
687 // All great-grandchildren bodies should be built
688 if (greatgrandchildren != null) {
689 for (Builder greatgrandchild : greatgrandchildren) {
690 if (!greatgrandchild.finished || greatgrandchild.target().parentOp == null) {
691 // Building did not finish, or finished with an exception
692 throw new IllegalStateException("Descendant body builder is not built");
693 }
694
695 Op.Result grandchild = greatgrandchild.target().parentOp.result();
696 if (grandchild == null) {
697 throw new IllegalStateException("Parent operation of descendant body is unplaced");
698 }
699 assert Body.this == grandchild.block.parentBody;
700 }
701 }
702
703 sortReversePostorder();
704 checkValueUse();
705
706 Body.this.parentOp = op;
707 return Body.this;
708 }
709
710 private static final int UNSORTED_INDEX = Block.UNBUILT_BLOCK_INDEX;
711 private static final int UNASSIGNED_INDEX = -2;
712
713 // Sort blocks in reverse post order, removing any unreachable blocks
714 // After sorting the following holds for a block
715 // block.parentBody().blocks().indexOf(block) == block.index()
716 private void sortReversePostorder() {
717 if (blocks.size() == 1) {
718 Block e = blocks.getFirst();
719 checkBlock(e);
720
721 e.index = 0;
722 return;
723 }
724
725 Deque<Block> stack = new ArrayDeque<>();
726 stack.push(blocks.get(0));
727
728 // Postorder iteration, starting from the entry block
729 int index = blocks.size();
730 while (!stack.isEmpty()) {
731 Block n = stack.peek();
732 if (n.index == UNASSIGNED_INDEX) {
733 // If n's successor has been processed then add n
734 stack.pop();
735 n.index = --index;
736 } else if (n.index != UNSORTED_INDEX) {
737 // If n has already been processed then ignore
738 stack.pop();
739 } else {
740 checkBlock(n);
741
742 // Mark before processing successors, a successor may refer back to n
743 n.index = UNASSIGNED_INDEX;
744 for (Block.Reference s : n.successors()) {
745 Block target = s.target;
746
747 // Check successor arity
748 if (s.arguments().size() != target.parameters().size()) {
749 String m = String.format("Reference to block %s with %d arguments but the block has %d parameters",
750 target, s.arguments().size(), target.parameters().size());
751 throw new IllegalStateException(m);
752 }
753
754 // Update target's predecessors with n
755 target.predecessors.add(n);
756 if (target.index != UNSORTED_INDEX) {
757 continue;
758 }
759
760 stack.push(target);
761 }
762 }
763 }
764
765 // Sort blocks by their reverse postorder indexes
766 blocks.sort(Comparator.comparingInt(b -> b.index < 0 ? Integer.MAX_VALUE : b.index));
767 // Remove unreachable blocks, those that are not dominated by the entry block
768 // They will be sorted at the end
769 int nUnreachableBlocks = blocks.get(0).index;
770 if (nUnreachableBlocks > 0) {
771 removeUnreachableBlocksAndValueUses(nUnreachableBlocks);
772 }
773
774 assert IntStream.range(0, blocks().size()).allMatch(i -> i == blocks.get(i).index);
775 assert blocks.stream().<List<Block>>mapMulti((b, consumer) -> {
776 for (Block.Reference s : b.successors()) {
777 consumer.accept(List.of(s.target, b));
778 }
779 }).allMatch(l -> l.get(0).predecessors.contains(l.get(1)));
780 }
781
782 private static void checkBlock(Block b) {
783 if (b.ops.isEmpty() || !(b.ops.getLast() instanceof Op.Terminating)) {
784 throw new IllegalStateException("Block has no terminating operation as the last operation");
785 }
786 }
787
788 private void removeUnreachableBlocksAndValueUses(int nUnreachableBlocks) {
789 List<Block> unreachableBlocks = blocks.subList(blocks.size() - nUnreachableBlocks, blocks.size());
790 // Remove uses of values in unreachable blocks
791 for (Block b : unreachableBlocks) {
792 assert b.index == UNSORTED_INDEX;
793
794 // It is ok to traverse the unobservable blocks via elements() prior to removal
795 // Direct access of the uses field is required since public access requires an observable block
796
797 // If an operation in an unreachable block uses a value not declared in an unreachable
798 // block, then the use needs to be removed.
799 // It is simpler to remove all uses, rather than check for specific uses.
800 b.elements().forEach(ce -> {
801 switch (ce) {
802 case Op op -> {
803 Op.Result use = op.result();
804 for (Value v : op.operands()) {
805 v.uses.remove(use);
806 }
807
808 for (Block.Reference s : op.successors()) {
809 for (Value v : s.arguments()) {
810 v.uses.remove(use);
811 }
812 }
813 }
814 default -> {
815 }
816 }
817 });
818 }
819 // Check uses of values declared in unreachable blocks
820 for (Block b : unreachableBlocks) {
821 // If an operation result or block parameter declared in an unreachable block is used by an operation
822 // in block that is not an unreachable block, then such use is invalid.
823 // Given the prior removal of all uses we only need to check if a declared value has uses or not.
824 // If so they must be from a block that is not unreachable and therefore the is invalid
825 b.elements().forEach(ce -> {
826 switch (ce) {
827 case Op op -> {
828 Op.Result use = op.result();
829 if (!use.uses.isEmpty()) {
830 throw new IllegalStateException("Use of an operation result is not dominated by the result");
831 }
832 }
833 case Block bb -> {
834 for (Block.Parameter p : bb.parameters()) {
835 if (!p.uses.isEmpty()) {
836 throw new IllegalStateException("Use of block parameter is not dominated by the parameter");
837 }
838 }
839 }
840 default -> {
841 }
842 }
843 });
844 }
845 // Remove unreachable blocks
846 unreachableBlocks.clear();
847
848 // Reassign indexes to their natural indexes, sort order is preserved
849 for (int i = 0; i < blocks.size(); i++) {
850 blocks.get(i).index = i;
851 }
852 }
853
854 // Validate each use of a value declared in the body.
855 // The use's declaring block must be dominated by the value's declaring block
856 private void checkValueUse() {
857 if (blocks.size() > 1) {
858 // Only need to check when there is more than one block, since for one block
859 // the use's declaring block will be the same as or a descendant of the
860 // value's declaring block.
861 // No need to check use within the same block, since operation results
862 // cannot be used until an operation is appended.
863 for (Block block : blocks) {
864 for (Block.Parameter p : block.parameters()) {
865 for (Op.Result use : p.uses()) {
866 if (!use.declaringBlock().isDominatedBy(block)) {
867 throw new IllegalStateException("Use of value is not dominated by value");
868 }
869 }
870 }
871
872 for (Op o : block.ops()) {
873 Op.Result r = o.result();
874 for (Op.Result use : r.uses()) {
875 if (!use.declaringBlock().isDominatedBy(block)) {
876 throw new IllegalStateException("Use of value is not dominated by value");
877 }
878 }
879 }
880 }
881 }
882 }
883
884 /**
885 * Returns this body builder's signature, represented as a function type.
886 * <p>
887 * The signature's return type is the body builder's yield type and parameter types are
888 * the currently built entry block's parameter types, in order.
889 *
890 * @return the body builder's signature
891 */
892 public FunctionType bodySignature() {
893 check();
894 CodeType returnType = Body.this.yieldType();
895 Block eb = Body.this.entryBlock();
896 return CoreType.functionType(returnType, eb.parameterTypes());
897 }
898
899 /**
900 * {@return this body builder's connected ancestor body builder if this body builder is
901 * <a href="#connected-builder">connected</a>, otherwise {@code null} if this body builder is isolated}
902 */
903 public Builder connectedAncestorBody() {
904 check();
905 return connectedAncestorBody;
906 }
907
908 /**
909 * {@return this body builder's entry block builder}
910 */
911 public Block.Builder entryBlock() {
912 check();
913 return entryBlock;
914 }
915
916 @Override
917 public boolean equals(Object o) {
918 check();
919 if (this == o) return true;
920 return o instanceof Builder that && Body.this == that.target();
921 }
922
923 @Override
924 public int hashCode() {
925 check();
926 return Body.this.hashCode();
927 }
928
929 void check() {
930 if (finished) {
931 throw new IllegalStateException("Builder is finished");
932 }
933 }
934
935 Body target() {
936 return Body.this;
937 }
938
939 // Build new block in body
940 Block.Builder block(List<CodeType> params, CodeContext cc, CodeTransformer ct) {
941 Block block = Body.this.createBlock(params);
942
943 return block.new Builder(this, cc, ct);
944 }
945 }
946
947 /**
948 * Transforms this body, returning an output body builder containing the transformed body.
949 * <p>
950 * This method creates an output body builder for this input body's {@link #bodySignature() signature}, with a
951 * {@link CodeContext#create(CodeContext) child} of the given parent code context, and the given code transformer.
952 * <p>
953 * The output body builder is <a href="Body.Builder.html#connected-builder">connected</a> to a body builder, as its
954 * nearest ancestor body builder, if that builder can be determined from this input body and the given parent code
955 * context. Otherwise, the output body builder is <a href="Body.Builder.html#isolated-builder">isolated</a>.
956 * <p>
957 * This method then transforms this input body by invoking
958 * {@link CodeTransformer#acceptBody(Block.Builder, Body, List)} with the created output body builder's
959 * {@link Body.Builder#entryBlock() entry} block builder, this input body, and that entry block builder's
960 * parameters.
961 *
962 * @apiNote
963 * To copy a body use the {@link CodeTransformer#COPYING_TRANSFORMER copying transformer}.
964 * <p>
965 * The body builder connected to the output body builder can be explicitly determined when this
966 * input body's {@link Body#ancestorBody() nearest ancestor} body is present and observable, and the given parent
967 * code context can be used to {@link CodeContext#queryBody(Body) query} the present body builder for that ancestor
968 * body. For example, in such cases:
969 * {@snippet lang = "java":
970 * Body nearestAncestorBody = this.ancestorBody(); // @link substring="ancestorBody" target="jdk.incubator.code.CodeElement#ancestorBody"
971 * Body.Builder connectedBodyBuilder = cc.queryBody(nearestAncestorBody).orElseThrow(); // @link substring="queryBody" target="jdk.incubator.code.CodeContext#queryBody"
972 * }
973 *
974 * @param cc the parent code context
975 * @param ct the code transformer
976 * @return a body builder containing the transformed body
977 */
978 public Builder transform(CodeContext cc, CodeTransformer ct) {
979 Builder connectedAncestorBodyBuilder = connectedAncestorBody != null
980 ? cc.queryBody(connectedAncestorBody).orElse(null)
981 : null;
982 Builder bodyBuilder = Builder.of(connectedAncestorBodyBuilder,
983 bodySignature(),
984 // Create child context for mapped code items contained in this body
985 // thereby not polluting the given context
986 CodeContext.create(cc), ct);
987
988 // Transform body starting from the entry block builder
989 ct.acceptBody(bodyBuilder.entryBlock, this, bodyBuilder.entryBlock.parameters());
990 return bodyBuilder;
991 }
992
993 // Modifying methods
994
995 // Create block
996 private Block createBlock(List<CodeType> params) {
997 Block b = new Block(this, params);
998 blocks.add(b);
999 return b;
1000 }
1001 }