20141104835

Committed 11 Dec 2025 05:03PM UTC coverage: 40.351% (-0.03%) from 40.379%

Build # 20141104835

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #387 from daisytuner/cleanup

Minor improvements in symbolic analysis

Run Details

13653 of 43801 branches covered (31.17%)

Branch coverage included in aggregate %.

10 of 17 new or added lines in 4 files covered. (58.82%)

6 existing lines in 4 files now uncovered.

11688 of 19000 relevant lines covered (61.52%)

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

daisytuner / sdfglib / 20141104835

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