1 /*
   2  * Copyright (c) 2016, 2018, 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 }