18691595059

Committed 21 Oct 2025 05:00PM UTC coverage: 61.604% (+0.4%) from 61.158%

Build # 18691595059

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #291 from daisytuner/allocation-hoisting

adds memory allocation hoisting pass

Run Details

78 of 97 new or added lines in 6 files covered. (80.41%)

1 existing line in 1 file now uncovered.

9458 of 15353 relevant lines covered (61.6%)

92.42 hits per line

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

87.06

/src/passes/memory/allocation_hoisting.cpp

#include "sdfg/passes/memory/allocation_hoisting.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 {

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

bool AllocationHoisting::can_be_applied(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 AllocationHoisting::apply(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::AllocationLifetime::Lifetime_Default);
    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 AllocationHoisting::accept(structured_control_flow::Block& node) {
    bool applied = false;

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

} // namespace passes
} // namespace sdfg

1	#include "sdfg/passes/memory/allocation_hoisting.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	AllocationHoisting::AllocationHoisting(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager)	3✔
13	: NonStoppingStructuredSDFGVisitor(builder, analysis_manager) {}	3✔
14
15	bool AllocationHoisting::can_be_applied(data_flow::DataFlowGraph& graph, data_flow::LibraryNode& library_node) {	3✔
16	symbolic::Expression allocation_size = SymEngine::null;	3✔
17	const data_flow::LibraryNode* libnode = nullptr;	3✔
18	if (library_node.code() == stdlib::LibraryNodeType_Alloca) {	3✔
19	if (auto alloca_node = dynamic_cast<stdlib::AllocaNode*>(&library_node)) {	1✔
20	libnode = &library_node;	1✔
21	allocation_size = alloca_node->size();	1✔
22	}	1✔
23	} else if (library_node.code() == stdlib::LibraryNodeType_Malloc) {	3✔
24	if (auto malloc_node = dynamic_cast<stdlib::MallocNode*>(&library_node)) {	2✔
25	libnode = &library_node;	2✔
26	allocation_size = malloc_node->size();	2✔
27	}	2✔
28	}	2✔
29	if (libnode == nullptr \|\| allocation_size.is_null()) {	3✔
NEW 30	return false;	×
31	}
32
33	// Retrieve allocated container
34	auto& sdfg = this->builder_.subject();	3✔
35	auto& oedge = *graph.out_edges(library_node).begin();	3✔
36	auto& dst = static_cast<data_flow::AccessNode&>(oedge.dst());	3✔
37	const std::string& container = dst.data();	3✔
38	auto& type = sdfg.type(container);	3✔
39	if (type.type_id() != types::TypeID::Pointer) {	3✔
NEW 40	return false;	×
41	}
42
43	// Limitations
44	if (graph.out_degree(dst) != 0) {	3✔
NEW 45	return false;	×
46	}
47	if (graph.in_degree(dst) != 1) {	3✔
NEW 48	return false;	×
49	}
50	if (graph.in_degree(*libnode) != 0) {	3✔
NEW 51	return false;	×
52	}
53
54	// Limitations
55	auto& block = static_cast<structured_control_flow::Block&>(*graph.get_parent());	3✔
56	auto& scope_analysis = this->analysis_manager_.get<analysis::ScopeAnalysis>();	3✔
57	if (scope_analysis.parent_scope(&block) != &sdfg.root()) {	3✔
NEW 58	return false;	×
59	}
60
61	// Criterion 1: Allocation size only depends on parameters
62	for (auto& sym : symbolic::atoms(allocation_size)) {	3✔
NEW 63	if (!sdfg.is_argument(sym->get_name())) {	×
NEW 64	return false;	×
65	}
66	}
67
68	// Criterion 2: Allocation dominates all uses
69	auto& users_analysis = this->analysis_manager_.get<analysis::Users>();	3✔
70	auto& dominance_analysis = this->analysis_manager_.get<analysis::DominanceAnalysis>();	3✔
71	auto uses = users_analysis.uses(container);	3✔
72	analysis::User* allocation_user = users_analysis.get_user(container, &dst, analysis::Use::WRITE);	3✔
73	for (auto& use : uses) {	6✔
74	if (use == allocation_user) {	3✔
75	continue;	3✔
76	}
NEW 77	if (!dominance_analysis.dominates(allocation_user, use)) {	×
NEW 78	return false;	×
79	}
80	}
81
82	return true;	3✔
83	}	3✔
84
85	void AllocationHoisting::apply(data_flow::DataFlowGraph& graph, data_flow::LibraryNode& library_node) {	3✔
86	symbolic::Expression allocation_size = SymEngine::null;	3✔
87	std::string storage_type_val;	3✔
88	if (library_node.code() == stdlib::LibraryNodeType_Alloca) {	3✔
89	if (auto alloca_node = dynamic_cast<stdlib::AllocaNode*>(&library_node)) {	1✔
90	allocation_size = alloca_node->size();	1✔
91	storage_type_val = "CPU_Stack";	1✔
92	}	1✔
93	} else if (library_node.code() == stdlib::LibraryNodeType_Malloc) {	3✔
94	if (auto malloc_node = dynamic_cast<stdlib::MallocNode*>(&library_node)) {	2✔
95	allocation_size = malloc_node->size();	2✔
96	storage_type_val = "CPU_Heap";	2✔
97	}	2✔
98	}	2✔
99
100	auto& sdfg = this->builder_.subject();	3✔
101	auto& oedge = *graph.out_edges(library_node).begin();	3✔
102	auto& dst = static_cast<data_flow::AccessNode&>(oedge.dst());	3✔
103	const std::string& container = dst.data();	3✔
104
105	// Update storage type
106	auto& type = sdfg.type(container);	3✔
107
108	auto new_type = type.clone();	3✔
109	types::StorageType new_storage_type =
110	types::StorageType(storage_type_val, allocation_size, types::StorageType::AllocationLifetime::Lifetime_Default);	3✔
111	new_type->storage_type(new_storage_type);	3✔
112
113	builder_.change_type(container, *new_type);	3✔
114
115	// Remove allocation node
116	auto& block = static_cast<structured_control_flow::Block&>(*graph.get_parent());	3✔
117	builder_.clear_node(block, dst);	3✔
118	}	3✔
119
120	bool AllocationHoisting::accept(structured_control_flow::Block& node) {	3✔
121	bool applied = false;	3✔
122
123	auto& graph = node.dataflow();	3✔
124	for (auto& lib_node : graph.library_nodes()) {	6✔
125	if (can_be_applied(graph, *lib_node)) {	3✔
126	apply(graph, *lib_node);	3✔
127	applied = true;	3✔
128	}	3✔
129	}
130	return applied; // Return whether any node was modified	3✔
NEW 131	}	×
132
133	} // namespace passes
134	} // namespace sdfg

daisytuner / sdfglib / 18691595059

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