thr3ads.net - llvm dev - [LLVMdev] PrescheduleNodesWithMultipleUses() causing failure in PickNodeToScheduleBottomUp() ??? [Aug 2013]

If this information is useful, please help other people find it:
Share via:

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

head link

[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

head link

[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>

Apparently Analagous Threads

Search for more apparently analagous threads

llvm dev - Aug 2013 - [LLVMdev] PrescheduleNodesWithMultipleUses() causing failure in PickNodeToScheduleBottomUp() ???

[LLVMdev] PrescheduleNodesWithMultipleUses() causing failure in PickNodeToScheduleBottomUp() ???

[LLVMdev] PrescheduleNodesWithMultipleUses() causing failure in PickNodeToScheduleBottomUp() ???

[LLVMdev] PrescheduleNodesWithMultipleUses() causing failure in PickNodeToScheduleBottomUp() ???

Apparently Analagous Threads