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

[Abe <abe_skolnik at yahoo dot com>]

[Alan wrote:]

> My understanding is that any decision as to whether one or both of y or z is evaluated (when 'evaluation' involves doing any work,
> e.g. a load), has already been encoded into the gimple/tree IR. Thus, if we are to only evaluate one of 'y' or 'z' in your example,
> the IR will (prior to if-conversion), contain basic blocks and control flow, that means we jump around the one that's not evaluated.

> This appears to be the case in pr61194.c: prior to if-conversion, the IR for the loop in barX is

>   <bb 3>:
>    # i_16 = PHI <i_13(7), 0(2)>
>    # ivtmp_21 = PHI <ivtmp_20(7), 1024(2)>
>    _5 = x[i_16];
>    _6 = _5 > 0.0;
>    _7 = w[i_16];
>    _8 = _7 < 0.0;
>    _9 = _6 & _8;
>    if (_9 != 0)
>      goto <bb 4>;
>    else
>      goto <bb 5>;
>
>    <bb 4>:
>    iftmp.0_10 = z[i_16];
>    goto <bb 6>;
>
>    <bb 5>:
>    iftmp.0_11 = y[i_16];

[snip]


[note: the following section, until the next quoted line, is mostly an explanation
 of if conversion and its trade-offs; please feel free to skip it or to read it later]


OK, but that`s overly-conservative in this case for most/all modern high-speed processors: "z[i]" and "y[i]" are both pure expressions and
the possible values of 'i' here [given that the hardware doesn`t malfunction, nobody alters the value in a debugger, etc.] can be proven
to not overflow the bounds of the arrays.  With purity established and bounds-validity known to be OK, all we need to do is to evaluate
the "cost" of evaluating both expressions vs. that of inflicting a conditional branch on the hardware.  I believe this "cost" depends on the
values in the arrays 'x' and 'w', but when the probability of either case -- "((x[i]>0) & (w[i]<0))" is true or is false -- is very close to
50% for a long time, the branch predictor is going to find it difficult to make any sense of it, and speculative execution is going to speculatively
execute the incorrect branch about 50% of the time until the data comes in that renders speculation no-longer-needed in the given iteration.

On most/all modern high-speed processors, doing the loads unconditionally is going to be better IMO for anything even remotely resembling a "normal"
or "average" workload.  In other words, so long as the result of "((x[i]>0) & (w[i]<0))" changes frequently and unpredictably as 'i' is incremented,
it should be better to do both loads: the needed data are in cache lines that are already in cache, possibly even in L1 data cache, so it`s pretty
"cheap" to just load them.  Conditional branches based on difficult-to-predict data that changes frequently [as the arrays are traversed],
OTOH, are likely to cause stalls and result in slower execution than the fastest possible on that CPU for the source code in question.

In cases where the data upon which the condition depends lead to mostly-true or mostly-false results,
the conditional branch should perform well for enough-iterations loops on any CPU with a decent branch predictor,
but those are rare conditions IMO.  I think we should assume random data in the arrays unless/until we have analysis that tells
us otherwise, and I don`t expect much compile-time analysis of the contents of arrays to become the norm in compilers anytime soon.
These are probably extremely-infrequent corner cases anyway, with the possible exception of the processing of sparse matrices;
does anybody reading this with a strong background in numerical/scientific computing have anything to comment on this?

Predication of instructions can help to remove the burden of the conditional branch, but is not available on all relevant architectures.
In some architectures that are typically implemented in modern high-speed processors -- i.e. with high core frequency, caches, speculative execution, etc. --
there is not full support for predication [as there is, for example, in 32-bit ARM] but there _is_ support for "conditional move" [hereinafter "cmove"].
If/when the ISA in question supports cmove to/from main memory, perhaps it would be profitable to use two cmoves back-to-back with opposite conditions
and the same register [destination for load, source for store] to implement e.g. "temp = c ? X[x] : Y[y]" and/or "temp = C[c] ? X[x] : Y[y]" etc.
Even without cmove to/from main memory, two cmoves back-to-back with opposite conditions could still be used, e.g. [not for a real-world ISA]:
  load X[x] -> reg1
  load Y[y] -> reg2
  cmove   c  ? reg1 -> reg3
  cmove (!c) ? reg2 -> reg3

Or even better if the ISA can support something like:
  load X[x] -> reg1
  load Y[y] -> reg2
  cmove (c ? reg1 : reg2) -> reg3

However, this is a code-gen issue from my POV, and at the present time all the if-conversion work is occurring at the GIMPLE level.
If anybody reading this knows how I could make the if converter generate GIMPLE that leads to code-gen that is better for at
least one ISA and the change[s] do/does not negatively impact upon code-gen for any other ISA, I`d be glad to read about it.


> Without -ftree-loop-if-convert-stores, if-conversion leaves this alone, and vectorization fails  (i.e. the vectorizer
> bails out because the loop has >2 basic blocks). With -ftree-loop-if-convert-stores, if-conversion produces
[snip]
> where I have commented the conditional loads that have become unconditional.
> (Hence, "-ftree-loop-if-convert-stores" looks misnamed - it affects how the if-conversion phase converts loads,
> too - please correct me if I misunderstand (Richard?) ?!) This contains no control flow, and so is vectorizable.
[snip]
> (This is all without your scratchpad patch, of course.)

I think the preceding is quite correct.

Sebastian and I have discussed [at some length, on my part ;-)] what to do about the flags.  We definitely want them to change.
We might wind up with a different number of flags, i.e. not just rename one or both of the two we currently have.

Does anybody know of any large codebase that depends heavily on the current flags?
AFAIK these have been infrequently-if-ever used so far in production code.


Regards,

Abe