23850118193

Committed 01 Apr 2026 01:06PM UTC coverage: 64.46%. First build

Build # 23850118193

Build Type

Pull #622

github

Committed by

web-flow

Commit Message

Merge 94c13aad2 into 53580ad0f

Pull Request Pull Request #622: Avoid Frequent Analysis Invalidation in Loop Scheduler

Coverage Stats

237 of 284 new or added lines in 15 files covered. (83.45%)

28931 of 44882 relevant lines covered (64.46%)

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

daisytuner / docc / 23850118193

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