<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>