23659726771

Committed 27 Mar 2026 05:43PM UTC coverage: 64.877% (+0.03%) from 64.845%

Build # 23659726771

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #614 from daisytuner/dde-clean-fix

Fixing DDE & clear_node: block it from removing critical output edges…

Coverage Stats

96 of 99 new or added lines in 9 files covered. (96.97%)

4 existing lines in 2 files now uncovered.

27037 of 41674 relevant lines covered (64.88%)

407.71 hits per line

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

94.1

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

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

#include "sdfg/analysis/base_user_visitor.h"
#include "sdfg/analysis/data_dependency_analysis.h"
#include "sdfg/data_flow/library_nodes/stdlib/free.h"
#include "sdfg/data_flow/library_nodes/stdlib/malloc.h"
#include "sdfg/visitor/structured_sdfg_visitor.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"; };

/**
 * Finds memory areas (heap for now) that are wholly owned by the surrounding function. Owned memory can be removed if
 * its no longer used, writes to it can be ellided if the data is never read. This is not true for memory writes in
 * general, as you must prove no reference to that data ever escapes our control
 */
class MemoryOwnershipAnalysis : public analysis::BaseUserVisitor {
    enum class BlockerType { Escape, Overwrite };

    struct FreeCluster {
        const Block* block;
        const data_flow::Memlet* in;
        const data_flow::Memlet* out;

        FreeCluster(const Block* b, const data_flow::Memlet* i, const data_flow::Memlet* o) : block(b), in(i), out(o) {}
    };

    struct OwnedArea {
        data_flow::Memlet* producer;
        structured_control_flow::Block* producer_block;
        symbolic::Expression allocation_size;
        bool non_ssa = false;
        std::vector<FreeCluster> free_clusters;

        OwnedArea(data_flow::Memlet* p, structured_control_flow::Block* pb, symbolic::Expression as, bool ns)
            : producer(p), producer_block(pb), allocation_size(std::move(as)), non_ssa(ns) {}

        void remove_from(builder::StructuredSDFGBuilder& builder) const;
    };

private:
    StructuredSDFG& sdfg_;
    // memory that is allocated by us and therefore 'owned' until it escapes
    std::unordered_map<std::string, OwnedArea> originally_owned_data_;
    std::unordered_map<std::string, std::unordered_map<const Element*, BlockerType>> blockers_;
    std::unordered_set<std::string> fully_owned_; // never escaped

public:
    MemoryOwnershipAnalysis(StructuredSDFG& sdfg);

    void run(analysis::AnalysisManager& manager);

    bool visit(sdfg::structured_control_flow::Block& node) override;

    void use_as_symbol_write(const symbolic::Symbol& container, const Element* user, SymbolWriteLocation loc) override;
    void use_as_symbol_read(
        const std::string& container,
        const Element* user,
        SymbolReadLocation loc,
        int loc_index,
        symbolic::Expression expr
    ) override;
    void use_as_src_node(
        const std::string& container,
        const data_flow::AccessNode& node,
        const data_flow::Memlet& edge,
        const Block& block
    ) override;
    void use_as_dst_node(
        const std::string& container,
        const data_flow::AccessNode& node,
        const data_flow::Memlet& edge,
        const Block& block
    ) override;
    void use_as_return_src(const std::string& container, const Return& ret) override;

    const std::unordered_set<std::string>& fully_owned_areas() const { return fully_owned_; }

    const OwnedArea& owned_area(const std::string& container) const { return originally_owned_data_.at(container); }

private:
    static bool excusedEscape(const Element* element, const OwnedArea& area);
    static bool excusedOverwrite(const Element* element, const OwnedArea& area);
};

void MemoryOwnershipAnalysis::OwnedArea::remove_from(builder::StructuredSDFGBuilder& builder) const {
    auto& malloc_write = this->producer->dst();
    auto& malloc_node = this->producer->src();
    builder.clear_code_node_legacy(*this->producer_block, dynamic_cast<const data_flow::CodeNode&>(malloc_node));
    // builder.clear_node(
    //     *this->producer_block, dynamic_cast<data_flow::AccessNode&>(malloc_write), {&malloc_write, &malloc_node}
    // );

    for (auto& free_cluster : this->free_clusters) {
        auto& memlet = *free_cluster.out;
        builder.clear_code_node_legacy(
            *const_cast<Block*>(free_cluster.block), dynamic_cast<const data_flow::CodeNode&>(memlet.src())
        );
        // builder.clear_node(*const_cast<Block*>(free_cluster.block), memlet.dst(), {&memlet.dst(), &memlet.src()});
    }
}

MemoryOwnershipAnalysis::MemoryOwnershipAnalysis(StructuredSDFG& sdfg) : sdfg_(sdfg) {}

bool MemoryOwnershipAnalysis::excusedEscape(const Element* element, const OwnedArea& area) {
    // An escape is excused if it matches the input edge of one of the free_clusters.
    // Reading the pointer to pass it to free() is not a real escape.
    for (const auto& cluster : area.free_clusters) {
        if (element == cluster.in) {
            return true;
        }
    }
    return false;
}

bool MemoryOwnershipAnalysis::excusedOverwrite(const Element* element, const OwnedArea& area) {
    // The producer (malloc output edge) is an excused overwrite — it's the initial assignment.
    if (element == area.producer) {
        return true;
    }
    // The output edge of a free cluster is an excused overwrite — free sets the pointer
    // to NULL (a fake overwrite that doesn't represent a meaningful reassignment).
    for (const auto& cluster : area.free_clusters) {
        if (element == cluster.out) {
            return true;
        }
    }
    return false;
}


void MemoryOwnershipAnalysis::run(analysis::AnalysisManager& manager) {
    dispatch(sdfg_.root());

    for (auto& [name, area] : originally_owned_data_) {
        if (!area.non_ssa && area.allocation_size != SymEngine::null) {
            auto it = blockers_.find(name);
            if (it != blockers_.end()) {
                bool killed = false;
                for (auto& [element, type] : it->second) {
                    if (type == BlockerType::Escape) {
                        if (!excusedEscape(element, area)) {
                            killed = true;
                            break;
                        }
                    } else if (type == BlockerType::Overwrite) {
                        if (!excusedOverwrite(element, area)) {
                            killed = true;
                            break;
                        }
                    }
                }
                if (!killed) {
                    fully_owned_.insert(name);
                }
            } else {
                fully_owned_.insert(name);
            }
        }
    }
}


bool MemoryOwnershipAnalysis::visit(sdfg::structured_control_flow::Block& node) {
    auto& dflow = node.dataflow();
    for (auto& library_node : dflow.library_nodes()) {
        if (library_node->code() == stdlib::LibraryNodeType_Malloc) {
            auto* malloc_node = dynamic_cast<const stdlib::MallocNode*>(library_node);
            auto& alloc_size = malloc_node->size();
            auto output_conn = malloc_node->output(0);
            auto oedges = dflow.out_edges(*malloc_node) |
                          std::views::filter([&](const auto& e) { return e.src_conn() == output_conn; });
            for (auto& oedge : oedges) {
                auto* access_node = dynamic_cast<data_flow::AccessNode*>(&oedge.dst());
                if (access_node && oedge.is_dst_write()) {
                    auto container = access_node->data();
                    auto it = originally_owned_data_.find(container);
                    if (it != originally_owned_data_.end()) {
                        auto& area = it->second;
                        area.non_ssa = true;
                        area.allocation_size = SymEngine::null;
                        area.producer_block = nullptr;
                        area.producer = nullptr;
                        // DEBUG_PRINTLN("Conflicting ownership of " << container);
                        continue;
                    }
                    originally_owned_data_.emplace(
                        std::piecewise_construct,
                        std::forward_as_tuple(container),
                        std::forward_as_tuple(&oedge, &node, alloc_size, false)
                    );
                }
            }
        } else if (library_node->code() == stdlib::LibraryNodeType_Free) {
            auto* free_node = dynamic_cast<const stdlib::FreeNode*>(library_node);
            auto input = dflow.in_edge_for_connector(*free_node, free_node->input(0));
            auto outputs = dflow.out_edges_for_connector(*free_node, free_node->output(0));
            if (input && outputs.size() == 1) {
                auto* in_access = dynamic_cast<const data_flow::AccessNode*>(&input->src());
                auto* out_access = dynamic_cast<const data_flow::AccessNode*>(&outputs.at(0)->dst());

                if (in_access && out_access && in_access->data() == out_access->data()) {
                    auto& container = in_access->data();
                    if (sdfg_.type(container).type_id() == types::TypeID::Pointer) {
                        auto area_it = originally_owned_data_.find(container);
                        if (area_it != originally_owned_data_.end()) { // we scan in execution order. Malloc needs to
                                                                       // have been found before
                            auto& area = area_it->second;
                            area.free_clusters.emplace_back(&node, input, outputs[0]);
                        }
                    }
                }
            }
        }
    }

    return BaseUserVisitor::visit(node);
}


void MemoryOwnershipAnalysis::use_as_return_src(const std::string& container, const Return& ret) {
    if (sdfg_.type(container).type_id() == types::TypeID::Pointer) {
        blockers_[container].emplace(&ret, BlockerType::Escape);
    }
}

void MemoryOwnershipAnalysis::
    use_as_symbol_write(const symbolic::Symbol& container, const Element* user, SymbolWriteLocation loc) {
    auto name = container->get_name();
    if (sdfg_.type(name).type_id() == types::TypeID::Pointer) {
        blockers_[name].emplace(user, BlockerType::Overwrite);
    }
}

void MemoryOwnershipAnalysis::use_as_symbol_read(
    const std::string& container, const Element* user, SymbolReadLocation loc, int loc_index, symbolic::Expression expr
) {
    auto& type = sdfg_.type(container);
    if (type.type_id() == types::TypeID::Pointer) {
        blockers_[container].emplace(user, BlockerType::Escape);
    }
}

void MemoryOwnershipAnalysis::use_as_src_node(
    const std::string& container, const data_flow::AccessNode& node, const data_flow::Memlet& edge, const Block& block
) {
    auto& type = sdfg_.type(container);
    if (edge.is_src_pointed_to_address_leak(type) || edge.is_src_address_leak()) {
        // pulls a reference to the owned memory area or can alias the entire pointer

        blockers_[container].emplace(&edge, BlockerType::Escape); // it may not be, but this is the safest
        // assumption. other passes can forward the original container and fold it into accesses
    }
}

void MemoryOwnershipAnalysis::use_as_dst_node(
    const std::string& container, const data_flow::AccessNode& node, const data_flow::Memlet& edge, const Block& block
) {
    if (edge.is_dst_write()) { // writes to the ptr
        auto& type = sdfg_.type(container);
        if (type.type_id() == types::TypeID::Pointer) {
            blockers_[container].emplace(&edge, BlockerType::Overwrite);
        }
    }
}

/**
 * Does not care about other types of accesses.
 * Presumes, that the data cannot alias and there is only one SSA-like instance of backing data.
 * So that indirect reads and writes can be matched up with each other.
 * Any read of the pointer or getting of an address is considered an escape for which aliasing cannot be excluded,
 * in which case you must not rely on this analysis
 */
class IndirectMemoryAccessFinder : public analysis::BaseUserVisitor {
private:
    std::unordered_map<std::string, std::unordered_set<const data_flow::Memlet*>> indirect_reads_;
    std::unordered_map<std::string, std::unordered_map<const data_flow::Memlet*, const Block*>> writes_to_remove_;
    const std::unordered_set<std::string>& target_containers_;

public:
    IndirectMemoryAccessFinder(const std::unordered_set<std::string>& target_containers);

    const std::unordered_map<std::string, std::unordered_set<const data_flow::Memlet*>>& indirect_reads() {
        return indirect_reads_;
    }
    const std::unordered_map<std::string, std::unordered_map<const data_flow::Memlet*, const Block*>>& writes_to_remove() {
        return writes_to_remove_;
    }

    void use_as_symbol_read(
        const std::string& container,
        const Element* user,
        SymbolReadLocation loc,
        int loc_index,
        symbolic::Expression expr
    ) override {}
    void use_as_symbol_write(const symbolic::Symbol& container, const Element* user, SymbolWriteLocation loc) override {
    }
    void use_as_src_node(
        const std::string& container,
        const data_flow::AccessNode& node,
        const data_flow::Memlet& edge,
        const Block& block
    ) override;
    void use_as_dst_node(
        const std::string& container,
        const data_flow::AccessNode& node,
        const data_flow::Memlet& edge,
        const Block& block
    ) override;
    void use_as_return_src(const std::string& container, const Return& ret) override {}
};

IndirectMemoryAccessFinder::IndirectMemoryAccessFinder(const std::unordered_set<std::string>& target_containers)
    : target_containers_(target_containers) {}

void IndirectMemoryAccessFinder::use_as_src_node(
    const std::string& container, const data_flow::AccessNode& node, const data_flow::Memlet& edge, const Block& block
) {
    if (target_containers_.contains(container)) {
        if (edge.is_src_pointed_to_read()) {
            indirect_reads_[container].insert(&edge);
        }
    }
}

void IndirectMemoryAccessFinder::use_as_dst_node(
    const std::string& container, const data_flow::AccessNode& node, const data_flow::Memlet& edge, const Block& block
) {
    if (target_containers_.contains(container)) {
        if (edge.is_dst_pointed_to_write()) {
            writes_to_remove_[container][&edge] = &block;
        }
    }
}


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

    auto& sdfg = builder.subject();

    // Check for locally allocated memory that we "own" and understand (no reference to it escapes or can potentially
    // alias)
    MemoryOwnershipAnalysis ownership_analysis(sdfg);
    ownership_analysis.run(analysis_manager);

    std::unordered_set<std::string> dead_containers;

    auto& fully_owned_areas = ownership_analysis.fully_owned_areas();
    if (!fully_owned_areas.empty()) {
        // We found pointered accesses, where we could prove that the pointer is unique and SSA-like, such that we may
        // check accesses via the pointer as well
        IndirectMemoryAccessFinder remaining_indirects(fully_owned_areas);
        remaining_indirects.dispatch(sdfg.root());
        for (auto& owned_area_id : fully_owned_areas) {
            auto& all_reads = remaining_indirects.indirect_reads();
            auto cont_reads_it = all_reads.find(owned_area_id);
            if (cont_reads_it == all_reads.end() || cont_reads_it->second.empty()) {
                DEBUG_PRINTLN("Removing fully owned memory " << owned_area_id << ", never used!");
                auto writes = remaining_indirects.writes_to_remove();
                // [owned_area] is never read, no reference to it escapes our control. So any write of it is useless
                auto writes_it = writes.find(owned_area_id);

                bool all_removed = true;
                if (writes_it != writes.end()) {
                    auto& to_remove = writes_it->second;
                    for (auto& [edge_to_remove, w_block] : to_remove) {
                        auto& write_node = dynamic_cast<const data_flow::AccessNode&>(edge_to_remove->dst());
                        int removed =
                            builder.clear_node(*const_cast<structured_control_flow::Block*>(w_block), write_node);
                        if (removed == 0) {
                            all_removed = false;
                        } else {
                            applied = true;
                        }
                    }
                }
                // This is the malloc. We can remove this because we understand what malloc does. Otherwise the
                // sideeffect flag would stop us from removing a libNode
                if (all_removed) {
                    auto& area = ownership_analysis.owned_area(owned_area_id);
                    area.remove_from(builder);
                    applied = true;
                }
            }
        }
    }
    if (applied) { // if changes were made, any cached analysis will be out of date.
        analysis_manager.invalidate_all();
    }

    // slightly expensive, because for fully_owned_areas we already looked for uses. But classified differently and did
    // not look at, whether the entire container can be removed
    auto& users = analysis_manager.get<analysis::Users>();
    auto& data_dependency_analysis = analysis_manager.get<analysis::DataDependencyAnalysis>();

    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) { // no reference of [name] anywhere
            dead_containers.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
            // more complex cases have been removed above already
        }

        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& block = dynamic_cast<structured_control_flow::Block&>(*graph.get_parent());

                    if (builder.clear_node(block, *access_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_containers.insert(name);
        }
    }

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

    return applied;
};

} // namespace passes
} // namespace sdfg

1	#include "sdfg/passes/dataflow/dead_data_elimination.h"
2
3	#include "sdfg/analysis/base_user_visitor.h"
4	#include "sdfg/analysis/data_dependency_analysis.h"
5	#include "sdfg/data_flow/library_nodes/stdlib/free.h"
6	#include "sdfg/data_flow/library_nodes/stdlib/malloc.h"
7	#include "sdfg/visitor/structured_sdfg_visitor.h"
8	#include "sdfg/visualizer/dot_visualizer.h"
9
10	namespace sdfg {
11	namespace passes {
12
13	DeadDataElimination::DeadDataElimination() : Pass(), permissive_(false) {};	57✔
14
15	DeadDataElimination::DeadDataElimination(bool permissive) : Pass(), permissive_(permissive) {};	×
16
17	std::string DeadDataElimination::name() { return "DeadDataElimination"; };	×
18
19	/**
20	* Finds memory areas (heap for now) that are wholly owned by the surrounding function. Owned memory can be removed if
21	* its no longer used, writes to it can be ellided if the data is never read. This is not true for memory writes in
22	* general, as you must prove no reference to that data ever escapes our control
23	*/
24	class MemoryOwnershipAnalysis : public analysis::BaseUserVisitor {
25	enum class BlockerType { Escape, Overwrite };
26
27	struct FreeCluster {
28	const Block* block;
29	const data_flow::Memlet* in;
30	const data_flow::Memlet* out;
31
32	FreeCluster(const Block* b, const data_flow::Memlet* i, const data_flow::Memlet* o) : block(b), in(i), out(o) {}	1✔
33	};
34
35	struct OwnedArea {
36	data_flow::Memlet* producer;
37	structured_control_flow::Block* producer_block;
38	symbolic::Expression allocation_size;
39	bool non_ssa = false;
40	std::vector<FreeCluster> free_clusters;
41
42	OwnedArea(data_flow::Memlet* p, structured_control_flow::Block* pb, symbolic::Expression as, bool ns)
43	: producer(p), producer_block(pb), allocation_size(std::move(as)), non_ssa(ns) {}	10✔
44
45	void remove_from(builder::StructuredSDFGBuilder& builder) const;
46	};
47
48	private:
49	StructuredSDFG& sdfg_;
50	// memory that is allocated by us and therefore 'owned' until it escapes
51	std::unordered_map<std::string, OwnedArea> originally_owned_data_;
52	std::unordered_map<std::string, std::unordered_map<const Element*, BlockerType>> blockers_;
53	std::unordered_set<std::string> fully_owned_; // never escaped
54
55	public:
56	MemoryOwnershipAnalysis(StructuredSDFG& sdfg);
57
58	void run(analysis::AnalysisManager& manager);
59
60	bool visit(sdfg::structured_control_flow::Block& node) override;
61
62	void use_as_symbol_write(const symbolic::Symbol& container, const Element* user, SymbolWriteLocation loc) override;
63	void use_as_symbol_read(
64	const std::string& container,
65	const Element* user,
66	SymbolReadLocation loc,
67	int loc_index,
68	symbolic::Expression expr
69	) override;
70	void use_as_src_node(
71	const std::string& container,
72	const data_flow::AccessNode& node,
73	const data_flow::Memlet& edge,
74	const Block& block
75	) override;
76	void use_as_dst_node(
77	const std::string& container,
78	const data_flow::AccessNode& node,
79	const data_flow::Memlet& edge,
80	const Block& block
81	) override;
82	void use_as_return_src(const std::string& container, const Return& ret) override;
83
84	const std::unordered_set<std::string>& fully_owned_areas() const { return fully_owned_; }	93✔
85
86	const OwnedArea& owned_area(const std::string& container) const { return originally_owned_data_.at(container); }	3✔
87
88	private:
89	static bool excusedEscape(const Element* element, const OwnedArea& area);
90	static bool excusedOverwrite(const Element* element, const OwnedArea& area);
91	};
92
93	void MemoryOwnershipAnalysis::OwnedArea::remove_from(builder::StructuredSDFGBuilder& builder) const {	3✔
94	auto& malloc_write = this->producer->dst();	3✔
95	auto& malloc_node = this->producer->src();	3✔
96	builder.clear_code_node_legacy(*this->producer_block, dynamic_cast<const data_flow::CodeNode&>(malloc_node));	3✔
97	// builder.clear_node(
98	// *this->producer_block, dynamic_cast<data_flow::AccessNode&>(malloc_write), {&malloc_write, &malloc_node}
99	// );
100
101	for (auto& free_cluster : this->free_clusters) {	3✔
102	auto& memlet = *free_cluster.out;	1✔
103	builder.clear_code_node_legacy(	1✔
104	const_cast<Block>(free_cluster.block), dynamic_cast<const data_flow::CodeNode&>(memlet.src())	1✔
105	);	1✔
106	// builder.clear_node(const_cast<Block>(free_cluster.block), memlet.dst(), {&memlet.dst(), &memlet.src()});
107	}	1✔
108	}	3✔
109
110	MemoryOwnershipAnalysis::MemoryOwnershipAnalysis(StructuredSDFG& sdfg) : sdfg_(sdfg) {}	93✔
111
112	bool MemoryOwnershipAnalysis::excusedEscape(const Element* element, const OwnedArea& area) {	7✔
113	// An escape is excused if it matches the input edge of one of the free_clusters.
114	// Reading the pointer to pass it to free() is not a real escape.
115	for (const auto& cluster : area.free_clusters) {	7✔
116	if (element == cluster.in) {	1✔
117	return true;	1✔
118	}	1✔
119	}	1✔
120	return false;	6✔
121	}	7✔
122
123	bool MemoryOwnershipAnalysis::excusedOverwrite(const Element* element, const OwnedArea& area) {	5✔
124	// The producer (malloc output edge) is an excused overwrite — it's the initial assignment.
125	if (element == area.producer) {	5✔
126	return true;	4✔
127	}	4✔
128	// The output edge of a free cluster is an excused overwrite — free sets the pointer
129	// to NULL (a fake overwrite that doesn't represent a meaningful reassignment).
130	for (const auto& cluster : area.free_clusters) {	1✔
131	if (element == cluster.out) {	1✔
132	return true;	1✔
133	}	1✔
134	}	1✔
135	return false;	×
136	}	1✔
137
138
139	void MemoryOwnershipAnalysis::run(analysis::AnalysisManager& manager) {	93✔
140	dispatch(sdfg_.root());	93✔
141
142	for (auto& [name, area] : originally_owned_data_) {	93✔
143	if (!area.non_ssa && area.allocation_size != SymEngine::null) {	10✔
144	auto it = blockers_.find(name);	10✔
145	if (it != blockers_.end()) {	10✔
146	bool killed = false;	10✔
147	for (auto& [element, type] : it->second) {	12✔
148	if (type == BlockerType::Escape) {	12✔
149	if (!excusedEscape(element, area)) {	7✔
150	killed = true;	6✔
151	break;	6✔
152	}	6✔
153	} else if (type == BlockerType::Overwrite) {	7✔
154	if (!excusedOverwrite(element, area)) {	5✔
155	killed = true;	×
156	break;	×
157	}	×
158	}	5✔
159	}	12✔
160	if (!killed) {	10✔
161	fully_owned_.insert(name);	4✔
162	}	4✔
163	} else {	10✔
164	fully_owned_.insert(name);	×
165	}	×
166	}	10✔
167	}	10✔
168	}	93✔
169
170
171	bool MemoryOwnershipAnalysis::visit(sdfg::structured_control_flow::Block& node) {	319✔
172	auto& dflow = node.dataflow();	319✔
173	for (auto& library_node : dflow.library_nodes()) {	319✔
174	if (library_node->code() == stdlib::LibraryNodeType_Malloc) {	19✔
175	auto* malloc_node = dynamic_cast<const stdlib::MallocNode*>(library_node);	10✔
176	auto& alloc_size = malloc_node->size();	10✔
177	auto output_conn = malloc_node->output(0);	10✔
178	auto oedges = dflow.out_edges(*malloc_node) \|	10✔
179	std::views::filter([&](const auto& e) { return e.src_conn() == output_conn; });	10✔
180	for (auto& oedge : oedges) {	10✔
181	auto* access_node = dynamic_cast<data_flow::AccessNode*>(&oedge.dst());	10✔
182	if (access_node && oedge.is_dst_write()) {	10✔
183	auto container = access_node->data();	10✔
184	auto it = originally_owned_data_.find(container);	10✔
185	if (it != originally_owned_data_.end()) {	10✔
186	auto& area = it->second;	×
187	area.non_ssa = true;	×
188	area.allocation_size = SymEngine::null;	×
189	area.producer_block = nullptr;	×
190	area.producer = nullptr;	×
191	// DEBUG_PRINTLN("Conflicting ownership of " << container);
192	continue;	×
193	}	×
194	originally_owned_data_.emplace(	10✔
195	std::piecewise_construct,	10✔
196	std::forward_as_tuple(container),	10✔
197	std::forward_as_tuple(&oedge, &node, alloc_size, false)	10✔
198	);	10✔
199	}	10✔
200	}	10✔
201	} else if (library_node->code() == stdlib::LibraryNodeType_Free) {	10✔
202	auto* free_node = dynamic_cast<const stdlib::FreeNode*>(library_node);	1✔
203	auto input = dflow.in_edge_for_connector(*free_node, free_node->input(0));	1✔
204	auto outputs = dflow.out_edges_for_connector(*free_node, free_node->output(0));	1✔
205	if (input && outputs.size() == 1) {	1✔
206	auto* in_access = dynamic_cast<const data_flow::AccessNode*>(&input->src());	1✔
207	auto* out_access = dynamic_cast<const data_flow::AccessNode*>(&outputs.at(0)->dst());	1✔
208
209	if (in_access && out_access && in_access->data() == out_access->data()) {	1✔
210	auto& container = in_access->data();	1✔
211	if (sdfg_.type(container).type_id() == types::TypeID::Pointer) {	1✔
212	auto area_it = originally_owned_data_.find(container);	1✔
213	if (area_it != originally_owned_data_.end()) { // we scan in execution order. Malloc needs to	1✔
214	// have been found before
215	auto& area = area_it->second;	1✔
216	area.free_clusters.emplace_back(&node, input, outputs[0]);	1✔
217	}	1✔
218	}	1✔
219	}	1✔
220	}	1✔
221	}	1✔
222	}	19✔
223
224	return BaseUserVisitor::visit(node);	319✔
225	}	319✔
226
227
228	void MemoryOwnershipAnalysis::use_as_return_src(const std::string& container, const Return& ret) {	8✔
229	if (sdfg_.type(container).type_id() == types::TypeID::Pointer) {	8✔
230	blockers_[container].emplace(&ret, BlockerType::Escape);	2✔
231	}	2✔
232	}	8✔
233
234	void MemoryOwnershipAnalysis::
235	use_as_symbol_write(const symbolic::Symbol& container, const Element* user, SymbolWriteLocation loc) {	261✔
236	auto name = container->get_name();	261✔
237	if (sdfg_.type(name).type_id() == types::TypeID::Pointer) {	261✔
238	blockers_[name].emplace(user, BlockerType::Overwrite);	1✔
239	}	1✔
240	}	261✔
241
242	void MemoryOwnershipAnalysis::use_as_symbol_read(
243	const std::string& container, const Element* user, SymbolReadLocation loc, int loc_index, symbolic::Expression expr
244	) {	1,740✔
245	auto& type = sdfg_.type(container);	1,740✔
246	if (type.type_id() == types::TypeID::Pointer) {	1,740✔
247	blockers_[container].emplace(user, BlockerType::Escape);	4✔
248	}	4✔
249	}	1,740✔
250
251	void MemoryOwnershipAnalysis::use_as_src_node(
252	const std::string& container, const data_flow::AccessNode& node, const data_flow::Memlet& edge, const Block& block
253	) {	527✔
254	auto& type = sdfg_.type(container);	527✔
255	if (edge.is_src_pointed_to_address_leak(type) \|\| edge.is_src_address_leak()) {	527✔
256	// pulls a reference to the owned memory area or can alias the entire pointer
257
258	blockers_[container].emplace(&edge, BlockerType::Escape); // it may not be, but this is the safest	27✔
259	// assumption. other passes can forward the original container and fold it into accesses
260	}	27✔
261	}	527✔
262
263	void MemoryOwnershipAnalysis::use_as_dst_node(
264	const std::string& container, const data_flow::AccessNode& node, const data_flow::Memlet& edge, const Block& block
265	) {	307✔
266	if (edge.is_dst_write()) { // writes to the ptr	307✔
267	auto& type = sdfg_.type(container);	196✔
268	if (type.type_id() == types::TypeID::Pointer) {	196✔
269	blockers_[container].emplace(&edge, BlockerType::Overwrite);	14✔
270	}	14✔
271	}	196✔
272	}	307✔
273
274	/**
275	* Does not care about other types of accesses.
276	* Presumes, that the data cannot alias and there is only one SSA-like instance of backing data.
277	* So that indirect reads and writes can be matched up with each other.
278	* Any read of the pointer or getting of an address is considered an escape for which aliasing cannot be excluded,
279	* in which case you must not rely on this analysis
280	*/
281	class IndirectMemoryAccessFinder : public analysis::BaseUserVisitor {
282	private:
283	std::unordered_map<std::string, std::unordered_set<const data_flow::Memlet*>> indirect_reads_;
284	std::unordered_map<std::string, std::unordered_map<const data_flow::Memlet, const Block>> writes_to_remove_;
285	const std::unordered_set<std::string>& target_containers_;
286
287	public:
288	IndirectMemoryAccessFinder(const std::unordered_set<std::string>& target_containers);
289
290	const std::unordered_map<std::string, std::unordered_set<const data_flow::Memlet*>>& indirect_reads() {	4✔
291	return indirect_reads_;	4✔
292	}	4✔
293	const std::unordered_map<std::string, std::unordered_map<const data_flow::Memlet, const Block>>& writes_to_remove() {	3✔
294	return writes_to_remove_;	3✔
295	}	3✔
296
297	void use_as_symbol_read(
298	const std::string& container,
299	const Element* user,
300	SymbolReadLocation loc,
301	int loc_index,
302	symbolic::Expression expr
303	) override {}	24✔
304	void use_as_symbol_write(const symbolic::Symbol& container, const Element* user, SymbolWriteLocation loc) override {	4✔
305	}	4✔
306	void use_as_src_node(
307	const std::string& container,
308	const data_flow::AccessNode& node,
309	const data_flow::Memlet& edge,
310	const Block& block
311	) override;
312	void use_as_dst_node(
313	const std::string& container,
314	const data_flow::AccessNode& node,
315	const data_flow::Memlet& edge,
316	const Block& block
317	) override;
318	void use_as_return_src(const std::string& container, const Return& ret) override {}	1✔
319	};
320
321	IndirectMemoryAccessFinder::IndirectMemoryAccessFinder(const std::unordered_set<std::string>& target_containers)
322	: target_containers_(target_containers) {}	4✔
323
324	void IndirectMemoryAccessFinder::use_as_src_node(
325	const std::string& container, const data_flow::AccessNode& node, const data_flow::Memlet& edge, const Block& block
326	) {	10✔
327	if (target_containers_.contains(container)) {	10✔
328	if (edge.is_src_pointed_to_read()) {	2✔
329	indirect_reads_[container].insert(&edge);	1✔
330	}	1✔
331	}	2✔
332	}	10✔
333
334	void IndirectMemoryAccessFinder::use_as_dst_node(
335	const std::string& container, const data_flow::AccessNode& node, const data_flow::Memlet& edge, const Block& block
336	) {	14✔
337	if (target_containers_.contains(container)) {	14✔
338	if (edge.is_dst_pointed_to_write()) {	9✔
339	writes_to_remove_[container][&edge] = &block;	4✔
340	}	4✔
341	}	9✔
342	}	14✔
343
344
345	bool DeadDataElimination::run_pass(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	93✔
346	bool applied = false;	93✔
347
348	auto& sdfg = builder.subject();	93✔
349
350	// Check for locally allocated memory that we "own" and understand (no reference to it escapes or can potentially
351	// alias)
352	MemoryOwnershipAnalysis ownership_analysis(sdfg);	93✔
353	ownership_analysis.run(analysis_manager);	93✔
354
355	std::unordered_set<std::string> dead_containers;	93✔
356
357	auto& fully_owned_areas = ownership_analysis.fully_owned_areas();	93✔
358	if (!fully_owned_areas.empty()) {	93✔
359	// We found pointered accesses, where we could prove that the pointer is unique and SSA-like, such that we may
360	// check accesses via the pointer as well
361	IndirectMemoryAccessFinder remaining_indirects(fully_owned_areas);	4✔
362	remaining_indirects.dispatch(sdfg.root());	4✔
363	for (auto& owned_area_id : fully_owned_areas) {	4✔
364	auto& all_reads = remaining_indirects.indirect_reads();	4✔
365	auto cont_reads_it = all_reads.find(owned_area_id);	4✔
366	if (cont_reads_it == all_reads.end() \|\| cont_reads_it->second.empty()) {	4✔
367	DEBUG_PRINTLN("Removing fully owned memory " << owned_area_id << ", never used!");	3✔
368	auto writes = remaining_indirects.writes_to_remove();	3✔
369	// [owned_area] is never read, no reference to it escapes our control. So any write of it is useless
370	auto writes_it = writes.find(owned_area_id);	3✔
371
372	bool all_removed = true;	3✔
373	if (writes_it != writes.end()) {	3✔
374	auto& to_remove = writes_it->second;	3✔
375	for (auto& [edge_to_remove, w_block] : to_remove) {	3✔
376	auto& write_node = dynamic_cast<const data_flow::AccessNode&>(edge_to_remove->dst());	3✔
377	int removed =	3✔
378	builder.clear_node(const_cast<structured_control_flow::Block>(w_block), write_node);	3✔
379	if (removed == 0) {	3✔
NEW 380	all_removed = false;	×
381	} else {	3✔
382	applied = true;	3✔
383	}	3✔
384	}	3✔
385	}	3✔
386	// This is the malloc. We can remove this because we understand what malloc does. Otherwise the
387	// sideeffect flag would stop us from removing a libNode
388	if (all_removed) {	3✔
389	auto& area = ownership_analysis.owned_area(owned_area_id);	3✔
390	area.remove_from(builder);	3✔
391	applied = true;	3✔
392	}	3✔
393	}	3✔
394	}	4✔
395	}	4✔
396	if (applied) { // if changes were made, any cached analysis will be out of date.	93✔
397	analysis_manager.invalidate_all();	3✔
398	}	3✔
399
400	// slightly expensive, because for fully_owned_areas we already looked for uses. But classified differently and did
401	// not look at, whether the entire container can be removed
402	auto& users = analysis_manager.get<analysis::Users>();	93✔
403	auto& data_dependency_analysis = analysis_manager.get<analysis::DataDependencyAnalysis>();	93✔
404
405	for (auto& name : sdfg.containers()) {	784✔
406	if (!sdfg.is_transient(name)) {	784✔
407	continue;	405✔
408	}	405✔
409	if (users.num_views(name) > 0 \|\| users.num_moves(name) > 0) {	379✔
410	continue;	3✔
411	}	3✔
412	auto num_reads = users.num_reads(name);	376✔
413	if (!num_reads && users.num_writes(name) == 0) { // no reference of [name] anywhere	376✔
414	dead_containers.insert(name);	12✔
415	applied = true;	12✔
416	continue;	12✔
417	}	12✔
418
419	if (sdfg.type(name).type_id() == types::TypeID::Pointer) {	364✔
420	continue;	7✔
421	// use analysis does not return actual reads and writes for pointers. So if [name] is a pointer,
422	// num reads/writes, does not actually mean no reads exist and any removal is problematic
423	// more complex cases have been removed above already
424	}	7✔
425
426	bool completely_unused = !num_reads; // if there are reads left, we can never remove the container, but maybe	357✔
427	// some writes
428	auto raws = data_dependency_analysis.definitions(name);	357✔
429	for (auto set : raws) {	646✔
430	bool no_reads = false;	646✔
431	if (set.second.size() == 0) {	646✔
432	no_reads = true;	13✔
433	}	13✔
434	if (data_dependency_analysis.is_undefined_user(*set.first)) {	646✔
435	continue;	1✔
436	}	1✔
437
438	if (no_reads) {	645✔
439	bool could_eliminate_write = false;	13✔
440	auto write = set.first;	13✔
441	if (auto transition = dynamic_cast<structured_control_flow::Transition*>(write->element())) {	13✔
442	transition->assignments().erase(symbolic::symbol(name));	11✔
443	applied = true;	11✔
444	could_eliminate_write = true;	11✔
445	} else if (auto access_node = dynamic_cast<data_flow::AccessNode*>(write->element())) {	11✔
446	auto& graph = access_node->get_parent();	2✔
447	auto& block = dynamic_cast<structured_control_flow::Block&>(*graph.get_parent());	2✔
448
449	if (builder.clear_node(block, *access_node)) {	2✔
450	applied = true;	1✔
451	could_eliminate_write = true;	1✔
452	}	1✔
453	}	2✔
454
455	completely_unused &= could_eliminate_write;	13✔
456	}	13✔
457	}	645✔
458
459	if (completely_unused) { // no reads, and all remaining writes could be removed	357✔
460	dead_containers.insert(name);	6✔
461	}	6✔
462	}	357✔
463
464	for (auto& name : dead_containers) {	93✔
465	builder.remove_container(name);	18✔
466	}	18✔
467
468	return applied;	93✔
469	};	93✔
470
471	} // namespace passes
472	} // namespace sdfg

daisytuner / docc / 23659726771

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