llvm dev - May 2017 - Optimizing diamond pattern in DAGCombine

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 ?
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170521/5d9192fd/attachment.html>

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

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>