21026754920

Committed 15 Jan 2026 09:45AM UTC coverage: 62.594% (+0.3%) from 62.264%

Build # 21026754920

Build Type

Pull #446

github

Committed by

web-flow

Commit Message

Merge 8638fa3d4 into eaabb9b4d

Pull Request Pull Request #446: Fix arg capturing

Run Details

265 of 396 new or added lines in 7 files covered. (66.92%)

11 existing lines in 4 files now uncovered.

15902 of 25405 relevant lines covered (62.59%)

96.77 hits per line

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

84.71

/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/helpers/helpers.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>();

    auto builder = MemAccessRangesBuilder(sdfg_, node, users, 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_or_assign(&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);
    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) {
    analysis::UsersView users_(users_analysis_, node_);

    const auto* varName = item->var_name;

    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()) {
        DEBUG_PRINTLN("Found views for " << *varName << " => not rangeable!");
        item->undefined = true;
    }

    const auto& moves = users_.moves(*varName);
    if (!moves.empty()) {
        DEBUG_PRINTLN("Found moves for " << *varName << " => not rangeable!");
        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));
        }

        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) {
        // The actual range analysis replaces symbols used in subsets
        // by their lower/upper bounds according to the assumptions analysis.
        // For this, we take the immediate scope to get the richest assumptions.
        const auto& user_scope = analysis::Users::scope(access);
        auto assums = assumptions_analysis_.get(*user_scope, false);

        // The final expression must be an expression w.r.t parameters,
        // i.e., constant symbols w.r.t the actual node.
        // Note we can compute this more efficiently once, but
        // we want to move this to the assumptions analysis anyway
        analysis::UsersView users_view(users_analysis_, node_);
        symbolic::SymbolSet params;
        for (auto& user : users_view.uses()) {
            if (user->container() == symbolic::__nullptr__()->get_name()) {
                continue;
            }
            auto& type = sdfg_.type(user->container());
            if (type.type_id() != types::TypeID::Scalar) {
                continue;
            }
            auto& scalar_type = static_cast<const types::Scalar&>(type);
            if (!types::is_integer(scalar_type.primitive_type())) {
                continue;
            }
            if (users_view.writes(user->container()).size() > 0) {
                continue;
            }
            params.insert(symbolic::symbol(user->container()));
        }

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

        auto subsets = access->subsets();
        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_new(dim, params, assums, true);
                auto ub = symbolic::maximum_new(dim, params, assums, true);

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

daisytuner / sdfglib / 21026754920

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