/* Data flow analysis 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 modifyit under the terms of the GNU General Public License as published bythe 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 ofMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See theGNU General Public License for more details.You should have received a copy of the GNU General Public Licensealong with GNU CC; see the file COPYING.  If not, write tothe Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, 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.   To each insn's REG_NOTES is added an element for each register   that is live before the insn or set by the insn, but is dead   after the insn.   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 <stdio.h>#include "config.h"#include "rtl.h"#include "basic-block.h"#include "regs.h"#include "hard-reg-set.h"#include "flags.h"#include "obstack.h"#define obstack_chunk_alloc xmalloc#define obstack_chunk_free freeextern int xmalloc ();extern void free ();/* Get the basic block number of an insn.   This info should not be expected to remain available   after the end of life_analysis.  */#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 short *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;/* Indexed by n, gives number of basic block that  (REG n) is used in.   If the value is REG_BLOCK_GLOBAL (-2),   it means (REG n) is used in more than one basic block.   REG_BLOCK_UNKNOWN (-1) means it hasn't been seen yet so we don't know.   This information remains valid for the rest of the compilation   of the current function; it is used to control register allocation.  */short *reg_basic_block;/* Indexed by n, gives number of times (REG n) is used or set, each   weighted by its loop-depth.   This information remains valid for the rest of the compilation   of the current function; it is used to control register allocation.  */short *reg_n_refs;/* Indexed by n, gives number of times (REG n) is set.   This information remains valid for the rest of the compilation   of the current function; it is used to control register allocation.  */short *reg_n_sets;/* Indexed by N, gives number of places register N dies.   This information remains valid for the rest of the compilation   of the current function; it is used to control register allocation.  */short *reg_n_deaths;/* Indexed by N, gives 1 if that reg is live across any CALL_INSNs.   This information remains valid for the rest of the compilation   of the current function; it is used to control register allocation.  */int *reg_n_calls_crossed;/* Indexed by N, gives the uid of the first insn that mentions reg N,   provided that reg is local to one basic block.   The value here is undefined otherwise.  */rtx *reg_first_use;/* Total number of instructions at which (REG n) is live.   The larger this is, the less priority (REG n) gets for   allocation in a real register.   This information remains valid for the rest of the compilation   of the current function; it is used to control register allocation.   local-alloc.c may alter this number to change the priority.   Negative values are special.   -1 is used to mark a pseudo reg which has a constant or memory equivalent   and is used infrequently enough that it should not get a hard register.   -2 is used to mark a pseudo reg for a parameter, when a frame pointer   is not required.  global-alloc.c makes an allocno for this but does   not try to assign a hard register to it.  */int *reg_live_length;/* 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;/* 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 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;/* Define AUTO_INC_DEC if machine has any kind of incrementing   or decrementing addressing.  */#ifdef HAVE_PRE_DECREMENT#define AUTO_INC_DEC#endif#ifdef HAVE_PRE_INCREMENT#define AUTO_INC_DEC#endif#ifdef HAVE_POST_DECREMENT#define AUTO_INC_DEC#endif#ifdef HAVE_POST_INCREMENT#define AUTO_INC_DEC#endif/* Forward declarations */static void find_basic_blocks ();static void life_analysis ();static void mark_label_ref ();void allocate_for_life_analysis (); /* Used also in stupid_life_analysis */static void init_regset_vector ();static void propagate_block ();static void mark_set_regs ();static void mark_used_regs ();static int insn_dead_p ();static int libcall_dead_p ();static int try_pre_increment ();static int try_pre_increment_1 ();static rtx find_use_as_address ();void dump_flow_info ();/* 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.  */voidflow_analysis (f, nregs, file)     rtx f;     int nregs;     FILE *file;{  register rtx insn;  register int i;  register int max_uid = 0;  /* Count the basic blocks.  Also find maximum insn uid value used.  */  {    register RTX_CODE prev_code = JUMP_INSN;    register RTX_CODE code;    for (insn = f, i = 0; insn; insn = NEXT_INSN (insn))      {	code = GET_CODE (insn);	if (INSN_UID (insn) > max_uid)	  max_uid = INSN_UID (insn);	if (code == CODE_LABEL	    || (prev_code != INSN && prev_code != CALL_INSN		&& prev_code != CODE_LABEL		&& (code == INSN || code == CALL_INSN || code == JUMP_INSN)))	  i++;	if (code != NOTE)	  prev_code = code;      }  }  /* 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 = (short *) alloca ((max_uid + 1) * sizeof (short));  uid_volatile = (char *) alloca (max_uid + 1);  bzero (uid_volatile, max_uid + 1);  find_basic_blocks (f);  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.  */static voidfind_basic_blocks (f)     rtx f;{  register rtx insn;  register int i;  /* 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.  */  {    register RTX_CODE prev_code = JUMP_INSN;    register RTX_CODE code;    int depth = 1;    for (insn = f, i = -1; insn; insn = NEXT_INSN (insn))      {	code = GET_CODE (insn);	if (code == NOTE)	  {	    if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)	      depth++;	    else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END)	      depth--;	  }	else if (code == CODE_LABEL		 || (prev_code != INSN && prev_code != CALL_INSN		     && prev_code != CODE_LABEL		     && (code == INSN || code == CALL_INSN || code == JUMP_INSN)))	  {	    basic_block_head[++i] = insn;	    basic_block_end[i] = insn;	    basic_block_loop_depth[i] = depth;	    if (code == CODE_LABEL)	      LABEL_REFS (insn) = insn;	  }	else if (code == INSN || code == CALL_INSN || code == JUMP_INSN)	  basic_block_end[i] = insn;	BLOCK_NUM (insn) = i;	if (code != NOTE)	  prev_code = code;      }    if (i + 1 != n_basic_blocks)      abort ();  }  /* Record which basic blocks control can drop in to.  */  {    register int i;    for (i = 0; i < n_basic_blocks; i++)      {	register rtx insn = PREV_INSN (basic_block_head[i]);	/* TEMP1 is used to avoid a bug in Sequent's compiler.  */	register int temp1;	while (insn && GET_CODE (insn) == NOTE)	  insn = PREV_INSN (insn);	temp1 = insn && GET_CODE (insn) != BARRIER;	basic_block_drops_in[i] = temp1;      }  }  /* Now find which basic blocks can actually be reached     and put all jump insns' LABEL_REFS onto the ref-chains     of their target labels.  */  if (n_basic_blocks > 0)    {      register char *block_live = (char *) alloca (n_basic_blocks);      register char *block_marked = (char *) alloca (n_basic_blocks);      int something_marked = 1;      /* Initialize with just block 0 reachable and no blocks marked.  */      bzero (block_live, n_basic_blocks);      bzero (block_marked, n_basic_blocks);      block_live[0] = 1;      block_live_static = block_live;      /* Pass over all blocks, marking each block that is reachable	 and has not yet been marked.