Home | History | Annotate | Download | only in nir 
      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 (at) 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-zero 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(nir_block *block, struct exec_list *worklist)
    117 {
    118    nir_foreach_instr(instr, block)
    119       init_instr(instr, worklist);
    120 
    121    nir_if *following_if = nir_block_get_following_if(block);
    122    if (following_if) {
    123       if (following_if->condition.is_ssa &&
    124           !following_if->condition.ssa->parent_instr->pass_flags)
    125          worklist_push(worklist, following_if->condition.ssa->parent_instr);
    126    }
    127 
    128    return true;
    129 }
    130 
    131 static bool
    132 nir_opt_dce_impl(nir_function_impl *impl)
    133 {
    134    struct exec_list *worklist = rzalloc(NULL, struct exec_list);
    135    exec_list_make_empty(worklist);
    136 
    137    nir_foreach_block(block, impl) {
    138       init_block(block, worklist);
    139    }
    140 
    141    while (!exec_list_is_empty(worklist)) {
    142       nir_instr *instr = worklist_pop(worklist);
    143       nir_foreach_src(instr, mark_live_cb, worklist);
    144    }
    145 
    146    ralloc_free(worklist);
    147 
    148    bool progress = false;
    149 
    150    nir_foreach_block(block, impl) {
    151       nir_foreach_instr_safe(instr, block) {
    152          if (!instr->pass_flags) {
    153             nir_instr_remove(instr);
    154             progress = true;
    155          }
    156       }
    157    }
    158 
    159    if (progress)
    160       nir_metadata_preserve(impl, nir_metadata_block_index |
    161                                   nir_metadata_dominance);
    162 
    163    return progress;
    164 }
    165 
    166 bool
    167 nir_opt_dce(nir_shader *shader)
    168 {
    169    bool progress = false;
    170    nir_foreach_function(function, shader) {
    171       if (function->impl && nir_opt_dce_impl(function->impl))
    172          progress = true;
    173    }
    174 
    175    return progress;
    176 }
    177