19406662809

Committed 16 Nov 2025 01:54PM UTC coverage: 62.092% (-0.4%) from 62.447%

Build # 19406662809

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #347 from daisytuner/symbolic-range-analysis

extends symbol promotion with checks for effective range of scalars

Run Details

174 of 355 new or added lines in 10 files covered. (49.01%)

13 existing lines in 4 files now uncovered.

11048 of 17793 relevant lines covered (62.09%)

112.56 hits per line

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

80.46

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

daisytuner / sdfglib / 19406662809

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