29408897400

Committed 15 Jul 2026 10:39AM UTC coverage: 63.163% (-0.02%) from 63.178%

Build # 29408897400

Build Type

Pull #851

github

Committed by

web-flow

Commit Message

Merge 41947f459 into dfbf2347f

Pull Request Pull Request #851: Add map fusion handling of analyses without invalidation

Coverage Stats

7 of 31 new or added lines in 3 files covered. (22.58%)

40628 of 64322 relevant lines covered (63.16%)

980.87 hits per line

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

27.85

/opt/src/passes/normalization/map_fusion.cpp

#include "sdfg/passes/normalization/map_fusion.h"

#include "sdfg/analysis/loop_analysis.h"
#include "sdfg/data_flow/library_nodes/stdlib/malloc.h"
#include "sdfg/transformations/map_fusion.h"

namespace sdfg {
namespace passes {
namespace normalization {

MapFusion::MapFusion(
    builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager, bool allow_init_hoist
)
    : visitor::NonStoppingStructuredSDFGVisitor(builder, analysis_manager), allow_init_hoist_(allow_init_hoist) {}

bool MapFusion::accept(structured_control_flow::Sequence& node) {
    bool applied = false;

    if (node.size() < 2) {
        return applied;
    }

    // LoopAnalysis is cheap to re-run and must be re-run whenever the loop structure changes.
    // AssumptionsAnalysis is expensive (symbolic computation) and is preserved across
    // ProducerIntoConsumer fusions: those only prepend Block nodes to the consumer body, so
    // the existing per-node assumption entries remain valid for all nodes that are not new.
    //
    // stale_loop tracks the StructuredLoop whose body was just modified by a
    // ProducerIntoConsumer fusion.  When it is encountered as the next producer candidate,
    // LoopAnalysis is invalidated so it is re-run with the updated body.
    structured_control_flow::StructuredLoop* stale_loop = nullptr;

    // Iterate over sequence looking for consecutive (Map, StructuredLoop) pairs
    size_t i = 0;
    while (i + 1 < node.size()) {
        auto* first = dyn_cast<structured_control_flow::Map*>(&node.at(i).first);
        if (!first) {
            stale_loop = nullptr;
            i++;
            continue;
        }
        if (first->root().size() == 0) {
            i++;
            continue;
        }

        // If this node was the consumer of a previous ProducerIntoConsumer fusion its
        // LoopAnalysis entry is stale (blocks were prepended to its body).  Force a
        // re-run before checking it as a new producer.
        if (stale_loop == first) {
            analysis_manager_.invalidate<analysis::LoopAnalysis>();
            stale_loop = nullptr;
        }

        if (auto* second = dyn_cast<structured_control_flow::StructuredLoop*>(&node.at(i + 1).first)) {
            if (second->root().size() == 0) {
                i++;
                continue;
            }
            transformations::MapFusion transformation(*first, *second, true, allow_init_hoist_);
            if (transformation.can_be_applied(builder_, analysis_manager_)) {
                auto first_name = first->indvar()->get_name();
                auto second_name = second->indvar()->get_name();

                // Apply without letting the transformation invalidate the manager;
                // we selectively invalidate below based on the fusion direction.
                transformation.apply_without_invalidate(builder_, analysis_manager_);

                if (transformation.was_producer_into_consumer()) {
                    // ProducerIntoConsumer only prepends Block nodes to second's body.
                    // The loop structure of every other node in this sequence is unchanged,
                    // so AssumptionsAnalysis and ArgumentsAnalysis stay valid.
                    // LoopAnalysis for `second` is now stale and must be re-run when
                    // `second` is next encountered as a producer candidate.
                    analysis_manager_.invalidate<analysis::LoopAnalysis>();
                    stale_loop = second;
                } else {
                    // ConsumerIntoProducer removes second_loop_ from the sequence and
                    // modifies the producer body — full invalidation is required.
                    analysis_manager_.invalidate_all();
                    stale_loop = nullptr;
                }

                DEBUG_PRINTLN("Applied MapFusion to maps " + first_name + " and " + second_name);
                applied = true;
            }
        } else if (i + 2 < node.size()) {
            auto* mid_block = dyn_cast<structured_control_flow::Block*>(&node.at(i + 1).first);
            if (mid_block && mid_block->is_a_library_node<stdlib::MallocNode>()) {
                if (auto* second = dyn_cast<structured_control_flow::StructuredLoop*>(&node.at(i + 2).first)) {
                    if (second->root().size() == 0) {
                        i++;
                        continue;
                    }
                    transformations::MapFusion transformation(*first, *second, false, allow_init_hoist_);
                    if (transformation.can_be_applied(builder_, analysis_manager_)) {
                        auto first_name = first->indvar()->get_name();
                        auto second_name = second->indvar()->get_name();

                        transformation.apply_without_invalidate(builder_, analysis_manager_);

                        if (transformation.was_producer_into_consumer()) {
                            analysis_manager_.invalidate<analysis::LoopAnalysis>();
                            stale_loop = second;
                        } else {
                            analysis_manager_.invalidate_all();
                            stale_loop = nullptr;
                        }

                        DEBUG_PRINTLN(
                            "Applied MapFusion to map " + first_name + " and loop " + second_name +
                            " with intermediate malloc block"
                        );
                        applied = true;

                        // Move malloc block before the first map
                        this->builder_.move_child(node, i + 1, node, i);
                        i = i + 2; // Skip over the newly moved malloc block and the second loop that was just fused
                        continue;
                    }
                }
            }
        }
        i++;
    }

    return applied;
}

} // namespace normalization
} // namespace passes
} // namespace sdfg

1	#include "sdfg/passes/normalization/map_fusion.h"
2
3	#include "sdfg/analysis/loop_analysis.h"
4	#include "sdfg/data_flow/library_nodes/stdlib/malloc.h"
5	#include "sdfg/transformations/map_fusion.h"
6
7	namespace sdfg {
8	namespace passes {
9	namespace normalization {
10
11	MapFusion::MapFusion(
12	builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager, bool allow_init_hoist
13	)
14	: visitor::NonStoppingStructuredSDFGVisitor(builder, analysis_manager), allow_init_hoist_(allow_init_hoist) {}	2✔
15
16	bool MapFusion::accept(structured_control_flow::Sequence& node) {	8✔
17	bool applied = false;	8✔
18
19	if (node.size() < 2) {	8✔
20	return applied;	6✔
21	}	6✔
22
23	// LoopAnalysis is cheap to re-run and must be re-run whenever the loop structure changes.
24	// AssumptionsAnalysis is expensive (symbolic computation) and is preserved across
25	// ProducerIntoConsumer fusions: those only prepend Block nodes to the consumer body, so
26	// the existing per-node assumption entries remain valid for all nodes that are not new.
27	//
28	// stale_loop tracks the StructuredLoop whose body was just modified by a
29	// ProducerIntoConsumer fusion. When it is encountered as the next producer candidate,
30	// LoopAnalysis is invalidated so it is re-run with the updated body.
31	structured_control_flow::StructuredLoop* stale_loop = nullptr;	2✔
32
33	// Iterate over sequence looking for consecutive (Map, StructuredLoop) pairs
34	size_t i = 0;	2✔
35	while (i + 1 < node.size()) {	4✔
36	auto* first = dyn_cast<structured_control_flow::Map*>(&node.at(i).first);	2✔
37	if (!first) {	2✔
NEW 38	stale_loop = nullptr;	×
39	i++;	×
40	continue;	×
41	}	×
42	if (first->root().size() == 0) {	2✔
43	i++;	×
44	continue;	×
45	}	×
46
47	// If this node was the consumer of a previous ProducerIntoConsumer fusion its
48	// LoopAnalysis entry is stale (blocks were prepended to its body). Force a
49	// re-run before checking it as a new producer.
50	if (stale_loop == first) {	2✔
NEW 51	analysis_manager_.invalidate<analysis::LoopAnalysis>();	×
NEW 52	stale_loop = nullptr;	×
NEW 53	}	×
54
55	if (auto* second = dyn_cast<structured_control_flow::StructuredLoop*>(&node.at(i + 1).first)) {	2✔
56	if (second->root().size() == 0) {	2✔
57	i++;	×
58	continue;	×
59	}	×
60	transformations::MapFusion transformation(first, second, true, allow_init_hoist_);	2✔
61	if (transformation.can_be_applied(builder_, analysis_manager_)) {	2✔
62	auto first_name = first->indvar()->get_name();	×
63	auto second_name = second->indvar()->get_name();	×
64
65	// Apply without letting the transformation invalidate the manager;
66	// we selectively invalidate below based on the fusion direction.
NEW 67	transformation.apply_without_invalidate(builder_, analysis_manager_);	×
68
NEW 69	if (transformation.was_producer_into_consumer()) {	×
70	// ProducerIntoConsumer only prepends Block nodes to second's body.
71	// The loop structure of every other node in this sequence is unchanged,
72	// so AssumptionsAnalysis and ArgumentsAnalysis stay valid.
73	// LoopAnalysis for `second` is now stale and must be re-run when
74	// `second` is next encountered as a producer candidate.
NEW 75	analysis_manager_.invalidate<analysis::LoopAnalysis>();	×
NEW 76	stale_loop = second;	×
NEW 77	} else {	×
78	// ConsumerIntoProducer removes second_loop_ from the sequence and
79	// modifies the producer body — full invalidation is required.
NEW 80	analysis_manager_.invalidate_all();	×
NEW 81	stale_loop = nullptr;	×
NEW 82	}	×
83
84	DEBUG_PRINTLN("Applied MapFusion to maps " + first_name + " and " + second_name);	×
85	applied = true;	×
86	}	×
87	} else if (i + 2 < node.size()) {	2✔
88	auto* mid_block = dyn_cast<structured_control_flow::Block*>(&node.at(i + 1).first);	×
89	if (mid_block && mid_block->is_a_library_node<stdlib::MallocNode>()) {	×
90	if (auto* second = dyn_cast<structured_control_flow::StructuredLoop*>(&node.at(i + 2).first)) {	×
91	if (second->root().size() == 0) {	×
92	i++;	×
93	continue;	×
94	}	×
95	transformations::MapFusion transformation(first, second, false, allow_init_hoist_);	×
96	if (transformation.can_be_applied(builder_, analysis_manager_)) {	×
97	auto first_name = first->indvar()->get_name();	×
98	auto second_name = second->indvar()->get_name();	×
99
NEW 100	transformation.apply_without_invalidate(builder_, analysis_manager_);	×
101
NEW 102	if (transformation.was_producer_into_consumer()) {	×
NEW 103	analysis_manager_.invalidate<analysis::LoopAnalysis>();	×
NEW 104	stale_loop = second;	×
NEW 105	} else {	×
NEW 106	analysis_manager_.invalidate_all();	×
NEW 107	stale_loop = nullptr;	×
NEW 108	}	×
109
110	DEBUG_PRINTLN(	×
111	"Applied MapFusion to map " + first_name + " and loop " + second_name +	×
112	" with intermediate malloc block"	×
113	);	×
114	applied = true;	×
115
116	// Move malloc block before the first map
117	this->builder_.move_child(node, i + 1, node, i);	×
118	i = i + 2; // Skip over the newly moved malloc block and the second loop that was just fused	×
119	continue;	×
120	}	×
121	}	×
122	}	×
123	}	×
124	i++;	2✔
125	}	2✔
126
127	return applied;	2✔
128	}	8✔
129
130	} // namespace normalization
131	} // namespace passes
132	} // namespace sdfg

daisytuner / docc / 29408897400

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