Given a loop of the form:
double w[1024], x[1024], a[1024];
void f() {
for (unsigned i = 0; i < 1024-1; i++) {
w[i] += a[i];
x[i] += a[i+1];
}
}Currently GVN PRE creates a phi which feeds a[i+1] into the next
iteration.
Prior to this patch, this phi is reported as being 'unknown':
remark: loop not vectorized: value that could not be identified as
reduction is used outside the loop [-Rpass-analysis=loop-vectorize]
w[i] += a[i];
^The reason is that isFixedOrderRecurrence sees the store to w[i]
occurring before the read from a[i+1] and it knows nothing about how
these are related.
This patch introduces a query for the memory dependences of the phi
input. If the memory dependency analysis reports a nonlocal dependency,
then any memory instructions can be sunk past it.
NOTE: I'm putting this patch up for early comments. Some things I'm
currently continuing to look into: Does LoopVectorize need the
memory dependence analysis, or is there other infrastructure available
that can be reused? Can I find any examples of miscompiles and does it
have the desired benchmarking impact?
This patch depends on https://reviews.llvm.org/D137158 which adds the MemoryDependance infrastructure.
This condition is fairly weak and I think it might be possible to make more specific queries.
At the moment my understanding is that this should allow sinking of memory instructions if it can be shown that the Previous value doesn't depend on anything above it in the block.
Perhaps isFixedOrderRecurrence could handle more cases if TryToPushSinkCandidate could consider specifically whether Previous depends on the SinkCandidate. I'm hesitating because I don't want to accidentally introduce an expensive query.
I'd appreciate input on whether using the memory dependence checker here is appropriate before I consider making this more general.