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