31009380971

Committed 05 Aug 2026 01:15PM UTC coverage: 65.103% (+0.1%) from 65.005%

Build # 31009380971

Build Type

Pull #814

github

Committed by

web-flow

Commit Message

Merge 268a080ae into 7d5b198bd

Pull Request Pull Request #814: Adds GPU reduce dispatchers

Coverage Stats

409 of 663 new or added lines in 18 files covered. (61.69%)

145 existing lines in 6 files now uncovered.

46693 of 71722 relevant lines covered (65.1%)

713.1 hits per line

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

85.24

/opt/src/targets/gpu/gpu_map_utils.cpp

#include "sdfg/targets/gpu/gpu_map_utils.h"

#include <string>
#include <unordered_set>

#include "sdfg/analysis/arguments_analysis.h"
#include "sdfg/analysis/assumptions_analysis.h"
#include "sdfg/analysis/loop_analysis.h"
#include "sdfg/analysis/users.h"
#include "sdfg/structured_control_flow/sequence.h"
#include "sdfg/targets/cuda/cuda.h"
#include "sdfg/targets/rocm/rocm.h"

namespace sdfg {
namespace gpu {

template<typename ScheduleT>
symbolic::Expression find_nested_gpu_blocksize(
    structured_control_flow::Map& node, analysis::AnalysisManager& analysis_manager, GPUDimension dimension
) {
    auto& loop_analysis = analysis_manager.get<analysis::LoopAnalysis>();
    auto loops = loop_analysis.descendants(&node);
    loops.insert(&node);

    // Check for repeated dimensions in loop tree paths
    auto loop_tree_paths = loop_analysis.loop_tree_paths(&node);
    for (auto& path : loop_tree_paths) {
        bool foundX = false;
        bool foundY = false;
        bool foundZ = false;
        for (auto& loop : path) {
            if (auto map = dynamic_cast<structured_control_flow::StructuredLoop*>(loop)) {
                if (map->schedule_type().value() == ScheduleT::value()) {
                    auto dim = ScheduleT::dimension(map->schedule_type());
                    if (dim == GPUDimension::X) {
                        if (foundX) {
                            throw InvalidSDFGException("Nested map in GPU kernel has repeated X dimension");
                        }
                        foundX = true;
                    } else if (dim == GPUDimension::Y) {
                        if (foundY) {
                            throw InvalidSDFGException("Nested map in GPU kernel has repeated Y dimension");
                        }
                        foundY = true;
                    } else if (dim == GPUDimension::Z) {
                        if (foundZ) {
                            throw InvalidSDFGException("Nested map in GPU kernel has repeated Z dimension");
                        }
                        foundZ = true;
                    }
                }
            }
        }
    }

    // Find block size for the requested dimension
    for (auto loop : loops) {
        if (auto map = dynamic_cast<structured_control_flow::StructuredLoop*>(loop)) {
            if (map->schedule_type().value() != ScheduleT::value() &&
                map->schedule_type().value() != structured_control_flow::ScheduleType_Sequential::value()) {
                throw InvalidSDFGException("Nested map in GPU kernel not GPU or Sequential");
            }

            if (map->schedule_type().value() == structured_control_flow::ScheduleType_Sequential::value()) {
                continue;
            }

            if (ScheduleT::dimension(map->schedule_type()) == dimension) {
                return ScheduleT::block_size(map->schedule_type());
            }
        }
    }
    return symbolic::one();
}

template<typename ScheduleT>
symbolic::Expression find_nested_gpu_iterations(
    structured_control_flow::Map& node, analysis::AnalysisManager& analysis_manager, GPUDimension dimension
) {
    auto& loop_analysis = analysis_manager.get<analysis::LoopAnalysis>();
    auto loops = loop_analysis.descendants(&node);
    loops.insert(&node);

    symbolic::Expression max_num_iterations = symbolic::one();

    for (auto loop : loops) {
        if (auto map = dynamic_cast<structured_control_flow::StructuredLoop*>(loop)) {
            if (map->schedule_type().value() != ScheduleT::value() &&
                map->schedule_type().value() != structured_control_flow::ScheduleType_Sequential::value()) {
                throw InvalidSDFGException("Nested map in GPU kernel not GPU or Sequential");
            }
            if (map->schedule_type().value() == structured_control_flow::ScheduleType_Sequential::value()) {
                continue;
            }
            if (ScheduleT::dimension(map->schedule_type()) != dimension) {
                continue;
            }

            // Note: arbitrary `init` and `stride` are permitted here; the
            // dispatcher emits `indvar = init + thread_flat_id * stride` so
            // the body sees the natural strided value. `num_iterations()`
            // already accounts for both.
            auto num_iterations = map->num_iterations();
            if (num_iterations.is_null()) {
                throw InvalidSDFGException("Cannot determine number of iterations for nested map in GPU kernel");
            }
            max_num_iterations = symbolic::max(max_num_iterations, num_iterations);
        }
    }
    return max_num_iterations;
}

template<typename ScheduleT>
bool is_outermost_gpu_map(structured_control_flow::Map& node, analysis::AnalysisManager& analysis_manager) {
    auto& loop_analysis = analysis_manager.get<analysis::LoopAnalysis>();
    auto& loop_tree = loop_analysis.loop_tree();
    structured_control_flow::ControlFlowNode* ancestor = loop_tree.at(&node);
    while (ancestor != nullptr) {
        if (auto map = dyn_cast<structured_control_flow::Map*>(ancestor)) {
            if (map->schedule_type().value() == ScheduleT::value()) {
                return false;
            }
        }
        ancestor = loop_tree.at(ancestor);
    }
    return true;
}

template<typename ScheduleT>
symbolic::SymbolSet get_gpu_indvars(
    structured_control_flow::Map& node, analysis::AnalysisManager& analysis_manager, GPUDimension dimension
) {
    auto& loop_analysis = analysis_manager.get<analysis::LoopAnalysis>();
    auto loops = loop_analysis.descendants(&node);
    loops.insert(&node);
    symbolic::SymbolSet indvars;
    for (const auto& loop : loops) {
        if (auto map = dyn_cast<structured_control_flow::Map*>(loop)) {
            if (map->schedule_type().value() == ScheduleT::value()) {
                if (ScheduleT::dimension(map->schedule_type()) == dimension) {
                    indvars.insert(map->indvar());
                }
            }
        }
    }
    return indvars;
}

template<typename ScheduleT>
std::vector<structured_control_flow::Map*>
get_gpu_maps(structured_control_flow::Map& node, analysis::AnalysisManager& analysis_manager, GPUDimension dimension) {
    auto& loop_analysis = analysis_manager.get<analysis::LoopAnalysis>();
    auto loops = loop_analysis.descendants(&node);
    loops.insert(&node);
    std::vector<structured_control_flow::Map*> maps;
    for (const auto& loop : loops) {
        if (auto map = dyn_cast<structured_control_flow::Map*>(loop)) {
            if (map->schedule_type().value() == ScheduleT::value()) {
                if (ScheduleT::dimension(map->schedule_type()) == dimension) {
                    maps.push_back(map);
                }
            }
        }
    }
    return maps;
}

bool nested_parallelization_is_unsafe(
    structured_control_flow::StructuredLoop& loop, analysis::AnalysisManager& analysis_manager
) {
    auto& loop_analysis = analysis_manager.get<analysis::LoopAnalysis>();

    // The outermost enclosing GPU map is the kernel scope. Everything below it is
    // folded into a single flattened launch, so adding a dimension for `loop`
    // distributes its iterations across the new dimension's threads and replicates
    // its siblings (and the siblings of any ancestor up to this map) across them.
    auto is_parallelized = [](structured_control_flow::Map* map) {
        return map->schedule_type().value() != structured_control_flow::ScheduleType_Sequential::value();
    };

    structured_control_flow::Map* outermost = nullptr;
    for (auto* ancestor = loop_analysis.parent_loop(&loop); ancestor != nullptr;
         ancestor = loop_analysis.parent_loop(ancestor)) {
        if (auto* map = dyn_cast<structured_control_flow::Map*>(ancestor)) {
            if (is_parallelized(map)) {
                outermost = map;
            }
        }
    }
    if (outermost == nullptr) {
        // No enclosing GPU map: nothing is folded, hence nothing is replicated.
        return false;
    }

    auto& users = analysis_manager.get<analysis::Users>();
    auto& arguments_analysis = analysis_manager.get<analysis::ArgumentsAnalysis>();
    // Containers whose entire lifetime is confined to the kernel are privatized per
    // thread (registers/stack, per-thread allocation), so they race nothing. Only a
    // container that escapes the kernel (function argument/external or a transient
    // living outside, per ArgumentsAnalysis) is a hazard. Loop induction variables
    // are locals by definition, so this subsumes loop-control bookkeeping.
    const auto& locals = arguments_analysis.locals(analysis_manager, *outermost);
    auto is_local = [&locals](const std::string& container) { return locals.count(container) != 0; };

    // Collect the container reads and writes of a subtree. Views alias memory and
    // are treated conservatively as both a read and a write.
    auto collect = [&](structured_control_flow::ControlFlowNode& node,
                       std::unordered_set<std::string>& writes,
                       std::unordered_set<std::string>& reads) {
        analysis::UsersView view(users, node);
        for (auto* u : view.writes()) {
            writes.insert(u->container());
        }
        for (auto* u : view.moves()) {
            writes.insert(u->container());
        }
        for (auto* u : view.views()) {
            writes.insert(u->container());
            reads.insert(u->container());
        }
        for (auto* u : view.reads()) {
            reads.insert(u->container());
        }
    };

    // `loop`'s writes vary across the new dimension (its iterations are distributed),
    // so any replicated sibling that touches one of these shared containers races.
    std::unordered_set<std::string> loop_writes;
    std::unordered_set<std::string> loop_reads;
    collect(loop, loop_writes, loop_reads);

    // A subtree performs an unsafe self-accumulation if it reads and writes the same
    // non-local container (e.g. `acc[i] += x`). A plain store is idempotent under
    // replication and therefore allowed.
    auto accumulates_on_shared = [&](const std::unordered_set<std::string>& writes,
                                     const std::unordered_set<std::string>& reads) {
        for (const auto& container : writes) {
            if (reads.count(container) != 0 && !is_local(container)) {
                return true;
            }
        }
        return false;
    };

    // Walk from `loop` up to (but excluding) the outermost GPU map, inspecting the
    // siblings at each level. Siblings above the kernel are not replicated and are
    // therefore not considered.
    structured_control_flow::ControlFlowNode* node = &loop;
    while (node != outermost) {
        auto* sequence = dynamic_cast<structured_control_flow::Sequence*>(node->get_parent());
        if (sequence == nullptr) {
            break;
        }
        for (size_t i = 0; i < sequence->size(); ++i) {
            auto& sibling = sequence->at(i);
            if (&sibling == node) {
                continue;
            }

            std::unordered_set<std::string> sibling_writes;
            std::unordered_set<std::string> sibling_reads;
            collect(sibling, sibling_writes, sibling_reads);

            // Hazard 1 (producer/consumer across the fold): a shared container that
            // `loop` writes is read or written by a replicated sibling. `loop`'s
            // writes vary across the new dimension, so the sibling observes another
            // thread's incomplete data without synchronization. This is the reduce
            // accumulator -> consumer race (softmax: reduce writes acc[i], a sibling
            // divides by acc[i]). Applies even if the sibling is itself a GPU map.
            for (const auto& container : loop_writes) {
                if (is_local(container)) {
                    continue;
                }
                if (sibling_writes.count(container) != 0 || sibling_reads.count(container) != 0) {
                    return true;
                }
            }

            // Hazard 2 (replicated self-accumulation): a sibling read-modify-writes a
            // shared container. A sibling that is itself a GPU map is exempt: codegen
            // maps it onto its own threads instead of replicating it.
            if (auto* sibling_map = dyn_cast<structured_control_flow::Map*>(&sibling)) {
                if (is_parallelized(sibling_map)) {
                    continue;
                }
            }
            if (accumulates_on_shared(sibling_writes, sibling_reads)) {
                return true;
            }
        }
        node = sequence->get_parent();
        if (node == nullptr) {
            break;
        }
    }

    return false;
}


// Explicit template instantiations for CUDA
template symbolic::Expression find_nested_gpu_blocksize<cuda::ScheduleType_CUDA>(
    structured_control_flow::Map& node, analysis::AnalysisManager& analysis_manager, GPUDimension dimension
);

template symbolic::Expression find_nested_gpu_iterations<cuda::ScheduleType_CUDA>(
    structured_control_flow::Map& node, analysis::AnalysisManager& analysis_manager, GPUDimension dimension
);

template bool is_outermost_gpu_map<
    cuda::ScheduleType_CUDA>(structured_control_flow::Map& node, analysis::AnalysisManager& analysis_manager);

template symbolic::SymbolSet get_gpu_indvars<cuda::ScheduleType_CUDA>(
    structured_control_flow::Map& node, analysis::AnalysisManager& analysis_manager, GPUDimension dimension
);

template std::vector<structured_control_flow::Map*> get_gpu_maps<cuda::ScheduleType_CUDA>(
    structured_control_flow::Map& node, analysis::AnalysisManager& analysis_manager, GPUDimension dimension
);

// Explicit template instantiations for ROCM
template symbolic::Expression find_nested_gpu_blocksize<rocm::ScheduleType_ROCM>(
    structured_control_flow::Map& node, analysis::AnalysisManager& analysis_manager, GPUDimension dimension
);

template symbolic::Expression find_nested_gpu_iterations<rocm::ScheduleType_ROCM>(
    structured_control_flow::Map& node, analysis::AnalysisManager& analysis_manager, GPUDimension dimension
);

template bool is_outermost_gpu_map<
    rocm::ScheduleType_ROCM>(structured_control_flow::Map& node, analysis::AnalysisManager& analysis_manager);

template symbolic::SymbolSet get_gpu_indvars<rocm::ScheduleType_ROCM>(
    structured_control_flow::Map& node, analysis::AnalysisManager& analysis_manager, GPUDimension dimension
);

template std::vector<structured_control_flow::Map*> get_gpu_maps<rocm::ScheduleType_ROCM>(
    structured_control_flow::Map& node, analysis::AnalysisManager& analysis_manager, GPUDimension dimension
);

} // namespace gpu
} // namespace sdfg

1	#include "sdfg/targets/gpu/gpu_map_utils.h"
2
3	#include <string>
4	#include <unordered_set>
5
6	#include "sdfg/analysis/arguments_analysis.h"
7	#include "sdfg/analysis/assumptions_analysis.h"
8	#include "sdfg/analysis/loop_analysis.h"
9	#include "sdfg/analysis/users.h"
10	#include "sdfg/structured_control_flow/sequence.h"
11	#include "sdfg/targets/cuda/cuda.h"
12	#include "sdfg/targets/rocm/rocm.h"
13
14	namespace sdfg {
15	namespace gpu {
16
17	template<typename ScheduleT>
18	symbolic::Expression find_nested_gpu_blocksize(
19	structured_control_flow::Map& node, analysis::AnalysisManager& analysis_manager, GPUDimension dimension
20	) {	24✔
21	auto& loop_analysis = analysis_manager.get<analysis::LoopAnalysis>();	24✔
22	auto loops = loop_analysis.descendants(&node);	24✔
23	loops.insert(&node);	24✔
24
25	// Check for repeated dimensions in loop tree paths
26	auto loop_tree_paths = loop_analysis.loop_tree_paths(&node);	24✔
27	for (auto& path : loop_tree_paths) {	24✔
28	bool foundX = false;	24✔
29	bool foundY = false;	24✔
30	bool foundZ = false;	24✔
31	for (auto& loop : path) {	39✔
32	if (auto map = dynamic_cast<structured_control_flow::StructuredLoop*>(loop)) {	39✔
33	if (map->schedule_type().value() == ScheduleT::value()) {	39✔
34	auto dim = ScheduleT::dimension(map->schedule_type());	39✔
35	if (dim == GPUDimension::X) {	39✔
36	if (foundX) {	12✔
37	throw InvalidSDFGException("Nested map in GPU kernel has repeated X dimension");	×
38	}	×
39	foundX = true;	12✔
40	} else if (dim == GPUDimension::Y) {	27✔
41	if (foundY) {	12✔
42	throw InvalidSDFGException("Nested map in GPU kernel has repeated Y dimension");	×
43	}	×
44	foundY = true;	12✔
45	} else if (dim == GPUDimension::Z) {	15✔
46	if (foundZ) {	15✔
47	throw InvalidSDFGException("Nested map in GPU kernel has repeated Z dimension");	×
48	}	×
49	foundZ = true;	15✔
50	}	15✔
51	}	39✔
52	}	39✔
53	}	39✔
54	}	24✔
55
56	// Find block size for the requested dimension
57	for (auto loop : loops) {	33✔
58	if (auto map = dynamic_cast<structured_control_flow::StructuredLoop*>(loop)) {	33✔
59	if (map->schedule_type().value() != ScheduleT::value() &&	33✔
60	map->schedule_type().value() != structured_control_flow::ScheduleType_Sequential::value()) {	33✔
61	throw InvalidSDFGException("Nested map in GPU kernel not GPU or Sequential");	×
62	}	×
63
64	if (map->schedule_type().value() == structured_control_flow::ScheduleType_Sequential::value()) {	33✔
65	continue;	×
66	}	×
67
68	if (ScheduleT::dimension(map->schedule_type()) == dimension) {	33✔
69	return ScheduleT::block_size(map->schedule_type());	13✔
70	}	13✔
71	}	33✔
72	}	33✔
73	return symbolic::one();	11✔
74	}	24✔
75
76	template<typename ScheduleT>
77	symbolic::Expression find_nested_gpu_iterations(
78	structured_control_flow::Map& node, analysis::AnalysisManager& analysis_manager, GPUDimension dimension
79	) {	24✔
80	auto& loop_analysis = analysis_manager.get<analysis::LoopAnalysis>();	24✔
81	auto loops = loop_analysis.descendants(&node);	24✔
82	loops.insert(&node);	24✔
83
84	symbolic::Expression max_num_iterations = symbolic::one();	24✔
85
86	for (auto loop : loops) {	39✔
87	if (auto map = dynamic_cast<structured_control_flow::StructuredLoop*>(loop)) {	39✔
88	if (map->schedule_type().value() != ScheduleT::value() &&	39✔
89	map->schedule_type().value() != structured_control_flow::ScheduleType_Sequential::value()) {	39✔
90	throw InvalidSDFGException("Nested map in GPU kernel not GPU or Sequential");	×
91	}	×
92	if (map->schedule_type().value() == structured_control_flow::ScheduleType_Sequential::value()) {	39✔
93	continue;	×
94	}	×
95	if (ScheduleT::dimension(map->schedule_type()) != dimension) {	39✔
96	continue;	26✔
97	}	26✔
98
99	// Note: arbitrary `init` and `stride` are permitted here; the
100	// dispatcher emits `indvar = init + thread_flat_id * stride` so
101	// the body sees the natural strided value. `num_iterations()`
102	// already accounts for both.
103	auto num_iterations = map->num_iterations();	13✔
104	if (num_iterations.is_null()) {	13✔
105	throw InvalidSDFGException("Cannot determine number of iterations for nested map in GPU kernel");	×
106	}	×
107	max_num_iterations = symbolic::max(max_num_iterations, num_iterations);	13✔
108	}	13✔
109	}	39✔
110	return max_num_iterations;	24✔
111	}	24✔
112
113	template<typename ScheduleT>
114	bool is_outermost_gpu_map(structured_control_flow::Map& node, analysis::AnalysisManager& analysis_manager) {	16✔
115	auto& loop_analysis = analysis_manager.get<analysis::LoopAnalysis>();	16✔
116	auto& loop_tree = loop_analysis.loop_tree();	16✔
117	structured_control_flow::ControlFlowNode* ancestor = loop_tree.at(&node);	16✔
118	while (ancestor != nullptr) {	16✔
119	if (auto map = dyn_cast<structured_control_flow::Map*>(ancestor)) {	8✔
120	if (map->schedule_type().value() == ScheduleT::value()) {	8✔
121	return false;	8✔
122	}	8✔
123	}	8✔
124	ancestor = loop_tree.at(ancestor);	×
125	}	×
126	return true;	8✔
127	}	16✔
128
129	template<typename ScheduleT>
130	symbolic::SymbolSet get_gpu_indvars(
131	structured_control_flow::Map& node, analysis::AnalysisManager& analysis_manager, GPUDimension dimension
132	) {	24✔
133	auto& loop_analysis = analysis_manager.get<analysis::LoopAnalysis>();	24✔
134	auto loops = loop_analysis.descendants(&node);	24✔
135	loops.insert(&node);	24✔
136	symbolic::SymbolSet indvars;	24✔
137	for (const auto& loop : loops) {	39✔
138	if (auto map = dyn_cast<structured_control_flow::Map*>(loop)) {	39✔
139	if (map->schedule_type().value() == ScheduleT::value()) {	39✔
140	if (ScheduleT::dimension(map->schedule_type()) == dimension) {	39✔
141	indvars.insert(map->indvar());	13✔
142	}	13✔
143	}	39✔
144	}	39✔
145	}	39✔
146	return indvars;	24✔
147	}	24✔
148
149	template<typename ScheduleT>
150	std::vector<structured_control_flow::Map*>
151	get_gpu_maps(structured_control_flow::Map& node, analysis::AnalysisManager& analysis_manager, GPUDimension dimension) {	12✔
152	auto& loop_analysis = analysis_manager.get<analysis::LoopAnalysis>();	12✔
153	auto loops = loop_analysis.descendants(&node);	12✔
154	loops.insert(&node);	12✔
155	std::vector<structured_control_flow::Map*> maps;	12✔
156	for (const auto& loop : loops) {	24✔
157	if (auto map = dyn_cast<structured_control_flow::Map*>(loop)) {	24✔
158	if (map->schedule_type().value() == ScheduleT::value()) {	24✔
159	if (ScheduleT::dimension(map->schedule_type()) == dimension) {	24✔
160	maps.push_back(map);	8✔
161	}	8✔
162	}	24✔
163	}	24✔
164	}	24✔
165	return maps;	12✔
166	}	12✔
167
168	bool nested_parallelization_is_unsafe(
169	structured_control_flow::StructuredLoop& loop, analysis::AnalysisManager& analysis_manager
170	) {	16✔
171	auto& loop_analysis = analysis_manager.get<analysis::LoopAnalysis>();	16✔
172
173	// The outermost enclosing GPU map is the kernel scope. Everything below it is
174	// folded into a single flattened launch, so adding a dimension for `loop`
175	// distributes its iterations across the new dimension's threads and replicates
176	// its siblings (and the siblings of any ancestor up to this map) across them.
177	auto is_parallelized = [](structured_control_flow::Map* map) {	23✔
178	return map->schedule_type().value() != structured_control_flow::ScheduleType_Sequential::value();	23✔
179	};	23✔
180
181	structured_control_flow::Map* outermost = nullptr;	16✔
182	for (auto* ancestor = loop_analysis.parent_loop(&loop); ancestor != nullptr;	34✔
183	ancestor = loop_analysis.parent_loop(ancestor)) {	18✔
184	if (auto* map = dyn_cast<structured_control_flow::Map*>(ancestor)) {	18✔
185	if (is_parallelized(map)) {	17✔
186	outermost = map;	17✔
187	}	17✔
188	}	17✔
189	}	18✔
190	if (outermost == nullptr) {	16✔
191	// No enclosing GPU map: nothing is folded, hence nothing is replicated.
192	return false;	×
193	}	×
194
195	auto& users = analysis_manager.get<analysis::Users>();	16✔
196	auto& arguments_analysis = analysis_manager.get<analysis::ArgumentsAnalysis>();	16✔
197	// Containers whose entire lifetime is confined to the kernel are privatized per
198	// thread (registers/stack, per-thread allocation), so they race nothing. Only a
199	// container that escapes the kernel (function argument/external or a transient
200	// living outside, per ArgumentsAnalysis) is a hazard. Loop induction variables
201	// are locals by definition, so this subsumes loop-control bookkeeping.
202	const auto& locals = arguments_analysis.locals(analysis_manager, *outermost);	16✔
203	auto is_local = [&locals](const std::string& container) { return locals.count(container) != 0; };	19✔
204
205	// Collect the container reads and writes of a subtree. Views alias memory and
206	// are treated conservatively as both a read and a write.
207	auto collect = [&](structured_control_flow::ControlFlowNode& node,	16✔
208	std::unordered_set<std::string>& writes,	16✔
209	std::unordered_set<std::string>& reads) {	22✔
210	analysis::UsersView view(users, node);	22✔
211	for (auto* u : view.writes()) {	78✔
212	writes.insert(u->container());	78✔
213	}	78✔
214	for (auto* u : view.moves()) {	22✔
215	writes.insert(u->container());	×
216	}	×
217	for (auto* u : view.views()) {	22✔
UNCOV 218	writes.insert(u->container());	×
219	reads.insert(u->container());	×
220	}	×
221	for (auto* u : view.reads()) {	168✔
222	reads.insert(u->container());	168✔
223	}	168✔
224	};	22✔
225
226	// `loop`'s writes vary across the new dimension (its iterations are distributed),
227	// so any replicated sibling that touches one of these shared containers races.
228	std::unordered_set<std::string> loop_writes;	16✔
229	std::unordered_set<std::string> loop_reads;	16✔
230	collect(loop, loop_writes, loop_reads);	16✔
231
232	// A subtree performs an unsafe self-accumulation if it reads and writes the same
233	// non-local container (e.g. `acc[i] += x`). A plain store is idempotent under
234	// replication and therefore allowed.
235	auto accumulates_on_shared = [&](const std::unordered_set<std::string>& writes,	16✔
236	const std::unordered_set<std::string>& reads) {	16✔
237	for (const auto& container : writes) {	7✔
238	if (reads.count(container) != 0 && !is_local(container)) {	7✔
239	return true;	2✔
240	}	2✔
241	}	7✔
242	return false;	2✔
243	};	4✔
244
245	// Walk from `loop` up to (but excluding) the outermost GPU map, inspecting the
246	// siblings at each level. Siblings above the kernel are not replicated and are
247	// therefore not considered.
248	structured_control_flow::ControlFlowNode* node = &loop;	16✔
249	while (node != outermost) {	31✔
250	auto* sequence = dynamic_cast<structured_control_flow::Sequence*>(node->get_parent());	17✔
251	if (sequence == nullptr) {	17✔
252	break;	×
253	}	×
254	for (size_t i = 0; i < sequence->size(); ++i) {	36✔
255	auto& sibling = sequence->at(i);	21✔
256	if (&sibling == node) {	21✔
257	continue;	15✔
258	}	15✔
259
260	std::unordered_set<std::string> sibling_writes;	6✔
261	std::unordered_set<std::string> sibling_reads;	6✔
262	collect(sibling, sibling_writes, sibling_reads);	6✔
263
264	// Hazard 1 (producer/consumer across the fold): a shared container that
265	// `loop` writes is read or written by a replicated sibling. `loop`'s
266	// writes vary across the new dimension, so the sibling observes another
267	// thread's incomplete data without synchronization. This is the reduce
268	// accumulator -> consumer race (softmax: reduce writes acc[i], a sibling
269	// divides by acc[i]). Applies even if the sibling is itself a GPU map.
270	for (const auto& container : loop_writes) {	12✔
271	if (is_local(container)) {	12✔
272	continue;	6✔
273	}	6✔
274	if (sibling_writes.count(container) != 0 \|\| sibling_reads.count(container) != 0) {	6✔
NEW 275	return true;	×
NEW 276	}	×
277	}	6✔
278
279	// Hazard 2 (replicated self-accumulation): a sibling read-modify-writes a
280	// shared container. A sibling that is itself a GPU map is exempt: codegen
281	// maps it onto its own threads instead of replicating it.
282	if (auto* sibling_map = dyn_cast<structured_control_flow::Map*>(&sibling)) {	6✔
283	if (is_parallelized(sibling_map)) {	6✔
284	continue;	2✔
285	}	2✔
286	}	6✔
287	if (accumulates_on_shared(sibling_writes, sibling_reads)) {	4✔
288	return true;	2✔
289	}	2✔
290	}	4✔
291	node = sequence->get_parent();	15✔
292	if (node == nullptr) {	15✔
293	break;	×
294	}	×
295	}	15✔
296
297	return false;	14✔
298	}	16✔
299
300
301	// Explicit template instantiations for CUDA
302	template symbolic::Expression find_nested_gpu_blocksize<cuda::ScheduleType_CUDA>(
303	structured_control_flow::Map& node, analysis::AnalysisManager& analysis_manager, GPUDimension dimension
304	);
305
306	template symbolic::Expression find_nested_gpu_iterations<cuda::ScheduleType_CUDA>(
307	structured_control_flow::Map& node, analysis::AnalysisManager& analysis_manager, GPUDimension dimension
308	);
309
310	template bool is_outermost_gpu_map<
311	cuda::ScheduleType_CUDA>(structured_control_flow::Map& node, analysis::AnalysisManager& analysis_manager);
312
313	template symbolic::SymbolSet get_gpu_indvars<cuda::ScheduleType_CUDA>(
314	structured_control_flow::Map& node, analysis::AnalysisManager& analysis_manager, GPUDimension dimension
315	);
316
317	template std::vector<structured_control_flow::Map*> get_gpu_maps<cuda::ScheduleType_CUDA>(
318	structured_control_flow::Map& node, analysis::AnalysisManager& analysis_manager, GPUDimension dimension
319	);
320
321	// Explicit template instantiations for ROCM
322	template symbolic::Expression find_nested_gpu_blocksize<rocm::ScheduleType_ROCM>(
323	structured_control_flow::Map& node, analysis::AnalysisManager& analysis_manager, GPUDimension dimension
324	);
325
326	template symbolic::Expression find_nested_gpu_iterations<rocm::ScheduleType_ROCM>(
327	structured_control_flow::Map& node, analysis::AnalysisManager& analysis_manager, GPUDimension dimension
328	);
329
330	template bool is_outermost_gpu_map<
331	rocm::ScheduleType_ROCM>(structured_control_flow::Map& node, analysis::AnalysisManager& analysis_manager);
332
333	template symbolic::SymbolSet get_gpu_indvars<rocm::ScheduleType_ROCM>(
334	structured_control_flow::Map& node, analysis::AnalysisManager& analysis_manager, GPUDimension dimension
335	);
336
337	template std::vector<structured_control_flow::Map*> get_gpu_maps<rocm::ScheduleType_ROCM>(
338	structured_control_flow::Map& node, analysis::AnalysisManager& analysis_manager, GPUDimension dimension
339	);
340
341	} // namespace gpu
342	} // namespace sdfg

daisytuner / docc / 31009380971

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