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