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 }

  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.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) {
  84             return new TrivialTraceAllocator();
  85         }
  86     }
  87 
  88     public static class BottomUpStrategy extends AllocationStrategy {
  89 
  90         public BottomUpStrategy(TraceRegisterAllocationPolicy plan) {
  91             // explicitly specify the enclosing instance for the superclass constructor call
  92             plan.super();
  93         }
  94 
  95         @Override
  96         public boolean shouldApplyTo(Trace trace) {
  97             return !containsExceptionEdge(trace);
  98         }
  99 
 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 }