clang  16.0.0git
InterpStack.h
Go to the documentation of this file.
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 "PrimType.h"
17 #include <memory>
18 #include <vector>
19 
20 namespace clang {
21 namespace interp {
22 
23 /// Stack frame storing temporaries and parameters.
24 class InterpStack final {
25 public:
27 
28  /// Destroys the stack, freeing up storage.
29  ~InterpStack();
30 
31  /// Constructs a value in place on the top of the stack.
32  template <typename T, typename... Tys> void push(Tys &&... Args) {
33  new (grow(aligned_size<T>())) T(std::forward<Tys>(Args)...);
34 #ifndef NDEBUG
35  ItemTypes.push_back(toPrimType<T>());
36 #endif
37  }
38 
39  /// Returns the value from the top of the stack and removes it.
40  template <typename T> T pop() {
41 #ifndef NDEBUG
42  assert(!ItemTypes.empty());
43  assert(ItemTypes.back() == toPrimType<T>());
44  ItemTypes.pop_back();
45 #endif
46  auto *Ptr = &peek<T>();
47  auto Value = std::move(*Ptr);
48  Ptr->~T();
49  shrink(aligned_size<T>());
50  return Value;
51  }
52 
53  /// Discards the top value from the stack.
54  template <typename T> void discard() {
55 #ifndef NDEBUG
56  assert(ItemTypes.back() == toPrimType<T>());
57  ItemTypes.pop_back();
58 #endif
59  auto *Ptr = &peek<T>();
60  Ptr->~T();
61  shrink(aligned_size<T>());
62  }
63 
64  /// Returns a reference to the value on the top of the stack.
65  template <typename T> T &peek() const {
66  return *reinterpret_cast<T *>(peek(aligned_size<T>()));
67  }
68 
69  /// Returns a pointer to the top object.
70  void *top() const { return Chunk ? peek(0) : nullptr; }
71 
72  /// Returns the size of the stack in bytes.
73  size_t size() const { return StackSize; }
74 
75  /// Clears the stack without calling any destructors.
76  void clear();
77 
78  // Returns whether the stack is empty.
79  bool empty() const { return StackSize == 0; }
80 
81 private:
82  /// All stack slots are aligned to the native pointer alignment for storage.
83  /// The size of an object is rounded up to a pointer alignment multiple.
84  template <typename T> constexpr size_t aligned_size() const {
85  constexpr size_t PtrAlign = alignof(void *);
86  return ((sizeof(T) + PtrAlign - 1) / PtrAlign) * PtrAlign;
87  }
88 
89  /// Grows the stack to accommodate a value and returns a pointer to it.
90  void *grow(size_t Size);
91  /// Returns a pointer from the top of the stack.
92  void *peek(size_t Size) const;
93  /// Shrinks the stack.
94  void shrink(size_t Size);
95 
96  /// Allocate stack space in 1Mb chunks.
97  static constexpr size_t ChunkSize = 1024 * 1024;
98 
99  /// Metadata for each stack chunk.
100  ///
101  /// The stack is composed of a linked list of chunks. Whenever an allocation
102  /// is out of bounds, a new chunk is linked. When a chunk becomes empty,
103  /// it is not immediately freed: a chunk is deallocated only when the
104  /// predecessor becomes empty.
105  struct StackChunk {
106  StackChunk *Next;
107  StackChunk *Prev;
108  char *End;
109 
110  StackChunk(StackChunk *Prev = nullptr)
111  : Next(nullptr), Prev(Prev), End(reinterpret_cast<char *>(this + 1)) {}
112 
113  /// Returns the size of the chunk, minus the header.
114  size_t size() const { return End - start(); }
115 
116  /// Returns a pointer to the start of the data region.
117  char *start() { return reinterpret_cast<char *>(this + 1); }
118  const char *start() const {
119  return reinterpret_cast<const char *>(this + 1);
120  }
121  };
122  static_assert(sizeof(StackChunk) < ChunkSize, "Invalid chunk size");
123 
124  /// First chunk on the stack.
125  StackChunk *Chunk = nullptr;
126  /// Total size of the stack.
127  size_t StackSize = 0;
128 
129 #ifndef NDEBUG
130  /// vector recording the type of data we pushed into the stack.
131  std::vector<PrimType> ItemTypes;
132 
133  template <typename T> static constexpr PrimType toPrimType() {
134  if constexpr (std::is_same_v<T, Pointer>)
135  return PT_Ptr;
136  else if constexpr (std::is_same_v<T, bool> ||
137  std::is_same_v<T, Boolean>)
138  return PT_Bool;
139  else if constexpr (std::is_same_v<T, int8_t> ||
140  std::is_same_v<T, Integral<8, true>>)
142  else if constexpr (std::is_same_v<T, uint8_t> ||
143  std::is_same_v<T, Integral<8, false>>)
145  else if constexpr (std::is_same_v<T, int16_t> ||
146  std::is_same_v<T, Integral<16, true>>)
148  else if constexpr (std::is_same_v<T, uint16_t> ||
149  std::is_same_v<T, Integral<16, false>>)
151  else if constexpr (std::is_same_v<T, int32_t> ||
152  std::is_same_v<T, Integral<32, true>>)
154  else if constexpr (std::is_same_v<T, uint32_t> ||
155  std::is_same_v<T, Integral<32, false>>)
157  else if constexpr (std::is_same_v<T, int64_t> ||
158  std::is_same_v<T, Integral<64, true>>)
160  else if constexpr (std::is_same_v<T, uint64_t> ||
161  std::is_same_v<T, Integral<64, false>>)
163 
164  llvm_unreachable("unknown type push()'ed into InterpStack");
165  }
166 #endif
167 };
168 
169 } // namespace interp
170 } // namespace clang
171 
172 #endif
clang::interp::InterpStack::size
size_t size() const
Returns the size of the stack in bytes.
Definition: InterpStack.h:73
clang::interp::InterpStack::discard
void discard()
Discards the top value from the stack.
Definition: InterpStack.h:54
return
return(__x >> __y)|(__x<<(32 - __y))
clang::if
if(T->getSizeExpr()) TRY_TO(TraverseStmt(T -> getSizeExpr()))
Definition: RecursiveASTVisitor.h:1081
clang::ast_matchers::type
const internal::VariadicAllOfMatcher< Type > type
Matches Types in the clang AST.
Definition: ASTMatchersInternal.cpp:773
clang::interp::PT_Uint16
@ PT_Uint16
Definition: PrimType.h:32
End
SourceLocation End
Definition: USRLocFinder.cpp:167
clang::interp::InterpStack::InterpStack
InterpStack()
Definition: InterpStack.h:26
clang::interp::InterpStack::pop
T pop()
Returns the value from the top of the stack and removes it.
Definition: InterpStack.h:40
clang::interp::PT_Sint16
@ PT_Sint16
Definition: PrimType.h:31
clang::interp::InterpStack::clear
void clear()
Clears the stack without calling any destructors.
Definition: InterpStack.cpp:20
clang::interp::InterpStack::push
void push(Tys &&... Args)
Constructs a value in place on the top of the stack.
Definition: InterpStack.h:32
hlsl::uint64_t
unsigned long uint64_t
Definition: hlsl_basic_types.h:25
clang::interp::PT_Bool
@ PT_Bool
Definition: PrimType.h:37
clang::interp::PT_Uint32
@ PT_Uint32
Definition: PrimType.h:34
clang::interp::PrimType
PrimType
Enumeration of the primitive types of the VM.
Definition: PrimType.h:28
PrimType.h
clang::interp::InterpStack::empty
bool empty() const
Definition: InterpStack.h:79
false
#define false
Definition: stdbool.h:22
Value
Value
Definition: UninitializedValues.cpp:103
clang::interp::PT_Uint8
@ PT_Uint8
Definition: PrimType.h:30
clang::interp::InterpStack
Stack frame storing temporaries and parameters.
Definition: InterpStack.h:24
clang::interp::InterpStack::~InterpStack
~InterpStack()
Destroys the stack, freeing up storage.
Definition: InterpStack.cpp:16
clang::interp::PT_Sint32
@ PT_Sint32
Definition: PrimType.h:33
std
Definition: Format.h:4477
clang::interp::PT_Sint8
@ PT_Sint8
Definition: PrimType.h:29
clang
Definition: CalledOnceCheck.h:17
hlsl::int64_t
long int64_t
Definition: hlsl_basic_types.h:26
clang::interp::PT_Uint64
@ PT_Uint64
Definition: PrimType.h:36
clang::interp::PT_Sint64
@ PT_Sint64
Definition: PrimType.h:35
clang::interp::PT_Ptr
@ PT_Ptr
Definition: PrimType.h:38
true
#define true
Definition: stdbool.h:21
clang::interp::InterpStack::top
void * top() const
Returns a pointer to the top object.
Definition: InterpStack.h:70
clang::interp::InterpStack::peek
T & peek() const
Returns a reference to the value on the top of the stack.
Definition: InterpStack.h:65