15852980623

Committed 24 Jun 2025 02:16PM UTC coverage: 64.412% (+0.3%) from 64.145%

Build # 15852980623

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #72 from daisytuner/capture-instrumentation

Capture instrumentation

Run Details

363 of 446 new or added lines in 19 files covered. (81.39%)

100 existing lines in 5 files now uncovered.

8389 of 13024 relevant lines covered (64.41%)

116.79 hits per line

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

90.6

/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 <utility>
#include <vector>
#include "sdfg/analysis/mem_access_range_analysis_internal.h"

#include "sdfg/analysis/analysis.h"
#include "sdfg/analysis/assumptions_analysis.h"
#include "sdfg/analysis/users.h"
#include "sdfg/symbolic/symbolic.h"
#include "sdfg/visualizer/dot_visualizer.h"

#include "sdfg/symbolic/extreme_values.h"

namespace sdfg {
namespace analysis {

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

void MemAccessRanges::run(analysis::AnalysisManager& analysis_manager) {

    auto& users = analysis_manager.get<Users>();
    auto& assumptions_analysis = analysis_manager.get<AssumptionsAnalysis>();

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

    auto& worklist = builder.worklist_;

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

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

    // 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_ = std::move(builder.ranges_);
}

const MemAccessRange* MemAccessRanges::get(const std::string& varName) const {
    auto res = ranges_.find(varName);
    if (res != ranges_.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, varName, false, reads);

    const auto& writes = users_.writes(*varName);
    process_direct_users(item, varName, 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, const std::string* varName, bool is_write, std::vector<User*> accesses) {

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

daisytuner / sdfglib / 15852980623

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