16141128586

Committed 08 Jul 2025 10:48AM UTC coverage: 64.71% (+0.3%) from 64.375%

Build # 16141128586

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #139 from daisytuner/loop-distribute

Switches loop distribute to new analyses and maps

Run Details

0 of 24 new or added lines in 1 file covered. (0.0%)

5 existing lines in 1 file now uncovered.

8578 of 13256 relevant lines covered (64.71%)

178.17 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 {
    j["transformation_type"] = this->name();
    j["loop_element_id"] = this->loop_.element_id();
};

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

    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
UNCOV 19	auto& body = this->loop_.root();	×
20	if (body.size() < 2) {	×
21	return false;	×
22	}
NEW 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
NEW 55	auto& analysis = analysis_manager.get<analysis::DataDependencyAnalysis>();	×
NEW 56	auto& dependencies = analysis.dependencies(this->loop_);	×
57
58	// collect child locals and child users
UNCOV 59	auto& users = analysis_manager.get<analysis::Users>();	×
NEW 60	analysis::UsersView child_users(users, child);	×
NEW 61	auto child_locals = users.locals(child);	×
62
63	// Check dependencies
64	for (auto& dep : dependencies) {	×
65	auto& container = dep.first;	×
NEW 66	if (child_users.uses(container).empty()) {	×
UNCOV 67	continue;	×
68	}
NEW 69	if (dep.second == analysis::LoopCarriedDependency::LOOP_CARRIED_DEPENDENCY_WRITE_WRITE) {	×
NEW 70	if (child_locals.find(container) != child_locals.end()) {	×
NEW 71	continue;	×
72	}
UNCOV 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();	×
NEW 90	auto& child = body.at(0).first;	×
91
NEW 92	auto& analysis = analysis_manager.get<analysis::ScopeAnalysis>();	×
NEW 93	auto parent = static_cast<structured_control_flow::Sequence*>(analysis.parent_scope(&this->loop_));	×
NEW 94	structured_control_flow::ScheduleType schedule_type = structured_control_flow::ScheduleType_Sequential;	×
NEW 95	if (auto map_stmt = dynamic_cast<structured_control_flow::Map*>(&this->loop_)) {	×
NEW 96	schedule_type = map_stmt->schedule_type();	×
UNCOV 97	}	×
NEW 98	auto& new_map =	×
NEW 99	builder	×
NEW 100	.add_map_before(	×
NEW 101	*parent, this->loop_, indvar, condition, init, update, schedule_type, {}, this->loop_.debug_info()	×
102	)
NEW 103	.first;	×
NEW 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()));	×
NEW 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 {	×
115	j["transformation_type"] = this->name();	×
NEW 116	j["loop_element_id"] = this->loop_.element_id();	×
117	};	×
118
119	LoopDistribute LoopDistribute::from_json(builder::StructuredSDFGBuilder& builder, const nlohmann::json& desc) {	×
120	auto loop_id = desc["loop_element_id"].get<size_t>();	×
121	auto element = builder.find_element_by_id(loop_id);	×
122	if (!element) {	×
123	throw InvalidTransformationDescriptionException("Element with ID " + std::to_string(loop_id) + " not found.");	×
124	}
NEW 125	auto loop = dynamic_cast<structured_control_flow::StructuredLoop*>(element);	×
126
127	return LoopDistribute(*loop);	×
128	};	×
129
130	} // namespace transformations
131	} // namespace sdfg

daisytuner / sdfglib / 16141128586

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