23488936848

Committed 24 Mar 2026 12:16PM UTC coverage: 64.295%. Remained the same

Build # 23488936848

Build Type

push

github

Committed by

lukastruemper

Commit Message

bump version to v0.0.5

Coverage Stats

26649 of 41448 relevant lines covered (64.3%)

406.41 hits per line

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

91.28

/sdfg/src/passes/dataflow/tasklet_fusion.cpp

#include "sdfg/passes/dataflow/tasklet_fusion.h"

#include <unordered_set>

#include "sdfg/analysis/analysis.h"
#include "sdfg/analysis/users.h"
#include "sdfg/builder/structured_sdfg_builder.h"
#include "sdfg/data_flow/access_node.h"
#include "sdfg/data_flow/data_flow_graph.h"
#include "sdfg/data_flow/memlet.h"
#include "sdfg/data_flow/tasklet.h"
#include "sdfg/element.h"
#include "sdfg/structured_control_flow/block.h"
#include "sdfg/structured_control_flow/control_flow_node.h"
#include "sdfg/structured_control_flow/if_else.h"
#include "sdfg/structured_control_flow/sequence.h"
#include "sdfg/structured_control_flow/structured_loop.h"
#include "sdfg/types/type.h"
#include "sdfg/visitor/structured_sdfg_visitor.h"

namespace sdfg {
namespace passes {

bool TaskletFusion::container_allowed_accesses(const std::string& container, const Element* allowed_read_and_writes) {
    for (auto* user : this->users_analysis_.uses(container)) {
        if ((user->use() == analysis::Use::READ || user->use() == analysis::Use::WRITE) &&
            user->element() != allowed_read_and_writes) {
            return false;
        }
    }
    return true;
}

TaskletFusion::TaskletFusion(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager)
    : visitor::NonStoppingStructuredSDFGVisitor(builder, analysis_manager),
      users_analysis_(analysis_manager.get<analysis::Users>()) {};

bool TaskletFusion::accept(structured_control_flow::Block& block) {
    bool applied = false;
    auto& dfg = block.dataflow();

    // Fuse "input" assignments:
    std::unordered_set<data_flow::AccessNode*> removed_in_input_loop;
    for (auto* access_node : dfg.data_nodes()) {
        // Skip nodes removed as a side-effect of an earlier iteration (e.g. duplicate
        // access nodes for the same container that were merged away).
        if (removed_in_input_loop.count(access_node)) {
            continue;
        }
        // Require exactly one in edge and at leat one out edge
        if (dfg.in_degree(*access_node) != 1 || dfg.out_degree(*access_node) == 0) {
            continue;
        }

        // The in edge must provide a scalar
        auto& iedge = *dfg.in_edges(*access_node).begin();
        if (iedge.base_type().type_id() != types::TypeID::Scalar) {
            continue;
        }
        types::PrimitiveType iedge_base_type = iedge.base_type().primitive_type();

        // The source of the in edge must be a tasklet with an assignment
        auto* assign_tasklet = dynamic_cast<data_flow::Tasklet*>(&iedge.src());
        if (!assign_tasklet || assign_tasklet->code() != data_flow::TaskletCode::assign ||
            dfg.in_degree(*assign_tasklet) != 1) {
            continue;
        }
        auto& assign_tasklet_iedge = *dfg.in_edges(*assign_tasklet).begin();

        // All out edges must provide scalars and their destination must be a tasklet
        std::unordered_set<data_flow::Memlet*> oedges;
        for (auto& oedge : dfg.out_edges(*access_node)) {
            if (oedge.base_type().type_id() == types::TypeID::Scalar &&
                oedge.base_type().primitive_type() == iedge_base_type &&
                dynamic_cast<data_flow::Tasklet*>(&oedge.dst())) {
                oedges.insert(&oedge);
            }
        }
        if (oedges.size() != dfg.out_degree(*access_node)) {
            continue;
        }

        // The result tye of the in edge of the assignment tasklet must match with the base types
        auto result_type = assign_tasklet_iedge.result_type(this->builder_.subject());
        if (result_type->type_id() != types::TypeID::Scalar || result_type->primitive_type() != iedge_base_type) {
            continue;
        }

        // Container is only read and written in this access node (SSA)
        if (!this->container_allowed_accesses(access_node->data(), access_node)) {
            continue;
        }

        // Replace each out edge with an edge from the input access node from the assignment tasklet to the out edges's
        // tasklet
        for (auto* oedge : oedges) {
            auto& tasklet = dynamic_cast<data_flow::Tasklet&>(oedge->dst());
            auto& new_access_node = dynamic_cast<data_flow::AccessNode&>(assign_tasklet_iedge.src());

            // Prevent multiple access nodes with same container having in edges to the out edges's tasklet
            std::unordered_set<data_flow::Memlet*> other_iedges;
            for (auto& other_iedge : dfg.in_edges(tasklet)) {
                other_iedges.insert(&other_iedge);
            }
            for (auto* other_iedge : other_iedges) {
                if (dynamic_cast<data_flow::ConstantNode*>(&other_iedge->src())) {
                    continue;
                } else if (auto* other_access_node = dynamic_cast<data_flow::AccessNode*>(&other_iedge->src())) {
                    if (other_access_node == access_node || other_access_node->data() != new_access_node.data()) {
                        continue;
                    }
                    this->builder_.add_memlet(
                        block,
                        new_access_node,
                        other_iedge->src_conn(),
                        tasklet,
                        other_iedge->dst_conn(),
                        other_iedge->subset(),
                        other_iedge->base_type(),
                        other_iedge->debug_info()
                    );
                    this->builder_.remove_memlet(block, *other_iedge);
                    new_access_node
                        .set_debug_info(DebugInfo::merge(new_access_node.debug_info(), other_access_node->debug_info())
                        );
                    if (dfg.in_degree(*other_access_node) == 0 && dfg.out_degree(*other_access_node) == 0) {
                        removed_in_input_loop.insert(other_access_node);
                        this->builder_.remove_node(block, *other_access_node);
                    }
                }
            }

            DebugInfo debug_info = DebugInfo::merge(
                assign_tasklet_iedge.debug_info(),
                DebugInfo::merge(
                    assign_tasklet->debug_info(),
                    DebugInfo::merge(iedge.debug_info(), DebugInfo::merge(access_node->debug_info(), oedge->debug_info()))
                )
            );
            this->builder_.add_memlet(
                block,
                new_access_node,
                assign_tasklet_iedge.src_conn(),
                tasklet,
                oedge->dst_conn(),
                assign_tasklet_iedge.subset(),
                assign_tasklet_iedge.base_type(),
                debug_info
            );
            this->builder_.remove_memlet(block, *oedge);
        }

        // Remove the obsolete memlets
        this->builder_.remove_memlet(block, assign_tasklet_iedge);
        this->builder_.remove_memlet(block, iedge);

        // Remove the obsolete nodes
        this->builder_.remove_node(block, *assign_tasklet);
        this->builder_.remove_node(block, *access_node);

        applied = true;
    }

    // Fuse "output" assignments:
    for (auto* access_node : dfg.data_nodes()) {
        // Require exactly one in and one out edge
        if (dfg.in_degree(*access_node) != 1 || dfg.out_degree(*access_node) != 1) {
            continue;
        }

        // The in edge must provide a scalar
        auto& iedge = *dfg.in_edges(*access_node).begin();
        if (iedge.base_type().type_id() != types::TypeID::Scalar) {
            continue;
        }

        // The out edge must provide a scalar
        auto& oedge = *dfg.out_edges(*access_node).begin();
        if (oedge.base_type().type_id() != types::TypeID::Scalar) {
            continue;
        }

        // The source of the in edge must be a tasklet
        auto* tasklet = dynamic_cast<data_flow::Tasklet*>(&iedge.src());
        if (!tasklet) {
            continue;
        }

        // The destination of the out edge must be a tasklet with an assignment
        auto* assign_tasklet = dynamic_cast<data_flow::Tasklet*>(&oedge.dst());
        if (!assign_tasklet || assign_tasklet->code() != data_flow::TaskletCode::assign ||
            dfg.out_degree(*assign_tasklet) != 1) {
            continue;
        }
        auto& assign_tasklet_oedge = *dfg.out_edges(*assign_tasklet).begin();

        // Types must match
        if (iedge.base_type().primitive_type() != oedge.base_type().primitive_type()) {
            continue;
        }
        auto result_type = assign_tasklet_oedge.result_type(this->builder_.subject());
        if (result_type->type_id() != types::TypeID::Scalar ||
            result_type->primitive_type() != iedge.base_type().primitive_type()) {
            continue;
        }

        // Container is only read and written in this access node (SSA)
        if (!this->container_allowed_accesses(access_node->data(), access_node)) {
            continue;
        }

        // Replace the in edge with an edge from the in edge's tasklet to the output access node
        DebugInfo debug_info = DebugInfo::merge(
            iedge.debug_info(),
            DebugInfo::merge(
                access_node->debug_info(),
                DebugInfo::merge(
                    oedge.debug_info(),
                    DebugInfo::merge(assign_tasklet->debug_info(), assign_tasklet_oedge.debug_info())
                )
            )
        );
        this->builder_.add_memlet(
            block,
            *tasklet,
            iedge.src_conn(),
            dynamic_cast<data_flow::AccessNode&>(assign_tasklet_oedge.dst()),
            assign_tasklet_oedge.dst_conn(),
            assign_tasklet_oedge.subset(),
            assign_tasklet_oedge.base_type(),
            debug_info
        );
        this->builder_.remove_memlet(block, iedge);

        // Remove obsolete memlets
        this->builder_.remove_memlet(block, oedge);
        this->builder_.remove_memlet(block, assign_tasklet_oedge);

        // Remove obsolete nodes
        this->builder_.remove_node(block, *access_node);
        this->builder_.remove_node(block, *assign_tasklet);

        applied = true;
    }

    return applied;
}

} // namespace passes
} // namespace sdfg

1	#include "sdfg/passes/dataflow/tasklet_fusion.h"
2
3	#include <unordered_set>
4
5	#include "sdfg/analysis/analysis.h"
6	#include "sdfg/analysis/users.h"
7	#include "sdfg/builder/structured_sdfg_builder.h"
8	#include "sdfg/data_flow/access_node.h"
9	#include "sdfg/data_flow/data_flow_graph.h"
10	#include "sdfg/data_flow/memlet.h"
11	#include "sdfg/data_flow/tasklet.h"
12	#include "sdfg/element.h"
13	#include "sdfg/structured_control_flow/block.h"
14	#include "sdfg/structured_control_flow/control_flow_node.h"
15	#include "sdfg/structured_control_flow/if_else.h"
16	#include "sdfg/structured_control_flow/sequence.h"
17	#include "sdfg/structured_control_flow/structured_loop.h"
18	#include "sdfg/types/type.h"
19	#include "sdfg/visitor/structured_sdfg_visitor.h"
20
21	namespace sdfg {
22	namespace passes {
23
24	bool TaskletFusion::container_allowed_accesses(const std::string& container, const Element* allowed_read_and_writes) {	7✔
25	for (auto* user : this->users_analysis_.uses(container)) {	12✔
26	if ((user->use() == analysis::Use::READ \|\| user->use() == analysis::Use::WRITE) &&	12✔
27	user->element() != allowed_read_and_writes) {	12✔
28	return false;	2✔
29	}	2✔
30	}	12✔
31	return true;	5✔
32	}	7✔
33
34	TaskletFusion::TaskletFusion(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager)
35	: visitor::NonStoppingStructuredSDFGVisitor(builder, analysis_manager),	8✔
36	users_analysis_(analysis_manager.get<analysis::Users>()) {};	8✔
37
38	bool TaskletFusion::accept(structured_control_flow::Block& block) {	10✔
39	bool applied = false;	10✔
40	auto& dfg = block.dataflow();	10✔
41
42	// Fuse "input" assignments:
43	std::unordered_set<data_flow::AccessNode*> removed_in_input_loop;	10✔
44	for (auto* access_node : dfg.data_nodes()) {	36✔
45	// Skip nodes removed as a side-effect of an earlier iteration (e.g. duplicate
46	// access nodes for the same container that were merged away).
47	if (removed_in_input_loop.count(access_node)) {	36✔
48	continue;	×
49	}	×
50	// Require exactly one in edge and at leat one out edge
51	if (dfg.in_degree(access_node) != 1 \|\| dfg.out_degree(access_node) == 0) {	36✔
52	continue;	27✔
53	}	27✔
54
55	// The in edge must provide a scalar
56	auto& iedge = dfg.in_edges(access_node).begin();	9✔
57	if (iedge.base_type().type_id() != types::TypeID::Scalar) {	9✔
58	continue;	×
59	}	×
60	types::PrimitiveType iedge_base_type = iedge.base_type().primitive_type();	9✔
61
62	// The source of the in edge must be a tasklet with an assignment
63	auto* assign_tasklet = dynamic_cast<data_flow::Tasklet*>(&iedge.src());	9✔
64	if (!assign_tasklet \|\| assign_tasklet->code() != data_flow::TaskletCode::assign \|\|	9✔
65	dfg.in_degree(*assign_tasklet) != 1) {	9✔
66	continue;	3✔
67	}	3✔
68	auto& assign_tasklet_iedge = dfg.in_edges(assign_tasklet).begin();	6✔
69
70	// All out edges must provide scalars and their destination must be a tasklet
71	std::unordered_set<data_flow::Memlet*> oedges;	6✔
72	for (auto& oedge : dfg.out_edges(*access_node)) {	6✔
73	if (oedge.base_type().type_id() == types::TypeID::Scalar &&	6✔
74	oedge.base_type().primitive_type() == iedge_base_type &&	6✔
75	dynamic_cast<data_flow::Tasklet*>(&oedge.dst())) {	6✔
76	oedges.insert(&oedge);	6✔
77	}	6✔
78	}	6✔
79	if (oedges.size() != dfg.out_degree(*access_node)) {	6✔
80	continue;	×
81	}	×
82
83	// The result tye of the in edge of the assignment tasklet must match with the base types
84	auto result_type = assign_tasklet_iedge.result_type(this->builder_.subject());	6✔
85	if (result_type->type_id() != types::TypeID::Scalar \|\| result_type->primitive_type() != iedge_base_type) {	6✔
86	continue;	1✔
87	}	1✔
88
89	// Container is only read and written in this access node (SSA)
90	if (!this->container_allowed_accesses(access_node->data(), access_node)) {	5✔
91	continue;	1✔
92	}	1✔
93
94	// Replace each out edge with an edge from the input access node from the assignment tasklet to the out edges's
95	// tasklet
96	for (auto* oedge : oedges) {	4✔
97	auto& tasklet = dynamic_cast<data_flow::Tasklet&>(oedge->dst());	4✔
98	auto& new_access_node = dynamic_cast<data_flow::AccessNode&>(assign_tasklet_iedge.src());	4✔
99
100	// Prevent multiple access nodes with same container having in edges to the out edges's tasklet
101	std::unordered_set<data_flow::Memlet*> other_iedges;	4✔
102	for (auto& other_iedge : dfg.in_edges(tasklet)) {	8✔
103	other_iedges.insert(&other_iedge);	8✔
104	}	8✔
105	for (auto* other_iedge : other_iedges) {	8✔
106	if (dynamic_cast<data_flow::ConstantNode*>(&other_iedge->src())) {	8✔
107	continue;	×
108	} else if (auto* other_access_node = dynamic_cast<data_flow::AccessNode*>(&other_iedge->src())) {	8✔
109	if (other_access_node == access_node \|\| other_access_node->data() != new_access_node.data()) {	8✔
110	continue;	6✔
111	}	6✔
112	this->builder_.add_memlet(	2✔
113	block,	2✔
114	new_access_node,	2✔
115	other_iedge->src_conn(),	2✔
116	tasklet,	2✔
117	other_iedge->dst_conn(),	2✔
118	other_iedge->subset(),	2✔
119	other_iedge->base_type(),	2✔
120	other_iedge->debug_info()	2✔
121	);	2✔
122	this->builder_.remove_memlet(block, *other_iedge);	2✔
123	new_access_node	2✔
124	.set_debug_info(DebugInfo::merge(new_access_node.debug_info(), other_access_node->debug_info())	2✔
125	);	2✔
126	if (dfg.in_degree(other_access_node) == 0 && dfg.out_degree(other_access_node) == 0) {	2✔
127	removed_in_input_loop.insert(other_access_node);	1✔
128	this->builder_.remove_node(block, *other_access_node);	1✔
129	}	1✔
130	}	2✔
131	}	8✔
132
133	DebugInfo debug_info = DebugInfo::merge(	4✔
134	assign_tasklet_iedge.debug_info(),	4✔
135	DebugInfo::merge(	4✔
136	assign_tasklet->debug_info(),	4✔
137	DebugInfo::merge(iedge.debug_info(), DebugInfo::merge(access_node->debug_info(), oedge->debug_info()))	4✔
138	)	4✔
139	);	4✔
140	this->builder_.add_memlet(	4✔
141	block,	4✔
142	new_access_node,	4✔
143	assign_tasklet_iedge.src_conn(),	4✔
144	tasklet,	4✔
145	oedge->dst_conn(),	4✔
146	assign_tasklet_iedge.subset(),	4✔
147	assign_tasklet_iedge.base_type(),	4✔
148	debug_info	4✔
149	);	4✔
150	this->builder_.remove_memlet(block, *oedge);	4✔
151	}	4✔
152
153	// Remove the obsolete memlets
154	this->builder_.remove_memlet(block, assign_tasklet_iedge);	4✔
155	this->builder_.remove_memlet(block, iedge);	4✔
156
157	// Remove the obsolete nodes
158	this->builder_.remove_node(block, *assign_tasklet);	4✔
159	this->builder_.remove_node(block, *access_node);	4✔
160
161	applied = true;	4✔
162	}	4✔
163
164	// Fuse "output" assignments:
165	for (auto* access_node : dfg.data_nodes()) {	31✔
166	// Require exactly one in and one out edge
167	if (dfg.in_degree(access_node) != 1 \|\| dfg.out_degree(access_node) != 1) {	31✔
168	continue;	26✔
169	}	26✔
170
171	// The in edge must provide a scalar
172	auto& iedge = dfg.in_edges(access_node).begin();	5✔
173	if (iedge.base_type().type_id() != types::TypeID::Scalar) {	5✔
174	continue;	×
175	}	×
176
177	// The out edge must provide a scalar
178	auto& oedge = dfg.out_edges(access_node).begin();	5✔
179	if (oedge.base_type().type_id() != types::TypeID::Scalar) {	5✔
180	continue;	×
181	}	×
182
183	// The source of the in edge must be a tasklet
184	auto* tasklet = dynamic_cast<data_flow::Tasklet*>(&iedge.src());	5✔
185	if (!tasklet) {	5✔
186	continue;	×
187	}	×
188
189	// The destination of the out edge must be a tasklet with an assignment
190	auto* assign_tasklet = dynamic_cast<data_flow::Tasklet*>(&oedge.dst());	5✔
191	if (!assign_tasklet \|\| assign_tasklet->code() != data_flow::TaskletCode::assign \|\|	5✔
192	dfg.out_degree(*assign_tasklet) != 1) {	5✔
193	continue;	2✔
194	}	2✔
195	auto& assign_tasklet_oedge = dfg.out_edges(assign_tasklet).begin();	3✔
196
197	// Types must match
198	if (iedge.base_type().primitive_type() != oedge.base_type().primitive_type()) {	3✔
199	continue;	×
200	}	×
201	auto result_type = assign_tasklet_oedge.result_type(this->builder_.subject());	3✔
202	if (result_type->type_id() != types::TypeID::Scalar \|\|	3✔
203	result_type->primitive_type() != iedge.base_type().primitive_type()) {	3✔
204	continue;	1✔
205	}	1✔
206
207	// Container is only read and written in this access node (SSA)
208	if (!this->container_allowed_accesses(access_node->data(), access_node)) {	2✔
209	continue;	1✔
210	}	1✔
211
212	// Replace the in edge with an edge from the in edge's tasklet to the output access node
213	DebugInfo debug_info = DebugInfo::merge(	1✔
214	iedge.debug_info(),	1✔
215	DebugInfo::merge(	1✔
216	access_node->debug_info(),	1✔
217	DebugInfo::merge(	1✔
218	oedge.debug_info(),	1✔
219	DebugInfo::merge(assign_tasklet->debug_info(), assign_tasklet_oedge.debug_info())	1✔
220	)	1✔
221	)	1✔
222	);	1✔
223	this->builder_.add_memlet(	1✔
224	block,	1✔
225	*tasklet,	1✔
226	iedge.src_conn(),	1✔
227	dynamic_cast<data_flow::AccessNode&>(assign_tasklet_oedge.dst()),	1✔
228	assign_tasklet_oedge.dst_conn(),	1✔
229	assign_tasklet_oedge.subset(),	1✔
230	assign_tasklet_oedge.base_type(),	1✔
231	debug_info	1✔
232	);	1✔
233	this->builder_.remove_memlet(block, iedge);	1✔
234
235	// Remove obsolete memlets
236	this->builder_.remove_memlet(block, oedge);	1✔
237	this->builder_.remove_memlet(block, assign_tasklet_oedge);	1✔
238
239	// Remove obsolete nodes
240	this->builder_.remove_node(block, *access_node);	1✔
241	this->builder_.remove_node(block, *assign_tasklet);	1✔
242
243	applied = true;	1✔
244	}	1✔
245
246	return applied;	10✔
247	}	10✔
248
249	} // namespace passes
250	} // namespace sdfg

daisytuner / docc / 23488936848

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