llvm dev - Apr 2020 - [RDF] Performance Issues for rdf::Liveness::computePhiInfo()

Hi Krzysztof,

I have been working to debug some performance issues in
https://reviews.llvm.org/D75936, and I have found that the main issue is
rdf::Liveness::computePhiInfo(). Specifically, a single line introduces 20-30%
overhead for the entire llc X86 pipeline:

https://github.com/llvm/llvm-project/blob/b5be1c5419e2a38eb60fc7e785567b54b6d9e0e0/llvm/lib/CodeGen/RDFLiveness.cpp#L208

Linux perf shows that the culprit is MachineDominatorTree::dominates(), which is
being invoked on nearly every less-than comparison between nodes. The
documentation for dominates() reads "dominates -Returns true iff A
dominates B. Note that this is not a constant time operation!"

Do you think that this could be fixed? Maybe some memorization could help?

Thanks and regards,

Scott Constable
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20200430/bbee9f90/attachment.html>

Hi Scott,
I'm actually fixing a correctness problem in that function and the node
ordering plays a role in it.  I will put more attention to trying to reduce the
complexity there.

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

From: Constable, Scott D <scott.d.constable at intel.com>
Sent: Thursday, April 30, 2020 3:49 PM
To: llvm-dev at lists.llvm.org; Krzysztof Parzyszek <kparzysz at
quicinc.com>
Cc: Matthew Riley <mattdr at google.com>; Topper, Craig <craig.topper
at intel.com>
Subject: [EXT] [RDF] Performance Issues for rdf::Liveness::computePhiInfo()

Hi Krzysztof,

I have been working to debug some performance issues in
https://reviews.llvm.org/D75936, and I have found that the main issue is
rdf::Liveness::computePhiInfo(). Specifically, a single line introduces 20-30%
overhead for the entire llc X86 pipeline:

https://github.com/llvm/llvm-project/blob/b5be1c5419e2a38eb60fc7e785567b54b6d9e0e0/llvm/lib/CodeGen/RDFLiveness.cpp#L208

Linux perf shows that the culprit is MachineDominatorTree::dominates(), which is
being invoked on nearly every less-than comparison between nodes. The
documentation for dominates() reads "dominates -Returns true iff A
dominates B. Note that this is not a constant time operation!"

Do you think that this could be fixed? Maybe some memorization could help?

Thanks and regards,

Scott Constable
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20200430/26e7ee45/attachment.html>