24078671664

Committed 07 Apr 2026 11:19AM UTC coverage: 64.886%. First build

Build # 24078671664

Build Type

Pull #632

github

Committed by

web-flow

Commit Message

Merge de7071fd4 into be4a18f39

Pull Request Pull Request #632: Separate can_be_applied and apply for GPUTilling during Loop Scheduling

Coverage Stats

272 of 338 new or added lines in 15 files covered. (80.47%)

28868 of 44490 relevant lines covered (64.89%)

606.24 hits per line

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

81.42

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

#include "sdfg/passes/scheduler/loop_scheduling_pass.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
    for (int i = 0; i < queue.size(); i++) {
        auto loop = queue.front();
        queue.pop_front();

        auto descendants = loop_analysis.descendants(loop);

        bool found_incompatible = false;
        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.invalidate_all();

    // ===== 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);
        applied = applied || target_applied;
    }

    if (applied) {
        DataTransferMinimizationPass dtm_pass;
        dtm_pass.run(builder, analysis_manager);
    }

    return applied;
}

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

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

daisytuner / docc / 24078671664

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