22298043375

Committed 23 Feb 2026 08:19AM UTC coverage: 64.63% (-0.1%) from 64.743%

Build # 22298043375

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #537 from daisytuner/map-optimizations

Adds memory management to frontend

Run Details

48 of 51 new or added lines in 4 files covered. (94.12%)

62 existing lines in 4 files now uncovered.

23672 of 36627 relevant lines covered (64.63%)

357.5 hits per line

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

63.51

/sdfg/src/analysis/escape_analysis.cpp

#include "sdfg/analysis/escape_analysis.h"

#include <unordered_set>

#include "sdfg/analysis/scope_analysis.h"
#include "sdfg/analysis/users.h"
#include "sdfg/data_flow/library_nodes/stdlib/malloc.h"
#include "sdfg/structured_control_flow/block.h"
#include "sdfg/structured_control_flow/for.h"
#include "sdfg/structured_control_flow/map.h"
#include "sdfg/structured_control_flow/return.h"
#include "sdfg/structured_control_flow/sequence.h"
#include "sdfg/structured_control_flow/structured_loop.h"
#include "sdfg/structured_control_flow/while.h"
#include "sdfg/visitor/structured_sdfg_visitor.h"

namespace sdfg {
namespace analysis {

namespace {

bool is_loop(structured_control_flow::ControlFlowNode* node) {
    return dynamic_cast<structured_control_flow::StructuredLoop*>(node) != nullptr ||
           dynamic_cast<structured_control_flow::While*>(node) != nullptr;
}

structured_control_flow::ControlFlowNode*
find_containing_loop(structured_control_flow::Block* block, ScopeAnalysis& scope_analysis) {
    auto ancestors = scope_analysis.ancestor_scopes(block);
    for (auto* ancestor : ancestors) {
        if (is_loop(ancestor)) {
            return ancestor;
        }
    }
    return nullptr;
}

class MallocFinder : public visitor::ActualStructuredSDFGVisitor {
public:
    std::unordered_map<std::string, stdlib::MallocNode*> malloc_containers;
    std::unordered_map<std::string, structured_control_flow::Block*> malloc_blocks;

    bool visit(structured_control_flow::Block& block) override {
        auto& dataflow = block.dataflow();
        for (auto* lib_node : dataflow.library_nodes()) {
            if (lib_node->code() == stdlib::LibraryNodeType_Malloc) {
                auto* malloc_node = dynamic_cast<stdlib::MallocNode*>(lib_node);
                if (malloc_node) {
                    // Find the output access node to get the container name
                    for (auto& oedge : dataflow.out_edges(*malloc_node)) {
                        if (auto* access = dynamic_cast<data_flow::AccessNode*>(&oedge.dst())) {
                            malloc_containers[access->data()] = malloc_node;
                            malloc_blocks[access->data()] = &block;
                        }
                    }
                }
            }
        }
        return true;
    }
};

class ReturnEscapeChecker : public visitor::ActualStructuredSDFGVisitor {
public:
    std::unordered_set<std::string> returned_containers;

    bool visit(structured_control_flow::Return& ret) override {
        if (ret.is_data()) {
            returned_containers.insert(ret.data());
        }
        return true;
    }
};

} // anonymous namespace

EscapeAnalysis::EscapeAnalysis(StructuredSDFG& sdfg) : Analysis(sdfg) {}

void EscapeAnalysis::run(analysis::AnalysisManager& analysis_manager) {
    auto& sdfg = this->sdfg_;
    auto& users = analysis_manager.get<Users>();
    auto& scope_analysis = analysis_manager.get<ScopeAnalysis>();

    // Step 1: Find all malloc allocations
    MallocFinder malloc_finder;
    malloc_finder.dispatch(sdfg.root());

    for (auto& [container, malloc_node] : malloc_finder.malloc_containers) {
        malloc_containers_.insert(container);
    }
    for (auto& [container, block] : malloc_finder.malloc_blocks) {
        malloc_blocks_[container] = block;
    }

    // Step 2: Find all containers that escape through return
    ReturnEscapeChecker return_checker;
    return_checker.dispatch(sdfg.root());

    // Step 3: For each malloc allocation, determine if it escapes
    for (const auto& container : malloc_containers_) {
        bool container_escapes = false;

        // Check 1: Returned from function
        if (return_checker.returned_containers.count(container) > 0) {
            container_escapes = true;
        }

        // Check 2: Stored into a non-transient (argument/global) container
        // This happens when the pointer is VIEWed or MOVEd into another container
        if (!container_escapes) {
            auto views = users.views(container);
            for (auto* view : views) {
                container_escapes = true;
                break;
            }
        }

        // Check 3: If the container is not transient, it's an argument and escapes
        if (!container_escapes && !sdfg.is_transient(container)) {
            container_escapes = true;
        }

        escapes_[container] = container_escapes;

        // Step 4: For non-escaping allocations, find the last use
        if (!container_escapes) {
            auto* malloc_block = malloc_blocks_[container];
            auto* containing_loop = find_containing_loop(malloc_block, scope_analysis);

            User* last = nullptr;

            if (containing_loop) {
                // Malloc is inside a loop - use UsersView to find last use within the loop body
                UsersView loop_users(users, *containing_loop);
                auto loop_uses = loop_users.uses(container);

                // Find the last use within this loop iteration
                for (auto* use : loop_uses) {
                    auto uses_after = loop_users.all_uses_after(*use);
                    bool is_last = true;
                    for (auto* after : uses_after) {
                        if (after->container() == container) {
                            is_last = false;
                            break;
                        }
                    }
                    if (is_last) {
                        last = use;
                        break;
                    }
                }
            } else {
                // Malloc is not inside a loop - check if uses are inside loops
                auto all_uses = users.uses(container);

                // Find the outermost loop containing any use (to determine proper last use)
                structured_control_flow::ControlFlowNode* outermost_use_loop = nullptr;
                for (auto* use : all_uses) {
                    auto* use_element = use->element();
                    structured_control_flow::Block* use_block = nullptr;
                    if (auto* access = dynamic_cast<data_flow::AccessNode*>(use_element)) {
                        use_block = dynamic_cast<structured_control_flow::Block*>(access->get_parent().get_parent());
                    } else if (auto* lib = dynamic_cast<data_flow::LibraryNode*>(use_element)) {
                        use_block = dynamic_cast<structured_control_flow::Block*>(lib->get_parent().get_parent());
                    }
                    if (use_block) {
                        auto* use_loop = find_containing_loop(use_block, scope_analysis);
                        if (use_loop && !outermost_use_loop) {
                            outermost_use_loop = use_loop;
                        }
                    }
                }

                if (outermost_use_loop) {
                    // Look for uses after the loop
                    for (auto* use : all_uses) {
                        auto* use_element = use->element();
                        structured_control_flow::Block* use_block = nullptr;
                        if (auto* access = dynamic_cast<data_flow::AccessNode*>(use_element)) {
                            use_block = dynamic_cast<structured_control_flow::Block*>(access->get_parent().get_parent()
                            );
                        } else if (auto* lib = dynamic_cast<data_flow::LibraryNode*>(use_element)) {
                            use_block = dynamic_cast<structured_control_flow::Block*>(lib->get_parent().get_parent());
                        }
                        if (use_block) {
                            auto* use_loop = find_containing_loop(use_block, scope_analysis);
                            // If this use is not inside the loop, it could be the last use
                            if (!use_loop) {
                                auto uses_after = users.all_uses_after(*use);
                                bool is_last = true;
                                for (auto* after : uses_after) {
                                    if (after->container() == container) {
                                        // Check if 'after' is also outside the loop
                                        auto* after_element = after->element();
                                        structured_control_flow::Block* after_block = nullptr;
                                        if (auto* acc = dynamic_cast<data_flow::AccessNode*>(after_element)) {
                                            after_block =
                                                dynamic_cast<structured_control_flow::Block*>(acc->get_parent()
                                                                                                  .get_parent());
                                        } else if (auto* lib = dynamic_cast<data_flow::LibraryNode*>(after_element)) {
                                            after_block =
                                                dynamic_cast<structured_control_flow::Block*>(lib->get_parent()
                                                                                                  .get_parent());
                                        }
                                        if (after_block) {
                                            auto* after_loop = find_containing_loop(after_block, scope_analysis);
                                            if (!after_loop) {
                                                is_last = false;
                                                break;
                                            }
                                        }
                                    }
                                }
                                if (is_last) {
                                    last = use;
                                    break;
                                }
                            }
                        }
                    }

                    if (!last) {
                        UsersView loop_users(users, *outermost_use_loop);
                        auto loop_uses = loop_users.uses(container);
                        for (auto* use : loop_uses) {
                            auto uses_after = loop_users.all_uses_after(*use);
                            bool is_last = true;
                            for (auto* after : uses_after) {
                                if (after->container() == container) {
                                    is_last = false;
                                    break;
                                }
                            }
                            if (is_last) {
                                last = use;
                                break;
                            }
                        }
                    }
                } else {
                    // No loops involved - simple case
                    for (auto* use : all_uses) {
                        auto uses_after = users.all_uses_after(*use);
                        bool is_last = true;
                        for (auto* after : uses_after) {
                            if (after->container() == container) {
                                is_last = false;
                                break;
                            }
                        }
                        if (is_last) {
                            last = use;
                            break;
                        }
                    }
                }
            }

            last_uses_[container] = last;
        }
    }
}

bool EscapeAnalysis::is_malloc_allocation(const std::string& container) const {
    return malloc_containers_.count(container) > 0;
}

bool EscapeAnalysis::escapes(const std::string& container) const {
    auto it = escapes_.find(container);
    if (it == escapes_.end()) {
        return false; // Not a malloc allocation
    }
    return it->second;
}

User* EscapeAnalysis::last_use(const std::string& container) const {
    auto it = last_uses_.find(container);
    if (it == last_uses_.end()) {
        return nullptr;
    }
    return it->second;
}

structured_control_flow::Block* EscapeAnalysis::malloc_block(const std::string& container) const {
    auto it = malloc_blocks_.find(container);
    if (it == malloc_blocks_.end()) {
        return nullptr;
    }
    return it->second;
}

std::unordered_set<std::string> EscapeAnalysis::non_escaping_allocations() const {
    std::unordered_set<std::string> result;
    for (const auto& container : malloc_containers_) {
        if (!escapes(container)) {
            result.insert(container);
        }
    }
    return result;
}

} // namespace analysis
} // namespace sdfg

1	#include "sdfg/analysis/escape_analysis.h"
2
3	#include <unordered_set>
4
5	#include "sdfg/analysis/scope_analysis.h"
6	#include "sdfg/analysis/users.h"
7	#include "sdfg/data_flow/library_nodes/stdlib/malloc.h"
8	#include "sdfg/structured_control_flow/block.h"
9	#include "sdfg/structured_control_flow/for.h"
10	#include "sdfg/structured_control_flow/map.h"
11	#include "sdfg/structured_control_flow/return.h"
12	#include "sdfg/structured_control_flow/sequence.h"
13	#include "sdfg/structured_control_flow/structured_loop.h"
14	#include "sdfg/structured_control_flow/while.h"
15	#include "sdfg/visitor/structured_sdfg_visitor.h"
16
17	namespace sdfg {
18	namespace analysis {
19
20	namespace {
21
22	bool is_loop(structured_control_flow::ControlFlowNode* node) {	19✔
23	return dynamic_cast<structured_control_flow::StructuredLoop*>(node) != nullptr \|\|	19✔
24	dynamic_cast<structured_control_flow::While*>(node) != nullptr;	19✔
25	}	19✔
26
27	structured_control_flow::ControlFlowNode*
28	find_containing_loop(structured_control_flow::Block* block, ScopeAnalysis& scope_analysis) {	18✔
29	auto ancestors = scope_analysis.ancestor_scopes(block);	18✔
30	for (auto* ancestor : ancestors) {	19✔
31	if (is_loop(ancestor)) {	19✔
32	return ancestor;	1✔
33	}	1✔
34	}	19✔
35	return nullptr;	17✔
36	}	18✔
37
38	class MallocFinder : public visitor::ActualStructuredSDFGVisitor {
39	public:
40	std::unordered_map<std::string, stdlib::MallocNode*> malloc_containers;
41	std::unordered_map<std::string, structured_control_flow::Block*> malloc_blocks;
42
43	bool visit(structured_control_flow::Block& block) override {	15✔
44	auto& dataflow = block.dataflow();	15✔
45	for (auto* lib_node : dataflow.library_nodes()) {	15✔
46	if (lib_node->code() == stdlib::LibraryNodeType_Malloc) {	11✔
47	auto* malloc_node = dynamic_cast<stdlib::MallocNode*>(lib_node);	11✔
48	if (malloc_node) {	11✔
49	// Find the output access node to get the container name
50	for (auto& oedge : dataflow.out_edges(*malloc_node)) {	11✔
51	if (auto* access = dynamic_cast<data_flow::AccessNode*>(&oedge.dst())) {	11✔
52	malloc_containers[access->data()] = malloc_node;	11✔
53	malloc_blocks[access->data()] = &block;	11✔
54	}	11✔
55	}	11✔
56	}	11✔
57	}	11✔
58	}	11✔
59	return true;	15✔
60	}	15✔
61	};
62
63	class ReturnEscapeChecker : public visitor::ActualStructuredSDFGVisitor {
64	public:
65	std::unordered_set<std::string> returned_containers;
66
67	bool visit(structured_control_flow::Return& ret) override {	2✔
68	if (ret.is_data()) {	2✔
69	returned_containers.insert(ret.data());	2✔
70	}	2✔
71	return true;	2✔
72	}	2✔
73	};
74
75	} // anonymous namespace
76
77	EscapeAnalysis::EscapeAnalysis(StructuredSDFG& sdfg) : Analysis(sdfg) {}	12✔
78
79	void EscapeAnalysis::run(analysis::AnalysisManager& analysis_manager) {	12✔
80	auto& sdfg = this->sdfg_;	12✔
81	auto& users = analysis_manager.get<Users>();	12✔
82	auto& scope_analysis = analysis_manager.get<ScopeAnalysis>();	12✔
83
84	// Step 1: Find all malloc allocations
85	MallocFinder malloc_finder;	12✔
86	malloc_finder.dispatch(sdfg.root());	12✔
87
88	for (auto& [container, malloc_node] : malloc_finder.malloc_containers) {	12✔
89	malloc_containers_.insert(container);	11✔
90	}	11✔
91	for (auto& [container, block] : malloc_finder.malloc_blocks) {	12✔
92	malloc_blocks_[container] = block;	11✔
93	}	11✔
94
95	// Step 2: Find all containers that escape through return
96	ReturnEscapeChecker return_checker;	12✔
97	return_checker.dispatch(sdfg.root());	12✔
98
99	// Step 3: For each malloc allocation, determine if it escapes
100	for (const auto& container : malloc_containers_) {	12✔
101	bool container_escapes = false;	11✔
102
103	// Check 1: Returned from function
104	if (return_checker.returned_containers.count(container) > 0) {	11✔
105	container_escapes = true;	2✔
106	}	2✔
107
108	// Check 2: Stored into a non-transient (argument/global) container
109	// This happens when the pointer is VIEWed or MOVEd into another container
110	if (!container_escapes) {	11✔
111	auto views = users.views(container);	9✔
112	for (auto* view : views) {	9✔
113	container_escapes = true;	×
114	break;	×
115	}	×
116	}	9✔
117
118	// Check 3: If the container is not transient, it's an argument and escapes
119	if (!container_escapes && !sdfg.is_transient(container)) {	11✔
120	container_escapes = true;	2✔
121	}	2✔
122
123	escapes_[container] = container_escapes;	11✔
124
125	// Step 4: For non-escaping allocations, find the last use
126	if (!container_escapes) {	11✔
127	auto* malloc_block = malloc_blocks_[container];	7✔
128	auto* containing_loop = find_containing_loop(malloc_block, scope_analysis);	7✔
129
130	User* last = nullptr;	7✔
131
132	if (containing_loop) {	7✔
133	// Malloc is inside a loop - use UsersView to find last use within the loop body
134	UsersView loop_users(users, *containing_loop);	1✔
135	auto loop_uses = loop_users.uses(container);	1✔
136
137	// Find the last use within this loop iteration
138	for (auto* use : loop_uses) {	1✔
139	auto uses_after = loop_users.all_uses_after(*use);	1✔
140	bool is_last = true;	1✔
141	for (auto* after : uses_after) {	2✔
142	if (after->container() == container) {	2✔
UNCOV 143	is_last = false;	×
UNCOV 144	break;	×
UNCOV 145	}	×
146	}	2✔
147	if (is_last) {	1✔
148	last = use;	1✔
149	break;	1✔
150	}	1✔
151	}	1✔
152	} else {	6✔
153	// Malloc is not inside a loop - check if uses are inside loops
154	auto all_uses = users.uses(container);	6✔
155
156	// Find the outermost loop containing any use (to determine proper last use)
157	structured_control_flow::ControlFlowNode* outermost_use_loop = nullptr;	6✔
158	for (auto* use : all_uses) {	11✔
159	auto* use_element = use->element();	11✔
160	structured_control_flow::Block* use_block = nullptr;	11✔
161	if (auto* access = dynamic_cast<data_flow::AccessNode*>(use_element)) {	11✔
162	use_block = dynamic_cast<structured_control_flow::Block*>(access->get_parent().get_parent());	11✔
163	} else if (auto* lib = dynamic_cast<data_flow::LibraryNode*>(use_element)) {	11✔
164	use_block = dynamic_cast<structured_control_flow::Block*>(lib->get_parent().get_parent());	×
165	}	×
166	if (use_block) {	11✔
167	auto* use_loop = find_containing_loop(use_block, scope_analysis);	11✔
168	if (use_loop && !outermost_use_loop) {	11✔
UNCOV 169	outermost_use_loop = use_loop;	×
UNCOV 170	}	×
171	}	11✔
172	}	11✔
173
174	if (outermost_use_loop) {	6✔
175	// Look for uses after the loop
UNCOV 176	for (auto* use : all_uses) {	×
UNCOV 177	auto* use_element = use->element();	×
UNCOV 178	structured_control_flow::Block* use_block = nullptr;	×
UNCOV 179	if (auto* access = dynamic_cast<data_flow::AccessNode*>(use_element)) {	×
UNCOV 180	use_block = dynamic_cast<structured_control_flow::Block*>(access->get_parent().get_parent()	×
UNCOV 181	);	×
UNCOV 182	} else if (auto* lib = dynamic_cast<data_flow::LibraryNode*>(use_element)) {	×
183	use_block = dynamic_cast<structured_control_flow::Block*>(lib->get_parent().get_parent());	×
184	}	×
UNCOV 185	if (use_block) {	×
UNCOV 186	auto* use_loop = find_containing_loop(use_block, scope_analysis);	×
187	// If this use is not inside the loop, it could be the last use
UNCOV 188	if (!use_loop) {	×
UNCOV 189	auto uses_after = users.all_uses_after(*use);	×
UNCOV 190	bool is_last = true;	×
UNCOV 191	for (auto* after : uses_after) {	×
UNCOV 192	if (after->container() == container) {	×
193	// Check if 'after' is also outside the loop
UNCOV 194	auto* after_element = after->element();	×
UNCOV 195	structured_control_flow::Block* after_block = nullptr;	×
UNCOV 196	if (auto* acc = dynamic_cast<data_flow::AccessNode*>(after_element)) {	×
UNCOV 197	after_block =	×
UNCOV 198	dynamic_cast<structured_control_flow::Block*>(acc->get_parent()	×
UNCOV 199	.get_parent());	×
UNCOV 200	} else if (auto* lib = dynamic_cast<data_flow::LibraryNode*>(after_element)) {	×
201	after_block =	×
202	dynamic_cast<structured_control_flow::Block*>(lib->get_parent()	×
203	.get_parent());	×
204	}	×
UNCOV 205	if (after_block) {	×
UNCOV 206	auto* after_loop = find_containing_loop(after_block, scope_analysis);	×
UNCOV 207	if (!after_loop) {	×
208	is_last = false;	×
209	break;	×
210	}	×
UNCOV 211	}	×
UNCOV 212	}	×
UNCOV 213	}	×
UNCOV 214	if (is_last) {	×
UNCOV 215	last = use;	×
UNCOV 216	break;	×
UNCOV 217	}	×
UNCOV 218	}	×
UNCOV 219	}	×
UNCOV 220	}	×
221
UNCOV 222	if (!last) {	×
223	UsersView loop_users(users, *outermost_use_loop);	×
224	auto loop_uses = loop_users.uses(container);	×
225	for (auto* use : loop_uses) {	×
226	auto uses_after = loop_users.all_uses_after(*use);	×
227	bool is_last = true;	×
228	for (auto* after : uses_after) {	×
229	if (after->container() == container) {	×
230	is_last = false;	×
231	break;	×
232	}	×
233	}	×
234	if (is_last) {	×
235	last = use;	×
236	break;	×
237	}	×
238	}	×
239	}	×
240	} else {	6✔
241	// No loops involved - simple case
242	for (auto* use : all_uses) {	6✔
243	auto uses_after = users.all_uses_after(*use);	6✔
244	bool is_last = true;	6✔
245	for (auto* after : uses_after) {	6✔
246	if (after->container() == container) {	4✔
UNCOV 247	is_last = false;	×
UNCOV 248	break;	×
UNCOV 249	}	×
250	}	4✔
251	if (is_last) {	6✔
252	last = use;	6✔
253	break;	6✔
254	}	6✔
255	}	6✔
256	}	6✔
257	}	6✔
258
259	last_uses_[container] = last;	7✔
260	}	7✔
261	}	11✔
262	}	12✔
263
264	bool EscapeAnalysis::is_malloc_allocation(const std::string& container) const {	10✔
265	return malloc_containers_.count(container) > 0;	10✔
266	}	10✔
267
268	bool EscapeAnalysis::escapes(const std::string& container) const {	18✔
269	auto it = escapes_.find(container);	18✔
270	if (it == escapes_.end()) {	18✔
271	return false; // Not a malloc allocation	3✔
272	}	3✔
273	return it->second;	15✔
274	}	18✔
275
276	User* EscapeAnalysis::last_use(const std::string& container) const {	4✔
277	auto it = last_uses_.find(container);	4✔
278	if (it == last_uses_.end()) {	4✔
279	return nullptr;	2✔
280	}	2✔
281	return it->second;	2✔
282	}	4✔
283
UNCOV 284	structured_control_flow::Block* EscapeAnalysis::malloc_block(const std::string& container) const {	×
UNCOV 285	auto it = malloc_blocks_.find(container);	×
UNCOV 286	if (it == malloc_blocks_.end()) {	×
287	return nullptr;	×
288	}	×
UNCOV 289	return it->second;	×
UNCOV 290	}	×
291
292	std::unordered_set<std::string> EscapeAnalysis::non_escaping_allocations() const {	4✔
293	std::unordered_set<std::string> result;	4✔
294	for (const auto& container : malloc_containers_) {	5✔
295	if (!escapes(container)) {	5✔
296	result.insert(container);	3✔
297	}	3✔
298	}	5✔
299	return result;	4✔
300	}	4✔
301
302	} // namespace analysis
303	} // namespace sdfg

daisytuner / docc / 22298043375

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