1//===--- InterpStack.h - Stack implementation for the VM --------*- 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// Defines the upwards-growing stack used by the interpreter.
10//
11//===----------------------------------------------------------------------===//
12
13#ifndef LLVM_CLANG_AST_INTERP_INTERPSTACK_H
14#define LLVM_CLANG_AST_INTERP_INTERPSTACK_H
15
16#include <memory>
17
18namespace clang {
19namespace interp {
20
21/// Stack frame storing temporaries and parameters.
22class InterpStack final {
23public:
24  InterpStack() {}
25
26  /// Destroys the stack, freeing up storage.
27  ~InterpStack();
28
29  /// Constructs a value in place on the top of the stack.
30  template <typename T, typename... Tys> void push(Tys &&... Args) {
31    new (grow(aligned_size<T>())) T(std::forward<Tys>(Args)...);
32  }
33
34  /// Returns the value from the top of the stack and removes it.
35  template <typename T> T pop() {
36    auto *Ptr = &peek<T>();
37    auto Value = std::move(*Ptr);
38    Ptr->~T();
39    shrink(aligned_size<T>());
40    return Value;
41  }
42
43  /// Discards the top value from the stack.
44  template <typename T> void discard() {
45    auto *Ptr = &peek<T>();
46    Ptr->~T();
47    shrink(aligned_size<T>());
48  }
49
50  /// Returns a reference to the value on the top of the stack.
51  template <typename T> T &peek() {
52    return *reinterpret_cast<T *>(peek(aligned_size<T>()));
53  }
54
55  /// Returns a pointer to the top object.
56  void *top() { return Chunk ? peek(0) : nullptr; }
57
58  /// Returns the size of the stack in bytes.
59  size_t size() const { return StackSize; }
60
61  /// Clears the stack without calling any destructors.
62  void clear();
63
64private:
65  /// All stack slots are aligned to the native pointer alignment for storage.
66  /// The size of an object is rounded up to a pointer alignment multiple.
67  template <typename T> constexpr size_t aligned_size() const {
68    constexpr size_t PtrAlign = alignof(void *);
69    return ((sizeof(T) + PtrAlign - 1) / PtrAlign) * PtrAlign;
70  }
71
72  /// Grows the stack to accomodate a value and returns a pointer to it.
73  void *grow(size_t Size);
74  /// Returns a pointer from the top of the stack.
75  void *peek(size_t Size);
76  /// Shrinks the stack.
77  void shrink(size_t Size);
78
79  /// Allocate stack space in 1Mb chunks.
80  static constexpr size_t ChunkSize = 1024 * 1024;
81
82  /// Metadata for each stack chunk.
83  ///
84  /// The stack is composed of a linked list of chunks. Whenever an allocation
85  /// is out of bounds, a new chunk is linked. When a chunk becomes empty,
86  /// it is not immediately freed: a chunk is deallocated only when the
87  /// predecessor becomes empty.
88  struct StackChunk {
89    StackChunk *Next;
90    StackChunk *Prev;
91    char *End;
92
93    StackChunk(StackChunk *Prev = nullptr)
94        : Next(nullptr), Prev(Prev), End(reinterpret_cast<char *>(this + 1)) {}
95
96    /// Returns the size of the chunk, minus the header.
97    size_t size() { return End - start(); }
98
99    /// Returns a pointer to the start of the data region.
100    char *start() { return reinterpret_cast<char *>(this + 1); }
101  };
102  static_assert(sizeof(StackChunk) < ChunkSize, "Invalid chunk size");
103
104  /// First chunk on the stack.
105  StackChunk *Chunk = nullptr;
106  /// Total size of the stack.
107  size_t StackSize = 0;
108};
109
110} // namespace interp
111} // namespace clang
112
113#endif
114