analysis::StackSafetyPass Class Reference

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

Inheritance diagram for analysis::StackSafetyPass:

Collaboration diagram for analysis::StackSafetyPass:

Public Types
using	Result = StackSafetyResult
Public Types inherited from analysis::AnalysisPass< StackSafetyPass, StackSafetyResult >
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

Verifies that:

1. All execution paths have consistent stack depths at merge points
2. No stack underflows occur (sufficient depth before pop operations)
3. All reachable terminal blocks end with expected final depth This is the final safety check before code generation. Depends on: BlockAnalysisPass

Definition at line 41 of file StackSafetyPass.hpp.

Member Typedef Documentation

Result

using analysis::StackSafetyPass::Result = StackSafetyResult

Definition at line 44 of file StackSafetyPass.hpp.

Member Function Documentation

getName()

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

inlinenodiscardoverridevirtual

Implements analysis::Pass.

Definition at line 46 of file StackSafetyPass.hpp.

                                                       {
        return "Stack Safety Pass";
    }

run()

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

overridevirtual

Implements analysis::AnalysisPass< StackSafetyPass, StackSafetyResult >.

Definition at line 29 of file StackSafetyPass.cpp.

                                                                  {
    const auto& block_result = am.getResult<BlockAnalysisPass>();
    const auto& cfg_blocks = block_result.cfg_blocks;
 
    int expected_final_depth = am.getExpectedFinalDepth();
 
    Result result;
    result.stack_depth_in.assign(cfg_blocks.size(), -1);
 
    std::vector<int> worklist;
 
    if (!cfg_blocks.empty()) {
        result.stack_depth_in[0] = 0;
        worklist.push_back(0);
    }
 
    size_t processed_count = 0;
    while (!worklist.empty()) {
        processed_count++;
        if (processed_count >
            cfg_blocks.size() * cfg_blocks.size()) { // Heuristic
            throw AnalysisError(std::format(
                "Failed to prove stack safety; check loops. "
                "processed_count = {}, cfg_blocks = {}, heuristic_limit = {}, "
                "worklist_size = {}, next_block_candidate = {}",
                processed_count, cfg_blocks.size(),
                cfg_blocks.size() * cfg_blocks.size(), worklist.size(),
                worklist.back()));
        }
 
        int block_idx = worklist.back();
        worklist.pop_back();
 
        const auto& block = cfg_blocks[block_idx];
        int depth_in = result.stack_depth_in[block_idx];
 
        if (depth_in < block.min_stack_needed) {
            throw AnalysisError(
                std::format("Stack underflow before executing block {}: "
                            "depth_in = {}, min_needed = {}, start token '{}'",
                            block_idx, depth_in, block.min_stack_needed,
                            tokens[block.start_token_idx].text),
                block.start_token_idx);
        }
 
        int depth_out = depth_in + block.stack_effect;
 
        for (int succ_idx : block.successors) {
            if (result.stack_depth_in[succ_idx] == -1) {
                result.stack_depth_in[succ_idx] = depth_out;
                worklist.push_back(succ_idx);
            } else if (result.stack_depth_in[succ_idx] != depth_out) {
                throw AnalysisError(
                    std::format(
                        "Stack depth mismatch on converging paths: "
                        "block {} -> successor {}. "
                        "incoming depth = {}, recorded successor depth = {}, "
                        "current start token '{}', successor start token '{}'",
                        block_idx, succ_idx, depth_out,
                        result.stack_depth_in[succ_idx],
                        tokens[block.start_token_idx].text,
                        tokens[cfg_blocks[succ_idx].start_token_idx].text),
                    cfg_blocks[succ_idx].start_token_idx);
            }
        }
    }
 
    for (size_t i = 0; i < cfg_blocks.size(); ++i) {
        if (result.stack_depth_in[i] != -1 &&
            cfg_blocks[i].successors.empty()) { // Reachable terminal block
            int final_depth =
                result.stack_depth_in[i] + cfg_blocks[i].stack_effect;
            if (final_depth != expected_final_depth) {
                throw AnalysisError(
                    std::format(
                        "Expression stack not balanced on "
                        "reachable terminal block {}: "
                        "final depth = {}, expected = {}, start token '{}'",
                        i, final_depth, expected_final_depth,
                        tokens[cfg_blocks[i].start_token_idx].text),
                    cfg_blocks[i].start_token_idx);
            }
        }
    }
 
    return result;
}

References analysis::AnalysisManager::getExpectedFinalDepth(), analysis::AnalysisManager::getResult(), and analysis::StackSafetyResult::stack_depth_in.

---

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

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