[GVN] Missed partial redundancy elimination opportunity of load through select instruction

[skachkov-sc]

Reproduction

int test(int i, int N, int *A)
{
    if (i != (N - 1) && A[i] > A[i+1])
        ++i;
    return A[i];
}

Compiled with: -O3 -S -emit-llvm

The latest load can be replaced with select between already loaded values, so we will have 2 loads on the execution path instead of 3. Pseudocode:

int test(int i, int N, int *A)
{
    int tmp1 = A[i];
    bool cond = false;
    if (i != (N - 1)) {
        int tmp2 = A[i+1];
        cond = tmp1 > tmp2;
    }
    return cond ? tmp2 : tmp1;
}

However, GVN pass can't process such case through select instruction. LLVM IR (-O3 -S -emit-llvm):

entry:
  %sub = add nsw i32 %N, -1
  %cmp.not = icmp eq i32 %sub, %i
  br i1 %cmp.not, label %if.end, label %land.lhs.true

land.lhs.true:                                    ; preds = %entry
  %idxprom = sext i32 %i to i64
  %arrayidx = getelementptr inbounds i32, ptr %A, i64 %idxprom
  %0 = load i32, ptr %arrayidx, align 4, !tbaa !5
  %add = add nsw i32 %i, 1
  %idxprom1 = sext i32 %add to i64
  %arrayidx2 = getelementptr inbounds i32, ptr %A, i64 %idxprom1
  %1 = load i32, ptr %arrayidx2, align 4, !tbaa !5
  %cmp3 = icmp sgt i32 %0, %1
  %spec.select = select i1 %cmp3, i32 %add, i32 %i
  br label %if.end

if.end:                                           ; preds = %land.lhs.true, %entry
  %i.addr.0 = phi i32 [ %i, %entry ], [ %spec.select, %land.lhs.true ]
  %idxprom4 = sext i32 %i.addr.0 to i64
  %arrayidx5 = getelementptr inbounds i32, ptr %A, i64 %idxprom4
  %2 = load i32, ptr %arrayidx5, align 4, !tbaa !5
  ret i32 %2

There is already some support of pointer-select in GVN pass (https://reviews.llvm.org/D118143), so I assume more generalized solution (select between indices) is required. This issue affects the performance of SPEC2017 520.omnetpp_r benchmark (the example is minimized from rather hot cMessageHeap::shiftup method), and looks like GCC is able to do PRE here.

[madhur13490]

Hello,
We found another case in the polyhedron fortran benchmark - rnflow.f90 file. Particularly, the function minlst shows a case where minimum index is computed and returned from the function.

Here is the equivalent C version for it.

int func(int *restrict arr, int N) {
  int minloc = 0;
  for (int i = 0; i < N; ++i)
    if (arr[i] < arr[minloc])
      minloc = i;
  return minloc;
}

Godbolt link

GCC is optimizing this in GVN PRE and can keep the minindex and minimum value in the register. While on the other hand, LLVM loads both arr[i] and arr[minloc] in the loop thus, we have two loads in the LLVM code.