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[1].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
179 // LOAD_SYMBOL sym
180 // TYPE
181 // LOAD_CONST cst
182 // EQ
183 // ---> CHECK_TYPE_OF sym, cst
184 // also works with LOAD_CONST cst, LOAD_SYMBOL sym, TYPE, EQ, but args will be flipped
185 Rule { { LOAD_SYMBOL, TYPE, LOAD_CONST, EQ }, [](const Entities e) {
186 return IR::Entity(CHECK_TYPE_OF, e[0].primaryArg(), e[2].primaryArg());
187 } },
188 Rule { { LOAD_CONST, LOAD_SYMBOL, TYPE, EQ }, [](const Entities e) {
189 return IR::Entity(CHECK_TYPE_OF, e[1].primaryArg(), e[0].primaryArg());
190 } },
191 Rule { { LOAD_SYMBOL_BY_INDEX, TYPE, LOAD_CONST, EQ }, [](const Entities e) {
192 return IR::Entity(CHECK_TYPE_OF_BY_INDEX, e[0].primaryArg(), e[2].primaryArg());
193 } },
194 Rule { { LOAD_CONST, LOAD_SYMBOL_BY_INDEX, TYPE, EQ }, [](const Entities e) {
195 return IR::Entity(CHECK_TYPE_OF_BY_INDEX, e[1].primaryArg(), e[0].primaryArg());
196 } },
197 };
198 }
199
200 void IROptimizer::process(const std::vector<IR::Block>& pages, const std::vector<std::string>& symbols, const std::vector<ValTableElem>& values)
201 {
202 m_logger.traceStart("process");
203 m_symbols = symbols;
204 m_values = values;
205
206 for (const auto& block : pages)
207 {
208 m_ir.emplace_back();
209 IR::Block& current_block = m_ir.back();
210
211 std::size_t i = 0;
212 const std::size_t end = block.size();
213
214 while (i < end)
215 {
216 std::optional<EntityWithOffset> maybe_compacted = replaceWithRules(
217 m_ruleset,
218 std::span(
219 block.begin() + static_cast<IR::Block::difference_type>(i),
220 block.size() - i));
221
222 if (maybe_compacted.has_value())
223 {
224 auto [entity, offset] = maybe_compacted.value();
225 current_block.emplace_back(entity);
226 i += offset;
227 }
228 else
229 {
230 current_block.emplace_back(block[i]);
231 ++i;
232 }
233 }
234 }
235
237 }
238
239 const std::vector<IR::Block>& IROptimizer::intermediateRepresentation() const noexcept
240 {
241 return m_ir;
242 }
243
244 bool IROptimizer::match(const std::vector<Instruction>& expected_insts, const std::span<const IR::Entity> entities) const
245 {
246 if (expected_insts.size() > entities.size())
247 return false;
248
249 for (std::size_t i = 0; i < expected_insts.size(); ++i)
250 {
251 if (expected_insts[i] != entities[i].inst())
252 return false;
253 }
254
255 return true;
256 }
257
258 bool IROptimizer::canBeOptimizedSafely(std::span<const IR::Entity> entities, std::size_t window_size) const
259 {
260 // check that we can actually safely apply the optimization on the given instructions
261 return std::ranges::none_of(
262 entities | std::ranges::views::take(window_size),
263 [](const IR::Entity& entity) {
264 return entity.primaryArg() > IR::MaxValueForDualArg;
265 });
266 }
267
268 std::optional<EntityWithOffset> IROptimizer::replaceWithRules(const std::vector<Rule>& rules, const std::span<const IR::Entity> entities)
269 {
270 for (const auto& [expected, condition, createReplacement] : rules)
271 {
272 if (match(expected, entities) && condition(entities))
273 {
274 const std::size_t window_size = expected.size();
275 if (!canBeOptimizedSafely(entities, window_size))
276 return std::nullopt; // no need to try other optimizations, they won't be applied either
277
278 auto output = createReplacement(entities);
279
280 if (const auto it = std::ranges::find_if(entities, [](const auto& entity) {
281 return entity.hasValidSourceLocation();
282 });
283 it != entities.end())
284 output.setSourceLocation(it->filename(), it->sourceLine());
285
286 return EntityWithOffset { output, window_size };
287 }
288 }
289
290 return std::nullopt;
291 }
292
293 bool IROptimizer::isPositiveNumberInlinable(const uint16_t id) const
294 {
295 if (std::cmp_less(id, m_values.size()) && m_values[id].type == ValTableElemType::Number)
296 {
297 const double val = std::get<double>(m_values[id].value);
298 return val >= 0.0 &&
300 static_cast<double>(static_cast<long>(val)) == val;
301 }
302 return false;
303 }
304
305 uint16_t IROptimizer::numberAsArg(const uint16_t id) const
306 {
307 return static_cast<uint16_t>(std::get<double>(m_values[id].value));
308 }
309}
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