[LV] Fix incorrect detection of type-promoted Phis

[mkazantsev]

Summary

Loop vectorizer may recognize the following pattern

%iv = phi i32 ...
%x = add i32 %iv, %mask

where %mask is 2^N - 1 as Phi node of type iN which was type-promoted
during canonicalizing transforms. In this case we can vectorize the loop using
its original type and fit more elements into one vector.

The logic that is responsible for this is broken. It only demands that a Phi is
masked, but does not check that after all calculations the result is actually
truncated to type iN. As result, it may falsely detect the following code as
being somehow connected to type-promoted Phis:

char foo(char c) {
    for (int i = 1; i < 193; i++) {
          c &= (char) 1;
          c += (char) 3;
    }
    return c;
}

Vectorizer tries to calculate the result of this loop in vector of i1, what lead
to incorrect calculations (answer is always 0 or 1 instead of 3 or `4).

This patch strengthens the detecor of this situation. If we have shrinked the
type due to masking, we should later check that the result of all calculations
is either dead or is properly truncated to this type.

[mkazantsev]

Added a comment, fixed some typos.

[mkazantsev]

Ping

[anna]

lib/Transforms/Utils/LoopUtils.cpp

372

I don't think you can assert since you can have uses of ExitInstruction in unreachable blocks and unreachable blocks by definition are outside a loop.

388

getNumUses is linear in the number of uses. This is better: LCSSAPhi->hasNUsesOrMore(2)

[mkazantsev]

lib/Transforms/Utils/LoopUtils.cpp

372

Good point, thanks!

[mkazantsev]

Ping

[anna]

LGTM. I think there maybe performance degradations in vectorization, but this is needed for a correctness fix.
Pls wait for @mssimpso if he has any comments.

[anna]

I just saw on another review thread that Matt's away for a few weeks.
Max, feel free to land this change.

[mkazantsev]

I cannot merge this because of https://reviews.llvm.org/D42309 which has been merged yesterday and removed the piece of code which I touched. It was addressing the bug PR35734 which actually looks pretty similar to what I was trying to fix here. I don't know this code good enough to understand whether it actually has fixed the problem or just hid it, though. However it helps the test. I think I will just end up merging the tests as NFC and abandoning this one since this logic is no more.

[mkazantsev]

Abandoning due to underlying code massive rework done in https://reviews.llvm.org/rL324195. The bug was fixed with this patch. The tests merged separately as NFC.

[mssimpso]

Max/Anna,

Sorry for not responding sooner - I was away from work for a few weeks. Yes, this looks like the same issue that was fixed over in rL324195. Thanks for adding the new tests, and sorry for the duplicated effort! Let me know if you run into any problems with the new code.

lib/Transforms/Utils/LoopUtils.cpp

if ((Kind == RK_IntegerMinMax || Kind == RK_FloatMinMax) &&
     return false;
 
   if (!FoundStartPHI || !FoundReduxOp || !ExitInstruction)
     return false;
 
   // If we think Phi may have been type-promoted, we also need to ensure that
   // all source operands of the reduction are either SExtInsts or ZEstInsts. If
   // so, we will be able to evaluate the reduction in the narrower bit width.
-  if (Start != Phi)
+  if (Start != Phi) {
     if (!getSourceExtensionKind(Start, ExitInstruction, RecurrenceType,
                                 IsSigned, VisitedInsts, CastInsts))
       return false;
 
+    // We need to be certain that we are dealing with type-promoted Phi. So we
+    // check that the value that goes outside the loop is only used by LCSSA
+    // Phi node which is either dead or truncated to the type we expect.
+    PHINode *LCSSAPhi = nullptr;
+    for (auto U = ExitInstruction->use_begin(), UE = ExitInstruction->use_end();
+         U != UE; ++U) {
+      Instruction *UI = cast<Instruction>(U->getUser());
+      if (!TheLoop->contains(UI->getParent())) {
+        // Two users outside the loop, we should not have it.
+        // TODO: Can this be safely replaced with assert?
+        if (LCSSAPhi)
+          return false;
+
+        PHINode *PN = dyn_cast<PHINode>(UI);
+        // LCSSA Phi node we are looking for is a Phi with 1 input.
+        if (!PN || PN->getNumOperands() != 1)
+          return false;
+        LCSSAPhi = PN;
+      }
+    }
+
+    // If the found LCSSA has uses, make sure that it is the only one use that
+    // is a trunc to a proper type. Otherwise what we are dealing with is not a
+    // type-promoted Phi node.
+    if (LCSSAPhi->getNumUses() > 1)
+      return false;
+
+    if (LCSSAPhi->hasOneUse()) {
+      TruncInst *Trunc = dyn_cast<TruncInst>(LCSSAPhi->use_begin()->getUser());
+      if (!Trunc || Trunc->getType() != RecurrenceType)
+        return false;
+    }
+  }
+
   // We found a reduction var if we have reached the original phi node and we
   // only have a single instruction with out-of-loop users.
 
   // The ExitInstruction(Instruction which is allowed to have out-of-loop users)
   // is saved as part of the RecurrenceDescriptor.
 
   // Save the description of this reduction variable.
   RecurrenceDescriptor RD(

test/Transforms/LoopVectorize/and-plus.ll

+; RUN: opt < %s  -loop-vectorize -S | FileCheck %s
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128-ni:1"
+target triple = "x86_64-unknown-linux-gnu"
+
+; This should not be vectorized. Current algorithm tries to choose type i1 for
+; vectorization because we apply and with 1 to the accumulator. But the result
+; of this calculation does not fit into type i1.
+; TODO: We vectorize this loop with type i32. For this, we need to be able to
+; undo the changes made by lookThroughAnd after we find out that our idea that
+; we are dealing with extended Phi of type i1 was wrong.
+define i8 @test_01(i8 %c) #0 {
+
+; CHECK-LABEL: @test_01(
+; CHECK-NOT:   vector.body:
+; CHECK-NOT:   zext i1 {{.*}} to i8
+
+entry:
+  br label %loop
+
+exit:                                           ; preds = %loop
+  ret i8 %accum.plus
+
+loop:                                            ; preds = %loop, %entry
+  %accum.phi = phi i8 [ %c, %entry ], [ %accum.plus, %loop ]
+  %iv = phi i32 [ 1, %entry ], [ %iv.next, %loop ]
+  %accum.and = and i8 %accum.phi, 1
+  %accum.plus = add nuw nsw i8 %accum.and, 3
+  %iv.next = add nuw nsw i32 %iv, 1
+  %cond = icmp ugt i32 %iv, 191
+  br i1 %cond, label %exit, label %loop
+}
+
+; This can be vectorized with type i1 because the result is not used.
+define void @test_02(i8 %c) #0 {
+
+; CHECK-LABEL: @test_02(
+; CHECK:   vector.body:
+; CHECK:   zext i1 {{.*}} to i8
+
+entry:
+  br label %loop
+
+exit:                                           ; preds = %loop
+  %lcssa = phi i8 [ %accum.plus, %loop ]
+  ret void
+
+loop:                                            ; preds = %loop, %entry
+  %accum.phi = phi i8 [ %c, %entry ], [ %accum.plus, %loop ]
+  %iv = phi i32 [ 1, %entry ], [ %iv.next, %loop ]
+  %accum.and = and i8 %accum.phi, 1
+  %accum.plus = add nuw nsw i8 %accum.and, 3
+  %iv.next = add nuw nsw i32 %iv, 1
+  %cond = icmp ugt i32 %iv, 191
+  br i1 %cond, label %exit, label %loop
+}
+
+; This can be vectorized with type i1 because the result is truncated properly.
+define i1 @test_03(i8 %c) #0 {
+
+; CHECK-LABEL: @test_03(
+; CHECK:   vector.body:
+; CHECK:   zext i1 {{.*}} to i8
+
+entry:
+  br label %loop
+
+exit:                                           ; preds = %loop
+  %lcssa = phi i8 [ %accum.plus, %loop ]
+  %trunc = trunc i8 %lcssa to i1
+  ret i1 %trunc
+
+loop:                                            ; preds = %loop, %entry
+  %accum.phi = phi i8 [ %c, %entry ], [ %accum.plus, %loop ]
+  %iv = phi i32 [ 1, %entry ], [ %iv.next, %loop ]
+  %accum.and = and i8 %accum.phi, 1
+  %accum.plus = add nuw nsw i8 %accum.and, 3
+  %iv.next = add nuw nsw i32 %iv, 1
+  %cond = icmp ugt i32 %iv, 191
+  br i1 %cond, label %exit, label %loop
+}
+
+; This cannot be vectorized with type i1 because the result is truncated to a
+; wrong type.
+; TODO: It can also be vectorized with type i32 (or maybe i4?) it we learn to
+; undo lookThroughAnd.
+define i4 @test_04(i8 %c) #0 {
+
+; CHECK-LABEL: @test_04(
+; CHECK-NOT:   vector.body:
+; CHECK-NOT:   zext i1 {{.*}} to i8
+
+entry:
+  br label %loop
+
+exit:                                           ; preds = %loop
+  %lcssa = phi i8 [ %accum.plus, %loop ]
+  %trunc = trunc i8 %lcssa to i4
+  ret i4 %trunc
+
+loop:                                            ; preds = %loop, %entry
+  %accum.phi = phi i8 [ %c, %entry ], [ %accum.plus, %loop ]
+  %iv = phi i32 [ 1, %entry ], [ %iv.next, %loop ]
+  %accum.and = and i8 %accum.phi, 1
+  %accum.plus = add nuw nsw i8 %accum.and, 3
+  %iv.next = add nuw nsw i32 %iv, 1
+  %cond = icmp ugt i32 %iv, 191
+  br i1 %cond, label %exit, label %loop
+}