23890660897

Committed 02 Apr 2026 08:06AM UTC coverage: 64.468% (+0.02%) from 64.453%

Build # 23890660897

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #624 from daisytuner/no-inv-loop-dist

Skip redundant invalidates on perfect loop distribution

Coverage Stats

43 of 45 new or added lines in 2 files covered. (95.56%)

4 existing lines in 2 files now uncovered.

28803 of 44678 relevant lines covered (64.47%)

436.12 hits per line

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

95.77

/opt/src/passes/normalization/perfect_loop_distribution.cpp

#include "sdfg/passes/normalization/perfect_loop_distribution.h"

#include <sdfg/structured_control_flow/structured_loop.h>
#include <sdfg/transformations/loop_distribute.h>
#include <sdfg/visitor/structured_sdfg_visitor.h>
#include <unordered_set>
#include "sdfg/analysis/loop_analysis.h"

namespace sdfg {
namespace passes {
namespace normalization {

bool PerfectLoopDistributionPass::can_be_applied(
    builder::StructuredSDFGBuilder& builder,
    analysis::AnalysisManager& analysis_manager,
    structured_control_flow::StructuredLoop& loop
) {
    if (loop.root().size() == 1) {
        return false;
    }

    bool has_subloop = false;
    for (size_t i = 0; i < loop.root().size(); i++) {
        // skip blocks
        if (dynamic_cast<structured_control_flow::Block*>(&loop.root().at(i).first)) {
            continue;
        }
        if (dynamic_cast<structured_control_flow::StructuredLoop*>(&loop.root().at(i).first)) {
            has_subloop = true;
            break;
        }
        // if not a block or a loop, then we can't apply the transformation
        return false;
    }
    if (!has_subloop) {
        return false;
    }

    transformations::LoopDistribute loop_distribute(loop);
    if (!loop_distribute.can_be_applied(builder, analysis_manager)) {
        return false;
    }

    return true;
};

void PerfectLoopDistributionPass::apply(
    builder::StructuredSDFGBuilder& builder,
    analysis::AnalysisManager& analysis_manager,
    structured_control_flow::StructuredLoop& loop
) {
    transformations::LoopDistribute loop_distribute(loop);
    loop_distribute.apply(builder, analysis_manager);
};

PerfectLoopDistributionPass::PerfectLoopDistributionPass()
    : passes::Pass() {

      };


bool PerfectLoopDistributionPass::
    run_pass(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {
    auto& loop_analysis = analysis_manager.get<analysis::LoopAnalysis>();
    auto& outermost_loops = loop_analysis.outermost_loops();
    std::list<std::vector<sdfg::structured_control_flow::ControlFlowNode*>> loop_tree_paths;

    for (auto& loop : outermost_loops) {
        loop_tree_paths.splice(loop_tree_paths.end(), loop_analysis.loop_tree_paths(loop));
    }

    if (loop_tree_paths.empty()) {
        // No loops to process, so we can exit early
        return false;
    }

    // sort paths by depth (deepest first)
    loop_tree_paths.sort([](const std::vector<sdfg::structured_control_flow::ControlFlowNode*>& a,
                            const std::vector<sdfg::structured_control_flow::ControlFlowNode*>& b) {
        return a.size() > b.size();
    });

    bool changed = false;
    auto max_depth = loop_tree_paths.front().size();
    for (size_t depth = max_depth; depth > 0; depth--) {
        // get individual loops at this depth
        std::unordered_set<structured_control_flow::StructuredLoop*> loops_at_depth;
        for (auto& path : loop_tree_paths) {
            if (path.size() < depth) {
                // We can break here because paths are sorted by depth, so all subsequent paths will be shallower
                break;
            }
            auto* node = path[depth - 1];
            auto* loop = dynamic_cast<structured_control_flow::StructuredLoop*>(node);
            if (loop) {
                loops_at_depth.insert(loop);
            }
        }

        // find applicable loops at this depth
        std::unordered_set<structured_control_flow::StructuredLoop*> applicable_loops;
        for (auto* loop : loops_at_depth) {
            if (this->can_be_applied(builder, analysis_manager, *loop)) {
                applicable_loops.insert(loop);
            }
        }

        // apply transformation to applicable loops
        for (auto* loop : applicable_loops) {
            this->apply(builder, analysis_manager, *loop);
            changed = true;
        }
    }
    return changed;
}

} // namespace normalization
} // namespace passes
} // namespace sdfg

1	#include "sdfg/passes/normalization/perfect_loop_distribution.h"
2
3	#include <sdfg/structured_control_flow/structured_loop.h>
4	#include <sdfg/transformations/loop_distribute.h>
5	#include <sdfg/visitor/structured_sdfg_visitor.h>
6	#include <unordered_set>
7	#include "sdfg/analysis/loop_analysis.h"
8
9	namespace sdfg {
10	namespace passes {
11	namespace normalization {
12
13	bool PerfectLoopDistributionPass::can_be_applied(
14	builder::StructuredSDFGBuilder& builder,
15	analysis::AnalysisManager& analysis_manager,
16	structured_control_flow::StructuredLoop& loop
17	) {	363✔
18	if (loop.root().size() == 1) {	363✔
19	return false;	261✔
20	}	261✔
21
22	bool has_subloop = false;	102✔
23	for (size_t i = 0; i < loop.root().size(); i++) {	231✔
24	// skip blocks
25	if (dynamic_cast<structured_control_flow::Block*>(&loop.root().at(i).first)) {	181✔
26	continue;	129✔
27	}	129✔
28	if (dynamic_cast<structured_control_flow::StructuredLoop*>(&loop.root().at(i).first)) {	52✔
29	has_subloop = true;	52✔
30	break;	52✔
31	}	52✔
32	// if not a block or a loop, then we can't apply the transformation
33	return false;	×
34	}	52✔
35	if (!has_subloop) {	102✔
36	return false;	50✔
37	}	50✔
38
39	transformations::LoopDistribute loop_distribute(loop);	52✔
40	if (!loop_distribute.can_be_applied(builder, analysis_manager)) {	52✔
41	return false;	20✔
42	}	20✔
43
44	return true;	32✔
45	};	52✔
46
47	void PerfectLoopDistributionPass::apply(
48	builder::StructuredSDFGBuilder& builder,
49	analysis::AnalysisManager& analysis_manager,
50	structured_control_flow::StructuredLoop& loop
51	) {	32✔
52	transformations::LoopDistribute loop_distribute(loop);	32✔
53	loop_distribute.apply(builder, analysis_manager);	32✔
54	};	32✔
55
56	PerfectLoopDistributionPass::PerfectLoopDistributionPass()
57	: passes::Pass() {	31✔
58
59	};	31✔
60
61
62	bool PerfectLoopDistributionPass::
63	run_pass(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	78✔
64	auto& loop_analysis = analysis_manager.get<analysis::LoopAnalysis>();	78✔
65	auto& outermost_loops = loop_analysis.outermost_loops();	78✔
66	std::list<std::vector<sdfg::structured_control_flow::ControlFlowNode*>> loop_tree_paths;	78✔
67
68	for (auto& loop : outermost_loops) {	162✔
69	loop_tree_paths.splice(loop_tree_paths.end(), loop_analysis.loop_tree_paths(loop));	162✔
70	}	162✔
71
72	if (loop_tree_paths.empty()) {	78✔
73	// No loops to process, so we can exit early
NEW 74	return false;	×
UNCOV 75	}	×
76
77	// sort paths by depth (deepest first)
78	loop_tree_paths.sort([](const std::vector<sdfg::structured_control_flow::ControlFlowNode*>& a,	78✔
79	const std::vector<sdfg::structured_control_flow::ControlFlowNode*>& b) {	153✔
80	return a.size() > b.size();	153✔
81	});	153✔
82
83	bool changed = false;	78✔
84	auto max_depth = loop_tree_paths.front().size();	78✔
85	for (size_t depth = max_depth; depth > 0; depth--) {	284✔
86	// get individual loops at this depth
87	std::unordered_set<structured_control_flow::StructuredLoop*> loops_at_depth;	206✔
88	for (auto& path : loop_tree_paths) {	475✔
89	if (path.size() < depth) {	475✔
90	// We can break here because paths are sorted by depth, so all subsequent paths will be shallower
91	break;	68✔
92	}	68✔
93	auto* node = path[depth - 1];	407✔
94	auto* loop = dynamic_cast<structured_control_flow::StructuredLoop*>(node);	407✔
95	if (loop) {	407✔
96	loops_at_depth.insert(loop);	407✔
97	}	407✔
98	}	407✔
99
100	// find applicable loops at this depth
101	std::unordered_set<structured_control_flow::StructuredLoop*> applicable_loops;	206✔
102	for (auto* loop : loops_at_depth) {	363✔
103	if (this->can_be_applied(builder, analysis_manager, *loop)) {	363✔
104	applicable_loops.insert(loop);	32✔
105	}	32✔
106	}	363✔
107
108	// apply transformation to applicable loops
109	for (auto* loop : applicable_loops) {	206✔
110	this->apply(builder, analysis_manager, *loop);	32✔
111	changed = true;	32✔
112	}	32✔
113	}	206✔
114	return changed;	78✔
115	}	78✔
116
117	} // namespace normalization
118	} // namespace passes
119	} // namespace sdfg

daisytuner / docc / 23890660897

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