28809522800

Committed 06 Jul 2026 05:12PM UTC coverage: 62.882% (-0.08%) from 62.96%

Build # 28809522800

Build Type

Pull #843

github

Committed by

web-flow

Commit Message

Merge beb5b23d7 into 95ea95f1f

Pull Request Pull Request #843: adds type_ids for Element classes and a human-readable element_type

Coverage Stats

413 of 587 new or added lines in 121 files covered. (70.36%)

74 existing lines in 6 files now uncovered.

40564 of 64508 relevant lines covered (62.88%)

961.48 hits per line

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

75.0

/sdfg/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/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"
#include "symengine/visitor.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::has_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 = SymEngine::Inf;
            } 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 = SymEngine::NegInf;
            } 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()) {
        if (!sdfg_.exists(user->container())) {
            continue;
        }

        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) {
    symbolic::Expression child = this->visit_sequence(loop.root(), analysis_manager);
    if (child.is_null()) {
        this->precise_ = false;
        return SymEngine::null;
    }

    structured_control_flow::ControlFlowNode* parent = loop.get_parent();
    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, child);
    return this->visit_structured_loop_with_scope(loop, analysis_manager, *parent, child);
}

symbolic::Expression FlopAnalysis::visit_structured_loop_with_scope(
    structured_control_flow::StructuredLoop& loop,
    AnalysisManager& analysis_manager,
    structured_control_flow::ControlFlowNode& scope,
    symbolic::Expression child_expr
) {
    // 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 && !loop_assumptions[indvar].lower_bounds().empty()) {
        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) {
        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 = loop.canonical_bound();
        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);

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

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 no 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) {
    auto it = this->flops_.find(node);
    if (it != this->flops_.end()) {
        return it->second;
    } else {
        return SymEngine::null;
    }
}

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

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

symbolic::Expression FlopAnalysis::get_if_valid_for_codegen(const symbolic::Expression flops) {
    if (!flops.is_null()) {
        for (auto& atom : SymEngine::atoms<SymEngine::Basic>(*flops)) { // TODO this excludes anything including
                                                                        // Infinity, as long as its not filtered out at
                                                                        // the beginning of flop analysis (untested,
                                                                        // whether parsing can handle incomplete traces
                                                                        // (we emit null, for such)
            if (SymEngine::is_a<SymEngine::Infty>(*atom)) {
                return SymEngine::null;
            }
        }
        if (!symbolic::has_dynamic_sizeof(flops)) {
            return flops;
        }
    }
    return SymEngine::null;
}

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

daisytuner / docc / 28809522800

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