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
24
25 package org.graalvm.compiler.lir.alloc.trace;
26
27 import java.util.ArrayList;
28
29 import org.graalvm.compiler.core.common.alloc.RegisterAllocationConfig;
30 import org.graalvm.compiler.core.common.alloc.Trace;
31 import org.graalvm.compiler.core.common.alloc.TraceBuilderResult;
32 import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
33 import org.graalvm.compiler.lir.alloc.trace.TraceAllocationPhase.TraceAllocationContext;
34 import org.graalvm.compiler.lir.alloc.trace.TraceRegisterAllocationPolicy.AllocationStrategy;
35 import org.graalvm.compiler.lir.alloc.trace.bu.BottomUpAllocator;
36 import org.graalvm.compiler.lir.alloc.trace.lsra.TraceLinearScanPhase;
37 import org.graalvm.compiler.lir.gen.LIRGenerationResult;
38 import org.graalvm.compiler.lir.gen.LIRGeneratorTool.MoveFactory;
39 import org.graalvm.compiler.options.EnumOptionKey;
40 import org.graalvm.compiler.options.Option;
41 import org.graalvm.compiler.options.OptionKey;
42 import org.graalvm.compiler.options.OptionType;
43 import org.graalvm.compiler.options.OptionValues;
44
45 import jdk.vm.ci.code.TargetDescription;
46 import jdk.vm.ci.common.JVMCIError;
47 import jdk.vm.ci.meta.AllocatableValue;
48 import jdk.vm.ci.meta.PlatformKind;
49
50 /**
51 * Manages the selection of allocation strategies.
52 */
53 public final class DefaultTraceRegisterAllocationPolicy {
54
55 public enum TraceRAPolicies {
56 Default,
57 LinearScanOnly,
58 BottomUpOnly,
59 AlmostTrivial,
60 NumVariables,
61 Ratio,
62 Loops,
63 MaxFreq,
64 FreqBudget,
65 LoopRatio,
66 LoopBudget,
67 LoopMaxFreq
68 }
69
70 public static class Options {
71 // @formatter:off
72 @Option(help = "Use special allocator for trivial blocks.", type = OptionType.Debug)
73 public static final OptionKey<Boolean> TraceRAtrivialBlockAllocator = new OptionKey<>(true);
74 @Option(help = "Use BottomUp if there is only one block with at most this number of instructions", type = OptionType.Debug)
75 public static final OptionKey<Integer> TraceRAalmostTrivialSize = new OptionKey<>(2);
76 @Option(help = "Use BottomUp for traces with low number of variables at block boundaries", type = OptionType.Debug)
77 public static final OptionKey<Integer> TraceRAnumVariables = new OptionKey<>(null);
78 @Option(help = "Use LSRA / BottomUp ratio", type = OptionType.Debug)
79 public static final OptionKey<Double> TraceRAbottomUpRatio = new OptionKey<>(0.0);
80 @Option(help = "Probability Threshold", type = OptionType.Debug)
81 public static final OptionKey<Double> TraceRAprobalilityThreshold = new OptionKey<>(0.8);
82 @Option(help = "Sum Probability Budget Threshold", type = OptionType.Debug)
83 public static final OptionKey<Double> TraceRAsumBudget = new OptionKey<>(0.5);
84 @Option(help = "TraceRA allocation policy to use.", type = OptionType.Debug)
85 public static final EnumOptionKey<TraceRAPolicies> TraceRAPolicy = new EnumOptionKey<>(TraceRAPolicies.Default);
86 // @formatter:on
87 }
88
89 public static final class TrivialTraceStrategy extends AllocationStrategy {
90
91 public TrivialTraceStrategy(TraceRegisterAllocationPolicy plan) {
92 plan.super();
93 }
94
95 @Override
96 public boolean shouldApplyTo(Trace trace) {
97 return TraceUtil.isTrivialTrace(getLIR(), trace);
98 }
99
100 @Override
101 protected TraceAllocationPhase<TraceAllocationContext> initAllocator(TargetDescription target, LIRGenerationResult lirGenRes, MoveFactory spillMoveFactory,
102 RegisterAllocationConfig registerAllocationConfig, AllocatableValue[] cachedStackSlots, TraceBuilderResult resultTraces, boolean neverSpillConstant,
103 GlobalLivenessInfo livenessInfo, ArrayList<AllocationStrategy> strategies) {
104 return new TrivialTraceAllocator();
105 }
106 }
107
108 public static class BottomUpStrategy extends AllocationStrategy {
109
110 public BottomUpStrategy(TraceRegisterAllocationPolicy plan) {
111 // explicitly specify the enclosing instance for the superclass constructor call
112 plan.super();
113 }
114
115 @Override
116 public boolean shouldApplyTo(Trace trace) {
117 return !containsExceptionEdge(trace);
118 }
119
120 private static boolean containsExceptionEdge(Trace trace) {
121 for (AbstractBlockBase<?> block : trace.getBlocks()) {
122 // check if one of the successors is an exception handler
123 for (AbstractBlockBase<?> succ : block.getSuccessors()) {
124 if (succ.isExceptionEntry()) {
125 return true;
126 }
127 }
128 }
129 return false;
130 }
131
132 @Override
133 protected TraceAllocationPhase<TraceAllocationContext> initAllocator(TargetDescription target, LIRGenerationResult lirGenRes, MoveFactory spillMoveFactory,
134 RegisterAllocationConfig registerAllocationConfig, AllocatableValue[] cachedStackSlots, TraceBuilderResult resultTraces, boolean neverSpillConstant,
135 GlobalLivenessInfo livenessInfo, ArrayList<AllocationStrategy> strategies) {
136 return new BottomUpAllocator(target, lirGenRes, spillMoveFactory, registerAllocationConfig, cachedStackSlots, resultTraces, neverSpillConstant, livenessInfo);
137 }
138 }
139
140 public static final class BottomUpAlmostTrivialStrategy extends BottomUpStrategy {
141
142 private final int trivialTraceSize;
143
144 public BottomUpAlmostTrivialStrategy(TraceRegisterAllocationPolicy plan) {
145 // explicitly specify the enclosing instance for the superclass constructor call
146 super(plan);
147 trivialTraceSize = Options.TraceRAalmostTrivialSize.getValue(plan.getOptions());
148 }
149
150 @Override
151 public boolean shouldApplyTo(Trace trace) {
152 if (!super.shouldApplyTo(trace)) {
153 return false;
154 }
155 if (trace.size() != 1) {
156 return false;
157 }
158 return getLIR().getLIRforBlock(trace.getBlocks()[0]).size() <= trivialTraceSize;
159 }
160
161 }
162
163 public static final class BottomUpNumVariablesStrategy extends BottomUpStrategy {
164
165 private final int numVarLimit;
166
167 public BottomUpNumVariablesStrategy(TraceRegisterAllocationPolicy plan) {
168 // explicitly specify the enclosing instance for the superclass constructor call
169 super(plan);
170 Integer value = Options.TraceRAnumVariables.getValue(plan.getOptions());
171 if (value != null) {
172 numVarLimit = value;
173 } else {
174 /* Default to the number of allocatable word registers. */
175 PlatformKind wordKind = getTarget().arch.getWordKind();
176 int numWordRegisters = getRegisterAllocationConfig().getAllocatableRegisters(wordKind).allocatableRegisters.length;
177 numVarLimit = numWordRegisters;
178 }
179 }
180
181 @Override
182 public boolean shouldApplyTo(Trace trace) {
183 if (!super.shouldApplyTo(trace)) {
184 return false;
185 }
186 GlobalLivenessInfo livenessInfo = getGlobalLivenessInfo();
187 int maxNumVars = livenessInfo.getBlockIn(trace.getBlocks()[0]).length;
188 for (AbstractBlockBase<?> block : trace.getBlocks()) {
189 maxNumVars = Math.max(maxNumVars, livenessInfo.getBlockOut(block).length);
190 }
191 return maxNumVars <= numVarLimit;
192 }
193
194 }
195
196 public static final class BottomUpRatioStrategy extends BottomUpStrategy {
197
198 private final double ratio;
199
200 public BottomUpRatioStrategy(TraceRegisterAllocationPolicy plan) {
201 // explicitly specify the enclosing instance for the superclass constructor call
202 super(plan);
203 ratio = Options.TraceRAbottomUpRatio.getValue(plan.getOptions());
204 }
205
206 @Override
207 public boolean shouldApplyTo(Trace trace) {
208 if (!super.shouldApplyTo(trace)) {
209 return false;
210 }
211 double numTraces = getTraceBuilderResult().getTraces().size();
212 double traceId = trace.getId();
213 assert ratio >= 0 && ratio <= 1.0 : "Ratio out of range: " + ratio;
214 return (traceId / numTraces) >= ratio;
215 }
216
217 }
218
219 public abstract static class BottomUpLoopStrategyBase extends BottomUpStrategy {
220
221 public BottomUpLoopStrategyBase(TraceRegisterAllocationPolicy plan) {
222 // explicitly specify the enclosing instance for the superclass constructor call
223 super(plan);
224 }
225
226 @Override
227 public final boolean shouldApplyTo(Trace trace) {
228 if (!super.shouldApplyTo(trace)) {
229 return false;
230 }
231 if (getLIR().getControlFlowGraph().getLoops().isEmpty()) {
232 return shouldApplyToNoLoop(trace);
233 }
234 for (AbstractBlockBase<?> block : trace.getBlocks()) {
235 if (block.getLoopDepth() > 0) {
236 return false;
237 }
238 }
239 return true;
240 }
241
242 protected abstract boolean shouldApplyToNoLoop(Trace trace);
243
244 }
245
246 public static final class BottomUpLoopStrategy extends BottomUpLoopStrategyBase {
247
248 public BottomUpLoopStrategy(TraceRegisterAllocationPolicy plan) {
249 // explicitly specify the enclosing instance for the superclass constructor call
250 super(plan);
251 }
252
253 @Override
254 protected boolean shouldApplyToNoLoop(Trace trace) {
255 // no loops at all -> use LSRA
256 return false;
257 }
258
259 }
260
261 public static final class BottomUpDelegatingLoopStrategy extends BottomUpLoopStrategyBase {
262
263 private final BottomUpStrategy delegate;
264
265 public BottomUpDelegatingLoopStrategy(TraceRegisterAllocationPolicy plan, BottomUpStrategy delegate) {
266 // explicitly specify the enclosing instance for the superclass constructor call
267 super(plan);
268 this.delegate = delegate;
269 }
270
271 @Override
272 protected boolean shouldApplyToNoLoop(Trace trace) {
273 return delegate.shouldApplyTo(trace);
274 }
275
276 }
277
278 public static final class BottomUpMaxFrequencyStrategy extends BottomUpStrategy {
279
280 private final double maxMethodProbability;
281 private final double probabilityThreshold;
282
283 public BottomUpMaxFrequencyStrategy(TraceRegisterAllocationPolicy plan) {
284 // explicitly specify the enclosing instance for the superclass constructor call
285 super(plan);
286 maxMethodProbability = maxProbability(getLIR().getControlFlowGraph().getBlocks());
287 probabilityThreshold = Options.TraceRAprobalilityThreshold.getValue(plan.getOptions());
288 }
289
290 private static double maxProbability(AbstractBlockBase<?>[] blocks) {
291 double max = 0;
292 for (AbstractBlockBase<?> block : blocks) {
293 double probability = block.probability();
294 if (probability > max) {
295 max = probability;
296 }
297 }
298 return max;
299 }
300
301 @Override
302 public boolean shouldApplyTo(Trace trace) {
303 if (!super.shouldApplyTo(trace)) {
304 return false;
305 }
306 return maxProbability(trace.getBlocks()) / maxMethodProbability <= probabilityThreshold;
307 }
308
309 }
310
311 public static final class BottomUpFrequencyBudgetStrategy extends BottomUpStrategy {
312
313 private final double[] cumulativeTraceProbability;
314 private final double budget;
315
316 public BottomUpFrequencyBudgetStrategy(TraceRegisterAllocationPolicy plan) {
317 // explicitly specify the enclosing instance for the superclass constructor call
318 super(plan);
319 ArrayList<Trace> traces = getTraceBuilderResult().getTraces();
320 this.cumulativeTraceProbability = new double[traces.size()];
321 double sumMethodProbability = init(traces, this.cumulativeTraceProbability);
322 this.budget = sumMethodProbability * Options.TraceRAsumBudget.getValue(plan.getOptions());
323 }
324
325 private static double init(ArrayList<Trace> traces, double[] sumTraces) {
326 double sumMethod = 0;
327 for (Trace trace : traces) {
328 double traceSum = 0;
329 for (AbstractBlockBase<?> block : trace.getBlocks()) {
330 traceSum += block.probability();
331 }
332 sumMethod += traceSum;
333 // store cumulative sum for trace
334 sumTraces[trace.getId()] = sumMethod;
335 }
336 return sumMethod;
337 }
338
339 @Override
340 public boolean shouldApplyTo(Trace trace) {
341 if (!super.shouldApplyTo(trace)) {
342 return false;
343 }
344 double cumTraceProb = cumulativeTraceProbability[trace.getId()];
345 return cumTraceProb > budget;
346 }
347
348 }
349
350 public static final class TraceLinearScanStrategy extends AllocationStrategy {
351
352 public TraceLinearScanStrategy(TraceRegisterAllocationPolicy plan) {
353 // explicitly specify the enclosing instance for the superclass constructor call
354 plan.super();
355 }
356
357 @Override
358 public boolean shouldApplyTo(Trace trace) {
359 return true;
360 }
361
362 @Override
363 protected TraceAllocationPhase<TraceAllocationContext> initAllocator(TargetDescription target, LIRGenerationResult lirGenRes, MoveFactory spillMoveFactory,
364 RegisterAllocationConfig registerAllocationConfig, AllocatableValue[] cachedStackSlots, TraceBuilderResult resultTraces, boolean neverSpillConstant,
365 GlobalLivenessInfo livenessInfo, ArrayList<AllocationStrategy> strategies) {
366 return new TraceLinearScanPhase(target, lirGenRes, spillMoveFactory, registerAllocationConfig, resultTraces, neverSpillConstant, cachedStackSlots, livenessInfo);
367 }
368
369 }
370
371 public static TraceRegisterAllocationPolicy allocationPolicy(TargetDescription target, LIRGenerationResult lirGenRes, MoveFactory spillMoveFactory,
372 RegisterAllocationConfig registerAllocationConfig, AllocatableValue[] cachedStackSlots, TraceBuilderResult resultTraces, boolean neverSpillConstant,
373 GlobalLivenessInfo livenessInfo, OptionValues options) {
374 TraceRegisterAllocationPolicy plan = new TraceRegisterAllocationPolicy(target, lirGenRes, spillMoveFactory, registerAllocationConfig, cachedStackSlots, resultTraces, neverSpillConstant,
375 livenessInfo);
376 if (Options.TraceRAtrivialBlockAllocator.getValue(options)) {
377 plan.appendStrategy(new TrivialTraceStrategy(plan));
378 }
379 switch (Options.TraceRAPolicy.getValue(options)) {
380 case Default:
381 case LinearScanOnly:
382 break;
383 case BottomUpOnly:
384 plan.appendStrategy(new BottomUpStrategy(plan));
385 break;
386 case AlmostTrivial:
387 plan.appendStrategy(new BottomUpAlmostTrivialStrategy(plan));
388 break;
389 case NumVariables:
390 plan.appendStrategy(new BottomUpNumVariablesStrategy(plan));
391 break;
392 case Ratio:
393 plan.appendStrategy(new BottomUpRatioStrategy(plan));
394 break;
395 case Loops:
396 plan.appendStrategy(new BottomUpLoopStrategy(plan));
397 break;
398 case MaxFreq:
399 plan.appendStrategy(new BottomUpMaxFrequencyStrategy(plan));
400 break;
401 case FreqBudget:
402 plan.appendStrategy(new BottomUpFrequencyBudgetStrategy(plan));
403 break;
404 case LoopRatio:
405 plan.appendStrategy(new BottomUpDelegatingLoopStrategy(plan, new BottomUpRatioStrategy(plan)));
406 break;
407 case LoopMaxFreq:
408 plan.appendStrategy(new BottomUpDelegatingLoopStrategy(plan, new BottomUpMaxFrequencyStrategy(plan)));
409 break;
410 case LoopBudget:
411 plan.appendStrategy(new BottomUpDelegatingLoopStrategy(plan, new BottomUpFrequencyBudgetStrategy(plan)));
412 break;
413 default:
414 throw JVMCIError.shouldNotReachHere();
415 }
416 // Fallback
417 plan.appendStrategy(new TraceLinearScanStrategy(plan));
418 return plan;
419 }
420 }