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

89.1

/src/symbolic/utils.cpp

#include "sdfg/symbolic/utils.h"

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

#include <regex>

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

namespace sdfg {
namespace symbolic {

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

std::tuple<std::string, std::string, std::string> expressions_to_intersection_map_str(
    const MultiExpression& expr1, const MultiExpression& expr2, const Symbol& indvar,
    const Assumptions& assums1, const Assumptions& assums2) {
    codegen::CLanguageExtension language_extension;

    // Get all symbols
    symbolic::SymbolSet syms;
    for (auto& expr : expr1) {
        auto syms_expr = symbolic::atoms(expr);
        syms.insert(syms_expr.begin(), syms_expr.end());
    }
    for (auto& expr : expr2) {
        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 (sym->get_name() != indvar->get_name() && is_parameter(sym, assums1)) {
            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, assums1, 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 two maps
    std::string map_1;
    std::string map_2;
    if (!parameters.empty()) {
        map_1 += "[";
        map_1 += helpers::join(parameters, ", ");
        map_1 += "] -> ";
        map_2 += "[";
        map_2 += helpers::join(parameters, ", ");
        map_2 += "] -> ";
    }
    map_1 += "{ [";
    map_2 += "{ [";
    for (size_t i = 0; i < dimensions.size(); i++) {
        map_1 += dimensions[i] + "_1";
        map_2 += dimensions[i] + "_2";
        if (i < dimensions.size() - 1) {
            map_1 += ", ";
            map_2 += ", ";
        }
    }
    map_1 += "] -> [";
    map_2 += "] -> [";
    for (size_t i = 0; i < expr1.size(); i++) {
        auto dim = expr1[i];
        for (auto& iter : dimensions) {
            dim = symbolic::subs(dim, symbolic::symbol(iter), symbolic::symbol(iter + "_1"));
        }
        map_1 += language_extension.expression(dim);
        if (i < expr1.size() - 1) {
            map_1 += ", ";
        }
    }
    for (size_t i = 0; i < expr2.size(); i++) {
        auto dim = expr2[i];
        for (auto& iter : dimensions) {
            dim = symbolic::subs(dim, symbolic::symbol(iter), symbolic::symbol(iter + "_2"));
        }
        map_2 += language_extension.expression(dim);
        if (i < expr2.size() - 1) {
            map_2 += ", ";
        }
    }
    map_1 += "] ";
    map_2 += "] ";

    std::vector<std::string> constraints_1;
    std::vector<std::string> constraints_2;
    // Add bounds
    for (auto& con : constraints_syms) {
        auto con_1 = con;
        auto con_2 = con;
        for (auto& iter : dimensions) {
            con_1 = symbolic::subs(con_1, symbolic::symbol(iter), symbolic::symbol(iter + "_1"));
            con_2 = symbolic::subs(con_2, symbolic::symbol(iter), symbolic::symbol(iter + "_2"));
        }
        auto con_str_1 = constraint_to_isl_str(con_1);
        if (con_str_1.empty()) {
            continue;
        }
        auto con_str_2 = constraint_to_isl_str(con_2);
        if (!con_str_1.empty()) {
            constraints_1.push_back(con_str_1);
            constraints_2.push_back(con_str_2);
        }
    }
    if (!constraints_1.empty()) {
        map_1 += " : ";
        map_1 += helpers::join(constraints_1, " and ");
    }
    map_1 += " }";

    if (!constraints_2.empty()) {
        map_2 += " : ";
        map_2 += helpers::join(constraints_2, " and ");
    }
    map_2 += " }";

    std::string map_3 = "{ [";
    for (size_t i = 0; i < dimensions.size(); i++) {
        map_3 += dimensions[i] + "_2";
        if (i < dimensions.size() - 1) {
            map_3 += ", ";
        }
    }
    map_3 += "] -> [";
    for (size_t i = 0; i < dimensions.size(); i++) {
        map_3 += dimensions[i] + "_1";
        if (i < dimensions.size() - 1) {
            map_3 += ", ";
        }
    }
    map_3 += "]";
    std::vector<std::string> monotonicity_constraints;
    if (dimensions_syms.find(indvar) != dimensions_syms.end()) {
        monotonicity_constraints.push_back(indvar->get_name() + "_1 != " + indvar->get_name() +
                                           "_2");
    }
    if (!monotonicity_constraints.empty()) {
        map_3 += " : ";
        map_3 += helpers::join(monotonicity_constraints, " and ");
    }
    map_3 += " }";

    map_1 = std::regex_replace(map_1, std::regex("\\."), "_");
    map_2 = std::regex_replace(map_2, std::regex("\\."), "_");
    map_3 = std::regex_replace(map_3, std::regex("\\."), "_");

    return {map_1, map_2, map_3};
}

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

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

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

}  // namespace symbolic
}  // namespace sdfg

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