28369888556

Committed 29 Jun 2026 11:50AM UTC coverage: 61.756% (+0.002%) from 61.754%

Build # 28369888556

Build Type

Pull #816

github

Committed by

web-flow

Commit Message

Merge cc77a73a1 into 8322f5994

Pull Request Pull Request #816: Remove all mentions of ScopeAnalysis, now that it is no longer needed

Coverage Stats

3 of 3 new or added lines in 1 file covered. (100.0%)

3 existing lines in 1 file now uncovered.

38818 of 62857 relevant lines covered (61.76%)

978.81 hits per line

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

63.68

/sdfg/src/analysis/escape_analysis.cpp

#include "sdfg/analysis/escape_analysis.h"

#include <unordered_set>

#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) {
    auto ancestor = block->get_parent();
    while (ancestor) {
        if (is_loop(ancestor)) {
            return ancestor;
        } else {
            ancestor = ancestor->get_parent();
        }
    }
    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>();

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

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

daisytuner / docc / 28369888556

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