15340968114

Committed 30 May 2025 06:47AM UTC coverage: 58.553% (+0.2%) from 58.324%

Build # 15340968114

Build Type

push

github

Committed by

web-flow

Commit Message

Add parallel Map node

* Introduce Map data structure

* Prepare infrastructure

* implement analysis support

* Add basic infrastructure

* visualizer/serializer

* include fix

* update from main

* remove default

* happens before test + fixes

* builder test

* dispatcher test

* visitor, copy and serializer tests

* for2map structures

* for2map conversion draft

* add tests

* Bug fixes

* small updates from feedback

* Visitor style pass implementation

* cleanup

* fixes linting errors

---------

Co-authored-by: Lukas Truemper <lukas.truemper@outlook.de>

Run Details

258 of 381 new or added lines in 26 files covered. (67.72%)

17 existing lines in 14 files now uncovered.

8184 of 13977 relevant lines covered (58.55%)

109.83 hits per line

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

0.0

/src/passes/structured_control_flow/loop_bound_normalization.cpp

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

namespace sdfg {
namespace passes {

bool LoopBoundNormalization::apply(builder::StructuredSDFGBuilder& builder,
                                   structured_control_flow::For& loop) {
    auto indvar = loop.indvar();
    auto condition = loop.condition();
    auto update = loop.update();

    // Condition must be of form indvar != bound
    if (!SymEngine::is_a<SymEngine::Unequality>(*condition)) {
        return false;
    }
    auto eq = SymEngine::rcp_static_cast<const SymEngine::Unequality>(condition);
    auto eq_args = eq->get_args();
    auto bound = eq_args.at(0);
    auto symbol = eq_args.at(1);
    if (symbolic::uses(symbol, indvar) && symbolic::uses(bound, indvar)) {
        return false;
    } else if (symbolic::uses(bound, indvar)) {
        bound = eq_args.at(1);
        symbol = eq_args.at(0);
    }
    if (symbolic::strict_monotonicity(symbol, indvar) != symbolic::Sign::POSITIVE) {
        return false;
    }

    // Check if monotonic update
    // TODO: Support more complex updates
    auto match = symbolic::affine(update, indvar);
    if (match.first == SymEngine::null) {
        return false;
    }
    auto first_term = match.first;
    auto second_term = match.second;
    if (!SymEngine::is_a<SymEngine::Integer>(*first_term) ||
        !SymEngine::is_a<SymEngine::Integer>(*second_term)) {
        return false;
    }
    auto multiplier = SymEngine::rcp_static_cast<const SymEngine::Integer>(first_term);
    auto offset = SymEngine::rcp_static_cast<const SymEngine::Integer>(second_term);
    if (multiplier->as_int() >= 1 && offset->as_int() >= 0) {
        auto new_bound = symbolic::Lt(symbol, bound);
        loop.condition() = new_bound;
        return true;
    } else if (multiplier->as_int() <= 1 && offset->as_int() < 0) {
        auto new_bound = symbolic::Gt(symbol, bound);
        loop.condition() = new_bound;
        return true;
    } else {
        return false;
    }

    return true;
};

LoopBoundNormalization::LoopBoundNormalization()
    : Pass() {

      };

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

bool LoopBoundNormalization::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();

        // If sequence, attempt promotion
        if (auto match = dynamic_cast<structured_control_flow::For*>(current)) {
            applied |= this->apply(builder, *match);
        }

        // 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++) {
                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());
        } else if (auto map_stmt = dynamic_cast<const structured_control_flow::Map*>(current)) {
            queue.push_back(&map_stmt->root());
        }
    }

    return applied;
};

}  // namespace passes
}  // namespace sdfg

1	#include "sdfg/passes/structured_control_flow/loop_bound_normalization.h"
2
3	namespace sdfg {
4	namespace passes {
5
6	bool LoopBoundNormalization::apply(builder::StructuredSDFGBuilder& builder,	×
7	structured_control_flow::For& loop) {
8	auto indvar = loop.indvar();	×
9	auto condition = loop.condition();	×
10	auto update = loop.update();	×
11
12	// Condition must be of form indvar != bound
13	if (!SymEngine::is_a<SymEngine::Unequality>(*condition)) {	×
14	return false;	×
15	}
16	auto eq = SymEngine::rcp_static_cast<const SymEngine::Unequality>(condition);	×
17	auto eq_args = eq->get_args();	×
18	auto bound = eq_args.at(0);	×
19	auto symbol = eq_args.at(1);	×
20	if (symbolic::uses(symbol, indvar) && symbolic::uses(bound, indvar)) {	×
21	return false;	×
22	} else if (symbolic::uses(bound, indvar)) {	×
23	bound = eq_args.at(1);	×
24	symbol = eq_args.at(0);	×
25	}	×
26	if (symbolic::strict_monotonicity(symbol, indvar) != symbolic::Sign::POSITIVE) {	×
27	return false;	×
28	}
29
30	// Check if monotonic update
31	// TODO: Support more complex updates
32	auto match = symbolic::affine(update, indvar);	×
33	if (match.first == SymEngine::null) {	×
34	return false;	×
35	}
36	auto first_term = match.first;	×
37	auto second_term = match.second;	×
38	if (!SymEngine::is_a<SymEngine::Integer>(*first_term) \|\|	×
39	!SymEngine::is_a<SymEngine::Integer>(*second_term)) {	×
40	return false;	×
41	}
42	auto multiplier = SymEngine::rcp_static_cast<const SymEngine::Integer>(first_term);	×
43	auto offset = SymEngine::rcp_static_cast<const SymEngine::Integer>(second_term);	×
44	if (multiplier->as_int() >= 1 && offset->as_int() >= 0) {	×
45	auto new_bound = symbolic::Lt(symbol, bound);	×
46	loop.condition() = new_bound;	×
47	return true;	×
48	} else if (multiplier->as_int() <= 1 && offset->as_int() < 0) {	×
49	auto new_bound = symbolic::Gt(symbol, bound);	×
50	loop.condition() = new_bound;	×
51	return true;	×
52	} else {	×
53	return false;	×
54	}
55
56	return true;
57	};	×
58
59	LoopBoundNormalization::LoopBoundNormalization()	×
NEW 60	: Pass() {	×
61
62	};	×
63
64	std::string LoopBoundNormalization::name() { return "LoopBoundNormalization"; };	×
65
66	bool LoopBoundNormalization::run_pass(builder::StructuredSDFGBuilder& builder,	×
67	analysis::AnalysisManager& analysis_manager) {
68	bool applied = false;	×
69
70	// Traverse structured SDFG
71	std::list<structured_control_flow::ControlFlowNode*> queue = {&builder.subject().root()};	×
72	while (!queue.empty()) {	×
73	auto current = queue.front();	×
74	queue.pop_front();	×
75
76	// If sequence, attempt promotion
77	if (auto match = dynamic_cast<structured_control_flow::For*>(current)) {	×
78	applied \|= this->apply(builder, *match);	×
79	}	×
80
81	// Add children to queue
82	if (auto sequence_stmt = dynamic_cast<structured_control_flow::Sequence*>(current)) {	×
83	for (size_t i = 0; i < sequence_stmt->size(); i++) {	×
84	queue.push_back(&sequence_stmt->at(i).first);	×
85	}	×
86	} else if (auto if_else_stmt = dynamic_cast<structured_control_flow::IfElse*>(current)) {	×
87	for (size_t i = 0; i < if_else_stmt->size(); i++) {	×
88	queue.push_back(&if_else_stmt->at(i).first);	×
89	}	×
90	} else if (auto loop_stmt = dynamic_cast<structured_control_flow::While*>(current)) {	×
91	queue.push_back(&loop_stmt->root());	×
92	} else if (auto for_stmt = dynamic_cast<structured_control_flow::For*>(current)) {	×
93	queue.push_back(&for_stmt->root());	×
94	} else if (auto kern_stmt = dynamic_cast<const structured_control_flow::Kernel*>(current)) {	×
95	queue.push_back(&kern_stmt->root());	×
NEW 96	} else if (auto map_stmt = dynamic_cast<const structured_control_flow::Map*>(current)) {	×
NEW 97	queue.push_back(&map_stmt->root());	×
UNCOV 98	}	×
99	}
100
101	return applied;	×
102	};	×
103
104	} // namespace passes
105	} // namespace sdfg

daisytuner / sdfglib / 15340968114

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