• Home
  • Features
  • Pricing
  • Docs
  • Announcements
  • Sign In

daisytuner / sdfglib / 20687533221

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

push

github

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

Add memlet linearization pass for flattening nested array pointers

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
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
STATUS · Troubleshooting · Open an Issue · Sales · Support · CAREERS · ENTERPRISE · START FREE · SCHEDULE DEMO
ANNOUNCEMENTS · TWITTER · TOS & SLA · Supported CI Services · What's a CI service? · Automated Testing

© 2026 Coveralls, Inc