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
76namespace {
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.
81class StrategyBase {
82public:
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
99protected:
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.
107template <bool hasLoops>
108class 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
114public:
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.
160using 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.
165using 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.
188class AsElementalStrategy : public StrategyBase {
189public:
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
277private:
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.
286class 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
291public:
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 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 (declaredType.getEleTy().isa<fir::CharacterType>())
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 !arrayConstructorElementType.isa<fir::CharacterType>() &&
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 (addr.getType().isa<fir::BaseBoxType>())
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
418private:
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.
434class ArrayCtorLoweringStrategy {
435public:
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 std::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 std::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 std::visit(
459 [&](auto &impl) { return impl.finishArrayCtorLowering(loc, builder); },
460 implVariant);
461 }
462
463 void startImpliedDoScope(llvm::StringRef doName, mlir::Value indexValue) {
464 std::visit(
465 [&](auto &impl) {
466 return impl.startImpliedDoScope(doName, indexValue);
467 },
468 implVariant);
469 }
470
471 void endImpliedDoScope() {
472 std::visit([&](auto &impl) { return impl.endImpliedDoScope(); },
473 implVariant);
474 }
475
476private:
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).
491static 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
504namespace {
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.
508template <typename T>
509struct 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
522template <>
523struct 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
537template <int Kind>
538using Character =
539 Fortran::evaluate::Type<Fortran::common::TypeCategory::Character, Kind>;
540template <int Kind>
541struct 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?
565static bool missingLengthParameters(mlir::Type elementType,
566 llvm::ArrayRef<mlir::Value> lengths) {
567 return (elementType.isa<fir::CharacterType>() ||
568 fir::isRecordWithTypeParameters(elementType)) &&
569 lengths.empty();
570}
571
572namespace {
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.
577struct 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
599template <typename T>
600ArrayCtorAnalysis::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 std::visit(Fortran::common::visitors{
616 [&](const Fortran::evaluate::ImpliedDo<T> &impledDo) {
617 arrayValueListStack.push_back(&impledDo.values());
618 localNumberOfImpliedDo++;
619 },
620 [&](const Fortran::evaluate::Expr<T> &expr) {
621 localNumberOfExpr++;
622 anyArrayExpr = anyArrayExpr || expr.Rank() > 0;
623 }},
624 acValue.u);
625 anyImpliedDo = anyImpliedDo || localNumberOfImpliedDo > 0;
626
627 if (localNumberOfImpliedDo == 0) {
628 // Leaf ac-value-list in the array constructor ac-value tree.
629 if (isPerfectLoopNest) {
630 // This this the only leaf of the array-constructor (the array
631 // constructor is a nest of single implied-do with a list of expression
632 // in the last deeper implied do). e.g: "[((i+j, i=1,n)j=1,m)]".
633 innerNumberOfExprIfPrefectNest = localNumberOfExpr;
634 if (localNumberOfExpr == 1)
635 innerExprIsPureIfPerfectNest = !Fortran::evaluate::FindImpureCall(
636 foldingContext, toEvExpr(std::get<Fortran::evaluate::Expr<T>>(
637 currentArrayValueList->begin()->u)));
638 }
639 } else if (localNumberOfImpliedDo == 1 && localNumberOfExpr == 0) {
640 // Perfect implied-do nest new level.
641 ++depthIfPerfectLoopNest;
642 } else {
643 // More than one implied-do, or at least one implied-do and an expr
644 // at that level. This will not form a perfect nest. Examples:
645 // "[a, (i, i=1,n)]" or "[(i, i=1,n), (j, j=1,m)]".
646 isPerfectLoopNest = false;
647 }
648 }
649}
650
651/// Does \p expr contain no calls to user function?
652static bool isCallFreeExpr(const Fortran::evaluate::ExtentExpr &expr) {
653 for (const Fortran::semantics::Symbol &symbol :
654 Fortran::evaluate::CollectSymbols(expr))
655 if (Fortran::semantics::IsProcedure(symbol))
656 return false;
657 return true;
658}
659
660/// Core function that pre-lowers the extent and length parameters of
661/// array constructors if it can, runs the ac-value analysis and
662/// select the lowering strategy accordingly.
663template <typename T>
664static ArrayCtorLoweringStrategy selectArrayCtorLoweringStrategy(
665 mlir::Location loc, Fortran::lower::AbstractConverter &converter,
666 const Fortran::evaluate::ArrayConstructor<T> &arrayCtorExpr,
667 Fortran::lower::SymMap &symMap, Fortran::lower::StatementContext &stmtCtx) {
668 fir::FirOpBuilder &builder = converter.getFirOpBuilder();
669 mlir::Type idxType = builder.getIndexType();
670 // Try to gather the array constructor extent.
671 mlir::Value extent;
672 fir::SequenceType::Extent typeExtent = fir::SequenceType::getUnknownExtent();
673 auto shapeExpr = Fortran::evaluate::GetContextFreeShape(
674 converter.getFoldingContext(), arrayCtorExpr);
675 if (shapeExpr && shapeExpr->size() == 1 && (*shapeExpr)[0]) {
676 const Fortran::evaluate::ExtentExpr &extentExpr = *(*shapeExpr)[0];
677 if (auto constantExtent = Fortran::evaluate::ToInt64(extentExpr)) {
678 typeExtent = *constantExtent;
679 extent = builder.createIntegerConstant(loc, idxType, typeExtent);
680 } else if (isCallFreeExpr(extentExpr)) {
681 // The expression built by expression analysis for the array constructor
682 // extent does not contain procedure symbols. It is side effect free.
683 // This could be relaxed to allow pure procedure, but some care must
684 // be taken to not bring in "unmapped" symbols from callee scopes.
685 extent = lowerExtentExpr(loc, converter, symMap, stmtCtx, extentExpr);
686 }
687 // Otherwise, the temporary will have to be built step by step with
688 // reallocation and the extent will only be known at the end of the array
689 // constructor evaluation.
690 }
691 // Convert the array constructor type and try to gather its length parameter
692 // values, if any.
693 mlir::SmallVector<mlir::Value> lengths;
694 mlir::Type elementType = LengthAndTypeCollector<T>::collect(
695 loc, converter, arrayCtorExpr, symMap, stmtCtx, lengths);
696 // Run an analysis of the array constructor ac-value.
697 ArrayCtorAnalysis analysis(converter.getFoldingContext(), arrayCtorExpr);
698 bool needToEvaluateOneExprToGetLengthParameters =
699 missingLengthParameters(elementType, lengths);
700 auto declaredType = fir::SequenceType::get({typeExtent}, elementType);
701
702 // Based on what was gathered and the result of the analysis, select and
703 // instantiate the right lowering strategy for the array constructor.
704 if (!extent || needToEvaluateOneExprToGetLengthParameters ||
705 analysis.anyArrayExpr || declaredType.getEleTy().isa<fir::RecordType>())
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,
728template <typename T>
729static 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.
745template <typename T>
746static 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 std::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.
778template <typename T>
779hlfir::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 std::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
802using namespace Fortran::evaluate;
803using namespace Fortran::common;
804FOR_EACH_SPECIFIC_TYPE(template class Fortran::lower::ArrayConstructorBuilder, )
805

source code of flang/lib/Lower/ConvertArrayConstructor.cpp