Mercurial > hg > graal-compiler

comparison graal/GraalCompiler/src/com/sun/c1x/ir/ComputeLinearScanOrder.java @ 2718:c1ce2a53d6c3

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Attempt to remove dependency between backend and BlockBegin.
author Thomas Wuerthinger <thomas@wuerthinger.net>
date Thu, 19 May 2011 16:05:42 +0200
parents bd85cf08720a
children 3fbe58ac818d
comparison
equal deleted inserted replaced
2717:bd85cf08720a 2718:c1ce2a53d6c3
39 39
40 List<BlockBegin> linearScanOrder; // the resulting list of blocks in correct order 40 List<BlockBegin> linearScanOrder; // the resulting list of blocks in correct order
41 41
42 final CiBitMap visitedBlocks; // used for recursive processing of blocks 42 final CiBitMap visitedBlocks; // used for recursive processing of blocks
43 final CiBitMap activeBlocks; // used for recursive processing of blocks 43 final CiBitMap activeBlocks; // used for recursive processing of blocks
44 final CiBitMap dominatorBlocks; // temporary BitMap used for computation of dominator
45 final int[] forwardBranches; // number of incoming forward branches for each block 44 final int[] forwardBranches; // number of incoming forward branches for each block
46 final List<BlockBegin> loopEndBlocks; // list of all loop end blocks collected during countEdges 45 final List<BlockBegin> loopEndBlocks; // list of all loop end blocks collected during countEdges
47 BitMap2D loopMap; // two-dimensional bit set: a bit is set if a block is contained in a loop 46 BitMap2D loopMap; // two-dimensional bit set: a bit is set if a block is contained in a loop
48 final List<BlockBegin> workList; // temporary list (used in markLoops and computeOrder) 47 final List<BlockBegin> workList; // temporary list (used in markLoops and computeOrder)
49 48
110 public ComputeLinearScanOrder(int maxBlockId, BlockBegin startBlock) { 109 public ComputeLinearScanOrder(int maxBlockId, BlockBegin startBlock) {
111 110
112 this.maxBlockId = maxBlockId; 111 this.maxBlockId = maxBlockId;
113 visitedBlocks = new CiBitMap(maxBlockId); 112 visitedBlocks = new CiBitMap(maxBlockId);
114 activeBlocks = new CiBitMap(maxBlockId); 113 activeBlocks = new CiBitMap(maxBlockId);
115 dominatorBlocks = new CiBitMap(maxBlockId);
116 forwardBranches = new int[maxBlockId]; 114 forwardBranches = new int[maxBlockId];
117 loopEndBlocks = new ArrayList<BlockBegin>(8); 115 loopEndBlocks = new ArrayList<BlockBegin>(8);
118 workList = new ArrayList<BlockBegin>(8); 116 workList = new ArrayList<BlockBegin>(8);
119 117
120 countEdges(startBlock, null); 118 countEdges(startBlock, null);
121 119
122 if (numLoops > 0) { 120 if (numLoops > 0) {
123 markLoops(); 121 markLoops();
124 clearNonNaturalLoops(startBlock); 122 clearNonNaturalLoops(startBlock);
125 assignLoopDepth(startBlock);
126 } 123 }
127 124
128 computeOrder(startBlock); 125 computeOrder(startBlock);
129 126
130 printBlocks(); 127 printBlocks();
186 // Each loop has a unique number. 183 // Each loop has a unique number.
187 // When multiple loops are nested, assignLoopDepth assumes that the 184 // When multiple loops are nested, assignLoopDepth assumes that the
188 // innermost loop has the lowest number. This is guaranteed by setting 185 // innermost loop has the lowest number. This is guaranteed by setting
189 // the loop number after the recursive calls for the successors above 186 // the loop number after the recursive calls for the successors above
190 // have returned. 187 // have returned.
191 if (cur.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopHeader)) { 188 // if (cur.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopHeader)) {
192 assert cur.loopIndex() == -1 : "cannot set loop-index twice"; 189 // // assert cur.loopIndex() == -1 : "cannot set loop-index twice";
193 if (C1XOptions.TraceLinearScanLevel >= 3) { 190 // if (C1XOptions.TraceLinearScanLevel >= 3) {
194 TTY.println("Block B%d is loop header of loop %d", cur.blockID, numLoops); 191 // TTY.println("Block B%d is loop header of loop %d", cur.blockID, numLoops);
195 } 192 // }
196 193 //
197 cur.setLoopIndex(numLoops); 194 // cur.setLoopIndex(numLoops);
198 numLoops++; 195 // numLoops++;
199 } 196 // }
200 197
201 if (C1XOptions.TraceLinearScanLevel >= 3) { 198 if (C1XOptions.TraceLinearScanLevel >= 3) {
202 TTY.println("Finished counting edges for block B%d", cur.blockID); 199 TTY.println("Finished counting edges for block B%d", cur.blockID);
203 } 200 }
204 } 201 }
205 202
206 private void markLoops() { 203 private void markLoops() {
207 if (C1XOptions.TraceLinearScanLevel >= 3) { 204 // if (C1XOptions.TraceLinearScanLevel >= 3) {
208 TTY.println("----- marking loops"); 205 // TTY.println("----- marking loops");
209 } 206 // }
210 207 //
211 loopMap = new BitMap2D(numLoops, maxBlockId); 208 // loopMap = new BitMap2D(numLoops, maxBlockId);
212 209 //
213 for (int i = loopEndBlocks.size() - 1; i >= 0; i--) { 210 // for (int i = loopEndBlocks.size() - 1; i >= 0; i--) {
214 BlockBegin loopEnd = loopEndBlocks.get(i); 211 // BlockBegin loopEnd = loopEndBlocks.get(i);
215 BlockBegin loopStart = loopEnd.suxAt(0); 212 // BlockBegin loopStart = loopEnd.suxAt(0);
216 int loopIdx = loopStart.loopIndex(); 213 // int loopIdx = loopStart.loopIndex();
217 214 //
218 if (C1XOptions.TraceLinearScanLevel >= 3) { 215 // if (C1XOptions.TraceLinearScanLevel >= 3) {
219 TTY.println("Processing loop from B%d to B%d (loop %d):", loopStart.blockID, loopEnd.blockID, loopIdx); 216 // TTY.println("Processing loop from B%d to B%d (loop %d):", loopStart.blockID, loopEnd.blockID, loopIdx);
220 } 217 // }
221 assert loopEnd.isLinearScanLoopEnd() : "loop end flag must be set"; 218 // assert loopEnd.isLinearScanLoopEnd() : "loop end flag must be set";
222 assert loopStart.isLinearScanLoopHeader() : "loop header flag must be set"; 219 // assert loopStart.isLinearScanLoopHeader() : "loop header flag must be set";
223 assert loopIdx >= 0 && loopIdx < numLoops : "loop index not set"; 220 // assert loopIdx >= 0 && loopIdx < numLoops : "loop index not set";
224 assert workList.isEmpty() : "work list must be empty before processing"; 221 // assert workList.isEmpty() : "work list must be empty before processing";
225 222 //
226 // add the end-block of the loop to the working list 223 // // add the end-block of the loop to the working list
227 workList.add(loopEnd); 224 // workList.add(loopEnd);
228 setBlockInLoop(loopIdx, loopEnd); 225 // setBlockInLoop(loopIdx, loopEnd);
229 do { 226 // do {
230 BlockBegin cur = workList.remove(workList.size() - 1); 227 // BlockBegin cur = workList.remove(workList.size() - 1);
231 228 //
232 if (C1XOptions.TraceLinearScanLevel >= 3) { 229 // if (C1XOptions.TraceLinearScanLevel >= 3) {
233 TTY.println(" processing B%d", cur.blockID); 230 // TTY.println(" processing B%d", cur.blockID);
234 } 231 // }
235 assert isBlockInLoop(loopIdx, cur) : "bit in loop map must be set when block is in work list"; 232 // //assert isBlockInLoop(loopIdx, cur) : "bit in loop map must be set when block is in work list";
236 233 //
237 // recursive processing of all predecessors ends when start block of loop is reached 234 // // recursive processing of all predecessors ends when start block of loop is reached
238 if (cur != loopStart) { 235 // if (cur != loopStart) {
239 for (int j = cur.numberOfPreds() - 1; j >= 0; j--) { 236 // for (int j = cur.numberOfPreds() - 1; j >= 0; j--) {
240 BlockBegin pred = cur.predAt(j).block(); 237 // BlockBegin pred = cur.predAt(j).block();
241 238 //
242 if (!isBlockInLoop(loopIdx, pred)) { 239 // if (!isBlockInLoop(loopIdx, pred)) {
243 // this predecessor has not been processed yet, so add it to work list 240 // // this predecessor has not been processed yet, so add it to work list
244 if (C1XOptions.TraceLinearScanLevel >= 3) { 241 // if (C1XOptions.TraceLinearScanLevel >= 3) {
245 TTY.println(" pushing B%d", pred.blockID); 242 // TTY.println(" pushing B%d", pred.blockID);
246 } 243 // }
247 workList.add(pred); 244 // workList.add(pred);
248 setBlockInLoop(loopIdx, pred); 245 // setBlockInLoop(loopIdx, pred);
249 } 246 // }
250 } 247 // }
251 } 248 // }
252 } while (!workList.isEmpty()); 249 // } while (!workList.isEmpty());
253 } 250 // }
254 } 251 }
255 252
256 // check for non-natural loops (loops where the loop header does not dominate 253 // check for non-natural loops (loops where the loop header does not dominate
257 // all other loop blocks = loops with multiple entries). 254 // all other loop blocks = loops with multiple entries).
258 // such loops are ignored 255 // such loops are ignored
259 private void clearNonNaturalLoops(BlockBegin startBlock) { 256 private void clearNonNaturalLoops(BlockBegin startBlock) {
260 for (int i = numLoops - 1; i >= 0; i--) { 257 // for (int i = numLoops - 1; i >= 0; i--) {
261 if (isBlockInLoop(i, startBlock)) { 258 // if (isBlockInLoop(i, startBlock)) {
262 // loop i contains the entry block of the method. 259 // // loop i contains the entry block of the method.
263 // this is not a natural loop, so ignore it 260 // // this is not a natural loop, so ignore it
264 if (C1XOptions.TraceLinearScanLevel >= 2) { 261 // if (C1XOptions.TraceLinearScanLevel >= 2) {
265 TTY.println("Loop %d is non-natural, so it is ignored", i); 262 // TTY.println("Loop %d is non-natural, so it is ignored", i);
266 } 263 // }
267 264 //
268 for (int blockId = maxBlockId - 1; blockId >= 0; blockId--) { 265 // for (int blockId = maxBlockId - 1; blockId >= 0; blockId--) {
269 clearBlockInLoop(i, blockId); 266 // clearBlockInLoop(i, blockId);
270 } 267 // }
271 iterativeDominators = true; 268 // iterativeDominators = true;
272 } 269 // }
273 } 270 // }
274 }
275
276 private void assignLoopDepth(BlockBegin startBlock) {
277 if (C1XOptions.TraceLinearScanLevel >= 3) {
278 TTY.println("----- computing loop-depth and weight");
279 }
280 initVisited();
281
282 assert workList.isEmpty() : "work list must be empty before processing";
283 workList.add(startBlock);
284
285 do {
286 BlockBegin cur = workList.remove(workList.size() - 1);
287
288 if (!isVisited(cur)) {
289 setVisited(cur);
290 if (C1XOptions.TraceLinearScanLevel >= 4) {
291 TTY.println("Computing loop depth for block B%d", cur.blockID);
292 }
293
294 // compute loop-depth and loop-index for the block
295 assert cur.loopDepth() == 0 : "cannot set loop-depth twice";
296 int i;
297 int loopDepth = 0;
298 int minLoopIdx = -1;
299 for (i = numLoops - 1; i >= 0; i--) {
300 if (isBlockInLoop(i, cur)) {
301 loopDepth++;
302 minLoopIdx = i;
303 }
304 }
305 cur.setLoopDepth(loopDepth);
306 cur.setLoopIndex(minLoopIdx);
307
308 // append all unvisited successors to work list
309 cur.allSuccessorsDo(true, new BlockClosure() {
310 public void apply(BlockBegin block) {
311 workList.add(block);
312 }
313 });
314 }
315 } while (!workList.isEmpty());
316 } 271 }
317 272
318 private int computeWeight(BlockBegin cur) { 273 private int computeWeight(BlockBegin cur) {
319 BlockBegin singleSux = null; 274 BlockBegin singleSux = null;
320 if (cur.numberOfSux() == 1) { 275 if (cur.numberOfSux() == 1) {
321 singleSux = cur.suxAt(0); 276 singleSux = cur.suxAt(0);
322 } 277 }
323 278
324 // limit loop-depth to 15 bit (only for security reason, it will never be so big) 279 // limit loop-depth to 15 bit (only for security reason, it will never be so big)
325 int weight = (cur.loopDepth() & 0x7FFF) << 16; 280 int loopDepth = 0; // TODO(tw): Assign loop depth
281 int weight = (loopDepth & 0x7FFF) << 16;
326 282
327 int curBit = 15; 283 int curBit = 15;
328 284
329 // this is necessary for the (very rare) case that two successive blocks have 285 // this is necessary for the (very rare) case that two successive blocks have
330 // the same loop depth, but a different loop index (can happen for endless loops 286 // the same loop depth, but a different loop index (can happen for endless loops
455 public void printBlocks() { 411 public void printBlocks() {
456 if (C1XOptions.TraceLinearScanLevel >= 2) { 412 if (C1XOptions.TraceLinearScanLevel >= 2) {
457 TTY.println("----- loop information:"); 413 TTY.println("----- loop information:");
458 for (BlockBegin cur : linearScanOrder) { 414 for (BlockBegin cur : linearScanOrder) {
459 TTY.print(String.format("%4d: B%02d: ", cur.linearScanNumber(), cur.blockID)); 415 TTY.print(String.format("%4d: B%02d: ", cur.linearScanNumber(), cur.blockID));
460 for (int loopIdx = 0; loopIdx < numLoops; loopIdx++) { 416 // for (int loopIdx = 0; loopIdx < numLoops; loopIdx++) {
461 TTY.print(String.format("%d = %b ", loopIdx, isBlockInLoop(loopIdx, cur))); 417 // TTY.print(String.format("%d = %b ", loopIdx, isBlockInLoop(loopIdx, cur)));
462 } 418 // }
463 TTY.println(String.format(" . loopIndex: %2d, loopDepth: %2d", cur.loopIndex(), cur.loopDepth())); 419 TTY.println(String.format(" . loopIndex: %2d, loopDepth: %2d", -1, -1));
464 } 420 }
465 } 421 }
466 422
467 if (C1XOptions.TraceLinearScanLevel >= 1) { 423 if (C1XOptions.TraceLinearScanLevel >= 1) {
468 TTY.println("----- linear-scan block order:"); 424 TTY.println("----- linear-scan block order:");
469 for (BlockBegin cur : linearScanOrder) { 425 for (BlockBegin cur : linearScanOrder) {
470 TTY.print(String.format("%4d: B%02d loop: %2d depth: %2d", cur.linearScanNumber(), cur.blockID, cur.loopIndex(), cur.loopDepth())); 426 TTY.print(String.format("%4d: B%02d loop: %2d depth: %2d", cur.linearScanNumber(), cur.blockID, -1, -1));
471 427
472 TTY.print(cur.isLinearScanLoopHeader() ? " lh" : " "); 428 TTY.print(cur.isLinearScanLoopHeader() ? " lh" : " ");
473 TTY.print(cur.isLinearScanLoopEnd() ? " le" : " "); 429 TTY.print(cur.isLinearScanLoopEnd() ? " le" : " ");
474 430
475 if (cur.numberOfPreds() > 0) { 431 if (cur.numberOfPreds() > 0) {
512 for (BlockBegin sux : cur.end().blockSuccessors()) { 468 for (BlockBegin sux : cur.end().blockSuccessors()) {
513 assert sux.linearScanNumber() >= 0 && sux.linearScanNumber() == linearScanOrder.indexOf(sux) : "incorrect linearScanNumber"; 469 assert sux.linearScanNumber() >= 0 && sux.linearScanNumber() == linearScanOrder.indexOf(sux) : "incorrect linearScanNumber";
514 if (!cur.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopEnd)) { 470 if (!cur.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopEnd)) {
515 assert cur.linearScanNumber() < sux.linearScanNumber() : "invalid order"; 471 assert cur.linearScanNumber() < sux.linearScanNumber() : "invalid order";
516 } 472 }
517 if (cur.loopDepth() == sux.loopDepth()) { 473 //if (cur.loopDepth() == sux.loopDepth()) {
518 assert cur.loopIndex() == sux.loopIndex() || sux.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopHeader) : "successing blocks with same loop depth must have same loop index"; 474 // assert cur.loopIndex() == sux.loopIndex() || sux.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopHeader) : "successing blocks with same loop depth must have same loop index";
519 } 475 //}
520 } 476 }
521 477
522 for (Instruction pred : cur.blockPredecessors()) { 478 for (Instruction pred : cur.blockPredecessors()) {
523 BlockBegin begin = pred.block(); 479 BlockBegin begin = pred.block();
524 assert begin.linearScanNumber() >= 0 && begin.linearScanNumber() == linearScanOrder.indexOf(begin) : "incorrect linearScanNumber"; 480 assert begin.linearScanNumber() >= 0 && begin.linearScanNumber() == linearScanOrder.indexOf(begin) : "incorrect linearScanNumber";
525 if (!cur.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopHeader)) { 481 if (!cur.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopHeader)) {
526 assert cur.linearScanNumber() > begin.linearScanNumber() : "invalid order"; 482 assert cur.linearScanNumber() > begin.linearScanNumber() : "invalid order";
527 } 483 }
528 if (cur.loopDepth() == begin.loopDepth()) { 484 //if (cur.loopDepth() == begin.loopDepth()) {
529 assert cur.loopIndex() == begin.loopIndex() || cur.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopHeader) : "successing blocks with same loop depth must have same loop index"; 485 // assert cur.loopIndex() == begin.loopIndex() || cur.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopHeader) : "successing blocks with same loop depth must have same loop index";
530 } 486 //}
531 } 487 }
532 } 488 }
533 489
534 // check that all loops are continuous 490 // check that all loops are continuous
535 for (int loopIdx = 0; loopIdx < numLoops; loopIdx++) { 491 // for (int loopIdx = 0; loopIdx < numLoops; loopIdx++) {
536 int blockIdx = 0; 492 // int blockIdx = 0;
537 assert !isBlockInLoop(loopIdx, linearScanOrder.get(blockIdx)) : "the first block must not be present in any loop"; 493 // assert !isBlockInLoop(loopIdx, linearScanOrder.get(blockIdx)) : "the first block must not be present in any loop";
538 494 //
539 // skip blocks before the loop 495 // // skip blocks before the loop
540 while (blockIdx < numBlocks && !isBlockInLoop(loopIdx, linearScanOrder.get(blockIdx))) { 496 // while (blockIdx < numBlocks && !isBlockInLoop(loopIdx, linearScanOrder.get(blockIdx))) {
541 blockIdx++; 497 // blockIdx++;
542 } 498 // }
543 // skip blocks of loop 499 // // skip blocks of loop
544 while (blockIdx < numBlocks && isBlockInLoop(loopIdx, linearScanOrder.get(blockIdx))) { 500 // while (blockIdx < numBlocks && isBlockInLoop(loopIdx, linearScanOrder.get(blockIdx))) {
545 blockIdx++; 501 // blockIdx++;
546 } 502 // }
547 // after the first non-loop block : there must not be another loop-block 503 // // after the first non-loop block : there must not be another loop-block
548 while (blockIdx < numBlocks) { 504 // while (blockIdx < numBlocks) {
549 assert !isBlockInLoop(loopIdx, linearScanOrder.get(blockIdx)) : "loop not continuous in linear-scan order"; 505 // assert !isBlockInLoop(loopIdx, linearScanOrder.get(blockIdx)) : "loop not continuous in linear-scan order";
550 blockIdx++; 506 // blockIdx++;
551 } 507 // }
552 } 508 // }
553 509
554 return true; 510 return true;
555 } 511 }
556 } 512 }