25108636403

Committed 29 Apr 2026 12:24PM UTC coverage: 64.274%. First build

Build # 25108636403

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #692 from daisytuner/memory-layout-analysis-tests

adds extended unit tests for memory layout analysis

Coverage Stats

195 of 255 new or added lines in 2 files covered. (76.47%)

31068 of 48337 relevant lines covered (64.27%)

573.14 hits per line

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

74.48

/sdfg/src/analysis/memory_layout_analysis.cpp

#include "sdfg/analysis/memory_layout_analysis.h"

#include <optional>
#include <set>
#include <unordered_set>

#include "sdfg/analysis/assumptions_analysis.h"
#include "sdfg/data_flow/access_node.h"
#include "sdfg/structured_control_flow/block.h"
#include "sdfg/structured_control_flow/if_else.h"
#include "sdfg/structured_control_flow/sequence.h"
#include "sdfg/structured_control_flow/structured_loop.h"
#include "sdfg/structured_control_flow/while.h"
#include "sdfg/symbolic/delinearization.h"
#include "sdfg/symbolic/extreme_values.h"
#include "sdfg/symbolic/polynomials.h"

namespace sdfg {
namespace analysis {

namespace {
// Collect StructuredLoop nodes that are direct children of the given node,
// stopping at loop boundaries (does not recurse into nested loops).
void collect_direct_child_loops(
    structured_control_flow::ControlFlowNode& node, std::set<const structured_control_flow::StructuredLoop*>& result
) {
    if (auto* loop = dynamic_cast<structured_control_flow::StructuredLoop*>(&node)) {
        result.insert(loop);
        return;
    }
    if (auto* seq = dynamic_cast<structured_control_flow::Sequence*>(&node)) {
        for (size_t i = 0; i < seq->size(); i++) {
            collect_direct_child_loops(seq->at(i).first, result);
        }
    } else if (auto* ife = dynamic_cast<structured_control_flow::IfElse*>(&node)) {
        for (size_t i = 0; i < ife->size(); i++) {
            collect_direct_child_loops(ife->at(i).first, result);
        }
    } else if (auto* w = dynamic_cast<structured_control_flow::While*>(&node)) {
        collect_direct_child_loops(w->root(), result);
    }
}
} // namespace

MemoryLayoutAnalysis::MemoryLayoutAnalysis(StructuredSDFG& sdfg) : Analysis(sdfg) {}

void MemoryLayoutAnalysis::run(analysis::AnalysisManager& analysis_manager) {
    accesses_.clear();
    tiles_.clear();
    traverse(sdfg_.root(), analysis_manager);
}

void MemoryLayoutAnalysis::
    traverse(structured_control_flow::ControlFlowNode& node, analysis::AnalysisManager& analysis_manager) {
    if (auto block = dynamic_cast<structured_control_flow::Block*>(&node)) {
        process_block(*block, analysis_manager);
    } else if (auto sequence = dynamic_cast<structured_control_flow::Sequence*>(&node)) {
        for (size_t i = 0; i < sequence->size(); i++) {
            traverse(sequence->at(i).first, analysis_manager);
        }
    } else if (auto if_else = dynamic_cast<structured_control_flow::IfElse*>(&node)) {
        for (size_t i = 0; i < if_else->size(); i++) {
            traverse(if_else->at(i).first, analysis_manager);
        }
    } else if (auto while_stmt = dynamic_cast<structured_control_flow::While*>(&node)) {
        traverse(while_stmt->root(), analysis_manager);
    } else if (auto loop = dynamic_cast<structured_control_flow::StructuredLoop*>(&node)) {
        // Snapshot current memlets before traversing loop body
        std::vector<const data_flow::Memlet*> memlets_before;
        memlets_before.reserve(accesses_.size());
        for (const auto& entry : accesses_) {
            memlets_before.push_back(entry.first);
        }

        // Snapshot tile keys before traversal
        std::set<std::pair<const structured_control_flow::StructuredLoop*, std::string>> tiles_before;
        for (const auto& entry : tiles_) {
            tiles_before.insert(entry.first);
        }

        traverse(loop->root(), analysis_manager);

        // Merge layouts for containers accessed within this loop
        merge_loop_layouts(*loop, memlets_before, tiles_before, analysis_manager);
    }
    // Break, Continue, Return nodes don't contain blocks
}

void MemoryLayoutAnalysis::
    process_block(structured_control_flow::Block& block, analysis::AnalysisManager& analysis_manager) {
    auto& assumptions_analysis = analysis_manager.get<AssumptionsAnalysis>();
    auto& assumptions = assumptions_analysis.get(block);

    auto& dfg = block.dataflow();
    for (auto& memlet : dfg.edges()) {
        const auto& subset = memlet.subset();
        if (subset.empty()) {
            continue;
        }

        // Get container name from the AccessNode (either src or dst)
        std::string container_name;
        if (auto* access = dynamic_cast<const data_flow::AccessNode*>(&memlet.src())) {
            container_name = access->data();
        } else if (auto* access = dynamic_cast<const data_flow::AccessNode*>(&memlet.dst())) {
            container_name = access->data();
        } else {
            continue; // Skip memlets without AccessNode
        }

        auto& base_type = memlet.base_type();
        switch (base_type.type_id()) {
            case types::TypeID::Scalar:
            case types::TypeID::Structure:
                continue; // Skip scalars and structures
            case types::TypeID::Tensor: {
                // Tensor types already contain layout information, so we can directly store it without delinearization
                auto& tensor_type = dynamic_cast<const types::Tensor&>(memlet.base_type());

                MemoryLayout layout(tensor_type.shape(), tensor_type.strides(), tensor_type.offset());
                MemoryAccess layout_info{container_name, subset, layout, true};
                this->accesses_.emplace(&memlet, layout_info);
                continue;
            }
            case types::TypeID::Array: {
                // Arrays are c-like stack array, so we can infer a simple row-major layout without needing
                // delinearization
                auto* array_type = dynamic_cast<const types::Array*>(&memlet.base_type());
                symbolic::MultiExpression shape = {array_type->num_elements()};
                while (array_type->element_type().type_id() == types::TypeID::Array) {
                    array_type = dynamic_cast<const types::Array*>(&array_type->element_type());
                }
                if (array_type->element_type().type_id() != types::TypeID::Scalar) {
                    continue; // Skip non-scalar arrays
                }

                MemoryLayout layout(shape);
                MemoryAccess layout_info{container_name, subset, layout, true};
                this->accesses_.emplace(&memlet, layout_info);
                continue;
            }
            case types::TypeID::Pointer: {
                // For pointers, we attempt to delinearize the access pattern to infer the layout based
                // on assumptions from loop bounds
                auto* pointer_type = dynamic_cast<const types::Pointer*>(&memlet.base_type());
                if (pointer_type->pointee_type().type_id() != types::TypeID::Scalar) {
                    continue; // Skip non-scalar pointers
                }

                if (subset.size() != 1) {
                    continue; // Require full linearization
                }
                auto& linearized_expr = subset.at(0);

                auto result = symbolic::delinearize(linearized_expr, assumptions);
                if (!result.success) {
                    continue; // Delinearization failed, skip
                }

                // Delinearization returns N indices but only N-1 dimensions (from stride division)
                // The first dimension is unbounded - insert a placeholder that will be filled in by merge
                // Using a special symbol as placeholder for the first dimension
                symbolic::MultiExpression shape;
                shape.push_back(symbolic::symbol("__unbounded__"));
                for (const auto& dim : result.dimensions) {
                    shape.push_back(dim);
                }

                // Store symbolic indices and dimensions with unbounded first dimension
                // The merge phase will attempt to bound the first dimension using loop assumptions
                MemoryLayout layout(shape);
                MemoryAccess layout_info{container_name, result.indices, layout, false};
                this->accesses_.emplace(&memlet, layout_info);
                continue;
            }
            default:
                continue; // Skip unsupported types
        }
    }
}

const MemoryAccess* MemoryLayoutAnalysis::access(const data_flow::Memlet& memlet) const {
    auto layout_it = accesses_.find(&memlet);
    if (layout_it == accesses_.end()) {
        return nullptr;
    }
    return &layout_it->second;
}

void MemoryLayoutAnalysis::merge_loop_layouts(
    structured_control_flow::StructuredLoop& loop,
    const std::vector<const data_flow::Memlet*>& memlets_before,
    const std::set<std::pair<const structured_control_flow::StructuredLoop*, std::string>>& tiles_before,
    analysis::AnalysisManager& analysis_manager
) {
    // Convert memlets_before to a set for O(1) lookup
    std::unordered_set<const data_flow::Memlet*> before_set(memlets_before.begin(), memlets_before.end());

    // Group all new accesses by container
    std::unordered_map<std::string, std::vector<const data_flow::Memlet*>> all_container_groups;
    for (auto& [memlet_ptr, acc] : accesses_) {
        if (before_set.find(memlet_ptr) != before_set.end()) {
            continue;
        }
        all_container_groups[acc.container].push_back(memlet_ptr);
    }

    auto& assumptions_analysis = analysis_manager.get<AssumptionsAnalysis>();
    auto& assumptions = assumptions_analysis.get(loop.root());
    // Start with SDFG-level parameters (read-only arguments like N, M)
    // then add any additional constant symbols from loop assumptions
    symbolic::SymbolSet parameters = assumptions_analysis.parameters();
    for (auto& entry : assumptions) {
        if (symbolic::eq(entry.first, loop.indvar())) {
            continue; // Skip induction variable itself
        }

        if (entry.second.constant()) {
            parameters.insert(entry.first);
        }
    }

    // Find direct child loops of this loop (not grandchildren)
    std::set<const structured_control_flow::StructuredLoop*> direct_child_loops;
    collect_direct_child_loops(loop.root(), direct_child_loops);

    for (auto& [container, memlets] : all_container_groups) {
        if (memlets.empty()) continue;

        // Find inner tiles from direct child loops only
        std::vector<const MemoryTile*> inner_tiles;
        for (auto& [key, tile] : tiles_) {
            if (tiles_before.count(key) > 0) continue;
            if (key.second != container) continue;
            if (direct_child_loops.count(key.first) == 0) continue;
            inner_tiles.push_back(&tile);
        }

        size_t ndims = 0;
        MemoryLayout reference_layout({symbolic::one()});
        // Separate min/max index lists to avoid unnecessary symbolic min/max
        std::vector<std::vector<symbolic::Expression>> min_indices;
        std::vector<std::vector<symbolic::Expression>> max_indices;

        if (!inner_tiles.empty()) {
            // Use inner tile min/max as representative values
            // Inner tiles have already resolved inner loop variables to their bounds
            ndims = inner_tiles[0]->min_subset.size();
            reference_layout = inner_tiles[0]->layout;
            min_indices.resize(ndims);
            max_indices.resize(ndims);

            for (const auto* tile : inner_tiles) {
                if (tile->min_subset.size() != ndims) continue;
                for (size_t d = 0; d < ndims; ++d) {
                    min_indices[d].push_back(tile->min_subset[d]);
                    max_indices[d].push_back(tile->max_subset[d]);
                }
            }
        } else {
            // Use raw access indices (no inner tiles available)
            auto& first_access = accesses_.at(memlets[0]);
            auto& reference_shape = first_access.layout.shape();
            ndims = reference_shape.size();
            reference_layout = first_access.layout;
            min_indices.resize(ndims);
            max_indices.resize(ndims);

            bool consistent = true;
            for (const auto* memlet_ptr : memlets) {
                auto& acc = accesses_.at(memlet_ptr);
                auto& shape = acc.layout.shape();

                if (shape.size() != ndims) {
                    consistent = false;
                    break;
                }
                // Check inner dimensions match (all except first which may be unbounded)
                for (size_t d = 1; d < ndims; ++d) {
                    if (!symbolic::eq(shape[d], reference_shape[d])) {
                        consistent = false;
                        break;
                    }
                }
                if (!consistent) break;

                // Collect indices for each dimension
                if (acc.subset.size() != ndims) {
                    consistent = false;
                    break;
                }
                for (size_t d = 0; d < ndims; ++d) {
                    min_indices[d].push_back(acc.subset[d]);
                    max_indices[d].push_back(acc.subset[d]);
                }
            }

            if (!consistent) continue;
        }

        if (ndims == 0) continue;

        // Compute min/max bounds for each dimension
        data_flow::Subset min_subset;
        data_flow::Subset max_subset;
        bool all_bounded = true;

        for (size_t d = 0; d < ndims; ++d) {
            symbolic::Expression dim_min = SymEngine::null;
            symbolic::Expression dim_max = SymEngine::null;

            // Compute dim_min from min_indices
            for (const auto& idx : min_indices[d]) {
                auto lb = symbolic::minimum(idx, parameters, assumptions, true);
                if (lb.is_null()) {
                    lb = symbolic::minimum(idx, parameters, assumptions, false);
                }
                if (lb.is_null()) {
                    all_bounded = false;
                    break;
                }
                if (dim_min.is_null()) {
                    dim_min = lb;
                } else {
                    dim_min = symbolic::min(dim_min, lb);
                }
            }
            if (!all_bounded) break;

            // Compute dim_max from max_indices
            for (const auto& idx : max_indices[d]) {
                auto ub = symbolic::maximum(idx, parameters, assumptions, true);
                if (ub.is_null()) {
                    ub = symbolic::maximum(idx, parameters, assumptions, false);
                }
                if (ub.is_null()) {
                    all_bounded = false;
                    break;
                }
                if (dim_max.is_null()) {
                    dim_max = ub;
                } else {
                    dim_max = symbolic::max(dim_max, ub);
                }
            }
            if (!all_bounded) break;

            min_subset.push_back(symbolic::simplify(dim_min));
            max_subset.push_back(symbolic::simplify(dim_max));
        }

        if (!all_bounded) continue;

        // Store this loop's tile with the original memory layout
        tiles_.insert({{&loop, container}, MemoryTile{container, min_subset, max_subset, reference_layout, true}});
    }
}

const MemoryTile* MemoryLayoutAnalysis::
    tile(const structured_control_flow::StructuredLoop& loop, const std::string& container) const {
    auto key = std::make_pair(&loop, container);
    auto it = tiles_.find(key);
    if (it == tiles_.end()) {
        return nullptr;
    }
    return &it->second;
}

symbolic::MultiExpression MemoryTile::extents() const {
    symbolic::MultiExpression result;
    for (size_t d = 0; d < min_subset.size(); ++d) {
        result.push_back(symbolic::simplify(
            symbolic::expand(symbolic::add(symbolic::sub(max_subset[d], min_subset[d]), symbolic::one()))
        ));
    }
    return result;
}

symbolic::MultiExpression MemoryTile::extents_approx() const {
    symbolic::MultiExpression result;
    for (size_t d = 0; d < min_subset.size(); ++d) {
        result.push_back(symbolic::simplify(symbolic::expand(
            symbolic::overapproximate(symbolic::add(symbolic::sub(max_subset[d], min_subset[d]), symbolic::one()))
        )));
    }
    return result;
}

std::pair<symbolic::Expression, symbolic::Expression> MemoryTile::contiguous_range() const {
    auto& strides = layout.strides();
    auto first = layout.offset();
    auto last = layout.offset();
    for (size_t d = 0; d < min_subset.size(); ++d) {
        first = symbolic::add(first, symbolic::mul(strides[d], min_subset[d]));
        last = symbolic::add(last, symbolic::mul(strides[d], max_subset[d]));
    }
    return {symbolic::simplify(symbolic::expand(first)), symbolic::simplify(symbolic::expand(last))};
}

} // namespace analysis
} // namespace sdfg

1	#include "sdfg/analysis/memory_layout_analysis.h"
2
3	#include <optional>
4	#include <set>
5	#include <unordered_set>
6
7	#include "sdfg/analysis/assumptions_analysis.h"
8	#include "sdfg/data_flow/access_node.h"
9	#include "sdfg/structured_control_flow/block.h"
10	#include "sdfg/structured_control_flow/if_else.h"
11	#include "sdfg/structured_control_flow/sequence.h"
12	#include "sdfg/structured_control_flow/structured_loop.h"
13	#include "sdfg/structured_control_flow/while.h"
14	#include "sdfg/symbolic/delinearization.h"
15	#include "sdfg/symbolic/extreme_values.h"
16	#include "sdfg/symbolic/polynomials.h"
17
18	namespace sdfg {
19	namespace analysis {
20
21	namespace {
22	// Collect StructuredLoop nodes that are direct children of the given node,
23	// stopping at loop boundaries (does not recurse into nested loops).
24	void collect_direct_child_loops(
25	structured_control_flow::ControlFlowNode& node, std::set<const structured_control_flow::StructuredLoop*>& result
26	) {	44✔
27	if (auto* loop = dynamic_cast<structured_control_flow::StructuredLoop*>(&node)) {	44✔
28	result.insert(loop);	14✔
29	return;	14✔
30	}	14✔
31	if (auto* seq = dynamic_cast<structured_control_flow::Sequence*>(&node)) {	30✔
32	for (size_t i = 0; i < seq->size(); i++) {	44✔
33	collect_direct_child_loops(seq->at(i).first, result);	22✔
34	}	22✔
35	} else if (auto* ife = dynamic_cast<structured_control_flow::IfElse*>(&node)) {	22✔
NEW 36	for (size_t i = 0; i < ife->size(); i++) {	×
NEW 37	collect_direct_child_loops(ife->at(i).first, result);	×
NEW 38	}	×
39	} else if (auto* w = dynamic_cast<structured_control_flow::While*>(&node)) {	8✔
NEW 40	collect_direct_child_loops(w->root(), result);	×
NEW 41	}	×
42	}	30✔
43	} // namespace
44
45	MemoryLayoutAnalysis::MemoryLayoutAnalysis(StructuredSDFG& sdfg) : Analysis(sdfg) {}	8✔
46
47	void MemoryLayoutAnalysis::run(analysis::AnalysisManager& analysis_manager) {	8✔
48	accesses_.clear();	8✔
49	tiles_.clear();	8✔
50	traverse(sdfg_.root(), analysis_manager);	8✔
51	}	8✔
52
53	void MemoryLayoutAnalysis::
54	traverse(structured_control_flow::ControlFlowNode& node, analysis::AnalysisManager& analysis_manager) {	60✔
55	if (auto block = dynamic_cast<structured_control_flow::Block*>(&node)) {	60✔
56	process_block(*block, analysis_manager);	8✔
57	} else if (auto sequence = dynamic_cast<structured_control_flow::Sequence*>(&node)) {	52✔
58	for (size_t i = 0; i < sequence->size(); i++) {	60✔
59	traverse(sequence->at(i).first, analysis_manager);	30✔
60	}	30✔
61	} else if (auto if_else = dynamic_cast<structured_control_flow::IfElse*>(&node)) {	30✔
62	for (size_t i = 0; i < if_else->size(); i++) {	×
63	traverse(if_else->at(i).first, analysis_manager);	×
64	}	×
65	} else if (auto while_stmt = dynamic_cast<structured_control_flow::While*>(&node)) {	22✔
66	traverse(while_stmt->root(), analysis_manager);	×
67	} else if (auto loop = dynamic_cast<structured_control_flow::StructuredLoop*>(&node)) {	22✔
68	// Snapshot current memlets before traversing loop body
69	std::vector<const data_flow::Memlet*> memlets_before;	22✔
70	memlets_before.reserve(accesses_.size());	22✔
71	for (const auto& entry : accesses_) {	22✔
72	memlets_before.push_back(entry.first);	×
73	}	×
74
75	// Snapshot tile keys before traversal
76	std::set<std::pair<const structured_control_flow::StructuredLoop*, std::string>> tiles_before;	22✔
77	for (const auto& entry : tiles_) {	22✔
78	tiles_before.insert(entry.first);	×
79	}	×
80
81	traverse(loop->root(), analysis_manager);	22✔
82
83	// Merge layouts for containers accessed within this loop
84	merge_loop_layouts(*loop, memlets_before, tiles_before, analysis_manager);	22✔
85	}	22✔
86	// Break, Continue, Return nodes don't contain blocks
87	}	60✔
88
89	void MemoryLayoutAnalysis::
90	process_block(structured_control_flow::Block& block, analysis::AnalysisManager& analysis_manager) {	8✔
91	auto& assumptions_analysis = analysis_manager.get<AssumptionsAnalysis>();	8✔
92	auto& assumptions = assumptions_analysis.get(block);	8✔
93
94	auto& dfg = block.dataflow();	8✔
95	for (auto& memlet : dfg.edges()) {	20✔
96	const auto& subset = memlet.subset();	20✔
97	if (subset.empty()) {	20✔
98	continue;	×
99	}	×
100
101	// Get container name from the AccessNode (either src or dst)
102	std::string container_name;	20✔
103	if (auto* access = dynamic_cast<const data_flow::AccessNode*>(&memlet.src())) {	20✔
104	container_name = access->data();	12✔
105	} else if (auto* access = dynamic_cast<const data_flow::AccessNode*>(&memlet.dst())) {	12✔
106	container_name = access->data();	8✔
107	} else {	8✔
108	continue; // Skip memlets without AccessNode	×
109	}	×
110
111	auto& base_type = memlet.base_type();	20✔
112	switch (base_type.type_id()) {	20✔
113	case types::TypeID::Scalar:	×
114	case types::TypeID::Structure:	×
115	continue; // Skip scalars and structures	×
116	case types::TypeID::Tensor: {	×
117	// Tensor types already contain layout information, so we can directly store it without delinearization
118	auto& tensor_type = dynamic_cast<const types::Tensor&>(memlet.base_type());	×
119
120	MemoryLayout layout(tensor_type.shape(), tensor_type.strides(), tensor_type.offset());	×
121	MemoryAccess layout_info{container_name, subset, layout, true};	×
122	this->accesses_.emplace(&memlet, layout_info);	×
123	continue;	×
124	}	×
125	case types::TypeID::Array: {	×
126	// Arrays are c-like stack array, so we can infer a simple row-major layout without needing
127	// delinearization
128	auto* array_type = dynamic_cast<const types::Array*>(&memlet.base_type());	×
129	symbolic::MultiExpression shape = {array_type->num_elements()};	×
130	while (array_type->element_type().type_id() == types::TypeID::Array) {	×
131	array_type = dynamic_cast<const types::Array*>(&array_type->element_type());	×
132	}	×
133	if (array_type->element_type().type_id() != types::TypeID::Scalar) {	×
134	continue; // Skip non-scalar arrays	×
135	}	×
136
137	MemoryLayout layout(shape);	×
138	MemoryAccess layout_info{container_name, subset, layout, true};	×
139	this->accesses_.emplace(&memlet, layout_info);	×
140	continue;	×
141	}	×
142	case types::TypeID::Pointer: {	20✔
143	// For pointers, we attempt to delinearize the access pattern to infer the layout based
144	// on assumptions from loop bounds
145	auto* pointer_type = dynamic_cast<const types::Pointer*>(&memlet.base_type());	20✔
146	if (pointer_type->pointee_type().type_id() != types::TypeID::Scalar) {	20✔
147	continue; // Skip non-scalar pointers	×
148	}	×
149
150	if (subset.size() != 1) {	20✔
151	continue; // Require full linearization	×
152	}	×
153	auto& linearized_expr = subset.at(0);	20✔
154
155	auto result = symbolic::delinearize(linearized_expr, assumptions);	20✔
156	if (!result.success) {	20✔
157	continue; // Delinearization failed, skip	×
158	}	×
159
160	// Delinearization returns N indices but only N-1 dimensions (from stride division)
161	// The first dimension is unbounded - insert a placeholder that will be filled in by merge
162	// Using a special symbol as placeholder for the first dimension
163	symbolic::MultiExpression shape;	20✔
164	shape.push_back(symbolic::symbol("__unbounded__"));	20✔
165	for (const auto& dim : result.dimensions) {	24✔
166	shape.push_back(dim);	24✔
167	}	24✔
168
169	// Store symbolic indices and dimensions with unbounded first dimension
170	// The merge phase will attempt to bound the first dimension using loop assumptions
171	MemoryLayout layout(shape);	20✔
172	MemoryAccess layout_info{container_name, result.indices, layout, false};	20✔
173	this->accesses_.emplace(&memlet, layout_info);	20✔
174	continue;	20✔
175	}	20✔
176	default:	×
177	continue; // Skip unsupported types	×
178	}	20✔
179	}	20✔
180	}	8✔
181
182	const MemoryAccess* MemoryLayoutAnalysis::access(const data_flow::Memlet& memlet) const {	18✔
183	auto layout_it = accesses_.find(&memlet);	18✔
184	if (layout_it == accesses_.end()) {	18✔
185	return nullptr;	×
186	}	×
187	return &layout_it->second;	18✔
188	}	18✔
189
190	void MemoryLayoutAnalysis::merge_loop_layouts(
191	structured_control_flow::StructuredLoop& loop,
192	const std::vector<const data_flow::Memlet*>& memlets_before,
193	const std::set<std::pair<const structured_control_flow::StructuredLoop*, std::string>>& tiles_before,
194	analysis::AnalysisManager& analysis_manager
195	) {	22✔
196	// Convert memlets_before to a set for O(1) lookup
197	std::unordered_set<const data_flow::Memlet*> before_set(memlets_before.begin(), memlets_before.end());	22✔
198
199	// Group all new accesses by container
200	std::unordered_map<std::string, std::vector<const data_flow::Memlet*>> all_container_groups;	22✔
201	for (auto& [memlet_ptr, acc] : accesses_) {	52✔
202	if (before_set.find(memlet_ptr) != before_set.end()) {	52✔
203	continue;	×
204	}	×
205	all_container_groups[acc.container].push_back(memlet_ptr);	52✔
206	}	52✔
207
208	auto& assumptions_analysis = analysis_manager.get<AssumptionsAnalysis>();	22✔
209	auto& assumptions = assumptions_analysis.get(loop.root());	22✔
210	// Start with SDFG-level parameters (read-only arguments like N, M)
211	// then add any additional constant symbols from loop assumptions
212	symbolic::SymbolSet parameters = assumptions_analysis.parameters();	22✔
213	for (auto& entry : assumptions) {	81✔
214	if (symbolic::eq(entry.first, loop.indvar())) {	81✔
215	continue; // Skip induction variable itself	22✔
216	}	22✔
217
218	if (entry.second.constant()) {	59✔
219	parameters.insert(entry.first);	59✔
220	}	59✔
221	}	59✔
222
223	// Find direct child loops of this loop (not grandchildren)
224	std::set<const structured_control_flow::StructuredLoop*> direct_child_loops;	22✔
225	collect_direct_child_loops(loop.root(), direct_child_loops);	22✔
226
227	for (auto& [container, memlets] : all_container_groups) {	24✔
228	if (memlets.empty()) continue;	24✔
229
230	// Find inner tiles from direct child loops only
231	std::vector<const MemoryTile*> inner_tiles;	24✔
232	for (auto& [key, tile] : tiles_) {	27✔
233	if (tiles_before.count(key) > 0) continue;	27✔
234	if (key.second != container) continue;	27✔
235	if (direct_child_loops.count(key.first) == 0) continue;	23✔
236	inner_tiles.push_back(&tile);	15✔
237	}	15✔
238
239	size_t ndims = 0;	24✔
240	MemoryLayout reference_layout({symbolic::one()});	24✔
241	// Separate min/max index lists to avoid unnecessary symbolic min/max
242	std::vector<std::vector<symbolic::Expression>> min_indices;	24✔
243	std::vector<std::vector<symbolic::Expression>> max_indices;	24✔
244
245	if (!inner_tiles.empty()) {	24✔
246	// Use inner tile min/max as representative values
247	// Inner tiles have already resolved inner loop variables to their bounds
248	ndims = inner_tiles[0]->min_subset.size();	15✔
249	reference_layout = inner_tiles[0]->layout;	15✔
250	min_indices.resize(ndims);	15✔
251	max_indices.resize(ndims);	15✔
252
253	for (const auto* tile : inner_tiles) {	15✔
254	if (tile->min_subset.size() != ndims) continue;	15✔
255	for (size_t d = 0; d < ndims; ++d) {	49✔
256	min_indices[d].push_back(tile->min_subset[d]);	34✔
257	max_indices[d].push_back(tile->max_subset[d]);	34✔
258	}	34✔
259	}	15✔
260	} else {	15✔
261	// Use raw access indices (no inner tiles available)
262	auto& first_access = accesses_.at(memlets[0]);	9✔
263	auto& reference_shape = first_access.layout.shape();	9✔
264	ndims = reference_shape.size();	9✔
265	reference_layout = first_access.layout;	9✔
266	min_indices.resize(ndims);	9✔
267	max_indices.resize(ndims);	9✔
268
269	bool consistent = true;	9✔
270	for (const auto* memlet_ptr : memlets) {	20✔
271	auto& acc = accesses_.at(memlet_ptr);	20✔
272	auto& shape = acc.layout.shape();	20✔
273
274	if (shape.size() != ndims) {	20✔
275	consistent = false;	×
276	break;	×
277	}	×
278	// Check inner dimensions match (all except first which may be unbounded)
279	for (size_t d = 1; d < ndims; ++d) {	44✔
280	if (!symbolic::eq(shape[d], reference_shape[d])) {	24✔
281	consistent = false;	×
282	break;	×
283	}	×
284	}	24✔
285	if (!consistent) break;	20✔
286
287	// Collect indices for each dimension
288	if (acc.subset.size() != ndims) {	20✔
289	consistent = false;	×
290	break;	×
291	}	×
292	for (size_t d = 0; d < ndims; ++d) {	64✔
293	min_indices[d].push_back(acc.subset[d]);	44✔
294	max_indices[d].push_back(acc.subset[d]);	44✔
295	}	44✔
296	}	20✔
297
298	if (!consistent) continue;	9✔
299	}	9✔
300
301	if (ndims == 0) continue;	24✔
302
303	// Compute min/max bounds for each dimension
304	data_flow::Subset min_subset;	24✔
305	data_flow::Subset max_subset;	24✔
306	bool all_bounded = true;	24✔
307
308	for (size_t d = 0; d < ndims; ++d) {	78✔
309	symbolic::Expression dim_min = SymEngine::null;	54✔
310	symbolic::Expression dim_max = SymEngine::null;	54✔
311
312	// Compute dim_min from min_indices
313	for (const auto& idx : min_indices[d]) {	78✔
314	auto lb = symbolic::minimum(idx, parameters, assumptions, true);	78✔
315	if (lb.is_null()) {	78✔
316	lb = symbolic::minimum(idx, parameters, assumptions, false);	×
317	}	×
318	if (lb.is_null()) {	78✔
319	all_bounded = false;	×
320	break;	×
321	}	×
322	if (dim_min.is_null()) {	78✔
323	dim_min = lb;	54✔
324	} else {	54✔
325	dim_min = symbolic::min(dim_min, lb);	24✔
326	}	24✔
327	}	78✔
328	if (!all_bounded) break;	54✔
329
330	// Compute dim_max from max_indices
331	for (const auto& idx : max_indices[d]) {	78✔
332	auto ub = symbolic::maximum(idx, parameters, assumptions, true);	78✔
333	if (ub.is_null()) {	78✔
334	ub = symbolic::maximum(idx, parameters, assumptions, false);	×
335	}	×
336	if (ub.is_null()) {	78✔
337	all_bounded = false;	×
338	break;	×
339	}	×
340	if (dim_max.is_null()) {	78✔
341	dim_max = ub;	54✔
342	} else {	54✔
343	dim_max = symbolic::max(dim_max, ub);	24✔
344	}	24✔
345	}	78✔
346	if (!all_bounded) break;	54✔
347
348	min_subset.push_back(symbolic::simplify(dim_min));	54✔
349	max_subset.push_back(symbolic::simplify(dim_max));	54✔
350	}	54✔
351
352	if (!all_bounded) continue;	24✔
353
354	// Store this loop's tile with the original memory layout
355	tiles_.insert({{&loop, container}, MemoryTile{container, min_subset, max_subset, reference_layout, true}});	24✔
356	}	24✔
357	}	22✔
358
359	const MemoryTile* MemoryLayoutAnalysis::
360	tile(const structured_control_flow::StructuredLoop& loop, const std::string& container) const {	24✔
361	auto key = std::make_pair(&loop, container);	24✔
362	auto it = tiles_.find(key);	24✔
363	if (it == tiles_.end()) {	24✔
364	return nullptr;	×
365	}	×
366	return &it->second;	24✔
367	}	24✔
368
369	symbolic::MultiExpression MemoryTile::extents() const {	20✔
370	symbolic::MultiExpression result;	20✔
371	for (size_t d = 0; d < min_subset.size(); ++d) {	66✔
372	result.push_back(symbolic::simplify(	46✔
373	symbolic::expand(symbolic::add(symbolic::sub(max_subset[d], min_subset[d]), symbolic::one()))	46✔
374	));	46✔
375	}	46✔
376	return result;	20✔
377	}	20✔
378
379	symbolic::MultiExpression MemoryTile::extents_approx() const {	4✔
380	symbolic::MultiExpression result;	4✔
381	for (size_t d = 0; d < min_subset.size(); ++d) {	12✔
382	result.push_back(symbolic::simplify(symbolic::expand(	8✔
383	symbolic::overapproximate(symbolic::add(symbolic::sub(max_subset[d], min_subset[d]), symbolic::one()))	8✔
384	)));	8✔
385	}	8✔
386	return result;	4✔
387	}	4✔
388
389	std::pair<symbolic::Expression, symbolic::Expression> MemoryTile::contiguous_range() const {	20✔
390	auto& strides = layout.strides();	20✔
391	auto first = layout.offset();	20✔
392	auto last = layout.offset();	20✔
393	for (size_t d = 0; d < min_subset.size(); ++d) {	66✔
394	first = symbolic::add(first, symbolic::mul(strides[d], min_subset[d]));	46✔
395	last = symbolic::add(last, symbolic::mul(strides[d], max_subset[d]));	46✔
396	}	46✔
397	return {symbolic::simplify(symbolic::expand(first)), symbolic::simplify(symbolic::expand(last))};	20✔
398	}	20✔
399
400	} // namespace analysis
401	} // namespace sdfg

daisytuner / docc / 25108636403

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