1 /* 2 * Copyright (c) 2017, 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.loop.test; 26 27 import java.util.ListIterator; 28 29 import org.graalvm.compiler.core.common.CompilationIdentifier; 30 import org.graalvm.compiler.core.test.GraalCompilerTest; 31 import org.graalvm.compiler.debug.DebugContext; 32 import org.graalvm.compiler.graph.iterators.NodeIterable; 33 import org.graalvm.compiler.java.ComputeLoopFrequenciesClosure; 34 import org.graalvm.compiler.loop.DefaultLoopPolicies; 35 import org.graalvm.compiler.loop.LoopEx; 36 import org.graalvm.compiler.loop.LoopFragmentInside; 37 import org.graalvm.compiler.loop.LoopsData; 38 import org.graalvm.compiler.loop.phases.LoopPartialUnrollPhase; 39 import org.graalvm.compiler.nodes.LoopBeginNode; 40 import org.graalvm.compiler.nodes.StructuredGraph; 41 import org.graalvm.compiler.nodes.spi.LoweringTool; 42 import org.graalvm.compiler.options.OptionValues; 43 import org.graalvm.compiler.phases.BasePhase; 44 import org.graalvm.compiler.phases.OptimisticOptimizations; 45 import org.graalvm.compiler.phases.PhaseSuite; 46 import org.graalvm.compiler.phases.common.CanonicalizerPhase; 47 import org.graalvm.compiler.phases.common.ConditionalEliminationPhase; 48 import org.graalvm.compiler.phases.common.DeadCodeEliminationPhase; 49 import org.graalvm.compiler.phases.common.DeoptimizationGroupingPhase; 50 import org.graalvm.compiler.phases.common.FloatingReadPhase; 51 import org.graalvm.compiler.phases.common.FrameStateAssignmentPhase; 52 import org.graalvm.compiler.phases.common.GuardLoweringPhase; 53 import org.graalvm.compiler.phases.common.LoweringPhase; 54 import org.graalvm.compiler.phases.common.RemoveValueProxyPhase; 55 import org.graalvm.compiler.phases.tiers.MidTierContext; 56 import org.graalvm.compiler.phases.tiers.Suites; 57 import org.junit.Ignore; 58 import org.junit.Test; 59 60 import jdk.vm.ci.meta.ResolvedJavaMethod; 61 62 public class LoopPartialUnrollTest extends GraalCompilerTest { 63 64 @Override 65 protected boolean checkMidTierGraph(StructuredGraph graph) { 66 NodeIterable<LoopBeginNode> loops = graph.getNodes().filter(LoopBeginNode.class); 67 for (LoopBeginNode loop : loops) { 68 if (loop.isMainLoop()) { 69 return true; 70 } 71 } 72 return false; 73 } 74 75 public static long sumWithEqualityLimit(int[] text) { 76 long sum = 0; 77 for (int i = 0; branchProbability(0.99, i != text.length); ++i) { 78 sum += volatileInt; 79 } 80 return sum; 81 } 82 83 @Ignore("equality limits aren't working properly") 84 @Test 85 public void testSumWithEqualityLimit() { 86 for (int i = -1; i < 128; i++) { 87 int[] data = new int[i]; 88 test("sumWithEqualityLimit", data); 89 } 90 } 91 92 @Test 93 public void testLoopCarried() { 94 for (int i = -1; i < 64; i++) { 95 test("testLoopCarriedSnippet", i); 96 } 97 } 98 99 @Test 100 public void testLoopCarriedDuplication() { 101 testDuplicateBody("testLoopCarriedReference", "testLoopCarriedSnippet"); 102 } 103 104 static volatile int volatileInt = 3; 105 106 public static int testLoopCarriedSnippet(int iterations) { 107 int a = 0; 108 int b = 0; 109 int c = 0; 110 111 for (int i = 0; branchProbability(0.99, i < iterations); i++) { 112 int t1 = volatileInt; 113 int t2 = a + b; 114 c = b; 115 b = a; 116 a = t1 + t2; 117 } 118 119 return c; 120 } 121 122 public static int testLoopCarriedReference(int iterations) { 123 int a = 0; 124 int b = 0; 125 int c = 0; 126 127 for (int i = 0; branchProbability(0.99, i < iterations); i += 2) { 128 int t1 = volatileInt; 129 int t2 = a + b; 130 c = b; 131 b = a; 132 a = t1 + t2; 133 t1 = volatileInt; 134 t2 = a + b; 135 c = b; 136 b = a; 137 a = t1 + t2; 138 } 139 140 return c; 141 } 142 143 @Test 144 public void testLoopCarried2() { 145 for (int i = -1; i < 64; i++) { 146 for (int j = -1; j < 64; j++) { 147 test("testLoopCarried2Snippet", i, j); 148 } 149 } 150 test("testLoopCarried2Snippet", Integer.MAX_VALUE - 32, Integer.MAX_VALUE); 151 test("testLoopCarried2Snippet", Integer.MAX_VALUE - 4, Integer.MAX_VALUE); 152 test("testLoopCarried2Snippet", Integer.MAX_VALUE, 0); 153 test("testLoopCarried2Snippet", Integer.MIN_VALUE, Integer.MIN_VALUE + 32); 154 test("testLoopCarried2Snippet", Integer.MIN_VALUE, Integer.MIN_VALUE + 4); 155 test("testLoopCarried2Snippet", 0, Integer.MIN_VALUE); 156 } 157 158 public static int testLoopCarried2Snippet(int start, int end) { 159 int a = 0; 160 int b = 0; 161 int c = 0; 162 163 for (int i = start; branchProbability(0.99, i < end); i++) { 164 int t1 = volatileInt; 165 int t2 = a + b; 166 c = b; 167 b = a; 168 a = t1 + t2; 169 } 170 171 return c; 172 } 173 174 public static long init = Runtime.getRuntime().totalMemory(); 175 private int x; 176 private int z; 177 178 public int[] testComplexSnippet(int d) { 179 x = 3; 180 int y = 5; 181 z = 7; 182 for (int i = 0; i < d; i++) { 183 for (int j = 0; branchProbability(0.99, j < i); j++) { 184 z += x; 185 } 186 y = x ^ z; 187 if ((i & 4) == 0) { 188 z--; 189 } else if ((i & 8) == 0) { 190 Runtime.getRuntime().totalMemory(); 191 } 192 } 193 return new int[]{x, y, z}; 194 } 195 196 @Test 197 public void testComplex() { 198 for (int i = -1; i < 10; i++) { 199 test("testComplexSnippet", i); 200 } 201 test("testComplexSnippet", 10); 202 test("testComplexSnippet", 100); 203 test("testComplexSnippet", 1000); 204 } 205 206 public static long testSignExtensionSnippet(long arg) { 207 long r = 1; 208 for (int i = 0; branchProbability(0.99, i < arg); i++) { 209 r *= i; 210 } 211 return r; 212 } 213 214 @Test 215 public void testSignExtension() { 216 test("testSignExtensionSnippet", 9L); 217 } 218 219 @Override 220 protected Suites createSuites(OptionValues opts) { 221 Suites suites = super.createSuites(opts).copy(); 222 PhaseSuite<MidTierContext> mid = suites.getMidTier(); 223 ListIterator<BasePhase<? super MidTierContext>> iter = mid.findPhase(LoopPartialUnrollPhase.class); 224 BasePhase<? super MidTierContext> partialUnoll = iter.previous(); 225 if (iter.previous().getClass() != FrameStateAssignmentPhase.class) { 226 // Ensure LoopPartialUnrollPhase runs immediately after FrameStateAssignment, so it gets 227 // priority over other optimizations in these tests. 228 mid.findPhase(LoopPartialUnrollPhase.class).remove(); 229 ListIterator<BasePhase<? super MidTierContext>> fsa = mid.findPhase(FrameStateAssignmentPhase.class); 230 fsa.add(partialUnoll); 231 } 232 return suites; 233 } 234 235 public void testGraph(String reference, String test) { 236 StructuredGraph referenceGraph = buildGraph(reference, false); 237 StructuredGraph testGraph = buildGraph(test, true); 238 assertEquals(referenceGraph, testGraph, false, false); 239 } 240 241 @SuppressWarnings("try") 242 public StructuredGraph buildGraph(String name, boolean partialUnroll) { 243 CompilationIdentifier id = new CompilationIdentifier() { 244 @Override 245 public String toString(Verbosity verbosity) { 246 return name; 247 } 248 }; 249 ResolvedJavaMethod method = getResolvedJavaMethod(name); 250 OptionValues options = new OptionValues(getInitialOptions(), DefaultLoopPolicies.Options.UnrollMaxIterations, 2); 251 StructuredGraph graph = parse(builder(method, StructuredGraph.AllowAssumptions.YES, id, options), getEagerGraphBuilderSuite()); 252 try (DebugContext.Scope buildScope = graph.getDebug().scope(name, method, graph)) { 253 MidTierContext context = new MidTierContext(getProviders(), getTargetProvider(), OptimisticOptimizations.ALL, null); 254 255 CanonicalizerPhase canonicalizer = new CanonicalizerPhase(); 256 canonicalizer.apply(graph, context); 257 new RemoveValueProxyPhase().apply(graph); 258 new LoweringPhase(canonicalizer, LoweringTool.StandardLoweringStage.HIGH_TIER).apply(graph, context); 259 new FloatingReadPhase().apply(graph); 260 new DeadCodeEliminationPhase().apply(graph); 261 new ConditionalEliminationPhase(true).apply(graph, context); 262 ComputeLoopFrequenciesClosure.compute(graph); 263 new GuardLoweringPhase().apply(graph, context); 264 new LoweringPhase(canonicalizer, LoweringTool.StandardLoweringStage.MID_TIER).apply(graph, context); 265 new FrameStateAssignmentPhase().apply(graph); 266 new DeoptimizationGroupingPhase().apply(graph, context); 267 canonicalizer.apply(graph, context); 268 new ConditionalEliminationPhase(true).apply(graph, context); 269 if (partialUnroll) { 270 LoopsData dataCounted = new LoopsData(graph); 271 dataCounted.detectedCountedLoops(); 272 for (LoopEx loop : dataCounted.countedLoops()) { 273 LoopFragmentInside newSegment = loop.inside().duplicate(); 274 newSegment.insertWithinAfter(loop, null); 275 } 276 canonicalizer.apply(graph, getDefaultMidTierContext()); 277 } 278 new DeadCodeEliminationPhase().apply(graph); 279 canonicalizer.apply(graph, context); 280 graph.getDebug().dump(DebugContext.BASIC_LEVEL, graph, "before compare"); 281 return graph; 282 } catch (Throwable e) { 283 throw getDebugContext().handle(e); 284 } 285 } 286 287 public void testDuplicateBody(String reference, String test) { 288 289 StructuredGraph referenceGraph = buildGraph(reference, false); 290 StructuredGraph testGraph = buildGraph(test, true); 291 CanonicalizerPhase canonicalizer = new CanonicalizerPhase(); 292 canonicalizer.apply(testGraph, getDefaultMidTierContext()); 293 canonicalizer.apply(referenceGraph, getDefaultMidTierContext()); 294 assertEquals(referenceGraph, testGraph); 295 } 296 }