loop_analysis.h

Go to the documentation of this file.

#pragma once
 
#include <unordered_set>
#include "sdfg/analysis/analysis.h"
#include "sdfg/structured_control_flow/structured_loop.h"
 
namespace sdfg {
namespace analysis {
 
class AssumptionsAnalysis;
 
#define LOOP_INFO_PROPERTIES              \
    X(int, loopnest_index, -1)            \
    X(sdfg::ElementId, element_id, 0)     \
    X(size_t, num_loops, 0)               \
    X(size_t, num_maps, 0)                \
    X(size_t, num_fors, 0)                \
    X(size_t, num_whiles, 0)              \
    X(size_t, max_depth, 0)               \
    X(bool, is_perfectly_nested, false)   \
    X(bool, is_perfectly_parallel, false) \
    X(bool, is_elementwise, false)        \
    X(bool, has_side_effects, false)      \
    X(uint32_t, loop_level, 0)            \
    X(uint32_t, map_stack_depth, 0)



 
struct LoopInfo {
#define X(type, name, val) type name = val;
    LOOP_INFO_PROPERTIES
#undef X
};

struct LocalLoopInfo {
    enum class LoopType : uint8_t { While, For, Map };
    uint32_t loop_id;
    uint32_t last_child_id;
    uint32_t loop_level;
    LoopType type;
    bool is_elementwise;
    bool contains_non_perfectly_nested;
    bool contains_side_effects;
};
 
inline nlohmann::json loop_info_to_json(LoopInfo info) {
    nlohmann::json j = nlohmann::json{
        {"loopnest_index", info.loopnest_index},
        {"element_id", info.element_id},
        {"num_loops", info.num_loops},
        {"num_maps", info.num_maps},
        {"num_fors", info.num_fors},
        {"num_whiles", info.num_whiles},
        {"max_depth", info.max_depth},
        {"is_perfectly_nested", info.is_perfectly_nested},
        {"is_perfectly_parallel", info.is_perfectly_parallel},
        {"is_elementwise", info.is_elementwise},
        {"has_side_effects", info.has_side_effects},
        {"loop_level", info.loop_level},
        {"map_stack_depth", info.map_stack_depth}
    };
    return j;
}
 
void loop_info_local_to_json(nlohmann::json& j, const LocalLoopInfo& info);
 
class LoopAnalysis : public Analysis {
public:
    struct LoopState {
        LocalLoopInfo local;
        LoopInfo nest;
    };
    struct AggregatedResult {
        uint32_t last_child_id;
        LoopInfo nest;
    };
 
private:
    std::vector<structured_control_flow::ControlFlowNode*> loops_; // currently required in Pre-order
    std::unordered_map<structured_control_flow::ControlFlowNode*, structured_control_flow::ControlFlowNode*> loop_tree_;
    std::unordered_map<structured_control_flow::ControlFlowNode*, std::vector<structured_control_flow::ControlFlowNode*>>
        loop_children_;
 
    std::unordered_map<structured_control_flow::ControlFlowNode*, LoopState> loop_infos_;

    void init_new_loop_info(
        LoopState& info,
        uint32_t id,
        uint32_t loop_level,
        structured_control_flow::ControlFlowNode* loop,
        structured_control_flow::Map* map,
        structured_control_flow::ControlFlowNode* while_loop
    );
 
    void
    run(structured_control_flow::ControlFlowNode& scope,
        structured_control_flow::ControlFlowNode* parent_loop,
        uint32_t loop_level);
 
    structured_control_flow::Sequence* get_loop_content_root(structured_control_flow::ControlFlowNode* loop);
 
    std::list<std::vector<sdfg::structured_control_flow::ControlFlowNode*>> loop_tree_paths(
        sdfg::structured_control_flow::ControlFlowNode* loop,
        const std::unordered_map<
            sdfg::structured_control_flow::ControlFlowNode*,
            sdfg::structured_control_flow::ControlFlowNode*>& tree
    ) const;
 
    LoopState& compute_loop_infos(structured_control_flow::ControlFlowNode* loop);

    AggregatedResult aggregate_loop_info(structured_control_flow::ControlFlowNode* loop) const;
 
    void reindex_loop_nest_idx();

    uint32_t child_insertion_index(structured_control_flow::ControlFlowNode* new_parent, bool start_not_end) const;

    void reindex(
        std::vector<structured_control_flow::ControlFlowNode*>::iterator start,
        std::vector<structured_control_flow::ControlFlowNode*>::iterator end
    );

    void propagate_changed_nest_info(std::vector<structured_control_flow::ControlFlowNode*>::iterator top);
 
public:
    LoopAnalysis(StructuredSDFG& sdfg);
 
    std::string name() const override {
        return "LoopAnalysis";
    }
 
    void run(analysis::AnalysisManager& analysis_manager) override;

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

    const std::vector<structured_control_flow::ControlFlowNode*> loops() const;

    const std::vector<structured_control_flow::ControlFlowNode*>& loops_in_pre_order() const;

    const std::unordered_map<structured_control_flow::ControlFlowNode*, structured_control_flow::ControlFlowNode*>&
    loop_tree() const;
 
    LoopInfo loop_info(structured_control_flow::ControlFlowNode* loop) const;
 
    const LocalLoopInfo& loop_info_local(structured_control_flow::ControlFlowNode* loop) const;
 
    structured_control_flow::ControlFlowNode* find_loop_by_indvar(const std::string& indvar);
 
    structured_control_flow::ControlFlowNode* parent_loop(structured_control_flow::ControlFlowNode* loop) const;
 
    const std::vector<structured_control_flow::ControlFlowNode*>& outermost_loops() const;
 
    bool is_outermost_loop(structured_control_flow::ControlFlowNode* loop) const;
 
    const std::vector<structured_control_flow::ControlFlowNode*> outermost_maps() const;
 
    const std::vector<sdfg::structured_control_flow::ControlFlowNode*>&
    children(sdfg::structured_control_flow::ControlFlowNode* node) const;
 
    std::list<std::vector<sdfg::structured_control_flow::ControlFlowNode*>>
    loop_tree_paths(sdfg::structured_control_flow::ControlFlowNode* loop) const;
 
    std::unordered_set<sdfg::structured_control_flow::ControlFlowNode*>
    descendants(sdfg::structured_control_flow::ControlFlowNode* loop) const;
 
    std::unordered_set<sdfg::structured_control_flow::ControlFlowNode*>
    ancestors(sdfg::structured_control_flow::ControlFlowNode* loop) const;
 
    std::vector<sdfg::structured_control_flow::ControlFlowNode*>::const_iterator
    get_loop_iterator(structured_control_flow::ControlFlowNode* loop);
    std::vector<sdfg::structured_control_flow::ControlFlowNode*>::const_iterator
    get_subtree_end(structured_control_flow::ControlFlowNode* loop);
 
    void dump_to_file(std::filesystem::path file) const;
 
    // update with changes
 
    void copied_loop(
        structured_control_flow::ControlFlowNode* existing_loop,
        structured_control_flow::ControlFlowNode* new_parent_loop,
        structured_control_flow::ControlFlowNode* new_loop,
        bool start_not_end = false
 
    );
 
    void moved_loop(
        structured_control_flow::ControlFlowNode* existing_loop,
        structured_control_flow::StructuredLoop* new_parent,
        bool start_not_end = false
    );
 
    void removed_loop(structured_control_flow::ControlFlowNode* existing_loop);

    void added_local_contents(structured_control_flow::ControlFlowNode* loop, bool side_effects, bool non_perfectly_nested);
};
 
} // namespace analysis
} // namespace sdfg