18644663668

Committed 20 Oct 2025 06:55AM UTC coverage: 60.996% (-0.5%) from 61.539%

Build # 18644663668

Build Type

Pull #282

github

Committed by

web-flow

Commit Message

Merge bbf0d3975 into d28faa6f0

Pull Request Pull Request #282: Performance Improvements for several passes

Run Details

197 of 415 new or added lines in 16 files covered. (47.47%)

8 existing lines in 1 file now uncovered.

9211 of 15101 relevant lines covered (61.0%)

91.74 hits per line

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

36.11

/src/analysis/reference_analysis.cpp

#include "sdfg/analysis/reference_analysis.h"

#include <cassert>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#include "sdfg/analysis/analysis.h"
#include "sdfg/analysis/loop_analysis.h"
#include "sdfg/structured_sdfg.h"
#include "sdfg/symbolic/maps.h"
#include "sdfg/symbolic/sets.h"

namespace sdfg {
namespace analysis {

ReferenceAnalysis::ReferenceAnalysis(StructuredSDFG& sdfg)
    : Analysis(sdfg), node_(sdfg.root()) {

      };

void ReferenceAnalysis::run(analysis::AnalysisManager& analysis_manager) {
    results_.clear();

    std::unordered_set<User*> undefined;
    std::unordered_map<User*, std::unordered_set<User*>> open_definitions;
    std::unordered_map<User*, std::unordered_set<User*>> closed_definitions;

    auto& users = analysis_manager.get<Users>();
    visit_sequence(users, node_, undefined, open_definitions, closed_definitions);

    for (auto& entry : open_definitions) {
        closed_definitions.insert(entry);
    }

    for (auto& entry : closed_definitions) {
        if (results_.find(entry.first->container()) == results_.end()) {
            results_.insert({entry.first->container(), {}});
        }
        results_.at(entry.first->container()).insert(entry);
    }
};

/****** Visitor API ******/

void ReferenceAnalysis::visit_block(
    analysis::Users& users,
    structured_control_flow::Block& block,
    std::unordered_set<User*>& undefined,
    std::unordered_map<User*, std::unordered_set<User*>>& open_definitions,
    std::unordered_map<User*, std::unordered_set<User*>>& closed_definitions
) {
    auto& dataflow = block.dataflow();

    for (auto node : dataflow.topological_sort()) {
        if (!dynamic_cast<data_flow::AccessNode*>(node) || dynamic_cast<data_flow::ConstantNode*>(node)) {
            continue;
        }
        auto access_node = static_cast<data_flow::AccessNode*>(node);

        // New definition (Move)
        if (dataflow.in_degree(*node) == 1) {
            auto& iedge = *dataflow.in_edges(*access_node).begin();
            if (iedge.type() == data_flow::MemletType::Reference) {
                auto current_user = users.get_user(access_node->data(), access_node, Use::MOVE);
                // Close all definitions that we dominate
                std::unordered_map<User*, std::unordered_set<User*>> to_close;
                for (auto& user : open_definitions) {
                    to_close.insert(user);
                }
                for (auto& user : to_close) {
                    open_definitions.erase(user.first);
                    closed_definitions.insert(user);
                }

                // Start new definition
                open_definitions.insert({current_user, {}});

                continue;
            }
        }

        auto read_user = users.get_user(access_node->data(), access_node, Use::READ);
        auto write_user = users.get_user(access_node->data(), access_node, Use::WRITE);
        auto view_user = users.get_user(access_node->data(), access_node, Use::VIEW);
        if (!read_user && !write_user && !view_user) {
            continue;
        }

        // Add uses to open definitions
        bool found = false;
        for (auto& move : open_definitions) {
            if (move.first->container() != access_node->data()) {
                continue;
            }

            if (read_user) {
                move.second.insert(read_user);
            }
            if (write_user) {
                move.second.insert(write_user);
            }
            if (view_user) {
                move.second.insert(view_user);
            }
        }

        if (!found) {
            if (read_user) {
                undefined.insert(read_user);
            }
            if (write_user) {
                undefined.insert(write_user);
            }
            if (view_user) {
                undefined.insert(view_user);
            }
        }
    }
}

void ReferenceAnalysis::visit_if_else(
    analysis::Users& users,
    structured_control_flow::IfElse& if_else,
    std::unordered_set<User*>& undefined,
    std::unordered_map<User*, std::unordered_set<User*>>& open_definitions,
    std::unordered_map<User*, std::unordered_set<User*>>& closed_definitions
) {
    // Read Conditions
    for (size_t i = 0; i < if_else.size(); i++) {
        auto child = if_else.at(i).second;
        for (auto sym : symbolic::atoms(child)) {
            auto current_user = users.get_user(sym->get_name(), &if_else, Use::READ);

            bool found = false;
            for (auto& user : open_definitions) {
                if (user.first->container() == sym->get_name()) {
                    user.second.insert(current_user);
                    found = true;
                }
            }
            if (!found) {
                undefined.insert(current_user);
            }
        }
    }

    std::vector<std::unordered_set<User*>> undefined_branches(if_else.size());
    std::vector<std::unordered_map<User*, std::unordered_set<User*>>> open_definitions_branches(if_else.size());
    std::vector<std::unordered_map<User*, std::unordered_set<User*>>> closed_definitions_branches(if_else.size());
    for (size_t i = 0; i < if_else.size(); i++) {
        auto& child = if_else.at(i).first;
        visit_sequence(
            users, child, undefined_branches.at(i), open_definitions_branches.at(i), closed_definitions_branches.at(i)
        );
    }

    for (auto& closing : closed_definitions_branches) {
        for (auto& entry : closing) {
            closed_definitions.insert(entry);
        }
    }

    for (size_t i = 0; i < if_else.size(); i++) {
        for (auto& entry : undefined_branches.at(i)) {
            bool found = false;
            for (auto& entry2 : open_definitions) {
                if (entry2.first->container() == entry->container()) {
                    entry2.second.insert(entry);
                    found = true;
                }
            }
            if (!found) {
                undefined.insert(entry);
            }
        }
    }

    // Close open reads_after_writes for complete branches
    if (if_else.is_complete()) {
        std::unordered_map<User*, std::unordered_set<User*>> to_close;
        std::unordered_set<std::string> candidates;
        std::unordered_set<std::string> candidates_tmp;

        /* Complete close open reads_after_writes
        1. get candidates from first iteration
        2. iterate over all branches and prune candidates
        3. find prior writes for remaining candidates
        4. close open reads_after_writes for all candidates
        */
        for (auto& entry : open_definitions_branches.at(0)) {
            candidates.insert(entry.first->container());
        }
        for (auto& entry : closed_definitions_branches.at(0)) {
            candidates.insert(entry.first->container());
        }

        for (size_t i = 1; i < if_else.size(); i++) {
            for (auto& entry : open_definitions_branches.at(i)) {
                if (candidates.find(entry.first->container()) != candidates.end()) {
                    candidates_tmp.insert(entry.first->container());
                }
            }
            candidates.swap(candidates_tmp);
            candidates_tmp.clear();
        }

        for (auto& entry : open_definitions) {
            if (candidates.find(entry.first->container()) != candidates.end()) {
                to_close.insert(entry);
            }
        }

        for (auto& entry : to_close) {
            open_definitions.erase(entry.first);
            closed_definitions.insert(entry);
        }
    } else {
        // Over-Approximation: Add all branch definitions to outer definitions or undefined
        // Here we add writes to read sets as "anti-reads"
        for (auto& branch : open_definitions_branches) {
            for (auto& def : branch) {
                bool found = false;
                for (auto& entry : open_definitions) {
                    entry.second.insert(def.first);
                    found = true;
                }
                if (!found) {
                    undefined.insert(def.first);
                }
            }
        }
    }

    for (auto& branch : open_definitions_branches) {
        for (auto& entry : branch) {
            open_definitions.insert(entry);
        }
    }
}

void ReferenceAnalysis::visit_for(
    analysis::Users& users,
    structured_control_flow::StructuredLoop& for_loop,
    std::unordered_set<User*>& undefined,
    std::unordered_map<User*, std::unordered_set<User*>>& open_definitions,
    std::unordered_map<User*, std::unordered_set<User*>>& closed_definitions
) {
    // Visit body
    std::unordered_map<User*, std::unordered_set<User*>> open_definitions_body;
    std::unordered_map<User*, std::unordered_set<User*>> closed_definitions_body;
    std::unordered_set<User*> undefined_body;
    visit_sequence(users, for_loop.root(), undefined_body, open_definitions_body, closed_definitions_body);

    for (auto& entry : closed_definitions_body) {
        closed_definitions.insert(entry);
    }

    for (auto& open : undefined_body) {
        // Loop-carried dependencies
        for (auto& entry : open_definitions_body) {
            if (entry.first->container() == open->container()) {
                entry.second.insert(open);
            }
        }

        bool found = false;
        for (auto entry : open_definitions) {
            if (entry.first->container() != open->container()) {
                continue;
            }

            entry.second.insert(open);
        }

        if (!found) {
            undefined.insert(open);
        }
    }

    for (auto& entry : open_definitions_body) {
        open_definitions.insert(entry);
    }
}

void ReferenceAnalysis::visit_while(
    analysis::Users& users,
    structured_control_flow::While& while_loop,
    std::unordered_set<User*>& undefined,
    std::unordered_map<User*, std::unordered_set<User*>>& open_definitions,
    std::unordered_map<User*, std::unordered_set<User*>>& closed_definitions
) {
    // Visit body
    std::unordered_map<User*, std::unordered_set<User*>> open_definitions_body;
    std::unordered_map<User*, std::unordered_set<User*>> closed_definitions_body;
    std::unordered_set<User*> undefined_body;
    visit_sequence(users, while_loop.root(), undefined_body, open_definitions_body, closed_definitions_body);

    for (auto& entry : closed_definitions_body) {
        closed_definitions.insert(entry);
    }

    for (auto& open : undefined_body) {
        // Loop-carried dependencies
        for (auto& entry : open_definitions_body) {
            if (entry.first->container() == open->container()) {
                entry.second.insert(open);
            }
        }

        bool found = false;
        for (auto entry : open_definitions) {
            if (entry.first->container() != open->container()) {
                continue;
            }

            entry.second.insert(open);
        }

        if (!found) {
            undefined.insert(open);
        }
    }

    for (auto& entry : open_definitions_body) {
        open_definitions.insert(entry);
    }
}

void ReferenceAnalysis::visit_return(
    analysis::Users& users,
    structured_control_flow::Return& return_statement,
    std::unordered_set<User*>& undefined,
    std::unordered_map<User*, std::unordered_set<User*>>& open_definitions,
    std::unordered_map<User*, std::unordered_set<User*>>& closed_definitions
) {
    for (auto& entry : open_definitions) {
        closed_definitions.insert(entry);
    }
    open_definitions.clear();
}

void ReferenceAnalysis::visit_sequence(
    analysis::Users& users,
    structured_control_flow::Sequence& sequence,
    std::unordered_set<User*>& undefined,
    std::unordered_map<User*, std::unordered_set<User*>>& open_definitions,
    std::unordered_map<User*, std::unordered_set<User*>>& closed_definitions
) {
    for (size_t i = 0; i < sequence.size(); i++) {
        auto child = sequence.at(i);
        if (auto block = dynamic_cast<structured_control_flow::Block*>(&child.first)) {
            visit_block(users, *block, undefined, open_definitions, closed_definitions);
        } else if (auto for_loop = dynamic_cast<structured_control_flow::StructuredLoop*>(&child.first)) {
            visit_for(users, *for_loop, undefined, open_definitions, closed_definitions);
        } else if (auto if_else = dynamic_cast<structured_control_flow::IfElse*>(&child.first)) {
            visit_if_else(users, *if_else, undefined, open_definitions, closed_definitions);
        } else if (auto while_loop = dynamic_cast<structured_control_flow::While*>(&child.first)) {
            visit_while(users, *while_loop, undefined, open_definitions, closed_definitions);
        } else if (auto return_statement = dynamic_cast<structured_control_flow::Return*>(&child.first)) {
            visit_return(users, *return_statement, undefined, open_definitions, closed_definitions);
        } else if (auto sequence = dynamic_cast<structured_control_flow::Sequence*>(&child.first)) {
            visit_sequence(users, *sequence, undefined, open_definitions, closed_definitions);
        }
    }
}

std::unordered_set<User*> ReferenceAnalysis::defines(User& move) {
    assert(move.use() == Use::MOVE);
    if (results_.find(move.container()) == results_.end()) {
        return {};
    }
    auto& raws = results_.at(move.container());
    assert(raws.find(&move) != raws.end());

    auto& users_for_move = raws.at(&move);

    std::unordered_set<User*> users;
    for (auto& entry : users_for_move) {
        users.insert(entry);
    }

    return users;
};

std::unordered_map<User*, std::unordered_set<User*>> ReferenceAnalysis::definitions(const std::string& container) {
    if (results_.find(container) == results_.end()) {
        return {};
    }
    return results_.at(container);
};

std::unordered_set<User*> ReferenceAnalysis::defined_by(User& user) {
    auto definitions = this->definitions(user.container());

    std::unordered_set<User*> moves;
    for (auto& entry : definitions) {
        for (auto& r : entry.second) {
            if (&user == r) {
                moves.insert(entry.first);
            }
        }
    }
    return moves;
};

std::unordered_map<User*, std::unordered_set<User*>> ReferenceAnalysis::defined_by(const std::string& container) {
    auto moves = this->definitions(container);

    std::unordered_map<User*, std::unordered_set<User*>> uses_to_move_map;
    for (auto& entry : moves) {
        for (auto& use : entry.second) {
            if (uses_to_move_map.find(use) == uses_to_move_map.end()) {
                uses_to_move_map[use] = {};
            }
            uses_to_move_map[use].insert(entry.first);
        }
    }
    return uses_to_move_map;
};

} // namespace analysis
} // namespace sdfg

1	#include "sdfg/analysis/reference_analysis.h"
2
3	#include <cassert>
4	#include <string>
5	#include <unordered_map>
6	#include <unordered_set>
7	#include <vector>
8
9	#include "sdfg/analysis/analysis.h"
10	#include "sdfg/analysis/loop_analysis.h"
11	#include "sdfg/structured_sdfg.h"
12	#include "sdfg/symbolic/maps.h"
13	#include "sdfg/symbolic/sets.h"
14
15	namespace sdfg {
16	namespace analysis {
17
18	ReferenceAnalysis::ReferenceAnalysis(StructuredSDFG& sdfg)	7✔
19	: Analysis(sdfg), node_(sdfg.root()) {	7✔
20
21	};	7✔
22
23	void ReferenceAnalysis::run(analysis::AnalysisManager& analysis_manager) {	7✔
24	results_.clear();	7✔
25
26	std::unordered_set<User*> undefined;	7✔
27	std::unordered_map<User, std::unordered_set<User>> open_definitions;	7✔
28	std::unordered_map<User, std::unordered_set<User>> closed_definitions;	7✔
29
30	auto& users = analysis_manager.get<Users>();	7✔
31	visit_sequence(users, node_, undefined, open_definitions, closed_definitions);	7✔
32
33	for (auto& entry : open_definitions) {	14✔
34	closed_definitions.insert(entry);	7✔
35	}
36
37	for (auto& entry : closed_definitions) {	16✔
38	if (results_.find(entry.first->container()) == results_.end()) {	9✔
39	results_.insert({entry.first->container(), {}});	8✔
40	}	8✔
41	results_.at(entry.first->container()).insert(entry);	9✔
42	}
43	};	7✔
44
45	/**** Visitor API ****/
46
47	void ReferenceAnalysis::visit_block(	14✔
48	analysis::Users& users,
49	structured_control_flow::Block& block,
50	std::unordered_set<User*>& undefined,
51	std::unordered_map<User, std::unordered_set<User>>& open_definitions,
52	std::unordered_map<User, std::unordered_set<User>>& closed_definitions
53	) {
54	auto& dataflow = block.dataflow();	14✔
55
56	for (auto node : dataflow.topological_sort()) {	44✔
57	if (!dynamic_cast<data_flow::AccessNode>(node) \|\| dynamic_cast<data_flow::ConstantNode>(node)) {	30✔
58	continue;	2✔
59	}
60	auto access_node = static_cast<data_flow::AccessNode*>(node);	28✔
61
62	// New definition (Move)
63	if (dataflow.in_degree(*node) == 1) {	28✔
64	auto& iedge = dataflow.in_edges(access_node).begin();	14✔
65	if (iedge.type() == data_flow::MemletType::Reference) {	14✔
66	auto current_user = users.get_user(access_node->data(), access_node, Use::MOVE);	9✔
67	// Close all definitions that we dominate
68	std::unordered_map<User, std::unordered_set<User>> to_close;	9✔
69	for (auto& user : open_definitions) {	11✔
70	to_close.insert(user);	2✔
71	}
72	for (auto& user : to_close) {	11✔
73	open_definitions.erase(user.first);	2✔
74	closed_definitions.insert(user);	2✔
75	}
76
77	// Start new definition
78	open_definitions.insert({current_user, {}});	9✔
79
80	continue;
81	}	9✔
82	}	5✔
83
84	auto read_user = users.get_user(access_node->data(), access_node, Use::READ);	19✔
85	auto write_user = users.get_user(access_node->data(), access_node, Use::WRITE);	19✔
86	auto view_user = users.get_user(access_node->data(), access_node, Use::VIEW);	19✔
87	if (!read_user && !write_user && !view_user) {	19✔
88	continue;	1✔
89	}
90
91	// Add uses to open definitions
92	bool found = false;	18✔
93	for (auto& move : open_definitions) {	29✔
94	if (move.first->container() != access_node->data()) {	11✔
95	continue;	3✔
96	}
97
98	if (read_user) {	8✔
99	move.second.insert(read_user);	3✔
100	}	3✔
101	if (write_user) {	8✔
102	move.second.insert(write_user);	4✔
103	}	4✔
104	if (view_user) {	8✔
105	move.second.insert(view_user);	1✔
106	}	1✔
107	}
108
109	if (!found) {	18✔
110	if (read_user) {	18✔
111	undefined.insert(read_user);	3✔
112	}	3✔
113	if (write_user) {	18✔
114	undefined.insert(write_user);	4✔
115	}	4✔
116	if (view_user) {	18✔
117	undefined.insert(view_user);	11✔
118	}	11✔
119	}	18✔
120	}
121	}	14✔
122
NEW 123	void ReferenceAnalysis::visit_if_else(	×
124	analysis::Users& users,
125	structured_control_flow::IfElse& if_else,
126	std::unordered_set<User*>& undefined,
127	std::unordered_map<User, std::unordered_set<User>>& open_definitions,
128	std::unordered_map<User, std::unordered_set<User>>& closed_definitions
129	) {
130	// Read Conditions
NEW 131	for (size_t i = 0; i < if_else.size(); i++) {	×
NEW 132	auto child = if_else.at(i).second;	×
NEW 133	for (auto sym : symbolic::atoms(child)) {	×
NEW 134	auto current_user = users.get_user(sym->get_name(), &if_else, Use::READ);	×
135
NEW 136	bool found = false;	×
NEW 137	for (auto& user : open_definitions) {	×
NEW 138	if (user.first->container() == sym->get_name()) {	×
NEW 139	user.second.insert(current_user);	×
NEW 140	found = true;	×
NEW 141	}	×
142	}
NEW 143	if (!found) {	×
NEW 144	undefined.insert(current_user);	×
NEW 145	}	×
NEW 146	}	×
NEW 147	}	×
148
NEW 149	std::vector<std::unordered_set<User*>> undefined_branches(if_else.size());	×
NEW 150	std::vector<std::unordered_map<User, std::unordered_set<User>>> open_definitions_branches(if_else.size());	×
NEW 151	std::vector<std::unordered_map<User, std::unordered_set<User>>> closed_definitions_branches(if_else.size());	×
NEW 152	for (size_t i = 0; i < if_else.size(); i++) {	×
NEW 153	auto& child = if_else.at(i).first;	×
NEW 154	visit_sequence(	×
NEW 155	users, child, undefined_branches.at(i), open_definitions_branches.at(i), closed_definitions_branches.at(i)	×
156	);
NEW 157	}	×
158
NEW 159	for (auto& closing : closed_definitions_branches) {	×
NEW 160	for (auto& entry : closing) {	×
NEW 161	closed_definitions.insert(entry);	×
162	}
163	}
164
NEW 165	for (size_t i = 0; i < if_else.size(); i++) {	×
NEW 166	for (auto& entry : undefined_branches.at(i)) {	×
NEW 167	bool found = false;	×
NEW 168	for (auto& entry2 : open_definitions) {	×
NEW 169	if (entry2.first->container() == entry->container()) {	×
NEW 170	entry2.second.insert(entry);	×
NEW 171	found = true;	×
NEW 172	}	×
173	}
NEW 174	if (!found) {	×
NEW 175	undefined.insert(entry);	×
NEW 176	}	×
177	}
NEW 178	}	×
179
180	// Close open reads_after_writes for complete branches
NEW 181	if (if_else.is_complete()) {	×
NEW 182	std::unordered_map<User, std::unordered_set<User>> to_close;	×
NEW 183	std::unordered_set<std::string> candidates;	×
NEW 184	std::unordered_set<std::string> candidates_tmp;	×
185
186	/* Complete close open reads_after_writes
187	1. get candidates from first iteration
188	2. iterate over all branches and prune candidates
189	3. find prior writes for remaining candidates
190	4. close open reads_after_writes for all candidates
191	*/
NEW 192	for (auto& entry : open_definitions_branches.at(0)) {	×
NEW 193	candidates.insert(entry.first->container());	×
194	}
NEW 195	for (auto& entry : closed_definitions_branches.at(0)) {	×
NEW 196	candidates.insert(entry.first->container());	×
197	}
198
NEW 199	for (size_t i = 1; i < if_else.size(); i++) {	×
NEW 200	for (auto& entry : open_definitions_branches.at(i)) {	×
NEW 201	if (candidates.find(entry.first->container()) != candidates.end()) {	×
NEW 202	candidates_tmp.insert(entry.first->container());	×
NEW 203	}	×
204	}
NEW 205	candidates.swap(candidates_tmp);	×
NEW 206	candidates_tmp.clear();	×
NEW 207	}	×
208
NEW 209	for (auto& entry : open_definitions) {	×
NEW 210	if (candidates.find(entry.first->container()) != candidates.end()) {	×
NEW 211	to_close.insert(entry);	×
NEW 212	}	×
213	}
214
NEW 215	for (auto& entry : to_close) {	×
NEW 216	open_definitions.erase(entry.first);	×
NEW 217	closed_definitions.insert(entry);	×
218	}
NEW 219	} else {	×
220	// Over-Approximation: Add all branch definitions to outer definitions or undefined
221	// Here we add writes to read sets as "anti-reads"
NEW 222	for (auto& branch : open_definitions_branches) {	×
NEW 223	for (auto& def : branch) {	×
NEW 224	bool found = false;	×
NEW 225	for (auto& entry : open_definitions) {	×
NEW 226	entry.second.insert(def.first);	×
NEW 227	found = true;	×
228	}
NEW 229	if (!found) {	×
NEW 230	undefined.insert(def.first);	×
NEW 231	}	×
232	}
233	}
234	}
235
NEW 236	for (auto& branch : open_definitions_branches) {	×
NEW 237	for (auto& entry : branch) {	×
NEW 238	open_definitions.insert(entry);	×
239	}
240	}
NEW 241	}	×
242
NEW 243	void ReferenceAnalysis::visit_for(	×
244	analysis::Users& users,
245	structured_control_flow::StructuredLoop& for_loop,
246	std::unordered_set<User*>& undefined,
247	std::unordered_map<User, std::unordered_set<User>>& open_definitions,
248	std::unordered_map<User, std::unordered_set<User>>& closed_definitions
249	) {
250	// Visit body
NEW 251	std::unordered_map<User, std::unordered_set<User>> open_definitions_body;	×
NEW 252	std::unordered_map<User, std::unordered_set<User>> closed_definitions_body;	×
NEW 253	std::unordered_set<User*> undefined_body;	×
NEW 254	visit_sequence(users, for_loop.root(), undefined_body, open_definitions_body, closed_definitions_body);	×
255
NEW 256	for (auto& entry : closed_definitions_body) {	×
NEW 257	closed_definitions.insert(entry);	×
258	}
259
NEW 260	for (auto& open : undefined_body) {	×
261	// Loop-carried dependencies
NEW 262	for (auto& entry : open_definitions_body) {	×
NEW 263	if (entry.first->container() == open->container()) {	×
NEW 264	entry.second.insert(open);	×
NEW 265	}	×
266	}
267
NEW 268	bool found = false;	×
NEW 269	for (auto entry : open_definitions) {	×
NEW 270	if (entry.first->container() != open->container()) {	×
NEW 271	continue;	×
272	}
273
NEW 274	entry.second.insert(open);	×
NEW 275	}	×
276
NEW 277	if (!found) {	×
NEW 278	undefined.insert(open);	×
NEW 279	}	×
280	}
281
NEW 282	for (auto& entry : open_definitions_body) {	×
NEW 283	open_definitions.insert(entry);	×
284	}
NEW 285	}	×
286
NEW 287	void ReferenceAnalysis::visit_while(	×
288	analysis::Users& users,
289	structured_control_flow::While& while_loop,
290	std::unordered_set<User*>& undefined,
291	std::unordered_map<User, std::unordered_set<User>>& open_definitions,
292	std::unordered_map<User, std::unordered_set<User>>& closed_definitions
293	) {
294	// Visit body
NEW 295	std::unordered_map<User, std::unordered_set<User>> open_definitions_body;	×
NEW 296	std::unordered_map<User, std::unordered_set<User>> closed_definitions_body;	×
NEW 297	std::unordered_set<User*> undefined_body;	×
NEW 298	visit_sequence(users, while_loop.root(), undefined_body, open_definitions_body, closed_definitions_body);	×
299
NEW 300	for (auto& entry : closed_definitions_body) {	×
NEW 301	closed_definitions.insert(entry);	×
302	}
303
NEW 304	for (auto& open : undefined_body) {	×
305	// Loop-carried dependencies
NEW 306	for (auto& entry : open_definitions_body) {	×
NEW 307	if (entry.first->container() == open->container()) {	×
NEW 308	entry.second.insert(open);	×
NEW 309	}	×
310	}
311
NEW 312	bool found = false;	×
NEW 313	for (auto entry : open_definitions) {	×
NEW 314	if (entry.first->container() != open->container()) {	×
NEW 315	continue;	×
316	}
317
NEW 318	entry.second.insert(open);	×
NEW 319	}	×
320
NEW 321	if (!found) {	×
NEW 322	undefined.insert(open);	×
NEW 323	}	×
324	}
325
NEW 326	for (auto& entry : open_definitions_body) {	×
NEW 327	open_definitions.insert(entry);	×
328	}
NEW 329	}	×
330
NEW 331	void ReferenceAnalysis::visit_return(	×
332	analysis::Users& users,
333	structured_control_flow::Return& return_statement,
334	std::unordered_set<User*>& undefined,
335	std::unordered_map<User, std::unordered_set<User>>& open_definitions,
336	std::unordered_map<User, std::unordered_set<User>>& closed_definitions
337	) {
NEW 338	for (auto& entry : open_definitions) {	×
NEW 339	closed_definitions.insert(entry);	×
340	}
NEW 341	open_definitions.clear();	×
NEW 342	}	×
343
344	void ReferenceAnalysis::visit_sequence(	7✔
345	analysis::Users& users,
346	structured_control_flow::Sequence& sequence,
347	std::unordered_set<User*>& undefined,
348	std::unordered_map<User, std::unordered_set<User>>& open_definitions,
349	std::unordered_map<User, std::unordered_set<User>>& closed_definitions
350	) {
351	for (size_t i = 0; i < sequence.size(); i++) {	21✔
352	auto child = sequence.at(i);	14✔
353	if (auto block = dynamic_cast<structured_control_flow::Block*>(&child.first)) {	14✔
354	visit_block(users, *block, undefined, open_definitions, closed_definitions);	14✔
355	} else if (auto for_loop = dynamic_cast<structured_control_flow::StructuredLoop*>(&child.first)) {	14✔
NEW 356	visit_for(users, *for_loop, undefined, open_definitions, closed_definitions);	×
NEW 357	} else if (auto if_else = dynamic_cast<structured_control_flow::IfElse*>(&child.first)) {	×
NEW 358	visit_if_else(users, *if_else, undefined, open_definitions, closed_definitions);	×
NEW 359	} else if (auto while_loop = dynamic_cast<structured_control_flow::While*>(&child.first)) {	×
NEW 360	visit_while(users, *while_loop, undefined, open_definitions, closed_definitions);	×
NEW 361	} else if (auto return_statement = dynamic_cast<structured_control_flow::Return*>(&child.first)) {	×
NEW 362	visit_return(users, *return_statement, undefined, open_definitions, closed_definitions);	×
NEW 363	} else if (auto sequence = dynamic_cast<structured_control_flow::Sequence*>(&child.first)) {	×
NEW 364	visit_sequence(users, *sequence, undefined, open_definitions, closed_definitions);	×
NEW 365	}	×
366	}	14✔
367	}	7✔
368
NEW 369	std::unordered_set<User*> ReferenceAnalysis::defines(User& move) {	×
NEW 370	assert(move.use() == Use::MOVE);	×
NEW 371	if (results_.find(move.container()) == results_.end()) {	×
NEW 372	return {};	×
373	}
NEW 374	auto& raws = results_.at(move.container());	×
NEW 375	assert(raws.find(&move) != raws.end());	×
376
NEW 377	auto& users_for_move = raws.at(&move);	×
378
NEW 379	std::unordered_set<User*> users;	×
NEW 380	for (auto& entry : users_for_move) {	×
NEW 381	users.insert(entry);	×
382	}
383
NEW 384	return users;	×
NEW 385	};	×
386
387	std::unordered_map<User, std::unordered_set<User>> ReferenceAnalysis::definitions(const std::string& container) {	10✔
388	if (results_.find(container) == results_.end()) {	10✔
389	return {};	3✔
390	}
391	return results_.at(container);	7✔
392	};	10✔
393
NEW 394	std::unordered_set<User*> ReferenceAnalysis::defined_by(User& user) {	×
NEW 395	auto definitions = this->definitions(user.container());	×
396
NEW 397	std::unordered_set<User*> moves;	×
NEW 398	for (auto& entry : definitions) {	×
NEW 399	for (auto& r : entry.second) {	×
NEW 400	if (&user == r) {	×
NEW 401	moves.insert(entry.first);	×
NEW 402	}	×
403	}
404	}
NEW 405	return moves;	×
NEW 406	};	×
407
408	std::unordered_map<User, std::unordered_set<User>> ReferenceAnalysis::defined_by(const std::string& container) {	10✔
409	auto moves = this->definitions(container);	10✔
410
411	std::unordered_map<User, std::unordered_set<User>> uses_to_move_map;	10✔
412	for (auto& entry : moves) {	18✔
413	for (auto& use : entry.second) {	16✔
414	if (uses_to_move_map.find(use) == uses_to_move_map.end()) {	8✔
415	uses_to_move_map[use] = {};	8✔
416	}	8✔
417	uses_to_move_map[use].insert(entry.first);	8✔
418	}
419	}
420	return uses_to_move_map;	10✔
421	};	10✔
422
423	} // namespace analysis
424	} // namespace sdfg

daisytuner / sdfglib / 18644663668

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