llvm dev - May 2017 - Optimizing diamond pattern in DAGCombine

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/5adee2e6/attachment.html>

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/fc15deab/attachment.html>

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>