1//===-------------------- FrameAllocator.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_FRAME_ALLOCATOR_H
10#define LLVM_CLANG_AST_INTERP_FRAME_ALLOCATOR_H
11
12#include "llvm/Support/Compiler.h"
13#ifndef NDEBUG
14#include "llvm/ADT/SmallVector.h"
15#endif
16#include <algorithm>
17#include <cassert>
18#include <new>
19
20namespace clang {
21namespace interp {
22
23// Set this to 1 to collect some light statistics.
24// Print via printStats().
25#define FRAME_ALLOCATOR_COLLECT_STATS 0
26
27/// Allocator for function frames.
28///
29/// The function frame size includes the size reserved for local variables.
30/// Function frames are allocated strictly in a LIFO manner, i.e. the last
31/// created frame is the first frame that is destroyed.
32///
33/// Since the address a function frame is allocated in needs to stay stable
34/// during the lifetime of the frame, we allocate them here in chunks.
35///
36/// A chunk is of (at least) MinChunkSize size and only gets deallocated once it
37/// is empty AND the previous chunk is also empty.
38///
39class FrameAllocator final {
40private:
41 struct Chunk {
42 Chunk *Prev = nullptr;
43 const unsigned Size;
44 unsigned Used = 0;
45 alignas(sizeof(void *)) char Memory[1];
46
47 Chunk(unsigned Size) : Size(Size) {}
48 unsigned bytesUnused() const { return Size - Used; }
49 };
50 static constexpr unsigned MinChunkSize = (4u * 1024u) - sizeof(Chunk);
51
52 Chunk *Tail = nullptr;
53#if FRAME_ALLOCATOR_COLLECT_STATS
54 size_t MaxSize = 0;
55 unsigned LargestFrame = 0;
56 unsigned NumFrames = 0;
57 unsigned NumAllocs = 0;
58#endif
59
60#ifndef NDEBUG
61 llvm::SmallVector<unsigned> FrameSizes;
62#endif
63
64public:
65 FrameAllocator() = default;
66 FrameAllocator(FrameAllocator &) = delete;
67 FrameAllocator(FrameAllocator &&) = delete;
68 ~FrameAllocator() {
69 while (Tail)
70 deallocTail();
71 }
72
73 char *reserve(unsigned Size) {
74 if (LLVM_UNLIKELY(!Tail))
75 allocateNewChunk(Size: std::max(a: Size, b: MinChunkSize));
76 assert(Tail);
77
78#ifndef NDEBUG
79 FrameSizes.push_back(Size);
80#endif
81
82 char *Mem;
83 if (Chunk *C = getChunkToUse(Size); C->bytesUnused() >= Size) {
84 Mem = &C->Memory[C->Used];
85 C->Used += Size;
86 } else {
87 // We need to allocate a new chunk. If the requested size is larger than
88 // the minimum, use that.
89 allocateNewChunk(Size: std::max(a: Size, b: MinChunkSize));
90 Tail->Used += Size;
91 Mem = Tail->Memory;
92 }
93
94#if FRAME_ALLOCATOR_COLLECT_STATS
95 LargestFrame = std::max(Size, LargestFrame);
96 MaxSize = std::max(MaxSize, countAllBytes());
97 ++NumFrames;
98#endif
99
100 return Mem;
101 }
102
103 /// Pop the memory of the last function frame that was added.
104 /// The passed \c FrameSize needs to match the latest size passed to
105 /// reserve(). If it doesn't, bad things will happen.
106 void pop(unsigned FrameSize) {
107#ifndef NDEBUG
108 assert(FrameSize == FrameSizes.back());
109#endif
110 // Frame destructor must've already been called.
111 assert(Tail);
112 Chunk *C = Tail->Used == 0 ? Tail->Prev : Tail;
113 assert(C);
114 assert(FrameSize <= C->Used);
115 C->Used -= FrameSize;
116
117 // Deallocate the tail chunk *if* it is empty _and_ the previous chunk is
118 // also empty.
119 // Since we create chunks specicially for large frames, we need to loop
120 // here.
121 while (Tail->Used == 0 && Tail->Prev && Tail->Prev->Used == 0)
122 deallocTail();
123
124#ifndef NDEBUG
125 FrameSizes.pop_back();
126#endif
127 }
128
129private:
130 /// Return the chunk to use to allocate a new frame into.
131 /// This is not always this->Tail, since Tail might be empty AND have a
132 /// previous chunk. In that case, we use the previous chunk, if it does have
133 /// \p Size bytes left.
134 Chunk *getChunkToUse(unsigned Size) {
135 assert(Tail);
136 if (Tail->Used == 0 && Tail->Prev && Tail->Prev->bytesUnused() >= Size)
137 return Tail->Prev;
138 return Tail;
139 }
140
141 void allocateNewChunk(unsigned Size) {
142 char *Mem = new char[sizeof(Chunk) + Size];
143 auto *C = new (Mem) Chunk(Size);
144 C->Prev = Tail;
145 Tail = C;
146
147 assert(Tail);
148
149#if FRAME_ALLOCATOR_COLLECT_STATS
150 ++NumAllocs;
151#endif
152 }
153
154 void deallocTail() {
155 assert(Tail);
156 Chunk *C = Tail;
157 Tail = Tail->Prev;
158 delete[] reinterpret_cast<char *>(C);
159 }
160
161#if FRAME_ALLOCATOR_COLLECT_STATS
162 size_t countAllBytes() const {
163 size_t Result = 0;
164 Chunk *C = Tail;
165 while (C) {
166 Result += C->Size + sizeof(Chunk);
167 C = C->Prev;
168 }
169 return Result;
170 }
171 void printStats() const {
172 llvm::errs() << "*** FrameAllocator stats ***\n";
173 if (!Tail) {
174 llvm::errs() << "empty\n";
175 return;
176 }
177
178 Chunk *C = Tail;
179 unsigned N = 0;
180 while (C) {
181 llvm::errs() << "Chunk " << N << ": " << C->Used << " / " << C->Size
182 << " (";
183 double Percentage =
184 (static_cast<double>(C->Used) / static_cast<double>(C->Size)) * 100;
185 llvm::errs() << llvm::formatv("{0:2}", Percentage) << "%)\n";
186 ++N;
187 C = C->Prev;
188 }
189 llvm::errs() << "Max allocated bytes: " << MaxSize << '\n';
190 llvm::errs() << "Largest frame: " << LargestFrame << '\n';
191 llvm::errs() << "Frames created: " << NumFrames << '\n';
192 llvm::errs() << "Allocations: " << NumAllocs << '\n';
193
194 llvm::errs() << "Occupancy: ";
195 size_t AllUsed = 0;
196 size_t AllSize = 0;
197 for (Chunk *C = Tail; C; C = C->Prev) {
198 AllUsed += C->Used;
199 AllSize += C->Size;
200 }
201 double Occupancy =
202 (static_cast<double>(AllUsed) / static_cast<double>(AllSize)) * 100;
203 llvm::errs() << llvm::formatv("{0:2}", Occupancy) << "%\n";
204 }
205#endif
206};
207} // namespace interp
208} // namespace clang
209
210#endif
211