<html><head><meta http-equiv="Content-Type" content="text/html; charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class="">On Jan 14, 2020, at 8:39 PM, Michael Kruse <<a href="mailto:llvmdev@meinersbur.de" class="">llvmdev@meinersbur.de</a>> wrote:<div><blockquote type="cite" class=""><div class=""><div dir="auto" class=""><div dir="ltr" class=""><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 class=""><div class=""><div class="">Once that is established, there is a question of “what is the right representation to use”? This question has two subcomponents: what data structure should we use, and what is the IR within it.</div><div class=""><br class=""></div><div class="">If you propose introducing a brand new data structure, please expect me to push back on that pretty hard. </div></div></div></blockquote><div class=""><br class=""></div><div class="">Which I think is a good thing since I also do not want too many data structures being more-or-less well maintained. But I also think there is a good argument to a loop-centric data structure.</div></div></div></div></div></blockquote><div><br class=""></div><div>Agreed, I think it is incredibly important for a first class loop optimizer to have first class structured loops, parallel loops etc.</div><br class=""><blockquote type="cite" class=""><div dir="auto" class=""><div dir="ltr" class=""><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 class=""><div class=""><div class=""><br class="">One you achieve consensus on data structure, there is the question of what IR to use within it. I would recommend starting with some combination of “existing LLVM IR operations + high level control flow representation”, e.g. parallel and affine loops. The key here is that you need to always be able to lower in a simple and predictable way to LLVM IR (this is one of the things that classic polyhedral systems did sub optimally, making it difficult to reason about the cost model of various transformations), and this is a natural incremental starting point anyway. Over time, more high level concepts can be gradually introduced. FYI, MLIR already has a reasonable <a href="https://mlir.llvm.org/docs/Dialects/LLVM/" target="_blank" rel="noreferrer" class="">LLVM dialect</a> and can generate LLVM IR from it, so we’d just need an “LLVM IR -> MLIR LLVM dialect” conversion, which should be straightforward to build.</div></div></div></blockquote><div class=""><br class=""></div><div class="">Adding a LLVM-IR -> MLIR -> LLVM-IR round-trip would at the beginning just introduce compile-time overhead and what Renato described as brittleness. I fear this hurts adaption.</div></div></div></div></blockquote><div><br class=""></div><div>Isn’t this true of *any* higher level IR? Unless I’m missing something big, this seems inherent to your proposal.</div><br class=""><blockquote type="cite" class=""><div dir="auto" class=""><div dir="ltr" class=""><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 class=""><div class=""><div class="">Once you have the data structure and the dialect within it decided, you have the set of transformations. Again, you’ve given a lot of thought to this, and that all sounds great to me, but the priorities can be driven by whoever wants to contribute and what concrete problems they have to solve.</div><div class=""><br class=""></div><div class=""><br class=""></div><div class="">Once the infra for “raising to this representation and lowering back down” is figured out, we can open the box of having clang and other front ends directly generate it.</div></div></div></blockquote><div class=""><br class=""></div><div class="">This suggestions would also apply to VPlan. Ignoring that work on VPlan started before MLIR, would you have suggested to implement VPlan on MLIR as well? Would you maybe even advise to retarget VPlan on MLIR now?</div></div></div></div></blockquote><div><br class=""></div><div>I don’t know enough to say: the tradeoffs depend a lot of where VPlan is, the challenges it faces etc. I don’t know much about VPlan or the engineering priorities behind it.</div><div><br class=""></div><div><br class=""></div><div>Here’s an observation though: if you ignore the engineering expense, it would clearly make sense to reimplement the mid-level LLVM optimizers on top of MLIR and replace include/llvm/IR with a dialect definition in MLIR instead. </div><div><br class=""></div><div>MLIR as an IR is strictly equal to or better than the LLVM IR data structures in all ways that I’m aware of. In addition to representational flexibility, MLIR allows (and provides) a multithreaded pass manager (function passes run in parallel), has a better representation of PHI nodes, allows better terminators (eliminating need for the really ugly/unfortunate <a href="http://llvm.org/docs/LangRef.html#landingpad-instruction" class="">landingpad</a>, <a href="http://llvm.org/docs/LangRef.html#catchpad-instruction" class="">catchpad</a> etc hacks), has a better representation for “operands that must be constants” (immarg etc), provides a better representation for location information (important for debugging optimized code and diagnostic emission from the optimizer), and better testing tools (by building on the better location info).</div><div><br class=""></div><div>The additional representational flexibility would allow a much more flexible compiler design - one where you could do progressive lowering of high level loops, OpenMP, separate out ABI lowering from Clang IRGen, etc.</div><div><br class=""></div><div>I’m very fond of LLVM IR obviously, but a lot has been learned in the <a href="https://github.com/llvm/llvm-project/commit/2f7c963559dbc6dbda43df77a090a93f94c6625e" class="">nearly 20 years</a> since it was designed and implemented, and MLIR was implemented with a superset of the experience that built LLVM :)</div><div><br class=""></div><blockquote type="cite" class=""><div dir="auto" class=""><div dir="ltr" class=""><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 class=""><div class=""><blockquote type="cite" class=""><div class=""><div class="">Q: Relation to MLIR?</div></div></blockquote><blockquote type="cite" class=""><div class=""><div class="">A: MLIR is more similar to LLVM-IR than a loop hierarchy.</div></div></blockquote><div class=""><br class=""></div><div class="">This is not true, MLIR is great for dialects that want to model loop hierarchies naturally, this is a major focus of the <a href="https://mlir.llvm.org/docs/Dialects/Affine/" target="_blank" rel="noreferrer" class="">affine dialect</a> (e.g. see affine.for on that page). MLIR is not limited to affine loops, that is just a choice made by the affine dialect - the <a href="https://mlir.llvm.org/docs/Dialects/LoopOps/" target="_blank" rel="noreferrer" class="">loop dialect</a> has more general constructs that are less developed.</div></div></div></blockquote><div class=""><br class=""></div><div class=""><br class=""></div><div class="">This is definitely subjective question. I think that MLIR is closer to LLVM-IR for how it is processed. Both have a sequence of passes running over a single source of truth. Both allow walking the entire structure from every instruction/operation/block. Analyses are on function or module level. Both have CFGs (I think for a certain kind of transformations it is an advantage that control flow is handled implicitly).</div></div></div></div></blockquote><div><br class=""></div><div>Right, but a frequent way that MLIR is used is without its CFG: most machine learning kernels use nests of loops and ifs, not CFGs. CFGs are exposed when those are lowered out. See some simple examples like:</div><div><a href="https://github.com/llvm/llvm-project/blob/master/mlir/test/Transforms/affine-data-copy.mlir" class="">https://github.com/llvm/llvm-project/blob/master/mlir/test/Transforms/affine-data-copy.mlir</a></div><div><br class=""></div><br class=""><blockquote type="cite" class=""><div dir="auto" class=""><div dir="ltr" class=""><div class="gmail_quote"><div class=""><br class=""></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div class=""><div class=""><blockquote type="cite" class=""><div class=""><div class=""> For<br class="">instance, it also does not feature cheap copies. </div></div></blockquote><div class=""><br class=""></div><div class="">I’m not sure what this means.</div><br class=""></div></div></blockquote><div class=""><br class=""></div><div class="">The possibility to make local changes speculatively without copying the entire data structure. IMHO this is a central idea that allows applying a transformations speculatively to pass it to a legality check and cost heuristic without committing to apply it. As a consequence, passes do not need to implement to implement these in a transformation-specific manner, drastically reducing the burden of implementation.</div><div class=""><br class=""></div><div class="">For instance, more loop transformations are feasible if instructions are moved into the innermost loops. With speculative transformations, we can canonicalize the representation to sink computations into loops -- the opposite of what LICM does -- and then see whether a transformation can applied. If not, the speculative representation is discarded without having an effect on the original representation (and not needing to hoist those computations again).</div><div class=""><br class=""></div><div class="">Because the MLIR classes have many references to related objects (such as pointer to parents and use-def chains), I don't think it is feasible to implement on top of MLIR. </div></div></div></div></blockquote><div><br class=""></div><div>Ah yes, I see what you mean. One way to do that is to represent multiple options as an op with region for each option. This means you only fork the part of the IR that you’re producing variants of. I think this is the red/green tree technique you mentioned, but I’m not sure.</div><br class=""><blockquote type="cite" class=""><div dir="auto" class=""><div dir="ltr" class=""><div class="gmail_quote"><div class=""><br class=""></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div class=""><div class=""><blockquote type="cite" class=""><div class=""><div class="">An advantage is that<br class="">loops and multi-dimensional arrays can be represented in the language<br class="">without the need of being rediscovered, but have to be inserted by a<br class="">front-end. </div></div></blockquote><div class=""><br class=""></div><div class="">This is correct, but I don’t see how this helps if your focus is raising code that has already been lowered to LLVM IR, e.g. by Clang or some other frontend that generates LLVM IR today.</div></div></div></blockquote><div class=""><br class=""></div><div class="">Indeed, I would hope that LLVM-IR can preserve multi-dimensional array accesses in some fashion as well (<a href="https://lists.llvm.org/pipermail/llvm-dev/2019-July/134063.html" target="_blank" rel="noreferrer" class="">https://lists.llvm.org/pipermail/llvm-dev/2019-July/134063.html</a>). However, currently MLIR has the advantage of being able represent it.</div></div></div></div></blockquote><div><br class=""></div><div>I don’t think LLVM IR will ever get there without a massive design change. It is possible that it will support static shaped accesses in limited ways though.</div><br class=""><blockquote type="cite" class=""><div dir="auto" class=""><div dir="ltr" class=""><div class="gmail_quote"><div class=""> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div class=""><div class=""><blockquote type="cite" class=""><div class=""><div class="">That is, if Clang was generating MLIR, loops and arrays<br class="">still have to be rediscovered. </div></div></blockquote><div class=""><br class=""></div><div class="">This isn’t true, it would be perfectly sensible to lower C control flow structures directly too LLVM. The primary concern are things like unstructured switches (think duff’s device) and unstructured gotos, but these occur rarely: they need to be handled correctly, but can do so with a traditionally lowered CFG and other “best effort” attempts to raise them.</div></div></div></blockquote><div class=""><br class=""></div><div class="">Moreover, syntactical loop structures are also not a reliable indicator that there is a loop. Often enough, do,for and while are used for syntactical reasons (`do { } while(0)`). Yes, you could eliminate them if a non-loop is detected, but handling break, continue, etc correctly is a lot of effort. Another case are corountines that are lowered with gotos into loops, unless you think loop optimizers should handle coroutines directly.</div></div></div></div></blockquote><div><br class=""></div><div>Yes, you’d want to canonicalize the form of course.</div><br class=""><blockquote type="cite" class=""><div dir="auto" class=""><div dir="ltr" class=""><div class="gmail_quote"><div class="">On the other side, natural loop detection on CFGs is quite mature (with a remaining issue of irreducible loops that might appear, but can also be eliminated again). As a plus, optimization does depend less on how the source code is written.<br class=""></div></div></div></div></blockquote><br class=""></div><div>Yep totally. The question is whether you lose semantic information from lowering to a CFG and reconstructing back up. This can affect you when you have higher level language semantics (e.g. Fortran parallel loops, openmp or other concurrency constructs etc). This is where MLIR excels of course.</div><div><br class=""></div><div>-Chris</div><br class=""></body></html>