1 /*
2 * Copyright (c) 2015, 2015, 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 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.CounterKey;
30 import org.graalvm.compiler.debug.DebugContext;
31 import org.graalvm.compiler.debug.Indent;
32 import org.graalvm.compiler.lir.LIR;
33 import org.graalvm.compiler.lir.alloc.trace.TraceAllocationPhase.TraceAllocationContext;
34 import org.graalvm.compiler.lir.gen.LIRGenerationResult;
35 import org.graalvm.compiler.lir.gen.LIRGeneratorTool.MoveFactory;
36 import org.graalvm.compiler.lir.phases.AllocationPhase;
37 import org.graalvm.compiler.lir.ssa.SSAUtil;
38 import org.graalvm.compiler.options.Option;
39 import org.graalvm.compiler.options.OptionKey;
40 import org.graalvm.compiler.options.OptionType;
41
42 import jdk.vm.ci.code.TargetDescription;
43 import jdk.vm.ci.meta.AllocatableValue;
44
45 /**
46 * Implements the Trace Register Allocation approach as described in
47 * <a href="http://dx.doi.org/10.1145/2972206.2972211">"Trace-based Register Allocation in a JIT
48 * Compiler"</a> by Josef Eisl et al.
49 */
50 public final class TraceRegisterAllocationPhase extends AllocationPhase {
51
52 public static class Options {
53 // @formatter:off
54 @Option(help = "Use inter-trace register hints.", type = OptionType.Debug)
55 public static final OptionKey<Boolean> TraceRAuseInterTraceHints = new OptionKey<>(true);
56 @Option(help = "Share information about spilled values to other traces.", type = OptionType.Debug)
57 public static final OptionKey<Boolean> TraceRAshareSpillInformation = new OptionKey<>(true);
58 @Option(help = "Reuse spill slots for global move resolution cycle breaking.", type = OptionType.Debug)
59 public static final OptionKey<Boolean> TraceRAreuseStackSlotsForMoveResolutionCycleBreaking = new OptionKey<>(true);
60 @Option(help = "Cache stack slots globally (i.e. a variable always gets the same slot in every trace).", type = OptionType.Debug)
61 public static final OptionKey<Boolean> TraceRACacheStackSlots = new OptionKey<>(true);
62 // @formatter:on
63 }
64
65 private static final CounterKey tracesCounter = DebugContext.counter("TraceRA[traces]");
66
67 public static final CounterKey globalStackSlots = DebugContext.counter("TraceRA[GlobalStackSlots]");
68 public static final CounterKey allocatedStackSlots = DebugContext.counter("TraceRA[AllocatedStackSlots]");
69
70 @Override
71 @SuppressWarnings("try")
72 protected void run(TargetDescription target, LIRGenerationResult lirGenRes, AllocationContext context) {
73 MoveFactory spillMoveFactory = context.spillMoveFactory;
74 RegisterAllocationConfig registerAllocationConfig = context.registerAllocationConfig;
75 LIR lir = lirGenRes.getLIR();
76 DebugContext debug = lir.getDebug();
77 TraceBuilderResult resultTraces = context.contextLookup(TraceBuilderResult.class);
78 GlobalLivenessInfo livenessInfo = context.contextLookup(GlobalLivenessInfo.class);
79 assert livenessInfo != null;
80 TraceAllocationContext traceContext = new TraceAllocationContext(spillMoveFactory, registerAllocationConfig, resultTraces, livenessInfo);
81 AllocatableValue[] cachedStackSlots = Options.TraceRACacheStackSlots.getValue(lir.getOptions()) ? new AllocatableValue[lir.numVariables()] : null;
82
83 // currently this is not supported
84 boolean neverSpillConstant = false;
85
86 final TraceRegisterAllocationPolicy plan = DefaultTraceRegisterAllocationPolicy.allocationPolicy(target, lirGenRes, spillMoveFactory, registerAllocationConfig, cachedStackSlots, resultTraces,
87 neverSpillConstant, livenessInfo, lir.getOptions());
88
89 try (DebugContext.Scope s0 = debug.scope("AllocateTraces", resultTraces, livenessInfo)) {
90 for (Trace trace : resultTraces.getTraces()) {
91 tracesCounter.increment(debug);
92 TraceAllocationPhase<TraceAllocationContext> allocator = plan.selectStrategy(trace);
93 try (Indent i = debug.logAndIndent("Allocating Trace%d: %s (%s)", trace.getId(), trace, allocator); DebugContext.Scope s = debug.scope("AllocateTrace", trace)) {
94 allocator.apply(target, lirGenRes, trace, traceContext);
95 }
96 }
97 } catch (Throwable e) {
98 throw debug.handle(e);
99 }
100
101 TraceGlobalMoveResolutionPhase.resolve(target, lirGenRes, traceContext);
102 deconstructSSAForm(lir);
103 }
104
105 /**
106 * Remove Phi In/Out.
107 */
108 private static void deconstructSSAForm(LIR lir) {
109 for (AbstractBlockBase<?> block : lir.getControlFlowGraph().getBlocks()) {
110 if (SSAUtil.isMerge(block)) {
111 SSAUtil.phiIn(lir, block).clearIncomingValues();
112 for (AbstractBlockBase<?> pred : block.getPredecessors()) {
113 SSAUtil.phiOut(lir, pred).clearOutgoingValues();
114 }
115 }
116 }
117 }
118
119 }