[LV] Pre-commit test case for AnyOf reduction , NFC

[Mel-Chen]

Summary

The loop in C code is:

int rdx = a;
for (i = 0; i < n; ++i)
  if(rdx != 3)
    rdx = b;

I'd like to raise a discussion: Can this loop be vectorized as AnyOf reduction?
My personally answer is no, but I might be mistaken.
Continuing from above, if this is a valid AnyOf reduction, we might need to make some modifications to the process of identifying reductions, as this isn't an FAnyOf but an IAnyOf. This patch will become a pre-commit patch to fix that. However, if this isn't a valid AnyOf reduction, then I will abandon this patch.

[Mel-Chen]

Corrected the debug message in test case.

[Mel-Chen]

Ping

[fhahn]

I think it makes sense to have a test like this in any case to make sure it is handled correctly.

llvm/test/Transforms/LoopVectorize/anyof-msg.ll

5

What's the reason for checking the debug output instead of the generated IR?

[Mel-Chen]

In D157375#4591459, @fhahn wrote:

I think it makes sense to have a test like this in any case to make sure it is handled correctly.

Thanks for your reviewing.

llvm/test/Transforms/LoopVectorize/anyof-msg.ll

5

This case was directly copied from Transforms/LoopVectorize/select-cmp.ll, where the generated IR was already checked. However, I found that the execution path for identifying reductions is incorrect. It should print out "an integer conditional select reduction PHI" instead of "a float conditional select reduction PHI". I believe this case should not be recognized as an AnyOf reduction pattern, but I hope more people can confirm this.
From an implementation perspective, the issue to be confirmed is whether AnyOf recurrence pattern should only include select instruction or if it can also include cmp instruction.

[michaelmaitland]

int rdx = a;
for (i = 0; i < n; ++i)
  if(rdx != 3)
    rdx = b;

is equivalent to

int rdx = a != 3 ? b : a;

I'd hope that this loop would be removed before we get to LV.

EDIT:
I just wanted to enumerate all of the possibilities so I was more confident in the statement I made above.

The first rdx in each statement below is the rdx after executing the loop from your example and the second rdx is from the statement I say is equivalent.

a=0;b=1; -> rdx=1; rdx=1 // neither are 3 but a and b are not equal
a=0;b=0; -> rdx=0; rdx=0 // neither are 3 but a and and b are equal
a=3;b=3; -> rdx=3; rdx=3 // and and b are 3
a=3;b=2; -> rdx=3; rdx=3 // a is 3 but b is not
a=2;b=3; -> rdx=3; rdx=3 // a is not 3 but b is

[Mel-Chen]

Add test case @select_i32_from_icmp_non_const_same_inputs.

[Mel-Chen]

@michaelmaitland Yes, with this example, the your transformation is possible.
However, this still remains a challenge that vectorizers need to address because we cannot restrict the input IR that goes into opt.
Therefore, I have provided a new case -- @select_i32_from_icmp_non_const_same_inputs:

int rdx = a;
for (i = 0; i < n; ++i)
  if(rdx != c[i])
    rdx = b;

The conclusions we can draw so far are that due to the loop-invariant of the values selected by AnyOf, it possess the following characteristics,

if all conditions are false:
   rdx = start_value (%a)
else:
  rdx = new_loop_invariant (%b)

which may allow AnyOf recurrence to include cmp instructions

[michaelmaitland]

llvm/test/Transforms/LoopVectorize/anyof-msg.ll

5

Is the code generated incorrect in Transforms/LoopVectorize/select-cmp.ll due to considering it a float conditional select reduction? If so, writing a fix and updating that test file may suffice and make this test redundant.

[michaelmaitland]

According to RecurKind, an AnyOf reduction has the form select(icmp(), x, y) where one of (x,y) are loop invariant. In RecurrenceDescriptor::isAnyOfPattern there is the additional condition that both (x, y) are loop invariant. (switching between two variables). The functions in your test case satisfy the first definition of AnyOf but not the second IIUC. Is there a reason why the two definitions of AnyOf are conflicting?

llvm/test/Transforms/LoopVectorize/anyof-msg.ll

+; REQUIRES: asserts
+; RUN: opt -passes=loop-vectorize -force-vector-interleave=1 -force-vector-width=4 -S < %s -debug-only=iv-descriptors,loop-vectorize -S 2>&1 | FileCheck %s
+
+; The test case is copied from Transforms/LoopVectorize/select-cmp.ll
+;
+; CHECK-LABEL: Checking a loop in 'select_i32_from_icmp_same_inputs'
+; CHECK: Found a float conditional select reduction PHI. PHI.  %1 = phi i32 [ %a, %entry ], [ %3, %for.body ]
+;
+define i32 @select_i32_from_icmp_same_inputs(i32 %a, i32 %b, i64 %n) {
+entry:
+  br label %for.body
+
+for.body:                                      ; preds = %entry, %for.body
+  %0 = phi i64 [ 0, %entry ], [ %4, %for.body ]
+  %1 = phi i32 [ %a, %entry ], [ %3, %for.body ]
+  %2 = icmp eq i32 %1, 3
+  %3 = select i1 %2, i32 %1, i32 %b
+  %4 = add nuw nsw i64 %0, 1
+  %5 = icmp eq i64 %4, %n
+  br i1 %5, label %exit, label %for.body
+
+exit:                                     ; preds = %for.body
+  ret i32 %3
+}
+
+;
+; The test case is modified from Transforms/LoopVectorize/select-cmp.ll
+;
+; CHECK-LABEL: Checking a loop in 'select_i32_from_icmp_non_const_same_inputs'
+; CHECK: Found a float conditional select reduction PHI. PHI.  %1 = phi i32 [ %a, %entry ], [ %5, %for.body ]
+;
+define i32 @select_i32_from_icmp_non_const_same_inputs(i32 %a, i32 %b, i64 %n, ptr %c) {
+entry:
+  br label %for.body
+
+for.body:                                      ; preds = %entry, %for.body
+  %0 = phi i64 [ 0, %entry ], [ %6, %for.body ]
+  %1 = phi i32 [ %a, %entry ], [ %5, %for.body ]
+  %2 = getelementptr inbounds i32, ptr %c, i64 %0
+  %3 = load i32, ptr %2, align 4
+  %4 = icmp eq i32 %1, %3
+  %5 = select i1 %4, i32 %1, i32 %b
+  %6 = add nuw nsw i64 %0, 1
+  %7 = icmp eq i64 %6, %n
+  br i1 %7, label %exit, label %for.body
+
+exit:                                     ; preds = %for.body
+  ret i32 %5
+}