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.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 }