18776259427

Committed 24 Oct 2025 09:55AM UTC coverage: 61.726% (+0.07%) from 61.661%

Build # 18776259427

Build Type

push

github

Committed by

web-flow

Commit Message

Made FlopAnalysis scope aware (#300)

* Made FlopAnalysis scope aware

Parameters are now determined based on the scope of the visited node.

* Perform `get_scope_parameters` in linear time instead of quadratic

Run Details

80 of 93 new or added lines in 2 files covered. (86.02%)

2 existing lines in 1 file now uncovered.

9812 of 15896 relevant lines covered (61.73%)

103.37 hits per line

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

82.56

/src/analysis/flop_analysis.cpp

#include "sdfg/analysis/flop_analysis.h"
#include <cassert>
#include <cstddef>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include "sdfg/analysis/analysis.h"
#include "sdfg/analysis/assumptions_analysis.h"
#include "sdfg/analysis/loop_analysis.h"
#include "sdfg/analysis/scope_analysis.h"
#include "sdfg/analysis/users.h"
#include "sdfg/data_flow/tasklet.h"
#include "sdfg/exceptions.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/functions.h"
#include "symengine/symengine_rcp.h"

namespace sdfg {
namespace analysis {

/// An expression is a parameter expression if all its symbols are parameters
bool FlopAnalysis::is_parameter_expression(const symbolic::SymbolSet& parameters, const symbolic::Expression& expr) {
    if (expr.is_null()) {
        return false;
    }
    for (auto& sym : symbolic::atoms(expr)) {
        if (!parameters.contains(sym)) {
            return false;
        }
    }
    return true;
}

symbolic::ExpressionSet FlopAnalysis::
    choose_bounds(const symbolic::SymbolSet& parameters, const symbolic::ExpressionSet& bounds) {
    symbolic::ExpressionSet result;
    for (auto& bound : bounds) {
        if (symbolic::eq(bound, SymEngine::NegInf) || symbolic::eq(bound, SymEngine::Inf)) {
            // Skip infinities
            continue;
        } else if (SymEngine::is_a<SymEngine::Integer>(*bound)) {
            // Collect integers
            result.insert(bound);
        } else if (!symbolic::contains_dynamic_sizeof(bound) && this->is_parameter_expression(parameters, bound)) {
            // Collect parameter expressions if they do not contain dynamic_sizeof
            result.insert(bound);
        }
    }
    if (result.empty()) {
        // Fallback if no integers or parameter expressions were found
        return bounds;
    } else {
        return result;
    }
}

symbolic::Expression FlopAnalysis::replace_loop_indices(
    const symbolic::SymbolSet& parameters, const symbolic::Expression expr, symbolic::Assumptions& assumptions
) {
    symbolic::Expression result = expr;
    auto atoms = symbolic::atoms(result);
    for (auto sym : atoms) {
        if (!assumptions.contains(sym)) continue;
        symbolic::Assumption assumption = assumptions.at(sym);
        if (!assumption.constant() || assumption.map().is_null()) continue;
        symbolic::Expression ub, lb;
        if (assumption.tight_upper_bound().is_null()) {
            auto bounds = this->choose_bounds(parameters, assumption.upper_bounds());
            if (bounds.empty()) {
                ub = assumption.upper_bound();
            } else {
                ub = SymEngine::min(std::vector<symbolic::Expression>(bounds.begin(), bounds.end()));
            }
        } else {
            ub = assumption.tight_upper_bound();
        }
        if (assumption.tight_lower_bound().is_null()) {
            auto bounds = this->choose_bounds(parameters, assumption.lower_bounds());
            if (bounds.empty()) {
                lb = assumption.lower_bound();
            } else {
                lb = SymEngine::max(std::vector<symbolic::Expression>(bounds.begin(), bounds.end()));
            }
        } else {
            lb = assumption.tight_lower_bound();
        }
        result = symbolic::subs(result, sym, symbolic::div(symbolic::sub(ub, lb), symbolic::integer(2)));
        this->precise_ = false;
    }
    return result;
}

symbolic::SymbolSet FlopAnalysis::
    get_scope_parameters(const structured_control_flow::ControlFlowNode& scope, AnalysisManager& analysis_manager) {
    auto& users_analysis = analysis_manager.get<Users>();
    analysis::UsersView users_view(users_analysis, scope);

    std::unordered_set<std::string> all_uses, illegal_uses;
    for (auto* user : users_view.uses()) {
        Use not_allowed;
        switch (this->sdfg_.type(user->container()).type_id()) {
            case types::TypeID::Scalar:
                not_allowed = Use::WRITE;
                break;
            case types::TypeID::Pointer:
            case types::TypeID::Array:
                not_allowed = Use::MOVE;
                break;
            default:
                continue;
        }
        all_uses.insert(user->container());
        if (user->use() == not_allowed) {
            illegal_uses.insert(user->container());
        }
    }

    symbolic::SymbolSet parameters;
    for (auto& container : all_uses) {
        if (!illegal_uses.contains(container)) {
            parameters.insert(symbolic::symbol(container));
        }
    }

    return parameters;
}

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) ||
               dynamic_cast<structured_control_flow::Break*>(&node) ||
               dynamic_cast<structured_control_flow::Continue*>(&node)) {
        this->flops_[&node] = symbolic::zero();
        return symbolic::zero();
    } else {
        this->flops_[&node] = SymEngine::null;
        this->precise_ = false;
        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 child = this->visit(sequence.at(i).first, analysis_manager);
        if (child.is_null()) {
            is_null = true;
        }
        if (!is_null) {
            result = symbolic::add(result, child);
        }
    }

    if (is_null) {
        this->flops_[&sequence] = SymEngine::null;
        this->precise_ = false;
        return SymEngine::null;
    }
    this->flops_[&sequence] = result;
    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()) {
            this->precise_ = false;
            return SymEngine::null;
        }
        libnodes_result = symbolic::add(libnodes_result, tmp);
    }

    // Determine scope parameters
    symbolic::SymbolSet parameters = this->get_scope_parameters(block, analysis_manager);

    // 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);
    libnodes_result = this->replace_loop_indices(parameters, libnodes_result, block_assumptions);

    symbolic::Expression result = symbolic::add(tasklets_result, libnodes_result);
    this->flops_[&block] = result;
    return result;
}

symbolic::Expression FlopAnalysis::
    visit_structured_loop(structured_control_flow::StructuredLoop& loop, AnalysisManager& analysis_manager) {
    auto& scope_analysis = analysis_manager.get<ScopeAnalysis>();
    structured_control_flow::ControlFlowNode* parent = scope_analysis.parent_scope(&loop);
    if (!parent) {
        throw InvalidSDFGException("FlopAnalysis: Could not find parent scope of structured loop");
    }
    this->flops_[&loop] = this->visit_structured_loop_with_scope(loop, analysis_manager, loop);
    return this->visit_structured_loop_with_scope(loop, analysis_manager, *parent);
}

symbolic::Expression FlopAnalysis::visit_structured_loop_with_scope(
    structured_control_flow::StructuredLoop& loop,
    AnalysisManager& analysis_manager,
    structured_control_flow::ControlFlowNode& scope
) {
    symbolic::Expression child = this->visit_sequence(loop.root(), analysis_manager);
    if (child.is_null()) {
        this->precise_ = false;
        return SymEngine::null;
    }

    // Determine scope parameters
    symbolic::SymbolSet parameters = this->get_scope_parameters(scope, analysis_manager);

    // Require existance of assumptions for the loop indvar
    auto indvar = loop.indvar();
    auto& assumptions_analysis = analysis_manager.get<AssumptionsAnalysis>();
    auto loop_assumptions = assumptions_analysis.get(loop.root());
    if (!loop_assumptions.contains(indvar)) {
        this->precise_ = false;
        return SymEngine::null;
    }
    bool done;

    // Determine initial value of loop
    symbolic::Expression init = SymEngine::null;
    done = false;
    if (!loop_assumptions[indvar].tight_lower_bound().is_null()) {
        init = this->replace_loop_indices(parameters, loop_assumptions[indvar].tight_lower_bound(), loop_assumptions);
        done = this->is_parameter_expression(parameters, init);
    }
    if (!done && !symbolic::eq(loop_assumptions[indvar].lower_bound(), SymEngine::NegInf)) {
        auto bounds = this->choose_bounds(parameters, loop_assumptions[indvar].lower_bounds());
        if (!bounds.empty()) {
            init = this->replace_loop_indices(
                parameters,
                SymEngine::max(std::vector<symbolic::Expression>(bounds.begin(), bounds.end())),
                loop_assumptions
            );
            this->precise_ = false;
            done = this->is_parameter_expression(parameters, init);
        }
    }
    if (!done) {
        init = this->replace_loop_indices(parameters, loop.init(), loop_assumptions);
        this->precise_ = false;
    }
    if (init.is_null()) {
        this->precise_ = false;
        return SymEngine::null;
    }

    // Determine bound of loop
    symbolic::Expression bound;
    done = false;
    if (!loop_assumptions[indvar].tight_upper_bound().is_null()) {
        bound = this->replace_loop_indices(parameters, loop_assumptions[indvar].tight_upper_bound(), loop_assumptions);
        done = this->is_parameter_expression(parameters, bound);
    }
    if (!done && !symbolic::eq(loop_assumptions[indvar].upper_bound(), SymEngine::Inf)) {
        auto bounds = this->choose_bounds(parameters, loop_assumptions[indvar].upper_bounds());
        if (!bounds.empty()) {
            bound = this->replace_loop_indices(
                parameters,
                SymEngine::min(std::vector<symbolic::Expression>(bounds.begin(), bounds.end())),
                loop_assumptions
            );
            this->precise_ = false;
            done = this->is_parameter_expression(parameters, bound);
        }
    }
    if (!done) {
        auto canonical_bound = LoopAnalysis::canonical_bound(&loop, assumptions_analysis);
        if (!canonical_bound.is_null()) {
            bound =
                this->replace_loop_indices(parameters, symbolic::sub(canonical_bound, symbolic::one()), loop_assumptions);
            this->precise_ = false;
        }
    }
    if (bound.is_null()) {
        this->precise_ = false;
        return SymEngine::null;
    }

    // Determine stride of loop
    symbolic::SymbolVec symbols = {indvar};
    auto update_polynomial = symbolic::polynomial(loop.update(), symbols);
    if (update_polynomial.is_null()) {
        this->precise_ = false;
        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 =
        this->replace_loop_indices(parameters, update_coeffs[symbolic::symbol("__daisy_constant__")], loop_assumptions);

    return symbolic::mul(symbolic::div(symbolic::add(symbolic::sub(bound, init), symbolic::one()), stride), child);
}

symbolic::Expression FlopAnalysis::
    visit_if_else(structured_control_flow::IfElse& if_else, AnalysisManager& analysis_manager) {
    if (if_else.size() == 0) {
        this->flops_[&if_else] = symbolic::zero();
        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 child = this->visit_sequence(if_else.at(i).first, analysis_manager);
        if (child.is_null()) {
            is_null = true;
        }
        if (!is_null) {
            sub_flops.push_back(child);
        }
    }

    this->precise_ = false;
    if (is_null) {
        this->flops_[&if_else] = SymEngine::null;
        return SymEngine::null;
    }
    symbolic::Expression result = SymEngine::max(sub_flops);
    this->flops_[&if_else] = result;
    return result;
}

symbolic::Expression FlopAnalysis::visit_while(structured_control_flow::While& loop, AnalysisManager& analysis_manager) {
    this->visit_sequence(loop.root(), analysis_manager);
    this->flops_[&loop] = SymEngine::null;
    this->precise_ = false;
    // 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->precise_ = true;

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

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

bool FlopAnalysis::precise() { return this->precise_; }

} // namespace analysis
} // namespace sdfg

1	#include "sdfg/analysis/flop_analysis.h"
2	#include <cassert>
3	#include <cstddef>
4	#include <string>
5	#include <unordered_map>
6	#include <unordered_set>
7	#include <vector>
8	#include "sdfg/analysis/analysis.h"
9	#include "sdfg/analysis/assumptions_analysis.h"
10	#include "sdfg/analysis/loop_analysis.h"
11	#include "sdfg/analysis/scope_analysis.h"
12	#include "sdfg/analysis/users.h"
13	#include "sdfg/data_flow/tasklet.h"
14	#include "sdfg/exceptions.h"
15	#include "sdfg/structured_control_flow/block.h"
16	#include "sdfg/structured_control_flow/control_flow_node.h"
17	#include "sdfg/structured_control_flow/if_else.h"
18	#include "sdfg/structured_control_flow/return.h"
19	#include "sdfg/structured_control_flow/sequence.h"
20	#include "sdfg/structured_control_flow/structured_loop.h"
21	#include "sdfg/structured_control_flow/while.h"
22	#include "sdfg/structured_sdfg.h"
23	#include "sdfg/symbolic/assumptions.h"
24	#include "sdfg/symbolic/polynomials.h"
25	#include "sdfg/symbolic/symbolic.h"
26	#include "symengine/functions.h"
27	#include "symengine/symengine_rcp.h"
28
29	namespace sdfg {
30	namespace analysis {
31
32	/// An expression is a parameter expression if all its symbols are parameters
33	bool FlopAnalysis::is_parameter_expression(const symbolic::SymbolSet& parameters, const symbolic::Expression& expr) {	55✔
34	if (expr.is_null()) {	55✔
35	return false;	×
36	}
37	for (auto& sym : symbolic::atoms(expr)) {	91✔
38	if (!parameters.contains(sym)) {	36✔
39	return false;	11✔
40	}
41	}
42	return true;	44✔
43	}	55✔
44
45	symbolic::ExpressionSet FlopAnalysis::
46	choose_bounds(const symbolic::SymbolSet& parameters, const symbolic::ExpressionSet& bounds) {	11✔
47	symbolic::ExpressionSet result;	11✔
48	for (auto& bound : bounds) {	20✔
49	if (symbolic::eq(bound, SymEngine::NegInf) \|\| symbolic::eq(bound, SymEngine::Inf)) {	9✔
50	// Skip infinities
51	continue;	×
52	} else if (SymEngine::is_a<SymEngine::Integer>(*bound)) {	9✔
53	// Collect integers
54	result.insert(bound);	3✔
55	} else if (!symbolic::contains_dynamic_sizeof(bound) && this->is_parameter_expression(parameters, bound)) {	9✔
56	// Collect parameter expressions if they do not contain dynamic_sizeof
57	result.insert(bound);	×
58	}	×
59	}
60	if (result.empty()) {	11✔
61	// Fallback if no integers or parameter expressions were found
62	return bounds;	8✔
63	} else {
64	return result;	3✔
65	}
66	}	11✔
67
68	symbolic::Expression FlopAnalysis::replace_loop_indices(	122✔
69	const symbolic::SymbolSet& parameters, const symbolic::Expression expr, symbolic::Assumptions& assumptions
70	) {
71	symbolic::Expression result = expr;	122✔
72	auto atoms = symbolic::atoms(result);	122✔
73	for (auto sym : atoms) {	170✔
74	if (!assumptions.contains(sym)) continue;	48✔
75	symbolic::Assumption assumption = assumptions.at(sym);	42✔
76	if (!assumption.constant() \|\| assumption.map().is_null()) continue;	42✔
77	symbolic::Expression ub, lb;	8✔
78	if (assumption.tight_upper_bound().is_null()) {	8✔
NEW 79	auto bounds = this->choose_bounds(parameters, assumption.upper_bounds());	×
80	if (bounds.empty()) {	×
81	ub = assumption.upper_bound();	×
82	} else {	×
83	ub = SymEngine::min(std::vector<symbolic::Expression>(bounds.begin(), bounds.end()));	×
84	}
85	} else {	×
86	ub = assumption.tight_upper_bound();	8✔
87	}
88	if (assumption.tight_lower_bound().is_null()) {	8✔
NEW 89	auto bounds = this->choose_bounds(parameters, assumption.lower_bounds());	×
90	if (bounds.empty()) {	×
91	lb = assumption.lower_bound();	×
92	} else {	×
93	lb = SymEngine::max(std::vector<symbolic::Expression>(bounds.begin(), bounds.end()));	×
94	}
95	} else {	×
96	lb = assumption.tight_lower_bound();	8✔
97	}
98	result = symbolic::subs(result, sym, symbolic::div(symbolic::sub(ub, lb), symbolic::integer(2)));	8✔
99	this->precise_ = false;	8✔
100	}	48✔
101	return result;	122✔
102	}	122✔
103
104	symbolic::SymbolSet FlopAnalysis::
105	get_scope_parameters(const structured_control_flow::ControlFlowNode& scope, AnalysisManager& analysis_manager) {	59✔
106	auto& users_analysis = analysis_manager.get<Users>();	59✔
107	analysis::UsersView users_view(users_analysis, scope);	59✔
108
109	std::unordered_set<std::string> all_uses, illegal_uses;	59✔
110	for (auto* user : users_view.uses()) {	567✔
111	Use not_allowed;
112	switch (this->sdfg_.type(user->container()).type_id()) {	508✔
113	case types::TypeID::Scalar:
114	not_allowed = Use::WRITE;	432✔
115	break;	432✔
116	case types::TypeID::Pointer:
117	case types::TypeID::Array:
118	not_allowed = Use::MOVE;	76✔
119	break;	76✔
120	default:
NEW 121	continue;	×
122	}
123	all_uses.insert(user->container());	508✔
124	if (user->use() == not_allowed) {	508✔
125	illegal_uses.insert(user->container());	129✔
126	}	129✔
127	}
128
129	symbolic::SymbolSet parameters;	59✔
130	for (auto& container : all_uses) {	361✔
131	if (!illegal_uses.contains(container)) {	302✔
132	parameters.insert(symbolic::symbol(container));	207✔
133	}	207✔
134	}
135
136	return parameters;	59✔
137	}	59✔
138
139	symbolic::Expression FlopAnalysis::visit(structured_control_flow::ControlFlowNode& node, AnalysisManager& analysis_manager) {	49✔
140	if (auto sequence = dynamic_cast<structured_control_flow::Sequence*>(&node)) {	49✔
141	return this->visit_sequence(*sequence, analysis_manager);	×
142	} else if (auto block = dynamic_cast<structured_control_flow::Block*>(&node)) {	49✔
143	return this->visit_block(*block, analysis_manager);	33✔
144	} else if (auto structured_loop = dynamic_cast<structured_control_flow::StructuredLoop*>(&node)) {	16✔
145	return this->visit_structured_loop(*structured_loop, analysis_manager);	13✔
146	} else if (auto if_else = dynamic_cast<structured_control_flow::IfElse*>(&node)) {	3✔
147	return this->visit_if_else(*if_else, analysis_manager);	1✔
148	} else if (auto while_loop = dynamic_cast<structured_control_flow::While*>(&node)) {	2✔
149	return this->visit_while(*while_loop, analysis_manager);	1✔
150	} else if (dynamic_cast<structured_control_flow::Return*>(&node) \|\|	1✔
151	dynamic_cast<structured_control_flow::Break*>(&node) \|\|	1✔
NEW 152	dynamic_cast<structured_control_flow::Continue*>(&node)) {	×
153	this->flops_[&node] = symbolic::zero();	1✔
154	return symbolic::zero();	1✔
155	} else {
NEW 156	this->flops_[&node] = SymEngine::null;	×
UNCOV 157	this->precise_ = false;	×
NEW 158	return SymEngine::null;	×
159	}
160	}	49✔
161
162	symbolic::Expression FlopAnalysis::
163	visit_sequence(structured_control_flow::Sequence& sequence, AnalysisManager& analysis_manager) {	39✔
164	symbolic::Expression result = symbolic::zero();	39✔
165	bool is_null = false;	39✔
166
167	for (size_t i = 0; i < sequence.size(); i++) {	88✔
168	symbolic::Expression child = this->visit(sequence.at(i).first, analysis_manager);	49✔
169	if (child.is_null()) {	49✔
170	is_null = true;	1✔
171	}	1✔
172	if (!is_null) {	49✔
173	result = symbolic::add(result, child);	48✔
174	}	48✔
175	}	49✔
176
177	if (is_null) {	39✔
178	this->flops_[&sequence] = SymEngine::null;	1✔
179	this->precise_ = false;	1✔
180	return SymEngine::null;	1✔
181	}
182	this->flops_[&sequence] = result;	38✔
183	return result;	38✔
184	}	39✔
185
186	symbolic::Expression FlopAnalysis::visit_block(structured_control_flow::Block& block, AnalysisManager& analysis_manager) {	33✔
187	auto& dfg = block.dataflow();	33✔
188
189	symbolic::Expression tasklets_result = symbolic::zero();	33✔
190	for (auto tasklet : dfg.tasklets()) {	68✔
191	if (tasklet->code() == data_flow::TaskletCode::fp_fma) {	35✔
192	tasklets_result = symbolic::add(tasklets_result, symbolic::integer(2));	10✔
193	} else if (data_flow::is_floating_point(tasklet->code())) {	35✔
194	tasklets_result = symbolic::add(tasklets_result, symbolic::one());	14✔
195	}	14✔
196	}
197
198	symbolic::Expression libnodes_result = symbolic::zero();	33✔
199	for (auto libnode : dfg.library_nodes()) {	34✔
200	symbolic::Expression tmp = libnode->flop();	1✔
201	if (tmp.is_null()) {	1✔
202	this->precise_ = false;	×
203	return SymEngine::null;	×
204	}
205	libnodes_result = symbolic::add(libnodes_result, tmp);	1✔
206	}	1✔
207
208	// Determine scope parameters
209	symbolic::SymbolSet parameters = this->get_scope_parameters(block, analysis_manager);	33✔
210
211	// Filter the loop index variables in libnodes_result, and replace them by (upper_bound - lower_bound) / 2
212	auto& assumptions_analysis = analysis_manager.get<AssumptionsAnalysis>();	33✔
213	auto block_assumptions = assumptions_analysis.get(block);	33✔
214	libnodes_result = this->replace_loop_indices(parameters, libnodes_result, block_assumptions);	33✔
215
216	symbolic::Expression result = symbolic::add(tasklets_result, libnodes_result);	33✔
217	this->flops_[&block] = result;	33✔
218	return result;	33✔
219	}	33✔
220
221	symbolic::Expression FlopAnalysis::
222	visit_structured_loop(structured_control_flow::StructuredLoop& loop, AnalysisManager& analysis_manager) {	13✔
223	auto& scope_analysis = analysis_manager.get<ScopeAnalysis>();	13✔
224	structured_control_flow::ControlFlowNode* parent = scope_analysis.parent_scope(&loop);	13✔
225	if (!parent) {	13✔
NEW 226	throw InvalidSDFGException("FlopAnalysis: Could not find parent scope of structured loop");	×
227	}
228	this->flops_[&loop] = this->visit_structured_loop_with_scope(loop, analysis_manager, loop);	13✔
229	return this->visit_structured_loop_with_scope(loop, analysis_manager, *parent);	13✔
NEW 230	}	×
231
232	symbolic::Expression FlopAnalysis::visit_structured_loop_with_scope(	26✔
233	structured_control_flow::StructuredLoop& loop,
234	AnalysisManager& analysis_manager,
235	structured_control_flow::ControlFlowNode& scope
236	) {
237	symbolic::Expression child = this->visit_sequence(loop.root(), analysis_manager);	26✔
238	if (child.is_null()) {	26✔
239	this->precise_ = false;	×
240	return SymEngine::null;	×
241	}
242
243	// Determine scope parameters
244	symbolic::SymbolSet parameters = this->get_scope_parameters(scope, analysis_manager);	26✔
245
246	// Require existance of assumptions for the loop indvar
247	auto indvar = loop.indvar();	26✔
248	auto& assumptions_analysis = analysis_manager.get<AssumptionsAnalysis>();	26✔
249	auto loop_assumptions = assumptions_analysis.get(loop.root());	26✔
250	if (!loop_assumptions.contains(indvar)) {	26✔
251	this->precise_ = false;	×
252	return SymEngine::null;	×
253	}
254	bool done;
255
256	// Determine initial value of loop
257	symbolic::Expression init = SymEngine::null;	26✔
258	done = false;	26✔
259	if (!loop_assumptions[indvar].tight_lower_bound().is_null()) {	26✔
260	init = this->replace_loop_indices(parameters, loop_assumptions[indvar].tight_lower_bound(), loop_assumptions);	26✔
261	done = this->is_parameter_expression(parameters, init);	26✔
262	}	26✔
263	if (!done && !symbolic::eq(loop_assumptions[indvar].lower_bound(), SymEngine::NegInf)) {	26✔
264	auto bounds = this->choose_bounds(parameters, loop_assumptions[indvar].lower_bounds());	6✔
265	if (!bounds.empty()) {	6✔
266	init = this->replace_loop_indices(	2✔
267	parameters,
268	SymEngine::max(std::vector<symbolic::Expression>(bounds.begin(), bounds.end())),	2✔
269	loop_assumptions
270	);
271	this->precise_ = false;	2✔
272	done = this->is_parameter_expression(parameters, init);	2✔
273	}	2✔
274	}	6✔
275	if (!done) {	26✔
276	init = this->replace_loop_indices(parameters, loop.init(), loop_assumptions);	4✔
277	this->precise_ = false;	4✔
278	}	4✔
279	if (init.is_null()) {	26✔
280	this->precise_ = false;	×
281	return SymEngine::null;	×
282	}
283
284	// Determine bound of loop
285	symbolic::Expression bound;	26✔
286	done = false;	26✔
287	if (!loop_assumptions[indvar].tight_upper_bound().is_null()) {	26✔
288	bound = this->replace_loop_indices(parameters, loop_assumptions[indvar].tight_upper_bound(), loop_assumptions);	22✔
289	done = this->is_parameter_expression(parameters, bound);	22✔
290	}	22✔
291	if (!done && !symbolic::eq(loop_assumptions[indvar].upper_bound(), SymEngine::Inf)) {	26✔
292	auto bounds = this->choose_bounds(parameters, loop_assumptions[indvar].upper_bounds());	5✔
293	if (!bounds.empty()) {	5✔
294	bound = this->replace_loop_indices(	5✔
295	parameters,
296	SymEngine::min(std::vector<symbolic::Expression>(bounds.begin(), bounds.end())),	5✔
297	loop_assumptions
298	);
299	this->precise_ = false;	5✔
300	done = this->is_parameter_expression(parameters, bound);	5✔
301	}	5✔
302	}	5✔
303	if (!done) {	26✔
304	auto canonical_bound = LoopAnalysis::canonical_bound(&loop, assumptions_analysis);	4✔
305	if (!canonical_bound.is_null()) {	4✔
306	bound =	4✔
307	this->replace_loop_indices(parameters, symbolic::sub(canonical_bound, symbolic::one()), loop_assumptions);	4✔
308	this->precise_ = false;	4✔
309	}	4✔
310	}	4✔
311	if (bound.is_null()) {	26✔
312	this->precise_ = false;	×
313	return SymEngine::null;	×
314	}
315
316	// Determine stride of loop
317	symbolic::SymbolVec symbols = {indvar};	26✔
318	auto update_polynomial = symbolic::polynomial(loop.update(), symbols);	26✔
319	if (update_polynomial.is_null()) {	26✔
320	this->precise_ = false;	×
321	return SymEngine::null;	×
322	}
323	auto update_coeffs = symbolic::affine_coefficients(update_polynomial, symbols);	26✔
324
325	// For now, only allow polynomial of the form: 1 * indvar + n
326	assert(update_coeffs.contains(indvar) && symbolic::eq(update_coeffs[indvar], symbolic::one()));	52✔
327	symbolic::Expression stride =
328	this->replace_loop_indices(parameters, update_coeffs[symbolic::symbol("__daisy_constant__")], loop_assumptions);	26✔
329
330	return symbolic::mul(symbolic::div(symbolic::add(symbolic::sub(bound, init), symbolic::one()), stride), child);	26✔
331	}	26✔
332
333	symbolic::Expression FlopAnalysis::
334	visit_if_else(structured_control_flow::IfElse& if_else, AnalysisManager& analysis_manager) {	1✔
335	if (if_else.size() == 0) {	1✔
NEW 336	this->flops_[&if_else] = symbolic::zero();	×
NEW 337	return symbolic::zero();	×
338	}
339
340	std::vector<symbolic::Expression> sub_flops;	1✔
341	bool is_null = false;	1✔
342
343	for (size_t i = 0; i < if_else.size(); i++) {	3✔
344	symbolic::Expression child = this->visit_sequence(if_else.at(i).first, analysis_manager);	2✔
345	if (child.is_null()) {	2✔
NEW 346	is_null = true;	×
NEW 347	}	×
348	if (!is_null) {	2✔
349	sub_flops.push_back(child);	2✔
350	}	2✔
351	}	2✔
352
353	this->precise_ = false;	1✔
354	if (is_null) {	1✔
NEW 355	this->flops_[&if_else] = SymEngine::null;	×
UNCOV 356	return SymEngine::null;	×
357	}
358	symbolic::Expression result = SymEngine::max(sub_flops);	1✔
359	this->flops_[&if_else] = result;	1✔
360	return result;	1✔
361	}	2✔
362
363	symbolic::Expression FlopAnalysis::visit_while(structured_control_flow::While& loop, AnalysisManager& analysis_manager) {	1✔
364	this->visit_sequence(loop.root(), analysis_manager);	1✔
365	this->flops_[&loop] = SymEngine::null;	1✔
366	this->precise_ = false;	1✔
367	// Return null because there is now good way to simply estimate the FLOPs of a while loop
368	return SymEngine::null;	1✔
369	}	×
370
371	void FlopAnalysis::run(AnalysisManager& analysis_manager) {	10✔
372	this->flops_.clear();	10✔
373	this->precise_ = true;	10✔
374
375	auto& assumptions_analysis = analysis_manager.get<AssumptionsAnalysis>();	10✔
376
377	this->visit_sequence(this->sdfg_.root(), analysis_manager);	10✔
378	}	10✔
379
380	FlopAnalysis::FlopAnalysis(StructuredSDFG& sdfg) : Analysis(sdfg) {}	10✔
381
382	bool FlopAnalysis::contains(const structured_control_flow::ControlFlowNode* node) {	47✔
383	return this->flops_.contains(node);	47✔
384	}
385
386	symbolic::Expression FlopAnalysis::get(const structured_control_flow::ControlFlowNode* node) {	47✔
387	return this->flops_[node];	47✔
388	}
389
390	std::unordered_map<const structured_control_flow::ControlFlowNode*, symbolic::Expression> FlopAnalysis::get() {	×
391	return this->flops_;	×
392	}
393
394	bool FlopAnalysis::precise() { return this->precise_; }	10✔
395
396	} // namespace analysis
397	} // namespace sdfg

daisytuner / sdfglib / 18776259427

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