mie: scf: implement lots of print and emit functions

mie/ctx.c

@@ -70,6 +70,27 @@ struct mie_ctx *mie_ctx_create(void)
 	return out;
 }
 
+struct mie_op *mie_ctx_create_op(
+	const struct mie_ctx *ctx, const char *dialect, const char *op)
+{
+	const struct mie_op_definition *def
+		= mie_ctx_get_op_definition(ctx, dialect, op);
+	if (!def) {
+		return NULL;
+	}
+
+	struct mie_op *out = mie_op_create();
+	if (!out) {
+		return NULL;
+	}
+
+	out->op_flags |= MIE_OP_F_OP_RESOLVED;
+	out->op_info = def;
+	out->op_dialect = def->op_parent;
+
+	return out;
+}
+
 bool mie_ctx_resolve_op(const struct mie_ctx *ctx, struct mie_op *op)
 {
 	if (op->op_flags & MIE_OP_F_OP_RESOLVED) {

mie/dialect/arith/op/addi.c

@@ -1,8 +1,12 @@
+#include <mie/ctx.h>
+#include <mie/dialect/builtin.h>
 #include <mie/dialect/dialect.h>
+#include <mie/ir/builder.h>
 #include <mie/ir/op-definition.h>
 #include <mie/ir/op.h>
 #include <mie/macros.h>
 #include <mie/print/printer.h>
+#include <mie/type/type.h>
 
 static enum mie_status print(struct mie_printer *printer, const struct mie_op *op)
 {
@@ -28,6 +32,24 @@ static enum mie_status parse(struct mie_parser *parser, struct mie_op *out)
 	return MIE_SUCCESS;
 }
 
+struct mie_register *mie_arith_put_addi(
+	struct mie_builder *builder, struct mie_register *left,
+	struct mie_register *right, const char *name)
+{
+	struct mie_register *args[] = {left, right};
+	const size_t nr_args = sizeof args / sizeof args[0];
+
+	struct mie_op *op
+		= mie_builder_put_op(builder, "arith", "addi", args, nr_args);
+	const struct mie_type *ty = left->reg_type;
+
+	struct mie_register *result = mie_op_add_result(op, ty);
+	result->reg_block = mie_builder_get_current_block(builder);
+	mie_builder_put_name(builder, &result->reg_name, name);
+
+	return result;
+}
+
 MIE_OP_DEFINITION_BEGIN(mie_arith_addi, "addi")
 	MIE_OP_DEFINITION_PRINT(print);
 	MIE_OP_DEFINITION_PARSE(parse);

mie/dialect/arith/op/constant.c

@@ -1,6 +1,7 @@
 #include <mie/attribute/attribute.h>
 #include <mie/dialect/builtin.h>
 #include <mie/dialect/dialect.h>
+#include <mie/ir/builder.h>
 #include <mie/ir/op-definition.h>
 #include <mie/ir/op.h>
 #include <mie/macros.h>
@@ -40,6 +41,44 @@ static enum mie_status parse(struct mie_parser *parser, struct mie_op *out)
 	return MIE_SUCCESS;
 }
 
+struct mie_register *mie_arith_put_constant_i(
+	struct mie_builder *builder, long long value, const char *name)
+{
+	struct mie_op *op
+		= mie_builder_put_op(builder, "arith", "constant", NULL, 0);
+	const struct mie_type *ty
+		= mie_ctx_get_int_type(mie_builder_get_ctx(builder), 32);
+	struct mie_register *result = mie_op_add_result(op, ty);
+
+	result->reg_block = mie_builder_get_current_block(builder);
+	mie_builder_put_name(builder, &result->reg_name, name);
+
+	struct mie_attribute *val
+		= mie_ctx_get_int(mie_builder_get_ctx(builder), value, 32);
+	mie_attribute_map_put(&op->op_attrib, "value", val, MIE_ATTRMAP_F_REPLACE);
+
+	return result;
+}
+
+struct mie_register *mie_arith_put_constant_f(
+	struct mie_builder *builder, long long value, const char *name)
+{
+	struct mie_op *op
+		= mie_builder_put_op(builder, "arith", "constant", NULL, 0);
+	const struct mie_type *ty
+		= mie_ctx_get_int_type(mie_builder_get_ctx(builder), 32);
+	struct mie_register *result = mie_op_add_result(op, ty);
+
+	result->reg_block = mie_builder_get_current_block(builder);
+	mie_builder_put_name(builder, &result->reg_name, name);
+
+	struct mie_attribute *val
+		= mie_ctx_get_float(mie_builder_get_ctx(builder), value, 32);
+	mie_attribute_map_put(&op->op_attrib, "value", val, MIE_ATTRMAP_F_REPLACE);
+
+	return result;
+}
+
 MIE_OP_DEFINITION_BEGIN(mie_arith_constant, "constant")
 	MIE_OP_DEFINITION_PRINT(print);
 	MIE_OP_DEFINITION_PARSE(parse);

mie/dialect/builtin/attribute/int.c

@@ -21,16 +21,25 @@ static enum mie_status print(
 		b_stream_write_string(out->p_stream, "#builtin.int<", NULL);
 	}
 
-	if (int_ty->i_width < 64 || !abbrev) {
+	if (int_ty->i_width <= 64) {
 		b_stream_write_fmt(
-			out->p_stream, NULL, "%zu : i%zu",
+			out->p_stream, NULL, "%zu", int_val->i_val.v_small,
-			int_val->i_val.v_small, int_ty->i_width);
+			int_ty->i_width);
-	} else if (int_ty->i_width == 64 && abbrev) {
+	} else {
+		b_stream_write_fmt(out->p_stream, NULL, "INF", int_ty->i_width);
+	}
+
+	if (int_ty->i_width != 64 || !abbrev) {
+		b_stream_write_string(out->p_stream, " : ", NULL);
+
+		if (abbrev) {
 			b_stream_write_fmt(
-			out->p_stream, NULL, "%zu", int_val->i_val.v_small);
+				out->p_stream, NULL, "i%zu", int_ty->i_width);
 		} else {
 			b_stream_write_fmt(
-			out->p_stream, NULL, "INF : i%zu", int_ty->i_width);
+				out->p_stream, NULL, "!builtin.int<%zu>",
+				int_ty->i_width);
+		}
 	}
 
 	if (!abbrev) {

mie/dialect/builtin/attribute/type.c

@@ -7,6 +7,23 @@
 #include <mie/parse/parser.h>
 #include <mie/print/printer.h>
 
+struct mie_attribute *mie_type_attr_create(
+	struct mie_ctx *ctx, const struct mie_type *ty)
+{
+	struct mie_type_attr *out = malloc(sizeof *out);
+	if (!out) {
+		return NULL;
+	}
+
+	memset(out, 0x0, sizeof *out);
+
+	out->ty_base.a_def
+		= mie_ctx_get_attribute_definition(ctx, "builtin", "type");
+	out->ty_value = ty;
+
+	return (struct mie_attribute *)out;
+}
+
 static enum mie_status print(
 	const struct mie_attribute *value, struct mie_printer *out)
 {
@@ -25,25 +42,11 @@ static enum mie_status print(
 	return MIE_SUCCESS;
 }
 
-static struct mie_type_attr *type_attr_create(struct mie_ctx *ctx)
-{
-	struct mie_type_attr *ty = malloc(sizeof *ty);
-	if (!ty) {
-		return NULL;
-	}
-
-	memset(ty, 0x0, sizeof *ty);
-
-	ty->ty_base.a_def
-		= mie_ctx_get_attribute_definition(ctx, "builtin", "type");
-
-	return ty;
-}
-
 static enum mie_status parse(
 	struct mie_parser *ctx, const struct mie_attribute **out)
 {
-	struct mie_type_attr *ty = type_attr_create(mie_parser_get_mie_ctx(ctx));
+	struct mie_type_attr *ty = (struct mie_type_attr *)mie_type_attr_create(
+		mie_parser_get_mie_ctx(ctx), NULL);
 	if (!ty) {
 		return MIE_ERR_NO_MEMORY;
 	}

mie/dialect/builtin/builtin.c

@@ -84,17 +84,17 @@ struct mie_attribute *mie_ctx_get_index(struct mie_ctx *ctx, size_t val)
 MIE_DIALECT_BEGIN(mie_builtin, struct builtin_dialect, "builtin")
 	MIE_DIALECT_INIT(init);
 	MIE_DIALECT_CLEANUP(cleanup);
-	MIE_DIALECT_ADD_OP(mie_builtin_module);
+	MIE_DIALECT_ADD_TRAIT(mie_builtin_isolated_from_above);
-	MIE_DIALECT_ADD_TYPE(mie_builtin_string);
+	MIE_DIALECT_ADD_TRAIT(mie_builtin_symbol_table);
 	MIE_DIALECT_ADD_TYPE(mie_builtin_int);
 	MIE_DIALECT_ADD_TYPE(mie_builtin_float);
 	MIE_DIALECT_ADD_TYPE(mie_builtin_index);
-	MIE_DIALECT_ADD_ATTRIBUTE(mie_builtin_string);
+	MIE_DIALECT_ADD_TYPE(mie_builtin_string);
 	MIE_DIALECT_ADD_ATTRIBUTE(mie_builtin_int);
 	MIE_DIALECT_ADD_ATTRIBUTE(mie_builtin_float);
-	MIE_DIALECT_ADD_ATTRIBUTE(mie_builtin_array);
 	MIE_DIALECT_ADD_ATTRIBUTE(mie_builtin_type);
-	MIE_DIALECT_ADD_TRAIT(mie_builtin_isolated_from_above);
+	MIE_DIALECT_ADD_ATTRIBUTE(mie_builtin_string);
-	MIE_DIALECT_ADD_TRAIT(mie_builtin_symbol_table);
 	MIE_DIALECT_ADD_INTERFACE(mie_builtin_symbol);
+	MIE_DIALECT_ADD_ATTRIBUTE(mie_builtin_array);
+	MIE_DIALECT_ADD_OP(mie_builtin_module);
 MIE_DIALECT_END()

mie/dialect/builtin/op/module.c

@@ -1,3 +1,4 @@
+#include <mie/ctx.h>
 #include <mie/dialect/dialect.h>
 #include <mie/ir/op-definition.h>
 #include <mie/ir/op.h>
@@ -26,4 +27,5 @@ static enum mie_status parse(struct mie_parser *parser, struct mie_op *out)
 MIE_OP_DEFINITION_BEGIN(mie_builtin_module, "module")
 	MIE_OP_DEFINITION_PRINT(print);
 	MIE_OP_DEFINITION_PARSE(parse);
+	MIE_OP_DEFINITION_TRAIT("builtin", "isolated-from-above");
 MIE_OP_DEFINITION_END()

mie/dialect/func/op/func.c

@@ -2,9 +2,11 @@
 #include <mie/ctx.h>
 #include <mie/dialect/builtin.h>
 #include <mie/dialect/dialect.h>
+#include <mie/dialect/func.h>
 #include <mie/interface/interface-definition.h>
 #include <mie/interface/interface.h>
 #include <mie/ir/block.h>
+#include <mie/ir/builder.h>
 #include <mie/ir/op-definition.h>
 #include <mie/ir/op.h>
 #include <mie/ir/region.h>
@@ -72,9 +74,63 @@ static enum mie_status parse(struct mie_parser *parser, struct mie_op *out)
 	return MIE_SUCCESS;
 }
 
+struct mie_op *mie_func_put_func(
+	struct mie_builder *builder, const char *name,
+	struct mie_func_parameter *params, size_t nr_params,
+	const struct mie_type **ret_types, size_t nr_ret_types)
+{
+	const struct mie_type **param_types
+		= calloc(nr_params, sizeof *param_types);
+	if (!param_types) {
+		return NULL;
+	}
+
+	for (size_t i = 0; i < nr_params; i++) {
+		param_types[i] = params[i].param_type;
+	}
+
+	const struct mie_type *func_type = mie_ctx_get_function_type(
+		mie_builder_get_ctx(builder), param_types, nr_params, ret_types,
+		nr_ret_types);
+	free(param_types);
+
+	if (!func_type) {
+		return NULL;
+	}
+
+	struct mie_op *op = mie_builder_put_op(builder, "func", "func", NULL, 0);
+
+	struct mie_region *region = mie_op_add_region(op);
+	struct mie_block *entry = mie_region_add_block(region);
+	mie_name_map_put(region->r_names, &entry->b_name, "entry", 0);
+
+	for (size_t i = 0; i < nr_params; i++) {
+		struct mie_register *param_reg = mie_block_add_param(entry);
+		mie_name_map_put(
+			region->r_names, &param_reg->reg_name,
+			params[i].param_name, 0);
+		param_reg->reg_type = params[i].param_type;
+		params[i].param_reg = param_reg;
+	}
+
+	struct mie_attribute *sym_name
+		= mie_ctx_get_string(mie_builder_get_ctx(builder), name);
+	struct mie_attribute *function_type
+		= mie_type_attr_create(mie_builder_get_ctx(builder), func_type);
+
+	mie_attribute_map_put(
+		&op->op_attrib, "sym_name", sym_name, MIE_ATTRMAP_F_REPLACE);
+	mie_attribute_map_put(
+		&op->op_attrib, "function_type", function_type,
+		MIE_ATTRMAP_F_REPLACE);
+
+	return op;
+}
+
 MIE_OP_DEFINITION_BEGIN(mie_func_func, "func")
 	MIE_OP_DEFINITION_PRINT(print);
 	MIE_OP_DEFINITION_PARSE(parse);
+	MIE_OP_DEFINITION_TRAIT("builtin", "isolated-from-above");
 	MIE_OP_INTERFACE_BEGIN("builtin", "symbol", struct mie_symbol)
 		MIE_OP_INTERFACE_FUNC(sym_get_name) = NULL;
 	MIE_OP_INTERFACE_END()

mie/dialect/scf/op/if.c

@@ -1,9 +1,45 @@
 #include <mie/dialect/dialect.h>
+#include <mie/ir/builder.h>
 #include <mie/ir/op-definition.h>
+#include <mie/ir/op.h>
+#include <mie/ir/region.h>
 #include <mie/macros.h>
+#include <mie/print/printer.h>
 
 static enum mie_status print(struct mie_printer *printer, const struct mie_op *op)
 {
+	b_stream_write_char(printer->p_stream, ' ');
+	mie_printer_print_op_arg(printer, &op->op_args.items[0], false);
+
+	if (MIE_VECTOR_COUNT(op->op_result) > 0) {
+		b_stream_write_string(printer->p_stream, " -> ", NULL);
+
+		if (MIE_VECTOR_COUNT(op->op_result) > 1) {
+			b_stream_write_char(printer->p_stream, '(');
+		}
+	}
+
+	for (size_t i = 0; i < MIE_VECTOR_COUNT(op->op_result); i++) {
+		if (i > 0) {
+			b_stream_write_string(printer->p_stream, ", ", NULL);
+		}
+
+		mie_printer_print_type(printer, op->op_result.items[i].reg_type);
+	}
+
+	if (MIE_VECTOR_COUNT(op->op_result) > 1) {
+		b_stream_write_char(printer->p_stream, '(');
+	}
+
+	b_stream_write_char(printer->p_stream, ' ');
+
+	mie_printer_print_region(printer, &op->op_regions.items[0], 0);
+
+	if (MIE_VECTOR_COUNT(op->op_regions) > 1) {
+		b_stream_write_string(printer->p_stream, " else ", NULL);
+		mie_printer_print_region(printer, &op->op_regions.items[1], 0);
+	}
+
 	return MIE_SUCCESS;
 }
 
@@ -12,6 +48,35 @@ static enum mie_status parse(struct mie_parser *parser, struct mie_op *out)
 	return MIE_SUCCESS;
 }
 
+struct mie_op *mie_scf_put_if(
+	struct mie_builder *builder, struct mie_register *cond,
+	const struct mie_type *result_type, struct mie_region **out_true,
+	struct mie_region **out_false, const char *name)
+{
+	struct mie_op *op = mie_builder_put_op(builder, "scf", "if", &cond, 1);
+	if (!op) {
+		return NULL;
+	}
+
+	if (result_type) {
+		struct mie_register *result = mie_op_add_result(op, result_type);
+		mie_builder_put_name(builder, &result->reg_name, name);
+	}
+
+	struct mie_region *r_true = mie_op_add_region(op);
+	struct mie_region *r_false = mie_op_add_region(op);
+
+	if (out_true) {
+		*out_true = r_true;
+	}
+
+	if (out_false) {
+		*out_false = r_false;
+	}
+
+	return op;
+}
+
 MIE_OP_DEFINITION_BEGIN(mie_scf_if, "if")
 	MIE_OP_DEFINITION_PRINT(print);
 	MIE_OP_DEFINITION_PARSE(parse);

mie/dialect/scf/op/yield.c

@@ -1,9 +1,32 @@
 #include <mie/dialect/dialect.h>
+#include <mie/ir/builder.h>
 #include <mie/ir/op-definition.h>
+#include <mie/ir/op.h>
 #include <mie/macros.h>
+#include <mie/print/printer.h>
 
 static enum mie_status print(struct mie_printer *printer, const struct mie_op *op)
 {
+	b_stream_write_char(printer->p_stream, ' ');
+	for (size_t i = 0; i < MIE_VECTOR_COUNT(op->op_args); i++) {
+		if (i > 0) {
+			b_stream_write_string(printer->p_stream, ", ", NULL);
+		}
+
+		mie_printer_print_op_arg(printer, &op->op_args.items[i], false);
+	}
+
+	b_stream_write_string(printer->p_stream, " : ", NULL);
+
+	for (size_t i = 0; i < MIE_VECTOR_COUNT(op->op_args); i++) {
+		if (i > 0) {
+			b_stream_write_string(printer->p_stream, ", ", NULL);
+		}
+
+		mie_printer_print_type(
+			printer, mie_op_arg_get_type(&op->op_args.items[i]));
+	}
+
 	return MIE_SUCCESS;
 }
 
@@ -12,6 +35,12 @@ static enum mie_status parse(struct mie_parser *parser, struct mie_op *out)
 	return MIE_SUCCESS;
 }
 
+struct mie_op *mie_scf_put_yield(
+	struct mie_builder *builder, struct mie_register *value)
+{
+	return mie_builder_put_op(builder, "scf", "yield", &value, 1);
+}
+
 MIE_OP_DEFINITION_BEGIN(mie_scf_yield, "yield")
 	MIE_OP_DEFINITION_PRINT(print);
 	MIE_OP_DEFINITION_PARSE(parse);

mie/include/mie/ctx.h

@@ -36,6 +36,8 @@ struct mie_ctx {
 MIE_API struct mie_ctx *mie_ctx_create(void);
 MIE_API void mie_ctx_destroy(struct mie_ctx *ctx);
 
+MIE_API struct mie_op *mie_ctx_create_op(
+	const struct mie_ctx *ctx, const char *dialect, const char *op);
 MIE_API bool mie_ctx_resolve_op(const struct mie_ctx *ctx, struct mie_op *op);
 
 MIE_API struct mie_dialect *mie_ctx_get_dialect(

mie/include/mie/dialect/arith.h

@@ -8,7 +8,19 @@
 
 struct mie_ctx;
 struct mie_dialect;
+struct mie_builder;
 
 MIE_API struct mie_dialect *mie_arith_dialect_create(struct mie_ctx *ctx);
 
+MIE_API struct mie_register *mie_arith_put_constant_i(
+	struct mie_builder *builder, long long value, const char *name);
+MIE_API struct mie_register *mie_arith_put_constant_f(
+	struct mie_builder *builder, long long value, const char *name);
+MIE_API struct mie_register *mie_arith_put_addi(
+	struct mie_builder *builder, struct mie_register *left,
+	struct mie_register *right, const char *name);
+MIE_API struct mie_register *mie_arith_put_addf(
+	struct mie_builder *builder, struct mie_register *left,
+	struct mie_register *right, const char *name);
+
 #endif

mie/include/mie/dialect/builtin.h

@@ -121,6 +121,9 @@ MIE_API struct mie_type *mie_ctx_get_int_type(struct mie_ctx *ctx, size_t bit_wi
 MIE_API struct mie_type *mie_ctx_get_float_type(
 	struct mie_ctx *ctx, size_t bit_width);
 
+MIE_API struct mie_attribute *mie_type_attr_create(
+	struct mie_ctx *ctx, const struct mie_type *ty);
+
 MIE_API size_t mie_int_type_get_width(const struct mie_type *type);
 MIE_API size_t mie_float_type_get_width(const struct mie_type *type);
 

mie/include/mie/dialect/func.h

@@ -2,10 +2,25 @@
 #define MIE_DIALECT_FUNC_H_
 
 #include <mie/misc.h>
+#include <stddef.h>
 
 struct mie_ctx;
+struct mie_type;
 struct mie_dialect;
+struct mie_register;
+struct mie_builder;
+
+struct mie_func_parameter {
+	const char *param_name;
+	const struct mie_type *param_type;
+	struct mie_register *param_reg;
+};
 
 MIE_API struct mie_dialect *mie_func_dialect_create(struct mie_ctx *ctx);
 
+MIE_API struct mie_op *mie_func_put_func(
+	struct mie_builder *builder, const char *name,
+	struct mie_func_parameter *params, size_t nr_params,
+	const struct mie_type **ret_types, size_t nr_ret_types);
+
 #endif

mie/include/mie/dialect/scf.h

@@ -4,8 +4,19 @@
 #include <mie/misc.h>
 
 struct mie_ctx;
+struct mie_type;
+struct mie_region;
 struct mie_dialect;
+struct mie_builder;
+struct mie_register;
 
 MIE_API struct mie_dialect *mie_scf_dialect_create(struct mie_ctx *ctx);
 
+MIE_API struct mie_op *mie_scf_put_if(
+	struct mie_builder *builder, struct mie_register *cond,
+	const struct mie_type *result_type, struct mie_region **out_true,
+	struct mie_region **out_false, const char *name);
+MIE_API struct mie_op *mie_scf_put_yield(
+	struct mie_builder *builder, struct mie_register *value);
+
 #endif

mie/include/mie/ir/block.h

@@ -20,5 +20,6 @@ struct mie_block {
 extern struct mie_vector_ops mie_block_vector_ops;
 
 MIE_API struct mie_op *mie_block_add_op(struct mie_block *block);
+MIE_API struct mie_register *mie_block_add_param(struct mie_block *block);
 
 #endif

mie/include/mie/ir/builder.h

@@ -0,0 +1,38 @@
+#ifndef MIE_IR_BUILDER_H_
+#define MIE_IR_BUILDER_H_
+
+#include <mie/misc.h>
+#include <stddef.h>
+
+struct mie_op;
+struct mie_ctx;
+struct mie_type;
+struct mie_name;
+struct mie_block;
+struct mie_region;
+struct mie_register;
+
+struct mie_builder;
+
+MIE_API struct mie_builder *mie_builder_create(
+	struct mie_ctx *ctx, struct mie_op *root);
+MIE_API void mie_builder_destroy(struct mie_builder *builder);
+
+MIE_API struct mie_ctx *mie_builder_get_ctx(struct mie_builder *builder);
+MIE_API struct mie_block *mie_builder_get_current_block(struct mie_builder *builder);
+
+MIE_API void mie_builder_step_into_op(
+	struct mie_builder *builder, struct mie_op *op);
+MIE_API void mie_builder_step_into_region(
+	struct mie_builder *builder, struct mie_region *region);
+MIE_API void mie_builder_step_into_block(
+	struct mie_builder *builder, struct mie_block *block);
+MIE_API void mie_builder_step_out(struct mie_builder *builder);
+
+MIE_API struct mie_op *mie_builder_put_op(
+	struct mie_builder *, const char *dialect, const char *op,
+	struct mie_register **args, size_t nr_args);
+MIE_API enum mie_status mie_builder_put_name(
+	struct mie_builder *, struct mie_name *name, const char *hint);
+
+#endif

mie/include/mie/ir/op.h

@@ -55,6 +55,7 @@ struct mie_op {
 	const struct mie_dialect *op_dialect;
 	const struct mie_op_definition *op_info;
 
+	struct mie_block *op_container;
 	struct mie_file_span op_name_span;
 	/* only valid if the F_RESOLVED flag is NOT set */
 	char *op_name;
@@ -72,6 +73,11 @@ MIE_API void mie_op_destroy(struct mie_op *op);
 MIE_API void mie_op_init(struct mie_op *op);
 MIE_API void mie_op_cleanup(struct mie_op *op);
 
+MIE_API struct mie_op_arg *mie_op_add_arg(struct mie_op *op);
+MIE_API struct mie_register *mie_op_add_result(
+	struct mie_op *op, const struct mie_type *ty);
+MIE_API struct mie_region *mie_op_add_region(struct mie_op *op);
+
 MIE_API bool mie_op_has_trait(
 	const struct mie_op *op, const char *dialect_name, const char *trait_name);
 MIE_API bool mie_op_has_interface(

mie/include/mie/ir/register.h

@@ -62,8 +62,13 @@ struct mie_register {
 };
 
 extern struct mie_vector_ops mie_register_vector_ops;
+extern struct mie_vector_ops mie_register_use_vector_ops;
 
 MIE_API void mie_register_move(struct mie_register *dest, struct mie_register *src);
 MIE_API void mie_register_cleanup(struct mie_register *reg);
 
+MIE_API void mie_register_use_move(
+	struct mie_register_use *dest, struct mie_register_use *src);
+MIE_API void mie_register_use_cleanup(struct mie_register_use *reg);
+
 #endif

mie/include/mie/ir/rewrite.h

@@ -1,6 +1,60 @@
 #ifndef MIE_IR_REWRITE_H_
 #define MIE_IR_REWRITE_H_
 
+#include <mie/misc.h>
+#include <mie/status.h>
+#include <stddef.h>
+
+struct mie_op;
+struct mie_ctx;
 struct mie_rewriter;
+struct mie_register;
+
+#define MIE_REWRITE_RESULT(result, status)                                     \
+	((struct mie_rewrite_result) {.r_result = (result), .r_status = (status)})
+
+enum mie_match_result {
+	MIE_NO_MATCH_FOUND = 0,
+	MIE_MATCH_FOUND,
+};
+
+struct mie_rewrite_result {
+	enum {
+		MIE_REWRITE_SUCCESS = 0,
+		MIE_REWRITE_IGNORE,
+		MIE_REWRITE_FAILURE,
+	} r_result;
+	enum mie_status r_status;
+};
+
+struct mie_rewrite_pattern {
+	struct {
+		const char *t_dialect_name, *t_op_name;
+		const struct mie_op_definition *t_op;
+	} p_root;
+
+	enum mie_match_result (*p_match)(const struct mie_op *);
+	struct mie_rewrite_result (*p_rewrite)(
+		struct mie_op *, struct mie_rewriter *);
+};
+
+MIE_API struct mie_rewriter *mie_rewriter_create(struct mie_ctx *ctx);
+
+MIE_API struct mie_block *mie_rewriter_get_insertion_block(
+	struct mie_rewriter *rewriter);
+MIE_API struct mie_op *mie_rewriter_get_insertion_point(
+	struct mie_rewriter *rewriter);
+
+MIE_API struct mie_block *mie_rewriter_split_block(
+	struct mie_rewriter *rewriter, struct mie_block *block,
+	struct mie_op *before);
+MIE_API struct mie_block *mie_rewriter_create_block(
+	struct mie_rewriter *rewriter, struct mie_block *insert_before);
+
+MIE_API struct mie_op *mie_rewriter_put_op(
+	struct mie_rewriter *rewriter, const char *dialect, const char *op,
+	struct mie_register **args, size_t nr_args);
+MIE_API enum mie_status mie_rewriter_erase_op(
+	struct mie_rewriter *rewriter, struct mie_op *op);
 
 #endif

mie/include/mie/ir/walk.h

@@ -1,6 +1,7 @@
 #ifndef MIE_IR_WALK_H_
 #define MIE_IR_WALK_H_
 
+#include <blue/core/queue.h>
 #include <mie/misc.h>
 #include <mie/status.h>
 #include <stddef.h>
@@ -26,12 +27,25 @@ enum mie_walker_flags {
 	MIE_WALKER_F_INCLUDE_BLOCKS = 0x20u,
 };
 
-struct mie_walker_item {
+enum mie_walk_item_type {
+	MIE_WALK_ITEM_NONE = 0,
+	MIE_WALK_ITEM_OP,
+	MIE_WALK_ITEM_BLOCK,
+	MIE_WALK_ITEM_REGION,
+};
+
+struct mie_walk_item {
+	int _f;
+	b_queue_entry _e;
+	enum mie_walk_item_type i_type;
+	size_t i_index;
 	size_t i_depth;
+	union {
 		struct mie_op *i_op;
 		struct mie_block *i_block;
 		struct mie_region *i_region;
 	};
+};
 
 MIE_API struct mie_walker *mie_walker_begin(
 	struct mie_op *op, enum mie_walker_flags flags);
@@ -39,6 +53,6 @@ MIE_API void mie_walker_end(struct mie_walker *walker);
 
 MIE_API enum mie_status mie_walker_step(struct mie_walker *walker);
 
-MIE_API struct mie_walker_item *mie_walker_get(struct mie_walker *walker);
+MIE_API struct mie_walk_item *mie_walker_get(struct mie_walker *walker);
 
 #endif

mie/include/mie/pass/pass-definition.h

@@ -14,6 +14,7 @@
 struct mie_op;
 struct mie_ctx;
 struct mie_pass;
+struct mie_dialect;
 struct mie_op_definition;
 struct mie_trait_definition;
 struct mie_interface_definition;
@@ -40,6 +41,7 @@ struct mie_pass_args {
 };
 
 struct mie_pass_filter {
+	const struct mie_dialect *f_dialect;
 	const struct mie_op_definition *f_op;
 	const struct mie_trait_definition *f_trait;
 	const struct mie_interface_definition *f_iface;

mie/ir/block.c

@@ -0,0 +1,27 @@
+#include <mie/ir/block.h>
+#include <mie/ir/op.h>
+#include <mie/ir/register.h>
+
+struct mie_op *mie_block_add_op(struct mie_block *block)
+{
+	struct mie_op *op = mie_vector_emplace_back(block->b_ops, NULL);
+	if (!op) {
+		return NULL;
+	}
+
+	mie_op_init(op);
+	op->op_container = block;
+
+	return op;
+}
+
+struct mie_register *mie_block_add_param(struct mie_block *block)
+{
+	struct mie_register *result = mie_vector_emplace_back(
+		block->b_params, &mie_register_vector_ops);
+	result->reg_flags = MIE_REGISTER_F_VIRTUAL | MIE_REGISTER_F_BLOCK_PARAM;
+	result->reg_block = block;
+	result->reg_op = NULL;
+
+	return result;
+}

mie/ir/builder.c

@@ -0,0 +1,191 @@
+#include <mie/ctx.h>
+#include <mie/ir/block.h>
+#include <mie/ir/builder.h>
+#include <mie/ir/op-definition.h>
+#include <mie/ir/op.h>
+#include <mie/ir/region.h>
+
+struct builder_scope {
+	b_queue_entry s_entry;
+	struct mie_op *s_op;
+	struct mie_region *s_region;
+	struct mie_block *s_block;
+};
+
+struct mie_builder {
+	struct mie_ctx *b_ctx;
+	b_queue b_scope_stack;
+	struct mie_op *b_root;
+	struct mie_op *b_prev_op;
+};
+
+struct mie_builder *mie_builder_create(struct mie_ctx *ctx, struct mie_op *root)
+{
+	struct mie_builder *out = malloc(sizeof *out);
+	if (!out) {
+		return NULL;
+	}
+
+	memset(out, 0x0, sizeof *out);
+
+	out->b_ctx = ctx;
+	out->b_root = root;
+
+	mie_builder_step_into_op(out, root);
+
+	return out;
+}
+
+struct mie_ctx *mie_builder_get_ctx(struct mie_builder *builder)
+{
+	return builder->b_ctx;
+}
+
+static struct mie_name_map *get_current_name_map(struct mie_builder *builder)
+{
+	b_queue_entry *cur = b_queue_last(&builder->b_scope_stack);
+	while (cur) {
+		struct builder_scope *scope
+			= b_unbox(struct builder_scope, cur, s_entry);
+
+		if (scope->s_region && scope->s_region->r_names) {
+			return scope->s_region->r_names;
+		}
+
+		cur = b_queue_prev(cur);
+	}
+
+	return NULL;
+}
+
+struct mie_block *mie_builder_get_current_block(struct mie_builder *builder)
+{
+	b_queue_entry *entry = b_queue_last(&builder->b_scope_stack);
+	if (!entry) {
+		return NULL;
+	}
+
+	struct builder_scope *scope
+		= b_unbox(struct builder_scope, entry, s_entry);
+
+	return scope->s_block;
+}
+
+void mie_builder_step_into_op(struct mie_builder *builder, struct mie_op *op)
+{
+	struct mie_region *region = NULL;
+
+	if (MIE_VECTOR_COUNT(op->op_regions) == 0) {
+		region = mie_op_add_region(op);
+	} else {
+		region = &op->op_regions.items[MIE_VECTOR_COUNT(op->op_regions) - 1];
+	}
+
+	mie_builder_step_into_region(builder, region);
+}
+
+void mie_builder_step_into_region(
+	struct mie_builder *builder, struct mie_region *region)
+{
+	struct mie_block *block = NULL;
+
+	if (MIE_VECTOR_COUNT(region->r_blocks) == 0) {
+		block = mie_region_add_block(region);
+	} else {
+		block = &region->r_blocks.items[MIE_VECTOR_COUNT(region->r_blocks) - 1];
+	}
+
+	mie_builder_step_into_block(builder, block);
+}
+
+void mie_builder_step_into_block(struct mie_builder *builder, struct mie_block *block)
+{
+	struct builder_scope *scope = malloc(sizeof *scope);
+	if (!scope) {
+		return;
+	}
+
+	memset(scope, 0x0, sizeof *scope);
+
+	scope->s_block = block;
+	scope->s_region = block->b_parent;
+	scope->s_op = scope->s_region->r_parent;
+
+	b_queue_push_back(&builder->b_scope_stack, &scope->s_entry);
+}
+
+void mie_builder_step_out(struct mie_builder *builder)
+{
+	b_queue_entry *entry = b_queue_last(&builder->b_scope_stack);
+	if (!entry) {
+		return;
+	}
+
+	struct builder_scope *scope
+		= b_unbox(struct builder_scope, entry, s_entry);
+	b_queue_delete(&builder->b_scope_stack, entry);
+	free(scope);
+}
+
+static struct mie_block *create_current_block(struct mie_builder *builder)
+{
+	struct mie_region *region = NULL;
+
+	if (MIE_VECTOR_COUNT(builder->b_root->op_regions) == 0) {
+		region = mie_op_add_region(builder->b_root);
+	} else {
+		region = &builder->b_root->op_regions
+		                  .items[MIE_VECTOR_COUNT(builder->b_root->op_result) - 1];
+	}
+
+	struct mie_block *block = NULL;
+
+	if (MIE_VECTOR_COUNT(region->r_blocks) == 0) {
+		block = mie_region_add_block(region);
+	} else {
+		block = &region->r_blocks.items[MIE_VECTOR_COUNT(region->r_blocks)];
+	}
+
+	return block;
+}
+
+struct mie_op *mie_builder_put_op(
+	struct mie_builder *builder, const char *dialect, const char *op_name,
+	struct mie_register **args, size_t nr_args)
+{
+	struct mie_block *block = mie_builder_get_current_block(builder);
+
+	const struct mie_op_definition *op_def
+		= mie_ctx_get_op_definition(builder->b_ctx, dialect, op_name);
+	if (!op_def) {
+		return NULL;
+	}
+
+	struct mie_op *op = mie_block_add_op(block);
+	op->op_flags = MIE_OP_F_OP_RESOLVED;
+	op->op_info = op_def;
+	op->op_dialect = op_def->op_parent;
+
+	for (size_t i = 0; i < nr_args; i++) {
+		struct mie_op_arg *arg = mie_op_add_arg(op);
+		arg->arg_flags = MIE_OP_F_ARG_RESOLVED;
+		arg->arg_value.u_reg = args[i];
+		arg->arg_value.u_user = op;
+		b_queue_push_back(&args[i]->reg_use, &arg->arg_value.u_entry);
+	}
+
+	return op;
+}
+
+enum mie_status mie_builder_put_name(
+	struct mie_builder *builder, struct mie_name *name, const char *hint)
+{
+	struct mie_name_map *map = get_current_name_map(builder);
+	if (!map) {
+		return MIE_ERR_BAD_STATE;
+	}
+
+	struct mie_name *result = mie_name_map_put(map, name, hint, 0);
+
+	return result ? MIE_SUCCESS : MIE_ERR_NAME_EXISTS;
+}

mie/ir/op.c

@@ -1,7 +1,39 @@
+#include <assert.h>
 #include <mie/ir/op-definition.h>
 #include <mie/ir/op.h>
+#include <mie/ir/region.h>
 #include <stdlib.h>
 
+static enum mie_status op_arg_cleanup(void *p)
+{
+	struct mie_op_arg *arg = p;
+
+	if (arg->arg_flags & MIE_OP_F_ARG_RESOLVED) {
+		b_queue_delete(
+			&arg->arg_value.u_reg->reg_use, &arg->arg_value.u_entry);
+	}
+
+	return MIE_SUCCESS;
+}
+
+static enum mie_status op_arg_move(void *dst, void *src, size_t itemsz)
+{
+	assert(itemsz == sizeof(struct mie_op_arg));
+	struct mie_op_arg *dest_arg = dst, *src_arg = src;
+	memmove(dest_arg, src_arg, sizeof *src_arg);
+
+	if (src_arg->arg_flags & MIE_OP_F_ARG_RESOLVED) {
+		mie_register_use_move(&dest_arg->arg_value, &src_arg->arg_value);
+	}
+
+	return MIE_SUCCESS;
+}
+
+struct mie_vector_ops op_arg_vector_ops = {
+	.v_destroy = op_arg_cleanup,
+	.v_move = op_arg_move,
+};
+
 struct mie_op *mie_op_create(void)
 {
 	struct mie_op *out = malloc(sizeof *out);
@@ -32,6 +64,43 @@ void mie_op_cleanup(struct mie_op *op)
 	/* TODO */
 }
 
+struct mie_op_arg *mie_op_add_arg(struct mie_op *op)
+{
+	return mie_vector_emplace_back(op->op_args, &op_arg_vector_ops);
+}
+
+struct mie_register *mie_op_add_result(struct mie_op *op, const struct mie_type *ty)
+{
+	struct mie_register *result = mie_vector_emplace_back(
+		op->op_result, &mie_register_vector_ops);
+	result->reg_flags = MIE_REGISTER_F_VIRTUAL | MIE_REGISTER_F_OP_RESULT;
+	result->reg_type = ty;
+	result->reg_op = op;
+
+	return result;
+}
+
+static bool is_isolated(const struct mie_op *op)
+{
+	const struct mie_trait *isolated = mie_trait_table_get_unique(
+		&op->op_info->op_traits, "builtin", "isolated-from-above");
+	return isolated != NULL;
+}
+
+struct mie_region *mie_op_add_region(struct mie_op *op)
+{
+	bool isolated = is_isolated(op);
+
+	struct mie_region *region = mie_vector_emplace_back(op->op_regions, NULL);
+	region->r_parent = op;
+
+	if (isolated) {
+		region->r_names = mie_name_map_create(NULL);
+	}
+
+	return region;
+}
+
 bool mie_op_has_trait(
 	const struct mie_op *op, const char *dialect_name, const char *trait_name)
 {

mie/ir/register.c

@@ -1,13 +1,14 @@
 #include <assert.h>
+#include <blue/core/queue.h>
 #include <mie/ir/register.h>
 
-static enum mie_status cleanup(void *p)
+static enum mie_status reg_cleanup(void *p)
 {
 	mie_register_cleanup(p);
 	return MIE_SUCCESS;
 }
 
-static enum mie_status move(void *dst, void *src, size_t itemsz)
+static enum mie_status reg_move(void *dst, void *src, size_t itemsz)
 {
 	assert(itemsz == sizeof(struct mie_register));
 	struct mie_register *dest_reg = dst, *src_reg = src;
@@ -15,9 +16,23 @@ static enum mie_status move(void *dst, void *src, size_t itemsz)
 	return MIE_SUCCESS;
 }
 
+static enum mie_status reg_use_cleanup(void *p)
+{
+	mie_register_use_cleanup(p);
+	return MIE_SUCCESS;
+}
+
+static enum mie_status reg_use_move(void *dst, void *src, size_t itemsz)
+{
+	assert(itemsz == sizeof(struct mie_register_use));
+	struct mie_register_use *dest_reg = dst, *src_reg = src;
+	mie_register_use_move(dest_reg, src_reg);
+	return MIE_SUCCESS;
+}
+
 struct mie_vector_ops mie_register_vector_ops = {
-	.v_destroy = cleanup,
+	.v_destroy = reg_cleanup,
-	.v_move = move,
+	.v_move = reg_move,
 };
 
 void mie_register_move(struct mie_register *dest, struct mie_register *src)
@@ -35,3 +50,20 @@ void mie_register_cleanup(struct mie_register *reg)
 		mie_name_destroy(&reg->reg_name);
 	}
 }
+
+void mie_register_use_move(
+	struct mie_register_use *dest, struct mie_register_use *src)
+{
+	memmove(dest, src, sizeof *dest);
+
+	if (src->u_reg) {
+		b_queue_move(&src->u_reg->reg_use, &src->u_entry, &dest->u_entry);
+	}
+}
+
+void mie_register_use_cleanup(struct mie_register_use *use)
+{
+	if (use->u_reg) {
+		b_queue_delete(&use->u_reg->reg_use, &use->u_entry);
+	}
+}

mie/ir/walk.c

@@ -1,253 +1,595 @@
+#include <mie/dialect/dialect.h>
 #include <mie/ir/block.h>
+#include <mie/ir/op-definition.h>
 #include <mie/ir/op.h>
 #include <mie/ir/region.h>
 #include <mie/ir/walk.h>
+#include <stdio.h>
+
+#define WALK_ITEM_F_CHILDREN_VISITED 0x01u
+#define WALK_ITEM_F_VISITED          0x02u
 
 #define ITEM_TYPE(f)                 ((f) & 0x0Fu)
 
-enum walk_schedule_item_flags {
-	SCHED_ITEM_F_NONE = 0,
-	SCHED_ITEM_F_OP = 0x01u,
-	SCHED_ITEM_F_BLOCK = 0x02u,
-	SCHED_ITEM_F_REGION = 0x04u,
-
-	SCHED_ITEM_F_VISITED = 0x10u,
-	SCHED_ITEM_F_CHILDREN_SCHEDULED = 0x20u,
-};
-
-struct walk_schedule_item {
-	enum walk_schedule_item_flags i_flags;
-	b_queue_entry i_entry;
-	size_t i_depth;
-
-	union {
-		struct mie_op *i_op;
-		struct mie_block *i_block;
-		struct mie_region *i_region;
-	};
-};
-
 struct mie_walker {
 	enum mie_walker_flags w_flags;
 	struct mie_op *w_root;
-	struct mie_walker_item w_cur;
+	b_queue w_stack;
-	b_queue w_sched;
 };
 
-static struct walk_schedule_item *op_schedule_item_create(struct mie_op *op)
-{
-	struct walk_schedule_item *out = malloc(sizeof *out);
-	if (!out) {
-		return NULL;
-	}
-
-	memset(out, 0x0, sizeof *out);
-
-	out->i_flags = SCHED_ITEM_F_OP;
-	out->i_op = op;
-
-	return out;
-}
-
-static struct walk_schedule_item *block_schedule_item_create(struct mie_block *block)
-{
-	struct walk_schedule_item *out = malloc(sizeof *out);
-	if (!out) {
-		return NULL;
-	}
-
-	memset(out, 0x0, sizeof *out);
-
-	out->i_flags = SCHED_ITEM_F_BLOCK;
-	out->i_block = block;
-
-	return out;
-}
-
-static struct walk_schedule_item *region_schedule_item_create(
-	struct mie_region *region)
-{
-	struct walk_schedule_item *out = malloc(sizeof *out);
-	if (!out) {
-		return NULL;
-	}
-
-	memset(out, 0x0, sizeof *out);
-
-	out->i_flags = SCHED_ITEM_F_REGION;
-	out->i_region = region;
-
-	return out;
-}
-
 static bool should_ignore_item(
-	const struct mie_walker *walker, const struct walk_schedule_item *item)
+	const struct mie_walker *walker, const struct mie_walk_item *item)
 {
-	switch (ITEM_TYPE(item->i_flags)) {
+	switch (item->i_type) {
-	case SCHED_ITEM_F_OP:
+	case MIE_WALK_ITEM_OP:
 		return (walker->w_flags & MIE_WALKER_F_INCLUDE_OPS) == 0;
-	case SCHED_ITEM_F_BLOCK:
+	case MIE_WALK_ITEM_BLOCK:
 		return (walker->w_flags & MIE_WALKER_F_INCLUDE_BLOCKS) == 0;
-	case SCHED_ITEM_F_REGION:
+	case MIE_WALK_ITEM_REGION:
 		return (walker->w_flags & MIE_WALKER_F_INCLUDE_REGIONS) == 0;
 	default:
 		return true;
 	}
 }
 
-static void schedule_child(
+static void push_walk_item(
-	struct mie_walker *walker, struct walk_schedule_item *parent,
+	struct mie_walker *walker, const struct mie_walk_item *item)
-	struct walk_schedule_item *child, b_queue_entry **ep)
 {
-#define REVERSE 0x04u
+	struct mie_walk_item *i = malloc(sizeof *i);
-
+	if (!i) {
-	enum {
-		PREORDER = 0x01u,
-		PREORDER_REVERSE = PREORDER | REVERSE,
-		POSTORDER = 0x02u,
-		POSTORDER_REVERSE = POSTORDER | REVERSE,
-	} mode;
-
-	if (walker->w_flags & MIE_WALKER_F_POSTORDER) {
-		mode = POSTORDER;
-	} else {
-		mode = PREORDER;
-	}
-
-	if (walker->w_flags & MIE_WALKER_F_BACKWARD) {
-		mode |= REVERSE;
-	}
-
-	child->i_depth = parent->i_depth;
-	if (!should_ignore_item(walker, child)) {
-		child->i_depth++;
-	}
-
-	switch (mode) {
-	case PREORDER:
-		b_queue_insert_after(&walker->w_sched, &child->i_entry, *ep);
-		*ep = &child->i_entry;
-		break;
-	case PREORDER_REVERSE:
-		b_queue_insert_after(
-			&walker->w_sched, &child->i_entry, &parent->i_entry);
-		*ep = &parent->i_entry;
-		break;
-	case POSTORDER:
-		if (*ep == &parent->i_entry) {
-			b_queue_insert_before(
-				&walker->w_sched, &child->i_entry, *ep);
-		} else {
-			b_queue_insert_after(
-				&walker->w_sched, &child->i_entry, *ep);
-		}
-
-		*ep = &child->i_entry;
-		break;
-	case POSTORDER_REVERSE:
-		b_queue_insert_before(&walker->w_sched, &child->i_entry, *ep);
-		*ep = &child->i_entry;
-		break;
-	default:
 		return;
 	}
 
-#undef REVERSE
+	memcpy(i, item, sizeof *i);
+	b_queue_push_back(&walker->w_stack, &i->_e);
 }
 
-static enum mie_status schedule_children_of_region(
+static void pop_walk_item(struct mie_walker *walker)
-	struct mie_walker *walker, struct walk_schedule_item *item)
 {
-	struct mie_region *region = item->i_region;
+	b_queue_entry *entry = b_queue_pop_back(&walker->w_stack);
-
+	if (entry) {
-	b_queue_entry *tmp = &item->i_entry;
+		struct mie_walk_item *item
-
+			= b_unbox(struct mie_walk_item, entry, _e);
-	for (size_t i = 0; i < MIE_VECTOR_COUNT(region->r_blocks); i++) {
+		free(item);
-		struct mie_block *block = &region->r_blocks.items[i];
+	}
-		struct walk_schedule_item *child
-			= block_schedule_item_create(block);
-
-		schedule_child(walker, item, child, &tmp);
 }
 
-	return MIE_SUCCESS;
+static struct mie_walk_item *current_item(struct mie_walker *walker)
-}
-
-static enum mie_status schedule_children_of_block(
-	struct mie_walker *walker, struct walk_schedule_item *item)
 {
-	struct mie_block *block = item->i_block;
+	b_queue_entry *entry = b_queue_last(&walker->w_stack);
-
+	if (!entry) {
-	b_queue_entry *tmp = &item->i_entry;
+		return NULL;
-
-	for (size_t i = 0; i < MIE_VECTOR_COUNT(block->b_ops); i++) {
-		struct mie_op *op = &block->b_ops.items[i];
-		struct walk_schedule_item *child = op_schedule_item_create(op);
-
-		schedule_child(walker, item, child, &tmp);
 	}
 
-	return MIE_SUCCESS;
+	struct mie_walk_item *item = b_unbox(struct mie_walk_item, entry, _e);
+	return item->i_type != MIE_WALK_ITEM_NONE ? item : NULL;
 }
 
-static enum mie_status schedule_children_of_op(
+static struct mie_op *get_first_child(struct mie_walker *walker, struct mie_op *op)
-	struct mie_walker *walker, struct walk_schedule_item *item)
 {
-	struct mie_op *op = item->i_op;
+	bool backwards = (walker->w_flags & MIE_WALKER_F_BACKWARD) != 0;
 
-	b_queue_entry *tmp = &item->i_entry;
+	while (1) {
-
+		if (MIE_VECTOR_COUNT(op->op_regions) == 0) {
-	for (size_t i = 0; i < MIE_VECTOR_COUNT(op->op_regions); i++) {
-		struct mie_region *region = &op->op_regions.items[i];
-		struct walk_schedule_item *child
-			= region_schedule_item_create(region);
-
-		schedule_child(walker, item, child, &tmp);
-	}
-
-	return MIE_SUCCESS;
-}
-
-static enum mie_status schedule_children(
-	struct mie_walker *walker, struct walk_schedule_item *item)
-{
-	if (item->i_flags & SCHED_ITEM_F_CHILDREN_SCHEDULED) {
-		return MIE_SUCCESS;
-	}
-
-	enum mie_status status;
-
-	switch (ITEM_TYPE(item->i_flags)) {
-	case SCHED_ITEM_F_BLOCK:
-		status = schedule_children_of_block(walker, item);
 			break;
-	case SCHED_ITEM_F_REGION:
+		}
-		status = schedule_children_of_region(walker, item);
+
+		size_t region_index
+			= backwards ? MIE_VECTOR_COUNT(op->op_regions) - 1 : 0;
+		struct mie_region *region = &op->op_regions.items[region_index];
+		if (MIE_VECTOR_COUNT(region->r_blocks) == 0) {
 			break;
-	case SCHED_ITEM_F_OP:
+		}
-		status = schedule_children_of_op(walker, item);
+
+		size_t block_index
+			= backwards ? MIE_VECTOR_COUNT(region->r_blocks) - 1 : 0;
+		struct mie_block *block = &region->r_blocks.items[block_index];
+		if (MIE_VECTOR_COUNT(block->b_ops) == 0) {
+			break;
+		}
+
+		size_t op_index
+			= backwards ? MIE_VECTOR_COUNT(block->b_ops) - 1 : 0;
+		op = &block->b_ops.items[op_index];
+	}
+
+	return op;
+}
+
+static size_t walk_item_get_nr_children(const struct mie_walk_item *item)
+{
+	switch (item->i_type) {
+	case MIE_WALK_ITEM_OP:
+		return MIE_VECTOR_COUNT(item->i_op->op_regions);
+	case MIE_WALK_ITEM_BLOCK:
+		return MIE_VECTOR_COUNT(item->i_block->b_ops);
+	case MIE_WALK_ITEM_REGION:
+		return MIE_VECTOR_COUNT(item->i_region->r_blocks);
+	default:
+		return 0;
+	}
+}
+
+static bool should_correct_depth(
+	struct mie_walker *walker, const struct mie_walk_item *item)
+{
+	if (should_ignore_item(walker, item)) {
+		return true;
+	}
+
+	size_t temp = 0;
+	switch (item->i_type) {
+	case MIE_WALK_ITEM_BLOCK:
+		return false;   //(walker->w_flags & MIE_WALKER_F_INCLUDE_OPS) == 0;
+	default:
+		break;
+	}
+
+	return false;
+}
+
+static bool walk_item_get_child(
+	struct mie_walker *walker, const struct mie_walk_item *item,
+	size_t index, struct mie_walk_item *child)
+{
+	bool ok = false;
+
+	switch (item->i_type) {
+	case MIE_WALK_ITEM_OP:
+		if (MIE_VECTOR_COUNT(item->i_op->op_regions) <= index) {
+			ok = false;
+			break;
+		}
+
+		child->i_type = MIE_WALK_ITEM_REGION;
+		child->i_region = &item->i_op->op_regions.items[index];
+		ok = true;
+		break;
+	case MIE_WALK_ITEM_BLOCK:
+		if (MIE_VECTOR_COUNT(item->i_block->b_ops) <= index) {
+			ok = false;
+			break;
+		}
+
+		child->i_type = MIE_WALK_ITEM_OP;
+		child->i_op = &item->i_block->b_ops.items[index];
+		ok = true;
+		break;
+	case MIE_WALK_ITEM_REGION:
+		if (MIE_VECTOR_COUNT(item->i_region->r_blocks) <= index) {
+			ok = false;
+			break;
+		}
+
+		child->i_type = MIE_WALK_ITEM_BLOCK;
+		child->i_block = &item->i_region->r_blocks.items[index];
+		ok = true;
 		break;
 	default:
-		status = MIE_ERR_BAD_STATE;
 		break;
 	}
 
-	item->i_flags |= SCHED_ITEM_F_CHILDREN_SCHEDULED;
+	if (!ok) {
+		return false;
+	}
+
+	child->i_depth = item->i_depth + 1;
+	child->i_index = index;
+
+	if (should_correct_depth(walker, item)) {
+		child->i_depth--;
+	}
+
+	return true;
+}
+
+static bool walk_item_get_next_sibling(
+	const struct mie_walk_item *item, struct mie_walk_item *sibling)
+{
+	if (item->i_depth == 0) {
+		return false;
+	}
+
+	sibling->i_depth = item->i_depth;
+	sibling->i_type = item->i_type;
+	sibling->i_index = item->i_index + 1;
+
+	struct mie_region *parent_r = NULL;
+	struct mie_block *parent_b = NULL;
+	struct mie_op *parent_o = NULL;
+
+	switch (item->i_type) {
+	case MIE_WALK_ITEM_OP:
+		parent_b = item->i_op->op_container;
+		if (!parent_b) {
+			return false;
+		}
+
+		if (item->i_index + 1 >= MIE_VECTOR_COUNT(parent_b->b_ops)) {
+			return false;
+		}
+
+		sibling->i_op = &parent_b->b_ops.items[item->i_index + 1];
+		return true;
+	case MIE_WALK_ITEM_BLOCK:
+		parent_r = item->i_block->b_parent;
+		if (!parent_r) {
+			return false;
+		}
+
+		if (item->i_index + 1 >= MIE_VECTOR_COUNT(parent_r->r_blocks)) {
+			return false;
+		}
+
+		sibling->i_block = &parent_r->r_blocks.items[item->i_index + 1];
+		return true;
+	case MIE_WALK_ITEM_REGION:
+		parent_o = item->i_region->r_parent;
+		if (!parent_o) {
+			return false;
+		}
+
+		if (item->i_index + 1 >= MIE_VECTOR_COUNT(parent_o->op_regions)) {
+			return false;
+		}
+
+		sibling->i_region = &parent_o->op_regions.items[item->i_index + 1];
+		return true;
+	default:
+		return false;
+	}
+}
+
+static bool walk_item_get_prev_sibling(
+	const struct mie_walk_item *item, struct mie_walk_item *sibling)
+{
+	if (item->i_depth == 0 || item->i_index == 0) {
+		return false;
+	}
+
+	sibling->i_depth = item->i_depth;
+	sibling->i_type = item->i_type;
+	sibling->i_index = item->i_index - 1;
+
+	struct mie_region *parent_r = NULL;
+	struct mie_block *parent_b = NULL;
+	struct mie_op *parent_o = NULL;
+
+	switch (item->i_type) {
+	case MIE_WALK_ITEM_OP:
+		parent_b = item->i_op->op_container;
+		if (!parent_b) {
+			return false;
+		}
+
+		sibling->i_op = &parent_b->b_ops.items[item->i_index - 1];
+		return true;
+	case MIE_WALK_ITEM_BLOCK:
+		parent_r = item->i_block->b_parent;
+		if (!parent_r) {
+			return false;
+		}
+
+		sibling->i_block = &parent_r->r_blocks.items[item->i_index - 1];
+		return true;
+	case MIE_WALK_ITEM_REGION:
+		parent_o = item->i_region->r_parent;
+		if (!parent_o) {
+			return false;
+		}
+
+		sibling->i_region = &parent_o->op_regions.items[item->i_index - 1];
+		return true;
+	default:
+		return false;
+	}
+}
+
+static void print_stack(struct mie_walker *walker)
+{
+	b_queue_entry *entry = b_queue_last(&walker->w_stack);
+
+	while (entry) {
+		struct mie_walk_item *item
+			= b_unbox(struct mie_walk_item, entry, _e);
+
+		switch (item->i_type) {
+		case MIE_WALK_ITEM_OP:
+			printf("* %zu: op %p", item->i_depth, item->i_op);
+			if (item->i_op->op_flags & MIE_OP_F_OP_RESOLVED) {
+				printf(" %s.%s", item->i_op->op_dialect->d_name,
+				       item->i_op->op_info->op_name);
+			} else {
+				printf(" %s", item->i_op->op_name);
+			}
+			break;
+		case MIE_WALK_ITEM_BLOCK:
+			printf("* %zu: block %p %s", item->i_depth,
+			       item->i_block, item->i_block->b_name.n_str);
+			break;
+		case MIE_WALK_ITEM_REGION:
+			printf("* %zu: region %p", item->i_depth, item->i_region);
+			break;
+		default:
+			printf(" unknown");
+			break;
+		}
+
+		printf("\n");
+
+		entry = b_queue_prev(entry);
+	}
+}
+
+static bool step_pre_f(struct mie_walker *walker)
+{
+	/* forward, pre-order traversal:
+	 * if this item has children, we need to visit the first one.
+	 * if this item has no children, we need to visit the next sibling.
+	 * if this is the last sibling, step up until we find an item that
+	 * has a next sibling.
+	 * if no item is found, we are done. */
+
+	struct mie_walk_item *item = current_item(walker);
+	struct mie_walk_item next;
+
+	bool ok = false;
+	size_t nr_children = walk_item_get_nr_children(item);
+	if (nr_children > 0) {
+		ok = walk_item_get_child(walker, item, 0, &next);
+
+		if (ok) {
+			push_walk_item(walker, &next);
+		}
+
+		return ok;
+	}
+
+	if (walk_item_get_next_sibling(item, &next)) {
+		pop_walk_item(walker);
+		push_walk_item(walker, &next);
+		return true;
+	}
+
+	static int i = 0;
+	while (1) {
+		pop_walk_item(walker);
+		struct mie_walk_item *parent = current_item(walker);
+		if (!parent) {
+			return false;
+		}
+
+		ok = walk_item_get_next_sibling(parent, &next);
+
+		if (ok) {
+			pop_walk_item(walker);
+			push_walk_item(walker, &next);
+			break;
+		}
+	}
+
+	return ok;
+}
+
+static bool step_pre_b(struct mie_walker *walker)
+{
+	/* backward, pre-order traversal:
+	 * if this item has children, we need to visit the last one.
+	 * if this item has no children, we need to visit the previous sibling.
+	 * if this is the first sibling, step up until we find an item that
+	 * has a previous sibling.
+	 * if no item is found, we are done. */
+
+	struct mie_walk_item *item = current_item(walker);
+	struct mie_walk_item next;
+
+	bool ok = false;
+	size_t nr_children = walk_item_get_nr_children(item);
+	if (nr_children > 0) {
+		ok = walk_item_get_child(walker, item, nr_children - 1, &next);
+
+		if (ok) {
+			push_walk_item(walker, &next);
+		}
+
+		return ok;
+	}
+
+	if (walk_item_get_prev_sibling(item, &next)) {
+		pop_walk_item(walker);
+		push_walk_item(walker, &next);
+		return true;
+	}
+
+	static int i = 0;
+	while (1) {
+		pop_walk_item(walker);
+		struct mie_walk_item *parent = current_item(walker);
+		if (!parent) {
+			return false;
+		}
+
+		ok = walk_item_get_prev_sibling(parent, &next);
+
+		if (ok) {
+			pop_walk_item(walker);
+			push_walk_item(walker, &next);
+			break;
+		}
+	}
+
+	return ok;
+}
+
+static bool step_post_f(struct mie_walker *walker)
+{
+	/* forward, post-order traversal:
+	 * if this item has children:
+	 *    if they have already been visited, visit the item itself
+	 *    if they haven't been visited yet, visit the first one.
+	 * if this item has a next sibling, move to the sibling and goto step 1.
+	 * if this item is the last child, we need to visit the parent next. */
+	struct mie_walk_item *item = current_item(walker);
+	item->_f |= WALK_ITEM_F_VISITED;
+
+	struct mie_walk_item next;
+	bool ok = false;
+
+	while (1) {
+		item = current_item(walker);
+		size_t nr_children = walk_item_get_nr_children(item);
+
+		if (nr_children > 0 && !(item->_f & WALK_ITEM_F_CHILDREN_VISITED)) {
+			ok = walk_item_get_child(walker, item, 0, &next);
+
+			if (ok) {
+				push_walk_item(walker, &next);
+			}
+
+			return ok;
+		}
+
+		if (nr_children == 0 && !(item->_f & WALK_ITEM_F_VISITED)) {
+			return true;
+		}
+
+		if (walk_item_get_next_sibling(item, &next)) {
+			pop_walk_item(walker);
+			push_walk_item(walker, &next);
+			continue;
+		}
+
+		pop_walk_item(walker);
+		struct mie_walk_item *parent = current_item(walker);
+		if (parent) {
+			parent->_f |= WALK_ITEM_F_CHILDREN_VISITED;
+		}
+
+		return parent != NULL;
+	}
+}
+
+static bool step_post_b(struct mie_walker *walker)
+{
+	/* backward, post-order traversal:
+	 * if this item has children:
+	 *    if they have already been visited, visit the item itself
+	 *    if they haven't been visited yet, visit the last one.
+	 * if this item has a previous sibling, move to the sibling and goto step 1.
+	 * if this item is the first child, we need to visit the parent next. */
+	struct mie_walk_item *item = current_item(walker);
+	item->_f |= WALK_ITEM_F_VISITED;
+
+	struct mie_walk_item next;
+	bool ok = false;
+
+	while (1) {
+		item = current_item(walker);
+		size_t nr_children = walk_item_get_nr_children(item);
+
+		if (nr_children > 0 && !(item->_f & WALK_ITEM_F_CHILDREN_VISITED)) {
+			ok = walk_item_get_child(
+				walker, item, nr_children - 1, &next);
+
+			if (ok) {
+				push_walk_item(walker, &next);
+			}
+
+			return ok;
+		}
+
+		if (nr_children == 0 && !(item->_f & WALK_ITEM_F_VISITED)) {
+			return true;
+		}
+
+		if (walk_item_get_prev_sibling(item, &next)) {
+			pop_walk_item(walker);
+			push_walk_item(walker, &next);
+			continue;
+		}
+
+		pop_walk_item(walker);
+		struct mie_walk_item *parent = current_item(walker);
+		if (parent) {
+			parent->_f |= WALK_ITEM_F_CHILDREN_VISITED;
+		}
+
+		return parent != NULL;
+	}
+}
+
+static bool step(struct mie_walker *walker)
+{
+	bool backward = (walker->w_flags & MIE_WALKER_F_BACKWARD) != 0;
+	bool postorder = (walker->w_flags & MIE_WALKER_F_POSTORDER) != 0;
+
+	if (backward) {
+		if (postorder) {
+			return step_post_b(walker);
+		}
+
+		return step_pre_b(walker);
+	}
+
+	if (postorder) {
+		return step_post_f(walker);
+	}
+
+	return step_pre_f(walker);
+}
+
+static enum mie_status prepare_preorder_traversal(struct mie_walker *walker)
+{
+	struct mie_walk_item *item = malloc(sizeof *item);
+	if (!item) {
+		return MIE_ERR_NO_MEMORY;
+	}
+
+	memset(item, 0x0, sizeof *item);
+	item->i_op = walker->w_root;
+	item->i_type = MIE_WALK_ITEM_OP;
+
+	push_walk_item(walker, item);
+
 	return MIE_SUCCESS;
 }
 
 static enum mie_status prepare_postorder_traversal(struct mie_walker *walker)
 {
-	b_queue_entry *cur = b_queue_last(&walker->w_sched);
+	struct mie_walk_item item = {};
-	while (cur) {
+	item.i_op = walker->w_root;
-		struct walk_schedule_item *item
+	item.i_type = MIE_WALK_ITEM_OP;
-			= b_unbox(struct walk_schedule_item, cur, i_entry);
-		schedule_children(walker, item);
 
-		cur = b_queue_prev(cur);
+	push_walk_item(walker, &item);
+
+	bool backward = walker->w_flags & MIE_WALKER_F_BACKWARD;
+	bool ok = false;
+
+	while (1) {
+		struct mie_walk_item *current = current_item(walker);
+		struct mie_walk_item child;
+		size_t nr_children = walk_item_get_nr_children(current);
+		if (!nr_children) {
+			break;
 		}
 
-	return MIE_SUCCESS;
+		bool ok = false;
+
+		if (backward) {
+			ok = walk_item_get_child(
+				walker, current, nr_children - 1, &child);
+		} else {
+			ok = walk_item_get_child(walker, current, 0, &child);
+		}
+
+		if (!ok) {
+			break;
+		}
+
+		push_walk_item(walker, &child);
+	}
+
+	return ok ? MIE_SUCCESS : MIE_ERR_NO_DATA;
 }
 
 struct mie_walker *mie_walker_begin(struct mie_op *op, enum mie_walker_flags flags)
@@ -262,11 +604,15 @@ struct mie_walker *mie_walker_begin(struct mie_op *op, enum mie_walker_flags fla
 	out->w_flags = flags;
 	out->w_root = op;
 
-	struct walk_schedule_item *item = op_schedule_item_create(op);
-	b_queue_push_back(&out->w_sched, &item->i_entry);
-
 	if (flags & MIE_WALKER_F_POSTORDER) {
 		prepare_postorder_traversal(out);
+	} else {
+		prepare_preorder_traversal(out);
+	}
+
+	struct mie_walk_item *cur = current_item(out);
+	if (should_ignore_item(out, cur)) {
+		mie_walker_step(out);
 	}
 
 	return out;
@@ -274,74 +620,23 @@ struct mie_walker *mie_walker_begin(struct mie_op *op, enum mie_walker_flags fla
 
 void mie_walker_end(struct mie_walker *walker)
 {
-}
+	/* TODO */
-
-static struct walk_schedule_item *current_item(struct mie_walker *walker)
-{
-	b_queue_entry *top = b_queue_first(&walker->w_sched);
-	if (!top) {
-		return NULL;
-	}
-
-	return b_unbox(struct walk_schedule_item, top, i_entry);
-}
-
-static enum mie_status step(struct mie_walker *walker)
-{
-	struct walk_schedule_item *cur = current_item(walker);
-	if (!cur) {
-		return MIE_ERR_NO_DATA;
-	}
-
-	if (walker->w_flags & MIE_WALKER_F_RECURSIVE || cur->i_depth == 0) {
-		schedule_children(walker, cur);
-	}
-
-	b_queue_delete(&walker->w_sched, &cur->i_entry);
-	free(cur);
-
-	if (!current_item(walker)) {
-		return MIE_ERR_NO_DATA;
-	}
-
-	return MIE_SUCCESS;
 }
 
 enum mie_status mie_walker_step(struct mie_walker *walker)
 {
-	struct walk_schedule_item *cur = current_item(walker);
+	struct mie_walk_item *cur = current_item(walker);
+	bool ok = false;
+
 	do {
-		step(walker);
+		ok = step(walker);
 		cur = current_item(walker);
 	} while (cur && should_ignore_item(walker, cur));
 
 	return cur ? MIE_SUCCESS : MIE_ERR_NO_DATA;
 }
 
-struct mie_walker_item *mie_walker_get(struct mie_walker *walker)
+struct mie_walk_item *mie_walker_get(struct mie_walker *walker)
 {
-	struct walk_schedule_item *cur = current_item(walker);
+	return current_item(walker);
-	if (!cur) {
-		return NULL;
-	}
-
-	memset(&walker->w_cur, 0x0, sizeof walker->w_cur);
-
-	walker->w_cur.i_depth = cur->i_depth;
-
-	switch (ITEM_TYPE(cur->i_flags)) {
-	case SCHED_ITEM_F_OP:
-		walker->w_cur.i_op = cur->i_op;
-		break;
-	case SCHED_ITEM_F_BLOCK:
-		walker->w_cur.i_block = cur->i_block;
-		break;
-	case SCHED_ITEM_F_REGION:
-		walker->w_cur.i_region = cur->i_region;
-		break;
-	default:
-		return NULL;
-	}
-
-	return &walker->w_cur;
 }

mie/parse/parser.c

@@ -837,8 +837,7 @@ bool mie_parser_parse_anonymous_block(
 {
 	mie_parser_parse_linefeed(ctx);
 
-	struct mie_op *op = mie_vector_emplace_back(block->b_ops, NULL);
+	struct mie_op *op = mie_block_add_op(block);
-	mie_op_init(op);
 
 	if (!mie_parser_parse_op(ctx, names, op)) {
 		return false;
@@ -855,8 +854,7 @@ bool mie_parser_parse_anonymous_block(
 			break;
 		}
 
-		struct mie_op *op = mie_vector_emplace_back(block->b_ops, NULL);
+		struct mie_op *op = mie_block_add_op(block);
-		mie_op_init(op);
 
 		if (!mie_parser_parse_op(ctx, names, op)) {
 			return false;
@@ -950,8 +948,7 @@ bool mie_parser_parse_block(
 			break;
 		}
 
-		struct mie_op *op = mie_vector_emplace_back(block->b_ops, NULL);
+		struct mie_op *op = mie_block_add_op(block);
-		mie_op_init(op);
 		if (!mie_parser_parse_op(ctx, names, op)) {
 			return false;
 		}
@@ -1150,9 +1147,6 @@ static bool parse_graph_op(
 bool mie_parser_parse_op(
 	struct mie_parser *ctx, struct mie_name_map *names, struct mie_op *dest)
 {
-	memset(dest, 0x0, sizeof *dest);
-	mie_attribute_map_init(&dest->op_attrib);
-
 	if (mie_parser_check_eof(ctx)) {
 		return false;
 	}

mie/pass/pass-manager.c

@@ -87,18 +87,19 @@ enum mie_status mie_pass_manager_filter_op(
 		return MIE_SUCCESS;
 	}
 
-	if (!dialect_name || !op_name) {
+	if (!dialect_name) {
 		return MIE_ERR_INVALID_ARGUMENT;
 	}
 
-	const struct mie_op_definition *op
+	if (!op_name) {
-		= mie_ctx_get_op_definition(pm->pm_ctx, dialect_name, op_name);
+		pm->pm_filter.f_dialect
-	if (!op) {
+			= mie_ctx_get_dialect(pm->pm_ctx, dialect_name);
-		return MIE_ERR_NO_ENTRY;
+		return pm->pm_filter.f_dialect ? MIE_SUCCESS : MIE_ERR_NO_ENTRY;
 	}
 
-	pm->pm_filter.f_op = op;
+	pm->pm_filter.f_op
-	return MIE_SUCCESS;
+		= mie_ctx_get_op_definition(pm->pm_ctx, dialect_name, op_name);
+	return pm->pm_filter.f_op ? MIE_SUCCESS : MIE_ERR_NO_ENTRY;
 }
 
 enum mie_status mie_pass_manager_filter_trait(
@@ -152,6 +153,10 @@ static bool filter_check_op(
 		return false;
 	}
 
+	if (filter->f_dialect && op->op_dialect != filter->f_dialect) {
+		return false;
+	}
+
 	if (filter->f_trait
 	    && !mie_op_has_trait(
 		    op, filter->f_trait->tr_parent->d_name,
@@ -203,7 +208,7 @@ static void schedule_passes(
 	while (mie_walker_step(walker) == MIE_SUCCESS) {
 		for (size_t i = 0; i < MIE_VECTOR_COUNT(pm->pm_nested); i++) {
 			struct mie_pass_manager *nested = pm->pm_nested.items[i];
-			struct mie_walker_item *item = mie_walker_get(walker);
+			struct mie_walk_item *item = mie_walker_get(walker);
 			schedule_passes(nested, schedule, item->i_op, depth + 1);
 		}
 	}

mie/trait/trait-table.c

@@ -106,7 +106,7 @@ const struct mie_trait *mie_trait_table_get_unique(
 
 	const mie_id *result = mie_id_map_get(&table->tr_unique, &id);
 	const struct unique_trait *entry
-		= b_unbox(struct unique_trait, entry, u_id);
+		= b_unbox(struct unique_trait, result, u_id);
 	return entry ? entry->u_trait : NULL;
 }