data_dependency_analysis.h

Go to the documentation of this file.

#pragma once
 
#include <unordered_map>
#include <unordered_set>
 
#include "sdfg/analysis/analysis.h"
#include "sdfg/analysis/assumptions_analysis.h"
#include "sdfg/analysis/loop_analysis.h"
#include "sdfg/analysis/users.h"
#include "sdfg/structured_sdfg.h"
 
namespace sdfg {
namespace analysis {

class DataDependencyAnalysis : public Analysis {
    friend class AnalysisManager;
 
private:
    structured_control_flow::Sequence& node_;
    // When set, only this loop nest is analyzed (instead of node_).
    structured_control_flow::StructuredLoop* loop_ = nullptr;
 
    std::unordered_map<std::string, std::unordered_map<User*, std::unordered_set<User*>>> results_;
 
    // Per-loop boundary snapshots taken at the moment of `visit_for`.
    // - first  = `undefined_for` (reads inside the loop body that look outside
    //            the loop body for their definition; equivalently, upward-exposed
    //            reads at the loop's boundary).
    // - second = `open_definitions_for` (writes inside the loop body that may
    //            escape the loop body or feed a future iteration; equivalently,
    //            live-out definitions at the loop's boundary).
    // This is the primitive consumed by `LoopCarriedDependencyAnalysis`.
    std::unordered_map<
        structured_control_flow::StructuredLoop*,
        std::pair<std::unordered_set<User*>, std::unordered_map<User*, std::unordered_set<User*>>>>
        loop_boundaries_;
 
    std::list<std::unique_ptr<User>> undefined_users_;
 
    // Per-run cache of whether a container is a scalar; queried for every candidate pair.
    std::unordered_map<std::string, bool> scalar_containers_;
 
    bool is_scalar(const std::string& container);
 
    // When false (default), the symbolic-subset/disjointness helpers below
    // (`supersedes_restrictive`, `intersects`, `closes`, `depends`) take
    // conservative shortcuts and skip the expensive ISL queries. Sound but
    // less precise. `LoopCarriedDependencyAnalysis` constructs its own
    // detailed instance manually with `detailed_ = true` to obtain the
    // precise boundary information it requires.
    bool detailed_ = false;
 
    // Per-run detailed `AssumptionsAnalysis` instance. Lazily constructed
    // by `ensure_detailed_assumptions()` on first use, with
    // `with_branch_conditions=true` so that IfElse-guard refinements (e.g.
    // coupled constraints emitted by halo guards) reach the symbolic subset
    // queries below. Bypasses `AnalysisManager` because the manager-cached
    // `AssumptionsAnalysis` intentionally uses the cheaper, branch-
    // condition-less form. Lazy init also handles direct `visit_*` entry
    // points (e.g. tests) that don't go through `run()`.
    std::unique_ptr<AssumptionsAnalysis> detailed_assumptions_;
 
    // Returns the per-instance detailed assumptions analysis, constructing
    // and `run()`ing it on first call. Must only be invoked behind a
    // `detailed_` guard at the call site.
    AssumptionsAnalysis& ensure_detailed_assumptions(analysis::AnalysisManager& analysis_manager);
 
    bool supersedes_restrictive(User& previous, User& current, analysis::AnalysisManager& analysis_manager);
 
    bool intersects(User& previous, User& current, analysis::AnalysisManager& analysis_manager);
 
    bool closes(analysis::AnalysisManager& analysis_manager, User& previous, User& current, bool requires_dominance);
 
    bool depends(analysis::AnalysisManager& analysis_manager, User& previous, User& current);
 
    // True iff every read-subset of `current` is contained in some single
    // open writer's subset (per-subset coverage). For scalars / undefined
    // users / symbol uses this degrades to `depends`. Used to detect partial
    // coverage that `depends` (intersect-any) would otherwise hide, which
    // would cause upward-exposed reads to be silently swallowed.
    bool fully_covered(
        analysis::AnalysisManager& analysis_manager,
        User& current,
        const std::unordered_map<User*, std::unordered_set<User*>>* open_definitions
    );
 
    using Definitions = std::unordered_map<User*, std::unordered_set<User*>>;
    // Open definitions grouped by container: every query only concerns writes to the same container.
    using OpenDefinitions = std::unordered_map<std::string, Definitions>;
 
    static OpenDefinitions group_by_container(const Definitions& definitions);
    static Definitions flatten(const OpenDefinitions& definitions);
 
    void visit_block_impl(
        analysis::AnalysisManager& analysis_manager,
        structured_control_flow::Block& block,
        std::unordered_set<User*>& undefined,
        OpenDefinitions& open_definitions,
        Definitions& closed_definitions
    );
    void visit_assignment_block_impl(
        analysis::AnalysisManager& analysis_manager,
        structured_control_flow::AssignmentBlock& assignments,
        std::unordered_set<User*>& undefined,
        OpenDefinitions& open_definitions,
        Definitions& closed_definitions
    );
    void visit_for_impl(
        analysis::AnalysisManager& analysis_manager,
        structured_control_flow::StructuredLoop& for_loop,
        std::unordered_set<User*>& undefined,
        OpenDefinitions& open_definitions,
        Definitions& closed_definitions
    );
    void visit_if_else_impl(
        analysis::AnalysisManager& analysis_manager,
        structured_control_flow::IfElse& if_else,
        std::unordered_set<User*>& undefined,
        OpenDefinitions& open_definitions,
        Definitions& closed_definitions
    );
    void visit_while_impl(
        analysis::AnalysisManager& analysis_manager,
        structured_control_flow::While& while_loop,
        std::unordered_set<User*>& undefined,
        OpenDefinitions& open_definitions,
        Definitions& closed_definitions
    );
    void visit_return_impl(
        analysis::AnalysisManager& analysis_manager,
        structured_control_flow::Return& return_statement,
        std::unordered_set<User*>& undefined,
        OpenDefinitions& open_definitions,
        Definitions& closed_definitions
    );
    void visit_sequence_impl(
        analysis::AnalysisManager& analysis_manager,
        structured_control_flow::Sequence& sequence,
        std::unordered_set<User*>& undefined,
        OpenDefinitions& open_definitions,
        Definitions& closed_definitions
    );
 
public:
    DataDependencyAnalysis(StructuredSDFG& sdfg);
 
    DataDependencyAnalysis(StructuredSDFG& sdfg, structured_control_flow::Sequence& node);
 
    DataDependencyAnalysis(StructuredSDFG& sdfg, structured_control_flow::StructuredLoop& loop);
 
    // Enable detailed symbolic subset/disjointness checks. Off by default;
    // `LoopCarriedDependencyAnalysis` flips it on for its own manually
    // constructed instance.
    void set_detailed(bool detailed) {
        detailed_ = detailed;
    }
 
    std::string name() const override {
        return "DataDependencyAnalysis";
    }
 
    void run(analysis::AnalysisManager& analysis_manager) override;
 
    /****** Visitor API ******/
 
    void 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
    );
 
    void visit_assignment_block(
        analysis::AnalysisManager& analysis_manager,
        structured_control_flow::AssignmentBlock& assignments,
        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
    );
 
    void 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
    );
 
    void visit_if_else(
        analysis::AnalysisManager& analysis_manager,
        structured_control_flow::IfElse& if_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
    );
 
    void 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
    );
 
    void 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
    );
 
    void 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
    );
 
    /****** Defines & Use ******/

    std::unordered_set<User*> defines(User& write);

    std::unordered_map<User*, std::unordered_set<User*>> definitions(const std::string& container);

    std::unordered_map<User*, std::unordered_set<User*>> defined_by(const std::string& container);

    std::unordered_set<User*> defined_by(User& read);
 
    bool is_undefined_user(User& user) const;
 
    /****** Loop boundaries (consumed by LoopCarriedDependencyAnalysis) ******/

    bool has_loop_boundary(structured_control_flow::StructuredLoop& loop) const;

    const std::unordered_set<User*>& upward_exposed_reads(structured_control_flow::StructuredLoop& loop) const;

    const std::unordered_map<User*, std::unordered_set<User*>>&
    escaping_definitions(structured_control_flow::StructuredLoop& loop) const;
};
 
} // namespace analysis
} // namespace sdfg