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 = 0; 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 = 0; 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 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 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 public static long init = Runtime.getRuntime().totalMemory(); 144 private int x; 145 private int z; 146 147 public int[] testComplexSnippet(int d) { 148 x = 3; 149 int y = 5; 150 z = 7; 151 for (int i = 0; i < d; i++) { 152 for (int j = 0; branchProbability(0.99, j < i); j++) { 153 z += x; 154 } 155 y = x ^ z; 156 if ((i & 4) == 0) { 157 z--; 158 } else if ((i & 8) == 0) { 159 Runtime.getRuntime().totalMemory(); 160 } 161 } 162 return new int[]{x, y, z}; 163 } 164 165 @Test 166 public void testComplex() { 167 for (int i = 0; i < 10; i++) { 168 test("testComplexSnippet", i); 169 } 170 test("testComplexSnippet", 10); 171 test("testComplexSnippet", 100); 172 test("testComplexSnippet", 1000); 173 } 174 175 public static long testSignExtensionSnippet(long arg) { 176 long r = 1; 177 for (int i = 0; branchProbability(0.99, i < arg); i++) { 178 r *= i; 179 } 180 return r; 181 } 182 183 @Test 184 public void testSignExtension() { 185 test("testSignExtensionSnippet", 9L); 186 } 187 188 @Override 189 protected Suites createSuites(OptionValues opts) { 190 Suites suites = super.createSuites(opts).copy(); 191 PhaseSuite<MidTierContext> mid = suites.getMidTier(); 192 ListIterator<BasePhase<? super MidTierContext>> iter = mid.findPhase(LoopPartialUnrollPhase.class); 193 BasePhase<? super MidTierContext> partialUnoll = iter.previous(); 194 if (iter.previous().getClass() != FrameStateAssignmentPhase.class) { 195 // Ensure LoopPartialUnrollPhase runs immediately after FrameStateAssignment, so it gets 196 // priority over other optimizations in these tests. 197 mid.findPhase(LoopPartialUnrollPhase.class).remove(); 198 ListIterator<BasePhase<? super MidTierContext>> fsa = mid.findPhase(FrameStateAssignmentPhase.class); 199 fsa.add(partialUnoll); 200 } 201 return suites; 202 } 203 204 public void testGraph(String reference, String test) { 205 StructuredGraph referenceGraph = buildGraph(reference, false); 206 StructuredGraph testGraph = buildGraph(test, true); 207 assertEquals(referenceGraph, testGraph, false, false); 208 } 209 210 @SuppressWarnings("try") 211 public StructuredGraph buildGraph(String name, boolean partialUnroll) { 212 CompilationIdentifier id = new CompilationIdentifier() { 213 @Override 214 public String toString(Verbosity verbosity) { 215 return name; 216 } 217 }; 218 ResolvedJavaMethod method = getResolvedJavaMethod(name); 219 OptionValues options = new OptionValues(getInitialOptions(), DefaultLoopPolicies.Options.UnrollMaxIterations, 2); 220 StructuredGraph graph = parse(builder(method, StructuredGraph.AllowAssumptions.YES, id, options), getEagerGraphBuilderSuite()); 221 try (DebugContext.Scope buildScope = graph.getDebug().scope(name, method, graph)) { 222 MidTierContext context = new MidTierContext(getProviders(), getTargetProvider(), OptimisticOptimizations.ALL, null); 223 224 CanonicalizerPhase canonicalizer = new CanonicalizerPhase(); 225 canonicalizer.apply(graph, context); 226 new RemoveValueProxyPhase().apply(graph); 227 new LoweringPhase(canonicalizer, LoweringTool.StandardLoweringStage.HIGH_TIER).apply(graph, context); 228 new FloatingReadPhase().apply(graph); 229 new DeadCodeEliminationPhase().apply(graph); 230 new ConditionalEliminationPhase(true).apply(graph, context); 231 ComputeLoopFrequenciesClosure.compute(graph); 232 new GuardLoweringPhase().apply(graph, context); 233 new LoweringPhase(canonicalizer, LoweringTool.StandardLoweringStage.MID_TIER).apply(graph, context); 234 new FrameStateAssignmentPhase().apply(graph); 235 new DeoptimizationGroupingPhase().apply(graph, context); 236 canonicalizer.apply(graph, context); 237 new ConditionalEliminationPhase(true).apply(graph, context); 238 if (partialUnroll) { 239 LoopsData dataCounted = new LoopsData(graph); 240 dataCounted.detectedCountedLoops(); 241 for (LoopEx loop : dataCounted.countedLoops()) { 242 LoopFragmentInside newSegment = loop.inside().duplicate(); 243 newSegment.insertWithinAfter(loop, false); 244 } 245 canonicalizer.apply(graph, getDefaultMidTierContext()); 246 } 247 new DeadCodeEliminationPhase().apply(graph); 248 canonicalizer.apply(graph, context); 249 graph.getDebug().dump(DebugContext.BASIC_LEVEL, graph, "before compare"); 250 return graph; 251 } catch (Throwable e) { 252 throw getDebugContext().handle(e); 253 } 254 } 255 256 public void testDuplicateBody(String reference, String test) { 257 258 StructuredGraph referenceGraph = buildGraph(reference, false); 259 StructuredGraph testGraph = buildGraph(test, true); 260 CanonicalizerPhase canonicalizer = new CanonicalizerPhase(); 261 canonicalizer.apply(testGraph, getDefaultMidTierContext()); 262 canonicalizer.apply(referenceGraph, getDefaultMidTierContext()); 263 assertEquals(referenceGraph, testGraph); 264 } 265 }