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