lib/Lower/OpenMP/DataSharingProcessor.cpp

//===-- DataSharingProcessor.cpp --------------------------------*- 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
//
//===----------------------------------------------------------------------===//
//
// Coding style: https://mlir.llvm.org/getting_started/DeveloperGuide/
//
//===----------------------------------------------------------------------===//

#include "DataSharingProcessor.h"

#include "Utils.h"
#include "flang/Lower/ConvertVariable.h"
#include "flang/Lower/PFTBuilder.h"
#include "flang/Lower/Support/PrivateReductionUtils.h"
#include "flang/Lower/Support/Utils.h"
#include "flang/Lower/SymbolMap.h"
#include "flang/Optimizer/Builder/BoxValue.h"
#include "flang/Optimizer/Builder/HLFIRTools.h"
#include "flang/Optimizer/Builder/Todo.h"
#include "flang/Optimizer/Dialect/FIROps.h"
#include "flang/Optimizer/HLFIR/HLFIRDialect.h"
#include "flang/Optimizer/HLFIR/HLFIROps.h"
#include "flang/Parser/openmp-utils.h"
#include "flang/Semantics/attr.h"
#include "flang/Semantics/openmp-directive-sets.h"
#include "flang/Semantics/openmp-utils.h"
#include "flang/Semantics/tools.h"
#include "llvm/Frontend/OpenMP/OMP.h"
#include <variant>

namespace Fortran {
namespace lower {
namespace omp {

static bool isConstructWithTopLevelTarget(lower::pft::Evaluation &eval) {
  const auto *ompEval = eval.getIf<parser::OpenMPConstruct>();
  if (ompEval) {
    auto dir = parser::omp::GetOmpDirectiveName(*ompEval).v;
    if (llvm::omp::topTargetSet.test(dir))
      return true;
  }
  return false;
}

static parser::CharBlock getSource(const lower::pft::Evaluation &eval) {
  return eval.visit(common::visitors{
      [&](const parser::OpenMPConstruct &x) {
        return parser::omp::GetOmpDirectiveName(x).source;
      },
      [&](const parser::OpenMPDeclarativeConstruct &x) { return x.source; },
      [&](const auto &x) {
        std::optional<parser::CharBlock> source = parser::GetSource(x);
        return source.has_value() ? source.value() : parser::CharBlock{};
      },
  });
}

static const semantics::Scope *
getCurrentScope(const semantics::SemanticsContext &semaCtx,
                const lower::pft::Evaluation &eval) {
  parser::CharBlock source = getSource(eval);
  return source.empty() ? nullptr : &semaCtx.FindScope(source);
}

DataSharingProcessor::DataSharingProcessor(
    lower::AbstractConverter &converter, semantics::SemanticsContext &semaCtx,
    const List<Clause> &clauses, lower::pft::Evaluation &eval,
    bool shouldCollectPreDeterminedSymbols, bool useDelayedPrivatization,
    lower::SymMap &symTable, bool isTargetPrivatization,
    llvm::ArrayRef<const semantics::Symbol *> metadirectiveLoopIVs)
    : converter(converter), semaCtx(semaCtx),
      firOpBuilder(converter.getFirOpBuilder()), clauses(clauses), eval(eval),
      shouldCollectPreDeterminedSymbols(shouldCollectPreDeterminedSymbols),
      useDelayedPrivatization(useDelayedPrivatization), symTable(symTable),
      isTargetPrivatization(isTargetPrivatization),
      isMetadirectiveLoop(!metadirectiveLoopIVs.empty()) {}

DataSharingProcessor::DataSharingProcessor(lower::AbstractConverter &converter,
                                           semantics::SemanticsContext &semaCtx,
                                           lower::pft::Evaluation &eval,
                                           bool useDelayedPrivatization,
                                           lower::SymMap &symTable,
                                           bool isTargetPrivatization)
    : DataSharingProcessor(converter, semaCtx, {}, eval,
                           /*shouldCollectPreDeterminedSymols=*/false,
                           useDelayedPrivatization, symTable,
                           isTargetPrivatization) {}

void DataSharingProcessor::processStep1(
    mlir::omp::PrivateClauseOps *clauseOps,
    std::optional<llvm::omp::Directive> dir) {
  collectSymbolsForPrivatization();
  if (isOpenMPPrivatizingEvaluation(eval) || isMetadirectiveLoop) {
    collectDefaultSymbols();
    collectImplicitSymbols();
    collectPreDeterminedSymbols();
    collectIndirectReferences();
  }

  privatize(clauseOps, dir);

  insertBarrier(clauseOps);
}

void DataSharingProcessor::processStep2(mlir::Operation *op, bool isLoop) {
  // 'sections' lastprivate is handled by genOMP()
  if (mlir::isa<mlir::omp::SectionOp>(op))
    return;
  if (!mlir::isa<mlir::omp::SectionsOp>(op)) {
    mlir::OpBuilder::InsertionGuard guard(firOpBuilder);
    copyLastPrivatize(op);
  }

  if (isLoop) {
    // push deallocs out of the loop
    firOpBuilder.setInsertionPointAfter(op);
    insertDeallocs();
  } else {
    mlir::OpBuilder::InsertionGuard guard(firOpBuilder);
    insertDeallocs();
  }
}

void DataSharingProcessor::insertDeallocs() {
  for (const semantics::Symbol *sym : allPrivatizedSymbols)
    if (semantics::IsAllocatable(sym->GetUltimate())) {
      if (!useDelayedPrivatization) {
        converter.createHostAssociateVarCloneDealloc(*sym);
        continue;
      }
      // For delayed privatization deallocs are created by
      // populateByRefInitAndCleanupRegions
    }
}

void DataSharingProcessor::cloneSymbol(const semantics::Symbol *sym) {
  bool isFirstPrivate = sym->test(semantics::Symbol::Flag::OmpFirstPrivate);

  // If we are doing eager-privatization on a symbol created using delayed
  // privatization there could be incompatible types here e.g.
  // fir.ref<fir.box<fir.array<>>>
  bool success = [&]() -> bool {
    const auto *details =
        sym->detailsIf<Fortran::semantics::HostAssocDetails>();
    assert(details && "No host-association found");
    const Fortran::semantics::Symbol &hsym = details->symbol();
    mlir::Value addr = converter.getSymbolAddress(hsym);

    if (auto refTy = mlir::dyn_cast<fir::ReferenceType>(addr.getType())) {
      if (auto boxTy = mlir::dyn_cast<fir::BoxType>(refTy.getElementType())) {
        if (auto arrayTy =
                mlir::dyn_cast<fir::SequenceType>(boxTy.getElementType())) {
          // FirConverter/fir::ExtendedValue considers all references to boxes
          // as mutable boxes. Outside of OpenMP it doesn't make sense to have a
          // mutable box of an array. Work around this here by loading the
          // reference so it is a normal boxed array.
          fir::FirOpBuilder &builder = converter.getFirOpBuilder();
          mlir::Location loc = converter.genLocation(hsym.name());
          fir::ExtendedValue hexv = converter.getSymbolExtendedValue(hsym);

          llvm::SmallVector<mlir::Value> extents =
              fir::factory::getExtents(loc, builder, hexv);

          // TODO: uniqName, name
          mlir::Value allocVal =
              builder.allocateLocal(loc, arrayTy, /*uniqName=*/"",
                                    /*name=*/"", extents, /*typeParams=*/{},
                                    sym->GetUltimate().attrs().test(
                                        Fortran::semantics::Attr::TARGET));
          mlir::Value shape = builder.genShape(loc, extents);
          mlir::Value box = builder.createBox(loc, boxTy, allocVal, shape,
                                              nullptr, {}, nullptr);

          // This can't be a CharArrayBoxValue because otherwise
          // boxTy.getElementType() would be a character type.
          // Assume the array element type isn't polymorphic because we are
          // privatizing.
          fir::ExtendedValue newExv = fir::ArrayBoxValue{box, extents};

          converter.bindSymbol(*sym, newExv);
          return true;
        }
      }
    }

    // Normal case:
    return converter.createHostAssociateVarClone(
        *sym, /*skipDefaultInit=*/isFirstPrivate);
  }();
  (void)success;
  assert(success && "Privatization failed due to existing binding");

  // Initialize clone from original object if it has any allocatable member.
  auto needInitClone = [&] {
    if (isFirstPrivate)
      return false;

    SymbolBox sb = symTable.lookupSymbol(sym);
    assert(sb);
    mlir::Value addr = sb.getAddr();
    assert(addr);
    return !fir::isPointerType(addr.getType()) &&
           hlfir::mayHaveAllocatableComponent(addr.getType());
  };

  if (needInitClone()) {
    Fortran::lower::initializeCloneAtRuntime(converter, *sym, symTable);
    mightHaveReadHostSym.insert(sym);
  }
}

void DataSharingProcessor::copyFirstPrivateSymbol(
    const semantics::Symbol *sym, mlir::OpBuilder::InsertPoint *copyAssignIP) {
  if (sym->test(semantics::Symbol::Flag::OmpFirstPrivate) ||
      sym->test(semantics::Symbol::Flag::LocalityLocalInit))
    converter.copyHostAssociateVar(*sym, copyAssignIP);
}

void DataSharingProcessor::copyLastPrivateSymbol(
    const semantics::Symbol *sym, mlir::OpBuilder::InsertPoint *lastPrivIP) {
  // Conditional-lastprivate symbols use their own guarded copy-back (from the
  // reduction accumulator), not the standard "last iteration wins" copy-back.
  if (!sym->test(semantics::Symbol::Flag::OmpLastPrivate) ||
      conditionalLastPrivatizedSymbols.contains(sym))
    return;

  if (sym->has<semantics::HostAssocDetails>()) {
    converter.copyHostAssociateVar(*sym, lastPrivIP, /*hostIsSource=*/false);
    return;
  }

  assert(isMetadirectiveLoop &&
         "unexpected lastprivate symbol without host association");

  // Metadirective loop IVs can be marked lastprivate during lowering, after
  // semantic host-association symbols would normally be created. Copy from the
  // private binding back to the one-level-up binding directly.
  mlir::OpBuilder::InsertionGuard guard(firOpBuilder);
  if (lastPrivIP)
    firOpBuilder.restoreInsertionPoint(*lastPrivIP);
  lower::SymbolBox hostBox = converter.lookupOneLevelUpSymbol(*sym);
  lower::SymbolBox privBox = converter.shallowLookupSymbol(*sym);
  assert(hostBox && privBox &&
         "expected symbol bindings for lastprivate loop IV");
  if (hostBox.getAddr() != privBox.getAddr())
    converter.copyVar(converter.getCurrentLocation(), hostBox.getAddr(),
                      privBox.getAddr(), fir::FortranVariableFlagsEnum::None);
}

void DataSharingProcessor::collectOmpObjectListSymbol(
    const omp::ObjectList &objects,
    llvm::SetVector<const semantics::Symbol *> &symbolSet) {
  for (const omp::Object &object : objects)
    symbolSet.insert(object.sym());
}

void DataSharingProcessor::collectSymbolsForPrivatization() {
  // Add checks here for exceptional cases where privatization is not
  // needed and be deferred to a later phase (like OpenMP IRBuilder).
  // Such cases are suggested to be clearly documented and explained
  // instead of being silently skipped
  auto isException = [&](const Fortran::semantics::Symbol *sym) -> bool {
    // Linear variables are privatized by the `linear` privatizers of the
    // linear clause, which genLinearPrivatizers creates.
    if (sym->test(Fortran::semantics::Symbol::Flag::OmpLinear))
      return true;
    return false;
  };

  for (const omp::Clause &clause : clauses) {
    if (const auto &privateClause =
            std::get_if<omp::clause::Private>(&clause.u)) {
      collectOmpObjectListSymbol(privateClause->v, explicitlyPrivatizedSymbols);
    } else if (const auto &firstPrivateClause =
                   std::get_if<omp::clause::Firstprivate>(&clause.u)) {
      collectOmpObjectListSymbol(firstPrivateClause->v,
                                 explicitlyPrivatizedSymbols);
    } else if (const auto &lastPrivateClause =
                   std::get_if<omp::clause::Lastprivate>(&clause.u)) {
      auto &modifier = std::get<
          std::optional<omp::clause::Lastprivate::LastprivateModifier>>(
          lastPrivateClause->t);

      const ObjectList &objects = std::get<ObjectList>(lastPrivateClause->t);
      if (modifier) {
        assert(*modifier ==
                   omp::clause::Lastprivate::LastprivateModifier::Conditional &&
               "unsupported lastprivate modifier");
        // The conditional modifier was added in OpenMP 5.0.  In earlier
        // versions semantics only warns and ignores it, so fall back to a
        // regular lastprivate here to keep lowering consistent and avoid the
        // conditional path for entities it cannot handle (e.g. characters).
        if (semaCtx.langOptions().getOpenMPVersion() >= 50) {
          collectOmpObjectListSymbol(objects, conditionalLastPrivatizedSymbols);
        } else {
          collectOmpObjectListSymbol(objects, explicitlyPrivatizedSymbols);
        }
      } else {
        collectOmpObjectListSymbol(objects, explicitlyPrivatizedSymbols);
      }
    }
  }

  // TODO For common blocks, add the underlying objects within the block. Doing
  // so, we won't need to explicitly handle block objects (or forget to do
  // so).
  // A conditional-lastprivate symbol is bound directly to the reduction struct
  // (not privatized) UNLESS the construct opts into the private-copy lowering
  // (conditionalLpUsesPrivateCopy, set by worksharing loops).  In that mode it
  // gets an ordinary private copy -- the "working" value that in-loop reads see
  // and that carries the execution-order value across iterations -- with the
  // reduction struct acting as the conditional-last accumulator, and the
  // standard lastprivate copy-back suppressed (see copyLastPrivateSymbol /
  // insertLastPrivateCompare) in favor of the conditional copy-back.
  for (auto *sym : explicitlyPrivatizedSymbols)
    if (!isException(sym) && (conditionalLpUsesPrivateCopy ||
                              !conditionalLastPrivatizedSymbols.contains(sym)))
      allPrivatizedSymbols.insert(sym);
  if (conditionalLpUsesPrivateCopy)
    for (auto *sym : conditionalLastPrivatizedSymbols)
      if (!isException(sym))
        allPrivatizedSymbols.insert(sym);
  // (A firstprivate + conditional-lastprivate symbol appears in both lists;
  // allPrivatizedSymbols is a SetVector, so it is inserted only once.)
}

bool DataSharingProcessor::needBarrier() {
  // Emit implicit barrier to synchronize threads and avoid data races on
  // initialization of firstprivate variables and post-update of lastprivate
  // variables.
  // Emit implicit barrier for linear clause in the OpenMPIRBuilder.
  // Skip for taskloop: the write-back only happens after the reads are done.

  const auto *ompEval = eval.getIf<parser::OpenMPConstruct>();
  if (ompEval && llvm::omp::allTaskloopSet.test(
                     parser::omp::GetOmpDirectiveName(*ompEval).v))
    return false;

  for (const semantics::Symbol *sym : allPrivatizedSymbols) {
    if (sym->test(semantics::Symbol::Flag::OmpLastPrivate) &&
        (sym->test(semantics::Symbol::Flag::OmpFirstPrivate) ||
         mightHaveReadHostSym.contains(sym)))
      return true;
  }
  return false;
}

void DataSharingProcessor::insertBarrier(
    mlir::omp::PrivateClauseOps *clauseOps) {
  if (!needBarrier())
    return;

  if (useDelayedPrivatization) {
    if (clauseOps)
      clauseOps->privateNeedsBarrier =
          mlir::UnitAttr::get(&converter.getMLIRContext());
  } else {
    mlir::omp::BarrierOp::create(firOpBuilder, converter.getCurrentLocation());
  }
}

void DataSharingProcessor::insertLastPrivateCompare(mlir::Operation *op) {
  mlir::omp::LoopNestOp loopOp;
  if (auto wrapper = mlir::dyn_cast<mlir::omp::LoopWrapperInterface>(op))
    loopOp = mlir::cast<mlir::omp::LoopNestOp>(wrapper.getWrappedLoop());

  mlir::OpBuilder::InsertionGuard guard(firOpBuilder);
  bool hasLastPrivate = [&]() {
    for (const semantics::Symbol *sym : allPrivatizedSymbols) {
      if (const auto *commonDet =
              sym->detailsIf<semantics::CommonBlockDetails>()) {
        for (const auto &mem : commonDet->objects())
          if (mem->test(semantics::Symbol::Flag::OmpLastPrivate))
            return true;
      } else if (sym->test(semantics::Symbol::Flag::OmpLastPrivate) &&
                 !conditionalLastPrivatizedSymbols.contains(sym))
        return true;
    }

    return false;
  }();

  if (!hasLastPrivate)
    return;

  if (mlir::isa<mlir::omp::WsloopOp>(op) || mlir::isa<mlir::omp::SimdOp>(op) ||
      mlir::isa<mlir::omp::TaskloopWrapperOp>(op)) {
    mlir::omp::LoopRelatedClauseOps result;
    llvm::SmallVector<const semantics::Symbol *> iv;
    collectLoopRelatedInfo(converter, converter.getCurrentLocation(), eval,
                           getNestedDoConstruct(eval), clauses, result, iv);

    // Update the original variable just before exiting the worksharing
    // loop. Conversion as follows:
    //
    // omp.wsloop / omp.simd {    omp.wsloop / omp.simd {
    //   omp.loop_nest {            omp.loop_nest {
    //     ...                        ...
    //     store          ===>        store
    //     omp.yield                  %v = arith.addi %iv, %step
    //   }                            %cmp = %step < 0 ? %v < %ub : %v > %ub
    // }                              fir.if %cmp {
    //                                  fir.store %v to %loopIV
    //                                  ^%lpv_update_blk:
    //                                }
    //                                omp.yield
    //                              }
    //                            }
    mlir::Location loc = loopOp.getLoc();
    mlir::Operation *lastOper = loopOp.getRegion().back().getTerminator();
    firOpBuilder.setInsertionPoint(lastOper);

    mlir::Value cmpOp;
    llvm::SmallVector<mlir::Value> vs;
    vs.reserve(loopOp.getIVs().size());
    for (auto [iv, ub, step] : llvm::zip_equal(
             loopOp.getIVs(), result.loopUpperBounds, result.loopSteps)) {
      // v = iv + step
      // cmp = step < 0 ? v < ub : v > ub
      mlir::Value v = mlir::arith::AddIOp::create(firOpBuilder, loc, iv, step);
      vs.push_back(v);
      mlir::Value zero =
          firOpBuilder.createIntegerConstant(loc, step.getType(), 0);
      mlir::Value negativeStep = mlir::arith::CmpIOp::create(
          firOpBuilder, loc, mlir::arith::CmpIPredicate::slt, step, zero);
      mlir::Value vLT = mlir::arith::CmpIOp::create(
          firOpBuilder, loc, mlir::arith::CmpIPredicate::slt, v, ub);
      mlir::Value vGT = mlir::arith::CmpIOp::create(
          firOpBuilder, loc, mlir::arith::CmpIPredicate::sgt, v, ub);
      mlir::Value icmpOp = mlir::arith::SelectOp::create(
          firOpBuilder, loc, negativeStep, vLT, vGT);

      if (cmpOp)
        cmpOp = mlir::arith::AndIOp::create(firOpBuilder, loc, cmpOp, icmpOp);
      else
        cmpOp = icmpOp;
    }

    auto ifOp = fir::IfOp::create(firOpBuilder, loc, cmpOp, /*else*/ false);
    firOpBuilder.setInsertionPointToStart(&ifOp.getThenRegion().front());
    for (auto [v, loopIV] : llvm::zip_equal(vs, loopIVs)) {
      hlfir::Entity loopIVEntity{loopIV};
      loopIVEntity =
          hlfir::derefPointersAndAllocatables(loc, firOpBuilder, loopIVEntity);
      hlfir::AssignOp::create(firOpBuilder, loc, v, loopIVEntity);
    }
    lastPrivIP = firOpBuilder.saveInsertionPoint();
  } else if (mlir::isa<mlir::omp::SectionsOp>(op)) {
    // Already handled by genOMP()
  } else {
    TODO(converter.getCurrentLocation(),
         "lastprivate clause in constructs other than "
         "simd/worksharing-loop/taskloop");
  }
}

bool DataSharingProcessor::isOpenMPPrivatizingConstruct(
    const parser::OpenMPConstruct &omp, llvm::omp::Version version) {
  return llvm::omp::isPrivatizingConstruct(
      parser::omp::GetOmpDirectiveName(omp).v, version);
}

bool DataSharingProcessor::isOpenMPPrivatizingEvaluation(
    const pft::Evaluation &eval) const {
  llvm::omp::Version version = semaCtx.langOptions().getOpenMPVersion();
  return eval.visit([=](auto &&s) {
    using BareS = llvm::remove_cvref_t<decltype(s)>;
    if constexpr (std::is_same_v<BareS, parser::OpenMPConstruct>) {
      return isOpenMPPrivatizingConstruct(s, version);
    } else {
      return false;
    }
  });
}

void DataSharingProcessor::collectSymbolsInNestedRegions(
    lower::pft::Evaluation &eval, semantics::Symbol::Flag flag,
    llvm::SetVector<const semantics::Symbol *> &symbolsInNestedRegions) {
  if (!eval.hasNestedEvaluations())
    return;
  const semantics::Scope *curScope = getCurrentScope(semaCtx, this->eval);
  if (!curScope)
    return;
  llvm::SetVector<const semantics::Symbol *> collectedSymbols;
  for (pft::Evaluation &nestedEval : eval.getNestedEvaluations()) {
    if (isOpenMPPrivatizingEvaluation(nestedEval)) {
      converter.collectSymbolSet(nestedEval, collectedSymbols, flag,
                                 /*collectSymbols=*/true,
                                 /*collectHostAssociatedSymbols=*/false);
    } else {
      // Recursively look for OpenMP constructs within `nestedEval`'s region
      collectSymbolsInNestedRegions(nestedEval, flag, collectedSymbols);
    }
  }
  for (const semantics::Symbol *sym : collectedSymbols)
    if (sym->owner() != *curScope)
      symbolsInNestedRegions.insert(sym);
}

// Collect symbols that `eval` must privatize, but whose data-sharing attributes
// (DSA) are not explicitly determined.
//
// `flag` selects the kind of symbols being collected:
//   - OmpPrivate / OmpFirstPrivate: symbols privatized by a DEFAULT clause.
//   - OmpImplicit: symbols with an implicitly determined DSA.
//   - OmpPreDetermined: symbols with a predetermined DSA.
//   - std::nullopt: indirect references (see collectIndirectReferences()).
//
// `allSymbols` contains the symbols referenced in `eval` (or the indirect
// references, when `flag` is not set).
// `symbolsInNestedRegions` contains the symbols referenced in privatizing
// constructs nested in `eval` that are not owned by `eval`'s scope. When
// `flag` is set, both sets are restricted to symbols that have it.
//
// Excluding some special cases, a symbol is privatized if it is in
// `allSymbols` but not in `symbolsInNestedRegions`, and it is owned by
// `eval`'s scope, meaning semantics assigned its DSA to this construct.
//
// The selected symbols are added to `allPrivatizedSymbols`, and also to
// `*symbols` when `symbols` is not null.
void DataSharingProcessor::collectPrivatizedSymbols(
    std::optional<semantics::Symbol::Flag> flag,
    const llvm::SetVector<const semantics::Symbol *> &allSymbols,
    const llvm::SetVector<const semantics::Symbol *> &symbolsInNestedRegions,
    llvm::SetVector<const semantics::Symbol *> *symbols) {
  const semantics::Scope *curScope = getCurrentScope(semaCtx, eval);
  if (!curScope)
    return;

  // Filter-out symbols that must not be privatized.
  bool collectImplicit = false;
  bool collectPreDetermined = false;
  bool collectIndirectRefs = !flag.has_value();
  if (!collectIndirectRefs) {
    collectImplicit = *flag == semantics::Symbol::Flag::OmpImplicit;
    collectPreDetermined = *flag == semantics::Symbol::Flag::OmpPreDetermined;
  }

  auto shouldCollectSymbol = [&](const semantics::Symbol *sym) {
    // Linear symbols are privatized by the linear clause, except when they are
    // enclosed within TARGET, where implicit linearization is skipped.
    mlir::Operation *currentOp =
        firOpBuilder.getInsertionBlock()->getParentOp();
    bool inTarget =
        currentOp && (mlir::isa<mlir::omp::TargetOp>(currentOp) ||
                      currentOp->getParentOfType<mlir::omp::TargetOp>());

    if (sym->test(semantics::Symbol::Flag::OmpLinear) && !inTarget)
      return false;

    if (collectImplicit) {
      // If we're a combined construct with a target region, implicit
      // firstprivate captures, should only belong to the target region
      // and not be added/captured by later directives. Parallel regions
      // will likely want the same captures to be shared and for SIMD it's
      // illegal to have firstprivate clauses.
      if (isConstructWithTopLevelTarget(eval) && !isTargetPrivatization &&
          sym->test(semantics::Symbol::Flag::OmpFirstPrivate)) {
        return false;
      }
      return sym->test(semantics::Symbol::Flag::OmpImplicit);
    }

    if (collectPreDetermined)
      return sym->test(semantics::Symbol::Flag::OmpPreDetermined);

    if (collectIndirectRefs)
      return true;

    return !sym->test(semantics::Symbol::Flag::OmpImplicit) &&
           !sym->test(semantics::Symbol::Flag::OmpPreDetermined);
  };

  for (const auto *sym : allSymbols) {
    // Metadirective loops also have symbols in spliced nested evaluations,
    // which means that not all symbols that must be privatized will be owned
    // by the current scope.
    if (semantics::omp::IsPrivatizable(*sym) &&
        !symbolsInNestedRegions.contains(sym) &&
        !explicitlyPrivatizedSymbols.contains(sym) &&
        shouldCollectSymbol(sym) &&
        (isMetadirectiveLoop || sym->owner() == *curScope)) {
      allPrivatizedSymbols.insert(sym);
      if (symbols)
        symbols->insert(sym);
    }
  }
}

void DataSharingProcessor::collectSymbols(
    semantics::Symbol::Flag flag,
    llvm::SetVector<const semantics::Symbol *> *symbols) {
  // Collect all symbols referenced in the evaluation being processed,
  // that matches 'flag'.
  llvm::SetVector<const semantics::Symbol *> allSymbols;
  converter.collectSymbolSet(eval, allSymbols, flag,
                             /*collectSymbols=*/true,
                             /*collectHostAssociatedSymbols=*/true);

  // Collect symbols from spliced nested evaluations for metadirectives.
  if (isMetadirectiveLoop && eval.hasNestedEvaluations()) {
    for (auto &nestedEval : eval.getNestedEvaluations())
      converter.collectSymbolSet(nestedEval, allSymbols, flag,
                                 /*collectSymbols=*/true,
                                 /*collectHostAssociatedSymbols=*/true);
  }

  llvm::SetVector<const semantics::Symbol *> symbolsInNestedRegions;
  collectSymbolsInNestedRegions(eval, flag, symbolsInNestedRegions);

  collectPrivatizedSymbols(flag, allSymbols, symbolsInNestedRegions);
}

void DataSharingProcessor::collectDefaultSymbols() {
  using DataSharingAttribute = omp::clause::Default::DataSharingAttribute;
  for (const omp::Clause &clause : clauses) {
    if (const auto *defaultClause =
            std::get_if<omp::clause::Default>(&clause.u)) {
      if (defaultClause->v == DataSharingAttribute::Private)
        collectSymbols(semantics::Symbol::Flag::OmpPrivate, &defaultSymbols);
      else if (defaultClause->v == DataSharingAttribute::Firstprivate)
        collectSymbols(semantics::Symbol::Flag::OmpFirstPrivate,
                       &defaultSymbols);
    }
  }
}

void DataSharingProcessor::collectImplicitSymbols() {
  // There will be no implicit symbols when a default clause is present.
  if (defaultSymbols.empty())
    collectSymbols(semantics::Symbol::Flag::OmpImplicit);
}

void DataSharingProcessor::collectPreDeterminedSymbols() {
  if (shouldCollectPreDeterminedSymbols)
    collectSymbols(semantics::Symbol::Flag::OmpPreDetermined);
}

// Collect symbols that may be referenced indirectly by lastprivate or linear
// DSAs in nested constructs. Their privatization must not be skipped in the
// enclosing context, to avoid updating the wrong symbol.
void DataSharingProcessor::collectIndirectReferences() {
  // For compound constructs, collect the symbols only for the last leaf.
  if (!shouldCollectPreDeterminedSymbols)
    return;

  const semantics::Scope *curScope = getCurrentScope(semaCtx, eval);
  if (!curScope)
    return;

  // Collect all linear and lastprivate symbols.
  llvm::SetVector<const semantics::Symbol *> allSymbols;
  llvm::SetVector<const semantics::Symbol *> symbolsInNestedRegions;

  auto collect = [&](semantics::Symbol::Flag flag) {
    converter.collectSymbolSet(eval, allSymbols, flag,
                               /*collectSymbols=*/true,
                               /*collectHostAssociatedSymbols=*/true);
    collectSymbolsInNestedRegions(eval, flag, symbolsInNestedRegions);
  };
  collect(semantics::Symbol::Flag::OmpLinear);
  collect(semantics::Symbol::Flag::OmpLastPrivate);

  auto isPrivate = [](const semantics::Symbol &sym) {
    using Symbol = semantics::Symbol;
    Symbol::Flags privateFlags{
        Symbol::Flag::OmpPrivate, Symbol::Flag::OmpFirstPrivate,
        Symbol::Flag::OmpLastPrivate, Symbol::Flag::OmpLinear};
    return (sym.flags() & privateFlags).any();
  };

  // Find indirect references.
  //
  // A symbol in the current scope may be indirectly referenced by a DSA in
  // nested constructs.
  // To simplify the implementation, any linear/lastprivate symbol in a nested
  // region is considered as an indirect reference. The produced output is
  // correct, although it may contain privatizations that could be eliminated.
  llvm::SetVector<const semantics::Symbol *> indirectReferences;
  for (auto it = curScope->begin(), end = curScope->end(); it != end; ++it) {
    const semantics::Symbol &sym = *it->second;
    if (!isPrivate(sym))
      continue;

    for (const semantics::Symbol *nestedSym : symbolsInNestedRegions) {
      if (&sym != nestedSym && sym.name() == nestedSym->name())
        indirectReferences.insert(&sym);
    }
  }

  // Remove indirectly referenced symbols from nested regions, to force them
  // to be privatized.
  for (const semantics::Symbol *sym : indirectReferences)
    symbolsInNestedRegions.remove(sym);

  collectPrivatizedSymbols(std::nullopt, indirectReferences,
                           symbolsInNestedRegions);
}

void DataSharingProcessor::privatize(mlir::omp::PrivateClauseOps *clauseOps,
                                     std::optional<llvm::omp::Directive> dir) {
  for (const semantics::Symbol *sym : allPrivatizedSymbols) {
    if (const auto *commonDet =
            sym->detailsIf<semantics::CommonBlockDetails>()) {
      for (const auto &mem : commonDet->objects())
        privatizeSymbol(&*mem, clauseOps, dir);
    } else
      privatizeSymbol(sym, clauseOps, dir);
  }
}

void DataSharingProcessor::copyLastPrivatize(mlir::Operation *op) {
  insertLastPrivateCompare(op);
  for (const semantics::Symbol *sym : allPrivatizedSymbols)
    if (const auto *commonDet =
            sym->detailsIf<semantics::CommonBlockDetails>()) {
      for (const auto &mem : commonDet->objects()) {
        copyLastPrivateSymbol(&*mem, &lastPrivIP);
      }
    } else {
      copyLastPrivateSymbol(sym, &lastPrivIP);
    }
}

void DataSharingProcessor::privatizeSymbol(
    const semantics::Symbol *symToPrivatize,
    mlir::omp::PrivateClauseOps *clauseOps,
    std::optional<llvm::omp::Directive> dir, bool isLinear) {
  if (!useDelayedPrivatization) {
    cloneSymbol(symToPrivatize);
    copyFirstPrivateSymbol(symToPrivatize);
    return;
  }

  Fortran::lower::privatizeSymbol<mlir::omp::PrivateClauseOp,
                                  mlir::omp::PrivateClauseOps>(
      converter, firOpBuilder, symTable, allPrivatizedSymbols,
      mightHaveReadHostSym, symToPrivatize, clauseOps, dir,
      forceHeapAllocationForPrivateDynamicArrays, isLinear);
}
} // namespace omp
} // namespace lower
} // namespace Fortran