flang/lib/Lower/ConvertArrayConstructor.cpp

   1 //===- ConvertArrayConstructor.cpp -- Array Constructor ---------*- C++ -*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "flang/Lower/ConvertArrayConstructor.h"
  10 #include "flang/Evaluate/expression.h"
  11 #include "flang/Lower/AbstractConverter.h"
  12 #include "flang/Lower/ConvertExprToHLFIR.h"
  13 #include "flang/Lower/ConvertType.h"
  14 #include "flang/Lower/StatementContext.h"
  15 #include "flang/Lower/SymbolMap.h"
  16 #include "flang/Optimizer/Builder/HLFIRTools.h"
  17 #include "flang/Optimizer/Builder/Runtime/ArrayConstructor.h"
  18 #include "flang/Optimizer/Builder/Runtime/RTBuilder.h"
  19 #include "flang/Optimizer/Builder/TemporaryStorage.h"
  20 #include "flang/Optimizer/Builder/Todo.h"
  21 #include "flang/Optimizer/HLFIR/HLFIROps.h"
  22
  23 // Array constructors are lowered with three different strategies.
  24 // All strategies are not possible with all array constructors.
  25 //
  26 // - Strategy 1: runtime approach (RuntimeTempStrategy).
  27 //   This strategy works will all array constructors, but will create more
  28 //   complex code that is harder to optimize. An allocatable temp is created,
  29 //   it may be unallocated if the array constructor length parameters or extent
  30 //   could not be computed. Then, the runtime is called to push lowered
  31 //   ac-value (array constructor elements) into the allocatable. The runtime
  32 //   will allocate or reallocate as needed while values are being pushed.
  33 //   In the end, the allocatable contain a temporary with all the array
  34 //   constructor evaluated elements.
  35 //
  36 // - Strategy 2: inlined temporary approach (InlinedTempStrategyImpl)
  37 //   This strategy can only be used if the array constructor extent and length
  38 //   parameters can be pre-computed without evaluating any ac-value, and if all
  39 //   of the ac-value are scalars (at least for now).
  40 //   A temporary is allocated inline in one go, and an index pointing at the
  41 //   current ac-value position in the array constructor element sequence is
  42 //   maintained and used to store ac-value as they are being lowered.
  43 //
  44 // - Strategy 3: "function of the indices" approach (AsElementalStrategy)
  45 //   This strategy can only be used if the array constructor extent and length
  46 //   parameters can be pre-computed and, if the array constructor is of the
  47 //   form "[(scalar_expr, ac-implied-do-control)]". In this case, it is lowered
  48 //   into an hlfir.elemental without creating any temporary in lowering. This
  49 //   form should maximize the chance of array temporary elision when assigning
  50 //   the array constructor, potentially reshaped, to an array variable.
  51 //
  52 //   The array constructor lowering looks like:
  53 //   ```
  54 //     strategy = selectArrayCtorLoweringStrategy(array-ctor-expr);
  55 //     for (ac-value : array-ctor-expr)
  56 //       if (ac-value is expression) {
  57 //         strategy.pushValue(ac-value);
  58 //       } else if (ac-value is implied-do) {
  59 //         strategy.startImpliedDo(lower, upper, stride);
  60 //         strategy.startImpliedDoScope();
  61 //         // lower nested values
  62 //         ...
  63 //         strategy.endImpliedDoScope();
  64 //       }
  65 //     result = strategy.finishArrayCtorLowering();
  66 //   ```
  67
  68 //===----------------------------------------------------------------------===//
  69 //   Definition of the lowering strategies. Each lowering strategy is defined
  70 //   as a class that implements "pushValue", "startImpliedDo" and
  71 //   "finishArrayCtorLowering". A strategy may optionally override
  72 //   "startImpliedDoScope" and "endImpliedDoScope" virtual methods
  73 //   of its base class StrategyBase.
  74 //===----------------------------------------------------------------------===//
  75
  76 namespace {
  77 /// Class provides common implementation of scope push/pop methods
  78 /// that update StatementContext scopes and SymMap bindings.
  79 /// They might be overridden by the lowering strategies, e.g.
  80 /// see AsElementalStrategy.
  81 class StrategyBase {
  82 public:
  83   StrategyBase(Fortran::lower::StatementContext &stmtCtx,
  84                Fortran::lower::SymMap &symMap)
  85       : stmtCtx{stmtCtx}, symMap{symMap} {};
  86   virtual ~StrategyBase() = default;
  87
  88   virtual void startImpliedDoScope(llvm::StringRef doName,
  89                                    mlir::Value indexValue) {
  90     symMap.pushImpliedDoBinding(doName, indexValue);
  91     stmtCtx.pushScope();
  92   }
  93
  94   virtual void endImpliedDoScope() {
  95     stmtCtx.finalizeAndPop();
  96     symMap.popImpliedDoBinding();
  97   }
  98
  99 protected:
 100   Fortran::lower::StatementContext &stmtCtx;
 101   Fortran::lower::SymMap &symMap;
 102 };
 103
 104 /// Class that implements the "inlined temp strategy" to lower array
 105 /// constructors. It must be provided a boolean to indicate if the array
 106 /// constructor has any implied-do-loop.
 107 template <bool hasLoops>
 108 class InlinedTempStrategyImpl : public StrategyBase,
 109                                 public fir::factory::HomogeneousScalarStack {
 110   /// Name that will be given to the temporary allocation and hlfir.declare in
 111   /// the IR.
 112   static constexpr char tempName[] = ".tmp.arrayctor";
 113
 114 public:
 115   /// Start lowering an array constructor according to the inline strategy.
 116   /// The temporary is created right away.
 117   InlinedTempStrategyImpl(mlir::Location loc, fir::FirOpBuilder &builder,
 118                           Fortran::lower::StatementContext &stmtCtx,
 119                           Fortran::lower::SymMap &symMap,
 120                           fir::SequenceType declaredType, mlir::Value extent,
 121                           llvm::ArrayRef<mlir::Value> lengths)
 122       : StrategyBase{stmtCtx, symMap},
 123         fir::factory::HomogeneousScalarStack{
 124             loc,      builder, declaredType,
 125             extent,   lengths, /*allocateOnHeap=*/true,
 126             hasLoops, tempName} {}
 127
 128   /// Push a lowered ac-value into the current insertion point and
 129   /// increment the insertion point.
 130   using fir::factory::HomogeneousScalarStack::pushValue;
 131
 132   /// Start a fir.do_loop with the control from an implied-do and return
 133   /// the loop induction variable that is the ac-do-variable value.
 134   /// Only usable if the counter is able to track the position through loops.
 135   mlir::Value startImpliedDo(mlir::Location loc, fir::FirOpBuilder &builder,
 136                              mlir::Value lower, mlir::Value upper,
 137                              mlir::Value stride) {
 138     if constexpr (!hasLoops)
 139       fir::emitFatalError(loc, "array constructor lowering is inconsistent");
 140     auto loop = builder.create<fir::DoLoopOp>(loc, lower, upper, stride,
 141                                               /*unordered=*/false,
 142                                               /*finalCount=*/false);
 143     builder.setInsertionPointToStart(loop.getBody());
 144     return loop.getInductionVar();
 145   }
 146
 147   /// Move the temporary to an hlfir.expr value (array constructors are not
 148   /// variables and cannot be further modified).
 149   hlfir::Entity finishArrayCtorLowering(mlir::Location loc,
 150                                         fir::FirOpBuilder &builder) {
 151     return moveStackAsArrayExpr(loc, builder);
 152   }
 153 };
 154
 155 /// Semantic analysis expression rewrites unroll implied do loop with
 156 /// compile time constant bounds (even if huge). So using a minimalistic
 157 /// counter greatly reduces the generated IR for simple but big array
 158 /// constructors [(i,i=1,constant-expr)] that are expected to be quite
 159 /// common.
 160 using LooplessInlinedTempStrategy = InlinedTempStrategyImpl</*hasLoops=*/false>;
 161 /// A generic memory based counter that can deal with all cases of
 162 /// "inlined temp strategy". The counter value is stored in a temp
 163 /// from which it is loaded, incremented, and stored every time an
 164 /// ac-value is pushed.
 165 using InlinedTempStrategy = InlinedTempStrategyImpl</*hasLoops=*/true>;
 166
 167 /// Class that implements the "as function of the indices" lowering strategy.
 168 /// It will lower [(scalar_expr(i), i=l,u,s)] to:
 169 /// ```
 170 ///   %extent = max((%u-%l+1)/%s, 0)
 171 ///   %shape = fir.shape %extent
 172 ///   %elem = hlfir.elemental %shape {
 173 ///     ^bb0(%pos:index):
 174 ///      %i = %l+(%i-1)*%s
 175 ///      %value = scalar_expr(%i)
 176 ///       hlfir.yield_element %value
 177 ///    }
 178 /// ```
 179 /// That way, no temporary is created in lowering, and if the array constructor
 180 /// is part of a more complex elemental expression, or an assignment, it will be
 181 /// trivial to "inline" it in the expression or assignment loops if allowed by
 182 /// alias analysis.
 183 /// This lowering is however only possible for the form of array constructors as
 184 /// in the illustration above. It could be extended to deeper independent
 185 /// implied-do nest and wrapped in an hlfir.reshape to a rank 1 array. But this
 186 /// op does not exist yet, so this is left for the future if it appears
 187 /// profitable.
 188 class AsElementalStrategy : public StrategyBase {
 189 public:
 190   /// The constructor only gathers the operands to create the hlfir.elemental.
 191   AsElementalStrategy(mlir::Location loc, fir::FirOpBuilder &builder,
 192                       Fortran::lower::StatementContext &stmtCtx,
 193                       Fortran::lower::SymMap &symMap,
 194                       fir::SequenceType declaredType, mlir::Value extent,
 195                       llvm::ArrayRef<mlir::Value> lengths)
 196       : StrategyBase{stmtCtx, symMap}, shape{builder.genShape(loc, {extent})},
 197         lengthParams{lengths.begin(), lengths.end()},
 198         exprType{getExprType(declaredType)} {}
 199
 200   static hlfir::ExprType getExprType(fir::SequenceType declaredType) {
 201     // Note: 7.8 point 4: the dynamic type of an array constructor is its static
 202     // type, it is not polymorphic.
 203     return hlfir::ExprType::get(declaredType.getContext(),
 204                                 declaredType.getShape(),
 205                                 declaredType.getEleTy(),
 206                                 /*isPolymorphic=*/false);
 207   }
 208
 209   /// Create the hlfir.elemental and compute the ac-implied-do-index value
 210   /// given the lower bound and stride (compute "%i" in the illustration above).
 211   mlir::Value startImpliedDo(mlir::Location loc, fir::FirOpBuilder &builder,
 212                              mlir::Value lower, mlir::Value upper,
 213                              mlir::Value stride) {
 214     assert(!elementalOp && "expected only one implied-do");
 215     mlir::Value one =
 216         builder.createIntegerConstant(loc, builder.getIndexType(), 1);
 217     elementalOp = builder.create<hlfir::ElementalOp>(
 218         loc, exprType, shape,
 219         /*mold=*/nullptr, lengthParams, /*isUnordered=*/true);
 220     builder.setInsertionPointToStart(elementalOp.getBody());
 221     // implied-do-index = lower+((i-1)*stride)
 222     mlir::Value diff = builder.create<mlir::arith::SubIOp>(
 223         loc, elementalOp.getIndices()[0], one);
 224     mlir::Value mul = builder.create<mlir::arith::MulIOp>(loc, diff, stride);
 225     mlir::Value add = builder.create<mlir::arith::AddIOp>(loc, lower, mul);
 226     return add;
 227   }
 228
 229   /// Create the elemental hlfir.yield_element with the scalar ac-value.
 230   void pushValue(mlir::Location loc, fir::FirOpBuilder &builder,
 231                  hlfir::Entity value) {
 232     assert(value.isScalar() && "cannot use hlfir.elemental with array values");
 233     assert(elementalOp && "array constructor must contain an outer implied-do");
 234     mlir::Value elementResult = value;
 235     if (fir::isa_trivial(elementResult.getType()))
 236       elementResult =
 237           builder.createConvert(loc, exprType.getElementType(), elementResult);
 238
 239     // The clean-ups associated with the implied-do body operations
 240     // must be initiated before the YieldElementOp, so we have to pop the scope
 241     // right now.
 242     stmtCtx.finalizeAndPop();
 243
 244     // This is a hacky way to get rid of the DestroyOp clean-up
 245     // associated with the final ac-value result if it is hlfir.expr.
 246     // Example:
 247     //   ... = (/(REPEAT(REPEAT(CHAR(i),2),2),i=1,n)/)
 248     // Each intrinsic call lowering will produce hlfir.expr result
 249     // with the associated clean-up, but only the last of them
 250     // is wrong. It is wrong because the value is used in hlfir.yield_element,
 251     // so it cannot be destroyed.
 252     mlir::Operation *destroyOp = nullptr;
 253     for (mlir::Operation *useOp : elementResult.getUsers())
 254       if (mlir::isa<hlfir::DestroyOp>(useOp)) {
 255         if (destroyOp)
 256           fir::emitFatalError(loc,
 257                               "multiple DestroyOp's for ac-value expression");
 258         destroyOp = useOp;
 259       }
 260
 261     if (destroyOp)
 262       destroyOp->erase();
 263
 264     builder.create<hlfir::YieldElementOp>(loc, elementResult);
 265   }
 266
 267   // Override the default, because the context scope must be popped in
 268   // pushValue().
 269   virtual void endImpliedDoScope() override { symMap.popImpliedDoBinding(); }
 270
 271   /// Return the created hlfir.elemental.
 272   hlfir::Entity finishArrayCtorLowering(mlir::Location loc,
 273                                         fir::FirOpBuilder &builder) {
 274     return hlfir::Entity{elementalOp};
 275   }
 276
 277 private:
 278   mlir::Value shape;
 279   llvm::SmallVector<mlir::Value> lengthParams;
 280   hlfir::ExprType exprType;
 281   hlfir::ElementalOp elementalOp{};
 282 };
 283
 284 /// Class that implements the "runtime temp strategy" to lower array
 285 /// constructors.
 286 class RuntimeTempStrategy : public StrategyBase {
 287   /// Name that will be given to the temporary allocation and hlfir.declare in
 288   /// the IR.
 289   static constexpr char tempName[] = ".tmp.arrayctor";
 290
 291 public:
 292   /// Start lowering an array constructor according to the runtime strategy.
 293   /// The temporary is only created if the extents and length parameters are
 294   /// already known. Otherwise, the handling of the allocation (and
 295   /// reallocation) is left up to the runtime.
 296   /// \p extent is the pre-computed extent of the array constructor, if it could
 297   /// be pre-computed. It is std::nullopt otherwise.
 298   /// \p lengths are the pre-computed length parameters of the array
 299   /// constructor, if they could be precomputed. \p missingLengthParameters is
 300   /// set to true if the length parameters could not be precomputed.
 301   RuntimeTempStrategy(mlir::Location loc, fir::FirOpBuilder &builder,
 302                       Fortran::lower::StatementContext &stmtCtx,
 303                       Fortran::lower::SymMap &symMap,
 304                       fir::SequenceType declaredType,
 305                       std::optional<mlir::Value> extent,
 306                       llvm::ArrayRef<mlir::Value> lengths,
 307                       bool missingLengthParameters)
 308       : StrategyBase{stmtCtx, symMap},
 309         arrayConstructorElementType{declaredType.getEleTy()} {
 310     mlir::Type heapType = fir::HeapType::get(declaredType);
 311     mlir::Type boxType = fir::BoxType::get(heapType);
 312     allocatableTemp = builder.createTemporary(loc, boxType, tempName);
 313     mlir::Value initialBoxValue;
 314     if (extent && !missingLengthParameters) {
 315       llvm::SmallVector<mlir::Value, 1> extents{*extent};
 316       mlir::Value tempStorage = builder.createHeapTemporary(
 317           loc, declaredType, tempName, extents, lengths);
 318       mlir::Value shape = builder.genShape(loc, extents);
 319       declare = builder.create<hlfir::DeclareOp>(
 320           loc, tempStorage, tempName, shape, lengths,
 321           /*dummy_scope=*/nullptr, fir::FortranVariableFlagsAttr{});
 322       initialBoxValue =
 323           builder.createBox(loc, boxType, declare->getOriginalBase(), shape,
 324                             /*slice=*/mlir::Value{}, lengths, /*tdesc=*/{});
 325     } else {
 326       // The runtime will have to do the initial allocation.
 327       // The declare operation cannot be emitted in this case since the final
 328       // array constructor has not yet been allocated. Instead, the resulting
 329       // temporary variable will be extracted from the allocatable descriptor
 330       // after all the API calls.
 331       // Prepare the initial state of the allocatable descriptor with a
 332       // deallocated status and all the available knowledge about the extent
 333       // and length parameters.
 334       llvm::SmallVector<mlir::Value> emboxLengths(lengths.begin(),
 335                                                   lengths.end());
 336       if (!extent)
 337         extent = builder.createIntegerConstant(loc, builder.getIndexType(), 0);
 338       if (missingLengthParameters) {
 339         if (mlir::isa<fir::CharacterType>(declaredType.getEleTy()))
 340           emboxLengths.push_back(builder.createIntegerConstant(
 341               loc, builder.getCharacterLengthType(), 0));
 342         else
 343           TODO(loc,
 344                "parametrized derived type array constructor without type-spec");
 345       }
 346       mlir::Value nullAddr = builder.createNullConstant(loc, heapType);
 347       mlir::Value shape = builder.genShape(loc, {*extent});
 348       initialBoxValue = builder.createBox(loc, boxType, nullAddr, shape,
 349                                           /*slice=*/mlir::Value{}, emboxLengths,
 350                                           /*tdesc=*/{});
 351     }
 352     builder.create<fir::StoreOp>(loc, initialBoxValue, allocatableTemp);
 353     arrayConstructorVector = fir::runtime::genInitArrayConstructorVector(
 354         loc, builder, allocatableTemp,
 355         builder.createBool(loc, missingLengthParameters));
 356   }
 357
 358   bool useSimplePushRuntime(hlfir::Entity value) {
 359     return value.isScalar() &&
 360            !mlir::isa<fir::CharacterType>(arrayConstructorElementType) &&
 361            !fir::isRecordWithAllocatableMember(arrayConstructorElementType) &&
 362            !fir::isRecordWithTypeParameters(arrayConstructorElementType);
 363   }
 364
 365   /// Push a lowered ac-value into the array constructor vector using
 366   /// the runtime API.
 367   void pushValue(mlir::Location loc, fir::FirOpBuilder &builder,
 368                  hlfir::Entity value) {
 369     if (useSimplePushRuntime(value)) {
 370       auto [addrExv, cleanUp] = hlfir::convertToAddress(
 371           loc, builder, value, arrayConstructorElementType);
 372       mlir::Value addr = fir::getBase(addrExv);
 373       if (mlir::isa<fir::BaseBoxType>(addr.getType()))
 374         addr = builder.create<fir::BoxAddrOp>(loc, addr);
 375       fir::runtime::genPushArrayConstructorSimpleScalar(
 376           loc, builder, arrayConstructorVector, addr);
 377       if (cleanUp)
 378         (*cleanUp)();
 379       return;
 380     }
 381     auto [boxExv, cleanUp] =
 382         hlfir::convertToBox(loc, builder, value, arrayConstructorElementType);
 383     fir::runtime::genPushArrayConstructorValue(
 384         loc, builder, arrayConstructorVector, fir::getBase(boxExv));
 385     if (cleanUp)
 386       (*cleanUp)();
 387   }
 388
 389   /// Start a fir.do_loop with the control from an implied-do and return
 390   /// the loop induction variable that is the ac-do-variable value.
 391   mlir::Value startImpliedDo(mlir::Location loc, fir::FirOpBuilder &builder,
 392                              mlir::Value lower, mlir::Value upper,
 393                              mlir::Value stride) {
 394     auto loop = builder.create<fir::DoLoopOp>(loc, lower, upper, stride,
 395                                               /*unordered=*/false,
 396                                               /*finalCount=*/false);
 397     builder.setInsertionPointToStart(loop.getBody());
 398     return loop.getInductionVar();
 399   }
 400
 401   /// Move the temporary to an hlfir.expr value (array constructors are not
 402   /// variables and cannot be further modified).
 403   hlfir::Entity finishArrayCtorLowering(mlir::Location loc,
 404                                         fir::FirOpBuilder &builder) {
 405     // Temp is created using createHeapTemporary, or allocated on the heap
 406     // by the runtime.
 407     mlir::Value mustFree = builder.createBool(loc, true);
 408     mlir::Value temp;
 409     if (declare)
 410       temp = declare->getBase();
 411     else
 412       temp = hlfir::derefPointersAndAllocatables(
 413           loc, builder, hlfir::Entity{allocatableTemp});
 414     auto hlfirExpr = builder.create<hlfir::AsExprOp>(loc, temp, mustFree);
 415     return hlfir::Entity{hlfirExpr};
 416   }
 417
 418 private:
 419   /// Element type of the array constructor being built.
 420   mlir::Type arrayConstructorElementType;
 421   /// Allocatable descriptor for the storage of the array constructor being
 422   /// built.
 423   mlir::Value allocatableTemp;
 424   /// Structure that allows the runtime API to maintain the status of
 425   /// of the array constructor being built between two API calls.
 426   mlir::Value arrayConstructorVector;
 427   /// DeclareOp for the array constructor storage, if it was possible to
 428   /// allocate it before any API calls.
 429   std::optional<hlfir::DeclareOp> declare;
 430 };
 431
 432 /// Wrapper class that dispatch to the selected array constructor lowering
 433 /// strategy and does nothing else.
 434 class ArrayCtorLoweringStrategy {
 435 public:
 436   template <typename A>
 437   ArrayCtorLoweringStrategy(A &&impl) : implVariant{std::forward<A>(impl)} {}
 438
 439   void pushValue(mlir::Location loc, fir::FirOpBuilder &builder,
 440                  hlfir::Entity value) {
 441     return Fortran::common::visit(
 442         [&](auto &impl) { return impl.pushValue(loc, builder, value); },
 443         implVariant);
 444   }
 445
 446   mlir::Value startImpliedDo(mlir::Location loc, fir::FirOpBuilder &builder,
 447                              mlir::Value lower, mlir::Value upper,
 448                              mlir::Value stride) {
 449     return Fortran::common::visit(
 450         [&](auto &impl) {
 451           return impl.startImpliedDo(loc, builder, lower, upper, stride);
 452         },
 453         implVariant);
 454   }
 455
 456   hlfir::Entity finishArrayCtorLowering(mlir::Location loc,
 457                                         fir::FirOpBuilder &builder) {
 458     return Fortran::common::visit(
 459         [&](auto &impl) { return impl.finishArrayCtorLowering(loc, builder); },
 460         implVariant);
 461   }
 462
 463   void startImpliedDoScope(llvm::StringRef doName, mlir::Value indexValue) {
 464     Fortran::common::visit(
 465         [&](auto &impl) {
 466           return impl.startImpliedDoScope(doName, indexValue);
 467         },
 468         implVariant);
 469   }
 470
 471   void endImpliedDoScope() {
 472     Fortran::common::visit([&](auto &impl) { return impl.endImpliedDoScope(); },
 473                            implVariant);
 474   }
 475
 476 private:
 477   std::variant<InlinedTempStrategy, LooplessInlinedTempStrategy,
 478                AsElementalStrategy, RuntimeTempStrategy>
 479       implVariant;
 480 };
 481 } // namespace
 482
 483 //===----------------------------------------------------------------------===//
 484 //   Definition of selectArrayCtorLoweringStrategy and its helpers.
 485 //   This is the code that analyses the evaluate::ArrayConstructor<T>,
 486 //   pre-lowers the array constructor extent and length parameters if it can,
 487 //   and chooses the lowering strategy.
 488 //===----------------------------------------------------------------------===//
 489
 490 /// Helper to lower a scalar extent expression (like implied-do bounds).
 491 static mlir::Value lowerExtentExpr(mlir::Location loc,
 492                                    Fortran::lower::AbstractConverter &converter,
 493                                    Fortran::lower::SymMap &symMap,
 494                                    Fortran::lower::StatementContext &stmtCtx,
 495                                    const Fortran::evaluate::ExtentExpr &expr) {
 496   fir::FirOpBuilder &builder = converter.getFirOpBuilder();
 497   mlir::IndexType idxTy = builder.getIndexType();
 498   hlfir::Entity value = Fortran::lower::convertExprToHLFIR(
 499       loc, converter, toEvExpr(expr), symMap, stmtCtx);
 500   value = hlfir::loadTrivialScalar(loc, builder, value);
 501   return builder.createConvert(loc, idxTy, value);
 502 }
 503
 504 namespace {
 505 /// Helper class to lower the array constructor type and its length parameters.
 506 /// The length parameters, if any, are only lowered if this does not require
 507 /// evaluating an ac-value.
 508 template <typename T>
 509 struct LengthAndTypeCollector {
 510   static mlir::Type collect(mlir::Location,
 511                             Fortran::lower::AbstractConverter &converter,
 512                             const Fortran::evaluate::ArrayConstructor<T> &,
 513                             Fortran::lower::SymMap &,
 514                             Fortran::lower::StatementContext &,
 515                             mlir::SmallVectorImpl<mlir::Value> &) {
 516     // Numerical and Logical types.
 517     return Fortran::lower::getFIRType(&converter.getMLIRContext(), T::category,
 518                                       T::kind, /*lenParams*/ {});
 519   }
 520 };
 521
 522 template <>
 523 struct LengthAndTypeCollector<Fortran::evaluate::SomeDerived> {
 524   static mlir::Type collect(
 525       mlir::Location loc, Fortran::lower::AbstractConverter &converter,
 526       const Fortran::evaluate::ArrayConstructor<Fortran::evaluate::SomeDerived>
 527           &arrayCtorExpr,
 528       Fortran::lower::SymMap &symMap, Fortran::lower::StatementContext &stmtCtx,
 529       mlir::SmallVectorImpl<mlir::Value> &lengths) {
 530     // Array constructors cannot be unlimited polymorphic (C7113), so there must
 531     // be a derived type spec available.
 532     return Fortran::lower::translateDerivedTypeToFIRType(
 533         converter, arrayCtorExpr.result().derivedTypeSpec());
 534   }
 535 };
 536
 537 template <int Kind>
 538 using Character =
 539     Fortran::evaluate::Type<Fortran::common::TypeCategory::Character, Kind>;
 540 template <int Kind>
 541 struct LengthAndTypeCollector<Character<Kind>> {
 542   static mlir::Type collect(
 543       mlir::Location loc, Fortran::lower::AbstractConverter &converter,
 544       const Fortran::evaluate::ArrayConstructor<Character<Kind>> &arrayCtorExpr,
 545       Fortran::lower::SymMap &symMap, Fortran::lower::StatementContext &stmtCtx,
 546       mlir::SmallVectorImpl<mlir::Value> &lengths) {
 547     llvm::SmallVector<Fortran::lower::LenParameterTy> typeLengths;
 548     if (const Fortran::evaluate::ExtentExpr *lenExpr = arrayCtorExpr.LEN()) {
 549       lengths.push_back(
 550           lowerExtentExpr(loc, converter, symMap, stmtCtx, *lenExpr));
 551       if (std::optional<std::int64_t> cstLen =
 552               Fortran::evaluate::ToInt64(*lenExpr))
 553         typeLengths.push_back(*cstLen);
 554     }
 555     return Fortran::lower::getFIRType(&converter.getMLIRContext(),
 556                                       Fortran::common::TypeCategory::Character,
 557                                       Kind, typeLengths);
 558   }
 559 };
 560 } // namespace
 561
 562 /// Does the array constructor have length parameters that
 563 /// LengthAndTypeCollector::collect could not lower because this requires
 564 /// lowering an ac-value and must be delayed?
 565 static bool missingLengthParameters(mlir::Type elementType,
 566                                     llvm::ArrayRef<mlir::Value> lengths) {
 567   return (mlir::isa<fir::CharacterType>(elementType) ||
 568           fir::isRecordWithTypeParameters(elementType)) &&
 569          lengths.empty();
 570 }
 571
 572 namespace {
 573 /// Structure that analyses the ac-value and implied-do of
 574 /// evaluate::ArrayConstructor before they are lowered. It does not generate any
 575 /// IR. The result of this analysis pass is used to select the lowering
 576 /// strategy.
 577 struct ArrayCtorAnalysis {
 578   template <typename T>
 579   ArrayCtorAnalysis(
 580       Fortran::evaluate::FoldingContext &,
 581       const Fortran::evaluate::ArrayConstructor<T> &arrayCtorExpr);
 582
 583   // Can the array constructor easily be rewritten into an hlfir.elemental ?
 584   bool isSingleImpliedDoWithOneScalarPureExpr() const {
 585     return !anyArrayExpr && isPerfectLoopNest &&
 586            innerNumberOfExprIfPrefectNest == 1 && depthIfPerfectLoopNest == 1 &&
 587            innerExprIsPureIfPerfectNest;
 588   }
 589
 590   bool anyImpliedDo = false;
 591   bool anyArrayExpr = false;
 592   bool isPerfectLoopNest = true;
 593   bool innerExprIsPureIfPerfectNest = false;
 594   std::int64_t innerNumberOfExprIfPrefectNest = 0;
 595   std::int64_t depthIfPerfectLoopNest = 0;
 596 };
 597 } // namespace
 598
 599 template <typename T>
 600 ArrayCtorAnalysis::ArrayCtorAnalysis(
 601     Fortran::evaluate::FoldingContext &foldingContext,
 602     const Fortran::evaluate::ArrayConstructor<T> &arrayCtorExpr) {
 603   llvm::SmallVector<const Fortran::evaluate::ArrayConstructorValues<T> *>
 604       arrayValueListStack{&arrayCtorExpr};
 605   // Loop through the ac-value-list(s) of the array constructor.
 606   while (!arrayValueListStack.empty()) {
 607     std::int64_t localNumberOfImpliedDo = 0;
 608     std::int64_t localNumberOfExpr = 0;
 609     // Loop though the ac-value of an ac-value list, and add any nested
 610     // ac-value-list of ac-implied-do to the stack.
 611     const Fortran::evaluate::ArrayConstructorValues<T> *currentArrayValueList =
 612         arrayValueListStack.pop_back_val();
 613     for (const Fortran::evaluate::ArrayConstructorValue<T> &acValue :
 614          *currentArrayValueList)
 615       Fortran::common::visit(
 616           Fortran::common::visitors{
 617               [&](const Fortran::evaluate::ImpliedDo<T> &impledDo) {
 618                 arrayValueListStack.push_back(&impledDo.values());
 619                 localNumberOfImpliedDo++;
 620               },
 621               [&](const Fortran::evaluate::Expr<T> &expr) {
 622                 localNumberOfExpr++;
 623                 anyArrayExpr = anyArrayExpr || expr.Rank() > 0;
 624               }},
 625           acValue.u);
 626     anyImpliedDo = anyImpliedDo || localNumberOfImpliedDo > 0;
 627
 628     if (localNumberOfImpliedDo == 0) {
 629       // Leaf ac-value-list in the array constructor ac-value tree.
 630       if (isPerfectLoopNest) {
 631         // This this the only leaf of the array-constructor (the array
 632         // constructor is a nest of single implied-do with a list of expression
 633         // in the last deeper implied do). e.g: "[((i+j, i=1,n)j=1,m)]".
 634         innerNumberOfExprIfPrefectNest = localNumberOfExpr;
 635         if (localNumberOfExpr == 1)
 636           innerExprIsPureIfPerfectNest = !Fortran::evaluate::FindImpureCall(
 637               foldingContext, toEvExpr(std::get<Fortran::evaluate::Expr<T>>(
 638                                   currentArrayValueList->begin()->u)));
 639       }
 640     } else if (localNumberOfImpliedDo == 1 && localNumberOfExpr == 0) {
 641       // Perfect implied-do nest new level.
 642       ++depthIfPerfectLoopNest;
 643     } else {
 644       // More than one implied-do, or at least one implied-do and an expr
 645       // at that level. This will not form a perfect nest. Examples:
 646       // "[a, (i, i=1,n)]" or "[(i, i=1,n), (j, j=1,m)]".
 647       isPerfectLoopNest = false;
 648     }
 649   }
 650 }
 651
 652 /// Does \p expr contain no calls to user function?
 653 static bool isCallFreeExpr(const Fortran::evaluate::ExtentExpr &expr) {
 654   for (const Fortran::semantics::Symbol &symbol :
 655        Fortran::evaluate::CollectSymbols(expr))
 656     if (Fortran::semantics::IsProcedure(symbol))
 657       return false;
 658   return true;
 659 }
 660
 661 /// Core function that pre-lowers the extent and length parameters of
 662 /// array constructors if it can, runs the ac-value analysis and
 663 /// select the lowering strategy accordingly.
 664 template <typename T>
 665 static ArrayCtorLoweringStrategy selectArrayCtorLoweringStrategy(
 666     mlir::Location loc, Fortran::lower::AbstractConverter &converter,
 667     const Fortran::evaluate::ArrayConstructor<T> &arrayCtorExpr,
 668     Fortran::lower::SymMap &symMap, Fortran::lower::StatementContext &stmtCtx) {
 669   fir::FirOpBuilder &builder = converter.getFirOpBuilder();
 670   mlir::Type idxType = builder.getIndexType();
 671   // Try to gather the array constructor extent.
 672   mlir::Value extent;
 673   fir::SequenceType::Extent typeExtent = fir::SequenceType::getUnknownExtent();
 674   auto shapeExpr = Fortran::evaluate::GetContextFreeShape(
 675       converter.getFoldingContext(), arrayCtorExpr);
 676   if (shapeExpr && shapeExpr->size() == 1 && (*shapeExpr)[0]) {
 677     const Fortran::evaluate::ExtentExpr &extentExpr = *(*shapeExpr)[0];
 678     if (auto constantExtent = Fortran::evaluate::ToInt64(extentExpr)) {
 679       typeExtent = *constantExtent;
 680       extent = builder.createIntegerConstant(loc, idxType, typeExtent);
 681     } else if (isCallFreeExpr(extentExpr)) {
 682       // The expression built by expression analysis for the array constructor
 683       // extent does not contain procedure symbols. It is side effect free.
 684       // This could be relaxed to allow pure procedure, but some care must
 685       // be taken to not bring in "unmapped" symbols from callee scopes.
 686       extent = lowerExtentExpr(loc, converter, symMap, stmtCtx, extentExpr);
 687     }
 688     // Otherwise, the temporary will have to be built step by step with
 689     // reallocation and the extent will only be known at the end of the array
 690     // constructor evaluation.
 691   }
 692   // Convert the array constructor type and try to gather its length parameter
 693   // values, if any.
 694   mlir::SmallVector<mlir::Value> lengths;
 695   mlir::Type elementType = LengthAndTypeCollector<T>::collect(
 696       loc, converter, arrayCtorExpr, symMap, stmtCtx, lengths);
 697   // Run an analysis of the array constructor ac-value.
 698   ArrayCtorAnalysis analysis(converter.getFoldingContext(), arrayCtorExpr);
 699   bool needToEvaluateOneExprToGetLengthParameters =
 700       missingLengthParameters(elementType, lengths);
 701   auto declaredType = fir::SequenceType::get({typeExtent}, elementType);
 702
 703   // Based on what was gathered and the result of the analysis, select and
 704   // instantiate the right lowering strategy for the array constructor.
 705   if (!extent || needToEvaluateOneExprToGetLengthParameters ||
 706       analysis.anyArrayExpr ||
 707       mlir::isa<fir::RecordType>(declaredType.getEleTy()))
 708     return RuntimeTempStrategy(
 709         loc, builder, stmtCtx, symMap, declaredType,
 710         extent ? std::optional<mlir::Value>(extent) : std::nullopt, lengths,
 711         needToEvaluateOneExprToGetLengthParameters);
 712   // Note: the generated hlfir.elemental is always unordered, thus,
 713   // AsElementalStrategy can only be used for array constructors without
 714   // impure ac-value expressions. If/when this changes, make sure
 715   // the 'unordered' attribute is set accordingly for the hlfir.elemental.
 716   if (analysis.isSingleImpliedDoWithOneScalarPureExpr())
 717     return AsElementalStrategy(loc, builder, stmtCtx, symMap, declaredType,
 718                                extent, lengths);
 719
 720   if (analysis.anyImpliedDo)
 721     return InlinedTempStrategy(loc, builder, stmtCtx, symMap, declaredType,
 722                                extent, lengths);
 723
 724   return LooplessInlinedTempStrategy(loc, builder, stmtCtx, symMap,
 725                                      declaredType, extent, lengths);
 726 }
 727
 728 /// Lower an ac-value expression \p expr and forward it to the selected
 729 /// lowering strategy \p arrayBuilder,
 730 template <typename T>
 731 static void genAcValue(mlir::Location loc,
 732                        Fortran::lower::AbstractConverter &converter,
 733                        const Fortran::evaluate::Expr<T> &expr,
 734                        Fortran::lower::SymMap &symMap,
 735                        Fortran::lower::StatementContext &stmtCtx,
 736                        ArrayCtorLoweringStrategy &arrayBuilder) {
 737   // TODO: get rid of the toEvExpr indirection.
 738   fir::FirOpBuilder &builder = converter.getFirOpBuilder();
 739   hlfir::Entity value = Fortran::lower::convertExprToHLFIR(
 740       loc, converter, toEvExpr(expr), symMap, stmtCtx);
 741   value = hlfir::loadTrivialScalar(loc, builder, value);
 742   arrayBuilder.pushValue(loc, builder, value);
 743 }
 744
 745 /// Lowers an ac-value implied-do \p impledDo according to the selected
 746 /// lowering strategy \p arrayBuilder.
 747 template <typename T>
 748 static void genAcValue(mlir::Location loc,
 749                        Fortran::lower::AbstractConverter &converter,
 750                        const Fortran::evaluate::ImpliedDo<T> &impledDo,
 751                        Fortran::lower::SymMap &symMap,
 752                        Fortran::lower::StatementContext &stmtCtx,
 753                        ArrayCtorLoweringStrategy &arrayBuilder) {
 754   auto lowerIndex =
 755       [&](const Fortran::evaluate::ExtentExpr expr) -> mlir::Value {
 756     return lowerExtentExpr(loc, converter, symMap, stmtCtx, expr);
 757   };
 758   mlir::Value lower = lowerIndex(impledDo.lower());
 759   mlir::Value upper = lowerIndex(impledDo.upper());
 760   mlir::Value stride = lowerIndex(impledDo.stride());
 761   fir::FirOpBuilder &builder = converter.getFirOpBuilder();
 762   mlir::OpBuilder::InsertPoint insertPt = builder.saveInsertionPoint();
 763   mlir::Value impliedDoIndexValue =
 764       arrayBuilder.startImpliedDo(loc, builder, lower, upper, stride);
 765   arrayBuilder.startImpliedDoScope(toStringRef(impledDo.name()),
 766                                    impliedDoIndexValue);
 767
 768   for (const auto &acValue : impledDo.values())
 769     Fortran::common::visit(
 770         [&](const auto &x) {
 771           genAcValue(loc, converter, x, symMap, stmtCtx, arrayBuilder);
 772         },
 773         acValue.u);
 774
 775   arrayBuilder.endImpliedDoScope();
 776   builder.restoreInsertionPoint(insertPt);
 777 }
 778
 779 /// Entry point for evaluate::ArrayConstructor lowering.
 780 template <typename T>
 781 hlfir::EntityWithAttributes Fortran::lower::ArrayConstructorBuilder<T>::gen(
 782     mlir::Location loc, Fortran::lower::AbstractConverter &converter,
 783     const Fortran::evaluate::ArrayConstructor<T> &arrayCtorExpr,
 784     Fortran::lower::SymMap &symMap, Fortran::lower::StatementContext &stmtCtx) {
 785   fir::FirOpBuilder &builder = converter.getFirOpBuilder();
 786   // Select the lowering strategy given the array constructor.
 787   auto arrayBuilder = selectArrayCtorLoweringStrategy(
 788       loc, converter, arrayCtorExpr, symMap, stmtCtx);
 789   // Run the array lowering strategy through the ac-values.
 790   for (const auto &acValue : arrayCtorExpr)
 791     Fortran::common::visit(
 792         [&](const auto &x) {
 793           genAcValue(loc, converter, x, symMap, stmtCtx, arrayBuilder);
 794         },
 795         acValue.u);
 796   hlfir::Entity hlfirExpr = arrayBuilder.finishArrayCtorLowering(loc, builder);
 797   // Insert the clean-up for the created hlfir.expr.
 798   fir::FirOpBuilder *bldr = &builder;
 799   stmtCtx.attachCleanup(
 800       [=]() { bldr->create<hlfir::DestroyOp>(loc, hlfirExpr); });
 801   return hlfir::EntityWithAttributes{hlfirExpr};
 802 }
 803
 804 using namespace Fortran::evaluate;
 805 using namespace Fortran::common;
 806 FOR_EACH_SPECIFIC_TYPE(template class Fortran::lower::ArrayConstructorBuilder, )