analysis::StructurizeCFGPass Class Reference

#include <llvmexpr/analysis/passes/StructurizeCFGPass.hpp>

Inheritance diagram for analysis::StructurizeCFGPass:

Collaboration diagram for analysis::StructurizeCFGPass:

Public Types
using	Result = StructurizeCFGResult
Public Types inherited from analysis::AnalysisPass< StructurizeCFGPass, StructurizeCFGResult >
using	Result

Public Member Functions
const char *	getName () const override
Result	run (const std::vector< Token > &tokens, AnalysisManager &am) override
Public Member Functions inherited from analysis::Pass
	Pass ()=default
virtual	~Pass ()=default
	Pass (const Pass &)=delete
Pass &	operator= (const Pass &)=delete
	Pass (Pass &&)=delete
Pass &	operator= (Pass &&)=delete

Detailed Description

Computes CFG structuring information for structured-control-flow codegen. Responsibilities:

• Compute post-dominators (for join point selection)
• Identify natural loops (backedges + loop body closure)
• Compute loop follow blocks Depends on: BuildCFGPass, BlockAnalysisPass

Definition at line 84 of file StructurizeCFGPass.hpp.

Member Typedef Documentation

Result

using analysis::StructurizeCFGPass::Result = StructurizeCFGResult

Definition at line 87 of file StructurizeCFGPass.hpp.

Member Function Documentation

getName()

const char * analysis::StructurizeCFGPass::getName ( ) const

inlinenodiscardoverridevirtual

Implements analysis::Pass.

Definition at line 89 of file StructurizeCFGPass.hpp.

                                                       {
        return "StructurizeCFG (Control Flow Structuring) Pass";
    }

run()

StructurizeCFGPass::Result analysis::StructurizeCFGPass::run ( const std::vector< Token > & tokens, AnalysisManager & am )

overridevirtual

Implements analysis::AnalysisPass< StructurizeCFGPass, StructurizeCFGResult >.

Definition at line 676 of file StructurizeCFGPass.cpp.

                                             {
    const auto& block_result = am.getResult<BlockAnalysisPass>();
    const auto& cfg = block_result.cfg_blocks;
    const auto& stack_safety = am.getResult<StackSafetyPass>();
 
    Result result;
 
    if (cfg.empty()) {
        return result;
    }
 
    const auto reachable0 = compute_reachable(cfg);
    const bool reducible0 = check_reducible(cfg, reachable0);
 
    const std::vector<CFGBlock>* analysis_cfg = &cfg;
 
    std::vector<CFGBlock> work_cfg = cfg;
    std::vector<int> origin_map(cfg.size());
    for (size_t i = 0; i < cfg.size(); ++i) {
        origin_map[i] = static_cast<int>(i);
    }
 
    constexpr size_t MAX_BLOCKS = 256;
    constexpr size_t MAX_BLOCKS_RATIO = 8;
    size_t max_blocks =
        std::max<size_t>(cfg.size() * MAX_BLOCKS_RATIO, MAX_BLOCKS);
 
    bool changed =
        tail_duplicate_trivial_joins(work_cfg, origin_map, max_blocks);
    if (!reducible0) {
        changed |= node_split_make_reducible(work_cfg, origin_map, max_blocks);
    }
 
    if (changed) {
        result.structured_cfg_blocks = std::move(work_cfg);
        result.structured_block_origin = std::move(origin_map);
        analysis_cfg = &result.structured_cfg_blocks;
 
        result.structured_stack_depth_in.resize(
            result.structured_cfg_blocks.size(), -1);
        for (size_t i = 0; i < result.structured_cfg_blocks.size(); ++i) {
            int orig = result.structured_block_origin[i];
            if (orig >= 0 && static_cast<size_t>(orig) <
                                 stack_safety.stack_depth_in.size()) {
                result.structured_stack_depth_in[i] =
                    stack_safety.stack_depth_in[(size_t)orig];
            }
        }
    }
 
    const auto reachable = compute_reachable(*analysis_cfg);
    result.reducible = check_reducible(*analysis_cfg, reachable);
    result.success = result.reducible;
 
    result.ipdom.assign(analysis_cfg->size(), -1);
    result.innermost_loop_header.assign(analysis_cfg->size(), -1);
 
    const auto dom = compute_dominators(*analysis_cfg, reachable);
    const auto pdom = compute_postdominators(*analysis_cfg, reachable);
 
    int n = (int)analysis_cfg->size();
    result.ipdom = compute_ipdom_vector(pdom, n, reachable);
 
    compute_natural_loops(result, *analysis_cfg, reachable, dom);
    compute_loop_follow(result);
    compute_innermost_loop_header(result, reachable);
 
    return result;
}

References analysis::AnalysisManager::getResult().

---

The documentation for this class was generated from the following files:

• llvmexpr/analysis/passes/StructurizeCFGPass.hpp
• llvmexpr/analysis/passes/StructurizeCFGPass.cpp