28806128926

Committed 06 Jul 2026 04:16PM UTC coverage: 62.96%. First build

Build # 28806128926

Build Type

push

github

Committed by

web-flow

Commit Message

New LibNodeExpansion pass (#740)

* Switched expansion "pipeline" to new LibNodeExpansionPass that can recursively expand using a LibNodeExpander impl.
- removed access to analysis_manager from expansion methods, as those would currently not be appropriately maintained between nodes
+ New expansion API handles more of the boilerplate code (checking for standalone, creating boundary access nodes, removing old elements)
* Also migrated sdfg-json-to-c.cpp to not using the expansion pipeline anymore
* toStr() for ReduceNodes and giving PyStructuredSDFG access to the output_dir for additional dumping
~ DotVisualizer : Fix on nested sequences.
+ DotVisualizer: visualize empty sequences
* DotVisualizer default-enabled show block/loop ids
 * while MathNodes still have an expand-method, the new infrastructure is based upon "Expander" classes. The MathNodeExpander just redirects to the method for now
 ~ Broadcast node still used old ptr-output semantics
 * updated tensor & blas node expand to new expand API, that handles more of the boilerplate code (checking, removing old nodes, creating standalone-replacement nodes)
 - removed Transpose Node. Was unused and on old ptr-semantics
 + StructuredSDFGBuilder.add_sequence_at, add_for_at, add_map_at
 * switched StructuredSDFGBuilder internally to use ptr of Assignments to express using default assignments when needed
 * updated tests to use the new expand_single_math_node helper function, instead of the method directly
 + pass and expand-single helper functions are ready to use other expanders
 + EinsumExpansionPass is basically the legacy ExpansionPass, only restricted to EinsumNodes. It still needs to run in a pipeline to ensure finding multiple EinsumNodes per block. This is temporary, because Einsum is the only node that already supported splitting a block, which the new expansion disallows, as it should handle it itself when needed (but that part is not yet implemented)

Coverage Stats

594 of 962 new or added lines in 31 files covered. (61.75%)

40554 of 64412 relevant lines covered (62.96%)

963.11 hits per line

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

39.8

/sdfg/src/data_flow/library_nodes/math/blas/dot_node.cpp

#include "sdfg/data_flow/library_nodes/math/blas/dot_node.h"
#include <stdexcept>
#include <string>

#include "sdfg/analysis/analysis.h"
#include "sdfg/builder/structured_sdfg_builder.h"

#include "sdfg/symbolic/symbolic.h"

namespace sdfg {
namespace math {
namespace blas {

DotNode::DotNode(
    size_t element_id,
    const DebugInfo& debug_info,
    const graph::Vertex vertex,
    data_flow::DataFlowGraph& parent,
    const data_flow::ImplementationType& implementation_type,
    const BLAS_Precision& precision,
    symbolic::Expression n,
    symbolic::Expression incx,
    symbolic::Expression incy
)
    : BLASNode(
          element_id,
          debug_info,
          vertex,
          parent,
          LibraryNodeType_DOT,
          {"__out"},
          {"__x", "__y"},
          implementation_type,
          precision
      ),
      n_(n), incx_(incx), incy_(incy) {}

symbolic::Expression DotNode::n() const { return this->n_; };

symbolic::Expression DotNode::incx() const { return this->incx_; };

symbolic::Expression DotNode::incy() const { return this->incy_; };

symbolic::SymbolSet DotNode::symbols() const {
    symbolic::SymbolSet syms;

    for (auto& atom : symbolic::atoms(this->n_)) {
        syms.insert(atom);
    }
    for (auto& atom : symbolic::atoms(this->incx_)) {
        syms.insert(atom);
    }
    for (auto& atom : symbolic::atoms(this->incy_)) {
        syms.insert(atom);
    }

    return syms;
};

void DotNode::replace(const symbolic::Expression old_expression, const symbolic::Expression new_expression) {
    this->n_ = symbolic::subs(this->n_, old_expression, new_expression);
    this->incx_ = symbolic::subs(this->incx_, old_expression, new_expression);
    this->incy_ = symbolic::subs(this->incy_, old_expression, new_expression);
};

void DotNode::replace(const symbolic::ExpressionMapping& replacements) {
    this->n_ = symbolic::subs(this->n_, replacements);
    this->incx_ = symbolic::subs(this->incx_, replacements);
    this->incy_ = symbolic::subs(this->incy_, replacements);
};

void DotNode::validate(const Function& function) const { BLASNode::validate(function); }

passes::LibNodeExpander::ExpandOutcome DotNode::
    expand(passes::LibNodeExpander::ExpandContext& context, structured_control_flow::Block& block) {
    auto& dataflow = this->get_parent();

    const data_flow::Memlet* iedge_x = nullptr;
    const data_flow::Memlet* iedge_y = nullptr;
    for (const auto& iedge : dataflow.in_edges(*this)) {
        if (iedge.dst_conn() == "__x") {
            iedge_x = &iedge;
        } else if (iedge.dst_conn() == "__y") {
            iedge_y = &iedge;
        }
    }

    const data_flow::Memlet* oedge_res = nullptr;
    for (const auto& oedge : dataflow.out_edges(*this)) {
        if (oedge.src_conn() == "__out") {
            oedge_res = &oedge;
            break;
        }
    }

    using Use = passes::LibNodeExpander::InputUse;
    auto standalone = context.replacement_requires_access_nodes({Use::IndirectRead, Use::IndirectRead});
    if (!standalone) {
        return context.unable();
    }

    auto& builder = standalone->builder();
    auto& new_sequence = standalone->replace_with_sequence();

    std::string loop_var = builder.find_new_name("_i");
    builder.add_container(loop_var, types::Scalar(types::PrimitiveType::UInt64));

    auto loop_indvar = symbolic::symbol(loop_var);
    auto loop_init = symbolic::integer(0);
    auto loop_condition = symbolic::Lt(loop_indvar, this->n_);
    auto loop_update = symbolic::add(loop_indvar, symbolic::integer(1));

    auto& loop =
        builder.add_for(new_sequence, loop_indvar, loop_condition, loop_init, loop_update, {}, block.debug_info());
    auto& body = loop.root();

    auto& new_block = builder.add_block(body);

    auto& res_out = standalone->add_output_access(new_block, 0);
    auto& res_in = builder.add_access(new_block, res_out.data());
    // absolute hack to read sth. that is supposed to be an output.
    // This will definitely break SSA when we switch and should use a temporary scoped to the loop instead

    auto& x = standalone->add_indirect_read_access(new_block, 0);
    auto& y = standalone->add_indirect_read_access(new_block, 1);

    auto& tasklet = builder.add_tasklet(new_block, data_flow::TaskletCode::fp_fma, "__out", {"_in1", "_in2", "_in3"});

    builder.add_computational_memlet(
        new_block,
        x,
        tasklet,
        "_in1",
        {symbolic::mul(loop_indvar, this->incx_)},
        iedge_x->base_type(),
        iedge_x->debug_info()
    );
    builder.add_computational_memlet(
        new_block,
        y,
        tasklet,
        "_in2",
        {symbolic::mul(loop_indvar, this->incy_)},
        iedge_y->base_type(),
        iedge_y->debug_info()
    );
    builder
        .add_computational_memlet(new_block, res_in, tasklet, "_in3", {}, oedge_res->base_type(), oedge_res->debug_info());
    builder.add_computational_memlet(
        new_block, tasklet, "__out", res_out, {}, oedge_res->base_type(), oedge_res->debug_info()
    );

    return context.unable();
}

symbolic::Expression DotNode::flop() const {
    auto muls = this->n_;
    auto adds = symbolic::sub(this->n_, symbolic::one());
    return symbolic::add(muls, adds);
}

std::unique_ptr<data_flow::DataFlowNode> DotNode::
    clone(size_t element_id, const graph::Vertex vertex, data_flow::DataFlowGraph& parent) const {
    auto node_clone = std::unique_ptr<DotNode>(new DotNode(
        element_id,
        this->debug_info(),
        vertex,
        parent,
        this->implementation_type_,
        this->precision_,
        this->n_,
        this->incx_,
        this->incy_
    ));
    return std::move(node_clone);
}

data_flow::PointerAccessType DotNode::pointer_access_type(int input_idx) const {
    if (input_idx == 0) {
        return data_flow::PointerAccessMeta::create_read_only(symbolic::mul(n_, incx_), true);
    } else if (input_idx == 1) {
        return data_flow::PointerAccessMeta::create_read_only(symbolic::mul(n_, incy_), true);
    } else {
        return BLASNode::pointer_access_type(input_idx);
    }
}

nlohmann::json DotNodeSerializer::serialize(const data_flow::LibraryNode& library_node) {
    const DotNode& gemm_node = static_cast<const DotNode&>(library_node);
    nlohmann::json j;

    serializer::JSONSerializer serializer;
    j["code"] = gemm_node.code().value();
    j["precision"] = gemm_node.precision();
    j["n"] = serializer.expression(gemm_node.n());
    j["incx"] = serializer.expression(gemm_node.incx());
    j["incy"] = serializer.expression(gemm_node.incy());

    return j;
}

data_flow::LibraryNode& DotNodeSerializer::deserialize(
    const nlohmann::json& j, builder::StructuredSDFGBuilder& builder, structured_control_flow::Block& parent
) {
    // Assertions for required fields
    assert(j.contains("element_id"));
    assert(j.contains("code"));
    assert(j.contains("debug_info"));

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

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

    auto precision = j.at("precision").get<BLAS_Precision>();
    auto n = symbolic::parse(j.at("n"));
    auto incx = symbolic::parse(j.at("incx"));
    auto incy = symbolic::parse(j.at("incy"));

    auto implementation_type = j.at("implementation_type").get<std::string>();

    return builder.add_library_node<DotNode>(parent, debug_info, implementation_type, precision, n, incx, incy);
}

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

void DotNodeDispatcher_BLAS::dispatch_code_with_edges(
    codegen::CodegenOutput& out,
    std::vector<codegen::DispatchInput>& inputs,
    std::vector<codegen::DispatchOutput>& outputs
) {
    auto& dot_node = static_cast<const DotNode&>(this->node_);

    sdfg::types::Scalar base_type(types::PrimitiveType::Void);
    BLAS_Precision precision = dot_node.precision();
    switch (precision) {
        case BLAS_Precision::h:
            base_type = types::Scalar(types::PrimitiveType::Half);
            break;
        case BLAS_Precision::s:
            base_type = types::Scalar(types::PrimitiveType::Float);
            break;
        case BLAS_Precision::d:
            base_type = types::Scalar(types::PrimitiveType::Double);
            break;
        default:
            throw std::runtime_error("Invalid BLAS_Precision value");
    }

    out.library_snippet_factory.require_dependency(BLASLibDependency::instance());

    auto& output = outputs.at(0);
    pre_allocate_output(out, output, dot_node.output(0));

    out.stream << *output.local_name << " = ";
    out.stream << "cblas_" << BLAS_Precision_to_string(precision) << "dot(";
    out.stream.changeIndent(+4);
    out.stream << this->language_extension_.expression(dot_node.n());
    out.stream << ", ";
    out.stream << inputs.at(0).expr;
    out.stream << ", ";
    out.stream << this->language_extension_.expression(dot_node.incx());
    out.stream << ", ";
    out.stream << inputs.at(1).expr;
    out.stream << ", ";
    out.stream << this->language_extension_.expression(dot_node.incy());
    out.stream.changeIndent(-4);
    out.stream << ");" << std::endl;
}


} // namespace blas
} // namespace math
} // namespace sdfg

1	#include "sdfg/data_flow/library_nodes/math/blas/dot_node.h"
2	#include <stdexcept>
3	#include <string>
4
5	#include "sdfg/analysis/analysis.h"
6	#include "sdfg/builder/structured_sdfg_builder.h"
7
8	#include "sdfg/symbolic/symbolic.h"
9
10	namespace sdfg {
11	namespace math {
12	namespace blas {
13
14	DotNode::DotNode(
15	size_t element_id,
16	const DebugInfo& debug_info,
17	const graph::Vertex vertex,
18	data_flow::DataFlowGraph& parent,
19	const data_flow::ImplementationType& implementation_type,
20	const BLAS_Precision& precision,
21	symbolic::Expression n,
22	symbolic::Expression incx,
23	symbolic::Expression incy
24	)
25	: BLASNode(	13✔
26	element_id,	13✔
27	debug_info,	13✔
28	vertex,	13✔
29	parent,	13✔
30	LibraryNodeType_DOT,	13✔
31	{"__out"},	13✔
32	{"__x", "__y"},	13✔
33	implementation_type,	13✔
34	precision	13✔
35	),	13✔
36	n_(n), incx_(incx), incy_(incy) {}	13✔
37
38	symbolic::Expression DotNode::n() const { return this->n_; };	4✔
39
40	symbolic::Expression DotNode::incx() const { return this->incx_; };	2✔
41
42	symbolic::Expression DotNode::incy() const { return this->incy_; };	2✔
43
44	symbolic::SymbolSet DotNode::symbols() const {	×
45	symbolic::SymbolSet syms;	×
46
47	for (auto& atom : symbolic::atoms(this->n_)) {	×
48	syms.insert(atom);	×
49	}	×
50	for (auto& atom : symbolic::atoms(this->incx_)) {	×
51	syms.insert(atom);	×
52	}	×
53	for (auto& atom : symbolic::atoms(this->incy_)) {	×
54	syms.insert(atom);	×
55	}	×
56
57	return syms;	×
58	};	×
59
60	void DotNode::replace(const symbolic::Expression old_expression, const symbolic::Expression new_expression) {	×
61	this->n_ = symbolic::subs(this->n_, old_expression, new_expression);	×
62	this->incx_ = symbolic::subs(this->incx_, old_expression, new_expression);	×
63	this->incy_ = symbolic::subs(this->incy_, old_expression, new_expression);	×
64	};	×
65
66	void DotNode::replace(const symbolic::ExpressionMapping& replacements) {	×
67	this->n_ = symbolic::subs(this->n_, replacements);	×
68	this->incx_ = symbolic::subs(this->incx_, replacements);	×
69	this->incy_ = symbolic::subs(this->incy_, replacements);	×
70	};	×
71
72	void DotNode::validate(const Function& function) const { BLASNode::validate(function); }	×
73
74	passes::LibNodeExpander::ExpandOutcome DotNode::
75	expand(passes::LibNodeExpander::ExpandContext& context, structured_control_flow::Block& block) {	5✔
76	auto& dataflow = this->get_parent();	5✔
77
78	const data_flow::Memlet* iedge_x = nullptr;	5✔
79	const data_flow::Memlet* iedge_y = nullptr;	5✔
80	for (const auto& iedge : dataflow.in_edges(*this)) {	10✔
81	if (iedge.dst_conn() == "__x") {	10✔
82	iedge_x = &iedge;	5✔
83	} else if (iedge.dst_conn() == "__y") {	5✔
84	iedge_y = &iedge;	5✔
85	}	5✔
86	}	10✔
87
88	const data_flow::Memlet* oedge_res = nullptr;	5✔
89	for (const auto& oedge : dataflow.out_edges(*this)) {	5✔
90	if (oedge.src_conn() == "__out") {	5✔
91	oedge_res = &oedge;	5✔
92	break;	5✔
93	}	5✔
94	}	5✔
95
96	using Use = passes::LibNodeExpander::InputUse;	5✔
97	auto standalone = context.replacement_requires_access_nodes({Use::IndirectRead, Use::IndirectRead});	5✔
98	if (!standalone) {	5✔
NEW 99	return context.unable();	×
100	}	×
101
102	auto& builder = standalone->builder();	5✔
103	auto& new_sequence = standalone->replace_with_sequence();	5✔
104
105	std::string loop_var = builder.find_new_name("_i");	5✔
106	builder.add_container(loop_var, types::Scalar(types::PrimitiveType::UInt64));	5✔
107
108	auto loop_indvar = symbolic::symbol(loop_var);	5✔
109	auto loop_init = symbolic::integer(0);	5✔
110	auto loop_condition = symbolic::Lt(loop_indvar, this->n_);	5✔
111	auto loop_update = symbolic::add(loop_indvar, symbolic::integer(1));	5✔
112
113	auto& loop =	5✔
114	builder.add_for(new_sequence, loop_indvar, loop_condition, loop_init, loop_update, {}, block.debug_info());	5✔
115	auto& body = loop.root();	5✔
116
117	auto& new_block = builder.add_block(body);	5✔
118
119	auto& res_out = standalone->add_output_access(new_block, 0);	5✔
120	auto& res_in = builder.add_access(new_block, res_out.data());	5✔
121	// absolute hack to read sth. that is supposed to be an output.
122	// This will definitely break SSA when we switch and should use a temporary scoped to the loop instead
123
124	auto& x = standalone->add_indirect_read_access(new_block, 0);	5✔
125	auto& y = standalone->add_indirect_read_access(new_block, 1);	5✔
126
127	auto& tasklet = builder.add_tasklet(new_block, data_flow::TaskletCode::fp_fma, "__out", {"_in1", "_in2", "_in3"});	5✔
128
129	builder.add_computational_memlet(	5✔
130	new_block,	5✔
131	x,	5✔
132	tasklet,	5✔
133	"_in1",	5✔
134	{symbolic::mul(loop_indvar, this->incx_)},	5✔
135	iedge_x->base_type(),	5✔
136	iedge_x->debug_info()	5✔
137	);	5✔
138	builder.add_computational_memlet(	5✔
139	new_block,	5✔
140	y,	5✔
141	tasklet,	5✔
142	"_in2",	5✔
143	{symbolic::mul(loop_indvar, this->incy_)},	5✔
144	iedge_y->base_type(),	5✔
145	iedge_y->debug_info()	5✔
146	);	5✔
147	builder	5✔
148	.add_computational_memlet(new_block, res_in, tasklet, "_in3", {}, oedge_res->base_type(), oedge_res->debug_info());	5✔
149	builder.add_computational_memlet(	5✔
150	new_block, tasklet, "__out", res_out, {}, oedge_res->base_type(), oedge_res->debug_info()	5✔
151	);	5✔
152
153	return context.unable();	5✔
154	}	5✔
155
156	symbolic::Expression DotNode::flop() const {	×
157	auto muls = this->n_;	×
158	auto adds = symbolic::sub(this->n_, symbolic::one());	×
159	return symbolic::add(muls, adds);	×
160	}	×
161
162	std::unique_ptr<data_flow::DataFlowNode> DotNode::
163	clone(size_t element_id, const graph::Vertex vertex, data_flow::DataFlowGraph& parent) const {	×
164	auto node_clone = std::unique_ptr<DotNode>(new DotNode(	×
165	element_id,	×
166	this->debug_info(),	×
167	vertex,	×
168	parent,	×
169	this->implementation_type_,	×
170	this->precision_,	×
171	this->n_,	×
172	this->incx_,	×
173	this->incy_	×
174	));	×
175	return std::move(node_clone);	×
176	}	×
177
178	data_flow::PointerAccessType DotNode::pointer_access_type(int input_idx) const {	×
179	if (input_idx == 0) {	×
180	return data_flow::PointerAccessMeta::create_read_only(symbolic::mul(n_, incx_), true);	×
181	} else if (input_idx == 1) {	×
182	return data_flow::PointerAccessMeta::create_read_only(symbolic::mul(n_, incy_), true);	×
183	} else {	×
184	return BLASNode::pointer_access_type(input_idx);	×
185	}	×
186	}	×
187
188	nlohmann::json DotNodeSerializer::serialize(const data_flow::LibraryNode& library_node) {	×
189	const DotNode& gemm_node = static_cast<const DotNode&>(library_node);	×
190	nlohmann::json j;	×
191
192	serializer::JSONSerializer serializer;	×
193	j["code"] = gemm_node.code().value();	×
194	j["precision"] = gemm_node.precision();	×
195	j["n"] = serializer.expression(gemm_node.n());	×
196	j["incx"] = serializer.expression(gemm_node.incx());	×
197	j["incy"] = serializer.expression(gemm_node.incy());	×
198
199	return j;	×
200	}	×
201
202	data_flow::LibraryNode& DotNodeSerializer::deserialize(
203	const nlohmann::json& j, builder::StructuredSDFGBuilder& builder, structured_control_flow::Block& parent
204	) {	×
205	// Assertions for required fields
206	assert(j.contains("element_id"));	×
207	assert(j.contains("code"));	×
208	assert(j.contains("debug_info"));	×
209
210	auto code = j["code"].get<std::string>();	×
211	if (code != LibraryNodeType_DOT.value()) {	×
212	throw std::runtime_error("Invalid library node code");	×
213	}	×
214
215	// Extract debug info using JSONSerializer
216	sdfg::serializer::JSONSerializer serializer;	×
217	DebugInfo debug_info = serializer.json_to_debug_info(j["debug_info"]);	×
218
219	auto precision = j.at("precision").get<BLAS_Precision>();	×
220	auto n = symbolic::parse(j.at("n"));	×
221	auto incx = symbolic::parse(j.at("incx"));	×
222	auto incy = symbolic::parse(j.at("incy"));	×
223
224	auto implementation_type = j.at("implementation_type").get<std::string>();	×
225
226	return builder.add_library_node<DotNode>(parent, debug_info, implementation_type, precision, n, incx, incy);	×
227	}	×
228
229	DotNodeDispatcher_BLAS::DotNodeDispatcher_BLAS(
230	codegen::LanguageExtension& language_extension,
231	const Function& function,
232	const data_flow::DataFlowGraph& data_flow_graph,
233	const DotNode& node
234	)
235	: codegen::LibraryNodeDispatcher(language_extension, function, data_flow_graph, node) {}	×
236
237	void DotNodeDispatcher_BLAS::dispatch_code_with_edges(
238	codegen::CodegenOutput& out,
239	std::vector<codegen::DispatchInput>& inputs,
240	std::vector<codegen::DispatchOutput>& outputs
241	) {	×
242	auto& dot_node = static_cast<const DotNode&>(this->node_);	×
243
244	sdfg::types::Scalar base_type(types::PrimitiveType::Void);	×
245	BLAS_Precision precision = dot_node.precision();	×
246	switch (precision) {	×
247	case BLAS_Precision::h:	×
248	base_type = types::Scalar(types::PrimitiveType::Half);	×
249	break;	×
250	case BLAS_Precision::s:	×
251	base_type = types::Scalar(types::PrimitiveType::Float);	×
252	break;	×
253	case BLAS_Precision::d:	×
254	base_type = types::Scalar(types::PrimitiveType::Double);	×
255	break;	×
256	default:	×
257	throw std::runtime_error("Invalid BLAS_Precision value");	×
258	}	×
259
260	out.library_snippet_factory.require_dependency(BLASLibDependency::instance());	×
261
262	auto& output = outputs.at(0);	×
263	pre_allocate_output(out, output, dot_node.output(0));	×
264
265	out.stream << *output.local_name << " = ";	×
266	out.stream << "cblas_" << BLAS_Precision_to_string(precision) << "dot(";	×
267	out.stream.changeIndent(+4);	×
268	out.stream << this->language_extension_.expression(dot_node.n());	×
269	out.stream << ", ";	×
270	out.stream << inputs.at(0).expr;	×
271	out.stream << ", ";	×
272	out.stream << this->language_extension_.expression(dot_node.incx());	×
273	out.stream << ", ";	×
274	out.stream << inputs.at(1).expr;	×
275	out.stream << ", ";	×
276	out.stream << this->language_extension_.expression(dot_node.incy());	×
277	out.stream.changeIndent(-4);	×
278	out.stream << ");" << std::endl;	×
279	}	×
280
281
282	} // namespace blas
283	} // namespace math
284	} // namespace sdfg

daisytuner / docc / 28806128926

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