18625138218

Committed 16 Oct 2025 02:58PM UTC coverage: 61.539% (+0.3%) from 61.233%

Build # 18625138218

Build Type

push

github

Committed by

web-flow

Commit Message

FlopAnalysis on SDFGs to create an expression of used FLOPs (#280)

* Added FlopAnalysis to create an expression of used FLOPs

* Added FlopAnalysis to instrumentation codegen

* Better test cases & explore children of while loops

* Format fix

* Replace loop indvars by assumptions (upper_bound - lower_bound) / 2

* Use assumption analysis instead of loop analysis

* Safe instrumentation for -O0

Run Details

122 of 157 new or added lines in 6 files covered. (77.71%)

1 existing line in 1 file now uncovered.

9117 of 14815 relevant lines covered (61.54%)

99.5 hits per line

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

83.58

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

    auto init = loop.init();

    auto indvar = loop.indvar();
    symbolic::SymbolVec symbols = {indvar};
    auto update_polynomial = symbolic::polynomial(loop.update(), symbols);
    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 {
NEW 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✔
NEW 88	if (!block_assumptions.contains(sym)) continue;	×
NEW 89	symbolic::Assumption assumption = block_assumptions.at(sym);	×
NEW 90	if (!assumption.constant() \|\| assumption.map().is_null()) continue;	×
NEW 91	libnodes_result = symbolic::subs(	×
NEW 92	libnodes_result,	×
NEW 93	sym,	×
NEW 94	symbolic::div(symbolic::sub(assumption.upper_bound(), assumption.lower_bound()), symbolic::integer(2))	×
95	);
NEW 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
110	auto init = loop.init();	13✔
111
112	auto indvar = loop.indvar();	13✔
113	symbolic::SymbolVec symbols = {indvar};	13✔
114	auto update_polynomial = symbolic::polynomial(loop.update(), symbols);	13✔
115	auto update_coeffs = symbolic::affine_coefficients(update_polynomial, symbols);	13✔
116
117	// For now, only allow polynomial of the form: 1 * indvar + n
118	assert(update_coeffs.contains(indvar) && symbolic::eq(update_coeffs[indvar], symbolic::one()));	26✔
119	symbolic::Expression stride = update_coeffs[symbolic::symbol("__daisy_constant__")];	13✔
120
121	// Filter the loop index variables in bound, init, and stride, and replace them by (upper_bound - lower_bound) / 2
122	auto loop_assumptions = assumptions_analysis.get(loop.root());	13✔
123	auto bound_atoms = symbolic::atoms(bound);	13✔
124	for (auto sym : bound_atoms) {	19✔
125	if (!loop_assumptions.contains(sym)) continue;	6✔
126	symbolic::Assumption assumption = loop_assumptions.at(sym);	6✔
127	if (!assumption.constant() \|\| assumption.map().is_null()) continue;	6✔
NEW 128	bound = symbolic::subs(	×
NEW 129	bound,	×
NEW 130	sym,	×
NEW 131	symbolic::div(symbolic::sub(assumption.upper_bound(), assumption.lower_bound()), symbolic::integer(2))	×
132	);
133	}	6✔
134	auto init_atoms = symbolic::atoms(init);	13✔
135	for (auto sym : init_atoms) {	14✔
136	if (!loop_assumptions.contains(sym)) continue;	1✔
137	symbolic::Assumption assumption = loop_assumptions.at(sym);	1✔
138	if (!assumption.constant() \|\| assumption.map().is_null()) continue;	1✔
139	init = symbolic::subs(	1✔
140	init,	1✔
141	sym,	1✔
142	symbolic::div(symbolic::sub(assumption.upper_bound(), assumption.lower_bound()), symbolic::integer(2))	1✔
143	);
144	}	1✔
145	auto stride_atoms = symbolic::atoms(stride);	13✔
146	for (auto sym : stride_atoms) {	13✔
NEW 147	if (!loop_assumptions.contains(sym)) continue;	×
NEW 148	symbolic::Assumption assumption = loop_assumptions.at(sym);	×
NEW 149	if (!assumption.constant() \|\| assumption.map().is_null()) continue;	×
NEW 150	stride = symbolic::subs(	×
NEW 151	stride,	×
NEW 152	sym,	×
NEW 153	symbolic::div(symbolic::sub(assumption.upper_bound(), assumption.lower_bound()), symbolic::integer(2))	×
154	);
NEW 155	}	×
156
157	return symbolic::mul(symbolic::div(symbolic::sub(bound, init), stride), tmp);	13✔
158	}	13✔
159
160	symbolic::Expression FlopAnalysis::
161	visit_if_else(structured_control_flow::IfElse& if_else, AnalysisManager& analysis_manager) {	4✔
162	if (if_else.size() == 0) return symbolic::zero();	4✔
163
164	std::vector<symbolic::Expression> sub_flops;	3✔
165	bool is_null = false;	3✔
166
167	for (size_t i = 0; i < if_else.size(); i++) {	9✔
168	symbolic::Expression tmp = this->visit_sequence(if_else.at(i).first, analysis_manager);	6✔
169	this->flops_[&if_else.at(i).first] = tmp;	6✔
170	if (tmp.is_null()) is_null = true;	6✔
171	if (!is_null) sub_flops.push_back(tmp);	6✔
172	}	6✔
173
174	if (is_null) return SymEngine::null;	3✔
175	return SymEngine::max(sub_flops);	3✔
176	}	4✔
177
178	symbolic::Expression FlopAnalysis::visit_while(structured_control_flow::While& loop, AnalysisManager& analysis_manager) {	7✔
179	this->flops_[&loop.root()] = this->visit_sequence(loop.root(), analysis_manager);	7✔
180	// Return null because there is now good way to simply estimate the FLOPs of a while loop
181	return SymEngine::null;	7✔
NEW 182	}	×
183
184	void FlopAnalysis::run(AnalysisManager& analysis_manager) {	50✔
185	this->flops_.clear();	50✔
186	this->flops_[&this->sdfg_.root()] = this->visit_sequence(this->sdfg_.root(), analysis_manager);	50✔
187	}	50✔
188
189	FlopAnalysis::FlopAnalysis(StructuredSDFG& sdfg) : Analysis(sdfg) {}	50✔
190
191	bool FlopAnalysis::contains(const structured_control_flow::ControlFlowNode* node) {	31✔
192	return this->flops_.contains(node);	31✔
193	}
194
195	symbolic::Expression FlopAnalysis::get(const structured_control_flow::ControlFlowNode* node) {	31✔
196	return this->flops_[node];	31✔
197	}
198
199	std::unordered_map<const structured_control_flow::ControlFlowNode*, symbolic::Expression> FlopAnalysis::get() {	42✔
200	return this->flops_;	42✔
201	}
202
203	} // namespace analysis
204	} // namespace sdfg

daisytuner / sdfglib / 18625138218

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