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    if (src->src.is_ssa)
 183       num_components = src->src.ssa->num_components;
 184    else {
 185       if (src->src.reg.reg->is_packed)
 186          num_components = 4; /* can't check anything */
 187       else
 188          num_components = src->src.reg.reg->num_components;
 189    }
 190    for (unsigned i = 0; i < 4; i++) {
 191       assert(src->swizzle[i] < 4);
 192
 193       if (nir_alu_instr_channel_used(instr, index, i))
 194          assert(src->swizzle[i] < num_components);
 195    }
 196
 197    validate_src(&src->src, state);
 198 }
 199
 200 static void
 201 validate_reg_dest(nir_reg_dest *dest, validate_state *state)
 202 {
 203    assert(dest->reg != NULL);
 204
 205    assert(dest->parent_instr == state->instr);
 206
 207    struct hash_entry *entry2;
 208    entry2 = _mesa_hash_table_search(state->regs, dest->reg);
 209
 210    assert(entry2);
 211
 212    reg_validate_state *reg_state = (reg_validate_state *) entry2->data;
 213    _mesa_set_add(reg_state->defs, dest);
 214
 215    if (!dest->reg->is_global) {
 216       assert(reg_state->where_defined == state->impl &&
 217              "writing to a register declared in a different function");
 218    }
 219
 220    assert((dest->reg->num_array_elems == 0 ||
 221           dest->base_offset < dest->reg->num_array_elems) &&
 222           "definitely out-of-bounds array access");
 223
 224    if (dest->indirect) {
 225       assert(dest->reg->num_array_elems != 0);
 226       assert((dest->indirect->is_ssa || dest->indirect->reg.indirect == NULL) &&
 227              "only one level of indirection allowed");
 228       validate_src(dest->indirect, state);
 229    }
 230 }
 231
 232 static void
 233 validate_ssa_def(nir_ssa_def *def, validate_state *state)
 234 {
 235    assert(def->index < state->impl->ssa_alloc);
 236    assert(!BITSET_TEST(state->ssa_defs_found, def->index));
 237    BITSET_SET(state->ssa_defs_found, def->index);
 238
 239    assert(def->parent_instr == state->instr);
 240
 241    assert(def->num_components <= 4);
 242
 243    list_validate(&def->uses);
 244    list_validate(&def->if_uses);
 245
 246    ssa_def_validate_state *def_state = ralloc(state->ssa_defs,
 247                                               ssa_def_validate_state);
 248    def_state->where_defined = state->impl;
 249    def_state->uses = _mesa_set_create(def_state, _mesa_hash_pointer,
 250                                       _mesa_key_pointer_equal);
 251    def_state->if_uses = _mesa_set_create(def_state, _mesa_hash_pointer,
 252                                          _mesa_key_pointer_equal);
 253    _mesa_hash_table_insert(state->ssa_defs, def, def_state);
 254 }
 255
 256 static void
 257 validate_dest(nir_dest *dest, validate_state *state)
 258 {
 259    if (dest->is_ssa)
 260       validate_ssa_def(&dest->ssa, state);
 261    else
 262       validate_reg_dest(&dest->reg, state);
 263 }
 264
 265 static void
 266 validate_alu_dest(nir_alu_dest *dest, validate_state *state)
 267 {
 268    unsigned dest_size =
 269       dest->dest.is_ssa ? dest->dest.ssa.num_components
 270                         : dest->dest.reg.reg->num_components;
 271    bool is_packed = !dest->dest.is_ssa && dest->dest.reg.reg->is_packed;
 272    /*
 273     * validate that the instruction doesn't write to components not in the
 274     * register/SSA value
 275     */
 276    assert(is_packed || !(dest->write_mask & ~((1 << dest_size) - 1)));
 277
 278    /* validate that saturate is only ever used on instructions with
 279     * destinations of type float
 280     */
 281    nir_alu_instr *alu = nir_instr_as_alu(state->instr);
 282    assert(nir_op_infos[alu->op].output_type == nir_type_float ||
 283           !dest->saturate);
 284
 285    validate_dest(&dest->dest, state);
 286 }
 287
 288 static void
 289 validate_alu_instr(nir_alu_instr *instr, validate_state *state)
 290 {
 291    assert(instr->op < nir_num_opcodes);
 292
 293    for (unsigned i = 0; i < nir_op_infos[instr->op].num_inputs; i++) {
 294       validate_alu_src(instr, i, state);
 295    }
 296
 297    validate_alu_dest(&instr->dest, state);
 298 }
 299
 300 static void
 301 validate_deref_chain(nir_deref *deref, validate_state *state)
 302 {
 303    assert(deref->child == NULL || ralloc_parent(deref->child) == deref);
 304
 305    nir_deref *parent = NULL;
 306    while (deref != NULL) {
 307       switch (deref->deref_type) {
 308       case nir_deref_type_array:
 309          assert(deref->type == glsl_get_array_element(parent->type));
 310          if (nir_deref_as_array(deref)->deref_array_type ==
 311              nir_deref_array_type_indirect)
 312             validate_src(&nir_deref_as_array(deref)->indirect, state);
 313          break;
 314
 315       case nir_deref_type_struct:
 316          assert(deref->type ==
 317                 glsl_get_struct_field(parent->type,
 318                                       nir_deref_as_struct(deref)->index));
 319          break;
 320
 321       case nir_deref_type_var:
 322          break;
 323
 324       default:
 325          assert(!"Invalid deref type");
 326          break;
 327       }
 328
 329       parent = deref;
 330       deref = deref->child;
 331    }
 332 }
 333
 334 static void
 335 validate_var_use(nir_variable *var, validate_state *state)
 336 {
 337    if (var->data.mode == nir_var_local) {
 338       struct hash_entry *entry = _mesa_hash_table_search(state->var_defs, var);
 339
 340       assert(entry);
 341       assert((nir_function_impl *) entry->data == state->impl);
 342    }
 343 }
 344
 345 static void
 346 validate_deref_var(void *parent_mem_ctx, nir_deref_var *deref, validate_state *state)
 347 {
 348    assert(deref != NULL);
 349    assert(ralloc_parent(deref) == parent_mem_ctx);
 350    assert(deref->deref.type == deref->var->type);
 351
 352    validate_var_use(deref->var, state);
 353
 354    validate_deref_chain(&deref->deref, state);
 355 }
 356
 357 static void
 358 validate_intrinsic_instr(nir_intrinsic_instr *instr, validate_state *state)
 359 {
 360    unsigned num_srcs = nir_intrinsic_infos[instr->intrinsic].num_srcs;
 361    for (unsigned i = 0; i < num_srcs; i++) {
 362       unsigned components_read =
 363          nir_intrinsic_infos[instr->intrinsic].src_components[i];
 364       if (components_read == 0)
 365          components_read = instr->num_components;
 366
 367       assert(components_read > 0);
 368
 369       if (instr->src[i].is_ssa) {
 370          assert(components_read <= instr->src[i].ssa->num_components);
 371       } else if (!instr->src[i].reg.reg->is_packed) {
 372          assert(components_read <= instr->src[i].reg.reg->num_components);
 373       }
 374
 375       validate_src(&instr->src[i], state);
 376    }
 377
 378    unsigned num_vars = nir_intrinsic_infos[instr->intrinsic].num_variables;
 379    for (unsigned i = 0; i < num_vars; i++) {
 380       validate_deref_var(instr, instr->variables[i], state);
 381    }
 382
 383    if (nir_intrinsic_infos[instr->intrinsic].has_dest) {
 384       unsigned components_written =
 385          nir_intrinsic_infos[instr->intrinsic].dest_components;
 386       if (components_written == 0)
 387          components_written = instr->num_components;
 388
 389       assert(components_written > 0);
 390
 391       if (instr->dest.is_ssa) {
 392          assert(components_written <= instr->dest.ssa.num_components);
 393       } else if (!instr->dest.reg.reg->is_packed) {
 394          assert(components_written <= instr->dest.reg.reg->num_components);
 395       }
 396
 397       validate_dest(&instr->dest, state);
 398    }
 399
 400    switch (instr->intrinsic) {
 401    case nir_intrinsic_load_var: {
 402       const struct glsl_type *type =
 403          nir_deref_tail(&instr->variables[0]->deref)->type;
 404       assert(glsl_type_is_vector_or_scalar(type) ||
 405              (instr->variables[0]->var->data.mode == nir_var_uniform &&
 406               glsl_get_base_type(type) == GLSL_TYPE_SUBROUTINE));
 407       assert(instr->num_components == glsl_get_vector_elements(type));
 408       break;
 409    }
 410    case nir_intrinsic_store_var: {
 411       const struct glsl_type *type =
 412          nir_deref_tail(&instr->variables[0]->deref)->type;
 413       assert(glsl_type_is_vector_or_scalar(type) ||
 414              (instr->variables[0]->var->data.mode == nir_var_uniform &&
 415               glsl_get_base_type(type) == GLSL_TYPE_SUBROUTINE));
 416       assert(instr->num_components == glsl_get_vector_elements(type));
 417       assert(instr->variables[0]->var->data.mode != nir_var_shader_in &&
 418              instr->variables[0]->var->data.mode != nir_var_uniform &&
 419              instr->variables[0]->var->data.mode != nir_var_shader_storage);
 420       assert((nir_intrinsic_write_mask(instr) & ~((1 << instr->num_components) - 1)) == 0);
 421       break;
 422    }
 423    case nir_intrinsic_copy_var:
 424       assert(nir_deref_tail(&instr->variables[0]->deref)->type ==
 425              nir_deref_tail(&instr->variables[1]->deref)->type);
 426       assert(instr->variables[0]->var->data.mode != nir_var_shader_in &&
 427              instr->variables[0]->var->data.mode != nir_var_uniform &&
 428              instr->variables[0]->var->data.mode != nir_var_shader_storage);
 429       break;
 430    default:
 431       break;
 432    }
 433 }
 434
 435 static void
 436 validate_tex_instr(nir_tex_instr *instr, validate_state *state)
 437 {
 438    bool src_type_seen[nir_num_tex_src_types];
 439    for (unsigned i = 0; i < nir_num_tex_src_types; i++)
 440       src_type_seen[i] = false;
 441
 442    for (unsigned i = 0; i < instr->num_srcs; i++) {
 443       assert(!src_type_seen[instr->src[i].src_type]);
 444       src_type_seen[instr->src[i].src_type] = true;
 445       validate_src(&instr->src[i].src, state);
 446    }
 447
 448    if (instr->texture != NULL)
 449       validate_deref_var(instr, instr->texture, state);
 450
 451    if (instr->sampler != NULL)
 452       validate_deref_var(instr, instr->sampler, state);
 453
 454    validate_dest(&instr->dest, state);
 455 }
 456
 457 static void
 458 validate_call_instr(nir_call_instr *instr, validate_state *state)
 459 {
 460    if (instr->return_deref == NULL) {
 461       assert(glsl_type_is_void(instr->callee->return_type));
 462    } else {
 463       assert(instr->return_deref->deref.type == instr->callee->return_type);
 464       validate_deref_var(instr, instr->return_deref, state);
 465    }
 466
 467    assert(instr->num_params == instr->callee->num_params);
 468
 469    for (unsigned i = 0; i < instr->num_params; i++) {
 470       assert(instr->callee->params[i].type == instr->params[i]->deref.type);
 471       validate_deref_var(instr, instr->params[i], state);
 472    }
 473 }
 474
 475 static void
 476 validate_load_const_instr(nir_load_const_instr *instr, validate_state *state)
 477 {
 478    validate_ssa_def(&instr->def, state);
 479 }
 480
 481 static void
 482 validate_ssa_undef_instr(nir_ssa_undef_instr *instr, validate_state *state)
 483 {
 484    validate_ssa_def(&instr->def, state);
 485 }
 486
 487 static void
 488 validate_phi_instr(nir_phi_instr *instr, validate_state *state)
 489 {
 490    /*
 491     * don't validate the sources until we get to them from their predecessor
 492     * basic blocks, to avoid validating an SSA use before its definition.
 493     */
 494
 495    validate_dest(&instr->dest, state);
 496
 497    exec_list_validate(&instr->srcs);
 498    assert(exec_list_length(&instr->srcs) ==
 499           state->block->predecessors->entries);
 500 }
 501
 502 static void
 503 validate_instr(nir_instr *instr, validate_state *state)
 504 {
 505    assert(instr->block == state->block);
 506
 507    state->instr = instr;
 508
 509    switch (instr->type) {
 510    case nir_instr_type_alu:
 511       validate_alu_instr(nir_instr_as_alu(instr), state);
 512       break;
 513
 514    case nir_instr_type_call:
 515       validate_call_instr(nir_instr_as_call(instr), state);
 516       break;
 517
 518    case nir_instr_type_intrinsic:
 519       validate_intrinsic_instr(nir_instr_as_intrinsic(instr), state);
 520       break;
 521
 522    case nir_instr_type_tex:
 523       validate_tex_instr(nir_instr_as_tex(instr), state);
 524       break;
 525
 526    case nir_instr_type_load_const:
 527       validate_load_const_instr(nir_instr_as_load_const(instr), state);
 528       break;
 529
 530    case nir_instr_type_phi:
 531       validate_phi_instr(nir_instr_as_phi(instr), state);
 532       break;
 533
 534    case nir_instr_type_ssa_undef:
 535       validate_ssa_undef_instr(nir_instr_as_ssa_undef(instr), state);
 536       break;
 537
 538    case nir_instr_type_jump:
 539       break;
 540
 541    default:
 542       assert(!"Invalid ALU instruction type");
 543       break;
 544    }
 545
 546    state->instr = NULL;
 547 }
 548
 549 static void
 550 validate_phi_src(nir_phi_instr *instr, nir_block *pred, validate_state *state)
 551 {
 552    state->instr = &instr->instr;
 553
 554    assert(instr->dest.is_ssa);
 555
 556    exec_list_validate(&instr->srcs);
 557    nir_foreach_phi_src(instr, src) {
 558       if (src->pred == pred) {
 559          assert(src->src.is_ssa);
 560          assert(src->src.ssa->num_components ==
 561                 instr->dest.ssa.num_components);
 562
 563          validate_src(&src->src, state);
 564          state->instr = NULL;
 565          return;
 566       }
 567    }
 568
 569    abort();
 570 }
 571
 572 static void
 573 validate_phi_srcs(nir_block *block, nir_block *succ, validate_state *state)
 574 {
 575    nir_foreach_instr(succ, instr) {
 576       if (instr->type != nir_instr_type_phi)
 577          break;
 578
 579       validate_phi_src(nir_instr_as_phi(instr), block, state);
 580    }
 581 }
 582
 583 static void validate_cf_node(nir_cf_node *node, validate_state *state);
 584
 585 static void
 586 validate_block(nir_block *block, validate_state *state)
 587 {
 588    assert(block->cf_node.parent == state->parent_node);
 589
 590    state->block = block;
 591
 592    exec_list_validate(&block->instr_list);
 593    nir_foreach_instr(block, instr) {
 594       if (instr->type == nir_instr_type_phi) {
 595          assert(instr == nir_block_first_instr(block) ||
 596                 nir_instr_prev(instr)->type == nir_instr_type_phi);
 597       }
 598
 599       if (instr->type == nir_instr_type_jump) {
 600          assert(instr == nir_block_last_instr(block));
 601       }
 602
 603       validate_instr(instr, state);
 604    }
 605
 606    assert(block->successors[0] != NULL);
 607    assert(block->successors[0] != block->successors[1]);
 608
 609    for (unsigned i = 0; i < 2; i++) {
 610       if (block->successors[i] != NULL) {
 611          struct set_entry *entry =
 612             _mesa_set_search(block->successors[i]->predecessors, block);
 613          assert(entry);
 614
 615          validate_phi_srcs(block, block->successors[i], state);
 616       }
 617    }
 618
 619    struct set_entry *entry;
 620    set_foreach(block->predecessors, entry) {
 621       const nir_block *pred = entry->key;
 622       assert(pred->successors[0] == block ||
 623              pred->successors[1] == block);
 624    }
 625
 626    if (!exec_list_is_empty(&block->instr_list) &&
 627        nir_block_last_instr(block)->type == nir_instr_type_jump) {
 628       assert(block->successors[1] == NULL);
 629       nir_jump_instr *jump = nir_instr_as_jump(nir_block_last_instr(block));
 630       switch (jump->type) {
 631       case nir_jump_break: {
 632          nir_block *after =
 633             nir_cf_node_as_block(nir_cf_node_next(&state->loop->cf_node));
 634          assert(block->successors[0] == after);
 635          break;
 636       }
 637
 638       case nir_jump_continue: {
 639          nir_block *first =
 640             nir_cf_node_as_block(nir_loop_first_cf_node(state->loop));
 641          assert(block->successors[0] == first);
 642          break;
 643       }
 644
 645       case nir_jump_return:
 646          assert(block->successors[0] == state->impl->end_block);
 647          break;
 648
 649       default:
 650          unreachable("bad jump type");
 651       }
 652    } else {
 653       nir_cf_node *next = nir_cf_node_next(&block->cf_node);
 654       if (next == NULL) {
 655          switch (state->parent_node->type) {
 656          case nir_cf_node_loop: {
 657             nir_block *first =
 658                nir_cf_node_as_block(nir_loop_first_cf_node(state->loop));
 659             assert(block->successors[0] == first);
 660             /* due to the hack for infinite loops, block->successors[1] may
 661              * point to the block after the loop.
 662              */
 663             break;
 664          }
 665
 666          case nir_cf_node_if: {
 667             nir_block *after =
 668                nir_cf_node_as_block(nir_cf_node_next(state->parent_node));
 669             assert(block->successors[0] == after);
 670             assert(block->successors[1] == NULL);
 671             break;
 672          }
 673
 674          case nir_cf_node_function:
 675             assert(block->successors[0] == state->impl->end_block);
 676             assert(block->successors[1] == NULL);
 677             break;
 678
 679          default:
 680             unreachable("unknown control flow node type");
 681          }
 682       } else {
 683          if (next->type == nir_cf_node_if) {
 684             nir_if *if_stmt = nir_cf_node_as_if(next);
 685             assert(&block->successors[0]->cf_node ==
 686                    nir_if_first_then_node(if_stmt));
 687             assert(&block->successors[1]->cf_node ==
 688                    nir_if_first_else_node(if_stmt));
 689          } else {
 690             assert(next->type == nir_cf_node_loop);
 691             nir_loop *loop = nir_cf_node_as_loop(next);
 692             assert(&block->successors[0]->cf_node ==
 693                    nir_loop_first_cf_node(loop));
 694             assert(block->successors[1] == NULL);
 695          }
 696       }
 697    }
 698 }
 699
 700 static void
 701 validate_if(nir_if *if_stmt, validate_state *state)
 702 {
 703    state->if_stmt = if_stmt;
 704
 705    assert(!exec_node_is_head_sentinel(if_stmt->cf_node.node.prev));
 706    nir_cf_node *prev_node = nir_cf_node_prev(&if_stmt->cf_node);
 707    assert(prev_node->type == nir_cf_node_block);
 708
 709    assert(!exec_node_is_tail_sentinel(if_stmt->cf_node.node.next));
 710    nir_cf_node *next_node = nir_cf_node_next(&if_stmt->cf_node);
 711    assert(next_node->type == nir_cf_node_block);
 712
 713    validate_src(&if_stmt->condition, state);
 714
 715    assert(!exec_list_is_empty(&if_stmt->then_list));
 716    assert(!exec_list_is_empty(&if_stmt->else_list));
 717
 718    nir_cf_node *old_parent = state->parent_node;
 719    state->parent_node = &if_stmt->cf_node;
 720
 721    exec_list_validate(&if_stmt->then_list);
 722    foreach_list_typed(nir_cf_node, cf_node, node, &if_stmt->then_list) {
 723       validate_cf_node(cf_node, state);
 724    }
 725
 726    exec_list_validate(&if_stmt->else_list);
 727    foreach_list_typed(nir_cf_node, cf_node, node, &if_stmt->else_list) {
 728       validate_cf_node(cf_node, state);
 729    }
 730
 731    state->parent_node = old_parent;
 732    state->if_stmt = NULL;
 733 }
 734
 735 static void
 736 validate_loop(nir_loop *loop, validate_state *state)
 737 {
 738    assert(!exec_node_is_head_sentinel(loop->cf_node.node.prev));
 739    nir_cf_node *prev_node = nir_cf_node_prev(&loop->cf_node);
 740    assert(prev_node->type == nir_cf_node_block);
 741
 742    assert(!exec_node_is_tail_sentinel(loop->cf_node.node.next));
 743    nir_cf_node *next_node = nir_cf_node_next(&loop->cf_node);
 744    assert(next_node->type == nir_cf_node_block);
 745
 746    assert(!exec_list_is_empty(&loop->body));
 747
 748    nir_cf_node *old_parent = state->parent_node;
 749    state->parent_node = &loop->cf_node;
 750    nir_loop *old_loop = state->loop;
 751    state->loop = loop;
 752
 753    exec_list_validate(&loop->body);
 754    foreach_list_typed(nir_cf_node, cf_node, node, &loop->body) {
 755       validate_cf_node(cf_node, state);
 756    }
 757
 758    state->parent_node = old_parent;
 759    state->loop = old_loop;
 760 }
 761
 762 static void
 763 validate_cf_node(nir_cf_node *node, validate_state *state)
 764 {
 765    assert(node->parent == state->parent_node);
 766
 767    switch (node->type) {
 768    case nir_cf_node_block:
 769       validate_block(nir_cf_node_as_block(node), state);
 770       break;
 771
 772    case nir_cf_node_if:
 773       validate_if(nir_cf_node_as_if(node), state);
 774       break;
 775
 776    case nir_cf_node_loop:
 777       validate_loop(nir_cf_node_as_loop(node), state);
 778       break;
 779
 780    default:
 781       unreachable("Invalid CF node type");
 782    }
 783 }
 784
 785 static void
 786 prevalidate_reg_decl(nir_register *reg, bool is_global, validate_state *state)
 787 {
 788    assert(reg->is_global == is_global);
 789
 790    if (is_global)
 791       assert(reg->index < state->shader->reg_alloc);
 792    else
 793       assert(reg->index < state->impl->reg_alloc);
 794    assert(!BITSET_TEST(state->regs_found, reg->index));
 795    BITSET_SET(state->regs_found, reg->index);
 796
 797    list_validate(&reg->uses);
 798    list_validate(&reg->defs);
 799    list_validate(&reg->if_uses);
 800
 801    reg_validate_state *reg_state = ralloc(state->regs, reg_validate_state);
 802    reg_state->uses = _mesa_set_create(reg_state, _mesa_hash_pointer,
 803                                       _mesa_key_pointer_equal);
 804    reg_state->if_uses = _mesa_set_create(reg_state, _mesa_hash_pointer,
 805                                          _mesa_key_pointer_equal);
 806    reg_state->defs = _mesa_set_create(reg_state, _mesa_hash_pointer,
 807                                       _mesa_key_pointer_equal);
 808
 809    reg_state->where_defined = is_global ? NULL : state->impl;
 810
 811    _mesa_hash_table_insert(state->regs, reg, reg_state);
 812 }
 813
 814 static void
 815 postvalidate_reg_decl(nir_register *reg, validate_state *state)
 816 {
 817    struct hash_entry *entry = _mesa_hash_table_search(state->regs, reg);
 818
 819    reg_validate_state *reg_state = (reg_validate_state *) entry->data;
 820
 821    nir_foreach_use(reg, src) {
 822       struct set_entry *entry = _mesa_set_search(reg_state->uses, src);
 823       assert(entry);
 824       _mesa_set_remove(reg_state->uses, entry);
 825    }
 826
 827    if (reg_state->uses->entries != 0) {
 828       printf("extra entries in register uses:\n");
 829       struct set_entry *entry;
 830       set_foreach(reg_state->uses, entry)
 831          printf("%p\n", entry->key);
 832
 833       abort();
 834    }
 835
 836    nir_foreach_if_use(reg, src) {
 837       struct set_entry *entry = _mesa_set_search(reg_state->if_uses, src);
 838       assert(entry);
 839       _mesa_set_remove(reg_state->if_uses, entry);
 840    }
 841
 842    if (reg_state->if_uses->entries != 0) {
 843       printf("extra entries in register if_uses:\n");
 844       struct set_entry *entry;
 845       set_foreach(reg_state->if_uses, entry)
 846          printf("%p\n", entry->key);
 847
 848       abort();
 849    }
 850
 851    nir_foreach_def(reg, src) {
 852       struct set_entry *entry = _mesa_set_search(reg_state->defs, src);
 853       assert(entry);
 854       _mesa_set_remove(reg_state->defs, entry);
 855    }
 856
 857    if (reg_state->defs->entries != 0) {
 858       printf("extra entries in register defs:\n");
 859       struct set_entry *entry;
 860       set_foreach(reg_state->defs, entry)
 861          printf("%p\n", entry->key);
 862
 863       abort();
 864    }
 865 }
 866
 867 static void
 868 validate_var_decl(nir_variable *var, bool is_global, validate_state *state)
 869 {
 870    assert(is_global == nir_variable_is_global(var));
 871
 872    /*
 873     * TODO validate some things ir_validate.cpp does (requires more GLSL type
 874     * support)
 875     */
 876
 877    if (!is_global) {
 878       _mesa_hash_table_insert(state->var_defs, var, state->impl);
 879    }
 880 }
 881
 882 static bool
 883 postvalidate_ssa_def(nir_ssa_def *def, void *void_state)
 884 {
 885    validate_state *state = void_state;
 886
 887    struct hash_entry *entry = _mesa_hash_table_search(state->ssa_defs, def);
 888    ssa_def_validate_state *def_state = (ssa_def_validate_state *)entry->data;
 889
 890    nir_foreach_use(def, src) {
 891       struct set_entry *entry = _mesa_set_search(def_state->uses, src);
 892       assert(entry);
 893       _mesa_set_remove(def_state->uses, entry);
 894    }
 895
 896    if (def_state->uses->entries != 0) {
 897       printf("extra entries in register uses:\n");
 898       struct set_entry *entry;
 899       set_foreach(def_state->uses, entry)
 900          printf("%p\n", entry->key);
 901
 902       abort();
 903    }
 904
 905    nir_foreach_if_use(def, src) {
 906       struct set_entry *entry = _mesa_set_search(def_state->if_uses, src);
 907       assert(entry);
 908       _mesa_set_remove(def_state->if_uses, entry);
 909    }
 910
 911    if (def_state->if_uses->entries != 0) {
 912       printf("extra entries in register uses:\n");
 913       struct set_entry *entry;
 914       set_foreach(def_state->if_uses, entry)
 915          printf("%p\n", entry->key);
 916
 917       abort();
 918    }
 919
 920    return true;
 921 }
 922
 923 static bool
 924 postvalidate_ssa_defs_block(nir_block *block, void *state)
 925 {
 926    nir_foreach_instr(block, instr)
 927       nir_foreach_ssa_def(instr, postvalidate_ssa_def, state);
 928
 929    return true;
 930 }
 931
 932 static void
 933 validate_function_impl(nir_function_impl *impl, validate_state *state)
 934 {
 935    assert(impl->function->impl == impl);
 936    assert(impl->cf_node.parent == NULL);
 937
 938    assert(impl->num_params == impl->function->num_params);
 939    for (unsigned i = 0; i < impl->num_params; i++) {
 940       assert(impl->params[i]->type == impl->function->params[i].type);
 941       assert(impl->params[i]->data.location == i);
 942       validate_var_decl(impl->params[i], false, state);
 943    }
 944
 945    if (glsl_type_is_void(impl->function->return_type)) {
 946       assert(impl->return_var == NULL);
 947    } else {
 948       assert(impl->return_var->type == impl->function->return_type);
 949       assert(impl->return_var->data.location == -1);
 950       validate_var_decl(impl->return_var, false, state);
 951    }
 952
 953    assert(exec_list_is_empty(&impl->end_block->instr_list));
 954    assert(impl->end_block->successors[0] == NULL);
 955    assert(impl->end_block->successors[1] == NULL);
 956
 957    state->impl = impl;
 958    state->parent_node = &impl->cf_node;
 959
 960    exec_list_validate(&impl->locals);
 961    nir_foreach_variable(var, &impl->locals) {
 962       validate_var_decl(var, false, state);
 963    }
 964
 965    state->regs_found = realloc(state->regs_found,
 966                                BITSET_WORDS(impl->reg_alloc) *
 967                                sizeof(BITSET_WORD));
 968    memset(state->regs_found, 0, BITSET_WORDS(impl->reg_alloc) *
 969                                 sizeof(BITSET_WORD));
 970    exec_list_validate(&impl->registers);
 971    foreach_list_typed(nir_register, reg, node, &impl->registers) {
 972       prevalidate_reg_decl(reg, false, state);
 973    }
 974
 975    state->ssa_defs_found = realloc(state->ssa_defs_found,
 976                                    BITSET_WORDS(impl->ssa_alloc) *
 977                                    sizeof(BITSET_WORD));
 978    memset(state->ssa_defs_found, 0, BITSET_WORDS(impl->ssa_alloc) *
 979                                     sizeof(BITSET_WORD));
 980    exec_list_validate(&impl->body);
 981    foreach_list_typed(nir_cf_node, node, node, &impl->body) {
 982       validate_cf_node(node, state);
 983    }
 984
 985    foreach_list_typed(nir_register, reg, node, &impl->registers) {
 986       postvalidate_reg_decl(reg, state);
 987    }
 988
 989    nir_foreach_block(impl, postvalidate_ssa_defs_block, state);
 990 }
 991
 992 static void
 993 validate_function(nir_function *func, validate_state *state)
 994 {
 995    if (func->impl != NULL) {
 996       assert(func->impl->function == func);
 997       validate_function_impl(func->impl, state);
 998    }
 999 }
1000
1001 static void
1002 init_validate_state(validate_state *state)
1003 {
1004    state->regs = _mesa_hash_table_create(NULL, _mesa_hash_pointer,
1005                                          _mesa_key_pointer_equal);
1006    state->ssa_defs = _mesa_hash_table_create(NULL, _mesa_hash_pointer,
1007                                              _mesa_key_pointer_equal);
1008    state->ssa_defs_found = NULL;
1009    state->regs_found = NULL;
1010    state->var_defs = _mesa_hash_table_create(NULL, _mesa_hash_pointer,
1011                                              _mesa_key_pointer_equal);
1012    state->loop = NULL;
1013 }
1014
1015 static void
1016 destroy_validate_state(validate_state *state)
1017 {
1018    _mesa_hash_table_destroy(state->regs, NULL);
1019    _mesa_hash_table_destroy(state->ssa_defs, NULL);
1020    free(state->ssa_defs_found);
1021    free(state->regs_found);
1022    _mesa_hash_table_destroy(state->var_defs, NULL);
1023 }
1024
1025 void
1026 nir_validate_shader(nir_shader *shader)
1027 {
1028    validate_state state;
1029    init_validate_state(&state);
1030
1031    state.shader = shader;
1032
1033    exec_list_validate(&shader->uniforms);
1034    nir_foreach_variable(var, &shader->uniforms) {
1035       validate_var_decl(var, true, &state);
1036    }
1037
1038    exec_list_validate(&shader->inputs);
1039    nir_foreach_variable(var, &shader->inputs) {
1040      validate_var_decl(var, true, &state);
1041    }
1042
1043    exec_list_validate(&shader->outputs);
1044    nir_foreach_variable(var, &shader->outputs) {
1045      validate_var_decl(var, true, &state);
1046    }
1047
1048    exec_list_validate(&shader->shared);
1049    nir_foreach_variable(var, &shader->shared) {
1050       validate_var_decl(var, true, &state);
1051    }
1052
1053    exec_list_validate(&shader->globals);
1054    nir_foreach_variable(var, &shader->globals) {
1055      validate_var_decl(var, true, &state);
1056    }
1057
1058    exec_list_validate(&shader->system_values);
1059    nir_foreach_variable(var, &shader->system_values) {
1060      validate_var_decl(var, true, &state);
1061    }
1062
1063    state.regs_found = realloc(state.regs_found,
1064                               BITSET_WORDS(shader->reg_alloc) *
1065                               sizeof(BITSET_WORD));
1066    memset(state.regs_found, 0, BITSET_WORDS(shader->reg_alloc) *
1067                                sizeof(BITSET_WORD));
1068    exec_list_validate(&shader->registers);
1069    foreach_list_typed(nir_register, reg, node, &shader->registers) {
1070       prevalidate_reg_decl(reg, true, &state);
1071    }
1072
1073    exec_list_validate(&shader->functions);
1074    foreach_list_typed(nir_function, func, node, &shader->functions) {
1075       validate_function(func, &state);
1076    }
1077
1078    foreach_list_typed(nir_register, reg, node, &shader->registers) {
1079       postvalidate_reg_decl(reg, &state);
1080    }
1081
1082    destroy_validate_state(&state);
1083 }
1084
1085 #endif /* NDEBUG */