<div dir="ltr"><div>iI still don't fully understand the issue, but it seems like you're doing multiple merges in a pass and the order of visitation is key.</div><div><br></div><div>Ideally, there's possible a way to write the rewrites such that they are confluent but it sounds like it's not the case. At least it seems like the output is mostly linear and you could be okay by forcing the order consideration carefully (add nodes to worklist in reverse-usage order and explicitly remove the nodes so the WorklistMap doesn't reorder things when it run into a CSEd node)</div><div><br></div><div>I'd need to see the interaction with multiple patterns to say more. </div><div><br></div><div>HTH, </div><div><br></div><div>-Nirav</div><div></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Mon, May 22, 2017 at 3:41 PM, Amaury SECHET <span dir="ltr"><<a href="mailto:deadalnix@gmail.com" target="_blank">deadalnix@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div>You can see an instance of that problem in <a href="https://reviews.llvm.org/D32756" target="_blank">https://reviews.llvm.org/<wbr>D32756</a><br><br></div>Depending on which order the combiner pass on the nodes, the optimization kicks in or not. I have other diamond pattern that I want to add and they all suffer in the same way.<br></div><div class="HOEnZb"><div class="h5"><div class="gmail_extra"><br><div class="gmail_quote">2017-05-22 12:19 GMT-07:00 Nirav Davé <span dir="ltr"><<a href="mailto:niravd@google.com" target="_blank">niravd@google.com</a>></span>:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">I suspect the most direct resolution here is to see the problem directly. Can you post a patch?<span class="m_-7110792769735494805HOEnZb"><font color="#888888"><div><br></div><div>-Nirav</div></font></span></div><div class="m_-7110792769735494805HOEnZb"><div class="m_-7110792769735494805h5"><div class="gmail_extra"><br><div class="gmail_quote">On Mon, May 22, 2017 at 3:01 PM, Amaury SECHET <span dir="ltr"><<a href="mailto:deadalnix@gmail.com" target="_blank">deadalnix@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Explicitly re-adding a node to be processed doesn't work, because the processing order is canonical.<br></div><div class="m_-7110792769735494805m_8034959720973468274HOEnZb"><div class="m_-7110792769735494805m_8034959720973468274h5"><div class="gmail_extra"><br><div class="gmail_quote">2017-05-22 11:39 GMT-07:00 Nirav Davé <span dir="ltr"><<a href="mailto:niravd@google.com" target="_blank">niravd@google.com</a>></span>:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div>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. </div><span class="m_-7110792769735494805m_8034959720973468274m_5726172412694635288HOEnZb"><font color="#888888"><div><br></div><div>-Nirav</div><div><br></div></font></span></div><div class="m_-7110792769735494805m_8034959720973468274m_5726172412694635288HOEnZb"><div class="m_-7110792769735494805m_8034959720973468274m_5726172412694635288h5"><div class="gmail_extra"><br><div class="gmail_quote">On Mon, May 22, 2017 at 2:07 PM, Amaury SECHET <span dir="ltr"><<a href="mailto:deadalnix@gmail.com" target="_blank">deadalnix@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div>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.<br><br></div><div>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.<br></div></div><div class="m_-7110792769735494805m_8034959720973468274m_5726172412694635288m_8942244940396829307HOEnZb"><div class="m_-7110792769735494805m_8034959720973468274m_5726172412694635288m_8942244940396829307h5"><div class="gmail_extra"><br><div class="gmail_quote">2017-05-22 7:30 GMT-07:00 Nirav Davé <span dir="ltr"><<a href="mailto:niravd@google.com" target="_blank">niravd@google.com</a>></span>:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div>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. <br></div><div><br></div><div>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. <br></div><div><br></div><div>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.</div><div><br></div><div>HTH,</div><div><br></div><div>-Nirav</div><div><br></div><div></div></div><div class="gmail_extra"><br><div class="gmail_quote"><div><div class="m_-7110792769735494805m_8034959720973468274m_5726172412694635288m_8942244940396829307m_-7887468062375878803h5">On Mon, May 22, 2017 at 2:21 AM, Amaury SECHET via llvm-dev <span dir="ltr"><<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>></span> wrote:<br></div></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div><div class="m_-7110792769735494805m_8034959720973468274m_5726172412694635288m_8942244940396829307m_-7887468062375878803h5"><div dir="ltr"><div><div><div><div><div><span style="font-family:monospace,monospace">I'm trying to optimize a pattern that goes roughly as:<br></span></div><span style="font-family:monospace,monospace"> A<br> / \<br></span></div><span style="font-family:monospace,monospace"> B C<br> \ /<br></span></div><span style="font-family:monospace,monospace"> D<br><br></span></div><span style="font-family:monospace,monospace">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.<br><br></span></div><span style="font-family:monospace,monospace">Is there a proper way to make this work ?<br></span></div>
<br></div></div>______________________________<wbr>_________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a><br>
<a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/<wbr>mailman/listinfo/llvm-dev</a><br>
<br></blockquote></div><br></div>
</blockquote></div><br></div>
</div></div></blockquote></div><br></div>
</div></div></blockquote></div><br></div>
</div></div></blockquote></div><br></div>
</div></div></blockquote></div><br></div>
</div></div></blockquote></div><br></div>