28188098396

Committed 25 Jun 2026 05:21PM UTC coverage: 61.746% (+0.1%) from 61.644%

Build # 28188098396

Build Type

Pull #802

github

Committed by

web-flow

Commit Message

Merge 08b5c3f1d into fe9abd1cb

Pull Request Pull Request #802: adds reduce as new structured loop type

Coverage Stats

705 of 985 new or added lines in 34 files covered. (71.57%)

5 existing lines in 4 files now uncovered.

38839 of 62901 relevant lines covered (61.75%)

978.2 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/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 parent = static_cast<structured_control_flow::Sequence*>(loop_.get_parent());

    // 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 if (auto reduce = dynamic_cast<structured_control_flow::Reduce*>(loop)) {
            new_loop = &builder.add_reduce(
                *current_parent,
                indvar,
                zero_condition,
                zero_init,
                loop->update(),
                reduce->reductions(),
                loop->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 if (auto reduce = dynamic_cast<structured_control_flow::Reduce*>(loop)) {
            new_loop = &builder.add_reduce(
                *current_parent,
                loop->indvar(),
                loop->condition(),
                loop->init(),
                loop->update(),
                reduce->reductions(),
                loop->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 {
    j["transformation_type"] = this->name();
    j["parameters"] = nlohmann::json::object();

    serializer::JSONSerializer ser_flat(false);
    j["subgraph"] = nlohmann::json::object();
    j["subgraph"]["0"] = nlohmann::json::object();
    ser_flat.serialize_node(j["subgraph"]["0"], loop_);
};

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

daisytuner / docc / 28188098396

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