26521975951

Committed 27 May 2026 03:45PM UTC coverage: 60.869% (-0.02%) from 60.886%

Build # 26521975951

Build Type

push

github

Committed by

web-flow

Commit Message

Libnode ptr edges (#719)

Migrating SDFGs to treat pointers as inputs to libNodes / Calls as scalars.
A pointer will only appear in an output edge if its actually returned from the function (like malloc).

* Stdlib, Blas and Tensor Matmul nodes were migrated to this new format. Other, currently transitory Tensor Nodes are not yet migrated.
* DOCC version was bumped to incorporate previous docc-llvm versions (up to 0.4.0) that had been counted separately.
! Until all passes consider the use / leak of pointers as uncertainty / hiding potential writes, TensorNodes are declared as general side-effect.
* Lots of utility functions to centralize the creation (and edges) of various libNodes that needed to be changed.
* Fixed & unified docc paths across python and llvm front-ends.
* Skip BlockFusion test that fails to its libNodes currently having side effects
~ Prevent a crash in DotViz when using symbolic offsets into structs
* Removing old ConstProp pass, it is not safe for the new pointer representation and should not be all too critical

Coverage Stats

961 of 1749 new or added lines in 52 files covered. (54.95%)

87 existing lines in 28 files now uncovered.

35225 of 57870 relevant lines covered (60.87%)

11046.32 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)) {	15✔
26	if ((user->use() == analysis::Use::READ \|\| user->use() == analysis::Use::WRITE) &&	15✔
27	user->element() != allowed_read_and_writes) {	15✔
28	return false;	2✔
29	}	2✔
30	}	15✔
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✔
UNCOV 48	continue;	×
UNCOV 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 / 26521975951

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