21110710975

Committed 18 Jan 2026 11:07AM UTC coverage: 64.154% (+0.09%) from 64.062%

Build # 21110710975

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #461 from daisytuner/highway-transform

tests static dispatch of Google Highway with Python frontend

Run Details

14 of 24 new or added lines in 2 files covered. (58.33%)

2 existing lines in 1 file now uncovered.

19467 of 30344 relevant lines covered (64.15%)

388.07 hits per line

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

43.1

/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));
        }
    }

    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;
                }

                // 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✔
NEW 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_)) {	10✔
58	auto& type = builder.subject().type(local);	10✔
59	if (type.type_id() != types::TypeID::Scalar) {	10✔
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()) {	9✔
66	continue;	9✔
67	}	9✔
68	if (types::is_integer(type.primitive_type())) {	×
69	local_symbols.insert(symbolic::symbol(local));	×
70	}	×
71	}	×
72
73	std::list<structured_control_flow::ControlFlowNode*> queue = {&map_.root()};	8✔
74	while (!queue.empty()) {	24✔
75	auto node = queue.front();	16✔
76	queue.pop_front();	16✔
77
78	if (auto block = dynamic_cast<structured_control_flow::Block*>(node)) {	16✔
79	auto& graph = block->dataflow();	8✔
80	for (auto& edge : graph.edges()) {	16✔
81	if (edge.type() != data_flow::MemletType::Computational) {	16✔
82	if (report_) {	×
83	report_->transform_impossible(	×
84	this,	×
85	"contains unsupported memlet type on edge with element ID " +	×
86	std::to_string(edge.element_id())	×
87	);	×
88	}	×
89	return false;	×
90	}	×
91
92	// Classify memlet access pattern
93	auto access_type = classify_memlet_access_type(edge.subset(), map_.indvar(), local_symbols);	16✔
94	if (access_type == HighwayTransform::CONSTANT) {	16✔
95	continue;	2✔
96	} else if (access_type == HighwayTransform::CONTIGUOUS) {	14✔
97	continue;	14✔
98	} else {	14✔
99	if (report_) {	×
100	report_->transform_impossible(	×
101	this,	×
102	"contains unsupported memlet access pattern on edge with element ID " +	×
103	std::to_string(edge.element_id())	×
104	);	×
105	}	×
106	return false;	×
107	}	×
108	}	16✔
109
110	for (auto& dnode : graph.topological_sort()) {	24✔
111	if (auto const_node = dynamic_cast<data_flow::ConstantNode*>(dnode)) {	24✔
112	if (const_node->type().type_id() != types::TypeID::Scalar) {	×
113	if (report_) {	×
114	report_->transform_impossible(	×
115	this,	×
116	"contains unsupported constant type on node with element ID " +	×
117	std::to_string(const_node->element_id())	×
118	);	×
119	}	×
120	return false;	×
121	}	×
122	continue;	×
123	}	×
124	if (auto access_node = dynamic_cast<data_flow::AccessNode*>(dnode)) {	24✔
125	continue;	16✔
126	}	16✔
127
128	if (auto tasklet = dynamic_cast<data_flow::Tasklet*>(dnode)) {	8✔
129	std::string code = highway::HighwayMapDispatcher::tasklet(*tasklet);	8✔
130	if (code.empty()) {	8✔
131	if (report_) {	×
132	report_->transform_impossible(	×
133	this,	×
134	"contains unsupported tasklet node with element ID " +	×
135	std::to_string(tasklet->element_id())	×
136	);	×
137	}	×
138	return false;	×
139	}	×
140	continue;	8✔
141	} else if (auto cmath_node = dynamic_cast<math::cmath::CMathNode*>(dnode)) {	8✔
142	std::string code = highway::HighwayMapDispatcher::cmath_node(*cmath_node);	×
143	if (code.empty()) {	×
144	if (report_) {	×
145	report_->transform_impossible(	×
146	this,	×
147	"contains unsupported CMath node with element ID " +	×
148	std::to_string(cmath_node->element_id())	×
149	);	×
150	}	×
151	return false;	×
152	}	×
153	continue;	×
154	} else {	×
155	if (report_) {	×
156	report_->transform_impossible(	×
157	this, "contains unsupported dataflow node of type " + std::string(typeid(*dnode).name())	×
158	);	×
159	}	×
160	return false;	×
161	}	×
162	}	8✔
163	} else if (auto sequence = dynamic_cast<structured_control_flow::Sequence*>(node)) {	8✔
164	for (size_t i = 0; i < sequence->size(); i++) {	16✔
165	if (sequence->at(i).second.assignments().size() > 0) {	8✔
166	if (report_) {	×
167	report_->transform_impossible(	×
168	this,	×
169	"contains unsupported transition with assignments at element ID " +	×
170	std::to_string(sequence->at(i).second.element_id())	×
171	);	×
172	}	×
173	return false;	×
174	}	×
175	queue.push_back(&sequence->at(i).first);	8✔
176	}	8✔
177	} else {	8✔
178	if (report_) {	×
179	report_->transform_impossible(	×
180	this, "contains unsupported control flow node of type " + std::string(typeid(*node).name())	×
181	);	×
182	}	×
183	return false;	×
184	}	×
185	}	16✔
186
187	return true;	8✔
188	}	8✔
189
190	void HighwayTransform::apply(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	8✔
191	builder.update_schedule_type(this->map_, highway::ScheduleType_Highway::create());	8✔
192	if (report_) report_->transform_applied(this);	8✔
193	}	8✔
194
195	void HighwayTransform::to_json(nlohmann::json& j) const {	×
196	j["transformation_type"] = this->name();	×
197	j["subgraph"] = {{"0", {{"element_id", this->map_.element_id()}, {"type", "map"}}}};	×
198	j["transformation_type"] = this->name();	×
199	}	×
200
201	HighwayTransform HighwayTransform::from_json(builder::StructuredSDFGBuilder& builder, const nlohmann::json& desc) {	×
202	auto map_id = desc["subgraph"]["0"]["element_id"].get<size_t>();	×
203	auto element = builder.find_element_by_id(map_id);	×
204	if (element == nullptr) {	×
205	throw std::runtime_error("Element with ID " + std::to_string(map_id) + " not found.");	×
206	}	×
207
208	auto loop = dynamic_cast<structured_control_flow::Map*>(element);	×
209
210	if (loop == nullptr) {	×
211	throw std::runtime_error("Element with ID " + std::to_string(map_id) + " is not a Map.");	×
212	}	×
213
214	return HighwayTransform(*loop);	×
215	}	×
216
217	HighwayTransform::MemletAccessType HighwayTransform::classify_memlet_access_type(
218	const data_flow::Subset& subset, const symbolic::Symbol& indvar, const symbolic::SymbolSet& local_symbols
219	) {	16✔
220	// Scalar access is constant
221	if (subset.empty()) {	16✔
222	return HighwayTransform::CONSTANT;	×
223	}	×
224
225	// Criterion: dim0, ..., dimN-1 are constant
226	for (size_t i = 0; i < subset.size() - 1; ++i) {	22✔
227	auto expr = subset.at(i);	6✔
228	bool is_constant = true;	6✔
229	for (auto& sym : symbolic::atoms(expr)) {	6✔
230	if (symbolic::eq(sym, indvar)) {	6✔
231	is_constant = false;	×
232	break;	×
233	}	×
234	if (local_symbols.find(sym) != local_symbols.end()) {	6✔
235	is_constant = false;	×
236	break;	×
237	}	×
238	}	6✔
239	if (!is_constant) {	6✔
240	return HighwayTransform::UNKNOWN;	×
241	}	×
242	}	6✔
243
244	// Classify dimN
245	auto dimN = subset.back();	16✔
246	for (auto& sym : symbolic::atoms(dimN)) {	18✔
247	// Gather / Scatter - extend here
248	if (local_symbols.find(sym) != local_symbols.end()) {	18✔
249	return HighwayTransform::UNKNOWN;	×
250	}	×
251	}	18✔
252	if (symbolic::uses(dimN, indvar)) {	16✔
253	if (symbolic::eq(dimN, indvar)) {	14✔
254	return HighwayTransform::CONTIGUOUS;	13✔
255	}	13✔
256
257	symbolic::SymbolVec poly_gens = {indvar};	1✔
258	auto poly = symbolic::polynomial(dimN, poly_gens);	1✔
259	if (poly.is_null()) {	1✔
NEW 260	return HighwayTransform::UNKNOWN;	×
NEW 261	}	×
262	auto affine_coeffs = symbolic::affine_coefficients(poly, poly_gens);	1✔
263	if (affine_coeffs.size() != 2) {	1✔
264	return HighwayTransform::UNKNOWN;	×
265	}	×
266	auto mul_coeff = affine_coeffs.at(indvar);	1✔
267	if (symbolic::eq(mul_coeff, symbolic::zero())) {	1✔
NEW 268	return HighwayTransform::CONSTANT;	×
NEW 269	}	×
270	if (symbolic::eq(mul_coeff, symbolic::one())) {	1✔
271	return HighwayTransform::CONTIGUOUS;	1✔
272	}	1✔
273
NEW 274	return HighwayTransform::UNKNOWN;	×
275	}	1✔
276
277	// dimN does not use indvar or moving symbols -> constant
278	return HighwayTransform::CONSTANT;	2✔
279	}	16✔
280
281	} // namespace transformations
282	} // namespace sdfg

daisytuner / sdfglib / 21110710975

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