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.hotspot.phases.profiling;
26
27 import static org.graalvm.compiler.hotspot.nodes.profiling.ProfileInvokeNode.getProfileInvokeNodes;
28 import static org.graalvm.compiler.hotspot.nodes.profiling.ProfileNode.getProfileNodes;
29
30 import java.util.HashMap;
31 import java.util.Map;
32
33 import org.graalvm.compiler.core.common.cfg.Loop;
34 import org.graalvm.compiler.hotspot.nodes.profiling.ProfileInvokeNode;
35 import org.graalvm.compiler.hotspot.nodes.profiling.ProfileNode;
36 import org.graalvm.compiler.hotspot.nodes.profiling.RandomSeedNode;
37 import org.graalvm.compiler.nodes.ConstantNode;
38 import org.graalvm.compiler.nodes.InvokeNode;
39 import org.graalvm.compiler.nodes.LoopBeginNode;
40 import org.graalvm.compiler.nodes.NodeView;
41 import org.graalvm.compiler.nodes.PhiNode;
42 import org.graalvm.compiler.nodes.StructuredGraph;
43 import org.graalvm.compiler.nodes.ValueNode;
44 import org.graalvm.compiler.nodes.ValuePhiNode;
45 import org.graalvm.compiler.nodes.calc.AddNode;
46 import org.graalvm.compiler.nodes.calc.MulNode;
47 import org.graalvm.compiler.nodes.cfg.Block;
48 import org.graalvm.compiler.nodes.cfg.ControlFlowGraph;
49 import org.graalvm.compiler.nodes.spi.CoreProviders;
50 import org.graalvm.compiler.nodes.util.GraphUtil;
51 import org.graalvm.compiler.options.Option;
52 import org.graalvm.compiler.options.OptionKey;
53 import org.graalvm.compiler.options.OptionType;
54 import org.graalvm.compiler.phases.BasePhase;
55
56 import jdk.vm.ci.meta.ResolvedJavaMethod;
57
58 public class FinalizeProfileNodesPhase extends BasePhase<CoreProviders> {
59 private int inlineeInvokeNotificationFreqLog;
60
61 public static class Options {
62 @Option(help = "Profile simple methods", type = OptionType.Expert)//
63 public static final OptionKey<Boolean> ProfileSimpleMethods = new OptionKey<>(true);
64 @Option(help = "Maximum number of nodes in a graph for a simple method", type = OptionType.Expert)//
65 public static final OptionKey<Integer> SimpleMethodGraphSize = new OptionKey<>(256);
66 @Option(help = "Maximum number of calls in a simple method", type = OptionType.Expert)//
67 public static final OptionKey<Integer> SimpleMethodCalls = new OptionKey<>(1);
68 @Option(help = "Maximum number of indirect calls in a simple moethod", type = OptionType.Expert)//
69 public static final OptionKey<Integer> SimpleMethodIndirectCalls = new OptionKey<>(0);
70
71 }
72
73 public FinalizeProfileNodesPhase(int inlineeInvokeNotificationFreqLog) {
74 this.inlineeInvokeNotificationFreqLog = inlineeInvokeNotificationFreqLog;
75 }
76
77 private static void removeAllProfilingNodes(StructuredGraph graph) {
78 getProfileNodes(graph).forEach((n) -> GraphUtil.removeFixedWithUnusedInputs(n));
79 }
80
81 private void assignInlineeInvokeFrequencies(StructuredGraph graph) {
82 for (ProfileInvokeNode node : getProfileInvokeNodes(graph)) {
83 ResolvedJavaMethod profiledMethod = node.getProfiledMethod();
84 if (!profiledMethod.equals(graph.method())) {
85 // Some inlinee, reassign the inlinee frequency
86 node.setNotificationFreqLog(inlineeInvokeNotificationFreqLog);
87 }
88 }
89 }
90
91 // Hacky heuristic to determine whether we want any profiling in this method.
92 // The heuristic is applied after the graph is fully formed and before the first lowering.
93 private static boolean simpleMethodHeuristic(StructuredGraph graph) {
94 if (Options.ProfileSimpleMethods.getValue(graph.getOptions())) {
95 return false;
96 }
97
98 // Check if the graph is smallish..
99 if (graph.getNodeCount() > Options.SimpleMethodGraphSize.getValue(graph.getOptions())) {
100 return false;
101 }
102
103 // Check if method has loops
104 if (graph.hasLoops()) {
105 return false;
106 }
107
108 // Check if method has calls
109 if (graph.getNodes().filter(InvokeNode.class).count() > Options.SimpleMethodCalls.getValue(graph.getOptions())) {
110 return false;
111 }
112
113 // Check if method has calls that need profiling
114 if (graph.getNodes().filter(InvokeNode.class).filter((n) -> ((InvokeNode) n).getInvokeKind().isIndirect()).count() > Options.SimpleMethodIndirectCalls.getDefaultValue()) {
115 return false;
116 }
117
118 return true;
119 }
120
121 private static void assignRandomSources(StructuredGraph graph) {
122 ValueNode seed = graph.unique(new RandomSeedNode());
123 ControlFlowGraph cfg = ControlFlowGraph.compute(graph, false, true, false, false);
124 Map<LoopBeginNode, ValueNode> loopRandomValueCache = new HashMap<>();
125
126 for (ProfileNode node : getProfileNodes(graph)) {
127 ValueNode random;
128 Block block = cfg.blockFor(node);
129 Loop<Block> loop = block.getLoop();
130 // Inject <a href=https://en.wikipedia.org/wiki/Linear_congruential_generator>LCG</a>
131 // pseudo-random number generator into the loop
132 if (loop != null) {
133 LoopBeginNode loopBegin = (LoopBeginNode) loop.getHeader().getBeginNode();
134 random = loopRandomValueCache.get(loopBegin);
135 if (random == null) {
136 PhiNode phi = graph.addWithoutUnique(new ValuePhiNode(seed.stamp(NodeView.DEFAULT), loopBegin));
137 phi.addInput(seed);
138 // X_{n+1} = a*X_n + c, using glibc-like constants
139 ValueNode a = ConstantNode.forInt(1103515245, graph);
140 ValueNode c = ConstantNode.forInt(12345, graph);
141 ValueNode next = graph.addOrUniqueWithInputs(new AddNode(c, new MulNode(phi, a)));
142 for (int i = 0; i < loopBegin.getLoopEndCount(); i++) {
143 phi.addInput(next);
144 }
145 random = phi;
146 loopRandomValueCache.put(loopBegin, random);
147 }
148 } else {
149 // Graal doesn't compile methods with irreducible loops. So all profile nodes that
150 // are not in a loop are guaranteed to be executed at most once. We feed the seed
151 // value to such nodes directly.
152 random = seed;
153 }
154 node.setRandom(random);
155 }
156 }
157
158 @Override
159 protected void run(StructuredGraph graph, CoreProviders context) {
160 if (simpleMethodHeuristic(graph)) {
161 removeAllProfilingNodes(graph);
162 return;
163 }
164
165 assignInlineeInvokeFrequencies(graph);
166 if (ProfileNode.Options.ProbabilisticProfiling.getValue(graph.getOptions())) {
167 assignRandomSources(graph);
168 }
169 }
170
171 @Override
172 public boolean checkContract() {
173 return false;
174 }
175 }