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

[Robert Lytton]

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>