Commit 633781e31d
Changed files (10)
src/all_types.hpp
@@ -28,6 +28,14 @@ struct BuiltinFnEntry;
struct TypeStructField;
struct CodeGen;
struct ConstExprValue;
+struct IrInstruction;
+struct IrBasicBlock;
+
+struct IrExecutable {
+ IrBasicBlock **basic_block_list;
+ size_t basic_block_count;
+ size_t next_debug_id;
+};
enum OutType {
OutTypeUnknown,
@@ -1105,6 +1113,7 @@ struct FnTableEntry {
AstNode *want_pure_return_type;
FnInline fn_inline;
FnAnalState anal_state;
+ IrExecutable ir_executable;
AstNode *fn_no_inline_set_node;
AstNode *fn_export_set_node;
@@ -1317,6 +1326,8 @@ struct CodeGen {
ZigList<AstNode *> error_decls;
bool generate_error_name_table;
LLVMValueRef err_name_table;
+
+ IrInstruction *invalid_instruction;
};
struct VariableTableEntry {
@@ -1388,5 +1399,145 @@ enum AtomicOrder {
AtomicOrderSeqCst,
};
+// A basic block contains no branching. Branches send control flow
+// to another basic block.
+// Phi instructions must be first in a basic block.
+// The last instruction in a basic block must be an expression of type unreachable.
+struct IrBasicBlock {
+ IrInstruction *first;
+ IrInstruction *last;
+};
+
+enum IrInstructionId {
+ IrInstructionIdInvalid,
+ IrInstructionIdCondBr,
+ IrInstructionIdSwitchBr,
+ IrInstructionIdPhi,
+ IrInstructionIdBinOp,
+ IrInstructionIdLoadVar,
+ IrInstructionIdStoreVar,
+ IrInstructionIdCall,
+ IrInstructionIdBuiltinCall,
+ IrInstructionIdConst,
+ IrInstructionIdReturn,
+};
+
+struct IrInstruction {
+ IrInstruction *prev;
+ IrInstruction *next;
+
+ IrInstructionId id;
+ AstNode *source_node;
+ ConstExprValue static_value;
+ TypeTableEntry *type_entry;
+ size_t debug_id;
+ LLVMValueRef llvm_value;
+};
+
+struct IrInstructionCondBr {
+ IrInstruction base;
+
+ // If the condition is null, then this is an unconditional branch.
+ IrInstruction *cond;
+ IrBasicBlock *dest;
+};
+
+struct IrInstructionSwitchBrCase {
+ IrInstruction *value;
+ IrBasicBlock *block;
+};
+
+struct IrInstructionSwitchBr {
+ IrInstruction base;
+
+ IrInstruction *target_value;
+ IrBasicBlock *else_block;
+ size_t case_count;
+ IrInstructionSwitchBrCase *cases;
+};
+
+struct IrInstructionPhi {
+ IrInstruction base;
+
+ size_t incoming_block_count;
+ IrBasicBlock **incoming_blocks;
+ IrInstruction **incoming_values;
+};
+
+enum IrBinOp {
+ IrBinOpInvalid,
+ IrBinOpBoolOr,
+ IrBinOpBoolAnd,
+ IrBinOpCmpEq,
+ IrBinOpCmpNotEq,
+ IrBinOpCmpLessThan,
+ IrBinOpCmpGreaterThan,
+ IrBinOpCmpLessOrEq,
+ IrBinOpCmpGreaterOrEq,
+ IrBinOpBinOr,
+ IrBinOpBinXor,
+ IrBinOpBinAnd,
+ IrBinOpBitShiftLeft,
+ IrBinOpBitShiftLeftWrap,
+ IrBinOpBitShiftRight,
+ IrBinOpAdd,
+ IrBinOpAddWrap,
+ IrBinOpSub,
+ IrBinOpSubWrap,
+ IrBinOpMult,
+ IrBinOpMultWrap,
+ IrBinOpDiv,
+ IrBinOpMod,
+ IrBinOpArrayCat,
+ IrBinOpArrayMult,
+};
+
+struct IrInstructionBinOp {
+ IrInstruction base;
+
+ IrInstruction *op1;
+ IrBinOp op_id;
+ IrInstruction *op2;
+};
+
+struct IrInstructionLoadVar {
+ IrInstruction base;
+
+ VariableTableEntry *var;
+};
+
+struct IrInstructionStoreVar {
+ IrInstruction base;
+
+ IrInstruction *value;
+ VariableTableEntry *var;
+};
+
+struct IrInstructionCall {
+ IrInstruction base;
+
+ IrInstruction *fn;
+ size_t arg_count;
+ IrInstruction **args;
+};
+
+struct IrInstructionBuiltinCall {
+ IrInstruction base;
+
+ BuiltinFnId fn_id;
+ size_t arg_count;
+ IrInstruction **args;
+};
+
+struct IrInstructionConst {
+ IrInstruction base;
+};
+
+struct IrInstructionReturn {
+ IrInstruction base;
+
+ IrInstruction *value;
+};
+
#endif
src/analyze.cpp
@@ -11,6 +11,7 @@
#include "error.hpp"
#include "eval.hpp"
#include "ir.hpp"
+#include "ir_print.hpp"
#include "os.hpp"
#include "parseh.hpp"
#include "parser.hpp"
@@ -54,7 +55,7 @@ static void analyze_fn_body(CodeGen *g, FnTableEntry *fn_table_entry);
static void resolve_use_decl(CodeGen *g, AstNode *node);
static void preview_use_decl(CodeGen *g, AstNode *node);
-static AstNode *first_executing_node(AstNode *node) {
+AstNode *first_executing_node(AstNode *node) {
switch (node->type) {
case NodeTypeFnCallExpr:
return first_executing_node(node->data.fn_call_expr.fn_ref_expr);
@@ -2381,18 +2382,6 @@ static VariableTableEntry *find_variable(CodeGen *g, BlockContext *orig_context,
return nullptr;
}
-static LabelTableEntry *find_label(CodeGen *g, BlockContext *orig_context, Buf *name) {
- BlockContext *context = orig_context;
- while (context && context->fn_entry) {
- auto entry = context->label_table.maybe_get(name);
- if (entry) {
- return entry->value;
- }
- context = context->parent;
- }
- return nullptr;
-}
-
static TypeEnumField *find_enum_type_field(TypeTableEntry *enum_type, Buf *name) {
for (uint32_t i = 0; i < enum_type->data.enumeration.src_field_count; i += 1) {
TypeEnumField *type_enum_field = &enum_type->data.enumeration.fields[i];
@@ -7098,14 +7087,19 @@ static void analyze_fn_body(CodeGen *g, FnTableEntry *fn_table_entry) {
buf_sprintf("byvalue types not yet supported on extern function return values"));
}
- IrBasicBlock *entry_basic_block = ir_gen(g, node, expected_type);
- if (!entry_basic_block) {
+ IrInstruction *result = ir_gen_fn(g, fn_table_entry);
+ if (result == g->invalid_instruction) {
fn_proto_node->data.fn_proto.skip = true;
fn_table_entry->anal_state = FnAnalStateSkipped;
return;
}
- TypeTableEntry *block_return_type = ir_analyze(g, node, entry_basic_block, expected_type);
+ if (g->verbose) {
+ fprintf(stderr, "fn %s {\n", buf_ptr(&fn_table_entry->symbol_name));
+ ir_print(stderr, &fn_table_entry->ir_executable, 4);
+ fprintf(stderr, "}\n");
+ }
+ TypeTableEntry *block_return_type = ir_analyze(g, &fn_table_entry->ir_executable, expected_type);
node->data.fn_def.implicit_return_type = block_return_type;
fn_table_entry->anal_state = FnAnalStateComplete;
src/analyze.hpp
@@ -43,4 +43,6 @@ uint64_t get_memcpy_align(CodeGen *g, TypeTableEntry *type_entry);
ImportTableEntry *add_source_file(CodeGen *g, PackageTableEntry *package,
Buf *abs_full_path, Buf *src_dirname, Buf *src_basename, Buf *source_code);
+AstNode *first_executing_node(AstNode *node);
+
#endif
src/codegen.cpp
@@ -5,18 +5,18 @@
* See http://opensource.org/licenses/MIT
*/
+#include "analyze.hpp"
+#include "ast_render.hpp"
#include "codegen.hpp"
-#include "hash_map.hpp"
-#include "zig_llvm.hpp"
-#include "os.hpp"
#include "config.h"
-#include "error.hpp"
-#include "analyze.hpp"
#include "errmsg.hpp"
+#include "error.hpp"
+#include "hash_map.hpp"
+#include "link.hpp"
+#include "os.hpp"
#include "parseh.hpp"
-#include "ast_render.hpp"
#include "target.hpp"
-#include "link.hpp"
+#include "zig_llvm.hpp"
#include <stdio.h>
#include <errno.h>
@@ -65,6 +65,8 @@ CodeGen *codegen_create(Buf *root_source_dir, const ZigTarget *target) {
g->is_test_build = false;
g->want_h_file = true;
+ g->invalid_instruction = allocate<IrInstruction>(1);
+
// the error.Ok value
g->error_decls.append(nullptr);
@@ -235,6 +237,7 @@ static LLVMValueRef gen_assign_raw(CodeGen *g, AstNode *source_node, BinOpType b
static LLVMValueRef gen_unwrap_maybe(CodeGen *g, AstNode *node, LLVMValueRef maybe_struct_ref);
static LLVMValueRef gen_div(CodeGen *g, AstNode *source_node, LLVMValueRef val1, LLVMValueRef val2,
TypeTableEntry *type_entry, bool exact);
+static LLVMValueRef gen_const_val(CodeGen *g, TypeTableEntry *type_entry, ConstExprValue *const_val);
static TypeTableEntry *get_type_for_type_node(AstNode *node) {
Expr *expr = get_resolved_expr(node);
@@ -249,6 +252,10 @@ static void set_debug_source_node(CodeGen *g, AstNode *node) {
ZigLLVMSetCurrentDebugLocation(g->builder, node->line + 1, node->column + 1, node->block_context->di_scope);
}
+static void ir_set_debug(CodeGen *g, IrInstruction *instruction) {
+ set_debug_source_node(g, instruction->source_node);
+}
+
static void clear_debug_source_node(CodeGen *g) {
ZigLLVMClearCurrentDebugLocation(g->builder);
}
@@ -2792,6 +2799,47 @@ static LLVMValueRef gen_if_var_expr(CodeGen *g, AstNode *node) {
return nullptr;
}
+static LLVMValueRef ir_render_return(CodeGen *g, IrExecutable *executable, IrInstructionReturn *return_instruction) {
+ ir_set_debug(g, &return_instruction->base);
+ LLVMBuildRet(g->builder, return_instruction->value->llvm_value);
+ return nullptr;
+}
+
+static LLVMValueRef ir_render_instruction(CodeGen *g, IrExecutable *executable, IrInstruction *instruction) {
+ switch (instruction->id) {
+ case IrInstructionIdInvalid:
+ zig_unreachable();
+ case IrInstructionIdConst:
+ return gen_const_val(g, instruction->type_entry, &instruction->static_value);
+ case IrInstructionIdReturn:
+ return ir_render_return(g, executable, (IrInstructionReturn *)instruction);
+ case IrInstructionIdCondBr:
+ case IrInstructionIdSwitchBr:
+ case IrInstructionIdPhi:
+ case IrInstructionIdBinOp:
+ case IrInstructionIdLoadVar:
+ case IrInstructionIdStoreVar:
+ case IrInstructionIdCall:
+ case IrInstructionIdBuiltinCall:
+ zig_panic("TODO render more IR instructions to LLVM");
+ }
+ zig_unreachable();
+}
+
+static void ir_render(CodeGen *g, FnTableEntry *fn_entry) {
+ assert(fn_entry);
+ IrExecutable *executable = &fn_entry->ir_executable;
+ assert(executable->basic_block_count > 0);
+ for (size_t i = 0; i < executable->basic_block_count; i += 1) {
+ IrBasicBlock *current_block = executable->basic_block_list[i];
+ for (IrInstruction *instruction = current_block->first; instruction != nullptr;
+ instruction = instruction->next)
+ {
+ instruction->llvm_value = ir_render_instruction(g, executable, instruction);
+ }
+ }
+}
+
static LLVMValueRef gen_block(CodeGen *g, AstNode *block_node, TypeTableEntry *implicit_return_type) {
assert(block_node->type == NodeTypeBlock);
@@ -3836,6 +3884,8 @@ static LLVMValueRef gen_const_val(CodeGen *g, TypeTableEntry *type_entry, ConstE
return LLVMConstStruct(fields, 2, false);
}
}
+ case TypeTableEntryIdVoid:
+ return nullptr;
case TypeTableEntryIdInvalid:
case TypeTableEntryIdMetaType:
case TypeTableEntryIdUnreachable:
@@ -3843,7 +3893,6 @@ static LLVMValueRef gen_const_val(CodeGen *g, TypeTableEntry *type_entry, ConstE
case TypeTableEntryIdNumLitInt:
case TypeTableEntryIdUndefLit:
case TypeTableEntryIdNullLit:
- case TypeTableEntryIdVoid:
case TypeTableEntryIdNamespace:
case TypeTableEntryIdBlock:
case TypeTableEntryIdGenericFn:
@@ -4199,7 +4248,6 @@ static void do_code_gen(CodeGen *g) {
}
ImportTableEntry *import = fn_table_entry->import_entry;
- AstNode *fn_def_node = fn_table_entry->fn_def_node;
LLVMValueRef fn = fn_table_entry->fn_value;
g->cur_fn = fn_table_entry;
if (handle_is_ptr(fn_table_entry->type_entry->data.fn.fn_type_id.return_type)) {
@@ -4307,9 +4355,7 @@ static void do_code_gen(CodeGen *g) {
gen_var_debug_decl(g, variable);
}
-
- TypeTableEntry *implicit_return_type = fn_def_node->data.fn_def.implicit_return_type;
- gen_block(g, fn_def_node->data.fn_def.body, implicit_return_type);
+ ir_render(g, fn_table_entry);
}
assert(!g->errors.length);
@@ -4967,7 +5013,6 @@ static void init(CodeGen *g, Buf *source_path) {
define_builtin_types(g);
define_builtin_fns(g);
-
}
void codegen_parseh(CodeGen *g, Buf *src_dirname, Buf *src_basename, Buf *source_code) {
@@ -5078,6 +5123,7 @@ void codegen_add_root_code(CodeGen *g, Buf *src_dir, Buf *src_basename, Buf *sou
if (g->verbose) {
fprintf(stderr, "\nCode Generation:\n");
fprintf(stderr, "------------------\n");
+
}
do_code_gen(g);
src/ir.cpp
@@ -1,44 +1,117 @@
#include "analyze.hpp"
#include "ir.hpp"
-
-static IrInstruction *ir_gen_node(IrGen *ir, AstNode *node, BlockContext *block_context);
-
-static const IrInstruction invalid_instruction_data;
-static const IrInstruction *invalid_instruction = &invalid_instruction_data;
-
-static const IrInstruction void_instruction_data;
-static const IrInstruction *void_instruction = &void_instruction_data;
+#include "error.hpp"
struct IrGen {
CodeGen *codegen;
- AstNode *fn_def_node;
+ AstNode *node;
IrBasicBlock *current_basic_block;
+ IrExecutable *exec;
};
-static IrInstruction *ir_build_return(Ir *ir, AstNode *source_node, IrInstruction *return_value) {
- IrInstruction *instructon = allocate<IrInstructionReturn>(1);
- instruction->base.id = IrInstructionIdReturn;
- instruction->base.source_node = source_node;
- instruction->base.type_entry = ir->codegen->builtin_types.entry_unreachable;
- ir->current_basic_block->instructions->append(instruction);
- return instructon;
-}
+static IrInstruction *ir_gen_node(IrGen *ir, AstNode *node, BlockContext *block_context);
-static size_t get_conditional_defer_count(BlockContext *inner_block, BlockContext *outer_block) {
- size_t result = 0;
- while (inner_block != outer_block) {
- if (inner_block->node->type == NodeTypeDefer &&
- (inner_block->node->data.defer.kind == ReturnKindError ||
- inner_block->node->data.defer.kind == ReturnKindMaybe))
- {
- result += 1;
- }
- inner_block = inner_block->parent;
+static void ir_instruction_append(IrBasicBlock *basic_block, IrInstruction *instruction) {
+ if (!basic_block->last) {
+ basic_block->first = instruction;
+ basic_block->last = instruction;
+ instruction->prev = nullptr;
+ instruction->next = nullptr;
+ } else {
+ basic_block->last->next = instruction;
+ instruction->prev = basic_block->last;
+ instruction->next = nullptr;
+ basic_block->last = instruction;
}
+}
+
+static size_t exec_next_debug_id(IrGen *ir) {
+ size_t result = ir->exec->next_debug_id;
+ ir->exec->next_debug_id += 1;
return result;
}
-static void ir_gen_defers_for_block(Ir *ir, BlockContext *inner_block, BlockContext *outer_block,
+static constexpr IrInstructionId ir_instruction_id(IrInstructionCondBr *) {
+ return IrInstructionIdCondBr;
+}
+
+static constexpr IrInstructionId ir_instruction_id(IrInstructionSwitchBr *) {
+ return IrInstructionIdSwitchBr;
+}
+
+static constexpr IrInstructionId ir_instruction_id(IrInstructionPhi *) {
+ return IrInstructionIdPhi;
+}
+
+static constexpr IrInstructionId ir_instruction_id(IrInstructionBinOp *) {
+ return IrInstructionIdBinOp;
+}
+
+static constexpr IrInstructionId ir_instruction_id(IrInstructionLoadVar *) {
+ return IrInstructionIdLoadVar;
+}
+
+static constexpr IrInstructionId ir_instruction_id(IrInstructionStoreVar *) {
+ return IrInstructionIdStoreVar;
+}
+
+static constexpr IrInstructionId ir_instruction_id(IrInstructionCall *) {
+ return IrInstructionIdCall;
+}
+
+static constexpr IrInstructionId ir_instruction_id(IrInstructionBuiltinCall *) {
+ return IrInstructionIdBuiltinCall;
+}
+
+static constexpr IrInstructionId ir_instruction_id(IrInstructionConst *) {
+ return IrInstructionIdConst;
+}
+
+static constexpr IrInstructionId ir_instruction_id(IrInstructionReturn *) {
+ return IrInstructionIdReturn;
+}
+
+template<typename T>
+static T *ir_build_instruction(IrGen *ir, AstNode *source_node) {
+ T *special_instruction = allocate<T>(1);
+ special_instruction->base.id = ir_instruction_id(special_instruction);
+ special_instruction->base.source_node = source_node;
+ special_instruction->base.type_entry = ir->codegen->builtin_types.entry_unreachable;
+ special_instruction->base.debug_id = exec_next_debug_id(ir);
+ ir_instruction_append(ir->current_basic_block, &special_instruction->base);
+ return special_instruction;
+}
+
+static IrInstruction *ir_build_return(IrGen *ir, AstNode *source_node, IrInstruction *return_value) {
+ IrInstructionReturn *return_instruction = ir_build_instruction<IrInstructionReturn>(ir, source_node);
+ return_instruction->base.type_entry = ir->codegen->builtin_types.entry_unreachable;
+ return_instruction->base.static_value.ok = true;
+ return_instruction->value = return_value;
+ return &return_instruction->base;
+}
+
+static IrInstruction *ir_build_void(IrGen *ir, AstNode *source_node) {
+ IrInstructionConst *const_instruction = ir_build_instruction<IrInstructionConst>(ir, source_node);
+ const_instruction->base.type_entry = ir->codegen->builtin_types.entry_void;
+ const_instruction->base.static_value.ok = true;
+ return &const_instruction->base;
+}
+
+//static size_t get_conditional_defer_count(BlockContext *inner_block, BlockContext *outer_block) {
+// size_t result = 0;
+// while (inner_block != outer_block) {
+// if (inner_block->node->type == NodeTypeDefer &&
+// (inner_block->node->data.defer.kind == ReturnKindError ||
+// inner_block->node->data.defer.kind == ReturnKindMaybe))
+// {
+// result += 1;
+// }
+// inner_block = inner_block->parent;
+// }
+// return result;
+//}
+
+static void ir_gen_defers_for_block(IrGen *ir, BlockContext *inner_block, BlockContext *outer_block,
bool gen_error_defers, bool gen_maybe_defers)
{
while (inner_block != outer_block) {
@@ -54,42 +127,44 @@ static void ir_gen_defers_for_block(Ir *ir, BlockContext *inner_block, BlockCont
}
}
-static IrInstruction *ir_gen_return(Ir *ir, AstNode *source_node, IrInstruction *value, ReturnKnowledge rk) {
- BlockContext *defer_inner_block = source_node->block_context;
- BlockContext *defer_outer_block = ir->fn_def_node->block_context;
- if (rk == ReturnKnowledgeUnknown) {
- if (get_conditional_defer_count(defer_inner_block, defer_outer_block) > 0) {
- // generate branching code that checks the return value and generates defers
- // if the return value is error
- zig_panic("TODO");
- }
- } else if (rk != ReturnKnowledgeSkipDefers) {
- ir_gen_defers_for_block(g, defer_inner_block, defer_outer_block,
- rk == ReturnKnowledgeKnownError, rk == ReturnKnowledgeKnownNull);
- }
-
- ir_build_return(ir, source_node, value);
- return void_instruction;
-}
+//static IrInstruction *ir_gen_return(IrGen *ir, AstNode *source_node, IrInstruction *value, ReturnKnowledge rk) {
+// BlockContext *defer_inner_block = source_node->block_context;
+// BlockContext *defer_outer_block = ir->node->block_context;
+// if (rk == ReturnKnowledgeUnknown) {
+// if (get_conditional_defer_count(defer_inner_block, defer_outer_block) > 0) {
+// // generate branching code that checks the return value and generates defers
+// // if the return value is error
+// zig_panic("TODO");
+// }
+// } else if (rk != ReturnKnowledgeSkipDefers) {
+// ir_gen_defers_for_block(ir, defer_inner_block, defer_outer_block,
+// rk == ReturnKnowledgeKnownError, rk == ReturnKnowledgeKnownNull);
+// }
+//
+// return ir_build_return(ir, source_node, value);
+//}
-static IrInstruction *ir_gen_block(IrGen *ir, AstNode *block_node, TypeTableEntry *implicit_return_type) {
+static IrInstruction *ir_gen_block(IrGen *ir, AstNode *block_node) {
assert(block_node->type == NodeTypeBlock);
- BlockContext *parent_context = block_node->context;
+ BlockContext *parent_context = block_node->block_context;
BlockContext *outer_block_context = new_block_context(block_node, parent_context);
BlockContext *child_context = outer_block_context;
IrInstruction *return_value = nullptr;
for (size_t i = 0; i < block_node->data.block.statements.length; i += 1) {
AstNode *statement_node = block_node->data.block.statements.at(i);
- return_value = ir_gen_node(g, statement_node, child_context);
- if (statement_node->type == NodeTypeDefer && return_value != invalid_instruction) {
+ return_value = ir_gen_node(ir, statement_node, child_context);
+ if (statement_node->type == NodeTypeDefer && return_value != ir->codegen->invalid_instruction) {
// defer starts a new block context
child_context = statement_node->data.defer.child_block;
assert(child_context);
}
}
+ if (!return_value)
+ return_value = ir_build_void(ir, block_node);
+
ir_gen_defers_for_block(ir, child_context, outer_block_context, false, false);
return return_value;
@@ -100,7 +175,7 @@ static IrInstruction *ir_gen_node(IrGen *ir, AstNode *node, BlockContext *block_
switch (node->type) {
case NodeTypeBlock:
- return ir_gen_block(ir, node, nullptr);
+ return ir_gen_block(ir, node);
case NodeTypeBinOpExpr:
case NodeTypeUnwrapErrorExpr:
case NodeTypeReturnExpr:
@@ -153,23 +228,53 @@ static IrInstruction *ir_gen_node(IrGen *ir, AstNode *node, BlockContext *block_
zig_unreachable();
}
-IrBasicBlock *ir_gen(CodeGen *g, AstNode *fn_def_node, TypeTableEntry *return_type) {
- assert(fn_def_node->type == NodeTypeFnDef);
- assert(fn_def_node->data.fn_def.block_context);
- assert(fn_def_node->owner);
- assert(return_type);
- assert(return_type->id != TypeTableEntryIdInvalid);
+static IrInstruction *ir_gen_add_return(CodeGen *g, AstNode *node, BlockContext *scope,
+ IrExecutable *ir_executable, bool add_return)
+{
+ assert(node->owner);
IrGen ir_gen = {0};
IrGen *ir = &ir_gen;
+ ir->codegen = g;
+ ir->node = node;
+ ir->exec = ir_executable;
+
+ ir->exec->basic_block_list = allocate<IrBasicBlock*>(1);
+ ir->exec->basic_block_count = 1;
+
IrBasicBlock *entry_basic_block = allocate<IrBasicBlock>(1);
ir->current_basic_block = entry_basic_block;
+ ir->exec->basic_block_list[0] = entry_basic_block;
+
+ IrInstruction *result = ir_gen_node(ir, node, scope);
+ assert(result);
+
+ if (result == g->invalid_instruction)
+ return result;
+
+ if (add_return)
+ return ir_build_return(ir, result->source_node, result);
+
+ return result;
+}
+
+IrInstruction *ir_gen(CodeGen *g, AstNode *node, BlockContext *scope, IrExecutable *ir_executable) {
+ return ir_gen_add_return(g, node, scope, ir_executable, false);
+}
+
+IrInstruction *ir_gen_fn(CodeGen *g, FnTableEntry *fn_entry) {
+ assert(fn_entry);
+
+ IrExecutable *ir_executable = &fn_entry->ir_executable;
+ AstNode *fn_def_node = fn_entry->fn_def_node;
+ assert(fn_def_node->type == NodeTypeFnDef);
AstNode *body_node = fn_def_node->data.fn_def.body;
- body_node->block_context = fn_def_node->data.fn_def.block_context;
- IrInstruction *instruction = ir_gen_block(ir, body_node, return_type);
- return (instructon == invalid_instruction) ? nullptr : entry_basic_block;
+ BlockContext *scope = fn_def_node->data.fn_def.block_context;
+
+ bool add_return_yes = true;
+ return ir_gen_add_return(g, body_node, scope, ir_executable, add_return_yes);
}
/*
@@ -205,22 +310,110 @@ static void analyze_goto_pass2(CodeGen *g, ImportTableEntry *import, AstNode *no
}
*/
+//static LabelTableEntry *find_label(CodeGen *g, BlockContext *orig_context, Buf *name) {
+// BlockContext *context = orig_context;
+// while (context && context->fn_entry) {
+// auto entry = context->label_table.maybe_get(name);
+// if (entry) {
+// return entry->value;
+// }
+// context = context->parent;
+// }
+// return nullptr;
+//}
+
+static IrInstruction *ir_get_casted_instruction(CodeGen *g, IrInstruction *instruction,
+ TypeTableEntry *expected_type)
+{
+ assert(instruction);
+ assert(instruction != g->invalid_instruction);
+ assert(!expected_type || expected_type->id != TypeTableEntryIdInvalid);
+ assert(instruction->type_entry);
+ assert(instruction->type_entry->id != TypeTableEntryIdInvalid);
+ if (expected_type == nullptr)
+ return instruction; // anything will do
+ if (expected_type == instruction->type_entry)
+ return instruction; // match
+ if (instruction->type_entry->id == TypeTableEntryIdUnreachable)
+ return instruction;
+
+ zig_panic("TODO implicit cast instruction");
+}
+
+static TypeTableEntry *ir_analyze_instruction_return(CodeGen *g, IrInstructionReturn *return_instruction) {
+ AstNode *source_node = return_instruction->base.source_node;
+ BlockContext *scope = source_node->block_context;
+ if (!scope->fn_entry) {
+ add_node_error(g, source_node, buf_sprintf("return expression outside function definition"));
+ return g->builtin_types.entry_invalid;
+ }
-TypeTableEntry *ir_analyze(CodeGen *g, AstNode *fn_def_node, IrBasicBlock *entry_basic_block,
+ TypeTableEntry *expected_return_type = scope->fn_entry->type_entry->data.fn.fn_type_id.return_type;
+ if (expected_return_type->id == TypeTableEntryIdVoid && !return_instruction->value) {
+ return g->builtin_types.entry_unreachable;
+ }
+
+ return_instruction->value = ir_get_casted_instruction(g, return_instruction->value, expected_return_type);
+ if (return_instruction->value == g->invalid_instruction) {
+ return g->builtin_types.entry_invalid;
+ }
+ return g->builtin_types.entry_unreachable;
+}
+
+static TypeTableEntry *ir_analyze_instruction_const(CodeGen *g, IrInstructionConst *const_instruction) {
+ return const_instruction->base.type_entry;
+}
+
+static TypeTableEntry *ir_analyze_instruction_nocast(CodeGen *g, IrInstruction *instruction) {
+ switch (instruction->id) {
+ case IrInstructionIdInvalid:
+ zig_unreachable();
+ case IrInstructionIdReturn:
+ return ir_analyze_instruction_return(g, (IrInstructionReturn *)instruction);
+ case IrInstructionIdConst:
+ return ir_analyze_instruction_const(g, (IrInstructionConst *)instruction);
+ case IrInstructionIdCondBr:
+ case IrInstructionIdSwitchBr:
+ case IrInstructionIdPhi:
+ case IrInstructionIdBinOp:
+ case IrInstructionIdLoadVar:
+ case IrInstructionIdStoreVar:
+ case IrInstructionIdCall:
+ case IrInstructionIdBuiltinCall:
+ zig_panic("TODO analyze more instructions");
+ }
+ zig_unreachable();
+}
+
+static TypeTableEntry *ir_analyze_instruction(CodeGen *g, IrInstruction *instruction,
TypeTableEntry *expected_type)
{
+ TypeTableEntry *instruction_type = ir_analyze_instruction_nocast(g, instruction);
+ instruction->type_entry = instruction_type;
+
+ IrInstruction *casted_instruction = ir_get_casted_instruction(g, instruction, expected_type);
+ return casted_instruction->type_entry;
+}
+
+TypeTableEntry *ir_analyze(CodeGen *g, IrExecutable *executable, TypeTableEntry *expected_type) {
TypeTableEntry *return_type = g->builtin_types.entry_void;
- for (size_t i = 0; i < entry_basic_block->instructions.length; i += 1) {
- IrInstruction *instruction = entry_basic_block->instructions.at(i);
+ for (size_t i = 0; i < executable->basic_block_count; i += 1) {
+ IrBasicBlock *current_block = executable->basic_block_list[i];
- if (return_type->id == TypeTableEntryIdUnreachable) {
- add_node_error(g, first_executing_node(instruction->source_node),
- buf_sprintf("unreachable code"));
- break;
+ for (IrInstruction *instruction = current_block->first; instruction != nullptr;
+ instruction = instruction->next)
+ {
+ if (return_type->id == TypeTableEntryIdUnreachable) {
+ add_node_error(g, first_executing_node(instruction->source_node),
+ buf_sprintf("unreachable code"));
+ break;
+ }
+ bool is_last = (instruction == current_block->last);
+ TypeTableEntry *passed_expected_type = is_last ? expected_type : nullptr;
+ return_type = ir_analyze_instruction(g, instruction, passed_expected_type);
}
- bool is_last = (i == entry_basic_block->instructions.length - 1);
- TypeTableEntry *passed_expected_type = is_last ? expected_type : nullptr;
- return_type = ir_analyze_instruction(g, instruction, passed_expected_type, child);
}
+
+ return return_type;
}
src/ir.hpp
@@ -10,144 +10,9 @@
#include "all_types.hpp"
-struct IrInstruction;
+IrInstruction *ir_gen(CodeGen *g, AstNode *node, BlockContext *scope, IrExecutable *ir_executable);
+IrInstruction *ir_gen_fn(CodeGen *g, FnTableEntry *fn_entry);
-// A basic block contains no branching. Branches send control flow
-// to another basic block.
-// Phi instructions must be first in a basic block.
-// The last instruction in a basic block must be an expression of type unreachable.
-struct IrBasicBlock {
- ZigList<IrInstruction *> instructions;
-};
-
-enum IrInstructionId {
- IrInstructionIdCondBr,
- IrInstructionIdSwitchBr,
- IrInstructionIdPhi,
- IrInstructionIdAdd,
- IrInstructionIdBinOp,
- IrInstructionIdLoadVar,
- IrInstructionIdStoreVar,
- IrInstructionIdCall,
- IrInstructionIdBuiltinCall,
- IrInstructionIdConst,
- IrInstructionIdReturn,
-};
-
-struct IrInstruction {
- IrInstructionId id;
- AstNode *source_node;
- ConstExprValue static_value;
- TypeTableEntry *type_entry;
-};
-
-struct IrInstructionCondBr {
- IrInstruction base;
-
- // If the condition is null, then this is an unconditional branch.
- IrInstruction *cond;
- IrBasicBlock *dest;
-};
-
-struct IrInstructionSwitchBrCase {
- IrInstruction *value;
- IrBasicBlock *block;
-};
-
-struct IrInstructionSwitchBr {
- IrInstruction base;
-
- IrInstruction *target_value;
- IrBasicBlock *else_block;
- size_t case_count;
- IrInstructionSwitchBrCase *cases;
-};
-
-struct IrInstructionPhi {
- IrInstruction base;
-
- size_t incoming_block_count;
- IrBasicBlock **incoming_blocks;
- IrInstruction **incoming_values;
-};
-
-enum IrBinOp {
- IrBinOpInvalid,
- IrBinOpBoolOr,
- IrBinOpBoolAnd,
- IrBinOpCmpEq,
- IrBinOpCmpNotEq,
- IrBinOpCmpLessThan,
- IrBinOpCmpGreaterThan,
- IrBinOpCmpLessOrEq,
- IrBinOpCmpGreaterOrEq,
- IrBinOpBinOr,
- IrBinOpBinXor,
- IrBinOpBinAnd,
- IrBinOpBitShiftLeft,
- IrBinOpBitShiftLeftWrap,
- IrBinOpBitShiftRight,
- IrBinOpAdd,
- IrBinOpAddWrap,
- IrBinOpSub,
- IrBinOpSubWrap,
- IrBinOpMult,
- IrBinOpMultWrap,
- IrBinOpDiv,
- IrBinOpMod,
- IrBinOpArrayCat,
- IrBinOpArrayMult,
-};
-
-struct IrInstructionBinOp {
- IrInstruction base;
-
- IrInstruction *op1;
- IrBinOp op_id;
- IrInstruction *op2;
-};
-
-struct IrInstructionLoadVar {
- IrInstruction base;
-
- VariableTableEntry *var;
-};
-
-struct IrInstructionStoreVar {
- IrInstruction base;
-
- IrInstruction *value;
- VariableTableEntry *var;
-};
-
-struct IrInstructionCall {
- IrInstruction base;
-
- IrInstruction *fn;
- size_t arg_count;
- IrInstruction **args;
-};
-
-struct IrInstructionBuiltinCall {
- IrInstruction base;
-
- BuiltinFnId fn_id;
- size_t arg_count;
- IrInstruction **args;
-};
-
-struct IrInstructionConst {
- IrInstruction base;
-};
-
-struct IrInstructionReturn {
- IrInstruction base;
-
- IrInstruction *value;
-};
-
-IrBasicBlock *ir_gen(CodeGen *g, AstNode *fn_def_node, TypeTableEntry *return_type);
-TypeTableEntry *ir_analyze(CodeGen *g, AstNode *fn_def_node, IrBasicBlock *entry_basic_block,
- TypeTableEntry *expected_type);
+TypeTableEntry *ir_analyze(CodeGen *g, IrExecutable *executable, TypeTableEntry *expected_type);
#endif
src/ir_print.cpp
@@ -0,0 +1,94 @@
+#include "ir_print.hpp"
+
+struct IrPrint {
+ FILE *f;
+ int indent;
+ int indent_size;
+};
+
+static void ir_print_indent(IrPrint *irp) {
+ for (int i = 0; i < irp->indent; i += 1) {
+ fprintf(irp->f, " ");
+ }
+}
+
+static void ir_print_prefix(IrPrint *irp, IrInstruction *instruction) {
+ ir_print_indent(irp);
+ fprintf(irp->f, "#%-3zu| ", instruction->debug_id);
+}
+
+static void ir_print_return(IrPrint *irp, IrInstructionReturn *return_instruction) {
+ ir_print_prefix(irp, &return_instruction->base);
+ assert(return_instruction->value);
+ fprintf(irp->f, "return #%zu;\n", return_instruction->value->debug_id);
+}
+
+static void ir_print_const(IrPrint *irp, IrInstructionConst *const_instruction) {
+ ir_print_prefix(irp, &const_instruction->base);
+ switch (const_instruction->base.type_entry->id) {
+ case TypeTableEntryIdInvalid:
+ zig_unreachable();
+ case TypeTableEntryIdVoid:
+ fprintf(irp->f, "void\n");
+ break;
+ case TypeTableEntryIdVar:
+ case TypeTableEntryIdMetaType:
+ case TypeTableEntryIdBool:
+ case TypeTableEntryIdUnreachable:
+ case TypeTableEntryIdInt:
+ case TypeTableEntryIdFloat:
+ case TypeTableEntryIdPointer:
+ case TypeTableEntryIdArray:
+ case TypeTableEntryIdStruct:
+ case TypeTableEntryIdNumLitFloat:
+ case TypeTableEntryIdNumLitInt:
+ case TypeTableEntryIdUndefLit:
+ case TypeTableEntryIdNullLit:
+ case TypeTableEntryIdMaybe:
+ case TypeTableEntryIdErrorUnion:
+ case TypeTableEntryIdPureError:
+ case TypeTableEntryIdEnum:
+ case TypeTableEntryIdUnion:
+ case TypeTableEntryIdFn:
+ case TypeTableEntryIdTypeDecl:
+ case TypeTableEntryIdNamespace:
+ case TypeTableEntryIdBlock:
+ case TypeTableEntryIdGenericFn:
+ zig_panic("TODO render more constant types in IR printer");
+ }
+}
+
+void ir_print(FILE *f, IrExecutable *executable, int indent_size) {
+ IrPrint ir_print = {};
+ IrPrint *irp = &ir_print;
+ irp->f = f;
+ irp->indent = indent_size;
+ irp->indent_size = indent_size;
+
+ for (size_t i = 0; i < executable->basic_block_count; i += 1) {
+ IrBasicBlock *current_block = executable->basic_block_list[i];
+ for (IrInstruction *instruction = current_block->first; instruction != nullptr;
+ instruction = instruction->next)
+ {
+ switch (instruction->id) {
+ case IrInstructionIdInvalid:
+ zig_unreachable();
+ case IrInstructionIdReturn:
+ ir_print_return(irp, (IrInstructionReturn *)instruction);
+ break;
+ case IrInstructionIdConst:
+ ir_print_const(irp, (IrInstructionConst *)instruction);
+ break;
+ case IrInstructionIdCondBr:
+ case IrInstructionIdSwitchBr:
+ case IrInstructionIdPhi:
+ case IrInstructionIdBinOp:
+ case IrInstructionIdLoadVar:
+ case IrInstructionIdStoreVar:
+ case IrInstructionIdCall:
+ case IrInstructionIdBuiltinCall:
+ zig_panic("TODO print more IR instructions");
+ }
+ }
+ }
+}
src/ir_print.hpp
@@ -0,0 +1,17 @@
+/*
+ * Copyright (c) 2016 Andrew Kelley
+ *
+ * This file is part of zig, which is MIT licensed.
+ * See http://opensource.org/licenses/MIT
+ */
+
+#ifndef ZIG_IR_PRINT_HPP
+#define ZIG_IR_PRINT_HPP
+
+#include "all_types.hpp"
+
+#include <stdio.h>
+
+void ir_print(FILE *f, IrExecutable *executable, int indent_size);
+
+#endif
src/parser.cpp
@@ -1912,14 +1912,14 @@ static AstNode *ast_parse_label(ParseContext *pc, size_t *token_index, bool mand
return node;
}
-static AstNode *ast_create_void_expr(ParseContext *pc, Token *token) {
- AstNode *node = ast_create_node(pc, NodeTypeContainerInitExpr, token);
- node->data.container_init_expr.type = ast_create_node(pc, NodeTypeSymbol, token);
- node->data.container_init_expr.kind = ContainerInitKindArray;
- node->data.container_init_expr.type->data.symbol_expr.symbol = pc->void_buf;
- normalize_parent_ptrs(node);
- return node;
-}
+//static AstNode *ast_create_void_expr(ParseContext *pc, Token *token) {
+// AstNode *node = ast_create_node(pc, NodeTypeContainerInitExpr, token);
+// node->data.container_init_expr.type = ast_create_node(pc, NodeTypeSymbol, token);
+// node->data.container_init_expr.kind = ContainerInitKindArray;
+// node->data.container_init_expr.type->data.symbol_expr.symbol = pc->void_buf;
+// normalize_parent_ptrs(node);
+// return node;
+//}
/*
Block : token(LBrace) list(option(Statement), token(Semicolon)) token(RBrace)
@@ -1961,13 +1961,12 @@ static AstNode *ast_parse_block(ParseContext *pc, size_t *token_index, bool mand
semicolon_expected = !statement_node;
if (!statement_node) {
statement_node = ast_parse_non_block_expr(pc, token_index, false);
- if (!statement_node) {
- statement_node = ast_create_void_expr(pc, last_token);
- }
}
}
}
- node->data.block.statements.append(statement_node);
+ if (statement_node) {
+ node->data.block.statements.append(statement_node);
+ }
last_token = &pc->tokens->at(*token_index);
if (last_token->id == TokenIdRBrace) {
CMakeLists.txt
@@ -48,6 +48,7 @@ set(ZIG_SOURCES
"${CMAKE_SOURCE_DIR}/src/error.cpp"
"${CMAKE_SOURCE_DIR}/src/eval.cpp"
"${CMAKE_SOURCE_DIR}/src/ir.cpp"
+ "${CMAKE_SOURCE_DIR}/src/ir_print.cpp"
"${CMAKE_SOURCE_DIR}/src/link.cpp"
"${CMAKE_SOURCE_DIR}/src/main.cpp"
"${CMAKE_SOURCE_DIR}/src/os.cpp"