15656007340

Committed 14 Jun 2025 08:51PM UTC coverage: 13.234% (-49.9%) from 63.144%

Build # 15656007340

Build Type

Pull #76

github

Committed by

web-flow

Commit Message

Merge 9586c8161 into 413c53212

Pull Request Pull Request #76: New Loop Dependency Analysis

Run Details

361 of 465 new or added lines in 7 files covered. (77.63%)

6215 existing lines in 110 files now uncovered.

1612 of 12181 relevant lines covered (13.23%)

13.64 hits per line

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

96.64

/src/analysis/loop_dependency_analysis.cpp

#include "sdfg/analysis/loop_dependency_analysis.h"

#include "sdfg/analysis/assumptions_analysis.h"
#include "sdfg/analysis/loop_analysis.h"
#include "sdfg/symbolic/sets.h"

namespace sdfg {
namespace analysis {

LoopDependencyAnalysis::LoopDependencyAnalysis(StructuredSDFG& sdfg)
    : Analysis(sdfg) {

      };

void LoopDependencyAnalysis::run(analysis::AnalysisManager& analysis_manager) {
    this->results_.clear();

    auto& loops_analsis = analysis_manager.get<analysis::LoopAnalysis>();
    for (auto& loop : loops_analsis.loops()) {
        if (auto sloop = dynamic_cast<structured_control_flow::StructuredLoop*>(loop)) {
            this->analyze(analysis_manager, sloop);
        }
    }
};

LoopDependencyAnalysisResult LoopDependencyAnalysis::get(
    const structured_control_flow::StructuredLoop& loop) const {
    return this->results_.at(&loop);
};

void LoopDependencyAnalysis::analyze(analysis::AnalysisManager& analysis_manager,
                                     structured_control_flow::StructuredLoop* loop) {
    auto& loop_analysis = analysis_manager.get<analysis::LoopAnalysis>();
    std::cout << "LoopDependencyAnalysis::analyze" << std::endl;

    // Criterion: Strictly monotonic update
    // I.e., the indvar never taskes the same value twice
    if (!loop_analysis.is_monotonic(loop)) {
        return;
    }
    std::cout << "is monotonic" << std::endl;

    // Criterion: No pointer assignments
    auto& body = loop->root();
    auto& users = analysis_manager.get<analysis::Users>();
    analysis::UsersView body_users(users, body);
    if (!body_users.views().empty() || !body_users.moves().empty()) {
        return;
    }
    std::cout << "no pointer assignments" << std::endl;

    /*** Dependency Analysis ***/

    LoopDependencyAnalysisResult result;
    std::cout << "Loop: " << loop->indvar()->get_name() << std::endl;

    // Step 0: Get assumptions
    auto& assumptions = analysis_manager.get<analysis::AssumptionsAnalysis>();
    auto body_assums = assumptions.get(body);

    // Step 1: For loop-carried dependency, the container must be written
    std::cout << "Written containers: ";
    std::unordered_set<std::string> written_containers;
    for (auto& write : body_users.writes()) {
        written_containers.insert(write->container());
        std::cout << write->container() << ",";
    }
    std::cout << std::endl;

    // Step 2: Find all reads potentially causing loop-carried dependency
    std::unordered_map<std::string, std::unordered_set<User*>> open_reads;
    for (auto& container : written_containers) {
        auto reads = body_users.reads(container);
        std::cout << "Reads for " << container << ": " << reads.size() << std::endl;

        // Step 3: Filter out reads that are not first uses
        for (auto& read : reads) {
            // If dominated by a write at the same subset, it is not a first use
            if (body_users.is_dominated_by(*read, Use::WRITE, body_assums)) {
                continue;
            }
            std::cout << "Inserting read: " << read->container() << std::endl;
            if (open_reads.find(read->container()) == open_reads.end()) {
                open_reads[read->container()] = {};
            }
            open_reads[read->container()].insert(read);
        }
    }
    std::cout << "Open reads: " << open_reads.size() << std::endl;

    // Step 4: Determine type of dependency
    for (auto& container : written_containers) {
        auto writes = body_users.writes(container);

        // a. Check if reads intersect with writes of other iterations
        if (open_reads.find(container) != open_reads.end()) {
            auto& reads = open_reads[container];
            for (auto& read : reads) {
                for (auto& write : writes) {
                    if (this->intersects(read, write, *loop, body_users, analysis_manager)) {
                        std::cout << "Found RAW dependency: " << read->container() << " "
                                  << write->container() << std::endl;
                        result[container] = LoopCarriedDependency::RAW;
                        break;
                    }
                }
                if (result.find(container) != result.end() &&
                    result.at(container) == LoopCarriedDependency::RAW) {
                    break;
                }
            }
        }

        // For a RAW dependency, we are done
        if (result.find(container) != result.end() &&
            result.at(container) == LoopCarriedDependency::RAW) {
            continue;
        }

        // b. Check if writes intersect with writes of other iterations
        for (auto& write : writes) {
            for (auto& write_other : writes) {
                std::cout << "Checking WAW dependency: " << write->container() << " "
                          << write_other->container() << std::endl;
                if (this->intersects(write, write_other, *loop, body_users, analysis_manager)) {
                    std::cout << "Found WAW dependency: " << write->container() << " "
                              << write_other->container() << std::endl;
                    result[container] = LoopCarriedDependency::WAW;
                    break;
                }
            }
            if (result.find(container) != result.end() &&
                result.at(container) == LoopCarriedDependency::WAW) {
                break;
            }
        }
    }

    std::cout << "Result: " << result.size() << std::endl;
    this->results_[loop] = result;
}

bool LoopDependencyAnalysis::intersects(User* first, User* second,
                                        structured_control_flow::StructuredLoop& loop,
                                        analysis::UsersView& body_users,
                                        analysis::AnalysisManager& analysis_manager) const {
    // Try to find tighter assumptions by lowering the scope
    auto scope_first = analysis::Users::scope(first);
    auto scope_second = analysis::Users::scope(second);
    // Simplification: If the scopes are different, we conservatively assume the loop body as the
    // scope
    if (scope_first != scope_second) {
        scope_first = &loop.root();
    }
    auto& assumptions = analysis_manager.get<analysis::AssumptionsAnalysis>();
    auto scope_assums = assumptions.get(*scope_first);

    for (auto& subset : first->subsets()) {
        // Collect all symbols of the subset;
        symbolic::SymbolSet first_symbols;
        for (auto& dim : subset) {
            for (auto& symbol : symbolic::atoms(dim)) {
                first_symbols.insert(symbol);
            }
        }

        for (auto& subset_other : second->subsets()) {
            // Collect all symbols of the subset;
            symbolic::SymbolSet second_symbols;
            for (auto& dim : subset_other) {
                for (auto& symbol : symbolic::atoms(dim)) {
                    second_symbols.insert(symbol);
                }
            }

            // Collect all symbols of the subsets;
            symbolic::SymbolSet symbols;
            for (auto& symbol : first_symbols) {
                symbols.insert(symbol);
            }
            for (auto& symbol : second_symbols) {
                symbols.insert(symbol);
            }

            // Determine which symbols are readonly -> params
            symbolic::SymbolSet params;
            for (auto& symbol : symbols) {
                if (symbol == loop.indvar()) {
                    continue;
                }
                if (body_users.writes(symbol->get_name()).empty()) {
                    params.insert(symbol);
                }
            }

            if (!symbolic::is_disjoint(subset, subset_other, params, {loop.indvar()},
                                       scope_assums)) {
                return true;
            }
        }
    }
    return false;
}

}  // namespace analysis
}  // namespace sdfg

1	#include "sdfg/analysis/loop_dependency_analysis.h"
2
3	#include "sdfg/analysis/assumptions_analysis.h"
4	#include "sdfg/analysis/loop_analysis.h"
5	#include "sdfg/symbolic/sets.h"
6
7	namespace sdfg {
8	namespace analysis {
9
10	LoopDependencyAnalysis::LoopDependencyAnalysis(StructuredSDFG& sdfg)	34✔
11	: Analysis(sdfg) {	17✔
12
13	};	17✔
14
15	void LoopDependencyAnalysis::run(analysis::AnalysisManager& analysis_manager) {	17✔
16	this->results_.clear();	17✔
17
18	auto& loops_analsis = analysis_manager.get<analysis::LoopAnalysis>();	17✔
19	for (auto& loop : loops_analsis.loops()) {	39✔
20	if (auto sloop = dynamic_cast<structured_control_flow::StructuredLoop*>(loop)) {	22✔
21	this->analyze(analysis_manager, sloop);	22✔
22	}	22✔
23	}
24	};	17✔
25
26	LoopDependencyAnalysisResult LoopDependencyAnalysis::get(	22✔
27	const structured_control_flow::StructuredLoop& loop) const {
28	return this->results_.at(&loop);	22✔
29	};
30
31	void LoopDependencyAnalysis::analyze(analysis::AnalysisManager& analysis_manager,	22✔
32	structured_control_flow::StructuredLoop* loop) {
33	auto& loop_analysis = analysis_manager.get<analysis::LoopAnalysis>();	22✔
34	std::cout << "LoopDependencyAnalysis::analyze" << std::endl;	22✔
35
36	// Criterion: Strictly monotonic update
37	// I.e., the indvar never taskes the same value twice
38	if (!loop_analysis.is_monotonic(loop)) {	22✔
NEW 39	return;	×
40	}
41	std::cout << "is monotonic" << std::endl;	22✔
42
43	// Criterion: No pointer assignments
44	auto& body = loop->root();	22✔
45	auto& users = analysis_manager.get<analysis::Users>();	22✔
46	analysis::UsersView body_users(users, body);	22✔
47	if (!body_users.views().empty() \|\| !body_users.moves().empty()) {	22✔
NEW 48	return;	×
49	}
50	std::cout << "no pointer assignments" << std::endl;	22✔
51
52	/* Dependency Analysis */
53
54	LoopDependencyAnalysisResult result;	22✔
55	std::cout << "Loop: " << loop->indvar()->get_name() << std::endl;	22✔
56
57	// Step 0: Get assumptions
58	auto& assumptions = analysis_manager.get<analysis::AssumptionsAnalysis>();	22✔
59	auto body_assums = assumptions.get(body);	22✔
60
61	// Step 1: For loop-carried dependency, the container must be written
62	std::cout << "Written containers: ";	22✔
63	std::unordered_set<std::string> written_containers;	22✔
64	for (auto& write : body_users.writes()) {	57✔
65	written_containers.insert(write->container());	35✔
66	std::cout << write->container() << ",";	35✔
67	}
68	std::cout << std::endl;	22✔
69
70	// Step 2: Find all reads potentially causing loop-carried dependency
71	std::unordered_map<std::string, std::unordered_set<User*>> open_reads;	22✔
72	for (auto& container : written_containers) {	52✔
73	auto reads = body_users.reads(container);	30✔
74	std::cout << "Reads for " << container << ": " << reads.size() << std::endl;	30✔
75
76	// Step 3: Filter out reads that are not first uses
77	for (auto& read : reads) {	66✔
78	// If dominated by a write at the same subset, it is not a first use
79	if (body_users.is_dominated_by(*read, Use::WRITE, body_assums)) {	36✔
80	continue;	23✔
81	}
82	std::cout << "Inserting read: " << read->container() << std::endl;	13✔
83	if (open_reads.find(read->container()) == open_reads.end()) {	13✔
84	open_reads[read->container()] = {};	12✔
85	}	12✔
86	open_reads[read->container()].insert(read);	13✔
87	}
88	}	30✔
89	std::cout << "Open reads: " << open_reads.size() << std::endl;	22✔
90
91	// Step 4: Determine type of dependency
92	for (auto& container : written_containers) {	52✔
93	auto writes = body_users.writes(container);	30✔
94
95	// a. Check if reads intersect with writes of other iterations
96	if (open_reads.find(container) != open_reads.end()) {	30✔
97	auto& reads = open_reads[container];	12✔
98	for (auto& read : reads) {	20✔
99	for (auto& write : writes) {	20✔
100	if (this->intersects(read, write, *loop, body_users, analysis_manager)) {	12✔
101	std::cout << "Found RAW dependency: " << read->container() << " "	4✔
102	<< write->container() << std::endl;	4✔
103	result[container] = LoopCarriedDependency::RAW;	4✔
104	break;	4✔
105	}
106	}
107	if (result.find(container) != result.end() &&	16✔
108	result.at(container) == LoopCarriedDependency::RAW) {	4✔
109	break;	4✔
110	}
111	}
112	}	12✔
113
114	// For a RAW dependency, we are done
115	if (result.find(container) != result.end() &&	34✔
116	result.at(container) == LoopCarriedDependency::RAW) {	4✔
117	continue;	4✔
118	}
119
120	// b. Check if writes intersect with writes of other iterations
121	for (auto& write : writes) {	42✔
122	for (auto& write_other : writes) {	42✔
123	std::cout << "Checking WAW dependency: " << write->container() << " "	26✔
124	<< write_other->container() << std::endl;	26✔
125	if (this->intersects(write, write_other, *loop, body_users, analysis_manager)) {	26✔
126	std::cout << "Found WAW dependency: " << write->container() << " "	10✔
127	<< write_other->container() << std::endl;	10✔
128	result[container] = LoopCarriedDependency::WAW;	10✔
129	break;	10✔
130	}
131	}
132	if (result.find(container) != result.end() &&	36✔
133	result.at(container) == LoopCarriedDependency::WAW) {	10✔
134	break;	10✔
135	}
136	}
137	}	30✔
138
139	std::cout << "Result: " << result.size() << std::endl;	22✔
140	this->results_[loop] = result;	22✔
141	}	22✔
142
143	bool LoopDependencyAnalysis::intersects(User* first, User* second,	38✔
144	structured_control_flow::StructuredLoop& loop,
145	analysis::UsersView& body_users,
146	analysis::AnalysisManager& analysis_manager) const {
147	// Try to find tighter assumptions by lowering the scope
148	auto scope_first = analysis::Users::scope(first);	38✔
149	auto scope_second = analysis::Users::scope(second);	38✔
150	// Simplification: If the scopes are different, we conservatively assume the loop body as the
151	// scope
152	if (scope_first != scope_second) {	38✔
NEW 153	scope_first = &loop.root();	×
NEW 154	}	×
155	auto& assumptions = analysis_manager.get<analysis::AssumptionsAnalysis>();	38✔
156	auto scope_assums = assumptions.get(*scope_first);	38✔
157
158	for (auto& subset : first->subsets()) {	77✔
159	// Collect all symbols of the subset;
160	symbolic::SymbolSet first_symbols;	39✔
161	for (auto& dim : subset) {	85✔
162	for (auto& symbol : symbolic::atoms(dim)) {	96✔
163	first_symbols.insert(symbol);	50✔
164	}
165	}
166
167	for (auto& subset_other : second->subsets()) {	80✔
168	// Collect all symbols of the subset;
169	symbolic::SymbolSet second_symbols;	41✔
170	for (auto& dim : subset_other) {	89✔
171	for (auto& symbol : symbolic::atoms(dim)) {	104✔
172	second_symbols.insert(symbol);	56✔
173	}
174	}
175
176	// Collect all symbols of the subsets;
177	symbolic::SymbolSet symbols;	41✔
178	for (auto& symbol : first_symbols) {	97✔
179	symbols.insert(symbol);	56✔
180	}
181	for (auto& symbol : second_symbols) {	97✔
182	symbols.insert(symbol);	56✔
183	}
184
185	// Determine which symbols are readonly -> params
186	symbolic::SymbolSet params;	41✔
187	for (auto& symbol : symbols) {	97✔
188	if (symbol == loop.indvar()) {	56✔
189	continue;	30✔
190	}
191	if (body_users.writes(symbol->get_name()).empty()) {	26✔
192	params.insert(symbol);	17✔
193	}	17✔
194	}
195
196	if (!symbolic::is_disjoint(subset, subset_other, params, {loop.indvar()},	41✔
197	scope_assums)) {
198	return true;	14✔
199	}
200	}	41✔
201	}	39✔
202	return false;	24✔
203	}	38✔
204
205	} // namespace analysis
206	} // namespace sdfg

daisytuner / sdfglib / 15656007340

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