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.lsra;
24
25 import static org.graalvm.compiler.core.common.GraalOptions.DetailedAsserts;
26
27 import java.util.BitSet;
28 import java.util.List;
29
30 import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
31 import org.graalvm.compiler.debug.Debug;
32 import org.graalvm.compiler.debug.Indent;
33 import org.graalvm.compiler.lir.LIRInstruction;
34 import org.graalvm.compiler.lir.StandardOp;
35 import org.graalvm.compiler.lir.gen.LIRGenerationResult;
36 import org.graalvm.compiler.lir.phases.AllocationPhase;
37
38 import jdk.vm.ci.code.TargetDescription;
39
40 /**
41 * Phase 6: resolve data flow
42 *
43 * Insert moves at edges between blocks if intervals have been split.
44 */
45 public class LinearScanResolveDataFlowPhase extends AllocationPhase {
46
47 protected final LinearScan allocator;
48
49 protected LinearScanResolveDataFlowPhase(LinearScan allocator) {
50 this.allocator = allocator;
51 }
52
53 @Override
54 protected void run(TargetDescription target, LIRGenerationResult lirGenRes, AllocationContext context) {
55 resolveDataFlow();
56 allocator.printIntervals("After resolve data flow");
57 }
58
59 protected void resolveCollectMappings(AbstractBlockBase<?> fromBlock, AbstractBlockBase<?> toBlock, AbstractBlockBase<?> midBlock, MoveResolver moveResolver) {
60 assert moveResolver.checkEmpty();
61 assert midBlock == null ||
62 (midBlock.getPredecessorCount() == 1 && midBlock.getSuccessorCount() == 1 && midBlock.getPredecessors()[0].equals(fromBlock) && midBlock.getSuccessors()[0].equals(
63 toBlock));
64
65 int toBlockFirstInstructionId = allocator.getFirstLirInstructionId(toBlock);
66 int fromBlockLastInstructionId = allocator.getLastLirInstructionId(fromBlock) + 1;
67 int numOperands = allocator.operandSize();
68 BitSet liveAtEdge = allocator.getBlockData(toBlock).liveIn;
69
70 // visit all variables for which the liveAtEdge bit is set
71 for (int operandNum = liveAtEdge.nextSetBit(0); operandNum >= 0; operandNum = liveAtEdge.nextSetBit(operandNum + 1)) {
72 assert operandNum < numOperands : "live information set for not exisiting interval";
73 assert allocator.getBlockData(fromBlock).liveOut.get(operandNum) && allocator.getBlockData(toBlock).liveIn.get(operandNum) : "interval not live at this edge";
74
75 Interval fromInterval = allocator.splitChildAtOpId(allocator.intervalFor(operandNum), fromBlockLastInstructionId, LIRInstruction.OperandMode.DEF);
76 Interval toInterval = allocator.splitChildAtOpId(allocator.intervalFor(operandNum), toBlockFirstInstructionId, LIRInstruction.OperandMode.DEF);
77
78 if (fromInterval != toInterval && !fromInterval.location().equals(toInterval.location())) {
79 // need to insert move instruction
80 moveResolver.addMapping(fromInterval, toInterval);
81 }
82 }
83 }
84
85 void resolveFindInsertPos(AbstractBlockBase<?> fromBlock, AbstractBlockBase<?> toBlock, MoveResolver moveResolver) {
86 if (fromBlock.getSuccessorCount() <= 1) {
87 if (Debug.isLogEnabled()) {
88 Debug.log("inserting moves at end of fromBlock B%d", fromBlock.getId());
89 }
90
91 List<LIRInstruction> instructions = allocator.getLIR().getLIRforBlock(fromBlock);
92 LIRInstruction instr = instructions.get(instructions.size() - 1);
93 if (instr instanceof StandardOp.JumpOp) {
94 // insert moves before branch
95 moveResolver.setInsertPosition(instructions, instructions.size() - 1);
96 } else {
97 moveResolver.setInsertPosition(instructions, instructions.size());
98 }
99
100 } else {
101 if (Debug.isLogEnabled()) {
102 Debug.log("inserting moves at beginning of toBlock B%d", toBlock.getId());
103 }
104
105 if (DetailedAsserts.getValue()) {
106 assert allocator.getLIR().getLIRforBlock(fromBlock).get(0) instanceof StandardOp.LabelOp : "block does not start with a label";
107
108 /*
109 * Because the number of predecessor edges matches the number of successor edges,
110 * blocks which are reached by switch statements may have be more than one
111 * predecessor but it will be guaranteed that all predecessors will be the same.
112 */
113 for (AbstractBlockBase<?> predecessor : toBlock.getPredecessors()) {
114 assert fromBlock == predecessor : "all critical edges must be broken";
115 }
116 }
117
118 moveResolver.setInsertPosition(allocator.getLIR().getLIRforBlock(toBlock), 1);
119 }
120 }
121
122 /**
123 * Inserts necessary moves (spilling or reloading) at edges between blocks for intervals that
124 * have been split.
125 */
126 @SuppressWarnings("try")
127 protected void resolveDataFlow() {
128 try (Indent indent = Debug.logAndIndent("resolve data flow")) {
129
130 MoveResolver moveResolver = allocator.createMoveResolver();
131 BitSet blockCompleted = new BitSet(allocator.blockCount());
132
133 optimizeEmptyBlocks(moveResolver, blockCompleted);
134
135 resolveDataFlow0(moveResolver, blockCompleted);
136
137 }
138 }
139
140 protected void optimizeEmptyBlocks(MoveResolver moveResolver, BitSet blockCompleted) {
141 for (AbstractBlockBase<?> block : allocator.sortedBlocks()) {
142
143 // check if block has only one predecessor and only one successor
144 if (block.getPredecessorCount() == 1 && block.getSuccessorCount() == 1) {
145 List<LIRInstruction> instructions = allocator.getLIR().getLIRforBlock(block);
146 assert instructions.get(0) instanceof StandardOp.LabelOp : "block must start with label";
147 assert instructions.get(instructions.size() - 1) instanceof StandardOp.JumpOp : "block with successor must end with unconditional jump";
148
149 // check if block is empty (only label and branch)
150 if (instructions.size() == 2) {
151 AbstractBlockBase<?> pred = block.getPredecessors()[0];
152 AbstractBlockBase<?> sux = block.getSuccessors()[0];
153
154 // prevent optimization of two consecutive blocks
155 if (!blockCompleted.get(pred.getLinearScanNumber()) && !blockCompleted.get(sux.getLinearScanNumber())) {
156 if (Debug.isLogEnabled()) {
157 Debug.log(" optimizing empty block B%d (pred: B%d, sux: B%d)", block.getId(), pred.getId(), sux.getId());
158 }
159
160 blockCompleted.set(block.getLinearScanNumber());
161
162 /*
163 * Directly resolve between pred and sux (without looking at the empty block
164 * between).
165 */
166 resolveCollectMappings(pred, sux, block, moveResolver);
167 if (moveResolver.hasMappings()) {
168 moveResolver.setInsertPosition(instructions, 1);
169 moveResolver.resolveAndAppendMoves();
170 }
171 }
172 }
173 }
174 }
175 }
176
177 protected void resolveDataFlow0(MoveResolver moveResolver, BitSet blockCompleted) {
178 BitSet alreadyResolved = new BitSet(allocator.blockCount());
179 for (AbstractBlockBase<?> fromBlock : allocator.sortedBlocks()) {
180 if (!blockCompleted.get(fromBlock.getLinearScanNumber())) {
181 alreadyResolved.clear();
182 alreadyResolved.or(blockCompleted);
183
184 for (AbstractBlockBase<?> toBlock : fromBlock.getSuccessors()) {
185
186 /*
187 * Check for duplicate edges between the same blocks (can happen with switch
188 * blocks).
189 */
190 if (!alreadyResolved.get(toBlock.getLinearScanNumber())) {
191 if (Debug.isLogEnabled()) {
192 Debug.log("processing edge between B%d and B%d", fromBlock.getId(), toBlock.getId());
193 }
194
195 alreadyResolved.set(toBlock.getLinearScanNumber());
196
197 // collect all intervals that have been split between
198 // fromBlock and toBlock
199 resolveCollectMappings(fromBlock, toBlock, null, moveResolver);
200 if (moveResolver.hasMappings()) {
201 resolveFindInsertPos(fromBlock, toBlock, moveResolver);
202 moveResolver.resolveAndAppendMoves();
203 }
204 }
205 }
206 }
207 }
208 }
209
210 }