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

Reply via email to