InterpStack.h

Go to the documentation of this file.

//===--- InterpStack.h - Stack implementation for the VM --------*- 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
//
//===----------------------------------------------------------------------===//
//
// Defines the upwards-growing stack used by the interpreter.
//
//===----------------------------------------------------------------------===//
 
#ifndef LLVM_CLANG_AST_INTERP_INTERPSTACK_H
#define LLVM_CLANG_AST_INTERP_INTERPSTACK_H
 
#include "FixedPoint.h"
#include "IntegralAP.h"
#include "MemberPointer.h"
#include "PrimType.h"
#include "Reflect.h"
 
namespace clang {
namespace interp {
 
/// Stack frame storing temporaries and parameters.
class InterpStack final {
public:
  InterpStack() = default;
 
  /// Destroys the stack, freeing up storage.
  ~InterpStack();
 
  /// Constructs a value in place on the top of the stack.
  template <typename T, typename... Tys> void push(Tys &&...Args) {
    new (grow<aligned_size<T>()>()) T(std::forward<Tys>(Args)...);
    ItemTypes.push_back(toPrimType<T>());
  }
 
  /// Returns the value from the top of the stack and removes it.
  template <typename T> T pop() {
    assert(!ItemTypes.empty());
    assert(ItemTypes.back() == toPrimType<T>());
    ItemTypes.pop_back();
    T *Ptr = &peekInternal<T>();
    T Value = std::move(*Ptr);
    shrink(aligned_size<T>());
    return Value;
  }
 
  /// Discards the top value from the stack.
  template <typename T> void discard() {
    assert(!ItemTypes.empty());
    assert(ItemTypes.back() == toPrimType<T>());
    ItemTypes.pop_back();
    T *Ptr = &peekInternal<T>();
    if constexpr (!std::is_trivially_destructible_v<T>) {
      Ptr->~T();
    }
    shrink(aligned_size<T>());
  }
  void discardSlow();
 
  /// Returns a reference to the value on the top of the stack.
  template <typename T> T &peek() const {
    assert(!ItemTypes.empty());
    assert(ItemTypes.back() == toPrimType<T>());
    return peekInternal<T>();
  }
 
  template <typename T> T &peek(size_t Offset) const {
    assert(aligned(Offset));
    return *reinterpret_cast<T *>(peekData(Offset));
  }
 
  /// Returns a pointer to the top object.
  void *top() const { return Chunk ? peekData(0) : nullptr; }
 
  /// Returns the size of the stack in bytes.
  size_t size() const { return StackSize; }
 
  /// Clears the stack.
  void clear();
  void clearTo(size_t NewSize);
 
  /// Returns whether the stack is empty.
  bool empty() const { return StackSize == 0; }
 
  /// dump the stack contents to stderr.
  void dump() const;
 
private:
  /// All stack slots are aligned to the native pointer alignment for storage.
  /// The size of an object is rounded up to a pointer alignment multiple.
  template <typename T> static constexpr size_t aligned_size() {
    constexpr size_t PtrAlign = alignof(void *);
    return ((sizeof(T) + PtrAlign - 1) / PtrAlign) * PtrAlign;
  }
 
  /// Like the public peek(), but without the debug type checks.
  template <typename T> T &peekInternal() const {
    return *reinterpret_cast<T *>(peekData(aligned_size<T>()));
  }
 
  /// Grows the stack to accommodate a value and returns a pointer to it.
  template <size_t Size> void *grow() {
    assert(Size < ChunkSize - sizeof(StackChunk) && "Object too large");
    static_assert(aligned(Size));
 
    // Allocate a new stack chunk if necessary.
    if (LLVM_UNLIKELY(!Chunk)) {
      Chunk = new (std::malloc(ChunkSize)) StackChunk(Chunk);
    } else if (LLVM_UNLIKELY(Chunk->size() >
                             ChunkSize - sizeof(StackChunk) - Size)) {
      if (Chunk->Next) {
        Chunk = Chunk->Next;
      } else {
        StackChunk *Next = new (std::malloc(ChunkSize)) StackChunk(Chunk);
        Chunk->Next = Next;
        Chunk = Next;
      }
    }
 
    auto *Object = reinterpret_cast<void *>(Chunk->start() + Chunk->Size);
    Chunk->Size += Size;
    StackSize += Size;
    return Object;
  }
 
  void *peekDataSlow(size_t Size) const;
  /// Returns a pointer from the top of the stack.
  void *peekData(size_t Size) const {
    assert(Chunk && "Stack is empty!");
    if (LLVM_LIKELY(Size <= Chunk->size()))
      return reinterpret_cast<void *>(Chunk->start() + Chunk->Size - Size);
 
    return peekDataSlow(Size);
  }
 
  void shrinkSlow(size_t Size);
  /// Shrinks the stack.
  void shrink(size_t Size) {
    assert(Chunk && "Chunk is empty!");
 
    // Likely case is that we simply remove something from the current chunk.
    if (LLVM_LIKELY(Size <= Chunk->size())) {
      Chunk->Size -= Size;
      StackSize -= Size;
      return;
    }
 
    shrinkSlow(Size);
  }
 
  /// Allocate stack space in 1Mb chunks.
  static constexpr size_t ChunkSize = 1024 * 1024;
 
  /// Metadata for each stack chunk.
  ///
  /// The stack is composed of a linked list of chunks. Whenever an allocation
  /// is out of bounds, a new chunk is linked. When a chunk becomes empty,
  /// it is not immediately freed: a chunk is deallocated only when the
  /// predecessor becomes empty.
  struct StackChunk {
    StackChunk *Next;
    StackChunk *Prev;
    uint32_t Size;
 
    StackChunk(StackChunk *Prev = nullptr)
        : Next(nullptr), Prev(Prev), Size(0) {}
 
    /// Returns the size of the chunk, minus the header.
    size_t size() const { return Size; }
 
    /// Returns a pointer to the start of the data region.
    char *start() { return reinterpret_cast<char *>(this + 1); }
    const char *start() const {
      return reinterpret_cast<const char *>(this + 1);
    }
  };
  static_assert(sizeof(StackChunk) < ChunkSize, "Invalid chunk size");
 
  /// First chunk on the stack.
  StackChunk *Chunk = nullptr;
  /// Total size of the stack.
  size_t StackSize = 0;
 
  /// SmallVector recording the type of data we pushed into the stack.
  /// We don't usually need this during normal code interpretation but
  /// when aborting, we need type information to call the destructors
  /// for what's left on the stack.
  llvm::SmallVector<PrimType> ItemTypes;
 
  template <typename T> static constexpr PrimType toPrimType() {
    if constexpr (std::is_same_v<T, Pointer>)
      return PT_Ptr;
    else if constexpr (std::is_same_v<T, bool> || std::is_same_v<T, Boolean>)
      return PT_Bool;
    else if constexpr (std::is_same_v<T, int8_t> ||
                       std::is_same_v<T, Char<true>>)
      return PT_Sint8;
    else if constexpr (std::is_same_v<T, uint8_t> ||
                       std::is_same_v<T, Char<false>>)
      return PT_Uint8;
    else if constexpr (std::is_same_v<T, Integral<16, true>>)
      return PT_Sint16;
    else if constexpr (std::is_same_v<T, Integral<16, false>>)
      return PT_Uint16;
    else if constexpr (std::is_same_v<T, Integral<32, true>>)
      return PT_Sint32;
    else if constexpr (std::is_same_v<T, Integral<32, false>>)
      return PT_Uint32;
    else if constexpr (std::is_same_v<T, Integral<64, true>>)
      return PT_Sint64;
    else if constexpr (std::is_same_v<T, Integral<64, false>>)
      return PT_Uint64;
 
    else if constexpr (std::is_same_v<T, Floating>)
      return PT_Float;
    else if constexpr (std::is_same_v<T, IntegralAP<true>>)
      return PT_IntAP;
    else if constexpr (std::is_same_v<T, IntegralAP<false>>)
      return PT_IntAP;
    else if constexpr (std::is_same_v<T, MemberPointer>)
      return PT_MemberPtr;
    else if constexpr (std::is_same_v<T, FixedPoint>)
      return PT_FixedPoint;
    else if constexpr (std::is_same_v<T, Reflect>)
      return PT_Reflect;
 
    llvm_unreachable("unknown type push()'ed into InterpStack");
  }
};
 
} // namespace interp
} // namespace clang
 
#endif