23049466917

Committed 13 Mar 2026 11:48AM UTC coverage: 63.722% (+0.2%) from 63.488%

Build # 23049466917

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #580 from daisytuner/advanced-loop-tiling

Dependence Deltas, LoopInterchange with Fourier-Motzkin and Novel TileFusion Transformation

Coverage Stats

613 of 845 new or added lines in 8 files covered. (72.54%)

5 existing lines in 3 files now uncovered.

25274 of 39663 relevant lines covered (63.72%)

400.64 hits per line

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

74.29

/sdfg/src/transformations/loop_interchange.cpp

#include "sdfg/transformations/loop_interchange.h"

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

#include "sdfg/analysis/data_dependency_analysis.h"
#include "sdfg/analysis/scope_analysis.h"
#include "sdfg/exceptions.h"
#include "sdfg/structured_control_flow/for.h"
#include "sdfg/structured_control_flow/structured_loop.h"
#include "sdfg/symbolic/polynomials.h"

namespace sdfg {
namespace transformations {

/// Check that a 2D delta set is lex-non-negative in the post-interchange order.
/// `new_outer_dim` is the index (0 or 1) of the dimension that becomes the
/// new outer loop after interchange.
/// Returns false (unsafe) if any delta vector is lex-negative in the new order.
static bool is_interchange_legal_2d(const std::string& deltas_str, int new_outer_dim) {
    if (deltas_str.empty()) {
        return false;
    }

    isl_ctx* ctx = isl_ctx_alloc();
    isl_options_set_on_error(ctx, ISL_ON_ERROR_CONTINUE);

    isl_set* deltas = isl_set_read_from_str(ctx, deltas_str.c_str());
    if (!deltas) {
        isl_ctx_free(ctx);
        return false;
    }

    int n_dims = isl_set_dim(deltas, isl_dim_set);
    if (n_dims != 2) {
        isl_set_free(deltas);
        isl_ctx_free(ctx);
        return false;
    }

    // Build lex-negative constraint in post-interchange order.
    // If new_outer is dim0: lex-neg = { [x, y] : x < 0 or (x = 0 and y < 0) }
    // If new_outer is dim1: lex-neg = { [x, y] : y < 0 or (y = 0 and x < 0) }
    const char* lex_neg_str = (new_outer_dim == 0) ? "{ [x, y] : x < 0 or (x = 0 and y < 0) }"
                                                   : "{ [x, y] : y < 0 or (y = 0 and x < 0) }";

    isl_set* lex_neg = isl_set_read_from_str(ctx, lex_neg_str);
    isl_set* violation = isl_set_intersect(deltas, lex_neg);
    bool legal = isl_set_is_empty(violation);
    isl_set_free(violation);
    isl_ctx_free(ctx);

    return legal;
}

/// Check that a 1D delta set {[d]} has no negative values.
/// After interchange the inner loop becomes the outer, so we need d >= 0.
static bool is_interchange_legal_1d(const std::string& deltas_str) {
    if (deltas_str.empty()) {
        return false;
    }

    isl_ctx* ctx = isl_ctx_alloc();
    isl_options_set_on_error(ctx, ISL_ON_ERROR_CONTINUE);

    isl_set* deltas = isl_set_read_from_str(ctx, deltas_str.c_str());
    if (!deltas) {
        isl_ctx_free(ctx);
        return false;
    }

    int n_dims = isl_set_dim(deltas, isl_dim_set);
    if (n_dims != 1) {
        isl_set_free(deltas);
        isl_ctx_free(ctx);
        return false;
    }

    isl_set* neg = isl_set_read_from_str(ctx, "{ [x] : x < 0 }");
    isl_set* violation = isl_set_intersect(deltas, neg);
    bool legal = isl_set_is_empty(violation);
    isl_set_free(violation);
    isl_ctx_free(ctx);

    return legal;
}

/// Extract the upper bound from a condition of the form `indvar [+ offset] < expr`,
/// or `And(indvar < expr1, indvar < expr2, ...)`.
/// Returns the equivalent RHS such that `indvar < result` (using min for conjunctions).
/// Returns SymEngine::null if the condition is not extractable.
static symbolic::Expression
extract_strict_upper_bound(const symbolic::Condition& condition, const symbolic::Symbol& indvar) {
    if (SymEngine::is_a<SymEngine::StrictLessThan>(*condition)) {
        auto lt = SymEngine::rcp_static_cast<const SymEngine::StrictLessThan>(condition);
        auto lhs = lt->get_arg1();
        auto rhs = lt->get_arg2();
        if (symbolic::eq(lhs, indvar)) {
            return rhs;
        }
        // Handle: Lt(indvar + offset, bound) → indvar < bound - offset
        if (symbolic::uses(lhs, indvar->get_name()) && !symbolic::uses(rhs, indvar->get_name())) {
            auto offset = symbolic::sub(lhs, indvar);
            if (!symbolic::uses(offset, indvar->get_name())) {
                return symbolic::sub(rhs, offset);
            }
        }
    }
    // Handle: And(cond1, cond2, ...) → min of extracted bounds
    if (SymEngine::is_a<SymEngine::And>(*condition)) {
        auto conj = SymEngine::rcp_static_cast<const SymEngine::And>(condition);
        symbolic::Expression result = SymEngine::null;
        for (auto& arg : conj->get_container()) {
            auto bound = extract_strict_upper_bound(SymEngine::rcp_dynamic_cast<const SymEngine::Boolean>(arg), indvar);
            if (bound == SymEngine::null) return SymEngine::null;
            if (result == SymEngine::null) {
                result = bound;
            } else {
                result = symbolic::min(result, bound);
            }
        }
        return result;
    }
    return SymEngine::null;
}

/// Decompose `expr` as `coefficient * sym + constant` where coefficient is a
/// positive integer.  Returns the (coefficient, constant) pair on success, or
/// (null, null) when the expression is not affine in `sym` or the coefficient
/// is not a positive integer.
struct AffineDecomp {
    symbolic::Expression coefficient = SymEngine::null;
    symbolic::Expression constant = SymEngine::null;
    explicit operator bool() const { return coefficient != SymEngine::null; }
};

static AffineDecomp check_affine(const symbolic::Expression& expr, const symbolic::Symbol& sym) {
    symbolic::SymbolVec syms = {sym};
    auto poly = symbolic::polynomial(expr, syms);
    if (poly == SymEngine::null) return {};
    auto coeffs = symbolic::affine_coefficients(poly, syms);
    if (coeffs.empty()) return {};
    auto coeff = coeffs[sym];
    // Coefficient must be a positive integer
    if (!SymEngine::is_a<SymEngine::Integer>(*coeff)) return {};
    if (SymEngine::down_cast<const SymEngine::Integer&>(*coeff).as_int() <= 0) return {};
    return {coeff, coeffs[symbolic::symbol("__daisy_constant__")]};
}

LoopInterchange::LoopInterchange(
    structured_control_flow::StructuredLoop& outer_loop, structured_control_flow::StructuredLoop& inner_loop
)
    : outer_loop_(outer_loop), inner_loop_(inner_loop) {

      };

std::string LoopInterchange::name() const { return "LoopInterchange"; };

bool LoopInterchange::can_be_applied(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {
    auto& outer_indvar = this->outer_loop_.indvar();

    // Check if inner bounds depend on outer loop
    auto inner_loop_init = this->inner_loop_.init();
    auto inner_loop_condition = this->inner_loop_.condition();
    auto inner_loop_update = this->inner_loop_.update();

    // Inner update must never depend on outer
    if (symbolic::uses(inner_loop_update, outer_indvar->get_name())) {
        return false;
    }

    bool inner_depends_on_outer = symbolic::uses(inner_loop_init, outer_indvar->get_name()) ||
                                  symbolic::uses(inner_loop_condition, outer_indvar->get_name());

    if (inner_depends_on_outer) {
        // Fourier-Motzkin elimination: only For-For
        if (dynamic_cast<structured_control_flow::Map*>(&outer_loop_) ||
            dynamic_cast<structured_control_flow::Map*>(&inner_loop_)) {
            return false;
        }
        // Outer loop must have unit step
        if (!symbolic::eq(outer_loop_.update(), symbolic::add(outer_loop_.indvar(), symbolic::integer(1)))) {
            return false;
        }
        // Inner loop must have a positive integer step
        auto inner_stride = symbolic::sub(inner_loop_.update(), inner_loop_.indvar());
        if (!SymEngine::is_a<SymEngine::Integer>(*inner_stride) ||
            SymEngine::down_cast<const SymEngine::Integer&>(*inner_stride).as_int() <= 0) {
            return false;
        }
        // Outer condition must be extractable as indvar < bound
        auto outer_bound = extract_strict_upper_bound(outer_loop_.condition(), outer_loop_.indvar());
        if (outer_bound == SymEngine::null) {
            return false;
        }
        // Inner init must be affine in outer indvar with positive integer coeff
        auto init_decomp = check_affine(inner_loop_init, outer_indvar);
        if (!init_decomp) {
            return false;
        }
        // Inner bound must be affine in outer indvar with positive integer coeff
        auto inner_bound = extract_strict_upper_bound(inner_loop_.condition(), inner_loop_.indvar());
        if (inner_bound == SymEngine::null) {
            return false;
        }
        auto bound_decomp = check_affine(inner_bound, outer_indvar);
        if (!bound_decomp) {
            return false;
        }
        // Both must have the same coefficient (ensures rectangular projection)
        if (!symbolic::eq(init_decomp.coefficient, bound_decomp.coefficient)) {
            return false;
        }
    }

    // Criterion: Outer loop must not have any outer blocks
    if (outer_loop_.root().size() > 1) {
        return false;
    }
    if (outer_loop_.root().at(0).second.assignments().size() > 0) {
        return false;
    }
    if (&outer_loop_.root().at(0).first != &inner_loop_) {
        return false;
    }
    // Criterion: Any of both loops is a map
    if (dynamic_cast<structured_control_flow::Map*>(&outer_loop_) ||
        dynamic_cast<structured_control_flow::Map*>(&inner_loop_)) {
        return true;
    }

    auto& users_analysis = analysis_manager.get<analysis::Users>();
    analysis::UsersView body_users(users_analysis, inner_loop_.root());
    if (!body_users.views().empty() || !body_users.moves().empty()) {
        // Views and moves may have complex semantics that we don't handle yet
        return false;
    }

    // For-For: check legality using dependence delta sets
    analysis::DataDependencyAnalysis dda(builder.subject(), true);
    dda.run(analysis_manager);

    std::string outer_indvar_name = outer_loop_.indvar()->get_name();
    std::string inner_indvar_name = inner_loop_.indvar()->get_name();

    // Check outer loop dependencies (2D delta sets: [d_outer, d_inner])
    auto& outer_deps = dda.dependencies(outer_loop_);
    for (auto& dep : outer_deps) {
        // Skip dependencies on loop induction variables — structurally safe
        if (dep.first == outer_indvar_name || dep.first == inner_indvar_name) {
            continue;
        }
        auto& deltas = dep.second.deltas;
        if (deltas.empty) {
            continue;
        }
        if (deltas.dimensions.empty()) {
            // No loop dimensions — purely intra-iteration, safe for interchange
            continue;
        }
        if (deltas.deltas_str.empty()) {
            // Dependence exists but no isl info — conservative reject
            return false;
        }
        if (deltas.dimensions.size() == 2) {
            // Determine which dimension becomes the new outer (= current inner indvar)
            int new_outer_dim = -1;
            for (int d = 0; d < 2; d++) {
                if (deltas.dimensions[d] == inner_indvar_name) {
                    new_outer_dim = d;
                    break;
                }
            }
            if (new_outer_dim < 0) {
                // Can't identify dimension mapping — conservative reject
                return false;
            }
            if (!is_interchange_legal_2d(deltas.deltas_str, new_outer_dim)) {
                return false;
            }
        } else if (deltas.dimensions.size() == 1) {
            // Only outer dimension — after interchange becomes inner, always safe
        } else {
            return false;
        }
    }

    // Check inner loop dependencies (1D delta sets: [d_inner])
    auto& inner_deps = dda.dependencies(inner_loop_);
    for (auto& dep : inner_deps) {
        if (dep.first == outer_indvar_name || dep.first == inner_indvar_name) {
            continue;
        }
        auto& deltas = dep.second.deltas;
        if (deltas.empty) {
            continue;
        }
        if (deltas.dimensions.empty()) {
            continue;
        }
        if (deltas.deltas_str.empty()) {
            return false;
        }
        if (deltas.dimensions.size() == 1) {
            if (!is_interchange_legal_1d(deltas.deltas_str)) {
                return false;
            }
        } else {
            return false;
        }
    }

    return true;
};

void LoopInterchange::apply(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {
    auto& scope_analysis = analysis_manager.get<analysis::ScopeAnalysis>();
    auto& outer_scope = static_cast<structured_control_flow::Sequence&>(*scope_analysis.parent_scope(&outer_loop_));
    auto& inner_scope = outer_loop_.root();

    int index = outer_scope.index(this->outer_loop_);
    auto& outer_transition = outer_scope.at(index).second;

    // Add new outer and inner loops
    structured_control_flow::StructuredLoop* new_outer_loop = nullptr;
    structured_control_flow::StructuredLoop* new_inner_loop = nullptr;

    auto* inner_map = dynamic_cast<structured_control_flow::Map*>(&inner_loop_);
    auto* outer_map = dynamic_cast<structured_control_flow::Map*>(&outer_loop_);

    bool dependent = !inner_map && !outer_map &&
                     (symbolic::uses(inner_loop_.init(), outer_loop_.indvar()->get_name()) ||
                      symbolic::uses(inner_loop_.condition(), outer_loop_.indvar()->get_name()));

    if (dependent) {
        // Fourier-Motzkin elimination: compute projected and inverted bounds
        auto outer_indvar = outer_loop_.indvar();
        auto inner_indvar = inner_loop_.indvar();
        auto outer_init_expr = outer_loop_.init();
        auto outer_bound = extract_strict_upper_bound(outer_loop_.condition(), outer_indvar);
        auto outer_max = symbolic::sub(outer_bound, symbolic::integer(1));

        auto inner_init_expr = inner_loop_.init();
        auto inner_bound_expr = extract_strict_upper_bound(inner_loop_.condition(), inner_indvar);

        // Project inner bounds for new outer loop:
        //   new_init = inner_init(outer_var = outer_init)
        //   new_bound = inner_bound(outer_var = outer_max)
        auto new_outer_init = symbolic::subs(inner_init_expr, outer_indvar, outer_init_expr);
        auto new_outer_bound = symbolic::subs(inner_bound_expr, outer_indvar, outer_max);
        auto new_outer_cond = symbolic::Lt(inner_indvar, new_outer_bound);

        // Invert inner bounds for new inner loop (FM elimination):
        //   inner_init  = α*outer_var + b  =>  from y >= α*x + b:  x <= (y-b)/α
        //   inner_bound = α*outer_var + d  =>  from y <  α*x + d:  x >  (y-d)/α
        // Integer rounding: x < floor((y-b)/α) + 1 and x >= floor((y-d)/α) + 1
        auto init_decomp = check_affine(inner_init_expr, outer_indvar);
        auto bound_decomp = check_affine(inner_bound_expr, outer_indvar);
        auto alpha = init_decomp.coefficient; // == bound_decomp.coefficient
        auto b = init_decomp.constant;
        auto d = bound_decomp.constant;

        symbolic::Expression lower_from_cond, upper_from_init;
        if (symbolic::eq(alpha, symbolic::integer(1))) {
            // Unit coefficient — avoid introducing idiv(x,1)
            lower_from_cond = symbolic::add(symbolic::sub(inner_indvar, d), symbolic::integer(1));
            upper_from_init = symbolic::add(symbolic::sub(inner_indvar, b), symbolic::integer(1));
        } else {
            // General: floor((y - const) / α) + 1
            lower_from_cond = symbolic::add(symbolic::div(symbolic::sub(inner_indvar, d), alpha), symbolic::integer(1));
            upper_from_init = symbolic::add(symbolic::div(symbolic::sub(inner_indvar, b), alpha), symbolic::integer(1));
        }
        auto new_inner_init = symbolic::max(outer_init_expr, lower_from_cond);
        auto new_inner_bound = symbolic::min(outer_bound, upper_from_init);
        auto new_inner_cond = symbolic::Lt(outer_indvar, new_inner_bound);

        new_outer_loop = &builder.add_for_after(
            outer_scope,
            this->outer_loop_,
            inner_indvar,
            new_outer_cond,
            new_outer_init,
            this->inner_loop_.update(),
            outer_transition.assignments(),
            this->inner_loop_.debug_info()
        );

        new_inner_loop = &builder.add_for_after(
            inner_scope,
            this->inner_loop_,
            outer_indvar,
            new_inner_cond,
            new_inner_init,
            this->outer_loop_.update(),
            {},
            this->outer_loop_.debug_info()
        );
    } else {
        // Standard case: just swap loop headers
        if (inner_map) {
            new_outer_loop = &builder.add_map_after(
                outer_scope,
                this->outer_loop_,
                inner_map->indvar(),
                inner_map->condition(),
                inner_map->init(),
                inner_map->update(),
                inner_map->schedule_type(),
                outer_transition.assignments(),
                this->inner_loop_.debug_info()
            );
        } else {
            new_outer_loop = &builder.add_for_after(
                outer_scope,
                this->outer_loop_,
                this->inner_loop_.indvar(),
                this->inner_loop_.condition(),
                this->inner_loop_.init(),
                this->inner_loop_.update(),
                outer_transition.assignments(),
                this->inner_loop_.debug_info()
            );
        }

        if (outer_map) {
            new_inner_loop = &builder.add_map_after(
                inner_scope,
                this->inner_loop_,
                outer_map->indvar(),
                outer_map->condition(),
                outer_map->init(),
                outer_map->update(),
                outer_map->schedule_type(),
                {},
                this->outer_loop_.debug_info()
            );
        } else {
            new_inner_loop = &builder.add_for_after(
                inner_scope,
                this->inner_loop_,
                this->outer_loop_.indvar(),
                this->outer_loop_.condition(),
                this->outer_loop_.init(),
                this->outer_loop_.update(),
                {},
                this->outer_loop_.debug_info()
            );
        }
    }

    // Insert inner loop body into new inner loop
    builder.move_children(this->inner_loop_.root(), new_inner_loop->root());

    // Insert outer loop body into new outer loop
    builder.move_children(this->outer_loop_.root(), new_outer_loop->root());

    // Remove old loops
    builder.remove_child(new_outer_loop->root(), 0);
    builder.remove_child(outer_scope, index);

    analysis_manager.invalidate_all();
    applied_ = true;
    new_outer_loop_ = new_outer_loop;
    new_inner_loop_ = new_inner_loop;
};

void LoopInterchange::to_json(nlohmann::json& j) const {
    std::vector<std::string> loop_types;
    for (auto* loop : {&(this->outer_loop_), &(this->inner_loop_)}) {
        if (dynamic_cast<structured_control_flow::For*>(loop)) {
            loop_types.push_back("for");
        } else if (dynamic_cast<structured_control_flow::Map*>(loop)) {
            loop_types.push_back("map");
        } else {
            throw InvalidSDFGException("Unsupported loop type for serialization of loop: " + loop->indvar()->get_name());
        }
    }
    j["transformation_type"] = this->name();
    j["subgraph"] = {
        {"0", {{"element_id", this->outer_loop_.element_id()}, {"type", loop_types[0]}}},
        {"1", {{"element_id", this->inner_loop_.element_id()}, {"type", loop_types[1]}}}
    };
};

LoopInterchange LoopInterchange::from_json(builder::StructuredSDFGBuilder& builder, const nlohmann::json& desc) {
    auto outer_loop_id = desc["subgraph"]["0"]["element_id"].get<size_t>();
    auto inner_loop_id = desc["subgraph"]["1"]["element_id"].get<size_t>();
    auto outer_element = builder.find_element_by_id(outer_loop_id);
    auto inner_element = builder.find_element_by_id(inner_loop_id);
    if (outer_element == nullptr) {
        throw InvalidSDFGException("Element with ID " + std::to_string(outer_loop_id) + " not found.");
    }
    if (inner_element == nullptr) {
        throw InvalidSDFGException("Element with ID " + std::to_string(inner_loop_id) + " not found.");
    }
    auto outer_loop = dynamic_cast<structured_control_flow::StructuredLoop*>(outer_element);
    if (outer_loop == nullptr) {
        throw InvalidSDFGException("Element with ID " + std::to_string(outer_loop_id) + " is not a StructuredLoop.");
    }
    auto inner_loop = dynamic_cast<structured_control_flow::StructuredLoop*>(inner_element);
    if (inner_loop == nullptr) {
        throw InvalidSDFGException("Element with ID " + std::to_string(inner_loop_id) + " is not a StructuredLoop.");
    }

    return LoopInterchange(*outer_loop, *inner_loop);
};

structured_control_flow::StructuredLoop* LoopInterchange::new_outer_loop() const {
    if (!applied_) {
        throw InvalidSDFGException("Transformation has not been applied yet.");
    }
    return new_outer_loop_;
};

structured_control_flow::StructuredLoop* LoopInterchange::new_inner_loop() const {
    if (!applied_) {
        throw InvalidSDFGException("Transformation has not been applied yet.");
    }
    return new_inner_loop_;
};

} // namespace transformations
} // namespace sdfg

daisytuner / docc / 23049466917

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