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