23979317520

Committed 04 Apr 2026 12:54PM UTC coverage: 64.736% (+0.006%) from 64.73%

Build # 23979317520

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #644 from daisytuner/loop-normal-form-api

adapts new loop analysis api

Coverage Stats

39 of 44 new or added lines in 16 files covered. (88.64%)

4 existing lines in 3 files now uncovered.

29098 of 44949 relevant lines covered (64.74%)

532.85 hits per line

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

54.92

/sdfg/src/passes/structured_control_flow/for2map.cpp

#include "sdfg/passes/structured_control_flow/for2map.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
) {
    if (!for_stmt.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.type == 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>();
    analysis::UsersView body_users(users, for_stmt.root());
    auto locals = users.locals(for_stmt.root());
    for (auto& dep : dependencies) {
        auto& container = dep.first;
        auto& type = builder.subject().type(container);

        // Must be loop-local variable
        if (locals.find(container) == locals.end()) {
            // Special case: Constant scalar assignments
            if (type.type_id() == types::TypeID::Scalar) {
                auto writes = body_users.writes(container);
                auto reads = body_users.reads(container);
                if (writes.size() == 1 && reads.empty()) {
                    auto write = writes.front();
                    if (auto write_transition =
                            dynamic_cast<const structured_control_flow::Transition*>(write->element())) {
                        auto lhs = symbolic::symbol(container);
                        auto rhs = write_transition->assignments().at(lhs);
                        if (SymEngine::is_a<SymEngine::Integer>(*rhs)) {
                            continue;
                        }
                    }
                }
            }

            return false;
        }

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

daisytuner / docc / 23979317520

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