diff options
Diffstat (limited to 'boot/evaluator.cc')
| -rw-r--r-- | boot/evaluator.cc | 563 |
1 files changed, 563 insertions, 0 deletions
diff --git a/boot/evaluator.cc b/boot/evaluator.cc new file mode 100644 index 0000000..f782dd6 --- /dev/null +++ b/boot/evaluator.cc @@ -0,0 +1,563 @@ +/* Constant expression evaluation. + Copyright (C) 2025 Free Software Foundation, Inc. + +GCC is free software; you can redistribute it and/or modify +it under the terms of the GNU General Public License as published by +the Free Software Foundation; either version 3, or (at your option) +any later version. + +GCC is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +GNU General Public License for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +<http://www.gnu.org/licenses/>. */ + +#include "elna/boot/evaluator.h" +#include "elna/boot/ast.h" + +#include <numeric> +#include <algorithm> +#include <limits> + +namespace elna::boot +{ + evaluator::evaluator(symbol_bag& bag, const target_info& target, + const std::map<std::string, expression*>& evaluated_initializers) + : bag(bag), target(target), evaluated_initializers(evaluated_initializers) + { + } + + std::optional<constant_value> evaluator::evaluate(expression& subject) + { + if (auto *literal_expression = subject.is_literal()) + { + return evaluate_literal(*literal_expression); + } + else if (auto *designator = subject.is_designator()) + { + if (auto *named = designator->is_named()) + { + return evaluate_named(*named); + } + } + else if (auto *unary = subject.is_unary()) + { + return evaluate_unary(*unary); + } + else if (auto *binary = subject.is_binary()) + { + return evaluate_binary(*binary); + } + else if (auto *cast = subject.is_cast()) + { + return evaluate_cast(*cast); + } + else if (auto *traits = subject.is_traits()) + { + return evaluate_traits(*traits); + } + else if (auto *record_constructor = subject.is_record_constructor()) + { + for (const field_initializer& field_initializer : record_constructor->field_initializers) + { + if (!evaluate(field_initializer.value())) + { + return std::nullopt; + } + } + return constant_value{ compound_constant{} }; + } + else if (auto *array_constructor = subject.is_array_constructor()) + { + for (expression *element : array_constructor->elements) + { + if (!evaluate(*element)) + { + return std::nullopt; + } + } + return constant_value{ compound_constant{} }; + } + return std::nullopt; + } + + std::optional<constant_value> evaluator::evaluate_literal(literal_expression& subject) + { + type decoration = subject.type_decoration; + + if (is_primitive_type(decoration, "Int")) + { + return constant_value{ static_cast<literal<std::int32_t>&>(subject).value }; + } + if (is_primitive_type(decoration, "Word")) + { + return constant_value{ static_cast<literal<std::uint32_t>&>(subject).value }; + } + if (is_primitive_type(decoration, "Float")) + { + return constant_value{ static_cast<literal<double>&>(subject).value }; + } + if (is_primitive_type(decoration, "Bool")) + { + return constant_value{ static_cast<literal<bool>&>(subject).value }; + } + if (is_primitive_type(decoration, "Char")) + { + return constant_value{ static_cast<literal<unsigned char>&>(subject).value }; + } + if (is_primitive_type(decoration, "Pointer")) + { + return constant_value{ std::nullptr_t{} }; + } + return std::nullopt; + } + + std::optional<constant_value> evaluator::evaluate_named(named_expression& subject) + { + auto symbol = this->bag.lookup(subject.name); + + if (symbol == nullptr) + { + return std::nullopt; + } + auto variable = symbol->is_variable(); + + if (variable == nullptr + || resolve_aliases(variable->symbol).get<constant_type>() == nullptr) + { + return std::nullopt; + } + auto initializer = this->evaluated_initializers.find(subject.name); + + return initializer == this->evaluated_initializers.end() + ? std::nullopt + : evaluate(*initializer->second); + } + + std::optional<constant_value> evaluator::evaluate_unary(unary_expression& subject) + { + if (subject.operation() == unary_operator::reference) + { + // The address of a module-level entity is a compile-time + // constant. The caller (type analysis) validates the context. + return constant_value{ std::nullptr_t{} }; + } + auto operand = evaluate(subject.operand()); + + if (!operand) + { + return std::nullopt; + } + if (subject.operation() == unary_operator::minus) + { + return std::visit([](auto&& value) -> std::optional<constant_value> { + using T = std::decay_t<decltype(value)>; + + if constexpr (std::is_same_v<T, std::int32_t>) + { + return value == std::numeric_limits<std::int32_t>::min() + ? std::nullopt + : std::make_optional<constant_value>(constant_value{ -value }); + } + if constexpr (std::is_same_v<T, double>) + { + return constant_value{ -value }; + } + return std::nullopt; + }, operand.value()); + } + if (subject.operation() == unary_operator::negation) + { + return std::visit([](auto v) -> std::optional<constant_value> { + using T = std::decay_t<decltype(v)>; + + if constexpr (std::is_same_v<T, bool>) + { + return constant_value{ !v }; + } + else if constexpr (std::is_integral_v<T>) + { + return constant_value{ ~v }; + } + return std::nullopt; + }, operand.value()); + } + return std::nullopt; + } + + template<typename T> + static std::optional<T> add_overflow(T lhs, T rhs) + { + if constexpr (std::is_integral_v<T> && !std::is_same_v<T, bool>) + { + T result; + return __builtin_add_overflow(lhs, rhs, &result) + ? std::nullopt + : std::make_optional<T>(result); + } + return std::make_optional<T>(lhs + rhs); + } + + template<typename T> + static std::optional<T> sub_overflow(T lhs, T rhs) + { + if constexpr (std::is_integral_v<T> && !std::is_same_v<T, bool>) + { + T result; + return __builtin_sub_overflow(lhs, rhs, &result) + ? std::nullopt + : std::make_optional<T>(result); + } + return std::make_optional<T>(lhs - rhs); + } + + template<typename T> + static std::optional<T> mul_overflow(T lhs, T rhs) + { + if constexpr (std::is_integral_v<T> && !std::is_same_v<T, bool>) + { + T result; + return __builtin_mul_overflow(lhs, rhs, &result) + ? std::nullopt + : std::make_optional<T>(result); + } + return std::make_optional<T>(lhs * rhs); + } + + template<typename T> + static std::optional<constant_value> evaluate_operation(binary_operator op, T lhs, T rhs) + { + if constexpr (std::is_same_v<T, std::nullptr_t> + || std::is_same_v<T, compound_constant>) + { + switch (op) + { + case binary_operator::equals: + return constant_value{ true }; + case binary_operator::not_equals: + return constant_value{ false }; + default: + return std::nullopt; + } + } + else + { + switch (op) + { + case binary_operator::sum: + if constexpr (std::is_arithmetic_v<T> && !std::is_same_v<T, bool>) + { + if (auto r = add_overflow(lhs, rhs)) + { + return constant_value{ *r }; + } + } + return std::nullopt; + case binary_operator::subtraction: + if constexpr (std::is_arithmetic_v<T> && !std::is_same_v<T, bool>) + { + if (auto r = sub_overflow(lhs, rhs)) + { + return constant_value{ *r }; + } + } + return std::nullopt; + case binary_operator::multiplication: + if constexpr (std::is_arithmetic_v<T> && !std::is_same_v<T, bool>) + { + if (auto r = mul_overflow(lhs, rhs)) + { + return constant_value{ *r }; + } + } + return std::nullopt; + case binary_operator::division: + if constexpr (std::is_arithmetic_v<T> && !std::is_same_v<T, bool>) + { + if (rhs != static_cast<T>(0)) + { + return constant_value{ lhs / rhs }; + } + } + return std::nullopt; + case binary_operator::remainder: + if constexpr (std::is_integral_v<T> && !std::is_same_v<T, bool>) + { + if (rhs != static_cast<T>(0)) + { + return constant_value{ lhs % rhs }; + } + } + return std::nullopt; + case binary_operator::disjunction: + if constexpr (std::is_integral_v<T>) + { + return constant_value{ lhs | rhs }; + } + return std::nullopt; + case binary_operator::conjunction: + if constexpr (std::is_integral_v<T>) + { + return constant_value{ lhs & rhs }; + } + return std::nullopt; + case binary_operator::exclusive_disjunction: + if constexpr (std::is_integral_v<T>) + { + return constant_value{ lhs ^ rhs }; + } + return std::nullopt; + case binary_operator::shift_left: + if constexpr (std::is_integral_v<T> && !std::is_same_v<T, bool>) + { + if (rhs < 0 || static_cast<std::make_unsigned_t<T>>(rhs) >= std::numeric_limits<T>::digits) + { + return std::nullopt; + } + return constant_value{ lhs << rhs }; + } + return std::nullopt; + case binary_operator::shift_right: + if constexpr (std::is_integral_v<T>) + { + return constant_value{ lhs >> rhs }; + } + return std::nullopt; + case binary_operator::equals: + return constant_value{ lhs == rhs }; + case binary_operator::not_equals: + return constant_value{ lhs != rhs }; + case binary_operator::less: + if constexpr (std::is_arithmetic_v<T> && !std::is_same_v<T, bool>) + { + return constant_value{ lhs < rhs }; + } + return std::nullopt; + case binary_operator::greater: + if constexpr (std::is_arithmetic_v<T> && !std::is_same_v<T, bool>) + { + return constant_value{ lhs > rhs }; + } + return std::nullopt; + case binary_operator::less_equal: + if constexpr (std::is_arithmetic_v<T> && !std::is_same_v<T, bool>) + { + return constant_value{ lhs <= rhs }; + } + return std::nullopt; + case binary_operator::greater_equal: + if constexpr (std::is_arithmetic_v<T> && !std::is_same_v<T, bool>) + { + return constant_value{ lhs >= rhs }; + } + return std::nullopt; + default: + return std::nullopt; + } + } + } + + std::optional<constant_value> evaluator::evaluate_binary(binary_expression& subject) + { + std::optional<constant_value> lhs = evaluate(subject.lhs()); + std::optional<constant_value> rhs = evaluate(subject.rhs()); + + if (!lhs || !rhs || lhs->index() != rhs->index()) + { + return std::nullopt; + } + return std::visit([this, &rhs, operation = subject.operation()](auto&& lhs_value) { + using T = std::decay_t<decltype(lhs_value)>; + auto rhs_value = std::get<T>(rhs.value()); + + return evaluate_operation<T>(operation, lhs_value, rhs_value); + }, lhs.value()); + } + + std::optional<constant_value> evaluator::evaluate_cast(cast_expression& subject) + { + if (auto value = evaluate(subject.value())) + { + return constant_value{ value.value() }; + } + else + { + return std::nullopt; + } + } + + std::optional<std::size_t> evaluator::evaluate_traits_size(const type& subject) + { + type resolved = resolve_underlying_type(subject); + + if (is_primitive_type(resolved, "Int")) + { + return target.int_size; + } + else if (is_primitive_type(resolved, "Word")) + { + return target.word_size; + } + else if (is_primitive_type(resolved, "Char")) + { + return target.char_size; + } + else if (is_primitive_type(resolved, "Float")) + { + return target.float_size; + } + else if (is_primitive_type(resolved, "Pointer")) + { + return target.pointer_size; + } + else if (resolved.get<pointer_type>() != nullptr) + { + return target.pointer_size; + } + else if (auto array = resolved.get<array_type>()) + { + if (auto element_size = evaluate_traits_size(array->base)) + { + return array->size * element_size.value(); + } + } + return std::nullopt; + } + + std::optional<std::size_t> evaluator::evaluate_traits_alignment(const type& subject) + { + type resolved = resolve_underlying_type(subject); + + if (is_primitive_type(resolved, "Int")) + { + return target.int_alignment; + } + if (is_primitive_type(resolved, "Word")) + { + return target.word_alignment; + } + if (is_primitive_type(resolved, "Char")) + { + return target.char_alignment; + } + if (is_primitive_type(resolved, "Float")) + { + return target.float_alignment; + } + if (is_primitive_type(resolved, "Pointer")) + { + return target.pointer_alignment; + } + if (resolved.get<pointer_type>() != nullptr) + { + return target.pointer_alignment; + } + if (auto array = resolved.get<array_type>()) + { + // The alignment of the array equals that of its element. + return evaluate_traits_alignment(array->base); + } + if (auto record = resolved.get<record_type>()) + { + // An empty record has alignment 1. + std::optional<std::size_t> by_field_alignment = std::accumulate( + std::begin(record->fields), std::end(record->fields), std::make_optional<std::size_t>(1), + [this](std::optional<std::size_t> max_alignment, auto& field) { + std::optional<std::size_t> field_alignment = evaluate_traits_alignment(field.second); + + return field_alignment.has_value() && max_alignment.has_value() + ? std::make_optional(std::max(field_alignment.value(), max_alignment.value())) + : std::nullopt; + } + ); + if (!by_field_alignment.has_value()) + { + return by_field_alignment; + } + std::size_t max_alignment = by_field_alignment.value(); + + if (!record->base.empty()) + { + if (auto base_alignment = evaluate_traits_alignment(record->base)) + { + max_alignment = std::max(base_alignment.value(), max_alignment); + } + else + { + return std::nullopt; + } + } + return max_alignment; + } + return std::nullopt; + } + + std::optional<constant_value> evaluator::evaluate_traits(traits_expression& subject) + { + if (subject.types.size() != 1) + { + return std::nullopt; + } + else if (subject.name.name() == "size") + { + if (auto size = evaluate_traits_size(subject.types.front())) + { + return constant_value{ static_cast<std::uint32_t>(size.value()) }; + } + } + else if (subject.name.name() == "alignment") + { + if (auto alignment = evaluate_traits_alignment(subject.types.front())) + { + return constant_value{ static_cast<std::uint32_t>(alignment.value()) }; + } + } + else if (subject.name.name() == "min") + { + type resolved = resolve_underlying_type(subject.types.front()); + + if (is_primitive_type(resolved, "Int")) + { + return constant_value{ std::numeric_limits<std::int32_t>::min() }; + } + if (is_primitive_type(resolved, "Word")) + { + return constant_value{ static_cast<std::uint32_t>(0) }; + } + if (is_primitive_type(resolved, "Char")) + { + return constant_value{ static_cast<unsigned char>(0) }; + } + if (auto enumeration = resolved.get<enumeration_type>()) + { + return constant_value{ 1 }; + } + } + else if (subject.name.name() == "max") + { + type resolved = resolve_underlying_type(subject.types.front()); + + if (is_primitive_type(resolved, "Int")) + { + return constant_value{ std::numeric_limits<std::int32_t>::max() }; + } + if (is_primitive_type(resolved, "Word")) + { + return constant_value{ std::numeric_limits<std::uint32_t>::max() }; + } + if (is_primitive_type(resolved, "Char")) + { + return constant_value{ static_cast<unsigned char>(255) }; + } + if (auto enumeration = resolved.get<enumeration_type>()) + { + return constant_value{ static_cast<std::int32_t>(enumeration->members.size()) }; + } + } + // #offset(T, field) stays in codegen - needs GCC record layout. + return std::nullopt; + } +} |