<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Jul 13, 2017 at 6:18 PM, Hal Finkel <span dir="ltr"><<a href="mailto:hfinkel@anl.gov" target="_blank">hfinkel@anl.gov</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 bgcolor="#FFFFFF"><span class="gmail-">
    <p><br>
    </p>
    <div class="gmail-m_6822423217570635499moz-cite-prefix">On 07/13/2017 06:40 PM, Daniel Berlin
      via llvm-dev wrote:<br>
    </div>
    <blockquote type="cite">
      
      <div dir="ltr">Ah yes, it can only return one instruction and you
        need two.
        <div><br>
          <div>
            <div>NewGVN could still handle it if instsimplify was
              changed to return the right binary operators because it
              has infrastructure that can handle insertion.<br>
            </div>
            <div>(it would need a little work).</div>
            <div><br>
            </div>
            <div><br>
            </div>
            <div>(At this point, InstCombine seems to have become worse
              to me than GCC's combining infrastructure, so i'd really
              like to see if we can stop putting things there.
              Otherwise, we just go farther down the path of 'let's
               just make everything one big graph rewrite)</div>
          </div>
        </div>
      </div>
    </blockquote>
    <br></span>
    Perhaps something of a digression:<br>
    <br>
    My general impression is that if InstCombine were actually doing a
    principled graph rewrite, then we wouldn't have these problems.</div></blockquote><div><br></div><div>Define "these problems"?<br><br></div><div>:)</div><div>I mean, you are right it would be better in general.   </div><div>But the notion of adding more and more graph rewrites to a single part of the compiler, to get second/third/etc order effects, is endless.  Pretty much everything can be expressed as a set of graph rewrites.  There is no principled stopping point.  IE You have to decide what you want each pass to do, and if you have one pass whose job is "perform all possible graph rewrites", that pass is in fact, your compiler :)</div><div><br></div><div>That's not such a bad thing, mind you, there are entire libraries/languages centered around this (see, e.g., stratego, <a href="https://en.wikipedia.org/wiki/Stratego/XT">https://en.wikipedia.org/wiki/Stratego/XT</a> and <a href="http://www.metaborg.org/en/latest/source/langdev/meta/lang/stratego/strategoxt/index.html">http://www.metaborg.org/en/latest/source/langdev/meta/lang/stratego/strategoxt/index.html</a>), but it should be a deliberate thing.</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div bgcolor="#FFFFFF">e
    problem we have, however, is that we have phase-ordering problems
    (even within the fixed-point iteration scheme): Patterns being
    matched depend on a canonical form, instructions nearly matching
    those patterns might be created, and then suboptimally consumed
    (i.e. further transformed), before being subject to the
    canonicalizing transformation(s) that would make the better pattern
    actually match.<br>
    <br>
    Except for TableGen'ing the whole thing, and making an actual graph
    automaton to match the patterns, it's not clear to me how to
    efficiently fix this </div></blockquote><div><br></div><div>That is what people used to do, make parsing grammars, etc.</div><div>Stratego is also  quite efficient at term rewriting, from what i remember.<br></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 bgcolor="#FFFFFF">. In the mean time, what we've been doing in
    practice, is that we have InstCombine patterns depend on canonical
    forms, until we hit some phase-ordering problem, and then we extend
    the pattern in question to match some non-canonical forms. We might
    do this here as well (if that's the problem here), but at some point
    I suspect we'll end up redoing everything.<br></div></blockquote><div><br></div><div>The question i would have is "how do you know when you are done?". As I said, pretty much everything can be expressed as a graph transform, and the more it gets added here, the more people want to run instcombine 50 times because cse/gvn/you name it "doesn't do what they want".</div><div><br></div></div></div></div>