21504454773

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

Build # 21504454773

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.

23051 of 34627 relevant lines covered (66.57%)

381.71 hits per line

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

59.32

/sdfg/src/passes/memory/insert_frees.cpp

#include "sdfg/passes/memory/insert_frees.h"

#include "sdfg/analysis/escape_analysis.h"
#include "sdfg/analysis/scope_analysis.h"
#include "sdfg/analysis/users.h"
#include "sdfg/data_flow/library_nodes/stdlib/free.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/sequence.h"
#include "sdfg/structured_control_flow/structured_loop.h"
#include "sdfg/structured_control_flow/while.h"
#include "sdfg/types/pointer.h"

namespace sdfg {
namespace passes {

InsertFrees::InsertFrees(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager)
    : NonStoppingStructuredSDFGVisitor(builder, analysis_manager) {}

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, analysis::ScopeAnalysis& scope_analysis) {
    auto ancestors = scope_analysis.ancestor_scopes(block);
    for (auto* ancestor : ancestors) {
        if (is_loop(ancestor)) {
            return ancestor;
        }
    }
    return nullptr;
}

bool same_loop_context(
    structured_control_flow::Block* malloc_block,
    structured_control_flow::Block* use_block,
    analysis::ScopeAnalysis& scope_analysis
) {
    auto* malloc_loop = find_containing_loop(malloc_block, scope_analysis);
    auto* use_loop = find_containing_loop(use_block, scope_analysis);

    if (malloc_loop == nullptr && use_loop == nullptr) {
        // Neither is in a loop
        return true;
    }

    if (malloc_loop == use_loop) {
        // Both in the same innermost loop
        return true;
    }

    if (malloc_loop == nullptr && use_loop != nullptr) {
        // Malloc outside loop, use inside loop - different context
        return false;
    }

    if (malloc_loop != nullptr && use_loop != nullptr) {
        auto use_ancestors = scope_analysis.ancestor_scopes(use_block);
        for (auto* ancestor : use_ancestors) {
            if (ancestor == malloc_loop) {
                return false;
            }
        }
    }

    return false;
}

} // anonymous namespace

void InsertFrees::insert_free_after(const std::string& container, analysis::User* last_use) {
    auto& sdfg = builder_.subject();
    auto& escape_analysis = analysis_manager_.get<analysis::EscapeAnalysis>();
    auto& scope_analysis = analysis_manager_.get<analysis::ScopeAnalysis>();

    auto* element = last_use->element();
    if (!element) {
        return;
    }

    structured_control_flow::Block* use_block = nullptr;
    if (auto* access_node = dynamic_cast<data_flow::AccessNode*>(element)) {
        auto* parent = access_node->get_parent().get_parent();
        use_block = dynamic_cast<structured_control_flow::Block*>(parent);
    } else if (auto* lib_node = dynamic_cast<data_flow::LibraryNode*>(element)) {
        auto* parent = lib_node->get_parent().get_parent();
        use_block = dynamic_cast<structured_control_flow::Block*>(parent);
    }

    if (!use_block) {
        return;
    }

    auto* malloc_block = escape_analysis.malloc_block(container);
    if (!malloc_block) {
        return;
    }

    structured_control_flow::ControlFlowNode* insert_after_node = use_block;
    structured_control_flow::Sequence* parent_sequence = nullptr;

    if (same_loop_context(malloc_block, use_block, scope_analysis)) {
        auto* parent_scope = scope_analysis.parent_scope(use_block);
        parent_sequence = dynamic_cast<structured_control_flow::Sequence*>(parent_scope);
    } else {
        auto* malloc_loop = find_containing_loop(malloc_block, scope_analysis);
        auto use_ancestors = scope_analysis.ancestor_scopes(use_block);

        structured_control_flow::ControlFlowNode* target_loop = nullptr;
        for (auto it = use_ancestors.rbegin(); it != use_ancestors.rend(); ++it) {
            if (is_loop(*it)) {
                if (*it != malloc_loop) {
                    target_loop = *it;
                    break;
                }
            }
        }

        if (target_loop) {
            insert_after_node = target_loop;
            auto* loop_parent = scope_analysis.parent_scope(target_loop);
            parent_sequence = dynamic_cast<structured_control_flow::Sequence*>(loop_parent);
        } else {
            auto* parent_scope = scope_analysis.parent_scope(use_block);
            parent_sequence = dynamic_cast<structured_control_flow::Sequence*>(parent_scope);
        }
    }

    if (!parent_sequence) {
        return;
    }

    DebugInfo debug_info;
    auto& free_block = builder_.add_block_after(*parent_sequence, *insert_after_node, {}, debug_info);

    auto& free_node = builder_.add_library_node<stdlib::FreeNode>(free_block, debug_info);

    auto& input_access = builder_.add_access(free_block, container, debug_info);
    auto& output_access = builder_.add_access(free_block, container, debug_info);

    types::Pointer opaque_ptr;
    builder_
        .add_computational_memlet(free_block, input_access, free_node, "_ptr", data_flow::Subset{}, opaque_ptr, debug_info);

    builder_.add_computational_memlet(
        free_block, free_node, "_ptr", output_access, data_flow::Subset{}, opaque_ptr, debug_info
    );
}

bool InsertFrees::visit() {
    auto& escape_analysis = analysis_manager_.get<analysis::EscapeAnalysis>();

    bool applied = false;

    auto non_escaping = escape_analysis.non_escaping_allocations();

    for (const auto& container : non_escaping) {
        if (freed_containers_.count(container) > 0) {
            continue;
        }

        auto* last_use = escape_analysis.last_use(container);
        if (!last_use) {
            continue;
        }

        insert_free_after(container, last_use);
        freed_containers_.insert(container);
        applied = true;
    }

    return applied;
}

} // namespace passes
} // namespace sdfg

1	#include "sdfg/passes/memory/insert_frees.h"
2
3	#include "sdfg/analysis/escape_analysis.h"
4	#include "sdfg/analysis/scope_analysis.h"
5	#include "sdfg/analysis/users.h"
6	#include "sdfg/data_flow/library_nodes/stdlib/free.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/sequence.h"
11	#include "sdfg/structured_control_flow/structured_loop.h"
12	#include "sdfg/structured_control_flow/while.h"
13	#include "sdfg/types/pointer.h"
14
15	namespace sdfg {
16	namespace passes {
17
18	InsertFrees::InsertFrees(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager)
19	: NonStoppingStructuredSDFGVisitor(builder, analysis_manager) {}	21✔
20
21	namespace {
22
23	bool is_loop(structured_control_flow::ControlFlowNode* node) {	64✔
24	return dynamic_cast<structured_control_flow::StructuredLoop*>(node) != nullptr \|\|	64✔
25	dynamic_cast<structured_control_flow::While*>(node) != nullptr;	64✔
26	}	64✔
27
28	structured_control_flow::ControlFlowNode*
29	find_containing_loop(structured_control_flow::Block* block, analysis::ScopeAnalysis& scope_analysis) {	40✔
30	auto ancestors = scope_analysis.ancestor_scopes(block);	40✔
31	for (auto* ancestor : ancestors) {	64✔
32	if (is_loop(ancestor)) {	64✔
33	return ancestor;	12✔
34	}	12✔
35	}	64✔
36	return nullptr;	28✔
37	}	40✔
38
39	bool same_loop_context(
40	structured_control_flow::Block* malloc_block,
41	structured_control_flow::Block* use_block,
42	analysis::ScopeAnalysis& scope_analysis
43	) {	20✔
44	auto* malloc_loop = find_containing_loop(malloc_block, scope_analysis);	20✔
45	auto* use_loop = find_containing_loop(use_block, scope_analysis);	20✔
46
47	if (malloc_loop == nullptr && use_loop == nullptr) {	20✔
48	// Neither is in a loop
49	return true;	14✔
50	}	14✔
51
52	if (malloc_loop == use_loop) {	6✔
53	// Both in the same innermost loop
54	return true;	6✔
55	}	6✔
56
NEW 57	if (malloc_loop == nullptr && use_loop != nullptr) {	×
58	// Malloc outside loop, use inside loop - different context
NEW 59	return false;	×
NEW 60	}	×
61
NEW 62	if (malloc_loop != nullptr && use_loop != nullptr) {	×
NEW 63	auto use_ancestors = scope_analysis.ancestor_scopes(use_block);	×
NEW 64	for (auto* ancestor : use_ancestors) {	×
NEW 65	if (ancestor == malloc_loop) {	×
NEW 66	return false;	×
NEW 67	}	×
NEW 68	}	×
NEW 69	}	×
70
NEW 71	return false;	×
NEW 72	}	×
73
74	} // anonymous namespace
75
76	void InsertFrees::insert_free_after(const std::string& container, analysis::User* last_use) {	20✔
77	auto& sdfg = builder_.subject();	20✔
78	auto& escape_analysis = analysis_manager_.get<analysis::EscapeAnalysis>();	20✔
79	auto& scope_analysis = analysis_manager_.get<analysis::ScopeAnalysis>();	20✔
80
81	auto* element = last_use->element();	20✔
82	if (!element) {	20✔
NEW 83	return;	×
NEW 84	}	×
85
86	structured_control_flow::Block* use_block = nullptr;	20✔
87	if (auto* access_node = dynamic_cast<data_flow::AccessNode*>(element)) {	20✔
88	auto* parent = access_node->get_parent().get_parent();	20✔
89	use_block = dynamic_cast<structured_control_flow::Block*>(parent);	20✔
90	} else if (auto* lib_node = dynamic_cast<data_flow::LibraryNode*>(element)) {	20✔
NEW 91	auto* parent = lib_node->get_parent().get_parent();	×
NEW 92	use_block = dynamic_cast<structured_control_flow::Block*>(parent);	×
NEW 93	}	×
94
95	if (!use_block) {	20✔
NEW 96	return;	×
NEW 97	}	×
98
99	auto* malloc_block = escape_analysis.malloc_block(container);	20✔
100	if (!malloc_block) {	20✔
NEW 101	return;	×
NEW 102	}	×
103
104	structured_control_flow::ControlFlowNode* insert_after_node = use_block;	20✔
105	structured_control_flow::Sequence* parent_sequence = nullptr;	20✔
106
107	if (same_loop_context(malloc_block, use_block, scope_analysis)) {	20✔
108	auto* parent_scope = scope_analysis.parent_scope(use_block);	20✔
109	parent_sequence = dynamic_cast<structured_control_flow::Sequence*>(parent_scope);	20✔
110	} else {	20✔
NEW 111	auto* malloc_loop = find_containing_loop(malloc_block, scope_analysis);	×
NEW 112	auto use_ancestors = scope_analysis.ancestor_scopes(use_block);	×
113
NEW 114	structured_control_flow::ControlFlowNode* target_loop = nullptr;	×
NEW 115	for (auto it = use_ancestors.rbegin(); it != use_ancestors.rend(); ++it) {	×
NEW 116	if (is_loop(*it)) {	×
NEW 117	if (*it != malloc_loop) {	×
NEW 118	target_loop = *it;	×
NEW 119	break;	×
NEW 120	}	×
NEW 121	}	×
NEW 122	}	×
123
NEW 124	if (target_loop) {	×
NEW 125	insert_after_node = target_loop;	×
NEW 126	auto* loop_parent = scope_analysis.parent_scope(target_loop);	×
NEW 127	parent_sequence = dynamic_cast<structured_control_flow::Sequence*>(loop_parent);	×
NEW 128	} else {	×
NEW 129	auto* parent_scope = scope_analysis.parent_scope(use_block);	×
NEW 130	parent_sequence = dynamic_cast<structured_control_flow::Sequence*>(parent_scope);	×
NEW 131	}	×
NEW 132	}	×
133
134	if (!parent_sequence) {	20✔
NEW 135	return;	×
NEW 136	}	×
137
138	DebugInfo debug_info;	20✔
139	auto& free_block = builder_.add_block_after(parent_sequence, insert_after_node, {}, debug_info);	20✔
140
141	auto& free_node = builder_.add_library_node<stdlib::FreeNode>(free_block, debug_info);	20✔
142
143	auto& input_access = builder_.add_access(free_block, container, debug_info);	20✔
144	auto& output_access = builder_.add_access(free_block, container, debug_info);	20✔
145
146	types::Pointer opaque_ptr;	20✔
147	builder_	20✔
148	.add_computational_memlet(free_block, input_access, free_node, "_ptr", data_flow::Subset{}, opaque_ptr, debug_info);	20✔
149
150	builder_.add_computational_memlet(	20✔
151	free_block, free_node, "_ptr", output_access, data_flow::Subset{}, opaque_ptr, debug_info	20✔
152	);	20✔
153	}	20✔
154
155	bool InsertFrees::visit() {	21✔
156	auto& escape_analysis = analysis_manager_.get<analysis::EscapeAnalysis>();	21✔
157
158	bool applied = false;	21✔
159
160	auto non_escaping = escape_analysis.non_escaping_allocations();	21✔
161
162	for (const auto& container : non_escaping) {	21✔
163	if (freed_containers_.count(container) > 0) {	20✔
NEW 164	continue;	×
NEW 165	}	×
166
167	auto* last_use = escape_analysis.last_use(container);	20✔
168	if (!last_use) {	20✔
NEW 169	continue;	×
NEW 170	}	×
171
172	insert_free_after(container, last_use);	20✔
173	freed_containers_.insert(container);	20✔
174	applied = true;	20✔
175	}	20✔
176
177	return applied;	21✔
178	}	21✔
179
180	} // namespace passes
181	} // namespace sdfg

daisytuner / sdfglib / 21504454773

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