17621055299

Committed 10 Sep 2025 05:00PM UTC coverage: 59.755% (+0.6%) from 59.145%

Build # 17621055299

Build Type

Pull #210

github

Committed by

web-flow

Commit Message

Merge 6e7cc1401 into b8fdeb232

Pull Request Pull Request #210: New debug info

Run Details

777 of 1111 new or added lines in 46 files covered. (69.94%)

11 existing lines in 11 files now uncovered.

9755 of 16325 relevant lines covered (59.75%)

115.06 hits per line

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

0.0

/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
    auto& analysis = analysis_manager.get<analysis::DataDependencyAnalysis>();
    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 == 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,
        {},
        builder.debug_info().get_region(this->loop_.debug_info().indices())
    );
    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) {	×
12
13	};	×
14
15	std::string LoopDistribute::name() const { return "LoopDistribute"; };	×
16
17	bool LoopDistribute::can_be_applied(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	×
18	// We distribute each child at a time
19	auto& body = this->loop_.root();	×
20	if (body.size() < 2) {	×
21	return false;	×
22	}
23	auto& child = body.at(0).first;	×
24	// Criterion: Only dataflow
25	if (!body.at(0).second.assignments().empty()) {	×
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	auto& analysis = analysis_manager.get<analysis::DataDependencyAnalysis>();	×
56	auto& dependencies = analysis.dependencies(this->loop_);	×
57
58	// collect child locals and child users
59	auto& users = analysis_manager.get<analysis::Users>();	×
60	analysis::UsersView child_users(users, child);	×
61	auto child_locals = users.locals(child);	×
62	if (!child_users.views().empty() \|\| !child_users.moves().empty()) {	×
63	return false;	×
64	}
65
66	// Check dependencies
67	for (auto& dep : dependencies) {	×
68	auto& container = dep.first;	×
69	if (child_users.uses(container).empty()) {	×
70	continue;	×
71	}
72	if (dep.second == analysis::LoopCarriedDependency::LOOP_CARRIED_DEPENDENCY_WRITE_WRITE) {	×
73	if (child_locals.find(container) != child_locals.end()) {	×
74	continue;	×
75	}
76	}	×
77
78	return false;	×
79	}
80
81	return true;	×
82	};	×
83
84	void LoopDistribute::apply(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	×
85	auto& sdfg = builder.subject();	×
86
87	auto indvar = this->loop_.indvar();	×
88	auto condition = this->loop_.condition();	×
89	auto update = this->loop_.update();	×
90	auto init = this->loop_.init();	×
91
92	auto& analysis = analysis_manager.get<analysis::ScopeAnalysis>();	×
93	auto parent = static_cast<structured_control_flow::Sequence*>(analysis.parent_scope(&this->loop_));	×
94	structured_control_flow::ScheduleType schedule_type = structured_control_flow::ScheduleType_Sequential::create();	×
95	if (auto map_stmt = dynamic_cast<structured_control_flow::Map*>(&this->loop_)) {	×
96	schedule_type = map_stmt->schedule_type();	×
97	}	×
98	auto& new_map = builder.add_map_before(	×
NEW 99	*parent,	×
NEW 100	this->loop_,	×
101	indvar,
102	condition,
103	init,
104	update,
105	schedule_type,
NEW 106	{},	×
NEW 107	builder.debug_info().get_region(this->loop_.debug_info().indices())	×
108	);
109	builder.move_child(this->loop_.root(), 0, new_map.root());	×
110
111	// Replace indvar in new loop
112	std::string new_indvar = builder.find_new_name(indvar->get_name());	×
113	builder.add_container(new_indvar, sdfg.type(indvar->get_name()));	×
114	new_map.replace(indvar, symbolic::symbol(new_indvar));	×
115
116	analysis_manager.invalidate_all();	×
117	};	×
118
119	void LoopDistribute::to_json(nlohmann::json& j) const {	×
120	std::string loop_type;	×
121	if (dynamic_cast<structured_control_flow::For*>(&loop_)) {	×
122	loop_type = "for";	×
123	} else if (dynamic_cast<structured_control_flow::Map*>(&loop_)) {	×
124	loop_type = "map";	×
125	} else {	×
126	throw std::runtime_error("Unsupported loop type for serialization of loop: " + loop_.indvar()->get_name());	×
127	}
128
129	j["transformation_type"] = this->name();	×
130	j["subgraph"] = {{"0", {{"element_id", this->loop_.element_id()}, {"type", loop_type}}}};	×
131	j["transformation_type"] = this->name();	×
132	};	×
133
134	LoopDistribute LoopDistribute::from_json(builder::StructuredSDFGBuilder& builder, const nlohmann::json& desc) {	×
135	auto loop_id = desc["subgraph"]["0"]["element_id"].get<size_t>();	×
136	auto element = builder.find_element_by_id(loop_id);	×
137	if (element == nullptr) {	×
138	throw InvalidTransformationDescriptionException("Element with ID " + std::to_string(loop_id) + " not found.");	×
139	}
140	auto loop = dynamic_cast<structured_control_flow::StructuredLoop*>(element);	×
141	if (loop == nullptr) {	×
142	throw InvalidTransformationDescriptionException(	×
143	"Element with ID " + std::to_string(loop_id) + " is not a StructuredLoop."	×
144	);
145	}
146
147	return LoopDistribute(*loop);	×
148	};	×
149
150	} // namespace transformations
151	} // namespace sdfg

daisytuner / sdfglib / 17621055299

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