27263464741

Committed 10 Jun 2026 08:27AM UTC coverage: 61.383% (+0.1%) from 61.275%

Build # 27263464741

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #741 from daisytuner/mem-access-range-replacement

replaces MemAccessRangeAnalysis with MemoryLayoutAnalysis

Coverage Stats

481 of 523 new or added lines in 12 files covered. (91.97%)

44 existing lines in 11 files now uncovered.

35745 of 58233 relevant lines covered (61.38%)

757.21 hits per line

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

77.18

/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.
    symbolic::AssumptionsBounds previous_bounds(previous_assumptions);
    symbolic::AssumptionsBounds current_bounds(current_assumptions);

    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_bounds, current_bounds);
            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
) {
    if (user.element() == nullptr) {
        return false;
    }
    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;
}

bool LoopCarriedDependencyAnalysis::has_loop_carried_hazard(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_WRITE_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)
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/
43	) {	×
44	// Per-loop work is done inline in `run()`.
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✔
66	for (auto& s : user.subsets()) result.push_back(s);	×
67	return result;	×
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);	998✔
74	} else {	998✔
75	result.push_back(edge.subset());	6✔
76	}	6✔
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);	3,297✔
82	} else {	3,297✔
UNCOV 83	result.push_back(edge.subset());	×
UNCOV 84	}	×
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✔
108	return empty_result;	×
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	symbolic::AssumptionsBounds previous_bounds(previous_assumptions);	2,116✔
157	symbolic::AssumptionsBounds current_bounds(current_assumptions);	2,116✔
158
159	isl_ctx* union_ctx = nullptr;	2,116✔
160	isl_set* accumulated = nullptr;	2,116✔
161	std::vector<std::string> result_dimensions;	2,116✔
162
163	for (auto& previous_subset : previous_subsets) {	2,116✔
164	for (auto& current_subset : current_subsets) {	2,167✔
165	auto deltas = symbolic::maps::	2,167✔
166	dependence_deltas(previous_subset, current_subset, loop.indvar(), previous_bounds, current_bounds);	2,167✔
167	if (deltas.empty) {	2,167✔
168	continue;	1,479✔
169	}	1,479✔
170	if (deltas.deltas_str.empty()) {	688✔
171	if (accumulated) {	79✔
172	isl_set_free(accumulated);	×
173	isl_ctx_free(union_ctx);	×
174	}	×
175	return symbolic::maps::DependenceDeltas{false, "", {}};	79✔
176	}	79✔
177	if (!union_ctx) {	609✔
178	union_ctx = isl_ctx_alloc();	589✔
179	isl_options_set_on_error(union_ctx, ISL_ON_ERROR_CONTINUE);	589✔
180	accumulated = isl_set_read_from_str(union_ctx, deltas.deltas_str.c_str());	589✔
181	result_dimensions = deltas.dimensions;	589✔
182	} else {	589✔
183	isl_set* new_set = isl_set_read_from_str(union_ctx, deltas.deltas_str.c_str());	20✔
184	if (new_set && accumulated) {	20✔
185	accumulated = isl_set_union(accumulated, new_set);	20✔
186	} else if (new_set) {	20✔
187	isl_set_free(new_set);	×
188	}	×
189	}	20✔
190	}	609✔
191	}	2,116✔
192
193	if (!accumulated) {	2,037✔
194	if (union_ctx) {	1,448✔
195	isl_ctx_free(union_ctx);	×
196	}	×
197	return empty_result;	1,448✔
198	}	1,448✔
199
200	char* str = isl_set_to_str(accumulated);	589✔
201	if (!str) {	589✔
202	isl_set_free(accumulated);	×
203	isl_ctx_free(union_ctx);	×
204	return symbolic::maps::DependenceDeltas{false, "", {}};	×
205	}	×
206	std::string union_str(str);	589✔
207	free(str);	589✔
208
209	isl_set_free(accumulated);	589✔
210	isl_ctx_free(union_ctx);	589✔
211
212	return symbolic::maps::DependenceDeltas{false, union_str, result_dimensions};	589✔
213	}	589✔
214
215	void merge_deltas(LoopCarriedDependencyInfo& info, const symbolic::maps::DependenceDeltas& add) {	115✔
216	if (add.empty) return;	115✔
217	if (info.deltas.empty) {	115✔
218	info.deltas = add;	×
219	return;	×
220	}	×
221	if (add.deltas_str.empty() \|\| info.deltas.deltas_str.empty()) {	115✔
222	info.deltas.empty = false;	60✔
223	return;	60✔
224	}	60✔
225	isl_ctx* ctx = isl_ctx_alloc();	55✔
226	isl_options_set_on_error(ctx, ISL_ON_ERROR_CONTINUE);	55✔
227	isl_set* s1 = isl_set_read_from_str(ctx, info.deltas.deltas_str.c_str());	55✔
228	isl_set* s2 = isl_set_read_from_str(ctx, add.deltas_str.c_str());	55✔
229	if (s1 && s2) {	55✔
230	isl_set* u = isl_set_union(s1, s2);	55✔
231	char* str = u ? isl_set_to_str(u) : nullptr;	55✔
232	if (str) {	55✔
233	info.deltas.deltas_str = std::string(str);	22✔
234	free(str);	22✔
235	} else {	33✔
236	info.deltas.deltas_str = "";	33✔
237	info.deltas.dimensions.clear();	33✔
238	}	33✔
239	if (u) isl_set_free(u);	55✔
240	} else {	55✔
241	if (s1) isl_set_free(s1);	×
242	if (s2) isl_set_free(s2);	×
243	info.deltas.deltas_str = "";	×
244	info.deltas.dimensions.clear();	×
245	}	×
246	isl_ctx_free(ctx);	55✔
247	}	55✔
248
249	bool user_in_subtree(
250	User& user, const structured_control_flow::ControlFlowNode& subtree, analysis::ScopeAnalysis& scope_analysis
251	) {	×
252	if (user.element() == nullptr) {	×
253	return false;	×
254	}	×
255	auto* scope = Users::scope(&user);	×
256	while (scope != nullptr) {	×
257	if (scope == &subtree) {	×
258	return true;	×
259	}	×
260	scope = scope_analysis.parent_scope(scope);	×
261	}	×
262	return false;	×
263	}	×
264
265	} // namespace
266
267	void LoopCarriedDependencyAnalysis::run(analysis::AnalysisManager& analysis_manager) {	166✔
268	dependencies_.clear();	166✔
269	pairs_.clear();	166✔
270
271	// Drive entirely from DDA's reaching-definitions scaffold:
272	// - DDA computes per-loop boundary snapshots (upward-exposed reads,
273	// escaping definitions) — its primary job.
274	// - LCDA enumerates the cross-iteration pair space and computes delta
275	// sets via `pair_deltas` (using `symbolic::maps::dependence_deltas`).
276	//
277	// For a structured loop L with indvar i_L:
278	// pairs(L) = { (W,R, RAW, Δ_L(W,R)) : W ∈ esc(L), R ∈ ue(L),
279	// cont(W) = cont(R), Δ ≠ ∅ }
280	// ∪ { (W₁,W₂, WAW, Δ_L(W₁,W₂)) : W₁,W₂ ∈ esc(L),
281	// cont(W₁) = cont(W₂), Δ ≠ ∅ }
282	auto& dda = detailed_dda();	166✔
283	dda.run(analysis_manager);	166✔
284	auto& loop_analysis = analysis_manager.get<analysis::LoopAnalysis>();	166✔
285	auto& scope_analysis = analysis_manager.get<analysis::ScopeAnalysis>();	166✔
286
287	for (auto* loop_node : loop_analysis.loops()) {	632✔
288	auto* loop = dynamic_cast<structured_control_flow::StructuredLoop*>(loop_node);	632✔
289	if (loop == nullptr) {	632✔
290	continue;	×
291	}	×
292
293	// Restrict to loops within the analysis scope (`node_`).
294	bool in_scope = false;	632✔
295	structured_control_flow::ControlFlowNode* cur = loop;	632✔
296	while (cur != nullptr) {	2,778✔
297	if (cur == &node_) {	2,778✔
298	in_scope = true;	632✔
299	break;	632✔
300	}	632✔
301	cur = scope_analysis.parent_scope(cur);	2,146✔
302	}	2,146✔
303	if (!in_scope) {	632✔
304	continue;	×
305	}	×
306
307	// Non-monotonic / unanalyzable loops: don't register; consumers must
308	// treat absence as "no info" and fall back to safe defaults.
309	if (!loop->is_monotonic()) {	632✔
310	continue;	×
311	}	×
312	if (!dda.has_loop_boundary(*loop)) {	632✔
313	continue;	×
314	}	×
315
316	auto& ue_reads = dda.upward_exposed_reads(*loop);	632✔
317	auto& esc_defs = dda.escaping_definitions(*loop);	632✔
318
319	auto& deps = dependencies_[loop];	632✔
320	auto& pair_list = pairs_[loop];	632✔
321
322	// RAW: escaping_writes × upward_exposed_reads
323	for (auto& write_entry : esc_defs) {	2,834✔
324	auto* write = write_entry.first;	2,834✔
325	for (auto* read : ue_reads) {	44,711✔
326	if (write->container() != read->container()) {	44,711✔
327	continue;	43,765✔
328	}	43,765✔
329	auto deltas = pair_deltas(this->sdfg_, write, read, analysis_manager, *loop);	946✔
330	if (deltas.empty) continue;	946✔
331	pair_list.push_back(LoopCarriedDependencyPair{write, read, LOOP_CARRIED_DEPENDENCY_READ_WRITE, deltas});	370✔
332	auto it = deps.find(read->container());	370✔
333	if (it == deps.end()) {	370✔
334	deps[read->container()] = LoopCarriedDependencyInfo{LOOP_CARRIED_DEPENDENCY_READ_WRITE, deltas};	255✔
335	} else {	255✔
336	it->second.type = LOOP_CARRIED_DEPENDENCY_READ_WRITE;	115✔
337	merge_deltas(it->second, deltas);	115✔
338	}	115✔
339	}	370✔
340	}	2,834✔
341
342	// WAW: escaping_writes × escaping_writes (ordered pairs incl. self)
343	for (auto& w1_entry : esc_defs) {	2,834✔
344	auto* w1 = w1_entry.first;	2,834✔
345	for (auto& w2_entry : esc_defs) {	26,508✔
346	auto* w2 = w2_entry.first;	26,508✔
347	if (w1->container() != w2->container()) {	26,508✔
348	continue;	21,784✔
349	}	21,784✔
350	auto deltas = pair_deltas(this->sdfg_, w1, w2, analysis_manager, *loop);	4,724✔
351	if (deltas.empty) continue;	4,724✔
352	pair_list.push_back(LoopCarriedDependencyPair{w1, w2, LOOP_CARRIED_DEPENDENCY_WRITE_WRITE, deltas});	3,848✔
353	if (deps.find(w1->container()) == deps.end()) {	3,848✔
354	deps[w1->container()] = LoopCarriedDependencyInfo{LOOP_CARRIED_DEPENDENCY_WRITE_WRITE, deltas};	1,208✔
355	}	1,208✔
356	}	3,848✔
357	}	2,834✔
358	}	632✔
359	}	166✔
360
361	bool LoopCarriedDependencyAnalysis::available(structured_control_flow::StructuredLoop& loop) const {	192✔
362	return pairs_.find(&loop) != pairs_.end();	192✔
363	}	192✔
364
365	const std::unordered_map<std::string, LoopCarriedDependencyInfo>& LoopCarriedDependencyAnalysis::
366	dependencies(structured_control_flow::StructuredLoop& loop) const {	379✔
367	auto it = dependencies_.find(&loop);	379✔
368	assert(it != dependencies_.end() && "LoopCarriedDependencyAnalysis: loop not analyzed");	379✔
369	return it->second;	379✔
370	}	379✔
371
372	const std::vector<LoopCarriedDependencyPair>& LoopCarriedDependencyAnalysis::pairs(structured_control_flow::StructuredLoop&
373	loop) const {	126✔
374	auto it = pairs_.find(&loop);	126✔
375	assert(it != pairs_.end() && "LoopCarriedDependencyAnalysis: loop not analyzed");	126✔
376	return it->second;	126✔
377	}	126✔
378
379	std::vector<const LoopCarriedDependencyPair*> LoopCarriedDependencyAnalysis::pairs_between(
380	structured_control_flow::StructuredLoop& loop,
381	const structured_control_flow::ControlFlowNode& subtree_a,
382	const structured_control_flow::ControlFlowNode& subtree_b,
383	analysis::AnalysisManager& analysis_manager
384	) const {	×
385	std::vector<const LoopCarriedDependencyPair*> result;	×
386	auto it = pairs_.find(&loop);	×
387	if (it == pairs_.end()) {	×
388	return result;	×
389	}	×
390	auto& scope_analysis = analysis_manager.get<analysis::ScopeAnalysis>();	×
391
392	for (auto& pair : it->second) {	×
393	bool wa = user_in_subtree(*pair.writer, subtree_a, scope_analysis);	×
394	bool wb = user_in_subtree(*pair.writer, subtree_b, scope_analysis);	×
395	bool ra = user_in_subtree(*pair.reader, subtree_a, scope_analysis);	×
396	bool rb = user_in_subtree(*pair.reader, subtree_b, scope_analysis);	×
397
398	if ((wa && rb) \|\| (wb && ra)) {	×
399	result.push_back(&pair);	×
400	}	×
401	}	×
402	return result;	×
403	}	×
404
405	bool LoopCarriedDependencyAnalysis::has_loop_carried(structured_control_flow::StructuredLoop& loop) const {	2✔
406	auto it = pairs_.find(&loop);	2✔
407	if (it == pairs_.end()) return false;	2✔
408	return !it->second.empty();	2✔
409	}	2✔
410
411	bool LoopCarriedDependencyAnalysis::has_loop_carried_raw(structured_control_flow::StructuredLoop& loop) const {	3✔
412	auto it = pairs_.find(&loop);	3✔
413	if (it == pairs_.end()) return false;	3✔
414	for (auto& p : it->second) {	3✔
415	if (p.type == LOOP_CARRIED_DEPENDENCY_READ_WRITE) return true;	3✔
416	}	3✔
417	return false;	1✔
418	}	3✔
419
420	bool LoopCarriedDependencyAnalysis::has_loop_carried_hazard(structured_control_flow::StructuredLoop& loop) const {	205✔
421	auto it = pairs_.find(&loop);	205✔
422	if (it == pairs_.end()) return false;	205✔
423	for (auto& p : it->second) {	404✔
424	if (p.type != LOOP_CARRIED_DEPENDENCY_WRITE_WRITE) return true;	404✔
425	}	404✔
426	return false;	77✔
427	}	205✔
428
429	} // namespace analysis
430	} // namespace sdfg

daisytuner / docc / 27263464741

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