Missed loop replace_if vectorization due to the presence of switch

[davidbolvansky]

Bugzilla Link	48844
Version	trunk
OS	Linux
CC	@fhahn,@RKSimon,@nikic,@rotateright

Extended Description

#include <algorithm>
#include <vector>
#include <cstdint>

void replace_if_epi8(std::vector<int8_t>& v) {
    std::replace_if(v.begin(), v.end(), [](int8_t x){return x == 13 || x == -12; }, 42);
}

void replace_if_epi32(std::vector<int32_t>& v) {
    std::replace_if(v.begin(), v.end(), [](int8_t x){return x == 13 || x == -12; }, 42);
}

LLVM fails to vectorize this code - possibly due to presence of switch (OR cond is converted to switch).
https://godbolt.org/z/sY5oT9

Second example:

void replace_if_epi8(std::vector<int8_t>& v) {
    std::replace_if(v.begin(), v.end(), [](int8_t x){return x == 13 ; }, 42);
}

void replace_if_epi32(std::vector<int32_t>& v) {
    std::replace_if(v.begin(), v.end(), [](int8_t x){return x == 13; }, 42);
}

This code is nicely vectorized by LLVM.
https://godbolt.org/z/jx4dqo

So either simplifycfg should not create switches before vectorizers (easy fix, maybe profitable for other optimizations too?), and/or vectorizers should know how to handle them.

[rotateright]

So either simplifycfg should not create switches before vectorizers (easy
fix, maybe profitable for other optimizations too?), and/or vectorizers
should know how to handle them.

I think the 1st option is more likely to succeed.
It even looks like we already have the opposite transform in SimplifyCFG -- ConvertTwoCaseSwitch() ?

[nikic]

We should at least adjust the heuristic to stop forming switches from two comparisons. I've seen this block optimizations a few times already, and I can't really imagine a case where this would be beneficial for optimization or lowering.

[davidbolvansky]

Or just delay SimplifyBranchOnICmpChain? Something like
https://reviews.llvm.org/D84108 ; to avoid creating switch too early.

[hiraditya]

If vectorizer were to handle this, there should be a way to roll it back if vectorization wasn't successful.

[hiraditya]

OTOH we generate jump table in AArch64 backend only when the number of case statements is more than 12 #98391

[hiraditya]

For some context https://godbolt.org/z/zKdxdPhKb

; *** IR Dump After SimplifyCFGPass on _ZNSt3__110replace_ifB8ne190000INS_11__wrap_iterIPaEEZ15replace_if_epi8RNS_6vectorIaNS_9allocatorIaEEEEE3$_0iEEvT_SA_T0_RKT1_ ***
define dso_local void @replace_if_epi8(std::__1::vector<signed char, std::__1::allocator<signed char>>&)(ptr nocapture noundef nonnull readonly align 8 dereferenceable(24) %v) local_unnamed_addr {
entry:
  %0 = load ptr, ptr %v, align 8
  %__end_.i = getelementptr inbounds i8, ptr %v, i64 8
  %1 = load ptr, ptr %__end_.i, align 8
  %cmp.i.i.not9.i = icmp eq ptr %0, %1
  br i1 %cmp.i.i.not9.i, label %"void std::__1::replace_if[abi:ne190000]<std::__1::__wrap_iter<signed char*>, replace_if_epi8(std::__1::vector<signed char, std::__1::allocator<signed char>>&)::$_0, int>(std::__1::__wrap_iter<signed char*>, std::__1::__wrap_iter<signed char*>, replace_if_epi8(std::__1::vector<signed char, std::__1::allocator<signed char>>&)::$_0, int const&).exit", label %for.body.i

for.body.i:                                       ; preds = %for.inc.i, %entry
  %__first.sroa.0.010.i = phi ptr [ %incdec.ptr.i.i, %for.inc.i ], [ %0, %entry ]
  %2 = load i8, ptr %__first.sroa.0.010.i, align 1
  switch i8 %2, label %for.inc.i [
    i8 -12, label %if.then.i
    i8 13, label %if.then.i
  ]

if.then.i:                                        ; preds = %for.body.i, %for.body.i
  store i8 42, ptr %__first.sroa.0.010.i, align 1
  br label %for.inc.i

for.inc.i:                                        ; preds = %if.then.i, %for.body.i
  %incdec.ptr.i.i = getelementptr inbounds i8, ptr %__first.sroa.0.010.i, i64 1
  %cmp.i.i.not.i = icmp eq ptr %incdec.ptr.i.i, %1
  br i1 %cmp.i.i.not.i, label %"void std::__1::replace_if[abi:ne190000]<std::__1::__wrap_iter<signed char*>, replace_if_epi8(std::__1::vector<signed char, std::__1::allocator<signed char>>&)::$_0, int>(std::__1::__wrap_iter<signed char*>, std::__1::__wrap_iter<signed char*>, replace_if_epi8(std::__1::vector<signed char, std::__1::allocator<signed char>>&)::$_0, int const&).exit", label %for.body.i

"void std::__1::replace_if[abi:ne190000]<std::__1::__wrap_iter<signed char*>, replace_if_epi8(std::__1::vector<signed char, std::__1::allocator<signed char>>&)::$_0, int>(std::__1::__wrap_iter<signed char*>, std::__1::__wrap_iter<signed char*>, replace_if_epi8(std::__1::vector<signed char, std::__1::allocator<signed char>>&)::$_0, int const&).exit": ; preds = %entry, %for.inc.i
  ret void
}

[hiraditya]

FYI cd3d80e added llvm/test/Transforms/PhaseOrdering/X86/pr48844-br-to-switch-vectorization.ll acknowledging this problem.

[fhahn]

It looks like it should be possible to support switch instructions during if-conversion in LV: #99808