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