25194337763

Committed 30 Apr 2026 11:25PM UTC coverage: 64.283% (+0.009%) from 64.274%

Build # 25194337763

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #693 from daisytuner/local-storage-generalization

unifies local storage api

Coverage Stats

277 of 358 new or added lines in 5 files covered. (77.37%)

16 existing lines in 6 files now uncovered.

30899 of 48067 relevant lines covered (64.28%)

684.61 hits per line

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

80.87

/opt/src/transformations/out_local_storage.cpp

#include "sdfg/transformations/out_local_storage.h"

#include <cstddef>
#include <string>

#include "sdfg/analysis/memory_layout_analysis.h"
#include "sdfg/analysis/scope_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/types/array.h"
#include "sdfg/types/pointer.h"
#include "sdfg/types/scalar.h"

namespace sdfg {
namespace transformations {

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

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

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

    tile_info_ = TileInfo{};

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

    auto& type = sdfg.type(this->container_);

    // Criterion: Container must be used in the loop body
    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 have writes (this is OutLocalStorage, not InLocalStorage)
    if (body_users.writes(this->container_).empty()) {
        return false;
    }

    // Determine if container is also read (read-write vs write-only)
    tile_info_.has_read = !body_users.reads(this->container_).empty();

    // Handle scalar containers: no tile needed, dimensions stay empty
    if (type.type_id() == types::TypeID::Scalar) {
        return true;
    }

    // For Array/Pointer types: use MemoryLayoutAnalysis tile API
    if (type.type_id() != types::TypeID::Pointer && type.type_id() != types::TypeID::Array) {
        return false;
    }

    auto& mla = analysis_manager.get<analysis::MemoryLayoutAnalysis>();
    auto* tile = mla.tile(loop_, this->container_);
    if (!tile) {
        return false;
    }

    // Get overapproximated extents (integer upper bounds)
    auto extents = tile->extents_approx();
    if (extents.empty()) {
        return false;
    }

    // Criterion: All extents must be provably integer
    for (size_t idx = 0; idx < extents.size(); idx++) {
        auto& ext = extents[idx];
        if (!SymEngine::is_a<SymEngine::Integer>(*ext)) {
            return false;
        }
    }

    // Store tile info
    tile_info_.dimensions = extents;
    tile_info_.bases = tile->min_subset;
    tile_info_.strides =
        std::vector<symbolic::Expression>(tile->layout.strides().begin(), tile->layout.strides().end());
    tile_info_.offset = tile->layout.offset();

    return true;
}

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

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

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

    // ========================================================================
    // SCALAR PATH: tile_info_.dimensions is empty
    // ========================================================================
    if (tile_info_.dimensions.empty()) {
        // Create scalar local buffer
        builder.add_container(local_name_, scalar_type);

        // Get the access subset from the first user (all scalar, so empty subset)
        analysis::UsersView body_users(users, loop_.root());
        auto accesses = body_users.uses(this->container_);
        auto first_access = accesses.at(0);
        auto first_subset = first_access->subsets().at(0);

        // Init block (copy from container to local) - before loop
        if (tile_info_.has_read) {
            auto& init_block = builder.add_block_before(*parent, loop_, {}, loop_.debug_info());
            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"});
            builder.add_computational_memlet(init_block, init_src, init_tasklet, "_in", first_subset, type);
            builder.add_computational_memlet(init_block, init_tasklet, "_out", init_dst, {}, scalar_type);
        }

        // Writeback block (copy from local to container) - after loop
        {
            auto& wb_block = builder.add_block_after(*parent, loop_, {}, loop_.debug_info());
            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"});
            builder.add_computational_memlet(wb_block, wb_src, wb_tasklet, "_in", {}, scalar_type);
            builder.add_computational_memlet(wb_block, wb_tasklet, "_out", wb_dst, first_subset, type);
        }

        // Rewrite body accesses to use scalar local
        for (auto* user : body_users.uses(this->container_)) {
            auto element = user->element();
            if (auto access = dynamic_cast<data_flow::AccessNode*>(element)) {
                for (auto& iedge : access->get_parent().in_edges(*access)) {
                    auto memlet = &iedge;
                    memlet->set_subset({});
                    memlet->set_base_type(scalar_type);
                }
                for (auto& oedge : access->get_parent().out_edges(*access)) {
                    auto memlet = &oedge;
                    memlet->set_subset({});
                    memlet->set_base_type(scalar_type);
                }
            }
        }

        // Replace container name in the loop body
        loop_.replace(symbolic::symbol(this->container_), symbolic::symbol(local_name_));
    }
    // ========================================================================
    // ARRAY PATH: tile_info_.dimensions is non-empty
    // ========================================================================
    else {
        // Collect varying dimensions (extent > 1) and compute buffer layout
        std::vector<size_t> varying_dims;
        std::vector<symbolic::Expression> dim_sizes;
        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))) {
                varying_dims.push_back(d);
                dim_sizes.push_back(dim_size);
            }
        }

        // Compute total buffer size
        symbolic::Expression total_size = symbolic::integer(1);
        for (auto& ds : dim_sizes) {
            total_size = symbolic::mul(total_size, ds);
        }

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

        // Helper: build linearized local index from per-dimension indices
        auto linearize = [&](const std::vector<symbolic::Symbol>& indvars) -> symbolic::Expression {
            symbolic::Expression linear_idx = symbolic::integer(0);
            symbolic::Expression stride = symbolic::integer(1);
            for (int i = indvars.size() - 1; i >= 0; i--) {
                linear_idx = symbolic::add(linear_idx, symbolic::mul(indvars[i], stride));
                stride = symbolic::mul(stride, dim_sizes[i]);
            }
            return linear_idx;
        };

        // Helper: build source subset (base[d] + copy_indvar[d]) for original container
        // For Pointer types: re-linearize to a single expression using layout strides
        // For Array types: produce multi-dimensional subset
        bool is_pointer = (type.type_id() == types::TypeID::Pointer);
        auto build_original_subset = [&](const std::vector<symbolic::Symbol>& copy_indvars) -> data_flow::Subset {
            // Build per-dimension indices: base[d] + indvar[d] for varying, base[d] for constant
            std::vector<symbolic::Expression> full_indices;
            size_t var_idx = 0;
            for (size_t d = 0; d < tile_info_.dimensions.size(); d++) {
                if (!symbolic::eq(tile_info_.dimensions.at(d), symbolic::integer(1))) {
                    full_indices.push_back(symbolic::add(tile_info_.bases.at(d), copy_indvars.at(var_idx++)));
                } else {
                    full_indices.push_back(tile_info_.bases.at(d));
                }
            }

            if (is_pointer) {
                // Linearize: offset + sum(stride[d] * index[d])
                symbolic::Expression linear = tile_info_.offset;
                for (size_t d = 0; d < full_indices.size(); d++) {
                    linear = symbolic::add(linear, symbolic::mul(tile_info_.strides.at(d), full_indices.at(d)));
                }
                return {linear};
            } else {
                // Multi-dimensional subset for Array types
                return data_flow::Subset(full_indices.begin(), full_indices.end());
            }
        };

        // ==================================================================
        // Create INIT loops (copy from container to tile) - before target loop
        // Only if the container is also read (read-write pattern)
        // ==================================================================
        if (tile_info_.has_read) {
            std::vector<symbolic::Symbol> init_indvars;
            structured_control_flow::Sequence* init_scope = parent;
            bool first_init_loop = true;

            for (size_t i = 0; i < varying_dims.size(); i++) {
                size_t d = varying_dims[i];
                auto indvar_name = "__daisy_ols_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_sizes[i]);
                auto update = symbolic::add(indvar, symbolic::integer(1));

                if (first_init_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 {
                    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"});

            auto init_src_subset = build_original_subset(init_indvars);
            data_flow::Subset init_dst_subset = {linearize(init_indvars)};

            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, buffer_type);
        }

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

            for (size_t i = 0; i < varying_dims.size(); i++) {
                size_t d = varying_dims[i];
                auto indvar_name = "__daisy_ols_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_sizes[i]);
                auto update = symbolic::add(indvar, symbolic::integer(1));

                if (first_wb_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 {
                    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"});

            data_flow::Subset wb_src_subset = {linearize(wb_indvars)};
            auto wb_dst_subset = build_original_subset(wb_indvars);

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

        // ==================================================================
        // Update accesses in the main loop to use the local buffer
        // ==================================================================
        analysis::UsersView body_users(users, loop_.root());
        auto& mla = analysis_manager.get<analysis::MemoryLayoutAnalysis>();

        for (auto* user : body_users.uses(this->container_)) {
            auto element = user->element();
            if (auto memlet = dynamic_cast<data_flow::Memlet*>(element)) {
                // Use MemoryLayoutAnalysis to get the delinearized access
                auto* access = mla.access(*memlet);
                if (access && access->subset.size() == tile_info_.dimensions.size()) {
                    // Compute local index: linearize (access[d] - base[d]) for varying dims
                    std::vector<symbolic::Expression> local_indices;
                    for (size_t d = 0; d < tile_info_.dimensions.size(); d++) {
                        if (!symbolic::eq(tile_info_.dimensions.at(d), symbolic::integer(1))) {
                            local_indices.push_back(symbolic::sub(access->subset.at(d), tile_info_.bases.at(d)));
                        }
                    }

                    // Linearize
                    symbolic::Expression linear_idx = symbolic::integer(0);
                    symbolic::Expression stride = symbolic::integer(1);
                    for (int i = local_indices.size() - 1; i >= 0; i--) {
                        linear_idx = symbolic::add(linear_idx, symbolic::mul(local_indices[i], stride));
                        stride = symbolic::mul(stride, dim_sizes[i]);
                    }

                    memlet->set_subset({linear_idx});
                    memlet->set_base_type(buffer_type);
                } else {
                    // Fallback: subtract bases from raw subset
                    auto& old_subset = memlet->subset();
                    if (old_subset.size() == tile_info_.dimensions.size()) {
                        std::vector<symbolic::Expression> local_indices;
                        for (size_t d = 0; d < tile_info_.dimensions.size(); d++) {
                            if (!symbolic::eq(tile_info_.dimensions.at(d), symbolic::integer(1))) {
                                local_indices.push_back(symbolic::sub(old_subset.at(d), tile_info_.bases.at(d)));
                            }
                        }

                        symbolic::Expression linear_idx = symbolic::integer(0);
                        symbolic::Expression stride = symbolic::integer(1);
                        for (int i = local_indices.size() - 1; i >= 0; i--) {
                            linear_idx = symbolic::add(linear_idx, symbolic::mul(local_indices[i], stride));
                            stride = symbolic::mul(stride, dim_sizes[i]);
                        }

                        memlet->set_subset({linear_idx});
                        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 OutLocalStorage::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}}},
        {"1", {{"element_id", this->access_node_.element_id()}, {"type", "access_node"}}}
    };
    j["transformation_type"] = this->name();
};

OutLocalStorage OutLocalStorage::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);

    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 OutLocalStorage(*loop, *access_node);
};

} // namespace transformations
} // namespace sdfg

1	#include "sdfg/transformations/out_local_storage.h"
2
3	#include <cstddef>
4	#include <string>
5
6	#include "sdfg/analysis/memory_layout_analysis.h"
7	#include "sdfg/analysis/scope_analysis.h"
8	#include "sdfg/analysis/users.h"
9	#include "sdfg/builder/structured_sdfg_builder.h"
10	#include "sdfg/data_flow/access_node.h"
11	#include "sdfg/data_flow/memlet.h"
12	#include "sdfg/passes/structured_control_flow/dead_cfg_elimination.h"
13	#include "sdfg/passes/structured_control_flow/sequence_fusion.h"
14	#include "sdfg/structured_control_flow/sequence.h"
15	#include "sdfg/structured_control_flow/structured_loop.h"
16	#include "sdfg/symbolic/symbolic.h"
17	#include "sdfg/types/array.h"
18	#include "sdfg/types/pointer.h"
19	#include "sdfg/types/scalar.h"
20
21	namespace sdfg {
22	namespace transformations {
23
24	OutLocalStorage::OutLocalStorage(structured_control_flow::StructuredLoop& loop, const data_flow::AccessNode& access_node)
25	: loop_(loop), access_node_(access_node), container_(access_node.data()) {};	18✔
26
27	std::string OutLocalStorage::name() const { return "OutLocalStorage"; };	5✔
28
29	bool OutLocalStorage::can_be_applied(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	16✔
30	auto& sdfg = builder.subject();	16✔
31	auto& body = this->loop_.root();	16✔
32
33	tile_info_ = TileInfo{};	16✔
34
35	// Criterion: Container must exist
36	if (!sdfg.exists(this->container_)) {	16✔
NEW 37	return false;	×
NEW 38	}	×
39
40	auto& type = sdfg.type(this->container_);	16✔
41
42	// Criterion: Container must be used in the loop body
43	auto& users = analysis_manager.get<analysis::Users>();	16✔
44	analysis::UsersView body_users(users, body);	16✔
45	if (body_users.uses(this->container_).empty()) {	16✔
46	return false;	2✔
47	}	2✔
48
49	// Criterion: Container must have writes (this is OutLocalStorage, not InLocalStorage)
50	if (body_users.writes(this->container_).empty()) {	14✔
51	return false;	1✔
52	}	1✔
53
54	// Determine if container is also read (read-write vs write-only)
55	tile_info_.has_read = !body_users.reads(this->container_).empty();	13✔
56
57	// Handle scalar containers: no tile needed, dimensions stay empty
58	if (type.type_id() == types::TypeID::Scalar) {	13✔
59	return true;	1✔
60	}	1✔
61
62	// For Array/Pointer types: use MemoryLayoutAnalysis tile API
63	if (type.type_id() != types::TypeID::Pointer && type.type_id() != types::TypeID::Array) {	12✔
NEW 64	return false;	×
UNCOV 65	}	×
66
67	auto& mla = analysis_manager.get<analysis::MemoryLayoutAnalysis>();	12✔
68	auto* tile = mla.tile(loop_, this->container_);	12✔
69	if (!tile) {	12✔
70	return false;	1✔
71	}	1✔
72
73	// Get overapproximated extents (integer upper bounds)
74	auto extents = tile->extents_approx();	11✔
75	if (extents.empty()) {	11✔
NEW 76	return false;	×
UNCOV 77	}	×
78
79	// Criterion: All extents must be provably integer
80	for (size_t idx = 0; idx < extents.size(); idx++) {	26✔
81	auto& ext = extents[idx];	15✔
82	if (!SymEngine::is_a<SymEngine::Integer>(*ext)) {	15✔
83	return false;	×
84	}	×
85	}	15✔
86
87	// Store tile info
88	tile_info_.dimensions = extents;	11✔
89	tile_info_.bases = tile->min_subset;	11✔
90	tile_info_.strides =	11✔
91	std::vector<symbolic::Expression>(tile->layout.strides().begin(), tile->layout.strides().end());	11✔
92	tile_info_.offset = tile->layout.offset();	11✔
93
94	return true;	11✔
95	}	11✔
96
97	void OutLocalStorage::apply(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	10✔
98	auto& sdfg = builder.subject();	10✔
99	auto& users = analysis_manager.get<analysis::Users>();	10✔
100	auto& scope_analysis = analysis_manager.get<analysis::ScopeAnalysis>();	10✔
101
102	auto parent_node = scope_analysis.parent_scope(&loop_);	10✔
103	auto parent = dynamic_cast<structured_control_flow::Sequence*>(parent_node);	10✔
104	if (!parent) {	10✔
105	throw InvalidSDFGException("OutLocalStorage: Parent of loop must be a Sequence!");	×
106	}	×
107
108	// Get type information
109	auto& type = sdfg.type(this->container_);	10✔
110	types::Scalar scalar_type(type.primitive_type());	10✔
111
112	// Create local buffer name
113	local_name_ = "__daisy_out_local_storage_" + this->container_;	10✔
114
115	// ========================================================================
116	// SCALAR PATH: tile_info_.dimensions is empty
117	// ========================================================================
118	if (tile_info_.dimensions.empty()) {	10✔
119	// Create scalar local buffer
120	builder.add_container(local_name_, scalar_type);	1✔
121
122	// Get the access subset from the first user (all scalar, so empty subset)
123	analysis::UsersView body_users(users, loop_.root());	1✔
124	auto accesses = body_users.uses(this->container_);	1✔
125	auto first_access = accesses.at(0);	1✔
126	auto first_subset = first_access->subsets().at(0);	1✔
127
128	// Init block (copy from container to local) - before loop
129	if (tile_info_.has_read) {	1✔
130	auto& init_block = builder.add_block_before(*parent, loop_, {}, loop_.debug_info());	1✔
131	auto& init_src = builder.add_access(init_block, this->container_);	1✔
132	auto& init_dst = builder.add_access(init_block, local_name_);	1✔
133	auto& init_tasklet = builder.add_tasklet(init_block, data_flow::TaskletCode::assign, "_out", {"_in"});	1✔
134	builder.add_computational_memlet(init_block, init_src, init_tasklet, "_in", first_subset, type);	1✔
135	builder.add_computational_memlet(init_block, init_tasklet, "_out", init_dst, {}, scalar_type);	1✔
136	}	1✔
137
138	// Writeback block (copy from local to container) - after loop
139	{	1✔
140	auto& wb_block = builder.add_block_after(*parent, loop_, {}, loop_.debug_info());	1✔
141	auto& wb_src = builder.add_access(wb_block, local_name_);	1✔
142	auto& wb_dst = builder.add_access(wb_block, this->container_);	1✔
143	auto& wb_tasklet = builder.add_tasklet(wb_block, data_flow::TaskletCode::assign, "_out", {"_in"});	1✔
144	builder.add_computational_memlet(wb_block, wb_src, wb_tasklet, "_in", {}, scalar_type);	1✔
145	builder.add_computational_memlet(wb_block, wb_tasklet, "_out", wb_dst, first_subset, type);	1✔
146	}	1✔
147
148	// Rewrite body accesses to use scalar local
149	for (auto* user : body_users.uses(this->container_)) {	2✔
150	auto element = user->element();	2✔
151	if (auto access = dynamic_cast<data_flow::AccessNode*>(element)) {	2✔
152	for (auto& iedge : access->get_parent().in_edges(*access)) {	2✔
153	auto memlet = &iedge;	1✔
154	memlet->set_subset({});	1✔
155	memlet->set_base_type(scalar_type);	1✔
156	}	1✔
157	for (auto& oedge : access->get_parent().out_edges(*access)) {	2✔
158	auto memlet = &oedge;	1✔
159	memlet->set_subset({});	1✔
160	memlet->set_base_type(scalar_type);	1✔
161	}	1✔
162	}	2✔
163	}	2✔
164
165	// Replace container name in the loop body
166	loop_.replace(symbolic::symbol(this->container_), symbolic::symbol(local_name_));	1✔
167	}	1✔
168	// ========================================================================
169	// ARRAY PATH: tile_info_.dimensions is non-empty
170	// ========================================================================
171	else {	9✔
172	// Collect varying dimensions (extent > 1) and compute buffer layout
173	std::vector<size_t> varying_dims;	9✔
174	std::vector<symbolic::Expression> dim_sizes;	9✔
175	for (size_t d = 0; d < tile_info_.dimensions.size(); d++) {	21✔
176	auto& dim_size = tile_info_.dimensions.at(d);	12✔
177	if (!symbolic::eq(dim_size, symbolic::integer(1))) {	12✔
178	varying_dims.push_back(d);	11✔
179	dim_sizes.push_back(dim_size);	11✔
180	}	11✔
181	}	12✔
182
183	// Compute total buffer size
184	symbolic::Expression total_size = symbolic::integer(1);	9✔
185	for (auto& ds : dim_sizes) {	11✔
186	total_size = symbolic::mul(total_size, ds);	11✔
187	}	11✔
188
189	// Create the local buffer
190	types::Array buffer_type(scalar_type, total_size);	9✔
191	builder.add_container(local_name_, buffer_type);	9✔
192
193	// Helper: build linearized local index from per-dimension indices
194	auto linearize = [&](const std::vector<symbolic::Symbol>& indvars) -> symbolic::Expression {	16✔
195	symbolic::Expression linear_idx = symbolic::integer(0);	16✔
196	symbolic::Expression stride = symbolic::integer(1);	16✔
197	for (int i = indvars.size() - 1; i >= 0; i--) {	36✔
198	linear_idx = symbolic::add(linear_idx, symbolic::mul(indvars[i], stride));	20✔
199	stride = symbolic::mul(stride, dim_sizes[i]);	20✔
200	}	20✔
201	return linear_idx;	16✔
202	};	16✔
203
204	// Helper: build source subset (base[d] + copy_indvar[d]) for original container
205	// For Pointer types: re-linearize to a single expression using layout strides
206	// For Array types: produce multi-dimensional subset
207	bool is_pointer = (type.type_id() == types::TypeID::Pointer);	9✔
208	auto build_original_subset = [&](const std::vector<symbolic::Symbol>& copy_indvars) -> data_flow::Subset {	16✔
209	// Build per-dimension indices: base[d] + indvar[d] for varying, base[d] for constant
210	std::vector<symbolic::Expression> full_indices;	16✔
211	size_t var_idx = 0;	16✔
212	for (size_t d = 0; d < tile_info_.dimensions.size(); d++) {	38✔
213	if (!symbolic::eq(tile_info_.dimensions.at(d), symbolic::integer(1))) {	22✔
214	full_indices.push_back(symbolic::add(tile_info_.bases.at(d), copy_indvars.at(var_idx++)));	20✔
215	} else {	20✔
216	full_indices.push_back(tile_info_.bases.at(d));	2✔
217	}	2✔
218	}	22✔
219
220	if (is_pointer) {	16✔
221	// Linearize: offset + sum(stride[d] * index[d])
222	symbolic::Expression linear = tile_info_.offset;	16✔
223	for (size_t d = 0; d < full_indices.size(); d++) {	38✔
224	linear = symbolic::add(linear, symbolic::mul(tile_info_.strides.at(d), full_indices.at(d)));	22✔
225	}	22✔
226	return {linear};	16✔
227	} else {	16✔
228	// Multi-dimensional subset for Array types
NEW 229	return data_flow::Subset(full_indices.begin(), full_indices.end());	×
NEW 230	}	×
231	};	16✔
232
233	// ==================================================================
234	// Create INIT loops (copy from container to tile) - before target loop
235	// Only if the container is also read (read-write pattern)
236	// ==================================================================
237	if (tile_info_.has_read) {	9✔
238	std::vector<symbolic::Symbol> init_indvars;	7✔
239	structured_control_flow::Sequence* init_scope = parent;	7✔
240	bool first_init_loop = true;	7✔
241
242	for (size_t i = 0; i < varying_dims.size(); i++) {	16✔
243	size_t d = varying_dims[i];	9✔
244	auto indvar_name = "__daisy_ols_init_" + this->container_ + "_d" + std::to_string(d);	9✔
245	types::Scalar indvar_type(types::PrimitiveType::UInt64);	9✔
246	builder.add_container(indvar_name, indvar_type);	9✔
247	auto indvar = symbolic::symbol(indvar_name);	9✔
248	init_indvars.push_back(indvar);	9✔
249
250	auto init = symbolic::integer(0);	9✔
251	auto condition = symbolic::Lt(indvar, dim_sizes[i]);	9✔
252	auto update = symbolic::add(indvar, symbolic::integer(1));	9✔
253
254	if (first_init_loop) {	9✔
255	auto& init_loop =	6✔
256	builder	6✔
257	.add_for_before(*init_scope, loop_, indvar, condition, init, update, {}, loop_.debug_info());	6✔
258	init_scope = &init_loop.root();	6✔
259	first_init_loop = false;	6✔
260	} else {	6✔
261	auto& init_loop =	3✔
262	builder.add_for(*init_scope, indvar, condition, init, update, {}, loop_.debug_info());	3✔
263	init_scope = &init_loop.root();	3✔
264	}	3✔
265	}	9✔
266
267	// Create init copy block
268	auto& init_block = builder.add_block(*init_scope);	7✔
269	auto& init_src = builder.add_access(init_block, this->container_);	7✔
270	auto& init_dst = builder.add_access(init_block, local_name_);	7✔
271	auto& init_tasklet = builder.add_tasklet(init_block, data_flow::TaskletCode::assign, "_out", {"_in"});	7✔
272
273	auto init_src_subset = build_original_subset(init_indvars);	7✔
274	data_flow::Subset init_dst_subset = {linearize(init_indvars)};	7✔
275
276	builder.add_computational_memlet(init_block, init_src, init_tasklet, "_in", init_src_subset, type);	7✔
277	builder.add_computational_memlet(init_block, init_tasklet, "_out", init_dst, init_dst_subset, buffer_type);	7✔
278	}	7✔
279
280	// ==================================================================
281	// Create WRITEBACK loops (copy from tile to container) - after loop
282	// ==================================================================
283	{	9✔
284	std::vector<symbolic::Symbol> wb_indvars;	9✔
285	structured_control_flow::Sequence* wb_scope = parent;	9✔
286	bool first_wb_loop = true;	9✔
287
288	for (size_t i = 0; i < varying_dims.size(); i++) {	20✔
289	size_t d = varying_dims[i];	11✔
290	auto indvar_name = "__daisy_ols_wb_" + this->container_ + "_d" + std::to_string(d);	11✔
291	types::Scalar indvar_type(types::PrimitiveType::UInt64);	11✔
292	builder.add_container(indvar_name, indvar_type);	11✔
293	auto indvar = symbolic::symbol(indvar_name);	11✔
294	wb_indvars.push_back(indvar);	11✔
295
296	auto init = symbolic::integer(0);	11✔
297	auto condition = symbolic::Lt(indvar, dim_sizes[i]);	11✔
298	auto update = symbolic::add(indvar, symbolic::integer(1));	11✔
299
300	if (first_wb_loop) {	11✔
301	auto& wb_loop =	8✔
302	builder.add_for_after(*wb_scope, loop_, indvar, condition, init, update, {}, loop_.debug_info());	8✔
303	wb_scope = &wb_loop.root();	8✔
304	first_wb_loop = false;	8✔
305	} else {	8✔
306	auto& wb_loop = builder.add_for(*wb_scope, indvar, condition, init, update, {}, loop_.debug_info());	3✔
307	wb_scope = &wb_loop.root();	3✔
308	}	3✔
309	}	11✔
310
311	// Create writeback copy block
312	auto& wb_block = builder.add_block(*wb_scope);	9✔
313	auto& wb_src = builder.add_access(wb_block, local_name_);	9✔
314	auto& wb_dst = builder.add_access(wb_block, this->container_);	9✔
315	auto& wb_tasklet = builder.add_tasklet(wb_block, data_flow::TaskletCode::assign, "_out", {"_in"});	9✔
316
317	data_flow::Subset wb_src_subset = {linearize(wb_indvars)};	9✔
318	auto wb_dst_subset = build_original_subset(wb_indvars);	9✔
319
320	builder.add_computational_memlet(wb_block, wb_src, wb_tasklet, "_in", wb_src_subset, buffer_type);	9✔
321	builder.add_computational_memlet(wb_block, wb_tasklet, "_out", wb_dst, wb_dst_subset, type);	9✔
322	}	9✔
323
324	// ==================================================================
325	// Update accesses in the main loop to use the local buffer
326	// ==================================================================
327	analysis::UsersView body_users(users, loop_.root());	9✔
328	auto& mla = analysis_manager.get<analysis::MemoryLayoutAnalysis>();	9✔
329
330	for (auto* user : body_users.uses(this->container_)) {	16✔
331	auto element = user->element();	16✔
332	if (auto memlet = dynamic_cast<data_flow::Memlet*>(element)) {	16✔
333	// Use MemoryLayoutAnalysis to get the delinearized access
NEW 334	auto* access = mla.access(*memlet);	×
NEW 335	if (access && access->subset.size() == tile_info_.dimensions.size()) {	×
336	// Compute local index: linearize (access[d] - base[d]) for varying dims
NEW 337	std::vector<symbolic::Expression> local_indices;	×
NEW 338	for (size_t d = 0; d < tile_info_.dimensions.size(); d++) {	×
NEW 339	if (!symbolic::eq(tile_info_.dimensions.at(d), symbolic::integer(1))) {	×
NEW 340	local_indices.push_back(symbolic::sub(access->subset.at(d), tile_info_.bases.at(d)));	×
NEW 341	}	×
NEW 342	}	×
343
344	// Linearize
NEW 345	symbolic::Expression linear_idx = symbolic::integer(0);	×
NEW 346	symbolic::Expression stride = symbolic::integer(1);	×
NEW 347	for (int i = local_indices.size() - 1; i >= 0; i--) {	×
NEW 348	linear_idx = symbolic::add(linear_idx, symbolic::mul(local_indices[i], stride));	×
NEW 349	stride = symbolic::mul(stride, dim_sizes[i]);	×
NEW 350	}	×
351
NEW 352	memlet->set_subset({linear_idx});	×
NEW 353	memlet->set_base_type(buffer_type);	×
NEW 354	} else {	×
355	// Fallback: subtract bases from raw subset
NEW 356	auto& old_subset = memlet->subset();	×
NEW 357	if (old_subset.size() == tile_info_.dimensions.size()) {	×
NEW 358	std::vector<symbolic::Expression> local_indices;	×
NEW 359	for (size_t d = 0; d < tile_info_.dimensions.size(); d++) {	×
NEW 360	if (!symbolic::eq(tile_info_.dimensions.at(d), symbolic::integer(1))) {	×
NEW 361	local_indices.push_back(symbolic::sub(old_subset.at(d), tile_info_.bases.at(d)));	×
NEW 362	}	×
NEW 363	}	×
364
NEW 365	symbolic::Expression linear_idx = symbolic::integer(0);	×
NEW 366	symbolic::Expression stride = symbolic::integer(1);	×
NEW 367	for (int i = local_indices.size() - 1; i >= 0; i--) {	×
NEW 368	linear_idx = symbolic::add(linear_idx, symbolic::mul(local_indices[i], stride));	×
NEW 369	stride = symbolic::mul(stride, dim_sizes[i]);	×
NEW 370	}	×
371
NEW 372	memlet->set_subset({linear_idx});	×
NEW 373	memlet->set_base_type(buffer_type);	×
NEW 374	}	×
NEW 375	}	×
UNCOV 376	}	×
377	}	16✔
378
379	// Replace container name in the loop body
380	loop_.replace(symbolic::symbol(this->container_), symbolic::symbol(local_name_));	9✔
381	}	9✔
382
383	// Cleanup
384	analysis_manager.invalidate_all();	10✔
385
386	passes::SequenceFusion sf_pass;	10✔
387	passes::DeadCFGElimination dce_pass;	10✔
388	bool applies = false;	10✔
389	do {	10✔
390	applies = false;	10✔
391	applies \|= dce_pass.run(builder, analysis_manager);	10✔
392	applies \|= sf_pass.run(builder, analysis_manager);	10✔
393	} while (applies);	10✔
394	};	10✔
395
396	void OutLocalStorage::to_json(nlohmann::json& j) const {	3✔
397	std::string loop_type;	3✔
398	if (dynamic_cast<structured_control_flow::For*>(&loop_)) {	3✔
399	loop_type = "for";	2✔
400	} else if (dynamic_cast<structured_control_flow::Map*>(&loop_)) {	2✔
401	loop_type = "map";	1✔
402	} else {	1✔
403	throw std::runtime_error("Unsupported loop type for serialization of loop: " + loop_.indvar()->get_name());	×
404	}	×
405	j["subgraph"] = {	3✔
406	{"0", {{"element_id", this->loop_.element_id()}, {"type", loop_type}}},	3✔
407	{"1", {{"element_id", this->access_node_.element_id()}, {"type", "access_node"}}}	3✔
408	};	3✔
409	j["transformation_type"] = this->name();	3✔
410	};	3✔
411
412	OutLocalStorage OutLocalStorage::from_json(builder::StructuredSDFGBuilder& builder, const nlohmann::json& desc) {	1✔
413	auto loop_id = desc["subgraph"]["0"]["element_id"].get<size_t>();	1✔
414	auto element = builder.find_element_by_id(loop_id);	1✔
415	if (!element) {	1✔
416	throw InvalidTransformationDescriptionException("Element with ID " + std::to_string(loop_id) + " not found.");	×
417	}	×
418	auto loop = dynamic_cast<structured_control_flow::StructuredLoop*>(element);	1✔
419
420	auto access_node = dynamic_cast<	1✔
421	data_flow::AccessNode*>(builder.find_element_by_id(desc.at("subgraph").at("1").at("element_id").get<size_t>()));	1✔
422	if (!access_node) {	1✔
423	throw InvalidTransformationDescriptionException(	×
424	"Access node with ID " + std::to_string(desc.at("subgraph").at("1").at("element_id").get<size_t>()) +	×
425	" not found."	×
426	);	×
427	}	×
428
429	return OutLocalStorage(loop, access_node);	1✔
430	};	1✔
431
432	} // namespace transformations
433	} // namespace sdfg

daisytuner / docc / 25194337763

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