<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=""><br class=""><div><br class=""><blockquote type="cite" class=""><div class="">On May 11, 2018, at 7:20 PM, Hal Finkel via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" class="">llvm-dev@lists.llvm.org</a>> wrote:</div><br class="Apple-interchange-newline"><div class="">
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" class="">
<div text="#000000" bgcolor="#FFFFFF" class="">
<br class="">
<div class="moz-cite-prefix">On 05/11/2018 08:40 PM, Daniel Berlin
via llvm-dev wrote:<br class="">
</div>
<blockquote type="cite" cite="mid:CAF4BwTUPWHKkJHBMx_Prrk7qMdSSdAOE2YZxXiD-fzLS-O92GQ@mail.gmail.com" class="">
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" class="">
<div dir="ltr" class=""><br class="">
<div class="gmail_extra"><br class="">
<div class="gmail_quote">On Fri, May 11, 2018 at 2:37 PM,
Hiroshi Yamauchi <span dir="ltr" class=""><<a href="mailto:yamauchi@google.com" target="_blank" moz-do-not-send="true" class="">yamauchi@google.com</a>></span>
wrote:<br class="">
<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" class="">
<div style="font-family:arial,helvetica,sans-serif" class=""><br class="">
</div>
<br class="">
<div class="gmail_quote">
<div class="">
<div class="gmail-m_2423541276025245453h5">
<div dir="ltr" class="">On Thu, May 10, 2018 at 12:49 PM
Daniel Berlin <<a href="mailto:dberlin@dberlin.org" target="_blank" moz-do-not-send="true" class="">dberlin@dberlin.org</a>>
wrote:<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 dir="ltr" class=""><br class="">
<div class="gmail_extra"><br class="">
<div class="gmail_quote">On Thu, May 10,
2018 at 12:05 PM, Hiroshi Yamauchi <span dir="ltr" class=""><<a href="mailto:yamauchi@google.com" target="_blank" moz-do-not-send="true" class="">yamauchi@google.com</a>></span>
wrote:<br class="">
<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" class="">
<div style="font-family:arial,helvetica,sans-serif" class=""><br class="">
</div>
<br class="">
<div class="gmail_quote"><span class="">
<div dir="ltr" class="">On Wed, May 9, 2018
at 8:24 PM Daniel Berlin <<a href="mailto:dberlin@dberlin.org" target="_blank" moz-do-not-send="true" class="">dberlin@dberlin.org</a>>
wrote:<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 dir="ltr" class=""><br class="">
<div class="gmail_extra"><br class="">
<div class="gmail_quote">On
Wed, May 9, 2018 at 10:39
AM, Hiroshi Yamauchi <span dir="ltr" class=""><<a href="mailto:yamauchi@google.com" target="_blank" moz-do-not-send="true" class="">yamauchi@google.com</a>></span>
wrote:<br class="">
<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" class="">
<div style="font-family:arial,helvetica,sans-serif" class=""><br class="">
</div>
<br class="">
<div class="gmail_quote"><span class="gmail-m_2423541276025245453m_-9018700274548918466gmail-m_2085822097580644453m_402989712542517733gmail-m_8307257963026143428gmail-">
<div dir="ltr" class="">On
Tue, May 8, 2018
at 11:15 AM
Daniel Berlin
<<a href="mailto:dberlin@dberlin.org" target="_blank" moz-do-not-send="true" class="">dberlin@dberlin.org</a>>
wrote:<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 dir="ltr" class=""><br class="">
<div class="gmail_extra"><br class="">
<div class="gmail_quote">On
Tue, May 8,
2018 at 10:38
AM, Hiroshi
Yamauchi via
llvm-dev <span dir="ltr" class=""><<a href="mailto:llvm-dev@lists.llvm.org" target="_blank" moz-do-not-send="true" class="">llvm-dev@lists.llvm.org</a>></span>
wrote:<br class="">
<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" class="">(
<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" class="">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" class=""> </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" moz-do-not-send="true" class="">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" class="">.</span>
<div style="font-family:arial,helvetica,sans-serif;display:inline" class="">
</div>
Thanks,
Sanjay, for
starting this
discussion.)<br class="">
<div class=""><br class="">
</div>
<div class="">If
<div style="font-family:arial,helvetica,sans-serif;display:inline" class="">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" class="">
<div style="font-family:arial,helvetica,sans-serif;display:inline" class="">reassociation, </div>
</span>or keep
additional
ones
<div style="font-family:arial,helvetica,sans-serif;display:inline" class="">,</div>
out of
instcombine,
<div style="font-family:arial,helvetica,sans-serif;display:inline" class="">open
questions for
me would be</div>
<div style="font-family:arial,helvetica,sans-serif;display:inline" class="">:</div>
<br class="">
<br class="">
1. Since
-reassociate
isn't a fixed
point pass,</div>
</div>
</blockquote>
<div class=""><br class="">
</div>
<div class="">This is
fixable, fwiw,
without
fixpointing
it.</div>
</div>
</div>
</div>
</blockquote>
<div class=""><br class="">
</div>
</span>
<div class="">
<div style="font-family:arial,helvetica,sans-serif" class="">How?</div>
</div>
</div>
</div>
</blockquote>
<div class=""><br class="">
</div>
<div class="">Depends on
specifically which part
you would like to know
about ;)</div>
</div>
</div>
</div>
</blockquote>
<div class=""><br class="">
</div>
</span>
<div class="">
<div style="font-family:arial,helvetica,sans-serif" class="">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" class="">the
specific motivating examples
from the above differentials
are foldable without
fixpointing?</span></div>
</div>
</div>
</div>
</blockquote>
<div class=""><br class="">
</div>
<div class="">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 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 dir="ltr" class="">
<div class="gmail_quote">
<div style="font-family:arial,helvetica,sans-serif" class=""><br class="">
</div>
<div style="font-family:arial,helvetica,sans-serif" class=""><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" class="">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" class="">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" class="">probably </span>need
some pass management change.</span></span></div>
<div class="">
<div class="gmail-m_2423541276025245453m_-9018700274548918466gmail-m_2085822097580644453h5">
<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 dir="ltr" class="">
<div class="gmail_extra">
<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 dir="ltr" class="">
<div class="gmail_quote"><span class="gmail-m_2423541276025245453m_-9018700274548918466gmail-m_2085822097580644453m_402989712542517733gmail-m_8307257963026143428gmail-">
<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 dir="ltr" class="">
<div class="gmail_extra">
<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 dir="ltr" class="">
<div class=""> we might
need to repeat
"-instcombine
-reassociate"
multiple times
to
<div style="font-family:arial,helvetica,sans-serif;display:inline" class="">fold</div>
down to what
we want
(relating to <a href="https://reviews.llvm.org/D46336#1087082" target="_blank" moz-do-not-send="true" class="">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" class="">?
My impression
is we don't do
a fixed-point
with passes?</div>
</div>
</div>
</blockquote>
<div class=""><br class="">
</div>
<div class="">Well, i
mean there is
no practical
difference
between passes
that we
fixpoint
externally and
fixpoint
internally.</div>
</div>
</div>
</div>
</blockquote>
</span>
<div class="">
<div style="font-family:arial,helvetica,sans-serif" class=""></div>
<div style="font-family:arial,helvetica,sans-serif" class=""><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" class="">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" class=""><br class="">
</div>
<div style="font-family:arial,helvetica,sans-serif" class="">But
if <span style="font-family:sans-serif" class="">there
is no
practical
difference</span>,
I don't see
any problem
with that :)</div>
</div>
<span class="gmail-m_2423541276025245453m_-9018700274548918466gmail-m_2085822097580644453m_402989712542517733gmail-m_8307257963026143428gmail-">
<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 dir="ltr" class="">
<div class="gmail_extra">
<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 dir="ltr" class="">
<div class=""> <br class="">
</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" class="">
<div class="">2.
<div style="font-family:arial,helvetica,sans-serif;display:inline" class="">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" class="">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" class="">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" class=""><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" class="">reassociative/commutative</span>
foldings that
we want? </span></span></div>
</div>
</div>
</blockquote>
<div class=""><br class="">
</div>
<div class="">In what
way?</div>
<div class="">Are you
asking whether
there is a
single
reassociation
order that
makes all
foldings occur
in the same
operation or
something?<br class="">
I don't feel
like i
understand
what you are
asking.<br class="">
</div>
</div>
</div>
</div>
</blockquote>
<div class=""><br class="">
</div>
</span>
<div class="">
<div class=""><span style="font-family:arial,helvetica,sans-serif" class="">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" class="">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" class="">reassociation
orders to fold
different
patterns?</span></span></span></div>
</div>
<span class="gmail-m_2423541276025245453m_-9018700274548918466gmail-m_2085822097580644453m_402989712542517733gmail-m_8307257963026143428gmail-"></span></div>
</div>
</blockquote>
<div class=""><br class="">
</div>
<div class="">It doesn't quite
help.</div>
<div class="">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 class=""><br class="">
</div>
<div class="">There is however, a
different question and
answer to a few
related problems that
maybe you are really
asking?<br class="">
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 class=""><br class="">
</div>
<div class="">(see, e.g., <a href="http://www.cs.cornell.edu/%7Eross/publications/eqsat/" target="_blank" moz-do-not-send="true" class="">http://www.cs.cornell.ed<wbr class="">u/~ross/publications/eqsat/</a>)</div>
<div class=""><br class="">
</div>
<div class="">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 class=""><br class="">
</div>
<div class="">(not a single easy
link, happy to talk
about it)</div>
<div class=""><br class="">
</div>
<div class="">Your original
question is basically
equivalent to</div>
<div class="">
<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" class="">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" class="">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" class=""><br class="">
</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" class="">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" class=""><br class="">
</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" class="">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" class=""><br class="">
</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" class=""><br class="">
</div>
</div>
</div>
</div>
</div>
</blockquote>
<div class=""><span style="font-family:arial,helvetica,sans-serif" class=""></span></div>
</div>
</div>
<div class="">
<div class=""><font face="arial, helvetica,
sans-serif" class="">Let me try one
more time :) </font><span style="font-family:arial,helvetica,sans-serif" class="">May
we need multiple reassociate
passes to fold different </span><span style="font-family:arial,helvetica,sans-serif" class="">reassociative patterns?</span></div>
<div class=""><font face="arial, helvetica,
sans-serif" class=""><br class="">
</font></div>
<div class=""><font face="arial, helvetica,
sans-serif" class="">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" class="">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" class="">pattern</span>
to be folded (</span><font face="arial, helvetica,
sans-serif" class="">D41574)</font><span style="font-family:arial,helvetica,sans-serif" class="">, and I want yet another </span><font face="arial, helvetica,
sans-serif" class=""></font><span style="font-family:arial,helvetica,sans-serif" class="">particular </span><span style="font-family:arial,helvetica,sans-serif" class="">reassociat<wbr class="">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" class="">pattern</span>
to be folded (</span><font face="arial, helvetica,
sans-serif" class="">D46336)</font><span style="font-family:arial,helvetica,sans-serif" class="">, 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" class="">somehow </span>handle
those cases in one shot,
(assuming we don't want to put
those in instcombine)?</span></div>
<div class=""><span style="font-family:arial,helvetica,sans-serif" class=""><br class="">
</span></div>
<div class=""><span style="font-family:arial,helvetica,sans-serif" class="">And
it sounds like the answer is
yes?</span></div>
</div>
</div>
</div>
</blockquote>
<div class=""><br class="">
</div>
<div class="">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" class="">
<div class="gmail_extra">
<div class="gmail_quote">
<div class="">
<div style="font-family:arial,helvetica,sans-serif;display:inline" class=""></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 class="">
<div style="font-family:arial,helvetica,sans-serif" class=""><br class="">
</div>
</div>
</div>
</div>
<div style="font-family:arial,helvetica,sans-serif" class="">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" class="">rearchitect,
you mean a major rewrite as per this comment</span><span style="font-family:sans-serif" class="">: </span><span style="font-family:sans-serif" class="">"</span><span style="font-family:sans-serif" class="">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" class="">Any pointer or time
to chat?</span></div>
</div>
</div>
</blockquote>
<div class=""><br class="">
</div>
<div class="">I'm happy to do both.</div>
<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 dir="ltr" class="">
<div class="gmail_quote">
<div style="font-family:arial,helvetica,sans-serif" class=""></div>
<div class="">
<div class="">
<div style="font-family:arial,helvetica,sans-serif;display:inline" class="">I
think that an approach like </div>
D
<div style="font-family:arial,helvetica,sans-serif;display:inline" class=""></div>
<div style="font-family:arial,helvetica,sans-serif;display:inline" class=""></div>
4
<div style="font-family:arial,helvetica,sans-serif;display:inline" class=""></div>
<div style="font-family:arial,helvetica,sans-serif;display:inline" class=""></div>
6
<div style="font-family:arial,helvetica,sans-serif;display:inline" class=""></div>
<div style="font-family:arial,helvetica,sans-serif;display:inline" class=""></div>
3
<div style="font-family:arial,helvetica,sans-serif;display:inline" class=""></div>
<div style="font-family:arial,helvetica,sans-serif;display:inline" class=""></div>
3
<div style="font-family:arial,helvetica,sans-serif;display:inline" class=""></div>
<div style="font-family:arial,helvetica,sans-serif;display:inline" class=""></div>
6
<div style="font-family:arial,helvetica,sans-serif;display:inline" class=""></div>
<div style="font-family:arial,helvetica,sans-serif;display:inline" class=""></div>
<div style="font-family:arial,helvetica,sans-serif;display:inline" class="">
/ </div>
<div style="font-family:arial,helvetica,sans-serif;display:inline" class=""></div>
D
<div style="font-family:arial,helvetica,sans-serif;display:inline" class=""></div>
<div style="font-family:arial,helvetica,sans-serif;display:inline" class=""></div>
4
<div style="font-family:arial,helvetica,sans-serif;display:inline" class=""></div>
<div style="font-family:arial,helvetica,sans-serif;display:inline" class=""></div>
6
<div style="font-family:arial,helvetica,sans-serif;display:inline" class=""></div>
<div style="font-family:arial,helvetica,sans-serif;display:inline" class=""></div>
5
<div style="font-family:arial,helvetica,sans-serif;display:inline" class=""></div>
<div style="font-family:arial,helvetica,sans-serif;display:inline" class=""></div>
9
<div style="font-family:arial,helvetica,sans-serif;display:inline" class=""></div>
<div style="font-family:arial,helvetica,sans-serif;display:inline" class=""></div>
5
<div style="font-family:arial,helvetica,sans-serif;display:inline" class=""></div>
<div style="font-family:arial,helvetica,sans-serif;display:inline" class="">
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" class=""> require:</span></div>
</div>
<div class="">
<div style="font-family:arial,helvetica,sans-serif;display:inline" class=""><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" class=""><br class="">
</span></div>
</div>
<div class="">
<div style="font-family:arial,helvetica,sans-serif;display:inline" class=""><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" class="">1.
a major rewrite of instcombine,</span></div>
</div>
<div class="">
<div style="font-family:arial,helvetica,sans-serif;display:inline" class=""><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" class="">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" class="">or</span></span></div>
</div>
<div class="">
<div style="font-family:arial,helvetica,sans-serif;display:inline" class=""><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" class=""><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" class="">3.
writing a self-contained folding pass for a
specific pattern</span></span></div>
</div>
<div class="">
<div style="font-family:arial,helvetica,sans-serif;display:inline" class=""><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" class=""><br class="">
</span></div>
</div>
<div class="">
<div style="font-family:arial,helvetica,sans-serif;display:inline" class=""><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" class="">If
you look at the diffs in the existing .ll
files in </span></div>
<font face="arial, helvetica, sans-serif" class="">D46336
<div style="font-family:arial,helvetica,sans-serif;display:inline" class="">,
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" class="">reassociat<wbr class="">ion
patterns beyond the bit check patterns that
it originally targeted.</span></div>
</font></div>
</div>
<div class=""><br class="">
</div>
</div>
</div>
</blockquote>
<div class="">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 class=""><br class="">
</div>
<div class="">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 class=""><br class="">
</div>
<div class="">Let me ask a different question:<br class="">
<br class="">
</div>
<div class="">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 class="">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 class=""><br class="">
</div>
<div class="">If the answer is "something", great, i'll set a mail
filter and ignore these threads until that something
happens :)</div>
<div class=""><br class="">
</div>
<div class="">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 class="">
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 class="">
<br class="">
<blockquote type="cite" cite="mid:CAF4BwTUPWHKkJHBMx_Prrk7qMdSSdAOE2YZxXiD-fzLS-O92GQ@mail.gmail.com" class="">
<div dir="ltr" class="">
<div class="gmail_extra">
<div class="gmail_quote">
<div class=""><br class="">
</div>
<div class="">[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 class="">I also computed the compile time increase in single
instcombine passes over the same time period.</div>
<div class=""><br class="">
</div>
<div class="">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 class=""><br class="">
</div>
<div class="">Certainly, apps/workloads/architectures may vary here,
and my goal is not to claim it's all worthless.</div>
<div class="">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 class="">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 class="">
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 class="">
<br class="">
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 class="">
<br class="">
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 class=""></div></div></blockquote>My experience is also exactly like this. We keep adding new patterns to inst-combine, but nothing has been done yet to modularize or somehow partition it to reduce the costs we need to pay for these new patterns. Inst-combine is scheduled to run 8 times in the current O2/Os pipelines and 9 times in O3. In most applications the new patterns will probably never even trigger, but we will check for them at least 8 times. It’s more or less acceptable for O3, where we’re supposed to try squeezing as much optimizations as possible, but for O2 and Os it doesn’t sound reasonable to me.</div><div><br class=""></div><div>Recently AggressiveInstCombine pass has been added and probably some of the patterns might go there to slightly reduce the costs, but a bigger rethink might be needed in this area anyway. I’d be glad to help doing this if we agree on a general direction we want to go.</div><div><br class=""></div><div>Michael<br class=""><blockquote type="cite" class=""><div class=""><div text="#000000" bgcolor="#FFFFFF" class="">
<br class="">
-Hal<br class="">
<br class="">
<blockquote type="cite" cite="mid:CAF4BwTUPWHKkJHBMx_Prrk7qMdSSdAOE2YZxXiD-fzLS-O92GQ@mail.gmail.com" class="">
<div dir="ltr" class="">
<div class="gmail_extra">
<div class="gmail_quote">
<div class=""><br class="">
</div>
<div class="">--Dan</div>
<div class=""><br class="">
</div>
<div class=""><br class="">
</div>
<div class=""><br class="">
</div>
<div class=""><br class="">
</div>
<div class=""><br class="">
</div>
</div>
</div>
</div>
<br class="">
<fieldset class="mimeAttachmentHeader"></fieldset>
<br class="">
<pre wrap="" class="">_______________________________________________
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="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a>
</pre>
</blockquote>
<br class="">
<pre class="moz-signature" cols="72">--
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory</pre>
</div>
_______________________________________________<br class="">LLVM Developers mailing list<br class=""><a href="mailto:llvm-dev@lists.llvm.org" class="">llvm-dev@lists.llvm.org</a><br class="">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev<br class=""></div></blockquote></div><br class=""></body></html>