20697769161

Committed 04 Jan 2026 07:10PM UTC coverage: 39.678% (+0.06%) from 39.623%

Build # 20697769161

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #427 from daisytuner/copilot/add-memlet-delinearization-analysis

Add MemletDelinearizationAnalysis for recovering multi-dimensional array access patterns

Run Details

15103 of 49551 branches covered (30.48%)

Branch coverage included in aggregate %.

44 of 50 new or added lines in 1 file covered. (88.0%)

17 existing lines in 3 files now uncovered.

12993 of 21259 relevant lines covered (61.12%)

92.38 hits per line

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

76.0

/src/analysis/memlet_delinearization_analysis.cpp

#include "sdfg/analysis/memlet_delinearization_analysis.h"

#include "sdfg/analysis/assumptions_analysis.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/utils.h"

namespace sdfg {
namespace analysis {

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

void MemletDelinearizationAnalysis::run(analysis::AnalysisManager& analysis_manager) {
    delinearized_subsets_.clear();
    traverse(sdfg_.root(), analysis_manager);
}

void MemletDelinearizationAnalysis::
    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)) {
        traverse(loop->root(), analysis_manager);
    }
    // Break, Continue, Return nodes don't contain blocks
}

void MemletDelinearizationAnalysis::
    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();

        // Skip empty subsets
        if (subset.empty()) {
            continue;
        }

        // Attempt to delinearize the subset
        auto delinearized = symbolic::delinearize(subset, assumptions);

        // Check if delinearization changed the subset
        bool changed = (delinearized.size() != subset.size());
        if (!changed) {
            for (size_t i = 0; i < subset.size(); i++) {
                if (!symbolic::eq(subset[i], delinearized[i])) {
                    changed = true;
                    break;
                }
            }
        }

        // Store result only if delinearization was successful (sparse storage)
        if (changed) {
            delinearized_subsets_[&memlet] = std::make_unique<data_flow::Subset>(std::move(delinearized));
        }
    }
}

const data_flow::Subset* MemletDelinearizationAnalysis::get(const data_flow::Memlet& memlet) const {
    auto it = delinearized_subsets_.find(&memlet);
    if (it == delinearized_subsets_.end()) {
        return nullptr;
    }
    return it->second.get();
}

} // namespace analysis
} // namespace sdfg

1	#include "sdfg/analysis/memlet_delinearization_analysis.h"
2
3	#include "sdfg/analysis/assumptions_analysis.h"
4	#include "sdfg/structured_control_flow/block.h"
5	#include "sdfg/structured_control_flow/if_else.h"
6	#include "sdfg/structured_control_flow/sequence.h"
7	#include "sdfg/structured_control_flow/structured_loop.h"
8	#include "sdfg/structured_control_flow/while.h"
9	#include "sdfg/symbolic/utils.h"
10
11	namespace sdfg {
12	namespace analysis {
13
14	MemletDelinearizationAnalysis::MemletDelinearizationAnalysis(StructuredSDFG& sdfg) : Analysis(sdfg) {}	7✔
15
16	void MemletDelinearizationAnalysis::run(analysis::AnalysisManager& analysis_manager) {	7✔
17	delinearized_subsets_.clear();	7✔
18	traverse(sdfg_.root(), analysis_manager);	7✔
19	}	7✔
20
21	void MemletDelinearizationAnalysis::
22	traverse(structured_control_flow::ControlFlowNode& node, analysis::AnalysisManager& analysis_manager) {	26✔
23	if (auto block = dynamic_cast<structured_control_flow::Block*>(&node)) {	26!
24	process_block(*block, analysis_manager);	7✔
25	} else if (auto sequence = dynamic_cast<structured_control_flow::Sequence*>(&node)) {	26!
26	for (size_t i = 0; i < sequence->size(); i++) {	26✔
27	traverse(sequence->at(i).first, analysis_manager);	13✔
28	}	13✔
29	} else if (auto if_else = dynamic_cast<structured_control_flow::IfElse*>(&node)) {	19!
NEW 30	for (size_t i = 0; i < if_else->size(); i++) {	×
NEW 31	traverse(if_else->at(i).first, analysis_manager);	×
NEW 32	}	×
33	} else if (auto while_stmt = dynamic_cast<structured_control_flow::While*>(&node)) {	6!
NEW 34	traverse(while_stmt->root(), analysis_manager);	×
35	} else if (auto loop = dynamic_cast<structured_control_flow::StructuredLoop*>(&node)) {	6!
36	traverse(loop->root(), analysis_manager);	6✔
37	}	6✔
38	// Break, Continue, Return nodes don't contain blocks
39	}	26✔
40
41	void MemletDelinearizationAnalysis::
42	process_block(structured_control_flow::Block& block, analysis::AnalysisManager& analysis_manager) {	7✔
43	auto& assumptions_analysis = analysis_manager.get<AssumptionsAnalysis>();	7✔
44	auto& assumptions = assumptions_analysis.get(block);	7✔
45
46	auto& dfg = block.dataflow();	7✔
47	for (auto& memlet : dfg.edges()) {	14✔
48	const auto& subset = memlet.subset();	7✔
49
50	// Skip empty subsets
51	if (subset.empty()) {	7✔
52	continue;	1✔
53	}
54
55	// Attempt to delinearize the subset
56	auto delinearized = symbolic::delinearize(subset, assumptions);	6✔
57
58	// Check if delinearization changed the subset
59	bool changed = (delinearized.size() != subset.size());	6✔
60	if (!changed) {	6✔
61	for (size_t i = 0; i < subset.size(); i++) {	8✔
62	if (!symbolic::eq(subset[i], delinearized[i])) {	4!
NEW 63	changed = true;	×
NEW 64	break;	×
65	}
66	}	4✔
67	}	4✔
68
69	// Store result only if delinearization was successful (sparse storage)
70	if (changed) {	6✔
71	delinearized_subsets_[&memlet] = std::make_unique<data_flow::Subset>(std::move(delinearized));	2!
72	}	2✔
73	}	6✔
74	}	7✔
75
76	const data_flow::Subset* MemletDelinearizationAnalysis::get(const data_flow::Memlet& memlet) const {	7✔
77	auto it = delinearized_subsets_.find(&memlet);	7✔
78	if (it == delinearized_subsets_.end()) {	7✔
79	return nullptr;	5✔
80	}
81	return it->second.get();	2✔
82	}	7✔
83
84	} // namespace analysis
85	} // namespace sdfg

daisytuner / sdfglib / 20697769161

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