17656823807

Committed 11 Sep 2025 08:42PM UTC coverage: 60.447% (+1.1%) from 59.335%

Build # 17656823807

Build Type

Pull #219

github

Committed by

web-flow

Commit Message

Merge d5416236f into 6c1992b40

Pull Request Pull Request #219: stdlib Library Nodes and ConstantNodes

Run Details

460 of 1635 new or added lines in 81 files covered. (28.13%)

93 existing lines in 35 files now uncovered.

9385 of 15526 relevant lines covered (60.45%)

107.21 hits per line

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

68.42

/src/passes/structured_control_flow/for2map.cpp

#include "sdfg/passes/structured_control_flow/for2map.h"

#include "sdfg/analysis/assumptions_analysis.h"
#include "sdfg/analysis/data_dependency_analysis.h"
#include "sdfg/analysis/loop_analysis.h"
#include "sdfg/analysis/scope_analysis.h"
#include "sdfg/analysis/users.h"
#include "sdfg/passes/pipeline.h"

namespace sdfg {
namespace passes {

For2Map::For2Map(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager)
    : visitor::StructuredSDFGVisitor(builder, analysis_manager) {

      };

bool For2Map::can_be_applied(structured_control_flow::For& for_stmt, analysis::AnalysisManager& analysis_manager) {
    // Criterion: Loop must not have dereference memlets
    auto& users = analysis_manager.get<analysis::Users>();
    analysis::UsersView users_view(users, for_stmt);
    for (auto& move : users_view.moves()) {
        auto element = move->element();
        if (auto node = dynamic_cast<data_flow::AccessNode*>(element)) {
            auto& parent = node->get_parent();
            for (auto& iedge : parent.in_edges(*node)) {
                if (iedge.type() == data_flow::MemletType::Dereference_Src) {
                    return false;
                }
            }
        }
    }
    for (auto& view : users_view.views()) {
        auto element = view->element();
        if (auto node = dynamic_cast<data_flow::AccessNode*>(element)) {
            auto& parent = node->get_parent();
            for (auto& iedge : parent.out_edges(*node)) {
                if (iedge.type() == data_flow::MemletType::Dereference_Dst) {
                    return false;
                }
            }
        }
    }

    // Criterion: Loop must not have side-effecting body
    std::list<const structured_control_flow::ControlFlowNode*> queue = {&for_stmt.root()};
    while (!queue.empty()) {
        auto current = queue.front();
        queue.pop_front();

        if (auto block = dynamic_cast<const structured_control_flow::Block*>(current)) {
            for (auto& node : block->dataflow().nodes()) {
                if (auto library_node = dynamic_cast<const data_flow::LibraryNode*>(&node)) {
                    if (library_node->side_effect()) {
                        return false;
                    }
                }
            }
        } else if (auto seq = dynamic_cast<const structured_control_flow::Sequence*>(current)) {
            for (size_t i = 0; i < seq->size(); i++) {
                auto& child = seq->at(i).first;
                queue.push_back(&child);
            }
        } else if (auto ifelse = dynamic_cast<const structured_control_flow::IfElse*>(current)) {
            for (size_t i = 0; i < ifelse->size(); i++) {
                auto& branch = ifelse->at(i).first;
                queue.push_back(&branch);
            }
        } else if (auto loop = dynamic_cast<const structured_control_flow::StructuredLoop*>(current)) {
            queue.push_back(&loop->root());
        } else if (auto while_stmt = dynamic_cast<const structured_control_flow::While*>(current)) {
            queue.push_back(&while_stmt->root());
        } else if (auto for_stmt = dynamic_cast<const structured_control_flow::Break*>(current)) {
            // Do nothing
        } else if (auto for_stmt = dynamic_cast<const structured_control_flow::Continue*>(current)) {
            // Do nothing
        } else if (auto for_stmt = dynamic_cast<const structured_control_flow::Return*>(current)) {
            return false;
        } else {
            throw InvalidSDFGException("Unknown control flow node type in For2Map pass.");
        }
    }

    // Criterion: loop must be data-parallel w.r.t containers
    auto& data_dependency_analysis = analysis_manager.get<analysis::DataDependencyAnalysis>();
    auto dependencies = data_dependency_analysis.dependencies(for_stmt);

    // a. No true dependencies (RAW) between iterations
    for (auto& dep : dependencies) {
        if (dep.second == analysis::LoopCarriedDependency::LOOP_CARRIED_DEPENDENCY_READ_WRITE) {
            return false;
        }
    }

    // b. False dependencies (WAW) are limited to loop-local variables
    auto locals = users.locals(for_stmt.root());
    for (auto& dep : dependencies) {
        auto& container = dep.first;
        if (locals.find(container) == locals.end()) {
            return false;
        }
    }

    // c. indvar not used after for
    if (locals.find(for_stmt.indvar()->get_name()) != locals.end()) {
        return false;
    }

    return true;
}

void For2Map::apply(
    structured_control_flow::For& for_stmt,
    builder::StructuredSDFGBuilder& builder,
    analysis::AnalysisManager& analysis_manager
) {
    auto& scope_analysis = analysis_manager.get<analysis::ScopeAnalysis>();
    auto parent = static_cast<structured_control_flow::Sequence*>(scope_analysis.parent_scope(&for_stmt));

    // convert for to map
    builder.convert_for(*parent, for_stmt);
}

bool For2Map::accept(structured_control_flow::For& node) {
    if (!this->can_be_applied(node, analysis_manager_)) {
        return false;
    }

    this->apply(node, builder_, analysis_manager_);
    return true;
}

} // namespace passes
} // namespace sdfg

1	#include "sdfg/passes/structured_control_flow/for2map.h"
2
3	#include "sdfg/analysis/assumptions_analysis.h"
4	#include "sdfg/analysis/data_dependency_analysis.h"
5	#include "sdfg/analysis/loop_analysis.h"
6	#include "sdfg/analysis/scope_analysis.h"
7	#include "sdfg/analysis/users.h"
8	#include "sdfg/passes/pipeline.h"
9
10	namespace sdfg {
11	namespace passes {
12
13	For2Map::For2Map(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager)	9✔
14	: visitor::StructuredSDFGVisitor(builder, analysis_manager) {	9✔
15
16	};	9✔
17
18	bool For2Map::can_be_applied(structured_control_flow::For& for_stmt, analysis::AnalysisManager& analysis_manager) {	9✔
19	// Criterion: Loop must not have dereference memlets
20	auto& users = analysis_manager.get<analysis::Users>();	9✔
21	analysis::UsersView users_view(users, for_stmt);	9✔
22	for (auto& move : users_view.moves()) {	10✔
23	auto element = move->element();	1✔
24	if (auto node = dynamic_cast<data_flow::AccessNode*>(element)) {	1✔
25	auto& parent = node->get_parent();	1✔
26	for (auto& iedge : parent.in_edges(*node)) {	1✔
27	if (iedge.type() == data_flow::MemletType::Dereference_Src) {	1✔
28	return false;	1✔
29	}
30	}
31	}	×
32	}
33	for (auto& view : users_view.views()) {	8✔
34	auto element = view->element();	×
35	if (auto node = dynamic_cast<data_flow::AccessNode*>(element)) {	×
36	auto& parent = node->get_parent();	×
37	for (auto& iedge : parent.out_edges(*node)) {	×
38	if (iedge.type() == data_flow::MemletType::Dereference_Dst) {	×
39	return false;	×
40	}
41	}
42	}	×
43	}
44
45	// Criterion: Loop must not have side-effecting body
46	std::list<const structured_control_flow::ControlFlowNode*> queue = {&for_stmt.root()};	8✔
47	while (!queue.empty()) {	26✔
48	auto current = queue.front();	18✔
49	queue.pop_front();	18✔
50
51	if (auto block = dynamic_cast<const structured_control_flow::Block*>(current)) {	18✔
52	for (auto& node : block->dataflow().nodes()) {	34✔
53	if (auto library_node = dynamic_cast<const data_flow::LibraryNode*>(&node)) {	26✔
NEW 54	if (library_node->side_effect()) {	×
NEW 55	return false;	×
56	}
NEW 57	}	×
58	}
59	} else if (auto seq = dynamic_cast<const structured_control_flow::Sequence*>(current)) {	18✔
60	for (size_t i = 0; i < seq->size(); i++) {	18✔
61	auto& child = seq->at(i).first;	9✔
62	queue.push_back(&child);	9✔
63	}	9✔
64	} else if (auto ifelse = dynamic_cast<const structured_control_flow::IfElse*>(current)) {	10✔
NEW 65	for (size_t i = 0; i < ifelse->size(); i++) {	×
NEW 66	auto& branch = ifelse->at(i).first;	×
NEW 67	queue.push_back(&branch);	×
NEW 68	}	×
69	} else if (auto loop = dynamic_cast<const structured_control_flow::StructuredLoop*>(current)) {	1✔
70	queue.push_back(&loop->root());	1✔
71	} else if (auto while_stmt = dynamic_cast<const structured_control_flow::While*>(current)) {	1✔
NEW 72	queue.push_back(&while_stmt->root());	×
NEW 73	} else if (auto for_stmt = dynamic_cast<const structured_control_flow::Break*>(current)) {	×
74	// Do nothing
NEW 75	} else if (auto for_stmt = dynamic_cast<const structured_control_flow::Continue*>(current)) {	×
76	// Do nothing
NEW 77	} else if (auto for_stmt = dynamic_cast<const structured_control_flow::Return*>(current)) {	×
NEW 78	return false;	×
79	} else {
NEW 80	throw InvalidSDFGException("Unknown control flow node type in For2Map pass.");	×
81	}
82	}
83
84	// Criterion: loop must be data-parallel w.r.t containers
85	auto& data_dependency_analysis = analysis_manager.get<analysis::DataDependencyAnalysis>();	8✔
86	auto dependencies = data_dependency_analysis.dependencies(for_stmt);	8✔
87
88	// a. No true dependencies (RAW) between iterations
89	for (auto& dep : dependencies) {	9✔
90	if (dep.second == analysis::LoopCarriedDependency::LOOP_CARRIED_DEPENDENCY_READ_WRITE) {	1✔
91	return false;	×
92	}
93	}
94
95	// b. False dependencies (WAW) are limited to loop-local variables
96	auto locals = users.locals(for_stmt.root());	8✔
97	for (auto& dep : dependencies) {	9✔
98	auto& container = dep.first;	1✔
99	if (locals.find(container) == locals.end()) {	1✔
100	return false;	×
101	}
102	}
103
104	// c. indvar not used after for
105	if (locals.find(for_stmt.indvar()->get_name()) != locals.end()) {	8✔
106	return false;	×
107	}
108
109	return true;	8✔
110	}	9✔
111
112	void For2Map::apply(	8✔
113	structured_control_flow::For& for_stmt,
114	builder::StructuredSDFGBuilder& builder,
115	analysis::AnalysisManager& analysis_manager
116	) {
117	auto& scope_analysis = analysis_manager.get<analysis::ScopeAnalysis>();	8✔
118	auto parent = static_cast<structured_control_flow::Sequence*>(scope_analysis.parent_scope(&for_stmt));	8✔
119
120	// convert for to map
121	builder.convert_for(*parent, for_stmt);	8✔
122	}	8✔
123
124	bool For2Map::accept(structured_control_flow::For& node) {	9✔
125	if (!this->can_be_applied(node, analysis_manager_)) {	9✔
126	return false;	1✔
127	}
128
129	this->apply(node, builder_, analysis_manager_);	8✔
130	return true;	8✔
131	}	9✔
132
133	} // namespace passes
134	} // namespace sdfg

daisytuner / sdfglib / 17656823807

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