16525628849

Committed 25 Jul 2025 03:25PM UTC coverage: 65.266% (-0.05%) from 65.32%

Build # 16525628849

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #162 from daisytuner/transfer-tuning

Transfer tuning

Run Details

25 of 53 new or added lines in 6 files covered. (47.17%)

1 existing line in 1 file now uncovered.

8976 of 13753 relevant lines covered (65.27%)

125.53 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);

    // 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& body = this->loop_.root();
    auto& child = body.at(0).first;

    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;
    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()
            )
            .first;
    builder.insert(child, this->loop_.root(), new_map.root(), child.debug_info());

    // 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
63	// Check dependencies
64	for (auto& dep : dependencies) {	×
65	auto& container = dep.first;	×
66	if (child_users.uses(container).empty()) {	×
67	continue;	×
68	}
69	if (dep.second == analysis::LoopCarriedDependency::LOOP_CARRIED_DEPENDENCY_WRITE_WRITE) {	×
70	if (child_locals.find(container) != child_locals.end()) {	×
71	continue;	×
72	}
73	}	×
74
75	return false;	×
76	}
77
78	return true;	×
79	};	×
80
81	void LoopDistribute::apply(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	×
82	auto& sdfg = builder.subject();	×
83
84	auto indvar = this->loop_.indvar();	×
85	auto condition = this->loop_.condition();	×
86	auto update = this->loop_.update();	×
87	auto init = this->loop_.init();	×
88
89	auto& body = this->loop_.root();	×
90	auto& child = body.at(0).first;	×
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;	×
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 =	×
99	builder	×
100	.add_map_before(	×
101	*parent, this->loop_, indvar, condition, init, update, schedule_type, {}, this->loop_.debug_info()	×
102	)
103	.first;	×
104	builder.insert(child, this->loop_.root(), new_map.root(), child.debug_info());	×
105
106	// Replace indvar in new loop
107	std::string new_indvar = builder.find_new_name(indvar->get_name());	×
108	builder.add_container(new_indvar, sdfg.type(indvar->get_name()));	×
109	new_map.replace(indvar, symbolic::symbol(new_indvar));	×
110
111	analysis_manager.invalidate_all();	×
112	};	×
113
114	void LoopDistribute::to_json(nlohmann::json& j) const {	×
NEW 115	std::string loop_type;	×
NEW 116	if (dynamic_cast<structured_control_flow::For*>(&loop_)) {	×
NEW 117	loop_type = "for";	×
NEW 118	} else if (dynamic_cast<structured_control_flow::Map*>(&loop_)) {	×
NEW 119	loop_type = "map";	×
NEW 120	} else {	×
NEW 121	throw std::runtime_error("Unsupported loop type for serialization of loop: " + loop_.indvar()->get_name());	×
122	}
123
NEW 124	j["transformation_type"] = this->name();	×
NEW 125	j["subgraph"] = {{"0", {{"element_id", this->loop_.element_id()}, {"type", loop_type}}}};	×
126	j["transformation_type"] = this->name();	×
127	};	×
128
129	LoopDistribute LoopDistribute::from_json(builder::StructuredSDFGBuilder& builder, const nlohmann::json& desc) {	×
NEW 130	auto loop_id = desc["subgraph"]["0"]["element_id"].get<size_t>();	×
131	auto element = builder.find_element_by_id(loop_id);	×
132	if (element == nullptr) {	×
133	throw InvalidTransformationDescriptionException("Element with ID " + std::to_string(loop_id) + " not found.");	×
134	}
135	auto loop = dynamic_cast<structured_control_flow::StructuredLoop*>(element);	×
136	if (loop == nullptr) {	×
137	throw InvalidTransformationDescriptionException(	×
138	"Element with ID " + std::to_string(loop_id) + " is not a StructuredLoop."	×
139	);
140	}
141
142	return LoopDistribute(*loop);	×
143	};	×
144
145	} // namespace transformations
146	} // namespace sdfg

daisytuner / sdfglib / 16525628849

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