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 java.lang.reflect.code;
27
28 import java.lang.reflect.code.type.FunctionType;
29 import java.util.*;
30
31 /**
32 * A body containing a sequence of (basic) blocks.
33 * <p>
34 * The sequence of blocks form a graph. The last operation in a block, a terminating operation,
35 * may refer to other blocks in the sequence as successors, thus forming the graph. Otherwise, the last
36 * operation defines how the body passes control flow back to the parent operation, and in doing so may optionally
37 * yield a value.
38 * <p>
39 * The first block in the sequence is the entry block, and no other blocks refer to it as a successor.
40 * <p>
41 * A body has a function type whose return type is the body's yield type and whose parameter types are the entry
42 * block's parameters types, in order.
43 * The function type describes the sequence of input parameters types for arguments that are passed to the
44 * body when control flow is passed to it, and describes the return type of values that are returned when body passes
45 * control back to its parent operation.
46 */
47 public final class Body implements CodeElement<Body, Block> {
48 // Parent operation
49 // Non-null when body is built, and therefore bound to operation
50 Op parentOp;
51
52 // The ancestor body, when null the body is isolated and cannot refer to values defined outside
53 // When non-null and body is built, ancestorBody == parentOp.result.block.parentBody
54 final Body ancestorBody;
55
56 final TypeElement yieldType;
57
58 // Sorted in reverse postorder
59 final List<Block> blocks;
60
61 // Map of a block to its immediate dominator
62 // Computed lazily, null if not computed
63 Map<Block, Block> idoms;
64
65 /**
66 * Constructs a body, whose ancestor is the given ancestor body.
67 */
68 Body(Body ancestorBody, TypeElement yieldType) {
69 this.ancestorBody = ancestorBody;
70 this.yieldType = yieldType;
71 this.blocks = new ArrayList<>();
72 }
73
74 /**
75 * Returns this body's parent operation.
76 *
77 * @return the body's parent operation.
78 */
79 @Override
80 public Op parent() {
81 return parentOp;
82 }
83
84 /**
85 * Returns this body's parent operation.
86 *
87 * @return the body's parent operation.
88 */
89 public Op parentOp() {
90 return parentOp;
91 }
92
93 @Override
94 public List<Block> children() {
95 return blocks();
96 }
97
98 /**
99 * Returns body's blocks in reverse-postorder as an unmodifiable list.
100 *
101 * @return the body's blocks in reverse-postorder.
102 */
103 public List<Block> blocks() {
104 return Collections.unmodifiableList(blocks);
105 }
106
107 /**
108 * {@return the yield type of this body}
109 */
110 public TypeElement yieldType() {
111 return yieldType;
112 }
113
114 /**
115 * Returns the body's function type.
116 * <p>The function type is composed of the body's entry block parameter types and
117 * the body's yield type.
118 *
119 * @return the body type.
120 */
121 public FunctionType bodyType() {
122 Block entryBlock = entryBlock();
123 return FunctionType.functionType(yieldType, entryBlock.parameterTypes());
124 }
125
126 /**
127 * Finds the block in this body that is the ancestor of the given block.
128 *
129 * @param b the given block.
130 * @return the block in this body that is the ancestor of the given block,
131 * otherwise {@code null}
132 */
133 public Block findAncestorBlockInBody(Block b) {
134 Objects.requireNonNull(b);
135
136 while (b != null && b.parentBody() != this) {
137 b = b.parentBody().parentOp().parentBlock();
138 }
139
140 return b;
141 }
142
143 /**
144 * Returns this body's entry block.
145 * <p>
146 * The entry block is the first block in the sequence. No other blocks refer to it as a successor.
147 *
148 * @return the body's entry block
149 */
150 public Block entryBlock() {
151 return blocks.getFirst();
152 }
153
154 /**
155 * Returns a map of block to its immediate dominator.
156 *
157 * @return a map of block to its immediate dominator
158 */
159 public Map<Block, Block> immediateDominators() {
160 /*
161 * Compute dominators of blocks in a body.
162 * <p>
163 * https://www.cs.rice.edu/~keith/EMBED/dom.pdf
164 * A Simple, Fast Dominance Algorithm
165 * Keith D. Cooper, Timothy J. Harvey, and Ken Kennedy
166 */
167
168 if (idoms != null) {
169 return idoms;
170 }
171
172 Map<Block, Block> doms = idoms = new HashMap<>();
173 doms.put(entryBlock(), entryBlock());
174
175 // Blocks are sorted in reverse postorder
176 boolean changed;
177 do {
178 changed = false;
179 // Iterate through blocks in reverse postorder, except for entry block
180 for (int i = 1; i < blocks.size(); i++) {
181 Block b = blocks.get(i);
182
183 // Find first processed predecessor of b
184 Block newIdom = null;
185 for (Block p : b.predecessors()) {
186 if (doms.containsKey(p)) {
187 newIdom = p;
188 break;
189 }
190 }
191 assert b.predecessors().isEmpty() || newIdom != null : b;
192
193 // For all other predecessors, p, of b
194 for (Block p : b.predecessors()) {
195 if (p == newIdom) {
196 continue;
197 }
198
199 if (doms.containsKey(p)) {
200 // If already calculated
201 newIdom = intersect(doms, p, newIdom);
202 }
203 }
204
205 if (doms.get(b) != newIdom) {
206 doms.put(b, newIdom);
207 changed = true;
208 }
209 }
210 } while (changed);
211
212 return doms;
213 }
214
215 static Block intersect(Map<Block, Block> doms, Block b1, Block b2) {
216 while (b1 != b2) {
217 while (b1.index > b2.index) {
218 b1 = doms.get(b1);
219 }
220
221 while (b2.index > b1.index) {
222 b2 = doms.get(b2);
223 }
224 }
225
226 return b1;
227 }
228
229 /**
230 * Returns the dominance frontier of each block in the body.
231 * <p>
232 * The dominance frontier of block, {@code B} say, is the set of all blocks, {@code C} say,
233 * such that {@code B} dominates a predecessor of {@code C} but does not strictly dominate
234 * {@code C}.
235 *
236 * @return the dominance frontier of each block in the body
237 */
238 public Map<Block, Set<Block>> dominanceFrontier() {
239 // @@@ cache result?
240 Map<Block, Block> idoms = immediateDominators();
241 Map<Block, Set<Block>> df = new HashMap<>();
242
243 for (Block b : blocks) {
244 Set<Block> preds = b.predecessors();
245
246 if (preds.size() > 1) {
247 for (Block p : preds) {
248 Block runner = p;
249 while (runner != idoms.get(b)) {
250 df.computeIfAbsent(runner, k -> new LinkedHashSet<>()).add(b);
251 runner = idoms.get(runner);
252 }
253 }
254 }
255 }
256
257 return df;
258 }
259
260 /**
261 * Returns {@code true} if this body is dominated by the given body {@code dom}.
262 * <p>
263 * A body, {@code b} say, is dominated by {@code dom} if {@code b} is the same as {@code dom} or a descendant of
264 * {@code dom}. Specifically, if {@code b} and {@code dom} are not equal then {@code b} becomes the nearest ancestor
265 * body, the result of {@code b.parentOp().parentBlock().parentBody()}, and so on until either:
266 * {@code b == dom}, therefore {@code b} is dominated by {@code dom} and this method returns {@code true};
267 * or {@code b.parentOp().parentBlock() == null}, therefore {@code b} is <b>not</b> dominated
268 * by {@code dom} and this method returns {@code false}.
269 *
270 * @param dom the dominating body
271 * @return {@code true} if this body is dominated by the given body {@code dom}.
272 */
273 public boolean isDominatedBy(Body dom) {
274 return isDominatedBy(this, dom);
275 }
276
277 static boolean isDominatedBy(Body r, Body dom) {
278 while (r != dom) {
279 Block eb = r.parentOp().parentBlock();
280 if (eb == null) {
281 return false;
282 }
283
284 r = eb.parentBody();
285 }
286
287 return true;
288 }
289
290 /**
291 * Computes values captured by this body. A captured value is a value that dominates
292 * this body and is used by a descendant operation of this body.
293 * <p>
294 * The order of the captured values is first use encountered in depth
295 * first search of this body's descendant operations.
296 *
297 * @return the list of captured values, modifiable
298 */
299 public List<Value> capturedValues() {
300 Set<Value> cvs = new LinkedHashSet<>();
301
302 capturedValues(cvs, new ArrayDeque<>(), this);
303 return new ArrayList<>(cvs);
304 }
305
306 static void capturedValues(Set<Value> capturedValues, Deque<Body> bodyStack, Body body) {
307 bodyStack.push(body);
308
309 for (Block b : body.blocks()) {
310 for (Op op : b.ops()) {
311 for (Body childBody : op.bodies()) {
312 capturedValues(capturedValues, bodyStack, childBody);
313 }
314
315 for (Value a : op.operands()) {
316 if (!bodyStack.contains(a.declaringBlock().parentBody())) {
317 capturedValues.add(a);
318 }
319 }
320
321 for (Block.Reference s : op.successors()) {
322 for (Value a : s.arguments()) {
323 if (!bodyStack.contains(a.declaringBlock().parentBody())) {
324 capturedValues.add(a);
325 }
326 }
327 }
328 }
329 }
330
331 bodyStack.pop();
332 }
333
334 /**
335 * A builder of a body.
336 * <p>
337 * When the body builder is built any associated block builders are also considered built.
338 */
339 public final class Builder {
340 /**
341 * Creates a body build with a new context, and a copying transformer.
342 *
343 * @param ancestorBody the nearest ancestor body builder
344 * @param bodyType the body's function type
345 * @return the body builder
346 * @throws IllegalStateException if the ancestor body builder is built
347 * @see #of(Builder, FunctionType, CopyContext, OpTransformer)
348 */
349 public static Builder of(Builder ancestorBody, FunctionType bodyType) {
350 // @@@ Creation of CopyContext
351 return of(ancestorBody, bodyType, CopyContext.create(), OpTransformer.COPYING_TRANSFORMER);
352 }
353
354 /**
355 * Creates a body build with a copying transformer.
356 *
357 * @param ancestorBody the nearest ancestor body builder
358 * @param bodyType the body's function type
359 * @param cc the context
360 * @return the body builder
361 * @throws IllegalStateException if the ancestor body builder is built
362 * @see #of(Builder, FunctionType, CopyContext, OpTransformer)
363 */
364 public static Builder of(Builder ancestorBody, FunctionType bodyType, CopyContext cc) {
365 return of(ancestorBody, bodyType, cc, OpTransformer.COPYING_TRANSFORMER);
366 }
367
368 /**
369 * Creates a body builder.
370 * <p>
371 * Structurally, the created body builder must be built before its ancestor body builder (if non-null) is built,
372 * otherwise an {@code IllegalStateException} will occur.
373 * <p>
374 * A function type, referred to as the body type, defines the body's yield type and the initial sequence of
375 * entry block parameters.
376 * The body's yield type is the function type's return type.
377 * An entry block builder is created with appended block parameters corresponding, in order, to
378 * the function type's parameter types.
379 * <p>
380 * If the ancestor body is null then the created body builder is isolated and descendant operations may only
381 * refer to values declared within the created body builder. Otherwise, operations
382 * may refer to values declared in the ancestor body builders (outside the created body builder).
383 *
384 * @param ancestorBody the nearest ancestor body builder, may be null if isolated
385 * @param bodyType the body's function type
386 * @param cc the context
387 * @param ot the transformer
388 * @return the body builder
389 * @throws IllegalStateException if the ancestor body builder is built
390 * @see #of(Builder, FunctionType, CopyContext, OpTransformer)
391 */
392 public static Builder of(Builder ancestorBody, FunctionType bodyType,
393 CopyContext cc, OpTransformer ot) {
394 Body body = new Body(ancestorBody != null ? ancestorBody.target() : null, bodyType.returnType());
395 return body.new Builder(ancestorBody, bodyType, cc, ot);
396 }
397
398 // The ancestor body, may be null
399 final Builder ancestorBody;
400
401 // The entry block of this body, whose parameters are given by the body's function type
402 final Block.Builder entryBlock;
403
404 // When non-null contains one or more great-grandchildren
405 List<Builder> greatgrandchildren;
406
407 // True when built
408 boolean closed;
409
410 Builder(Builder ancestorBody, FunctionType bodyType,
411 CopyContext cc, OpTransformer ot) {
412 // Structural check
413 // The ancestor body should not be built before this body is created
414 if (ancestorBody != null) {
415 ancestorBody.check();
416 ancestorBody.addGreatgrandchild(this);
417 }
418
419 this.ancestorBody = ancestorBody;
420 // Create entry block from the body's function type
421 Block eb = Body.this.createBlock(bodyType.parameterTypes());
422 this.entryBlock = eb.new Builder(this, cc, ot);
423 }
424
425 void addGreatgrandchild(Builder greatgrandchild) {
426 var l = greatgrandchildren == null
427 ? (greatgrandchildren = new ArrayList<>()) : greatgrandchildren;
428 l.add(greatgrandchild);
429 }
430
431 /**
432 * Builds the body and its blocks, associating the body with a parent operation.
433 * <p>
434 * Structurally, any descendant body builders must be built before this body builder is built,
435 * otherwise an {@code IllegalStateException} will occur.
436 * <p>
437 * Blocks are sorted in reserve postorder.
438 * <p>
439 * Any unreferenced empty blocks are removed. An unreferenced block is a non-entry block with no predecessors.
440 *
441 * @param op the parent operation
442 * @return the build body
443 * @throws IllegalStateException if this body builder is built
444 * @throws IllegalStateException if any descendant body builders are not built
445 * @throws IllegalStateException if a block has no terminal operation, unless unreferenced and empty
446 */
447 // @@@ Validation
448 // e.g., every operand dominates the operation result (potentially expensive)
449 public Body build(Op op) {
450 // Structural check
451 // This body should not be closed
452 check();
453 closed = true;
454
455 // Structural check
456 // All great-grandchildren bodies should be built
457 if (greatgrandchildren != null) {
458 for (Builder greatgrandchild : greatgrandchildren) {
459 if (!greatgrandchild.closed) {
460 throw new IllegalStateException("Descendant body builder is not built");
461 }
462 }
463 }
464
465 Iterator<Block> i = blocks.iterator();
466 while (i.hasNext()) {
467 Block block = i.next();
468
469 // Structural check
470 // All referenced blocks should have a terminating operation as the last operation
471 if (block.ops.isEmpty()) {
472 if (block.isEntryBlock() || !block.predecessors.isEmpty()) {
473 throw noTerminatingOperation();
474 }
475
476 // Remove unreferenced empty block
477 assert !block.isEntryBlock() && block.predecessors.isEmpty();
478 i.remove();
479 } else if (!(block.ops.getLast() instanceof Op.Terminating)) {
480 throw noTerminatingOperation();
481 }
482 }
483
484 sortReversePostorder();
485
486 Body.this.parentOp = op;
487 return Body.this;
488 }
489
490 static IllegalStateException noTerminatingOperation() {
491 return new IllegalStateException("Block has no terminating operation as the last operation");
492 }
493
494 /**
495 * Returns the body builder's function type.
496 * <p>
497 * The function type is composed of the body builder's yield type, as the function type's return type, and the
498 * currently built entry block's parameter types, in order, as the function type's parameter types.
499 *
500 * @return the body builder's function type
501 */
502 public FunctionType bodyType() {
503 TypeElement returnType = Body.this.yieldType();
504 Block eb = Body.this.entryBlock();
505 return FunctionType.functionType(returnType, eb.parameterTypes());
506 }
507
508 /**
509 * {@return the body builder's nearest ancestor body builder}
510 */
511 public Builder ancestorBody() {
512 return ancestorBody;
513 }
514
515 /**
516 * {@return the body's entry block builder}
517 */
518 public Block.Builder entryBlock() {
519 return entryBlock;
520 }
521
522 @Override
523 public boolean equals(Object o) {
524 if (this == o) return true;
525 return o instanceof Builder that && Body.this == that.target();
526 }
527
528 @Override
529 public int hashCode() {
530 return Body.this.hashCode();
531 }
532
533 void check() {
534 if (closed) {
535 throw new IllegalStateException("Builder is closed");
536 }
537 }
538
539 Body target() {
540 return Body.this;
541 }
542
543 // Build new block in body
544 Block.Builder block(List<TypeElement> params, CopyContext cc, OpTransformer ot) {
545 check();
546 Block block = Body.this.createBlock(params);
547
548 return block.new Builder(this, cc, ot);
549 }
550 }
551
552 /**
553 * Copies the contents of this body.
554 *
555 * @param cc the copy context
556 * @return the builder of a body containing the copied body
557 * @see #transform(CopyContext, OpTransformer)
558 */
559 public Builder copy(CopyContext cc) {
560 return transform(cc, OpTransformer.COPYING_TRANSFORMER);
561 }
562
563 /**
564 * Transforms this body.
565 * <p>
566 * A new body builder is created with the same function type as this body.
567 * Then, this body is {@link Block.Builder#transformBody(Body, java.util.List, CopyContext, OpTransformer) transformed}
568 * into the body builder's entry block builder with the given copy context, operation transformer, and values
569 * that are the entry block's parameters.
570 *
571 * @param cc the copy context
572 * @param ot the operation transformer
573 * @return a body builder containing the transformed body
574 */
575 public Builder transform(CopyContext cc, OpTransformer ot) {
576 Block.Builder ancestorBlockBuilder = ancestorBody != null
577 ? cc.getBlock(ancestorBody.entryBlock()) : null;
578 Builder ancestorBodyBuilder = ancestorBlockBuilder != null
579 ? ancestorBlockBuilder.parentBody() : null;
580 Builder body = Builder.of(ancestorBodyBuilder,
581 // Create function type with just the return type and add parameters afterward
582 FunctionType.functionType(yieldType),
583 cc, ot);
584
585 for (Block.Parameter p : entryBlock().parameters()) {
586 body.entryBlock.parameter(p.type());
587 }
588
589 body.entryBlock.transformBody(this, body.entryBlock.parameters(), cc, ot);
590 return body;
591 }
592
593 // Sort blocks in reverse post order
594 // After sorting the following holds for a block
595 // block.parentBody().blocks().indexOf(block) == block.index()
596 private void sortReversePostorder() {
597 if (blocks.size() < 2) {
598 for (int i = 0; i < blocks.size(); i++) {
599 blocks.get(i).index = i;
600 }
601 return;
602 }
603
604 // Reset block indexes
605 // Also ensuring blocks with no predecessors occur last
606 for (Block b : blocks) {
607 b.index = Integer.MAX_VALUE;
608 }
609
610 Deque<Block> stack = new ArrayDeque<>();
611 stack.push(blocks.get(0));
612
613 // Postorder iteration
614 int index = blocks.size();
615 while (!stack.isEmpty()) {
616 Block n = stack.peek();
617 if (n.index == Integer.MIN_VALUE) {
618 // If n's successor has been processed then add n
619 stack.pop();
620 n.index = --index;
621 } else if (n.index < Integer.MAX_VALUE) {
622 // If n has already been processed then ignore
623 stack.pop();
624 } else {
625 // Mark before processing successors, a successor may refer back to n
626 n.index = Integer.MIN_VALUE;
627 for (Block.Reference s : n.successors()) {
628 if (s.target.index < Integer.MAX_VALUE) {
629 continue;
630 }
631
632 stack.push(s.target);
633 }
634 }
635 }
636
637 blocks.sort(Comparator.comparingInt(b -> b.index));
638 if (blocks.get(0).index > 0) {
639 // There are blocks with no predecessors
640 // Reassign indexes to their natural indexes, sort order is preserved
641 for (int i = 0; i < blocks.size(); i++) {
642 blocks.get(i).index = i;
643 }
644 }
645 }
646
647 // Modifying methods
648
649 // Create block
650 private Block createBlock(List<TypeElement> params) {
651 Block b = new Block(this, params);
652 blocks.add(b);
653 return b;
654 }
655 }