<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
</head>
<body>
<br>
<br>
<div class="moz-cite-prefix">On 2/29/20 9:38 PM, Mehdi AMINI wrote:<br>
</div>
<blockquote type="cite"
cite="mid:CANF-O=YzPTDaxLWxYR+4pBQV=-a7mf_jv7sy4xyLN1Euceqc_w@mail.gmail.com">
<meta http-equiv="content-type" content="text/html; charset=UTF-8">
<div dir="ltr">
<div dir="ltr">
<div dir="ltr"><br>
</div>
<br>
<div class="gmail_quote">
<div dir="ltr" class="gmail_attr">On Sat, Feb 29, 2020 at
5:14 PM Nicholas Krause via llvm-dev <<a
href="mailto:llvm-dev@lists.llvm.org"
moz-do-not-send="true">llvm-dev@lists.llvm.org</a>>
wrote:<br>
</div>
<blockquote class="gmail_quote" style="margin:0px 0px 0px
0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">
<div> <br>
<br>
<div>On 2/29/20 7:23 PM, River Riddle wrote:<br>
</div>
<blockquote type="cite">
<div dir="ltr">
<div dir="ltr"><br>
</div>
<br>
<div class="gmail_quote">
<div dir="ltr" class="gmail_attr">On Sat, Feb 29,
2020 at 4:00 PM Nicholas Krause <<a
href="mailto:xerofoify@gmail.com"
target="_blank" moz-do-not-send="true">xerofoify@gmail.com</a>>
wrote:<br>
</div>
<blockquote class="gmail_quote" style="margin:0px
0px 0px
0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">
<div> <br>
<br>
<div>On 2/29/20 6:17 PM, River Riddle via
llvm-dev wrote:<br>
</div>
<blockquote type="cite">
<div dir="ltr">
<div dir="ltr"><br>
</div>
<br>
<div class="gmail_quote">
<div dir="ltr" class="gmail_attr">On
Sat, Feb 29, 2020 at 2:25 PM David
Blaikie via llvm-dev <<a
href="mailto:llvm-dev@lists.llvm.org"
target="_blank"
moz-do-not-send="true">llvm-dev@lists.llvm.org</a>>
wrote:<br>
</div>
<blockquote class="gmail_quote"
style="margin:0px 0px 0px
0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">
<div dir="ltr">
<div dir="ltr"><br>
</div>
<br>
<div class="gmail_quote">
<div dir="ltr" class="gmail_attr">On
Sat, Feb 29, 2020 at 2:19 PM
Chris Lattner <<a
href="mailto:clattner@nondot.org"
target="_blank"
moz-do-not-send="true">clattner@nondot.org</a>>
wrote:<br>
</div>
<blockquote class="gmail_quote"
style="margin:0px 0px 0px
0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">
<div>On Feb 29, 2020, at 2:08
PM, David Blaikie <<a
href="mailto:dblaikie@gmail.com"
target="_blank"
moz-do-not-send="true">dblaikie@gmail.com</a>>
wrote:
<div>
<blockquote type="cite">
<div>
<blockquote
class="gmail_quote"
style="font-family:Helvetica;font-size:12px;font-style:normal;font-variant-caps:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-decoration:none;margin:0px
0px 0px
0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">I've<span> </span><br>
curious as<br>
to how MLIR deals with
IPO as that's the
problem I was running
into.<span> </span><br>
</blockquote>
<div
style="font-family:Helvetica;font-size:12px;font-style:normal;font-variant-caps:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-decoration:none"><br>
FWIW I believe LLVM's
new pass manager (NPM)
was designed with
parallelism and the
ability to support
this situation (that
MLIR doesn't? Or
doesn't to the
degree/way in which
the NPM does). I'll
leave it to folks
(Chandler probably has
the most context here)
to provide some more
detail there if they
can/have time.<br>
</div>
</div>
</blockquote>
</div>
<br>
<div>Historically speaking,
all of the LLVM pass
managers have been designed
to support multithreaded
compilation (check out the
ancient history of the <a
href="http://llvm.org/docs/WritingAnLLVMPass.html"
target="_blank"
moz-do-not-send="true">WritingAnLLVMPass</a> doc
if curious).</div>
</div>
</blockquote>
<div><br>
</div>
<div>I think the specific thing
that might'v been a bit
different in the NPM was to do
with analysis invalidation in a
way that's more parallelism
friendly than the previous one -
but I may be
misrepresenting/misundrstanding
some of it.</div>
<div> </div>
<blockquote class="gmail_quote"
style="margin:0px 0px 0px
0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">
<div>
<div>The problem is that LLVM
has global use-def chains on
constants, functions and
globals, etc, so it is
impractical to do this.
Every “inst->setOperand”
would have to be able to
take locks or use something
like software transactional
memory techniques in their
implementation. This would
be very complicated and very
slow.<br>
</div>
</div>
</blockquote>
<div><br>
Oh, yeah - I recall that
particular limitation being
discussed/not addressed as yet.<br>
</div>
<blockquote class="gmail_quote"
style="margin:0px 0px 0px
0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">
<div>
<div>MLIR defines this away
from the beginning. This is
a result of the core IR
design, not the pass manager
design itself.<br>
</div>
</div>
</blockquote>
<div><br>
What does MLIR do differently
here/how does it define that
issue away? (doesn't have
use-lists built-in?)<br>
</div>
</div>
</div>
</blockquote>
<div><br>
</div>
<div>The major thing is that constants
and global-like objects don't produce
SSA values and thus don't have
use-lists. <a
href="https://mlir.llvm.org/docs/Rationale/#multithreading-the-compiler"
target="_blank"
moz-do-not-send="true">https://mlir.llvm.org/docs/Rationale/#multithreading-the-compiler</a> discusses
this a bit. </div>
<div><br>
</div>
<div>For constants, the data is stored
as an Attribute(context uniqued
metadata, have no use-list, not SSA).
This attribute can either placed in
the attribute list(if the operand is
always constant, like for the value of
a switch case), otherwise it must be
explicitly materialized via some
operation. For example, the `<a
href="https://mlir.llvm.org/docs/Dialects/Standard/#constant-operation"
target="_blank"
moz-do-not-send="true">std.constant</a>`
operation will materialize an SSA
value from some attribute data.</div>
<div><br>
</div>
<div>For references to functions and
other global-like objects, we have a
non-SSA mechanism built around
`symbols`. This is essentially using a
special attribute to reference the
function by-name, instead of by ssa
value. You can find more information
on <a
href="https://mlir.llvm.org/docs/SymbolsAndSymbolTables/"
target="_blank"
moz-do-not-send="true">MLIR symbols
here</a>. </div>
<div><br>
</div>
<div>Along with the above, there is a
trait that can be attached to
operations called `<a
href="https://mlir.llvm.org/docs/Traits/#isolatedfromabove"
target="_blank"
moz-do-not-send="true">IsolatedFromAbove</a>`.
This essentially means that no SSA
values defined above a region can be
referenced from within that region.
The pass manager only allows schedule
passes on operations that have this
property, meaning that all pipelines
are implicitly multi-threaded.</div>
<div><br>
</div>
<div>The pass manager in MLIR was
heavily inspired by the work on the
new pass manager in LLVM, but with
specific constraints/requirements that
are unique to the design of MLIR. That
being said, there are some usability
features added that would also make
great additions to LLVM: instance
specific pass options and statistics,
pipeline crash reproducer generation,
etc.</div>
<div><br>
</div>
<div>Not sure if any of the above helps
clarify, but happy to chat more if you
are interested.</div>
<div><br>
</div>
<div>-- River</div>
<div> </div>
<blockquote class="gmail_quote"
style="margin:0px 0px 0px
0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">
<div dir="ltr">
<div class="gmail_quote">
<div>- Dave<br>
</div>
</div>
</div>
</blockquote>
</div>
</div>
</blockquote>
River,<br>
The big thing from my reading of the Pass
Manager in MLIR is that it allows us to
iterate through<br>
a pass per function or module as a group
allowing it to run in async. I've proposed
this <br>
on the GCC side:<br>
<a
href="https://gcc.gnu.org/ml/gcc/2020-02/msg00247.html"
target="_blank" moz-do-not-send="true">https://gcc.gnu.org/ml/gcc/2020-02/msg00247.html</a><br>
<br>
Its to walk through the IPA passes which are
similar to analyze passes on the LLVM side.<br>
</div>
</blockquote>
<div><br>
</div>
<div>Hi Nicholas,</div>
<div><br>
</div>
<div>I can't say anything about the GCC side, but
this isn't a particularly novel aspect of the
MLIR pass manager. In many ways, the pass
manager is the easiest/simplest part of the
multi-threading problem. The bigger problem is
making sure that the rest of the compiler
infrastructure is structured in a way that is
thread-safe, or can be made thread-safe. This is
why most of the discussion is based around how
to model things like constants, global values,
etc. When I made MLIR multi-threaded a year ago,
a large majority of my time was spent outside of
the pass manager. For a real example, I spent
much more time just on <a
href="https://mlir.llvm.org/docs/WritingAPass/#multi-threaded-pass-timing"
target="_blank" moz-do-not-send="true">multi-threaded
pass timing</a> than making the pass manager
itself multi-threaded.</div>
<div><br>
</div>
<div>-- River</div>
</div>
</div>
</blockquote>
Actually in my experience, the biggest problem is if we
can detect IPO and run async guarantees on that. MLIR
runs operations but only for a module or set of
functions<br>
without this. One of my dreams would be to run passes in
parallel including IPO detection and stop if it cannot
continue pass a IPO pass or set of passes due to
changes.<br>
<br>
Maybe MLIR does do that but its the one bottleneck that
is really hard to fix,<br>
</div>
</blockquote>
<div><br>
</div>
<div>What MLIR does (that would require quite some work in
LLVM) is making sure that you can process and transform
functions in isolation, allowing to run *local*
optimizations in parallel. This does not solve the IPO
problem you're after. As I understand it, this is a
difficult thing to design, and it requires consideration
about how you think the passes and the pass-pipeline
entirely.</div>
</div>
</div>
</div>
</blockquote>
I've been thinking about it on the GCC side for the last few months.
It's non trivial through something similar to this may be possible
but I<br>
will need to research both pass managers better:<br>
<a
href="https://elixir.bootlin.com/linux/latest/source/include/linux/workqueue.h#L102">https://elixir.bootlin.com/linux/latest/source/include/linux/workqueue.h#L102</a><br>
<br>
I'm looking on some RFCS for the pass manager and SSA iterators on
the GCC side. Through one easy thing to do is a lot of core<br>
classes in both GCC/LLVM there are loops that run a lot. LRA on the
GCC for register allocation does. We may want to figure<br>
out how and if its a good idea to run these loops in small worker
functions that are only used by the one function that requires<br>
it. The only real question is some loops are only very performance
intensive on corner cases which we may require heuristics<br>
in order to decide when to launch i.e. number of elements iterating
through e.t.c. Maybe that's a bad idea but after looking <br>
through the GCC and LLVM side a little this seems to be a later
tedious but trivial fix mostly due to figuring out what loops are<br>
expensive enough to do this.<br>
<br>
I believe Johannes was going to reach out next week about the Module
Classes and we will go for there,<br>
<br>
Nick<br>
<blockquote type="cite"
cite="mid:CANF-O=YzPTDaxLWxYR+4pBQV=-a7mf_jv7sy4xyLN1Euceqc_w@mail.gmail.com">
<div dir="ltr">
<div dir="ltr">
<div class="gmail_quote">
<div><br>
</div>
<div>Running function-passes and "local" optimizations in
parallel in LLVM isn't possible because the structures in
the LLVMContext aren't thread-safe, and because the IR
itself isn't thread-safe. Something like just DCE or CSE a
function call requires to modify the callee (through its
use-list).</div>
<div><br>
</div>
<div>-- </div>
<div>Mehdi</div>
</div>
</div>
</div>
</blockquote>
<br>
</body>
</html>