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