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 exception.
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
503 * {@link CodeContext#create() new} code context and a {@link CodeTransformer#COPYING_TRANSFORMER copying}
504 * 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 * @return the body builder
510 * @throws IllegalStateException if the ancestor body builder is finished
511 * @see #of(Builder, FunctionType, CodeContext, CodeTransformer)
512 */
513 public static Builder of(Builder connectedAncestorBody, FunctionType bodySignature) {
514 // @@@ Creation of CodeContext
515 return of(connectedAncestorBody, bodySignature, CodeContext.create(), CodeTransformer.COPYING_TRANSFORMER);
516 }
517
518 /**
519 * Creates a body builder, with an entry block {@link #entryBlock builder} that has the given code context
520 * and a {@link CodeTransformer#COPYING_TRANSFORMER copying} code transformer.
521 *
522 * @param connectedAncestorBody the nearest ancestor body builder if the created body builder is connected, or
523 * {@code null} if the created body builder is isolated
524 * @param bodySignature the initial body signature
525 * @param cc the code context
526 * @return the body builder
527 * @throws IllegalStateException if the ancestor body builder is finished
528 * @see #of(Builder, FunctionType, CodeContext, CodeTransformer)
529 */
530 public static Builder of(Builder connectedAncestorBody, FunctionType bodySignature, CodeContext cc) {
531 return of(connectedAncestorBody, bodySignature, cc, CodeTransformer.COPYING_TRANSFORMER);
532 }
533
534 /**
535 * Creates a body builder whose entry block {@link #entryBlock builder} uses the given code context and code
536 * transformer.
537 * <p>
538 * If {@code connectedAncestorBody} is non-{@code null}, the created body builder is
539 * <a id="connected-builder"><i>connected</i></a> to {@code connectedAncestorBody} as the
540 * {@link #connectedAncestorBody() nearest ancestor} body builder, builds an <i>open</i> body, and the following
541 * apply:
542 * <ul>
543 * <li>
544 * the created body builder must finish before the nearest ancestor body builder finishes, which implies the
545 * ancestor body builder cannot finish until all body builders connected to it finish; and
546 * <li>
547 * the body built by the created body builder must have, as its nearest {@link Body#ancestorBody() ancestor body},
548 * the body built by the nearest ancestor body builder.
549 * </ul>
550 * If {@code connectedAncestorBody} is {@code null}, the created body builder is
551 * <a id="isolated-builder"><i>isolated</i></a>, it has no nearest ancestor body builder, builds an
552 * <i>isolated</i> body, and the following applies:
553 * <ul>
554 * <li>
555 * the scope of <a href="Block.Builder.html#reachable-value">reachable</a> values used by operations is
556 * reduced to that up to and including the created body builder.
557 * </ul>
558 * <p>
559 * One or more body builders can be connected to the created body builder, as their nearest ancestor body
560 * builder, whether the created body builder be connected or isolated, which implies the created body builder
561 * cannot finish until all of its connected body builders finish.
562 * <p>
563 * The initial body signature's return type defines the body's yield type, and its parameter types are used,
564 * in order, to create the initial parameters of the entry block builder.
565 *
566 * @param connectedAncestorBody the nearest ancestor body builder if the created body builder is connected, or
567 * {@code null} if the created body builder is isolated
568 * @param bodySignature the initial body signature
569 * @param cc the code context for the entry block builder
570 * @param ct the code transformer for the entry block builder
571 * @return the body builder
572 * @throws IllegalStateException if the connected ancestor body builder is finished
573 */
574 public static Builder of(Builder connectedAncestorBody, FunctionType bodySignature,
575 CodeContext cc, CodeTransformer ct) {
576 Body body = new Body(connectedAncestorBody != null ? connectedAncestorBody.target() : null,
577 bodySignature.returnType());
578 return body.new Builder(connectedAncestorBody, bodySignature, cc, ct);
579 }
580
581 // The connected nearest ancestor body, may be null
582 final Builder connectedAncestorBody;
583
584 // The entry block of this body, whose parameters are given by the body's function type
585 final Block.Builder entryBlock;
586
587 // When non-null contains one or more great-grandchildren
588 List<Builder> greatgrandchildren;
589
590 // True when finished
591 boolean finished;
592
593 Builder(Builder connectedAncestorBody, FunctionType bodySignature,
594 CodeContext cc, CodeTransformer ct) {
595 // Structural check
596 // The connected ancestor body should not be built before this body is built
597 if (connectedAncestorBody != null) {
598 connectedAncestorBody.check();
599 connectedAncestorBody.addGreatgrandchild(this);
600 }
601
602 this.connectedAncestorBody = connectedAncestorBody;
603 // Create entry block from the body's function type
604 Block eb = Body.this.createBlock(bodySignature.parameterTypes());
605 this.entryBlock = eb.new Builder(this, cc, ct);
606 }
607
608 void addGreatgrandchild(Builder greatgrandchild) {
609 var l = greatgrandchildren == null
610 ? (greatgrandchildren = new ArrayList<>()) : greatgrandchildren;
611 l.add(greatgrandchild);
612 }
613
614 /**
615 * Finishes building the body and its child blocks, associating the body with a parent operation.
616 * <p>
617 * The parent operation must report the built body as one of its child bodies.
618 * <p>
619 * After building finishes, the body builder and its block builders all become inoperable, regardless of whether
620 * building succeeds or fails with an exception. Further attempts to operate on the builders throw an exception.
621 * <p>
622 * Body builders connected to this body builder must finish building before this body builder finishes.
623 * <p>
624 * The entry block and all blocks reachable from it, by following successors, become children of the body. The
625 * reachable blocks are sorted in reverse postorder and form a control-flow graph. In that graph, the entry
626 * block dominates every other block. Any block not reached from the entry block is unreachable, does not become
627 * a child of the body, and remains unobservable after building finishes. An unreachable block may have a
628 * successor whose target is a reachable block, and may use a value declared in a reachable block or an ancestor
629 * block being built.
630 *
631 * @apiNote
632 * This method is commonly called from the parent operation's constructor, which holds a reference to the built
633 * body so it can report it as one of its child bodies.
634 *
635 * @param op the parent operation
636 * @return the built body
637 * @throws IllegalStateException if this body builder has finished
638 * @throws IllegalStateException if any connected body builder finishes unsuccessfully
639 * @throws IllegalStateException if any connected body builder finishes successfully and its body's parent
640 * operation is unplaced
641 * @throws IllegalStateException if a reachable block has no terminating operation
642 * @throws IllegalStateException if a reachable block has a successor whose number of arguments is greater than
643 * the number of parameters of the successor's target block
644 * @throws IllegalStateException if an operation result or block parameter declared in an unreachable block is
645 * used by an operation in a reachable block or a descendant block of a reachable block.
646 * @throws IllegalStateException if an operation result or block parameter declared in a reachable block does
647 * not {@link Value#isDominatedBy(Value) dominate} a use of that value
648 */
649 public Body build(Op op) {
650 Objects.requireNonNull(op);
651
652 // Structural check
653 // This body builder should not be finished
654 check();
655 finished = true;
656
657 // Structural check
658 // All great-grandchildren bodies should be built
659 if (greatgrandchildren != null) {
660 for (Builder greatgrandchild : greatgrandchildren) {
661 if (!greatgrandchild.finished || greatgrandchild.target().parentOp == null) {
662 // Building did not finish, or finished with an exception
663 throw new IllegalStateException("Descendant body builder is not built");
664 }
665
666 Op.Result grandchild = greatgrandchild.target().parentOp.result;
667 if (grandchild == null) {
668 throw new IllegalStateException("Parent operation of descendant body is unplaced");
669 }
670 assert Body.this == grandchild.block.parentBody;
671 }
672 }
673
674 sortReversePostorder();
675 checkValueUse();
676
677 Body.this.parentOp = op;
678 return Body.this;
679 }
680
681 private static final int UNSORTED_INDEX = Block.UNBUILT_BLOCK_INDEX;
682 private static final int UNASSIGNED_INDEX = -2;
683
684 // Sort blocks in reverse post order, removing any unreachable blocks
685 // After sorting the following holds for a block
686 // block.parentBody().blocks().indexOf(block) == block.index()
687 private void sortReversePostorder() {
688 if (blocks.size() == 1) {
689 Block e = blocks.getFirst();
690 checkBlock(e);
691
692 e.index = 0;
693 return;
694 }
695
696 Deque<Block> stack = new ArrayDeque<>();
697 stack.push(blocks.get(0));
698
699 // Postorder iteration, starting from the entry block
700 int index = blocks.size();
701 while (!stack.isEmpty()) {
702 Block n = stack.peek();
703 if (n.index == UNASSIGNED_INDEX) {
704 // If n's successor has been processed then add n
705 stack.pop();
706 n.index = --index;
707 } else if (n.index != UNSORTED_INDEX) {
708 // If n has already been processed then ignore
709 stack.pop();
710 } else {
711 checkBlock(n);
712
713 // Mark before processing successors, a successor may refer back to n
714 n.index = UNASSIGNED_INDEX;
715 for (Block.Reference s : n.successors()) {
716 Block target = s.target;
717
718 // Check successor arity
719 if (s.arguments().size() > target.parameters().size()) {
720 String m = String.format("Reference to block %s with %d arguments but the block has %d parameters",
721 target, s.arguments().size(), target.parameters().size());
722 throw new IllegalStateException(m);
723 }
724
725 // Update target's predecessors with n
726 target.predecessors.add(n);
727 if (target.index != UNSORTED_INDEX) {
728 continue;
729 }
730
731 stack.push(target);
732 }
733 }
734 }
735
736 // Sort blocks by their reverse postorder indexes
737 blocks.sort(Comparator.comparingInt(b -> b.index < 0 ? Integer.MAX_VALUE : b.index));
738 // Remove unreachable blocks, those that are not dominated by the entry block
739 // They will be sorted at the end
740 int nUnreachableBlocks = blocks.get(0).index;
741 if (nUnreachableBlocks > 0) {
742 removeUnreachableBlocksAndValueUses(nUnreachableBlocks);
743 }
744
745 assert IntStream.range(0, blocks().size()).allMatch(i -> i == blocks.get(i).index);
746 assert blocks.stream().<List<Block>>mapMulti((b, consumer) -> {
747 for (Block.Reference s : b.successors()) {
748 consumer.accept(List.of(s.target, b));
749 }
750 }).allMatch(l -> l.get(0).predecessors.contains(l.get(1)));
751 }
752
753 private static void checkBlock(Block b) {
754 if (b.ops.isEmpty() || !(b.ops.getLast() instanceof Op.Terminating)) {
755 throw new IllegalStateException("Block has no terminating operation as the last operation");
756 }
757 }
758
759 private void removeUnreachableBlocksAndValueUses(int nUnreachableBlocks) {
760 List<Block> unreachableBlocks = blocks.subList(blocks.size() - nUnreachableBlocks, blocks.size());
761 // Remove uses of values in unreachable blocks
762 for (Block b : unreachableBlocks) {
763 assert b.index == UNSORTED_INDEX;
764
765 // It is ok to traverse the unobservable blocks via elements() prior to removal
766 // Direct access of the uses field is required since public access requires an observable block
767
768 // If an operation in an unreachable block uses a value not declared in an unreachable
769 // block, then the use needs to be removed.
770 // It is simpler to remove all uses, rather than check for specific uses.
771 b.elements().forEach(ce -> {
772 switch (ce) {
773 case Op op -> {
774 Op.Result use = op.result;
775 for (Value v : op.operands()) {
776 v.uses.remove(use);
777 }
778
779 for (Block.Reference s : op.successors()) {
780 for (Value v : s.arguments()) {
781 v.uses.remove(use);
782 }
783 }
784 }
785 default -> {
786 }
787 }
788 });
789 }
790 // Check uses of values declared in unreachable blocks
791 for (Block b : unreachableBlocks) {
792 // If an operation result or block parameter declared in an unreachable block is used by an operation
793 // in block that is not an unreachable block, then such use is invalid.
794 // Given the prior removal of all uses we only need to check if a declared value has uses or not.
795 // If so they must be from a block that is not unreachable and therefore the is invalid
796 b.elements().forEach(ce -> {
797 switch (ce) {
798 case Op op -> {
799 Op.Result use = op.result;
800 if (!use.uses.isEmpty()) {
801 throw new IllegalStateException("Use of an operation result is not dominated by the result");
802 }
803 }
804 case Block bb -> {
805 for (Block.Parameter p : bb.parameters()) {
806 if (!p.uses.isEmpty()) {
807 throw new IllegalStateException("Use of block parameter is not dominated by the parameter");
808 }
809 }
810 }
811 default -> {
812 }
813 }
814 });
815 }
816 // Remove unreachable blocks
817 unreachableBlocks.clear();
818
819 // Reassign indexes to their natural indexes, sort order is preserved
820 for (int i = 0; i < blocks.size(); i++) {
821 blocks.get(i).index = i;
822 }
823 }
824
825 // Validate each use of a value declared in the body.
826 // The use's declaring block must be dominated by the value's declaring block
827 private void checkValueUse() {
828 if (blocks.size() > 1) {
829 // Only need to check when there is more than one block, since for one block
830 // the use's declaring block will be the same as or a descendant of the
831 // value's declaring block.
832 // No need to check use within the same block, since operation results
833 // cannot be used until an operation is appended.
834 for (Block block : blocks) {
835 for (Block.Parameter p : block.parameters()) {
836 for (Op.Result use : p.uses()) {
837 if (!use.declaringBlock().isDominatedBy(block)) {
838 throw new IllegalStateException("Use of value is not dominated by value");
839 }
840 }
841 }
842
843 for (Op o : block.ops()) {
844 Op.Result r = o.result();
845 for (Op.Result use : r.uses()) {
846 if (!use.declaringBlock().isDominatedBy(block)) {
847 throw new IllegalStateException("Use of value is not dominated by value");
848 }
849 }
850 }
851 }
852 }
853 }
854
855 /**
856 * Returns this body builder's signature, represented as a function type.
857 * <p>
858 * The signature's return type is the body builder's yield type and parameter types are
859 * the currently built entry block's parameter types, in order.
860 *
861 * @return the body builder's signature
862 */
863 public FunctionType bodySignature() {
864 CodeType returnType = Body.this.yieldType();
865 Block eb = Body.this.entryBlock();
866 return CoreType.functionType(returnType, eb.parameterTypes());
867 }
868
869 /**
870 * {@return this body builder's connected ancestor body builder if this body builder is
871 * <a href="#connected-builder">connected</a>, otherwise {@code null} if this body builder is isolated}
872 */
873 public Builder connectedAncestorBody() {
874 return connectedAncestorBody;
875 }
876
877 /**
878 * {@return this body builder's entry block builder}
879 */
880 public Block.Builder entryBlock() {
881 return entryBlock;
882 }
883
884 @Override
885 public boolean equals(Object o) {
886 if (this == o) return true;
887 return o instanceof Builder that && Body.this == that.target();
888 }
889
890 @Override
891 public int hashCode() {
892 return Body.this.hashCode();
893 }
894
895 void check() {
896 if (finished) {
897 throw new IllegalStateException("Builder is finished");
898 }
899 }
900
901 Body target() {
902 return Body.this;
903 }
904
905 // Build new block in body
906 Block.Builder block(List<CodeType> params, CodeContext cc, CodeTransformer ct) {
907 check();
908 Block block = Body.this.createBlock(params);
909
910 return block.new Builder(this, cc, ct);
911 }
912 }
913
914 /**
915 * Transforms this body, returning an output body builder containing the transformed body.
916 * <p>
917 * This method creates an output body builder for this input body's {@link #bodySignature() signature}, with a
918 * {@link CodeContext#create(CodeContext) child} of the given parent code context, and the given code transformer.
919 * <p>
920 * The output body builder is <a href="Body.Builder.html#connected-builder">connected</a> to a body builder, as its
921 * nearest ancestor body builder, if that builder can be determined from this input body and the given parent code
922 * context. Otherwise, the output body builder is <a href="Body.Builder.html#isolated-builder">isolated</a>.
923 * <p>
924 * This method then transforms this input body by invoking
925 * {@link CodeTransformer#acceptBody(Block.Builder, Body, List)} with the created output body builder's
926 * {@link Body.Builder#entryBlock() entry} block builder, this input body, and that entry block builder's
927 * parameters.
928 *
929 * @apiNote
930 * To copy a body use the {@link CodeTransformer#COPYING_TRANSFORMER copying transformer}.
931 * <p>
932 * The body builder connected to the output body builder can be explicitly determined when this
933 * input body's {@link Body#ancestorBody() nearest ancestor} body is present and observable, and the given parent
934 * code context can be used to {@link CodeContext#queryBody(Body) query} the present body builder for that ancestor
935 * body. For example, in such cases:
936 * {@snippet lang = "java":
937 * Body nearestAncestorBody = this.ancestorBody(); // @link substring="ancestorBody" target="jdk.incubator.code.CodeElement#ancestorBody"
938 * Body.Builder connectedBodyBuilder = cc.queryBody(nearestAncestorBody).orElseThrow(); // @link substring="queryBody" target="jdk.incubator.code.CodeContext#queryBody"
939 * }
940 *
941 * @param cc the parent code context
942 * @param ct the code transformer
943 * @return a body builder containing the transformed body
944 */
945 public Builder transform(CodeContext cc, CodeTransformer ct) {
946 Builder connectedAncestorBodyBuilder = connectedAncestorBody != null
947 ? cc.queryBody(connectedAncestorBody).orElse(null)
948 : null;
949 Builder bodyBuilder = Builder.of(connectedAncestorBodyBuilder,
950 bodySignature(),
951 // Create child context for mapped code items contained in this body
952 // thereby not polluting the given context
953 CodeContext.create(cc), ct);
954
955 // Transform body starting from the entry block builder
956 ct.acceptBody(bodyBuilder.entryBlock, this, bodyBuilder.entryBlock.parameters());
957 return bodyBuilder;
958 }
959
960 // Modifying methods
961
962 // Create block
963 private Block createBlock(List<CodeType> params) {
964 Block b = new Block(this, params);
965 blocks.add(b);
966 return b;
967 }
968 }