19336243385

Committed 13 Nov 2025 03:14PM UTC coverage: 62.407% (+0.6%) from 61.76%

Build # 19336243385

Build Type

push

github

Committed by

web-flow

Commit Message

Extended BlockHoisting and BlockSorting (#345)

* Added hoisting moves and views from branching to BlockHoistingPass

* Added hoisting library nodes (alloca, memcpy, memmove, memset) to BlockHoistingPass

* Added hoisting library nodes from branches to BlockHoistingPass

* Added hoisting for last child of loops and branches to BlockHoistingPass

* Little bugfies

* Adapted BlockSortingPass to handle library nodes (without side effects)

* Bugfix for BlockSorting

Library nodes with side effects were swapped which lead to dead code because an exit was bubbled up

Run Details

369 of 463 new or added lines in 3 files covered. (79.7%)

14 existing lines in 2 files now uncovered.

10905 of 17474 relevant lines covered (62.41%)

112.11 hits per line

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

56.96

/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/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/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) {
    if (sequence.size() == 0) {
        return false;
    }

    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;
        }
        auto* next_block = dynamic_cast<structured_control_flow::Block*>(&next_child.first);
        if (!next_block) {
            continue;
        }

        // Check if next block is a high-priority candidate for sorting
        if (!this->is_reference_block(*next_block) && !this->is_libnode_block(*next_block)) {
            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();
            bool side_effect = false;
            for (auto& libnode : current_dfg.library_nodes()) {
                if (libnode->side_effect()) {
                    side_effect = true;
                    break;
                }
            }
            if (side_effect) {
                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()
                                             << " in '" << builder_.subject().name() << "'"
        );
        builder_.move_child(sequence, i + 1, sequence, i);
        applied = true;
        break; // Restart after modification
    }

    return applied;
}

bool BlockSorting::is_reference_block(structured_control_flow::Block& next_block) {
    auto& next_dfg = next_block.dataflow();
    if (next_dfg.nodes().size() != 2) {
        return false;
    }
    if (next_dfg.edges().size() != 1) {
        return false;
    }
    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) {
        return false;
    }
    return true;
}

bool BlockSorting::is_libnode_block(structured_control_flow::Block& next_block) {
    auto& next_dfg = next_block.dataflow();
    if (next_dfg.library_nodes().size() != 1) {
        return false;
    }
    auto* libnode = *next_dfg.library_nodes().begin();
    if (libnode->side_effect()) {
        return false;
    }
    if (next_dfg.edges().size() != libnode->inputs().size() + libnode->outputs().size()) {
        return false;
    }
    return true;
}

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

daisytuner / sdfglib / 19336243385

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