<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
</head>
<body text="#000000" bgcolor="#FFFFFF">
<br>
<div class="moz-cite-prefix">On 05/11/2018 08:40 PM, Daniel Berlin
via llvm-dev wrote:<br>
</div>
<blockquote type="cite"
cite="mid:CAF4BwTUPWHKkJHBMx_Prrk7qMdSSdAOE2YZxXiD-fzLS-O92GQ@mail.gmail.com">
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<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"
moz-do-not-send="true">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_2423541276025245453h5">
<div dir="ltr">On Thu, May 10, 2018 at 12:49 PM
Daniel Berlin <<a
href="mailto:dberlin@dberlin.org"
target="_blank" moz-do-not-send="true">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" moz-do-not-send="true">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" moz-do-not-send="true">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"
moz-do-not-send="true">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_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" moz-do-not-send="true">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"
moz-do-not-send="true">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" moz-do-not-send="true">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_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_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"
moz-do-not-send="true">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_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_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"
moz-do-not-send="true">http://www.cs.cornell.ed<wbr>u/~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"
cite="mid:CAF4BwTUPWHKkJHBMx_Prrk7qMdSSdAOE2YZxXiD-fzLS-O92GQ@mail.gmail.com">
<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>
-Hal<br>
<br>
<blockquote type="cite"
cite="mid:CAF4BwTUPWHKkJHBMx_Prrk7qMdSSdAOE2YZxXiD-fzLS-O92GQ@mail.gmail.com">
<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="mimeAttachmentHeader"></fieldset>
<br>
<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="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a>
</pre>
</blockquote>
<br>
<pre class="moz-signature" cols="72">--
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory</pre>
</body>
</html>