Mercurial > hg > graal-jvmci-8
comparison graal/GraalCompiler/src/com/sun/c1x/alloc/LinearScanWalker.java @ 2718:c1ce2a53d6c3
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 { |