combine.c

这是完整的gcc源代码

/* Optimize by combining instructions for GNU compiler.
   Copyright (C) 1987, 1988 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 1, 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, 675 Mass Ave, Cambridge, MA 02139, 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.

   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.

   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 <stdio.h>

#include "config.h"
#include "rtl.h"
#include "flags.h"
#include "regs.h"
#include "basic-block.h"
#include "insn-config.h"
#include "recog.h"

#define max(A,B) ((A) > (B) ? (A) : (B))
#define min(A,B) ((A) < (B) ? (A) : (B))

/* 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;
static int distrib_attempts;

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

static int combine_merges;
static int distrib_merges_1, distrib_merges_2;

/* 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;
static int distrib_successes;

/* Totals over entire compilation.  */

static int total_attempts, total_merges, total_extras, total_successes;
static int total_distrib_attempts, total_distrib_merges_1, total_distrib_merges_2, total_distrib_successes;


/* Vector mapping INSN_UIDs to cuids.
   The cuids are like uids but increase monononically 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;

/* Get the cuid of an insn.  */

#define INSN_CUID(INSN) (uid_cuid[INSN_UID (INSN)])


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

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;

/* 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
{
  rtx *where;
  rtx old_contents;
  int is_int;
};

struct undo_int
{
  int *where;
  int old_contents;
  int is_int;
};

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

#define MAX_UNDO 10

struct undobuf
{
  int num_undo;
  char *storage;
  struct undo undo[MAX_UNDO];
};

static struct undobuf undobuf;

/* Number of times the pseudo being substituted for
   was found and replaced.  */

static int n_occurrences;

static void move_deaths ();
static void move_deaths_2 ();
void remove_death ();
static void record_dead_and_set_regs ();
int regno_dead_p ();
static int use_crosses_set_p ();
static int try_combine ();
static rtx try_distrib ();
static rtx subst ();
static void undo_all ();
static void copy_substitutions ();
static void add_links ();
static void remove_links ();
static void add_incs ();
static int adjacent_insns_p ();
static int check_asm_operands ();
static rtx simplify_and_const_int ();
static rtx gen_lowpart_for_combine ();
static void simplify_set_cc0_and ();

/* Main entry point for combiner.  F is the first insn of the function.
   NREGS is the first unused pseudo-reg number.  */

void
combine_instructions (f, nregs)
     rtx f;
     int nregs;
{
  register rtx insn;
  register int i;
  register rtx links, nextlinks;
  rtx prev;

  combine_attempts = 0;
  combine_merges = 0;
  combine_extras = 0;
  combine_successes = 0;
  distrib_attempts = 0;
  distrib_merges_1 = 0;
  distrib_merges_2 = 0;
  distrib_successes = 0;

  reg_last_death = (rtx *) alloca (nregs * sizeof (rtx));
  reg_last_set = (rtx *) alloca (nregs * sizeof (rtx));
  bzero (reg_last_death, nregs * sizeof (rtx));
  bzero (reg_last_set, nregs * sizeof (rtx));

  init_recog ();

  /* Compute maximum uid value so uid_cuid can be allocated.  */

  for (insn = f, i = 0; insn; insn = NEXT_INSN (insn))
    if (INSN_UID (insn) > i)
      i = INSN_UID (insn);

  uid_cuid = (int *) alloca ((i + 1) * sizeof (int));

  /* Compute the mapping from uids to cuids.
     Cuids are numbers assigned to insns, like uids,
     except that cuids increase monotonically through the code.  */

  for (insn = f, i = 0; insn; insn = NEXT_INSN (insn))
    INSN_CUID (insn) = ++i;

  /* Now scan all the insns in forward order.  */

  last_call_cuid = 0;
  mem_last_set = 0;
  prev = 0;

  for (insn = f; insn; insn = NEXT_INSN (insn))
    {
      if (GET_CODE (insn) == INSN
	  || GET_CODE (insn) == CALL_INSN
	  || GET_CODE (insn) == JUMP_INSN)
	{
	retry:
	  /* Try this insn with each insn it links back to.  */

	  for (links = LOG_LINKS (insn); links; links = XEXP (links, 1))
	    if (try_combine (insn, XEXP (links, 0), 0))
	      goto retry;

	  /* Try each sequence of three linked insns ending with this one.  */

	  for (links = LOG_LINKS (insn); links; links = XEXP (links, 1))
	    if (GET_CODE (XEXP (links, 0)) != NOTE)
	      for (nextlinks = LOG_LINKS (XEXP (links, 0)); nextlinks;
		   nextlinks = XEXP (nextlinks, 1))
		if (try_combine (insn, XEXP (links, 0), XEXP (nextlinks, 0)))
		  goto retry;

	  /* Try to combine a jump insn that uses CC0
	     with a preceding insn that sets CC0, and maybe with its
	     logical predecessor as well.
	     This is how we make decrement-and-branch insns.
	     We need this special code because data flow connections
	     via CC0 do not get entered in LOG_LINKS.  */

	  if (GET_CODE (insn) == JUMP_INSN
	      && prev != 0
	      && GET_CODE (prev) == INSN
	      && GET_CODE (PATTERN (prev)) == SET
	      && GET_CODE (SET_DEST (PATTERN (prev))) == CC0)
	    {
	      if (try_combine (insn, prev, 0))
		goto retry;

	      if (GET_CODE (prev) != NOTE)
		for (nextlinks = LOG_LINKS (prev); nextlinks;
		     nextlinks = XEXP (nextlinks, 1))
		  if (try_combine (insn, prev, XEXP (nextlinks, 0)))
		    goto retry;
	    }

	  /* Try to apply the distributive law to this insn
	     and two insns that compute the operands of this one.  */
	  for (links = LOG_LINKS (insn); links; links = XEXP (links, 1))
	    if (GET_CODE (XEXP (links, 0)) != NOTE)
	      for (nextlinks = XEXP (links, 1); nextlinks; nextlinks = XEXP (nextlinks, 1))
		if (GET_CODE (XEXP (nextlinks, 0)) != NOTE)
		  {
		    rtx try_from = 0;

		    if (GET_CODE (PATTERN (XEXP (links, 0))) == SET
			&& find_reg_note (insn, REG_DEAD, SET_DEST (PATTERN (XEXP (links, 0))))
			&& GET_CODE (PATTERN (XEXP (nextlinks, 0))) == SET
			&& find_reg_note (insn, REG_DEAD, SET_DEST (PATTERN (XEXP (nextlinks, 0)))))
		      try_from = try_distrib (insn, XEXP (links, 0), XEXP (nextlinks, 0));
		    if (try_from != 0)
		      {
			insn = try_from;
			goto retry;
		      }
		  }
#if 0
/* Turned off because on 68020 it takes four insns to make
   something like (a[b / 32] & (1 << (31 - (b % 32)))) != 0
   that could actually be optimized, and that's an unlikely piece of code.  */
	  /* If an insn gets or sets a bit field, try combining it
	     with two different insns whose results it uses.  */
	  if (GET_CODE (insn) == INSN
	      && GET_CODE (PATTERN (insn)) == SET
	      && (GET_CODE (SET_DEST (PATTERN (insn))) == ZERO_EXTRACT
		  || GET_CODE (SET_DEST (PATTERN (insn))) == SIGN_EXTRACT
		  || GET_CODE (SET_SRC (PATTERN (insn))) == ZERO_EXTRACT
		  || GET_CODE (SET_SRC (PATTERN (insn))) == SIGN_EXTRACT))
	    {
	      for (links = LOG_LINKS (insn); links; links = XEXP (links, 1))
		if (GET_CODE (XEXP (links, 0)) != NOTE)
		  for (nextlinks = XEXP (links, 1); nextlinks;
		       nextlinks = XEXP (nextlinks, 1))
		    if (try_combine (insn, XEXP (links, 0), XEXP (nextlinks, 0)))
		      goto retry;
	    }
#endif
	  if (GET_CODE (insn) != NOTE)
	    record_dead_and_set_regs (insn);
	  prev = insn;
	}
      else if (GET_CODE (insn) != NOTE)
	prev = 0;
    }
  total_attempts += combine_attempts;
  total_merges += combine_merges;
  total_extras += combine_extras;
  total_successes += combine_successes;
}

/* Try to combine the insns I1 and I2 into I3.
   Here I1 appears earlier than I2, which is earlier than I3.
   I1 can be zero; then we combine just I2 into I3.
 
   Return 1 if successful; if that happens, I1 and I2 are pseudo-deleted
   by turning them into NOTEs, and I3 is modified.
   Return 0 if the combination does not work.  Then nothing is changed.  */

static int
try_combine (i3, i2, i1)
     register rtx i3, i2, i1;
{
  register rtx newpat;
  int added_sets_1 = 0;
  int added_sets_2 = 0;
  int total_sets;
  int i2_is_used;
  register rtx link;
  int insn_code_number;
  rtx i2dest, i2src;
  rtx i1dest, i1src;
  int maxreg;
  rtx temp;
  int i;

  combine_attempts++;

  /* Don't combine with something already used up by combination.  */

  if (GET_CODE (i2) == NOTE