21495396714

Committed 29 Jan 2026 09:29PM UTC coverage: 66.564% (+0.3%) from 66.308%

Build # 21495396714

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #487 from daisytuner/python-openmp

improves auto-parallelization for npbench kernels

Run Details

288 of 371 new or added lines in 6 files covered. (77.63%)

1 existing line in 1 file now uncovered.

23049 of 34627 relevant lines covered (66.56%)

381.69 hits per line

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

85.14

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

daisytuner / sdfglib / 21495396714

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