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 package org.graalvm.compiler.loop;
24
25 import java.util.Collections;
26 import java.util.Iterator;
27 import java.util.Map;
28
29 import org.graalvm.compiler.debug.GraalError;
30 import org.graalvm.compiler.graph.Graph;
31 import org.graalvm.compiler.graph.Graph.DuplicationReplacement;
32 import org.graalvm.compiler.graph.Node;
33 import org.graalvm.compiler.graph.NodeBitMap;
34 import org.graalvm.compiler.graph.iterators.NodeIterable;
35 import org.graalvm.compiler.nodes.AbstractBeginNode;
36 import org.graalvm.compiler.nodes.EndNode;
37 import org.graalvm.compiler.nodes.FixedNode;
38 import org.graalvm.compiler.nodes.FrameState;
39 import org.graalvm.compiler.nodes.GuardPhiNode;
40 import org.graalvm.compiler.nodes.GuardProxyNode;
41 import org.graalvm.compiler.nodes.Invoke;
42 import org.graalvm.compiler.nodes.LoopExitNode;
43 import org.graalvm.compiler.nodes.MergeNode;
44 import org.graalvm.compiler.nodes.PhiNode;
45 import org.graalvm.compiler.nodes.ProxyNode;
46 import org.graalvm.compiler.nodes.StructuredGraph;
47 import org.graalvm.compiler.nodes.ValueNode;
48 import org.graalvm.compiler.nodes.ValuePhiNode;
49 import org.graalvm.compiler.nodes.ValueProxyNode;
50 import org.graalvm.compiler.nodes.VirtualState;
51 import org.graalvm.compiler.nodes.cfg.Block;
52 import org.graalvm.compiler.nodes.java.MonitorEnterNode;
53 import org.graalvm.compiler.nodes.spi.NodeWithState;
54 import org.graalvm.compiler.nodes.virtual.CommitAllocationNode;
55 import org.graalvm.compiler.nodes.virtual.VirtualObjectNode;
56
57 public abstract class LoopFragment {
58
59 private final LoopEx loop;
60 private final LoopFragment original;
61 protected NodeBitMap nodes;
62 protected boolean nodesReady;
63 private Map<Node, Node> duplicationMap;
64
65 public LoopFragment(LoopEx loop) {
66 this(loop, null);
67 this.nodesReady = true;
68 }
69
70 public LoopFragment(LoopEx loop, LoopFragment original) {
71 this.loop = loop;
72 this.original = original;
73 this.nodesReady = false;
74 }
75
76 public LoopEx loop() {
77 return loop;
78 }
79
80 public abstract LoopFragment duplicate();
81
82 public abstract void insertBefore(LoopEx l);
83
195 withState.states().forEach(state -> state.applyToVirtual(node -> nodes.mark(node)));
196 }
197 nodes.mark(n);
198 }
199 }
200 for (LoopExitNode earlyExit : earlyExits) {
201 if (earlyExit.isDeleted()) {
202 continue;
203 }
204
205 FrameState stateAfter = earlyExit.stateAfter();
206 if (stateAfter != null) {
207 stateAfter.applyToVirtual(node -> nodes.mark(node));
208 }
209 nodes.mark(earlyExit);
210 for (ProxyNode proxy : earlyExit.proxies()) {
211 nodes.mark(proxy);
212 }
213 }
214
215 final NodeBitMap notloopNodes = graph.createNodeBitMap();
216 for (AbstractBeginNode b : blocks) {
217 if (b.isDeleted()) {
218 continue;
219 }
220
221 for (Node n : b.getBlockNodes()) {
222 if (n instanceof CommitAllocationNode) {
223 for (VirtualObjectNode obj : ((CommitAllocationNode) n).getVirtualObjects()) {
224 markFloating(obj, nodes, notloopNodes);
225 }
226 }
227 if (n instanceof MonitorEnterNode) {
228 markFloating(((MonitorEnterNode) n).getMonitorId(), nodes, notloopNodes);
229 }
230 for (Node usage : n.usages()) {
231 markFloating(usage, nodes, notloopNodes);
232 }
233 }
234 }
235 }
236
237 private static boolean markFloating(Node n, NodeBitMap loopNodes, NodeBitMap notloopNodes) {
238 if (loopNodes.isMarked(n)) {
239 return true;
240 }
241 if (notloopNodes.isMarked(n)) {
242 return false;
243 }
244 if (n instanceof FixedNode) {
245 return false;
246 }
247 boolean mark = false;
248 if (n instanceof PhiNode) {
249 PhiNode phi = (PhiNode) n;
250 mark = loopNodes.isMarked(phi.merge());
251 if (mark) {
252 loopNodes.mark(n);
253 } else {
254 notloopNodes.mark(n);
255 return false;
256 }
257 }
258 for (Node usage : n.usages()) {
259 if (markFloating(usage, loopNodes, notloopNodes)) {
260 mark = true;
261 }
262 }
263 if (mark) {
264 loopNodes.mark(n);
265 return true;
266 }
267 notloopNodes.mark(n);
268 return false;
269 }
270
271 public static NodeIterable<AbstractBeginNode> toHirBlocks(final Iterable<Block> blocks) {
272 return new NodeIterable<AbstractBeginNode>() {
273
274 @Override
275 public Iterator<AbstractBeginNode> iterator() {
276 final Iterator<Block> it = blocks.iterator();
277 return new Iterator<AbstractBeginNode>() {
278
279 @Override
280 public void remove() {
281 throw new UnsupportedOperationException();
282 }
283
284 @Override
285 public AbstractBeginNode next() {
286 return it.next().getBeginNode();
287 }
|
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 package org.graalvm.compiler.loop;
24
25 import java.util.Collections;
26 import java.util.Iterator;
27
28 import org.graalvm.compiler.debug.GraalError;
29 import org.graalvm.compiler.graph.Graph;
30 import org.graalvm.compiler.graph.Graph.DuplicationReplacement;
31 import org.graalvm.compiler.graph.Node;
32 import org.graalvm.compiler.graph.NodeBitMap;
33 import org.graalvm.compiler.graph.iterators.NodeIterable;
34 import org.graalvm.compiler.nodes.AbstractBeginNode;
35 import org.graalvm.compiler.nodes.EndNode;
36 import org.graalvm.compiler.nodes.FixedNode;
37 import org.graalvm.compiler.nodes.FrameState;
38 import org.graalvm.compiler.nodes.GuardNode;
39 import org.graalvm.compiler.nodes.GuardPhiNode;
40 import org.graalvm.compiler.nodes.GuardProxyNode;
41 import org.graalvm.compiler.nodes.Invoke;
42 import org.graalvm.compiler.nodes.LoopExitNode;
43 import org.graalvm.compiler.nodes.MergeNode;
44 import org.graalvm.compiler.nodes.PhiNode;
45 import org.graalvm.compiler.nodes.ProxyNode;
46 import org.graalvm.compiler.nodes.StructuredGraph;
47 import org.graalvm.compiler.nodes.ValueNode;
48 import org.graalvm.compiler.nodes.ValuePhiNode;
49 import org.graalvm.compiler.nodes.ValueProxyNode;
50 import org.graalvm.compiler.nodes.VirtualState;
51 import org.graalvm.compiler.nodes.cfg.Block;
52 import org.graalvm.compiler.nodes.java.MonitorEnterNode;
53 import org.graalvm.compiler.nodes.spi.NodeWithState;
54 import org.graalvm.compiler.nodes.virtual.CommitAllocationNode;
55 import org.graalvm.compiler.nodes.virtual.VirtualObjectNode;
56 import org.graalvm.util.EconomicMap;
57
58 public abstract class LoopFragment {
59
60 private final LoopEx loop;
61 private final LoopFragment original;
62 protected NodeBitMap nodes;
63 protected boolean nodesReady;
64 private EconomicMap<Node, Node> duplicationMap;
65
66 public LoopFragment(LoopEx loop) {
67 this(loop, null);
68 this.nodesReady = true;
69 }
70
71 public LoopFragment(LoopEx loop, LoopFragment original) {
72 this.loop = loop;
73 this.original = original;
74 this.nodesReady = false;
75 }
76
77 public LoopEx loop() {
78 return loop;
79 }
80
81 public abstract LoopFragment duplicate();
82
83 public abstract void insertBefore(LoopEx l);
84
196 withState.states().forEach(state -> state.applyToVirtual(node -> nodes.mark(node)));
197 }
198 nodes.mark(n);
199 }
200 }
201 for (LoopExitNode earlyExit : earlyExits) {
202 if (earlyExit.isDeleted()) {
203 continue;
204 }
205
206 FrameState stateAfter = earlyExit.stateAfter();
207 if (stateAfter != null) {
208 stateAfter.applyToVirtual(node -> nodes.mark(node));
209 }
210 nodes.mark(earlyExit);
211 for (ProxyNode proxy : earlyExit.proxies()) {
212 nodes.mark(proxy);
213 }
214 }
215
216 final NodeBitMap nonLoopNodes = graph.createNodeBitMap();
217 for (AbstractBeginNode b : blocks) {
218 if (b.isDeleted()) {
219 continue;
220 }
221
222 for (Node n : b.getBlockNodes()) {
223 if (n instanceof CommitAllocationNode) {
224 for (VirtualObjectNode obj : ((CommitAllocationNode) n).getVirtualObjects()) {
225 markFloating(obj, nodes, nonLoopNodes);
226 }
227 }
228 if (n instanceof MonitorEnterNode) {
229 markFloating(((MonitorEnterNode) n).getMonitorId(), nodes, nonLoopNodes);
230 }
231 for (Node usage : n.usages()) {
232 markFloating(usage, nodes, nonLoopNodes);
233 }
234 }
235 }
236 }
237
238 private static boolean markFloating(Node n, NodeBitMap loopNodes, NodeBitMap nonLoopNodes) {
239 if (loopNodes.isMarked(n)) {
240 return true;
241 }
242 if (nonLoopNodes.isMarked(n)) {
243 return false;
244 }
245 if (n instanceof FixedNode) {
246 return false;
247 }
248 boolean mark = false;
249 if (n instanceof PhiNode) {
250 PhiNode phi = (PhiNode) n;
251 mark = loopNodes.isMarked(phi.merge());
252 if (mark) {
253 loopNodes.mark(n);
254 } else {
255 nonLoopNodes.mark(n);
256 return false;
257 }
258 }
259 for (Node usage : n.usages()) {
260 if (markFloating(usage, loopNodes, nonLoopNodes)) {
261 mark = true;
262 }
263 }
264 if (!mark && n instanceof GuardNode) {
265 // (gd) this is only OK if we are not going to make loop transforms based on this
266 assert !((GuardNode) n).graph().hasValueProxies();
267 mark = true;
268 }
269 if (mark) {
270 loopNodes.mark(n);
271 return true;
272 }
273 nonLoopNodes.mark(n);
274 return false;
275 }
276
277 public static NodeIterable<AbstractBeginNode> toHirBlocks(final Iterable<Block> blocks) {
278 return new NodeIterable<AbstractBeginNode>() {
279
280 @Override
281 public Iterator<AbstractBeginNode> iterator() {
282 final Iterator<Block> it = blocks.iterator();
283 return new Iterator<AbstractBeginNode>() {
284
285 @Override
286 public void remove() {
287 throw new UnsupportedOperationException();
288 }
289
290 @Override
291 public AbstractBeginNode next() {
292 return it.next().getBeginNode();
293 }
|