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

38.96

/sdfg/src/data_flow/library_nodes/call_node.cpp

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

namespace sdfg {
namespace data_flow {

CallNode::CallNode(
    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,
    std::vector<PointerAccessType> ptr_access_meta
)
    : LibraryNode(
          element_id,
          debug_info,
          vertex,
          parent,
          LibraryNodeType_Call,
          outputs,
          inputs,
          true,
          data_flow::ImplementationType_NONE
      ),
      callee_name_(callee_name), ptr_access_meta_(std::move(ptr_access_meta)) {}

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

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

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

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

    if (!function.exists(this->callee_name_)) {
        throw InvalidSDFGException("CallNode: 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("CallNode: '" + 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("CallNode: Function '" + this->callee_name_ + "' must be declared.");
        }
        if (!func_type->is_var_arg() && inputs_.size() != func_type->num_params()) {
            throw InvalidSDFGException(
                "CallNode: 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 CallNode::symbols() const { return {symbolic::symbol(this->callee_name_)}; }

std::unique_ptr<data_flow::DataFlowNode> CallNode::
    clone(size_t element_id, const graph::Vertex vertex, data_flow::DataFlowGraph& parent) const {
    std::vector<PointerAccessType> ptr_access_meta_clone;
    ptr_access_meta_clone.reserve(ptr_access_meta_.size());
    for (auto& ptr_access_meta : ptr_access_meta_) {
        if (ptr_access_meta) {
            ptr_access_meta_clone.push_back(ptr_access_meta->clone());
        } else {
            ptr_access_meta_clone.push_back(nullptr);
        }
    }
    return std::make_unique<CallNode>(
        element_id, debug_info_, vertex, parent, callee_name_, outputs_, inputs_, std::move(ptr_access_meta_clone)
    );
}

PointerAccessType CallNode::pointer_access_type(int input_idx) const {
    if (ptr_access_meta_.size() > input_idx) {
        return ptr_access_meta_.at(0)->ref();
    } else {
        return LibraryNode::pointer_access_type(input_idx);
    }
}

const std::vector<PointerAccessType>& CallNode::pointer_access_meta() const { return ptr_access_meta_; }

std::string CallNode::toStr() const { return LibraryNode::toStr() + "('" + callee_name_ + "')"; }

void CallNode::replace(const symbolic::Expression old_expression, const symbolic::Expression new_expression) {
    for (auto& meta : ptr_access_meta_) {
        if (meta) {
            meta->replace(old_expression, new_expression);
        }
    }
}

void CallNode::replace(const symbolic::ExpressionMapping& replacements) {
    for (auto& meta : ptr_access_meta_) {
        if (meta) {
            meta->replace(replacements);
        }
    }
}

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

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

    return j;
}

data_flow::LibraryNode& CallNodeSerializer::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_Call.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>>();
    auto ptr_access_meta = PointerAccessMetaSerializer::deserialize_list(j.find("ptr_access_meta"), j);

    return builder
        .add_library_node<CallNode>(parent, debug_info, callee_name, outputs, inputs, std::move(ptr_access_meta));
}

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

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

    codegen::DispatchOutput* output = nullptr;
    if (!node.is_void(function_)) {
        output = &outputs.at(0);
        pre_allocate_output(out, *output, node.output(0));
        out.stream << *output->local_name << " = ";
    }
    if (node.is_indirect_call(function_)) {
        // Cast callee to function pointer type
        std::string func_ptr_type;

        // Return type
        if (output) {
            func_ptr_type = language_extension_.declaration("", *output->out_type) + " (*)";
        } else {
            func_ptr_type = "void (*)";
        }

        // Parameters
        func_ptr_type += "(";
        for (size_t i = 0; i < inputs.size(); i++) {
            auto& input = inputs.at(i);

            auto in_type = input.edge.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") {
            out.stream << "((" << func_ptr_type << ") " << node.callee_name() << ")" << "(";
        } else if (this->language_extension_.language() == "C++") {
            out.stream << "reinterpret_cast<" << func_ptr_type << ">(" << node.callee_name() << ")" << "(";
        }
    } else {
        out.stream << this->language_extension_.external_prefix() << node.callee_name() << "(";
    }
    for (size_t i = 0; i < inputs.size(); ++i) {
        out.stream << inputs.at(i).expr;
        if (i < node.inputs().size() - 1) {
            out.stream << ", ";
        }
    }
    out.stream << ")" << ";";
    out.stream << std::endl;
}

} // namespace data_flow
} // namespace sdfg

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