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

0.0

/sdfg/src/data_flow/library_nodes/math/tensor/broadcast_node.cpp

#include "sdfg/data_flow/library_nodes/math/tensor/broadcast_node.h"
#include "sdfg/builder/structured_sdfg_builder.h"
#include "sdfg/data_flow/library_nodes/math/tensor/matmul_node.h"
#include "sdfg/structured_control_flow/for.h"

namespace sdfg {
namespace math {
namespace tensor {

BroadcastNode::BroadcastNode(
    size_t element_id,
    const DebugInfo& debug_info,
    const graph::Vertex vertex,
    data_flow::DataFlowGraph& parent,
    const std::vector<symbolic::Expression>& input_shape,
    const std::vector<symbolic::Expression>& output_shape
)
    : TensorNode(
          element_id,
          debug_info,
          vertex,
          parent,
          LibraryNodeType_Broadcast,
          {},
          {"Y", "X"},
          data_flow::ImplementationType_NONE
      ),
      input_shape_(input_shape), output_shape_(output_shape) {}

void BroadcastNode::validate(const Function& function) const {
    TensorNode::validate(function);

    auto& graph = this->get_parent();

    auto* iedge = graph.in_edge_for_connector(*this, inputs_.at(X_INPUT_IDX));
    auto& shape = static_cast<const types::Tensor&>(iedge->base_type());
    if (!shape.is_scalar()) {
        if (shape.shape().size() != this->input_shape_.size()) {
            throw InvalidSDFGException(
                "Library Node: Tensor shape must match node shape. Tensor shape: " +
                std::to_string(shape.shape().size()) + " Node shape: " + std::to_string(this->input_shape_.size())
            );
        }
        for (size_t i = 0; i < this->input_shape_.size(); ++i) {
            if (!symbolic::eq(shape.shape().at(i), this->input_shape_.at(i))) {
                throw InvalidSDFGException(
                    "Library Node: Tensor shape does not match expected shape. Tensor shape: " +
                    shape.shape().at(i)->__str__() + " Expected shape: " + this->input_shape_.at(i)->__str__()
                );
            }
        }
    }

    auto* oedge = graph.in_edge_for_connector(*this, inputs_.at(RESULT_PTR_IDX));
    auto& output_shape = static_cast<const types::Tensor&>(oedge->base_type());
    if (output_shape.shape().size() != this->output_shape_.size()) {
        throw InvalidSDFGException(
            "Library Node: Output tensor shape must match node shape. Output tensor shape: " +
            std::to_string(output_shape.shape().size()) + " Node shape: " + std::to_string(this->output_shape_.size())
        );
    }

    for (size_t i = 0; i < this->output_shape_.size(); ++i) {
        if (!symbolic::eq(output_shape.shape().at(i), this->output_shape_.at(i))) {
            throw InvalidSDFGException(
                "Library Node: Output tensor shape does not match expected shape. Output tensor shape: " +
                output_shape.shape().at(i)->__str__() + " Expected shape: " + this->output_shape_.at(i)->__str__()
            );
        }
    }
}

symbolic::SymbolSet BroadcastNode::symbols() const {
    symbolic::SymbolSet syms;
    for (const auto& dim : input_shape_) {
        for (auto& atom : symbolic::atoms(dim)) {
            syms.insert(atom);
        }
    }
    for (const auto& dim : output_shape_) {
        for (auto& atom : symbolic::atoms(dim)) {
            syms.insert(atom);
        }
    }
    return syms;
}

void BroadcastNode::replace(const symbolic::Expression old_expression, const symbolic::Expression new_expression) {
    for (auto& dim : input_shape_) {
        dim = symbolic::subs(dim, old_expression, new_expression);
    }
    for (auto& dim : output_shape_) {
        dim = symbolic::subs(dim, old_expression, new_expression);
    }
}

void BroadcastNode::replace(const symbolic::ExpressionMapping& replacements) {
    for (auto& dim : input_shape_) {
        dim = symbolic::subs(dim, replacements);
    }
    for (auto& dim : output_shape_) {
        dim = symbolic::subs(dim, replacements);
    }
}

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

    if (dataflow.in_degree(*this) != 2 || dataflow.out_degree(*this) != 0) {
        return context.unable();
    }

    auto edges = dataflow.in_edges_by_connector(*this);
    auto& in_edge = *edges.at(X_INPUT_IDX);
    auto& result_ptr_edge = *edges.at(RESULT_PTR_IDX);


    using Use = passes::LibNodeExpander::InputUse;
    auto standalone = context.replacement_requires_access_nodes({Use::IndirectWrite, Use::IndirectRead});

    if (!standalone) {
        return context.unable();
    }

    symbolic::MultiExpression loop_vars;
    auto& builder = standalone->builder();
    structured_control_flow::Sequence* inner_scope = nullptr;

    for (size_t i = 0; i < output_shape_.size(); ++i) {
        std::string var_name = builder.find_new_name("_i" + std::to_string(i));
        builder.add_container(var_name, types::Scalar(types::PrimitiveType::Int64));

        auto sym_var = symbolic::symbol(var_name);
        auto condition = symbolic::Lt(sym_var, output_shape_[i]);
        auto init = symbolic::zero();
        auto update = symbolic::add(sym_var, symbolic::one());

        if (i == 0) {
            auto& loop = standalone->replace_with_structured_loop(
                passes::LibNodeExpander::AccessNodeExpand::LoopType::Map,
                sym_var,
                condition,
                init,
                update,
                structured_control_flow::ScheduleType_Sequential::create()
            );
            inner_scope = &loop.root();
        } else {
            auto& loop = builder.add_map(
                *inner_scope,
                sym_var,
                condition,
                init,
                update,
                structured_control_flow::ScheduleType_Sequential::create(),
                {},
                this->debug_info()
            );
            inner_scope = &loop.root();
        }
        loop_vars.push_back(sym_var);
    }

    auto& tasklet_block = builder.add_block(*inner_scope, {}, this->debug_info());

    auto& in_acc = standalone->add_indirect_read_access(tasklet_block, X_INPUT_IDX);
    auto& out_acc = standalone->add_indirect_write_access(tasklet_block, RESULT_PTR_IDX);

    symbolic::MultiExpression input_subset = {};
    for (size_t i = 0; i < input_shape_.size(); ++i) {
        if (!symbolic::eq(input_shape_[i], symbolic::one())) {
            input_subset.push_back(loop_vars[i]);
        } else {
            input_subset.push_back(symbolic::zero());
        }
    }
    auto& iedge_tensor = static_cast<const types::Tensor&>(in_edge.base_type());
    if (iedge_tensor.is_scalar()) {
        input_subset = {};
    }

    auto& tasklet =
        builder.add_tasklet(tasklet_block, data_flow::TaskletCode::assign, "_out", {"_in"}, this->debug_info());

    builder.add_computational_memlet(
        tasklet_block, in_acc, tasklet, "_in", input_subset, in_edge.base_type(), this->debug_info()
    );
    builder.add_computational_memlet(
        tasklet_block, tasklet, "_out", out_acc, loop_vars, result_ptr_edge.base_type(), this->debug_info()
    );

    return standalone->successfully_expanded();
}

std::unique_ptr<data_flow::DataFlowNode> BroadcastNode::
    clone(size_t element_id, const graph::Vertex vertex, data_flow::DataFlowGraph& parent) const {
    return std::unique_ptr<data_flow::DataFlowNode>(
        new BroadcastNode(element_id, this->debug_info(), vertex, parent, input_shape_, output_shape_)
    );
}

data_flow::PointerAccessType BroadcastNode::pointer_access_type(int input_idx) const {
    if (input_idx == RESULT_PTR_IDX) {
        return data_flow::PointerAccessMeta::create_full_write_only(symbolic::__nullptr__(), true);
    } else if (input_idx == X_INPUT_IDX) {
        return data_flow::PointerAccessMeta::create_read_only(symbolic::__nullptr__(), true);
    } else {
        return TensorNode::pointer_access_type(input_idx);
    }
}

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

1	#include "sdfg/data_flow/library_nodes/math/tensor/broadcast_node.h"
2	#include "sdfg/builder/structured_sdfg_builder.h"
3	#include "sdfg/data_flow/library_nodes/math/tensor/matmul_node.h"
4	#include "sdfg/structured_control_flow/for.h"
5
6	namespace sdfg {
7	namespace math {
8	namespace tensor {
9
10	BroadcastNode::BroadcastNode(
11	size_t element_id,
12	const DebugInfo& debug_info,
13	const graph::Vertex vertex,
14	data_flow::DataFlowGraph& parent,
15	const std::vector<symbolic::Expression>& input_shape,
16	const std::vector<symbolic::Expression>& output_shape
17	)
18	: TensorNode(	×
19	element_id,	×
20	debug_info,	×
21	vertex,	×
22	parent,	×
23	LibraryNodeType_Broadcast,	×
NEW 24	{},	×
NEW 25	{"Y", "X"},	×
26	data_flow::ImplementationType_NONE	×
27	),	×
28	input_shape_(input_shape), output_shape_(output_shape) {}	×
29
30	void BroadcastNode::validate(const Function& function) const {	×
31	TensorNode::validate(function);	×
32
33	auto& graph = this->get_parent();	×
34
NEW 35	auto* iedge = graph.in_edge_for_connector(*this, inputs_.at(X_INPUT_IDX));	×
NEW 36	auto& shape = static_cast<const types::Tensor&>(iedge->base_type());	×
37	if (!shape.is_scalar()) {	×
38	if (shape.shape().size() != this->input_shape_.size()) {	×
39	throw InvalidSDFGException(	×
40	"Library Node: Tensor shape must match node shape. Tensor shape: " +	×
41	std::to_string(shape.shape().size()) + " Node shape: " + std::to_string(this->input_shape_.size())	×
42	);	×
43	}	×
44	for (size_t i = 0; i < this->input_shape_.size(); ++i) {	×
45	if (!symbolic::eq(shape.shape().at(i), this->input_shape_.at(i))) {	×
46	throw InvalidSDFGException(	×
47	"Library Node: Tensor shape does not match expected shape. Tensor shape: " +	×
48	shape.shape().at(i)->__str__() + " Expected shape: " + this->input_shape_.at(i)->__str__()	×
49	);	×
50	}	×
51	}	×
52	}	×
53
NEW 54	auto* oedge = graph.in_edge_for_connector(*this, inputs_.at(RESULT_PTR_IDX));	×
NEW 55	auto& output_shape = static_cast<const types::Tensor&>(oedge->base_type());	×
56	if (output_shape.shape().size() != this->output_shape_.size()) {	×
57	throw InvalidSDFGException(	×
58	"Library Node: Output tensor shape must match node shape. Output tensor shape: " +	×
59	std::to_string(output_shape.shape().size()) + " Node shape: " + std::to_string(this->output_shape_.size())	×
60	);	×
61	}	×
62
63	for (size_t i = 0; i < this->output_shape_.size(); ++i) {	×
64	if (!symbolic::eq(output_shape.shape().at(i), this->output_shape_.at(i))) {	×
65	throw InvalidSDFGException(	×
66	"Library Node: Output tensor shape does not match expected shape. Output tensor shape: " +	×
67	output_shape.shape().at(i)->__str__() + " Expected shape: " + this->output_shape_.at(i)->__str__()	×
68	);	×
69	}	×
70	}	×
71	}	×
72
73	symbolic::SymbolSet BroadcastNode::symbols() const {	×
74	symbolic::SymbolSet syms;	×
75	for (const auto& dim : input_shape_) {	×
76	for (auto& atom : symbolic::atoms(dim)) {	×
77	syms.insert(atom);	×
78	}	×
79	}	×
80	for (const auto& dim : output_shape_) {	×
81	for (auto& atom : symbolic::atoms(dim)) {	×
82	syms.insert(atom);	×
83	}	×
84	}	×
85	return syms;	×
86	}	×
87
88	void BroadcastNode::replace(const symbolic::Expression old_expression, const symbolic::Expression new_expression) {	×
89	for (auto& dim : input_shape_) {	×
90	dim = symbolic::subs(dim, old_expression, new_expression);	×
91	}	×
92	for (auto& dim : output_shape_) {	×
93	dim = symbolic::subs(dim, old_expression, new_expression);	×
94	}	×
95	}	×
96
97	void BroadcastNode::replace(const symbolic::ExpressionMapping& replacements) {	×
98	for (auto& dim : input_shape_) {	×
99	dim = symbolic::subs(dim, replacements);	×
100	}	×
101	for (auto& dim : output_shape_) {	×
102	dim = symbolic::subs(dim, replacements);	×
103	}	×
104	}	×
105
106	passes::LibNodeExpander::ExpandOutcome BroadcastNode::
NEW 107	expand(passes::LibNodeExpander::ExpandContext& context, structured_control_flow::Block& block) {	×
108	auto& dataflow = this->get_parent();	×
109
NEW 110	if (dataflow.in_degree(this) != 2 \|\| dataflow.out_degree(this) != 0) {	×
NEW 111	return context.unable();	×
112	}	×
113
NEW 114	auto edges = dataflow.in_edges_by_connector(*this);	×
NEW 115	auto& in_edge = *edges.at(X_INPUT_IDX);	×
NEW 116	auto& result_ptr_edge = *edges.at(RESULT_PTR_IDX);	×
117
118
NEW 119	using Use = passes::LibNodeExpander::InputUse;	×
NEW 120	auto standalone = context.replacement_requires_access_nodes({Use::IndirectWrite, Use::IndirectRead});	×
121
NEW 122	if (!standalone) {	×
NEW 123	return context.unable();	×
NEW 124	}	×
125
126	symbolic::MultiExpression loop_vars;	×
NEW 127	auto& builder = standalone->builder();	×
128	structured_control_flow::Sequence* inner_scope = nullptr;	×
129
130	for (size_t i = 0; i < output_shape_.size(); ++i) {	×
131	std::string var_name = builder.find_new_name("_i" + std::to_string(i));	×
132	builder.add_container(var_name, types::Scalar(types::PrimitiveType::Int64));	×
133
134	auto sym_var = symbolic::symbol(var_name);	×
135	auto condition = symbolic::Lt(sym_var, output_shape_[i]);	×
136	auto init = symbolic::zero();	×
137	auto update = symbolic::add(sym_var, symbolic::one());	×
138
139	if (i == 0) {	×
NEW 140	auto& loop = standalone->replace_with_structured_loop(	×
NEW 141	passes::LibNodeExpander::AccessNodeExpand::LoopType::Map,	×
142	sym_var,	×
143	condition,	×
144	init,	×
145	update,	×
NEW 146	structured_control_flow::ScheduleType_Sequential::create()	×
147	);	×
148	inner_scope = &loop.root();	×
149	} else {	×
150	auto& loop = builder.add_map(	×
151	*inner_scope,	×
152	sym_var,	×
153	condition,	×
154	init,	×
155	update,	×
156	structured_control_flow::ScheduleType_Sequential::create(),	×
157	{},	×
158	this->debug_info()	×
159	);	×
160	inner_scope = &loop.root();	×
161	}	×
162	loop_vars.push_back(sym_var);	×
163	}	×
164
165	auto& tasklet_block = builder.add_block(*inner_scope, {}, this->debug_info());	×
166
NEW 167	auto& in_acc = standalone->add_indirect_read_access(tasklet_block, X_INPUT_IDX);	×
NEW 168	auto& out_acc = standalone->add_indirect_write_access(tasklet_block, RESULT_PTR_IDX);	×
169
170	symbolic::MultiExpression input_subset = {};	×
171	for (size_t i = 0; i < input_shape_.size(); ++i) {	×
172	if (!symbolic::eq(input_shape_[i], symbolic::one())) {	×
173	input_subset.push_back(loop_vars[i]);	×
174	} else {	×
175	input_subset.push_back(symbolic::zero());	×
176	}	×
177	}	×
178	auto& iedge_tensor = static_cast<const types::Tensor&>(in_edge.base_type());	×
179	if (iedge_tensor.is_scalar()) {	×
180	input_subset = {};	×
181	}	×
182
183	auto& tasklet =	×
184	builder.add_tasklet(tasklet_block, data_flow::TaskletCode::assign, "_out", {"_in"}, this->debug_info());	×
185
186	builder.add_computational_memlet(	×
187	tasklet_block, in_acc, tasklet, "_in", input_subset, in_edge.base_type(), this->debug_info()	×
188	);	×
189	builder.add_computational_memlet(	×
NEW 190	tasklet_block, tasklet, "_out", out_acc, loop_vars, result_ptr_edge.base_type(), this->debug_info()	×
191	);	×
192
NEW 193	return standalone->successfully_expanded();	×
194	}	×
195
196	std::unique_ptr<data_flow::DataFlowNode> BroadcastNode::
197	clone(size_t element_id, const graph::Vertex vertex, data_flow::DataFlowGraph& parent) const {	×
198	return std::unique_ptr<data_flow::DataFlowNode>(	×
199	new BroadcastNode(element_id, this->debug_info(), vertex, parent, input_shape_, output_shape_)	×
200	);	×
201	}	×
202
NEW 203	data_flow::PointerAccessType BroadcastNode::pointer_access_type(int input_idx) const {	×
NEW 204	if (input_idx == RESULT_PTR_IDX) {	×
NEW 205	return data_flow::PointerAccessMeta::create_full_write_only(symbolic::__nullptr__(), true);	×
NEW 206	} else if (input_idx == X_INPUT_IDX) {	×
NEW 207	return data_flow::PointerAccessMeta::create_read_only(symbolic::__nullptr__(), true);	×
NEW 208	} else {	×
NEW 209	return TensorNode::pointer_access_type(input_idx);	×
NEW 210	}	×
NEW 211	}	×
212
213	} // namespace tensor
214	} // namespace math
215	} // 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