1 /*
2 * Copyright (c) 2024, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26 package jdk.incubator.code;
27
28 import jdk.incubator.code.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, as an unmodifiable map
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 // @@@ 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(), entryBlock());
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 b.predecessors().isEmpty() || 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 idoms = 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 * Returns {@code true} if this body is dominated by the given body {@code dom}.
265 * <p>
266 * A body, {@code b} say, is dominated by {@code dom} if {@code b} is the same as {@code dom} or a descendant of
267 * {@code dom}. Specifically, if {@code b} and {@code dom} are not equal then {@code b} becomes the nearest ancestor
268 * body, the result of {@code b.parentOp().parentBlock().parentBody()}, and so on until either:
269 * {@code b == dom}, therefore {@code b} is dominated by {@code dom} and this method returns {@code true};
270 * or {@code b.parentOp().parentBlock() == null}, therefore {@code b} is <b>not</b> dominated
271 * by {@code dom} and this method returns {@code false}.
272 *
273 * @param dom the dominating body
274 * @return {@code true} if this body is dominated by the given body {@code dom}.
275 */
276 public boolean isDominatedBy(Body dom) {
277 return isDominatedBy(this, dom);
278 }
279
280 static boolean isDominatedBy(Body r, Body dom) {
281 while (r != dom) {
282 Block eb = r.parentOp().parentBlock();
283 if (eb == null) {
284 return false;
285 }
286
287 r = eb.parentBody();
288 }
289
290 return true;
291 }
292
293 /**
294 * Computes values captured by this body. A captured value is a value that dominates
295 * this body and is used by a descendant operation of this body.
296 * <p>
297 * The order of the captured values is first use encountered in depth
298 * first search of this body's descendant operations.
299 *
300 * @return the list of captured values, modifiable
301 */
302 public List<Value> capturedValues() {
303 Set<Value> cvs = new LinkedHashSet<>();
304
305 capturedValues(cvs, new ArrayDeque<>(), this);
306 return new ArrayList<>(cvs);
307 }
308
309 static void capturedValues(Set<Value> capturedValues, Deque<Body> bodyStack, Body body) {
310 bodyStack.push(body);
311
312 for (Block b : body.blocks()) {
313 for (Op op : b.ops()) {
314 for (Body childBody : op.bodies()) {
315 capturedValues(capturedValues, bodyStack, childBody);
316 }
317
318 for (Value a : op.operands()) {
319 if (!bodyStack.contains(a.declaringBlock().parentBody())) {
320 capturedValues.add(a);
321 }
322 }
323
324 for (Block.Reference s : op.successors()) {
325 for (Value a : s.arguments()) {
326 if (!bodyStack.contains(a.declaringBlock().parentBody())) {
327 capturedValues.add(a);
328 }
329 }
330 }
331 }
332 }
333
334 bodyStack.pop();
335 }
336
337 /**
338 * A builder of a body.
339 * <p>
340 * When the body builder is built any associated block builders are also considered built.
341 */
342 public final class Builder {
343 /**
344 * Creates a body build with a new context, and a copying transformer.
345 *
346 * @param ancestorBody the nearest ancestor body builder
347 * @param bodyType the body's function type
348 * @return the body builder
349 * @throws IllegalStateException if the ancestor body builder is built
350 * @see #of(Builder, FunctionType, CopyContext, OpTransformer)
351 */
352 public static Builder of(Builder ancestorBody, FunctionType bodyType) {
353 // @@@ Creation of CopyContext
354 return of(ancestorBody, bodyType, CopyContext.create(), OpTransformer.COPYING_TRANSFORMER);
355 }
356
357 /**
358 * Creates a body build with a copying transformer.
359 *
360 * @param ancestorBody the nearest ancestor body builder
361 * @param bodyType the body's function type
362 * @param cc the context
363 * @return the body builder
364 * @throws IllegalStateException if the ancestor body builder is built
365 * @see #of(Builder, FunctionType, CopyContext, OpTransformer)
366 */
367 public static Builder of(Builder ancestorBody, FunctionType bodyType, CopyContext cc) {
368 return of(ancestorBody, bodyType, cc, OpTransformer.COPYING_TRANSFORMER);
369 }
370
371 /**
372 * Creates a body builder.
373 * <p>
374 * Structurally, the created body builder must be built before its ancestor body builder (if non-null) is built,
375 * otherwise an {@code IllegalStateException} will occur.
376 * <p>
377 * A function type, referred to as the body type, defines the body's yield type and the initial sequence of
378 * entry block parameters.
379 * The body's yield type is the function type's return type.
380 * An entry block builder is created with appended block parameters corresponding, in order, to
381 * the function type's parameter types.
382 * <p>
383 * If the ancestor body is null then the created body builder is isolated and descendant operations may only
384 * refer to values declared within the created body builder. Otherwise, operations
385 * may refer to values declared in the ancestor body builders (outside the created body builder).
386 *
387 * @param ancestorBody the nearest ancestor body builder, may be null if isolated
388 * @param bodyType the body's function type
389 * @param cc the context
390 * @param ot the transformer
391 * @return the body builder
392 * @throws IllegalStateException if the ancestor body builder is built
393 * @see #of(Builder, FunctionType, CopyContext, OpTransformer)
394 */
395 public static Builder of(Builder ancestorBody, FunctionType bodyType,
396 CopyContext cc, OpTransformer ot) {
397 Body body = new Body(ancestorBody != null ? ancestorBody.target() : null, bodyType.returnType());
398 return body.new Builder(ancestorBody, bodyType, cc, ot);
399 }
400
401 // The ancestor body, may be null
402 final Builder ancestorBody;
403
404 // The entry block of this body, whose parameters are given by the body's function type
405 final Block.Builder entryBlock;
406
407 // When non-null contains one or more great-grandchildren
408 List<Builder> greatgrandchildren;
409
410 // True when built
411 boolean closed;
412
413 Builder(Builder ancestorBody, FunctionType bodyType,
414 CopyContext cc, OpTransformer ot) {
415 // Structural check
416 // The ancestor body should not be built before this body is created
417 if (ancestorBody != null) {
418 ancestorBody.check();
419 ancestorBody.addGreatgrandchild(this);
420 }
421
422 this.ancestorBody = ancestorBody;
423 // Create entry block from the body's function type
424 Block eb = Body.this.createBlock(bodyType.parameterTypes());
425 this.entryBlock = eb.new Builder(this, cc, ot);
426 }
427
428 void addGreatgrandchild(Builder greatgrandchild) {
429 var l = greatgrandchildren == null
430 ? (greatgrandchildren = new ArrayList<>()) : greatgrandchildren;
431 l.add(greatgrandchild);
432 }
433
434 /**
435 * Builds the body and its blocks, associating the body with a parent operation.
436 * <p>
437 * Structurally, any descendant body builders must be built before this body builder is built,
438 * otherwise an {@code IllegalStateException} will occur.
439 * <p>
440 * Blocks are sorted in reserve postorder.
441 * <p>
442 * Any unreferenced empty blocks are removed. An unreferenced block is a non-entry block with no predecessors.
443 *
444 * @param op the parent operation
445 * @return the build body
446 * @throws IllegalStateException if this body builder is built
447 * @throws IllegalStateException if any descendant body builders are not built
448 * @throws IllegalStateException if a block has no terminal operation, unless unreferenced and empty
449 */
450 // @@@ Validation
451 // e.g., every operand dominates the operation result (potentially expensive)
452 public Body build(Op op) {
453 // Structural check
454 // This body should not be closed
455 check();
456 closed = true;
457
458 // Structural check
459 // All great-grandchildren bodies should be built
460 if (greatgrandchildren != null) {
461 for (Builder greatgrandchild : greatgrandchildren) {
462 if (!greatgrandchild.closed) {
463 throw new IllegalStateException("Descendant body builder is not built");
464 }
465 }
466 }
467
468 Iterator<Block> i = blocks.iterator();
469 while (i.hasNext()) {
470 Block block = i.next();
471
472 // Structural check
473 // All referenced blocks should have a terminating operation as the last operation
474 if (block.ops.isEmpty()) {
475 if (block.isEntryBlock() || !block.predecessors.isEmpty()) {
476 throw noTerminatingOperation();
477 }
478
479 // Remove unreferenced empty block
480 assert !block.isEntryBlock() && block.predecessors.isEmpty();
481 i.remove();
482 } else if (!(block.ops.getLast() instanceof Op.Terminating)) {
483 throw noTerminatingOperation();
484 }
485 }
486
487 sortReversePostorder();
488
489 Body.this.parentOp = op;
490 return Body.this;
491 }
492
493 static IllegalStateException noTerminatingOperation() {
494 return new IllegalStateException("Block has no terminating operation as the last operation");
495 }
496
497 /**
498 * Returns the body builder's function type.
499 * <p>
500 * The function type is composed of the body builder's yield type, as the function type's return type, and the
501 * currently built entry block's parameter types, in order, as the function type's parameter types.
502 *
503 * @return the body builder's function type
504 */
505 public FunctionType bodyType() {
506 TypeElement returnType = Body.this.yieldType();
507 Block eb = Body.this.entryBlock();
508 return FunctionType.functionType(returnType, eb.parameterTypes());
509 }
510
511 /**
512 * {@return the body builder's nearest ancestor body builder}
513 */
514 public Builder ancestorBody() {
515 return ancestorBody;
516 }
517
518 /**
519 * {@return the body's entry block builder}
520 */
521 public Block.Builder entryBlock() {
522 return entryBlock;
523 }
524
525 @Override
526 public boolean equals(Object o) {
527 if (this == o) return true;
528 return o instanceof Builder that && Body.this == that.target();
529 }
530
531 @Override
532 public int hashCode() {
533 return Body.this.hashCode();
534 }
535
536 void check() {
537 if (closed) {
538 throw new IllegalStateException("Builder is closed");
539 }
540 }
541
542 Body target() {
543 return Body.this;
544 }
545
546 // Build new block in body
547 Block.Builder block(List<TypeElement> params, CopyContext cc, OpTransformer ot) {
548 check();
549 Block block = Body.this.createBlock(params);
550
551 return block.new Builder(this, cc, ot);
552 }
553 }
554
555 /**
556 * Copies the contents of this body.
557 *
558 * @param cc the copy context
559 * @return the builder of a body containing the copied body
560 * @see #transform(CopyContext, OpTransformer)
561 */
562 public Builder copy(CopyContext cc) {
563 return transform(cc, OpTransformer.COPYING_TRANSFORMER);
564 }
565
566 /**
567 * Transforms this body.
568 * <p>
569 * A new body builder is created with the same function type as this body.
570 * Then, this body is {@link Block.Builder#transformBody(Body, java.util.List, CopyContext, OpTransformer) transformed}
571 * into the body builder's entry block builder with the given copy context, operation transformer, and values
572 * that are the entry block's parameters.
573 *
574 * @param cc the copy context
575 * @param ot the operation transformer
576 * @return a body builder containing the transformed body
577 */
578 public Builder transform(CopyContext cc, OpTransformer ot) {
579 Block.Builder ancestorBlockBuilder = ancestorBody != null
580 ? cc.getBlock(ancestorBody.entryBlock()) : null;
581 Builder ancestorBodyBuilder = ancestorBlockBuilder != null
582 ? ancestorBlockBuilder.parentBody() : null;
583 Builder body = Builder.of(ancestorBodyBuilder,
584 // Create function type with just the return type and add parameters afterward
585 FunctionType.functionType(yieldType),
586 cc, ot);
587
588 for (Block.Parameter p : entryBlock().parameters()) {
589 body.entryBlock.parameter(p.type());
590 }
591
592 body.entryBlock.transformBody(this, body.entryBlock.parameters(), cc, ot);
593 return body;
594 }
595
596 // Sort blocks in reverse post order
597 // After sorting the following holds for a block
598 // block.parentBody().blocks().indexOf(block) == block.index()
599 private void sortReversePostorder() {
600 if (blocks.size() < 2) {
601 for (int i = 0; i < blocks.size(); i++) {
602 blocks.get(i).index = i;
603 }
604 return;
605 }
606
607 // Reset block indexes
608 // Also ensuring blocks with no predecessors occur last
609 for (Block b : blocks) {
610 b.index = Integer.MAX_VALUE;
611 }
612
613 Deque<Block> stack = new ArrayDeque<>();
614 stack.push(blocks.get(0));
615
616 // Postorder iteration
617 int index = blocks.size();
618 while (!stack.isEmpty()) {
619 Block n = stack.peek();
620 if (n.index == Integer.MIN_VALUE) {
621 // If n's successor has been processed then add n
622 stack.pop();
623 n.index = --index;
624 } else if (n.index < Integer.MAX_VALUE) {
625 // If n has already been processed then ignore
626 stack.pop();
627 } else {
628 // Mark before processing successors, a successor may refer back to n
629 n.index = Integer.MIN_VALUE;
630 for (Block.Reference s : n.successors()) {
631 if (s.target.index < Integer.MAX_VALUE) {
632 continue;
633 }
634
635 stack.push(s.target);
636 }
637 }
638 }
639
640 blocks.sort(Comparator.comparingInt(b -> b.index));
641 if (blocks.get(0).index > 0) {
642 // There are blocks with no predecessors
643 // Reassign indexes to their natural indexes, sort order is preserved
644 for (int i = 0; i < blocks.size(); i++) {
645 blocks.get(i).index = i;
646 }
647 }
648 }
649
650 // Modifying methods
651
652 // Create block
653 private Block createBlock(List<TypeElement> params) {
654 Block b = new Block(this, params);
655 blocks.add(b);
656 return b;
657 }
658 }