22755770845

Committed 06 Mar 2026 08:39AM UTC coverage: 64.441% (-0.004%) from 64.445%

Build # 22755770845

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #560 from daisytuner/quick-fix-dead-data-elim

Quick fix dead data elim

Coverage Stats

6 of 10 new or added lines in 3 files covered. (60.0%)

24490 of 38004 relevant lines covered (64.44%)

386.53 hits per line

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

81.94

/sdfg/src/passes/dataflow/dead_data_elimination.cpp

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

#include "sdfg/analysis/data_dependency_analysis.h"
#include "sdfg/data_flow/library_nodes/stdlib/malloc.h"
#include "sdfg/visualizer/dot_visualizer.h"

namespace sdfg {
namespace passes {

DeadDataElimination::DeadDataElimination() : Pass(), permissive_(false) {};

DeadDataElimination::DeadDataElimination(bool permissive) : Pass(), permissive_(permissive) {};

std::string DeadDataElimination::name() { return "DeadDataElimination"; };

bool DeadDataElimination::run_pass(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {
    bool applied = false;

    auto& sdfg = builder.subject();
    auto& users = analysis_manager.get<analysis::Users>();
    auto& data_dependency_analysis = analysis_manager.get<analysis::DataDependencyAnalysis>();

    // Eliminate dead code, i.e., never read
    std::unordered_set<std::string> dead;
    for (auto& name : sdfg.containers()) {
        if (!sdfg.is_transient(name)) {
            continue;
        }
        if (users.num_views(name) > 0 || users.num_moves(name) > 0) {
            continue;
        }
        auto num_reads = users.num_reads(name);
        if (!num_reads && users.num_writes(name) == 0) {
            dead.insert(name);
            applied = true;
            continue;
        }

        if (sdfg.type(name).type_id() == types::TypeID::Pointer) {
            continue;
            // use analysis does not return actual reads and writes for pointers. So if [name] is a pointer,
            // num reads/writes, does not actually mean no reads exist and any removal is problematic
        }


        bool completely_unused = !num_reads; // if there are reads left, we can never remove the container, but maybe
                                             // some writes
        auto raws = data_dependency_analysis.definitions(name);
        for (auto set : raws) {
            bool no_reads = false;
            if (set.second.size() == 0) {
                no_reads = true;
            }
            if (data_dependency_analysis.is_undefined_user(*set.first)) {
                continue;
            }

            if (no_reads) {
                bool could_eliminate_write = false;
                auto write = set.first;
                if (auto transition = dynamic_cast<structured_control_flow::Transition*>(write->element())) {
                    transition->assignments().erase(symbolic::symbol(name));
                    applied = true;
                    could_eliminate_write = true;
                } else if (auto access_node = dynamic_cast<data_flow::AccessNode*>(write->element())) {
                    auto& graph = access_node->get_parent();

                    auto& src = (*graph.in_edges(*access_node).begin()).src();
                    if (auto tasklet = dynamic_cast<data_flow::Tasklet*>(&src)) {
                        auto& block = dynamic_cast<structured_control_flow::Block&>(*graph.get_parent());
                        builder.clear_node(block, *tasklet);
                        applied = true;
                        could_eliminate_write = true;
                    } else if (auto library_node = dynamic_cast<data_flow::LibraryNode*>(&src)) {
                        if (!library_node->side_effect() ||
                            (permissive_ && library_node->code() == stdlib::LibraryNodeType_Malloc)) {
                            auto& block = dynamic_cast<structured_control_flow::Block&>(*graph.get_parent());
                            builder.clear_node(block, *library_node);
                            applied = true;
                            could_eliminate_write = true;
                        }
                    }
                }

                completely_unused &= could_eliminate_write;
            }
        }

        if (completely_unused) { // no reads, and all remaining writes could be removed
            dead.insert(name);
        }
    }

    for (auto& name : dead) {
        builder.remove_container(name);
    }

    return applied;
};

} // namespace passes
} // namespace sdfg

1	#include "sdfg/passes/dataflow/dead_data_elimination.h"
2
3	#include "sdfg/analysis/data_dependency_analysis.h"
4	#include "sdfg/data_flow/library_nodes/stdlib/malloc.h"
5	#include "sdfg/visualizer/dot_visualizer.h"
6
7	namespace sdfg {
8	namespace passes {
9
10	DeadDataElimination::DeadDataElimination() : Pass(), permissive_(false) {};	38✔
11
12	DeadDataElimination::DeadDataElimination(bool permissive) : Pass(), permissive_(permissive) {};	1✔
13
14	std::string DeadDataElimination::name() { return "DeadDataElimination"; };	×
15
16	bool DeadDataElimination::run_pass(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	74✔
17	bool applied = false;	74✔
18
19	auto& sdfg = builder.subject();	74✔
20	auto& users = analysis_manager.get<analysis::Users>();	74✔
21	auto& data_dependency_analysis = analysis_manager.get<analysis::DataDependencyAnalysis>();	74✔
22
23	// Eliminate dead code, i.e., never read
24	std::unordered_set<std::string> dead;	74✔
25	for (auto& name : sdfg.containers()) {	679✔
26	if (!sdfg.is_transient(name)) {	679✔
27	continue;	350✔
28	}	350✔
29	if (users.num_views(name) > 0 \|\| users.num_moves(name) > 0) {	329✔
30	continue;	×
31	}	×
32	auto num_reads = users.num_reads(name);	329✔
33	if (!num_reads && users.num_writes(name) == 0) {	329✔
34	dead.insert(name);	5✔
35	applied = true;	5✔
36	continue;	5✔
37	}	5✔
38
39	if (sdfg.type(name).type_id() == types::TypeID::Pointer) {	324✔
NEW 40	continue;	×
41	// use analysis does not return actual reads and writes for pointers. So if [name] is a pointer,
42	// num reads/writes, does not actually mean no reads exist and any removal is problematic
NEW 43	}	×
44
45
46	bool completely_unused = !num_reads; // if there are reads left, we can never remove the container, but maybe	324✔
47	// some writes
48	auto raws = data_dependency_analysis.definitions(name);	324✔
49	for (auto set : raws) {	588✔
50	bool no_reads = false;	588✔
51	if (set.second.size() == 0) {	588✔
52	no_reads = true;	8✔
53	}	8✔
54	if (data_dependency_analysis.is_undefined_user(*set.first)) {	588✔
55	continue;	1✔
56	}	1✔
57
58	if (no_reads) {	587✔
59	bool could_eliminate_write = false;	8✔
60	auto write = set.first;	8✔
61	if (auto transition = dynamic_cast<structured_control_flow::Transition*>(write->element())) {	8✔
62	transition->assignments().erase(symbolic::symbol(name));	7✔
63	applied = true;	7✔
64	could_eliminate_write = true;	7✔
65	} else if (auto access_node = dynamic_cast<data_flow::AccessNode*>(write->element())) {	7✔
66	auto& graph = access_node->get_parent();	1✔
67
68	auto& src = (graph.in_edges(access_node).begin()).src();	1✔
69	if (auto tasklet = dynamic_cast<data_flow::Tasklet*>(&src)) {	1✔
70	auto& block = dynamic_cast<structured_control_flow::Block&>(*graph.get_parent());	1✔
71	builder.clear_node(block, *tasklet);	1✔
72	applied = true;	1✔
73	could_eliminate_write = true;	1✔
74	} else if (auto library_node = dynamic_cast<data_flow::LibraryNode*>(&src)) {	1✔
75	if (!library_node->side_effect() \|\|	×
76	(permissive_ && library_node->code() == stdlib::LibraryNodeType_Malloc)) {	×
77	auto& block = dynamic_cast<structured_control_flow::Block&>(*graph.get_parent());	×
78	builder.clear_node(block, *library_node);	×
79	applied = true;	×
80	could_eliminate_write = true;	×
81	}	×
82	}	×
83	}	1✔
84
85	completely_unused &= could_eliminate_write;	8✔
86	}	8✔
87	}	587✔
88
89	if (completely_unused) { // no reads, and all remaining writes could be removed	324✔
90	dead.insert(name);	2✔
91	}	2✔
92	}	324✔
93
94	for (auto& name : dead) {	74✔
95	builder.remove_container(name);	7✔
96	}	7✔
97
98	return applied;	74✔
99	};	74✔
100
101	} // namespace passes
102	} // namespace sdfg

daisytuner / docc / 22755770845

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