Branch data Line data Source code
1 : : #pragma once
2 : :
3 : : #include <cstdint>
4 : : #include <mutable/catalog/Schema.hpp>
5 : : #include <mutable/IR/Tuple.hpp>
6 : :
7 : :
8 : : namespace m {
9 : :
10 : : namespace ast {
11 : :
12 : : struct Expr;
13 : :
14 : : }
15 : :
16 : : namespace cnf {
17 : :
18 : : struct CNF;
19 : :
20 : : }
21 : :
22 : : struct StackMachineBuilder;
23 : :
24 : : /** A stack machine that evaluates an expression. */
25 : : struct StackMachine
26 : : {
27 : : friend struct Interpreter;
28 : : friend struct StackMachineBuilder;
29 : :
30 : : static constexpr std::size_t SIZE_OF_MEMORY = 4 * 1024; // 4 KiB
31 : :
32 : : enum class Opcode : uint8_t
33 : : {
34 : : #define M_OPCODE(CODE, ...) CODE,
35 : : #include "tables/Opcodes.tbl"
36 : : #undef M_OPCODE
37 : : Last
38 : : };
39 : : static_assert(uint64_t(Opcode::Last) < (1UL << (sizeof(Opcode) * 8)), "too many opcodes");
40 : :
41 : : using index_t = std::size_t;
42 : :
43 : : private:
44 : : static constexpr const char *OPCODE_TO_STR[] = {
45 : : #define M_OPCODE(CODE, ...) #CODE,
46 : : #include "tables/Opcodes.tbl"
47 : : #undef M_OPCODE
48 : : };
49 : : static const std::unordered_map<std::string, Opcode> STR_TO_OPCODE;
50 : :
51 : : public:
52 : : static Opcode str_to_opcode(const std::string &str) { return STR_TO_OPCODE.at(str); }
53 : :
54 : : private:
55 : : /*----- The schema of incoming and outgoing tuples. --------------------------------------------------------------*/
56 : : Schema in_schema; ///< schema of the input tuple
57 : : std::vector<const Type*> out_schema; ///< schema of the output tuple
58 : :
59 : : /*----- Fields defining the structure of the machine. ------------------------------------------------------------*/
60 : : std::vector<Opcode> ops; ///< the sequence of operations to perform
61 : : std::vector<Value> context_; ///< the context of the stack machine, e.g. constants or global variables
62 : 2149 : int64_t required_stack_size_ = 0; ///< the required size of the stack
63 : 2149 : int64_t current_stack_size_ = 0; ///< the "current" stack size; i.e. after the last operation is executed
64 : :
65 : : /*----- Fields capturing the internal state during execution. ----------------------------------------------------*/
66 : 2149 : mutable Value *values_ = nullptr; ///< array of values used as a stack
67 : 2149 : mutable bool *null_bits_ = nullptr; ///< array of NULL bits used as a stack
68 : : mutable decltype(ops)::const_iterator op_; ///< the next operation to execute
69 : 2149 : mutable std::size_t top_ = 0; ///< the top of the stack
70 : : mutable uint8_t memory_[SIZE_OF_MEMORY]; ///< memory usable by the stack machine, e.g. to work on BLOBs
71 : :
72 : : public:
73 : : /** Create a `StackMachine` that does not accept input. */
74 : 3342 : StackMachine() { }
75 : :
76 : : /** Create a `StackMachine` with the given input `Schema` `in_schema`. This is the c'tor used when constructing the
77 : : * opcode sequence from the outside. */
78 : 3105 : explicit StackMachine(Schema in_schema) : in_schema(in_schema) { }
79 : :
80 : : /** Create a `StackMachine` with the given input `Schema` `in_schema`, compile the `Expr` `expr`, and emit the
81 : : * result to the output `Tuple` at index `0`. This is a *convenience* c'tor to construct a `StackMachine` that
82 : : * evaluates exactly one expression. */
83 : : StackMachine(Schema in_schema, const ast::Expr &expr);
84 : :
85 : : /** Create a `StackMachine` with the given input `Schema` `in_schema`, compile the `cnf::CNF` `cnf`, and emit the
86 : : * result to the output `Tuple` at index `0`. This is a *convenience* c'tor to construct a `StackMachine` that
87 : : * evaluates exactly one CNF formula. */
88 : : StackMachine(Schema in_schema, const cnf::CNF &cnf);
89 : :
90 : : StackMachine(const StackMachine&) = delete;
91 : 801 : StackMachine(StackMachine&&) = default;
92 : :
93 : 2950 : ~StackMachine() {
94 [ + + ]: 2950 : delete[] values_;
95 [ + + ]: 2950 : delete[] null_bits_;
96 : 2950 : }
97 : :
98 : : /** Returns the `Schema` of input `Tuple`s. */
99 : : const Schema & schema_in() const { return in_schema; }
100 : :
101 : : /** Returns a sequence of `Type`s defining the schema of output `Tuple`s. */
102 : : const std::vector<const Type*> & schema_out() const { return out_schema; }
103 : :
104 : : std::size_t num_ops() const { return ops.size(); }
105 : :
106 : : /** Returns the required size of the stack to evaluate the opcode sequence. */
107 : 446219 : std::size_t required_stack_size() const { return required_stack_size_; }
108 : :
109 : : /** Emit operations evaluating the `Expr` `expr`. */
110 : : void emit(const ast::Expr &expr, std::size_t tuple_id = 0);
111 : :
112 : : /** Emit operations evaluating the `Expr` `expr`. */
113 : : void emit(const ast::Expr &expr, const Schema &schema, std::size_t tuple_id = 0);
114 : :
115 : : /** Emit operations evaluating the `Expr` `expr`. */
116 : : void emit(const ast::Expr &expr,
117 : : std::vector<Schema> &schemas,
118 : : std::vector<std::size_t> &tuple_ids);
119 : :
120 : : /** Emit operations evaluating the `CNF` formula `cnf`. */
121 : : void emit(const cnf::CNF &cnf, std::size_t tuple_id = 0);
122 : :
123 : : /** Emit operations evaluating the `Expr` `expr`. */
124 : : void emit(const cnf::CNF &cnf,
125 : : std::vector<Schema> &schemas,
126 : : std::vector<std::size_t> &tuple_ids);
127 : :
128 : : /* The following macros are used to automatically generate methods to emit a particular opcode. For example, for
129 : : * the opcode `Pop`, we will define a function `emit_Pop()`, that appends the `Pop` opcode to the current opcode
130 : : * sequence. For opcodes that require an argument, a function with the respective parameter is defined and that
131 : : * parameter is inserted into the opcode sequence. For example, the opcode `Ld_Ctx` requires a single parameter
132 : : * with the index of the context value. The macro will expand to the method `emit_Ld_Ctx(uint8_t idx)`, that first
133 : : * appends the `Ld_Ctx` opcode to the opcode sequence and then appends the `idx` parameter to the opcode sequence.
134 : : */
135 : : #define SELECT(XXX, _1, _2, _3, FN, ...) FN(__VA_ARGS__)
136 : : #define ARGS_0(XXX, ...)
137 : : #define ARGS_1(I, XXX, ARG0, ...) uint8_t ARG0
138 : : #define ARGS_2(I, II, XXX, ARG0, ARG1, ...) uint8_t ARG0, uint8_t ARG1
139 : : #define ARGS_3(I, II, III, XXX, ARG0, ARG1, ARG2, ...) uint8_t ARG0, uint8_t ARG1, uint8_t ARG2
140 : : #define ARGS(...) SELECT(__VA_ARGS__, ARGS_3, ARGS_2, ARGS_1, ARGS_0, __VA_ARGS__)
141 : : #define PUSH_0(XXX, ...)
142 : : #define PUSH_1(I, XXX, ARG0, ...) \
143 : : ops.push_back(static_cast<Opcode>((ARG0)));
144 : : #define PUSH_2(I, II, XXX, ARG0, ARG1, ...) \
145 : : ops.push_back(static_cast<Opcode>((ARG0))); \
146 : : ops.push_back(static_cast<Opcode>((ARG1)));
147 : : #define PUSH_3(I, II, III, XXX, ARG0, ARG1, ARG2, ...) \
148 : : ops.push_back(static_cast<Opcode>((ARG0))); \
149 : : ops.push_back(static_cast<Opcode>((ARG1))); \
150 : : ops.push_back(static_cast<Opcode>((ARG2)));
151 : : #define PUSH(...) SELECT(__VA_ARGS__, PUSH_3, PUSH_2, PUSH_1, PUSH_0, __VA_ARGS__)
152 : :
153 : : #define M_OPCODE(CODE, DELTA, ...) \
154 : : void emit_ ## CODE ( ARGS(XXX, ##__VA_ARGS__) ) { \
155 : : ops.push_back(StackMachine::Opcode:: CODE ); \
156 : : current_stack_size_ += DELTA; \
157 : : M_insist(current_stack_size_ >= 0); \
158 : : required_stack_size_ = std::max(required_stack_size_, current_stack_size_); \
159 : : PUSH(XXX, ##__VA_ARGS__) \
160 : : }
161 : :
162 : : #include "tables/Opcodes.tbl"
163 : :
164 : : #undef M_OPCODE
165 : : #undef SELECT
166 : : #undef ARGS_0
167 : : #undef ARGS_1
168 : : #undef ARGS_2
169 : : #undef ARGS
170 : : #undef PUSH_0
171 : : #undef PUSH_1
172 : : #undef PUSH_2
173 : : #undef PUSH
174 : :
175 : : /** Append the given opcode to the opcode sequence. */
176 : 12007 : void emit(Opcode opc) { ops.push_back(opc); }
177 : :
178 : : /** Emit a `Ld_X` instruction based on `Type` `ty`, e.g.\ `Ld_i32` for 4 byte integral types. */
179 : : void emit_Ld(const Type *ty);
180 : :
181 : : /** Emit a `St_X` instruction based on `Type` `ty`, e.g.\ `St_i32` for 4 byte integral types. */
182 : : void emit_St(const Type *ty);
183 : :
184 : : /** Emit a `St_Tup_X` instruction based on `Type` `ty`, e.g.\ `St_Tup_i` for integral `Type`s. */
185 : : void emit_St_Tup(std::size_t tuple_id, std::size_t index, const Type *ty);
186 : :
187 : : /** Emit a `Print_X` instruction based on `Type` `ty`, e.g.\ `Print_i` for integral `Type`s. */
188 : : void emit_Print(std::size_t ostream_index, const Type *ty);
189 : :
190 : : /** Emit opcodes to convert a value of `Type` `from_ty` to `Type` `to_ty`. */
191 : : void emit_Cast(const Type *to_ty, const Type *from_ty);
192 : :
193 : : /** Appends the `Value` `val` to the context and returns its assigned index. */
194 : 44695 : std::size_t add(Value val) {
195 : 44695 : auto idx = context_.size();
196 : 44695 : context_.push_back(val);
197 : 44695 : return idx;
198 : : }
199 : :
200 : : /** Sets the `Value` in the context at index `idx` to `val`. */
201 : : void set(std::size_t idx, Value val) {
202 : : M_insist(idx < context_.size(), "index out of bounds");
203 : : context_[idx] = val;
204 : : }
205 : :
206 : : /** Adds the `Value` `val` to the context and emits a `load` instruction to load this value to the top of the stack.
207 : : */
208 : 36883 : std::size_t add_and_emit_load(Value val) {
209 : 36883 : auto idx = add(val);
210 : 36883 : emit_Ld_Ctx(idx);
211 : 36883 : return idx;
212 : : }
213 : :
214 : : /** Evaluate this `StackMachine` given the `Tuple`s referenced by `tuples`.
215 : : *
216 : : * By convention, the *output* `Tuple`s should be given before the *input* `Tuple`s. However, a `Tuple` can be used
217 : : * for both input and output. */
218 : : void operator()(Tuple **tuples) const;
219 : :
220 : : void dump(std::ostream &out) const;
221 : : void dump() const;
222 : : };
223 : :
224 : : }
|
