20770413849

Committed 06 Jan 2026 10:50PM UTC coverage: 62.168% (+21.4%) from 40.764%

Build # 20770413849

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #433 from daisytuner/clang-coverage

updates clang coverage flags

Run Details

14988 of 24109 relevant lines covered (62.17%)

88.57 hits per line

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

83.97

/src/symbolic/polynomials.cpp

#include "sdfg/symbolic/polynomials.h"

#include <symengine/polys/basic_conversions.h>

namespace sdfg {
namespace symbolic {

Polynomial polynomial(const Expression expr, SymbolVec& symbols) {
    try {
        ExpressionSet gens;
        for (auto& symbol : symbols) {
            gens.insert(symbol);
        }
        return SymEngine::from_basic<SymEngine::MExprPoly>(expr, gens);
    } catch (SymEngine::SymEngineException& e) {
        return SymEngine::null;
    }
};

AffineCoeffs affine_coefficients(Polynomial poly, SymbolVec& symbols) {
    AffineCoeffs coeffs;
    for (auto& symbol : symbols) {
        coeffs[symbol] = symbolic::zero();
    }
    coeffs[symbolic::symbol("__daisy_constant__")] = symbolic::zero();

    auto& D = poly->get_poly().get_dict();
    for (auto& [exponents, coeff] : D) {
        // Check if sum of exponents is <= 1
        symbolic::Symbol symbol = symbolic::symbol("__daisy_constant__");
        unsigned total_deg = 0;
        for (size_t i = 0; i < exponents.size(); i++) {
            auto& e = exponents[i];
            if (e > 0) {
                symbol = symbols[i];
            }
            total_deg += e;
        }
        if (total_deg > 1) {
            return {};
        }

        // Add coefficient to corresponding symbol
        coeffs[symbol] = symbolic::add(coeffs[symbol], coeff);
    }

    return coeffs;
}

Expression affine_inverse(AffineCoeffs coeffs, Symbol symbol) {
    if (!coeffs.contains(symbol) || eq(coeffs[symbol], zero())) {
        return SymEngine::null;
    }

    Expression result = symbol;
    for (auto& [sym, expr] : coeffs) {
        if (eq(sym, symbol)) {
            continue;
        }
        result = symbolic::add(result, SymEngine::neg(expr));
    }

    return symbolic::div(result, coeffs[symbol]);
}

std::pair<std::vector<int>, Expression> get_leading_term(const Polynomial& poly) {
    if (poly->get_poly().dict_.empty()) {
        return {{}, symbolic::zero()};
    }

    auto it = poly->get_poly().dict_.begin();
    std::vector<int> max_exp = it->first;
    Expression max_coeff = it->second;

    for (++it; it != poly->get_poly().dict_.end(); ++it) {
        // Compare exponents lexicographically
        bool greater = false;
        for (size_t i = 0; i < max_exp.size(); ++i) {
            if (it->first[i] > max_exp[i]) {
                greater = true;
                break;
            } else if (it->first[i] < max_exp[i]) {
                break;
            }
        }
        if (greater) {
            max_exp = it->first;
            max_coeff = it->second;
        }
    }
    return {max_exp, max_coeff};
}

std::pair<Expression, Expression> polynomial_div(const Expression& offset, const Expression& stride) {
    if (symbolic::eq(offset, symbolic::zero())) {
        return {symbolic::zero(), symbolic::zero()};
    }

    // Collect symbols for polynomial conversion
    SymbolVec symbols;
    SymbolSet atom_set;
    for (auto& s : symbolic::atoms(offset)) atom_set.insert(s);
    for (auto& s : symbolic::atoms(stride)) atom_set.insert(s);
    for (auto& s : atom_set) symbols.push_back(s);

    auto poly_stride = polynomial(stride, symbols);
    if (poly_stride == SymEngine::null) {
        // Fallback to simple division if not a polynomial
        Expression div_expr = SymEngine::div(offset, stride);
        Expression expanded = symbolic::expand(div_expr);
        Expression quotient = symbolic::zero();
        auto process_term = [&](const Expression& term) {
            SymEngine::RCP<const SymEngine::Basic> num, den;
            SymEngine::as_numer_denom(term, SymEngine::outArg(num), SymEngine::outArg(den));
            if (symbolic::eq(den, symbolic::one())) {
                quotient = symbolic::add(quotient, term);
            }
        };
        if (SymEngine::is_a<SymEngine::Add>(*expanded)) {
            auto add = SymEngine::rcp_static_cast<const SymEngine::Add>(expanded);
            for (auto& term : add->get_args()) process_term(term);
        } else {
            process_term(expanded);
        }
        Expression remainder = symbolic::sub(offset, symbolic::mul(quotient, stride));
        remainder = symbolic::expand(remainder);
        return {quotient, remainder};
    }

    Expression quotient_expr = symbolic::zero();
    Expression remainder_expr = symbolic::zero();
    Expression dividend_expr = offset;

    int max_iter = 100;
    while (!symbolic::eq(dividend_expr, symbolic::zero()) && max_iter-- > 0) {
        auto poly_dividend = polynomial(dividend_expr, symbols);
        if (poly_dividend == SymEngine::null) break;

        auto [exp_div, coeff_div] = get_leading_term(poly_dividend);
        auto [exp_sor, coeff_sor] = get_leading_term(poly_stride);

        if (exp_div.empty() && symbolic::eq(coeff_div, symbolic::zero())) break;

        bool divisible = true;
        std::vector<int> exp_diff(exp_div.size());
        for (size_t i = 0; i < exp_div.size(); ++i) {
            if (exp_div[i] < exp_sor[i]) {
                divisible = false;
                break;
            }
            exp_diff[i] = exp_div[i] - exp_sor[i];
        }

        Expression term = symbolic::zero();
        if (divisible) {
            Expression coeff_q = symbolic::div(coeff_div, coeff_sor);
            if (symbolic::eq(coeff_q, symbolic::zero())) {
                divisible = false;
            } else {
                term = coeff_q;
                for (size_t i = 0; i < exp_diff.size(); ++i) {
                    if (exp_diff[i] > 0) {
                        term = symbolic::mul(term, symbolic::pow(symbols[i], symbolic::integer(exp_diff[i])));
                    }
                }
            }
        }

        if (divisible) {
            quotient_expr = symbolic::add(quotient_expr, term);
            dividend_expr = symbolic::sub(dividend_expr, symbolic::mul(term, stride));
            dividend_expr = symbolic::expand(dividend_expr);
        } else {
            // Move LT to remainder
            term = coeff_div;
            for (size_t i = 0; i < exp_div.size(); ++i) {
                if (exp_div[i] > 0) {
                    term = symbolic::mul(term, symbolic::pow(symbols[i], symbolic::integer(exp_div[i])));
                }
            }
            remainder_expr = symbolic::add(remainder_expr, term);
            dividend_expr = symbolic::sub(dividend_expr, term);
            dividend_expr = symbolic::expand(dividend_expr);
        }
    }
    remainder_expr = symbolic::add(remainder_expr, dividend_expr);
    remainder_expr = symbolic::expand(remainder_expr);

    return {quotient_expr, remainder_expr};
}

} // namespace symbolic
} // namespace sdfg

1	#include "sdfg/symbolic/polynomials.h"
2
3	#include <symengine/polys/basic_conversions.h>
4
5	namespace sdfg {
6	namespace symbolic {
7
8	Polynomial polynomial(const Expression expr, SymbolVec& symbols) {	879✔
9	try {	879✔
10	ExpressionSet gens;	879✔
11	for (auto& symbol : symbols) {	1,080✔
12	gens.insert(symbol);	1,080✔
13	}	1,080✔
14	return SymEngine::from_basic<SymEngine::MExprPoly>(expr, gens);	879✔
15	} catch (SymEngine::SymEngineException& e) {	879✔
16	return SymEngine::null;	×
17	}	×
18	};	879✔
19
20	AffineCoeffs affine_coefficients(Polynomial poly, SymbolVec& symbols) {	660✔
21	AffineCoeffs coeffs;	660✔
22	for (auto& symbol : symbols) {	713✔
23	coeffs[symbol] = symbolic::zero();	713✔
24	}	713✔
25	coeffs[symbolic::symbol("__daisy_constant__")] = symbolic::zero();	660✔
26
27	auto& D = poly->get_poly().get_dict();	660✔
28	for (auto& [exponents, coeff] : D) {	1,115✔
29	// Check if sum of exponents is <= 1
30	symbolic::Symbol symbol = symbolic::symbol("__daisy_constant__");	1,115✔
31	unsigned total_deg = 0;	1,115✔
32	for (size_t i = 0; i < exponents.size(); i++) {	2,472✔
33	auto& e = exponents[i];	1,357✔
34	if (e > 0) {	1,357✔
35	symbol = symbols[i];	702✔
36	}	702✔
37	total_deg += e;	1,357✔
38	}	1,357✔
39	if (total_deg > 1) {	1,115✔
40	return {};	3✔
41	}	3✔
42
43	// Add coefficient to corresponding symbol
44	coeffs[symbol] = symbolic::add(coeffs[symbol], coeff);	1,112✔
45	}	1,112✔
46
47	return coeffs;	657✔
48	}	660✔
49
50	Expression affine_inverse(AffineCoeffs coeffs, Symbol symbol) {	145✔
51	if (!coeffs.contains(symbol) \|\| eq(coeffs[symbol], zero())) {	145✔
52	return SymEngine::null;	1✔
53	}	1✔
54
55	Expression result = symbol;	144✔
56	for (auto& [sym, expr] : coeffs) {	288✔
57	if (eq(sym, symbol)) {	288✔
58	continue;	144✔
59	}	144✔
60	result = symbolic::add(result, SymEngine::neg(expr));	144✔
61	}	144✔
62
63	return symbolic::div(result, coeffs[symbol]);	144✔
64	}	145✔
65
66	std::pair<std::vector<int>, Expression> get_leading_term(const Polynomial& poly) {	294✔
67	if (poly->get_poly().dict_.empty()) {	294✔
68	return {{}, symbolic::zero()};	×
69	}	×
70
71	auto it = poly->get_poly().dict_.begin();	294✔
72	std::vector<int> max_exp = it->first;	294✔
73	Expression max_coeff = it->second;	294✔
74
75	for (++it; it != poly->get_poly().dict_.end(); ++it) {	981✔
76	// Compare exponents lexicographically
77	bool greater = false;	687✔
78	for (size_t i = 0; i < max_exp.size(); ++i) {	1,083✔
79	if (it->first[i] > max_exp[i]) {	1,083✔
80	greater = true;	82✔
81	break;	82✔
82	} else if (it->first[i] < max_exp[i]) {	1,001✔
83	break;	605✔
84	}	605✔
85	}	1,083✔
86	if (greater) {	687✔
87	max_exp = it->first;	82✔
88	max_coeff = it->second;	82✔
89	}	82✔
90	}	687✔
91	return {max_exp, max_coeff};	294✔
92	}	294✔
93
94	std::pair<Expression, Expression> polynomial_div(const Expression& offset, const Expression& stride) {	131✔
95	if (symbolic::eq(offset, symbolic::zero())) {	131✔
96	return {symbolic::zero(), symbolic::zero()};	59✔
97	}	59✔
98
99	// Collect symbols for polynomial conversion
100	SymbolVec symbols;	72✔
101	SymbolSet atom_set;	72✔
102	for (auto& s : symbolic::atoms(offset)) atom_set.insert(s);	72✔
103	for (auto& s : symbolic::atoms(stride)) atom_set.insert(s);	87✔
104	for (auto& s : atom_set) symbols.push_back(s);	89✔
105
106	auto poly_stride = polynomial(stride, symbols);	72✔
107	if (poly_stride == SymEngine::null) {	72✔
108	// Fallback to simple division if not a polynomial
109	Expression div_expr = SymEngine::div(offset, stride);	×
110	Expression expanded = symbolic::expand(div_expr);	×
111	Expression quotient = symbolic::zero();	×
112	auto process_term = [&](const Expression& term) {	×
113	SymEngine::RCP<const SymEngine::Basic> num, den;	×
114	SymEngine::as_numer_denom(term, SymEngine::outArg(num), SymEngine::outArg(den));	×
115	if (symbolic::eq(den, symbolic::one())) {	×
116	quotient = symbolic::add(quotient, term);	×
117	}	×
118	};	×
119	if (SymEngine::is_a<SymEngine::Add>(*expanded)) {	×
120	auto add = SymEngine::rcp_static_cast<const SymEngine::Add>(expanded);	×
121	for (auto& term : add->get_args()) process_term(term);	×
122	} else {	×
123	process_term(expanded);	×
124	}	×
125	Expression remainder = symbolic::sub(offset, symbolic::mul(quotient, stride));	×
126	remainder = symbolic::expand(remainder);	×
127	return {quotient, remainder};	×
128	}	×
129
130	Expression quotient_expr = symbolic::zero();	72✔
131	Expression remainder_expr = symbolic::zero();	72✔
132	Expression dividend_expr = offset;	72✔
133
134	int max_iter = 100;	72✔
135	while (!symbolic::eq(dividend_expr, symbolic::zero()) && max_iter-- > 0) {	219✔
136	auto poly_dividend = polynomial(dividend_expr, symbols);	147✔
137	if (poly_dividend == SymEngine::null) break;	147✔
138
139	auto [exp_div, coeff_div] = get_leading_term(poly_dividend);	147✔
140	auto [exp_sor, coeff_sor] = get_leading_term(poly_stride);	147✔
141
142	if (exp_div.empty() && symbolic::eq(coeff_div, symbolic::zero())) break;	147✔
143
144	bool divisible = true;	147✔
145	std::vector<int> exp_diff(exp_div.size());	147✔
146	for (size_t i = 0; i < exp_div.size(); ++i) {	196✔
147	if (exp_div[i] < exp_sor[i]) {	140✔
148	divisible = false;	91✔
149	break;	91✔
150	}	91✔
151	exp_diff[i] = exp_div[i] - exp_sor[i];	49✔
152	}	49✔
153
154	Expression term = symbolic::zero();	147✔
155	if (divisible) {	147✔
156	Expression coeff_q = symbolic::div(coeff_div, coeff_sor);	56✔
157	if (symbolic::eq(coeff_q, symbolic::zero())) {	56✔
158	divisible = false;	×
159	} else {	56✔
160	term = coeff_q;	56✔
161	for (size_t i = 0; i < exp_diff.size(); ++i) {	105✔
162	if (exp_diff[i] > 0) {	49✔
163	term = symbolic::mul(term, symbolic::pow(symbols[i], symbolic::integer(exp_diff[i])));	3✔
164	}	3✔
165	}	49✔
166	}	56✔
167	}	56✔
168
169	if (divisible) {	147✔
170	quotient_expr = symbolic::add(quotient_expr, term);	56✔
171	dividend_expr = symbolic::sub(dividend_expr, symbolic::mul(term, stride));	56✔
172	dividend_expr = symbolic::expand(dividend_expr);	56✔
173	} else {	91✔
174	// Move LT to remainder
175	term = coeff_div;	91✔
176	for (size_t i = 0; i < exp_div.size(); ++i) {	320✔
177	if (exp_div[i] > 0) {	229✔
178	term = symbolic::mul(term, symbolic::pow(symbols[i], symbolic::integer(exp_div[i])));	62✔
179	}	62✔
180	}	229✔
181	remainder_expr = symbolic::add(remainder_expr, term);	91✔
182	dividend_expr = symbolic::sub(dividend_expr, term);	91✔
183	dividend_expr = symbolic::expand(dividend_expr);	91✔
184	}	91✔
185	}	147✔
186	remainder_expr = symbolic::add(remainder_expr, dividend_expr);	72✔
187	remainder_expr = symbolic::expand(remainder_expr);	72✔
188
189	return {quotient_expr, remainder_expr};	72✔
190	}	72✔
191
192	} // namespace symbolic
193	} // namespace sdfg

daisytuner / sdfglib / 20770413849

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