A programming language is not a language without statements
that affect the control flow. Arguably there is already a
return statement, which can immediately
transfer the control back to the caller, but the language
still misses conditions and loops.
Conditions are implemented in the form of
if statements. These statements start with the
if keyword, which is followed by an expression
and a block. This series of tokens can optionally be
followed by an else keyword and another
if statement, or a block.
<ifStatement>
::= 'if' <expr> <block> ('else' (<ifStatement> | <block>))?This allows the programmers to create different branches in their code.
fn condition(x: number) {
if x == 2 {
...
} else if x == 3 {
...
} else {
...
}
}Design Note
A well-known problem with conditions is the dangling else problem. It happens when the block is not mandatory after the condition and multiple nested conditions are followed by one
elsebranch.if (1) if (2) return 0; else return 1;Does the
elsebranch belong to the first condition or the second one? The parser needs to know this to construct the correct AST.By making the block mandatory, this question becomes simple to answer.
if (1) { if (2) { ... } } else { return 1; }Also, notice that the
( ... )around the condition was necessary for the parser to know where the condition ends if it's not followed by a block. With making the block mandatory these symbols are no longer needed as the parser knows the condition ends before the{token.
To start extending the language with conditions, the
if and else keywords must be
introduced to the lexer.
enum class TokenKind : char {
...
KwIf,
KwElse,
...
};
const std::unordered_map<std::string_view, TokenKind> keywords = {
...,
{"if", TokenKind::KwIf}, {"else", TokenKind::KwElse}};
In the AST the if statement has a condition and
a block for its true and false branches respectively even
though in the else if case, the else branch is
not a block, but a statement.
The else if case is actually a syntactic sugar
for else { if ... } and to keep the grammar and
the AST simple, it is also parsed that way.
struct IfStmt : public Stmt {
std::unique_ptr<Expr> condition;
std::unique_ptr<Block> trueBlock;
std::unique_ptr<Block> falseBlock;
IfStmt(SourceLocation location,
std::unique_ptr<Expr> condition,
std::unique_ptr<Block> trueBlock,
std::unique_ptr<Block> falseBlock = nullptr)
: Stmt(location),
condition(std::move(condition)),
trueBlock(std::move(trueBlock)),
falseBlock(std::move(falseBlock)) {}
void dump(size_t level = 0) const override;
};The textual representation of the node includes the condition, the true block and the false block if it's present.
void IfStmt::dump(size_t level) const {
std::cerr << indent(level) << "IfStmt\n";
condition->dump(level + 1);
trueBlock->dump(level + 1);
if (falseBlock)
falseBlock->dump(level + 1);
}
In the parser, the IfStmt gets its dedicated
parser method, which is called from
parseStmt().
std::unique_ptr<Stmt> Parser::parseStmt() {
if (nextToken.kind == TokenKind::KwIf)
return parseIfStmt();
...
}
The method expects the next token to be
KwIf, which it eats and then proceeds with
parsing the condition of the statement.
std::unique_ptr<IfStmt> Parser::parseIfStmt() {
SourceLocation location = nextToken.location;
eatNextToken(); // eat 'if'
varOrReturn(condition, parseExpr());
...
}
If the next token is not the beginning of a block an error
is reported, otherwise the true block is parsed. If the
block is not followed by an else keyword the
statement only has a true block and an AST node can be
returned.
std::unique_ptr<IfStmt> Parser::parseIfStmt() {
...
matchOrReturn(TokenKind::Lbrace, "expected 'if' body");
varOrReturn(trueBlock, parseBlock());
if (nextToken.kind != TokenKind::KwElse)
return std::make_unique<IfStmt>(location, std::move(condition),
std::move(trueBlock));
...
}
If there is an else branch, the
KwElse token is eaten. If this branch is not an
else if, the block is parsed and the AST node
is returned.
std::unique_ptr<IfStmt> Parser::parseIfStmt() {
...
eatNextToken(); // eat 'else'
std::unique_ptr<Block> falseBlock;
if (nextToken.kind == TokenKind::KwIf) {
...
} else {
matchOrReturn(TokenKind::Lbrace, "expected 'else' body");
falseBlock = parseBlock();
}
if (!falseBlock)
return nullptr;
return std::make_unique<IfStmt>(location, std::move(condition),
std::move(trueBlock), std::move(falseBlock));
}
If the branch is an else if, the other if
statement is parsed and put into a manually created false
block.
std::unique_ptr<IfStmt> Parser::parseIfStmt() {
...
if (nextToken.kind == TokenKind::KwIf) {
varOrReturn(elseIf, parseIfStmt());
SourceLocation loc = elseIf->location;
std::vector<std::unique_ptr<Stmt>> stmts;
stmts.emplace_back(std::move(elseIf));
falseBlock = std::make_unique<Block>(loc, std::move(stmts));
}
...
}
The resolved node of the if statement is
identical to its non-resolved counterpart.
struct ResolvedIfStmt : public ResolvedStmt {
std::unique_ptr<ResolvedExpr> condition;
std::unique_ptr<ResolvedBlock> trueBlock;
std::unique_ptr<ResolvedBlock> falseBlock;
ResolvedIfStmt(SourceLocation location,
std::unique_ptr<ResolvedExpr> condition,
std::unique_ptr<ResolvedBlock> trueBlock,
std::unique_ptr<ResolvedBlock> falseBlock = nullptr)
: ResolvedStmt(location),
condition(std::move(condition)),
trueBlock(std::move(trueBlock)),
falseBlock(std::move(falseBlock)) {}
void dump(size_t level = 0) const override;
};The similarity persists even in the textual representation of the node.
void ResolvedIfStmt::dump(size_t level) const {
std::cerr << indent(level) << "ResolvedIfStmt\n";
condition->dump(level + 1);
trueBlock->dump(level + 1);
if (falseBlock)
falseBlock->dump(level + 1);
}
The resolution of the statement is driven by
resolveStmt().
std::unique_ptr<ResolvedStmt> Sema::resolveStmt(const Stmt &stmt) {
...
if (auto *ifStmt = dynamic_cast<const IfStmt *>(&stmt))
return resolveIfStmt(*ifStmt);
...
}First, the condition is resolved and checked if it's a number.
std::unique_ptr<ResolvedIfStmt> Sema::resolveIfStmt(const IfStmt &ifStmt) {
varOrReturn(condition, resolveExpr(*ifStmt.condition));
if (condition->type.kind != Type::Kind::Number)
return report(condition->location, "expected number in condition");
...
}Then the semantic analyzer proceeds with resolving the true block and if present, the false block too.
std::unique_ptr<ResolvedIfStmt> Sema::resolveIfStmt(const IfStmt &ifStmt) {
...
varOrReturn(resolvedTrueBlock, resolveBlock(*ifStmt.trueBlock));
std::unique_ptr<ResolvedBlock> resolvedFalseBlock;
if (ifStmt.falseBlock) {
resolvedFalseBlock = resolveBlock(*ifStmt.falseBlock);
if (!resolvedFalseBlock)
return nullptr;
}
...
}Once everything is resolved, it's checked if the value of the condition is a compile-time constant and the value is set accordingly.
std::unique_ptr<ResolvedIfStmt> Sema::resolveIfStmt(const IfStmt &ifStmt) {
...
condition->setConstantValue(cee.evaluate(*condition, false));
return std::make_unique<ResolvedIfStmt>(ifStmt.location, std::move(condition),
std::move(resolvedTrueBlock),
std::move(resolvedFalseBlock));
}
The code generation is driven by
generateStmt().
llvm::Value *Codegen::generateStmt(const ResolvedStmt &stmt) {
...
if (auto *ifStmt = dynamic_cast<const ResolvedIfStmt *>(&stmt))
return generateIfStmt(*ifStmt);
...
}
The idea for representing an IfStmt in LLVM IR
is to create a new basic block for all of its branches, and
another one for the rest of the code after the statement.
┌─────────────────────────────────────────────┐
│ br i1 %con, label %if.true, label %if.false │
└─────────────────────────────────────────────┘
┌───────────┴───────────┐
V V
┌─────────────────────┐ ┌─────────────────────┐
│ if.true: │ │ if.false: │
│ br label %if.exit │ │ br label %if.exit │
└─────────────────────┘ └─────────────────────┘
└───────────┬───────────┘
V
┌─────────────────────┐
│ if.exit: │
│ ... │
└─────────────────────┘
When there is no else block in the source code,
the exit block is treated as the else block.
┌─────────────────────────────────────────────┐
│ br i1 %cond, label %if.true, label %if.exit │
└─────────────────────────────────────────────┘
┌───────────┴───────────┐
V │
┌─────────────────────┐ │
│ if.true: │ │
│ br label %if.exit │ │
└─────────────────────┘ │
├───────────────────────┘
V
┌─────────────────────┐
│ if.exit: │
│ ... │
└─────────────────────┘
First, a new basic block is created for the true, false and exit blocks. Unless there is an explicit false block, the false block is set to be the exit block as mentioned.
llvm::Value *Codegen::generateIfStmt(const ResolvedIfStmt &stmt) {
llvm::Function *function = getCurrentFunction();
auto *trueBB = llvm::BasicBlock::Create(context, "if.true");
auto *exitBB = llvm::BasicBlock::Create(context, "if.exit");
llvm::BasicBlock *elseBB = exitBB;
if (stmt.falseBlock)
elseBB = llvm::BasicBlock::Create(context, "if.false");
...
}Then the condition is generated and a jump to either the true or the false block based on its value is inserted. Because this instruction expects the condition to be a logical value, it is converted to bool first.
llvm::Value *Codegen::generateIfStmt(const ResolvedIfStmt &stmt) {
...
llvm::Value *cond = generateExpr(*stmt.condition);
builder.CreateCondBr(doubleToBool(cond), trueBB, elseBB);
...
}After generating the condition, the true and the false blocks are created and the required break instructions are inserted.
llvm::Value *Codegen::generateIfStmt(const ResolvedIfStmt &stmt) {
...
trueBB->insertInto(function);
builder.SetInsertPoint(trueBB);
generateBlock(*stmt.trueBlock);
builder.CreateBr(exitBB);
if (stmt.falseBlock) {
elseBB->insertInto(function);
builder.SetInsertPoint(elseBB);
generateBlock(*stmt.falseBlock);
builder.CreateBr(exitBB);
}
...
}Finally, the blocks are inserted into the function and the insertion point is set to the exit block.
llvm::Value *Codegen::generateIfStmt(const ResolvedIfStmt &stmt) {
...
exitBB->insertInto(function);
builder.SetInsertPoint(exitBB);
return nullptr;
}
Loops come in handy when the same statement needs to be
repeated multiple times. Without them, the developer would
be required to write the same statement on multiple lines
after each other, unless the number of times the statement
needs to be run is unknown. In that case, the problem
becomes difficult to solve without a dedicated element in
the language. In
your language, this dedicated element is the
while loop.
<whileStatement>
::= 'while' <expr> <block>
The grammar rule introduces a new keyword,
while.
enum class TokenKind : char {
...
KwWhile,
...
};
const std::unordered_map<std::string_view, TokenKind> keywords = {
..., {"while", TokenKind::KwWhile}};
The AST node of the while statement stores an
Expr for its condition and a block.
struct WhileStmt : public Stmt {
std::unique_ptr<Expr> condition;
std::unique_ptr<Block> body;
WhileStmt(SourceLocation location,
std::unique_ptr<Expr> condition,
std::unique_ptr<Block> body)
: Stmt(location),
condition(std::move(condition)),
body(std::move(body)) {}
void dump(size_t level = 0) const override;
};The textual representation of the node also includes these fields.
void WhileStmt::dump(size_t level) const {
std::cerr << indent(level) << "WhileStmt\n";
condition->dump(level + 1);
body->dump(level + 1);
}
As in the case of every other statement, the parsing is
driven by parseStmt().
std::unique_ptr<Stmt> Parser::parseStmt() {
...
if (nextToken.kind == TokenKind::KwWhile)
return parseWhileStmt();
...
}
The parseWhileStmt() method is small and
simple. It only parses the condition and the body. If
everything is successful, the corresponding AST node is
returned.
std::unique_ptr<WhileStmt> Parser::parseWhileStmt() {
SourceLocation location = nextToken.location;
eatNextToken(); // eat 'while'
varOrReturn(cond, parseExpr());
matchOrReturn(TokenKind::Lbrace, "expected 'while' body");
varOrReturn(body, parseBlock());
return std::make_unique<WhileStmt>(location, std::move(cond),
std::move(body));
}
Similarly to if statements, the resolved node
of WhileStmt is identical to its non-resolved
counterpart.
struct ResolvedWhileStmt : public ResolvedStmt {
std::unique_ptr<ResolvedExpr> condition;
std::unique_ptr<ResolvedBlock> body;
ResolvedWhileStmt(SourceLocation location,
std::unique_ptr<ResolvedExpr> condition,
std::unique_ptr<ResolvedBlock> body)
: ResolvedStmt(location),
condition(std::move(condition)),
body(std::move(body)) {}
void dump(size_t level = 0) const override;
};Their textual representations are also the same except for the name of the node.
void ResolvedWhileStmt::dump(size_t level) const {
std::cerr << indent(level) << "ResolvedWhileStmt\n";
condition->dump(level + 1);
body->dump(level + 1);
}
The resolution of the statement is driven by
resolveStmt().
std::unique_ptr<ResolvedStmt> Sema::resolveStmt(const Stmt &stmt) {
...
if (auto *whileStmt = dynamic_cast<const WhileStmt *>(&stmt))
return resolveWhileStmt(*whileStmt);
...
}First, the condition is resolved and checked to be a number.
std::unique_ptr<ResolvedWhileStmt>
Sema::resolveWhileStmt(const WhileStmt &whileStmt) {
varOrReturn(condition, resolveExpr(*whileStmt.condition));
if (condition->type.kind != Type::Kind::Number)
return report(condition->location, "expected number in condition");
...
}Then the resolution is continued with resolving the body.
std::unique_ptr<ResolvedWhileStmt>
Sema::resolveWhileStmt(const WhileStmt &whileStmt) {
...
varOrReturn(body, resolveBlock(*whileStmt.body));
...
}Finally, the condition is evaluated as a compile-time constant and the corresponding resolved node is returned.
std::unique_ptr<ResolvedWhileStmt>
Sema::resolveWhileStmt(const WhileStmt &whileStmt) {
...
condition->setConstantValue(cee.evaluate(*condition, false));
return std::make_unique<ResolvedWhileStmt>(
whileStmt.location, std::move(condition), std::move(body));
}Code generation is driven by generateStmt().
llvm::Value *Codegen::generateStmt(const ResolvedStmt &stmt) {
...
if (auto *whileStmt = dynamic_cast<const ResolvedWhileStmt *>(&stmt))
return generateWhileStmt(*whileStmt);
...
}
A while loop in LLVM IR consists of multiple
basic blocks. The condition is placed into its separate
block, as it has to be evaluated before every iteration. One
more block is created for the body of the loop, which always
jumps back to the condition and another one is created for
the rest of the code that runs after the loop.
┌───────────────────────┐
│ ... │
│ br label %while.cond │
└───────────────────────┘
|
V
┌─────────────────────────────────────────────────────┐
│ while.cond: │
│ ... │
│ br i1 %cond, label %while.body, label %while.exit │
└─────────────────────────────────────────────────────┘
| ^ |
V | V
┌────────────────────────┐ ┌────────────────────────┐
│ while.body: │ │ while.exit: │
│ br label %while.cond │ │ ... │
└────────────────────────┘ └────────────────────────┘First, the blocks for the condition, body and the rest of the code are created. By convention, the block with the condition is called the header of the loop. A jump to the header is also inserted into the current block.
llvm::Value *Codegen::generateWhileStmt(const ResolvedWhileStmt &stmt) {
llvm::Function *function = getCurrentFunction();
auto *header = llvm::BasicBlock::Create(context, "while.cond", function);
auto *body = llvm::BasicBlock::Create(context, "while.body", function);
auto *exit = llvm::BasicBlock::Create(context, "while.exit", function);
builder.CreateBr(header);
...
}Next, the condition is generated into the header followed by the insertion of a conditional jump to either the body or the exit block. The conditional jump expects a logical value, so the condition is first converted to bool.
llvm::Value *Codegen::generateWhileStmt(const ResolvedWhileStmt &stmt) {
...
builder.SetInsertPoint(header);
llvm::Value *cond = generateExpr(*stmt.condition);
builder.CreateCondBr(doubleToBool(cond), body, exit);
...
}Finally, the body of the loop is generated into the corresponding block followed by the insertion of a jump back to the header. Upon finishing the generation of the body, the insertion point is set to the exit block.
llvm::Value *Codegen::generateWhileStmt(const ResolvedWhileStmt &stmt) {
...
builder.SetInsertPoint(body);
generateBlock(*stmt.body);
builder.CreateBr(header);
builder.SetInsertPoint(exit);
return nullptr;
}The control flow graph is a graph representation of all paths the program might traverse during its execution. It is a required data structure for many optimization and analysis techniques. It is also essential for any kind of flow-sensitive reasoning about the program and can be used to make code generation easier or to simulate the execution of the program without actually compiling and running it.
How the CFG is constructed varies on what it is going to be used for. This compiler uses it for performing a simple flow-sensitive analysis and data-flow analysis later, so the minimalistic CFG is constructed with these goals in mind.
Design Note
Different production-ready compilers construct different control flow graphs and use them for different purposes.
In Clang the CFG was created for the Clang Static Analyzer to be able to perform symbolic execution. As a result, the Clang CFG is the list of the statements of the program in the order they are executed. This way the Clang Static Analyzer can traverse the statements from top to bottom and simulate their execution as if the program was running.
[B1] 1: 0 2: int x = 0; 3: x int x = 0; 4: [B1.3] (ImplicitCastExpr, ...) int y = x; 5: int y = x; x = 1; 6: 1 7: x 8: [B1.7] = [B1.6] Preds (1): B2 Succs (1): B0Notice that
[B1.3]and[B1.7]are the same kind of statements. The former is reading the value ofxwhile at the latterxis about to be assigned a value, but this information is not known while traversing the CFG and it can be an issue if the CFG is used for data flow analysis or code generation. During code generation[B1.3]needs to be a load instruction, while[B1.7]needs to be a store.The Kotlin CFG on the other hand is used for data flow analysis, so it is an implementation of the already introduced SSA form.
$1 = 0 x = $1 var x = 0 val y = x $2 = x x = 1 y = $2 $3 = 1 x = $3Here it can be clearly seen that when
xis on the LHS, it's an assignment and when it's on the RHS, it's reading its value.
The CFG consists of the basic blocks of the program and the edges between them. Each basic block consists of a set of statements that execute together as well as a list of predecessors from which the program can enter this block and a set of successors to which the program can continue from it.
struct BasicBlock {
std::set<std::pair<int, bool>> predecessors;
std::set<std::pair<int, bool>> successors;
std::vector<const ResolvedStmt *> statements;
};
In the predecessors and
successors sets, the int refers to
the number of the block, while the
bool indicates whether that block is reachable
or not.
The CFG is modelled as a list of basic blocks. It also knows which block is the entry of the function and which is the exit.
struct CFG {
std::vector<BasicBlock> basicBlocks;
int entry = -1;
int exit = -1;
...
};Three operations are supported on the CFG.
struct CFG {
...
int insertNewBlock() {
basicBlocks.emplace_back();
return basicBlocks.size() - 1;
};
int insertNewBlockBefore(int before, bool reachable) {
int b = insertNewBlock();
insertEdge(b, before, reachable);
return b;
}
void insertEdge(int from, int to, bool reachable) {
basicBlocks[from].successors.emplace(std::make_pair(to, reachable));
basicBlocks[to].predecessors.emplace(std::make_pair(from, reachable));
}
void insertStmt(const ResolvedStmt *stmt, int block) {
basicBlocks[block].statements.emplace_back(stmt);
}
...
};
The logic for constructing a CFG is encapsulated by the
CFGBuilder class. It takes a function and
builds the CFG for that function.
class CFGBuilder {
CFG cfg;
public:
CFG build(const ResolvedFunctionDecl &fn);
};
The construction of the CFG happens from the end of the
function to the beginning of the function. The
build() method first creates the exit block,
then inserts the body of the function and finally inserts
the entry block.
Return statements automatically jump to the exit block, so by inserting the exit block first, the edge between the block ending with a return statement and the exit block can immediately be inserted. From a top-to-bottom construction, these blocks would need to be collected first and the edges can only be inserted once the builder finished processing the function.
CFG CFGBuilder::build(const ResolvedFunctionDecl &fn) {
cfg = {};
cfg.exit = cfg.insertNewBlock();
int body = insertBlock(*fn.body, cfg.exit);
cfg.entry = cfg.insertNewBlockBefore(body, true);
return cfg;
};
The insertBlock() method first creates a new
CFG block for the given ResolvedBlock if it is
not empty, and then traverses its statements in reverse
order while inserting them into the actual CFG block.
To be able to create the new BasicBlock, the
method takes the number of the successor block as a
parameter. The return value is the number of the
BasicBlock from which the CFG construction
should continue after the final statement has been inserted.
int CFGBuilder::insertBlock(const ResolvedBlock &block, int succ) {
const auto &stmts = block.statements;
bool insertNewBlock = true;
for (auto it = stmts.rbegin(); it != stmts.rend(); ++it) {
if (insertNewBlock)
succ = cfg.insertNewBlockBefore(succ, true);
insertNewBlock = false;
succ = insertStmt(**it, succ);
}
return succ;
}The following figure showcases how the CFG of a function with no control flow elements is built.
fn cfgConstruction(): void {
stmt1;
stmt2;
stmt3;
}
1.) create the exit block for the function
┌─────────┐
│ fn.exit │
└─────────┘
2.) insertBlock(fn.body, fn.exit)
return this block -> ┌─────────┐
┌─────────┐ │ stmt1; │
┌─────────┐ ┌─────────┐ │ stmt2; │ │ stmt2; │
│ │ │ stmt3; │ │ stmt3; │ │ stmt3; │
└─────────┘ └─────────┘ └─────────┘ └─────────┘
│ │ │ │
V V V V
┌─────────┐ ┌─────────┐ ┌─────────┐ ┌─────────┐
│ fn.exit │ │ fn.exit │ │ fn.exit │ │ fn.exit │
└─────────┘ └─────────┘ └─────────┘ └─────────┘
3.) create and insert the entry block
┌──────────┐
│ fn.entry │
└──────────┘
│
V
┌─────────┐
│ stmt1; │
│ stmt2; │
│ stmt3; │
└─────────┘
│
V
┌─────────┐
│ fn.exit │
└─────────┘
The insertStmt() method takes the statement and
the basic block to which the statement should be inserted
into as parameters. It then dispatches the correct insert
function for the given statement.
int CFGBuilder::insertStmt(const ResolvedStmt &stmt, int block) {
if (auto *ifStmt = dynamic_cast<const ResolvedIfStmt *>(&stmt))
return insertIfStmt(*ifStmt, block);
if (auto *whileStmt = dynamic_cast<const ResolvedWhileStmt *>(&stmt))
return insertWhileStmt(*whileStmt, block);
if (auto *expr = dynamic_cast<const ResolvedExpr *>(&stmt))
return insertExpr(*expr, block);
if (auto *returnStmt = dynamic_cast<const ResolvedReturnStmt *>(&stmt))
return insertReturnStmt(*returnStmt, block);
llvm_unreachable("unexpected expression");
}
When a return statement is inserted, the builder stops
processing the current block and creates a new one right
before the exit block. Because the graph is constructed from
bottom to top, the ReturnStmt is inserted
first, then the expression whose result it returns.
int CFGBuilder::insertReturnStmt(const ResolvedReturnStmt &stmt, int block) {
block = cfg.insertNewBlockBefore(cfg.exit, true);
cfg.insertStmt(&stmt, block);
if (stmt.expr)
return insertExpr(*stmt.expr, block);
return block;
}Below can be seen the visualization of how a return statement affects the construction of the current basic block.
fn cfgConstruction(): number {
stmt1;
return 0;
stmt2;
}
1.) insert stmt2
┌─────────┐
│ stmt2; │
└─────────┘
│
V
┌─────────┐
│ fn.exit │
└─────────┘
2.) insertReturnStmt()
return this block -> ┌─────────┐
┌─────────┐ ┌─────────┐ │ 0; │
┌─│ │ ┌─│ return; │ ┌─│ return; │
│ └─────────┘ │ └─────────┘ │ └─────────┘
│ ┌─────────┐ │ ┌─────────┐ │ ┌─────────┐
│ │ stmt2; │─┐ │ │ stmt2; │─┐ │ │ stmt2; │─┐
│ └─────────┘ │ │ └─────────┘ │ │ └─────────┘ │
│ ┌─────────┐ │ │ ┌─────────┐ │ │ ┌─────────┐ │
└>│ fn.exit │<┘ └>│ fn.exit │<┘ └>│ fn.exit │<┘
└─────────┘ └─────────┘ └─────────┘
3.) insert stmt1
┌─────────┐
│ stmt1; │
│ 0; │
┌─│ return; │
│ └─────────┘
│ ┌─────────┐
│ │ stmt2; │─┐
│ └─────────┘ │
│ ┌─────────┐ │
└>│ fn.exit │<┘
└─────────┘
In the case of expressions, first, the expression is inserted, then its child expressions in reverse order of their evaluation.
int CFGBuilder::insertExpr(const ResolvedExpr &expr, int block) {
cfg.insertStmt(&expr, block);
if (const auto *call = dynamic_cast<const ResolvedCallExpr *>(&expr)) {
for (auto it = call->arguments.rbegin(); it != call->arguments.rend(); ++it)
insertExpr(**it, block);
return block;
}
if (const auto *grouping = dynamic_cast<const ResolvedGroupingExpr *>(&expr))
return insertExpr(*grouping->expr, block);
if (const auto *binop = dynamic_cast<const ResolvedBinaryOperator *>(&expr))
return insertExpr(*binop->rhs, block), insertExpr(*binop->lhs, block);
if (const auto *unop = dynamic_cast<const ResolvedUnaryOperator *>(&expr))
return insertExpr(*unop->operand, block);
return block;
}
Note that for conditional binary operators, this insertion tactic leads to a little inaccurate CFG.
stmt1;
1 || 2;
stmt2;
┌─────────┐
│ stmt1; │
│ 1; │
│ 2; │
│ ||; │
│ stmt2; │
└─────────┘
Because the || and && operators
are lazily evaluated, if the LHS yields a result from which
the result of the whole operator can be determined, the RHS
is not evaluated. Depending on the goal of the CFG this
should also be modelled.
stmt1;
1 || 2;
stmt2;
┌─────────┐
│ stmt1; │
│ 1; │─────┐
└─────────┘ V
│ ┌─────────┐
│ │ 2; │
V └─────────┘
┌─────────┐ │
│ ||; │<────┘
│ stmt2; │
└─────────┘Since this compiler wouldn't take advantage of such accuracy, and constructing such detailed CFG is not a trivial task, this not completely accurate version is used. This way the CFG and its construction are kept as simple as possible.
In the case of an IfStmt the inserter method
takes the exit block as its parameter. If there is a false
block, it is inserted first, otherwise, the exit block is
considered to be the false block.
int CFGBuilder::insertIfStmt(const ResolvedIfStmt &stmt, int exit) {
int falseBlock = exit;
if (stmt.falseBlock)
falseBlock = insertBlock(*stmt.falseBlock, exit);
...
}This is followed by the insertion of the true block and the creation of the entry block.
int CFGBuilder::insertIfStmt(const ResolvedIfStmt &stmt, int exit) {
...
int trueBlock = insertBlock(*stmt.trueBlock, exit);
int entry = cfg.insertNewBlock();
...
}
The tree walk interpreter is invoked to determine if the
condition is always true or not. Since in this case even
statements like sideEffect() || true should be
returned as true, the interpreter is invoked
with the allowSideEffects option turned on.
The true block is reachable only if the condition is not
0, while the false block is reachable only if
the condition is 0 or unknown.
int CFGBuilder::insertIfStmt(const ResolvedIfStmt &stmt, int exit) {
...
std::optional<double> val = cee.evaluate(*stmt.condition, true);
cfg.insertEdge(entry, trueBlock, val != 0);
cfg.insertEdge(entry, falseBlock, val.value_or(0) == 0);
...
}Finally, the statement itself is inserted into the entry block followed by the insertion of the condition.
int CFGBuilder::insertIfStmt(const ResolvedIfStmt &stmt, int exit) {
...
cfg.insertStmt(&stmt, entry);
return insertExpr(*stmt.condition, entry);
}
Below can be seen the visualization of how the body of a
function with an
IfStmt is inserted into the CFG.
fn cfgConstruction(): number {
stmt1;
if cond {
stmt2;
} else {
stmt3;
}
stmt4;
}
1.) insert stmt4
┌─────────┐
│ stmt4; │
└─────────┘
│
V
┌─────────┐
│ fn.exit │
└─────────┘
2.) insertIfStmt()
return this block -> ┌─────────┐
│ cond; │
│ if; │─┐
└─────────┘ │
│ │
V │
┌─────────┐ ┌─────────┐ │
┌─│ stmt2; │ ┌─│ stmt2; │ │
│ └─────────┘ │ └─────────┘ │
┌─────────┐ │ ┌─────────┐ │ ┌─────────┐ │
│ stmt3; │ │ │ stmt3; │ │ │ stmt3; │<┘
└─────────┘ │ └─────────┘ │ └─────────┘
│ │ │ │ │
V │ V │ V
┌─────────┐ │ ┌─────────┐ │ ┌─────────┐
│ stmt4; │ └>│ stmt4; │ └>│ stmt4; │
└─────────┘ └─────────┘ └─────────┘
│ │ │
V V V
┌─────────┐ ┌─────────┐ ┌─────────┐
│ fn.exit │ │ fn.exit │ │ fn.exit │
└─────────┘ └─────────┘ └─────────┘
3.) insert stmt1
┌─────────┐
│ stmt1; │
│ cond; │
│ if; │─┐
└─────────┘ │
│ │
...
The last statement to handle is the WhileStmt.
Similarly to the previous method,
insertWhileStmt() also takes the exit block as
its parameter.
For this loop, one additional helper block is inserted,
which by terminology is called the latch. This
is the block after the body that loops back to the
condition. After the latch, the body of the loop is inserted
with the latch as its successor. Finally, the header is
inserted along with an edge between the latch and itself.
int CFGBuilder::insertWhileStmt(const ResolvedWhileStmt &stmt, int exit) {
int latch = cfg.insertNewBlock();
int body = insertBlock(*stmt.body, latch);
int header = cfg.insertNewBlock();
cfg.insertEdge(latch, header, true);
...
}For the condition, it's checked if its value is known in compile time and the reachability of the edges is set accordingly.
The body of the loop is only reachable from the header if
the condition is not 0, while the exit block is
only reachable if the value is 0 or unknown.
int CFGBuilder::insertWhileStmt(const ResolvedWhileStmt &stmt, int exit) {
...
std::optional<double> val = cee.evaluate(*stmt.condition, true);
cfg.insertEdge(header, body, val != 0);
cfg.insertEdge(header, exit, val.value_or(0) == 0);
...
}Finally, the statement and the condition are inserted into the header node and the header is returned.
int CFGBuilder::insertWhileStmt(const ResolvedWhileStmt &stmt, int exit) {
...
cfg.insertStmt(&stmt, header);
insertExpr(*stmt.condition, header);
return header;
}Because the header houses the condition, if there is any other statement before it, a new block needs to be created before the header that houses that statement.
int CFGBuilder::insertBlock(const ResolvedBlock &block, int succ) {
...
for (auto it = stmts.rbegin(); it != stmts.rend(); ++it) {
...
insertNewBlock = dynamic_cast<const ResolvedWhileStmt *>(it->get());
...
}
...
}
The following figure shows step-by-step how the body of a
function with a
while loop is inserted into the CFG.
fn cfgConstruction(): number {
stmt1;
while cond {
stmt2;
}
stmt3;
}
1.) insert stmt3
┌─────────┐
│ stmt3; │
└─────────┘
│
V
┌─────────┐
│ fn.exit │
└─────────┘
2.) insertWhileStmt()
┌─────────┐
│ cond; │
┌─│ while; │<┐
│ └─────────┘ │
│ │ │
│ V │
┌─────────┐ │ ┌─────────┐ │
│ stmt2; │ │ │ stmt2; │ │
└─────────┘ │ └─────────┘ │
│ │ │ │
V │ V │
┌─────────┐ ┌─────────┐ │ ┌─────────┐ │
│ latch │ │ latch │ │ │ latch │─┘
└─────────┘ └─────────┘ │ └─────────┘
┌─────────┐ ┌─────────┐ │ ┌─────────┐
│ stmt3; │ │ stmt3; │ └>│ stmt3; │
└─────────┘ └─────────┘ └─────────┘
│ │ │
V V V
┌─────────┐ ┌─────────┐ ┌─────────┐
│ fn.exit │ │ fn.exit │ │ fn.exit │
└─────────┘ └─────────┘ └─────────┘
3.) insert stmt1
┌─────────┐
│ stmt1; │
└─────────┘
│
V
┌─────────┐
│ cond; │
┌─│ while; │<┐
│ └─────────┘ │
│ │ │
...
One additional case to handle is when a block is about to be
created but the statement that is going to be inserted into
the new block is a statement that terminates the block, like
ReturnStmt, WhileStmt and
IfStmt.
In those cases, the block shouldn't be created. A terminating statement creates a new block on its own and the created block would stay empty.
int CFGBuilder::insertBlock(const ResolvedBlock &block, int succ) {
...
if (insertNewBlock && !isTerminator(**it))
succ = cfg.insertNewBlockBefore(succ, true);
...
}The terminator statements are the ones already listed above.
bool isTerminator(const ResolvedStmt &stmt) {
return dynamic_cast<const ResolvedIfStmt *>(&stmt) ||
dynamic_cast<const ResolvedWhileStmt *>(&stmt) ||
dynamic_cast<const ResolvedReturnStmt *>(&stmt);
}The following visualization explains this edge case by showing what happens when two return statements follow each other.
incorrect graph:
┌─────────┐
│ return; │
└─────────┘
|
V
┌─────────┐ ┌─────────┐
│ │ │ │
└─────────┘ └─────────┘
| |
V V
┌─────────┐ ┌─────────┐ ┌─────────┐
│ return; │ │ return; │ │ return; │
└─────────┘ └─────────┘ └─────────┘
correct graph:
┌─────────┐
│ return; │
└─────────┘
|
V
┌─────────┐ ┌─────────┐
│ return; │ │ return; │
└─────────┘ └─────────┘
The users of the compiler are provided with the option to
visualize the generated control flow graph, but first the
dump() method of the CFG needs to be defined.
Because the entry block is inserted last, the blocks are printed in a reverse order, so that the CFG dump starts with the entry block.
void CFG::dump() const {
for (int i = basicBlocks.size() - 1; i >= 0; --i) {
...
}
}First, the number of the block is printed with a tag indicating if it's the entry or the exit block.
void CFG::dump(size_t) const {
for (int i = basicBlocks.size() - 1; i >= 0; --i) {
std::cerr << '[' << i;
if (i == entry)
std::cerr << " (entry)";
else if (i == exit)
std::cerr << " (exit)";
std::cerr << ']' << '\n';
...
}
}After the number of the block, its predecessors and successors are printed along with their reachability.
void CFG::dump(size_t) const {
for (int i = basicBlocks.size() - 1; i >= 0; --i) {
...
std::cerr << " preds: ";
for (auto &&[id, reachable] : basicBlocks[i].predecessors)
std::cerr << id << ((reachable) ? " " : "(U) ");
std::cerr << '\n';
std::cerr << " succs: ";
for (auto &&[id, reachable] : basicBlocks[i].successors)
std::cerr << id << ((reachable) ? " " : "(U) ");
std::cerr << '\n';
...
}
}Finally, because the statements have also been inserted from backwards, they are printed in a reverse order too.
void CFG::dump(size_t) const {
for (int i = basicBlocks.size() - 1; i >= 0; --i) {
...
const auto &statements = basicBlocks[i].statements;
for (auto it = statements.rbegin(); it != statements.rend(); ++it)
(*it)->dump(1);
std::cerr << '\n';
}
}
To let the users know that the CFG can be visualized, the
help message is extended with the
-cfg-dump flag.
void displayHelp() {
...
<< " -cfg-dump print the control flow graph\n";
}
The corresponding option is added to the
CompilerOptions structure too.
struct CompilerOptions {
...
bool cfgDump = false;
};The argument parser is also extended to be able to handle the newly introduced flag.
CompilerOptions parseArguments(int argc, const char **argv) {
...
while (idx < argc) {
...
else if (arg == "-cfg-dump")
options.cfgDump = true;
...
}
...
}The CFG can only be constructed for functions that have been resolved successfully, so the printing of the CFG happens in the driver after the semantic analyzer returns.
int main(int argc, const char **argv) {
...
if (options.cfgDump) {
for (auto &&fn : resolvedTree) {
std::cerr << fn->identifier << ':' << '\n';
CFGBuilder().build(*fn).dump();
}
return 0;
}
if (resolvedTree.empty())
...
}The first flow-sensitive analysis performed during semantic analysis is for checking if a function returns a value on every execution path.
std::vector<std::unique_ptr<ResolvedFunctionDecl>> Sema::resolveAST() {
...
for (size_t i = 1; i < resolvedTree.size(); ++i) {
...
currentFunction->body = std::move(resolvedBody);
error |= runFlowSensitiveChecks(*currentFunction);
}
...
}
The runFlowSensitiveChecks() helper first
builds the CFG of the function and hands it over to the
checkReturnOnAllPaths() method, which contains
the analysis logic.
bool Sema::runFlowSensitiveChecks(const ResolvedFunctionDecl &fn) {
CFG cfg = CFGBuilder().build(fn);
bool error = false;
error |= checkReturnOnAllPaths(fn, cfg);
return error;
};If the given function doesn't return a value, there is nothing to check, so the method can return immediately.
bool Sema::checkReturnOnAllPaths(const ResolvedFunctionDecl &fn,
const CFG &cfg) {
if (fn.type.kind == Type::Kind::Void)
return false;
...
}
The core of the function is a DFS traversal of the reachable
CFG blocks. Because basic blocks can loop back to each other
in the case of a WhileStmt, a set is created to
keep track of the already visited blocks.
bool Sema::checkReturnOnAllPaths(const ResolvedFunctionDecl &fn,
const CFG &cfg) {
...
std::set<int> visited;
...
}Then the worklist is created and the entry block is inserted into it.
bool Sema::checkReturnOnAllPaths(const ResolvedFunctionDecl &fn,
const CFG &cfg) {
...
std::vector<int> worklist;
worklist.emplace_back(cfg.entry);
...
}While the worklist is not empty, its last block is popped and if it hasn't been visited already, all of its reachable successors are added to the end of the worklist.
bool Sema::checkReturnOnAllPaths(const ResolvedFunctionDecl &fn,
const CFG &cfg) {
...
while (!worklist.empty()) {
int bb = worklist.back();
worklist.pop_back();
if (!visited.emplace(bb).second)
continue;
...
const auto &[preds, succs, stmts] = cfg.basicBlocks[bb];
for (auto &&[succ, reachable] : succs)
if (reachable)
worklist.emplace_back(succ);
}
...
}Because of the way the CFG is constructed, a return statement must be the first statement in the statement list of a block. To create more accurate error messages, the number of seen return statements is tracked.
bool Sema::checkReturnOnAllPaths(const ResolvedFunctionDecl &fn,
const CFG &cfg) {
...
int returnCount = 0;
while (!worklist.empty()) {
...
if (!stmts.empty() && dynamic_cast<const ResolvedReturnStmt *>(stmts[0])) {
++returnCount;
continue;
}
...
}
...
}If the block ends with a return statement, its successors are not visited. As a result, it's enough to keep track of whether the exit block is reached during the traversal. If any path to the exit block is not blocked by a return statement, a value is not returned on that path of execution.
bool Sema::checkReturnOnAllPaths(const ResolvedFunctionDecl &fn,
const CFG &cfg) {
...
bool exitReached = false;
while (!worklist.empty()) {
...
exitReached |= bb == cfg.exit;
...
}
...
}After the traversal, if the exit block is reachable, or there are no return statements at all, an error is reported.
If there are no return statements the function might be stuck in an infinite loop and doesn't return a value at all. If there is at least one return statement, the function only returns a value on some branches but not all of them.
bool Sema::checkReturnOnAllPaths(const ResolvedFunctionDecl &fn,
const CFG &cfg) {
...
if (exitReached || returnCount == 0) {
report(fn.location,
returnCount > 0
? "non-void function doesn't return a value on every path"
: "non-void function doesn't return a value");
}
...
}An indicator is also returned to the caller that shows if the check found any errors.
bool Sema::checkReturnOnAllPaths(const ResolvedFunctionDecl &fn,
const CFG &cfg) {
...
return exitReached || returnCount == 0;
}