/* Reaching definition (RD) flow analysis for AE.
   Adapted from GCC's flow.c.
   Copyright (C) 1987, 1988 Free Software Foundation, Inc.
   Copyright (C) 1989, 1990 James R. Larus (larus@cs.wisc.edu)

   AE and AEC are 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.

   AE and AEC are 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 James R.
   Larus, Computer Sciences Department, University of Wisconsin--Madison,
   1210 West Dayton Street, Madison, WI 53706, USA or to the Free
   Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */


/* $Header: /var/home/larus/AE/AE/RCS/ae-rd.c,v 2.0 90/02/09 17:20:07 larus Exp Locker: larus $ */


#include <stdio.h>
#include "config.h"
#include "rtl.h"
#include "basic-block.h"
#include "regs.h"
#include "ae.h"

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

extern int xmalloc ();
extern void free ();


/* Get the basic block number of an insn.  This info lasts until we
   finish compiling the function. */

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


/* This is where the BLOCK_NUM values are really stored. */

short *uid_block_number;


/* Not used in rd_analysis, but computed by find_basic_blocks. */

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;


/* Either analyze all registers or just the hardware registers (saves
   some space). */

#ifdef RD_SYMBOLIC_REGS
#define MAX_REGNO max_regno
#else
#define MAX_REGNO FIRST_PSEUDO_REGISTER
#endif


/* Maximum UID for an instruction in this function. */

int max_uid = 0;


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

int defset_bytes;
int defset_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 defset describing the definitions that reach basic
   block N.  This info lasts until we finish compiling the function.  */

regset *basic_block_rd_at_start;


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

char *basic_block_drops_in;


/* Element N is depth within loops of basic block number N.
   This info lasts until we finish compiling the function.  */

short *basic_block_loop_depth;


/* Element N is a defset describing the definitions that modify register
   N.  This info lasts until we finish compiling the function.  */

regset *defn_of_reg;


/* Maximum definition number in this function. */

int max_defn_no = 0;


/* Entry N is definition N.  This info lasts until we finish compiling
   the function. */

rtx *n_to_defn;


/* Entry N is the min/max register defined by definition N. */

short *defn_min_reg;
short *defn_max_reg;


/* Entry N is I if instruction N corresponds to definition I and -1
   otherwise.  This info lasts until we finish compiling the function. */

int *insn_to_defn;


/* Use these functions from flow analysis: */
void find_basic_blocks ();
void init_regset_vector ();

/* Use these function from AE: */
int simplejump_p ();
int condjump_p ();
int multiway_jump_p ();
rtx jump_target ();


/* Forward declarations */
static void rd_analysis ();
static void find_reg_defns ();
static void compute_block_gen_kill ();
static void insn_defines_regs ();
void dump_rd_info ();



/* Find basic blocks of the current function and perform reaching
   definition analysis.  F is the first insn of the function and NREGS the
   number of register numbers in use.  */

void
reaching_defn_analysis (f, nregs, file)
     rtx f;
     int nregs;
     FILE *file;
{
  register rtx insn;
  register int i;
  int min_reg, max_reg;

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

  {
    register RTX_CODE prev_code = JUMP_INSN;
    register RTX_CODE code;

    max_defn_no = 0;

    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;
	insn_defines_regs (insn, &min_reg, &max_reg);
	if (min_reg <= max_reg)
	  max_defn_no += 1;
      }
  }

  /* Allocate some tables that last till end of compiling this function
     and some needed only in find_basic_blocks and rd_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 *) oballoc (n_basic_blocks * sizeof (short));
  uid_block_number = (short *) oballoc ((max_uid + 1) * sizeof (short));
  uid_volatile = (char *) alloca (max_uid + 1);
  bzero (uid_volatile, max_uid + 1);

  n_to_defn = (rtx *) oballoc (max_defn_no * sizeof (rtx));
  defn_min_reg = (short *) oballoc (max_defn_no * sizeof (short));
  defn_max_reg = (short *) oballoc (max_defn_no * sizeof (short));
  insn_to_defn = (int *) oballoc ((max_uid + 1) * sizeof (int));
  for (insn = f, i = 0; insn; insn = NEXT_INSN (insn))
    {
      insn_defines_regs (insn, &min_reg, &max_reg);
      if (min_reg <= max_reg)
      {
	insn_to_defn [INSN_UID (insn)] = i;
	defn_min_reg [i] = min_reg;
	defn_max_reg [i] = max_reg;
	n_to_defn [i ++] = insn;
      }
      else
	insn_to_defn [INSN_UID (insn)] = -1;
    }

  find_basic_blocks (f);
  rd_analysis (f, nregs);
  if (file)
    dump_rd_info (file);

  basic_block_drops_in = 0;
}



/* Determine which registers are live at the start of each basic block in
   the function whose first insn is F.  NREGS is the number of registers
   used in F.  We allocate the vector basic_block_rd_at_start and the
   defsets that it points to, and fill them with the data.  defset_size and
   defset_bytes are also set here.  */

static void
rd_analysis (f, nregs)
     rtx f;
     int nregs;
{
  register regset tem;
  int first_pass;
  int changed;
  /* For each basic block, a bitmask of defns reaching end of block. */
  register regset *bb_rd_at_end;
  /* For each basic block, a bitmask of defns reaching entry to a
     successor-block of this block.  If this does not match
     basic_block_rd_at_start, that must be updated. */
  register regset *bb_new_rd_at_start;
  /* For each basic block, a bitmask of defns produced in the block. */
  register regset *bb_gen;
  /* For each basic block, a bitmask of defns killed in the block. */
  register regset *bb_kill;
  register int i;

  struct obstack flow_obstack;

  obstack_init (&flow_obstack);

  max_regno = nregs;

  /* Allocate and zero out data structures that will record the data from
     RD analysis.  */

  defset_size = ((max_defn_no + REGSET_ELT_BITS - 1) / REGSET_ELT_BITS);
  defset_bytes = defset_size * sizeof (*(regset)0);

  basic_block_rd_at_start =
    (regset *) oballoc (n_basic_blocks * sizeof (regset));
  tem = (regset) oballoc (n_basic_blocks * defset_bytes);
  bzero (tem, n_basic_blocks * defset_bytes);
  init_regset_vector (basic_block_rd_at_start, tem, n_basic_blocks,
		      defset_bytes);

  defn_of_reg = (regset *) oballoc (MAX_REGNO * sizeof (regset));
  tem = (regset) oballoc (MAX_REGNO * defset_bytes);
  bzero (tem, MAX_REGNO * defset_bytes);
  init_regset_vector (defn_of_reg, tem, MAX_REGNO, defset_bytes);


  /* Set up regset-vectors used internally within this function. */

  bb_rd_at_end = (regset *) alloca (n_basic_blocks * sizeof (regset));
  /* Don't use alloca since that leads to a crash rather than an error message
     if there isn't enough space.
     Don't use oballoc since we may need to allocate other things during
     this function on the temporary obstack.  */
  tem = (regset) obstack_alloc (&flow_obstack, n_basic_blocks * defset_bytes);
  bzero (tem, n_basic_blocks * defset_bytes);
  init_regset_vector (bb_rd_at_end, tem, n_basic_blocks, defset_bytes);

  bb_new_rd_at_start = (regset *) alloca (n_basic_blocks * sizeof (regset));
  tem = (regset) obstack_alloc (&flow_obstack, n_basic_blocks * defset_bytes);
  bzero (tem, n_basic_blocks * defset_bytes);
  init_regset_vector (bb_new_rd_at_start, tem, n_basic_blocks, defset_bytes);

  bb_gen = (regset *) alloca (n_basic_blocks * sizeof (regset));
  tem = (regset) obstack_alloc (&flow_obstack, n_basic_blocks * defset_bytes);
  bzero (tem, n_basic_blocks * defset_bytes);
  init_regset_vector (bb_gen , tem, n_basic_blocks, defset_bytes);

  bb_kill = (regset *) alloca (n_basic_blocks * sizeof (regset));
  tem = (regset) obstack_alloc (&flow_obstack, n_basic_blocks * defset_bytes);
  bzero (tem, n_basic_blocks * defset_bytes);
  init_regset_vector (bb_kill, tem, n_basic_blocks, defset_bytes);


  /* Find which registers each instruction defines. */
  find_reg_defns (f);

  for (i = 0; i < n_basic_blocks; i ++)
    compute_block_gen_kill (bb_gen [i], bb_kill [i],
			    basic_block_head [i], basic_block_end [i]);

  /* Propagate RD info through the basic blocks in the graph of blocks.

     This is a relaxation process: each time a new definition reaches the
     start of a basic block, we must determine which definitions, as a
     consequence, reach the end of that block.  These definitions reaching the
     start of all the blocks that are successors to that block.  The process
     continues until it reaches a fixed point.  */

  first_pass = 1;
  changed = 1;
  while (changed)
    {
      changed = 0;
      for (i = 0; i < n_basic_blocks; i++)
	{
	  int consider = first_pass;
	  register int j;

	  /* Set CONSIDER if this block needs thinking about at all (that
	     is, if the regs reaching it are not the same as those that
	     reached it when we last thought about it). */
	  for (j = 0; j < defset_size; j++)
	    if (bb_new_rd_at_start [i][j] & ~basic_block_rd_at_start [i][j])
	      {
		consider = 1;
		break;
	      }

	  if (! consider)
	    continue;

	  /* The rd_at_end of this block may change, so another pass
	     will be required after this one.  */
	  changed = 1;

	  bcopy (bb_new_rd_at_start [i], basic_block_rd_at_start [i],
		 defset_bytes);

	  for (j = 0; j < defset_size; j++)
	    /* RDout = (RDin - KILL) + GEN: */
	    bb_rd_at_end [i][j] =
	      (basic_block_rd_at_start [i][j] & ~bb_kill [i][j])
		| bb_gen [i][j];

	  {
	    register rtx end = basic_block_end [i];

	    /* Update the bb_new_rd_at_start's of the block that this
	       one falls through into (if any).*/
	    if ((i + 1 < n_basic_blocks) && basic_block_drops_in [i + 1])
	      {
		register int j;

		for (j = 0; j < defset_size; j++)
		  bb_new_rd_at_start [i + 1][j] |= bb_rd_at_end [i][j];
	      }

	    /* Update the bb_new_rd_at_start's of all the blocks that
	       this one jumps to. */
	    if (GET_CODE (end) == JUMP_INSN
		&& (simplejump_p (end) || condjump_p (end)))
	      {
		register int to_block = BLOCK_NUM (jump_target (end));
		register int j;

		for (j = 0; j < defset_size; j++)
		  bb_new_rd_at_start [to_block][j] |= bb_rd_at_end [i][j];
	      }
	    else if (multiway_jump_p (end))
	      {
		rtx body =  PATTERN (end);
		register int vlen, j, k;

		vlen = XVECLEN (body, 0);
		for (k = 0; k < vlen; k++)
		  {
		    register int to_block =
		      BLOCK_NUM (XEXP (XVECEXP (body, 0, k), 0));

		    for (j = 0; j < defset_size; j++)
		      bb_new_rd_at_start [to_block][j]
			|= bb_rd_at_end [i][j];
		  }
	      }
	  }
#ifdef USE_C_ALLOCA
	  alloca (0);
#endif
	}
      first_pass = 0;
    }
  obstack_free (&flow_obstack, 0);
}



#define SET_REGSET_BIT(rs,bn) \
  rs [bn / REGSET_ELT_BITS] |= 1 << (bn % REGSET_ELT_BITS);


/* For each instruction in the function, record which registers its defines
 in DEFN_OF_REG. */

static void
find_reg_defns (insns)
     rtx insns;
{
  register rtx insn;

  for (insn = insns; insn != NULL; insn = NEXT_INSN (insn))
    {
      register int r;
      register int defn_id = insn_to_defn [INSN_UID (insn)];

      if (defn_id != -1)
	for (r = defn_min_reg [defn_id]; r <= defn_max_reg [defn_id]; r++)
	  SET_REGSET_BIT (defn_of_reg [r], defn_id);
    }
}


static void
compute_block_gen_kill (gen, kill, first, last)
     register regset gen, kill;
     rtx first;
     rtx last;
{
  register rtx insn;

  for (insn = first; PREV_INSN (insn) != last ; insn = NEXT_INSN (insn))
    {
      register int defn_id = insn_to_defn [INSN_UID (insn)];
      register int r, i;

      if (defn_id != -1)
	{
	  for (r = defn_min_reg [defn_id]; r <= defn_max_reg [defn_id]; r++)
	    for (i = 0; i < defset_size; i++)
	      kill [i] |= defn_of_reg [r][i];

	  SET_REGSET_BIT (gen, defn_id);
	}
    }
}


static void find_def_range ();

static void
insn_defines_regs (insn, min_reg, max_reg)
     rtx insn;
     int *min_reg, *max_reg;
{
  /* Initially, insn does not define any regs. */
  *min_reg = -1, *max_reg = -2;

  if (!INSN_DELETED_P (insn)
      && (GET_CODE (insn) == INSN || GET_CODE (insn) == CALL_INSN))
      {
	register rtx x = PATTERN (insn);
	register RTX_CODE code = GET_CODE (x);

	if (code == SET || code == CLOBBER)
	  find_def_range (x, insn, min_reg, max_reg);
	else if (code == PARALLEL)
	  {
	    register int i;
	    for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
	      {
		code = GET_CODE (XVECEXP (x, 0, i));
		if (code == SET || code == CLOBBER)
		  find_def_range (XVECEXP (x, 0, i), insn, min_reg, max_reg);
	      }
	  }
      }
}


/* Process a single SET rtx, X.  */

static void
find_def_range (x, insn, min_reg, max_reg)
     rtx x;
     rtx insn;
     int *min_reg, *max_reg;
{
  register int regno;
  register rtx reg = SET_DEST (x);
  int subreg_p = 0;

  if (reg == 0)
    return;

  if (GET_CODE (reg) == STRICT_LOW_PART)
    reg = XEXP (reg, 0);

  if (GET_CODE (reg) == SUBREG || GET_CODE (reg) == ZERO_EXTRACT
      || GET_CODE (reg) == SIGN_EXTRACT)
    {
      /* Modifying just one hardware register of a multi-reg value or
	 just a byte field of a register does not mean the value from before
	 this insn is now dead. */
      if (REG_SIZE (SUBREG_REG (reg)) > REG_SIZE (reg))
	subreg_p = 1;

      reg = SUBREG_REG (reg);
    }

  if (GET_CODE (reg) == REG
      && (regno = REGNO (reg), regno != FRAME_POINTER_REGNUM)
      && regno != ARG_POINTER_REGNUM)
    {
      *min_reg = *max_reg = regno;

      /* A hard reg in a wide mode may really be multiple registers. */
      if (regno < FIRST_PSEUDO_REGISTER)
	{
	  if (regno == STACK_POINTER_REGNUM)
	    return;

	  *max_reg += HARD_REGNO_NREGS (regno, GET_MODE (reg)) - 1;
	}
    }
}



/* Return a list of the definitions of REG reaching INSN. */

list
defns_reaching_insn (insn, reg)
     register rtx insn, reg;
{
  int regno = REGNO (reg);
  int block_no = BLOCK_NUM (insn);
  register rtx block_end = basic_block_end [block_no];
  register regset defns = (regset) alloca (defset_bytes);
  register rtx insns;
  register int i, j;
  list rds = NULL;

  bcopy (basic_block_rd_at_start [block_no], defns, defset_bytes);

  for (insns = basic_block_head [block_no];
       /* Peephole may delete insn (which may have been block end) */
       insns != insn && insns != block_end && insns != NULL;
       insns = NEXT_INSN (insns))
    {
      register int defn_id = insn_to_defn [INSN_UID (insns)];
      register int r, i;

      if (defn_id != -1)
	{
	  for (r = defn_min_reg [defn_id]; r <= defn_max_reg [defn_id]; r++)
	    for (i = 0; i < defset_size; i++)
	      defns [i] &= ~defn_of_reg [r][i];

	  SET_REGSET_BIT (defns, defn_id);
	}
    }

  for (i = 0; i < defset_size; i++)
    {
      /* Only want defns of register REGNO */
      register int x = defns [i] & defn_of_reg [regno][i];

      for (j = 0; x != 0 && j < REGSET_ELT_BITS; j ++)
	{
	  if (x & 1)
	    {
	      rtx def_insn = n_to_defn [i * REGSET_ELT_BITS + j];

	      if (def_insn)
		rds = cons (def_insn, rds);
	    }
	  x = x >> 1;
	}
    }

  return rds;
}



/* Write information about defns and basic blocks into FILE.
   This is part of making a debugging dump.  */

void
dump_rd_info (file)
     FILE *file;
{
  register int i, defno;

  fprintf (file, "%d insn.\n", max_defn_no);

  fprintf (file, "\n%d basic blocks.\n", n_basic_blocks);
  for (i = 0; i < n_basic_blocks; i ++)
    {
      register rtx head, jump;
      fprintf (file, "\nBasic block %d: first insn %d, last %d.\n",
	       i,
	       INSN_UID (basic_block_head [i]),
	       INSN_UID (basic_block_end [i]));

      /* The control flow graph's storage is freed when flow_analysis
	 returns. Don't try to print it if it is gone.  */
      if (basic_block_drops_in)
	{
	  fprintf (file, "Reached from blocks: ");
	  head = basic_block_head [i];
	  if (GET_CODE (head) == CODE_LABEL)
	    for (jump = LABEL_REFS (head);
		 jump != head;
		 jump = LABEL_NEXTREF (jump))
	      {
		register int from_block = BLOCK_NUM (CONTAINING_INSN (jump));
		fprintf (file, " %d", from_block);
	      }
	  if (basic_block_drops_in [i])
	    fprintf (file, " previous");
	}

      fprintf (file, "\nDefns reaching start:");
      for (defno = 0; defno < max_defn_no; defno ++)
	{
	  register int offset = defno / REGSET_ELT_BITS;
	  register int bit = 1 << (defno % REGSET_ELT_BITS);

	  if (basic_block_rd_at_start [i][offset] & bit)
	    fprintf (file, " %d", INSN_UID (n_to_defn [defno]));
	}
      fprintf (file, "\n");
    }

  fprintf (file, "%d registers.\n", MAX_REGNO);
  for (i = 0; i < MAX_REGNO; i ++)
    {
      fprintf (file, "Register %d defined by: ", i);
      for (defno = 0; defno < max_defn_no; defno ++)
	{
	  register int offset = defno / REGSET_ELT_BITS;
	  register int bit = 1 << (defno % REGSET_ELT_BITS);

	  if (defn_of_reg [i][offset] & bit)
	    fprintf (file, " %d", INSN_UID (n_to_defn [defno]));
	}
      fprintf (file, "\n");
    }

  fprintf (file, "\n");
}
