20141104835

Committed 11 Dec 2025 05:03PM UTC coverage: 40.351% (-0.03%) from 40.379%

Build # 20141104835

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #387 from daisytuner/cleanup

Minor improvements in symbolic analysis

Run Details

13653 of 43801 branches covered (31.17%)

Branch coverage included in aggregate %.

10 of 17 new or added lines in 4 files covered. (58.82%)

6 existing lines in 4 files now uncovered.

11688 of 19000 relevant lines covered (61.52%)

94.14 hits per line

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

40.81

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

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

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

daisytuner / sdfglib / 20141104835

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