001/*
002 * Copyright (c) 2011, Oracle and/or its affiliates. All rights reserved.
003 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
004 *
005 * This code is free software; you can redistribute it and/or modify it
006 * under the terms of the GNU General Public License version 2 only, as
007 * published by the Free Software Foundation.
008 *
009 * This code is distributed in the hope that it will be useful, but WITHOUT
010 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
011 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
012 * version 2 for more details (a copy is included in the LICENSE file that
013 * accompanied this code).
014 *
015 * You should have received a copy of the GNU General Public License version
016 * 2 along with this work; if not, write to the Free Software Foundation,
017 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
018 *
019 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
020 * or visit www.oracle.com if you need additional information or have any
021 * questions.
022 */
023package com.oracle.graal.compiler.test;
024
025import com.oracle.graal.debug.*;
026
027import org.junit.*;
028
029import com.oracle.graal.compiler.common.cfg.*;
030import com.oracle.graal.graph.*;
031import com.oracle.graal.nodes.*;
032import com.oracle.graal.nodes.StructuredGraph.AllowAssumptions;
033import com.oracle.graal.nodes.cfg.*;
034import com.oracle.graal.nodes.java.*;
035
036public class NestedLoopTest extends GraalCompilerTest {
037
038    @Test
039    public void test1() {
040        test("test1Snippet", 1, 2, 2);
041    }
042
043    @Test
044    public void test2() {
045        test("test2Snippet", 1, 2, 2);
046    }
047
048    @Test
049    public void test3() {
050        test("test3Snippet", 1, 2, 2);
051    }
052
053    @Test
054    public void test4() {
055        test("test4Snippet", 1, 3, 2);
056    }
057
058    @SuppressWarnings("all")
059    public static void test1Snippet(int a) {
060        while (a()) { // a() exits root, while() exits root
061            m1: while (b()) { // b() exits nested & root, while() exits nested
062                while (c()) { // c() exits innermost & nested & root, while() exits innermost
063                    if (d()) { // d() exits innermost & nested & root
064                        break m1; // break exits innermost & nested
065                    }
066                }
067            }
068        }
069    }// total : root = 5 exits, nested = 5, innermost = 4
070
071    @SuppressWarnings("all")
072    public static void test2Snippet(int a) {
073        while (a()) { // a() exits root, while() exits root
074            try {
075                m1: while (b()) { // b() exits nested, while() exits nested
076                    while (c()) { // c() exits innermost & nested, while() exits innermost
077                        if (d()) { // d() exits innermost & nested
078                            break m1; // break exits innermost & nested
079                        }
080                    }
081                }
082            } catch (Throwable t) {
083            }
084        }
085    }// total : root = 2 exits, nested = 5, innermost = 4
086
087    @SuppressWarnings("all")
088    public static void test3Snippet(int a) {
089        while (a == 0) { // while() exits root
090            try {
091                m1: while (b()) { // b() exits nested, while() exits nested
092                    while (c()) { // c() exits innermost & nested, while() exits innermost
093                        if (d()) { // d() exits innermost & nested
094                            a(); // a() exits nothing (already outside innermost & nested)
095                            break m1; // break exits innermost & nested
096                        }
097                    }
098                }
099            } catch (Throwable t) {
100            }
101        }
102    }// total : root = 1 exit, nested = 5, innermost = 4
103
104    public static void test4Snippet(int a) {
105        while (a != 0) { // while() exits root
106            try {
107                m1: while (a != 0) { // while() exits nested
108                    b(); // b() exits nested
109                    while (c()) { // c() exits innermost & nested, while() exits innermost
110                        if (d()) { // d() exits innermost & nested
111                            break m1; // break exits innermost & nested
112                        }
113                    }
114                    if (a != 2) {
115                        a(); // a() exits nothing (already outside innermost & nested)
116                        throw new Exception(); // throw exits nested
117                    }
118                }
119            } catch (Throwable t) {
120            }
121        }
122    } // total : root = 1 exit, nested = 6, innermost = 4
123
124    private static native boolean a();
125
126    private static native boolean b();
127
128    private static native boolean c();
129
130    private static native boolean d();
131
132    private static Invoke getInvoke(String name, StructuredGraph graph) {
133        for (MethodCallTargetNode callTarget : graph.getNodes(MethodCallTargetNode.TYPE)) {
134            if (callTarget.targetMethod().getName().equals(name)) {
135                return callTarget.invoke();
136            }
137        }
138        return null;
139    }
140
141    private void test(String snippet, int rootExits, int nestedExits, int innerExits) {
142        StructuredGraph graph = parseEager(snippet, AllowAssumptions.YES);
143        Debug.dump(graph, "Graph");
144        ControlFlowGraph cfg = ControlFlowGraph.compute(graph, true, true, true, true);
145
146        Assert.assertEquals(3, cfg.getLoops().size());
147        Loop<Block> rootLoop = cfg.getLoops().get(0);
148        Loop<Block> nestedLoop = cfg.getLoops().get(1);
149        Loop<Block> innerMostLoop = cfg.getLoops().get(2);
150        Invoke a = getInvoke("a", graph);
151        Invoke b = getInvoke("b", graph);
152        Invoke c = getInvoke("c", graph);
153        Invoke d = getInvoke("d", graph);
154        Assert.assertTrue(containsDirect(rootLoop, a, cfg));
155        Assert.assertTrue(containsDirect(nestedLoop, b, cfg));
156        Assert.assertTrue(containsDirect(innerMostLoop, c, cfg));
157        Assert.assertTrue(containsDirect(innerMostLoop, d, cfg));
158        Assert.assertTrue(contains(rootLoop, d, cfg));
159        Assert.assertTrue(contains(nestedLoop, d, cfg));
160        Assert.assertEquals(rootExits, rootLoop.getExits().size());
161        Assert.assertEquals(nestedExits, nestedLoop.getExits().size());
162        Assert.assertEquals(innerExits, innerMostLoop.getExits().size());
163        Debug.dump(graph, "Graph");
164    }
165
166    private static boolean contains(Loop<Block> loop, Invoke node, ControlFlowGraph cfg) {
167        Block block = cfg.blockFor((Node) node);
168        Assert.assertNotNull(block);
169        return loop.getBlocks().contains(block);
170    }
171
172    private static boolean containsDirect(Loop<Block> loop, Invoke node, ControlFlowGraph cfg) {
173        for (Loop<Block> child : loop.getChildren()) {
174            if (contains(child, node, cfg)) {
175                return false;
176            }
177        }
178        return contains(loop, node, cfg);
179    }
180}