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

0.0

/sdfg/src/data_flow/library_nodes/invoke_node.cpp

#include "sdfg/data_flow/library_nodes/invoke_node.h"

namespace sdfg {
namespace data_flow {

InvokeNode::InvokeNode(
    size_t element_id,
    const DebugInfo& debug_info,
    const graph::Vertex vertex,
    data_flow::DataFlowGraph& parent,
    const std::string& callee_name,
    const std::vector<std::string>& outputs,
    const std::vector<std::string>& inputs
)
    : LibraryNode(
          element_id,
          debug_info,
          vertex,
          parent,
          LibraryNodeType_Invoke,
          outputs,
          inputs,
          true,
          data_flow::ImplementationType_NONE
      ),
      callee_name_(callee_name) {
    this->outputs_.push_back("_unwind"); // Add unwind output
}

const std::string& InvokeNode::callee_name() const { return this->callee_name_; }

bool InvokeNode::is_void(const Function& sdfg) const { return outputs_.size() == 1 || outputs_.at(0) != "_ret"; }

bool InvokeNode::is_indirect_call(const Function& sdfg) const {
    auto& type = sdfg.type(this->callee_name_);
    return dynamic_cast<const types::Pointer*>(&type) != nullptr;
}

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

    if (!function.exists(this->callee_name_)) {
        throw InvalidSDFGException("InvokeNode: Function '" + this->callee_name_ + "' does not exist.");
    }
    auto& type = function.type(this->callee_name_);
    if (!dynamic_cast<const types::Function*>(&type) && !dynamic_cast<const types::Pointer*>(&type)) {
        throw InvalidSDFGException("InvokeNode: '" + this->callee_name_ + "' is not a function or pointer.");
    }

    if (auto func_type = dynamic_cast<const types::Function*>(&type)) {
        if (!function.is_external(this->callee_name_)) {
            throw InvalidSDFGException("InvokeNode: Function '" + this->callee_name_ + "' must be declared.");
        }
        if (!func_type->is_var_arg() && inputs_.size() != func_type->num_params()) {
            throw InvalidSDFGException(
                "InvokeNode: Number of inputs does not match number of function parameters. Expected " +
                std::to_string(func_type->num_params()) + ", got " + std::to_string(inputs_.size())
            );
        }
        if (!this->is_void(function) && outputs_.size() < 1) {
            throw InvalidSDFGException(
                "CallNode: Non-void function must have at least one output to store the return value."
            );
        }
    }
}

symbolic::SymbolSet InvokeNode::symbols() const { return {symbolic::symbol(this->callee_name_)}; }

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

void InvokeNode::replace(const symbolic::Expression old_expression, const symbolic::Expression new_expression) {}

void InvokeNode::replace(const symbolic::ExpressionMapping& replacements) {}

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

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

    return j;
}

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

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

    sdfg::serializer::JSONSerializer serializer;
    DebugInfo debug_info = serializer.json_to_debug_info(j["debug_info"]);

    std::string callee_name = j["callee_name"].get<std::string>();
    auto outputs = j["outputs"].get<std::vector<std::string>>();
    auto inputs = j["inputs"].get<std::vector<std::string>>();

    return builder.add_library_node<InvokeNode>(parent, debug_info, callee_name, outputs, inputs);
}

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

void InvokeNodeDispatcher::dispatch_code(
    codegen::PrettyPrinter& stream,
    codegen::PrettyPrinter& globals_stream,
    codegen::CodeSnippetFactory& library_snippet_factory
) {
    auto& node = static_cast<const InvokeNode&>(node_);

    stream << "try {" << std::endl;
    stream.setIndent(stream.indent() + 4);

    if (!node.is_void(function_)) {
        stream << node.outputs().at(0) << " = ";
    }
    if (node.is_indirect_call(function_)) {
        auto& graph = node.get_parent();

        // Collect return memlet
        const data_flow::Memlet* ret_memlet = nullptr;
        for (auto& oedge : graph.out_edges(node)) {
            if (oedge.src_conn() == "_ret") {
                ret_memlet = &oedge;
                break;
            }
        }

        // Collect input memlets
        std::unordered_map<std::string, const data_flow::Memlet*> input_memlets;
        for (auto& iedge : graph.in_edges(node)) {
            input_memlets[iedge.dst_conn()] = &iedge;
        }

        // Cast callee to function pointer type
        std::string func_ptr_type;

        // Return type
        if (ret_memlet) {
            auto ret_type = ret_memlet->result_type(function_);
            func_ptr_type = language_extension_.declaration("", *ret_type) + " (*)";
        } else {
            func_ptr_type = "void (*)";
        }

        // Parameters
        func_ptr_type += "(";
        for (size_t i = 0; i < node.inputs().size(); i++) {
            auto memlet_in = input_memlets.find(node.inputs().at(i));
            assert(memlet_in != input_memlets.end());
            auto in_type = memlet_in->second->result_type(function_);
            func_ptr_type += language_extension_.declaration("", *in_type);
            if (i < node.inputs().size() - 1) {
                func_ptr_type += ", ";
            }
        }
        func_ptr_type += ")";

        if (this->language_extension_.language() == "C") {
            stream << "((" << func_ptr_type << ") " << node.callee_name() << ")" << "(";
        } else if (this->language_extension_.language() == "C++") {
            stream << "reinterpret_cast<" << func_ptr_type << ">(" << node.callee_name() << ")" << "(";
        }
    } else {
        stream << this->language_extension_.external_prefix() << node.callee_name() << "(";
    }
    for (size_t i = 0; i < node.inputs().size(); ++i) {
        stream << node.inputs().at(i);
        if (i < node.inputs().size() - 1) {
            stream << ", ";
        }
    }
    stream << ")" << ";";
    stream << std::endl;

    stream << node_.outputs().at(node.outputs().size() - 1) << " = false;" << std::endl;
    stream.setIndent(stream.indent() - 4);
    stream << "} catch (...) {" << std::endl;
    stream.setIndent(stream.indent() + 4);
    stream << node_.outputs().at(node.outputs().size() - 1) << " = true;" << std::endl;
    stream.setIndent(stream.indent() - 4);
    stream << "}" << std::endl;
}

} // namespace data_flow
} // namespace sdfg

1	#include "sdfg/data_flow/library_nodes/invoke_node.h"
2
3	namespace sdfg {
4	namespace data_flow {
5
6	InvokeNode::InvokeNode(
7	size_t element_id,
8	const DebugInfo& debug_info,
9	const graph::Vertex vertex,
10	data_flow::DataFlowGraph& parent,
11	const std::string& callee_name,
12	const std::vector<std::string>& outputs,
13	const std::vector<std::string>& inputs
14	)
15	: LibraryNode(	×
16	element_id,	×
17	debug_info,	×
18	vertex,	×
19	parent,	×
20	LibraryNodeType_Invoke,	×
21	outputs,	×
22	inputs,	×
23	true,	×
24	data_flow::ImplementationType_NONE	×
25	),	×
26	callee_name_(callee_name) {	×
27	this->outputs_.push_back("_unwind"); // Add unwind output	×
28	}	×
29
30	const std::string& InvokeNode::callee_name() const { return this->callee_name_; }	×
31
32	bool InvokeNode::is_void(const Function& sdfg) const { return outputs_.size() == 1 \|\| outputs_.at(0) != "_ret"; }	×
33
34	bool InvokeNode::is_indirect_call(const Function& sdfg) const {	×
35	auto& type = sdfg.type(this->callee_name_);	×
36	return dynamic_cast<const types::Pointer*>(&type) != nullptr;	×
37	}	×
38
39	void InvokeNode::validate(const Function& function) const {	×
40	LibraryNode::validate(function);	×
41
42	if (!function.exists(this->callee_name_)) {	×
43	throw InvalidSDFGException("InvokeNode: Function '" + this->callee_name_ + "' does not exist.");	×
44	}	×
45	auto& type = function.type(this->callee_name_);	×
46	if (!dynamic_cast<const types::Function>(&type) && !dynamic_cast<const types::Pointer>(&type)) {	×
47	throw InvalidSDFGException("InvokeNode: '" + this->callee_name_ + "' is not a function or pointer.");	×
48	}	×
49
50	if (auto func_type = dynamic_cast<const types::Function*>(&type)) {	×
51	if (!function.is_external(this->callee_name_)) {	×
52	throw InvalidSDFGException("InvokeNode: Function '" + this->callee_name_ + "' must be declared.");	×
53	}	×
54	if (!func_type->is_var_arg() && inputs_.size() != func_type->num_params()) {	×
55	throw InvalidSDFGException(	×
56	"InvokeNode: Number of inputs does not match number of function parameters. Expected " +	×
57	std::to_string(func_type->num_params()) + ", got " + std::to_string(inputs_.size())	×
58	);	×
59	}	×
60	if (!this->is_void(function) && outputs_.size() < 1) {	×
61	throw InvalidSDFGException(	×
62	"CallNode: Non-void function must have at least one output to store the return value."	×
63	);	×
64	}	×
65	}	×
66	}	×
67
68	symbolic::SymbolSet InvokeNode::symbols() const { return {symbolic::symbol(this->callee_name_)}; }	×
69
70	std::unique_ptr<data_flow::DataFlowNode> InvokeNode::
71	clone(size_t element_id, const graph::Vertex vertex, data_flow::DataFlowGraph& parent) const {	×
72	return std::make_unique<InvokeNode>(element_id, debug_info_, vertex, parent, callee_name_, outputs_, inputs_);	×
73	}	×
74
75	void InvokeNode::replace(const symbolic::Expression old_expression, const symbolic::Expression new_expression) {}	×
76
NEW 77	void InvokeNode::replace(const symbolic::ExpressionMapping& replacements) {}	×
78
79	nlohmann::json InvokeNodeSerializer::serialize(const data_flow::LibraryNode& library_node) {	×
80	const InvokeNode& node = static_cast<const InvokeNode&>(library_node);	×
81
82	nlohmann::json j;	×
83	j["code"] = node.code().value();	×
84	j["callee_name"] = node.callee_name();	×
85	j["outputs"] = node.outputs();	×
86	j["inputs"] = node.inputs();	×
87
88	return j;	×
89	}	×
90
91	data_flow::LibraryNode& InvokeNodeSerializer::deserialize(
92	const nlohmann::json& j, builder::StructuredSDFGBuilder& builder, structured_control_flow::Block& parent
93	) {	×
94	assert(j.contains("code"));	×
95	assert(j.contains("callee_name"));	×
96	assert(j.contains("outputs"));	×
97	assert(j.contains("inputs"));	×
98	assert(j.contains("debug_info"));	×
99
100	auto code = j["code"].get<std::string>();	×
101	if (code != LibraryNodeType_Invoke.value()) {	×
102	throw InvalidSDFGException("Invalid library node code");	×
103	}	×
104
105	sdfg::serializer::JSONSerializer serializer;	×
106	DebugInfo debug_info = serializer.json_to_debug_info(j["debug_info"]);	×
107
108	std::string callee_name = j["callee_name"].get<std::string>();	×
109	auto outputs = j["outputs"].get<std::vector<std::string>>();	×
110	auto inputs = j["inputs"].get<std::vector<std::string>>();	×
111
112	return builder.add_library_node<InvokeNode>(parent, debug_info, callee_name, outputs, inputs);	×
113	}	×
114
115	InvokeNodeDispatcher::InvokeNodeDispatcher(
116	codegen::LanguageExtension& language_extension,
117	const Function& function,
118	const data_flow::DataFlowGraph& data_flow_graph,
119	const InvokeNode& node
120	)
121	: codegen::LibraryNodeDispatcher(language_extension, function, data_flow_graph, node) {}	×
122
123	void InvokeNodeDispatcher::dispatch_code(
124	codegen::PrettyPrinter& stream,
125	codegen::PrettyPrinter& globals_stream,
126	codegen::CodeSnippetFactory& library_snippet_factory
127	) {	×
128	auto& node = static_cast<const InvokeNode&>(node_);	×
129
130	stream << "try {" << std::endl;	×
131	stream.setIndent(stream.indent() + 4);	×
132
133	if (!node.is_void(function_)) {	×
134	stream << node.outputs().at(0) << " = ";	×
135	}	×
136	if (node.is_indirect_call(function_)) {	×
137	auto& graph = node.get_parent();	×
138
139	// Collect return memlet
140	const data_flow::Memlet* ret_memlet = nullptr;	×
141	for (auto& oedge : graph.out_edges(node)) {	×
142	if (oedge.src_conn() == "_ret") {	×
143	ret_memlet = &oedge;	×
144	break;	×
145	}	×
146	}	×
147
148	// Collect input memlets
149	std::unordered_map<std::string, const data_flow::Memlet*> input_memlets;	×
150	for (auto& iedge : graph.in_edges(node)) {	×
151	input_memlets[iedge.dst_conn()] = &iedge;	×
152	}	×
153
154	// Cast callee to function pointer type
155	std::string func_ptr_type;	×
156
157	// Return type
158	if (ret_memlet) {	×
159	auto ret_type = ret_memlet->result_type(function_);	×
160	func_ptr_type = language_extension_.declaration("", ret_type) + " ()";	×
161	} else {	×
162	func_ptr_type = "void (*)";	×
163	}	×
164
165	// Parameters
166	func_ptr_type += "(";	×
167	for (size_t i = 0; i < node.inputs().size(); i++) {	×
168	auto memlet_in = input_memlets.find(node.inputs().at(i));	×
169	assert(memlet_in != input_memlets.end());	×
170	auto in_type = memlet_in->second->result_type(function_);	×
171	func_ptr_type += language_extension_.declaration("", *in_type);	×
172	if (i < node.inputs().size() - 1) {	×
173	func_ptr_type += ", ";	×
174	}	×
175	}	×
176	func_ptr_type += ")";	×
177
178	if (this->language_extension_.language() == "C") {	×
179	stream << "((" << func_ptr_type << ") " << node.callee_name() << ")" << "(";	×
180	} else if (this->language_extension_.language() == "C++") {	×
181	stream << "reinterpret_cast<" << func_ptr_type << ">(" << node.callee_name() << ")" << "(";	×
182	}	×
183	} else {	×
184	stream << this->language_extension_.external_prefix() << node.callee_name() << "(";	×
185	}	×
186	for (size_t i = 0; i < node.inputs().size(); ++i) {	×
187	stream << node.inputs().at(i);	×
188	if (i < node.inputs().size() - 1) {	×
189	stream << ", ";	×
190	}	×
191	}	×
192	stream << ")" << ";";	×
193	stream << std::endl;	×
194
195	stream << node_.outputs().at(node.outputs().size() - 1) << " = false;" << std::endl;	×
196	stream.setIndent(stream.indent() - 4);	×
197	stream << "} catch (...) {" << std::endl;	×
198	stream.setIndent(stream.indent() + 4);	×
199	stream << node_.outputs().at(node.outputs().size() - 1) << " = true;" << std::endl;	×
200	stream.setIndent(stream.indent() - 4);	×
201	stream << "}" << std::endl;	×
202	}	×
203
204	} // namespace data_flow
205	} // 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