17697974118

Committed 13 Sep 2025 02:36PM UTC coverage: 60.51% (+1.2%) from 59.335%

Build # 17697974118

Build Type

Pull #219

github

Committed by

web-flow

Commit Message

Merge a1c5ecbc6 into 6c1992b40

Pull Request Pull Request #219: stdlib Library Nodes and ConstantNodes

Run Details

565 of 1799 new or added lines in 102 files covered. (31.41%)

102 existing lines in 38 files now uncovered.

9442 of 15604 relevant lines covered (60.51%)

107.02 hits per line

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

83.33

/src/passes/structured_control_flow/loop_normalization.cpp

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

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

namespace sdfg {
namespace passes {

bool LoopNormalization::apply(
    builder::StructuredSDFGBuilder& builder,
    analysis::AnalysisManager& analysis_manager,
    structured_control_flow::For& loop
) {
    auto condition = loop.condition();

    bool applied = false;

    // Step 1: Normalize condition
    try {
        auto cnf = symbolic::conjunctive_normal_form(condition);
        symbolic::Condition new_condition = symbolic::__true__();
        for (auto& clause : cnf) {
            symbolic::Condition new_clause = symbolic::__false__();
            for (auto& literal : clause) {
                new_clause = symbolic::Or(new_clause, literal);
            }
            new_condition = symbolic::And(new_condition, new_clause);
        }
        if (!symbolic::eq(new_condition, condition)) {
            builder.update_loop(loop, loop.indvar(), new_condition, loop.init(), loop.update());
            applied = true;
        }

        condition = new_condition;
    } catch (const symbolic::CNFException e) {
        return false;
    }

    auto& assumptions_analysis = analysis_manager.get<analysis::AssumptionsAnalysis>();
    if (!analysis::LoopAnalysis::is_contiguous(&loop, assumptions_analysis)) {
        return applied;
    }

    // Section: Condition
    // Turn inequalities into strict less than
    auto indvar = loop.indvar();

    try {
        auto cnf = symbolic::conjunctive_normal_form(condition);
        symbolic::CNF new_cnf;
        for (auto& clause : cnf) {
            std::vector<symbolic::Condition> new_clause;
            for (auto& literal : clause) {
                if (SymEngine::is_a<SymEngine::Unequality>(*literal)) {
                    auto eq = SymEngine::rcp_static_cast<const SymEngine::Unequality>(literal);
                    auto eq_args = eq->get_args();
                    auto lhs = eq_args.at(0);
                    auto rhs = eq_args.at(1);
                    if (SymEngine::eq(*lhs, *indvar) && !symbolic::uses(rhs, indvar)) {
                        new_clause.push_back(symbolic::Lt(lhs, rhs));
                    } else if (SymEngine::eq(*rhs, *indvar) && !symbolic::uses(lhs, indvar)) {
                        new_clause.push_back(symbolic::Lt(rhs, lhs));
                    } else {
                        new_clause.push_back(literal);
                    }
                } else {
                    new_clause.push_back(literal);
                }
            }
            new_cnf.push_back(new_clause);
        }
        // Construct new condition
        symbolic::Condition new_condition = symbolic::__true__();
        for (auto& clause : new_cnf) {
            symbolic::Condition new_clause = symbolic::__false__();
            for (auto& literal : clause) {
                new_clause = symbolic::Or(new_clause, literal);
            }
            new_condition = symbolic::And(new_condition, new_clause);
        }
        if (!symbolic::eq(new_condition, condition)) {
            builder.update_loop(loop, loop.indvar(), new_condition, loop.init(), loop.update());
            applied = true;
        }
        condition = new_condition;
    } catch (const symbolic::CNFException e) {
    }

    return applied;
};

LoopNormalization::LoopNormalization()
    : Pass() {

      };

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

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

    auto& loop_analysis = analysis_manager.get<analysis::LoopAnalysis>();
    for (const auto& loop : loop_analysis.loops()) {
        if (auto for_loop = dynamic_cast<structured_control_flow::For*>(loop)) {
            applied |= this->apply(builder, analysis_manager, *for_loop);
        }
    }

    return applied;
};

} // namespace passes
} // namespace sdfg

1	#include "sdfg/passes/structured_control_flow/loop_normalization.h"
2
3	#include "sdfg/analysis/assumptions_analysis.h"
4	#include "sdfg/analysis/loop_analysis.h"
5	#include "sdfg/symbolic/conjunctive_normal_form.h"
6	#include "sdfg/symbolic/series.h"
7
8	namespace sdfg {
9	namespace passes {
10
11	bool LoopNormalization::apply(	3✔
12	builder::StructuredSDFGBuilder& builder,
13	analysis::AnalysisManager& analysis_manager,
14	structured_control_flow::For& loop
15	) {
16	auto condition = loop.condition();	3✔
17
18	bool applied = false;	3✔
19
20	// Step 1: Normalize condition
21	try {
22	auto cnf = symbolic::conjunctive_normal_form(condition);	3✔
23	symbolic::Condition new_condition = symbolic::__true__();	3✔
24	for (auto& clause : cnf) {	7✔
25	symbolic::Condition new_clause = symbolic::__false__();	4✔
26	for (auto& literal : clause) {	9✔
27	new_clause = symbolic::Or(new_clause, literal);	5✔
28	}
29	new_condition = symbolic::And(new_condition, new_clause);	4✔
30	}	4✔
31	if (!symbolic::eq(new_condition, condition)) {	3✔
NEW 32	builder.update_loop(loop, loop.indvar(), new_condition, loop.init(), loop.update());	×
33	applied = true;	×
34	}	×
35
36	condition = new_condition;	3✔
37	} catch (const symbolic::CNFException e) {	3✔
38	return false;	×
39	}	×
40
41	auto& assumptions_analysis = analysis_manager.get<analysis::AssumptionsAnalysis>();	3✔
42	if (!analysis::LoopAnalysis::is_contiguous(&loop, assumptions_analysis)) {	3✔
43	return applied;	×
44	}
45
46	// Section: Condition
47	// Turn inequalities into strict less than
48	auto indvar = loop.indvar();	3✔
49
50	try {
51	auto cnf = symbolic::conjunctive_normal_form(condition);	3✔
52	symbolic::CNF new_cnf;	3✔
53	for (auto& clause : cnf) {	7✔
54	std::vector<symbolic::Condition> new_clause;	4✔
55	for (auto& literal : clause) {	9✔
56	if (SymEngine::is_a<SymEngine::Unequality>(*literal)) {	5✔
57	auto eq = SymEngine::rcp_static_cast<const SymEngine::Unequality>(literal);	5✔
58	auto eq_args = eq->get_args();	5✔
59	auto lhs = eq_args.at(0);	5✔
60	auto rhs = eq_args.at(1);	5✔
61	if (SymEngine::eq(lhs, indvar) && !symbolic::uses(rhs, indvar)) {	5✔
62	new_clause.push_back(symbolic::Lt(lhs, rhs));	×
63	} else if (SymEngine::eq(rhs, indvar) && !symbolic::uses(lhs, indvar)) {	5✔
64	new_clause.push_back(symbolic::Lt(rhs, lhs));	5✔
65	} else {	5✔
66	new_clause.push_back(literal);	×
67	}
68	} else {	5✔
69	new_clause.push_back(literal);	×
70	}
71	}
72	new_cnf.push_back(new_clause);	4✔
73	}	4✔
74	// Construct new condition
75	symbolic::Condition new_condition = symbolic::__true__();	3✔
76	for (auto& clause : new_cnf) {	7✔
77	symbolic::Condition new_clause = symbolic::__false__();	4✔
78	for (auto& literal : clause) {	9✔
79	new_clause = symbolic::Or(new_clause, literal);	5✔
80	}
81	new_condition = symbolic::And(new_condition, new_clause);	4✔
82	}	4✔
83	if (!symbolic::eq(new_condition, condition)) {	3✔
84	builder.update_loop(loop, loop.indvar(), new_condition, loop.init(), loop.update());	3✔
85	applied = true;	3✔
86	}	3✔
87	condition = new_condition;	3✔
88	} catch (const symbolic::CNFException e) {	3✔
89	}	×
90
91	return applied;	3✔
92	};	3✔
93
94	LoopNormalization::LoopNormalization()	3✔
95	: Pass() {	3✔
96
97	};	3✔
98
99	std::string LoopNormalization::name() { return "LoopNormalization"; };	×
100
101	bool LoopNormalization::run_pass(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	3✔
102	bool applied = false;	3✔
103
104	auto& loop_analysis = analysis_manager.get<analysis::LoopAnalysis>();	3✔
105	for (const auto& loop : loop_analysis.loops()) {	6✔
106	if (auto for_loop = dynamic_cast<structured_control_flow::For*>(loop)) {	3✔
107	applied \|= this->apply(builder, analysis_manager, *for_loop);	3✔
108	}	3✔
109	}
110
111	return applied;	3✔
112	};	×
113
114	} // namespace passes
115	} // namespace sdfg

daisytuner / sdfglib / 17697974118

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