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