/*
 * Copyright © 2014 Intel Corporation
 *
 * Permission is hereby granted, free of charge, to any person obtaining a
 * copy of this software and associated documentation files (the "Software"),
 * to deal in the Software without restriction, including without limitation
 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
 * and/or sell copies of the Software, and to permit persons to whom the
 * Software is furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice (including the next
 * paragraph) shall be included in all copies or substantial portions of the
 * Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
 * IN THE SOFTWARE.
 *
 * Authors:
 *    Connor Abbott (cwabbott0@gmail.com)
 *
 */

#include "nir.h"

static bool
is_def_live(const nir_def *def, BITSET_WORD *defs_live)
{
   return BITSET_TEST(defs_live, def->index);
}

static bool
mark_src_live(const nir_src *src, BITSET_WORD *defs_live)
{
   if (!BITSET_TEST(defs_live, src->ssa->index)) {
      BITSET_SET(defs_live, src->ssa->index);
      return true;
   } else {
      return false;
   }
}

static bool
mark_live_cb(nir_src *src, void *defs_live)
{
   mark_src_live(src, defs_live);
   return true;
}

static bool
is_live(BITSET_WORD *defs_live, nir_instr *instr)
{
   switch (instr->type) {
   case nir_instr_type_call:
   case nir_instr_type_jump:
      return true;
   case nir_instr_type_alu: {
      nir_alu_instr *alu = nir_instr_as_alu(instr);
      return is_def_live(&alu->def, defs_live);
   }
   case nir_instr_type_deref: {
      nir_deref_instr *deref = nir_instr_as_deref(instr);
      return is_def_live(&deref->def, defs_live);
   }
   case nir_instr_type_intrinsic: {
      nir_intrinsic_instr *intrin = nir_instr_as_intrinsic(instr);
      const nir_intrinsic_info *info = &nir_intrinsic_infos[intrin->intrinsic];
      return !(info->flags & NIR_INTRINSIC_CAN_ELIMINATE) ||
             (info->has_dest && is_def_live(&intrin->def, defs_live));
   }
   case nir_instr_type_tex: {
      nir_tex_instr *tex = nir_instr_as_tex(instr);
      return is_def_live(&tex->def, defs_live);
   }
   case nir_instr_type_phi: {
      nir_phi_instr *phi = nir_instr_as_phi(instr);
      return is_def_live(&phi->def, defs_live);
   }
   case nir_instr_type_load_const: {
      nir_load_const_instr *lc = nir_instr_as_load_const(instr);
      return is_def_live(&lc->def, defs_live);
   }
   case nir_instr_type_undef: {
      nir_undef_instr *undef = nir_instr_as_undef(instr);
      return is_def_live(&undef->def, defs_live);
   }
   case nir_instr_type_parallel_copy: {
      nir_parallel_copy_instr *pc = nir_instr_as_parallel_copy(instr);
      nir_foreach_parallel_copy_entry(entry, pc) {
         if (entry->dest_is_reg || is_def_live(&entry->dest.def, defs_live))
            return true;
      }
      return false;
   }
   case nir_instr_type_debug_info: {
      nir_debug_info_instr *di = nir_instr_as_debug_info(instr);
      if (di->type == nir_debug_info_src_loc) {
         nir_instr *next = nir_instr_next(instr);
         return !next || next->type != nir_instr_type_debug_info;
      } else if (di->type == nir_debug_info_string) {
         return is_def_live(&di->def, defs_live);
      }
      return true;
   }
   default:
      unreachable("unexpected instr type");
   }
}

struct loop_state {
   bool header_phis_changed;
   nir_block *preheader;
};

static bool
dce_block(nir_block *block, BITSET_WORD *defs_live, struct loop_state *loop,
          struct exec_list *dead_instrs)
{
   bool progress = false;
   bool phis_changed = false;
   nir_foreach_instr_reverse_safe(instr, block) {
      bool live = is_live(defs_live, instr);
      if (live) {
         if (instr->type == nir_instr_type_phi) {
            nir_foreach_phi_src(src, nir_instr_as_phi(instr)) {
               phis_changed |= mark_src_live(&src->src, defs_live) &&
                               src->pred != loop->preheader;
            }
         } else {
            nir_foreach_src(instr, mark_live_cb, defs_live);
         }
      }

      /* If we're not in a loop, remove it now if it's dead. If we are in a
       * loop, leave instructions to be removed later if they're still dead.
       */
      if (loop->preheader) {
         instr->pass_flags = live;
      } else if (!live) {
         nir_instr_remove(instr);
         exec_list_push_tail(dead_instrs, &instr->node);
         progress = true;
      }
   }

   /* Because blocks are visited in reverse and this stomps header_phis_changed,
    * we don't have to check whether the current block is a loop header before
    * setting header_phis_changed.
    */
   loop->header_phis_changed = phis_changed;

   return progress;
}

static bool
dce_cf_list(struct exec_list *cf_list, BITSET_WORD *defs_live,
            struct loop_state *parent_loop, struct exec_list *dead_instrs)
{
   bool progress = false;
   foreach_list_typed_reverse(nir_cf_node, cf_node, node, cf_list) {
      switch (cf_node->type) {
      case nir_cf_node_block: {
         nir_block *block = nir_cf_node_as_block(cf_node);
         progress |= dce_block(block, defs_live, parent_loop, dead_instrs);
         break;
      }
      case nir_cf_node_if: {
         nir_if *nif = nir_cf_node_as_if(cf_node);
         progress |= dce_cf_list(&nif->else_list, defs_live, parent_loop, dead_instrs);
         progress |= dce_cf_list(&nif->then_list, defs_live, parent_loop, dead_instrs);
         mark_src_live(&nif->condition, defs_live);
         break;
      }
      case nir_cf_node_loop: {
         nir_loop *loop = nir_cf_node_as_loop(cf_node);
         assert(!nir_loop_has_continue_construct(loop));

         struct loop_state inner_state;
         inner_state.preheader = nir_cf_node_as_block(nir_cf_node_prev(cf_node));
         inner_state.header_phis_changed = false;

         /* Fast path if the loop has no continues: we can remove instructions
          * as we mark the others live.
          */
         struct set *predecessors = nir_loop_first_block(loop)->predecessors;
         if (predecessors->entries == 1 &&
             _mesa_set_next_entry(predecessors, NULL)->key == inner_state.preheader) {
            progress |= dce_cf_list(&loop->body, defs_live, parent_loop, dead_instrs);
            break;
         }

         /* Mark instructions as live until there is no more progress. */
         do {
            /* dce_cf_list() resets inner_state.header_phis_changed itself, so
             * it doesn't have to be done here.
             */
            dce_cf_list(&loop->body, defs_live, &inner_state, dead_instrs);
         } while (inner_state.header_phis_changed);

         /* We don't know how many times mark_cf_list() will repeat, so
          * remove instructions separately.
          *
          * By checking parent_loop->preheader, we ensure that we only do this
          * walk for the outer-most loops so it only happens once.
          */
         if (!parent_loop->preheader) {
            nir_foreach_block_in_cf_node(block, cf_node) {
               nir_foreach_instr_safe(instr, block) {
                  if (!instr->pass_flags) {
                     nir_instr_remove(instr);
                     exec_list_push_tail(dead_instrs, &instr->node);
                     progress = true;
                  }
               }
            }
         }
         break;
      }
      case nir_cf_node_function:
         unreachable("Invalid cf type");
      }
   }

   return progress;
}

static bool
nir_opt_dce_impl(nir_function_impl *impl)
{
   assert(impl->structured);

   BITSET_WORD *defs_live = rzalloc_array(NULL, BITSET_WORD,
                                          BITSET_WORDS(impl->ssa_alloc));

   struct exec_list dead_instrs;
   exec_list_make_empty(&dead_instrs);

   struct loop_state loop;
   loop.preheader = NULL;
   bool progress = dce_cf_list(&impl->body, defs_live, &loop, &dead_instrs);

   ralloc_free(defs_live);

   nir_instr_free_list(&dead_instrs);

   if (progress) {
      nir_metadata_preserve(impl, nir_metadata_control_flow);
   } else {
      nir_metadata_preserve(impl, nir_metadata_all);
   }

   return progress;
}

bool
nir_opt_dce(nir_shader *shader)
{
   bool progress = false;
   nir_foreach_function_impl(impl, shader) {
      if (nir_opt_dce_impl(impl))
         progress = true;
   }

   return progress;
}