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