1 /*
2 * Copyright (c) 2024, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26 package jdk.incubator.code;
27
28 import jdk.incubator.code.dialect.core.CoreType;
29 import jdk.incubator.code.dialect.core.FunctionType;
30 import java.util.*;
31
32 /**
33 * A body containing a sequence of (basic) blocks.
34 * <p>
35 * The sequence of blocks form a graph topologically sorted in reserve postorder.
36 * The first block in the sequence is the entry block, and no other blocks refer to it as a successor.
37 * The last operation in a block, a terminating operation, may refer to other blocks in the sequence as successors,
38 * thus forming the graph. Otherwise, the last operation defines how the body passes control back to the parent
39 * operation, and in doing so may optionally yield a value.
40 * <p>
41 * A body has a 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 is passed to it, and describes the return type of values that are yielded when the body passes
45 * control back to its parent operation.
46 * <p>
47 * A body is built using a {@link Body.Builder body builder} that creates and exposes an entry block
48 * {@link Block.Builder builder} from which further blocks in the body may be
49 * {@link Block.Builder#block(TypeElement...) built}. When a body is {@link Body.Builder#build(Op) built} all blocks
50 * in the body are also built.
51 */
52 public final class Body implements CodeElement<Body, Block> {
53 // @Stable?
54 // Parent operation
55 // Non-null when body is built, and therefore child of an operation
56 Op parentOp;
57
58 // The ancestor body, when null the body is isolated and cannot refer to values defined outside
59 // When non-null and body is built, ancestorBody == parentOp.result.block.parentBody
60 final Body ancestorBody;
61
62 final TypeElement yieldType;
63
64 // Sorted in reverse postorder
65 final List<Block> blocks;
66
67 // Map of a block to its immediate dominator
68 // Computed lazily, null if not computed
69 Map<Block, Block> idoms;
70
71 /**
72 * Constructs a body, whose ancestor is the given ancestor body.
73 */
74 Body(Body ancestorBody, TypeElement yieldType) {
75 this.ancestorBody = ancestorBody;
76 this.yieldType = yieldType;
77 this.blocks = new ArrayList<>();
78 }
79
80 @Override
81 public String toString() {
82 return "body@" + Integer.toHexString(hashCode());
83 }
84
85 /**
86 * Returns this body's parent operation.
87 *
88 * @return the body's parent operation.
89 */
90 @Override
91 public Op parent() {
92 return parentOp;
93 }
94
95 @Override
96 public List<Block> children() {
97 return blocks();
98 }
99
100 /**
101 * Returns body's blocks in reverse-postorder as an unmodifiable list.
102 *
103 * @return the body's blocks in reverse-postorder.
104 */
105 public List<Block> blocks() {
106 return Collections.unmodifiableList(blocks);
107 }
108
109 /**
110 * {@return the yield type of this body}
111 */
112 public TypeElement yieldType() {
113 return yieldType;
114 }
115
116 /**
117 * Returns the body's function type.
118 * <p>The function type is composed of the body's entry block parameter types and
119 * the body's yield type.
120 *
121 * @return the body type.
122 */
123 public FunctionType bodyType() {
124 Block entryBlock = entryBlock();
125 return CoreType.functionType(yieldType, entryBlock.parameterTypes());
126 }
127
128 /**
129 * Returns this body's entry block.
130 * <p>
131 * The entry block is the first block in the sequence. No other blocks refer to it as a successor.
132 *
133 * @return the body's entry block
134 */
135 public Block entryBlock() {
136 return blocks.getFirst();
137 }
138
139 /**
140 * Returns a map of block to its immediate dominator.
141 *
142 * @return a map of block to its immediate dominator, as an unmodifiable map
143 */
144 public Map<Block, Block> immediateDominators() {
145 /*
146 * Compute dominators of blocks in a body.
147 * <p>
148 * https://www.cs.rice.edu/~keith/EMBED/dom.pdf
149 * A Simple, Fast Dominance Algorithm
150 * Keith D. Cooper, Timothy J. Harvey, and Ken Kennedy
151 */
152
153 if (idoms != null) {
154 return idoms;
155 }
156
157 // @@@ Compute the idoms as a block index mapping using int[]
158 // and wrap and a specific map implementation
159
160 Map<Block, Block> doms = new HashMap<>();
161 doms.put(entryBlock(), entryBlock());
162
163 // Blocks are sorted in reverse postorder
164 boolean changed;
165 do {
166 changed = false;
167 // Iterate through blocks in reverse postorder, except for entry block
168 for (int i = 1; i < blocks.size(); i++) {
169 Block b = blocks.get(i);
170
171 // Find first processed predecessor of b
172 Block newIdom = null;
173 for (Block p : b.predecessors()) {
174 if (doms.containsKey(p)) {
175 newIdom = p;
176 break;
177 }
178 }
179 assert b.predecessors().isEmpty() || newIdom != null : b;
180
181 // For all other predecessors, p, of b
182 for (Block p : b.predecessors()) {
183 if (p == newIdom) {
184 continue;
185 }
186
187 if (doms.containsKey(p)) {
188 // If already calculated
189 newIdom = intersect(doms, p, newIdom);
190 }
191 }
192
193 if (doms.get(b) != newIdom) {
194 doms.put(b, newIdom);
195 changed = true;
196 }
197 }
198 } while (changed);
199
200 return idoms = Collections.unmodifiableMap(doms);
201 }
202
203 static Block intersect(Map<Block, Block> doms, Block b1, Block b2) {
204 while (b1 != b2) {
205 while (b1.index > b2.index) {
206 b1 = doms.get(b1);
207 }
208
209 while (b2.index > b1.index) {
210 b2 = doms.get(b2);
211 }
212 }
213
214 return b1;
215 }
216
217 /**
218 * Returns the dominance frontier of each block in the body.
219 * <p>
220 * The dominance frontier of block, {@code B} say, is the set of all blocks, {@code C} say,
221 * such that {@code B} dominates a predecessor of {@code C} but does not strictly dominate
222 * {@code C}.
223 *
224 * @return the dominance frontier of each block in the body, as a modifiable map
225 */
226 public Map<Block, Set<Block>> dominanceFrontier() {
227 // @@@ cache result?
228 Map<Block, Block> idoms = immediateDominators();
229 Map<Block, Set<Block>> df = new HashMap<>();
230
231 for (Block b : blocks) {
232 Set<Block> preds = b.predecessors();
233
234 if (preds.size() > 1) {
235 for (Block p : preds) {
236 Block runner = p;
237 while (runner != idoms.get(b)) {
238 df.computeIfAbsent(runner, _ -> new LinkedHashSet<>()).add(b);
239 runner = idoms.get(runner);
240 }
241 }
242 }
243 }
244
245 return df;
246 }
247
248 /**
249 * A synthetic block representing the post dominator of all blocks
250 * when two or more blocks in the body have no successors.
251 * <p>
252 * Computing the immediate post dominators requires a single exit point,
253 * one block that has no successors. When there are two or more blocks
254 * with no successors then this block represents the immediate post
255 * dominator of those blocks
256 */
257 public static final Block IPDOM_EXIT;
258 static {
259 IPDOM_EXIT = new Block(null);
260 IPDOM_EXIT.index = Integer.MAX_VALUE;
261 }
262
263 /**
264 * Returns a map of block to its immediate post dominator.
265 * <p>
266 * If there are two or more blocks with no successors then
267 * a single exit point is synthesized using the {@link #IPDOM_EXIT}
268 * block, which represents the immediate post dominator of those blocks.
269 *
270 * @return a map of block to its immediate post dominator, as an unmodifiable map
271 */
272 public Map<Block, Block> immediatePostDominators() {
273 Map<Block, Block> pdoms = new HashMap<>();
274
275 // If there are multiple exit blocks (those with zero successors)
276 // then use the block IPDOM_EXIT that is the synthetic successor of
277 // the exit blocks
278 boolean nSuccessors = blocks.stream().filter(b -> b.successors().isEmpty()).count() > 1;
279
280 if (nSuccessors) {
281 pdoms.put(IPDOM_EXIT, IPDOM_EXIT);
282 } else {
283 Block exit = blocks.getLast();
284 assert blocks.stream().filter(b -> b.successors().isEmpty()).findFirst().orElseThrow() == exit;
285 pdoms.put(exit, exit);
286 }
287
288 // Blocks are sorted in reverse postorder
289 boolean changed;
290 do {
291 changed = false;
292 // Iterate in reverse through blocks in reverse postorder, except for exit block
293 for (int i = blocks.size() - (nSuccessors ? 1 : 2); i >= 0; i--) {
294 Block b = blocks.get(i);
295
296 // Find first processed successor of b
297 Block newIpdom = null;
298 Collection<Block> targets = b.successorTargets();
299 for (Block s : nSuccessors && targets.isEmpty() ? List.of(IPDOM_EXIT) : targets) {
300 if (pdoms.containsKey(s)) {
301 newIpdom = s;
302 break;
303 }
304 }
305
306 if (newIpdom == null) {
307 // newIpdom can be null if all successors reference
308 // prior blocks (back branch) yet to be encountered
309 // in the dominator treee
310 continue;
311 }
312
313 // For all other successors, s, of b
314 for (Block s : b.successorTargets()) {
315 if (s == newIpdom) {
316 continue;
317 }
318
319 if (pdoms.containsKey(s)) {
320 // If already calculated
321 newIpdom = postIntersect(pdoms, s, newIpdom, blocks.size());
322 }
323 }
324
325 if (pdoms.get(b) != newIpdom) {
326 pdoms.put(b, newIpdom);
327 changed = true;
328 }
329 }
330 } while (changed);
331
332 return Collections.unmodifiableMap(pdoms);
333 }
334
335 static Block postIntersect(Map<Block, Block> doms, Block b1, Block b2, int exitIndex) {
336 while (b1 != b2) {
337 while (b1.index() < b2.index()) {
338 b1 = doms.get(b1);
339 }
340
341 while (b2.index() < b1.index()) {
342 b2 = doms.get(b2);
343 }
344 }
345
346 return b1;
347 }
348
349 /**
350 * Returns the post dominance frontier of each block in the body.
351 * <p>
352 * The post dominance frontier of block, {@code B} say, is the set of all blocks, {@code C} say,
353 * such that {@code B} post dominates a successor of {@code C} but does not strictly post dominate
354 * {@code C}.
355 *
356 * @return the post dominance frontier of each block in the body, as a modifiable map
357 */
358 public Map<Block, Set<Block>> postDominanceFrontier() {
359 // @@@ cache result?
360 Map<Block, Block> idoms = immediatePostDominators();
361 Map<Block, Set<Block>> df = new HashMap<>();
362
363 for (Block b : blocks) {
364 Set<Block> succs = b.successorTargets();
365
366 if (succs.size() > 1) {
367 for (Block s : succs) {
368 Block runner = s;
369 while (runner != idoms.get(b)) {
370 df.computeIfAbsent(runner, _ -> new LinkedHashSet<>()).add(b);
371 runner = idoms.get(runner);
372 }
373 }
374 }
375 }
376
377 return df;
378 }
379
380 /**
381 * Returns {@code true} if this body is dominated by the given body {@code dom}.
382 * <p>
383 * A body, {@code b} say, is dominated by {@code dom} if {@code b} is the same as {@code dom} or a descendant of
384 * {@code dom}. Specifically, if {@code b} and {@code dom} are not equal then {@code b} becomes the nearest ancestor
385 * body, the result of {@code b.parentOp().parentBlock().parentBody()}, and so on until either:
386 * {@code b == dom}, therefore {@code b} is dominated by {@code dom} and this method returns {@code true};
387 * or {@code b.parentOp().parentBlock() == null}, therefore {@code b} is <b>not</b> dominated
388 * by {@code dom} and this method returns {@code false}.
389 *
390 * @param dom the dominating body
391 * @return {@code true} if this body is dominated by the given body {@code dom}.
392 */
393 public boolean isDominatedBy(Body dom) {
394 return isDominatedBy(this, dom);
395 }
396
397 static boolean isDominatedBy(Body r, Body dom) {
398 while (r != dom) {
399 r = r.ancestorBody();
400 if (r == null) {
401 return false;
402 }
403 }
404
405 return true;
406 }
407
408 /**
409 * Computes values captured by this body. A captured value is a value that is used
410 * but not declared by any descendant block or operation of this body.
411 * <p>
412 * The order of the captured values is first use encountered in depth
413 * first search of this body's descendant operations.
414 *
415 * @return the list of captured values, modifiable
416 */
417 public List<Value> capturedValues() {
418 Set<Value> cvs = new LinkedHashSet<>();
419
420 capturedValues(cvs, new ArrayDeque<>(), this);
421 return new ArrayList<>(cvs);
422 }
423
424 static void capturedValues(Set<Value> capturedValues, Deque<Body> bodyStack, Body body) {
425 bodyStack.push(body);
426
427 for (Block b : body.blocks()) {
428 for (Op op : b.ops()) {
429 for (Body childBody : op.bodies()) {
430 capturedValues(capturedValues, bodyStack, childBody);
431 }
432
433 for (Value a : op.operands()) {
434 if (!bodyStack.contains(a.declaringBlock().ancestorBody())) {
435 capturedValues.add(a);
436 }
437 }
438
439 for (Block.Reference s : op.successors()) {
440 for (Value a : s.arguments()) {
441 if (!bodyStack.contains(a.declaringBlock().ancestorBody())) {
442 capturedValues.add(a);
443 }
444 }
445 }
446 }
447 }
448
449 bodyStack.pop();
450 }
451
452 /**
453 * A builder of a body.
454 * <p>
455 * When the body builder is {@link Body.Builder#build(Op) built} all associated {@link Block.Builder block builders}
456 * are also built and their blocks become children of the body.
457 */
458 public final class Builder {
459 /**
460 * Creates a body build with a new context, and a copying transformer.
461 *
462 * @param ancestorBody the nearest ancestor body builder, may be null if isolated
463 * @param bodyType the body's function type
464 * @return the body builder
465 * @throws IllegalStateException if the ancestor body builder is built
466 * @see #of(Builder, FunctionType, CodeContext, CodeTransformer)
467 */
468 public static Builder of(Builder ancestorBody, FunctionType bodyType) {
469 // @@@ Creation of CodeContext
470 return of(ancestorBody, bodyType, CodeContext.create(), CodeTransformer.COPYING_TRANSFORMER);
471 }
472
473 /**
474 * Creates a body build with a copying transformer.
475 *
476 * @param ancestorBody the nearest ancestor body builder, may be null if isolated
477 * @param bodyType the body's function type
478 * @param cc the context
479 * @return the body builder
480 * @throws IllegalStateException if the ancestor body builder is built
481 * @see #of(Builder, FunctionType, CodeContext, CodeTransformer)
482 */
483 public static Builder of(Builder ancestorBody, FunctionType bodyType, CodeContext cc) {
484 return of(ancestorBody, bodyType, cc, CodeTransformer.COPYING_TRANSFORMER);
485 }
486
487 /**
488 * Creates a body builder.
489 * <p>
490 * Structurally, the created body builder must be built before its ancestor body builder (if non-null) is built,
491 * otherwise an {@code IllegalStateException} will occur.
492 * <p>
493 * A function type, referred to as the body type, defines the body's yield type and the initial sequence of
494 * entry block parameters.
495 * The body's yield type is the function type's return type.
496 * An entry block builder is created with appended block parameters corresponding, in order, to
497 * the function type's parameter types.
498 * <p>
499 * If the ancestor body is null then the created body builder is isolated and descendant operations may only
500 * use values declared within the created body builder. Otherwise, operations
501 * may use reachable values declared in the ancestor body builders (outside the created body builder).
502 *
503 * @param ancestorBody the nearest ancestor body builder, may be null if isolated
504 * @param bodyType the body's function type
505 * @param cc the context
506 * @param ot the transformer
507 * @return the body builder
508 * @throws IllegalStateException if the ancestor body builder is built
509 * @see #of(Builder, FunctionType, CodeContext, CodeTransformer)
510 */
511 public static Builder of(Builder ancestorBody, FunctionType bodyType,
512 CodeContext cc, CodeTransformer ot) {
513 Body body = new Body(ancestorBody != null ? ancestorBody.target() : null, bodyType.returnType());
514 return body.new Builder(ancestorBody, bodyType, cc, ot);
515 }
516
517 // The ancestor body, may be null
518 final Builder ancestorBody;
519
520 // The entry block of this body, whose parameters are given by the body's function type
521 final Block.Builder entryBlock;
522
523 // When non-null contains one or more great-grandchildren
524 List<Builder> greatgrandchildren;
525
526 // True when built
527 boolean closed;
528
529 Builder(Builder ancestorBody, FunctionType bodyType,
530 CodeContext cc, CodeTransformer ot) {
531 // Structural check
532 // The ancestor body should not be built before this body is created
533 if (ancestorBody != null) {
534 ancestorBody.check();
535 ancestorBody.addGreatgrandchild(this);
536 }
537
538 this.ancestorBody = ancestorBody;
539 // Create entry block from the body's function type
540 Block eb = Body.this.createBlock(bodyType.parameterTypes());
541 this.entryBlock = eb.new Builder(this, cc, ot);
542 }
543
544 void addGreatgrandchild(Builder greatgrandchild) {
545 var l = greatgrandchildren == null
546 ? (greatgrandchildren = new ArrayList<>()) : greatgrandchildren;
547 l.add(greatgrandchild);
548 }
549
550 /**
551 * Builds the body and its child blocks, associating the body with a parent operation.
552 * <p>
553 * Structurally, any descendant body builders must be built before this body is built,
554 * otherwise an {@code IllegalStateException} will occur.
555 * <p>
556 * Any unreferenced empty blocks are ignored and do not become children of the body. An unreferenced block is
557 * a non-entry block with no predecessors.
558 *
559 * @param op the parent operation
560 * @return the build body
561 * @throws IllegalStateException if this body builder is built
562 * @throws IllegalStateException if any descendant body builders are not built
563 * @throws IllegalStateException if a block has no terminal operation, unless unreferenced and empty
564 */
565 // @@@ Check every operand dominates the operation result.
566 // An operation in block B that uses a value declared in block B requires no special checks, since an
567 // operation result does not exist until an operation is appended to a block, and B's parameters always
568 // occur before any of its operations.
569 // Similarly, when an operation uses a value declared in an ancestor no special checks are required due to
570 // structural checks and reachability checks when building.
571 // Therefore, a body with only one entry block requires no special checks when building.
572 // A body with two or more blocks requires dominance checks. An operation in block C that uses a value
573 // declared in block B, where C and B are siblings, requires that B dominates C.
574 // Since blocks are already sorted in reverse postorder the work to compute the immediate dominator map
575 // is incremental and can it be represented efficiently as an integer array of block indexes.
576 public Body build(Op op) {
577 // Structural check
578 // This body should not be closed
579 check();
580 closed = true;
581
582 // Structural check
583 // All great-grandchildren bodies should be built
584 if (greatgrandchildren != null) {
585 for (Builder greatgrandchild : greatgrandchildren) {
586 if (!greatgrandchild.closed) {
587 throw new IllegalStateException("Descendant body builder is not built");
588 }
589 }
590 }
591
592 Iterator<Block> i = blocks.iterator();
593 while (i.hasNext()) {
594 Block block = i.next();
595
596 // Structural check
597 // All referenced blocks should have a terminating operation as the last operation
598 if (block.ops.isEmpty()) {
599 if (block.isEntryBlock() || !block.predecessors.isEmpty()) {
600 throw noTerminatingOperation();
601 }
602
603 // Remove unreferenced empty block
604 assert !block.isEntryBlock() && block.predecessors.isEmpty();
605 i.remove();
606 } else if (!(block.ops.getLast() instanceof Op.Terminating)) {
607 throw noTerminatingOperation();
608 }
609 }
610
611 sortReversePostorder();
612
613 Body.this.parentOp = op;
614 return Body.this;
615 }
616
617 static IllegalStateException noTerminatingOperation() {
618 return new IllegalStateException("Block has no terminating operation as the last operation");
619 }
620
621 /**
622 * Returns the body builder's function type.
623 * <p>
624 * The function type is composed of the body builder's yield type, as the function type's return type, and the
625 * currently built entry block's parameter types, in order, as the function type's parameter types.
626 *
627 * @return the body builder's function type
628 */
629 public FunctionType bodyType() {
630 TypeElement returnType = Body.this.yieldType();
631 Block eb = Body.this.entryBlock();
632 return CoreType.functionType(returnType, eb.parameterTypes());
633 }
634
635 /**
636 * {@return the body builder's nearest ancestor body builder}
637 */
638 public Builder ancestorBody() {
639 return ancestorBody;
640 }
641
642 /**
643 * {@return the body's entry block builder}
644 */
645 public Block.Builder entryBlock() {
646 return entryBlock;
647 }
648
649 @Override
650 public boolean equals(Object o) {
651 if (this == o) return true;
652 return o instanceof Builder that && Body.this == that.target();
653 }
654
655 @Override
656 public int hashCode() {
657 return Body.this.hashCode();
658 }
659
660 void check() {
661 if (closed) {
662 throw new IllegalStateException("Builder is closed");
663 }
664 }
665
666 Body target() {
667 return Body.this;
668 }
669
670 // Build new block in body
671 Block.Builder block(List<TypeElement> params, CodeContext cc, CodeTransformer ot) {
672 check();
673 Block block = Body.this.createBlock(params);
674
675 return block.new Builder(this, cc, ot);
676 }
677 }
678
679 /**
680 * Copies the contents of this body.
681 *
682 * @param cc the code context
683 * @return the builder of a body containing the copied body
684 * @see #transform(CodeContext, CodeTransformer)
685 */
686 public Builder copy(CodeContext cc) {
687 return transform(cc, CodeTransformer.COPYING_TRANSFORMER);
688 }
689
690 /**
691 * Transforms this body.
692 * <p>
693 * A new body builder is created with the same function type as this body.
694 * Then, this body is {@link Block.Builder#body(Body, java.util.List, CodeContext, CodeTransformer) transformed}
695 * into the body builder's entry block builder with the given code context, operation transformer, and arguments
696 * that are the entry block builder's parameters.
697 *
698 * @param cc the code context
699 * @param ot the operation transformer
700 * @return a body builder containing the transformed body
701 */
702 public Builder transform(CodeContext cc, CodeTransformer ot) {
703 Block.Builder ancestorBlockBuilder = ancestorBody != null
704 ? cc.getBlock(ancestorBody.entryBlock()) : null;
705 Builder ancestorBodyBuilder = ancestorBlockBuilder != null
706 ? ancestorBlockBuilder.parentBody() : null;
707 Builder bodyBuilder = Builder.of(ancestorBodyBuilder,
708 bodyType(),
709 // Create child context for mapped code items contained in this body
710 // thereby not polluting the given context
711 CodeContext.create(cc), ot);
712
713 // Transform body starting from the entry block builder
714 ot.acceptBody(bodyBuilder.entryBlock, this, bodyBuilder.entryBlock.parameters());
715 return bodyBuilder;
716 }
717
718 // Sort blocks in reverse post order
719 // After sorting the following holds for a block
720 // block.parentBody().blocks().indexOf(block) == block.index()
721 private void sortReversePostorder() {
722 if (blocks.size() < 2) {
723 for (int i = 0; i < blocks.size(); i++) {
724 blocks.get(i).index = i;
725 }
726 return;
727 }
728
729 // Reset block indexes
730 // Also ensuring blocks with no predecessors occur last
731 for (Block b : blocks) {
732 b.index = Integer.MAX_VALUE;
733 }
734
735 Deque<Block> stack = new ArrayDeque<>();
736 stack.push(blocks.get(0));
737
738 // Postorder iteration
739 int index = blocks.size();
740 while (!stack.isEmpty()) {
741 Block n = stack.peek();
742 if (n.index == Integer.MIN_VALUE) {
743 // If n's successor has been processed then add n
744 stack.pop();
745 n.index = --index;
746 } else if (n.index < Integer.MAX_VALUE) {
747 // If n has already been processed then ignore
748 stack.pop();
749 } else {
750 // Mark before processing successors, a successor may refer back to n
751 n.index = Integer.MIN_VALUE;
752 for (Block.Reference s : n.successors()) {
753 if (s.target.index < Integer.MAX_VALUE) {
754 continue;
755 }
756
757 stack.push(s.target);
758 }
759 }
760 }
761
762 blocks.sort(Comparator.comparingInt(b -> b.index));
763 if (blocks.get(0).index > 0) {
764 // There are blocks with no predecessors
765 // Reassign indexes to their natural indexes, sort order is preserved
766 for (int i = 0; i < blocks.size(); i++) {
767 blocks.get(i).index = i;
768 }
769 }
770 }
771
772 // Modifying methods
773
774 // Create block
775 private Block createBlock(List<TypeElement> params) {
776 Block b = new Block(this, params);
777 blocks.add(b);
778 return b;
779 }
780 }