src/compiler/spirv/vtn_cfg.c

   1 /*
   2  * Copyright © 2015 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
  24 #include "vtn_private.h"
  25 #include "nir/nir_vla.h"
  26
  27 static struct vtn_pointer *
  28 vtn_pointer_for_image_or_sampler_variable(struct vtn_builder *b,
  29                                           struct vtn_variable *var)
  30 {
  31    assert(var->type->base_type == vtn_base_type_image ||
  32           var->type->base_type == vtn_base_type_sampler);
  33
  34    struct vtn_type *ptr_type = rzalloc(b, struct vtn_type);
  35    ptr_type->base_type = vtn_base_type_pointer;
  36    ptr_type->storage_class = SpvStorageClassUniformConstant;
  37    ptr_type->deref = var->type;
  38
  39    return vtn_pointer_for_variable(b, var, ptr_type);
  40 }
  41
  42 static bool
  43 vtn_cfg_handle_prepass_instruction(struct vtn_builder *b, SpvOp opcode,
  44                                    const uint32_t *w, unsigned count)
  45 {
  46    switch (opcode) {
  47    case SpvOpFunction: {
  48       vtn_assert(b->func == NULL);
  49       b->func = rzalloc(b, struct vtn_function);
  50
  51       list_inithead(&b->func->body);
  52       b->func->control = w[3];
  53
  54       MAYBE_UNUSED const struct glsl_type *result_type =
  55          vtn_value(b, w[1], vtn_value_type_type)->type->type;
  56       struct vtn_value *val = vtn_push_value(b, w[2], vtn_value_type_function);
  57       val->func = b->func;
  58
  59       const struct vtn_type *func_type =
  60          vtn_value(b, w[4], vtn_value_type_type)->type;
  61
  62       vtn_assert(func_type->return_type->type == result_type);
  63
  64       nir_function *func =
  65          nir_function_create(b->shader, ralloc_strdup(b->shader, val->name));
  66
  67       func->num_params = func_type->length;
  68       func->params = ralloc_array(b->shader, nir_parameter, func->num_params);
  69       unsigned np = 0;
  70       for (unsigned i = 0; i < func_type->length; i++) {
  71          if (func_type->params[i]->base_type == vtn_base_type_pointer &&
  72              func_type->params[i]->type == NULL) {
  73             func->params[np].type = func_type->params[i]->deref->type;
  74             func->params[np].param_type = nir_parameter_inout;
  75             np++;
  76          } else if (func_type->params[i]->base_type ==
  77                     vtn_base_type_sampled_image) {
  78             /* Sampled images are actually two parameters */
  79             func->params = reralloc(b->shader, func->params,
  80                                     nir_parameter, func->num_params++);
  81             func->params[np].type = func_type->params[i]->type;
  82             func->params[np].param_type = nir_parameter_in;
  83             np++;
  84             func->params[np].type = glsl_bare_sampler_type();
  85             func->params[np].param_type = nir_parameter_in;
  86             np++;
  87          } else {
  88             func->params[np].type = func_type->params[i]->type;
  89             func->params[np].param_type = nir_parameter_in;
  90             np++;
  91          }
  92       }
  93       assert(np == func->num_params);
  94
  95       func->return_type = func_type->return_type->type;
  96
  97       b->func->impl = nir_function_impl_create(func);
  98       b->nb.cursor = nir_before_cf_list(&b->func->impl->body);
  99
 100       b->func_param_idx = 0;
 101       break;
 102    }
 103
 104    case SpvOpFunctionEnd:
 105       b->func->end = w;
 106       b->func = NULL;
 107       break;
 108
 109    case SpvOpFunctionParameter: {
 110       struct vtn_type *type = vtn_value(b, w[1], vtn_value_type_type)->type;
 111
 112       vtn_assert(b->func_param_idx < b->func->impl->num_params);
 113       nir_variable *param = b->func->impl->params[b->func_param_idx++];
 114
 115       if (type->base_type == vtn_base_type_pointer && type->type == NULL) {
 116          struct vtn_variable *vtn_var = rzalloc(b, struct vtn_variable);
 117          vtn_var->type = type->deref;
 118          vtn_var->var = param;
 119
 120          vtn_assert(vtn_var->type->type == param->type);
 121
 122          struct vtn_type *without_array = vtn_var->type;
 123          while(glsl_type_is_array(without_array->type))
 124             without_array = without_array->array_element;
 125
 126          if (glsl_type_is_image(without_array->type)) {
 127             vtn_var->mode = vtn_variable_mode_uniform;
 128             param->interface_type = without_array->type;
 129          } else if (glsl_type_is_sampler(without_array->type)) {
 130             vtn_var->mode = vtn_variable_mode_uniform;
 131             param->interface_type = without_array->type;
 132          } else {
 133             vtn_var->mode = vtn_variable_mode_param;
 134          }
 135
 136          struct vtn_value *val =
 137             vtn_push_value(b, w[2], vtn_value_type_pointer);
 138
 139          /* Name the parameter so it shows up nicely in NIR */
 140          param->name = ralloc_strdup(param, val->name);
 141
 142          val->pointer = vtn_pointer_for_variable(b, vtn_var, type);
 143       } else if (type->base_type == vtn_base_type_image ||
 144                  type->base_type == vtn_base_type_sampler ||
 145                  type->base_type == vtn_base_type_sampled_image) {
 146          struct vtn_variable *vtn_var = rzalloc(b, struct vtn_variable);
 147          vtn_var->type = type;
 148          vtn_var->var = param;
 149          param->interface_type = param->type;
 150
 151          if (type->base_type == vtn_base_type_sampled_image) {
 152             /* Sampled images are actually two parameters.  The first is the
 153              * image and the second is the sampler.
 154              */
 155             struct vtn_value *val =
 156                vtn_push_value(b, w[2], vtn_value_type_sampled_image);
 157
 158             /* Name the parameter so it shows up nicely in NIR */
 159             param->name = ralloc_strdup(param, val->name);
 160
 161             /* Adjust the type of the image variable to the image type */
 162             vtn_var->type = type->image;
 163
 164             /* Now get the sampler parameter and set up its variable */
 165             param = b->func->impl->params[b->func_param_idx++];
 166             struct vtn_variable *sampler_var = rzalloc(b, struct vtn_variable);
 167             sampler_var->type = rzalloc(b, struct vtn_type);
 168             sampler_var->type->base_type = vtn_base_type_sampler;
 169             sampler_var->type->type = glsl_bare_sampler_type();
 170             sampler_var->var = param;
 171             param->interface_type = param->type;
 172             param->name = ralloc_strdup(param, val->name);
 173
 174             val->sampled_image = ralloc(b, struct vtn_sampled_image);
 175             val->sampled_image->type = type;
 176             val->sampled_image->image =
 177                vtn_pointer_for_image_or_sampler_variable(b, vtn_var);
 178             val->sampled_image->sampler =
 179                vtn_pointer_for_image_or_sampler_variable(b, sampler_var);
 180          } else {
 181             struct vtn_value *val =
 182                vtn_push_value(b, w[2], vtn_value_type_pointer);
 183
 184             /* Name the parameter so it shows up nicely in NIR */
 185             param->name = ralloc_strdup(param, val->name);
 186
 187             val->pointer =
 188                vtn_pointer_for_image_or_sampler_variable(b, vtn_var);
 189          }
 190       } else {
 191          /* We're a regular SSA value. */
 192          struct vtn_ssa_value *param_ssa =
 193             vtn_local_load(b, nir_deref_var_create(b, param));
 194          struct vtn_value *val = vtn_push_ssa(b, w[2], type, param_ssa);
 195
 196          /* Name the parameter so it shows up nicely in NIR */
 197          param->name = ralloc_strdup(param, val->name);
 198       }
 199       break;
 200    }
 201
 202    case SpvOpLabel: {
 203       vtn_assert(b->block == NULL);
 204       b->block = rzalloc(b, struct vtn_block);
 205       b->block->node.type = vtn_cf_node_type_block;
 206       b->block->label = w;
 207       vtn_push_value(b, w[1], vtn_value_type_block)->block = b->block;
 208
 209       if (b->func->start_block == NULL) {
 210          /* This is the first block encountered for this function.  In this
 211           * case, we set the start block and add it to the list of
 212           * implemented functions that we'll walk later.
 213           */
 214          b->func->start_block = b->block;
 215          exec_list_push_tail(&b->functions, &b->func->node);
 216       }
 217       break;
 218    }
 219
 220    case SpvOpSelectionMerge:
 221    case SpvOpLoopMerge:
 222       vtn_assert(b->block && b->block->merge == NULL);
 223       b->block->merge = w;
 224       break;
 225
 226    case SpvOpBranch:
 227    case SpvOpBranchConditional:
 228    case SpvOpSwitch:
 229    case SpvOpKill:
 230    case SpvOpReturn:
 231    case SpvOpReturnValue:
 232    case SpvOpUnreachable:
 233       vtn_assert(b->block && b->block->branch == NULL);
 234       b->block->branch = w;
 235       b->block = NULL;
 236       break;
 237
 238    default:
 239       /* Continue on as per normal */
 240       return true;
 241    }
 242
 243    return true;
 244 }
 245
 246 static void
 247 vtn_add_case(struct vtn_builder *b, struct vtn_switch *swtch,
 248              struct vtn_block *break_block,
 249              uint32_t block_id, uint64_t val, bool is_default)
 250 {
 251    struct vtn_block *case_block =
 252       vtn_value(b, block_id, vtn_value_type_block)->block;
 253
 254    /* Don't create dummy cases that just break */
 255    if (case_block == break_block)
 256       return;
 257
 258    if (case_block->switch_case == NULL) {
 259       struct vtn_case *c = ralloc(b, struct vtn_case);
 260
 261       list_inithead(&c->body);
 262       c->start_block = case_block;
 263       c->fallthrough = NULL;
 264       util_dynarray_init(&c->values, b);
 265       c->is_default = false;
 266       c->visited = false;
 267
 268       list_addtail(&c->link, &swtch->cases);
 269
 270       case_block->switch_case = c;
 271    }
 272
 273    if (is_default) {
 274       case_block->switch_case->is_default = true;
 275    } else {
 276       util_dynarray_append(&case_block->switch_case->values, uint64_t, val);
 277    }
 278 }
 279
 280 /* This function performs a depth-first search of the cases and puts them
 281  * in fall-through order.
 282  */
 283 static void
 284 vtn_order_case(struct vtn_switch *swtch, struct vtn_case *cse)
 285 {
 286    if (cse->visited)
 287       return;
 288
 289    cse->visited = true;
 290
 291    list_del(&cse->link);
 292
 293    if (cse->fallthrough) {
 294       vtn_order_case(swtch, cse->fallthrough);
 295
 296       /* If we have a fall-through, place this case right before the case it
 297        * falls through to.  This ensures that fallthroughs come one after
 298        * the other.  These two can never get separated because that would
 299        * imply something else falling through to the same case.  Also, this
 300        * can't break ordering because the DFS ensures that this case is
 301        * visited before anything that falls through to it.
 302        */
 303       list_addtail(&cse->link, &cse->fallthrough->link);
 304    } else {
 305       list_add(&cse->link, &swtch->cases);
 306    }
 307 }
 308
 309 static enum vtn_branch_type
 310 vtn_get_branch_type(struct vtn_builder *b,
 311                     struct vtn_block *block,
 312                     struct vtn_case *swcase, struct vtn_block *switch_break,
 313                     struct vtn_block *loop_break, struct vtn_block *loop_cont)
 314 {
 315    if (block->switch_case) {
 316       /* This branch is actually a fallthrough */
 317       vtn_assert(swcase->fallthrough == NULL ||
 318                  swcase->fallthrough == block->switch_case);
 319       swcase->fallthrough = block->switch_case;
 320       return vtn_branch_type_switch_fallthrough;
 321    } else if (block == loop_break) {
 322       return vtn_branch_type_loop_break;
 323    } else if (block == loop_cont) {
 324       return vtn_branch_type_loop_continue;
 325    } else if (block == switch_break) {
 326       return vtn_branch_type_switch_break;
 327    } else {
 328       return vtn_branch_type_none;
 329    }
 330 }
 331
 332 static void
 333 vtn_cfg_walk_blocks(struct vtn_builder *b, struct list_head *cf_list,
 334                     struct vtn_block *start, struct vtn_case *switch_case,
 335                     struct vtn_block *switch_break,
 336                     struct vtn_block *loop_break, struct vtn_block *loop_cont,
 337                     struct vtn_block *end)
 338 {
 339    struct vtn_block *block = start;
 340    while (block != end) {
 341       if (block->merge && (*block->merge & SpvOpCodeMask) == SpvOpLoopMerge &&
 342           !block->loop) {
 343          struct vtn_loop *loop = ralloc(b, struct vtn_loop);
 344
 345          loop->node.type = vtn_cf_node_type_loop;
 346          list_inithead(&loop->body);
 347          list_inithead(&loop->cont_body);
 348          loop->control = block->merge[3];
 349
 350          list_addtail(&loop->node.link, cf_list);
 351          block->loop = loop;
 352
 353          struct vtn_block *new_loop_break =
 354             vtn_value(b, block->merge[1], vtn_value_type_block)->block;
 355          struct vtn_block *new_loop_cont =
 356             vtn_value(b, block->merge[2], vtn_value_type_block)->block;
 357
 358          /* Note: This recursive call will start with the current block as
 359           * its start block.  If we weren't careful, we would get here
 360           * again and end up in infinite recursion.  This is why we set
 361           * block->loop above and check for it before creating one.  This
 362           * way, we only create the loop once and the second call that
 363           * tries to handle this loop goes to the cases below and gets
 364           * handled as a regular block.
 365           *
 366           * Note: When we make the recursive walk calls, we pass NULL for
 367           * the switch break since you have to break out of the loop first.
 368           * We do, however, still pass the current switch case because it's
 369           * possible that the merge block for the loop is the start of
 370           * another case.
 371           */
 372          vtn_cfg_walk_blocks(b, &loop->body, block, switch_case, NULL,
 373                              new_loop_break, new_loop_cont, NULL );
 374          vtn_cfg_walk_blocks(b, &loop->cont_body, new_loop_cont, NULL, NULL,
 375                              new_loop_break, NULL, block);
 376
 377          enum vtn_branch_type branch_type =
 378             vtn_get_branch_type(b, new_loop_break, switch_case, switch_break,
 379                                 loop_break, loop_cont);
 380
 381          if (branch_type != vtn_branch_type_none) {
 382             /* Stop walking through the CFG when this inner loop's break block
 383              * ends up as the same block as the outer loop's continue block
 384              * because we are already going to visit it.
 385              */
 386             vtn_assert(branch_type == vtn_branch_type_loop_continue);
 387             return;
 388          }
 389
 390          block = new_loop_break;
 391          continue;
 392       }
 393
 394       vtn_assert(block->node.link.next == NULL);
 395       list_addtail(&block->node.link, cf_list);
 396
 397       switch (*block->branch & SpvOpCodeMask) {
 398       case SpvOpBranch: {
 399          struct vtn_block *branch_block =
 400             vtn_value(b, block->branch[1], vtn_value_type_block)->block;
 401
 402          block->branch_type = vtn_get_branch_type(b, branch_block,
 403                                                   switch_case, switch_break,
 404                                                   loop_break, loop_cont);
 405
 406          if (block->branch_type != vtn_branch_type_none)
 407             return;
 408
 409          block = branch_block;
 410          continue;
 411       }
 412
 413       case SpvOpReturn:
 414       case SpvOpReturnValue:
 415          block->branch_type = vtn_branch_type_return;
 416          return;
 417
 418       case SpvOpKill:
 419          block->branch_type = vtn_branch_type_discard;
 420          return;
 421
 422       case SpvOpBranchConditional: {
 423          struct vtn_block *then_block =
 424             vtn_value(b, block->branch[2], vtn_value_type_block)->block;
 425          struct vtn_block *else_block =
 426             vtn_value(b, block->branch[3], vtn_value_type_block)->block;
 427
 428          struct vtn_if *if_stmt = ralloc(b, struct vtn_if);
 429
 430          if_stmt->node.type = vtn_cf_node_type_if;
 431          if_stmt->condition = block->branch[1];
 432          list_inithead(&if_stmt->then_body);
 433          list_inithead(&if_stmt->else_body);
 434
 435          list_addtail(&if_stmt->node.link, cf_list);
 436
 437          if (block->merge &&
 438              (*block->merge & SpvOpCodeMask) == SpvOpSelectionMerge) {
 439             if_stmt->control = block->merge[2];
 440          }
 441
 442          if_stmt->then_type = vtn_get_branch_type(b, then_block,
 443                                                   switch_case, switch_break,
 444                                                   loop_break, loop_cont);
 445          if_stmt->else_type = vtn_get_branch_type(b, else_block,
 446                                                   switch_case, switch_break,
 447                                                   loop_break, loop_cont);
 448
 449          if (then_block == else_block) {
 450             block->branch_type = if_stmt->then_type;
 451             if (block->branch_type == vtn_branch_type_none) {
 452                block = then_block;
 453                continue;
 454             } else {
 455                return;
 456             }
 457          } else if (if_stmt->then_type == vtn_branch_type_none &&
 458                     if_stmt->else_type == vtn_branch_type_none) {
 459             /* Neither side of the if is something we can short-circuit. */
 460             vtn_assert((*block->merge & SpvOpCodeMask) == SpvOpSelectionMerge);
 461             struct vtn_block *merge_block =
 462                vtn_value(b, block->merge[1], vtn_value_type_block)->block;
 463
 464             vtn_cfg_walk_blocks(b, &if_stmt->then_body, then_block,
 465                                 switch_case, switch_break,
 466                                 loop_break, loop_cont, merge_block);
 467             vtn_cfg_walk_blocks(b, &if_stmt->else_body, else_block,
 468                                 switch_case, switch_break,
 469                                 loop_break, loop_cont, merge_block);
 470
 471             enum vtn_branch_type merge_type =
 472                vtn_get_branch_type(b, merge_block, switch_case, switch_break,
 473                                    loop_break, loop_cont);
 474             if (merge_type == vtn_branch_type_none) {
 475                block = merge_block;
 476                continue;
 477             } else {
 478                return;
 479             }
 480          } else if (if_stmt->then_type != vtn_branch_type_none &&
 481                     if_stmt->else_type != vtn_branch_type_none) {
 482             /* Both sides were short-circuited.  We're done here. */
 483             return;
 484          } else {
 485             /* Exeactly one side of the branch could be short-circuited.
 486              * We set the branch up as a predicated break/continue and we
 487              * continue on with the other side as if it were what comes
 488              * after the if.
 489              */
 490             if (if_stmt->then_type == vtn_branch_type_none) {
 491                block = then_block;
 492             } else {
 493                block = else_block;
 494             }
 495             continue;
 496          }
 497          vtn_fail("Should have returned or continued");
 498       }
 499
 500       case SpvOpSwitch: {
 501          vtn_assert((*block->merge & SpvOpCodeMask) == SpvOpSelectionMerge);
 502          struct vtn_block *break_block =
 503             vtn_value(b, block->merge[1], vtn_value_type_block)->block;
 504
 505          struct vtn_switch *swtch = ralloc(b, struct vtn_switch);
 506
 507          swtch->node.type = vtn_cf_node_type_switch;
 508          swtch->selector = block->branch[1];
 509          list_inithead(&swtch->cases);
 510
 511          list_addtail(&swtch->node.link, cf_list);
 512
 513          /* First, we go through and record all of the cases. */
 514          const uint32_t *branch_end =
 515             block->branch + (block->branch[0] >> SpvWordCountShift);
 516
 517          struct vtn_value *cond_val = vtn_untyped_value(b, block->branch[1]);
 518          vtn_fail_if(!cond_val->type ||
 519                      cond_val->type->base_type != vtn_base_type_scalar,
 520                      "Selector of OpSelect must have a type of OpTypeInt");
 521
 522          nir_alu_type cond_type =
 523             nir_get_nir_type_for_glsl_type(cond_val->type->type);
 524          vtn_fail_if(nir_alu_type_get_base_type(cond_type) != nir_type_int &&
 525                      nir_alu_type_get_base_type(cond_type) != nir_type_uint,
 526                      "Selector of OpSelect must have a type of OpTypeInt");
 527
 528          bool is_default = true;
 529          const unsigned bitsize = nir_alu_type_get_type_size(cond_type);
 530          for (const uint32_t *w = block->branch + 2; w < branch_end;) {
 531             uint64_t literal = 0;
 532             if (!is_default) {
 533                if (bitsize <= 32) {
 534                   literal = *(w++);
 535                } else {
 536                   assert(bitsize == 64);
 537                   literal = vtn_u64_literal(w);
 538                   w += 2;
 539                }
 540             }
 541
 542             uint32_t block_id = *(w++);
 543
 544             vtn_add_case(b, swtch, break_block, block_id, literal, is_default);
 545             is_default = false;
 546          }
 547
 548          /* Now, we go through and walk the blocks.  While we walk through
 549           * the blocks, we also gather the much-needed fall-through
 550           * information.
 551           */
 552          list_for_each_entry(struct vtn_case, cse, &swtch->cases, link) {
 553             vtn_assert(cse->start_block != break_block);
 554             vtn_cfg_walk_blocks(b, &cse->body, cse->start_block, cse,
 555                                 break_block, loop_break, loop_cont, NULL);
 556          }
 557
 558          /* Finally, we walk over all of the cases one more time and put
 559           * them in fall-through order.
 560           */
 561          for (const uint32_t *w = block->branch + 2; w < branch_end;) {
 562             struct vtn_block *case_block =
 563                vtn_value(b, *w, vtn_value_type_block)->block;
 564
 565             if (bitsize <= 32) {
 566                w += 2;
 567             } else {
 568                assert(bitsize == 64);
 569                w += 3;
 570             }
 571
 572             if (case_block == break_block)
 573                continue;
 574
 575             vtn_assert(case_block->switch_case);
 576
 577             vtn_order_case(swtch, case_block->switch_case);
 578          }
 579
 580          enum vtn_branch_type branch_type =
 581             vtn_get_branch_type(b, break_block, switch_case, NULL,
 582                                 loop_break, loop_cont);
 583
 584          if (branch_type != vtn_branch_type_none) {
 585             /* It is possible that the break is actually the continue block
 586              * for the containing loop.  In this case, we need to bail and let
 587              * the loop parsing code handle the continue properly.
 588              */
 589             vtn_assert(branch_type == vtn_branch_type_loop_continue);
 590             return;
 591          }
 592
 593          block = break_block;
 594          continue;
 595       }
 596
 597       case SpvOpUnreachable:
 598          return;
 599
 600       default:
 601          vtn_fail("Unhandled opcode");
 602       }
 603    }
 604 }
 605
 606 void
 607 vtn_build_cfg(struct vtn_builder *b, const uint32_t *words, const uint32_t *end)
 608 {
 609    vtn_foreach_instruction(b, words, end,
 610                            vtn_cfg_handle_prepass_instruction);
 611
 612    foreach_list_typed(struct vtn_function, func, node, &b->functions) {
 613       vtn_cfg_walk_blocks(b, &func->body, func->start_block,
 614                           NULL, NULL, NULL, NULL, NULL);
 615    }
 616 }
 617
 618 static bool
 619 vtn_handle_phis_first_pass(struct vtn_builder *b, SpvOp opcode,
 620                            const uint32_t *w, unsigned count)
 621 {
 622    if (opcode == SpvOpLabel)
 623       return true; /* Nothing to do */
 624
 625    /* If this isn't a phi node, stop. */
 626    if (opcode != SpvOpPhi)
 627       return false;
 628
 629    /* For handling phi nodes, we do a poor-man's out-of-ssa on the spot.
 630     * For each phi, we create a variable with the appropreate type and
 631     * do a load from that variable.  Then, in a second pass, we add
 632     * stores to that variable to each of the predecessor blocks.
 633     *
 634     * We could do something more intelligent here.  However, in order to
 635     * handle loops and things properly, we really need dominance
 636     * information.  It would end up basically being the into-SSA
 637     * algorithm all over again.  It's easier if we just let
 638     * lower_vars_to_ssa do that for us instead of repeating it here.
 639     */
 640    struct vtn_type *type = vtn_value(b, w[1], vtn_value_type_type)->type;
 641    nir_variable *phi_var =
 642       nir_local_variable_create(b->nb.impl, type->type, "phi");
 643    _mesa_hash_table_insert(b->phi_table, w, phi_var);
 644
 645    vtn_push_ssa(b, w[2], type,
 646                 vtn_local_load(b, nir_deref_var_create(b, phi_var)));
 647
 648    return true;
 649 }
 650
 651 static bool
 652 vtn_handle_phi_second_pass(struct vtn_builder *b, SpvOp opcode,
 653                            const uint32_t *w, unsigned count)
 654 {
 655    if (opcode != SpvOpPhi)
 656       return true;
 657
 658    struct hash_entry *phi_entry = _mesa_hash_table_search(b->phi_table, w);
 659    vtn_assert(phi_entry);
 660    nir_variable *phi_var = phi_entry->data;
 661
 662    for (unsigned i = 3; i < count; i += 2) {
 663       struct vtn_block *pred =
 664          vtn_value(b, w[i + 1], vtn_value_type_block)->block;
 665
 666       b->nb.cursor = nir_after_instr(&pred->end_nop->instr);
 667
 668       struct vtn_ssa_value *src = vtn_ssa_value(b, w[i]);
 669
 670       vtn_local_store(b, src, nir_deref_var_create(b, phi_var));
 671    }
 672
 673    return true;
 674 }
 675
 676 static void
 677 vtn_emit_branch(struct vtn_builder *b, enum vtn_branch_type branch_type,
 678                 nir_variable *switch_fall_var, bool *has_switch_break)
 679 {
 680    switch (branch_type) {
 681    case vtn_branch_type_switch_break:
 682       nir_store_var(&b->nb, switch_fall_var, nir_imm_int(&b->nb, NIR_FALSE), 1);
 683       *has_switch_break = true;
 684       break;
 685    case vtn_branch_type_switch_fallthrough:
 686       break; /* Nothing to do */
 687    case vtn_branch_type_loop_break:
 688       nir_jump(&b->nb, nir_jump_break);
 689       break;
 690    case vtn_branch_type_loop_continue:
 691       nir_jump(&b->nb, nir_jump_continue);
 692       break;
 693    case vtn_branch_type_return:
 694       nir_jump(&b->nb, nir_jump_return);
 695       break;
 696    case vtn_branch_type_discard: {
 697       nir_intrinsic_instr *discard =
 698          nir_intrinsic_instr_create(b->nb.shader, nir_intrinsic_discard);
 699       nir_builder_instr_insert(&b->nb, &discard->instr);
 700       break;
 701    }
 702    default:
 703       vtn_fail("Invalid branch type");
 704    }
 705 }
 706
 707 static void
 708 vtn_emit_cf_list(struct vtn_builder *b, struct list_head *cf_list,
 709                  nir_variable *switch_fall_var, bool *has_switch_break,
 710                  vtn_instruction_handler handler)
 711 {
 712    list_for_each_entry(struct vtn_cf_node, node, cf_list, link) {
 713       switch (node->type) {
 714       case vtn_cf_node_type_block: {
 715          struct vtn_block *block = (struct vtn_block *)node;
 716
 717          const uint32_t *block_start = block->label;
 718          const uint32_t *block_end = block->merge ? block->merge :
 719                                                     block->branch;
 720
 721          block_start = vtn_foreach_instruction(b, block_start, block_end,
 722                                                vtn_handle_phis_first_pass);
 723
 724          vtn_foreach_instruction(b, block_start, block_end, handler);
 725
 726          block->end_nop = nir_intrinsic_instr_create(b->nb.shader,
 727                                                      nir_intrinsic_nop);
 728          nir_builder_instr_insert(&b->nb, &block->end_nop->instr);
 729
 730          if ((*block->branch & SpvOpCodeMask) == SpvOpReturnValue) {
 731             struct vtn_ssa_value *src = vtn_ssa_value(b, block->branch[1]);
 732             vtn_local_store(b, src,
 733                             nir_deref_var_create(b, b->nb.impl->return_var));
 734          }
 735
 736          if (block->branch_type != vtn_branch_type_none) {
 737             vtn_emit_branch(b, block->branch_type,
 738                             switch_fall_var, has_switch_break);
 739          }
 740
 741          break;
 742       }
 743
 744       case vtn_cf_node_type_if: {
 745          struct vtn_if *vtn_if = (struct vtn_if *)node;
 746          bool sw_break = false;
 747
 748          nir_if *nif =
 749             nir_push_if(&b->nb, vtn_ssa_value(b, vtn_if->condition)->def);
 750          if (vtn_if->then_type == vtn_branch_type_none) {
 751             vtn_emit_cf_list(b, &vtn_if->then_body,
 752                              switch_fall_var, &sw_break, handler);
 753          } else {
 754             vtn_emit_branch(b, vtn_if->then_type, switch_fall_var, &sw_break);
 755          }
 756
 757          nir_push_else(&b->nb, nif);
 758          if (vtn_if->else_type == vtn_branch_type_none) {
 759             vtn_emit_cf_list(b, &vtn_if->else_body,
 760                              switch_fall_var, &sw_break, handler);
 761          } else {
 762             vtn_emit_branch(b, vtn_if->else_type, switch_fall_var, &sw_break);
 763          }
 764
 765          nir_pop_if(&b->nb, nif);
 766
 767          /* If we encountered a switch break somewhere inside of the if,
 768           * then it would have been handled correctly by calling
 769           * emit_cf_list or emit_branch for the interrior.  However, we
 770           * need to predicate everything following on wether or not we're
 771           * still going.
 772           */
 773          if (sw_break) {
 774             *has_switch_break = true;
 775             nir_push_if(&b->nb, nir_load_var(&b->nb, switch_fall_var));
 776          }
 777          break;
 778       }
 779
 780       case vtn_cf_node_type_loop: {
 781          struct vtn_loop *vtn_loop = (struct vtn_loop *)node;
 782
 783          nir_loop *loop = nir_push_loop(&b->nb);
 784          vtn_emit_cf_list(b, &vtn_loop->body, NULL, NULL, handler);
 785
 786          if (!list_empty(&vtn_loop->cont_body)) {
 787             /* If we have a non-trivial continue body then we need to put
 788              * it at the beginning of the loop with a flag to ensure that
 789              * it doesn't get executed in the first iteration.
 790              */
 791             nir_variable *do_cont =
 792                nir_local_variable_create(b->nb.impl, glsl_bool_type(), "cont");
 793
 794             b->nb.cursor = nir_before_cf_node(&loop->cf_node);
 795             nir_store_var(&b->nb, do_cont, nir_imm_int(&b->nb, NIR_FALSE), 1);
 796
 797             b->nb.cursor = nir_before_cf_list(&loop->body);
 798
 799             nir_if *cont_if =
 800                nir_push_if(&b->nb, nir_load_var(&b->nb, do_cont));
 801
 802             vtn_emit_cf_list(b, &vtn_loop->cont_body, NULL, NULL, handler);
 803
 804             nir_pop_if(&b->nb, cont_if);
 805
 806             nir_store_var(&b->nb, do_cont, nir_imm_int(&b->nb, NIR_TRUE), 1);
 807
 808             b->has_loop_continue = true;
 809          }
 810
 811          nir_pop_loop(&b->nb, loop);
 812          break;
 813       }
 814
 815       case vtn_cf_node_type_switch: {
 816          struct vtn_switch *vtn_switch = (struct vtn_switch *)node;
 817
 818          /* First, we create a variable to keep track of whether or not the
 819           * switch is still going at any given point.  Any switch breaks
 820           * will set this variable to false.
 821           */
 822          nir_variable *fall_var =
 823             nir_local_variable_create(b->nb.impl, glsl_bool_type(), "fall");
 824          nir_store_var(&b->nb, fall_var, nir_imm_int(&b->nb, NIR_FALSE), 1);
 825
 826          /* Next, we gather up all of the conditions.  We have to do this
 827           * up-front because we also need to build an "any" condition so
 828           * that we can use !any for default.
 829           */
 830          const int num_cases = list_length(&vtn_switch->cases);
 831          NIR_VLA(nir_ssa_def *, conditions, num_cases);
 832
 833          nir_ssa_def *sel = vtn_ssa_value(b, vtn_switch->selector)->def;
 834          /* An accumulation of all conditions.  Used for the default */
 835          nir_ssa_def *any = NULL;
 836
 837          int i = 0;
 838          list_for_each_entry(struct vtn_case, cse, &vtn_switch->cases, link) {
 839             if (cse->is_default) {
 840                conditions[i++] = NULL;
 841                continue;
 842             }
 843
 844             nir_ssa_def *cond = NULL;
 845             util_dynarray_foreach(&cse->values, uint64_t, val) {
 846                nir_ssa_def *imm = nir_imm_intN_t(&b->nb, *val, sel->bit_size);
 847                nir_ssa_def *is_val = nir_ieq(&b->nb, sel, imm);
 848
 849                cond = cond ? nir_ior(&b->nb, cond, is_val) : is_val;
 850             }
 851
 852             any = any ? nir_ior(&b->nb, any, cond) : cond;
 853             conditions[i++] = cond;
 854          }
 855          vtn_assert(i == num_cases);
 856
 857          /* Now we can walk the list of cases and actually emit code */
 858          i = 0;
 859          list_for_each_entry(struct vtn_case, cse, &vtn_switch->cases, link) {
 860             /* Figure out the condition */
 861             nir_ssa_def *cond = conditions[i++];
 862             if (cse->is_default) {
 863                vtn_assert(cond == NULL);
 864                cond = nir_inot(&b->nb, any);
 865             }
 866             /* Take fallthrough into account */
 867             cond = nir_ior(&b->nb, cond, nir_load_var(&b->nb, fall_var));
 868
 869             nir_if *case_if = nir_push_if(&b->nb, cond);
 870
 871             bool has_break = false;
 872             nir_store_var(&b->nb, fall_var, nir_imm_int(&b->nb, NIR_TRUE), 1);
 873             vtn_emit_cf_list(b, &cse->body, fall_var, &has_break, handler);
 874             (void)has_break; /* We don't care */
 875
 876             nir_pop_if(&b->nb, case_if);
 877          }
 878          vtn_assert(i == num_cases);
 879
 880          break;
 881       }
 882
 883       default:
 884          vtn_fail("Invalid CF node type");
 885       }
 886    }
 887 }
 888
 889 void
 890 vtn_function_emit(struct vtn_builder *b, struct vtn_function *func,
 891                   vtn_instruction_handler instruction_handler)
 892 {
 893    nir_builder_init(&b->nb, func->impl);
 894    b->nb.cursor = nir_after_cf_list(&func->impl->body);
 895    b->has_loop_continue = false;
 896    b->phi_table = _mesa_hash_table_create(b, _mesa_hash_pointer,
 897                                           _mesa_key_pointer_equal);
 898
 899    vtn_emit_cf_list(b, &func->body, NULL, NULL, instruction_handler);
 900
 901    vtn_foreach_instruction(b, func->start_block->label, func->end,
 902                            vtn_handle_phi_second_pass);
 903
 904    /* Continue blocks for loops get inserted before the body of the loop
 905     * but instructions in the continue may use SSA defs in the loop body.
 906     * Therefore, we need to repair SSA to insert the needed phi nodes.
 907     */
 908    if (b->has_loop_continue)
 909       nir_repair_ssa_impl(func->impl);
 910
 911    func->emitted = true;
 912 }