<div dir="ltr">I mentioned this earlier in the thread - I would like to see something like D41574 in the optimizer. It's optimizing code that no other pass does currently, and I don't see any other near-term proposal that gets us those optimizations.<br> <br><div>Omer, can you rebase that to trunk? I think a header has moved, so it doesn't build as-is. I'd like to know if it can catch the cases in D45842. If not, why not? If it can handle those easily, I'll abandon D45842.<br></div><div><br></div>Also, I don't know if it's better to include that functionality as another iteration of the existing -reassociate or split it off as its own pass. But I think it should do the distributive simplifications that are currently in -instcombine (InstCombiner::<wbr>SimplifyUsingDistributiveLaws)<wbr>. Using that instsimplify logic for analysis lets us decide if the reassociation is worthwhile in the 1st place, it removes the risk that some other pass would somehow mess up the pattern before instcombine could zap it, and it reduces the burden on instcombine to be the entire optimizer. :)<br><div><div><div><div> </div></div></div></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Mon, May 14, 2018 at 1:34 PM, Hiroshi Yamauchi via llvm-dev <span dir="ltr"><<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div class="gmail_default" style="font-family:arial,helvetica,sans-serif"><br></div><br><div class="gmail_quote"><div><div class="gmail-h5"><div dir="ltr">On Fri, May 11, 2018 at 7:20 PM Hal Finkel <<a href="mailto:hfinkel@anl.gov" target="_blank">hfinkel@anl.gov</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 bgcolor="#FFFFFF">
<br>
<div class="gmail-m_596114956539797037gmail-m_7327146177040704443moz-cite-prefix">On 05/11/2018 08:40 PM, Daniel Berlin
via llvm-dev wrote:<br>
</div>
<blockquote type="cite">
<div dir="ltr"><br>
<div class="gmail_extra"><br>
<div class="gmail_quote">On Fri, May 11, 2018 at 2:37 PM,
Hiroshi Yamauchi <span dir="ltr"><<a href="mailto:yamauchi@google.com" target="_blank">yamauchi@google.com</a>></span>
wrote:<br>
<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 style="font-family:arial,helvetica,sans-serif"><br>
</div>
<br>
<div class="gmail_quote">
<div>
<div class="gmail-m_596114956539797037gmail-m_7327146177040704443gmail-m_2423541276025245453h5">
<div dir="ltr">On Thu, May 10, 2018 at 12:49 PM
Daniel Berlin <<a href="mailto:dberlin@dberlin.org" target="_blank">dberlin@dberlin.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"><br>
<div class="gmail_extra"><br>
<div class="gmail_quote">On Thu, May 10,
2018 at 12:05 PM, Hiroshi Yamauchi <span dir="ltr"><<a href="mailto:yamauchi@google.com" target="_blank">yamauchi@google.com</a>></span>
wrote:<br>
<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 style="font-family:arial,helvetica,sans-serif"><br>
</div>
<br>
<div class="gmail_quote"><span>
<div dir="ltr">On Wed, May 9, 2018
at 8:24 PM Daniel Berlin <<a href="mailto:dberlin@dberlin.org" target="_blank">dberlin@dberlin.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"><br>
<div class="gmail_extra"><br>
<div class="gmail_quote">On
Wed, May 9, 2018 at 10:39
AM, Hiroshi Yamauchi <span dir="ltr"><<a href="mailto:yamauchi@google.com" target="_blank">yamauchi@google.com</a>></span>
wrote:<br>
<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 style="font-family:arial,helvetica,sans-serif"><br>
</div>
<br>
<div class="gmail_quote"><span class="gmail-m_596114956539797037gmail-m_7327146177040704443gmail-m_2423541276025245453m_-9018700274548918466gmail-m_2085822097580644453m_402989712542517733gmail-m_8307257963026143428gmail-">
<div dir="ltr">On
Tue, May 8, 2018
at 11:15 AM
Daniel Berlin
<<a href="mailto:dberlin@dberlin.org" target="_blank">dberlin@dberlin.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"><br>
<div class="gmail_extra"><br>
<div class="gmail_quote">On
Tue, May 8,
2018 at 10:38
AM, Hiroshi
Yamauchi via
llvm-dev <span dir="ltr"><<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>></span>
wrote:<br>
<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 style="color:rgb(34,34,34);font-size:13px;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-decoration-style:initial;text-decoration-color:initial;font-family:arial,helvetica,sans-serif;display:inline">I
came across
this issue in
the context of</div>
<span style="color:rgb(34,34,34);font-family:sans-serif;font-size:13px;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial;float:none;display:inline"> </span><a href="https://reviews.llvm.org/D46336" style="color:rgb(17,85,204);font-family:sans-serif;font-size:13px;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px" target="_blank">D46336</a><span style="color:rgb(34,34,34);font-family:sans-serif;font-size:13px;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial;float:none;display:inline">.</span>
<div style="font-family:arial,helvetica,sans-serif;display:inline">
</div>
Thanks,
Sanjay, for
starting this
discussion.)<br>
<div><br>
</div>
<div>If
<div style="font-family:arial,helvetica,sans-serif;display:inline">we
will</div>
move <span style="color:rgb(34,34,34);font-family:sans-serif;font-size:13px;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial;float:none;display:inline">
<div style="font-family:arial,helvetica,sans-serif;display:inline">reassociation, </div>
</span>or keep
additional
ones
<div style="font-family:arial,helvetica,sans-serif;display:inline">,</div>
out of
instcombine,
<div style="font-family:arial,helvetica,sans-serif;display:inline">open
questions for
me would be</div>
<div style="font-family:arial,helvetica,sans-serif;display:inline">:</div>
<br>
<br>
1. Since
-reassociate
isn't a fixed
point pass,</div>
</div>
</blockquote>
<div><br>
</div>
<div>This is
fixable, fwiw,
without
fixpointing
it.</div>
</div>
</div>
</div>
</blockquote>
<div><br>
</div>
</span>
<div>
<div style="font-family:arial,helvetica,sans-serif">How?</div>
</div>
</div>
</div>
</blockquote>
<div><br>
</div>
<div>Depends on
specifically which part
you would like to know
about ;)</div>
</div>
</div>
</div>
</blockquote>
<div><br>
</div>
</span>
<div>
<div style="font-family:arial,helvetica,sans-serif">Maybe
I misunderstood what you meant
by "This is fixable". Did you
mean that we won't somehow need
to fixpoint between instcombine
and reassociate, or that <span style="color:rgb(34,34,34);font-family:arial,helvetica,sans-serif;font-size:13px;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial;float:none;display:inline">the
specific motivating examples
from the above differentials
are foldable without
fixpointing?</span></div>
</div>
</div>
</div>
</blockquote>
<div><br>
</div>
<div>If by fixpointing you mean
"fixpointing reassociate and
instcombine", then yes, that is fixable
without fixpointing reassociate and
instcombine, but would require rewriting
instcombine :)</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 dir="ltr">
<div class="gmail_quote">
<div style="font-family:arial,helvetica,sans-serif"><br>
</div>
<div style="font-family:arial,helvetica,sans-serif"><span style="color:rgb(34,34,34);font-family:arial,helvetica,sans-serif;font-size:13px;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial;float:none;display:inline">If
the latter, that may be the
case. The concern was that we
may encounter examples that may
need many more iterations, if
not fixpointing. As long as it's
feasible to fixpoint between <span style="color:rgb(34,34,34);font-family:arial,helvetica,sans-serif;font-size:13px;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial;float:none;display:inline">instcombine
and reassociate, it seems to
work, but I guess that would <span style="color:rgb(34,34,34);font-family:arial,helvetica,sans-serif;font-size:13px;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial;float:none;display:inline">probably </span>need
some pass management change.</span></span></div>
<div>
<div class="gmail-m_596114956539797037gmail-m_7327146177040704443gmail-m_2423541276025245453m_-9018700274548918466gmail-m_2085822097580644453h5">
<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 dir="ltr">
<div class="gmail_extra">
<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 dir="ltr">
<div class="gmail_quote"><span class="gmail-m_596114956539797037gmail-m_7327146177040704443gmail-m_2423541276025245453m_-9018700274548918466gmail-m_2085822097580644453m_402989712542517733gmail-m_8307257963026143428gmail-">
<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 dir="ltr">
<div class="gmail_extra">
<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 dir="ltr">
<div> we might
need to repeat
"-instcombine
-reassociate"
multiple times
to
<div style="font-family:arial,helvetica,sans-serif;display:inline">fold</div>
down to what
we want
(relating to <a href="https://reviews.llvm.org/D46336#1087082" target="_blank">my
comment here</a>).
I assumed this
isn't not what
we want to do
<div style="font-family:arial,helvetica,sans-serif;display:inline">?
My impression
is we don't do
a fixed-point
with passes?</div>
</div>
</div>
</blockquote>
<div><br>
</div>
<div>Well, i
mean there is
no practical
difference
between passes
that we
fixpoint
externally and
fixpoint
internally.</div>
</div>
</div>
</div>
</blockquote>
</span>
<div>
<div style="font-family:arial,helvetica,sans-serif"></div>
<div style="font-family:arial,helvetica,sans-serif"><span style="color:rgb(34,34,34);font-family:arial,helvetica,sans-serif;font-size:13px;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial;float:none;display:inline">I
had the
following in
mind: Does the
pass manager
support
fixpointing
externally? Is
there any
performance
difference?
Are people
okay with that
in general?</span></div>
<div style="font-family:arial,helvetica,sans-serif"><br>
</div>
<div style="font-family:arial,helvetica,sans-serif">But
if <span style="font-family:sans-serif">there
is no
practical
difference</span>,
I don't see
any problem
with that :)</div>
</div>
<span class="gmail-m_596114956539797037gmail-m_7327146177040704443gmail-m_2423541276025245453m_-9018700274548918466gmail-m_2085822097580644453m_402989712542517733gmail-m_8307257963026143428gmail-">
<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 dir="ltr">
<div class="gmail_extra">
<div class="gmail_quote">
<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 dir="ltr">
<div> <br>
</div>
</div>
</blockquote>
<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>2.
<div style="font-family:arial,helvetica,sans-serif;display:inline">Since
-<span style="color:rgb(34,34,34);font-family:sans-serif;font-size:13px;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial;float:none;display:inline">reassociate
needs to come
up with one
operand order
(at least
currently as
the only <span style="color:rgb(34,34,34);font-family:sans-serif;font-size:13px;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial;float:none;display:inline">reassociate </span>pass),
would there
exist a
single, unique
operand order
that would
enable all <span style="color:rgb(34,34,34);font-family:arial,helvetica,sans-serif;font-size:13px;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial;float:none;display:inline"><span style="color:rgb(34,34,34);font-family:sans-serif;font-size:13px;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial;float:none;display:inline">reassociative/commutative</span>
foldings that
we want? </span></span></div>
</div>
</div>
</blockquote>
<div><br>
</div>
<div>In what
way?</div>
<div>Are you
asking whether
there is a
single
reassociation
order that
makes all
foldings occur
in the same
operation or
something?<br>
I don't feel
like i
understand
what you are
asking.<br>
</div>
</div>
</div>
</div>
</blockquote>
<div><br>
</div>
</span>
<div>
<div><span style="font-family:arial,helvetica,sans-serif">Does
this rephrase
help: with the
motivating
examples (like
and-of-shifts
or bit check
patterns) from
the above
differentials
in mind, can
we come up
with a single <span style="color:rgb(34,34,34);font-family:sans-serif;font-size:13px;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial;float:none;display:inline">reassociation
order that
solves all
those and all
the others
that may come
up in the
future? Would
we need
different <span style="color:rgb(34,34,34);font-family:sans-serif;font-size:13px;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial;float:none;display:inline">reassociation
orders to fold
different
patterns?</span></span></span></div>
</div>
<span class="gmail-m_596114956539797037gmail-m_7327146177040704443gmail-m_2423541276025245453m_-9018700274548918466gmail-m_2085822097580644453m_402989712542517733gmail-m_8307257963026143428gmail-"></span></div>
</div>
</blockquote>
<div><br>
</div>
<div>It doesn't quite
help.</div>
<div>When stated that
generally, there can
be no such ordering at
all, that's easy to
prove. It is a
statically undecidable
problem.</div>
<div><br>
</div>
<div>There is however, a
different question and
answer to a few
related problems that
maybe you are really
asking?<br>
1. Is there a way to
determine and apply
the a maximal or
nearly-maximal set of
folds/graph transforms
that could be applied
to a given set of code
in a sane and
principled way ->
yes</div>
<div><br>
</div>
<div>(see, e.g., <a href="http://www.cs.cornell.edu/%7Eross/publications/eqsat/" target="_blank">http://www.cs.cornell.<wbr>edu/~ross/publications/eqsat/</a>)</div>
<div><br>
</div>
<div>2. Is there a way
to determine all
expressions in the
program as it exists
that are equivalent or
equivalent under
constant time constant
folding/reassociation,
in a reasonable time
bound -> yes</div>
<div><br>
</div>
<div>(not a single easy
link, happy to talk
about it)</div>
<div><br>
</div>
<div>Your original
question is basically
equivalent to</div>
<div>
<div style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:small;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial">Is
there a way to
determine all
expressions in the
program as it exists
that are equivalent
or could be made
equivalent through
any type of folding
that one can think
up?</div>
<div style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:small;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial">The
answer to that is
"no", it's provable
that this is not
statically
decidable, so the
time bound doesn't
matter :)</div>
<div style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:small;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial"><br>
</div>
<div style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:small;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial">You
have to limit the
possible
folding/evaluation
you apply in various
ways to make this
decidable, and then
further limit it to
make the time bound
reasonable.</div>
<div style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:small;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial"><br>
</div>
<div style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:small;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial">This
all quickly devolves
into herbrand
equivalence and it's
variations.</div>
<div style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:small;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial"><br>
</div>
<div style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:small;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial"><br>
</div>
</div>
</div>
</div>
</div>
</blockquote>
<div><span style="font-family:arial,helvetica,sans-serif"></span></div>
</div>
</div>
<div>
<div><font face="arial, helvetica,
sans-serif">Let me try one
more time :) </font><span style="font-family:arial,helvetica,sans-serif">May
we need multiple reassociate
passes to fold different </span><span style="font-family:arial,helvetica,sans-serif">reassociative patterns?</span></div>
<div><font face="arial, helvetica,
sans-serif"><br>
</font></div>
<div><font face="arial, helvetica,
sans-serif">A longer version:
If Sanjay wants a particular
reassociative pattern to be
folded (D45842), Omer wants
another particular </font><span style="font-family:arial,helvetica,sans-serif">reassociative <span style="color:rgb(34,34,34);font-family:arial,helvetica,sans-serif;font-size:13px;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial;float:none;display:inline">pattern</span>
to be folded (</span><font face="arial, helvetica,
sans-serif">D41574)</font><span style="font-family:arial,helvetica,sans-serif">, and I want yet another </span><font face="arial, helvetica,
sans-serif"></font><span style="font-family:arial,helvetica,sans-serif">particular </span><span style="font-family:arial,helvetica,sans-serif">reassociat<wbr>ive <span style="color:rgb(34,34,34);font-family:arial,helvetica,sans-serif;font-size:13px;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial;float:none;display:inline">pattern</span>
to be folded (</span><font face="arial, helvetica,
sans-serif">D46336)</font><span style="font-family:arial,helvetica,sans-serif">, would we potentially
need three
different reassociate passes
with each combined with
instcombine, rather than just
one that may be able to <span style="color:rgb(34,34,34);font-family:arial,helvetica,sans-serif;font-size:13px;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial;float:none;display:inline">somehow </span>handle
those cases in one shot,
(assuming we don't want to put
those in instcombine)?</span></div>
<div><span style="font-family:arial,helvetica,sans-serif"><br>
</span></div>
<div><span style="font-family:arial,helvetica,sans-serif">And
it sounds like the answer is
yes?</span></div>
</div>
</div>
</div>
</blockquote>
<div><br>
</div>
<div>If you take the current instcombine
as a base, then yes, that is correct.</div>
</div>
</div>
</div>
</blockquote>
<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_extra">
<div class="gmail_quote">
<div>
<div style="font-family:arial,helvetica,sans-serif;display:inline"></div>
If you are willing to rearchitect
instcombine, the answer is no, it's
possible to do this all in a single pass
in a relatively sane way.</div>
</div>
</div>
</div>
</blockquote>
<div>
<div style="font-family:arial,helvetica,sans-serif"><br>
</div>
</div>
</div>
</div>
<div style="font-family:arial,helvetica,sans-serif">I
assume by <span style="color:rgb(34,34,34);font-family:sans-serif;font-size:13px;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial;float:none;display:inline">rearchitect,
you mean a major rewrite as per this comment</span><span style="font-family:sans-serif">: </span><span style="font-family:sans-serif">"</span><span style="font-family:sans-serif">Is there a way to
determine all expressions in the program as it
exists that are equivalent or equivalent under
constant time constant folding/reassociation, in a
reasonable time bound -> yes". </span><span style="font-family:sans-serif">Any pointer or time
to chat?</span></div>
</div>
</div>
</blockquote>
<div><br>
</div>
<div>I'm happy to do both.</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 style="font-family:arial,helvetica,sans-serif"></div>
<div>
<div>
<div style="font-family:arial,helvetica,sans-serif;display:inline">I
think that an approach like </div>
D
<div style="font-family:arial,helvetica,sans-serif;display:inline"></div>
<div style="font-family:arial,helvetica,sans-serif;display:inline"></div>
4
<div style="font-family:arial,helvetica,sans-serif;display:inline"></div>
<div style="font-family:arial,helvetica,sans-serif;display:inline"></div>
6
<div style="font-family:arial,helvetica,sans-serif;display:inline"></div>
<div style="font-family:arial,helvetica,sans-serif;display:inline"></div>
3
<div style="font-family:arial,helvetica,sans-serif;display:inline"></div>
<div style="font-family:arial,helvetica,sans-serif;display:inline"></div>
3
<div style="font-family:arial,helvetica,sans-serif;display:inline"></div>
<div style="font-family:arial,helvetica,sans-serif;display:inline"></div>
6
<div style="font-family:arial,helvetica,sans-serif;display:inline"></div>
<div style="font-family:arial,helvetica,sans-serif;display:inline"></div>
<div style="font-family:arial,helvetica,sans-serif;display:inline">
/ </div>
<div style="font-family:arial,helvetica,sans-serif;display:inline"></div>
D
<div style="font-family:arial,helvetica,sans-serif;display:inline"></div>
<div style="font-family:arial,helvetica,sans-serif;display:inline"></div>
4
<div style="font-family:arial,helvetica,sans-serif;display:inline"></div>
<div style="font-family:arial,helvetica,sans-serif;display:inline"></div>
6
<div style="font-family:arial,helvetica,sans-serif;display:inline"></div>
<div style="font-family:arial,helvetica,sans-serif;display:inline"></div>
5
<div style="font-family:arial,helvetica,sans-serif;display:inline"></div>
<div style="font-family:arial,helvetica,sans-serif;display:inline"></div>
9
<div style="font-family:arial,helvetica,sans-serif;display:inline"></div>
<div style="font-family:arial,helvetica,sans-serif;display:inline"></div>
5
<div style="font-family:arial,helvetica,sans-serif;display:inline"></div>
<div style="font-family:arial,helvetica,sans-serif;display:inline">
has a merit: it would adds a bit of complexity,
but would not<span style="color:rgb(34,34,34);font-family:arial,helvetica,sans-serif;font-size:13px;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial;float:none;display:inline"> require:</span></div>
</div>
<div>
<div style="font-family:arial,helvetica,sans-serif;display:inline"><span style="color:rgb(34,34,34);font-family:arial,helvetica,sans-serif;font-size:13px;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial;float:none;display:inline"><br>
</span></div>
</div>
<div>
<div style="font-family:arial,helvetica,sans-serif;display:inline"><span style="color:rgb(34,34,34);font-family:arial,helvetica,sans-serif;font-size:13px;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial;float:none;display:inline">1.
a major rewrite of instcombine,</span></div>
</div>
<div>
<div style="font-family:arial,helvetica,sans-serif;display:inline"><span style="color:rgb(34,34,34);font-family:arial,helvetica,sans-serif;font-size:13px;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial;float:none;display:inline">2.
writing multiple (potentially many)
reassociate passes and figuring out how to
fixpoint them with instcombine, <span style="color:rgb(34,34,34);font-family:arial,helvetica,sans-serif;font-size:13px;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial;float:none;display:inline">or</span></span></div>
</div>
<div>
<div style="font-family:arial,helvetica,sans-serif;display:inline"><span style="color:rgb(34,34,34);font-family:arial,helvetica,sans-serif;font-size:13px;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial;float:none;display:inline"><span style="color:rgb(34,34,34);font-family:arial,helvetica,sans-serif;font-size:13px;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial;float:none;display:inline">3.
writing a self-contained folding pass for a
specific pattern</span></span></div>
</div>
<div>
<div style="font-family:arial,helvetica,sans-serif;display:inline"><span style="color:rgb(34,34,34);font-family:arial,helvetica,sans-serif;font-size:13px;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial;float:none;display:inline"><br>
</span></div>
</div>
<div>
<div style="font-family:arial,helvetica,sans-serif;display:inline"><span style="color:rgb(34,34,34);font-family:arial,helvetica,sans-serif;font-size:13px;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial;float:none;display:inline">If
you look at the diffs in the existing .ll
files in </span></div>
<font face="arial, helvetica, sans-serif">D46336
<div style="font-family:arial,helvetica,sans-serif;display:inline">,
it helps fold some previously-unfolded <span style="color:rgb(34,34,34);font-family:arial,helvetica,sans-serif;font-size:13px;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial;float:none;display:inline">reassociat<wbr>ion
patterns beyond the bit check patterns that
it originally targeted.</span></div>
</font></div>
</div>
<div><br>
</div>
</div>
</div>
</blockquote>
<div>Sure, and it does so by adding another O(N) cost to
evaluation in each case. Instcombine doesn't even do lazy
reevaluation through tracking dependencies, so it'll do so
a lot of times as well.</div>
<div><br>
</div>
<div>To me, that's not a good tradeoff, especially given how
slow instcombine is *already*. The code it produces is
"good enough" to stop for a while and do something else
and not suffer horribly in performance.[1]</div>
<div><br>
</div>
<div>Let me ask a different question:<br>
<br>
</div>
<div>At what point would anyone here be willing to stop
adding things to instcombine and start doing something
else instead, instead of waiting for someone else to do
it?</div>
<div>As far as i can tell, the answer is: "never", which
makes most of these discussions just pointless rehashes as
we slowly repeat the same disaster that became gcc's
instruction combiner :)</div>
<div><br>
</div>
<div>If the answer is "something", great, i'll set a mail
filter and ignore these threads until that something
happens :)</div>
<div><br>
</div>
<div>Personally, in my experience people will never do more
here unless pushed somewhat, or the thing becomes such a
complete disaster no one wants to touch it.</div>
</div>
</div>
</div>
</blockquote>
<br>
I've said this before, but I think a major impediment to forward
progress here is coming up with an agreement on what the "something
else" should be. Some of us have talked for years about having some
TableGen-driven replacement, or maybe we want something with a
syntax more like what is used by the Alive tool, but regardless, in
order to gain in efficiency I suspect we need a model that is more
restrictive than more-or-less arbitrary C++ code, and so we should
pick a model and figure out how things might work.<br>
<br>
<blockquote type="cite">
<div dir="ltr">
<div class="gmail_extra">
<div class="gmail_quote">
<div><br>
</div>
<div>[1] Last year i computed the "improvement in
performance on applications" due to instcombine for a
bunch of google apps and open source apps that had easy to
use benchmarks (IE I isolated about two years of
instcombine changes and made them to a current compiler
piece by piece while measuring performance).</div>
<div>I also computed the compile time increase in single
instcombine passes over the same time period.</div>
<div><br>
</div>
<div>On x86, but the numbers basically said we were
basically gaining nearly nothing for high cost. IE our
drive for better looking output does not appear to
translate into any real gains that i can find. Either
improvements to other opts hid them, or they simply didn't
matter on the processors i tested on.</div>
<div><br>
</div>
<div>Certainly, apps/workloads/architectures may vary here,
and my goal is not to claim it's all worthless.</div>
<div>My actual goal in all of this was to get a sense of
whether my perspective on instcombine was still
"reasonable", not to do a true scientific exploration :)</div>
<div>I didn't have time/energy/etc to run it elsewhere, and
again, my goal was not to give certainty/try to give exact
percentages.</div>
</div>
</div>
</div>
</blockquote>
<br>
This also matches my experience, but I draw a somewhat different
lesson. I often tell application developers that *this* is why they
must file compiler bug reports. Waiting and assuming that someone
else will hit the same problem, and file the report, is a bad
strategy. I think that this is due to two things:<br>
<br>
1. As far as things go, the tail of the distribution is often
really long, and probability that the particular thing hampering one
piece of hot code is the same thing hampering another piece of hot
code is often small.<br>
<br>
2. We tend to add special cases instead of adding more-general
algorithms. The more-general work is often hard because figuring out
the cost modeling is often highly non-trivial. Also, when it's
finally done, the chances that the old special cases are removed is
also small (so we'll still accumulate cruft without specific
effort).<br>
<br></div></blockquote><div><br></div></div></div><div><div class="gmail_default" style="color:rgb(34,34,34);font-size:13px;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial;font-family:arial,helvetica,sans-serif">I don't have better or larger study results or data<span style="color:rgb(34,34,34);font-family:sans-serif;font-size:13px;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial;float:none;display:inline">, but for fixing some smaller but important enough performance degradations (often in microbenchmarks, but occasionally in larger settings) smaller compiler improvements<span> </span><span style="color:rgb(34,34,34);font-family:sans-serif;font-size:13px;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial;float:none;display:inline">(not necessarily in instcombine but around that level) </span>do seem to matter at least in individual contexts. It's not clear how much those actually mattered in a grander scheme of things, though.</span></div><div class="gmail_default" style="color:rgb(34,34,34);font-size:13px;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial;font-family:arial,helvetica,sans-serif"><br></div></div><div class="gmail_default" style="color:rgb(34,34,34);font-size:13px;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial;font-family:arial,helvetica,sans-serif">It sounds like we don't want to add to instcombine due to added cost/complexity, rearchitecting would be hard, it's not clear if incremental changes in instcombine did much per cost, which would make it harder to justify <span style="color:rgb(34,34,34);font-family:arial,helvetica,sans-serif;font-size:13px;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial;float:none;display:inline">rearchitecting it...</span></div><div class="gmail_default" style="color:rgb(34,34,34);font-size:13px;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial;font-family:arial,helvetica,sans-serif"><br></div><div class="gmail_default" style="color:rgb(34,34,34);font-size:13px;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial;font-family:arial,helvetica,sans-serif">What do people think of approaches like D41574 and D45842?</div><span class="gmail-"><div class="gmail_default" style="color:rgb(34,34,34);font-size:13px;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial;font-family:arial,helvetica,sans-serif"><br></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 bgcolor="#FFFFFF">
-Hal<br>
<br>
<blockquote type="cite">
<div dir="ltr">
<div class="gmail_extra">
<div class="gmail_quote">
<div><br>
</div>
<div>--Dan</div>
<div><br>
</div>
<div><br>
</div>
<div><br>
</div>
<div><br>
</div>
<div><br>
</div>
</div>
</div>
</div>
<br>
<fieldset class="gmail-m_596114956539797037gmail-m_7327146177040704443mimeAttachmentHeader"></fieldset>
<br>
<pre>______________________________<wbr>_________________
LLVM Developers mailing list
<a class="gmail-m_596114956539797037gmail-m_7327146177040704443moz-txt-link-abbreviated" href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>
<a class="gmail-m_596114956539797037gmail-m_7327146177040704443moz-txt-link-freetext" href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" target="_blank">http://lists.llvm.org/cgi-bin/<wbr>mailman/listinfo/llvm-dev</a>
</pre>
</blockquote>
<br>
<pre class="gmail-m_596114956539797037gmail-m_7327146177040704443moz-signature" cols="72">--
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory</pre>
</div>
</blockquote></span></div></div>
<br>______________________________<wbr>_________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a><br>
<a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/<wbr>mailman/listinfo/llvm-dev</a><br>
<br></blockquote></div><br></div>