[llvm-dev] Single use rule for chained node in pattern matcher

Thu Oct 22 13:36:50 PDT 2020

Many thanks Krzysztof,

Your explanation is very clear and convincing. I'll think of something else as you suggested.

Best regards,

Thomas
________________________________
From: llvm-dev <llvm-dev-bounces at lists.llvm.org> on behalf of Krzysztof Parzyszek via llvm-dev <llvm-dev at lists.llvm.org>
Sent: 20 October 2020 16:54
To: llvm-dev at lists.llvm.org <llvm-dev at lists.llvm.org>
Subject: Re: [llvm-dev] Single use rule for chained node in pattern matcher

One problem with this approach is that it’s difficult to actually formulate the proper condition under which such a match would be legal and desirable.  Consider this scenario: C is a node with a chain, and let U be the user with multiple uses of it.  What you’re proposing would work for U(C, C) alone, but would fail if there was another user V(C, C).  As a matter of fact, if would work at first when you only have U, but would fail for both once you add V.

My bigger concern is that even if such a satisfactory condition was created, it would potentially add a lot of complexity to the matcher (and the matcher generator).  Right now the matcher is kind of like a state machine---it tries to match one node at a time, and it’s not really aware of what source pattern it came from.  The matcher starts as a machine trying to match a sub-DAG rooted at a given node against all existing patterns: if the target defines 5000 patterns, the matcher will be ready to try all of them every time.  For example, if you have a pattern (add x, (sub y, z)), first it will check the root: “is it add?”, and then move on to different things depending on whether it matched or not.  If it did match, it’ll go and check the operand against “sub y, z”, otherwise it will go check the root of the next pattern, and so on.  The sub-DAG at this point it _everything_ under the root node, but a match may only cover a part of it (creating more roots for further matching).

Personally, I would be very hesitant to make such a change to the matcher/generator, and I’d try to solve this problem in a different way.  If you think it’s still a good idea, go for it, but please be aware that there may be undesirable consequences that are far from obvious initially, but will need to be addressed.

--

Krzysztof Parzyszek  kparzysz at quicinc.com<mailto:kparzysz at quicinc.com>   AI tools development

From: Thomas Preud'homme <thomasp at graphcore.ai>
Sent: Tuesday, October 20, 2020 5:09 AM
To: llvm-dev at lists.llvm.org; Krzysztof Parzyszek <kparzysz at quicinc.com>
Subject: [EXT] Re: [llvm-dev] Single use rule for chained node in pattern matcher

Hi Krzysztof,

Thanks for the explanation. How about adding the requirement that not only all those uses are by the same node but also that the node is within the sub-DAG being matched?

Best regards,

Thomas

________________________________

From: llvm-dev <llvm-dev-bounces at lists.llvm.org<mailto:llvm-dev-bounces at lists.llvm.org>> on behalf of Krzysztof Parzyszek via llvm-dev <llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>>
Sent: 19 October 2020 16:53
To: llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org> <llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>>
Subject: Re: [llvm-dev] Single use rule for chained node in pattern matcher

Single-use is an easy condition to check, easier than analyzing the consequences of folding a sub-DAG on a case by case basis.

In general, chain edges can appear. Consider this case (with arrows being chains):

A --> C
 \   /
   B

The chains are A->C, B->C, assume B has multiple uses, but A and C are single-use.  If ABC gets matched to T, B must remain due to the extra uses, and we end up with T having a cyclic chain edges with B.

--
Krzysztof Parzyszek  mailto:kparzysz at quicinc.com   AI tools development

From: llvm-dev <llvm-dev-bounces at lists.llvm.org<mailto:llvm-dev-bounces at lists.llvm.org>> On Behalf Of Thomas Preud'homme via llvm-dev
Sent: Monday, October 19, 2020 4:40 AM
To: llvm-dev <llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>>
Cc: Chris Lattner <clattner at llvm.org<mailto:clattner at llvm.org>>
Subject: [EXT] [llvm-dev] Single use rule for chained node in pattern matcher

Hi,

I'm trying to write a pattern for a truncating strict*floating-point instruction that broadcast the result in the resulting register. However the pattern is not recognized by the pattern matcher because the any_fpround node is used more than once due to the broadcasting. I'm not quite sure I understand the reason behind that single use rule [1] (introduced by commit [2]) but all the uses are within the same pattern, as arguments of the same node even. Is there a way to relax the single use rule to allow uses in the same node? If not, how would you suggest I go about implementing pattern matching for this instruction?

[1] https://reviews.llvm.org/source/llvm-github/browse/master/llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp$3214-3228
[2] https://reviews.llvm.org/rGf8695c1ee9bb8b18a4e1991591fa92383d427435

Thanks in advance for your help. Best regards,

Thomas
_______________________________________________
LLVM Developers mailing list
llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

** We have updated our privacy policy, which contains important information about how we collect and process your personal data. To read the policy, please click here<http://www.graphcore.ai/privacy> **

This email and its attachments are intended solely for the addressed recipients and may contain confidential or legally privileged information.
If you are not the intended recipient you must not copy, distribute or disseminate this email in any way; to do so may be unlawful.

Any personal data/special category personal data herein are processed in accordance with UK data protection legislation.
All associated feasible security measures are in place. Further details are available from the Privacy Notice on the website and/or from the Company.

Graphcore Limited (registered in England and Wales with registration number 10185006) is registered at 107 Cheapside, London, UK, EC2V 6DN.
This message was scanned for viruses upon transmission. However Graphcore accepts no liability for any such transmission.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20201022/8a962516/attachment.html>