25436733018

Committed 06 May 2026 12:59PM UTC coverage: 65.227% (+0.004%) from 65.223%

Build # 25436733018

Build Type

Pull #681

github

Committed by

web-flow

Commit Message

Merge e31167aa2 into 84dc11a09

Pull Request Pull Request #681: Target specific expand

Coverage Stats

55 of 59 new or added lines in 3 files covered. (93.22%)

27 existing lines in 2 files now uncovered.

31624 of 48483 relevant lines covered (65.23%)

2351.88 hits per line

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

85.54

/opt/src/transformations/loop_distribute.cpp

#include "sdfg/transformations/loop_distribute.h"

#include "sdfg/analysis/data_dependency_analysis.h"
#include "sdfg/analysis/scope_analysis.h"
#include "sdfg/deepcopy/structured_sdfg_deep_copy.h"

namespace sdfg {
namespace transformations {

LoopDistribute::LoopDistribute(structured_control_flow::StructuredLoop& loop)
    : loop_(loop) {

      };

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

bool LoopDistribute::can_be_applied(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {
    // We distribute each child at a time
    auto& body = this->loop_.root();
    if (body.size() < 2) {
        return false;
    }
    auto& child = body.at(0).first;
    // Criterion: Only dataflow
    if (!body.at(0).second.assignments().empty()) {
        return false;
    }

    // Criterion: Child does not write to loop-local containers
    /**
     * Positive example:
     * A = ...;
     * ...
     * for (i = 0; i < 10; i++) {
     *  // child 0
     *  A[i] = 0;
     *  // child 1..n
     *  ... (uses A[i])
     * }
     *
     * Negative example:
     * for (i = 0; i < 10; i++) {
     *  // child 0
     *  double a = 0;
     *  // child 1..n
     *  ... (uses a)
     * }
     */

    // Criterion: If dependency exists, then it is
    // a) a child-local WAW, we can ignore it
    // b) is not used by child at all

    // collect dependencies
    analysis::DataDependencyAnalysis analysis(builder.subject(), true);
    analysis.run(analysis_manager);
    auto& dependencies = analysis.dependencies(this->loop_);

    // collect child locals and child users
    auto& users = analysis_manager.get<analysis::Users>();
    analysis::UsersView child_users(users, child);
    auto child_locals = users.locals(child);
    if (!child_users.views().empty() || !child_users.moves().empty()) {
        return false;
    }

    // Check dependencies
    for (auto& dep : dependencies) {
        auto& container = dep.first;
        if (child_users.uses(container).empty()) {
            continue;
        }
        if (dep.second.type == analysis::LoopCarriedDependency::LOOP_CARRIED_DEPENDENCY_WRITE_WRITE) {
            if (child_locals.find(container) != child_locals.end()) {
                continue;
            }
        }

        return false;
    }

    return true;
};

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

    auto indvar = this->loop_.indvar();
    auto condition = this->loop_.condition();
    auto update = this->loop_.update();
    auto init = this->loop_.init();

    auto& analysis = analysis_manager.get<analysis::ScopeAnalysis>();
    auto parent = static_cast<structured_control_flow::Sequence*>(analysis.parent_scope(&this->loop_));
    structured_control_flow::ScheduleType schedule_type = structured_control_flow::ScheduleType_Sequential::create();
    if (auto map_stmt = dynamic_cast<structured_control_flow::Map*>(&this->loop_)) {
        schedule_type = map_stmt->schedule_type();
    }
    auto& new_map = builder.add_map_before(
        *parent, this->loop_, indvar, condition, init, update, schedule_type, {}, this->loop_.debug_info()
    );
    builder.move_child(this->loop_.root(), 0, new_map.root());

    // Replace indvar in new loop
    std::string new_indvar = builder.find_new_name(indvar->get_name());
    builder.add_container(new_indvar, sdfg.type(indvar->get_name()));
    new_map.replace(indvar, symbolic::symbol(new_indvar));

    analysis_manager.invalidate_all();
};

void LoopDistribute::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}}}};
    j["transformation_type"] = this->name();
};

LoopDistribute LoopDistribute::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 LoopDistribute(*loop);
};

} // namespace transformations
} // namespace sdfg

1	#include "sdfg/transformations/loop_distribute.h"
2
3	#include "sdfg/analysis/data_dependency_analysis.h"
4	#include "sdfg/analysis/scope_analysis.h"
5	#include "sdfg/deepcopy/structured_sdfg_deep_copy.h"
6
7	namespace sdfg {
8	namespace transformations {
9
10	LoopDistribute::LoopDistribute(structured_control_flow::StructuredLoop& loop)
11	: loop_(loop) {	106✔
12
13	};	106✔
14
15	std::string LoopDistribute::name() const { return "LoopDistribute"; };	7✔
16
17	bool LoopDistribute::can_be_applied(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	59✔
18	// We distribute each child at a time
19	auto& body = this->loop_.root();	59✔
20	if (body.size() < 2) {	59✔
21	return false;	1✔
22	}	1✔
23	auto& child = body.at(0).first;	58✔
24	// Criterion: Only dataflow
25	if (!body.at(0).second.assignments().empty()) {	58✔
26	return false;	×
27	}	×
28
29	// Criterion: Child does not write to loop-local containers
30	/**
31	* Positive example:
32	* A = ...;
33	* ...
34	* for (i = 0; i < 10; i++) {
35	* // child 0
36	* A[i] = 0;
37	* // child 1..n
38	* ... (uses A[i])
39	* }
40	*
41	* Negative example:
42	* for (i = 0; i < 10; i++) {
43	* // child 0
44	* double a = 0;
45	* // child 1..n
46	* ... (uses a)
47	* }
48	*/
49
50	// Criterion: If dependency exists, then it is
51	// a) a child-local WAW, we can ignore it
52	// b) is not used by child at all
53
54	// collect dependencies
55	analysis::DataDependencyAnalysis analysis(builder.subject(), true);	58✔
56	analysis.run(analysis_manager);	58✔
57	auto& dependencies = analysis.dependencies(this->loop_);	58✔
58
59	// collect child locals and child users
60	auto& users = analysis_manager.get<analysis::Users>();	58✔
61	analysis::UsersView child_users(users, child);	58✔
62	auto child_locals = users.locals(child);	58✔
63	if (!child_users.views().empty() \|\| !child_users.moves().empty()) {	58✔
UNCOV 64	return false;	×
UNCOV 65	}	×
66
67	// Check dependencies
68	for (auto& dep : dependencies) {	184✔
69	auto& container = dep.first;	184✔
70	if (child_users.uses(container).empty()) {	184✔
71	continue;	116✔
72	}	116✔
73	if (dep.second.type == analysis::LoopCarriedDependency::LOOP_CARRIED_DEPENDENCY_WRITE_WRITE) {	68✔
74	if (child_locals.find(container) != child_locals.end()) {	60✔
75	continue;	54✔
76	}	54✔
77	}	60✔
78
79	return false;	14✔
80	}	68✔
81
82	return true;	44✔
83	};	58✔
84
85	void LoopDistribute::apply(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	44✔
86	auto& sdfg = builder.subject();	44✔
87
88	auto indvar = this->loop_.indvar();	44✔
89	auto condition = this->loop_.condition();	44✔
90	auto update = this->loop_.update();	44✔
91	auto init = this->loop_.init();	44✔
92
93	auto& analysis = analysis_manager.get<analysis::ScopeAnalysis>();	44✔
94	auto parent = static_cast<structured_control_flow::Sequence*>(analysis.parent_scope(&this->loop_));	44✔
95	structured_control_flow::ScheduleType schedule_type = structured_control_flow::ScheduleType_Sequential::create();	44✔
96	if (auto map_stmt = dynamic_cast<structured_control_flow::Map*>(&this->loop_)) {	44✔
97	schedule_type = map_stmt->schedule_type();	27✔
98	}	27✔
99	auto& new_map = builder.add_map_before(	44✔
100	*parent, this->loop_, indvar, condition, init, update, schedule_type, {}, this->loop_.debug_info()	44✔
101	);	44✔
102	builder.move_child(this->loop_.root(), 0, new_map.root());	44✔
103
104	// Replace indvar in new loop
105	std::string new_indvar = builder.find_new_name(indvar->get_name());	44✔
106	builder.add_container(new_indvar, sdfg.type(indvar->get_name()));	44✔
107	new_map.replace(indvar, symbolic::symbol(new_indvar));	44✔
108
109	analysis_manager.invalidate_all();	44✔
110	};	44✔
111
112	void LoopDistribute::to_json(nlohmann::json& j) const {	2✔
113	std::string loop_type;	2✔
114	if (dynamic_cast<structured_control_flow::For*>(&loop_)) {	2✔
115	loop_type = "for";	1✔
116	} else if (dynamic_cast<structured_control_flow::Map*>(&loop_)) {	1✔
117	loop_type = "map";	1✔
118	} else {	1✔
UNCOV 119	throw std::runtime_error("Unsupported loop type for serialization of loop: " + loop_.indvar()->get_name());	×
UNCOV 120	}	×
121
122	j["transformation_type"] = this->name();	2✔
123	j["subgraph"] = {{"0", {{"element_id", this->loop_.element_id()}, {"type", loop_type}}}};	2✔
124	j["transformation_type"] = this->name();	2✔
125	};	2✔
126
127	LoopDistribute LoopDistribute::from_json(builder::StructuredSDFGBuilder& builder, const nlohmann::json& desc) {	2✔
128	auto loop_id = desc["subgraph"]["0"]["element_id"].get<size_t>();	2✔
129	auto element = builder.find_element_by_id(loop_id);	2✔
130	if (element == nullptr) {	2✔
UNCOV 131	throw InvalidTransformationDescriptionException("Element with ID " + std::to_string(loop_id) + " not found.");	×
UNCOV 132	}	×
133	auto loop = dynamic_cast<structured_control_flow::StructuredLoop*>(element);	2✔
134	if (loop == nullptr) {	2✔
135	throw InvalidTransformationDescriptionException(	×
UNCOV 136	"Element with ID " + std::to_string(loop_id) + " is not a StructuredLoop."	×
UNCOV 137	);	×
138	}	×
139
140	return LoopDistribute(*loop);	2✔
141	};	2✔
142
143	} // namespace transformations
144	} // namespace sdfg

daisytuner / docc / 25436733018

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