15049122732

Committed 15 May 2025 03:33PM UTC coverage: 62.241% (+4.7%) from 57.525%

Build # 15049122732

Build Type

Pull #9

github

Committed by

web-flow

Commit Message

Merge b96e33e0e into 9d3b1a2b3

Pull Request Pull Request #9: Graphviz DOT Visualizer for SDFGs

Run Details

520 of 542 new or added lines in 3 files covered. (95.94%)

782 existing lines in 68 files now uncovered.

8049 of 12932 relevant lines covered (62.24%)

504.09 hits per line

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

38.04

/src/transformations/loop_to_kernel_dim.cpp

#include "sdfg/transformations/loop_to_kernel_dim.h"

#include <utility>

#include "sdfg/analysis/assumptions_analysis.h"
#include "sdfg/analysis/data_parallelism_analysis.h"
#include "sdfg/builder/structured_sdfg_builder.h"
#include "sdfg/passes/pipeline.h"
#include "sdfg/passes/structured_control_flow/dead_cfg_elimination.h"
#include "sdfg/passes/structured_control_flow/sequence_fusion.h"
#include "sdfg/structured_control_flow/if_else.h"
#include "sdfg/structured_control_flow/kernel.h"
#include "sdfg/structured_control_flow/sequence.h"
#include "sdfg/symbolic/symbolic.h"
#include "sdfg/transformations/utils.h"
#include "symengine/symengine_rcp.h"

namespace sdfg {
namespace transformations {

LoopToKernelDim::LoopToKernelDim(structured_control_flow::Sequence& parent,
                                 structured_control_flow::For& loop)
    : parent_(parent), loop_(loop) {};

std::string LoopToKernelDim::name() { return "LoopToKernelDim"; };

bool LoopToKernelDim::can_be_applied(Schedule& schedule) {
    auto& analysis_manager = schedule.analysis_manager();
    sdfg::passes::Pipeline expression_combine = sdfg::passes::Pipeline::expression_combine();
    sdfg::passes::Pipeline memlet_combine = sdfg::passes::Pipeline::memlet_combine();
    memlet_combine.run(schedule.builder(), analysis_manager);
    auto& builder = schedule.builder();

    auto& sdfg = builder.subject();
    auto& root = sdfg.root();

    // Criterion: Check if ancestor is a kernel
    if (root.size() != 1) {
        return false;
    }
    auto kernel = dynamic_cast<const sdfg::structured_control_flow::Kernel*>(&root.at(0).first);
    if (!kernel) {
        return false;
    }

    // Criterion: Iteration count is known and an Integer
    symbolic::Integer iteration_count = get_iteration_count(loop_);
    if (iteration_count == SymEngine::null) {
        return false;
    }

    // Criterion: Indvar is only used to access arrays
    auto& users = analysis_manager.get<analysis::Users>();
    analysis::UsersView body_users(users, loop_.root());
    for (auto user : body_users.reads(loop_.indvar()->get_name())) {
        if (auto access_node = dynamic_cast<data_flow::AccessNode*>(user->element())) {
            return false;
        }
    }

    // Criterion: Kernel dimensions are known and an Integer
    auto& assumptions_analysis = analysis_manager.get<analysis::AssumptionsAnalysis>();
    auto assumptions = assumptions_analysis.get(loop_.root());
    auto x_dim_size = assumptions[kernel->blockDim_x()].integer_value();
    if (x_dim_size == SymEngine::null) {
        return false;
    }
    auto y_dim_size = assumptions[kernel->blockDim_y()].integer_value();
    if (y_dim_size == SymEngine::null) {
        return false;
    }
    auto z_dim_size = assumptions[kernel->blockDim_z()].integer_value();
    if (z_dim_size == SymEngine::null) {
        return false;
    }

    // Criterion: Available kernel dimensions is free
    bool x_dim_available = false;
    bool y_dim_available = false;
    bool z_dim_available = false;

    if (!symbolic::eq(x_dim_size, symbolic::integer(1))) {
        if (body_users.reads(kernel->threadIdx_x()->get_name()).empty()) {
            x_dim_available = true;
        }
    }
    if (!symbolic::eq(y_dim_size, symbolic::integer(1))) {
        if (body_users.reads(kernel->threadIdx_y()->get_name()).empty()) {
            y_dim_available = true;
        }
    }
    if (!symbolic::eq(z_dim_size, symbolic::integer(1))) {
        if (body_users.reads(kernel->threadIdx_z()->get_name()).empty()) {
            z_dim_available = true;
        }
    }
    if (!x_dim_available && !y_dim_available && !z_dim_available) {
        return false;
    }

    // Criterion: Unused kernel dimension is bigger or equal to loop iteration count
    bool x_match = false;
    bool y_match = false;
    bool z_match = false;
    if (x_dim_available) {
        auto cond = symbolic::Ge(x_dim_size, iteration_count);
        if (symbolic::is_true(cond)) {
            x_match = true;
        }
    }
    if (y_dim_available) {
        auto cond = symbolic::Ge(y_dim_size, iteration_count);
        if (symbolic::is_true(cond)) {
            y_match = true;
        }
    }
    if (z_dim_available) {
        auto cond = symbolic::Ge(z_dim_size, iteration_count);
        if (symbolic::is_true(cond)) {
            z_match = true;
        }
    }
    if (!x_match && !y_match && !z_match) {
        return false;
    }

    // Criterion: Loop is a map
    auto& analysis = analysis_manager.get<analysis::DataParallelismAnalysis>();
    auto& data_dependencies = analysis.get(this->loop_);
    for (auto& dep : data_dependencies) {
        auto& container = dep.first;
        auto& dep_type = dep.second;
        if (dep_type < analysis::Parallelism::PARALLEL) {
            return false;
        }
    }

    return true;
};

void LoopToKernelDim::apply(Schedule& schedule) {
    auto& analysis_manager = schedule.analysis_manager();
    auto& builder = schedule.builder();
    auto& sdfg = builder.subject();
    auto& root = sdfg.root();
    auto kernel = static_cast<const sdfg::structured_control_flow::Kernel*>(&root.at(0).first);

    auto& assumptions_analysis = analysis_manager.get<analysis::AssumptionsAnalysis>();
    auto assumptions = assumptions_analysis.get(loop_.root());
    auto x_dim_size = assumptions[kernel->blockDim_x()].integer_value();
    auto y_dim_size = assumptions[kernel->blockDim_y()].integer_value();
    auto z_dim_size = assumptions[kernel->blockDim_z()].integer_value();

    bool x_dim_available = false;
    bool y_dim_available = false;
    bool z_dim_available = false;
    auto& users = analysis_manager.get<analysis::Users>();
    analysis::UsersView body_users(users, loop_.root());

    if (!symbolic::eq(x_dim_size, symbolic::integer(1))) {
        if (body_users.reads(kernel->threadIdx_x()->get_name()).empty()) {
            x_dim_available = true;
        }
    }
    if (!symbolic::eq(y_dim_size, symbolic::integer(1))) {
        if (body_users.reads(kernel->threadIdx_y()->get_name()).empty()) {
            y_dim_available = true;
        }
    }
    if (!symbolic::eq(z_dim_size, symbolic::integer(1))) {
        if (body_users.reads(kernel->threadIdx_z()->get_name()).empty()) {
            z_dim_available = true;
        }
    }

    bool x_match = false;
    bool y_match = false;
    bool z_match = false;
    symbolic::Integer iteration_count = get_iteration_count(loop_);
    if (x_dim_available) {
        auto cond = symbolic::Ge(x_dim_size, iteration_count);
        if (symbolic::is_true(cond)) {
            x_match = true;
        }
    }
    if (y_dim_available) {
        auto cond = symbolic::Ge(y_dim_size, iteration_count);
        if (symbolic::is_true(cond)) {
            y_match = true;
        }
    }
    if (z_dim_available) {
        auto cond = symbolic::Ge(z_dim_size, iteration_count);
        if (symbolic::is_true(cond)) {
            z_match = true;
        }
    }

    auto target_dim = kernel->threadIdx_z();
    if (x_match) {
        target_dim = kernel->threadIdx_x();
    } else if (y_match) {
        target_dim = kernel->threadIdx_y();
    }

    auto& parent = builder.parent(loop_);
    auto& if_else = builder.add_if_else_before(parent, loop_).first;
    auto condition =
        symbolic::subs(loop_.condition(), loop_.indvar(), symbolic::add(target_dim, loop_.init()));
    auto& branch = builder.add_case(if_else, condition);

    builder.insert_children(branch, loop_.root(), 0);
    branch.replace(loop_.indvar(), symbolic::add(target_dim, loop_.init()));
    builder.remove_child(parent, loop_);

    analysis_manager.invalidate_all();
    passes::SequenceFusion sf_pass;
    passes::DeadCFGElimination dce_pass;
    bool applies = false;
    do {
        applies = false;
        applies |= dce_pass.run(schedule.builder(), analysis_manager);
        applies |= sf_pass.run(schedule.builder(), analysis_manager);
    } while (applies);
};

}  // namespace transformations
}  // namespace sdfg

1	#include "sdfg/transformations/loop_to_kernel_dim.h"
2
3	#include <utility>
4
5	#include "sdfg/analysis/assumptions_analysis.h"
6	#include "sdfg/analysis/data_parallelism_analysis.h"
7	#include "sdfg/builder/structured_sdfg_builder.h"
8	#include "sdfg/passes/pipeline.h"
9	#include "sdfg/passes/structured_control_flow/dead_cfg_elimination.h"
10	#include "sdfg/passes/structured_control_flow/sequence_fusion.h"
11	#include "sdfg/structured_control_flow/if_else.h"
12	#include "sdfg/structured_control_flow/kernel.h"
13	#include "sdfg/structured_control_flow/sequence.h"
14	#include "sdfg/symbolic/symbolic.h"
15	#include "sdfg/transformations/utils.h"
16	#include "symengine/symengine_rcp.h"
17
18	namespace sdfg {
19	namespace transformations {
20
21	LoopToKernelDim::LoopToKernelDim(structured_control_flow::Sequence& parent,	3✔
22	structured_control_flow::For& loop)
23	: parent_(parent), loop_(loop) {};	3✔
24
25	std::string LoopToKernelDim::name() { return "LoopToKernelDim"; };	×
26
27	bool LoopToKernelDim::can_be_applied(Schedule& schedule) {	3✔
28	auto& analysis_manager = schedule.analysis_manager();	3✔
29	sdfg::passes::Pipeline expression_combine = sdfg::passes::Pipeline::expression_combine();	3✔
30	sdfg::passes::Pipeline memlet_combine = sdfg::passes::Pipeline::memlet_combine();	3✔
31	memlet_combine.run(schedule.builder(), analysis_manager);	3✔
32	auto& builder = schedule.builder();	3✔
33
34	auto& sdfg = builder.subject();	3✔
35	auto& root = sdfg.root();	3✔
36
37	// Criterion: Check if ancestor is a kernel
38	if (root.size() != 1) {	3✔
39	return false;	×
40	}
41	auto kernel = dynamic_cast<const sdfg::structured_control_flow::Kernel*>(&root.at(0).first);	3✔
42	if (!kernel) {	3✔
43	return false;	×
44	}
45
46	// Criterion: Iteration count is known and an Integer
47	symbolic::Integer iteration_count = get_iteration_count(loop_);	3✔
48	if (iteration_count == SymEngine::null) {	3✔
49	return false;	×
50	}
51
52	// Criterion: Indvar is only used to access arrays
53	auto& users = analysis_manager.get<analysis::Users>();	3✔
54	analysis::UsersView body_users(users, loop_.root());	3✔
55	for (auto user : body_users.reads(loop_.indvar()->get_name())) {	8✔
56	if (auto access_node = dynamic_cast<data_flow::AccessNode*>(user->element())) {	5✔
57	return false;	×
58	}
59	}
60
61	// Criterion: Kernel dimensions are known and an Integer
62	auto& assumptions_analysis = analysis_manager.get<analysis::AssumptionsAnalysis>();	3✔
63	auto assumptions = assumptions_analysis.get(loop_.root());	3✔
64	auto x_dim_size = assumptions[kernel->blockDim_x()].integer_value();	3✔
65	if (x_dim_size == SymEngine::null) {	3✔
66	return false;	×
67	}
68	auto y_dim_size = assumptions[kernel->blockDim_y()].integer_value();	3✔
69	if (y_dim_size == SymEngine::null) {	3✔
70	return false;	×
71	}
72	auto z_dim_size = assumptions[kernel->blockDim_z()].integer_value();	3✔
73	if (z_dim_size == SymEngine::null) {	3✔
74	return false;	×
75	}
76
77	// Criterion: Available kernel dimensions is free
78	bool x_dim_available = false;	3✔
79	bool y_dim_available = false;	3✔
80	bool z_dim_available = false;	3✔
81
82	if (!symbolic::eq(x_dim_size, symbolic::integer(1))) {	3✔
83	if (body_users.reads(kernel->threadIdx_x()->get_name()).empty()) {	3✔
84	x_dim_available = true;	×
UNCOV 85	}	×
86	}	3✔
87	if (!symbolic::eq(y_dim_size, symbolic::integer(1))) {	3✔
88	if (body_users.reads(kernel->threadIdx_y()->get_name()).empty()) {	2✔
89	y_dim_available = true;	2✔
90	}	2✔
91	}	2✔
92	if (!symbolic::eq(z_dim_size, symbolic::integer(1))) {	3✔
93	if (body_users.reads(kernel->threadIdx_z()->get_name()).empty()) {	×
94	z_dim_available = true;	×
UNCOV 95	}	×
UNCOV 96	}	×
97	if (!x_dim_available && !y_dim_available && !z_dim_available) {	3✔
98	return false;	1✔
99	}
100
101	// Criterion: Unused kernel dimension is bigger or equal to loop iteration count
102	bool x_match = false;	2✔
103	bool y_match = false;	2✔
104	bool z_match = false;	2✔
105	if (x_dim_available) {	2✔
106	auto cond = symbolic::Ge(x_dim_size, iteration_count);	×
107	if (symbolic::is_true(cond)) {	×
108	x_match = true;	×
UNCOV 109	}	×
110	}	×
111	if (y_dim_available) {	2✔
112	auto cond = symbolic::Ge(y_dim_size, iteration_count);	2✔
113	if (symbolic::is_true(cond)) {	2✔
114	y_match = true;	1✔
115	}	1✔
116	}	2✔
117	if (z_dim_available) {	2✔
118	auto cond = symbolic::Ge(z_dim_size, iteration_count);	×
119	if (symbolic::is_true(cond)) {	×
120	z_match = true;	×
UNCOV 121	}	×
122	}	×
123	if (!x_match && !y_match && !z_match) {	2✔
124	return false;	1✔
125	}
126
127	// Criterion: Loop is a map
128	auto& analysis = analysis_manager.get<analysis::DataParallelismAnalysis>();	1✔
129	auto& data_dependencies = analysis.get(this->loop_);	1✔
130	for (auto& dep : data_dependencies) {	1✔
131	auto& container = dep.first;	1✔
132	auto& dep_type = dep.second;	1✔
133	if (dep_type < analysis::Parallelism::PARALLEL) {	1✔
134	return false;	1✔
135	}
136	}
137
UNCOV 138	return true;	×
139	};	3✔
140
UNCOV 141	void LoopToKernelDim::apply(Schedule& schedule) {	×
UNCOV 142	auto& analysis_manager = schedule.analysis_manager();	×
UNCOV 143	auto& builder = schedule.builder();	×
UNCOV 144	auto& sdfg = builder.subject();	×
UNCOV 145	auto& root = sdfg.root();	×
UNCOV 146	auto kernel = static_cast<const sdfg::structured_control_flow::Kernel*>(&root.at(0).first);	×
147
UNCOV 148	auto& assumptions_analysis = analysis_manager.get<analysis::AssumptionsAnalysis>();	×
UNCOV 149	auto assumptions = assumptions_analysis.get(loop_.root());	×
UNCOV 150	auto x_dim_size = assumptions[kernel->blockDim_x()].integer_value();	×
UNCOV 151	auto y_dim_size = assumptions[kernel->blockDim_y()].integer_value();	×
UNCOV 152	auto z_dim_size = assumptions[kernel->blockDim_z()].integer_value();	×
153
UNCOV 154	bool x_dim_available = false;	×
UNCOV 155	bool y_dim_available = false;	×
UNCOV 156	bool z_dim_available = false;	×
UNCOV 157	auto& users = analysis_manager.get<analysis::Users>();	×
UNCOV 158	analysis::UsersView body_users(users, loop_.root());	×
159
UNCOV 160	if (!symbolic::eq(x_dim_size, symbolic::integer(1))) {	×
UNCOV 161	if (body_users.reads(kernel->threadIdx_x()->get_name()).empty()) {	×
162	x_dim_available = true;	×
UNCOV 163	}	×
UNCOV 164	}	×
UNCOV 165	if (!symbolic::eq(y_dim_size, symbolic::integer(1))) {	×
UNCOV 166	if (body_users.reads(kernel->threadIdx_y()->get_name()).empty()) {	×
UNCOV 167	y_dim_available = true;	×
UNCOV 168	}	×
UNCOV 169	}	×
UNCOV 170	if (!symbolic::eq(z_dim_size, symbolic::integer(1))) {	×
171	if (body_users.reads(kernel->threadIdx_z()->get_name()).empty()) {	×
172	z_dim_available = true;	×
UNCOV 173	}	×
UNCOV 174	}	×
175
UNCOV 176	bool x_match = false;	×
UNCOV 177	bool y_match = false;	×
UNCOV 178	bool z_match = false;	×
UNCOV 179	symbolic::Integer iteration_count = get_iteration_count(loop_);	×
UNCOV 180	if (x_dim_available) {	×
181	auto cond = symbolic::Ge(x_dim_size, iteration_count);	×
182	if (symbolic::is_true(cond)) {	×
183	x_match = true;	×
UNCOV 184	}	×
185	}	×
UNCOV 186	if (y_dim_available) {	×
UNCOV 187	auto cond = symbolic::Ge(y_dim_size, iteration_count);	×
UNCOV 188	if (symbolic::is_true(cond)) {	×
UNCOV 189	y_match = true;	×
UNCOV 190	}	×
UNCOV 191	}	×
UNCOV 192	if (z_dim_available) {	×
193	auto cond = symbolic::Ge(z_dim_size, iteration_count);	×
194	if (symbolic::is_true(cond)) {	×
195	z_match = true;	×
UNCOV 196	}	×
197	}	×
198
UNCOV 199	auto target_dim = kernel->threadIdx_z();	×
UNCOV 200	if (x_match) {	×
201	target_dim = kernel->threadIdx_x();	×
UNCOV 202	} else if (y_match) {	×
UNCOV 203	target_dim = kernel->threadIdx_y();	×
UNCOV 204	}	×
205
UNCOV 206	auto& parent = builder.parent(loop_);	×
UNCOV 207	auto& if_else = builder.add_if_else_before(parent, loop_).first;	×
208	auto condition =
UNCOV 209	symbolic::subs(loop_.condition(), loop_.indvar(), symbolic::add(target_dim, loop_.init()));	×
UNCOV 210	auto& branch = builder.add_case(if_else, condition);	×
211
UNCOV 212	builder.insert_children(branch, loop_.root(), 0);	×
UNCOV 213	branch.replace(loop_.indvar(), symbolic::add(target_dim, loop_.init()));	×
UNCOV 214	builder.remove_child(parent, loop_);	×
215
UNCOV 216	analysis_manager.invalidate_all();	×
UNCOV 217	passes::SequenceFusion sf_pass;	×
UNCOV 218	passes::DeadCFGElimination dce_pass;	×
UNCOV 219	bool applies = false;	×
UNCOV 220	do {	×
UNCOV 221	applies = false;	×
UNCOV 222	applies \|= dce_pass.run(schedule.builder(), analysis_manager);	×
UNCOV 223	applies \|= sf_pass.run(schedule.builder(), analysis_manager);	×
UNCOV 224	} while (applies);	×
UNCOV 225	};	×
226
227	} // namespace transformations
228	} // namespace sdfg

daisytuner / sdfglib / 15049122732

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