<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">xerofoify@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid 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">llvm-dev@lists.llvm.org</a>>
wrote:<br>
</div>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid 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">clattner@nondot.org</a>>
wrote:<br>
</div>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid 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">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:1px solid 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">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:1px solid 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:1px solid 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">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">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">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">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:1px solid 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">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">multi-threaded pass timing</a> than making the pass manager itself multi-threaded.</div><div><br></div><div>-- River</div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div>
<br>
Nick <br>
<br>
<blockquote type="cite">
<div dir="ltr">
<div class="gmail_quote">
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<div dir="ltr">
<div class="gmail_quote">
<div> </div>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<div>
<div><br>
</div>
<div>-Chris</div>
</div>
</blockquote>
</div>
</div>
_______________________________________________<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="https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br>
</blockquote>
</div>
</div>
<br>
<fieldset></fieldset>
<pre>_______________________________________________
LLVM Developers mailing list
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>
<a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" target="_blank">https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a>
</pre>
</blockquote>
<br>
</div>
</blockquote></div></div>