[loop vectorizer] Auto vectorisation breaks because of bug in alias analysis.

Quuxplusone commented 5 years ago


Bugzilla Link	PR43161
Status	NEW
Importance	P normal
Reported by	Emmanouil Michalainas (manolismih@windowslive.com)
Reported on	2019-08-29 01:14:41 -0700
Last modified on	2019-08-31 15:56:57 -0700
Version	9.0
Hardware	PC Linux
CC	ashutosh.nema@amd.com, florian_hahn@apple.com, hfinkel@anl.gov, htmldeveloper@gmail.com, llvm-bugs@lists.llvm.org, llvm@meinersbur.de, manolismih@windowslive.com, neeilans@live.com, richard-llvm@metafoo.co.uk
Fixed by commit(s)
Attachments	`bug.cxx` (1430 bytes, text/x-c++src)
Blocks
Blocked by
See also

Created attachment 22446
Code posted on godbolt

Hello, could you please have a look at this code posted on godbolt.org:
https://godbolt.org/z/O-O-Q7
(code also attached in case godbolt link breaks)

The problem is that inside the compute function, only the first loop vectorizes
while the rest copies of it don't. But if I remove any of the for loops, then
the rest vectorize successfully. The message "Cannot identify array bounds" is
not helpful.

Quuxplusone commented 5 years ago

Attached bug.cxx (1430 bytes, text/x-c++src): Code posted on godbolt

Quuxplusone commented 5 years ago

Discussion from llvm-dev mailing lists about this issue:

Reply from Nema, Ashutosh

"""
Seems like when you comment out a loop in “compute” function, it gets inlined,
this helps LV by finding the bounds and vectorizes it.

With the presence of all the loops LAA is not able to identify the bounds for
the accesses:

LAA: Can't find bounds for ptr:  %arrayidx.i159 = getelementptr inbounds
double, double* %30, i64 %and.i158, !dbg !46

LAA: Can't find bounds for ptr:  %arrayidx.i155 = getelementptr inbounds
double, double* %36, i64 %and.i154, !dbg !66

LAA: Can't find bounds for ptr:  %arrayidx.i151 = getelementptr inbounds
double, double* %42, i64 %and.i150, !dbg !91

Its bit strange as its able to identify the bounds correctly for the first loop.

////////////////////////////////////////////////////////////////////////////////
Reply from Michael Kruse

"""
There is some weird interaction between alias-analysis and the
vectorized code. For the first loop, alias-analysis is able to
determine that "output" is not aliasing with the read-only arrays:

LAA: Processing memory accesses...
  AST: Alias Set Tracker: 2 alias sets for 7 pointer values.
  AliasSet[0x16a131c3120, 1] must alias, No access Pointers: (double*
%arrayidx6, unknown)
  AliasSet[0x16a131c1e90, 6] may alias, No access Pointers: (double*
%arrayidx, unknown), (double* %arrayidx1, unknown), (double**
%_pointer.i, unknown), (i64* %_mask.i, unknown), (double* %arrayidx.i,
unknown), (double* %arrayidx5, unknown)

After vectorizing the first loop, it is not able to do this anymore
(did not investigate the why). When trying to vectorize the second
loop, it requires a runtime condition to guard against aliasing (for
which it needs to determine the loop bounds), but is unable to do so
because of the the and-mask of "G"/BracketAdapterWithMask:
%arrayidx.i159  --- or as SCEV: ((8 * %and.i158)<nsw> + %36)<nsw>

When removing one of the for-loops, the entire compute-function is
inlined into the run function and this problem is magically resolved.
Not sure why.

Would you file a bug report?

Quuxplusone / LLVMBugzillaTest

[loop vectorizer] Auto vectorisation breaks because of bug in alias analysis. #42131