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.lir.alloc.trace;
24
25 import java.util.ArrayList;
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.EnumOptionValue;
38 import org.graalvm.compiler.options.Option;
39 import org.graalvm.compiler.options.OptionType;
40 import org.graalvm.compiler.options.StableOptionValue;
41
42 import jdk.vm.ci.code.TargetDescription;
43 import jdk.vm.ci.common.JVMCIError;
44 import jdk.vm.ci.meta.AllocatableValue;
45
46 /**
47 * Manages the selection of allocation strategies.
48 */
49 public final class DefaultTraceRegisterAllocationPolicy {
50
51 public enum TraceRAPolicies {
52 Default,
53 LinearScanOnly,
54 BottomUpOnly
55 }
56
57 public static class Options {
58 // @formatter:off
59 @Option(help = "Use special allocator for trivial blocks.", type = OptionType.Debug)
60 public static final StableOptionValue<Boolean> TraceRAtrivialBlockAllocator = new StableOptionValue<>(true);
61 @Option(help = "Use LSRA / BottomUp ratio", type = OptionType.Debug)
62 public static final StableOptionValue<Double> TraceRAbottomUpRatio = new StableOptionValue<>(0.0);
63 @Option(help = "TraceRA allocation policy to use.", type = OptionType.Debug)
64 public static final EnumOptionValue<TraceRAPolicies> TraceRAPolicy = new EnumOptionValue<>(TraceRAPolicies.Default);
65 // @formatter:on
66 }
67
68 public static final class TrivialTraceStrategy extends AllocationStrategy {
69
70 public TrivialTraceStrategy(TraceRegisterAllocationPolicy plan) {
71 plan.super();
72 }
73
74 @Override
75 public boolean shouldApplyTo(Trace trace) {
76 return TraceUtil.isTrivialTrace(getLIR(), trace);
77 }
78
79 @Override
80 protected TraceAllocationPhase<TraceAllocationContext> initAllocator(TargetDescription target, LIRGenerationResult lirGenRes, MoveFactory spillMoveFactory,
81 RegisterAllocationConfig registerAllocationConfig, AllocatableValue[] cachedStackSlots, TraceBuilderResult resultTraces, boolean neverSpillConstant,
82 ArrayList<AllocationStrategy> strategies) {
83 return new TrivialTraceAllocator();
84 }
85 }
86
87 public static class BottomUpStrategy extends AllocationStrategy {
88
89 public BottomUpStrategy(TraceRegisterAllocationPolicy plan) {
90 // explicitly specify the enclosing instance for the superclass constructor call
91 plan.super();
92 }
93
94 @Override
95 public boolean shouldApplyTo(Trace trace) {
96 return !containsExceptionEdge(trace);
97 }
98
99 private static boolean containsExceptionEdge(Trace trace) {
100 for (AbstractBlockBase<?> block : trace.getBlocks()) {
101 // check if one of the successors is an exception handler
102 for (AbstractBlockBase<?> succ : block.getSuccessors()) {
103 if (succ.isExceptionEntry()) {
104 return true;
105 }
106 }
107 }
108 return false;
109 }
110
111 @Override
112 protected TraceAllocationPhase<TraceAllocationContext> initAllocator(TargetDescription target, LIRGenerationResult lirGenRes, MoveFactory spillMoveFactory,
113 RegisterAllocationConfig registerAllocationConfig, AllocatableValue[] cachedStackSlots, TraceBuilderResult resultTraces, boolean neverSpillConstant,
114 ArrayList<AllocationStrategy> strategies) {
115 return new BottomUpAllocator(target, lirGenRes, spillMoveFactory, registerAllocationConfig, cachedStackSlots, resultTraces, neverSpillConstant);
116 }
117 }
118
119 public static final class TraceLinearScanStrategy extends AllocationStrategy {
120
121 public TraceLinearScanStrategy(TraceRegisterAllocationPolicy plan) {
122 // explicitly specify the enclosing instance for the superclass constructor call
123 plan.super();
124 }
125
126 @Override
127 public boolean shouldApplyTo(Trace trace) {
128 return true;
129 }
130
131 @Override
132 protected TraceAllocationPhase<TraceAllocationContext> initAllocator(TargetDescription target, LIRGenerationResult lirGenRes, MoveFactory spillMoveFactory,
133 RegisterAllocationConfig registerAllocationConfig, AllocatableValue[] cachedStackSlots, TraceBuilderResult resultTraces, boolean neverSpillConstant,
134 ArrayList<AllocationStrategy> strategies) {
135 return new TraceLinearScanPhase(target, lirGenRes, spillMoveFactory, registerAllocationConfig, resultTraces, neverSpillConstant, cachedStackSlots);
136 }
137 }
138
139 public static TraceRegisterAllocationPolicy allocationPolicy(TargetDescription target, LIRGenerationResult lirGenRes, MoveFactory spillMoveFactory,
140 RegisterAllocationConfig registerAllocationConfig, AllocatableValue[] cachedStackSlots, TraceBuilderResult resultTraces, boolean neverSpillConstant) {
141 TraceRegisterAllocationPolicy plan = new TraceRegisterAllocationPolicy(target, lirGenRes, spillMoveFactory, registerAllocationConfig, cachedStackSlots, resultTraces, neverSpillConstant);
142 if (Options.TraceRAtrivialBlockAllocator.getValue()) {
143 plan.appendStrategy(new TrivialTraceStrategy(plan));
144 }
145 switch (Options.TraceRAPolicy.getValue()) {
146 case Default:
147 case LinearScanOnly:
148 plan.appendStrategy(new TraceLinearScanStrategy(plan));
149 break;
150 case BottomUpOnly:
151 plan.appendStrategy(new BottomUpStrategy(plan));
152 // Fallback
153 plan.appendStrategy(new TraceLinearScanStrategy(plan));
154 break;
155 default:
156 throw JVMCIError.shouldNotReachHere();
157 }
158 return plan;
159 }
160 }