flang/docs/DoConcurrentConversionToOpenMP.md

<!--===- docs/DoConcurrentMappingToOpenMP.md

   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

-->

# `DO CONCURRENT` mapping to OpenMP


This document seeks to describe the effort to parallelize `do concurrent` loops
by mapping them to OpenMP worksharing constructs. The goals of this document
are:
* Describing how to instruct `flang` to map `DO CONCURRENT` loops to OpenMP
  constructs.
* Tracking the current status of such mapping.
* Describing the limitations of the current implementation.
* Describing next steps.
* Tracking the current upstreaming status (from the AMD ROCm fork).

## Usage

In order to enable `do concurrent` to OpenMP mapping, `flang` adds a new
compiler flag: `-fdo-concurrent-to-openmp`. This flag has 3 possible values:
1. `host`: this maps `do concurrent` loops to run in parallel on the host CPU.
   This maps such loops to the equivalent of `omp parallel do`.
2. `device`: this maps `do concurrent` loops to run in parallel on a target device.
   This maps such loops to the equivalent of
   `omp target teams distribute parallel do`.
3. `none`: this disables `do concurrent` mapping altogether. In that case, such
   loops are emitted as sequential loops.

The `-fdo-concurrent-to-openmp` compiler switch is currently available only when
OpenMP is also enabled. So you need to provide the following options to flang in
order to enable it:
```
flang ... -fopenmp -fdo-concurrent-to-openmp=[host|device|none] ...
```
For mapping to device, the target device architecture must be specified as well.
See `-fopenmp-targets` and `--offload-arch` for more info.

## Current status

As of LLVM 22, flang adds more extensive support for parallelizing `do concurrent` loops
on the CPU and the GPU. In particular, the local specifier, partial support for reduce,
and automatic mapping of user-defined types are now supported.
On the CPU, we validated the feature using [FIATS](https://github.com/BerkeleyLab/fiats)
inference and training codes where `do concurrent` and OpenMP had very similar 
acceleration results (for more information, see: [1]).
On the GPU, we have basic support that is still in progress. We have offload tests for 
1D and 2D saxpy. We also validated using codes that do not make extensive use of user-defined
types and allocatables.

[1] Automatically Parallelizing Batch Inference on Deep Neural Networks Using Fiats
and Fortran 2023 “Do Concurrent” (https://link.springer.com/chapter/10.1007/978-3-032-07612-0_11)

### Loop nest detection

On the `FIR` dialect level, the following loop:
```fortran
  do concurrent(i=1:n, j=1:m, k=1:o)
    a(i,j,k) = i + j + k
  end do
```
is modelled as a nest of `fir.do_loop` ops such that an outer loop's region
contains **only** the following:
  1. The operations needed to assign/update the outer loop's induction variable.
  1. The inner loop itself.

So the MLIR structure for the above example looks similar to the following:
```
  fir.do_loop %i_idx = %34 to %36 step %c1 unordered {
    %i_idx_2 = fir.convert %i_idx : (index) -> i32
    fir.store %i_idx_2 to %i_iv#1 : !fir.ref<i32>

    fir.do_loop %j_idx = %37 to %39 step %c1_3 unordered {
      %j_idx_2 = fir.convert %j_idx : (index) -> i32
      fir.store %j_idx_2 to %j_iv#1 : !fir.ref<i32>

      fir.do_loop %k_idx = %40 to %42 step %c1_5 unordered {
        %k_idx_2 = fir.convert %k_idx : (index) -> i32
        fir.store %k_idx_2 to %k_iv#1 : !fir.ref<i32>

        ... loop nest body goes here ...
      }
    }
  }
```
This applies to multi-range loops in general; they are represented in the IR as
a nest of `fir.do_loop` ops with the above nesting structure.

Therefore, the pass detects such "perfectly" nested loop ops to identify multi-range
loops and map them as "collapsed" loops in OpenMP.

#### Further info regarding loop nest detection

Loop nest detection is currently limited to the scenario described in the previous
section. However, this is quite limited and can be extended in the future to cover
more cases. At the moment, for the following loop nest, even though both loops are
perfectly nested, only the outer loop is parallelized:
```fortran
do concurrent(i=1:n)
  do concurrent(j=1:m)
    a(i,j) = i * j
  end do
end do
```

Similarly, for the following loop nest, even though the intervening statement `x = 41`
does not have any memory effects that would affect parallelization, this nest is
not parallelized either (only the outer loop is).

```fortran
do concurrent(i=1:n)
  x = 41
  do concurrent(j=1:m)
    a(i,j) = i * j
  end do
end do
```

The above also has the consequence that the `j` variable will **not** be
privatized in the OpenMP parallel/target region. In other words, it will be
treated as if it was a `shared` variable. For more details about privatization,
see the "Data environment" section below.

See `flang/test/Transforms/DoConcurrent/loop_nest_test.f90` for more examples
of what is and is not detected as a perfect loop nest.

### Single-range loops

Given the following loop:
```fortran
  do concurrent(i=1:n)
    a(i) = i * i
  end do
```

#### Mapping to `host`

Mapping this loop to the `host`, generates MLIR operations of the following
structure:

```
%4 = fir.address_of(@_QFEa) ...
%6:2 = hlfir.declare %4 ...

omp.parallel {
  // Allocate private copy for `i`.
  // TODO Use delayed privatization.
  %19 = fir.alloca i32 {bindc_name = "i"}
  %20:2 = hlfir.declare %19 {uniq_name = "_QFEi"} ...

  omp.wsloop {
    omp.loop_nest (%arg0) : index = (%21) to (%22) inclusive step (%c1_2) {
      %23 = fir.convert %arg0 : (index) -> i32
      // Use the privatized version of `i`.
      fir.store %23 to %20#1 : !fir.ref<i32>
      ...

      // Use "shared" SSA value of `a`.
      %42 = hlfir.designate %6#0
      hlfir.assign %35 to %42
      ...
      omp.yield
    }
    omp.terminator
  }
  omp.terminator
}
```

#### Mapping to `device`

<!-- TODO -->

### Multi-range loops

The pass currently supports multi-range loops as well. Given the following
example:

```fortran
   do concurrent(i=1:n, j=1:m)
       a(i,j) = i * j
   end do
```

The generated `omp.loop_nest` operation look like:

```
omp.loop_nest (%arg0, %arg1)
    : index = (%17, %19) to (%18, %20)
    inclusive step (%c1_2, %c1_4) {
  fir.store %arg0 to %private_i#1 : !fir.ref<i32>
  fir.store %arg1 to %private_j#1 : !fir.ref<i32>
  ...
  omp.yield
}
```

It is worth noting that we have privatized versions for both iteration
variables: `i` and `j`. These are locally allocated inside the parallel/target
OpenMP region similar to what the single-range example in previous section
shows.

### Data environment

By default, variables that are used inside a `do concurrent` loop nest are
either treated as `shared` in case of mapping to `host`, or mapped into the
`target` region using a `map` clause in case of mapping to `device`. The only
exceptions to this are:
  1. the loop's iteration variable(s) (IV) of **perfect** loop nests. In that
     case, for each IV, we allocate a local copy as shown by the mapping
     examples above.
  1. any values that are from allocations outside the loop nest and used
     exclusively inside of it. In such cases, a local privatized
     copy is created in the OpenMP region to prevent multiple teams of threads
     from accessing and destroying the same memory block, which causes runtime
     issues. For an example of such cases, see
     `flang/test/Transforms/DoConcurrent/locally_destroyed_temp.f90`.

Implicit mapping detection (for mapping to the target device) is still quite
limited and work to make it smarter is underway for both OpenMP in general
and `do concurrent` mapping.

#### Non-perfectly-nested loops' IVs

For non-perfectly-nested loops, the IVs are still treated as `shared` or
`map` entries as pointed out above. This **might not** be consistent with what
the Fortran specification tells us. In particular, taking the following
snippets from the spec (version 2023) into account:

> § 3.35
> ------
> construct entity
> entity whose identifier has the scope of a construct

> § 19.4
> ------
>  A variable that appears as an index-name in a FORALL or DO CONCURRENT
>  construct [...] is a construct entity. A variable that has LOCAL or
>  LOCAL_INIT locality in a DO CONCURRENT construct is a construct entity.
> [...]
> The name of a variable that appears as an index-name in a DO CONCURRENT
> construct, FORALL statement, or FORALL construct has a scope of the statement
> or construct. A variable that has LOCAL or LOCAL_INIT locality in a DO
> CONCURRENT construct has the scope of that construct.

From the above quotes, it seems there is an equivalence between the IV of a `do
concurrent` loop and a variable with a `LOCAL` locality specifier (equivalent
to OpenMP's `private` clause). Which means that we should probably
localize/privatize a `do concurrent` loop's IV even if it is not perfectly
nested in the nest we are parallelizing. For now, however, we **do not** do
that as pointed out previously. In the near future, we propose a middle-ground
solution (see the Next steps section for more details).

<!--
More details about current status will be added along with relevant parts of the
implementation in later upstreaming patches.
-->

## Implementation notes

### Separate MLIR op for `do concurrent`

`do concurrent` has its own dedicated ops: `fir.do_concurrent` (wrapper) and
`fir.do_concurrent.loop` (loop). These support multi-range loops natively with
multiple induction variables, locality specifier operands (`local_vars`,
`local_syms`), and reduction operands (`reduce_vars`, `reduce_syms`,
`reduce_attrs`). The wrapper provides an `AutomaticAllocationScope` for
iteration variable allocation.

### Delayed privatization

Delayed privatization is implemented for `do concurrent` locality specifiers.
`fir.local` ops (analogous to `omp.private`) are created during lowering and
converted to `omp.private` ops by `DoConcurrentConversion`. This provides a
cleaner IR representation where privatization logic is encapsulated in symbol ops
rather than inlined in the loop body.

## Next steps

This section describes open questions and items not yet addressed.

### Locality specifiers for `do concurrent`

Locality specifiers control the data environment of the `do concurrent` loop.
The following table summarizes the current implementation status:

| Specifier | Supported | OpenMP mapping | Notes |
|-----------|-----------|----------------|-------|
| `LOCAL` | Yes | `omp.private {type = private}` | Per-thread allocation via delayed privatization |
| `LOCAL_INIT` | Yes | `omp.private {type = private}` + per-iteration copy | Copy inlined at top of `omp.loop_nest` body (not via `omp.private` copy_region — see below) |
| `REDUCE` | Yes | `omp.declare_reduction` + reduction clause | All Fortran reduction operators supported |
| `SHARED` | Yes | Implicit live-in (no clause needed) | `fir.local {type = shared}` created for documentation; variable remains a live-in to `omp.parallel` |
| `DEFAULT(NONE)` | Yes | No OpenMP equivalent | Enforced at semantics level; all variables must have explicit locality |

#### LOCAL and LOCAL_INIT

`LOCAL` maps directly to OpenMP `private` via delayed privatization: a
`fir.local {type = local}` op is created during lowering and converted to
`omp.private {type = private}` by `DoConcurrentConversion`. Each thread gets its
own storage with an undefined initial value.

`LOCAL_INIT` requires per-iteration initialization — at the start of each iteration,
the private variable must be re-initialized from the host variable. This differs
from OpenMP `firstprivate`, which initializes once per thread before the worksharing
loop. The `DoConcurrentConversion` pass handles this by:
1. Creating `omp.private {type = private}` (same as `LOCAL` — no copy_region).
2. Inlining the `fir.local` copy_region operations at the top of the `omp.loop_nest`
   body, so re-initialization happens every iteration.

The copy is not placed on the `omp.private` op because `copyFirstPrivateVars()` in
`OpenMPToLLVMIRTranslation.cpp` fires `omp.private`'s copy_region once per thread,
not once per iteration.

#### SHARED

`SHARED` variables are handled by `copySymbolBinding` during lowering, which makes
the inner scope's symbol alias the same MLIR value as the host variable. The
variable becomes an implicit live-in to `omp.parallel`, which is shared by default
in OpenMP. A `fir.local {type = shared}` op is created at the module level for
documentation and future `DEFAULT(NONE)` support, but is not placed in the loop's
locality operands.

#### REDUCE

Reductions are fully supported. A `fir.declare_reduction` op is created during
lowering and converted to `omp.declare_reduction` by `DoConcurrentConversion`.
The reduction clause is attached to `omp.wsloop`.

#### DEFAULT(NONE)

`DEFAULT(NONE)` is enforced during semantic analysis in `check-do-forall.cpp`.
When present, all variables from enclosing scopes used in the loop body must
appear in a locality specifier (`LOCAL`, `LOCAL_INIT`, `SHARED`, or `REDUCE`).
No FIR representation or OpenMP conversion is needed — the enforcement happens
before FIR generation, and the MLIR OpenMP dialect does not have a `default`
clause.

### More advanced detection of loop nests

As pointed out earlier, any intervening code between the headers of 2 nested
`do concurrent` loops prevents us from detecting this as a loop nest. In some
cases this is overly conservative. Therefore, a more flexible detection logic
of loop nests needs to be implemented.

### Data-dependence analysis

Right now, we map loop nests without analysing whether such mapping is safe to
do or not. We probably need to at least warn the user of unsafe loop nests due
to loop-carried dependencies.

### Non-rectangular loop nests

So far, we did not need to use the pass for non-rectangular loop nests. For
example:
```fortran
do concurrent(i=1:n)
  do concurrent(j=i:n)
    ...
  end do
end do
```
We defer this to the (hopefully) near future when we get the conversion in a
good share for the samples/projects at hand.

### Generalizing the pass to other parallel programming models

Once we have a stable and capable `do concurrent` to OpenMP mapping, we can take
this in a more generalized direction and allow the pass to target other models;
e.g. OpenACC. This goal should be kept in mind from the get-go even while only
targeting OpenMP.


## Upstreaming status

- [x] Command line options for `flang` and `bbc`.
- [x] Conversion pass skeleton (no transormations happen yet).
- [x] Status description and tracking document (this document).
- [x] Loop nest detection to identify multi-range loops.
- [ ] Basic host/CPU mapping support.
- [ ] Basic device/GPU mapping support.
- [ ] More advanced host and device support (expaned to multiple items as needed).