19258124803

Committed 11 Nov 2025 07:18AM UTC coverage: 61.767% (+0.2%) from 61.551%

Build # 19258124803

Build Type

Pull #340

github

Committed by

web-flow

Commit Message

Merge c3254019c into 41e436a2a

Pull Request Pull Request #340: Adds BlockSorting and BlockHoisting Passes

Run Details

139 of 179 new or added lines in 5 files covered. (77.65%)

10538 of 17061 relevant lines covered (61.77%)

107.11 hits per line

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

68.42

/src/passes/code_motion/block_sorting.cpp

#include "sdfg/passes/code_motion/block_sorting.h"

#include <unordered_set>

#include "sdfg/analysis/analysis.h"
#include "sdfg/analysis/users.h"
#include "sdfg/analysis/scope_analysis.h"
#include "sdfg/builder/structured_sdfg_builder.h"
#include "sdfg/data_flow/access_node.h"
#include "sdfg/data_flow/data_flow_graph.h"
#include "sdfg/data_flow/memlet.h"
#include "sdfg/data_flow/tasklet.h"
#include "sdfg/element.h"
#include "sdfg/structured_control_flow/block.h"
#include "sdfg/structured_control_flow/control_flow_node.h"
#include "sdfg/structured_control_flow/if_else.h"
#include "sdfg/structured_control_flow/sequence.h"
#include "sdfg/structured_control_flow/structured_loop.h"
#include "sdfg/types/type.h"
#include "sdfg/visitor/structured_sdfg_visitor.h"

namespace sdfg {
namespace passes {

BlockSorting::BlockSorting(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager)
    : visitor::StructuredSDFGVisitor(builder, analysis_manager) {};

bool BlockSorting::accept(structured_control_flow::Sequence& sequence) {
    bool applied = false;
    for (size_t i = 0; i < sequence.size() - 1; i++) {
        auto current_child = sequence.at(i);
        if (!current_child.second.assignments().empty()) {
            continue;
        }
        // Highest-priority: skip if current block is not computational
        if (auto current_block = dynamic_cast<structured_control_flow::Block*>(&current_child.first)) {
            auto& current_dfg = current_block->dataflow();
            if (current_dfg.nodes().size() == 2 && current_dfg.edges().size() == 1) {
                auto& edge = *current_dfg.edges().begin();
                if (edge.type() == data_flow::MemletType::Reference
                    || edge.type() == data_flow::MemletType::Dereference_Src
                    || edge.type() == data_flow::MemletType::Dereference_Dst) {
                        continue;
                }
            }
        }

        auto next_child = sequence.at(i + 1);
        if (!next_child.second.assignments().empty()) {
            continue;
        }
        if (!dynamic_cast<structured_control_flow::Block*>(&current_child.first)) {
            continue;
        }
        auto& next_block = static_cast<structured_control_flow::Block&>(next_child.first);
        
        // Check if next block is a high-priority candidate for sorting
        auto& next_dfg = next_block.dataflow();
        if (next_dfg.nodes().size() != 2) {
            continue;
        }
        if (next_dfg.edges().size() != 1) {
            continue;
        }
        auto& edge = *next_dfg.edges().begin();
        if (edge.type() != data_flow::MemletType::Reference
            && edge.type() != data_flow::MemletType::Dereference_Src
            && edge.type() != data_flow::MemletType::Dereference_Dst) {
            continue;
        }

        // Check if current block has side-effects
        if (auto current_block = dynamic_cast<structured_control_flow::Block*>(&current_child.first)) {
            auto& current_dfg = current_block->dataflow();
            for (auto& libnode : current_dfg.library_nodes()) {
                continue;
            }
        } else {
            continue;
        }

        // Check if happens-before relation allows swapping
        auto& users_analysis = this->analysis_manager_.get<analysis::Users>();
        analysis::UsersView current_users(users_analysis, current_child.first);
        analysis::UsersView next_users(users_analysis, next_child.first);
        bool safe = true;
        for (auto user : next_users.uses()) {
            if (current_users.uses(user->container()).size() > 0) {
                safe = false;
                break;
            }
        }
        if (!safe) {
            continue;
        }

        // Swap blocks
        DEBUG_PRINTLN("BlockSorting: Swapping blocks " << current_child.first.element_id() << " " << next_child.first.element_id());
        builder_.move_child(sequence, i + 1, sequence, i);
        applied = true;
        break; // Restart after modification
    }

    return applied;
}

} // namespace passes
} // namespace sdfg

1	#include "sdfg/passes/code_motion/block_sorting.h"
2
3	#include <unordered_set>
4
5	#include "sdfg/analysis/analysis.h"
6	#include "sdfg/analysis/users.h"
7	#include "sdfg/analysis/scope_analysis.h"
8	#include "sdfg/builder/structured_sdfg_builder.h"
9	#include "sdfg/data_flow/access_node.h"
10	#include "sdfg/data_flow/data_flow_graph.h"
11	#include "sdfg/data_flow/memlet.h"
12	#include "sdfg/data_flow/tasklet.h"
13	#include "sdfg/element.h"
14	#include "sdfg/structured_control_flow/block.h"
15	#include "sdfg/structured_control_flow/control_flow_node.h"
16	#include "sdfg/structured_control_flow/if_else.h"
17	#include "sdfg/structured_control_flow/sequence.h"
18	#include "sdfg/structured_control_flow/structured_loop.h"
19	#include "sdfg/types/type.h"
20	#include "sdfg/visitor/structured_sdfg_visitor.h"
21
22	namespace sdfg {
23	namespace passes {
24
25	BlockSorting::BlockSorting(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager)	1✔
26	: visitor::StructuredSDFGVisitor(builder, analysis_manager) {};	1✔
27
28	bool BlockSorting::accept(structured_control_flow::Sequence& sequence) {	1✔
29	bool applied = false;	1✔
30	for (size_t i = 0; i < sequence.size() - 1; i++) {	2✔
31	auto current_child = sequence.at(i);	1✔
32	if (!current_child.second.assignments().empty()) {	1✔
NEW 33	continue;	×
34	}
35	// Highest-priority: skip if current block is not computational
36	if (auto current_block = dynamic_cast<structured_control_flow::Block*>(&current_child.first)) {	1✔
37	auto& current_dfg = current_block->dataflow();	1✔
38	if (current_dfg.nodes().size() == 2 && current_dfg.edges().size() == 1) {	1✔
NEW 39	auto& edge = *current_dfg.edges().begin();	×
NEW 40	if (edge.type() == data_flow::MemletType::Reference	×
NEW 41	\|\| edge.type() == data_flow::MemletType::Dereference_Src	×
NEW 42	\|\| edge.type() == data_flow::MemletType::Dereference_Dst) {	×
NEW 43	continue;	×
44	}
NEW 45	}	×
46	}	1✔
47
48	auto next_child = sequence.at(i + 1);	1✔
49	if (!next_child.second.assignments().empty()) {	1✔
NEW 50	continue;	×
51	}
52	if (!dynamic_cast<structured_control_flow::Block*>(&current_child.first)) {	1✔
NEW 53	continue;	×
54	}
55	auto& next_block = static_cast<structured_control_flow::Block&>(next_child.first);	1✔
56
57	// Check if next block is a high-priority candidate for sorting
58	auto& next_dfg = next_block.dataflow();	1✔
59	if (next_dfg.nodes().size() != 2) {	1✔
NEW 60	continue;	×
61	}
62	if (next_dfg.edges().size() != 1) {	1✔
NEW 63	continue;	×
64	}
65	auto& edge = *next_dfg.edges().begin();	1✔
66	if (edge.type() != data_flow::MemletType::Reference	1✔
67	&& edge.type() != data_flow::MemletType::Dereference_Src	1✔
68	&& edge.type() != data_flow::MemletType::Dereference_Dst) {	1✔
NEW 69	continue;	×
70	}
71
72	// Check if current block has side-effects
73	if (auto current_block = dynamic_cast<structured_control_flow::Block*>(&current_child.first)) {	1✔
74	auto& current_dfg = current_block->dataflow();	1✔
75	for (auto& libnode : current_dfg.library_nodes()) {	1✔
NEW 76	continue;	×
77	}
78	} else {	1✔
NEW 79	continue;	×
80	}
81
82	// Check if happens-before relation allows swapping
83	auto& users_analysis = this->analysis_manager_.get<analysis::Users>();	1✔
84	analysis::UsersView current_users(users_analysis, current_child.first);	1✔
85	analysis::UsersView next_users(users_analysis, next_child.first);	1✔
86	bool safe = true;	1✔
87	for (auto user : next_users.uses()) {	3✔
88	if (current_users.uses(user->container()).size() > 0) {	2✔
NEW 89	safe = false;	×
NEW 90	break;	×
91	}
92	}
93	if (!safe) {	1✔
NEW 94	continue;	×
95	}
96
97	// Swap blocks
98	DEBUG_PRINTLN("BlockSorting: Swapping blocks " << current_child.first.element_id() << " " << next_child.first.element_id());	1✔
99	builder_.move_child(sequence, i + 1, sequence, i);	1✔
100	applied = true;	1✔
101	break; // Restart after modification	1✔
102	}	1✔
103
104	return applied;	1✔
NEW 105	}	×
106
107	} // namespace passes
108	} // namespace sdfg

daisytuner / sdfglib / 19258124803

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