26556322966

Committed 27 May 2026 03:45PM UTC coverage: 60.869% (-0.02%) from 60.886%

Build # 26556322966

Build Type

push

github

Committed by

web-flow

Commit Message

Libnode ptr edges (#719)

Migrating SDFGs to treat pointers as inputs to libNodes / Calls as scalars.
A pointer will only appear in an output edge if its actually returned from the function (like malloc).

* Stdlib, Blas and Tensor Matmul nodes were migrated to this new format. Other, currently transitory Tensor Nodes are not yet migrated.
* DOCC version was bumped to incorporate previous docc-llvm versions (up to 0.4.0) that had been counted separately.
! Until all passes consider the use / leak of pointers as uncertainty / hiding potential writes, TensorNodes are declared as general side-effect.
* Lots of utility functions to centralize the creation (and edges) of various libNodes that needed to be changed.
* Fixed & unified docc paths across python and llvm front-ends.
* Skip BlockFusion test that fails to its libNodes currently having side effects
~ Prevent a crash in DotViz when using symbolic offsets into structs
* Removing old ConstProp pass, it is not safe for the new pointer representation and should not be all too critical

Coverage Stats

961 of 1749 new or added lines in 52 files covered. (54.95%)

87 existing lines in 28 files now uncovered.

35225 of 57870 relevant lines covered (60.87%)

11046.32 hits per line

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

82.82

/sdfg/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_access_node_legacy(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& iedge = *graph.in_edge_for_connector(library_node, library_node.input(0));
    auto& src = static_cast<const data_flow::AccessNode&>(iedge.src());
    const std::string& container = src.data();
    auto& type = sdfg.type(container);
    if (type.type_id() != types::TypeID::Pointer) {
        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, const_cast<data_flow::AccessNode*>(&src), analysis::Use::READ);
    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& iedge = *graph.in_edge_for_connector(library_node, library_node.input(0));
    auto& src = static_cast<const data_flow::AccessNode&>(iedge.src());
    const std::string& container = src.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, library_node);
}

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_access_node_legacy(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& iedge = *graph.in_edge_for_connector(library_node, library_node.input(0));	2✔
140	auto& src = static_cast<const data_flow::AccessNode&>(iedge.src());	2✔
141	const std::string& container = src.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	auto& block = static_cast<structured_control_flow::Block&>(*graph.get_parent());	2✔
149	auto& scope_analysis = this->analysis_manager_.get<analysis::ScopeAnalysis>();	2✔
150	if (scope_analysis.parent_scope(&block) != &sdfg.root()) {	2✔
151	return false;	×
152	}	×
153
154	// Criterion 2: Allocation post-dominates all uses
155	auto& users_analysis = this->analysis_manager_.get<analysis::Users>();	2✔
156	auto& dominance_analysis = this->analysis_manager_.get<analysis::DominanceAnalysis>();	2✔
157	auto uses = users_analysis.uses(container);	2✔
158	analysis::User* deallocation_user =	2✔
159	users_analysis.get_user(container, const_cast<data_flow::AccessNode*>(&src), analysis::Use::READ);	2✔
160	for (auto& use : uses) {	2✔
161	if (use == deallocation_user) {	2✔
162	continue;	2✔
163	}	2✔
UNCOV 164	if (!dominance_analysis.post_dominates(deallocation_user, use)) {	×
165	return false;	×
166	}	×
UNCOV 167	}	×
168
169	return true;	2✔
170	}	2✔
171
172	void AllocationManagement::apply_deallocation(data_flow::DataFlowGraph& graph, data_flow::LibraryNode& library_node) {	2✔
173	auto& sdfg = this->builder_.subject();	2✔
174	auto& iedge = *graph.in_edge_for_connector(library_node, library_node.input(0));	2✔
175	auto& src = static_cast<const data_flow::AccessNode&>(iedge.src());	2✔
176	const std::string& container = src.data();	2✔
177
178	// Update storage type
179	auto& type = sdfg.type(container);	2✔
180
181	auto new_type = type.clone();	2✔
182	types::StorageType new_storage_type = types::StorageType(	2✔
183	"CPU_Heap",	2✔
184	type.storage_type().allocation_size(),	2✔
185	type.storage_type().allocation(),	2✔
186	types::StorageType::AllocationType::Managed	2✔
187	);	2✔
188	new_type->storage_type(new_storage_type);	2✔
189
190	builder_.change_type(container, *new_type);	2✔
191
192	// Remove allocation node
193	auto& block = static_cast<structured_control_flow::Block&>(*graph.get_parent());	2✔
194	builder_.clear_node(block, library_node);	2✔
195	}	2✔
196
197	bool AllocationManagement::accept(structured_control_flow::Block& node) {	5✔
198	bool applied = false;	5✔
199
200	auto& graph = node.dataflow();	5✔
201	for (auto& lib_node : graph.library_nodes()) {	5✔
202	if (can_be_applied_allocation(graph, *lib_node)) {	5✔
203	apply_allocation(graph, *lib_node);	3✔
204	applied = true;	3✔
205	continue;	3✔
206	}	3✔
207	if (can_be_applied_deallocation(graph, *lib_node)) {	2✔
208	apply_deallocation(graph, *lib_node);	2✔
209	applied = true;	2✔
210	continue;	2✔
211	}	2✔
212	}	2✔
213	return applied; // Return whether any node was modified	5✔
214	}	5✔
215
216	} // namespace passes
217	} // namespace sdfg

daisytuner / docc / 26556322966

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