27746949498

Committed 18 Jun 2026 08:30AM UTC coverage: 61.628% (+0.008%) from 61.62%

Build # 27746949498

Build Type

push

github

Committed by

web-flow

Commit Message

adds thread coarsening to GPU optimization tests (#773)

Coverage Stats

36659 of 59484 relevant lines covered (61.63%)

1022.57 hits per line

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

71.63

/opt/src/transformations/offloading/gpu_condition_propagation.cpp

#include "sdfg/transformations/offloading/gpu_condition_propagation.h"
#include <vector>
#include "sdfg/analysis/users.h"
#include "sdfg/data_flow/library_nodes/barrier_local_node.h"
#include "sdfg/element.h"
#include "sdfg/structured_control_flow/control_flow_node.h"
#include "sdfg/structured_control_flow/map.h"
#include "sdfg/structured_sdfg.h"
#include "sdfg/targets/gpu/gpu_schedule_type.h"
#include "sdfg/visitor/structured_sdfg_visitor.h"

namespace sdfg {
namespace transformations {

GPUConditionPropagation::GPUConditionPropagation(structured_control_flow::Map& map_) : map_(map_) {};


bool GPUConditionPropagation::
    can_be_applied(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {
    // Criterion: Must be a GPU map (CUDA or ROCm)
    if (!gpu::is_gpu_schedule(map_.schedule_type())) {
        return false;
    }

    // Criterion: Loop must contain thread barriers
    BarrierFinder barrier_finder(builder, analysis_manager);
    if (!barrier_finder.visit(&map_)) {
        return false;
    }

    return true;
}

void GPUConditionPropagation::apply(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {
    //  1. iterate over all nodes in the map body
    //  2. for each node, check if it contains a barrier
    //  3. if, propagate the map condition to the barrier
    //  4. else mark the node as relevant for condition propagation

    auto new_sched_type = map_.schedule_type();
    new_sched_type.set_property("nested_sync", "true");
    builder.update_schedule_type(map_, new_sched_type);

    std::vector<structured_control_flow::ControlFlowNode*> nodes_to_visit;
    nodes_to_visit.push_back(&map_.root());
    BarrierFinder barrier_finder(builder, analysis_manager);

    auto& users = analysis_manager.get<analysis::Users>();

    while (!nodes_to_visit.empty()) {
        auto current_node = nodes_to_visit.back();
        nodes_to_visit.pop_back();
        auto parent_scope = current_node->get_parent();
        auto parent_sequence = dynamic_cast<structured_control_flow::Sequence*>(parent_scope);
        analysis::UsersView current_users(users, *current_node);
        auto uses = current_users.uses(map_.indvar()->get_name());
        if (uses.empty()) {
            // Node does not use the map indvar, skip
            continue;
        }

        if (auto block_node = dynamic_cast<structured_control_flow::Block*>(current_node)) {
            if (!barrier_finder.visit(block_node)) {
                auto& if_else = builder.add_if_else_before(*parent_sequence, *block_node, {}, DebugInfo());
                auto& branch = builder.add_case(if_else, map_.condition());
                builder.move_child(*parent_sequence, parent_sequence->index(*block_node), branch);
            }
        } else if (auto seq_node = dynamic_cast<structured_control_flow::Sequence*>(current_node)) {
            if (barrier_finder.visit(seq_node)) {
                for (int i = 0; i < seq_node->size(); i++) {
                    nodes_to_visit.push_back(&seq_node->at(i).first);
                }
            } else {
                auto& if_else = builder.add_if_else_before(*parent_sequence, seq_node->at(0).first, {}, DebugInfo());
                auto& branch = builder.add_case(if_else, map_.condition());
                for (int i = 0; i < seq_node->size(); i++) {
                    builder.move_child(*seq_node, seq_node->index(seq_node->at(0).first), branch);
                }
            }
        } else if (auto ifelse_node = dynamic_cast<structured_control_flow::IfElse*>(current_node)) {
            if (barrier_finder.visit(ifelse_node)) {
                for (size_t i = 0; i < ifelse_node->size(); i++) {
                    nodes_to_visit.push_back(&ifelse_node->at(i).first);
                }
            } else {
                auto& if_else = builder.add_if_else_before(*parent_sequence, *ifelse_node, {}, DebugInfo());
                auto& branch = builder.add_case(if_else, map_.condition());
                builder.move_child(*parent_sequence, parent_sequence->index(*ifelse_node), branch);
            }
        } else if (auto for_node = dynamic_cast<structured_control_flow::For*>(current_node)) {
            if (barrier_finder.visit(for_node)) {
                nodes_to_visit.push_back(&for_node->root());
            } else {
                auto& if_else = builder.add_if_else_before(*parent_sequence, *for_node, {}, DebugInfo());
                auto& branch = builder.add_case(if_else, map_.condition());
                builder.move_child(*parent_sequence, parent_sequence->index(*for_node), branch);
            }
        } else if (auto while_node = dynamic_cast<structured_control_flow::While*>(current_node)) {
            if (barrier_finder.visit(while_node)) {
                nodes_to_visit.push_back(&while_node->root());
            } else {
                auto& if_else = builder.add_if_else_before(*parent_sequence, *while_node, {}, DebugInfo());
                auto& branch = builder.add_case(if_else, map_.condition());
                builder.move_child(*parent_sequence, parent_sequence->index(*while_node), branch);
            }
        } else if (auto map_node = dynamic_cast<structured_control_flow::Map*>(current_node)) {
            if (barrier_finder.visit(map_node)) {
                nodes_to_visit.push_back(&map_node->root());
            } else {
                auto& if_else = builder.add_if_else_before(*parent_sequence, *map_node, {}, DebugInfo());
                auto& branch = builder.add_case(if_else, map_.condition());
                builder.move_child(*parent_sequence, parent_sequence->index(*map_node), branch);
            }
        }
    }
    analysis_manager.invalidate_all();
}

std::string GPUConditionPropagation::name() const { return "GPUConditionPropagation"; };

void GPUConditionPropagation::to_json(nlohmann::json& j) const {
    j["transformation_type"] = this->name();

    j["subgraph"] = {{"0", {{"element_id", this->map_.element_id()}, {"type", "map"}}}};

    // Legacy field for backward compatibility
    j["map_element_id"] = this->map_.element_id();
}

GPUConditionPropagation GPUConditionPropagation::
    from_json(builder::StructuredSDFGBuilder& builder, const nlohmann::json& j) {
    size_t map_id;
    if (j.contains("subgraph")) {
        const auto& node_desc = j.at("subgraph").at("0");
        map_id = node_desc.at("element_id").get<size_t>();
    } else {
        map_id = j.at("map_element_id").get<size_t>();
    }

    auto element = builder.find_element_by_id(map_id);
    if (!element) {
        throw InvalidTransformationDescriptionException("Element with ID " + std::to_string(map_id) + " not found.");
    }
    auto map = dynamic_cast<structured_control_flow::Map*>(element);

    return GPUConditionPropagation(*map);
}

BarrierFinder::BarrierFinder(builder::StructuredSDFGBuilder& builder, sdfg::analysis::AnalysisManager& analysis_manager)
    : visitor::StructuredSDFGVisitor(builder, analysis_manager) {}

bool BarrierFinder::accept(structured_control_flow::Block& node) {
    for (auto& library_node : node.dataflow().nodes()) {
        if (auto barrier_node = dynamic_cast<data_flow::BarrierLocalNode*>(&library_node)) {
            return true;
        }
    }
    return false;
}

bool BarrierFinder::visit(structured_control_flow::ControlFlowNode* node) {
    if (auto block_stmt = dynamic_cast<structured_control_flow::Block*>(node)) {
        return this->accept(*block_stmt);
    } else if (auto sequence_stmt = dynamic_cast<structured_control_flow::Sequence*>(node)) {
        return this->visit_internal(*sequence_stmt);
    } else if (auto if_else_stmt = dynamic_cast<structured_control_flow::IfElse*>(node)) {
        for (int i = 0; i < if_else_stmt->size(); i++) {
            if (this->visit_internal(if_else_stmt->at(i).first)) {
                return true;
            }
        }
    } else if (auto for_stmt = dynamic_cast<structured_control_flow::For*>(node)) {
        return this->visit_internal(for_stmt->root());
    } else if (auto map_stmt = dynamic_cast<structured_control_flow::Map*>(node)) {
        return this->visit_internal(map_stmt->root());
    } else if (auto while_stmt = dynamic_cast<structured_control_flow::While*>(node)) {
        return this->visit_internal(while_stmt->root());
    } else if (auto continue_stmt = dynamic_cast<structured_control_flow::Continue*>(node)) {
        return this->accept(*continue_stmt);
    } else if (auto break_stmt = dynamic_cast<structured_control_flow::Break*>(node)) {
        return this->accept(*break_stmt);
    } else if (auto return_stmt = dynamic_cast<structured_control_flow::Return*>(node)) {
        return this->accept(*return_stmt);
    }

    return false;
}

} // namespace transformations
} // namespace sdfg

1	#include "sdfg/transformations/offloading/gpu_condition_propagation.h"
2	#include <vector>
3	#include "sdfg/analysis/users.h"
4	#include "sdfg/data_flow/library_nodes/barrier_local_node.h"
5	#include "sdfg/element.h"
6	#include "sdfg/structured_control_flow/control_flow_node.h"
7	#include "sdfg/structured_control_flow/map.h"
8	#include "sdfg/structured_sdfg.h"
9	#include "sdfg/targets/gpu/gpu_schedule_type.h"
10	#include "sdfg/visitor/structured_sdfg_visitor.h"
11
12	namespace sdfg {
13	namespace transformations {
14
15	GPUConditionPropagation::GPUConditionPropagation(structured_control_flow::Map& map_) : map_(map_) {};	6✔
16
17
18	bool GPUConditionPropagation::
19	can_be_applied(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	4✔
20	// Criterion: Must be a GPU map (CUDA or ROCm)
21	if (!gpu::is_gpu_schedule(map_.schedule_type())) {	4✔
22	return false;	×
23	}	×
24
25	// Criterion: Loop must contain thread barriers
26	BarrierFinder barrier_finder(builder, analysis_manager);	4✔
27	if (!barrier_finder.visit(&map_)) {	4✔
28	return false;	×
29	}	×
30
31	return true;	4✔
32	}	4✔
33
34	void GPUConditionPropagation::apply(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	4✔
35	// 1. iterate over all nodes in the map body
36	// 2. for each node, check if it contains a barrier
37	// 3. if, propagate the map condition to the barrier
38	// 4. else mark the node as relevant for condition propagation
39
40	auto new_sched_type = map_.schedule_type();	4✔
41	new_sched_type.set_property("nested_sync", "true");	4✔
42	builder.update_schedule_type(map_, new_sched_type);	4✔
43
44	std::vector<structured_control_flow::ControlFlowNode*> nodes_to_visit;	4✔
45	nodes_to_visit.push_back(&map_.root());	4✔
46	BarrierFinder barrier_finder(builder, analysis_manager);	4✔
47
48	auto& users = analysis_manager.get<analysis::Users>();	4✔
49
50	while (!nodes_to_visit.empty()) {	52✔
51	auto current_node = nodes_to_visit.back();	48✔
52	nodes_to_visit.pop_back();	48✔
53	auto parent_scope = current_node->get_parent();	48✔
54	auto parent_sequence = dynamic_cast<structured_control_flow::Sequence*>(parent_scope);	48✔
55	analysis::UsersView current_users(users, *current_node);	48✔
56	auto uses = current_users.uses(map_.indvar()->get_name());	48✔
57	if (uses.empty()) {	48✔
58	// Node does not use the map indvar, skip
59	continue;	20✔
60	}	20✔
61
62	if (auto block_node = dynamic_cast<structured_control_flow::Block*>(current_node)) {	28✔
63	if (!barrier_finder.visit(block_node)) {	×
64	auto& if_else = builder.add_if_else_before(parent_sequence, block_node, {}, DebugInfo());	×
65	auto& branch = builder.add_case(if_else, map_.condition());	×
66	builder.move_child(parent_sequence, parent_sequence->index(block_node), branch);	×
67	}	×
68	} else if (auto seq_node = dynamic_cast<structured_control_flow::Sequence*>(current_node)) {	28✔
69	if (barrier_finder.visit(seq_node)) {	10✔
70	for (int i = 0; i < seq_node->size(); i++) {	48✔
71	nodes_to_visit.push_back(&seq_node->at(i).first);	38✔
72	}	38✔
73	} else {	10✔
74	auto& if_else = builder.add_if_else_before(*parent_sequence, seq_node->at(0).first, {}, DebugInfo());	×
75	auto& branch = builder.add_case(if_else, map_.condition());	×
76	for (int i = 0; i < seq_node->size(); i++) {	×
77	builder.move_child(*seq_node, seq_node->index(seq_node->at(0).first), branch);	×
78	}	×
79	}	×
80	} else if (auto ifelse_node = dynamic_cast<structured_control_flow::IfElse*>(current_node)) {	18✔
81	if (barrier_finder.visit(ifelse_node)) {	6✔
82	for (size_t i = 0; i < ifelse_node->size(); i++) {	×
83	nodes_to_visit.push_back(&ifelse_node->at(i).first);	×
84	}	×
85	} else {	6✔
86	auto& if_else = builder.add_if_else_before(parent_sequence, ifelse_node, {}, DebugInfo());	6✔
87	auto& branch = builder.add_case(if_else, map_.condition());	6✔
88	builder.move_child(parent_sequence, parent_sequence->index(ifelse_node), branch);	6✔
89	}	6✔
90	} else if (auto for_node = dynamic_cast<structured_control_flow::For*>(current_node)) {	12✔
91	if (barrier_finder.visit(for_node)) {	6✔
92	nodes_to_visit.push_back(&for_node->root());	4✔
93	} else {	4✔
94	auto& if_else = builder.add_if_else_before(parent_sequence, for_node, {}, DebugInfo());	2✔
95	auto& branch = builder.add_case(if_else, map_.condition());	2✔
96	builder.move_child(parent_sequence, parent_sequence->index(for_node), branch);	2✔
97	}	2✔
98	} else if (auto while_node = dynamic_cast<structured_control_flow::While*>(current_node)) {	6✔
99	if (barrier_finder.visit(while_node)) {	×
100	nodes_to_visit.push_back(&while_node->root());	×
101	} else {	×
102	auto& if_else = builder.add_if_else_before(parent_sequence, while_node, {}, DebugInfo());	×
103	auto& branch = builder.add_case(if_else, map_.condition());	×
104	builder.move_child(parent_sequence, parent_sequence->index(while_node), branch);	×
105	}	×
106	} else if (auto map_node = dynamic_cast<structured_control_flow::Map*>(current_node)) {	6✔
107	if (barrier_finder.visit(map_node)) {	6✔
108	nodes_to_visit.push_back(&map_node->root());	2✔
109	} else {	4✔
110	auto& if_else = builder.add_if_else_before(parent_sequence, map_node, {}, DebugInfo());	4✔
111	auto& branch = builder.add_case(if_else, map_.condition());	4✔
112	builder.move_child(parent_sequence, parent_sequence->index(map_node), branch);	4✔
113	}	4✔
114	}	6✔
115	}	28✔
116	analysis_manager.invalidate_all();	4✔
117	}	4✔
118
119	std::string GPUConditionPropagation::name() const { return "GPUConditionPropagation"; };	3✔
120
121	void GPUConditionPropagation::to_json(nlohmann::json& j) const {	1✔
122	j["transformation_type"] = this->name();	1✔
123
124	j["subgraph"] = {{"0", {{"element_id", this->map_.element_id()}, {"type", "map"}}}};	1✔
125
126	// Legacy field for backward compatibility
127	j["map_element_id"] = this->map_.element_id();	1✔
128	}	1✔
129
130	GPUConditionPropagation GPUConditionPropagation::
131	from_json(builder::StructuredSDFGBuilder& builder, const nlohmann::json& j) {	1✔
132	size_t map_id;	1✔
133	if (j.contains("subgraph")) {	1✔
134	const auto& node_desc = j.at("subgraph").at("0");	1✔
135	map_id = node_desc.at("element_id").get<size_t>();	1✔
136	} else {	1✔
137	map_id = j.at("map_element_id").get<size_t>();	×
138	}	×
139
140	auto element = builder.find_element_by_id(map_id);	1✔
141	if (!element) {	1✔
142	throw InvalidTransformationDescriptionException("Element with ID " + std::to_string(map_id) + " not found.");	×
143	}	×
144	auto map = dynamic_cast<structured_control_flow::Map*>(element);	1✔
145
146	return GPUConditionPropagation(*map);	1✔
147	}	1✔
148
149	BarrierFinder::BarrierFinder(builder::StructuredSDFGBuilder& builder, sdfg::analysis::AnalysisManager& analysis_manager)
150	: visitor::StructuredSDFGVisitor(builder, analysis_manager) {}	8✔
151
152	bool BarrierFinder::accept(structured_control_flow::Block& node) {	38✔
153	for (auto& library_node : node.dataflow().nodes()) {	82✔
154	if (auto barrier_node = dynamic_cast<data_flow::BarrierLocalNode*>(&library_node)) {	82✔
155	return true;	20✔
156	}	20✔
157	}	82✔
158	return false;	18✔
159	}	38✔
160
161	bool BarrierFinder::visit(structured_control_flow::ControlFlowNode* node) {	32✔
162	if (auto block_stmt = dynamic_cast<structured_control_flow::Block*>(node)) {	32✔
163	return this->accept(*block_stmt);	×
164	} else if (auto sequence_stmt = dynamic_cast<structured_control_flow::Sequence*>(node)) {	32✔
165	return this->visit_internal(*sequence_stmt);	10✔
166	} else if (auto if_else_stmt = dynamic_cast<structured_control_flow::IfElse*>(node)) {	22✔
167	for (int i = 0; i < if_else_stmt->size(); i++) {	12✔
168	if (this->visit_internal(if_else_stmt->at(i).first)) {	6✔
169	return true;	×
170	}	×
171	}	6✔
172	} else if (auto for_stmt = dynamic_cast<structured_control_flow::For*>(node)) {	16✔
173	return this->visit_internal(for_stmt->root());	6✔
174	} else if (auto map_stmt = dynamic_cast<structured_control_flow::Map*>(node)) {	10✔
175	return this->visit_internal(map_stmt->root());	10✔
176	} else if (auto while_stmt = dynamic_cast<structured_control_flow::While*>(node)) {	10✔
177	return this->visit_internal(while_stmt->root());	×
178	} else if (auto continue_stmt = dynamic_cast<structured_control_flow::Continue*>(node)) {	×
179	return this->accept(*continue_stmt);	×
180	} else if (auto break_stmt = dynamic_cast<structured_control_flow::Break*>(node)) {	×
181	return this->accept(*break_stmt);	×
182	} else if (auto return_stmt = dynamic_cast<structured_control_flow::Return*>(node)) {	×
183	return this->accept(*return_stmt);	×
184	}	×
185
186	return false;	6✔
187	}	32✔
188
189	} // namespace transformations
190	} // namespace sdfg

daisytuner / docc / 27746949498

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