1 /*
2 * Copyright (c) 2015, 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.lsra;
24
25 import static jdk.vm.ci.code.ValueUtil.isRegister;
26 import static org.graalvm.compiler.core.common.GraalOptions.DetailedAsserts;
27 import static org.graalvm.compiler.lir.LIRValueUtil.asConstant;
28 import static org.graalvm.compiler.lir.LIRValueUtil.asVariable;
29 import static org.graalvm.compiler.lir.LIRValueUtil.isConstantValue;
30 import static org.graalvm.compiler.lir.LIRValueUtil.isStackSlotValue;
31 import static org.graalvm.compiler.lir.LIRValueUtil.isVirtualStackSlot;
32
33 import java.util.ArrayList;
34
35 import org.graalvm.compiler.core.common.alloc.RegisterAllocationConfig;
36 import org.graalvm.compiler.core.common.alloc.Trace;
37 import org.graalvm.compiler.core.common.alloc.TraceBuilderResult;
38 import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
39 import org.graalvm.compiler.debug.CounterKey;
40 import org.graalvm.compiler.debug.DebugContext;
41 import org.graalvm.compiler.debug.Indent;
42 import org.graalvm.compiler.lir.LIR;
43 import org.graalvm.compiler.lir.LIRInstruction;
44 import org.graalvm.compiler.lir.StandardOp;
45 import org.graalvm.compiler.lir.StandardOp.JumpOp;
46 import org.graalvm.compiler.lir.StandardOp.LabelOp;
47 import org.graalvm.compiler.lir.alloc.trace.GlobalLivenessInfo;
48 import org.graalvm.compiler.lir.alloc.trace.lsra.TraceLinearScanPhase.TraceLinearScan;
49 import org.graalvm.compiler.lir.gen.LIRGenerationResult;
50 import org.graalvm.compiler.lir.gen.LIRGeneratorTool.MoveFactory;
51 import org.graalvm.compiler.lir.ssa.SSAUtil;
52
53 import jdk.vm.ci.code.TargetDescription;
54 import jdk.vm.ci.meta.Value;
55
56 /**
57 * Phase 6: resolve data flow
58 *
59 * Insert moves at edges between blocks if intervals have been split.
60 */
61 final class TraceLinearScanResolveDataFlowPhase extends TraceLinearScanAllocationPhase {
62
63 @Override
64 protected void run(TargetDescription target, LIRGenerationResult lirGenRes, Trace trace, MoveFactory spillMoveFactory, RegisterAllocationConfig registerAllocationConfig,
65 TraceBuilderResult traceBuilderResult, TraceLinearScan allocator) {
66 new Resolver(allocator, traceBuilderResult).resolveDataFlow(trace, allocator.sortedBlocks());
67 }
68
69 private static final class Resolver {
70 private final TraceLinearScan allocator;
71 private final TraceBuilderResult traceBuilderResult;
72 private final DebugContext debug;
73
74 private Resolver(TraceLinearScan allocator, TraceBuilderResult traceBuilderResult) {
75 this.allocator = allocator;
76 this.traceBuilderResult = traceBuilderResult;
77 this.debug = allocator.getDebug();
78 }
79
80 private void resolveFindInsertPos(AbstractBlockBase<?> fromBlock, AbstractBlockBase<?> toBlock, TraceLocalMoveResolver moveResolver) {
81 if (fromBlock.getSuccessorCount() <= 1) {
82 if (debug.isLogEnabled()) {
83 debug.log("inserting moves at end of fromBlock B%d", fromBlock.getId());
84 }
85
86 ArrayList<LIRInstruction> instructions = allocator.getLIR().getLIRforBlock(fromBlock);
87 LIRInstruction instr = instructions.get(instructions.size() - 1);
88 if (instr instanceof StandardOp.JumpOp) {
89 // insert moves before branch
90 moveResolver.setInsertPosition(instructions, instructions.size() - 1);
91 } else {
92 moveResolver.setInsertPosition(instructions, instructions.size());
93 }
94
95 } else {
96 if (debug.isLogEnabled()) {
97 debug.log("inserting moves at beginning of toBlock B%d", toBlock.getId());
98 }
99
100 if (DetailedAsserts.getValue(allocator.getOptions())) {
101 assert allocator.getLIR().getLIRforBlock(fromBlock).get(0) instanceof StandardOp.LabelOp : "block does not start with a label";
102
103 /*
104 * Because the number of predecessor edges matches the number of successor
105 * edges, blocks which are reached by switch statements may have be more than
106 * one predecessor but it will be guaranteed that all predecessors will be the
107 * same.
108 */
109 for (AbstractBlockBase<?> predecessor : toBlock.getPredecessors()) {
110 assert fromBlock == predecessor : "all critical edges must be broken";
111 }
112 }
113
114 moveResolver.setInsertPosition(allocator.getLIR().getLIRforBlock(toBlock), 1);
115 }
116 }
117
118 /**
119 * Inserts necessary moves (spilling or reloading) at edges between blocks for intervals
120 * that have been split.
121 */
122 @SuppressWarnings("try")
123 private void resolveDataFlow(Trace currentTrace, AbstractBlockBase<?>[] blocks) {
124 if (blocks.length < 2) {
125 // no resolution necessary
126 return;
127 }
128 try (Indent indent = debug.logAndIndent("resolve data flow")) {
129
130 TraceLocalMoveResolver moveResolver = allocator.createMoveResolver();
131 AbstractBlockBase<?> toBlock = null;
132 for (int i = 0; i < blocks.length - 1; i++) {
133 AbstractBlockBase<?> fromBlock = blocks[i];
134 toBlock = blocks[i + 1];
135 assert containedInTrace(currentTrace, fromBlock) : "Not in Trace: " + fromBlock;
136 assert containedInTrace(currentTrace, toBlock) : "Not in Trace: " + toBlock;
137 resolveCollectMappings(fromBlock, toBlock, moveResolver);
138 }
139 assert blocks[blocks.length - 1].equals(toBlock);
140 if (toBlock.isLoopEnd()) {
141 assert toBlock.getSuccessorCount() == 1;
142 AbstractBlockBase<?> loopHeader = toBlock.getSuccessors()[0];
143 if (containedInTrace(currentTrace, loopHeader)) {
144 resolveCollectMappings(toBlock, loopHeader, moveResolver);
145 }
146 }
147
148 }
149 }
150
151 @SuppressWarnings("try")
152 private void resolveCollectMappings(AbstractBlockBase<?> fromBlock, AbstractBlockBase<?> toBlock, TraceLocalMoveResolver moveResolver) {
153 try (Indent indent0 = debug.logAndIndent("Edge %s -> %s", fromBlock, toBlock)) {
154 // collect all intervals that have been split between
155 // fromBlock and toBlock
156 int toId = allocator.getFirstLirInstructionId(toBlock);
157 int fromId = allocator.getLastLirInstructionId(fromBlock);
158 assert fromId >= 0;
159 LIR lir = allocator.getLIR();
160 if (SSAUtil.isMerge(toBlock)) {
161 JumpOp blockEnd = SSAUtil.phiOut(lir, fromBlock);
162 LabelOp label = SSAUtil.phiIn(lir, toBlock);
163 for (int i = 0; i < label.getPhiSize(); i++) {
164 addMapping(blockEnd.getOutgoingValue(i), label.getIncomingValue(i), fromId, toId, moveResolver);
165 }
166 }
167 GlobalLivenessInfo livenessInfo = allocator.getGlobalLivenessInfo();
168 int[] locTo = livenessInfo.getBlockIn(toBlock);
169 for (int i = 0; i < locTo.length; i++) {
170 TraceInterval interval = allocator.intervalFor(locTo[i]);
171 addMapping(interval, interval, fromId, toId, moveResolver);
172 }
173
174 if (moveResolver.hasMappings()) {
175 resolveFindInsertPos(fromBlock, toBlock, moveResolver);
176 moveResolver.resolveAndAppendMoves();
177 }
178 }
179 }
180
181 private boolean containedInTrace(Trace currentTrace, AbstractBlockBase<?> block) {
182 return currentTrace.getId() == traceBuilderResult.getTraceForBlock(block).getId();
183 }
184
185 private static final CounterKey numResolutionMoves = DebugContext.counter("TraceRA[numTraceLSRAResolutionMoves]");
186 private static final CounterKey numStackToStackMoves = DebugContext.counter("TraceRA[numTraceLSRAStackToStackMoves]");
187
188 private void addMapping(Value phiFrom, Value phiTo, int fromId, int toId, TraceLocalMoveResolver moveResolver) {
189 assert !isRegister(phiFrom) : "Out is a register: " + phiFrom;
190 assert !isRegister(phiTo) : "In is a register: " + phiTo;
191 assert !Value.ILLEGAL.equals(phiTo) : "The value not needed in this branch? " + phiFrom;
192 if (isVirtualStackSlot(phiTo) && isVirtualStackSlot(phiFrom) && phiTo.equals(phiFrom)) {
193 // no need to handle virtual stack slots
194 return;
195 }
196 TraceInterval toParent = allocator.intervalFor(asVariable(phiTo));
197 if (isConstantValue(phiFrom)) {
198 numResolutionMoves.increment(debug);
199 TraceInterval toInterval = allocator.splitChildAtOpId(toParent, toId, LIRInstruction.OperandMode.DEF);
200 moveResolver.addMapping(asConstant(phiFrom), toInterval);
201 } else {
202 addMapping(allocator.intervalFor(asVariable(phiFrom)), toParent, fromId, toId, moveResolver);
203 }
204 }
205
206 private void addMapping(TraceInterval fromParent, TraceInterval toParent, int fromId, int toId, TraceLocalMoveResolver moveResolver) {
207 TraceInterval fromInterval = allocator.splitChildAtOpId(fromParent, fromId, LIRInstruction.OperandMode.USE);
208 TraceInterval toInterval = toParent.getSplitChildAtOpIdOrNull(toId, LIRInstruction.OperandMode.DEF);
209 if (toInterval == null) {
210 // not alive
211 return;
212 }
213 if (fromInterval != toInterval) {
214 numResolutionMoves.increment(debug);
215 if (isStackSlotValue(toInterval.location()) && isStackSlotValue(fromInterval.location())) {
216 numStackToStackMoves.increment(debug);
217 }
218 moveResolver.addMapping(fromInterval, toInterval);
219 }
220 }
221 }
222
223 }