17396811834

Committed 02 Sep 2025 07:43AM UTC coverage: 59.027% (+0.05%) from 58.982%

Build # 17396811834

Build Type

Pull #217

github

Committed by

web-flow

Commit Message

Merge bbbb6c82f into fd4755975

Pull Request Pull Request #217: Several fixes for better auto-parallelization

Run Details

5 of 20 new or added lines in 3 files covered. (25.0%)

9207 of 15598 relevant lines covered (59.03%)

116.0 hits per line

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

61.7

/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 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)	8✔
14	: visitor::StructuredSDFGVisitor(builder, analysis_manager) {	8✔
15
16	};	8✔
17
18	bool For2Map::can_be_applied(structured_control_flow::For& for_stmt, analysis::AnalysisManager& analysis_manager) {	8✔
19	// Criterion: Loop must not have dereference memlets
20	auto& users = analysis_manager.get<analysis::Users>();	8✔
21	analysis::UsersView users_view(users, for_stmt);	8✔
22	for (auto& move : users_view.moves()) {	8✔
NEW 23	auto element = move->element();	×
NEW 24	if (auto node = dynamic_cast<data_flow::AccessNode*>(element)) {	×
NEW 25	auto& parent = node->get_parent();	×
NEW 26	for (auto& iedge : parent.in_edges(*node)) {	×
NEW 27	if (iedge.type() == data_flow::MemletType::Dereference_Src) {	×
NEW 28	return false;	×
29	}
30	}
NEW 31	}	×
32	}
33	for (auto& view : users_view.views()) {	8✔
NEW 34	auto element = view->element();	×
NEW 35	if (auto node = dynamic_cast<data_flow::AccessNode*>(element)) {	×
NEW 36	auto& parent = node->get_parent();	×
NEW 37	for (auto& iedge : parent.out_edges(*node)) {	×
NEW 38	if (iedge.type() == data_flow::MemletType::Dereference_Dst) {	×
NEW 39	return false;	×
40	}
41	}
NEW 42	}	×
43	}
44
45	// Criterion: loop must be data-parallel w.r.t containers
46	auto& data_dependency_analysis = analysis_manager.get<analysis::DataDependencyAnalysis>();	8✔
47	auto dependencies = data_dependency_analysis.dependencies(for_stmt);	8✔
48
49	// a. No true dependencies (RAW) between iterations
50	for (auto& dep : dependencies) {	9✔
51	if (dep.second == analysis::LoopCarriedDependency::LOOP_CARRIED_DEPENDENCY_READ_WRITE) {	1✔
52	return false;	×
53	}
54	}
55
56	// b. False dependencies (WAW) are limited to loop-local variables
57	auto locals = users.locals(for_stmt.root());	8✔
58	for (auto& dep : dependencies) {	9✔
59	auto& container = dep.first;	1✔
60	if (locals.find(container) == locals.end()) {	1✔
61	return false;	×
62	}
63	}
64
65	// c. indvar not used after for
66	if (locals.find(for_stmt.indvar()->get_name()) != locals.end()) {	8✔
67	return false;	×
68	}
69
70	return true;	8✔
71	}	8✔
72
73	void For2Map::apply(	8✔
74	structured_control_flow::For& for_stmt,
75	builder::StructuredSDFGBuilder& builder,
76	analysis::AnalysisManager& analysis_manager
77	) {
78	auto& scope_analysis = analysis_manager.get<analysis::ScopeAnalysis>();	8✔
79	auto parent = static_cast<structured_control_flow::Sequence*>(scope_analysis.parent_scope(&for_stmt));	8✔
80
81	// convert for to map
82	builder.convert_for(*parent, for_stmt);	8✔
83	}	8✔
84
85	bool For2Map::accept(structured_control_flow::For& node) {	8✔
86	if (!this->can_be_applied(node, analysis_manager_)) {	8✔
87	return false;	×
88	}
89
90	this->apply(node, builder_, analysis_manager_);	8✔
91	return true;	8✔
92	}	8✔
93
94	} // namespace passes
95	} // namespace sdfg

daisytuner / sdfglib / 17396811834

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