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}, 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
276private:
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.
285class 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
290public:
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
416private:
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.
432class ArrayCtorLoweringStrategy {
433public:
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
474private:
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).
489static 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
502namespace {
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.
506template <typename T>
507struct 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
520template <>
521struct 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
535template <int Kind>
536using Character =
537 Fortran::evaluate::Type<Fortran::common::TypeCategory::Character, Kind>;
538template <int Kind>
539struct 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?
563static 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
570namespace {
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.
575struct 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
597template <typename T>
598ArrayCtorAnalysis::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?
651static 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.
662template <typename T>
663static 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,
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 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.
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 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
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