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

57.53

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

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

namespace sdfg {
namespace stdlib {

MallocNode::MallocNode(
    size_t element_id,
    const DebugInfo& debug_info,
    const graph::Vertex vertex,
    data_flow::DataFlowGraph& parent,
    const symbolic::Expression size
)
    : StdlibNode(
          element_id,
          debug_info,
          vertex,
          parent,
          LibraryNodeType_Malloc,
          {"_ret"},
          {},
          true, // debatable. Its a big change and we may want it as a flag
          data_flow::ImplementationType_NONE
      ),
      size_(size) {}

const symbolic::Expression MallocNode::size() const { return size_; }

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

symbolic::SymbolSet MallocNode::symbols() const { return symbolic::atoms(this->size_); }

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

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

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

std::string MallocNode::toStr() const { return LibraryNode::toStr() + "(" + size_->__str__() + ")"; }

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

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

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

    return j;
}

data_flow::LibraryNode& MallocNodeSerializer::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("size"));

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

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

    auto size = symbolic::parse(j.at("size"));

    return builder.add_library_node<MallocNode>(parent, debug_info, size);
}

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

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

    auto& graph = malloc_node.get_parent();
    auto& oedge = *graph.out_edges(malloc_node).begin();

    auto& ptr_out = outputs.at(0);
    auto& out_name = node_.output(0);

    out.stream << language_extension_.declaration(node_.output(0), *ptr_out.out_type) << " = ("
               << language_extension_.type_cast(
                      language_extension_.external_prefix() + "malloc(" +
                          language_extension_.expression(malloc_node.size()) + ")",
                      oedge.base_type()
                  )
               << ");" << std::endl;

    register_output(ptr_out, out_name);
}

MallocNode& add_malloc_node(
    builder::StructuredSDFGBuilder& builder,
    Block& block,
    const std::string& dst_ptr,
    const symbolic::Expression& size,
    const types::IType& ptr_type,
    DebugInfo debug_info
) {
    auto& dst_ptr_access = builder.add_access(block, dst_ptr);
    auto& libnode = builder.add_library_node<stdlib::MallocNode>(block, debug_info, size);
    builder.add_computational_memlet(block, libnode, "_ret", dst_ptr_access, {}, ptr_type);

    return static_cast<MallocNode&>(libnode);
}

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

    auto& libnode = add_malloc_node(builder, block, dst_ptr, size, ptr_type, debug_info);

    return {block, libnode};
}

} // namespace stdlib
} // namespace sdfg

1	#include "sdfg/data_flow/library_nodes/stdlib/malloc.h"
2
3	namespace sdfg {
4	namespace stdlib {
5
6	MallocNode::MallocNode(
7	size_t element_id,
8	const DebugInfo& debug_info,
9	const graph::Vertex vertex,
10	data_flow::DataFlowGraph& parent,
11	const symbolic::Expression size
12	)
13	: StdlibNode(	97✔
14	element_id,	97✔
15	debug_info,	97✔
16	vertex,	97✔
17	parent,	97✔
18	LibraryNodeType_Malloc,	97✔
19	{"_ret"},	97✔
20	{},	97✔
21	true, // debatable. Its a big change and we may want it as a flag	97✔
22	data_flow::ImplementationType_NONE	97✔
23	),	97✔
24	size_(size) {}	97✔
25
26	const symbolic::Expression MallocNode::size() const { return size_; }	73✔
27
28	void MallocNode::validate(const Function& function) const { LibraryNode::validate(function); }	199✔
29
30	symbolic::SymbolSet MallocNode::symbols() const { return symbolic::atoms(this->size_); }	114✔
31
32	std::unique_ptr<data_flow::DataFlowNode> MallocNode::
33	clone(size_t element_id, const graph::Vertex vertex, data_flow::DataFlowGraph& parent) const {	×
34	return std::make_unique<MallocNode>(element_id, debug_info_, vertex, parent, size_);	×
35	}	×
36
37	void MallocNode::replace(const symbolic::Expression old_expression, const symbolic::Expression new_expression) {	×
38	this->size_ = symbolic::subs(this->size_, old_expression, new_expression);	×
39	}	×
40
NEW 41	void MallocNode::replace(const symbolic::ExpressionMapping& replacements) {	×
NEW 42	this->size_ = symbolic::subs(this->size_, replacements);	×
NEW 43	}	×
44
UNCOV 45	std::string MallocNode::toStr() const { return LibraryNode::toStr() + "(" + size_->__str__() + ")"; }	×
46
47	nlohmann::json MallocNodeSerializer::serialize(const data_flow::LibraryNode& library_node) {	×
48	const MallocNode& node = static_cast<const MallocNode&>(library_node);	×
49
50	nlohmann::json j;	×
51	j["code"] = node.code().value();	×
52
53	sdfg::serializer::JSONSerializer serializer;	×
54	j["size"] = serializer.expression(node.size());	×
55
56	return j;	×
57	}	×
58
59	data_flow::LibraryNode& MallocNodeSerializer::deserialize(
60	const nlohmann::json& j, builder::StructuredSDFGBuilder& builder, structured_control_flow::Block& parent
61	) {	×
62	assert(j.contains("code"));	×
63	assert(j.contains("debug_info"));	×
64	assert(j.contains("size"));	×
65
66	auto code = j["code"].get<std::string>();	×
67	if (code != LibraryNodeType_Malloc.value()) {	×
68	throw InvalidSDFGException("Invalid library node code");	×
69	}	×
70
71	sdfg::serializer::JSONSerializer serializer;	×
72	DebugInfo debug_info = serializer.json_to_debug_info(j["debug_info"]);	×
73
74	auto size = symbolic::parse(j.at("size"));	×
75
76	return builder.add_library_node<MallocNode>(parent, debug_info, size);	×
77	}	×
78
79	MallocNodeDispatcher::MallocNodeDispatcher(
80	codegen::LanguageExtension& language_extension,
81	const Function& function,
82	const data_flow::DataFlowGraph& data_flow_graph,
83	const MallocNode& node
84	)
85	: codegen::LibraryNodeDispatcher(language_extension, function, data_flow_graph, node) {}	1✔
86
87	void MallocNodeDispatcher::dispatch_code_with_edges(
88	codegen::CodegenOutput& out,
89	std::vector<codegen::DispatchInput>& inputs,
90	std::vector<codegen::DispatchOutput>& outputs
91	) {	1✔
92	auto& malloc_node = static_cast<const MallocNode&>(node_);	1✔
93
94	auto& graph = malloc_node.get_parent();	1✔
95	auto& oedge = *graph.out_edges(malloc_node).begin();	1✔
96
97	auto& ptr_out = outputs.at(0);	1✔
98	auto& out_name = node_.output(0);	1✔
99
100	out.stream << language_extension_.declaration(node_.output(0), *ptr_out.out_type) << " = ("	1✔
101	<< language_extension_.type_cast(	1✔
102	language_extension_.external_prefix() + "malloc(" +	1✔
103	language_extension_.expression(malloc_node.size()) + ")",	1✔
104	oedge.base_type()	1✔
105	)	1✔
106	<< ");" << std::endl;	1✔
107
108	register_output(ptr_out, out_name);	1✔
109	}	1✔
110
111	MallocNode& add_malloc_node(
112	builder::StructuredSDFGBuilder& builder,
113	Block& block,
114	const std::string& dst_ptr,
115	const symbolic::Expression& size,
116	const types::IType& ptr_type,
117	DebugInfo debug_info
118	) {	19✔
119	auto& dst_ptr_access = builder.add_access(block, dst_ptr);	19✔
120	auto& libnode = builder.add_library_node<stdlib::MallocNode>(block, debug_info, size);	19✔
121	builder.add_computational_memlet(block, libnode, "_ret", dst_ptr_access, {}, ptr_type);	19✔
122
123	return static_cast<MallocNode&>(libnode);	19✔
124	}	19✔
125
126	std::tuple<Block&, MallocNode&> add_malloc_block(
127	builder::StructuredSDFGBuilder& builder,
128	Sequence& parent,
129	const std::string& dst_ptr,
130	const symbolic::Expression& size,
131	const types::IType& ptr_type,
132	DebugInfo debug_info
133	) {	19✔
134	auto& block = builder.add_block(parent);	19✔
135
136	auto& libnode = add_malloc_node(builder, block, dst_ptr, size, ptr_type, debug_info);	19✔
137
138	return {block, libnode};	19✔
139	}	19✔
140
141	} // namespace stdlib
142	} // 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