<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<style type="text/css" style="display:none;"> P {margin-top:0;margin-bottom:0;} </style>
</head>
<body dir="ltr">
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
Many thanks Krzysztof,</div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<br>
</div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
Your explanation is very clear and convincing. I'll think of something else as you suggested.</div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<br>
</div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
Best regards,</div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<br>
</div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
Thomas<br>
</div>
<div id="appendonsend"></div>
<hr style="display:inline-block;width:98%" tabindex="-1">
<div id="divRplyFwdMsg" dir="ltr"><font face="Calibri, sans-serif" style="font-size:11pt" color="#000000"><b>From:</b> llvm-dev <llvm-dev-bounces@lists.llvm.org> on behalf of Krzysztof Parzyszek via llvm-dev <llvm-dev@lists.llvm.org><br>
<b>Sent:</b> 20 October 2020 16:54<br>
<b>To:</b> llvm-dev@lists.llvm.org <llvm-dev@lists.llvm.org><br>
<b>Subject:</b> Re: [llvm-dev] Single use rule for chained node in pattern matcher</font>
<div> </div>
</div>
<style>
<!--
@font-face
{font-family:"Cambria Math"}
@font-face
{font-family:Calibri}
@font-face
{font-family:Consolas}
p.x_MsoNormal, li.x_MsoNormal, div.x_MsoNormal
{margin:0in;
font-size:11.0pt;
font-family:"Calibri",sans-serif}
a:link, span.x_MsoHyperlink
{color:blue;
text-decoration:underline}
span.x_vhqudtyelxqknvzkxcjct
{}
span.x_EmailStyle22
{font-family:"Calibri",sans-serif;
color:windowtext}
.x_MsoChpDefault
{font-size:10.0pt}
@page WordSection1
{margin:1.0in 1.0in 1.0in 1.0in}
div.x_WordSection1
{}
-->
</style>
<div lang="EN-US" link="blue" vlink="purple" style="word-wrap:break-word">
<div class="x_WordSection1">
<p class="x_MsoNormal">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.</p>
<p class="x_MsoNormal"> </p>
<p class="x_MsoNormal">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 _<i>everything</i>_ under the root node, but a match may only cover a part of it (creating more roots for further matching).</p>
<p class="x_MsoNormal"> </p>
<p class="x_MsoNormal">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.</p>
<p class="x_MsoNormal"> </p>
<p class="x_MsoNormal"> </p>
<div>
<p class="x_MsoNormal"><span style="font-size:9.0pt; font-family:Consolas">-- </span>
<span style="font-size:9.0pt; font-family:Consolas"></span></p>
<p class="x_MsoNormal"><span style="font-size:8.0pt; font-family:Consolas">Krzysztof Parzyszek
<a href="mailto:kparzysz@quicinc.com"><span style="color:#0563C1">kparzysz@quicinc.com</span></a> AI tools development</span></p>
</div>
<p class="x_MsoNormal"> </p>
<div>
<div style="border:none; border-top:solid #E1E1E1 1.0pt; padding:3.0pt 0in 0in 0in">
<p class="x_MsoNormal"><b>From:</b> Thomas Preud'homme <thomasp@graphcore.ai> <br>
<b>Sent:</b> Tuesday, October 20, 2020 5:09 AM<br>
<b>To:</b> llvm-dev@lists.llvm.org; Krzysztof Parzyszek <kparzysz@quicinc.com><br>
<b>Subject:</b> [EXT] Re: [llvm-dev] Single use rule for chained node in pattern matcher</p>
</div>
</div>
<p class="x_MsoNormal"> </p>
<div>
<p class="x_MsoNormal"><span style="font-size:12.0pt; color:black">Hi <span class="x_vhqudtyelxqknvzkxcjct">
Krzysztof</span>,</span></p>
</div>
<div>
<p class="x_MsoNormal"><span style="font-size:12.0pt; color:black"> </span></p>
</div>
<div>
<p class="x_MsoNormal"><span style="font-size:12.0pt; color:black">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?</span></p>
</div>
<div>
<p class="x_MsoNormal"><span style="font-size:12.0pt; color:black"> </span></p>
</div>
<div>
<p class="x_MsoNormal"><span style="font-size:12.0pt; color:black">Best regards,</span></p>
</div>
<div>
<p class="x_MsoNormal"><span style="font-size:12.0pt; color:black"> </span></p>
</div>
<div>
<p class="x_MsoNormal"><span style="font-size:12.0pt; color:black">Thomas</span></p>
</div>
<div class="x_MsoNormal" align="center" style="text-align:center">
<hr size="2" width="98%" align="center">
</div>
<div id="x_divRplyFwdMsg">
<p class="x_MsoNormal"><b><span style="color:black">From:</span></b><span style="color:black"> llvm-dev <<a href="mailto:llvm-dev-bounces@lists.llvm.org">llvm-dev-bounces@lists.llvm.org</a>> on behalf of Krzysztof Parzyszek via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>><br>
<b>Sent:</b> 19 October 2020 16:53<br>
<b>To:</b> <a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a> <<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>><br>
<b>Subject:</b> Re: [llvm-dev] Single use rule for chained node in pattern matcher</span>
</p>
<div>
<p class="x_MsoNormal"> </p>
</div>
</div>
<div>
<div>
<p class="x_MsoNormal">Single-use is an easy condition to check, easier than analyzing the consequences of folding a sub-DAG on a case by case basis.<br>
<br>
In general, chain edges can appear. Consider this case (with arrows being chains):<br>
<br>
A --> C<br>
\ /<br>
B<br>
<br>
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.<br>
<br>
--<br>
Krzysztof Parzyszek <a href="mailto:kparzysz@quicinc.com">mailto:kparzysz@quicinc.com</a> AI tools development<br>
<br>
From: llvm-dev <<a href="mailto:llvm-dev-bounces@lists.llvm.org">llvm-dev-bounces@lists.llvm.org</a>> On Behalf Of Thomas Preud'homme via llvm-dev<br>
Sent: Monday, October 19, 2020 4:40 AM<br>
To: llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>><br>
Cc: Chris Lattner <<a href="mailto:clattner@llvm.org">clattner@llvm.org</a>><br>
Subject: [EXT] [llvm-dev] Single use rule for chained node in pattern matcher<br>
<br>
Hi,<br>
<br>
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?<br>
<br>
[1] <a href="https://reviews.llvm.org/source/llvm-github/browse/master/llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp$3214-3228">
https://reviews.llvm.org/source/llvm-github/browse/master/llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp$3214-3228</a><br>
[2] <a href="https://reviews.llvm.org/rGf8695c1ee9bb8b18a4e1991591fa92383d427435">
https://reviews.llvm.org/rGf8695c1ee9bb8b18a4e1991591fa92383d427435</a><br>
<br>
Thanks in advance for your help. Best regards,<br>
<br>
Thomas<br>
_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a><br>
<a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev">https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a></p>
</div>
</div>
<p class="x_MsoNormal"><br>
<br>
<span style="font-size:7.5pt">** 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
<a href="http://www.graphcore.ai/privacy">here</a> **<br>
<br>
This email and its attachments are intended solely for the addressed recipients and may contain confidential or legally privileged information.<br>
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.<br>
<br>
Any personal data/special category personal data herein are processed in accordance with UK data protection legislation.<br>
All associated feasible security measures are in place. Further details are available from the Privacy Notice on the website and/or from the Company.<br>
<br>
Graphcore Limited (registered in England and Wales with registration number 10185006) is registered at 107 Cheapside, London, UK, EC2V 6DN.<br>
This message was scanned for viruses upon transmission. However Graphcore accepts no liability for any such transmission.</span></p>
</div>
</div>
</body>
</html>