28156217026

Committed 25 Jun 2026 08:09AM UTC coverage: 61.616% (+0.03%) from 61.582%

Build # 28156217026

Build Type

Pull #811

github

Committed by

web-flow

Commit Message

Merge c362b48ab into 0a5f3e8d4

Pull Request Pull Request #811: Add a pass to make loop indvars unique again

Coverage Stats

64 of 72 new or added lines in 2 files covered. (88.89%)

19 existing lines in 1 file now uncovered.

37640 of 61088 relevant lines covered (61.62%)

999.0 hits per line

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

81.74

/opt/src/passes/scheduler/loop_scheduling_pass.cpp

#include "sdfg/passes/scheduler/loop_scheduling_pass.h"

#include "sdfg/analysis/data_transfer_elimination_analysis.h"
#include "sdfg/passes/offloading/data_transfer_minimization_pass.h"
#include "sdfg/passes/scheduler/loop_scheduler.h"
#include "sdfg/passes/scheduler/scheduler_registry.h"
#include "sdfg/structured_control_flow/map.h"

namespace sdfg {
namespace passes {
namespace scheduler {

bool LoopSchedulingPass::run_pass_target(
    builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager, const std::string& target
) {
    auto scheduler = SchedulerRegistry::instance().get_loop_scheduler(target);
    if (!scheduler) {
        throw std::runtime_error("Unsupported scheduling target: " + target);
    }
    scheduler->set_report(report_);

    // ===== Phase 1: Find all applicable loops =====
    auto& loop_analysis = analysis_manager.get<analysis::LoopAnalysis>();
    auto& flop_analysis = analysis_manager.get<analysis::FlopAnalysis>();

    // Initialize queue with outermost loops
    std::list<structured_control_flow::ControlFlowNode*> queue;
    std::unordered_map<structured_control_flow::ControlFlowNode*, SchedulerLoopInfo> scheduling_info_map;
    for (auto& loop : loop_analysis.outermost_loops()) {
        queue.push_back(loop);

        SchedulerLoopInfo info;
        info.loop_info = loop_analysis.loop_info(loop);
        info.flop = flop_analysis.get(loop);
        scheduling_info_map[loop] = info;
    }
    if (queue.empty()) {
        return false;
    }

    // Filter by compatible types
    size_t num_to_check = queue.size();
    for (size_t i = 0; i < num_to_check; i++) {
        auto loop = queue.front();
        queue.pop_front();

        bool found_incompatible = false;

        // Check descendants
        if (!found_incompatible) {
            auto descendants = loop_analysis.descendants(loop);
            for (auto descendant : descendants) {
                if (auto map_node = dynamic_cast<structured_control_flow::Map*>(descendant)) {
                    auto compatible_schedules = scheduler->compatible_types();
                    if (compatible_schedules.find(map_node->schedule_type().category()) == compatible_schedules.end()) {
                        found_incompatible = true;
                        break;
                    }
                }
            }
        }

        if (!found_incompatible) {
            queue.push_back(loop);
        }
    }

    // Traverse loop tree using scheduler's find() to collect applicable loops
    std::vector<structured_control_flow::StructuredLoop*> applicable_loops;
    while (!queue.empty()) {
        auto loop = queue.front();
        queue.pop_front();

        auto scheduling_info = scheduling_info_map.at(loop);
        scheduling_info_map.erase(loop);

        // Set the report context
        if (report_ && scheduling_info.loop_info.loopnest_index >= 0) {
            report_->in_outermost_loop(scheduling_info.loop_info.loopnest_index);
        }

        SchedulerAction action;
        if (auto while_loop = dynamic_cast<structured_control_flow::While*>(loop)) {
            action = scheduler->find(builder, analysis_manager, *while_loop, offload_unknown_sizes_);
        } else if (auto structured_loop = dynamic_cast<structured_control_flow::StructuredLoop*>(loop)) {
            action = scheduler->find(builder, analysis_manager, *structured_loop, offload_unknown_sizes_);
        } else {
            throw InvalidSDFGException("LoopScheduler encountered non-loop in loop analysis.");
        }

        switch (action) {
            case SchedulerAction::NEXT: {
                if (auto structured_loop = dynamic_cast<structured_control_flow::StructuredLoop*>(loop)) {
                    applicable_loops.push_back(structured_loop);
                }
                break;
            }
            case SchedulerAction::CHILDREN: {
                auto children = loop_analysis.children(loop);
                for (auto& child : children) {
                    queue.push_front(child);

                    SchedulerLoopInfo info;
                    info.loop_info = loop_analysis.loop_info(child);
                    info.flop = flop_analysis.get(child);
                    scheduling_info_map[child] = info;
                }
                break;
            }
        }
    }

    if (applicable_loops.empty()) {
        return false;
    }

    // ===== Phase 2: Pre-schedule (collapse + cleanup) =====
    scheduler->pre_schedule(builder, analysis_manager, applicable_loops);

    // ===== Phase 3: Apply scheduling transforms =====
    // Phase 3a: Collect loops where transform can be applied
    std::vector<structured_control_flow::StructuredLoop*> schedulable_loops;
    for (auto* loop : applicable_loops) {
        if (scheduler->can_apply_schedule(builder, analysis_manager, *loop, offload_unknown_sizes_)) {
            schedulable_loops.push_back(loop);
        }
    }

    if (schedulable_loops.empty()) {
        return false;
    }

    // Phase 3b: Apply transforms
    for (auto* loop : schedulable_loops) {
        scheduler->apply_schedule(builder, analysis_manager, *loop, offload_unknown_sizes_);
    }
    analysis_manager.preserve<sdfg::analysis::ArgumentsAnalysis>();

    // ===== Phase 4: Post-schedule =====
    scheduler->post_schedule(builder, analysis_manager, schedulable_loops);

    return true;
}

bool LoopSchedulingPass::run_pass(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {
    if (targets_.empty()) {
        return false;
    }
    if (targets_.size() == 1 && targets_[0] == "none") {
        return false;
    }

    bool applied = false;
    for (const auto& target : targets_) {
        bool target_applied = run_pass_target(builder, analysis_manager, target);
        if (target_applied) {
            analysis_manager.invalidate_all();
        }
        applied = applied || target_applied;
    }

    return applied;
}

} // namespace scheduler
} // namespace passes
} // namespace sdfg

1	#include "sdfg/passes/scheduler/loop_scheduling_pass.h"
2
3	#include "sdfg/analysis/data_transfer_elimination_analysis.h"
4	#include "sdfg/passes/offloading/data_transfer_minimization_pass.h"
5	#include "sdfg/passes/scheduler/loop_scheduler.h"
6	#include "sdfg/passes/scheduler/scheduler_registry.h"
7	#include "sdfg/structured_control_flow/map.h"
8
9	namespace sdfg {
10	namespace passes {
11	namespace scheduler {
12
13	bool LoopSchedulingPass::run_pass_target(
14	builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager, const std::string& target
15	) {	9✔
16	auto scheduler = SchedulerRegistry::instance().get_loop_scheduler(target);	9✔
17	if (!scheduler) {	9✔
UNCOV 18	throw std::runtime_error("Unsupported scheduling target: " + target);	×
19	}	×
20	scheduler->set_report(report_);	9✔
21
22	// ===== Phase 1: Find all applicable loops =====
23	auto& loop_analysis = analysis_manager.get<analysis::LoopAnalysis>();	9✔
24	auto& flop_analysis = analysis_manager.get<analysis::FlopAnalysis>();	9✔
25
26	// Initialize queue with outermost loops
27	std::list<structured_control_flow::ControlFlowNode*> queue;	9✔
28	std::unordered_map<structured_control_flow::ControlFlowNode*, SchedulerLoopInfo> scheduling_info_map;	9✔
29	for (auto& loop : loop_analysis.outermost_loops()) {	18✔
30	queue.push_back(loop);	18✔
31
32	SchedulerLoopInfo info;	18✔
33	info.loop_info = loop_analysis.loop_info(loop);	18✔
34	info.flop = flop_analysis.get(loop);	18✔
35	scheduling_info_map[loop] = info;	18✔
36	}	18✔
37	if (queue.empty()) {	9✔
UNCOV 38	return false;	×
UNCOV 39	}	×
40
41	// Filter by compatible types
42	size_t num_to_check = queue.size();	9✔
43	for (size_t i = 0; i < num_to_check; i++) {	27✔
44	auto loop = queue.front();	18✔
45	queue.pop_front();	18✔
46
47	bool found_incompatible = false;	18✔
48
49	// Check descendants
50	if (!found_incompatible) {	18✔
51	auto descendants = loop_analysis.descendants(loop);	18✔
52	for (auto descendant : descendants) {	18✔
53	if (auto map_node = dynamic_cast<structured_control_flow::Map*>(descendant)) {	10✔
54	auto compatible_schedules = scheduler->compatible_types();	10✔
55	if (compatible_schedules.find(map_node->schedule_type().category()) == compatible_schedules.end()) {	10✔
UNCOV 56	found_incompatible = true;	×
UNCOV 57	break;	×
UNCOV 58	}	×
59	}	10✔
60	}	10✔
61	}	18✔
62
63	if (!found_incompatible) {	18✔
64	queue.push_back(loop);	18✔
65	}	18✔
66	}	18✔
67
68	// Traverse loop tree using scheduler's find() to collect applicable loops
69	std::vector<structured_control_flow::StructuredLoop*> applicable_loops;	9✔
70	while (!queue.empty()) {	33✔
71	auto loop = queue.front();	24✔
72	queue.pop_front();	24✔
73
74	auto scheduling_info = scheduling_info_map.at(loop);	24✔
75	scheduling_info_map.erase(loop);	24✔
76
77	// Set the report context
78	if (report_ && scheduling_info.loop_info.loopnest_index >= 0) {	24✔
UNCOV 79	report_->in_outermost_loop(scheduling_info.loop_info.loopnest_index);	×
UNCOV 80	}	×
81
82	SchedulerAction action;	24✔
83	if (auto while_loop = dynamic_cast<structured_control_flow::While*>(loop)) {	24✔
84	action = scheduler->find(builder, analysis_manager, *while_loop, offload_unknown_sizes_);	4✔
85	} else if (auto structured_loop = dynamic_cast<structured_control_flow::StructuredLoop*>(loop)) {	20✔
86	action = scheduler->find(builder, analysis_manager, *structured_loop, offload_unknown_sizes_);	20✔
87	} else {	20✔
UNCOV 88	throw InvalidSDFGException("LoopScheduler encountered non-loop in loop analysis.");	×
UNCOV 89	}	×
90
91	switch (action) {	24✔
92	case SchedulerAction::NEXT: {	20✔
93	if (auto structured_loop = dynamic_cast<structured_control_flow::StructuredLoop*>(loop)) {	20✔
94	applicable_loops.push_back(structured_loop);	20✔
95	}	20✔
96	break;	20✔
UNCOV 97	}	×
98	case SchedulerAction::CHILDREN: {	4✔
99	auto children = loop_analysis.children(loop);	4✔
100	for (auto& child : children) {	6✔
101	queue.push_front(child);	6✔
102
103	SchedulerLoopInfo info;	6✔
104	info.loop_info = loop_analysis.loop_info(child);	6✔
105	info.flop = flop_analysis.get(child);	6✔
106	scheduling_info_map[child] = info;	6✔
107	}	6✔
108	break;	4✔
UNCOV 109	}	×
110	}	24✔
111	}	24✔
112
113	if (applicable_loops.empty()) {	9✔
UNCOV 114	return false;	×
UNCOV 115	}	×
116
117	// ===== Phase 2: Pre-schedule (collapse + cleanup) =====
118	scheduler->pre_schedule(builder, analysis_manager, applicable_loops);	9✔
119
120	// ===== Phase 3: Apply scheduling transforms =====
121	// Phase 3a: Collect loops where transform can be applied
122	std::vector<structured_control_flow::StructuredLoop*> schedulable_loops;	9✔
123	for (auto* loop : applicable_loops) {	20✔
124	if (scheduler->can_apply_schedule(builder, analysis_manager, *loop, offload_unknown_sizes_)) {	20✔
125	schedulable_loops.push_back(loop);	20✔
126	}	20✔
127	}	20✔
128
129	if (schedulable_loops.empty()) {	9✔
UNCOV 130	return false;	×
UNCOV 131	}	×
132
133	// Phase 3b: Apply transforms
134	for (auto* loop : schedulable_loops) {	20✔
135	scheduler->apply_schedule(builder, analysis_manager, *loop, offload_unknown_sizes_);	20✔
136	}	20✔
137	analysis_manager.preserve<sdfg::analysis::ArgumentsAnalysis>();	9✔
138
139	// ===== Phase 4: Post-schedule =====
140	scheduler->post_schedule(builder, analysis_manager, schedulable_loops);	9✔
141
142	return true;	9✔
143	}	9✔
144
145	bool LoopSchedulingPass::run_pass(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	9✔
146	if (targets_.empty()) {	9✔
UNCOV 147	return false;	×
UNCOV 148	}	×
149	if (targets_.size() == 1 && targets_[0] == "none") {	9✔
UNCOV 150	return false;	×
151	}	×
152
153	bool applied = false;	9✔
154	for (const auto& target : targets_) {	9✔
155	bool target_applied = run_pass_target(builder, analysis_manager, target);	9✔
156	if (target_applied) {	9✔
157	analysis_manager.invalidate_all();	9✔
158	}	9✔
159	applied = applied \|\| target_applied;	9✔
160	}	9✔
161
162	return applied;	9✔
163	}	9✔
164
165	} // namespace scheduler
166	} // namespace passes
167	} // namespace sdfg

daisytuner / docc / 28156217026

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