llvm dev - Aug 2013 - [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>

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>

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>