28158800507

Committed 25 Jun 2026 08:57AM UTC coverage: 61.644% (+0.06%) from 61.582%

Build # 28158800507

Build Type

push

github

Committed by

web-flow

Commit Message

MapFusionByDomain (#771)

 + New Map fusion caches data about iteration domain and map candidates
 + only matches up iteration domain exactly, per loop level.
 + Can support fusing non-leaf stacks of loops (stack ends where the shallower stack stops being perfectly nested & parallel)
 + new Element::replace for bulk replacements
 + New PatternMatcher visitor supports descending into replaced or modified nodes to allow for single-pass nested loop fusings
 + LoopAnalysis can now be kept up-to-date with changes done by Map-fusion
 + unit tests for the updating of LoopAnalysis
 * updated LoopAnalysis to be easier to keep up-to-date with changes. LoopTree is no longer ordered, if you want to iterate in pre-order, use the specific method for that
 + convenience StructuredSDFGBuilder.remove_from_parent()
 + RedundantLoadElim pass to skip reading from memory locations that have just been written (same block). Fusing no longer needs to do this
     RedundantLoadElimination does a simple check for other writes to the same structure. Can skip writes if redundant or not modify, if their are writes to different indices
* Updated verifiers to match new fusion
~ moved verifier checks behind correctness checks in npbench harness. Its more critical if we do not even get the expected results
* Added MapFusionByDomain also to loop-norm stage (currently inactive, causes more kernels that currently cannot be safely offloaded to CUDA.
---------

Co-authored-by: Lukas Truemper <lukas.truemper@outlook.de>

Coverage Stats

771 of 1186 new or added lines in 55 files covered. (65.01%)

6 existing lines in 6 files now uncovered.

38302 of 62134 relevant lines covered (61.64%)

987.24 hits per line

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

45.59

/sdfg/src/data_flow/library_nodes/stdlib/memmove.cpp

#include "sdfg/data_flow/library_nodes/stdlib/memmove.h"

namespace sdfg {
namespace stdlib {

MemmoveNode::MemmoveNode(
    size_t element_id,
    const DebugInfo& debug_info,
    const graph::Vertex vertex,
    data_flow::DataFlowGraph& parent,
    const symbolic::Expression count
)
    : StdlibNode(
          element_id,
          debug_info,
          vertex,
          parent,
          LibraryNodeType_Memmove,
          {},
          {"_dst", "_src"},
          true,
          data_flow::ImplementationType_NONE
      ),
      count_(count) {}

const symbolic::Expression MemmoveNode::count() const { return count_; }

void MemmoveNode::validate(const Function& function) const { LibraryNode::validate(function); }

symbolic::SymbolSet MemmoveNode::symbols() const {
    auto count_symbols = symbolic::atoms(this->count_);
    return count_symbols;
}

std::unique_ptr<data_flow::DataFlowNode> MemmoveNode::
    clone(size_t element_id, const graph::Vertex vertex, data_flow::DataFlowGraph& parent) const {
    return std::make_unique<MemmoveNode>(element_id, debug_info_, vertex, parent, count_);
}

void MemmoveNode::replace(const symbolic::Expression old_expression, const symbolic::Expression new_expression) {
    this->count_ = symbolic::subs(this->count_, old_expression, new_expression);
}

void MemmoveNode::replace(const symbolic::ExpressionMapping& replacements) {
    this->count_ = symbolic::subs(this->count_, replacements);
}

nlohmann::json MemmoveNodeSerializer::serialize(const data_flow::LibraryNode& library_node) {
    const MemmoveNode& node = static_cast<const MemmoveNode&>(library_node);

    nlohmann::json j;
    j["code"] = node.code().value();

    sdfg::serializer::JSONSerializer serializer;
    j["count"] = serializer.expression(node.count());

    return j;
}

data_flow::LibraryNode& MemmoveNodeSerializer::deserialize(
    const nlohmann::json& j, builder::StructuredSDFGBuilder& builder, structured_control_flow::Block& parent
) {
    assert(j.contains("code"));
    assert(j.contains("debug_info"));
    assert(j.contains("count"));

    auto code = j["code"].get<std::string>();
    if (code != LibraryNodeType_Memmove.value()) {
        throw InvalidSDFGException("Invalid library node code");
    }

    // Extract debug info using JSONSerializer
    sdfg::serializer::JSONSerializer serializer;
    DebugInfo debug_info = serializer.json_to_debug_info(j["debug_info"]);

    // Extract properties
    auto count = symbolic::parse(j.at("count"));

    return builder.add_library_node<MemmoveNode>(parent, debug_info, count);
}

MemmoveNodeDispatcher::MemmoveNodeDispatcher(
    codegen::LanguageExtension& language_extension,
    const Function& function,
    const data_flow::DataFlowGraph& data_flow_graph,
    const MemmoveNode& node
)
    : codegen::LibraryNodeDispatcher(language_extension, function, data_flow_graph, node) {}

void MemmoveNodeDispatcher::dispatch_code_with_edges(
    codegen::CodegenOutput& out,
    std::vector<codegen::DispatchInput>& inputs,
    std::vector<codegen::DispatchOutput>& outputs
) {
    auto& node = static_cast<const MemmoveNode&>(node_);

    out.stream << language_extension_.external_prefix() << "memmove(" << inputs.at(0).expr << ", " << inputs.at(1).expr
               << ", " << language_extension_.expression(node.count()) << ")" << ";";
    out.stream << std::endl;
}

MemmoveNode& add_memmove_node(
    builder::StructuredSDFGBuilder& builder,
    Block& block,
    const std::string& src_ptr,
    const std::string& dst_ptr,
    const symbolic::Expression& count,
    const types::IType& ptr_type,
    DebugInfo debug_info
) {
    auto& src_ptr_access = builder.add_access(block, src_ptr);
    auto& dst_ptr_access = builder.add_access(block, dst_ptr);
    auto& libnode = builder.add_library_node<stdlib::MemmoveNode>(block, debug_info, count);
    builder.add_computational_memlet(block, src_ptr_access, libnode, "_src", {}, ptr_type);
    builder.add_computational_memlet(block, dst_ptr_access, libnode, "_dst", {}, ptr_type);

    return static_cast<MemmoveNode&>(libnode);
}

std::tuple<Block&, MemmoveNode&> add_memmove_block(
    builder::StructuredSDFGBuilder& builder,
    Sequence& parent,
    const std::string& src_ptr,
    const std::string& dst_ptr,
    const symbolic::Expression& count,
    const types::IType& ptr_type,
    DebugInfo debug_info
) {
    auto& block = builder.add_block(parent);

    auto& libnode = add_memmove_node(builder, block, src_ptr, dst_ptr, count, ptr_type, debug_info);

    return {block, libnode};
}

} // namespace stdlib
} // namespace sdfg

1	#include "sdfg/data_flow/library_nodes/stdlib/memmove.h"
2
3	namespace sdfg {
4	namespace stdlib {
5
6	MemmoveNode::MemmoveNode(
7	size_t element_id,
8	const DebugInfo& debug_info,
9	const graph::Vertex vertex,
10	data_flow::DataFlowGraph& parent,
11	const symbolic::Expression count
12	)
13	: StdlibNode(	8✔
14	element_id,	8✔
15	debug_info,	8✔
16	vertex,	8✔
17	parent,	8✔
18	LibraryNodeType_Memmove,	8✔
19	{},	8✔
20	{"_dst", "_src"},	8✔
21	true,	8✔
22	data_flow::ImplementationType_NONE	8✔
23	),	8✔
24	count_(count) {}	8✔
25
26	const symbolic::Expression MemmoveNode::count() const { return count_; }	4✔
27
28	void MemmoveNode::validate(const Function& function) const { LibraryNode::validate(function); }	6✔
29
30	symbolic::SymbolSet MemmoveNode::symbols() const {	2✔
31	auto count_symbols = symbolic::atoms(this->count_);	2✔
32	return count_symbols;	2✔
33	}	2✔
34
35	std::unique_ptr<data_flow::DataFlowNode> MemmoveNode::
36	clone(size_t element_id, const graph::Vertex vertex, data_flow::DataFlowGraph& parent) const {	×
37	return std::make_unique<MemmoveNode>(element_id, debug_info_, vertex, parent, count_);	×
38	}	×
39
40	void MemmoveNode::replace(const symbolic::Expression old_expression, const symbolic::Expression new_expression) {	×
41	this->count_ = symbolic::subs(this->count_, old_expression, new_expression);	×
42	}	×
43
NEW 44	void MemmoveNode::replace(const symbolic::ExpressionMapping& replacements) {	×
NEW 45	this->count_ = symbolic::subs(this->count_, replacements);	×
NEW 46	}	×
47
48	nlohmann::json MemmoveNodeSerializer::serialize(const data_flow::LibraryNode& library_node) {	×
49	const MemmoveNode& node = static_cast<const MemmoveNode&>(library_node);	×
50
51	nlohmann::json j;	×
52	j["code"] = node.code().value();	×
53
54	sdfg::serializer::JSONSerializer serializer;	×
55	j["count"] = serializer.expression(node.count());	×
56
57	return j;	×
58	}	×
59
60	data_flow::LibraryNode& MemmoveNodeSerializer::deserialize(
61	const nlohmann::json& j, builder::StructuredSDFGBuilder& builder, structured_control_flow::Block& parent
62	) {	×
63	assert(j.contains("code"));	×
64	assert(j.contains("debug_info"));	×
65	assert(j.contains("count"));	×
66
67	auto code = j["code"].get<std::string>();	×
68	if (code != LibraryNodeType_Memmove.value()) {	×
69	throw InvalidSDFGException("Invalid library node code");	×
70	}	×
71
72	// Extract debug info using JSONSerializer
73	sdfg::serializer::JSONSerializer serializer;	×
74	DebugInfo debug_info = serializer.json_to_debug_info(j["debug_info"]);	×
75
76	// Extract properties
77	auto count = symbolic::parse(j.at("count"));	×
78
79	return builder.add_library_node<MemmoveNode>(parent, debug_info, count);	×
80	}	×
81
82	MemmoveNodeDispatcher::MemmoveNodeDispatcher(
83	codegen::LanguageExtension& language_extension,
84	const Function& function,
85	const data_flow::DataFlowGraph& data_flow_graph,
86	const MemmoveNode& node
87	)
88	: codegen::LibraryNodeDispatcher(language_extension, function, data_flow_graph, node) {}	×
89
90	void MemmoveNodeDispatcher::dispatch_code_with_edges(
91	codegen::CodegenOutput& out,
92	std::vector<codegen::DispatchInput>& inputs,
93	std::vector<codegen::DispatchOutput>& outputs
94	) {	×
95	auto& node = static_cast<const MemmoveNode&>(node_);	×
96
97	out.stream << language_extension_.external_prefix() << "memmove(" << inputs.at(0).expr << ", " << inputs.at(1).expr	×
98	<< ", " << language_extension_.expression(node.count()) << ")" << ";";	×
99	out.stream << std::endl;	×
100	}	×
101
102	MemmoveNode& add_memmove_node(
103	builder::StructuredSDFGBuilder& builder,
104	Block& block,
105	const std::string& src_ptr,
106	const std::string& dst_ptr,
107	const symbolic::Expression& count,
108	const types::IType& ptr_type,
109	DebugInfo debug_info
110	) {	8✔
111	auto& src_ptr_access = builder.add_access(block, src_ptr);	8✔
112	auto& dst_ptr_access = builder.add_access(block, dst_ptr);	8✔
113	auto& libnode = builder.add_library_node<stdlib::MemmoveNode>(block, debug_info, count);	8✔
114	builder.add_computational_memlet(block, src_ptr_access, libnode, "_src", {}, ptr_type);	8✔
115	builder.add_computational_memlet(block, dst_ptr_access, libnode, "_dst", {}, ptr_type);	8✔
116
117	return static_cast<MemmoveNode&>(libnode);	8✔
118	}	8✔
119
120	std::tuple<Block&, MemmoveNode&> add_memmove_block(
121	builder::StructuredSDFGBuilder& builder,
122	Sequence& parent,
123	const std::string& src_ptr,
124	const std::string& dst_ptr,
125	const symbolic::Expression& count,
126	const types::IType& ptr_type,
127	DebugInfo debug_info
128	) {	8✔
129	auto& block = builder.add_block(parent);	8✔
130
131	auto& libnode = add_memmove_node(builder, block, src_ptr, dst_ptr, count, ptr_type, debug_info);	8✔
132
133	return {block, libnode};	8✔
134	}	8✔
135
136	} // namespace stdlib
137	} // namespace sdfg

daisytuner / docc / 28158800507

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