23906044628

Committed 02 Apr 2026 02:40PM UTC coverage: 64.553% (+0.08%) from 64.474%

Build # 23906044628

Build Type

Pull #632

github

Committed by

web-flow

Commit Message

Merge b2698daab into 3125b927b

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

Run Details

282 of 348 new or added lines in 16 files covered. (81.03%)

29 existing lines in 10 files now uncovered.

28998 of 44921 relevant lines covered (64.55%)

453.01 hits per line

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

71.03

/sdfg/src/analysis/arguments_analysis.cpp

#include "sdfg/analysis/arguments_analysis.h"
#include "sdfg/analysis/mem_access_range_analysis.h"
#include "sdfg/analysis/type_analysis.h"
#include "sdfg/analysis/users.h"
#include "sdfg/codegen/utils.h"
#include "sdfg/helpers/helpers.h"
#include "sdfg/types/utils.h"

namespace sdfg {
namespace analysis {

void ArgumentsAnalysis::find_arguments_and_locals(
    analysis::AnalysisManager& analysis_manager, structured_control_flow::ControlFlowNode& node
) {
    auto& users = analysis_manager.get<analysis::Users>();
    analysis::UsersView scope_users(users, node);

    analysis::TypeAnalysis type_analysis(sdfg_, &node, analysis_manager);

    std::unordered_map<std::string, DataRwFlags> all_containers;
    for (auto& user : scope_users.uses()) {
        if (user->container() == symbolic::__nullptr__()->get_name()) {
            continue;
        }

        DataRwFlags meta;
        switch (user->use()) {
            case analysis::READ:
                meta.found_explicit_read();
                break;
            case analysis::WRITE:
                meta.found_explicit_write();
                break;
            case analysis::MOVE:
            case analysis::VIEW:
            default:
                meta.found_analysis_escape();
        }
        auto it = all_containers.insert({user->container(), meta});
        if (!it.second) {
            it.first->second.merge(meta);
        }
    }

    bool inferred_types = true;
    std::map<std::string, RegionArgument> arguments;
    std::unordered_set<std::string> locals;
    for (auto& [container, rwFlags] : all_containers) {
        bool is_scalar = false;
        bool is_ptr = false;

        auto type = type_analysis.get_outer_type(container);
        if (type == nullptr) {
            inferred_types = false;
            is_ptr = true;
            is_scalar = false;
        } else {
            // Unwrap Reference types to check the underlying type
            const types::IType* effective_type = type;
            if (type->type_id() == types::TypeID::Reference) {
                auto* reference = dynamic_cast<const codegen::Reference*>(type);
                assert(reference != nullptr);
                effective_type = &reference->reference_type();
            }
            is_scalar = effective_type->type_id() == types::TypeID::Scalar;
            is_ptr = effective_type->type_id() == types::TypeID::Pointer ||
                     effective_type->type_id() == types::TypeID::Array;
        }

        if (sdfg_.is_argument(container) || sdfg_.is_external(container)) {
            arguments.insert({container, {rwFlags, is_scalar, is_ptr}});
            continue;
        }

        size_t total_uses = users.uses(container).size();
        size_t scope_uses = scope_users.uses(container).size();

        if (scope_uses < total_uses) {
            arguments.insert({container, {rwFlags, is_scalar, is_ptr}});
        } else {
            locals.insert(container);
        }
    }

    node_arguments_.insert({&node, arguments});
    node_locals_.insert({&node, locals});
    node_inferred_types_.insert({&node, inferred_types});
}

void ArgumentsAnalysis::collect_arg_sizes(
    analysis::AnalysisManager& analysis_manager,
    structured_control_flow::ControlFlowNode& node,
    bool allow_dynamic_sizes_,
    bool do_not_throw
) {
    std::unordered_set<std::string> internal_vars;
    argument_sizes_.insert({&node, {}});
    argument_element_sizes_.insert({&node, {}});

    auto& mem_access_ranges = analysis_manager.get<analysis::MemAccessRanges>();

    auto arguments = this->arguments(analysis_manager, node);
    auto locals = this->locals(analysis_manager, node);

    internal_vars.insert(locals.begin(), locals.end());
    std::ranges::for_each(arguments, [&internal_vars](const auto& pair) { internal_vars.insert(pair.first); });

    analysis::TypeAnalysis type_analysis(sdfg_, &node, analysis_manager);

    for (auto& [argument, meta] : arguments) {
        if (!meta.is_scalar) {
            auto range = mem_access_ranges.get(argument, node, internal_vars);
            if (range == nullptr) {
                if (do_not_throw) {
                    known_sizes_.insert({&node, false});
                    return;
                } else {
                    throw std::runtime_error("Range not found for " + argument);
                }
            }
            auto base_type = type_analysis.get_outer_type(argument);
            auto elem_size = types::get_contiguous_element_size(*base_type, true);
            if (range->is_undefined()) {
                if (!allow_dynamic_sizes_) {
                    if (do_not_throw) {
                        known_sizes_.insert({&node, false});
                        return;
                    } else {
                        throw std::runtime_error("Argument " + argument + " has undefined range");
                    }
                }
                DEBUG_PRINTLN("Argument " << argument << " has undefined range, using malloc_usable_size");
                argument_sizes_.at(&node).insert({argument, symbolic::malloc_usable_size(symbolic::symbol(argument))});
                argument_element_sizes_.at(&node).insert({argument, elem_size});
                continue;
            }

            symbolic::Expression size = symbolic::one();
            if (!range->dims().empty()) {
                size = symbolic::add(range->dims().at(0).second, symbolic::one());
            }

            bool is_nested_type = true;
            auto peeled_type = types::peel_to_next_element(*base_type);
            while (is_nested_type) {
                if (peeled_type == nullptr) {
                    if (do_not_throw) {
                        known_sizes_.insert({&node, false});
                        return;
                    } else {
                        throw std::runtime_error("Could not infer type for argument: " + argument);
                    }
                }
                if (peeled_type->type_id() == types::TypeID::Array) {
                    auto array_type = dynamic_cast<const types::Array*>(peeled_type);
                    size = symbolic::mul(size, array_type->num_elements());
                    peeled_type = &array_type->element_type();
                } else if (peeled_type->type_id() == types::TypeID::Pointer) {
                    if (do_not_throw) {
                        known_sizes_.insert({&node, false});
                        return;
                    } else {
                        throw std::runtime_error("Non-contiguous pointer type: " + argument);
                    }
                } else {
                    is_nested_type = false;
                }
            }


            size = symbolic::mul(size, elem_size);
            DEBUG_PRINTLN("Size of " << argument << " is " << size->__str__());
            if (size.is_null()) {
                if (do_not_throw) {
                    known_sizes_.insert({&node, false});
                    return;
                } else {
                    throw std::runtime_error("Cannot figure out access size of " + argument);
                }
            } else {
                argument_sizes_.at(&node).insert({argument, size});
                argument_element_sizes_.at(&node).insert({argument, elem_size});
            }
        } else {
            auto type = type_analysis.get_outer_type(argument);
            if (type == nullptr) {
                if (do_not_throw) {
                    known_sizes_.insert({&node, false});
                    return;
                } else {
                    throw std::runtime_error("Could not infer type for argument: " + argument);
                }
            }
            DEBUG_PRINTLN("type of argument: " << type->print());
            auto size = types::get_contiguous_element_size(*type);
            DEBUG_PRINTLN("Size of " << argument << " is " << size->__str__());
            argument_sizes_.at(&node).insert({argument, size});
            argument_element_sizes_.at(&node).insert({argument, size});
        }
    }

    known_sizes_.insert({&node, true});
}

ArgumentsAnalysis::ArgumentsAnalysis(StructuredSDFG& sdfg) : Analysis(sdfg) {}

void ArgumentsAnalysis::run(analysis::AnalysisManager& analysis_manager) {}

const std::map<std::string, RegionArgument>& ArgumentsAnalysis::
    arguments(analysis::AnalysisManager& analysis_manager, structured_control_flow::ControlFlowNode& node) {
    if (node_arguments_.find(&node) != node_arguments_.end()) {
        return node_arguments_.at(&node);
    } else {
        find_arguments_and_locals(analysis_manager, node);
        return node_arguments_.at(&node);
    }
}

const std::unordered_set<std::string>& ArgumentsAnalysis::
    locals(analysis::AnalysisManager& analysis_manager, structured_control_flow::ControlFlowNode& node) {
    if (node_locals_.find(&node) != node_locals_.end()) {
        return node_locals_.at(&node);
    } else {
        find_arguments_and_locals(analysis_manager, node);
        return node_locals_.at(&node);
    }
}

bool ArgumentsAnalysis::
    inferred_types(analysis::AnalysisManager& analysis_manager, structured_control_flow::ControlFlowNode& node) {
    if (node_inferred_types_.find(&node) != node_inferred_types_.end()) {
        return node_inferred_types_.at(&node);
    } else {
        find_arguments_and_locals(analysis_manager, node);
        return node_inferred_types_.at(&node);
    }
}

const std::unordered_map<std::string, symbolic::Expression>& ArgumentsAnalysis::argument_sizes(
    analysis::AnalysisManager& analysis_manager,
    structured_control_flow::ControlFlowNode& node,
    bool allow_dynamic_sizes_
) {
    if (argument_sizes_.find(&node) != argument_sizes_.end() && known_sizes_.at(&node)) {
        return argument_sizes_.at(&node);
    } else {
        collect_arg_sizes(analysis_manager, node, allow_dynamic_sizes_, false);
        return argument_sizes_.at(&node);
    }
}

const std::unordered_map<std::string, symbolic::Expression>& ArgumentsAnalysis::argument_element_sizes(
    analysis::AnalysisManager& analysis_manager,
    structured_control_flow::ControlFlowNode& node,
    bool allow_dynamic_sizes_
) {
    if (argument_element_sizes_.find(&node) != argument_element_sizes_.end() && known_sizes_.at(&node)) {
        return argument_element_sizes_.at(&node);
    } else {
        collect_arg_sizes(analysis_manager, node, allow_dynamic_sizes_, false);
        return argument_element_sizes_.at(&node);
    }
}

bool ArgumentsAnalysis::argument_size_known(
    analysis::AnalysisManager& analysis_manager,
    structured_control_flow::ControlFlowNode& node,
    bool allow_dynamic_sizes_
) {
    if (known_sizes_.find(&node) != known_sizes_.end()) {
        return known_sizes_.at(&node);
    } else {
        collect_arg_sizes(analysis_manager, node, allow_dynamic_sizes_, true);
        return known_sizes_.at(&node);
    }
}

} // namespace analysis
} // namespace sdfg

1	#include "sdfg/analysis/arguments_analysis.h"
2	#include "sdfg/analysis/mem_access_range_analysis.h"
3	#include "sdfg/analysis/type_analysis.h"
4	#include "sdfg/analysis/users.h"
5	#include "sdfg/codegen/utils.h"
6	#include "sdfg/helpers/helpers.h"
7	#include "sdfg/types/utils.h"
8
9	namespace sdfg {
10	namespace analysis {
11
12	void ArgumentsAnalysis::find_arguments_and_locals(
13	analysis::AnalysisManager& analysis_manager, structured_control_flow::ControlFlowNode& node
14	) {	100✔
15	auto& users = analysis_manager.get<analysis::Users>();	100✔
16	analysis::UsersView scope_users(users, node);	100✔
17
18	analysis::TypeAnalysis type_analysis(sdfg_, &node, analysis_manager);	100✔
19
20	std::unordered_map<std::string, DataRwFlags> all_containers;	100✔
21	for (auto& user : scope_users.uses()) {	1,038✔
22	if (user->container() == symbolic::__nullptr__()->get_name()) {	1,038✔
23	continue;	×
24	}	×
25
26	DataRwFlags meta;	1,038✔
27	switch (user->use()) {	1,038✔
28	case analysis::READ:	689✔
29	meta.found_explicit_read();	689✔
30	break;	689✔
31	case analysis::WRITE:	346✔
32	meta.found_explicit_write();	346✔
33	break;	346✔
34	case analysis::MOVE:	2✔
35	case analysis::VIEW:	3✔
36	default:	3✔
37	meta.found_analysis_escape();	3✔
38	}	1,038✔
39	auto it = all_containers.insert({user->container(), meta});	1,038✔
40	if (!it.second) {	1,038✔
41	it.first->second.merge(meta);	633✔
42	}	633✔
43	}	1,038✔
44
45	bool inferred_types = true;	100✔
46	std::map<std::string, RegionArgument> arguments;	100✔
47	std::unordered_set<std::string> locals;	100✔
48	for (auto& [container, rwFlags] : all_containers) {	405✔
49	bool is_scalar = false;	405✔
50	bool is_ptr = false;	405✔
51
52	auto type = type_analysis.get_outer_type(container);	405✔
53	if (type == nullptr) {	405✔
54	inferred_types = false;	×
55	is_ptr = true;	×
56	is_scalar = false;	×
57	} else {	405✔
58	// Unwrap Reference types to check the underlying type
59	const types::IType* effective_type = type;	405✔
60	if (type->type_id() == types::TypeID::Reference) {	405✔
61	auto* reference = dynamic_cast<const codegen::Reference*>(type);	4✔
62	assert(reference != nullptr);	4✔
63	effective_type = &reference->reference_type();	4✔
64	}	4✔
65	is_scalar = effective_type->type_id() == types::TypeID::Scalar;	405✔
66	is_ptr = effective_type->type_id() == types::TypeID::Pointer \|\|	405✔
67	effective_type->type_id() == types::TypeID::Array;	405✔
68	}	405✔
69
70	if (sdfg_.is_argument(container) \|\| sdfg_.is_external(container)) {	405✔
71	arguments.insert({container, {rwFlags, is_scalar, is_ptr}});	196✔
72	continue;	196✔
73	}	196✔
74
75	size_t total_uses = users.uses(container).size();	209✔
76	size_t scope_uses = scope_users.uses(container).size();	209✔
77
78	if (scope_uses < total_uses) {	209✔
79	arguments.insert({container, {rwFlags, is_scalar, is_ptr}});	70✔
80	} else {	139✔
81	locals.insert(container);	139✔
82	}	139✔
83	}	209✔
84
85	node_arguments_.insert({&node, arguments});	100✔
86	node_locals_.insert({&node, locals});	100✔
87	node_inferred_types_.insert({&node, inferred_types});	100✔
88	}	100✔
89
90	void ArgumentsAnalysis::collect_arg_sizes(
91	analysis::AnalysisManager& analysis_manager,
92	structured_control_flow::ControlFlowNode& node,
93	bool allow_dynamic_sizes_,
94	bool do_not_throw
95	) {	17✔
96	std::unordered_set<std::string> internal_vars;	17✔
97	argument_sizes_.insert({&node, {}});	17✔
98	argument_element_sizes_.insert({&node, {}});	17✔
99
100	auto& mem_access_ranges = analysis_manager.get<analysis::MemAccessRanges>();	17✔
101
102	auto arguments = this->arguments(analysis_manager, node);	17✔
103	auto locals = this->locals(analysis_manager, node);	17✔
104
105	internal_vars.insert(locals.begin(), locals.end());	17✔
106	std::ranges::for_each(arguments, [&internal_vars](const auto& pair) { internal_vars.insert(pair.first); });	23✔
107
108	analysis::TypeAnalysis type_analysis(sdfg_, &node, analysis_manager);	17✔
109
110	for (auto& [argument, meta] : arguments) {	23✔
111	if (!meta.is_scalar) {	23✔
112	auto range = mem_access_ranges.get(argument, node, internal_vars);	10✔
113	if (range == nullptr) {	10✔
114	if (do_not_throw) {	×
115	known_sizes_.insert({&node, false});	×
116	return;	×
117	} else {	×
118	throw std::runtime_error("Range not found for " + argument);	×
119	}	×
120	}	×
121	auto base_type = type_analysis.get_outer_type(argument);	10✔
122	auto elem_size = types::get_contiguous_element_size(*base_type, true);	10✔
123	if (range->is_undefined()) {	10✔
124	if (!allow_dynamic_sizes_) {	×
125	if (do_not_throw) {	×
126	known_sizes_.insert({&node, false});	×
127	return;	×
128	} else {	×
129	throw std::runtime_error("Argument " + argument + " has undefined range");	×
130	}	×
131	}	×
132	DEBUG_PRINTLN("Argument " << argument << " has undefined range, using malloc_usable_size");	×
133	argument_sizes_.at(&node).insert({argument, symbolic::malloc_usable_size(symbolic::symbol(argument))});	×
134	argument_element_sizes_.at(&node).insert({argument, elem_size});	×
135	continue;	×
136	}	×
137
138	symbolic::Expression size = symbolic::one();	10✔
139	if (!range->dims().empty()) {	10✔
140	size = symbolic::add(range->dims().at(0).second, symbolic::one());	10✔
141	}	10✔
142
143	bool is_nested_type = true;	10✔
144	auto peeled_type = types::peel_to_next_element(*base_type);	10✔
145	while (is_nested_type) {	22✔
146	if (peeled_type == nullptr) {	12✔
147	if (do_not_throw) {	×
148	known_sizes_.insert({&node, false});	×
149	return;	×
150	} else {	×
151	throw std::runtime_error("Could not infer type for argument: " + argument);	×
152	}	×
153	}	×
154	if (peeled_type->type_id() == types::TypeID::Array) {	12✔
155	auto array_type = dynamic_cast<const types::Array*>(peeled_type);	2✔
156	size = symbolic::mul(size, array_type->num_elements());	2✔
157	peeled_type = &array_type->element_type();	2✔
158	} else if (peeled_type->type_id() == types::TypeID::Pointer) {	10✔
159	if (do_not_throw) {	×
160	known_sizes_.insert({&node, false});	×
161	return;	×
162	} else {	×
163	throw std::runtime_error("Non-contiguous pointer type: " + argument);	×
164	}	×
165	} else {	10✔
166	is_nested_type = false;	10✔
167	}	10✔
168	}	12✔
169
170
171	size = symbolic::mul(size, elem_size);	10✔
172	DEBUG_PRINTLN("Size of " << argument << " is " << size->__str__());	10✔
173	if (size.is_null()) {	10✔
174	if (do_not_throw) {	×
175	known_sizes_.insert({&node, false});	×
176	return;	×
177	} else {	×
178	throw std::runtime_error("Cannot figure out access size of " + argument);	×
179	}	×
180	} else {	10✔
181	argument_sizes_.at(&node).insert({argument, size});	10✔
182	argument_element_sizes_.at(&node).insert({argument, elem_size});	10✔
183	}	10✔
184	} else {	13✔
185	auto type = type_analysis.get_outer_type(argument);	13✔
186	if (type == nullptr) {	13✔
187	if (do_not_throw) {	×
188	known_sizes_.insert({&node, false});	×
189	return;	×
190	} else {	×
191	throw std::runtime_error("Could not infer type for argument: " + argument);	×
192	}	×
193	}	×
194	DEBUG_PRINTLN("type of argument: " << type->print());	13✔
195	auto size = types::get_contiguous_element_size(*type);	13✔
196	DEBUG_PRINTLN("Size of " << argument << " is " << size->__str__());	13✔
197	argument_sizes_.at(&node).insert({argument, size});	13✔
198	argument_element_sizes_.at(&node).insert({argument, size});	13✔
199	}	13✔
200	}	23✔
201
202	known_sizes_.insert({&node, true});	17✔
203	}	17✔
204
205	ArgumentsAnalysis::ArgumentsAnalysis(StructuredSDFG& sdfg) : Analysis(sdfg) {}	65✔
206
207	void ArgumentsAnalysis::run(analysis::AnalysisManager& analysis_manager) {}	65✔
208
209	const std::map<std::string, RegionArgument>& ArgumentsAnalysis::
210	arguments(analysis::AnalysisManager& analysis_manager, structured_control_flow::ControlFlowNode& node) {	121✔
211	if (node_arguments_.find(&node) != node_arguments_.end()) {	121✔
212	return node_arguments_.at(&node);	40✔
213	} else {	81✔
214	find_arguments_and_locals(analysis_manager, node);	81✔
215	return node_arguments_.at(&node);	81✔
216	}	81✔
217	}	121✔
218
219	const std::unordered_set<std::string>& ArgumentsAnalysis::
220	locals(analysis::AnalysisManager& analysis_manager, structured_control_flow::ControlFlowNode& node) {	52✔
221	if (node_locals_.find(&node) != node_locals_.end()) {	52✔
222	return node_locals_.at(&node);	52✔
223	} else {	52✔
224	find_arguments_and_locals(analysis_manager, node);	×
225	return node_locals_.at(&node);	×
226	}	×
227	}	52✔
228
229	bool ArgumentsAnalysis::
230	inferred_types(analysis::AnalysisManager& analysis_manager, structured_control_flow::ControlFlowNode& node) {	19✔
231	if (node_inferred_types_.find(&node) != node_inferred_types_.end()) {	19✔
232	return node_inferred_types_.at(&node);	×
233	} else {	19✔
234	find_arguments_and_locals(analysis_manager, node);	19✔
235	return node_inferred_types_.at(&node);	19✔
236	}	19✔
237	}	19✔
238
239	const std::unordered_map<std::string, symbolic::Expression>& ArgumentsAnalysis::argument_sizes(
240	analysis::AnalysisManager& analysis_manager,
241	structured_control_flow::ControlFlowNode& node,
242	bool allow_dynamic_sizes_
243	) {	19✔
244	if (argument_sizes_.find(&node) != argument_sizes_.end() && known_sizes_.at(&node)) {	19✔
245	return argument_sizes_.at(&node);	19✔
246	} else {	19✔
UNCOV 247	collect_arg_sizes(analysis_manager, node, allow_dynamic_sizes_, false);	×
UNCOV 248	return argument_sizes_.at(&node);	×
UNCOV 249	}	×
250	}	19✔
251
252	const std::unordered_map<std::string, symbolic::Expression>& ArgumentsAnalysis::argument_element_sizes(
253	analysis::AnalysisManager& analysis_manager,
254	structured_control_flow::ControlFlowNode& node,
255	bool allow_dynamic_sizes_
256	) {	1✔
257	if (argument_element_sizes_.find(&node) != argument_element_sizes_.end() && known_sizes_.at(&node)) {	1✔
258	return argument_element_sizes_.at(&node);	1✔
259	} else {	1✔
260	collect_arg_sizes(analysis_manager, node, allow_dynamic_sizes_, false);	×
261	return argument_element_sizes_.at(&node);	×
262	}	×
263	}	1✔
264
265	bool ArgumentsAnalysis::argument_size_known(
266	analysis::AnalysisManager& analysis_manager,
267	structured_control_flow::ControlFlowNode& node,
268	bool allow_dynamic_sizes_
269	) {	17✔
270	if (known_sizes_.find(&node) != known_sizes_.end()) {	17✔
271	return known_sizes_.at(&node);	×
272	} else {	17✔
273	collect_arg_sizes(analysis_manager, node, allow_dynamic_sizes_, true);	17✔
274	return known_sizes_.at(&node);	17✔
275	}	17✔
276	}	17✔
277
278	} // namespace analysis
279	} // namespace sdfg

daisytuner / docc / 23906044628

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