[SCEV] Repeated max not hoisted out of loop

[aengelke]

The repeated computation of a maximum/minimum is not hoisted outside of a loop, preventing the elimination of the loop (instead, the loop gets pointlessly vectorized).

Example (https://godbolt.org/z/faM4od4dM; see also: https://alive2.llvm.org/ce/z/YqPC82)

#include <cstdint>
uint8_t f(uint8_t n, uint8_t a, uint8_t b) {
    for (uint8_t i = 0; i < n; i++)
        a = a < b ? b : a;
    return a;
}

To me this looks like something that SCEV should recognize (I might be wrong here, but in the end, the loop should get eliminated).

[nikic]

define i8 @test(i8 %n, i8 %a, i8 %b) {
entry:
  br label %loop

loop:
  %iv = phi i8 [ %iv.next, %loop ], [ 0, %entry ]
  %umax.acc = phi i8 [ %umax, %loop ], [ %a, %entry ]
  %umax = call i8 @llvm.umax.i8(i8 %umax.acc, i8 %b)
  %iv.next = add nuw i8 %iv, 1
  %cmp = icmp ult i8 %iv.next, %n
  br i1 %cmp, label %loop, label %exit

exit:
  ret i8 %umax
}

I don't think SCEV is the right place for this, it doesn't generally reason about non-add recurrences. Possibly this should just be in InstCombine.

[dtcxzyw]

@antoniofrighetto Can you add a matchSimpleRecurrence-like helper for binary intrinsics in ValueTracking? I plan to extend #143020 to handle other reductions. Thank you!

[antoniofrighetto]

@dtcxzyw Assigning this to you too, for the remaining work to be done :)