1 /*
2 * Copyright (c) 2012, 2018, 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
25
26 package org.graalvm.compiler.core.common.cfg;
27
28 import static org.graalvm.compiler.core.common.cfg.AbstractBlockBase.BLOCK_ID_COMPARATOR;
29
30 import java.util.ArrayList;
31 import java.util.Collections;
32 import java.util.List;
33
34 public abstract class Loop<T extends AbstractBlockBase<T>> {
35
36 private final Loop<T> parent;
37 private final ArrayList<Loop<T>> children;
38
39 private final int depth;
40 private final int index;
41 private final T header;
42 private final ArrayList<T> blocks;
43 private final ArrayList<T> exits;
44 /**
45 * Natural exits, ignoring LoopExitNodes.
46 *
47 * @see #getNaturalExits()
48 */
49 private final ArrayList<T> naturalExits;
50
51 protected Loop(Loop<T> parent, int index, T header) {
52 this.parent = parent;
53 if (parent != null) {
54 this.depth = parent.getDepth() + 1;
55 } else {
56 this.depth = 1;
57 }
58 this.index = index;
59 this.header = header;
60 this.blocks = new ArrayList<>();
61 this.children = new ArrayList<>();
62 this.exits = new ArrayList<>();
63 this.naturalExits = new ArrayList<>();
64 }
65
66 public abstract long numBackedges();
67
68 @Override
69 public String toString() {
70 return "loop " + index + " depth " + getDepth() + (parent != null ? " outer " + parent.index : "");
71 }
72
73 public Loop<T> getParent() {
74 return parent;
75 }
76
77 public List<Loop<T>> getChildren() {
78 return children;
79 }
80
81 public int getDepth() {
82 return depth;
83 }
84
85 public int getIndex() {
86 return index;
87 }
88
89 public T getHeader() {
90 return header;
91 }
92
93 public List<T> getBlocks() {
94 return blocks;
95 }
96
97 /**
98 * Returns the loop exits.
99 *
100 * This might be a conservative set: before framestate assignment it matches the LoopExitNodes
101 * even if earlier blocks could be considered as exits. After framestate assignments, this is
102 * the same as {@link #getNaturalExits()}.
103 *
104 * <p>
105 * LoopExitNodes are inserted in the control-flow during parsing and are natural exits: they are
106 * the earliest block at which we are guaranteed to have exited the loop. However, after some
107 * transformations of the graph, the natural exit might go up but the LoopExitNodes are not
108 * updated.
109 * </p>
110 *
111 * <p>
112 * For example in:
113 *
114 * <pre>
115 * for (int i = 0; i < N; i++) {
116 * if (c) {
117 * // Block 1
118 * if (dummy) {
119 * // ...
120 * } else {
121 * // ...
122 * }
123 * if (b) {
124 * continue;
125 * } else {
126 * // Block 2
127 * // LoopExitNode
128 * break;
129 * }
130 * }
131 * }
132 * </pre>
133 *
134 * After parsing, the natural exits match the LoopExitNode: Block 2 is a natural exit and has a
135 * LoopExitNode. If the {@code b} condition gets canonicalized to {@code false}, the natural
136 * exit moves to Block 1 while the LoopExitNode remains in Block 2. In such a scenario,
137 * {@code getLoopExits()} will contain block 2 while {@link #getNaturalExits()} will contain
138 * block 1.
139 *
140 *
141 * @see #getNaturalExits()
142 */
143 public List<T> getLoopExits() {
144 return exits;
145 }
146
147 public boolean isLoopExit(T block) {
148 assert isSorted(exits);
149 return Collections.binarySearch(exits, block, BLOCK_ID_COMPARATOR) >= 0;
150 }
151
152 /**
153 * Returns the natural exit points: these are the earliest block that are guaranteed to never
154 * reach a back-edge.
155 *
156 * This can not be used in the context of preserving or using loop-closed form.
157 *
158 * @see #getLoopExits()
159 */
160 public ArrayList<T> getNaturalExits() {
161 return naturalExits;
162 }
163
164 public boolean isNaturalExit(T block) {
165 assert isSorted(naturalExits);
166 return Collections.binarySearch(naturalExits, block, BLOCK_ID_COMPARATOR) >= 0;
167 }
168
169 private static <T extends AbstractBlockBase<T>> boolean isSorted(List<T> list) {
170 int lastId = Integer.MIN_VALUE;
171 for (AbstractBlockBase<?> block : list) {
172 if (block.getId() < lastId) {
173 return false;
174 }
175 lastId = block.getId();
176 }
177 return true;
178 }
179
180 /**
181 * Determines if one loop is a transitive parent of another loop.
182 *
183 * @param childLoop The loop for which parentLoop might be a transitive parent loop.
184 * @param parentLoop The loop which might be a transitive parent loop of child loop.
185 * @return {@code true} if parentLoop is a (transitive) parent loop of childLoop, {@code false}
186 * otherwise
187 */
188 public static <T extends AbstractBlockBase<T>> boolean transitiveParentLoop(Loop<T> childLoop, Loop<T> parentLoop) {
189 Loop<T> curr = childLoop;
190 while (curr != null) {
191 if (curr == parentLoop) {
192 return true;
193 }
194 curr = curr.getParent();
195 }
196 return false;
197 }
198
199 @Override
200 public int hashCode() {
201 return index + depth * 31;
202 }
203
204 @Override
205 public boolean equals(Object obj) {
206 return super.equals(obj);
207 }
208 }