[LoopVectorizer] Fix invalid scenario that is allowed to interleave

[dancgr]

Summary

Tentative change to Loop Vectorizer to avoid a case of interleaving that creates incorrect code.

This problem is described on bug https://bugs.llvm.org/show_bug.cgi?id=48546.

In short, there is a case of compiling the following code with -O2 which triggers the loop vectorizer bug with clang -O2 test.c

int printf(const char *, ...);
int a, b, e;
char c, d;
int main() {
  d = 19;
  printf("%d\n", c);
  for (; d < 161; d++) {
    char *f = &c;
    *f &= 1;
    e = b== 0 ?:a%b;
    (*f)--;
  }
  printf("%d\n", c);
}

The output compilation produces incorrect code. The value printed is 254 instead of 0.

This is because we determine that we can interleave this loop, when instead it should not be allowed.

There are cases without interleaving that would make it legal to vectorize this code, so the condition is placed only if we can interleave.

[dancgr]

Are there any opinions on this bugfix?

[fhahn]

can you add a test case?

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorizationLegality.cpp

1268

Could you elaborate why the type width would matter here? Is it possible that this only exposed a problem somewhere else, e.g. lowering operations on vectors of i1?

(I tried to reproduce the problem with current trunk on macOS, but failed)

[dmgreen]

Hello

I could not replicate the bug in https://bugs.llvm.org/show_bug.cgi?id=48546 with the latest clang, as I mentioned in the ticket. Can you provide a more specific reproducer, and use it as a test case for what is being fixed?

[dancgr]

@dmgreen @fhahn Sorry about that, the test case I posted was incorrect. I updated the test.c file, and in the process of finding the correct test case for you to be able to reproduce I found out the bug is worse than I expected.

With the new code I edited in the description you should be able to reproduce the bug. Unfortunately this patch doesn't cover the new test case, I am working in a new patch.

[fhahn]

Marking as changes requested, as there is an update pending IIUC

llvm/include/llvm/Transforms/Vectorize/LoopVectorizationLegality.h

   bool isMaskRequired(const Instruction *I) { return (MaskedOp.count(I) != 0); }
 
   unsigned getNumStores() const { return LAI->getNumStores(); }
   unsigned getNumLoads() const { return LAI->getNumLoads(); }
 
   // Returns true if the NoNaN attribute is set on the function.
   bool hasFunNoNaNAttr() const { return HasFunNoNaNAttr; }
 
+  bool isLegalToInterleave();
+
 private:
   /// Return true if the pre-header, exiting and latch blocks of \p Lp and all
   /// its nested loops are considered legal for vectorization. These legal
   /// checks are common for inner and outer loop vectorization.
   /// Temporarily taking UseVPlanNativePath parameter. If true, take
   /// the new code path being implemented for outer loop vectorization
   /// (should be functional for inner loop vectorization) based on VPlan.
   /// If false, good old LV code.

llvm/lib/Transforms/Vectorize/LoopVectorizationLegality.cpp

       return false;
     }
   }
 
   LLVM_DEBUG(dbgs() << "LV: can fold tail by masking.\n");
   return true;
 }
 
+bool LoopVectorizationLegality::isLegalToInterleave() {
+  // Check if reduction has invalid type for interleaving.
+  for (auto &Reduction : *getReductionVars()) {
+    auto Descriptor = Reduction.second;
+    auto ComputedType = Descriptor.getRecurrenceType();
+    auto IsSigned = Descriptor.isSigned();
+    // Eliminate degenerate types.
+    if (ComputedType->isIntegerTy(1) && IsSigned) {
+      return false;
+    }
+  }
+  return true;
+}
+
 } // namespace llvm

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

   unsigned UserIC = Hints.getInterleave();
 
   if (MaybeVF) {
     VF = *MaybeVF;
     // Select the interleave count.
     IC = CM.selectInterleaveCount(VF.Width, VF.Cost, LVI);
   }
 
+  // Check if it is legal to interleave the loop.
+  if (IC > 1 && !LVL.isLegalToInterleave()) {
+    LLVM_DEBUG(dbgs() << "LV: Not vectorizing: Can't interleave reduction.\n");
+    Hints.emitRemarkWithHints();
+    return false;
+  }
+
   // Identify the diagnostic messages that should be produced.
   std::pair<StringRef, std::string> VecDiagMsg, IntDiagMsg;
   bool VectorizeLoop = true, InterleaveLoop = true;
   bool IfReorder = false;
   if (Requirements.doesNotMeet(F, L, Hints, IfReorder)) {
     if (EnableFpAggressiveInterleave && IfReorder) {
       // Re-calculate IC for loops that may reorder floating-point operations in
       // vectorization.