diff --git a/flang/include/flang/Runtime/array-constructor.h b/flang/include/flang/Runtime/array-constructor.h new file mode 100644 --- /dev/null +++ b/flang/include/flang/Runtime/array-constructor.h @@ -0,0 +1,116 @@ +//===-- include/flang/Runtime/array-constructor.h ---------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +// External APIs to create temporary storage for array constructors when their +// final extents or length parameters cannot be pre-computed. + +#ifndef FORTRAN_RUNTIME_ARRAYCONSTRUCTOR_H_ +#define FORTRAN_RUNTIME_ARRAYCONSTRUCTOR_H_ + +#include "flang/Runtime/descriptor.h" +#include "flang/Runtime/entry-names.h" +#include + +namespace Fortran::runtime { + +// Runtime data structure to hold information about the storage of +// an array constructor being constructed. +struct ArrayConstructorVector { + ArrayConstructorVector(class Descriptor &to, SubscriptValue nextValuePosition, + SubscriptValue actualAllocationSize, const char *sourceFile, + int sourceLine, bool useValueLengthParameters) + : to{to}, nextValuePosition{nextValuePosition}, + actualAllocationSize{actualAllocationSize}, sourceFile{sourceFile}, + sourceLine{sourceLine}, useValueLengthParameters_{ + useValueLengthParameters} {} + + bool useValueLengthParameters() const { return useValueLengthParameters_; } + + class Descriptor &to; + SubscriptValue nextValuePosition; + SubscriptValue actualAllocationSize; + const char *sourceFile; + int sourceLine; + +private: + unsigned char useValueLengthParameters_ : 1; +}; + +// This file defines an API to "push" an evaluated array constructor value +// "from" into some storage "to" of an array constructor. It can be seen as a +// form of std::vector::push_back() implementation for Fortran array +// constructors. In the APIs and ArrayConstructorVector struct above: +// +// - "to" is a ranked-1 descriptor whose declared type is already set to the +// array constructor derived type. It may be already allocated, even before the +// first call to this API, or it may be unallocated. "to" extent is increased +// every time a "from" is pushed past its current extent. At this end of the +// API calls, its extent is the extent of the array constructor. If "to" is +// unallocated and its extent is not null, it is assumed this is the final array +// constructor extent value, and the first allocation already "reserves" storage +// space accordingly to avoid reallocations. +// - "from" is a scalar or array descriptor for the evaluated array +// constructor value that must be copied into the storage of "to" at +// "nextValuePosition". +// - "useValueLengthParameters" must be set to true if the array constructor +// has length parameters and no type spec. If it is true and "to" is +// unallocated, "to" will take the length parameters of "from". If it is true +// and "to" is an allocated character array constructor, it will be checked +// that "from" length matches the one from "to". When it is false, the +// character length must already be set in "to" before the first call to this +// API and "from" character lengths are allowed to mismatch from "to". +// - "nextValuePosition" is the zero based sequence position of "from" in the +// array constructor. It is updated after this call by the number of "from" +// elements. It should be set to zero by the caller of this API before the first +// call. +// - "actualAllocationSize" is the current allocation size of "to" storage. It +// may be bigger than "to" extent for reallocation optimization purposes, but +// should never be smaller, unless this is the first call and "to" is +// unallocated. It is updated by the runtime after each successful allocation or +// reallocation. It should be set to "to" extent if "to" is allocated before the +// first call of this API, and can be left undefined otherwise. +// +// Note that this API can be used with "to" being a variable (that can be +// discontiguous). This can be done when the variable is the left hand side of +// an assignment from an array constructor as long as: +// - none of the ac-value overlaps with the variable, +// - this is an intrinsic assignment that is not a whole allocatable +// assignment, *and* for a type that has no components requiring user defined +// assignments, +// - the variable is properly finalized before using this API if its need to, +// - "useValueLengthParameters" should be set to false in this case, even if +// the array constructor has no type-spec, since the variable may have a +// different character length than the array constructor values. + +extern "C" { +// API to initialize an ArrayConstructorVector before any values are pushed to +// it. Inlined code is only expected to allocate the "ArrayConstructorVector" +// class instance storage with sufficient size (using +// "2*sizeof(ArrayConstructorVector)" on the host should be safe regardless of +// the target the runtime is compiled for). This avoids the need for the runtime +// to maintain a state, or to use dynamic allocation for it. "vectorClassSize" +// is used to validate that lowering allocated enough space for it. +void RTNAME(InitArrayConstructorVector)(ArrayConstructorVector &vector, + Descriptor &to, bool useValueLengthParameters, int vectorClassSize, + const char *sourceFile = nullptr, int sourceLine = 0); + +// Generic API to push any kind of entity into the array constructor (any +// Fortran type and any rank). +void RTNAME(PushArrayConstructorValue)( + ArrayConstructorVector &vector, const Descriptor &from); + +// API to push scalar array constructor value of: +// - a numerical or logical type, +// - or a derived type that has no length parameters, and no allocatable +// component (that would require deep copies). +// It requires no descriptor for the value that is passed via its base address. +void RTNAME(PushArrayConstructorSimpleScalar)( + ArrayConstructorVector &vector, void *from); +} // extern "C" +} // namespace Fortran::runtime +#endif // FORTRAN_RUNTIME_ARRAYCONSTRUCTOR_H_ diff --git a/flang/lib/Lower/ConvertArrayConstructor.cpp b/flang/lib/Lower/ConvertArrayConstructor.cpp --- a/flang/lib/Lower/ConvertArrayConstructor.cpp +++ b/flang/lib/Lower/ConvertArrayConstructor.cpp @@ -14,8 +14,10 @@ #include "flang/Lower/StatementContext.h" #include "flang/Lower/SymbolMap.h" #include "flang/Optimizer/Builder/HLFIRTools.h" +#include "flang/Optimizer/Builder/Runtime/RTBuilder.h" #include "flang/Optimizer/Builder/Todo.h" #include "flang/Optimizer/HLFIR/HLFIROps.h" +#include "flang/Runtime/array-constructor.h" // Array constructors are lowered with three different strategies. // All strategies are not possible with all array constructors. diff --git a/flang/runtime/CMakeLists.txt b/flang/runtime/CMakeLists.txt --- a/flang/runtime/CMakeLists.txt +++ b/flang/runtime/CMakeLists.txt @@ -96,6 +96,7 @@ add_flang_library(FortranRuntime ISO_Fortran_binding.cpp allocatable.cpp + array-constructor.cpp assign.cpp buffer.cpp command.cpp diff --git a/flang/runtime/array-constructor.cpp b/flang/runtime/array-constructor.cpp new file mode 100644 --- /dev/null +++ b/flang/runtime/array-constructor.cpp @@ -0,0 +1,180 @@ +//===-- runtime/array-constructor.cpp -------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "flang/Runtime/array-constructor.h" +#include "derived.h" +#include "terminator.h" +#include "type-info.h" +#include "flang/Runtime/allocatable.h" +#include "flang/Runtime/assign.h" +#include "flang/Runtime/descriptor.h" + +namespace Fortran::runtime { + +// Initial allocation size for an array constructor temporary whose extent +// cannot be pre-computed. This could be fined tuned if needed based on actual +// program performance. +// REAL(4), INTEGER(4), COMPLEX(2), ... -> 32 elements. +// REAL(8), INTEGER(8), COMPLEX(4), ... -> 16 elements. +// REAL(16), INTEGER(16), COMPLEX(8), ... -> 8 elements. +// Bigger types -> 4 elements. +static SubscriptValue initialAllocationSize( + SubscriptValue initialNumberOfElements, SubscriptValue elementBytes) { + // Try to guess an optimal initial allocation size in number of elements to + // avoid doing too many reallocation. + static constexpr SubscriptValue minNumberOfBytes{128}; + static constexpr SubscriptValue minNumberOfElements{4}; + SubscriptValue numberOfElements{initialNumberOfElements > minNumberOfElements + ? initialNumberOfElements + : minNumberOfElements}; + SubscriptValue elementsForMinBytes{minNumberOfBytes / elementBytes}; + return std::max(numberOfElements, elementsForMinBytes); +} + +static void AllocateOrReallocateVectorIfNeeded(ArrayConstructorVector &vector, + Terminator &terminator, SubscriptValue previousToElements, + SubscriptValue fromElements) { + Descriptor &to{vector.to}; + if (to.IsAllocatable() && !to.IsAllocated()) { + // The descriptor bounds may already be set here if the array constructor + // extent could be pre-computed, but information about length parameters + // was missing and required evaluating the first array constructor value. + if (previousToElements == 0) { + SubscriptValue allocationSize{ + initialAllocationSize(fromElements, to.ElementBytes())}; + to.GetDimension(0).SetBounds(1, allocationSize); + RTNAME(AllocatableAllocate) + (to, /*hasStat=*/false, /*errMsg=*/nullptr, vector.sourceFile, + vector.sourceLine); + to.GetDimension(0).SetBounds(1, fromElements); + vector.actualAllocationSize = allocationSize; + } else { + // Do not over-allocate if the final extent was known before pushing the + // first value: there should be no reallocation. + RUNTIME_CHECK(terminator, previousToElements >= fromElements); + RTNAME(AllocatableAllocate) + (to, /*hasStat=*/false, /*errMsg=*/nullptr, vector.sourceFile, + vector.sourceLine); + vector.actualAllocationSize = previousToElements; + } + } else { + SubscriptValue newToElements{vector.nextValuePosition + fromElements}; + if (to.IsAllocatable() && vector.actualAllocationSize < newToElements) { + // Reallocate. Ensure the current storage is at least doubled to avoid + // doing too many reallocations. + SubscriptValue requestedAllocationSize{ + std::max(newToElements, vector.actualAllocationSize * 2)}; + std::size_t newByteSize{requestedAllocationSize * to.ElementBytes()}; + // realloc is undefined with zero new size and ElementBytes() may be null + // if the character length is null, or if "from" is a zero sized array. + if (newByteSize > 0) { + void *p{std::realloc(to.raw().base_addr, newByteSize)}; + RUNTIME_CHECK(terminator, p); + to.set_base_addr(p); + } + vector.actualAllocationSize = requestedAllocationSize; + to.GetDimension(0).SetBounds(1, newToElements); + } else if (previousToElements < newToElements) { + // Storage is big enough, but descriptor extent must be increased because + // the final extent was not known before pushing array constructor values. + to.GetDimension(0).SetBounds(1, newToElements); + } + } +} + +extern "C" { +void RTNAME(InitArrayConstructorVector)(ArrayConstructorVector &vector, + Descriptor &to, bool useValueLengthParameters, int vectorClassSize, + const char *sourceFile, int sourceLine) { + Terminator terminator{vector.sourceFile, vector.sourceLine}; + RUNTIME_CHECK(terminator, + to.rank() == 1 && + sizeof(ArrayConstructorVector) <= + static_cast(vectorClassSize)); + SubscriptValue actualAllocationSize{ + to.IsAllocated() ? static_cast(to.Elements()) : 0}; + (void)new (&vector) ArrayConstructorVector{to, /*nextValuePosition=*/0, + actualAllocationSize, sourceFile, sourceLine, useValueLengthParameters}; +} + +void RTNAME(PushArrayConstructorValue)( + ArrayConstructorVector &vector, const Descriptor &from) { + Terminator terminator{vector.sourceFile, vector.sourceLine}; + Descriptor &to{vector.to}; + SubscriptValue fromElements{static_cast(from.Elements())}; + SubscriptValue previousToElements{static_cast(to.Elements())}; + if (vector.useValueLengthParameters()) { + // Array constructor with no type spec. + if (to.IsAllocatable() && !to.IsAllocated()) { + // Takes length parameters, if any, from the first value. + // Note that "to" type must already be set by the caller of this API since + // it cannot be taken from "from" here: "from" may be polymorphic (have a + // dynamic type that differs from its declared type) and Fortran 2018 7.8 + // point 4. says that the dynamic type of an array constructor is its + // declared type: it does not inherit the dynamic type of its ac-value + // even if if there is no type-spec. + if (to.type().IsCharacter()) { + to.raw().elem_len = from.ElementBytes(); + } else if (auto *toAddendum{to.Addendum()}) { + if (const auto *fromAddendum{from.Addendum()}) { + if (const auto *toDerived{toAddendum->derivedType()}) { + std::size_t lenParms{toDerived->LenParameters()}; + for (std::size_t j{0}; j < lenParms; ++j) { + toAddendum->SetLenParameterValue( + j, fromAddendum->LenParameterValue(j)); + } + } + } + } + } else if (to.type().IsCharacter()) { + // Fortran 2018 7.8 point 2. + if (to.ElementBytes() != from.ElementBytes()) { + terminator.Crash("Array constructor: mismatched character lengths (%d " + "!= %d) between " + "values of an array constructor without type-spec", + to.ElementBytes() / to.type().GetCategoryAndKind()->second, + from.ElementBytes() / from.type().GetCategoryAndKind()->second); + } + } + } + // Otherwise, the array constructor had a type-spec and the length + // parameters are already in the "to" descriptor. + + AllocateOrReallocateVectorIfNeeded( + vector, terminator, previousToElements, fromElements); + + // Create descriptor for "to" element or section being copied to. + SubscriptValue lower[1]{ + to.GetDimension(0).LowerBound() + vector.nextValuePosition}; + SubscriptValue upper[1]{lower[0] + fromElements - 1}; + SubscriptValue stride[1]{from.rank() == 0 ? 0 : 1}; + StaticDescriptor staticDesc; + Descriptor &toCurrentElement{staticDesc.descriptor()}; + toCurrentElement.EstablishPointerSection(to, lower, upper, stride); + // Note: toCurrentElement and from have the same number of elements + // and "toCurrentElement" is not an allocatable so AssignTemporary + // below works even if "from" rank is bigger than one (and differs + // from "toCurrentElement") and not time is wasted reshaping + // "toCurrentElement" to "from" shape. + RTNAME(AssignTemporary) + (toCurrentElement, from, vector.sourceFile, vector.sourceLine); + vector.nextValuePosition += fromElements; +} + +void RTNAME(PushArrayConstructorSimpleScalar)( + ArrayConstructorVector &vector, void *from) { + Terminator terminator{vector.sourceFile, vector.sourceLine}; + Descriptor &to{vector.to}; + AllocateOrReallocateVectorIfNeeded(vector, terminator, to.Elements(), 1); + SubscriptValue subscript[1]{ + to.GetDimension(0).LowerBound() + vector.nextValuePosition}; + std::memcpy(to.Element(subscript), from, to.ElementBytes()); + ++vector.nextValuePosition; +} +} // extern "C" +} // namespace Fortran::runtime diff --git a/flang/runtime/assign.cpp b/flang/runtime/assign.cpp --- a/flang/runtime/assign.cpp +++ b/flang/runtime/assign.cpp @@ -205,6 +205,11 @@ // of the capabilities of this function -- but when the LHS is allocatable, // the type might have a user-defined ASSIGNMENT(=), or the type might be // finalizable, this function should be used. +// When "to" is not a whole allocatable, "from" is an array, and defined +// assignments are not used, "to" and "from" only need to have the same number +// of elements, but their shape need not to conform (the assignment is done in +// element sequence order). This facilitates some internal usages, like when +// dealing with array constructors. static void Assign(Descriptor &to, const Descriptor &from, Terminator &terminator, bool maybeReallocate, bool needFinalization, bool canBeDefinedAssignment, bool componentCanBeDefinedAssignment) { diff --git a/flang/unittests/Runtime/ArrayConstructor.cpp b/flang/unittests/Runtime/ArrayConstructor.cpp new file mode 100644 --- /dev/null +++ b/flang/unittests/Runtime/ArrayConstructor.cpp @@ -0,0 +1,159 @@ +//===-- flang/unittests/Runtime/ArrayConstructor.cpp-------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "gtest/gtest.h" +#include "tools.h" +#include "flang/Runtime/allocatable.h" +#include "flang/Runtime/array-constructor.h" +#include "flang/Runtime/cpp-type.h" +#include "flang/Runtime/descriptor.h" +#include "flang/Runtime/type-code.h" + +#include + +using namespace Fortran::runtime; +using Fortran::common::TypeCategory; + +TEST(ArrayConstructor, Basic) { + // X(4) = [1,2,3,4] + // Y(2:3,4:6) = RESHAPE([5,6,7,8,9,10], shape=[2,3]) + // + // Test creation of: [(i, X, Y, i=0,99,1)] + auto x{MakeArray( + std::vector{4}, std::vector{1, 2, 3, 4})}; + auto y{MakeArray( + std::vector{2, 3}, std::vector{5, 6, 7, 8, 9, 10})}; + y->GetDimension(0).SetBounds(2, 3); + y->GetDimension(1).SetBounds(4, 6); + + StaticDescriptor<1, false> statDesc; + Descriptor &result{statDesc.descriptor()}; + result.Establish(TypeCode{CFI_type_int32_t}, 4, /*p=*/nullptr, + /*rank=*/1, /*extents=*/nullptr, CFI_attribute_allocatable); + std::allocator cookieAllocator; + ArrayConstructorVector *acVector{cookieAllocator.allocate(1)}; + ASSERT_TRUE(acVector); + + // Case 1: result is a temp and extent is unknown before first call. + result.GetDimension(0).SetBounds(1, 0); + + RTNAME(InitArrayConstructorVector) + (*acVector, result, /*useValueLengthParameters=*/false, + /*vectorClassSize=*/sizeof(ArrayConstructorVector)); + for (std::int32_t i{0}; i <= 99; ++i) { + RTNAME(PushArrayConstructorSimpleScalar)(*acVector, &i); + RTNAME(PushArrayConstructorValue)(*acVector, *x); + RTNAME(PushArrayConstructorValue)(*acVector, *y); + } + + ASSERT_TRUE(result.IsAllocated()); + ASSERT_EQ(result.Elements(), static_cast(100 * (1 + 4 + 2 * 3))); + SubscriptValue subscript[1]{1}; + for (std::int32_t i{0}; i <= 99; ++i) { + ASSERT_EQ(*result.Element(subscript), i); + ++subscript[0]; + for (std::int32_t j{1}; j <= 10; ++j) { + EXPECT_EQ(*result.Element(subscript), j); + ++subscript[0]; + } + } + EXPECT_LE(result.Elements(), + static_cast(acVector->actualAllocationSize)); + result.Deallocate(); + ASSERT_TRUE(!result.IsAllocated()); + + // Case 2: result is an unallocated temp and extent is know before first call. + // and is allocated when the first value is pushed. + result.GetDimension(0).SetBounds(1, 1234); + RTNAME(InitArrayConstructorVector) + (*acVector, result, /*useValueLengthParameters=*/false, + /*vectorClassSize=*/sizeof(ArrayConstructorVector)); + EXPECT_EQ(0, acVector->actualAllocationSize); + std::int32_t i{42}; + RTNAME(PushArrayConstructorSimpleScalar)(*acVector, &i); + ASSERT_TRUE(result.IsAllocated()); + EXPECT_EQ(1234, acVector->actualAllocationSize); + result.Deallocate(); + + cookieAllocator.deallocate(acVector, 1); +} + +TEST(ArrayConstructor, Character) { + // CHARACTER(2) :: C = "12" + // X(4) = ["ab", "cd", "ef", "gh"] + // Y(2:3,4:6) = RESHAPE(["ij", "jl", "mn", "op", "qr","st"], shape=[2,3]) + auto x{MakeArray(std::vector{4}, + std::vector{"ab", "cd", "ef", "gh"}, 2)}; + auto y{MakeArray(std::vector{2, 3}, + std::vector{"ij", "kl", "mn", "op", "qr", "st"}, 2)}; + y->GetDimension(0).SetBounds(2, 3); + y->GetDimension(1).SetBounds(4, 6); + auto c{MakeArray( + std::vector{}, std::vector{"12"}, 2)}; + + StaticDescriptor<1, false> statDesc; + Descriptor &result{statDesc.descriptor()}; + result.Establish(TypeCode{CFI_type_char}, 0, /*p=*/nullptr, + /*rank=*/1, /*extents=*/nullptr, CFI_attribute_allocatable); + std::allocator cookieAllocator; + ArrayConstructorVector *acVector{cookieAllocator.allocate(1)}; + ASSERT_TRUE(acVector); + + // Case 1: result is a temp and extent and length are unknown before the first + // call. Test creation of: [(C, X, Y, i=1,10,1)] + static constexpr std::size_t expectedElements{10 * (1 + 4 + 2 * 3)}; + result.GetDimension(0).SetBounds(1, 0); + RTNAME(InitArrayConstructorVector) + (*acVector, result, /*useValueLengthParameters=*/true, + /*vectorClassSize=*/sizeof(ArrayConstructorVector)); + for (std::int32_t i{1}; i <= 10; ++i) { + RTNAME(PushArrayConstructorValue)(*acVector, *c); + RTNAME(PushArrayConstructorValue)(*acVector, *x); + RTNAME(PushArrayConstructorValue)(*acVector, *y); + } + ASSERT_TRUE(result.IsAllocated()); + ASSERT_EQ(result.Elements(), expectedElements); + ASSERT_EQ(result.ElementBytes(), 2u); + EXPECT_LE(result.Elements(), + static_cast(acVector->actualAllocationSize)); + std::string CXY{"12abcdefghijklmnopqrst"}; + std::string expect; + for (int i{0}; i < 10; ++i) + expect.append(CXY); + EXPECT_EQ(std::memcmp( + result.OffsetElement(0), expect.data(), expect.length()), + 0); + result.Deallocate(); + cookieAllocator.deallocate(acVector, 1); +} + +TEST(ArrayConstructor, CharacterRuntimeCheck) { + // CHARACTER(2) :: C2 + // CHARACTER(3) :: C3 + // Test the runtime catch bad [C2, C3] array constructors (Fortran 2018 7.8 + // point 2.) + auto c2{MakeArray( + std::vector{}, std::vector{"ab"}, 2)}; + auto c3{MakeArray( + std::vector{}, std::vector{"abc"}, 3)}; + StaticDescriptor<1, false> statDesc; + Descriptor &result{statDesc.descriptor()}; + result.Establish(TypeCode{CFI_type_char}, 0, /*p=*/nullptr, + /*rank=*/1, /*extents=*/nullptr, CFI_attribute_allocatable); + std::allocator cookieAllocator; + ArrayConstructorVector *acVector{cookieAllocator.allocate(1)}; + ASSERT_TRUE(acVector); + + result.GetDimension(0).SetBounds(1, 0); + RTNAME(InitArrayConstructorVector) + (*acVector, result, /*useValueLengthParameters=*/true, + /*vectorClassSize=*/sizeof(ArrayConstructorVector)); + RTNAME(PushArrayConstructorValue)(*acVector, *c2); + ASSERT_DEATH(RTNAME(PushArrayConstructorValue)(*acVector, *c3), + "Array constructor: mismatched character lengths"); +} diff --git a/flang/unittests/Runtime/CMakeLists.txt b/flang/unittests/Runtime/CMakeLists.txt --- a/flang/unittests/Runtime/CMakeLists.txt +++ b/flang/unittests/Runtime/CMakeLists.txt @@ -1,5 +1,6 @@ add_flang_unittest(FlangRuntimeTests Allocatable.cpp + ArrayConstructor.cpp BufferTest.cpp CharacterTest.cpp CommandTest.cpp