20319772105

Committed 17 Dec 2025 10:51PM UTC coverage: 39.875% (-0.1%) from 40.001%

Build # 20319772105

Build Type

Pull #397

github

Committed by

web-flow

Commit Message

Merge 4c22ff16d into ea9155d89

Pull Request Pull Request #397: adds zext_i64 symbolic function

Run Details

13477 of 43840 branches covered (30.74%)

Branch coverage included in aggregate %.

39 of 114 new or added lines in 8 files covered. (34.21%)

9 existing lines in 3 files now uncovered.

11603 of 19057 relevant lines covered (60.89%)

86.69 hits per line

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

39.37

/src/symbolic/extreme_values.cpp

#include "sdfg/symbolic/extreme_values.h"

#include "sdfg/symbolic/polynomials.h"

namespace sdfg {
namespace symbolic {

size_t MAX_DEPTH = 100;
Expression minimum(const Expression expr, const SymbolSet& parameters, const Assumptions& assumptions, const size_t depth);
Expression maximum(const Expression expr, const SymbolSet& parameters, const Assumptions& assumptions, const size_t depth);

Expression minimum(const Expression expr, const SymbolSet& parameters, const Assumptions& assumptions, const size_t depth) {
    // Base Cases
    if (depth > MAX_DEPTH) {
        return SymEngine::null;
    }

    if (SymEngine::is_a<SymEngine::NaN>(*expr)) {
        return SymEngine::null;
    }

    if (SymEngine::is_a<SymEngine::Integer>(*expr)) {
        return expr;
    } else if (SymEngine::is_a<SymEngine::Infty>(*expr)) {
        return expr;
    } else if (SymEngine::is_a<symbolic::ZExtI64Function>(*expr)) {
        auto zext = SymEngine::rcp_static_cast<const symbolic::ZExtI64Function>(expr);
        return symbolic::zext_i64(minimum(zext->get_args()[0], parameters, assumptions, depth + 1));
    }

    // Symbol
    if (SymEngine::is_a<SymEngine::Symbol>(*expr)) {
        auto sym = SymEngine::rcp_static_cast<const SymEngine::Symbol>(expr);
        if (parameters.find(sym) != parameters.end()) {
            return sym;
        }
        if (assumptions.find(sym) != assumptions.end()) {
            return minimum(assumptions.at(sym).lower_bound_deprecated(), parameters, assumptions, depth + 1);
        }
        return SymEngine::null;
    }

    // Mul
    if (SymEngine::is_a<SymEngine::Mul>(*expr)) {
        auto mul = SymEngine::rcp_static_cast<const SymEngine::Mul>(expr);
        const auto& args = mul->get_args();
        size_t n = args.size();

        std::vector<std::pair<Expression, Expression>> bounds;
        bounds.reserve(n);

        for (const auto& arg : args) {
            Expression min_val = minimum(arg, parameters, assumptions, depth + 1);
            Expression max_val = maximum(arg, parameters, assumptions, depth + 1);

            if (min_val == SymEngine::null || max_val == SymEngine::null) {
                return SymEngine::null;
            }
            bounds.emplace_back(min_val, max_val);
        }

        // Iterate over 2^n combinations
        Expression min_product = SymEngine::null;
        const size_t total_combinations = 1ULL << n;

        for (size_t mask = 0; mask < total_combinations; ++mask) {
            Expression product = SymEngine::integer(1);
            for (size_t i = 0; i < n; ++i) {
                const auto& bound = bounds[i];
                Expression val = (mask & (1ULL << i)) ? bound.second : bound.first;
                product = symbolic::mul(product, val);
            }
            if (min_product == SymEngine::null) {
                min_product = product;
            } else {
                min_product = symbolic::min(min_product, product);
            }
        }

        return min_product;
    }

    // Add
    if (SymEngine::is_a<SymEngine::Add>(*expr)) {
        auto add = SymEngine::rcp_static_cast<const SymEngine::Add>(expr);
        const auto& args = add->get_args();
        Expression lbs = SymEngine::null;
        for (const auto& arg : args) {
            auto lb = minimum(arg, parameters, assumptions, depth + 1);
            if (lb == SymEngine::null) {
                return SymEngine::null;
            }
            if (lbs == SymEngine::null) {
                lbs = lb;
            } else {
                lbs = symbolic::add(lbs, lb);
            }
        }
        return lbs;
    }

    // Max
    if (SymEngine::is_a<SymEngine::Max>(*expr)) {
        auto args = SymEngine::rcp_dynamic_cast<const SymEngine::Max>(expr)->get_args();
        Expression lbs = SymEngine::null;
        for (const auto& arg : args) {
            auto lb = minimum(arg, parameters, assumptions, depth + 1);
            if (lb == SymEngine::null) {
                return SymEngine::null;
            }
            if (lbs == SymEngine::null) {
                lbs = lb;
            } else {
                lbs = symbolic::min(lbs, lb);
            }
        }
        return lbs;
    }

    // Min
    if (SymEngine::is_a<SymEngine::Min>(*expr)) {
        auto args = SymEngine::rcp_dynamic_cast<const SymEngine::Min>(expr)->get_args();
        Expression lbs = SymEngine::null;
        for (const auto& arg : args) {
            auto lb = minimum(arg, parameters, assumptions, depth + 1);
            if (lb == SymEngine::null) {
                return SymEngine::null;
            }
            if (lbs == SymEngine::null) {
                lbs = lb;
            } else {
                lbs = symbolic::min(lbs, lb);
            }
        }
        return lbs;
    }

    return SymEngine::null;
}

Expression maximum(const Expression expr, const SymbolSet& parameters, const Assumptions& assumptions, const size_t depth) {
    if (depth > MAX_DEPTH) {
        return SymEngine::null;
    }

    if (SymEngine::is_a<SymEngine::NaN>(*expr)) {
        return SymEngine::null;
    }

    // Base Cases
    if (SymEngine::is_a<SymEngine::Integer>(*expr)) {
        return expr;
    } else if (SymEngine::is_a<SymEngine::Infty>(*expr)) {
        return expr;
    }

    // Symbol
    if (SymEngine::is_a<SymEngine::Symbol>(*expr)) {
        auto sym = SymEngine::rcp_static_cast<const SymEngine::Symbol>(expr);
        if (parameters.find(sym) != parameters.end()) {
            return sym;
        }
        if (assumptions.find(sym) != assumptions.end()) {
            return maximum(assumptions.at(sym).upper_bound_deprecated(), parameters, assumptions, depth + 1);
        }
        return SymEngine::null;
    }

    if (SymEngine::is_a<symbolic::ZExtI64Function>(*expr)) {
        auto zext = SymEngine::rcp_static_cast<const symbolic::ZExtI64Function>(expr);
        return symbolic::zext_i64(maximum(zext->get_args()[0], parameters, assumptions, depth + 1));
    }

    // Mul
    if (SymEngine::is_a<SymEngine::Mul>(*expr)) {
        auto mul = SymEngine::rcp_static_cast<const SymEngine::Mul>(expr);
        const auto& args = mul->get_args();
        size_t n = args.size();

        std::vector<std::pair<Expression, Expression>> bounds;
        bounds.reserve(n);

        for (const auto& arg : args) {
            Expression min_val = minimum(arg, parameters, assumptions, depth + 1);
            Expression max_val = maximum(arg, parameters, assumptions, depth + 1);

            if (min_val == SymEngine::null || max_val == SymEngine::null) {
                return SymEngine::null;
            }
            bounds.emplace_back(min_val, max_val);
        }

        // Iterate over 2^n combinations
        Expression max_product = SymEngine::null;
        const size_t total_combinations = 1ULL << n;

        for (size_t mask = 0; mask < total_combinations; ++mask) {
            Expression product = SymEngine::integer(1);
            for (size_t i = 0; i < n; ++i) {
                const auto& bound = bounds[i];
                Expression val = (mask & (1ULL << i)) ? bound.second : bound.first;
                product = symbolic::mul(product, val);
            }
            if (max_product == SymEngine::null) {
                max_product = product;
            } else {
                max_product = symbolic::max(max_product, product);
            }
        }

        return max_product;
    }

    // Add
    if (SymEngine::is_a<SymEngine::Add>(*expr)) {
        auto add = SymEngine::rcp_static_cast<const SymEngine::Add>(expr);
        const auto& args = add->get_args();
        Expression ubs = SymEngine::null;
        for (const auto& arg : args) {
            auto ub = maximum(arg, parameters, assumptions, depth + 1);
            if (ub == SymEngine::null) {
                return SymEngine::null;
            }
            if (ubs == SymEngine::null) {
                ubs = ub;
            } else {
                ubs = symbolic::add(ubs, ub);
            }
        }
        return ubs;
    }

    // Max
    if (SymEngine::is_a<SymEngine::Max>(*expr)) {
        auto args = SymEngine::rcp_dynamic_cast<const SymEngine::Max>(expr)->get_args();
        Expression ubs = SymEngine::null;
        for (const auto& arg : args) {
            auto ub = maximum(arg, parameters, assumptions, depth + 1);
            if (ub == SymEngine::null) {
                return SymEngine::null;
            }
            if (ubs == SymEngine::null) {
                ubs = ub;
            } else {
                ubs = symbolic::max(ubs, ub);
            }
        }
        return ubs;
    }

    // Min
    if (SymEngine::is_a<SymEngine::Min>(*expr)) {
        auto args = SymEngine::rcp_dynamic_cast<const SymEngine::Min>(expr)->get_args();
        Expression ubs = SymEngine::null;
        for (const auto& arg : args) {
            auto ub = maximum(arg, parameters, assumptions, depth + 1);
            if (ub == SymEngine::null) {
                return SymEngine::null;
            }
            if (ubs == SymEngine::null) {
                ubs = ub;
            } else {
                ubs = symbolic::max(ubs, ub);
            }
        }
        return ubs;
    }

    return SymEngine::null;
}

Expression minimum(const Expression expr, const SymbolSet& parameters, const Assumptions& assumptions) {
    return minimum(expr, parameters, assumptions, 0);
}

Expression maximum(const Expression expr, const SymbolSet& parameters, const Assumptions& assumptions) {
    return maximum(expr, parameters, assumptions, 0);
}

Expression minimum_new(
    const Expression expr, const SymbolSet& parameters, const Assumptions& assumptions, const size_t depth, bool tight
);
Expression maximum_new(
    const Expression expr, const SymbolSet& parameters, const Assumptions& assumptions, const size_t depth, bool tight
);

Expression minimum_new(
    const Expression expr, const SymbolSet& parameters, const Assumptions& assumptions, const size_t depth, bool tight
) {
    // End of recursion: fail
    if (depth > MAX_DEPTH) {
        return SymEngine::null;
    }
    if (SymEngine::is_a<SymEngine::NaN>(*expr)) {
        return SymEngine::null;
    }
    if (SymEngine::is_a<SymEngine::Infty>(*expr)) {
        return SymEngine::null;
    }
    // End of recursion: success
    if (SymEngine::is_a<SymEngine::Integer>(*expr)) {
        return expr;
    }
    if (SymEngine::is_a<SymEngine::Symbol>(*expr)) {
        auto sym = SymEngine::rcp_static_cast<const SymEngine::Symbol>(expr);
        if (parameters.find(sym) != parameters.end()) {
            return sym;
        }
    }

    if (SymEngine::is_a<symbolic::ZExtI64Function>(*expr)) {
        auto zext = SymEngine::rcp_static_cast<const symbolic::ZExtI64Function>(expr);
        return symbolic::zext_i64(minimum_new(zext->get_args()[0], parameters, assumptions, depth + 1, tight));
    }

    // Symbol
    if (SymEngine::is_a<SymEngine::Symbol>(*expr)) {
        auto sym = SymEngine::rcp_static_cast<const SymEngine::Symbol>(expr);
        if (assumptions.find(sym) != assumptions.end()) {
            if (tight) {
                if (assumptions.at(sym).tight_lower_bound().is_null()) {
                    return SymEngine::null;
                }
                return minimum_new(assumptions.at(sym).tight_lower_bound(), parameters, assumptions, depth + 1, tight);
            }
            symbolic::Expression new_lb = SymEngine::null;
            for (auto& lb : assumptions.at(sym).lower_bounds()) {
                auto new_min = minimum_new(lb, parameters, assumptions, depth + 1, tight);
                if (new_min.is_null()) {
                    continue;
                }
                if (new_lb.is_null()) {
                    new_lb = new_min;
                    continue;
                }
                new_lb = symbolic::max(new_lb, new_min);
            }
            return new_lb;
        }
        return SymEngine::null;
    }

    // Mul
    if (SymEngine::is_a<SymEngine::Mul>(*expr)) {
        auto mul = SymEngine::rcp_static_cast<const SymEngine::Mul>(expr);
        const auto& args = mul->get_args();
        size_t n = args.size();

        std::vector<std::pair<Expression, Expression>> bounds;
        bounds.reserve(n);

        for (const auto& arg : args) {
            Expression min_val = minimum_new(arg, parameters, assumptions, depth + 1, tight);
            Expression max_val = maximum_new(arg, parameters, assumptions, depth + 1, tight);

            if (min_val == SymEngine::null || max_val == SymEngine::null) {
                return SymEngine::null;
            }
            bounds.emplace_back(min_val, max_val);
        }

        // Iterate over 2^n combinations
        Expression min_product = SymEngine::null;
        const size_t total_combinations = 1ULL << n;

        for (size_t mask = 0; mask < total_combinations; ++mask) {
            Expression product = SymEngine::integer(1);
            for (size_t i = 0; i < n; ++i) {
                const auto& bound = bounds[i];
                Expression val = (mask & (1ULL << i)) ? bound.second : bound.first;
                product = symbolic::mul(product, val);
            }
            if (min_product == SymEngine::null) {
                min_product = product;
            } else {
                min_product = symbolic::min(min_product, product);
            }
        }

        return min_product;
    }

    // Add
    if (SymEngine::is_a<SymEngine::Add>(*expr)) {
        auto add = SymEngine::rcp_static_cast<const SymEngine::Add>(expr);
        const auto& args = add->get_args();
        Expression lbs = SymEngine::null;
        for (const auto& arg : args) {
            auto lb = minimum_new(arg, parameters, assumptions, depth + 1, tight);
            if (lb == SymEngine::null) {
                return SymEngine::null;
            }
            if (lbs == SymEngine::null) {
                lbs = lb;
            } else {
                lbs = symbolic::add(lbs, lb);
            }
        }
        return lbs;
    }

    // Max
    if (SymEngine::is_a<SymEngine::Max>(*expr)) {
        auto args = SymEngine::rcp_dynamic_cast<const SymEngine::Max>(expr)->get_args();
        Expression lbs = SymEngine::null;
        for (const auto& arg : args) {
            auto lb = minimum_new(arg, parameters, assumptions, depth + 1, tight);
            if (lb == SymEngine::null) {
                return SymEngine::null;
            }
            if (lbs == SymEngine::null) {
                lbs = lb;
            } else {
                lbs = symbolic::min(lbs, lb);
            }
        }
        return lbs;
    }

    // Min
    if (SymEngine::is_a<SymEngine::Min>(*expr)) {
        auto args = SymEngine::rcp_dynamic_cast<const SymEngine::Min>(expr)->get_args();
        Expression lbs = SymEngine::null;
        for (const auto& arg : args) {
            auto lb = minimum_new(arg, parameters, assumptions, depth + 1, tight);
            if (lb == SymEngine::null) {
                return SymEngine::null;
            }
            if (lbs == SymEngine::null) {
                lbs = lb;
            } else {
                lbs = symbolic::min(lbs, lb);
            }
        }
        return lbs;
    }

    return SymEngine::null;
}

Expression maximum_new(
    const Expression expr, const SymbolSet& parameters, const Assumptions& assumptions, const size_t depth, bool tight
) {
    // End of recursion: fail
    if (depth > MAX_DEPTH) {
        return SymEngine::null;
    }
    if (SymEngine::is_a<SymEngine::NaN>(*expr)) {
        return SymEngine::null;
    }
    if (SymEngine::is_a<SymEngine::Infty>(*expr)) {
        return SymEngine::null;
    }
    // End of recursion: success
    if (SymEngine::is_a<SymEngine::Integer>(*expr)) {
        return expr;
    }
    if (SymEngine::is_a<SymEngine::Symbol>(*expr)) {
        auto sym = SymEngine::rcp_static_cast<const SymEngine::Symbol>(expr);
        if (parameters.find(sym) != parameters.end()) {
            return sym;
        }
    }

    if (SymEngine::is_a<symbolic::ZExtI64Function>(*expr)) {
        auto zext = SymEngine::rcp_static_cast<const symbolic::ZExtI64Function>(expr);
        return symbolic::zext_i64(maximum_new(zext->get_args()[0], parameters, assumptions, depth + 1, tight));
    }

    // Symbol
    if (SymEngine::is_a<SymEngine::Symbol>(*expr)) {
        auto sym = SymEngine::rcp_static_cast<const SymEngine::Symbol>(expr);
        if (assumptions.find(sym) != assumptions.end()) {
            if (tight) {
                if (assumptions.at(sym).tight_upper_bound().is_null()) {
                    return SymEngine::null;
                }
                return maximum_new(assumptions.at(sym).tight_upper_bound(), parameters, assumptions, depth + 1, tight);
            }
            symbolic::Expression new_ub = SymEngine::null;
            for (auto& ub : assumptions.at(sym).upper_bounds()) {
                auto new_max = maximum_new(ub, parameters, assumptions, depth + 1, tight);
                if (new_max.is_null()) {
                    continue;
                }
                if (new_ub.is_null()) {
                    new_ub = new_max;
                    continue;
                }
                new_ub = symbolic::min(new_ub, new_max);
            }
            return new_ub;
        }
        return SymEngine::null;
    }

    // Mul
    if (SymEngine::is_a<SymEngine::Mul>(*expr)) {
        auto mul = SymEngine::rcp_static_cast<const SymEngine::Mul>(expr);
        const auto& args = mul->get_args();
        size_t n = args.size();

        std::vector<std::pair<Expression, Expression>> bounds;
        bounds.reserve(n);

        for (const auto& arg : args) {
            Expression min_val = minimum_new(arg, parameters, assumptions, depth + 1, tight);
            Expression max_val = maximum_new(arg, parameters, assumptions, depth + 1, tight);

            if (min_val == SymEngine::null || max_val == SymEngine::null) {
                return SymEngine::null;
            }
            bounds.emplace_back(min_val, max_val);
        }

        // Iterate over 2^n combinations
        Expression max_product = SymEngine::null;
        const size_t total_combinations = 1ULL << n;

        for (size_t mask = 0; mask < total_combinations; ++mask) {
            Expression product = SymEngine::integer(1);
            for (size_t i = 0; i < n; ++i) {
                const auto& bound = bounds[i];
                Expression val = (mask & (1ULL << i)) ? bound.second : bound.first;
                product = symbolic::mul(product, val);
            }
            if (max_product == SymEngine::null) {
                max_product = product;
            } else {
                max_product = symbolic::max(max_product, product);
            }
        }

        return max_product;
    }

    // Add
    if (SymEngine::is_a<SymEngine::Add>(*expr)) {
        auto add = SymEngine::rcp_static_cast<const SymEngine::Add>(expr);
        const auto& args = add->get_args();
        Expression ubs = SymEngine::null;
        for (const auto& arg : args) {
            auto ub = maximum_new(arg, parameters, assumptions, depth + 1, tight);
            if (ub == SymEngine::null) {
                return SymEngine::null;
            }
            if (ubs == SymEngine::null) {
                ubs = ub;
            } else {
                ubs = symbolic::add(ubs, ub);
            }
        }
        return ubs;
    }

    // Max
    if (SymEngine::is_a<SymEngine::Max>(*expr)) {
        auto args = SymEngine::rcp_dynamic_cast<const SymEngine::Max>(expr)->get_args();
        Expression ubs = SymEngine::null;
        for (const auto& arg : args) {
            auto ub = maximum_new(arg, parameters, assumptions, depth + 1, tight);
            if (ub == SymEngine::null) {
                return SymEngine::null;
            }
            if (ubs == SymEngine::null) {
                ubs = ub;
            } else {
                ubs = symbolic::max(ubs, ub);
            }
        }
        return ubs;
    }

    // Min
    if (SymEngine::is_a<SymEngine::Min>(*expr)) {
        auto args = SymEngine::rcp_dynamic_cast<const SymEngine::Min>(expr)->get_args();
        Expression ubs = SymEngine::null;
        for (const auto& arg : args) {
            auto ub = maximum_new(arg, parameters, assumptions, depth + 1, tight);
            if (ub == SymEngine::null) {
                return SymEngine::null;
            }
            if (ubs == SymEngine::null) {
                ubs = ub;
            } else {
                ubs = symbolic::max(ubs, ub);
            }
        }
        return ubs;
    }

    return SymEngine::null;
}

Expression minimum_new(const Expression expr, const SymbolSet& parameters, const Assumptions& assumptions, bool tight) {
    return minimum_new(expr, parameters, assumptions, 0, tight);
}

Expression maximum_new(const Expression expr, const SymbolSet& parameters, const Assumptions& assumptions, bool tight) {
    return maximum_new(expr, parameters, assumptions, 0, tight);
}

} // namespace symbolic
} // namespace sdfg

1	#include "sdfg/symbolic/extreme_values.h"
2
3	#include "sdfg/symbolic/polynomials.h"
4
5	namespace sdfg {
6	namespace symbolic {
7
8	size_t MAX_DEPTH = 100;
9	Expression minimum(const Expression expr, const SymbolSet& parameters, const Assumptions& assumptions, const size_t depth);
10	Expression maximum(const Expression expr, const SymbolSet& parameters, const Assumptions& assumptions, const size_t depth);
11
12	Expression minimum(const Expression expr, const SymbolSet& parameters, const Assumptions& assumptions, const size_t depth) {	4,883✔
13	// Base Cases
14	if (depth > MAX_DEPTH) {	4,883✔
15	return SymEngine::null;	12✔
16	}
17
18	if (SymEngine::is_a<SymEngine::NaN>(*expr)) {	4,871!
19	return SymEngine::null;	×
20	}
21
22	if (SymEngine::is_a<SymEngine::Integer>(*expr)) {	4,871✔
23	return expr;	2,488✔
24	} else if (SymEngine::is_a<SymEngine::Infty>(*expr)) {	2,383!
25	return expr;	×
26	} else if (SymEngine::is_a<symbolic::ZExtI64Function>(*expr)) {	2,383!
NEW 27	auto zext = SymEngine::rcp_static_cast<const symbolic::ZExtI64Function>(expr);	×
NEW 28	return symbolic::zext_i64(minimum(zext->get_args()[0], parameters, assumptions, depth + 1));	×
UNCOV 29	}	×
30
31	// Symbol
32	if (SymEngine::is_a<SymEngine::Symbol>(*expr)) {	2,383✔
33	auto sym = SymEngine::rcp_static_cast<const SymEngine::Symbol>(expr);	1,488✔
34	if (parameters.find(sym) != parameters.end()) {	1,488!
35	return sym;	7✔
36	}
37	if (assumptions.find(sym) != assumptions.end()) {	1,481!
38	return minimum(assumptions.at(sym).lower_bound_deprecated(), parameters, assumptions, depth + 1);	1,478!
39	}
40	return SymEngine::null;	3!
41	}	1,488✔
42
43	// Mul
44	if (SymEngine::is_a<SymEngine::Mul>(*expr)) {	895✔
45	auto mul = SymEngine::rcp_static_cast<const SymEngine::Mul>(expr);	150✔
46	const auto& args = mul->get_args();	150!
47	size_t n = args.size();	150✔
48
49	std::vector<std::pair<Expression, Expression>> bounds;	150✔
50	bounds.reserve(n);	150!
51
52	for (const auto& arg : args) {	508✔
53	Expression min_val = minimum(arg, parameters, assumptions, depth + 1);	358!
54	Expression max_val = maximum(arg, parameters, assumptions, depth + 1);	358!
55
56	if (min_val == SymEngine::null \|\| max_val == SymEngine::null) {	358!
57	return SymEngine::null;	×
58	}
59	bounds.emplace_back(min_val, max_val);	358!
60	}	358!
61
62	// Iterate over 2^n combinations
63	Expression min_product = SymEngine::null;	150!
64	const size_t total_combinations = 1ULL << n;	150✔
65
66	for (size_t mask = 0; mask < total_combinations; ++mask) {	982✔
67	Expression product = SymEngine::integer(1);	832!
68	for (size_t i = 0; i < n; ++i) {	2,960✔
69	const auto& bound = bounds[i];	2,128✔
70	Expression val = (mask & (1ULL << i)) ? bound.second : bound.first;	2,128!
71	product = symbolic::mul(product, val);	2,128!
72	}	2,128✔
73	if (min_product == SymEngine::null) {	832!
74	min_product = product;	150!
75	} else {	150✔
76	min_product = symbolic::min(min_product, product);	682!
77	}
78	}	832✔
79
80	return min_product;	150✔
81	}	300!
82
83	// Add
84	if (SymEngine::is_a<SymEngine::Add>(*expr)) {	745✔
85	auto add = SymEngine::rcp_static_cast<const SymEngine::Add>(expr);	459✔
86	const auto& args = add->get_args();	459!
87	Expression lbs = SymEngine::null;	459!
88	for (const auto& arg : args) {	1,190✔
89	auto lb = minimum(arg, parameters, assumptions, depth + 1);	995!
90	if (lb == SymEngine::null) {	995!
91	return SymEngine::null;	264!
92	}
93	if (lbs == SymEngine::null) {	731!
94	lbs = lb;	451!
95	} else {	451✔
96	lbs = symbolic::add(lbs, lb);	280!
97	}
98	}	995✔
99	return lbs;	195✔
100	}	459✔
101
102	// Max
103	if (SymEngine::is_a<SymEngine::Max>(*expr)) {	286✔
104	auto args = SymEngine::rcp_dynamic_cast<const SymEngine::Max>(expr)->get_args();	284!
105	Expression lbs = SymEngine::null;	284!
106	for (const auto& arg : args) {	576✔
107	auto lb = minimum(arg, parameters, assumptions, depth + 1);	566!
108	if (lb == SymEngine::null) {	566!
109	return SymEngine::null;	274!
110	}
111	if (lbs == SymEngine::null) {	292!
112	lbs = lb;	282!
113	} else {	282✔
114	lbs = symbolic::min(lbs, lb);	10!
115	}
116	}	566✔
117	return lbs;	10✔
118	}	284✔
119
120	// Min
121	if (SymEngine::is_a<SymEngine::Min>(*expr)) {	2!
122	auto args = SymEngine::rcp_dynamic_cast<const SymEngine::Min>(expr)->get_args();	2!
123	Expression lbs = SymEngine::null;	2!
124	for (const auto& arg : args) {	6✔
125	auto lb = minimum(arg, parameters, assumptions, depth + 1);	4!
126	if (lb == SymEngine::null) {	4!
127	return SymEngine::null;	×
128	}
129	if (lbs == SymEngine::null) {	4!
130	lbs = lb;	2!
131	} else {	2✔
132	lbs = symbolic::min(lbs, lb);	2!
133	}
134	}	4!
135	return lbs;	2✔
136	}	2✔
137
138	return SymEngine::null;	×
139	}	4,883✔
140
141	Expression maximum(const Expression expr, const SymbolSet& parameters, const Assumptions& assumptions, const size_t depth) {	2,950✔
142	if (depth > MAX_DEPTH) {	2,950!
143	return SymEngine::null;	×
144	}
145
146	if (SymEngine::is_a<SymEngine::NaN>(*expr)) {	2,950!
147	return SymEngine::null;	×
148	}
149
150	// Base Cases
151	if (SymEngine::is_a<SymEngine::Integer>(*expr)) {	2,950✔
152	return expr;	1,389✔
153	} else if (SymEngine::is_a<SymEngine::Infty>(*expr)) {	1,561!
154	return expr;	×
155	}
156
157	// Symbol
158	if (SymEngine::is_a<SymEngine::Symbol>(*expr)) {	1,561✔
159	auto sym = SymEngine::rcp_static_cast<const SymEngine::Symbol>(expr);	936✔
160	if (parameters.find(sym) != parameters.end()) {	936!
161	return sym;	8✔
162	}
163	if (assumptions.find(sym) != assumptions.end()) {	928!
164	return maximum(assumptions.at(sym).upper_bound_deprecated(), parameters, assumptions, depth + 1);	928!
165	}
166	return SymEngine::null;	×
167	}	936✔
168
169	if (SymEngine::is_a<symbolic::ZExtI64Function>(*expr)) {	625!
NEW 170	auto zext = SymEngine::rcp_static_cast<const symbolic::ZExtI64Function>(expr);	×
NEW 171	return symbolic::zext_i64(maximum(zext->get_args()[0], parameters, assumptions, depth + 1));	×
NEW 172	}	×
173
174	// Mul
175	if (SymEngine::is_a<SymEngine::Mul>(*expr)) {	625✔
176	auto mul = SymEngine::rcp_static_cast<const SymEngine::Mul>(expr);	150✔
177	const auto& args = mul->get_args();	150!
178	size_t n = args.size();	150✔
179
180	std::vector<std::pair<Expression, Expression>> bounds;	150✔
181	bounds.reserve(n);	150!
182
183	for (const auto& arg : args) {	508✔
184	Expression min_val = minimum(arg, parameters, assumptions, depth + 1);	358!
185	Expression max_val = maximum(arg, parameters, assumptions, depth + 1);	358!
186
187	if (min_val == SymEngine::null \|\| max_val == SymEngine::null) {	358!
188	return SymEngine::null;	×
189	}
190	bounds.emplace_back(min_val, max_val);	358!
191	}	358!
192
193	// Iterate over 2^n combinations
194	Expression max_product = SymEngine::null;	150!
195	const size_t total_combinations = 1ULL << n;	150✔
196
197	for (size_t mask = 0; mask < total_combinations; ++mask) {	982✔
198	Expression product = SymEngine::integer(1);	832!
199	for (size_t i = 0; i < n; ++i) {	2,960✔
200	const auto& bound = bounds[i];	2,128✔
201	Expression val = (mask & (1ULL << i)) ? bound.second : bound.first;	2,128!
202	product = symbolic::mul(product, val);	2,128!
203	}	2,128✔
204	if (max_product == SymEngine::null) {	832!
205	max_product = product;	150!
206	} else {	150✔
207	max_product = symbolic::max(max_product, product);	682!
208	}
209	}	832✔
210
211	return max_product;	150✔
212	}	300!
213
214	// Add
215	if (SymEngine::is_a<SymEngine::Add>(*expr)) {	475✔
216	auto add = SymEngine::rcp_static_cast<const SymEngine::Add>(expr);	471✔
217	const auto& args = add->get_args();	471!
218	Expression ubs = SymEngine::null;	471!
219	for (const auto& arg : args) {	1,498✔
220	auto ub = maximum(arg, parameters, assumptions, depth + 1);	1,027!
221	if (ub == SymEngine::null) {	1,027!
222	return SymEngine::null;	×
223	}
224	if (ubs == SymEngine::null) {	1,027!
225	ubs = ub;	471!
226	} else {	471✔
227	ubs = symbolic::add(ubs, ub);	556!
228	}
229	}	1,027!
230	return ubs;	471✔
231	}	471✔
232
233	// Max
234	if (SymEngine::is_a<SymEngine::Max>(*expr)) {	4✔
235	auto args = SymEngine::rcp_dynamic_cast<const SymEngine::Max>(expr)->get_args();	2!
236	Expression ubs = SymEngine::null;	2!
237	for (const auto& arg : args) {	6✔
238	auto ub = maximum(arg, parameters, assumptions, depth + 1);	4!
239	if (ub == SymEngine::null) {	4!
240	return SymEngine::null;	×
241	}
242	if (ubs == SymEngine::null) {	4!
243	ubs = ub;	2!
244	} else {	2✔
245	ubs = symbolic::max(ubs, ub);	2!
246	}
247	}	4!
248	return ubs;	2✔
249	}	2✔
250
251	// Min
252	if (SymEngine::is_a<SymEngine::Min>(*expr)) {	2!
253	auto args = SymEngine::rcp_dynamic_cast<const SymEngine::Min>(expr)->get_args();	2!
254	Expression ubs = SymEngine::null;	2!
255	for (const auto& arg : args) {	6✔
256	auto ub = maximum(arg, parameters, assumptions, depth + 1);	4!
257	if (ub == SymEngine::null) {	4!
258	return SymEngine::null;	×
259	}
260	if (ubs == SymEngine::null) {	4!
261	ubs = ub;	2!
262	} else {	2✔
263	ubs = symbolic::max(ubs, ub);	2!
264	}
265	}	4!
266	return ubs;	2✔
267	}	2✔
268
269	return SymEngine::null;	×
270	}	2,950✔
271
272	Expression minimum(const Expression expr, const SymbolSet& parameters, const Assumptions& assumptions) {	1,124✔
273	return minimum(expr, parameters, assumptions, 0);	1,124!
274	}	×
275
276	Expression maximum(const Expression expr, const SymbolSet& parameters, const Assumptions& assumptions) {	271✔
277	return maximum(expr, parameters, assumptions, 0);	271!
278	}	×
279
280	Expression minimum_new(
281	const Expression expr, const SymbolSet& parameters, const Assumptions& assumptions, const size_t depth, bool tight
282	);
283	Expression maximum_new(
284	const Expression expr, const SymbolSet& parameters, const Assumptions& assumptions, const size_t depth, bool tight
285	);
286
287	Expression minimum_new(	22✔
288	const Expression expr, const SymbolSet& parameters, const Assumptions& assumptions, const size_t depth, bool tight
289	) {
290	// End of recursion: fail
291	if (depth > MAX_DEPTH) {	22!
292	return SymEngine::null;	×
293	}
294	if (SymEngine::is_a<SymEngine::NaN>(*expr)) {	22!
295	return SymEngine::null;	×
296	}
297	if (SymEngine::is_a<SymEngine::Infty>(*expr)) {	22!
298	return SymEngine::null;	×
299	}
300	// End of recursion: success
301	if (SymEngine::is_a<SymEngine::Integer>(*expr)) {	22✔
302	return expr;	10✔
303	}
304	if (SymEngine::is_a<SymEngine::Symbol>(*expr)) {	12!
305	auto sym = SymEngine::rcp_static_cast<const SymEngine::Symbol>(expr);	12✔
306	if (parameters.find(sym) != parameters.end()) {	12!
307	return sym;	3✔
308	}
309	}	12✔
310
311	if (SymEngine::is_a<symbolic::ZExtI64Function>(*expr)) {	9!
NEW 312	auto zext = SymEngine::rcp_static_cast<const symbolic::ZExtI64Function>(expr);	×
NEW 313	return symbolic::zext_i64(minimum_new(zext->get_args()[0], parameters, assumptions, depth + 1, tight));	×
NEW 314	}	×
315
316	// Symbol
317	if (SymEngine::is_a<SymEngine::Symbol>(*expr)) {	9!
318	auto sym = SymEngine::rcp_static_cast<const SymEngine::Symbol>(expr);	9✔
319	if (assumptions.find(sym) != assumptions.end()) {	9!
320	if (tight) {	9!
321	if (assumptions.at(sym).tight_lower_bound().is_null()) {	9!
322	return SymEngine::null;	1!
323	}
324	return minimum_new(assumptions.at(sym).tight_lower_bound(), parameters, assumptions, depth + 1, tight);	8!
325	}
326	symbolic::Expression new_lb = SymEngine::null;	×
327	for (auto& lb : assumptions.at(sym).lower_bounds()) {	×
328	auto new_min = minimum_new(lb, parameters, assumptions, depth + 1, tight);	×
329	if (new_min.is_null()) {	×
330	continue;	×
331	}
332	if (new_lb.is_null()) {	×
333	new_lb = new_min;	×
334	continue;	×
335	}
336	new_lb = symbolic::max(new_lb, new_min);	×
337	}	×
338	return new_lb;	×
339	}	×
340	return SymEngine::null;	×
341	}	9✔
342
343	// Mul
344	if (SymEngine::is_a<SymEngine::Mul>(*expr)) {	×
345	auto mul = SymEngine::rcp_static_cast<const SymEngine::Mul>(expr);	×
346	const auto& args = mul->get_args();	×
347	size_t n = args.size();	×
348
349	std::vector<std::pair<Expression, Expression>> bounds;	×
350	bounds.reserve(n);	×
351
352	for (const auto& arg : args) {	×
353	Expression min_val = minimum_new(arg, parameters, assumptions, depth + 1, tight);	×
354	Expression max_val = maximum_new(arg, parameters, assumptions, depth + 1, tight);	×
355
356	if (min_val == SymEngine::null \|\| max_val == SymEngine::null) {	×
357	return SymEngine::null;	×
358	}
359	bounds.emplace_back(min_val, max_val);	×
360	}	×
361
362	// Iterate over 2^n combinations
363	Expression min_product = SymEngine::null;	×
364	const size_t total_combinations = 1ULL << n;	×
365
366	for (size_t mask = 0; mask < total_combinations; ++mask) {	×
367	Expression product = SymEngine::integer(1);	×
368	for (size_t i = 0; i < n; ++i) {	×
369	const auto& bound = bounds[i];	×
370	Expression val = (mask & (1ULL << i)) ? bound.second : bound.first;	×
371	product = symbolic::mul(product, val);	×
372	}	×
373	if (min_product == SymEngine::null) {	×
374	min_product = product;	×
375	} else {	×
376	min_product = symbolic::min(min_product, product);	×
377	}
378	}	×
379
380	return min_product;	×
381	}	×
382
383	// Add
384	if (SymEngine::is_a<SymEngine::Add>(*expr)) {	×
385	auto add = SymEngine::rcp_static_cast<const SymEngine::Add>(expr);	×
386	const auto& args = add->get_args();	×
387	Expression lbs = SymEngine::null;	×
388	for (const auto& arg : args) {	×
389	auto lb = minimum_new(arg, parameters, assumptions, depth + 1, tight);	×
390	if (lb == SymEngine::null) {	×
391	return SymEngine::null;	×
392	}
393	if (lbs == SymEngine::null) {	×
394	lbs = lb;	×
395	} else {	×
396	lbs = symbolic::add(lbs, lb);	×
397	}
398	}	×
399	return lbs;	×
400	}	×
401
402	// Max
403	if (SymEngine::is_a<SymEngine::Max>(*expr)) {	×
404	auto args = SymEngine::rcp_dynamic_cast<const SymEngine::Max>(expr)->get_args();	×
405	Expression lbs = SymEngine::null;	×
406	for (const auto& arg : args) {	×
407	auto lb = minimum_new(arg, parameters, assumptions, depth + 1, tight);	×
408	if (lb == SymEngine::null) {	×
409	return SymEngine::null;	×
410	}
411	if (lbs == SymEngine::null) {	×
412	lbs = lb;	×
413	} else {	×
414	lbs = symbolic::min(lbs, lb);	×
415	}
416	}	×
417	return lbs;	×
418	}	×
419
420	// Min
421	if (SymEngine::is_a<SymEngine::Min>(*expr)) {	×
422	auto args = SymEngine::rcp_dynamic_cast<const SymEngine::Min>(expr)->get_args();	×
423	Expression lbs = SymEngine::null;	×
424	for (const auto& arg : args) {	×
425	auto lb = minimum_new(arg, parameters, assumptions, depth + 1, tight);	×
426	if (lb == SymEngine::null) {	×
427	return SymEngine::null;	×
428	}
429	if (lbs == SymEngine::null) {	×
430	lbs = lb;	×
431	} else {	×
432	lbs = symbolic::min(lbs, lb);	×
433	}
434	}	×
435	return lbs;	×
436	}	×
437
438	return SymEngine::null;	×
439	}	22✔
440
441	Expression maximum_new(	29✔
442	const Expression expr, const SymbolSet& parameters, const Assumptions& assumptions, const size_t depth, bool tight
443	) {
444	// End of recursion: fail
445	if (depth > MAX_DEPTH) {	29!
446	return SymEngine::null;	×
447	}
448	if (SymEngine::is_a<SymEngine::NaN>(*expr)) {	29!
449	return SymEngine::null;	×
450	}
451	if (SymEngine::is_a<SymEngine::Infty>(*expr)) {	29!
452	return SymEngine::null;	×
453	}
454	// End of recursion: success
455	if (SymEngine::is_a<SymEngine::Integer>(*expr)) {	29✔
456	return expr;	10✔
457	}
458	if (SymEngine::is_a<SymEngine::Symbol>(*expr)) {	19✔
459	auto sym = SymEngine::rcp_static_cast<const SymEngine::Symbol>(expr);	15✔
460	if (parameters.find(sym) != parameters.end()) {	15!
461	return sym;	7✔
462	}
463	}	15✔
464
465	if (SymEngine::is_a<symbolic::ZExtI64Function>(*expr)) {	12!
NEW 466	auto zext = SymEngine::rcp_static_cast<const symbolic::ZExtI64Function>(expr);	×
NEW 467	return symbolic::zext_i64(maximum_new(zext->get_args()[0], parameters, assumptions, depth + 1, tight));	×
NEW 468	}	×
469
470	// Symbol
471	if (SymEngine::is_a<SymEngine::Symbol>(*expr)) {	12✔
472	auto sym = SymEngine::rcp_static_cast<const SymEngine::Symbol>(expr);	8✔
473	if (assumptions.find(sym) != assumptions.end()) {	8!
474	if (tight) {	8!
475	if (assumptions.at(sym).tight_upper_bound().is_null()) {	8!
476	return SymEngine::null;	1!
477	}
478	return maximum_new(assumptions.at(sym).tight_upper_bound(), parameters, assumptions, depth + 1, tight);	7!
479	}
480	symbolic::Expression new_ub = SymEngine::null;	×
481	for (auto& ub : assumptions.at(sym).upper_bounds()) {	×
482	auto new_max = maximum_new(ub, parameters, assumptions, depth + 1, tight);	×
483	if (new_max.is_null()) {	×
484	continue;	×
485	}
486	if (new_ub.is_null()) {	×
487	new_ub = new_max;	×
488	continue;	×
489	}
490	new_ub = symbolic::min(new_ub, new_max);	×
491	}	×
492	return new_ub;	×
493	}	×
494	return SymEngine::null;	×
495	}	8✔
496
497	// Mul
498	if (SymEngine::is_a<SymEngine::Mul>(*expr)) {	4!
499	auto mul = SymEngine::rcp_static_cast<const SymEngine::Mul>(expr);	×
500	const auto& args = mul->get_args();	×
501	size_t n = args.size();	×
502
503	std::vector<std::pair<Expression, Expression>> bounds;	×
504	bounds.reserve(n);	×
505
506	for (const auto& arg : args) {	×
507	Expression min_val = minimum_new(arg, parameters, assumptions, depth + 1, tight);	×
508	Expression max_val = maximum_new(arg, parameters, assumptions, depth + 1, tight);	×
509
510	if (min_val == SymEngine::null \|\| max_val == SymEngine::null) {	×
511	return SymEngine::null;	×
512	}
513	bounds.emplace_back(min_val, max_val);	×
514	}	×
515
516	// Iterate over 2^n combinations
517	Expression max_product = SymEngine::null;	×
518	const size_t total_combinations = 1ULL << n;	×
519
520	for (size_t mask = 0; mask < total_combinations; ++mask) {	×
521	Expression product = SymEngine::integer(1);	×
522	for (size_t i = 0; i < n; ++i) {	×
523	const auto& bound = bounds[i];	×
524	Expression val = (mask & (1ULL << i)) ? bound.second : bound.first;	×
525	product = symbolic::mul(product, val);	×
526	}	×
527	if (max_product == SymEngine::null) {	×
528	max_product = product;	×
529	} else {	×
530	max_product = symbolic::max(max_product, product);	×
531	}
532	}	×
533
534	return max_product;	×
535	}	×
536
537	// Add
538	if (SymEngine::is_a<SymEngine::Add>(*expr)) {	4!
539	auto add = SymEngine::rcp_static_cast<const SymEngine::Add>(expr);	4✔
540	const auto& args = add->get_args();	4!
541	Expression ubs = SymEngine::null;	4!
542	for (const auto& arg : args) {	12✔
543	auto ub = maximum_new(arg, parameters, assumptions, depth + 1, tight);	8!
544	if (ub == SymEngine::null) {	8!
545	return SymEngine::null;	×
546	}
547	if (ubs == SymEngine::null) {	8!
548	ubs = ub;	4!
549	} else {	4✔
550	ubs = symbolic::add(ubs, ub);	4!
551	}
552	}	8!
553	return ubs;	4✔
554	}	4✔
555
556	// Max
557	if (SymEngine::is_a<SymEngine::Max>(*expr)) {	×
558	auto args = SymEngine::rcp_dynamic_cast<const SymEngine::Max>(expr)->get_args();	×
559	Expression ubs = SymEngine::null;	×
560	for (const auto& arg : args) {	×
561	auto ub = maximum_new(arg, parameters, assumptions, depth + 1, tight);	×
562	if (ub == SymEngine::null) {	×
563	return SymEngine::null;	×
564	}
565	if (ubs == SymEngine::null) {	×
566	ubs = ub;	×
567	} else {	×
568	ubs = symbolic::max(ubs, ub);	×
569	}
570	}	×
571	return ubs;	×
572	}	×
573
574	// Min
575	if (SymEngine::is_a<SymEngine::Min>(*expr)) {	×
576	auto args = SymEngine::rcp_dynamic_cast<const SymEngine::Min>(expr)->get_args();	×
577	Expression ubs = SymEngine::null;	×
578	for (const auto& arg : args) {	×
579	auto ub = maximum_new(arg, parameters, assumptions, depth + 1, tight);	×
580	if (ub == SymEngine::null) {	×
581	return SymEngine::null;	×
582	}
583	if (ubs == SymEngine::null) {	×
584	ubs = ub;	×
585	} else {	×
586	ubs = symbolic::max(ubs, ub);	×
587	}
588	}	×
589	return ubs;	×
590	}	×
591
592	return SymEngine::null;	×
593	}	29✔
594
595	Expression minimum_new(const Expression expr, const SymbolSet& parameters, const Assumptions& assumptions, bool tight) {	14✔
596	return minimum_new(expr, parameters, assumptions, 0, tight);	14!
597	}	×
598
599	Expression maximum_new(const Expression expr, const SymbolSet& parameters, const Assumptions& assumptions, bool tight) {	14✔
600	return maximum_new(expr, parameters, assumptions, 0, tight);	14!
601	}	×
602
603	} // namespace symbolic
604	} // namespace sdfg

daisytuner / sdfglib / 20319772105

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