1 /*
2 * Copyright (c) 2011, 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 package org.graalvm.compiler.core.test;
26
27 import org.graalvm.compiler.core.common.cfg.Loop;
28 import org.graalvm.compiler.debug.DebugContext;
29 import org.graalvm.compiler.graph.Node;
30 import org.graalvm.compiler.nodes.Invoke;
31 import org.graalvm.compiler.nodes.StructuredGraph;
32 import org.graalvm.compiler.nodes.StructuredGraph.AllowAssumptions;
33 import org.graalvm.compiler.nodes.cfg.Block;
34 import org.graalvm.compiler.nodes.cfg.ControlFlowGraph;
35 import org.graalvm.compiler.nodes.java.MethodCallTargetNode;
36 import org.junit.Assert;
37 import org.junit.Test;
38
39 public class NestedLoopTest extends GraalCompilerTest {
40
41 @Test
42 public void test1() {
43 test("test1Snippet", 1, 2, 2);
44 }
45
46 @Test
47 public void test2() {
48 test("test2Snippet", 1, 2, 2);
49 }
50
51 @Test
52 public void test3() {
53 test("test3Snippet", 1, 2, 2);
54 }
55
56 @Test
57 public void test4() {
58 test("test4Snippet", 1, 3, 2);
59 }
60
61 @SuppressWarnings("all")
62 public static void test1Snippet(int a) {
63 while (a()) { // a() exits root, while() exits root
64 m1: while (b()) { // b() exits nested & root, while() exits nested
65 while (c()) { // c() exits innermost & nested & root, while() exits innermost
66 if (d()) { // d() exits innermost & nested & root
67 break m1; // break exits innermost & nested
68 }
69 }
70 }
71 }
72 }// total : root = 5 exits, nested = 5, innermost = 4
73
74 @SuppressWarnings("all")
75 public static void test2Snippet(int a) {
76 while (a()) { // a() exits root, while() exits root
77 try {
78 m1: while (b()) { // b() exits nested, while() exits nested
79 while (c()) { // c() exits innermost & nested, while() exits innermost
80 if (d()) { // d() exits innermost & nested
81 break m1; // break exits innermost & nested
82 }
83 }
84 }
85 } catch (Throwable t) {
86 }
87 }
88 }// total : root = 2 exits, nested = 5, innermost = 4
89
90 @SuppressWarnings("all")
91 public static void test3Snippet(int a) {
92 while (a == 0) { // while() exits root
93 try {
94 m1: while (b()) { // b() exits nested, while() exits nested
95 while (c()) { // c() exits innermost & nested, while() exits innermost
96 if (d()) { // d() exits innermost & nested
97 a(); // a() exits nothing (already outside innermost & nested)
98 break m1; // break exits innermost & nested
99 }
100 }
101 }
102 } catch (Throwable t) {
103 }
104 }
105 }// total : root = 1 exit, nested = 5, innermost = 4
106
107 public static void test4Snippet(int a) {
108 while (a != 0) { // while() exits root
109 try {
110 m1: while (a != 0) { // while() exits nested
111 b(); // b() exits nested
112 while (c()) { // c() exits innermost & nested, while() exits innermost
113 if (d()) { // d() exits innermost & nested
114 break m1; // break exits innermost & nested
115 }
116 }
117 if (a != 2) {
118 a(); // a() exits nothing (already outside innermost & nested)
119 throw new Exception(); // throw exits nested
120 }
121 }
122 } catch (Throwable t) {
123 }
124 }
125 } // total : root = 1 exit, nested = 6, innermost = 4
126
127 private static native boolean a();
128
129 private static native boolean b();
130
131 private static native boolean c();
132
133 private static native boolean d();
134
135 private static Invoke getInvoke(String name, StructuredGraph graph) {
136 for (MethodCallTargetNode callTarget : graph.getNodes(MethodCallTargetNode.TYPE)) {
137 if (callTarget.targetMethod().getName().equals(name)) {
138 return callTarget.invoke();
139 }
140 }
141 return null;
142 }
143
144 private void test(String snippet, int rootExits, int nestedExits, int innerExits) {
145 StructuredGraph graph = parseEager(snippet, AllowAssumptions.YES);
146 DebugContext debug = graph.getDebug();
147 debug.dump(DebugContext.BASIC_LEVEL, graph, "Graph");
148 ControlFlowGraph cfg = ControlFlowGraph.compute(graph, true, true, true, true);
149
150 Assert.assertEquals(3, cfg.getLoops().size());
151 Loop<Block> rootLoop = cfg.getLoops().get(0);
152 Loop<Block> nestedLoop = cfg.getLoops().get(1);
153 Loop<Block> innerMostLoop = cfg.getLoops().get(2);
154 Invoke a = getInvoke("a", graph);
155 Invoke b = getInvoke("b", graph);
156 Invoke c = getInvoke("c", graph);
157 Invoke d = getInvoke("d", graph);
158 Assert.assertTrue(containsDirect(rootLoop, a, cfg));
159 Assert.assertTrue(containsDirect(nestedLoop, b, cfg));
160 Assert.assertTrue(containsDirect(innerMostLoop, c, cfg));
161 Assert.assertTrue(containsDirect(innerMostLoop, d, cfg));
162 Assert.assertTrue(contains(rootLoop, d, cfg));
163 Assert.assertTrue(contains(nestedLoop, d, cfg));
164 Assert.assertEquals(rootExits, rootLoop.getLoopExits().size());
165 Assert.assertEquals(nestedExits, nestedLoop.getLoopExits().size());
166 Assert.assertEquals(innerExits, innerMostLoop.getLoopExits().size());
167 debug.dump(DebugContext.BASIC_LEVEL, graph, "Graph");
168 }
169
170 private static boolean contains(Loop<Block> loop, Invoke node, ControlFlowGraph cfg) {
171 Block block = cfg.blockFor((Node) node);
172 Assert.assertNotNull(block);
173 return loop.getBlocks().contains(block);
174 }
175
176 private static boolean containsDirect(Loop<Block> loop, Invoke node, ControlFlowGraph cfg) {
177 for (Loop<Block> child : loop.getChildren()) {
178 if (contains(child, node, cfg)) {
179 return false;
180 }
181 }
182 return contains(loop, node, cfg);
183 }
184 }