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