24823673078

Committed 23 Apr 2026 07:53AM UTC coverage: 64.167%. First build

Build # 24823673078

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #689 from daisytuner/rewrite-storage-transformation-interfaces

Make *LocalStorage* transformations interfaces compatible with Transer Tuning

Coverage Stats

69 of 97 new or added lines in 6 files covered. (71.13%)

30773 of 47958 relevant lines covered (64.17%)

574.36 hits per line

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

75.76

/opt/src/transformations/accumulator_tile.cpp

#include "sdfg/transformations/accumulator_tile.h"

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

#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/for.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 {

AccumulatorTile::AccumulatorTile(structured_control_flow::StructuredLoop& loop, const data_flow::AccessNode& access_node)
    : loop_(loop), access_node_(access_node), container_(access_node.data()) {}

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

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

    // Clear any previous analysis
    tile_info_ = TileInfo{};

    // Check container exists
    if (!sdfg.exists(this->container_)) {
        return false;
    }

    // Check container is an array/pointer type
    auto& type = sdfg.type(this->container_);
    if (type.type_id() != types::TypeID::Pointer && type.type_id() != types::TypeID::Array) {
        return false;
    }

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

    // Check that container has BOTH reads and writes (accumulator pattern)
    // - has reads: uses exist that aren't writes
    // - has writes: body_users.writes() is non-empty
    bool has_write = !body_users.writes(this->container_).empty();
    bool has_read = accesses.size() > body_users.writes(this->container_).size();

    if (!has_read || !has_write) {
        return false;
    }

    // Get the first access's subset as representative
    auto first_access = accesses.at(0);
    if (first_access->subsets().empty()) {
        return false;
    }
    tile_info_.representative_subset = first_access->subsets().at(0);

    // Check all accesses have identical subsets
    for (auto* access : accesses) {
        if (access->subsets().size() != first_access->subsets().size()) {
            return false;
        }
        for (size_t i = 0; i < first_access->subsets().size(); i++) {
            auto& first_sub = tile_info_.representative_subset;
            auto& sub = access->subsets().at(i);
            if (first_sub.size() != sub.size()) {
                return false;
            }
            for (size_t j = 0; j < first_sub.size(); j++) {
                if (!symbolic::eq(first_sub.at(j), sub.at(j))) {
                    return false;
                }
            }
        }
    }

    // Get loop analysis to find nested loops
    auto& loop_analysis = analysis_manager.get<analysis::LoopAnalysis>();

    // Get all descendant For loops (NOT including target loop)
    auto descendants = loop_analysis.descendants(&loop_);

    // Collect indvars from nested For loops
    std::vector<symbolic::Symbol> inner_indvars;
    for (auto* desc : descendants) {
        if (auto* for_loop = dynamic_cast<structured_control_flow::For*>(desc)) {
            inner_indvars.push_back(for_loop->indvar());
            tile_info_.inner_loops.push_back(for_loop);
        }
    }

    if (inner_indvars.empty()) {
        // No inner loops - degenerate case, use OutLocalStorage instead
        return false;
    }

    // Analyze each dimension
    auto& subset = tile_info_.representative_subset;
    bool found_inner_loop_dim = false;

    for (size_t dim = 0; dim < subset.size(); dim++) {
        auto& index_expr = subset.at(dim);
        auto atoms = symbolic::atoms(index_expr);

        // Find which inner loop indvar, if any, appears in this dimension's index
        symbolic::Symbol found_indvar = SymEngine::null;
        structured_control_flow::For* found_loop = nullptr;

        for (size_t i = 0; i < inner_indvars.size(); i++) {
            for (auto& atom : atoms) {
                if (symbolic::eq(atom, inner_indvars[i])) {
                    found_indvar = inner_indvars[i];
                    found_loop = tile_info_.inner_loops[i];
                    break;
                }
            }
            if (found_indvar != SymEngine::null) break;
        }

        if (found_indvar != SymEngine::null && found_loop) {
            // This dimension varies with an inner loop
            // Get iteration count of that loop
            auto dim_size = found_loop->num_iterations();
            if (dim_size.is_null()) {
                return false;
            }

            // Base is index_expr with inner indvar replaced by loop init
            auto base = symbolic::subs(index_expr, found_indvar, found_loop->init());

            tile_info_.dimensions.push_back(dim_size);
            tile_info_.bases.push_back(base);
            found_inner_loop_dim = true;
        } else {
            // Constant dimension - size 1
            tile_info_.dimensions.push_back(symbolic::integer(1));
            tile_info_.bases.push_back(index_expr);
        }
    }

    // Must have at least one dimension that varies with inner loops
    if (!found_inner_loop_dim) {
        return false;
    }

    return true;
}

void AccumulatorTile::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("AccumulatorTile: Parent of loop must be a Sequence!");
    }

    // Get type information
    auto& type = sdfg.type(this->container_);
    types::Scalar scalar_type(type.primitive_type());

    // Create tile buffer name
    local_name_ = "__daisy_accumulator_tile_" + this->container_;

    // Compute total tile size
    symbolic::Expression total_size = symbolic::integer(1);
    for (auto& dim : tile_info_.dimensions) {
        if (!symbolic::eq(dim, symbolic::integer(1))) {
            total_size = symbolic::mul(total_size, dim);
        }
    }

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

    // Get representative subset
    auto& first_subset = tile_info_.representative_subset;

    // ========================================================================
    // Create INIT loops (copy from C to tile) - before target loop
    // ========================================================================
    std::vector<symbolic::Symbol> init_indvars;
    structured_control_flow::Sequence* init_scope = parent;
    bool first_init_loop = true;

    for (size_t d = 0; d < tile_info_.dimensions.size(); d++) {
        auto& dim_size = tile_info_.dimensions.at(d);
        if (symbolic::eq(dim_size, symbolic::integer(1))) {
            init_indvars.push_back(SymEngine::null);
            continue;
        }

        auto indvar_name = "__daisy_acc_init_" + 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);
        init_indvars.push_back(indvar);

        auto init = symbolic::integer(0);
        auto condition = symbolic::Lt(indvar, dim_size);
        auto update = symbolic::add(indvar, symbolic::integer(1));

        if (first_init_loop) {
            // First init loop: insert before the target loop
            auto& init_loop =
                builder.add_for_before(*init_scope, loop_, indvar, condition, init, update, {}, loop_.debug_info());
            init_scope = &init_loop.root();
            first_init_loop = false;
        } else {
            // Nested init loops: add inside the current init scope
            auto& init_loop = builder.add_for(*init_scope, indvar, condition, init, update, {}, loop_.debug_info());
            init_scope = &init_loop.root();
        }
    }

    // Create init copy block
    auto& init_block = builder.add_block(*init_scope);
    auto& init_src = builder.add_access(init_block, this->container_);
    auto& init_dst = builder.add_access(init_block, local_name_);
    auto& init_tasklet = builder.add_tasklet(init_block, data_flow::TaskletCode::assign, "_out", {"_in"});

    // Build source subset (base + init_indvar) for original container
    data_flow::Subset init_src_subset;
    for (size_t d = 0; d < tile_info_.dimensions.size(); d++) {
        if (init_indvars[d] != SymEngine::null) {
            init_src_subset.push_back(symbolic::add(tile_info_.bases[d], init_indvars[d]));
        } else {
            init_src_subset.push_back(tile_info_.bases[d]);
        }
    }

    // Compute linearized index for tile buffer
    // Linear index = sum of (indvar[d] * stride[d]) for each varying dimension
    // stride[d] = product of dimensions[d+1..n]
    std::vector<symbolic::Expression> varying_dims;
    std::vector<symbolic::Symbol> varying_indvars;
    for (size_t d = 0; d < tile_info_.dimensions.size(); d++) {
        if (init_indvars[d] != SymEngine::null) {
            varying_dims.push_back(tile_info_.dimensions[d]);
            varying_indvars.push_back(init_indvars[d]);
        }
    }

    symbolic::Expression init_linear_idx = symbolic::integer(0);
    symbolic::Expression stride = symbolic::integer(1);
    for (int d = varying_indvars.size() - 1; d >= 0; d--) {
        init_linear_idx = symbolic::add(init_linear_idx, symbolic::mul(varying_indvars[d], stride));
        stride = symbolic::mul(stride, varying_dims[d]);
    }

    data_flow::Subset init_dst_subset = {init_linear_idx};

    builder.add_computational_memlet(init_block, init_src, init_tasklet, "_in", init_src_subset, type);
    builder.add_computational_memlet(init_block, init_tasklet, "_out", init_dst, init_dst_subset, tile_type);

    // ========================================================================
    // Create WRITEBACK loops (copy from tile to C) - after target loop
    // ========================================================================
    std::vector<symbolic::Symbol> wb_indvars;
    structured_control_flow::Sequence* wb_scope = parent;
    bool first_wb_loop = true;

    for (size_t d = 0; d < tile_info_.dimensions.size(); d++) {
        auto& dim_size = tile_info_.dimensions.at(d);
        if (symbolic::eq(dim_size, symbolic::integer(1))) {
            wb_indvars.push_back(SymEngine::null);
            continue;
        }

        auto indvar_name = "__daisy_acc_wb_" + 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);
        wb_indvars.push_back(indvar);

        auto init = symbolic::integer(0);
        auto condition = symbolic::Lt(indvar, dim_size);
        auto update = symbolic::add(indvar, symbolic::integer(1));

        if (first_wb_loop) {
            // First writeback loop: insert after the target loop
            auto& wb_loop =
                builder.add_for_after(*wb_scope, loop_, indvar, condition, init, update, {}, loop_.debug_info());
            wb_scope = &wb_loop.root();
            first_wb_loop = false;
        } else {
            // Nested writeback loops: add inside the current writeback scope
            auto& wb_loop = builder.add_for(*wb_scope, indvar, condition, init, update, {}, loop_.debug_info());
            wb_scope = &wb_loop.root();
        }
    }

    // Create writeback copy block
    auto& wb_block = builder.add_block(*wb_scope);
    auto& wb_src = builder.add_access(wb_block, local_name_);
    auto& wb_dst = builder.add_access(wb_block, this->container_);
    auto& wb_tasklet = builder.add_tasklet(wb_block, data_flow::TaskletCode::assign, "_out", {"_in"});

    // Build destination subset for original container
    data_flow::Subset wb_dst_subset;
    for (size_t d = 0; d < tile_info_.dimensions.size(); d++) {
        if (wb_indvars[d] != SymEngine::null) {
            wb_dst_subset.push_back(symbolic::add(tile_info_.bases[d], wb_indvars[d]));
        } else {
            wb_dst_subset.push_back(tile_info_.bases[d]);
        }
    }

    // Compute linearized index for writeback source
    std::vector<symbolic::Expression> wb_varying_dims;
    std::vector<symbolic::Symbol> wb_varying_indvars;
    for (size_t d = 0; d < tile_info_.dimensions.size(); d++) {
        if (wb_indvars[d] != SymEngine::null) {
            wb_varying_dims.push_back(tile_info_.dimensions[d]);
            wb_varying_indvars.push_back(wb_indvars[d]);
        }
    }

    symbolic::Expression wb_linear_idx = symbolic::integer(0);
    symbolic::Expression wb_stride = symbolic::integer(1);
    for (int d = wb_varying_indvars.size() - 1; d >= 0; d--) {
        wb_linear_idx = symbolic::add(wb_linear_idx, symbolic::mul(wb_varying_indvars[d], wb_stride));
        wb_stride = symbolic::mul(wb_stride, wb_varying_dims[d]);
    }

    data_flow::Subset wb_src_subset = {wb_linear_idx};

    builder.add_computational_memlet(wb_block, wb_src, wb_tasklet, "_in", wb_src_subset, tile_type);
    builder.add_computational_memlet(wb_block, wb_tasklet, "_out", wb_dst, wb_dst_subset, type);

    // ========================================================================
    // Update accesses in the main loop to use tile
    // ========================================================================
    analysis::UsersView body_users(users, loop_.root());
    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();

            // Compute linearized index: sum of ((old_idx[d] - base[d]) * stride[d])
            // where stride includes products of dimensions after d
            symbolic::Expression linear_idx = symbolic::integer(0);
            symbolic::Expression current_stride = symbolic::integer(1);

            // Collect varying dimensions for stride calculation
            std::vector<int> varying_dim_indices;
            for (size_t d = 0; d < old_subset.size(); d++) {
                if (!symbolic::eq(tile_info_.dimensions[d], symbolic::integer(1))) {
                    varying_dim_indices.push_back(d);
                }
            }

            // Compute linearized index (row-major order)
            for (int i = varying_dim_indices.size() - 1; i >= 0; i--) {
                size_t d = varying_dim_indices[i];
                auto local_idx = symbolic::sub(old_subset.at(d), tile_info_.bases[d]);
                linear_idx = symbolic::add(linear_idx, symbolic::mul(local_idx, current_stride));
                current_stride = symbolic::mul(current_stride, tile_info_.dimensions[d]);
            }

            data_flow::Subset new_subset = {linear_idx};
            memlet->set_subset(new_subset);
            memlet->set_base_type(tile_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 AccumulatorTile::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");
    }
    j["subgraph"] = {
        {"0", {{"element_id", this->loop_.element_id()}, {"type", loop_type}}},
        {"1", {{"element_id", this->access_node_.element_id()}, {"type", "access_node"}}}
    };
    j["transformation_type"] = this->name();
}

AccumulatorTile AccumulatorTile::from_json(builder::StructuredSDFGBuilder& builder, const nlohmann::json& desc) {
    auto loop_id = desc["subgraph"]["0"]["element_id"].get<size_t>();
    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 loop.");
    }

    auto access_node = dynamic_cast<
        data_flow::AccessNode*>(builder.find_element_by_id(desc.at("subgraph").at("1").at("element_id").get<size_t>()));
    if (!access_node) {
        throw InvalidTransformationDescriptionException(
            "Access node with ID " + std::to_string(desc.at("subgraph").at("1").at("element_id").get<size_t>()) +
            " not found."
        );
    }

    return AccumulatorTile(*loop, *access_node);
}

} // namespace transformations
} // namespace sdfg

1	#include "sdfg/transformations/accumulator_tile.h"
2
3	#include <cassert>
4	#include <cstddef>
5	#include <string>
6
7	#include "sdfg/analysis/loop_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/for.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	AccumulatorTile::AccumulatorTile(structured_control_flow::StructuredLoop& loop, const data_flow::AccessNode& access_node)
28	: loop_(loop), access_node_(access_node), container_(access_node.data()) {}	8✔
29
30	std::string AccumulatorTile::name() const { return "AccumulatorTile"; }	1✔
31
32	bool AccumulatorTile::can_be_applied(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	8✔
33	auto& sdfg = builder.subject();	8✔
34	auto& body = this->loop_.root();	8✔
35
36	// Clear any previous analysis
37	tile_info_ = TileInfo{};	8✔
38
39	// Check container exists
40	if (!sdfg.exists(this->container_)) {	8✔
41	return false;	×
42	}	×
43
44	// Check container is an array/pointer type
45	auto& type = sdfg.type(this->container_);	8✔
46	if (type.type_id() != types::TypeID::Pointer && type.type_id() != types::TypeID::Array) {	8✔
47	return false;	1✔
48	}	1✔
49
50	// Check container is used in the loop
51	auto& users = analysis_manager.get<analysis::Users>();	7✔
52	analysis::UsersView body_users(users, body);	7✔
53	auto accesses = body_users.uses(this->container_);	7✔
54	if (accesses.size() == 0) {	7✔
55	return false;	1✔
56	}	1✔
57
58	// Check that container has BOTH reads and writes (accumulator pattern)
59	// - has reads: uses exist that aren't writes
60	// - has writes: body_users.writes() is non-empty
61	bool has_write = !body_users.writes(this->container_).empty();	6✔
62	bool has_read = accesses.size() > body_users.writes(this->container_).size();	6✔
63
64	if (!has_read \|\| !has_write) {	6✔
65	return false;	2✔
66	}	2✔
67
68	// Get the first access's subset as representative
69	auto first_access = accesses.at(0);	4✔
70	if (first_access->subsets().empty()) {	4✔
71	return false;	×
72	}	×
73	tile_info_.representative_subset = first_access->subsets().at(0);	4✔
74
75	// Check all accesses have identical subsets
76	for (auto* access : accesses) {	8✔
77	if (access->subsets().size() != first_access->subsets().size()) {	8✔
78	return false;	×
79	}	×
80	for (size_t i = 0; i < first_access->subsets().size(); i++) {	16✔
81	auto& first_sub = tile_info_.representative_subset;	8✔
82	auto& sub = access->subsets().at(i);	8✔
83	if (first_sub.size() != sub.size()) {	8✔
84	return false;	×
85	}	×
86	for (size_t j = 0; j < first_sub.size(); j++) {	20✔
87	if (!symbolic::eq(first_sub.at(j), sub.at(j))) {	12✔
88	return false;	×
89	}	×
90	}	12✔
91	}	8✔
92	}	8✔
93
94	// Get loop analysis to find nested loops
95	auto& loop_analysis = analysis_manager.get<analysis::LoopAnalysis>();	4✔
96
97	// Get all descendant For loops (NOT including target loop)
98	auto descendants = loop_analysis.descendants(&loop_);	4✔
99
100	// Collect indvars from nested For loops
101	std::vector<symbolic::Symbol> inner_indvars;	4✔
102	for (auto* desc : descendants) {	9✔
103	if (auto* for_loop = dynamic_cast<structured_control_flow::For*>(desc)) {	9✔
104	inner_indvars.push_back(for_loop->indvar());	9✔
105	tile_info_.inner_loops.push_back(for_loop);	9✔
106	}	9✔
107	}	9✔
108
109	if (inner_indvars.empty()) {	4✔
110	// No inner loops - degenerate case, use OutLocalStorage instead
111	return false;	1✔
112	}	1✔
113
114	// Analyze each dimension
115	auto& subset = tile_info_.representative_subset;	3✔
116	bool found_inner_loop_dim = false;	3✔
117
118	for (size_t dim = 0; dim < subset.size(); dim++) {	8✔
119	auto& index_expr = subset.at(dim);	5✔
120	auto atoms = symbolic::atoms(index_expr);	5✔
121
122	// Find which inner loop indvar, if any, appears in this dimension's index
123	symbolic::Symbol found_indvar = SymEngine::null;	5✔
124	structured_control_flow::For* found_loop = nullptr;	5✔
125
126	for (size_t i = 0; i < inner_indvars.size(); i++) {	7✔
127	for (auto& atom : atoms) {	7✔
128	if (symbolic::eq(atom, inner_indvars[i])) {	7✔
129	found_indvar = inner_indvars[i];	5✔
130	found_loop = tile_info_.inner_loops[i];	5✔
131	break;	5✔
132	}	5✔
133	}	7✔
134	if (found_indvar != SymEngine::null) break;	7✔
135	}	7✔
136
137	if (found_indvar != SymEngine::null && found_loop) {	5✔
138	// This dimension varies with an inner loop
139	// Get iteration count of that loop
140	auto dim_size = found_loop->num_iterations();	5✔
141	if (dim_size.is_null()) {	5✔
142	return false;	×
143	}	×
144
145	// Base is index_expr with inner indvar replaced by loop init
146	auto base = symbolic::subs(index_expr, found_indvar, found_loop->init());	5✔
147
148	tile_info_.dimensions.push_back(dim_size);	5✔
149	tile_info_.bases.push_back(base);	5✔
150	found_inner_loop_dim = true;	5✔
151	} else {	5✔
152	// Constant dimension - size 1
153	tile_info_.dimensions.push_back(symbolic::integer(1));	×
154	tile_info_.bases.push_back(index_expr);	×
155	}	×
156	}	5✔
157
158	// Must have at least one dimension that varies with inner loops
159	if (!found_inner_loop_dim) {	3✔
160	return false;	×
161	}	×
162
163	return true;	3✔
164	}	3✔
165
166	void AccumulatorTile::apply(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	2✔
167	auto& sdfg = builder.subject();	2✔
168	auto& users = analysis_manager.get<analysis::Users>();	2✔
169	auto& scope_analysis = analysis_manager.get<analysis::ScopeAnalysis>();	2✔
170
171	auto parent_node = scope_analysis.parent_scope(&loop_);	2✔
172	auto parent = dynamic_cast<structured_control_flow::Sequence*>(parent_node);	2✔
173	if (!parent) {	2✔
174	throw InvalidSDFGException("AccumulatorTile: Parent of loop must be a Sequence!");	×
175	}	×
176
177	// Get type information
178	auto& type = sdfg.type(this->container_);	2✔
179	types::Scalar scalar_type(type.primitive_type());	2✔
180
181	// Create tile buffer name
182	local_name_ = "__daisy_accumulator_tile_" + this->container_;	2✔
183
184	// Compute total tile size
185	symbolic::Expression total_size = symbolic::integer(1);	2✔
186	for (auto& dim : tile_info_.dimensions) {	3✔
187	if (!symbolic::eq(dim, symbolic::integer(1))) {	3✔
188	total_size = symbolic::mul(total_size, dim);	3✔
189	}	3✔
190	}	3✔
191
192	// Create the tile buffer array
193	types::Array tile_type(scalar_type, total_size);	2✔
194	builder.add_container(local_name_, tile_type);	2✔
195
196	// Get representative subset
197	auto& first_subset = tile_info_.representative_subset;	2✔
198
199	// ========================================================================
200	// Create INIT loops (copy from C to tile) - before target loop
201	// ========================================================================
202	std::vector<symbolic::Symbol> init_indvars;	2✔
203	structured_control_flow::Sequence* init_scope = parent;	2✔
204	bool first_init_loop = true;	2✔
205
206	for (size_t d = 0; d < tile_info_.dimensions.size(); d++) {	5✔
207	auto& dim_size = tile_info_.dimensions.at(d);	3✔
208	if (symbolic::eq(dim_size, symbolic::integer(1))) {	3✔
209	init_indvars.push_back(SymEngine::null);	×
210	continue;	×
211	}	×
212
213	auto indvar_name = "__daisy_acc_init_" + this->container_ + "_d" + std::to_string(d);	3✔
214	types::Scalar indvar_type(types::PrimitiveType::UInt64);	3✔
215	builder.add_container(indvar_name, indvar_type);	3✔
216	auto indvar = symbolic::symbol(indvar_name);	3✔
217	init_indvars.push_back(indvar);	3✔
218
219	auto init = symbolic::integer(0);	3✔
220	auto condition = symbolic::Lt(indvar, dim_size);	3✔
221	auto update = symbolic::add(indvar, symbolic::integer(1));	3✔
222
223	if (first_init_loop) {	3✔
224	// First init loop: insert before the target loop
225	auto& init_loop =	2✔
226	builder.add_for_before(*init_scope, loop_, indvar, condition, init, update, {}, loop_.debug_info());	2✔
227	init_scope = &init_loop.root();	2✔
228	first_init_loop = false;	2✔
229	} else {	2✔
230	// Nested init loops: add inside the current init scope
231	auto& init_loop = builder.add_for(*init_scope, indvar, condition, init, update, {}, loop_.debug_info());	1✔
232	init_scope = &init_loop.root();	1✔
233	}	1✔
234	}	3✔
235
236	// Create init copy block
237	auto& init_block = builder.add_block(*init_scope);	2✔
238	auto& init_src = builder.add_access(init_block, this->container_);	2✔
239	auto& init_dst = builder.add_access(init_block, local_name_);	2✔
240	auto& init_tasklet = builder.add_tasklet(init_block, data_flow::TaskletCode::assign, "_out", {"_in"});	2✔
241
242	// Build source subset (base + init_indvar) for original container
243	data_flow::Subset init_src_subset;	2✔
244	for (size_t d = 0; d < tile_info_.dimensions.size(); d++) {	5✔
245	if (init_indvars[d] != SymEngine::null) {	3✔
246	init_src_subset.push_back(symbolic::add(tile_info_.bases[d], init_indvars[d]));	3✔
247	} else {	3✔
248	init_src_subset.push_back(tile_info_.bases[d]);	×
249	}	×
250	}	3✔
251
252	// Compute linearized index for tile buffer
253	// Linear index = sum of (indvar[d] * stride[d]) for each varying dimension
254	// stride[d] = product of dimensions[d+1..n]
255	std::vector<symbolic::Expression> varying_dims;	2✔
256	std::vector<symbolic::Symbol> varying_indvars;	2✔
257	for (size_t d = 0; d < tile_info_.dimensions.size(); d++) {	5✔
258	if (init_indvars[d] != SymEngine::null) {	3✔
259	varying_dims.push_back(tile_info_.dimensions[d]);	3✔
260	varying_indvars.push_back(init_indvars[d]);	3✔
261	}	3✔
262	}	3✔
263
264	symbolic::Expression init_linear_idx = symbolic::integer(0);	2✔
265	symbolic::Expression stride = symbolic::integer(1);	2✔
266	for (int d = varying_indvars.size() - 1; d >= 0; d--) {	5✔
267	init_linear_idx = symbolic::add(init_linear_idx, symbolic::mul(varying_indvars[d], stride));	3✔
268	stride = symbolic::mul(stride, varying_dims[d]);	3✔
269	}	3✔
270
271	data_flow::Subset init_dst_subset = {init_linear_idx};	2✔
272
273	builder.add_computational_memlet(init_block, init_src, init_tasklet, "_in", init_src_subset, type);	2✔
274	builder.add_computational_memlet(init_block, init_tasklet, "_out", init_dst, init_dst_subset, tile_type);	2✔
275
276	// ========================================================================
277	// Create WRITEBACK loops (copy from tile to C) - after target loop
278	// ========================================================================
279	std::vector<symbolic::Symbol> wb_indvars;	2✔
280	structured_control_flow::Sequence* wb_scope = parent;	2✔
281	bool first_wb_loop = true;	2✔
282
283	for (size_t d = 0; d < tile_info_.dimensions.size(); d++) {	5✔
284	auto& dim_size = tile_info_.dimensions.at(d);	3✔
285	if (symbolic::eq(dim_size, symbolic::integer(1))) {	3✔
286	wb_indvars.push_back(SymEngine::null);	×
287	continue;	×
288	}	×
289
290	auto indvar_name = "__daisy_acc_wb_" + this->container_ + "_d" + std::to_string(d);	3✔
291	types::Scalar indvar_type(types::PrimitiveType::UInt64);	3✔
292	builder.add_container(indvar_name, indvar_type);	3✔
293	auto indvar = symbolic::symbol(indvar_name);	3✔
294	wb_indvars.push_back(indvar);	3✔
295
296	auto init = symbolic::integer(0);	3✔
297	auto condition = symbolic::Lt(indvar, dim_size);	3✔
298	auto update = symbolic::add(indvar, symbolic::integer(1));	3✔
299
300	if (first_wb_loop) {	3✔
301	// First writeback loop: insert after the target loop
302	auto& wb_loop =	2✔
303	builder.add_for_after(*wb_scope, loop_, indvar, condition, init, update, {}, loop_.debug_info());	2✔
304	wb_scope = &wb_loop.root();	2✔
305	first_wb_loop = false;	2✔
306	} else {	2✔
307	// Nested writeback loops: add inside the current writeback scope
308	auto& wb_loop = builder.add_for(*wb_scope, indvar, condition, init, update, {}, loop_.debug_info());	1✔
309	wb_scope = &wb_loop.root();	1✔
310	}	1✔
311	}	3✔
312
313	// Create writeback copy block
314	auto& wb_block = builder.add_block(*wb_scope);	2✔
315	auto& wb_src = builder.add_access(wb_block, local_name_);	2✔
316	auto& wb_dst = builder.add_access(wb_block, this->container_);	2✔
317	auto& wb_tasklet = builder.add_tasklet(wb_block, data_flow::TaskletCode::assign, "_out", {"_in"});	2✔
318
319	// Build destination subset for original container
320	data_flow::Subset wb_dst_subset;	2✔
321	for (size_t d = 0; d < tile_info_.dimensions.size(); d++) {	5✔
322	if (wb_indvars[d] != SymEngine::null) {	3✔
323	wb_dst_subset.push_back(symbolic::add(tile_info_.bases[d], wb_indvars[d]));	3✔
324	} else {	3✔
325	wb_dst_subset.push_back(tile_info_.bases[d]);	×
326	}	×
327	}	3✔
328
329	// Compute linearized index for writeback source
330	std::vector<symbolic::Expression> wb_varying_dims;	2✔
331	std::vector<symbolic::Symbol> wb_varying_indvars;	2✔
332	for (size_t d = 0; d < tile_info_.dimensions.size(); d++) {	5✔
333	if (wb_indvars[d] != SymEngine::null) {	3✔
334	wb_varying_dims.push_back(tile_info_.dimensions[d]);	3✔
335	wb_varying_indvars.push_back(wb_indvars[d]);	3✔
336	}	3✔
337	}	3✔
338
339	symbolic::Expression wb_linear_idx = symbolic::integer(0);	2✔
340	symbolic::Expression wb_stride = symbolic::integer(1);	2✔
341	for (int d = wb_varying_indvars.size() - 1; d >= 0; d--) {	5✔
342	wb_linear_idx = symbolic::add(wb_linear_idx, symbolic::mul(wb_varying_indvars[d], wb_stride));	3✔
343	wb_stride = symbolic::mul(wb_stride, wb_varying_dims[d]);	3✔
344	}	3✔
345
346	data_flow::Subset wb_src_subset = {wb_linear_idx};	2✔
347
348	builder.add_computational_memlet(wb_block, wb_src, wb_tasklet, "_in", wb_src_subset, tile_type);	2✔
349	builder.add_computational_memlet(wb_block, wb_tasklet, "_out", wb_dst, wb_dst_subset, type);	2✔
350
351	// ========================================================================
352	// Update accesses in the main loop to use tile
353	// ========================================================================
354	analysis::UsersView body_users(users, loop_.root());	2✔
355	for (auto* user : body_users.uses(this->container_)) {	4✔
356	auto element = user->element();	4✔
357	if (auto memlet = dynamic_cast<data_flow::Memlet*>(element)) {	4✔
358	auto& old_subset = memlet->subset();	×
359
360	// Compute linearized index: sum of ((old_idx[d] - base[d]) * stride[d])
361	// where stride includes products of dimensions after d
362	symbolic::Expression linear_idx = symbolic::integer(0);	×
363	symbolic::Expression current_stride = symbolic::integer(1);	×
364
365	// Collect varying dimensions for stride calculation
366	std::vector<int> varying_dim_indices;	×
367	for (size_t d = 0; d < old_subset.size(); d++) {	×
368	if (!symbolic::eq(tile_info_.dimensions[d], symbolic::integer(1))) {	×
369	varying_dim_indices.push_back(d);	×
370	}	×
371	}	×
372
373	// Compute linearized index (row-major order)
374	for (int i = varying_dim_indices.size() - 1; i >= 0; i--) {	×
375	size_t d = varying_dim_indices[i];	×
376	auto local_idx = symbolic::sub(old_subset.at(d), tile_info_.bases[d]);	×
377	linear_idx = symbolic::add(linear_idx, symbolic::mul(local_idx, current_stride));	×
378	current_stride = symbolic::mul(current_stride, tile_info_.dimensions[d]);	×
379	}	×
380
381	data_flow::Subset new_subset = {linear_idx};	×
382	memlet->set_subset(new_subset);	×
383	memlet->set_base_type(tile_type);	×
384	}	×
385	}	4✔
386
387	// Replace container name in the loop body
388	loop_.replace(symbolic::symbol(this->container_), symbolic::symbol(local_name_));	2✔
389
390	// Cleanup
391	analysis_manager.invalidate_all();	2✔
392
393	passes::SequenceFusion sf_pass;	2✔
394	passes::DeadCFGElimination dce_pass;	2✔
395	bool applies = false;	2✔
396	do {	2✔
397	applies = false;	2✔
398	applies \|= dce_pass.run(builder, analysis_manager);	2✔
399	applies \|= sf_pass.run(builder, analysis_manager);	2✔
400	} while (applies);	2✔
401	}	2✔
402
403	void AccumulatorTile::to_json(nlohmann::json& j) const {	1✔
404	std::string loop_type;	1✔
405	if (dynamic_cast<structured_control_flow::For*>(&loop_)) {	1✔
406	loop_type = "for";	1✔
407	} else if (dynamic_cast<structured_control_flow::Map*>(&loop_)) {	1✔
408	loop_type = "map";	×
409	} else {	×
410	throw std::runtime_error("Unsupported loop type for serialization");	×
411	}	×
412	j["subgraph"] = {	1✔
413	{"0", {{"element_id", this->loop_.element_id()}, {"type", loop_type}}},	1✔
414	{"1", {{"element_id", this->access_node_.element_id()}, {"type", "access_node"}}}	1✔
415	};	1✔
416	j["transformation_type"] = this->name();	1✔
417	}	1✔
418
419	AccumulatorTile AccumulatorTile::from_json(builder::StructuredSDFGBuilder& builder, const nlohmann::json& desc) {	×
420	auto loop_id = desc["subgraph"]["0"]["element_id"].get<size_t>();	×
421	auto element = builder.find_element_by_id(loop_id);	×
422	if (!element) {	×
423	throw InvalidTransformationDescriptionException("Element with ID " + std::to_string(loop_id) + " not found.");	×
424	}	×
425	auto loop = dynamic_cast<structured_control_flow::StructuredLoop*>(element);	×
426	if (!loop) {	×
427	throw InvalidTransformationDescriptionException("Element with ID " + std::to_string(loop_id) + " is not a loop.");	×
428	}	×
429
NEW 430	auto access_node = dynamic_cast<	×
NEW 431	data_flow::AccessNode*>(builder.find_element_by_id(desc.at("subgraph").at("1").at("element_id").get<size_t>()));	×
NEW 432	if (!access_node) {	×
NEW 433	throw InvalidTransformationDescriptionException(	×
NEW 434	"Access node with ID " + std::to_string(desc.at("subgraph").at("1").at("element_id").get<size_t>()) +	×
NEW 435	" not found."	×
NEW 436	);	×
NEW 437	}	×
438
NEW 439	return AccumulatorTile(loop, access_node);	×
440	}	×
441
442	} // namespace transformations
443	} // namespace sdfg

daisytuner / docc / 24823673078

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