[flang][runtime] Add ragged array runtime functions

[clementval]

Summary

This patch adds the runtime function to allocate and
deallocate ragged arrays.

This patch is part of the upstreaming effort from fir-dev branch.

Co-authored-by: Eric Schweitz <[e-mail]>

[kiranchandramohan]

Might be good to get a review from @klausler.

[klausler]

There's no documentation in these APIs and the code doesn't look anything like the rest of the runtime. Please document what this code does and how it works.

[clementval]

In D114534#3158659, @klausler wrote:

There's no documentation in these APIs and the code doesn't look anything like the rest of the runtime. Please document what this code does and how it works.

@schweitz Can you take over this patch since you are the original author of these APIs in fir-dev?

[clementval]

Add update from Eric

[klausler]

flang/include/flang/Runtime/ragged.h

28

Could you convert the "flags" data member into a bool and a std::uint8_t? It's just holding a flag and an integer in the range 1-15, if I understand this rightly.

flang/runtime/ragged.cpp

15

These would both be better encoded as member functions, if that's possible.

26

Please use braced initialization in the runtime.

36

When bufferPointer is allocated with operator new [], it should be deleted with operator delete [], not std::free() as is done below. But maybe you should avoid the use of C++ runtime features to reduce the risk of making the Fortran runtime library dependent on a C++ runtime. Can you rewrite as a call to std::malloc()?

[clementval]

Address review comments

[klausler]

flang/include/flang/Runtime/ragged.h

28

Ping; this is the last unaddressed comment. Will this improvement be possible to make?

[clementval]

flang/include/flang/Runtime/ragged.h

28

It's done just forgot to mark it as done.

flang/include/flang/Runtime/ragged.h

+//===-- Runtime/ragged.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
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef FORTRAN_RUNTIME_RAGGED_H_
+#define FORTRAN_RUNTIME_RAGGED_H_
+
+#include "flang/Runtime/entry-names.h"
+#include <cstdint>
+
+namespace Fortran::runtime {
+struct RaggedArrayHeader {
+  std::uint64_t flags{0u};
+  void *bufferPointer{nullptr};
+  std::int64_t *extentPointer{nullptr};
+
+  bool isIndirection() const { return flags & 1; }
+  std::size_t rank() const { return flags >> 1; }
+};
+
+extern "C" {
+// Helper for allocation of ragged array buffer blocks.
+void *RTNAME(RaggedArrayAllocate)(
+    void *, bool, std::int64_t, std::int64_t, std::int64_t *);
+// Helper for deallocation of ragged array buffers.
+void RTNAME(RaggedArrayDeallocate)(void *);
+} // extern "C"
+} // namespace Fortran::runtime
+#endif // FORTRAN_RUNTIME_RAGGED_H_

flang/runtime/CMakeLists.txt

add_flang_library(FortranRuntime
   io-error.cpp
   io-stmt.cpp
   main.cpp
   matmul.cpp
   memory.cpp
   misc-intrinsic.cpp
   namelist.cpp
   numeric.cpp
+  ragged.cpp
   random.cpp
   reduction.cpp
   pointer.cpp
   product.cpp
   stat.cpp
   stop.cpp
   sum.cpp
   terminator.cpp

flang/runtime/ragged.cpp

+//===-- runtime/ragged.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/ragged.h"
+#include <cstdlib>
+
+namespace Fortran::runtime {
+
+static RaggedArrayHeader *RaggedArrayAllocate(RaggedArrayHeader *header,
+    bool isHeader, std::int64_t rank, std::int64_t elementSize,
+    std::int64_t *extentVector) {
+  if (header && rank) {
+    std::int64_t size = 1;
+    for (std::int64_t counter{0}; counter < rank; ++counter) {
+      size *= extentVector[counter];
+      if (size <= 0) {
+        return nullptr;
+      }
+    }
+    header->flags = (rank << 1) | isHeader;
+    header->extentPointer = extentVector;
+    if (isHeader) {
+      header->bufferPointer = new RaggedArrayHeader[size];
+    } else {
+      header->bufferPointer =
+          static_cast<void *>(std::calloc(elementSize, size));
+    }
+    return header;
+  } else {
+    return nullptr;
+  }
+}
+
+// Deallocate a ragged array from the heap.
+static void RaggedArrayDeallocate(RaggedArrayHeader *raggedArrayHeader) {
+  if (raggedArrayHeader) {
+    if (std::size_t end{raggedArrayHeader->rank()}) {
+      if (raggedArrayHeader->isIndirection()) {
+        std::size_t linearExtent{1u};
+        for (std::size_t counter{0u}; counter < end && linearExtent > 0;
+             ++counter) {
+          linearExtent *= raggedArrayHeader->extentPointer[counter];
+        }
+        for (std::size_t counter{0u}; counter < linearExtent; ++counter) {
+          RaggedArrayDeallocate(&static_cast<RaggedArrayHeader *>(
+              raggedArrayHeader->bufferPointer)[counter]);
+        }
+      }
+      std::free(raggedArrayHeader->bufferPointer);
+      std::free(raggedArrayHeader->extentPointer);
+      raggedArrayHeader->flags = 0u;
+    }
+  }
+}
+
+extern "C" {
+void *RTNAME(RaggedArrayAllocate)(void *header, bool isHeader,
+    std::int64_t rank, std::int64_t elementSize, std::int64_t *extentVector) {
+  auto *result = RaggedArrayAllocate(static_cast<RaggedArrayHeader *>(header),
+      isHeader, rank, elementSize, extentVector);
+  return static_cast<void *>(result);
+}
+
+void RTNAME(RaggedArrayDeallocate)(void *raggedArrayHeader) {
+  RaggedArrayDeallocate(static_cast<RaggedArrayHeader *>(raggedArrayHeader));
+}
+} // extern "C"
+} // namespace Fortran::runtime

flang/unittests/Runtime/CMakeLists.txt

 add_flang_unittest(FlangRuntimeTests
   BufferTest.cpp
   CharacterTest.cpp
   CommandTest.cpp
   CrashHandlerFixture.cpp
   ExternalIOTest.cpp
   Format.cpp
   ListInputTest.cpp
   Matmul.cpp
   MiscIntrinsic.cpp
   Namelist.cpp
   Numeric.cpp
   NumericalFormatTest.cpp
+  Ragged.cpp
   Random.cpp
   Reduction.cpp
   RuntimeCrashTest.cpp
   Stop.cpp
   Time.cpp
   Transformational.cpp
 )
 
 target_link_libraries(FlangRuntimeTests
   PRIVATE
   FortranRuntime
 )

flang/unittests/Runtime/Ragged.cpp

+//===-- flang/unittests/Runtime/Ragged.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 "flang/Runtime/ragged.h"
+#include "gtest/gtest.h"
+
+using namespace Fortran::runtime;
+
+TEST(Ragged, RaggedArrayAllocateDeallocateTest) {
+  struct RaggedArrayHeader header;
+  unsigned rank = 2;
+  int64_t *extents = new int64_t[2];
+  extents[0] = 10;
+  extents[1] = 100;
+  RaggedArrayHeader *ret = (RaggedArrayHeader *)_FortranARaggedArrayAllocate(
+      &header, false, rank, 32, extents);
+  EXPECT_TRUE(ret != nullptr);
+  EXPECT_EQ(4u, ret->flags);
+  EXPECT_TRUE(ret->bufferPointer != nullptr);
+  EXPECT_EQ(extents, ret->extentPointer);
+  EXPECT_EQ(10, ret->extentPointer[0]);
+  EXPECT_EQ(100, ret->extentPointer[1]);
+  EXPECT_EQ(rank, ret->rank());
+  EXPECT_FALSE(ret->isIndirection());
+
+  _FortranARaggedArrayDeallocate(ret);
+  EXPECT_EQ(0u, ret->flags);
+}