20263852258

Committed 16 Dec 2025 09:58AM UTC coverage: 40.086% (-0.2%) from 40.252%

Build # 20263852258

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #392 from daisytuner/for2map-performance

refactors passes to improve performance

Run Details

13621 of 43972 branches covered (30.98%)

Branch coverage included in aggregate %.

126 of 173 new or added lines in 14 files covered. (72.83%)

55 existing lines in 8 files now uncovered.

11633 of 19027 relevant lines covered (61.14%)

90.79 hits per line

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

43.25

/src/passes/structured_control_flow/for2map.cpp

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

#include "sdfg/analysis/assumptions_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 {

std::string For2MapPass::name() { return "For2Map"; }

bool For2MapPass::can_be_applied(
    builder::StructuredSDFGBuilder& builder,
    analysis::AnalysisManager& analysis_manager,
    structured_control_flow::For& for_stmt
) {
    auto& assumptions_analysis = analysis_manager.get<analysis::AssumptionsAnalysis>();
    bool is_monotonic = analysis::LoopAnalysis::is_monotonic(&for_stmt, assumptions_analysis);
    if (!is_monotonic) {
        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 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& users = analysis_manager.get<analysis::Users>();
    auto locals = users.locals(for_stmt.root());
    for (auto& dep : dependencies) {
        auto& container = dep.first;

        // Must be loop-local variable
        if (locals.find(container) == locals.end()) {
            return false;
        }

        // Check for pointers that they point to loop-local storage
        auto& type = builder.subject().type(container);
        if (type.type_id() != types::TypeID::Pointer) {
            continue;
        }
        if (type.storage_type().allocation() == types::StorageType::AllocationType::Managed) {
            continue;
        }

        // or alias of loop-local storage
        if (users.moves(container).size() != 1) {
            return false;
        }
        auto move = users.moves(container).front();
        auto move_node = static_cast<const data_flow::AccessNode*>(move->element());
        auto& move_graph = move_node->get_parent();
        auto& move_edge = *move_graph.in_edges(*move_node).begin();
        auto& move_src = static_cast<const data_flow::AccessNode&>(move_edge.src());
        if (locals.find(move_src.data()) == locals.end()) {
            return false;
        }
        auto& move_type = builder.subject().type(move_src.data());
        if (move_type.storage_type().allocation() == types::StorageType::AllocationType::Unmanaged) {
            return false;
        }
    }

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

    return true;
}

bool For2MapPass::run_pass(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {
    this->data_dependency_analysis_ = std::make_unique<analysis::DataDependencyAnalysis>(builder.subject(), true);
    this->data_dependency_analysis_->run(analysis_manager);

    auto& loop_analysis = analysis_manager.get<analysis::LoopAnalysis>();
    auto& loop_tree = loop_analysis.loop_tree();

    // Traverse loops in bottom-up fashion (reverse loop)
    std::list<structured_control_flow::For*> for_queue;
    for (auto& entry : loop_tree) {
        if (auto for_stmt = dynamic_cast<structured_control_flow::For*>(entry.first)) {
            for_queue.push_front(for_stmt);
        }
    }

    // Mark for loops that can be converted
    std::list<structured_control_flow::For*> map_queue;
    for (auto& for_loop : for_queue) {
        if (this->can_be_applied(builder, analysis_manager, *for_loop)) {
            map_queue.push_back(for_loop);
        }
    }

    // Convert marked for loops
    bool applied = false;
    auto& scope_analysis = analysis_manager.get<analysis::ScopeAnalysis>();
    for (auto& for_stmt : map_queue) {
        auto parent = static_cast<structured_control_flow::Sequence*>(scope_analysis.parent_scope(for_stmt));
        builder.convert_for(*parent, *for_stmt);
        applied = true;
    }

    return applied;
}

} // 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/loop_analysis.h"
5	#include "sdfg/analysis/scope_analysis.h"
6	#include "sdfg/analysis/users.h"
7	#include "sdfg/passes/pipeline.h"
8
9	namespace sdfg {
10	namespace passes {
11
NEW 12	std::string For2MapPass::name() { return "For2Map"; }	×
13
14	bool For2MapPass::can_be_applied(	9✔
15	builder::StructuredSDFGBuilder& builder,
16	analysis::AnalysisManager& analysis_manager,
17	structured_control_flow::For& for_stmt
18	) {
19	auto& assumptions_analysis = analysis_manager.get<analysis::AssumptionsAnalysis>();	9✔
20	bool is_monotonic = analysis::LoopAnalysis::is_monotonic(&for_stmt, assumptions_analysis);	9✔
21	if (!is_monotonic) {	9!
22	return false;	×
23	}
24
25	// Criterion: Loop must not have side-effecting body
26	std::list<const structured_control_flow::ControlFlowNode*> queue = {&for_stmt.root()};	9!
27	while (!queue.empty()) {	30✔
28	auto current = queue.front();	21✔
29	queue.pop_front();	21✔
30
31	if (auto block = dynamic_cast<const structured_control_flow::Block*>(current)) {	21!
32	for (auto& node : block->dataflow().nodes()) {	41!
33	if (auto library_node = dynamic_cast<const data_flow::LibraryNode*>(&node)) {	31!
34	if (library_node->side_effect()) {	×
35	return false;	×
36	}
37	}	×
38	}
39	} else if (auto seq = dynamic_cast<const structured_control_flow::Sequence*>(current)) {	21!
40	for (size_t i = 0; i < seq->size(); i++) {	21!
41	auto& child = seq->at(i).first;	11!
42	queue.push_back(&child);	11!
43	}	11✔
44	} else if (auto ifelse = dynamic_cast<const structured_control_flow::IfElse*>(current)) {	11!
45	for (size_t i = 0; i < ifelse->size(); i++) {	×
46	auto& branch = ifelse->at(i).first;	×
47	queue.push_back(&branch);	×
48	}	×
49	} else if (auto loop = dynamic_cast<const structured_control_flow::StructuredLoop*>(current)) {	1!
50	queue.push_back(&loop->root());	1!
51	} else if (auto while_stmt = dynamic_cast<const structured_control_flow::While*>(current)) {	1!
52	queue.push_back(&while_stmt->root());	×
53	} else if (auto for_stmt = dynamic_cast<const structured_control_flow::Break*>(current)) {	×
54	// Do nothing
55	} else if (auto for_stmt = dynamic_cast<const structured_control_flow::Continue*>(current)) {	×
56	// Do nothing
57	} else if (auto for_stmt = dynamic_cast<const structured_control_flow::Return*>(current)) {	×
58	return false;	×
59	} else {
60	throw InvalidSDFGException("Unknown control flow node type in For2Map pass.");	×
61	}
62	}
63
64	// Criterion: loop must be data-parallel w.r.t containers
65	auto dependencies = data_dependency_analysis_->dependencies(for_stmt);	9!
66
67	// a. No true dependencies (RAW) between iterations
68	for (auto& dep : dependencies) {	10✔
69	if (dep.second == analysis::LoopCarriedDependency::LOOP_CARRIED_DEPENDENCY_READ_WRITE) {	1!
70	return false;	×
71	}
72	}
73
74	// b. False dependencies (WAW) are limited to loop-local variables
75	auto& users = analysis_manager.get<analysis::Users>();	9!
76	auto locals = users.locals(for_stmt.root());	9!
77	for (auto& dep : dependencies) {	10✔
78	auto& container = dep.first;	1✔
79
80	// Must be loop-local variable
81	if (locals.find(container) == locals.end()) {	1!
82	return false;	×
83	}
84
85	// Check for pointers that they point to loop-local storage
86	auto& type = builder.subject().type(container);	1!
87	if (type.type_id() != types::TypeID::Pointer) {	1!
88	continue;	1✔
89	}
90	if (type.storage_type().allocation() == types::StorageType::AllocationType::Managed) {	×
91	continue;	×
92	}
93
94	// or alias of loop-local storage
95	if (users.moves(container).size() != 1) {	×
96	return false;	×
97	}
98	auto move = users.moves(container).front();	×
99	auto move_node = static_cast<const data_flow::AccessNode*>(move->element());	×
100	auto& move_graph = move_node->get_parent();	×
101	auto& move_edge = move_graph.in_edges(move_node).begin();	×
102	auto& move_src = static_cast<const data_flow::AccessNode&>(move_edge.src());	×
103	if (locals.find(move_src.data()) == locals.end()) {	×
104	return false;	×
105	}
NEW 106	auto& move_type = builder.subject().type(move_src.data());	×
107	if (move_type.storage_type().allocation() == types::StorageType::AllocationType::Unmanaged) {	×
108	return false;	×
109	}
110	}
111
112	// c. indvar not used after for
113	if (locals.find(for_stmt.indvar()->get_name()) != locals.end()) {	9!
114	return false;	×
115	}
116
117	return true;	9✔
118	}	9✔
119
120	bool For2MapPass::run_pass(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	8✔
121	this->data_dependency_analysis_ = std::make_unique<analysis::DataDependencyAnalysis>(builder.subject(), true);	8✔
122	this->data_dependency_analysis_->run(analysis_manager);	8✔
123
124	auto& loop_analysis = analysis_manager.get<analysis::LoopAnalysis>();	8✔
125	auto& loop_tree = loop_analysis.loop_tree();	8✔
126
127	// Traverse loops in bottom-up fashion (reverse loop)
128	std::list<structured_control_flow::For*> for_queue;	8✔
129	for (auto& entry : loop_tree) {	17✔
130	if (auto for_stmt = dynamic_cast<structured_control_flow::For*>(entry.first)) {	9!
131	for_queue.push_front(for_stmt);	9!
132	}	9✔
133	}
134
135	// Mark for loops that can be converted
136	std::list<structured_control_flow::For*> map_queue;	8✔
137	for (auto& for_loop : for_queue) {	17✔
138	if (this->can_be_applied(builder, analysis_manager, *for_loop)) {	9!
139	map_queue.push_back(for_loop);	9!
140	}	9✔
141	}
142
143	// Convert marked for loops
144	bool applied = false;	8✔
145	auto& scope_analysis = analysis_manager.get<analysis::ScopeAnalysis>();	8!
146	for (auto& for_stmt : map_queue) {	17✔
147	auto parent = static_cast<structured_control_flow::Sequence*>(scope_analysis.parent_scope(for_stmt));	9!
148	builder.convert_for(parent, for_stmt);	9!
149	applied = true;	9✔
150	}
151
152	return applied;	8✔
153	}	8✔
154
155	} // namespace passes
156	} // namespace sdfg

daisytuner / sdfglib / 20263852258

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