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.inlining;
26 
27 import static org.graalvm.compiler.phases.common.DeadCodeEliminationPhase.Optionality.Optional;
28 
29 import jdk.internal.vm.compiler.collections.EconomicSet;
30 import org.graalvm.compiler.core.test.GraalCompilerTest;
31 import org.graalvm.compiler.debug.DebugContext;
32 import org.graalvm.compiler.debug.TTY;
33 import org.graalvm.compiler.graph.Node;
34 import org.graalvm.compiler.nodes.Invoke;
35 import org.graalvm.compiler.nodes.StructuredGraph;
36 import org.graalvm.compiler.nodes.StructuredGraph.AllowAssumptions;
37 import org.graalvm.compiler.nodes.java.MethodCallTargetNode;
38 import org.graalvm.compiler.options.OptionValues;
39 import org.graalvm.compiler.phases.BasePhase;
40 import org.graalvm.compiler.phases.OptimisticOptimizations;
41 import org.graalvm.compiler.phases.PhaseSuite;
42 import org.graalvm.compiler.phases.common.CanonicalizerPhase;
43 import org.graalvm.compiler.phases.common.DeadCodeEliminationPhase;
44 import org.graalvm.compiler.phases.common.inlining.InliningUtil;
45 import org.graalvm.compiler.phases.tiers.HighTierContext;
46 import org.graalvm.compiler.phases.tiers.PhaseContext;
47 import org.graalvm.compiler.virtual.phases.ea.EarlyReadEliminationPhase;
48 import org.graalvm.compiler.virtual.phases.ea.PartialEscapePhase;
49 
50 import org.junit.Rule;
51 import org.junit.Test;
52 import org.junit.rules.TestRule;
53 
54 import jdk.vm.ci.meta.ResolvedJavaMethod;
55 import sun.misc.Unsafe;
56 
57 public class NestedLoopEffectsPhaseComplexityTest extends GraalCompilerTest {
58 
59     public static int IntSideEffect;
60     public static int[] Memory = new int[]{0};
61 
recursiveLoopMethodUnsafeLoad(int a)62     public static void recursiveLoopMethodUnsafeLoad(int a) {
63         long arrayIntBaseOffset = Unsafe.ARRAY_INT_BASE_OFFSET;
64         if (UNSAFE.getInt(Memory, arrayIntBaseOffset) == 0) {
65             return;
66         }
67         for (int i = 0; i < a; i++) {
68             recursiveLoopMethodUnsafeLoad(i);
69         }
70     }
71 
recursiveLoopMethodFieldLoad(int a)72     public static void recursiveLoopMethodFieldLoad(int a) {
73         if (IntSideEffect == 0) {
74             return;
75         }
76         for (int i = 0; i < a; i++) {
77             recursiveLoopMethodFieldLoad(i);
78         }
79     }
80 
recursiveLoopMethod(int a)81     public static void recursiveLoopMethod(int a) {
82         if (a == 0) {
83             return;
84         }
85         for (int i = 0; i < a; i++) {
86             recursiveLoopMethod(i);
87         }
88     }
89 
90     private static final boolean LOG_PHASE_TIMINGS = false;
91     private static int InliningCountLowerBound = 1;
92     private static int InliningCountUpperBound = 32;
93 
94     @Rule public TestRule timeout = createTimeoutSeconds(120);
95 
96     @Test
inlineDirectRecursiveLoopCallUnsafeLoad()97     public void inlineDirectRecursiveLoopCallUnsafeLoad() {
98         testAndTime("recursiveLoopMethodUnsafeLoad");
99     }
100 
101     @Test
inlineDirectRecursiveLoopCallFieldLoad()102     public void inlineDirectRecursiveLoopCallFieldLoad() {
103         testAndTime("recursiveLoopMethodFieldLoad");
104     }
105 
106     @Test
inlineDirectRecursiveLoopCallNoReads()107     public void inlineDirectRecursiveLoopCallNoReads() {
108         testAndTime("recursiveLoopMethod");
109     }
110 
testAndTime(String snippet)111     private void testAndTime(String snippet) {
112         for (int i = InliningCountLowerBound; i < InliningCountUpperBound; i++) {
113             StructuredGraph g1 = prepareGraph(snippet, i);
114             StructuredGraph g2 = (StructuredGraph) g1.copy(g1.getDebug());
115             ResolvedJavaMethod method = g1.method();
116             long elapsedRE = runAndTimePhase(g1, new EarlyReadEliminationPhase(new CanonicalizerPhase()));
117             long elapsedPEA = runAndTimePhase(g2, new PartialEscapePhase(true, new CanonicalizerPhase(), g1.getOptions()));
118             if (LOG_PHASE_TIMINGS) {
119                 TTY.printf("Needed %dms to run early partial escape analysis on a graph with %d nested loops compiling method %s\n", elapsedPEA, i, method);
120             }
121             if (LOG_PHASE_TIMINGS) {
122                 TTY.printf("Needed %dms to run early read elimination on a graph with %d nested loops compiling method %s\n", elapsedRE, i, method);
123             }
124         }
125     }
126 
runAndTimePhase(StructuredGraph g, BasePhase<? super PhaseContext> phase)127     private long runAndTimePhase(StructuredGraph g, BasePhase<? super PhaseContext> phase) {
128         HighTierContext context = getDefaultHighTierContext();
129         long start = System.currentTimeMillis();
130         phase.apply(g, context);
131         long end = System.currentTimeMillis();
132         DebugContext debug = g.getDebug();
133         debug.dump(DebugContext.DETAILED_LEVEL, g, "After %s", phase.contractorName());
134         return end - start;
135     }
136 
prepareGraph(String snippet, int inliningCount)137     private StructuredGraph prepareGraph(String snippet, int inliningCount) {
138         ResolvedJavaMethod callerMethod = getResolvedJavaMethod(snippet);
139         StructuredGraph callerGraph = parseEager(callerMethod, AllowAssumptions.YES);
140         PhaseSuite<HighTierContext> graphBuilderSuite = getDefaultGraphBuilderSuite();
141         HighTierContext context = new HighTierContext(getProviders(), graphBuilderSuite, OptimisticOptimizations.ALL);
142         CanonicalizerPhase canonicalizer = new CanonicalizerPhase();
143         Invoke next = callerGraph.getNodes(MethodCallTargetNode.TYPE).first().invoke();
144         StructuredGraph calleeGraph = parseBytecodes(next.callTarget().targetMethod(), context, canonicalizer);
145         ResolvedJavaMethod calleeMethod = next.callTarget().targetMethod();
146         for (int i = 0; i < inliningCount; i++) {
147             next = callerGraph.getNodes(MethodCallTargetNode.TYPE).first().invoke();
148             EconomicSet<Node> canonicalizeNodes = InliningUtil.inlineForCanonicalization(next, calleeGraph, false, calleeMethod, null,
149                             "Called explicitly from a unit test.", "Test case");
150             canonicalizer.applyIncremental(callerGraph, context, canonicalizeNodes);
151             callerGraph.getDebug().dump(DebugContext.DETAILED_LEVEL, callerGraph, "After inlining %s into %s iteration %d", calleeMethod, callerMethod, i);
152         }
153         return callerGraph;
154     }
155 
parseBytecodes(ResolvedJavaMethod method, HighTierContext context, CanonicalizerPhase canonicalizer)156     private StructuredGraph parseBytecodes(ResolvedJavaMethod method, HighTierContext context, CanonicalizerPhase canonicalizer) {
157         OptionValues options = getInitialOptions();
158         StructuredGraph newGraph = new StructuredGraph.Builder(options, getDebugContext(options, null, method), AllowAssumptions.NO).method(method).build();
159         context.getGraphBuilderSuite().apply(newGraph, context);
160         new DeadCodeEliminationPhase(Optional).apply(newGraph);
161         canonicalizer.apply(newGraph, context);
162         return newGraph;
163     }
164 
165 }
166