23209646190

Committed 17 Mar 2026 06:16PM UTC coverage: 93.659% (-0.05%) from 93.706%

Build # 23209646190

Build Type

push

github

Committed by

SuperFola

Commit Message

feat(vm): add a new super instruction CALL_SYMBOL_BY_INDEX

Coverage Stats

17 of 19 new or added lines in 3 files covered. (89.47%)

132 existing lines in 8 files now uncovered.

9601 of 10251 relevant lines covered (93.66%)

275534.05 hits per line

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

95.79

/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
{
    IR::Entity fuseMathOps3(const std::span<const IR::Entity> e)
    {
        return IR::Entity(FUSED_MATH, e[0].inst(), e[1].inst(), e[2].inst());
    }

    IR::Entity fuseMathOps2(const std::span<const IR::Entity> e)
    {
        return IR::Entity(FUSED_MATH, e[0].inst(), e[1].inst(), NOP);
    }

    IROptimizer::IROptimizer(const unsigned debug) :
        Pass("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_FAST, STORE }, STORE_FROM },
            Rule { { LOAD_FAST_BY_INDEX, STORE }, STORE_FROM_INDEX },
            Rule { { LOAD_FAST, SET_VAL }, SET_VAL_FROM },
            Rule { { LOAD_FAST_BY_INDEX, SET_VAL }, SET_VAL_FROM_INDEX },
            Rule { { STORE, PUSH_RETURN_ADDRESS, LOAD_FAST_BY_INDEX, CALL_BUILTIN },
                   [](const Entities entities, const std::size_t start_idx) {
                       return start_idx == 0 && entities[5].inst() == RET;
                   },
                   [](const Entities e) {
                       return IR::Entity(CALL_BUILTIN_WITHOUT_RETURN_ADDRESS, e[3].primaryArg(), 1);
                   } },
            Rule { { STORE, STORE, PUSH_RETURN_ADDRESS, LOAD_FAST_BY_INDEX, LOAD_FAST_BY_INDEX, CALL_BUILTIN },
                   [](const Entities entities, const std::size_t start_idx) {
                       return start_idx == 0 && entities[7].inst() == RET;
                   },
                   [](const Entities e) {
                       return IR::Entity(CALL_BUILTIN_WITHOUT_RETURN_ADDRESS, e[5].primaryArg(), 2);
                   } },
            Rule { { STORE, STORE, STORE, PUSH_RETURN_ADDRESS, LOAD_FAST_BY_INDEX, LOAD_FAST_BY_INDEX, LOAD_FAST_BY_INDEX, CALL_BUILTIN },
                   [](const Entities entities, const std::size_t start_idx) {
                       return start_idx == 0 && entities[9].inst() == RET;
                   },
                   [](const Entities e) {
                       return IR::Entity(CALL_BUILTIN_WITHOUT_RETURN_ADDRESS, e[7].primaryArg(), 3);
                   } },
            Rule { { LOAD_FAST, GET_FIELD }, GET_FIELD_FROM_SYMBOL },
            Rule { { LOAD_FAST_BY_INDEX, GET_FIELD }, GET_FIELD_FROM_SYMBOL_INDEX },
            Rule { { LIST, STORE }, STORE_LIST },
            Rule { { LOAD_FAST, APPEND_IN_PLACE }, APPEND_IN_PLACE_SYM },
            Rule { { LOAD_FAST_BY_INDEX, APPEND_IN_PLACE }, APPEND_IN_PLACE_SYM_INDEX },
            // LOAD_CONST, LOAD_FAST a, MUL, SET_VAL / LOAD_FAST a, LOAD_CONST, MUL, SET_VAL
            // ---> MUL_SET_VAL a value
            Rule { { LOAD_CONST, LOAD_FAST, 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_FAST, 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_FAST a, MUL / LOAD_FAST a, LOAD_CONST, MUL
            // ---> MUL_(BY|BY_INDEX) a value
            Rule { { LOAD_CONST, LOAD_FAST, 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_FAST, 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_FAST_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_FAST_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_FAST a | LOAD_FAST_BY_INDEX index), LOAD_CONST n (=1), (ADD | SUB), STORE
            // ---> INCREMENT_STORE / DECREMENT_STORE a value
            Rule { { LOAD_CONST, LOAD_FAST, 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_FAST, 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_FAST, 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_FAST, 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_FAST, 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_FAST, 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_FAST_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_FAST_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_FAST_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_FAST list, (TAIL | HEAD), (STORE | SET_VAL a)
            // ---> STORE_TAIL list a ; STORE_HEAD ; SET_VAL_TAIL ; SET_VAL_HEAD
            Rule { { LOAD_FAST, TAIL, STORE }, [](const Entities e) {
                      return IR::Entity(STORE_TAIL, e[0].primaryArg(), e[2].primaryArg());
                  } },
            Rule { { LOAD_FAST, TAIL, SET_VAL }, [](const Entities e) {
                      return IR::Entity(SET_VAL_TAIL, e[0].primaryArg(), e[2].primaryArg());
                  } },
            Rule { { LOAD_FAST, HEAD, STORE }, [](const Entities e) {
                      return IR::Entity(STORE_HEAD, e[0].primaryArg(), e[2].primaryArg());
                  } },
            Rule { { LOAD_FAST, HEAD, SET_VAL }, [](const Entities e) {
                      return IR::Entity(SET_VAL_HEAD, e[0].primaryArg(), e[2].primaryArg());
                  } },
            Rule { { LOAD_FAST_BY_INDEX, TAIL, STORE }, [](const Entities e) {
                      return IR::Entity(STORE_TAIL_BY_INDEX, e[0].primaryArg(), e[2].primaryArg());
                  } },
            Rule { { LOAD_FAST_BY_INDEX, TAIL, SET_VAL }, [](const Entities e) {
                      return IR::Entity(SET_VAL_TAIL_BY_INDEX, e[0].primaryArg(), e[2].primaryArg());
                  } },
            Rule { { LOAD_FAST_BY_INDEX, HEAD, STORE }, [](const Entities e) {
                      return IR::Entity(STORE_HEAD_BY_INDEX, e[0].primaryArg(), e[2].primaryArg());
                  } },
            Rule { { LOAD_FAST_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_FAST 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_FAST, 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_FAST, 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_FAST_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_FAST, NEQ, POP_JUMP_IF_FALSE }, [](const Entities e) {
                      return IR::Entity::GotoWithArg(e[2], NEQ_SYM_JUMP_IF_FALSE, e[0].primaryArg());
                  } },
            // LOAD_FAST id, LOAD_FAST id2, AT
            // ---> AT_SYM_SYM id id2
            Rule { { LOAD_FAST, LOAD_FAST, AT }, AT_SYM_SYM },
            Rule { { LOAD_FAST_BY_INDEX, LOAD_FAST_BY_INDEX, AT }, AT_SYM_INDEX_SYM_INDEX },
            Rule { { LOAD_FAST_BY_INDEX, LOAD_CONST, AT }, AT_SYM_INDEX_CONST },
            // LOAD_FAST sym, TYPE, LOAD_CONST cst, EQ
            // ---> CHECK_TYPE_OF sym, cst
            // also works with LOAD_CONST cst, LOAD_FAST sym, TYPE, EQ, but args will be flipped
            Rule { { LOAD_FAST, TYPE, LOAD_CONST, EQ }, [](const Entities e) {
                      return IR::Entity(CHECK_TYPE_OF, e[0].primaryArg(), e[2].primaryArg());
                  } },
            Rule { { LOAD_CONST, LOAD_FAST, TYPE, EQ }, [](const Entities e) {
                      return IR::Entity(CHECK_TYPE_OF, e[1].primaryArg(), e[0].primaryArg());
                  } },
            Rule { { LOAD_FAST_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_FAST_BY_INDEX, TYPE, EQ }, [](const Entities e) {
                      return IR::Entity(CHECK_TYPE_OF_BY_INDEX, e[1].primaryArg(), e[0].primaryArg());
                  } },
            // ---
            Rule { { LOAD_FAST_BY_INDEX, LEN, STORE }, [](const Entities e) {
                      return IR::Entity(STORE_LEN, e[0].primaryArg(), e[2].primaryArg());
                  } },
            Rule { { LOAD_FAST, LEN, LT, POP_JUMP_IF_FALSE }, [](const Entities e) {
                      return IR::Entity::GotoWithArg(e[3], LT_LEN_SYM_JUMP_IF_FALSE, e[0].primaryArg());
                  } },
        };

        const auto math_ops = { ADD, SUB, MUL, DIV };
        for (const auto& one : math_ops)
        {
            for (const auto& two : math_ops)
            {
                for (const auto& three : math_ops)
                    m_ruleset.emplace_back(Rule { { one, two, three }, fuseMathOps3 });
            }
        }

        for (const auto& one : math_ops)
        {
            for (const auto& two : math_ops)
                m_ruleset.emplace_back(Rule { { one, two }, fuseMathOps2 });
        }

        m_logger.debug("Loaded {} rules", m_ruleset.size());
    }

    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;

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

        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	IR::Entity fuseMathOps3(const std::span<const IR::Entity> e)	92✔
13	{	92✔
14	return IR::Entity(FUSED_MATH, e[0].inst(), e[1].inst(), e[2].inst());	92✔
15	}
16
17	IR::Entity fuseMathOps2(const std::span<const IR::Entity> e)	274✔
18	{	274✔
19	return IR::Entity(FUSED_MATH, e[0].inst(), e[1].inst(), NOP);	274✔
20	}
21
22	IROptimizer::IROptimizer(const unsigned debug) :	914✔
23	Pass("IROptimizer", debug)	457✔
24	{	914✔
25	m_ruleset = {	26,506✔
26	Rule { { LOAD_CONST, LOAD_CONST }, LOAD_CONST_LOAD_CONST },	457✔
27	Rule { { LOAD_CONST, STORE }, LOAD_CONST_STORE },	457✔
28	Rule { { LOAD_CONST, SET_VAL }, LOAD_CONST_SET_VAL },	457✔
29	Rule { { LOAD_FAST, STORE }, STORE_FROM },	457✔
30	Rule { { LOAD_FAST_BY_INDEX, STORE }, STORE_FROM_INDEX },	457✔
31	Rule { { LOAD_FAST, SET_VAL }, SET_VAL_FROM },	457✔
32	Rule { { LOAD_FAST_BY_INDEX, SET_VAL }, SET_VAL_FROM_INDEX },	457✔
33	Rule { { STORE, PUSH_RETURN_ADDRESS, LOAD_FAST_BY_INDEX, CALL_BUILTIN },	457✔
34	[](const Entities entities, const std::size_t start_idx) {	1,075✔
35	return start_idx == 0 && entities[5].inst() == RET;	618✔
36	},
37	[](const Entities e) {	1,074✔
38	return IR::Entity(CALL_BUILTIN_WITHOUT_RETURN_ADDRESS, e[3].primaryArg(), 1);	617✔
39	} },
40	Rule { { STORE, STORE, PUSH_RETURN_ADDRESS, LOAD_FAST_BY_INDEX, LOAD_FAST_BY_INDEX, CALL_BUILTIN },	457✔
41	[](const Entities entities, const std::size_t start_idx) {	542✔
42	return start_idx == 0 && entities[7].inst() == RET;	85✔
43	},
44	[](const Entities e) {	542✔
45	return IR::Entity(CALL_BUILTIN_WITHOUT_RETURN_ADDRESS, e[5].primaryArg(), 2);	85✔
46	} },
47	Rule { { STORE, STORE, STORE, PUSH_RETURN_ADDRESS, LOAD_FAST_BY_INDEX, LOAD_FAST_BY_INDEX, LOAD_FAST_BY_INDEX, CALL_BUILTIN },	457✔
48	[](const Entities entities, const std::size_t start_idx) {	509✔
49	return start_idx == 0 && entities[9].inst() == RET;	52✔
50	},
51	[](const Entities e) {	509✔
52	return IR::Entity(CALL_BUILTIN_WITHOUT_RETURN_ADDRESS, e[7].primaryArg(), 3);	52✔
53	} },
54	Rule { { LOAD_FAST, GET_FIELD }, GET_FIELD_FROM_SYMBOL },	457✔
55	Rule { { LOAD_FAST_BY_INDEX, GET_FIELD }, GET_FIELD_FROM_SYMBOL_INDEX },	457✔
56	Rule { { LIST, STORE }, STORE_LIST },	457✔
57	Rule { { LOAD_FAST, APPEND_IN_PLACE }, APPEND_IN_PLACE_SYM },	457✔
58	Rule { { LOAD_FAST_BY_INDEX, APPEND_IN_PLACE }, APPEND_IN_PLACE_SYM_INDEX },	457✔
59	// LOAD_CONST, LOAD_FAST a, MUL, SET_VAL / LOAD_FAST a, LOAD_CONST, MUL, SET_VAL
60	// ---> MUL_SET_VAL a value
61	Rule { { LOAD_CONST, LOAD_FAST, MUL, SET_VAL }, [this](const Entities e, const std::size_t) {	459✔
62	return isSmallerNumberInlinable(e[0].primaryArg()) && e[1].primaryArg() == e[3].primaryArg();	2✔
63	},
64	[this](const Entities e) {	459✔
65	return IR::Entity(MUL_SET_VAL, e[1].primaryArg(), smallerNumberAsArg(e[0].primaryArg()));	2✔
66	} },
67	Rule { { LOAD_FAST, LOAD_CONST, MUL, SET_VAL }, [this](const Entities e, const std::size_t) {	459✔
68	return isSmallerNumberInlinable(e[1].primaryArg()) && e[0].primaryArg() == e[3].primaryArg();	2✔
69	},
70	[this](const Entities e) {	459✔
71	return IR::Entity(MUL_SET_VAL, e[0].primaryArg(), smallerNumberAsArg(e[1].primaryArg()));	2✔
72	} },
73	// LOAD_CONST, LOAD_FAST a, MUL / LOAD_FAST a, LOAD_CONST, MUL
74	// ---> MUL_(BY\|BY_INDEX) a value
75	Rule { { LOAD_CONST, LOAD_FAST, MUL }, [this](const Entities e, const std::size_t) {	482✔
76	return isSmallerNumberInlinable(e[0].primaryArg());	25✔
77	},
78	[this](const Entities e) {	482✔
79	return IR::Entity(MUL_BY, e[1].primaryArg(), smallerNumberAsArg(e[0].primaryArg()));	25✔
80	} },
81	Rule { { LOAD_FAST, LOAD_CONST, MUL }, [this](const Entities e, const std::size_t) {	459✔
82	return isSmallerNumberInlinable(e[1].primaryArg());	2✔
83	},
84	[this](const Entities e) {	459✔
85	return IR::Entity(MUL_BY, e[0].primaryArg(), smallerNumberAsArg(e[1].primaryArg()));	2✔
86	} },
87	Rule { { LOAD_CONST, LOAD_FAST_BY_INDEX, MUL }, [this](const Entities e, const std::size_t) {	537✔
88	return isSmallerNumberInlinable(e[0].primaryArg());	80✔
89	},
90	[this](const Entities e) {	537✔
91	return IR::Entity(MUL_BY_INDEX, e[1].primaryArg(), smallerNumberAsArg(e[0].primaryArg()));	80✔
92	} },
93	Rule { { LOAD_FAST_BY_INDEX, LOAD_CONST, MUL }, [this](const Entities e, const std::size_t) {	460✔
94	return isSmallerNumberInlinable(e[1].primaryArg());	3✔
95	},
96	[this](const Entities e) {	460✔
97	return IR::Entity(MUL_BY_INDEX, e[0].primaryArg(), smallerNumberAsArg(e[1].primaryArg()));	3✔
98	} },
99	// (LOAD_FAST a \| LOAD_FAST_BY_INDEX index), LOAD_CONST n (=1), (ADD \| SUB), STORE
100	// ---> INCREMENT_STORE / DECREMENT_STORE a value
101	Rule { { LOAD_CONST, LOAD_FAST, ADD, SET_VAL }, [this](const Entities e, const std::size_t) {	1,479✔
102	return isPositiveNumberInlinable(e[0].primaryArg()) && e[1].primaryArg() == e[3].primaryArg();	1,022✔
103	},
104	[this](const Entities e) {	1,478✔
105	return IR::Entity(INCREMENT_STORE, e[1].primaryArg(), numberAsArg(e[0].primaryArg()));	1,021✔
106	} },
107	Rule { { LOAD_FAST, LOAD_CONST, ADD, SET_VAL }, [this](const Entities e, const std::size_t) {	598✔
108	return isPositiveNumberInlinable(e[1].primaryArg()) && e[0].primaryArg() == e[3].primaryArg();	141✔
109	},
110	[this](const Entities e) {	585✔
111	return IR::Entity(INCREMENT_STORE, e[0].primaryArg(), numberAsArg(e[1].primaryArg()));	128✔
112	} },
113	Rule { { LOAD_FAST, LOAD_CONST, SUB, SET_VAL }, [this](const Entities e, const std::size_t) {	506✔
114	return isPositiveNumberInlinable(e[1].primaryArg()) && e[0].primaryArg() == e[3].primaryArg();	49✔
115	},
116	[this](const Entities e) {	506✔
117	return IR::Entity(DECREMENT_STORE, e[0].primaryArg(), numberAsArg(e[1].primaryArg()));	49✔
118	} },
119	// without the final store, just increment/decrement
120	Rule { { LOAD_CONST, LOAD_FAST, ADD }, [this](const Entities e, const std::size_t) {	463✔
121	return isPositiveNumberInlinable(e[0].primaryArg());	6✔
122	},
123	[this](const Entities e) {	463✔
124	return IR::Entity(INCREMENT, e[1].primaryArg(), numberAsArg(e[0].primaryArg()));	6✔
125	} },
126	Rule { { LOAD_FAST, LOAD_CONST, ADD }, [this](const Entities e, const std::size_t) {	473✔
127	return isPositiveNumberInlinable(e[1].primaryArg());	16✔
128	},
129	[this](const Entities e) {	460✔
130	return IR::Entity(INCREMENT, e[0].primaryArg(), numberAsArg(e[1].primaryArg()));	3✔
131	} },
132	Rule { { LOAD_FAST, LOAD_CONST, SUB }, [this](const Entities e, const std::size_t) {	592✔
133	return isPositiveNumberInlinable(e[1].primaryArg());	135✔
134	},
135	[this](const Entities e) {	592✔
136	return IR::Entity(DECREMENT, e[0].primaryArg(), numberAsArg(e[1].primaryArg()));	135✔
137	} },
138	Rule { { LOAD_CONST, LOAD_FAST_BY_INDEX, ADD }, [this](const Entities e, const std::size_t) {	593✔
139	return isPositiveNumberInlinable(e[0].primaryArg());	136✔
140	},
141	[this](const Entities e) {	589✔
142	return IR::Entity(INCREMENT_BY_INDEX, e[1].primaryArg(), numberAsArg(e[0].primaryArg()));	132✔
143	} },
144	Rule { { LOAD_FAST_BY_INDEX, LOAD_CONST, ADD }, [this](const Entities e, const std::size_t) {	490✔
145	return isPositiveNumberInlinable(e[1].primaryArg());	33✔
146	},
147	[this](const Entities e) {	476✔
148	return IR::Entity(INCREMENT_BY_INDEX, e[0].primaryArg(), numberAsArg(e[1].primaryArg()));	19✔
149	} },
150	Rule { { LOAD_FAST_BY_INDEX, LOAD_CONST, SUB }, [this](const Entities e, const std::size_t) {	641✔
151	return isPositiveNumberInlinable(e[1].primaryArg());	184✔
152	},
153	[this](const Entities e) {	640✔
154	return IR::Entity(DECREMENT_BY_INDEX, e[0].primaryArg(), numberAsArg(e[1].primaryArg()));	183✔
155	} },
156	// LOAD_FAST list, (TAIL \| HEAD), (STORE \| SET_VAL a)
157	// ---> STORE_TAIL list a ; STORE_HEAD ; SET_VAL_TAIL ; SET_VAL_HEAD
158	Rule { { LOAD_FAST, TAIL, STORE }, [](const Entities e) {	459✔
159	return IR::Entity(STORE_TAIL, e[0].primaryArg(), e[2].primaryArg());	2✔
160	} },
161	Rule { { LOAD_FAST, TAIL, SET_VAL }, [](const Entities e) {	462✔
162	return IR::Entity(SET_VAL_TAIL, e[0].primaryArg(), e[2].primaryArg());	5✔
163	} },
164	Rule { { LOAD_FAST, HEAD, STORE }, [](const Entities e) {	460✔
165	return IR::Entity(STORE_HEAD, e[0].primaryArg(), e[2].primaryArg());	3✔
166	} },
167	Rule { { LOAD_FAST, HEAD, SET_VAL }, [](const Entities e) {	459✔
168	return IR::Entity(SET_VAL_HEAD, e[0].primaryArg(), e[2].primaryArg());	2✔
169	} },
170	Rule { { LOAD_FAST_BY_INDEX, TAIL, STORE }, [](const Entities e) {	482✔
171	return IR::Entity(STORE_TAIL_BY_INDEX, e[0].primaryArg(), e[2].primaryArg());	25✔
172	} },
173	Rule { { LOAD_FAST_BY_INDEX, TAIL, SET_VAL }, [](const Entities e) {	459✔
174	return IR::Entity(SET_VAL_TAIL_BY_INDEX, e[0].primaryArg(), e[2].primaryArg());	2✔
175	} },
176	Rule { { LOAD_FAST_BY_INDEX, HEAD, STORE }, [](const Entities e) {	483✔
177	return IR::Entity(STORE_HEAD_BY_INDEX, e[0].primaryArg(), e[2].primaryArg());	26✔
178	} },
179	Rule { { LOAD_FAST_BY_INDEX, HEAD, SET_VAL }, [](const Entities e) {	459✔
180	return IR::Entity(SET_VAL_HEAD_BY_INDEX, e[0].primaryArg(), e[2].primaryArg());	2✔
181	} },
182	// (LOAD_CONST id \| LOAD_FAST id), <comparison operator>, POP_JUMP_IF_(FALSE\|TRUE)
183	// ---> <OP>_(CONST\|SYM)_JUMP_IF_(FALSE\|TRUE)
184	Rule { { LOAD_CONST, LT, POP_JUMP_IF_FALSE }, [](const Entities e) {	469✔
185	return IR::Entity::GotoWithArg(e[2], LT_CONST_JUMP_IF_FALSE, e[0].primaryArg());	12✔
186	} },
187	Rule { { LOAD_CONST, LT, POP_JUMP_IF_TRUE }, [](const Entities e) {	537✔
188	return IR::Entity::GotoWithArg(e[2], LT_CONST_JUMP_IF_TRUE, e[0].primaryArg());	80✔
189	} },
190	Rule { { LOAD_FAST, LT, POP_JUMP_IF_FALSE }, [](const Entities e) {	866✔
191	return IR::Entity::GotoWithArg(e[2], LT_SYM_JUMP_IF_FALSE, e[0].primaryArg());	409✔
192	} },
193	Rule { { LOAD_CONST, GT, POP_JUMP_IF_TRUE }, [](const Entities e) {	517✔
194	return IR::Entity::GotoWithArg(e[2], GT_CONST_JUMP_IF_TRUE, e[0].primaryArg());	60✔
195	} },
196	Rule { { LOAD_CONST, GT, POP_JUMP_IF_FALSE }, [](const Entities e) {	499✔
197	return IR::Entity::GotoWithArg(e[2], GT_CONST_JUMP_IF_FALSE, e[0].primaryArg());	42✔
198	} },
199	Rule { { LOAD_FAST, GT, POP_JUMP_IF_FALSE }, [](const Entities e) {	459✔
200	return IR::Entity::GotoWithArg(e[2], GT_SYM_JUMP_IF_FALSE, e[0].primaryArg());	2✔
201	} },
202	Rule { { LOAD_CONST, EQ, POP_JUMP_IF_TRUE }, [](const Entities e) {	536✔
203	return IR::Entity::GotoWithArg(e[2], EQ_CONST_JUMP_IF_TRUE, e[0].primaryArg());	79✔
204	} },
205	Rule { { LOAD_FAST_BY_INDEX, EQ, POP_JUMP_IF_TRUE }, [](const Entities e) {	662✔
206	return IR::Entity::GotoWithArg(e[2], EQ_SYM_INDEX_JUMP_IF_TRUE, e[0].primaryArg());	205✔
207	} },
208	Rule { { LOAD_CONST, NEQ, POP_JUMP_IF_TRUE }, [](const Entities e) {	460✔
209	return IR::Entity::GotoWithArg(e[2], NEQ_CONST_JUMP_IF_TRUE, e[0].primaryArg());	3✔
210	} },
211	Rule { { LOAD_FAST, NEQ, POP_JUMP_IF_FALSE }, [](const Entities e) {	486✔
212	return IR::Entity::GotoWithArg(e[2], NEQ_SYM_JUMP_IF_FALSE, e[0].primaryArg());	29✔
213	} },
214	// LOAD_FAST id, LOAD_FAST id2, AT
215	// ---> AT_SYM_SYM id id2
216	Rule { { LOAD_FAST, LOAD_FAST, AT }, AT_SYM_SYM },	457✔
217	Rule { { LOAD_FAST_BY_INDEX, LOAD_FAST_BY_INDEX, AT }, AT_SYM_INDEX_SYM_INDEX },	457✔
218	Rule { { LOAD_FAST_BY_INDEX, LOAD_CONST, AT }, AT_SYM_INDEX_CONST },	457✔
219	// LOAD_FAST sym, TYPE, LOAD_CONST cst, EQ
220	// ---> CHECK_TYPE_OF sym, cst
221	// also works with LOAD_CONST cst, LOAD_FAST sym, TYPE, EQ, but args will be flipped
222	Rule { { LOAD_FAST, TYPE, LOAD_CONST, EQ }, [](const Entities e) {	460✔
223	return IR::Entity(CHECK_TYPE_OF, e[0].primaryArg(), e[2].primaryArg());	3✔
224	} },
225	Rule { { LOAD_CONST, LOAD_FAST, TYPE, EQ }, [](const Entities e) {	458✔
226	return IR::Entity(CHECK_TYPE_OF, e[1].primaryArg(), e[0].primaryArg());	1✔
227	} },
228	Rule { { LOAD_FAST_BY_INDEX, TYPE, LOAD_CONST, EQ }, [](const Entities e) {	460✔
229	return IR::Entity(CHECK_TYPE_OF_BY_INDEX, e[0].primaryArg(), e[2].primaryArg());	3✔
230	} },
231	Rule { { LOAD_CONST, LOAD_FAST_BY_INDEX, TYPE, EQ }, [](const Entities e) {	517✔
232	return IR::Entity(CHECK_TYPE_OF_BY_INDEX, e[1].primaryArg(), e[0].primaryArg());	60✔
233	} },
234	// ---
235	Rule { { LOAD_FAST_BY_INDEX, LEN, STORE }, [](const Entities e) {	714✔
236	return IR::Entity(STORE_LEN, e[0].primaryArg(), e[2].primaryArg());	257✔
237	} },
238	Rule { { LOAD_FAST, LEN, LT, POP_JUMP_IF_FALSE }, [](const Entities e) {	1,013✔
239	return IR::Entity::GotoWithArg(e[3], LT_LEN_SYM_JUMP_IF_FALSE, e[0].primaryArg());	556✔
240	} },
241	};
242
243	const auto math_ops = { ADD, SUB, MUL, DIV };	457✔
244	for (const auto& one : math_ops)	2,285✔
245	{
246	for (const auto& two : math_ops)	9,140✔
247	{
248	for (const auto& three : math_ops)	36,560✔
249	m_ruleset.emplace_back(Rule { { one, two, three }, fuseMathOps3 });	29,248✔
250	}	7,312✔
251	}	1,828✔
252
253	for (const auto& one : math_ops)	2,285✔
254	{
255	for (const auto& two : math_ops)	9,140✔
256	m_ruleset.emplace_back(Rule { { one, two }, fuseMathOps2 });	7,312✔
257	}	1,828✔
258
259	m_logger.debug("Loaded {} rules", m_ruleset.size());	457✔
260	}	457✔
261
262	void IROptimizer::process(const std::vector<IR::Block>& pages, const std::vector<std::string>& symbols, const std::vector<ValTableElem>& values)	311✔
263	{	311✔
264	m_logger.traceStart("process");	311✔
265	m_symbols = symbols;	311✔
266	m_values = values;	311✔
267
268	for (const auto& block : pages)	4,437✔
269	{
270	m_ir.emplace_back();	4,126✔
271	IR::Block& current_block = m_ir.back();	4,126✔
272
273	std::size_t i = 0;	4,126✔
274	const std::size_t end = block.size();	4,126✔
275
276	while (i < end)	122,423✔
277	{
278	std::optional<EntityWithOffset> maybe_compacted = replaceWithRules(	236,594✔
279	std::span(	118,297✔
280	block.begin() + static_cast<IR::Block::difference_type>(i),	118,297✔
281	block.size() - i),	118,297✔
282	i);	118,297✔
283
284	if (maybe_compacted.has_value())	118,297✔
285	{
286	auto [entity, offset] = maybe_compacted.value();	38,504✔
287	current_block.emplace_back(entity);	19,252✔
288	i += offset;	19,252✔
289	}	19,252✔
290	else
291	{
292	current_block.emplace_back(block[i]);	99,045✔
293	++i;	99,045✔
294	}
295	}	118,297✔
296	}	4,126✔
297
298	m_logger.traceEnd();	311✔
299	}	311✔
300
301	const std::vector<IR::Block>& IROptimizer::intermediateRepresentation() const noexcept	311✔
302	{	311✔
303	return m_ir;	311✔
304	}
305
306	bool IROptimizer::match(const std::vector<Instruction>& expected_insts, const std::span<const IR::Entity> entities) const	13,873,039✔
307	{	13,873,039✔
308	if (expected_insts.size() > entities.size())	13,873,039✔
309	return false;	1,040,348✔
310
311	std::size_t i = 0;	12,832,691✔
312	while (i < expected_insts.size())	13,461,082✔
313	{
314	if (expected_insts[i] != entities[i].inst())	13,441,783✔
315	return false;	12,813,392✔
316	if (entities[i].kind() != IR::Kind::Label)	628,391✔
317	++i;	628,391✔
318	}
319
320	return true;	19,299✔
321	}	13,873,039✔
322
323	bool IROptimizer::canBeOptimizedSafely(std::span<const IR::Entity> entities, std::size_t window_size) const	19,252✔
324	{	19,252✔
325	// check that we can actually safely apply the optimization on the given instructions
326	return std::ranges::none_of(	19,252✔
327	entities \| std::ranges::views::take(window_size),	19,252✔
328	[](const IR::Entity& entity) {	47,376✔
329	return entity.primaryArg() > IR::MaxValueForDualArg;	47,376✔
330	});
331	}
332
333	std::optional<EntityWithOffset> IROptimizer::replaceWithRules(const std::span<const IR::Entity> entities, const std::size_t position_in_block)	118,297✔
334	{	118,297✔
335	for (const auto& [expected, condition, createReplacement] : m_ruleset)	14,049,139✔
336	{
337	if (match(expected, entities) && condition(entities, position_in_block))	13,873,039✔
338	{
339	const std::size_t window_size = expected.size();	38,504✔
340	if (!canBeOptimizedSafely(entities, window_size))	19,252✔
UNCOV 341	return std::nullopt; // no need to try other optimizations, they won't be applied either	×
342
343	auto output = createReplacement(entities);	38,504✔
344
345	if (const auto it = std::ranges::find_if(entities, [](const auto& entity) {	4,256,531✔
346	return entity.hasValidSourceLocation();	4,237,279✔
347	});
348	it != entities.end())	38,504✔
349	output.setSourceLocation(it->filename(), it->sourceLine());	19,252✔
350
351	return EntityWithOffset { output, window_size };	19,252✔
352	}	19,252✔
353	}	13,873,039✔
354
355	return std::nullopt;	99,045✔
356	}	118,297✔
357
358	bool IROptimizer::isPositiveNumberInlinable(const uint16_t id) const	1,722✔
359	{	1,722✔
360	if (std::cmp_less(id, m_values.size()) && m_values[id].type == ValTableElemType::Number)	1,722✔
361	{
362	const double val = std::get<double>(m_values[id].value);	1,680✔
363	return val >= 0.0 &&	3,360✔
364	val < IR::MaxValueForDualArg &&	1,680✔
365	static_cast<double>(static_cast<long>(val)) == val;	1,679✔
366	}	1,680✔
367	return false;	42✔
368	}	1,722✔
369
370	bool IROptimizer::isSmallerNumberInlinable(const uint16_t id) const	114✔
371	{	114✔
372	if (std::cmp_less(id, m_values.size()) && m_values[id].type == ValTableElemType::Number)	114✔
373	{
374	const double val = std::get<double>(m_values[id].value) + IR::MaxValueForSmallNumber;	114✔
375	return val >= 0.0 &&	228✔
376	val < IR::MaxValueForDualArg &&	114✔
377	static_cast<double>(static_cast<long>(val)) == val;	114✔
378	}	114✔
UNCOV 379	return false;	×
380	}	114✔
381
UNCOV 382	bool IROptimizer::isNumberEqualTo(const uint16_t id, const int number) const	×
UNCOV 383	{	×
384	if (std::cmp_less(id, m_values.size()) && m_values[id].type == ValTableElemType::Number)	×
385	{
UNCOV 386	const double val = std::get<double>(m_values[id].value);	×
387	return static_cast<double>(static_cast<long>(val)) == val &&	×
388	static_cast<int>(val) == number;	×
389	}	×
UNCOV 390	return false;	×
391	}	×
392
393	uint16_t IROptimizer::numberAsArg(const uint16_t id) const	1,676✔
394	{	1,676✔
395	return static_cast<uint16_t>(std::get<double>(m_values[id].value));	1,676✔
396	}
397
398	uint16_t IROptimizer::smallerNumberAsArg(const uint16_t id) const	114✔
399	{	114✔
400	return static_cast<uint16_t>(std::get<double>(m_values[id].value) + IR::MaxValueForSmallNumber);	114✔
401	}
402	}

ArkScript-lang / Ark / 23209646190

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