15044057891

Committed 15 May 2025 11:42AM UTC coverage: 59.37% (+1.8%) from 57.525%

Build # 15044057891

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #14 from daisytuner/sanitizers

enables sanitizer on unit tests

Run Details

63 of 67 new or added lines in 47 files covered. (94.03%)

570 existing lines in 62 files now uncovered.

7356 of 12390 relevant lines covered (59.37%)

505.93 hits per line

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

0.0

/src/passes/structured_control_flow/loop_dependent_symbol_elimination.cpp

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

namespace sdfg {
namespace passes {

bool LoopDependentSymbolElimination::eliminate_symbols(
    builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager,
    structured_control_flow::For& loop, structured_control_flow::Transition& transition) {
    if (loop.root().size() == 0) {
        return false;
    }

    auto& sdfg = builder.subject();
    bool applied = false;

    auto indvar = loop.indvar();
    auto update = loop.update();
    auto init = loop.init();
    auto condition = loop.condition();

    // Assume simple loops: i = 0; i < N; i++
    if (!SymEngine::eq(*init, *symbolic::integer(0))) {
        return false;
    }
    auto match = symbolic::affine(update, indvar);
    if (match.first == SymEngine::null) {
        return false;
    }
    if (!SymEngine::eq(*match.first, *symbolic::integer(1)) ||
        !SymEngine::eq(*match.second, *symbolic::integer(1))) {
        return false;
    }
    auto bound = analysis::DataParallelismAnalysis::bound(loop);
    if (bound == SymEngine::null || !SymEngine::is_a<SymEngine::StrictLessThan>(*condition)) {
        return false;
    }
    for (auto atom : symbolic::atoms(bound)) {
        auto sym = SymEngine::rcp_static_cast<const SymEngine::Symbol>(atom);
        if (transition.assignments().find(sym) != transition.assignments().end()) {
            return false;
        }
    }

    // Find all symbolic upates
    auto& last_transition = loop.root().at(loop.root().size() - 1).second;
    auto& last_assignments = last_transition.assignments();
    std::unordered_set<std::string> loop_dependent_symbols;
    for (auto& entry : last_assignments) {
        auto& sym = entry.first;
        auto& assign = entry.second;
        auto sym_match = symbolic::affine(assign, sym);
        if (sym_match.first == SymEngine::null) {
            continue;
        }
        if (!SymEngine::eq(*sym_match.first, *symbolic::integer(1)) ||
            !SymEngine::eq(*sym_match.second, *symbolic::integer(1))) {
            return false;
        }
        loop_dependent_symbols.insert(sym->get_name());
    }
    if (loop_dependent_symbols.empty()) {
        return false;
    }

    auto& all_users = analysis_manager.get<analysis::Users>();
    analysis::UsersView users(all_users, loop.root());
    for (auto& cand : loop_dependent_symbols) {
        auto writes = users.writes(cand);
        if (writes.size() != 1) {
            continue;
        }
        auto reads = users.reads(cand);
        bool has_dataflow = false;
        for (auto& read : reads) {
            if (dynamic_cast<data_flow::AccessNode*>(read->element())) {
                has_dataflow = true;
                break;
            }
        }
        if (has_dataflow) {
            continue;
        }
        auto sym = symbolic::symbol(cand);
        last_assignments.erase(sym);
        loop.root().replace(sym, symbolic::add(indvar, sym));

        transition.assignments().insert({sym, symbolic::add(sym, bound)});

        applied = true;
    }

    return applied;
};

LoopDependentSymbolElimination::LoopDependentSymbolElimination()
    : Pass(){

      };

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

bool LoopDependentSymbolElimination::run_pass(builder::StructuredSDFGBuilder& builder,
                                              analysis::AnalysisManager& analysis_manager) {
    bool applied = false;

    // Traverse structured SDFG
    std::list<structured_control_flow::ControlFlowNode*> queue = {&builder.subject().root()};
    while (!queue.empty()) {
        auto current = queue.front();
        queue.pop_front();

        // Add children to queue
        if (auto sequence_stmt = dynamic_cast<structured_control_flow::Sequence*>(current)) {
            for (size_t i = 0; i < sequence_stmt->size(); i++) {
                auto child = sequence_stmt->at(i);
                if (auto match = dynamic_cast<structured_control_flow::For*>(&child.first)) {
                    applied |=
                        this->eliminate_symbols(builder, analysis_manager, *match, child.second);
                }
            }
            for (size_t i = 0; i < sequence_stmt->size(); i++) {
                queue.push_back(&sequence_stmt->at(i).first);
            }
        } else if (auto if_else_stmt = dynamic_cast<structured_control_flow::IfElse*>(current)) {
            for (size_t i = 0; i < if_else_stmt->size(); i++) {
                queue.push_back(&if_else_stmt->at(i).first);
            }
        } else if (auto loop_stmt = dynamic_cast<structured_control_flow::While*>(current)) {
            queue.push_back(&loop_stmt->root());
        } else if (auto for_stmt = dynamic_cast<structured_control_flow::For*>(current)) {
            queue.push_back(&for_stmt->root());
        } else if (auto kern_stmt = dynamic_cast<const structured_control_flow::Kernel*>(current)) {
            queue.push_back(&kern_stmt->root());
        }
    }

    return applied;
};

}  // namespace passes
}  // namespace sdfg

1	#include "sdfg/passes/structured_control_flow/loop_dependent_symbol_elimination.h"
2
3	namespace sdfg {
4	namespace passes {
5
6	bool LoopDependentSymbolElimination::eliminate_symbols(	×
7	builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager,
8	structured_control_flow::For& loop, structured_control_flow::Transition& transition) {
9	if (loop.root().size() == 0) {	×
10	return false;	×
11	}
12
13	auto& sdfg = builder.subject();	×
14	bool applied = false;	×
15
16	auto indvar = loop.indvar();	×
17	auto update = loop.update();	×
18	auto init = loop.init();	×
19	auto condition = loop.condition();	×
20
21	// Assume simple loops: i = 0; i < N; i++
22	if (!SymEngine::eq(init, symbolic::integer(0))) {	×
23	return false;	×
24	}
25	auto match = symbolic::affine(update, indvar);	×
26	if (match.first == SymEngine::null) {	×
27	return false;	×
28	}
29	if (!SymEngine::eq(match.first, symbolic::integer(1)) \|\|	×
30	!SymEngine::eq(match.second, symbolic::integer(1))) {	×
31	return false;	×
32	}
33	auto bound = analysis::DataParallelismAnalysis::bound(loop);	×
34	if (bound == SymEngine::null \|\| !SymEngine::is_a<SymEngine::StrictLessThan>(*condition)) {	×
35	return false;	×
36	}
37	for (auto atom : symbolic::atoms(bound)) {	×
38	auto sym = SymEngine::rcp_static_cast<const SymEngine::Symbol>(atom);	×
39	if (transition.assignments().find(sym) != transition.assignments().end()) {	×
40	return false;	×
41	}
42	}	×
43
44	// Find all symbolic upates
45	auto& last_transition = loop.root().at(loop.root().size() - 1).second;	×
46	auto& last_assignments = last_transition.assignments();	×
47	std::unordered_set<std::string> loop_dependent_symbols;	×
48	for (auto& entry : last_assignments) {	×
49	auto& sym = entry.first;	×
50	auto& assign = entry.second;	×
51	auto sym_match = symbolic::affine(assign, sym);	×
52	if (sym_match.first == SymEngine::null) {	×
53	continue;	×
54	}
55	if (!SymEngine::eq(sym_match.first, symbolic::integer(1)) \|\|	×
56	!SymEngine::eq(sym_match.second, symbolic::integer(1))) {	×
57	return false;	×
58	}
59	loop_dependent_symbols.insert(sym->get_name());	×
60	}	×
61	if (loop_dependent_symbols.empty()) {	×
62	return false;	×
63	}
64
65	auto& all_users = analysis_manager.get<analysis::Users>();	×
66	analysis::UsersView users(all_users, loop.root());	×
67	for (auto& cand : loop_dependent_symbols) {	×
68	auto writes = users.writes(cand);	×
69	if (writes.size() != 1) {	×
70	continue;	×
71	}
72	auto reads = users.reads(cand);	×
73	bool has_dataflow = false;	×
74	for (auto& read : reads) {	×
75	if (dynamic_cast<data_flow::AccessNode*>(read->element())) {	×
76	has_dataflow = true;	×
77	break;	×
78	}
79	}
80	if (has_dataflow) {	×
81	continue;	×
82	}
83	auto sym = symbolic::symbol(cand);	×
84	last_assignments.erase(sym);	×
85	loop.root().replace(sym, symbolic::add(indvar, sym));	×
86
87	transition.assignments().insert({sym, symbolic::add(sym, bound)});	×
88
89	applied = true;	×
90	}	×
91
92	return applied;	×
93	};	×
94
95	LoopDependentSymbolElimination::LoopDependentSymbolElimination()	×
96	: Pass(){	×
97
98	};	×
99
100	std::string LoopDependentSymbolElimination::name() { return "LoopDependentSymbolElimination"; };	×
101
102	bool LoopDependentSymbolElimination::run_pass(builder::StructuredSDFGBuilder& builder,	×
103	analysis::AnalysisManager& analysis_manager) {
104	bool applied = false;	×
105
106	// Traverse structured SDFG
107	std::list<structured_control_flow::ControlFlowNode*> queue = {&builder.subject().root()};	×
108	while (!queue.empty()) {	×
109	auto current = queue.front();	×
110	queue.pop_front();	×
111
112	// Add children to queue
113	if (auto sequence_stmt = dynamic_cast<structured_control_flow::Sequence*>(current)) {	×
114	for (size_t i = 0; i < sequence_stmt->size(); i++) {	×
115	auto child = sequence_stmt->at(i);	×
116	if (auto match = dynamic_cast<structured_control_flow::For*>(&child.first)) {	×
117	applied \|=	×
118	this->eliminate_symbols(builder, analysis_manager, *match, child.second);	×
UNCOV 119	}	×
UNCOV 120	}	×
121	for (size_t i = 0; i < sequence_stmt->size(); i++) {	×
122	queue.push_back(&sequence_stmt->at(i).first);	×
UNCOV 123	}	×
124	} else if (auto if_else_stmt = dynamic_cast<structured_control_flow::IfElse*>(current)) {	×
125	for (size_t i = 0; i < if_else_stmt->size(); i++) {	×
126	queue.push_back(&if_else_stmt->at(i).first);	×
UNCOV 127	}	×
128	} else if (auto loop_stmt = dynamic_cast<structured_control_flow::While*>(current)) {	×
129	queue.push_back(&loop_stmt->root());	×
130	} else if (auto for_stmt = dynamic_cast<structured_control_flow::For*>(current)) {	×
131	queue.push_back(&for_stmt->root());	×
132	} else if (auto kern_stmt = dynamic_cast<const structured_control_flow::Kernel*>(current)) {	×
133	queue.push_back(&kern_stmt->root());	×
UNCOV 134	}	×
135	}
136
137	return applied;	×
138	};	×
139
140	} // namespace passes
141	} // namespace sdfg

daisytuner / sdfglib / 15044057891

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