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
49 public static int oneBlock() {
50 return 0;
51 }
52
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
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
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")
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
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
148 public void test01() {
149 List<Block> blocks = getVisitedBlocksInOrder("oneBlock");
150 assertOrder(blocks, 0);
151 }
152
153 @Test
154 public void test02() {
155 List<Block> blocks = getVisitedBlocksInOrder("fourBlock");
156 assertOrder(blocks, 0, 1, 2, 3);
157 }
158
159 @Test
160 public void test03() {
161 List<Block> blocks = getVisitedBlocksInOrder("loopBlocks");
162 assertOrder(blocks, 0, 1, 2, 3);
163 }
164
165 @Test
166 public void test04() {
167 List<Block> blocks = getVisitedBlocksInOrder("loopBlocks2");
168 assertOrder(blocks, 0, 1, 2, 3, 4, 5, 6);
169 }
170
171 @Test
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
178 public void test06() {
179 getVisitedBlocksInOrder("loopBlocks4");
180 }
181
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
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
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 }