ArkScript
A small, lisp-inspired, functional scripting language
IROptimizer.cpp
Go to the documentation of this file.
2
3#include <cassert>
4#include <utility>
5#include <ranges>
6#include <algorithm>
7
9
10namespace Ark::internal
11{
12 IROptimizer::IROptimizer(const unsigned debug) :
13 m_logger("IROptimizer", debug)
14 {
15 m_ruleset = {
24 return Builtins::builtins[entities[3].primaryArg()].second.isFunction();
25 },
26 [](const Entities e) {
27 return IR::Entity(CALL_BUILTIN_WITHOUT_RETURN_ADDRESS, e[3].primaryArg(), 1);
28 } },
30 return Builtins::builtins[entities[5].primaryArg()].second.isFunction();
31 },
32 [](const Entities e) {
33 return IR::Entity(CALL_BUILTIN_WITHOUT_RETURN_ADDRESS, e[5].primaryArg(), 2);
34 } },
36 return Builtins::builtins[entities[7].primaryArg()].second.isFunction();
37 },
38 [](const Entities e) {
39 return IR::Entity(CALL_BUILTIN_WITHOUT_RETURN_ADDRESS, e[7].primaryArg(), 3);
40 } },
41 Rule { { BUILTIN, CALL }, CALL_BUILTIN, [](const Entities entities) {
42 return Builtins::builtins[entities[0].primaryArg()].second.isFunction();
43 } },
48 Rule { { LIST, STORE }, STORE_LIST },
51 // LOAD_SYMBOL a / LOAD_SYMBOL_BY_INDEX index
52 // LOAD_CONST n (1)
53 // ADD / SUB
54 // STORE
55 // ---> INCREMENT_STORE / DECREMENT_STORE a value
56 Rule { { LOAD_CONST, LOAD_SYMBOL, ADD, SET_VAL }, [this](const Entities e) {
57 return isPositiveNumberInlinable(e[0].primaryArg()) && e[1].primaryArg() == e[3].primaryArg();
58 },
59 [this](const Entities e) {
60 return IR::Entity(INCREMENT_STORE, e[1].primaryArg(), numberAsArg(e[0].primaryArg()));
61 } },
62 Rule { { LOAD_SYMBOL, LOAD_CONST, ADD, SET_VAL }, [this](const Entities e) {
63 return isPositiveNumberInlinable(e[1].primaryArg()) && e[0].primaryArg() == e[3].primaryArg();
64 },
65 [this](const Entities e) {
66 return IR::Entity(INCREMENT_STORE, e[0].primaryArg(), numberAsArg(e[1].primaryArg()));
67 } },
68 Rule { { LOAD_SYMBOL, LOAD_CONST, SUB, SET_VAL }, [this](const Entities e) {
69 return isPositiveNumberInlinable(e[1].primaryArg()) && e[0].primaryArg() == e[3].primaryArg();
70 },
71 [this](const Entities e) {
72 return IR::Entity(DECREMENT_STORE, e[0].primaryArg(), numberAsArg(e[1].primaryArg()));
73 } },
74 // without the final store, just increment/decrement
75 Rule { { LOAD_CONST, LOAD_SYMBOL, ADD }, [this](const Entities e) {
76 return isPositiveNumberInlinable(e[0].primaryArg());
77 },
78 [this](const Entities e) {
79 return IR::Entity(INCREMENT, e[1].primaryArg(), numberAsArg(e[0].primaryArg()));
80 } },
81 Rule { { LOAD_SYMBOL, LOAD_CONST, ADD }, [this](const Entities e) {
82 return isPositiveNumberInlinable(e[1].primaryArg());
83 },
84 [this](const Entities e) {
85 return IR::Entity(INCREMENT, e[0].primaryArg(), numberAsArg(e[1].primaryArg()));
86 } },
87 Rule { { LOAD_SYMBOL, LOAD_CONST, SUB }, [this](const Entities e) {
88 return isPositiveNumberInlinable(e[1].primaryArg());
89 },
90 [this](const Entities e) {
91 return IR::Entity(DECREMENT, e[0].primaryArg(), numberAsArg(e[1].primaryArg()));
92 } },
93 Rule { { LOAD_CONST, LOAD_SYMBOL_BY_INDEX, ADD }, [this](const Entities e) {
94 return isPositiveNumberInlinable(e[0].primaryArg());
95 },
96 [this](const Entities e) {
97 return IR::Entity(INCREMENT_BY_INDEX, e[1].primaryArg(), numberAsArg(e[0].primaryArg()));
98 } },
99 Rule { { LOAD_SYMBOL_BY_INDEX, LOAD_CONST, ADD }, [this](const Entities e) {
100 return isPositiveNumberInlinable(e[1].primaryArg());
101 },
102 [this](const Entities e) {
103 return IR::Entity(INCREMENT_BY_INDEX, e[0].primaryArg(), numberAsArg(e[1].primaryArg()));
104 } },
105 Rule { { LOAD_SYMBOL_BY_INDEX, LOAD_CONST, SUB }, [this](const Entities e) {
106 return isPositiveNumberInlinable(e[1].primaryArg());
107 },
108 [this](const Entities e) {
109 return IR::Entity(DECREMENT_BY_INDEX, e[0].primaryArg(), numberAsArg(e[1].primaryArg()));
110 } },
111 // LOAD_SYMBOL list
112 // TAIL / HEAD
113 // STORE / SET_VAL a
114 // ---> STORE_TAIL list a ; STORE_HEAD ; SET_VAL_TAIL ; SET_VAL_HEAD
115 Rule { { LOAD_SYMBOL, TAIL, STORE }, [](const Entities e) {
116 return IR::Entity(STORE_TAIL, e[0].primaryArg(), e[2].primaryArg());
117 } },
118 Rule { { LOAD_SYMBOL, TAIL, SET_VAL }, [](const Entities e) {
119 return IR::Entity(SET_VAL_TAIL, e[0].primaryArg(), e[2].primaryArg());
120 } },
121 Rule { { LOAD_SYMBOL, HEAD, STORE }, [](const Entities e) {
122 return IR::Entity(STORE_HEAD, e[0].primaryArg(), e[2].primaryArg());
123 } },
124 Rule { { LOAD_SYMBOL, HEAD, SET_VAL }, [](const Entities e) {
125 return IR::Entity(SET_VAL_HEAD, e[0].primaryArg(), e[2].primaryArg());
126 } },
127 Rule { { LOAD_SYMBOL_BY_INDEX, TAIL, STORE }, [](const Entities e) {
128 return IR::Entity(STORE_TAIL_BY_INDEX, e[0].primaryArg(), e[2].primaryArg());
129 } },
130 Rule { { LOAD_SYMBOL_BY_INDEX, TAIL, SET_VAL }, [](const Entities e) {
131 return IR::Entity(SET_VAL_TAIL_BY_INDEX, e[0].primaryArg(), e[2].primaryArg());
132 } },
133 Rule { { LOAD_SYMBOL_BY_INDEX, HEAD, STORE }, [](const Entities e) {
134 return IR::Entity(STORE_HEAD_BY_INDEX, e[0].primaryArg(), e[2].primaryArg());
135 } },
136 Rule { { LOAD_SYMBOL_BY_INDEX, HEAD, SET_VAL }, [](const Entities e) {
137 return IR::Entity(SET_VAL_HEAD_BY_INDEX, e[0].primaryArg(), e[2].primaryArg());
138 } },
139 // LOAD_CONST id / LOAD_SYMBOL id
140 // <comparison operator>
141 // POP_JUMP_IF_(FALSE|TRUE)
142 // ---> <OP>_(CONST|SYM)_JUMP_IF_(FALSE|TRUE)
143 Rule { { LOAD_CONST, LT, POP_JUMP_IF_FALSE }, [](const Entities e) {
144 return IR::Entity::GotoWithArg(e[2], LT_CONST_JUMP_IF_FALSE, e[0].primaryArg());
145 } },
146 Rule { { LOAD_CONST, LT, POP_JUMP_IF_TRUE }, [](const Entities e) {
147 return IR::Entity::GotoWithArg(e[2], LT_CONST_JUMP_IF_TRUE, e[0].primaryArg());
148 } },
149 Rule { { LOAD_SYMBOL, LT, POP_JUMP_IF_FALSE }, [](const Entities e) {
150 return IR::Entity::GotoWithArg(e[2], LT_SYM_JUMP_IF_FALSE, e[0].primaryArg());
151 } },
152 Rule { { LOAD_CONST, GT, POP_JUMP_IF_TRUE }, [](const Entities e) {
153 return IR::Entity::GotoWithArg(e[2], GT_CONST_JUMP_IF_TRUE, e[0].primaryArg());
154 } },
155 Rule { { LOAD_CONST, GT, POP_JUMP_IF_FALSE }, [](const Entities e) {
156 return IR::Entity::GotoWithArg(e[2], GT_CONST_JUMP_IF_FALSE, e[0].primaryArg());
157 } },
158 Rule { { LOAD_SYMBOL, GT, POP_JUMP_IF_FALSE }, [](const Entities e) {
159 return IR::Entity::GotoWithArg(e[2], GT_SYM_JUMP_IF_FALSE, e[0].primaryArg());
160 } },
161 Rule { { LOAD_CONST, EQ, POP_JUMP_IF_TRUE }, [](const Entities e) {
162 return IR::Entity::GotoWithArg(e[2], EQ_CONST_JUMP_IF_TRUE, e[0].primaryArg());
163 } },
165 return IR::Entity::GotoWithArg(e[2], EQ_SYM_INDEX_JUMP_IF_TRUE, e[0].primaryArg());
166 } },
167 Rule { { LOAD_CONST, NEQ, POP_JUMP_IF_TRUE }, [](const Entities e) {
168 return IR::Entity::GotoWithArg(e[2], NEQ_CONST_JUMP_IF_TRUE, e[0].primaryArg());
169 } },
170 Rule { { LOAD_SYMBOL, NEQ, POP_JUMP_IF_FALSE }, [](const Entities e) {
171 return IR::Entity::GotoWithArg(e[2], NEQ_SYM_JUMP_IF_FALSE, e[0].primaryArg());
172 } },
173 // LOAD_SYMBOL id
174 // LOAD_SYMBOL id2
175 // AT
176 // ---> AT_SYM_SYM id id2
180 // LOAD_SYMBOL sym
181 // TYPE
182 // LOAD_CONST cst
183 // EQ
184 // ---> CHECK_TYPE_OF sym, cst
185 // also works with LOAD_CONST cst, LOAD_SYMBOL sym, TYPE, EQ, but args will be flipped
186 Rule { { LOAD_SYMBOL, TYPE, LOAD_CONST, EQ }, [](const Entities e) {
187 return IR::Entity(CHECK_TYPE_OF, e[0].primaryArg(), e[2].primaryArg());
188 } },
189 Rule { { LOAD_CONST, LOAD_SYMBOL, TYPE, EQ }, [](const Entities e) {
190 return IR::Entity(CHECK_TYPE_OF, e[1].primaryArg(), e[0].primaryArg());
191 } },
192 Rule { { LOAD_SYMBOL_BY_INDEX, TYPE, LOAD_CONST, EQ }, [](const Entities e) {
193 return IR::Entity(CHECK_TYPE_OF_BY_INDEX, e[0].primaryArg(), e[2].primaryArg());
194 } },
195 Rule { { LOAD_CONST, LOAD_SYMBOL_BY_INDEX, TYPE, EQ }, [](const Entities e) {
196 return IR::Entity(CHECK_TYPE_OF_BY_INDEX, e[1].primaryArg(), e[0].primaryArg());
197 } },
198 // ---
199 Rule { { LOAD_SYMBOL_BY_INDEX, LEN, STORE }, [](const Entities e) {
200 return IR::Entity(STORE_LEN, e[0].primaryArg(), e[2].primaryArg());
201 } },
202 Rule { { LOAD_SYMBOL, LEN, LT, POP_JUMP_IF_FALSE }, [](const Entities e) {
203 return IR::Entity::GotoWithArg(e[3], LT_LEN_SYM_JUMP_IF_FALSE, e[0].primaryArg());
204 } },
205 };
206 }
207
208 void IROptimizer::process(const std::vector<IR::Block>& pages, const std::vector<std::string>& symbols, const std::vector<ValTableElem>& values)
209 {
210 m_logger.traceStart("process");
211 m_symbols = symbols;
212 m_values = values;
213
214 for (const auto& block : pages)
215 {
216 m_ir.emplace_back();
217 IR::Block& current_block = m_ir.back();
218
219 std::size_t i = 0;
220 const std::size_t end = block.size();
221
222 while (i < end)
223 {
224 std::optional<EntityWithOffset> maybe_compacted = replaceWithRules(
225 m_ruleset,
226 std::span(
227 block.begin() + static_cast<IR::Block::difference_type>(i),
228 block.size() - i));
229
230 if (maybe_compacted.has_value())
231 {
232 auto [entity, offset] = maybe_compacted.value();
233 current_block.emplace_back(entity);
234 i += offset;
235 }
236 else
237 {
238 current_block.emplace_back(block[i]);
239 ++i;
240 }
241 }
242 }
243
245 }
246
247 const std::vector<IR::Block>& IROptimizer::intermediateRepresentation() const noexcept
248 {
249 return m_ir;
250 }
251
252 bool IROptimizer::match(const std::vector<Instruction>& expected_insts, const std::span<const IR::Entity> entities) const
253 {
254 if (expected_insts.size() > entities.size())
255 return false;
256
257 for (std::size_t i = 0; i < expected_insts.size(); ++i)
258 {
259 if (expected_insts[i] != entities[i].inst())
260 return false;
261 }
262
263 return true;
264 }
265
266 bool IROptimizer::canBeOptimizedSafely(std::span<const IR::Entity> entities, std::size_t window_size) const
267 {
268 // check that we can actually safely apply the optimization on the given instructions
269 return std::ranges::none_of(
270 entities | std::ranges::views::take(window_size),
271 [](const IR::Entity& entity) {
272 return entity.primaryArg() > IR::MaxValueForDualArg;
273 });
274 }
275
276 std::optional<EntityWithOffset> IROptimizer::replaceWithRules(const std::vector<Rule>& rules, const std::span<const IR::Entity> entities)
277 {
278 for (const auto& [expected, condition, createReplacement] : rules)
279 {
280 if (match(expected, entities) && condition(entities))
281 {
282 const std::size_t window_size = expected.size();
283 if (!canBeOptimizedSafely(entities, window_size))
284 return std::nullopt; // no need to try other optimizations, they won't be applied either
285
286 auto output = createReplacement(entities);
287
288 if (const auto it = std::ranges::find_if(entities, [](const auto& entity) {
289 return entity.hasValidSourceLocation();
290 });
291 it != entities.end())
292 output.setSourceLocation(it->filename(), it->sourceLine());
293
294 return EntityWithOffset { output, window_size };
295 }
296 }
297
298 return std::nullopt;
299 }
300
301 bool IROptimizer::isPositiveNumberInlinable(const uint16_t id) const
302 {
303 if (std::cmp_less(id, m_values.size()) && m_values[id].type == ValTableElemType::Number)
304 {
305 const double val = std::get<double>(m_values[id].value);
306 return val >= 0.0 &&
308 static_cast<double>(static_cast<long>(val)) == val;
309 }
310 return false;
311 }
312
313 uint16_t IROptimizer::numberAsArg(const uint16_t id) const
314 {
315 return static_cast<uint16_t>(std::get<double>(m_values[id].value));
316 }
317}
Host the declaration of all the ArkScript builtins.
Optimize IR based on IR entity grouped by 2 (or more)
std::vector< ValTableElem > m_values
bool isPositiveNumberInlinable(uint16_t id) const
std::vector< IR::Block > m_ir
IROptimizer(unsigned debug)
Create a new IROptimizer.
uint16_t numberAsArg(uint16_t id) const
bool canBeOptimizedSafely(std::span< const IR::Entity > entities, std::size_t window_size) const
std::optional< EntityWithOffset > replaceWithRules(const std::vector< Rule > &rules, std::span< const IR::Entity > entities)
std::span< const IR::Entity > Entities
const std::vector< IR::Block > & intermediateRepresentation() const noexcept
Return the IR blocks (one per scope)
std::vector< Rule > m_ruleset
void process(const std::vector< IR::Block > &pages, const std::vector< std::string > &symbols, const std::vector< ValTableElem > &values)
Turn a given IR into bytecode.
std::vector< std::string > m_symbols
bool match(const std::vector< Instruction > &expected_insts, std::span< const IR::Entity > entities) const
static Entity GotoWithArg(const Entity &label, Instruction inst, uint16_t primary_arg)
Definition Entity.cpp:37
uint16_t primaryArg() const
Definition Entity.hpp:62
void traceStart(std::string &&trace_name)
Definition Logger.hpp:90
ARK_API const std::vector< std::pair< std::string, Value > > builtins
std::vector< Entity > Block
Definition Entity.hpp:84
constexpr uint16_t MaxValueForDualArg
The maximum value an argument can have when an IR entity has two arguments.
Definition Entity.hpp:35
@ CALL_BUILTIN_WITHOUT_RETURN_ADDRESS