28156217026

Committed 25 Jun 2026 08:09AM UTC coverage: 61.616% (+0.03%) from 61.582%

Build # 28156217026

Build Type

Pull #811

github

Committed by

web-flow

Commit Message

Merge c362b48ab into 0a5f3e8d4

Pull Request Pull Request #811: Add a pass to make loop indvars unique again

Coverage Stats

64 of 72 new or added lines in 2 files covered. (88.89%)

19 existing lines in 1 file now uncovered.

37640 of 61088 relevant lines covered (61.62%)

999.0 hits per line

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

88.57

/sdfg/src/passes/structured_control_flow/unique_loop_indvars.cpp

#include "sdfg/passes/structured_control_flow/unique_loop_indvars.h"

#include <string>
#include <unordered_set>

#include "sdfg/analysis/users.h"
#include "sdfg/structured_control_flow/for.h"
#include "sdfg/structured_control_flow/map.h"
#include "sdfg/structured_control_flow/structured_loop.h"
#include "sdfg/symbolic/symbolic.h"
#include "sdfg/visitor/structured_sdfg_visitor.h"

namespace sdfg {
namespace passes {

namespace {

/**
 * @brief Renames induction variables so that every loop has a unique one.
 *
 * The traversal is a pre-order walk (a loop is visited before its body), so an
 * outer/earlier loop reserves its induction variable name before any nested or
 * later loop is considered.
 */
class UniqueLoopIndvarsVisitor : public visitor::NonStoppingStructuredSDFGVisitor {
private:
    std::unordered_set<std::string> used_indvars_;

    /**
     * @brief Checks whether the loop's induction variable is genuinely read.
     *
     * Uses the Users analysis: starting from the loop's update user (the write
     * to the induction variable performed at the end of each iteration), it looks
     * for read users of the same container that depend on that update and are not
     * the loop-control use of another loop (i.e. an actual data read).
     */
    bool indvar_is_read(structured_control_flow::StructuredLoop& loop, const std::string& name) {
        auto& users = analysis_manager_.get<analysis::Users>();

        auto* update_user = users.get_user(name, &loop, analysis::Use::WRITE, false, false, true);
        if (update_user == nullptr) {
            return false;
        }

        for (auto* user : users.all_uses_after(*update_user)) {
            if (user->use() != analysis::Use::READ || user->container() != name) {
                continue;
            }
            // Skip reads that are the init/condition/update of another loop.
            if (auto* for_user = dynamic_cast<analysis::ForUser*>(user)) {
                if (for_user->element() != &loop) {
                    continue;
                }
            }
            return true;
        }
        return false;
    }

    /**
     * @brief Checks whether the induction variable's value escapes the loop.
     *
     * A genuine (non loop-control) read of the same container that depends on the
     * loop's update user but lies outside the loop subtree consumes the final
     * induction-variable value. Renaming only rewrites uses within the loop, so
     * such an escaping read would be left dangling; in that case the loop must not
     * be renamed.
     */
    bool indvar_escapes(structured_control_flow::StructuredLoop& loop, const std::string& name) {
        auto& users = analysis_manager_.get<analysis::Users>();

        auto* update_user = users.get_user(name, &loop, analysis::Use::WRITE, false, false, true);
        if (update_user == nullptr) {
            return false;
        }

        // Reads of the induction variable that live inside the loop subtree.
        analysis::UsersView loop_view(users, loop);
        auto inner_reads = loop_view.reads(name);
        std::unordered_set<analysis::User*> inner(inner_reads.begin(), inner_reads.end());

        for (auto* user : users.all_uses_after(*update_user)) {
            if (user->use() != analysis::Use::READ || user->container() != name) {
                continue;
            }
            // Loop-control reads (init/condition/update) are not data escapes.
            if (dynamic_cast<analysis::ForUser*>(user) != nullptr) {
                continue;
            }
            // A read still inside the loop is just the body using the variable.
            if (inner.find(user) != inner.end()) {
                continue;
            }
            return true;
        }
        return false;
    }

    bool handle_loop(structured_control_flow::StructuredLoop& loop) {
        const std::string name = loop.indvar()->get_name();

        // First loop to claim this induction variable: just reserve the name.
        if (used_indvars_.insert(name).second) {
            return false;
        }

        // Name already in use by another loop. Only disambiguate if the variable
        // is actually read within this loop; otherwise the clash is harmless.
        if (!indvar_is_read(loop, name)) {
            return false;
        }

        // The induction variable is consumed after the loop: a local rename would
        // break that downstream user, so leave the loop untouched.
        if (indvar_escapes(loop, name)) {
            return false;
        }

        auto& sdfg = builder_.subject();
        std::string new_name = builder_.find_new_name(name + "_");
        builder_.add_container(new_name, sdfg.type(name));

        loop.replace(loop.indvar(), symbolic::symbol(new_name));
        used_indvars_.insert(new_name);

        // The rename rewrote the loop subtree, so user information is now stale.
        analysis_manager_.invalidate_all();
        return true;
    }

public:
    UniqueLoopIndvarsVisitor(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager)
        : visitor::NonStoppingStructuredSDFGVisitor(builder, analysis_manager) {}

    bool accept(structured_control_flow::For& node) override { return handle_loop(node); }

    bool accept(structured_control_flow::Map& node) override { return handle_loop(node); }
};

} // namespace

UniqueLoopIndvars::UniqueLoopIndvars() : Pass() {}

std::string UniqueLoopIndvars::name() { return "UniqueLoopIndvars"; }

bool UniqueLoopIndvars::run_pass(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {
    UniqueLoopIndvarsVisitor visitor(builder, analysis_manager);
    return visitor.visit();
}

} // namespace passes
} // namespace sdfg

1	#include "sdfg/passes/structured_control_flow/unique_loop_indvars.h"
2
3	#include <string>
4	#include <unordered_set>
5
6	#include "sdfg/analysis/users.h"
7	#include "sdfg/structured_control_flow/for.h"
8	#include "sdfg/structured_control_flow/map.h"
9	#include "sdfg/structured_control_flow/structured_loop.h"
10	#include "sdfg/symbolic/symbolic.h"
11	#include "sdfg/visitor/structured_sdfg_visitor.h"
12
13	namespace sdfg {
14	namespace passes {
15
16	namespace {
17
18	/**
19	* @brief Renames induction variables so that every loop has a unique one.
20	*
21	* The traversal is a pre-order walk (a loop is visited before its body), so an
22	* outer/earlier loop reserves its induction variable name before any nested or
23	* later loop is considered.
24	*/
25	class UniqueLoopIndvarsVisitor : public visitor::NonStoppingStructuredSDFGVisitor {
26	private:
27	std::unordered_set<std::string> used_indvars_;
28
29	/**
30	* @brief Checks whether the loop's induction variable is genuinely read.
31	*
32	* Uses the Users analysis: starting from the loop's update user (the write
33	* to the induction variable performed at the end of each iteration), it looks
34	* for read users of the same container that depend on that update and are not
35	* the loop-control use of another loop (i.e. an actual data read).
36	*/
37	bool indvar_is_read(structured_control_flow::StructuredLoop& loop, const std::string& name) {	5✔
38	auto& users = analysis_manager_.get<analysis::Users>();	5✔
39
40	auto* update_user = users.get_user(name, &loop, analysis::Use::WRITE, false, false, true);	5✔
41	if (update_user == nullptr) {	5✔
NEW 42	return false;	×
NEW 43	}	×
44
45	for (auto* user : users.all_uses_after(*update_user)) {	11✔
46	if (user->use() != analysis::Use::READ \|\| user->container() != name) {	11✔
47	continue;	4✔
48	}	4✔
49	// Skip reads that are the init/condition/update of another loop.
50	if (auto* for_user = dynamic_cast<analysis::ForUser*>(user)) {	7✔
51	if (for_user->element() != &loop) {	7✔
52	continue;	2✔
53	}	2✔
54	}	7✔
55	return true;	5✔
56	}	7✔
NEW 57	return false;	×
58	}	5✔
59
60	/**
61	* @brief Checks whether the induction variable's value escapes the loop.
62	*
63	* A genuine (non loop-control) read of the same container that depends on the
64	* loop's update user but lies outside the loop subtree consumes the final
65	* induction-variable value. Renaming only rewrites uses within the loop, so
66	* such an escaping read would be left dangling; in that case the loop must not
67	* be renamed.
68	*/
69	bool indvar_escapes(structured_control_flow::StructuredLoop& loop, const std::string& name) {	5✔
70	auto& users = analysis_manager_.get<analysis::Users>();	5✔
71
72	auto* update_user = users.get_user(name, &loop, analysis::Use::WRITE, false, false, true);	5✔
73	if (update_user == nullptr) {	5✔
NEW 74	return false;	×
NEW 75	}	×
76
77	// Reads of the induction variable that live inside the loop subtree.
78	analysis::UsersView loop_view(users, loop);	5✔
79	auto inner_reads = loop_view.reads(name);	5✔
80	std::unordered_set<analysis::User*> inner(inner_reads.begin(), inner_reads.end());	5✔
81
82	for (auto* user : users.all_uses_after(*update_user)) {	33✔
83	if (user->use() != analysis::Use::READ \|\| user->container() != name) {	33✔
84	continue;	13✔
85	}	13✔
86	// Loop-control reads (init/condition/update) are not data escapes.
87	if (dynamic_cast<analysis::ForUser*>(user) != nullptr) {	20✔
88	continue;	15✔
89	}	15✔
90	// A read still inside the loop is just the body using the variable.
91	if (inner.find(user) != inner.end()) {	5✔
92	continue;	4✔
93	}	4✔
94	return true;	1✔
95	}	5✔
96	return false;	4✔
97	}	5✔
98
99	bool handle_loop(structured_control_flow::StructuredLoop& loop) {	14✔
100	const std::string name = loop.indvar()->get_name();	14✔
101
102	// First loop to claim this induction variable: just reserve the name.
103	if (used_indvars_.insert(name).second) {	14✔
104	return false;	9✔
105	}	9✔
106
107	// Name already in use by another loop. Only disambiguate if the variable
108	// is actually read within this loop; otherwise the clash is harmless.
109	if (!indvar_is_read(loop, name)) {	5✔
NEW 110	return false;	×
NEW 111	}	×
112
113	// The induction variable is consumed after the loop: a local rename would
114	// break that downstream user, so leave the loop untouched.
115	if (indvar_escapes(loop, name)) {	5✔
116	return false;	1✔
117	}	1✔
118
119	auto& sdfg = builder_.subject();	4✔
120	std::string new_name = builder_.find_new_name(name + "_");	4✔
121	builder_.add_container(new_name, sdfg.type(name));	4✔
122
123	loop.replace(loop.indvar(), symbolic::symbol(new_name));	4✔
124	used_indvars_.insert(new_name);	4✔
125
126	// The rename rewrote the loop subtree, so user information is now stale.
127	analysis_manager_.invalidate_all();	4✔
128	return true;	4✔
129	}	5✔
130
131	public:
132	UniqueLoopIndvarsVisitor(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager)
133	: visitor::NonStoppingStructuredSDFGVisitor(builder, analysis_manager) {}	7✔
134
135	bool accept(structured_control_flow::For& node) override { return handle_loop(node); }	12✔
136
137	bool accept(structured_control_flow::Map& node) override { return handle_loop(node); }	2✔
138	};
139
140	} // namespace
141
142	UniqueLoopIndvars::UniqueLoopIndvars() : Pass() {}	6✔
143
NEW 144	std::string UniqueLoopIndvars::name() { return "UniqueLoopIndvars"; }	×
145
146	bool UniqueLoopIndvars::run_pass(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	7✔
147	UniqueLoopIndvarsVisitor visitor(builder, analysis_manager);	7✔
148	return visitor.visit();	7✔
149	}	7✔
150
151	} // namespace passes
152	} // namespace sdfg

daisytuner / docc / 28156217026

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