19203085125

Committed 08 Nov 2025 07:07PM UTC coverage: 61.165% (-0.1%) from 61.281%

Build # 19203085125

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #330 from daisytuner/for-2-map-improvs

handles dereferences via local pointers in for2map conversion

Run Details

7 of 22 new or added lines in 1 file covered. (31.82%)

16 existing lines in 2 files now uncovered.

10247 of 16753 relevant lines covered (61.17%)

100.55 hits per line

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

60.0

/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) {
    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& 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& 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;
}

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	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✔
NEW 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& data_dependency_analysis = analysis_manager.get<analysis::DataDependencyAnalysis>();	9✔
66	auto dependencies = data_dependency_analysis.dependencies(for_stmt);	9✔
67
68	// a. No true dependencies (RAW) between iterations
69	for (auto& dep : dependencies) {	10✔
70	if (dep.second == analysis::LoopCarriedDependency::LOOP_CARRIED_DEPENDENCY_READ_WRITE) {	1✔
71	return false;	×
72	}
73	}
74
75	// b. False dependencies (WAW) are limited to loop-local variables
76	auto& users = analysis_manager.get<analysis::Users>();	9✔
77	auto locals = users.locals(for_stmt.root());	9✔
78	for (auto& dep : dependencies) {	10✔
79	auto& container = dep.first;	1✔
80
81	// Must be loop-local variable
82	if (locals.find(container) == locals.end()) {	1✔
83	return false;	×
84	}
85
86	// Check for pointers that they point to loop-local storage
87	auto& type = builder_.subject().type(container);	1✔
88	if (type.type_id() != types::TypeID::Pointer) {	1✔
89	continue;	1✔
90	}
NEW 91	if (type.storage_type().allocation() == types::StorageType::AllocationType::Managed) {	×
NEW 92	continue;	×
93	}
94
95	// or alias of loop-local storage
NEW 96	if (users.moves(container).size() != 1) {	×
NEW 97	return false;	×
98	}
NEW 99	auto move = users.moves(container).front();	×
NEW 100	auto move_node = static_cast<const data_flow::AccessNode*>(move->element());	×
NEW 101	auto& move_graph = move_node->get_parent();	×
NEW 102	auto& move_edge = move_graph.in_edges(move_node).begin();	×
NEW 103	auto& move_src = static_cast<const data_flow::AccessNode&>(move_edge.src());	×
NEW 104	if (locals.find(move_src.data()) == locals.end()) {	×
NEW 105	return false;	×
106	}
NEW 107	auto& move_type = builder_.subject().type(move_src.data());	×
NEW 108	if (move_type.storage_type().allocation() == types::StorageType::AllocationType::Unmanaged) {	×
NEW 109	return false;	×
110	}
111	}
112
113	// c. indvar not used after for
114	if (locals.find(for_stmt.indvar()->get_name()) != locals.end()) {	9✔
115	return false;	×
116	}
117
118	return true;	9✔
119	}	9✔
120
121	void For2Map::apply(	9✔
122	structured_control_flow::For& for_stmt,
123	builder::StructuredSDFGBuilder& builder,
124	analysis::AnalysisManager& analysis_manager
125	) {
126	auto& scope_analysis = analysis_manager.get<analysis::ScopeAnalysis>();	9✔
127	auto parent = static_cast<structured_control_flow::Sequence*>(scope_analysis.parent_scope(&for_stmt));	9✔
128
129	// convert for to map
130	builder.convert_for(*parent, for_stmt);	9✔
131	}	9✔
132
133	bool For2Map::accept(structured_control_flow::For& node) {	9✔
134	if (!this->can_be_applied(node, analysis_manager_)) {	9✔
UNCOV 135	return false;	×
136	}
137
138	this->apply(node, builder_, analysis_manager_);	9✔
139	return true;	9✔
140	}	9✔
141
142	} // namespace passes
143	} // namespace sdfg

daisytuner / sdfglib / 19203085125

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