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