1//===----------------------- InitMap.h --------------------------*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9#ifndef LLVM_CLANG_AST_INTERP_INIT_MAP_H
10#define LLVM_CLANG_AST_INTERP_INIT_MAP_H
11
12#include <cassert>
13#include <climits>
14#include <cstdint>
15#include <limits>
16#include <memory>
17
18namespace clang {
19namespace interp {
20
21/// Bitfield tracking the initialisation status of elements of primitive arrays.
22struct InitMap final {
23private:
24 /// Type packing bits.
25 using T = uint64_t;
26 /// Bits stored in a single field.
27 static constexpr uint64_t PER_FIELD = sizeof(T) * CHAR_BIT;
28 /// Number of fields in the init map.
29 unsigned NumElems;
30 /// Number of fields not initialized.
31 unsigned UninitFields;
32 unsigned DeadFields = 0;
33 std::unique_ptr<T[]> Data;
34
35public:
36 /// Initializes the map with no fields set.
37 explicit InitMap(unsigned N)
38 : NumElems(N), UninitFields(N),
39 Data(std::make_unique<T[]>(num: numFields(N))) {}
40 explicit InitMap(unsigned N, bool AllInitialized)
41 : NumElems(N), UninitFields(AllInitialized ? 0 : N),
42 Data(std::make_unique<T[]>(num: numFields(N))) {
43 if (AllInitialized) {
44 for (unsigned I = 0; I != (numFields(N) / 2); ++I)
45 Data[I] = std::numeric_limits<T>::max();
46 }
47 }
48
49 void startElementLifetime(unsigned I);
50 void endElementLifetime(unsigned I);
51
52 bool isElementAlive(unsigned I) const {
53 unsigned LifetimeIndex = (NumElems + I);
54 unsigned Bucket = numFields(N: NumElems) / 2 + (I / PER_FIELD);
55 return !(data()[Bucket] & (T(1) << (LifetimeIndex % PER_FIELD)));
56 }
57
58 bool allElementsAlive() const { return DeadFields == 0; }
59
60 /// Initializes an element. Returns true when object if fully initialized.
61 bool initializeElement(unsigned I);
62
63 /// Checks if an element was initialized.
64 bool isElementInitialized(unsigned I) const;
65
66private:
67 /// Returns a pointer to storage.
68 T *data() { return Data.get(); }
69 const T *data() const { return Data.get(); }
70
71 static constexpr size_t numFields(unsigned N) {
72 return ((N + PER_FIELD - 1) / PER_FIELD) * 2;
73 }
74};
75
76/// A pointer-sized struct we use to allocate into data storage.
77/// An InitMapPtr is either backed by an actual InitMap, or it
78/// hold information about the absence of the InitMap.
79struct InitMapPtr final {
80 /// V's value before an initmap has been created.
81 static constexpr intptr_t NoInitMapValue = 0;
82 /// V's value after the initmap has been destroyed because
83 /// all its elements have already been initialized.
84 static constexpr intptr_t AllInitializedValue = 1;
85 uintptr_t V = 0;
86
87 explicit InitMapPtr() = default;
88 bool hasInitMap() const {
89 return V != NoInitMapValue && V != AllInitializedValue;
90 }
91 /// Are all elements in the array already initialized?
92 bool allInitialized() const { return V == AllInitializedValue; }
93
94 void setInitMap(const InitMap *IM) {
95 assert(IM != nullptr);
96 V = reinterpret_cast<uintptr_t>(IM);
97 assert(hasInitMap());
98 }
99
100 void noteAllInitialized() {
101 if (hasInitMap())
102 delete (operator->)();
103 V = AllInitializedValue;
104 }
105
106 /// Access the underlying InitMap directly.
107 InitMap *operator->() {
108 assert(hasInitMap());
109 return reinterpret_cast<InitMap *>(V);
110 }
111
112 /// Delete the InitMap if one exists.
113 void deleteInitMap() {
114 if (hasInitMap())
115 delete (operator->)();
116 V = NoInitMapValue;
117 };
118};
119static_assert(sizeof(InitMapPtr) == sizeof(void *));
120} // namespace interp
121} // namespace clang
122
123#endif
124