23994483481

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

Build # 23994483481

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #648 from daisytuner/blocking

Adds AccumulatorTile transformation and blocking test cases

Run Details

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

74.65

/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, std::string container)
    : loop_(loop), container_(container) {}

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}}}};
    j["transformation_type"] = this->name();
    j["container"] = container_;
}

AccumulatorTile AccumulatorTile::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 loop.");
    }
    return AccumulatorTile(*loop, container);
}

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

daisytuner / docc / 23994483481

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