15682370338

Committed 16 Jun 2025 01:36PM UTC coverage: 64.969% (+0.08%) from 64.887%

Build # 15682370338

Build Type

Pull #82

github

Committed by

web-flow

Commit Message

Merge 7ab4074df into 9816a9336

Pull Request Pull Request #82: parametrize extreme value analysis

Run Details

147 of 165 new or added lines in 8 files covered. (89.09%)

7 existing lines in 2 files now uncovered.

8062 of 12409 relevant lines covered (64.97%)

119.02 hits per line

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

87.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 assumptions.at(sym).lower_bound();
        }
        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();
        if (args.size() != 2) {
            // Extend to N-ary multiplication if needed
            return SymEngine::null;
        }

        Expression a = args[0];
        Expression b = args[1];

        Expression a_min = minimum(a, parameters, assumptions, depth + 1);
        Expression a_max = maximum(a, parameters, assumptions, depth + 1);
        Expression b_min = minimum(b, parameters, assumptions, depth + 1);
        Expression b_max = maximum(b, parameters, assumptions, depth + 1);

        if (a_min == SymEngine::null || a_max == SymEngine::null || b_min == SymEngine::null ||
            b_max == SymEngine::null) {
            return SymEngine::null;
        }

        // Compute all 4 combinations
        Expression p1 = symbolic::mul(a_min, b_min);
        Expression p2 = symbolic::mul(a_min, b_max);
        Expression p3 = symbolic::mul(a_max, b_min);
        Expression p4 = symbolic::mul(a_max, b_max);

        // Return minimum of all products
        return symbolic::min(symbolic::min(p1, p2), symbolic::min(p3, p4));
    }

    // 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 assumptions.at(sym).upper_bound();
        }
        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();
        if (args.size() != 2) {
            // Extend to N-ary multiplication if needed
            return SymEngine::null;
        }

        Expression a = args[0];
        Expression b = args[1];

        Expression a_min = minimum(a, parameters, assumptions, depth + 1);
        Expression a_max = maximum(a, parameters, assumptions, depth + 1);
        Expression b_min = minimum(b, parameters, assumptions, depth + 1);
        Expression b_max = maximum(b, parameters, assumptions, depth + 1);

        if (a_min == SymEngine::null || a_max == SymEngine::null || b_min == SymEngine::null ||
            b_max == SymEngine::null) {
            return SymEngine::null;
        }

        // Compute all 4 combinations
        Expression p1 = symbolic::mul(a_min, b_min);
        Expression p2 = symbolic::mul(a_min, b_max);
        Expression p3 = symbolic::mul(a_max, b_min);
        Expression p4 = symbolic::mul(a_max, b_max);

        // Return maximum of all products
        return symbolic::max(symbolic::max(p1, p2), symbolic::max(p3, p4));
    }

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

}  // 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,
10	const Assumptions& assumptions, const size_t depth);
11	Expression maximum(const Expression& expr, const SymbolSet& parameters,
12	const Assumptions& assumptions, const size_t depth);
13
14	Expression minimum(const Expression& expr, const SymbolSet& parameters,	978✔
15	const Assumptions& assumptions, const size_t depth) {
16	// Base Cases
17	if (depth > MAX_DEPTH) {	978✔
UNCOV 18	return expr;	×
19	}
20
21	if (SymEngine::is_a<SymEngine::NaN>(*expr)) {	978✔
NEW 22	return SymEngine::null;	×
23	}
24
25	if (SymEngine::is_a<SymEngine::Integer>(*expr)) {	978✔
26	return expr;	858✔
27	} else if (SymEngine::is_a<SymEngine::Infty>(*expr)) {	120✔
28	return expr;	×
29	}
30
31	// Symbol
32	if (SymEngine::is_a<SymEngine::Symbol>(*expr)) {	120✔
33	auto sym = SymEngine::rcp_static_cast<const SymEngine::Symbol>(expr);	112✔
34	if (parameters.find(sym) != parameters.end()) {	112✔
NEW 35	return sym;	×
36	}
37	if (assumptions.find(sym) != assumptions.end()) {	112✔
38	return assumptions.at(sym).lower_bound();	111✔
39	}
40	return SymEngine::null;	1✔
41	}	112✔
42
43	// Mul
44	if (SymEngine::is_a<SymEngine::Mul>(*expr)) {	8✔
45	auto mul = SymEngine::rcp_static_cast<const SymEngine::Mul>(expr);	2✔
46	const auto& args = mul->get_args();	2✔
47	if (args.size() != 2) {	2✔
48	// Extend to N-ary multiplication if needed
NEW 49	return SymEngine::null;	×
50	}
51
52	Expression a = args[0];	2✔
53	Expression b = args[1];	2✔
54
55	Expression a_min = minimum(a, parameters, assumptions, depth + 1);	2✔
56	Expression a_max = maximum(a, parameters, assumptions, depth + 1);	2✔
57	Expression b_min = minimum(b, parameters, assumptions, depth + 1);	2✔
58	Expression b_max = maximum(b, parameters, assumptions, depth + 1);	2✔
59
60	if (a_min == SymEngine::null \|\| a_max == SymEngine::null \|\| b_min == SymEngine::null \|\|	4✔
61	b_max == SymEngine::null) {	2✔
NEW 62	return SymEngine::null;	×
63	}
64
65	// Compute all 4 combinations
66	Expression p1 = symbolic::mul(a_min, b_min);	2✔
67	Expression p2 = symbolic::mul(a_min, b_max);	2✔
68	Expression p3 = symbolic::mul(a_max, b_min);	2✔
69	Expression p4 = symbolic::mul(a_max, b_max);	2✔
70
71	// Return minimum of all products
72	return symbolic::min(symbolic::min(p1, p2), symbolic::min(p3, p4));	2✔
73	}	2✔
74
75	// Add
76	if (SymEngine::is_a<SymEngine::Add>(*expr)) {	6✔
77	auto add = SymEngine::rcp_static_cast<const SymEngine::Add>(expr);	2✔
78	const auto& args = add->get_args();	2✔
79	Expression lbs = SymEngine::null;	2✔
80	for (const auto& arg : args) {	6✔
81	auto lb = minimum(arg, parameters, assumptions, depth + 1);	4✔
82	if (lb == SymEngine::null) {	4✔
83	return SymEngine::null;	×
84	}
85	if (lbs == SymEngine::null) {	4✔
86	lbs = lb;	2✔
87	} else {	2✔
88	lbs = symbolic::add(lbs, lb);	2✔
89	}
90	}	4✔
91	return lbs;	2✔
92	}	2✔
93
94	// Max
95	if (SymEngine::is_a<SymEngine::Max>(*expr)) {	4✔
96	auto args = SymEngine::rcp_dynamic_cast<const SymEngine::Max>(expr)->get_args();	2✔
97	Expression lbs = SymEngine::null;	2✔
98	for (const auto& arg : args) {	6✔
99	auto lb = minimum(arg, parameters, assumptions, depth + 1);	4✔
100	if (lb == SymEngine::null) {	4✔
101	return SymEngine::null;	×
102	}
103	if (lbs == SymEngine::null) {	4✔
104	lbs = lb;	2✔
105	} else {	2✔
106	lbs = symbolic::min(lbs, lb);	2✔
107	}
108	}	4✔
109	return lbs;	2✔
110	}	2✔
111
112	// Min
113	if (SymEngine::is_a<SymEngine::Min>(*expr)) {	2✔
114	auto args = SymEngine::rcp_dynamic_cast<const SymEngine::Min>(expr)->get_args();	2✔
115	Expression lbs = SymEngine::null;	2✔
116	for (const auto& arg : args) {	6✔
117	auto lb = minimum(arg, parameters, assumptions, depth + 1);	4✔
118	if (lb == SymEngine::null) {	4✔
NEW 119	return SymEngine::null;	×
120	}
121	if (lbs == SymEngine::null) {	4✔
122	lbs = lb;	2✔
123	} else {	2✔
124	lbs = symbolic::min(lbs, lb);	2✔
125	}
126	}	4✔
127	return lbs;	2✔
128	}	2✔
129
NEW 130	return SymEngine::null;	×
131	}	978✔
132
133	Expression maximum(const Expression& expr, const SymbolSet& parameters,	28✔
134	const Assumptions& assumptions, const size_t depth) {
135	if (depth > MAX_DEPTH) {	28✔
NEW 136	return expr;	×
137	}
138
139	if (SymEngine::is_a<SymEngine::NaN>(*expr)) {	28✔
UNCOV 140	return SymEngine::null;	×
141	}
142
143	// Base Cases
144	if (SymEngine::is_a<SymEngine::Integer>(*expr)) {	28✔
145	return expr;	6✔
146	} else if (SymEngine::is_a<SymEngine::Infty>(*expr)) {	22✔
NEW 147	return expr;	×
148	}
149
150	// Symbol
151	if (SymEngine::is_a<SymEngine::Symbol>(*expr)) {	22✔
152	auto sym = SymEngine::rcp_static_cast<const SymEngine::Symbol>(expr);	14✔
153	if (parameters.find(sym) != parameters.end()) {	14✔
NEW 154	return sym;	×
155	}
156	if (assumptions.find(sym) != assumptions.end()) {	14✔
157	return assumptions.at(sym).upper_bound();	14✔
158	}
UNCOV 159	return SymEngine::null;	×
160	}	14✔
161
162	// Mul
163	if (SymEngine::is_a<SymEngine::Mul>(*expr)) {	8✔
164	auto mul = SymEngine::rcp_static_cast<const SymEngine::Mul>(expr);	2✔
165	const auto& args = mul->get_args();	2✔
166	if (args.size() != 2) {	2✔
167	// Extend to N-ary multiplication if needed
UNCOV 168	return SymEngine::null;	×
169	}
170
171	Expression a = args[0];	2✔
172	Expression b = args[1];	2✔
173
174	Expression a_min = minimum(a, parameters, assumptions, depth + 1);	2✔
175	Expression a_max = maximum(a, parameters, assumptions, depth + 1);	2✔
176	Expression b_min = minimum(b, parameters, assumptions, depth + 1);	2✔
177	Expression b_max = maximum(b, parameters, assumptions, depth + 1);	2✔
178
179	if (a_min == SymEngine::null \|\| a_max == SymEngine::null \|\| b_min == SymEngine::null \|\|	4✔
180	b_max == SymEngine::null) {	2✔
UNCOV 181	return SymEngine::null;	×
182	}
183
184	// Compute all 4 combinations
185	Expression p1 = symbolic::mul(a_min, b_min);	2✔
186	Expression p2 = symbolic::mul(a_min, b_max);	2✔
187	Expression p3 = symbolic::mul(a_max, b_min);	2✔
188	Expression p4 = symbolic::mul(a_max, b_max);	2✔
189
190	// Return maximum of all products
191	return symbolic::max(symbolic::max(p1, p2), symbolic::max(p3, p4));	2✔
192	}	2✔
193
194	// Add
195	if (SymEngine::is_a<SymEngine::Add>(*expr)) {	6✔
196	auto add = SymEngine::rcp_static_cast<const SymEngine::Add>(expr);	2✔
197	const auto& args = add->get_args();	2✔
198	Expression ubs = SymEngine::null;	2✔
199	for (const auto& arg : args) {	6✔
200	auto ub = maximum(arg, parameters, assumptions, depth + 1);	4✔
201	if (ub == SymEngine::null) {	4✔
202	return SymEngine::null;	×
203	}
204	if (ubs == SymEngine::null) {	4✔
205	ubs = ub;	2✔
206	} else {	2✔
207	ubs = symbolic::add(ubs, ub);	2✔
208	}
209	}	4✔
210	return ubs;	2✔
211	}	2✔
212
213	// Max
214	if (SymEngine::is_a<SymEngine::Max>(*expr)) {	4✔
215	auto args = SymEngine::rcp_dynamic_cast<const SymEngine::Max>(expr)->get_args();	2✔
216	Expression ubs = SymEngine::null;	2✔
217	for (const auto& arg : args) {	6✔
218	auto ub = maximum(arg, parameters, assumptions, depth + 1);	4✔
219	if (ub == SymEngine::null) {	4✔
220	return SymEngine::null;	×
221	}
222	if (ubs == SymEngine::null) {	4✔
223	ubs = ub;	2✔
224	} else {	2✔
225	ubs = symbolic::max(ubs, ub);	2✔
226	}
227	}	4✔
228	return ubs;	2✔
229	}	2✔
230
231	// Min
232	if (SymEngine::is_a<SymEngine::Min>(*expr)) {	2✔
233	auto args = SymEngine::rcp_dynamic_cast<const SymEngine::Min>(expr)->get_args();	2✔
234	Expression ubs = SymEngine::null;	2✔
235	for (const auto& arg : args) {	6✔
236	auto ub = maximum(arg, parameters, assumptions, depth + 1);	4✔
237	if (ub == SymEngine::null) {	4✔
NEW 238	return SymEngine::null;	×
239	}
240	if (ubs == SymEngine::null) {	4✔
241	ubs = ub;	2✔
242	} else {	2✔
243	ubs = symbolic::max(ubs, ub);	2✔
244	}
245	}	4✔
246	return ubs;	2✔
247	}	2✔
248
NEW 249	return SymEngine::null;	×
250	}	28✔
251
252	Expression minimum(const Expression& expr, const SymbolSet& parameters,	958✔
253	const Assumptions& assumptions) {
254	return minimum(expr, parameters, assumptions, 0);	958✔
255	}
256
257	Expression maximum(const Expression& expr, const SymbolSet& parameters,	8✔
258	const Assumptions& assumptions) {
259	return maximum(expr, parameters, assumptions, 0);	8✔
260	}
261
262	} // namespace symbolic
263	} // namespace sdfg

daisytuner / sdfglib / 15682370338

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