Mercurial > hg > graal-jvmci-8

comparison graal/GraalCompiler/src/com/sun/c1x/alloc/LinearScanWalker.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 42450f536d24
children a2f62de90c76
comparison
equal deleted inserted replaced
2717:bd85cf08720a 2718:c1ce2a53d6c3
56 // accessors mapped to same functions in class LinearScan 56 // accessors mapped to same functions in class LinearScan
57 int blockCount() { 57 int blockCount() {
58 return allocator.blockCount(); 58 return allocator.blockCount();
59 } 59 }
60 60
61 BlockBegin blockAt(int idx) { 61 LIRBlock blockAt(int idx) {
62 return allocator.blockAt(idx); 62 return allocator.blockAt(idx);
63 } 63 }
64 64
65 BlockBegin blockOfOpWithId(int opId) { 65 LIRBlock blockOfOpWithId(int opId) {
66 return allocator.blockForId(opId); 66 return allocator.blockForId(opId);
67 } 67 }
68 68
69 LinearScanWalker(LinearScan allocator, Interval unhandledFixedFirst, Interval unhandledAnyFirst) { 69 LinearScanWalker(LinearScan allocator, Interval unhandledFixedFirst, Interval unhandledAnyFirst) {
70 super(allocator, unhandledFixedFirst, unhandledAnyFirst); 70 super(allocator, unhandledFixedFirst, unhandledAnyFirst);
226 void insertMove(int opId, Interval srcIt, Interval dstIt) { 226 void insertMove(int opId, Interval srcIt, Interval dstIt) {
227 // output all moves here. When source and target are equal, the move is 227 // output all moves here. When source and target are equal, the move is
228 // optimized away later in assignRegNums 228 // optimized away later in assignRegNums
229 229
230 opId = (opId + 1) & ~1; 230 opId = (opId + 1) & ~1;
231 BlockBegin opBlock = allocator.blockForId(opId); 231 LIRBlock opBlock = allocator.blockForId(opId);
232 assert opId > 0 && allocator.blockForId(opId - 2) == opBlock : "cannot insert move at block boundary"; 232 assert opId > 0 && allocator.blockForId(opId - 2) == opBlock : "cannot insert move at block boundary";
233 233
234 // calculate index of instruction inside instruction list of current block 234 // calculate index of instruction inside instruction list of current block
235 // the minimal index (for a block with no spill moves) can be calculated because the 235 // the minimal index (for a block with no spill moves) can be calculated because the
236 // numbering of instructions is known. 236 // numbering of instructions is known.
250 // insert new instruction before instruction at position index 250 // insert new instruction before instruction at position index
251 moveResolver.moveInsertPosition(opBlock.lir(), index - 1); 251 moveResolver.moveInsertPosition(opBlock.lir(), index - 1);
252 moveResolver.addMapping(srcIt, dstIt); 252 moveResolver.addMapping(srcIt, dstIt);
253 } 253 }
254 254
255 int findOptimalSplitPos(BlockBegin minBlock, BlockBegin maxBlock, int maxSplitPos) { 255 int findOptimalSplitPos(LIRBlock minBlock, LIRBlock maxBlock, int maxSplitPos) {
256 int fromBlockNr = minBlock.linearScanNumber(); 256 int fromBlockNr = minBlock.linearScanNumber();
257 int toBlockNr = maxBlock.linearScanNumber(); 257 int toBlockNr = maxBlock.linearScanNumber();
258 258
259 assert 0 <= fromBlockNr && fromBlockNr < blockCount() : "out of range"; 259 assert 0 <= fromBlockNr && fromBlockNr < blockCount() : "out of range";
260 assert 0 <= toBlockNr && toBlockNr < blockCount() : "out of range"; 260 assert 0 <= toBlockNr && toBlockNr < blockCount() : "out of range";
261 assert fromBlockNr < toBlockNr : "must cross block boundary"; 261 assert fromBlockNr < toBlockNr : "must cross block boundary";
262 262
263 // Try to split at end of maxBlock. If this would be after 263 // Try to split at end of maxBlock. If this would be after
264 // maxSplitPos, then use the begin of maxBlock 264 // maxSplitPos, then use the begin of maxBlock
265 int optimalSplitPos = maxBlock.lirBlock.lastLirInstructionId() + 2; 265 int optimalSplitPos = maxBlock.lastLirInstructionId() + 2;
266 if (optimalSplitPos > maxSplitPos) { 266 if (optimalSplitPos > maxSplitPos) {
267 optimalSplitPos = maxBlock.lirBlock.firstLirInstructionId(); 267 optimalSplitPos = maxBlock.firstLirInstructionId();
268 } 268 }
269 269
270 int minLoopDepth = maxBlock.loopDepth(); 270 int minLoopDepth = maxBlock.loopDepth();
271 for (int i = toBlockNr - 1; i >= fromBlockNr; i--) { 271 for (int i = toBlockNr - 1; i >= fromBlockNr; i--) {
272 BlockBegin cur = blockAt(i); 272 LIRBlock cur = blockAt(i);
273 273
274 if (cur.loopDepth() < minLoopDepth) { 274 if (cur.loopDepth() < minLoopDepth) {
275 // block with lower loop-depth found . split at the end of this block 275 // block with lower loop-depth found . split at the end of this block
276 minLoopDepth = cur.loopDepth(); 276 minLoopDepth = cur.loopDepth();
277 optimalSplitPos = cur.lirBlock.lastLirInstructionId() + 2; 277 optimalSplitPos = cur.lastLirInstructionId() + 2;
278 } 278 }
279 } 279 }
280 assert optimalSplitPos > allocator.maxOpId() || allocator.isBlockBegin(optimalSplitPos) : "algorithm must move split pos to block boundary"; 280 assert optimalSplitPos > allocator.maxOpId() || allocator.isBlockBegin(optimalSplitPos) : "algorithm must move split pos to block boundary";
281 281
282 return optimalSplitPos; 282 return optimalSplitPos;
296 assert minSplitPos > 0 : "cannot access minSplitPos - 1 otherwise"; 296 assert minSplitPos > 0 : "cannot access minSplitPos - 1 otherwise";
297 297
298 // reason for using minSplitPos - 1: when the minimal split pos is exactly at the 298 // reason for using minSplitPos - 1: when the minimal split pos is exactly at the
299 // beginning of a block, then minSplitPos is also a possible split position. 299 // beginning of a block, then minSplitPos is also a possible split position.
300 // Use the block before as minBlock, because then minBlock.lastLirInstructionId() + 2 == minSplitPos 300 // Use the block before as minBlock, because then minBlock.lastLirInstructionId() + 2 == minSplitPos
301 BlockBegin minBlock = allocator.blockForId(minSplitPos - 1); 301 LIRBlock minBlock = allocator.blockForId(minSplitPos - 1);
302 302
303 // reason for using maxSplitPos - 1: otherwise there would be an assert on failure 303 // reason for using maxSplitPos - 1: otherwise there would be an assert on failure
304 // when an interval ends at the end of the last block of the method 304 // when an interval ends at the end of the last block of the method
305 // (in this case, maxSplitPos == allocator().maxLirOpId() + 2, and there is no 305 // (in this case, maxSplitPos == allocator().maxLirOpId() + 2, and there is no
306 // block at this opId) 306 // block at this opId)
307 BlockBegin maxBlock = allocator.blockForId(maxSplitPos - 1); 307 LIRBlock maxBlock = allocator.blockForId(maxSplitPos - 1);
308 308
309 assert minBlock.linearScanNumber() <= maxBlock.linearScanNumber() : "invalid order"; 309 assert minBlock.linearScanNumber() <= maxBlock.linearScanNumber() : "invalid order";
310 if (minBlock == maxBlock) { 310 if (minBlock == maxBlock) {
311 // split position cannot be moved to block boundary : so split as late as possible 311 // split position cannot be moved to block boundary : so split as late as possible
312 if (C1XOptions.TraceLinearScanLevel >= 4) { 312 if (C1XOptions.TraceLinearScanLevel >= 4) {
326 optimalSplitPos = maxSplitPos; 326 optimalSplitPos = maxSplitPos;
327 327
328 } else { 328 } else {
329 // seach optimal block boundary between minSplitPos and maxSplitPos 329 // seach optimal block boundary between minSplitPos and maxSplitPos
330 if (C1XOptions.TraceLinearScanLevel >= 4) { 330 if (C1XOptions.TraceLinearScanLevel >= 4) {
331 TTY.println(" moving split pos to optimal block boundary between block B%d and B%d", minBlock.blockID, maxBlock.blockID); 331 TTY.println(" moving split pos to optimal block boundary between block B%d and B%d", minBlock.blockID(), maxBlock.blockID());
332 } 332 }
333 333
334 if (doLoopOptimization) { 334 if (doLoopOptimization) {
335 // Loop optimization: if a loop-end marker is found between min- and max-position : 335 // Loop optimization: if a loop-end marker is found between min- and max-position :
336 // then split before this loop 336 // then split before this loop
337 int loopEndPos = interval.nextUsageExact(RegisterPriority.LiveAtLoopEnd, minBlock.lirBlock.lastLirInstructionId() + 2); 337 int loopEndPos = interval.nextUsageExact(RegisterPriority.LiveAtLoopEnd, minBlock.lastLirInstructionId() + 2);
338 if (C1XOptions.TraceLinearScanLevel >= 4) { 338 if (C1XOptions.TraceLinearScanLevel >= 4) {
339 TTY.println(" loop optimization: loop end found at pos %d", loopEndPos); 339 TTY.println(" loop optimization: loop end found at pos %d", loopEndPos);
340 } 340 }
341 341
342 assert loopEndPos > minSplitPos : "invalid order"; 342 assert loopEndPos > minSplitPos : "invalid order";
344 // loop-end marker found between min- and max-position 344 // loop-end marker found between min- and max-position
345 // if it is not the end marker for the same loop as the min-position : then move 345 // if it is not the end marker for the same loop as the min-position : then move
346 // the max-position to this loop block. 346 // the max-position to this loop block.
347 // Desired result: uses tagged as shouldHaveRegister inside a loop cause a reloading 347 // Desired result: uses tagged as shouldHaveRegister inside a loop cause a reloading
348 // of the interval (normally, only mustHaveRegister causes a reloading) 348 // of the interval (normally, only mustHaveRegister causes a reloading)
349 BlockBegin loopBlock = allocator.blockForId(loopEndPos); 349 LIRBlock loopBlock = allocator.blockForId(loopEndPos);
350 350
351 if (C1XOptions.TraceLinearScanLevel >= 4) { 351 if (C1XOptions.TraceLinearScanLevel >= 4) {
352 TTY.println(" interval is used in loop that ends in block B%d, so trying to move maxBlock back from B%d to B%d", loopBlock.blockID, maxBlock.blockID, loopBlock.blockID); 352 TTY.println(" interval is used in loop that ends in block B%d, so trying to move maxBlock back from B%d to B%d", loopBlock.blockID(), maxBlock.blockID(), loopBlock.blockID());
353 } 353 }
354 assert loopBlock != minBlock : "loopBlock and minBlock must be different because block boundary is needed between"; 354 assert loopBlock != minBlock : "loopBlock and minBlock must be different because block boundary is needed between";
355 355
356 optimalSplitPos = findOptimalSplitPos(minBlock, loopBlock, loopBlock.lirBlock.lastLirInstructionId() + 2); 356 optimalSplitPos = findOptimalSplitPos(minBlock, loopBlock, loopBlock.lastLirInstructionId() + 2);
357 if (optimalSplitPos == loopBlock.lirBlock.lastLirInstructionId() + 2) { 357 if (optimalSplitPos == loopBlock.lastLirInstructionId() + 2) {
358 optimalSplitPos = -1; 358 optimalSplitPos = -1;
359 if (C1XOptions.TraceLinearScanLevel >= 4) { 359 if (C1XOptions.TraceLinearScanLevel >= 4) {
360 TTY.println(" loop optimization not necessary"); 360 TTY.println(" loop optimization not necessary");
361 } 361 }
362 } else { 362 } else {