15796425724

Committed 21 Jun 2025 02:00PM UTC coverage: 64.059% (-0.5%) from 64.591%

Build # 15796425724

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #95 from daisytuner/data-dependencies

Extends Data Dependency Analysis

Run Details

993 of 1197 new or added lines in 19 files covered. (82.96%)

55 existing lines in 5 files now uncovered.

8058 of 12579 relevant lines covered (64.06%)

150.28 hits per line

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

73.03

/src/symbolic/maps.cpp

#include "sdfg/symbolic/maps.h"

#include <isl/ctx.h>
#include <isl/set.h>
#include <isl/space.h>

#include "sdfg/symbolic/extreme_values.h"
#include "sdfg/symbolic/polynomials.h"
#include "sdfg/symbolic/utils.h"

namespace sdfg {
namespace symbolic {

bool is_monotonic_affine(const Expression& expr, const Symbol& sym, const Assumptions& assums) {
    SymbolVec symbols = {sym};
    auto poly = polynomial(expr, symbols);
    if (poly == SymEngine::null) {
        return false;
    }
    auto coeffs = affine_coefficients(poly, symbols);
    if (coeffs.empty()) {
        return false;
    }
    auto mul = minimum(coeffs[sym], {}, assums);
    if (mul == SymEngine::null) {
        return false;
    }
    auto offset = minimum(coeffs[symbol("__daisy_constant__")], {}, assums);
    if (offset == SymEngine::null) {
        return false;
    }
    if (!SymEngine::is_a<SymEngine::Integer>(*mul) ||
        !SymEngine::is_a<SymEngine::Integer>(*offset)) {
        return false;
    }
    auto mul_int = SymEngine::rcp_dynamic_cast<const SymEngine::Integer>(mul);
    auto offset_int = SymEngine::rcp_dynamic_cast<const SymEngine::Integer>(offset);
    if (mul_int->as_int() <= 0 || offset_int->as_int() <= 0) {
        return false;
    }

    return true;
}

bool is_monotonic_pow(const Expression& expr, const Symbol& sym, const Assumptions& assums) {
    if (SymEngine::is_a<SymEngine::Pow>(*expr)) {
        auto pow = SymEngine::rcp_dynamic_cast<const SymEngine::Pow>(expr);
        auto base = pow->get_base();
        auto exp = pow->get_exp();
        if (SymEngine::is_a<SymEngine::Integer>(*exp) &&
            SymEngine::is_a<SymEngine::Symbol>(*base)) {
            auto exp_int = SymEngine::rcp_dynamic_cast<const SymEngine::Integer>(exp);
            if (exp_int->as_int() <= 0) {
                return false;
            }
            auto base_sym = SymEngine::rcp_static_cast<const SymEngine::Symbol>(base);
            auto ub_sym = minimum(base_sym, {}, assums);
            if (ub_sym == SymEngine::null) {
                return false;
            }
            auto positive = symbolic::Ge(ub_sym, symbolic::integer(0));
            return symbolic::is_true(positive);
        }
    }

    return false;
}

bool is_monotonic(const Expression& expr, const Symbol& sym, const Assumptions& assums) {
    if (is_monotonic_affine(expr, sym, assums)) {
        return true;
    }
    return is_monotonic_pow(expr, sym, assums);
}

bool is_contiguous(const Expression& expr, const Symbol& sym, const Assumptions& assums) {
    SymbolVec symbols = {sym};
    auto poly = polynomial(expr, symbols);
    if (poly == SymEngine::null) {
        return false;
    }
    auto coeffs = affine_coefficients(poly, symbols);
    if (coeffs.empty()) {
        return false;
    }
    auto mul = minimum(coeffs[sym], {}, assums);
    if (mul == SymEngine::null) {
        return false;
    }
    auto offset = minimum(coeffs[symbol("__daisy_constant__")], {}, assums);
    if (offset == SymEngine::null) {
        return false;
    }
    if (!SymEngine::is_a<SymEngine::Integer>(*mul) ||
        !SymEngine::is_a<SymEngine::Integer>(*offset)) {
        return false;
    }
    auto mul_int = SymEngine::rcp_dynamic_cast<const SymEngine::Integer>(mul);
    auto offset_int = SymEngine::rcp_dynamic_cast<const SymEngine::Integer>(offset);
    if (mul_int->as_int() == 1 && offset_int->as_int() == 1) {
        return true;
    }

    return false;
}

bool is_disjoint_isl(const MultiExpression& expr1, const MultiExpression& expr2,
                     const Symbol& indvar, const Assumptions& assums1, const Assumptions& assums2) {
    if (expr1.size() != expr2.size()) {
        return false;
    }
    if (expr1.empty()) {
        return false;
    }

    isl_ctx* ctx = isl_ctx_alloc();

    // Transform both expressions into two maps with separate dimensions
    auto expr1_delinearized = delinearize(expr1, assums1);
    auto expr2_delinearized = delinearize(expr2, assums2);
    auto maps = expressions_to_intersection_map_str(expr1_delinearized, expr2_delinearized, indvar,
                                                    assums1, assums2);
    isl_map* map_1 = isl_map_read_from_str(ctx, std::get<0>(maps).c_str());
    isl_map* map_2 = isl_map_read_from_str(ctx, std::get<1>(maps).c_str());
    isl_map* map_3 = isl_map_read_from_str(ctx, std::get<2>(maps).c_str());
    if (!map_1 || !map_2 || !map_3) {
        if (map_1) {
            isl_map_free(map_1);
        }
        if (map_2) {
            isl_map_free(map_2);
        }
        if (map_3) {
            isl_map_free(map_3);
        }
        isl_ctx_free(ctx);
        return false;
    }

    // Find aliasing pairs under the constraint that dimensions are different

    isl_map* composed = isl_map_apply_domain(map_2, map_3);
    if (!composed) {
        isl_map_free(map_1);
        if (map_2) {
            isl_map_free(map_2);
        }
        if (map_3) {
            isl_map_free(map_3);
        }
        isl_ctx_free(ctx);
        return false;
    }
    isl_map* alias_pairs = isl_map_intersect(composed, map_1);
    if (!alias_pairs) {
        if (composed) {
            isl_map_free(composed);
        }
        if (map_1) {
            isl_map_free(map_1);
        }
        isl_ctx_free(ctx);
        return false;
    }

    bool disjoint = isl_map_is_empty(alias_pairs);
    isl_map_free(alias_pairs);
    isl_ctx_free(ctx);

    return disjoint;
}

bool is_disjoint_monotonic(const MultiExpression& expr1, const MultiExpression& expr2,
                           const Symbol& indvar, const Assumptions& assums1,
                           const Assumptions& assums2) {
    for (size_t i = 0; i < expr1.size(); i++) {
        auto& dim1 = expr1[i];
        if (expr2.size() <= i) {
            continue;
        }
        auto& dim2 = expr2[i];
        if (!symbolic::eq(dim1, dim2)) {
            continue;
        }

        // Collect all symbols
        symbolic::SymbolSet syms;
        for (auto& sym : symbolic::atoms(dim1)) {
            syms.insert(sym);
        }

        // Collect all non-constant symbols
        bool can_analyze = true;
        for (auto& sym : syms) {
            if (!is_parameter(sym, assums1)) {
                if (sym->get_name() != indvar->get_name()) {
                    can_analyze = false;
                    break;
                }
            }
        }
        if (!can_analyze) {
            continue;
        }

        // Check if both dimensions are monotonic in non-constant symbols
        if (symbolic::is_monotonic(dim1, indvar, assums1)) {
            return true;
        }
    }

    return false;
}

bool intersects(const MultiExpression& expr1, const MultiExpression& expr2, const Symbol& indvar,
                const Assumptions& assums1, const Assumptions& assums2) {
    if (is_disjoint_monotonic(expr1, expr2, indvar, assums1, assums2)) {
        return false;
    }
    return !is_disjoint_isl(expr1, expr2, indvar, assums1, assums2);
}

}  // namespace symbolic
}  // namespace sdfg

1	#include "sdfg/symbolic/maps.h"
2
3	#include <isl/ctx.h>
4	#include <isl/set.h>
5	#include <isl/space.h>
6
7	#include "sdfg/symbolic/extreme_values.h"
8	#include "sdfg/symbolic/polynomials.h"
9	#include "sdfg/symbolic/utils.h"
10
11	namespace sdfg {
12	namespace symbolic {
13
14	bool is_monotonic_affine(const Expression& expr, const Symbol& sym, const Assumptions& assums) {	261✔
15	SymbolVec symbols = {sym};	261✔
16	auto poly = polynomial(expr, symbols);	261✔
17	if (poly == SymEngine::null) {	261✔
NEW 18	return false;	×
19	}
20	auto coeffs = affine_coefficients(poly, symbols);	261✔
21	if (coeffs.empty()) {	261✔
22	return false;	1✔
23	}
24	auto mul = minimum(coeffs[sym], {}, assums);	260✔
25	if (mul == SymEngine::null) {	260✔
NEW 26	return false;	×
27	}
28	auto offset = minimum(coeffs[symbol("__daisy_constant__")], {}, assums);	260✔
29	if (offset == SymEngine::null) {	260✔
30	return false;	1✔
31	}
32	if (!SymEngine::is_a<SymEngine::Integer>(*mul) \|\|	518✔
33	!SymEngine::is_a<SymEngine::Integer>(*offset)) {	259✔
NEW 34	return false;	×
35	}
36	auto mul_int = SymEngine::rcp_dynamic_cast<const SymEngine::Integer>(mul);	259✔
37	auto offset_int = SymEngine::rcp_dynamic_cast<const SymEngine::Integer>(offset);	259✔
38	if (mul_int->as_int() <= 0 \|\| offset_int->as_int() <= 0) {	259✔
39	return false;	35✔
40	}
41
42	return true;	224✔
43	}	261✔
44
45	bool is_monotonic_pow(const Expression& expr, const Symbol& sym, const Assumptions& assums) {	37✔
46	if (SymEngine::is_a<SymEngine::Pow>(*expr)) {	37✔
47	auto pow = SymEngine::rcp_dynamic_cast<const SymEngine::Pow>(expr);	1✔
48	auto base = pow->get_base();	1✔
49	auto exp = pow->get_exp();	1✔
50	if (SymEngine::is_a<SymEngine::Integer>(*exp) &&	2✔
51	SymEngine::is_a<SymEngine::Symbol>(*base)) {	1✔
52	auto exp_int = SymEngine::rcp_dynamic_cast<const SymEngine::Integer>(exp);	1✔
53	if (exp_int->as_int() <= 0) {	1✔
NEW 54	return false;	×
55	}
56	auto base_sym = SymEngine::rcp_static_cast<const SymEngine::Symbol>(base);	1✔
57	auto ub_sym = minimum(base_sym, {}, assums);	1✔
58	if (ub_sym == SymEngine::null) {	1✔
NEW 59	return false;	×
60	}
61	auto positive = symbolic::Ge(ub_sym, symbolic::integer(0));	1✔
62	return symbolic::is_true(positive);	1✔
63	}	1✔
64	}	1✔
65
66	return false;	36✔
67	}	37✔
68
69	bool is_monotonic(const Expression& expr, const Symbol& sym, const Assumptions& assums) {	261✔
70	if (is_monotonic_affine(expr, sym, assums)) {	261✔
71	return true;	224✔
72	}
73	return is_monotonic_pow(expr, sym, assums);	37✔
74	}	261✔
75
76	bool is_contiguous(const Expression& expr, const Symbol& sym, const Assumptions& assums) {	35✔
77	SymbolVec symbols = {sym};	35✔
78	auto poly = polynomial(expr, symbols);	35✔
79	if (poly == SymEngine::null) {	35✔
NEW 80	return false;	×
81	}
82	auto coeffs = affine_coefficients(poly, symbols);	35✔
83	if (coeffs.empty()) {	35✔
NEW 84	return false;	×
85	}
86	auto mul = minimum(coeffs[sym], {}, assums);	35✔
87	if (mul == SymEngine::null) {	35✔
NEW 88	return false;	×
89	}
90	auto offset = minimum(coeffs[symbol("__daisy_constant__")], {}, assums);	35✔
91	if (offset == SymEngine::null) {	35✔
NEW 92	return false;	×
93	}
94	if (!SymEngine::is_a<SymEngine::Integer>(*mul) \|\|	70✔
95	!SymEngine::is_a<SymEngine::Integer>(*offset)) {	35✔
NEW 96	return false;	×
97	}
98	auto mul_int = SymEngine::rcp_dynamic_cast<const SymEngine::Integer>(mul);	35✔
99	auto offset_int = SymEngine::rcp_dynamic_cast<const SymEngine::Integer>(offset);	35✔
100	if (mul_int->as_int() == 1 && offset_int->as_int() == 1) {	35✔
101	return true;	33✔
102	}
103
104	return false;	2✔
105	}	35✔
106
107	bool is_disjoint_isl(const MultiExpression& expr1, const MultiExpression& expr2,	43✔
108	const Symbol& indvar, const Assumptions& assums1, const Assumptions& assums2) {
109	if (expr1.size() != expr2.size()) {	43✔
NEW 110	return false;	×
111	}
112	if (expr1.empty()) {	43✔
NEW 113	return false;	×
114	}
115
116	isl_ctx* ctx = isl_ctx_alloc();	43✔
117
118	// Transform both expressions into two maps with separate dimensions
119	auto expr1_delinearized = delinearize(expr1, assums1);	43✔
120	auto expr2_delinearized = delinearize(expr2, assums2);	43✔
121	auto maps = expressions_to_intersection_map_str(expr1_delinearized, expr2_delinearized, indvar,	86✔
122	assums1, assums2);	43✔
123	isl_map* map_1 = isl_map_read_from_str(ctx, std::get<0>(maps).c_str());	43✔
124	isl_map* map_2 = isl_map_read_from_str(ctx, std::get<1>(maps).c_str());	43✔
125	isl_map* map_3 = isl_map_read_from_str(ctx, std::get<2>(maps).c_str());	43✔
126	if (!map_1 \|\| !map_2 \|\| !map_3) {	43✔
NEW 127	if (map_1) {	×
NEW 128	isl_map_free(map_1);	×
NEW 129	}	×
NEW 130	if (map_2) {	×
NEW 131	isl_map_free(map_2);	×
NEW 132	}	×
NEW 133	if (map_3) {	×
NEW 134	isl_map_free(map_3);	×
NEW 135	}	×
NEW 136	isl_ctx_free(ctx);	×
NEW 137	return false;	×
138	}
139
140	// Find aliasing pairs under the constraint that dimensions are different
141
142	isl_map* composed = isl_map_apply_domain(map_2, map_3);	43✔
143	if (!composed) {	43✔
NEW 144	isl_map_free(map_1);	×
NEW 145	if (map_2) {	×
NEW 146	isl_map_free(map_2);	×
NEW 147	}	×
NEW 148	if (map_3) {	×
NEW 149	isl_map_free(map_3);	×
NEW 150	}	×
NEW 151	isl_ctx_free(ctx);	×
NEW 152	return false;	×
153	}
154	isl_map* alias_pairs = isl_map_intersect(composed, map_1);	43✔
155	if (!alias_pairs) {	43✔
NEW 156	if (composed) {	×
NEW 157	isl_map_free(composed);	×
NEW 158	}	×
NEW 159	if (map_1) {	×
NEW 160	isl_map_free(map_1);	×
NEW 161	}	×
NEW 162	isl_ctx_free(ctx);	×
NEW 163	return false;	×
164	}
165
166	bool disjoint = isl_map_is_empty(alias_pairs);	43✔
167	isl_map_free(alias_pairs);	43✔
168	isl_ctx_free(ctx);	43✔
169
170	return disjoint;	43✔
171	}	43✔
172
173	bool is_disjoint_monotonic(const MultiExpression& expr1, const MultiExpression& expr2,	44✔
174	const Symbol& indvar, const Assumptions& assums1,
175	const Assumptions& assums2) {
176	for (size_t i = 0; i < expr1.size(); i++) {	101✔
177	auto& dim1 = expr1[i];	58✔
178	if (expr2.size() <= i) {	58✔
NEW 179	continue;	×
180	}
181	auto& dim2 = expr2[i];	58✔
182	if (!symbolic::eq(dim1, dim2)) {	58✔
183	continue;	10✔
184	}
185
186	// Collect all symbols
187	symbolic::SymbolSet syms;	48✔
188	for (auto& sym : symbolic::atoms(dim1)) {	94✔
189	syms.insert(sym);	46✔
190	}
191
192	// Collect all non-constant symbols
193	bool can_analyze = true;	48✔
194	for (auto& sym : syms) {	81✔
195	if (!is_parameter(sym, assums1)) {	46✔
196	if (sym->get_name() != indvar->get_name()) {	46✔
197	can_analyze = false;	13✔
198	break;	13✔
199	}
200	}	33✔
201	}
202	if (!can_analyze) {	48✔
203	continue;	13✔
204	}
205
206	// Check if both dimensions are monotonic in non-constant symbols
207	if (symbolic::is_monotonic(dim1, indvar, assums1)) {	35✔
208	return true;	1✔
209	}
210	}	48✔
211
212	return false;	43✔
213	}	44✔
214
215	bool intersects(const MultiExpression& expr1, const MultiExpression& expr2, const Symbol& indvar,	44✔
216	const Assumptions& assums1, const Assumptions& assums2) {
217	if (is_disjoint_monotonic(expr1, expr2, indvar, assums1, assums2)) {	44✔
218	return false;	1✔
219	}
220	return !is_disjoint_isl(expr1, expr2, indvar, assums1, assums2);	43✔
221	}	44✔
222
223	} // namespace symbolic
224	} // namespace sdfg

daisytuner / sdfglib / 15796425724

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