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