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