src/compiler/nir/nir_validate.c

   1 /*
   2  * Copyright © 2014 Intel Corporation
   3  *
   4  * Permission is hereby granted, free of charge, to any person obtaining a
   5  * copy of this software and associated documentation files (the "Software"),
   6  * to deal in the Software without restriction, including without limitation
   7  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
   8  * and/or sell copies of the Software, and to permit persons to whom the
   9  * Software is furnished to do so, subject to the following conditions:
  10  *
  11  * The above copyright notice and this permission notice (including the next
  12  * paragraph) shall be included in all copies or substantial portions of the
  13  * Software.
  14  *
  15  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  16  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  17  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
  18  * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  19  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
  20  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
  21  * IN THE SOFTWARE.
  22  *
  23  * Authors:
  24  *    Connor Abbott (cwabbott0@gmail.com)
  25  *
  26  */
  27
  28 #include "nir.h"
  29 #include <assert.h>
  30
  31 /*
  32  * This file checks for invalid IR indicating a bug somewhere in the compiler.
  33  */
  34
  35 /* Since this file is just a pile of asserts, don't bother compiling it if
  36  * we're not building a debug build.
  37  */
  38 #ifdef DEBUG
  39
  40 /*
  41  * Per-register validation state.
  42  */
  43
  44 typedef struct {
  45    /*
  46     * equivalent to the uses and defs in nir_register, but built up by the
  47     * validator. At the end, we verify that the sets have the same entries.
  48     */
  49    struct set *uses, *if_uses, *defs;
  50    nir_function_impl *where_defined; /* NULL for global registers */
  51 } reg_validate_state;
  52
  53 typedef struct {
  54    /*
  55     * equivalent to the uses in nir_ssa_def, but built up by the validator.
  56     * At the end, we verify that the sets have the same entries.
  57     */
  58    struct set *uses, *if_uses;
  59    nir_function_impl *where_defined;
  60 } ssa_def_validate_state;
  61
  62 typedef struct {
  63    /* map of register -> validation state (struct above) */
  64    struct hash_table *regs;
  65
  66    /* the current shader being validated */
  67    nir_shader *shader;
  68
  69    /* the current instruction being validated */
  70    nir_instr *instr;
  71
  72    /* the current basic block being validated */
  73    nir_block *block;
  74
  75    /* the current if statement being validated */
  76    nir_if *if_stmt;
  77
  78    /* the current loop being visited */
  79    nir_loop *loop;
  80
  81    /* the parent of the current cf node being visited */
  82    nir_cf_node *parent_node;
  83
  84    /* the current function implementation being validated */
  85    nir_function_impl *impl;
  86
  87    /* map of SSA value -> function implementation where it is defined */
  88    struct hash_table *ssa_defs;
  89
  90    /* bitset of ssa definitions we have found; used to check uniqueness */
  91    BITSET_WORD *ssa_defs_found;
  92
  93    /* bitset of registers we have currently found; used to check uniqueness */
  94    BITSET_WORD *regs_found;
  95
  96    /* map of local variable -> function implementation where it is defined */
  97    struct hash_table *var_defs;
  98 } validate_state;
  99
 100 static void validate_src(nir_src *src, validate_state *state);
 101
 102 static void
 103 validate_reg_src(nir_src *src, validate_state *state)
 104 {
 105    assert(src->reg.reg != NULL);
 106
 107    struct hash_entry *entry;
 108    entry = _mesa_hash_table_search(state->regs, src->reg.reg);
 109    assert(entry);
 110
 111    reg_validate_state *reg_state = (reg_validate_state *) entry->data;
 112
 113    if (state->instr) {
 114       _mesa_set_add(reg_state->uses, src);
 115    } else {
 116       assert(state->if_stmt);
 117       _mesa_set_add(reg_state->if_uses, src);
 118    }
 119
 120    if (!src->reg.reg->is_global) {
 121       assert(reg_state->where_defined == state->impl &&
 122              "using a register declared in a different function");
 123    }
 124
 125    assert((src->reg.reg->num_array_elems == 0 ||
 126           src->reg.base_offset < src->reg.reg->num_array_elems) &&
 127           "definitely out-of-bounds array access");
 128
 129    if (src->reg.indirect) {
 130       assert(src->reg.reg->num_array_elems != 0);
 131       assert((src->reg.indirect->is_ssa ||
 132               src->reg.indirect->reg.indirect == NULL) &&
 133              "only one level of indirection allowed");
 134       validate_src(src->reg.indirect, state);
 135    }
 136 }
 137
 138 static void
 139 validate_ssa_src(nir_src *src, validate_state *state)
 140 {
 141    assert(src->ssa != NULL);
 142
 143    struct hash_entry *entry = _mesa_hash_table_search(state->ssa_defs, src->ssa);
 144
 145    assert(entry);
 146
 147    ssa_def_validate_state *def_state = (ssa_def_validate_state *)entry->data;
 148
 149    assert(def_state->where_defined == state->impl &&
 150           "using an SSA value defined in a different function");
 151
 152    if (state->instr) {
 153       _mesa_set_add(def_state->uses, src);
 154    } else {
 155       assert(state->if_stmt);
 156       _mesa_set_add(def_state->if_uses, src);
 157    }
 158
 159    /* TODO validate that the use is dominated by the definition */
 160 }
 161
 162 static void
 163 validate_src(nir_src *src, validate_state *state)
 164 {
 165    if (state->instr)
 166       assert(src->parent_instr == state->instr);
 167    else
 168       assert(src->parent_if == state->if_stmt);
 169
 170    if (src->is_ssa)
 171       validate_ssa_src(src, state);
 172    else
 173       validate_reg_src(src, state);
 174 }
 175
 176 static void
 177 validate_alu_src(nir_alu_instr *instr, unsigned index, validate_state *state)
 178 {
 179    nir_alu_src *src = &instr->src[index];
 180
 181    unsigned num_components;
 182    unsigned src_bit_size;
 183    if (src->src.is_ssa) {
 184       src_bit_size = src->src.ssa->bit_size;
 185       num_components = src->src.ssa->num_components;
 186    } else {
 187       src_bit_size = src->src.reg.reg->bit_size;
 188       if (src->src.reg.reg->is_packed)
 189          num_components = 4; /* can't check anything */
 190       else
 191          num_components = src->src.reg.reg->num_components;
 192    }
 193    for (unsigned i = 0; i < 4; i++) {
 194       assert(src->swizzle[i] < 4);
 195
 196       if (nir_alu_instr_channel_used(instr, index, i))
 197          assert(src->swizzle[i] < num_components);
 198    }
 199
 200    nir_alu_type src_type = nir_op_infos[instr->op].input_types[index];
 201
 202    /* 8-bit float isn't a thing */
 203    if (nir_alu_type_get_base_type(src_type) == nir_type_float)
 204       assert(src_bit_size == 16 || src_bit_size == 32 || src_bit_size == 64);
 205
 206    if (nir_alu_type_get_type_size(src_type)) {
 207       /* This source has an explicit bit size */
 208       assert(nir_alu_type_get_type_size(src_type) == src_bit_size);
 209    } else {
 210       if (!nir_alu_type_get_type_size(nir_op_infos[instr->op].output_type)) {
 211          unsigned dest_bit_size =
 212             instr->dest.dest.is_ssa ? instr->dest.dest.ssa.bit_size
 213                                     : instr->dest.dest.reg.reg->bit_size;
 214          assert(dest_bit_size == src_bit_size);
 215       }
 216    }
 217
 218    validate_src(&src->src, state);
 219 }
 220
 221 static void
 222 validate_reg_dest(nir_reg_dest *dest, validate_state *state)
 223 {
 224    assert(dest->reg != NULL);
 225
 226    assert(dest->parent_instr == state->instr);
 227
 228    struct hash_entry *entry2;
 229    entry2 = _mesa_hash_table_search(state->regs, dest->reg);
 230
 231    assert(entry2);
 232
 233    reg_validate_state *reg_state = (reg_validate_state *) entry2->data;
 234    _mesa_set_add(reg_state->defs, dest);
 235
 236    if (!dest->reg->is_global) {
 237       assert(reg_state->where_defined == state->impl &&
 238              "writing to a register declared in a different function");
 239    }
 240
 241    assert((dest->reg->num_array_elems == 0 ||
 242           dest->base_offset < dest->reg->num_array_elems) &&
 243           "definitely out-of-bounds array access");
 244
 245    if (dest->indirect) {
 246       assert(dest->reg->num_array_elems != 0);
 247       assert((dest->indirect->is_ssa || dest->indirect->reg.indirect == NULL) &&
 248              "only one level of indirection allowed");
 249       validate_src(dest->indirect, state);
 250    }
 251 }
 252
 253 static void
 254 validate_ssa_def(nir_ssa_def *def, validate_state *state)
 255 {
 256    assert(def->index < state->impl->ssa_alloc);
 257    assert(!BITSET_TEST(state->ssa_defs_found, def->index));
 258    BITSET_SET(state->ssa_defs_found, def->index);
 259
 260    assert(def->parent_instr == state->instr);
 261
 262    assert(def->num_components <= 4);
 263
 264    list_validate(&def->uses);
 265    list_validate(&def->if_uses);
 266
 267    ssa_def_validate_state *def_state = ralloc(state->ssa_defs,
 268                                               ssa_def_validate_state);
 269    def_state->where_defined = state->impl;
 270    def_state->uses = _mesa_set_create(def_state, _mesa_hash_pointer,
 271                                       _mesa_key_pointer_equal);
 272    def_state->if_uses = _mesa_set_create(def_state, _mesa_hash_pointer,
 273                                          _mesa_key_pointer_equal);
 274    _mesa_hash_table_insert(state->ssa_defs, def, def_state);
 275 }
 276
 277 static void
 278 validate_dest(nir_dest *dest, validate_state *state)
 279 {
 280    if (dest->is_ssa)
 281       validate_ssa_def(&dest->ssa, state);
 282    else
 283       validate_reg_dest(&dest->reg, state);
 284 }
 285
 286 static void
 287 validate_alu_dest(nir_alu_instr *instr, validate_state *state)
 288 {
 289    nir_alu_dest *dest = &instr->dest;
 290
 291    unsigned dest_size =
 292       dest->dest.is_ssa ? dest->dest.ssa.num_components
 293                         : dest->dest.reg.reg->num_components;
 294    bool is_packed = !dest->dest.is_ssa && dest->dest.reg.reg->is_packed;
 295    /*
 296     * validate that the instruction doesn't write to components not in the
 297     * register/SSA value
 298     */
 299    assert(is_packed || !(dest->write_mask & ~((1 << dest_size) - 1)));
 300
 301    /* validate that saturate is only ever used on instructions with
 302     * destinations of type float
 303     */
 304    nir_alu_instr *alu = nir_instr_as_alu(state->instr);
 305    assert(nir_op_infos[alu->op].output_type == nir_type_float ||
 306           !dest->saturate);
 307
 308    unsigned bit_size = dest->dest.is_ssa ? dest->dest.ssa.bit_size
 309                                          : dest->dest.reg.reg->bit_size;
 310    nir_alu_type type = nir_op_infos[instr->op].output_type;
 311
 312    /* 8-bit float isn't a thing */
 313    if (nir_alu_type_get_base_type(type) == nir_type_float)
 314       assert(bit_size == 16 || bit_size == 32 || bit_size == 64);
 315
 316    assert(nir_alu_type_get_type_size(type) == 0 ||
 317           nir_alu_type_get_type_size(type) == bit_size);
 318
 319    validate_dest(&dest->dest, state);
 320 }
 321
 322 static void
 323 validate_alu_instr(nir_alu_instr *instr, validate_state *state)
 324 {
 325    assert(instr->op < nir_num_opcodes);
 326
 327    for (unsigned i = 0; i < nir_op_infos[instr->op].num_inputs; i++) {
 328       validate_alu_src(instr, i, state);
 329    }
 330
 331    validate_alu_dest(instr, state);
 332 }
 333
 334 static void
 335 validate_deref_chain(nir_deref *deref, validate_state *state)
 336 {
 337    assert(deref->child == NULL || ralloc_parent(deref->child) == deref);
 338
 339    nir_deref *parent = NULL;
 340    while (deref != NULL) {
 341       switch (deref->deref_type) {
 342       case nir_deref_type_array:
 343          assert(deref->type == glsl_get_array_element(parent->type));
 344          if (nir_deref_as_array(deref)->deref_array_type ==
 345              nir_deref_array_type_indirect)
 346             validate_src(&nir_deref_as_array(deref)->indirect, state);
 347          break;
 348
 349       case nir_deref_type_struct:
 350          assert(deref->type ==
 351                 glsl_get_struct_field(parent->type,
 352                                       nir_deref_as_struct(deref)->index));
 353          break;
 354
 355       case nir_deref_type_var:
 356          break;
 357
 358       default:
 359          assert(!"Invalid deref type");
 360          break;
 361       }
 362
 363       parent = deref;
 364       deref = deref->child;
 365    }
 366 }
 367
 368 static void
 369 validate_var_use(nir_variable *var, validate_state *state)
 370 {
 371    if (var->data.mode == nir_var_local) {
 372       struct hash_entry *entry = _mesa_hash_table_search(state->var_defs, var);
 373
 374       assert(entry);
 375       assert((nir_function_impl *) entry->data == state->impl);
 376    }
 377 }
 378
 379 static void
 380 validate_deref_var(void *parent_mem_ctx, nir_deref_var *deref, validate_state *state)
 381 {
 382    assert(deref != NULL);
 383    assert(ralloc_parent(deref) == parent_mem_ctx);
 384    assert(deref->deref.type == deref->var->type);
 385
 386    validate_var_use(deref->var, state);
 387
 388    validate_deref_chain(&deref->deref, state);
 389 }
 390
 391 static void
 392 validate_intrinsic_instr(nir_intrinsic_instr *instr, validate_state *state)
 393 {
 394    unsigned num_srcs = nir_intrinsic_infos[instr->intrinsic].num_srcs;
 395    for (unsigned i = 0; i < num_srcs; i++) {
 396       unsigned components_read =
 397          nir_intrinsic_infos[instr->intrinsic].src_components[i];
 398       if (components_read == 0)
 399          components_read = instr->num_components;
 400
 401       assert(components_read > 0);
 402
 403       if (instr->src[i].is_ssa) {
 404          assert(components_read <= instr->src[i].ssa->num_components);
 405       } else if (!instr->src[i].reg.reg->is_packed) {
 406          assert(components_read <= instr->src[i].reg.reg->num_components);
 407       }
 408
 409       validate_src(&instr->src[i], state);
 410    }
 411
 412    unsigned num_vars = nir_intrinsic_infos[instr->intrinsic].num_variables;
 413    for (unsigned i = 0; i < num_vars; i++) {
 414       validate_deref_var(instr, instr->variables[i], state);
 415    }
 416
 417    if (nir_intrinsic_infos[instr->intrinsic].has_dest) {
 418       unsigned components_written =
 419          nir_intrinsic_infos[instr->intrinsic].dest_components;
 420       if (components_written == 0)
 421          components_written = instr->num_components;
 422
 423       assert(components_written > 0);
 424
 425       if (instr->dest.is_ssa) {
 426          assert(components_written <= instr->dest.ssa.num_components);
 427       } else if (!instr->dest.reg.reg->is_packed) {
 428          assert(components_written <= instr->dest.reg.reg->num_components);
 429       }
 430
 431       validate_dest(&instr->dest, state);
 432    }
 433
 434    switch (instr->intrinsic) {
 435    case nir_intrinsic_load_var: {
 436       const struct glsl_type *type =
 437          nir_deref_tail(&instr->variables[0]->deref)->type;
 438       assert(glsl_type_is_vector_or_scalar(type) ||
 439              (instr->variables[0]->var->data.mode == nir_var_uniform &&
 440               glsl_get_base_type(type) == GLSL_TYPE_SUBROUTINE));
 441       assert(instr->num_components == glsl_get_vector_elements(type));
 442       break;
 443    }
 444    case nir_intrinsic_store_var: {
 445       const struct glsl_type *type =
 446          nir_deref_tail(&instr->variables[0]->deref)->type;
 447       assert(glsl_type_is_vector_or_scalar(type) ||
 448              (instr->variables[0]->var->data.mode == nir_var_uniform &&
 449               glsl_get_base_type(type) == GLSL_TYPE_SUBROUTINE));
 450       assert(instr->num_components == glsl_get_vector_elements(type));
 451       assert(instr->variables[0]->var->data.mode != nir_var_shader_in &&
 452              instr->variables[0]->var->data.mode != nir_var_uniform &&
 453              instr->variables[0]->var->data.mode != nir_var_shader_storage);
 454       assert((nir_intrinsic_write_mask(instr) & ~((1 << instr->num_components) - 1)) == 0);
 455       break;
 456    }
 457    case nir_intrinsic_copy_var:
 458       assert(nir_deref_tail(&instr->variables[0]->deref)->type ==
 459              nir_deref_tail(&instr->variables[1]->deref)->type);
 460       assert(instr->variables[0]->var->data.mode != nir_var_shader_in &&
 461              instr->variables[0]->var->data.mode != nir_var_uniform &&
 462              instr->variables[0]->var->data.mode != nir_var_shader_storage);
 463       break;
 464    default:
 465       break;
 466    }
 467 }
 468
 469 static void
 470 validate_tex_instr(nir_tex_instr *instr, validate_state *state)
 471 {
 472    bool src_type_seen[nir_num_tex_src_types];
 473    for (unsigned i = 0; i < nir_num_tex_src_types; i++)
 474       src_type_seen[i] = false;
 475
 476    for (unsigned i = 0; i < instr->num_srcs; i++) {
 477       assert(!src_type_seen[instr->src[i].src_type]);
 478       src_type_seen[instr->src[i].src_type] = true;
 479       validate_src(&instr->src[i].src, state);
 480    }
 481
 482    if (instr->texture != NULL)
 483       validate_deref_var(instr, instr->texture, state);
 484
 485    if (instr->sampler != NULL)
 486       validate_deref_var(instr, instr->sampler, state);
 487
 488    validate_dest(&instr->dest, state);
 489 }
 490
 491 static void
 492 validate_call_instr(nir_call_instr *instr, validate_state *state)
 493 {
 494    if (instr->return_deref == NULL) {
 495       assert(glsl_type_is_void(instr->callee->return_type));
 496    } else {
 497       assert(instr->return_deref->deref.type == instr->callee->return_type);
 498       validate_deref_var(instr, instr->return_deref, state);
 499    }
 500
 501    assert(instr->num_params == instr->callee->num_params);
 502
 503    for (unsigned i = 0; i < instr->num_params; i++) {
 504       assert(instr->callee->params[i].type == instr->params[i]->deref.type);
 505       validate_deref_var(instr, instr->params[i], state);
 506    }
 507 }
 508
 509 static void
 510 validate_load_const_instr(nir_load_const_instr *instr, validate_state *state)
 511 {
 512    validate_ssa_def(&instr->def, state);
 513 }
 514
 515 static void
 516 validate_ssa_undef_instr(nir_ssa_undef_instr *instr, validate_state *state)
 517 {
 518    validate_ssa_def(&instr->def, state);
 519 }
 520
 521 static void
 522 validate_phi_instr(nir_phi_instr *instr, validate_state *state)
 523 {
 524    /*
 525     * don't validate the sources until we get to them from their predecessor
 526     * basic blocks, to avoid validating an SSA use before its definition.
 527     */
 528
 529    validate_dest(&instr->dest, state);
 530
 531    exec_list_validate(&instr->srcs);
 532    assert(exec_list_length(&instr->srcs) ==
 533           state->block->predecessors->entries);
 534 }
 535
 536 static void
 537 validate_instr(nir_instr *instr, validate_state *state)
 538 {
 539    assert(instr->block == state->block);
 540
 541    state->instr = instr;
 542
 543    switch (instr->type) {
 544    case nir_instr_type_alu:
 545       validate_alu_instr(nir_instr_as_alu(instr), state);
 546       break;
 547
 548    case nir_instr_type_call:
 549       validate_call_instr(nir_instr_as_call(instr), state);
 550       break;
 551
 552    case nir_instr_type_intrinsic:
 553       validate_intrinsic_instr(nir_instr_as_intrinsic(instr), state);
 554       break;
 555
 556    case nir_instr_type_tex:
 557       validate_tex_instr(nir_instr_as_tex(instr), state);
 558       break;
 559
 560    case nir_instr_type_load_const:
 561       validate_load_const_instr(nir_instr_as_load_const(instr), state);
 562       break;
 563
 564    case nir_instr_type_phi:
 565       validate_phi_instr(nir_instr_as_phi(instr), state);
 566       break;
 567
 568    case nir_instr_type_ssa_undef:
 569       validate_ssa_undef_instr(nir_instr_as_ssa_undef(instr), state);
 570       break;
 571
 572    case nir_instr_type_jump:
 573       break;
 574
 575    default:
 576       assert(!"Invalid ALU instruction type");
 577       break;
 578    }
 579
 580    state->instr = NULL;
 581 }
 582
 583 static void
 584 validate_phi_src(nir_phi_instr *instr, nir_block *pred, validate_state *state)
 585 {
 586    state->instr = &instr->instr;
 587
 588    assert(instr->dest.is_ssa);
 589
 590    exec_list_validate(&instr->srcs);
 591    nir_foreach_phi_src(instr, src) {
 592       if (src->pred == pred) {
 593          assert(src->src.is_ssa);
 594          assert(src->src.ssa->num_components ==
 595                 instr->dest.ssa.num_components);
 596
 597          validate_src(&src->src, state);
 598          state->instr = NULL;
 599          return;
 600       }
 601    }
 602
 603    abort();
 604 }
 605
 606 static void
 607 validate_phi_srcs(nir_block *block, nir_block *succ, validate_state *state)
 608 {
 609    nir_foreach_instr(succ, instr) {
 610       if (instr->type != nir_instr_type_phi)
 611          break;
 612
 613       validate_phi_src(nir_instr_as_phi(instr), block, state);
 614    }
 615 }
 616
 617 static void validate_cf_node(nir_cf_node *node, validate_state *state);
 618
 619 static void
 620 validate_block(nir_block *block, validate_state *state)
 621 {
 622    assert(block->cf_node.parent == state->parent_node);
 623
 624    state->block = block;
 625
 626    exec_list_validate(&block->instr_list);
 627    nir_foreach_instr(block, instr) {
 628       if (instr->type == nir_instr_type_phi) {
 629          assert(instr == nir_block_first_instr(block) ||
 630                 nir_instr_prev(instr)->type == nir_instr_type_phi);
 631       }
 632
 633       if (instr->type == nir_instr_type_jump) {
 634          assert(instr == nir_block_last_instr(block));
 635       }
 636
 637       validate_instr(instr, state);
 638    }
 639
 640    assert(block->successors[0] != NULL);
 641    assert(block->successors[0] != block->successors[1]);
 642
 643    for (unsigned i = 0; i < 2; i++) {
 644       if (block->successors[i] != NULL) {
 645          struct set_entry *entry =
 646             _mesa_set_search(block->successors[i]->predecessors, block);
 647          assert(entry);
 648
 649          validate_phi_srcs(block, block->successors[i], state);
 650       }
 651    }
 652
 653    struct set_entry *entry;
 654    set_foreach(block->predecessors, entry) {
 655       const nir_block *pred = entry->key;
 656       assert(pred->successors[0] == block ||
 657              pred->successors[1] == block);
 658    }
 659
 660    if (!exec_list_is_empty(&block->instr_list) &&
 661        nir_block_last_instr(block)->type == nir_instr_type_jump) {
 662       assert(block->successors[1] == NULL);
 663       nir_jump_instr *jump = nir_instr_as_jump(nir_block_last_instr(block));
 664       switch (jump->type) {
 665       case nir_jump_break: {
 666          nir_block *after =
 667             nir_cf_node_as_block(nir_cf_node_next(&state->loop->cf_node));
 668          assert(block->successors[0] == after);
 669          break;
 670       }
 671
 672       case nir_jump_continue: {
 673          nir_block *first =
 674             nir_cf_node_as_block(nir_loop_first_cf_node(state->loop));
 675          assert(block->successors[0] == first);
 676          break;
 677       }
 678
 679       case nir_jump_return:
 680          assert(block->successors[0] == state->impl->end_block);
 681          break;
 682
 683       default:
 684          unreachable("bad jump type");
 685       }
 686    } else {
 687       nir_cf_node *next = nir_cf_node_next(&block->cf_node);
 688       if (next == NULL) {
 689          switch (state->parent_node->type) {
 690          case nir_cf_node_loop: {
 691             nir_block *first =
 692                nir_cf_node_as_block(nir_loop_first_cf_node(state->loop));
 693             assert(block->successors[0] == first);
 694             /* due to the hack for infinite loops, block->successors[1] may
 695              * point to the block after the loop.
 696              */
 697             break;
 698          }
 699
 700          case nir_cf_node_if: {
 701             nir_block *after =
 702                nir_cf_node_as_block(nir_cf_node_next(state->parent_node));
 703             assert(block->successors[0] == after);
 704             assert(block->successors[1] == NULL);
 705             break;
 706          }
 707
 708          case nir_cf_node_function:
 709             assert(block->successors[0] == state->impl->end_block);
 710             assert(block->successors[1] == NULL);
 711             break;
 712
 713          default:
 714             unreachable("unknown control flow node type");
 715          }
 716       } else {
 717          if (next->type == nir_cf_node_if) {
 718             nir_if *if_stmt = nir_cf_node_as_if(next);
 719             assert(&block->successors[0]->cf_node ==
 720                    nir_if_first_then_node(if_stmt));
 721             assert(&block->successors[1]->cf_node ==
 722                    nir_if_first_else_node(if_stmt));
 723          } else {
 724             assert(next->type == nir_cf_node_loop);
 725             nir_loop *loop = nir_cf_node_as_loop(next);
 726             assert(&block->successors[0]->cf_node ==
 727                    nir_loop_first_cf_node(loop));
 728             assert(block->successors[1] == NULL);
 729          }
 730       }
 731    }
 732 }
 733
 734 static void
 735 validate_if(nir_if *if_stmt, validate_state *state)
 736 {
 737    state->if_stmt = if_stmt;
 738
 739    assert(!exec_node_is_head_sentinel(if_stmt->cf_node.node.prev));
 740    nir_cf_node *prev_node = nir_cf_node_prev(&if_stmt->cf_node);
 741    assert(prev_node->type == nir_cf_node_block);
 742
 743    assert(!exec_node_is_tail_sentinel(if_stmt->cf_node.node.next));
 744    nir_cf_node *next_node = nir_cf_node_next(&if_stmt->cf_node);
 745    assert(next_node->type == nir_cf_node_block);
 746
 747    validate_src(&if_stmt->condition, state);
 748
 749    assert(!exec_list_is_empty(&if_stmt->then_list));
 750    assert(!exec_list_is_empty(&if_stmt->else_list));
 751
 752    nir_cf_node *old_parent = state->parent_node;
 753    state->parent_node = &if_stmt->cf_node;
 754
 755    exec_list_validate(&if_stmt->then_list);
 756    foreach_list_typed(nir_cf_node, cf_node, node, &if_stmt->then_list) {
 757       validate_cf_node(cf_node, state);
 758    }
 759
 760    exec_list_validate(&if_stmt->else_list);
 761    foreach_list_typed(nir_cf_node, cf_node, node, &if_stmt->else_list) {
 762       validate_cf_node(cf_node, state);
 763    }
 764
 765    state->parent_node = old_parent;
 766    state->if_stmt = NULL;
 767 }
 768
 769 static void
 770 validate_loop(nir_loop *loop, validate_state *state)
 771 {
 772    assert(!exec_node_is_head_sentinel(loop->cf_node.node.prev));
 773    nir_cf_node *prev_node = nir_cf_node_prev(&loop->cf_node);
 774    assert(prev_node->type == nir_cf_node_block);
 775
 776    assert(!exec_node_is_tail_sentinel(loop->cf_node.node.next));
 777    nir_cf_node *next_node = nir_cf_node_next(&loop->cf_node);
 778    assert(next_node->type == nir_cf_node_block);
 779
 780    assert(!exec_list_is_empty(&loop->body));
 781
 782    nir_cf_node *old_parent = state->parent_node;
 783    state->parent_node = &loop->cf_node;
 784    nir_loop *old_loop = state->loop;
 785    state->loop = loop;
 786
 787    exec_list_validate(&loop->body);
 788    foreach_list_typed(nir_cf_node, cf_node, node, &loop->body) {
 789       validate_cf_node(cf_node, state);
 790    }
 791
 792    state->parent_node = old_parent;
 793    state->loop = old_loop;
 794 }
 795
 796 static void
 797 validate_cf_node(nir_cf_node *node, validate_state *state)
 798 {
 799    assert(node->parent == state->parent_node);
 800
 801    switch (node->type) {
 802    case nir_cf_node_block:
 803       validate_block(nir_cf_node_as_block(node), state);
 804       break;
 805
 806    case nir_cf_node_if:
 807       validate_if(nir_cf_node_as_if(node), state);
 808       break;
 809
 810    case nir_cf_node_loop:
 811       validate_loop(nir_cf_node_as_loop(node), state);
 812       break;
 813
 814    default:
 815       unreachable("Invalid CF node type");
 816    }
 817 }
 818
 819 static void
 820 prevalidate_reg_decl(nir_register *reg, bool is_global, validate_state *state)
 821 {
 822    assert(reg->is_global == is_global);
 823
 824    if (is_global)
 825       assert(reg->index < state->shader->reg_alloc);
 826    else
 827       assert(reg->index < state->impl->reg_alloc);
 828    assert(!BITSET_TEST(state->regs_found, reg->index));
 829    BITSET_SET(state->regs_found, reg->index);
 830
 831    list_validate(&reg->uses);
 832    list_validate(&reg->defs);
 833    list_validate(&reg->if_uses);
 834
 835    reg_validate_state *reg_state = ralloc(state->regs, reg_validate_state);
 836    reg_state->uses = _mesa_set_create(reg_state, _mesa_hash_pointer,
 837                                       _mesa_key_pointer_equal);
 838    reg_state->if_uses = _mesa_set_create(reg_state, _mesa_hash_pointer,
 839                                          _mesa_key_pointer_equal);
 840    reg_state->defs = _mesa_set_create(reg_state, _mesa_hash_pointer,
 841                                       _mesa_key_pointer_equal);
 842
 843    reg_state->where_defined = is_global ? NULL : state->impl;
 844
 845    _mesa_hash_table_insert(state->regs, reg, reg_state);
 846 }
 847
 848 static void
 849 postvalidate_reg_decl(nir_register *reg, validate_state *state)
 850 {
 851    struct hash_entry *entry = _mesa_hash_table_search(state->regs, reg);
 852
 853    reg_validate_state *reg_state = (reg_validate_state *) entry->data;
 854
 855    nir_foreach_use(reg, src) {
 856       struct set_entry *entry = _mesa_set_search(reg_state->uses, src);
 857       assert(entry);
 858       _mesa_set_remove(reg_state->uses, entry);
 859    }
 860
 861    if (reg_state->uses->entries != 0) {
 862       printf("extra entries in register uses:\n");
 863       struct set_entry *entry;
 864       set_foreach(reg_state->uses, entry)
 865          printf("%p\n", entry->key);
 866
 867       abort();
 868    }
 869
 870    nir_foreach_if_use(reg, src) {
 871       struct set_entry *entry = _mesa_set_search(reg_state->if_uses, src);
 872       assert(entry);
 873       _mesa_set_remove(reg_state->if_uses, entry);
 874    }
 875
 876    if (reg_state->if_uses->entries != 0) {
 877       printf("extra entries in register if_uses:\n");
 878       struct set_entry *entry;
 879       set_foreach(reg_state->if_uses, entry)
 880          printf("%p\n", entry->key);
 881
 882       abort();
 883    }
 884
 885    nir_foreach_def(reg, src) {
 886       struct set_entry *entry = _mesa_set_search(reg_state->defs, src);
 887       assert(entry);
 888       _mesa_set_remove(reg_state->defs, entry);
 889    }
 890
 891    if (reg_state->defs->entries != 0) {
 892       printf("extra entries in register defs:\n");
 893       struct set_entry *entry;
 894       set_foreach(reg_state->defs, entry)
 895          printf("%p\n", entry->key);
 896
 897       abort();
 898    }
 899 }
 900
 901 static void
 902 validate_var_decl(nir_variable *var, bool is_global, validate_state *state)
 903 {
 904    assert(is_global == nir_variable_is_global(var));
 905
 906    /* Must have exactly one mode set */
 907    assert(util_bitcount(var->data.mode) == 1);
 908
 909    /*
 910     * TODO validate some things ir_validate.cpp does (requires more GLSL type
 911     * support)
 912     */
 913
 914    if (!is_global) {
 915       _mesa_hash_table_insert(state->var_defs, var, state->impl);
 916    }
 917 }
 918
 919 static bool
 920 postvalidate_ssa_def(nir_ssa_def *def, void *void_state)
 921 {
 922    validate_state *state = void_state;
 923
 924    struct hash_entry *entry = _mesa_hash_table_search(state->ssa_defs, def);
 925    ssa_def_validate_state *def_state = (ssa_def_validate_state *)entry->data;
 926
 927    nir_foreach_use(def, src) {
 928       struct set_entry *entry = _mesa_set_search(def_state->uses, src);
 929       assert(entry);
 930       _mesa_set_remove(def_state->uses, entry);
 931    }
 932
 933    if (def_state->uses->entries != 0) {
 934       printf("extra entries in register uses:\n");
 935       struct set_entry *entry;
 936       set_foreach(def_state->uses, entry)
 937          printf("%p\n", entry->key);
 938
 939       abort();
 940    }
 941
 942    nir_foreach_if_use(def, src) {
 943       struct set_entry *entry = _mesa_set_search(def_state->if_uses, src);
 944       assert(entry);
 945       _mesa_set_remove(def_state->if_uses, entry);
 946    }
 947
 948    if (def_state->if_uses->entries != 0) {
 949       printf("extra entries in register uses:\n");
 950       struct set_entry *entry;
 951       set_foreach(def_state->if_uses, entry)
 952          printf("%p\n", entry->key);
 953
 954       abort();
 955    }
 956
 957    return true;
 958 }
 959
 960 static bool
 961 postvalidate_ssa_defs_block(nir_block *block, void *state)
 962 {
 963    nir_foreach_instr(block, instr)
 964       nir_foreach_ssa_def(instr, postvalidate_ssa_def, state);
 965
 966    return true;
 967 }
 968
 969 static void
 970 validate_function_impl(nir_function_impl *impl, validate_state *state)
 971 {
 972    assert(impl->function->impl == impl);
 973    assert(impl->cf_node.parent == NULL);
 974
 975    assert(impl->num_params == impl->function->num_params);
 976    for (unsigned i = 0; i < impl->num_params; i++) {
 977       assert(impl->params[i]->type == impl->function->params[i].type);
 978       assert(impl->params[i]->data.mode == nir_var_param);
 979       assert(impl->params[i]->data.location == i);
 980       validate_var_decl(impl->params[i], false, state);
 981    }
 982
 983    if (glsl_type_is_void(impl->function->return_type)) {
 984       assert(impl->return_var == NULL);
 985    } else {
 986       assert(impl->return_var->type == impl->function->return_type);
 987       assert(impl->return_var->data.mode == nir_var_param);
 988       assert(impl->return_var->data.location == -1);
 989       validate_var_decl(impl->return_var, false, state);
 990    }
 991
 992    assert(exec_list_is_empty(&impl->end_block->instr_list));
 993    assert(impl->end_block->successors[0] == NULL);
 994    assert(impl->end_block->successors[1] == NULL);
 995
 996    state->impl = impl;
 997    state->parent_node = &impl->cf_node;
 998
 999    exec_list_validate(&impl->locals);
1000    nir_foreach_variable(var, &impl->locals) {
1001       validate_var_decl(var, false, state);
1002    }
1003
1004    state->regs_found = realloc(state->regs_found,
1005                                BITSET_WORDS(impl->reg_alloc) *
1006                                sizeof(BITSET_WORD));
1007    memset(state->regs_found, 0, BITSET_WORDS(impl->reg_alloc) *
1008                                 sizeof(BITSET_WORD));
1009    exec_list_validate(&impl->registers);
1010    foreach_list_typed(nir_register, reg, node, &impl->registers) {
1011       prevalidate_reg_decl(reg, false, state);
1012    }
1013
1014    state->ssa_defs_found = realloc(state->ssa_defs_found,
1015                                    BITSET_WORDS(impl->ssa_alloc) *
1016                                    sizeof(BITSET_WORD));
1017    memset(state->ssa_defs_found, 0, BITSET_WORDS(impl->ssa_alloc) *
1018                                     sizeof(BITSET_WORD));
1019    exec_list_validate(&impl->body);
1020    foreach_list_typed(nir_cf_node, node, node, &impl->body) {
1021       validate_cf_node(node, state);
1022    }
1023
1024    foreach_list_typed(nir_register, reg, node, &impl->registers) {
1025       postvalidate_reg_decl(reg, state);
1026    }
1027
1028    nir_foreach_block(impl, postvalidate_ssa_defs_block, state);
1029 }
1030
1031 static void
1032 validate_function(nir_function *func, validate_state *state)
1033 {
1034    if (func->impl != NULL) {
1035       assert(func->impl->function == func);
1036       validate_function_impl(func->impl, state);
1037    }
1038 }
1039
1040 static void
1041 init_validate_state(validate_state *state)
1042 {
1043    state->regs = _mesa_hash_table_create(NULL, _mesa_hash_pointer,
1044                                          _mesa_key_pointer_equal);
1045    state->ssa_defs = _mesa_hash_table_create(NULL, _mesa_hash_pointer,
1046                                              _mesa_key_pointer_equal);
1047    state->ssa_defs_found = NULL;
1048    state->regs_found = NULL;
1049    state->var_defs = _mesa_hash_table_create(NULL, _mesa_hash_pointer,
1050                                              _mesa_key_pointer_equal);
1051    state->loop = NULL;
1052 }
1053
1054 static void
1055 destroy_validate_state(validate_state *state)
1056 {
1057    _mesa_hash_table_destroy(state->regs, NULL);
1058    _mesa_hash_table_destroy(state->ssa_defs, NULL);
1059    free(state->ssa_defs_found);
1060    free(state->regs_found);
1061    _mesa_hash_table_destroy(state->var_defs, NULL);
1062 }
1063
1064 void
1065 nir_validate_shader(nir_shader *shader)
1066 {
1067    validate_state state;
1068    init_validate_state(&state);
1069
1070    state.shader = shader;
1071
1072    exec_list_validate(&shader->uniforms);
1073    nir_foreach_variable(var, &shader->uniforms) {
1074       validate_var_decl(var, true, &state);
1075    }
1076
1077    exec_list_validate(&shader->inputs);
1078    nir_foreach_variable(var, &shader->inputs) {
1079      validate_var_decl(var, true, &state);
1080    }
1081
1082    exec_list_validate(&shader->outputs);
1083    nir_foreach_variable(var, &shader->outputs) {
1084      validate_var_decl(var, true, &state);
1085    }
1086
1087    exec_list_validate(&shader->shared);
1088    nir_foreach_variable(var, &shader->shared) {
1089       validate_var_decl(var, true, &state);
1090    }
1091
1092    exec_list_validate(&shader->globals);
1093    nir_foreach_variable(var, &shader->globals) {
1094      validate_var_decl(var, true, &state);
1095    }
1096
1097    exec_list_validate(&shader->system_values);
1098    nir_foreach_variable(var, &shader->system_values) {
1099      validate_var_decl(var, true, &state);
1100    }
1101
1102    state.regs_found = realloc(state.regs_found,
1103                               BITSET_WORDS(shader->reg_alloc) *
1104                               sizeof(BITSET_WORD));
1105    memset(state.regs_found, 0, BITSET_WORDS(shader->reg_alloc) *
1106                                sizeof(BITSET_WORD));
1107    exec_list_validate(&shader->registers);
1108    foreach_list_typed(nir_register, reg, node, &shader->registers) {
1109       prevalidate_reg_decl(reg, true, &state);
1110    }
1111
1112    exec_list_validate(&shader->functions);
1113    foreach_list_typed(nir_function, func, node, &shader->functions) {
1114       validate_function(func, &state);
1115    }
1116
1117    foreach_list_typed(nir_register, reg, node, &shader->registers) {
1118       postvalidate_reg_decl(reg, &state);
1119    }
1120
1121    destroy_validate_state(&state);
1122 }
1123
1124 #endif /* NDEBUG */