ir.c

/*
 * IR - Lightweight JIT Compilation Framework
 * (IR construction, folding, utilities)
 * This file is part of the IR Project distributed under the MIT-style LICENSE.
 * Authors: Dmitry Stogov <dmitry@php.net>
 *
 * The logical IR representation is based on Cliff Click's Sea of Nodes.
 * See: C. Click, M. Paleczny. "A Simple Graph-Based Intermediate
 * Representation" In ACM SIGPLAN Workshop on Intermediate Representations
 * (IR '95), pages 35-49, Jan. 1995.
 *
 * The physical IR representation is based on Mike Pall's LuaJIT IR.
 * See: M. Pall. "LuaJIT 2.0 intellectual property disclosure and research
 * opportunities" November 2009 http://lua-users.org/lists/lua-l/2009-11/msg00089.html
 */

#ifndef _GNU_SOURCE
# define _GNU_SOURCE
#endif

#ifndef _WIN32
# include <sys/mman.h>
# if defined(__linux__) || defined(__sun)
#  include <alloca.h>
# endif
# if defined(__APPLE__) && defined(__aarch64__)
#  include <libkern/OSCacheControl.h>
# endif
#else
# define WIN32_LEAN_AND_MEAN
# include <windows.h>
#endif

#include "ir.h"
#include "ir_private.h"

#include <stddef.h>
#include <stdlib.h>
#include <math.h>

#ifdef HAVE_VALGRIND
# include <valgrind/valgrind.h>
#endif

#define IR_TYPE_FLAGS(name, type, field, flags) (flags),
#define IR_TYPE_NAME(name, type, field, flags)  #name,
#define IR_TYPE_CNAME(name, type, field, flags) #type,
#define IR_TYPE_SIZE(name, type, field, flags)  sizeof(type),
#define IR_OP_NAME(name, flags, op1, op2, op3)  #name,

const uint8_t ir_type_flags[IR_LAST_TYPE] = {
	0,
	IR_TYPES(IR_TYPE_FLAGS)
};

const char *ir_type_name[IR_LAST_TYPE] = {
	"void",
	IR_TYPES(IR_TYPE_NAME)
};

const uint8_t ir_type_size[IR_LAST_TYPE] = {
	0,
	IR_TYPES(IR_TYPE_SIZE)
};

const char *ir_type_cname[IR_LAST_TYPE] = {
	"void",
	IR_TYPES(IR_TYPE_CNAME)
};

const char *ir_op_name[IR_LAST_OP] = {
	IR_OPS(IR_OP_NAME)
#ifdef IR_PHP
	IR_PHP_OPS(IR_OP_NAME)
#endif
};

void ir_print_escaped_str(const char *s, size_t len, FILE *f)
{
	char ch;

	while (len > 0) {
		ch = *s;
		switch (ch) {
			case '\\': fputs("\\\\", f); break;
			case '\'': fputs("'", f); break;
			case '\"': fputs("\\\"", f); break;
			case '\a': fputs("\\a", f); break;
			case '\b': fputs("\\b", f); break;
			case '\033': fputs("\\e", f); break;
			case '\f': fputs("\\f", f); break;
			case '\n': fputs("\\n", f); break;
			case '\r': fputs("\\r", f); break;
			case '\t': fputs("\\t", f); break;
			case '\v': fputs("\\v", f); break;
			case '\?': fputs("\\?", f); break;
			default:
#ifdef __aarch64__
				if (ch < 32) {
#else
				if (ch >= 0 && ch < 32) {
#endif
					fprintf(f, "\\%c%c%c",
						'0' + ((ch >> 6) % 8),
						'0' + ((ch >> 3) % 8),
						'0' + (ch % 8));
					break;
				} else {
					fputc(ch, f);
				}
		}
		s++;
		len--;
	}
}

static void ir_print_double(double v, FILE *f)
{
	char buf[128];

	if (isnan(v)) {
		union {
			double d;
			long long i;
		} u1, u2, u3;
		u1.d = v;
		u2.d = NAN;
		u3.d = -NAN;
		if (u1.i == u2.i) {
			fprintf(f, "nan");
		} else if (u1.i == u3.i) {
			fprintf(f, "-nan");
		} else {
			fprintf(f, "nan(0x%llx)", u1.i);
		}
	} else {
		snprintf(buf, sizeof(buf), "%g", v);
		if (strtod(buf, NULL) != v) {
			snprintf(buf, sizeof(buf), "%.53e", v);
			if (strtod(buf, NULL) != v) {
				IR_ASSERT(0 && "can't format double");
			}
		}
		fprintf(f, "%s", buf);
	}
}

static void ir_print_float(float v, FILE *f)
{
	char buf[128];

	if (isnan(v)) {
		union {
			float f;
			int i;
		} u1, u2, u3;
		u1.f = v;
		u2.f = NAN;
		u3.f = -NAN;
		if (u1.i == u2.i) {
			fprintf(f, "nan");
		} else if (u1.i == u3.i) {
			fprintf(f, "-nan");
		} else {
			fprintf(f, "nan(0x%x)", u1.i);
		}
	} else {
		snprintf(buf, sizeof(buf), "%g", v);
		if (strtod(buf, NULL) != v) {
			snprintf(buf, sizeof(buf), "%.24e", v);
			if (strtod(buf, NULL) != v) {
				IR_ASSERT(0 && "can't format float");
			}
		}
		fprintf(f, "%s", buf);
	}
}

void ir_print_const(const ir_ctx *ctx, const ir_insn *insn, FILE *f, bool quoted)
{
	if (insn->op == IR_FUNC || insn->op == IR_SYM || insn->op == IR_LABEL) {
		fprintf(f, "%s", ir_get_str(ctx, insn->val.name));
		return;
	} else if (insn->op == IR_STR) {
		size_t len;
		const char *str = ir_get_strl(ctx, insn->val.str, &len);

		if (quoted) {
			fprintf(f, "\"");
			ir_print_escaped_str(str, len, f);
			fprintf(f, "\"");
		} else {
			ir_print_escaped_str(str, len, f);
		}
		return;
	}

	if (IR_IS_TYPE_VECTOR(insn->type)) {
		ir_type t = IR_VECTOR_BASE_TYPE(insn->type);
		uint32_t n = IR_VECTOR_LENGTH(insn->type);
		const void *p = insn + 1;

		fprintf(f, "{");
		switch (t) {
			case IR_I8:
			case IR_CHAR:
				fprintf(f, "%d", *(int8_t*)p);
				while (--n) {
					p = (char*)p + sizeof(int8_t);;
					fprintf(f, ", %d", *(int8_t*)p);
				}
				break;
			case IR_I16:
				fprintf(f, "%d", *(int16_t*)p);
				while (--n) {
					p = (char*)p + sizeof(int16_t);
					fprintf(f, ", %d", *(int16_t*)p);
				}
				break;
			case IR_I32:
				fprintf(f, "%d", *(int32_t*)p);
				while (--n) {
					p = (char*)p + sizeof(int32_t);
					fprintf(f, ", %d", *(int32_t*)p);
				}
				break;
			case IR_I64:
				fprintf(f, "%" PRIi64, *(int64_t*)p);
				while (--n) {
					p = (char*)p + sizeof(int64_t);
					fprintf(f, ", %" PRIi64, *(int64_t*)p);
				}
				break;
			case IR_U8:
				fprintf(f, "%u", *(uint8_t*)p);
				while (--n) {
					p = (char*)p + sizeof(uint8_t);
					fprintf(f, ", %u", *(uint8_t*)p);
				}
				break;
			case IR_U16:
				fprintf(f, "%u", *(uint16_t*)p);
				while (--n) {
					p = (char*)p + sizeof(uint16_t);
					fprintf(f, ", %u", *(uint16_t*)p);
				}
				break;
			case IR_U32:
				fprintf(f, "%u", *(uint32_t*)p);
				while (--n) {
					p = (char*)p + sizeof(uint32_t);
					fprintf(f, ", %u", *(uint32_t*)p);
				}
				break;
			case IR_U64:
				fprintf(f, "%" PRIu64, *(uint64_t*)p);
				while (--n) {
					p = (char*)p + sizeof(uint64_t);
					fprintf(f, ", %" PRIu64, *(uint64_t*)p);
				}
				break;
			case IR_DOUBLE:
				ir_print_double(*(double*)p, f);
				while (--n) {
					p = (char*)p + sizeof(double);
					fprintf(f, ", ");
					ir_print_double(*(double*)p, f);
				}
				break;
			case IR_FLOAT:
				ir_print_float(*(float*)p, f);
				while (--n) {
					p = (char*)p + sizeof(float);
					fprintf(f, ", ");
					ir_print_float(*(float*)p, f);
				}
				break;
			default:
				IR_ASSERT(0);
				break;
		}
		fprintf(f, "}");
		return;
	}

	IR_ASSERT(IR_IS_CONST_OP(insn->op) || insn->op == IR_FUNC_ADDR);
	switch (insn->type) {
		case IR_BOOL:
			fprintf(f, "%u", insn->val.b);
			break;
		case IR_U8:
			fprintf(f, "%u", insn->val.u8);
			break;
		case IR_U16:
			fprintf(f, "%u", insn->val.u16);
			break;
		case IR_U32:
			fprintf(f, "%u", insn->val.u32);
			break;
		case IR_U64:
			fprintf(f, "%" PRIu64, insn->val.u64);
			break;
		case IR_ADDR:
			if (insn->val.addr) {
				fprintf(f, "0x%" PRIxPTR, insn->val.addr);
			} else {
				fprintf(f, "0");
			}
			break;
		case IR_CHAR:
			if (insn->val.c == '\\') {
				fprintf(f, "'\\\\'");
			} else if (insn->val.c == '\'') {
				fprintf(f, "'\\\''");
			} else if (insn->val.c >= ' ') {
				fprintf(f, "'%c'", insn->val.c);
			} else if (insn->val.c == '\t') {
				fprintf(f, "'\\t'");
			} else if (insn->val.c == '\r') {
				fprintf(f, "'\\r'");
			} else if (insn->val.c == '\n') {
				fprintf(f, "'\\n'");
			} else if (insn->val.c == '\0') {
				fprintf(f, "'\\0'");
			} else {
				fprintf(f, "%u", (unsigned char)insn->val.c);
			}
			break;
		case IR_I8:
			fprintf(f, "%d", insn->val.i8);
			break;
		case IR_I16:
			fprintf(f, "%d", insn->val.i16);
			break;
		case IR_I32:
			fprintf(f, "%d", insn->val.i32);
			break;
		case IR_I64:
			fprintf(f, "%" PRIi64, insn->val.i64);
			break;
		case IR_DOUBLE:
			ir_print_double(insn->val.d, f);
			break;
		case IR_FLOAT:
			ir_print_float(insn->val.f, f);
			break;
		default:
			IR_ASSERT(0);
			break;
	}
}

#define ir_op_flag_v       0
#define ir_op_flag_v0X3    (0 | (3 << IR_OP_FLAG_OPERANDS_SHIFT))
#define ir_op_flag_d       IR_OP_FLAG_DATA
#define ir_op_flag_d0      ir_op_flag_d
#define ir_op_flag_d1      (ir_op_flag_d | 1 | (1 << IR_OP_FLAG_OPERANDS_SHIFT))
#define ir_op_flag_d1X1    (ir_op_flag_d | 1 | (2 << IR_OP_FLAG_OPERANDS_SHIFT))
#define ir_op_flag_d1X2    (ir_op_flag_d | 1 | (3 << IR_OP_FLAG_OPERANDS_SHIFT))
#define ir_op_flag_d2      (ir_op_flag_d | 2 | (2 << IR_OP_FLAG_OPERANDS_SHIFT))
#define ir_op_flag_d2C     (ir_op_flag_d | IR_OP_FLAG_COMMUTATIVE | 2 | (2 << IR_OP_FLAG_OPERANDS_SHIFT))
#define ir_op_flag_d3      (ir_op_flag_d | 3 | (3 << IR_OP_FLAG_OPERANDS_SHIFT))
#define ir_op_flag_r       IR_OP_FLAG_DATA                                         // "d" and "r" are the same now
#define ir_op_flag_r0      ir_op_flag_r
#define ir_op_flag_p       (IR_OP_FLAG_DATA | IR_OP_FLAG_PINNED)
#define ir_op_flag_p1      (ir_op_flag_p | 1 | (1 << IR_OP_FLAG_OPERANDS_SHIFT))
#define ir_op_flag_p1X1    (ir_op_flag_p | 1 | (2 << IR_OP_FLAG_OPERANDS_SHIFT))
#define ir_op_flag_p1X2    (ir_op_flag_p | 1 | (3 << IR_OP_FLAG_OPERANDS_SHIFT))
#define ir_op_flag_p2      (ir_op_flag_p | 2 | (2 << IR_OP_FLAG_OPERANDS_SHIFT))
#define ir_op_flag_pN      (ir_op_flag_p | IR_OP_FLAG_VAR_INPUTS)
#define ir_op_flag_c       IR_OP_FLAG_CONTROL
#define ir_op_flag_c1X2    (ir_op_flag_c | 1 | (3 << IR_OP_FLAG_OPERANDS_SHIFT))
#define ir_op_flag_c3      (ir_op_flag_c | 3 | (3 << IR_OP_FLAG_OPERANDS_SHIFT))
#define ir_op_flag_S       (IR_OP_FLAG_CONTROL|IR_OP_FLAG_BB_START)
#define ir_op_flag_S0X1    (ir_op_flag_S | 0 | (1 << IR_OP_FLAG_OPERANDS_SHIFT))
#define ir_op_flag_S1      (ir_op_flag_S | 1 | (1 << IR_OP_FLAG_OPERANDS_SHIFT))
#define ir_op_flag_S1X1    (ir_op_flag_S | 1 | (2 << IR_OP_FLAG_OPERANDS_SHIFT))
#define ir_op_flag_S2      (ir_op_flag_S | 2 | (2 << IR_OP_FLAG_OPERANDS_SHIFT))
#define ir_op_flag_S2X1    (ir_op_flag_S | 2 | (3 << IR_OP_FLAG_OPERANDS_SHIFT))
#define ir_op_flag_S3      (ir_op_flag_S | 3 | (3 << IR_OP_FLAG_OPERANDS_SHIFT))
#define ir_op_flag_SN      (ir_op_flag_S | IR_OP_FLAG_VAR_INPUTS)
#define ir_op_flag_E       (IR_OP_FLAG_CONTROL|IR_OP_FLAG_BB_END)
#define ir_op_flag_E1      (ir_op_flag_E | 1 | (1 << IR_OP_FLAG_OPERANDS_SHIFT))
#define ir_op_flag_E2      (ir_op_flag_E | 2 | (2 << IR_OP_FLAG_OPERANDS_SHIFT))
#define ir_op_flag_T       (IR_OP_FLAG_CONTROL|IR_OP_FLAG_BB_END|IR_OP_FLAG_TERMINATOR)
#define ir_op_flag_T2X1    (ir_op_flag_T | 2 | (3 << IR_OP_FLAG_OPERANDS_SHIFT))
#define ir_op_flag_T1X2    (ir_op_flag_T | 1 | (3 << IR_OP_FLAG_OPERANDS_SHIFT))
#define ir_op_flag_l       (IR_OP_FLAG_CONTROL|IR_OP_FLAG_MEM|IR_OP_FLAG_MEM_LOAD)
#define ir_op_flag_l0      ir_op_flag_l
#define ir_op_flag_l1      (ir_op_flag_l | 1 | (1 << IR_OP_FLAG_OPERANDS_SHIFT))
#define ir_op_flag_l1X1    (ir_op_flag_l | 1 | (2 << IR_OP_FLAG_OPERANDS_SHIFT))
#define ir_op_flag_l1X2    (ir_op_flag_l | 1 | (3 << IR_OP_FLAG_OPERANDS_SHIFT))
#define ir_op_flag_l2      (ir_op_flag_l | 2 | (2 << IR_OP_FLAG_OPERANDS_SHIFT))
#define ir_op_flag_l3      (ir_op_flag_l | 3 | (3 << IR_OP_FLAG_OPERANDS_SHIFT))
#define ir_op_flag_s       (IR_OP_FLAG_CONTROL|IR_OP_FLAG_MEM|IR_OP_FLAG_MEM_STORE)
#define ir_op_flag_s0      ir_op_flag_s
#define ir_op_flag_s1      (ir_op_flag_s | 1 | (1 << IR_OP_FLAG_OPERANDS_SHIFT))
#define ir_op_flag_s2      (ir_op_flag_s | 2 | (2 << IR_OP_FLAG_OPERANDS_SHIFT))
#define ir_op_flag_s2X1    (ir_op_flag_s | 2 | (3 << IR_OP_FLAG_OPERANDS_SHIFT))
#define ir_op_flag_s3      (ir_op_flag_s | 3 | (3 << IR_OP_FLAG_OPERANDS_SHIFT))
#define ir_op_flag_x1      (IR_OP_FLAG_CONTROL|IR_OP_FLAG_MEM|IR_OP_FLAG_MEM_CALL | 1 | (1 << IR_OP_FLAG_OPERANDS_SHIFT))
#define ir_op_flag_x2      (IR_OP_FLAG_CONTROL|IR_OP_FLAG_MEM|IR_OP_FLAG_MEM_CALL | 2 | (2 << IR_OP_FLAG_OPERANDS_SHIFT))
#define ir_op_flag_x2X1    (IR_OP_FLAG_CONTROL|IR_OP_FLAG_MEM|IR_OP_FLAG_MEM_CALL | 2 | (3 << IR_OP_FLAG_OPERANDS_SHIFT))
#define ir_op_flag_x3      (IR_OP_FLAG_CONTROL|IR_OP_FLAG_MEM|IR_OP_FLAG_MEM_CALL | 3 | (3 << IR_OP_FLAG_OPERANDS_SHIFT))
#define ir_op_flag_xN      (IR_OP_FLAG_CONTROL|IR_OP_FLAG_MEM|IR_OP_FLAG_MEM_CALL | IR_OP_FLAG_VAR_INPUTS)
#define ir_op_flag_a1      (IR_OP_FLAG_CONTROL|IR_OP_FLAG_MEM|IR_OP_FLAG_MEM_ALLOC | 1 | (1 << IR_OP_FLAG_OPERANDS_SHIFT))
#define ir_op_flag_a2      (IR_OP_FLAG_CONTROL|IR_OP_FLAG_MEM|IR_OP_FLAG_MEM_ALLOC | 2 | (2 << IR_OP_FLAG_OPERANDS_SHIFT))
#define ir_op_flag_a2X1    (IR_OP_FLAG_CONTROL|IR_OP_FLAG_MEM|IR_OP_FLAG_MEM_ALLOC | 2 | (3 << IR_OP_FLAG_OPERANDS_SHIFT))

#define ir_op_kind____     IR_OPND_UNUSED
#define ir_op_kind_def     IR_OPND_DATA
#define ir_op_kind_ref     IR_OPND_DATA
#define ir_op_kind_src     IR_OPND_CONTROL
#define ir_op_kind_reg     IR_OPND_CONTROL_DEP
#define ir_op_kind_ret     IR_OPND_CONTROL_REF
#define ir_op_kind_grd     IR_OPND_CONTROL_GUARD
#define ir_op_kind_str     IR_OPND_STR
#define ir_op_kind_num     IR_OPND_NUM
#define ir_op_kind_fld     IR_OPND_STR
#define ir_op_kind_var     IR_OPND_DATA
#define ir_op_kind_opt     IR_OPND_OPT
#define ir_op_kind_prb     IR_OPND_OPT
#define ir_op_kind_alg     IR_OPND_OPT
#define ir_op_kind_pro     IR_OPND_PROTO
#define ir_op_kind_lbl     IR_OPND_LABEL_REF

#define _IR_OP_FLAGS(name, flags, op1, op2, op3) \
	IR_OP_FLAGS(ir_op_flag_ ## flags, ir_op_kind_ ## op1, ir_op_kind_ ## op2, ir_op_kind_ ## op3),

const uint32_t ir_op_flags[IR_LAST_OP] = {
	IR_OPS(_IR_OP_FLAGS)
#ifdef IR_PHP
	IR_PHP_OPS(_IR_OP_FLAGS)
#endif
};

static void ir_grow_bottom(ir_ctx *ctx)
{
	ir_insn *buf = ctx->ir_base - ctx->consts_limit;
	ir_ref old_consts_limit = ctx->consts_limit;

	if (ctx->consts_limit < 1024 * 4) {
		ctx->consts_limit *= 2;
	} else if (ctx->consts_limit < 1024 * 4 * 2) {
		ctx->consts_limit = 1024 * 4 * 2;
	} else {
		ctx->consts_limit += 1024 * 4;
	}
	buf = ir_mem_realloc(buf, (ctx->consts_limit + ctx->insns_limit) * sizeof(ir_insn));
	memmove(buf + (ctx->consts_limit - old_consts_limit),
		buf,
		(old_consts_limit + ctx->insns_count) * sizeof(ir_insn));
	ctx->ir_base = buf + ctx->consts_limit;
}

static ir_ref ir_next_const(ir_ctx *ctx)
{
	ir_ref ref = ctx->consts_count;

	if (UNEXPECTED(ref >= ctx->consts_limit)) {
		ir_grow_bottom(ctx);
	}
	ctx->consts_count = ref + 1;
	return -ref;
}

static void ir_grow_top(ir_ctx *ctx)
{
	ir_ref old_insns_limit = ctx->insns_limit;
	ir_insn *buf = ctx->ir_base - ctx->consts_limit;

	if (ctx->insns_limit < 1024 * 4) {
		ctx->insns_limit *= 2;
	} else if (ctx->insns_limit < 1024 * 4 * 2) {
		ctx->insns_limit = 1024 * 4 * 2;
	} else {
		ctx->insns_limit += 1024 * 4;
	}
	buf = ir_mem_realloc(buf, (ctx->consts_limit + ctx->insns_limit) * sizeof(ir_insn));
	ctx->ir_base = buf + ctx->consts_limit;

	if (ctx->use_lists) {
		ctx->use_lists = ir_mem_realloc(ctx->use_lists, ctx->insns_limit * sizeof(ir_use_list));
		memset(ctx->use_lists + old_insns_limit, 0,
			(ctx->insns_limit - old_insns_limit) * sizeof(ir_use_list));
	}

	if (ctx->cfg_map) {
		ctx->cfg_map = ir_mem_realloc(ctx->cfg_map, ctx->insns_limit * sizeof(uint32_t));
		memset(ctx->cfg_map + old_insns_limit, 0,
			(ctx->insns_limit - old_insns_limit) * sizeof(uint32_t));
	}
}

static ir_ref ir_next_insn(ir_ctx *ctx)
{
	ir_ref ref = ctx->insns_count;

	if (UNEXPECTED(ref >= ctx->insns_limit)) {
		ir_grow_top(ctx);
	}
	ctx->insns_count = ref + 1;
	return ref;
}

void ir_truncate(ir_ctx *ctx)
{
	ir_insn *buf = ir_mem_malloc((ctx->consts_count + ctx->insns_count) * sizeof(ir_insn));

	memcpy(buf, ctx->ir_base - ctx->consts_count, (ctx->consts_count + ctx->insns_count) * sizeof(ir_insn));
	ir_mem_free(ctx->ir_base - ctx->consts_limit);
	ctx->insns_limit = ctx->insns_count;
	ctx->consts_limit = ctx->consts_count;
	ctx->ir_base = buf + ctx->consts_limit;
}

void ir_init(ir_ctx *ctx, uint32_t flags, ir_ref consts_limit, ir_ref insns_limit)
{
	ir_insn *buf;

	IR_ASSERT(consts_limit >= IR_CONSTS_LIMIT_MIN);
	IR_ASSERT(insns_limit >= IR_INSNS_LIMIT_MIN);

	memset(ctx, 0, sizeof(ir_ctx));

	ctx->insns_count = IR_UNUSED + 1;
	ctx->insns_limit = insns_limit;
	ctx->consts_count = -(IR_TRUE - 1);
	ctx->consts_limit = consts_limit;
	ctx->const_hash = ctx->_const_hash;
	ctx->const_hash_mask = IR_CONST_HASH_SIZE - 1;
	ctx->fold_cse_limit = IR_UNUSED + 1;
	ctx->flags = flags;

	ctx->spill_base = -1;
	ctx->fixed_stack_frame_size = -1;

	buf = ir_mem_malloc((consts_limit + insns_limit) * sizeof(ir_insn));
	ctx->ir_base = buf + consts_limit;

	MAKE_NOP(&ctx->ir_base[IR_UNUSED]);
	ctx->ir_base[IR_NULL].optx = IR_OPT(IR_C_ADDR, IR_ADDR);
	ctx->ir_base[IR_NULL].val.u64 = 0;
	ctx->ir_base[IR_FALSE].optx = IR_OPT(IR_C_BOOL, IR_BOOL);
	ctx->ir_base[IR_FALSE].val.u64 = 0;
	ctx->ir_base[IR_TRUE].optx = IR_OPT(IR_C_BOOL, IR_BOOL);
	ctx->ir_base[IR_TRUE].val.u64 = 1;
}

void ir_free(ir_ctx *ctx)
{
	ir_insn *buf = ctx->ir_base - ctx->consts_limit;
	ir_mem_free(buf);
	if (ctx->value_params) {
		ir_mem_free(ctx->value_params);
	}
	if (ctx->strtab.data) {
		ir_strtab_free(&ctx->strtab);
	}
	if (ctx->binding) {
		ir_hashtab_free(ctx->binding);
		ir_mem_free(ctx->binding);
	}
	if (ctx->use_lists) {
		ir_mem_free(ctx->use_lists);
	}
	if (ctx->use_edges) {
		ir_mem_free(ctx->use_edges);
	}
	if (ctx->cfg_blocks) {
		ir_mem_free(ctx->cfg_blocks);
	}
	if (ctx->cfg_edges) {
		ir_mem_free(ctx->cfg_edges);
	}
	if (ctx->cfg_map) {
		ir_mem_free(ctx->cfg_map);
	}
	if (ctx->cfg_schedule) {
		ir_mem_free(ctx->cfg_schedule);
	}
	if (ctx->rules) {
		ir_mem_free(ctx->rules);
	}
	if (ctx->vregs) {
		ir_mem_free(ctx->vregs);
	}
	if (ctx->live_intervals) {
		ir_mem_free(ctx->live_intervals);
	}
	if (ctx->arena) {
		ir_arena_free(ctx->arena);
	}
	if (ctx->regs) {
		ir_mem_free(ctx->regs);
		if (ctx->tmp_regs) {
			ir_mem_free(ctx->tmp_regs);
		}
		if (ctx->fused_regs) {
			ir_strtab_free(ctx->fused_regs);
			ir_mem_free(ctx->fused_regs);
		}
	}
	if (ctx->prev_ref) {
		ir_mem_free(ctx->prev_ref);
	}
	if (ctx->entries) {
		ir_mem_free(ctx->entries);
	}
	if (ctx->osr_entry_loads) {
		ir_list_free((ir_list*)ctx->osr_entry_loads);
		ir_mem_free(ctx->osr_entry_loads);
	}

	if (ctx->const_hash_mask != IR_CONST_HASH_SIZE - 1) {
		ir_mem_free(ctx->const_hash);
	}
}

ir_ref ir_unique_const_addr(ir_ctx *ctx, uintptr_t addr)
{
	ir_ref ref = ir_next_const(ctx);
	ir_insn *insn = &ctx->ir_base[ref];

	insn->optx = IR_OPT(IR_ADDR, IR_ADDR);
	insn->val.u64 = addr;
	/* don't insert into constants chain */
	insn->prev_const = IR_UNUSED;

	return ref;
}

IR_ALWAYS_INLINE uintptr_t ir_const_hash(ir_val val, uint32_t optx)
{
	return (uintptr_t)(val.u64 ^ (val.u64 >> 32) ^ optx);
}

static IR_NEVER_INLINE void ir_const_hash_rehash(ir_ctx *ctx)
{
	ir_insn *insn;
	ir_ref ref;
	uintptr_t hash;

	if (ctx->const_hash_mask != IR_CONST_HASH_SIZE - 1) {
		ir_mem_free(ctx->const_hash);
	}
	ctx->const_hash_mask = (ctx->const_hash_mask + 1) * 2 - 1;
	ctx->const_hash = ir_mem_calloc(ctx->const_hash_mask + 1, sizeof(ir_ref));
	for (ref = 1 - ctx->consts_count, insn = ctx->ir_base + ref; ref < IR_TRUE; ref++, insn++) {
		if (insn->op == IR_LONG_CONST) {
			hash = insn->val.addr;
			insn->prev_const = ctx->const_hash[hash & ctx->const_hash_mask];
			ctx->const_hash[hash & ctx->const_hash_mask] = ref;
			ref += IR_ALIGNED_SIZE(insn->long_const_size, sizeof(ir_insn)) / sizeof(ir_insn);
			insn += IR_ALIGNED_SIZE(insn->long_const_size, sizeof(ir_insn)) / sizeof(ir_insn);
		} else {
			hash = ir_const_hash(insn->val, insn->optx) & ctx->const_hash_mask;
			insn->prev_const = ctx->const_hash[hash];
			ctx->const_hash[hash] = ref;
		}
	}
}

#ifdef IR_DEBUG
/* Narrow integer constants are kept sign/zero extended to 64 bits, FLOAT has zero upper half */
static bool ir_const_is_canonical(ir_val val, uint8_t type)
{
	uint32_t shift;

	if (type == IR_FLOAT) {
		return val.u32_hi == 0;
	}
	if (!IR_IS_TYPE_INT(type) || ir_type_size[type] == 8) {
		return 1;
	}
	shift = (8 - ir_type_size[type]) * 8;
	if (IR_IS_TYPE_SIGNED(type)) {
		return val.i64 == (int64_t)(val.u64 << shift) >> shift;
	}
	return val.u64 == (val.u64 << shift) >> shift;
}
#endif

ir_ref ir_const_ex(ir_ctx *ctx, ir_val val, uint8_t type, uint32_t optx)
{
	ir_insn *insn;
	ir_ref ref, prev;
	uintptr_t hash;

	if (type == IR_BOOL) {
		return val.u64 ? IR_TRUE : IR_FALSE;
	} else if (type == IR_ADDR && val.u64 == 0) {
		return IR_NULL;
	}

	IR_ASSERT(IR_IS_SYM_CONST(optx & IR_OPT_OP_MASK) || ir_const_is_canonical(val, type));

	hash = ir_const_hash(val, optx) & ctx->const_hash_mask;
	ref = ctx->const_hash[hash];
	while (ref) {
		insn = &ctx->ir_base[ref];
		if (insn->val.u64 == val.u64 && insn->optx == optx) {
			return ref;
		}
		ref = insn->prev_const;
	}

	if ((uintptr_t)ctx->consts_count > ctx->const_hash_mask) {
		ir_const_hash_rehash(ctx);
		hash = ir_const_hash(val, optx) & ctx->const_hash_mask;
	}

	prev = ctx->const_hash[hash];
	ctx->const_hash[hash] = -ctx->consts_count;

	ref = ir_next_const(ctx);
	insn = &ctx->ir_base[ref];
	insn->prev_const = prev;

	insn->optx = optx;
	insn->val.u64 = val.u64;

	return ref;
}

ir_ref ir_const(ir_ctx *ctx, ir_val val, uint8_t type)
{
	return ir_const_ex(ctx, val, type, IR_OPT(type, type));
}

ir_ref ir_const_i8(ir_ctx *ctx, int8_t c)
{
	ir_val val;
	val.i64 = c;
	return ir_const(ctx, val, IR_I8);
}

ir_ref ir_const_i16(ir_ctx *ctx, int16_t c)
{
	ir_val val;
	val.i64 = c;
	return ir_const(ctx, val, IR_I16);
}

ir_ref ir_const_i32(ir_ctx *ctx, int32_t c)
{
	ir_val val;
	val.i64 = c;
	return ir_const(ctx, val, IR_I32);
}

ir_ref ir_const_i64(ir_ctx *ctx, int64_t c)
{
	ir_val val;
	val.i64 = c;
	return ir_const(ctx, val, IR_I64);
}

ir_ref ir_const_u8(ir_ctx *ctx, uint8_t c)
{
	ir_val val;
	val.u64 = c;
	return ir_const(ctx, val, IR_U8);
}

ir_ref ir_const_u16(ir_ctx *ctx, uint16_t c)
{
	ir_val val;
	val.u64 = c;
	return ir_const(ctx, val, IR_U16);
}

ir_ref ir_const_u32(ir_ctx *ctx, uint32_t c)
{
	ir_val val;
	val.u64 = c;
	return ir_const(ctx, val, IR_U32);
}

ir_ref ir_const_u64(ir_ctx *ctx, uint64_t c)
{
	ir_val val;
	val.u64 = c;
	return ir_const(ctx, val, IR_U64);
}

ir_ref ir_const_bool(ir_ctx *ctx, bool c)
{
	return (c) ? IR_TRUE : IR_FALSE;
}

ir_ref ir_const_char(ir_ctx *ctx, char c)
{
	ir_val val;
	val.i64 = (signed char)c;
	return ir_const(ctx, val, IR_CHAR);
}

ir_ref ir_const_float(ir_ctx *ctx, float c)
{
	ir_val val;
	val.u32_hi = 0;
	val.f = c;
	return ir_const(ctx, val, IR_FLOAT);
}

ir_ref ir_const_double(ir_ctx *ctx, double c)
{
	ir_val val;
	val.d = c;
	return ir_const(ctx, val, IR_DOUBLE);
}

ir_ref ir_const_addr(ir_ctx *ctx, uintptr_t c)
{
	if (c == 0) {
		return IR_NULL;
	}
	ir_val val;
	val.u64 = c;
	return ir_const(ctx, val, IR_ADDR);
}

ir_ref ir_const_func_addr(ir_ctx *ctx, uintptr_t c, ir_str proto)
{
	if (c == 0) {
		return IR_NULL;
	}
	ir_val val;
	val.u64 = c;
	IR_ASSERT(proto >= 0 && proto < 0xffff);
	return ir_const_ex(ctx, val, IR_ADDR, IR_OPTX(IR_FUNC_ADDR, IR_ADDR, proto));
}

ir_ref ir_const_func(ir_ctx *ctx, ir_str str, ir_str proto)
{
	ir_val val;
	val.u64 = str;
	IR_ASSERT(proto >= 0 && proto < 0xffff);
	return ir_const_ex(ctx, val, IR_ADDR, IR_OPTX(IR_FUNC, IR_ADDR, proto));
}

ir_ref ir_const_sym(ir_ctx *ctx, ir_str str)
{
	ir_val val;
	val.u64 = str;
	return ir_const_ex(ctx, val, IR_ADDR, IR_OPTX(IR_SYM, IR_ADDR, 0));
}

ir_ref ir_const_str(ir_ctx *ctx, ir_str str)
{
	ir_val val;
	val.u64 = str;
	return ir_const_ex(ctx, val, IR_ADDR, IR_OPTX(IR_STR, IR_ADDR, 0));
}

ir_ref ir_const_label(ir_ctx *ctx, ir_str str)
{
	ir_val val;
	val.u64 = str;
	return ir_const_ex(ctx, val, IR_ADDR, IR_OPTX(IR_LABEL, IR_ADDR, 0));
}

ir_ref ir_long_const(ir_ctx *ctx, ir_type type, size_t size)
{
	ir_ref ref = ctx->consts_count;
	ir_insn *insn;

	IR_ASSERT(size <= 0xfff0);

	ref = ctx->consts_count + IR_ALIGNED_SIZE(size, sizeof(ir_insn)) / sizeof(ir_insn);
	while (UNEXPECTED(ref >= ctx->consts_limit)) {
		ir_grow_bottom(ctx);
	}
	ctx->consts_count = ref + 1;
	ref = -ref;

	insn = &ctx->ir_base[ref];
	insn->optx = IR_OPTX(IR_LONG_CONST, type, size);
	insn->op1 = IR_UNUSED;
	insn->val.u64 = 0;

	ctx->flags2 |= IR_HAS_LONG_CONSTANTS;

	return ref;
}

void *ir_long_const_ptr(ir_ctx *ctx, ir_ref ref)
{
	IR_ASSERT(IR_IS_CONST_REF(ref));
	return (void*)&ctx->ir_base[ref + 1];
}

IR_ALWAYS_INLINE uintptr_t ir_long_const_hash(uint32_t optx, const void *ptr, size_t len)
{
	size_t i;
	const uint8_t *str = ptr;
	uint32_t h = 5381;

    for (i = 0; i < len; i++) {
        h = ((h << 5) + h) + *str;
        str++;
    }
	return (uintptr_t)(h ^ optx);
}

ir_ref ir_long_const_commit(ir_ctx *ctx, ir_ref const_ref)
{
	ir_ref ref;
	uintptr_t hash, n;
	ir_insn *insn = &ctx->ir_base[const_ref];
	uint32_t optx = insn->optx;
	size_t size = insn->long_const_size;
	const void *ptr = insn + 1;

	IR_ASSERT(ctx->consts_count == 1 - const_ref && "ir_long_const_commit() argument must be result of the last ir_long_const()");

	/* check if we already have the same constant */
	hash = ir_long_const_hash(optx, ptr, size);
	ref = ctx->const_hash[hash & ctx->const_hash_mask];
	while (ref) {
		insn = &ctx->ir_base[ref];
		if (insn->val.u64 == hash && insn->optx == optx && memcmp(ptr, insn + 1, size) == 0) {
			/* rollback */
			ctx->consts_count -= (IR_ALIGNED_SIZE(size, sizeof(ir_insn)) / sizeof(ir_insn)) + 1;
			return ref;
		}
		ref = insn->prev_const;
	}

	if ((uintptr_t)ctx->consts_count > ctx->const_hash_mask) {
		ir_const_hash_rehash(ctx);
	}

	n = hash & ctx->const_hash_mask;
	insn = &ctx->ir_base[const_ref];
	insn->prev_const = ctx->const_hash[n];
	insn->val.u64 = hash;
	ctx->const_hash[n] = const_ref;

	return const_ref;
}

ir_ref ir_const_vector(ir_ctx *ctx, ir_type type)
{
	IR_ASSERT(IR_IS_TYPE_VECTOR(type));
	return ir_long_const(ctx, type, IR_VECTOR_SIZE(type));
}

ir_str ir_string(ir_ctx *ctx, const char *s)
{
	size_t len;

	if (!ctx->strtab.data) {
		ir_strtab_init(&ctx->strtab, 64, 4096);
	}
	len = strlen(s);
	IR_ASSERT(len <= 0xffffffff);
	return ir_strtab_lookup(&ctx->strtab, s, (uint32_t)len, ir_strtab_count(&ctx->strtab) + 1);
}

ir_str ir_stringl(ir_ctx *ctx, const char *s, size_t len)
{
	if (!ctx->strtab.data) {
		ir_strtab_init(&ctx->strtab, 64, 4096);
	}
	IR_ASSERT(len <= 0xffffffff);
	return ir_strtab_lookup(&ctx->strtab, s, (uint32_t)len, ir_strtab_count(&ctx->strtab) + 1);
}

const char *ir_get_str(const ir_ctx *ctx, ir_str idx)
{
	if (IR_IS_EXT_STR(idx)) {
		return ctx->loader->get_str(ctx->loader, idx);
	}
	IR_ASSERT(ctx->strtab.data);
	return ir_strtab_str(&ctx->strtab, idx - 1);
}

const char *ir_get_strl(const ir_ctx *ctx, ir_str idx, size_t *len)
{
	if (IR_IS_EXT_STR(idx)) {
		return ctx->loader->get_strl(ctx->loader, idx, len);
	}
	IR_ASSERT(ctx->strtab.data);
	return ir_strtab_strl(&ctx->strtab, idx - 1, len);
}

ir_str ir_proto_0(ir_ctx *ctx, uint8_t flags, ir_type ret_type)
{
	ir_proto_t proto;

	proto.flags = flags;
	proto.ret_type = ret_type;
	proto.params_count = 0;
	return ir_stringl(ctx, (const char *)&proto, offsetof(ir_proto_t, param_types) + 0);
}

ir_str ir_proto_1(ir_ctx *ctx, uint8_t flags, ir_type ret_type, ir_type t1)
{
	ir_proto_t proto;

	proto.flags = flags;
	proto.ret_type = ret_type;
	proto.params_count = 1;
	proto.param_types[0] = t1;
	return ir_stringl(ctx, (const char *)&proto, offsetof(ir_proto_t, param_types) + 1);
}

ir_str ir_proto_2(ir_ctx *ctx, uint8_t flags, ir_type ret_type, ir_type t1, ir_type t2)
{
	ir_proto_t proto;

	proto.flags = flags;
	proto.ret_type = ret_type;
	proto.params_count = 2;
	proto.param_types[0] = t1;
	proto.param_types[1] = t2;
	return ir_stringl(ctx, (const char *)&proto, offsetof(ir_proto_t, param_types) + 2);
}

ir_str ir_proto_3(ir_ctx *ctx, uint8_t flags, ir_type ret_type, ir_type t1, ir_type t2, ir_type t3)
{
	ir_proto_t proto;

	proto.flags = flags;
	proto.ret_type = ret_type;
	proto.params_count = 3;
	proto.param_types[0] = t1;
	proto.param_types[1] = t2;
	proto.param_types[2] = t3;
	return ir_stringl(ctx, (const char *)&proto, offsetof(ir_proto_t, param_types) + 3);
}

ir_str ir_proto_4(ir_ctx *ctx, uint8_t flags, ir_type ret_type, ir_type t1, ir_type t2, ir_type t3,
                                                                ir_type t4)
{
	ir_proto_t proto;

	proto.flags = flags;
	proto.ret_type = ret_type;
	proto.params_count = 4;
	proto.param_types[0] = t1;
	proto.param_types[1] = t2;
	proto.param_types[2] = t3;
	proto.param_types[3] = t4;
	return ir_stringl(ctx, (const char *)&proto, offsetof(ir_proto_t, param_types) + 4);
}

ir_str ir_proto_5(ir_ctx *ctx, uint8_t flags, ir_type ret_type, ir_type t1, ir_type t2, ir_type t3,
                                                                ir_type t4, ir_type t5)
{
	ir_proto_t proto;

	proto.flags = flags;
	proto.ret_type = ret_type;
	proto.params_count = 5;
	proto.param_types[0] = t1;
	proto.param_types[1] = t2;
	proto.param_types[2] = t3;
	proto.param_types[3] = t4;
	proto.param_types[4] = t5;
	return ir_stringl(ctx, (const char *)&proto, offsetof(ir_proto_t, param_types) + 5);
}

ir_str ir_proto(ir_ctx *ctx, uint8_t flags, ir_type ret_type, uint32_t params_count, uint8_t *param_types)
{
	ir_proto_t *proto = alloca(offsetof(ir_proto_t, param_types) + params_count);

	IR_ASSERT(params_count <= IR_MAX_PROTO_PARAMS);
	proto->flags = flags;
	proto->ret_type = ret_type;
	proto->params_count = params_count;
	if (params_count) {
		memcpy(proto->param_types, param_types, params_count);
	}
	return ir_stringl(ctx, (const char *)proto, offsetof(ir_proto_t, param_types) + params_count);
}

/* IR construction */
ir_ref ir_emit(ir_ctx *ctx, uint32_t opt, ir_ref op1, ir_ref op2, ir_ref op3)
{
	ir_ref   ref = ir_next_insn(ctx);
	ir_insn *insn = &ctx->ir_base[ref];

	insn->optx = opt;
	insn->op1 = op1;
	insn->op2 = op2;
	insn->op3 = op3;

	return ref;
}

ir_ref ir_emit0(ir_ctx *ctx, uint32_t opt)
{
	return ir_emit(ctx, opt, IR_UNUSED, IR_UNUSED, IR_UNUSED);
}

ir_ref ir_emit1(ir_ctx *ctx, uint32_t opt, ir_ref op1)
{
	return ir_emit(ctx, opt, op1, IR_UNUSED, IR_UNUSED);
}

ir_ref ir_emit2(ir_ctx *ctx, uint32_t opt, ir_ref op1, ir_ref op2)
{
	return ir_emit(ctx, opt, op1, op2, IR_UNUSED);
}

ir_ref ir_emit3(ir_ctx *ctx, uint32_t opt, ir_ref op1, ir_ref op2, ir_ref op3)
{
	return ir_emit(ctx, opt, op1, op2, op3);
}

static ir_ref _ir_fold_cse(ir_ctx *ctx, uint32_t opt, ir_ref op1, ir_ref op2, ir_ref op3)
{
	ir_ref ref = ctx->prev_insn_chain[opt & IR_OPT_OP_MASK];
	const ir_insn *insn;

	if (ref) {
		ir_ref limit = ctx->fold_cse_limit;

		if (op1 > limit) {
			limit = op1;
		}
		if (op2 > limit) {
			limit = op2;
		}
		if (op3 > limit) {
			limit = op3;
		}
		while (ref >= limit) {
			insn = &ctx->ir_base[ref];
			if (insn->opt == opt && insn->op1 == op1 && insn->op2 == op2 && insn->op3 == op3) {
				return ref;
			}
			if (!insn->prev_insn_offset) {
				break;
			}
			ref = ref - (ir_ref)(uint32_t)insn->prev_insn_offset;
		}
	}

	return IR_UNUSED;
}

IR_ALWAYS_INLINE ir_ref _ir_fold_cast(ir_ctx *ctx, ir_ref ref, ir_type type)
{
	if (ctx->ir_base[ref].type == type) {
		return ref;
	} else if (IR_IS_CONST_REF(ref) && !IR_IS_SYM_CONST(ctx->ir_base[ref].op)) {
		return ir_const(ctx, ctx->ir_base[ref].val, type);
	} else if (EXPECTED(!ctx->use_lists)) {
		return ir_emit1(ctx, IR_OPT(IR_BITCAST, type), ref);
	} else {
		ir_ref ret = ir_emit1(ctx, IR_OPTX(IR_BITCAST, type, 1), ref);
		ir_use_list_add(ctx, ref, ret);
		return ret;
	}
}

#define IR_FOLD(X)        IR_FOLD1(X, __LINE__)
#define IR_FOLD1(X, Y)    IR_FOLD2(X, Y)
#define IR_FOLD2(X, Y)    case IR_RULE_ ## Y:

#define IR_FOLD_ERROR(msg) do { \
		IR_ASSERT(0 && (msg)); \
		goto ir_fold_emit; \
	} while (0)

#define IR_FOLD_CONST_U(_val) do { \
		val.u64 = (_val); \
		goto ir_fold_const; \
	} while (0)

#define IR_FOLD_CONST_I(_val) do { \
		val.i64 = (_val); \
		goto ir_fold_const; \
	} while (0)

#define IR_FOLD_CONST_D(_val) do { \
		val.d = (_val); \
		goto ir_fold_const; \
	} while (0)

#define IR_FOLD_CONST_F(_val) do { \
		val.f = (_val); \
		val.u32_hi = 0; \
		goto ir_fold_const; \
	} while (0)

#define IR_FOLD_COPY(op)  do { \
		ref = (op); \
		goto ir_fold_copy; \
	} while (0)

#define IR_FOLD_BOOL(cond) \
	IR_FOLD_COPY((cond) ? IR_TRUE : IR_FALSE)

#define IR_FOLD_NAMED(name)    ir_fold_ ## name:
#define IR_FOLD_DO_NAMED(name) goto ir_fold_ ## name
#define IR_FOLD_RESTART        goto ir_fold_restart
#define IR_FOLD_CSE            goto ir_fold_cse
#define IR_FOLD_EMIT           goto ir_fold_emit
#define IR_FOLD_NEXT           break

#include <ir_fold_hash.h>

#define IR_FOLD_RULE(x) ((x) >> 21)
#define IR_FOLD_KEY(x)  ((x) & 0x1fffff)

/*
 * key = insn->op | (insn->op1->op << 7) | (insn->op2->op << 14)
 *
 * ANY and UNUSED ops are represented by 0
 */

ir_ref ir_folding(ir_ctx *ctx, uint32_t opt, ir_ref op1, ir_ref op2, ir_ref op3,
                  const ir_insn *op1_insn, const ir_insn *op2_insn, const ir_insn *op3_insn)
{
	uint8_t op;
	ir_ref ref;
	ir_val val;
	uint32_t key, any;
	(void) op3_insn;

restart:
	key = (opt & IR_OPT_OP_MASK) + ((uint32_t)op1_insn->op << 7) + ((uint32_t)op2_insn->op << 14);
	any = 0x1fffff;
	do {
		uint32_t k = key & any;
		uint32_t h = _ir_fold_hashkey(k);
		uint32_t fh = _ir_fold_hash[h];
		if (IR_FOLD_KEY(fh) == k
#ifdef IR_FOLD_SEMI_PERFECT_HASH
		 || (fh = _ir_fold_hash[h+1], (fh & 0x1fffff) == k)
#endif
		) {
			switch (IR_FOLD_RULE(fh)) {
#include "ir_fold.h"
				default:
					break;
			}
		}
		if (any == 0x7f) {
			/* All parrerns are checked. Pass on to CSE. */
			goto ir_fold_cse;
		}
		/* op2/op1/op  op2/_/op    _/op1/op    _/_/op
		 * 0x1fffff -> 0x1fc07f -> 0x003fff -> 0x00007f
		 * from masks to bis: 11 -> 10 -> 01 -> 00
		 *
		 * a b  => x y
		 * 1 1     1 0
		 * 1 0     0 1
		 * 0 1     0 0
		 *
		 * x = a & b; y = !b
		 */
		any = ((any & (any << 7)) & 0x1fc000) | (~any & 0x3f80) | 0x7f;
	} while (1);

ir_fold_restart:
	if (!ctx->use_lists) {
		op1_insn = ctx->ir_base + op1;
		op2_insn = ctx->ir_base + op2;
		op3_insn = ctx->ir_base + op3;
		goto restart;
	} else {
		ctx->fold_insn.optx = opt;
		ctx->fold_insn.op1 = op1;
		ctx->fold_insn.op2 = op2;
		ctx->fold_insn.op3 = op3;
		return IR_FOLD_DO_RESTART;
	}
ir_fold_cse:
	if (!ctx->use_lists) {
		/* Local CSE */
		ref = _ir_fold_cse(ctx, opt, op1, op2, op3);
		if (ref) {
			return ref;
		}

		ref = ir_emit(ctx, opt, op1, op2, op3);

		/* Update local CSE chain */
		op = opt & IR_OPT_OP_MASK;
		ir_ref prev = ctx->prev_insn_chain[op];
		ir_insn *insn = ctx->ir_base + ref;
		if (!prev || ref - prev > 0xffff) {
			/* can't fit into 16-bit */
			insn->prev_insn_offset = 0;
		} else {
			insn->prev_insn_offset = ref - prev;
		}
		ctx->prev_insn_chain[op] = ref;

		return ref;
	} else {
		ctx->fold_insn.optx = opt;
		ctx->fold_insn.op1 = op1;
		ctx->fold_insn.op2 = op2;
		ctx->fold_insn.op3 = op3;
		return IR_FOLD_DO_CSE;
	}
ir_fold_emit:
	if (!ctx->use_lists) {
		return ir_emit(ctx, opt, op1, op2, op3);
	} else {
		ctx->fold_insn.optx = opt;
		ctx->fold_insn.op1 = op1;
		ctx->fold_insn.op2 = op2;
		ctx->fold_insn.op3 = op3;
		return IR_FOLD_DO_EMIT;
	}
ir_fold_copy:
	if (!ctx->use_lists) {
		return ref;
	} else {
		ctx->fold_insn.op1 = ref;
		return IR_FOLD_DO_COPY;
	}
ir_fold_const:
	{
		ir_type type = IR_OPT_TYPE(opt);

		/* Extend a narrow integer result to its type width so no
		 * fold rule sees garbage in the upper bits. */
		if (IR_IS_TYPE_INT(type) && ir_type_size[type] < 8) {
			val.u64 = ir_fix_int(type, val.u64);
		}

		if (!ctx->use_lists) {
			return ir_const(ctx, val, type);
		} else {
			ctx->fold_insn.opt = IR_OPT(type, type);
			ctx->fold_insn.val.u64 = val.u64;
			return IR_FOLD_DO_CONST;
		}
	}
}

ir_ref ir_fold(ir_ctx *ctx, uint32_t opt, ir_ref op1, ir_ref op2, ir_ref op3)
{
	if (UNEXPECTED(!(ctx->flags & IR_OPT_FOLDING))) {
		if ((opt & IR_OPT_OP_MASK) == IR_PHI) {
			opt |= (3 << IR_OPT_INPUTS_SHIFT);
		} else if ((ir_op_flags[(opt & IR_OPT_OP_MASK)] & IR_OP_FLAG_COMMUTATIVE)
		 && op1 < op2
		 && IR_IS_CONST_REF(op1)) {
			/* Move constants to op2 for better instruction selection with (this is for -O0) */
			SWAP_REFS(op1, op2);
		}
		return ir_emit(ctx, opt, op1, op2, op3);
	}
	return ir_folding(ctx, opt, op1, op2, op3, ctx->ir_base + op1, ctx->ir_base + op2, ctx->ir_base + op3);
}

ir_ref ir_fold0(ir_ctx *ctx, uint32_t opt)
{
	return ir_fold(ctx, opt, IR_UNUSED, IR_UNUSED, IR_UNUSED);
}

ir_ref ir_fold1(ir_ctx *ctx, uint32_t opt, ir_ref op1)
{
	return ir_fold(ctx, opt, op1, IR_UNUSED, IR_UNUSED);
}

ir_ref ir_fold2(ir_ctx *ctx, uint32_t opt, ir_ref op1, ir_ref op2)
{
	return ir_fold(ctx, opt, op1, op2, IR_UNUSED);
}

ir_ref ir_fold3(ir_ctx *ctx, uint32_t opt, ir_ref op1, ir_ref op2, ir_ref op3)
{
	return ir_fold(ctx, opt, op1, op2, op3);
}

ir_ref ir_emit_N(ir_ctx *ctx, uint32_t opt, int32_t count)
{
	int i;
	ir_ref *p, ref = ctx->insns_count;
	ir_insn *insn;

	IR_ASSERT(count >= 0 && count < 65536);
	while (UNEXPECTED(ref + count/4 >= ctx->insns_limit)) {
		ir_grow_top(ctx);
	}
	ctx->insns_count = ref + 1 + count/4;

	insn = &ctx->ir_base[ref];
	insn->optx = opt | (count << IR_OPT_INPUTS_SHIFT);
	for (i = 1, p = insn->ops + i; i <= (count|3); i++, p++) {
		*p = IR_UNUSED;
	}

	return ref;
}

void ir_set_op(ir_ctx *ctx, ir_ref ref, int32_t n, ir_ref val)
{
	ir_insn *insn = &ctx->ir_base[ref];

#ifdef IR_DEBUG
	if (n > 3) {
		int32_t count;

		IR_ASSERT(IR_OP_HAS_VAR_INPUTS(ir_op_flags[insn->op]));
		count = insn->inputs_count;
		IR_ASSERT(n <= count);
	}
#endif
	ir_insn_set_op(insn, n, val);
}

ir_ref ir_get_op(const ir_ctx *ctx, ir_ref ref, int32_t n)
{
	const ir_insn *insn = &ctx->ir_base[ref];

#ifdef IR_DEBUG
	if (n > 3) {
		int32_t count;

		IR_ASSERT(IR_OP_HAS_VAR_INPUTS(ir_op_flags[insn->op]));
		count = insn->inputs_count;
		IR_ASSERT(n <= count);
	}
#endif
	return ir_insn_op(insn, n);
}

ir_ref ir_param(ir_ctx *ctx, ir_type type, ir_ref region, const char *name, int pos)
{
	IR_ASSERT(ctx->ir_base[region].op == IR_START);
	return ir_emit(ctx, IR_OPT(IR_PARAM, type), region, ir_string(ctx, name), pos);
}

ir_ref ir_param_ex(ir_ctx *ctx, ir_type type, ir_ref region, ir_str name, int pos)
{
	IR_ASSERT(ctx->ir_base[region].op == IR_START);
	return ir_emit(ctx, IR_OPT(IR_PARAM, type), region, name, pos);
}

ir_ref ir_var(ir_ctx *ctx, ir_type type, ir_ref region, const char *name)
{
	IR_ASSERT(IR_IS_BB_START(ctx->ir_base[region].op));
	return ir_emit(ctx, IR_OPT(IR_VAR, type), region, ir_string(ctx, name), IR_UNUSED);
}

ir_ref ir_var_ex(ir_ctx *ctx, ir_type type, ir_ref region, ir_str name)
{
	IR_ASSERT(IR_IS_BB_START(ctx->ir_base[region].op));
	return ir_emit(ctx, IR_OPT(IR_VAR, type), region, name, IR_UNUSED);
}

ir_ref ir_bind(ir_ctx *ctx, ir_ref var, ir_ref def)
{
	if (IR_IS_CONST_REF(def)) {
		return def;
	}
	if (!ctx->binding) {
		ctx->binding = ir_mem_malloc(sizeof(ir_hashtab));;
		ir_hashtab_init(ctx->binding, 16);
	}
	/* Node may be bound to some special spill slot (using negative "var") */
	IR_ASSERT(var < 0);
	if (!ir_hashtab_add(ctx->binding, def, var)) {
		/* Add a copy with different binding */
		def = ir_emit2(ctx, IR_OPT(IR_COPY, ctx->ir_base[def].type), def, IR_COPY_HARD);
		ir_hashtab_add(ctx->binding, def, var);
	}
	return def;
}

ir_ref ir_binding_find(const ir_ctx *ctx, ir_ref ref)
{
	ir_ref var = ir_hashtab_find(ctx->binding, ref);
	return (var != (ir_ref)IR_INVALID_VAL) ? var : 0;
}

/* Batch construction of def->use edges */
#if 0
void ir_build_def_use_lists(ir_ctx *ctx)
{
	ir_ref n, i, j, *p, def;
	ir_insn *insn;
	uint32_t edges_count;
	ir_use_list *lists = ir_mem_calloc(ctx->insns_limit, sizeof(ir_use_list));
	ir_ref *edges;
	ir_use_list *use_list;

	for (i = IR_UNUSED + 1, insn = ctx->ir_base + i; i < ctx->insns_count;) {
		uint32_t flags = ir_op_flags[insn->op];

		if (UNEXPECTED(IR_OP_HAS_VAR_INPUTS(flags))) {
			n = insn->inputs_count;
		} else {
			n = insn->inputs_count = IR_INPUT_EDGES_COUNT(flags);
		}
		for (j = n, p = insn->ops + 1; j > 0; j--, p++) {
			def = *p;
			if (def > 0) {
				lists[def].count++;
			}
		}
		n = ir_insn_inputs_to_len(n);
		i += n;
		insn += n;
	}

	edges_count = 0;
	for (i = IR_UNUSED + 1, use_list = &lists[i]; i < ctx->insns_count; i++, use_list++) {
		use_list->refs = edges_count;
		edges_count += use_list->count;
		use_list->count = 0;
	}

	edges = ir_mem_malloc(IR_ALIGNED_SIZE(edges_count * sizeof(ir_ref), 4096));
	for (i = IR_UNUSED + 1, insn = ctx->ir_base + i; i < ctx->insns_count;) {
		n = insn->inputs_count;
		for (j = n, p = insn->ops + 1; j > 0; j--, p++) {
			def = *p;
			if (def > 0) {
				use_list = &lists[def];
				edges[use_list->refs + use_list->count++] = i;
			}
		}
		n = ir_insn_inputs_to_len(n);
		i += n;
		insn += n;
	}

	ctx->use_edges = edges;
	ctx->use_edges_count = edges_count;
	ctx->use_lists = lists;
}
#else
void ir_build_def_use_lists(ir_ctx *ctx)
{
	ir_ref n, i, j, *p, def;
	ir_insn *insn;
	size_t linked_lists_size, linked_lists_top = 0, edges_count = 0;
	ir_use_list *lists = ir_mem_calloc(ctx->insns_limit, sizeof(ir_use_list));
	ir_ref *edges;
	ir_use_list *use_list;
	ir_ref *linked_lists;

	linked_lists_size = IR_ALIGNED_SIZE(ctx->insns_count, 1024);
	linked_lists = ir_mem_malloc(linked_lists_size * sizeof(ir_ref));
	for (i = IR_UNUSED + 1, insn = ctx->ir_base + i; i < ctx->insns_count;) {
		uint32_t flags = ir_op_flags[insn->op];

		if (UNEXPECTED(IR_OP_HAS_VAR_INPUTS(flags))) {
			n = insn->inputs_count;
		} else {
			n = insn->inputs_count = IR_INPUT_EDGES_COUNT(flags);
		}
		for (j = n, p = insn->ops + 1; j > 0; j--, p++) {
			def = *p;
			if (def > 0) {
				use_list = &lists[def];
				edges_count++;
				if (!use_list->refs) {
					/* store a single "use" directly in "refs" using a positive number */
					use_list->refs = i;
					use_list->count = 1;
				} else {
					if (UNEXPECTED(linked_lists_top >= linked_lists_size)) {
						linked_lists_size += 1024;
						linked_lists = ir_mem_realloc(linked_lists, linked_lists_size * sizeof(ir_ref));
					}
					/* form a linked list of "uses" (like in binsort) */
					linked_lists[linked_lists_top] = i; /* store the "use" */
					linked_lists[linked_lists_top + 1] = use_list->refs; /* store list next */
					use_list->refs = -(ir_ref)(linked_lists_top + 1); /* store a head of the list using a negative number */
					linked_lists_top += 2;
					use_list->count++;
				}
			}
		}
		n = ir_insn_inputs_to_len(n);
		i += n;
		insn += n;
	}

	IR_ASSERT(edges_count <= 0x7fffffff);
	ctx->use_edges_count = (ir_ref)edges_count;
	edges = ir_mem_malloc(IR_ALIGNED_SIZE(edges_count * sizeof(ir_ref), 4096));
	for (use_list = lists + ctx->insns_count - 1; use_list != lists; use_list--) {
		n = use_list->refs;
		if (n) {
			/* transform linked list to plain array */
			while (n < 0) {
				n = -n;
				edges[--edges_count] = linked_lists[n - 1];
				n = linked_lists[n];
			}
			IR_ASSERT(n > 0);
			edges[--edges_count] = n;
			use_list->refs = (ir_ref)edges_count;
		}
	}

	ctx->use_edges = edges;
	ctx->use_lists = lists;
	ir_mem_free(linked_lists);
}
#endif

void ir_use_list_remove_all(ir_ctx *ctx, ir_ref from, ir_ref ref)
{
	ir_ref n, *p, *q, use;
	ir_use_list *use_list;

	IR_ASSERT(from > 0);
	use_list = &ctx->use_lists[from];
	n = use_list->count;
	for (p = q = &ctx->use_edges[use_list->refs]; n > 0; p++, n--) {
		use = *p;
		if (use != ref) {
			if (p != q) {
				*q = use;
			}
			q++;
		}
	}
	if (p != q) {
		use_list->count -= (ir_ref)(p - q);
		do {
			*q = IR_UNUSED;
			q++;
		} while (q != p);
	}
}

void ir_use_list_remove_one(ir_ctx *ctx, ir_ref from, ir_ref ref)
{
	ir_ref n, *p;
	ir_use_list *use_list;

	IR_ASSERT(from > 0);
	use_list = &ctx->use_lists[from];
	n = use_list->count;
	p = &ctx->use_edges[use_list->refs];
	while (n > 0) {
		if (*p == ref) {
			use_list->count--;
			n--;
			while (n > 0) {
				*p = *(p+1);
				p++;
				n--;
			}
			*p = IR_UNUSED;
			break;
		}
		p++;
		n--;
	}
}

void ir_use_list_replace_one(ir_ctx *ctx, ir_ref ref, ir_ref use, ir_ref new_use)
{
	ir_use_list *use_list;
	ir_ref n, *p;

	IR_ASSERT(ref > 0);
	use_list = &ctx->use_lists[ref];
	n = use_list->count;
	for (p = &ctx->use_edges[use_list->refs]; n > 0; p++, n--) {
		if (*p == use) {
			*p = new_use;
			break;
		}
	}
}

void ir_use_list_replace_all(ir_ctx *ctx, ir_ref ref, ir_ref use, ir_ref new_use)
{
	ir_use_list *use_list;
	ir_ref n, *p;

	IR_ASSERT(ref > 0);
	use_list = &ctx->use_lists[ref];
	n = use_list->count;
	for (p = &ctx->use_edges[use_list->refs]; n > 0; p++, n--) {
		if (*p == use) {
			*p = new_use;
		}
	}
}

bool ir_use_list_add(ir_ctx *ctx, ir_ref to, ir_ref ref)
{
	ir_use_list *use_list;
	ir_ref n;

	IR_ASSERT(to > 0);
	use_list = &ctx->use_lists[to];
	n = use_list->refs + use_list->count;
	if (n < ctx->use_edges_count && ctx->use_edges[n] == IR_UNUSED) {
		ctx->use_edges[n] = ref;
		use_list->count++;
		return 0;
	} else {
		size_t old_size = IR_ALIGNED_SIZE(ctx->use_edges_count * sizeof(ir_ref), 4096);
		size_t new_size = IR_ALIGNED_SIZE((ctx->use_edges_count + use_list->count + 1) * sizeof(ir_ref), 4096);

		if (old_size < new_size) {
			/* Reallocate the whole edges buffer (this is inefficient) */
			ctx->use_edges = ir_mem_realloc(ctx->use_edges, new_size);
			if (n == ctx->use_edges_count) {
				ctx->use_edges[n] = ref;
				use_list->count++;
				ctx->use_edges_count++;
				return 1;
			}
		} else if (n == ctx->use_edges_count) {
			ctx->use_edges[n] = ref;
			use_list->count++;
			ctx->use_edges_count++;
			return 0;
		}
		if (use_list->count) {
			memcpy(ctx->use_edges + ctx->use_edges_count, ctx->use_edges + use_list->refs, use_list->count * sizeof(ir_ref));
		}
		use_list->refs = ctx->use_edges_count;
		ctx->use_edges[use_list->refs + use_list->count] = ref;
		use_list->count++;
		ctx->use_edges_count += use_list->count;
		return 1;
	}
}

void ir_replace(ir_ctx *ctx, ir_ref ref, ir_ref new_ref)
{
	int i, j, n, *p, use;
	ir_insn *insn;
	ir_use_list *use_list;

	IR_ASSERT(ref != new_ref);
	use_list = &ctx->use_lists[ref];
	n = use_list->count;
	p = ctx->use_edges + use_list->refs;

	if (new_ref <= 0) {
		/* constant or IR_UNUSED */
		for (; n; p++, n--) {
			use = *p;
			IR_ASSERT(use != ref);
			insn = &ctx->ir_base[use];
			j = ir_insn_find_op(insn, ref);
			IR_ASSERT(j > 0);
			ir_insn_set_op(insn, j, new_ref);
		}
	} else {
		for (i = 0; i < n; p++, i++) {
			use = *p;
			IR_ASSERT(use != ref);
			insn = &ctx->ir_base[use];
			j = ir_insn_find_op(insn, ref);
			IR_ASSERT(j > 0);
			ir_insn_set_op(insn, j, new_ref);
			if (ir_use_list_add(ctx, new_ref, use)) {
				/* restore after reallocation */
				use_list = &ctx->use_lists[ref];
				n = use_list->count;
				p = &ctx->use_edges[use_list->refs + i];
			}
		}
	}
}

void ir_update_op(ir_ctx *ctx, ir_ref ref, uint32_t idx, ir_ref new_val)
{
	ir_insn *insn = &ctx->ir_base[ref];
	ir_ref old_val = ir_insn_op(insn, idx);

	IR_ASSERT(old_val != new_val);
	if (new_val > 0) {
		ir_use_list_add(ctx, new_val, ref);
	}
	ir_insn_set_op(insn, idx, new_val);
	if (old_val > 0) {
		ir_use_list_remove_one(ctx, old_val, ref);
	}
}

/* Helper Data Types */
void ir_array_grow(ir_array *a, uint32_t size)
{
	IR_ASSERT(size > a->size);
	if (size >= 256) {
		size = IR_ALIGNED_SIZE(size, 256);
	} else {
		/* Use big enough power of 2 */
		size -= 1;
		size |= (size >> 1);
		size |= (size >> 2);
		size |= (size >> 4);
//		size |= (size >> 8);
//		size |= (size >> 16);
		size += 1;
	}
	a->refs = ir_mem_realloc(a->refs, size * sizeof(ir_ref));
	a->size = size;
}

void ir_array_insert(ir_array *a, uint32_t i, ir_ref val)
{
	IR_ASSERT(i < a->size);
	if (a->refs[a->size - 1]) {
		ir_array_grow(a, a->size + 1);
	}
	memmove(a->refs + i + 1, a->refs + i, (a->size - i - 1) * sizeof(ir_ref));
	a->refs[i] = val;
}

void ir_array_remove(ir_array *a, uint32_t i)
{
	IR_ASSERT(i < a->size);
	memmove(a->refs + i, a->refs + i + 1, (a->size - i - 1) * sizeof(ir_ref));
	a->refs[a->size - 1] = IR_UNUSED;
}

void ir_list_insert(ir_list *l, uint32_t i, ir_ref val)
{
	IR_ASSERT(i < l->len);
	if (l->len >= l->a.size) {
		ir_array_grow(&l->a, l->a.size + 1);
	}
	memmove(l->a.refs + i + 1, l->a.refs + i, (l->len - i) * sizeof(ir_ref));
	l->a.refs[i] = val;
	l->len++;
}

void ir_list_remove(ir_list *l, uint32_t i)
{
	IR_ASSERT(i < l->len);
	memmove(l->a.refs + i, l->a.refs + i + 1, (l->len - i) * sizeof(ir_ref));
	l->len--;
}

uint32_t ir_list_find(const ir_list *l, ir_ref val)
{
	uint32_t i;

	for (i = 0; i < l->len; i++) {
		if (ir_array_at(&l->a, i) == val) {
			return i;
		}
	}
	return (uint32_t)-1;
}

static uint32_t ir_hashtab_hash_size(uint32_t size)
{
	size -= 1;
	size |= (size >> 1);
	size |= (size >> 2);
	size |= (size >> 4);
	size |= (size >> 8);
	size |= (size >> 16);
	return IR_MAX(size + 1, 4);
}

static void ir_hashtab_resize(ir_hashtab *tab)
{
	uint32_t old_hash_size = (uint32_t)(-(int32_t)tab->mask);
	char *old_data = tab->data;
	uint32_t size = tab->size * 2;
	uint32_t hash_size = ir_hashtab_hash_size(size);
	char *data = ir_mem_malloc(hash_size * sizeof(uint32_t) + size * sizeof(ir_hashtab_bucket));
	ir_hashtab_bucket *p;
	uint32_t pos, i;

	memset(data, -1, hash_size * sizeof(uint32_t));
	tab->data = data + (hash_size * sizeof(uint32_t));
	tab->mask = (uint32_t)(-(int32_t)hash_size);
	tab->size = size;

	memcpy(tab->data, old_data, tab->count * sizeof(ir_hashtab_bucket));
	ir_mem_free(old_data - (old_hash_size * sizeof(uint32_t)));

	i = tab->count;
	pos = 0;
	p = (ir_hashtab_bucket*)tab->data;
	do {
		uint32_t key = p->key | tab->mask;
		p->next = ((uint32_t*)tab->data)[(int32_t)key];
		((uint32_t*)tab->data)[(int32_t)key] = pos;
		pos += sizeof(ir_hashtab_bucket);
		p++;
	} while (--i);
}

void ir_hashtab_init(ir_hashtab *tab, uint32_t size)
{
	IR_ASSERT(size > 0);
	uint32_t hash_size = ir_hashtab_hash_size(size);
	char *data = ir_mem_malloc(hash_size * sizeof(uint32_t) + size * sizeof(ir_hashtab_bucket));
	memset(data, -1, hash_size * sizeof(uint32_t));
	tab->data = (data + (hash_size * sizeof(uint32_t)));
	tab->mask = (uint32_t)(-(int32_t)hash_size);
	tab->size = size;
	tab->count = 0;
	tab->pos = 0;
}

void ir_hashtab_free(ir_hashtab *tab)
{
	uint32_t hash_size = (uint32_t)(-(int32_t)tab->mask);
	char *data = (char*)tab->data - (hash_size * sizeof(uint32_t));
	ir_mem_free(data);
	tab->data = NULL;
}

ir_ref ir_hashtab_find(const ir_hashtab *tab, uint32_t key)
{
	const char *data = (const char*)tab->data;
	uint32_t pos = ((uint32_t*)data)[(int32_t)(key | tab->mask)];
	ir_hashtab_bucket *p;

	while (pos != IR_INVALID_IDX) {
		p = (ir_hashtab_bucket*)(data + pos);
		if (p->key == key) {
			return p->val;
		}
		pos = p->next;
	}
	return IR_INVALID_VAL;
}

bool ir_hashtab_add(ir_hashtab *tab, uint32_t key, ir_ref val)
{
	char *data = (char*)tab->data;
	uint32_t pos = ((uint32_t*)data)[(int32_t)(key | tab->mask)];
	ir_hashtab_bucket *p;

	while (pos != IR_INVALID_IDX) {
		p = (ir_hashtab_bucket*)(data + pos);
		if (p->key == key) {
			return p->val == val;
		}
		pos = p->next;
	}

	if (UNEXPECTED(tab->count >= tab->size)) {
		ir_hashtab_resize(tab);
		data = tab->data;
	}

	pos = tab->pos;
	tab->pos += sizeof(ir_hashtab_bucket);
	tab->count++;
	p = (ir_hashtab_bucket*)(data + pos);
	p->key = key;
	p->val = val;
	key |= tab->mask;
	p->next = ((uint32_t*)data)[(int32_t)key];
	((uint32_t*)data)[(int32_t)key] = pos;
	return 1;
}

static int ir_hashtab_key_cmp(const void *b1, const void *b2)
{
	return ((ir_hashtab_bucket*)b1)->key - ((ir_hashtab_bucket*)b2)->key;
}

void ir_hashtab_key_sort(ir_hashtab *tab)
{
	ir_hashtab_bucket *p;
	uint32_t hash_size, pos, i;

	if (!tab->count) {
		return;
	}

	qsort(tab->data, tab->count, sizeof(ir_hashtab_bucket), ir_hashtab_key_cmp);

	hash_size = ir_hashtab_hash_size(tab->size);
	memset((char*)tab->data - (hash_size * sizeof(uint32_t)), -1, hash_size * sizeof(uint32_t));

	i = tab->count;
	pos = 0;
	p = (ir_hashtab_bucket*)tab->data;
	do {
		uint32_t key = p->key | tab->mask;
		p->next = ((uint32_t*)tab->data)[(int32_t)key];
		((uint32_t*)tab->data)[(int32_t)key] = pos;
		pos += sizeof(ir_hashtab_bucket);
		p++;
	} while (--i);
}

static void ir_addrtab_resize(ir_hashtab *tab)
{
	uint32_t old_hash_size = (uint32_t)(-(int32_t)tab->mask);
	char *old_data = tab->data;
	uint32_t size = tab->size * 2;
	uint32_t hash_size = ir_hashtab_hash_size(size);
	char *data = ir_mem_malloc(hash_size * sizeof(uint32_t) + size * sizeof(ir_addrtab_bucket));
	ir_addrtab_bucket *p;
	uint32_t pos, i;

	memset(data, -1, hash_size * sizeof(uint32_t));
	tab->data = data + (hash_size * sizeof(uint32_t));
	tab->mask = (uint32_t)(-(int32_t)hash_size);
	tab->size = size;

	memcpy(tab->data, old_data, tab->count * sizeof(ir_addrtab_bucket));
	ir_mem_free(old_data - (old_hash_size * sizeof(uint32_t)));

	i = tab->count;
	pos = 0;
	p = (ir_addrtab_bucket*)tab->data;
	do {
		uint32_t key = (uint32_t)p->key | tab->mask;
		p->next = ((uint32_t*)tab->data)[(int32_t)key];
		((uint32_t*)tab->data)[(int32_t)key] = pos;
		pos += sizeof(ir_addrtab_bucket);
		p++;
	} while (--i);
}

void ir_addrtab_init(ir_hashtab *tab, uint32_t size)
{
	IR_ASSERT(size > 0);
	uint32_t hash_size = ir_hashtab_hash_size(size);
	char *data = ir_mem_malloc(hash_size * sizeof(uint32_t) + size * sizeof(ir_addrtab_bucket));
	memset(data, -1, hash_size * sizeof(uint32_t));
	tab->data = (data + (hash_size * sizeof(uint32_t)));
	tab->mask = (uint32_t)(-(int32_t)hash_size);
	tab->size = size;
	tab->count = 0;
	tab->pos = 0;
}

void ir_addrtab_free(ir_hashtab *tab)
{
	uint32_t hash_size = (uint32_t)(-(int32_t)tab->mask);
	char *data = (char*)tab->data - (hash_size * sizeof(uint32_t));
	ir_mem_free(data);
	tab->data = NULL;
}

ir_ref ir_addrtab_find(const ir_hashtab *tab, uint64_t key)
{
	const char *data = (const char*)tab->data;
	uint32_t pos = ((uint32_t*)data)[(int32_t)(key | tab->mask)];
	ir_addrtab_bucket *p;

	while (pos != IR_INVALID_IDX) {
		p = (ir_addrtab_bucket*)(data + pos);
		if (p->key == key) {
			return p->val;
		}
		pos = p->next;
	}
	return IR_INVALID_VAL;
}

void ir_addrtab_set(ir_hashtab *tab, uint64_t key, ir_ref val)
{
	char *data = (char*)tab->data;
	uint32_t pos = ((uint32_t*)data)[(int32_t)(key | tab->mask)];
	ir_addrtab_bucket *p;

	while (pos != IR_INVALID_IDX) {
		p = (ir_addrtab_bucket*)(data + pos);
		if (p->key == key) {
			p->val = val;
			return;
		}
		pos = p->next;
	}

	if (UNEXPECTED(tab->count >= tab->size)) {
		ir_addrtab_resize(tab);
		data = tab->data;
	}

	pos = tab->pos;
	tab->pos += sizeof(ir_addrtab_bucket);
	tab->count++;
	p = (ir_addrtab_bucket*)(data + pos);
	p->key = key;
	p->val = val;
	key |= tab->mask;
	p->next = ((uint32_t*)data)[(int32_t)key];
	((uint32_t*)data)[(int32_t)key] = pos;
}

/* Memory API */
#ifdef _WIN32
void *ir_mem_mmap(size_t size)
{
	void *ret;

#ifdef _M_X64
	DWORD size_hi = size >> 32, size_lo = size & 0xffffffff;
#else
	DWORD size_hi = 0, size_lo = size;
#endif

	HANDLE h = CreateFileMapping(INVALID_HANDLE_VALUE, NULL, PAGE_EXECUTE_READWRITE, size_hi, size_lo, NULL);

	ret = MapViewOfFile(h, FILE_MAP_READ | FILE_MAP_WRITE | FILE_MAP_EXECUTE, 0, 0, size);
	if (!ret) {
		CloseHandle(h);
	}

	return ret;
}

int ir_mem_unmap(void *ptr, size_t size)
{
	/* XXX file handle is leaked. */
	UnmapViewOfFile(ptr);
	return 1;
}

int ir_mem_protect(void *ptr, size_t size)
{
	return 1;
}

int ir_mem_unprotect(void *ptr, size_t size)
{
	return 1;
}

int ir_mem_flush(void *ptr, size_t size)
{
	return FlushInstructionCache(GetCurrentProcess(), ptr, size) == TRUE ? 1 : 0;
}
#else

#if defined(__linux__) && defined(__x86_64__) && defined(PKEY_DISABLE_WRITE)
# define HAVE_PKEY_MPROTECT 1
#endif

#ifdef HAVE_PKEY_MPROTECT

#ifndef PKEY_DISABLE_EXECUTE
# define PKEY_DISABLE_EXECUTE 0
#endif

int pkey_mprotect(void* addr, size_t len, int prot, int pkey) __attribute__((weak));
int pkey_alloc(unsigned int, unsigned int) __attribute__((weak));
int pkey_free(int) __attribute__((weak));
int pkey_set(int, unsigned) __attribute__((weak));

static int ir_pkey = 0;
#endif

void *ir_mem_mmap(size_t size)
{
#ifdef HAVE_PKEY_MPROTECT
	if (!ir_pkey && pkey_mprotect) {
		int key = pkey_alloc(0, PKEY_DISABLE_WRITE);
		if (key > 0) {
			ir_pkey = key;
		}
	}
	if (ir_pkey > 0) {
		void *ret = mmap(NULL, size, PROT_EXEC|PROT_READ|PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
		if (ret == MAP_FAILED) {
			return NULL;
		}
		if (pkey_mprotect(ret, size, PROT_EXEC|PROT_READ|PROT_WRITE, ir_pkey) != 0) {
#ifdef IR_DEBUG
			fprintf(stderr, "pkey_mprotect() failed\n");
#endif
			munmap(ret, size);
			return NULL;
		}
		return ret;
	}
#endif
	int prot_flags = PROT_EXEC;
#if defined(__NetBSD__)
	prot_flags |= PROT_MPROTECT(PROT_READ|PROT_WRITE);
#endif
	void *ret = mmap(NULL, size, prot_flags, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
	if (ret == MAP_FAILED) {
		ret = NULL;
	}
	return ret;
}

int ir_mem_unmap(void *ptr, size_t size)
{
	munmap(ptr, size);
#ifdef HAVE_PKEY_MPROTECT
//	if (ir_pkey > 0) {
//		pkey_free(ir_pkey);
//		ir_pkey = 0;
//	}
#endif
	return 1;
}

int ir_mem_protect(void *ptr, size_t size)
{
#ifdef HAVE_PKEY_MPROTECT
	if (ir_pkey > 0) {
		if (pkey_set(ir_pkey, PKEY_DISABLE_WRITE)) {
#ifdef IR_DEBUG
			fprintf(stderr, "mprotect() failed\n");
#endif
			return 0;
		}
		return 1;
	}
#endif
	if (mprotect(ptr, size, PROT_READ | PROT_EXEC) != 0) {
#ifdef IR_DEBUG
		fprintf(stderr, "mprotect() failed\n");
#endif
		return 0;
	}
	return 1;
}

int ir_mem_unprotect(void *ptr, size_t size)
{
#ifdef HAVE_PKEY_MPROTECT
	if (ir_pkey > 0) {
		if (pkey_set(ir_pkey, PKEY_DISABLE_EXECUTE)) {
#ifdef IR_DEBUG
			fprintf(stderr, "mprotect() failed\n");
#endif
			return 0;
		}
		return 1;
	}
#endif
	if (mprotect(ptr, size, PROT_READ | PROT_WRITE) != 0) {
#ifdef IR_DEBUG
		fprintf(stderr, "mprotect() failed\n");
#endif
		return 0;
	}
	return 1;
}

int ir_mem_flush(void *ptr, size_t size)
{
#if ((defined(__GNUC__) && ZEND_GCC_VERSION >= 4003) || __has_builtin(__builtin___clear_cache))
	__builtin___clear_cache((char*)(ptr), (char*)(ptr) + size);
#endif
#if defined(__APPLE__) && defined(__aarch64__)
	sys_icache_invalidate(ptr, size);
#endif
#ifdef HAVE_VALGRIND
	VALGRIND_DISCARD_TRANSLATIONS(ptr, size);
#endif
	return 1;
}
#endif

/* Alias Analyses */
typedef enum _ir_alias {
	IR_MAY_ALIAS  = -1,
	IR_NO_ALIAS   =  0,
	IR_MUST_ALIAS =  1,
} ir_alias;

IR_ALWAYS_INLINE const ir_insn *ir_decompose_addr(const ir_ctx *ctx, ir_ref addr, ir_ref *base, ir_ref *index, intptr_t *offset)
{
	const ir_insn *insn = &ctx->ir_base[addr];
	ir_ref idx = IR_UNUSED;
	intptr_t off = 0;

	while (1) {
		if (insn->op == IR_ADD) {
			ir_ref op1 = insn->op1;
			ir_ref op2 = insn->op2;
			const ir_insn *op1_insn = &ctx->ir_base[op1];
			const ir_insn *op2_insn = &ctx->ir_base[op2];

			if ((op2_insn->type == IR_ADDR && op1_insn->type != IR_ADDR)
			 || op2_insn->op == IR_SYM
			 || op2_insn->op == IR_ALLOCA
			 || op2_insn->op == IR_VADDR) {
				const ir_insn *tmp = op1_insn;
				op1_insn = op2_insn;
				op2_insn = tmp;
				SWAP_REFS(op1, op2);
		    }
			if (IR_IS_CONST_REF(op2) && !IR_IS_SYM_CONST(op2_insn->op)) {
				off += op2_insn->val.addr;
				addr = op1;
				insn = op1_insn;
			} else if (!idx) {
				addr = op1;
				insn = op1_insn;
				idx = op2;
			} else {
				goto exit;
			}
		} else if (insn->op == IR_SUB
		 && IR_IS_CONST_REF(insn->op2)
		 && !IR_IS_SYM_CONST(ctx->ir_base[insn->op2].op)) {
			off -= ctx->ir_base[insn->op2].val.addr;
			addr = insn->op1;
			insn = &ctx->ir_base[insn->op1];
		} else {
			break;
		}
	}

	if (idx) {
		while (1) {
			const ir_insn *insn = &ctx->ir_base[idx];

			if (insn->op == IR_ADD) {
				if (IR_IS_CONST_REF(insn->op2)
				 && !IR_IS_SYM_CONST(ctx->ir_base[insn->op2].op)) {
					off += ctx->ir_base[insn->op2].val.addr;
					idx = insn->op1;
				} else {
					break;
				}
			} else if (insn->op == IR_SUB
			 && IR_IS_CONST_REF(insn->op2)
			 && !IR_IS_SYM_CONST(ctx->ir_base[insn->op2].op)) {
				off -= ctx->ir_base[insn->op2].val.addr;
				idx = insn->op1;
			} else {
				break;
			}
		}
	}

exit:
	*base = addr;
	*index = idx;
	*offset = off;

	return insn;
}

IR_ALWAYS_INLINE const ir_insn *ir_get_base_addr(const ir_ctx *ctx, const ir_insn *insn)
{
	while (1) {
		if (insn->op == IR_ADD) {
			ir_ref op1 = insn->op1;
			ir_ref op2 = insn->op2;
			const ir_insn *op1_insn = &ctx->ir_base[op1];
			const ir_insn *op2_insn = &ctx->ir_base[op2];

			if (op2_insn->op == IR_SYM || op2_insn->op == IR_ALLOCA || op2_insn->op == IR_VADDR) {
				return op2_insn;
			} else if (op2_insn->type == IR_ADDR && op1_insn->type != IR_ADDR) {
				insn = op2_insn;
		    } else {
				insn = op1_insn;
			}
		} else if (insn->op == IR_SUB) {
			insn = &ctx->ir_base[insn->op1];
		} else {
			break;
		}
	}
	return insn;
}

static ir_alias ir_check_aliasing(const ir_ctx *ctx, ir_ref addr1, ir_ref addr2, ir_type type1, ir_type type2)
{
	const ir_insn *insn1, *insn2;
	ir_ref base1, base2, index1, index2;
	intptr_t offset1, offset2;

	/* this must be already check */
	IR_ASSERT(addr1 != addr2);

	/* check if addresses overlap */
	insn1 = ir_decompose_addr(ctx, addr1, &base1, &index1, &offset1);
	insn2 = ir_decompose_addr(ctx, addr2, &base2, &index2, &offset2);

	if (base1 == base2) {
		if (index1 != index2) {
			return IR_MAY_ALIAS;
		} else if (offset1 == offset2) {
			return IR_MUST_ALIAS;
		} else if (offset1 < offset2) {
			return offset1 + (intptr_t)ir_get_type_size(type1) <= offset2 ? IR_NO_ALIAS : IR_MUST_ALIAS;
		} else {
			return offset2 + (intptr_t)ir_get_type_size(type2) <= offset1 ? IR_NO_ALIAS : IR_MUST_ALIAS;
		}
	}

	/* check if addresses lay in different memory areas (e.g. local variables cannot alias with arguments) */
	insn1 = ir_get_base_addr(ctx, insn1);
	insn2 = ir_get_base_addr(ctx, insn2);

	if (insn1 == insn2 || insn1->type != IR_ADDR || insn2->type != IR_ADDR) {
		return IR_MAY_ALIAS;
	}

	if ((insn1->op == IR_ALLOCA && (insn2->op == IR_ALLOCA || insn2->op == IR_VADDR || insn2->op == IR_SYM || insn2->op == IR_PARAM))
	 || (insn1->op == IR_VADDR && (insn2->op == IR_ALLOCA || insn2->op == IR_VADDR || insn2->op == IR_SYM || insn2->op == IR_PARAM))
	 || (insn1->op == IR_SYM && (insn2->op == IR_ALLOCA || insn2->op == IR_VADDR || insn2->op == IR_SYM))
	 || (insn1->op == IR_PARAM && (insn2->op == IR_ALLOCA || insn2->op == IR_VADDR))) {
		return IR_NO_ALIAS;
	}

	return IR_MAY_ALIAS;
}

IR_ALWAYS_INLINE ir_ref ir_find_aliasing_load_i(const ir_ctx *ctx, ir_ref ref, ir_type type, ir_ref addr, ir_ref limit)
{
	const ir_insn *insn;
	uint32_t modified_regset = 0;

	while (ref > limit) {
		insn = &ctx->ir_base[ref];
		if (insn->op == IR_LOAD) {
			if (insn->op2 == addr) {
				if (insn->type == type) {
					return ref; /* load forwarding (L2L) */
				} else if (ir_get_type_size(insn->type) == ir_get_type_size(type)) {
					return ref; /* load forwarding with bitcast (L2L) */
				} else if (ir_get_type_size(insn->type) > ir_get_type_size(type)
						&& IR_IS_TYPE_INT(type) && IR_IS_TYPE_INT(insn->type)) {
					return ref; /* partial load forwarding (L2L) */
				}
			}
		} else if (insn->op == IR_STORE) {
			ir_type type2 = ctx->ir_base[insn->op3].type;

			if (insn->op2 == addr) {
				if (ctx->ir_base[insn->op3].op == IR_RLOAD
				 && (modified_regset & (1 << ctx->ir_base[insn->op3].op2))) {
					/* anti-dependency */
					return IR_UNUSED;
				} else if (type2 == type) {
					return insn->op3; /* store forwarding (S2L) */
				} else if (ir_get_type_size(type2) == ir_get_type_size(type)) {
					return insn->op3; /* store forwarding with bitcast (S2L) */
				} else if (ir_get_type_size(type2) > ir_get_type_size(type)
						&& IR_IS_TYPE_INT(type) && IR_IS_TYPE_INT(type2)) {
					return insn->op3; /* partial store forwarding (S2L) */
				} else {
					return IR_UNUSED;
				}
			} else if (ir_check_aliasing(ctx, addr, insn->op2, type, type2) != IR_NO_ALIAS) {
				return IR_UNUSED;
			}
		} else if (insn->op == IR_RSTORE) {
			modified_regset |= (1 << insn->op3);
		} else if (insn->op == IR_CALL) {
			const ir_insn *func = &ctx->ir_base[insn->op2];
			ir_ref func_proto;
			const ir_proto_t *proto;

			if (func->op == IR_FUNC || func->op == IR_FUNC_ADDR) {
				func_proto = func->proto;
			} else if (func->op == IR_PROTO) {
				func_proto = func->op2;
			} else {
				break;
			}
			if (!func_proto) {
				break;
			}
			proto = (const ir_proto_t *)ir_get_str(ctx, func_proto);
			if (!(proto->flags & (IR_CONST_FUNC|IR_PURE_FUNC))) {
				break;
			}
		} else if (insn->op == IR_MERGE
				|| insn->op == IR_LOOP_BEGIN
				|| insn->op == IR_VSTORE
				|| (insn->op == IR_BEGIN && insn->op2)) {
			return IR_UNUSED;
		}
		ref = insn->op1;
	}

	return IR_UNUSED;
}

ir_ref ir_find_aliasing_load(const ir_ctx *ctx, ir_ref ref, ir_type type, ir_ref addr)
{
	return ir_find_aliasing_load_i(ctx, ref, type, addr, (addr > 0 && addr < ref) ? addr : 1);
}

IR_ALWAYS_INLINE ir_ref ir_find_aliasing_vload_i(const ir_ctx *ctx, ir_ref ref, ir_type type, ir_ref var)
{
	const ir_insn *insn;

	while (ref > var) {
		insn = &ctx->ir_base[ref];
		if (insn->op == IR_VLOAD) {
			if (insn->op2 == var) {
				if (insn->type == type) {
					return ref; /* load forwarding (L2L) */
				} else if (ir_get_type_size(insn->type) > ir_get_type_size(type)) {
					return ref; /* load forwarding with bitcast (L2L) */
				} else if (ir_get_type_size(insn->type) > ir_get_type_size(type)
						&& IR_IS_TYPE_INT(type) && IR_IS_TYPE_INT(insn->type)) {
					return ref; /* partial load forwarding (L2L) */
				}
			}
		} else if (insn->op == IR_VSTORE) {
			ir_type type2 = ctx->ir_base[insn->op3].type;

			if (insn->op2 == var) {
				if (type2 == type) {
					return insn->op3; /* store forwarding (S2L) */
				} else if (ir_get_type_size(type2) == ir_get_type_size(type)) {
					return insn->op3; /* store forwarding with bitcast (S2L) */
				} else if (ir_get_type_size(type2) > ir_get_type_size(type)
						&& IR_IS_TYPE_INT(type) && IR_IS_TYPE_INT(type2)) {
					return insn->op3; /* partial store forwarding (S2L) */
				} else {
					break;
				}
			}
		} else if (insn->op == IR_CALL) {
			const ir_insn *func = &ctx->ir_base[insn->op2];
			ir_ref func_proto;
			const ir_proto_t *proto;

			if (func->op == IR_FUNC || func->op == IR_FUNC_ADDR) {
				func_proto = func->proto;
			} else if (func->op == IR_PROTO) {
				func_proto = func->op2;
			} else {
				break;
			}
			if (!func_proto) {
				break;
			}
			proto = (const ir_proto_t *)ir_get_str(ctx, func_proto);
			if (!(proto->flags & (IR_CONST_FUNC|IR_PURE_FUNC))) {
				break;
			}
		} else if (insn->op == IR_MERGE
				|| insn->op == IR_LOOP_BEGIN
				|| insn->op == IR_STORE
				|| (insn->op == IR_BEGIN && insn->op2)) {
			break;
		}
		ref = insn->op1;
	}

	return IR_UNUSED;
}

ir_ref ir_find_aliasing_vload(const ir_ctx *ctx, ir_ref ref, ir_type type, ir_ref var)
{
	return ir_find_aliasing_vload_i(ctx, ref, type, var);
}

IR_ALWAYS_INLINE ir_ref ir_find_aliasing_store_i(ir_ctx *ctx, ir_ref ref, ir_ref addr, ir_ref val, ir_ref limit)
{
	ir_ref next = IR_UNUSED;
	ir_insn *insn;
	ir_type type = ctx->ir_base[val].type;
	ir_type type2;
	bool guarded = 0;

//	if (!IR_IS_CONST_REF(val)) {
//		insn = &ctx->ir_base[val];
//		if (insn->op == IR_BITCAST
//		 && !IR_IS_CONST_REF(insn->op1)
//		 && ir_type_size[insn->type] == ir_type_size[ctx->ir_base[insn->op1].type]) {
//			/* skip BITCAST */
//			val = insn->op1;
//		}
//	}

	while (ref > limit) {
		insn = &ctx->ir_base[ref];
		if (insn->op == IR_STORE) {
			if (insn->op2 == addr) {
				if (ctx->ir_base[insn->op3].type == type) {
					if (insn->op3 == val) {
						/* dead STORE (store the same value once again) */
						return ref;
					} else {
						if (!guarded) {
							/* the previous STORE is dead (there are no LOADs) */
							if (!ctx->use_lists) {
								if (next) {
									ctx->ir_base[next].op1 = insn->op1;
								} else {
									ctx->control = insn->op1;
								}
							} else {
								ir_ref prev = insn->op1;

								if (!next) {
									IR_ASSERT(ctx->use_lists[ref].count == 1);
									next = ctx->use_edges[ctx->use_lists[ref].refs];
								}
								ctx->ir_base[next].op1 = prev;
								ir_use_list_remove_one(ctx, ref, next);
								ir_use_list_replace_one(ctx, prev, ref, next);
								if (!IR_IS_CONST_REF(insn->op2)) {
									ir_use_list_remove_one(ctx, insn->op2, ref);
									if (ctx->iter_worklist && ctx->use_lists[insn->op2].count == 0) {
										ir_bitqueue_add(ctx->iter_worklist, insn->op2);
									}
								}
								if (!IR_IS_CONST_REF(insn->op3)) {
									ir_use_list_remove_one(ctx, insn->op3, ref);
									if (ctx->iter_worklist && ctx->use_lists[insn->op3].count == 0) {
										ir_bitqueue_add(ctx->iter_worklist, insn->op3);
									}
								}
								insn->op1 = IR_UNUSED;
							}
							MAKE_NOP(insn);
						}
						break;
					}
				} else {
					break;
				}
			} else {
				type2 = ctx->ir_base[insn->op3].type;
				goto check_aliasing;
			}
		} else if (insn->op == IR_LOAD) {
			if (insn->op2 == addr) {
				if (ref == val) {
					/* dead STORE (store the value that was loaded before) */
					return ref;
				}
				break;
			}
			type2 = insn->type;
check_aliasing:
			if (ir_check_aliasing(ctx, addr, insn->op2, type, type2) != IR_NO_ALIAS) {
				break;
			}
		} else if (insn->op == IR_GUARD || insn->op == IR_GUARD_NOT) {
			guarded = 1;
		} else if (insn->op >= IR_START) {
			if (insn->op == IR_BEGIN && insn->op1 && !insn->op2) {
				/* skip END */
				ref = insn->op1;
				insn = &ctx->ir_base[ref];
			} else {
				break;
			}
		} else if (insn->op == IR_CALL) {
			break;
		}
		next = ref;
		ref = insn->op1;
	}

	return IR_UNUSED;
}

ir_ref ir_find_aliasing_store(ir_ctx *ctx, ir_ref ref, ir_ref addr, ir_ref val)
{
	return ir_find_aliasing_store_i(ctx, ref, addr, val, (addr > 0 && addr < ref) ? addr : 1);
}

IR_ALWAYS_INLINE ir_ref ir_find_aliasing_vstore_i(ir_ctx *ctx, ir_ref ref, ir_ref var, ir_ref val)
{
	ir_ref limit = var;
	ir_ref next = IR_UNUSED;
	ir_insn *insn;
	bool guarded = 0;

//	if (!IR_IS_CONST_REF(val)) {
//		insn = &ctx->ir_base[val];
//		if (insn->op == IR_BITCAST
//		 && !IR_IS_CONST_REF(insn->op1)
//		 && ir_type_size[insn->type] == ir_type_size[ctx->ir_base[insn->op1].type]) {
//			/* skip BITCAST */
//			val = insn->op1;
//		}
//	}

	while (ref > limit) {
		insn = &ctx->ir_base[ref];
		if (insn->op == IR_VSTORE) {
			if (insn->op2 == var) {
				if (insn->op3 == val) {
					/* dead VSTORE */
					return ref;
				} else {
					if (!guarded) {
						/* the previous VSTORE is dead (there are no VLOADs) */
						if (!ctx->use_lists) {
							if (next) {
								ctx->ir_base[next].op1 = insn->op1;
							} else {
								ctx->control = insn->op1;
							}
						} else {
							ir_ref prev = insn->op1;

							if (!next) {
								IR_ASSERT(ctx->use_lists[ref].count == 1);
								next = ctx->use_edges[ctx->use_lists[ref].refs];
							}
							ctx->ir_base[next].op1 = prev;
							ir_use_list_remove_one(ctx, ref, next);
							ir_use_list_replace_one(ctx, prev, ref, next);
							if (!IR_IS_CONST_REF(insn->op2)) {
								ir_use_list_remove_one(ctx, insn->op2, ref);
							}
							if (!IR_IS_CONST_REF(insn->op3)) {
								ir_use_list_remove_one(ctx, insn->op3, ref);
								if (ctx->iter_worklist && ctx->use_lists[insn->op3].count == 0) {
									ir_bitqueue_add(ctx->iter_worklist, insn->op3);
								}
							}
							insn->op1 = IR_UNUSED;
						}
						MAKE_NOP(insn);
					}
					break;
				}
			}
		} else if (insn->op == IR_VLOAD) {
			if (insn->op2 == var) {
				if (ref == val) {
					/* dead VSTORE */
					return ref;
				}
				break;
			}
		} else if (insn->op == IR_GUARD || insn->op == IR_GUARD_NOT) {
			guarded = 1;
		} else if (insn->op >= IR_START) {
			if (insn->op == IR_BEGIN && insn->op1 && !insn->op2) {
				/* skip END */
				ref = insn->op1;
				insn = &ctx->ir_base[ref];
			} else {
				break;
			}
		} else if (insn->op == IR_CALL || insn->op == IR_LOAD || insn->op == IR_STORE) {
			break;
		}
		next = ref;
		ref = insn->op1;
	}
	return IR_UNUSED;
}

ir_ref ir_find_aliasing_vstore(ir_ctx *ctx, ir_ref ref, ir_ref var, ir_ref val)
{
	return ir_find_aliasing_vstore_i(ctx, ref, var, val);
}

/* IR Construction API */
static ir_ref ir_last_guard(ir_ctx *ctx)
{
	ir_ref ref;
	ir_insn *insn;

	IR_ASSERT(ctx->control);
	ref = ctx->control;
	while (1) {
		insn = &ctx->ir_base[ref];
		if (IR_IS_BB_START(insn->op) || insn->op == IR_GUARD || insn->op == IR_GUARD_NOT) {
			if (insn->op == IR_START) ref = IR_UNUSED;
			break;
		}
		ref = insn->op1;
	}
	return ref;
}

ir_ref _ir_DIV(ir_ctx *ctx, ir_type type, ir_ref op1, ir_ref op2)
{
	ir_ref guard = (IR_IS_TYPE_FP(type) || (IR_IS_CONST_REF(op2) && ctx->ir_base[op2].val.u64 != 0)) ?
		IR_UNUSED : ir_last_guard(ctx);
	return ir_fold3(ctx, IR_OPT(IR_DIV, type), op1, op2, guard);
}

ir_ref _ir_MOD(ir_ctx *ctx, ir_type type, ir_ref op1, ir_ref op2)
{
	ir_ref guard = (IR_IS_CONST_REF(op2) && ctx->ir_base[op2].val.u64 != 0) ?
		IR_UNUSED : ir_last_guard(ctx);
	return ir_fold3(ctx, IR_OPT(IR_MOD, type), op1, op2, guard);
}

ir_ref _ir_PARAM(ir_ctx *ctx, ir_type type, const char* name, ir_ref num)
{
	IR_ASSERT(ctx->control);
	IR_ASSERT(ctx->ir_base[ctx->control].op == IR_START);
	IR_ASSERT(ctx->insns_count == num + 1);
	return ir_param(ctx, type, ctx->control, name, num);
}

ir_ref _ir_VAR(ir_ctx *ctx, ir_type type, const char* name)
{
//	IR_ASSERT(ctx->control);
//	IR_ASSERT(IR_IS_BB_START(ctx->ir_base[ctx->control].op));
//	TODO: VAR may be insterted after some "memory" instruction
	ir_ref ref = ctx->control;

	while (1) {
		IR_ASSERT(ref);
		if (IR_IS_BB_START(ctx->ir_base[ref].op)) {
			break;
		}
		ref = ctx->ir_base[ref].op1;
	}
	return ir_var(ctx, type, ref, name);
}

ir_ref _ir_PHI_2(ir_ctx *ctx, ir_type type, ir_ref src1, ir_ref src2)
{
	IR_ASSERT(ctx->control);
	IR_ASSERT(ctx->ir_base[ctx->control].op == IR_MERGE || ctx->ir_base[ctx->control].op == IR_LOOP_BEGIN);
	if (src1 == src2 && src1 != IR_UNUSED) {
		return src1;
	}
	return ir_emit3(ctx, IR_OPTX(IR_PHI, type, 3), ctx->control, src1, src2);
}

ir_ref _ir_PHI_N(ir_ctx *ctx, ir_type type, ir_ref n, ir_ref *inputs)
{
	IR_ASSERT(ctx->control);
	IR_ASSERT(n > 0);
	if (n == 1) {
		return inputs[0];
	} else {
	    ir_ref i;
		ir_ref ref;

		if (UNEXPECTED(!(ctx->flags & IR_OPT_FOLDING))) {
			IR_ASSERT(ctx->ir_base[ctx->control].op == IR_MERGE
				|| ctx->ir_base[ctx->control].op == IR_LOOP_BEGIN);
			ref = inputs[0];
			if (ref != IR_UNUSED) {
				for (i = 1; i < n; i++) {
					if (inputs[i] != ref) {
						break;
					}
				}
				if (i == n) {
					/* all the same */
					return ref;
				}
			}
		}

		ref = ir_emit_N(ctx, IR_OPT(IR_PHI, type), n + 1);
		ir_set_op(ctx, ref, 1, ctx->control);
		for (i = 0; i < n; i++) {
			ir_set_op(ctx, ref, i + 2, inputs[i]);
		}
		return ref;
	}
}

void _ir_PHI_SET_OP(ir_ctx *ctx, ir_ref phi, ir_ref pos, ir_ref src)
{
	ir_insn *insn = &ctx->ir_base[phi];
	ir_ref *ops = insn->ops;

	IR_ASSERT(insn->op == IR_PHI);
	IR_ASSERT(ctx->ir_base[insn->op1].op == IR_MERGE || ctx->ir_base[insn->op1].op == IR_LOOP_BEGIN);
	IR_ASSERT(pos > 0 && pos < insn->inputs_count);
	pos++; /* op1 is used for control */
	ops[pos] = src;
}

void _ir_START(ir_ctx *ctx)
{
	IR_ASSERT(!ctx->control);
	IR_ASSERT(ctx->insns_count == 1);
	ctx->control = ir_emit0(ctx, IR_START);
}

void _ir_ENTRY(ir_ctx *ctx, ir_ref src, ir_ref num)
{
	IR_ASSERT(!ctx->control);
	/* fake control edge */
	IR_ASSERT((ir_op_flags[ctx->ir_base[src].op] & IR_OP_FLAG_TERMINATOR)
		|| ctx->ir_base[src].op == IR_END
		|| ctx->ir_base[src].op == IR_LOOP_END); /* return from a recursive call */
	ctx->control = ir_emit2(ctx, IR_ENTRY, src, num);
}

void _ir_BEGIN(ir_ctx *ctx, ir_ref src)
{
	IR_ASSERT(!ctx->control);
	if (EXPECTED(ctx->flags & IR_OPT_FOLDING)
	 && src
	 && src + 1 == ctx->insns_count
	 && ctx->ir_base[src].op == IR_END) {
		/* merge with the last END */
		ctx->control = ctx->ir_base[src].op1;
		ctx->insns_count--;
	} else {
		ctx->control = ir_emit1(ctx, IR_BEGIN, src);
	}
}

static ir_ref _ir_fold_condition(const ir_ctx *ctx, ir_ref ref)
{
	const ir_insn *insn = &ctx->ir_base[ref];

	if (insn->op == IR_NE && IR_IS_CONST_REF(insn->op2)) {
		const ir_insn *op2_insn = &ctx->ir_base[insn->op2];

		if (IR_IS_TYPE_INT(op2_insn->type) && op2_insn->val.u64 == 0) {
			ref = insn->op1;
			insn = &ctx->ir_base[ref];
			if (insn->op == IR_ALLOCA || insn->op == IR_VADDR) {
				return IR_TRUE;
			}
		}
	} else if (insn->op == IR_EQ && insn->op2 == IR_TRUE) {
		ref = insn->op1;
		insn = &ctx->ir_base[ref];
	} else if (insn->op == IR_EQ && insn->op2 == IR_NULL) {
		const ir_insn *op1_insn = &ctx->ir_base[insn->op1];
		if (op1_insn->op == IR_ALLOCA || op1_insn->op == IR_VADDR) {
			return IR_FALSE;
		}
	}
//	while (insn->op == IR_SEXT || insn->op == IR_ZEXT || insn->op == IR_BITCAST) {
//		ref = insn->op1;
//		insn = &ctx->ir_base[ref];
//	}
	return ref;
}

IR_ALWAYS_INLINE ir_ref ir_check_dominating_predicates_i(const ir_ctx *ctx, ir_ref ref, ir_ref condition, ir_ref limit)
{
	const ir_insn *prev = NULL;
	const ir_insn *insn;

	while (ref > limit) {
		insn = &ctx->ir_base[ref];
		if (insn->op == IR_GUARD_NOT) {
			if (insn->op2 == condition) {
				return IR_FALSE;
			}
		} else if (insn->op == IR_GUARD) {
			if (insn->op2 == condition) {
				return IR_TRUE;
			}
		} else if (insn->op == IR_IF) {
			if (insn->op2 == condition) {
				if (prev->op == IR_IF_TRUE) {
					return IR_TRUE;
				} else if (prev->op == IR_IF_FALSE) {
					return IR_FALSE;
				}
			}
		} else if (insn->op == IR_START || insn->op == IR_MERGE || insn->op == IR_LOOP_BEGIN) {
			break;
		}
		prev = insn;
		ref = insn->op1;
	}

	return condition;
}

ir_ref ir_check_dominating_predicates(const ir_ctx *ctx, ir_ref ref, ir_ref condition)
{
	IR_ASSERT(!IR_IS_CONST_REF(condition));
	return ir_check_dominating_predicates_i(ctx, ref, condition, (condition < ref) ? condition : 1);
}

ir_ref _ir_IF(ir_ctx *ctx, ir_ref condition)
{
	ir_ref if_ref;

	IR_ASSERT(ctx->control);
	if (UNEXPECTED(!(ctx->flags & IR_OPT_FOLDING))) {
		if_ref = ir_emit2(ctx, IR_IF, ctx->control, condition);
		ctx->control = IR_UNUSED;
		return if_ref;
	}

	condition = _ir_fold_condition(ctx, condition);
	if (IR_IS_CONST_REF(condition)) {
		condition = ir_ref_is_true(ctx, condition) ? IR_TRUE : IR_FALSE;
	} else {
		condition = ir_check_dominating_predicates_i(ctx, ctx->control, condition, condition);
	}
	if_ref = ir_emit2(ctx, IR_IF, ctx->control, condition);
	ctx->control = IR_UNUSED;
	return if_ref;
}

void _ir_IF_TRUE(ir_ctx *ctx, ir_ref if_ref)
{
	IR_ASSERT(!ctx->control);
	IR_ASSERT(if_ref);
	IR_ASSERT(ctx->ir_base[if_ref].op == IR_IF);
	ctx->control = ir_emit1(ctx, IR_IF_TRUE, if_ref);
}

void _ir_IF_TRUE_cold(ir_ctx *ctx, ir_ref if_ref)
{
	IR_ASSERT(!ctx->control);
	IR_ASSERT(if_ref);
	IR_ASSERT(ctx->ir_base[if_ref].op == IR_IF);
	/* op2 is used as an indicator of low-probability branch */
	ctx->control = ir_emit2(ctx, IR_IF_TRUE, if_ref, 1);
}

void _ir_IF_FALSE(ir_ctx *ctx, ir_ref if_ref)
{
	IR_ASSERT(!ctx->control);
	IR_ASSERT(if_ref);
	IR_ASSERT(ctx->ir_base[if_ref].op == IR_IF);
	ctx->control = ir_emit1(ctx, IR_IF_FALSE, if_ref);
}

void _ir_IF_FALSE_cold(ir_ctx *ctx, ir_ref if_ref)
{
	IR_ASSERT(!ctx->control);
	IR_ASSERT(if_ref);
	IR_ASSERT(ctx->ir_base[if_ref].op == IR_IF);
	/* op2 is used as an indicator of low-probability branch */
	ctx->control = ir_emit2(ctx, IR_IF_FALSE, if_ref, 1);
}

ir_ref _ir_END(ir_ctx *ctx)
{
	ir_ref ref;

	IR_ASSERT(ctx->control);
	ref = ir_emit1(ctx, IR_END, ctx->control);
	ctx->control = IR_UNUSED;
	return ref;
}

void _ir_MERGE_2(ir_ctx *ctx, ir_ref src1, ir_ref src2)
{
	IR_ASSERT(!ctx->control);
	ctx->control = ir_emit2(ctx, IR_OPTX(IR_MERGE, IR_VOID, 2), src1, src2);
}

void _ir_MERGE_N(ir_ctx *ctx, ir_ref n, ir_ref *inputs)
{
	IR_ASSERT(!ctx->control);
	IR_ASSERT(n > 0);
	if (n == 1) {
		_ir_BEGIN(ctx, inputs[0]);
	} else {
		ir_ref *ops;

		ctx->control = ir_emit_N(ctx, IR_MERGE, n);
		ops = ctx->ir_base[ctx->control].ops;
		while (n) {
			n--;
			ops[n + 1] = inputs[n];
		}
	}
}

void _ir_MERGE_SET_OP(ir_ctx *ctx, ir_ref merge, ir_ref pos, ir_ref src)
{
	ir_insn *insn = &ctx->ir_base[merge];
	ir_ref *ops = insn->ops;

	IR_ASSERT(insn->op == IR_MERGE || insn->op == IR_LOOP_BEGIN);
	IR_ASSERT(pos > 0 && pos <= insn->inputs_count);
	ops[pos] = src;
}

ir_ref _ir_END_LIST(ir_ctx *ctx, ir_ref list)
{
	ir_ref ref;

	IR_ASSERT(ctx->control);
	IR_ASSERT(!list || ctx->ir_base[list].op == IR_END);
	/* create a liked list of END nodes with the same destination through END.op2 */
	ref = ir_emit2(ctx, IR_END, ctx->control, list);
	ctx->control = IR_UNUSED;
	return ref;
}

ir_ref _ir_END_PHI_LIST(ir_ctx *ctx, ir_ref list, ir_ref val)
{
	ir_ref ref;

	IR_ASSERT(ctx->control);
	IR_ASSERT(!list || ctx->ir_base[list].op == IR_END);
	/* create a liked list of END nodes with the same destination through END.op2 */
	ref = ir_emit3(ctx, IR_END, ctx->control, list, val);
	ctx->control = IR_UNUSED;
	return ref;
}

void _ir_MERGE_LIST(ir_ctx *ctx, ir_ref list)
{
	ir_ref ref = list;

	if (list != IR_UNUSED) {
		uint32_t n = 0;

		IR_ASSERT(!ctx->control);

		/* count inputs count */
		do {
			const ir_insn *insn = &ctx->ir_base[ref];

			IR_ASSERT(insn->op == IR_END);
			ref = insn->op2;
			n++;
		} while (ref != IR_UNUSED);


		/* create MERGE node */
		IR_ASSERT(n > 0);
		if (n == 1) {
			ctx->ir_base[list].op2 = IR_UNUSED;
			_ir_BEGIN(ctx, list);
		} else {
			ctx->control = ir_emit_N(ctx, IR_MERGE, n);
			ref = list;
			while (n) {
				ir_insn *insn = &ctx->ir_base[ref];

				ir_set_op(ctx, ctx->control, n, ref);
				ref = insn->op2;
				insn->op2 = IR_UNUSED;
				n--;
			}
		}
	}
}

ir_ref _ir_PHI_LIST(ir_ctx *ctx, ir_ref list)
{
	const ir_insn *merge;
	const ir_ref *ops;
	ir_insn *end;
	ir_ref phi, i;
	ir_type type;

	if (list == IR_UNUSED) {
		return IR_UNUSED;
	}
	end = &ctx->ir_base[list];
	if (!end->op2) {
		phi = end->op3;
		end->op3 = IR_UNUSED;
		_ir_BEGIN(ctx, list);
	} else if (!end->op3) {
		_ir_MERGE_LIST(ctx, list);
		phi = IR_UNUSED;
	} else {
		type = ctx->ir_base[end->op3].type;
		_ir_MERGE_LIST(ctx, list);
		merge = &ctx->ir_base[ctx->control];
		IR_ASSERT(merge->op == IR_MERGE);
		phi = ir_emit_N(ctx, IR_OPT(IR_PHI, type), merge->inputs_count + 1);
		merge = &ctx->ir_base[ctx->control];
		ops = merge->ops;
		ir_set_op(ctx, phi, 1, ctx->control);
		for (i = 0; i < merge->inputs_count; i++) {
			end = &ctx->ir_base[ops[i + 1]];
			ir_set_op(ctx, phi, i + 2, end->op3);
			end->op3 = IR_END;
		}
	}
	return phi;
}

ir_ref _ir_LOOP_BEGIN(ir_ctx *ctx, ir_ref src1)
{
	IR_ASSERT(!ctx->control);
	ctx->control = ir_emit2(ctx, IR_OPTX(IR_LOOP_BEGIN, IR_VOID, 2), src1, IR_UNUSED);
	return ctx->control;
}

ir_ref _ir_LOOP_END(ir_ctx *ctx)
{
	ir_ref ref;

	IR_ASSERT(ctx->control);
	ref = ir_emit1(ctx, IR_LOOP_END, ctx->control);
	ctx->control = IR_UNUSED;
	return ref;
}

ir_ref _ir_CALL(ir_ctx *ctx, ir_type type, ir_ref func)
{
	IR_ASSERT(ctx->control);
	return ctx->control = ir_emit2(ctx, IR_OPTX(IR_CALL, type, 2), ctx->control, func);
}

ir_ref _ir_CALL_1(ir_ctx *ctx, ir_type type, ir_ref func, ir_ref arg1)
{
	IR_ASSERT(ctx->control);
	return ctx->control = ir_emit3(ctx, IR_OPTX(IR_CALL, type, 3), ctx->control, func, arg1);
}

ir_ref _ir_CALL_2(ir_ctx *ctx, ir_type type, ir_ref func, ir_ref arg1, ir_ref arg2)
{
	ir_ref call;

	IR_ASSERT(ctx->control);
	call = ir_emit_N(ctx, IR_OPT(IR_CALL, type), 4);
	ir_set_op(ctx, call, 1, ctx->control);
	ir_set_op(ctx, call, 2, func);
	ir_set_op(ctx, call, 3, arg1);
	ir_set_op(ctx, call, 4, arg2);
	ctx->control = call;
	return call;
}

ir_ref _ir_CALL_3(ir_ctx *ctx, ir_type type, ir_ref func, ir_ref arg1, ir_ref arg2, ir_ref arg3)
{
	ir_ref call;

	IR_ASSERT(ctx->control);
	call = ir_emit_N(ctx, IR_OPT(IR_CALL, type), 5);
	ir_set_op(ctx, call, 1, ctx->control);
	ir_set_op(ctx, call, 2, func);
	ir_set_op(ctx, call, 3, arg1);
	ir_set_op(ctx, call, 4, arg2);
	ir_set_op(ctx, call, 5, arg3);
	ctx->control = call;
	return call;
}

ir_ref _ir_CALL_4(ir_ctx *ctx, ir_type type, ir_ref func, ir_ref arg1, ir_ref arg2, ir_ref arg3, ir_ref arg4)
{
	ir_ref call;

	IR_ASSERT(ctx->control);
	call = ir_emit_N(ctx, IR_OPT(IR_CALL, type), 6);
	ir_set_op(ctx, call, 1, ctx->control);
	ir_set_op(ctx, call, 2, func);
	ir_set_op(ctx, call, 3, arg1);
	ir_set_op(ctx, call, 4, arg2);
	ir_set_op(ctx, call, 5, arg3);
	ir_set_op(ctx, call, 6, arg4);
	ctx->control = call;
	return call;
}

ir_ref _ir_CALL_5(ir_ctx *ctx, ir_type type, ir_ref func, ir_ref arg1, ir_ref arg2, ir_ref arg3, ir_ref arg4, ir_ref arg5)
{
	ir_ref call;

	IR_ASSERT(ctx->control);
	call = ir_emit_N(ctx, IR_OPT(IR_CALL, type), 7);
	ir_set_op(ctx, call, 1, ctx->control);
	ir_set_op(ctx, call, 2, func);
	ir_set_op(ctx, call, 3, arg1);
	ir_set_op(ctx, call, 4, arg2);
	ir_set_op(ctx, call, 5, arg3);
	ir_set_op(ctx, call, 6, arg4);
	ir_set_op(ctx, call, 7, arg5);
	ctx->control = call;
	return call;
}

ir_ref _ir_CALL_6(ir_ctx *ctx, ir_type type, ir_ref func, ir_ref arg1, ir_ref arg2, ir_ref arg3, ir_ref arg4, ir_ref arg5, ir_ref arg6)
{
	ir_ref call;

	IR_ASSERT(ctx->control);
	call = ir_emit_N(ctx, IR_OPT(IR_CALL, type), 8);
	ir_set_op(ctx, call, 1, ctx->control);
	ir_set_op(ctx, call, 2, func);
	ir_set_op(ctx, call, 3, arg1);
	ir_set_op(ctx, call, 4, arg2);
	ir_set_op(ctx, call, 5, arg3);
	ir_set_op(ctx, call, 6, arg4);
	ir_set_op(ctx, call, 7, arg5);
	ir_set_op(ctx, call, 8, arg6);
	ctx->control = call;
	return call;
}

ir_ref _ir_CALL_N(ir_ctx *ctx, ir_type type, ir_ref func, uint32_t count, ir_ref *args)
{
	ir_ref call;
	uint32_t i;

	IR_ASSERT(ctx->control);
	call = ir_emit_N(ctx, IR_OPT(IR_CALL, type), count + 2);
	ir_set_op(ctx, call, 1, ctx->control);
	ir_set_op(ctx, call, 2, func);
	for (i = 0; i < count; i++) {
		ir_set_op(ctx, call, i + 3, args[i]);
	}
	ctx->control = call;
	return call;
}

void _ir_UNREACHABLE(ir_ctx *ctx)
{
	IR_ASSERT(ctx->control);
	ctx->control = ir_emit3(ctx, IR_UNREACHABLE, ctx->control, IR_UNUSED, ctx->ir_base[1].op1);
	ctx->ir_base[1].op1 = ctx->control;
	ctx->control = IR_UNUSED;
}

void _ir_TAILCALL(ir_ctx *ctx, ir_type type, ir_ref func)
{
	IR_ASSERT(ctx->control);
	if (ctx->ret_type == (ir_type)-1) {
		ctx->ret_type = type;
	}
	IR_ASSERT(ctx->ret_type == type && "conflicting return type");
	ctx->control = ir_emit2(ctx, IR_OPTX(IR_TAILCALL, type, 2), ctx->control, func);
	_ir_UNREACHABLE(ctx);
}

void _ir_TAILCALL_1(ir_ctx *ctx, ir_type type, ir_ref func, ir_ref arg1)
{
	IR_ASSERT(ctx->control);
	if (ctx->ret_type == (ir_type)-1) {
		ctx->ret_type = type;
	}
	IR_ASSERT(ctx->ret_type == type && "conflicting return type");
	ctx->control = ir_emit3(ctx, IR_OPTX(IR_TAILCALL, type, 3), ctx->control, func, arg1);
	_ir_UNREACHABLE(ctx);
}

void _ir_TAILCALL_2(ir_ctx *ctx, ir_type type, ir_ref func, ir_ref arg1, ir_ref arg2)
{
	ir_ref call;

	IR_ASSERT(ctx->control);
	if (ctx->ret_type == (ir_type)-1) {
		ctx->ret_type = type;
	}
	IR_ASSERT(ctx->ret_type == type && "conflicting return type");
	call = ir_emit_N(ctx, IR_OPT(IR_TAILCALL, type), 4);
	ir_set_op(ctx, call, 1, ctx->control);
	ir_set_op(ctx, call, 2, func);
	ir_set_op(ctx, call, 3, arg1);
	ir_set_op(ctx, call, 4, arg2);
	ctx->control = call;
	_ir_UNREACHABLE(ctx);
}

void _ir_TAILCALL_3(ir_ctx *ctx, ir_type type, ir_ref func, ir_ref arg1, ir_ref arg2, ir_ref arg3)
{
	ir_ref call;

	IR_ASSERT(ctx->control);
	if (ctx->ret_type == (ir_type)-1) {
		ctx->ret_type = type;
	}
	IR_ASSERT(ctx->ret_type == type && "conflicting return type");
	call = ir_emit_N(ctx, IR_OPT(IR_TAILCALL, type), 5);
	ir_set_op(ctx, call, 1, ctx->control);
	ir_set_op(ctx, call, 2, func);
	ir_set_op(ctx, call, 3, arg1);
	ir_set_op(ctx, call, 4, arg2);
	ir_set_op(ctx, call, 5, arg3);
	ctx->control = call;
	_ir_UNREACHABLE(ctx);
}

void _ir_TAILCALL_4(ir_ctx *ctx, ir_type type, ir_ref func, ir_ref arg1, ir_ref arg2, ir_ref arg3, ir_ref arg4)
{
	ir_ref call;

	IR_ASSERT(ctx->control);
	if (ctx->ret_type == (ir_type)-1) {
		ctx->ret_type = type;
	}
	IR_ASSERT(ctx->ret_type == type && "conflicting return type");
	call = ir_emit_N(ctx, IR_OPT(IR_TAILCALL, type), 6);
	ir_set_op(ctx, call, 1, ctx->control);
	ir_set_op(ctx, call, 2, func);
	ir_set_op(ctx, call, 3, arg1);
	ir_set_op(ctx, call, 4, arg2);
	ir_set_op(ctx, call, 5, arg3);
	ir_set_op(ctx, call, 6, arg4);
	ctx->control = call;
	_ir_UNREACHABLE(ctx);
}

void _ir_TAILCALL_5(ir_ctx *ctx, ir_type type, ir_ref func, ir_ref arg1, ir_ref arg2, ir_ref arg3, ir_ref arg4, ir_ref arg5)
{
	ir_ref call;

	IR_ASSERT(ctx->control);
	if (ctx->ret_type == (ir_type)-1) {
		ctx->ret_type = type;
	}
	IR_ASSERT(ctx->ret_type == type && "conflicting return type");
	call = ir_emit_N(ctx, IR_OPT(IR_TAILCALL, type), 7);
	ir_set_op(ctx, call, 1, ctx->control);
	ir_set_op(ctx, call, 2, func);
	ir_set_op(ctx, call, 3, arg1);
	ir_set_op(ctx, call, 4, arg2);
	ir_set_op(ctx, call, 5, arg3);
	ir_set_op(ctx, call, 6, arg4);
	ir_set_op(ctx, call, 7, arg5);
	ctx->control = call;
	_ir_UNREACHABLE(ctx);
}

void _ir_TAILCALL_6(ir_ctx *ctx, ir_type type, ir_ref func, ir_ref arg1, ir_ref arg2, ir_ref arg3, ir_ref arg4, ir_ref arg5, ir_ref arg6)
{
	ir_ref call;

	IR_ASSERT(ctx->control);
	if (ctx->ret_type == (ir_type)-1) {
		ctx->ret_type = type;
	}
	IR_ASSERT(ctx->ret_type == type && "conflicting return type");
	call = ir_emit_N(ctx, IR_OPT(IR_TAILCALL, type), 8);
	ir_set_op(ctx, call, 1, ctx->control);
	ir_set_op(ctx, call, 2, func);
	ir_set_op(ctx, call, 3, arg1);
	ir_set_op(ctx, call, 4, arg2);
	ir_set_op(ctx, call, 5, arg3);
	ir_set_op(ctx, call, 6, arg4);
	ir_set_op(ctx, call, 7, arg5);
	ir_set_op(ctx, call, 8, arg6);
	ctx->control = call;
	_ir_UNREACHABLE(ctx);
}

void _ir_TAILCALL_N(ir_ctx *ctx, ir_type type, ir_ref func, uint32_t count, ir_ref *args)
{
	ir_ref call;
	uint32_t i;

	IR_ASSERT(ctx->control);
	if (ctx->ret_type == (ir_type)-1) {
		ctx->ret_type = type;
	}
	IR_ASSERT(ctx->ret_type == type && "conflicting return type");
	call = ir_emit_N(ctx, IR_OPT(IR_TAILCALL, type), count + 2);
	ir_set_op(ctx, call, 1, ctx->control);
	ir_set_op(ctx, call, 2, func);
	for (i = 0; i < count; i++) {
		ir_set_op(ctx, call, i + 3, args[i]);
	}
	ctx->control = call;
	_ir_UNREACHABLE(ctx);
}

ir_ref _ir_SWITCH(ir_ctx *ctx, ir_ref val)
{
	ir_ref ref;

	IR_ASSERT(ctx->control);
	ref = ir_emit2(ctx, IR_SWITCH, ctx->control, val);
	ctx->control = IR_UNUSED;
	return ref;
}

void _ir_CASE_VAL(ir_ctx *ctx, ir_ref switch_ref, ir_ref val)
{
	IR_ASSERT(!ctx->control);
	ctx->control = ir_emit2(ctx, IR_CASE_VAL, switch_ref, val);
}

void _ir_CASE_RANGE(ir_ctx *ctx, ir_ref switch_ref, ir_ref v1, ir_ref v2)
{
	IR_ASSERT(!ctx->control);
	ctx->control = ir_emit3(ctx, IR_CASE_RANGE, switch_ref, v1, v2);
}

void _ir_CASE_DEFAULT(ir_ctx *ctx, ir_ref switch_ref)
{
	IR_ASSERT(!ctx->control);
	ctx->control = ir_emit1(ctx, IR_CASE_DEFAULT, switch_ref);
}

void _ir_RETURN(ir_ctx *ctx, ir_ref val)
{
	ir_type type = (val != IR_UNUSED) ? ctx->ir_base[val].type : IR_VOID;

	IR_ASSERT(ctx->control);
	if (ctx->ret_type == (ir_type)-1) {
		ctx->ret_type = type;
	}
	IR_ASSERT(ctx->ret_type == type && "conflicting return type");
	ctx->control = ir_emit3(ctx, IR_RETURN, ctx->control, val, ctx->ir_base[1].op1);
	ctx->ir_base[1].op1 = ctx->control;
	ctx->control = IR_UNUSED;
}

void _ir_IJMP(ir_ctx *ctx, ir_ref addr)
{
	IR_ASSERT(ctx->control);
	ctx->control = ir_emit3(ctx, IR_IJMP, ctx->control, addr, ctx->ir_base[1].op1);
	ctx->ir_base[1].op1 = ctx->control;
	ctx->control = IR_UNUSED;
}

ir_ref _ir_IGOTO(ir_ctx *ctx, ir_ref addr)
{
	ir_ref ref;

	IR_ASSERT(ctx->control);
	ctx->control = ref = ir_emit2(ctx, IR_IGOTO, ctx->control, addr);
	ctx->control = IR_UNUSED;
	return ref;
}

ir_ref _ir_ADD_OFFSET(ir_ctx *ctx, ir_ref addr, uintptr_t offset)
{
	if (offset) {
		addr = ir_fold2(ctx, IR_OPT(IR_ADD, IR_ADDR), addr, ir_const_addr(ctx, offset));
	}
	return addr;
}

void _ir_GUARD(ir_ctx *ctx, ir_ref condition, ir_ref addr)
{
	IR_ASSERT(ctx->control);
	if (IR_IS_CONST_REF(condition)) {
		if (ir_ref_is_true(ctx, condition)) {
			return;
		}
		condition = IR_FALSE;
	} else if (EXPECTED(ctx->flags & IR_OPT_FOLDING)) {
		condition = ir_check_dominating_predicates_i(ctx, ctx->control, condition, condition);
		if (condition == IR_TRUE) {
			return;
		}
	}
	if (ctx->snapshot_create) {
		ctx->snapshot_create(ctx, addr);
	}
	ctx->control = ir_emit3(ctx, IR_GUARD, ctx->control, condition, addr);
}

void _ir_GUARD_NOT(ir_ctx *ctx, ir_ref condition, ir_ref addr)
{
	IR_ASSERT(ctx->control);
	if (IR_IS_CONST_REF(condition)) {
		if (!ir_ref_is_true(ctx, condition)) {
			return;
		}
		condition = IR_TRUE;
	} else if (EXPECTED(ctx->flags & IR_OPT_FOLDING)) {
		condition = ir_check_dominating_predicates_i(ctx, ctx->control, condition, condition);
		if (condition == IR_FALSE) {
			return;
		}
	}
	if (ctx->snapshot_create) {
		ctx->snapshot_create(ctx, addr);
	}
	ctx->control = ir_emit3(ctx, IR_GUARD_NOT, ctx->control, condition, addr);
}

ir_ref _ir_SNAPSHOT(ir_ctx *ctx, ir_ref n)
{
	ir_ref snapshot;

	IR_ASSERT(ctx->control);
	snapshot = ir_emit_N(ctx, IR_SNAPSHOT, 1 + n); /* op1 is used for control */
	ctx->ir_base[snapshot].op1 = ctx->control;
	ctx->control = snapshot;
	return snapshot;
}

void _ir_SNAPSHOT_SET_OP(ir_ctx *ctx, ir_ref snapshot, ir_ref pos, ir_ref val)
{
	ir_insn *insn = &ctx->ir_base[snapshot];
	ir_ref *ops = insn->ops;

	IR_ASSERT(val < snapshot);
	IR_ASSERT(insn->op == IR_SNAPSHOT);
	pos++; /* op1 is used for control */
	IR_ASSERT(pos > 1 && pos <= insn->inputs_count);
	ops[pos] = val;
}

ir_ref _ir_EXITCALL(ir_ctx *ctx, ir_ref func)
{
	IR_ASSERT(ctx->control);
	return ctx->control = ir_emit2(ctx, IR_OPT(IR_EXITCALL, IR_I32), ctx->control, func);
}

ir_ref _ir_ALLOCA(ir_ctx *ctx, ir_ref size)
{
	IR_ASSERT(ctx->control);
	return ctx->control = ir_emit2(ctx, IR_OPT(IR_ALLOCA, IR_ADDR), ctx->control, size);
}

void _ir_AFREE(ir_ctx *ctx, ir_ref size)
{
	IR_ASSERT(ctx->control);
	ctx->control = ir_emit2(ctx, IR_AFREE, ctx->control, size);
}

ir_ref _ir_VLOAD(ir_ctx *ctx, ir_type type, ir_ref var)
{
	ir_ref ref;

	IR_ASSERT(ctx->control);
	if (EXPECTED(ctx->flags & IR_OPT_FOLDING)) {
		ref = ir_find_aliasing_vload_i(ctx, ctx->control, type, var);
		if (ref) {
			const ir_insn *insn = &ctx->ir_base[ref];

			if (insn->type == type) {
				return ref;
			} else if (ir_get_type_size(insn->type) == ir_get_type_size(type)) {
				return ir_fold1(ctx, IR_OPT(IR_BITCAST, type), ref); /* load forwarding with bitcast (L2L) */
			} else {
				return ir_fold1(ctx, IR_OPT(IR_TRUNC, type), ref); /* partial load forwarding (L2L) */
			}
		}
	}
	return ctx->control = ir_emit2(ctx, IR_OPT(IR_VLOAD, type), ctx->control, var);
}

void _ir_VSTORE(ir_ctx *ctx, ir_ref var, ir_ref val)
{
	IR_ASSERT(ctx->control);
	if (EXPECTED(ctx->flags & IR_OPT_FOLDING)) {
		if (ir_find_aliasing_vstore_i(ctx, ctx->control, var, val)) {
			/* dead STORE */
			return;
		}
	}
	ctx->control = ir_emit3(ctx, IR_VSTORE, ctx->control, var, val);
}

ir_ref _ir_VLOAD_v(ir_ctx *ctx, ir_type type, ir_ref var)
{
	IR_ASSERT(ctx->control);
	return ctx->control = ir_emit2(ctx, IR_OPT(IR_VLOAD_v, type), ctx->control, var);
}

void _ir_VSTORE_v(ir_ctx *ctx, ir_ref var, ir_ref val)
{
	IR_ASSERT(ctx->control);
	ctx->control = ir_emit3(ctx, IR_VSTORE_v, ctx->control, var, val);
}

ir_ref _ir_TLS_ADDR(ir_ctx *ctx, ir_ref index, ir_ref offset)
{
	IR_ASSERT(ctx->control);
	return ctx->control = ir_emit3(ctx, IR_OPT(IR_TLS_ADDR, IR_ADDR), ctx->control, index, offset);
}

ir_ref _ir_RLOAD(ir_ctx *ctx, ir_type type, ir_ref reg)
{
	IR_ASSERT(ctx->control);
	return ctx->control = ir_emit2(ctx, IR_OPT(IR_RLOAD, type), ctx->control, reg);
}

void _ir_RSTORE(ir_ctx *ctx, ir_ref reg, ir_ref val)
{
	IR_ASSERT(ctx->control);
	ctx->control = ir_emit3(ctx, IR_RSTORE, ctx->control, val, reg);
}

ir_ref _ir_LOAD(ir_ctx *ctx, ir_type type, ir_ref addr)
{
	ir_ref ref;

	IR_ASSERT(ctx->control);
	if (EXPECTED(ctx->flags & IR_OPT_FOLDING)) {
		if (ctx->ir_base[addr].op == IR_VADDR) {
			return _ir_VLOAD(ctx, type, ctx->ir_base[addr].op1);
		}
		ref = ir_find_aliasing_load_i(ctx, ctx->control, type, addr, (addr > 0) ? addr : 1);
		if (ref) {
			const ir_insn *insn = &ctx->ir_base[ref];

			if (insn->type == type) {
				return ref;
			} else if (ir_get_type_size(insn->type) == ir_get_type_size(type)) {
				return ir_fold1(ctx, IR_OPT(IR_BITCAST, type), ref); /* load forwarding with bitcast (L2L) */
			} else {
				return ir_fold1(ctx, IR_OPT(IR_TRUNC, type), ref); /* partial load forwarding (L2L) */
			}
		}
	}
	return ctx->control = ir_emit2(ctx, IR_OPT(IR_LOAD, type), ctx->control, addr);
}

void _ir_STORE(ir_ctx *ctx, ir_ref addr, ir_ref val)
{
	IR_ASSERT(ctx->control);
	if (EXPECTED(ctx->flags & IR_OPT_FOLDING)) {
		if (ctx->ir_base[addr].op == IR_VADDR) {
			_ir_VSTORE(ctx, ctx->ir_base[addr].op1, val);
			return;
		}
		if (ir_find_aliasing_store_i(ctx, ctx->control, addr, val, (addr > 0) ? addr : 1)) {
			/* dead STORE */
			return;
		}
	}
	ctx->control = ir_emit3(ctx, IR_STORE, ctx->control, addr, val);
}

ir_ref _ir_LOAD_v(ir_ctx *ctx, ir_type type, ir_ref addr)
{
	IR_ASSERT(ctx->control);
	return ctx->control = ir_emit2(ctx, IR_OPT(IR_LOAD_v, type), ctx->control, addr);
}

void _ir_STORE_v(ir_ctx *ctx, ir_ref addr, ir_ref val)
{
	IR_ASSERT(ctx->control);
	ctx->control = ir_emit3(ctx, IR_STORE_v, ctx->control, addr, val);
}

void _ir_VA_START(ir_ctx *ctx, ir_ref list)
{
	IR_ASSERT(ctx->control);
	ctx->control = ir_emit2(ctx, IR_VA_START, ctx->control, list);
}

void _ir_VA_END(ir_ctx *ctx, ir_ref list)
{
	IR_ASSERT(ctx->control);
	ctx->control = ir_emit2(ctx, IR_VA_END, ctx->control, list);
}

void _ir_VA_COPY(ir_ctx *ctx, ir_ref dst, ir_ref src)
{
	IR_ASSERT(ctx->control);
	ctx->control = ir_emit3(ctx, IR_VA_COPY, ctx->control, dst, src);
}

ir_ref _ir_VA_ARG(ir_ctx *ctx, ir_type type, ir_ref list)
{
	IR_ASSERT(ctx->control);
	return ctx->control = ir_emit2(ctx, IR_OPT(IR_VA_ARG, type), ctx->control, list);
}

ir_ref _ir_VA_ARG_EX(ir_ctx *ctx, ir_type type, ir_ref list, size_t size, size_t align)
{
	IR_ASSERT(ctx->control);
	IR_ASSERT(size <= 0x0fffffff);
	IR_ASSERT(align != 0 && ((align & (align - 1)) == 0) && align <= 128);
	return ctx->control = ir_emit3(ctx, IR_OPT(IR_VA_ARG, type), ctx->control, list,
		(ir_ref)IR_VA_ARG_OP3(size, align));
}

ir_ref _ir_BLOCK_BEGIN(ir_ctx *ctx)
{
	IR_ASSERT(ctx->control);
	return ctx->control = ir_emit1(ctx, IR_OPT(IR_BLOCK_BEGIN, IR_ADDR), ctx->control);
}