This is the mail archive of the mailing list for the GCC project.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

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

On 7/2/15 4:30 AM, Alan Lawrence wrote:

Hi, pleased to meet you :)

Likewise.  :-)

[Abe wrote:]

* 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];".

[Alan wrote:]

For the unenlightened, can you outline the problem with this code sequence?
(i.e. the expected transformation that makes it unsafe!?)
I would hope your scratchpad patch would turn this into something like

a1 = c ? &Y[y] : &scratch;
temp = *a1;
a2 = c ? &X[x] : &scratch;
*a2 = temp;

which seems OK to me

Yes, you are right.  The problem I was thinking about is not present in the above:
in the "'c' is false" case, the vectorized code for the above just wastes some effort
by reading garbage from the scratchpad and writing it back to the scratchpad.

so is the scratchpad approach going away?

Not at all.  :-)

My example[s] was/were not written well with regard to expressing what I had in mind.
The problem I was thinking about is shown with a scalar destination, e.g.:

  if (c)  foo = X[x];

... which is if-converted into the equivalent of:

  foo = c ? X[x] : foo;

The [perceived/potential] problem with the preceding is that the part that is equivalent to "foo = foo;"
in the above can _not_ be optimized out, as it normally would for a non-"volatile" "foo",
because it is part of a larger vectorized operation and this small part cannot be broken out of the whole
without breaking vectorization.  Therefore, the value of "foo" might be read and then written back
a few {micro|nano|pico|whatever}-seconds later, which may cause an update to the same location to be overwritten.
That`s why the pathological program-under-compilation is a badly-written multithreaded program without enough locking:
without the "if something, then overwrite" being replaced by "read, then if something then write the new value,
and if not that same something then rewrite the old value", the badly-written multithreaded program might work correctly
through "good luck", but with the replacement [i.e. the if conversion] the chances of success
[where "success" here basically means not "missing" a write by another thread] is lower than it was before.

However, after some discussion with Sebastian I learned that this is already taken care of, i.e. safe:
the "read, then if something then write the new value, and if not that same something then rewrite the old value"
replacement strategy is only used for thread-local scalars.  For global scalars and static scalars,
we treat the scalar as if it were the first element of a length=1 array and don`t have this problem.

In other words, the problem about which I was concerned is not going to be triggered by e.g. "if (c)  x = ..."
which lacks an attached "else  x = ..." in a multithreaded program without enough locking just because 'x' is global/static.

The only remaining case to consider is if some code being compiler takes the address of something thread-local and then "gives"
that pointer to another thread.  Even for _that_ extreme case, Sebastian says that the gimplifier will detect this
"address has been taken" situation and do the right thing such that the new if converter also does the right thing.

TLDR: Abe was being too paranoid; to the best of our knowledge, it`s OK as-is.  ;-)

[Abe wrote:]

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.

[Alan wrote:]

Can you give an example?

The test cases in the GCC tree at "gcc.dg/vect/pr61194.c" and "gcc.dg/vect/vect-mask-load-1.c"
currently test as: the new if-converter is "converting" something that`s already vectorizer-friendly,
messing up the IR in the process and thus disabling vectorization for the test case in question.

My understanding was that the existing vectorizer bailed out pretty much straightaway
if the number of basic blocks in the loop was not exactly 2 (for inner loops) or 5
(for outermost loops, i.e. containing exactly one inner loop)...

I see nothing in that text that I know to be wrong.

that seems to rule out vectorization of *any* kind of
conditional execution, that the if-converter might convert?

If the converter takes something that`s already good [e.g. manually "converted"]
and doesn`t "understand" that the code is already good, it may analyze the code in question,
arrive at the conclusion "if-conversion candidate", and then "convert" it, making a mess in the process.
This mess, in turn, causes the vectorizer to arrive at the conclusion "NOT a vectorization candidate"
whereas without the incorrect "conversion" its conclusion would have been
"vectorization candidate" and it would have vectorized it.

However, TTBOMK the vectorizer already "understands" that in cases where its input looks like:

  x = c ? y : z;

... and 'y' and 'z' are both pure [side-effect-free] -- including, but not limited to, they must be non-"volatile" --
it may vectorize a loop containing code like the preceding, ignoring for this particular instance the C mandate
that only one of {y, z} be evaluated, depending on the value of 'c', since when both are truly pure expressions it`s only
at worst a waste of time/energy/both, not a semantics issue, and the vectorizer is either assuming that it`s worth it
to make the transformation due to the factors-level speedup of vectorization, or it is using a cost model
and arriving at the conclusion that for the loop in question, vectorization is worth it.

Normally, the code would not really look all that close to the preceding, but rather more like:

  X[x] = c ? Y[y] : Z[z];

... since if all the operands are scalars, it`s not very likely to be worth vectorizing, of course.

The code in the loop being vectorized might even look like:

  X[x] = C[c] ? Y[y] : Z[z];

... i.e. the condition could also be read from an array rather than from a scalar,
regardless of whether or not that scalar [in the previous example] is a compiler-generated temporary.

I hope the above is helpful.



Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]