23983017072

Committed 04 Apr 2026 04:35PM UTC coverage: 64.774% (+0.04%) from 64.736%

Build # 23983017072

Build Type

Pull #645

github

Committed by

web-flow

Commit Message

Merge e8d587946 into affb8e1db

Pull Request Pull Request #645: Handles final value of loops when normalizing

Coverage Stats

62 of 88 new or added lines in 6 files covered. (70.45%)

29164 of 45024 relevant lines covered (64.77%)

532.48 hits per line

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

89.13

/opt/src/passes/normalization/loop_normal_form.cpp

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

#include "sdfg/analysis/loop_analysis.h"
#include "sdfg/symbolic/symbolic.h"
#include "sdfg/transformations/loop_condition_normalize.h"
#include "sdfg/transformations/loop_indvar_finalize.h"
#include "sdfg/transformations/loop_rotate.h"
#include "sdfg/transformations/loop_shift.h"
#include "sdfg/transformations/loop_unit_stride.h"

namespace sdfg {
namespace passes {
namespace normalization {

LoopNormalFormPass::LoopNormalFormPass() {};

bool LoopNormalFormPass::apply(
    builder::StructuredSDFGBuilder& builder,
    analysis::AnalysisManager& analysis_manager,
    structured_control_flow::StructuredLoop& loop
) {
    bool applied = false;

    // Step 1: Shift loop to start from 0
    transformations::LoopShift loop_shift(loop);
    if (loop_shift.can_be_applied(builder, analysis_manager)) {
        loop_shift.apply(builder, analysis_manager);
        applied = true;
    }

    // Step 2: Convert non-unit stride to unit stride
    transformations::LoopUnitStride loop_unit_stride(loop);
    if (loop_unit_stride.can_be_applied(builder, analysis_manager)) {
        loop_unit_stride.apply(builder, analysis_manager);
        applied = true;
    }

    // Step 3: Convert != conditions to < or > (requires unit stride)
    transformations::LoopConditionNormalize loop_cond_normalize(loop);
    if (loop_cond_normalize.can_be_applied(builder, analysis_manager)) {
        loop_cond_normalize.apply(builder, analysis_manager);
        applied = true;
    }

    // Step 4: Convert negative stride to positive (requires < or > conditions)
    transformations::LoopRotate loop_rotate(loop);
    if (loop_rotate.can_be_applied(builder, analysis_manager)) {
        loop_rotate.apply(builder, analysis_manager);
        applied = true;

        // After rotation, we may have a non-zero init, so try shifting
        transformations::LoopShift loop_shift(loop);
        if (loop_shift.can_be_applied(builder, analysis_manager)) {
            loop_shift.apply(builder, analysis_manager);
            applied = true;
        }
    }

    // Step 5: Simplify reconstruction blocks with closed-form expression
    transformations::LoopIndvarFinalize finalize(loop);
    if (finalize.can_be_applied(builder, analysis_manager)) {
        finalize.apply(builder, analysis_manager);
        applied = true;
    }

    return applied;
};

bool LoopNormalFormPass::run_pass(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {
    bool modified = false;

    auto& loop_analysis = analysis_manager.get<analysis::LoopAnalysis>();
    for (auto& loop : loop_analysis.loops()) {
        if (!dynamic_cast<structured_control_flow::StructuredLoop*>(loop)) {
            continue; // Skip non-structured loops
        }
        modified |= apply(builder, analysis_manager, *dynamic_cast<structured_control_flow::StructuredLoop*>(loop));
    }

    return modified;
}


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

1	#include "sdfg/passes/normalization/loop_normal_form.h"
2
3	#include "sdfg/analysis/loop_analysis.h"
4	#include "sdfg/symbolic/symbolic.h"
5	#include "sdfg/transformations/loop_condition_normalize.h"
6	#include "sdfg/transformations/loop_indvar_finalize.h"
7	#include "sdfg/transformations/loop_rotate.h"
8	#include "sdfg/transformations/loop_shift.h"
9	#include "sdfg/transformations/loop_unit_stride.h"
10
11	namespace sdfg {
12	namespace passes {
13	namespace normalization {
14
15	LoopNormalFormPass::LoopNormalFormPass() {};	9✔
16
17	bool LoopNormalFormPass::apply(
18	builder::StructuredSDFGBuilder& builder,
19	analysis::AnalysisManager& analysis_manager,
20	structured_control_flow::StructuredLoop& loop
21	) {	10✔
22	bool applied = false;	10✔
23
24	// Step 1: Shift loop to start from 0
25	transformations::LoopShift loop_shift(loop);	10✔
26	if (loop_shift.can_be_applied(builder, analysis_manager)) {	10✔
27	loop_shift.apply(builder, analysis_manager);	5✔
28	applied = true;	5✔
29	}	5✔
30
31	// Step 2: Convert non-unit stride to unit stride
32	transformations::LoopUnitStride loop_unit_stride(loop);	10✔
33	if (loop_unit_stride.can_be_applied(builder, analysis_manager)) {	10✔
34	loop_unit_stride.apply(builder, analysis_manager);	6✔
35	applied = true;	6✔
36	}	6✔
37
38	// Step 3: Convert != conditions to < or > (requires unit stride)
39	transformations::LoopConditionNormalize loop_cond_normalize(loop);	10✔
40	if (loop_cond_normalize.can_be_applied(builder, analysis_manager)) {	10✔
NEW 41	loop_cond_normalize.apply(builder, analysis_manager);	×
42	applied = true;	×
43	}	×
44
45	// Step 4: Convert negative stride to positive (requires < or > conditions)
46	transformations::LoopRotate loop_rotate(loop);	10✔
47	if (loop_rotate.can_be_applied(builder, analysis_manager)) {	10✔
48	loop_rotate.apply(builder, analysis_manager);	2✔
49	applied = true;	2✔
50
51	// After rotation, we may have a non-zero init, so try shifting
52	transformations::LoopShift loop_shift(loop);	2✔
53	if (loop_shift.can_be_applied(builder, analysis_manager)) {	2✔
54	loop_shift.apply(builder, analysis_manager);	2✔
55	applied = true;	2✔
56	}	2✔
57	}	2✔
58
59	// Step 5: Simplify reconstruction blocks with closed-form expression
60	transformations::LoopIndvarFinalize finalize(loop);	10✔
61	if (finalize.can_be_applied(builder, analysis_manager)) {	10✔
62	finalize.apply(builder, analysis_manager);	10✔
63	applied = true;	10✔
64	}	10✔
65
66	return applied;	10✔
67	};	10✔
68
69	bool LoopNormalFormPass::run_pass(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	9✔
70	bool modified = false;	9✔
71
72	auto& loop_analysis = analysis_manager.get<analysis::LoopAnalysis>();	9✔
73	for (auto& loop : loop_analysis.loops()) {	10✔
74	if (!dynamic_cast<structured_control_flow::StructuredLoop*>(loop)) {	10✔
NEW 75	continue; // Skip non-structured loops	×
NEW 76	}	×
77	modified \|= apply(builder, analysis_manager, dynamic_cast<structured_control_flow::StructuredLoop>(loop));	10✔
78	}	10✔
79
80	return modified;	9✔
81	}	9✔
82
83
84	} // namespace normalization
85	} // namespace passes
86	} // namespace sdfg

daisytuner / docc / 23983017072

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