1 /*
2  * Copyright (c) 2016, 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 java.util.ArrayList;
28 import java.util.Arrays;
29 import java.util.List;
30 
31 import org.junit.Assert;
32 import org.junit.Test;
33 
34 import org.graalvm.compiler.api.directives.GraalDirectives;
35 import org.graalvm.compiler.core.common.cfg.Loop;
36 import org.graalvm.compiler.nodes.StructuredGraph;
37 import org.graalvm.compiler.nodes.StructuredGraph.AllowAssumptions;
38 import org.graalvm.compiler.nodes.StructuredGraph.GuardsStage;
39 import org.graalvm.compiler.nodes.cfg.Block;
40 import org.graalvm.compiler.nodes.cfg.ControlFlowGraph;
41 import org.graalvm.compiler.phases.graph.ReentrantBlockIterator;
42 import org.graalvm.compiler.phases.graph.ReentrantBlockIterator.BlockIteratorClosure;
43 import org.graalvm.compiler.phases.schedule.SchedulePhase;
44 
45 public class ReentrantBlockIteratorTest extends GraalCompilerTest {
46 
47     public static int IntSideEffect;
48 
oneBlock()49     public static int oneBlock() {
50         return 0;
51     }
52 
fourBlock(int a)53     public static int fourBlock(int a) {
54         if (a > 0) {
55             IntSideEffect = a;
56         } else {
57             IntSideEffect = 0;
58         }
59         GraalDirectives.controlFlowAnchor();
60         return 0;
61     }
62 
loopBlocks(int a)63     public static int loopBlocks(int a) {
64         int phi = 0;
65         for (int i = 0; i < a; i++) {
66             phi += i;
67         }
68         return phi;
69     }
70 
loopBlocks2(int a)71     public static int loopBlocks2(int a) {
72         int phi = 0;
73         for (int i = 0; i < a; i++) {
74             phi += i;
75         }
76         // first loop exit, second loop will not be visited at all AFTER_FSA
77         for (int i = 0; i < a; i++) {
78             phi += i;
79         }
80         return phi;
81     }
82 
83     // from String.indexof
84     @SuppressWarnings("all")
loopBlocks3(char[] source, int sourceOffset, int sourceCount, char[] target, int targetOffset, int targetCount, int fromIndex)85     public static int loopBlocks3(char[] source, int sourceOffset, int sourceCount, char[] target, int targetOffset, int targetCount,
86                     int fromIndex) {
87 
88         // Checkstyle: stop
89         if (fromIndex >= sourceCount) {
90             return (targetCount == 0 ? sourceCount : -1);
91         }
92         if (fromIndex < 0) {
93             fromIndex = 0;
94         }
95         if (targetCount == 0) {
96             return fromIndex;
97         }
98 
99         char first = target[targetOffset];
100         int max = sourceOffset + (sourceCount - targetCount);
101 
102         for (int i = sourceOffset + fromIndex; i <= max; i++) {
103             /* Look for first character. */
104             if (source[i] != first) {
105                 while (++i <= max && source[i] != first) {
106 
107                 }
108             }
109 
110             /* Found first character, now look at the rest of v2 */
111             if (i <= max) {
112                 int j = i + 1;
113                 int end = j + targetCount - 1;
114                 for (int k = targetOffset + 1; j < end && source[j] == target[k]; j++, k++) {
115 
116                 }
117 
118                 if (j == end) {
119                     /* Found whole string. */
120                     return i - sourceOffset;
121                 }
122             }
123         }
124         return -1;
125         // Checkstyle: resume
126     }
127 
loopBlocks4(int a, int c, int d)128     public static int loopBlocks4(int a, int c, int d) {
129         int phi = 0;
130         l1: for (int i = 0; i < a; i++) {
131             l3: for (int k = 0; k < c; k++) {
132                 for (int l = 0; l < d; l++) {
133                     phi += i * k * l;
134                     if (phi == 5) {
135                         break l3;
136                     }
137                 }
138             }
139             if (phi > 100) {
140                 break l1;
141             }
142         }
143         return phi;
144     }
145 
146     @Test
147 
test01()148     public void test01() {
149         List<Block> blocks = getVisitedBlocksInOrder("oneBlock");
150         assertOrder(blocks, 0);
151     }
152 
153     @Test
test02()154     public void test02() {
155         List<Block> blocks = getVisitedBlocksInOrder("fourBlock");
156         assertOrder(blocks, 0, 1, 2, 3);
157     }
158 
159     @Test
test03()160     public void test03() {
161         List<Block> blocks = getVisitedBlocksInOrder("loopBlocks");
162         assertOrder(blocks, 0, 1, 2, 3);
163     }
164 
165     @Test
test04()166     public void test04() {
167         List<Block> blocks = getVisitedBlocksInOrder("loopBlocks2");
168         assertOrder(blocks, 0, 1, 2, 3, 4, 5, 6);
169     }
170 
171     @Test
test05()172     public void test05() {
173         List<Block> blocks = getVisitedBlocksInOrder("loopBlocks3");
174         assertVisited(blocks, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32);
175     }
176 
177     @Test
test06()178     public void test06() {
179         getVisitedBlocksInOrder("loopBlocks4");
180     }
181 
assertOrder(List<Block> blocks, int... ids)182     private static void assertOrder(List<Block> blocks, int... ids) {
183         if (blocks.size() != ids.length) {
184             Assert.fail("Different length of blocks " + Arrays.toString(blocks.toArray()) + " ids:" + Arrays.toString(ids));
185         }
186         for (int i = 0; i < blocks.size(); i++) {
187             if (blocks.get(i).getId() != ids[i]) {
188                 Assert.fail("Different id for block " + blocks.get(i) + " and associated id " + ids[i]);
189             }
190         }
191     }
192 
assertVisited(List<Block> blocks, int... ids)193     private static void assertVisited(List<Block> blocks, int... ids) {
194         if (blocks.size() != ids.length) {
195             Assert.fail("Different length of blocks " + Arrays.toString(blocks.toArray()) + " ids:" + Arrays.toString(ids));
196         }
197         outer: for (int i = 0; i < blocks.size(); i++) {
198             for (int j = 0; j < blocks.size(); j++) {
199                 if (blocks.get(i).getId() == ids[j]) {
200                     continue outer;
201                 }
202             }
203             Assert.fail("Id for block " + blocks.get(i) + " not found");
204         }
205     }
206 
getVisitedBlocksInOrder(String snippet)207     private List<Block> getVisitedBlocksInOrder(String snippet) {
208         StructuredGraph graph = parseEager(snippet, AllowAssumptions.YES);
209         // after FSA to ensure HIR loop data structure does not contain loop exits
210         graph.setGuardsStage(GuardsStage.AFTER_FSA);
211         ArrayList<Block> blocks = new ArrayList<>();
212         class VoidState {
213         }
214         final VoidState voidState = new VoidState();
215         BlockIteratorClosure<VoidState> closure = new BlockIteratorClosure<VoidState>() {
216 
217             @Override
218             protected VoidState getInitialState() {
219                 return voidState;
220             }
221 
222             @Override
223             protected VoidState processBlock(Block block, VoidState currentState) {
224                 // remember the visit order
225                 blocks.add(block);
226                 return currentState;
227             }
228 
229             @Override
230             protected VoidState merge(Block merge, List<VoidState> states) {
231                 return voidState;
232             }
233 
234             @Override
235             protected VoidState cloneState(VoidState oldState) {
236                 return voidState;
237             }
238 
239             @Override
240             protected List<VoidState> processLoop(Loop<Block> loop, VoidState initialState) {
241                 return ReentrantBlockIterator.processLoop(this, loop, initialState).exitStates;
242             }
243         };
244         ControlFlowGraph cfg = ControlFlowGraph.compute(graph, true, true, true, false);
245         ReentrantBlockIterator.apply(closure, cfg.getStartBlock());
246         // schedule for IGV
247         new SchedulePhase(graph.getOptions()).apply(graph);
248         return blocks;
249     }
250 
251 }
252