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
