16069945621

Committed 04 Jul 2025 08:56AM UTC coverage: 64.375% (-0.2%) from 64.606%

Build # 16069945621

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #137 from daisytuner/clang-format

runs clang-format on codebase

Run Details

609 of 827 new or added lines in 63 files covered. (73.64%)

46 existing lines in 30 files now uncovered.

8578 of 13325 relevant lines covered (64.38%)

177.24 hits per line

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

81.16

/src/analysis/mem_access_range_analysis.cpp


#include "sdfg/analysis/mem_access_range_analysis.h"

#include <stdbool.h>
#include <symengine/basic.h>
#include <symengine/functions.h>
#include <symengine/infinity.h>
#include <symengine/number.h>
#include <symengine/symengine_rcp.h>

#include <tuple>
#include <unordered_set>
#include <utility>
#include <vector>

#include "sdfg/analysis/analysis.h"
#include "sdfg/analysis/assumptions_analysis.h"
#include "sdfg/analysis/mem_access_range_analysis_internal.h"
#include "sdfg/analysis/users.h"
#include "sdfg/symbolic/extreme_values.h"
#include "sdfg/symbolic/symbolic.h"

namespace sdfg {
namespace analysis {

MemAccessRanges::MemAccessRanges(StructuredSDFG& sdfg) : Analysis(sdfg), graph_() {}

void MemAccessRanges::
    run(structured_control_flow::ControlFlowNode& node, std::unordered_set<std::string> target_containers) {
    auto& users = analysis_manager_->get<Users>();
    auto& assumptions_analysis = analysis_manager_->get<AssumptionsAnalysis>();

    UsersView users_view(users, node);

    auto builder = MemAccessRangesBuilder(sdfg_, users_view, assumptions_analysis);

    auto& worklist = builder.worklist_;

    // Initialize worklist with containers
    for (const auto& container : target_containers) {
        worklist.push_back(new WorkItem{&container});
    }

    // Iterate over all variables and their users
    while (!worklist.empty()) {
        auto* workItem = worklist.front();
        builder.process_workItem(workItem);
        worklist.pop_front();
        delete workItem;
    }

    this->ranges_.insert({&node, std::move(builder.ranges_)});
}

void MemAccessRanges::run(analysis::AnalysisManager& analysis_manager) {
    this->analysis_manager_ = &analysis_manager;
    std::unordered_set<std::string> containers;

    // Collect argument names
    for (auto& arg : sdfg_.arguments()) {
        if (sdfg_.type(arg).type_id() != types::TypeID::Scalar) {
            containers.insert(arg);
        }
    }

    // Collect external names
    for (auto& ext : sdfg_.externals()) {
        if (sdfg_.type(ext).type_id() != types::TypeID::Scalar) {
            containers.insert(ext);
        }
    }

    this->run(sdfg_.root(), containers);
}

const MemAccessRange* MemAccessRanges::get(const std::string& varName) const {
    auto ranges = this->ranges_.find(&sdfg_.root());
    if (ranges == this->ranges_.end()) {
        return nullptr;
    }
    auto res = ranges->second.find(varName);
    if (res != ranges->second.end()) {
        return &res->second;
    } else {
        return nullptr;
    }
}

const MemAccessRange* MemAccessRanges::
    get(const std::string& varName,
        structured_control_flow::ControlFlowNode& node,
        std::unordered_set<std::string> target_nodes) {
    auto ranges = this->ranges_.find(&node);
    if (ranges == this->ranges_.end()) {
        this->run(node, target_nodes);
        ranges = this->ranges_.find(&node);
        if (ranges == this->ranges_.end()) {
            return nullptr;
        }
    }
    auto res = ranges->second.find(varName);
    if (res != ranges->second.end()) {
        return &res->second;
    } else {
        return nullptr;
    }
}

MemAccessRange::MemAccessRange(
    const std::string& name,
    bool saw_read,
    bool saw_write,
    bool undefined,
    const std::vector<std::pair<symbolic::Expression, symbolic::Expression>>&& dims
)
    : name_(name), saw_read_(saw_read), saw_write_(saw_write), undefined_(undefined), dims_(dims) {}

const std::string& MemAccessRange::get_name() const { return name_; }

bool MemAccessRange::saw_read() const { return saw_read_; }
bool MemAccessRange::saw_write() const { return saw_write_; }
bool MemAccessRange::is_undefined() const { return undefined_; }

const std::vector<std::pair<symbolic::Expression, symbolic::Expression>>& MemAccessRange::dims() const { return dims_; }

void MemAccessRangesBuilder::process_workItem(WorkItem* item) {
    const auto* varName = item->var_name;
    const auto& type = sdfg_.type(*varName);

    const auto& reads = users_.reads(*varName);
    process_direct_users(item, false, reads);

    const auto& writes = users_.writes(*varName);
    process_direct_users(item, true, writes);

    const auto& views = users_.views(*varName);
    if (!views.empty()) {
#ifndef NDEBUG
        std::cerr << "Found views for " << *varName << " => not rangeable!" << std::endl;
#endif
        item->undefined = true;
    }

    const auto& moves = users_.moves(*varName);
    if (!moves.empty()) {
        std::cerr << "Found moves for " << *varName << " => not rangeable!" << std::endl;
        item->undefined = true;
    }

    if (!item->dims.empty()) {
        std::vector<std::pair<symbolic::Expression, symbolic::Expression>> finalDims;
        finalDims.reserve(item->dims.size());

        for (auto& dim : item->dims) {
            auto& lowerExprs = std::get<0>(dim);
            bool isLowerUndefined = std::get<1>(dim);
            symbolic::Expression lb = (!lowerExprs.empty() && !isLowerUndefined)
                                          ? SymEngine::min(lowerExprs)
                                          : SymEngine::RCP<const SymEngine::Basic>();
            auto& upperExprs = std::get<2>(dim);
            bool isUpperUndefined = std::get<3>(dim);
            symbolic::Expression ub = (!upperExprs.empty() && !isUpperUndefined)
                                          ? SymEngine::max(upperExprs)
                                          : SymEngine::RCP<const SymEngine::Basic>();

            if (lb.is_null() || ub.is_null()) {
                item->undefined = true;
            }
            if (!lb.is_null() && SymEngine::is_a<SymEngine::Infty>(*lb)) {
                lb = SymEngine::null;
                item->undefined = true;
            }
            if (!ub.is_null() && SymEngine::is_a<SymEngine::Infty>(*ub)) {
                ub = SymEngine::null;
                item->undefined = true;
            }

            finalDims.emplace_back(std::move(lb), std::move(ub));
        }

#if !defined(NDEBUG)
        // std::cout << "RangeAna: " << *varName << ": (" << (item->saw_read? "r" : "") <<
        // (item->saw_write? "w" : "") << ") " << (!item->undefined? "ranged" : "undef")
        //           << ", " << finalDims.size() << "D: [\n";
        // for (size_t i = 0; i < finalDims.size(); ++i) {
        //     const auto& dim = finalDims[i];
        //     std::cout << "\t(" << (!dim.first.is_null()? dim.first->__str__() : "null")
        //               << " .. " << (!dim.second.is_null()? dim.second->__str__() : "null") <<
        //               ")";
        //     std::cout << "\n";
        // }
        // std::cout << "]" << std::endl;
#endif

        this->ranges_.emplace(
            std::piecewise_construct,
            std::forward_as_tuple(*varName),
            std::forward_as_tuple(*varName, item->saw_read, item->saw_write, item->undefined, std::move(finalDims))
        );
    }
}

void MemAccessRangesBuilder::process_direct_users(WorkItem* item, bool is_write, std::vector<User*> accesses) {
    for (auto& access : accesses) {
        auto subsets = access->subsets();
        const auto& user_scope = analysis::Users::scope(access);
        auto assums = assumptions_analysis_.get(*user_scope, false);
        auto params = this->sdfg_.parameters();

        item->saw_read |= !is_write;
        item->saw_write |= is_write;

        for (const auto& subset : subsets) {
            auto subsetDims = subset.size();
            item->dims.reserve(subsetDims);
            for (size_t i = item->dims.size(); i < subsetDims; ++i) {
                item->dims.emplace_back(std::make_tuple<
                                        std::vector<symbolic::Expression>,
                                        bool,
                                        std::vector<symbolic::Expression>,
                                        bool>({}, false, {}, false));
            }
            int dimIdx = 0;
            for (auto& dim : subset) {
                auto lb = symbolic::minimum(dim, params, assums);
                auto ub = symbolic::maximum(dim, params, assums);

                if (lb.is_null()) {
                    std::get<1>(item->dims[dimIdx]) = true;
                } else {
                    std::get<0>(item->dims[dimIdx]).push_back(lb);
                }
                if (ub.is_null()) {
                    std::get<3>(item->dims[dimIdx]) = true;
                } else {
                    std::get<2>(item->dims[dimIdx]).push_back(ub);
                }

                ++dimIdx;
            }
        }
    }
}

} // namespace analysis
} // namespace sdfg

1
2	#include "sdfg/analysis/mem_access_range_analysis.h"
3
4	#include <stdbool.h>
5	#include <symengine/basic.h>
6	#include <symengine/functions.h>
7	#include <symengine/infinity.h>
8	#include <symengine/number.h>
9	#include <symengine/symengine_rcp.h>
10
11	#include <tuple>
12	#include <unordered_set>
13	#include <utility>
14	#include <vector>
15
16	#include "sdfg/analysis/analysis.h"
17	#include "sdfg/analysis/assumptions_analysis.h"
18	#include "sdfg/analysis/mem_access_range_analysis_internal.h"
19	#include "sdfg/analysis/users.h"
20	#include "sdfg/symbolic/extreme_values.h"
21	#include "sdfg/symbolic/symbolic.h"
22
23	namespace sdfg {
24	namespace analysis {
25
26	MemAccessRanges::MemAccessRanges(StructuredSDFG& sdfg) : Analysis(sdfg), graph_() {}	4✔
27
28	void MemAccessRanges::
29	run(structured_control_flow::ControlFlowNode& node, std::unordered_set<std::string> target_containers) {	4✔
30	auto& users = analysis_manager_->get<Users>();	4✔
31	auto& assumptions_analysis = analysis_manager_->get<AssumptionsAnalysis>();	4✔
32
33	UsersView users_view(users, node);	4✔
34
35	auto builder = MemAccessRangesBuilder(sdfg_, users_view, assumptions_analysis);	4✔
36
37	auto& worklist = builder.worklist_;	4✔
38
39	// Initialize worklist with containers
40	for (const auto& container : target_containers) {	11✔
41	worklist.push_back(new WorkItem{&container});	7✔
42	}
43
44	// Iterate over all variables and their users
45	while (!worklist.empty()) {	11✔
46	auto* workItem = worklist.front();	7✔
47	builder.process_workItem(workItem);	7✔
48	worklist.pop_front();	7✔
49	delete workItem;	7✔
50	}
51
52	this->ranges_.insert({&node, std::move(builder.ranges_)});	4✔
53	}	4✔
54
55	void MemAccessRanges::run(analysis::AnalysisManager& analysis_manager) {	4✔
56	this->analysis_manager_ = &analysis_manager;	4✔
57	std::unordered_set<std::string> containers;	4✔
58
59	// Collect argument names
60	for (auto& arg : sdfg_.arguments()) {	13✔
61	if (sdfg_.type(arg).type_id() != types::TypeID::Scalar) {	9✔
62	containers.insert(arg);	6✔
63	}	6✔
64	}
65
66	// Collect external names
67	for (auto& ext : sdfg_.externals()) {	6✔
68	if (sdfg_.type(ext).type_id() != types::TypeID::Scalar) {	2✔
69	containers.insert(ext);	1✔
70	}	1✔
71	}
72
73	this->run(sdfg_.root(), containers);	4✔
74	}	4✔
75
76	const MemAccessRange* MemAccessRanges::get(const std::string& varName) const {	12✔
77	auto ranges = this->ranges_.find(&sdfg_.root());	12✔
78	if (ranges == this->ranges_.end()) {	12✔
79	return nullptr;	×
80	}
81	auto res = ranges->second.find(varName);	12✔
82	if (res != ranges->second.end()) {	12✔
83	return &res->second;	6✔
84	} else {
85	return nullptr;	6✔
86	}
87	}	12✔
88
89	const MemAccessRange* MemAccessRanges::
NEW 90	get(const std::string& varName,	×
91	structured_control_flow::ControlFlowNode& node,
92	std::unordered_set<std::string> target_nodes) {
93	auto ranges = this->ranges_.find(&node);	×
94	if (ranges == this->ranges_.end()) {	×
95	this->run(node, target_nodes);	×
96	ranges = this->ranges_.find(&node);	×
97	if (ranges == this->ranges_.end()) {	×
98	return nullptr;	×
99	}
100	}	×
101	auto res = ranges->second.find(varName);	×
102	if (res != ranges->second.end()) {	×
103	return &res->second;	×
104	} else {
105	return nullptr;	×
106	}
107	}	×
108
109	MemAccessRange::MemAccessRange(	7✔
110	const std::string& name,
111	bool saw_read,
112	bool saw_write,
113	bool undefined,
114	const std::vector<std::pair<symbolic::Expression, symbolic::Expression>>&& dims
115	)
116	: name_(name), saw_read_(saw_read), saw_write_(saw_write), undefined_(undefined), dims_(dims) {}	7✔
117
118	const std::string& MemAccessRange::get_name() const { return name_; }	4✔
119
120	bool MemAccessRange::saw_read() const { return saw_read_; }	6✔
121	bool MemAccessRange::saw_write() const { return saw_write_; }	6✔
122	bool MemAccessRange::is_undefined() const { return undefined_; }	6✔
123
124	const std::vector<std::pair<symbolic::Expression, symbolic::Expression>>& MemAccessRange::dims() const { return dims_; }	6✔
125
126	void MemAccessRangesBuilder::process_workItem(WorkItem* item) {	7✔
127	const auto* varName = item->var_name;	7✔
128	const auto& type = sdfg_.type(*varName);	7✔
129
130	const auto& reads = users_.reads(*varName);	7✔
131	process_direct_users(item, false, reads);	7✔
132
133	const auto& writes = users_.writes(*varName);	7✔
134	process_direct_users(item, true, writes);	7✔
135
136	const auto& views = users_.views(*varName);	7✔
137	if (!views.empty()) {	7✔
138	#ifndef NDEBUG
139	std::cerr << "Found views for " << *varName << " => not rangeable!" << std::endl;	×
140	#endif
141	item->undefined = true;	×
142	}	×
143
144	const auto& moves = users_.moves(*varName);	7✔
145	if (!moves.empty()) {	7✔
146	std::cerr << "Found moves for " << *varName << " => not rangeable!" << std::endl;	×
147	item->undefined = true;	×
148	}	×
149
150	if (!item->dims.empty()) {	7✔
151	std::vector<std::pair<symbolic::Expression, symbolic::Expression>> finalDims;	7✔
152	finalDims.reserve(item->dims.size());	7✔
153
154	for (auto& dim : item->dims) {	17✔
155	auto& lowerExprs = std::get<0>(dim);	10✔
156	bool isLowerUndefined = std::get<1>(dim);	10✔
157	symbolic::Expression lb = (!lowerExprs.empty() && !isLowerUndefined)	20✔
158	? SymEngine::min(lowerExprs)	9✔
159	: SymEngine::RCP<const SymEngine::Basic>();	1✔
160	auto& upperExprs = std::get<2>(dim);	10✔
161	bool isUpperUndefined = std::get<3>(dim);	10✔
162	symbolic::Expression ub = (!upperExprs.empty() && !isUpperUndefined)	20✔
163	? SymEngine::max(upperExprs)	10✔
164	: SymEngine::RCP<const SymEngine::Basic>();	×
165
166	if (lb.is_null() \|\| ub.is_null()) {	10✔
167	item->undefined = true;	1✔
168	}	1✔
169	if (!lb.is_null() && SymEngine::is_a<SymEngine::Infty>(*lb)) {	10✔
170	lb = SymEngine::null;	×
171	item->undefined = true;	×
172	}	×
173	if (!ub.is_null() && SymEngine::is_a<SymEngine::Infty>(*ub)) {	10✔
174	ub = SymEngine::null;	1✔
175	item->undefined = true;	1✔
176	}	1✔
177
178	finalDims.emplace_back(std::move(lb), std::move(ub));	10✔
179	}	10✔
180
181	#if !defined(NDEBUG)
182	// std::cout << "RangeAna: " << *varName << ": (" << (item->saw_read? "r" : "") <<
183	// (item->saw_write? "w" : "") << ") " << (!item->undefined? "ranged" : "undef")
184	// << ", " << finalDims.size() << "D: [\n";
185	// for (size_t i = 0; i < finalDims.size(); ++i) {
186	// const auto& dim = finalDims[i];
187	// std::cout << "\t(" << (!dim.first.is_null()? dim.first->__str__() : "null")
188	// << " .. " << (!dim.second.is_null()? dim.second->__str__() : "null") <<
189	// ")";
190	// std::cout << "\n";
191	// }
192	// std::cout << "]" << std::endl;
193	#endif
194
195	this->ranges_.emplace(	14✔
196	std::piecewise_construct,
197	std::forward_as_tuple(*varName),	7✔
198	std::forward_as_tuple(*varName, item->saw_read, item->saw_write, item->undefined, std::move(finalDims))	7✔
199	);
200	}	7✔
201	}	7✔
202
203	void MemAccessRangesBuilder::process_direct_users(WorkItem* item, bool is_write, std::vector<User*> accesses) {	14✔
204	for (auto& access : accesses) {	22✔
205	auto subsets = access->subsets();	8✔
206	const auto& user_scope = analysis::Users::scope(access);	8✔
207	auto assums = assumptions_analysis_.get(*user_scope, false);	8✔
208	auto params = this->sdfg_.parameters();	8✔
209
210	item->saw_read \|= !is_write;	8✔
211	item->saw_write \|= is_write;	8✔
212
213	for (const auto& subset : subsets) {	16✔
214	auto subsetDims = subset.size();	8✔
215	item->dims.reserve(subsetDims);	8✔
216	for (size_t i = item->dims.size(); i < subsetDims; ++i) {	18✔
217	item->dims.emplace_back(std::make_tuple<	20✔
218	std::vector<symbolic::Expression>,
219	bool,
220	std::vector<symbolic::Expression>,
221	bool>({}, false, {}, false));	10✔
222	}	10✔
223	int dimIdx = 0;	8✔
224	for (auto& dim : subset) {	20✔
225	auto lb = symbolic::minimum(dim, params, assums);	12✔
226	auto ub = symbolic::maximum(dim, params, assums);	12✔
227
228	if (lb.is_null()) {	12✔
229	std::get<1>(item->dims[dimIdx]) = true;	1✔
230	} else {	1✔
231	std::get<0>(item->dims[dimIdx]).push_back(lb);	11✔
232	}
233	if (ub.is_null()) {	12✔
234	std::get<3>(item->dims[dimIdx]) = true;	×
235	} else {	×
236	std::get<2>(item->dims[dimIdx]).push_back(ub);	12✔
237	}
238
239	++dimIdx;	12✔
240	}	12✔
241	}
242	}	8✔
243	}	14✔
244
245	} // namespace analysis
246	} // namespace sdfg

daisytuner / sdfglib / 16069945621

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