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