28188098396

Committed 25 Jun 2026 05:21PM UTC coverage: 61.746% (+0.1%) from 61.644%

Build # 28188098396

Build Type

Pull #802

github

Committed by

web-flow

Commit Message

Merge 08b5c3f1d into fe9abd1cb

Pull Request Pull Request #802: adds reduce as new structured loop type

Coverage Stats

705 of 985 new or added lines in 34 files covered. (71.57%)

5 existing lines in 4 files now uncovered.

38839 of 62901 relevant lines covered (61.75%)

978.2 hits per line

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

62.25

/sdfg/src/passes/structured_control_flow/for_classification.cpp

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

#include <set>
#include <vector>

#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 ForClassificationPass::name() { return "ForClassification"; }

ForClassificationPass::Classification ForClassificationPass::classify(
    builder::StructuredSDFGBuilder& builder,
    analysis::AnalysisManager& analysis_manager,
    structured_control_flow::For& for_stmt,
    std::vector<structured_control_flow::ReductionInfo>& reductions
) {
    reductions.clear();

    if (!for_stmt.is_monotonic()) {
        return Classification::None;
    }

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

    if (loop_analysis.loop_info(&for_stmt).has_side_effects) {
        return Classification::None;
    }

    // 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 Classification::None;
                    }
                }
            }
        } 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 Classification::None;
        } else {
            throw InvalidSDFGException("Unknown control flow node type in ForClassification pass.");
        }
    }

    // Criterion: loop must be data-parallel w.r.t containers
    auto& lcd = analysis_manager.get<analysis::LoopCarriedDependencyAnalysis>();
    auto& dependencies = lcd.dependencies(for_stmt);

    // Recognized reductions: loop-carried read-write dependencies that are
    // reorderable accumulations. These are NOT hazards for a Reduce loop.
    const auto& recognized_reductions = lcd.reductions(for_stmt);
    std::set<std::string> reduction_containers;
    for (auto& reduction : recognized_reductions) {
        reduction_containers.insert(reduction.container);
    }
    bool is_reduction = lcd.is_reduction_only(for_stmt);

    // a. The only true dependencies (RAW / undefined) allowed between iterations
    //    are recognized reductions. Any other hazard rules out both Map and
    //    Reduce.
    if (lcd.has_loop_carried_hazard(for_stmt) && !is_reduction) {
        return Classification::None;
    }

    // b. False dependencies (WAW) are limited to loop-local variables. Reduction
    //    accumulators are exempt: their cross-iteration writes are handled by
    //    the reduction itself.
    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;
        if (reduction_containers.count(container) != 0) {
            continue;
        }
        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 Classification::None;
        }

        // 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 Classification::None;
        }
        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 Classification::None;
        }
        auto& move_type = builder.subject().type(move_src.data());
        if (move_type.storage_type().allocation() == types::StorageType::AllocationType::Unmanaged) {
            return Classification::None;
        }
    }

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

    if (is_reduction) {
        reductions.assign(recognized_reductions.begin(), recognized_reductions.end());
        return Classification::Reduce;
    }
    return Classification::Map;
}

bool ForClassificationPass::run_pass(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {
    auto& loop_analysis = analysis_manager.get<analysis::LoopAnalysis>();

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

    // Mark for loops that can be converted, recording the target classification
    // (and the reductions for Reduce loops) up front while the analyses are valid.
    std::list<structured_control_flow::For*> map_queue;
    std::list<std::pair<structured_control_flow::For*, std::vector<structured_control_flow::ReductionInfo>>>
        reduce_queue;
    for (auto& for_loop : for_queue) {
        std::vector<structured_control_flow::ReductionInfo> reductions;
        switch (this->classify(builder, analysis_manager, *for_loop, reductions)) {
            case Classification::Map:
                map_queue.push_back(for_loop);
                break;
            case Classification::Reduce:
                reduce_queue.emplace_back(for_loop, std::move(reductions));
                break;
            case Classification::None:
                break;
        }
    }

    // Convert marked for loops
    bool applied = false;
    for (auto& for_stmt : map_queue) {
        auto parent = static_cast<structured_control_flow::Sequence*>(for_stmt->get_parent());
        builder.convert_for(*parent, *for_stmt);
        applied = true;
    }
    for (auto& entry : reduce_queue) {
        auto* for_stmt = entry.first;
        auto parent = static_cast<structured_control_flow::Sequence*>(for_stmt->get_parent());
        builder.convert_for_to_reduce(*parent, *for_stmt, entry.second);
        applied = true;
    }

    return applied;
}

} // namespace passes
} // namespace sdfg

1	#include "sdfg/passes/structured_control_flow/for_classification.h"
2
3	#include <set>
4	#include <vector>
5
6	#include "sdfg/analysis/loop_analysis.h"
7	#include "sdfg/analysis/loop_carried_dependency_analysis.h"
8	#include "sdfg/analysis/scope_analysis.h"
9	#include "sdfg/analysis/users.h"
10	#include "sdfg/passes/pipeline.h"
11
12	namespace sdfg {
13	namespace passes {
14
NEW 15	std::string ForClassificationPass::name() { return "ForClassification"; }	×
16
17	ForClassificationPass::Classification ForClassificationPass::classify(
18	builder::StructuredSDFGBuilder& builder,
19	analysis::AnalysisManager& analysis_manager,
20	structured_control_flow::For& for_stmt,
21	std::vector<structured_control_flow::ReductionInfo>& reductions
22	) {	166✔
23	reductions.clear();	166✔
24
25	if (!for_stmt.is_monotonic()) {	166✔
NEW 26	return Classification::None;	×
27	}	×
28
29	auto& loop_analysis = analysis_manager.get<analysis::LoopAnalysis>();	166✔
30
31	if (loop_analysis.loop_info(&for_stmt).has_side_effects) {	166✔
NEW 32	return Classification::None;	×
33	}	×
34
35	// Criterion: Loop must not have side-effecting body
36	std::list<const structured_control_flow::ControlFlowNode*> queue = {&for_stmt.root()};	166✔
37	while (!queue.empty()) {	1,113✔
38	auto current = queue.front();	947✔
39	queue.pop_front();	947✔
40
41	if (auto block = dynamic_cast<const structured_control_flow::Block*>(current)) {	947✔
42	for (auto& node : block->dataflow().nodes()) {	1,682✔
43	if (auto library_node = dynamic_cast<const data_flow::LibraryNode*>(&node)) {	1,682✔
44	if (library_node->side_effect()) {	3✔
NEW 45	return Classification::None;	×
46	}	×
47	}	3✔
48	}	1,682✔
49	} else if (auto seq = dynamic_cast<const structured_control_flow::Sequence*>(current)) {	552✔
50	for (size_t i = 0; i < seq->size(); i++) {	947✔
51	auto& child = seq->at(i).first;	588✔
52	queue.push_back(&child);	588✔
53	}	588✔
54	} else if (auto ifelse = dynamic_cast<const structured_control_flow::IfElse*>(current)) {	359✔
55	for (size_t i = 0; i < ifelse->size(); i++) {	×
56	auto& branch = ifelse->at(i).first;	×
57	queue.push_back(&branch);	×
58	}	×
59	} else if (auto loop = dynamic_cast<const structured_control_flow::StructuredLoop*>(current)) {	193✔
60	queue.push_back(&loop->root());	193✔
61	} else if (auto while_stmt = dynamic_cast<const structured_control_flow::While*>(current)) {	193✔
62	queue.push_back(&while_stmt->root());	×
63	} else if (auto for_stmt = dynamic_cast<const structured_control_flow::Break*>(current)) {	×
64	// Do nothing
65	} else if (auto for_stmt = dynamic_cast<const structured_control_flow::Continue*>(current)) {	×
66	// Do nothing
67	} else if (auto for_stmt = dynamic_cast<const structured_control_flow::Return*>(current)) {	×
NEW 68	return Classification::None;	×
69	} else {	×
NEW 70	throw InvalidSDFGException("Unknown control flow node type in ForClassification pass.");	×
71	}	×
72	}	947✔
73
74	// Criterion: loop must be data-parallel w.r.t containers
75	auto& lcd = analysis_manager.get<analysis::LoopCarriedDependencyAnalysis>();	166✔
76	auto& dependencies = lcd.dependencies(for_stmt);	166✔
77
78	// Recognized reductions: loop-carried read-write dependencies that are
79	// reorderable accumulations. These are NOT hazards for a Reduce loop.
80	const auto& recognized_reductions = lcd.reductions(for_stmt);	166✔
81	std::set<std::string> reduction_containers;	166✔
82	for (auto& reduction : recognized_reductions) {	166✔
83	reduction_containers.insert(reduction.container);	29✔
84	}	29✔
85	bool is_reduction = lcd.is_reduction_only(for_stmt);	166✔
86
87	// a. The only true dependencies (RAW / undefined) allowed between iterations
88	// are recognized reductions. Any other hazard rules out both Map and
89	// Reduce.
90	if (lcd.has_loop_carried_hazard(for_stmt) && !is_reduction) {	166✔
91	return Classification::None;	63✔
92	}	63✔
93
94	// b. False dependencies (WAW) are limited to loop-local variables. Reduction
95	// accumulators are exempt: their cross-iteration writes are handled by
96	// the reduction itself.
97	auto& users = analysis_manager.get<analysis::Users>();	103✔
98	analysis::UsersView body_users(users, for_stmt.root());	103✔
99	auto locals = users.locals(for_stmt.root());	103✔
100	for (auto& dep : dependencies) {	148✔
101	auto& container = dep.first;	148✔
102	if (reduction_containers.count(container) != 0) {	148✔
103	continue;	29✔
104	}	29✔
105	auto& type = builder.subject().type(container);	119✔
106
107	// Must be loop-local variable
108	if (locals.find(container) == locals.end()) {	119✔
109	// Special case: Constant scalar assignments
110	if (type.type_id() == types::TypeID::Scalar) {	×
111	auto writes = body_users.writes(container);	×
112	auto reads = body_users.reads(container);	×
113	if (writes.size() == 1 && reads.empty()) {	×
114	auto write = writes.front();	×
115	if (auto write_transition =	×
116	dynamic_cast<const structured_control_flow::Transition*>(write->element())) {	×
117	auto lhs = symbolic::symbol(container);	×
118	auto rhs = write_transition->assignments().at(lhs);	×
119	if (SymEngine::is_a<SymEngine::Integer>(*rhs)) {	×
120	continue;	×
121	}	×
122	}	×
123	}	×
124	}	×
125
NEW 126	return Classification::None;	×
127	}	×
128
129	// Check for pointers that they point to loop-local storage
130	if (type.type_id() != types::TypeID::Pointer) {	119✔
131	continue;	119✔
132	}	119✔
133	if (type.storage_type().allocation() == types::StorageType::AllocationType::Managed) {	×
134	continue;	×
135	}	×
136
137	// or alias of loop-local storage
138	if (users.moves(container).size() != 1) {	×
NEW 139	return Classification::None;	×
140	}	×
141	auto move = users.moves(container).front();	×
142	auto move_node = static_cast<const data_flow::AccessNode*>(move->element());	×
143	auto& move_graph = move_node->get_parent();	×
144	auto& move_edge = move_graph.in_edges(move_node).begin();	×
145	auto& move_src = static_cast<const data_flow::AccessNode&>(move_edge.src());	×
146	if (locals.find(move_src.data()) == locals.end()) {	×
NEW 147	return Classification::None;	×
148	}	×
149	auto& move_type = builder.subject().type(move_src.data());	×
150	if (move_type.storage_type().allocation() == types::StorageType::AllocationType::Unmanaged) {	×
NEW 151	return Classification::None;	×
152	}	×
153	}	×
154
155	// c. indvar not used after for
156	if (locals.find(for_stmt.indvar()->get_name()) != locals.end()) {	103✔
NEW 157	return Classification::None;	×
158	}	×
159
160	if (is_reduction) {	103✔
161	reductions.assign(recognized_reductions.begin(), recognized_reductions.end());	26✔
162	return Classification::Reduce;	26✔
163	}	26✔
164	return Classification::Map;	77✔
165	}	103✔
166
167	bool ForClassificationPass::run_pass(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	93✔
168	auto& loop_analysis = analysis_manager.get<analysis::LoopAnalysis>();	93✔
169
170	// Traverse loops in bottom-up fashion (reverse loop)
171	std::list<structured_control_flow::For*> for_queue;	93✔
172	for (auto& loop : loop_analysis.loops_in_pre_order()) {	346✔
173	if (auto for_stmt = dynamic_cast<structured_control_flow::For*>(loop)) {	346✔
174	for_queue.push_front(for_stmt);	166✔
175	}	166✔
176	}	346✔
177
178	// Mark for loops that can be converted, recording the target classification
179	// (and the reductions for Reduce loops) up front while the analyses are valid.
180	std::list<structured_control_flow::For*> map_queue;	93✔
181	std::list<std::pair<structured_control_flow::For*, std::vector<structured_control_flow::ReductionInfo>>>	93✔
182	reduce_queue;	93✔
183	for (auto& for_loop : for_queue) {	166✔
184	std::vector<structured_control_flow::ReductionInfo> reductions;	166✔
185	switch (this->classify(builder, analysis_manager, *for_loop, reductions)) {	166✔
186	case Classification::Map:	77✔
187	map_queue.push_back(for_loop);	77✔
188	break;	77✔
189	case Classification::Reduce:	26✔
190	reduce_queue.emplace_back(for_loop, std::move(reductions));	26✔
191	break;	26✔
192	case Classification::None:	63✔
193	break;	63✔
194	}	166✔
195	}	166✔
196
197	// Convert marked for loops
198	bool applied = false;	93✔
199	for (auto& for_stmt : map_queue) {	93✔
200	auto parent = static_cast<structured_control_flow::Sequence*>(for_stmt->get_parent());	77✔
201	builder.convert_for(parent, for_stmt);	77✔
202	applied = true;	77✔
203	}	77✔
204	for (auto& entry : reduce_queue) {	93✔
205	auto* for_stmt = entry.first;	26✔
206	auto parent = static_cast<structured_control_flow::Sequence*>(for_stmt->get_parent());	26✔
207	builder.convert_for_to_reduce(parent, for_stmt, entry.second);	26✔
208	applied = true;	26✔
209	}	26✔
210
211	return applied;	93✔
212	}	93✔
213
214	} // namespace passes
215	} // namespace sdfg

daisytuner / docc / 28188098396

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