[llvm-dev] [GlobalISel] Prioritizing long patterns in combiner over short ones
Dominik Montada via llvm-dev
llvm-dev at lists.llvm.org
Thu Jan 21 23:27:55 PST 2021
Hi Jay,
thanks for this clarification and sorry for the confusion I seem to have
caused! I was solely thinking in terms of IR instead of the pattern.
Also thanks for linking that DAGCombiner discussion as well. I'll update
my pattern to handle my use-case. In the future I might even add a 2nd
post-combiner-combiner to our backend, should it turn out to be beneficial.
Cheers,
Dominik
Am 21.01.21 um 18:02 schrieb Jay Foad:
> I think the terminology is confusing. By "bottom up" I mean visiting
> the leaves of an expression tree first like in BURS
> (https://en.wikipedia.org/wiki/BURS). This is "bottom up" if you draw
> your trees with the root at the top. For the expression (fadd (fmul a,
> b), c) it would visit the mul before the add. I think simplifying
> things in this order is sane because when you visit a node, you can
> assume that the operands of that node have already been simplified.
>
> In my defence I think I got this definition from earlier discussions
> about the order in which DAGCombiner runs:
> https://reviews.llvm.org/D33587#1372912
>
> Unfortunately if you think of textual IR in a basic block, then
> "bottom up" order starts at the top of the block and proceeds towards
> the bottom :-(
> %mul = fmul float %a, %b
> %add = fadd float %mul, %c
>
> A quick experiment shows that InstCombine is bottom-up:
> $ cat z.ll
> define float @main(float %a, float %b, float %c, float %d, float %e) {
> %add = fadd float %a, %b
> %sub = fsub float %add, %c
> %mul = fmul float %sub, %d
> %div = fdiv float %mul, %e
> ret float %div
> }
> $ opt -instcombine -debug-only=instcombine z.ll
> IC: Visiting: %add = fadd float %a, %b
> IC: Visiting: %sub = fsub float %add, %c
> IC: Visiting: %mul = fmul float %sub, %d
> IC: Visiting: %div = fdiv float %mul, %e
>
> DAGCombiner is top-down, which I think is wrong but it's hard to fix:
> $ llc -march=aarch64 -debug-only=dagcombine z.ll
> Combining: t14: f32 = fdiv t13, t10
> Combining: t13: f32 = fmul t12, t8
> Combining: t12: f32 = fsub t11, t6
> Combining: t11: f32 = fadd t2, t4
>
> I'm happy to see that GISel Combiner is bottom-up after all:
> $ llc -march=aarch64 -global-isel -debug-only=gi-combiner z.ll
> Try combining %5:_(s32) = G_FADD %0:_, %1:_
> Try combining %6:_(s32) = G_FSUB %5:_, %2:_
> Try combining %7:_(s32) = G_FMUL %6:_, %3:_
> Try combining %8:_(s32) = G_FDIV %7:_, %4:_
>
>
> Sorry if I have derailed your original questions Dominik. I think the
> answers are "yes you have to teach your larger pattern to handle this
> case" and "no there are no plans to improve this behaviour as far as I
> know, and I'm not even sure how it would be improved".
>
> Jay.
>
>
>
>
>
> Jay.
>
> On Wed, 20 Jan 2021 at 18:50, Daniel Sanders <daniel_l_sanders at apple.com> wrote:
>> To be honest, hearing it was top-down surprised me too at first but I think I was remembering the algorithm I wanted to experiment with which required bottom-up.
>>
>> I asked Aditya about this and apparently it's to address the pathological case where we repeatedly do an entire pass only to simplify a single node of the MIR and slowly propagate that through the MIR. Another reason was because InstCombine is like this too.
>>
>> I think we can probably address a fair portion of the pathological case by controlling how we populate the work list. Instead of adding all MI's to it each time, we could filter out blocks that can't possibly match on this round. I'm thinking that a block only needs revisiting on the next pass if it contains a use of a register that was def'd by an instruction we changed on the current pass. Therefore the observer could track the vreg defs affected by a pass and build a list of MBB's to revisit. I think we'd have to revisit all the successors of those blocks too if the pass is running top-down (in case we make changes that allow further changes in the same pass) but if we changed it to bottom-up we wouldn't need that. This wouldn't help with large blocks but maybe we can find a similar scheme there.
>>
>>> On Jan 19, 2021, at 22:51, Amara Emerson <amara at apple.com> wrote:
>>>
>>> +Daniel.
>>>
>>> Daniel, do you remember if there was a strong reason for choosing to go top-down on the combiner?
>>>
>>> Amara
>>>
>>>> On Dec 17, 2020, at 2:14 AM, Jay Foad via llvm-dev <llvm-dev at lists.llvm.org> wrote:
>>>>
>>>> I am really surprised that "the combiner runs top-down". Surely it's
>>>> better to combine smaller sub-expressions before combining larger
>>>> expressions? Or is there actually a good reason to keep the top-down
>>>> order??
>>>>
>>>> DAGCombiner also runs mostly top-down (but it can also add nodes to
>>>> the worklist in a bottom-up direction for certain cases). The top-down
>>>> order causes problems when you have deep expressions trees that could
>>>> be simplified away to nothing. Outer combines see these subexpression
>>>> unsimplified. They can use recursive helper functions like
>>>> computeKnownBits to try to analyse the unsimplified expression, but
>>>> the recursive helper functions typically have a max recursion depth of
>>>> 6. which is easy to hit.
>>>>
>>>> DAGCombiner is so embedded now that it is hard to change the basic
>>>> top-down order, but I would hope we could change the GlobalISel
>>>> combiner.
>>>>
>>>> Jay.
>>>>
>>>> On Tue, 15 Dec 2020 at 15:09, Dominik Montada via llvm-dev
>>>> <llvm-dev at lists.llvm.org> wrote:
>>>>> Hi,
>>>>>
>>>>> I'm currently writing target specific combiners with GlobalISel. I have
>>>>> a case where a sub-node of a larger pattern also matches another,
>>>>> smaller combiner pattern. Because the combiner runs top-down, the
>>>>> smaller pattern is matched before the larger pattern has a chance to be
>>>>> matched. Do I have to teach my larger pattern to handle this case or is
>>>>> there a better way to do this?
>>>>>
>>>>> More importantly, are there any plans to improve this behavior?
>>>>>
>>>>> Cheers,
>>>>>
>>>>> Dominik
>>>>>
>>>>> --
>>>>> ----------------------------------------------------------------------
>>>>> Dominik Montada Email: dominik.montada at hightec-rt.com
>>>>> HighTec EDV-Systeme GmbH Phone: +49 681 92613 19
>>>>> Europaallee 19 Fax: +49-681-92613-26
>>>>> D-66113 Saarbrücken WWW: http://www.hightec-rt.com
>>>>>
>>>>> Managing Director: Vera Strothmann
>>>>> Register Court: Saarbrücken, HRB 10445, VAT ID: DE 138344222
>>>>>
>>>>> This e-mail may contain confidential and/or privileged information. If
>>>>> you are not the intended recipient please notify the sender immediately
>>>>> and destroy this e-mail. Any unauthorised copying, disclosure or
>>>>> distribution of the material in this e-mail is strictly forbidden.
>>>>> ---
>>>>>
>>>>> _______________________________________________
>>>>> LLVM Developers mailing list
>>>>> llvm-dev at lists.llvm.org
>>>>> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>>> _______________________________________________
>>>> LLVM Developers mailing list
>>>> llvm-dev at lists.llvm.org
>>>> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
--
----------------------------------------------------------------------
Dominik Montada Email: dominik.montada at hightec-rt.com
HighTec EDV-Systeme GmbH Phone: +49 681 92613 19
Europaallee 19 Fax: +49-681-92613-26
D-66113 Saarbrücken WWW: http://www.hightec-rt.com
Managing Director: Vera Strothmann
Register Court: Saarbrücken, HRB 10445, VAT ID: DE 138344222
This e-mail may contain confidential and/or privileged information. If
you are not the intended recipient please notify the sender immediately
and destroy this e-mail. Any unauthorised copying, disclosure or
distribution of the material in this e-mail is strictly forbidden.
---
-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/x-pkcs7-signature
Size: 6822 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20210122/4a8b44d6/attachment.bin>
More information about the llvm-dev
mailing list