23988249051

Committed 04 Apr 2026 09:46PM UTC coverage: 64.951% (+0.1%) from 64.827%

Build # 23988249051

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #648 from daisytuner/blocking

Adds AccumulatorTile transformation and blocking test cases

Coverage Stats

327 of 421 new or added lines in 4 files covered. (77.67%)

3 existing lines in 1 file now uncovered.

29593 of 45562 relevant lines covered (64.95%)

615.06 hits per line

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

83.06

/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/loop_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;

    // Use LoopAnalysis to collect all nested loops within the target loop
    auto& loop_analysis = analysis_manager.get<analysis::LoopAnalysis>();

    // Collect all nested loops (descendants of this loop, plus this loop itself)
    std::vector<structured_control_flow::StructuredLoop*> nested_loops;
    nested_loops.push_back(&loop_);

    auto descendants = loop_analysis.descendants(&loop_);
    for (auto* desc : descendants) {
        if (auto* nested_loop = dynamic_cast<structured_control_flow::StructuredLoop*>(desc)) {
            nested_loops.push_back(nested_loop);
        }
    }

    // Analyze index expressions per dimension
    // For each dimension, check which nested loop indvars it depends on
    // and compute buffer size from their iteration counts
    access_info_.dimensions.clear();
    access_info_.bases.clear();

    // Track which loops contribute to buffer dimensions
    bool target_loop_contributes = false;
    bool descendant_loops_contribute = false;

    bool found_varying_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);

        // Check if any atom is an induction variable of a nested loop
        symbolic::Expression dim_size = symbolic::integer(1);
        symbolic::Expression dim_base = index_expr;
        bool has_loop_indvar = false;

        for (auto* nested_loop : nested_loops) {
            auto indvar = nested_loop->indvar();

            // Check if this indvar appears in the index expression
            bool found = false;
            for (auto& atom : atoms) {
                if (symbolic::eq(atom, indvar)) {
                    found = true;
                    break;
                }
            }

            if (found) {
                // Get iteration count for this loop
                auto iter_count = nested_loop->num_iterations();
                if (iter_count.is_null()) {
                    return false; // Need known iteration count
                }

                dim_size = symbolic::mul(dim_size, iter_count);

                // Base: substitute indvar with its initial value
                dim_base = symbolic::subs(dim_base, indvar, nested_loop->init());
                has_loop_indvar = true;

                // Track whether target or descendants contribute
                if (nested_loop == &loop_) {
                    target_loop_contributes = true;
                } else {
                    descendant_loops_contribute = true;
                }
            }
        }

        if (has_loop_indvar) {
            access_info_.dimensions.push_back(dim_size);
            access_info_.bases.push_back(dim_base);
            found_varying_dim = true;
        } else {
            // Constant dimension - size 1, base is the expression itself
            access_info_.dimensions.push_back(symbolic::integer(1));
            access_info_.bases.push_back(index_expr);
        }
    }

    // We need at least one varying dimension to make localization useful
    if (!found_varying_dim) {
        return false;
    }

    // Determine copy placement:
    // - copy_inside_loop = true: only descendants contribute (tiled case, per-iteration)
    // - copy_inside_loop = false: target loop contributes (simple case, copy once before)
    //   This includes the case where both target and descendants contribute.
    access_info_.copy_inside_loop = descendant_loops_contribute && !target_loop_contributes;

    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
    auto& type = sdfg.type(this->container_);
    types::Scalar scalar_type(type.primitive_type());

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

    // Collect varying dimensions and compute strides for linearization
    std::vector<size_t> varying_dims;
    std::vector<symbolic::Expression> dim_sizes;
    for (size_t d = 0; d < access_info_.dimensions.size(); d++) {
        auto dim_size = access_info_.dimensions.at(d);
        if (!symbolic::eq(dim_size, symbolic::integer(1))) {
            varying_dims.push_back(d);
            dim_sizes.push_back(dim_size);
        }
    }

    // Compute strides: stride[i] = product of dim_sizes[i+1..]
    std::vector<symbolic::Expression> strides(varying_dims.size());
    symbolic::Expression total_size = symbolic::integer(1);
    for (int i = varying_dims.size() - 1; i >= 0; i--) {
        strides[i] = total_size;
        total_size = symbolic::mul(total_size, dim_sizes[i]);
    }

    // Create the local buffer array
    types::Array buffer_type(scalar_type, total_size);
    builder.add_container(local_name_, buffer_type);

    // 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 = access_info_.representative_subset;

    // Determine where to insert copy loops based on analysis
    // - copy_inside_loop == true: insert inside loop_.root() (per-iteration, for tiled case)
    // - copy_inside_loop == false: insert before loop_ in parent (once, for simple case)
    structured_control_flow::Sequence* copy_scope;
    structured_control_flow::ControlFlowNode* insert_before_node;

    if (access_info_.copy_inside_loop) {
        // Tiled case: insert inside loop, before its children
        copy_scope = &loop_.root();
        insert_before_node = (loop_.root().size() > 0) ? &loop_.root().at(0).first : nullptr;
    } else {
        // Simple case: insert before loop in its parent
        copy_scope = parent;
        insert_before_node = &loop_;
    }

    std::vector<symbolic::Symbol> copy_indvars;
    data_flow::Subset local_subset; // Indices for the local buffer

    bool first_copy_loop = true;
    for (size_t d = 0; d < access_info_.dimensions.size(); d++) {
        auto dim_size = access_info_.dimensions.at(d);

        // Skip dimensions with size 1 (constant)
        if (symbolic::eq(dim_size, symbolic::integer(1))) {
            local_subset.push_back(symbolic::integer(0));
            continue;
        }

        // Create loop index variable for this dimension
        auto indvar_name = "__daisy_ils_" + this->container_ + "_d" + std::to_string(d);
        types::Scalar indvar_type(types::PrimitiveType::UInt64);
        builder.add_container(indvar_name, indvar_type);
        auto indvar = symbolic::symbol(indvar_name);
        copy_indvars.push_back(indvar);

        // Loop: for indvar = 0; indvar < dim_size; indvar++
        auto init = symbolic::integer(0);
        auto condition = symbolic::Lt(indvar, dim_size);
        auto update = symbolic::add(indvar, symbolic::integer(1));

        if (first_copy_loop && insert_before_node) {
            // First copy loop: insert before the existing node
            auto& copy_loop = builder.add_for_before(
                *copy_scope, *insert_before_node, indvar, condition, init, update, {}, loop_.debug_info()
            );
            copy_scope = &copy_loop.root();
            first_copy_loop = false;
        } else if (first_copy_loop) {
            // No existing node to insert before - just add the loop
            auto& copy_loop = builder.add_for(*copy_scope, indvar, condition, init, update, {}, loop_.debug_info());
            copy_scope = &copy_loop.root();
            first_copy_loop = false;
        } else {
            // Nested copy loops: add inside the current copy scope
            auto& copy_loop = builder.add_for(*copy_scope, indvar, condition, init, update, {}, loop_.debug_info());
            copy_scope = &copy_loop.root();
        }

        // Index for local buffer is the loop indvar
        local_subset.push_back(indvar);
    }

    // Create the copy block in the innermost loop
    auto& copy_block = builder.add_block(*copy_scope);

    // Build the source subset - substitute index expressions with (base + local_indvar)
    data_flow::Subset src_subset;
    size_t indvar_idx = 0;
    for (size_t d = 0; d < first_subset.size(); d++) {
        auto dim_size = access_info_.dimensions.at(d);
        if (symbolic::eq(dim_size, symbolic::integer(1))) {
            // Constant dimension - use original expression
            src_subset.push_back(first_subset.at(d));
        } else {
            // Varying dimension - base + local_indvar
            auto base = access_info_.bases.at(d);
            auto local_indvar = copy_indvars.at(indvar_idx++);
            src_subset.push_back(symbolic::add(base, local_indvar));
        }
    }

    // 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
    builder.add_computational_memlet(copy_block, copy_access_src, copy_tasklet, "_in", src_subset, type);

    // Output memlet: write to local buffer
    builder.add_computational_memlet(copy_block, copy_tasklet, "_out", copy_access_dst, local_subset, buffer_type);

    // Now update all accesses in the main loop body to use the local buffer
    // Transform the access indices from original form to local indices
    for (auto* user : body_users.uses(this->container_)) {
        auto element = user->element();
        if (auto memlet = dynamic_cast<data_flow::Memlet*>(element)) {
            auto& old_subset = memlet->subset();

            // Build new subset: subtract base from each dimension
            data_flow::Subset new_subset;
            for (size_t d = 0; d < old_subset.size(); d++) {
                auto base = access_info_.bases.at(d);
                // new_index = old_index - base
                new_subset.push_back(symbolic::sub(old_subset.at(d), base));
            }
            memlet->set_subset(new_subset);
            memlet->set_base_type(buffer_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/loop_analysis.h"
9	#include "sdfg/analysis/scope_analysis.h"
10	#include "sdfg/analysis/type_analysis.h"
11	#include "sdfg/analysis/users.h"
12	#include "sdfg/builder/structured_sdfg_builder.h"
13	#include "sdfg/data_flow/access_node.h"
14	#include "sdfg/data_flow/memlet.h"
15	#include "sdfg/passes/structured_control_flow/dead_cfg_elimination.h"
16	#include "sdfg/passes/structured_control_flow/sequence_fusion.h"
17	#include "sdfg/structured_control_flow/sequence.h"
18	#include "sdfg/structured_control_flow/structured_loop.h"
19	#include "sdfg/symbolic/symbolic.h"
20	#include "sdfg/transformations/utils.h"
21	#include "sdfg/types/array.h"
22	#include "sdfg/types/scalar.h"
23
24	namespace sdfg {
25	namespace transformations {
26
27	InLocalStorage::InLocalStorage(structured_control_flow::StructuredLoop& loop, std::string container)
28	: loop_(loop), container_(std::move(container)) {}	21✔
29
30	std::string InLocalStorage::name() const { return "InLocalStorage"; }	7✔
31
32	bool InLocalStorage::can_be_applied(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	21✔
33	auto& sdfg = builder.subject();	21✔
34	auto& body = this->loop_.root();	21✔
35
36	// Criterion: Container must exist in the SDFG
37	if (!sdfg.exists(this->container_)) {	21✔
38	return false;	1✔
39	}	1✔
40
41	// Criterion: Container must be an array type
42	auto& container_type = sdfg.type(this->container_);	20✔
43	if (container_type.type_id() != types::TypeID::Pointer && container_type.type_id() != types::TypeID::Array) {	20✔
44	return false;	1✔
45	}	1✔
46
47	// Criterion: Check if container is used in the loop
48	auto& users = analysis_manager.get<analysis::Users>();	19✔
49	analysis::UsersView body_users(users, body);	19✔
50	if (body_users.uses(this->container_).empty()) {	19✔
51	return false;	1✔
52	}	1✔
53
54	// Criterion: Container must be READ-ONLY within the loop (no writes)
55	// This is what distinguishes InLocalStorage from OutLocalStorage
56	if (!body_users.writes(this->container_).empty()) {	18✔
57	return false;	1✔
58	}	1✔
59
60	// Criterion: All accesses must have the same dimensionality
61	auto accesses = body_users.uses(this->container_);	17✔
62	auto first_access = accesses.at(0);	17✔
63	auto first_subsets = first_access->subsets();	17✔
64	if (first_subsets.empty()) {	17✔
65	return false;	×
66	}	×
67	auto& first_subset = first_subsets.at(0);	17✔
68	if (first_subset.size() == 0) {	17✔
69	return false;	×
70	}	×
71
72	for (auto* access : accesses) {	17✔
73	for (auto& subset : access->subsets()) {	17✔
74	if (subset.size() != first_subset.size()) {	17✔
75	return false;	×
76	}	×
77	}	17✔
78	}	17✔
79
80	// Store representative subset for later use
81	access_info_.representative_subset = first_subset;	17✔
82
83	// Use LoopAnalysis to collect all nested loops within the target loop
84	auto& loop_analysis = analysis_manager.get<analysis::LoopAnalysis>();	17✔
85
86	// Collect all nested loops (descendants of this loop, plus this loop itself)
87	std::vector<structured_control_flow::StructuredLoop*> nested_loops;	17✔
88	nested_loops.push_back(&loop_);	17✔
89
90	auto descendants = loop_analysis.descendants(&loop_);	17✔
91	for (auto* desc : descendants) {	34✔
92	if (auto* nested_loop = dynamic_cast<structured_control_flow::StructuredLoop*>(desc)) {	34✔
93	nested_loops.push_back(nested_loop);	34✔
94	}	34✔
95	}	34✔
96
97	// Analyze index expressions per dimension
98	// For each dimension, check which nested loop indvars it depends on
99	// and compute buffer size from their iteration counts
100	access_info_.dimensions.clear();	17✔
101	access_info_.bases.clear();	17✔
102
103	// Track which loops contribute to buffer dimensions
104	bool target_loop_contributes = false;	17✔
105	bool descendant_loops_contribute = false;	17✔
106
107	bool found_varying_dim = false;	17✔
108	for (size_t d = 0; d < first_subset.size(); d++) {	44✔
109	auto& index_expr = first_subset.at(d);	27✔
110	auto atoms = symbolic::atoms(index_expr);	27✔
111
112	// Check if any atom is an induction variable of a nested loop
113	symbolic::Expression dim_size = symbolic::integer(1);	27✔
114	symbolic::Expression dim_base = index_expr;	27✔
115	bool has_loop_indvar = false;	27✔
116
117	for (auto* nested_loop : nested_loops) {	92✔
118	auto indvar = nested_loop->indvar();	92✔
119
120	// Check if this indvar appears in the index expression
121	bool found = false;	92✔
122	for (auto& atom : atoms) {	92✔
123	if (symbolic::eq(atom, indvar)) {	92✔
124	found = true;	27✔
125	break;	27✔
126	}	27✔
127	}	92✔
128
129	if (found) {	92✔
130	// Get iteration count for this loop
131	auto iter_count = nested_loop->num_iterations();	27✔
132	if (iter_count.is_null()) {	27✔
NEW 133	return false; // Need known iteration count	×
NEW 134	}	×
135
136	dim_size = symbolic::mul(dim_size, iter_count);	27✔
137
138	// Base: substitute indvar with its initial value
139	dim_base = symbolic::subs(dim_base, indvar, nested_loop->init());	27✔
140	has_loop_indvar = true;	27✔
141
142	// Track whether target or descendants contribute
143	if (nested_loop == &loop_) {	27✔
144	target_loop_contributes = true;	5✔
145	} else {	22✔
146	descendant_loops_contribute = true;	22✔
147	}	22✔
148	}	27✔
149	}	92✔
150
151	if (has_loop_indvar) {	27✔
152	access_info_.dimensions.push_back(dim_size);	27✔
153	access_info_.bases.push_back(dim_base);	27✔
154	found_varying_dim = true;	27✔
155	} else {	27✔
156	// Constant dimension - size 1, base is the expression itself
UNCOV 157	access_info_.dimensions.push_back(symbolic::integer(1));	×
158	access_info_.bases.push_back(index_expr);	×
159	}	×
160	}	27✔
161
162	// We need at least one varying dimension to make localization useful
163	if (!found_varying_dim) {	17✔
164	return false;	×
165	}	×
166
167	// Determine copy placement:
168	// - copy_inside_loop = true: only descendants contribute (tiled case, per-iteration)
169	// - copy_inside_loop = false: target loop contributes (simple case, copy once before)
170	// This includes the case where both target and descendants contribute.
171	access_info_.copy_inside_loop = descendant_loops_contribute && !target_loop_contributes;	17✔
172
173	return true;	17✔
174	}	17✔
175
176	void InLocalStorage::apply(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	9✔
177	auto& sdfg = builder.subject();	9✔
178	auto& users = analysis_manager.get<analysis::Users>();	9✔
179	auto& scope_analysis = analysis_manager.get<analysis::ScopeAnalysis>();	9✔
180
181	auto parent_node = scope_analysis.parent_scope(&loop_);	9✔
182	auto parent = dynamic_cast<structured_control_flow::Sequence*>(parent_node);	9✔
183	if (!parent) {	9✔
184	throw InvalidSDFGException("InLocalStorage: Parent of loop must be a Sequence!");	×
185	}	×
186
187	// Get type information for the original container
188	auto& type = sdfg.type(this->container_);	9✔
189	types::Scalar scalar_type(type.primitive_type());	9✔
190
191	// Create local buffer name
192	local_name_ = "__daisy_in_local_storage_" + this->container_;	9✔
193
194	// Collect varying dimensions and compute strides for linearization
195	std::vector<size_t> varying_dims;	9✔
196	std::vector<symbolic::Expression> dim_sizes;	9✔
197	for (size_t d = 0; d < access_info_.dimensions.size(); d++) {	24✔
198	auto dim_size = access_info_.dimensions.at(d);	15✔
199	if (!symbolic::eq(dim_size, symbolic::integer(1))) {	15✔
200	varying_dims.push_back(d);	15✔
201	dim_sizes.push_back(dim_size);	15✔
202	}	15✔
203	}	15✔
204
205	// Compute strides: stride[i] = product of dim_sizes[i+1..]
206	std::vector<symbolic::Expression> strides(varying_dims.size());	9✔
207	symbolic::Expression total_size = symbolic::integer(1);	9✔
208	for (int i = varying_dims.size() - 1; i >= 0; i--) {	24✔
209	strides[i] = total_size;	15✔
210	total_size = symbolic::mul(total_size, dim_sizes[i]);	15✔
211	}	15✔
212
213	// Create the local buffer array
214	types::Array buffer_type(scalar_type, total_size);	9✔
215	builder.add_container(local_name_, buffer_type);	9✔
216
217	// Get access information from loop body
218	analysis::UsersView body_users(users, loop_.root());	9✔
219	auto accesses = body_users.uses(this->container_);	9✔
220	auto first_access = accesses.at(0);	9✔
221	auto& first_subset = access_info_.representative_subset;	9✔
222
223	// Determine where to insert copy loops based on analysis
224	// - copy_inside_loop == true: insert inside loop_.root() (per-iteration, for tiled case)
225	// - copy_inside_loop == false: insert before loop_ in parent (once, for simple case)
226	structured_control_flow::Sequence* copy_scope;	9✔
227	structured_control_flow::ControlFlowNode* insert_before_node;	9✔
228
229	if (access_info_.copy_inside_loop) {	9✔
230	// Tiled case: insert inside loop, before its children
231	copy_scope = &loop_.root();	7✔
232	insert_before_node = (loop_.root().size() > 0) ? &loop_.root().at(0).first : nullptr;	7✔
233	} else {	7✔
234	// Simple case: insert before loop in its parent
235	copy_scope = parent;	2✔
236	insert_before_node = &loop_;	2✔
237	}	2✔
238
239	std::vector<symbolic::Symbol> copy_indvars;	9✔
240	data_flow::Subset local_subset; // Indices for the local buffer	9✔
241
242	bool first_copy_loop = true;	9✔
243	for (size_t d = 0; d < access_info_.dimensions.size(); d++) {	24✔
244	auto dim_size = access_info_.dimensions.at(d);	15✔
245
246	// Skip dimensions with size 1 (constant)
247	if (symbolic::eq(dim_size, symbolic::integer(1))) {	15✔
NEW 248	local_subset.push_back(symbolic::integer(0));	×
NEW 249	continue;	×
NEW 250	}	×
251
252	// Create loop index variable for this dimension
253	auto indvar_name = "__daisy_ils_" + this->container_ + "_d" + std::to_string(d);	15✔
254	types::Scalar indvar_type(types::PrimitiveType::UInt64);	15✔
255	builder.add_container(indvar_name, indvar_type);	15✔
256	auto indvar = symbolic::symbol(indvar_name);	15✔
257	copy_indvars.push_back(indvar);	15✔
258
259	// Loop: for indvar = 0; indvar < dim_size; indvar++
260	auto init = symbolic::integer(0);	15✔
261	auto condition = symbolic::Lt(indvar, dim_size);	15✔
262	auto update = symbolic::add(indvar, symbolic::integer(1));	15✔
263
264	if (first_copy_loop && insert_before_node) {	15✔
265	// First copy loop: insert before the existing node
266	auto& copy_loop = builder.add_for_before(	9✔
267	copy_scope, insert_before_node, indvar, condition, init, update, {}, loop_.debug_info()	9✔
268	);	9✔
269	copy_scope = &copy_loop.root();	9✔
270	first_copy_loop = false;	9✔
271	} else if (first_copy_loop) {	9✔
272	// No existing node to insert before - just add the loop
NEW 273	auto& copy_loop = builder.add_for(*copy_scope, indvar, condition, init, update, {}, loop_.debug_info());	×
NEW 274	copy_scope = &copy_loop.root();	×
NEW 275	first_copy_loop = false;	×
276	} else {	6✔
277	// Nested copy loops: add inside the current copy scope
278	auto& copy_loop = builder.add_for(*copy_scope, indvar, condition, init, update, {}, loop_.debug_info());	6✔
279	copy_scope = &copy_loop.root();	6✔
280	}	6✔
281
282	// Index for local buffer is the loop indvar
283	local_subset.push_back(indvar);	15✔
284	}	15✔
285
286	// Create the copy block in the innermost loop
287	auto& copy_block = builder.add_block(*copy_scope);	9✔
288
289	// Build the source subset - substitute index expressions with (base + local_indvar)
290	data_flow::Subset src_subset;	9✔
291	size_t indvar_idx = 0;	9✔
292	for (size_t d = 0; d < first_subset.size(); d++) {	24✔
293	auto dim_size = access_info_.dimensions.at(d);	15✔
294	if (symbolic::eq(dim_size, symbolic::integer(1))) {	15✔
295	// Constant dimension - use original expression
NEW 296	src_subset.push_back(first_subset.at(d));	×
297	} else {	15✔
298	// Varying dimension - base + local_indvar
299	auto base = access_info_.bases.at(d);	15✔
300	auto local_indvar = copy_indvars.at(indvar_idx++);	15✔
301	src_subset.push_back(symbolic::add(base, local_indvar));	15✔
302	}	15✔
303	}	15✔
304
305	// Read from original container
306	auto& copy_access_src = builder.add_access(copy_block, this->container_);	9✔
307	// Write to local buffer
308	auto& copy_access_dst = builder.add_access(copy_block, local_name_);	9✔
309	// Tasklet: _out = _in
310	auto& copy_tasklet = builder.add_tasklet(copy_block, data_flow::TaskletCode::assign, "_out", {"_in"});	9✔
311
312	// Input memlet: read from original array
313	builder.add_computational_memlet(copy_block, copy_access_src, copy_tasklet, "_in", src_subset, type);	9✔
314
315	// Output memlet: write to local buffer
316	builder.add_computational_memlet(copy_block, copy_tasklet, "_out", copy_access_dst, local_subset, buffer_type);	9✔
317
318	// Now update all accesses in the main loop body to use the local buffer
319	// Transform the access indices from original form to local indices
320	for (auto* user : body_users.uses(this->container_)) {	9✔
321	auto element = user->element();	9✔
322	if (auto memlet = dynamic_cast<data_flow::Memlet*>(element)) {	9✔
NEW 323	auto& old_subset = memlet->subset();	×
324
325	// Build new subset: subtract base from each dimension
NEW 326	data_flow::Subset new_subset;	×
NEW 327	for (size_t d = 0; d < old_subset.size(); d++) {	×
NEW 328	auto base = access_info_.bases.at(d);	×
329	// new_index = old_index - base
NEW 330	new_subset.push_back(symbolic::sub(old_subset.at(d), base));	×
UNCOV 331	}	×
NEW 332	memlet->set_subset(new_subset);	×
NEW 333	memlet->set_base_type(buffer_type);	×
UNCOV 334	}	×
335	}	9✔
336
337	// Replace container name in the loop body
338	loop_.replace(symbolic::symbol(this->container_), symbolic::symbol(local_name_));	9✔
339
340	// Cleanup
341	analysis_manager.invalidate_all();	9✔
342
343	passes::SequenceFusion sf_pass;	9✔
344	passes::DeadCFGElimination dce_pass;	9✔
345	bool applies = false;	9✔
346	do {	9✔
347	applies = false;	9✔
348	applies \|= dce_pass.run(builder, analysis_manager);	9✔
349	applies \|= sf_pass.run(builder, analysis_manager);	9✔
350	} while (applies);	9✔
351	}	9✔
352
353	void InLocalStorage::to_json(nlohmann::json& j) const {	6✔
354	std::string loop_type;	6✔
355	if (dynamic_cast<structured_control_flow::For*>(&loop_)) {	6✔
356	loop_type = "for";	6✔
357	} else if (dynamic_cast<structured_control_flow::Map*>(&loop_)) {	6✔
358	loop_type = "map";	×
359	} else {	×
360	throw std::runtime_error("Unsupported loop type for serialization of loop: " + loop_.indvar()->get_name());	×
361	}	×
362	j["subgraph"] = {{"0", {{"element_id", this->loop_.element_id()}, {"type", loop_type}}}};	6✔
363	j["transformation_type"] = this->name();	6✔
364	j["container"] = container_;	6✔
365	}	6✔
366
367	InLocalStorage InLocalStorage::from_json(builder::StructuredSDFGBuilder& builder, const nlohmann::json& desc) {	1✔
368	auto loop_id = desc["subgraph"]["0"]["element_id"].get<size_t>();	1✔
369	std::string container = desc["container"].get<std::string>();	1✔
370	auto element = builder.find_element_by_id(loop_id);	1✔
371	if (!element) {	1✔
372	throw InvalidTransformationDescriptionException("Element with ID " + std::to_string(loop_id) + " not found.");	×
373	}	×
374	auto loop = dynamic_cast<structured_control_flow::StructuredLoop*>(element);	1✔
375	if (!loop) {	1✔
376	throw InvalidTransformationDescriptionException(	×
377	"Element with ID " + std::to_string(loop_id) + " is not a structured loop."	×
378	);	×
379	}	×
380
381	return InLocalStorage(*loop, container);	1✔
382	}	1✔
383
384	} // namespace transformations
385	} // namespace sdfg

daisytuner / docc / 23988249051

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