25078193631

Committed 28 Apr 2026 09:17PM UTC coverage: 64.109%. First build

Build # 25078193631

Build Type

Pull #691

github

Committed by

web-flow

Commit Message

Merge 8012a3e1f into b33be87fb

Pull Request Pull Request #691: Several minor improvements for memory layout analysis

Coverage Stats

147 of 179 new or added lines in 3 files covered. (82.12%)

30825 of 48082 relevant lines covered (64.11%)

572.85 hits per line

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

71.49

/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 {

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

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

        // Find new inner tiles for this container (created by nested loops)
        std::vector<const MemoryTile*> inner_tiles;
        for (auto& [key, tile] : tiles_) {
            if (tiles_before.count(key) > 0) continue;
            if (key.second != container) 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;
}

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

daisytuner / docc / 25078193631

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