15612270835

Committed 12 Jun 2025 01:44PM UTC coverage: 60.871% (-0.8%) from 61.71%

Build # 15612270835

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #68 from daisytuner/loop-types

refactors symbolic analysis into polynomials, extreme values and cnf

Run Details

638 of 862 new or added lines in 24 files covered. (74.01%)

334 existing lines in 20 files now uncovered.

6571 of 10795 relevant lines covered (60.87%)

100.35 hits per line

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

85.71

/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& loop_analysis = analysis_manager.get<analysis::LoopAnalysis>();
    if (!loop_analysis.is_contiguous(&loop)) {
        return false;
    }

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

    auto& assumptions = analysis_manager.get<analysis::AssumptionsAnalysis>();
    auto& assums = assumptions.get(loop);

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

daisytuner / sdfglib / 15612270835

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