ffrankies updated this revision to Diff 329082.
ffrankies marked 6 inline comments as done.
ffrankies added a comment.

Rebased with the latest main branch to fix patch application errors.


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D72235/new/

https://reviews.llvm.org/D72235

Files:
  clang-tools-extra/clang-tidy/altera/AlteraTidyModule.cpp
  clang-tools-extra/clang-tidy/altera/CMakeLists.txt
  clang-tools-extra/clang-tidy/altera/UnrollLoopsCheck.cpp
  clang-tools-extra/clang-tidy/altera/UnrollLoopsCheck.h
  clang-tools-extra/docs/ReleaseNotes.rst
  clang-tools-extra/docs/clang-tidy/checks/altera-unroll-loops.rst
  clang-tools-extra/docs/clang-tidy/checks/list.rst
  clang-tools-extra/test/clang-tidy/checkers/altera-unroll-loops.cpp

Index: clang-tools-extra/test/clang-tidy/checkers/altera-unroll-loops.cpp
===================================================================
--- /dev/null
+++ clang-tools-extra/test/clang-tidy/checkers/altera-unroll-loops.cpp
@@ -0,0 +1,518 @@
+// RUN: %check_clang_tidy %s altera-unroll-loops %t -- -config="{CheckOptions: [{key: "altera-unroll-loops.MaxLoopIterations", value: 50}]}" -header-filter=.*
+// RUN: %check_clang_tidy -check-suffix=MULT %s altera-unroll-loops %t -- -config="{CheckOptions: [{key: "altera-unroll-loops.MaxLoopIterations", value: 5}]}" -header-filter=.* "--" -DMULT
+
+#ifdef MULT
+// For loops with *= and /= increments.
+void for_loop_mult_div_increments(int *A) {
+    // *=
+    #pragma unroll
+    for (int i = 2; i <= 32; i *= 2)
+        A[i]++;  // OK
+
+    #pragma unroll
+    for (int i = 2; i <= 64; i *= 2)
+// CHECK-MESSAGES-MULT: :[[@LINE-1]]:5: warning: loop likely has a large number of iterations and thus cannot be fully unrolled; to partially unroll this loop, use the '#pragma unroll <num>' directive [altera-unroll-loops]
+        A[i]++;  // Not OK
+
+    // /=
+    #pragma unroll
+    for (int i = 32; i >= 2; i /= 2)
+        A[i]++;  // OK
+
+    #pragma unroll
+    for (int i = 64; i >= 2; i /= 2)
+// CHECK-MESSAGES-MULT: :[[@LINE-1]]:5: warning: loop likely has a large number of iterations and thus cannot be fully unrolled; to partially unroll this loop, use the '#pragma unroll <num>' directive [altera-unroll-loops]
+        A[i]++;  // Not OK
+}
+#else
+// Cannot determine loop bounds for while loops.
+void while_loops(int *A) {
+    // Recommend unrolling loops that aren't already unrolled.
+    int j = 0;
+    while (j < 2000) {
+// CHECK-MESSAGES: :[[@LINE-1]]:5: warning: kernel performance could be improved by unrolling this loop with a '#pragma unroll' directive [altera-unroll-loops]
+        A[1] += j;
+        j++;
+    }
+
+    do {
+// CHECK-MESSAGES: :[[@LINE-1]]:5: warning: kernel performance could be improved by unrolling this loop with a '#pragma unroll' directive [altera-unroll-loops]
+        A[2] += j;
+        j++;
+    } while (j < 2000);
+
+    // If a while loop is fully unrolled, add a note recommending partial
+    // unrolling.
+    #pragma unroll
+    while (j < 2000) {
+// CHECK-MESSAGES: :[[@LINE-1]]:5: note: full unrolling requested, but loop bounds may not be known; to partially unroll this loop, use the '#pragma unroll <num>' directive
+        A[j]++;
+    }
+
+    #pragma unroll
+    do {
+// CHECK-MESSAGES: :[[@LINE-1]]:5: note: full unrolling requested, but loop bounds may not be known; to partially unroll this loop, use the '#pragma unroll <num>' directive
+        A[j]++;
+    } while (j < 2000);
+
+    // While loop is partially unrolled, no action needed.
+    #pragma unroll 4
+    while (j < 2000) {
+        A[j]++;
+    }
+
+    #pragma unroll 4
+    do {
+        A[j]++;
+    } while (j < 2000);
+}
+
+// Range-based for loops.
+void cxx_for_loops(int *A, int vectorSize) {
+    // Loop with known array size should be unrolled.
+    int a[] = { 0, 1, 2, 3, 4, 5 };
+    for (int k : a) {
+// CHECK-MESSAGES: :[[@LINE-1]]:5: warning: kernel performance could be improved by unrolling this loop with a '#pragma unroll' directive [altera-unroll-loops]
+        A[k]++;
+    }
+
+    // Loop with known size correctly unrolled.
+    #pragma unroll
+    for (int k : a) {
+        A[k]++;
+    }
+
+    // Loop with unknown size should be partially unrolled.
+    int b[vectorSize];
+    #pragma unroll
+    for (int k : b) {
+// CHECK-MESSAGES: :[[@LINE-1]]:5: warning: full unrolling requested, but loop bounds are not known; to partially unroll this loop, use the '#pragma unroll <num>' directive [altera-unroll-loops]
+        k++;
+    }
+
+    // Loop with unknown size correctly unrolled.
+    #pragma unroll 5
+    for (int k : b) {
+        k++;
+    }
+
+    // Loop with large size should be partially unrolled.
+    int c[51];
+    #pragma unroll
+    for (int k : c) {
+// CHECK-MESSAGES: :[[@LINE-1]]:5: warning: loop likely has a large number of iterations and thus cannot be fully unrolled; to partially unroll this loop, use the '#pragma unroll <num>' directive [altera-unroll-loops]
+        A[k]++;
+    }
+
+    // Loop with large size correctly unrolled.
+    #pragma unroll 5
+    for (int k : c) {
+        A[k]++;
+    }
+}
+
+// Simple for loops.
+void for_loops(int *A, int size) {
+    // Recommend unrolling loops that aren't already unrolled.
+    for (int i = 0; i < 2000; ++i) {
+// CHECK-MESSAGES: :[[@LINE-1]]:5: warning: kernel performance could be improved by unrolling this loop with a '#pragma unroll' directive [altera-unroll-loops]
+        A[0] += i;
+    }
+
+    // Loop with known size correctly unrolled.
+    #pragma unroll
+    for (int i = 0; i < 50; ++i) {
+        A[i]++;
+    }
+
+    // Loop with unknown size should be partially unrolled.
+    #pragma unroll
+    for (int i = 0; i < size; ++i) {
+// CHECK-MESSAGES: :[[@LINE-1]]:5: warning: full unrolling requested, but loop bounds are not known; to partially unroll this loop, use the '#pragma unroll <num>' directive [altera-unroll-loops]
+        A[i]++;
+    }
+
+    #pragma unroll
+    for (;;) {
+// CHECK-MESSAGES: :[[@LINE-1]]:5: warning: full unrolling requested, but loop bounds are not known; to partially unroll this loop, use the '#pragma unroll <num>' directive [altera-unroll-loops]
+        A[0]++;
+    }
+
+    int i = 0;
+    #pragma unroll
+    for (; i < size; ++i) {
+// CHECK-MESSAGES: :[[@LINE-1]]:5: warning: full unrolling requested, but loop bounds are not known; to partially unroll this loop, use the '#pragma unroll <num>' directive [altera-unroll-loops]
+        A[i]++;
+    }
+
+    #pragma unroll
+    for (int i = 0;; ++i) {
+// CHECK-MESSAGES: :[[@LINE-1]]:5: warning: full unrolling requested, but loop bounds are not known; to partially unroll this loop, use the '#pragma unroll <num>' directive [altera-unroll-loops]
+        A[i]++;
+    }
+
+    #pragma unroll
+    for (int i = 0; i < size;) {
+// CHECK-MESSAGES: :[[@LINE-1]]:5: warning: full unrolling requested, but loop bounds are not known; to partially unroll this loop, use the '#pragma unroll <num>' directive [altera-unroll-loops]
+        A[i]++;
+    }
+
+    #pragma unroll
+    for (int i = size; i < 50; ++i) {
+// CHECK-MESSAGES: :[[@LINE-1]]:5: warning: full unrolling requested, but loop bounds are not known; to partially unroll this loop, use the '#pragma unroll <num>' directive [altera-unroll-loops]
+        A[i]++;
+    }
+
+    #pragma unroll
+    for (int i = 0; true; ++i) {
+// CHECK-MESSAGES: :[[@LINE-1]]:5: warning: full unrolling requested, but loop bounds are not known; to partially unroll this loop, use the '#pragma unroll <num>' directive [altera-unroll-loops]
+        A[i]++;
+    }
+
+    #pragma unroll
+    for (int i = 0; i == i; ++i) {
+// CHECK-MESSAGES: :[[@LINE-1]]:5: warning: full unrolling requested, but loop bounds are not known; to partially unroll this loop, use the '#pragma unroll <num>' directive [altera-unroll-loops]
+        A[i]++;
+    }
+
+    // Loop with unknown size correctly unrolled.
+    #pragma unroll 5
+    for (int i = 0; i < size; ++i) {
+        A[i]++;
+    }
+
+    // Loop with large size should be partially unrolled.
+    #pragma unroll
+    for (int i = 0; i < 51; ++i) {
+// CHECK-MESSAGES: :[[@LINE-1]]:5: warning: loop likely has a large number of iterations and thus cannot be fully unrolled; to partially unroll this loop, use the '#pragma unroll <num>' directive [altera-unroll-loops]
+        A[i]++;
+    }
+
+    // Loop with large size correctly unrolled.
+    #pragma unroll 5
+    for (int i = 0; i < 51; ++i) {
+        A[i]++;
+    }
+}
+
+// For loops with different increments.
+void for_loop_increments(int *A) {
+    // ++
+    #pragma unroll
+    for (int i = 0; i < 50; ++i)
+        A[i]++;  // OK
+
+    #pragma unroll
+    for (int i = 0; i < 51; ++i)
+// CHECK-MESSAGES: :[[@LINE-1]]:5: warning: loop likely has a large number of iterations and thus cannot be fully unrolled; to partially unroll this loop, use the '#pragma unroll <num>' directive [altera-unroll-loops]
+        A[i]++;  // Not OK
+
+    // --
+    #pragma unroll
+    for (int i = 50; i > 0; --i)
+        A[i]++;  // OK
+
+    #pragma unroll
+    for (int i = 51; i > 0; --i)
+// CHECK-MESSAGES: :[[@LINE-1]]:5: warning: loop likely has a large number of iterations and thus cannot be fully unrolled; to partially unroll this loop, use the '#pragma unroll <num>' directive [altera-unroll-loops]
+        A[i]++;  // Not OK
+
+    // +=
+    #pragma unroll
+    for (int i = 0; i < 100; i += 2)
+        A[i]++;  // OK
+
+    #pragma unroll
+    for (int i = 0; i < 101; i += 2)
+// CHECK-MESSAGES: :[[@LINE-1]]:5: warning: loop likely has a large number of iterations and thus cannot be fully unrolled; to partially unroll this loop, use the '#pragma unroll <num>' directive [altera-unroll-loops]
+        A[i]++;  // Not OK
+
+    // -=
+    #pragma unroll
+    for (int i = 100; i > 0; i -= 2)
+        A[i]++;  // OK
+
+    #pragma unroll
+    for (int i = 101; i > 0; i -= 2)
+// CHECK-MESSAGES: :[[@LINE-1]]:5: warning: loop likely has a large number of iterations and thus cannot be fully unrolled; to partially unroll this loop, use the '#pragma unroll <num>' directive [altera-unroll-loops]
+        A[i]++;  // Not OK
+
+}
+
+// Inner loops should be unrolled.
+void nested_simple_loops(int *A) {
+    for (int i = 0; i < 1000; ++i) {
+        for (int j = 0; j < 2000; ++j) {
+// CHECK-MESSAGES: :[[@LINE-1]]:9: warning: kernel performance could be improved by unrolling this loop with a '#pragma unroll' directive [altera-unroll-loops]
+            A[0] += i + j;
+        }
+    }
+
+    for (int i = 0; i < 1000; ++i) {
+        int j = 0;
+        while (j < 2000) {
+// CHECK-MESSAGES: :[[@LINE-1]]:9: warning: kernel performance could be improved by unrolling this loop with a '#pragma unroll' directive [altera-unroll-loops]
+            A[1] += i + j;
+            j++;
+        }
+    }
+
+    for (int i = 0; i < 1000; ++i) {
+        int j = 0;
+        do {
+// CHECK-MESSAGES: :[[@LINE-1]]:9: warning: kernel performance could be improved by unrolling this loop with a '#pragma unroll' directive [altera-unroll-loops]
+            A[2] += i + j;
+            j++;
+        } while (j < 2000);
+    }
+
+    int i = 0;
+    while (i < 1000) {
+        for (int j = 0; j < 2000; ++j) {
+// CHECK-MESSAGES: :[[@LINE-1]]:9: warning: kernel performance could be improved by unrolling this loop with a '#pragma unroll' directive [altera-unroll-loops]
+            A[3] += i + j;
+        }
+        i++;
+    }
+
+    i = 0;
+    while (i < 1000) {
+        int j = 0;
+        while (j < 2000) {
+// CHECK-MESSAGES: :[[@LINE-1]]:9: warning: kernel performance could be improved by unrolling this loop with a '#pragma unroll' directive [altera-unroll-loops]
+            A[4] += i + j;
+            j++;
+        }
+        i++;
+    }
+
+    i = 0;
+    while (i < 1000) {
+        int j = 0;
+        do {
+// CHECK-MESSAGES: :[[@LINE-1]]:9: warning: kernel performance could be improved by unrolling this loop with a '#pragma unroll' directive [altera-unroll-loops]
+            A[5] += i + j;
+            j++;
+        } while (j < 2000);
+        i++;
+    }
+
+    i = 0;
+    do {
+        for (int j = 0; j < 2000; ++j) {
+// CHECK-MESSAGES: :[[@LINE-1]]:9: warning: kernel performance could be improved by unrolling this loop with a '#pragma unroll' directive [altera-unroll-loops]
+            A[6] += i + j;
+        }
+        i++;
+    } while (i < 1000);
+
+    i = 0;
+    do {
+        int j = 0;
+        while (j < 2000) {
+// CHECK-MESSAGES: :[[@LINE-1]]:9: warning: kernel performance could be improved by unrolling this loop with a '#pragma unroll' directive [altera-unroll-loops]
+            A[7] += i + j;
+            j++;
+        }
+        i++;
+    } while (i < 1000);
+
+    i = 0;
+    do {
+        int j = 0;
+        do {
+// CHECK-MESSAGES: :[[@LINE-1]]:9: warning: kernel performance could be improved by unrolling this loop with a '#pragma unroll' directive [altera-unroll-loops]
+            A[8] += i + j;
+            j++;
+        } while (j < 2000);
+        i++;
+    } while (i < 1000);
+
+    for (int i = 0; i < 100; ++i) {
+// CHECK-MESSAGES: :[[@LINE-1]]:5: warning: kernel performance could be improved by unrolling this loop with a '#pragma unroll' directive [altera-unroll-loops]
+        A[i]++;
+    }
+
+    i = 0;
+    while (i < 100) {
+// CHECK-MESSAGES: :[[@LINE-1]]:5: warning: kernel performance could be improved by unrolling this loop with a '#pragma unroll' directive [altera-unroll-loops]
+        i++;
+    }
+
+    i = 0;
+    do {
+// CHECK-MESSAGES: :[[@LINE-1]]:5: warning: kernel performance could be improved by unrolling this loop with a '#pragma unroll' directive [altera-unroll-loops]
+        i++;
+    } while (i < 100);
+
+}
+
+// These loops are all correctly unrolled.
+void unrolled_nested_simple_loops(int *A) {
+    for (int i = 0; i < 1000; ++i) {
+        #pragma unroll
+        for (int j = 0; j < 50; ++j) {
+            A[0] += i + j;
+        }
+    }
+
+    for (int i = 0; i < 1000; ++i) {
+        int j = 0;
+        #pragma unroll 5
+        while (j < 50) {
+            A[1] += i + j;
+            j++;
+        }
+    }
+
+    for (int i = 0; i < 1000; ++i) {
+        int j = 0;
+        #pragma unroll 5
+        do {
+            A[2] += i + j;
+            j++;
+        } while (j < 50);
+    }
+
+    int i = 0;
+    while (i < 1000) {
+        #pragma unroll
+        for (int j = 0; j < 50; ++j) {
+            A[3] += i + j;
+        }
+        i++;
+    }
+
+    i = 0;
+    while (i < 1000) {
+        int j = 0;
+        #pragma unroll 5
+        while (50 > j) {
+            A[4] += i + j;
+            j++;
+        }
+        i++;
+    }
+
+    i = 0;
+    while (1000 > i) {
+        int j = 0;
+        #pragma unroll 5
+        do {
+            A[5] += i + j;
+            j++;
+        } while (j < 50);
+        i++;
+    }
+
+    i = 0;
+    do {
+        #pragma unroll
+        for (int j = 0; j < 50; ++j) {
+            A[6] += i + j;
+        }
+        i++;
+    } while (i < 1000);
+
+    i = 0;
+    do {
+        int j = 0;
+        #pragma unroll 5
+        while (j < 50) {
+            A[7] += i + j;
+            j++;
+        }
+        i++;
+    } while (i < 1000);
+
+    i = 0;
+    do {
+        int j = 0;
+        #pragma unroll 5
+        do {
+            A[8] += i + j;
+            j++;
+        } while (j < 50);
+        i++;
+    } while (i < 1000);
+}
+
+// These inner loops are large and should be partially unrolled.
+void unrolled_nested_simple_loops_large_num_iterations(int *A) {
+    for (int i = 0; i < 1000; ++i) {
+        #pragma unroll
+        for (int j = 0; j < 51; ++j) {
+// CHECK-MESSAGES: :[[@LINE-1]]:9: warning: loop likely has a large number of iterations and thus cannot be fully unrolled; to partially unroll this loop, use the '#pragma unroll <num>' directive [altera-unroll-loops]
+            A[0] += i + j;
+        }
+    }
+
+    int i = 0;
+    while (i < 1000) {
+        #pragma unroll
+        for (int j = 0; j < 51; ++j) {
+// CHECK-MESSAGES: :[[@LINE-1]]:9: warning: loop likely has a large number of iterations and thus cannot be fully unrolled; to partially unroll this loop, use the '#pragma unroll <num>' directive [altera-unroll-loops]
+            A[3] += i + j;
+        }
+        i++;
+    }
+
+    i = 0;
+    do {
+        #pragma unroll
+        for (int j = 0; j < 51; ++j) {
+// CHECK-MESSAGES: :[[@LINE-1]]:9: warning: loop likely has a large number of iterations and thus cannot be fully unrolled; to partially unroll this loop, use the '#pragma unroll <num>' directive [altera-unroll-loops]
+            A[6] += i + j;
+        }
+        i++;
+    } while (i < 1000);
+
+    i = 0;
+    do {
+        int j = 0;
+        #pragma unroll
+        do {
+// CHECK-MESSAGES: :[[@LINE-1]]:9: note: full unrolling requested, but loop bounds may not be known; to partially unroll this loop, use the '#pragma unroll <num>' directive
+            A[8] += i + j;
+            j++;
+        } while (j < 51);
+        i++;
+    } while (i < 1000);
+
+    i = 0;
+    int a[51];
+    do {
+        #pragma unroll
+        for (int k : a) {
+// CHECK-MESSAGES: :[[@LINE-1]]:9: warning: loop likely has a large number of iterations and thus cannot be fully unrolled; to partially unroll this loop, use the '#pragma unroll <num>' directive [altera-unroll-loops]
+            A[k]++;
+        }
+    } while (i < 1000);
+}
+
+// These loops have unknown bounds and should be partially unrolled.
+void fully_unrolled_unknown_bounds(int vectorSize) {
+    int someVector[101];
+
+    // There is no loop condition
+    #pragma unroll
+    for (;;) {
+// CHECK-MESSAGES: :[[@LINE-1]]:5: warning: full unrolling requested, but loop bounds are not known; to partially unroll this loop, use the '#pragma unroll <num>' directive [altera-unroll-loops]
+        someVector[0]++;
+    }
+
+    #pragma unroll
+    for (int i = 0; 1 < 5; ++i) {
+// CHECK-MESSAGES: :[[@LINE-1]]:5: warning: full unrolling requested, but loop bounds are not known; to partially unroll this loop, use the '#pragma unroll <num>' directive [altera-unroll-loops]
+        someVector[i]++;
+    }
+
+    // Both sides are value-dependent
+    #pragma unroll
+    for (int i = 0; i < vectorSize; ++i) {
+// CHECK-MESSAGES: :[[@LINE-1]]:5: warning: full unrolling requested, but loop bounds are not known; to partially unroll this loop, use the '#pragma unroll <num>' directive [altera-unroll-loops]
+        someVector[i]++;
+    }
+}
+#endif
+// There are no fix-its for this check
Index: clang-tools-extra/docs/clang-tidy/checks/list.rst
===================================================================
--- clang-tools-extra/docs/clang-tidy/checks/list.rst
+++ clang-tools-extra/docs/clang-tidy/checks/list.rst
@@ -33,6 +33,7 @@
    `altera-kernel-name-restriction <altera-kernel-name-restriction.html>`_,
    `altera-single-work-item-barrier <altera-single-work-item-barrier.html>`_,
    `altera-struct-pack-align <altera-struct-pack-align.html>`_, "Yes"
+   `altera-unroll-loops <altera-unroll-loops.html>`_,
    `android-cloexec-accept <android-cloexec-accept.html>`_, "Yes"
    `android-cloexec-accept4 <android-cloexec-accept4.html>`_,
    `android-cloexec-creat <android-cloexec-creat.html>`_, "Yes"
Index: clang-tools-extra/docs/clang-tidy/checks/altera-unroll-loops.rst
===================================================================
--- /dev/null
+++ clang-tools-extra/docs/clang-tidy/checks/altera-unroll-loops.rst
@@ -0,0 +1,105 @@
+.. title:: clang-tidy - altera-unroll-loops
+
+altera-unroll-loops
+===================
+
+Finds inner loops that have not been unrolled, as well as fully unrolled loops
+with unknown loop bounds or a large number of iterations.
+
+Unrolling inner loops could improve the performance of OpenCL kernels. However,
+if they have unknown loop bounds or a large number of iterations, they cannot
+be fully unrolled, and should be partially unrolled.
+
+Notes:
+
+- This check is unable to determine the number of iterations in a ``while`` or
+  ``do..while`` loop; hence if such a loop is fully unrolled, a note is emitted
+  advising the user to partially unroll instead.
+
+- In ``for`` loops, our check only works with simple arithmetic increments (
+  ``+``, ``-``, ``*``, ``/``). For all other increments, partial unrolling is
+  advised.
+
+- Depending on the exit condition, the calculations for determining if the
+  number of iterations is large may be off by 1. This should not be an issue
+  since the cut-off is generally arbitrary.
+
+Based on the `Altera SDK for OpenCL: Best Practices Guide
+<https://www.altera.com/en_US/pdfs/literature/hb/opencl-sdk/aocl_optimization_guide.pdf>`_.
+
+.. code-block:: c++
+
+   for (int i = 0; i < 10; i++) {  // ok: outer loops should not be unrolled
+      int j = 0;
+      do {  // warning: this inner do..while loop should be unrolled
+         j++;
+      } while (j < 15);
+
+      int k = 0;
+      #pragma unroll
+      while (k < 20) {  // ok: this inner loop is already unrolled
+         k++;
+      }
+   }
+
+   int A[1000];
+   #pragma unroll
+   // warning: this loop is large and should be partially unrolled
+   for (int a : A) {
+      printf("%d", a);
+   }
+
+   #pragma unroll 5
+   // ok: this loop is large, but is partially unrolled
+   for (int a : A) {
+      printf("%d", a);
+   }
+
+   #pragma unroll
+   // warning: this loop is large and should be partially unrolled
+   for (int i = 0; i < 1000; ++i) {
+      printf("%d", i);
+   }
+
+   #pragma unroll 5
+   // ok: this loop is large, but is partially unrolled
+   for (int i = 0; i < 1000; ++i) {
+      printf("%d", i);
+   }
+
+   #pragma unroll
+   // warning: << operator not supported, recommend partial unrolling
+   for (int i = 0; i < 1000; i<<1) {
+      printf("%d", i);
+   }
+
+   std::vector<int> someVector (100, 0);
+   int i = 0;
+   #pragma unroll
+   // note: loop may be large, recommend partial unrolling
+   while (i < someVector.size()) {
+      someVector[i]++;
+   }
+
+   #pragma unroll
+   // note: loop may be large, recommend partial unrolling
+   while (true) {
+      printf("In loop");
+   }
+
+   #pragma unroll 5
+   // ok: loop may be large, but is partially unrolled
+   while (i < someVector.size()) {
+      someVector[i]++;
+   }
+
+Options
+-------
+
+.. option:: MaxLoopIterations
+
+   Defines the maximum number of loop iterations that a fully unrolled loop
+   can have. By default, it is set to `100`.
+
+   In practice, this refers to the integer value of the upper bound
+   within the loop statement's condition expression.
Index: clang-tools-extra/docs/ReleaseNotes.rst
===================================================================
--- clang-tools-extra/docs/ReleaseNotes.rst
+++ clang-tools-extra/docs/ReleaseNotes.rst
@@ -83,6 +83,12 @@
   Finds ``pthread_setcanceltype`` function calls where a thread's cancellation
   type is set to asynchronous.
 
+- New :doc:`altera-unroll-loops
+  <clang-tidy/checks/altera-unroll-loops>` check.
+
+  Finds inner loops that have not been unrolled, as well as fully unrolled
+  loops with unknown loops bounds or a large number of iterations.
+
 - New :doc:`cppcoreguidelines-prefer-member-initializer
   <clang-tidy/checks/cppcoreguidelines-prefer-member-initializer>` check.
 
Index: clang-tools-extra/clang-tidy/altera/UnrollLoopsCheck.h
===================================================================
--- /dev/null
+++ clang-tools-extra/clang-tidy/altera/UnrollLoopsCheck.h
@@ -0,0 +1,78 @@
+//===--- UnrollLoopsCheck.h - clang-tidy ------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_ALTERA_UNROLL_LOOPS_CHECK_H
+#define LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_ALTERA_UNROLL_LOOPS_CHECK_H
+
+#include "../ClangTidyCheck.h"
+
+namespace clang {
+namespace tidy {
+namespace altera {
+
+/// Finds inner loops that have not been unrolled, as well as fully unrolled
+/// loops with unknown loop bounds or a large number of iterations.
+///
+/// Unrolling inner loops could improve the performance of OpenCL kernels.
+/// However, if they have unknown loop bounds or a large number of iterations,
+/// they cannot be fully unrolled, and should be partially unrolled.
+///
+/// For the user-facing documentation see:
+/// http://clang.llvm.org/extra/clang-tidy/checks/altera-unroll-loops.html
+class UnrollLoopsCheck : public ClangTidyCheck {
+public:
+  UnrollLoopsCheck(StringRef Name, ClangTidyContext *Context);
+  void registerMatchers(ast_matchers::MatchFinder *Finder) override;
+  void check(const ast_matchers::MatchFinder::MatchResult &Result) override;
+
+private:
+  /// Recommend partial unrolling if number of loop iterations is greater than
+  /// MaxLoopIterations.
+  const unsigned MaxLoopIterations;
+  /// The kind of unrolling, if any, applied to a given loop.
+  enum UnrollType {
+    // This loop has no #pragma unroll directive associated with it.
+    NotUnrolled,
+    // This loop has a #pragma unroll directive associated with it.
+    FullyUnrolled,
+    // This loop has a #pragma unroll <num> directive associated with it.
+    PartiallyUnrolled
+  };
+  /// Attempts to extract an integer value from either side of the
+  /// BinaryOperator. Returns true and saves the result to &value if successful,
+  /// returns false otherwise.
+  bool extractValue(int &value, const BinaryOperator *Op,
+                    const ASTContext *Context);
+  /// Returns true if the given loop statement has a large number of iterations,
+  /// as determined by the integer value in the loop's condition expression,
+  /// if one exists.
+  bool hasLargeNumIterations(const Stmt *Statement,
+                             const IntegerLiteral *CXXLoopBound,
+                             const ASTContext *Context);
+  /// Checks one hand side of the binary operator to ascertain if the upper
+  /// bound on the number of loops is greater than max_loop_iterations or not.
+  /// If the expression is not evaluatable or not an integer, returns false.
+  bool exprHasLargeNumIterations(const Expr *Expression,
+                                 const ASTContext *Context);
+  /// Returns the type of unrolling, if any, associated with the given
+  /// statement.
+  enum UnrollType unrollType(const Stmt *Statement, ASTContext *Context);
+  /// Returns the condition expression within a given for statement. If there is
+  /// none, or if the Statement is not a loop, then returns a NULL pointer.
+  const Expr *getCondExpr(const Stmt *Statement);
+  /// Returns True if the loop statement has known bounds.
+  bool hasKnownBounds(const Stmt *Statement, const IntegerLiteral *CXXLoopBound,
+                      const ASTContext *Context);
+  void storeOptions(ClangTidyOptions::OptionMap &Opts);
+};
+
+} // namespace altera
+} // namespace tidy
+} // namespace clang
+
+#endif // LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_ALTERA_UNROLL_LOOPS_CHECK_H
Index: clang-tools-extra/clang-tidy/altera/UnrollLoopsCheck.cpp
===================================================================
--- /dev/null
+++ clang-tools-extra/clang-tidy/altera/UnrollLoopsCheck.cpp
@@ -0,0 +1,277 @@
+//===--- UnrollLoopsCheck.cpp - clang-tidy --------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "UnrollLoopsCheck.h"
+#include "clang/AST/APValue.h"
+#include "clang/AST/ASTContext.h"
+#include "clang/AST/ASTTypeTraits.h"
+#include "clang/AST/OperationKinds.h"
+#include "clang/AST/ParentMapContext.h"
+#include "clang/ASTMatchers/ASTMatchFinder.h"
+#include <math.h>
+
+using namespace clang::ast_matchers;
+
+namespace clang {
+namespace tidy {
+namespace altera {
+
+UnrollLoopsCheck::UnrollLoopsCheck(StringRef Name, ClangTidyContext *Context)
+    : ClangTidyCheck(Name, Context),
+      MaxLoopIterations(Options.get("MaxLoopIterations", 100U)) {}
+
+void UnrollLoopsCheck::registerMatchers(MatchFinder *Finder) {
+  const auto HasLoopBound = hasDescendant(
+      varDecl(allOf(matchesName("__end*"),
+                    hasDescendant(integerLiteral().bind("cxx_loop_bound")))));
+  const auto CXXForRangeLoop =
+      cxxForRangeStmt(anyOf(HasLoopBound, unless(HasLoopBound)));
+  const auto AnyLoop = anyOf(forStmt(), whileStmt(), doStmt(), CXXForRangeLoop);
+  Finder->addMatcher(
+      stmt(allOf(AnyLoop, unless(hasDescendant(stmt(AnyLoop))))).bind("loop"),
+      this);
+}
+
+void UnrollLoopsCheck::check(const MatchFinder::MatchResult &Result) {
+  const auto *Loop = Result.Nodes.getNodeAs<Stmt>("loop");
+  const auto *CXXLoopBound =
+      Result.Nodes.getNodeAs<IntegerLiteral>("cxx_loop_bound");
+  const ASTContext *Context = Result.Context;
+  switch (unrollType(Loop, Result.Context)) {
+  case NotUnrolled:
+    diag(Loop->getBeginLoc(),
+         "kernel performance could be improved by unrolling this loop with a "
+         "'#pragma unroll' directive");
+    break;
+  case PartiallyUnrolled:
+    // Loop already partially unrolled, do nothing.
+    break;
+  case FullyUnrolled:
+    if (hasKnownBounds(Loop, CXXLoopBound, Context)) {
+      if (hasLargeNumIterations(Loop, CXXLoopBound, Context)) {
+        diag(Loop->getBeginLoc(),
+             "loop likely has a large number of iterations and thus "
+             "cannot be fully unrolled; to partially unroll this loop, use "
+             "the '#pragma unroll <num>' directive");
+        return;
+      }
+      return;
+    }
+    if (isa<WhileStmt>(Loop) || isa<DoStmt>(Loop)) {
+      diag(Loop->getBeginLoc(),
+           "full unrolling requested, but loop bounds may not be known; to "
+           "partially unroll this loop, use the '#pragma unroll <num>' "
+           "directive",
+           DiagnosticIDs::Note);
+      break;
+    }
+    diag(Loop->getBeginLoc(),
+         "full unrolling requested, but loop bounds are not known; to "
+         "partially unroll this loop, use the '#pragma unroll <num>' "
+         "directive");
+    break;
+  }
+}
+
+enum UnrollLoopsCheck::UnrollType
+UnrollLoopsCheck::unrollType(const Stmt *Statement, ASTContext *Context) {
+  const clang::DynTypedNodeList Parents = Context->getParents<Stmt>(*Statement);
+  for (const clang::DynTypedNode &Parent : Parents) {
+    const auto *ParentStmt = Parent.get<AttributedStmt>();
+    if (!ParentStmt)
+      continue;
+    for (const Attr *Attribute : ParentStmt->getAttrs()) {
+      const auto *LoopHint = dyn_cast<LoopHintAttr>(Attribute);
+      if (!LoopHint)
+        continue;
+      switch (LoopHint->getState()) {
+      case LoopHintAttr::Numeric:
+        return PartiallyUnrolled;
+      case LoopHintAttr::Disable:
+        return NotUnrolled;
+      case LoopHintAttr::Full:
+        return FullyUnrolled;
+      case LoopHintAttr::Enable:
+        return FullyUnrolled;
+      case LoopHintAttr::AssumeSafety:
+        return NotUnrolled;
+      }
+    }
+  }
+  return NotUnrolled;
+}
+
+bool UnrollLoopsCheck::hasKnownBounds(const Stmt *Statement,
+                                      const IntegerLiteral *CXXLoopBound,
+                                      const ASTContext *Context) {
+  if (isa<CXXForRangeStmt>(Statement)) {
+    if (CXXLoopBound)
+      return true;
+    return false;
+  }
+  // Too many possibilities in a while statement, so always recommend partial
+  // unrolling for these.
+  if (isa<WhileStmt>(Statement) || isa<DoStmt>(Statement))
+    return false;
+  // The last loop type is a for loop.
+  const auto *ForLoop = dyn_cast<ForStmt>(Statement);
+  if (!ForLoop)
+    llvm_unreachable("Unknown loop");
+  const Stmt *Initializer = ForLoop->getInit();
+  const Expr *Conditional = ForLoop->getCond();
+  const Expr *Increment = ForLoop->getInc();
+  if (!Initializer || !Conditional || !Increment)
+    return false;
+  // If the loop variable value isn't known, loop bounds are unknown.
+  if (const auto *InitDeclStatement = dyn_cast<DeclStmt>(Initializer)) {
+    if (const auto *VariableDecl =
+            dyn_cast<VarDecl>(InitDeclStatement->getSingleDecl())) {
+      APValue *Evaluation = VariableDecl->evaluateValue();
+      if (!Evaluation || !Evaluation->hasValue())
+        return false;
+    }
+  }
+  // If increment is unary and not one of ++ and --, loop bounds are unknown.
+  if (const auto *Op = dyn_cast<UnaryOperator>(Increment))
+    if (!Op->isIncrementDecrementOp())
+      return false;
+
+  if (isa<BinaryOperator>(Conditional)) {
+    const auto *BinaryOp = dyn_cast<BinaryOperator>(Conditional);
+    const Expr *LHS = BinaryOp->getLHS();
+    const Expr *RHS = BinaryOp->getRHS();
+    // If both sides are value dependent or constant, loop bounds are unknown.
+    return LHS->isEvaluatable(*Context) != RHS->isEvaluatable(*Context);
+  }
+  return false; // If it's not a binary operator, loop bounds are unknown.
+}
+
+const Expr *UnrollLoopsCheck::getCondExpr(const Stmt *Statement) {
+  if (const auto *ForLoop = dyn_cast<ForStmt>(Statement))
+    return ForLoop->getCond();
+  if (const auto *WhileLoop = dyn_cast<WhileStmt>(Statement))
+    return WhileLoop->getCond();
+  if (const auto *DoWhileLoop = dyn_cast<DoStmt>(Statement))
+    return DoWhileLoop->getCond();
+  if (const auto *CXXRangeLoop = dyn_cast<CXXForRangeStmt>(Statement))
+    return CXXRangeLoop->getCond();
+  llvm_unreachable("Unknown loop");
+}
+
+bool UnrollLoopsCheck::hasLargeNumIterations(const Stmt *Statement,
+                                             const IntegerLiteral *CXXLoopBound,
+                                             const ASTContext *Context) {
+  // Because hasKnownBounds is called before this, if this is true, then
+  // CXXLoopBound is also matched.
+  if (isa<CXXForRangeStmt>(Statement)) {
+    const auto *LoopBoundExpr = dyn_cast<Expr>(CXXLoopBound);
+    return exprHasLargeNumIterations(LoopBoundExpr, Context);
+  }
+  const auto *ForLoop = dyn_cast<ForStmt>(Statement);
+  if (!ForLoop)
+    llvm_unreachable("Unknown loop");
+  const Stmt *Initializer = ForLoop->getInit();
+  const Expr *Conditional = ForLoop->getCond();
+  const Expr *Increment = ForLoop->getInc();
+  int InitValue;
+  // If the loop variable value isn't known, we can't know the loop bounds.
+  if (const auto *InitDeclStatement = dyn_cast<DeclStmt>(Initializer)) {
+    if (const auto *VariableDecl =
+            dyn_cast<VarDecl>(InitDeclStatement->getSingleDecl())) {
+      APValue *Evaluation = VariableDecl->evaluateValue();
+      if (!Evaluation || !Evaluation->isInt())
+        return true;
+      InitValue = Evaluation->getInt().getExtValue();
+    }
+  }
+  if (!isa<BinaryOperator>(Conditional))
+    llvm_unreachable("Conditional is not a binary operator");
+  int EndValue;
+  const auto *BinaryOp = dyn_cast<BinaryOperator>(Conditional);
+  if (!extractValue(EndValue, BinaryOp, Context))
+    return true;
+
+  double Iterations;
+
+  // If increment is unary and not one of ++, --, we can't know the loop bounds.
+  if (const auto *Op = dyn_cast<UnaryOperator>(Increment)) {
+    if (Op->isIncrementOp())
+      Iterations = EndValue - InitValue;
+    else if (Op->isDecrementOp())
+      Iterations = InitValue - EndValue;
+    else
+      llvm_unreachable("Unary operator neither increment nor decrement");
+  }
+
+  // If increment is binary and not one of +, -, *, /, we can't know the loop
+  // bounds.
+  if (const auto *Op = dyn_cast<BinaryOperator>(Increment)) {
+    int ConstantValue;
+    if (!extractValue(ConstantValue, Op, Context))
+      return true;
+    switch (Op->getOpcode()) {
+    case (BO_AddAssign):
+      Iterations = ceil(float(EndValue - InitValue) / ConstantValue);
+      break;
+    case (BO_SubAssign):
+      Iterations = ceil(float(InitValue - EndValue) / ConstantValue);
+      break;
+    case (BO_MulAssign):
+      Iterations = 1 + (log(EndValue) - log(InitValue)) / log(ConstantValue);
+      break;
+    case (BO_DivAssign):
+      Iterations = 1 + (log(InitValue) - log(EndValue)) / log(ConstantValue);
+      break;
+    default:
+      // All other operators are not handled; assume large bounds.
+      return true;
+    }
+  }
+  return Iterations > MaxLoopIterations;
+}
+
+bool UnrollLoopsCheck::extractValue(int &value, const BinaryOperator *Op,
+                                    const ASTContext *Context) {
+  const Expr *LHS = Op->getLHS();
+  const Expr *RHS = Op->getRHS();
+  Expr::EvalResult Result;
+  if (LHS->isEvaluatable(*Context))
+    LHS->EvaluateAsRValue(Result, *Context);
+  else if (RHS->isEvaluatable(*Context))
+    RHS->EvaluateAsRValue(Result, *Context);
+  else
+    return false; // Cannot evalue either side.
+  if (!Result.Val.isInt())
+    return false; // Cannot check number of iterations, return false to be
+                  // safe.
+  value = Result.Val.getInt().getExtValue();
+  return true;
+}
+
+bool UnrollLoopsCheck::exprHasLargeNumIterations(const Expr *Expression,
+                                                 const ASTContext *Context) {
+  Expr::EvalResult Result;
+  if (Expression->EvaluateAsRValue(Result, *Context)) {
+    if (!Result.Val.isInt())
+      return false; // Cannot check number of iterations, return false to be
+                    // safe.
+    // The following assumes values go from 0 to Val in increments of 1.
+    return Result.Val.getInt() > MaxLoopIterations;
+  }
+  // Cannot evaluate Expression as an r-value, so cannot check number of
+  // iterations.
+  return false;
+}
+
+void UnrollLoopsCheck::storeOptions(ClangTidyOptions::OptionMap &Opts) {
+  Options.store(Opts, "MaxLoopIterations", MaxLoopIterations);
+}
+
+} // namespace altera
+} // namespace tidy
+} // namespace clang
Index: clang-tools-extra/clang-tidy/altera/CMakeLists.txt
===================================================================
--- clang-tools-extra/clang-tidy/altera/CMakeLists.txt
+++ clang-tools-extra/clang-tidy/altera/CMakeLists.txt
@@ -8,6 +8,7 @@
   KernelNameRestrictionCheck.cpp
   SingleWorkItemBarrierCheck.cpp
   StructPackAlignCheck.cpp
+  UnrollLoopsCheck.cpp
 
   LINK_LIBS
   clangTidy
Index: clang-tools-extra/clang-tidy/altera/AlteraTidyModule.cpp
===================================================================
--- clang-tools-extra/clang-tidy/altera/AlteraTidyModule.cpp
+++ clang-tools-extra/clang-tidy/altera/AlteraTidyModule.cpp
@@ -12,6 +12,7 @@
 #include "KernelNameRestrictionCheck.h"
 #include "SingleWorkItemBarrierCheck.h"
 #include "StructPackAlignCheck.h"
+#include "UnrollLoopsCheck.h"
 
 using namespace clang::ast_matchers;
 
@@ -28,6 +29,8 @@
         "altera-single-work-item-barrier");
     CheckFactories.registerCheck<StructPackAlignCheck>(
         "altera-struct-pack-align");
+    CheckFactories.registerCheck<UnrollLoopsCheck>(
+        "altera-unroll-loops");
   }
 };
 
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

Reply via email to