15512041711

Committed 07 Jun 2025 09:59PM UTC coverage: 57.416% (+0.1%) from 57.315%

Build # 15512041711

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #44 from daisytuner/StructuredLoops

Add Structured Loops

Run Details

51 of 102 new or added lines in 20 files covered. (50.0%)

10 existing lines in 8 files now uncovered.

7618 of 13268 relevant lines covered (57.42%)

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

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

daisytuner / sdfglib / 15512041711

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