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

62.71

/sdfg/src/data_flow/library_nodes/math/tensor/reduce_ops/std_node.cpp

#include "sdfg/data_flow/library_nodes/math/tensor/reduce_ops/std_node.h"
#include "sdfg/builder/structured_sdfg_builder.h"
#include "sdfg/data_flow/library_nodes/math/tensor/elementwise_ops/mul_node.h"
#include "sdfg/data_flow/library_nodes/math/tensor/elementwise_ops/sqrt_node.h"
#include "sdfg/data_flow/library_nodes/math/tensor/elementwise_ops/sub_node.h"
#include "sdfg/data_flow/library_nodes/math/tensor/reduce_ops/mean_node.h"
#include "sdfg/data_flow/library_nodes/stdlib/malloc.h"
#include "sdfg/structured_control_flow/block.h"
#include "sdfg/types/scalar.h"
#include "sdfg/types/utils.h"

namespace sdfg {
namespace math {
namespace tensor {

StdNode::StdNode(
    size_t element_id,
    const DebugInfo& debug_info,
    const graph::Vertex vertex,
    data_flow::DataFlowGraph& parent,
    const std::vector<symbolic::Expression>& shape,
    const std::vector<int64_t>& axes,
    bool keepdims
)
    : ReduceNode(element_id, debug_info, vertex, parent, LibraryNodeType_Std, shape, axes, keepdims) {}

passes::LibNodeExpander::ExpandOutcome StdNode::expand_inner(
    passes::LibNodeExpander::AccessNodeExpand& expansion,
    structured_control_flow::Block& block,
    const data_flow::Memlet* iedge_input,
    const data_flow::Memlet* iedge_result,
    const std::vector<symbolic::Expression>& output_shape,
    const std::vector<int64_t>& sorted_axes
) {
    auto& out_type = iedge_result->base_type();
    auto& in_type = iedge_input->base_type();
    types::Scalar element_type(this->primitive_type(get_parent()));
    types::Pointer pointer_type(element_type);

    auto& seq = expansion.replace_with_sequence();
    auto& builder = expansion.builder();

    std::string tmp_x2_name = builder.find_new_name("_std_x2");
    builder.add_container(tmp_x2_name, pointer_type);
    std::string tmp_mean_x2_name = builder.find_new_name("_std_mean_x2");
    std::string tmp_mean_x_name = builder.find_new_name("_std_mean_x");

    symbolic::Expression bytes_in = types::get_type_size(element_type, false);
    for (auto& dim : this->shape_) {
        bytes_in = symbolic::mul(dim, bytes_in);
    }
    {
        auto& alloc_block = builder.add_block(seq, {}, this->debug_info());
        auto& tmp_x2_name_access = builder.add_access(alloc_block, tmp_x2_name);
        auto& tmp_x2_name_malloc_node =
            builder.add_library_node<stdlib::MallocNode>(alloc_block, this->debug_info(), bytes_in);
        builder.add_computational_memlet(
            alloc_block, tmp_x2_name_malloc_node, "_ret", tmp_x2_name_access, {}, pointer_type, this->debug_info()
        );
    }

    if (!output_shape.empty()) {
        symbolic::Expression bytes_out = types::get_type_size(element_type, false);
        for (auto& dim : output_shape) {
            bytes_out = symbolic::mul(dim, bytes_out);
        }
        builder.add_container(tmp_mean_x2_name, pointer_type);
        {
            auto& alloc_block = builder.add_block(seq, {}, this->debug_info());
            auto& tmp_mean_x2_name_access = builder.add_access(alloc_block, tmp_mean_x2_name);
            auto& tmp_mean_x2_name_malloc_node =
                builder.add_library_node<stdlib::MallocNode>(alloc_block, this->debug_info(), bytes_out);
            builder.add_computational_memlet(
                alloc_block,
                tmp_mean_x2_name_malloc_node,
                "_ret",
                tmp_mean_x2_name_access,
                {},
                pointer_type,
                this->debug_info()
            );
        }

        builder.add_container(tmp_mean_x_name, pointer_type);
        {
            auto& alloc_block = builder.add_block(seq, {}, this->debug_info());
            auto& tmp_mean_x_name_access = builder.add_access(alloc_block, tmp_mean_x_name);
            auto& tmp_mean_x_name_malloc_node =
                builder.add_library_node<stdlib::MallocNode>(alloc_block, this->debug_info(), bytes_out);
            builder.add_computational_memlet(
                alloc_block,
                tmp_mean_x_name_malloc_node,
                "_ret",
                tmp_mean_x_name_access,
                {},
                pointer_type,
                this->debug_info()
            );
        }
    } else {
        builder.add_container(tmp_mean_x2_name, element_type);
        builder.add_container(tmp_mean_x_name, element_type);
    }

    // 1. X^2
    auto& pow_block = builder.add_block(seq, {}, this->debug_info());
    auto& pow_in_node = expansion.add_scalar_input_access(pow_block, X_INPUT_IDX);
    auto& pow_out_node = builder.add_access(pow_block, tmp_x2_name, this->debug_info());

    auto& pow_node_1 = builder.add_library_node<MulNode>(pow_block, this->debug_info(), shape_);
    builder.add_computational_memlet(pow_block, pow_in_node, pow_node_1, "A", {}, in_type, this->debug_info());
    builder.add_computational_memlet(pow_block, pow_in_node, pow_node_1, "B", {}, in_type, this->debug_info());
    builder.add_computational_memlet(pow_block, pow_out_node, pow_node_1, "C", {}, in_type, this->debug_info());

    // 2. Mean(X^2)
    auto& mean_x2_block = builder.add_block(seq, {}, this->debug_info());
    auto& mean_x2_in_node = builder.add_access(mean_x2_block, tmp_x2_name, this->debug_info());
    auto& mean_x2_out_node = builder.add_access(mean_x2_block, tmp_mean_x2_name, this->debug_info());

    auto& mean_node_1 = builder.add_library_node<MeanNode>(mean_x2_block, this->debug_info(), shape_, axes_, keepdims_);
    builder.add_computational_memlet(mean_x2_block, mean_x2_in_node, mean_node_1, "X", {}, in_type, this->debug_info());
    builder
        .add_computational_memlet(mean_x2_block, mean_x2_out_node, mean_node_1, "Y", {}, out_type, this->debug_info());

    // 3. Mean(X)
    auto& mean_x_block = builder.add_block(seq, {}, this->debug_info());
    auto& mean_x_in_node = expansion.add_scalar_input_access(mean_x_block, X_INPUT_IDX);
    auto& mean_x_out_node = builder.add_access(mean_x_block, tmp_mean_x_name, this->debug_info());

    auto& mean_node_2 = builder.add_library_node<MeanNode>(mean_x_block, this->debug_info(), shape_, axes_, keepdims_);
    builder.add_computational_memlet(mean_x_block, mean_x_in_node, mean_node_2, "X", {}, in_type, this->debug_info());
    builder.add_computational_memlet(mean_x_block, mean_x_out_node, mean_node_2, "Y", {}, out_type, this->debug_info());

    // 4. Mean(X)^2
    auto& pow_mean_x_block = builder.add_block(seq, {}, this->debug_info());
    auto& pow_mean_x_in_node = builder.add_access(pow_mean_x_block, tmp_mean_x_name, this->debug_info());

    auto& pow_node_2 = builder.add_library_node<MulNode>(pow_mean_x_block, this->debug_info(), output_shape);

    builder
        .add_computational_memlet(pow_mean_x_block, pow_mean_x_in_node, pow_node_2, "A", {}, out_type, this->debug_info());
    builder
        .add_computational_memlet(pow_mean_x_block, pow_mean_x_in_node, pow_node_2, "B", {}, out_type, this->debug_info());
    builder
        .add_computational_memlet(pow_mean_x_block, pow_mean_x_in_node, pow_node_2, "C", {}, out_type, this->debug_info());

    // 5. Mean(X^2) - Mean(X)^2
    auto& sub_block = builder.add_block(seq, {}, this->debug_info());
    auto& sub_in1_node = builder.add_access(sub_block, tmp_mean_x2_name, this->debug_info());
    auto& sub_in2_node = builder.add_access(sub_block, tmp_mean_x_name, this->debug_info());
    auto& sub_out_node = expansion.add_scalar_input_access(sub_block, RESULT_PTR_IDX);

    auto& sub_node = builder.add_library_node<SubNode>(sub_block, this->debug_info(), output_shape);
    builder.add_computational_memlet(sub_block, sub_in1_node, sub_node, "A", {}, out_type, this->debug_info());
    builder.add_computational_memlet(sub_block, sub_in2_node, sub_node, "B", {}, out_type, this->debug_info());
    builder.add_computational_memlet(sub_block, sub_out_node, sub_node, "C", {}, out_type, this->debug_info());

    // 6. Sqrt(...)
    auto& sqrt_block = builder.add_block(seq, {}, this->debug_info());
    auto& sqrt_in_node = expansion.add_scalar_input_access(sqrt_block, RESULT_PTR_IDX);

    auto& sqrt_node = builder.add_library_node<SqrtNode>(sqrt_block, this->debug_info(), output_shape);
    builder.add_computational_memlet(sqrt_block, sqrt_in_node, sqrt_node, "X", {}, out_type, this->debug_info());
    builder.add_computational_memlet(sqrt_block, sqrt_in_node, sqrt_node, "Y", {}, out_type, this->debug_info());

    return expansion.successfully_expanded();
}

bool StdNode::expand_reduction(
    passes::LibNodeExpander::AccessNodeExpand& expansion,
    builder::StructuredSDFGBuilder& builder,
    structured_control_flow::Sequence& body,
    const types::Tensor& input_type,
    const types::Tensor& output_type,
    const data_flow::Subset& input_subset,
    const data_flow::Subset& output_subset
) {
    throw std::runtime_error("StdNode::expand_reduction should not be called");
}

std::string StdNode::identity(types::PrimitiveType primitive_type) const { return "0"; }

std::unique_ptr<data_flow::DataFlowNode> StdNode::
    clone(size_t element_id, const graph::Vertex vertex, data_flow::DataFlowGraph& parent) const {
    return std::unique_ptr<
        data_flow::DataFlowNode>(new StdNode(element_id, debug_info_, vertex, parent, shape_, axes_, keepdims_));
}

} // namespace tensor
} // namespace math
} // namespace sdfg

1	#include "sdfg/data_flow/library_nodes/math/tensor/reduce_ops/std_node.h"
2	#include "sdfg/builder/structured_sdfg_builder.h"
3	#include "sdfg/data_flow/library_nodes/math/tensor/elementwise_ops/mul_node.h"
4	#include "sdfg/data_flow/library_nodes/math/tensor/elementwise_ops/sqrt_node.h"
5	#include "sdfg/data_flow/library_nodes/math/tensor/elementwise_ops/sub_node.h"
6	#include "sdfg/data_flow/library_nodes/math/tensor/reduce_ops/mean_node.h"
7	#include "sdfg/data_flow/library_nodes/stdlib/malloc.h"
8	#include "sdfg/structured_control_flow/block.h"
9	#include "sdfg/types/scalar.h"
10	#include "sdfg/types/utils.h"
11
12	namespace sdfg {
13	namespace math {
14	namespace tensor {
15
16	StdNode::StdNode(
17	size_t element_id,
18	const DebugInfo& debug_info,
19	const graph::Vertex vertex,
20	data_flow::DataFlowGraph& parent,
21	const std::vector<symbolic::Expression>& shape,
22	const std::vector<int64_t>& axes,
23	bool keepdims
24	)
25	: ReduceNode(element_id, debug_info, vertex, parent, LibraryNodeType_Std, shape, axes, keepdims) {}	3✔
26
27	passes::LibNodeExpander::ExpandOutcome StdNode::expand_inner(
28	passes::LibNodeExpander::AccessNodeExpand& expansion,
29	structured_control_flow::Block& block,
30	const data_flow::Memlet* iedge_input,
31	const data_flow::Memlet* iedge_result,
32	const std::vector<symbolic::Expression>& output_shape,
33	const std::vector<int64_t>& sorted_axes
34	) {	3✔
35	auto& out_type = iedge_result->base_type();	3✔
36	auto& in_type = iedge_input->base_type();	3✔
37	types::Scalar element_type(this->primitive_type(get_parent()));	3✔
38	types::Pointer pointer_type(element_type);	3✔
39
40	auto& seq = expansion.replace_with_sequence();	3✔
41	auto& builder = expansion.builder();	3✔
42
43	std::string tmp_x2_name = builder.find_new_name("_std_x2");	3✔
44	builder.add_container(tmp_x2_name, pointer_type);	3✔
45	std::string tmp_mean_x2_name = builder.find_new_name("_std_mean_x2");	3✔
46	std::string tmp_mean_x_name = builder.find_new_name("_std_mean_x");	3✔
47
48	symbolic::Expression bytes_in = types::get_type_size(element_type, false);	3✔
49	for (auto& dim : this->shape_) {	3✔
50	bytes_in = symbolic::mul(dim, bytes_in);	3✔
51	}	3✔
52	{	3✔
53	auto& alloc_block = builder.add_block(seq, {}, this->debug_info());	3✔
54	auto& tmp_x2_name_access = builder.add_access(alloc_block, tmp_x2_name);	3✔
55	auto& tmp_x2_name_malloc_node =	3✔
56	builder.add_library_node<stdlib::MallocNode>(alloc_block, this->debug_info(), bytes_in);	3✔
57	builder.add_computational_memlet(	3✔
58	alloc_block, tmp_x2_name_malloc_node, "_ret", tmp_x2_name_access, {}, pointer_type, this->debug_info()	3✔
59	);	3✔
60	}	3✔
61
62	if (!output_shape.empty()) {	3✔
63	symbolic::Expression bytes_out = types::get_type_size(element_type, false);	×
64	for (auto& dim : output_shape) {	×
65	bytes_out = symbolic::mul(dim, bytes_out);	×
66	}	×
67	builder.add_container(tmp_mean_x2_name, pointer_type);	×
68	{	×
NEW 69	auto& alloc_block = builder.add_block(seq, {}, this->debug_info());	×
70	auto& tmp_mean_x2_name_access = builder.add_access(alloc_block, tmp_mean_x2_name);	×
71	auto& tmp_mean_x2_name_malloc_node =	×
72	builder.add_library_node<stdlib::MallocNode>(alloc_block, this->debug_info(), bytes_out);	×
73	builder.add_computational_memlet(	×
74	alloc_block,	×
75	tmp_mean_x2_name_malloc_node,	×
76	"_ret",	×
77	tmp_mean_x2_name_access,	×
78	{},	×
79	pointer_type,	×
80	this->debug_info()	×
81	);	×
82	}	×
83
84	builder.add_container(tmp_mean_x_name, pointer_type);	×
85	{	×
NEW 86	auto& alloc_block = builder.add_block(seq, {}, this->debug_info());	×
87	auto& tmp_mean_x_name_access = builder.add_access(alloc_block, tmp_mean_x_name);	×
88	auto& tmp_mean_x_name_malloc_node =	×
89	builder.add_library_node<stdlib::MallocNode>(alloc_block, this->debug_info(), bytes_out);	×
90	builder.add_computational_memlet(	×
91	alloc_block,	×
92	tmp_mean_x_name_malloc_node,	×
93	"_ret",	×
94	tmp_mean_x_name_access,	×
95	{},	×
96	pointer_type,	×
97	this->debug_info()	×
98	);	×
99	}	×
100	} else {	3✔
101	builder.add_container(tmp_mean_x2_name, element_type);	3✔
102	builder.add_container(tmp_mean_x_name, element_type);	3✔
103	}	3✔
104
105	// 1. X^2
106	auto& pow_block = builder.add_block(seq, {}, this->debug_info());	3✔
107	auto& pow_in_node = expansion.add_scalar_input_access(pow_block, X_INPUT_IDX);	3✔
108	auto& pow_out_node = builder.add_access(pow_block, tmp_x2_name, this->debug_info());	3✔
109
110	auto& pow_node_1 = builder.add_library_node<MulNode>(pow_block, this->debug_info(), shape_);	3✔
111	builder.add_computational_memlet(pow_block, pow_in_node, pow_node_1, "A", {}, in_type, this->debug_info());	3✔
112	builder.add_computational_memlet(pow_block, pow_in_node, pow_node_1, "B", {}, in_type, this->debug_info());	3✔
113	builder.add_computational_memlet(pow_block, pow_out_node, pow_node_1, "C", {}, in_type, this->debug_info());	3✔
114
115	// 2. Mean(X^2)
116	auto& mean_x2_block = builder.add_block(seq, {}, this->debug_info());	3✔
117	auto& mean_x2_in_node = builder.add_access(mean_x2_block, tmp_x2_name, this->debug_info());	3✔
118	auto& mean_x2_out_node = builder.add_access(mean_x2_block, tmp_mean_x2_name, this->debug_info());	3✔
119
120	auto& mean_node_1 = builder.add_library_node<MeanNode>(mean_x2_block, this->debug_info(), shape_, axes_, keepdims_);	3✔
121	builder.add_computational_memlet(mean_x2_block, mean_x2_in_node, mean_node_1, "X", {}, in_type, this->debug_info());	3✔
122	builder	3✔
123	.add_computational_memlet(mean_x2_block, mean_x2_out_node, mean_node_1, "Y", {}, out_type, this->debug_info());	3✔
124
125	// 3. Mean(X)
126	auto& mean_x_block = builder.add_block(seq, {}, this->debug_info());	3✔
127	auto& mean_x_in_node = expansion.add_scalar_input_access(mean_x_block, X_INPUT_IDX);	3✔
128	auto& mean_x_out_node = builder.add_access(mean_x_block, tmp_mean_x_name, this->debug_info());	3✔
129
130	auto& mean_node_2 = builder.add_library_node<MeanNode>(mean_x_block, this->debug_info(), shape_, axes_, keepdims_);	3✔
131	builder.add_computational_memlet(mean_x_block, mean_x_in_node, mean_node_2, "X", {}, in_type, this->debug_info());	3✔
132	builder.add_computational_memlet(mean_x_block, mean_x_out_node, mean_node_2, "Y", {}, out_type, this->debug_info());	3✔
133
134	// 4. Mean(X)^2
135	auto& pow_mean_x_block = builder.add_block(seq, {}, this->debug_info());	3✔
136	auto& pow_mean_x_in_node = builder.add_access(pow_mean_x_block, tmp_mean_x_name, this->debug_info());	3✔
137
138	auto& pow_node_2 = builder.add_library_node<MulNode>(pow_mean_x_block, this->debug_info(), output_shape);	3✔
139
140	builder	3✔
141	.add_computational_memlet(pow_mean_x_block, pow_mean_x_in_node, pow_node_2, "A", {}, out_type, this->debug_info());	3✔
142	builder	3✔
143	.add_computational_memlet(pow_mean_x_block, pow_mean_x_in_node, pow_node_2, "B", {}, out_type, this->debug_info());	3✔
144	builder	3✔
145	.add_computational_memlet(pow_mean_x_block, pow_mean_x_in_node, pow_node_2, "C", {}, out_type, this->debug_info());	3✔
146
147	// 5. Mean(X^2) - Mean(X)^2
148	auto& sub_block = builder.add_block(seq, {}, this->debug_info());	3✔
149	auto& sub_in1_node = builder.add_access(sub_block, tmp_mean_x2_name, this->debug_info());	3✔
150	auto& sub_in2_node = builder.add_access(sub_block, tmp_mean_x_name, this->debug_info());	3✔
151	auto& sub_out_node = expansion.add_scalar_input_access(sub_block, RESULT_PTR_IDX);	3✔
152
153	auto& sub_node = builder.add_library_node<SubNode>(sub_block, this->debug_info(), output_shape);	3✔
154	builder.add_computational_memlet(sub_block, sub_in1_node, sub_node, "A", {}, out_type, this->debug_info());	3✔
155	builder.add_computational_memlet(sub_block, sub_in2_node, sub_node, "B", {}, out_type, this->debug_info());	3✔
156	builder.add_computational_memlet(sub_block, sub_out_node, sub_node, "C", {}, out_type, this->debug_info());	3✔
157
158	// 6. Sqrt(...)
159	auto& sqrt_block = builder.add_block(seq, {}, this->debug_info());	3✔
160	auto& sqrt_in_node = expansion.add_scalar_input_access(sqrt_block, RESULT_PTR_IDX);	3✔
161
162	auto& sqrt_node = builder.add_library_node<SqrtNode>(sqrt_block, this->debug_info(), output_shape);	3✔
163	builder.add_computational_memlet(sqrt_block, sqrt_in_node, sqrt_node, "X", {}, out_type, this->debug_info());	3✔
164	builder.add_computational_memlet(sqrt_block, sqrt_in_node, sqrt_node, "Y", {}, out_type, this->debug_info());	3✔
165
166	return expansion.successfully_expanded();	3✔
167	}	3✔
168
169	bool StdNode::expand_reduction(
170	passes::LibNodeExpander::AccessNodeExpand& expansion,
171	builder::StructuredSDFGBuilder& builder,
172	structured_control_flow::Sequence& body,
173	const types::Tensor& input_type,
174	const types::Tensor& output_type,
175	const data_flow::Subset& input_subset,
176	const data_flow::Subset& output_subset
177	) {	×
178	throw std::runtime_error("StdNode::expand_reduction should not be called");	×
179	}	×
180
181	std::string StdNode::identity(types::PrimitiveType primitive_type) const { return "0"; }	×
182
183	std::unique_ptr<data_flow::DataFlowNode> StdNode::
184	clone(size_t element_id, const graph::Vertex vertex, data_flow::DataFlowGraph& parent) const {	×
185	return std::unique_ptr<	×
186	data_flow::DataFlowNode>(new StdNode(element_id, debug_info_, vertex, parent, shape_, axes_, keepdims_));	×
187	}	×
188
189	} // namespace tensor
190	} // namespace math
191	} // 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