24251733303

Committed 10 Apr 2026 03:55PM UTC coverage: 64.159% (-0.2%) from 64.376%

Build # 24251733303

Build Type

Pull #673

github

Committed by

web-flow

Commit Message

Merge b555ef1c7 into ccfd1d376

Pull Request Pull Request #673: Data flow transfer elimination

Coverage Stats

381 of 542 new or added lines in 12 files covered. (70.3%)

112 existing lines in 3 files now uncovered.

30169 of 47022 relevant lines covered (64.16%)

578.46 hits per line

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

81.63

/opt/src/analysis/data_transfer_elimination_analysis.cpp

#include "sdfg/analysis/data_transfer_elimination_analysis.h"


#include "sdfg/targets/cuda/cuda.h"
#include "sdfg/targets/offloading/data_offloading_node.h"

namespace sdfg::analysis {

OffloadState::OffloadState(DataTransferEliminationCandidateCollector& collector) : collector_(collector) {}

void OffloadState::found_escape(const std::string& container) { kills_containers_.insert(container); }

void OffloadState::found_ptr_write(const std::string& container, const data_flow::Memlet* memlet) {
    kills_containers_.insert(container);
}

void OffloadState::found_ptr_read(const std::string& container, const data_flow::Memlet* memlet) {
    // todo check with generated set if its ever possible for it to contain the transfer and a use
    reads_[container].push_back(memlet);
}

void OffloadState::found_full_barrier(ControlFlowNode& node) {
    generated_.clear(); // all generateds are from before and now wiped
    full_kill_ = true;
}

/**
 * @return { candidate_for_elimination, killing node }
 */
std::pair<bool, const OffloadHolder*> OffloadState::find_killing_entry_node(const OffloadHolder& exit_node) const {
    auto& host_access_type = exit_node.host_access->base_type();
    for (const auto& entry_node : kernel_entry_nodes_ | std::views::values) {
        if (entry_node.host_data->data() == exit_node.host_data->data()) {
            bool is_elim_candidate = exit_node.node->redundant_with(*entry_node.node);
            return {is_elim_candidate, &entry_node};
        } else if (host_access_type == entry_node.host_access->base_type()) { // aliases
            // return &entry_node; // TODO left unhandled for now, because then most situations like a matmul could
            // never be eliminated
        }
    }

    return {false, nullptr};
}

void OffloadState::found_offload_node(Block& block, offloading::DataOffloadingNode& offload) {
    auto& dflow = block.dataflow();

    bool src_is_dev = false;
    bool src_is_host = false;
    bool dst_is_dev = false;
    bool dst_is_host = false;

    if (is_D2H(offload.transfer_direction())) {
        src_is_dev = true;
        dst_is_host = true;
    } else if (is_H2D(offload.transfer_direction())) {
        src_is_host = true;
        dst_is_dev = true;
    }

    const data_flow::AccessNode* found_dev_access = nullptr;
    const data_flow::AccessNode* found_host_access = nullptr;
    const data_flow::Memlet* found_host_memlet = nullptr;

    for (auto& conn : offload.inputs()) {
        auto* memlet = dflow.in_edge_for_connector(offload, conn);
        auto* access_node = dynamic_cast<const data_flow::AccessNode*>(&memlet->src());

        if (src_is_host) {
            found_host_access = access_node;
            found_host_memlet = memlet;
        }
        if (src_is_dev) {
            found_dev_access = access_node;
        }
    }

    for (auto& conn : offload.outputs()) {
        auto edges = dflow.out_edges_for_connector(offload, conn);
        if (edges.size() > 1) {
            throw std::runtime_error(
                "Unsupported: offload node " + std::to_string(offload.element_id()) +
                " with multiple outputs edges on " + conn
            );
        }
        auto* memlet = edges.at(0);
        auto* access_node = dynamic_cast<const data_flow::AccessNode*>(&memlet->dst());

        if (dst_is_host) {
            found_host_access = access_node;
            found_host_memlet = memlet;
        }
        if (dst_is_dev) {
            found_dev_access = access_node;
        }
    }

    if (found_host_access && found_dev_access) {
        if (dst_is_host) {
            generated_.emplace(
                offload.element_id(),
                std::make_unique<OffloadHolder>(&offload, found_host_access, found_host_memlet, found_dev_access)
            );
        } else {
            add_h2d_entry(OffloadHolder{&offload, found_host_access, found_host_memlet, found_dev_access});
        }
    }
}

void OffloadState::add_h2d_entry(const OffloadHolder& entry) {
    kernel_entry_nodes_.emplace(entry.node->element_id(), entry);
    // todo also need to remove generated ones killed by this. But right now
}

ExposedOffload OffloadState::expose(OffloadHolder& holder) { return ExposedOffload{&holder, 0}; }

void OffloadState::apply_kills_and_changes(ExposedType& exposed) const {
    if (full_kill_) {
        exposed.clear();
        return;
    }
    for (auto it = exposed.begin(); it != exposed.end();) {
        auto& [id, exposedOffload] = *it;
        auto* host = exposedOffload.offload->host_data;
        auto& host_container = host->data();

        auto host_reads = reads_.find(host_container);
        if (host_reads != reads_.end() && host_reads->second.size() > 0) {
            ++exposedOffload.read_count;
        }

        if (host && kills_containers_.contains(host_container)) {
            it = exposed.erase(it);
            continue;
        }

        auto [is_elim_candidate, killing_entry] = find_killing_entry_node(*exposedOffload.offload);
        if (killing_entry) {
            if (is_elim_candidate) {
                collector_.found_candidate_pair(exposedOffload, *killing_entry);
            }
            it = exposed.erase(it);
            continue;
        }
        ++it;
    }
}


void DataTransferEliminationAnalysis::handle_lib_node(Block& block, data_flow::LibraryNode& node) {
    BaseUserVisitor::handle_lib_node(block, node);

    if (auto* offload_node = dynamic_cast<offloading::DataOffloadingNode*>(&node)) {
        get_or_create_state(block).found_offload_node(block, *offload_node);
    }
}

void DataTransferEliminationAnalysis::handle_structured_loop_before_body(StructuredLoop& loop) {
    BaseUserVisitor::handle_structured_loop_before_body(loop);

    // auto* map = dynamic_cast<sdfg::structured_control_flow::Map*>(&loop);

    // if (map && map->schedule_type().category() == ScheduleTypeCategory::Offloader) {
    //     get_or_create_state(loop).found_offloaded_kernel(*map);
    // }
}

void DataTransferEliminationAnalysis::
    on_escape(const std::string& container, const ControlFlowNode* node, const Element* user) {
    if (dynamic_cast<const Block*>(node)) {
        if (auto* memlet = dynamic_cast<const data_flow::Memlet*>(user)) {
            if (auto* offload = dynamic_cast<const offloading::DataOffloadingNode*>(&memlet->dst())) {
                // accesses of offloading nodes are handled more intelligently in found_offload_node, so ignore them
                // here
                return;
            }
        }
    }
    get_or_create_state(*node).found_escape(container);
}

void DataTransferEliminationAnalysis::
    on_read_via(const std::string& container, const ControlFlowNode* node, const data_flow::Memlet* user) {
    if (!dynamic_cast<const offloading::DataOffloadingNode*>(&user->dst())) {
        get_or_create_state(*node).found_ptr_read(container, user);
    }
}

void DataTransferEliminationAnalysis::
    on_write_via(const std::string& container, const ControlFlowNode* node, const data_flow::Memlet* user) {
    if (!dynamic_cast<const offloading::DataOffloadingNode*>(&user->dst())) {
        get_or_create_state(*node).found_ptr_write(container, user);
    }
}

std::unique_ptr<OffloadState> DataTransferEliminationAnalysis::
    create_initial_state(const structured_control_flow::ControlFlowNode& node) {
    return std::make_unique<OffloadState>(*this);
}

void DataTransferEliminationAnalysis::run() {
    dispatch(sdfg_.root());

    run_forward(sdfg_.root());
}

} // namespace sdfg::analysis

1	#include "sdfg/analysis/data_transfer_elimination_analysis.h"
2
3
4	#include "sdfg/targets/cuda/cuda.h"
5	#include "sdfg/targets/offloading/data_offloading_node.h"
6
7	namespace sdfg::analysis {
8
9	OffloadState::OffloadState(DataTransferEliminationCandidateCollector& collector) : collector_(collector) {}	9✔
10
NEW 11	void OffloadState::found_escape(const std::string& container) { kills_containers_.insert(container); }	×
12
13	void OffloadState::found_ptr_write(const std::string& container, const data_flow::Memlet* memlet) {	1✔
14	kills_containers_.insert(container);	1✔
15	}	1✔
16
17	void OffloadState::found_ptr_read(const std::string& container, const data_flow::Memlet* memlet) {	1✔
18	// todo check with generated set if its ever possible for it to contain the transfer and a use
19	reads_[container].push_back(memlet);	1✔
20	}	1✔
21
NEW 22	void OffloadState::found_full_barrier(ControlFlowNode& node) {	×
NEW 23	generated_.clear(); // all generateds are from before and now wiped	×
NEW 24	full_kill_ = true;	×
NEW 25	}	×
26
27	/**
28	* @return { candidate_for_elimination, killing node }
29	*/
30	std::pair<bool, const OffloadHolder*> OffloadState::find_killing_entry_node(const OffloadHolder& exit_node) const {	2✔
31	auto& host_access_type = exit_node.host_access->base_type();	2✔
32	for (const auto& entry_node : kernel_entry_nodes_ \| std::views::values) {	2✔
33	if (entry_node.host_data->data() == exit_node.host_data->data()) {	2✔
34	bool is_elim_candidate = exit_node.node->redundant_with(*entry_node.node);	2✔
35	return {is_elim_candidate, &entry_node};	2✔
36	} else if (host_access_type == entry_node.host_access->base_type()) { // aliases	2✔
37	// return &entry_node; // TODO left unhandled for now, because then most situations like a matmul could
38	// never be eliminated
NEW 39	}	×
40	}	2✔
41
NEW 42	return {false, nullptr};	×
43	}	2✔
44
45	void OffloadState::found_offload_node(Block& block, offloading::DataOffloadingNode& offload) {	5✔
46	auto& dflow = block.dataflow();	5✔
47
48	bool src_is_dev = false;	5✔
49	bool src_is_host = false;	5✔
50	bool dst_is_dev = false;	5✔
51	bool dst_is_host = false;	5✔
52
53	if (is_D2H(offload.transfer_direction())) {	5✔
54	src_is_dev = true;	3✔
55	dst_is_host = true;	3✔
56	} else if (is_H2D(offload.transfer_direction())) {	3✔
57	src_is_host = true;	2✔
58	dst_is_dev = true;	2✔
59	}	2✔
60
61	const data_flow::AccessNode* found_dev_access = nullptr;	5✔
62	const data_flow::AccessNode* found_host_access = nullptr;	5✔
63	const data_flow::Memlet* found_host_memlet = nullptr;	5✔
64
65	for (auto& conn : offload.inputs()) {	5✔
66	auto* memlet = dflow.in_edge_for_connector(offload, conn);	5✔
67	auto* access_node = dynamic_cast<const data_flow::AccessNode*>(&memlet->src());	5✔
68
69	if (src_is_host) {	5✔
70	found_host_access = access_node;	2✔
71	found_host_memlet = memlet;	2✔
72	}	2✔
73	if (src_is_dev) {	5✔
74	found_dev_access = access_node;	3✔
75	}	3✔
76	}	5✔
77
78	for (auto& conn : offload.outputs()) {	5✔
79	auto edges = dflow.out_edges_for_connector(offload, conn);	5✔
80	if (edges.size() > 1) {	5✔
NEW 81	throw std::runtime_error(	×
NEW 82	"Unsupported: offload node " + std::to_string(offload.element_id()) +	×
NEW 83	" with multiple outputs edges on " + conn	×
NEW 84	);	×
NEW 85	}	×
86	auto* memlet = edges.at(0);	5✔
87	auto* access_node = dynamic_cast<const data_flow::AccessNode*>(&memlet->dst());	5✔
88
89	if (dst_is_host) {	5✔
90	found_host_access = access_node;	3✔
91	found_host_memlet = memlet;	3✔
92	}	3✔
93	if (dst_is_dev) {	5✔
94	found_dev_access = access_node;	2✔
95	}	2✔
96	}	5✔
97
98	if (found_host_access && found_dev_access) {	5✔
99	if (dst_is_host) {	5✔
100	generated_.emplace(	3✔
101	offload.element_id(),	3✔
102	std::make_unique<OffloadHolder>(&offload, found_host_access, found_host_memlet, found_dev_access)	3✔
103	);	3✔
104	} else {	3✔
105	add_h2d_entry(OffloadHolder{&offload, found_host_access, found_host_memlet, found_dev_access});	2✔
106	}	2✔
107	}	5✔
108	}	5✔
109
110	void OffloadState::add_h2d_entry(const OffloadHolder& entry) {	2✔
111	kernel_entry_nodes_.emplace(entry.node->element_id(), entry);	2✔
112	// todo also need to remove generated ones killed by this. But right now
113	}	2✔
114
115	ExposedOffload OffloadState::expose(OffloadHolder& holder) { return ExposedOffload{&holder, 0}; }	3✔
116
117	void OffloadState::apply_kills_and_changes(ExposedType& exposed) const {	6✔
118	if (full_kill_) {	6✔
NEW 119	exposed.clear();	×
NEW 120	return;	×
NEW 121	}	×
122	for (auto it = exposed.begin(); it != exposed.end();) {	8✔
123	auto& [id, exposedOffload] = *it;	2✔
124	auto* host = exposedOffload.offload->host_data;	2✔
125	auto& host_container = host->data();	2✔
126
127	auto host_reads = reads_.find(host_container);	2✔
128	if (host_reads != reads_.end() && host_reads->second.size() > 0) {	2✔
NEW 129	++exposedOffload.read_count;	×
NEW 130	}	×
131
132	if (host && kills_containers_.contains(host_container)) {	2✔
NEW 133	it = exposed.erase(it);	×
NEW 134	continue;	×
NEW 135	}	×
136
137	auto [is_elim_candidate, killing_entry] = find_killing_entry_node(*exposedOffload.offload);	2✔
138	if (killing_entry) {	2✔
139	if (is_elim_candidate) {	2✔
140	collector_.found_candidate_pair(exposedOffload, *killing_entry);	2✔
141	}	2✔
142	it = exposed.erase(it);	2✔
143	continue;	2✔
144	}	2✔
NEW 145	++it;	×
NEW 146	}	×
147	}	6✔
148
149
150	void DataTransferEliminationAnalysis::handle_lib_node(Block& block, data_flow::LibraryNode& node) {	5✔
151	BaseUserVisitor::handle_lib_node(block, node);	5✔
152
153	if (auto* offload_node = dynamic_cast<offloading::DataOffloadingNode*>(&node)) {	5✔
154	get_or_create_state(block).found_offload_node(block, *offload_node);	5✔
155	}	5✔
156	}	5✔
157
NEW 158	void DataTransferEliminationAnalysis::handle_structured_loop_before_body(StructuredLoop& loop) {	×
NEW 159	BaseUserVisitor::handle_structured_loop_before_body(loop);	×
160
161	// auto* map = dynamic_cast<sdfg::structured_control_flow::Map*>(&loop);
162
163	// if (map && map->schedule_type().category() == ScheduleTypeCategory::Offloader) {
164	// get_or_create_state(loop).found_offloaded_kernel(*map);
165	// }
NEW 166	}	×
167
168	void DataTransferEliminationAnalysis::
169	on_escape(const std::string& container, const ControlFlowNode* node, const Element* user) {	5✔
170	if (dynamic_cast<const Block*>(node)) {	5✔
171	if (auto* memlet = dynamic_cast<const data_flow::Memlet*>(user)) {	5✔
172	if (auto* offload = dynamic_cast<const offloading::DataOffloadingNode*>(&memlet->dst())) {	5✔
173	// accesses of offloading nodes are handled more intelligently in found_offload_node, so ignore them
174	// here
175	return;	5✔
176	}	5✔
177	}	5✔
178	}	5✔
NEW 179	get_or_create_state(*node).found_escape(container);	×
NEW 180	}	×
181
182	void DataTransferEliminationAnalysis::
183	on_read_via(const std::string& container, const ControlFlowNode* node, const data_flow::Memlet* user) {	1✔
184	if (!dynamic_cast<const offloading::DataOffloadingNode*>(&user->dst())) {	1✔
185	get_or_create_state(*node).found_ptr_read(container, user);	1✔
186	}	1✔
187	}	1✔
188
189	void DataTransferEliminationAnalysis::
190	on_write_via(const std::string& container, const ControlFlowNode* node, const data_flow::Memlet* user) {	1✔
191	if (!dynamic_cast<const offloading::DataOffloadingNode*>(&user->dst())) {	1✔
192	get_or_create_state(*node).found_ptr_write(container, user);	1✔
193	}	1✔
194	}	1✔
195
196	std::unique_ptr<OffloadState> DataTransferEliminationAnalysis::
197	create_initial_state(const structured_control_flow::ControlFlowNode& node) {	9✔
198	return std::make_unique<OffloadState>(*this);	9✔
199	}	9✔
200
201	void DataTransferEliminationAnalysis::run() {	3✔
202	dispatch(sdfg_.root());	3✔
203
204	run_forward(sdfg_.root());	3✔
205	}	3✔
206
207	} // namespace sdfg::analysis

daisytuner / docc / 24251733303

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