<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">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">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">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">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">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">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">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-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">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">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><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>