loop_carried_dependency_analysis.h

Go to the documentation of this file.

#pragma once
 
#include <memory>
#include <string>
#include <unordered_map>
#include <vector>
 
#include "sdfg/analysis/analysis.h"
#include "sdfg/analysis/assumptions_analysis.h"
#include "sdfg/analysis/data_dependency_analysis.h"
#include "sdfg/analysis/users.h"
#include "sdfg/structured_control_flow/reduce.h"
#include "sdfg/structured_control_flow/structured_loop.h"
#include "sdfg/structured_sdfg.h"
#include "sdfg/symbolic/maps.h"
 
namespace sdfg {
namespace parallelization {
 
enum LoopCarriedDependency {
    LOOP_CARRIED_DEPENDENCY_READ_WRITE,
    LOOP_CARRIED_DEPENDENCY_WRITE_WRITE,
    LOOP_CARRIED_DEPENDENCY_UNDEFINED,
};

struct LoopCarriedDependencyInfo {
    LoopCarriedDependency type;
    symbolic::maps::DependenceDeltas deltas;
};

struct LoopCarriedDependencyPair {
    analysis::User* writer;
    analysis::User* reader;
    LoopCarriedDependency type;
    symbolic::maps::DependenceDeltas deltas;
};

class LoopCarriedDependencyAnalysis : public analysis::Analysis {
    friend class analysis::AnalysisManager;
 
private:
    struct LoopResult {
        // False for loops that cannot be analyzed (non-monotonic, no boundary information).
        bool available = false;
        std::unordered_map<std::string, LoopCarriedDependencyInfo> dependencies;
        std::vector<LoopCarriedDependencyPair> pairs;
        // Recognized reductions: loop-carried read-write dependencies realized by a single
        // associative/commutative combine on a loop-invariant accumulator location.
        std::vector<structured_control_flow::ReductionInfo> reductions;
    };
 
    analysis::AnalysisManager* analysis_manager_ = nullptr;
 
    std::unordered_map<const structured_control_flow::StructuredLoop*, LoopResult> results_;
 
    // Detailed data dependency analyses, keyed by the outermost loop of a nest. Constructed
    // manually: the manager-cached DDA runs in a cheaper, conservative mode.
    std::unordered_map<const structured_control_flow::StructuredLoop*, std::unique_ptr<analysis::DataDependencyAnalysis>>
        nest_ddas_;
 
    // Branch-condition-aware assumptions (the manager-cached AA skips IfElse refinement, which
    // the ISL formulation needs to prove halo-style patterns non-loop-carried).
    std::unique_ptr<analysis::AssumptionsAnalysis> detailed_assumptions_;
 
    const LoopResult& result(structured_control_flow::StructuredLoop& loop);
    void compute(structured_control_flow::StructuredLoop& loop, LoopResult& result);
    void detect_reductions(structured_control_flow::StructuredLoop& loop, LoopResult& result);
    analysis::DataDependencyAnalysis& nest_dda(structured_control_flow::StructuredLoop& loop);
    analysis::AssumptionsAnalysis& detailed_assumptions();
 
public:
    LoopCarriedDependencyAnalysis(StructuredSDFG& sdfg);
 
    std::string name() const override {
        return "LoopCarriedDependencyAnalysis";
    }

    void run(analysis::AnalysisManager& analysis_manager) override;

    bool available(structured_control_flow::StructuredLoop& loop);

    const std::unordered_map<std::string, LoopCarriedDependencyInfo>&
    dependencies(structured_control_flow::StructuredLoop& loop);

    const std::vector<LoopCarriedDependencyPair>& pairs(structured_control_flow::StructuredLoop& loop);

    std::vector<const LoopCarriedDependencyPair*> pairs_between(
        structured_control_flow::StructuredLoop& loop,
        const structured_control_flow::ControlFlowNode& subtree_a,
        const structured_control_flow::ControlFlowNode& subtree_b
    );

    bool has_loop_carried(structured_control_flow::StructuredLoop& loop);

    bool has_loop_carried_raw(structured_control_flow::StructuredLoop& loop);

    bool has_loop_carried_hazard(structured_control_flow::StructuredLoop& loop);

    const std::vector<structured_control_flow::ReductionInfo>& reductions(structured_control_flow::StructuredLoop& loop);

    bool has_reductions(structured_control_flow::StructuredLoop& loop);

    bool is_reduction_only(structured_control_flow::StructuredLoop& loop);
};
 
} // namespace parallelization
} // namespace sdfg