VapourSynth-llvmexpr
Loading...
Searching...
No Matches
analysis::BuildCFGPass Class Reference

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

Inheritance diagram for analysis::BuildCFGPass:
Inheritance graph
[legend]
Collaboration diagram for analysis::BuildCFGPass:
Collaboration graph
[legend]

Public Types

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

Constructs the Control Flow Graph Responsibilities:

  • Identify basic blocks
  • Build successor/predecessor relationships
  • Map label names to block indices
  • Validate jump targets Depends on: None

Definition at line 45 of file BuildCFGPass.hpp.

Member Typedef Documentation

◆ Result

using analysis::BuildCFGPass::Result = BuildCFGResult

Definition at line 47 of file BuildCFGPass.hpp.

Member Function Documentation

◆ getName()

const char * analysis::BuildCFGPass::getName ( ) const
inlinenodiscardoverridevirtual

Implements analysis::Pass.

Definition at line 49 of file BuildCFGPass.hpp.

49 {
50 return "Build CFG Pass";
51 }

◆ run()

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

Implements analysis::AnalysisPass< BuildCFGPass, BuildCFGResult >.

Definition at line 28 of file BuildCFGPass.cpp.

29 {
30 Result result;
31 std::map<int, int> token_idx_to_block_idx;
32
33 int current_token_idx = 0;
34 while (static_cast<size_t>(current_token_idx) < tokens.size()) {
35 int block_idx = static_cast<int>(result.cfg_blocks.size());
36 CFGBlock block;
37 block.start_token_idx = current_token_idx;
38
39 int block_start_idx = current_token_idx;
40 token_idx_to_block_idx[block_start_idx] = block_idx;
41
42 // Register label if this block starts with one
43 if (tokens[current_token_idx].type == TokenType::LabelDef) {
44 const auto& payload =
45 std::get<TokenPayloadLabel>(tokens[current_token_idx].payload);
46 if (result.label_to_block_idx.contains(payload.name)) {
47 throw AnalysisError(
48 std::format("Duplicate label: {}", payload.name),
49 current_token_idx);
50 }
51 result.label_to_block_idx[payload.name] = block_idx;
52 }
53
54 // End of block: hit a jump or another label
55 int scan_idx = current_token_idx;
56 while (static_cast<size_t>(scan_idx) < tokens.size()) {
57 const auto& token = tokens[scan_idx];
58 if (token.type == TokenType::Jump) {
59 scan_idx++;
60 break;
61 }
62 if (scan_idx > block_start_idx &&
63 token.type == TokenType::LabelDef) {
64 break;
65 }
66 scan_idx++;
67 }
68 block.end_token_idx = scan_idx;
69 result.cfg_blocks.push_back(block);
70 current_token_idx = scan_idx;
71 }
72
73 // Build successor/predecessor relationships
74 for (size_t i = 0; i < result.cfg_blocks.size(); ++i) {
75 CFGBlock& block = result.cfg_blocks[i];
76 const auto& last_token = tokens[block.end_token_idx - 1];
77
78 if (last_token.type == TokenType::Jump) {
79 const auto& payload =
80 std::get<TokenPayloadLabel>(last_token.payload);
81
82 if (!result.label_to_block_idx.contains(payload.name)) {
83 throw AnalysisError(
84 std::format("Undefined label for jump: {}", payload.name),
85 block.end_token_idx - 1);
86 }
87
88 int target_block_idx = result.label_to_block_idx.at(payload.name);
89 block.successors.push_back(target_block_idx);
90 result.cfg_blocks[target_block_idx].predecessors.push_back(
91 static_cast<int>(i));
92
93 if (static_cast<size_t>(block.end_token_idx) < tokens.size()) {
94 int fallthrough_block_idx =
95 token_idx_to_block_idx.at(block.end_token_idx);
96 block.successors.push_back(fallthrough_block_idx);
97 result.cfg_blocks[fallthrough_block_idx].predecessors.push_back(
98 static_cast<int>(i));
99 }
100 } else {
101 if (static_cast<size_t>(block.end_token_idx) < tokens.size()) {
102 int fallthrough_block_idx =
103 token_idx_to_block_idx.at(block.end_token_idx);
104 block.successors.push_back(fallthrough_block_idx);
105 result.cfg_blocks[fallthrough_block_idx].predecessors.push_back(
106 static_cast<int>(i));
107 }
108 }
109 }
110
111 return result;
112}

References analysis::BuildCFGResult::cfg_blocks, analysis::CFGBlock::end_token_idx, Jump, analysis::BuildCFGResult::label_to_block_idx, LabelDef, analysis::CFGBlock::start_token_idx, and analysis::CFGBlock::successors.

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