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