23986340991

Committed 04 Apr 2026 07:51PM UTC coverage: 64.827% (+0.05%) from 64.774%

Build # 23986340991

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #647 from daisytuner/in-local-storage

Adds InLocalStorage transformation

Coverage Stats

139 of 178 new or added lines in 2 files covered. (78.09%)

29303 of 45202 relevant lines covered (64.83%)

530.65 hits per line

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

78.98

/opt/src/transformations/in_local_storage.cpp

#include "sdfg/transformations/in_local_storage.h"

#include <cassert>
#include <cstddef>
#include <string>

#include "sdfg/analysis/assumptions_analysis.h"
#include "sdfg/analysis/scope_analysis.h"
#include "sdfg/analysis/type_analysis.h"
#include "sdfg/analysis/users.h"
#include "sdfg/builder/structured_sdfg_builder.h"
#include "sdfg/data_flow/access_node.h"
#include "sdfg/data_flow/memlet.h"
#include "sdfg/passes/structured_control_flow/dead_cfg_elimination.h"
#include "sdfg/passes/structured_control_flow/sequence_fusion.h"
#include "sdfg/structured_control_flow/sequence.h"
#include "sdfg/structured_control_flow/structured_loop.h"
#include "sdfg/symbolic/symbolic.h"
#include "sdfg/transformations/utils.h"
#include "sdfg/types/array.h"
#include "sdfg/types/scalar.h"

namespace sdfg {
namespace transformations {

InLocalStorage::InLocalStorage(structured_control_flow::StructuredLoop& loop, std::string container)
    : loop_(loop), container_(std::move(container)) {}

std::string InLocalStorage::name() const { return "InLocalStorage"; }

bool InLocalStorage::can_be_applied(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {
    auto& sdfg = builder.subject();
    auto& body = this->loop_.root();

    // Criterion: Container must exist in the SDFG
    if (!sdfg.exists(this->container_)) {
        return false;
    }

    // Criterion: Container must be an array type
    auto& container_type = sdfg.type(this->container_);
    if (container_type.type_id() != types::TypeID::Pointer && container_type.type_id() != types::TypeID::Array) {
        return false;
    }

    // Criterion: Check if container is used in the loop
    auto& users = analysis_manager.get<analysis::Users>();
    analysis::UsersView body_users(users, body);
    if (body_users.uses(this->container_).empty()) {
        return false;
    }

    // Criterion: Container must be READ-ONLY within the loop (no writes)
    // This is what distinguishes InLocalStorage from OutLocalStorage
    if (!body_users.writes(this->container_).empty()) {
        return false;
    }

    // Criterion: All accesses must have the same dimensionality
    auto accesses = body_users.uses(this->container_);
    auto first_access = accesses.at(0);
    auto first_subsets = first_access->subsets();
    if (first_subsets.empty()) {
        return false;
    }
    auto& first_subset = first_subsets.at(0);
    if (first_subset.size() == 0) {
        return false;
    }

    for (auto* access : accesses) {
        for (auto& subset : access->subsets()) {
            if (subset.size() != first_subset.size()) {
                return false;
            }
        }
    }

    // Store representative subset for later use
    access_info_.representative_subset = first_subset;

    // Analyze index expressions per dimension
    // For simplicity, we require that the access pattern uses the loop indvar
    // and the buffer size equals the iteration count
    auto iteration_count = this->loop_.num_iterations();
    if (iteration_count.is_null()) {
        return false;
    }

    // For each dimension, determine if it depends on the loop indvar
    // We support 1D localization: the dimension that uses loop indvar gets iteration_count size
    access_info_.dimensions.clear();
    access_info_.bases.clear();

    bool found_loop_dim = false;
    for (size_t d = 0; d < first_subset.size(); d++) {
        auto& index_expr = first_subset.at(d);
        auto atoms = symbolic::atoms(index_expr);

        bool depends_on_indvar = false;
        for (auto& atom : atoms) {
            if (symbolic::eq(atom, this->loop_.indvar())) {
                depends_on_indvar = true;
                break;
            }
        }

        if (depends_on_indvar) {
            // This dimension is indexed by the loop variable
            // Buffer dimension = iteration count
            access_info_.dimensions.push_back(iteration_count);
            // Base = the constant part (index_expr - indvar contribution at init)
            auto base = symbolic::subs(index_expr, this->loop_.indvar(), this->loop_.init());
            access_info_.bases.push_back(base);
            found_loop_dim = true;
        } else {
            // This dimension is constant across loop iterations
            // We still need to capture it for multi-dimensional buffers
            access_info_.dimensions.push_back(symbolic::integer(1));
            access_info_.bases.push_back(index_expr);
        }
    }

    // We need at least one dimension that depends on the loop indvar
    if (!found_loop_dim) {
        return false;
    }

    return true;
}

void InLocalStorage::apply(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {
    auto& sdfg = builder.subject();
    auto& users = analysis_manager.get<analysis::Users>();
    auto& scope_analysis = analysis_manager.get<analysis::ScopeAnalysis>();

    auto parent_node = scope_analysis.parent_scope(&loop_);
    auto parent = dynamic_cast<structured_control_flow::Sequence*>(parent_node);
    if (!parent) {
        throw InvalidSDFGException("InLocalStorage: Parent of loop must be a Sequence!");
    }

    // Get type information for the original container
    analysis::TypeAnalysis type_analysis(sdfg, &loop_, analysis_manager);
    auto type = type_analysis.get_outer_type(container_);
    types::Scalar scalar_type(type->primitive_type());

    // Create local buffer name
    local_name_ = "__daisy_in_local_storage_" + this->container_;

    // Create the local buffer array
    // For now, we support 1D buffer matching the iteration count
    auto iteration_count = this->loop_.num_iterations();
    types::Array array_type(scalar_type, iteration_count);
    builder.add_container(local_name_, array_type);

    // Create loop index variable for the copy loop
    auto indvar_name = "__daisy_in_local_storage_" + this->loop_.indvar()->get_name();
    types::Scalar indvar_type(sdfg.type(loop_.indvar()->get_name()).primitive_type());
    builder.add_container(indvar_name, indvar_type);
    auto indvar = symbolic::symbol(indvar_name);

    auto init = loop_.init();
    auto update = symbolic::subs(loop_.update(), loop_.indvar(), indvar);
    auto condition = symbolic::subs(loop_.condition(), loop_.indvar(), indvar);

    // Get access information from loop body
    analysis::UsersView body_users(users, loop_.root());
    auto accesses = body_users.uses(this->container_);
    auto first_access = accesses.at(0);
    auto first_subset = first_access->subsets().at(0);

    // Insert copy loop BEFORE the main loop: A_local[i] = A[...]
    auto& copy_loop = builder.add_for_before(*parent, loop_, indvar, condition, init, update, {}, loop_.debug_info());
    auto& copy_body = copy_loop.root();
    auto& copy_block = builder.add_block(copy_body);

    // Read from original container
    auto& copy_access_src = builder.add_access(copy_block, this->container_);
    // Write to local buffer
    auto& copy_access_dst = builder.add_access(copy_block, local_name_);
    // Tasklet: _out = _in
    auto& copy_tasklet = builder.add_tasklet(copy_block, data_flow::TaskletCode::assign, "_out", {"_in"});

    // Input memlet: read from original array with substituted index
    auto& copy_memlet_in =
        builder.add_computational_memlet(copy_block, copy_access_src, copy_tasklet, "_in", first_subset, *type);
    copy_memlet_in.replace(loop_.indvar(), indvar);

    // Output memlet: write to local buffer indexed by loop variable
    builder.add_computational_memlet(copy_block, copy_tasklet, "_out", copy_access_dst, {indvar}, array_type);

    // Now update all accesses in the main loop body to use the local buffer
    // Change subset to use just the loop indvar
    for (auto* user : body_users.uses(this->container_)) {
        auto element = user->element();
        if (auto memlet = dynamic_cast<data_flow::Memlet*>(element)) {
            auto subset = memlet->subset();
            subset.clear();
            subset.push_back(this->loop_.indvar());
            memlet->set_subset(subset);
        }
    }

    // Update access node edges to use local buffer type
    for (auto* user : body_users.uses(this->container_)) {
        auto element = user->element();
        if (auto access = dynamic_cast<data_flow::AccessNode*>(element)) {
            for (auto& iedge : access->get_parent().in_edges(*access)) {
                auto memlet = &iedge;
                auto subset = memlet->subset();
                subset.clear();
                subset.push_back(this->loop_.indvar());
                memlet->set_subset(subset);
                memlet->set_base_type(array_type);
            }
            for (auto& oedge : access->get_parent().out_edges(*access)) {
                auto memlet = &oedge;
                auto subset = memlet->subset();
                subset.clear();
                subset.push_back(this->loop_.indvar());
                memlet->set_subset(subset);
                memlet->set_base_type(array_type);
            }
        }
    }

    // Replace container name in the loop body
    loop_.replace(symbolic::symbol(this->container_), symbolic::symbol(local_name_));

    // Cleanup
    analysis_manager.invalidate_all();

    passes::SequenceFusion sf_pass;
    passes::DeadCFGElimination dce_pass;
    bool applies = false;
    do {
        applies = false;
        applies |= dce_pass.run(builder, analysis_manager);
        applies |= sf_pass.run(builder, analysis_manager);
    } while (applies);
}

void InLocalStorage::to_json(nlohmann::json& j) const {
    std::string loop_type;
    if (dynamic_cast<structured_control_flow::For*>(&loop_)) {
        loop_type = "for";
    } else if (dynamic_cast<structured_control_flow::Map*>(&loop_)) {
        loop_type = "map";
    } else {
        throw std::runtime_error("Unsupported loop type for serialization of loop: " + loop_.indvar()->get_name());
    }
    j["subgraph"] = {{"0", {{"element_id", this->loop_.element_id()}, {"type", loop_type}}}};
    j["transformation_type"] = this->name();
    j["container"] = container_;
}

InLocalStorage InLocalStorage::from_json(builder::StructuredSDFGBuilder& builder, const nlohmann::json& desc) {
    auto loop_id = desc["subgraph"]["0"]["element_id"].get<size_t>();
    std::string container = desc["container"].get<std::string>();
    auto element = builder.find_element_by_id(loop_id);
    if (!element) {
        throw InvalidTransformationDescriptionException("Element with ID " + std::to_string(loop_id) + " not found.");
    }
    auto loop = dynamic_cast<structured_control_flow::StructuredLoop*>(element);
    if (!loop) {
        throw InvalidTransformationDescriptionException(
            "Element with ID " + std::to_string(loop_id) + " is not a structured loop."
        );
    }

    return InLocalStorage(*loop, container);
}

} // namespace transformations
} // namespace sdfg

1	#include "sdfg/transformations/in_local_storage.h"
2
3	#include <cassert>
4	#include <cstddef>
5	#include <string>
6
7	#include "sdfg/analysis/assumptions_analysis.h"
8	#include "sdfg/analysis/scope_analysis.h"
9	#include "sdfg/analysis/type_analysis.h"
10	#include "sdfg/analysis/users.h"
11	#include "sdfg/builder/structured_sdfg_builder.h"
12	#include "sdfg/data_flow/access_node.h"
13	#include "sdfg/data_flow/memlet.h"
14	#include "sdfg/passes/structured_control_flow/dead_cfg_elimination.h"
15	#include "sdfg/passes/structured_control_flow/sequence_fusion.h"
16	#include "sdfg/structured_control_flow/sequence.h"
17	#include "sdfg/structured_control_flow/structured_loop.h"
18	#include "sdfg/symbolic/symbolic.h"
19	#include "sdfg/transformations/utils.h"
20	#include "sdfg/types/array.h"
21	#include "sdfg/types/scalar.h"
22
23	namespace sdfg {
24	namespace transformations {
25
26	InLocalStorage::InLocalStorage(structured_control_flow::StructuredLoop& loop, std::string container)
27	: loop_(loop), container_(std::move(container)) {}	8✔
28
29	std::string InLocalStorage::name() const { return "InLocalStorage"; }	2✔
30
31	bool InLocalStorage::can_be_applied(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	8✔
32	auto& sdfg = builder.subject();	8✔
33	auto& body = this->loop_.root();	8✔
34
35	// Criterion: Container must exist in the SDFG
36	if (!sdfg.exists(this->container_)) {	8✔
37	return false;	1✔
38	}	1✔
39
40	// Criterion: Container must be an array type
41	auto& container_type = sdfg.type(this->container_);	7✔
42	if (container_type.type_id() != types::TypeID::Pointer && container_type.type_id() != types::TypeID::Array) {	7✔
43	return false;	1✔
44	}	1✔
45
46	// Criterion: Check if container is used in the loop
47	auto& users = analysis_manager.get<analysis::Users>();	6✔
48	analysis::UsersView body_users(users, body);	6✔
49	if (body_users.uses(this->container_).empty()) {	6✔
50	return false;	1✔
51	}	1✔
52
53	// Criterion: Container must be READ-ONLY within the loop (no writes)
54	// This is what distinguishes InLocalStorage from OutLocalStorage
55	if (!body_users.writes(this->container_).empty()) {	5✔
56	return false;	1✔
57	}	1✔
58
59	// Criterion: All accesses must have the same dimensionality
60	auto accesses = body_users.uses(this->container_);	4✔
61	auto first_access = accesses.at(0);	4✔
62	auto first_subsets = first_access->subsets();	4✔
63	if (first_subsets.empty()) {	4✔
NEW 64	return false;	×
NEW 65	}	×
66	auto& first_subset = first_subsets.at(0);	4✔
67	if (first_subset.size() == 0) {	4✔
NEW 68	return false;	×
NEW 69	}	×
70
71	for (auto* access : accesses) {	4✔
72	for (auto& subset : access->subsets()) {	4✔
73	if (subset.size() != first_subset.size()) {	4✔
NEW 74	return false;	×
NEW 75	}	×
76	}	4✔
77	}	4✔
78
79	// Store representative subset for later use
80	access_info_.representative_subset = first_subset;	4✔
81
82	// Analyze index expressions per dimension
83	// For simplicity, we require that the access pattern uses the loop indvar
84	// and the buffer size equals the iteration count
85	auto iteration_count = this->loop_.num_iterations();	4✔
86	if (iteration_count.is_null()) {	4✔
NEW 87	return false;	×
NEW 88	}	×
89
90	// For each dimension, determine if it depends on the loop indvar
91	// We support 1D localization: the dimension that uses loop indvar gets iteration_count size
92	access_info_.dimensions.clear();	4✔
93	access_info_.bases.clear();	4✔
94
95	bool found_loop_dim = false;	4✔
96	for (size_t d = 0; d < first_subset.size(); d++) {	8✔
97	auto& index_expr = first_subset.at(d);	4✔
98	auto atoms = symbolic::atoms(index_expr);	4✔
99
100	bool depends_on_indvar = false;	4✔
101	for (auto& atom : atoms) {	4✔
102	if (symbolic::eq(atom, this->loop_.indvar())) {	4✔
103	depends_on_indvar = true;	4✔
104	break;	4✔
105	}	4✔
106	}	4✔
107
108	if (depends_on_indvar) {	4✔
109	// This dimension is indexed by the loop variable
110	// Buffer dimension = iteration count
111	access_info_.dimensions.push_back(iteration_count);	4✔
112	// Base = the constant part (index_expr - indvar contribution at init)
113	auto base = symbolic::subs(index_expr, this->loop_.indvar(), this->loop_.init());	4✔
114	access_info_.bases.push_back(base);	4✔
115	found_loop_dim = true;	4✔
116	} else {	4✔
117	// This dimension is constant across loop iterations
118	// We still need to capture it for multi-dimensional buffers
NEW 119	access_info_.dimensions.push_back(symbolic::integer(1));	×
NEW 120	access_info_.bases.push_back(index_expr);	×
NEW 121	}	×
122	}	4✔
123
124	// We need at least one dimension that depends on the loop indvar
125	if (!found_loop_dim) {	4✔
NEW 126	return false;	×
NEW 127	}	×
128
129	return true;	4✔
130	}	4✔
131
132	void InLocalStorage::apply(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	1✔
133	auto& sdfg = builder.subject();	1✔
134	auto& users = analysis_manager.get<analysis::Users>();	1✔
135	auto& scope_analysis = analysis_manager.get<analysis::ScopeAnalysis>();	1✔
136
137	auto parent_node = scope_analysis.parent_scope(&loop_);	1✔
138	auto parent = dynamic_cast<structured_control_flow::Sequence*>(parent_node);	1✔
139	if (!parent) {	1✔
NEW 140	throw InvalidSDFGException("InLocalStorage: Parent of loop must be a Sequence!");	×
NEW 141	}	×
142
143	// Get type information for the original container
144	analysis::TypeAnalysis type_analysis(sdfg, &loop_, analysis_manager);	1✔
145	auto type = type_analysis.get_outer_type(container_);	1✔
146	types::Scalar scalar_type(type->primitive_type());	1✔
147
148	// Create local buffer name
149	local_name_ = "__daisy_in_local_storage_" + this->container_;	1✔
150
151	// Create the local buffer array
152	// For now, we support 1D buffer matching the iteration count
153	auto iteration_count = this->loop_.num_iterations();	1✔
154	types::Array array_type(scalar_type, iteration_count);	1✔
155	builder.add_container(local_name_, array_type);	1✔
156
157	// Create loop index variable for the copy loop
158	auto indvar_name = "__daisy_in_local_storage_" + this->loop_.indvar()->get_name();	1✔
159	types::Scalar indvar_type(sdfg.type(loop_.indvar()->get_name()).primitive_type());	1✔
160	builder.add_container(indvar_name, indvar_type);	1✔
161	auto indvar = symbolic::symbol(indvar_name);	1✔
162
163	auto init = loop_.init();	1✔
164	auto update = symbolic::subs(loop_.update(), loop_.indvar(), indvar);	1✔
165	auto condition = symbolic::subs(loop_.condition(), loop_.indvar(), indvar);	1✔
166
167	// Get access information from loop body
168	analysis::UsersView body_users(users, loop_.root());	1✔
169	auto accesses = body_users.uses(this->container_);	1✔
170	auto first_access = accesses.at(0);	1✔
171	auto first_subset = first_access->subsets().at(0);	1✔
172
173	// Insert copy loop BEFORE the main loop: A_local[i] = A[...]
174	auto& copy_loop = builder.add_for_before(*parent, loop_, indvar, condition, init, update, {}, loop_.debug_info());	1✔
175	auto& copy_body = copy_loop.root();	1✔
176	auto& copy_block = builder.add_block(copy_body);	1✔
177
178	// Read from original container
179	auto& copy_access_src = builder.add_access(copy_block, this->container_);	1✔
180	// Write to local buffer
181	auto& copy_access_dst = builder.add_access(copy_block, local_name_);	1✔
182	// Tasklet: _out = _in
183	auto& copy_tasklet = builder.add_tasklet(copy_block, data_flow::TaskletCode::assign, "_out", {"_in"});	1✔
184
185	// Input memlet: read from original array with substituted index
186	auto& copy_memlet_in =	1✔
187	builder.add_computational_memlet(copy_block, copy_access_src, copy_tasklet, "_in", first_subset, *type);	1✔
188	copy_memlet_in.replace(loop_.indvar(), indvar);	1✔
189
190	// Output memlet: write to local buffer indexed by loop variable
191	builder.add_computational_memlet(copy_block, copy_tasklet, "_out", copy_access_dst, {indvar}, array_type);	1✔
192
193	// Now update all accesses in the main loop body to use the local buffer
194	// Change subset to use just the loop indvar
195	for (auto* user : body_users.uses(this->container_)) {	1✔
196	auto element = user->element();	1✔
197	if (auto memlet = dynamic_cast<data_flow::Memlet*>(element)) {	1✔
NEW 198	auto subset = memlet->subset();	×
NEW 199	subset.clear();	×
NEW 200	subset.push_back(this->loop_.indvar());	×
NEW 201	memlet->set_subset(subset);	×
NEW 202	}	×
203	}	1✔
204
205	// Update access node edges to use local buffer type
206	for (auto* user : body_users.uses(this->container_)) {	1✔
207	auto element = user->element();	1✔
208	if (auto access = dynamic_cast<data_flow::AccessNode*>(element)) {	1✔
209	for (auto& iedge : access->get_parent().in_edges(*access)) {	1✔
NEW 210	auto memlet = &iedge;	×
NEW 211	auto subset = memlet->subset();	×
NEW 212	subset.clear();	×
NEW 213	subset.push_back(this->loop_.indvar());	×
NEW 214	memlet->set_subset(subset);	×
NEW 215	memlet->set_base_type(array_type);	×
NEW 216	}	×
217	for (auto& oedge : access->get_parent().out_edges(*access)) {	1✔
218	auto memlet = &oedge;	1✔
219	auto subset = memlet->subset();	1✔
220	subset.clear();	1✔
221	subset.push_back(this->loop_.indvar());	1✔
222	memlet->set_subset(subset);	1✔
223	memlet->set_base_type(array_type);	1✔
224	}	1✔
225	}	1✔
226	}	1✔
227
228	// Replace container name in the loop body
229	loop_.replace(symbolic::symbol(this->container_), symbolic::symbol(local_name_));	1✔
230
231	// Cleanup
232	analysis_manager.invalidate_all();	1✔
233
234	passes::SequenceFusion sf_pass;	1✔
235	passes::DeadCFGElimination dce_pass;	1✔
236	bool applies = false;	1✔
237	do {	1✔
238	applies = false;	1✔
239	applies \|= dce_pass.run(builder, analysis_manager);	1✔
240	applies \|= sf_pass.run(builder, analysis_manager);	1✔
241	} while (applies);	1✔
242	}	1✔
243
244	void InLocalStorage::to_json(nlohmann::json& j) const {	1✔
245	std::string loop_type;	1✔
246	if (dynamic_cast<structured_control_flow::For*>(&loop_)) {	1✔
247	loop_type = "for";	1✔
248	} else if (dynamic_cast<structured_control_flow::Map*>(&loop_)) {	1✔
NEW 249	loop_type = "map";	×
NEW 250	} else {	×
NEW 251	throw std::runtime_error("Unsupported loop type for serialization of loop: " + loop_.indvar()->get_name());	×
NEW 252	}	×
253	j["subgraph"] = {{"0", {{"element_id", this->loop_.element_id()}, {"type", loop_type}}}};	1✔
254	j["transformation_type"] = this->name();	1✔
255	j["container"] = container_;	1✔
256	}	1✔
257
258	InLocalStorage InLocalStorage::from_json(builder::StructuredSDFGBuilder& builder, const nlohmann::json& desc) {	1✔
259	auto loop_id = desc["subgraph"]["0"]["element_id"].get<size_t>();	1✔
260	std::string container = desc["container"].get<std::string>();	1✔
261	auto element = builder.find_element_by_id(loop_id);	1✔
262	if (!element) {	1✔
NEW 263	throw InvalidTransformationDescriptionException("Element with ID " + std::to_string(loop_id) + " not found.");	×
NEW 264	}	×
265	auto loop = dynamic_cast<structured_control_flow::StructuredLoop*>(element);	1✔
266	if (!loop) {	1✔
NEW 267	throw InvalidTransformationDescriptionException(	×
NEW 268	"Element with ID " + std::to_string(loop_id) + " is not a structured loop."	×
NEW 269	);	×
NEW 270	}	×
271
272	return InLocalStorage(*loop, container);	1✔
273	}	1✔
274
275	} // namespace transformations
276	} // namespace sdfg

daisytuner / docc / 23986340991

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