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