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 }