22941264241

Committed 11 Mar 2026 07:16AM UTC coverage: 63.677% (-0.9%) from 64.621%

Build # 22941264241

Build Type

Pull #569

github

Committed by

web-flow

Commit Message

Merge fb0bb9692 into af8bb4c54

Pull Request Pull Request #569: HipTarget

Coverage Stats

191 of 803 new or added lines in 15 files covered. (23.79%)

595 existing lines in 6 files now uncovered.

24699 of 38788 relevant lines covered (63.68%)

370.82 hits per line

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

42.68

/opt/src/transformations/highway_transform.cpp

#include "sdfg/transformations/highway_transform.h"

#include <list>
#include <stdexcept>

#include "sdfg/analysis/assumptions_analysis.h"
#include "sdfg/optimization_report/pass_report_consumer.h"
#include "sdfg/symbolic/polynomials.h"
#include "sdfg/targets/highway/codegen/highway_map_dispatcher.h"

namespace sdfg {
namespace transformations {

HighwayTransform::HighwayTransform(structured_control_flow::Map& map) : map_(map) {}

std::string HighwayTransform::name() const { return "HighwayTransform"; }

bool HighwayTransform::can_be_applied(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {
    if (map_.schedule_type().value() != structured_control_flow::ScheduleType_Sequential::value()) {
        if (report_) {
            report_->transform_impossible(this, "not sequential");
        }
        return false;
    }

    // Check for contiguous loop stride
    auto& assumptions_analysis = analysis_manager.get<analysis::AssumptionsAnalysis>();
    if (!analysis::LoopAnalysis::is_contiguous(&this->map_, assumptions_analysis)) {
        if (report_) {
            report_->transform_impossible(this, "not contiguous");
        }
        return false;
    }

    // Check all outputs are pointers
    auto& arguments_analysis = analysis_manager.get<analysis::ArgumentsAnalysis>();
    std::vector<std::string> arguments;
    for (auto& entry : arguments_analysis.arguments(analysis_manager, map_)) {
        if (entry.second.is_output) {
            if (!entry.second.is_ptr) {
                if (report_) {
                    report_->transform_impossible(this, "contains non-pointer output argument " + entry.first);
                }
                return false;
            }
        }
        if (entry.first == map_.indvar()->get_name()) {
            if (report_) {
                report_->transform_impossible(this, "contains induction variable as argument " + entry.first);
            }
            return false;
        }
    }

    // Check: all locals are scalar (implicitly converted into vectors)
    symbolic::SymbolSet local_symbols;
    for (auto& local : arguments_analysis.locals(analysis_manager, map_)) {
        auto& type = builder.subject().type(local);
        if (type.type_id() != types::TypeID::Scalar) {
            if (report_) {
                report_->transform_impossible(this, "contains non-scalar local " + local);
            }
            return false;
        }
        if (local == map_.indvar()->get_name()) {
            continue;
        }
        if (types::is_integer(type.primitive_type())) {
            local_symbols.insert(symbolic::symbol(local));
        }
    }

    size_t bitwidth = 0;
    std::list<structured_control_flow::ControlFlowNode*> queue = {&map_.root()};
    while (!queue.empty()) {
        auto node = queue.front();
        queue.pop_front();

        if (auto block = dynamic_cast<structured_control_flow::Block*>(node)) {
            auto& graph = block->dataflow();
            for (auto& edge : graph.edges()) {
                if (edge.type() != data_flow::MemletType::Computational) {
                    if (report_) {
                        report_->transform_impossible(
                            this,
                            "contains unsupported memlet type on edge with element ID " +
                                std::to_string(edge.element_id())
                        );
                    }
                    return false;
                }

                size_t edge_bitwidth = types::bit_width(edge.base_type().primitive_type());
                if (bitwidth == 0) {
                    bitwidth = edge_bitwidth;
                } else if (edge_bitwidth != bitwidth) {
                    if (report_) {
                        report_->transform_impossible(
                            this,
                            "contains mismatched memlet bitwidth on edge with element ID " +
                                std::to_string(edge.element_id())
                        );
                    }
                    return false;
                }

                // Classify memlet access pattern
                auto access_type = classify_memlet_access_type(edge.subset(), map_.indvar(), local_symbols);
                if (access_type == HighwayTransform::CONSTANT) {
                    continue;
                } else if (access_type == HighwayTransform::CONTIGUOUS) {
                    continue;
                } else {
                    if (report_) {
                        report_->transform_impossible(
                            this,
                            "contains unsupported memlet access pattern on edge with element ID " +
                                std::to_string(edge.element_id())
                        );
                    }
                    return false;
                }
            }

            for (auto& dnode : graph.topological_sort()) {
                if (auto const_node = dynamic_cast<data_flow::ConstantNode*>(dnode)) {
                    if (const_node->type().type_id() != types::TypeID::Scalar) {
                        if (report_) {
                            report_->transform_impossible(
                                this,
                                "contains unsupported constant type on node with element ID " +
                                    std::to_string(const_node->element_id())
                            );
                        }
                        return false;
                    }
                    continue;
                }
                if (auto access_node = dynamic_cast<data_flow::AccessNode*>(dnode)) {
                    continue;
                }

                if (auto tasklet = dynamic_cast<data_flow::Tasklet*>(dnode)) {
                    std::string code = highway::HighwayMapDispatcher::tasklet(*tasklet);
                    if (code.empty()) {
                        if (report_) {
                            report_->transform_impossible(
                                this,
                                "contains unsupported tasklet node with element ID " +
                                    std::to_string(tasklet->element_id())
                            );
                        }
                        return false;
                    }
                    continue;
                } else if (auto cmath_node = dynamic_cast<math::cmath::CMathNode*>(dnode)) {
                    std::string code = highway::HighwayMapDispatcher::cmath_node(*cmath_node);
                    if (code.empty()) {
                        if (report_) {
                            report_->transform_impossible(
                                this,
                                "contains unsupported CMath node with element ID " +
                                    std::to_string(cmath_node->element_id())
                            );
                        }
                        return false;
                    }
                    continue;
                } else {
                    if (report_) {
                        report_->transform_impossible(
                            this, "contains unsupported dataflow node of type " + std::string(typeid(*dnode).name())
                        );
                    }
                    return false;
                }
            }
        } else if (auto sequence = dynamic_cast<structured_control_flow::Sequence*>(node)) {
            for (size_t i = 0; i < sequence->size(); i++) {
                if (sequence->at(i).second.assignments().size() > 0) {
                    if (report_) {
                        report_->transform_impossible(
                            this,
                            "contains unsupported transition with assignments at element ID " +
                                std::to_string(sequence->at(i).second.element_id())
                        );
                    }
                    return false;
                }
                queue.push_back(&sequence->at(i).first);
            }
        } else {
            if (report_) {
                report_->transform_impossible(
                    this, "contains unsupported control flow node of type " + std::string(typeid(*node).name())
                );
            }
            return false;
        }
    }

    return true;
}

void HighwayTransform::apply(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {
    builder.update_schedule_type(this->map_, highway::ScheduleType_Highway::create());
    if (report_) report_->transform_applied(this);
}

void HighwayTransform::to_json(nlohmann::json& j) const {
    j["transformation_type"] = this->name();
    j["subgraph"] = {{"0", {{"element_id", this->map_.element_id()}, {"type", "map"}}}};
    j["transformation_type"] = this->name();
}

HighwayTransform HighwayTransform::from_json(builder::StructuredSDFGBuilder& builder, const nlohmann::json& desc) {
    auto map_id = desc["subgraph"]["0"]["element_id"].get<size_t>();
    auto element = builder.find_element_by_id(map_id);
    if (element == nullptr) {
        throw std::runtime_error("Element with ID " + std::to_string(map_id) + " not found.");
    }

    auto loop = dynamic_cast<structured_control_flow::Map*>(element);

    if (loop == nullptr) {
        throw std::runtime_error("Element with ID " + std::to_string(map_id) + " is not a Map.");
    }

    return HighwayTransform(*loop);
}

HighwayTransform::MemletAccessType HighwayTransform::classify_memlet_access_type(
    const data_flow::Subset& subset, const symbolic::Symbol& indvar, const symbolic::SymbolSet& local_symbols
) {
    // Scalar access is constant
    if (subset.empty()) {
        return HighwayTransform::CONSTANT;
    }

    // Criterion: dim0, ..., dimN-1 are constant
    for (size_t i = 0; i < subset.size() - 1; ++i) {
        auto expr = subset.at(i);
        bool is_constant = true;
        for (auto& sym : symbolic::atoms(expr)) {
            if (symbolic::eq(sym, indvar)) {
                is_constant = false;
                break;
            }
            if (local_symbols.find(sym) != local_symbols.end()) {
                is_constant = false;
                break;
            }
        }
        if (!is_constant) {
            return HighwayTransform::UNKNOWN;
        }
    }

    // Classify dimN
    auto dimN = subset.back();
    for (auto& sym : symbolic::atoms(dimN)) {
        // Gather / Scatter - extend here
        if (local_symbols.find(sym) != local_symbols.end()) {
            return HighwayTransform::UNKNOWN;
        }
    }
    if (symbolic::uses(dimN, indvar)) {
        if (symbolic::eq(dimN, indvar)) {
            return HighwayTransform::CONTIGUOUS;
        }

        symbolic::SymbolVec poly_gens = {indvar};
        auto poly = symbolic::polynomial(dimN, poly_gens);
        if (poly.is_null()) {
            return HighwayTransform::UNKNOWN;
        }
        auto affine_coeffs = symbolic::affine_coefficients(poly, poly_gens);
        if (affine_coeffs.size() != 2) {
            return HighwayTransform::UNKNOWN;
        }
        auto mul_coeff = affine_coeffs.at(indvar);
        if (symbolic::eq(mul_coeff, symbolic::zero())) {
            return HighwayTransform::CONSTANT;
        }
        if (symbolic::eq(mul_coeff, symbolic::one())) {
            return HighwayTransform::CONTIGUOUS;
        }

        return HighwayTransform::UNKNOWN;
    }

    // dimN does not use indvar or moving symbols -> constant
    return HighwayTransform::CONSTANT;
}

} // namespace transformations
} // namespace sdfg

1	#include "sdfg/transformations/highway_transform.h"
2
3	#include <list>
4	#include <stdexcept>
5
6	#include "sdfg/analysis/assumptions_analysis.h"
7	#include "sdfg/optimization_report/pass_report_consumer.h"
8	#include "sdfg/symbolic/polynomials.h"
9	#include "sdfg/targets/highway/codegen/highway_map_dispatcher.h"
10
11	namespace sdfg {
12	namespace transformations {
13
14	HighwayTransform::HighwayTransform(structured_control_flow::Map& map) : map_(map) {}	11✔
15
16	std::string HighwayTransform::name() const { return "HighwayTransform"; }	×
17
18	bool HighwayTransform::can_be_applied(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	11✔
19	if (map_.schedule_type().value() != structured_control_flow::ScheduleType_Sequential::value()) {	11✔
20	if (report_) {	×
21	report_->transform_impossible(this, "not sequential");	×
22	}	×
23	return false;	×
24	}	×
25
26	// Check for contiguous loop stride
27	auto& assumptions_analysis = analysis_manager.get<analysis::AssumptionsAnalysis>();	11✔
28	if (!analysis::LoopAnalysis::is_contiguous(&this->map_, assumptions_analysis)) {	11✔
29	if (report_) {	1✔
30	report_->transform_impossible(this, "not contiguous");	×
31	}	×
32	return false;	1✔
33	}	1✔
34
35	// Check all outputs are pointers
36	auto& arguments_analysis = analysis_manager.get<analysis::ArgumentsAnalysis>();	10✔
37	std::vector<std::string> arguments;	10✔
38	for (auto& entry : arguments_analysis.arguments(analysis_manager, map_)) {	28✔
39	if (entry.second.is_output) {	28✔
40	if (!entry.second.is_ptr) {	11✔
41	if (report_) {	1✔
42	report_->transform_impossible(this, "contains non-pointer output argument " + entry.first);	×
43	}	×
44	return false;	1✔
45	}	1✔
46	}	11✔
47	if (entry.first == map_.indvar()->get_name()) {	27✔
48	if (report_) {	×
49	report_->transform_impossible(this, "contains induction variable as argument " + entry.first);	×
50	}	×
51	return false;	×
52	}	×
53	}	27✔
54
55	// Check: all locals are scalar (implicitly converted into vectors)
56	symbolic::SymbolSet local_symbols;	9✔
57	for (auto& local : arguments_analysis.locals(analysis_manager, map_)) {	9✔
58	auto& type = builder.subject().type(local);	9✔
59	if (type.type_id() != types::TypeID::Scalar) {	9✔
60	if (report_) {	1✔
61	report_->transform_impossible(this, "contains non-scalar local " + local);	×
62	}	×
63	return false;	1✔
64	}	1✔
65	if (local == map_.indvar()->get_name()) {	8✔
66	continue;	8✔
67	}	8✔
68	if (types::is_integer(type.primitive_type())) {	×
69	local_symbols.insert(symbolic::symbol(local));	×
70	}	×
71	}	×
72
73	size_t bitwidth = 0;	8✔
74	std::list<structured_control_flow::ControlFlowNode*> queue = {&map_.root()};	8✔
75	while (!queue.empty()) {	24✔
76	auto node = queue.front();	16✔
77	queue.pop_front();	16✔
78
79	if (auto block = dynamic_cast<structured_control_flow::Block*>(node)) {	16✔
80	auto& graph = block->dataflow();	8✔
81	for (auto& edge : graph.edges()) {	16✔
82	if (edge.type() != data_flow::MemletType::Computational) {	16✔
83	if (report_) {	×
84	report_->transform_impossible(	×
85	this,	×
86	"contains unsupported memlet type on edge with element ID " +	×
87	std::to_string(edge.element_id())	×
88	);	×
89	}	×
90	return false;	×
UNCOV 91	}	×
92
93	size_t edge_bitwidth = types::bit_width(edge.base_type().primitive_type());	16✔
94	if (bitwidth == 0) {	16✔
95	bitwidth = edge_bitwidth;	8✔
96	} else if (edge_bitwidth != bitwidth) {	8✔
UNCOV 97	if (report_) {	×
UNCOV 98	report_->transform_impossible(	×
99	this,	×
100	"contains mismatched memlet bitwidth on edge with element ID " +	×
101	std::to_string(edge.element_id())	×
102	);	×
103	}	×
104	return false;	×
105	}	×
106
107	// Classify memlet access pattern
108	auto access_type = classify_memlet_access_type(edge.subset(), map_.indvar(), local_symbols);	16✔
109	if (access_type == HighwayTransform::CONSTANT) {	16✔
110	continue;	2✔
111	} else if (access_type == HighwayTransform::CONTIGUOUS) {	14✔
112	continue;	14✔
113	} else {	14✔
114	if (report_) {	×
115	report_->transform_impossible(	×
116	this,	×
117	"contains unsupported memlet access pattern on edge with element ID " +	×
118	std::to_string(edge.element_id())	×
119	);	×
120	}	×
121	return false;	×
122	}	×
123	}	16✔
124
125	for (auto& dnode : graph.topological_sort()) {	24✔
126	if (auto const_node = dynamic_cast<data_flow::ConstantNode*>(dnode)) {	24✔
UNCOV 127	if (const_node->type().type_id() != types::TypeID::Scalar) {	×
UNCOV 128	if (report_) {	×
UNCOV 129	report_->transform_impossible(	×
UNCOV 130	this,	×
131	"contains unsupported constant type on node with element ID " +	×
132	std::to_string(const_node->element_id())	×
133	);	×
134	}	×
135	return false;	×
136	}	×
137	continue;	×
138	}	×
139	if (auto access_node = dynamic_cast<data_flow::AccessNode*>(dnode)) {	24✔
140	continue;	16✔
141	}	16✔
142
143	if (auto tasklet = dynamic_cast<data_flow::Tasklet*>(dnode)) {	8✔
144	std::string code = highway::HighwayMapDispatcher::tasklet(*tasklet);	8✔
145	if (code.empty()) {	8✔
146	if (report_) {	×
147	report_->transform_impossible(	×
148	this,	×
149	"contains unsupported tasklet node with element ID " +	×
150	std::to_string(tasklet->element_id())	×
151	);	×
152	}	×
153	return false;	×
154	}	×
155	continue;	8✔
156	} else if (auto cmath_node = dynamic_cast<math::cmath::CMathNode*>(dnode)) {	8✔
157	std::string code = highway::HighwayMapDispatcher::cmath_node(*cmath_node);	×
158	if (code.empty()) {	×
159	if (report_) {	×
160	report_->transform_impossible(	×
161	this,	×
UNCOV 162	"contains unsupported CMath node with element ID " +	×
UNCOV 163	std::to_string(cmath_node->element_id())	×
UNCOV 164	);	×
UNCOV 165	}	×
166	return false;	×
167	}	×
168	continue;	×
169	} else {	×
170	if (report_) {	×
171	report_->transform_impossible(	×
172	this, "contains unsupported dataflow node of type " + std::string(typeid(*dnode).name())	×
173	);	×
174	}	×
UNCOV 175	return false;	×
UNCOV 176	}	×
177	}	8✔
178	} else if (auto sequence = dynamic_cast<structured_control_flow::Sequence*>(node)) {	8✔
179	for (size_t i = 0; i < sequence->size(); i++) {	16✔
180	if (sequence->at(i).second.assignments().size() > 0) {	8✔
181	if (report_) {	×
182	report_->transform_impossible(	×
183	this,	×
184	"contains unsupported transition with assignments at element ID " +	×
UNCOV 185	std::to_string(sequence->at(i).second.element_id())	×
UNCOV 186	);	×
UNCOV 187	}	×
UNCOV 188	return false;	×
UNCOV 189	}	×
190	queue.push_back(&sequence->at(i).first);	8✔
191	}	8✔
192	} else {	8✔
UNCOV 193	if (report_) {	×
UNCOV 194	report_->transform_impossible(	×
195	this, "contains unsupported control flow node of type " + std::string(typeid(*node).name())	×
196	);	×
197	}	×
198	return false;	×
199	}	×
200	}	16✔
201
202	return true;	8✔
203	}	8✔
204
205	void HighwayTransform::apply(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	8✔
206	builder.update_schedule_type(this->map_, highway::ScheduleType_Highway::create());	8✔
207	if (report_) report_->transform_applied(this);	8✔
208	}	8✔
209
210	void HighwayTransform::to_json(nlohmann::json& j) const {	×
211	j["transformation_type"] = this->name();	×
212	j["subgraph"] = {{"0", {{"element_id", this->map_.element_id()}, {"type", "map"}}}};	×
UNCOV 213	j["transformation_type"] = this->name();	×
214	}	×
215
UNCOV 216	HighwayTransform HighwayTransform::from_json(builder::StructuredSDFGBuilder& builder, const nlohmann::json& desc) {	×
UNCOV 217	auto map_id = desc["subgraph"]["0"]["element_id"].get<size_t>();	×
UNCOV 218	auto element = builder.find_element_by_id(map_id);	×
UNCOV 219	if (element == nullptr) {	×
UNCOV 220	throw std::runtime_error("Element with ID " + std::to_string(map_id) + " not found.");	×
UNCOV 221	}	×
222
223	auto loop = dynamic_cast<structured_control_flow::Map*>(element);	×
224
UNCOV 225	if (loop == nullptr) {	×
UNCOV 226	throw std::runtime_error("Element with ID " + std::to_string(map_id) + " is not a Map.");	×
UNCOV 227	}	×
228
UNCOV 229	return HighwayTransform(*loop);	×
UNCOV 230	}	×
231
232	HighwayTransform::MemletAccessType HighwayTransform::classify_memlet_access_type(
233	const data_flow::Subset& subset, const symbolic::Symbol& indvar, const symbolic::SymbolSet& local_symbols
234	) {	16✔
235	// Scalar access is constant
236	if (subset.empty()) {	16✔
237	return HighwayTransform::CONSTANT;	×
UNCOV 238	}	×
239
240	// Criterion: dim0, ..., dimN-1 are constant
241	for (size_t i = 0; i < subset.size() - 1; ++i) {	22✔
242	auto expr = subset.at(i);	6✔
243	bool is_constant = true;	6✔
244	for (auto& sym : symbolic::atoms(expr)) {	6✔
245	if (symbolic::eq(sym, indvar)) {	6✔
UNCOV 246	is_constant = false;	×
UNCOV 247	break;	×
UNCOV 248	}	×
249	if (local_symbols.find(sym) != local_symbols.end()) {	6✔
250	is_constant = false;	×
UNCOV 251	break;	×
UNCOV 252	}	×
253	}	6✔
254	if (!is_constant) {	6✔
UNCOV 255	return HighwayTransform::UNKNOWN;	×
UNCOV 256	}	×
257	}	6✔
258
259	// Classify dimN
260	auto dimN = subset.back();	16✔
261	for (auto& sym : symbolic::atoms(dimN)) {	18✔
262	// Gather / Scatter - extend here
263	if (local_symbols.find(sym) != local_symbols.end()) {	18✔
264	return HighwayTransform::UNKNOWN;	×
265	}	×
266	}	18✔
267	if (symbolic::uses(dimN, indvar)) {	16✔
268	if (symbolic::eq(dimN, indvar)) {	14✔
269	return HighwayTransform::CONTIGUOUS;	13✔
270	}	13✔
271
272	symbolic::SymbolVec poly_gens = {indvar};	1✔
273	auto poly = symbolic::polynomial(dimN, poly_gens);	1✔
274	if (poly.is_null()) {	1✔
UNCOV 275	return HighwayTransform::UNKNOWN;	×
UNCOV 276	}	×
277	auto affine_coeffs = symbolic::affine_coefficients(poly, poly_gens);	1✔
278	if (affine_coeffs.size() != 2) {	1✔
UNCOV 279	return HighwayTransform::UNKNOWN;	×
UNCOV 280	}	×
281	auto mul_coeff = affine_coeffs.at(indvar);	1✔
282	if (symbolic::eq(mul_coeff, symbolic::zero())) {	1✔
UNCOV 283	return HighwayTransform::CONSTANT;	×
UNCOV 284	}	×
285	if (symbolic::eq(mul_coeff, symbolic::one())) {	1✔
286	return HighwayTransform::CONTIGUOUS;	1✔
287	}	1✔
288
UNCOV 289	return HighwayTransform::UNKNOWN;	×
290	}	1✔
291
292	// dimN does not use indvar or moving symbols -> constant
293	return HighwayTransform::CONSTANT;	2✔
294	}	16✔
295
296	} // namespace transformations
297	} // namespace sdfg

daisytuner / docc / 22941264241

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