15781182351

Committed 20 Jun 2025 02:27PM UTC coverage: 62.978% (-1.6%) from 64.591%

Build # 15781182351

Build Type

Pull #95

github

Committed by

web-flow

Commit Message

Merge 3b6e445ac into 37b47b09d

Pull Request Pull Request #95: Extends Data Dependency Analysis

Run Details

393 of 500 new or added lines in 10 files covered. (78.6%)

114 existing lines in 7 files now uncovered.

7752 of 12309 relevant lines covered (62.98%)

137.91 hits per line

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

80.9

/src/symbolic/sets.cpp

#include "sdfg/symbolic/sets.h"

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

#include <regex>

#include "sdfg/codegen/language_extensions/c_language_extension.h"
#include "sdfg/symbolic/extreme_values.h"
#include "sdfg/symbolic/polynomials.h"
#include "sdfg/symbolic/series.h"

namespace sdfg {
namespace symbolic {

MultiExpression delinearize(const MultiExpression& expr, const Assumptions& assums);

bool is_monotonic(const Symbol& sym, const Assumptions& assums);

bool is_parameter(const Symbol& sym, const Assumptions& assums);

std::string expression_to_map_str(const MultiExpression& expr, const Assumptions& assums);

ExpressionSet generate_constraints(SymbolSet& syms, const Assumptions& assums, SymbolSet& seen);

std::string constraint_to_isl_str(const Expression& con);

void canonicalize_map_dims(isl_map* map, const std::string& in_prefix,
                           const std::string& out_prefix) {
    int n_in = isl_map_dim(map, isl_dim_in);
    int n_out = isl_map_dim(map, isl_dim_out);

    for (int i = 0; i < n_in; ++i) {
        std::string name = in_prefix + std::to_string(i);
        map = isl_map_set_dim_name(map, isl_dim_in, i, name.c_str());
    }

    for (int i = 0; i < n_out; ++i) {
        std::string name = out_prefix + std::to_string(i);
        map = isl_map_set_dim_name(map, isl_dim_out, i, name.c_str());
    }
}

bool is_subset(const MultiExpression& expr1, const MultiExpression& expr2,
               const Assumptions& assums1, const Assumptions& assums2) {
    if (expr1.size() == 0 && expr2.size() == 0) {
        return true;
    }

    auto expr1_delinearized = delinearize(expr1, assums1);
    auto expr2_delinearized = delinearize(expr2, assums2);

    std::string map_1_str = expression_to_map_str(expr1_delinearized, assums1);
    std::string map_2_str = expression_to_map_str(expr2_delinearized, assums2);

    isl_ctx* ctx = isl_ctx_alloc();
    isl_map* map_1 = isl_map_read_from_str(ctx, map_1_str.c_str());
    isl_map* map_2 = isl_map_read_from_str(ctx, map_2_str.c_str());
    if (!map_1 || !map_2) {
        if (map_1) {
            isl_map_free(map_1);
        }
        if (map_2) {
            isl_map_free(map_2);
        }
        isl_ctx_free(ctx);
        return false;
    }
    isl_space* params_map1 = isl_space_params(isl_map_get_space(map_1));
    isl_space* params_map2 = isl_space_params(isl_map_get_space(map_2));

    // Align parameters carefully:
    isl_space* unified_params =
        isl_space_align_params(isl_space_copy(params_map1), isl_space_copy(params_map2));

    // Align maps to unified params:
    isl_map* aligned_map_1 = isl_map_align_params(map_1, isl_space_copy(unified_params));
    isl_map* aligned_map_2 = isl_map_align_params(map_2, isl_space_copy(unified_params));

    // Remove parameters explicitly (project them out)
    aligned_map_1 = isl_map_project_out(aligned_map_1, isl_dim_param, 0,
                                        isl_map_dim(aligned_map_1, isl_dim_param));
    aligned_map_2 = isl_map_project_out(aligned_map_2, isl_dim_param, 0,
                                        isl_map_dim(aligned_map_2, isl_dim_param));

    canonicalize_map_dims(aligned_map_1, "in_", "out_");
    canonicalize_map_dims(aligned_map_2, "in_", "out_");

    isl_set* set_1 = isl_map_range(aligned_map_1);
    isl_set* set_2 = isl_map_range(aligned_map_2);

    bool subset = isl_set_is_subset(set_1, set_2) == isl_bool_true;

    // Cleanup carefully:
    isl_map_free(aligned_map_1);
    isl_map_free(aligned_map_2);
    isl_space_free(unified_params);
    isl_space_free(params_map1);
    isl_space_free(params_map2);
    isl_ctx_free(ctx);

    return subset;
}

bool is_disjoint(const MultiExpression& expr1, const MultiExpression& expr2,
                 const Assumptions& assums1, const Assumptions& assums2) {
    auto expr1_delinearized = delinearize(expr1, assums1);
    auto expr2_delinearized = delinearize(expr2, assums2);

    std::string map_1_str = expression_to_map_str(expr1_delinearized, assums1);
    std::string map_2_str = expression_to_map_str(expr2_delinearized, assums2);

    isl_ctx* ctx = isl_ctx_alloc();
    isl_map* map_1 = isl_map_read_from_str(ctx, map_1_str.c_str());
    isl_map* map_2 = isl_map_read_from_str(ctx, map_2_str.c_str());
    if (!map_1 || !map_2) {
        if (map_1) isl_map_free(map_1);
        if (map_2) isl_map_free(map_2);
        isl_ctx_free(ctx);
        return false;
    }

    isl_space* params_map1 = isl_space_params(isl_map_get_space(map_1));
    isl_space* params_map2 = isl_space_params(isl_map_get_space(map_2));

    // Align parameters carefully:
    isl_space* unified_params =
        isl_space_align_params(isl_space_copy(params_map1), isl_space_copy(params_map2));

    // Align maps to unified params:
    isl_map* aligned_map_1 = isl_map_align_params(map_1, isl_space_copy(unified_params));
    isl_map* aligned_map_2 = isl_map_align_params(map_2, isl_space_copy(unified_params));

    // Remove parameters explicitly (project them out)
    aligned_map_1 = isl_map_project_out(aligned_map_1, isl_dim_param, 0,
                                        isl_map_dim(aligned_map_1, isl_dim_param));
    aligned_map_2 = isl_map_project_out(aligned_map_2, isl_dim_param, 0,
                                        isl_map_dim(aligned_map_2, isl_dim_param));

    canonicalize_map_dims(aligned_map_1, "in_", "out_");
    canonicalize_map_dims(aligned_map_2, "in_", "out_");

    isl_set* set_1 = isl_map_range(aligned_map_1);
    isl_set* set_2 = isl_map_range(aligned_map_2);

    bool disjoint = isl_set_is_disjoint(set_1, set_2) == isl_bool_true;

    // Cleanup carefully:
    isl_map_free(aligned_map_1);
    isl_map_free(aligned_map_2);
    isl_space_free(unified_params);
    isl_space_free(params_map1);
    isl_space_free(params_map2);
    isl_ctx_free(ctx);

    return disjoint;
}

MultiExpression delinearize(const MultiExpression& expr, const Assumptions& assums) {
    MultiExpression delinearized;
    for (auto& dim : expr) {
        // Step 1: Convert expression into an affine polynomial
        SymbolVec symbols;
        for (auto& sym : atoms(dim)) {
            if (!is_parameter(sym, assums)) {
                symbols.push_back(sym);
            }
        }
        if (symbols.empty()) {
            delinearized.push_back(dim);
            continue;
        }

        auto poly = polynomial(dim, symbols);
        if (poly == SymEngine::null) {
            delinearized.push_back(dim);
            continue;
        }

        auto aff_coeffs = affine_coefficients(poly, symbols);
        if (aff_coeffs.empty()) {
            delinearized.push_back(dim);
            continue;
        }

        // Step 2: Peel-off dimensions
        bool success = true;
        Expression remaining = dim;
        std::vector<Expression> peeled_dims;
        while (aff_coeffs.size() > 1) {
            // Find the symbol with largest stride (= largest atom count)
            Symbol new_dim = symbolic::symbol("");
            size_t max_atom_count = 0;
            for (const auto& [sym, coeff] : aff_coeffs) {
                if (sym->get_name() == "__daisy_constant__") {
                    continue;
                }
                size_t atom_count = symbolic::atoms(coeff).size();
                if (atom_count > max_atom_count || new_dim->get_name() == "") {
                    max_atom_count = atom_count;
                    new_dim = sym;
                }
            }
            if (new_dim->get_name() == "") {
                break;
            }

            // Symbol must be nonnegative
            auto sym_lb = minimum(new_dim, {}, assums);
            if (sym_lb == SymEngine::null) {
                success = false;
                break;
            }
            auto sym_cond = symbolic::Ge(sym_lb, symbolic::zero());
            if (!symbolic::is_true(sym_cond)) {
                success = false;
                break;
            }

            // Stride must be positive
            Expression stride = aff_coeffs.at(new_dim);
            auto stride_lb = minimum(stride, {}, assums);
            if (stride_lb == SymEngine::null) {
                success = false;
                break;
            }
            auto stride_cond = symbolic::Ge(stride_lb, symbolic::one());
            if (!symbolic::is_true(stride_cond)) {
                success = false;
                break;
            }

            // Peel off the dimension
            remaining = symbolic::sub(remaining, symbolic::mul(stride, new_dim));

            // Check if remainder is within bounds

            // remaining must be nonnegative
            auto rem_lb = minimum(remaining, {}, assums);
            if (rem_lb == SymEngine::null) {
                success = false;
                break;
            }
            auto cond_zero = symbolic::Ge(rem_lb, symbolic::zero());
            if (!symbolic::is_true(cond_zero)) {
                success = false;
                break;
            }

            // remaining must be less than stride
            auto rem = symbolic::sub(stride, remaining);
            rem = minimum(rem, {}, assums);
            if (rem == SymEngine::null) {
                success = false;
                break;
            }

            auto cond_stride = symbolic::Ge(rem, symbolic::one());
            if (!symbolic::is_true(cond_stride)) {
                success = false;
                break;
            }

            // Add the peeled dimension to the list
            peeled_dims.push_back(new_dim);
            aff_coeffs.erase(new_dim);
        }
        if (!success) {
            delinearized.push_back(dim);
            continue;
        }

        for (auto& peeled_dim : peeled_dims) {
            delinearized.push_back(peeled_dim);
        }

        // If remaining is not zero, then add the constant term
        if (!symbolic::eq(remaining, symbolic::zero()) && success) {
            delinearized.push_back(remaining);
        }
    }

    return delinearized;
}

bool is_parameter(const Symbol& sym, const Assumptions& assums) {
    if (assums.find(sym) == assums.end()) {
        return false;
    }
    auto& ass = assums.at(sym);
    if (ass.map() == SymEngine::null) {
        return false;
    }
    if (symbolic::eq(ass.map(), symbolic::zero())) {
        return true;
    }
    return false;
}

bool is_monotonic(const Symbol& sym, const Assumptions& assums) {
    if (assums.find(sym) == assums.end()) {
        return false;
    }
    auto& ass = assums.at(sym);
    if (ass.map() == SymEngine::null) {
        return false;
    }
    if (symbolic::eq(ass.map(), symbolic::add(sym, symbolic::one()))) {
        return true;
    }
    return false;
}

std::string expression_to_map_str(const MultiExpression& expr, const Assumptions& assums) {
    codegen::CLanguageExtension language_extension;

    // Get all symbols
    symbolic::SymbolSet syms;
    for (auto& expr : expr) {
        auto syms_expr = symbolic::atoms(expr);
        syms.insert(syms_expr.begin(), syms_expr.end());
    }

    // Distinguish between dimensions and parameters
    std::vector<std::string> dimensions;
    SymbolSet dimensions_syms;
    std::vector<std::string> parameters;
    SymbolSet parameters_syms;
    for (auto& sym : syms) {
        if (is_parameter(sym, assums)) {
            if (parameters_syms.find(sym) != parameters_syms.end()) {
                continue;
            }
            parameters.push_back(sym->get_name());
            parameters_syms.insert(sym);
        } else {
            if (dimensions_syms.find(sym) != dimensions_syms.end()) {
                continue;
            }
            dimensions.push_back(sym->get_name());
            dimensions_syms.insert(sym);
        }
    }

    // Generate constraints
    SymbolSet seen;
    auto constraints_syms = generate_constraints(syms, assums, seen);

    // Extend parameters with additional symbols from constraints
    for (auto& con : constraints_syms) {
        auto con_syms = symbolic::atoms(con);
        for (auto& con_sym : con_syms) {
            if (dimensions_syms.find(con_sym) == dimensions_syms.end()) {
                if (parameters_syms.find(con_sym) != parameters_syms.end()) {
                    continue;
                }
                parameters.push_back(con_sym->get_name());
                parameters_syms.insert(con_sym);
            }
        }
    }

    // Define map
    std::string map;
    if (!parameters.empty()) {
        std::sort(parameters.begin(), parameters.end());
        map += "[";
        map += helpers::join(parameters, ", ");
        map += "] -> ";
    }
    map += "{ [" + helpers::join(dimensions, ", ") + "] -> [";
    for (size_t i = 0; i < expr.size(); i++) {
        auto dim = expr[i];
        map += language_extension.expression(dim);
        if (i < expr.size() - 1) {
            map += ", ";
        }
    }
    map += "] ";

    std::vector<std::string> constraints;
    for (auto& con : constraints_syms) {
        auto con_str = constraint_to_isl_str(con);
        if (!con_str.empty()) {
            constraints.push_back(con_str);
        }
    }
    if (!constraints.empty()) {
        map += " : ";
        map += helpers::join(constraints, " and ");
    }

    map += " }";

    map = std::regex_replace(map, std::regex("\\."), "_");
    return map;
}

ExpressionSet generate_constraints(SymbolSet& syms, const Assumptions& assums, SymbolSet& seen) {
    ExpressionSet constraints;
    for (auto& sym : syms) {
        if (assums.find(sym) == assums.end()) {
            continue;
        }
        if (seen.find(sym) != seen.end()) {
            continue;
        }
        seen.insert(sym);

        auto ub = assums.at(sym).upper_bound();
        auto lb = assums.at(sym).lower_bound();
        if (!symbolic::eq(ub, symbolic::infty(1))) {
            if (SymEngine::is_a<SymEngine::Min>(*ub)) {
                auto min = SymEngine::rcp_static_cast<const SymEngine::Min>(ub);
                auto args = min->get_args();
                for (auto& arg : args) {
                    auto con = symbolic::Le(sym, arg);
                    auto con_syms = symbolic::atoms(con);
                    constraints.insert(con);

                    auto con_cons = generate_constraints(con_syms, assums, seen);
                    constraints.insert(con_cons.begin(), con_cons.end());
                }
            } else {
                auto con = symbolic::Le(sym, ub);
                auto con_syms = symbolic::atoms(con);
                constraints.insert(con);

                auto con_cons = generate_constraints(con_syms, assums, seen);
                constraints.insert(con_cons.begin(), con_cons.end());
            }
        }
        if (!symbolic::eq(lb, symbolic::infty(-1))) {
            if (SymEngine::is_a<SymEngine::Max>(*lb)) {
                auto max = SymEngine::rcp_static_cast<const SymEngine::Max>(lb);
                auto args = max->get_args();
                for (auto& arg : args) {
                    auto con = symbolic::Ge(sym, arg);
                    auto con_syms = symbolic::atoms(con);
                    constraints.insert(con);

                    auto con_cons = generate_constraints(con_syms, assums, seen);
                    constraints.insert(con_cons.begin(), con_cons.end());
                }
            } else {
                auto con = symbolic::Ge(sym, lb);
                auto con_syms = symbolic::atoms(con);
                constraints.insert(con);

                auto con_cons = generate_constraints(con_syms, assums, seen);
                constraints.insert(con_cons.begin(), con_cons.end());
            }
        }
    }
    return constraints;
}

std::string constraint_to_isl_str(const Expression& con) {
    codegen::CLanguageExtension language_extension;

    if (SymEngine::is_a<SymEngine::StrictLessThan>(*con)) {
        auto le = SymEngine::rcp_static_cast<const SymEngine::StrictLessThan>(con);
        auto lhs = le->get_arg1();
        auto rhs = le->get_arg2();
        return language_extension.expression(lhs) + " < " + language_extension.expression(rhs);
    } else if (SymEngine::is_a<SymEngine::LessThan>(*con)) {
        auto le = SymEngine::rcp_static_cast<const SymEngine::LessThan>(con);
        auto lhs = le->get_arg1();
        auto rhs = le->get_arg2();
        return language_extension.expression(lhs) + " <= " + language_extension.expression(rhs);
    } else if (SymEngine::is_a<SymEngine::Equality>(*con)) {
        auto eq = SymEngine::rcp_static_cast<const SymEngine::Equality>(con);
        auto lhs = eq->get_arg1();
        auto rhs = eq->get_arg2();
        return language_extension.expression(lhs) + " == " + language_extension.expression(rhs);
    } else if (SymEngine::is_a<SymEngine::Unequality>(*con)) {
        auto ne = SymEngine::rcp_static_cast<const SymEngine::Unequality>(con);
        auto lhs = ne->get_arg1();
        auto rhs = ne->get_arg2();
        return language_extension.expression(lhs) + " != " + language_extension.expression(rhs);
    }

    return "";
}

}  // namespace symbolic
}  // namespace sdfg

1	#include "sdfg/symbolic/sets.h"
2
3	#include <isl/ctx.h>
4	#include <isl/map.h>
5	#include <isl/set.h>
6	#include <isl/space.h>
7
8	#include <regex>
9
10	#include "sdfg/codegen/language_extensions/c_language_extension.h"
11	#include "sdfg/symbolic/extreme_values.h"
12	#include "sdfg/symbolic/polynomials.h"
13	#include "sdfg/symbolic/series.h"
14
15	namespace sdfg {
16	namespace symbolic {
17
18	MultiExpression delinearize(const MultiExpression& expr, const Assumptions& assums);
19
20	bool is_monotonic(const Symbol& sym, const Assumptions& assums);
21
22	bool is_parameter(const Symbol& sym, const Assumptions& assums);
23
24	std::string expression_to_map_str(const MultiExpression& expr, const Assumptions& assums);
25
26	ExpressionSet generate_constraints(SymbolSet& syms, const Assumptions& assums, SymbolSet& seen);
27
28	std::string constraint_to_isl_str(const Expression& con);
29
30	void canonicalize_map_dims(isl_map* map, const std::string& in_prefix,	50✔
31	const std::string& out_prefix) {
32	int n_in = isl_map_dim(map, isl_dim_in);	50✔
33	int n_out = isl_map_dim(map, isl_dim_out);	50✔
34
35	for (int i = 0; i < n_in; ++i) {	68✔
36	std::string name = in_prefix + std::to_string(i);	18✔
37	map = isl_map_set_dim_name(map, isl_dim_in, i, name.c_str());	18✔
38	}	18✔
39
40	for (int i = 0; i < n_out; ++i) {	94✔
41	std::string name = out_prefix + std::to_string(i);	44✔
42	map = isl_map_set_dim_name(map, isl_dim_out, i, name.c_str());	44✔
43	}	44✔
44	}	50✔
45
46	bool is_subset(const MultiExpression& expr1, const MultiExpression& expr2,	21✔
47	const Assumptions& assums1, const Assumptions& assums2) {
48	if (expr1.size() == 0 && expr2.size() == 0) {	21✔
49	return true;	3✔
50	}
51
52	auto expr1_delinearized = delinearize(expr1, assums1);	18✔
53	auto expr2_delinearized = delinearize(expr2, assums2);	18✔
54
55	std::string map_1_str = expression_to_map_str(expr1_delinearized, assums1);	18✔
56	std::string map_2_str = expression_to_map_str(expr2_delinearized, assums2);	18✔
57
58	isl_ctx* ctx = isl_ctx_alloc();	18✔
59	isl_map* map_1 = isl_map_read_from_str(ctx, map_1_str.c_str());	18✔
60	isl_map* map_2 = isl_map_read_from_str(ctx, map_2_str.c_str());	18✔
61	if (!map_1 \|\| !map_2) {	18✔
62	if (map_1) {	×
63	isl_map_free(map_1);	×
64	}	×
65	if (map_2) {	×
66	isl_map_free(map_2);	×
67	}	×
68	isl_ctx_free(ctx);	×
69	return false;	×
70	}
71	isl_space* params_map1 = isl_space_params(isl_map_get_space(map_1));	18✔
72	isl_space* params_map2 = isl_space_params(isl_map_get_space(map_2));	18✔
73
74	// Align parameters carefully:
75	isl_space* unified_params =	18✔
76	isl_space_align_params(isl_space_copy(params_map1), isl_space_copy(params_map2));	18✔
77
78	// Align maps to unified params:
79	isl_map* aligned_map_1 = isl_map_align_params(map_1, isl_space_copy(unified_params));	18✔
80	isl_map* aligned_map_2 = isl_map_align_params(map_2, isl_space_copy(unified_params));	18✔
81
82	// Remove parameters explicitly (project them out)
83	aligned_map_1 = isl_map_project_out(aligned_map_1, isl_dim_param, 0,	18✔
84	isl_map_dim(aligned_map_1, isl_dim_param));	18✔
85	aligned_map_2 = isl_map_project_out(aligned_map_2, isl_dim_param, 0,	18✔
86	isl_map_dim(aligned_map_2, isl_dim_param));	18✔
87
88	canonicalize_map_dims(aligned_map_1, "in_", "out_");	18✔
89	canonicalize_map_dims(aligned_map_2, "in_", "out_");	18✔
90
91	isl_set* set_1 = isl_map_range(aligned_map_1);	18✔
92	isl_set* set_2 = isl_map_range(aligned_map_2);	18✔
93
94	bool subset = isl_set_is_subset(set_1, set_2) == isl_bool_true;	18✔
95
96	// Cleanup carefully:
97	isl_map_free(aligned_map_1);	18✔
98	isl_map_free(aligned_map_2);	18✔
99	isl_space_free(unified_params);	18✔
100	isl_space_free(params_map1);	18✔
101	isl_space_free(params_map2);	18✔
102	isl_ctx_free(ctx);	18✔
103
104	return subset;	18✔
105	}	21✔
106
107	bool is_disjoint(const MultiExpression& expr1, const MultiExpression& expr2,	7✔
108	const Assumptions& assums1, const Assumptions& assums2) {
109	auto expr1_delinearized = delinearize(expr1, assums1);	7✔
110	auto expr2_delinearized = delinearize(expr2, assums2);	7✔
111
112	std::string map_1_str = expression_to_map_str(expr1_delinearized, assums1);	7✔
113	std::string map_2_str = expression_to_map_str(expr2_delinearized, assums2);	7✔
114
115	isl_ctx* ctx = isl_ctx_alloc();	7✔
116	isl_map* map_1 = isl_map_read_from_str(ctx, map_1_str.c_str());	7✔
117	isl_map* map_2 = isl_map_read_from_str(ctx, map_2_str.c_str());	7✔
118	if (!map_1 \|\| !map_2) {	7✔
NEW 119	if (map_1) isl_map_free(map_1);	×
NEW 120	if (map_2) isl_map_free(map_2);	×
121	isl_ctx_free(ctx);	×
122	return false;	×
123	}
124
125	isl_space* params_map1 = isl_space_params(isl_map_get_space(map_1));	7✔
126	isl_space* params_map2 = isl_space_params(isl_map_get_space(map_2));	7✔
127
128	// Align parameters carefully:
129	isl_space* unified_params =	7✔
130	isl_space_align_params(isl_space_copy(params_map1), isl_space_copy(params_map2));	7✔
131
132	// Align maps to unified params:
133	isl_map* aligned_map_1 = isl_map_align_params(map_1, isl_space_copy(unified_params));	7✔
134	isl_map* aligned_map_2 = isl_map_align_params(map_2, isl_space_copy(unified_params));	7✔
135
136	// Remove parameters explicitly (project them out)
137	aligned_map_1 = isl_map_project_out(aligned_map_1, isl_dim_param, 0,	7✔
138	isl_map_dim(aligned_map_1, isl_dim_param));	7✔
139	aligned_map_2 = isl_map_project_out(aligned_map_2, isl_dim_param, 0,	7✔
140	isl_map_dim(aligned_map_2, isl_dim_param));	7✔
141
142	canonicalize_map_dims(aligned_map_1, "in_", "out_");	7✔
143	canonicalize_map_dims(aligned_map_2, "in_", "out_");	7✔
144
145	isl_set* set_1 = isl_map_range(aligned_map_1);	7✔
146	isl_set* set_2 = isl_map_range(aligned_map_2);	7✔
147
148	bool disjoint = isl_set_is_disjoint(set_1, set_2) == isl_bool_true;	7✔
149
150	// Cleanup carefully:
151	isl_map_free(aligned_map_1);	7✔
152	isl_map_free(aligned_map_2);	7✔
153	isl_space_free(unified_params);	7✔
154	isl_space_free(params_map1);	7✔
155	isl_space_free(params_map2);	7✔
156	isl_ctx_free(ctx);	7✔
157
158	return disjoint;	7✔
159	}	7✔
160
161	MultiExpression delinearize(const MultiExpression& expr, const Assumptions& assums) {	50✔
162	MultiExpression delinearized;	50✔
163	for (auto& dim : expr) {	94✔
164	// Step 1: Convert expression into an affine polynomial
165	SymbolVec symbols;	44✔
166	for (auto& sym : atoms(dim)) {	62✔
167	if (!is_parameter(sym, assums)) {	18✔
168	symbols.push_back(sym);	18✔
169	}	18✔
170	}
171	if (symbols.empty()) {	44✔
172	delinearized.push_back(dim);	26✔
173	continue;	26✔
174	}
175
176	auto poly = polynomial(dim, symbols);	18✔
177	if (poly == SymEngine::null) {	18✔
178	delinearized.push_back(dim);	×
179	continue;	×
180	}
181
182	auto aff_coeffs = affine_coefficients(poly, symbols);	18✔
183	if (aff_coeffs.empty()) {	18✔
184	delinearized.push_back(dim);	×
185	continue;	×
186	}
187
188	// Step 2: Peel-off dimensions
189	bool success = true;	18✔
190	Expression remaining = dim;	18✔
191	std::vector<Expression> peeled_dims;	18✔
192	while (aff_coeffs.size() > 1) {	22✔
193	// Find the symbol with largest stride (= largest atom count)
194	Symbol new_dim = symbolic::symbol("");	18✔
195	size_t max_atom_count = 0;	18✔
196	for (const auto& [sym, coeff] : aff_coeffs) {	90✔
197	if (sym->get_name() == "__daisy_constant__") {	36✔
198	continue;	18✔
199	}
200	size_t atom_count = symbolic::atoms(coeff).size();	18✔
201	if (atom_count > max_atom_count \|\| new_dim->get_name() == "") {	18✔
202	max_atom_count = atom_count;	18✔
203	new_dim = sym;	18✔
204	}	18✔
205	}
206	if (new_dim->get_name() == "") {	18✔
207	break;	×
208	}
209
210	// Symbol must be nonnegative
211	auto sym_lb = minimum(new_dim, {}, assums);	18✔
212	if (sym_lb == SymEngine::null) {	18✔
UNCOV 213	success = false;	×
UNCOV 214	break;	×
215	}
216	auto sym_cond = symbolic::Ge(sym_lb, symbolic::zero());	18✔
217	if (!symbolic::is_true(sym_cond)) {	18✔
218	success = false;	6✔
219	break;	6✔
220	}
221
222	// Stride must be positive
223	Expression stride = aff_coeffs.at(new_dim);	12✔
224	auto stride_lb = minimum(stride, {}, assums);	12✔
225	if (stride_lb == SymEngine::null) {	12✔
226	success = false;	×
227	break;	×
228	}
229	auto stride_cond = symbolic::Ge(stride_lb, symbolic::one());	12✔
230	if (!symbolic::is_true(stride_cond)) {	12✔
231	success = false;	×
232	break;	×
233	}
234
235	// Peel off the dimension
236	remaining = symbolic::sub(remaining, symbolic::mul(stride, new_dim));	12✔
237
238	// Check if remainder is within bounds
239
240	// remaining must be nonnegative
241	auto rem_lb = minimum(remaining, {}, assums);	12✔
242	if (rem_lb == SymEngine::null) {	12✔
243	success = false;	×
244	break;	×
245	}
246	auto cond_zero = symbolic::Ge(rem_lb, symbolic::zero());	12✔
247	if (!symbolic::is_true(cond_zero)) {	12✔
UNCOV 248	success = false;	×
UNCOV 249	break;	×
250	}
251
252	// remaining must be less than stride
253	auto rem = symbolic::sub(stride, remaining);	12✔
254	rem = minimum(rem, {}, assums);	12✔
255	if (rem == SymEngine::null) {	12✔
256	success = false;	×
257	break;	×
258	}
259
260	auto cond_stride = symbolic::Ge(rem, symbolic::one());	12✔
261	if (!symbolic::is_true(cond_stride)) {	12✔
262	success = false;	8✔
263	break;	8✔
264	}
265
266	// Add the peeled dimension to the list
267	peeled_dims.push_back(new_dim);	4✔
268	aff_coeffs.erase(new_dim);	4✔
269	}	18✔
270	if (!success) {	18✔
271	delinearized.push_back(dim);	14✔
272	continue;	14✔
273	}
274
275	for (auto& peeled_dim : peeled_dims) {	8✔
276	delinearized.push_back(peeled_dim);	4✔
277	}
278
279	// If remaining is not zero, then add the constant term
280	if (!symbolic::eq(remaining, symbolic::zero()) && success) {	4✔
281	delinearized.push_back(remaining);	×
282	}	×
283	}	44✔
284
285	return delinearized;	50✔
286	}	50✔
287
288	bool is_parameter(const Symbol& sym, const Assumptions& assums) {	36✔
289	if (assums.find(sym) == assums.end()) {	36✔
NEW 290	return false;	×
291	}
292	auto& ass = assums.at(sym);	36✔
293	if (ass.map() == SymEngine::null) {	36✔
294	return false;	28✔
295	}
296	if (symbolic::eq(ass.map(), symbolic::zero())) {	8✔
NEW 297	return true;	×
298	}
299	return false;	8✔
300	}	36✔
301
NEW 302	bool is_monotonic(const Symbol& sym, const Assumptions& assums) {	×
NEW 303	if (assums.find(sym) == assums.end()) {	×
NEW 304	return false;	×
305	}
NEW 306	auto& ass = assums.at(sym);	×
NEW 307	if (ass.map() == SymEngine::null) {	×
NEW 308	return false;	×
309	}
NEW 310	if (symbolic::eq(ass.map(), symbolic::add(sym, symbolic::one()))) {	×
NEW 311	return true;	×
312	}
NEW 313	return false;	×
NEW 314	}	×
315
316	std::string expression_to_map_str(const MultiExpression& expr, const Assumptions& assums) {	50✔
317	codegen::CLanguageExtension language_extension;	50✔
318
319	// Get all symbols
320	symbolic::SymbolSet syms;	50✔
321	for (auto& expr : expr) {	94✔
322	auto syms_expr = symbolic::atoms(expr);	44✔
323	syms.insert(syms_expr.begin(), syms_expr.end());	44✔
324	}	44✔
325
326	// Distinguish between dimensions and parameters
327	std::vector<std::string> dimensions;	50✔
328	SymbolSet dimensions_syms;	50✔
329	std::vector<std::string> parameters;	50✔
330	SymbolSet parameters_syms;	50✔
331	for (auto& sym : syms) {	68✔
332	if (is_parameter(sym, assums)) {	18✔
NEW 333	if (parameters_syms.find(sym) != parameters_syms.end()) {	×
NEW 334	continue;	×
335	}
NEW 336	parameters.push_back(sym->get_name());	×
NEW 337	parameters_syms.insert(sym);	×
NEW 338	} else {	×
339	if (dimensions_syms.find(sym) != dimensions_syms.end()) {	18✔
NEW 340	continue;	×
341	}
342	dimensions.push_back(sym->get_name());	18✔
343	dimensions_syms.insert(sym);	18✔
344	}
345	}
346
347	// Generate constraints
348	SymbolSet seen;	50✔
349	auto constraints_syms = generate_constraints(syms, assums, seen);	50✔
350
351	// Extend parameters with additional symbols from constraints
352	for (auto& con : constraints_syms) {	96✔
353	auto con_syms = symbolic::atoms(con);	46✔
354	for (auto& con_sym : con_syms) {	110✔
355	if (dimensions_syms.find(con_sym) == dimensions_syms.end()) {	64✔
356	if (parameters_syms.find(con_sym) != parameters_syms.end()) {	24✔
357	continue;	12✔
358	}
359	parameters.push_back(con_sym->get_name());	12✔
360	parameters_syms.insert(con_sym);	12✔
361	}	12✔
362	}
363	}	46✔
364
365	// Define map
366	std::string map;	50✔
367	if (!parameters.empty()) {	50✔
368	std::sort(parameters.begin(), parameters.end());	6✔
369	map += "[";	6✔
370	map += helpers::join(parameters, ", ");	6✔
371	map += "] -> ";	6✔
372	}	6✔
373	map += "{ [" + helpers::join(dimensions, ", ") + "] -> [";	50✔
374	for (size_t i = 0; i < expr.size(); i++) {	94✔
375	auto dim = expr[i];	44✔
376	map += language_extension.expression(dim);	44✔
377	if (i < expr.size() - 1) {	44✔
NEW 378	map += ", ";	×
NEW 379	}	×
380	}	44✔
381	map += "] ";	50✔
382
383	std::vector<std::string> constraints;	50✔
384	for (auto& con : constraints_syms) {	96✔
385	auto con_str = constraint_to_isl_str(con);	46✔
386	if (!con_str.empty()) {	46✔
387	constraints.push_back(con_str);	44✔
388	}	44✔
389	}	46✔
390	if (!constraints.empty()) {	50✔
391	map += " : ";	18✔
392	map += helpers::join(constraints, " and ");	18✔
393	}	18✔
394
395	map += " }";	50✔
396
397	map = std::regex_replace(map, std::regex("\\."), "_");	50✔
398	return map;	50✔
399	}	50✔
400
401	ExpressionSet generate_constraints(SymbolSet& syms, const Assumptions& assums, SymbolSet& seen) {	102✔
402	ExpressionSet constraints;	102✔
403	for (auto& sym : syms) {	192✔
404	if (assums.find(sym) == assums.end()) {	90✔
405	continue;	8✔
406	}
407	if (seen.find(sym) != seen.end()) {	82✔
408	continue;	58✔
409	}
410	seen.insert(sym);	24✔
411
412	auto ub = assums.at(sym).upper_bound();	24✔
413	auto lb = assums.at(sym).lower_bound();	24✔
414	if (!symbolic::eq(ub, symbolic::infty(1))) {	24✔
415	if (SymEngine::is_a<SymEngine::Min>(*ub)) {	24✔
416	auto min = SymEngine::rcp_static_cast<const SymEngine::Min>(ub);	2✔
417	auto args = min->get_args();	2✔
418	for (auto& arg : args) {	6✔
419	auto con = symbolic::Le(sym, arg);	4✔
420	auto con_syms = symbolic::atoms(con);	4✔
421	constraints.insert(con);	4✔
422
423	auto con_cons = generate_constraints(con_syms, assums, seen);	4✔
424	constraints.insert(con_cons.begin(), con_cons.end());	4✔
425	}	4✔
426	} else {	2✔
427	auto con = symbolic::Le(sym, ub);	22✔
428	auto con_syms = symbolic::atoms(con);	22✔
429	constraints.insert(con);	22✔
430
431	auto con_cons = generate_constraints(con_syms, assums, seen);	22✔
432	constraints.insert(con_cons.begin(), con_cons.end());	22✔
433	}	22✔
434	}	24✔
435	if (!symbolic::eq(lb, symbolic::infty(-1))) {	24✔
436	if (SymEngine::is_a<SymEngine::Max>(*lb)) {	24✔
437	auto max = SymEngine::rcp_static_cast<const SymEngine::Max>(lb);	2✔
438	auto args = max->get_args();	2✔
439	for (auto& arg : args) {	6✔
440	auto con = symbolic::Ge(sym, arg);	4✔
441	auto con_syms = symbolic::atoms(con);	4✔
442	constraints.insert(con);	4✔
443
444	auto con_cons = generate_constraints(con_syms, assums, seen);	4✔
445	constraints.insert(con_cons.begin(), con_cons.end());	4✔
446	}	4✔
447	} else {	2✔
448	auto con = symbolic::Ge(sym, lb);	22✔
449	auto con_syms = symbolic::atoms(con);	22✔
450	constraints.insert(con);	22✔
451
452	auto con_cons = generate_constraints(con_syms, assums, seen);	22✔
453	constraints.insert(con_cons.begin(), con_cons.end());	22✔
454	}	22✔
455	}	24✔
456	}	24✔
457	return constraints;	102✔
458	}	102✔
459
460	std::string constraint_to_isl_str(const Expression& con) {	46✔
461	codegen::CLanguageExtension language_extension;	46✔
462
463	if (SymEngine::is_a<SymEngine::StrictLessThan>(*con)) {	46✔
NEW 464	auto le = SymEngine::rcp_static_cast<const SymEngine::StrictLessThan>(con);	×
NEW 465	auto lhs = le->get_arg1();	×
NEW 466	auto rhs = le->get_arg2();	×
NEW 467	return language_extension.expression(lhs) + " < " + language_extension.expression(rhs);	×
468	} else if (SymEngine::is_a<SymEngine::LessThan>(*con)) {	46✔
469	auto le = SymEngine::rcp_static_cast<const SymEngine::LessThan>(con);	44✔
470	auto lhs = le->get_arg1();	44✔
471	auto rhs = le->get_arg2();	44✔
472	return language_extension.expression(lhs) + " <= " + language_extension.expression(rhs);	44✔
473	} else if (SymEngine::is_a<SymEngine::Equality>(*con)) {	46✔
NEW 474	auto eq = SymEngine::rcp_static_cast<const SymEngine::Equality>(con);	×
NEW 475	auto lhs = eq->get_arg1();	×
NEW 476	auto rhs = eq->get_arg2();	×
NEW 477	return language_extension.expression(lhs) + " == " + language_extension.expression(rhs);	×
478	} else if (SymEngine::is_a<SymEngine::Unequality>(*con)) {	2✔
NEW 479	auto ne = SymEngine::rcp_static_cast<const SymEngine::Unequality>(con);	×
NEW 480	auto lhs = ne->get_arg1();	×
NEW 481	auto rhs = ne->get_arg2();	×
NEW 482	return language_extension.expression(lhs) + " != " + language_extension.expression(rhs);	×
NEW 483	}	×
484
485	return "";	2✔
486	}	46✔
487
488	} // namespace symbolic
489	} // namespace sdfg

daisytuner / sdfglib / 15781182351

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