1 /*
2 * Copyright (c) 2025, 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.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
23
24 import jdk.incubator.code.Block;
25 import jdk.incubator.code.Body;
26
27 import java.util.*;
28
29 public class LoopAnalyzer {
30 public record Loop(Block header, List<Block> latches, Set<Block> body, List<LoopExit> exits) {
31 }
32
33 public record LoopExit(Block exit, Block target) {
34 }
35
36 public static Optional<Loop> isLoop(Block header) {
37 List<Block> latches = header.predecessors()
38 .stream().filter(p -> p.isDominatedBy(header))
39 .toList();
40 if (latches.isEmpty()) {
41 return Optional.empty();
42 }
43
44 Set<Block> body = new HashSet<>();
45 for (Block latch : latches) {
46 loopBody(body, header, latch);
47 }
48 List<LoopExit> exits = loopExits(body);
49 return Optional.of(new Loop(header, latches, body, exits));
50 }
51
52 static Set<Block> naturalLoopBody(Set<Block> loopBody, Block header, Block latch) {
53 Deque<Block> stack = new ArrayDeque<>();
54 stack.push(latch);
55 Block node;
56 // Backward depth first search from latch to header
57 while (!stack.isEmpty() && (node = stack.pop()) != header) {
58 if (!loopBody.add(node)) {
59 continue;
60 }
61
62 stack.addAll(node.predecessors().reversed());
63 }
64 loopBody.add(header);
65
66 return loopBody;
67 }
68
69 static Set<Block> loopBody(Set<Block> loopBody, Block header, Block latch) {
70 naturalLoopBody(loopBody, header, latch);
71
72 Set<Block> extendedLoopBody = new HashSet<>();
73 for (Block lb : loopBody) {
74 for (Block lbs : lb.successorTargets()) {
75 if (!loopBody.contains(lbs) && !extendedLoopBody.contains(lbs)) {
76 // Find if there is path from lbs to latch that does not pass through header
77 Deque<Block> stack = new ArrayDeque<>();
78 stack.push(lbs);
79 Set<Block> visited = new HashSet<>();
80 while (!stack.isEmpty()) {
81 Block x = stack.pop();
82 if (!visited.add(x)) {
83 continue;
84 }
85
86 if (find(x, header, latch)) {
87 extendedLoopBody.add(x);
88 }
89
90 stack.addAll(x.successorTargets());
91 }
92 }
93 }
94 }
95
96 loopBody.addAll(extendedLoopBody);
97 return loopBody;
98 }
99
100 // Determine if there is a forward path from x to y that does not pass through n
101 static boolean find(Block x, Block n, Block y) {
102 if (x == n) {
103 return false;
104 }
105 if (x == y) {
106 return true;
107 }
108
109 boolean r = false;
110 for (Block b : x.successorTargets()) {
111 // Back branch
112 if (x.isDominatedBy(b))
113 return false;
114 if (find(b, n, y)) {
115 return true;
116 }
117 }
118 return false;
119 }
120
121 static List<LoopExit> loopExits(Set<Block> loopBody) {
122 List<LoopExit> loopExits = new ArrayList<>();
123 for (Block block : loopBody) {
124 for (Block t : block.successorTargets()) {
125 if (!loopBody.contains(t)) {
126 loopExits.add(new LoopExit(block, t));
127 }
128 }
129 }
130 return loopExits;
131 }
132
133 static List<Loop> findLoops(Body body) {
134 return body.blocks().stream().flatMap(b -> isLoop(b).stream()).toList();
135 }
136 }