1 /*
2 * Copyright (c) 2009, 2011, 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
24 package org.graalvm.compiler.core.common.alloc;
25
26 import java.util.ArrayList;
27 import java.util.BitSet;
28 import java.util.Comparator;
29 import java.util.List;
30 import java.util.PriorityQueue;
31
32 import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
33 import org.graalvm.compiler.core.common.cfg.Loop;
34
35 /**
36 * Computes an ordering of the block that can be used by the linear scan register allocator and the
37 * machine code generator. The machine code generation order will start with the first block and
38 * produce a straight sequence always following the most likely successor. Then it will continue
39 * with the most likely path that was left out during this process. The process iteratively
40 * continues until all blocks are scheduled. Additionally, it is guaranteed that all blocks of a
41 * loop are scheduled before any block following the loop is scheduled.
42 *
43 * The machine code generator order includes reordering of loop headers such that the backward jump
44 * is a conditional jump if there is only one loop end block. Additionally, the target of loop
45 * backward jumps are always marked as aligned. Aligning the target of conditional jumps does not
46 * bring a measurable benefit and is therefore avoided to keep the code size small.
47 *
48 * The linear scan register allocator order has an additional mechanism that prevents merge nodes
49 * from being scheduled if there is at least one highly likely predecessor still unscheduled. This
50 * increases the probability that the merge node and the corresponding predecessor are more closely
51 * together in the schedule thus decreasing the probability for inserted phi moves. Also, the
52 * algorithm sets the linear scan order number of the block that corresponds to its index in the
53 * linear scan order.
54 */
55 public final class ComputeBlockOrder {
56
57 /**
58 * The initial capacities of the worklists used for iteratively finding the block order.
59 */
60 private static final int INITIAL_WORKLIST_CAPACITY = 10;
61
62 /**
63 * Divisor used for degrading the probability of the current path versus unscheduled paths at a
64 * merge node when calculating the linear scan order. A high value means that predecessors of
65 * merge nodes are more likely to be scheduled before the merge node.
66 */
67 private static final int PENALTY_VERSUS_UNSCHEDULED = 10;
68
69 /**
70 * Computes the block order used for the linear scan register allocator.
71 *
72 * @return sorted list of blocks
73 */
74 public static <T extends AbstractBlockBase<T>> AbstractBlockBase<?>[] computeLinearScanOrder(int blockCount, T startBlock) {
75 List<T> order = new ArrayList<>();
76 BitSet visitedBlocks = new BitSet(blockCount);
77 PriorityQueue<T> worklist = initializeWorklist(startBlock, visitedBlocks);
78 computeLinearScanOrder(order, worklist, visitedBlocks);
79 assert checkOrder(order, blockCount);
80 return order.toArray(new AbstractBlockBase<?>[0]);
81 }
82
83 /**
84 * Computes the block order used for code emission.
85 *
86 * @return sorted list of blocks
87 */
88 public static <T extends AbstractBlockBase<T>> AbstractBlockBase<?>[] computeCodeEmittingOrder(int blockCount, T startBlock) {
89 List<T> order = new ArrayList<>();
90 BitSet visitedBlocks = new BitSet(blockCount);
91 PriorityQueue<T> worklist = initializeWorklist(startBlock, visitedBlocks);
92 computeCodeEmittingOrder(order, worklist, visitedBlocks);
93 assert checkOrder(order, blockCount);
94 return order.toArray(new AbstractBlockBase<?>[0]);
95 }
96
97 /**
98 * Iteratively adds paths to the code emission block order.
99 */
100 private static <T extends AbstractBlockBase<T>> void computeCodeEmittingOrder(List<T> order, PriorityQueue<T> worklist, BitSet visitedBlocks) {
101 while (!worklist.isEmpty()) {
102 T nextImportantPath = worklist.poll();
103 addPathToCodeEmittingOrder(nextImportantPath, order, worklist, visitedBlocks);
104 }
105 }
106
107 /**
108 * Iteratively adds paths to the linear scan block order.
109 */
110 private static <T extends AbstractBlockBase<T>> void computeLinearScanOrder(List<T> order, PriorityQueue<T> worklist, BitSet visitedBlocks) {
111 while (!worklist.isEmpty()) {
112 T nextImportantPath = worklist.poll();
113 do {
114 nextImportantPath = addPathToLinearScanOrder(nextImportantPath, order, worklist, visitedBlocks);
115 } while (nextImportantPath != null);
116 }
117 }
118
119 /**
120 * Initializes the priority queue used for the work list of blocks and adds the start block.
121 */
122 private static <T extends AbstractBlockBase<T>> PriorityQueue<T> initializeWorklist(T startBlock, BitSet visitedBlocks) {
123 PriorityQueue<T> result = new PriorityQueue<>(INITIAL_WORKLIST_CAPACITY, new BlockOrderComparator<>());
124 result.add(startBlock);
125 visitedBlocks.set(startBlock.getId());
126 return result;
127 }
128
129 /**
130 * Add a linear path to the linear scan order greedily following the most likely successor.
131 */
132 private static <T extends AbstractBlockBase<T>> T addPathToLinearScanOrder(T block, List<T> order, PriorityQueue<T> worklist, BitSet visitedBlocks) {
133 block.setLinearScanNumber(order.size());
134 order.add(block);
135 T mostLikelySuccessor = findAndMarkMostLikelySuccessor(block, visitedBlocks);
136 enqueueSuccessors(block, worklist, visitedBlocks);
137 if (mostLikelySuccessor != null) {
138 if (!mostLikelySuccessor.isLoopHeader() && mostLikelySuccessor.getPredecessorCount() > 1) {
139 // We are at a merge. Check probabilities of predecessors that are not yet
140 // scheduled.
141 double unscheduledSum = 0.0;
142 for (T pred : mostLikelySuccessor.getPredecessors()) {
143 if (pred.getLinearScanNumber() == -1) {
144 unscheduledSum += pred.probability();
145 }
146 }
147
148 if (unscheduledSum > block.probability() / PENALTY_VERSUS_UNSCHEDULED) {
149 // Add this merge only after at least one additional predecessor gets scheduled.
150 visitedBlocks.clear(mostLikelySuccessor.getId());
151 return null;
152 }
153 }
154 return mostLikelySuccessor;
155 }
156 return null;
157 }
158
159 /**
160 * Add a linear path to the code emission order greedily following the most likely successor.
161 */
162 private static <T extends AbstractBlockBase<T>> void addPathToCodeEmittingOrder(T initialBlock, List<T> order, PriorityQueue<T> worklist, BitSet visitedBlocks) {
163 T block = initialBlock;
164 while (block != null) {
165 // Skip loop headers if there is only a single loop end block to
166 // make the backward jump be a conditional jump.
167 if (!skipLoopHeader(block)) {
168
169 // Align unskipped loop headers as they are the target of the backward jump.
170 if (block.isLoopHeader()) {
171 block.setAlign(true);
172 }
173 addBlock(block, order);
174 }
175
176 Loop<T> loop = block.getLoop();
177 if (block.isLoopEnd() && skipLoopHeader(loop.getHeader())) {
178
179 // This is the only loop end of a skipped loop header.
180 // Add the header immediately afterwards.
181 addBlock(loop.getHeader(), order);
182
183 // Make sure the loop successors of the loop header are aligned
184 // as they are the target
185 // of the backward jump.
186 for (T successor : loop.getHeader().getSuccessors()) {
187 if (successor.getLoopDepth() == block.getLoopDepth()) {
188 successor.setAlign(true);
189 }
190 }
191 }
192
193 T mostLikelySuccessor = findAndMarkMostLikelySuccessor(block, visitedBlocks);
194 enqueueSuccessors(block, worklist, visitedBlocks);
195 block = mostLikelySuccessor;
196 }
197 }
198
199 /**
200 * Adds a block to the ordering.
201 */
202 private static <T extends AbstractBlockBase<T>> void addBlock(T header, List<T> order) {
203 assert !order.contains(header) : "Cannot insert block twice";
204 order.add(header);
205 }
206
207 /**
208 * Find the highest likely unvisited successor block of a given block.
209 */
210 private static <T extends AbstractBlockBase<T>> T findAndMarkMostLikelySuccessor(T block, BitSet visitedBlocks) {
211 T result = null;
212 for (T successor : block.getSuccessors()) {
213 assert successor.probability() >= 0.0 : "Probabilities must be positive";
214 if (!visitedBlocks.get(successor.getId()) && successor.getLoopDepth() >= block.getLoopDepth() && (result == null || successor.probability() >= result.probability())) {
215 result = successor;
216 }
217 }
218 if (result != null) {
219 visitedBlocks.set(result.getId());
220 }
221 return result;
222 }
223
224 /**
225 * Add successor blocks into the given work list if they are not already marked as visited.
226 */
227 private static <T extends AbstractBlockBase<T>> void enqueueSuccessors(T block, PriorityQueue<T> worklist, BitSet visitedBlocks) {
228 for (T successor : block.getSuccessors()) {
229 if (!visitedBlocks.get(successor.getId())) {
230 visitedBlocks.set(successor.getId());
231 worklist.add(successor);
232 }
233 }
234 }
235
236 /**
237 * Skip the loop header block if the loop consists of more than one block and it has only a
238 * single loop end block.
239 */
240 private static <T extends AbstractBlockBase<T>> boolean skipLoopHeader(AbstractBlockBase<T> block) {
241 return (block.isLoopHeader() && !block.isLoopEnd() && block.getLoop().numBackedges() == 1);
242 }
243
244 /**
245 * Checks that the ordering contains the expected number of blocks.
246 */
247 private static boolean checkOrder(List<? extends AbstractBlockBase<?>> order, int expectedBlockCount) {
248 assert order.size() == expectedBlockCount : String.format("Number of blocks in ordering (%d) does not match expected block count (%d)", order.size(), expectedBlockCount);
249 return true;
250 }
251
252 /**
253 * Comparator for sorting blocks based on loop depth and probability.
254 */
255 private static class BlockOrderComparator<T extends AbstractBlockBase<T>> implements Comparator<T> {
256
257 @Override
258 public int compare(T a, T b) {
259 // Loop blocks before any loop exit block.
260 int diff = b.getLoopDepth() - a.getLoopDepth();
261 if (diff != 0) {
262 return diff;
263 }
264
265 // Blocks with high probability before blocks with low probability.
266 if (a.probability() > b.probability()) {
267 return -1;
268 } else {
269 return 1;
270 }
271 }
272 }
273 }