20687533221

Committed 03 Jan 2026 04:16PM UTC coverage: 39.64% (+0.07%) from 39.569%

Build # 20687533221

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #424 from daisytuner/copilot/add-normalize-base-type-pass

Add memlet linearization pass for flattening nested array pointers

Run Details

15089 of 49538 branches covered (30.46%)

Branch coverage included in aggregate %.

56 of 62 new or added lines in 2 files covered. (90.32%)

1 existing line in 1 file now uncovered.

12957 of 21214 relevant lines covered (61.08%)

91.56 hits per line

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

65.24

/src/passes/dataflow/memlet_linearization.cpp

#include "sdfg/passes/dataflow/memlet_linearization.h"

#include "sdfg/data_flow/data_flow_graph.h"
#include "sdfg/data_flow/memlet.h"
#include "sdfg/structured_control_flow/block.h"
#include "sdfg/symbolic/symbolic.h"
#include "sdfg/types/array.h"
#include "sdfg/types/pointer.h"
#include "sdfg/types/utils.h"
#include "sdfg/visitor/structured_sdfg_visitor.h"

namespace sdfg {
namespace passes {

MemletLinearization::
    MemletLinearization(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager)
    : visitor::NonStoppingStructuredSDFGVisitor(builder, analysis_manager) {}

bool MemletLinearization::accept(structured_control_flow::Block& block) {
    bool applied = false;
    auto& dfg = block.dataflow();

    // Collect all memlets that need linearization
    std::vector<data_flow::Memlet*> memlets_to_linearize;

    for (auto& memlet : dfg.edges()) {
        auto& base_type = memlet.base_type();

        // Check if base_type is a pointer to nested arrays
        if (base_type.type_id() != types::TypeID::Pointer) {
            continue;
        }

        auto& pointer_type = dynamic_cast<const types::Pointer&>(base_type);
        if (!pointer_type.has_pointee_type()) {
            continue;
        }

        // Check if pointee type contains arrays
        auto& pointee_type = pointer_type.pointee_type();
        const types::IType* current_type = &pointee_type;
        std::vector<symbolic::Expression> array_dimensions;

        // Collect all array dimensions
        while (current_type->type_id() == types::TypeID::Array) {
            auto array_type = dynamic_cast<const types::Array*>(current_type);
            array_dimensions.push_back(array_type->num_elements());
            current_type = &array_type->element_type();
        }

        // If we found nested arrays, mark this memlet for linearization
        if (!array_dimensions.empty()) {
            memlets_to_linearize.push_back(const_cast<data_flow::Memlet*>(&memlet));
        }
    }

    // Apply linearization to collected memlets
    for (auto* memlet : memlets_to_linearize) {
        auto& base_type = memlet->base_type();
        auto& pointer_type = dynamic_cast<const types::Pointer&>(base_type);
        auto& pointee_type = pointer_type.pointee_type();

        // Get innermost element type and collect array dimensions
        const types::IType* current_type = &pointee_type;
        std::vector<symbolic::Expression> array_dimensions;

        while (current_type->type_id() == types::TypeID::Array) {
            auto array_type = dynamic_cast<const types::Array*>(current_type);
            array_dimensions.push_back(array_type->num_elements());
            current_type = &array_type->element_type();
        }

        // Create new pointer type with innermost element type, preserving storage properties
        auto storage = pointer_type.storage_type();
        auto alignment = pointer_type.alignment();
        auto initializer = pointer_type.initializer();
        types::Pointer new_pointer_type(storage, alignment, initializer, *current_type);

        // Linearize subset
        auto old_subset = memlet->subset();
        data_flow::Subset new_subset;

        // If subset is empty or doesn't match array dimensions, keep it as is
        if (!old_subset.empty() && old_subset.size() <= array_dimensions.size()) {
            // Calculate linearized index: idx = i0 * (d1 * d2 * ... * dn-1) + i1 * (d2 * ... * dn-1) + ... + in-1
            symbolic::Expression linearized_index = symbolic::zero();

            for (size_t i = 0; i < old_subset.size(); ++i) {
                symbolic::Expression stride = symbolic::one();

                // Calculate stride: product of all dimensions after current dimension
                for (size_t j = i + 1; j < array_dimensions.size(); ++j) {
                    stride = symbolic::mul(stride, array_dimensions[j]);
                }

                linearized_index = symbolic::add(linearized_index, symbolic::mul(old_subset[i], stride));
            }

            new_subset.push_back(linearized_index);

            // Keep any remaining subset dimensions that were beyond the array dimensions.
            // This handles cases where the subset has more dimensions than the flattened array,
            // which can occur when the pointee contains additional structure after the arrays.
            for (size_t i = array_dimensions.size(); i < old_subset.size(); ++i) {
                new_subset.push_back(old_subset[i]);
            }
        } else {
            // Keep original subset if it doesn't fit the pattern
            new_subset = old_subset;
        }

        // Update memlet with new base type and subset
        memlet->set_base_type(new_pointer_type);
        memlet->set_subset(new_subset);

        applied = true;
    }

    return applied;
}

} // namespace passes
} // namespace sdfg

1	#include "sdfg/passes/dataflow/memlet_linearization.h"
2
3	#include "sdfg/data_flow/data_flow_graph.h"
4	#include "sdfg/data_flow/memlet.h"
5	#include "sdfg/structured_control_flow/block.h"
6	#include "sdfg/symbolic/symbolic.h"
7	#include "sdfg/types/array.h"
8	#include "sdfg/types/pointer.h"
9	#include "sdfg/types/utils.h"
10	#include "sdfg/visitor/structured_sdfg_visitor.h"
11
12	namespace sdfg {
13	namespace passes {
14
15	MemletLinearization::
16	MemletLinearization(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager)	6✔
17	: visitor::NonStoppingStructuredSDFGVisitor(builder, analysis_manager) {}	6✔
18
19	bool MemletLinearization::accept(structured_control_flow::Block& block) {	6✔
20	bool applied = false;	6✔
21	auto& dfg = block.dataflow();	6✔
22
23	// Collect all memlets that need linearization
24	std::vector<data_flow::Memlet*> memlets_to_linearize;	6✔
25
26	for (auto& memlet : dfg.edges()) {	12!
27	auto& base_type = memlet.base_type();	6!
28
29	// Check if base_type is a pointer to nested arrays
30	if (base_type.type_id() != types::TypeID::Pointer) {	6!
NEW 31	continue;	×
32	}
33
34	auto& pointer_type = dynamic_cast<const types::Pointer&>(base_type);	6!
35	if (!pointer_type.has_pointee_type()) {	6!
NEW 36	continue;	×
37	}
38
39	// Check if pointee type contains arrays
40	auto& pointee_type = pointer_type.pointee_type();	6!
41	const types::IType* current_type = &pointee_type;	6✔
42	std::vector<symbolic::Expression> array_dimensions;	6✔
43
44	// Collect all array dimensions
45	while (current_type->type_id() == types::TypeID::Array) {	17!
46	auto array_type = dynamic_cast<const types::Array*>(current_type);	11!
47	array_dimensions.push_back(array_type->num_elements());	11!
48	current_type = &array_type->element_type();	11!
49	}
50
51	// If we found nested arrays, mark this memlet for linearization
52	if (!array_dimensions.empty()) {	6✔
53	memlets_to_linearize.push_back(const_cast<data_flow::Memlet*>(&memlet));	5!
54	}	5✔
55	}	6✔
56
57	// Apply linearization to collected memlets
58	for (auto* memlet : memlets_to_linearize) {	11✔
59	auto& base_type = memlet->base_type();	5!
60	auto& pointer_type = dynamic_cast<const types::Pointer&>(base_type);	5!
61	auto& pointee_type = pointer_type.pointee_type();	5!
62
63	// Get innermost element type and collect array dimensions
64	const types::IType* current_type = &pointee_type;	5✔
65	std::vector<symbolic::Expression> array_dimensions;	5✔
66
67	while (current_type->type_id() == types::TypeID::Array) {	16!
68	auto array_type = dynamic_cast<const types::Array*>(current_type);	11!
69	array_dimensions.push_back(array_type->num_elements());	11!
70	current_type = &array_type->element_type();	11!
71	}
72
73	// Create new pointer type with innermost element type, preserving storage properties
74	auto storage = pointer_type.storage_type();	5!
75	auto alignment = pointer_type.alignment();	5!
76	auto initializer = pointer_type.initializer();	5!
77	types::Pointer new_pointer_type(storage, alignment, initializer, *current_type);	5!
78
79	// Linearize subset
80	auto old_subset = memlet->subset();	5!
81	data_flow::Subset new_subset;	5✔
82
83	// If subset is empty or doesn't match array dimensions, keep it as is
84	if (!old_subset.empty() && old_subset.size() <= array_dimensions.size()) {	5!
85	// Calculate linearized index: idx = i0 * (d1 * d2 * ... * dn-1) + i1 * (d2 * ... * dn-1) + ... + in-1
86	symbolic::Expression linearized_index = symbolic::zero();	5!
87
88	for (size_t i = 0; i < old_subset.size(); ++i) {	14✔
89	symbolic::Expression stride = symbolic::one();	9!
90
91	// Calculate stride: product of all dimensions after current dimension
92	for (size_t j = i + 1; j < array_dimensions.size(); ++j) {	16✔
93	stride = symbolic::mul(stride, array_dimensions[j]);	7!
94	}	7✔
95
96	linearized_index = symbolic::add(linearized_index, symbolic::mul(old_subset[i], stride));	9!
97	}	9✔
98
99	new_subset.push_back(linearized_index);	5!
100
101	// Keep any remaining subset dimensions that were beyond the array dimensions.
102	// This handles cases where the subset has more dimensions than the flattened array,
103	// which can occur when the pointee contains additional structure after the arrays.
104	for (size_t i = array_dimensions.size(); i < old_subset.size(); ++i) {	5!
NEW 105	new_subset.push_back(old_subset[i]);	×
NEW 106	}	×
107	} else {	5✔
108	// Keep original subset if it doesn't fit the pattern
NEW 109	new_subset = old_subset;	×
110	}
111
112	// Update memlet with new base type and subset
113	memlet->set_base_type(new_pointer_type);	5!
114	memlet->set_subset(new_subset);	5!
115
116	applied = true;	5✔
117	}	5✔
118
119	return applied;	6✔
120	}	6✔
121
122	} // namespace passes
123	} // namespace sdfg

daisytuner / sdfglib / 20687533221

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