RFC: Detecting Data-Parallel Loop Patterns in C/C++ Source Using Clang/LLVM Analysis

Clang Frontend
,
1

Motivation

Many C and C++ applications contain loops that are inherently data-parallel but remain sequential because developers are unaware that the iterations are independent. While LLVM already performs sophisticated analyses for optimisation (such as dependence analysis and loop vectorisation), these analyses are primarily used internally by optimisation passes and are not exposed as developer-facing diagnostics for identifying potential parallelisation opportunities.

The goal of this proposal is to introduce a static analysis that identifies loops whose iterations appear independent and may therefore be suitable for data-parallel execution (e.g., SIMD vectorisation or OpenMP parallelisation).

Problem Statement

Consider the following example:

#include <cmath>

void compute(float *data, int N) {
    for (int i = 0; i < N; ++i) {
        data[i] = std::sin(data[i]) + std::cos(data[i]);
    }
}

Each iteration only accesses data[i].

There are no loop-carried dependencies, making the loop a good candidate for data-parallel execution.

However, Clang currently does not provide a developer-facing diagnostic explicitly identifying such opportunities.

Proposal

Introduce a static analysis capable of identifying loops whose iterations appear independent.

The analysis would:

  • Identify loops within each function.
  • Analyse memory accesses and loop-carried dependencies.
  • Detect element-wise computations over independent data.
  • Emit diagnostics explaining why a loop is considered data-parallel.

Example diagnostic:

Function 'compute':
  Loop beginning at line 12 appears data-parallel.
  Reason:
    • Independent array accesses
    • No detected loop-carried dependencies

Prototype Implementation

To better illustrate the proposal, I have implemented a prototype demonstrating this analysis.

Reference Pull Request: Add Static Analysis for Identifying Data Parallelism Using LLVM/Clang by HITESH-S-P · Pull Request #190511 · llvm/llvm-project · GitHub

The current implementation is intended as a proof of concept and demonstrates:

  • Detection of loops with independent iterations.
  • Basic identification of data-parallel patterns.
  • Emission of developer-facing diagnostics.
  • Integration with the Clang tooling infrastructure used in the prototype.

The purpose of this implementation is to facilitate discussion around the design and feasibility of the proposal. I fully expect that the implementation may need to evolve based on community feedback, including changes to its architecture or integration point within the LLVM ecosystem.

Feedback on both the overall direction and the implementation approach would be greatly appreciated.

Possible Integration Points

The current prototype was implemented as a standalone analysis to explore the idea with minimal impact on existing infrastructure.

However, I would appreciate guidance from the community regarding the most appropriate long-term integration point. Possible options include:

  • a new clang-tidy performance check
  • an LLVM analysis pass
  • optimisation remarks
  • another existing Clang/LLVM framework

I do not have a strong preference and would like to follow the direction that best aligns with LLVM’s architecture and long-term maintainability.

Open Questions

I would appreciate feedback on the following:

  1. Does this analysis provide sufficient value to justify inclusion in LLVM/Clang?
  2. Which existing framework would be the most appropriate integration point?
  3. Are there existing analyses that should be reused rather than introducing new logic?
  4. Would such a feature be acceptable if implemented using existing LLVM infrastructure?
2

The goal of this proposal is to introduce a static analysis that identifies loops whose iterations appear independent and may therefore be suitable for data-parallel execution

Based on this sentence I do not think that the Clang Static Analyzer is the right tool for this kind of analysis. The CSA’s primary job is to catch bugs and it is not used (AFAIK) to this kind of optimisation. Would this RFC basically be implemented in a CSA checker? That is my understanding so far.

While LLVM already performs sophisticated analyses for optimisation (such as dependence analysis and loop vectorisation), these analyses are primarily used internally by optimisation passes and are not exposed as developer-facing diagnostics for identifying potential parallelisation opportunities.

Would your tool also do dependence analysis? If yes then I am pretty sure that even clang-tidy won’t be the right tool here since it heavily, if not 100%, uses Clang’s AST. Based on (https://stackoverflow.com/questions/70178835/how-to-get-the-data-dependency-information-from-llvm-ir) I do not think that the dependency analysis in LLVM uses Clang’s AST, so this can be a bottleneck in implementing this analysis in clang-tidy, no?

However, I would appreciate guidance from the community regarding the most appropriate long-term integration point. Possible options include:

  • a new clang-tidy performance check
  • an LLVM analysis pass
  • optimisation remarks
  • another existing Clang/LLVM framework

clang-tidy might be the right tool for this kind of analysis, but I do not have expertise with it, so I cannot help with that.

I have checked and clang-tidy indeed has a performance- check, so I assume it does performance analysis as well. Someone working on clang-tidy will 100% give you a clear answer on this.

I am a student working on the CSA, so only take my word knowing that, but I am pretty sure the CSA is not the right tool for this.

3

We actually have work happening to do exactly this type of analysis internally (via intern), and intend for it to happen in CIR. We believe it is the perfect tool to do something like this, and would encourage you to chat with @Rithik to see if this is perhaps something you could help/lead in CIR!

1 Like
4

Since clang-tidy is linter tool, we need to give suggesting to user about how they can rewrite the code to comply with the check.
If you go with AST level, from this RFC I don’t understand what user is expected to do with the code. To use std::simd, to use simd intrinsics or something else?

I’m not so experienced in IR/codegen but I guess in IR level this analysis makes sense if it helps with better codegen (by using simd instruction set).