Subversion Repositories openrisc_me

/* RTL dead code elimination.

   Copyright (C) 2005, 2006, 2007, 2008, 2009 Free Software Foundation, Inc.

This file is part of GCC.

GCC is free software; you can redistribute it and/or modify it under

the terms of the GNU General Public License as published by the Free

Software Foundation; either version 3, or (at your option) any later

version.

GCC is distributed in the hope that it will be useful, but WITHOUT ANY

WARRANTY; without even the implied warranty of MERCHANTABILITY or

FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

for more details.

You should have received a copy of the GNU General Public License

along with GCC; see the file COPYING3.  If not see

<http://www.gnu.org/licenses/>.  */

#include "config.h"

#include "system.h"

#include "coretypes.h"

#include "hashtab.h"

#include "tm.h"

#include "rtl.h"

#include "tree.h"

#include "regs.h"

#include "hard-reg-set.h"

#include "flags.h"

#include "except.h"

#include "df.h"

#include "cselib.h"

#include "dce.h"

#include "timevar.h"

#include "tree-pass.h"

#include "dbgcnt.h"

#include "tm_p.h"

/* -------------------------------------------------------------------------

   Core mark/delete routines

   ------------------------------------------------------------------------- */

/* True if we are invoked while the df engine is running; in this case,

   we don't want to reenter it.  */

static bool df_in_progress = false;

/* Instructions that have been marked but whose dependencies have not

   yet been processed.  */

static VEC(rtx,heap) *worklist;

/* Bitmap of instructions marked as needed indexed by INSN_UID.  */

static sbitmap marked;

/* Bitmap obstacks used for block processing by the fast algorithm.  */

static bitmap_obstack dce_blocks_bitmap_obstack;

static bitmap_obstack dce_tmp_bitmap_obstack;

static bool find_call_stack_args (rtx, bool, bool, bitmap);

/* A subroutine for which BODY is part of the instruction being tested;

   either the top-level pattern, or an element of a PARALLEL.  The

   instruction is known not to be a bare USE or CLOBBER.  */

static bool

deletable_insn_p_1 (rtx body)

{

  switch (GET_CODE (body))

    {

    case PREFETCH:

    case TRAP_IF:

      /* The UNSPEC case was added here because the ia-64 claims that

         USEs do not work after reload and generates UNSPECS rather

         than USEs.  Since dce is run after reload we need to avoid

         deleting these even if they are dead.  If it turns out that

         USEs really do work after reload, the ia-64 should be

         changed, and the UNSPEC case can be removed.  */

    case UNSPEC:

      return false;

    default:

      return !volatile_refs_p (body);

    }

}

/* Return true if INSN is a normal instruction that can be deleted by

   the DCE pass.  */

static bool

deletable_insn_p (rtx insn, bool fast, bitmap arg_stores)

{

  rtx body, x;

  int i;

  if (CALL_P (insn)

      /* We cannot delete calls inside of the recursive dce because

         this may cause basic blocks to be deleted and this messes up

         the rest of the stack of optimization passes.  */

      && (!df_in_progress)

      /* We cannot delete pure or const sibling calls because it is

         hard to see the result.  */

      && (!SIBLING_CALL_P (insn))

      /* We can delete dead const or pure calls as long as they do not

         infinite loop.  */

      && (RTL_CONST_OR_PURE_CALL_P (insn)

          && !RTL_LOOPING_CONST_OR_PURE_CALL_P (insn)))

    return find_call_stack_args (insn, false, fast, arg_stores);

  /* Don't delete jumps, notes and the like.  */

  if (!NONJUMP_INSN_P (insn))

    return false;

  /* Don't delete insns that can throw.  */

  if (!insn_nothrow_p (insn))

    return false;

  body = PATTERN (insn);

  switch (GET_CODE (body))

    {

    case USE:

    case VAR_LOCATION:

      return false;

    case CLOBBER:

      if (fast)

        {

          /* A CLOBBER of a dead pseudo register serves no purpose.

             That is not necessarily true for hard registers until

             after reload.  */

          x = XEXP (body, 0);

          return REG_P (x) && (!HARD_REGISTER_P (x) || reload_completed);

        }

      else

        /* Because of the way that use-def chains are built, it is not

           possible to tell if the clobber is dead because it can

           never be the target of a use-def chain.  */

        return false;

    case PARALLEL:

      for (i = XVECLEN (body, 0) - 1; i >= 0; i--)

        if (!deletable_insn_p_1 (XVECEXP (body, 0, i)))

          return false;

      return true;

    default:

      return deletable_insn_p_1 (body);

    }

}

/* Return true if INSN has been marked as needed.  */

static inline int

marked_insn_p (rtx insn)

{

  /* Artificial defs are always needed and they do not have an insn.

     We should never see them here.  */

  gcc_assert (insn);

  return TEST_BIT (marked, INSN_UID (insn));

}

/* If INSN has not yet been marked as needed, mark it now, and add it to

   the worklist.  */

static void

mark_insn (rtx insn, bool fast)

{

  if (!marked_insn_p (insn))

    {

      if (!fast)

        VEC_safe_push (rtx, heap, worklist, insn);

      SET_BIT (marked, INSN_UID (insn));

      if (dump_file)

        fprintf (dump_file, "  Adding insn %d to worklist\n", INSN_UID (insn));

      if (CALL_P (insn)

          && !df_in_progress

          && !SIBLING_CALL_P (insn)

          && (RTL_CONST_OR_PURE_CALL_P (insn)

              && !RTL_LOOPING_CONST_OR_PURE_CALL_P (insn)))

        find_call_stack_args (insn, true, fast, NULL);

    }

}

/* A note_stores callback used by mark_nonreg_stores.  DATA is the

   instruction containing DEST.  */

static void

mark_nonreg_stores_1 (rtx dest, const_rtx pattern, void *data)

{

  if (GET_CODE (pattern) != CLOBBER && !REG_P (dest))

    mark_insn ((rtx) data, true);

}

/* A note_stores callback used by mark_nonreg_stores.  DATA is the

   instruction containing DEST.  */

static void

mark_nonreg_stores_2 (rtx dest, const_rtx pattern, void *data)

{

  if (GET_CODE (pattern) != CLOBBER && !REG_P (dest))

    mark_insn ((rtx) data, false);

}

/* Mark INSN if BODY stores to a non-register destination.  */

static void

mark_nonreg_stores (rtx body, rtx insn, bool fast)

{

  if (fast)

    note_stores (body, mark_nonreg_stores_1, insn);

  else

    note_stores (body, mark_nonreg_stores_2, insn);

}

/* Try to find all stack stores of CALL_INSN arguments if

   ACCUMULATE_OUTGOING_ARGS.  If all stack stores have been found

   and it is therefore safe to eliminate the call, return true,

   otherwise return false.  This function should be first called

   with DO_MARK false, and only when the CALL_INSN is actually

   going to be marked called again with DO_MARK true.  */

static bool

find_call_stack_args (rtx call_insn, bool do_mark, bool fast,

                      bitmap arg_stores)

{

  rtx p, insn, prev_insn;

  bool ret;

  HOST_WIDE_INT min_sp_off, max_sp_off;

  bitmap sp_bytes;

  gcc_assert (CALL_P (call_insn));

  if (!ACCUMULATE_OUTGOING_ARGS)

    return true;

  if (!do_mark)

    {

      gcc_assert (arg_stores);

      bitmap_clear (arg_stores);

    }

  min_sp_off = INTTYPE_MAXIMUM (HOST_WIDE_INT);

  max_sp_off = 0;

  /* First determine the minimum and maximum offset from sp for

     stored arguments.  */

  for (p = CALL_INSN_FUNCTION_USAGE (call_insn); p; p = XEXP (p, 1))

    if (GET_CODE (XEXP (p, 0)) == USE

        && MEM_P (XEXP (XEXP (p, 0), 0)))

      {

        rtx mem = XEXP (XEXP (p, 0), 0), addr, size;

        HOST_WIDE_INT off = 0;

        size = MEM_SIZE (mem);

        if (size == NULL_RTX)

          return false;

        addr = XEXP (mem, 0);

        if (GET_CODE (addr) == PLUS

            && REG_P (XEXP (addr, 0))

            && CONST_INT_P (XEXP (addr, 1)))

          {

            off = INTVAL (XEXP (addr, 1));

            addr = XEXP (addr, 0);

          }

        if (addr != stack_pointer_rtx)

          {

            if (!REG_P (addr))

              return false;

            /* If not fast, use chains to see if addr wasn't set to

               sp + offset.  */

            if (!fast)

              {

                df_ref *use_rec;

                struct df_link *defs;

                rtx set;

                for (use_rec = DF_INSN_USES (call_insn); *use_rec; use_rec++)

                  if (rtx_equal_p (addr, DF_REF_REG (*use_rec)))

                    break;

                if (*use_rec == NULL)

                  return false;

                for (defs = DF_REF_CHAIN (*use_rec); defs; defs = defs->next)

                  if (! DF_REF_IS_ARTIFICIAL (defs->ref))

                    break;

                if (defs == NULL)

                  return false;

                set = single_set (DF_REF_INSN (defs->ref));

                if (!set)

                  return false;

                if (GET_CODE (SET_SRC (set)) != PLUS

                    || XEXP (SET_SRC (set), 0) != stack_pointer_rtx

                    || !CONST_INT_P (XEXP (SET_SRC (set), 1)))

                  return false;

                off += INTVAL (XEXP (SET_SRC (set), 1));

              }

            else

              return false;

          }

        min_sp_off = MIN (min_sp_off, off);

        max_sp_off = MAX (max_sp_off, off + INTVAL (size));

      }

  if (min_sp_off >= max_sp_off)

    return true;

  sp_bytes = BITMAP_ALLOC (NULL);

  /* Set bits in SP_BYTES bitmap for bytes relative to sp + min_sp_off

     which contain arguments.  Checking has been done in the previous

     loop.  */

  for (p = CALL_INSN_FUNCTION_USAGE (call_insn); p; p = XEXP (p, 1))

    if (GET_CODE (XEXP (p, 0)) == USE

        && MEM_P (XEXP (XEXP (p, 0), 0)))

      {

        rtx mem = XEXP (XEXP (p, 0), 0), addr;

        HOST_WIDE_INT off = 0, byte;

        addr = XEXP (mem, 0);

        if (GET_CODE (addr) == PLUS

            && REG_P (XEXP (addr, 0))

            && CONST_INT_P (XEXP (addr, 1)))

          {

            off = INTVAL (XEXP (addr, 1));

            addr = XEXP (addr, 0);

          }

        if (addr != stack_pointer_rtx)

          {

            df_ref *use_rec;

            struct df_link *defs;

            rtx set;

            for (use_rec = DF_INSN_USES (call_insn); *use_rec; use_rec++)

              if (rtx_equal_p (addr, DF_REF_REG (*use_rec)))

                break;

            for (defs = DF_REF_CHAIN (*use_rec); defs; defs = defs->next)

              if (! DF_REF_IS_ARTIFICIAL (defs->ref))

                break;

            set = single_set (DF_REF_INSN (defs->ref));

            off += INTVAL (XEXP (SET_SRC (set), 1));

          }

        for (byte = off; byte < off + INTVAL (MEM_SIZE (mem)); byte++)

          {

            if (!bitmap_set_bit (sp_bytes, byte - min_sp_off))

              gcc_unreachable ();

          }

      }

  /* Walk backwards, looking for argument stores.  The search stops

     when seeing another call, sp adjustment or memory store other than

     argument store.  */

  ret = false;

  for (insn = PREV_INSN (call_insn); insn; insn = prev_insn)

    {

      rtx set, mem, addr;

      HOST_WIDE_INT off, byte;

      if (insn == BB_HEAD (BLOCK_FOR_INSN (call_insn)))

        prev_insn = NULL_RTX;

      else

        prev_insn = PREV_INSN (insn);

      if (CALL_P (insn))

        break;

      if (!INSN_P (insn))

        continue;

      set = single_set (insn);

      if (!set || SET_DEST (set) == stack_pointer_rtx)

        break;

      if (!MEM_P (SET_DEST (set)))

        continue;

      mem = SET_DEST (set);

      addr = XEXP (mem, 0);

      off = 0;

      if (GET_CODE (addr) == PLUS

          && REG_P (XEXP (addr, 0))

          && CONST_INT_P (XEXP (addr, 1)))

        {

          off = INTVAL (XEXP (addr, 1));

          addr = XEXP (addr, 0);

        }

      if (addr != stack_pointer_rtx)

        {

          if (!REG_P (addr))

            break;

          if (!fast)

            {

              df_ref *use_rec;

              struct df_link *defs;

              rtx set;

              for (use_rec = DF_INSN_USES (insn); *use_rec; use_rec++)

                if (rtx_equal_p (addr, DF_REF_REG (*use_rec)))

                  break;

              if (*use_rec == NULL)

                break;

              for (defs = DF_REF_CHAIN (*use_rec); defs; defs = defs->next)

                if (! DF_REF_IS_ARTIFICIAL (defs->ref))

                  break;

              if (defs == NULL)

                break;

              set = single_set (DF_REF_INSN (defs->ref));

              if (!set)

                break;

              if (GET_CODE (SET_SRC (set)) != PLUS

                  || XEXP (SET_SRC (set), 0) != stack_pointer_rtx

                  || !CONST_INT_P (XEXP (SET_SRC (set), 1)))

                break;

              off += INTVAL (XEXP (SET_SRC (set), 1));

            }

          else

            break;

        }

      if (GET_MODE_SIZE (GET_MODE (mem)) == 0)

        break;

      for (byte = off; byte < off + GET_MODE_SIZE (GET_MODE (mem)); byte++)

        {

          if (byte < min_sp_off

              || byte >= max_sp_off

              || !bitmap_clear_bit (sp_bytes, byte - min_sp_off))

            break;

        }

      if (!deletable_insn_p (insn, fast, NULL))

        break;

      if (do_mark)

        mark_insn (insn, fast);

      else

        bitmap_set_bit (arg_stores, INSN_UID (insn));

      if (bitmap_empty_p (sp_bytes))

        {

          ret = true;

          break;

        }

    }

  BITMAP_FREE (sp_bytes);

  if (!ret && arg_stores)

    bitmap_clear (arg_stores);

  return ret;

}

/* Delete all REG_EQUAL notes of the registers INSN writes, to prevent

   bad dangling REG_EQUAL notes. */

static void

delete_corresponding_reg_eq_notes (rtx insn)

{

  df_ref *def_rec;

  for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)

    {

      df_ref def = *def_rec;

      unsigned int regno = DF_REF_REGNO (def);

      /* This loop is a little tricky.  We cannot just go down the

         chain because it is being modified by the actions in the

         loop.  So we just get the head.  We plan to drain the list

         anyway.  */

      while (DF_REG_EQ_USE_CHAIN (regno))

        {

          df_ref eq_use = DF_REG_EQ_USE_CHAIN (regno);

          rtx noted_insn = DF_REF_INSN (eq_use);

          rtx note = find_reg_note (noted_insn, REG_EQUAL, NULL_RTX);

          if (!note)

            note = find_reg_note (noted_insn, REG_EQUIV, NULL_RTX);

          /* This assert is generally triggered when someone deletes a

             REG_EQUAL or REG_EQUIV note by hacking the list manually

             rather than calling remove_note.  */

          gcc_assert (note);

          remove_note (noted_insn, note);

        }

    }

}

/* Delete every instruction that hasn't been marked.  */

static void

delete_unmarked_insns (void)

{

  basic_block bb;

  rtx insn, next;

  bool must_clean = false;

  FOR_EACH_BB_REVERSE (bb)

    FOR_BB_INSNS_REVERSE_SAFE (bb, insn, next)

      if (INSN_P (insn))

        {

          /* Always delete no-op moves.  */

          if (noop_move_p (insn))

            ;

          /* Otherwise rely only on the DCE algorithm.  */

          else if (marked_insn_p (insn))

            continue;

          /* Beware that reaching a dbg counter limit here can result

             in miscompiled file.  This occurs when a group of insns

             must be deleted together, typically because the kept insn

             depends on the output from the deleted insn.  Deleting

             this insns in reverse order (both at the bb level and

             when looking at the blocks) minimizes this, but does not

             eliminate it, since it is possible for the using insn to

             be top of a block and the producer to be at the bottom of

             the block.  However, in most cases this will only result

             in an uninitialized use of an insn that is dead anyway.

             However, there is one rare case that will cause a

             miscompile: deletion of non-looping pure and constant

             calls on a machine where ACCUMULATE_OUTGOING_ARGS is true.

             In this case it is possible to remove the call, but leave

             the argument pushes to the stack.  Because of the changes

             to the stack pointer, this will almost always lead to a

             miscompile.  */

          if (!dbg_cnt (dce))

            continue;

          if (dump_file)

            fprintf (dump_file, "DCE: Deleting insn %d\n", INSN_UID (insn));

          /* Before we delete the insn we have to delete REG_EQUAL notes

             for the destination regs in order to avoid dangling notes.  */

          delete_corresponding_reg_eq_notes (insn);

          /* If a pure or const call is deleted, this may make the cfg

             have unreachable blocks.  We rememeber this and call

             delete_unreachable_blocks at the end.  */

          if (CALL_P (insn))

            must_clean = true;

          /* Now delete the insn.  */

          delete_insn_and_edges (insn);

        }

  /* Deleted a pure or const call.  */

  if (must_clean)

    delete_unreachable_blocks ();

}

/* Go through the instructions and mark those whose necessity is not

   dependent on inter-instruction information.  Make sure all other

   instructions are not marked.  */

static void

prescan_insns_for_dce (bool fast)

{

  basic_block bb;

  rtx insn, prev;

  bitmap arg_stores = NULL;

  if (dump_file)

    fprintf (dump_file, "Finding needed instructions:\n");

  if (!df_in_progress && ACCUMULATE_OUTGOING_ARGS)

    arg_stores = BITMAP_ALLOC (NULL);

  FOR_EACH_BB (bb)

    {

      FOR_BB_INSNS_REVERSE_SAFE (bb, insn, prev)

        if (INSN_P (insn))

          {

            /* Don't mark argument stores now.  They will be marked

               if needed when the associated CALL is marked.  */

            if (arg_stores && bitmap_bit_p (arg_stores, INSN_UID (insn)))

              continue;

            if (deletable_insn_p (insn, fast, arg_stores))

              mark_nonreg_stores (PATTERN (insn), insn, fast);

            else

              mark_insn (insn, fast);

          }

      /* find_call_stack_args only looks at argument stores in the

         same bb.  */

      if (arg_stores)

        bitmap_clear (arg_stores);

    }

  if (arg_stores)

    BITMAP_FREE (arg_stores);

  if (dump_file)

    fprintf (dump_file, "Finished finding needed instructions:\n");

}

/* UD-based DSE routines. */

/* Mark instructions that define artificially-used registers, such as

   the frame pointer and the stack pointer.  */

static void

mark_artificial_uses (void)

{

  basic_block bb;

  struct df_link *defs;

  df_ref *use_rec;

  FOR_ALL_BB (bb)

    {

      for (use_rec = df_get_artificial_uses (bb->index);

           *use_rec; use_rec++)

        for (defs = DF_REF_CHAIN (*use_rec); defs; defs = defs->next)

          if (! DF_REF_IS_ARTIFICIAL (defs->ref))

            mark_insn (DF_REF_INSN (defs->ref), false);

    }

}

/* Mark every instruction that defines a register value that INSN uses.  */

static void

mark_reg_dependencies (rtx insn)

{

  struct df_link *defs;

  df_ref *use_rec;

  if (DEBUG_INSN_P (insn))

    return;

  for (use_rec = DF_INSN_USES (insn); *use_rec; use_rec++)

    {

      df_ref use = *use_rec;

      if (dump_file)

        {

          fprintf (dump_file, "Processing use of ");

          print_simple_rtl (dump_file, DF_REF_REG (use));

          fprintf (dump_file, " in insn %d:\n", INSN_UID (insn));

        }

      for (defs = DF_REF_CHAIN (use); defs; defs = defs->next)

        if (! DF_REF_IS_ARTIFICIAL (defs->ref))

          mark_insn (DF_REF_INSN (defs->ref), false);

    }

}

/* Initialize global variables for a new DCE pass.  */

static void

init_dce (bool fast)

{

  if (!df_in_progress)

    {

      if (!fast)

        df_chain_add_problem (DF_UD_CHAIN);

      df_analyze ();

    }

  if (dump_file)

    df_dump (dump_file);

  if (fast)

    {

      bitmap_obstack_initialize (&dce_blocks_bitmap_obstack);

      bitmap_obstack_initialize (&dce_tmp_bitmap_obstack);

    }

  marked = sbitmap_alloc (get_max_uid () + 1);

  sbitmap_zero (marked);

}

/* Free the data allocated by init_dce.  */

static void

fini_dce (bool fast)

{

  sbitmap_free (marked);