/src/php-src/ext/opcache/jit/ir/ir_check.c

Source
/*
 * IR - Lightweight JIT Compilation Framework
 * (IR verification)
 * This file is part of the IR Project distributed under the MIT-style LICENSE.
 * Authors: Dmitry Stogov <dmitry@php.net>
 */

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

void ir_consistency_check(void)
{
  IR_ASSERT(IR_UNUSED == 0);
  IR_ASSERT(IR_NOP == 0);

  IR_ASSERT((int)IR_BOOL   == (int)IR_C_BOOL);
  IR_ASSERT((int)IR_U8     == (int)IR_C_U8);
  IR_ASSERT((int)IR_U16    == (int)IR_C_U16);
  IR_ASSERT((int)IR_U32    == (int)IR_C_U32);
  IR_ASSERT((int)IR_U64    == (int)IR_C_U64);
  IR_ASSERT((int)IR_ADDR   == (int)IR_C_ADDR);
  IR_ASSERT((int)IR_CHAR   == (int)IR_C_CHAR);
  IR_ASSERT((int)IR_I8     == (int)IR_C_I8);
  IR_ASSERT((int)IR_I16    == (int)IR_C_I16);
  IR_ASSERT((int)IR_I32    == (int)IR_C_I32);
  IR_ASSERT((int)IR_I64    == (int)IR_C_I64);
  IR_ASSERT((int)IR_DOUBLE == (int)IR_C_DOUBLE);
  IR_ASSERT((int)IR_FLOAT  == (int)IR_C_FLOAT);

  IR_ASSERT((IR_EQ ^ 1) == IR_NE);
  IR_ASSERT((IR_LT ^ 3) == IR_GT);
  IR_ASSERT((IR_GT ^ 3) == IR_LT);
  IR_ASSERT((IR_LE ^ 3) == IR_GE);
  IR_ASSERT((IR_GE ^ 3) == IR_LE);
  IR_ASSERT((IR_ULT ^ 3) == IR_UGT);
  IR_ASSERT((IR_UGT ^ 3) == IR_ULT);
  IR_ASSERT((IR_ULE ^ 3) == IR_UGE);
  IR_ASSERT((IR_UGE ^ 3) == IR_ULE);
  IR_ASSERT((IR_ORDERED ^ 1) == IR_UNORDERED);

  IR_ASSERT(IR_ADD + 1 == IR_SUB);
}

typedef struct {
  ir_arena  *arena;
  ir_bitset *use_set;
  ir_bitset *input_set;
} ir_check_ctx;

static bool ir_check_use_list(ir_check_ctx *check_ctx, const ir_ctx *ctx, ir_ref from, ir_ref to)
{
  ir_ref n, *p;
  ir_use_list *use_list = &ctx->use_lists[from];

  n = use_list->count;
  if (n > 16) {
    /* Avoid quadratic complexity by maintaining a temporary bit-set */
    ir_bitset set;

    if (!check_ctx->use_set || !(set = check_ctx->use_set[from])) {
      if (!check_ctx->arena) {
        check_ctx->arena = ir_arena_create(sizeof(ir_arena) +
          ctx->insns_count * sizeof(ir_bitset) +
          ir_bitset_len(ctx->insns_count) * sizeof(ir_bitset_base_t));
      }
      if (!check_ctx->use_set) {
        check_ctx->use_set = ir_arena_alloc(&check_ctx->arena, ctx->insns_count * sizeof(ir_bitset));
        memset(check_ctx->use_set, 0, ctx->insns_count * sizeof(ir_bitset));
      }
      check_ctx->use_set[from] = set = (ir_bitset)ir_arena_alloc(&check_ctx->arena,
        ir_bitset_len(ctx->insns_count) * sizeof(ir_bitset_base_t));
      memset(set, 0, ir_bitset_len(ctx->insns_count) * sizeof(ir_bitset_base_t));
      for (p = &ctx->use_edges[use_list->refs]; n > 0; p++, n--) {
        ir_bitset_incl(set, *p);
      }
    }
    return ir_bitset_in(set, to);
  }
  for (p = &ctx->use_edges[use_list->refs]; n > 0; p++, n--) {
    if (*p == to) {
      return 1;
    }
  }
  return 0;
}

static bool ir_check_input_list(ir_check_ctx *check_ctx, const ir_ctx *ctx, ir_ref from, ir_ref to)
{
  ir_insn *insn = &ctx->ir_base[to];
  ir_ref n, j, *p;

  n = ir_input_edges_count(ctx, insn);
  if (n > 16) {
    /* Avoid quadratic complexity by maintaining a temporary bit-set */
    ir_bitset set;

    if (!check_ctx->input_set || !(set = check_ctx->input_set[to])) {
      if (!check_ctx->arena) {
        check_ctx->arena = ir_arena_create(sizeof(ir_arena) +
          ctx->insns_count * sizeof(ir_bitset) +
          ir_bitset_len(ctx->insns_count) * sizeof(ir_bitset_base_t));
      }
      if (!check_ctx->input_set) {
        check_ctx->input_set = ir_arena_alloc(&check_ctx->arena, ctx->insns_count * sizeof(ir_bitset));
        memset(check_ctx->input_set, 0, ctx->insns_count * sizeof(ir_bitset));
      }
      check_ctx->input_set[to] = set = (ir_bitset)ir_arena_alloc(&check_ctx->arena,
        ir_bitset_len(ctx->insns_count) * sizeof(ir_bitset_base_t));
      memset(set, 0, ir_bitset_len(ctx->insns_count) * sizeof(ir_bitset_base_t));
      for (j = 1, p = insn->ops + 1; j <= n; j++, p++) {
        if (*p > 0) ir_bitset_incl(set, *p);
      }
    }
    return ir_bitset_in(set, from);
  }
  for (j = 1, p = insn->ops + 1; j <= n; j++, p++) {
    if (*p == from) {
      return 1;
    }
  }
  return 0;
}

static bool ir_check_domination(const ir_ctx *ctx, ir_ref def, ir_ref use)
{
  uint32_t b1 = ctx->cfg_map[def];
  uint32_t b2 = ctx->cfg_map[use];
  ir_block *blocks = ctx->cfg_blocks;
  uint32_t b1_depth = blocks[b1].dom_depth;
  const ir_block *bb2 = &blocks[b2];

  if (b1 == b2) {
    return def < use;
  }
  while (bb2->dom_depth > b1_depth) {
    b2 = bb2->dom_parent;
    bb2 = &blocks[b2];
  }
  return b1 == b2;
}

bool ir_check(const ir_ctx *ctx)
{
  ir_ref i, j, n, *p, use;
  ir_insn *insn, *use_insn;
  ir_type type;
  uint32_t flags;
  bool ok = 1;
  ir_check_ctx check_ctx;

  if (ctx->insns_count < 1 || ctx->ir_base[1].op != IR_START) {
    fprintf(stderr, "ir_base[1].op invalid opcode (%d)\n",
      (ctx->insns_count < 1) ? IR_NOP : ctx->ir_base[0].op);
    ok = 0;
  }

  check_ctx.arena = NULL;
  check_ctx.use_set = NULL;
  check_ctx.input_set = NULL;

  for (i = IR_UNUSED + 1, insn = ctx->ir_base + i; i < ctx->insns_count;) {
    if (insn->op >= IR_LAST_OP) {
      fprintf(stderr, "ir_base[%d].op invalid opcode (%d)\n", i, insn->op);
      ok = 0;
      break;
    }
    flags = ir_op_flags[insn->op];
    n = ir_input_edges_count(ctx, insn);
    for (j = 1, p = insn->ops + 1; j <= n; j++, p++) {
      use = *p;
      if (use != IR_UNUSED) {
        if (IR_IS_CONST_REF(use)) {
          if (IR_OPND_KIND(flags, j) != IR_OPND_DATA) {
            fprintf(stderr, "ir_base[%d].ops[%d] reference (%d) must not be constant\n", i, j, use);
            ok = 0;
          } else if (-use >= ctx->consts_count) {
            fprintf(stderr, "ir_base[%d].ops[%d] constant reference (%d) is out of range\n", i, j, use);
            ok = 0;
          }
        } else {
          if (use >= ctx->insns_count) {
            fprintf(stderr, "ir_base[%d].ops[%d] insn reference (%d) is out of range\n", i, j, use);
            ok = 0;
            continue;
          }
          use_insn = &ctx->ir_base[use];
          switch (IR_OPND_KIND(flags, j)) {
            case IR_OPND_DATA:
              if (!(ir_op_flags[use_insn->op] & IR_OP_FLAG_DATA)) {
                if (!(ir_op_flags[use_insn->op] & IR_OP_FLAG_MEM)
                 || use_insn->type == IR_VOID) {
                  fprintf(stderr, "ir_base[%d].ops[%d] reference (%d) must be DATA\n", i, j, use);
                  ok = 0;
                }
              }
              if ((ctx->flags2 & IR_LINEAR)
               && use >= i
               && !(insn->op == IR_PHI && ctx->ir_base[insn->op1].op == IR_LOOP_BEGIN)) {
                fprintf(stderr, "ir_base[%d].ops[%d] invalid forward reference (%d)\n", i, j, use);
                ok = 0;
              }
              if (flags & IR_OP_FLAG_DATA) {
                switch (insn->op) {
                  case IR_COND:
                    if (j == 1) {
                      break;
                    }
                    IR_FALLTHROUGH;
                  case IR_ADD:
                  case IR_SUB:
                  case IR_MUL:
                  case IR_DIV:
                  case IR_MOD:
                  case IR_NEG:
                  case IR_ABS:
                  case IR_ADD_OV:
                  case IR_SUB_OV:
                  case IR_MUL_OV:
                  case IR_NOT:
                  case IR_OR:
                  case IR_AND:
                  case IR_XOR:
                  case IR_SHL:
                  case IR_SHR:
                  case IR_SAR:
                  case IR_ROL:
                  case IR_ROR:
                  case IR_BSWAP:
                  case IR_MIN:
                  case IR_MAX:
                  case IR_PHI:
                  case IR_COPY:
                  case IR_PI:
                    if (insn->type != use_insn->type) {
                      if (j == 2
                       && (insn->op == IR_SHL
                        || insn->op == IR_SHR
                        || insn->op == IR_SAR
                        || insn->op == IR_ROL
                        || insn->op == IR_ROR)
                       && IR_IS_TYPE_INT(use_insn->type)
                       && (IR_IS_TYPE_INT(insn->type) || IR_IS_TYPE_VECTOR(insn->type))) {
                        /* second argument of SHIFT may be incompatible with result */
                        break;
                      }
                      if (insn->op == IR_NOT && insn->type == IR_BOOL) {
                        /* boolean not */
                        break;
                      }
                      if (insn->type == IR_ADDR && (use_insn->type == IR_UINTPTR_T || use_insn->type == IR_INTPTR_T)) {
                        break;
                      } else if (use_insn->type == IR_ADDR && (insn->type == IR_UINTPTR_T || insn->type == IR_INTPTR_T)) {
                        break;
                      }
                      fprintf(stderr, "ir_base[%d].ops[%d] (%d) type is incompatible with result type (%d != %d)\n",
                        i, j, use, use_insn->type, insn->type);
                      ok = 0;
                    }
                    break;
                }
              }
              if ((ctx->flags2 & IR_LINEAR)
               && ctx->cfg_map
               && insn->op != IR_PHI
               && !ir_check_domination(ctx, use, i)) {
                fprintf(stderr, "ir_base[%d].ops[%d] -> %d, %d doesn't dominate %d\n", i, j, use, use, i);
                ok = 0;
              }
              break;
            case IR_OPND_CONTROL:
              if (flags & IR_OP_FLAG_BB_START) {
                if (!(ir_op_flags[use_insn->op] & IR_OP_FLAG_BB_END)) {
                  fprintf(stderr, "ir_base[%d].ops[%d] reference (%d) must be BB_END\n", i, j, use);
                  ok = 0;
                }
              } else {
                if (ir_op_flags[use_insn->op] & IR_OP_FLAG_BB_END) {
                  fprintf(stderr, "ir_base[%d].ops[%d] reference (%d) must not be BB_END\n", i, j, use);
                  ok = 0;
                }
              }
              if ((ctx->flags2 & IR_LINEAR)
               && use >= i
               && !(insn->op == IR_LOOP_BEGIN)) {
                fprintf(stderr, "ir_base[%d].ops[%d] invalid forward reference (%d)\n", i, j, use);
                ok = 0;
              }
              break;
            case IR_OPND_CONTROL_DEP:
              if ((ctx->flags2 & IR_LINEAR)
               && use >= i) {
                fprintf(stderr, "ir_base[%d].ops[%d] invalid forward reference (%d)\n", i, j, use);
                ok = 0;
              } else if (insn->op == IR_PHI) {
                ir_insn *merge_insn = &ctx->ir_base[insn->op1];
                if (merge_insn->op != IR_MERGE && merge_insn->op != IR_LOOP_BEGIN) {
                  fprintf(stderr, "ir_base[%d].ops[%d] reference (%d) must be MERGE or LOOP_BEGIN\n", i, j, use);
                  ok = 0;
                }
              }
              break;
            case IR_OPND_CONTROL_REF:
              if (!(ir_op_flags[use_insn->op] & IR_OP_FLAG_CONTROL)) {
                fprintf(stderr, "ir_base[%d].ops[%d] reference (%d) must be CONTROL\n", i, j, use);
                ok = 0;
              }
              break;
            case IR_OPND_CONTROL_GUARD:
              if (!(ir_op_flags[use_insn->op] & IR_OP_FLAG_BB_START)
               && use_insn->op != IR_GUARD
               && use_insn->op != IR_GUARD_NOT) {
                fprintf(stderr, "ir_base[%d].ops[%d] reference (%d) must be BB_START or GUARD\n", i, j, use);
                ok = 0;
              }
              break;
            default:
              fprintf(stderr, "ir_base[%d].ops[%d] reference (%d) of unsupported kind\n", i, j, use);
              ok = 0;
          }
        }
      } else if ((insn->op == IR_RETURN || insn->op == IR_UNREACHABLE) && j == 2) {
        /* pass (function returns void) */
      } else if (insn->op == IR_BEGIN && j == 1) {
        /* pass (start of unreachable basic block) */
      } else if (IR_OPND_KIND(flags, j) == IR_OPND_CONTROL_GUARD) {
        /* reference to control guard is optional */
      } else if (IR_OPND_KIND(flags, j) != IR_OPND_CONTROL_REF
          && (insn->op != IR_SNAPSHOT || j == 1)) {
        fprintf(stderr, "ir_base[%d].ops[%d] missing reference (%d)\n", i, j, use);
        ok = 0;
      }
      if (ctx->use_lists
       && use > 0
       && !ir_check_use_list(&check_ctx, ctx, use, i)) {
        fprintf(stderr, "ir_base[%d].ops[%d] is not in use list (%d)\n", i, j, use);
        ok = 0;
      }
    }

    switch (insn->op) {
      case IR_PHI:
        if (insn->inputs_count != ctx->ir_base[insn->op1].inputs_count + 1) {
          fprintf(stderr, "ir_base[%d] inconsistent PHI inputs_count (%d != %d)\n",
            i, insn->inputs_count, ctx->ir_base[insn->op1].inputs_count + 1);
          ok = 0;
        }
        break;
      case IR_LOAD:
      case IR_LOAD_v:
      case IR_STORE:
      case IR_STORE_v:
        type = ctx->ir_base[insn->op2].type;
        if (type != IR_ADDR
         && (!IR_IS_TYPE_INT(type) || ir_type_size[type] != ir_type_size[IR_ADDR])) {
          fprintf(stderr, "ir_base[%d].op2 must have ADDR type (%s)\n",
            i, IR_IS_TYPE_VECTOR(type) ? "VECTOR" : ir_type_name[type]);
          ok = 0;
        }
        break;
      case IR_VLOAD:
      case IR_VLOAD_v:
      case IR_VSTORE:
      case IR_VSTORE_v:
        if (ctx->ir_base[insn->op2].op != IR_VAR) {
          fprintf(stderr, "ir_base[%d].op2 must be 'VAR' (%s)\n",
            i, ir_op_name[ctx->ir_base[insn->op2].op]);
          ok = 0;
        }
        break;
      case IR_RETURN:
        if (ctx->ret_type != (insn->op2 ? ctx->ir_base[insn->op2].type : IR_VOID)) {
          fprintf(stderr, "ir_base[%d].type incompatible return type\n", i);
          ok = 0;
        }
        break;
      case IR_TAILCALL:
        if (ctx->ret_type != insn->type) {
          fprintf(stderr, "ir_base[%d].type incompatible return type\n", i);
          ok = 0;
        }
        break;
      case IR_PARAM:
        if (i > 2 && ctx->ir_base[i - 1].op != IR_PARAM) {
          fprintf(stderr, "ir_base[%d].op PARAMs must be used only right after START\n", i);
          ok = 0;
        }
        break;
    }

    if (ctx->use_lists) {
      ir_use_list *use_list = &ctx->use_lists[i];
      ir_ref count, n = use_list->count;

      for (p = &ctx->use_edges[use_list->refs]; n > 0; p++, n--) {
        use = *p;
        if (!ir_check_input_list(&check_ctx, ctx, i, use)) {
          fprintf(stderr, "ir_base[%d] is in use list of ir_base[%d]\n", use, i);
          ok = 0;
        }
      }

      if ((flags & IR_OP_FLAG_CONTROL) && !(flags & IR_OP_FLAG_MEM)) {
        switch (insn->op) {
          case IR_SWITCH:
            /* may have many successors */
            if (use_list->count < 1) {
              fprintf(stderr, "ir_base[%d].op (SWITCH) must have at least 1 successor (%d)\n", i, use_list->count);
              ok = 0;
            }
            break;
          case IR_IF:
            if (use_list->count != 2) {
              fprintf(stderr, "ir_base[%d].op (IF) must have 2 successors (%d)\n", i, use_list->count);
              ok = 0;
            }
            break;
          case IR_UNREACHABLE:
          case IR_RETURN:
            if (use_list->count == 1) {
              /* UNREACHABLE and RETURN may be linked with the following ENTRY by a fake edge */
              if (ctx->ir_base[ctx->use_edges[use_list->refs]].op == IR_ENTRY) {
                break;
              }
            }
            IR_FALLTHROUGH;
          case IR_IJMP:
            if (use_list->count != 0) {
              fprintf(stderr, "ir_base[%d].op (%s) must not have successors (%d)\n",
                i, ir_op_name[insn->op], use_list->count);
              ok = 0;
            }
            break;
          case IR_IGOTO:
          case IR_ASM_GOTO:
            break;
          default:
            /* skip data references */
            count = n = use_list->count;
            for (p = &ctx->use_edges[use_list->refs]; n > 0; p++, n--) {
              use = *p;
              if (!(ir_op_flags[ctx->ir_base[use].op] & IR_OP_FLAG_CONTROL)) {
                count--;
              }
            }
            if (count != 1) {
              if (insn->op == IR_CALL && count == 2) {
                /* result of CALL may be used as data in control instruction */
                break;
              }
              if ((insn->op == IR_LOOP_END || insn->op == IR_END) && count == 2) {
                /* LOOP_END/END may be linked with the following ENTRY by a fake edge */
                if (ctx->ir_base[ctx->use_edges[use_list->refs]].op == IR_ENTRY) {
                  count--;
                }
                if (ctx->ir_base[ctx->use_edges[use_list->refs + 1]].op == IR_ENTRY) {
                  count--;
                }
                if (count == 1) {
                  break;
                }
              }
              if (count == 0 && (insn->op == IR_END || insn->op == IR_LOOP_END)) {
                /* Dead block */
                break;
              }
              fprintf(stderr, "ir_base[%d].op (%s) must have 1 successor (%d)\n",
                i, ir_op_name[insn->op], count);
              ok = 0;
            }
            break;
        }
      }
    }
    n = ir_insn_inputs_to_len(n);
    i += n;
    insn += n;
  }

  if (check_ctx.arena) {
    ir_arena_free(check_ctx.arena);
  }

//  if (!ok) {
//    ir_dump_codegen(ctx, stderr);
//  }

#ifndef IR_CHECK_NO_ABORT
  IR_ASSERT(ok);
#endif

  return ok;
}

bool ir_check_prototype(const ir_ctx *ctx, uint32_t flags, uint8_t ret_type, uint32_t params_count, uint8_t *param_types)
{
  bool ok = 1;
  ir_ref ref = 2;
  uint32_t n = 0;

  while (ref < ctx->insns_count && ctx->ir_base[ref].op == IR_PARAM) {
    if (n >= params_count) {
      fprintf(stderr, "parameter count doesn't match function signature\n");
      ok = 0;
      break;
    } else if (ctx->ir_base[ref].type != param_types[n]) {
      fprintf(stderr, "parameter %d type doesn't match function signature\n", n);
      ok = 0;
    }
    ref++;
    n++;
  }

  if (n < params_count) {
    fprintf(stderr, "parameter count doesn't match function signature\n");
    ok = 0;
  }
  if ((flags & IR_VARARG_FUNC) != (ctx->flags & IR_VARARG_FUNC)) {
    fprintf(stderr, "IR_VARARG_FUNC flag doesn't match function signature\n");
    ok = 0;
  }
  if (ret_type != ctx->ret_type) {
    fprintf(stderr, "return type doesn't match function signature\n");
    ok = 0;
  }
  if ((flags & IR_CALL_CONV_MASK) != (ctx->flags & IR_CALL_CONV_MASK)) {
    fprintf(stderr, "calling convention doesn't match function signature\n");
    ok = 0;
  }

  return ok;
}

Coverage Report

Created: 2026-10-28 06:20

Line	Count	Source
1		/*
2		* IR - Lightweight JIT Compilation Framework
3		* (IR verification)
4		* This file is part of the IR Project distributed under the MIT-style LICENSE.
5		* Authors: Dmitry Stogov <dmitry@php.net>
6		*/
7
8		#include "ir.h"
9		#include "ir_private.h"
10
11		void ir_consistency_check(void)
12	0	{
13	0	IR_ASSERT(IR_UNUSED == 0);
14	0	IR_ASSERT(IR_NOP == 0);
15
16	0	IR_ASSERT((int)IR_BOOL == (int)IR_C_BOOL);
17	0	IR_ASSERT((int)IR_U8 == (int)IR_C_U8);
18	0	IR_ASSERT((int)IR_U16 == (int)IR_C_U16);
19	0	IR_ASSERT((int)IR_U32 == (int)IR_C_U32);
20	0	IR_ASSERT((int)IR_U64 == (int)IR_C_U64);
21	0	IR_ASSERT((int)IR_ADDR == (int)IR_C_ADDR);
22	0	IR_ASSERT((int)IR_CHAR == (int)IR_C_CHAR);
23	0	IR_ASSERT((int)IR_I8 == (int)IR_C_I8);
24	0	IR_ASSERT((int)IR_I16 == (int)IR_C_I16);
25	0	IR_ASSERT((int)IR_I32 == (int)IR_C_I32);
26	0	IR_ASSERT((int)IR_I64 == (int)IR_C_I64);
27	0	IR_ASSERT((int)IR_DOUBLE == (int)IR_C_DOUBLE);
28	0	IR_ASSERT((int)IR_FLOAT == (int)IR_C_FLOAT);
29
30	0	IR_ASSERT((IR_EQ ^ 1) == IR_NE);
31	0	IR_ASSERT((IR_LT ^ 3) == IR_GT);
32	0	IR_ASSERT((IR_GT ^ 3) == IR_LT);
33	0	IR_ASSERT((IR_LE ^ 3) == IR_GE);
34	0	IR_ASSERT((IR_GE ^ 3) == IR_LE);
35	0	IR_ASSERT((IR_ULT ^ 3) == IR_UGT);
36	0	IR_ASSERT((IR_UGT ^ 3) == IR_ULT);
37	0	IR_ASSERT((IR_ULE ^ 3) == IR_UGE);
38	0	IR_ASSERT((IR_UGE ^ 3) == IR_ULE);
39	0	IR_ASSERT((IR_ORDERED ^ 1) == IR_UNORDERED);
40
41	0	IR_ASSERT(IR_ADD + 1 == IR_SUB);
42	0	}
43
44		typedef struct {
45		ir_arena *arena;
46		ir_bitset *use_set;
47		ir_bitset *input_set;
48		} ir_check_ctx;
49
50		static bool ir_check_use_list(ir_check_ctx check_ctx, const ir_ctx ctx, ir_ref from, ir_ref to)
51	5.22M	{
52	5.22M	ir_ref n, *p;
53	5.22M	ir_use_list *use_list = &ctx->use_lists[from];
54
55	5.22M	n = use_list->count;
56	5.22M	if (n > 16) {
57		/* Avoid quadratic complexity by maintaining a temporary bit-set */
58	612	ir_bitset set;
59
60	612	if (!check_ctx->use_set \|\| !(set = check_ctx->use_set[from])) {
61	34	if (!check_ctx->arena) {
62	32	check_ctx->arena = ir_arena_create(sizeof(ir_arena) +
63	32	ctx->insns_count * sizeof(ir_bitset) +
64	32	ir_bitset_len(ctx->insns_count) * sizeof(ir_bitset_base_t));
65	32	}
66	34	if (!check_ctx->use_set) {
67	32	check_ctx->use_set = ir_arena_alloc(&check_ctx->arena, ctx->insns_count * sizeof(ir_bitset));
68	32	memset(check_ctx->use_set, 0, ctx->insns_count * sizeof(ir_bitset));
69	32	}
70	34	check_ctx->use_set[from] = set = (ir_bitset)ir_arena_alloc(&check_ctx->arena,
71	34	ir_bitset_len(ctx->insns_count) * sizeof(ir_bitset_base_t));
72	34	memset(set, 0, ir_bitset_len(ctx->insns_count) * sizeof(ir_bitset_base_t));
73	646	for (p = &ctx->use_edges[use_list->refs]; n > 0; p++, n--) {
74	612	ir_bitset_incl(set, *p);
75	612	}
76	34	}
77	612	return ir_bitset_in(set, to);
78	612	}
79	7.92M	for (p = &ctx->use_edges[use_list->refs]; n > 0; p++, n--) {
80	7.92M	if (*p == to) {
81	5.21M	return 1;
82	5.21M	}
83	7.92M	}
84	0	return 0;
85	5.21M	}
86
87		static bool ir_check_input_list(ir_check_ctx check_ctx, const ir_ctx ctx, ir_ref from, ir_ref to)
88	5.22M	{
89	5.22M	ir_insn *insn = &ctx->ir_base[to];
90	5.22M	ir_ref n, j, *p;
91
92	5.22M	n = ir_input_edges_count(ctx, insn);
93	5.22M	if (n > 16) {
94		/* Avoid quadratic complexity by maintaining a temporary bit-set */
95	0	ir_bitset set;
96
97	0	if (!check_ctx->input_set \|\| !(set = check_ctx->input_set[to])) {
98	0	if (!check_ctx->arena) {
99	0	check_ctx->arena = ir_arena_create(sizeof(ir_arena) +
100	0	ctx->insns_count * sizeof(ir_bitset) +
101	0	ir_bitset_len(ctx->insns_count) * sizeof(ir_bitset_base_t));
102	0	}
103	0	if (!check_ctx->input_set) {
104	0	check_ctx->input_set = ir_arena_alloc(&check_ctx->arena, ctx->insns_count * sizeof(ir_bitset));
105	0	memset(check_ctx->input_set, 0, ctx->insns_count * sizeof(ir_bitset));
106	0	}
107	0	check_ctx->input_set[to] = set = (ir_bitset)ir_arena_alloc(&check_ctx->arena,
108	0	ir_bitset_len(ctx->insns_count) * sizeof(ir_bitset_base_t));
109	0	memset(set, 0, ir_bitset_len(ctx->insns_count) * sizeof(ir_bitset_base_t));
110	0	for (j = 1, p = insn->ops + 1; j <= n; j++, p++) {
111	0	if (p > 0) ir_bitset_incl(set, p);
112	0	}
113	0	}
114	0	return ir_bitset_in(set, from);
115	0	}
116	7.00M	for (j = 1, p = insn->ops + 1; j <= n; j++, p++) {
117	7.00M	if (*p == from) {
118	5.22M	return 1;
119	5.22M	}
120	7.00M	}
121	0	return 0;
122	5.22M	}
123
124		static bool ir_check_domination(const ir_ctx *ctx, ir_ref def, ir_ref use)
125	1.04M	{
126	1.04M	uint32_t b1 = ctx->cfg_map[def];
127	1.04M	uint32_t b2 = ctx->cfg_map[use];
128	1.04M	ir_block *blocks = ctx->cfg_blocks;
129	1.04M	uint32_t b1_depth = blocks[b1].dom_depth;
130	1.04M	const ir_block *bb2 = &blocks[b2];
131
132	1.04M	if (b1 == b2) {
133	882k	return def < use;
134	882k	}
135	456k	while (bb2->dom_depth > b1_depth) {
136	294k	b2 = bb2->dom_parent;
137	294k	bb2 = &blocks[b2];
138	294k	}
139	161k	return b1 == b2;
140	1.04M	}
141
142		bool ir_check(const ir_ctx *ctx)
143	29.8k	{
144	29.8k	ir_ref i, j, n, *p, use;
145	29.8k	ir_insn insn, use_insn;
146	29.8k	ir_type type;
147	29.8k	uint32_t flags;
148	29.8k	bool ok = 1;
149	29.8k	ir_check_ctx check_ctx;
150
151	29.8k	if (ctx->insns_count < 1 \|\| ctx->ir_base[1].op != IR_START) {
152	0	fprintf(stderr, "ir_base[1].op invalid opcode (%d)\n",
153	0	(ctx->insns_count < 1) ? IR_NOP : ctx->ir_base[0].op);
154	0	ok = 0;
155	0	}
156
157	29.8k	check_ctx.arena = NULL;
158	29.8k	check_ctx.use_set = NULL;
159	29.8k	check_ctx.input_set = NULL;
160
161	5.29M	for (i = IR_UNUSED + 1, insn = ctx->ir_base + i; i < ctx->insns_count;) {
162	5.26M	if (insn->op >= IR_LAST_OP) {
163	0	fprintf(stderr, "ir_base[%d].op invalid opcode (%d)\n", i, insn->op);
164	0	ok = 0;
165	0	break;
166	0	}
167	5.26M	flags = ir_op_flags[insn->op];
168	5.26M	n = ir_input_edges_count(ctx, insn);
169	14.9M	for (j = 1, p = insn->ops + 1; j <= n; j++, p++) {
170	9.65M	use = *p;
171	9.65M	if (use != IR_UNUSED) {
172	9.64M	if (IR_IS_CONST_REF(use)) {
173	1.81M	if (IR_OPND_KIND(flags, j) != IR_OPND_DATA) {
174	0	fprintf(stderr, "ir_base[%d].ops[%d] reference (%d) must not be constant\n", i, j, use);
175	0	ok = 0;
176	1.81M	} else if (-use >= ctx->consts_count) {
177	0	fprintf(stderr, "ir_base[%d].ops[%d] constant reference (%d) is out of range\n", i, j, use);
178	0	ok = 0;
179	0	}
180	7.83M	} else {
181	7.83M	if (use >= ctx->insns_count) {
182	0	fprintf(stderr, "ir_base[%d].ops[%d] insn reference (%d) is out of range\n", i, j, use);
183	0	ok = 0;
184	0	continue;
185	0	}
186	7.83M	use_insn = &ctx->ir_base[use];
187	7.83M	switch (IR_OPND_KIND(flags, j)) {
188	3.28M	case IR_OPND_DATA:
189	3.28M	if (!(ir_op_flags[use_insn->op] & IR_OP_FLAG_DATA)) {
190	2.01M	if (!(ir_op_flags[use_insn->op] & IR_OP_FLAG_MEM)
191	2.01M	\|\| use_insn->type == IR_VOID) {
192	0	fprintf(stderr, "ir_base[%d].ops[%d] reference (%d) must be DATA\n", i, j, use);
193	0	ok = 0;
194	0	}
195	2.01M	}
196	3.28M	if ((ctx->flags2 & IR_LINEAR)
197	1.09M	&& use >= i
198	6.04k	&& !(insn->op == IR_PHI && ctx->ir_base[insn->op1].op == IR_LOOP_BEGIN)) {
199	0	fprintf(stderr, "ir_base[%d].ops[%d] invalid forward reference (%d)\n", i, j, use);
200	0	ok = 0;
201	0	}
202	3.28M	if (flags & IR_OP_FLAG_DATA) {
203	1.22M	switch (insn->op) {
204	0	case IR_COND:
205	0	if (j == 1) {
206	0	break;
207	0	}
208	0	IR_FALLTHROUGH;
209	684k	case IR_ADD:
210	778k	case IR_SUB:
211	798k	case IR_MUL:
212	798k	case IR_DIV:
213	803k	case IR_MOD:
214	803k	case IR_NEG:
215	803k	case IR_ABS:
216	803k	case IR_ADD_OV:
217	803k	case IR_SUB_OV:
218	804k	case IR_MUL_OV:
219	804k	case IR_NOT:
220	805k	case IR_OR:
221	925k	case IR_AND:
222	925k	case IR_XOR:
223	925k	case IR_SHL:
224	926k	case IR_SHR:
225	926k	case IR_SAR:
226	926k	case IR_ROL:
227	926k	case IR_ROR:
228	926k	case IR_BSWAP:
229	927k	case IR_MIN:
230	927k	case IR_MAX:
231	1.06M	case IR_PHI:
232	1.07M	case IR_COPY:
233	1.07M	case IR_PI:
234	1.07M	if (insn->type != use_insn->type) {
235	36	if (j == 2
236	6	&& (insn->op == IR_SHL
237	0	\|\| insn->op == IR_SHR
238	0	\|\| insn->op == IR_SAR
239	0	\|\| insn->op == IR_ROL
240	0	\|\| insn->op == IR_ROR)
241	6	&& IR_IS_TYPE_INT(use_insn->type)
242	6	&& (IR_IS_TYPE_INT(insn->type) \|\| IR_IS_TYPE_VECTOR(insn->type))) {
243		/* second argument of SHIFT may be incompatible with result */
244	6	break;
245	6	}
246	30	if (insn->op == IR_NOT && insn->type == IR_BOOL) {
247		/* boolean not */
248	0	break;
249	0	}
250	30	if (insn->type == IR_ADDR && (use_insn->type == IR_UINTPTR_T \|\| use_insn->type == IR_INTPTR_T)) {
251	30	break;
252	30	} else if (use_insn->type == IR_ADDR && (insn->type == IR_UINTPTR_T \|\| insn->type == IR_INTPTR_T)) {
253	0	break;
254	0	}
255	0	fprintf(stderr, "ir_base[%d].ops[%d] (%d) type is incompatible with result type (%d != %d)\n",
256	0	i, j, use, use_insn->type, insn->type);
257	0	ok = 0;
258	0	}
259	1.07M	break;
260	1.22M	}
261	1.22M	}
262	3.28M	if ((ctx->flags2 & IR_LINEAR)
263	1.09M	&& ctx->cfg_map
264	1.09M	&& insn->op != IR_PHI
265	1.04M	&& !ir_check_domination(ctx, use, i)) {
266	0	fprintf(stderr, "ir_base[%d].ops[%d] -> %d, %d doesn't dominate %d\n", i, j, use, use, i);
267	0	ok = 0;
268	0	}
269	3.28M	break;
270	4.47M	case IR_OPND_CONTROL:
271	4.47M	if (flags & IR_OP_FLAG_BB_START) {
272	1.25M	if (!(ir_op_flags[use_insn->op] & IR_OP_FLAG_BB_END)) {
273	0	fprintf(stderr, "ir_base[%d].ops[%d] reference (%d) must be BB_END\n", i, j, use);
274	0	ok = 0;
275	0	}
276	3.22M	} else {
277	3.22M	if (ir_op_flags[use_insn->op] & IR_OP_FLAG_BB_END) {
278	0	fprintf(stderr, "ir_base[%d].ops[%d] reference (%d) must not be BB_END\n", i, j, use);
279	0	ok = 0;
280	0	}
281	3.22M	}
282	4.47M	if ((ctx->flags2 & IR_LINEAR)
283	1.48M	&& use >= i
284	3.21k	&& !(insn->op == IR_LOOP_BEGIN)) {
285	0	fprintf(stderr, "ir_base[%d].ops[%d] invalid forward reference (%d)\n", i, j, use);
286	0	ok = 0;
287	0	}
288	4.47M	break;
289	74.1k	case IR_OPND_CONTROL_DEP:
290	74.1k	if ((ctx->flags2 & IR_LINEAR)
291	24.6k	&& use >= i) {
292	0	fprintf(stderr, "ir_base[%d].ops[%d] invalid forward reference (%d)\n", i, j, use);
293	0	ok = 0;
294	74.1k	} else if (insn->op == IR_PHI) {
295	73.9k	ir_insn *merge_insn = &ctx->ir_base[insn->op1];
296	73.9k	if (merge_insn->op != IR_MERGE && merge_insn->op != IR_LOOP_BEGIN) {
297	0	fprintf(stderr, "ir_base[%d].ops[%d] reference (%d) must be MERGE or LOOP_BEGIN\n", i, j, use);
298	0	ok = 0;
299	0	}
300	73.9k	}
301	74.1k	break;
302	0	case IR_OPND_CONTROL_REF:
303	0	if (!(ir_op_flags[use_insn->op] & IR_OP_FLAG_CONTROL)) {
304	0	fprintf(stderr, "ir_base[%d].ops[%d] reference (%d) must be CONTROL\n", i, j, use);
305	0	ok = 0;
306	0	}
307	0	break;
308	1.10k	case IR_OPND_CONTROL_GUARD:
309	1.10k	if (!(ir_op_flags[use_insn->op] & IR_OP_FLAG_BB_START)
310	0	&& use_insn->op != IR_GUARD
311	0	&& use_insn->op != IR_GUARD_NOT) {
312	0	fprintf(stderr, "ir_base[%d].ops[%d] reference (%d) must be BB_START or GUARD\n", i, j, use);
313	0	ok = 0;
314	0	}
315	1.10k	break;
316	0	default:
317	0	fprintf(stderr, "ir_base[%d].ops[%d] reference (%d) of unsupported kind\n", i, j, use);
318	0	ok = 0;
319	7.83M	}
320	7.83M	}
321	9.64M	} else if ((insn->op == IR_RETURN \|\| insn->op == IR_UNREACHABLE) && j == 2) {
322		/* pass (function returns void) */
323	3.62k	} else if (insn->op == IR_BEGIN && j == 1) {
324		/* pass (start of unreachable basic block) */
325	3.60k	} else if (IR_OPND_KIND(flags, j) == IR_OPND_CONTROL_GUARD) {
326		/* reference to control guard is optional */
327	2.45k	} else if (IR_OPND_KIND(flags, j) != IR_OPND_CONTROL_REF
328	1.14k	&& (insn->op != IR_SNAPSHOT \|\| j == 1)) {
329	0	fprintf(stderr, "ir_base[%d].ops[%d] missing reference (%d)\n", i, j, use);
330	0	ok = 0;
331	0	}
332	9.65M	if (ctx->use_lists
333	6.43M	&& use > 0
334	5.22M	&& !ir_check_use_list(&check_ctx, ctx, use, i)) {
335	0	fprintf(stderr, "ir_base[%d].ops[%d] is not in use list (%d)\n", i, j, use);
336	0	ok = 0;
337	0	}
338	9.65M	}
339
340	5.26M	switch (insn->op) {
341	73.9k	case IR_PHI:
342	73.9k	if (insn->inputs_count != ctx->ir_base[insn->op1].inputs_count + 1) {
343	0	fprintf(stderr, "ir_base[%d] inconsistent PHI inputs_count (%d != %d)\n",
344	0	i, insn->inputs_count, ctx->ir_base[insn->op1].inputs_count + 1);
345	0	ok = 0;
346	0	}
347	73.9k	break;
348	640k	case IR_LOAD:
349	640k	case IR_LOAD_v:
350	1.07M	case IR_STORE:
351	1.07M	case IR_STORE_v:
352	1.07M	type = ctx->ir_base[insn->op2].type;
353	1.07M	if (type != IR_ADDR
354	0	&& (!IR_IS_TYPE_INT(type) \|\| ir_type_size[type] != ir_type_size[IR_ADDR])) {
355	0	fprintf(stderr, "ir_base[%d].op2 must have ADDR type (%s)\n",
356	0	i, IR_IS_TYPE_VECTOR(type) ? "VECTOR" : ir_type_name[type]);
357	0	ok = 0;
358	0	}
359	1.07M	break;
360	0	case IR_VLOAD:
361	0	case IR_VLOAD_v:
362	0	case IR_VSTORE:
363	0	case IR_VSTORE_v:
364	0	if (ctx->ir_base[insn->op2].op != IR_VAR) {
365	0	fprintf(stderr, "ir_base[%d].op2 must be 'VAR' (%s)\n",
366	0	i, ir_op_name[ctx->ir_base[insn->op2].op]);
367	0	ok = 0;
368	0	}
369	0	break;
370	180	case IR_RETURN:
371	180	if (ctx->ret_type != (insn->op2 ? ctx->ir_base[insn->op2].type : IR_VOID)) {
372	0	fprintf(stderr, "ir_base[%d].type incompatible return type\n", i);
373	0	ok = 0;
374	0	}
375	180	break;
376	38.8k	case IR_TAILCALL:
377	38.8k	if (ctx->ret_type != insn->type) {
378	0	fprintf(stderr, "ir_base[%d].type incompatible return type\n", i);
379	0	ok = 0;
380	0	}
381	38.8k	break;
382	132	case IR_PARAM:
383	132	if (i > 2 && ctx->ir_base[i - 1].op != IR_PARAM) {
384	0	fprintf(stderr, "ir_base[%d].op PARAMs must be used only right after START\n", i);
385	0	ok = 0;
386	0	}
387	132	break;
388	5.26M	}
389
390	5.26M	if (ctx->use_lists) {
391	3.50M	ir_use_list *use_list = &ctx->use_lists[i];
392	3.50M	ir_ref count, n = use_list->count;
393
394	8.72M	for (p = &ctx->use_edges[use_list->refs]; n > 0; p++, n--) {
395	5.22M	use = *p;
396	5.22M	if (!ir_check_input_list(&check_ctx, ctx, i, use)) {
397	0	fprintf(stderr, "ir_base[%d] is in use list of ir_base[%d]\n", use, i);
398	0	ok = 0;
399	0	}
400	5.22M	}
401
402	3.50M	if ((flags & IR_OP_FLAG_CONTROL) && !(flags & IR_OP_FLAG_MEM)) {
403	1.36M	switch (insn->op) {
404	12	case IR_SWITCH:
405		/* may have many successors */
406	12	if (use_list->count < 1) {
407	0	fprintf(stderr, "ir_base[%d].op (SWITCH) must have at least 1 successor (%d)\n", i, use_list->count);
408	0	ok = 0;
409	0	}
410	12	break;
411	228k	case IR_IF:
412	228k	if (use_list->count != 2) {
413	0	fprintf(stderr, "ir_base[%d].op (IF) must have 2 successors (%d)\n", i, use_list->count);
414	0	ok = 0;
415	0	}
416	228k	break;
417	25.8k	case IR_UNREACHABLE:
418	25.9k	case IR_RETURN:
419	25.9k	if (use_list->count == 1) {
420		/* UNREACHABLE and RETURN may be linked with the following ENTRY by a fake edge */
421	6.25k	if (ctx->ir_base[ctx->use_edges[use_list->refs]].op == IR_ENTRY) {
422	6.25k	break;
423	6.25k	}
424	6.25k	}
425	19.7k	IR_FALLTHROUGH;
426	28.7k	case IR_IJMP:
427	28.7k	if (use_list->count != 0) {
428	0	fprintf(stderr, "ir_base[%d].op (%s) must not have successors (%d)\n",
429	0	i, ir_op_name[insn->op], use_list->count);
430	0	ok = 0;
431	0	}
432	28.7k	break;
433	0	case IR_IGOTO:
434	0	case IR_ASM_GOTO:
435	0	break;
436	1.09M	default:
437		/* skip data references */
438	1.09M	count = n = use_list->count;
439	2.24M	for (p = &ctx->use_edges[use_list->refs]; n > 0; p++, n--) {
440	1.14M	use = *p;
441	1.14M	if (!(ir_op_flags[ctx->ir_base[use].op] & IR_OP_FLAG_CONTROL)) {
442	50.1k	count--;
443	50.1k	}
444	1.14M	}
445	1.09M	if (count != 1) {
446	66	if (insn->op == IR_CALL && count == 2) {
447		/* result of CALL may be used as data in control instruction */
448	0	break;
449	0	}
450	66	if ((insn->op == IR_LOOP_END \|\| insn->op == IR_END) && count == 2) {
451		/* LOOP_END/END may be linked with the following ENTRY by a fake edge */
452	66	if (ctx->ir_base[ctx->use_edges[use_list->refs]].op == IR_ENTRY) {
453	66	count--;
454	66	}
455	66	if (ctx->ir_base[ctx->use_edges[use_list->refs + 1]].op == IR_ENTRY) {
456	0	count--;
457	0	}
458	66	if (count == 1) {
459	66	break;
460	66	}
461	66	}
462	0	if (count == 0 && (insn->op == IR_END \|\| insn->op == IR_LOOP_END)) {
463		/* Dead block */
464	0	break;
465	0	}
466	0	fprintf(stderr, "ir_base[%d].op (%s) must have 1 successor (%d)\n",
467	0	i, ir_op_name[insn->op], count);
468	0	ok = 0;
469	0	}
470	1.09M	break;
471	1.36M	}
472	1.36M	}
473	3.50M	}
474	5.26M	n = ir_insn_inputs_to_len(n);
475	5.26M	i += n;
476	5.26M	insn += n;
477	5.26M	}
478
479	29.8k	if (check_ctx.arena) {
480	32	ir_arena_free(check_ctx.arena);
481	32	}
482
483		// if (!ok) {
484		// ir_dump_codegen(ctx, stderr);
485		// }
486
487	29.8k	#ifndef IR_CHECK_NO_ABORT
488	29.8k	IR_ASSERT(ok);
489	29.8k	#endif
490
491	29.8k	return ok;
492	29.8k	}
493
494		bool ir_check_prototype(const ir_ctx ctx, uint32_t flags, uint8_t ret_type, uint32_t params_count, uint8_t param_types)
495	0	{
496	0	bool ok = 1;
497	0	ir_ref ref = 2;
498	0	uint32_t n = 0;
499
500	0	while (ref < ctx->insns_count && ctx->ir_base[ref].op == IR_PARAM) {
501	0	if (n >= params_count) {
502	0	fprintf(stderr, "parameter count doesn't match function signature\n");
503	0	ok = 0;
504	0	break;
505	0	} else if (ctx->ir_base[ref].type != param_types[n]) {
506	0	fprintf(stderr, "parameter %d type doesn't match function signature\n", n);
507	0	ok = 0;
508	0	}
509	0	ref++;
510	0	n++;
511	0	}
512
513	0	if (n < params_count) {
514	0	fprintf(stderr, "parameter count doesn't match function signature\n");
515	0	ok = 0;
516	0	}
517	0	if ((flags & IR_VARARG_FUNC) != (ctx->flags & IR_VARARG_FUNC)) {
518	0	fprintf(stderr, "IR_VARARG_FUNC flag doesn't match function signature\n");
519	0	ok = 0;
520	0	}
521	0	if (ret_type != ctx->ret_type) {
522	0	fprintf(stderr, "return type doesn't match function signature\n");
523	0	ok = 0;
524	0	}
525	0	if ((flags & IR_CALL_CONV_MASK) != (ctx->flags & IR_CALL_CONV_MASK)) {
526	0	fprintf(stderr, "calling convention doesn't match function signature\n");
527	0	ok = 0;
528	0	}
529
530	0	return ok;
531	0	}