22994637400

Committed 12 Mar 2026 09:13AM UTC coverage: 63.488% (-1.1%) from 64.629%

Build # 22994637400

Build Type

Pull #570

github

Committed by

web-flow

Commit Message

Merge 4acc9e80f into 607827514

Pull Request Pull Request #570: Added ET target tests to github CI

Coverage Stats

24709 of 38919 relevant lines covered (63.49%)

369.41 hits per line

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

79.29

/sdfg/src/analysis/loop_analysis.cpp

#include "sdfg/analysis/loop_analysis.h"
#include <unordered_set>
#include <vector>

#include "sdfg/analysis/assumptions_analysis.h"
#include "sdfg/structured_control_flow/map.h"
#include "sdfg/structured_control_flow/structured_loop.h"
#include "sdfg/structured_control_flow/while.h"
#include "sdfg/symbolic/conjunctive_normal_form.h"
#include "sdfg/symbolic/series.h"

namespace sdfg {
namespace analysis {

LoopAnalysis::LoopAnalysis(StructuredSDFG& sdfg) : Analysis(sdfg), loops_(), loop_tree_(DFSLoopComparator(&loops_)) {}

void LoopAnalysis::
    run(structured_control_flow::ControlFlowNode& scope, structured_control_flow::ControlFlowNode* parent_loop) {
    std::list<structured_control_flow::ControlFlowNode*> queue = {&scope};
    while (!queue.empty()) {
        auto current = queue.front();
        queue.pop_front();

        // Loop detected
        if (auto while_stmt = dynamic_cast<structured_control_flow::While*>(current)) {
            this->loops_.push_back(while_stmt);
            this->loop_tree_[while_stmt] = parent_loop;
        } else if (auto loop_stmt = dynamic_cast<structured_control_flow::StructuredLoop*>(current)) {
            this->loops_.push_back(loop_stmt);
            this->loop_tree_[loop_stmt] = parent_loop;
        }

        if (dynamic_cast<structured_control_flow::Block*>(current)) {
            continue;
        } else if (auto sequence_stmt = dynamic_cast<structured_control_flow::Sequence*>(current)) {
            for (size_t i = 0; i < sequence_stmt->size(); i++) {
                queue.push_back(&sequence_stmt->at(i).first);
            }
        } else if (auto if_else_stmt = dynamic_cast<structured_control_flow::IfElse*>(current)) {
            for (size_t i = 0; i < if_else_stmt->size(); i++) {
                queue.push_back(&if_else_stmt->at(i).first);
            }
        } else if (auto while_stmt = dynamic_cast<structured_control_flow::While*>(current)) {
            this->run(while_stmt->root(), while_stmt);
        } else if (auto for_stmt = dynamic_cast<structured_control_flow::StructuredLoop*>(current)) {
            this->run(for_stmt->root(), for_stmt);
        } else if (dynamic_cast<structured_control_flow::Break*>(current)) {
            continue;
        } else if (dynamic_cast<structured_control_flow::Continue*>(current)) {
            continue;
        } else if (dynamic_cast<structured_control_flow::Return*>(current)) {
            continue;
        } else {
            throw std::runtime_error("Unsupported control flow node type");
        }
    }
}

void LoopAnalysis::compute_loop_infos(structured_control_flow::ControlFlowNode* loop) {
    structured_control_flow::Sequence* root = nullptr;
    if (auto while_stmt = dynamic_cast<structured_control_flow::While*>(loop)) {
        root = &while_stmt->root();
    } else if (auto loop_stmt = dynamic_cast<structured_control_flow::StructuredLoop*>(loop)) {
        root = &loop_stmt->root();
    } else {
        throw std::runtime_error("Node is not a loop");
    }

    LoopInfo init_info;
    init_info.element_id = loop->element_id();
    init_info.loopnest_index = -1;
    init_info.is_perfectly_nested = true;
    init_info.is_perfectly_parallel = true;
    init_info.is_elementwise = (dynamic_cast<structured_control_flow::Map*>(loop) != nullptr);
    init_info.has_side_effects = false;
    init_info.max_depth = 1;
    init_info.num_loops = 1;
    if (dynamic_cast<structured_control_flow::Map*>(loop)) {
        init_info.num_maps = 1;
        init_info.num_fors = 0;
        init_info.num_whiles = 0;
    } else if (dynamic_cast<structured_control_flow::StructuredLoop*>(loop)) {
        init_info.num_maps = 0;
        init_info.num_fors = 1;
        init_info.num_whiles = 0;
    } else if (dynamic_cast<structured_control_flow::While*>(loop)) {
        init_info.num_maps = 0;
        init_info.num_fors = 0;
        init_info.num_whiles = 1;
    }
    this->loop_infos_[loop] = init_info;

    // Recursion
    LoopInfo& info = this->loop_infos_[loop];
    std::list<structured_control_flow::ControlFlowNode*> queue = {root};
    while (!queue.empty()) {
        auto current = queue.front();
        queue.pop_front();

        if (auto block = dynamic_cast<structured_control_flow::Block*>(current)) {
            for (auto& node : block->dataflow().nodes()) {
                if (auto library_node = dynamic_cast<data_flow::LibraryNode*>(&node)) {
                    if (library_node->side_effect()) {
                        info.has_side_effects = true;
                        break;
                    }
                }
            }
        } else if (auto seq = dynamic_cast<structured_control_flow::Sequence*>(current)) {
            for (size_t i = 0; i < seq->size(); i++) {
                auto& child = seq->at(i).first;
                queue.push_back(&child);
            }
        } else if (auto ifelse = dynamic_cast<structured_control_flow::IfElse*>(current)) {
            for (size_t i = 0; i < ifelse->size(); i++) {
                auto& branch = ifelse->at(i).first;
                queue.push_back(&branch);
            }
        } else if (auto loop_stmt = dynamic_cast<structured_control_flow::StructuredLoop*>(current)) {
            this->compute_loop_infos(loop_stmt);

            auto& sub_info = this->loop_infos_[loop_stmt];
            info.num_loops += sub_info.num_loops;
            info.num_maps += sub_info.num_maps;
            info.num_fors += sub_info.num_fors;
            info.num_whiles += sub_info.num_whiles;
            info.max_depth = std::max(info.max_depth, 1 + sub_info.max_depth);

            info.has_side_effects = info.has_side_effects || sub_info.has_side_effects;
            info.is_elementwise = info.is_elementwise && sub_info.is_elementwise;
            info.is_perfectly_nested = info.is_perfectly_nested && sub_info.is_perfectly_nested;
            info.is_perfectly_parallel = info.is_perfectly_parallel && sub_info.is_perfectly_parallel;
        } else if (auto while_stmt = dynamic_cast<structured_control_flow::While*>(current)) {
            this->compute_loop_infos(while_stmt);

            auto& sub_info = this->loop_infos_[while_stmt];
            info.num_loops += sub_info.num_loops;
            info.num_maps += sub_info.num_maps;
            info.num_fors += sub_info.num_fors;
            info.num_whiles += sub_info.num_whiles;
            info.max_depth = std::max(info.max_depth, 1 + sub_info.max_depth);

            info.has_side_effects = info.has_side_effects || sub_info.has_side_effects;
            info.is_elementwise = info.is_elementwise && sub_info.is_elementwise;
            info.is_perfectly_nested = info.is_perfectly_nested && sub_info.is_perfectly_nested;
            info.is_perfectly_parallel = info.is_perfectly_parallel && sub_info.is_perfectly_parallel;
        } else if (dynamic_cast<structured_control_flow::Break*>(current)) {
            continue;
        } else if (dynamic_cast<structured_control_flow::Continue*>(current)) {
            continue;
        } else if (dynamic_cast<structured_control_flow::Return*>(current)) {
            info.has_side_effects = false;
            continue;
        } else {
            throw std::runtime_error("Unsupported control flow node type");
        }
    }

    // Perfectly nested
    if (info.is_perfectly_nested) {
        if (info.num_loops != info.max_depth) {
            info.is_perfectly_nested = false;
        } else {
            if (info.num_loops == 1) {
                // Leaf-nodes are by definition perfectly nested
                info.is_perfectly_nested = true;
            } else {
                // Non-leaf loop: body contains next loop
                info.is_perfectly_nested = (root->size() == 1 && root->at(0).second.empty());
            }
        }
    }

    // Perfectly parallel if all loops are maps
    if (info.is_perfectly_parallel) {
        info.is_perfectly_parallel = (info.num_maps == info.num_loops);
    }

    // Elementwise: perfectly nested, perfectly parallel, one increment
    if (info.is_elementwise) {
        if (info.is_perfectly_nested && info.is_perfectly_parallel) {
            auto loop_stmt = dynamic_cast<structured_control_flow::Map*>(loop);
            bool is_contiguous =
                symbolic::series::is_contiguous(loop_stmt->update(), loop_stmt->indvar(), symbolic::Assumptions());
            info.is_elementwise = is_contiguous;
        } else {
            info.is_elementwise = false;
        }
    }
}

void LoopAnalysis::run(AnalysisManager& analysis_manager) {
    this->loops_.clear();
    this->loop_tree_.clear();
    this->loop_infos_.clear();
    this->run(this->sdfg_.root(), nullptr);

    // Set loopnest indices for outermost loops
    int loopnest_index = 0;
    for (const auto& [loop, parent] : this->loop_tree_) {
        if (parent != nullptr) {
            continue;
        }
        this->compute_loop_infos(loop);
        this->loop_infos_[loop].loopnest_index = loopnest_index++;
    }
}

const std::vector<structured_control_flow::ControlFlowNode*> LoopAnalysis::loops() const { return this->loops_; }

LoopInfo LoopAnalysis::loop_info(structured_control_flow::ControlFlowNode* loop) const {
    return this->loop_infos_.at(loop);
}

structured_control_flow::ControlFlowNode* LoopAnalysis::find_loop_by_indvar(const std::string& indvar) {
    for (auto& loop : this->loops_) {
        if (auto loop_stmt = dynamic_cast<structured_control_flow::StructuredLoop*>(loop)) {
            if (loop_stmt->indvar()->get_name() == indvar) {
                return loop;
            }
        }
    }
    return nullptr;
}

bool LoopAnalysis::is_monotonic(structured_control_flow::StructuredLoop* loop, AssumptionsAnalysis& assumptions_analysis) {
    auto assums = assumptions_analysis.get(*loop, true);

    return symbolic::series::is_monotonic(loop->update(), loop->indvar(), assums);
}

bool LoopAnalysis::is_monotonic(structured_control_flow::StructuredLoop* loop, const symbolic::Assumptions& assumptions) {
    return symbolic::series::is_monotonic(loop->update(), loop->indvar(), assumptions);
}

bool LoopAnalysis::is_contiguous(structured_control_flow::StructuredLoop* loop, AssumptionsAnalysis& assumptions_analysis) {
    auto assums = assumptions_analysis.get(*loop, true);

    return symbolic::series::is_contiguous(loop->update(), loop->indvar(), assums);
}

bool LoopAnalysis::is_contiguous(structured_control_flow::StructuredLoop* loop, const symbolic::Assumptions& assumptions) {
    return symbolic::series::is_contiguous(loop->update(), loop->indvar(), assumptions);
}

symbolic::Expression LoopAnalysis::
    canonical_bound(structured_control_flow::StructuredLoop* loop, AssumptionsAnalysis& assumptions_analysis) {
    auto assums = assumptions_analysis.get(*loop, true);
    return LoopAnalysis::canonical_bound(loop, assums);
}

symbolic::Expression LoopAnalysis::
    canonical_bound(structured_control_flow::StructuredLoop* loop, const symbolic::Assumptions& assumptions) {
    if (!LoopAnalysis::is_monotonic(loop, assumptions)) {
        return SymEngine::null;
    }

    symbolic::CNF cnf;
    try {
        cnf = symbolic::conjunctive_normal_form(loop->condition());
    } catch (const std::runtime_error& e) {
        return SymEngine::null;
    }

    bool has_complex_clauses = false;
    for (auto& clause : cnf) {
        if (clause.size() > 1) {
            has_complex_clauses = true;
            break;
        }
    }
    if (has_complex_clauses) {
        return SymEngine::null;
    }

    auto indvar = loop->indvar();
    symbolic::Expression bound = SymEngine::null;
    for (auto& clause : cnf) {
        for (auto& literal : clause) {
            if (SymEngine::is_a<SymEngine::StrictLessThan>(*literal)) {
                auto lt = SymEngine::rcp_dynamic_cast<const SymEngine::StrictLessThan>(literal);
                auto lhs = lt->get_args()[0];
                auto rhs = lt->get_args()[1];
                if (SymEngine::eq(*lhs, *indvar)) {
                    if (bound == SymEngine::null) {
                        bound = rhs;
                    } else {
                        bound = symbolic::min(bound, rhs);
                    }
                } else {
                    return SymEngine::null;
                }
            } else if (SymEngine::is_a<SymEngine::LessThan>(*literal)) {
                auto le = SymEngine::rcp_dynamic_cast<const SymEngine::LessThan>(literal);
                auto lhs = le->get_args()[0];
                auto rhs = le->get_args()[1];
                if (SymEngine::eq(*lhs, *indvar)) {
                    if (bound == SymEngine::null) {
                        bound = symbolic::add(rhs, symbolic::one());
                    } else {
                        bound = symbolic::min(bound, symbolic::add(rhs, symbolic::one()));
                    }
                } else {
                    return SymEngine::null;
                }
            } else {
                return SymEngine::null;
            }
        }
    }

    return bound;
}

symbolic::Integer LoopAnalysis::stride(structured_control_flow::StructuredLoop* loop) {
    auto expr = loop->update();
    auto indvar = loop->indvar();

    if (SymEngine::is_a<SymEngine::Add>(*expr)) {
        auto add_expr = SymEngine::rcp_static_cast<const SymEngine::Add>(expr);
        if (add_expr->get_args().size() != 2) {
            return SymEngine::null;
        }
        auto arg1 = add_expr->get_args()[0];
        auto arg2 = add_expr->get_args()[1];
        if (symbolic::eq(arg1, indvar)) {
            if (SymEngine::is_a<SymEngine::Integer>(*arg2)) {
                return SymEngine::rcp_static_cast<const SymEngine::Integer>(arg2);
            }
        }
        if (symbolic::eq(arg2, indvar)) {
            if (SymEngine::is_a<SymEngine::Integer>(*arg1)) {
                return SymEngine::rcp_static_cast<const SymEngine::Integer>(arg1);
            }
        }
    }
    return SymEngine::null;
}

const std::map<structured_control_flow::ControlFlowNode*, structured_control_flow::ControlFlowNode*, DFSLoopComparator>&
LoopAnalysis::loop_tree() const {
    return this->loop_tree_;
}

structured_control_flow::ControlFlowNode* LoopAnalysis::parent_loop(structured_control_flow::ControlFlowNode* loop
) const {
    return this->loop_tree_.at(loop);
}

const std::vector<structured_control_flow::ControlFlowNode*> LoopAnalysis::outermost_loops() const {
    std::vector<structured_control_flow::ControlFlowNode*> outermost_loops_;
    for (const auto& [loop, parent] : this->loop_tree_) {
        if (parent == nullptr) {
            outermost_loops_.push_back(loop);
        }
    }
    return outermost_loops_;
}

bool LoopAnalysis::is_outermost_loop(structured_control_flow::ControlFlowNode* loop) const {
    if (this->loop_tree_.find(loop) == this->loop_tree_.end()) {
        return false;
    }
    return this->loop_tree_.at(loop) == nullptr;
}

const std::vector<structured_control_flow::ControlFlowNode*> LoopAnalysis::outermost_maps() const {
    std::vector<structured_control_flow::ControlFlowNode*> outermost_maps_;
    for (const auto& [loop, parent] : this->loop_tree_) {
        if (dynamic_cast<structured_control_flow::Map*>(loop)) {
            auto ancestor = parent;
            while (true) {
                if (ancestor == nullptr) {
                    outermost_maps_.push_back(loop);
                    break;
                }
                if (dynamic_cast<structured_control_flow::Map*>(ancestor)) {
                    break;
                }
                ancestor = this->loop_tree_.at(ancestor);
            }
        }
    }
    return outermost_maps_;
}

std::vector<sdfg::structured_control_flow::ControlFlowNode*> LoopAnalysis::
    children(sdfg::structured_control_flow::ControlFlowNode* node) const {
    // Find unique child
    return this->children(node, this->loop_tree_);
};

std::vector<sdfg::structured_control_flow::ControlFlowNode*> LoopAnalysis::children(
    sdfg::structured_control_flow::ControlFlowNode* node,
    const std::map<
        sdfg::structured_control_flow::ControlFlowNode*,
        sdfg::structured_control_flow::ControlFlowNode*,
        DFSLoopComparator>& tree
) const {
    // Find unique child
    std::vector<sdfg::structured_control_flow::ControlFlowNode*> c;
    for (auto& entry : tree) {
        if (entry.second == node) {
            c.push_back(entry.first);
        }
    }
    return c;
};

std::list<std::vector<sdfg::structured_control_flow::ControlFlowNode*>> LoopAnalysis::
    loop_tree_paths(sdfg::structured_control_flow::ControlFlowNode* loop) const {
    return this->loop_tree_paths(loop, this->loop_tree_);
};

std::list<std::vector<sdfg::structured_control_flow::ControlFlowNode*>> LoopAnalysis::loop_tree_paths(
    sdfg::structured_control_flow::ControlFlowNode* loop,
    const std::map<
        sdfg::structured_control_flow::ControlFlowNode*,
        sdfg::structured_control_flow::ControlFlowNode*,
        DFSLoopComparator>& tree
) const {
    // Collect all paths in tree starting from loop recursively (DFS)
    std::list<std::vector<sdfg::structured_control_flow::ControlFlowNode*>> paths;
    auto children = this->children(loop, tree);
    if (children.empty()) {
        paths.push_back({loop});
        return paths;
    }

    for (auto& child : children) {
        auto p = this->loop_tree_paths(child, tree);
        for (auto& path : p) {
            path.insert(path.begin(), loop);
            paths.push_back(path);
        }
    }

    return paths;
};

std::unordered_set<sdfg::structured_control_flow::ControlFlowNode*> LoopAnalysis::
    descendants(sdfg::structured_control_flow::ControlFlowNode* loop) const {
    std::unordered_set<sdfg::structured_control_flow::ControlFlowNode*> desc;
    std::list<sdfg::structured_control_flow::ControlFlowNode*> queue = {loop};
    while (!queue.empty()) {
        auto current = queue.front();
        queue.pop_front();
        auto children = this->children(current, this->loop_tree_);
        for (auto& child : children) {
            if (desc.find(child) == desc.end()) {
                desc.insert(child);
                queue.push_back(child);
            }
        }
    }
    return desc;
}

} // namespace analysis
} // namespace sdfg

1	#include "sdfg/analysis/loop_analysis.h"
2	#include <unordered_set>
3	#include <vector>
4
5	#include "sdfg/analysis/assumptions_analysis.h"
6	#include "sdfg/structured_control_flow/map.h"
7	#include "sdfg/structured_control_flow/structured_loop.h"
8	#include "sdfg/structured_control_flow/while.h"
9	#include "sdfg/symbolic/conjunctive_normal_form.h"
10	#include "sdfg/symbolic/series.h"
11
12	namespace sdfg {
13	namespace analysis {
14
15	LoopAnalysis::LoopAnalysis(StructuredSDFG& sdfg) : Analysis(sdfg), loops_(), loop_tree_(DFSLoopComparator(&loops_)) {}	231✔
16
17	void LoopAnalysis::
18	run(structured_control_flow::ControlFlowNode& scope, structured_control_flow::ControlFlowNode* parent_loop) {	933✔
19	std::list<structured_control_flow::ControlFlowNode*> queue = {&scope};	933✔
20	while (!queue.empty()) {	3,160✔
21	auto current = queue.front();	2,227✔
22	queue.pop_front();	2,227✔
23
24	// Loop detected
25	if (auto while_stmt = dynamic_cast<structured_control_flow::While*>(current)) {	2,227✔
26	this->loops_.push_back(while_stmt);	27✔
27	this->loop_tree_[while_stmt] = parent_loop;	27✔
28	} else if (auto loop_stmt = dynamic_cast<structured_control_flow::StructuredLoop*>(current)) {	2,200✔
29	this->loops_.push_back(loop_stmt);	675✔
30	this->loop_tree_[loop_stmt] = parent_loop;	675✔
31	}	675✔
32
33	if (dynamic_cast<structured_control_flow::Block*>(current)) {	2,227✔
34	continue;	579✔
35	} else if (auto sequence_stmt = dynamic_cast<structured_control_flow::Sequence*>(current)) {	1,648✔
36	for (size_t i = 0; i < sequence_stmt->size(); i++) {	2,229✔
37	queue.push_back(&sequence_stmt->at(i).first);	1,288✔
38	}	1,288✔
39	} else if (auto if_else_stmt = dynamic_cast<structured_control_flow::IfElse*>(current)) {	941✔
40	for (size_t i = 0; i < if_else_stmt->size(); i++) {	11✔
41	queue.push_back(&if_else_stmt->at(i).first);	6✔
42	}	6✔
43	} else if (auto while_stmt = dynamic_cast<structured_control_flow::While*>(current)) {	702✔
44	this->run(while_stmt->root(), while_stmt);	27✔
45	} else if (auto for_stmt = dynamic_cast<structured_control_flow::StructuredLoop*>(current)) {	675✔
46	this->run(for_stmt->root(), for_stmt);	675✔
47	} else if (dynamic_cast<structured_control_flow::Break*>(current)) {	675✔
48	continue;	×
49	} else if (dynamic_cast<structured_control_flow::Continue*>(current)) {	×
50	continue;	×
51	} else if (dynamic_cast<structured_control_flow::Return*>(current)) {	×
52	continue;	×
53	} else {	×
54	throw std::runtime_error("Unsupported control flow node type");	×
55	}	×
56	}	2,227✔
57	}	933✔
58
59	void LoopAnalysis::compute_loop_infos(structured_control_flow::ControlFlowNode* loop) {	702✔
60	structured_control_flow::Sequence* root = nullptr;	702✔
61	if (auto while_stmt = dynamic_cast<structured_control_flow::While*>(loop)) {	702✔
62	root = &while_stmt->root();	27✔
63	} else if (auto loop_stmt = dynamic_cast<structured_control_flow::StructuredLoop*>(loop)) {	675✔
64	root = &loop_stmt->root();	675✔
65	} else {	675✔
66	throw std::runtime_error("Node is not a loop");	×
67	}	×
68
69	LoopInfo init_info;	702✔
70	init_info.element_id = loop->element_id();	702✔
71	init_info.loopnest_index = -1;	702✔
72	init_info.is_perfectly_nested = true;	702✔
73	init_info.is_perfectly_parallel = true;	702✔
74	init_info.is_elementwise = (dynamic_cast<structured_control_flow::Map*>(loop) != nullptr);	702✔
75	init_info.has_side_effects = false;	702✔
76	init_info.max_depth = 1;	702✔
77	init_info.num_loops = 1;	702✔
78	if (dynamic_cast<structured_control_flow::Map*>(loop)) {	702✔
79	init_info.num_maps = 1;	362✔
80	init_info.num_fors = 0;	362✔
81	init_info.num_whiles = 0;	362✔
82	} else if (dynamic_cast<structured_control_flow::StructuredLoop*>(loop)) {	362✔
83	init_info.num_maps = 0;	313✔
84	init_info.num_fors = 1;	313✔
85	init_info.num_whiles = 0;	313✔
86	} else if (dynamic_cast<structured_control_flow::While*>(loop)) {	313✔
87	init_info.num_maps = 0;	27✔
88	init_info.num_fors = 0;	27✔
89	init_info.num_whiles = 1;	27✔
90	}	27✔
91	this->loop_infos_[loop] = init_info;	702✔
92
93	// Recursion
94	LoopInfo& info = this->loop_infos_[loop];	702✔
95	std::list<structured_control_flow::ControlFlowNode*> queue = {root};	702✔
96	while (!queue.empty()) {	2,346✔
97	auto current = queue.front();	1,644✔
98	queue.pop_front();	1,644✔
99
100	if (auto block = dynamic_cast<structured_control_flow::Block*>(current)) {	1,644✔
101	for (auto& node : block->dataflow().nodes()) {	2,057✔
102	if (auto library_node = dynamic_cast<data_flow::LibraryNode*>(&node)) {	2,057✔
103	if (library_node->side_effect()) {	24✔
104	info.has_side_effects = true;	22✔
105	break;	22✔
106	}	22✔
107	}	24✔
108	}	2,057✔
109	} else if (auto seq = dynamic_cast<structured_control_flow::Sequence*>(current)) {	1,090✔
110	for (size_t i = 0; i < seq->size(); i++) {	1,645✔
111	auto& child = seq->at(i).first;	936✔
112	queue.push_back(&child);	936✔
113	}	936✔
114	} else if (auto ifelse = dynamic_cast<structured_control_flow::IfElse*>(current)) {	709✔
115	for (size_t i = 0; i < ifelse->size(); i++) {	11✔
116	auto& branch = ifelse->at(i).first;	6✔
117	queue.push_back(&branch);	6✔
118	}	6✔
119	} else if (auto loop_stmt = dynamic_cast<structured_control_flow::StructuredLoop*>(current)) {	376✔
120	this->compute_loop_infos(loop_stmt);	375✔
121
122	auto& sub_info = this->loop_infos_[loop_stmt];	375✔
123	info.num_loops += sub_info.num_loops;	375✔
124	info.num_maps += sub_info.num_maps;	375✔
125	info.num_fors += sub_info.num_fors;	375✔
126	info.num_whiles += sub_info.num_whiles;	375✔
127	info.max_depth = std::max(info.max_depth, 1 + sub_info.max_depth);	375✔
128
129	info.has_side_effects = info.has_side_effects \|\| sub_info.has_side_effects;	375✔
130	info.is_elementwise = info.is_elementwise && sub_info.is_elementwise;	375✔
131	info.is_perfectly_nested = info.is_perfectly_nested && sub_info.is_perfectly_nested;	375✔
132	info.is_perfectly_parallel = info.is_perfectly_parallel && sub_info.is_perfectly_parallel;	375✔
133	} else if (auto while_stmt = dynamic_cast<structured_control_flow::While*>(current)) {	375✔
134	this->compute_loop_infos(while_stmt);	1✔
135
136	auto& sub_info = this->loop_infos_[while_stmt];	1✔
137	info.num_loops += sub_info.num_loops;	1✔
138	info.num_maps += sub_info.num_maps;	1✔
139	info.num_fors += sub_info.num_fors;	1✔
140	info.num_whiles += sub_info.num_whiles;	1✔
141	info.max_depth = std::max(info.max_depth, 1 + sub_info.max_depth);	1✔
142
143	info.has_side_effects = info.has_side_effects \|\| sub_info.has_side_effects;	1✔
144	info.is_elementwise = info.is_elementwise && sub_info.is_elementwise;	1✔
145	info.is_perfectly_nested = info.is_perfectly_nested && sub_info.is_perfectly_nested;	1✔
146	info.is_perfectly_parallel = info.is_perfectly_parallel && sub_info.is_perfectly_parallel;	1✔
147	} else if (dynamic_cast<structured_control_flow::Break*>(current)) {	1✔
148	continue;	×
149	} else if (dynamic_cast<structured_control_flow::Continue*>(current)) {	×
150	continue;	×
151	} else if (dynamic_cast<structured_control_flow::Return*>(current)) {	×
152	info.has_side_effects = false;	×
153	continue;	×
154	} else {	×
155	throw std::runtime_error("Unsupported control flow node type");	×
156	}	×
157	}	1,644✔
158
159	// Perfectly nested
160	if (info.is_perfectly_nested) {	702✔
161	if (info.num_loops != info.max_depth) {	679✔
162	info.is_perfectly_nested = false;	51✔
163	} else {	628✔
164	if (info.num_loops == 1) {	628✔
165	// Leaf-nodes are by definition perfectly nested
166	info.is_perfectly_nested = true;	394✔
167	} else {	394✔
168	// Non-leaf loop: body contains next loop
169	info.is_perfectly_nested = (root->size() == 1 && root->at(0).second.empty());	234✔
170	}	234✔
171	}	628✔
172	}	679✔
173
174	// Perfectly parallel if all loops are maps
175	if (info.is_perfectly_parallel) {	702✔
176	info.is_perfectly_parallel = (info.num_maps == info.num_loops);	529✔
177	}	529✔
178
179	// Elementwise: perfectly nested, perfectly parallel, one increment
180	if (info.is_elementwise) {	702✔
181	if (info.is_perfectly_nested && info.is_perfectly_parallel) {	304✔
182	auto loop_stmt = dynamic_cast<structured_control_flow::Map*>(loop);	303✔
183	bool is_contiguous =	303✔
184	symbolic::series::is_contiguous(loop_stmt->update(), loop_stmt->indvar(), symbolic::Assumptions());	303✔
185	info.is_elementwise = is_contiguous;	303✔
186	} else {	303✔
187	info.is_elementwise = false;	1✔
188	}	1✔
189	}	304✔
190	}	702✔
191
192	void LoopAnalysis::run(AnalysisManager& analysis_manager) {	231✔
193	this->loops_.clear();	231✔
194	this->loop_tree_.clear();	231✔
195	this->loop_infos_.clear();	231✔
196	this->run(this->sdfg_.root(), nullptr);	231✔
197
198	// Set loopnest indices for outermost loops
199	int loopnest_index = 0;	231✔
200	for (const auto& [loop, parent] : this->loop_tree_) {	702✔
201	if (parent != nullptr) {	702✔
202	continue;	376✔
203	}	376✔
204	this->compute_loop_infos(loop);	326✔
205	this->loop_infos_[loop].loopnest_index = loopnest_index++;	326✔
206	}	326✔
207	}	231✔
208
209	const std::vector<structured_control_flow::ControlFlowNode*> LoopAnalysis::loops() const { return this->loops_; }	5✔
210
211	LoopInfo LoopAnalysis::loop_info(structured_control_flow::ControlFlowNode* loop) const {	92✔
212	return this->loop_infos_.at(loop);	92✔
213	}	92✔
214
215	structured_control_flow::ControlFlowNode* LoopAnalysis::find_loop_by_indvar(const std::string& indvar) {	×
216	for (auto& loop : this->loops_) {	×
217	if (auto loop_stmt = dynamic_cast<structured_control_flow::StructuredLoop*>(loop)) {	×
218	if (loop_stmt->indvar()->get_name() == indvar) {	×
219	return loop;	×
220	}	×
221	}	×
222	}	×
223	return nullptr;	×
224	}	×
225
226	bool LoopAnalysis::is_monotonic(structured_control_flow::StructuredLoop* loop, AssumptionsAnalysis& assumptions_analysis) {	875✔
227	auto assums = assumptions_analysis.get(*loop, true);	875✔
228
229	return symbolic::series::is_monotonic(loop->update(), loop->indvar(), assums);	875✔
230	}	875✔
231
232	bool LoopAnalysis::is_monotonic(structured_control_flow::StructuredLoop* loop, const symbolic::Assumptions& assumptions) {	39✔
233	return symbolic::series::is_monotonic(loop->update(), loop->indvar(), assumptions);	39✔
234	}	39✔
235
236	bool LoopAnalysis::is_contiguous(structured_control_flow::StructuredLoop* loop, AssumptionsAnalysis& assumptions_analysis) {	28✔
237	auto assums = assumptions_analysis.get(*loop, true);	28✔
238
239	return symbolic::series::is_contiguous(loop->update(), loop->indvar(), assums);	28✔
240	}	28✔
241
242	bool LoopAnalysis::is_contiguous(structured_control_flow::StructuredLoop* loop, const symbolic::Assumptions& assumptions) {	23✔
243	return symbolic::series::is_contiguous(loop->update(), loop->indvar(), assumptions);	23✔
244	}	23✔
245
246	symbolic::Expression LoopAnalysis::
247	canonical_bound(structured_control_flow::StructuredLoop* loop, AssumptionsAnalysis& assumptions_analysis) {	16✔
248	auto assums = assumptions_analysis.get(*loop, true);	16✔
249	return LoopAnalysis::canonical_bound(loop, assums);	16✔
250	}	16✔
251
252	symbolic::Expression LoopAnalysis::
253	canonical_bound(structured_control_flow::StructuredLoop* loop, const symbolic::Assumptions& assumptions) {	39✔
254	if (!LoopAnalysis::is_monotonic(loop, assumptions)) {	39✔
255	return SymEngine::null;	×
256	}	×
257
258	symbolic::CNF cnf;	39✔
259	try {	39✔
260	cnf = symbolic::conjunctive_normal_form(loop->condition());	39✔
261	} catch (const std::runtime_error& e) {	39✔
262	return SymEngine::null;	×
263	}	×
264
265	bool has_complex_clauses = false;	39✔
266	for (auto& clause : cnf) {	41✔
267	if (clause.size() > 1) {	41✔
268	has_complex_clauses = true;	×
269	break;	×
270	}	×
271	}	41✔
272	if (has_complex_clauses) {	39✔
273	return SymEngine::null;	×
274	}	×
275
276	auto indvar = loop->indvar();	39✔
277	symbolic::Expression bound = SymEngine::null;	39✔
278	for (auto& clause : cnf) {	41✔
279	for (auto& literal : clause) {	41✔
280	if (SymEngine::is_a<SymEngine::StrictLessThan>(*literal)) {	41✔
281	auto lt = SymEngine::rcp_dynamic_cast<const SymEngine::StrictLessThan>(literal);	20✔
282	auto lhs = lt->get_args()[0];	20✔
283	auto rhs = lt->get_args()[1];	20✔
284	if (SymEngine::eq(lhs, indvar)) {	20✔
285	if (bound == SymEngine::null) {	20✔
286	bound = rhs;	19✔
287	} else {	19✔
288	bound = symbolic::min(bound, rhs);	1✔
289	}	1✔
290	} else {	20✔
291	return SymEngine::null;	×
292	}	×
293	} else if (SymEngine::is_a<SymEngine::LessThan>(*literal)) {	21✔
294	auto le = SymEngine::rcp_dynamic_cast<const SymEngine::LessThan>(literal);	21✔
295	auto lhs = le->get_args()[0];	21✔
296	auto rhs = le->get_args()[1];	21✔
297	if (SymEngine::eq(lhs, indvar)) {	21✔
298	if (bound == SymEngine::null) {	21✔
299	bound = symbolic::add(rhs, symbolic::one());	20✔
300	} else {	20✔
301	bound = symbolic::min(bound, symbolic::add(rhs, symbolic::one()));	1✔
302	}	1✔
303	} else {	21✔
304	return SymEngine::null;	×
305	}	×
306	} else {	21✔
307	return SymEngine::null;	×
308	}	×
309	}	41✔
310	}	41✔
311
312	return bound;	39✔
313	}	39✔
314
315	symbolic::Integer LoopAnalysis::stride(structured_control_flow::StructuredLoop* loop) {	82✔
316	auto expr = loop->update();	82✔
317	auto indvar = loop->indvar();	82✔
318
319	if (SymEngine::is_a<SymEngine::Add>(*expr)) {	82✔
320	auto add_expr = SymEngine::rcp_static_cast<const SymEngine::Add>(expr);	82✔
321	if (add_expr->get_args().size() != 2) {	82✔
322	return SymEngine::null;	×
323	}	×
324	auto arg1 = add_expr->get_args()[0];	82✔
325	auto arg2 = add_expr->get_args()[1];	82✔
326	if (symbolic::eq(arg1, indvar)) {	82✔
327	if (SymEngine::is_a<SymEngine::Integer>(*arg2)) {	×
328	return SymEngine::rcp_static_cast<const SymEngine::Integer>(arg2);	×
329	}	×
330	}	×
331	if (symbolic::eq(arg2, indvar)) {	82✔
332	if (SymEngine::is_a<SymEngine::Integer>(*arg1)) {	82✔
333	return SymEngine::rcp_static_cast<const SymEngine::Integer>(arg1);	82✔
334	}	82✔
335	}	82✔
336	}	82✔
337	return SymEngine::null;	×
338	}	82✔
339
340	const std::map<structured_control_flow::ControlFlowNode, structured_control_flow::ControlFlowNode, DFSLoopComparator>&
341	LoopAnalysis::loop_tree() const {	98✔
342	return this->loop_tree_;	98✔
343	}	98✔
344
345	structured_control_flow::ControlFlowNode* LoopAnalysis::parent_loop(structured_control_flow::ControlFlowNode* loop
346	) const {	19✔
347	return this->loop_tree_.at(loop);	19✔
348	}	19✔
349
350	const std::vector<structured_control_flow::ControlFlowNode*> LoopAnalysis::outermost_loops() const {	48✔
351	std::vector<structured_control_flow::ControlFlowNode*> outermost_loops_;	48✔
352	for (const auto& [loop, parent] : this->loop_tree_) {	207✔
353	if (parent == nullptr) {	207✔
354	outermost_loops_.push_back(loop);	91✔
355	}	91✔
356	}	207✔
357	return outermost_loops_;	48✔
358	}	48✔
359
360	bool LoopAnalysis::is_outermost_loop(structured_control_flow::ControlFlowNode* loop) const {	×
361	if (this->loop_tree_.find(loop) == this->loop_tree_.end()) {	×
362	return false;	×
363	}	×
364	return this->loop_tree_.at(loop) == nullptr;	×
365	}	×
366
367	const std::vector<structured_control_flow::ControlFlowNode*> LoopAnalysis::outermost_maps() const {	×
368	std::vector<structured_control_flow::ControlFlowNode*> outermost_maps_;	×
369	for (const auto& [loop, parent] : this->loop_tree_) {	×
370	if (dynamic_cast<structured_control_flow::Map*>(loop)) {	×
371	auto ancestor = parent;	×
372	while (true) {	×
373	if (ancestor == nullptr) {	×
374	outermost_maps_.push_back(loop);	×
375	break;	×
376	}	×
377	if (dynamic_cast<structured_control_flow::Map*>(ancestor)) {	×
378	break;	×
379	}	×
380	ancestor = this->loop_tree_.at(ancestor);	×
381	}	×
382	}	×
383	}	×
384	return outermost_maps_;	×
385	}	×
386
387	std::vector<sdfg::structured_control_flow::ControlFlowNode*> LoopAnalysis::
388	children(sdfg::structured_control_flow::ControlFlowNode* node) const {	19✔
389	// Find unique child
390	return this->children(node, this->loop_tree_);	19✔
391	};	19✔
392
393	std::vector<sdfg::structured_control_flow::ControlFlowNode*> LoopAnalysis::children(
394	sdfg::structured_control_flow::ControlFlowNode* node,
395	const std::map<
396	sdfg::structured_control_flow::ControlFlowNode*,
397	sdfg::structured_control_flow::ControlFlowNode*,
398	DFSLoopComparator>& tree
399	) const {	4,001✔
400	// Find unique child
401	std::vector<sdfg::structured_control_flow::ControlFlowNode*> c;	4,001✔
402	for (auto& entry : tree) {	19,423✔
403	if (entry.second == node) {	19,423✔
404	c.push_back(entry.first);	2,464✔
405	}	2,464✔
406	}	19,423✔
407	return c;	4,001✔
408	};	4,001✔
409
410	std::list<std::vector<sdfg::structured_control_flow::ControlFlowNode*>> LoopAnalysis::
411	loop_tree_paths(sdfg::structured_control_flow::ControlFlowNode* loop) const {	97✔
412	return this->loop_tree_paths(loop, this->loop_tree_);	97✔
413	};	97✔
414
415	std::list<std::vector<sdfg::structured_control_flow::ControlFlowNode*>> LoopAnalysis::loop_tree_paths(
416	sdfg::structured_control_flow::ControlFlowNode* loop,
417	const std::map<
418	sdfg::structured_control_flow::ControlFlowNode*,
419	sdfg::structured_control_flow::ControlFlowNode*,
420	DFSLoopComparator>& tree
421	) const {	203✔
422	// Collect all paths in tree starting from loop recursively (DFS)
423	std::list<std::vector<sdfg::structured_control_flow::ControlFlowNode*>> paths;	203✔
424	auto children = this->children(loop, tree);	203✔
425	if (children.empty()) {	203✔
426	paths.push_back({loop});	111✔
427	return paths;	111✔
428	}	111✔
429
430	for (auto& child : children) {	106✔
431	auto p = this->loop_tree_paths(child, tree);	106✔
432	for (auto& path : p) {	112✔
433	path.insert(path.begin(), loop);	112✔
434	paths.push_back(path);	112✔
435	}	112✔
436	}	106✔
437
438	return paths;	92✔
439	};	203✔
440
441	std::unordered_set<sdfg::structured_control_flow::ControlFlowNode*> LoopAnalysis::
442	descendants(sdfg::structured_control_flow::ControlFlowNode* loop) const {	1,442✔
443	std::unordered_set<sdfg::structured_control_flow::ControlFlowNode*> desc;	1,442✔
444	std::list<sdfg::structured_control_flow::ControlFlowNode*> queue = {loop};	1,442✔
445	while (!queue.empty()) {	5,221✔
446	auto current = queue.front();	3,779✔
447	queue.pop_front();	3,779✔
448	auto children = this->children(current, this->loop_tree_);	3,779✔
449	for (auto& child : children) {	3,779✔
450	if (desc.find(child) == desc.end()) {	2,337✔
451	desc.insert(child);	2,337✔
452	queue.push_back(child);	2,337✔
453	}	2,337✔
454	}	2,337✔
455	}	3,779✔
456	return desc;	1,442✔
457	}	1,442✔
458
459	} // namespace analysis
460	} // namespace sdfg

daisytuner / docc / 22994637400

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