20369834167

Committed 19 Dec 2025 12:17PM UTC coverage: 90.661% (-0.1%) from 90.758%

Build # 20369834167

Build Type

push

github

Committed by

SuperFola

Commit Message

feat(ir optimizer, vm): new super instructions MUL_BY, MUL_BY_INDEX and MUL_SET_VAL

Run Details

69 of 86 new or added lines in 2 files covered. (80.23%)

3 existing lines in 1 file now uncovered.

8193 of 9037 relevant lines covered (90.66%)

239488.84 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

95.51

/src/arkreactor/Compiler/IntermediateRepresentation/IROptimizer.cpp

#include <Ark/Compiler/IntermediateRepresentation/IROptimizer.hpp>

#include <cassert>
#include <utility>
#include <ranges>
#include <algorithm>

#include <Ark/Builtins/Builtins.hpp>

namespace Ark::internal
{
    IROptimizer::IROptimizer(const unsigned debug) :
        m_logger("IROptimizer", debug)
    {
        m_ruleset = {
            Rule { { LOAD_CONST, LOAD_CONST }, LOAD_CONST_LOAD_CONST },
            Rule { { LOAD_CONST, STORE }, LOAD_CONST_STORE },
            Rule { { LOAD_CONST, SET_VAL }, LOAD_CONST_SET_VAL },
            Rule { { LOAD_SYMBOL, STORE }, STORE_FROM },
            Rule { { LOAD_SYMBOL_BY_INDEX, STORE }, STORE_FROM_INDEX },
            Rule { { LOAD_SYMBOL, SET_VAL }, SET_VAL_FROM },
            Rule { { LOAD_SYMBOL_BY_INDEX, SET_VAL }, SET_VAL_FROM_INDEX },
            Rule { { STORE, PUSH_RETURN_ADDRESS, LOAD_SYMBOL_BY_INDEX, BUILTIN, CALL },
                   [](const Entities entities, const std::size_t start_idx) {
                       return Builtins::builtins[entities[3].primaryArg()].second.isFunction() && start_idx == 0;
                   },
                   [](const Entities e) {
                       return IR::Entity(CALL_BUILTIN_WITHOUT_RETURN_ADDRESS, e[3].primaryArg(), 1);
                   } },
            Rule { { STORE, STORE, PUSH_RETURN_ADDRESS, LOAD_SYMBOL_BY_INDEX, LOAD_SYMBOL_BY_INDEX, BUILTIN, CALL },
                   [](const Entities entities, const std::size_t start_idx) {
                       return Builtins::builtins[entities[5].primaryArg()].second.isFunction() && start_idx == 0;
                   },
                   [](const Entities e) {
                       return IR::Entity(CALL_BUILTIN_WITHOUT_RETURN_ADDRESS, e[5].primaryArg(), 2);
                   } },
            Rule { { STORE, STORE, STORE, PUSH_RETURN_ADDRESS, LOAD_SYMBOL_BY_INDEX, LOAD_SYMBOL_BY_INDEX, LOAD_SYMBOL_BY_INDEX, BUILTIN, CALL },
                   [](const Entities entities, const std::size_t start_idx) {
                       return Builtins::builtins[entities[7].primaryArg()].second.isFunction() && start_idx == 0;
                   },
                   [](const Entities e) {
                       return IR::Entity(CALL_BUILTIN_WITHOUT_RETURN_ADDRESS, e[7].primaryArg(), 3);
                   } },
            Rule { { BUILTIN, CALL }, CALL_BUILTIN, [](const Entities entities, const std::size_t) {
                      return Builtins::builtins[entities[0].primaryArg()].second.isFunction();
                  } },
            Rule { { LOAD_SYMBOL, CALL }, CALL_SYMBOL },
            Rule { { GET_CURRENT_PAGE_ADDR, CALL }, CALL_CURRENT_PAGE },
            Rule { { LOAD_SYMBOL, GET_FIELD }, GET_FIELD_FROM_SYMBOL },
            Rule { { LOAD_SYMBOL_BY_INDEX, GET_FIELD }, GET_FIELD_FROM_SYMBOL_INDEX },
            Rule { { LIST, STORE }, STORE_LIST },
            Rule { { LOAD_SYMBOL, APPEND_IN_PLACE }, APPEND_IN_PLACE_SYM },
            Rule { { LOAD_SYMBOL_BY_INDEX, APPEND_IN_PLACE }, APPEND_IN_PLACE_SYM_INDEX },
            // LOAD_CONST, LOAD_SYMBOL a, MUL, SET_VAL / LOAD_SYMBOL a, LOAD_CONST, MUL, SET_VAL
            // ---> MUL_SET_VAL a value
            Rule { { LOAD_CONST, LOAD_SYMBOL, MUL, SET_VAL }, [this](const Entities e, const std::size_t) {
                      return isSmallerNumberInlinable(e[0].primaryArg()) && e[1].primaryArg() == e[3].primaryArg();
                  },
                   [this](const Entities e) {
                       return IR::Entity(MUL_SET_VAL, e[1].primaryArg(), smallerNumberAsArg(e[0].primaryArg()));
                   } },
            Rule { { LOAD_SYMBOL, LOAD_CONST, MUL, SET_VAL }, [this](const Entities e, const std::size_t) {
                      return isSmallerNumberInlinable(e[1].primaryArg()) && e[0].primaryArg() == e[3].primaryArg();
                  },
                   [this](const Entities e) {
                       return IR::Entity(MUL_SET_VAL, e[0].primaryArg(), smallerNumberAsArg(e[1].primaryArg()));
                   } },
            // LOAD_CONST, LOAD_SYMBOL a, MUL / LOAD_SYMBOL a, LOAD_CONST, MUL
            // ---> MUL_(BY|BY_INDEX) a value
            Rule { { LOAD_CONST, LOAD_SYMBOL, MUL }, [this](const Entities e, const std::size_t) {
                      return isSmallerNumberInlinable(e[0].primaryArg());
                  },
                   [this](const Entities e) {
                       return IR::Entity(MUL_BY, e[1].primaryArg(), smallerNumberAsArg(e[0].primaryArg()));
                   } },
            Rule { { LOAD_SYMBOL, LOAD_CONST, MUL }, [this](const Entities e, const std::size_t) {
                      return isSmallerNumberInlinable(e[1].primaryArg());
                  },
                   [this](const Entities e) {
                       return IR::Entity(MUL_BY, e[0].primaryArg(), smallerNumberAsArg(e[1].primaryArg()));
                   } },
            Rule { { LOAD_CONST, LOAD_SYMBOL_BY_INDEX, MUL }, [this](const Entities e, const std::size_t) {
                      return isSmallerNumberInlinable(e[0].primaryArg());
                  },
                   [this](const Entities e) {
                       return IR::Entity(MUL_BY_INDEX, e[1].primaryArg(), smallerNumberAsArg(e[0].primaryArg()));
                   } },
            Rule { { LOAD_SYMBOL_BY_INDEX, LOAD_CONST, MUL }, [this](const Entities e, const std::size_t) {
                      return isSmallerNumberInlinable(e[1].primaryArg());
                  },
                   [this](const Entities e) {
                       return IR::Entity(MUL_BY_INDEX, e[0].primaryArg(), smallerNumberAsArg(e[1].primaryArg()));
                   } },
            // (LOAD_SYMBOL a | LOAD_SYMBOL_BY_INDEX index), LOAD_CONST n (=1), (ADD | SUB), STORE
            // ---> INCREMENT_STORE / DECREMENT_STORE a value
            Rule { { LOAD_CONST, LOAD_SYMBOL, ADD, SET_VAL }, [this](const Entities e, const std::size_t) {
                      return isPositiveNumberInlinable(e[0].primaryArg()) && e[1].primaryArg() == e[3].primaryArg();
                  },
                   [this](const Entities e) {
                       return IR::Entity(INCREMENT_STORE, e[1].primaryArg(), numberAsArg(e[0].primaryArg()));
                   } },
            Rule { { LOAD_SYMBOL, LOAD_CONST, ADD, SET_VAL }, [this](const Entities e, const std::size_t) {
                      return isPositiveNumberInlinable(e[1].primaryArg()) && e[0].primaryArg() == e[3].primaryArg();
                  },
                   [this](const Entities e) {
                       return IR::Entity(INCREMENT_STORE, e[0].primaryArg(), numberAsArg(e[1].primaryArg()));
                   } },
            Rule { { LOAD_SYMBOL, LOAD_CONST, SUB, SET_VAL }, [this](const Entities e, const std::size_t) {
                      return isPositiveNumberInlinable(e[1].primaryArg()) && e[0].primaryArg() == e[3].primaryArg();
                  },
                   [this](const Entities e) {
                       return IR::Entity(DECREMENT_STORE, e[0].primaryArg(), numberAsArg(e[1].primaryArg()));
                   } },
            // without the final store, just increment/decrement
            Rule { { LOAD_CONST, LOAD_SYMBOL, ADD }, [this](const Entities e, const std::size_t) {
                      return isPositiveNumberInlinable(e[0].primaryArg());
                  },
                   [this](const Entities e) {
                       return IR::Entity(INCREMENT, e[1].primaryArg(), numberAsArg(e[0].primaryArg()));
                   } },
            Rule { { LOAD_SYMBOL, LOAD_CONST, ADD }, [this](const Entities e, const std::size_t) {
                      return isPositiveNumberInlinable(e[1].primaryArg());
                  },
                   [this](const Entities e) {
                       return IR::Entity(INCREMENT, e[0].primaryArg(), numberAsArg(e[1].primaryArg()));
                   } },
            Rule { { LOAD_SYMBOL, LOAD_CONST, SUB }, [this](const Entities e, const std::size_t) {
                      return isPositiveNumberInlinable(e[1].primaryArg());
                  },
                   [this](const Entities e) {
                       return IR::Entity(DECREMENT, e[0].primaryArg(), numberAsArg(e[1].primaryArg()));
                   } },
            Rule { { LOAD_CONST, LOAD_SYMBOL_BY_INDEX, ADD }, [this](const Entities e, const std::size_t) {
                      return isPositiveNumberInlinable(e[0].primaryArg());
                  },
                   [this](const Entities e) {
                       return IR::Entity(INCREMENT_BY_INDEX, e[1].primaryArg(), numberAsArg(e[0].primaryArg()));
                   } },
            Rule { { LOAD_SYMBOL_BY_INDEX, LOAD_CONST, ADD }, [this](const Entities e, const std::size_t) {
                      return isPositiveNumberInlinable(e[1].primaryArg());
                  },
                   [this](const Entities e) {
                       return IR::Entity(INCREMENT_BY_INDEX, e[0].primaryArg(), numberAsArg(e[1].primaryArg()));
                   } },
            Rule { { LOAD_SYMBOL_BY_INDEX, LOAD_CONST, SUB }, [this](const Entities e, const std::size_t) {
                      return isPositiveNumberInlinable(e[1].primaryArg());
                  },
                   [this](const Entities e) {
                       return IR::Entity(DECREMENT_BY_INDEX, e[0].primaryArg(), numberAsArg(e[1].primaryArg()));
                   } },
            // LOAD_SYMBOL list, (TAIL | HEAD), (STORE | SET_VAL a)
            // ---> STORE_TAIL list a ; STORE_HEAD ; SET_VAL_TAIL ; SET_VAL_HEAD
            Rule { { LOAD_SYMBOL, TAIL, STORE }, [](const Entities e) {
                      return IR::Entity(STORE_TAIL, e[0].primaryArg(), e[2].primaryArg());
                  } },
            Rule { { LOAD_SYMBOL, TAIL, SET_VAL }, [](const Entities e) {
                      return IR::Entity(SET_VAL_TAIL, e[0].primaryArg(), e[2].primaryArg());
                  } },
            Rule { { LOAD_SYMBOL, HEAD, STORE }, [](const Entities e) {
                      return IR::Entity(STORE_HEAD, e[0].primaryArg(), e[2].primaryArg());
                  } },
            Rule { { LOAD_SYMBOL, HEAD, SET_VAL }, [](const Entities e) {
                      return IR::Entity(SET_VAL_HEAD, e[0].primaryArg(), e[2].primaryArg());
                  } },
            Rule { { LOAD_SYMBOL_BY_INDEX, TAIL, STORE }, [](const Entities e) {
                      return IR::Entity(STORE_TAIL_BY_INDEX, e[0].primaryArg(), e[2].primaryArg());
                  } },
            Rule { { LOAD_SYMBOL_BY_INDEX, TAIL, SET_VAL }, [](const Entities e) {
                      return IR::Entity(SET_VAL_TAIL_BY_INDEX, e[0].primaryArg(), e[2].primaryArg());
                  } },
            Rule { { LOAD_SYMBOL_BY_INDEX, HEAD, STORE }, [](const Entities e) {
                      return IR::Entity(STORE_HEAD_BY_INDEX, e[0].primaryArg(), e[2].primaryArg());
                  } },
            Rule { { LOAD_SYMBOL_BY_INDEX, HEAD, SET_VAL }, [](const Entities e) {
                      return IR::Entity(SET_VAL_HEAD_BY_INDEX, e[0].primaryArg(), e[2].primaryArg());
                  } },
            // (LOAD_CONST id | LOAD_SYMBOL id), <comparison operator>, POP_JUMP_IF_(FALSE|TRUE)
            // ---> <OP>_(CONST|SYM)_JUMP_IF_(FALSE|TRUE)
            Rule { { LOAD_CONST, LT, POP_JUMP_IF_FALSE }, [](const Entities e) {
                      return IR::Entity::GotoWithArg(e[2], LT_CONST_JUMP_IF_FALSE, e[0].primaryArg());
                  } },
            Rule { { LOAD_CONST, LT, POP_JUMP_IF_TRUE }, [](const Entities e) {
                      return IR::Entity::GotoWithArg(e[2], LT_CONST_JUMP_IF_TRUE, e[0].primaryArg());
                  } },
            Rule { { LOAD_SYMBOL, LT, POP_JUMP_IF_FALSE }, [](const Entities e) {
                      return IR::Entity::GotoWithArg(e[2], LT_SYM_JUMP_IF_FALSE, e[0].primaryArg());
                  } },
            Rule { { LOAD_CONST, GT, POP_JUMP_IF_TRUE }, [](const Entities e) {
                      return IR::Entity::GotoWithArg(e[2], GT_CONST_JUMP_IF_TRUE, e[0].primaryArg());
                  } },
            Rule { { LOAD_CONST, GT, POP_JUMP_IF_FALSE }, [](const Entities e) {
                      return IR::Entity::GotoWithArg(e[2], GT_CONST_JUMP_IF_FALSE, e[0].primaryArg());
                  } },
            Rule { { LOAD_SYMBOL, GT, POP_JUMP_IF_FALSE }, [](const Entities e) {
                      return IR::Entity::GotoWithArg(e[2], GT_SYM_JUMP_IF_FALSE, e[0].primaryArg());
                  } },
            Rule { { LOAD_CONST, EQ, POP_JUMP_IF_TRUE }, [](const Entities e) {
                      return IR::Entity::GotoWithArg(e[2], EQ_CONST_JUMP_IF_TRUE, e[0].primaryArg());
                  } },
            Rule { { LOAD_SYMBOL_BY_INDEX, EQ, POP_JUMP_IF_TRUE }, [](const Entities e) {
                      return IR::Entity::GotoWithArg(e[2], EQ_SYM_INDEX_JUMP_IF_TRUE, e[0].primaryArg());
                  } },
            Rule { { LOAD_CONST, NEQ, POP_JUMP_IF_TRUE }, [](const Entities e) {
                      return IR::Entity::GotoWithArg(e[2], NEQ_CONST_JUMP_IF_TRUE, e[0].primaryArg());
                  } },
            Rule { { LOAD_SYMBOL, NEQ, POP_JUMP_IF_FALSE }, [](const Entities e) {
                      return IR::Entity::GotoWithArg(e[2], NEQ_SYM_JUMP_IF_FALSE, e[0].primaryArg());
                  } },
            // LOAD_SYMBOL id, LOAD_SYMBOL id2, AT
            // ---> AT_SYM_SYM id id2
            Rule { { LOAD_SYMBOL, LOAD_SYMBOL, AT }, AT_SYM_SYM },
            Rule { { LOAD_SYMBOL_BY_INDEX, LOAD_SYMBOL_BY_INDEX, AT }, AT_SYM_INDEX_SYM_INDEX },
            Rule { { LOAD_SYMBOL_BY_INDEX, LOAD_CONST, AT }, AT_SYM_INDEX_CONST },
            // LOAD_SYMBOL sym, TYPE, LOAD_CONST cst, EQ
            // ---> CHECK_TYPE_OF sym, cst
            // also works with LOAD_CONST cst, LOAD_SYMBOL sym, TYPE, EQ, but args will be flipped
            Rule { { LOAD_SYMBOL, TYPE, LOAD_CONST, EQ }, [](const Entities e) {
                      return IR::Entity(CHECK_TYPE_OF, e[0].primaryArg(), e[2].primaryArg());
                  } },
            Rule { { LOAD_CONST, LOAD_SYMBOL, TYPE, EQ }, [](const Entities e) {
                      return IR::Entity(CHECK_TYPE_OF, e[1].primaryArg(), e[0].primaryArg());
                  } },
            Rule { { LOAD_SYMBOL_BY_INDEX, TYPE, LOAD_CONST, EQ }, [](const Entities e) {
                      return IR::Entity(CHECK_TYPE_OF_BY_INDEX, e[0].primaryArg(), e[2].primaryArg());
                  } },
            Rule { { LOAD_CONST, LOAD_SYMBOL_BY_INDEX, TYPE, EQ }, [](const Entities e) {
                      return IR::Entity(CHECK_TYPE_OF_BY_INDEX, e[1].primaryArg(), e[0].primaryArg());
                  } },
            // ---
            Rule { { LOAD_SYMBOL_BY_INDEX, LEN, STORE }, [](const Entities e) {
                      return IR::Entity(STORE_LEN, e[0].primaryArg(), e[2].primaryArg());
                  } },
            Rule { { LOAD_SYMBOL, LEN, LT, POP_JUMP_IF_FALSE }, [](const Entities e) {
                      return IR::Entity::GotoWithArg(e[3], LT_LEN_SYM_JUMP_IF_FALSE, e[0].primaryArg());
                  } },
        };
    }

    void IROptimizer::process(const std::vector<IR::Block>& pages, const std::vector<std::string>& symbols, const std::vector<ValTableElem>& values)
    {
        m_logger.traceStart("process");
        m_symbols = symbols;
        m_values = values;

        for (const auto& block : pages)
        {
            m_ir.emplace_back();
            IR::Block& current_block = m_ir.back();

            std::size_t i = 0;
            const std::size_t end = block.size();

            while (i < end)
            {
                std::optional<EntityWithOffset> maybe_compacted = replaceWithRules(
                    std::span(
                        block.begin() + static_cast<IR::Block::difference_type>(i),
                        block.size() - i),
                    i);

                if (maybe_compacted.has_value())
                {
                    auto [entity, offset] = maybe_compacted.value();
                    current_block.emplace_back(entity);
                    i += offset;
                }
                else
                {
                    current_block.emplace_back(block[i]);
                    ++i;
                }
            }
        }

        m_logger.traceEnd();
    }

    const std::vector<IR::Block>& IROptimizer::intermediateRepresentation() const noexcept
    {
        return m_ir;
    }

    bool IROptimizer::match(const std::vector<Instruction>& expected_insts, const std::span<const IR::Entity> entities) const
    {
        if (expected_insts.size() > entities.size())
            return false;

        for (std::size_t i = 0; i < expected_insts.size(); ++i)
        {
            if (expected_insts[i] != entities[i].inst())
                return false;
        }

        return true;
    }

    bool IROptimizer::canBeOptimizedSafely(std::span<const IR::Entity> entities, std::size_t window_size) const
    {
        // check that we can actually safely apply the optimization on the given instructions
        return std::ranges::none_of(
            entities | std::ranges::views::take(window_size),
            [](const IR::Entity& entity) {
                return entity.primaryArg() > IR::MaxValueForDualArg;
            });
    }

    std::optional<EntityWithOffset> IROptimizer::replaceWithRules(const std::span<const IR::Entity> entities, const std::size_t position_in_block)
    {
        for (const auto& [expected, condition, createReplacement] : m_ruleset)
        {
            if (match(expected, entities) && condition(entities, position_in_block))
            {
                const std::size_t window_size = expected.size();
                if (!canBeOptimizedSafely(entities, window_size))
                    return std::nullopt;  // no need to try other optimizations, they won't be applied either

                auto output = createReplacement(entities);

                if (const auto it = std::ranges::find_if(entities, [](const auto& entity) {
                        return entity.hasValidSourceLocation();
                    });
                    it != entities.end())
                    output.setSourceLocation(it->filename(), it->sourceLine());

                return EntityWithOffset { output, window_size };
            }
        }

        return std::nullopt;
    }

    bool IROptimizer::isPositiveNumberInlinable(const uint16_t id) const
    {
        if (std::cmp_less(id, m_values.size()) && m_values[id].type == ValTableElemType::Number)
        {
            const double val = std::get<double>(m_values[id].value);
            return val >= 0.0 &&
                val < IR::MaxValueForDualArg &&
                static_cast<double>(static_cast<long>(val)) == val;
        }
        return false;
    }

    bool IROptimizer::isSmallerNumberInlinable(const uint16_t id) const
    {
        if (std::cmp_less(id, m_values.size()) && m_values[id].type == ValTableElemType::Number)
        {
            const double val = std::get<double>(m_values[id].value) + IR::MaxValueForSmallNumber;
            return val >= 0.0 &&
                val < IR::MaxValueForDualArg &&
                static_cast<double>(static_cast<long>(val)) == val;
        }
        return false;
    }

    bool IROptimizer::isNumberEqualTo(const uint16_t id, const int number) const
    {
        if (std::cmp_less(id, m_values.size()) && m_values[id].type == ValTableElemType::Number)
        {
            const double val = std::get<double>(m_values[id].value);
            return static_cast<double>(static_cast<long>(val)) == val &&
                static_cast<int>(val) == number;
        }
        return false;
    }

    uint16_t IROptimizer::numberAsArg(const uint16_t id) const
    {
        return static_cast<uint16_t>(std::get<double>(m_values[id].value));
    }

    uint16_t IROptimizer::smallerNumberAsArg(const uint16_t id) const
    {
        return static_cast<uint16_t>(std::get<double>(m_values[id].value) + IR::MaxValueForSmallNumber);
    }
}

1	#include <Ark/Compiler/IntermediateRepresentation/IROptimizer.hpp>
2
3	#include <cassert>
4	#include <utility>
5	#include <ranges>
6	#include <algorithm>
7
8	#include <Ark/Builtins/Builtins.hpp>
9
10	namespace Ark::internal
11	{
12	IROptimizer::IROptimizer(const unsigned debug) :	700✔
13	m_logger("IROptimizer", debug)	350✔
14	{	350✔
15	m_ruleset = {	21,350✔
16	Rule { { LOAD_CONST, LOAD_CONST }, LOAD_CONST_LOAD_CONST },	350✔
17	Rule { { LOAD_CONST, STORE }, LOAD_CONST_STORE },	350✔
18	Rule { { LOAD_CONST, SET_VAL }, LOAD_CONST_SET_VAL },	350✔
19	Rule { { LOAD_SYMBOL, STORE }, STORE_FROM },	350✔
20	Rule { { LOAD_SYMBOL_BY_INDEX, STORE }, STORE_FROM_INDEX },	350✔
21	Rule { { LOAD_SYMBOL, SET_VAL }, SET_VAL_FROM },	350✔
22	Rule { { LOAD_SYMBOL_BY_INDEX, SET_VAL }, SET_VAL_FROM_INDEX },	350✔
23	Rule { { STORE, PUSH_RETURN_ADDRESS, LOAD_SYMBOL_BY_INDEX, BUILTIN, CALL },	350✔
24	[](const Entities entities, const std::size_t start_idx) {	959✔
25	return Builtins::builtins[entities[3].primaryArg()].second.isFunction() && start_idx == 0;	609✔
26	},
27	[](const Entities e) {	959✔
28	return IR::Entity(CALL_BUILTIN_WITHOUT_RETURN_ADDRESS, e[3].primaryArg(), 1);	609✔
29	} },
30	Rule { { STORE, STORE, PUSH_RETURN_ADDRESS, LOAD_SYMBOL_BY_INDEX, LOAD_SYMBOL_BY_INDEX, BUILTIN, CALL },	350✔
31	[](const Entities entities, const std::size_t start_idx) {	433✔
32	return Builtins::builtins[entities[5].primaryArg()].second.isFunction() && start_idx == 0;	83✔
33	},
34	[](const Entities e) {	433✔
35	return IR::Entity(CALL_BUILTIN_WITHOUT_RETURN_ADDRESS, e[5].primaryArg(), 2);	83✔
36	} },
37	Rule { { STORE, STORE, STORE, PUSH_RETURN_ADDRESS, LOAD_SYMBOL_BY_INDEX, LOAD_SYMBOL_BY_INDEX, LOAD_SYMBOL_BY_INDEX, BUILTIN, CALL },	350✔
38	[](const Entities entities, const std::size_t start_idx) {	402✔
39	return Builtins::builtins[entities[7].primaryArg()].second.isFunction() && start_idx == 0;	52✔
40	},
41	[](const Entities e) {	402✔
42	return IR::Entity(CALL_BUILTIN_WITHOUT_RETURN_ADDRESS, e[7].primaryArg(), 3);	52✔
43	} },
44	Rule { { BUILTIN, CALL }, CALL_BUILTIN, [](const Entities entities, const std::size_t) {	831✔
45	return Builtins::builtins[entities[0].primaryArg()].second.isFunction();	481✔
46	} },
47	Rule { { LOAD_SYMBOL, CALL }, CALL_SYMBOL },	350✔
48	Rule { { GET_CURRENT_PAGE_ADDR, CALL }, CALL_CURRENT_PAGE },	350✔
49	Rule { { LOAD_SYMBOL, GET_FIELD }, GET_FIELD_FROM_SYMBOL },	350✔
50	Rule { { LOAD_SYMBOL_BY_INDEX, GET_FIELD }, GET_FIELD_FROM_SYMBOL_INDEX },	350✔
51	Rule { { LIST, STORE }, STORE_LIST },	350✔
52	Rule { { LOAD_SYMBOL, APPEND_IN_PLACE }, APPEND_IN_PLACE_SYM },	350✔
53	Rule { { LOAD_SYMBOL_BY_INDEX, APPEND_IN_PLACE }, APPEND_IN_PLACE_SYM_INDEX },	350✔
54	// LOAD_CONST, LOAD_SYMBOL a, MUL, SET_VAL / LOAD_SYMBOL a, LOAD_CONST, MUL, SET_VAL
55	// ---> MUL_SET_VAL a value
56	Rule { { LOAD_CONST, LOAD_SYMBOL, MUL, SET_VAL }, [this](const Entities e, const std::size_t) {	352✔
57	return isSmallerNumberInlinable(e[0].primaryArg()) && e[1].primaryArg() == e[3].primaryArg();	2✔
58	},
59	[this](const Entities e) {	352✔
60	return IR::Entity(MUL_SET_VAL, e[1].primaryArg(), smallerNumberAsArg(e[0].primaryArg()));	2✔
61	} },
62	Rule { { LOAD_SYMBOL, LOAD_CONST, MUL, SET_VAL }, [this](const Entities e, const std::size_t) {	351✔
63	return isSmallerNumberInlinable(e[1].primaryArg()) && e[0].primaryArg() == e[3].primaryArg();	1✔
64	},
65	[this](const Entities e) {	351✔
66	return IR::Entity(MUL_SET_VAL, e[0].primaryArg(), smallerNumberAsArg(e[1].primaryArg()));	1✔
67	} },
68	// LOAD_CONST, LOAD_SYMBOL a, MUL / LOAD_SYMBOL a, LOAD_CONST, MUL
69	// ---> MUL_(BY\|BY_INDEX) a value
70	Rule { { LOAD_CONST, LOAD_SYMBOL, MUL }, [this](const Entities e, const std::size_t) {	352✔
71	return isSmallerNumberInlinable(e[0].primaryArg());	2✔
72	},
73	[this](const Entities e) {	352✔
74	return IR::Entity(MUL_BY, e[1].primaryArg(), smallerNumberAsArg(e[0].primaryArg()));	2✔
75	} },
76	Rule { { LOAD_SYMBOL, LOAD_CONST, MUL }, [this](const Entities e, const std::size_t) {	352✔
77	return isSmallerNumberInlinable(e[1].primaryArg());	2✔
78	},
79	[this](const Entities e) {	352✔
80	return IR::Entity(MUL_BY, e[0].primaryArg(), smallerNumberAsArg(e[1].primaryArg()));	2✔
81	} },
82	Rule { { LOAD_CONST, LOAD_SYMBOL_BY_INDEX, MUL }, [this](const Entities e, const std::size_t) {	430✔
83	return isSmallerNumberInlinable(e[0].primaryArg());	80✔
84	},
85	[this](const Entities e) {	430✔
86	return IR::Entity(MUL_BY_INDEX, e[1].primaryArg(), smallerNumberAsArg(e[0].primaryArg()));	80✔
87	} },
88	Rule { { LOAD_SYMBOL_BY_INDEX, LOAD_CONST, MUL }, [this](const Entities e, const std::size_t) {	353✔
89	return isSmallerNumberInlinable(e[1].primaryArg());	3✔
90	},
91	[this](const Entities e) {	353✔
92	return IR::Entity(MUL_BY_INDEX, e[0].primaryArg(), smallerNumberAsArg(e[1].primaryArg()));	3✔
93	} },
94	// (LOAD_SYMBOL a \| LOAD_SYMBOL_BY_INDEX index), LOAD_CONST n (=1), (ADD \| SUB), STORE
95	// ---> INCREMENT_STORE / DECREMENT_STORE a value
96	Rule { { LOAD_CONST, LOAD_SYMBOL, ADD, SET_VAL }, [this](const Entities e, const std::size_t) {	1,243✔
97	return isPositiveNumberInlinable(e[0].primaryArg()) && e[1].primaryArg() == e[3].primaryArg();	893✔
98	},
99	[this](const Entities e) {	1,242✔
100	return IR::Entity(INCREMENT_STORE, e[1].primaryArg(), numberAsArg(e[0].primaryArg()));	892✔
101	} },
102	Rule { { LOAD_SYMBOL, LOAD_CONST, ADD, SET_VAL }, [this](const Entities e, const std::size_t) {	491✔
103	return isPositiveNumberInlinable(e[1].primaryArg()) && e[0].primaryArg() == e[3].primaryArg();	141✔
104	},
105	[this](const Entities e) {	478✔
106	return IR::Entity(INCREMENT_STORE, e[0].primaryArg(), numberAsArg(e[1].primaryArg()));	128✔
107	} },
108	Rule { { LOAD_SYMBOL, LOAD_CONST, SUB, SET_VAL }, [this](const Entities e, const std::size_t) {	399✔
109	return isPositiveNumberInlinable(e[1].primaryArg()) && e[0].primaryArg() == e[3].primaryArg();	49✔
110	},
111	[this](const Entities e) {	399✔
112	return IR::Entity(DECREMENT_STORE, e[0].primaryArg(), numberAsArg(e[1].primaryArg()));	49✔
113	} },
114	// without the final store, just increment/decrement
115	Rule { { LOAD_CONST, LOAD_SYMBOL, ADD }, [this](const Entities e, const std::size_t) {	352✔
116	return isPositiveNumberInlinable(e[0].primaryArg());	2✔
117	},
118	[this](const Entities e) {	352✔
119	return IR::Entity(INCREMENT, e[1].primaryArg(), numberAsArg(e[0].primaryArg()));	2✔
120	} },
121	Rule { { LOAD_SYMBOL, LOAD_CONST, ADD }, [this](const Entities e, const std::size_t) {	366✔
122	return isPositiveNumberInlinable(e[1].primaryArg());	16✔
123	},
124	[this](const Entities e) {	353✔
125	return IR::Entity(INCREMENT, e[0].primaryArg(), numberAsArg(e[1].primaryArg()));	3✔
126	} },
127	Rule { { LOAD_SYMBOL, LOAD_CONST, SUB }, [this](const Entities e, const std::size_t) {	361✔
128	return isPositiveNumberInlinable(e[1].primaryArg());	11✔
129	},
130	[this](const Entities e) {	361✔
131	return IR::Entity(DECREMENT, e[0].primaryArg(), numberAsArg(e[1].primaryArg()));	11✔
132	} },
133	Rule { { LOAD_CONST, LOAD_SYMBOL_BY_INDEX, ADD }, [this](const Entities e, const std::size_t) {	472✔
134	return isPositiveNumberInlinable(e[0].primaryArg());	122✔
135	},
136	[this](const Entities e) {	472✔
137	return IR::Entity(INCREMENT_BY_INDEX, e[1].primaryArg(), numberAsArg(e[0].primaryArg()));	122✔
138	} },
139	Rule { { LOAD_SYMBOL_BY_INDEX, LOAD_CONST, ADD }, [this](const Entities e, const std::size_t) {	381✔
140	return isPositiveNumberInlinable(e[1].primaryArg());	31✔
141	},
142	[this](const Entities e) {	369✔
143	return IR::Entity(INCREMENT_BY_INDEX, e[0].primaryArg(), numberAsArg(e[1].primaryArg()));	19✔
144	} },
145	Rule { { LOAD_SYMBOL_BY_INDEX, LOAD_CONST, SUB }, [this](const Entities e, const std::size_t) {	462✔
146	return isPositiveNumberInlinable(e[1].primaryArg());	112✔
147	},
148	[this](const Entities e) {	461✔
149	return IR::Entity(DECREMENT_BY_INDEX, e[0].primaryArg(), numberAsArg(e[1].primaryArg()));	111✔
150	} },
151	// LOAD_SYMBOL list, (TAIL \| HEAD), (STORE \| SET_VAL a)
152	// ---> STORE_TAIL list a ; STORE_HEAD ; SET_VAL_TAIL ; SET_VAL_HEAD
153	Rule { { LOAD_SYMBOL, TAIL, STORE }, [](const Entities e) {	352✔
154	return IR::Entity(STORE_TAIL, e[0].primaryArg(), e[2].primaryArg());	2✔
155	} },
156	Rule { { LOAD_SYMBOL, TAIL, SET_VAL }, [](const Entities e) {	355✔
157	return IR::Entity(SET_VAL_TAIL, e[0].primaryArg(), e[2].primaryArg());	5✔
158	} },
159	Rule { { LOAD_SYMBOL, HEAD, STORE }, [](const Entities e) {	353✔
160	return IR::Entity(STORE_HEAD, e[0].primaryArg(), e[2].primaryArg());	3✔
161	} },
162	Rule { { LOAD_SYMBOL, HEAD, SET_VAL }, [](const Entities e) {	352✔
163	return IR::Entity(SET_VAL_HEAD, e[0].primaryArg(), e[2].primaryArg());	2✔
164	} },
165	Rule { { LOAD_SYMBOL_BY_INDEX, TAIL, STORE }, [](const Entities e) {	375✔
166	return IR::Entity(STORE_TAIL_BY_INDEX, e[0].primaryArg(), e[2].primaryArg());	25✔
167	} },
168	Rule { { LOAD_SYMBOL_BY_INDEX, TAIL, SET_VAL }, [](const Entities e) {	352✔
169	return IR::Entity(SET_VAL_TAIL_BY_INDEX, e[0].primaryArg(), e[2].primaryArg());	2✔
170	} },
171	Rule { { LOAD_SYMBOL_BY_INDEX, HEAD, STORE }, [](const Entities e) {	376✔
172	return IR::Entity(STORE_HEAD_BY_INDEX, e[0].primaryArg(), e[2].primaryArg());	26✔
173	} },
174	Rule { { LOAD_SYMBOL_BY_INDEX, HEAD, SET_VAL }, [](const Entities e) {	352✔
175	return IR::Entity(SET_VAL_HEAD_BY_INDEX, e[0].primaryArg(), e[2].primaryArg());	2✔
176	} },
177	// (LOAD_CONST id \| LOAD_SYMBOL id), <comparison operator>, POP_JUMP_IF_(FALSE\|TRUE)
178	// ---> <OP>_(CONST\|SYM)_JUMP_IF_(FALSE\|TRUE)
179	Rule { { LOAD_CONST, LT, POP_JUMP_IF_FALSE }, [](const Entities e) {	360✔
180	return IR::Entity::GotoWithArg(e[2], LT_CONST_JUMP_IF_FALSE, e[0].primaryArg());	10✔
181	} },
182	Rule { { LOAD_CONST, LT, POP_JUMP_IF_TRUE }, [](const Entities e) {	430✔
183	return IR::Entity::GotoWithArg(e[2], LT_CONST_JUMP_IF_TRUE, e[0].primaryArg());	80✔
184	} },
185	Rule { { LOAD_SYMBOL, LT, POP_JUMP_IF_FALSE }, [](const Entities e) {	661✔
186	return IR::Entity::GotoWithArg(e[2], LT_SYM_JUMP_IF_FALSE, e[0].primaryArg());	311✔
187	} },
188	Rule { { LOAD_CONST, GT, POP_JUMP_IF_TRUE }, [](const Entities e) {	387✔
189	return IR::Entity::GotoWithArg(e[2], GT_CONST_JUMP_IF_TRUE, e[0].primaryArg());	37✔
190	} },
191	Rule { { LOAD_CONST, GT, POP_JUMP_IF_FALSE }, [](const Entities e) {	392✔
192	return IR::Entity::GotoWithArg(e[2], GT_CONST_JUMP_IF_FALSE, e[0].primaryArg());	42✔
193	} },
194	Rule { { LOAD_SYMBOL, GT, POP_JUMP_IF_FALSE }, [](const Entities e) {	352✔
195	return IR::Entity::GotoWithArg(e[2], GT_SYM_JUMP_IF_FALSE, e[0].primaryArg());	2✔
196	} },
197	Rule { { LOAD_CONST, EQ, POP_JUMP_IF_TRUE }, [](const Entities e) {	429✔
198	return IR::Entity::GotoWithArg(e[2], EQ_CONST_JUMP_IF_TRUE, e[0].primaryArg());	79✔
199	} },
200	Rule { { LOAD_SYMBOL_BY_INDEX, EQ, POP_JUMP_IF_TRUE }, [](const Entities e) {	554✔
201	return IR::Entity::GotoWithArg(e[2], EQ_SYM_INDEX_JUMP_IF_TRUE, e[0].primaryArg());	204✔
202	} },
203	Rule { { LOAD_CONST, NEQ, POP_JUMP_IF_TRUE }, [](const Entities e) {	353✔
204	return IR::Entity::GotoWithArg(e[2], NEQ_CONST_JUMP_IF_TRUE, e[0].primaryArg());	3✔
205	} },
206	Rule { { LOAD_SYMBOL, NEQ, POP_JUMP_IF_FALSE }, [](const Entities e) {	379✔
207	return IR::Entity::GotoWithArg(e[2], NEQ_SYM_JUMP_IF_FALSE, e[0].primaryArg());	29✔
208	} },
209	// LOAD_SYMBOL id, LOAD_SYMBOL id2, AT
210	// ---> AT_SYM_SYM id id2
211	Rule { { LOAD_SYMBOL, LOAD_SYMBOL, AT }, AT_SYM_SYM },	350✔
212	Rule { { LOAD_SYMBOL_BY_INDEX, LOAD_SYMBOL_BY_INDEX, AT }, AT_SYM_INDEX_SYM_INDEX },	350✔
213	Rule { { LOAD_SYMBOL_BY_INDEX, LOAD_CONST, AT }, AT_SYM_INDEX_CONST },	350✔
214	// LOAD_SYMBOL sym, TYPE, LOAD_CONST cst, EQ
215	// ---> CHECK_TYPE_OF sym, cst
216	// also works with LOAD_CONST cst, LOAD_SYMBOL sym, TYPE, EQ, but args will be flipped
217	Rule { { LOAD_SYMBOL, TYPE, LOAD_CONST, EQ }, [](const Entities e) {	353✔
218	return IR::Entity(CHECK_TYPE_OF, e[0].primaryArg(), e[2].primaryArg());	3✔
219	} },
220	Rule { { LOAD_CONST, LOAD_SYMBOL, TYPE, EQ }, [](const Entities e) {	351✔
221	return IR::Entity(CHECK_TYPE_OF, e[1].primaryArg(), e[0].primaryArg());	1✔
222	} },
223	Rule { { LOAD_SYMBOL_BY_INDEX, TYPE, LOAD_CONST, EQ }, [](const Entities e) {	353✔
224	return IR::Entity(CHECK_TYPE_OF_BY_INDEX, e[0].primaryArg(), e[2].primaryArg());	3✔
225	} },
226	Rule { { LOAD_CONST, LOAD_SYMBOL_BY_INDEX, TYPE, EQ }, [](const Entities e) {	404✔
227	return IR::Entity(CHECK_TYPE_OF_BY_INDEX, e[1].primaryArg(), e[0].primaryArg());	54✔
228	} },
229	// ---
230	Rule { { LOAD_SYMBOL_BY_INDEX, LEN, STORE }, [](const Entities e) {	561✔
231	return IR::Entity(STORE_LEN, e[0].primaryArg(), e[2].primaryArg());	211✔
232	} },
233	Rule { { LOAD_SYMBOL, LEN, LT, POP_JUMP_IF_FALSE }, [](const Entities e) {	877✔
234	return IR::Entity::GotoWithArg(e[3], LT_LEN_SYM_JUMP_IF_FALSE, e[0].primaryArg());	527✔
235	} },
236	};
237	}	350✔
238
239	void IROptimizer::process(const std::vector<IR::Block>& pages, const std::vector<std::string>& symbols, const std::vector<ValTableElem>& values)	218✔
240	{	218✔
241	m_logger.traceStart("process");	218✔
242	m_symbols = symbols;	218✔
243	m_values = values;	218✔
244
245	for (const auto& block : pages)	4,035✔
246	{
247	m_ir.emplace_back();	3,817✔
248	IR::Block& current_block = m_ir.back();	3,817✔
249
250	std::size_t i = 0;	3,817✔
251	const std::size_t end = block.size();	3,817✔
252
253	while (i < end)	101,587✔
254	{
255	std::optional<EntityWithOffset> maybe_compacted = replaceWithRules(	195,540✔
256	std::span(	97,770✔
257	block.begin() + static_cast<IR::Block::difference_type>(i),	97,770✔
258	block.size() - i),	97,770✔
259	i);	97,770✔
260
261	if (maybe_compacted.has_value())	97,770✔
262	{
263	auto [entity, offset] = maybe_compacted.value();	45,348✔
264	current_block.emplace_back(entity);	22,674✔
265	i += offset;	22,674✔
266	}	22,674✔
267	else
268	{
269	current_block.emplace_back(block[i]);	75,096✔
270	++i;	75,096✔
271	}
272	}	97,770✔
273	}	3,817✔
274
275	m_logger.traceEnd();	218✔
276	}	218✔
277
278	const std::vector<IR::Block>& IROptimizer::intermediateRepresentation() const noexcept	218✔
279	{	218✔
280	return m_ir;	218✔
281	}
282
283	bool IROptimizer::match(const std::vector<Instruction>& expected_insts, const std::span<const IR::Entity> entities) const	4,822,150✔
284	{	4,822,150✔
285	if (expected_insts.size() > entities.size())	4,822,150✔
286	return false;	435,856✔
287
288	for (std::size_t i = 0; i < expected_insts.size(); ++i)	9,257,630✔
289	{
290	if (expected_insts[i] != entities[i].inst())	4,871,336✔
291	return false;	4,363,577✔
292	}	507,759✔
293
294	return true;	22,717✔
295	}	4,822,150✔
296
297	bool IROptimizer::canBeOptimizedSafely(std::span<const IR::Entity> entities, std::size_t window_size) const	22,674✔
298	{	22,674✔
299	// check that we can actually safely apply the optimization on the given instructions
300	return std::ranges::none_of(	22,674✔
301	entities \| std::ranges::views::take(window_size),	22,674✔
302	[](const IR::Entity& entity) {	53,895✔
303	return entity.primaryArg() > IR::MaxValueForDualArg;	53,895✔
304	});
305	}
306
307	std::optional<EntityWithOffset> IROptimizer::replaceWithRules(const std::span<const IR::Entity> entities, const std::size_t position_in_block)	97,770✔
308	{	97,770✔
309	for (const auto& [expected, condition, createReplacement] : m_ruleset)	4,987,985✔
310	{
311	if (match(expected, entities) && condition(entities, position_in_block))	4,822,150✔
312	{
313	const std::size_t window_size = expected.size();	45,348✔
314	if (!canBeOptimizedSafely(entities, window_size))	22,674✔
315	return std::nullopt; // no need to try other optimizations, they won't be applied either	×
316
317	auto output = createReplacement(entities);	45,348✔
318
319	if (const auto it = std::ranges::find_if(entities, [](const auto& entity) {	4,259,852✔
320	return entity.hasValidSourceLocation();	4,237,178✔
321	});
322	it != entities.end())	45,348✔
323	output.setSourceLocation(it->filename(), it->sourceLine());	22,674✔
324
325	return EntityWithOffset { output, window_size };	22,674✔
326	}	22,674✔
327	}	4,822,150✔
328
329	return std::nullopt;	75,096✔
330	}	97,770✔
331
332	bool IROptimizer::isPositiveNumberInlinable(const uint16_t id) const	1,377✔
333	{	1,377✔
334	if (std::cmp_less(id, m_values.size()) && m_values[id].type == ValTableElemType::Number)	1,377✔
335	{
336	const double val = std::get<double>(m_values[id].value);	1,341✔
337	return val >= 0.0 &&	2,682✔
338	val < IR::MaxValueForDualArg &&	1,341✔
339	static_cast<double>(static_cast<long>(val)) == val;	1,340✔
340	}	1,341✔
341	return false;	36✔
342	}	1,377✔
343
344	bool IROptimizer::isSmallerNumberInlinable(const uint16_t id) const	90✔
345	{	90✔
346	if (std::cmp_less(id, m_values.size()) && m_values[id].type == ValTableElemType::Number)	90✔
347	{
348	const double val = std::get<double>(m_values[id].value) + IR::MaxValueForSmallNumber;	90✔
349	return val >= 0.0 &&	180✔
350	val < IR::MaxValueForDualArg &&	90✔
351	static_cast<double>(static_cast<long>(val)) == val;	90✔
352	}	90✔
NEW 353	return false;	×
354	}	90✔
355
NEW 356	bool IROptimizer::isNumberEqualTo(const uint16_t id, const int number) const	×
NEW 357	{	×
NEW 358	if (std::cmp_less(id, m_values.size()) && m_values[id].type == ValTableElemType::Number)	×
359	{
NEW 360	const double val = std::get<double>(m_values[id].value);	×
NEW 361	return static_cast<double>(static_cast<long>(val)) == val &&	×
NEW 362	static_cast<int>(val) == number;	×
NEW 363	}	×
NEW 364	return false;	×
NEW 365	}	×
366
367	uint16_t IROptimizer::numberAsArg(const uint16_t id) const	1,337✔
368	{	1,337✔
369	return static_cast<uint16_t>(std::get<double>(m_values[id].value));	1,337✔
370	}
371
372	uint16_t IROptimizer::smallerNumberAsArg(const uint16_t id) const	90✔
373	{	90✔
374	return static_cast<uint16_t>(std::get<double>(m_values[id].value) + IR::MaxValueForSmallNumber);	90✔
375	}
376	}

ArkScript-lang / Ark / 20369834167

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous