making the new if-converter not mangle IR that is already vectorizer-friendly

[Abe <abe_skolnik at yahoo dot com>]

Dear all,

[Please feel free to skip to the second instance of "end of introductions"
 and read the introduction sections later or never.]


<personal introduction>

Hi!  My name is Abe.  Although I`m from New York City, I`ve been living in Texas for about 5 years now,
due to having been "sucked in" to Texas by Texas A&M University and staying in Texas for an excellent job
at the Samsung Austin R&D Center ["SARC"], where the compiler team of which I am a part is working on GCC.

</personal introduction>


<topic introduction>

As some of you already know, at SARC we are working on a new "if converter" to help convert
simple "if"-based blocks of code that appear inside loops into an autovectorizer-friendly form
that closely resembles the C ternary operator ["c ? x : y"].  GCC already has such a converter,
but it is off by default, in part because it is unsafe: if enabled, it can cause certain code
to be transformed in such a way that it malfunctions even though the non-converted code worked
just fine with the same inputs.  The new converter, originally by my teammate Sebastian Pop,
is safer [almost-always safe *]; we are working on getting it into good-enough shape that the
always-safe transformations can be turned on by default whenever the autovectorizer is on.

* Always safe for stores, sometimes a little risky for loads:
  speculative loads might cause multithreaded programs with
  insufficient locking to fail due to writes by another thread
  being "lost"/"missed", even though the same program works OK
  "by luck" when compiled without if-conversion of loads.
  This risk comes mainly/only from what the relevant literature
  calls a "half hammock": an "if" with a "then" section but no
  "else" section [or effectively vice-versa, e.g. an empty "then"
  and a non-empty "else"].  In this case, e.g. "if (c)  X[x] = Y[y];"
  with no attached "else" section is risky to fully if-convert
  in the event of the code being compiled running multithreaded
  and not having been written with all the locking it really needs.
  Respectively, e.g. "if (c)  ; /* empty ''then'' */  else  X[x] = Y[y];".

</topic introduction>


[end of introductions]


<new business>

One of the reasons the new if converter has not yet been submitted
for incorporation into GCC`s trunk is that it still has some
performance regressions WRT the old converter, and most of those
are "true regressions", i.e. not just because the old converter
was less safe and the additional safety is what is causing the loss,
but rather because there is more work to do before the patch is ready.

As of this writing, the new if converter sometimes tries
to "convert" something that is already vectorizer-friendly,
and in doing so it renders that code now-NOT-vectorizer-friendly.
I think this is the first class of true regression that I should fix.
The question is how to do so.

My first choice was to try to have the if converter ask the vectorizer
"is this code already vectorizable?", but that seems to not be feasible.

The second choice is to use loop versioning to defer the decision to the vectorizer itself.
In other words, when the if converter sees what it "thinks" is an opportunity to convert
a loop, it will duplicate that loop inside a new "if" and convert exactly one of the
duplicates, producing something like this:

  if (__vectorizable_0001__) {
    /* if-converted loop */
  } else {
    /* original     loop */
  }

Under this plan, the vectorizer will be modified to detect code such as the above,
and when appropriate will check to see if the if-converted code is vectorizable,
then replacing e.g. "__vectorizable_0001__" with either (0) or (1) as per the check,
thus allowing dead-code elimination to clean up the temporary mess.

Sebastian has suggested that we add something like "tree ifConversion_condition;"
to "struct loop" so that we can keep track of e.g. "__vectorizable_0001__"
and use it in the vectorizer.  When there is no relevant conversion,
this field will be set to null.  This seems like a good plan to me.

I/we seek your feedback on the above.

</new business>


Regards,

Abe