27406975263

Committed 12 Jun 2026 09:24AM UTC coverage: 61.385% (-0.002%) from 61.387%

Build # 27406975263

Build Type

Pull #755

github

Committed by

web-flow

Commit Message

Merge e854ee324 into 620c84d46

Pull Request Pull Request #755: removes type-induced size estimation from arguments analysis

Coverage Stats

5 of 6 new or added lines in 1 file covered. (83.33%)

5 existing lines in 2 files now uncovered.

36338 of 59197 relevant lines covered (61.38%)

1119.12 hits per line

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

74.24

/sdfg/src/analysis/arguments_analysis.cpp

#include "sdfg/analysis/arguments_analysis.h"
#include "sdfg/analysis/memory_layout_analysis.h"
#include "sdfg/analysis/type_analysis.h"
#include "sdfg/analysis/users.h"
#include "sdfg/codegen/utils.h"
#include "sdfg/data_flow/library_nodes/stdlib/malloc.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
) {
    argument_sizes_.insert({&node, {}});
    argument_element_sizes_.insert({&node, {}});

    auto& memory_layout_analysis = analysis_manager.get<analysis::MemoryLayoutAnalysis>();
    auto& users = analysis_manager.get<analysis::Users>();

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

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

    for (auto& [argument, meta] : arguments) {
        if (!meta.is_scalar) {
            // Check if a Malloc node provides a known host allocation size
            symbolic::Expression malloc_size = SymEngine::null;
            for (auto* user : users.writes(argument)) {
                auto* access_node = dynamic_cast<data_flow::AccessNode*>(user->element());
                if (!access_node) continue;
                auto& graph = access_node->get_parent();
                for (auto& iedge : graph.in_edges(*access_node)) {
                    auto* malloc_node = dynamic_cast<const stdlib::MallocNode*>(&iedge.src());
                    if (!malloc_node) continue;
                    malloc_size = malloc_node->size();
                    break;
                }
                if (!malloc_size.is_null()) break;
            }

            // If malloc size is known, use it directly — skip range analysis
            if (!malloc_size.is_null()) {
                auto base_type = type_analysis.get_outer_type(argument);
                auto elem_size = types::get_contiguous_element_size(*base_type, true);
                argument_sizes_.at(&node).insert({argument, malloc_size});
                argument_element_sizes_.at(&node).insert({argument, elem_size});
                continue;
            }

            auto tile = memory_layout_analysis.tile(node, argument);
            if (tile == nullptr) {
                if (do_not_throw) {
                    known_sizes_.insert({&node, false});
                    return;
                } else {
                    throw std::runtime_error("Tile not found for " + argument);
                }
            }
            auto range = tile->contiguous_range();
            // contiguous_range returns {null, null} when the tile's extent would depend on
            // an unbounded leading dimension; treat that as "size unknown" rather than
            // dereferencing a null expression.
            if (range.first.is_null() || range.second.is_null()) {
                if (do_not_throw) {
                    known_sizes_.insert({&node, false});
                    return;
                } else {
                    throw std::runtime_error("Tile size unknown (unbounded dimension) for " + argument);
                }
            }
            symbolic::Expression size = range.second;
            size = symbolic::add(size, symbolic::one()); // Inclusive range, so add 1

            auto base_type = type_analysis.get_outer_type(argument);
            auto elem_size = types::get_contiguous_element_size(*base_type, true);
            if (elem_size.is_null()) {
                if (do_not_throw) {
                    known_sizes_.insert({&node, false});
                    return;
                } else {
                    throw std::runtime_error("Could not determine element size for " + argument);
                }
            }
            size = symbolic::mul(size, elem_size);
            DEBUG_PRINTLN("Size of " << argument << " is " << size->__str__());

            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/memory_layout_analysis.h"
3	#include "sdfg/analysis/type_analysis.h"
4	#include "sdfg/analysis/users.h"
5	#include "sdfg/codegen/utils.h"
6	#include "sdfg/data_flow/library_nodes/stdlib/malloc.h"
7	#include "sdfg/helpers/helpers.h"
8	#include "sdfg/types/utils.h"
9
10	namespace sdfg {
11	namespace analysis {
12
13	void ArgumentsAnalysis::find_arguments_and_locals(
14	analysis::AnalysisManager& analysis_manager, structured_control_flow::ControlFlowNode& node
15	) {	130✔
16	auto& users = analysis_manager.get<analysis::Users>();	130✔
17	analysis::UsersView scope_users(users, node);	130✔
18
19	analysis::TypeAnalysis type_analysis(sdfg_, &node, analysis_manager);	130✔
20
21	std::unordered_map<std::string, DataRwFlags> all_containers;	130✔
22	for (auto& user : scope_users.uses()) {	1,780✔
23	if (user->container() == symbolic::__nullptr__()->get_name()) {	1,780✔
24	continue;	×
25	}	×
26
27	DataRwFlags meta;	1,780✔
28	switch (user->use()) {	1,780✔
29	case analysis::READ:	1,225✔
30	meta.found_explicit_read();	1,225✔
31	break;	1,225✔
32	case analysis::WRITE:	555✔
33	meta.found_explicit_write();	555✔
34	break;	555✔
35	case analysis::MOVE:	×
36	case analysis::VIEW:	×
37	default:	×
38	meta.found_analysis_escape();	×
39	}	1,780✔
40	auto it = all_containers.insert({user->container(), meta});	1,780✔
41	if (!it.second) {	1,780✔
42	it.first->second.merge(meta);	1,163✔
43	}	1,163✔
44	}	1,780✔
45
46	bool inferred_types = true;	130✔
47	std::map<std::string, RegionArgument> arguments;	130✔
48	std::unordered_set<std::string> locals;	130✔
49	for (auto& [container, rwFlags] : all_containers) {	617✔
50	bool is_scalar = false;	617✔
51	bool is_ptr = false;	617✔
52
53	auto type = type_analysis.get_outer_type(container);	617✔
54	if (type == nullptr) {	617✔
55	inferred_types = false;	×
56	is_ptr = true;	×
57	is_scalar = false;	×
58	} else {	617✔
59	// Unwrap Reference types to check the underlying type
60	const types::IType* effective_type = type;	617✔
61	if (type->type_id() == types::TypeID::Reference) {	617✔
62	auto* reference = dynamic_cast<const codegen::Reference*>(type);	4✔
63	assert(reference != nullptr);	4✔
64	effective_type = &reference->reference_type();	4✔
65	}	4✔
66	is_scalar = effective_type->type_id() == types::TypeID::Scalar;	617✔
67	is_ptr = effective_type->type_id() == types::TypeID::Pointer \|\|	617✔
68	effective_type->type_id() == types::TypeID::Array;	617✔
69	}	617✔
70
71	if (sdfg_.is_argument(container) \|\| sdfg_.is_external(container)) {	617✔
72	arguments.insert({container, {rwFlags, is_scalar, is_ptr}});	288✔
73	continue;	288✔
74	}	288✔
75
76	size_t total_uses = users.uses(container).size();	329✔
77	size_t scope_uses = scope_users.uses(container).size();	329✔
78
79	if (scope_uses < total_uses) {	329✔
80	arguments.insert({container, {rwFlags, is_scalar, is_ptr}});	91✔
81	} else {	238✔
82	locals.insert(container);	238✔
83	}	238✔
84	}	329✔
85
86	node_arguments_.insert({&node, arguments});	130✔
87	node_locals_.insert({&node, locals});	130✔
88	node_inferred_types_.insert({&node, inferred_types});	130✔
89	}	130✔
90
91	void ArgumentsAnalysis::collect_arg_sizes(
92	analysis::AnalysisManager& analysis_manager,
93	structured_control_flow::ControlFlowNode& node,
94	bool allow_dynamic_sizes_,
95	bool do_not_throw
96	) {	19✔
97	argument_sizes_.insert({&node, {}});	19✔
98	argument_element_sizes_.insert({&node, {}});	19✔
99
100	auto& memory_layout_analysis = analysis_manager.get<analysis::MemoryLayoutAnalysis>();	19✔
101	auto& users = analysis_manager.get<analysis::Users>();	19✔
102
103	auto arguments = this->arguments(analysis_manager, node);	19✔
104	auto locals = this->locals(analysis_manager, node);	19✔
105
106	analysis::TypeAnalysis type_analysis(sdfg_, &node, analysis_manager);	19✔
107
108	for (auto& [argument, meta] : arguments) {	29✔
109	if (!meta.is_scalar) {	29✔
110	// Check if a Malloc node provides a known host allocation size
111	symbolic::Expression malloc_size = SymEngine::null;	14✔
112	for (auto* user : users.writes(argument)) {	14✔
113	auto* access_node = dynamic_cast<data_flow::AccessNode*>(user->element());	10✔
114	if (!access_node) continue;	10✔
115	auto& graph = access_node->get_parent();	10✔
116	for (auto& iedge : graph.in_edges(*access_node)) {	10✔
117	auto* malloc_node = dynamic_cast<const stdlib::MallocNode*>(&iedge.src());	10✔
118	if (!malloc_node) continue;	10✔
119	malloc_size = malloc_node->size();	×
120	break;	×
121	}	10✔
122	if (!malloc_size.is_null()) break;	10✔
123	}	10✔
124
125	// If malloc size is known, use it directly — skip range analysis
126	if (!malloc_size.is_null()) {	14✔
127	auto base_type = type_analysis.get_outer_type(argument);	×
128	auto elem_size = types::get_contiguous_element_size(*base_type, true);	×
129	argument_sizes_.at(&node).insert({argument, malloc_size});	×
130	argument_element_sizes_.at(&node).insert({argument, elem_size});	×
131	continue;	×
132	}	×
133
134	auto tile = memory_layout_analysis.tile(node, argument);	14✔
135	if (tile == nullptr) {	14✔
136	if (do_not_throw) {	2✔
137	known_sizes_.insert({&node, false});	2✔
138	return;	2✔
139	} else {	2✔
140	throw std::runtime_error("Tile not found for " + argument);	×
141	}	×
142	}	2✔
143	auto range = tile->contiguous_range();	12✔
144	// contiguous_range returns {null, null} when the tile's extent would depend on
145	// an unbounded leading dimension; treat that as "size unknown" rather than
146	// dereferencing a null expression.
147	if (range.first.is_null() \|\| range.second.is_null()) {	12✔
148	if (do_not_throw) {	×
149	known_sizes_.insert({&node, false});	×
150	return;	×
151	} else {	×
152	throw std::runtime_error("Tile size unknown (unbounded dimension) for " + argument);	×
153	}	×
154	}	×
155	symbolic::Expression size = range.second;	12✔
156	size = symbolic::add(size, symbolic::one()); // Inclusive range, so add 1	12✔
157
158	auto base_type = type_analysis.get_outer_type(argument);	12✔
159	auto elem_size = types::get_contiguous_element_size(*base_type, true);	12✔
160	if (elem_size.is_null()) {	12✔
UNCOV 161	if (do_not_throw) {	×
162	known_sizes_.insert({&node, false});	×
163	return;	×
164	} else {	×
NEW 165	throw std::runtime_error("Could not determine element size for " + argument);	×
166	}	×
UNCOV 167	}	×
168	size = symbolic::mul(size, elem_size);	12✔
169	DEBUG_PRINTLN("Size of " << argument << " is " << size->__str__());	12✔
170
171	argument_sizes_.at(&node).insert({argument, size});	12✔
172	argument_element_sizes_.at(&node).insert({argument, elem_size});	12✔
173	} else {	15✔
174	auto type = type_analysis.get_outer_type(argument);	15✔
175	if (type == nullptr) {	15✔
176	if (do_not_throw) {	×
177	known_sizes_.insert({&node, false});	×
178	return;	×
179	} else {	×
180	throw std::runtime_error("Could not infer type for argument: " + argument);	×
181	}	×
182	}	×
183	DEBUG_PRINTLN("type of argument: " << type->print());	15✔
184	auto size = types::get_contiguous_element_size(*type);	15✔
185	DEBUG_PRINTLN("Size of " << argument << " is " << size->__str__());	15✔
186	argument_sizes_.at(&node).insert({argument, size});	15✔
187	argument_element_sizes_.at(&node).insert({argument, size});	15✔
188	}	15✔
189	}	29✔
190
191	known_sizes_.insert({&node, true});	17✔
192	}	17✔
193
194	ArgumentsAnalysis::ArgumentsAnalysis(StructuredSDFG& sdfg) : Analysis(sdfg) {}	80✔
195
196	void ArgumentsAnalysis::run(analysis::AnalysisManager& analysis_manager) {}	80✔
197
198	const std::map<std::string, RegionArgument>& ArgumentsAnalysis::
199	arguments(analysis::AnalysisManager& analysis_manager, structured_control_flow::ControlFlowNode& node) {	155✔
200	if (node_arguments_.find(&node) != node_arguments_.end()) {	155✔
201	return node_arguments_.at(&node);	46✔
202	} else {	109✔
203	find_arguments_and_locals(analysis_manager, node);	109✔
204	return node_arguments_.at(&node);	109✔
205	}	109✔
206	}	155✔
207
208	const std::unordered_set<std::string>& ArgumentsAnalysis::
209	locals(analysis::AnalysisManager& analysis_manager, structured_control_flow::ControlFlowNode& node) {	44✔
210	if (node_locals_.find(&node) != node_locals_.end()) {	44✔
211	return node_locals_.at(&node);	44✔
212	} else {	44✔
213	find_arguments_and_locals(analysis_manager, node);	×
214	return node_locals_.at(&node);	×
215	}	×
216	}	44✔
217
218	bool ArgumentsAnalysis::
219	inferred_types(analysis::AnalysisManager& analysis_manager, structured_control_flow::ControlFlowNode& node) {	21✔
220	if (node_inferred_types_.find(&node) != node_inferred_types_.end()) {	21✔
221	return node_inferred_types_.at(&node);	×
222	} else {	21✔
223	find_arguments_and_locals(analysis_manager, node);	21✔
224	return node_inferred_types_.at(&node);	21✔
225	}	21✔
226	}	21✔
227
228	const std::unordered_map<std::string, symbolic::Expression>& ArgumentsAnalysis::argument_sizes(
229	analysis::AnalysisManager& analysis_manager,
230	structured_control_flow::ControlFlowNode& node,
231	bool allow_dynamic_sizes_
232	) {	17✔
233	if (argument_sizes_.find(&node) != argument_sizes_.end() && known_sizes_.at(&node)) {	17✔
234	return argument_sizes_.at(&node);	17✔
235	} else {	17✔
236	collect_arg_sizes(analysis_manager, node, allow_dynamic_sizes_, false);	×
237	return argument_sizes_.at(&node);	×
238	}	×
239	}	17✔
240
241	const std::unordered_map<std::string, symbolic::Expression>& ArgumentsAnalysis::argument_element_sizes(
242	analysis::AnalysisManager& analysis_manager,
243	structured_control_flow::ControlFlowNode& node,
244	bool allow_dynamic_sizes_
245	) {	1✔
246	if (argument_element_sizes_.find(&node) != argument_element_sizes_.end() && known_sizes_.at(&node)) {	1✔
247	return argument_element_sizes_.at(&node);	1✔
248	} else {	1✔
249	collect_arg_sizes(analysis_manager, node, allow_dynamic_sizes_, false);	×
250	return argument_element_sizes_.at(&node);	×
251	}	×
252	}	1✔
253
254	bool ArgumentsAnalysis::argument_size_known(
255	analysis::AnalysisManager& analysis_manager,
256	structured_control_flow::ControlFlowNode& node,
257	bool allow_dynamic_sizes_
258	) {	19✔
259	if (known_sizes_.find(&node) != known_sizes_.end()) {	19✔
260	return known_sizes_.at(&node);	×
261	} else {	19✔
262	collect_arg_sizes(analysis_manager, node, allow_dynamic_sizes_, true);	19✔
263	return known_sizes_.at(&node);	19✔
264	}	19✔
265	}	19✔
266
267	} // namespace analysis
268	} // namespace sdfg

daisytuner / docc / 27406975263

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