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 }