15682840168

Committed 16 Jun 2025 01:56PM UTC coverage: 64.969% (+0.08%) from 64.887%

Build # 15682840168

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #82 from daisytuner/assumptions2

parametrize extreme value analysis

Run Details

147 of 165 new or added lines in 8 files covered. (89.09%)

7 existing lines in 2 files now uncovered.

8062 of 12409 relevant lines covered (64.97%)

119.02 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"

#include "sdfg/analysis/assumptions_analysis.h"
#include "sdfg/analysis/data_parallelism_analysis.h"
#include "sdfg/analysis/loop_analysis.h"
#include "sdfg/analysis/users.h"
#include "sdfg/symbolic/series.h"

namespace sdfg {
namespace passes {

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

    bool applied = false;

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

    auto& loop_analysis = analysis_manager.get<analysis::LoopAnalysis>();
    auto& assumptions_analysis = analysis_manager.get<analysis::AssumptionsAnalysis>();
    auto assumptions = assumptions_analysis.get(loop.root(), true);

    // Assume simple loops: i = 0; i < N; i++
    if (!SymEngine::eq(*init, *symbolic::integer(0))) {
        return false;
    }
    if (!loop_analysis.is_contiguous(&loop)) {
        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;
        if (!symbolic::is_contiguous(assign, sym, assumptions)) {
            continue;
        }
        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 sloop_stmt =
                       dynamic_cast<structured_control_flow::StructuredLoop*>(current)) {
            queue.push_back(&sloop_stmt->root());
        }
    }

    return applied;
};

}  // namespace passes
}  // namespace sdfg

1	#include "sdfg/passes/structured_control_flow/loop_dependent_symbol_elimination.h"
2
3	#include "sdfg/analysis/assumptions_analysis.h"
4	#include "sdfg/analysis/data_parallelism_analysis.h"
5	#include "sdfg/analysis/loop_analysis.h"
6	#include "sdfg/analysis/users.h"
7	#include "sdfg/symbolic/series.h"
8
9	namespace sdfg {
10	namespace passes {
11
12	bool LoopDependentSymbolElimination::eliminate_symbols(	×
13	builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager,
14	structured_control_flow::StructuredLoop& loop,
15	structured_control_flow::Transition& transition) {
16	if (loop.root().size() == 0) {	×
17	return false;	×
18	}
19
20	bool applied = false;	×
21
22	auto indvar = loop.indvar();	×
23	auto update = loop.update();	×
24	auto init = loop.init();	×
25	auto condition = loop.condition();	×
26
27	auto& loop_analysis = analysis_manager.get<analysis::LoopAnalysis>();	×
28	auto& assumptions_analysis = analysis_manager.get<analysis::AssumptionsAnalysis>();	×
NEW 29	auto assumptions = assumptions_analysis.get(loop.root(), true);	×
30
31	// Assume simple loops: i = 0; i < N; i++
32	if (!SymEngine::eq(init, symbolic::integer(0))) {	×
33	return false;	×
34	}
35	if (!loop_analysis.is_contiguous(&loop)) {	×
36	return false;	×
37	}
38	auto bound = analysis::DataParallelismAnalysis::bound(loop);	×
39	if (bound == SymEngine::null \|\| !SymEngine::is_a<SymEngine::StrictLessThan>(*condition)) {	×
40	return false;	×
41	}
42	for (auto atom : symbolic::atoms(bound)) {	×
43	auto sym = SymEngine::rcp_static_cast<const SymEngine::Symbol>(atom);	×
44	if (transition.assignments().find(sym) != transition.assignments().end()) {	×
45	return false;	×
46	}
47	}	×
48
49	// Find all symbolic upates
50	auto& last_transition = loop.root().at(loop.root().size() - 1).second;	×
51	auto& last_assignments = last_transition.assignments();	×
52	std::unordered_set<std::string> loop_dependent_symbols;	×
53	for (auto& entry : last_assignments) {	×
54	auto& sym = entry.first;	×
55	auto& assign = entry.second;	×
56	if (!symbolic::is_contiguous(assign, sym, assumptions)) {	×
57	continue;	×
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);	×
119	}	×
120	}	×
121	for (size_t i = 0; i < sequence_stmt->size(); i++) {	×
122	queue.push_back(&sequence_stmt->at(i).first);	×
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);	×
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 sloop_stmt =	×
131	dynamic_cast<structured_control_flow::StructuredLoop*>(current)) {	×
132	queue.push_back(&sloop_stmt->root());	×
133	}	×
134	}
135
136	return applied;	×
137	};	×
138
139	} // namespace passes
140	} // namespace sdfg

daisytuner / sdfglib / 15682840168

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