26520678771

Committed 27 May 2026 03:22PM UTC coverage: 60.864% (-0.02%) from 60.886%

Build # 26520678771

Build Type

Pull #719

github

Committed by

web-flow

Commit Message

Merge 99c5e4f9d into 707dadcf8

Pull Request Pull Request #719: Libnode ptr edges

Coverage Stats

961 of 1749 new or added lines in 52 files covered. (54.95%)

90 existing lines in 29 files now uncovered.

35222 of 57870 relevant lines covered (60.86%)

11043.61 hits per line

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

53.66

/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/loop_carried_dependency_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;
    }

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

    if (loop_analysis.loop_info(&for_stmt).has_side_effects) {
        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& lcd = analysis_manager.get<analysis::LoopCarriedDependencyAnalysis>();
    auto& dependencies = lcd.dependencies(for_stmt);

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

daisytuner / docc / 26520678771

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