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

[Robert Lytton]

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>