Robert Lytton
2013-Aug-21 17:34 UTC
[LLVMdev] PrescheduleNodesWithMultipleUses() causing failure in PickNodeToScheduleBottomUp() ???
Hi, I have reasoned through and believe the problem is with the PrescheduleNodesWithMultipleUses. Take the following DAG (arrow to predecessor): Destroy Destroy ^ ^ | | | | SetUp----->PredSU <-----SU ^ ^ ^ | | | | | | ----------- | --------- | | | Setup ^ | When there are two successors of PredSU with type getCallFrameDestroyOpcode and there is order between them, if the successor of the two's matching getCallFrameSetupOpcode is a predecessor of SU, if the dependency is routed through SU, there will be a dead lock. Viz: Destroy PredSU Destroy ^ ^ ^ | | | | | | SetUp-------> SU -------- ^ ^ ^ | | | | | | ----------- | | | | | Setup ^ | I have attached a patch that adds a check for this situation in PrescheduleNodesWithMultipleUses. Comments please! Robert ________________________________ From: llvmdev-bounces at cs.uiuc.edu [llvmdev-bounces at cs.uiuc.edu] on behalf of Robert Lytton [robert at xmos.com] Sent: 21 August 2013 11:02 To: llvmdev at cs.uiuc.edu Subject: Re: [LLVMdev] PrescheduleNodesWithMultipleUses() causing failure in PickNodeToScheduleBottomUp() ??? Here is a bit more data. After PrescheduleNodesWithMultipleUses has been run, the following Predecessor/Successor links are 'dumpAll'ed. (I attach the full dumpAll before & after "Prescheduling SU #7 next to PredSU #4 to guide scheduling in the presence of multiple uses") SU(3) Predecessors: val SU(5): Latency=1 ch SU(7): Latency=1 val SU(7): Latency=1 SU(7): ch SU(3): Latency=1 val SU(3): Latency=1 val SU(5): Latency=1 It looks odd but seems to be fine as all nodes are capable of being scheduled viz: NumSuccsLeft after each schedule sched - 0 2 1 3 5 7 6 8 4 SU(0) 0 SU(1) 1 0 SU(2) 1 0 SU(3) 3 2 1 0 SU(4) 1 0 SU(5) 1 0 SU(6) 1 0 SU(7) 3 1 0 SU(8) 1 0 So, the problem comes back to trying to find the physical address of a 'CallResource' in the later part of PickNodeToScheduleBottomUp(). Robert ________________________________ From: llvmdev-bounces at cs.uiuc.edu [llvmdev-bounces at cs.uiuc.edu] on behalf of Robert Lytton [robert at xmos.com] Sent: 20 August 2013 22:57 To: llvmdev at cs.uiuc.edu Subject: [LLVMdev] PrescheduleNodesWithMultipleUses() causing failure in PickNodeToScheduleBottomUp() ??? Hi, I have an assert firing due to PickNodeToScheduleBottomUp(): 1. having a CallResource in use pushing an interference of current SUnit. 2. having no more SUnits in the AvailableQueue 3. The only interference being the SUnit that just failed due to a Call Resource. 4. An attempt to duplicate this node which has the 'Call Resource' as a physical register. Thus the call to getMinimalPhysRegClass() asserts - Call Resource is not in a class! ..../lib/CodeGen/TargetRegisterInfo.cpp:120: const llvm::TargetRegisterClass* llvm::TargetRegisterInfo::getMinimalPhysRegClass(unsigned int, llvm::EVT) const: Assertion `BestRC && "Couldn't find the register class"' failed. The interesting thing about this failure is that the Predecessor/Successor of two nodes was changed by PrescheduleNodesWithMultipleUses(). If they were not, the AvailableQueue would have had nodes, and all would have been fine. I am quite uneasy over how PrescheduleNodesWithMultipleUses() has changed the Predecessor/Successor. It seems to have changed the DAG into something impossible to schedule - I need to look more carefully to confirm this. I'm not sure if this is one problem or two - or a target problem passing something dangerous to the scheduler. Any help would be most welcome. I have attached the code to exercise the bug - the slightest of perturbation will make it compile fine e.g. add an extra 'undef' argument to f2 viz: double @f2(i32, double, double, double). This example only fails for xcore targets. Robert -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20130821/cb019ffb/attachment.html> -------------- next part -------------- A non-text attachment was scrubbed... Name: PatchCallResourceDeadLock Type: application/octet-stream Size: 5359 bytes Desc: PatchCallResourceDeadLock URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20130821/cb019ffb/attachment.obj>
Robert Lytton
2013-Aug-22 07:39 UTC
[LLVMdev] PrescheduleNodesWithMultipleUses() causing failure in PickNodeToScheduleBottomUp() ???
sorry, Just noticed that the diagrams have 'Destroy' & 'SetUp' the wrong way around! Robert ________________________________ From: llvmdev-bounces at cs.uiuc.edu [llvmdev-bounces at cs.uiuc.edu] on behalf of Robert Lytton [robert at xmos.com] Sent: 21 August 2013 18:34 To: llvmdev at cs.uiuc.edu Subject: Re: [LLVMdev] PrescheduleNodesWithMultipleUses() causing failure in PickNodeToScheduleBottomUp() ??? Hi, I have reasoned through and believe the problem is with the PrescheduleNodesWithMultipleUses. Take the following DAG (arrow to predecessor): Destroy Destroy ^ ^ | | | | SetUp----->PredSU <-----SU ^ ^ ^ | | | | | | ----------- | --------- | | | Setup ^ | When there are two successors of PredSU with type getCallFrameDestroyOpcode and there is order between them, if the successor of the two's matching getCallFrameSetupOpcode is a predecessor of SU, if the dependency is routed through SU, there will be a dead lock. Viz: Destroy PredSU Destroy ^ ^ ^ | | | | | | SetUp-------> SU -------- ^ ^ ^ | | | | | | ----------- | | | | | Setup ^ | I have attached a patch that adds a check for this situation in PrescheduleNodesWithMultipleUses. Comments please! Robert ________________________________ From: llvmdev-bounces at cs.uiuc.edu [llvmdev-bounces at cs.uiuc.edu] on behalf of Robert Lytton [robert at xmos.com] Sent: 21 August 2013 11:02 To: llvmdev at cs.uiuc.edu Subject: Re: [LLVMdev] PrescheduleNodesWithMultipleUses() causing failure in PickNodeToScheduleBottomUp() ??? Here is a bit more data. After PrescheduleNodesWithMultipleUses has been run, the following Predecessor/Successor links are 'dumpAll'ed. (I attach the full dumpAll before & after "Prescheduling SU #7 next to PredSU #4 to guide scheduling in the presence of multiple uses") SU(3) Predecessors: val SU(5): Latency=1 ch SU(7): Latency=1 val SU(7): Latency=1 SU(7): ch SU(3): Latency=1 val SU(3): Latency=1 val SU(5): Latency=1 It looks odd but seems to be fine as all nodes are capable of being scheduled viz: NumSuccsLeft after each schedule sched - 0 2 1 3 5 7 6 8 4 SU(0) 0 SU(1) 1 0 SU(2) 1 0 SU(3) 3 2 1 0 SU(4) 1 0 SU(5) 1 0 SU(6) 1 0 SU(7) 3 1 0 SU(8) 1 0 So, the problem comes back to trying to find the physical address of a 'CallResource' in the later part of PickNodeToScheduleBottomUp(). Robert ________________________________ From: llvmdev-bounces at cs.uiuc.edu [llvmdev-bounces at cs.uiuc.edu] on behalf of Robert Lytton [robert at xmos.com] Sent: 20 August 2013 22:57 To: llvmdev at cs.uiuc.edu Subject: [LLVMdev] PrescheduleNodesWithMultipleUses() causing failure in PickNodeToScheduleBottomUp() ??? Hi, I have an assert firing due to PickNodeToScheduleBottomUp(): 1. having a CallResource in use pushing an interference of current SUnit. 2. having no more SUnits in the AvailableQueue 3. The only interference being the SUnit that just failed due to a Call Resource. 4. An attempt to duplicate this node which has the 'Call Resource' as a physical register. Thus the call to getMinimalPhysRegClass() asserts - Call Resource is not in a class! ..../lib/CodeGen/TargetRegisterInfo.cpp:120: const llvm::TargetRegisterClass* llvm::TargetRegisterInfo::getMinimalPhysRegClass(unsigned int, llvm::EVT) const: Assertion `BestRC && "Couldn't find the register class"' failed. The interesting thing about this failure is that the Predecessor/Successor of two nodes was changed by PrescheduleNodesWithMultipleUses(). If they were not, the AvailableQueue would have had nodes, and all would have been fine. I am quite uneasy over how PrescheduleNodesWithMultipleUses() has changed the Predecessor/Successor. It seems to have changed the DAG into something impossible to schedule - I need to look more carefully to confirm this. I'm not sure if this is one problem or two - or a target problem passing something dangerous to the scheduler. Any help would be most welcome. I have attached the code to exercise the bug - the slightest of perturbation will make it compile fine e.g. add an extra 'undef' argument to f2 viz: double @f2(i32, double, double, double). This example only fails for xcore targets. Robert -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20130822/fd98033a/attachment.html>
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>
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() ???