memory_layout_analysis.h

Go to the documentation of this file.

 
#pragma once
 
#include <functional>
#include <map>
#include <optional>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
 
#include <string>
 
#include "sdfg/analysis/analysis.h"
#include "sdfg/analysis/assumptions_analysis.h"
#include "sdfg/data_flow/memlet.h"
#include "sdfg/structured_control_flow/block.h"
#include "sdfg/structured_control_flow/control_flow_node.h"
#include "sdfg/symbolic/extreme_values.h"
#include "sdfg/symbolic/symbolic.h"
 
namespace sdfg {
namespace analysis {
 
typedef math::tensor::TensorLayout MemoryLayout;
 
struct MemoryTile {
    std::string container; // Container name
    data_flow::Subset min_subset; // Minimum accessed indices in this tile
    data_flow::Subset max_subset; // Maximum accessed indices (empty for point tiles: max == min)
    MemoryLayout layout; // Inferred tile layout at this loop level
    bool first_dim_bounded; // True if first dimension is bounded (Tensor/Array), false for unbounded pointers
 
    // A pre-ranged access already spans its full accessed region in [min_subset,
    // max_subset] (e.g. a library-node operand whose offset was partitioned into
    // per-dimension bases). During merge its min gets only a lower bound and its
    // max only an upper bound. A point access (false) samples a single index that
    // must be swept over its own symbols' ranges, so both bounds apply to it.
    bool pre_ranged = false;

    bool is_point() const;

    const data_flow::Subset& upper_subset() const {
        return max_subset.empty() ? min_subset : max_subset;
    }

    symbolic::MultiExpression extents() const;

    symbolic::MultiExpression extents_approx() const;

    std::pair<symbolic::Expression, symbolic::Expression> contiguous_range() const;
};
 
struct MemoryTileGroup {
    MemoryTile tile; // Bounding box for this group
    std::vector<const data_flow::Memlet*> memlets; // Memlets belonging to this group
};

class MemoryLayoutAnalysis : public Analysis {
private:
    std::unordered_map<const data_flow::Memlet*, MemoryTile> accesses_;
    // Per node, the memlets in its subtree whose accesses are recorded, and the nodes whose tiles are up to date.
    // Queries compute a scope that is not, from its children that are not either: after a local invalidation, only
    // what is queried is computed again.
    std::unordered_map<const structured_control_flow::ControlFlowNode*, std::vector<const data_flow::Memlet*>>
        scope_memlets_;
    std::unordered_set<const structured_control_flow::ControlFlowNode*> computed_;
    analysis::AnalysisManager* analysis_manager_ = nullptr;
    std::map<std::pair<const structured_control_flow::ControlFlowNode*, std::string>, MemoryTile> tiles_;
    std::map<std::pair<const structured_control_flow::ControlFlowNode*, std::string>, std::vector<MemoryTileGroup>>
        tile_groups_;
 
    // Owned, branch-condition-aware `AssumptionsAnalysis` instance. The
    // manager-cached AA is kept cheap and does NOT refine branch
    // assumptions; MLA's per-scope tile inference must see the refined
    // halo-style coupled constraints emitted at IfElse guards, so it owns
    // its own instance rebuilt on every `run()`.
    std::unique_ptr<AssumptionsAnalysis> detailed_assumptions_;
 
    // Per-run bounds/proof caches, shared by all blocks with the same assumption set.
    std::unordered_map<const symbolic::Assumptions*, std::unique_ptr<symbolic::AssumptionsBounds>> bounds_cache_;
 
    void traverse(structured_control_flow::ControlFlowNode& node, analysis::AnalysisManager& analysis_manager);

    void ensure(const structured_control_flow::ControlFlowNode& scope) const;
 
    void process_block(structured_control_flow::Block& block, analysis::AnalysisManager& analysis_manager);
 
    void record_access(const data_flow::Memlet& memlet, MemoryTile access);
 
    void merge_scope_layouts(
        structured_control_flow::ControlFlowNode& scope,
        const std::vector<const data_flow::Memlet*>& memlets,
        analysis::AnalysisManager& analysis_manager
    );
 
    void compute_tile_groups(
        structured_control_flow::ControlFlowNode& scope,
        const std::string& container,
        const std::vector<const data_flow::Memlet*>& memlets,
        const MemoryLayout& reference_layout,
        size_t ndims,
        symbolic::BoundAnalysis& ba_tight,
        symbolic::BoundAnalysis& ba_loose,
        const std::function<bool(const symbolic::Expression&)>& bounds_are_sound
    );
 
protected:
    void run(analysis::AnalysisManager& analysis_manager) override;
 
public:
    MemoryLayoutAnalysis(StructuredSDFG& sdfg);
    MemoryLayoutAnalysis(StructuredSDFG& sdfg, const Options& options);
 
    std::string name() const override {
        return "MemoryLayoutAnalysis";
    }

    bool invalidate(structured_control_flow::ControlFlowNode& changed) override;

    const MemoryTile* access(const data_flow::Memlet& memlet) const;

    const MemoryTile* tile(const structured_control_flow::ControlFlowNode& scope, const std::string& container) const;

    const std::vector<MemoryTileGroup>*
    tile_groups(const structured_control_flow::ControlFlowNode& scope, const std::string& container) const;

    const MemoryTileGroup*
    tile_group_for(const structured_control_flow::ControlFlowNode& scope, const data_flow::Memlet& memlet) const;
};
 
} // namespace analysis
} // namespace sdfg