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