20770413849

Committed 06 Jan 2026 10:50PM UTC coverage: 62.168% (+21.4%) from 40.764%

Build # 20770413849

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #433 from daisytuner/clang-coverage

updates clang coverage flags

Run Details

14988 of 24109 relevant lines covered (62.17%)

88.57 hits per line

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

82.14

/src/passes/memory/allocation_management.cpp

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

#include "sdfg/analysis/dominance_analysis.h"
#include "sdfg/analysis/scope_analysis.h"
#include "sdfg/analysis/users.h"

#include "sdfg/data_flow/library_nodes/stdlib/stdlib.h"

namespace sdfg {
namespace passes {

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

bool AllocationManagement::can_be_applied_allocation(data_flow::DataFlowGraph& graph, data_flow::LibraryNode& library_node) {
    symbolic::Expression allocation_size = SymEngine::null;
    const data_flow::LibraryNode* libnode = nullptr;
    if (library_node.code() == stdlib::LibraryNodeType_Alloca) {
        if (auto alloca_node = dynamic_cast<stdlib::AllocaNode*>(&library_node)) {
            libnode = &library_node;
            allocation_size = alloca_node->size();
        }
    } else if (library_node.code() == stdlib::LibraryNodeType_Malloc) {
        if (auto malloc_node = dynamic_cast<stdlib::MallocNode*>(&library_node)) {
            libnode = &library_node;
            allocation_size = malloc_node->size();
        }
    }
    if (libnode == nullptr || allocation_size.is_null()) {
        return false;
    }

    // Retrieve allocated container
    auto& sdfg = this->builder_.subject();
    auto& oedge = *graph.out_edges(library_node).begin();
    auto& dst = static_cast<data_flow::AccessNode&>(oedge.dst());
    const std::string& container = dst.data();
    auto& type = sdfg.type(container);
    if (type.type_id() != types::TypeID::Pointer) {
        return false;
    }

    // Limitations
    if (graph.out_degree(dst) != 0) {
        return false;
    }
    if (graph.in_degree(dst) != 1) {
        return false;
    }
    if (graph.in_degree(*libnode) != 0) {
        return false;
    }

    // Limitations
    auto& block = static_cast<structured_control_flow::Block&>(*graph.get_parent());
    auto& scope_analysis = this->analysis_manager_.get<analysis::ScopeAnalysis>();
    if (scope_analysis.parent_scope(&block) != &sdfg.root()) {
        return false;
    }

    // Criterion 1: Allocation size only depends on parameters
    for (auto& sym : symbolic::atoms(allocation_size)) {
        if (!sdfg.is_argument(sym->get_name())) {
            return false;
        }
    }

    // Criterion 2: Allocation dominates all uses
    auto& users_analysis = this->analysis_manager_.get<analysis::Users>();
    auto& dominance_analysis = this->analysis_manager_.get<analysis::DominanceAnalysis>();
    auto uses = users_analysis.uses(container);
    analysis::User* allocation_user = users_analysis.get_user(container, &dst, analysis::Use::WRITE);
    for (auto& use : uses) {
        if (use == allocation_user) {
            continue;
        }
        if (!dominance_analysis.dominates(*allocation_user, *use)) {
            return false;
        }
    }

    return true;
}

void AllocationManagement::apply_allocation(data_flow::DataFlowGraph& graph, data_flow::LibraryNode& library_node) {
    symbolic::Expression allocation_size = SymEngine::null;
    std::string storage_type_val;
    if (library_node.code() == stdlib::LibraryNodeType_Alloca) {
        if (auto alloca_node = dynamic_cast<stdlib::AllocaNode*>(&library_node)) {
            allocation_size = alloca_node->size();
            storage_type_val = "CPU_Stack";
        }
    } else if (library_node.code() == stdlib::LibraryNodeType_Malloc) {
        if (auto malloc_node = dynamic_cast<stdlib::MallocNode*>(&library_node)) {
            allocation_size = malloc_node->size();
            storage_type_val = "CPU_Heap";
        }
    }

    auto& sdfg = this->builder_.subject();
    auto& oedge = *graph.out_edges(library_node).begin();
    auto& dst = static_cast<data_flow::AccessNode&>(oedge.dst());
    const std::string& container = dst.data();

    // Update storage type
    auto& type = sdfg.type(container);

    auto new_type = type.clone();
    types::StorageType new_storage_type = types::StorageType(
        storage_type_val,
        allocation_size,
        types::StorageType::AllocationType::Managed,
        type.storage_type().deallocation()
    );
    new_type->storage_type(new_storage_type);

    builder_.change_type(container, *new_type);

    // Remove allocation node
    auto& block = static_cast<structured_control_flow::Block&>(*graph.get_parent());
    builder_.clear_node(block, dst);
}

bool AllocationManagement::
    can_be_applied_deallocation(data_flow::DataFlowGraph& graph, data_flow::LibraryNode& library_node) {
    const data_flow::LibraryNode* libnode = nullptr;
    if (library_node.code() == stdlib::LibraryNodeType_Free) {
        if (auto free_node = dynamic_cast<stdlib::FreeNode*>(&library_node)) {
            libnode = &library_node;
        }
    }
    if (libnode == nullptr) {
        return false;
    }

    // Retrieve allocated container
    auto& sdfg = this->builder_.subject();
    auto& oedge = *graph.out_edges(library_node).begin();
    auto& dst = static_cast<data_flow::AccessNode&>(oedge.dst());
    const std::string& container = dst.data();
    auto& type = sdfg.type(container);
    if (type.type_id() != types::TypeID::Pointer) {
        return false;
    }

    // Limitations
    if (graph.out_degree(dst) != 0) {
        return false;
    }
    if (graph.in_degree(dst) != 1) {
        return false;
    }

    // Limitations
    auto& block = static_cast<structured_control_flow::Block&>(*graph.get_parent());
    auto& scope_analysis = this->analysis_manager_.get<analysis::ScopeAnalysis>();
    if (scope_analysis.parent_scope(&block) != &sdfg.root()) {
        return false;
    }

    // Criterion 2: Allocation post-dominates all uses
    auto& users_analysis = this->analysis_manager_.get<analysis::Users>();
    auto& dominance_analysis = this->analysis_manager_.get<analysis::DominanceAnalysis>();
    auto uses = users_analysis.uses(container);
    analysis::User* deallocation_user = users_analysis.get_user(container, &dst, analysis::Use::WRITE);
    for (auto& use : uses) {
        if (use == deallocation_user) {
            continue;
        }
        if (!dominance_analysis.post_dominates(*deallocation_user, *use)) {
            return false;
        }
    }

    return true;
}

void AllocationManagement::apply_deallocation(data_flow::DataFlowGraph& graph, data_flow::LibraryNode& library_node) {
    auto& sdfg = this->builder_.subject();
    auto& oedge = *graph.out_edges(library_node).begin();
    auto& dst = static_cast<data_flow::AccessNode&>(oedge.dst());
    const std::string& container = dst.data();

    // Update storage type
    auto& type = sdfg.type(container);

    auto new_type = type.clone();
    types::StorageType new_storage_type = types::StorageType(
        "CPU_Heap",
        type.storage_type().allocation_size(),
        type.storage_type().allocation(),
        types::StorageType::AllocationType::Managed
    );
    new_type->storage_type(new_storage_type);

    builder_.change_type(container, *new_type);

    // Remove allocation node
    auto& block = static_cast<structured_control_flow::Block&>(*graph.get_parent());
    builder_.clear_node(block, dst);
}

bool AllocationManagement::accept(structured_control_flow::Block& node) {
    bool applied = false;

    auto& graph = node.dataflow();
    for (auto& lib_node : graph.library_nodes()) {
        if (can_be_applied_allocation(graph, *lib_node)) {
            apply_allocation(graph, *lib_node);
            applied = true;
            continue;
        }
        if (can_be_applied_deallocation(graph, *lib_node)) {
            apply_deallocation(graph, *lib_node);
            applied = true;
            continue;
        }
    }
    return applied; // Return whether any node was modified
}

} // namespace passes
} // namespace sdfg

1	#include "sdfg/passes/memory/allocation_management.h"
2
3	#include "sdfg/analysis/dominance_analysis.h"
4	#include "sdfg/analysis/scope_analysis.h"
5	#include "sdfg/analysis/users.h"
6
7	#include "sdfg/data_flow/library_nodes/stdlib/stdlib.h"
8
9	namespace sdfg {
10	namespace passes {
11
12	AllocationManagement::
13	AllocationManagement(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager)
14	: NonStoppingStructuredSDFGVisitor(builder, analysis_manager) {}	5✔
15
16	bool AllocationManagement::can_be_applied_allocation(data_flow::DataFlowGraph& graph, data_flow::LibraryNode& library_node) {	5✔
17	symbolic::Expression allocation_size = SymEngine::null;	5✔
18	const data_flow::LibraryNode* libnode = nullptr;	5✔
19	if (library_node.code() == stdlib::LibraryNodeType_Alloca) {	5✔
20	if (auto alloca_node = dynamic_cast<stdlib::AllocaNode*>(&library_node)) {	1✔
21	libnode = &library_node;	1✔
22	allocation_size = alloca_node->size();	1✔
23	}	1✔
24	} else if (library_node.code() == stdlib::LibraryNodeType_Malloc) {	4✔
25	if (auto malloc_node = dynamic_cast<stdlib::MallocNode*>(&library_node)) {	2✔
26	libnode = &library_node;	2✔
27	allocation_size = malloc_node->size();	2✔
28	}	2✔
29	}	2✔
30	if (libnode == nullptr \|\| allocation_size.is_null()) {	5✔
31	return false;	2✔
32	}	2✔
33
34	// Retrieve allocated container
35	auto& sdfg = this->builder_.subject();	3✔
36	auto& oedge = *graph.out_edges(library_node).begin();	3✔
37	auto& dst = static_cast<data_flow::AccessNode&>(oedge.dst());	3✔
38	const std::string& container = dst.data();	3✔
39	auto& type = sdfg.type(container);	3✔
40	if (type.type_id() != types::TypeID::Pointer) {	3✔
41	return false;	×
42	}	×
43
44	// Limitations
45	if (graph.out_degree(dst) != 0) {	3✔
46	return false;	×
47	}	×
48	if (graph.in_degree(dst) != 1) {	3✔
49	return false;	×
50	}	×
51	if (graph.in_degree(*libnode) != 0) {	3✔
52	return false;	×
53	}	×
54
55	// Limitations
56	auto& block = static_cast<structured_control_flow::Block&>(*graph.get_parent());	3✔
57	auto& scope_analysis = this->analysis_manager_.get<analysis::ScopeAnalysis>();	3✔
58	if (scope_analysis.parent_scope(&block) != &sdfg.root()) {	3✔
59	return false;	×
60	}	×
61
62	// Criterion 1: Allocation size only depends on parameters
63	for (auto& sym : symbolic::atoms(allocation_size)) {	3✔
64	if (!sdfg.is_argument(sym->get_name())) {	×
65	return false;	×
66	}	×
67	}	×
68
69	// Criterion 2: Allocation dominates all uses
70	auto& users_analysis = this->analysis_manager_.get<analysis::Users>();	3✔
71	auto& dominance_analysis = this->analysis_manager_.get<analysis::DominanceAnalysis>();	3✔
72	auto uses = users_analysis.uses(container);	3✔
73	analysis::User* allocation_user = users_analysis.get_user(container, &dst, analysis::Use::WRITE);	3✔
74	for (auto& use : uses) {	3✔
75	if (use == allocation_user) {	3✔
76	continue;	3✔
77	}	3✔
78	if (!dominance_analysis.dominates(allocation_user, use)) {	×
79	return false;	×
80	}	×
81	}	×
82
83	return true;	3✔
84	}	3✔
85
86	void AllocationManagement::apply_allocation(data_flow::DataFlowGraph& graph, data_flow::LibraryNode& library_node) {	3✔
87	symbolic::Expression allocation_size = SymEngine::null;	3✔
88	std::string storage_type_val;	3✔
89	if (library_node.code() == stdlib::LibraryNodeType_Alloca) {	3✔
90	if (auto alloca_node = dynamic_cast<stdlib::AllocaNode*>(&library_node)) {	1✔
91	allocation_size = alloca_node->size();	1✔
92	storage_type_val = "CPU_Stack";	1✔
93	}	1✔
94	} else if (library_node.code() == stdlib::LibraryNodeType_Malloc) {	2✔
95	if (auto malloc_node = dynamic_cast<stdlib::MallocNode*>(&library_node)) {	2✔
96	allocation_size = malloc_node->size();	2✔
97	storage_type_val = "CPU_Heap";	2✔
98	}	2✔
99	}	2✔
100
101	auto& sdfg = this->builder_.subject();	3✔
102	auto& oedge = *graph.out_edges(library_node).begin();	3✔
103	auto& dst = static_cast<data_flow::AccessNode&>(oedge.dst());	3✔
104	const std::string& container = dst.data();	3✔
105
106	// Update storage type
107	auto& type = sdfg.type(container);	3✔
108
109	auto new_type = type.clone();	3✔
110	types::StorageType new_storage_type = types::StorageType(	3✔
111	storage_type_val,	3✔
112	allocation_size,	3✔
113	types::StorageType::AllocationType::Managed,	3✔
114	type.storage_type().deallocation()	3✔
115	);	3✔
116	new_type->storage_type(new_storage_type);	3✔
117
118	builder_.change_type(container, *new_type);	3✔
119
120	// Remove allocation node
121	auto& block = static_cast<structured_control_flow::Block&>(*graph.get_parent());	3✔
122	builder_.clear_node(block, dst);	3✔
123	}	3✔
124
125	bool AllocationManagement::
126	can_be_applied_deallocation(data_flow::DataFlowGraph& graph, data_flow::LibraryNode& library_node) {	2✔
127	const data_flow::LibraryNode* libnode = nullptr;	2✔
128	if (library_node.code() == stdlib::LibraryNodeType_Free) {	2✔
129	if (auto free_node = dynamic_cast<stdlib::FreeNode*>(&library_node)) {	2✔
130	libnode = &library_node;	2✔
131	}	2✔
132	}	2✔
133	if (libnode == nullptr) {	2✔
134	return false;	×
135	}	×
136
137	// Retrieve allocated container
138	auto& sdfg = this->builder_.subject();	2✔
139	auto& oedge = *graph.out_edges(library_node).begin();	2✔
140	auto& dst = static_cast<data_flow::AccessNode&>(oedge.dst());	2✔
141	const std::string& container = dst.data();	2✔
142	auto& type = sdfg.type(container);	2✔
143	if (type.type_id() != types::TypeID::Pointer) {	2✔
144	return false;	×
145	}	×
146
147	// Limitations
148	if (graph.out_degree(dst) != 0) {	2✔
149	return false;	×
150	}	×
151	if (graph.in_degree(dst) != 1) {	2✔
152	return false;	×
153	}	×
154
155	// Limitations
156	auto& block = static_cast<structured_control_flow::Block&>(*graph.get_parent());	2✔
157	auto& scope_analysis = this->analysis_manager_.get<analysis::ScopeAnalysis>();	2✔
158	if (scope_analysis.parent_scope(&block) != &sdfg.root()) {	2✔
159	return false;	×
160	}	×
161
162	// Criterion 2: Allocation post-dominates all uses
163	auto& users_analysis = this->analysis_manager_.get<analysis::Users>();	2✔
164	auto& dominance_analysis = this->analysis_manager_.get<analysis::DominanceAnalysis>();	2✔
165	auto uses = users_analysis.uses(container);	2✔
166	analysis::User* deallocation_user = users_analysis.get_user(container, &dst, analysis::Use::WRITE);	2✔
167	for (auto& use : uses) {	4✔
168	if (use == deallocation_user) {	4✔
169	continue;	2✔
170	}	2✔
171	if (!dominance_analysis.post_dominates(deallocation_user, use)) {	2✔
172	return false;	×
173	}	×
174	}	2✔
175
176	return true;	2✔
177	}	2✔
178
179	void AllocationManagement::apply_deallocation(data_flow::DataFlowGraph& graph, data_flow::LibraryNode& library_node) {	2✔
180	auto& sdfg = this->builder_.subject();	2✔
181	auto& oedge = *graph.out_edges(library_node).begin();	2✔
182	auto& dst = static_cast<data_flow::AccessNode&>(oedge.dst());	2✔
183	const std::string& container = dst.data();	2✔
184
185	// Update storage type
186	auto& type = sdfg.type(container);	2✔
187
188	auto new_type = type.clone();	2✔
189	types::StorageType new_storage_type = types::StorageType(	2✔
190	"CPU_Heap",	2✔
191	type.storage_type().allocation_size(),	2✔
192	type.storage_type().allocation(),	2✔
193	types::StorageType::AllocationType::Managed	2✔
194	);	2✔
195	new_type->storage_type(new_storage_type);	2✔
196
197	builder_.change_type(container, *new_type);	2✔
198
199	// Remove allocation node
200	auto& block = static_cast<structured_control_flow::Block&>(*graph.get_parent());	2✔
201	builder_.clear_node(block, dst);	2✔
202	}	2✔
203
204	bool AllocationManagement::accept(structured_control_flow::Block& node) {	5✔
205	bool applied = false;	5✔
206
207	auto& graph = node.dataflow();	5✔
208	for (auto& lib_node : graph.library_nodes()) {	5✔
209	if (can_be_applied_allocation(graph, *lib_node)) {	5✔
210	apply_allocation(graph, *lib_node);	3✔
211	applied = true;	3✔
212	continue;	3✔
213	}	3✔
214	if (can_be_applied_deallocation(graph, *lib_node)) {	2✔
215	apply_deallocation(graph, *lib_node);	2✔
216	applied = true;	2✔
217	continue;	2✔
218	}	2✔
219	}	2✔
220	return applied; // Return whether any node was modified	5✔
221	}	5✔
222
223	} // namespace passes
224	} // namespace sdfg

daisytuner / sdfglib / 20770413849

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