26556322966

Committed 27 May 2026 03:45PM UTC coverage: 60.869% (-0.02%) from 60.886%

Build # 26556322966

Build Type

push

github

Committed by

web-flow

Commit Message

Libnode ptr edges (#719)

Migrating SDFGs to treat pointers as inputs to libNodes / Calls as scalars.
A pointer will only appear in an output edge if its actually returned from the function (like malloc).

* Stdlib, Blas and Tensor Matmul nodes were migrated to this new format. Other, currently transitory Tensor Nodes are not yet migrated.
* DOCC version was bumped to incorporate previous docc-llvm versions (up to 0.4.0) that had been counted separately.
! Until all passes consider the use / leak of pointers as uncertainty / hiding potential writes, TensorNodes are declared as general side-effect.
* Lots of utility functions to centralize the creation (and edges) of various libNodes that needed to be changed.
* Fixed & unified docc paths across python and llvm front-ends.
* Skip BlockFusion test that fails to its libNodes currently having side effects
~ Prevent a crash in DotViz when using symbolic offsets into structs
* Removing old ConstProp pass, it is not safe for the new pointer representation and should not be all too critical

Coverage Stats

961 of 1749 new or added lines in 52 files covered. (54.95%)

87 existing lines in 28 files now uncovered.

35225 of 57870 relevant lines covered (60.87%)

11046.32 hits per line

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

91.21

/sdfg/src/analysis/data_dependency_analysis.cpp

#include "sdfg/analysis/data_dependency_analysis.h"

#include <cassert>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

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

#include "sdfg/analysis/analysis.h"
#include "sdfg/analysis/loop_analysis.h"
#include "sdfg/structured_sdfg.h"
#include "sdfg/symbolic/maps.h"
#include "sdfg/symbolic/sets.h"

namespace sdfg {
namespace analysis {

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

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

void DataDependencyAnalysis::run(analysis::AnalysisManager& analysis_manager) {
    results_.clear();
    undefined_users_.clear();
    loop_boundaries_.clear();

    std::unordered_set<User*> undefined;
    std::unordered_map<User*, std::unordered_set<User*>> open_definitions;
    std::unordered_map<User*, std::unordered_set<User*>> closed_definitions;

    visit_sequence(analysis_manager, node_, undefined, open_definitions, closed_definitions);

    for (auto& entry : open_definitions) {
        closed_definitions.insert(entry);
    }

    for (auto& entry : closed_definitions) {
        if (results_.find(entry.first->container()) == results_.end()) {
            results_.insert({entry.first->container(), {}});
        }
        results_.at(entry.first->container()).insert(entry);
    }
};

/****** Visitor API ******/

void DataDependencyAnalysis::visit_block(
    analysis::AnalysisManager& analysis_manager,
    structured_control_flow::Block& block,
    std::unordered_set<User*>& undefined,
    std::unordered_map<User*, std::unordered_set<User*>>& open_definitions,
    std::unordered_map<User*, std::unordered_set<User*>>& closed_definitions
) {
    auto& dominance_analysis = analysis_manager.get<analysis::DominanceAnalysis>();
    auto& users = analysis_manager.get<analysis::Users>();

    auto& dataflow = block.dataflow();

    for (auto node : dataflow.topological_sort()) {
        if (dynamic_cast<data_flow::ConstantNode*>(node) != nullptr) {
            continue;
        }

        if (auto access_node = dynamic_cast<data_flow::AccessNode*>(node)) {
            auto& access_node_type = sdfg_.type(access_node->data());
            if (!symbolic::is_pointer(symbolic::symbol(access_node->data()))) {
                if (dataflow.in_degree(*node) > 0) {
                    Use use = Use::WRITE;
                    for (auto& iedge : dataflow.in_edges(*access_node)) {
                        if (iedge.type() == data_flow::MemletType::Reference ||
                            iedge.type() == data_flow::MemletType::Dereference_Src) {
                            use = Use::MOVE;
                            break;
                        }
                    }

                    if (use == Use::WRITE) {
                        auto current_user = users.get_user(access_node->data(), access_node, use);

                        // Close open definitions if possible
                        std::unordered_map<User*, std::unordered_set<User*>> to_close;
                        for (auto& user : open_definitions) {
                            if (this->closes(analysis_manager, *user.first, *current_user, false)) {
                                to_close.insert(user);
                            }
                        }
                        for (auto& user : to_close) {
                            open_definitions.erase(user.first);
                            closed_definitions.insert(user);
                        }

                        // Start new open definition
                        open_definitions.insert({current_user, {}});
                    }
                }
                if (dataflow.out_degree(*access_node) > 0) {
                    Use use = Use::READ;
                    for (auto& oedge : dataflow.out_edges(*access_node)) {
                        if (access_node_type.type_id() == types::TypeID::Pointer &&
                            oedge.is_src_pointed_to_address_leak(access_node_type)) {
                            if (auto* libConsumer = dynamic_cast<data_flow::LibraryNode*>(&oedge.dst())) {
                                auto access = libConsumer->pointer_access_type(oedge);
                                if (!access || !access->no_capture()) {
                                    use = Use::MOVE; // we know nothing and cannot say anything reliable. Consider the
                                                     // libNode having side effects
                                    break;
                                } else {
                                    if (access->may_contain_reads()) {
                                        // TODO let handle as a normal read
                                        use = Use::VIEW;
                                    } else if (access->may_contain_writes()) {
                                        // handle as a normal write
                                        use = Use::WRITE;
                                        break;
                                    }
                                }
                            } else {
                                use = Use::VIEW;
                                break;
                            }
                        } else if (oedge.type() == data_flow::MemletType::Reference ||
                                   oedge.type() == data_flow::MemletType::Dereference_Dst) {
                            use = Use::VIEW;
                            break;
                        }
                    }

                    if (use == Use::READ) {
                        auto current_user = users.get_user(access_node->data(), access_node, use);

                        // Assign to open definitions
                        bool found_user = false;
                        bool found_undefined_user = false;
                        for (auto& user : open_definitions) {
                            if (this->depends(analysis_manager, *user.first, *current_user)) {
                                user.second.insert(current_user);
                                found_user = true;
                                found_undefined_user = this->is_undefined_user(*user.first);
                            }
                        }
                        // If no definition found, undefined user found, or
                        // the read's subset footprint is only partially
                        // covered by the matching open writers, mark as
                        // upward-exposed (undefined). `depends` uses
                        // intersect-any across the cartesian product of
                        // subsets, which silently swallows partial-cover
                        // multi-subset reads (e.g. an access node with two
                        // out-edges where only one edge is killed inside
                        // the current scope).
                        if (!found_user || found_undefined_user ||
                            !this->fully_covered(analysis_manager, *current_user, open_definitions)) {
                            undefined.insert(current_user);
                        }
                    }
                }
            }
        } else if (auto library_node = dynamic_cast<data_flow::LibraryNode*>(node)) {
            for (auto& symbol : library_node->symbols()) {
                auto current_user = users.get_user(symbol->get_name(), library_node, Use::READ);

                // Assign to open definitions
                bool found_user = false;
                bool found_undefined_user = false;
                for (auto& user : open_definitions) {
                    if (this->depends(analysis_manager, *user.first, *current_user)) {
                        user.second.insert(current_user);
                        found_user = true;
                        found_undefined_user = this->is_undefined_user(*current_user);
                    }
                }
                // If no definition found or undefined user found, mark as undefined
                if (!found_user || found_undefined_user) {
                    undefined.insert(current_user);
                }
            }
        }

        for (auto& oedge : dataflow.out_edges(*node)) {
            std::unordered_set<std::string> used;
            for (auto& dim : oedge.subset()) {
                for (auto atom : symbolic::atoms(dim)) {
                    used.insert(atom->get_name());
                }
            }
            for (auto& atom : used) {
                auto current_user = users.get_user(atom, &oedge, Use::READ);

                // Assign to open definitions
                bool found_user = false;
                bool found_undefined_user = false;
                for (auto& user : open_definitions) {
                    if (this->depends(analysis_manager, *user.first, *current_user)) {
                        user.second.insert(current_user);
                        found_user = true;
                        found_undefined_user = this->is_undefined_user(*user.first);
                    }
                }
                // If no definition found or undefined user found, mark as undefined
                if (!found_user || found_undefined_user) {
                    undefined.insert(current_user);
                }
            }
        }
    }
}

void DataDependencyAnalysis::visit_for(
    analysis::AnalysisManager& analysis_manager,
    structured_control_flow::StructuredLoop& for_loop,
    std::unordered_set<User*>& undefined,
    std::unordered_map<User*, std::unordered_set<User*>>& open_definitions,
    std::unordered_map<User*, std::unordered_set<User*>>& closed_definitions
) {
    auto& users = analysis_manager.get<analysis::Users>();

    // Init - Read
    for (auto atom : symbolic::atoms(for_loop.init())) {
        auto current_user = users.get_user(atom->get_name(), &for_loop, Use::READ, true);

        // Assign to open definitions
        bool found_user = false;
        bool found_undefined_user = false;
        for (auto& user : open_definitions) {
            if (this->depends(analysis_manager, *user.first, *current_user)) {
                user.second.insert(current_user);
                found_user = true;
                found_undefined_user = this->is_undefined_user(*user.first);
            }
        }
        // If no definition found or undefined user found, mark as undefined
        if (!found_user || found_undefined_user) {
            undefined.insert(current_user);
        }
    }

    // Init - Write
    {
        // Write Induction Variable
        auto current_user = users.get_user(for_loop.indvar()->get_name(), &for_loop, Use::WRITE, true);

        // Close open definitions if possible
        std::unordered_map<User*, std::unordered_set<User*>> to_close;
        for (auto& user : open_definitions) {
            if (this->closes(analysis_manager, *user.first, *current_user, true)) {
                to_close.insert(user);
            }
        }
        for (auto& user : to_close) {
            open_definitions.erase(user.first);
            closed_definitions.insert(user);
        }

        // Start new open definition
        open_definitions.insert({current_user, {}});
    }

    // Update - Write
    {
        auto current_user = users.get_user(for_loop.indvar()->get_name(), &for_loop, Use::WRITE, false, false, true);
        open_definitions.insert({current_user, {}});
    }

    // Condition - Read
    for (auto atom : symbolic::atoms(for_loop.condition())) {
        auto current_user = users.get_user(atom->get_name(), &for_loop, Use::READ, false, true);

        // Assign to open definitions
        bool found_user = false;
        bool found_undefined_user = false;
        for (auto& user : open_definitions) {
            if (this->depends(analysis_manager, *user.first, *current_user)) {
                user.second.insert(current_user);
                found_user = true;
                found_undefined_user = this->is_undefined_user(*user.first);
            }
        }
        // If no definition found or undefined user found, mark as undefined
        if (!found_user || found_undefined_user) {
            undefined.insert(current_user);
        }
    }

    std::unordered_map<User*, std::unordered_set<User*>> open_definitions_for;
    std::unordered_map<User*, std::unordered_set<User*>> closed_definitions_for;
    std::unordered_set<User*> undefined_for;

    // Add assumptions for body
    visit_sequence(analysis_manager, for_loop.root(), undefined_for, open_definitions_for, closed_definitions_for);

    // Update - Read
    for (auto atom : symbolic::atoms(for_loop.update())) {
        auto current_user = users.get_user(atom->get_name(), &for_loop, Use::READ, false, false, true);

        // Assign to open definitions
        bool found_user = false;
        bool found_undefined_user = false;
        for (auto& user : open_definitions_for) {
            if (this->depends(analysis_manager, *user.first, *current_user)) {
                user.second.insert(current_user);
                found_user = true;
                found_undefined_user = this->is_undefined_user(*user.first);
            }
        }
        // If no definition found or undefined user found, mark as undefined
        if (!found_user || found_undefined_user) {
            undefined_for.insert(current_user);
        }
    }

    // Merge for with outside
    auto& dominance_analysis = analysis_manager.get<analysis::DominanceAnalysis>();

    // Closed definitions are simply merged
    for (auto& entry : closed_definitions_for) {
        closed_definitions.insert(entry);
    }

    // Undefined reads are matched or forwarded
    for (auto open_read : undefined_for) {
        // Simple check: no match or undefined user
        std::unordered_set<User*> frontier;
        bool found = false;
        bool found_undefined_user = false;
        for (auto& entry : open_definitions) {
            if (intersects(*entry.first, *open_read, analysis_manager)) {
                entry.second.insert(open_read);
                found = true;
                found_undefined_user = this->is_undefined_user(*entry.first);
                frontier.insert(entry.first);
            }
        }
        if (!found || found_undefined_user) {
            undefined.insert(open_read);
            continue;
        }

        // Users found, check if they fully cover the read
        bool covered = false;
        for (auto& entry : frontier) {
            if (!dominance_analysis.dominates(*entry, *open_read)) {
                continue;
            }
            bool covers = supersedes_restrictive(*open_read, *entry, analysis_manager);
            if (covers) {
                covered = true;
                break;
            }
        }
        if (!covered) {
            undefined.insert(open_read);
        }
    }

    // Open definitions may close outside open definitions after loop
    std::unordered_set<User*> to_close;
    for (auto& previous : open_definitions) {
        for (auto& user : open_definitions_for) {
            if (this->closes(analysis_manager, *previous.first, *user.first, true)) {
                to_close.insert(previous.first);
                break;
            }
        }
    }
    for (auto& user : to_close) {
        closed_definitions.insert({user, open_definitions.at(user)});
        open_definitions.erase(user);
    }

    // Cross-iteration linkage for SCALARS only.
    //
    // An in-body upward-exposed read may be satisfied (in some non-first
    // iteration) by an in-body open writer. We must record those
    // (write -> read) edges in `open_definitions_for` so that public
    // queries like `defined_by(read)` return the in-body writer in
    // addition to any pre-loop write -- otherwise consumers (e.g.
    // SymbolPropagation) treat the read as having a single dominating
    // definition and incorrectly fold the loop-carried value away.
    //
    // We restrict to scalar containers because:
    //   - For scalars, every access touches the same cell, so the
    //     prior-iteration writer always reaches the in-body read --
    //     this is sound and precise.
    //   - For arrays, deciding whether a writer flows across iterations
    //     requires precise per-pair delta analysis (done in LCDA).
    //     Adding edges via the over-approximate `depends` predicate
    //     would create spurious in-body RAW links that pollute
    //     consumers reasoning about precise dataflow on arrays.
    //
    // This must run BEFORE the snapshot below and BEFORE merging into the
    // outer `open_definitions`, since both perform by-value copies of the
    // (writer -> readers) sets we are mutating.
    for (auto* open_read : undefined_for) {
        auto& type = this->sdfg_.type(open_read->container());
        if (!dynamic_cast<const types::Scalar*>(&type)) continue;
        for (auto& write_entry : open_definitions_for) {
            if (write_entry.first->container() != open_read->container()) continue;
            if (this->is_undefined_user(*write_entry.first)) continue;
            write_entry.second.insert(open_read);
        }
    }

    // Snapshot loop boundary sets so LoopCarriedDependencyAnalysis can compute LCDs.
    loop_boundaries_[&for_loop] = std::make_pair(undefined_for, open_definitions_for);

    // Add open definitions from for to outside
    for (auto& entry : open_definitions_for) {
        open_definitions.insert(entry);
    }
}

void DataDependencyAnalysis::visit_if_else(
    analysis::AnalysisManager& analysis_manager,
    structured_control_flow::IfElse& if_else,
    std::unordered_set<User*>& undefined,
    std::unordered_map<User*, std::unordered_set<User*>>& open_definitions,
    std::unordered_map<User*, std::unordered_set<User*>>& closed_definitions
) {
    auto& users = analysis_manager.get<analysis::Users>();

    // Read Conditions
    for (size_t i = 0; i < if_else.size(); i++) {
        auto child = if_else.at(i).second;
        for (auto atom : symbolic::atoms(child)) {
            auto current_user = users.get_user(atom->get_name(), &if_else, Use::READ);

            bool found_user = false;
            bool found_undefined_user = false;
            for (auto& user : open_definitions) {
                if (this->depends(analysis_manager, *user.first, *current_user)) {
                    user.second.insert(current_user);
                    found_user = true;
                    found_undefined_user = this->is_undefined_user(*user.first);
                }
            }
            // If no definition found or undefined user found, mark as undefined
            if (!found_user || found_undefined_user) {
                undefined.insert(current_user);
            }
        }
    }

    std::vector<std::unordered_set<User*>> undefined_branches(if_else.size());
    std::vector<std::unordered_map<User*, std::unordered_set<User*>>> open_definitions_branches(if_else.size());
    std::vector<std::unordered_map<User*, std::unordered_set<User*>>> closed_definitionss_branches(if_else.size());
    for (size_t i = 0; i < if_else.size(); i++) {
        auto& child = if_else.at(i).first;
        visit_sequence(
            analysis_manager,
            child,
            undefined_branches.at(i),
            open_definitions_branches.at(i),
            closed_definitionss_branches.at(i)
        );
    }

    // merge partial open reads
    for (size_t i = 0; i < if_else.size(); i++) {
        for (auto& entry : undefined_branches.at(i)) {
            bool found_user = false;
            bool found_undefined_user = false;
            for (auto& user : open_definitions) {
                if (this->depends(analysis_manager, *user.first, *entry)) {
                    user.second.insert(entry);
                    found_user = true;
                    found_undefined_user = this->is_undefined_user(*user.first);
                }
            }
            // If no definition found or undefined user found, mark as undefined
            if (!found_user || found_undefined_user) {
                undefined.insert(entry);
            }
        }
    }

    // merge closed writes
    for (auto& closing : closed_definitionss_branches) {
        for (auto& entry : closing) {
            closed_definitions.insert(entry);
        }
    }

    // Close open reads_after_writes for complete branches
    if (if_else.is_complete()) {
        std::unordered_map<User*, std::unordered_set<User*>> to_close;
        std::unordered_set<std::string> candidates;
        std::unordered_set<std::string> candidates_tmp;

        /* Complete close open reads_after_writes
        1. get candidates from first iteration
        2. iterate over all branches and prune candidates
        3. find prior writes for remaining candidates
        4. close open reads_after_writes for all candidates
        */
        for (auto& entry : open_definitions_branches.at(0)) {
            candidates.insert(entry.first->container());
        }
        for (auto& entry : closed_definitionss_branches.at(0)) {
            candidates.insert(entry.first->container());
        }

        for (size_t i = 1; i < if_else.size(); i++) {
            for (auto& entry : open_definitions_branches.at(i)) {
                if (candidates.find(entry.first->container()) != candidates.end()) {
                    candidates_tmp.insert(entry.first->container());
                }
            }
            candidates.swap(candidates_tmp);
            candidates_tmp.clear();
        }

        for (auto& entry : open_definitions) {
            if (candidates.find(entry.first->container()) != candidates.end()) {
                to_close.insert(entry);
            }
        }

        for (auto& entry : to_close) {
            open_definitions.erase(entry.first);
            closed_definitions.insert(entry);
        }
    } else {
        // Incomplete if-else

        // In order to determine whether a new read is undefined
        // we would need to check whether all open definitions
        // jointly dominate the read.
        // Since this is expensive, we apply a trick:
        // For incomplete if-elses and any newly opened definition in
        // any branch, we add an artificial undefined user for that container.
        // If we encounter this user later, we know that not all branches defined it.
        // Hence, we can mark the read as (partially) undefined.

        for (auto& branch : open_definitions_branches) {
            for (auto& open_definition : branch) {
                auto write = open_definition.first;
                auto artificial_user = std::make_unique<
                    User>(boost::graph_traits<graph::Graph>::null_vertex(), write->container(), nullptr, Use::WRITE);
                this->undefined_users_.push_back(std::move(artificial_user));
                open_definitions.insert({this->undefined_users_.back().get(), {}});
            }
        }
    }

    // Add open definitions from branches to outside
    for (auto& branch : open_definitions_branches) {
        for (auto& entry : branch) {
            open_definitions.insert(entry);
        }
    }
}

void DataDependencyAnalysis::visit_while(
    analysis::AnalysisManager& analysis_manager,
    structured_control_flow::While& while_loop,
    std::unordered_set<User*>& undefined,
    std::unordered_map<User*, std::unordered_set<User*>>& open_definitions,
    std::unordered_map<User*, std::unordered_set<User*>>& closed_definitions
) {
    std::unordered_map<User*, std::unordered_set<User*>> open_definitions_while;
    std::unordered_map<User*, std::unordered_set<User*>> closed_definitions_while;
    std::unordered_set<User*> undefined_while;

    visit_sequence(analysis_manager, while_loop.root(), undefined_while, open_definitions_while, closed_definitions_while);

    // Scope-local closed definitions
    for (auto& entry : closed_definitions_while) {
        closed_definitions.insert(entry);
    }

    for (auto open_read : undefined_while) {
        // Over-Approximation: Add loop-carried dependencies for all open reads
        for (auto& entry : open_definitions_while) {
            if (entry.first->container() == open_read->container()) {
                entry.second.insert(open_read);
            }
        }

        // Connect to outside
        bool found = false;
        for (auto& entry : open_definitions) {
            if (entry.first->container() == open_read->container()) {
                entry.second.insert(open_read);
                found = true;
            }
        }
        if (!found) {
            undefined.insert(open_read);
        }
    }

    // Add open definitions from while to outside
    for (auto& entry : open_definitions_while) {
        open_definitions.insert(entry);
    }
}

void DataDependencyAnalysis::visit_return(
    analysis::AnalysisManager& analysis_manager,
    structured_control_flow::Return& return_statement,
    std::unordered_set<User*>& undefined,
    std::unordered_map<User*, std::unordered_set<User*>>& open_definitions,
    std::unordered_map<User*, std::unordered_set<User*>>& closed_definitions
) {
    auto& users = analysis_manager.get<analysis::Users>();

    if (return_statement.is_data() && !return_statement.data().empty()) {
        auto current_user = users.get_user(return_statement.data(), &return_statement, Use::READ);

        bool found = false;
        for (auto& user : open_definitions) {
            if (user.first->container() == return_statement.data()) {
                user.second.insert(current_user);
                found = true;
            }
        }
        if (!found) {
            undefined.insert(current_user);
        }
    }

    // close all open reads_after_writes
    for (auto& entry : open_definitions) {
        closed_definitions.insert(entry);
    }
    open_definitions.clear();
}

void DataDependencyAnalysis::visit_sequence(
    analysis::AnalysisManager& analysis_manager,
    structured_control_flow::Sequence& sequence,
    std::unordered_set<User*>& undefined,
    std::unordered_map<User*, std::unordered_set<User*>>& open_definitions,
    std::unordered_map<User*, std::unordered_set<User*>>& closed_definitions
) {
    auto& users = analysis_manager.get<analysis::Users>();

    for (size_t i = 0; i < sequence.size(); i++) {
        auto child = sequence.at(i);
        if (auto block = dynamic_cast<structured_control_flow::Block*>(&child.first)) {
            visit_block(analysis_manager, *block, undefined, open_definitions, closed_definitions);
        } else if (auto for_loop = dynamic_cast<structured_control_flow::StructuredLoop*>(&child.first)) {
            visit_for(analysis_manager, *for_loop, undefined, open_definitions, closed_definitions);
        } else if (auto if_else = dynamic_cast<structured_control_flow::IfElse*>(&child.first)) {
            visit_if_else(analysis_manager, *if_else, undefined, open_definitions, closed_definitions);
        } else if (auto while_loop = dynamic_cast<structured_control_flow::While*>(&child.first)) {
            visit_while(analysis_manager, *while_loop, undefined, open_definitions, closed_definitions);
        } else if (auto return_statement = dynamic_cast<structured_control_flow::Return*>(&child.first)) {
            visit_return(analysis_manager, *return_statement, undefined, open_definitions, closed_definitions);
        } else if (auto sequence = dynamic_cast<structured_control_flow::Sequence*>(&child.first)) {
            visit_sequence(analysis_manager, *sequence, undefined, open_definitions, closed_definitions);
        }

        // handle transitions read
        for (auto& entry : child.second.assignments()) {
            for (auto& atom : symbolic::atoms(entry.second)) {
                if (symbolic::is_pointer(atom)) {
                    continue;
                }
                auto current_user = users.get_user(atom->get_name(), &child.second, Use::READ);

                bool found = false;
                for (auto& user : open_definitions) {
                    if (user.first->container() == atom->get_name()) {
                        user.second.insert(current_user);
                        found = true;
                    }
                }
                if (!found) {
                    undefined.insert(current_user);
                }
            }
        }

        // handle transitions write
        for (auto& entry : child.second.assignments()) {
            auto current_user = users.get_user(entry.first->get_name(), &child.second, Use::WRITE);

            std::unordered_set<User*> to_close;
            for (auto& user : open_definitions) {
                if (this->closes(analysis_manager, *user.first, *current_user, true)) {
                    to_close.insert(user.first);
                }
            }
            for (auto& user : to_close) {
                closed_definitions.insert({user, open_definitions.at(user)});
                open_definitions.erase(user);
            }
            open_definitions.insert({current_user, {}});
        }
    }
}

bool DataDependencyAnalysis::
    supersedes_restrictive(User& previous, User& current, analysis::AnalysisManager& analysis_manager) {
    if (previous.container() != current.container()) {
        return false;
    }
    // Shortcut for scalars
    auto& type = this->sdfg_.type(previous.container());
    if (dynamic_cast<const types::Scalar*>(&type)) {
        return true;
    }

    if (this->is_undefined_user(previous) || this->is_undefined_user(current)) {
        return false;
    }

    // Conservative shortcut: skip the full symbolic subset analysis and
    // assume the previous write does NOT fully cover `current`. Sound
    // (downstream consumers treat the read as potentially upward-exposed)
    // and avoids ISL queries that have caused fixed-point hangs in the
    // wider pass pipeline.
    if (!detailed_) {
        return false;
    }

    auto& assumptions_analysis = analysis_manager.get<analysis::AssumptionsAnalysis>();
    auto& previous_subsets = previous.subsets();
    auto& current_subsets = current.subsets();
    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);

    // Check if previous subset is subset of any current subset
    for (auto& previous_subset : previous_subsets) {
        bool found = false;
        for (auto& current_subset : current_subsets) {
            if (symbolic::is_subset(previous_subset, current_subset, previous_assumptions, previous_assumptions)) {
                found = true;
                break;
            }
        }
        if (!found) {
            return false;
        }
    }

    return true;
}

bool DataDependencyAnalysis::fully_covered(
    analysis::AnalysisManager& analysis_manager,
    User& current,
    const std::unordered_map<User*, std::unordered_set<User*>>& open_definitions
) {
    // Scalar reads: container-level open definition is full coverage.
    auto& type = this->sdfg_.type(current.container());
    if (dynamic_cast<const types::Scalar*>(&type)) {
        for (auto& w : open_definitions) {
            if (w.first->container() == current.container() && !this->is_undefined_user(*w.first)) {
                return true;
            }
        }
        return false;
    }
    if (this->is_undefined_user(current)) {
        return false;
    }

    // Conservative shortcut: assume coverage holds (treat the read as
    // satisfied by some open writer, equivalent to `depends`'s
    // intersect-any semantics). Sound: it allows the previous detection
    // path to drop the read into `undefined` only when truly unmatched,
    // matching pre-`fully_covered` behavior, while skipping ISL queries.
    if (!detailed_) {
        for (auto& w : open_definitions) {
            if (w.first->container() == current.container() && !this->is_undefined_user(*w.first)) {
                return true;
            }
        }
        return false;
    }

    auto& current_subsets = current.subsets();
    if (current_subsets.empty()) {
        // Symbol use / no real read footprint -- fall back to existence of any
        // matching open definition (depends() semantics).
        for (auto& w : open_definitions) {
            if (w.first->container() == current.container() && !this->is_undefined_user(*w.first)) {
                return true;
            }
        }
        return false;
    }

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

    // Each read subset must be contained in some single open writer's subset.
    for (auto& read_subset : current_subsets) {
        bool covered = false;
        for (auto& w_entry : open_definitions) {
            auto* w = w_entry.first;
            if (w->container() != current.container()) continue;
            if (this->is_undefined_user(*w)) continue;
            auto& w_assumptions = assumptions_analysis.get(*Users::scope(w), true);
            for (auto& w_subset : w->subsets()) {
                if (symbolic::is_subset(read_subset, w_subset, current_assumptions, w_assumptions)) {
                    covered = true;
                    break;
                }
            }
            if (covered) break;
        }
        if (!covered) return false;
    }
    return true;
}

bool DataDependencyAnalysis::intersects(User& previous, User& current, analysis::AnalysisManager& analysis_manager) {
    if (previous.container() != current.container()) {
        return false;
    }
    // Shortcut for scalars
    auto& type = this->sdfg_.type(previous.container());
    if (dynamic_cast<const types::Scalar*>(&type)) {
        return true;
    }

    if (this->is_undefined_user(previous) || this->is_undefined_user(current)) {
        return true;
    }

    // Conservative shortcut: assume the two subsets may intersect. Sound
    // for dependence tracking (we may report spurious dependencies but
    // never miss a real one) and avoids ISL hangs.
    if (!detailed_) {
        return true;
    }

    auto& previous_subsets = previous.subsets();
    auto& current_subsets = current.subsets();

    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);

    // Check if any current subset intersects with any previous subset
    bool found = false;
    for (auto& current_subset : current_subsets) {
        for (auto& previous_subset : previous_subsets) {
            if (!symbolic::is_disjoint(current_subset, previous_subset, current_assumptions, previous_assumptions)) {
                found = true;
                break;
            }
        }
        if (found) {
            break;
        }
    }

    return found;
}

bool DataDependencyAnalysis::
    closes(analysis::AnalysisManager& analysis_manager, User& previous, User& current, bool requires_dominance) {
    if (previous.container() != current.container()) {
        return false;
    }

    if (this->is_undefined_user(previous) || this->is_undefined_user(current)) {
        return false;
    }

    // Check dominance
    if (requires_dominance) {
        auto& dominance_analysis = analysis_manager.get<analysis::DominanceAnalysis>();
        if (!dominance_analysis.post_dominates(current, previous)) {
            return false;
        }
    }

    // Previous memlets are subsets of current memlets
    auto& type = sdfg_.type(previous.container());
    if (type.type_id() == types::TypeID::Scalar) {
        return true;
    }

    // Conservative shortcut: assume `current` does not fully overwrite
    // `previous`. Sound (we just keep more open definitions live) and
    // avoids ISL hangs.
    if (!detailed_) {
        return false;
    }

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

    auto& previous_memlets = previous.subsets();
    auto& current_memlets = current.subsets();

    for (auto& subset_ : previous_memlets) {
        bool overwritten = false;
        for (auto& subset : current_memlets) {
            if (symbolic::is_subset(subset_, subset, previous_assumptions, current_assumptions)) {
                overwritten = true;
                break;
            }
        }
        if (!overwritten) {
            return false;
        }
    }

    return true;
}

bool DataDependencyAnalysis::depends(analysis::AnalysisManager& analysis_manager, User& previous, User& current) {
    if (previous.container() != current.container()) {
        return false;
    }

    // Previous memlets are subsets of current memlets
    auto& type = sdfg_.type(previous.container());
    if (type.type_id() == types::TypeID::Scalar) {
        return true;
    }

    if (this->is_undefined_user(previous)) {
        return true;
    }

    // Conservative shortcut: assume `current` may depend on `previous`.
    if (!detailed_) {
        return true;
    }

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

    auto& previous_memlets = previous.subsets();
    auto& current_memlets = current.subsets();

    bool intersect_any = false;
    for (auto& current_subset : current_memlets) {
        for (auto& previous_subset : previous_memlets) {
            if (!symbolic::is_disjoint(current_subset, previous_subset, current_assumptions, previous_assumptions)) {
                intersect_any = true;
                break;
            }
        }
        if (intersect_any) {
            break;
        }
    }

    return intersect_any;
}

/****** Public API ******/

std::unordered_set<User*> DataDependencyAnalysis::defines(User& write) {
    assert(write.use() == Use::WRITE);
    if (results_.find(write.container()) == results_.end()) {
        return {};
    }
    auto& raws = results_.at(write.container());
    assert(raws.find(&write) != raws.end());

    auto& reads_for_write = raws.at(&write);

    std::unordered_set<User*> reads;
    for (auto& entry : reads_for_write) {
        reads.insert(entry);
    }

    return reads;
};

std::unordered_map<User*, std::unordered_set<User*>> DataDependencyAnalysis::definitions(const std::string& container) {
    if (results_.find(container) == results_.end()) {
        return {};
    }
    return results_.at(container);
};

std::unordered_map<User*, std::unordered_set<User*>> DataDependencyAnalysis::defined_by(const std::string& container) {
    auto reads = this->definitions(container);

    std::unordered_map<User*, std::unordered_set<User*>> read_to_writes_map;
    for (auto& entry : reads) {
        for (auto& read : entry.second) {
            if (read_to_writes_map.find(read) == read_to_writes_map.end()) {
                read_to_writes_map[read] = {};
            }
            read_to_writes_map[read].insert(entry.first);
        }
    }
    return read_to_writes_map;
};

std::unordered_set<User*> DataDependencyAnalysis::defined_by(User& read) {
    assert(read.use() == Use::READ);
    auto definitions = this->definitions(read.container());

    std::unordered_set<User*> writes;
    for (auto& entry : definitions) {
        for (auto& r : entry.second) {
            if (&read == r) {
                writes.insert(entry.first);
            }
        }
    }
    return writes;
};

bool DataDependencyAnalysis::is_undefined_user(User& user) const {
    return user.vertex_ == boost::graph_traits<graph::Graph>::null_vertex();
};

bool DataDependencyAnalysis::has_loop_boundary(structured_control_flow::StructuredLoop& loop) const {
    return this->loop_boundaries_.find(&loop) != this->loop_boundaries_.end();
}

const std::unordered_set<User*>& DataDependencyAnalysis::upward_exposed_reads(structured_control_flow::StructuredLoop&
                                                                                  loop) const {
    return this->loop_boundaries_.at(&loop).first;
}

const std::unordered_map<User*, std::unordered_set<User*>>& DataDependencyAnalysis::
    escaping_definitions(structured_control_flow::StructuredLoop& loop) const {
    return this->loop_boundaries_.at(&loop).second;
}

} // namespace analysis
} // namespace sdfg

daisytuner / docc / 26556322966

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