20770413849

Committed 06 Jan 2026 10:50PM UTC coverage: 62.168% (+21.4%) from 40.764%

Build # 20770413849

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #433 from daisytuner/clang-coverage

updates clang coverage flags

Run Details

14988 of 24109 relevant lines covered (62.17%)

88.57 hits per line

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

62.9

/src/passes/structured_control_flow/pointer_evolution.cpp

#include "sdfg/passes/structured_control_flow/pointer_evolution.h"

#include "sdfg/analysis/assumptions_analysis.h"
#include "sdfg/analysis/dominance_analysis.h"
#include "sdfg/analysis/loop_analysis.h"
#include "sdfg/symbolic/conjunctive_normal_form.h"
#include "sdfg/symbolic/polynomials.h"
#include "sdfg/symbolic/series.h"

namespace sdfg {
namespace passes {

IteratorToIndvar::IteratorToIndvar(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager)
    : NonStoppingStructuredSDFGVisitor(builder, analysis_manager) {

      };

bool IteratorToIndvar::accept(structured_control_flow::For& loop) {
    // Pattern: recursive pointer update
    // a = &a[1]

    // Criterion: Find iterator
    auto& users_analysis = analysis_manager_.get<analysis::Users>();
    analysis::UsersView body_users(users_analysis, loop.root());
    if (body_users.moves().size() != 1) {
        return false;
    }
    auto move = body_users.moves().at(0);
    auto& iterator = move->container();

    // Check whether update is recursive
    auto& move_dst = static_cast<data_flow::AccessNode&>(*move->element());
    auto& dfg = move_dst.get_parent();
    auto& move_edge = *dfg.in_edges(move_dst).begin();
    if (move_edge.type() != data_flow::MemletType::Reference) {
        return false;
    }
    auto& move_src = static_cast<data_flow::AccessNode&>(move_edge.src());
    if (move_src.data() != iterator) {
        return false;
    }

    // Criterion: Offset must be constant and in bytes
    auto& move_subset = move_edge.subset();
    if (move_subset.size() != 1) {
        return false;
    }
    auto offset = move_subset.at(0);
    if (!SymEngine::is_a<SymEngine::Integer>(*offset)) {
        return false;
    }
    int offset_int = SymEngine::rcp_static_cast<const SymEngine::Integer>(offset)->as_int();
    if (offset_int <= 0) {
        return false;
    }
    if (move_edge.base_type().type_id() != types::TypeID::Pointer) {
        return false;
    }
    auto& base_type = static_cast<const types::Pointer&>(move_edge.base_type());
    if (!base_type.has_pointee_type() || base_type.pointee_type().type_id() != types::TypeID::Scalar) {
        return false;
    }
    auto& pointee_type = static_cast<const types::Scalar&>(base_type.pointee_type());
    if (pointee_type.primitive_type() != types::PrimitiveType::UInt8 &&
        pointee_type.primitive_type() != types::PrimitiveType::Int8) {
        return false;
    }

    // All uses of iterator happen before update
    std::unordered_set<data_flow::Memlet*> edges;
    auto& dominance_analysis = analysis_manager_.get<analysis::DominanceAnalysis>();
    for (auto& use : body_users.uses(iterator)) {
        // Ignore move
        if (use == move) {
            continue;
        }
        // Ignore view of move
        if (use->element() == &move_src && use->use() == analysis::Use::VIEW) {
            continue;
        }
        if (!dynamic_cast<data_flow::AccessNode*>(use->element())) {
            return false;
        }
        auto& use_node = static_cast<data_flow::AccessNode&>(*use->element());
        auto& use_dfg = use_node.get_parent();

        // No second view
        if (use->use() == analysis::Use::VIEW) {
            return false;
        }
        // Happens before
        if (!dominance_analysis.post_dominates(*move, *use)) {
            return false;
        }

        if (use->use() == analysis::Use::READ) {
            for (auto& edge : use_dfg.out_edges(use_node)) {
                auto& subset = edge.subset();
                if (subset.size() != 1) {
                    return false;
                }
                if (!symbolic::eq(subset.at(0), symbolic::zero())) {
                    return false;
                }
                // Criterion: offseted bytes should equal interpreted type
                auto& use_edge_type = edge.base_type();
                if (use_edge_type.type_id() != types::TypeID::Pointer) {
                    return false;
                }
                auto& use_pointee_type = static_cast<const types::Pointer&>(use_edge_type).pointee_type();
                if (use_pointee_type.type_id() != types::TypeID::Scalar) {
                    return false;
                }
                auto use_pointee_bitwidth = types::bit_width(use_pointee_type.primitive_type());
                if (use_pointee_bitwidth != offset_int * 8) {
                    return false;
                }
                edges.insert(&edge);
            }
        } else if (use->use() == analysis::Use::WRITE) {
            for (auto& edge : use_dfg.in_edges(use_node)) {
                auto& subset = edge.subset();
                if (subset.size() != 1) {
                    return false;
                }
                if (!symbolic::eq(subset.at(0), symbolic::zero())) {
                    return false;
                }
                // Criterion: offseted bytes should equal interpreted type
                auto& use_edge_type = edge.base_type();
                if (use_edge_type.type_id() != types::TypeID::Pointer) {
                    return false;
                }
                auto& use_pointee_type = static_cast<const types::Pointer&>(use_edge_type).pointee_type();
                if (use_pointee_type.type_id() != types::TypeID::Scalar) {
                    return false;
                }
                auto use_pointee_bitwidth = types::bit_width(use_pointee_type.primitive_type());
                if (use_pointee_bitwidth != offset_int * 8) {
                    return false;
                }
                edges.insert(&edge);
            }
        } else {
            // Other uses are not allowed
            return false;
        }
    }

    // Step 1: Replace all subsets with iterator - init
    data_flow::Subset new_subset = {symbolic::sub(loop.indvar(), loop.init())};
    for (auto& edge : edges) {
        edge->set_subset(new_subset);
    }

    // Step 2: Remove iterator
    auto& block = static_cast<structured_control_flow::Block&>(*dfg.get_parent());
    builder_.remove_memlet(block, move_edge);
    builder_.remove_node(block, move_dst);
    builder_.remove_node(block, move_src);

    return true;
};

} // namespace passes
} // namespace sdfg

1	#include "sdfg/passes/structured_control_flow/pointer_evolution.h"
2
3	#include "sdfg/analysis/assumptions_analysis.h"
4	#include "sdfg/analysis/dominance_analysis.h"
5	#include "sdfg/analysis/loop_analysis.h"
6	#include "sdfg/symbolic/conjunctive_normal_form.h"
7	#include "sdfg/symbolic/polynomials.h"
8	#include "sdfg/symbolic/series.h"
9
10	namespace sdfg {
11	namespace passes {
12
13	IteratorToIndvar::IteratorToIndvar(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager)
14	: NonStoppingStructuredSDFGVisitor(builder, analysis_manager) {	1✔
15
16	};	1✔
17
18	bool IteratorToIndvar::accept(structured_control_flow::For& loop) {	1✔
19	// Pattern: recursive pointer update
20	// a = &a[1]
21
22	// Criterion: Find iterator
23	auto& users_analysis = analysis_manager_.get<analysis::Users>();	1✔
24	analysis::UsersView body_users(users_analysis, loop.root());	1✔
25	if (body_users.moves().size() != 1) {	1✔
26	return false;	×
27	}	×
28	auto move = body_users.moves().at(0);	1✔
29	auto& iterator = move->container();	1✔
30
31	// Check whether update is recursive
32	auto& move_dst = static_cast<data_flow::AccessNode&>(*move->element());	1✔
33	auto& dfg = move_dst.get_parent();	1✔
34	auto& move_edge = *dfg.in_edges(move_dst).begin();	1✔
35	if (move_edge.type() != data_flow::MemletType::Reference) {	1✔
36	return false;	×
37	}	×
38	auto& move_src = static_cast<data_flow::AccessNode&>(move_edge.src());	1✔
39	if (move_src.data() != iterator) {	1✔
40	return false;	×
41	}	×
42
43	// Criterion: Offset must be constant and in bytes
44	auto& move_subset = move_edge.subset();	1✔
45	if (move_subset.size() != 1) {	1✔
46	return false;	×
47	}	×
48	auto offset = move_subset.at(0);	1✔
49	if (!SymEngine::is_a<SymEngine::Integer>(*offset)) {	1✔
50	return false;	×
51	}	×
52	int offset_int = SymEngine::rcp_static_cast<const SymEngine::Integer>(offset)->as_int();	1✔
53	if (offset_int <= 0) {	1✔
54	return false;	×
55	}	×
56	if (move_edge.base_type().type_id() != types::TypeID::Pointer) {	1✔
57	return false;	×
58	}	×
59	auto& base_type = static_cast<const types::Pointer&>(move_edge.base_type());	1✔
60	if (!base_type.has_pointee_type() \|\| base_type.pointee_type().type_id() != types::TypeID::Scalar) {	1✔
61	return false;	×
62	}	×
63	auto& pointee_type = static_cast<const types::Scalar&>(base_type.pointee_type());	1✔
64	if (pointee_type.primitive_type() != types::PrimitiveType::UInt8 &&	1✔
65	pointee_type.primitive_type() != types::PrimitiveType::Int8) {	1✔
66	return false;	×
67	}	×
68
69	// All uses of iterator happen before update
70	std::unordered_set<data_flow::Memlet*> edges;	1✔
71	auto& dominance_analysis = analysis_manager_.get<analysis::DominanceAnalysis>();	1✔
72	for (auto& use : body_users.uses(iterator)) {	4✔
73	// Ignore move
74	if (use == move) {	4✔
75	continue;	1✔
76	}	1✔
77	// Ignore view of move
78	if (use->element() == &move_src && use->use() == analysis::Use::VIEW) {	3✔
79	continue;	1✔
80	}	1✔
81	if (!dynamic_cast<data_flow::AccessNode*>(use->element())) {	2✔
82	return false;	×
83	}	×
84	auto& use_node = static_cast<data_flow::AccessNode&>(*use->element());	2✔
85	auto& use_dfg = use_node.get_parent();	2✔
86
87	// No second view
88	if (use->use() == analysis::Use::VIEW) {	2✔
89	return false;	×
90	}	×
91	// Happens before
92	if (!dominance_analysis.post_dominates(move, use)) {	2✔
93	return false;	×
94	}	×
95
96	if (use->use() == analysis::Use::READ) {	2✔
97	for (auto& edge : use_dfg.out_edges(use_node)) {	1✔
98	auto& subset = edge.subset();	1✔
99	if (subset.size() != 1) {	1✔
100	return false;	×
101	}	×
102	if (!symbolic::eq(subset.at(0), symbolic::zero())) {	1✔
103	return false;	×
104	}	×
105	// Criterion: offseted bytes should equal interpreted type
106	auto& use_edge_type = edge.base_type();	1✔
107	if (use_edge_type.type_id() != types::TypeID::Pointer) {	1✔
108	return false;	×
109	}	×
110	auto& use_pointee_type = static_cast<const types::Pointer&>(use_edge_type).pointee_type();	1✔
111	if (use_pointee_type.type_id() != types::TypeID::Scalar) {	1✔
112	return false;	×
113	}	×
114	auto use_pointee_bitwidth = types::bit_width(use_pointee_type.primitive_type());	1✔
115	if (use_pointee_bitwidth != offset_int * 8) {	1✔
116	return false;	×
117	}	×
118	edges.insert(&edge);	1✔
119	}	1✔
120	} else if (use->use() == analysis::Use::WRITE) {	1✔
121	for (auto& edge : use_dfg.in_edges(use_node)) {	1✔
122	auto& subset = edge.subset();	1✔
123	if (subset.size() != 1) {	1✔
124	return false;	×
125	}	×
126	if (!symbolic::eq(subset.at(0), symbolic::zero())) {	1✔
127	return false;	×
128	}	×
129	// Criterion: offseted bytes should equal interpreted type
130	auto& use_edge_type = edge.base_type();	1✔
131	if (use_edge_type.type_id() != types::TypeID::Pointer) {	1✔
132	return false;	×
133	}	×
134	auto& use_pointee_type = static_cast<const types::Pointer&>(use_edge_type).pointee_type();	1✔
135	if (use_pointee_type.type_id() != types::TypeID::Scalar) {	1✔
136	return false;	×
137	}	×
138	auto use_pointee_bitwidth = types::bit_width(use_pointee_type.primitive_type());	1✔
139	if (use_pointee_bitwidth != offset_int * 8) {	1✔
140	return false;	×
141	}	×
142	edges.insert(&edge);	1✔
143	}	1✔
144	} else {	1✔
145	// Other uses are not allowed
146	return false;	×
147	}	×
148	}	2✔
149
150	// Step 1: Replace all subsets with iterator - init
151	data_flow::Subset new_subset = {symbolic::sub(loop.indvar(), loop.init())};	1✔
152	for (auto& edge : edges) {	2✔
153	edge->set_subset(new_subset);	2✔
154	}	2✔
155
156	// Step 2: Remove iterator
157	auto& block = static_cast<structured_control_flow::Block&>(*dfg.get_parent());	1✔
158	builder_.remove_memlet(block, move_edge);	1✔
159	builder_.remove_node(block, move_dst);	1✔
160	builder_.remove_node(block, move_src);	1✔
161
162	return true;	1✔
163	};	1✔
164
165	} // namespace passes
166	} // namespace sdfg

daisytuner / sdfglib / 20770413849

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