[SingleSource/Vectorizer] Add runtime checks tests for nested loops

[david-arm]

Summary

This patch adds tests for nested loops like this:

for (int i = 0; i < N; i++) {
  for (int j = 0; j < N; j++) {
    a[(i * (N + 1)) + j] += b[(i * N) + j];
  }
}

where we generate runtime checks for the inner loop that do not
currently get hoisted above the outer loop.

[fhahn]

Thanks for adding those. Do you think it would be relatively straight forward to add variants where the trip counts of both loops are different & maybe where the induction counts down?

SingleSource/UnitTests/Vectorizer/common.h

21

Does the helper need 3 pointer arguments? It looks like only A and B are used in the code below.

[david-arm]

• Added more test cases, such as allowing the trip counts to differ, and permitting decreasing outer loop induction variables.

[david-arm]

In D154719#4483638, @fhahn wrote:

Thanks for adding those. Do you think it would be relatively straight forward to add variants where the trip counts of both loops are different & maybe where the induction counts down?

Both are good suggestions! I've added some to the file.

[fhahn]

LGTM, thanks!

SingleSource/UnitTests/Vectorizer/common.h

20

nit: might be good to include the fact that this is for nested loops in the name

SingleSource/UnitTests/Vectorizer/common.h

 #define DEFINE_SCALAR_AND_VECTOR_FN3(Loop)                                     \
   auto ScalarFn = [](auto *A, auto *B, auto *C, unsigned TC) {                 \
     _Pragma("clang loop vectorize(disable) interleave_count(1)") Loop          \
   };                                                                           \
   auto VectorFn = [](auto *A, auto *B, auto *C, unsigned TC) {                 \
     _Pragma("clang loop vectorize(enable)") Loop                               \
   };
 
+#define DEFINE_NESTED_SCALAR_AND_VECTOR_FN4(InnerLoopCode)                     \
+  auto ScalarFn = [](auto *A, auto *B, unsigned OuterTC, unsigned InnerTC) {   \
+    for (unsigned long i = 0; i < OuterTC; i++) {                              \
+      _Pragma("clang loop vectorize(disable) interleave_count(1)")             \
+      for (unsigned long j = 0; j < InnerTC; j++) {                            \
+        InnerLoopCode                                                          \
+      }                                                                        \
+    }                                                                          \
+  };                                                                           \
+  auto VectorFn = [](auto *A, auto *B, unsigned OuterTC, unsigned InnerTC) {   \
+    for (unsigned long i = 0; i < OuterTC; i++) {                              \
+      _Pragma("clang loop vectorize(enable)")                                  \
+      for (unsigned long j = 0; j < InnerTC; j++) {                            \
+        InnerLoopCode                                                          \
+      }                                                                        \
+    }                                                                          \
+  };
+
+#define DEFINE_NESTED_SCALAR_AND_VECTOR_FN5(InnerLoopCode)                            \
+  auto ScalarFn = [](auto *A, auto *B, unsigned OuterTC, unsigned InnerTC) {   \
+    for (long i = OuterTC - 1; i >= 0; i--) {                         \
+      _Pragma("clang loop vectorize(disable) interleave_count(1)")             \
+      for (unsigned long j = 0; j < InnerTC; j++) {                            \
+        InnerLoopCode                                                          \
+      }                                                                        \
+    }                                                                          \
+  };                                                                           \
+  auto VectorFn = [](auto *A, auto *B, unsigned OuterTC, unsigned InnerTC) {   \
+    for (long i = OuterTC - 1; i >= 0; i--) {                         \
+      _Pragma("clang loop vectorize(enable)")                                  \
+      for (unsigned long j = 0; j < InnerTC; j++) {                            \
+        InnerLoopCode                                                          \
+      }                                                                        \
+    }                                                                          \
+  };
+
 static std::mt19937 rng;
 
 // Initialize arrays A with random numbers.
 template <typename Ty>
 static void init_data(const std::unique_ptr<Ty[]> &A, unsigned N) {
   std::uniform_int_distribution<uint64_t> distrib(
       std::numeric_limits<Ty>::min(), std::numeric_limits<Ty>::max());
   for (unsigned i = 0; i < N; i++)

SingleSource/UnitTests/Vectorizer/runtime-checks.cpp

 #include <functional>
 #include <iostream>
 #include <limits>
 #include <memory>
 #include <random>
 #include <stdint.h>
 
 #include "common.h"
 
+
 // Tests for memory runtime checks generated by the vectorizer. Runs scalar and
 // vectorized versions of a loop requiring runtime checks on the same inputs
 // with pointers to the same buffer using various offsets between reads and
 // writes. Fails if they do not produce the same results.
 
 template <typename Ty>
 static void check(const std::unique_ptr<Ty[]> &Reference,
                   const std::unique_ptr<Ty[]> &Tmp, unsigned NumElements,
auto CheckWithOffsetSecond = [&](int Offset) {
     // Compare scalar and vector output.
     check(Reference, ToCheck, NumArrayElements, Offset);
   };
 
   for (int i = -100; i <= 100; i++)
     CheckWithOffsetSecond(i);
 }
 
+
+
+template <typename Ty>
+using Fn4Ty = std::function<void(Ty *, Ty *, unsigned, unsigned)>;
+template <typename Ty>
+static void checkOverlappingMemoryTwoRuntimeChecksNested(Fn4Ty<Ty> ScalarFn,
+                                                         Fn4Ty<Ty> VectorFn,
+                                                         const int OuterTC,
+                                                         const int InnerTC,
+                                                         const char *Name) {
+  std::cout << "Checking " << Name << "\n";
+
+  // Make sure we have enough extra elements so we can be liberal with offsets.
+  const unsigned NumArrayElements = (InnerTC * (OuterTC + 1)) * 8;
+  std::unique_ptr<Ty[]> Input1(new Ty[NumArrayElements]);
+  std::unique_ptr<Ty[]> Reference(new Ty[NumArrayElements]);
+  std::unique_ptr<Ty[]> ToCheck(new Ty[NumArrayElements]);
+
+  auto CheckWithOffsetSecond = [&](int Offset) {
+    init_data(Input1, NumArrayElements);
+    for (unsigned i = 0; i < NumArrayElements; i++) {
+      Reference[i] = Input1[i];
+      ToCheck[i] = Input1[i];
+    }
+
+    // Run scalar function to generate reference output.
+    Ty *ReferenceStart = &Reference[NumArrayElements / 2];
+    ScalarFn(ReferenceStart + Offset, ReferenceStart, OuterTC, InnerTC);
+
+    // Run vector function to generate output to check.
+    Ty *StartPtr = &ToCheck[NumArrayElements / 2];
+    callThroughOptnone(VectorFn, StartPtr + Offset, StartPtr, OuterTC, InnerTC);
+
+    // Compare scalar and vector output.
+    check(Reference, ToCheck, NumArrayElements, Offset);
+  };
+
+  // With a nested loop, sometimes the runtime checks will fail and sometimes
+  // succeed. For example, with large offsets you'd expect for the first and
+  // last one or two executions of the inner loop there is no overlap.
+  for (int i = -(2 * (InnerTC + 1)); i <= (2 * (InnerTC + 1)); i++)
+    CheckWithOffsetSecond(i);
+}
+
+
 int main(void) {
   rng = std::mt19937(15);
 
   {
     DEFINE_SCALAR_AND_VECTOR_FN2(,
       for (unsigned i = 0; i < TC; i++)
         A[i] = B[i] + 10;
     );
rng = std::mt19937(15);
     checkOverlappingMemoryTwoRuntimeChecks<uint8_t>(
         ScalarFn, VectorFn, "1 read, 2 writes, simple indices, uint8_t");
     checkOverlappingMemoryTwoRuntimeChecks<uint32_t>(
         ScalarFn, VectorFn, "1 read, 2 writes, simple indices, uint32_t");
     checkOverlappingMemoryTwoRuntimeChecks<uint64_t>(
         ScalarFn, VectorFn, "1 read, 2 writes, simple indices, uint64_t");
   }
 
+  {
+    DEFINE_NESTED_SCALAR_AND_VECTOR_FN4(
+        auto X = B[(i * OuterTC) + j];
+        A[(i * (OuterTC + 1)) + j] = X;
+    );
+    checkOverlappingMemoryTwoRuntimeChecksNested<uint8_t>(
+        ScalarFn, VectorFn, 100, 100, "1 read, 1 write, nested loop (matching trip counts), uint8_t");
+    checkOverlappingMemoryTwoRuntimeChecksNested<uint32_t>(
+        ScalarFn, VectorFn, 100, 100, "1 read, 1 write, nested loop (matching trip counts), uint32_t");
+    checkOverlappingMemoryTwoRuntimeChecksNested<uint64_t>(
+        ScalarFn, VectorFn, 100, 100, "1 read, 1 write, nested loop (matching trip counts), uint64_t");
+
+    checkOverlappingMemoryTwoRuntimeChecksNested<uint8_t>(
+        ScalarFn, VectorFn, 100, 50, "1 read, 1 write, nested loop (different trip counts), uint8_t");
+    checkOverlappingMemoryTwoRuntimeChecksNested<uint32_t>(
+        ScalarFn, VectorFn, 100, 50, "1 read, 1 write, nested loop (different trip counts), uint32_t");
+    checkOverlappingMemoryTwoRuntimeChecksNested<uint64_t>(
+        ScalarFn, VectorFn, 100, 50, "1 read, 1 write, nested loop (different trip counts), uint64_t");
+  }
+
+  {
+    DEFINE_NESTED_SCALAR_AND_VECTOR_FN4(
+        auto X = B[(i * OuterTC) + j];
+        A[(i * (OuterTC + 1)) + j] += X;
+    );
+
+    checkOverlappingMemoryTwoRuntimeChecksNested<uint8_t>(
+        ScalarFn, VectorFn, 100, 100, "2 reads, 1 write, nested loop (matching trip counts), uint8_t");
+    checkOverlappingMemoryTwoRuntimeChecksNested<uint32_t>(
+        ScalarFn, VectorFn, 100, 100, "2 reads, 1 write, nested loop (matching trip counts), uint32_t");
+    checkOverlappingMemoryTwoRuntimeChecksNested<uint64_t>(
+        ScalarFn, VectorFn, 100, 100, "2 reads, 1 write, nested loop (matching trip counts), uint64_t");
+
+    checkOverlappingMemoryTwoRuntimeChecksNested<uint8_t>(
+        ScalarFn, VectorFn, 100, 50, "2 reads, 1 write, nested loop (different trip counts), uint8_t");
+    checkOverlappingMemoryTwoRuntimeChecksNested<uint32_t>(
+        ScalarFn, VectorFn, 100, 50, "2 reads, 1 write, nested loop (different trip counts), uint32_t");
+    checkOverlappingMemoryTwoRuntimeChecksNested<uint64_t>(
+        ScalarFn, VectorFn, 100, 50, "2 reads, 1 write, nested loop (different trip counts), uint64_t");
+  }
+
+  {
+    DEFINE_NESTED_SCALAR_AND_VECTOR_FN5(
+        auto X = B[(i * OuterTC) + j];
+        A[(i * (OuterTC + 1)) + j] = X;
+    );
+    checkOverlappingMemoryTwoRuntimeChecksNested<uint8_t>(
+        ScalarFn, VectorFn, 100, 100, "1 read, 1 write, nested loop (decreasing outer iv, matching trip counts), uint8_t");
+    checkOverlappingMemoryTwoRuntimeChecksNested<uint32_t>(
+        ScalarFn, VectorFn, 100, 100, "1 read, 1 write, nested loop (decreasing outer iv, matching trip counts), uint32_t");
+    checkOverlappingMemoryTwoRuntimeChecksNested<uint64_t>(
+        ScalarFn, VectorFn, 100, 100, "1 read, 1 write, nested loop (decreasing outer iv, matching trip counts), uint64_t");
+  }
+
+  {
+    DEFINE_NESTED_SCALAR_AND_VECTOR_FN5(
+        auto X = B[(i * OuterTC) + j];
+        A[(i * (OuterTC + 1)) + j] += X;
+    );
+
+    checkOverlappingMemoryTwoRuntimeChecksNested<uint8_t>(
+        ScalarFn, VectorFn, 100, 100, "2 reads, 1 write, nested loop (decreasing outer iv, matching trip counts), uint8_t");
+    checkOverlappingMemoryTwoRuntimeChecksNested<uint32_t>(
+        ScalarFn, VectorFn, 100, 100, "2 reads, 1 write, nested loop (decreasing outer iv, matching trip counts), uint32_t");
+    checkOverlappingMemoryTwoRuntimeChecksNested<uint64_t>(
+        ScalarFn, VectorFn, 100, 100, "2 reads, 1 write, nested loop (decreasing outer iv, matching trip counts), uint64_t");
+  }
+
   return 0;
 }

SingleSource/UnitTests/Vectorizer/runtime-checks.reference_output

 Checking 1 read, 1 write to invariant address, step 1, uint32_t
 Checking 1 read, 1 write to invariant address, step 1, uint64_t
 Checking 2 reads, 1 write, simple indices, uint32_t
 Checking 2 reads, 1 write, simple indices, uint8_t
 Checking 2 reads, 1 write, simple indices, uint64_t
 Checking 1 read, 2 writes, simple indices, uint8_t
 Checking 1 read, 2 writes, simple indices, uint32_t
 Checking 1 read, 2 writes, simple indices, uint64_t
+Checking 1 read, 1 write, nested loop (matching trip counts), uint8_t
+Checking 1 read, 1 write, nested loop (matching trip counts), uint32_t
+Checking 1 read, 1 write, nested loop (matching trip counts), uint64_t
+Checking 1 read, 1 write, nested loop (different trip counts), uint8_t
+Checking 1 read, 1 write, nested loop (different trip counts), uint32_t
+Checking 1 read, 1 write, nested loop (different trip counts), uint64_t
+Checking 2 reads, 1 write, nested loop (matching trip counts), uint8_t
+Checking 2 reads, 1 write, nested loop (matching trip counts), uint32_t
+Checking 2 reads, 1 write, nested loop (matching trip counts), uint64_t
+Checking 2 reads, 1 write, nested loop (different trip counts), uint8_t
+Checking 2 reads, 1 write, nested loop (different trip counts), uint32_t
+Checking 2 reads, 1 write, nested loop (different trip counts), uint64_t
+Checking 1 read, 1 write, nested loop (decreasing outer iv, matching trip counts), uint8_t
+Checking 1 read, 1 write, nested loop (decreasing outer iv, matching trip counts), uint32_t
+Checking 1 read, 1 write, nested loop (decreasing outer iv, matching trip counts), uint64_t
+Checking 2 reads, 1 write, nested loop (decreasing outer iv, matching trip counts), uint8_t
+Checking 2 reads, 1 write, nested loop (decreasing outer iv, matching trip counts), uint32_t
+Checking 2 reads, 1 write, nested loop (decreasing outer iv, matching trip counts), uint64_t
 exit 0