15970039243

Committed 30 Jun 2025 10:08AM UTC coverage: 64.86% (+0.05%) from 64.811%

Build # 15970039243

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #122 from daisytuner/tighest-bounds

adds support for handling different assumptions for two maps

Run Details

42 of 63 new or added lines in 4 files covered. (66.67%)

3 existing lines in 1 file now uncovered.

8675 of 13375 relevant lines covered (64.86%)

172.52 hits per line

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

86.43

/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 (assums.find(sym) == assums.end() && assums.at(sym).constant()) {
            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 += " }";

    // NV Symbols, e.g., threadIdx.x
    map = std::regex_replace(map, std::regex("\\."), "_");

    // min, max
    map = std::regex_replace(map, std::regex("__daisy_min"), "min_");
    map = std::regex_replace(map, std::regex("__daisy_max"), "max_");

    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() && assums1.at(sym).constant() &&
            assums2.at(sym).constant()) {
            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_1 = generate_constraints(syms, assums1, seen);
    seen.clear();
    auto constraints_syms_2 = generate_constraints(syms, assums2, seen);

    // Extend parameters with additional symbols from constraints
    for (auto& con : constraints_syms_1) {
        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);
            }
        }
    }
    for (auto& con : constraints_syms_2) {
        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;
    // Add bounds
    for (auto& con : constraints_syms_1) {
        auto con_1 = con;
        for (auto& iter : dimensions) {
            con_1 = symbolic::subs(con_1, symbolic::symbol(iter), symbolic::symbol(iter + "_1"));
        }
        auto con_str_1 = constraint_to_isl_str(con_1);
        if (con_str_1.empty()) {
            continue;
        }
        constraints_1.push_back(con_str_1);
    }
    if (!constraints_1.empty()) {
        map_1 += " : ";
        map_1 += helpers::join(constraints_1, " and ");
    }
    map_1 += " }";

    std::vector<std::string> constraints_2;
    for (auto& con : constraints_syms_2) {
        auto con_2 = con;
        for (auto& iter : dimensions) {
            con_2 = symbolic::subs(con_2, symbolic::symbol(iter), symbolic::symbol(iter + "_2"));
        }
        auto con_str_2 = constraint_to_isl_str(con_2);
        if (con_str_2.empty()) {
            continue;
        }
        constraints_2.push_back(con_str_2);
    }
    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("\\."), "_");

    map_1 = std::regex_replace(map_1, std::regex("__daisy_min"), "min");
    map_1 = std::regex_replace(map_1, std::regex("__daisy_max"), "max");
    map_2 = std::regex_replace(map_2, std::regex("__daisy_min"), "min");
    map_2 = std::regex_replace(map_2, std::regex("__daisy_max"), "max");
    map_3 = std::regex_replace(map_3, std::regex("__daisy_min"), "min");
    map_3 = std::regex_replace(map_3, std::regex("__daisy_max"), "max");

    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();
        if (SymEngine::is_a<SymEngine::Infty>(*lhs) || SymEngine::is_a<SymEngine::Infty>(*rhs)) {
            return "";
        }
        auto res = language_extension.expression(lhs) + " < " + language_extension.expression(rhs);
        res = std::regex_replace(res, std::regex("\\."), "_");
        res = std::regex_replace(res, std::regex("__daisy_min"), "min");
        res = std::regex_replace(res, std::regex("__daisy_max"), "max");
        return res;
    } 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();
        if (SymEngine::is_a<SymEngine::Infty>(*lhs) || SymEngine::is_a<SymEngine::Infty>(*rhs)) {
            return "";
        }
        auto res = language_extension.expression(lhs) + " <= " + language_extension.expression(rhs);
        res = std::regex_replace(res, std::regex("\\."), "_");
        res = std::regex_replace(res, std::regex("__daisy_min"), "min");
        res = std::regex_replace(res, std::regex("__daisy_max"), "max");
        return res;
    } 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();
        if (SymEngine::is_a<SymEngine::Infty>(*lhs) || SymEngine::is_a<SymEngine::Infty>(*rhs)) {
            return "";
        }
        auto res = language_extension.expression(lhs) + " == " + language_extension.expression(rhs);
        res = std::regex_replace(res, std::regex("\\."), "_");
        res = std::regex_replace(res, std::regex("__daisy_min"), "min");
        res = std::regex_replace(res, std::regex("__daisy_max"), "max");
        return res;
    } 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();
        if (SymEngine::is_a<SymEngine::Infty>(*lhs) || SymEngine::is_a<SymEngine::Infty>(*rhs)) {
            return "";
        }
        auto res = language_extension.expression(lhs) + " != " + language_extension.expression(rhs);
        res = std::regex_replace(res, std::regex("\\."), "_");
        res = std::regex_replace(res, std::regex("__daisy_min"), "min");
        res = std::regex_replace(res, std::regex("__daisy_max"), "max");
        return res;
    }

    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 (assums.at(sym).constant() && assums.at(sym).map() == SymEngine::null) {
                continue;
            }
            symbols.push_back(sym);
        }
        if (symbols.empty() || symbols.size() <= 1) {
            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));
            remaining = symbolic::expand(remaining);
            remaining = symbolic::simplify(remaining);

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

daisytuner / sdfglib / 15970039243

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