19406662809

Committed 16 Nov 2025 01:54PM UTC coverage: 62.092% (-0.4%) from 62.447%

Build # 19406662809

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #347 from daisytuner/symbolic-range-analysis

extends symbol promotion with checks for effective range of scalars

Run Details

174 of 355 new or added lines in 10 files covered. (49.01%)

13 existing lines in 4 files now uncovered.

11048 of 17793 relevant lines covered (62.09%)

112.56 hits per line

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

58.5

/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 expr;
    }

    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;
    }

    // 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 expr;
    }

    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;
    }

    // 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;
        }
    }

    // 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;
        }
    }

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

daisytuner / sdfglib / 19406662809

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