Mercurial > hg > truffle

comparison graal/com.oracle.max.graal.compiler/src/com/sun/c1x/ir/ComputeLinearScanOrder.java @ 2872:0341b6424579

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Project renaming.
author Thomas Wuerthinger <thomas@wuerthinger.net>
date Wed, 08 Jun 2011 08:42:25 +0200
parents graal/GraalCompiler/src/com/sun/c1x/ir/ComputeLinearScanOrder.java@9b8c194c1b1f
children
comparison
equal deleted inserted replaced
2871:d704eb526603 2872:0341b6424579
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 com.sun.c1x.ir;
25
26 import java.util.*;
27
28 import com.sun.c1x.*;
29 import com.sun.c1x.debug.*;
30 import com.sun.c1x.lir.*;
31 import com.sun.c1x.util.*;
32 import com.sun.cri.ci.*;
33
34 public final class ComputeLinearScanOrder {
35
36 private final int maxBlockId; // the highest blockId of a block
37 private int numBlocks; // total number of blocks (smaller than maxBlockId)
38 private int numLoops; // total number of loops
39 private boolean iterativeDominators; // method requires iterative computation of dominators
40
41 List<LIRBlock> linearScanOrder; // the resulting list of blocks in correct order
42
43 final CiBitMap visitedBlocks; // used for recursive processing of blocks
44 final CiBitMap activeBlocks; // used for recursive processing of blocks
45 final CiBitMap dominatorBlocks; // temporary BitMap used for computation of dominator
46 final int[] forwardBranches; // number of incoming forward branches for each block
47 final List<LIRBlock> loopEndBlocks; // list of all loop end blocks collected during countEdges
48 BitMap2D loopMap; // two-dimensional bit set: a bit is set if a block is contained in a loop
49 final List<LIRBlock> workList; // temporary list (used in markLoops and computeOrder)
50
51 // accessors for visitedBlocks and activeBlocks
52 void initVisited() {
53 activeBlocks.clearAll();
54 visitedBlocks.clearAll();
55 }
56
57 boolean isVisited(LIRBlock b) {
58 return visitedBlocks.get(b.blockID());
59 }
60
61 boolean isActive(LIRBlock b) {
62 return activeBlocks.get(b.blockID());
63 }
64
65 void setVisited(LIRBlock b) {
66 assert !isVisited(b) : "already set";
67 visitedBlocks.set(b.blockID());
68 }
69
70 void setActive(LIRBlock b) {
71 assert !isActive(b) : "already set";
72 activeBlocks.set(b.blockID());
73 }
74
75 void clearActive(LIRBlock b) {
76 assert isActive(b) : "not already";
77 activeBlocks.clear(b.blockID());
78 }
79
80 // accessors for forwardBranches
81 void incForwardBranches(LIRBlock b) {
82 forwardBranches[b.blockID()]++;
83 }
84
85 int decForwardBranches(LIRBlock b) {
86 return --forwardBranches[b.blockID()];
87 }
88
89 // accessors for loopMap
90 boolean isBlockInLoop(int loopIdx, LIRBlock b) {
91 return loopMap.at(loopIdx, b.blockID());
92 }
93
94 void setBlockInLoop(int loopIdx, LIRBlock b) {
95 loopMap.setBit(loopIdx, b.blockID());
96 }
97
98 void clearBlockInLoop(int loopIdx, int blockId) {
99 loopMap.clearBit(loopIdx, blockId);
100 }
101
102 // accessors for final result
103 public List<LIRBlock> linearScanOrder() {
104 return linearScanOrder;
105 }
106
107 public int numLoops() {
108 return numLoops;
109 }
110
111 public ComputeLinearScanOrder(int maxBlockId, LIRBlock startBlock) {
112
113 this.maxBlockId = maxBlockId;
114 visitedBlocks = new CiBitMap(maxBlockId);
115 activeBlocks = new CiBitMap(maxBlockId);
116 dominatorBlocks = new CiBitMap(maxBlockId);
117 forwardBranches = new int[maxBlockId];
118 loopEndBlocks = new ArrayList<LIRBlock>(8);
119 workList = new ArrayList<LIRBlock>(8);
120
121 splitCriticalEdges();
122
123 countEdges(startBlock, null);
124
125 if (numLoops > 0) {
126 markLoops();
127 clearNonNaturalLoops(startBlock);
128 assignLoopDepth(startBlock);
129 }
130
131 computeOrder(startBlock);
132
133 printBlocks();
134 assert verify();
135 }
136
137 void splitCriticalEdges() {
138 // TODO: move critical edge splitting from IR to here
139 }
140
141 /**
142 * Traverses the CFG to analyze block and edge info. The analysis performed is:
143 *
144 * 1. Count of total number of blocks.
145 * 2. Count of all incoming edges and backward incoming edges.
146 * 3. Number loop header blocks.
147 * 4. Create a list with all loop end blocks.
148 */
149 void countEdges(LIRBlock cur, LIRBlock parent) {
150 if (C1XOptions.TraceLinearScanLevel >= 3) {
151 TTY.println("Counting edges for block B%d%s", cur.blockID(), parent == null ? "" : " coming from B" + parent.blockID());
152 }
153
154 if (isActive(cur)) {
155 if (C1XOptions.TraceLinearScanLevel >= 3) {
156 TTY.println("backward branch");
157 }
158 assert isVisited(cur) : "block must be visited when block is active";
159 assert parent != null : "must have parent";
160
161 cur.setLinearScanLoopHeader();
162 parent.setLinearScanLoopEnd();
163
164 loopEndBlocks.add(parent);
165 return;
166 }
167
168 // increment number of incoming forward branches
169 incForwardBranches(cur);
170
171 if (isVisited(cur)) {
172 if (C1XOptions.TraceLinearScanLevel >= 3) {
173 TTY.println("block already visited");
174 }
175 return;
176 }
177
178 numBlocks++;
179 setVisited(cur);
180 setActive(cur);
181
182 // recursive call for all successors
183 int i;
184 for (i = cur.numberOfSux() - 1; i >= 0; i--) {
185 countEdges(cur.suxAt(i), cur);
186 }
187
188 clearActive(cur);
189
190 // Each loop has a unique number.
191 // When multiple loops are nested, assignLoopDepth assumes that the
192 // innermost loop has the lowest number. This is guaranteed by setting
193 // the loop number after the recursive calls for the successors above
194 // have returned.
195 if (cur.isLinearScanLoopHeader()) {
196 assert cur.loopIndex() == -1 : "cannot set loop-index twice";
197 if (C1XOptions.TraceLinearScanLevel >= 3) {
198 TTY.println("Block B%d is loop header of loop %d", cur.blockID(), numLoops);
199 }
200
201 cur.setLoopIndex(numLoops);
202 numLoops++;
203 }
204
205 if (C1XOptions.TraceLinearScanLevel >= 3) {
206 TTY.println("Finished counting edges for block B%d", cur.blockID());
207 }
208 }
209
210 void markLoops() {
211 if (C1XOptions.TraceLinearScanLevel >= 3) {
212 TTY.println("----- marking loops");
213 }
214
215 loopMap = new BitMap2D(numLoops, maxBlockId);
216
217 for (int i = loopEndBlocks.size() - 1; i >= 0; i--) {
218 LIRBlock loopEnd = loopEndBlocks.get(i);
219 LIRBlock loopStart = loopEnd.suxAt(0);
220 int loopIdx = loopStart.loopIndex();
221
222 if (C1XOptions.TraceLinearScanLevel >= 3) {
223 TTY.println("Processing loop from B%d to B%d (loop %d):", loopStart.blockID(), loopEnd.blockID(), loopIdx);
224 }
225 assert loopEnd.isLinearScanLoopEnd() : "loop end flag must be set";
226 // assert loopEnd.numberOfSux() == 1 : "incorrect number of successors";
227 assert loopStart.isLinearScanLoopHeader() : "loop header flag must be set";
228 assert loopIdx >= 0 && loopIdx < numLoops : "loop index not set";
229 assert workList.isEmpty() : "work list must be empty before processing";
230
231 // add the end-block of the loop to the working list
232 workList.add(loopEnd);
233 setBlockInLoop(loopIdx, loopEnd);
234 do {
235 LIRBlock cur = workList.remove(workList.size() - 1);
236
237 if (C1XOptions.TraceLinearScanLevel >= 3) {
238 TTY.println(" processing B%d", cur.blockID());
239 }
240 assert isBlockInLoop(loopIdx, cur) : "bit in loop map must be set when block is in work list";
241
242 // recursive processing of all predecessors ends when start block of loop is reached
243 if (cur != loopStart) {
244 for (int j = cur.numberOfPreds() - 1; j >= 0; j--) {
245 LIRBlock pred = cur.predAt(j);
246
247 if (!isBlockInLoop(loopIdx, pred)) {
248 // this predecessor has not been processed yet, so add it to work list
249 if (C1XOptions.TraceLinearScanLevel >= 3) {
250 TTY.println(" pushing B%d", pred.blockID());
251 }
252 workList.add(pred);
253 setBlockInLoop(loopIdx, pred);
254 }
255 }
256 }
257 } while (!workList.isEmpty());
258 }
259 }
260
261 // check for non-natural loops (loops where the loop header does not dominate
262 // all other loop blocks = loops with multiple entries).
263 // such loops are ignored
264 void clearNonNaturalLoops(LIRBlock startBlock) {
265 for (int i = numLoops - 1; i >= 0; i--) {
266 if (isBlockInLoop(i, startBlock)) {
267 // loop i contains the entry block of the method.
268 // this is not a natural loop, so ignore it
269 if (C1XOptions.TraceLinearScanLevel >= 2) {
270 TTY.println("Loop %d is non-natural, so it is ignored", i);
271 }
272
273 for (int blockId = maxBlockId - 1; blockId >= 0; blockId--) {
274 clearBlockInLoop(i, blockId);
275 }
276 iterativeDominators = true;
277 }
278 }
279 }
280
281 void assignLoopDepth(LIRBlock startBlock) {
282 if (C1XOptions.TraceLinearScanLevel >= 3) {
283 TTY.println("----- computing loop-depth and weight");
284 }
285 initVisited();
286
287 assert workList.isEmpty() : "work list must be empty before processing";
288 workList.add(startBlock);
289
290 do {
291 LIRBlock cur = workList.remove(workList.size() - 1);
292
293 if (!isVisited(cur)) {
294 setVisited(cur);
295 if (C1XOptions.TraceLinearScanLevel >= 4) {
296 TTY.println("Computing loop depth for block B%d", cur.blockID());
297 }
298
299 // compute loop-depth and loop-index for the block
300 assert cur.loopDepth() == 0 : "cannot set loop-depth twice";
301 int i;
302 int loopDepth = 0;
303 int minLoopIdx = -1;
304 for (i = numLoops - 1; i >= 0; i--) {
305 if (isBlockInLoop(i, cur)) {
306 loopDepth++;
307 minLoopIdx = i;
308 }
309 }
310 cur.setLoopDepth(loopDepth);
311 cur.setLoopIndex(minLoopIdx);
312
313 // append all unvisited successors to work list
314 for (i = cur.numberOfSux() - 1; i >= 0; i--) {
315 workList.add(cur.suxAt(i));
316 }
317 }
318 } while (!workList.isEmpty());
319 }
320
321 int computeWeight(LIRBlock cur) {
322 LIRBlock singleSux = null;
323 if (cur.numberOfSux() == 1) {
324 singleSux = cur.suxAt(0);
325 }
326
327 // limit loop-depth to 15 bit (only for security reason, it will never be so big)
328 int weight = (cur.loopDepth() & 0x7FFF) << 16;
329
330 int curBit = 15;
331
332 // this is necessary for the (very rare) case that two successive blocks have
333 // the same loop depth, but a different loop index (can happen for endless loops
334 // with exception handlers)
335 if (!cur.isLinearScanLoopHeader()) {
336 weight |= 1 << curBit;
337 }
338 curBit--;
339
340 // loop end blocks (blocks that end with a backward branch) are added
341 // after all other blocks of the loop.
342 if (!cur.isLinearScanLoopEnd()) {
343 weight |= 1 << curBit;
344 }
345 curBit--;
346
347 // critical edge split blocks are preferred because then they have a greater
348 // probability to be completely empty
349 //if (cur.isCriticalEdgeSplit()) {
350 // weight |= 1 << curBit;
351 //}
352 //curBit--;
353
354 // exceptions should not be thrown in normal control flow, so these blocks
355 // are added as late as possible
356 // if (!(cur.end() instanceof Throw) && (singleSux == null || !(singleSux.end() instanceof Throw))) {
357 // weight |= 1 << curBit;
358 // }
359 // curBit--;
360 // if (!(cur.end() instanceof Return) && (singleSux == null || !(singleSux.end() instanceof Return))) {
361 // weight |= 1 << curBit;
362 // }
363 // curBit--;
364
365 // exceptions handlers are added as late as possible
366 // if (!cur.isExceptionEntry()) {
367 // weight |= 1 << curBit;
368 // }
369 // curBit--;
370
371 // guarantee that weight is > 0
372 weight |= 1;
373
374 assert curBit >= 0 : "too many flags";
375 assert weight > 0 : "weight cannot become negative";
376
377 return weight;
378 }
379
380 boolean readyForProcessing(LIRBlock cur) {
381 // Discount the edge just traveled.
382 // When the number drops to zero, all forward branches were processed
383 if (decForwardBranches(cur) != 0) {
384 return false;
385 }
386
387 assert !linearScanOrder.contains(cur) : "block already processed (block can be ready only once)";
388 assert !workList.contains(cur) : "block already in work-list (block can be ready only once)";
389 return true;
390 }
391
392 void sortIntoWorkList(LIRBlock cur) {
393 assert !workList.contains(cur) : "block already in work list";
394
395 int curWeight = computeWeight(cur);
396
397 // the linearScanNumber is used to cache the weight of a block
398 cur.setLinearScanNumber(curWeight);
399
400 if (C1XOptions.StressLinearScan) {
401 workList.add(0, cur);
402 return;
403 }
404
405 workList.add(null); // provide space for new element
406
407 int insertIdx = workList.size() - 1;
408 while (insertIdx > 0 && workList.get(insertIdx - 1).linearScanNumber() > curWeight) {
409 workList.set(insertIdx, workList.get(insertIdx - 1));
410 insertIdx--;
411 }
412 workList.set(insertIdx, cur);
413
414 if (C1XOptions.TraceLinearScanLevel >= 3) {
415 TTY.println("Sorted B%d into worklist. new worklist:", cur.blockID());
416 for (int i = 0; i < workList.size(); i++) {
417 TTY.println(String.format("%8d B%02d weight:%6x", i, workList.get(i).blockID(), workList.get(i).linearScanNumber()));
418 }
419 }
420
421 for (int i = 0; i < workList.size(); i++) {
422 assert workList.get(i).linearScanNumber() > 0 : "weight not set";
423 assert i == 0 || workList.get(i - 1).linearScanNumber() <= workList.get(i).linearScanNumber() : "incorrect order in worklist";
424 }
425 }
426
427 void appendBlock(LIRBlock cur) {
428 if (C1XOptions.TraceLinearScanLevel >= 3) {
429 TTY.println("appending block B%d (weight 0x%06x) to linear-scan order", cur.blockID(), cur.linearScanNumber());
430 }
431 assert !linearScanOrder.contains(cur) : "cannot add the same block twice";
432
433 // currently, the linear scan order and code emit order are equal.
434 // therefore the linearScanNumber and the weight of a block must also
435 // be equal.
436 cur.setLinearScanNumber(linearScanOrder.size());
437 linearScanOrder.add(cur);
438 }
439
440 void computeOrder(LIRBlock startBlock) {
441 if (C1XOptions.TraceLinearScanLevel >= 3) {
442 TTY.println("----- computing final block order");
443 }
444
445 // the start block is always the first block in the linear scan order
446 linearScanOrder = new ArrayList<LIRBlock>(numBlocks);
447 // appendBlock(startBlock);
448
449 LIRBlock stdEntry = startBlock; //.suxAt(0);
450
451 // start processing with standard entry block
452 assert workList.isEmpty() : "list must be empty before processing";
453
454 if (readyForProcessing(stdEntry)) {
455 sortIntoWorkList(stdEntry);
456 } else {
457 throw new CiBailout("the stdEntry must be ready for processing (otherwise, the method has no start block)");
458 }
459
460 do {
461 LIRBlock cur = workList.remove(workList.size() - 1);
462
463 appendBlock(cur);
464
465 int i;
466 int numSux = cur.numberOfSux();
467 // changed loop order to get "intuitive" order of if- and else-blocks
468 for (i = 0; i < numSux; i++) {
469 LIRBlock sux = cur.suxAt(i);
470 if (readyForProcessing(sux)) {
471 sortIntoWorkList(sux);
472 }
473 }
474 } while (workList.size() > 0);
475 }
476
477 public void printBlocks() {
478 if (C1XOptions.TraceLinearScanLevel >= 2) {
479 TTY.println("----- loop information:");
480 for (LIRBlock cur : linearScanOrder) {
481 TTY.print(String.format("%4d: B%02d: ", cur.linearScanNumber(), cur.blockID()));
482 for (int loopIdx = 0; loopIdx < numLoops; loopIdx++) {
483 TTY.print(String.format("%d = %b ", loopIdx, isBlockInLoop(loopIdx, cur)));
484 }
485 TTY.println(String.format(" . loopIndex: %2d, loopDepth: %2d", cur.loopIndex(), cur.loopDepth()));
486 }
487 }
488
489 if (C1XOptions.TraceLinearScanLevel >= 1) {
490 TTY.println("----- linear-scan block order:");
491 for (LIRBlock cur : linearScanOrder) {
492 TTY.print(String.format("%4d: B%02d loop: %2d depth: %2d", cur.linearScanNumber(), cur.blockID(), cur.loopIndex(), cur.loopDepth()));
493
494 TTY.print(cur.isLinearScanLoopHeader() ? " lh" : " ");
495 TTY.print(cur.isLinearScanLoopEnd() ? " le" : " ");
496
497 TTY.print(" dom: null ");
498
499
500 if (cur.numberOfPreds() > 0) {
501 TTY.print(" preds: ");
502 for (int j = 0; j < cur.numberOfPreds(); j++) {
503 LIRBlock pred = cur.predAt(j);
504 TTY.print("B%d ", pred.blockID());
505 }
506 }
507 if (cur.numberOfSux() > 0) {
508 TTY.print(" sux: ");
509 for (int j = 0; j < cur.numberOfSux(); j++) {
510 LIRBlock sux = cur.suxAt(j);
511 TTY.print("B%d ", sux.blockID());
512 }
513 }
514 TTY.println();
515 }
516 }
517 }
518
519 boolean verify() {
520 /* assert linearScanOrder.size() == numBlocks : "wrong number of blocks in list";
521
522 if (C1XOptions.StressLinearScan) {
523 // blocks are scrambled when StressLinearScan is used
524 return true;
525 }
526
527 // check that all successors of a block have a higher linear-scan-number
528 // and that all predecessors of a block have a lower linear-scan-number
529 // (only backward branches of loops are ignored)
530 int i;
531 for (i = 0; i < linearScanOrder.size(); i++) {
532 BlockBegin cur = linearScanOrder.get(i);
533
534 assert cur.linearScanNumber() == i : "incorrect linearScanNumber";
535 assert cur.linearScanNumber() >= 0 && cur.linearScanNumber() == linearScanOrder.indexOf(cur) : "incorrect linearScanNumber";
536
537 for (BlockBegin sux : cur.end().successors()) {
538 assert sux.linearScanNumber() >= 0 && sux.linearScanNumber() == linearScanOrder.indexOf(sux) : "incorrect linearScanNumber";
539 if (!cur.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopEnd)) {
540 assert cur.linearScanNumber() < sux.linearScanNumber() : "invalid order";
541 }
542 if (cur.loopDepth() == sux.loopDepth()) {
543 assert cur.loopIndex() == sux.loopIndex() || sux.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopHeader) : "successing blocks with same loop depth must have same loop index";
544 }
545 }
546
547 for (BlockBegin pred : cur.predecessors()) {
548 assert pred.linearScanNumber() >= 0 && pred.linearScanNumber() == linearScanOrder.indexOf(pred) : "incorrect linearScanNumber";
549 if (!cur.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopHeader)) {
550 assert cur.linearScanNumber() > pred.linearScanNumber() : "invalid order";
551 }
552 if (cur.loopDepth() == pred.loopDepth()) {
553 assert cur.loopIndex() == pred.loopIndex() || cur.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopHeader) : "successing blocks with same loop depth must have same loop index";
554 }
555
556 assert cur.dominator().linearScanNumber() <= pred.linearScanNumber() : "dominator must be before predecessors";
557 }
558
559 // check dominator
560 if (i == 0) {
561 assert cur.dominator() == null : "first block has no dominator";
562 } else {
563 assert cur.dominator() != null : "all but first block must have dominator";
564 }
565 assert cur.numberOfPreds() != 1 || cur.dominator() == cur.predAt(0) || cur.isExceptionEntry() : "Single predecessor must also be dominator";
566 }
567
568 // check that all loops are continuous
569 for (int loopIdx = 0; loopIdx < numLoops; loopIdx++) {
570 int blockIdx = 0;
571 assert !isBlockInLoop(loopIdx, linearScanOrder.get(blockIdx)) : "the first block must not be present in any loop";
572
573 // skip blocks before the loop
574 while (blockIdx < numBlocks && !isBlockInLoop(loopIdx, linearScanOrder.get(blockIdx))) {
575 blockIdx++;
576 }
577 // skip blocks of loop
578 while (blockIdx < numBlocks && isBlockInLoop(loopIdx, linearScanOrder.get(blockIdx))) {
579 blockIdx++;
580 }
581 // after the first non-loop block : there must not be another loop-block
582 while (blockIdx < numBlocks) {
583 assert !isBlockInLoop(loopIdx, linearScanOrder.get(blockIdx)) : "loop not continuous in linear-scan order";
584 blockIdx++;
585 }
586 }
587 */
588 return true;
589 }
590 }