* ssa-dce.c: Renamed from dce.c.

git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@43457 138bc75d-0d04-0410-961f-82ee72b054a4

1 files changed, 618 insertions, 0 deletions

diff --git a/gcc/ssa-dce.c b/gcc/ssa-dce.c
new file mode 100644
index 00000000000..ca0d998070b
--- /dev/null
+++ b/gcc/ssa-dce.c
@@ -0,0 +1,618 @@
+/* Dead-code elimination pass for the GNU compiler.
+   Copyright (C) 2000 Free Software Foundation, Inc.
+   Written by Jeffrey D. Oldham <oldham@codesourcery.com>.
+
+This file is part of GNU CC.
+
+GNU CC 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 2, or (at your option) any
+later version.
+
+GNU CC 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 GNU CC; see the file COPYING.  If not, write to the Free
+Software Foundation, 59 Temple Place - Suite 330, Boston, MA
+02111-1307, USA.  */
+
+/* Dead-code elimination is the removal of instructions which have no
+   impact on the program's output.  "Dead instructions" have no impact
+   on the program's output, while "necessary instructions" may have
+   impact on the output.
+
+   The algorithm consists of three phases:
+   1) marking as necessary all instructions known to be necessary,
+      e.g., writing a value to memory,
+   2) propagating necessary instructions, e.g., the instructions
+      giving values to operands in necessary instructions, and
+   3) removing dead instructions (except replacing dead conditionals
+      with unconditional jumps).
+
+   Side Effects:
+   The last step can require adding labels, deleting insns, and
+   modifying basic block structures.  Some conditional jumps may be
+   converted to unconditional jumps so the control-flow graph may be
+   out-of-date.  
+
+   Edges from some infinite loops to the exit block can be added to
+   the control-flow graph.
+
+   It Does Not Perform:
+   We decided to not simultaneously perform jump optimization and dead
+   loop removal during dead-code elimination.  Thus, all jump
+   instructions originally present remain after dead-code elimination
+   but 1) unnecessary conditional jump instructions are changed to
+   unconditional jump instructions and 2) all unconditional jump
+   instructions remain.
+
+   Assumptions:
+   1) SSA has been performed.
+   2) The basic block and control-flow graph structures are accurate.
+   3) The flow graph permits constructing an edge_list.
+   4) note rtxes should be saved.
+
+   Unfinished:
+   When replacing unnecessary conditional jumps with unconditional
+   jumps, the control-flow graph is not updated.  It should be.
+
+   References:
+   Building an Optimizing Compiler
+   Robert Morgan
+   Butterworth-Heinemann, 1998
+   Section 8.9
+*/
+
+#include "config.h"
+#include "system.h"
+
+#include "rtl.h"
+#include "hard-reg-set.h"
+#include "basic-block.h"
+#include "ssa.h"
+#include "insn-config.h"
+#include "recog.h"
+#include "output.h"
+
+
+/* A map from blocks to the edges on which they are control dependent.  */
+typedef struct {
+  /* An dynamically allocated array.  The Nth element corresponds to
+     the block with index N + 2.  The Ith bit in the bitmap is set if
+     that block is dependent on the Ith edge.  */
+  bitmap *data;
+  /* The number of elements in the array.  */
+  int length;
+} control_dependent_block_to_edge_map_s, *control_dependent_block_to_edge_map;
+
+/* Local function prototypes.  */
+static control_dependent_block_to_edge_map control_dependent_block_to_edge_map_create
+  PARAMS((size_t num_basic_blocks));
+static void set_control_dependent_block_to_edge_map_bit
+  PARAMS ((control_dependent_block_to_edge_map c, basic_block bb,
+	   int edge_index));
+static void control_dependent_block_to_edge_map_free
+  PARAMS ((control_dependent_block_to_edge_map c));
+static void find_all_control_dependences
+  PARAMS ((struct edge_list *el, int *pdom,
+	   control_dependent_block_to_edge_map cdbte));
+static void find_control_dependence
+  PARAMS ((struct edge_list *el, int edge_index, int *pdom,
+	   control_dependent_block_to_edge_map cdbte));
+static basic_block find_pdom
+  PARAMS ((int *pdom, basic_block block));
+static int inherently_necessary_register_1
+  PARAMS ((rtx *current_rtx, void *data));
+static int inherently_necessary_register
+  PARAMS ((rtx current_rtx));
+static int find_inherently_necessary
+  PARAMS ((rtx current_rtx));
+static int propagate_necessity_through_operand
+  PARAMS ((rtx *current_rtx, void *data));
+
+/* Unnecessary insns are indicated using insns' in_struct bit.  */
+
+/* Indicate INSN is dead-code; returns nothing.  */
+#define KILL_INSN(INSN)		INSN_DEAD_CODE_P(INSN) = 1
+/* Indicate INSN is necessary, i.e., not dead-code; returns nothing.  */
+#define RESURRECT_INSN(INSN)	INSN_DEAD_CODE_P(INSN) = 0
+/* Return nonzero if INSN is unnecessary.  */
+#define UNNECESSARY_P(INSN)	INSN_DEAD_CODE_P(INSN)
+static void mark_all_insn_unnecessary
+  PARAMS ((void));
+/* Execute CODE with free variable INSN for all unnecessary insns in
+   an unspecified order, producing no output.  */
+#define EXECUTE_IF_UNNECESSARY(INSN, CODE)	\
+{								\
+  rtx INSN;							\
+								\
+  for (INSN = get_insns (); INSN != NULL_RTX; INSN = NEXT_INSN (INSN))	\
+    if (INSN_DEAD_CODE_P (INSN)) {				\
+      CODE;							\
+    }								\
+}
+/* Find the label beginning block BB.  */
+static rtx find_block_label
+  PARAMS ((basic_block bb));
+/* Remove INSN, updating its basic block structure.  */
+static void delete_insn_bb
+  PARAMS ((rtx insn));
+
+/* Recording which blocks are control dependent on which edges.  We
+   expect each block to be control dependent on very few edges so we
+   use a bitmap for each block recording its edges.  An array holds
+   the bitmap.  Its position 0 entry holds the bitmap for block
+   INVALID_BLOCK+1 so that all blocks, including the entry and exit
+   blocks can participate in the data structure.  */
+
+/* Create a control_dependent_block_to_edge_map, given the number
+   NUM_BASIC_BLOCKS of non-entry, non-exit basic blocks, e.g.,
+   n_basic_blocks.  This memory must be released using
+   control_dependent_block_to_edge_map_free ().  */
+
+static control_dependent_block_to_edge_map
+control_dependent_block_to_edge_map_create (num_basic_blocks)
+     size_t num_basic_blocks;
+{
+  int i;
+  control_dependent_block_to_edge_map c
+    = xmalloc (sizeof (control_dependent_block_to_edge_map_s));
+  c->length = num_basic_blocks - (INVALID_BLOCK+1);
+  c->data = xmalloc ((size_t) c->length*sizeof (bitmap));
+  for (i = 0; i < c->length; ++i)
+    c->data[i] = BITMAP_XMALLOC ();
+
+  return c;
+}
+
+/* Indicate block BB is control dependent on an edge with index
+   EDGE_INDEX in the mapping C of blocks to edges on which they are
+   control-dependent.  */
+
+static void
+set_control_dependent_block_to_edge_map_bit (c, bb, edge_index)
+     control_dependent_block_to_edge_map c;
+     basic_block bb;
+     int edge_index;
+{
+  if (bb->index - (INVALID_BLOCK+1) >= c->length)
+    abort ();
+
+  bitmap_set_bit (c->data[bb->index - (INVALID_BLOCK+1)],
+		  edge_index);
+}
+
+/* Execute CODE for each edge (given number EDGE_NUMBER within the
+   CODE) for which the block containing INSN is control dependent,
+   returning no output.  CDBTE is the mapping of blocks to edges on
+   which they are control-dependent.  */
+
+#define EXECUTE_IF_CONTROL_DEPENDENT(CDBTE, INSN, EDGE_NUMBER, CODE) \
+	EXECUTE_IF_SET_IN_BITMAP \
+	  (CDBTE->data[BLOCK_NUM (INSN) - (INVALID_BLOCK+1)], 0, \
+	  EDGE_NUMBER, CODE)
+
+/* Destroy a control_dependent_block_to_edge_map C.  */
+
+static void
+control_dependent_block_to_edge_map_free (c)
+     control_dependent_block_to_edge_map c;
+{
+  int i;
+  for (i = 0; i < c->length; ++i)
+    BITMAP_XFREE (c->data[i]);
+  free ((PTR) c);
+}
+
+/* Record all blocks' control dependences on all edges in the edge
+   list EL, ala Morgan, Section 3.6.  The mapping PDOM of blocks to
+   their postdominators are used, and results are stored in CDBTE,
+   which should be empty.  */
+
+static void
+find_all_control_dependences (el, pdom, cdbte)
+   struct edge_list *el;
+   int *pdom;
+   control_dependent_block_to_edge_map cdbte;
+{
+  int i;
+
+  for (i = 0; i < NUM_EDGES (el); ++i)
+    find_control_dependence (el, i, pdom, cdbte);
+}
+
+/* Determine all blocks' control dependences on the given edge with
+   edge_list EL index EDGE_INDEX, ala Morgan, Section 3.6.  The
+   mapping PDOM of blocks to their postdominators are used, and
+   results are stored in CDBTE, which is assumed to be initialized
+   with zeros in each (block b', edge) position.  */
+
+static void
+find_control_dependence (el, edge_index, pdom, cdbte)
+   struct edge_list *el;
+   int edge_index;
+   int *pdom;
+   control_dependent_block_to_edge_map cdbte;
+{
+  basic_block current_block;
+  basic_block ending_block;
+
+  if (INDEX_EDGE_PRED_BB (el, edge_index) == EXIT_BLOCK_PTR)
+    abort ();
+  ending_block = 
+    (INDEX_EDGE_PRED_BB (el, edge_index) == ENTRY_BLOCK_PTR) 
+    ? BASIC_BLOCK (0) 
+    : find_pdom (pdom, INDEX_EDGE_PRED_BB (el, edge_index));
+
+  for (current_block = INDEX_EDGE_SUCC_BB (el, edge_index);
+       current_block != ending_block && current_block != EXIT_BLOCK_PTR;
+       current_block = find_pdom (pdom, current_block))
+    {
+      set_control_dependent_block_to_edge_map_bit (cdbte,
+						   current_block,
+						   edge_index);
+    }
+}
+
+/* Find the immediate postdominator PDOM of the specified basic block
+   BLOCK.  This function is necessary because some blocks have
+   negative numbers.  */
+
+static basic_block
+find_pdom (pdom, block)
+     int *pdom;
+     basic_block block;
+{
+  if (!block)
+    abort ();
+  if (block->index == INVALID_BLOCK)
+    abort ();
+
+  if (block == ENTRY_BLOCK_PTR)
+    return BASIC_BLOCK (0);
+  else if (block == EXIT_BLOCK_PTR || pdom[block->index] == EXIT_BLOCK)
+    return EXIT_BLOCK_PTR;
+  else
+    return BASIC_BLOCK (pdom[block->index]);
+}
+
+/* Determine if the given CURRENT_RTX uses a hard register not
+   converted to SSA.  Returns nonzero only if it uses such a hard
+   register.  DATA is not used.
+
+   The program counter (PC) is not considered inherently necessary
+   since code should be position-independent and thus not depend on
+   particular PC values.  */
+
+static int
+inherently_necessary_register_1 (current_rtx, data)
+     rtx *current_rtx;
+     void *data ATTRIBUTE_UNUSED;
+{
+  rtx x = *current_rtx;
+
+  if (x == NULL_RTX)
+    return 0;
+  switch (GET_CODE (x))
+    {
+    case CLOBBER:
+      /* Do not traverse the rest of the clobber.  */
+      return -1;		
+      break;
+    case PC:
+      return 0;
+      break;
+    case REG:
+      if (CONVERT_REGISTER_TO_SSA_P (REGNO (x)) || x == pc_rtx)
+	return 0;
+      else
+	return !0;
+      break;
+    default:
+      return 0;
+      break;
+    }
+}
+
+/* Return nonzero if the insn CURRENT_RTX is inherently necessary.  */
+
+static int
+inherently_necessary_register (current_rtx)
+     rtx current_rtx;
+{
+  return for_each_rtx (&current_rtx,
+		       &inherently_necessary_register_1, NULL);
+}
+
+/* Mark X as inherently necessary if appropriate.  For example,
+   function calls and storing values into memory are inherently
+   necessary.  This function is to be used with for_each_rtx ().
+   Return nonzero iff inherently necessary.  */
+
+static int
+find_inherently_necessary (x)
+     rtx x;
+{
+  rtx pattern;
+  if (x == NULL_RTX)
+    return 0;
+  else if (inherently_necessary_register (x))
+    return !0;
+  else
+    switch (GET_CODE (x))
+      {  
+      case CALL_INSN:
+      case CODE_LABEL:
+      case NOTE:
+      case BARRIER:
+	return !0;
+	break;
+      case JUMP_INSN:
+	return JUMP_TABLE_DATA_P (x) || computed_jump_p (x) != 0;
+	break;
+      case INSN:
+	pattern = PATTERN (x);
+	switch (GET_CODE (pattern))
+	  {
+	  case SET:
+	  case PRE_DEC:
+	  case PRE_INC:
+	  case POST_DEC:
+	  case POST_INC:
+	    return GET_CODE (SET_DEST (pattern)) == MEM;
+	  case CALL:
+	  case RETURN:
+	  case USE:
+	  case CLOBBER:
+	    return !0;
+	    break;
+	  case ASM_INPUT:
+	    /* We treat assembler instructions as inherently
+	       necessary, and we hope that its operands do not need to
+	       be propagated.  */
+	    return !0;
+	    break;
+	  default:
+	    return 0;
+	  }
+      default:
+	/* Found an impossible insn type.  */
+	abort();
+	break;
+      }
+}
+
+/* Propagate necessity through REG and SUBREG operands of CURRENT_RTX.
+   This function is called with for_each_rtx () on necessary
+   instructions.  The DATA must be a varray of unprocessed
+   instructions.  */
+
+static int
+propagate_necessity_through_operand (current_rtx, data)
+     rtx *current_rtx;
+     void *data;
+{
+  rtx x = *current_rtx;
+  varray_type *unprocessed_instructions = (varray_type *) data;
+
+  if (x == NULL_RTX)
+    return 0;
+  switch ( GET_CODE (x))
+    {
+    case REG:
+      if (CONVERT_REGISTER_TO_SSA_P (REGNO (x)))
+	{
+	  rtx insn = VARRAY_RTX (ssa_definition, REGNO (x));
+	  if (insn != NULL_RTX && UNNECESSARY_P (insn))
+	    {
+	      RESURRECT_INSN (insn);
+	      VARRAY_PUSH_RTX (*unprocessed_instructions, insn);
+	    }
+	}
+      return 0;
+
+    default:
+      return 0;
+    }
+}
+
+/* Indicate all insns initially assumed to be unnecessary.  */
+
+static void
+mark_all_insn_unnecessary ()
+{
+  rtx insn;
+  for (insn = get_insns (); insn != NULL_RTX; insn = NEXT_INSN (insn))
+    KILL_INSN (insn);
+}
+
+/* Find the label beginning block BB, adding one if necessary.  */
+
+static rtx
+find_block_label (bb)
+     basic_block bb;
+{
+  rtx insn = bb->head;
+  if (LABEL_P (insn))
+    return insn;
+  else
+    {
+      rtx new_label = emit_label_before (gen_label_rtx (), insn);
+      if (insn == bb->head)
+	bb->head = new_label;
+      return new_label;
+    }
+}
+
+/* Remove INSN, updating its basic block structure.  */
+
+static void
+delete_insn_bb (insn)
+     rtx insn;
+{
+  basic_block bb;
+  if (!insn)
+    abort ();
+  bb = BLOCK_FOR_INSN (insn);
+  if (!bb)
+    abort ();
+  if (bb->head == bb->end)
+    {
+      /* Delete the insn by converting it to a note.  */
+      PUT_CODE (insn, NOTE);
+      NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
+      return;
+    }
+  else if (insn == bb->head)
+    bb->head = NEXT_INSN (insn);
+  else if (insn == bb->end)
+    bb->end = PREV_INSN (insn);
+  delete_insn (insn);
+}
+
+/* Perform the dead-code elimination.  */
+
+void
+eliminate_dead_code ()
+{
+  int i;
+  rtx insn;
+  /* Necessary instructions with operands to explore.  */
+  varray_type unprocessed_instructions;
+  /* Map element (b,e) is nonzero if the block is control dependent on
+     edge.  "cdbte" abbreviates control dependent block to edge.  */
+  control_dependent_block_to_edge_map cdbte;
+ /* Element I is the immediate postdominator of block I.  */
+  int *pdom;
+  struct edge_list *el;
+
+  int max_insn_uid = get_max_uid ();
+
+  /* Initialize the data structures.  */
+  mark_all_insn_unnecessary ();
+  VARRAY_RTX_INIT (unprocessed_instructions, 64,
+		   "unprocessed instructions");
+  cdbte = control_dependent_block_to_edge_map_create (n_basic_blocks);
+
+  /* Prepare for use of BLOCK_NUM ().  */
+  connect_infinite_loops_to_exit ();
+   /* Be careful not to clear the added edges.  */
+  compute_bb_for_insn (max_insn_uid);
+
+  /* Compute control dependence.  */
+  pdom = (int *) xmalloc (n_basic_blocks * sizeof (int));
+  for (i = 0; i < n_basic_blocks; ++i)
+    pdom[i] = INVALID_BLOCK;
+  calculate_dominance_info (pdom, NULL, CDI_POST_DOMINATORS);
+  /* Assume there is a path from each node to the exit block.  */
+  for (i = 0; i < n_basic_blocks; ++i)
+    if (pdom[i] == INVALID_BLOCK)
+      pdom[i] = EXIT_BLOCK;
+  el = create_edge_list();
+  find_all_control_dependences (el, pdom, cdbte);
+
+  /* Find inherently necessary instructions.  */
+  for (insn = get_insns (); insn != NULL_RTX; insn = NEXT_INSN (insn))
+    if (find_inherently_necessary (insn))
+      {
+	RESURRECT_INSN (insn);
+	VARRAY_PUSH_RTX (unprocessed_instructions, insn);
+      }
+
+  /* Propagate necessity using the operands of necessary instructions.  */
+  while (VARRAY_ACTIVE_SIZE (unprocessed_instructions) > 0)
+    {
+      rtx current_instruction;
+      int edge_number;
+
+      current_instruction = VARRAY_TOP_RTX (unprocessed_instructions);
+      VARRAY_POP (unprocessed_instructions);
+
+      /* Make corresponding control dependent edges necessary.  */
+      /* Assume the only JUMP_INSN is the block's last insn.  It appears
+	 that the last instruction of the program need not be a
+	 JUMP_INSN.  */
+
+      if (INSN_P (current_instruction)
+	  && !JUMP_TABLE_DATA_P (current_instruction))
+	{
+	  /* Notes and labels contain no interesting operands.  */
+	  EXECUTE_IF_CONTROL_DEPENDENT
+	    (cdbte, current_instruction, edge_number,
+	    {
+	      rtx jump_insn = (INDEX_EDGE_PRED_BB (el, edge_number))->end;
+	      if (GET_CODE (jump_insn) == JUMP_INSN
+		  && UNNECESSARY_P (jump_insn))
+		{
+		  RESURRECT_INSN (jump_insn);
+		  VARRAY_PUSH_RTX (unprocessed_instructions, jump_insn);
+		}
+	    });
+
+	  /* Propagate through the operands.  */
+	  for_each_rtx (&current_instruction,
+			&propagate_necessity_through_operand,
+			(PTR) &unprocessed_instructions);
+
+	}
+    }
+
+  /* Remove the unnecessary instructions.  */
+  EXECUTE_IF_UNNECESSARY (insn,
+  {
+    if (any_condjump_p (insn))
+      {
+      /* Convert unnecessary conditional insn to an unconditional
+	 jump to immediate postdominator block.  */
+	rtx old_label = JUMP_LABEL (insn);
+	int pdom_block_number =
+	  find_pdom (pdom, BLOCK_FOR_INSN (insn))->index;
+
+	/* Prevent the conditional jump's label from being deleted so
+	   we do not have to modify the basic block structure.  */
+	++LABEL_NUSES (old_label);
+
+	if (pdom_block_number != EXIT_BLOCK
+	    && pdom_block_number != INVALID_BLOCK)
+	  {
+	    rtx lbl = find_block_label (BASIC_BLOCK (pdom_block_number));
+	    rtx new_jump = emit_jump_insn_before (gen_jump (lbl), insn);
+	    
+	    /* Let jump know that label is in use.  */
+	    JUMP_LABEL (new_jump) = lbl;
+	    ++LABEL_NUSES (lbl);
+
+	    delete_insn_bb (insn);
+
+	    /* A conditional branch is unnecessary if and only if any
+	       block control-dependent on it is unnecessary.  Thus,
+	       any phi nodes in these unnecessary blocks are also
+	       removed and these nodes need not be updated.  */
+
+	    /* A barrier must follow any unconditional jump.  Barriers
+	       are not in basic blocks so this must occur after
+	       deleting the conditional jump.  */
+	    emit_barrier_after (new_jump);
+	  }
+	else
+	  /* The block drops off the end of the function and the
+	     ending conditional jump is not needed.  */
+	  delete_insn_bb (insn);
+      }
+    else if (!JUMP_P (insn))
+      delete_insn_bb (insn);
+  });
+  
+  /* Release allocated memory.  */
+  for (insn = get_insns (); insn != NULL_RTX; insn = NEXT_INSN (insn))
+    RESURRECT_INSN (insn);
+  if (VARRAY_ACTIVE_SIZE (unprocessed_instructions) != 0)
+    abort ();
+  VARRAY_FREE (unprocessed_instructions);
+  control_dependent_block_to_edge_map_free (cdbte);
+  free ((PTR) pdom);
+  free_edge_list (el);
+}