[clang] [llvm] [APFloat] Add APFloat support for FP4 data type (PR #95392)

[Jakub Kuderski via cfe-commits]

@@ -6907,6 +7028,42 @@ TEST(APFloatTest, ConvertE2M3FToE3M2F) {
   EXPECT_EQ(status, APFloat::opInexact);
 }
 
+TEST(APFloatTest, ConvertDoubleToE2M1F) {
+  bool losesInfo;

kuhar wrote:

It's an output parameter in `.convert`, so shouldn't matter either way?

https://github.com/llvm/llvm-project/pull/95392
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [llvm] Intrinsic: introduce minimumnum and maximumnum (PR #93841)

[Jakub Kuderski via cfe-commits]

@@ -1449,6 +1449,16 @@ inline APFloat minimum(const APFloat , const APFloat 
) {
 return A.isNegative() ? A : B;
   return B < A ? B : A;
 }
+LLVM_READONLY

kuhar wrote:

Please add and an empty line before this function and document its semantics.

https://github.com/llvm/llvm-project/pull/93841
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [llvm] Intrinsic: introduce minimumnum and maximumnum (PR #93841)

[Jakub Kuderski via cfe-commits]

@@ -1462,6 +1472,16 @@ inline APFloat maximum(const APFloat , const APFloat 
) {
 return A.isNegative() ? B : A;
   return A < B ? B : A;
 }
+LLVM_READONLY

kuhar wrote:

also here

https://github.com/llvm/llvm-project/pull/93841
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [llvm] [APFloat] Add APFloat support for FP6 data types (PR #94735)

[Jakub Kuderski via cfe-commits]

https://github.com/kuhar edited https://github.com/llvm/llvm-project/pull/94735
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [llvm] [APFloat] Add APFloat support for FP6 data types (PR #94735)

[Jakub Kuderski via cfe-commits]

@@ -68,6 +68,10 @@ enum class fltNonfiniteBehavior {
   // `fltNanEncoding` enum. We treat all NaNs as quiet, as the available
   // encodings do not distinguish between signalling and quiet NaN.
   NanOnly,
+
+  // This behavior is present in Float6E3M2FN and Float6E2M3FN types.
+  // There is no representation for Inf or NaN.
+  NoNanInf,

kuhar wrote:

> FiniteOnly
I find this one most descriptive.

https://github.com/llvm/llvm-project/pull/94735
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [llvm] [APFloat] Add APFloat support for FP6 data types (PR #94735)

[Jakub Kuderski via cfe-commits]

@@ -1499,16 +1521,18 @@ static void tcSetLeastSignificantBits(APInt::WordType 
*dst, unsigned parts,
 /* Handle overflow.  Sign is preserved.  We either become infinity or
the largest finite number.  */
 IEEEFloat::opStatus IEEEFloat::handleOverflow(roundingMode rounding_mode) {
-  /* Infinity?  */
-  if (rounding_mode == rmNearestTiesToEven ||
-  rounding_mode == rmNearestTiesToAway ||
-  (rounding_mode == rmTowardPositive && !sign) ||
-  (rounding_mode == rmTowardNegative && sign)) {
-if (semantics->nonFiniteBehavior == fltNonfiniteBehavior::NanOnly)
-  makeNaN(false, sign);
-else
-  category = fcInfinity;
-return (opStatus) (opOverflow | opInexact);
+  if (semantics->nonFiniteBehavior != fltNonfiniteBehavior::NoNanInf) {
+/* Infinity?  */
+if (rounding_mode == rmNearestTiesToEven ||
+rounding_mode == rmNearestTiesToAway ||
+(rounding_mode == rmTowardPositive && !sign) ||
+(rounding_mode == rmTowardNegative && sign)) {
+  if (semantics->nonFiniteBehavior == fltNonfiniteBehavior::NanOnly)
+makeNaN(false, sign);
+  else
+category = fcInfinity;
+  return (opStatus)(opOverflow | opInexact);

kuhar wrote:

nit: prefer `static_cast`

https://github.com/llvm/llvm-project/pull/94735
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [llvm] [APFloat] Add APFloat support for FP6 data types (PR #94735)

[Jakub Kuderski via cfe-commits]

@@ -68,6 +68,10 @@ enum class fltNonfiniteBehavior {
   // `fltNanEncoding` enum. We treat all NaNs as quiet, as the available
   // encodings do not distinguish between signalling and quiet NaN.
   NanOnly,
+
+  // This behavior is present in Float6E3M2FN and Float6E2M3FN types.
+  // There is no representation for Inf or NaN.
+  NoNanInf,

kuhar wrote:

nit:
```suggestion
  // This behavior is present in Float6E3M2FN and Float6E2M3FN types,
  // which do not support Inf or NaN values.
  NoNanInf,
```
also, is there a standard name for such FP types? Maybe `Finite` or would that 
be too overloaded?


https://github.com/llvm/llvm-project/pull/94735
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [llvm] [APFloat] Add APFloat support for FP6 data types (PR #94735)

[Jakub Kuderski via cfe-commits]

@@ -878,6 +896,10 @@ void IEEEFloat::copySignificand(const IEEEFloat ) {
for the significand.  If double or longer, this is a signalling NaN,
which may not be ideal.  If float, this is QNaN(0).  */
 void IEEEFloat::makeNaN(bool SNaN, bool Negative, const APInt *fill) {
+  if (semantics->nonFiniteBehavior == fltNonfiniteBehavior::NoNanInf) {
+assert(false && "This floating point format does not support NaN\n");
+return;

kuhar wrote:

Also no `\n`

https://github.com/llvm/llvm-project/pull/94735
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [llvm] [AArch64] Add support for Qualcomm Oryon processor (PR #91022)

[Jakub Kuderski via cfe-commits]

https://github.com/kuhar updated https://github.com/llvm/llvm-project/pull/91022

>From 8aebe46d7fdd15f02a9716718f53b03056ef0d19 Mon Sep 17 00:00:00 2001
From: Wei Zhao 
Date: Fri, 3 May 2024 22:01:58 +
Subject: [PATCH 1/3] [AArch64] Add support for Qualcomm Oryon processor

---
 clang/test/Driver/aarch64-oryon-1.c   |   19 +
 clang/test/Misc/target-invalid-cpu-note.c |4 +-
 .../llvm/TargetParser/AArch64TargetParser.h   |5 +
 llvm/lib/Target/AArch64/AArch64.td|5 +
 llvm/lib/Target/AArch64/AArch64Processors.td  |   30 +
 llvm/lib/Target/AArch64/AArch64SchedOryon.td  | 1727 +
 llvm/lib/Target/AArch64/AArch64Subtarget.cpp  |7 +
 llvm/lib/TargetParser/Host.cpp|1 +
 llvm/unittests/TargetParser/Host.cpp  |3 +
 .../TargetParser/TargetParserTest.cpp |   16 +-
 10 files changed, 1813 insertions(+), 4 deletions(-)
 create mode 100644 clang/test/Driver/aarch64-oryon-1.c
 create mode 100644 llvm/lib/Target/AArch64/AArch64SchedOryon.td

diff --git a/clang/test/Driver/aarch64-oryon-1.c 
b/clang/test/Driver/aarch64-oryon-1.c
new file mode 100644
index 0..952ba5df74baf
--- /dev/null
+++ b/clang/test/Driver/aarch64-oryon-1.c
@@ -0,0 +1,19 @@
+// RUN: %clang -target aarch64 -mcpu=oryon-1 -### -c %s 2>&1 | FileCheck 
-check-prefix=Phoenix %s
+// RUN: %clang -target aarch64 -mlittle-endian -mcpu=oryon-1 -### -c %s 2>&1 | 
FileCheck -check-prefix=Phoenix %s
+// RUN: %clang -target aarch64_be -mlittle-endian -mcpu=oryon-1 -### -c %s 
2>&1 | FileCheck -check-prefix=Phoenix %s
+// RUN: %clang -target aarch64 -mtune=oryon-1 -### -c %s 2>&1 | FileCheck 
-check-prefix=Phoenix-TUNE %s
+// RUN: %clang -target aarch64 -mlittle-endian -mtune=oryon-1 -### -c %s 2>&1 
| FileCheck -check-prefix=Phoenix-TUNE %s
+// RUN: %clang -target aarch64_be -mlittle-endian -mtune=oryon-1 -### -c %s 
2>&1 | FileCheck -check-prefix=Phoenix-TUNE %s
+// Phoenix: "-cc1"{{.*}} "-triple" "aarch64{{(--)?}}"{{.*}} "-target-cpu" 
"oryon-1" "-target-feature" "+v8.6a"
+// Phoenix-TUNE: "-cc1"{{.*}} "-triple" "aarch64{{(--)?}}"{{.*}} "-target-cpu" 
"generic"
+
+// RUN: %clang -target arm64 -mcpu=oryon-1 -### -c %s 2>&1 | FileCheck 
-check-prefix=ARM64-Phoenix %s
+// RUN: %clang -target arm64 -mlittle-endian -mcpu=oryon-1 -### -c %s 2>&1 | 
FileCheck -check-prefix=ARM64-Phoenix %s
+// RUN: %clang -target arm64 -mtune=oryon-1 -### -c %s 2>&1 | FileCheck 
-check-prefix=ARM64-Phoenix-TUNE %s
+// RUN: %clang -target arm64 -mlittle-endian -mtune=oryon-1 -### -c %s 2>&1 | 
FileCheck -check-prefix=ARM64-Phoenix-TUNE %s
+// ARM64-Phoenix: "-cc1"{{.*}} "-triple" "arm64{{.*}}" "-target-cpu" "oryon-1" 
"-target-feature" "+v8.6a"
+// ARM64-Phoenix-TUNE: "-cc1"{{.*}} "-triple" "arm64{{.*}}" "-target-cpu" 
"generic"
+
+// RUN: %clang -target aarch64 -mcpu=oryon-1 -mtune=cortex-a53 -### -c %s 2>&1 
| FileCheck -check-prefix=MCPU-MTUNE-Phoenix %s
+// RUN: %clang -target aarch64 -mtune=cortex-a53 -mcpu=oryon-1  -### -c %s 
2>&1 | FileCheck -check-prefix=MCPU-MTUNE-Phoenix %s
+// MCPU-MTUNE-Phoenix: "-cc1"{{.*}} "-triple" "aarch64{{.*}}" "-target-cpu" 
"oryon-1"
diff --git a/clang/test/Misc/target-invalid-cpu-note.c 
b/clang/test/Misc/target-invalid-cpu-note.c
index 768b243b04e3a..a71ebd6a023e7 100644
--- a/clang/test/Misc/target-invalid-cpu-note.c
+++ b/clang/test/Misc/target-invalid-cpu-note.c
@@ -5,11 +5,11 @@
 
 // RUN: not %clang_cc1 -triple arm64--- -target-cpu not-a-cpu -fsyntax-only %s 
2>&1 | FileCheck %s --check-prefix AARCH64
 // AARCH64: error: unknown target CPU 'not-a-cpu'
-// AARCH64-NEXT: note: valid target CPU values are: cortex-a34, cortex-a35, 
cortex-a53, cortex-a55, cortex-a510, cortex-a520, cortex-a520ae, cortex-a57, 
cortex-a65, cortex-a65ae, cortex-a72, cortex-a73, cortex-a75, cortex-a76, 
cortex-a76ae, cortex-a77, cortex-a78, cortex-a78ae, cortex-a78c, cortex-a710, 
cortex-a715, cortex-a720, cortex-a720ae, cortex-r82, cortex-r82ae, cortex-x1, 
cortex-x1c, cortex-x2, cortex-x3, cortex-x4, neoverse-e1, neoverse-n1, 
neoverse-n2, neoverse-n3, neoverse-512tvb, neoverse-v1, neoverse-v2, 
neoverse-v3, neoverse-v3ae, cyclone, apple-a7, apple-a8, apple-a9, apple-a10, 
apple-a11, apple-a12, apple-a13, apple-a14, apple-a15, apple-a16, apple-a17, 
apple-m1, apple-m2, apple-m3, apple-s4, apple-s5, exynos-m3, exynos-m4, 
exynos-m5, falkor, saphira, kryo, thunderx2t99, thunderx3t110, thunderx, 
thunderxt88, thunderxt81, thunderxt83, tsv110, a64fx, carmel, ampere1, 
ampere1a, ampere1b, cobalt-100, grace{{$}}
+// AARCH64-NEXT: note: valid target CPU values are: cortex-a34, cortex-a35, 
cortex-a53, cortex-a55, cortex-a510, cortex-a520, cortex-a520ae, cortex-a57, 
cortex-a65, cortex-a65ae, cortex-a72, cortex-a73, cortex-a75, cortex-a76, 
cortex-a76ae, cortex-a77, cortex-a78, cortex-a78ae, cortex-a78c, cortex-a710, 
cortex-a715, cortex-a720, cortex-a720ae, cortex-r82, cortex-r82ae, cortex-x1, 
cortex-x1c, cortex-x2, cortex-x3, cortex-x4, neoverse-e1, neoverse-n1, 

[clang-tools-extra] [flang] [lld] [llvm] Use StringRef::operator== instead of StringRef::equals (NFC) (PR #91864)

[Jakub Kuderski via cfe-commits]

https://github.com/kuhar approved this pull request.


https://github.com/llvm/llvm-project/pull/91864
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[mlir] [clang-tools-extra] [llvm] [mlir][ArithToAMDGPU] Add option for saturating truncation to fp8 (PR #74153)

[Jakub Kuderski via cfe-commits]

https://github.com/kuhar approved this pull request.

LGTM

https://github.com/llvm/llvm-project/pull/74153
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[compiler-rt] [mlir] [llvm] [clang] [libcxx] [flang] [clang-tools-extra] [libc] Make SmallVectorImpl destructor protected (PR #71439)

[Jakub Kuderski via cfe-commits]

https://github.com/kuhar approved this pull request.

I think we have reached consensus that this is the preferred direction. 
`SerializeToHsaco` is a tiny detail in the grand scheme of things, and because 
this PR doesn't make it any worse, I don't think we should be blocked by it.

https://github.com/llvm/llvm-project/pull/71439
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[flang] [compiler-rt] [libc] [libcxx] [clang-tools-extra] [llvm] [clang] [mlir] Make SmallVectorImpl destructor protected (PR #71439)

[Jakub Kuderski via cfe-commits]

https://github.com/kuhar edited https://github.com/llvm/llvm-project/pull/71439
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [libcxx] [mlir] [compiler-rt] [clang-tools-extra] [flang] [llvm] [libc] Make SmallVectorImpl destructor protected (PR #71439)

[Jakub Kuderski via cfe-commits]

https://github.com/kuhar commented:

Overall I think this makes sense, but the `SerializeToHsaco` changes look 
suboptimal

https://github.com/llvm/llvm-project/pull/71439
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[flang] [compiler-rt] [libc] [libcxx] [clang-tools-extra] [llvm] [clang] [mlir] Make SmallVectorImpl destructor protected (PR #71439)

[Jakub Kuderski via cfe-commits]

https://github.com/kuhar edited https://github.com/llvm/llvm-project/pull/71439
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[flang] [libcxx] [libc] [compiler-rt] [llvm] [clang-tools-extra] [clang] [mlir] Make SmallVectorImpl destructor protected (PR #71439)

[Jakub Kuderski via cfe-commits]

@@ -95,7 +95,7 @@ class SerializeToHsacoPass
   std::unique_ptr>
   serializeISA(const std::string ) override;
 
-  std::unique_ptr> assembleIsa(const std::string );
+  std::unique_ptr> assembleIsa(const std::string );

kuhar wrote:

IMO this should either return `SmallVector` (without an exact size) or 
take `SmallVectorImpl &` as the second function argument

https://github.com/llvm/llvm-project/pull/71439
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [Support] Deprecate system_endianness (PR #68279)

[Jakub Kuderski via cfe-commits]

https://github.com/kuhar approved this pull request.

nit: typos in the commit/PR message: bit --> big

code lgtm

https://github.com/llvm/llvm-project/pull/68279
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] Avoid need for SLocEntryLoaded BitVector (PR #67960)

[Jakub Kuderski via cfe-commits]

https://github.com/kuhar commented:

The ADT change looks good to me, I'm not familiar with the clang code though.

https://github.com/llvm/llvm-project/pull/67960
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] Avoid need for SLocEntryLoaded BitVector (PR #67960)

[Jakub Kuderski via cfe-commits]

https://github.com/kuhar edited https://github.com/llvm/llvm-project/pull/67960
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] Avoid need for SLocEntryLoaded BitVector (PR #67960)

[Jakub Kuderski via cfe-commits]

@@ -180,6 +180,20 @@ TEST(PagedVectorTest, FillNonTrivialConstructor) {
   EXPECT_EQ(std::distance(V.materialized_begin(), V.materialized_end()), 10LL);
 }
 
+// Test that isMaterialized returns true for all the elements
+// of the page, not only the one that was accessed.
+TEST(PagedVectorTest, IsMaterialized) {
+  PagedVector V;
+  V.resize(20);
+  EXPECT_EQ(V.isMaterialized(0), false);

kuhar wrote:

We can Uluse `EXPECT_TRUE`/`FALSE`.

https://github.com/llvm/llvm-project/pull/67960
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] Avoid need for SLocEntryLoaded BitVector (PR #67960)

[Jakub Kuderski via cfe-commits]

@@ -103,6 +103,14 @@ template  
class PagedVector {
   /// Return the size of the vector.
   [[nodiscard]] size_t size() const { return Size; }
 
+  /// @return true in case the element at index @a Index belongs to a page 
which
+  /// was already materialised.

kuhar wrote:

nit: This uses a different style than all the other function documentation in 
this file. For consistency, shouldn't this be something like:
```suggestion
  /// Return true if the element at `Index` belongs to a page which was already
  /// materialized, i.e., had at least one element accessed.
```

https://github.com/llvm/llvm-project/pull/67960
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] Avoid need for SLocEntryLoaded BitVector (PR #67960)

[Jakub Kuderski via cfe-commits]

@@ -103,6 +103,12 @@ template  
class PagedVector {
   /// Return the size of the vector.
   [[nodiscard]] size_t size() const { return Size; }
 
+  [[nodiscard]] bool isMaterialized(size_t Index) const {

kuhar wrote:

Could you add a documentation comment above? This is not a standard function 
found in most containers so it would be nice to introduce it properly.

https://github.com/llvm/llvm-project/pull/67960
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] Avoid need for SLocEntryLoaded BitVector (PR #67960)

[Jakub Kuderski via cfe-commits]

@@ -103,6 +103,12 @@ template  
class PagedVector {
   /// Return the size of the vector.
   [[nodiscard]] size_t size() const { return Size; }
 
+  [[nodiscard]] bool isMaterialized(size_t Index) const {
+assert(Index < Size);
+assert(Index / PageSize < PageToDataPtrs.size());
+return PageToDataPtrs[Index / PageSize] != nullptr;

kuhar wrote:

```suggestion
return PageToDataPtrs[Index / PageSize];
```

https://github.com/llvm/llvm-project/pull/67960
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] Introduce paged vector (PR #66430)

[Jakub Kuderski via cfe-commits]

kuhar wrote:

@vgvassilev 
> I find the use of the macro I proposed cleaner though.

Ideally, I think we could have an llvm-specific macro that combines the guard 
and the check (say `LLVM_EXPECT_DEATH`), so that it's less of a footgun. In any 
case, the failures should be resolved now, and we can iterate it further in the 
future.

https://github.com/llvm/llvm-project/pull/66430
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] Introduce paged vector (PR #66430)

[Jakub Kuderski via cfe-commits]

kuhar wrote:

Also, don't use have to guard that with `#ifdef EXPECT_DEBUG_DEATH`?

https://github.com/llvm/llvm-project/pull/66430
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] Introduce paged vector (PR #66430)

[Jakub Kuderski via cfe-commits]

kuhar wrote:

@vgvassilev I've seen other tests use the pattern from my fix. Feel free to 
overwrite with your version if that's preferred.

https://github.com/llvm/llvm-project/pull/66430
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] Introduce paged vector (PR #66430)

[Jakub Kuderski via cfe-commits]

kuhar wrote:

@vvereschaka I submitted a fix for death tests in 
https://github.com/llvm/llvm-project/commit/8580010672e9ff37b0744927296ca00dbcbef5be

https://github.com/llvm/llvm-project/pull/66430
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] Introduce paged vector (PR #66430)

[Jakub Kuderski via cfe-commits]

@@ -0,0 +1,266 @@
+//===- llvm/ADT/PagedVector.h - 'Lazily allocated' vectors --*- 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
+//
+//===--===//
+//
+// This file defines the PagedVector class.
+//
+//===--===//
+#ifndef LLVM_ADT_PAGEDVECTOR_H
+#define LLVM_ADT_PAGEDVECTOR_H
+
+#include "llvm/ADT/PointerIntPair.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/iterator_range.h"
+#include "llvm/Support/Allocator.h"
+#include 
+#include 
+
+namespace llvm {
+/// A vector that allocates memory in pages.
+///
+/// Order is kept, but memory is allocated only when one element of the page is
+/// accessed. This introduces a level of indirection, but it is useful when you
+/// have a sparsely initialised vector where the full size is allocated 
upfront.
+///
+/// As a side effect the elements are initialised later than in a normal 
vector.
+/// On the first access to one of the elements of a given page, all the 
elements
+/// of the page are initialised. This also means that the elements of the page
+/// are initialised beyond the size of the vector.
+///
+/// Similarly on destruction the elements are destroyed only when the page is
+/// not needed anymore, delaying invoking the destructor of the elements.
+///
+/// Notice that this has iterators only on materialized elements. This
+/// is deliberately done under the assumption you would dereference the 
elements
+/// while iterating, therefore materialising them and losing the gains in terms
+/// of memory usage this container provides. If you have such a use case, you
+/// probably want to use a normal std::vector or a llvm::SmallVector.
+template  class PagedVector {
+  static_assert(PageSize > 1, "PageSize must be greater than 0. Most likely "
+  "you want it to be greater than 16.");
+  /// The actual number of elements in the vector which can be accessed.
+  size_t Size = 0;
+
+  /// The position of the initial element of the page in the Data vector.
+  /// Pages are allocated contiguously in the Data vector.
+  mutable SmallVector PageToDataPtrs;
+  /// Actual page data. All the page elements are allocated on the
+  /// first access of any of the elements of the page. Elements are default
+  /// constructed and elements of the page are stored contiguously.
+  PointerIntPair Allocator;
+
+public:
+  using value_type = T;
+
+  /// Default constructor. We build our own allocator and mark it as such with
+  /// `true` in the second pair element.
+  PagedVector() : Allocator(new BumpPtrAllocator, true) {}
+  explicit PagedVector(BumpPtrAllocator *A) : Allocator(A, false) {
+assert(A && "Allocator cannot be nullptr");
+  }
+
+  ~PagedVector() {
+clear();
+// If we own the allocator, delete it.
+if (Allocator.getInt())
+  delete Allocator.getPointer();
+  }
+
+  // Forbid copy and move as we do not need them for the current use case.
+  PagedVector(const PagedVector &) = delete;
+  PagedVector(PagedVector &&) = delete;
+  PagedVector =(const PagedVector &) = delete;
+  PagedVector =(PagedVector &&) = delete;
+
+  /// Look up an element at position `Index`.
+  /// If the associated page is not filled, it will be filled with default
+  /// constructed elements.
+  T [](size_t Index) const {
+assert(Index < Size);
+assert(Index / PageSize < PageToDataPtrs.size());
+T * = PageToDataPtrs[Index / PageSize];
+// If the page was not yet allocated, allocate it.
+if (!PagePtr) {
+  PagePtr = Allocator.getPointer()->template Allocate(PageSize);
+  // We need to invoke the default constructor on all the elements of the
+  // page.
+  std::uninitialized_value_construct_n(PagePtr, PageSize);
+}
+// Dereference the element in the page.
+return PagePtr[Index % PageSize];
+  }
+
+  /// Return the capacity of the vector. I.e. the maximum size it can be
+  /// expanded to with the resize method without allocating more pages.
+  [[nodiscard]] size_t capacity() const {
+return PageToDataPtrs.size() * PageSize;
+  }
+
+  /// Return the size of the vector.
+  [[nodiscard]] size_t size() const { return Size; }
+
+  /// Resize the vector. Notice that the constructor of the elements will not
+  /// be invoked until an element of a given page is accessed, at which point
+  /// all the elements of the page will be constructed.
+  ///
+  /// If the new size is smaller than the current size, the elements of the
+  /// pages that are not needed anymore will be destroyed, however, elements of
+  /// the last page will not be destroyed.
+  ///
+  /// For these reason the usage of this vector is discouraged if you rely
+  /// on the construction / destructor of the 

[clang] Introduce paged vector (PR #66430)

[Jakub Kuderski via cfe-commits]

@@ -0,0 +1,266 @@
+//===- llvm/ADT/PagedVector.h - 'Lazily allocated' vectors --*- 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
+//
+//===--===//
+//
+// This file defines the PagedVector class.
+//
+//===--===//
+#ifndef LLVM_ADT_PAGEDVECTOR_H
+#define LLVM_ADT_PAGEDVECTOR_H
+
+#include "llvm/ADT/PointerIntPair.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/iterator_range.h"
+#include "llvm/Support/Allocator.h"
+#include 
+#include 
+
+namespace llvm {
+/// A vector that allocates memory in pages.
+///
+/// Order is kept, but memory is allocated only when one element of the page is
+/// accessed. This introduces a level of indirection, but it is useful when you
+/// have a sparsely initialised vector where the full size is allocated 
upfront.
+///
+/// As a side effect the elements are initialised later than in a normal 
vector.
+/// On the first access to one of the elements of a given page, all the 
elements
+/// of the page are initialised. This also means that the elements of the page
+/// are initialised beyond the size of the vector.
+///
+/// Similarly on destruction the elements are destroyed only when the page is
+/// not needed anymore, delaying invoking the destructor of the elements.
+///
+/// Notice that this has iterators only on materialized elements. This
+/// is deliberately done under the assumption you would dereference the 
elements
+/// while iterating, therefore materialising them and losing the gains in terms
+/// of memory usage this container provides. If you have such a use case, you
+/// probably want to use a normal std::vector or a llvm::SmallVector.
+template  class PagedVector {
+  static_assert(PageSize > 1, "PageSize must be greater than 0. Most likely "
+  "you want it to be greater than 16.");
+  /// The actual number of elements in the vector which can be accessed.
+  size_t Size = 0;
+
+  /// The position of the initial element of the page in the Data vector.
+  /// Pages are allocated contiguously in the Data vector.
+  mutable SmallVector PageToDataPtrs;
+  /// Actual page data. All the page elements are allocated on the
+  /// first access of any of the elements of the page. Elements are default
+  /// constructed and elements of the page are stored contiguously.
+  PointerIntPair Allocator;
+
+public:
+  using value_type = T;
+
+  /// Default constructor. We build our own allocator and mark it as such with
+  /// `true` in the second pair element.
+  PagedVector() : Allocator(new BumpPtrAllocator, true) {}
+  explicit PagedVector(BumpPtrAllocator *A) : Allocator(A, false) {
+assert(A && "Allocator cannot be nullptr");
+  }
+
+  ~PagedVector() {
+clear();
+// If we own the allocator, delete it.
+if (Allocator.getInt())
+  delete Allocator.getPointer();
+  }
+
+  // Forbid copy and move as we do not need them for the current use case.
+  PagedVector(const PagedVector &) = delete;
+  PagedVector(PagedVector &&) = delete;
+  PagedVector =(const PagedVector &) = delete;
+  PagedVector =(PagedVector &&) = delete;
+
+  /// Look up an element at position `Index`.
+  /// If the associated page is not filled, it will be filled with default
+  /// constructed elements.
+  T [](size_t Index) const {
+assert(Index < Size);
+assert(Index / PageSize < PageToDataPtrs.size());
+T * = PageToDataPtrs[Index / PageSize];
+// If the page was not yet allocated, allocate it.
+if (!PagePtr) {
+  PagePtr = Allocator.getPointer()->template Allocate(PageSize);
+  // We need to invoke the default constructor on all the elements of the
+  // page.
+  std::uninitialized_value_construct_n(PagePtr, PageSize);
+}
+// Dereference the element in the page.
+return PagePtr[Index % PageSize];
+  }
+
+  /// Return the capacity of the vector. I.e. the maximum size it can be
+  /// expanded to with the resize method without allocating more pages.
+  [[nodiscard]] size_t capacity() const {
+return PageToDataPtrs.size() * PageSize;
+  }
+
+  /// Return the size of the vector.
+  [[nodiscard]] size_t size() const { return Size; }
+
+  /// Resize the vector. Notice that the constructor of the elements will not
+  /// be invoked until an element of a given page is accessed, at which point
+  /// all the elements of the page will be constructed.
+  ///
+  /// If the new size is smaller than the current size, the elements of the
+  /// pages that are not needed anymore will be destroyed, however, elements of
+  /// the last page will not be destroyed.
+  ///
+  /// For these reason the usage of this vector is discouraged if you rely
+  /// on the construction / destructor of the 

[clang] Introduce paged vector (PR #66430)

[Jakub Kuderski via cfe-commits]

@@ -0,0 +1,266 @@
+//===- llvm/ADT/PagedVector.h - 'Lazily allocated' vectors --*- 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
+//
+//===--===//
+//
+// This file defines the PagedVector class.
+//
+//===--===//
+#ifndef LLVM_ADT_PAGEDVECTOR_H
+#define LLVM_ADT_PAGEDVECTOR_H
+
+#include "llvm/ADT/PointerIntPair.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/iterator_range.h"
+#include "llvm/Support/Allocator.h"
+#include 
+#include 
+
+namespace llvm {
+/// A vector that allocates memory in pages.
+///
+/// Order is kept, but memory is allocated only when one element of the page is
+/// accessed. This introduces a level of indirection, but it is useful when you
+/// have a sparsely initialised vector where the full size is allocated 
upfront.
+///
+/// As a side effect the elements are initialised later than in a normal 
vector.
+/// On the first access to one of the elements of a given page, all the 
elements
+/// of the page are initialised. This also means that the elements of the page
+/// are initialised beyond the size of the vector.
+///
+/// Similarly on destruction the elements are destroyed only when the page is
+/// not needed anymore, delaying invoking the destructor of the elements.
+///
+/// Notice that this has iterators only on materialized elements. This
+/// is deliberately done under the assumption you would dereference the 
elements
+/// while iterating, therefore materialising them and losing the gains in terms
+/// of memory usage this container provides. If you have such a use case, you
+/// probably want to use a normal std::vector or a llvm::SmallVector.
+template  class PagedVector {
+  static_assert(PageSize > 1, "PageSize must be greater than 0. Most likely "
+  "you want it to be greater than 16.");
+  /// The actual number of elements in the vector which can be accessed.
+  size_t Size = 0;
+
+  /// The position of the initial element of the page in the Data vector.
+  /// Pages are allocated contiguously in the Data vector.
+  mutable SmallVector PageToDataPtrs;
+  /// Actual page data. All the page elements are allocated on the
+  /// first access of any of the elements of the page. Elements are default
+  /// constructed and elements of the page are stored contiguously.
+  PointerIntPair Allocator;
+
+public:
+  using value_type = T;
+
+  /// Default constructor. We build our own allocator and mark it as such with
+  /// `true` in the second pair element.
+  PagedVector() : Allocator(new BumpPtrAllocator, true) {}
+  explicit PagedVector(BumpPtrAllocator *A) : Allocator(A, false) {
+assert(A && "Allocator cannot be nullptr");
+  }
+
+  ~PagedVector() {
+clear();
+// If we own the allocator, delete it.
+if (Allocator.getInt())
+  delete Allocator.getPointer();
+  }
+
+  // Forbid copy and move as we do not need them for the current use case.
+  PagedVector(const PagedVector &) = delete;
+  PagedVector(PagedVector &&) = delete;
+  PagedVector =(const PagedVector &) = delete;
+  PagedVector =(PagedVector &&) = delete;
+
+  /// Look up an element at position `Index`.
+  /// If the associated page is not filled, it will be filled with default
+  /// constructed elements.
+  T [](size_t Index) const {
+assert(Index < Size);
+assert(Index / PageSize < PageToDataPtrs.size());
+T * = PageToDataPtrs[Index / PageSize];
+// If the page was not yet allocated, allocate it.
+if (!PagePtr) {
+  PagePtr = Allocator.getPointer()->template Allocate(PageSize);
+  // We need to invoke the default constructor on all the elements of the
+  // page.
+  std::uninitialized_value_construct_n(PagePtr, PageSize);
+}
+// Dereference the element in the page.
+return PagePtr[Index % PageSize];
+  }
+
+  /// Return the capacity of the vector. I.e. the maximum size it can be
+  /// expanded to with the resize method without allocating more pages.
+  [[nodiscard]] size_t capacity() const {
+return PageToDataPtrs.size() * PageSize;
+  }
+
+  /// Return the size of the vector.
+  [[nodiscard]] size_t size() const { return Size; }
+
+  /// Resize the vector. Notice that the constructor of the elements will not
+  /// be invoked until an element of a given page is accessed, at which point
+  /// all the elements of the page will be constructed.
+  ///
+  /// If the new size is smaller than the current size, the elements of the
+  /// pages that are not needed anymore will be destroyed, however, elements of
+  /// the last page will not be destroyed.
+  ///
+  /// For these reason the usage of this vector is discouraged if you rely
+  /// on the construction / destructor of the 

[clang] Introduce paged vector (PR #66430)

[Jakub Kuderski via cfe-commits]

@@ -0,0 +1,266 @@
+//===- llvm/ADT/PagedVector.h - 'Lazily allocated' vectors --*- 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
+//
+//===--===//
+//
+// This file defines the PagedVector class.
+//
+//===--===//
+#ifndef LLVM_ADT_PAGEDVECTOR_H
+#define LLVM_ADT_PAGEDVECTOR_H
+
+#include "llvm/ADT/PointerIntPair.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/iterator_range.h"
+#include "llvm/Support/Allocator.h"
+#include 
+#include 
+
+namespace llvm {
+/// A vector that allocates memory in pages.
+///
+/// Order is kept, but memory is allocated only when one element of the page is
+/// accessed. This introduces a level of indirection, but it is useful when you
+/// have a sparsely initialised vector where the full size is allocated 
upfront.
+///
+/// As a side effect the elements are initialised later than in a normal 
vector.
+/// On the first access to one of the elements of a given page, all the 
elements
+/// of the page are initialised. This also means that the elements of the page
+/// are initialised beyond the size of the vector.
+///
+/// Similarly on destruction the elements are destroyed only when the page is
+/// not needed anymore, delaying invoking the destructor of the elements.
+///
+/// Notice that this has iterators only on materialized elements. This
+/// is deliberately done under the assumption you would dereference the 
elements
+/// while iterating, therefore materialising them and losing the gains in terms
+/// of memory usage this container provides. If you have such a use case, you
+/// probably want to use a normal std::vector or a llvm::SmallVector.
+template  class PagedVector {
+  static_assert(PageSize > 1, "PageSize must be greater than 0. Most likely "
+  "you want it to be greater than 16.");
+  /// The actual number of elements in the vector which can be accessed.
+  size_t Size = 0;
+
+  /// The position of the initial element of the page in the Data vector.
+  /// Pages are allocated contiguously in the Data vector.
+  mutable SmallVector PageToDataPtrs;
+  /// Actual page data. All the page elements are allocated on the
+  /// first access of any of the elements of the page. Elements are default
+  /// constructed and elements of the page are stored contiguously.
+  PointerIntPair Allocator;
+
+public:
+  using value_type = T;
+
+  /// Default constructor. We build our own allocator and mark it as such with
+  /// `true` in the second pair element.
+  PagedVector() : Allocator(new BumpPtrAllocator, true) {}
+  explicit PagedVector(BumpPtrAllocator *A) : Allocator(A, false) {
+assert(A && "Allocator cannot be nullptr");
+  }
+
+  ~PagedVector() {
+clear();
+// If we own the allocator, delete it.
+if (Allocator.getInt())
+  delete Allocator.getPointer();
+  }
+
+  // Forbid copy and move as we do not need them for the current use case.
+  PagedVector(const PagedVector &) = delete;
+  PagedVector(PagedVector &&) = delete;
+  PagedVector =(const PagedVector &) = delete;
+  PagedVector =(PagedVector &&) = delete;
+
+  /// Look up an element at position `Index`.
+  /// If the associated page is not filled, it will be filled with default
+  /// constructed elements.
+  T [](size_t Index) const {
+assert(Index < Size);
+assert(Index / PageSize < PageToDataPtrs.size());
+T * = PageToDataPtrs[Index / PageSize];
+// If the page was not yet allocated, allocate it.
+if (!PagePtr) {
+  PagePtr = Allocator.getPointer()->template Allocate(PageSize);
+  // We need to invoke the default constructor on all the elements of the
+  // page.
+  std::uninitialized_value_construct_n(PagePtr, PageSize);
+}
+// Dereference the element in the page.
+return PagePtr[Index % PageSize];
+  }
+
+  /// Return the capacity of the vector. I.e. the maximum size it can be
+  /// expanded to with the resize method without allocating more pages.
+  [[nodiscard]] size_t capacity() const {
+return PageToDataPtrs.size() * PageSize;
+  }
+
+  /// Return the size of the vector.
+  [[nodiscard]] size_t size() const { return Size; }
+
+  /// Resize the vector. Notice that the constructor of the elements will not
+  /// be invoked until an element of a given page is accessed, at which point
+  /// all the elements of the page will be constructed.
+  ///
+  /// If the new size is smaller than the current size, the elements of the
+  /// pages that are not needed anymore will be destroyed, however, elements of
+  /// the last page will not be destroyed.
+  ///
+  /// For these reason the usage of this vector is discouraged if you rely
+  /// on the construction / destructor of the 

[clang] Introduce paged vector (PR #66430)

[Jakub Kuderski via cfe-commits]

@@ -0,0 +1,266 @@
+//===- llvm/ADT/PagedVector.h - 'Lazily allocated' vectors --*- 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
+//
+//===--===//
+//
+// This file defines the PagedVector class.
+//
+//===--===//
+#ifndef LLVM_ADT_PAGEDVECTOR_H
+#define LLVM_ADT_PAGEDVECTOR_H
+
+#include "llvm/ADT/PointerIntPair.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/iterator_range.h"
+#include "llvm/Support/Allocator.h"
+#include 
+#include 
+
+namespace llvm {
+/// A vector that allocates memory in pages.
+///
+/// Order is kept, but memory is allocated only when one element of the page is
+/// accessed. This introduces a level of indirection, but it is useful when you
+/// have a sparsely initialised vector where the full size is allocated 
upfront.
+///
+/// As a side effect the elements are initialised later than in a normal 
vector.
+/// On the first access to one of the elements of a given page, all the 
elements
+/// of the page are initialised. This also means that the elements of the page
+/// are initialised beyond the size of the vector.
+///
+/// Similarly on destruction the elements are destroyed only when the page is
+/// not needed anymore, delaying invoking the destructor of the elements.
+///
+/// Notice that this has iterators only on materialized elements. This
+/// is deliberately done under the assumption you would dereference the 
elements
+/// while iterating, therefore materialising them and losing the gains in terms
+/// of memory usage this container provides. If you have such a use case, you
+/// probably want to use a normal std::vector or a llvm::SmallVector.
+template  class PagedVector {
+  static_assert(PageSize > 1, "PageSize must be greater than 0. Most likely "
+  "you want it to be greater than 16.");
+  /// The actual number of elements in the vector which can be accessed.
+  size_t Size = 0;
+
+  /// The position of the initial element of the page in the Data vector.
+  /// Pages are allocated contiguously in the Data vector.
+  mutable SmallVector PageToDataPtrs;
+  /// Actual page data. All the page elements are allocated on the
+  /// first access of any of the elements of the page. Elements are default
+  /// constructed and elements of the page are stored contiguously.
+  PointerIntPair Allocator;
+
+public:
+  using value_type = T;
+
+  /// Default constructor. We build our own allocator and mark it as such with
+  /// `true` in the second pair element.
+  PagedVector() : Allocator(new BumpPtrAllocator, true) {}
+  explicit PagedVector(BumpPtrAllocator *A) : Allocator(A, false) {
+assert(A && "Allocator cannot be nullptr");
+  }
+
+  ~PagedVector() {
+clear();
+// If we own the allocator, delete it.
+if (Allocator.getInt())
+  delete Allocator.getPointer();
+  }
+
+  // Forbid copy and move as we do not need them for the current use case.
+  PagedVector(const PagedVector &) = delete;
+  PagedVector(PagedVector &&) = delete;
+  PagedVector =(const PagedVector &) = delete;
+  PagedVector =(PagedVector &&) = delete;
+
+  /// Look up an element at position `Index`.
+  /// If the associated page is not filled, it will be filled with default
+  /// constructed elements.
+  T [](size_t Index) const {
+assert(Index < Size);
+assert(Index / PageSize < PageToDataPtrs.size());
+T * = PageToDataPtrs[Index / PageSize];
+// If the page was not yet allocated, allocate it.
+if (!PagePtr) {
+  PagePtr = Allocator.getPointer()->template Allocate(PageSize);
+  // We need to invoke the default constructor on all the elements of the
+  // page.
+  std::uninitialized_value_construct_n(PagePtr, PageSize);
+}
+// Dereference the element in the page.
+return PagePtr[Index % PageSize];
+  }
+
+  /// Return the capacity of the vector. I.e. the maximum size it can be
+  /// expanded to with the resize method without allocating more pages.
+  [[nodiscard]] size_t capacity() const {
+return PageToDataPtrs.size() * PageSize;
+  }
+
+  /// Return the size of the vector.
+  [[nodiscard]] size_t size() const { return Size; }
+
+  /// Resize the vector. Notice that the constructor of the elements will not
+  /// be invoked until an element of a given page is accessed, at which point
+  /// all the elements of the page will be constructed.
+  ///
+  /// If the new size is smaller than the current size, the elements of the
+  /// pages that are not needed anymore will be destroyed, however, elements of
+  /// the last page will not be destroyed.
+  ///
+  /// For these reason the usage of this vector is discouraged if you rely
+  /// on the construction / destructor of the 

[clang] Introduce paged vector (PR #66430)

[Jakub Kuderski via cfe-commits]

https://github.com/kuhar approved this pull request.

Thanks for all the changes, LGTM. Please wait for a second approval before 
submitting if you can.

https://github.com/llvm/llvm-project/pull/66430
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] Introduce paged vector (PR #66430)

[Jakub Kuderski via cfe-commits]

https://github.com/kuhar resolved 
https://github.com/llvm/llvm-project/pull/66430
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] Introduce paged vector (PR #66430)

[Jakub Kuderski via cfe-commits]

@@ -0,0 +1,322 @@
+//===- llvm/ADT/PagedVector.h - 'Lazyly allocated' vectors *- 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
+//
+//===--===//
+//
+// This file defines the PagedVector class.
+//
+//===--===//
+#ifndef LLVM_ADT_PAGEDVECTOR_H
+#define LLVM_ADT_PAGEDVECTOR_H
+
+#include "llvm/ADT/PointerIntPair.h"
+#include "llvm/Support/Allocator.h"
+#include 
+#include 
+#include 
+
+namespace llvm {
+// A vector that allocates memory in pages.
+// Order is kept, but memory is allocated only when one element of the page is
+// accessed. This introduces a level of indirection, but it is useful when you
+// have a sparsely initialised vector where the full size is allocated upfront
+// with the default constructor and elements are initialised later, on first
+// access.
+//
+// Notice that this does not have iterators, because if you
+// have iterators it probably means you are going to touch
+// all the memory in any case, so better use a std::vector in
+// the first place.
+//
+// Pages are allocated in SLAB_SIZE chunks, using the BumpPtrAllocator.
+template 
+class PagedVector {
+  static_assert(PAGE_SIZE > 0, "PAGE_SIZE must be greater than 0. Most likely "
+   "you want it to be greater than 16.");
+  // The actual number of element in the vector which can be accessed.
+  std::size_t Size = 0;
+
+  // The position of the initial element of the page in the Data vector.
+  // Pages are allocated contiguously in the Data vector.
+  mutable std::vector PageToDataIdx;
+  // Actual page data. All the page elements are added to this vector on the
+  // first access of any of the elements of the page. Elements default
+  // constructed and elements of the page are stored contiguously. The order of
+  // the elements however depends on the order of access of the pages.
+  PointerIntPair Allocator;
+
+  constexpr static uintptr_t InvalidPage = SIZE_MAX;
+
+public:
+  using value_type = T;
+
+  // Default constructor. We build our own allocator.
+  PagedVector() : Allocator(new BumpPtrAllocator, true) {}
+  PagedVector(BumpPtrAllocator *A) : Allocator(A, false) {}
+
+  ~PagedVector() {

kuhar wrote:

SG

https://github.com/llvm/llvm-project/pull/66430
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] Introduce paged vector (PR #66430)

[Jakub Kuderski via cfe-commits]

@@ -0,0 +1,303 @@
+//===- llvm/ADT/PagedVector.h - 'Lazyly allocated' vectors *- 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
+//
+//===--===//
+//
+// This file defines the PagedVector class.
+//
+//===--===//
+#ifndef LLVM_ADT_PAGEDVECTOR_H
+#define LLVM_ADT_PAGEDVECTOR_H
+
+#include "llvm/ADT/PointerIntPair.h"
+#include "llvm/Support/Allocator.h"
+#include 
+#include 

kuhar wrote:

We don't need iostream

https://github.com/llvm/llvm-project/pull/66430
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] Introduce paged vector (PR #66430)

[Jakub Kuderski via cfe-commits]

https://github.com/kuhar resolved 
https://github.com/llvm/llvm-project/pull/66430
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] Introduce paged vector (PR #66430)

[Jakub Kuderski via cfe-commits]

https://github.com/kuhar resolved 
https://github.com/llvm/llvm-project/pull/66430
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] Introduce paged vector (PR #66430)

[Jakub Kuderski via cfe-commits]

https://github.com/kuhar resolved 
https://github.com/llvm/llvm-project/pull/66430
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] Introduce paged vector (PR #66430)

[Jakub Kuderski via cfe-commits]

https://github.com/kuhar resolved 
https://github.com/llvm/llvm-project/pull/66430
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] Introduce paged vector (PR #66430)

[Jakub Kuderski via cfe-commits]

@@ -0,0 +1,322 @@
+//===- llvm/ADT/PagedVector.h - 'Lazyly allocated' vectors *- 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
+//
+//===--===//
+//
+// This file defines the PagedVector class.
+//
+//===--===//
+#ifndef LLVM_ADT_PAGEDVECTOR_H
+#define LLVM_ADT_PAGEDVECTOR_H
+
+#include "llvm/ADT/PointerIntPair.h"
+#include "llvm/Support/Allocator.h"
+#include 
+#include 
+#include 
+
+namespace llvm {
+// A vector that allocates memory in pages.
+// Order is kept, but memory is allocated only when one element of the page is
+// accessed. This introduces a level of indirection, but it is useful when you
+// have a sparsely initialised vector where the full size is allocated upfront
+// with the default constructor and elements are initialised later, on first
+// access.
+//
+// Notice that this does not have iterators, because if you
+// have iterators it probably means you are going to touch
+// all the memory in any case, so better use a std::vector in
+// the first place.
+//
+// Pages are allocated in SLAB_SIZE chunks, using the BumpPtrAllocator.
+template 
+class PagedVector {
+  static_assert(PAGE_SIZE > 0, "PAGE_SIZE must be greater than 0. Most likely "
+   "you want it to be greater than 16.");
+  // The actual number of element in the vector which can be accessed.
+  std::size_t Size = 0;
+
+  // The position of the initial element of the page in the Data vector.
+  // Pages are allocated contiguously in the Data vector.
+  mutable std::vector PageToDataIdx;
+  // Actual page data. All the page elements are added to this vector on the
+  // first access of any of the elements of the page. Elements default
+  // constructed and elements of the page are stored contiguously. The order of
+  // the elements however depends on the order of access of the pages.
+  PointerIntPair Allocator;
+
+  constexpr static uintptr_t InvalidPage = SIZE_MAX;
+
+public:
+  using value_type = T;
+
+  // Default constructor. We build our own allocator.
+  PagedVector() : Allocator(new BumpPtrAllocator, true) {}
+  PagedVector(BumpPtrAllocator *A) : Allocator(A, false) {}
+
+  ~PagedVector() {
+// If we own the allocator, delete it.
+if (Allocator.getInt() == true)
+  delete Allocator.getPointer();
+  }
+
+  // Lookup an element at position i.
+  // If the associated page is not filled, it will be filled with default
+  // constructed elements. If the associated page is filled, return the 
element.
+  T [](std::size_t Index) const {
+assert(Index < Size);
+assert(Index / PAGE_SIZE < PageToDataIdx.size());
+uintptr_t  = PageToDataIdx[Index / PAGE_SIZE];
+// If the page was not yet allocated, allocate it.
+if (PagePtr == InvalidPage) {
+  T *NewPagePtr = Allocator.getPointer()->template Allocate(PAGE_SIZE);
+  // We need to invoke the default constructor on all the elements of the
+  // page.
+  for (std::size_t I = 0; I < PAGE_SIZE; ++I)
+new (NewPagePtr + I) T();
+
+  PagePtr = reinterpret_cast(NewPagePtr);
+}
+// Dereference the element in the page.
+return *((Index % PAGE_SIZE) + reinterpret_cast(PagePtr));
+  }
+
+  // Return the capacity of the vector. I.e. the maximum size it can be 
expanded
+  // to with the resize method without allocating more pages.
+  [[nodiscard]] std::size_t capacity() const {
+return PageToDataIdx.size() * PAGE_SIZE;
+  }
+
+  // Return the size of the vector. I.e. the maximum index that can be
+  // accessed, i.e. the maximum value which was used as argument of the
+  // resize method.
+  [[nodiscard]] std::size_t size() const { return Size; }
+
+  // Expands the vector to the given NewSize number of elements.
+  // If the vector was smaller, allocates new pages as needed.
+  // It should be called only with NewSize >= Size.
+  void resize(std::size_t NewSize) {
+// Handle shrink case: delete the pages and update the size.
+if (NewSize < Size) {
+  std::size_t NewLastPage = (NewSize - 1) / PAGE_SIZE;
+  for (std::size_t I = NewLastPage + 1; I < PageToDataIdx.size(); ++I) {
+uintptr_t PagePtr = PageToDataIdx[I];
+if (PagePtr == InvalidPage)
+  continue;
+T *Page = reinterpret_cast(PagePtr);
+// We need to invoke the destructor on all the elements of the page.
+for (std::size_t J = 0; J < PAGE_SIZE; ++J)
+  Page[J].~T();
+Allocator.getPointer()->Deallocate(Page);
+  }
+  // Delete the extra ones in the new last page.
+  uintptr_t PagePtr = PageToDataIdx[NewLastPage];
+  if (PagePtr != InvalidPage) {
+T *Page = reinterpret_cast(PagePtr);
+// If 

[clang] Introduce paged vector (PR #66430)

[Jakub Kuderski via cfe-commits]

@@ -0,0 +1,322 @@
+//===- llvm/ADT/PagedVector.h - 'Lazyly allocated' vectors *- 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
+//
+//===--===//
+//
+// This file defines the PagedVector class.
+//
+//===--===//
+#ifndef LLVM_ADT_PAGEDVECTOR_H
+#define LLVM_ADT_PAGEDVECTOR_H
+
+#include "llvm/ADT/PointerIntPair.h"
+#include "llvm/Support/Allocator.h"
+#include 
+#include 
+#include 
+
+namespace llvm {
+// A vector that allocates memory in pages.
+// Order is kept, but memory is allocated only when one element of the page is
+// accessed. This introduces a level of indirection, but it is useful when you
+// have a sparsely initialised vector where the full size is allocated upfront
+// with the default constructor and elements are initialised later, on first
+// access.
+//
+// Notice that this does not have iterators, because if you
+// have iterators it probably means you are going to touch
+// all the memory in any case, so better use a std::vector in
+// the first place.
+//
+// Pages are allocated in SLAB_SIZE chunks, using the BumpPtrAllocator.
+template 
+class PagedVector {
+  static_assert(PAGE_SIZE > 0, "PAGE_SIZE must be greater than 0. Most likely "
+   "you want it to be greater than 16.");
+  // The actual number of element in the vector which can be accessed.
+  std::size_t Size = 0;
+
+  // The position of the initial element of the page in the Data vector.
+  // Pages are allocated contiguously in the Data vector.
+  mutable std::vector PageToDataIdx;
+  // Actual page data. All the page elements are added to this vector on the
+  // first access of any of the elements of the page. Elements default
+  // constructed and elements of the page are stored contiguously. The order of
+  // the elements however depends on the order of access of the pages.
+  PointerIntPair Allocator;
+
+  constexpr static uintptr_t InvalidPage = SIZE_MAX;
+
+public:
+  using value_type = T;
+
+  // Default constructor. We build our own allocator.
+  PagedVector() : Allocator(new BumpPtrAllocator, true) {}
+  PagedVector(BumpPtrAllocator *A) : Allocator(A, false) {}
+
+  ~PagedVector() {
+// If we own the allocator, delete it.
+if (Allocator.getInt() == true)
+  delete Allocator.getPointer();
+  }
+
+  // Lookup an element at position i.

kuhar wrote:

```suggestion
  // Look up an element at position `Index`.
```

https://github.com/llvm/llvm-project/pull/66430
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] Introduce paged vector (PR #66430)

[Jakub Kuderski via cfe-commits]

@@ -0,0 +1,322 @@
+//===- llvm/ADT/PagedVector.h - 'Lazyly allocated' vectors *- 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
+//
+//===--===//
+//
+// This file defines the PagedVector class.
+//
+//===--===//
+#ifndef LLVM_ADT_PAGEDVECTOR_H
+#define LLVM_ADT_PAGEDVECTOR_H
+
+#include "llvm/ADT/PointerIntPair.h"
+#include "llvm/Support/Allocator.h"
+#include 
+#include 
+#include 
+
+namespace llvm {
+// A vector that allocates memory in pages.
+// Order is kept, but memory is allocated only when one element of the page is
+// accessed. This introduces a level of indirection, but it is useful when you
+// have a sparsely initialised vector where the full size is allocated upfront
+// with the default constructor and elements are initialised later, on first
+// access.
+//
+// Notice that this does not have iterators, because if you
+// have iterators it probably means you are going to touch
+// all the memory in any case, so better use a std::vector in
+// the first place.
+//
+// Pages are allocated in SLAB_SIZE chunks, using the BumpPtrAllocator.
+template 
+class PagedVector {
+  static_assert(PAGE_SIZE > 0, "PAGE_SIZE must be greater than 0. Most likely "
+   "you want it to be greater than 16.");
+  // The actual number of element in the vector which can be accessed.
+  std::size_t Size = 0;
+
+  // The position of the initial element of the page in the Data vector.
+  // Pages are allocated contiguously in the Data vector.
+  mutable std::vector PageToDataIdx;
+  // Actual page data. All the page elements are added to this vector on the
+  // first access of any of the elements of the page. Elements default
+  // constructed and elements of the page are stored contiguously. The order of
+  // the elements however depends on the order of access of the pages.
+  PointerIntPair Allocator;
+
+  constexpr static uintptr_t InvalidPage = SIZE_MAX;
+
+public:
+  using value_type = T;
+
+  // Default constructor. We build our own allocator.
+  PagedVector() : Allocator(new BumpPtrAllocator, true) {}
+  PagedVector(BumpPtrAllocator *A) : Allocator(A, false) {}
+
+  ~PagedVector() {
+// If we own the allocator, delete it.
+if (Allocator.getInt() == true)
+  delete Allocator.getPointer();
+  }
+
+  // Lookup an element at position i.
+  // If the associated page is not filled, it will be filled with default
+  // constructed elements. If the associated page is filled, return the 
element.
+  T [](std::size_t Index) const {
+assert(Index < Size);
+assert(Index / PAGE_SIZE < PageToDataIdx.size());
+uintptr_t  = PageToDataIdx[Index / PAGE_SIZE];
+// If the page was not yet allocated, allocate it.
+if (PagePtr == InvalidPage) {
+  T *NewPagePtr = Allocator.getPointer()->template Allocate(PAGE_SIZE);
+  // We need to invoke the default constructor on all the elements of the
+  // page.
+  for (std::size_t I = 0; I < PAGE_SIZE; ++I)
+new (NewPagePtr + I) T();
+
+  PagePtr = reinterpret_cast(NewPagePtr);
+}
+// Dereference the element in the page.
+return *((Index % PAGE_SIZE) + reinterpret_cast(PagePtr));
+  }
+
+  // Return the capacity of the vector. I.e. the maximum size it can be 
expanded
+  // to with the resize method without allocating more pages.
+  [[nodiscard]] std::size_t capacity() const {
+return PageToDataIdx.size() * PAGE_SIZE;
+  }
+
+  // Return the size of the vector. I.e. the maximum index that can be
+  // accessed, i.e. the maximum value which was used as argument of the
+  // resize method.
+  [[nodiscard]] std::size_t size() const { return Size; }
+
+  // Expands the vector to the given NewSize number of elements.
+  // If the vector was smaller, allocates new pages as needed.
+  // It should be called only with NewSize >= Size.
+  void resize(std::size_t NewSize) {
+// Handle shrink case: delete the pages and update the size.
+if (NewSize < Size) {
+  std::size_t NewLastPage = (NewSize - 1) / PAGE_SIZE;
+  for (std::size_t I = NewLastPage + 1; I < PageToDataIdx.size(); ++I) {
+uintptr_t PagePtr = PageToDataIdx[I];
+if (PagePtr == InvalidPage)
+  continue;
+T *Page = reinterpret_cast(PagePtr);
+// We need to invoke the destructor on all the elements of the page.
+for (std::size_t J = 0; J < PAGE_SIZE; ++J)
+  Page[J].~T();
+Allocator.getPointer()->Deallocate(Page);
+  }
+  // Delete the extra ones in the new last page.
+  uintptr_t PagePtr = PageToDataIdx[NewLastPage];
+  if (PagePtr != InvalidPage) {
+T *Page = reinterpret_cast(PagePtr);
+// If 

[clang] Introduce paged vector (PR #66430)

[Jakub Kuderski via cfe-commits]

@@ -0,0 +1,322 @@
+//===- llvm/ADT/PagedVector.h - 'Lazyly allocated' vectors *- 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
+//
+//===--===//
+//
+// This file defines the PagedVector class.
+//
+//===--===//
+#ifndef LLVM_ADT_PAGEDVECTOR_H
+#define LLVM_ADT_PAGEDVECTOR_H
+
+#include "llvm/ADT/PointerIntPair.h"
+#include "llvm/Support/Allocator.h"
+#include 
+#include 
+#include 
+
+namespace llvm {
+// A vector that allocates memory in pages.
+// Order is kept, but memory is allocated only when one element of the page is
+// accessed. This introduces a level of indirection, but it is useful when you
+// have a sparsely initialised vector where the full size is allocated upfront
+// with the default constructor and elements are initialised later, on first
+// access.
+//
+// Notice that this does not have iterators, because if you
+// have iterators it probably means you are going to touch
+// all the memory in any case, so better use a std::vector in
+// the first place.

kuhar wrote:

nit: could you reflow this comment? The lines wrap well before the 80 character 
line limit

https://github.com/llvm/llvm-project/pull/66430
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] Introduce paged vector (PR #66430)

[Jakub Kuderski via cfe-commits]

@@ -0,0 +1,322 @@
+//===- llvm/ADT/PagedVector.h - 'Lazyly allocated' vectors *- 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
+//
+//===--===//
+//
+// This file defines the PagedVector class.
+//
+//===--===//
+#ifndef LLVM_ADT_PAGEDVECTOR_H
+#define LLVM_ADT_PAGEDVECTOR_H
+
+#include "llvm/ADT/PointerIntPair.h"
+#include "llvm/Support/Allocator.h"
+#include 
+#include 
+#include 
+
+namespace llvm {
+// A vector that allocates memory in pages.
+// Order is kept, but memory is allocated only when one element of the page is
+// accessed. This introduces a level of indirection, but it is useful when you
+// have a sparsely initialised vector where the full size is allocated upfront
+// with the default constructor and elements are initialised later, on first
+// access.
+//
+// Notice that this does not have iterators, because if you
+// have iterators it probably means you are going to touch
+// all the memory in any case, so better use a std::vector in
+// the first place.
+//
+// Pages are allocated in SLAB_SIZE chunks, using the BumpPtrAllocator.
+template 
+class PagedVector {
+  static_assert(PAGE_SIZE > 0, "PAGE_SIZE must be greater than 0. Most likely "

kuhar wrote:

If we assert that page size is > 2, we can also use `IntPointerPair` for 
invalid pages, no? Maybe just enforce the minimum size of 16? This would allow 
us to get rid of those reinterpret casts.

https://github.com/llvm/llvm-project/pull/66430
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] Introduce paged vector (PR #66430)

[Jakub Kuderski via cfe-commits]

https://github.com/kuhar commented:

Thanks for all the fixes, this is looking very good. Did another pass and left 
some local suggestions.

https://github.com/llvm/llvm-project/pull/66430
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] Introduce paged vector (PR #66430)

[Jakub Kuderski via cfe-commits]

@@ -0,0 +1,322 @@
+//===- llvm/ADT/PagedVector.h - 'Lazyly allocated' vectors *- 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
+//
+//===--===//
+//
+// This file defines the PagedVector class.
+//
+//===--===//
+#ifndef LLVM_ADT_PAGEDVECTOR_H
+#define LLVM_ADT_PAGEDVECTOR_H
+
+#include "llvm/ADT/PointerIntPair.h"
+#include "llvm/Support/Allocator.h"
+#include 
+#include 
+#include 
+
+namespace llvm {
+// A vector that allocates memory in pages.
+// Order is kept, but memory is allocated only when one element of the page is
+// accessed. This introduces a level of indirection, but it is useful when you
+// have a sparsely initialised vector where the full size is allocated upfront
+// with the default constructor and elements are initialised later, on first
+// access.
+//
+// Notice that this does not have iterators, because if you
+// have iterators it probably means you are going to touch
+// all the memory in any case, so better use a std::vector in
+// the first place.
+//
+// Pages are allocated in SLAB_SIZE chunks, using the BumpPtrAllocator.
+template 
+class PagedVector {
+  static_assert(PAGE_SIZE > 0, "PAGE_SIZE must be greater than 0. Most likely "
+   "you want it to be greater than 16.");
+  // The actual number of element in the vector which can be accessed.
+  std::size_t Size = 0;
+
+  // The position of the initial element of the page in the Data vector.
+  // Pages are allocated contiguously in the Data vector.
+  mutable std::vector PageToDataIdx;
+  // Actual page data. All the page elements are added to this vector on the
+  // first access of any of the elements of the page. Elements default
+  // constructed and elements of the page are stored contiguously. The order of
+  // the elements however depends on the order of access of the pages.
+  PointerIntPair Allocator;
+
+  constexpr static uintptr_t InvalidPage = SIZE_MAX;
+
+public:
+  using value_type = T;
+
+  // Default constructor. We build our own allocator.
+  PagedVector() : Allocator(new BumpPtrAllocator, true) {}
+  PagedVector(BumpPtrAllocator *A) : Allocator(A, false) {}
+
+  ~PagedVector() {
+// If we own the allocator, delete it.
+if (Allocator.getInt() == true)
+  delete Allocator.getPointer();
+  }
+
+  // Lookup an element at position i.
+  // If the associated page is not filled, it will be filled with default
+  // constructed elements. If the associated page is filled, return the 
element.
+  T [](std::size_t Index) const {
+assert(Index < Size);
+assert(Index / PAGE_SIZE < PageToDataIdx.size());
+uintptr_t  = PageToDataIdx[Index / PAGE_SIZE];
+// If the page was not yet allocated, allocate it.
+if (PagePtr == InvalidPage) {
+  T *NewPagePtr = Allocator.getPointer()->template Allocate(PAGE_SIZE);
+  // We need to invoke the default constructor on all the elements of the
+  // page.
+  for (std::size_t I = 0; I < PAGE_SIZE; ++I)
+new (NewPagePtr + I) T();
+
+  PagePtr = reinterpret_cast(NewPagePtr);
+}
+// Dereference the element in the page.
+return *((Index % PAGE_SIZE) + reinterpret_cast(PagePtr));
+  }
+
+  // Return the capacity of the vector. I.e. the maximum size it can be 
expanded
+  // to with the resize method without allocating more pages.
+  [[nodiscard]] std::size_t capacity() const {
+return PageToDataIdx.size() * PAGE_SIZE;
+  }
+
+  // Return the size of the vector. I.e. the maximum index that can be
+  // accessed, i.e. the maximum value which was used as argument of the
+  // resize method.
+  [[nodiscard]] std::size_t size() const { return Size; }
+
+  // Expands the vector to the given NewSize number of elements.
+  // If the vector was smaller, allocates new pages as needed.
+  // It should be called only with NewSize >= Size.
+  void resize(std::size_t NewSize) {
+// Handle shrink case: delete the pages and update the size.
+if (NewSize < Size) {
+  std::size_t NewLastPage = (NewSize - 1) / PAGE_SIZE;
+  for (std::size_t I = NewLastPage + 1; I < PageToDataIdx.size(); ++I) {
+uintptr_t PagePtr = PageToDataIdx[I];
+if (PagePtr == InvalidPage)
+  continue;
+T *Page = reinterpret_cast(PagePtr);
+// We need to invoke the destructor on all the elements of the page.
+for (std::size_t J = 0; J < PAGE_SIZE; ++J)
+  Page[J].~T();
+Allocator.getPointer()->Deallocate(Page);
+  }
+  // Delete the extra ones in the new last page.
+  uintptr_t PagePtr = PageToDataIdx[NewLastPage];
+  if (PagePtr != InvalidPage) {
+T *Page = reinterpret_cast(PagePtr);
+// If 

[clang] Introduce paged vector (PR #66430)

[Jakub Kuderski via cfe-commits]

@@ -0,0 +1,322 @@
+//===- llvm/ADT/PagedVector.h - 'Lazyly allocated' vectors *- 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
+//
+//===--===//
+//
+// This file defines the PagedVector class.
+//
+//===--===//
+#ifndef LLVM_ADT_PAGEDVECTOR_H
+#define LLVM_ADT_PAGEDVECTOR_H
+
+#include "llvm/ADT/PointerIntPair.h"
+#include "llvm/Support/Allocator.h"
+#include 
+#include 
+#include 
+
+namespace llvm {
+// A vector that allocates memory in pages.
+// Order is kept, but memory is allocated only when one element of the page is
+// accessed. This introduces a level of indirection, but it is useful when you
+// have a sparsely initialised vector where the full size is allocated upfront
+// with the default constructor and elements are initialised later, on first
+// access.
+//
+// Notice that this does not have iterators, because if you
+// have iterators it probably means you are going to touch
+// all the memory in any case, so better use a std::vector in
+// the first place.
+//
+// Pages are allocated in SLAB_SIZE chunks, using the BumpPtrAllocator.
+template 
+class PagedVector {
+  static_assert(PAGE_SIZE > 0, "PAGE_SIZE must be greater than 0. Most likely "
+   "you want it to be greater than 16.");
+  // The actual number of element in the vector which can be accessed.
+  std::size_t Size = 0;
+
+  // The position of the initial element of the page in the Data vector.
+  // Pages are allocated contiguously in the Data vector.
+  mutable std::vector PageToDataIdx;
+  // Actual page data. All the page elements are added to this vector on the
+  // first access of any of the elements of the page. Elements default
+  // constructed and elements of the page are stored contiguously. The order of
+  // the elements however depends on the order of access of the pages.
+  PointerIntPair Allocator;
+
+  constexpr static uintptr_t InvalidPage = SIZE_MAX;
+
+public:
+  using value_type = T;
+
+  // Default constructor. We build our own allocator.

kuhar wrote:

Maybe explain the value of the `bool` in `Allocator`:
```suggestion
  // Default constructor. We build our own allocator and mark it as such with 
`true` in the second pair element.
```

https://github.com/llvm/llvm-project/pull/66430
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] Introduce paged vector (PR #66430)

[Jakub Kuderski via cfe-commits]

@@ -0,0 +1,322 @@
+//===- llvm/ADT/PagedVector.h - 'Lazyly allocated' vectors *- 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
+//
+//===--===//
+//
+// This file defines the PagedVector class.
+//
+//===--===//
+#ifndef LLVM_ADT_PAGEDVECTOR_H
+#define LLVM_ADT_PAGEDVECTOR_H
+
+#include "llvm/ADT/PointerIntPair.h"
+#include "llvm/Support/Allocator.h"
+#include 
+#include 
+#include 
+
+namespace llvm {
+// A vector that allocates memory in pages.
+// Order is kept, but memory is allocated only when one element of the page is
+// accessed. This introduces a level of indirection, but it is useful when you
+// have a sparsely initialised vector where the full size is allocated upfront
+// with the default constructor and elements are initialised later, on first
+// access.
+//
+// Notice that this does not have iterators, because if you
+// have iterators it probably means you are going to touch
+// all the memory in any case, so better use a std::vector in
+// the first place.
+//
+// Pages are allocated in SLAB_SIZE chunks, using the BumpPtrAllocator.
+template 

kuhar wrote:

nit: I looked at other code under ADT and believe that we use ThisCase for 
template arguments. Could you update the second argument to `PageSize`?

https://github.com/llvm/llvm-project/pull/66430
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] Introduce paged vector (PR #66430)

[Jakub Kuderski via cfe-commits]

@@ -1625,6 +1625,38 @@ SmallVector has grown a few other minor advantages over 
std::vector, causing
and is no longer "private to the implementation". A name like
``SmallVectorHeader`` might be more appropriate.
 
+.. _dss_pagedvector:
+
+llvm/ADT/PagedVector.h
+^^
+
+``PagedVector`` is a random access container that allocates
+(PageSize) elements of type Type when the first element of a page is accessed
+via the ``operator[]``.  This is useful for the case in which the number of
+elements is known in advance and their actual initialization is expensive and
+sparse so that it's only done lazily when the element is accessed. When the
+number of used pages is small significant memory savings can be achieved.
+
+The main advantage is that a ``PagedVector`` allows to delay the actual 
allocation
+of the page until it's needed, at the extra cost of one integer per page and 
one
+extra indirection when accessing elements with their positional index. 
+
+In order to maximise the memory footprint of this container, it's important to
+balance the PageSize so that it's not too small (otherwise the overhead of the
+integer per page might become too high) and not too big (otherwise the memory 
is
+wasted if the page is not fully used).
+
+Moreover, while retaining the oder of the elements based on their insertion

kuhar wrote:

```suggestion
Moreover, while retaining the order of the elements based on their insertion
```

https://github.com/llvm/llvm-project/pull/66430
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] Introduce paged vector (PR #66430)

[Jakub Kuderski via cfe-commits]

https://github.com/kuhar resolved 
https://github.com/llvm/llvm-project/pull/66430
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] Introduce paged vector (PR #66430)

[Jakub Kuderski via cfe-commits]

@@ -0,0 +1,301 @@
+//===- llvm/ADT/PagedVector.h - 'Lazyly allocated' vectors *- 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
+//
+//===--===//
+//
+// This file defines the PagedVector class.
+//
+//===--===//
+#ifndef LLVM_ADT_PAGEDVECTOR_H
+#define LLVM_ADT_PAGEDVECTOR_H
+
+#include "llvm/Support/Allocator.h"
+#include 
+#include 
+#include 
+
+namespace llvm {
+// A vector that allocates memory in pages.
+// Order is kept, but memory is allocated only when one element of the page is
+// accessed. This introduces a level of indirection, but it is useful when you
+// have a sparsely initialised vector where the full size is allocated upfront
+// with the default constructor and elements are initialised later, on first
+// access.
+//
+// Notice that this does not have iterators, because if you
+// have iterators it probably means you are going to touch
+// all the memory in any case, so better use a std::vector in
+// the first place.
+//
+// Pages are allocated in SLAB_SIZE chunks, using the BumpPtrAllocator.
+template 
+class PagedVector {
+  static_assert(PAGE_SIZE > 0, "PAGE_SIZE must be greater than 0. Most likely "
+   "you want it to be greater than 16.");
+  // The actual number of element in the vector which can be accessed.
+  std::size_t Size = 0;
+
+  // The position of the initial element of the page in the Data vector.
+  // Pages are allocated contiguously in the Data vector.
+  mutable std::vector PageToDataIdx;
+  // Actual page data. All the page elements are added to this vector on the
+  // first access of any of the elements of the page. Elements default
+  // constructed and elements of the page are stored contiguously. The order of
+  // the elements however depends on the order of access of the pages.
+  uintptr_t Allocator = 0;
+
+  constexpr static T *invalidPage() { return reinterpret_cast(SIZE_MAX); }
+
+public:
+  // Default constructor. We build our own allocator.
+  PagedVector()
+  : Allocator(reinterpret_cast(new BumpPtrAllocator) | 0x1) {}
+  PagedVector(BumpPtrAllocator *A)
+  : Allocator(reinterpret_cast(A)) {}
+
+  ~PagedVector() {
+// If we own the allocator, delete it.
+if (Allocator & 0x1) {
+  delete getAllocator();
+}
+  }
+
+  // Get the allocator.
+  BumpPtrAllocator *getAllocator() const {
+return reinterpret_cast(Allocator & ~0x1);
+  }
+  // Lookup an element at position Index.
+  T [](std::size_t Index) const { return at(Index); }
+
+  // Lookup an element at position i.
+  // If the associated page is not filled, it will be filled with default
+  // constructed elements. If the associated page is filled, return the 
element.
+  T (std::size_t Index) const {
+assert(Index < Size);
+assert(Index / PAGE_SIZE < PageToDataIdx.size());
+auto * = PageToDataIdx[Index / PAGE_SIZE];
+// If the page was not yet allocated, allocate it.
+if (PagePtr == invalidPage()) {
+  PagePtr = getAllocator()->template Allocate(PAGE_SIZE);
+  // We need to invoke the default constructor on all the elements of the
+  // page.
+  for (std::size_t I = 0; I < PAGE_SIZE; ++I) {
+new (PagePtr + I) T();
+  }
+}
+// Dereference the element in the page.
+return *((Index % PAGE_SIZE) + PagePtr);
+  }
+
+  // Return the capacity of the vector. I.e. the maximum size it can be 
expanded
+  // to with the expand method without allocating more pages.
+  std::size_t capacity() const { return PageToDataIdx.size() * PAGE_SIZE; }
+
+  // Return the size of the vector. I.e. the maximum index that can be
+  // accessed, i.e. the maximum value which was used as argument of the
+  // expand method.
+  std::size_t size() const { return Size; }
+
+  // Expands the vector to the given NewSize number of elements.
+  // If the vector was smaller, allocates new pages as needed.
+  // It should be called only with NewSize >= Size.
+  void expand(std::size_t NewSize) {
+// You cannot shrink the vector, otherwise
+// one would have to invalidate contents which is expensive and
+// while giving the false hope that the resize is cheap.
+if (NewSize <= Size) {
+  return;
+}
+// If the capacity is enough, just update the size and continue
+// with the currently allocated pages.
+if (NewSize <= capacity()) {
+  Size = NewSize;
+  return;
+}
+// The number of pages to allocate. The Remainder is calculated
+// for the case in which the NewSize is not a multiple of PAGE_SIZE.
+// In that case we need one more page.
+auto Pages = NewSize / PAGE_SIZE;
+auto Remainder = NewSize % PAGE_SIZE;
+if 

[clang] Introduce paged vector (PR #66430)

[Jakub Kuderski via cfe-commits]

@@ -0,0 +1,301 @@
+//===- llvm/ADT/PagedVector.h - 'Lazyly allocated' vectors *- 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
+//
+//===--===//
+//
+// This file defines the PagedVector class.
+//
+//===--===//
+#ifndef LLVM_ADT_PAGEDVECTOR_H
+#define LLVM_ADT_PAGEDVECTOR_H
+
+#include "llvm/Support/Allocator.h"
+#include 
+#include 
+#include 
+
+namespace llvm {
+// A vector that allocates memory in pages.
+// Order is kept, but memory is allocated only when one element of the page is
+// accessed. This introduces a level of indirection, but it is useful when you
+// have a sparsely initialised vector where the full size is allocated upfront
+// with the default constructor and elements are initialised later, on first
+// access.
+//
+// Notice that this does not have iterators, because if you
+// have iterators it probably means you are going to touch
+// all the memory in any case, so better use a std::vector in
+// the first place.
+//
+// Pages are allocated in SLAB_SIZE chunks, using the BumpPtrAllocator.
+template 
+class PagedVector {
+  static_assert(PAGE_SIZE > 0, "PAGE_SIZE must be greater than 0. Most likely "
+   "you want it to be greater than 16.");
+  // The actual number of element in the vector which can be accessed.
+  std::size_t Size = 0;
+
+  // The position of the initial element of the page in the Data vector.
+  // Pages are allocated contiguously in the Data vector.
+  mutable std::vector PageToDataIdx;
+  // Actual page data. All the page elements are added to this vector on the
+  // first access of any of the elements of the page. Elements default
+  // constructed and elements of the page are stored contiguously. The order of
+  // the elements however depends on the order of access of the pages.
+  uintptr_t Allocator = 0;
+
+  constexpr static T *invalidPage() { return reinterpret_cast(SIZE_MAX); }
+
+public:
+  // Default constructor. We build our own allocator.
+  PagedVector()
+  : Allocator(reinterpret_cast(new BumpPtrAllocator) | 0x1) {}
+  PagedVector(BumpPtrAllocator *A)
+  : Allocator(reinterpret_cast(A)) {}
+
+  ~PagedVector() {
+// If we own the allocator, delete it.
+if (Allocator & 0x1) {
+  delete getAllocator();
+}
+  }
+
+  // Get the allocator.
+  BumpPtrAllocator *getAllocator() const {
+return reinterpret_cast(Allocator & ~0x1);
+  }
+  // Lookup an element at position Index.
+  T [](std::size_t Index) const { return at(Index); }
+
+  // Lookup an element at position i.
+  // If the associated page is not filled, it will be filled with default
+  // constructed elements. If the associated page is filled, return the 
element.
+  T (std::size_t Index) const {
+assert(Index < Size);
+assert(Index / PAGE_SIZE < PageToDataIdx.size());
+auto * = PageToDataIdx[Index / PAGE_SIZE];
+// If the page was not yet allocated, allocate it.
+if (PagePtr == invalidPage()) {
+  PagePtr = getAllocator()->template Allocate(PAGE_SIZE);
+  // We need to invoke the default constructor on all the elements of the
+  // page.
+  for (std::size_t I = 0; I < PAGE_SIZE; ++I) {
+new (PagePtr + I) T();
+  }
+}
+// Dereference the element in the page.
+return *((Index % PAGE_SIZE) + PagePtr);
+  }
+
+  // Return the capacity of the vector. I.e. the maximum size it can be 
expanded
+  // to with the expand method without allocating more pages.
+  std::size_t capacity() const { return PageToDataIdx.size() * PAGE_SIZE; }
+
+  // Return the size of the vector. I.e. the maximum index that can be
+  // accessed, i.e. the maximum value which was used as argument of the
+  // expand method.
+  std::size_t size() const { return Size; }
+
+  // Expands the vector to the given NewSize number of elements.
+  // If the vector was smaller, allocates new pages as needed.
+  // It should be called only with NewSize >= Size.
+  void expand(std::size_t NewSize) {
+// You cannot shrink the vector, otherwise
+// one would have to invalidate contents which is expensive and
+// while giving the false hope that the resize is cheap.
+if (NewSize <= Size) {
+  return;
+}
+// If the capacity is enough, just update the size and continue
+// with the currently allocated pages.
+if (NewSize <= capacity()) {
+  Size = NewSize;
+  return;
+}
+// The number of pages to allocate. The Remainder is calculated
+// for the case in which the NewSize is not a multiple of PAGE_SIZE.
+// In that case we need one more page.
+auto Pages = NewSize / PAGE_SIZE;
+auto Remainder = NewSize % PAGE_SIZE;

[clang] Introduce paged vector (PR #66430)

[Jakub Kuderski via cfe-commits]

@@ -0,0 +1,301 @@
+//===- llvm/ADT/PagedVector.h - 'Lazyly allocated' vectors *- 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
+//
+//===--===//
+//
+// This file defines the PagedVector class.
+//
+//===--===//
+#ifndef LLVM_ADT_PAGEDVECTOR_H
+#define LLVM_ADT_PAGEDVECTOR_H
+
+#include "llvm/Support/Allocator.h"
+#include 
+#include 
+#include 
+
+namespace llvm {
+// A vector that allocates memory in pages.
+// Order is kept, but memory is allocated only when one element of the page is
+// accessed. This introduces a level of indirection, but it is useful when you
+// have a sparsely initialised vector where the full size is allocated upfront
+// with the default constructor and elements are initialised later, on first
+// access.
+//
+// Notice that this does not have iterators, because if you
+// have iterators it probably means you are going to touch
+// all the memory in any case, so better use a std::vector in
+// the first place.
+//
+// Pages are allocated in SLAB_SIZE chunks, using the BumpPtrAllocator.
+template 
+class PagedVector {
+  static_assert(PAGE_SIZE > 0, "PAGE_SIZE must be greater than 0. Most likely "
+   "you want it to be greater than 16.");
+  // The actual number of element in the vector which can be accessed.
+  std::size_t Size = 0;
+
+  // The position of the initial element of the page in the Data vector.
+  // Pages are allocated contiguously in the Data vector.
+  mutable std::vector PageToDataIdx;
+  // Actual page data. All the page elements are added to this vector on the
+  // first access of any of the elements of the page. Elements default
+  // constructed and elements of the page are stored contiguously. The order of
+  // the elements however depends on the order of access of the pages.
+  uintptr_t Allocator = 0;
+
+  constexpr static T *invalidPage() { return reinterpret_cast(SIZE_MAX); }
+
+public:
+  // Default constructor. We build our own allocator.
+  PagedVector()
+  : Allocator(reinterpret_cast(new BumpPtrAllocator) | 0x1) {}
+  PagedVector(BumpPtrAllocator *A)
+  : Allocator(reinterpret_cast(A)) {}
+
+  ~PagedVector() {
+// If we own the allocator, delete it.
+if (Allocator & 0x1) {
+  delete getAllocator();
+}
+  }
+
+  // Get the allocator.
+  BumpPtrAllocator *getAllocator() const {
+return reinterpret_cast(Allocator & ~0x1);
+  }
+  // Lookup an element at position Index.
+  T [](std::size_t Index) const { return at(Index); }
+
+  // Lookup an element at position i.
+  // If the associated page is not filled, it will be filled with default
+  // constructed elements. If the associated page is filled, return the 
element.
+  T (std::size_t Index) const {
+assert(Index < Size);
+assert(Index / PAGE_SIZE < PageToDataIdx.size());
+auto * = PageToDataIdx[Index / PAGE_SIZE];
+// If the page was not yet allocated, allocate it.
+if (PagePtr == invalidPage()) {
+  PagePtr = getAllocator()->template Allocate(PAGE_SIZE);
+  // We need to invoke the default constructor on all the elements of the
+  // page.
+  for (std::size_t I = 0; I < PAGE_SIZE; ++I) {
+new (PagePtr + I) T();
+  }
+}
+// Dereference the element in the page.
+return *((Index % PAGE_SIZE) + PagePtr);
+  }
+
+  // Return the capacity of the vector. I.e. the maximum size it can be 
expanded
+  // to with the expand method without allocating more pages.
+  std::size_t capacity() const { return PageToDataIdx.size() * PAGE_SIZE; }
+
+  // Return the size of the vector. I.e. the maximum index that can be
+  // accessed, i.e. the maximum value which was used as argument of the
+  // expand method.
+  std::size_t size() const { return Size; }
+
+  // Expands the vector to the given NewSize number of elements.
+  // If the vector was smaller, allocates new pages as needed.
+  // It should be called only with NewSize >= Size.
+  void expand(std::size_t NewSize) {
+// You cannot shrink the vector, otherwise
+// one would have to invalidate contents which is expensive and
+// while giving the false hope that the resize is cheap.
+if (NewSize <= Size) {
+  return;
+}
+// If the capacity is enough, just update the size and continue
+// with the currently allocated pages.
+if (NewSize <= capacity()) {
+  Size = NewSize;
+  return;
+}
+// The number of pages to allocate. The Remainder is calculated
+// for the case in which the NewSize is not a multiple of PAGE_SIZE.
+// In that case we need one more page.
+auto Pages = NewSize / PAGE_SIZE;
+auto Remainder = NewSize % PAGE_SIZE;
+if 

[clang] Introduce paged vector (PR #66430)

[Jakub Kuderski via cfe-commits]

@@ -0,0 +1,301 @@
+//===- llvm/ADT/PagedVector.h - 'Lazyly allocated' vectors *- 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
+//
+//===--===//
+//
+// This file defines the PagedVector class.
+//
+//===--===//
+#ifndef LLVM_ADT_PAGEDVECTOR_H
+#define LLVM_ADT_PAGEDVECTOR_H
+
+#include "llvm/Support/Allocator.h"
+#include 
+#include 
+#include 
+
+namespace llvm {
+// A vector that allocates memory in pages.
+// Order is kept, but memory is allocated only when one element of the page is
+// accessed. This introduces a level of indirection, but it is useful when you
+// have a sparsely initialised vector where the full size is allocated upfront
+// with the default constructor and elements are initialised later, on first
+// access.
+//
+// Notice that this does not have iterators, because if you
+// have iterators it probably means you are going to touch
+// all the memory in any case, so better use a std::vector in
+// the first place.
+//
+// Pages are allocated in SLAB_SIZE chunks, using the BumpPtrAllocator.
+template 
+class PagedVector {
+  static_assert(PAGE_SIZE > 0, "PAGE_SIZE must be greater than 0. Most likely "
+   "you want it to be greater than 16.");
+  // The actual number of element in the vector which can be accessed.
+  std::size_t Size = 0;
+
+  // The position of the initial element of the page in the Data vector.
+  // Pages are allocated contiguously in the Data vector.
+  mutable std::vector PageToDataIdx;
+  // Actual page data. All the page elements are added to this vector on the
+  // first access of any of the elements of the page. Elements default
+  // constructed and elements of the page are stored contiguously. The order of
+  // the elements however depends on the order of access of the pages.
+  uintptr_t Allocator = 0;
+
+  constexpr static T *invalidPage() { return reinterpret_cast(SIZE_MAX); }
+
+public:
+  // Default constructor. We build our own allocator.
+  PagedVector()
+  : Allocator(reinterpret_cast(new BumpPtrAllocator) | 0x1) {}
+  PagedVector(BumpPtrAllocator *A)
+  : Allocator(reinterpret_cast(A)) {}
+
+  ~PagedVector() {
+// If we own the allocator, delete it.
+if (Allocator & 0x1) {
+  delete getAllocator();
+}
+  }
+
+  // Get the allocator.
+  BumpPtrAllocator *getAllocator() const {
+return reinterpret_cast(Allocator & ~0x1);
+  }
+  // Lookup an element at position Index.
+  T [](std::size_t Index) const { return at(Index); }
+
+  // Lookup an element at position i.
+  // If the associated page is not filled, it will be filled with default
+  // constructed elements. If the associated page is filled, return the 
element.
+  T (std::size_t Index) const {
+assert(Index < Size);
+assert(Index / PAGE_SIZE < PageToDataIdx.size());
+auto * = PageToDataIdx[Index / PAGE_SIZE];
+// If the page was not yet allocated, allocate it.
+if (PagePtr == invalidPage()) {
+  PagePtr = getAllocator()->template Allocate(PAGE_SIZE);
+  // We need to invoke the default constructor on all the elements of the
+  // page.
+  for (std::size_t I = 0; I < PAGE_SIZE; ++I) {
+new (PagePtr + I) T();
+  }
+}
+// Dereference the element in the page.
+return *((Index % PAGE_SIZE) + PagePtr);
+  }
+
+  // Return the capacity of the vector. I.e. the maximum size it can be 
expanded
+  // to with the expand method without allocating more pages.
+  std::size_t capacity() const { return PageToDataIdx.size() * PAGE_SIZE; }
+
+  // Return the size of the vector. I.e. the maximum index that can be
+  // accessed, i.e. the maximum value which was used as argument of the
+  // expand method.
+  std::size_t size() const { return Size; }
+
+  // Expands the vector to the given NewSize number of elements.
+  // If the vector was smaller, allocates new pages as needed.
+  // It should be called only with NewSize >= Size.
+  void expand(std::size_t NewSize) {
+// You cannot shrink the vector, otherwise
+// one would have to invalidate contents which is expensive and
+// while giving the false hope that the resize is cheap.
+if (NewSize <= Size) {
+  return;
+}
+// If the capacity is enough, just update the size and continue
+// with the currently allocated pages.
+if (NewSize <= capacity()) {
+  Size = NewSize;
+  return;
+}
+// The number of pages to allocate. The Remainder is calculated
+// for the case in which the NewSize is not a multiple of PAGE_SIZE.
+// In that case we need one more page.
+auto Pages = NewSize / PAGE_SIZE;
+auto Remainder = NewSize % PAGE_SIZE;
+if 

[clang] Introduce paged vector (PR #66430)

[Jakub Kuderski via cfe-commits]

@@ -0,0 +1,301 @@
+//===- llvm/ADT/PagedVector.h - 'Lazyly allocated' vectors *- 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
+//
+//===--===//
+//
+// This file defines the PagedVector class.
+//
+//===--===//
+#ifndef LLVM_ADT_PAGEDVECTOR_H
+#define LLVM_ADT_PAGEDVECTOR_H
+
+#include "llvm/Support/Allocator.h"
+#include 
+#include 
+#include 
+
+namespace llvm {
+// A vector that allocates memory in pages.
+// Order is kept, but memory is allocated only when one element of the page is
+// accessed. This introduces a level of indirection, but it is useful when you
+// have a sparsely initialised vector where the full size is allocated upfront
+// with the default constructor and elements are initialised later, on first
+// access.
+//
+// Notice that this does not have iterators, because if you
+// have iterators it probably means you are going to touch
+// all the memory in any case, so better use a std::vector in
+// the first place.
+//
+// Pages are allocated in SLAB_SIZE chunks, using the BumpPtrAllocator.
+template 
+class PagedVector {
+  static_assert(PAGE_SIZE > 0, "PAGE_SIZE must be greater than 0. Most likely "
+   "you want it to be greater than 16.");
+  // The actual number of element in the vector which can be accessed.
+  std::size_t Size = 0;
+
+  // The position of the initial element of the page in the Data vector.
+  // Pages are allocated contiguously in the Data vector.
+  mutable std::vector PageToDataIdx;
+  // Actual page data. All the page elements are added to this vector on the
+  // first access of any of the elements of the page. Elements default
+  // constructed and elements of the page are stored contiguously. The order of
+  // the elements however depends on the order of access of the pages.
+  uintptr_t Allocator = 0;
+
+  constexpr static T *invalidPage() { return reinterpret_cast(SIZE_MAX); }
+
+public:
+  // Default constructor. We build our own allocator.
+  PagedVector()
+  : Allocator(reinterpret_cast(new BumpPtrAllocator) | 0x1) {}
+  PagedVector(BumpPtrAllocator *A)
+  : Allocator(reinterpret_cast(A)) {}
+
+  ~PagedVector() {
+// If we own the allocator, delete it.
+if (Allocator & 0x1) {
+  delete getAllocator();
+}
+  }
+
+  // Get the allocator.
+  BumpPtrAllocator *getAllocator() const {
+return reinterpret_cast(Allocator & ~0x1);
+  }
+  // Lookup an element at position Index.
+  T [](std::size_t Index) const { return at(Index); }
+
+  // Lookup an element at position i.
+  // If the associated page is not filled, it will be filled with default
+  // constructed elements. If the associated page is filled, return the 
element.
+  T (std::size_t Index) const {
+assert(Index < Size);
+assert(Index / PAGE_SIZE < PageToDataIdx.size());
+auto * = PageToDataIdx[Index / PAGE_SIZE];
+// If the page was not yet allocated, allocate it.
+if (PagePtr == invalidPage()) {
+  PagePtr = getAllocator()->template Allocate(PAGE_SIZE);
+  // We need to invoke the default constructor on all the elements of the
+  // page.
+  for (std::size_t I = 0; I < PAGE_SIZE; ++I) {
+new (PagePtr + I) T();
+  }
+}
+// Dereference the element in the page.
+return *((Index % PAGE_SIZE) + PagePtr);
+  }
+
+  // Return the capacity of the vector. I.e. the maximum size it can be 
expanded
+  // to with the expand method without allocating more pages.
+  std::size_t capacity() const { return PageToDataIdx.size() * PAGE_SIZE; }
+
+  // Return the size of the vector. I.e. the maximum index that can be
+  // accessed, i.e. the maximum value which was used as argument of the
+  // expand method.
+  std::size_t size() const { return Size; }
+
+  // Expands the vector to the given NewSize number of elements.
+  // If the vector was smaller, allocates new pages as needed.
+  // It should be called only with NewSize >= Size.
+  void expand(std::size_t NewSize) {
+// You cannot shrink the vector, otherwise
+// one would have to invalidate contents which is expensive and
+// while giving the false hope that the resize is cheap.
+if (NewSize <= Size) {
+  return;
+}
+// If the capacity is enough, just update the size and continue
+// with the currently allocated pages.
+if (NewSize <= capacity()) {

kuhar wrote:

Could we set `Size = NewSize` before this `if` to handle both outcomes?

https://github.com/llvm/llvm-project/pull/66430
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] Introduce paged vector (PR #66430)

[Jakub Kuderski via cfe-commits]

@@ -0,0 +1,301 @@
+//===- llvm/ADT/PagedVector.h - 'Lazyly allocated' vectors *- 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
+//
+//===--===//
+//
+// This file defines the PagedVector class.
+//
+//===--===//
+#ifndef LLVM_ADT_PAGEDVECTOR_H
+#define LLVM_ADT_PAGEDVECTOR_H
+
+#include "llvm/Support/Allocator.h"
+#include 
+#include 
+#include 
+
+namespace llvm {
+// A vector that allocates memory in pages.
+// Order is kept, but memory is allocated only when one element of the page is
+// accessed. This introduces a level of indirection, but it is useful when you
+// have a sparsely initialised vector where the full size is allocated upfront
+// with the default constructor and elements are initialised later, on first
+// access.
+//
+// Notice that this does not have iterators, because if you
+// have iterators it probably means you are going to touch
+// all the memory in any case, so better use a std::vector in
+// the first place.
+//
+// Pages are allocated in SLAB_SIZE chunks, using the BumpPtrAllocator.
+template 
+class PagedVector {
+  static_assert(PAGE_SIZE > 0, "PAGE_SIZE must be greater than 0. Most likely "
+   "you want it to be greater than 16.");
+  // The actual number of element in the vector which can be accessed.
+  std::size_t Size = 0;
+
+  // The position of the initial element of the page in the Data vector.
+  // Pages are allocated contiguously in the Data vector.
+  mutable std::vector PageToDataIdx;
+  // Actual page data. All the page elements are added to this vector on the
+  // first access of any of the elements of the page. Elements default
+  // constructed and elements of the page are stored contiguously. The order of
+  // the elements however depends on the order of access of the pages.
+  uintptr_t Allocator = 0;
+
+  constexpr static T *invalidPage() { return reinterpret_cast(SIZE_MAX); }
+
+public:
+  // Default constructor. We build our own allocator.
+  PagedVector()
+  : Allocator(reinterpret_cast(new BumpPtrAllocator) | 0x1) {}

kuhar wrote:

Could we use `PointerIntPair`?

https://github.com/llvm/llvm-project/pull/66430
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] Introduce paged vector (PR #66430)

[Jakub Kuderski via cfe-commits]

@@ -0,0 +1,301 @@
+//===- llvm/ADT/PagedVector.h - 'Lazyly allocated' vectors *- 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
+//
+//===--===//
+//
+// This file defines the PagedVector class.
+//
+//===--===//
+#ifndef LLVM_ADT_PAGEDVECTOR_H
+#define LLVM_ADT_PAGEDVECTOR_H
+
+#include "llvm/Support/Allocator.h"
+#include 
+#include 
+#include 
+
+namespace llvm {
+// A vector that allocates memory in pages.
+// Order is kept, but memory is allocated only when one element of the page is
+// accessed. This introduces a level of indirection, but it is useful when you
+// have a sparsely initialised vector where the full size is allocated upfront
+// with the default constructor and elements are initialised later, on first
+// access.
+//
+// Notice that this does not have iterators, because if you
+// have iterators it probably means you are going to touch
+// all the memory in any case, so better use a std::vector in
+// the first place.
+//
+// Pages are allocated in SLAB_SIZE chunks, using the BumpPtrAllocator.
+template 
+class PagedVector {
+  static_assert(PAGE_SIZE > 0, "PAGE_SIZE must be greater than 0. Most likely "
+   "you want it to be greater than 16.");
+  // The actual number of element in the vector which can be accessed.
+  std::size_t Size = 0;
+
+  // The position of the initial element of the page in the Data vector.
+  // Pages are allocated contiguously in the Data vector.
+  mutable std::vector PageToDataIdx;
+  // Actual page data. All the page elements are added to this vector on the
+  // first access of any of the elements of the page. Elements default
+  // constructed and elements of the page are stored contiguously. The order of
+  // the elements however depends on the order of access of the pages.
+  uintptr_t Allocator = 0;
+
+  constexpr static T *invalidPage() { return reinterpret_cast(SIZE_MAX); }

kuhar wrote:

Can we make this a constant instead of a function? Or do you see benefits of 
doing it this way?

Also, since this is not a valid pointer to `T`, what do you think of changing 
the type to `uintptr_t`?

https://github.com/llvm/llvm-project/pull/66430
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] Introduce paged vector (PR #66430)

[Jakub Kuderski via cfe-commits]

@@ -0,0 +1,301 @@
+//===- llvm/ADT/PagedVector.h - 'Lazyly allocated' vectors *- 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
+//
+//===--===//
+//
+// This file defines the PagedVector class.
+//
+//===--===//
+#ifndef LLVM_ADT_PAGEDVECTOR_H
+#define LLVM_ADT_PAGEDVECTOR_H
+
+#include "llvm/Support/Allocator.h"
+#include 
+#include 
+#include 
+
+namespace llvm {
+// A vector that allocates memory in pages.
+// Order is kept, but memory is allocated only when one element of the page is
+// accessed. This introduces a level of indirection, but it is useful when you
+// have a sparsely initialised vector where the full size is allocated upfront
+// with the default constructor and elements are initialised later, on first
+// access.
+//
+// Notice that this does not have iterators, because if you
+// have iterators it probably means you are going to touch
+// all the memory in any case, so better use a std::vector in
+// the first place.
+//
+// Pages are allocated in SLAB_SIZE chunks, using the BumpPtrAllocator.
+template 
+class PagedVector {
+  static_assert(PAGE_SIZE > 0, "PAGE_SIZE must be greater than 0. Most likely "
+   "you want it to be greater than 16.");
+  // The actual number of element in the vector which can be accessed.
+  std::size_t Size = 0;
+
+  // The position of the initial element of the page in the Data vector.
+  // Pages are allocated contiguously in the Data vector.
+  mutable std::vector PageToDataIdx;
+  // Actual page data. All the page elements are added to this vector on the
+  // first access of any of the elements of the page. Elements default
+  // constructed and elements of the page are stored contiguously. The order of
+  // the elements however depends on the order of access of the pages.
+  uintptr_t Allocator = 0;
+
+  constexpr static T *invalidPage() { return reinterpret_cast(SIZE_MAX); }
+
+public:
+  // Default constructor. We build our own allocator.
+  PagedVector()
+  : Allocator(reinterpret_cast(new BumpPtrAllocator) | 0x1) {}
+  PagedVector(BumpPtrAllocator *A)
+  : Allocator(reinterpret_cast(A)) {}
+
+  ~PagedVector() {
+// If we own the allocator, delete it.
+if (Allocator & 0x1) {
+  delete getAllocator();
+}
+  }
+
+  // Get the allocator.
+  BumpPtrAllocator *getAllocator() const {
+return reinterpret_cast(Allocator & ~0x1);
+  }
+  // Lookup an element at position Index.
+  T [](std::size_t Index) const { return at(Index); }
+
+  // Lookup an element at position i.
+  // If the associated page is not filled, it will be filled with default
+  // constructed elements. If the associated page is filled, return the 
element.
+  T (std::size_t Index) const {
+assert(Index < Size);
+assert(Index / PAGE_SIZE < PageToDataIdx.size());
+auto * = PageToDataIdx[Index / PAGE_SIZE];
+// If the page was not yet allocated, allocate it.
+if (PagePtr == invalidPage()) {
+  PagePtr = getAllocator()->template Allocate(PAGE_SIZE);
+  // We need to invoke the default constructor on all the elements of the
+  // page.
+  for (std::size_t I = 0; I < PAGE_SIZE; ++I) {
+new (PagePtr + I) T();
+  }
+}
+// Dereference the element in the page.
+return *((Index % PAGE_SIZE) + PagePtr);
+  }
+
+  // Return the capacity of the vector. I.e. the maximum size it can be 
expanded
+  // to with the expand method without allocating more pages.
+  std::size_t capacity() const { return PageToDataIdx.size() * PAGE_SIZE; }
+
+  // Return the size of the vector. I.e. the maximum index that can be
+  // accessed, i.e. the maximum value which was used as argument of the
+  // expand method.
+  std::size_t size() const { return Size; }
+
+  // Expands the vector to the given NewSize number of elements.
+  // If the vector was smaller, allocates new pages as needed.
+  // It should be called only with NewSize >= Size.
+  void expand(std::size_t NewSize) {
+// You cannot shrink the vector, otherwise
+// one would have to invalidate contents which is expensive and
+// while giving the false hope that the resize is cheap.
+if (NewSize <= Size) {
+  return;
+}
+// If the capacity is enough, just update the size and continue
+// with the currently allocated pages.
+if (NewSize <= capacity()) {
+  Size = NewSize;
+  return;
+}
+// The number of pages to allocate. The Remainder is calculated
+// for the case in which the NewSize is not a multiple of PAGE_SIZE.
+// In that case we need one more page.
+auto Pages = NewSize / PAGE_SIZE;
+auto Remainder = NewSize % PAGE_SIZE;
+if 

[clang] Introduce paged vector (PR #66430)

[Jakub Kuderski via cfe-commits]

@@ -0,0 +1,301 @@
+//===- llvm/ADT/PagedVector.h - 'Lazyly allocated' vectors *- 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
+//
+//===--===//
+//
+// This file defines the PagedVector class.
+//
+//===--===//
+#ifndef LLVM_ADT_PAGEDVECTOR_H
+#define LLVM_ADT_PAGEDVECTOR_H
+
+#include "llvm/Support/Allocator.h"
+#include 
+#include 
+#include 
+
+namespace llvm {
+// A vector that allocates memory in pages.
+// Order is kept, but memory is allocated only when one element of the page is
+// accessed. This introduces a level of indirection, but it is useful when you
+// have a sparsely initialised vector where the full size is allocated upfront
+// with the default constructor and elements are initialised later, on first
+// access.
+//
+// Notice that this does not have iterators, because if you
+// have iterators it probably means you are going to touch
+// all the memory in any case, so better use a std::vector in
+// the first place.
+//
+// Pages are allocated in SLAB_SIZE chunks, using the BumpPtrAllocator.
+template 
+class PagedVector {
+  static_assert(PAGE_SIZE > 0, "PAGE_SIZE must be greater than 0. Most likely "
+   "you want it to be greater than 16.");
+  // The actual number of element in the vector which can be accessed.
+  std::size_t Size = 0;
+
+  // The position of the initial element of the page in the Data vector.
+  // Pages are allocated contiguously in the Data vector.
+  mutable std::vector PageToDataIdx;
+  // Actual page data. All the page elements are added to this vector on the
+  // first access of any of the elements of the page. Elements default
+  // constructed and elements of the page are stored contiguously. The order of
+  // the elements however depends on the order of access of the pages.
+  uintptr_t Allocator = 0;
+
+  constexpr static T *invalidPage() { return reinterpret_cast(SIZE_MAX); }
+
+public:
+  // Default constructor. We build our own allocator.
+  PagedVector()
+  : Allocator(reinterpret_cast(new BumpPtrAllocator) | 0x1) {}
+  PagedVector(BumpPtrAllocator *A)
+  : Allocator(reinterpret_cast(A)) {}
+
+  ~PagedVector() {
+// If we own the allocator, delete it.
+if (Allocator & 0x1) {
+  delete getAllocator();
+}
+  }
+
+  // Get the allocator.
+  BumpPtrAllocator *getAllocator() const {
+return reinterpret_cast(Allocator & ~0x1);
+  }
+  // Lookup an element at position Index.
+  T [](std::size_t Index) const { return at(Index); }
+
+  // Lookup an element at position i.
+  // If the associated page is not filled, it will be filled with default
+  // constructed elements. If the associated page is filled, return the 
element.
+  T (std::size_t Index) const {
+assert(Index < Size);
+assert(Index / PAGE_SIZE < PageToDataIdx.size());
+auto * = PageToDataIdx[Index / PAGE_SIZE];
+// If the page was not yet allocated, allocate it.
+if (PagePtr == invalidPage()) {
+  PagePtr = getAllocator()->template Allocate(PAGE_SIZE);
+  // We need to invoke the default constructor on all the elements of the
+  // page.
+  for (std::size_t I = 0; I < PAGE_SIZE; ++I) {
+new (PagePtr + I) T();
+  }
+}
+// Dereference the element in the page.
+return *((Index % PAGE_SIZE) + PagePtr);
+  }
+
+  // Return the capacity of the vector. I.e. the maximum size it can be 
expanded
+  // to with the expand method without allocating more pages.
+  std::size_t capacity() const { return PageToDataIdx.size() * PAGE_SIZE; }
+
+  // Return the size of the vector. I.e. the maximum index that can be
+  // accessed, i.e. the maximum value which was used as argument of the
+  // expand method.
+  std::size_t size() const { return Size; }
+
+  // Expands the vector to the given NewSize number of elements.
+  // If the vector was smaller, allocates new pages as needed.
+  // It should be called only with NewSize >= Size.
+  void expand(std::size_t NewSize) {
+// You cannot shrink the vector, otherwise
+// one would have to invalidate contents which is expensive and
+// while giving the false hope that the resize is cheap.
+if (NewSize <= Size) {
+  return;
+}
+// If the capacity is enough, just update the size and continue
+// with the currently allocated pages.
+if (NewSize <= capacity()) {
+  Size = NewSize;
+  return;
+}
+// The number of pages to allocate. The Remainder is calculated
+// for the case in which the NewSize is not a multiple of PAGE_SIZE.
+// In that case we need one more page.
+auto Pages = NewSize / PAGE_SIZE;
+auto Remainder = NewSize % PAGE_SIZE;
+if 

[clang] Introduce paged vector (PR #66430)

[Jakub Kuderski via cfe-commits]

@@ -0,0 +1,301 @@
+//===- llvm/ADT/PagedVector.h - 'Lazyly allocated' vectors *- 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
+//
+//===--===//
+//
+// This file defines the PagedVector class.
+//
+//===--===//
+#ifndef LLVM_ADT_PAGEDVECTOR_H
+#define LLVM_ADT_PAGEDVECTOR_H
+
+#include "llvm/Support/Allocator.h"
+#include 
+#include 
+#include 
+
+namespace llvm {
+// A vector that allocates memory in pages.
+// Order is kept, but memory is allocated only when one element of the page is
+// accessed. This introduces a level of indirection, but it is useful when you
+// have a sparsely initialised vector where the full size is allocated upfront
+// with the default constructor and elements are initialised later, on first
+// access.
+//
+// Notice that this does not have iterators, because if you
+// have iterators it probably means you are going to touch
+// all the memory in any case, so better use a std::vector in
+// the first place.
+//
+// Pages are allocated in SLAB_SIZE chunks, using the BumpPtrAllocator.
+template 
+class PagedVector {
+  static_assert(PAGE_SIZE > 0, "PAGE_SIZE must be greater than 0. Most likely "
+   "you want it to be greater than 16.");
+  // The actual number of element in the vector which can be accessed.
+  std::size_t Size = 0;
+
+  // The position of the initial element of the page in the Data vector.
+  // Pages are allocated contiguously in the Data vector.
+  mutable std::vector PageToDataIdx;
+  // Actual page data. All the page elements are added to this vector on the
+  // first access of any of the elements of the page. Elements default
+  // constructed and elements of the page are stored contiguously. The order of
+  // the elements however depends on the order of access of the pages.
+  uintptr_t Allocator = 0;
+
+  constexpr static T *invalidPage() { return reinterpret_cast(SIZE_MAX); }
+
+public:
+  // Default constructor. We build our own allocator.
+  PagedVector()
+  : Allocator(reinterpret_cast(new BumpPtrAllocator) | 0x1) {}
+  PagedVector(BumpPtrAllocator *A)
+  : Allocator(reinterpret_cast(A)) {}
+
+  ~PagedVector() {
+// If we own the allocator, delete it.
+if (Allocator & 0x1) {
+  delete getAllocator();
+}
+  }
+
+  // Get the allocator.
+  BumpPtrAllocator *getAllocator() const {
+return reinterpret_cast(Allocator & ~0x1);
+  }
+  // Lookup an element at position Index.
+  T [](std::size_t Index) const { return at(Index); }
+
+  // Lookup an element at position i.
+  // If the associated page is not filled, it will be filled with default
+  // constructed elements. If the associated page is filled, return the 
element.
+  T (std::size_t Index) const {
+assert(Index < Size);
+assert(Index / PAGE_SIZE < PageToDataIdx.size());
+auto * = PageToDataIdx[Index / PAGE_SIZE];
+// If the page was not yet allocated, allocate it.
+if (PagePtr == invalidPage()) {
+  PagePtr = getAllocator()->template Allocate(PAGE_SIZE);
+  // We need to invoke the default constructor on all the elements of the
+  // page.
+  for (std::size_t I = 0; I < PAGE_SIZE; ++I) {
+new (PagePtr + I) T();
+  }
+}
+// Dereference the element in the page.
+return *((Index % PAGE_SIZE) + PagePtr);
+  }
+
+  // Return the capacity of the vector. I.e. the maximum size it can be 
expanded
+  // to with the expand method without allocating more pages.
+  std::size_t capacity() const { return PageToDataIdx.size() * PAGE_SIZE; }
+
+  // Return the size of the vector. I.e. the maximum index that can be
+  // accessed, i.e. the maximum value which was used as argument of the
+  // expand method.
+  std::size_t size() const { return Size; }
+
+  // Expands the vector to the given NewSize number of elements.
+  // If the vector was smaller, allocates new pages as needed.
+  // It should be called only with NewSize >= Size.
+  void expand(std::size_t NewSize) {
+// You cannot shrink the vector, otherwise
+// one would have to invalidate contents which is expensive and
+// while giving the false hope that the resize is cheap.
+if (NewSize <= Size) {
+  return;
+}
+// If the capacity is enough, just update the size and continue
+// with the currently allocated pages.
+if (NewSize <= capacity()) {
+  Size = NewSize;
+  return;
+}
+// The number of pages to allocate. The Remainder is calculated
+// for the case in which the NewSize is not a multiple of PAGE_SIZE.
+// In that case we need one more page.
+auto Pages = NewSize / PAGE_SIZE;
+auto Remainder = NewSize % PAGE_SIZE;
+if 

[clang] Introduce paged vector (PR #66430)

[Jakub Kuderski via cfe-commits]

@@ -0,0 +1,133 @@
+//===- llvm/ADT/PagedVector.h - 'Lazyly allocated' vectors *- 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
+//
+//===--===//
+//
+// This file defines the PagedVector class.
+//
+//===--===//
+#ifndef LLVM_ADT_PAGEDVECTOR_H
+#define LLVM_ADT_PAGEDVECTOR_H
+
+#include 
+#include 
+
+namespace llvm {
+// A vector that allocates memory in pages.
+// Order is kept, but memory is allocated only when one element of the page is
+// accessed. This introduces a level of indirection, but it is useful when you
+// have a sparsely initialised vector where the full size is allocated upfront
+// with the default constructor and elements are initialised later, on first
+// access.
+//
+// Notice that this does not have iterators, because if you
+// have iterators it probably means you are going to touch
+// all the memory in any case, so better use a std::vector in
+// the first place.
+template  class PagedVector {
+  // The actual number of element in the vector which can be accessed.
+  std::size_t Size = 0;
+  // The position of the initial element of the page in the Data vector.
+  // Pages are allocated contiguously in the Data vector.
+  mutable std::vector Lookup;
+  // Actual page data. All the page elements are added to this vector on the
+  // first access of any of the elements of the page. Elements default
+  // constructed and elements of the page are stored contiguously. The oder of
+  // the elements however depends on the order of access of the pages.
+  mutable std::vector Data;
+
+public:
+  // Lookup an element at position Index.
+  T [](std::size_t Index) const { return at(Index); }
+
+  // Lookup an element at position i.
+  // If the associated page is not filled, it will be filled with default
+  // constructed elements. If the associated page is filled, return the 
element.
+  T (std::size_t Index) const {
+assert(Index < Size);
+assert(Index / PAGE_SIZE < Lookup.size());
+auto  = Lookup[Index / PAGE_SIZE];
+// If the range is not filled, fill it
+if (PageId == -1) {
+  int OldSize = Data.size();
+  PageId = OldSize / PAGE_SIZE;
+  // Allocate the memory
+  Data.resize(OldSize + PAGE_SIZE);
+  // Fill the whole capacity with empty elements
+  for (int I = 0; I < PAGE_SIZE; ++I) {
+Data[I + OldSize] = T();
+  }
+}
+// Calculate the actual position in the Data vector
+// by taking the start of the page and adding the offset
+// in the page.
+std::size_t StoreIndex = Index % PAGE_SIZE + PAGE_SIZE * PageId;
+// Return the element
+assert(StoreIndex < Data.size());
+return Data[StoreIndex];
+  }
+
+  // Return the capacity of the vector. I.e. the maximum size it can be 
expanded
+  // to with the expand method without allocating more pages.
+  std::size_t capacity() const { return Lookup.size() * PAGE_SIZE; }
+
+  // Return the size of the vector. I.e. the maximum index that can be
+  // accessed, i.e. the maximum value which was used as argument of the
+  // expand method.
+  std::size_t size() const { return Size; }
+
+  // Expands the vector to the given NewSize number of elements.
+  // If the vector was smaller, allocates new pages as needed.
+  // It should be called only with NewSize >= Size.
+  void expand(std::size_t NewSize) {
+// You cannot shrink the vector, otherwise
+// one would have to invalidate contents which is expensive and
+// while giving the false hope that the resize is cheap.
+if (NewSize <= Size) {
+  return;
+}
+// If the capacity is enough, just update the size and continue
+// with the currently allocated pages.
+if (NewSize <= capacity()) {
+  Size = NewSize;
+  return;
+}
+// The number of pages to allocate. The Remainder is calculated
+// for the case in which the NewSize is not a multiple of PAGE_SIZE.
+// In that case we need one more page.
+auto Pages = NewSize / PAGE_SIZE;
+auto Remainder = NewSize % PAGE_SIZE;
+if (Remainder) {
+  Pages += 1;
+}
+assert(Pages > Lookup.size());
+// We use -1 to indicate that a page has not been allocated yet.
+// This cannot be 0, because 0 is a valid page id.
+// We use -1 instead of a separate bool to avoid wasting space.
+Lookup.resize(Pages, -1);
+Size = NewSize;
+  }
+
+  // Return true if the vector is empty
+  bool empty() const { return Size == 0; }
+
+  /// Clear the vector, i.e. clear the allocated pages, the whole page
+  /// lookup index and reset the size.
+  void clear() {
+Size = 0;
+Lookup.clear();
+Data.clear();
+  }
+
+  /// Return the materialised vector. 

[clang] Introduce paged vector (PR #66430)

[Jakub Kuderski via cfe-commits]

@@ -1625,6 +1625,35 @@ SmallVector has grown a few other minor advantages over 
std::vector, causing
and is no longer "private to the implementation". A name like
``SmallVectorHeader`` might be more appropriate.
 
+.. _dss_pagedvector:
+
+llvm/ADT/PagedVector.h
+^^
+
+``PagedVector`` is a random access container that allocates 
(PageSize) elements
+of type Type when the first element of a page is accessed via the 
``operator[]`` or the ``at()``
+method.  This is useful for the case in which the number of elements is known 
in advance and 
+their actual initialization is expensive and sparse so that it's only done 
lazily when the element is 
+accessed. When the number of used pages is small significant memory savings 
can be achieved.
+
+The main advantage is that a PagedVector allows to delay the actual allocation 
of the page until it's needed,
+at the extra cost of one integer per page and one extra indirection when 
accessing elements with their positional
+index. 

kuhar wrote:

Please reflow this section to fit the column limit. Your editor should be able 
to do this automatically (either built-in or via a plugin).

https://github.com/llvm/llvm-project/pull/66430
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] Introduce paged vector (PR #66430)

[Jakub Kuderski via cfe-commits]

@@ -0,0 +1,132 @@
+//===- llvm/ADT/PagedVector.h - 'Lazyly allocated' vectors *- 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
+//
+//===--===//
+//
+// This file defines the PagedVector class.
+//
+//===--===//
+#ifndef LLVM_ADT_PAGEDVECTOR_H
+#define LLVM_ADT_PAGEDVECTOR_H
+
+#include 
+#include 
+
+namespace llvm {
+// A vector that allocates memory in pages.
+// Order is kept, but memory is allocated only when one element of the page is
+// accessed. This introduces a level of indirection, but it is useful when you
+// have a sparsely initialised vector where the full size is allocated upfront
+// with the default constructor and elements are initialised later, on first
+// access.
+//
+// Notice that this does not have iterators, because if you
+// have iterators it probably means you are going to touch
+// all the memory in any case, so better use a std::vector in
+// the first place.
+template 
+class PagedVector {
+  static_assert(PAGE_SIZE > 0, "PAGE_SIZE must be greater than 0. Most likely 
you want it to be greater than 16.");

kuhar wrote:

Please run this through clang-format

https://github.com/llvm/llvm-project/pull/66430
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] Introduce paged vector (PR #66430)

[Jakub Kuderski via cfe-commits]

@@ -0,0 +1,133 @@
+//===- llvm/ADT/PagedVector.h - 'Lazyly allocated' vectors *- 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
+//
+//===--===//
+//
+// This file defines the PagedVector class.
+//
+//===--===//
+#ifndef LLVM_ADT_PAGEDVECTOR_H
+#define LLVM_ADT_PAGEDVECTOR_H
+
+#include 
+#include 
+
+namespace llvm {
+// A vector that allocates memory in pages.
+// Order is kept, but memory is allocated only when one element of the page is
+// accessed. This introduces a level of indirection, but it is useful when you
+// have a sparsely initialised vector where the full size is allocated upfront
+// with the default constructor and elements are initialised later, on first
+// access.
+//
+// Notice that this does not have iterators, because if you
+// have iterators it probably means you are going to touch
+// all the memory in any case, so better use a std::vector in
+// the first place.
+template  class PagedVector {
+  // The actual number of element in the vector which can be accessed.
+  std::size_t Size = 0;
+  // The position of the initial element of the page in the Data vector.
+  // Pages are allocated contiguously in the Data vector.
+  mutable std::vector Lookup;
+  // Actual page data. All the page elements are added to this vector on the
+  // first access of any of the elements of the page. Elements default
+  // constructed and elements of the page are stored contiguously. The oder of
+  // the elements however depends on the order of access of the pages.
+  mutable std::vector Data;
+
+public:
+  // Lookup an element at position Index.
+  T [](std::size_t Index) const { return at(Index); }
+
+  // Lookup an element at position i.
+  // If the associated page is not filled, it will be filled with default
+  // constructed elements. If the associated page is filled, return the 
element.
+  T (std::size_t Index) const {
+assert(Index < Size);
+assert(Index / PAGE_SIZE < Lookup.size());
+auto  = Lookup[Index / PAGE_SIZE];
+// If the range is not filled, fill it
+if (PageId == -1) {
+  int OldSize = Data.size();
+  PageId = OldSize / PAGE_SIZE;
+  // Allocate the memory
+  Data.resize(OldSize + PAGE_SIZE);
+  // Fill the whole capacity with empty elements
+  for (int I = 0; I < PAGE_SIZE; ++I) {
+Data[I + OldSize] = T();
+  }
+}
+// Calculate the actual position in the Data vector
+// by taking the start of the page and adding the offset
+// in the page.
+std::size_t StoreIndex = Index % PAGE_SIZE + PAGE_SIZE * PageId;
+// Return the element
+assert(StoreIndex < Data.size());
+return Data[StoreIndex];
+  }
+
+  // Return the capacity of the vector. I.e. the maximum size it can be 
expanded
+  // to with the expand method without allocating more pages.
+  std::size_t capacity() const { return Lookup.size() * PAGE_SIZE; }
+
+  // Return the size of the vector. I.e. the maximum index that can be
+  // accessed, i.e. the maximum value which was used as argument of the
+  // expand method.
+  std::size_t size() const { return Size; }
+
+  // Expands the vector to the given NewSize number of elements.
+  // If the vector was smaller, allocates new pages as needed.
+  // It should be called only with NewSize >= Size.
+  void expand(std::size_t NewSize) {
+// You cannot shrink the vector, otherwise
+// one would have to invalidate contents which is expensive and
+// while giving the false hope that the resize is cheap.
+if (NewSize <= Size) {
+  return;
+}
+// If the capacity is enough, just update the size and continue
+// with the currently allocated pages.
+if (NewSize <= capacity()) {
+  Size = NewSize;
+  return;
+}
+// The number of pages to allocate. The Remainder is calculated
+// for the case in which the NewSize is not a multiple of PAGE_SIZE.
+// In that case we need one more page.
+auto Pages = NewSize / PAGE_SIZE;
+auto Remainder = NewSize % PAGE_SIZE;
+if (Remainder) {
+  Pages += 1;
+}
+assert(Pages > Lookup.size());
+// We use -1 to indicate that a page has not been allocated yet.
+// This cannot be 0, because 0 is a valid page id.
+// We use -1 instead of a separate bool to avoid wasting space.
+Lookup.resize(Pages, -1);
+Size = NewSize;
+  }
+
+  // Return true if the vector is empty
+  bool empty() const { return Size == 0; }
+
+  /// Clear the vector, i.e. clear the allocated pages, the whole page
+  /// lookup index and reset the size.
+  void clear() {
+Size = 0;
+Lookup.clear();
+Data.clear();
+  }
+
+  /// Return the materialised vector. 

[clang] Introduce paged vector (PR #66430)

[Jakub Kuderski via cfe-commits]

https://github.com/kuhar resolved 
https://github.com/llvm/llvm-project/pull/66430
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] Introduce paged vector (PR #66430)

[Jakub Kuderski via cfe-commits]

https://github.com/kuhar resolved 
https://github.com/llvm/llvm-project/pull/66430
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] Introduce paged vector (PR #66430)

[Jakub Kuderski via cfe-commits]

https://github.com/kuhar resolved 
https://github.com/llvm/llvm-project/pull/66430
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] Introduce paged vector (PR #66430)

[Jakub Kuderski via cfe-commits]

https://github.com/kuhar resolved 
https://github.com/llvm/llvm-project/pull/66430
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] Introduce paged vector (PR #66430)

[Jakub Kuderski via cfe-commits]

https://github.com/kuhar resolved 
https://github.com/llvm/llvm-project/pull/66430
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] Introduce paged vector (PR #66430)

[Jakub Kuderski via cfe-commits]

@@ -0,0 +1,133 @@
+//===- llvm/ADT/PagedVector.h - 'Lazyly allocated' vectors *- 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
+//
+//===--===//
+//
+// This file defines the PagedVector class.
+//
+//===--===//
+#ifndef LLVM_ADT_PAGEDVECTOR_H
+#define LLVM_ADT_PAGEDVECTOR_H
+
+#include 
+#include 
+
+namespace llvm {
+// A vector that allocates memory in pages.
+// Order is kept, but memory is allocated only when one element of the page is
+// accessed. This introduces a level of indirection, but it is useful when you
+// have a sparsely initialised vector where the full size is allocated upfront
+// with the default constructor and elements are initialised later, on first
+// access.
+//
+// Notice that this does not have iterators, because if you
+// have iterators it probably means you are going to touch
+// all the memory in any case, so better use a std::vector in
+// the first place.
+template  class PagedVector {
+  // The actual number of element in the vector which can be accessed.
+  std::size_t Size = 0;
+  // The position of the initial element of the page in the Data vector.
+  // Pages are allocated contiguously in the Data vector.
+  mutable std::vector Lookup;
+  // Actual page data. All the page elements are added to this vector on the
+  // first access of any of the elements of the page. Elements default
+  // constructed and elements of the page are stored contiguously. The oder of
+  // the elements however depends on the order of access of the pages.
+  mutable std::vector Data;
+
+public:
+  // Lookup an element at position Index.
+  T [](std::size_t Index) const { return at(Index); }
+
+  // Lookup an element at position i.
+  // If the associated page is not filled, it will be filled with default
+  // constructed elements. If the associated page is filled, return the 
element.
+  T (std::size_t Index) const {
+assert(Index < Size);
+assert(Index / PAGE_SIZE < Lookup.size());
+auto  = Lookup[Index / PAGE_SIZE];
+// If the range is not filled, fill it
+if (PageId == -1) {
+  int OldSize = Data.size();
+  PageId = OldSize / PAGE_SIZE;

kuhar wrote:

Ah, right, please disregard then.

https://github.com/llvm/llvm-project/pull/66430
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] Introduce paged vector (PR #66430)

[Jakub Kuderski via cfe-commits]

kuhar wrote:

A few more questions @ktf:
1. Would it be possible to add a benchmark that compares this paged vector to 
`std::vector` and `llvm::SmallVector` for a few data types? Maybe `int`, 
`std::string`, `std::vector`. I would love to see what the performance 
characteristics are like. We have a few existing benchmarks (with google 
benchmark) in the source tree that you could start with.
2. Could we benefits from not initializing elements on resize and only on the 
first page access? I guess this would require a tri-state for `Lookup`.
3. Would it be possible to get a similar speedup by providing a custom 
allocator to `std::vector`?
4. Are there some alternative data structures that could work in your use case?

https://github.com/llvm/llvm-project/pull/66430
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] Introduce paged vector (PR #66430)

[Jakub Kuderski via cfe-commits]

@@ -0,0 +1,133 @@
+//===- llvm/ADT/PagedVector.h - 'Lazyly allocated' vectors *- 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
+//
+//===--===//
+//
+// This file defines the PagedVector class.
+//
+//===--===//
+#ifndef LLVM_ADT_PAGEDVECTOR_H
+#define LLVM_ADT_PAGEDVECTOR_H
+
+#include 
+#include 
+
+namespace llvm {
+// A vector that allocates memory in pages.
+// Order is kept, but memory is allocated only when one element of the page is
+// accessed. This introduces a level of indirection, but it is useful when you
+// have a sparsely initialised vector where the full size is allocated upfront
+// with the default constructor and elements are initialised later, on first
+// access.
+//
+// Notice that this does not have iterators, because if you
+// have iterators it probably means you are going to touch
+// all the memory in any case, so better use a std::vector in
+// the first place.
+template  class PagedVector {
+  // The actual number of element in the vector which can be accessed.
+  std::size_t Size = 0;
+  // The position of the initial element of the page in the Data vector.
+  // Pages are allocated contiguously in the Data vector.
+  mutable std::vector Lookup;
+  // Actual page data. All the page elements are added to this vector on the
+  // first access of any of the elements of the page. Elements default
+  // constructed and elements of the page are stored contiguously. The oder of
+  // the elements however depends on the order of access of the pages.
+  mutable std::vector Data;
+
+public:
+  // Lookup an element at position Index.
+  T [](std::size_t Index) const { return at(Index); }
+
+  // Lookup an element at position i.
+  // If the associated page is not filled, it will be filled with default
+  // constructed elements. If the associated page is filled, return the 
element.
+  T (std::size_t Index) const {
+assert(Index < Size);
+assert(Index / PAGE_SIZE < Lookup.size());
+auto  = Lookup[Index / PAGE_SIZE];
+// If the range is not filled, fill it
+if (PageId == -1) {
+  int OldSize = Data.size();

kuhar wrote:

size_t

https://github.com/llvm/llvm-project/pull/66430
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] Introduce paged vector (PR #66430)

[Jakub Kuderski via cfe-commits]

@@ -0,0 +1,92 @@
+//===- llvm/unittest/ADT/PagedVectorTest.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
+//
+//===--===//
+//
+// PagedVector unit tests.
+//
+//===--===//
+
+#include "llvm/ADT/PagedVector.h"
+#include "gtest/gtest.h"
+
+namespace llvm {
+TEST(PagedVectorTest, FunctionalityTest) {
+  PagedVector V;
+  EXPECT_EQ(V.empty(), true);
+
+  // Next ten numbers are 10..19
+  V.expand(2);
+  EXPECT_EQ(V.empty(), false);
+  V.expand(10);
+  V.expand(20);
+  V.expand(30);
+  EXPECT_EQ(V.materialised().size(), 0ULL);
+
+  EXPECT_EQ(V.size(), 30ULL);
+  for (int I = 0; I < 10; ++I) {
+V[I] = I;
+  }
+  for (int I = 0; I < 10; ++I) {
+EXPECT_EQ(V[I], I);
+  }
+  EXPECT_EQ(V.materialised().size(), 10ULL);
+  for (int I = 20; I < 30; ++I) {
+V[I] = I;
+  }
+  for (int I = 20; I < 30; ++I) {
+EXPECT_EQ(V[I], I);
+  }
+  EXPECT_EQ(V.materialised().size(), 20ULL);
+
+  for (int I = 10; I < 20; ++I) {
+V[I] = I;
+  }
+  for (int I = 10; I < 20; ++I) {
+EXPECT_EQ(V[I], I);
+  }
+  EXPECT_EQ(V.materialised().size(), 30ULL);
+  V.expand(35);
+  EXPECT_EQ(V.materialised().size(), 30ULL);
+  for (int I = 30; I < 35; ++I) {
+V[I] = I;
+  }
+  EXPECT_EQ(V.materialised().size(), 40ULL);
+  EXPECT_EQ(V.size(), 35ULL);
+  EXPECT_EQ(V.capacity(), 40ULL);
+  V.expand(37);
+  for (int I = 30; I < 37; ++I) {
+V[I] = I;
+  }
+  EXPECT_EQ(V.size(), 37ULL);
+  EXPECT_EQ(V.capacity(), 40ULL);
+  for (int I = 0; I < 37; ++I) {
+EXPECT_EQ(V[I], I);
+  }
+
+  V.expand(41);
+  V[40] = 40;
+  EXPECT_EQ(V.size(), 41ULL);
+  EXPECT_EQ(V.capacity(), 50ULL);
+  for (int I = 0; I < 36; ++I) {
+EXPECT_EQ(V[I], I);
+EXPECT_EQ(V.at(I), I);
+  }
+  for (int I = 37; I < 40; ++I) {
+EXPECT_EQ(V[I], 0);
+EXPECT_EQ(V.at(I), 0);
+  }
+  V.expand(50);

kuhar wrote:

Could you split this into multiple smaller tests? I find it difficult to tell 
what each block of code is trying to test.

https://github.com/llvm/llvm-project/pull/66430
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] Introduce paged vector (PR #66430)

[Jakub Kuderski via cfe-commits]

@@ -0,0 +1,133 @@
+//===- llvm/ADT/PagedVector.h - 'Lazyly allocated' vectors *- 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
+//
+//===--===//
+//
+// This file defines the PagedVector class.
+//
+//===--===//
+#ifndef LLVM_ADT_PAGEDVECTOR_H
+#define LLVM_ADT_PAGEDVECTOR_H
+
+#include 
+#include 
+
+namespace llvm {
+// A vector that allocates memory in pages.
+// Order is kept, but memory is allocated only when one element of the page is
+// accessed. This introduces a level of indirection, but it is useful when you
+// have a sparsely initialised vector where the full size is allocated upfront
+// with the default constructor and elements are initialised later, on first
+// access.
+//
+// Notice that this does not have iterators, because if you
+// have iterators it probably means you are going to touch
+// all the memory in any case, so better use a std::vector in
+// the first place.
+template  class PagedVector {
+  // The actual number of element in the vector which can be accessed.
+  std::size_t Size = 0;
+  // The position of the initial element of the page in the Data vector.
+  // Pages are allocated contiguously in the Data vector.
+  mutable std::vector Lookup;
+  // Actual page data. All the page elements are added to this vector on the
+  // first access of any of the elements of the page. Elements default
+  // constructed and elements of the page are stored contiguously. The oder of
+  // the elements however depends on the order of access of the pages.
+  mutable std::vector Data;

kuhar wrote:

Do you expect this storage to be >4G elements? If not, would it make sense to 
define it in terms of `SmallVector` or `SmallVector`?

https://github.com/llvm/llvm-project/pull/66430
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] Introduce paged vector (PR #66430)

[Jakub Kuderski via cfe-commits]

@@ -0,0 +1,84 @@
+//===- llvm/unittest/ADT/PagedVectorTest.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
+//
+//===--===//
+//
+// PagedVector unit tests.
+//
+//===--===//
+
+#include "llvm/ADT/PagedVector.h"
+#include "gtest/gtest.h"
+
+namespace llvm {
+TEST(PagedVectorTest, FunctionalityTest) {

kuhar wrote:

@ktf we have examples in other tests, grep for EXPECT_DEATH. IIRC this needs to 
be guarded with a define that checks if gtest supports death tests and NDEBUG.

https://github.com/llvm/llvm-project/pull/66430
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] Introduce paged vector (PR #66430)

[Jakub Kuderski via cfe-commits]

@@ -0,0 +1,133 @@
+//===- llvm/ADT/PagedVector.h - 'Lazyly allocated' vectors *- 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
+//
+//===--===//
+//
+// This file defines the PagedVector class.
+//
+//===--===//
+#ifndef LLVM_ADT_PAGEDVECTOR_H
+#define LLVM_ADT_PAGEDVECTOR_H
+
+#include 
+#include 
+
+namespace llvm {
+// A vector that allocates memory in pages.
+// Order is kept, but memory is allocated only when one element of the page is
+// accessed. This introduces a level of indirection, but it is useful when you
+// have a sparsely initialised vector where the full size is allocated upfront
+// with the default constructor and elements are initialised later, on first
+// access.
+//
+// Notice that this does not have iterators, because if you
+// have iterators it probably means you are going to touch
+// all the memory in any case, so better use a std::vector in
+// the first place.
+template  class PagedVector {
+  // The actual number of element in the vector which can be accessed.
+  std::size_t Size = 0;
+  // The position of the initial element of the page in the Data vector.
+  // Pages are allocated contiguously in the Data vector.
+  mutable std::vector Lookup;
+  // Actual page data. All the page elements are added to this vector on the
+  // first access of any of the elements of the page. Elements default
+  // constructed and elements of the page are stored contiguously. The oder of
+  // the elements however depends on the order of access of the pages.
+  mutable std::vector Data;
+
+public:
+  // Lookup an element at position Index.
+  T [](std::size_t Index) const { return at(Index); }
+
+  // Lookup an element at position i.
+  // If the associated page is not filled, it will be filled with default
+  // constructed elements. If the associated page is filled, return the 
element.
+  T (std::size_t Index) const {
+assert(Index < Size);
+assert(Index / PAGE_SIZE < Lookup.size());
+auto  = Lookup[Index / PAGE_SIZE];
+// If the range is not filled, fill it
+if (PageId == -1) {
+  int OldSize = Data.size();
+  PageId = OldSize / PAGE_SIZE;
+  // Allocate the memory
+  Data.resize(OldSize + PAGE_SIZE);
+  // Fill the whole capacity with empty elements
+  for (int I = 0; I < PAGE_SIZE; ++I) {
+Data[I + OldSize] = T();
+  }

kuhar wrote:

Does this for loop do anything? I thought that new elements are initialized on 
`resize()`. https://en.cppreference.com/w/cpp/container/vector/resize

https://github.com/llvm/llvm-project/pull/66430
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] Introduce paged vector (PR #66430)

[Jakub Kuderski via cfe-commits]

@@ -0,0 +1,133 @@
+//===- llvm/ADT/PagedVector.h - 'Lazyly allocated' vectors *- 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
+//
+//===--===//
+//
+// This file defines the PagedVector class.
+//
+//===--===//
+#ifndef LLVM_ADT_PAGEDVECTOR_H
+#define LLVM_ADT_PAGEDVECTOR_H
+
+#include 
+#include 
+
+namespace llvm {
+// A vector that allocates memory in pages.
+// Order is kept, but memory is allocated only when one element of the page is
+// accessed. This introduces a level of indirection, but it is useful when you
+// have a sparsely initialised vector where the full size is allocated upfront
+// with the default constructor and elements are initialised later, on first
+// access.
+//
+// Notice that this does not have iterators, because if you
+// have iterators it probably means you are going to touch
+// all the memory in any case, so better use a std::vector in
+// the first place.
+template  class PagedVector {
+  // The actual number of element in the vector which can be accessed.
+  std::size_t Size = 0;
+  // The position of the initial element of the page in the Data vector.
+  // Pages are allocated contiguously in the Data vector.
+  mutable std::vector Lookup;
+  // Actual page data. All the page elements are added to this vector on the
+  // first access of any of the elements of the page. Elements default
+  // constructed and elements of the page are stored contiguously. The oder of
+  // the elements however depends on the order of access of the pages.
+  mutable std::vector Data;
+
+public:
+  // Lookup an element at position Index.
+  T [](std::size_t Index) const { return at(Index); }
+
+  // Lookup an element at position i.
+  // If the associated page is not filled, it will be filled with default
+  // constructed elements. If the associated page is filled, return the 
element.
+  T (std::size_t Index) const {
+assert(Index < Size);
+assert(Index / PAGE_SIZE < Lookup.size());
+auto  = Lookup[Index / PAGE_SIZE];
+// If the range is not filled, fill it
+if (PageId == -1) {
+  int OldSize = Data.size();
+  PageId = OldSize / PAGE_SIZE;

kuhar wrote:

Could we make this closer to the first use?

https://github.com/llvm/llvm-project/pull/66430
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] Introduce paged vector (PR #66430)

[Jakub Kuderski via cfe-commits]

@@ -0,0 +1,133 @@
+//===- llvm/ADT/PagedVector.h - 'Lazyly allocated' vectors *- 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
+//
+//===--===//
+//
+// This file defines the PagedVector class.
+//
+//===--===//
+#ifndef LLVM_ADT_PAGEDVECTOR_H
+#define LLVM_ADT_PAGEDVECTOR_H
+
+#include 
+#include 
+
+namespace llvm {
+// A vector that allocates memory in pages.
+// Order is kept, but memory is allocated only when one element of the page is
+// accessed. This introduces a level of indirection, but it is useful when you
+// have a sparsely initialised vector where the full size is allocated upfront
+// with the default constructor and elements are initialised later, on first
+// access.
+//
+// Notice that this does not have iterators, because if you
+// have iterators it probably means you are going to touch
+// all the memory in any case, so better use a std::vector in
+// the first place.
+template  class PagedVector {

kuhar wrote:

Why not use size_t/unsigned for page size? Do we support negative numbers or 
keep them as reserved for some future use?

https://github.com/llvm/llvm-project/pull/66430
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] Introduce paged vector (PR #66430)

[Jakub Kuderski via cfe-commits]

@@ -0,0 +1,133 @@
+//===- llvm/ADT/PagedVector.h - 'Lazyly allocated' vectors *- 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
+//
+//===--===//
+//
+// This file defines the PagedVector class.
+//
+//===--===//
+#ifndef LLVM_ADT_PAGEDVECTOR_H
+#define LLVM_ADT_PAGEDVECTOR_H
+
+#include 
+#include 
+
+namespace llvm {
+// A vector that allocates memory in pages.
+// Order is kept, but memory is allocated only when one element of the page is
+// accessed. This introduces a level of indirection, but it is useful when you
+// have a sparsely initialised vector where the full size is allocated upfront
+// with the default constructor and elements are initialised later, on first
+// access.
+//
+// Notice that this does not have iterators, because if you
+// have iterators it probably means you are going to touch
+// all the memory in any case, so better use a std::vector in
+// the first place.
+template  class PagedVector {
+  // The actual number of element in the vector which can be accessed.
+  std::size_t Size = 0;
+  // The position of the initial element of the page in the Data vector.
+  // Pages are allocated contiguously in the Data vector.
+  mutable std::vector Lookup;
+  // Actual page data. All the page elements are added to this vector on the
+  // first access of any of the elements of the page. Elements default
+  // constructed and elements of the page are stored contiguously. The oder of
+  // the elements however depends on the order of access of the pages.
+  mutable std::vector Data;
+
+public:
+  // Lookup an element at position Index.
+  T [](std::size_t Index) const { return at(Index); }
+
+  // Lookup an element at position i.
+  // If the associated page is not filled, it will be filled with default
+  // constructed elements. If the associated page is filled, return the 
element.
+  T (std::size_t Index) const {
+assert(Index < Size);
+assert(Index / PAGE_SIZE < Lookup.size());
+auto  = Lookup[Index / PAGE_SIZE];
+// If the range is not filled, fill it
+if (PageId == -1) {
+  int OldSize = Data.size();
+  PageId = OldSize / PAGE_SIZE;
+  // Allocate the memory
+  Data.resize(OldSize + PAGE_SIZE);
+  // Fill the whole capacity with empty elements
+  for (int I = 0; I < PAGE_SIZE; ++I) {
+Data[I + OldSize] = T();
+  }
+}
+// Calculate the actual position in the Data vector
+// by taking the start of the page and adding the offset
+// in the page.
+std::size_t StoreIndex = Index % PAGE_SIZE + PAGE_SIZE * PageId;
+// Return the element
+assert(StoreIndex < Data.size());
+return Data[StoreIndex];
+  }
+
+  // Return the capacity of the vector. I.e. the maximum size it can be 
expanded
+  // to with the expand method without allocating more pages.
+  std::size_t capacity() const { return Lookup.size() * PAGE_SIZE; }
+
+  // Return the size of the vector. I.e. the maximum index that can be
+  // accessed, i.e. the maximum value which was used as argument of the
+  // expand method.
+  std::size_t size() const { return Size; }
+
+  // Expands the vector to the given NewSize number of elements.
+  // If the vector was smaller, allocates new pages as needed.
+  // It should be called only with NewSize >= Size.
+  void expand(std::size_t NewSize) {
+// You cannot shrink the vector, otherwise
+// one would have to invalidate contents which is expensive and
+// while giving the false hope that the resize is cheap.
+if (NewSize <= Size) {
+  return;
+}
+// If the capacity is enough, just update the size and continue
+// with the currently allocated pages.
+if (NewSize <= capacity()) {
+  Size = NewSize;
+  return;
+}
+// The number of pages to allocate. The Remainder is calculated
+// for the case in which the NewSize is not a multiple of PAGE_SIZE.
+// In that case we need one more page.
+auto Pages = NewSize / PAGE_SIZE;
+auto Remainder = NewSize % PAGE_SIZE;
+if (Remainder) {
+  Pages += 1;
+}
+assert(Pages > Lookup.size());
+// We use -1 to indicate that a page has not been allocated yet.
+// This cannot be 0, because 0 is a valid page id.
+// We use -1 instead of a separate bool to avoid wasting space.
+Lookup.resize(Pages, -1);
+Size = NewSize;
+  }
+
+  // Return true if the vector is empty
+  bool empty() const { return Size == 0; }
+
+  /// Clear the vector, i.e. clear the allocated pages, the whole page
+  /// lookup index and reset the size.
+  void clear() {
+Size = 0;
+Lookup.clear();
+Data.clear();
+  }
+
+  /// Return the materialised vector. 

[clang] b9db89f - [ADT][NFCI] Do not use non-const lvalue-refs with enumerate in llvm/

[Jakub Kuderski via cfe-commits]

Author: Jakub Kuderski
Date: 2023-03-13T20:59:06-04:00
New Revision: b9db89fbcfdaece8656159a2a0f0a2f09cdd7db7

URL: 
https://github.com/llvm/llvm-project/commit/b9db89fbcfdaece8656159a2a0f0a2f09cdd7db7
DIFF: 
https://github.com/llvm/llvm-project/commit/b9db89fbcfdaece8656159a2a0f0a2f09cdd7db7.diff

LOG: [ADT][NFCI] Do not use non-const lvalue-refs with enumerate in llvm/

Replace references to `enumerate` results with either const lvalue
rerences or structured bindings. I did not use structured bindings
everywhere as it wasn't clear to me it would improve readability.

This is in preparation to the switch to `zip` semantics which won't
support non-const lvalue reference to elements:
https://reviews.llvm.org/D144503.

Reviewed By: dblaikie

Differential Revision: https://reviews.llvm.org/D145987

Added: 


Modified: 
clang/tools/clang-refactor/TestSupport.cpp
llvm/lib/ObjectYAML/DWARFYAML.cpp
llvm/lib/ObjectYAML/MinidumpEmitter.cpp
llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp
llvm/tools/llvm-reduce/deltas/ReduceArguments.cpp
llvm/unittests/DebugInfo/CodeView/RandomAccessVisitorTest.cpp
llvm/utils/TableGen/GlobalISel/GIMatchTree.cpp

Removed: 




diff  --git a/clang/tools/clang-refactor/TestSupport.cpp 
b/clang/tools/clang-refactor/TestSupport.cpp
index 400313eeab5e5..3fae18c2109a6 100644
--- a/clang/tools/clang-refactor/TestSupport.cpp
+++ b/clang/tools/clang-refactor/TestSupport.cpp
@@ -176,11 +176,11 @@ std::pair getLineColumn(StringRef 
Filename,
 
 bool TestRefactoringResultConsumer::handleAllResults() {
   bool Failed = false;
-  for (auto  : llvm::enumerate(Results)) {
+  for (const auto  : llvm::enumerate(Results)) {
 // All ranges in the group must produce the same result.
 std::optional CanonicalResult;
 std::optional CanonicalErrorMessage;
-for (auto  : llvm::enumerate(Group.value())) {
+for (const auto  : llvm::enumerate(Group.value())) {
   Expected  = I.value();
   std::string ErrorMessage;
   bool HasResult = !!Result;

diff  --git a/llvm/lib/ObjectYAML/DWARFYAML.cpp 
b/llvm/lib/ObjectYAML/DWARFYAML.cpp
index 37116ada99015..2bddeed464135 100644
--- a/llvm/lib/ObjectYAML/DWARFYAML.cpp
+++ b/llvm/lib/ObjectYAML/DWARFYAML.cpp
@@ -59,22 +59,20 @@ Expected
 DWARFYAML::Data::getAbbrevTableInfoByID(uint64_t ID) const {
   if (AbbrevTableInfoMap.empty()) {
 uint64_t AbbrevTableOffset = 0;
-for (auto  : enumerate(DebugAbbrev)) {
+for (const auto &[Index, AbbrevTable] : enumerate(DebugAbbrev)) {
   // If the abbrev table's ID isn't specified, we use the index as its ID.
-  uint64_t AbbrevTableID =
-  AbbrevTable.value().ID.value_or(AbbrevTable.index());
+  uint64_t AbbrevTableID = AbbrevTable.ID.value_or(Index);
   auto It = AbbrevTableInfoMap.insert(
-  {AbbrevTableID, AbbrevTableInfo{/*Index=*/AbbrevTable.index(),
+  {AbbrevTableID, AbbrevTableInfo{/*Index=*/Index,
   /*Offset=*/AbbrevTableOffset}});
   if (!It.second)
 return createStringError(
 errc::invalid_argument,
 "the ID (%" PRIu64 ") of abbrev table with index %zu has been used 
"
 "by abbrev table with index %" PRIu64,
-AbbrevTableID, AbbrevTable.index(), It.first->second.Index);
+AbbrevTableID, Index, It.first->second.Index);
 
-  AbbrevTableOffset +=
-  getAbbrevTableContentByIndex(AbbrevTable.index()).size();
+  AbbrevTableOffset += getAbbrevTableContentByIndex(Index).size();
 }
   }
 

diff  --git a/llvm/lib/ObjectYAML/MinidumpEmitter.cpp 
b/llvm/lib/ObjectYAML/MinidumpEmitter.cpp
index 1bda6f364b1bd..24b521a9925c7 100644
--- a/llvm/lib/ObjectYAML/MinidumpEmitter.cpp
+++ b/llvm/lib/ObjectYAML/MinidumpEmitter.cpp
@@ -236,8 +236,8 @@ bool yaml2minidump(MinidumpYAML::Object , raw_ostream 
,
   Obj.Header.StreamDirectoryRVA = 
File.allocateArray(ArrayRef(StreamDirectory));
   Obj.Header.NumberOfStreams = StreamDirectory.size();
 
-  for (auto  : enumerate(Obj.Streams))
-StreamDirectory[Stream.index()] = layout(File, *Stream.value());
+  for (const auto &[Index, Stream] : enumerate(Obj.Streams))
+StreamDirectory[Index] = layout(File, *Stream);
 
   File.writeTo(Out);
   return true;

diff  --git a/llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp 
b/llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp
index 1d479bb111b13..8256832b64e87 100644
--- a/llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp
+++ b/llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp
@@ -349,16 +349,16 @@ enum class UseMask {
 static SmallBitVector buildUseMask(int VF, ArrayRef Mask,
UseMask MaskArg) {
   SmallBitVector UseMask(VF, true);
-  for (auto P : enumerate(Mask)) {
-if (P.value() == UndefMaskElem) {
+  for (auto [Idx, Value] : enumerate(Mask)) {
+if (Value == UndefMaskElem) {
   if 

r308041 - [Dominators] Update Clang's DominatorTree to use the new template argument

[Jakub Kuderski via cfe-commits]

Author: kuhar
Date: Fri Jul 14 11:26:21 2017
New Revision: 308041

URL: http://llvm.org/viewvc/llvm-project?rev=308041=rev
Log:
[Dominators] Update Clang's DominatorTree to use the new template argument

Summary: This patch makes the Clang's DominatorTree use the new IsPostDom 
template argument for DominatorTreeBase.

Reviewers: dberlin, sanjoy, davide, grosser

Reviewed By: dberlin

Subscribers: llvm-commits

Differential Revision: https://reviews.llvm.org/D35316

Modified:
cfe/trunk/include/clang/Analysis/Analyses/Dominators.h

Modified: cfe/trunk/include/clang/Analysis/Analyses/Dominators.h
URL: 
http://llvm.org/viewvc/llvm-project/cfe/trunk/include/clang/Analysis/Analyses/Dominators.h?rev=308041=308040=308041=diff
==
--- cfe/trunk/include/clang/Analysis/Analyses/Dominators.h (original)
+++ cfe/trunk/include/clang/Analysis/Analyses/Dominators.h Fri Jul 14 11:26:21 
2017
@@ -38,15 +38,15 @@ typedef llvm::DomTreeNodeBase
 class DominatorTree : public ManagedAnalysis {
   virtual void anchor();
 public:
-  llvm::DominatorTreeBase* DT;
+  llvm::DomTreeBase* DT;
 
   DominatorTree() {
-DT = new llvm::DominatorTreeBase(false);
+DT = new llvm::DomTreeBase();
   }
 
   ~DominatorTree() override { delete DT; }
 
-  llvm::DominatorTreeBase& getBase() { return *DT; }
+  llvm::DomTreeBase& getBase() { return *DT; }
 
   /// \brief This method returns the root CFGBlock of the dominators tree.
   ///


___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang-tools-extra] r303145 - [clang-tidy] modernize-use-emplace: Remove unnecessary make_tuple calls

[Jakub Kuderski via cfe-commits]

Author: kuhar
Date: Tue May 16 01:32:38 2017
New Revision: 303145

URL: http://llvm.org/viewvc/llvm-project?rev=303145=rev
Log:
[clang-tidy] modernize-use-emplace: Remove unnecessary make_tuple calls

Summary:
This patch makes modernize-use-emplace remove unnecessary make_ calls from 
push_back calls and turn them into emplace_back -- the same way make_pair calls 
are handled.
Custom make_ calls can be removed for custom tuple-like types -- two new 
options that control that are `TupleTypes` and `TupleMakeFunctions`. By 
default, the check removes calls to `std::make_pair` and `std::make_tuple`.

Eq.

```
std::vector> v;
v.push_back(std::make_tuple(1, 'A', true)); // --> v.emplace_back(1, 'A', true);
```

Reviewers: alexfh, aaron.ballman, Prazek, hokein

Reviewed By: Prazek

Subscribers: JDevlieghere, xazax.hun, JonasToth, cfe-commits

Tags: #clang-tools-extra

Differential Revision: https://reviews.llvm.org/D32690

Modified:
clang-tools-extra/trunk/clang-tidy/modernize/UseEmplaceCheck.cpp
clang-tools-extra/trunk/clang-tidy/modernize/UseEmplaceCheck.h
clang-tools-extra/trunk/docs/ReleaseNotes.rst
clang-tools-extra/trunk/docs/clang-tidy/checks/modernize-use-emplace.rst
clang-tools-extra/trunk/test/clang-tidy/modernize-use-emplace.cpp

Modified: clang-tools-extra/trunk/clang-tidy/modernize/UseEmplaceCheck.cpp
URL: 
http://llvm.org/viewvc/llvm-project/clang-tools-extra/trunk/clang-tidy/modernize/UseEmplaceCheck.cpp?rev=303145=303144=303145=diff
==
--- clang-tools-extra/trunk/clang-tidy/modernize/UseEmplaceCheck.cpp (original)
+++ clang-tools-extra/trunk/clang-tidy/modernize/UseEmplaceCheck.cpp Tue May 16 
01:32:38 2017
@@ -24,6 +24,8 @@ const auto DefaultContainersWithPushBack
 "::std::vector; ::std::list; ::std::deque";
 const auto DefaultSmartPointers =
 "::std::shared_ptr; ::std::unique_ptr; ::std::auto_ptr; ::std::weak_ptr";
+const auto DefaultTupleTypes = "::std::pair; ::std::tuple";
+const auto DefaultTupleMakeFunctions = "::std::make_pair; ::std::make_tuple";
 } // namespace
 
 UseEmplaceCheck::UseEmplaceCheck(StringRef Name, ClangTidyContext *Context)
@@ -31,7 +33,11 @@ UseEmplaceCheck::UseEmplaceCheck(StringR
   ContainersWithPushBack(utils::options::parseStringList(Options.get(
   "ContainersWithPushBack", DefaultContainersWithPushBack))),
   SmartPointers(utils::options::parseStringList(
-  Options.get("SmartPointers", DefaultSmartPointers))) {}
+  Options.get("SmartPointers", DefaultSmartPointers))),
+  TupleTypes(utils::options::parseStringList(
+  Options.get("TupleTypes", DefaultTupleTypes))),
+  TupleMakeFunctions(utils::options::parseStringList(
+  Options.get("TupleMakeFunctions", DefaultTupleMakeFunctions))) {}
 
 void UseEmplaceCheck::registerMatchers(MatchFinder *Finder) {
   if (!getLangOpts().CPlusPlus11)
@@ -87,20 +93,23 @@ void UseEmplaceCheck::registerMatchers(M
   .bind("ctor");
   auto HasConstructExpr = has(ignoringImplicit(SoughtConstructExpr));
 
-  auto MakePair = ignoringImplicit(
-  callExpr(callee(expr(ignoringImplicit(
-  declRefExpr(unless(hasExplicitTemplateArgs()),
-  to(functionDecl(hasName("::std::make_pair"
-  .bind("make_pair"));
+  auto MakeTuple = ignoringImplicit(
+  callExpr(
+  callee(expr(ignoringImplicit(declRefExpr(
+  unless(hasExplicitTemplateArgs()),
+  to(functionDecl(hasAnyName(SmallVector(
+  TupleMakeFunctions.begin(), TupleMakeFunctions.end())
+  .bind("make"));
 
-  // make_pair can return type convertible to container's element type.
+  // make_something can return type convertible to container's element type.
   // Allow the conversion only on containers of pairs.
-  auto MakePairCtor = ignoringImplicit(cxxConstructExpr(
-  has(materializeTemporaryExpr(MakePair)),
-  hasDeclaration(cxxConstructorDecl(ofClass(hasName("::std::pair"));
+  auto MakeTupleCtor = ignoringImplicit(cxxConstructExpr(
+  has(materializeTemporaryExpr(MakeTuple)),
+  hasDeclaration(cxxConstructorDecl(ofClass(hasAnyName(
+  SmallVector(TupleTypes.begin(), 
TupleTypes.end(;
 
   auto SoughtParam = materializeTemporaryExpr(
-  anyOf(has(MakePair), has(MakePairCtor),
+  anyOf(has(MakeTuple), has(MakeTupleCtor),
 HasConstructExpr, has(cxxFunctionalCastExpr(HasConstructExpr;
 
   Finder->addMatcher(cxxMemberCallExpr(CallPushBack, has(SoughtParam),
@@ -112,8 +121,8 @@ void UseEmplaceCheck::registerMatchers(M
 void UseEmplaceCheck::check(const MatchFinder::MatchResult ) {
   const auto *Call = Result.Nodes.getNodeAs("call");
   const auto *InnerCtorCall = Result.Nodes.getNodeAs("ctor");
-  const auto *MakePairCall = Result.Nodes.getNodeAs("make_pair");
-  assert((InnerCtorCall || MakePairCall) && 

[clang-tools-extra] r303140 - Revert "[clang-tidy] modernize-use-emplace: Remove unnecessary make_tuple calls"

[Jakub Kuderski via cfe-commits]

Author: kuhar
Date: Tue May 16 00:07:40 2017
New Revision: 303140

URL: http://llvm.org/viewvc/llvm-project?rev=303140=rev
Log:
Revert "[clang-tidy] modernize-use-emplace: Remove unnecessary make_tuple calls"

This reverts commit r303139. The commit made docs build emit a warning.

Modified:
clang-tools-extra/trunk/clang-tidy/modernize/UseEmplaceCheck.cpp
clang-tools-extra/trunk/clang-tidy/modernize/UseEmplaceCheck.h
clang-tools-extra/trunk/docs/ReleaseNotes.rst
clang-tools-extra/trunk/docs/clang-tidy/checks/modernize-use-emplace.rst
clang-tools-extra/trunk/test/clang-tidy/modernize-use-emplace.cpp

Modified: clang-tools-extra/trunk/clang-tidy/modernize/UseEmplaceCheck.cpp
URL: 
http://llvm.org/viewvc/llvm-project/clang-tools-extra/trunk/clang-tidy/modernize/UseEmplaceCheck.cpp?rev=303140=303139=303140=diff
==
--- clang-tools-extra/trunk/clang-tidy/modernize/UseEmplaceCheck.cpp (original)
+++ clang-tools-extra/trunk/clang-tidy/modernize/UseEmplaceCheck.cpp Tue May 16 
00:07:40 2017
@@ -24,8 +24,6 @@ const auto DefaultContainersWithPushBack
 "::std::vector; ::std::list; ::std::deque";
 const auto DefaultSmartPointers =
 "::std::shared_ptr; ::std::unique_ptr; ::std::auto_ptr; ::std::weak_ptr";
-const auto DefaultTupleTypes = "::std::pair; ::std::tuple";
-const auto DefaultTupleMakeFunctions = "::std::make_pair; ::std::make_tuple";
 } // namespace
 
 UseEmplaceCheck::UseEmplaceCheck(StringRef Name, ClangTidyContext *Context)
@@ -33,11 +31,7 @@ UseEmplaceCheck::UseEmplaceCheck(StringR
   ContainersWithPushBack(utils::options::parseStringList(Options.get(
   "ContainersWithPushBack", DefaultContainersWithPushBack))),
   SmartPointers(utils::options::parseStringList(
-  Options.get("SmartPointers", DefaultSmartPointers))),
-  TupleTypes(utils::options::parseStringList(
-  Options.get("TupleTypes", DefaultTupleTypes))),
-  TupleMakeFunctions(utils::options::parseStringList(
-  Options.get("TupleMakeFunctions", DefaultTupleMakeFunctions))) {}
+  Options.get("SmartPointers", DefaultSmartPointers))) {}
 
 void UseEmplaceCheck::registerMatchers(MatchFinder *Finder) {
   if (!getLangOpts().CPlusPlus11)
@@ -93,23 +87,20 @@ void UseEmplaceCheck::registerMatchers(M
   .bind("ctor");
   auto HasConstructExpr = has(ignoringImplicit(SoughtConstructExpr));
 
-  auto MakeTuple = ignoringImplicit(
-  callExpr(
-  callee(expr(ignoringImplicit(declRefExpr(
-  unless(hasExplicitTemplateArgs()),
-  to(functionDecl(hasAnyName(SmallVector(
-  TupleMakeFunctions.begin(), TupleMakeFunctions.end())
-  .bind("make"));
+  auto MakePair = ignoringImplicit(
+  callExpr(callee(expr(ignoringImplicit(
+  declRefExpr(unless(hasExplicitTemplateArgs()),
+  to(functionDecl(hasName("::std::make_pair"
+  .bind("make_pair"));
 
-  // make_something can return type convertible to container's element type.
+  // make_pair can return type convertible to container's element type.
   // Allow the conversion only on containers of pairs.
-  auto MakeTupleCtor = ignoringImplicit(cxxConstructExpr(
-  has(materializeTemporaryExpr(MakeTuple)),
-  hasDeclaration(cxxConstructorDecl(ofClass(hasAnyName(
-  SmallVector(TupleTypes.begin(), 
TupleTypes.end(;
+  auto MakePairCtor = ignoringImplicit(cxxConstructExpr(
+  has(materializeTemporaryExpr(MakePair)),
+  hasDeclaration(cxxConstructorDecl(ofClass(hasName("::std::pair"));
 
   auto SoughtParam = materializeTemporaryExpr(
-  anyOf(has(MakeTuple), has(MakeTupleCtor),
+  anyOf(has(MakePair), has(MakePairCtor),
 HasConstructExpr, has(cxxFunctionalCastExpr(HasConstructExpr;
 
   Finder->addMatcher(cxxMemberCallExpr(CallPushBack, has(SoughtParam),
@@ -121,8 +112,8 @@ void UseEmplaceCheck::registerMatchers(M
 void UseEmplaceCheck::check(const MatchFinder::MatchResult ) {
   const auto *Call = Result.Nodes.getNodeAs("call");
   const auto *InnerCtorCall = Result.Nodes.getNodeAs("ctor");
-  const auto *MakeCall = Result.Nodes.getNodeAs("make");
-  assert((InnerCtorCall || MakeCall) && "No push_back parameter matched");
+  const auto *MakePairCall = Result.Nodes.getNodeAs("make_pair");
+  assert((InnerCtorCall || MakePairCall) && "No push_back parameter matched");
 
   const auto FunctionNameSourceRange = CharSourceRange::getCharRange(
   Call->getExprLoc(), Call->getArg(0)->getExprLoc());
@@ -132,20 +123,20 @@ void UseEmplaceCheck::check(const MatchF
   if (FunctionNameSourceRange.getBegin().isMacroID())
 return;
 
-  const auto *EmplacePrefix = MakeCall ? "emplace_back" : "emplace_back(";
+  const auto *EmplacePrefix = MakePairCall ? "emplace_back" : "emplace_back(";
   Diag << FixItHint::CreateReplacement(FunctionNameSourceRange, EmplacePrefix);
 
  

[clang-tools-extra] r303139 - [clang-tidy] modernize-use-emplace: Remove unnecessary make_tuple calls

[Jakub Kuderski via cfe-commits]

Author: kuhar
Date: Mon May 15 23:25:42 2017
New Revision: 303139

URL: http://llvm.org/viewvc/llvm-project?rev=303139=rev
Log:
[clang-tidy] modernize-use-emplace: Remove unnecessary make_tuple calls

Summary:
This patch makes modernize-use-emplace remove unnecessary make_ calls from 
push_back calls and turn them into emplace_back -- the same way make_pair calls 
are handled.
Custom make_ calls can be removed for custom tuple-like types -- two new 
options that control that are `TupleTypes` and `TupleMakeFunctions`. By 
default, the check removes calls to `std::make_pair` and `std::make_tuple`.

Eq.

```
std::vector> v;
v.push_back(std::make_tuple(1, 'A', true)); // --> v.emplace_back(1, 'A', true);
```

Reviewers: alexfh, aaron.ballman, Prazek, hokein

Reviewed By: Prazek

Subscribers: JDevlieghere, xazax.hun, JonasToth, cfe-commits

Tags: #clang-tools-extra

Differential Revision: https://reviews.llvm.org/D32690

Modified:
clang-tools-extra/trunk/clang-tidy/modernize/UseEmplaceCheck.cpp
clang-tools-extra/trunk/clang-tidy/modernize/UseEmplaceCheck.h
clang-tools-extra/trunk/docs/ReleaseNotes.rst
clang-tools-extra/trunk/docs/clang-tidy/checks/modernize-use-emplace.rst
clang-tools-extra/trunk/test/clang-tidy/modernize-use-emplace.cpp

Modified: clang-tools-extra/trunk/clang-tidy/modernize/UseEmplaceCheck.cpp
URL: 
http://llvm.org/viewvc/llvm-project/clang-tools-extra/trunk/clang-tidy/modernize/UseEmplaceCheck.cpp?rev=303139=303138=303139=diff
==
--- clang-tools-extra/trunk/clang-tidy/modernize/UseEmplaceCheck.cpp (original)
+++ clang-tools-extra/trunk/clang-tidy/modernize/UseEmplaceCheck.cpp Mon May 15 
23:25:42 2017
@@ -24,6 +24,8 @@ const auto DefaultContainersWithPushBack
 "::std::vector; ::std::list; ::std::deque";
 const auto DefaultSmartPointers =
 "::std::shared_ptr; ::std::unique_ptr; ::std::auto_ptr; ::std::weak_ptr";
+const auto DefaultTupleTypes = "::std::pair; ::std::tuple";
+const auto DefaultTupleMakeFunctions = "::std::make_pair; ::std::make_tuple";
 } // namespace
 
 UseEmplaceCheck::UseEmplaceCheck(StringRef Name, ClangTidyContext *Context)
@@ -31,7 +33,11 @@ UseEmplaceCheck::UseEmplaceCheck(StringR
   ContainersWithPushBack(utils::options::parseStringList(Options.get(
   "ContainersWithPushBack", DefaultContainersWithPushBack))),
   SmartPointers(utils::options::parseStringList(
-  Options.get("SmartPointers", DefaultSmartPointers))) {}
+  Options.get("SmartPointers", DefaultSmartPointers))),
+  TupleTypes(utils::options::parseStringList(
+  Options.get("TupleTypes", DefaultTupleTypes))),
+  TupleMakeFunctions(utils::options::parseStringList(
+  Options.get("TupleMakeFunctions", DefaultTupleMakeFunctions))) {}
 
 void UseEmplaceCheck::registerMatchers(MatchFinder *Finder) {
   if (!getLangOpts().CPlusPlus11)
@@ -87,20 +93,23 @@ void UseEmplaceCheck::registerMatchers(M
   .bind("ctor");
   auto HasConstructExpr = has(ignoringImplicit(SoughtConstructExpr));
 
-  auto MakePair = ignoringImplicit(
-  callExpr(callee(expr(ignoringImplicit(
-  declRefExpr(unless(hasExplicitTemplateArgs()),
-  to(functionDecl(hasName("::std::make_pair"
-  .bind("make_pair"));
+  auto MakeTuple = ignoringImplicit(
+  callExpr(
+  callee(expr(ignoringImplicit(declRefExpr(
+  unless(hasExplicitTemplateArgs()),
+  to(functionDecl(hasAnyName(SmallVector(
+  TupleMakeFunctions.begin(), TupleMakeFunctions.end())
+  .bind("make"));
 
-  // make_pair can return type convertible to container's element type.
+  // make_something can return type convertible to container's element type.
   // Allow the conversion only on containers of pairs.
-  auto MakePairCtor = ignoringImplicit(cxxConstructExpr(
-  has(materializeTemporaryExpr(MakePair)),
-  hasDeclaration(cxxConstructorDecl(ofClass(hasName("::std::pair"));
+  auto MakeTupleCtor = ignoringImplicit(cxxConstructExpr(
+  has(materializeTemporaryExpr(MakeTuple)),
+  hasDeclaration(cxxConstructorDecl(ofClass(hasAnyName(
+  SmallVector(TupleTypes.begin(), 
TupleTypes.end(;
 
   auto SoughtParam = materializeTemporaryExpr(
-  anyOf(has(MakePair), has(MakePairCtor),
+  anyOf(has(MakeTuple), has(MakeTupleCtor),
 HasConstructExpr, has(cxxFunctionalCastExpr(HasConstructExpr;
 
   Finder->addMatcher(cxxMemberCallExpr(CallPushBack, has(SoughtParam),
@@ -112,8 +121,8 @@ void UseEmplaceCheck::registerMatchers(M
 void UseEmplaceCheck::check(const MatchFinder::MatchResult ) {
   const auto *Call = Result.Nodes.getNodeAs("call");
   const auto *InnerCtorCall = Result.Nodes.getNodeAs("ctor");
-  const auto *MakePairCall = Result.Nodes.getNodeAs("make_pair");
-  assert((InnerCtorCall || MakePairCall) && 

[clang-tools-extra] r302317 - [clang-tidy] Use cxxStdInitializerListExpr in modernize-use-emplace

[Jakub Kuderski via cfe-commits]

Author: kuhar
Date: Fri May  5 18:00:37 2017
New Revision: 302317

URL: http://llvm.org/viewvc/llvm-project?rev=302317=rev
Log:
[clang-tidy] Use cxxStdInitializerListExpr in modernize-use-emplace

Summary: Use the cxxStdInitializerListExp matcher from ASTMatchers.h instead of 
a local one.

Reviewers: aaron.ballman, alexfh, Prazek

Reviewed By: aaron.ballman

Subscribers: xazax.hun, cfe-commits

Tags: #clang-tools-extra

Differential Revision: https://reviews.llvm.org/D32923

Modified:
clang-tools-extra/trunk/clang-tidy/modernize/UseEmplaceCheck.cpp

Modified: clang-tools-extra/trunk/clang-tidy/modernize/UseEmplaceCheck.cpp
URL: 
http://llvm.org/viewvc/llvm-project/clang-tools-extra/trunk/clang-tidy/modernize/UseEmplaceCheck.cpp?rev=302317=302316=302317=diff
==
--- clang-tools-extra/trunk/clang-tidy/modernize/UseEmplaceCheck.cpp (original)
+++ clang-tools-extra/trunk/clang-tidy/modernize/UseEmplaceCheck.cpp Fri May  5 
18:00:37 2017
@@ -20,12 +20,6 @@ AST_MATCHER(DeclRefExpr, hasExplicitTemp
   return Node.hasExplicitTemplateArgs();
 }
 
-namespace impl {
-// FIXME: This matcher should be replaced by a matcher from ASTMatcher.h
-const ast_matchers::internal::VariadicDynCastAllOfMatcher cxxStdInitializerListExpr;
-} // namespace impl
-
 const auto DefaultContainersWithPushBack =
 "::std::vector; ::std::list; ::std::deque";
 const auto DefaultSmartPointers =
@@ -81,9 +75,7 @@ void UseEmplaceCheck::registerMatchers(M
   auto IsPrivateCtor = hasDeclaration(cxxConstructorDecl(isPrivate()));
 
   auto HasInitList = anyOf(has(ignoringImplicit(initListExpr())),
-   has(impl::cxxStdInitializerListExpr()));
-  // FIXME: Replace internal C++ initializer list matcher with one from
-  // ASTMatchers.h
+   has(cxxStdInitializerListExpr()));
 
   // FIXME: Discard 0/NULL (as nullptr), static inline const data members,
   // overloaded functions and template names.


___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

r302287 - Add cxxStdInitializerListExpr AST matcher

[Jakub Kuderski via cfe-commits]

Author: kuhar
Date: Fri May  5 16:01:12 2017
New Revision: 302287

URL: http://llvm.org/viewvc/llvm-project?rev=302287=rev
Log:
Add cxxStdInitializerListExpr AST matcher

Summary:
This adds a new ASTMatcher for CXXStdInitializerListExprs that matches C++ 
initializer list expressions.

The primary motivation is to use it to fix [[ 
https://bugs.llvm.org/show_bug.cgi?id=32896 | PR32896 ]] (review here [[ 
https://reviews.llvm.org/D32767 | D32767 ]]).

Reviewers: alexfh, Prazek, aaron.ballman

Reviewed By: alexfh, aaron.ballman

Subscribers: malcolm.parsons, cfe-commits, klimek

Differential Revision: https://reviews.llvm.org/D32810

Modified:
cfe/trunk/docs/LibASTMatchersReference.html
cfe/trunk/include/clang/ASTMatchers/ASTMatchers.h
cfe/trunk/lib/ASTMatchers/Dynamic/Registry.cpp
cfe/trunk/unittests/ASTMatchers/ASTMatchersNodeTest.cpp

Modified: cfe/trunk/docs/LibASTMatchersReference.html
URL: 
http://llvm.org/viewvc/llvm-project/cfe/trunk/docs/LibASTMatchersReference.html?rev=302287=302286=302287=diff
==
--- cfe/trunk/docs/LibASTMatchersReference.html (original)
+++ cfe/trunk/docs/LibASTMatchersReference.html Fri May  5 16:01:12 2017
@@ -924,6 +924,19 @@ in
 
 
 
+Matcherhttp://clang.llvm.org/doxygen/classclang_1_1Stmt.html;>StmtcxxStdInitializerListExprMatcherhttp://clang.llvm.org/doxygen/classclang_1_1CXXStdInitializerListExpr.html;>CXXStdInitializerListExpr...
+Matches 
C++ initializer list expressions.
+
+Given
+  std::vectorint a({ 1, 2, 3 });
+  std::vectorint b = { 4, 5 };
+  int c[] = { 6, 7 };
+  std::pairint, int d = { 8, 9 };
+cxxStdInitializerListExpr()
+  matches "{ 1, 2, 3 }" and "{ 4, 5 }"
+
+
+
 Matcherhttp://clang.llvm.org/doxygen/classclang_1_1Stmt.html;>StmtcxxTemporaryObjectExprMatcherhttp://clang.llvm.org/doxygen/classclang_1_1CXXTemporaryObjectExpr.html;>CXXTemporaryObjectExpr...
 Matches 
functional cast expressions having N != 1 arguments
 
@@ -1160,7 +1173,7 @@ Example matches [](){return 5;}
 Matches 
nodes where temporaries are materialized.
 
 Example: Given
-  struct T {void func()};
+  struct T {void func();};
   T f();
   void g(T);
 materializeTemporaryExpr() matches 'f()' in these statements
@@ -5233,7 +5246,7 @@ Example matches y in x(y)
 Matches on the 
receiver of an ObjectiveC Message expression.
 
 Example
-matcher = objCMessageExpr(hasRecieverType(asString("UIWebView *")));
+matcher = objCMessageExpr(hasReceiverType(asString("UIWebView *")));
 matches the [webView ...] message invocation.
   NSString *webViewJavaScript = ...
   UIWebView *webView = ...

Modified: cfe/trunk/include/clang/ASTMatchers/ASTMatchers.h
URL: 
http://llvm.org/viewvc/llvm-project/cfe/trunk/include/clang/ASTMatchers/ASTMatchers.h?rev=302287=302286=302287=diff
==
--- cfe/trunk/include/clang/ASTMatchers/ASTMatchers.h (original)
+++ cfe/trunk/include/clang/ASTMatchers/ASTMatchers.h Fri May  5 16:01:12 2017
@@ -1223,6 +1223,20 @@ AST_MATCHER_P(InitListExpr, hasSyntactic
   InnerMatcher.matches(*SyntForm, Finder, Builder));
 }
 
+/// \brief Matches C++ initializer list expressions.
+///
+/// Given
+/// \code
+///   std::vector a({ 1, 2, 3 });
+///   std::vector b = { 4, 5 };
+///   int c[] = { 6, 7 };
+///   std::pair d = { 8, 9 };
+/// \endcode
+/// cxxStdInitializerListExpr()
+///   matches "{ 1, 2, 3 }" and "{ 4, 5 }"
+const internal::VariadicDynCastAllOfMatcher cxxStdInitializerListExpr;
+
 /// \brief Matches implicit initializers of init list expressions.
 ///
 /// Given

Modified: cfe/trunk/lib/ASTMatchers/Dynamic/Registry.cpp
URL: 
http://llvm.org/viewvc/llvm-project/cfe/trunk/lib/ASTMatchers/Dynamic/Registry.cpp?rev=302287=302286=302287=diff
==
--- cfe/trunk/lib/ASTMatchers/Dynamic/Registry.cpp (original)
+++ cfe/trunk/lib/ASTMatchers/Dynamic/Registry.cpp Fri May  5 16:01:12 2017
@@ -153,6 +153,7 @@ RegistryMaps::RegistryMaps() {
   REGISTER_MATCHER(cxxRecordDecl);
   REGISTER_MATCHER(cxxReinterpretCastExpr);
   REGISTER_MATCHER(cxxStaticCastExpr);
+  REGISTER_MATCHER(cxxStdInitializerListExpr);
   REGISTER_MATCHER(cxxTemporaryObjectExpr);
   REGISTER_MATCHER(cxxThisExpr);
   REGISTER_MATCHER(cxxThrowExpr);

Modified: cfe/trunk/unittests/ASTMatchers/ASTMatchersNodeTest.cpp
URL: 
http://llvm.org/viewvc/llvm-project/cfe/trunk/unittests/ASTMatchers/ASTMatchersNodeTest.cpp?rev=302287=302286=302287=diff
==
--- cfe/trunk/unittests/ASTMatchers/ASTMatchersNodeTest.cpp (original)
+++ cfe/trunk/unittests/ASTMatchers/ASTMatchersNodeTest.cpp Fri May  5 16:01:12 
2017
@@ -1020,6 +1020,29 @@ TEST(InitListExpression, MatchesInitList
 matches("int i[1] = {42, [0] = 43};", integerLiteral(equals(42;
 }
 

[clang-tools-extra] r302281 - [clang-tidy] Fix PR32896: detect initializer lists in modernize-use-empalce

[Jakub Kuderski via cfe-commits]

Author: kuhar
Date: Fri May  5 15:35:30 2017
New Revision: 302281

URL: http://llvm.org/viewvc/llvm-project?rev=302281=rev
Log:
[clang-tidy] Fix PR32896: detect initializer lists in modernize-use-empalce

Summary:
This patch fixes [[ https://bugs.llvm.org/show_bug.cgi?id=32896 | PR32896 ]].

The problem was that modernize-use-emplace incorrectly removed changed 
push_back into emplace_back, removing explicit constructor call with 
initializer list parameter, resulting in compiler error after applying fixits.
modernize-use-emplace used to check if matched constructor had InitListExpr, 
but didn't check against CXXStdInitializerListExpr.

Eg.

```
std::vector v;
  v.push_back(std::vector({1})); // --> v.emplace_back({1});
```

Reviewers: Prazek, alexfh, aaron.ballman

Reviewed By: Prazek, alexfh, aaron.ballman

Subscribers: xazax.hun, cfe-commits

Tags: #clang-tools-extra

Differential Revision: https://reviews.llvm.org/D32767

Modified:
clang-tools-extra/trunk/clang-tidy/modernize/UseEmplaceCheck.cpp
clang-tools-extra/trunk/test/clang-tidy/modernize-use-emplace.cpp

Modified: clang-tools-extra/trunk/clang-tidy/modernize/UseEmplaceCheck.cpp
URL: 
http://llvm.org/viewvc/llvm-project/clang-tools-extra/trunk/clang-tidy/modernize/UseEmplaceCheck.cpp?rev=302281=302280=302281=diff
==
--- clang-tools-extra/trunk/clang-tidy/modernize/UseEmplaceCheck.cpp (original)
+++ clang-tools-extra/trunk/clang-tidy/modernize/UseEmplaceCheck.cpp Fri May  5 
15:35:30 2017
@@ -20,6 +20,12 @@ AST_MATCHER(DeclRefExpr, hasExplicitTemp
   return Node.hasExplicitTemplateArgs();
 }
 
+namespace impl {
+// FIXME: This matcher should be replaced by a matcher from ASTMatcher.h
+const ast_matchers::internal::VariadicDynCastAllOfMatcher cxxStdInitializerListExpr;
+} // namespace impl
+
 const auto DefaultContainersWithPushBack =
 "::std::vector; ::std::list; ::std::deque";
 const auto DefaultSmartPointers =
@@ -74,7 +80,11 @@ void UseEmplaceCheck::registerMatchers(M
   // emplace_back can't access private constructor.
   auto IsPrivateCtor = hasDeclaration(cxxConstructorDecl(isPrivate()));
 
-  auto HasInitList = has(ignoringImplicit(initListExpr()));
+  auto HasInitList = anyOf(has(ignoringImplicit(initListExpr())),
+   has(impl::cxxStdInitializerListExpr()));
+  // FIXME: Replace internal C++ initializer list matcher with one from
+  // ASTMatchers.h
+
   // FIXME: Discard 0/NULL (as nullptr), static inline const data members,
   // overloaded functions and template names.
   auto SoughtConstructExpr =

Modified: clang-tools-extra/trunk/test/clang-tidy/modernize-use-emplace.cpp
URL: 
http://llvm.org/viewvc/llvm-project/clang-tools-extra/trunk/test/clang-tidy/modernize-use-emplace.cpp?rev=302281=302280=302281=diff
==
--- clang-tools-extra/trunk/test/clang-tidy/modernize-use-emplace.cpp (original)
+++ clang-tools-extra/trunk/test/clang-tidy/modernize-use-emplace.cpp Fri May  
5 15:35:30 2017
@@ -4,9 +4,19 @@
 // RUN:   value: '::std::vector; ::std::list; ::std::deque; 
llvm::LikeASmallVector'}]}" -- -std=c++11
 
 namespace std {
+template 
+class initializer_list
+{
+public:
+  initializer_list() noexcept {}
+};
+
 template 
 class vector {
 public:
+  vector() = default;
+  vector(initializer_list) {}
+
   void push_back(const T &) {}
   void push_back(T &&) {}
 
@@ -455,3 +465,16 @@ void testWithDtor() {
   // CHECK-MESSAGES: :[[@LINE-1]]:5: warning: use emplace_back
   // CHECK-FIXES: v.emplace_back(42);
 }
+
+void testInitializerList() {
+  std::vector v;
+  v.push_back(std::vector({1}));
+  // Test against the bug reported in PR32896.
+
+  v.push_back({{2}});
+
+  using PairIntVector = std::pair;
+  std::vector x;
+  x.push_back(PairIntVector(3, {4}));
+  x.push_back({5, {6}});
+}


___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang-tools-extra] r301780 - [clang-tidy] Fix naming convention in modernize-use-emplace

[Jakub Kuderski via cfe-commits]

Author: kuhar
Date: Sun Apr 30 16:12:56 2017
New Revision: 301780

URL: http://llvm.org/viewvc/llvm-project?rev=301780=rev
Log:
[clang-tidy] Fix naming convention in modernize-use-emplace

Summary: Conform to the llvm naming convention for local variables in 
modernize-use-emplace check.

Reviewers: Prazek, JonasToth, alexfh

Reviewed By: Prazek, JonasToth, alexfh

Subscribers: cfe-commits

Tags: #clang-tools-extra

Differential Revision: https://reviews.llvm.org/D32678

Modified:
clang-tools-extra/trunk/clang-tidy/modernize/UseEmplaceCheck.cpp

Modified: clang-tools-extra/trunk/clang-tidy/modernize/UseEmplaceCheck.cpp
URL: 
http://llvm.org/viewvc/llvm-project/clang-tools-extra/trunk/clang-tidy/modernize/UseEmplaceCheck.cpp?rev=301780=301779=301780=diff
==
--- clang-tools-extra/trunk/clang-tidy/modernize/UseEmplaceCheck.cpp (original)
+++ clang-tools-extra/trunk/clang-tidy/modernize/UseEmplaceCheck.cpp Sun Apr 30 
16:12:56 2017
@@ -45,7 +45,7 @@ void UseEmplaceCheck::registerMatchers(M
   // because this requires special treatment (it could cause performance
   // regression)
   // + match for emplace calls that should be replaced with insertion
-  auto callPushBack = cxxMemberCallExpr(
+  auto CallPushBack = cxxMemberCallExpr(
   hasDeclaration(functionDecl(hasName("push_back"))),
   on(hasType(cxxRecordDecl(hasAnyName(SmallVector(
   ContainersWithPushBack.begin(), ContainersWithPushBack.end()));
@@ -54,38 +54,38 @@ void UseEmplaceCheck::registerMatchers(M
   // if emplacement fails (f.e. bad_alloc in vector) we will have leak of
   // passed pointer because smart pointer won't be constructed
   // (and destructed) as in push_back case.
-  auto isCtorOfSmartPtr = hasDeclaration(cxxConstructorDecl(ofClass(hasAnyName(
+  auto IsCtorOfSmartPtr = hasDeclaration(cxxConstructorDecl(ofClass(hasAnyName(
   SmallVector(SmartPointers.begin(), 
SmartPointers.end());
 
   // Bitfields binds only to consts and emplace_back take it by universal ref.
-  auto bitFieldAsArgument = hasAnyArgument(
+  auto BitFieldAsArgument = hasAnyArgument(
   ignoringImplicit(memberExpr(hasDeclaration(fieldDecl(isBitField());
 
   // Initializer list can't be passed to universal reference.
-  auto initializerListAsArgument = hasAnyArgument(
+  auto InitializerListAsArgument = hasAnyArgument(
   ignoringImplicit(cxxConstructExpr(isListInitialization(;
 
   // We could have leak of resource.
-  auto newExprAsArgument = hasAnyArgument(ignoringImplicit(cxxNewExpr()));
+  auto NewExprAsArgument = hasAnyArgument(ignoringImplicit(cxxNewExpr()));
   // We would call another constructor.
-  auto constructingDerived =
+  auto ConstructingDerived =
   hasParent(implicitCastExpr(hasCastKind(CastKind::CK_DerivedToBase)));
 
   // emplace_back can't access private constructor.
-  auto isPrivateCtor = hasDeclaration(cxxConstructorDecl(isPrivate()));
+  auto IsPrivateCtor = hasDeclaration(cxxConstructorDecl(isPrivate()));
 
-  auto hasInitList = has(ignoringImplicit(initListExpr()));
+  auto HasInitList = has(ignoringImplicit(initListExpr()));
   // FIXME: Discard 0/NULL (as nullptr), static inline const data members,
   // overloaded functions and template names.
-  auto soughtConstructExpr =
+  auto SoughtConstructExpr =
   cxxConstructExpr(
-  unless(anyOf(isCtorOfSmartPtr, hasInitList, bitFieldAsArgument,
-   initializerListAsArgument, newExprAsArgument,
-   constructingDerived, isPrivateCtor)))
+  unless(anyOf(IsCtorOfSmartPtr, HasInitList, BitFieldAsArgument,
+   InitializerListAsArgument, NewExprAsArgument,
+   ConstructingDerived, IsPrivateCtor)))
   .bind("ctor");
-  auto hasConstructExpr = has(ignoringImplicit(soughtConstructExpr));
+  auto HasConstructExpr = has(ignoringImplicit(SoughtConstructExpr));
 
-  auto makePair = ignoringImplicit(
+  auto MakePair = ignoringImplicit(
   callExpr(callee(expr(ignoringImplicit(
   declRefExpr(unless(hasExplicitTemplateArgs()),
   to(functionDecl(hasName("::std::make_pair"
@@ -93,15 +93,15 @@ void UseEmplaceCheck::registerMatchers(M
 
   // make_pair can return type convertible to container's element type.
   // Allow the conversion only on containers of pairs.
-  auto makePairCtor = ignoringImplicit(cxxConstructExpr(
-  has(materializeTemporaryExpr(makePair)),
+  auto MakePairCtor = ignoringImplicit(cxxConstructExpr(
+  has(materializeTemporaryExpr(MakePair)),
   hasDeclaration(cxxConstructorDecl(ofClass(hasName("::std::pair"));
 
-  auto soughtParam = materializeTemporaryExpr(
-  anyOf(has(makePair), has(makePairCtor),
-hasConstructExpr, has(cxxFunctionalCastExpr(hasConstructExpr;
+  auto SoughtParam = materializeTemporaryExpr(
+  anyOf(has(MakePair), 

[clang-tools-extra] r301651 - [clang-tidy] modernize-use-emplace: remove unnecessary make_pair calls

[Jakub Kuderski via cfe-commits]

Author: kuhar
Date: Fri Apr 28 11:25:45 2017
New Revision: 301651

URL: http://llvm.org/viewvc/llvm-project?rev=301651=rev
Log:
[clang-tidy] modernize-use-emplace: remove unnecessary make_pair calls

Summary:
When there is a push_back with a call to make_pair, turn it into emplace_back 
and remove the unnecessary make_pair call.

Eg.

```
std::vector> v;
v.push_back(std::make_pair(1, 2)); // --> v.emplace_back(1, 2);
```

make_pair doesn't get removed when explicit template parameters are provided, 
because of potential problems with type conversions.

Reviewers: Prazek, aaron.ballman, hokein, alexfh

Reviewed By: Prazek, alexfh

Subscribers: JDevlieghere, JonasToth, cfe-commits

Tags: #clang-tools-extra

Differential Revision: https://reviews.llvm.org/D32395

Modified:
clang-tools-extra/trunk/clang-tidy/modernize/UseEmplaceCheck.cpp
clang-tools-extra/trunk/docs/ReleaseNotes.rst
clang-tools-extra/trunk/docs/clang-tidy/checks/modernize-use-emplace.rst
clang-tools-extra/trunk/test/clang-tidy/modernize-use-emplace.cpp

Modified: clang-tools-extra/trunk/clang-tidy/modernize/UseEmplaceCheck.cpp
URL: 
http://llvm.org/viewvc/llvm-project/clang-tools-extra/trunk/clang-tidy/modernize/UseEmplaceCheck.cpp?rev=301651=301650=301651=diff
==
--- clang-tools-extra/trunk/clang-tidy/modernize/UseEmplaceCheck.cpp (original)
+++ clang-tools-extra/trunk/clang-tidy/modernize/UseEmplaceCheck.cpp Fri Apr 28 
11:25:45 2017
@@ -15,10 +15,16 @@ namespace clang {
 namespace tidy {
 namespace modernize {
 
-static const auto DefaultContainersWithPushBack =
+namespace {
+AST_MATCHER(DeclRefExpr, hasExplicitTemplateArgs) {
+  return Node.hasExplicitTemplateArgs();
+}
+
+const auto DefaultContainersWithPushBack =
 "::std::vector; ::std::list; ::std::deque";
-static const auto DefaultSmartPointers =
+const auto DefaultSmartPointers =
 "::std::shared_ptr; ::std::unique_ptr; ::std::auto_ptr; ::std::weak_ptr";
+} // namespace
 
 UseEmplaceCheck::UseEmplaceCheck(StringRef Name, ClangTidyContext *Context)
 : ClangTidyCheck(Name, Context),
@@ -39,7 +45,6 @@ void UseEmplaceCheck::registerMatchers(M
   // because this requires special treatment (it could cause performance
   // regression)
   // + match for emplace calls that should be replaced with insertion
-  // + match for make_pair calls.
   auto callPushBack = cxxMemberCallExpr(
   hasDeclaration(functionDecl(hasName("push_back"))),
   on(hasType(cxxRecordDecl(hasAnyName(SmallVector(
@@ -80,10 +85,23 @@ void UseEmplaceCheck::registerMatchers(M
   .bind("ctor");
   auto hasConstructExpr = has(ignoringImplicit(soughtConstructExpr));
 
-  auto ctorAsArgument = materializeTemporaryExpr(
-  anyOf(hasConstructExpr, has(cxxFunctionalCastExpr(hasConstructExpr;
+  auto makePair = ignoringImplicit(
+  callExpr(callee(expr(ignoringImplicit(
+  declRefExpr(unless(hasExplicitTemplateArgs()),
+  to(functionDecl(hasName("::std::make_pair"
+  .bind("make_pair"));
+
+  // make_pair can return type convertible to container's element type.
+  // Allow the conversion only on containers of pairs.
+  auto makePairCtor = ignoringImplicit(cxxConstructExpr(
+  has(materializeTemporaryExpr(makePair)),
+  hasDeclaration(cxxConstructorDecl(ofClass(hasName("::std::pair"));
+
+  auto soughtParam = materializeTemporaryExpr(
+  anyOf(has(makePair), has(makePairCtor),
+hasConstructExpr, has(cxxFunctionalCastExpr(hasConstructExpr;
 
-  Finder->addMatcher(cxxMemberCallExpr(callPushBack, has(ctorAsArgument),
+  Finder->addMatcher(cxxMemberCallExpr(callPushBack, has(soughtParam),
unless(isInTemplateInstantiation()))
  .bind("call"),
  this);
@@ -92,8 +110,10 @@ void UseEmplaceCheck::registerMatchers(M
 void UseEmplaceCheck::check(const MatchFinder::MatchResult ) {
   const auto *Call = Result.Nodes.getNodeAs("call");
   const auto *InnerCtorCall = Result.Nodes.getNodeAs("ctor");
+  const auto *MakePairCall = Result.Nodes.getNodeAs("make_pair");
+  assert((InnerCtorCall || MakePairCall) && "No push_back parameter matched");
 
-  auto FunctionNameSourceRange = CharSourceRange::getCharRange(
+  const auto FunctionNameSourceRange = CharSourceRange::getCharRange(
   Call->getExprLoc(), Call->getArg(0)->getExprLoc());
 
   auto Diag = diag(Call->getExprLoc(), "use emplace_back instead of 
push_back");
@@ -101,22 +121,28 @@ void UseEmplaceCheck::check(const MatchF
   if (FunctionNameSourceRange.getBegin().isMacroID())
 return;
 
-  Diag << FixItHint::CreateReplacement(FunctionNameSourceRange,
-   "emplace_back(");
+  const auto *EmplacePrefix = MakePairCall ? "emplace_back" : "emplace_back(";
+  Diag << FixItHint::CreateReplacement(FunctionNameSourceRange, EmplacePrefix);
 

[clang-tools-extra] r301365 - [clang-tidy] run-clang-tidy.py: check if clang-apply-replacements succeeds

[Jakub Kuderski via cfe-commits]

Author: kuhar
Date: Tue Apr 25 17:38:39 2017
New Revision: 301365

URL: http://llvm.org/viewvc/llvm-project?rev=301365=rev
Log:
[clang-tidy] run-clang-tidy.py: check if clang-apply-replacements succeeds

Summary:
When running run-clang-tidy.py with -fix it tries to apply found replacements 
at the end.
If there are errors running clang-apply-replacements, the script currently 
crashes or displays no error at all.

This patch checks for errors running clang-apply-replacements the same way 
clang-tidy binary is handled.

Another option would be probably checking for clang-apply-replacements (when 
-fix is passed) even before running clang-tidy.

Reviewers: Prazek, alexfh, bkramer, mfherbst

Reviewed By: Prazek, alexfh

Subscribers: kimgr, cfe-commits

Tags: #clang-tools-extra

Differential Revision: https://reviews.llvm.org/D32294

Modified:
clang-tools-extra/trunk/clang-tidy/tool/run-clang-tidy.py

Modified: clang-tools-extra/trunk/clang-tidy/tool/run-clang-tidy.py
URL: 
http://llvm.org/viewvc/llvm-project/clang-tools-extra/trunk/clang-tidy/tool/run-clang-tidy.py?rev=301365=301364=301365=diff
==
--- clang-tools-extra/trunk/clang-tidy/tool/run-clang-tidy.py (original)
+++ clang-tools-extra/trunk/clang-tidy/tool/run-clang-tidy.py Tue Apr 25 
17:38:39 2017
@@ -34,6 +34,7 @@ Compilation database setup:
 http://clang.llvm.org/docs/HowToSetupToolingForLLVM.html
 """
 
+from __future__ import print_function
 import argparse
 import json
 import multiprocessing
@@ -45,6 +46,7 @@ import subprocess
 import sys
 import tempfile
 import threading
+import traceback
 
 
 def find_compilation_database(path):
@@ -52,7 +54,7 @@ def find_compilation_database(path):
   result = './'
   while not os.path.isfile(os.path.join(result, path)):
 if os.path.realpath(result) == '/':
-  print 'Error: could not find compilation database.'
+  print('Error: could not find compilation database.')
   sys.exit(1)
 result += '../'
   return os.path.realpath(result)
@@ -87,6 +89,17 @@ def get_tidy_invocation(f, clang_tidy_bi
   return start
 
 
+def check_clang_apply_replacements_binary(args):
+  """Checks if invoking supplied clang-apply-replacements binary works."""
+  try:
+subprocess.check_call([args.clang_apply_replacements_binary, '--version'])
+  except:
+print('Unable to run clang-apply-replacements. Is clang-apply-replacements 
'
+  'binary correctly specified?', file=sys.stderr)
+traceback.print_exc()
+sys.exit(1)
+
+
 def apply_fixes(args, tmpdir):
   """Calls clang-apply-fixes on a given directory. Deletes the dir when 
done."""
   invocation = [args.clang_apply_replacements_binary]
@@ -94,7 +107,6 @@ def apply_fixes(args, tmpdir):
 invocation.append('-format')
   invocation.append(tmpdir)
   subprocess.call(invocation)
-  shutil.rmtree(tmpdir)
 
 
 def run_tidy(args, tmpdir, build_path, queue):
@@ -164,9 +176,9 @@ def main():
 if args.checks:
   invocation.append('-checks=' + args.checks)
 invocation.append('-')
-print subprocess.check_output(invocation)
+print(subprocess.check_output(invocation))
   except:
-print >>sys.stderr, "Unable to run clang-tidy."
+print("Unable to run clang-tidy.", file=sys.stderr)
 sys.exit(1)
 
   # Load the database and extract all files.
@@ -179,6 +191,7 @@ def main():
 
   tmpdir = None
   if args.fix:
+check_clang_apply_replacements_binary(args)
 tmpdir = tempfile.mkdtemp()
 
   # Build up a big regexy filter from all command line arguments.
@@ -204,14 +217,25 @@ def main():
   except KeyboardInterrupt:
 # This is a sad hack. Unfortunately subprocess goes
 # bonkers with ctrl-c and we start forking merrily.
-print '\nCtrl-C detected, goodbye.'
+print('\nCtrl-C detected, goodbye.')
 if args.fix:
   shutil.rmtree(tmpdir)
 os.kill(0, 9)
 
   if args.fix:
-print 'Applying fixes ...'
-apply_fixes(args, tmpdir)
+print('Applying fixes ...')
+successfully_applied = False
+
+try:
+  apply_fixes(args, tmpdir)
+  successfully_applied = True
+except:
+  print('Error applying fixes.\n', file=sys.stderr)
+  traceback.print_exc()
+
+shutil.rmtree(tmpdir)
+if not successfully_applied:
+  sys.exit(1)
 
 if __name__ == '__main__':
   main()


___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

Re: [PATCH] D12400: Fix store detection for return value in CGCall

[Jakub Kuderski via cfe-commits]

kuhar updated this revision to Diff 33919.
kuhar added a comment.

Some refactoring + comments added.


Repository:
  rL LLVM

http://reviews.llvm.org/D12400

Files:
  lib/CodeGen/CGCall.cpp
  test/CodeGen/arm_function_epilog.cpp

Index: test/CodeGen/arm_function_epilog.cpp
===
--- /dev/null
+++ test/CodeGen/arm_function_epilog.cpp
@@ -0,0 +1,17 @@
+// REQUIRES: arm-registered-target
+// RUN: %clang_cc1 -triple armv7-none-linux-androideabi -target-abi 
aapcs-linux -mfloat-abi hard -x c++ -emit-llvm %s -o - | FileCheck %s
+
+struct Vec2 {
+union { struct { float x, y; };
+float data[2];
+};
+};
+
+// CHECK: define arm_aapcs_vfpcc %struct.Vec2 @_Z7getVec2v()
+// CHECK: ret %struct.Vec2
+Vec2 getVec2() {
+Vec2 out;
+union { Vec2* v; unsigned char* u; } x;
+x.v = 
+return out;
+}
Index: lib/CodeGen/CGCall.cpp
===
--- lib/CodeGen/CGCall.cpp
+++ lib/CodeGen/CGCall.cpp
@@ -2277,6 +2277,18 @@
 
 /// Heuristically search for a dominating store to the return-value slot.
 static llvm::StoreInst *findDominatingStoreToReturnValue(CodeGenFunction ) 
{
+  // Check if a User is a store which pointerOperand is the ReturnValue.
+  // We are looking for stores to the ReturnValue, not for stores of the
+  // ReturnValue to some other location.
+  auto getStoreIfValid = [](llvm::User *U) -> llvm::StoreInst * {
+auto *SI = dyn_cast(U);
+if (!SI || SI->getPointerOperand() != CGF.ReturnValue)
+  return nullptr;
+// These aren't actually possible for non-coerced returns, and we
+// only care about non-coerced returns on this code path.
+assert(!SI->isAtomic() && !SI->isVolatile());
+return SI;
+  };
   // If there are multiple uses of the return-value slot, just check
   // for something immediately preceding the IP.  Sometimes this can
   // happen with how we generate implicit-returns; it can also happen
@@ -2305,21 +2317,12 @@
   break;
 }
 
-llvm::StoreInst *store = dyn_cast(I);
-if (!store) return nullptr;
-if (store->getPointerOperand() != CGF.ReturnValue) return nullptr;
-assert(!store->isAtomic() && !store->isVolatile()); // see below
-return store;
+return getStoreIfValid(I);
   }
 
-  llvm::StoreInst *store =
-dyn_cast(CGF.ReturnValue->user_back());
+  llvm::StoreInst *store = getStoreIfValid(CGF.ReturnValue->user_back());
   if (!store) return nullptr;
 
-  // These aren't actually possible for non-coerced returns, and we
-  // only care about non-coerced returns on this code path.
-  assert(!store->isAtomic() && !store->isVolatile());
-
   // Now do a first-and-dirty dominance check: just walk up the
   // single-predecessors chain from the current insertion point.
   llvm::BasicBlock *StoreBB = store->getParent();


Index: test/CodeGen/arm_function_epilog.cpp
===
--- /dev/null
+++ test/CodeGen/arm_function_epilog.cpp
@@ -0,0 +1,17 @@
+// REQUIRES: arm-registered-target
+// RUN: %clang_cc1 -triple armv7-none-linux-androideabi -target-abi aapcs-linux -mfloat-abi hard -x c++ -emit-llvm %s -o - | FileCheck %s
+
+struct Vec2 {
+union { struct { float x, y; };
+float data[2];
+};
+};
+
+// CHECK: define arm_aapcs_vfpcc %struct.Vec2 @_Z7getVec2v()
+// CHECK: ret %struct.Vec2
+Vec2 getVec2() {
+Vec2 out;
+union { Vec2* v; unsigned char* u; } x;
+x.v = 
+return out;
+}
Index: lib/CodeGen/CGCall.cpp
===
--- lib/CodeGen/CGCall.cpp
+++ lib/CodeGen/CGCall.cpp
@@ -2277,6 +2277,18 @@
 
 /// Heuristically search for a dominating store to the return-value slot.
 static llvm::StoreInst *findDominatingStoreToReturnValue(CodeGenFunction ) {
+  // Check if a User is a store which pointerOperand is the ReturnValue.
+  // We are looking for stores to the ReturnValue, not for stores of the
+  // ReturnValue to some other location.
+  auto getStoreIfValid = [](llvm::User *U) -> llvm::StoreInst * {
+auto *SI = dyn_cast(U);
+if (!SI || SI->getPointerOperand() != CGF.ReturnValue)
+  return nullptr;
+// These aren't actually possible for non-coerced returns, and we
+// only care about non-coerced returns on this code path.
+assert(!SI->isAtomic() && !SI->isVolatile());
+return SI;
+  };
   // If there are multiple uses of the return-value slot, just check
   // for something immediately preceding the IP.  Sometimes this can
   // happen with how we generate implicit-returns; it can also happen
@@ -2305,21 +2317,12 @@
   break;
 }
 
-llvm::StoreInst *store = dyn_cast(I);
-if (!store) return nullptr;
-if (store->getPointerOperand() != CGF.ReturnValue) return nullptr;
-assert(!store->isAtomic() && !store->isVolatile()); // see below
-return store;
+return getStoreIfValid(I);
   }
 
-  llvm::StoreInst 

Re: [PATCH] D12400: Fix store detection for return value in CGCall

[Jakub Kuderski via cfe-commits]

kuhar added a comment.

ping


Repository:
  rL LLVM

http://reviews.llvm.org/D12400



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D12400: Fix store detection for return value in CGCall

[Jakub Kuderski via cfe-commits]

kuhar created this revision.
kuhar added a subscriber: cfe-commits.
kuhar set the repository for this revision to rL LLVM.
Herald added subscribers: srhines, danalbert, tberghammer.

`findDominatingStoreToReturn` in CGCall.cpp didn't check if a candidate store 
instruction used the ReturnValue as pointer operand or value operand. This led 
to wrong code gen - in later stages (load-store elision code) the found store 
and its operand would be erased, causing ReturnValue to become a badref.

The patch adds a check that makes sure that ReturnValue is a pointer operand of 
store instruction. Regression test is also added.

This fixes PR24386.

Repository:
  rL LLVM

http://reviews.llvm.org/D12400

Files:
  lib/CodeGen/CGCall.cpp
  test/CodeGen/arm_function_epilog.cpp

Index: test/CodeGen/arm_function_epilog.cpp
===
--- /dev/null
+++ test/CodeGen/arm_function_epilog.cpp
@@ -0,0 +1,17 @@
+// REQUIRES: arm-registered-target
+// RUN: %clang_cc1 -triple armv7-none-linux-androideabi -target-abi 
aapcs-linux -mfloat-abi hard -x c++ -emit-llvm %s -o - | FileCheck %s
+
+struct Vec2 {
+union { struct { float x, y; };
+float data[2];
+};
+};
+
+// CHECK: define arm_aapcs_vfpcc %struct.Vec2 @_Z7getVec2v()
+// CHECK: ret %struct.Vec2
+Vec2 getVec2() {
+Vec2 out;
+union { Vec2* v; unsigned char* u; } x;
+x.v = out;
+return out;
+}
Index: lib/CodeGen/CGCall.cpp
===
--- lib/CodeGen/CGCall.cpp
+++ lib/CodeGen/CGCall.cpp
@@ -2329,6 +2329,7 @@
   llvm::StoreInst *store =
 dyn_castllvm::StoreInst(CGF.ReturnValue-user_back());
   if (!store) return nullptr;
+  if (store-getPointerOperand() != CGF.ReturnValue) return nullptr;
 
   // These aren't actually possible for non-coerced returns, and we
   // only care about non-coerced returns on this code path.


Index: test/CodeGen/arm_function_epilog.cpp
===
--- /dev/null
+++ test/CodeGen/arm_function_epilog.cpp
@@ -0,0 +1,17 @@
+// REQUIRES: arm-registered-target
+// RUN: %clang_cc1 -triple armv7-none-linux-androideabi -target-abi aapcs-linux -mfloat-abi hard -x c++ -emit-llvm %s -o - | FileCheck %s
+
+struct Vec2 {
+union { struct { float x, y; };
+float data[2];
+};
+};
+
+// CHECK: define arm_aapcs_vfpcc %struct.Vec2 @_Z7getVec2v()
+// CHECK: ret %struct.Vec2
+Vec2 getVec2() {
+Vec2 out;
+union { Vec2* v; unsigned char* u; } x;
+x.v = out;
+return out;
+}
Index: lib/CodeGen/CGCall.cpp
===
--- lib/CodeGen/CGCall.cpp
+++ lib/CodeGen/CGCall.cpp
@@ -2329,6 +2329,7 @@
   llvm::StoreInst *store =
 dyn_castllvm::StoreInst(CGF.ReturnValue-user_back());
   if (!store) return nullptr;
+  if (store-getPointerOperand() != CGF.ReturnValue) return nullptr;
 
   // These aren't actually possible for non-coerced returns, and we
   // only care about non-coerced returns on this code path.
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits