llvm dev - May 2017 - Optimizing diamond pattern in DAGCombine

Explicitly re-adding a node to be processed doesn't work, because the
processing order is canonical.

2017-05-22 11:39 GMT-07:00 Nirav Davé <niravd at google.com>:
> You can always explicitly add D to the worklist when you make the
> transformation with AddToWorklist. Presuambly this was the cause for your
> infinite loop.
>
> -Nirav
>
>
> On Mon, May 22, 2017 at 2:07 PM, Amaury SECHET <deadalnix at
gmail.com>
> wrote:
>
>> The root problem is that, when A gets modified, D doesn't get added
back
>> to the worklist. I could match the pattern on A, but the problem
remains:
>> when D gets modified, A do not get added back tot he worklist.
>>
>> I also considered ding several round of DAGCombine, but it is very easy
>> to run into infinite loops, even with a fair amount of sanity checks.
>>
>> 2017-05-22 7:30 GMT-07:00 Nirav Davé <niravd at google.com>:
>>
>>> This is a little hard to diagnose in the abstract, but it sounds
like
>>> you're having a loop along the lines of visit A -> visit B/C
-> visit D ->
>>> visit A and that at each step you're making a real reasonable
change to the
>>> DAG and returning to the original DAG.
>>>
>>> One possible solution is to to rework the optimization to occur
when
>>> visiting A not D. so the last edge in the visit loop no longer
happens.
>>>
>>> If that's not feasible, I don't think there's much you
can do that is
>>> not effectively preventing one of those transitions from occurring
when it
>>> would cause the infinite visit loop.
>>>
>>> HTH,
>>>
>>> -Nirav
>>>
>>>
>>> On Mon, May 22, 2017 at 2:21 AM, Amaury SECHET via llvm-dev <
>>> llvm-dev at lists.llvm.org> wrote:
>>>
>>>> I'm trying to optimize a pattern that goes roughly as:
>>>>     A
>>>>    / \
>>>>   B   C
>>>>    \ /
>>>>     D
>>>>
>>>> Problem is, when A gets modified, B and C get added back to the
>>>> worklist, but D doesn't. Readding D to the worklist just
create an infinite
>>>> loop where one process D again and again.
>>>>
>>>> Is there a proper way to make this work ?
>>>>
>>>> _______________________________________________
>>>> LLVM Developers mailing list
>>>> llvm-dev at lists.llvm.org
>>>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>>>
>>>>
>>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170522/1a59cc19/attachment.html>

I suspect the most direct resolution here is to see the problem directly.
Can you post a patch?

-Nirav

On Mon, May 22, 2017 at 3:01 PM, Amaury SECHET <deadalnix at gmail.com>
wrote:
> Explicitly re-adding a node to be processed doesn't work, because the
> processing order is canonical.
>
> 2017-05-22 11:39 GMT-07:00 Nirav Davé <niravd at google.com>:
>
>> You can always explicitly add D to the worklist when you make the
>> transformation with AddToWorklist. Presuambly this was the cause for
your
>> infinite loop.
>>
>> -Nirav
>>
>>
>> On Mon, May 22, 2017 at 2:07 PM, Amaury SECHET <deadalnix at
gmail.com>
>> wrote:
>>
>>> The root problem is that, when A gets modified, D doesn't get
added back
>>> to the worklist. I could match the pattern on A, but the problem
remains:
>>> when D gets modified, A do not get added back tot he worklist.
>>>
>>> I also considered ding several round of DAGCombine, but it is very
easy
>>> to run into infinite loops, even with a fair amount of sanity
checks.
>>>
>>> 2017-05-22 7:30 GMT-07:00 Nirav Davé <niravd at google.com>:
>>>
>>>> This is a little hard to diagnose in the abstract, but it
sounds like
>>>> you're having a loop along the lines of visit A -> visit
B/C -> visit D ->
>>>> visit A and that at each step you're making a real
reasonable change to the
>>>> DAG and returning to the original DAG.
>>>>
>>>> One possible solution is to to rework the optimization to occur
when
>>>> visiting A not D. so the last edge in the visit loop no longer
happens.
>>>>
>>>> If that's not feasible, I don't think there's much
you can do that is
>>>> not effectively preventing one of those transitions from
occurring when it
>>>> would cause the infinite visit loop.
>>>>
>>>> HTH,
>>>>
>>>> -Nirav
>>>>
>>>>
>>>> On Mon, May 22, 2017 at 2:21 AM, Amaury SECHET via llvm-dev
<
>>>> llvm-dev at lists.llvm.org> wrote:
>>>>
>>>>> I'm trying to optimize a pattern that goes roughly as:
>>>>>     A
>>>>>    / \
>>>>>   B   C
>>>>>    \ /
>>>>>     D
>>>>>
>>>>> Problem is, when A gets modified, B and C get added back to
the
>>>>> worklist, but D doesn't. Readding D to the worklist
just create an infinite
>>>>> loop where one process D again and again.
>>>>>
>>>>> Is there a proper way to make this work ?
>>>>>
>>>>> _______________________________________________
>>>>> LLVM Developers mailing list
>>>>> llvm-dev at lists.llvm.org
>>>>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>>>>
>>>>>
>>>>
>>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170522/59157970/attachment.html>

You can see an instance of that problem in https://reviews.llvm.org/D32756

Depending on which order the combiner pass on the nodes, the optimization
kicks in or not. I have other diamond pattern that I want to add and they
all suffer in the same way.

2017-05-22 12:19 GMT-07:00 Nirav Davé <niravd at google.com>:
> I suspect the most direct resolution here is to see the problem directly.
> Can you post a patch?
>
> -Nirav
>
> On Mon, May 22, 2017 at 3:01 PM, Amaury SECHET <deadalnix at
gmail.com>
> wrote:
>
>> Explicitly re-adding a node to be processed doesn't work, because
the
>> processing order is canonical.
>>
>> 2017-05-22 11:39 GMT-07:00 Nirav Davé <niravd at google.com>:
>>
>>> You can always explicitly add D to the worklist when you make the
>>> transformation with AddToWorklist. Presuambly this was the cause
for your
>>> infinite loop.
>>>
>>> -Nirav
>>>
>>>
>>> On Mon, May 22, 2017 at 2:07 PM, Amaury SECHET <deadalnix at
gmail.com>
>>> wrote:
>>>
>>>> The root problem is that, when A gets modified, D doesn't
get added
>>>> back to the worklist. I could match the pattern on A, but the
problem
>>>> remains: when D gets modified, A do not get added back tot he
worklist.
>>>>
>>>> I also considered ding several round of DAGCombine, but it is
very easy
>>>> to run into infinite loops, even with a fair amount of sanity
checks.
>>>>
>>>> 2017-05-22 7:30 GMT-07:00 Nirav Davé <niravd at
google.com>:
>>>>
>>>>> This is a little hard to diagnose in the abstract, but it
sounds like
>>>>> you're having a loop along the lines of visit A ->
visit B/C -> visit D ->
>>>>> visit A and that at each step you're making a real
reasonable change to the
>>>>> DAG and returning to the original DAG.
>>>>>
>>>>> One possible solution is to to rework the optimization to
occur when
>>>>> visiting A not D. so the last edge in the visit loop no
longer happens.
>>>>>
>>>>> If that's not feasible, I don't think there's
much you can do that is
>>>>> not effectively preventing one of those transitions from
occurring when it
>>>>> would cause the infinite visit loop.
>>>>>
>>>>> HTH,
>>>>>
>>>>> -Nirav
>>>>>
>>>>>
>>>>> On Mon, May 22, 2017 at 2:21 AM, Amaury SECHET via llvm-dev
<
>>>>> llvm-dev at lists.llvm.org> wrote:
>>>>>
>>>>>> I'm trying to optimize a pattern that goes roughly
as:
>>>>>>     A
>>>>>>    / \
>>>>>>   B   C
>>>>>>    \ /
>>>>>>     D
>>>>>>
>>>>>> Problem is, when A gets modified, B and C get added
back to the
>>>>>> worklist, but D doesn't. Readding D to the worklist
just create an infinite
>>>>>> loop where one process D again and again.
>>>>>>
>>>>>> Is there a proper way to make this work ?
>>>>>>
>>>>>> _______________________________________________
>>>>>> LLVM Developers mailing list
>>>>>> llvm-dev at lists.llvm.org
>>>>>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>>>>>
>>>>>>
>>>>>
>>>>
>>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170522/edf28a11/attachment.html>