[clang-tidy] Add performance-inefficient-array-traversal check

[njames93]

Summary

Adds a check that detects 2D array traversals where the array is traversed column wise instead of row wise.
These patterns harm cache performance as well as prevent auto-vectorisation opportunities.

[Eugene.Zelenko]

clang-tools-extra/clang-tidy/performance/InefficientArrayTraversalCheck.cpp

60

I think will be reasonable to check for += and -=.

clang-tools-extra/docs/ReleaseNotes.rst

121

Please highlight for with double back-ticks. Same in documentation.

clang-tools-extra/docs/clang-tidy/checks/performance-inefficient-array-traversal.rst

16

Excessive newline.

27

Excessive newline.

[njames93]

Address comments

[njames93]

clang-tools-extra/clang-tidy/performance/InefficientArrayTraversalCheck.cpp

64

Thoughts on this, prefetchers are often able to detect strided access so is forcing increment to be 1 removing potential functionality.

92

Any ideas on a nicer way to say this? I feel like this message isn't as descriptive as I'd like, and non-native English speakers could struggle to understand it.

[Eugene.Zelenko]

clang-tools-extra/clang-tidy/performance/InefficientArrayTraversalCheck.cpp

64

Theoretically index changes may be other than 1. For example, in some electronic simulation each block/device store matrix indexes to contribute (but sparse, not dense, matrix is used). It'll be good idea to look on BLAS and LAPACK (through both are written in Fortran).

[njames93]

Add support for array access Arr[I * JExtent + J]

[LegalizeAdulthood]

Except for a couple nits, LGTM.

clang-tools-extra/clang-tidy/performance/InefficientArrayTraversalCheck.h

26–27

If you're not doing anything different, I believe you can just do
using ClangTidyCheck::ClangTidyCheck;

Also, shouldn't you be explicitly overriding the d'tor?
~InefficientArrayTraversalCheck() override = default;

[njames93]

clang-tools-extra/clang-tidy/performance/InefficientArrayTraversalCheck.h

26–27

No need to explicitly override the d'tor

[njames93]

Use inheriting constructor for check

[njames93]

Uploaded wrong diff

[njames93]

Simplify check logic to only detect loop inits with 0 and incriment with 1.
Functionality can be introduced with later patches.

[shafik]

Is this change still relevant or can we close the PR?

clang-tools-extra/clang-tidy/performance/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   FrontendOpenMP
   Support
   )
 
 add_clang_library(clangTidyPerformanceModule
   FasterStringFindCheck.cpp
   ForRangeCopyCheck.cpp
   ImplicitConversionInLoopCheck.cpp
   InefficientAlgorithmCheck.cpp
+  InefficientArrayTraversalCheck.cpp
   InefficientStringConcatenationCheck.cpp
   InefficientVectorOperationCheck.cpp
   MoveConstArgCheck.cpp
   MoveConstructorInitCheck.cpp
   NoAutomaticMoveCheck.cpp
   NoIntToPtrCheck.cpp
   NoexceptMoveConstructorCheck.cpp
   PerformanceTidyModule.cpp

clang-tools-extra/clang-tidy/performance/InefficientArrayTraversalCheck.h

+//===--- InefficientArrayTraversalCheck.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_PERFORMANCE_INEFFICIENTARRAYTRAVERSALCHECK_H
+#define LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_PERFORMANCE_INEFFICIENTARRAYTRAVERSALCHECK_H
+
+#include "../ClangTidyCheck.h"
+
+namespace clang {
+namespace tidy {
+namespace performance {
+
+/// Detects nested for loops used to traverse a 2D array where the row index is
+/// iterated on the inner loop.
+///
+/// For the user-facing documentation see:
+/// http://clang.llvm.org/extra/clang-tidy/checks/performance-inefficient-array-traversal.html
+class InefficientArrayTraversalCheck : public ClangTidyCheck {
+public:
+  InefficientArrayTraversalCheck(StringRef Name, ClangTidyContext *Context)
+      : ClangTidyCheck(Name, Context) {}
+  void registerMatchers(ast_matchers::MatchFinder *Finder) override;
+  void check(const ast_matchers::MatchFinder::MatchResult &Result) override;
+  llvm::Optional<TraversalKind> getCheckTraversalKind() const override {
+    return TK_IgnoreUnlessSpelledInSource;
+  }
+};
+
+} // namespace performance
+} // namespace tidy
+} // namespace clang
+
+#endif // LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_PERFORMANCE_INEFFICIENTARRAYTRAVERSALCHECK_H

clang-tools-extra/clang-tidy/performance/InefficientArrayTraversalCheck.cpp

+//===--- InefficientArrayTraversalCheck.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 "InefficientArrayTraversalCheck.h"
+#include "clang/ASTMatchers/ASTMatchFinder.h"
+#include "clang/ASTMatchers/ASTMatchers.h"
+
+using namespace clang::ast_matchers;
+
+namespace clang {
+namespace tidy {
+namespace performance {
+
+namespace {
+AST_MATCHER_P(Stmt, hasSingleStmt, ast_matchers::internal::Matcher<Stmt>,
+              InnerMatch) {
+  clang::ast_matchers::internal::BoundNodesTreeBuilder Copy(*Builder);
+  if (InnerMatch.matches(Node, Finder, &Copy)) {
+    *Builder = Copy;
+    return true;
+  }
+  if (const auto *Res = dyn_cast<CompoundStmt>(&Node)) {
+    return Res->size() == 1 &&
+           InnerMatch.matches(*Res->body_front(), Finder, Builder);
+  }
+  return false;
+}
+ast_matchers::internal::Matcher<Stmt>
+stmtOrCompound(ast_matchers::internal::Matcher<Stmt> Inner) {
+  return anyOf(Inner, compoundStmt(hasAnySubstatement(Inner)));
+}
+AST_MATCHER_P2(Expr, isEquivalentToEither, StringRef, LHSBound, StringRef,
+               RHSBound) {
+  llvm::FoldingSetNodeID ExprID, MatchedID;
+  Node.Profile(ExprID, Finder->getASTContext(), true);
+  return Builder->removeBindings(
+      [this, &ExprID, &MatchedID,
+       Finder](const ast_matchers::internal::BoundNodesMap &Nodes) {
+        for (const auto &Item : {&LHSBound, &RHSBound}) {
+          const auto *MatchedExpr = Nodes.getNodeAs<Expr>(*Item);
+          MatchedID.clear();
+          if (MatchedExpr) {
+            MatchedExpr->Profile(MatchedID, Finder->getASTContext(), true);
+            if (MatchedID == ExprID)
+              return false;
+          }
+        }
+        return true;
+      });
+}
+} // namespace
+
+static const char InnerVar[] = "InnerVar";
+static const char OuterVar[] = "OuterVar";
+static const char OuterExtent[] = "OuterExtent";
+static const char OuterInit[] = "OuterInit";
+static const char InnerLoop[] = "InnerLoop";
+static const char OuterLoop[] = "OuterLoop";
+static const char ArrayAccess[] = "ArrayAccess";
+static const char StridedArrayAccess[] = "Strided";
+
+void InefficientArrayTraversalCheck::registerMatchers(MatchFinder *Finder) {
+  auto NestedLoopMatcher = [](auto InnerLoopBody) {
+    auto ForLoopBase = [](auto BodyMatcher, bool Inner) {
+      StringRef Var = Inner ? InnerVar : OuterVar;
+      auto ToDecl = declRefExpr(hasDeclaration(equalsBoundNode(Var.str())));
+      return forStmt(hasLoopInit(declStmt(hasSingleDecl(
+                         varDecl(hasType(isInteger()),
+                                 Inner ? anything()
+                                       : hasInitializer(ignoringParenImpCasts(
+                                             expr().bind(OuterInit))))
+                             .bind(Var)))),
+                     hasCondition(binaryOperator(
+                         Inner ? binaryOperator(hasEitherOperand(ToDecl))
+                               : binaryOperator(hasOperands(
+                                     ToDecl, ignoringParenImpCasts(
+                                                 expr().bind(OuterExtent)))),
+                         hasAnyOperatorName("<", ">", "!=", ">=", "<="))),
+                     // TODO: Add support for x = x [+-] 1
+                     hasIncrement(anyOf(
+                         unaryOperator(hasUnaryOperand(ToDecl),
+                                       hasAnyOperatorName("++", "--")),
+                         binaryOperator(hasAnyOperatorName("+=", "-="),
+                                        hasLHS(ToDecl),
+                                        hasRHS(integerLiteral(equals(1)))))),
+                     hasBody(BodyMatcher))
+          .bind(Inner ? InnerLoop : OuterLoop);
+    };
+    return ForLoopBase(
+        hasSingleStmt(ForLoopBase(stmtOrCompound(InnerLoopBody), true)), false);
+  };
+  auto ArrayExprMatcher = expr(hasDescendant(
+      arraySubscriptExpr(
+          hasIndex(declRefExpr(hasDeclaration(equalsBoundNode(OuterVar)))),
+          hasBase(arraySubscriptExpr(hasIndex(
+              declRefExpr(hasDeclaration(equalsBoundNode(InnerVar)))))))
+          .bind(ArrayAccess)));
+  auto StridedAccess = expr(hasDescendant(
+      arraySubscriptExpr(
+          hasIndex(binaryOperator(
+              hasOperatorName("+"),
+              hasOperands(
+                  declRefExpr(hasDeclaration(equalsBoundNode(OuterVar))),
+                  binaryOperator(hasOperatorName("*"),
+                                 hasOperands(declRefExpr(hasDeclaration(
+                                                 equalsBoundNode(InnerVar))),
+                                             isEquivalentToEither(
+                                                 OuterInit, OuterExtent)))))))
+          .bind(StridedArrayAccess)));
+  Finder->addMatcher(NestedLoopMatcher(ArrayExprMatcher), this);
+  Finder->addMatcher(NestedLoopMatcher(StridedAccess), this);
+  // TODO: Add a matcher that works for containers
+  // VectorOfVectors[InnerVar][OuterVar]
+}
+
+void InefficientArrayTraversalCheck::check(
+    const MatchFinder::MatchResult &Result) {
+  auto DisplayLoops = [this, &Result] {
+    const auto *InnerLoopStmt = Result.Nodes.getNodeAs<ForStmt>(InnerLoop);
+    diag(InnerLoopStmt->getBeginLoc(), "Row index %0 incremented in this loop",
+         DiagnosticIDs::Note)
+        << Result.Nodes.getNodeAs<VarDecl>(InnerVar)
+        << SourceRange(InnerLoopStmt->getBeginLoc(),
+                       InnerLoopStmt->getRParenLoc());
+    const auto *OuterLoopStmt = Result.Nodes.getNodeAs<ForStmt>(OuterLoop);
+    diag(OuterLoopStmt->getBeginLoc(),
+         "Column index %0 incremented in this loop", DiagnosticIDs::Note)
+        << Result.Nodes.getNodeAs<VarDecl>(OuterVar)
+        << SourceRange(OuterLoopStmt->getBeginLoc(),
+                       OuterLoopStmt->getRParenLoc());
+  };
+  if (const auto *Array =
+          Result.Nodes.getNodeAs<ArraySubscriptExpr>(ArrayAccess)) {
+    diag(Array->getBeginLoc(),
+         "Nonsequential array traversal can harm performance");
+    DisplayLoops();
+    return;
+  }
+  if (const auto *Array =
+          Result.Nodes.getNodeAs<ArraySubscriptExpr>(StridedArrayAccess)) {
+    diag(Array->getBeginLoc(),
+         "Nonsequential array traversal can harm performance");
+    DisplayLoops();
+    return;
+  }
+  llvm_unreachable("Unhandled Match");
+}
+
+} // namespace performance
+} // namespace tidy
+} // namespace clang

clang-tools-extra/clang-tidy/performance/PerformanceTidyModule.cpp

 //===-- PerformanceTidyModule.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 "../ClangTidy.h"
 #include "../ClangTidyModule.h"
 #include "../ClangTidyModuleRegistry.h"
 #include "FasterStringFindCheck.h"
 #include "ForRangeCopyCheck.h"
 #include "ImplicitConversionInLoopCheck.h"
 #include "InefficientAlgorithmCheck.h"
+#include "InefficientArrayTraversalCheck.h"
 #include "InefficientStringConcatenationCheck.h"
 #include "InefficientVectorOperationCheck.h"
 #include "MoveConstArgCheck.h"
 #include "MoveConstructorInitCheck.h"
 #include "NoAutomaticMoveCheck.h"
 #include "NoIntToPtrCheck.h"
 #include "NoexceptMoveConstructorCheck.h"
 #include "TriviallyDestructibleCheck.h"
void addCheckFactories(ClangTidyCheckFactories &CheckFactories) override {
     CheckFactories.registerCheck<FasterStringFindCheck>(
         "performance-faster-string-find");
     CheckFactories.registerCheck<ForRangeCopyCheck>(
         "performance-for-range-copy");
     CheckFactories.registerCheck<ImplicitConversionInLoopCheck>(
         "performance-implicit-conversion-in-loop");
     CheckFactories.registerCheck<InefficientAlgorithmCheck>(
         "performance-inefficient-algorithm");
+    CheckFactories.registerCheck<InefficientArrayTraversalCheck>(
+        "performance-inefficient-array-traversal");
     CheckFactories.registerCheck<InefficientStringConcatenationCheck>(
         "performance-inefficient-string-concatenation");
     CheckFactories.registerCheck<InefficientVectorOperationCheck>(
         "performance-inefficient-vector-operation");
     CheckFactories.registerCheck<MoveConstArgCheck>(
         "performance-move-const-arg");
     CheckFactories.registerCheck<MoveConstructorInitCheck>(
         "performance-move-constructor-init");

clang-tools-extra/docs/ReleaseNotes.rst

- New :doc:`cppcoreguidelines-virtual-class-destructor
 
   Finds virtual classes whose destructor is neither public and virtual nor
   protected and non-virtual.
 
 - New :doc:`misc-misleading-identifier <clang-tidy/checks/misc-misleading-identifier>` check.
 
   Reports identifier with unicode right-to-left characters.
 
+- New :doc:`performance-inefficient-array-traversal
+  <clang-tidy/checks/performance-inefficient-array-traversal>` check.
+
+  Detects nested ``for`` loops used to traverse a 2D array where the row index
+  is iterated on the inner loop.
+
 - New :doc:`readability-container-data-pointer
   <clang-tidy/checks/readability-container-data-pointer>` check.
 
   Finds cases where code could use ``data()`` rather than the address of the
   element at index 0 in a container.
 
 - New :doc:`readability-identifier-length
   <clang-tidy/checks/readability-identifier-length>` check.

clang-tools-extra/docs/clang-tidy/checks/list.rst

.. csv-table::
    `objc-property-declaration <objc-property-declaration.html>`_, "Yes"
    `objc-super-self <objc-super-self.html>`_, "Yes"
    `openmp-exception-escape <openmp-exception-escape.html>`_,
    `openmp-use-default-none <openmp-use-default-none.html>`_,
    `performance-faster-string-find <performance-faster-string-find.html>`_, "Yes"
    `performance-for-range-copy <performance-for-range-copy.html>`_, "Yes"
    `performance-implicit-conversion-in-loop <performance-implicit-conversion-in-loop.html>`_,
    `performance-inefficient-algorithm <performance-inefficient-algorithm.html>`_, "Yes"
+   `performance-inefficient-array-traversal <performance-inefficient-array-traversal.html>`_,
    `performance-inefficient-string-concatenation <performance-inefficient-string-concatenation.html>`_,
    `performance-inefficient-vector-operation <performance-inefficient-vector-operation.html>`_, "Yes"
    `performance-move-const-arg <performance-move-const-arg.html>`_, "Yes"
    `performance-move-constructor-init <performance-move-constructor-init.html>`_,
    `performance-no-automatic-move <performance-no-automatic-move.html>`_,
    `performance-no-int-to-ptr <performance-no-int-to-ptr.html>`_,
    `performance-noexcept-move-constructor <performance-noexcept-move-constructor.html>`_, "Yes"
    `performance-trivially-destructible <performance-trivially-destructible.html>`_, "Yes"

clang-tools-extra/docs/clang-tidy/checks/performance-inefficient-array-traversal.rst

+.. title:: clang-tidy - performance-inefficient-array-traversal
+
+performance-inefficient-array-traversal
+=======================================
+
+Detects nested ``for`` loops used to traverse a 2D array where the row index
+is iterated on the inner loop.
+
+.. code-block:: c++
+
+   for (int X = 0; X < Columns; ++X)
+     for (int Y = 0; Y < Rows; ++Y)
+       Array[Y][X]++;
+
+This array access pattern results in nonsequential data access which is cache 
+unfriendly and can prevent auto vectorization optimizations.
+
+A much faster version of the above loop would be
+
+.. code-block:: c++
+
+   for (int Y = 0; Y < Rows; ++Y)
+     for (int X = 0; X < Columns; ++X)
+       Array[Y][X]++;

clang-tools-extra/test/clang-tidy/checkers/performance-inefficient-array-traversal.cpp

+// RUN: %check_clang_tidy %s performance-inefficient-array-traversal %t
+
+constexpr unsigned Rows = 10U;
+constexpr unsigned Cols = 16U;
+
+int Arr[Rows][Cols];
+int *PtrArr[Cols];
+int **Ptr;
+int FlatArray[Rows * Cols];
+
+void foo();
+
+void warned() {
+  for (unsigned I = 0; I < Cols; ++I) {
+    for (unsigned J = 0; J < Rows; ++J) {
+      Arr[J][I]++;
+      // CHECK-MESSAGES: :[[@LINE-1]]:7: warning: Nonsequential array traversal can harm performance
+      // CHECK-MESSAGES: :[[@LINE-3]]:5: note: Row index 'J' incremented in this loop
+      // CHECK-MESSAGES: :[[@LINE-5]]:3: note: Column index 'I' incremented in this loop
+    }
+  }
+  for (unsigned I = 0; I < Cols; ++I)
+    for (unsigned J = 0; J < Rows; ++J)
+      Arr[J][I]++;
+  // CHECK-MESSAGES: :[[@LINE-1]]:7: warning: Nonsequential array traversal can harm performance
+
+  // Ensure it works on array access that use pointers
+  for (unsigned I = 0; I < Cols; ++I)
+    for (unsigned J = 0; J < Rows; ++J)
+      PtrArr[J][I]++;
+  // CHECK-MESSAGES: :[[@LINE-1]]:7: warning: Nonsequential array traversal can harm performance
+
+  for (unsigned I = 0; I < Cols; ++I)
+    for (unsigned J = 0; J < Rows; ++J)
+      Ptr[J][I]++;
+  // CHECK-MESSAGES: :[[@LINE-1]]:7: warning: Nonsequential array traversal can harm performance
+
+  // Detect += 1 as the loop incriment
+  for (unsigned I = 0; I < Cols; I += 1)
+    for (unsigned J = 0; J < Rows; J += 1)
+      Arr[J][I]++;
+  // CHECK-MESSAGES: :[[@LINE-1]]:7: warning: Nonsequential array traversal can harm performance
+
+  // Still warn on this as calls inside the inner loop shouldn't complicate a fix.
+  for (unsigned I = 0; I < Cols; ++I) {
+    for (unsigned J = 0; J < Rows; ++J) {
+      foo();
+      Arr[J][I]++;
+      // CHECK-MESSAGES: :[[@LINE-1]]:7: warning: Nonsequential array traversal can harm performance
+      foo();
+    }
+  }
+  for (unsigned I = 0; I < Cols; ++I) {
+    for (unsigned J = 0; J < Rows; ++J) {
+      FlatArray[J * Cols + I]++;
+      // CHECK-MESSAGES: :[[@LINE-1]]:7: warning: Nonsequential array traversal can harm performance
+      // CHECK-MESSAGES: :[[@LINE-3]]:5: note: Row index 'J' incremented in this loop
+      // CHECK-MESSAGES: :[[@LINE-5]]:3: note: Column index 'I' incremented in this loop
+    }
+  }
+}
+
+void ignored() {
+  // Correct traversal.
+  for (unsigned I = 0; I < Rows; ++I) {
+    for (unsigned J = 0; J < Cols; ++J) {
+      Arr[I][J]++;
+    }
+  }
+  for (unsigned I = 0; I < Rows; ++I) {
+    for (unsigned J = 0; J < Cols; ++J) {
+      PtrArr[I][J]++;
+    }
+  }
+  for (unsigned I = 0; I < Rows; ++I) {
+    for (unsigned J = 0; J < Cols; ++J) {
+      FlatArray[I * Cols + J]++;
+    }
+  }
+  // Don'w warn on these cases as extra code inside the outer loop could complicate a fix.
+  for (unsigned I = 0; I < Cols; ++I) {
+    foo();
+    for (unsigned J = 0; J < Rows; ++J) {
+      Arr[J][I]++;
+    }
+  }
+  for (unsigned I = 0; I < Cols; ++I) {
+    for (unsigned J = 0; J < Rows; ++J) {
+      Arr[J][I]++;
+    }
+    foo();
+  }
+
+  // Nested loop increments incorrect variable, don't warn on the traversal.
+  for (unsigned I = 0; I < Cols; ++I)
+    for (unsigned J = 0; J < Rows; ++I)
+      Arr[J][I]++;
+
+  // These 2 loops are questionable and definitely a memory safety bug,
+  // but this is not the point of this check.
+  for (unsigned I = 0; I < Cols; ++I)
+    for (unsigned J = 0; J < Rows; ++I)
+      FlatArray[I * Cols + J]++;
+  for (unsigned I = 0; I < Rows; ++I)
+    for (unsigned J = 0; J < Cols; ++I)
+      FlatArray[J * Rows + I]++;
+}