24047998797

Committed 06 Apr 2026 07:46PM UTC coverage: 64.771% (-0.2%) from 64.968%

Build # 24047998797

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #649 from daisytuner/remove-polly

removes polly scheduler

Coverage Stats

28641 of 44219 relevant lines covered (64.77%)

625.62 hits per line

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

78.5

/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/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"
#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 = 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()) {
        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;
    }

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

daisytuner / docc / 24047998797

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