23290386671

Committed 19 Mar 2026 10:23AM UTC coverage: 63.42% (-0.4%) from 63.839%

Build # 23290386671

Build Type

Pull #600

github

Committed by

web-flow

Commit Message

Merge a96768fad into 5fb101d73

Pull Request Pull Request #600: moves transformations from sdfg to opt

Coverage Stats

17 of 53 new or added lines in 1 file covered. (32.08%)

4 existing lines in 3 files now uncovered.

26084 of 41129 relevant lines covered (63.42%)

399.2 hits per line

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

93.85

/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;
    };

    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;
        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_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_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;
                        std::cerr << "Conflicting ownership of " << container << std::endl;
                        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);
                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());
                        builder.clear_node(*const_cast<structured_control_flow::Block*>(w_block), write_node);
                    }
                }
                // 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
                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());

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

daisytuner / docc / 23290386671

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