[LICM] TSVC s113: not vectorized because LICM doesn't work

[yus3710-fj]

Flang can't vectorize the loop in s113 of TSVC while Clang can vectorize the loop written in C.

! Fortran version
      do 1 nl = 1,ntimes
      do 10 i = 2,n
        a(i) = a(1) + b(i)
   10 continue
      call dummy(ld,n,a,b,c,d,e,aa,bb,cc,1.)
   1  continue

// C version
for (int nl = 0; nl < ntimes; nl++) {
  for (int i = 1; i < n; i++) {
    a[i] = a[0] + b[i];
  }
  dummy(a, b, c, d, e, aa, bb, cc, 0.);
}

$ flang-new -v -Ofast s113.f -S -Rpass=licm\|vector -falias-analysis
flang-new version 18.0.0 (https://github.com/llvm/llvm-project.git 1c1227846425883a3d39ff56700660236a97152c)
Target: aarch64-unknown-linux-gnu
Thread model: posix
InstalledDir: /path/to/install/bin
Found candidate GCC installation: /path/to/lib/gcc/aarch64-unknown-linux-gnu/11.2.0
Selected GCC installation: /path/to/lib/gcc/aarch64-unknown-linux-gnu/11.2.0
Candidate multilib: .;@m64
Selected multilib: .;@m64
 "/path/to/install/bin/flang-new" -fc1 -triple aarch64-unknown-linux-gnu -S -fcolor-diagnostics -mrelocation-model pic -pic-level 2 -pic-is-pie -ffast-math -target-cpu generic -target-feature +neon -target-feature +v8a -fstack-arrays -fversion-loops-for-stride -falias-analysis -Rpass=vector -O3 -o s113.s -x f95-cpp-input s113.f
$ clang -Ofast s113.c -Rpass=licm\|vector
/path/to/s113.c:16:11: remark: hoisting load [-Rpass=licm]
   16 |                         a[i] = a[0] + b[i];
      |                                ^
/path/to/s113.c:15:3: remark: vectorized loop (vectorization width: 4, interleaved count: 2) [-Rpass=loop-vectorize]
   15 |                 for (int i = 1; i < LEN; i++) {
      |                 ^

It can be reproduced with the following C code which is the same program as the above C code essentially.

// C version
for (int nl = 0; nl < ntimes; nl++) {
  for (int i = 2; i <= n; i++) {
    a[i-1] = a[0] + b[i-1];
  }
  dummy(a, b, c, d, e, aa, bb, cc, 0.);
}

Actually, Flang generates LLVM IR like this C code.

LICM is necessary for vectorization because LoopAccessAnalysis can't analyze a[0] correctly.
It seems that LICM doesn't work due to the linear expression in indices of arrays.

[llvmbot]

@llvm/issue-subscribers-flang-ir

Author: Yusuke MINATO (yus3710-fj)

Flang can't vectorize the loop in `s113` of [TSVC](https://www.netlib.org/benchmark/vectors) while Clang can vectorize the loop written in C.

! Fortran version
      do 1 nl = 1,ntimes
      do 10 i = 2,n
        a(i) = a(1) + b(i)
   10 continue
      call dummy(ld,n,a,b,c,d,e,aa,bb,cc,1.)
   1  continue

// C version
for (int nl = 0; nl < ntimes; nl++) {
  for (int i = 1; i < n; i++) {
    a[i] = a[0] + b[i];
  }
  dummy(a, b, c, d, e, aa, bb, cc, 0.);
}

$ flang-new -v -Ofast s113.f -S -Rpass=licm\|vector
flang-new version 18.0.0 (https://github.com/llvm/llvm-project.git 1c1227846425883a3d39ff56700660236a97152c)
Target: aarch64-unknown-linux-gnu
Thread model: posix
InstalledDir: /path/to/install/bin
Found candidate GCC installation: /path/to/lib/gcc/aarch64-unknown-linux-gnu/11.2.0
Selected GCC installation: /path/to/lib/gcc/aarch64-unknown-linux-gnu/11.2.0
Candidate multilib: .;@<!-- -->m64
Selected multilib: .;@<!-- -->m64
 "/path/to/install/bin/flang-new" -fc1 -triple aarch64-unknown-linux-gnu -S -fcolor-diagnostics -mrelocation-model pic -pic-level 2 -pic-is-pie -ffast-math -target-cpu generic -target-feature +neon -target-feature +v8a -fstack-arrays -fversion-loops-for-stride -Rpass=vector -O3 -o s113.s -x f95-cpp-input s113.f
$ clang -Ofast s113.c -Rpass=licm\|vector
/path/to/s113.c:16:11: remark: hoisting load [-Rpass=licm]
   16 |                         a[i] = a[0] + b[i];
      |                                ^
/path/to/s113.c:15:3: remark: vectorized loop (vectorization width: 4, interleaved count: 2) [-Rpass=loop-vectorize]
   15 |                 for (int i = 1; i &lt; LEN; i++) {
      |                 ^

It can be reproduced with the following C code which is the same program as the above C code essentially.

// C version
for (int nl = 0; nl < ntimes; nl++) {
  for (int i = 2; i <= n; i++) {
    a[i-1] = a[0] + b[i-1];
  }
  dummy(a, b, c, d, e, aa, bb, cc, 0.);
}

Actually, Flang generates LLVM IR like this C code.

LICM is necessary for vectorization because LoopAccessAnalysis can't analyze a[0] correctly.
It seems that LICM doesn't work due to the linear expression in indices of arrays.

[tblah]

Thanks for reporting this.

Please could you try this with -falias-analysis and report if that resolves the issue. Hopefully this will be enabled by default very soon: #74250

[yus3710-fj]

Thank you for the information.
This issue isn't resolved even if -falias-analysis is enabled.

At the moment, I think this is the issue of alias analysis in LLVM itself, not the way alias information is passed from Flang to LLVM.

[tblah]

Thank you for confirming

[yus3710-fj]

BasicAliasAnalysis is invoked in the LICM pass to check whether a[i-1] and a[0] alias each other.
But BasicAA doesn't have the information of loops, so the access range of a[i-1] isn't calculated correctly.

llvm-project/llvm/lib/Analysis/BasicAliasAnalysis.cpp

Lines 1221 to 1226 in 6615581

	ConstantRange Range1 = OffsetRange.add(
	ConstantRange(APInt(BW, 0), APInt(BW, V1Size.getValue())));
	ConstantRange Range2 =
	ConstantRange(APInt(BW, 0), APInt(BW, V2Size.getValue()));
	if (Range1.intersectWith(Range2).isEmptySet())
	return AliasResult::NoAlias;

According to BasicAA, the range of a[i-1] is [-4,8589934588) and that of a[0] is [0,4) so they are overlapping.
This is wrong because the true range of a[i-1] is [4,8589934588).

[yus3710-fj]

Hello, @fhahn and @nikic.
I found you commented on some issues about LICM, so please let me ask you for your advices.

I have no idea what I should fix to resolve this issue, so please let me clarify whether I should fix BasicAA at first.
I'd like to know whether the above behavior of BasicAA is what it's expected.
I'm not sure BasicAA should handle with analysis for indices of arrays. IIUC, alias analysis is used to determine whether two different variables can point the same memory location, that is alias analysis doesn't have to handle with indices of the same array.
If so, I can say I should fix LICM or LAA to resolve this issue.

[nikic]

In principle, improving BasicAA to determine that these don't alias would be the right fix. We might be willing to accept some crude range analysis for simple recurrences, if it is reasonably simple and has no impact on compile-time.

[yus3710-fj]

Thank you for your helpful comment.
I started to consider fixing computeConstantRange which is called from BasicAA. If the change makes an influence on some other passes calling it, I'll consider another fix.