18651924023

Committed 20 Oct 2025 12:26PM UTC coverage: 60.977% (-0.6%) from 61.539%

Build # 18651924023

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #286 from daisytuner/reserved-names

removes restricted globals filtering in codegen

Run Details

8 of 20 new or added lines in 2 files covered. (40.0%)

342 existing lines in 17 files now uncovered.

9174 of 15045 relevant lines covered (60.98%)

92.1 hits per line

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

82.61

/src/analysis/flop_analysis.cpp

#include "sdfg/analysis/flop_analysis.h"
#include <cassert>
#include <cstddef>
#include <unordered_map>
#include <vector>
#include "sdfg/analysis/analysis.h"
#include "sdfg/analysis/assumptions_analysis.h"
#include "sdfg/analysis/loop_analysis.h"
#include "sdfg/data_flow/tasklet.h"
#include "sdfg/structured_control_flow/block.h"
#include "sdfg/structured_control_flow/control_flow_node.h"
#include "sdfg/structured_control_flow/if_else.h"
#include "sdfg/structured_control_flow/return.h"
#include "sdfg/structured_control_flow/sequence.h"
#include "sdfg/structured_control_flow/structured_loop.h"
#include "sdfg/structured_control_flow/while.h"
#include "sdfg/structured_sdfg.h"
#include "sdfg/symbolic/assumptions.h"
#include "sdfg/symbolic/polynomials.h"
#include "sdfg/symbolic/symbolic.h"
#include "symengine/symengine_rcp.h"

namespace sdfg {
namespace analysis {

symbolic::Expression FlopAnalysis::visit(structured_control_flow::ControlFlowNode& node, AnalysisManager& analysis_manager) {
    if (auto sequence = dynamic_cast<structured_control_flow::Sequence*>(&node)) {
        return this->visit_sequence(*sequence, analysis_manager);
    } else if (auto block = dynamic_cast<structured_control_flow::Block*>(&node)) {
        return this->visit_block(*block, analysis_manager);
    } else if (auto structured_loop = dynamic_cast<structured_control_flow::StructuredLoop*>(&node)) {
        return this->visit_structured_loop(*structured_loop, analysis_manager);
    } else if (auto if_else = dynamic_cast<structured_control_flow::IfElse*>(&node)) {
        return this->visit_if_else(*if_else, analysis_manager);
    } else if (auto while_loop = dynamic_cast<structured_control_flow::While*>(&node)) {
        return this->visit_while(*while_loop, analysis_manager);
    } else if (dynamic_cast<structured_control_flow::Return*>(&node)) {
        return symbolic::zero();
    } else if (dynamic_cast<structured_control_flow::Break*>(&node)) {
        return symbolic::zero();
    } else if (dynamic_cast<structured_control_flow::Continue*>(&node)) {
        return symbolic::zero();
    } else {
        return SymEngine::null;
    }
}

symbolic::Expression FlopAnalysis::
    visit_sequence(structured_control_flow::Sequence& sequence, AnalysisManager& analysis_manager) {
    symbolic::Expression result = symbolic::zero();
    bool is_null = false;

    for (size_t i = 0; i < sequence.size(); i++) {
        symbolic::Expression tmp = this->visit(sequence.at(i).first, analysis_manager);
        this->flops_[&sequence.at(i).first] = tmp;
        if (tmp.is_null()) is_null = true;
        if (!is_null) result = symbolic::add(result, tmp);
    }

    if (is_null) return SymEngine::null;
    return result;
}

symbolic::Expression FlopAnalysis::visit_block(structured_control_flow::Block& block, AnalysisManager& analysis_manager) {
    auto& dfg = block.dataflow();

    symbolic::Expression tasklets_result = symbolic::zero();
    for (auto tasklet : dfg.tasklets()) {
        if (tasklet->code() == data_flow::TaskletCode::fp_fma) {
            tasklets_result = symbolic::add(tasklets_result, symbolic::integer(2));
        } else if (data_flow::is_floating_point(tasklet->code())) {
            tasklets_result = symbolic::add(tasklets_result, symbolic::one());
        }
    }

    symbolic::Expression libnodes_result = symbolic::zero();
    for (auto libnode : dfg.library_nodes()) {
        symbolic::Expression tmp = libnode->flop();
        if (tmp.is_null()) return SymEngine::null;
        libnodes_result = symbolic::add(libnodes_result, tmp);
    }

    // Filter the loop index variables in libnodes_result, and replace them by (upper_bound - lower_bound) / 2
    auto& assumptions_analysis = analysis_manager.get<AssumptionsAnalysis>();
    auto block_assumptions = assumptions_analysis.get(block);
    auto libnodes_result_atoms = symbolic::atoms(libnodes_result);
    for (auto sym : libnodes_result_atoms) {
        if (!block_assumptions.contains(sym)) continue;
        symbolic::Assumption assumption = block_assumptions.at(sym);
        if (!assumption.constant() || assumption.map().is_null()) continue;
        libnodes_result = symbolic::subs(
            libnodes_result,
            sym,
            symbolic::div(symbolic::sub(assumption.upper_bound(), assumption.lower_bound()), symbolic::integer(2))
        );
    }

    return symbolic::add(tasklets_result, libnodes_result);
}

symbolic::Expression FlopAnalysis::
    visit_structured_loop(structured_control_flow::StructuredLoop& loop, AnalysisManager& analysis_manager) {
    symbolic::Expression tmp = this->visit_sequence(loop.root(), analysis_manager);
    this->flops_[&loop.root()] = tmp;
    if (tmp.is_null()) return SymEngine::null;

    auto& assumptions_analysis = analysis_manager.get<AssumptionsAnalysis>();
    auto bound = LoopAnalysis::canonical_bound(&loop, assumptions_analysis);
    if (bound.is_null()) {
        return SymEngine::null;
    }

    auto init = loop.init();

    auto indvar = loop.indvar();
    symbolic::SymbolVec symbols = {indvar};
    auto update_polynomial = symbolic::polynomial(loop.update(), symbols);
    if (update_polynomial.is_null()) {
        return SymEngine::null;
    }
    auto update_coeffs = symbolic::affine_coefficients(update_polynomial, symbols);

    // For now, only allow polynomial of the form: 1 * indvar + n
    assert(update_coeffs.contains(indvar) && symbolic::eq(update_coeffs[indvar], symbolic::one()));
    symbolic::Expression stride = update_coeffs[symbolic::symbol("__daisy_constant__")];

    // Filter the loop index variables in bound, init, and stride, and replace them by (upper_bound - lower_bound) / 2
    auto loop_assumptions = assumptions_analysis.get(loop.root());
    auto bound_atoms = symbolic::atoms(bound);
    for (auto sym : bound_atoms) {
        if (!loop_assumptions.contains(sym)) continue;
        symbolic::Assumption assumption = loop_assumptions.at(sym);
        if (!assumption.constant() || assumption.map().is_null()) continue;
        bound = symbolic::subs(
            bound,
            sym,
            symbolic::div(symbolic::sub(assumption.upper_bound(), assumption.lower_bound()), symbolic::integer(2))
        );
    }
    auto init_atoms = symbolic::atoms(init);
    for (auto sym : init_atoms) {
        if (!loop_assumptions.contains(sym)) continue;
        symbolic::Assumption assumption = loop_assumptions.at(sym);
        if (!assumption.constant() || assumption.map().is_null()) continue;
        init = symbolic::subs(
            init,
            sym,
            symbolic::div(symbolic::sub(assumption.upper_bound(), assumption.lower_bound()), symbolic::integer(2))
        );
    }
    auto stride_atoms = symbolic::atoms(stride);
    for (auto sym : stride_atoms) {
        if (!loop_assumptions.contains(sym)) continue;
        symbolic::Assumption assumption = loop_assumptions.at(sym);
        if (!assumption.constant() || assumption.map().is_null()) continue;
        stride = symbolic::subs(
            stride,
            sym,
            symbolic::div(symbolic::sub(assumption.upper_bound(), assumption.lower_bound()), symbolic::integer(2))
        );
    }

    return symbolic::mul(symbolic::div(symbolic::sub(bound, init), stride), tmp);
}

symbolic::Expression FlopAnalysis::
    visit_if_else(structured_control_flow::IfElse& if_else, AnalysisManager& analysis_manager) {
    if (if_else.size() == 0) return symbolic::zero();

    std::vector<symbolic::Expression> sub_flops;
    bool is_null = false;

    for (size_t i = 0; i < if_else.size(); i++) {
        symbolic::Expression tmp = this->visit_sequence(if_else.at(i).first, analysis_manager);
        this->flops_[&if_else.at(i).first] = tmp;
        if (tmp.is_null()) is_null = true;
        if (!is_null) sub_flops.push_back(tmp);
    }

    if (is_null) return SymEngine::null;
    return SymEngine::max(sub_flops);
}

symbolic::Expression FlopAnalysis::visit_while(structured_control_flow::While& loop, AnalysisManager& analysis_manager) {
    this->flops_[&loop.root()] = this->visit_sequence(loop.root(), analysis_manager);
    // Return null because there is now good way to simply estimate the FLOPs of a while loop
    return SymEngine::null;
}

void FlopAnalysis::run(AnalysisManager& analysis_manager) {
    this->flops_.clear();
    this->flops_[&this->sdfg_.root()] = this->visit_sequence(this->sdfg_.root(), analysis_manager);
}

FlopAnalysis::FlopAnalysis(StructuredSDFG& sdfg) : Analysis(sdfg) {}

bool FlopAnalysis::contains(const structured_control_flow::ControlFlowNode* node) {
    return this->flops_.contains(node);
}

symbolic::Expression FlopAnalysis::get(const structured_control_flow::ControlFlowNode* node) {
    return this->flops_[node];
}

std::unordered_map<const structured_control_flow::ControlFlowNode*, symbolic::Expression> FlopAnalysis::get() {
    return this->flops_;
}

} // namespace analysis
} // namespace sdfg

1	#include "sdfg/analysis/flop_analysis.h"
2	#include <cassert>
3	#include <cstddef>
4	#include <unordered_map>
5	#include <vector>
6	#include "sdfg/analysis/analysis.h"
7	#include "sdfg/analysis/assumptions_analysis.h"
8	#include "sdfg/analysis/loop_analysis.h"
9	#include "sdfg/data_flow/tasklet.h"
10	#include "sdfg/structured_control_flow/block.h"
11	#include "sdfg/structured_control_flow/control_flow_node.h"
12	#include "sdfg/structured_control_flow/if_else.h"
13	#include "sdfg/structured_control_flow/return.h"
14	#include "sdfg/structured_control_flow/sequence.h"
15	#include "sdfg/structured_control_flow/structured_loop.h"
16	#include "sdfg/structured_control_flow/while.h"
17	#include "sdfg/structured_sdfg.h"
18	#include "sdfg/symbolic/assumptions.h"
19	#include "sdfg/symbolic/polynomials.h"
20	#include "sdfg/symbolic/symbolic.h"
21	#include "symengine/symengine_rcp.h"
22
23	namespace sdfg {
24	namespace analysis {
25
26	symbolic::Expression FlopAnalysis::visit(structured_control_flow::ControlFlowNode& node, AnalysisManager& analysis_manager) {	48✔
27	if (auto sequence = dynamic_cast<structured_control_flow::Sequence*>(&node)) {	48✔
28	return this->visit_sequence(*sequence, analysis_manager);	1✔
29	} else if (auto block = dynamic_cast<structured_control_flow::Block*>(&node)) {	47✔
30	return this->visit_block(*block, analysis_manager);	16✔
31	} else if (auto structured_loop = dynamic_cast<structured_control_flow::StructuredLoop*>(&node)) {	31✔
32	return this->visit_structured_loop(*structured_loop, analysis_manager);	13✔
33	} else if (auto if_else = dynamic_cast<structured_control_flow::IfElse*>(&node)) {	18✔
34	return this->visit_if_else(*if_else, analysis_manager);	4✔
35	} else if (auto while_loop = dynamic_cast<structured_control_flow::While*>(&node)) {	14✔
36	return this->visit_while(*while_loop, analysis_manager);	7✔
37	} else if (dynamic_cast<structured_control_flow::Return*>(&node)) {	7✔
38	return symbolic::zero();	2✔
39	} else if (dynamic_cast<structured_control_flow::Break*>(&node)) {	5✔
40	return symbolic::zero();	3✔
41	} else if (dynamic_cast<structured_control_flow::Continue*>(&node)) {	2✔
42	return symbolic::zero();	2✔
43	} else {
44	return SymEngine::null;	×
45	}
46	}	48✔
47
48	symbolic::Expression FlopAnalysis::
49	visit_sequence(structured_control_flow::Sequence& sequence, AnalysisManager& analysis_manager) {	77✔
50	symbolic::Expression result = symbolic::zero();	77✔
51	bool is_null = false;	77✔
52
53	for (size_t i = 0; i < sequence.size(); i++) {	125✔
54	symbolic::Expression tmp = this->visit(sequence.at(i).first, analysis_manager);	48✔
55	this->flops_[&sequence.at(i).first] = tmp;	48✔
56	if (tmp.is_null()) is_null = true;	48✔
57	if (!is_null) result = symbolic::add(result, tmp);	48✔
58	}	48✔
59
60	if (is_null) return SymEngine::null;	77✔
61	return result;	70✔
62	}	77✔
63
64	symbolic::Expression FlopAnalysis::visit_block(structured_control_flow::Block& block, AnalysisManager& analysis_manager) {	16✔
65	auto& dfg = block.dataflow();	16✔
66
67	symbolic::Expression tasklets_result = symbolic::zero();	16✔
68	for (auto tasklet : dfg.tasklets()) {	29✔
69	if (tasklet->code() == data_flow::TaskletCode::fp_fma) {	13✔
70	tasklets_result = symbolic::add(tasklets_result, symbolic::integer(2));	3✔
71	} else if (data_flow::is_floating_point(tasklet->code())) {	13✔
72	tasklets_result = symbolic::add(tasklets_result, symbolic::one());	6✔
73	}	6✔
74	}
75
76	symbolic::Expression libnodes_result = symbolic::zero();	16✔
77	for (auto libnode : dfg.library_nodes()) {	17✔
78	symbolic::Expression tmp = libnode->flop();	1✔
79	if (tmp.is_null()) return SymEngine::null;	1✔
80	libnodes_result = symbolic::add(libnodes_result, tmp);	1✔
81	}	1✔
82
83	// Filter the loop index variables in libnodes_result, and replace them by (upper_bound - lower_bound) / 2
84	auto& assumptions_analysis = analysis_manager.get<AssumptionsAnalysis>();	16✔
85	auto block_assumptions = assumptions_analysis.get(block);	16✔
86	auto libnodes_result_atoms = symbolic::atoms(libnodes_result);	16✔
87	for (auto sym : libnodes_result_atoms) {	16✔
88	if (!block_assumptions.contains(sym)) continue;	×
89	symbolic::Assumption assumption = block_assumptions.at(sym);	×
90	if (!assumption.constant() \|\| assumption.map().is_null()) continue;	×
91	libnodes_result = symbolic::subs(	×
92	libnodes_result,	×
93	sym,	×
94	symbolic::div(symbolic::sub(assumption.upper_bound(), assumption.lower_bound()), symbolic::integer(2))	×
95	);
96	}	×
97
98	return symbolic::add(tasklets_result, libnodes_result);	16✔
99	}	16✔
100
101	symbolic::Expression FlopAnalysis::
102	visit_structured_loop(structured_control_flow::StructuredLoop& loop, AnalysisManager& analysis_manager) {	13✔
103	symbolic::Expression tmp = this->visit_sequence(loop.root(), analysis_manager);	13✔
104	this->flops_[&loop.root()] = tmp;	13✔
105	if (tmp.is_null()) return SymEngine::null;	13✔
106
107	auto& assumptions_analysis = analysis_manager.get<AssumptionsAnalysis>();	13✔
108	auto bound = LoopAnalysis::canonical_bound(&loop, assumptions_analysis);	13✔
109	if (bound.is_null()) {	13✔
UNCOV 110	return SymEngine::null;	×
111	}
112
113	auto init = loop.init();	13✔
114
115	auto indvar = loop.indvar();	13✔
116	symbolic::SymbolVec symbols = {indvar};	13✔
117	auto update_polynomial = symbolic::polynomial(loop.update(), symbols);	13✔
118	if (update_polynomial.is_null()) {	13✔
UNCOV 119	return SymEngine::null;	×
120	}
121	auto update_coeffs = symbolic::affine_coefficients(update_polynomial, symbols);	13✔
122
123	// For now, only allow polynomial of the form: 1 * indvar + n
124	assert(update_coeffs.contains(indvar) && symbolic::eq(update_coeffs[indvar], symbolic::one()));	26✔
125	symbolic::Expression stride = update_coeffs[symbolic::symbol("__daisy_constant__")];	13✔
126
127	// Filter the loop index variables in bound, init, and stride, and replace them by (upper_bound - lower_bound) / 2
128	auto loop_assumptions = assumptions_analysis.get(loop.root());	13✔
129	auto bound_atoms = symbolic::atoms(bound);	13✔
130	for (auto sym : bound_atoms) {	19✔
131	if (!loop_assumptions.contains(sym)) continue;	6✔
132	symbolic::Assumption assumption = loop_assumptions.at(sym);	6✔
133	if (!assumption.constant() \|\| assumption.map().is_null()) continue;	6✔
UNCOV 134	bound = symbolic::subs(	×
UNCOV 135	bound,	×
UNCOV 136	sym,	×
UNCOV 137	symbolic::div(symbolic::sub(assumption.upper_bound(), assumption.lower_bound()), symbolic::integer(2))	×
138	);
139	}	6✔
140	auto init_atoms = symbolic::atoms(init);	13✔
141	for (auto sym : init_atoms) {	14✔
142	if (!loop_assumptions.contains(sym)) continue;	1✔
143	symbolic::Assumption assumption = loop_assumptions.at(sym);	1✔
144	if (!assumption.constant() \|\| assumption.map().is_null()) continue;	1✔
145	init = symbolic::subs(	1✔
146	init,	1✔
147	sym,	1✔
148	symbolic::div(symbolic::sub(assumption.upper_bound(), assumption.lower_bound()), symbolic::integer(2))	1✔
149	);
150	}	1✔
151	auto stride_atoms = symbolic::atoms(stride);	13✔
152	for (auto sym : stride_atoms) {	13✔
153	if (!loop_assumptions.contains(sym)) continue;	×
UNCOV 154	symbolic::Assumption assumption = loop_assumptions.at(sym);	×
155	if (!assumption.constant() \|\| assumption.map().is_null()) continue;	×
UNCOV 156	stride = symbolic::subs(	×
UNCOV 157	stride,	×
UNCOV 158	sym,	×
UNCOV 159	symbolic::div(symbolic::sub(assumption.upper_bound(), assumption.lower_bound()), symbolic::integer(2))	×
160	);
UNCOV 161	}	×
162
163	return symbolic::mul(symbolic::div(symbolic::sub(bound, init), stride), tmp);	13✔
164	}	13✔
165
166	symbolic::Expression FlopAnalysis::
167	visit_if_else(structured_control_flow::IfElse& if_else, AnalysisManager& analysis_manager) {	4✔
168	if (if_else.size() == 0) return symbolic::zero();	4✔
169
170	std::vector<symbolic::Expression> sub_flops;	3✔
171	bool is_null = false;	3✔
172
173	for (size_t i = 0; i < if_else.size(); i++) {	9✔
174	symbolic::Expression tmp = this->visit_sequence(if_else.at(i).first, analysis_manager);	6✔
175	this->flops_[&if_else.at(i).first] = tmp;	6✔
176	if (tmp.is_null()) is_null = true;	6✔
177	if (!is_null) sub_flops.push_back(tmp);	6✔
178	}	6✔
179
180	if (is_null) return SymEngine::null;	3✔
181	return SymEngine::max(sub_flops);	3✔
182	}	4✔
183
184	symbolic::Expression FlopAnalysis::visit_while(structured_control_flow::While& loop, AnalysisManager& analysis_manager) {	7✔
185	this->flops_[&loop.root()] = this->visit_sequence(loop.root(), analysis_manager);	7✔
186	// Return null because there is now good way to simply estimate the FLOPs of a while loop
187	return SymEngine::null;	7✔
UNCOV 188	}	×
189
190	void FlopAnalysis::run(AnalysisManager& analysis_manager) {	50✔
191	this->flops_.clear();	50✔
192	this->flops_[&this->sdfg_.root()] = this->visit_sequence(this->sdfg_.root(), analysis_manager);	50✔
193	}	50✔
194
195	FlopAnalysis::FlopAnalysis(StructuredSDFG& sdfg) : Analysis(sdfg) {}	50✔
196
197	bool FlopAnalysis::contains(const structured_control_flow::ControlFlowNode* node) {	31✔
198	return this->flops_.contains(node);	31✔
199	}
200
201	symbolic::Expression FlopAnalysis::get(const structured_control_flow::ControlFlowNode* node) {	31✔
202	return this->flops_[node];	31✔
203	}
204
205	std::unordered_map<const structured_control_flow::ControlFlowNode*, symbolic::Expression> FlopAnalysis::get() {	42✔
206	return this->flops_;	42✔
207	}
208
209	} // namespace analysis
210	} // namespace sdfg

daisytuner / sdfglib / 18651924023

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