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}, exprType{getExprType(declaredType)} {}
 198
 199   static hlfir::ExprType getExprType(fir::SequenceType declaredType) {
 200     // Note: 7.8 point 4: the dynamic type of an array constructor is its static
 201     // type, it is not polymorphic.
 202     return hlfir::ExprType::get(declaredType.getContext(),
 203                                 declaredType.getShape(),
 204                                 declaredType.getEleTy(),
 205                                 /*isPolymorphic=*/false);
 206   }
 207
 208   /// Create the hlfir.elemental and compute the ac-implied-do-index value
 209   /// given the lower bound and stride (compute "%i" in the illustration above).
 210   mlir::Value startImpliedDo(mlir::Location loc, fir::FirOpBuilder &builder,
 211                              mlir::Value lower, mlir::Value upper,
 212                              mlir::Value stride) {
 213     assert(!elementalOp && "expected only one implied-do");
 214     mlir::Value one =
 215         builder.createIntegerConstant(loc, builder.getIndexType(), 1);
 216     elementalOp = builder.create<hlfir::ElementalOp>(
 217         loc, exprType, shape,
 218         /*mold=*/nullptr, lengthParams, /*isUnordered=*/true);
 219     builder.setInsertionPointToStart(elementalOp.getBody());
 220     // implied-do-index = lower+((i-1)*stride)
 221     mlir::Value diff = builder.create<mlir::arith::SubIOp>(
 222         loc, elementalOp.getIndices()[0], one);
 223     mlir::Value mul = builder.create<mlir::arith::MulIOp>(loc, diff, stride);
 224     mlir::Value add = builder.create<mlir::arith::AddIOp>(loc, lower, mul);
 225     return add;
 226   }
 227
 228   /// Create the elemental hlfir.yield_element with the scalar ac-value.
 229   void pushValue(mlir::Location loc, fir::FirOpBuilder &builder,
 230                  hlfir::Entity value) {
 231     assert(value.isScalar() && "cannot use hlfir.elemental with array values");
 232     assert(elementalOp && "array constructor must contain an outer implied-do");
 233     mlir::Value elementResult = value;
 234     if (fir::isa_trivial(elementResult.getType()))
 235       elementResult =
 236           builder.createConvert(loc, exprType.getElementType(), elementResult);
 237
 238     // The clean-ups associated with the implied-do body operations
 239     // must be initiated before the YieldElementOp, so we have to pop the scope
 240     // right now.
 241     stmtCtx.finalizeAndPop();
 242
 243     // This is a hacky way to get rid of the DestroyOp clean-up
 244     // associated with the final ac-value result if it is hlfir.expr.
 245     // Example:
 246     //   ... = (/(REPEAT(REPEAT(CHAR(i),2),2),i=1,n)/)
 247     // Each intrinsic call lowering will produce hlfir.expr result
 248     // with the associated clean-up, but only the last of them
 249     // is wrong. It is wrong because the value is used in hlfir.yield_element,
 250     // so it cannot be destroyed.
 251     mlir::Operation *destroyOp = nullptr;
 252     for (mlir::Operation *useOp : elementResult.getUsers())
 253       if (mlir::isa<hlfir::DestroyOp>(useOp)) {
 254         if (destroyOp)
 255           fir::emitFatalError(loc,
 256                               "multiple DestroyOp's for ac-value expression");
 257         destroyOp = useOp;
 258       }
 259
 260     if (destroyOp)
 261       destroyOp->erase();
 262
 263     builder.create<hlfir::YieldElementOp>(loc, elementResult);
 264   }
 265
 266   // Override the default, because the context scope must be popped in
 267   // pushValue().
 268   virtual void endImpliedDoScope() override { symMap.popImpliedDoBinding(); }
 269
 270   /// Return the created hlfir.elemental.
 271   hlfir::Entity finishArrayCtorLowering(mlir::Location loc,
 272                                         fir::FirOpBuilder &builder) {
 273     return hlfir::Entity{elementalOp};
 274   }
 275
 276 private:
 277   mlir::Value shape;
 278   llvm::SmallVector<mlir::Value> lengthParams;
 279   hlfir::ExprType exprType;
 280   hlfir::ElementalOp elementalOp{};
 281 };
 282
 283 /// Class that implements the "runtime temp strategy" to lower array
 284 /// constructors.
 285 class RuntimeTempStrategy : public StrategyBase {
 286   /// Name that will be given to the temporary allocation and hlfir.declare in
 287   /// the IR.
 288   static constexpr char tempName[] = ".tmp.arrayctor";
 289
 290 public:
 291   /// Start lowering an array constructor according to the runtime strategy.
 292   /// The temporary is only created if the extents and length parameters are
 293   /// already known. Otherwise, the handling of the allocation (and
 294   /// reallocation) is left up to the runtime.
 295   /// \p extent is the pre-computed extent of the array constructor, if it could
 296   /// be pre-computed. It is std::nullopt otherwise.
 297   /// \p lengths are the pre-computed length parameters of the array
 298   /// constructor, if they could be precomputed. \p missingLengthParameters is
 299   /// set to true if the length parameters could not be precomputed.
 300   RuntimeTempStrategy(mlir::Location loc, fir::FirOpBuilder &builder,
 301                       Fortran::lower::StatementContext &stmtCtx,
 302                       Fortran::lower::SymMap &symMap,
 303                       fir::SequenceType declaredType,
 304                       std::optional<mlir::Value> extent,
 305                       llvm::ArrayRef<mlir::Value> lengths,
 306                       bool missingLengthParameters)
 307       : StrategyBase{stmtCtx, symMap},
 308         arrayConstructorElementType{declaredType.getEleTy()} {
 309     mlir::Type heapType = fir::HeapType::get(declaredType);
 310     mlir::Type boxType = fir::BoxType::get(heapType);
 311     allocatableTemp = builder.createTemporary(loc, boxType, tempName);
 312     mlir::Value initialBoxValue;
 313     if (extent && !missingLengthParameters) {
 314       llvm::SmallVector<mlir::Value, 1> extents{*extent};
 315       mlir::Value tempStorage = builder.createHeapTemporary(
 316           loc, declaredType, tempName, extents, lengths);
 317       mlir::Value shape = builder.genShape(loc, extents);
 318       declare = builder.create<hlfir::DeclareOp>(
 319           loc, tempStorage, tempName, shape, lengths,
 320           /*dummy_scope=*/nullptr, fir::FortranVariableFlagsAttr{});
 321       initialBoxValue =
 322           builder.createBox(loc, boxType, declare->getOriginalBase(), shape,
 323                             /*slice=*/mlir::Value{}, lengths, /*tdesc=*/{});
 324     } else {
 325       // The runtime will have to do the initial allocation.
 326       // The declare operation cannot be emitted in this case since the final
 327       // array constructor has not yet been allocated. Instead, the resulting
 328       // temporary variable will be extracted from the allocatable descriptor
 329       // after all the API calls.
 330       // Prepare the initial state of the allocatable descriptor with a
 331       // deallocated status and all the available knowledge about the extent
 332       // and length parameters.
 333       llvm::SmallVector<mlir::Value> emboxLengths(lengths);
 334       if (!extent)
 335         extent = builder.createIntegerConstant(loc, builder.getIndexType(), 0);
 336       if (missingLengthParameters) {
 337         if (mlir::isa<fir::CharacterType>(declaredType.getEleTy()))
 338           emboxLengths.push_back(builder.createIntegerConstant(
 339               loc, builder.getCharacterLengthType(), 0));
 340         else
 341           TODO(loc,
 342                "parametrized derived type array constructor without type-spec");
 343       }
 344       mlir::Value nullAddr = builder.createNullConstant(loc, heapType);
 345       mlir::Value shape = builder.genShape(loc, {*extent});
 346       initialBoxValue = builder.createBox(loc, boxType, nullAddr, shape,
 347                                           /*slice=*/mlir::Value{}, emboxLengths,
 348                                           /*tdesc=*/{});
 349     }
 350     builder.create<fir::StoreOp>(loc, initialBoxValue, allocatableTemp);
 351     arrayConstructorVector = fir::runtime::genInitArrayConstructorVector(
 352         loc, builder, allocatableTemp,
 353         builder.createBool(loc, missingLengthParameters));
 354   }
 355
 356   bool useSimplePushRuntime(hlfir::Entity value) {
 357     return value.isScalar() &&
 358            !mlir::isa<fir::CharacterType>(arrayConstructorElementType) &&
 359            !fir::isRecordWithAllocatableMember(arrayConstructorElementType) &&
 360            !fir::isRecordWithTypeParameters(arrayConstructorElementType);
 361   }
 362
 363   /// Push a lowered ac-value into the array constructor vector using
 364   /// the runtime API.
 365   void pushValue(mlir::Location loc, fir::FirOpBuilder &builder,
 366                  hlfir::Entity value) {
 367     if (useSimplePushRuntime(value)) {
 368       auto [addrExv, cleanUp] = hlfir::convertToAddress(
 369           loc, builder, value, arrayConstructorElementType);
 370       mlir::Value addr = fir::getBase(addrExv);
 371       if (mlir::isa<fir::BaseBoxType>(addr.getType()))
 372         addr = builder.create<fir::BoxAddrOp>(loc, addr);
 373       fir::runtime::genPushArrayConstructorSimpleScalar(
 374           loc, builder, arrayConstructorVector, addr);
 375       if (cleanUp)
 376         (*cleanUp)();
 377       return;
 378     }
 379     auto [boxExv, cleanUp] =
 380         hlfir::convertToBox(loc, builder, value, arrayConstructorElementType);
 381     fir::runtime::genPushArrayConstructorValue(
 382         loc, builder, arrayConstructorVector, fir::getBase(boxExv));
 383     if (cleanUp)
 384       (*cleanUp)();
 385   }
 386
 387   /// Start a fir.do_loop with the control from an implied-do and return
 388   /// the loop induction variable that is the ac-do-variable value.
 389   mlir::Value startImpliedDo(mlir::Location loc, fir::FirOpBuilder &builder,
 390                              mlir::Value lower, mlir::Value upper,
 391                              mlir::Value stride) {
 392     auto loop = builder.create<fir::DoLoopOp>(loc, lower, upper, stride,
 393                                               /*unordered=*/false,
 394                                               /*finalCount=*/false);
 395     builder.setInsertionPointToStart(loop.getBody());
 396     return loop.getInductionVar();
 397   }
 398
 399   /// Move the temporary to an hlfir.expr value (array constructors are not
 400   /// variables and cannot be further modified).
 401   hlfir::Entity finishArrayCtorLowering(mlir::Location loc,
 402                                         fir::FirOpBuilder &builder) {
 403     // Temp is created using createHeapTemporary, or allocated on the heap
 404     // by the runtime.
 405     mlir::Value mustFree = builder.createBool(loc, true);
 406     mlir::Value temp;
 407     if (declare)
 408       temp = declare->getBase();
 409     else
 410       temp = hlfir::derefPointersAndAllocatables(
 411           loc, builder, hlfir::Entity{allocatableTemp});
 412     auto hlfirExpr = builder.create<hlfir::AsExprOp>(loc, temp, mustFree);
 413     return hlfir::Entity{hlfirExpr};
 414   }
 415
 416 private:
 417   /// Element type of the array constructor being built.
 418   mlir::Type arrayConstructorElementType;
 419   /// Allocatable descriptor for the storage of the array constructor being
 420   /// built.
 421   mlir::Value allocatableTemp;
 422   /// Structure that allows the runtime API to maintain the status of
 423   /// of the array constructor being built between two API calls.
 424   mlir::Value arrayConstructorVector;
 425   /// DeclareOp for the array constructor storage, if it was possible to
 426   /// allocate it before any API calls.
 427   std::optional<hlfir::DeclareOp> declare;
 428 };
 429
 430 /// Wrapper class that dispatch to the selected array constructor lowering
 431 /// strategy and does nothing else.
 432 class ArrayCtorLoweringStrategy {
 433 public:
 434   template <typename A>
 435   ArrayCtorLoweringStrategy(A &&impl) : implVariant{std::forward<A>(impl)} {}
 436
 437   void pushValue(mlir::Location loc, fir::FirOpBuilder &builder,
 438                  hlfir::Entity value) {
 439     return Fortran::common::visit(
 440         [&](auto &impl) { return impl.pushValue(loc, builder, value); },
 441         implVariant);
 442   }
 443
 444   mlir::Value startImpliedDo(mlir::Location loc, fir::FirOpBuilder &builder,
 445                              mlir::Value lower, mlir::Value upper,
 446                              mlir::Value stride) {
 447     return Fortran::common::visit(
 448         [&](auto &impl) {
 449           return impl.startImpliedDo(loc, builder, lower, upper, stride);
 450         },
 451         implVariant);
 452   }
 453
 454   hlfir::Entity finishArrayCtorLowering(mlir::Location loc,
 455                                         fir::FirOpBuilder &builder) {
 456     return Fortran::common::visit(
 457         [&](auto &impl) { return impl.finishArrayCtorLowering(loc, builder); },
 458         implVariant);
 459   }
 460
 461   void startImpliedDoScope(llvm::StringRef doName, mlir::Value indexValue) {
 462     Fortran::common::visit(
 463         [&](auto &impl) {
 464           return impl.startImpliedDoScope(doName, indexValue);
 465         },
 466         implVariant);
 467   }
 468
 469   void endImpliedDoScope() {
 470     Fortran::common::visit([&](auto &impl) { return impl.endImpliedDoScope(); },
 471                            implVariant);
 472   }
 473
 474 private:
 475   std::variant<InlinedTempStrategy, LooplessInlinedTempStrategy,
 476                AsElementalStrategy, RuntimeTempStrategy>
 477       implVariant;
 478 };
 479 } // namespace
 480
 481 //===----------------------------------------------------------------------===//
 482 //   Definition of selectArrayCtorLoweringStrategy and its helpers.
 483 //   This is the code that analyses the evaluate::ArrayConstructor<T>,
 484 //   pre-lowers the array constructor extent and length parameters if it can,
 485 //   and chooses the lowering strategy.
 486 //===----------------------------------------------------------------------===//
 487
 488 /// Helper to lower a scalar extent expression (like implied-do bounds).
 489 static mlir::Value lowerExtentExpr(mlir::Location loc,
 490                                    Fortran::lower::AbstractConverter &converter,
 491                                    Fortran::lower::SymMap &symMap,
 492                                    Fortran::lower::StatementContext &stmtCtx,
 493                                    const Fortran::evaluate::ExtentExpr &expr) {
 494   fir::FirOpBuilder &builder = converter.getFirOpBuilder();
 495   mlir::IndexType idxTy = builder.getIndexType();
 496   hlfir::Entity value = Fortran::lower::convertExprToHLFIR(
 497       loc, converter, toEvExpr(expr), symMap, stmtCtx);
 498   value = hlfir::loadTrivialScalar(loc, builder, value);
 499   return builder.createConvert(loc, idxTy, value);
 500 }
 501
 502 namespace {
 503 /// Helper class to lower the array constructor type and its length parameters.
 504 /// The length parameters, if any, are only lowered if this does not require
 505 /// evaluating an ac-value.
 506 template <typename T>
 507 struct LengthAndTypeCollector {
 508   static mlir::Type collect(mlir::Location,
 509                             Fortran::lower::AbstractConverter &converter,
 510                             const Fortran::evaluate::ArrayConstructor<T> &,
 511                             Fortran::lower::SymMap &,
 512                             Fortran::lower::StatementContext &,
 513                             mlir::SmallVectorImpl<mlir::Value> &) {
 514     // Numerical and Logical types.
 515     return Fortran::lower::getFIRType(&converter.getMLIRContext(), T::category,
 516                                       T::kind, /*lenParams*/ {});
 517   }
 518 };
 519
 520 template <>
 521 struct LengthAndTypeCollector<Fortran::evaluate::SomeDerived> {
 522   static mlir::Type collect(
 523       mlir::Location loc, Fortran::lower::AbstractConverter &converter,
 524       const Fortran::evaluate::ArrayConstructor<Fortran::evaluate::SomeDerived>
 525           &arrayCtorExpr,
 526       Fortran::lower::SymMap &symMap, Fortran::lower::StatementContext &stmtCtx,
 527       mlir::SmallVectorImpl<mlir::Value> &lengths) {
 528     // Array constructors cannot be unlimited polymorphic (C7113), so there must
 529     // be a derived type spec available.
 530     return Fortran::lower::translateDerivedTypeToFIRType(
 531         converter, arrayCtorExpr.result().derivedTypeSpec());
 532   }
 533 };
 534
 535 template <int Kind>
 536 using Character =
 537     Fortran::evaluate::Type<Fortran::common::TypeCategory::Character, Kind>;
 538 template <int Kind>
 539 struct LengthAndTypeCollector<Character<Kind>> {
 540   static mlir::Type collect(
 541       mlir::Location loc, Fortran::lower::AbstractConverter &converter,
 542       const Fortran::evaluate::ArrayConstructor<Character<Kind>> &arrayCtorExpr,
 543       Fortran::lower::SymMap &symMap, Fortran::lower::StatementContext &stmtCtx,
 544       mlir::SmallVectorImpl<mlir::Value> &lengths) {
 545     llvm::SmallVector<Fortran::lower::LenParameterTy> typeLengths;
 546     if (const Fortran::evaluate::ExtentExpr *lenExpr = arrayCtorExpr.LEN()) {
 547       lengths.push_back(
 548           lowerExtentExpr(loc, converter, symMap, stmtCtx, *lenExpr));
 549       if (std::optional<std::int64_t> cstLen =
 550               Fortran::evaluate::ToInt64(*lenExpr))
 551         typeLengths.push_back(*cstLen);
 552     }
 553     return Fortran::lower::getFIRType(&converter.getMLIRContext(),
 554                                       Fortran::common::TypeCategory::Character,
 555                                       Kind, typeLengths);
 556   }
 557 };
 558 } // namespace
 559
 560 /// Does the array constructor have length parameters that
 561 /// LengthAndTypeCollector::collect could not lower because this requires
 562 /// lowering an ac-value and must be delayed?
 563 static bool missingLengthParameters(mlir::Type elementType,
 564                                     llvm::ArrayRef<mlir::Value> lengths) {
 565   return (mlir::isa<fir::CharacterType>(elementType) ||
 566           fir::isRecordWithTypeParameters(elementType)) &&
 567          lengths.empty();
 568 }
 569
 570 namespace {
 571 /// Structure that analyses the ac-value and implied-do of
 572 /// evaluate::ArrayConstructor before they are lowered. It does not generate any
 573 /// IR. The result of this analysis pass is used to select the lowering
 574 /// strategy.
 575 struct ArrayCtorAnalysis {
 576   template <typename T>
 577   ArrayCtorAnalysis(
 578       Fortran::evaluate::FoldingContext &,
 579       const Fortran::evaluate::ArrayConstructor<T> &arrayCtorExpr);
 580
 581   // Can the array constructor easily be rewritten into an hlfir.elemental ?
 582   bool isSingleImpliedDoWithOneScalarPureExpr() const {
 583     return !anyArrayExpr && isPerfectLoopNest &&
 584            innerNumberOfExprIfPrefectNest == 1 && depthIfPerfectLoopNest == 1 &&
 585            innerExprIsPureIfPerfectNest;
 586   }
 587
 588   bool anyImpliedDo = false;
 589   bool anyArrayExpr = false;
 590   bool isPerfectLoopNest = true;
 591   bool innerExprIsPureIfPerfectNest = false;
 592   std::int64_t innerNumberOfExprIfPrefectNest = 0;
 593   std::int64_t depthIfPerfectLoopNest = 0;
 594 };
 595 } // namespace
 596
 597 template <typename T>
 598 ArrayCtorAnalysis::ArrayCtorAnalysis(
 599     Fortran::evaluate::FoldingContext &foldingContext,
 600     const Fortran::evaluate::ArrayConstructor<T> &arrayCtorExpr) {
 601   llvm::SmallVector<const Fortran::evaluate::ArrayConstructorValues<T> *>
 602       arrayValueListStack{&arrayCtorExpr};
 603   // Loop through the ac-value-list(s) of the array constructor.
 604   while (!arrayValueListStack.empty()) {
 605     std::int64_t localNumberOfImpliedDo = 0;
 606     std::int64_t localNumberOfExpr = 0;
 607     // Loop though the ac-value of an ac-value list, and add any nested
 608     // ac-value-list of ac-implied-do to the stack.
 609     const Fortran::evaluate::ArrayConstructorValues<T> *currentArrayValueList =
 610         arrayValueListStack.pop_back_val();
 611     for (const Fortran::evaluate::ArrayConstructorValue<T> &acValue :
 612          *currentArrayValueList)
 613       Fortran::common::visit(
 614           Fortran::common::visitors{
 615               [&](const Fortran::evaluate::ImpliedDo<T> &impledDo) {
 616                 arrayValueListStack.push_back(&impledDo.values());
 617                 localNumberOfImpliedDo++;
 618               },
 619               [&](const Fortran::evaluate::Expr<T> &expr) {
 620                 localNumberOfExpr++;
 621                 anyArrayExpr = anyArrayExpr || expr.Rank() > 0;
 622               }},
 623           acValue.u);
 624     anyImpliedDo = anyImpliedDo || localNumberOfImpliedDo > 0;
 625
 626     if (localNumberOfImpliedDo == 0) {
 627       // Leaf ac-value-list in the array constructor ac-value tree.
 628       if (isPerfectLoopNest) {
 629         // This this the only leaf of the array-constructor (the array
 630         // constructor is a nest of single implied-do with a list of expression
 631         // in the last deeper implied do). e.g: "[((i+j, i=1,n)j=1,m)]".
 632         innerNumberOfExprIfPrefectNest = localNumberOfExpr;
 633         if (localNumberOfExpr == 1)
 634           innerExprIsPureIfPerfectNest = !Fortran::evaluate::FindImpureCall(
 635               foldingContext, toEvExpr(std::get<Fortran::evaluate::Expr<T>>(
 636                                   currentArrayValueList->begin()->u)));
 637       }
 638     } else if (localNumberOfImpliedDo == 1 && localNumberOfExpr == 0) {
 639       // Perfect implied-do nest new level.
 640       ++depthIfPerfectLoopNest;
 641     } else {
 642       // More than one implied-do, or at least one implied-do and an expr
 643       // at that level. This will not form a perfect nest. Examples:
 644       // "[a, (i, i=1,n)]" or "[(i, i=1,n), (j, j=1,m)]".
 645       isPerfectLoopNest = false;
 646     }
 647   }
 648 }
 649
 650 /// Does \p expr contain no calls to user function?
 651 static bool isCallFreeExpr(const Fortran::evaluate::ExtentExpr &expr) {
 652   for (const Fortran::semantics::Symbol &symbol :
 653        Fortran::evaluate::CollectSymbols(expr))
 654     if (Fortran::semantics::IsProcedure(symbol))
 655       return false;
 656   return true;
 657 }
 658
 659 /// Core function that pre-lowers the extent and length parameters of
 660 /// array constructors if it can, runs the ac-value analysis and
 661 /// select the lowering strategy accordingly.
 662 template <typename T>
 663 static ArrayCtorLoweringStrategy selectArrayCtorLoweringStrategy(
 664     mlir::Location loc, Fortran::lower::AbstractConverter &converter,
 665     const Fortran::evaluate::ArrayConstructor<T> &arrayCtorExpr,
 666     Fortran::lower::SymMap &symMap, Fortran::lower::StatementContext &stmtCtx) {
 667   fir::FirOpBuilder &builder = converter.getFirOpBuilder();
 668   mlir::Type idxType = builder.getIndexType();
 669   // Try to gather the array constructor extent.
 670   mlir::Value extent;
 671   fir::SequenceType::Extent typeExtent = fir::SequenceType::getUnknownExtent();
 672   auto shapeExpr = Fortran::evaluate::GetContextFreeShape(
 673       converter.getFoldingContext(), arrayCtorExpr);
 674   if (shapeExpr && shapeExpr->size() == 1 && (*shapeExpr)[0]) {
 675     const Fortran::evaluate::ExtentExpr &extentExpr = *(*shapeExpr)[0];
 676     if (auto constantExtent = Fortran::evaluate::ToInt64(extentExpr)) {
 677       typeExtent = *constantExtent;
 678       extent = builder.createIntegerConstant(loc, idxType, typeExtent);
 679     } else if (isCallFreeExpr(extentExpr)) {
 680       // The expression built by expression analysis for the array constructor
 681       // extent does not contain procedure symbols. It is side effect free.
 682       // This could be relaxed to allow pure procedure, but some care must
 683       // be taken to not bring in "unmapped" symbols from callee scopes.
 684       extent = lowerExtentExpr(loc, converter, symMap, stmtCtx, extentExpr);
 685     }
 686     // Otherwise, the temporary will have to be built step by step with
 687     // reallocation and the extent will only be known at the end of the array
 688     // constructor evaluation.
 689   }
 690   // Convert the array constructor type and try to gather its length parameter
 691   // values, if any.
 692   mlir::SmallVector<mlir::Value> lengths;
 693   mlir::Type elementType = LengthAndTypeCollector<T>::collect(
 694       loc, converter, arrayCtorExpr, symMap, stmtCtx, lengths);
 695   // Run an analysis of the array constructor ac-value.
 696   ArrayCtorAnalysis analysis(converter.getFoldingContext(), arrayCtorExpr);
 697   bool needToEvaluateOneExprToGetLengthParameters =
 698       missingLengthParameters(elementType, lengths);
 699   auto declaredType = fir::SequenceType::get({typeExtent}, elementType);
 700
 701   // Based on what was gathered and the result of the analysis, select and
 702   // instantiate the right lowering strategy for the array constructor.
 703   if (!extent || needToEvaluateOneExprToGetLengthParameters ||
 704       analysis.anyArrayExpr ||
 705       mlir::isa<fir::RecordType>(declaredType.getEleTy()))
 706     return RuntimeTempStrategy(
 707         loc, builder, stmtCtx, symMap, declaredType,
 708         extent ? std::optional<mlir::Value>(extent) : std::nullopt, lengths,
 709         needToEvaluateOneExprToGetLengthParameters);
 710   // Note: the generated hlfir.elemental is always unordered, thus,
 711   // AsElementalStrategy can only be used for array constructors without
 712   // impure ac-value expressions. If/when this changes, make sure
 713   // the 'unordered' attribute is set accordingly for the hlfir.elemental.
 714   if (analysis.isSingleImpliedDoWithOneScalarPureExpr())
 715     return AsElementalStrategy(loc, builder, stmtCtx, symMap, declaredType,
 716                                extent, lengths);
 717
 718   if (analysis.anyImpliedDo)
 719     return InlinedTempStrategy(loc, builder, stmtCtx, symMap, declaredType,
 720                                extent, lengths);
 721
 722   return LooplessInlinedTempStrategy(loc, builder, stmtCtx, symMap,
 723                                      declaredType, extent, lengths);
 724 }
 725
 726 /// Lower an ac-value expression \p expr and forward it to the selected
 727 /// lowering strategy \p arrayBuilder,
 728 template <typename T>
 729 static void genAcValue(mlir::Location loc,
 730                        Fortran::lower::AbstractConverter &converter,
 731                        const Fortran::evaluate::Expr<T> &expr,
 732                        Fortran::lower::SymMap &symMap,
 733                        Fortran::lower::StatementContext &stmtCtx,
 734                        ArrayCtorLoweringStrategy &arrayBuilder) {
 735   // TODO: get rid of the toEvExpr indirection.
 736   fir::FirOpBuilder &builder = converter.getFirOpBuilder();
 737   hlfir::Entity value = Fortran::lower::convertExprToHLFIR(
 738       loc, converter, toEvExpr(expr), symMap, stmtCtx);
 739   value = hlfir::loadTrivialScalar(loc, builder, value);
 740   arrayBuilder.pushValue(loc, builder, value);
 741 }
 742
 743 /// Lowers an ac-value implied-do \p impledDo according to the selected
 744 /// lowering strategy \p arrayBuilder.
 745 template <typename T>
 746 static void genAcValue(mlir::Location loc,
 747                        Fortran::lower::AbstractConverter &converter,
 748                        const Fortran::evaluate::ImpliedDo<T> &impledDo,
 749                        Fortran::lower::SymMap &symMap,
 750                        Fortran::lower::StatementContext &stmtCtx,
 751                        ArrayCtorLoweringStrategy &arrayBuilder) {
 752   auto lowerIndex =
 753       [&](const Fortran::evaluate::ExtentExpr expr) -> mlir::Value {
 754     return lowerExtentExpr(loc, converter, symMap, stmtCtx, expr);
 755   };
 756   mlir::Value lower = lowerIndex(impledDo.lower());
 757   mlir::Value upper = lowerIndex(impledDo.upper());
 758   mlir::Value stride = lowerIndex(impledDo.stride());
 759   fir::FirOpBuilder &builder = converter.getFirOpBuilder();
 760   mlir::OpBuilder::InsertPoint insertPt = builder.saveInsertionPoint();
 761   mlir::Value impliedDoIndexValue =
 762       arrayBuilder.startImpliedDo(loc, builder, lower, upper, stride);
 763   arrayBuilder.startImpliedDoScope(toStringRef(impledDo.name()),
 764                                    impliedDoIndexValue);
 765
 766   for (const auto &acValue : impledDo.values())
 767     Fortran::common::visit(
 768         [&](const auto &x) {
 769           genAcValue(loc, converter, x, symMap, stmtCtx, arrayBuilder);
 770         },
 771         acValue.u);
 772
 773   arrayBuilder.endImpliedDoScope();
 774   builder.restoreInsertionPoint(insertPt);
 775 }
 776
 777 /// Entry point for evaluate::ArrayConstructor lowering.
 778 template <typename T>
 779 hlfir::EntityWithAttributes Fortran::lower::ArrayConstructorBuilder<T>::gen(
 780     mlir::Location loc, Fortran::lower::AbstractConverter &converter,
 781     const Fortran::evaluate::ArrayConstructor<T> &arrayCtorExpr,
 782     Fortran::lower::SymMap &symMap, Fortran::lower::StatementContext &stmtCtx) {
 783   fir::FirOpBuilder &builder = converter.getFirOpBuilder();
 784   // Select the lowering strategy given the array constructor.
 785   auto arrayBuilder = selectArrayCtorLoweringStrategy(
 786       loc, converter, arrayCtorExpr, symMap, stmtCtx);
 787   // Run the array lowering strategy through the ac-values.
 788   for (const auto &acValue : arrayCtorExpr)
 789     Fortran::common::visit(
 790         [&](const auto &x) {
 791           genAcValue(loc, converter, x, symMap, stmtCtx, arrayBuilder);
 792         },
 793         acValue.u);
 794   hlfir::Entity hlfirExpr = arrayBuilder.finishArrayCtorLowering(loc, builder);
 795   // Insert the clean-up for the created hlfir.expr.
 796   fir::FirOpBuilder *bldr = &builder;
 797   stmtCtx.attachCleanup(
 798       [=]() { bldr->create<hlfir::DestroyOp>(loc, hlfirExpr); });
 799   return hlfir::EntityWithAttributes{hlfirExpr};
 800 }
 801
 802 using namespace Fortran::evaluate;
 803 using namespace Fortran::common;
 804 FOR_EACH_SPECIFIC_TYPE(template class Fortran::lower::ArrayConstructorBuilder, )