25289367548

Committed 03 May 2026 08:01PM UTC coverage: 64.317% (+0.1%) from 64.206%

Build # 25289367548

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #698 from daisytuner/tile-fusion-double-buffering

Tile fusion double buffering

Coverage Stats

306 of 453 new or added lines in 4 files covered. (67.55%)

3 existing lines in 2 files now uncovered.

31682 of 49259 relevant lines covered (64.32%)

1432.27 hits per line

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

0.0

/opt/src/transformations/loop_peeling.cpp

#include "sdfg/transformations/loop_peeling.h"

#include "sdfg/analysis/scope_analysis.h"
#include "sdfg/builder/structured_sdfg_builder.h"
#include "sdfg/deepcopy/structured_sdfg_deep_copy.h"
#include "sdfg/structured_control_flow/for.h"
#include "sdfg/structured_control_flow/map.h"
#include "sdfg/structured_control_flow/sequence.h"
#include "sdfg/symbolic/symbolic.h"

#include <symengine/functions.h>
#include <symengine/logic.h>

namespace sdfg {
namespace transformations {

LoopPeeling::LoopPeeling(structured_control_flow::StructuredLoop& loop) : loop_(loop) {};

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

/// Extract upper bound from a condition of the form `indvar < bound`.
/// Returns SymEngine::null if not a simple strict-less-than on indvar.
static symbolic::Expression extract_upper_bound(const symbolic::Condition& cond, const symbolic::Symbol& indvar) {
    if (!SymEngine::is_a<SymEngine::StrictLessThan>(*cond)) {
        return SymEngine::null;
    }
    auto lt = SymEngine::rcp_static_cast<const SymEngine::StrictLessThan>(cond);
    auto lhs = lt->get_arg1();
    auto rhs = lt->get_arg2();
    if (symbolic::eq(lhs, indvar)) {
        return rhs;
    }
    return SymEngine::null;
}

/// Determine if `bound - init` simplifies to a positive integer constant.
/// Also handles the case where init is a max() expression: if bound - any_arg
/// gives a positive integer constant, the loop has a bounded trip count.
static bool is_constant_trip_bound(const symbolic::Expression& bound, const symbolic::Expression& init) {
    auto diff = symbolic::expand(symbolic::sub(bound, init));
    if (SymEngine::is_a<SymEngine::Integer>(*diff)) {
        auto val = SymEngine::rcp_static_cast<const SymEngine::Integer>(diff);
        return val->as_int() > 0;
    }
    // If init is max(a, b, ...), check if bound - arg is constant for any arg.
    // trip_count = bound - max(a, b, ...) = min(bound-a, bound-b, ...)
    // If any (bound - arg) is a positive constant, then the trip count is at most that constant.
    if (SymEngine::is_a<SymEngine::Max>(*init)) {
        auto max_op = SymEngine::rcp_static_cast<const SymEngine::Max>(init);
        auto args = max_op->get_args();
        for (auto& arg : args) {
            auto arg_diff = symbolic::expand(symbolic::sub(bound, arg));
            if (SymEngine::is_a<SymEngine::Integer>(*arg_diff)) {
                auto val = SymEngine::rcp_static_cast<const SymEngine::Integer>(arg_diff);
                if (val->as_int() > 0) {
                    return true;
                }
            }
        }
    }
    return false;
}

/// Get the constant trip count for a bound/init pair that passes is_constant_trip_bound.
/// Returns the positive integer trip count, handling max() in init.
static int64_t get_constant_trip_count(const symbolic::Expression& bound, const symbolic::Expression& init) {
    auto diff = symbolic::expand(symbolic::sub(bound, init));
    if (SymEngine::is_a<SymEngine::Integer>(*diff)) {
        return SymEngine::rcp_static_cast<const SymEngine::Integer>(diff)->as_int();
    }
    // For init = max(a, b, ...), find the smallest positive constant among (bound - arg)
    if (SymEngine::is_a<SymEngine::Max>(*init)) {
        auto max_op = SymEngine::rcp_static_cast<const SymEngine::Max>(init);
        auto args = max_op->get_args();
        int64_t best = INT64_MAX;
        for (auto& arg : args) {
            auto arg_diff = symbolic::expand(symbolic::sub(bound, arg));
            if (SymEngine::is_a<SymEngine::Integer>(*arg_diff)) {
                auto val = SymEngine::rcp_static_cast<const SymEngine::Integer>(arg_diff)->as_int();
                if (val > 0 && val < best) {
                    best = val;
                }
            }
        }
        return best;
    }
    // Should not reach here if is_constant_trip_bound returned true
    return 0;
}

/// Check if a loop has a compound condition with at least one canonical bound.
static bool loop_is_peelable(structured_control_flow::StructuredLoop& loop) {
    auto cond = loop.condition();
    if (!SymEngine::is_a<SymEngine::And>(*cond)) {
        return false;
    }
    auto and_cond = SymEngine::rcp_static_cast<const SymEngine::And>(cond);
    auto& conjuncts = and_cond->get_container();
    if (conjuncts.size() < 2) {
        return false;
    }

    auto indvar = loop.indvar();
    auto init = loop.init();
    bool has_canonical = false;
    bool has_dynamic = false;

    for (auto& conjunct : conjuncts) {
        auto bound = extract_upper_bound(conjunct, indvar);
        if (bound == SymEngine::null) {
            return false;
        }
        if (is_constant_trip_bound(bound, init)) {
            has_canonical = true;
        } else {
            has_dynamic = true;
        }
    }
    return has_canonical && has_dynamic;
}

/// For a peelable loop, extract the canonical bound (tightest constant-trip bound).
static symbolic::Expression find_canonical_bound(structured_control_flow::StructuredLoop& loop) {
    auto cond = loop.condition();
    auto and_cond = SymEngine::rcp_static_cast<const SymEngine::And>(cond);
    auto& conjuncts = and_cond->get_container();
    auto indvar = loop.indvar();
    auto init = loop.init();

    symbolic::Expression canonical = SymEngine::null;
    int64_t canonical_trip = INT64_MAX;
    for (auto& conjunct : conjuncts) {
        auto bound = extract_upper_bound(conjunct, indvar);
        if (bound == SymEngine::null) continue;
        if (!is_constant_trip_bound(bound, init)) continue;

        auto trip = get_constant_trip_count(bound, init);
        if (canonical == SymEngine::null || trip < canonical_trip) {
            canonical = bound;
            canonical_trip = trip;
        }
    }
    return canonical;
}

/// Build the peeling condition for a single loop: canonical_bound <= each dynamic bound.
static symbolic::Condition build_loop_peeling_condition(
    structured_control_flow::StructuredLoop& loop, const symbolic::Expression& canonical_bound
) {
    auto cond = loop.condition();
    auto and_cond = SymEngine::rcp_static_cast<const SymEngine::And>(cond);
    auto& conjuncts = and_cond->get_container();
    auto indvar = loop.indvar();
    auto init = loop.init();

    symbolic::Condition result = SymEngine::boolTrue;
    for (auto& conjunct : conjuncts) {
        auto bound = extract_upper_bound(conjunct, indvar);
        if (bound == SymEngine::null) continue;
        if (is_constant_trip_bound(bound, init) && symbolic::eq(bound, canonical_bound)) continue;
        // canonical_bound <= this dynamic/looser bound
        result = symbolic::And(result, symbolic::Le(canonical_bound, bound));
    }

    // If init is max(a, b, ...), we need to ensure the max resolves to the arg
    // that gives the constant trip count. Add conditions: chosen_arg >= other_args.
    if (SymEngine::is_a<SymEngine::Max>(*init)) {
        auto max_op = SymEngine::rcp_static_cast<const SymEngine::Max>(init);
        auto args = max_op->get_args();
        // Find the arg that gives the constant trip (smallest constant trip)
        symbolic::Expression chosen_arg = SymEngine::null;
        int64_t best_trip = INT64_MAX;
        for (auto& arg : args) {
            auto arg_diff = symbolic::expand(symbolic::sub(canonical_bound, arg));
            if (SymEngine::is_a<SymEngine::Integer>(*arg_diff)) {
                auto val = SymEngine::rcp_static_cast<const SymEngine::Integer>(arg_diff)->as_int();
                if (val > 0 && val < best_trip) {
                    best_trip = val;
                    chosen_arg = arg;
                }
            }
        }
        // Add conditions: chosen_arg >= each other arg (so max resolves to chosen_arg)
        if (chosen_arg != SymEngine::null) {
            for (auto& arg : args) {
                if (!symbolic::eq(arg, chosen_arg)) {
                    result = symbolic::And(result, symbolic::Le(arg, chosen_arg));
                }
            }
        }
    }

    return result;
}

/// Collect the perfectly nested chain of peelable loops starting from `loop`.
/// A chain continues as long as the loop body has exactly one child which is
/// another peelable structured loop.
static std::vector<structured_control_flow::StructuredLoop*> collect_peelable_nest(structured_control_flow::StructuredLoop&
                                                                                       loop) {
    std::vector<structured_control_flow::StructuredLoop*> nest;
    nest.push_back(&loop);

    auto* current = &loop;
    while (true) {
        auto& body = current->root();
        if (body.size() != 1) break;
        auto& child = body.at(0).first;
        auto* inner_loop = dynamic_cast<structured_control_flow::StructuredLoop*>(&child);
        if (!inner_loop) break;
        if (!loop_is_peelable(*inner_loop)) break;
        nest.push_back(inner_loop);
        current = inner_loop;
    }
    return nest;
}

bool LoopPeeling::can_be_applied(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {
    return loop_is_peelable(loop_);
};

void LoopPeeling::apply(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {
    auto& sdfg = builder.subject();

    // Collect perfectly nested chain of peelable loops
    auto nest = collect_peelable_nest(loop_);

    // For each loop in the nest, find its canonical bound and build peeling condition
    struct LoopPeelInfo {
        structured_control_flow::StructuredLoop* loop;
        symbolic::Expression canonical_bound;
        symbolic::Condition peeling_condition;
    };
    std::vector<LoopPeelInfo> peel_infos;

    symbolic::Condition combined_peeling_condition = SymEngine::boolTrue;
    for (auto* loop : nest) {
        auto canonical = find_canonical_bound(*loop);
        auto peel_cond = build_loop_peeling_condition(*loop, canonical);
        combined_peeling_condition = symbolic::And(combined_peeling_condition, peel_cond);
        peel_infos.push_back({loop, canonical, peel_cond});
    }

    // Get parent scope of the outermost loop
    auto& scope_analysis = analysis_manager.get<analysis::ScopeAnalysis>();
    auto parent = static_cast<structured_control_flow::Sequence*>(scope_analysis.parent_scope(&loop_));

    // Create IfElse before the outermost loop
    auto& if_else = builder.add_if_else_before(*parent, loop_, {}, loop_.debug_info());

    // === Then branch: all loops normalized to start at 0 with constant trip counts ===
    auto& then_branch = builder.add_case(if_else, combined_peeling_condition);

    // Build the nest of loops with clean 0-based bounds in the then branch
    structured_control_flow::Sequence* current_parent = &then_branch;
    // Track substitutions: original_indvar → indvar + init (for body fixup)
    std::vector<std::pair<symbolic::Symbol, symbolic::Expression>> substitutions;

    for (size_t i = 0; i < peel_infos.size(); i++) {
        auto& info = peel_infos[i];
        auto* loop = info.loop;
        auto indvar = loop->indvar();
        auto init = loop->init();

        // Compute constant trip count: canonical_bound - init (using helper for max() cases)
        auto trip_count = symbolic::integer(get_constant_trip_count(info.canonical_bound, init));

        // Resolve effective init for the then-branch.
        // If init = max(a, b, ...) and canonical_bound - b is the constant trip,
        // then in the then-branch (where peeling condition guarantees max = b), use b directly.
        symbolic::Expression effective_init = init;
        if (SymEngine::is_a<SymEngine::Max>(*init)) {
            auto max_op = SymEngine::rcp_static_cast<const SymEngine::Max>(init);
            auto args = max_op->get_args();
            int64_t best_trip = INT64_MAX;
            for (auto& arg : args) {
                auto arg_diff = symbolic::expand(symbolic::sub(info.canonical_bound, arg));
                if (SymEngine::is_a<SymEngine::Integer>(*arg_diff)) {
                    auto val = SymEngine::rcp_static_cast<const SymEngine::Integer>(arg_diff)->as_int();
                    if (val > 0 && val < best_trip) {
                        best_trip = val;
                        effective_init = arg;
                    }
                }
            }
        }

        // New loop: indvar goes from 0 to trip_count
        auto zero_condition = symbolic::Lt(indvar, trip_count);
        auto zero_init = symbolic::integer(0);

        structured_control_flow::StructuredLoop* new_loop = nullptr;
        if (auto map = dynamic_cast<structured_control_flow::Map*>(loop)) {
            new_loop = &builder.add_map(
                *current_parent,
                indvar,
                zero_condition,
                zero_init,
                loop->update(),
                map->schedule_type(),
                {},
                loop->debug_info()
            );
        } else {
            new_loop =
                &builder
                     .add_for(*current_parent, indvar, zero_condition, zero_init, loop->update(), {}, loop->debug_info());
        }

        // Record substitution: in the body, original indvar usage = new_indvar + effective_init
        substitutions.push_back({indvar, effective_init});
        current_parent = &new_loop->root();
    }

    // Deep copy the innermost loop's body into the new innermost loop
    auto* innermost = nest.back();
    deepcopy::StructuredSDFGDeepCopy main_copier(builder, *current_parent, innermost->root());
    main_copier.insert();

    // Apply shift substitutions in the copied body:
    // Replace indvar with (indvar + original_init) so body accesses use correct offsets.
    // Must apply outermost first (since inner body may reference outer indvars).
    for (auto& [indvar, init] : substitutions) {
        if (symbolic::eq(init, symbolic::zero())) continue;
        auto shifted_expr = symbolic::add(indvar, init);
        current_parent->replace(indvar, shifted_expr);
    }

    // === Else branch: original compound bounds (remainder) ===
    auto else_condition = symbolic::Not(combined_peeling_condition);
    auto& else_branch = builder.add_case(if_else, else_condition);

    // Build the nest of loops with original conditions in the else branch
    current_parent = &else_branch;
    for (size_t i = 0; i < peel_infos.size(); i++) {
        auto* loop = peel_infos[i].loop;

        structured_control_flow::StructuredLoop* new_loop = nullptr;
        if (auto map = dynamic_cast<structured_control_flow::Map*>(loop)) {
            new_loop = &builder.add_map(
                *current_parent,
                loop->indvar(),
                loop->condition(),
                loop->init(),
                loop->update(),
                map->schedule_type(),
                {},
                loop->debug_info()
            );
        } else {
            new_loop = &builder.add_for(
                *current_parent, loop->indvar(), loop->condition(), loop->init(), loop->update(), {}, loop->debug_info()
            );
        }
        current_parent = &new_loop->root();
    }

    // Deep copy the innermost loop's body into the remainder innermost loop
    deepcopy::StructuredSDFGDeepCopy remainder_copier(builder, *current_parent, innermost->root());
    remainder_copier.insert();

    // Remove the original loop
    builder.remove_child(*parent, parent->index(loop_));

    analysis_manager.invalidate_all();
};

void LoopPeeling::to_json(nlohmann::json& j) const {
    std::string loop_type;
    if (dynamic_cast<structured_control_flow::For*>(&loop_)) {
        loop_type = "for";
    } else if (dynamic_cast<structured_control_flow::Map*>(&loop_)) {
        loop_type = "map";
    } else {
        throw std::runtime_error("Unsupported loop type for serialization of loop: " + loop_.indvar()->get_name());
    }

    j["transformation_type"] = this->name();
    j["subgraph"] = {{"0", {{"element_id", this->loop_.element_id()}, {"type", loop_type}}}};
};

LoopPeeling LoopPeeling::from_json(builder::StructuredSDFGBuilder& builder, const nlohmann::json& desc) {
    auto loop_id = desc["subgraph"]["0"]["element_id"].get<size_t>();
    auto element = builder.find_element_by_id(loop_id);
    if (element == nullptr) {
        throw InvalidTransformationDescriptionException("Element with ID " + std::to_string(loop_id) + " not found.");
    }
    auto loop = dynamic_cast<structured_control_flow::StructuredLoop*>(element);
    if (loop == nullptr) {
        throw InvalidTransformationDescriptionException(
            "Element with ID " + std::to_string(loop_id) + " is not a StructuredLoop."
        );
    }

    return LoopPeeling(*loop);
};

} // namespace transformations
} // namespace sdfg

1	#include "sdfg/transformations/loop_peeling.h"
2
3	#include "sdfg/analysis/scope_analysis.h"
4	#include "sdfg/builder/structured_sdfg_builder.h"
5	#include "sdfg/deepcopy/structured_sdfg_deep_copy.h"
6	#include "sdfg/structured_control_flow/for.h"
7	#include "sdfg/structured_control_flow/map.h"
8	#include "sdfg/structured_control_flow/sequence.h"
9	#include "sdfg/symbolic/symbolic.h"
10
11	#include <symengine/functions.h>
12	#include <symengine/logic.h>
13
14	namespace sdfg {
15	namespace transformations {
16
17	LoopPeeling::LoopPeeling(structured_control_flow::StructuredLoop& loop) : loop_(loop) {};	×
18
19	std::string LoopPeeling::name() const { return "LoopPeeling"; };	×
20
21	/// Extract upper bound from a condition of the form `indvar < bound`.
22	/// Returns SymEngine::null if not a simple strict-less-than on indvar.
23	static symbolic::Expression extract_upper_bound(const symbolic::Condition& cond, const symbolic::Symbol& indvar) {	×
24	if (!SymEngine::is_a<SymEngine::StrictLessThan>(*cond)) {	×
25	return SymEngine::null;	×
26	}	×
27	auto lt = SymEngine::rcp_static_cast<const SymEngine::StrictLessThan>(cond);	×
28	auto lhs = lt->get_arg1();	×
29	auto rhs = lt->get_arg2();	×
30	if (symbolic::eq(lhs, indvar)) {	×
31	return rhs;	×
32	}	×
33	return SymEngine::null;	×
34	}	×
35
36	/// Determine if `bound - init` simplifies to a positive integer constant.
37	/// Also handles the case where init is a max() expression: if bound - any_arg
38	/// gives a positive integer constant, the loop has a bounded trip count.
39	static bool is_constant_trip_bound(const symbolic::Expression& bound, const symbolic::Expression& init) {	×
NEW 40	auto diff = symbolic::expand(symbolic::sub(bound, init));	×
41	if (SymEngine::is_a<SymEngine::Integer>(*diff)) {	×
42	auto val = SymEngine::rcp_static_cast<const SymEngine::Integer>(diff);	×
43	return val->as_int() > 0;	×
44	}	×
45	// If init is max(a, b, ...), check if bound - arg is constant for any arg.
46	// trip_count = bound - max(a, b, ...) = min(bound-a, bound-b, ...)
47	// If any (bound - arg) is a positive constant, then the trip count is at most that constant.
NEW 48	if (SymEngine::is_a<SymEngine::Max>(*init)) {	×
NEW 49	auto max_op = SymEngine::rcp_static_cast<const SymEngine::Max>(init);	×
NEW 50	auto args = max_op->get_args();	×
NEW 51	for (auto& arg : args) {	×
NEW 52	auto arg_diff = symbolic::expand(symbolic::sub(bound, arg));	×
NEW 53	if (SymEngine::is_a<SymEngine::Integer>(*arg_diff)) {	×
NEW 54	auto val = SymEngine::rcp_static_cast<const SymEngine::Integer>(arg_diff);	×
NEW 55	if (val->as_int() > 0) {	×
NEW 56	return true;	×
NEW 57	}	×
NEW 58	}	×
NEW 59	}	×
NEW 60	}	×
61	return false;	×
62	}	×
63
64	/// Get the constant trip count for a bound/init pair that passes is_constant_trip_bound.
65	/// Returns the positive integer trip count, handling max() in init.
NEW 66	static int64_t get_constant_trip_count(const symbolic::Expression& bound, const symbolic::Expression& init) {	×
NEW 67	auto diff = symbolic::expand(symbolic::sub(bound, init));	×
NEW 68	if (SymEngine::is_a<SymEngine::Integer>(*diff)) {	×
NEW 69	return SymEngine::rcp_static_cast<const SymEngine::Integer>(diff)->as_int();	×
NEW 70	}	×
71	// For init = max(a, b, ...), find the smallest positive constant among (bound - arg)
NEW 72	if (SymEngine::is_a<SymEngine::Max>(*init)) {	×
NEW 73	auto max_op = SymEngine::rcp_static_cast<const SymEngine::Max>(init);	×
NEW 74	auto args = max_op->get_args();	×
NEW 75	int64_t best = INT64_MAX;	×
NEW 76	for (auto& arg : args) {	×
NEW 77	auto arg_diff = symbolic::expand(symbolic::sub(bound, arg));	×
NEW 78	if (SymEngine::is_a<SymEngine::Integer>(*arg_diff)) {	×
NEW 79	auto val = SymEngine::rcp_static_cast<const SymEngine::Integer>(arg_diff)->as_int();	×
NEW 80	if (val > 0 && val < best) {	×
NEW 81	best = val;	×
NEW 82	}	×
NEW 83	}	×
NEW 84	}	×
NEW 85	return best;	×
NEW 86	}	×
87	// Should not reach here if is_constant_trip_bound returned true
NEW 88	return 0;	×
NEW 89	}	×
90
91	/// Check if a loop has a compound condition with at least one canonical bound.
92	static bool loop_is_peelable(structured_control_flow::StructuredLoop& loop) {	×
93	auto cond = loop.condition();	×
94	if (!SymEngine::is_a<SymEngine::And>(*cond)) {	×
95	return false;	×
96	}	×
97	auto and_cond = SymEngine::rcp_static_cast<const SymEngine::And>(cond);	×
98	auto& conjuncts = and_cond->get_container();	×
99	if (conjuncts.size() < 2) {	×
100	return false;	×
101	}	×
102
103	auto indvar = loop.indvar();	×
104	auto init = loop.init();	×
105	bool has_canonical = false;	×
106	bool has_dynamic = false;	×
107
108	for (auto& conjunct : conjuncts) {	×
109	auto bound = extract_upper_bound(conjunct, indvar);	×
110	if (bound == SymEngine::null) {	×
111	return false;	×
112	}	×
113	if (is_constant_trip_bound(bound, init)) {	×
114	has_canonical = true;	×
115	} else {	×
116	has_dynamic = true;	×
117	}	×
118	}	×
119	return has_canonical && has_dynamic;	×
120	}	×
121
122	/// For a peelable loop, extract the canonical bound (tightest constant-trip bound).
123	static symbolic::Expression find_canonical_bound(structured_control_flow::StructuredLoop& loop) {	×
124	auto cond = loop.condition();	×
125	auto and_cond = SymEngine::rcp_static_cast<const SymEngine::And>(cond);	×
126	auto& conjuncts = and_cond->get_container();	×
127	auto indvar = loop.indvar();	×
128	auto init = loop.init();	×
129
130	symbolic::Expression canonical = SymEngine::null;	×
NEW 131	int64_t canonical_trip = INT64_MAX;	×
132	for (auto& conjunct : conjuncts) {	×
133	auto bound = extract_upper_bound(conjunct, indvar);	×
134	if (bound == SymEngine::null) continue;	×
135	if (!is_constant_trip_bound(bound, init)) continue;	×
136
NEW 137	auto trip = get_constant_trip_count(bound, init);	×
NEW 138	if (canonical == SymEngine::null \|\| trip < canonical_trip) {	×
139	canonical = bound;	×
NEW 140	canonical_trip = trip;	×
141	}	×
142	}	×
143	return canonical;	×
144	}	×
145
146	/// Build the peeling condition for a single loop: canonical_bound <= each dynamic bound.
147	static symbolic::Condition build_loop_peeling_condition(
148	structured_control_flow::StructuredLoop& loop, const symbolic::Expression& canonical_bound
149	) {	×
150	auto cond = loop.condition();	×
151	auto and_cond = SymEngine::rcp_static_cast<const SymEngine::And>(cond);	×
152	auto& conjuncts = and_cond->get_container();	×
153	auto indvar = loop.indvar();	×
154	auto init = loop.init();	×
155
156	symbolic::Condition result = SymEngine::boolTrue;	×
157	for (auto& conjunct : conjuncts) {	×
158	auto bound = extract_upper_bound(conjunct, indvar);	×
159	if (bound == SymEngine::null) continue;	×
160	if (is_constant_trip_bound(bound, init) && symbolic::eq(bound, canonical_bound)) continue;	×
161	// canonical_bound <= this dynamic/looser bound
162	result = symbolic::And(result, symbolic::Le(canonical_bound, bound));	×
163	}	×
164
165	// If init is max(a, b, ...), we need to ensure the max resolves to the arg
166	// that gives the constant trip count. Add conditions: chosen_arg >= other_args.
NEW 167	if (SymEngine::is_a<SymEngine::Max>(*init)) {	×
NEW 168	auto max_op = SymEngine::rcp_static_cast<const SymEngine::Max>(init);	×
NEW 169	auto args = max_op->get_args();	×
170	// Find the arg that gives the constant trip (smallest constant trip)
NEW 171	symbolic::Expression chosen_arg = SymEngine::null;	×
NEW 172	int64_t best_trip = INT64_MAX;	×
NEW 173	for (auto& arg : args) {	×
NEW 174	auto arg_diff = symbolic::expand(symbolic::sub(canonical_bound, arg));	×
NEW 175	if (SymEngine::is_a<SymEngine::Integer>(*arg_diff)) {	×
NEW 176	auto val = SymEngine::rcp_static_cast<const SymEngine::Integer>(arg_diff)->as_int();	×
NEW 177	if (val > 0 && val < best_trip) {	×
NEW 178	best_trip = val;	×
NEW 179	chosen_arg = arg;	×
NEW 180	}	×
NEW 181	}	×
NEW 182	}	×
183	// Add conditions: chosen_arg >= each other arg (so max resolves to chosen_arg)
NEW 184	if (chosen_arg != SymEngine::null) {	×
NEW 185	for (auto& arg : args) {	×
NEW 186	if (!symbolic::eq(arg, chosen_arg)) {	×
NEW 187	result = symbolic::And(result, symbolic::Le(arg, chosen_arg));	×
NEW 188	}	×
NEW 189	}	×
NEW 190	}	×
NEW 191	}	×
192
193	return result;	×
194	}	×
195
196	/// Collect the perfectly nested chain of peelable loops starting from `loop`.
197	/// A chain continues as long as the loop body has exactly one child which is
198	/// another peelable structured loop.
199	static std::vector<structured_control_flow::StructuredLoop*> collect_peelable_nest(structured_control_flow::StructuredLoop&
200	loop) {	×
201	std::vector<structured_control_flow::StructuredLoop*> nest;	×
202	nest.push_back(&loop);	×
203
204	auto* current = &loop;	×
205	while (true) {	×
206	auto& body = current->root();	×
207	if (body.size() != 1) break;	×
208	auto& child = body.at(0).first;	×
209	auto* inner_loop = dynamic_cast<structured_control_flow::StructuredLoop*>(&child);	×
210	if (!inner_loop) break;	×
211	if (!loop_is_peelable(*inner_loop)) break;	×
212	nest.push_back(inner_loop);	×
213	current = inner_loop;	×
214	}	×
215	return nest;	×
216	}	×
217
218	bool LoopPeeling::can_be_applied(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	×
219	return loop_is_peelable(loop_);	×
220	};	×
221
222	void LoopPeeling::apply(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	×
223	auto& sdfg = builder.subject();	×
224
225	// Collect perfectly nested chain of peelable loops
226	auto nest = collect_peelable_nest(loop_);	×
227
228	// For each loop in the nest, find its canonical bound and build peeling condition
229	struct LoopPeelInfo {	×
230	structured_control_flow::StructuredLoop* loop;	×
231	symbolic::Expression canonical_bound;	×
232	symbolic::Condition peeling_condition;	×
233	};	×
234	std::vector<LoopPeelInfo> peel_infos;	×
235
236	symbolic::Condition combined_peeling_condition = SymEngine::boolTrue;	×
237	for (auto* loop : nest) {	×
238	auto canonical = find_canonical_bound(*loop);	×
239	auto peel_cond = build_loop_peeling_condition(*loop, canonical);	×
240	combined_peeling_condition = symbolic::And(combined_peeling_condition, peel_cond);	×
241	peel_infos.push_back({loop, canonical, peel_cond});	×
242	}	×
243
244	// Get parent scope of the outermost loop
245	auto& scope_analysis = analysis_manager.get<analysis::ScopeAnalysis>();	×
246	auto parent = static_cast<structured_control_flow::Sequence*>(scope_analysis.parent_scope(&loop_));	×
247
248	// Create IfElse before the outermost loop
249	auto& if_else = builder.add_if_else_before(*parent, loop_, {}, loop_.debug_info());	×
250
251	// === Then branch: all loops normalized to start at 0 with constant trip counts ===
252	auto& then_branch = builder.add_case(if_else, combined_peeling_condition);	×
253
254	// Build the nest of loops with clean 0-based bounds in the then branch
255	structured_control_flow::Sequence* current_parent = &then_branch;	×
256	// Track substitutions: original_indvar → indvar + init (for body fixup)
257	std::vector<std::pair<symbolic::Symbol, symbolic::Expression>> substitutions;	×
258
259	for (size_t i = 0; i < peel_infos.size(); i++) {	×
260	auto& info = peel_infos[i];	×
261	auto* loop = info.loop;	×
262	auto indvar = loop->indvar();	×
263	auto init = loop->init();	×
264
265	// Compute constant trip count: canonical_bound - init (using helper for max() cases)
NEW 266	auto trip_count = symbolic::integer(get_constant_trip_count(info.canonical_bound, init));	×
267
268	// Resolve effective init for the then-branch.
269	// If init = max(a, b, ...) and canonical_bound - b is the constant trip,
270	// then in the then-branch (where peeling condition guarantees max = b), use b directly.
NEW 271	symbolic::Expression effective_init = init;	×
NEW 272	if (SymEngine::is_a<SymEngine::Max>(*init)) {	×
NEW 273	auto max_op = SymEngine::rcp_static_cast<const SymEngine::Max>(init);	×
NEW 274	auto args = max_op->get_args();	×
NEW 275	int64_t best_trip = INT64_MAX;	×
NEW 276	for (auto& arg : args) {	×
NEW 277	auto arg_diff = symbolic::expand(symbolic::sub(info.canonical_bound, arg));	×
NEW 278	if (SymEngine::is_a<SymEngine::Integer>(*arg_diff)) {	×
NEW 279	auto val = SymEngine::rcp_static_cast<const SymEngine::Integer>(arg_diff)->as_int();	×
NEW 280	if (val > 0 && val < best_trip) {	×
NEW 281	best_trip = val;	×
NEW 282	effective_init = arg;	×
NEW 283	}	×
NEW 284	}	×
NEW 285	}	×
NEW 286	}	×
287
288	// New loop: indvar goes from 0 to trip_count
289	auto zero_condition = symbolic::Lt(indvar, trip_count);	×
290	auto zero_init = symbolic::integer(0);	×
291
292	structured_control_flow::StructuredLoop* new_loop = nullptr;	×
293	if (auto map = dynamic_cast<structured_control_flow::Map*>(loop)) {	×
294	new_loop = &builder.add_map(	×
295	*current_parent,	×
296	indvar,	×
297	zero_condition,	×
298	zero_init,	×
299	loop->update(),	×
300	map->schedule_type(),	×
301	{},	×
302	loop->debug_info()	×
303	);	×
304	} else {	×
305	new_loop =	×
306	&builder	×
307	.add_for(*current_parent, indvar, zero_condition, zero_init, loop->update(), {}, loop->debug_info());	×
308	}	×
309
310	// Record substitution: in the body, original indvar usage = new_indvar + effective_init
NEW 311	substitutions.push_back({indvar, effective_init});	×
312	current_parent = &new_loop->root();	×
313	}	×
314
315	// Deep copy the innermost loop's body into the new innermost loop
316	auto* innermost = nest.back();	×
317	deepcopy::StructuredSDFGDeepCopy main_copier(builder, *current_parent, innermost->root());	×
318	main_copier.insert();	×
319
320	// Apply shift substitutions in the copied body:
321	// Replace indvar with (indvar + original_init) so body accesses use correct offsets.
322	// Must apply outermost first (since inner body may reference outer indvars).
323	for (auto& [indvar, init] : substitutions) {	×
324	if (symbolic::eq(init, symbolic::zero())) continue;	×
325	auto shifted_expr = symbolic::add(indvar, init);	×
326	current_parent->replace(indvar, shifted_expr);	×
327	}	×
328
329	// === Else branch: original compound bounds (remainder) ===
330	auto else_condition = symbolic::Not(combined_peeling_condition);	×
331	auto& else_branch = builder.add_case(if_else, else_condition);	×
332
333	// Build the nest of loops with original conditions in the else branch
334	current_parent = &else_branch;	×
335	for (size_t i = 0; i < peel_infos.size(); i++) {	×
336	auto* loop = peel_infos[i].loop;	×
337
338	structured_control_flow::StructuredLoop* new_loop = nullptr;	×
339	if (auto map = dynamic_cast<structured_control_flow::Map*>(loop)) {	×
340	new_loop = &builder.add_map(	×
341	*current_parent,	×
342	loop->indvar(),	×
343	loop->condition(),	×
344	loop->init(),	×
345	loop->update(),	×
346	map->schedule_type(),	×
347	{},	×
348	loop->debug_info()	×
349	);	×
350	} else {	×
351	new_loop = &builder.add_for(	×
352	*current_parent, loop->indvar(), loop->condition(), loop->init(), loop->update(), {}, loop->debug_info()	×
353	);	×
354	}	×
355	current_parent = &new_loop->root();	×
356	}	×
357
358	// Deep copy the innermost loop's body into the remainder innermost loop
359	deepcopy::StructuredSDFGDeepCopy remainder_copier(builder, *current_parent, innermost->root());	×
360	remainder_copier.insert();	×
361
362	// Remove the original loop
363	builder.remove_child(*parent, parent->index(loop_));	×
364
365	analysis_manager.invalidate_all();	×
366	};	×
367
368	void LoopPeeling::to_json(nlohmann::json& j) const {	×
369	std::string loop_type;	×
370	if (dynamic_cast<structured_control_flow::For*>(&loop_)) {	×
371	loop_type = "for";	×
372	} else if (dynamic_cast<structured_control_flow::Map*>(&loop_)) {	×
373	loop_type = "map";	×
374	} else {	×
375	throw std::runtime_error("Unsupported loop type for serialization of loop: " + loop_.indvar()->get_name());	×
376	}	×
377
378	j["transformation_type"] = this->name();	×
379	j["subgraph"] = {{"0", {{"element_id", this->loop_.element_id()}, {"type", loop_type}}}};	×
380	};	×
381
382	LoopPeeling LoopPeeling::from_json(builder::StructuredSDFGBuilder& builder, const nlohmann::json& desc) {	×
383	auto loop_id = desc["subgraph"]["0"]["element_id"].get<size_t>();	×
384	auto element = builder.find_element_by_id(loop_id);	×
385	if (element == nullptr) {	×
386	throw InvalidTransformationDescriptionException("Element with ID " + std::to_string(loop_id) + " not found.");	×
387	}	×
388	auto loop = dynamic_cast<structured_control_flow::StructuredLoop*>(element);	×
389	if (loop == nullptr) {	×
390	throw InvalidTransformationDescriptionException(	×
391	"Element with ID " + std::to_string(loop_id) + " is not a StructuredLoop."	×
392	);	×
393	}	×
394
395	return LoopPeeling(*loop);	×
396	};	×
397
398	} // namespace transformations
399	} // namespace sdfg

daisytuner / docc / 25289367548

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