flow.c

GCC编译器源代码

/* Data flow analysis for GNU compiler.
   Copyright (C) 1987, 88, 92-96, 1997 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 file contains the data flow analysis pass of the compiler.
   It computes data flow information
   which tells combine_instructions which insns to consider combining
   and controls register allocation.

   Additional data flow information that is too bulky to record
   is generated during the analysis, and is used at that time to
   create autoincrement and autodecrement addressing.

   The first step is dividing the function into basic blocks.
   find_basic_blocks does this.  Then life_analysis determines
   where each register is live and where it is dead.

   ** find_basic_blocks **

   find_basic_blocks divides the current function's rtl
   into basic blocks.  It records the beginnings and ends of the
   basic blocks in the vectors basic_block_head and basic_block_end,
   and the number of blocks in n_basic_blocks.

   find_basic_blocks also finds any unreachable loops
   and deletes them.

   ** life_analysis **

   life_analysis is called immediately after find_basic_blocks.
   It uses the basic block information to determine where each
   hard or pseudo register is live.

   ** live-register info **

   The information about where each register is live is in two parts:
   the REG_NOTES of insns, and the vector basic_block_live_at_start.

   basic_block_live_at_start has an element for each basic block,
   and the element is a bit-vector with a bit for each hard or pseudo
   register.  The bit is 1 if the register is live at the beginning
   of the basic block.

   Two types of elements can be added to an insn's REG_NOTES.  
   A REG_DEAD note is added to an insn's REG_NOTES for any register
   that meets both of two conditions:  The value in the register is not
   needed in subsequent insns and the insn does not replace the value in
   the register (in the case of multi-word hard registers, the value in
   each register must be replaced by the insn to avoid a REG_DEAD note).

   In the vast majority of cases, an object in a REG_DEAD note will be
   used somewhere in the insn.  The (rare) exception to this is if an
   insn uses a multi-word hard register and only some of the registers are
   needed in subsequent insns.  In that case, REG_DEAD notes will be
   provided for those hard registers that are not subsequently needed.
   Partial REG_DEAD notes of this type do not occur when an insn sets
   only some of the hard registers used in such a multi-word operand;
   omitting REG_DEAD notes for objects stored in an insn is optional and
   the desire to do so does not justify the complexity of the partial
   REG_DEAD notes.

   REG_UNUSED notes are added for each register that is set by the insn
   but is unused subsequently (if every register set by the insn is unused
   and the insn does not reference memory or have some other side-effect,
   the insn is deleted instead).  If only part of a multi-word hard
   register is used in a subsequent insn, REG_UNUSED notes are made for
   the parts that will not be used.

   To determine which registers are live after any insn, one can
   start from the beginning of the basic block and scan insns, noting
   which registers are set by each insn and which die there.

   ** Other actions of life_analysis **

   life_analysis sets up the LOG_LINKS fields of insns because the
   information needed to do so is readily available.

   life_analysis deletes insns whose only effect is to store a value
   that is never used.

   life_analysis notices cases where a reference to a register as
   a memory address can be combined with a preceding or following
   incrementation or decrementation of the register.  The separate
   instruction to increment or decrement is deleted and the address
   is changed to a POST_INC or similar rtx.

   Each time an incrementing or decrementing address is created,
   a REG_INC element is added to the insn's REG_NOTES list.

   life_analysis fills in certain vectors containing information about
   register usage: reg_n_refs, reg_n_deaths, reg_n_sets, reg_live_length,
   reg_n_calls_crosses and reg_basic_block.  */

#include "config.h"
#include <stdio.h>
#include "rtl.h"
#include "basic-block.h"
#include "insn-config.h"
#include "regs.h"
#include "hard-reg-set.h"
#include "flags.h"
#include "output.h"
#include "except.h"

#include "obstack.h"
#define obstack_chunk_alloc xmalloc
#define obstack_chunk_free free

/* The contents of the current function definition are allocated
   in this obstack, and all are freed at the end of the function.
   For top-level functions, this is temporary_obstack.
   Separate obstacks are made for nested functions.  */

extern struct obstack *function_obstack;

/* List of labels that must never be deleted.  */
extern rtx forced_labels;

/* Get the basic block number of an insn.
   This info should not be expected to remain available
   after the end of life_analysis.  */

/* This is the limit of the allocated space in the following two arrays.  */

static int max_uid_for_flow;

#define BLOCK_NUM(INSN)  uid_block_number[INSN_UID (INSN)]

/* This is where the BLOCK_NUM values are really stored.
   This is set up by find_basic_blocks and used there and in life_analysis,
   and then freed.  */

static int *uid_block_number;

/* INSN_VOLATILE (insn) is 1 if the insn refers to anything volatile.  */

#define INSN_VOLATILE(INSN) uid_volatile[INSN_UID (INSN)]
static char *uid_volatile;

/* Number of basic blocks in the current function.  */

int n_basic_blocks;

/* Maximum register number used in this function, plus one.  */

int max_regno;

/* Maximum number of SCRATCH rtx's used in any basic block of this
   function.  */

int max_scratch;

/* Number of SCRATCH rtx's in the current block.  */

static int num_scratch;

/* Indexed by n, giving various register information */

reg_info *reg_n_info;

/* Element N is the next insn that uses (hard or pseudo) register number N
   within the current basic block; or zero, if there is no such insn.
   This is valid only during the final backward scan in propagate_block.  */

static rtx *reg_next_use;

/* Size of a regset for the current function,
   in (1) bytes and (2) elements.  */

int regset_bytes;
int regset_size;

/* Element N is first insn in basic block N.
   This info lasts until we finish compiling the function.  */

rtx *basic_block_head;

/* Element N is last insn in basic block N.
   This info lasts until we finish compiling the function.  */

rtx *basic_block_end;

/* Element N is a regset describing the registers live
   at the start of basic block N.
   This info lasts until we finish compiling the function.  */

regset *basic_block_live_at_start;

/* Regset of regs live when calls to `setjmp'-like functions happen.  */

regset regs_live_at_setjmp;

/* List made of EXPR_LIST rtx's which gives pairs of pseudo registers
   that have to go in the same hard reg.
   The first two regs in the list are a pair, and the next two
   are another pair, etc.  */
rtx regs_may_share;

/* Element N is nonzero if control can drop into basic block N
   from the preceding basic block.  Freed after life_analysis.  */

static char *basic_block_drops_in;

/* Element N is depth within loops of the last insn in basic block number N.
   Freed after life_analysis.  */

static short *basic_block_loop_depth;

/* Element N nonzero if basic block N can actually be reached.
   Vector exists only during find_basic_blocks.  */

static char *block_live_static;

/* Depth within loops of basic block being scanned for lifetime analysis,
   plus one.  This is the weight attached to references to registers.  */

static int loop_depth;

/* During propagate_block, this is non-zero if the value of CC0 is live.  */

static int cc0_live;

/* During propagate_block, this contains the last MEM stored into.  It
   is used to eliminate consecutive stores to the same location.  */

static rtx last_mem_set;

/* Set of registers that may be eliminable.  These are handled specially
   in updating regs_ever_live.  */

static HARD_REG_SET elim_reg_set;

/* Forward declarations */
static void find_basic_blocks		PROTO((rtx, rtx));
static void mark_label_ref		PROTO((rtx, rtx, int));
static void life_analysis		PROTO((rtx, int));
void allocate_for_life_analysis		PROTO((void));
void init_regset_vector			PROTO((regset *, int, struct obstack *));
void free_regset_vector			PROTO((regset *, int));
static void propagate_block		PROTO((regset, rtx, rtx, int, 
					       regset, int));
static rtx flow_delete_insn		PROTO((rtx));
static int insn_dead_p			PROTO((rtx, regset, int));
static int libcall_dead_p		PROTO((rtx, regset, rtx, rtx));
static void mark_set_regs		PROTO((regset, regset, rtx,
					       rtx, regset));
static void mark_set_1			PROTO((regset, regset, rtx,
					       rtx, regset));
static void find_auto_inc		PROTO((regset, rtx, rtx));
static void mark_used_regs		PROTO((regset, regset, rtx, int, rtx));
static int try_pre_increment_1		PROTO((rtx));
static int try_pre_increment		PROTO((rtx, rtx, HOST_WIDE_INT));
static rtx find_use_as_address		PROTO((rtx, rtx, HOST_WIDE_INT));
void dump_flow_info			PROTO((FILE *));

/* Find basic blocks of the current function and perform data flow analysis.
   F is the first insn of the function and NREGS the number of register numbers
   in use.  */

void
flow_analysis (f, nregs, file)
     rtx f;
     int nregs;
     FILE *file;
{
  register rtx insn;
  register int i;
  rtx nonlocal_label_list = nonlocal_label_rtx_list ();

#ifdef ELIMINABLE_REGS
  static struct {int from, to; } eliminables[] = ELIMINABLE_REGS;
#endif

  /* Record which registers will be eliminated.  We use this in
     mark_used_regs.  */

  CLEAR_HARD_REG_SET (elim_reg_set);

#ifdef ELIMINABLE_REGS
  for (i = 0; i < sizeof eliminables / sizeof eliminables[0]; i++)
    SET_HARD_REG_BIT (elim_reg_set, eliminables[i].from);
#else
  SET_HARD_REG_BIT (elim_reg_set, FRAME_POINTER_REGNUM);
#endif

  /* Count the basic blocks.  Also find maximum insn uid value used.  */

  {
    register RTX_CODE prev_code = JUMP_INSN;
    register RTX_CODE code;

    max_uid_for_flow = 0;

    for (insn = f, i = 0; insn; insn = NEXT_INSN (insn))
      {
	code = GET_CODE (insn);
	if (INSN_UID (insn) > max_uid_for_flow)
	  max_uid_for_flow = INSN_UID (insn);
	if (code == CODE_LABEL
	    || (GET_RTX_CLASS (code) == 'i'
		&& (prev_code == JUMP_INSN
		    || (prev_code == CALL_INSN
			&& nonlocal_label_list != 0)
		    || prev_code == BARRIER)))
	  i++;

	if (code == CALL_INSN && find_reg_note (insn, REG_RETVAL, NULL_RTX))
	  code = INSN;

	if (code != NOTE)
	  prev_code = code;
      }
  }

#ifdef AUTO_INC_DEC
  /* Leave space for insns we make in some cases for auto-inc.  These cases
     are rare, so we don't need too much space.  */
  max_uid_for_flow += max_uid_for_flow / 10;
#endif

  /* Allocate some tables that last till end of compiling this function
     and some needed only in find_basic_blocks and life_analysis.  */

  n_basic_blocks = i;
  basic_block_head = (rtx *) oballoc (n_basic_blocks * sizeof (rtx));
  basic_block_end = (rtx *) oballoc (n_basic_blocks * sizeof (rtx));
  basic_block_drops_in = (char *) alloca (n_basic_blocks);
  basic_block_loop_depth = (short *) alloca (n_basic_blocks * sizeof (short));
  uid_block_number
    = (int *) alloca ((max_uid_for_flow + 1) * sizeof (int));
  uid_volatile = (char *) alloca (max_uid_for_flow + 1);
  bzero (uid_volatile, max_uid_for_flow + 1);

  find_basic_blocks (f, nonlocal_label_list);
  life_analysis (f, nregs);
  if (file)
    dump_flow_info (file);

  basic_block_drops_in = 0;
  uid_block_number = 0;
  basic_block_loop_depth = 0;
}

/* Find all basic blocks of the function whose first insn is F.
   Store the correct data in the tables that describe the basic blocks,
   set up the chains of references for each CODE_LABEL, and
   delete any entire basic blocks that cannot be reached.

   NONLOCAL_LABEL_LIST is the same local variable from flow_analysis.  */

static void
find_basic_blocks (f, nonlocal_label_list)
     rtx f, nonlocal_label_list;
{
  register rtx insn;
  register int i;
  register char *block_live = (char *) alloca (n_basic_blocks);
  register char *block_marked = (char *) alloca (n_basic_blocks);
  /* List of label_refs to all labels whose addresses are taken
     and used as data.  */
  rtx label_value_list;
  int label_value_list_marked_live;
  rtx x, note;
  enum rtx_code prev_code, code;
  int depth, pass;

  pass = 1;
 restart:

  label_value_list = 0;
  label_value_list_marked_live = 0;
  block_live_static = block_live;
  bzero (block_live, n_basic_blocks);
  bzero (block_marked, n_basic_blocks);

  /* Initialize with just block 0 reachable and no blocks marked.  */
  if (n_basic_blocks > 0)
    block_live[0] = 1;

  /* Initialize the ref chain of each label to 0.  Record where all the
     blocks start and end and their depth in loops.  For each insn, record
     the block it is in.   Also mark as reachable any blocks headed by labels
     that must not be deleted.  */