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 org.graalvm.compiler.core.common.alloc.RegisterAllocationConfig;
  26 import org.graalvm.compiler.core.common.alloc.Trace;
  27 import org.graalvm.compiler.core.common.alloc.TraceBuilderResult;
  28 import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
  29 import org.graalvm.compiler.debug.Debug;
  30 import org.graalvm.compiler.debug.Debug.Scope;
  31 import org.graalvm.compiler.debug.DebugCounter;
  32 import org.graalvm.compiler.debug.Indent;
  33 import org.graalvm.compiler.lir.LIR;
  34 import org.graalvm.compiler.lir.LIRInstruction;
  35 import org.graalvm.compiler.lir.alloc.trace.TraceAllocationPhase.TraceAllocationContext;
  36 import org.graalvm.compiler.lir.gen.LIRGenerationResult;
  37 import org.graalvm.compiler.lir.gen.LIRGeneratorTool.MoveFactory;
  38 import org.graalvm.compiler.lir.phases.AllocationPhase;
  39 import org.graalvm.compiler.lir.ssi.SSIUtil;
  40 import org.graalvm.compiler.lir.ssi.SSIVerifier;
  41 import org.graalvm.compiler.options.Option;

  42 import org.graalvm.compiler.options.OptionType;
  43 import org.graalvm.compiler.options.StableOptionValue;
  44 
  45 import jdk.vm.ci.code.TargetDescription;
  46 import jdk.vm.ci.meta.AllocatableValue;
  47 
  48 /**
  49  * Implements the Trace Register Allocation approach as described in
  50  * <a href="http://dx.doi.org/10.1145/2972206.2972211">"Trace-based Register Allocation in a JIT
  51  * Compiler"</a> by Josef Eisl et al.
  52  */
  53 public final class TraceRegisterAllocationPhase extends AllocationPhase {
  54 
  55     public static class Options {
  56         // @formatter:off
  57         @Option(help = "Use inter-trace register hints.", type = OptionType.Debug)
  58         public static final StableOptionValue<Boolean> TraceRAuseInterTraceHints = new StableOptionValue<>(true);
  59         @Option(help = "Share information about spilled values to other traces.", type = OptionType.Debug)
  60         public static final StableOptionValue<Boolean> TraceRAshareSpillInformation = new StableOptionValue<>(true);
  61         @Option(help = "Reuse spill slots for global move resolution cycle breaking.", type = OptionType.Debug)
  62         public static final StableOptionValue<Boolean> TraceRAreuseStackSlotsForMoveResolutionCycleBreaking = new StableOptionValue<>(true);
  63         @Option(help = "Cache stack slots globally (i.e. a variable always gets the same slot in every trace).", type = OptionType.Debug)
  64         public static final StableOptionValue<Boolean> TraceRACacheStackSlots = new StableOptionValue<>(true);
  65         // @formatter:on
  66     }
  67 
  68     private static final TraceGlobalMoveResolutionPhase TRACE_GLOBAL_MOVE_RESOLUTION_PHASE = new TraceGlobalMoveResolutionPhase();
  69 
  70     private static final DebugCounter tracesCounter = Debug.counter("TraceRA[traces]");
  71 
  72     public static final DebugCounter globalStackSlots = Debug.counter("TraceRA[GlobalStackSlots]");
  73     public static final DebugCounter allocatedStackSlots = Debug.counter("TraceRA[AllocatedStackSlots]");
  74 
  75     @Override
  76     @SuppressWarnings("try")
  77     protected void run(TargetDescription target, LIRGenerationResult lirGenRes, AllocationContext context) {
  78         MoveFactory spillMoveFactory = context.spillMoveFactory;
  79         RegisterAllocationConfig registerAllocationConfig = context.registerAllocationConfig;
  80         LIR lir = lirGenRes.getLIR();
  81         assert SSIVerifier.verify(lir) : "LIR not in SSI form.";
  82         TraceBuilderResult resultTraces = context.contextLookup(TraceBuilderResult.class);
  83 
  84         TraceAllocationContext traceContext = new TraceAllocationContext(spillMoveFactory, registerAllocationConfig, resultTraces);
  85         AllocatableValue[] cachedStackSlots = Options.TraceRACacheStackSlots.getValue() ? new AllocatableValue[lir.numVariables()] : null;

  86 
  87         // currently this is not supported
  88         boolean neverSpillConstant = false;
  89 
  90         final TraceRegisterAllocationPolicy plan = DefaultTraceRegisterAllocationPolicy.allocationPolicy(target, lirGenRes, spillMoveFactory, registerAllocationConfig, cachedStackSlots,
  91                         resultTraces, neverSpillConstant);
  92 
  93         Debug.dump(Debug.INFO_LOG_LEVEL, lir, "Before TraceRegisterAllocation");
  94         try (Scope s0 = Debug.scope("AllocateTraces", resultTraces)) {
  95             for (Trace trace : resultTraces.getTraces()) {
  96                 tracesCounter.increment();
  97                 TraceAllocationPhase<TraceAllocationContext> allocator = plan.selectStrategy(trace);
  98                 try (Indent i = Debug.logAndIndent("Allocating Trace%d: %s (%s)", trace.getId(), trace, allocator); Scope s = Debug.scope("AllocateTrace", trace)) {
  99                     allocator.apply(target, lirGenRes, trace, traceContext);
 100                 }
 101             }
 102         } catch (Throwable e) {
 103             throw Debug.handle(e);
 104         }
 105         if (Debug.isDumpEnabled(Debug.INFO_LOG_LEVEL)) {
 106             unnumberInstructions(lir);
 107             Debug.dump(Debug.INFO_LOG_LEVEL, lir, "After trace allocation");
 108         }
 109 
 110         TRACE_GLOBAL_MOVE_RESOLUTION_PHASE.apply(target, lirGenRes, traceContext);
 111         deconstructSSIForm(lir);
 112     }
 113 
 114     /**
 115      * Remove Phi/Sigma In/Out.
 116      *
 117      * Note: Incoming Values are needed for the RegisterVerifier, otherwise SIGMAs/PHIs where the
 118      * Out and In value matches (ie. there is no resolution move) are falsely detected as errors.
 119      */
 120     @SuppressWarnings("try")
 121     private static void deconstructSSIForm(LIR lir) {
 122         for (AbstractBlockBase<?> block : lir.getControlFlowGraph().getBlocks()) {
 123             try (Indent i = Debug.logAndIndent("Fixup Block %s", block)) {
 124                 if (block.getPredecessorCount() != 0) {
 125                     SSIUtil.removeIncoming(lir, block);
 126                 } else {
 127                     assert lir.getControlFlowGraph().getStartBlock().equals(block);
 128                 }
 129                 SSIUtil.removeOutgoing(lir, block);
 130             }
 131         }
 132     }
 133 
 134     private static void unnumberInstructions(LIR lir) {
 135         for (AbstractBlockBase<?> block : lir.getControlFlowGraph().getBlocks()) {
 136             for (LIRInstruction op : lir.getLIRforBlock(block)) {
 137                 op.setId(-1);
 138             }
 139         }
 140     }
 141 }

  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 org.graalvm.compiler.core.common.alloc.RegisterAllocationConfig;
  26 import org.graalvm.compiler.core.common.alloc.Trace;
  27 import org.graalvm.compiler.core.common.alloc.TraceBuilderResult;
  28 import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
  29 import org.graalvm.compiler.debug.Debug;
  30 import org.graalvm.compiler.debug.Debug.Scope;
  31 import org.graalvm.compiler.debug.DebugCounter;
  32 import org.graalvm.compiler.debug.Indent;
  33 import org.graalvm.compiler.lir.LIR;
  34 import org.graalvm.compiler.lir.LIRInstruction;
  35 import org.graalvm.compiler.lir.alloc.trace.TraceAllocationPhase.TraceAllocationContext;
  36 import org.graalvm.compiler.lir.gen.LIRGenerationResult;
  37 import org.graalvm.compiler.lir.gen.LIRGeneratorTool.MoveFactory;
  38 import org.graalvm.compiler.lir.phases.AllocationPhase;
  39 import org.graalvm.compiler.lir.ssa.SSAUtil;

  40 import org.graalvm.compiler.options.Option;
  41 import org.graalvm.compiler.options.OptionKey;
  42 import org.graalvm.compiler.options.OptionType;

  43 
  44 import jdk.vm.ci.code.TargetDescription;
  45 import jdk.vm.ci.meta.AllocatableValue;
  46 
  47 /**
  48  * Implements the Trace Register Allocation approach as described in
  49  * <a href="http://dx.doi.org/10.1145/2972206.2972211">"Trace-based Register Allocation in a JIT
  50  * Compiler"</a> by Josef Eisl et al.
  51  */
  52 public final class TraceRegisterAllocationPhase extends AllocationPhase {
  53 
  54     public static class Options {
  55         // @formatter:off
  56         @Option(help = "Use inter-trace register hints.", type = OptionType.Debug)
  57         public static final OptionKey<Boolean> TraceRAuseInterTraceHints = new OptionKey<>(true);
  58         @Option(help = "Share information about spilled values to other traces.", type = OptionType.Debug)
  59         public static final OptionKey<Boolean> TraceRAshareSpillInformation = new OptionKey<>(true);
  60         @Option(help = "Reuse spill slots for global move resolution cycle breaking.", type = OptionType.Debug)
  61         public static final OptionKey<Boolean> TraceRAreuseStackSlotsForMoveResolutionCycleBreaking = new OptionKey<>(true);
  62         @Option(help = "Cache stack slots globally (i.e. a variable always gets the same slot in every trace).", type = OptionType.Debug)
  63         public static final OptionKey<Boolean> TraceRACacheStackSlots = new OptionKey<>(true);
  64         // @formatter:on
  65     }
  66 
  67     private static final TraceGlobalMoveResolutionPhase TRACE_GLOBAL_MOVE_RESOLUTION_PHASE = new TraceGlobalMoveResolutionPhase();
  68 
  69     private static final DebugCounter tracesCounter = Debug.counter("TraceRA[traces]");
  70 
  71     public static final DebugCounter globalStackSlots = Debug.counter("TraceRA[GlobalStackSlots]");
  72     public static final DebugCounter allocatedStackSlots = Debug.counter("TraceRA[AllocatedStackSlots]");
  73 
  74     @Override
  75     @SuppressWarnings("try")
  76     protected void run(TargetDescription target, LIRGenerationResult lirGenRes, AllocationContext context) {
  77         MoveFactory spillMoveFactory = context.spillMoveFactory;
  78         RegisterAllocationConfig registerAllocationConfig = context.registerAllocationConfig;
  79         LIR lir = lirGenRes.getLIR();

  80         TraceBuilderResult resultTraces = context.contextLookup(TraceBuilderResult.class);
  81         GlobalLivenessInfo livenessInfo = context.contextLookup(GlobalLivenessInfo.class);
  82         assert livenessInfo != null;
  83         TraceAllocationContext traceContext = new TraceAllocationContext(spillMoveFactory, registerAllocationConfig, resultTraces, livenessInfo);
  84         AllocatableValue[] cachedStackSlots = Options.TraceRACacheStackSlots.getValue(lir.getOptions()) ? new AllocatableValue[lir.numVariables()] : null;
  85 
  86         // currently this is not supported
  87         boolean neverSpillConstant = false;
  88 
  89         final TraceRegisterAllocationPolicy plan = DefaultTraceRegisterAllocationPolicy.allocationPolicy(target, lirGenRes, spillMoveFactory, registerAllocationConfig, cachedStackSlots, resultTraces,
  90                         neverSpillConstant, livenessInfo, lir.getOptions());
  91 
  92         Debug.dump(Debug.INFO_LOG_LEVEL, lir, "Before TraceRegisterAllocation");
  93         try (Scope s0 = Debug.scope("AllocateTraces", resultTraces, livenessInfo)) {
  94             for (Trace trace : resultTraces.getTraces()) {
  95                 tracesCounter.increment();
  96                 TraceAllocationPhase<TraceAllocationContext> allocator = plan.selectStrategy(trace);
  97                 try (Indent i = Debug.logAndIndent("Allocating Trace%d: %s (%s)", trace.getId(), trace, allocator); Scope s = Debug.scope("AllocateTrace", trace)) {
  98                     allocator.apply(target, lirGenRes, trace, traceContext);
  99                 }
 100             }
 101         } catch (Throwable e) {
 102             throw Debug.handle(e);
 103         }
 104         if (Debug.isDumpEnabled(Debug.INFO_LOG_LEVEL)) {
 105             unnumberInstructions(lir);
 106             Debug.dump(Debug.INFO_LOG_LEVEL, lir, "After trace allocation");
 107         }
 108 
 109         TRACE_GLOBAL_MOVE_RESOLUTION_PHASE.apply(target, lirGenRes, traceContext);
 110         deconstructSSAForm(lir);
 111     }
 112 
 113     /**
 114      * Remove Phi In/Out.



 115      */
 116     private static void deconstructSSAForm(LIR lir) {

 117         for (AbstractBlockBase<?> block : lir.getControlFlowGraph().getBlocks()) {
 118             if (SSAUtil.isMerge(block)) {
 119                 SSAUtil.phiIn(lir, block).clearIncomingValues();
 120                 for (AbstractBlockBase<?> pred : block.getPredecessors()) {
 121                     SSAUtil.phiOut(lir, pred).clearOutgoingValues();

 122                 }

 123             }
 124         }
 125     }
 126 
 127     private static void unnumberInstructions(LIR lir) {
 128         for (AbstractBlockBase<?> block : lir.getControlFlowGraph().getBlocks()) {
 129             for (LIRInstruction op : lir.getLIRforBlock(block)) {
 130                 op.setId(-1);
 131             }
 132         }
 133     }
 134 }