27623444566

Committed 16 Jun 2026 02:06PM UTC coverage: 61.524% (-0.02%) from 61.54%

Build # 27623444566

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #767 from daisytuner/loop-analysis-stacks

Extending LoopAnalysis to provide data for partially perfect loop nests

Coverage Stats

333 of 398 new or added lines in 4 files covered. (83.67%)

9 existing lines in 2 files now uncovered.

36494 of 59317 relevant lines covered (61.52%)

1107.09 hits per line

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

75.43

/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"

namespace sdfg {
namespace analysis {

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

void LoopAnalysis::init_new_loop_info(
    std::pair<LocalLoopInfo, LoopInfo>& info,
    uint32_t loop_level,
    structured_control_flow::ControlFlowNode* loop,
    structured_control_flow::Map* map,
    structured_control_flow::ControlFlowNode* while_loop
) {
    auto is_elementwise = (map != nullptr && map->is_contiguous());

    info.first = {
        .loop_id = this->next_loop_id_++,
        .loop_level = loop_level,
        .is_map = map != nullptr,
        .is_elementwise = is_elementwise,
        .contains_non_perfectly_nested = false,
        .contains_side_effects = false
    };
    info.second.element_id = loop->element_id();
    info.second.is_elementwise = is_elementwise;
    info.second.has_side_effects = false;
    info.second.max_depth = 1;
    info.second.num_loops = 1;
    info.second.loop_level = loop_level;
    if (map != nullptr) {
        info.second.num_maps = 1;
        info.second.num_fors = 0;
        info.second.num_whiles = 0;
    } else if (while_loop != nullptr) {
        info.second.num_maps = 0;
        info.second.num_fors = 0;
        info.second.num_whiles = 1;
    } else {
        info.second.num_maps = 0;
        info.second.num_fors = 1;
        info.second.num_whiles = 0;
    }
}

void LoopAnalysis::
    run(structured_control_flow::ControlFlowNode& scope,
        structured_control_flow::ControlFlowNode* parent_loop,
        uint32_t loop_level) {
    std::list<structured_control_flow::ControlFlowNode*> queue = {&scope};
    bool non_perfectly_nested = false;
    bool side_effects = false;

    while (!queue.empty()) {
        auto current = queue.front();
        queue.pop_front();

        structured_control_flow::While* new_while = nullptr;
        structured_control_flow::Map* new_map = nullptr;
        structured_control_flow::For* new_for = nullptr;
        structured_control_flow::ControlFlowNode* new_loop = nullptr;
        // Loop detected
        if (auto while_stmt = dynamic_cast<structured_control_flow::While*>(current)) {
            new_loop = while_stmt;
            new_while = while_stmt;
        } else if (auto map_stmt = dynamic_cast<structured_control_flow::Map*>(current)) {
            new_map = map_stmt;
            new_loop = map_stmt;
        } else if (auto for_stmt = dynamic_cast<structured_control_flow::For*>(current)) {
            new_for = for_stmt;
            new_loop = for_stmt;
        }

        if (new_loop != nullptr) {
            this->loops_.push_back(new_loop);
            this->loop_tree_[new_loop] = parent_loop;
            this->loop_children_[parent_loop].push_back(new_loop);
            this->loop_children_[new_loop]; // ensure it gets created
            auto& loop_info = loop_infos_[new_loop];
            init_new_loop_info(loop_info, loop_level, new_loop, new_map, new_while);
        }

        if (auto block = dynamic_cast<structured_control_flow::Block*>(current)) {
            non_perfectly_nested = true;
            for (auto& node : block->dataflow().nodes()) {
                if (auto library_node = dynamic_cast<data_flow::LibraryNode*>(&node)) {
                    if (library_node->side_effect()) { // also look at pointer metadata (no capture to not infer
                                                       // side-effects)
                        side_effects = true;
                        break;
                    }
                }
            }
        } else if (auto sequence_stmt = dynamic_cast<structured_control_flow::Sequence*>(current)) {
            auto seq_entries = sequence_stmt->size();
            if (current != &scope) { // the body-root of each loop is expected to be a sequence
                non_perfectly_nested = true;
            }
            for (size_t i = 0; i < seq_entries; i++) {
                auto entry = sequence_stmt->at(i);
                if (i > 0 || !entry.second.empty()) {
                    non_perfectly_nested = true;
                }
                queue.push_back(&entry.first);
            }
        } else if (auto if_else_stmt = dynamic_cast<structured_control_flow::IfElse*>(current)) {
            non_perfectly_nested = true;
            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, loop_level + 1);
        } else if (auto for_stmt = dynamic_cast<structured_control_flow::StructuredLoop*>(current)) {
            this->run(for_stmt->root(), for_stmt, loop_level + 1);
        } else if (dynamic_cast<structured_control_flow::Break*>(current)) {
            non_perfectly_nested = true;
            continue;
        } else if (dynamic_cast<structured_control_flow::Continue*>(current)) {
            non_perfectly_nested = true;
            continue;
        } else if (dynamic_cast<structured_control_flow::Return*>(current)) {
            non_perfectly_nested = true;
            continue;
        } else {
            throw std::runtime_error("Unsupported control flow node type");
        }
    }

    if (parent_loop != nullptr) {
        auto child_count = loop_children_.at(parent_loop).size();
        auto& state = loop_infos_.at(parent_loop);
        state.first.last_child_id = this->next_loop_id_ - 1;
        state.first.contains_side_effects = side_effects;

        if (child_count > 1) {
            non_perfectly_nested = true;
        } else if (child_count < 1) {
            non_perfectly_nested = false;
        }
        if (non_perfectly_nested) {
            state.first.contains_non_perfectly_nested = non_perfectly_nested;
        }
    }
}

structured_control_flow::Sequence* LoopAnalysis::get_loop_content_root(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");
    }
    return root;
}

LoopState& LoopAnalysis::compute_loop_infos(structured_control_flow::ControlFlowNode* loop) {
    // Recursion
    auto& loop_state = this->loop_infos_.at(loop);
    LoopInfo& info = loop_state.second;
    auto& loop_children = this->loop_children_.at(loop);

    bool is_perfectly_nested = !loop_state.first.contains_non_perfectly_nested;
    bool is_perfectly_parallel = loop_state.first.is_map;
    bool is_elementwise = loop_state.first.is_elementwise;
    bool map_stack_member = loop_state.first.is_map;
    bool has_side_effects = loop_state.first.contains_side_effects;
    bool map_stack_children = map_stack_member && loop_children.size() <= 1;
    uint32_t map_stack_depth = 0;

    for (auto& child_loop : loop_children) {
        this->compute_loop_infos(child_loop);

        auto& sub_info = this->loop_infos_.at(child_loop).second;
        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);

        has_side_effects |= sub_info.has_side_effects;
        is_perfectly_nested &= sub_info.is_perfectly_nested;
        is_perfectly_parallel &= sub_info.is_perfectly_parallel;
        is_elementwise &= sub_info.is_elementwise;
        if (map_stack_children) {
            map_stack_depth = sub_info.map_stack_depth; // only allowed if there is just a single, direct child
        }
    }

    info.is_perfectly_parallel = is_perfectly_parallel;
    info.is_perfectly_nested = is_perfectly_nested;
    info.is_elementwise &= is_elementwise && is_perfectly_nested & is_perfectly_parallel;
    info.has_side_effects = has_side_effects;
    if (map_stack_member) {
        if (!is_perfectly_nested) { // needs to be perfectly nested to form a larger stack
            map_stack_depth = 0;
        }
        info.map_stack_depth = map_stack_depth + 1;
    }

    return loop_state;
}

void LoopAnalysis::run(AnalysisManager& analysis_manager) {
    this->loops_.clear();
    this->loop_tree_.clear();
    this->loop_infos_.clear();
    this->loop_children_.clear();
    this->loop_children_[nullptr]; // ensure it exists
    this->run(this->sdfg_.root(), nullptr, 0);

    // Set loopnest indices for outermost loops
    int loopnest_index = 0;
    auto root_it = this->loop_children_.find(nullptr);
    if (root_it != this->loop_children_.end()) {
        auto& root_loops = root_it->second;
        for (auto* root_loop : root_loops) {
            this->compute_loop_infos(root_loop);
            this->loop_infos_[root_loop].second.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).second;
}

const LocalLoopInfo& LoopAnalysis::loop_info_local(structured_control_flow::ControlFlowNode* loop) const {
    return this->loop_infos_.at(loop).first;
}

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

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 {
    return loop_children_.at(nullptr);
}

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

const std::vector<sdfg::structured_control_flow::ControlFlowNode*>& LoopAnalysis::
    children(sdfg::structured_control_flow::ControlFlowNode* node) const {
    // Find unique child
    return loop_children_.at(node);
}

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);
    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);
        for (auto& child : children) {
            if (desc.find(child) == desc.end()) {
                desc.insert(child);
                queue.push_back(child);
            }
        }
    }
    return desc;
}

void LoopAnalysis::dump_to_file(std::filesystem::path file) const {
    nlohmann::json arr;
    for (auto& loop : this->loops_) {
        auto& info = loop_infos_.at(loop);

        arr.push_back(loop_info_to_json(info.second));
    }


    std::filesystem::create_directories(file.parent_path());
    std::ofstream out(file, std::ofstream::out);
    if (!out.is_open()) {
        std::cerr << "Could not open file " << file << " for writing JSON output." << std::endl;
    }
    out << arr << std::endl;
    out.close();
}

} // 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
11	namespace sdfg {
12	namespace analysis {
13
14	LoopAnalysis::LoopAnalysis(StructuredSDFG& sdfg) : Analysis(sdfg), loops_(), loop_tree_(DFSLoopComparator(&loops_)) {}	331✔
15
16	void LoopAnalysis::init_new_loop_info(
17	std::pair<LocalLoopInfo, LoopInfo>& info,
18	uint32_t loop_level,
19	structured_control_flow::ControlFlowNode* loop,
20	structured_control_flow::Map* map,
21	structured_control_flow::ControlFlowNode* while_loop
22	) {	1,163✔
23	auto is_elementwise = (map != nullptr && map->is_contiguous());	1,163✔
24
25	info.first = {	1,163✔
26	.loop_id = this->next_loop_id_++,	1,163✔
27	.loop_level = loop_level,	1,163✔
28	.is_map = map != nullptr,	1,163✔
29	.is_elementwise = is_elementwise,	1,163✔
30	.contains_non_perfectly_nested = false,	1,163✔
31	.contains_side_effects = false	1,163✔
32	};	1,163✔
33	info.second.element_id = loop->element_id();	1,163✔
34	info.second.is_elementwise = is_elementwise;	1,163✔
35	info.second.has_side_effects = false;	1,163✔
36	info.second.max_depth = 1;	1,163✔
37	info.second.num_loops = 1;	1,163✔
38	info.second.loop_level = loop_level;	1,163✔
39	if (map != nullptr) {	1,163✔
40	info.second.num_maps = 1;	605✔
41	info.second.num_fors = 0;	605✔
42	info.second.num_whiles = 0;	605✔
43	} else if (while_loop != nullptr) {	605✔
44	info.second.num_maps = 0;	12✔
45	info.second.num_fors = 0;	12✔
46	info.second.num_whiles = 1;	12✔
47	} else {	546✔
48	info.second.num_maps = 0;	546✔
49	info.second.num_fors = 1;	546✔
50	info.second.num_whiles = 0;	546✔
51	}	546✔
52	}	1,163✔
53
54	void LoopAnalysis::
55	run(structured_control_flow::ControlFlowNode& scope,
56	structured_control_flow::ControlFlowNode* parent_loop,
57	uint32_t loop_level) {	1,494✔
58	std::list<structured_control_flow::ControlFlowNode*> queue = {&scope};	1,494✔
59	bool non_perfectly_nested = false;	1,494✔
60	bool side_effects = false;	1,494✔
61
62	while (!queue.empty()) {	5,062✔
63	auto current = queue.front();	3,568✔
64	queue.pop_front();	3,568✔
65
66	structured_control_flow::While* new_while = nullptr;	3,568✔
67	structured_control_flow::Map* new_map = nullptr;	3,568✔
68	structured_control_flow::For* new_for = nullptr;	3,568✔
69	structured_control_flow::ControlFlowNode* new_loop = nullptr;	3,568✔
70	// Loop detected
71	if (auto while_stmt = dynamic_cast<structured_control_flow::While*>(current)) {	3,568✔
72	new_loop = while_stmt;	12✔
73	new_while = while_stmt;	12✔
74	} else if (auto map_stmt = dynamic_cast<structured_control_flow::Map*>(current)) {	3,556✔
75	new_map = map_stmt;	605✔
76	new_loop = map_stmt;	605✔
77	} else if (auto for_stmt = dynamic_cast<structured_control_flow::For*>(current)) {	2,951✔
78	new_for = for_stmt;	546✔
79	new_loop = for_stmt;	546✔
80	}	546✔
81
82	if (new_loop != nullptr) {	3,568✔
83	this->loops_.push_back(new_loop);	1,163✔
84	this->loop_tree_[new_loop] = parent_loop;	1,163✔
85	this->loop_children_[parent_loop].push_back(new_loop);	1,163✔
86	this->loop_children_[new_loop]; // ensure it gets created	1,163✔
87	auto& loop_info = loop_infos_[new_loop];	1,163✔
88	init_new_loop_info(loop_info, loop_level, new_loop, new_map, new_while);	1,163✔
89	}	1,163✔
90
91	if (auto block = dynamic_cast<structured_control_flow::Block*>(current)) {	3,568✔
92	non_perfectly_nested = true;	894✔
93	for (auto& node : block->dataflow().nodes()) {	3,290✔
94	if (auto library_node = dynamic_cast<data_flow::LibraryNode*>(&node)) {	3,290✔
95	if (library_node->side_effect()) { // also look at pointer metadata (no capture to not infer	31✔
96	// side-effects)
97	side_effects = true;	29✔
98	break;	29✔
99	}	29✔
100	}	31✔
101	}	3,290✔
102	} else if (auto sequence_stmt = dynamic_cast<structured_control_flow::Sequence*>(current)) {	2,674✔
103	auto seq_entries = sequence_stmt->size();	1,504✔
104	if (current != &scope) { // the body-root of each loop is expected to be a sequence	1,504✔
105	non_perfectly_nested = true;	10✔
106	}	10✔
107	for (size_t i = 0; i < seq_entries; i++) {	3,568✔
108	auto entry = sequence_stmt->at(i);	2,064✔
109	if (i > 0 \|\| !entry.second.empty()) {	2,064✔
110	non_perfectly_nested = true;	589✔
111	}	589✔
112	queue.push_back(&entry.first);	2,064✔
113	}	2,064✔
114	} else if (auto if_else_stmt = dynamic_cast<structured_control_flow::IfElse*>(current)) {	1,504✔
115	non_perfectly_nested = true;	7✔
116	for (size_t i = 0; i < if_else_stmt->size(); i++) {	17✔
117	queue.push_back(&if_else_stmt->at(i).first);	10✔
118	}	10✔
119	} else if (auto while_stmt = dynamic_cast<structured_control_flow::While*>(current)) {	1,163✔
120	this->run(while_stmt->root(), while_stmt, loop_level + 1);	12✔
121	} else if (auto for_stmt = dynamic_cast<structured_control_flow::StructuredLoop*>(current)) {	1,151✔
122	this->run(for_stmt->root(), for_stmt, loop_level + 1);	1,151✔
123	} else if (dynamic_cast<structured_control_flow::Break*>(current)) {	1,151✔
NEW 124	non_perfectly_nested = true;	×
125	continue;	×
126	} else if (dynamic_cast<structured_control_flow::Continue*>(current)) {	×
NEW 127	non_perfectly_nested = true;	×
128	continue;	×
129	} else if (dynamic_cast<structured_control_flow::Return*>(current)) {	×
NEW 130	non_perfectly_nested = true;	×
131	continue;	×
132	} else {	×
133	throw std::runtime_error("Unsupported control flow node type");	×
134	}	×
135	}	3,568✔
136
137	if (parent_loop != nullptr) {	1,494✔
138	auto child_count = loop_children_.at(parent_loop).size();	1,163✔
139	auto& state = loop_infos_.at(parent_loop);	1,163✔
140	state.first.last_child_id = this->next_loop_id_ - 1;	1,163✔
141	state.first.contains_side_effects = side_effects;	1,163✔
142
143	if (child_count > 1) {	1,163✔
144	non_perfectly_nested = true;	83✔
145	} else if (child_count < 1) {	1,080✔
146	non_perfectly_nested = false;	588✔
147	}	588✔
148	if (non_perfectly_nested) {	1,163✔
149	state.first.contains_non_perfectly_nested = non_perfectly_nested;	143✔
150	}	143✔
151	}	1,163✔
152	}	1,494✔
153
NEW 154	structured_control_flow::Sequence* LoopAnalysis::get_loop_content_root(structured_control_flow::ControlFlowNode* loop) {	×
UNCOV 155	structured_control_flow::Sequence* root = nullptr;	×
UNCOV 156	if (auto while_stmt = dynamic_cast<structured_control_flow::While*>(loop)) {	×
UNCOV 157	root = &while_stmt->root();	×
UNCOV 158	} else if (auto loop_stmt = dynamic_cast<structured_control_flow::StructuredLoop*>(loop)) {	×
UNCOV 159	root = &loop_stmt->root();	×
UNCOV 160	} else {	×
161	throw std::runtime_error("Node is not a loop");	×
162	}	×
NEW 163	return root;	×
NEW 164	}	×
165
166	LoopState& LoopAnalysis::compute_loop_infos(structured_control_flow::ControlFlowNode* loop) {	1,163✔
167	// Recursion
168	auto& loop_state = this->loop_infos_.at(loop);	1,163✔
169	LoopInfo& info = loop_state.second;	1,163✔
170	auto& loop_children = this->loop_children_.at(loop);	1,163✔
171
172	bool is_perfectly_nested = !loop_state.first.contains_non_perfectly_nested;	1,163✔
173	bool is_perfectly_parallel = loop_state.first.is_map;	1,163✔
174	bool is_elementwise = loop_state.first.is_elementwise;	1,163✔
175	bool map_stack_member = loop_state.first.is_map;	1,163✔
176	bool has_side_effects = loop_state.first.contains_side_effects;	1,163✔
177	bool map_stack_children = map_stack_member && loop_children.size() <= 1;	1,163✔
178	uint32_t map_stack_depth = 0;	1,163✔
179
180	for (auto& child_loop : loop_children) {	1,163✔
181	this->compute_loop_infos(child_loop);	680✔
182
183	auto& sub_info = this->loop_infos_.at(child_loop).second;	680✔
184	info.num_loops += sub_info.num_loops;	680✔
185	info.num_maps += sub_info.num_maps;	680✔
186	info.num_fors += sub_info.num_fors;	680✔
187	info.num_whiles += sub_info.num_whiles;	680✔
188	info.max_depth = std::max(info.max_depth, 1 + sub_info.max_depth);	680✔
189
190	has_side_effects \|= sub_info.has_side_effects;	680✔
191	is_perfectly_nested &= sub_info.is_perfectly_nested;	680✔
192	is_perfectly_parallel &= sub_info.is_perfectly_parallel;	680✔
193	is_elementwise &= sub_info.is_elementwise;	680✔
194	if (map_stack_children) {	680✔
195	map_stack_depth = sub_info.map_stack_depth; // only allowed if there is just a single, direct child	270✔
196	}	270✔
197	}	680✔
198
199	info.is_perfectly_parallel = is_perfectly_parallel;	1,163✔
200	info.is_perfectly_nested = is_perfectly_nested;	1,163✔
201	info.is_elementwise &= is_elementwise && is_perfectly_nested & is_perfectly_parallel;	1,163✔
202	info.has_side_effects = has_side_effects;	1,163✔
203	if (map_stack_member) {	1,163✔
204	if (!is_perfectly_nested) { // needs to be perfectly nested to form a larger stack	605✔
205	map_stack_depth = 0;	58✔
206	}	58✔
207	info.map_stack_depth = map_stack_depth + 1;	605✔
208	}	605✔
209
210	return loop_state;	1,163✔
211	}	1,163✔
212
213	void LoopAnalysis::run(AnalysisManager& analysis_manager) {	331✔
214	this->loops_.clear();	331✔
215	this->loop_tree_.clear();	331✔
216	this->loop_infos_.clear();	331✔
217	this->loop_children_.clear();	331✔
218	this->loop_children_[nullptr]; // ensure it exists	331✔
219	this->run(this->sdfg_.root(), nullptr, 0);	331✔
220
221	// Set loopnest indices for outermost loops
222	int loopnest_index = 0;	331✔
223	auto root_it = this->loop_children_.find(nullptr);	331✔
224	if (root_it != this->loop_children_.end()) {	331✔
225	auto& root_loops = root_it->second;	331✔
226	for (auto* root_loop : root_loops) {	483✔
227	this->compute_loop_infos(root_loop);	483✔
228	this->loop_infos_[root_loop].second.loopnest_index = loopnest_index++;	483✔
229	}	483✔
230	}	331✔
231	}	331✔
232
233	const std::vector<structured_control_flow::ControlFlowNode*> LoopAnalysis::loops() const { return this->loops_; }	180✔
234
235	LoopInfo LoopAnalysis::loop_info(structured_control_flow::ControlFlowNode* loop) const {	353✔
236	return this->loop_infos_.at(loop).second;	353✔
237	}	353✔
238
239	const LocalLoopInfo& LoopAnalysis::loop_info_local(structured_control_flow::ControlFlowNode* loop) const {	3✔
240	return this->loop_infos_.at(loop).first;	3✔
241	}	3✔
242
243	structured_control_flow::ControlFlowNode* LoopAnalysis::find_loop_by_indvar(const std::string& indvar) {	×
244	for (auto& loop : this->loops_) {	×
245	if (auto loop_stmt = dynamic_cast<structured_control_flow::StructuredLoop*>(loop)) {	×
246	if (loop_stmt->indvar()->get_name() == indvar) {	×
247	return loop;	×
248	}	×
249	}	×
250	}	×
251	return nullptr;	×
252	}	×
253
254	const std::map<structured_control_flow::ControlFlowNode, structured_control_flow::ControlFlowNode, DFSLoopComparator>&
255	LoopAnalysis::loop_tree() const {	104✔
256	return this->loop_tree_;	104✔
257	}	104✔
258
259	structured_control_flow::ControlFlowNode* LoopAnalysis::parent_loop(structured_control_flow::ControlFlowNode* loop
260	) const {	27✔
261	return this->loop_tree_.at(loop);	27✔
262	}	27✔
263
264	const std::vector<structured_control_flow::ControlFlowNode*>& LoopAnalysis::outermost_loops() const {	145✔
265	return loop_children_.at(nullptr);	145✔
266	}	145✔
267
268	bool LoopAnalysis::is_outermost_loop(structured_control_flow::ControlFlowNode* loop) const {	×
269	if (this->loop_tree_.find(loop) == this->loop_tree_.end()) {	×
270	return false;	×
271	}	×
272	return this->loop_tree_.at(loop) == nullptr;	×
273	}	×
274
275	const std::vector<structured_control_flow::ControlFlowNode*> LoopAnalysis::outermost_maps() const {	×
276	std::vector<structured_control_flow::ControlFlowNode*> outermost_maps_;	×
277	for (const auto& [loop, parent] : this->loop_tree_) {	×
278	if (dynamic_cast<structured_control_flow::Map*>(loop)) {	×
279	auto ancestor = parent;	×
280	while (true) {	×
281	if (ancestor == nullptr) {	×
282	outermost_maps_.push_back(loop);	×
283	break;	×
284	}	×
285	if (dynamic_cast<structured_control_flow::Map*>(ancestor)) {	×
286	break;	×
287	}	×
288	ancestor = this->loop_tree_.at(ancestor);	×
289	}	×
290	}	×
291	}	×
292	return outermost_maps_;	×
293	}	×
294
295	const std::vector<sdfg::structured_control_flow::ControlFlowNode*>& LoopAnalysis::
296	children(sdfg::structured_control_flow::ControlFlowNode* node) const {	8,137✔
297	// Find unique child
298	return loop_children_.at(node);	8,137✔
299	}	8,137✔
300
301	std::list<std::vector<sdfg::structured_control_flow::ControlFlowNode*>> LoopAnalysis::
302	loop_tree_paths(sdfg::structured_control_flow::ControlFlowNode* loop) const {	318✔
303	return this->loop_tree_paths(loop, this->loop_tree_);	318✔
304	};	318✔
305
306	std::list<std::vector<sdfg::structured_control_flow::ControlFlowNode*>> LoopAnalysis::loop_tree_paths(
307	sdfg::structured_control_flow::ControlFlowNode* loop,
308	const std::map<
309	sdfg::structured_control_flow::ControlFlowNode*,
310	sdfg::structured_control_flow::ControlFlowNode*,
311	DFSLoopComparator>& tree
312	) const {	695✔
313	// Collect all paths in tree starting from loop recursively (DFS)
314	std::list<std::vector<sdfg::structured_control_flow::ControlFlowNode*>> paths;	695✔
315	auto& children = this->children(loop);	695✔
316	if (children.empty()) {	695✔
317	paths.push_back({loop});	364✔
318	return paths;	364✔
319	}	364✔
320
321	for (auto& child : children) {	377✔
322	auto p = this->loop_tree_paths(child, tree);	377✔
323	for (auto& path : p) {	393✔
324	path.insert(path.begin(), loop);	393✔
325	paths.push_back(path);	393✔
326	}	393✔
327	}	377✔
328
329	return paths;	331✔
330	};	695✔
331
332	std::unordered_set<sdfg::structured_control_flow::ControlFlowNode*> LoopAnalysis::
333	descendants(sdfg::structured_control_flow::ControlFlowNode* loop) const {	2,204✔
334	std::unordered_set<sdfg::structured_control_flow::ControlFlowNode*> desc;	2,204✔
335	std::list<sdfg::structured_control_flow::ControlFlowNode*> queue = {loop};	2,204✔
336	while (!queue.empty()) {	9,639✔
337	auto current = queue.front();	7,435✔
338	queue.pop_front();	7,435✔
339	auto& children = this->children(current);	7,435✔
340	for (auto& child : children) {	7,435✔
341	if (desc.find(child) == desc.end()) {	5,231✔
342	desc.insert(child);	5,231✔
343	queue.push_back(child);	5,231✔
344	}	5,231✔
345	}	5,231✔
346	}	7,435✔
347	return desc;	2,204✔
348	}	2,204✔
349
NEW 350	void LoopAnalysis::dump_to_file(std::filesystem::path file) const {	×
NEW 351	nlohmann::json arr;	×
NEW 352	for (auto& loop : this->loops_) {	×
NEW 353	auto& info = loop_infos_.at(loop);	×
354
NEW 355	arr.push_back(loop_info_to_json(info.second));	×
NEW 356	}	×
357
358
NEW 359	std::filesystem::create_directories(file.parent_path());	×
NEW 360	std::ofstream out(file, std::ofstream::out);	×
NEW 361	if (!out.is_open()) {	×
NEW 362	std::cerr << "Could not open file " << file << " for writing JSON output." << std::endl;	×
NEW 363	}	×
NEW 364	out << arr << std::endl;	×
NEW 365	out.close();	×
NEW 366	}	×
367
368	} // namespace analysis
369	} // namespace sdfg

daisytuner / docc / 27623444566

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