25459771247

Committed 06 May 2026 08:37PM UTC coverage: 65.659% (+0.4%) from 65.223%

Build # 25459771247

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #704 from daisytuner/lcd-analysis

Refactors LoopCarriedDependencyAnalysis into standalone analysis

Coverage Stats

731 of 828 new or added lines in 13 files covered. (88.29%)

42 existing lines in 5 files now uncovered.

32175 of 49003 relevant lines covered (65.66%)

12934.86 hits per line

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

77.97

/sdfg/src/analysis/loop_carried_dependency_analysis.cpp

#include "sdfg/analysis/loop_carried_dependency_analysis.h"

#include <cassert>
#include <string>
#include <vector>

#include <isl/ctx.h>
#include <isl/options.h>
#include <isl/set.h>

#include "sdfg/analysis/analysis.h"
#include "sdfg/analysis/assumptions_analysis.h"
#include "sdfg/analysis/data_dependency_analysis.h"
#include "sdfg/analysis/loop_analysis.h"
#include "sdfg/analysis/memory_layout_analysis.h"
#include "sdfg/analysis/scope_analysis.h"
#include "sdfg/analysis/users.h"
#include "sdfg/data_flow/access_node.h"
#include "sdfg/data_flow/memlet.h"
#include "sdfg/structured_sdfg.h"
#include "sdfg/symbolic/maps.h"
#include "sdfg/types/scalar.h"

namespace sdfg {
namespace analysis {

LoopCarriedDependencyAnalysis::LoopCarriedDependencyAnalysis(StructuredSDFG& sdfg)
    : Analysis(sdfg), node_(sdfg.root()) {}

LoopCarriedDependencyAnalysis::LoopCarriedDependencyAnalysis(StructuredSDFG& sdfg, structured_control_flow::Sequence& node)
    : Analysis(sdfg), node_(node) {}

DataDependencyAnalysis& LoopCarriedDependencyAnalysis::detailed_dda() {
    if (!detailed_dda_) {
        detailed_dda_ = std::make_unique<DataDependencyAnalysis>(this->sdfg_, this->node_);
        detailed_dda_->set_detailed(true);
    }
    return *detailed_dda_;
}

void LoopCarriedDependencyAnalysis::analyze_loop(
    analysis::AnalysisManager& /*analysis_manager*/, structured_control_flow::StructuredLoop& /*loop*/
) {
    // Per-loop work is done inline in `run()`.
}

namespace {

bool is_undefined_user(User& user) {
    // Mirror DDA::is_undefined_user — undefined users have a null vertex.
    return user.element() == nullptr;
}

// Collect a user's subsets, preferring delinearized (multi-dim) subsets from
// MemoryLayoutAnalysis when available. ISL cannot reason precisely about
// linearized expressions like `i*N + j`; delinearization recovers `[i, j]` so
// `dependence_deltas` can compute exact distance vectors.
//
// The returned vector is index-aligned with the user's underlying memlets:
// for each memlet, either MLA's delinearized subset (when MLA succeeded) or
// the memlet's original subset (linearized fallback).
std::vector<data_flow::Subset> collect_subsets(User& user, MemoryLayoutAnalysis& mla) {
    std::vector<data_flow::Subset> result;
    auto* access_node = dynamic_cast<data_flow::AccessNode*>(user.element());
    if (access_node == nullptr) {
        for (auto& s : user.subsets()) result.push_back(s);
        return result;
    }
    auto& graph = access_node->get_parent();
    if (user.use() == Use::READ || user.use() == Use::VIEW) {
        for (auto& edge : graph.out_edges(*access_node)) {
            if (auto* acc = mla.access(edge)) {
                result.push_back(acc->subset);
            } else {
                result.push_back(edge.subset());
            }
        }
    } else if (user.use() == Use::WRITE || user.use() == Use::MOVE) {
        for (auto& edge : graph.in_edges(*access_node)) {
            if (auto* acc = mla.access(edge)) {
                result.push_back(acc->subset);
            } else {
                result.push_back(edge.subset());
            }
        }
    }
    return result;
}

// Compute the union of iteration-distance delta sets between two users wrt
// `loop`'s indvar. Inner-loop indvars are marked non-constant so that the ISL
// formulation existentially quantifies them per-side (giving "different inner
// iteration" the freedom it needs).
//
// Returns {empty=true} when no loop-carried dependence exists between the two
// users. Returns {empty=false, deltas_str=""} for the scalar shortcut and for
// undefined users (dependence exists, distance unrepresentable).
symbolic::maps::DependenceDeltas pair_deltas(
    StructuredSDFG& sdfg,
    User& previous,
    User& current,
    analysis::AnalysisManager& analysis_manager,
    structured_control_flow::StructuredLoop& loop
) {
    symbolic::maps::DependenceDeltas empty_result{true, "", {}};

    if (previous.container() != current.container()) {
        return empty_result;
    }

    // Scalar shortcut: any pair of accesses to a scalar is loop-carried but the
    // distance vector is unrepresentable.
    auto& type = sdfg.type(previous.container());
    if (dynamic_cast<const types::Scalar*>(&type)) {
        return symbolic::maps::DependenceDeltas{false, "", {}};
    }

    if (is_undefined_user(previous) || is_undefined_user(current)) {
        return empty_result;
    }

    // Use MLA-delinearized subsets when available so ISL can reason precisely
    // about multi-dimensional pointer accesses.
    auto& mla = analysis_manager.get<analysis::MemoryLayoutAnalysis>();
    auto previous_subsets = collect_subsets(previous, mla);
    auto current_subsets = collect_subsets(current, mla);

    auto& assumptions_analysis = analysis_manager.get<analysis::AssumptionsAnalysis>();
    auto previous_scope = Users::scope(&previous);
    auto previous_assumptions = assumptions_analysis.get(*previous_scope, true);
    auto current_scope = Users::scope(&current);
    auto current_assumptions = assumptions_analysis.get(*current_scope, true);

    // Mark loop's indvar and all nested loop indvars as non-constant from this
    // loop's perspective.
    auto& loop_analysis = analysis_manager.get<analysis::LoopAnalysis>();
    if (previous_assumptions.find(loop.indvar()) != previous_assumptions.end()) {
        previous_assumptions.at(loop.indvar()).constant(false);
    }
    if (current_assumptions.find(loop.indvar()) != current_assumptions.end()) {
        current_assumptions.at(loop.indvar()).constant(false);
    }
    for (auto& inner_loop : loop_analysis.descendants(&loop)) {
        if (auto structured_loop = dynamic_cast<const structured_control_flow::StructuredLoop*>(inner_loop)) {
            auto indvar = structured_loop->indvar();
            if (previous_assumptions.find(indvar) != previous_assumptions.end()) {
                previous_assumptions.at(indvar).constant(false);
            }
            if (current_assumptions.find(indvar) != current_assumptions.end()) {
                current_assumptions.at(indvar).constant(false);
            }
        }
    }

    // Collect deltas across all subset pairs and union them.
    isl_ctx* union_ctx = nullptr;
    isl_set* accumulated = nullptr;
    std::vector<std::string> result_dimensions;

    for (auto& previous_subset : previous_subsets) {
        for (auto& current_subset : current_subsets) {
            auto deltas = symbolic::maps::dependence_deltas(
                previous_subset, current_subset, loop.indvar(), previous_assumptions, current_assumptions
            );
            if (deltas.empty) {
                continue;
            }
            if (deltas.deltas_str.empty()) {
                if (accumulated) {
                    isl_set_free(accumulated);
                    isl_ctx_free(union_ctx);
                }
                return symbolic::maps::DependenceDeltas{false, "", {}};
            }
            if (!union_ctx) {
                union_ctx = isl_ctx_alloc();
                isl_options_set_on_error(union_ctx, ISL_ON_ERROR_CONTINUE);
                accumulated = isl_set_read_from_str(union_ctx, deltas.deltas_str.c_str());
                result_dimensions = deltas.dimensions;
            } else {
                isl_set* new_set = isl_set_read_from_str(union_ctx, deltas.deltas_str.c_str());
                if (new_set && accumulated) {
                    accumulated = isl_set_union(accumulated, new_set);
                } else if (new_set) {
                    isl_set_free(new_set);
                }
            }
        }
    }

    if (!accumulated) {
        if (union_ctx) {
            isl_ctx_free(union_ctx);
        }
        return empty_result;
    }

    char* str = isl_set_to_str(accumulated);
    if (!str) {
        isl_set_free(accumulated);
        isl_ctx_free(union_ctx);
        return symbolic::maps::DependenceDeltas{false, "", {}};
    }
    std::string union_str(str);
    free(str);

    isl_set_free(accumulated);
    isl_ctx_free(union_ctx);

    return symbolic::maps::DependenceDeltas{false, union_str, result_dimensions};
}

void merge_deltas(LoopCarriedDependencyInfo& info, const symbolic::maps::DependenceDeltas& add) {
    if (add.empty) return;
    if (info.deltas.empty) {
        info.deltas = add;
        return;
    }
    if (add.deltas_str.empty() || info.deltas.deltas_str.empty()) {
        info.deltas.empty = false;
        return;
    }
    isl_ctx* ctx = isl_ctx_alloc();
    isl_options_set_on_error(ctx, ISL_ON_ERROR_CONTINUE);
    isl_set* s1 = isl_set_read_from_str(ctx, info.deltas.deltas_str.c_str());
    isl_set* s2 = isl_set_read_from_str(ctx, add.deltas_str.c_str());
    if (s1 && s2) {
        isl_set* u = isl_set_union(s1, s2);
        char* str = u ? isl_set_to_str(u) : nullptr;
        if (str) {
            info.deltas.deltas_str = std::string(str);
            free(str);
        } else {
            info.deltas.deltas_str = "";
            info.deltas.dimensions.clear();
        }
        if (u) isl_set_free(u);
    } else {
        if (s1) isl_set_free(s1);
        if (s2) isl_set_free(s2);
        info.deltas.deltas_str = "";
        info.deltas.dimensions.clear();
    }
    isl_ctx_free(ctx);
}

bool user_in_subtree(
    User& user, const structured_control_flow::ControlFlowNode& subtree, analysis::ScopeAnalysis& scope_analysis
) {
    auto* scope = Users::scope(&user);
    while (scope != nullptr) {
        if (scope == &subtree) {
            return true;
        }
        scope = scope_analysis.parent_scope(scope);
    }
    return false;
}

} // namespace

void LoopCarriedDependencyAnalysis::run(analysis::AnalysisManager& analysis_manager) {
    dependencies_.clear();
    pairs_.clear();

    // Drive entirely from DDA's reaching-definitions scaffold:
    //   - DDA computes per-loop boundary snapshots (upward-exposed reads,
    //     escaping definitions) — its primary job.
    //   - LCDA enumerates the cross-iteration pair space and computes delta
    //     sets via `pair_deltas` (using `symbolic::maps::dependence_deltas`).
    //
    // For a structured loop L with indvar i_L:
    //   pairs(L) = { (W,R, RAW, Δ_L(W,R)) : W ∈ esc(L), R ∈ ue(L),
    //                                       cont(W) = cont(R), Δ ≠ ∅ }
    //            ∪ { (W₁,W₂, WAW, Δ_L(W₁,W₂)) : W₁,W₂ ∈ esc(L),
    //                                           cont(W₁) = cont(W₂), Δ ≠ ∅ }
    auto& dda = detailed_dda();
    dda.run(analysis_manager);
    auto& loop_analysis = analysis_manager.get<analysis::LoopAnalysis>();
    auto& scope_analysis = analysis_manager.get<analysis::ScopeAnalysis>();

    for (auto* loop_node : loop_analysis.loops()) {
        auto* loop = dynamic_cast<structured_control_flow::StructuredLoop*>(loop_node);
        if (loop == nullptr) {
            continue;
        }

        // Restrict to loops within the analysis scope (`node_`).
        bool in_scope = false;
        structured_control_flow::ControlFlowNode* cur = loop;
        while (cur != nullptr) {
            if (cur == &node_) {
                in_scope = true;
                break;
            }
            cur = scope_analysis.parent_scope(cur);
        }
        if (!in_scope) {
            continue;
        }

        // Non-monotonic / unanalyzable loops: don't register; consumers must
        // treat absence as "no info" and fall back to safe defaults.
        if (!loop->is_monotonic()) {
            continue;
        }
        if (!dda.has_loop_boundary(*loop)) {
            continue;
        }

        auto& ue_reads = dda.upward_exposed_reads(*loop);
        auto& esc_defs = dda.escaping_definitions(*loop);

        auto& deps = dependencies_[loop];
        auto& pair_list = pairs_[loop];

        // RAW: escaping_writes × upward_exposed_reads
        for (auto& write_entry : esc_defs) {
            auto* write = write_entry.first;
            for (auto* read : ue_reads) {
                if (write->container() != read->container()) {
                    continue;
                }
                auto deltas = pair_deltas(this->sdfg_, *write, *read, analysis_manager, *loop);
                if (deltas.empty) continue;
                pair_list.push_back(LoopCarriedDependencyPair{write, read, LOOP_CARRIED_DEPENDENCY_READ_WRITE, deltas});
                auto it = deps.find(read->container());
                if (it == deps.end()) {
                    deps[read->container()] = LoopCarriedDependencyInfo{LOOP_CARRIED_DEPENDENCY_READ_WRITE, deltas};
                } else {
                    it->second.type = LOOP_CARRIED_DEPENDENCY_READ_WRITE;
                    merge_deltas(it->second, deltas);
                }
            }
        }

        // WAW: escaping_writes × escaping_writes (ordered pairs incl. self)
        for (auto& w1_entry : esc_defs) {
            auto* w1 = w1_entry.first;
            for (auto& w2_entry : esc_defs) {
                auto* w2 = w2_entry.first;
                if (w1->container() != w2->container()) {
                    continue;
                }
                auto deltas = pair_deltas(this->sdfg_, *w1, *w2, analysis_manager, *loop);
                if (deltas.empty) continue;
                pair_list.push_back(LoopCarriedDependencyPair{w1, w2, LOOP_CARRIED_DEPENDENCY_WRITE_WRITE, deltas});
                if (deps.find(w1->container()) == deps.end()) {
                    deps[w1->container()] = LoopCarriedDependencyInfo{LOOP_CARRIED_DEPENDENCY_WRITE_WRITE, deltas};
                }
            }
        }
    }
}

bool LoopCarriedDependencyAnalysis::available(structured_control_flow::StructuredLoop& loop) const {
    return pairs_.find(&loop) != pairs_.end();
}

const std::unordered_map<std::string, LoopCarriedDependencyInfo>& LoopCarriedDependencyAnalysis::
    dependencies(structured_control_flow::StructuredLoop& loop) const {
    auto it = dependencies_.find(&loop);
    assert(it != dependencies_.end() && "LoopCarriedDependencyAnalysis: loop not analyzed");
    return it->second;
}

const std::vector<LoopCarriedDependencyPair>& LoopCarriedDependencyAnalysis::pairs(structured_control_flow::StructuredLoop&
                                                                                       loop) const {
    auto it = pairs_.find(&loop);
    assert(it != pairs_.end() && "LoopCarriedDependencyAnalysis: loop not analyzed");
    return it->second;
}

std::vector<const LoopCarriedDependencyPair*> LoopCarriedDependencyAnalysis::pairs_between(
    structured_control_flow::StructuredLoop& loop,
    const structured_control_flow::ControlFlowNode& subtree_a,
    const structured_control_flow::ControlFlowNode& subtree_b,
    analysis::AnalysisManager& analysis_manager
) const {
    std::vector<const LoopCarriedDependencyPair*> result;
    auto it = pairs_.find(&loop);
    if (it == pairs_.end()) {
        return result;
    }
    auto& scope_analysis = analysis_manager.get<analysis::ScopeAnalysis>();

    for (auto& pair : it->second) {
        bool wa = user_in_subtree(*pair.writer, subtree_a, scope_analysis);
        bool wb = user_in_subtree(*pair.writer, subtree_b, scope_analysis);
        bool ra = user_in_subtree(*pair.reader, subtree_a, scope_analysis);
        bool rb = user_in_subtree(*pair.reader, subtree_b, scope_analysis);

        if ((wa && rb) || (wb && ra)) {
            result.push_back(&pair);
        }
    }
    return result;
}

bool LoopCarriedDependencyAnalysis::has_loop_carried(structured_control_flow::StructuredLoop& loop) const {
    auto it = pairs_.find(&loop);
    if (it == pairs_.end()) return false;
    return !it->second.empty();
}

bool LoopCarriedDependencyAnalysis::has_loop_carried_raw(structured_control_flow::StructuredLoop& loop) const {
    auto it = pairs_.find(&loop);
    if (it == pairs_.end()) return false;
    for (auto& p : it->second) {
        if (p.type == LOOP_CARRIED_DEPENDENCY_READ_WRITE) return true;
    }
    return false;
}

} // namespace analysis
} // namespace sdfg

1	#include "sdfg/analysis/loop_carried_dependency_analysis.h"
2
3	#include <cassert>
4	#include <string>
5	#include <vector>
6
7	#include <isl/ctx.h>
8	#include <isl/options.h>
9	#include <isl/set.h>
10
11	#include "sdfg/analysis/analysis.h"
12	#include "sdfg/analysis/assumptions_analysis.h"
13	#include "sdfg/analysis/data_dependency_analysis.h"
14	#include "sdfg/analysis/loop_analysis.h"
15	#include "sdfg/analysis/memory_layout_analysis.h"
16	#include "sdfg/analysis/scope_analysis.h"
17	#include "sdfg/analysis/users.h"
18	#include "sdfg/data_flow/access_node.h"
19	#include "sdfg/data_flow/memlet.h"
20	#include "sdfg/structured_sdfg.h"
21	#include "sdfg/symbolic/maps.h"
22	#include "sdfg/types/scalar.h"
23
24	namespace sdfg {
25	namespace analysis {
26
27	LoopCarriedDependencyAnalysis::LoopCarriedDependencyAnalysis(StructuredSDFG& sdfg)
28	: Analysis(sdfg), node_(sdfg.root()) {}	166✔
29
30	LoopCarriedDependencyAnalysis::LoopCarriedDependencyAnalysis(StructuredSDFG& sdfg, structured_control_flow::Sequence& node)
NEW 31	: Analysis(sdfg), node_(node) {}	×
32
33	DataDependencyAnalysis& LoopCarriedDependencyAnalysis::detailed_dda() {	166✔
34	if (!detailed_dda_) {	166✔
35	detailed_dda_ = std::make_unique<DataDependencyAnalysis>(this->sdfg_, this->node_);	166✔
36	detailed_dda_->set_detailed(true);	166✔
37	}	166✔
38	return *detailed_dda_;	166✔
39	}	166✔
40
41	void LoopCarriedDependencyAnalysis::analyze_loop(
42	analysis::AnalysisManager& /analysis_manager/, structured_control_flow::StructuredLoop& /loop/
NEW 43	) {	×
44	// Per-loop work is done inline in `run()`.
NEW 45	}	×
46
47	namespace {
48
49	bool is_undefined_user(User& user) {	4,237✔
50	// Mirror DDA::is_undefined_user — undefined users have a null vertex.
51	return user.element() == nullptr;	4,237✔
52	}	4,237✔
53
54	// Collect a user's subsets, preferring delinearized (multi-dim) subsets from
55	// MemoryLayoutAnalysis when available. ISL cannot reason precisely about
56	// linearized expressions like `i*N + j`; delinearization recovers `[i, j]` so
57	// `dependence_deltas` can compute exact distance vectors.
58	//
59	// The returned vector is index-aligned with the user's underlying memlets:
60	// for each memlet, either MLA's delinearized subset (when MLA succeeded) or
61	// the memlet's original subset (linearized fallback).
62	std::vector<data_flow::Subset> collect_subsets(User& user, MemoryLayoutAnalysis& mla) {	4,232✔
63	std::vector<data_flow::Subset> result;	4,232✔
64	auto* access_node = dynamic_cast<data_flow::AccessNode*>(user.element());	4,232✔
65	if (access_node == nullptr) {	4,232✔
NEW 66	for (auto& s : user.subsets()) result.push_back(s);	×
NEW 67	return result;	×
NEW 68	}	×
69	auto& graph = access_node->get_parent();	4,232✔
70	if (user.use() == Use::READ \|\| user.use() == Use::VIEW) {	4,232✔
71	for (auto& edge : graph.out_edges(*access_node)) {	1,004✔
72	if (auto* acc = mla.access(edge)) {	1,004✔
73	result.push_back(acc->subset);	494✔
74	} else {	510✔
75	result.push_back(edge.subset());	510✔
76	}	510✔
77	}	1,004✔
78	} else if (user.use() == Use::WRITE \|\| user.use() == Use::MOVE) {	3,297✔
79	for (auto& edge : graph.in_edges(*access_node)) {	3,297✔
80	if (auto* acc = mla.access(edge)) {	3,297✔
81	result.push_back(acc->subset);	1,567✔
82	} else {	1,730✔
83	result.push_back(edge.subset());	1,730✔
84	}	1,730✔
85	}	3,297✔
86	}	3,297✔
87	return result;	4,232✔
88	}	4,232✔
89
90	// Compute the union of iteration-distance delta sets between two users wrt
91	// `loop`'s indvar. Inner-loop indvars are marked non-constant so that the ISL
92	// formulation existentially quantifies them per-side (giving "different inner
93	// iteration" the freedom it needs).
94	//
95	// Returns {empty=true} when no loop-carried dependence exists between the two
96	// users. Returns {empty=false, deltas_str=""} for the scalar shortcut and for
97	// undefined users (dependence exists, distance unrepresentable).
98	symbolic::maps::DependenceDeltas pair_deltas(
99	StructuredSDFG& sdfg,
100	User& previous,
101	User& current,
102	analysis::AnalysisManager& analysis_manager,
103	structured_control_flow::StructuredLoop& loop
104	) {	5,670✔
105	symbolic::maps::DependenceDeltas empty_result{true, "", {}};	5,670✔
106
107	if (previous.container() != current.container()) {	5,670✔
NEW 108	return empty_result;	×
NEW 109	}	×
110
111	// Scalar shortcut: any pair of accesses to a scalar is loop-carried but the
112	// distance vector is unrepresentable.
113	auto& type = sdfg.type(previous.container());	5,670✔
114	if (dynamic_cast<const types::Scalar*>(&type)) {	5,670✔
115	return symbolic::maps::DependenceDeltas{false, "", {}};	3,550✔
116	}	3,550✔
117
118	if (is_undefined_user(previous) \|\| is_undefined_user(current)) {	2,120✔
119	return empty_result;	4✔
120	}	4✔
121
122	// Use MLA-delinearized subsets when available so ISL can reason precisely
123	// about multi-dimensional pointer accesses.
124	auto& mla = analysis_manager.get<analysis::MemoryLayoutAnalysis>();	2,116✔
125	auto previous_subsets = collect_subsets(previous, mla);	2,116✔
126	auto current_subsets = collect_subsets(current, mla);	2,116✔
127
128	auto& assumptions_analysis = analysis_manager.get<analysis::AssumptionsAnalysis>();	2,116✔
129	auto previous_scope = Users::scope(&previous);	2,116✔
130	auto previous_assumptions = assumptions_analysis.get(*previous_scope, true);	2,116✔
131	auto current_scope = Users::scope(&current);	2,116✔
132	auto current_assumptions = assumptions_analysis.get(*current_scope, true);	2,116✔
133
134	// Mark loop's indvar and all nested loop indvars as non-constant from this
135	// loop's perspective.
136	auto& loop_analysis = analysis_manager.get<analysis::LoopAnalysis>();	2,116✔
137	if (previous_assumptions.find(loop.indvar()) != previous_assumptions.end()) {	2,116✔
138	previous_assumptions.at(loop.indvar()).constant(false);	2,116✔
139	}	2,116✔
140	if (current_assumptions.find(loop.indvar()) != current_assumptions.end()) {	2,116✔
141	current_assumptions.at(loop.indvar()).constant(false);	2,116✔
142	}	2,116✔
143	for (auto& inner_loop : loop_analysis.descendants(&loop)) {	5,168✔
144	if (auto structured_loop = dynamic_cast<const structured_control_flow::StructuredLoop*>(inner_loop)) {	5,168✔
145	auto indvar = structured_loop->indvar();	5,168✔
146	if (previous_assumptions.find(indvar) != previous_assumptions.end()) {	5,168✔
147	previous_assumptions.at(indvar).constant(false);	5,168✔
148	}	5,168✔
149	if (current_assumptions.find(indvar) != current_assumptions.end()) {	5,168✔
150	current_assumptions.at(indvar).constant(false);	5,168✔
151	}	5,168✔
152	}	5,168✔
153	}	5,168✔
154
155	// Collect deltas across all subset pairs and union them.
156	isl_ctx* union_ctx = nullptr;	2,116✔
157	isl_set* accumulated = nullptr;	2,116✔
158	std::vector<std::string> result_dimensions;	2,116✔
159
160	for (auto& previous_subset : previous_subsets) {	2,116✔
161	for (auto& current_subset : current_subsets) {	2,167✔
162	auto deltas = symbolic::maps::dependence_deltas(	2,167✔
163	previous_subset, current_subset, loop.indvar(), previous_assumptions, current_assumptions	2,167✔
164	);	2,167✔
165	if (deltas.empty) {	2,167✔
166	continue;	1,479✔
167	}	1,479✔
168	if (deltas.deltas_str.empty()) {	688✔
169	if (accumulated) {	64✔
NEW 170	isl_set_free(accumulated);	×
NEW 171	isl_ctx_free(union_ctx);	×
NEW 172	}	×
173	return symbolic::maps::DependenceDeltas{false, "", {}};	64✔
174	}	64✔
175	if (!union_ctx) {	624✔
176	union_ctx = isl_ctx_alloc();	604✔
177	isl_options_set_on_error(union_ctx, ISL_ON_ERROR_CONTINUE);	604✔
178	accumulated = isl_set_read_from_str(union_ctx, deltas.deltas_str.c_str());	604✔
179	result_dimensions = deltas.dimensions;	604✔
180	} else {	604✔
181	isl_set* new_set = isl_set_read_from_str(union_ctx, deltas.deltas_str.c_str());	20✔
182	if (new_set && accumulated) {	20✔
183	accumulated = isl_set_union(accumulated, new_set);	20✔
184	} else if (new_set) {	20✔
NEW 185	isl_set_free(new_set);	×
NEW 186	}	×
187	}	20✔
188	}	624✔
189	}	2,116✔
190
191	if (!accumulated) {	2,052✔
192	if (union_ctx) {	1,448✔
NEW 193	isl_ctx_free(union_ctx);	×
NEW 194	}	×
195	return empty_result;	1,448✔
196	}	1,448✔
197
198	char* str = isl_set_to_str(accumulated);	604✔
199	if (!str) {	604✔
NEW 200	isl_set_free(accumulated);	×
NEW 201	isl_ctx_free(union_ctx);	×
NEW 202	return symbolic::maps::DependenceDeltas{false, "", {}};	×
NEW 203	}	×
204	std::string union_str(str);	604✔
205	free(str);	604✔
206
207	isl_set_free(accumulated);	604✔
208	isl_ctx_free(union_ctx);	604✔
209
210	return symbolic::maps::DependenceDeltas{false, union_str, result_dimensions};	604✔
211	}	604✔
212
213	void merge_deltas(LoopCarriedDependencyInfo& info, const symbolic::maps::DependenceDeltas& add) {	115✔
214	if (add.empty) return;	115✔
215	if (info.deltas.empty) {	115✔
NEW 216	info.deltas = add;	×
NEW 217	return;	×
NEW 218	}	×
219	if (add.deltas_str.empty() \|\| info.deltas.deltas_str.empty()) {	115✔
220	info.deltas.empty = false;	62✔
221	return;	62✔
222	}	62✔
223	isl_ctx* ctx = isl_ctx_alloc();	53✔
224	isl_options_set_on_error(ctx, ISL_ON_ERROR_CONTINUE);	53✔
225	isl_set* s1 = isl_set_read_from_str(ctx, info.deltas.deltas_str.c_str());	53✔
226	isl_set* s2 = isl_set_read_from_str(ctx, add.deltas_str.c_str());	53✔
227	if (s1 && s2) {	53✔
228	isl_set* u = isl_set_union(s1, s2);	53✔
229	char* str = u ? isl_set_to_str(u) : nullptr;	53✔
230	if (str) {	53✔
231	info.deltas.deltas_str = std::string(str);	20✔
232	free(str);	20✔
233	} else {	33✔
234	info.deltas.deltas_str = "";	33✔
235	info.deltas.dimensions.clear();	33✔
236	}	33✔
237	if (u) isl_set_free(u);	53✔
238	} else {	53✔
NEW 239	if (s1) isl_set_free(s1);	×
NEW 240	if (s2) isl_set_free(s2);	×
NEW 241	info.deltas.deltas_str = "";	×
NEW 242	info.deltas.dimensions.clear();	×
NEW 243	}	×
244	isl_ctx_free(ctx);	53✔
245	}	53✔
246
247	bool user_in_subtree(
248	User& user, const structured_control_flow::ControlFlowNode& subtree, analysis::ScopeAnalysis& scope_analysis
NEW 249	) {	×
NEW 250	auto* scope = Users::scope(&user);	×
NEW 251	while (scope != nullptr) {	×
NEW 252	if (scope == &subtree) {	×
NEW 253	return true;	×
NEW 254	}	×
NEW 255	scope = scope_analysis.parent_scope(scope);	×
NEW 256	}	×
NEW 257	return false;	×
NEW 258	}	×
259
260	} // namespace
261
262	void LoopCarriedDependencyAnalysis::run(analysis::AnalysisManager& analysis_manager) {	166✔
263	dependencies_.clear();	166✔
264	pairs_.clear();	166✔
265
266	// Drive entirely from DDA's reaching-definitions scaffold:
267	// - DDA computes per-loop boundary snapshots (upward-exposed reads,
268	// escaping definitions) — its primary job.
269	// - LCDA enumerates the cross-iteration pair space and computes delta
270	// sets via `pair_deltas` (using `symbolic::maps::dependence_deltas`).
271	//
272	// For a structured loop L with indvar i_L:
273	// pairs(L) = { (W,R, RAW, Δ_L(W,R)) : W ∈ esc(L), R ∈ ue(L),
274	// cont(W) = cont(R), Δ ≠ ∅ }
275	// ∪ { (W₁,W₂, WAW, Δ_L(W₁,W₂)) : W₁,W₂ ∈ esc(L),
276	// cont(W₁) = cont(W₂), Δ ≠ ∅ }
277	auto& dda = detailed_dda();	166✔
278	dda.run(analysis_manager);	166✔
279	auto& loop_analysis = analysis_manager.get<analysis::LoopAnalysis>();	166✔
280	auto& scope_analysis = analysis_manager.get<analysis::ScopeAnalysis>();	166✔
281
282	for (auto* loop_node : loop_analysis.loops()) {	632✔
283	auto* loop = dynamic_cast<structured_control_flow::StructuredLoop*>(loop_node);	632✔
284	if (loop == nullptr) {	632✔
NEW 285	continue;	×
NEW 286	}	×
287
288	// Restrict to loops within the analysis scope (`node_`).
289	bool in_scope = false;	632✔
290	structured_control_flow::ControlFlowNode* cur = loop;	632✔
291	while (cur != nullptr) {	2,778✔
292	if (cur == &node_) {	2,778✔
293	in_scope = true;	632✔
294	break;	632✔
295	}	632✔
296	cur = scope_analysis.parent_scope(cur);	2,146✔
297	}	2,146✔
298	if (!in_scope) {	632✔
NEW 299	continue;	×
NEW 300	}	×
301
302	// Non-monotonic / unanalyzable loops: don't register; consumers must
303	// treat absence as "no info" and fall back to safe defaults.
304	if (!loop->is_monotonic()) {	632✔
NEW 305	continue;	×
NEW 306	}	×
307	if (!dda.has_loop_boundary(*loop)) {	632✔
NEW 308	continue;	×
NEW 309	}	×
310
311	auto& ue_reads = dda.upward_exposed_reads(*loop);	632✔
312	auto& esc_defs = dda.escaping_definitions(*loop);	632✔
313
314	auto& deps = dependencies_[loop];	632✔
315	auto& pair_list = pairs_[loop];	632✔
316
317	// RAW: escaping_writes × upward_exposed_reads
318	for (auto& write_entry : esc_defs) {	2,834✔
319	auto* write = write_entry.first;	2,834✔
320	for (auto* read : ue_reads) {	44,711✔
321	if (write->container() != read->container()) {	44,711✔
322	continue;	43,765✔
323	}	43,765✔
324	auto deltas = pair_deltas(this->sdfg_, write, read, analysis_manager, *loop);	946✔
325	if (deltas.empty) continue;	946✔
326	pair_list.push_back(LoopCarriedDependencyPair{write, read, LOOP_CARRIED_DEPENDENCY_READ_WRITE, deltas});	370✔
327	auto it = deps.find(read->container());	370✔
328	if (it == deps.end()) {	370✔
329	deps[read->container()] = LoopCarriedDependencyInfo{LOOP_CARRIED_DEPENDENCY_READ_WRITE, deltas};	255✔
330	} else {	255✔
331	it->second.type = LOOP_CARRIED_DEPENDENCY_READ_WRITE;	115✔
332	merge_deltas(it->second, deltas);	115✔
333	}	115✔
334	}	370✔
335	}	2,834✔
336
337	// WAW: escaping_writes × escaping_writes (ordered pairs incl. self)
338	for (auto& w1_entry : esc_defs) {	2,834✔
339	auto* w1 = w1_entry.first;	2,834✔
340	for (auto& w2_entry : esc_defs) {	26,508✔
341	auto* w2 = w2_entry.first;	26,508✔
342	if (w1->container() != w2->container()) {	26,508✔
343	continue;	21,784✔
344	}	21,784✔
345	auto deltas = pair_deltas(this->sdfg_, w1, w2, analysis_manager, *loop);	4,724✔
346	if (deltas.empty) continue;	4,724✔
347	pair_list.push_back(LoopCarriedDependencyPair{w1, w2, LOOP_CARRIED_DEPENDENCY_WRITE_WRITE, deltas});	3,848✔
348	if (deps.find(w1->container()) == deps.end()) {	3,848✔
349	deps[w1->container()] = LoopCarriedDependencyInfo{LOOP_CARRIED_DEPENDENCY_WRITE_WRITE, deltas};	1,208✔
350	}	1,208✔
351	}	3,848✔
352	}	2,834✔
353	}	632✔
354	}	166✔
355
356	bool LoopCarriedDependencyAnalysis::available(structured_control_flow::StructuredLoop& loop) const {	192✔
357	return pairs_.find(&loop) != pairs_.end();	192✔
358	}	192✔
359
360	const std::unordered_map<std::string, LoopCarriedDependencyInfo>& LoopCarriedDependencyAnalysis::
361	dependencies(structured_control_flow::StructuredLoop& loop) const {	379✔
362	auto it = dependencies_.find(&loop);	379✔
363	assert(it != dependencies_.end() && "LoopCarriedDependencyAnalysis: loop not analyzed");	379✔
364	return it->second;	379✔
365	}	379✔
366
367	const std::vector<LoopCarriedDependencyPair>& LoopCarriedDependencyAnalysis::pairs(structured_control_flow::StructuredLoop&
368	loop) const {	126✔
369	auto it = pairs_.find(&loop);	126✔
370	assert(it != pairs_.end() && "LoopCarriedDependencyAnalysis: loop not analyzed");	126✔
371	return it->second;	126✔
372	}	126✔
373
374	std::vector<const LoopCarriedDependencyPair*> LoopCarriedDependencyAnalysis::pairs_between(
375	structured_control_flow::StructuredLoop& loop,
376	const structured_control_flow::ControlFlowNode& subtree_a,
377	const structured_control_flow::ControlFlowNode& subtree_b,
378	analysis::AnalysisManager& analysis_manager
NEW 379	) const {	×
NEW 380	std::vector<const LoopCarriedDependencyPair*> result;	×
NEW 381	auto it = pairs_.find(&loop);	×
NEW 382	if (it == pairs_.end()) {	×
NEW 383	return result;	×
NEW 384	}	×
NEW 385	auto& scope_analysis = analysis_manager.get<analysis::ScopeAnalysis>();	×
386
NEW 387	for (auto& pair : it->second) {	×
NEW 388	bool wa = user_in_subtree(*pair.writer, subtree_a, scope_analysis);	×
NEW 389	bool wb = user_in_subtree(*pair.writer, subtree_b, scope_analysis);	×
NEW 390	bool ra = user_in_subtree(*pair.reader, subtree_a, scope_analysis);	×
NEW 391	bool rb = user_in_subtree(*pair.reader, subtree_b, scope_analysis);	×
392
NEW 393	if ((wa && rb) \|\| (wb && ra)) {	×
NEW 394	result.push_back(&pair);	×
NEW 395	}	×
NEW 396	}	×
NEW 397	return result;	×
NEW 398	}	×
399
400	bool LoopCarriedDependencyAnalysis::has_loop_carried(structured_control_flow::StructuredLoop& loop) const {	2✔
401	auto it = pairs_.find(&loop);	2✔
402	if (it == pairs_.end()) return false;	2✔
403	return !it->second.empty();	2✔
404	}	2✔
405
406	bool LoopCarriedDependencyAnalysis::has_loop_carried_raw(structured_control_flow::StructuredLoop& loop) const {	208✔
407	auto it = pairs_.find(&loop);	208✔
408	if (it == pairs_.end()) return false;	208✔
409	for (auto& p : it->second) {	407✔
410	if (p.type == LOOP_CARRIED_DEPENDENCY_READ_WRITE) return true;	407✔
411	}	407✔
412	return false;	78✔
413	}	208✔
414
415	} // namespace analysis
416	} // namespace sdfg

daisytuner / docc / 25459771247

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