Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | RSS feed

  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.  
  30. /* SSA-based mark-and-sweep dead code elimination */
  31.  
  32. typedef struct {
  33.    struct exec_node node;
  34.    nir_instr *instr;
  35. } worklist_elem;
  36.  
  37. static void
  38. worklist_push(struct exec_list *worklist, nir_instr *instr)
  39. {
  40.    worklist_elem *elem = ralloc(worklist, worklist_elem);
  41.    elem->instr = instr;
  42.    instr->pass_flags = 1;
  43.    exec_list_push_tail(worklist, &elem->node);
  44. }
  45.  
  46. static nir_instr *
  47. worklist_pop(struct exec_list *worklist)
  48. {
  49.    struct exec_node *node = exec_list_pop_head(worklist);
  50.    worklist_elem *elem = exec_node_data(worklist_elem, node, node);
  51.    return elem->instr;
  52. }
  53.  
  54. static bool
  55. mark_live_cb(nir_src *src, void *_state)
  56. {
  57.    struct exec_list *worklist = (struct exec_list *) _state;
  58.  
  59.    if (src->is_ssa && !src->ssa->parent_instr->pass_flags) {
  60.       worklist_push(worklist, src->ssa->parent_instr);
  61.    }
  62.  
  63.    return true;
  64. }
  65.  
  66. static void
  67. init_instr(nir_instr *instr, struct exec_list *worklist)
  68. {
  69.    nir_alu_instr *alu_instr;
  70.    nir_intrinsic_instr *intrin_instr;
  71.    nir_tex_instr *tex_instr;
  72.  
  73.    /* We use the pass_flags to store the live/dead information.  In DCE, we
  74.     * just treat it as a zero/non-zerl boolean for whether or not the
  75.     * instruction is live.
  76.     */
  77.    instr->pass_flags = 0;
  78.  
  79.    switch (instr->type) {
  80.    case nir_instr_type_call:
  81.    case nir_instr_type_jump:
  82.       worklist_push(worklist, instr);
  83.       break;
  84.  
  85.    case nir_instr_type_alu:
  86.       alu_instr = nir_instr_as_alu(instr);
  87.       if (!alu_instr->dest.dest.is_ssa)
  88.          worklist_push(worklist, instr);
  89.       break;
  90.  
  91.    case nir_instr_type_intrinsic:
  92.       intrin_instr = nir_instr_as_intrinsic(instr);
  93.       if (nir_intrinsic_infos[intrin_instr->intrinsic].flags &
  94.           NIR_INTRINSIC_CAN_ELIMINATE) {
  95.          if (nir_intrinsic_infos[intrin_instr->intrinsic].has_dest &&
  96.              !intrin_instr->dest.is_ssa) {
  97.             worklist_push(worklist, instr);
  98.          }
  99.       } else {
  100.          worklist_push(worklist, instr);
  101.       }
  102.       break;
  103.  
  104.    case nir_instr_type_tex:
  105.       tex_instr = nir_instr_as_tex(instr);
  106.       if (!tex_instr->dest.is_ssa)
  107.          worklist_push(worklist, instr);
  108.       break;
  109.  
  110.    default:
  111.       break;
  112.    }
  113. }
  114.  
  115. static bool
  116. init_block_cb(nir_block *block, void *_state)
  117. {
  118.    struct exec_list *worklist = (struct exec_list *) _state;
  119.  
  120.    nir_foreach_instr(block, instr)
  121.       init_instr(instr, worklist);
  122.  
  123.    nir_if *following_if = nir_block_get_following_if(block);
  124.    if (following_if) {
  125.       if (following_if->condition.is_ssa &&
  126.           !following_if->condition.ssa->parent_instr->pass_flags)
  127.          worklist_push(worklist, following_if->condition.ssa->parent_instr);
  128.    }
  129.  
  130.    return true;
  131. }
  132.  
  133. static bool
  134. delete_block_cb(nir_block *block, void *_state)
  135. {
  136.    bool *progress = (bool *) _state;
  137.  
  138.    nir_foreach_instr_safe(block, instr) {
  139.       if (!instr->pass_flags) {
  140.          nir_instr_remove(instr);
  141.          *progress = true;
  142.       }
  143.    }
  144.  
  145.    return true;
  146. }
  147.  
  148. bool
  149. nir_opt_dce_impl(nir_function_impl *impl)
  150. {
  151.    struct exec_list *worklist = ralloc(NULL, struct exec_list);
  152.    exec_list_make_empty(worklist);
  153.  
  154.    nir_foreach_block(impl, init_block_cb, worklist);
  155.  
  156.    while (!exec_list_is_empty(worklist)) {
  157.       nir_instr *instr = worklist_pop(worklist);
  158.       nir_foreach_src(instr, mark_live_cb, worklist);
  159.    }
  160.  
  161.    ralloc_free(worklist);
  162.  
  163.    bool progress = false;
  164.    nir_foreach_block(impl, delete_block_cb, &progress);
  165.  
  166.    if (progress)
  167.       nir_metadata_preserve(impl, nir_metadata_block_index |
  168.                                   nir_metadata_dominance);
  169.  
  170.    return progress;
  171. }
  172.  
  173. bool
  174. nir_opt_dce(nir_shader *shader)
  175. {
  176.    bool progress = false;
  177.    nir_foreach_overload(shader, overload) {
  178.       if (overload->impl && nir_opt_dce_impl(overload->impl))
  179.          progress = true;
  180.    }
  181.  
  182.    return progress;
  183. }
  184.