combine.c

GCC编译器源代码

/* Optimize by combining instructions for GNU compiler.
   Copyright (C) 1987, 88, 92-97, 1998 Free Software Foundation, Inc.

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.  */


/* This module is essentially the "combiner" phase of the U. of Arizona
   Portable Optimizer, but redone to work on our list-structured
   representation for RTL instead of their string representation.

   The LOG_LINKS of each insn identify the most recent assignment
   to each REG used in the insn.  It is a list of previous insns,
   each of which contains a SET for a REG that is used in this insn
   and not used or set in between.  LOG_LINKs never cross basic blocks.
   They were set up by the preceding pass (lifetime analysis).

   We try to combine each pair of insns joined by a logical link.
   We also try to combine triples of insns A, B and C when
   C has a link back to B and B has a link back to A.

   LOG_LINKS does not have links for use of the CC0.  They don't
   need to, because the insn that sets the CC0 is always immediately
   before the insn that tests it.  So we always regard a branch
   insn as having a logical link to the preceding insn.  The same is true
   for an insn explicitly using CC0.

   We check (with use_crosses_set_p) to avoid combining in such a way
   as to move a computation to a place where its value would be different.

   Combination is done by mathematically substituting the previous
   insn(s) values for the regs they set into the expressions in
   the later insns that refer to these regs.  If the result is a valid insn
   for our target machine, according to the machine description,
   we install it, delete the earlier insns, and update the data flow
   information (LOG_LINKS and REG_NOTES) for what we did.

   There are a few exceptions where the dataflow information created by
   flow.c aren't completely updated:

   - reg_live_length is not updated
   - reg_n_refs is not adjusted in the rare case when a register is
     no longer required in a computation
   - there are extremely rare cases (see distribute_regnotes) when a
     REG_DEAD note is lost
   - a LOG_LINKS entry that refers to an insn with multiple SETs may be
     removed because there is no way to know which register it was 
     linking

   To simplify substitution, we combine only when the earlier insn(s)
   consist of only a single assignment.  To simplify updating afterward,
   we never combine when a subroutine call appears in the middle.

   Since we do not represent assignments to CC0 explicitly except when that
   is all an insn does, there is no LOG_LINKS entry in an insn that uses
   the condition code for the insn that set the condition code.
   Fortunately, these two insns must be consecutive.
   Therefore, every JUMP_INSN is taken to have an implicit logical link
   to the preceding insn.  This is not quite right, since non-jumps can
   also use the condition code; but in practice such insns would not
   combine anyway.  */

#include "config.h"
#ifdef __STDC__
#include <stdarg.h>
#else
#include <varargs.h>
#endif

/* Must precede rtl.h for FFS.  */
#include <stdio.h>

#include "rtl.h"
#include "flags.h"
#include "regs.h"
#include "hard-reg-set.h"
#include "expr.h"
#include "basic-block.h"
#include "insn-config.h"
#include "insn-flags.h"
#include "insn-codes.h"
#include "insn-attr.h"
#include "recog.h"
#include "real.h"

/* It is not safe to use ordinary gen_lowpart in combine.
   Use gen_lowpart_for_combine instead.  See comments there.  */
#define gen_lowpart dont_use_gen_lowpart_you_dummy

/* Number of attempts to combine instructions in this function.  */

static int combine_attempts;

/* Number of attempts that got as far as substitution in this function.  */

static int combine_merges;

/* Number of instructions combined with added SETs in this function.  */

static int combine_extras;

/* Number of instructions combined in this function.  */

static int combine_successes;

/* Totals over entire compilation.  */

static int total_attempts, total_merges, total_extras, total_successes;

/* Define a default value for REVERSIBLE_CC_MODE.
   We can never assume that a condition code mode is safe to reverse unless
   the md tells us so.  */
#ifndef REVERSIBLE_CC_MODE
#define REVERSIBLE_CC_MODE(MODE) 0
#endif

/* Vector mapping INSN_UIDs to cuids.
   The cuids are like uids but increase monotonically always.
   Combine always uses cuids so that it can compare them.
   But actually renumbering the uids, which we used to do,
   proves to be a bad idea because it makes it hard to compare
   the dumps produced by earlier passes with those from later passes.  */

static int *uid_cuid;
static int max_uid_cuid;

/* Get the cuid of an insn.  */

#define INSN_CUID(INSN) \
(INSN_UID (INSN) > max_uid_cuid ? insn_cuid (INSN) : uid_cuid[INSN_UID (INSN)])

/* Maximum register number, which is the size of the tables below.  */

static int combine_max_regno;

/* Record last point of death of (hard or pseudo) register n.  */

static rtx *reg_last_death;

/* Record last point of modification of (hard or pseudo) register n.  */

static rtx *reg_last_set;

/* Record the cuid of the last insn that invalidated memory
   (anything that writes memory, and subroutine calls, but not pushes).  */

static int mem_last_set;

/* Record the cuid of the last CALL_INSN
   so we can tell whether a potential combination crosses any calls.  */

static int last_call_cuid;

/* When `subst' is called, this is the insn that is being modified
   (by combining in a previous insn).  The PATTERN of this insn
   is still the old pattern partially modified and it should not be
   looked at, but this may be used to examine the successors of the insn
   to judge whether a simplification is valid.  */

static rtx subst_insn;

/* This is an insn that belongs before subst_insn, but is not currently
   on the insn chain.  */

static rtx subst_prev_insn;

/* This is the lowest CUID that `subst' is currently dealing with.
   get_last_value will not return a value if the register was set at or
   after this CUID.  If not for this mechanism, we could get confused if
   I2 or I1 in try_combine were an insn that used the old value of a register
   to obtain a new value.  In that case, we might erroneously get the
   new value of the register when we wanted the old one.  */

static int subst_low_cuid;

/* This contains any hard registers that are used in newpat; reg_dead_at_p
   must consider all these registers to be always live.  */

static HARD_REG_SET newpat_used_regs;

/* This is an insn to which a LOG_LINKS entry has been added.  If this
   insn is the earlier than I2 or I3, combine should rescan starting at
   that location.  */

static rtx added_links_insn;

/* Basic block number of the block in which we are performing combines.  */
static int this_basic_block;

/* The next group of arrays allows the recording of the last value assigned
   to (hard or pseudo) register n.  We use this information to see if a
   operation being processed is redundant given a prior operation performed
   on the register.  For example, an `and' with a constant is redundant if
   all the zero bits are already known to be turned off.

   We use an approach similar to that used by cse, but change it in the
   following ways:

   (1) We do not want to reinitialize at each label.
   (2) It is useful, but not critical, to know the actual value assigned
       to a register.  Often just its form is helpful.

   Therefore, we maintain the following arrays:

   reg_last_set_value		the last value assigned
   reg_last_set_label		records the value of label_tick when the
				register was assigned
   reg_last_set_table_tick	records the value of label_tick when a
				value using the register is assigned
   reg_last_set_invalid		set to non-zero when it is not valid
				to use the value of this register in some
				register's value

   To understand the usage of these tables, it is important to understand
   the distinction between the value in reg_last_set_value being valid
   and the register being validly contained in some other expression in the
   table.

   Entry I in reg_last_set_value is valid if it is non-zero, and either
   reg_n_sets[i] is 1 or reg_last_set_label[i] == label_tick.

   Register I may validly appear in any expression returned for the value
   of another register if reg_n_sets[i] is 1.  It may also appear in the
   value for register J if reg_last_set_label[i] < reg_last_set_label[j] or
   reg_last_set_invalid[j] is zero.

   If an expression is found in the table containing a register which may
   not validly appear in an expression, the register is replaced by
   something that won't match, (clobber (const_int 0)).

   reg_last_set_invalid[i] is set non-zero when register I is being assigned
   to and reg_last_set_table_tick[i] == label_tick.  */

/* Record last value assigned to (hard or pseudo) register n.  */

static rtx *reg_last_set_value;

/* Record the value of label_tick when the value for register n is placed in
   reg_last_set_value[n].  */

static int *reg_last_set_label;

/* Record the value of label_tick when an expression involving register n
   is placed in reg_last_set_value.  */

static int *reg_last_set_table_tick;

/* Set non-zero if references to register n in expressions should not be
   used.  */

static char *reg_last_set_invalid;

/* Incremented for each label.  */

static int label_tick;

/* Some registers that are set more than once and used in more than one
   basic block are nevertheless always set in similar ways.  For example,
   a QImode register may be loaded from memory in two places on a machine
   where byte loads zero extend.

   We record in the following array what we know about the nonzero
   bits of a register, specifically which bits are known to be zero.

   If an entry is zero, it means that we don't know anything special.  */

static unsigned HOST_WIDE_INT *reg_nonzero_bits;

/* Mode used to compute significance in reg_nonzero_bits.  It is the largest
   integer mode that can fit in HOST_BITS_PER_WIDE_INT.  */

static enum machine_mode nonzero_bits_mode;

/* Nonzero if we know that a register has some leading bits that are always
   equal to the sign bit.  */

static char *reg_sign_bit_copies;

/* Nonzero when reg_nonzero_bits and reg_sign_bit_copies can be safely used.
   It is zero while computing them and after combine has completed.  This
   former test prevents propagating values based on previously set values,
   which can be incorrect if a variable is modified in a loop.  */

static int nonzero_sign_valid;

/* These arrays are maintained in parallel with reg_last_set_value
   and are used to store the mode in which the register was last set,
   the bits that were known to be zero when it was last set, and the
   number of sign bits copies it was known to have when it was last set.  */

static enum machine_mode *reg_last_set_mode;
static unsigned HOST_WIDE_INT *reg_last_set_nonzero_bits;
static char *reg_last_set_sign_bit_copies;

/* Record one modification to rtl structure
   to be undone by storing old_contents into *where.
   is_int is 1 if the contents are an int.  */

struct undo
{
  struct undo *next;
  int is_int;
  union {rtx r; int i;} old_contents;
  union {rtx *r; int *i;} where;
};

/* Record a bunch of changes to be undone, up to MAX_UNDO of them.
   num_undo says how many are currently recorded.

   storage is nonzero if we must undo the allocation of new storage.
   The value of storage is what to pass to obfree.

   other_insn is nonzero if we have modified some other insn in the process
   of working on subst_insn.  It must be verified too.

   previous_undos is the value of undobuf.undos when we started processing
   this substitution.  This will prevent gen_rtx_combine from re-used a piece
   from the previous expression.  Doing so can produce circular rtl
   structures.  */

struct undobuf
{
  char *storage;
  struct undo *undos;
  struct undo *frees;
  struct undo *previous_undos;
  rtx other_insn;
};

static struct undobuf undobuf;

/* Substitute NEWVAL, an rtx expression, into INTO, a place in some
   insn.  The substitution can be undone by undo_all.  If INTO is already
   set to NEWVAL, do not record this change.  Because computing NEWVAL might
   also call SUBST, we have to compute it before we put anything into
   the undo table.  */

#define SUBST(INTO, NEWVAL)  \
 do { rtx _new = (NEWVAL);					\
      struct undo *_buf;					\
								\
      if (undobuf.frees)					\
	_buf = undobuf.frees, undobuf.frees = _buf->next;	\
      else							\
	_buf = (struct undo *) xmalloc (sizeof (struct undo));	\