Robert Lytton
2013-Aug-22 11:15 UTC
[LLVMdev] PrescheduleNodesWithMultipleUses() causing failure in PickNodeToScheduleBottomUp() ???
Hi I have brought everything together in this email. The problem ======= Take the following DAG (arrow to predecessor): SetUp2 SetUp1 ^ ^ | | | | Destroy2---->PredSU <----SU ^ ^ ^ | | | | | | ----------- | --------- | | | Destroy1 ^ | In this example there are two successors of 'PredSU' with type getCallFrameDestroyOpcode (Destroy) and one is a successor of the other. Taking the successor of the two Destroys (Destroy1), noted that it's matching getCallFrameSetupOpcode (Setup1) is a predecessor of 'SU'. In this situation, re-routing the dependency on 'PredSU' through 'SU' will cause a dead lock Viz: SetUp2 PredSU SetUp1 ^ ^ ^ | | | | | | Destroy2-----> SU ------- ^ ^ ^ | | | | | | ----------- | | | | | Destroy1 ^ | Outstanding issues =========== 1. Is it too aggressive in searching predecessors and successors? Should the algorithm give up and assume the worst if the depth of search reaches a predefined limit? 2. Should the initial search for 'SetUp1' and 'Destroy1' only search along chains? viz conditional upon II->isCtrl() 3. Is it possible to input a DAG for testing? What is the best way to construct the test case? Using an IR as input does not guarantee the required DAG will be output for testing. 4. Where should the test be placed? (How do I test for no-assert?) Please do comment. Robert -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20130822/48b7e816/attachment.html> -------------- next part -------------- A non-text attachment was scrubbed... Name: PatchCallResourceDeadLock Type: application/octet-stream Size: 6952 bytes Desc: PatchCallResourceDeadLock URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20130822/48b7e816/attachment.obj>
Dan Gohman
2013-Aug-22 17:37 UTC
[LLVMdev] PrescheduleNodesWithMultipleUses() causing failure in PickNodeToScheduleBottomUp() ???
On Thu, Aug 22, 2013 at 4:15 AM, Robert Lytton <robert at xmos.com> wrote:> > > Outstanding issues > ===========> > 1. Is it too aggressive in searching predecessors and successors? > Should the algorithm give up and assume the worst if the depth of > search reaches a predefined limit? > > 2. Should the initial search for 'SetUp1' and 'Destroy1' only search along > chains? viz conditional upon II->isCtrl() >The code is a kludge to work around a particular symptom of a deeper bug in the underlying scheduling algorithm. It's entirely possible that you've found a real bug in it; feel free to check in the fix if you're confident it's right.> 3. Is it possible to input a DAG for testing? >Only by constructing an LLVM IR testcase and feeding it all the way through.> What is the best way to construct the test case? >The above.> Using an IR as input does not guarantee the required DAG will be > output for testing. >Yes, it is quite unfortunate.> > 4. Where should the test be placed? > (How do I test for no-assert?) >Just use an LLVM IR testcase which reproduces the problem before the fix is applied. Dan -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20130822/136fabf7/attachment.html>
Robert Lytton
2013-Aug-23 09:47 UTC
[LLVMdev] PrescheduleNodesWithMultipleUses() causing failure in PickNodeToScheduleBottomUp() ???
Hi Dan, Thank you for the reply. The underlying scheduling algorithm is correct - in this example. The problem is that PrescheduleNodesWithMultipleUses() is incorrectly transforming the schedule when callResource are in play. The callResourceDeadLockDanger() is there to prevent PrescheduleNodesWithMultipleUses() from making the transformation - hence keep the original schedule. Thus, at worst it will prevent a possible shortening of a register's live range - although I believe not. (There is also the additional processing requirment) I will re-post this to llvm-commit for further reviewing. Robert ________________________________ From: Dan Gohman [dan433584 at gmail.com] Sent: 22 August 2013 18:37 To: Robert Lytton Cc: llvmdev at cs.uiuc.edu; Bill Wendling Subject: Re: [LLVMdev] PrescheduleNodesWithMultipleUses() causing failure in PickNodeToScheduleBottomUp() ??? On Thu, Aug 22, 2013 at 4:15 AM, Robert Lytton <robert at xmos.com<mailto:robert at xmos.com>> wrote: Outstanding issues =========== 1. Is it too aggressive in searching predecessors and successors? Should the algorithm give up and assume the worst if the depth of search reaches a predefined limit? 2. Should the initial search for 'SetUp1' and 'Destroy1' only search along chains? viz conditional upon II->isCtrl() The code is a kludge to work around a particular symptom of a deeper bug in the underlying scheduling algorithm. It's entirely possible that you've found a real bug in it; feel free to check in the fix if you're confident it's right. 3. Is it possible to input a DAG for testing? Only by constructing an LLVM IR testcase and feeding it all the way through. What is the best way to construct the test case? The above. Using an IR as input does not guarantee the required DAG will be output for testing. Yes, it is quite unfortunate. 4. Where should the test be placed? (How do I test for no-assert?) Just use an LLVM IR testcase which reproduces the problem before the fix is applied. Dan -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20130823/d149fe15/attachment.html>
Reasonably Related Threads
- [LLVMdev] PrescheduleNodesWithMultipleUses() causing failure in PickNodeToScheduleBottomUp() ???
- [LLVMdev] PrescheduleNodesWithMultipleUses() causing failure in PickNodeToScheduleBottomUp() ???
- [LLVMdev] PrescheduleNodesWithMultipleUses() causing failure in PickNodeToScheduleBottomUp() ???
- [LLVMdev] PrescheduleNodesWithMultipleUses() causing failure in PickNodeToScheduleBottomUp() ???
- [LLVMdev] PrescheduleNodesWithMultipleUses() causing failure in PickNodeToScheduleBottomUp() ???