24639587487

Committed 19 Apr 2026 09:30PM UTC coverage: 63.96%. First build

Build # 24639587487

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #687 from daisytuner/assumptions-analysis

Removes deprecated assumptions analysis functions

Coverage Stats

710 of 1128 new or added lines in 18 files covered. (62.94%)

30647 of 47916 relevant lines covered (63.96%)

574.05 hits per line

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

67.84

/sdfg/src/analysis/memory_layout_analysis.cpp

#include "sdfg/analysis/memory_layout_analysis.h"

#include <iostream>
#include <optional>
#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/polynomials.h"

namespace sdfg {
namespace analysis {

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

void MemoryLayoutAnalysis::run(analysis::AnalysisManager& analysis_manager) {
    layouts_.clear();
    loop_layouts_.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(layouts_.size());
        for (const auto& entry : layouts_) {
            memlets_before.push_back(entry.first);
        }

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

        // Merge layouts for containers accessed within this loop
        merge_loop_layouts(*loop, memlets_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->layouts_.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->layouts_.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) {
                    std::cerr << "[DEBUG] Skipping non-scalar pointer for " << container_name << std::endl;
                    continue; // Skip non-scalar pointers
                }

                if (subset.size() != 1) {
                    std::cerr << "[DEBUG] Skipping " << container_name << ": subset.size() = " << subset.size()
                              << " (requires 1)" << std::endl;
                    continue; // Require full linearization
                }
                auto& linearized_expr = subset.at(0);

                std::cerr << "[DEBUG] Delinearizing " << container_name << ": " << *linearized_expr << std::endl;
                std::cerr << "[DEBUG] Assumptions available:" << std::endl;
                for (const auto& [sym, assump] : assumptions) {
                    for (const auto& bound : assump.upper_bounds()) {
                        std::cerr << "  " << *sym << ": upper bound " << *bound << std::endl;
                    }
                    for (const auto& bound : assump.lower_bounds()) {
                        std::cerr << "  " << *sym << ": lower bound " << *bound << std::endl;
                    }
                }

                auto result = symbolic::delinearize(linearized_expr, assumptions);
                if (!result.success) {
                    std::cerr << "[DEBUG] Delinearization FAILED for " << container_name << std::endl;
                    continue; // Delinearization failed, skip
                }

                std::cerr << "[DEBUG] Delinearization SUCCESS for " << container_name << std::endl;
                std::cerr << "[DEBUG]   Indices: ";
                for (const auto& idx : result.indices) {
                    std::cerr << *idx << " ";
                }
                std::cerr << std::endl;
                std::cerr << "[DEBUG]   Dimensions: ";
                for (const auto& dim : result.dimensions) {
                    std::cerr << *dim << " ";
                }
                std::cerr << std::endl;
                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("__first_dim_placeholder__"));
                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->layouts_.emplace(&memlet, layout_info);
                continue;
            }
            default:
                continue; // Skip unsupported types
        }
    }
}

const MemoryAccess* MemoryLayoutAnalysis::get(const data_flow::Memlet& memlet) const {
    auto layout_it = layouts_.find(&memlet);
    if (layout_it == layouts_.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,
    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 newly added unbounded layouts by container
    std::unordered_map<std::string, std::vector<const data_flow::Memlet*>> container_groups;
    for (auto& [memlet_ptr, access] : layouts_) {
        if (before_set.find(memlet_ptr) != before_set.end()) {
            continue; // Skip memlets that existed before this loop
        }
        if (access.first_dim_bounded) {
            continue; // Skip already bounded layouts
        }
        container_groups[access.container].push_back(memlet_ptr);
    }

    // Get assumptions at loop body level (includes loop variable bounds)
    // The loop's indvar bounds are only available inside the loop body, not at the loop node itself
    auto& assumptions_analysis = analysis_manager.get<AssumptionsAnalysis>();
    auto& assumptions = assumptions_analysis.get(loop.root());

    // Process each container group
    for (auto& [container, memlets] : container_groups) {
        if (memlets.empty()) continue;

        // Collect all inner dimensions and first-dim indices for consistency check
        auto& first_access = layouts_.at(memlets[0]);
        auto& reference_shape = first_access.layout.shape();
        if (reference_shape.empty()) continue;

        // Check consistency of inner dimensions across all accesses
        bool consistent = true;
        std::vector<symbolic::Expression> first_dim_indices;
        first_dim_indices.reserve(memlets.size());

        for (const auto* memlet_ptr : memlets) {
            auto& access = layouts_.at(memlet_ptr);
            auto& shape = access.layout.shape();

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

            // Collect first-dimension index
            if (!access.subset.empty()) {
                first_dim_indices.push_back(access.subset[0]);
            }
        }

        if (!consistent || first_dim_indices.empty()) {
            continue; // Skip containers with inconsistent layouts
        }

        // Attempt to bound first dimension from collected indices
        // Find the maximum offset across all first-dim indices
        std::optional<symbolic::Expression> max_bound;

        for (const auto& first_idx : first_dim_indices) {
            // Extract symbols from the index expression
            auto syms = symbolic::atoms(first_idx);
            if (syms.size() != 1) {
                // Can't handle multi-symbol or constant-only indices at this level
                // Skip and let outer loop try
                continue;
            }
            auto sym = *syms.begin();

            // Check if we have assumptions for this symbol
            if (assumptions.find(sym) == assumptions.end()) {
                continue; // No bounds for this symbol at this loop level
            }

            // Get the affine coefficients: first_idx = mul * sym + add
            symbolic::SymbolVec gens = {sym};
            auto polynomial = symbolic::polynomial(first_idx, gens);
            if (polynomial == SymEngine::null) {
                continue; // Not a polynomial
            }
            auto coeffs = symbolic::affine_coefficients(polynomial, gens);
            if (coeffs.find(sym) == coeffs.end()) {
                continue;
            }

            auto mul = coeffs.at(sym);
            if (!symbolic::eq(mul, symbolic::one())) {
                continue; // Non-unit coefficient, can't simply bound
            }

            auto constant_sym = symbolic::symbol("__daisy_constant__");
            symbolic::Expression add;
            if (coeffs.count(constant_sym)) {
                add = coeffs.at(constant_sym);
            } else {
                add = symbolic::zero();
            }
            auto& sym_assumption = assumptions.at(sym);
            auto sym_bound = sym_assumption.tight_upper_bound();

            // Accessed range upper bound: sym_bound + add + 1 (exclusive)
            auto access_bound = symbolic::simplify(symbolic::add(symbolic::add(sym_bound, add), symbolic::one()));

            if (!max_bound.has_value()) {
                max_bound = access_bound;
            } else {
                // Take maximum of current max and this bound
                // For simplicity, if they differ symbolically, keep symbolic max
                if (!symbolic::eq(*max_bound, access_bound)) {
                    max_bound = symbolic::max(*max_bound, access_bound);
                }
            }
        }

        if (!max_bound.has_value()) {
            continue; // Could not bound first dimension at this loop level
        }
        auto max_bound_val = symbolic::expand(*max_bound);
        max_bound_val = symbolic::simplify(max_bound_val);

        // Store this loop's view of the container
        auto loop_shape = first_access.layout.shape();
        if (!loop_shape.empty()) {
            loop_shape[0] = max_bound_val;
        }
        loop_layouts_.insert(
            {{&loop, container}, MemoryLayout(loop_shape, first_access.layout.strides(), first_access.layout.offset())}
        );

        // Update all accesses in this container with the bounded first dimension
        for (const auto* memlet_ptr : memlets) {
            auto& access = layouts_.at(memlet_ptr);
            // Copy data before modifying
            auto container = access.container;
            auto subset = access.subset;
            auto new_shape = access.layout.shape();
            auto strides = access.layout.strides();
            auto offset = access.layout.offset();
            if (!new_shape.empty()) {
                new_shape[0] = max_bound_val;
            }
            // Update the layout with bounded first dimension
            layouts_.erase(memlet_ptr);
            layouts_
                .emplace(memlet_ptr, MemoryAccess{container, subset, MemoryLayout(new_shape, strides, offset), true});
        }
    }
}

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

} // namespace analysis
} // namespace sdfg

1	#include "sdfg/analysis/memory_layout_analysis.h"
2
3	#include <iostream>
4	#include <optional>
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/polynomials.h"
16
17	namespace sdfg {
18	namespace analysis {
19
20	MemoryLayoutAnalysis::MemoryLayoutAnalysis(StructuredSDFG& sdfg) : Analysis(sdfg) {}	2✔
21
22	void MemoryLayoutAnalysis::run(analysis::AnalysisManager& analysis_manager) {	2✔
23	layouts_.clear();	2✔
24	loop_layouts_.clear();	2✔
25	traverse(sdfg_.root(), analysis_manager);	2✔
26	}	2✔
27
28	void MemoryLayoutAnalysis::
29	traverse(structured_control_flow::ControlFlowNode& node, analysis::AnalysisManager& analysis_manager) {	12✔
30	if (auto block = dynamic_cast<structured_control_flow::Block*>(&node)) {	12✔
31	process_block(*block, analysis_manager);	2✔
32	} else if (auto sequence = dynamic_cast<structured_control_flow::Sequence*>(&node)) {	10✔
33	for (size_t i = 0; i < sequence->size(); i++) {	12✔
34	traverse(sequence->at(i).first, analysis_manager);	6✔
35	}	6✔
36	} else if (auto if_else = dynamic_cast<structured_control_flow::IfElse*>(&node)) {	6✔
NEW 37	for (size_t i = 0; i < if_else->size(); i++) {	×
NEW 38	traverse(if_else->at(i).first, analysis_manager);	×
NEW 39	}	×
40	} else if (auto while_stmt = dynamic_cast<structured_control_flow::While*>(&node)) {	4✔
NEW 41	traverse(while_stmt->root(), analysis_manager);	×
42	} else if (auto loop = dynamic_cast<structured_control_flow::StructuredLoop*>(&node)) {	4✔
43	// Snapshot current memlets before traversing loop body
44	std::vector<const data_flow::Memlet*> memlets_before;	4✔
45	memlets_before.reserve(layouts_.size());	4✔
46	for (const auto& entry : layouts_) {	4✔
NEW 47	memlets_before.push_back(entry.first);	×
NEW 48	}	×
49
50	traverse(loop->root(), analysis_manager);	4✔
51
52	// Merge layouts for containers accessed within this loop
53	merge_loop_layouts(*loop, memlets_before, analysis_manager);	4✔
54	}	4✔
55	// Break, Continue, Return nodes don't contain blocks
56	}	12✔
57
58	void MemoryLayoutAnalysis::
59	process_block(structured_control_flow::Block& block, analysis::AnalysisManager& analysis_manager) {	2✔
60	auto& assumptions_analysis = analysis_manager.get<AssumptionsAnalysis>();	2✔
61	auto& assumptions = assumptions_analysis.get(block);	2✔
62
63	auto& dfg = block.dataflow();	2✔
64	for (auto& memlet : dfg.edges()) {	7✔
65	const auto& subset = memlet.subset();	7✔
66	if (subset.empty()) {	7✔
NEW 67	continue;	×
NEW 68	}	×
69
70	// Get container name from the AccessNode (either src or dst)
71	std::string container_name;	7✔
72	if (auto* access = dynamic_cast<const data_flow::AccessNode*>(&memlet.src())) {	7✔
73	container_name = access->data();	6✔
74	} else if (auto* access = dynamic_cast<const data_flow::AccessNode*>(&memlet.dst())) {	6✔
75	container_name = access->data();	1✔
76	} else {	1✔
NEW 77	continue; // Skip memlets without AccessNode	×
NEW 78	}	×
79
80	auto& base_type = memlet.base_type();	7✔
81	switch (base_type.type_id()) {	7✔
NEW 82	case types::TypeID::Scalar:	×
NEW 83	case types::TypeID::Structure:	×
NEW 84	continue; // Skip scalars and structures	×
NEW 85	case types::TypeID::Tensor: {	×
86	// Tensor types already contain layout information, so we can directly store it without delinearization
NEW 87	auto& tensor_type = dynamic_cast<const types::Tensor&>(memlet.base_type());	×
88
NEW 89	MemoryLayout layout(tensor_type.shape(), tensor_type.strides(), tensor_type.offset());	×
NEW 90	MemoryAccess layout_info{container_name, subset, layout, true};	×
NEW 91	this->layouts_.emplace(&memlet, layout_info);	×
NEW 92	continue;	×
NEW 93	}	×
NEW 94	case types::TypeID::Array: {	×
95	// Arrays are c-like stack array, so we can infer a simple row-major layout without needing
96	// delinearization
NEW 97	auto* array_type = dynamic_cast<const types::Array*>(&memlet.base_type());	×
NEW 98	symbolic::MultiExpression shape = {array_type->num_elements()};	×
NEW 99	while (array_type->element_type().type_id() == types::TypeID::Array) {	×
NEW 100	array_type = dynamic_cast<const types::Array*>(&array_type->element_type());	×
NEW 101	}	×
NEW 102	if (array_type->element_type().type_id() != types::TypeID::Scalar) {	×
NEW 103	continue; // Skip non-scalar arrays	×
NEW 104	}	×
105
NEW 106	MemoryLayout layout(shape);	×
NEW 107	MemoryAccess layout_info{container_name, subset, layout, true};	×
NEW 108	this->layouts_.emplace(&memlet, layout_info);	×
NEW 109	continue;	×
NEW 110	}	×
111	case types::TypeID::Pointer: {	7✔
112	// For pointers, we attempt to delinearize the access pattern to infer the layout based
113	// on assumptions from loop bounds
114	auto* pointer_type = dynamic_cast<const types::Pointer*>(&memlet.base_type());	7✔
115	if (pointer_type->pointee_type().type_id() != types::TypeID::Scalar) {	7✔
NEW 116	std::cerr << "[DEBUG] Skipping non-scalar pointer for " << container_name << std::endl;	×
NEW 117	continue; // Skip non-scalar pointers	×
NEW 118	}	×
119
120	if (subset.size() != 1) {	7✔
NEW 121	std::cerr << "[DEBUG] Skipping " << container_name << ": subset.size() = " << subset.size()	×
NEW 122	<< " (requires 1)" << std::endl;	×
NEW 123	continue; // Require full linearization	×
NEW 124	}	×
125	auto& linearized_expr = subset.at(0);	7✔
126
127	std::cerr << "[DEBUG] Delinearizing " << container_name << ": " << *linearized_expr << std::endl;	7✔
128	std::cerr << "[DEBUG] Assumptions available:" << std::endl;	7✔
129	for (const auto& [sym, assump] : assumptions) {	28✔
130	for (const auto& bound : assump.upper_bounds()) {	28✔
131	std::cerr << " " << sym << ": upper bound " << bound << std::endl;	14✔
132	}	14✔
133	for (const auto& bound : assump.lower_bounds()) {	28✔
134	std::cerr << " " << sym << ": lower bound " << bound << std::endl;	28✔
135	}	28✔
136	}	28✔
137
138	auto result = symbolic::delinearize(linearized_expr, assumptions);	7✔
139	if (!result.success) {	7✔
NEW 140	std::cerr << "[DEBUG] Delinearization FAILED for " << container_name << std::endl;	×
NEW 141	continue; // Delinearization failed, skip	×
NEW 142	}	×
143
144	std::cerr << "[DEBUG] Delinearization SUCCESS for " << container_name << std::endl;	7✔
145	std::cerr << "[DEBUG] Indices: ";	7✔
146	for (const auto& idx : result.indices) {	14✔
147	std::cerr << *idx << " ";	14✔
148	}	14✔
149	std::cerr << std::endl;	7✔
150	std::cerr << "[DEBUG] Dimensions: ";	7✔
151	for (const auto& dim : result.dimensions) {	7✔
152	std::cerr << *dim << " ";	7✔
153	}	7✔
154	std::cerr << std::endl;	7✔
155	if (!result.success) {	7✔
NEW 156	continue; // Delinearization failed, skip	×
NEW 157	}	×
158
159	// Delinearization returns N indices but only N-1 dimensions (from stride division)
160	// The first dimension is unbounded - insert a placeholder that will be filled in by merge
161	// Using a special symbol as placeholder for the first dimension
162	symbolic::MultiExpression shape;	7✔
163	shape.push_back(symbolic::symbol("__first_dim_placeholder__"));	7✔
164	for (const auto& dim : result.dimensions) {	7✔
165	shape.push_back(dim);	7✔
166	}	7✔
167
168	// Store symbolic indices and dimensions with unbounded first dimension
169	// The merge phase will attempt to bound the first dimension using loop assumptions
170	MemoryLayout layout(shape);	7✔
171	MemoryAccess layout_info{container_name, result.indices, layout, false};	7✔
172	this->layouts_.emplace(&memlet, layout_info);	7✔
173	continue;	7✔
174	}	7✔
NEW 175	default:	×
NEW 176	continue; // Skip unsupported types	×
177	}	7✔
178	}	7✔
179	}	2✔
180
181	const MemoryAccess* MemoryLayoutAnalysis::get(const data_flow::Memlet& memlet) const {	13✔
182	auto layout_it = layouts_.find(&memlet);	13✔
183	if (layout_it == layouts_.end()) {	13✔
NEW 184	return nullptr;	×
NEW 185	}	×
186	return &layout_it->second;	13✔
187	}	13✔
188
189	void MemoryLayoutAnalysis::merge_loop_layouts(
190	structured_control_flow::StructuredLoop& loop,
191	const std::vector<const data_flow::Memlet*>& memlets_before,
192	analysis::AnalysisManager& analysis_manager
193	) {	4✔
194	// Convert memlets_before to a set for O(1) lookup
195	std::unordered_set<const data_flow::Memlet*> before_set(memlets_before.begin(), memlets_before.end());	4✔
196
197	// Group newly added unbounded layouts by container
198	std::unordered_map<std::string, std::vector<const data_flow::Memlet*>> container_groups;	4✔
199	for (auto& [memlet_ptr, access] : layouts_) {	14✔
200	if (before_set.find(memlet_ptr) != before_set.end()) {	14✔
NEW 201	continue; // Skip memlets that existed before this loop	×
NEW 202	}	×
203	if (access.first_dim_bounded) {	14✔
204	continue; // Skip already bounded layouts	7✔
205	}	7✔
206	container_groups[access.container].push_back(memlet_ptr);	7✔
207	}	7✔
208
209	// Get assumptions at loop body level (includes loop variable bounds)
210	// The loop's indvar bounds are only available inside the loop body, not at the loop node itself
211	auto& assumptions_analysis = analysis_manager.get<AssumptionsAnalysis>();	4✔
212	auto& assumptions = assumptions_analysis.get(loop.root());	4✔
213
214	// Process each container group
215	for (auto& [container, memlets] : container_groups) {	4✔
216	if (memlets.empty()) continue;	3✔
217
218	// Collect all inner dimensions and first-dim indices for consistency check
219	auto& first_access = layouts_.at(memlets[0]);	3✔
220	auto& reference_shape = first_access.layout.shape();	3✔
221	if (reference_shape.empty()) continue;	3✔
222
223	// Check consistency of inner dimensions across all accesses
224	bool consistent = true;	3✔
225	std::vector<symbolic::Expression> first_dim_indices;	3✔
226	first_dim_indices.reserve(memlets.size());	3✔
227
228	for (const auto* memlet_ptr : memlets) {	7✔
229	auto& access = layouts_.at(memlet_ptr);	7✔
230	auto& shape = access.layout.shape();	7✔
231
232	// Check inner dimensions match (all except first)
233	if (shape.size() != reference_shape.size()) {	7✔
NEW 234	consistent = false;	×
NEW 235	break;	×
NEW 236	}	×
237	for (size_t i = 1; i < shape.size(); ++i) {	14✔
238	if (!symbolic::eq(shape[i], reference_shape[i])) {	7✔
NEW 239	consistent = false;	×
NEW 240	break;	×
NEW 241	}	×
242	}	7✔
243	if (!consistent) break;	7✔
244
245	// Collect first-dimension index
246	if (!access.subset.empty()) {	7✔
247	first_dim_indices.push_back(access.subset[0]);	7✔
248	}	7✔
249	}	7✔
250
251	if (!consistent \|\| first_dim_indices.empty()) {	3✔
NEW 252	continue; // Skip containers with inconsistent layouts	×
NEW 253	}	×
254
255	// Attempt to bound first dimension from collected indices
256	// Find the maximum offset across all first-dim indices
257	std::optional<symbolic::Expression> max_bound;	3✔
258
259	for (const auto& first_idx : first_dim_indices) {	7✔
260	// Extract symbols from the index expression
261	auto syms = symbolic::atoms(first_idx);	7✔
262	if (syms.size() != 1) {	7✔
263	// Can't handle multi-symbol or constant-only indices at this level
264	// Skip and let outer loop try
NEW 265	continue;	×
NEW 266	}	×
267	auto sym = *syms.begin();	7✔
268
269	// Check if we have assumptions for this symbol
270	if (assumptions.find(sym) == assumptions.end()) {	7✔
NEW 271	continue; // No bounds for this symbol at this loop level	×
NEW 272	}	×
273
274	// Get the affine coefficients: first_idx = mul * sym + add
275	symbolic::SymbolVec gens = {sym};	7✔
276	auto polynomial = symbolic::polynomial(first_idx, gens);	7✔
277	if (polynomial == SymEngine::null) {	7✔
NEW 278	continue; // Not a polynomial	×
NEW 279	}	×
280	auto coeffs = symbolic::affine_coefficients(polynomial, gens);	7✔
281	if (coeffs.find(sym) == coeffs.end()) {	7✔
NEW 282	continue;	×
NEW 283	}	×
284
285	auto mul = coeffs.at(sym);	7✔
286	if (!symbolic::eq(mul, symbolic::one())) {	7✔
NEW 287	continue; // Non-unit coefficient, can't simply bound	×
NEW 288	}	×
289
290	auto constant_sym = symbolic::symbol("__daisy_constant__");	7✔
291	symbolic::Expression add;	7✔
292	if (coeffs.count(constant_sym)) {	7✔
293	add = coeffs.at(constant_sym);	7✔
294	} else {	7✔
NEW 295	add = symbolic::zero();	×
NEW 296	}	×
297	auto& sym_assumption = assumptions.at(sym);	7✔
298	auto sym_bound = sym_assumption.tight_upper_bound();	7✔
299
300	// Accessed range upper bound: sym_bound + add + 1 (exclusive)
301	auto access_bound = symbolic::simplify(symbolic::add(symbolic::add(sym_bound, add), symbolic::one()));	7✔
302
303	if (!max_bound.has_value()) {	7✔
304	max_bound = access_bound;	3✔
305	} else {	4✔
306	// Take maximum of current max and this bound
307	// For simplicity, if they differ symbolically, keep symbolic max
308	if (!symbolic::eq(*max_bound, access_bound)) {	4✔
309	max_bound = symbolic::max(*max_bound, access_bound);	3✔
310	}	3✔
311	}	4✔
312	}	7✔
313
314	if (!max_bound.has_value()) {	3✔
NEW 315	continue; // Could not bound first dimension at this loop level	×
NEW 316	}	×
317	auto max_bound_val = symbolic::expand(*max_bound);	3✔
318	max_bound_val = symbolic::simplify(max_bound_val);	3✔
319
320	// Store this loop's view of the container
321	auto loop_shape = first_access.layout.shape();	3✔
322	if (!loop_shape.empty()) {	3✔
323	loop_shape[0] = max_bound_val;	3✔
324	}	3✔
325	loop_layouts_.insert(	3✔
326	{{&loop, container}, MemoryLayout(loop_shape, first_access.layout.strides(), first_access.layout.offset())}	3✔
327	);	3✔
328
329	// Update all accesses in this container with the bounded first dimension
330	for (const auto* memlet_ptr : memlets) {	7✔
331	auto& access = layouts_.at(memlet_ptr);	7✔
332	// Copy data before modifying
333	auto container = access.container;	7✔
334	auto subset = access.subset;	7✔
335	auto new_shape = access.layout.shape();	7✔
336	auto strides = access.layout.strides();	7✔
337	auto offset = access.layout.offset();	7✔
338	if (!new_shape.empty()) {	7✔
339	new_shape[0] = max_bound_val;	7✔
340	}	7✔
341	// Update the layout with bounded first dimension
342	layouts_.erase(memlet_ptr);	7✔
343	layouts_	7✔
344	.emplace(memlet_ptr, MemoryAccess{container, subset, MemoryLayout(new_shape, strides, offset), true});	7✔
345	}	7✔
346	}	3✔
347	}	4✔
348
349	const MemoryLayout* MemoryLayoutAnalysis::
NEW 350	get(const structured_control_flow::StructuredLoop& loop, const std::string& container) const {	×
NEW 351	auto key = std::make_pair(&loop, container);	×
NEW 352	auto it = loop_layouts_.find(key);	×
NEW 353	if (it == loop_layouts_.end()) {	×
NEW 354	return nullptr;	×
NEW 355	}	×
NEW 356	return &it->second;	×
NEW 357	}	×
358
359	} // namespace analysis
360	} // namespace sdfg

daisytuner / docc / 24639587487

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