20388902294

Committed 18 Dec 2025 07:41PM UTC coverage: 39.328% (-0.1%) from 39.454%

Build # 20388902294

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #400 from daisytuner/backward-symbol-propagation

adds backward symbol propagation

Run Details

13427 of 44322 branches covered (30.29%)

Branch coverage included in aggregate %.

113 of 250 new or added lines in 4 files covered. (45.2%)

13 existing lines in 3 files now uncovered.

11565 of 19225 relevant lines covered (60.16%)

83.99 hits per line

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

37.43

/src/passes/structured_control_flow/for2map.cpp

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

#include "sdfg/analysis/assumptions_analysis.h"
#include "sdfg/analysis/loop_analysis.h"
#include "sdfg/analysis/scope_analysis.h"
#include "sdfg/analysis/users.h"
#include "sdfg/passes/pipeline.h"

namespace sdfg {
namespace passes {

std::string For2MapPass::name() { return "For2Map"; }

bool For2MapPass::can_be_applied(
    builder::StructuredSDFGBuilder& builder,
    analysis::AnalysisManager& analysis_manager,
    structured_control_flow::For& for_stmt
) {
    auto& assumptions_analysis = analysis_manager.get<analysis::AssumptionsAnalysis>();
    bool is_monotonic = analysis::LoopAnalysis::is_monotonic(&for_stmt, assumptions_analysis);
    if (!is_monotonic) {
        return false;
    }

    // Criterion: Loop must not have side-effecting body
    std::list<const structured_control_flow::ControlFlowNode*> queue = {&for_stmt.root()};
    while (!queue.empty()) {
        auto current = queue.front();
        queue.pop_front();

        if (auto block = dynamic_cast<const structured_control_flow::Block*>(current)) {
            for (auto& node : block->dataflow().nodes()) {
                if (auto library_node = dynamic_cast<const data_flow::LibraryNode*>(&node)) {
                    if (library_node->side_effect()) {
                        return false;
                    }
                }
            }
        } else if (auto seq = dynamic_cast<const 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<const 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 = dynamic_cast<const structured_control_flow::StructuredLoop*>(current)) {
            queue.push_back(&loop->root());
        } else if (auto while_stmt = dynamic_cast<const structured_control_flow::While*>(current)) {
            queue.push_back(&while_stmt->root());
        } else if (auto for_stmt = dynamic_cast<const structured_control_flow::Break*>(current)) {
            // Do nothing
        } else if (auto for_stmt = dynamic_cast<const structured_control_flow::Continue*>(current)) {
            // Do nothing
        } else if (auto for_stmt = dynamic_cast<const structured_control_flow::Return*>(current)) {
            return false;
        } else {
            throw InvalidSDFGException("Unknown control flow node type in For2Map pass.");
        }
    }

    // Criterion: loop must be data-parallel w.r.t containers
    auto dependencies = data_dependency_analysis_->dependencies(for_stmt);

    // a. No true dependencies (RAW) between iterations
    for (auto& dep : dependencies) {
        if (dep.second == analysis::LoopCarriedDependency::LOOP_CARRIED_DEPENDENCY_READ_WRITE) {
            return false;
        }
    }

    // b. False dependencies (WAW) are limited to loop-local variables
    auto& users = analysis_manager.get<analysis::Users>();
    analysis::UsersView body_users(users, for_stmt.root());
    auto locals = users.locals(for_stmt.root());
    for (auto& dep : dependencies) {
        auto& container = dep.first;
        auto& type = builder.subject().type(container);

        // Must be loop-local variable
        if (locals.find(container) == locals.end()) {
            // Special case: Constant scalar assignments
            if (type.type_id() == types::TypeID::Scalar) {
                auto writes = body_users.writes(container);
                auto reads = body_users.reads(container);
                if (writes.size() == 1 && reads.empty()) {
                    auto write = writes.front();
                    if (auto write_transition =
                            dynamic_cast<const structured_control_flow::Transition*>(write->element())) {
                        auto lhs = symbolic::symbol(container);
                        auto rhs = write_transition->assignments().at(lhs);
                        if (SymEngine::is_a<SymEngine::Integer>(*rhs)) {
                            continue;
                        }
                    }
                }
            }

            return false;
        }

        // Check for pointers that they point to loop-local storage
        if (type.type_id() != types::TypeID::Pointer) {
            continue;
        }
        if (type.storage_type().allocation() == types::StorageType::AllocationType::Managed) {
            continue;
        }

        // or alias of loop-local storage
        if (users.moves(container).size() != 1) {
            return false;
        }
        auto move = users.moves(container).front();
        auto move_node = static_cast<const data_flow::AccessNode*>(move->element());
        auto& move_graph = move_node->get_parent();
        auto& move_edge = *move_graph.in_edges(*move_node).begin();
        auto& move_src = static_cast<const data_flow::AccessNode&>(move_edge.src());
        if (locals.find(move_src.data()) == locals.end()) {
            return false;
        }
        auto& move_type = builder.subject().type(move_src.data());
        if (move_type.storage_type().allocation() == types::StorageType::AllocationType::Unmanaged) {
            return false;
        }
    }

    // c. indvar not used after for
    if (locals.find(for_stmt.indvar()->get_name()) != locals.end()) {
        return false;
    }

    return true;
}

bool For2MapPass::run_pass(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {
    this->data_dependency_analysis_ = std::make_unique<analysis::DataDependencyAnalysis>(builder.subject(), true);
    this->data_dependency_analysis_->run(analysis_manager);

    auto& loop_analysis = analysis_manager.get<analysis::LoopAnalysis>();
    auto& loop_tree = loop_analysis.loop_tree();

    // Traverse loops in bottom-up fashion (reverse loop)
    std::list<structured_control_flow::For*> for_queue;
    for (auto& entry : loop_tree) {
        if (auto for_stmt = dynamic_cast<structured_control_flow::For*>(entry.first)) {
            for_queue.push_front(for_stmt);
        }
    }

    // Mark for loops that can be converted
    std::list<structured_control_flow::For*> map_queue;
    for (auto& for_loop : for_queue) {
        if (this->can_be_applied(builder, analysis_manager, *for_loop)) {
            map_queue.push_back(for_loop);
        }
    }

    // Convert marked for loops
    bool applied = false;
    auto& scope_analysis = analysis_manager.get<analysis::ScopeAnalysis>();
    for (auto& for_stmt : map_queue) {
        auto parent = static_cast<structured_control_flow::Sequence*>(scope_analysis.parent_scope(for_stmt));
        builder.convert_for(*parent, *for_stmt);
        applied = true;
    }

    return applied;
}

} // namespace passes
} // namespace sdfg

1	#include "sdfg/passes/structured_control_flow/for2map.h"
2
3	#include "sdfg/analysis/assumptions_analysis.h"
4	#include "sdfg/analysis/loop_analysis.h"
5	#include "sdfg/analysis/scope_analysis.h"
6	#include "sdfg/analysis/users.h"
7	#include "sdfg/passes/pipeline.h"
8
9	namespace sdfg {
10	namespace passes {
11
12	std::string For2MapPass::name() { return "For2Map"; }	×
13
14	bool For2MapPass::can_be_applied(	9✔
15	builder::StructuredSDFGBuilder& builder,
16	analysis::AnalysisManager& analysis_manager,
17	structured_control_flow::For& for_stmt
18	) {
19	auto& assumptions_analysis = analysis_manager.get<analysis::AssumptionsAnalysis>();	9✔
20	bool is_monotonic = analysis::LoopAnalysis::is_monotonic(&for_stmt, assumptions_analysis);	9✔
21	if (!is_monotonic) {	9!
22	return false;	×
23	}
24
25	// Criterion: Loop must not have side-effecting body
26	std::list<const structured_control_flow::ControlFlowNode*> queue = {&for_stmt.root()};	9!
27	while (!queue.empty()) {	30✔
28	auto current = queue.front();	21✔
29	queue.pop_front();	21✔
30
31	if (auto block = dynamic_cast<const structured_control_flow::Block*>(current)) {	21!
32	for (auto& node : block->dataflow().nodes()) {	41!
33	if (auto library_node = dynamic_cast<const data_flow::LibraryNode*>(&node)) {	31!
34	if (library_node->side_effect()) {	×
35	return false;	×
36	}
37	}	×
38	}
39	} else if (auto seq = dynamic_cast<const structured_control_flow::Sequence*>(current)) {	21!
40	for (size_t i = 0; i < seq->size(); i++) {	21!
41	auto& child = seq->at(i).first;	11!
42	queue.push_back(&child);	11!
43	}	11✔
44	} else if (auto ifelse = dynamic_cast<const structured_control_flow::IfElse*>(current)) {	11!
45	for (size_t i = 0; i < ifelse->size(); i++) {	×
46	auto& branch = ifelse->at(i).first;	×
47	queue.push_back(&branch);	×
48	}	×
49	} else if (auto loop = dynamic_cast<const structured_control_flow::StructuredLoop*>(current)) {	1!
50	queue.push_back(&loop->root());	1!
51	} else if (auto while_stmt = dynamic_cast<const structured_control_flow::While*>(current)) {	1!
52	queue.push_back(&while_stmt->root());	×
53	} else if (auto for_stmt = dynamic_cast<const structured_control_flow::Break*>(current)) {	×
54	// Do nothing
55	} else if (auto for_stmt = dynamic_cast<const structured_control_flow::Continue*>(current)) {	×
56	// Do nothing
57	} else if (auto for_stmt = dynamic_cast<const structured_control_flow::Return*>(current)) {	×
58	return false;	×
59	} else {
60	throw InvalidSDFGException("Unknown control flow node type in For2Map pass.");	×
61	}
62	}
63
64	// Criterion: loop must be data-parallel w.r.t containers
65	auto dependencies = data_dependency_analysis_->dependencies(for_stmt);	9!
66
67	// a. No true dependencies (RAW) between iterations
68	for (auto& dep : dependencies) {	10✔
69	if (dep.second == analysis::LoopCarriedDependency::LOOP_CARRIED_DEPENDENCY_READ_WRITE) {	1!
70	return false;	×
71	}
72	}
73
74	// b. False dependencies (WAW) are limited to loop-local variables
75	auto& users = analysis_manager.get<analysis::Users>();	9!
76	analysis::UsersView body_users(users, for_stmt.root());	9!
77	auto locals = users.locals(for_stmt.root());	9!
78	for (auto& dep : dependencies) {	10✔
79	auto& container = dep.first;	1✔
80	auto& type = builder.subject().type(container);	1!
81
82	// Must be loop-local variable
83	if (locals.find(container) == locals.end()) {	1!
84	// Special case: Constant scalar assignments
NEW 85	if (type.type_id() == types::TypeID::Scalar) {	×
NEW 86	auto writes = body_users.writes(container);	×
NEW 87	auto reads = body_users.reads(container);	×
NEW 88	if (writes.size() == 1 && reads.empty()) {	×
NEW 89	auto write = writes.front();	×
NEW 90	if (auto write_transition =	×
NEW 91	dynamic_cast<const structured_control_flow::Transition*>(write->element())) {	×
NEW 92	auto lhs = symbolic::symbol(container);	×
NEW 93	auto rhs = write_transition->assignments().at(lhs);	×
NEW 94	if (SymEngine::is_a<SymEngine::Integer>(*rhs)) {	×
NEW 95	continue;	×
96	}
NEW 97	}	×
NEW 98	}	×
NEW 99	}	×
100
UNCOV 101	return false;	×
102	}
103
104	// Check for pointers that they point to loop-local storage
105	if (type.type_id() != types::TypeID::Pointer) {	1!
106	continue;	1✔
107	}
108	if (type.storage_type().allocation() == types::StorageType::AllocationType::Managed) {	×
109	continue;	×
110	}
111
112	// or alias of loop-local storage
113	if (users.moves(container).size() != 1) {	×
114	return false;	×
115	}
116	auto move = users.moves(container).front();	×
117	auto move_node = static_cast<const data_flow::AccessNode*>(move->element());	×
118	auto& move_graph = move_node->get_parent();	×
119	auto& move_edge = move_graph.in_edges(move_node).begin();	×
120	auto& move_src = static_cast<const data_flow::AccessNode&>(move_edge.src());	×
121	if (locals.find(move_src.data()) == locals.end()) {	×
122	return false;	×
123	}
124	auto& move_type = builder.subject().type(move_src.data());	×
125	if (move_type.storage_type().allocation() == types::StorageType::AllocationType::Unmanaged) {	×
126	return false;	×
127	}
128	}
129
130	// c. indvar not used after for
131	if (locals.find(for_stmt.indvar()->get_name()) != locals.end()) {	9!
132	return false;	×
133	}
134
135	return true;	9✔
136	}	9✔
137
138	bool For2MapPass::run_pass(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	8✔
139	this->data_dependency_analysis_ = std::make_unique<analysis::DataDependencyAnalysis>(builder.subject(), true);	8✔
140	this->data_dependency_analysis_->run(analysis_manager);	8✔
141
142	auto& loop_analysis = analysis_manager.get<analysis::LoopAnalysis>();	8✔
143	auto& loop_tree = loop_analysis.loop_tree();	8✔
144
145	// Traverse loops in bottom-up fashion (reverse loop)
146	std::list<structured_control_flow::For*> for_queue;	8✔
147	for (auto& entry : loop_tree) {	17✔
148	if (auto for_stmt = dynamic_cast<structured_control_flow::For*>(entry.first)) {	9!
149	for_queue.push_front(for_stmt);	9!
150	}	9✔
151	}
152
153	// Mark for loops that can be converted
154	std::list<structured_control_flow::For*> map_queue;	8✔
155	for (auto& for_loop : for_queue) {	17✔
156	if (this->can_be_applied(builder, analysis_manager, *for_loop)) {	9!
157	map_queue.push_back(for_loop);	9!
158	}	9✔
159	}
160
161	// Convert marked for loops
162	bool applied = false;	8✔
163	auto& scope_analysis = analysis_manager.get<analysis::ScopeAnalysis>();	8!
164	for (auto& for_stmt : map_queue) {	17✔
165	auto parent = static_cast<structured_control_flow::Sequence*>(scope_analysis.parent_scope(for_stmt));	9!
166	builder.convert_for(parent, for_stmt);	9!
167	applied = true;	9✔
168	}
169
170	return applied;	8✔
171	}	8✔
172
173	} // namespace passes
174	} // namespace sdfg

daisytuner / sdfglib / 20388902294

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