<html><head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
</head>
<body>
<p><br>
</p>
<div class="moz-cite-prefix">On 2/5/20 6:13 PM, Chris Lattner via
llvm-dev wrote:<br>
</div>
<blockquote type="cite" cite="mid:FC5BF5FC-A6C4-47E5-B803-3FB42C1CA71F@nondot.org">
<br class="">
<div><br class="">
<blockquote type="cite" class="">
<div class="">On Feb 2, 2020, at 10:35 PM, Michael Kruse via
llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" class="" moz-do-not-send="true">llvm-dev@lists.llvm.org</a>>
wrote:</div>
<br class="Apple-interchange-newline">
<div class="">
<blockquote type="cite" style="font-family: Helvetica;
font-size: 12px; font-style: normal; font-variant-caps:
normal; font-weight: normal; letter-spacing: normal;
orphans: auto; text-align: start; text-indent: 0px;
text-transform: none; white-space: normal; widows: auto;
word-spacing: 0px; -webkit-text-size-adjust: auto;
-webkit-text-stroke-width: 0px; text-decoration: none;" class=""><br class="Apple-interchange-newline">
That's actually not how I read it. Red/green trees was
*one* of the nine items you mentioned in your list and
this didn't come out as the central idea in your opening
paras, but let's go with this now that it's clearer to me.<br class="">
</blockquote>
<br style="caret-color: rgb(0, 0, 0); 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; -webkit-text-stroke-width: 0px;
text-decoration: none;" class="">
<span style="caret-color: rgb(0, 0, 0); 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; -webkit-text-stroke-width: 0px;
text-decoration: none; float: none; display: inline
!important;" class="">Indeed, red/green trees (or DAGs)
are one one of the ideas to improve</span><br style="caret-color: rgb(0, 0, 0); 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;
-webkit-text-stroke-width: 0px; text-decoration: none;" class="">
<span style="caret-color: rgb(0, 0, 0); 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; -webkit-text-stroke-width: 0px;
text-decoration: none; float: none; display: inline
!important;" class="">loop optimizations, but does justify
its use by itself. They happen to</span><br style="caret-color: rgb(0, 0, 0); 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;
-webkit-text-stroke-width: 0px; text-decoration: none;" class="">
<span style="caret-color: rgb(0, 0, 0); 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; -webkit-text-stroke-width: 0px;
text-decoration: none; float: none; display: inline
!important;" class="">be effectively necessary for others
in the list (e.g. versioning,</span><br style="caret-color: rgb(0, 0, 0); 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;
-webkit-text-stroke-width: 0px; text-decoration: none;" class="">
<span style="caret-color: rgb(0, 0, 0); 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; -webkit-text-stroke-width: 0px;
text-decoration: none; float: none; display: inline
!important;" class="">profitiability heuristic by cost
function, etc...) and the reason why</span><br style="caret-color: rgb(0, 0, 0); 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;
-webkit-text-stroke-width: 0px; text-decoration: none;" class="">
<span style="caret-color: rgb(0, 0, 0); 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; -webkit-text-stroke-width: 0px;
text-decoration: none; float: none; display: inline
!important;" class="">I think the same cannot be done with
MLIR. In hindsight, I could have</span><br style="caret-color: rgb(0, 0, 0); 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;
-webkit-text-stroke-width: 0px; text-decoration: none;" class="">
<span style="caret-color: rgb(0, 0, 0); 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; -webkit-text-stroke-width: 0px;
text-decoration: none; float: none; display: inline
!important;" class="">pointed this out more in the
original RFC. Note that a hierarchical</span><br style="caret-color: rgb(0, 0, 0); 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;
-webkit-text-stroke-width: 0px; text-decoration: none;" class="">
<span style="caret-color: rgb(0, 0, 0); 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; -webkit-text-stroke-width: 0px;
text-decoration: none; float: none; display: inline
!important;" class="">representation was not an explicit
feature in the list.</span><br style="caret-color: rgb(0,
0, 0); 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;
-webkit-text-stroke-width: 0px; text-decoration: none;" class="">
<br style="caret-color: rgb(0, 0, 0); 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; -webkit-text-stroke-width: 0px;
text-decoration: none;" class="">
<span style="caret-color: rgb(0, 0, 0); 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; -webkit-text-stroke-width: 0px;
text-decoration: none; float: none; display: inline
!important;" class="">To convince me that MLIR is the
better IR for loop optimizations,</span><br style="caret-color: rgb(0, 0, 0); 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;
-webkit-text-stroke-width: 0px; text-decoration: none;" class="">
<span style="caret-color: rgb(0, 0, 0); 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; -webkit-text-stroke-width: 0px;
text-decoration: none; float: none; display: inline
!important;" class="">might show that each of the features
enabled by cheap subtree reuse</span><br style="caret-color: rgb(0, 0, 0); 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;
-webkit-text-stroke-width: 0px; text-decoration: none;" class="">
<span style="caret-color: rgb(0, 0, 0); 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; -webkit-text-stroke-width: 0px;
text-decoration: none; float: none; display: inline
!important;" class="">can also be done sufficiently
efficient and easily on MLIR (or that a</span><br style="caret-color: rgb(0, 0, 0); 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;
-webkit-text-stroke-width: 0px; text-decoration: none;" class="">
<span style="caret-color: rgb(0, 0, 0); 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; -webkit-text-stroke-width: 0px;
text-decoration: none; float: none; display: inline
!important;" class="">feature is not what would actually
would want).</span><br style="caret-color: rgb(0, 0, 0);
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; -webkit-text-stroke-width: 0px;
text-decoration: none;" class="">
</div>
</blockquote>
</div>
<br class="">
<div class="">Hi Michael,</div>
<div class=""><br class="">
</div>
<div class="">If I understand your claims, you are claiming both
that red/green trees are essential for a loop optimizer, and
that this essential nature “justifies” the cost of reinventing
an entire compiler infrastructure is lower than the benefit of
using (e.g.) MLIR to do this. I haven’t seen evidence of either
point:</div>
</blockquote>
<p><br>
</p>
<p>Michael and I have discussed this offilne, and I think that more
quantitative information here would be helpful. One phrasing might
be: For a reasonable test suite of programs, for the loops we
might optimize, how many different loop-nest variants do we need
to represent for costing purposes (also note that, depending on
profiling information and/or heuristics, we may need to cost at
multiple trip-count values)? Given that, what is the relative cost
of creating deep copies of the loop nests and transforming them
vs. the cost of using a red/green tree? Does that cost seem
significant?</p>
<p>We don't want to invest significant effort into a infrastructure
that we know ahead of time won't scale sufficiently.<br>
</p>
<p><br>
</p>
<blockquote type="cite" cite="mid:FC5BF5FC-A6C4-47E5-B803-3FB42C1CA71F@nondot.org">
<div class=""> lots of loop optimizers exist that don’t use
red/green trees.</div>
</blockquote>
<p><br>
</p>
<p>I've worked with many compilers, some from vendors known for
having strong loop optimizers, and none of them would meet our
goals for performance, robustness, and modeling accuracy (e.g.,
not regressing performance in many cases). Our goal here is to
significantly improve on the state of the art.<br>
</p>
<p><br>
</p>
<blockquote type="cite" cite="mid:FC5BF5FC-A6C4-47E5-B803-3FB42C1CA71F@nondot.org">
<div class=""><br class="">
</div>
<div class="">Furthermore, my experience is that specialized IRs
never get the investment in (e.g.). testing, location
propagation for debugging optimized code, textual round
tripping, pass management, and the multitude of other things
that are required for a world class compiler implementation.</div>
</blockquote>
<p><br>
</p>
<p>I agree, but I think that these are well-known requirements
within this ecosystem. What this means also depends on context (it
might be more helpful to think of this more like SCEV than like a
custom IR).</p>
<p> -Hal<br>
</p>
<p><br>
</p>
<blockquote type="cite" cite="mid:FC5BF5FC-A6C4-47E5-B803-3FB42C1CA71F@nondot.org">
<div class=""><br class="">
</div>
<div class="">-Chris</div>
<br>
<fieldset class="mimeAttachmentHeader"></fieldset>
<pre class="moz-quote-pre" wrap="">_______________________________________________
LLVM Developers mailing list
<a class="moz-txt-link-abbreviated" href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>
<a class="moz-txt-link-freetext" href="https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev">https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a>
</pre>
</blockquote>
<pre class="moz-signature" cols="72">--
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory</pre>
</body>
</html>