Subversion Repositories scarts

/* Perform branch target register load optimizations.

   Copyright (C) 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.

This file is part of GCC.

GCC 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.

GCC 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 GCC; see the file COPYING.  If not, write to the Free

Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA

02110-1301, USA.  */

#include "config.h"

#include "system.h"

#include "coretypes.h"

#include "tm.h"

#include "rtl.h"

#include "hard-reg-set.h"

#include "regs.h"

#include "fibheap.h"

#include "output.h"

#include "target.h"

#include "expr.h"

#include "flags.h"

#include "insn-attr.h"

#include "function.h"

#include "except.h"

#include "tm_p.h"

#include "toplev.h"

#include "tree-pass.h"

/* Target register optimizations - these are performed after reload.  */

typedef struct btr_def_group_s

{

  struct btr_def_group_s *next;

  rtx src;

  struct btr_def_s *members;

} *btr_def_group;

typedef struct btr_user_s

{

  struct btr_user_s *next;

  basic_block bb;

  int luid;

  rtx insn;

  /* If INSN has a single use of a single branch register, then

     USE points to it within INSN.  If there is more than

     one branch register use, or the use is in some way ambiguous,

     then USE is NULL.  */

  rtx use;

  int n_reaching_defs;

  int first_reaching_def;

  char other_use_this_block;

} *btr_user;

/* btr_def structs appear on three lists:

     1. A list of all btr_def structures (head is

        ALL_BTR_DEFS, linked by the NEXT field).

     2. A list of branch reg definitions per basic block (head is

        BB_BTR_DEFS[i], linked by the NEXT_THIS_BB field).

     3. A list of all branch reg definitions belonging to the same

        group (head is in a BTR_DEF_GROUP struct, linked by

        NEXT_THIS_GROUP field).  */

typedef struct btr_def_s

{

  struct btr_def_s *next_this_bb;

  struct btr_def_s *next_this_group;

  basic_block bb;

  int luid;

  rtx insn;

  int btr;

  int cost;

  /* For a branch register setting insn that has a constant

     source (i.e. a label), group links together all the

     insns with the same source.  For other branch register

     setting insns, group is NULL.  */

  btr_def_group group;

  btr_user uses;

  /* If this def has a reaching use which is not a simple use

     in a branch instruction, then has_ambiguous_use will be true,

     and we will not attempt to migrate this definition.  */

  char has_ambiguous_use;

  /* live_range is an approximation to the true live range for this

     def/use web, because it records the set of blocks that contain

     the live range.  There could be other live ranges for the same

     branch register in that set of blocks, either in the block

     containing the def (before the def), or in a block containing

     a use (after the use).  If there are such other live ranges, then

     other_btr_uses_before_def or other_btr_uses_after_use must be set true

     as appropriate.  */

  char other_btr_uses_before_def;

  char other_btr_uses_after_use;

  /* We set own_end when we have moved a definition into a dominator.

     Thus, when a later combination removes this definition again, we know

     to clear out trs_live_at_end again.  */

  char own_end;

  bitmap live_range;

} *btr_def;

static int issue_rate;

static int basic_block_freq (basic_block);

static int insn_sets_btr_p (rtx, int, int *);

static rtx *find_btr_use (rtx);

static int btr_referenced_p (rtx, rtx *);

static int find_btr_reference (rtx *, void *);

static void find_btr_def_group (btr_def_group *, btr_def);

static btr_def add_btr_def (fibheap_t, basic_block, int, rtx,

                            unsigned int, int, btr_def_group *);

static btr_user new_btr_user (basic_block, int, rtx);

static void dump_hard_reg_set (HARD_REG_SET);

static void dump_btrs_live (int);

static void note_other_use_this_block (unsigned int, btr_user);

static void compute_defs_uses_and_gen (fibheap_t, btr_def *,btr_user *,

                                       sbitmap *, sbitmap *, HARD_REG_SET *);

static void compute_kill (sbitmap *, sbitmap *, HARD_REG_SET *);

static void compute_out (sbitmap *bb_out, sbitmap *, sbitmap *, int);

static void link_btr_uses (btr_def *, btr_user *, sbitmap *, sbitmap *, int);

static void build_btr_def_use_webs (fibheap_t);

static int block_at_edge_of_live_range_p (int, btr_def);

static void clear_btr_from_live_range (btr_def def);

static void add_btr_to_live_range (btr_def, int);

static void augment_live_range (bitmap, HARD_REG_SET *, basic_block,

                                basic_block, int);

static int choose_btr (HARD_REG_SET);

static void combine_btr_defs (btr_def, HARD_REG_SET *);

static void btr_def_live_range (btr_def, HARD_REG_SET *);

static void move_btr_def (basic_block, int, btr_def, bitmap, HARD_REG_SET *);

static int migrate_btr_def (btr_def, int);

static void migrate_btr_defs (enum reg_class, int);

static int can_move_up (basic_block, rtx, int);

static void note_btr_set (rtx, rtx, void *);

/* The following code performs code motion of target load instructions

   (instructions that set branch target registers), to move them

   forward away from the branch instructions and out of loops (or,

   more generally, from a more frequently executed place to a less

   frequently executed place).

   Moving target load instructions further in front of the branch

   instruction that uses the target register value means that the hardware

   has a better chance of preloading the instructions at the branch

   target by the time the branch is reached.  This avoids bubbles

   when a taken branch needs to flush out the pipeline.

   Moving target load instructions out of loops means they are executed

   less frequently.  */

/* An obstack to hold the def-use web data structures built up for

   migrating branch target load instructions.  */

static struct obstack migrate_btrl_obstack;

/* Array indexed by basic block number, giving the set of registers

   live in that block.  */

static HARD_REG_SET *btrs_live;

/* Array indexed by basic block number, giving the set of registers live at

  the end of that block, including any uses by a final jump insn, if any.  */

static HARD_REG_SET *btrs_live_at_end;

/* Set of all target registers that we are willing to allocate.  */

static HARD_REG_SET all_btrs;

/* Provide lower and upper bounds for target register numbers, so that

   we don't need to search through all the hard registers all the time.  */

static int first_btr, last_btr;

/* Return an estimate of the frequency of execution of block bb.  */

static int

basic_block_freq (basic_block bb)

{

  return bb->frequency;

}

static rtx *btr_reference_found;

/* A subroutine of btr_referenced_p, called through for_each_rtx.

   PREG is a pointer to an rtx that is to be excluded from the

   traversal.  If we find a reference to a target register anywhere

   else, return 1, and put a pointer to it into btr_reference_found.  */

static int

find_btr_reference (rtx *px, void *preg)

{

  rtx x;

  int regno, i;

  if (px == preg)

    return -1;

  x = *px;

  if (!REG_P (x))

    return 0;

  regno = REGNO (x);

  for (i = hard_regno_nregs[regno][GET_MODE (x)] - 1; i >= 0; i--)

    if (TEST_HARD_REG_BIT (all_btrs, regno+i))

      {

        btr_reference_found = px;

        return 1;

      }

  return -1;

}

/* Return nonzero if X references (sets or reads) any branch target register.

   If EXCLUDEP is set, disregard any references within the rtx pointed to

   by it.  If returning nonzero, also set btr_reference_found as above.  */

static int

btr_referenced_p (rtx x, rtx *excludep)

{

  return for_each_rtx (&x, find_btr_reference, excludep);

}

/* Return true if insn is an instruction that sets a target register.

   if CHECK_CONST is true, only return true if the source is constant.

   If such a set is found and REGNO is nonzero, assign the register number

   of the destination register to *REGNO.  */

static int

insn_sets_btr_p (rtx insn, int check_const, int *regno)

{

  rtx set;

  if (NONJUMP_INSN_P (insn)

      && (set = single_set (insn)))

    {

      rtx dest = SET_DEST (set);

      rtx src = SET_SRC (set);

      if (GET_CODE (dest) == SUBREG)

        dest = XEXP (dest, 0);

      if (REG_P (dest)

          && TEST_HARD_REG_BIT (all_btrs, REGNO (dest)))

        {

          gcc_assert (!btr_referenced_p (src, NULL));

          if (!check_const || CONSTANT_P (src))

            {

              if (regno)

                *regno = REGNO (dest);

              return 1;

            }

        }

    }

  return 0;

}

/* Find and return a use of a target register within an instruction INSN.  */

static rtx *

find_btr_use (rtx insn)

{

  return btr_referenced_p (insn, NULL) ? btr_reference_found : NULL;

}

/* Find the group that the target register definition DEF belongs

   to in the list starting with *ALL_BTR_DEF_GROUPS.  If no such

   group exists, create one.  Add def to the group.  */

static void

find_btr_def_group (btr_def_group *all_btr_def_groups, btr_def def)

{

  if (insn_sets_btr_p (def->insn, 1, NULL))

    {

      btr_def_group this_group;

      rtx def_src = SET_SRC (single_set (def->insn));

      /* ?? This linear search is an efficiency concern, particularly

         as the search will almost always fail to find a match.  */

      for (this_group = *all_btr_def_groups;

           this_group != NULL;

           this_group = this_group->next)

        if (rtx_equal_p (def_src, this_group->src))

          break;

      if (!this_group)

        {

          this_group = obstack_alloc (&migrate_btrl_obstack,

                                      sizeof (struct btr_def_group_s));

          this_group->src = def_src;

          this_group->members = NULL;

          this_group->next = *all_btr_def_groups;

          *all_btr_def_groups = this_group;

        }

      def->group = this_group;

      def->next_this_group = this_group->members;

      this_group->members = def;

    }

  else

    def->group = NULL;

}

/* Create a new target register definition structure, for a definition in

   block BB, instruction INSN, and insert it into ALL_BTR_DEFS.  Return

   the new definition.  */

static btr_def

add_btr_def (fibheap_t all_btr_defs, basic_block bb, int insn_luid, rtx insn,

             unsigned int dest_reg, int other_btr_uses_before_def,

             btr_def_group *all_btr_def_groups)

{

  btr_def this

    = obstack_alloc (&migrate_btrl_obstack, sizeof (struct btr_def_s));

  this->bb = bb;

  this->luid = insn_luid;

  this->insn = insn;

  this->btr = dest_reg;

  this->cost = basic_block_freq (bb);

  this->has_ambiguous_use = 0;

  this->other_btr_uses_before_def = other_btr_uses_before_def;

  this->other_btr_uses_after_use = 0;

  this->next_this_bb = NULL;

  this->next_this_group = NULL;

  this->uses = NULL;

  this->live_range = NULL;

  find_btr_def_group (all_btr_def_groups, this);

  fibheap_insert (all_btr_defs, -this->cost, this);

  if (dump_file)

    fprintf (dump_file,

      "Found target reg definition: sets %u { bb %d, insn %d }%s priority %d\n",

      dest_reg, bb->index, INSN_UID (insn), (this->group ? "" : ":not const"),

      this->cost);

  return this;

}

/* Create a new target register user structure, for a use in block BB,

   instruction INSN.  Return the new user.  */

static btr_user

new_btr_user (basic_block bb, int insn_luid, rtx insn)

{

  /* This instruction reads target registers.  We need

     to decide whether we can replace all target register

     uses easily.

   */

  rtx *usep = find_btr_use (PATTERN (insn));

  rtx use;

  btr_user user = NULL;

  if (usep)

    {

      int unambiguous_single_use;

      /* We want to ensure that USE is the only use of a target

         register in INSN, so that we know that to rewrite INSN to use

         a different target register, all we have to do is replace USE.  */

      unambiguous_single_use = !btr_referenced_p (PATTERN (insn), usep);

      if (!unambiguous_single_use)

        usep = NULL;

    }

  use = usep ? *usep : NULL_RTX;

  user = obstack_alloc (&migrate_btrl_obstack, sizeof (struct btr_user_s));

  user->bb = bb;

  user->luid = insn_luid;

  user->insn = insn;

  user->use = use;

  user->other_use_this_block = 0;

  user->next = NULL;

  user->n_reaching_defs = 0;

  user->first_reaching_def = -1;

  if (dump_file)

    {

      fprintf (dump_file, "Uses target reg: { bb %d, insn %d }",

               bb->index, INSN_UID (insn));

      if (user->use)

        fprintf (dump_file, ": unambiguous use of reg %d\n",

                 REGNO (user->use));

    }

  return user;

}

/* Write the contents of S to the dump file.  */

static void

dump_hard_reg_set (HARD_REG_SET s)

{

  int reg;

  for (reg = 0; reg < FIRST_PSEUDO_REGISTER; reg++)

    if (TEST_HARD_REG_BIT (s, reg))

      fprintf (dump_file, " %d", reg);

}

/* Write the set of target regs live in block BB to the dump file.  */

static void

dump_btrs_live (int bb)

{

  fprintf (dump_file, "BB%d live:", bb);

  dump_hard_reg_set (btrs_live[bb]);

  fprintf (dump_file, "\n");

}

/* REGNO is the number of a branch target register that is being used or

   set.  USERS_THIS_BB is a list of preceding branch target register users;

   If any of them use the same register, set their other_use_this_block

   flag.  */

static void

note_other_use_this_block (unsigned int regno, btr_user users_this_bb)

{

  btr_user user;

  for (user = users_this_bb; user != NULL; user = user->next)

    if (user->use && REGNO (user->use) == regno)

      user->other_use_this_block = 1;

}

typedef struct {

  btr_user users_this_bb;

  HARD_REG_SET btrs_written_in_block;

  HARD_REG_SET btrs_live_in_block;

  sbitmap bb_gen;

  sbitmap *btr_defset;

} defs_uses_info;

/* Called via note_stores or directly to register stores into /

   clobbers of a branch target register DEST that are not recognized as

   straightforward definitions.  DATA points to information about the

   current basic block that needs updating.  */

static void

note_btr_set (rtx dest, rtx set ATTRIBUTE_UNUSED, void *data)

{

  defs_uses_info *info = data;

  int regno, end_regno;

  if (!REG_P (dest))

    return;

  regno = REGNO (dest);

  end_regno = regno + hard_regno_nregs[regno][GET_MODE (dest)];

  for (; regno < end_regno; regno++)

    if (TEST_HARD_REG_BIT (all_btrs, regno))

      {

        note_other_use_this_block (regno, info->users_this_bb);

        SET_HARD_REG_BIT (info->btrs_written_in_block, regno);

        SET_HARD_REG_BIT (info->btrs_live_in_block, regno);

        sbitmap_difference (info->bb_gen, info->bb_gen,

                            info->btr_defset[regno - first_btr]);

      }

}

static void

compute_defs_uses_and_gen (fibheap_t all_btr_defs, btr_def *def_array,

                           btr_user *use_array, sbitmap *btr_defset,

                           sbitmap *bb_gen, HARD_REG_SET *btrs_written)

{

  /* Scan the code building up the set of all defs and all uses.

     For each target register, build the set of defs of that register.

     For each block, calculate the set of target registers

     written in that block.

     Also calculate the set of btrs ever live in that block.

  */

  int i;

  int insn_luid = 0;

  btr_def_group all_btr_def_groups = NULL;

  defs_uses_info info;

  sbitmap_vector_zero (bb_gen, n_basic_blocks);

  for (i = 0; i < n_basic_blocks; i++)

    {

      basic_block bb = BASIC_BLOCK (i);

      int reg;

      btr_def defs_this_bb = NULL;

      rtx insn;

      rtx last;

      int can_throw = 0;

      info.users_this_bb = NULL;

      info.bb_gen = bb_gen[i];

      info.btr_defset = btr_defset;

      CLEAR_HARD_REG_SET (info.btrs_live_in_block);

      CLEAR_HARD_REG_SET (info.btrs_written_in_block);

      for (reg = first_btr; reg <= last_btr; reg++)

        if (TEST_HARD_REG_BIT (all_btrs, reg)

            && REGNO_REG_SET_P (bb->il.rtl->global_live_at_start, reg))

          SET_HARD_REG_BIT (info.btrs_live_in_block, reg);

      for (insn = BB_HEAD (bb), last = NEXT_INSN (BB_END (bb));

           insn != last;

           insn = NEXT_INSN (insn), insn_luid++)

        {

          if (INSN_P (insn))

            {

              int regno;

              int insn_uid = INSN_UID (insn);

              if (insn_sets_btr_p (insn, 0, &regno))

                {

                  btr_def def = add_btr_def (

                      all_btr_defs, bb, insn_luid, insn, regno,

                      TEST_HARD_REG_BIT (info.btrs_live_in_block, regno),

                      &all_btr_def_groups);

                  def_array[insn_uid] = def;

                  SET_HARD_REG_BIT (info.btrs_written_in_block, regno);

                  SET_HARD_REG_BIT (info.btrs_live_in_block, regno);

                  sbitmap_difference (bb_gen[i], bb_gen[i],

                                      btr_defset[regno - first_btr]);

                  SET_BIT (bb_gen[i], insn_uid);

                  def->next_this_bb = defs_this_bb;

                  defs_this_bb = def;

                  SET_BIT (btr_defset[regno - first_btr], insn_uid);

                  note_other_use_this_block (regno, info.users_this_bb);

                }

              /* Check for the blockage emitted by expand_nl_goto_receiver.  */

              else if (current_function_has_nonlocal_label

                       && GET_CODE (PATTERN (insn)) == ASM_INPUT)

                {

                  btr_user user;

                  /* Do the equivalent of calling note_other_use_this_block

                     for every target register.  */

                  for (user = info.users_this_bb; user != NULL;

                       user = user->next)

                    if (user->use)

                      user->other_use_this_block = 1;

                  IOR_HARD_REG_SET (info.btrs_written_in_block, all_btrs);

                  IOR_HARD_REG_SET (info.btrs_live_in_block, all_btrs);

                  sbitmap_zero (info.bb_gen);

                }

              else

                {

                  if (btr_referenced_p (PATTERN (insn), NULL))

                    {

                      btr_user user = new_btr_user (bb, insn_luid, insn);

                      use_array[insn_uid] = user;

                      if (user->use)

                        SET_HARD_REG_BIT (info.btrs_live_in_block,

                                          REGNO (user->use));

                      else

                        {

                          int reg;

                          for (reg = first_btr; reg <= last_btr; reg++)

                            if (TEST_HARD_REG_BIT (all_btrs, reg)

                                && refers_to_regno_p (reg, reg + 1, user->insn,

                                                      NULL))

                              {

                                note_other_use_this_block (reg,

                                                           info.users_this_bb);

                                SET_HARD_REG_BIT (info.btrs_live_in_block, reg);

                              }

                          note_stores (PATTERN (insn), note_btr_set, &info);

                        }

                      user->next = info.users_this_bb;

                      info.users_this_bb = user;

                    }

                  if (CALL_P (insn))

                    {

                      HARD_REG_SET *clobbered = &call_used_reg_set;

                      HARD_REG_SET call_saved;

                      rtx pat = PATTERN (insn);

                      int i;

                      /* Check for sibcall.  */

                      if (GET_CODE (pat) == PARALLEL)

                        for (i = XVECLEN (pat, 0) - 1; i >= 0; i--)

                          if (GET_CODE (XVECEXP (pat, 0, i)) == RETURN)

                            {

                              COMPL_HARD_REG_SET (call_saved,

                                                  call_used_reg_set);

                              clobbered = &call_saved;

                            }

                      for (regno = first_btr; regno <= last_btr; regno++)

                        if (TEST_HARD_REG_BIT (*clobbered, regno))

                          note_btr_set (regno_reg_rtx[regno], NULL_RTX, &info);

                    }

                }

            }

        }

      COPY_HARD_REG_SET (btrs_live[i], info.btrs_live_in_block);

      COPY_HARD_REG_SET (btrs_written[i], info.btrs_written_in_block);

      REG_SET_TO_HARD_REG_SET (btrs_live_at_end[i], bb->il.rtl->global_live_at_end);

      /* If this block ends in a jump insn, add any uses or even clobbers

         of branch target registers that it might have.  */

      for (insn = BB_END (bb); insn != BB_HEAD (bb) && ! INSN_P (insn); )

        insn = PREV_INSN (insn);

      /* ??? for the fall-through edge, it would make sense to insert the

         btr set on the edge, but that would require to split the block

         early on so that we can distinguish between dominance from the fall

         through edge - which can use the call-clobbered registers - from

         dominance by the throw edge.  */

      if (can_throw_internal (insn))

        {

          HARD_REG_SET tmp;

          COPY_HARD_REG_SET (tmp, call_used_reg_set);

          AND_HARD_REG_SET (tmp, all_btrs);

          IOR_HARD_REG_SET (btrs_live_at_end[i], tmp);

          can_throw = 1;

        }

      if (can_throw || JUMP_P (insn))

        {

          int regno;

          for (regno = first_btr; regno <= last_btr; regno++)

            if (refers_to_regno_p (regno, regno+1, insn, NULL))

              SET_HARD_REG_BIT (btrs_live_at_end[i], regno);

        }

      if (dump_file)

        dump_btrs_live(i);

    }

}

static void

compute_kill (sbitmap *bb_kill, sbitmap *btr_defset,

              HARD_REG_SET *btrs_written)

{

  int i;

  int regno;

  /* For each basic block, form the set BB_KILL - the set

     of definitions that the block kills.  */

  sbitmap_vector_zero (bb_kill, n_basic_blocks);

  for (i = 0; i < n_basic_blocks; i++)

    {

      for (regno = first_btr; regno <= last_btr; regno++)

        if (TEST_HARD_REG_BIT (all_btrs, regno)

            && TEST_HARD_REG_BIT (btrs_written[i], regno))

          sbitmap_a_or_b (bb_kill[i], bb_kill[i],

                          btr_defset[regno - first_btr]);

    }

}

static void

compute_out (sbitmap *bb_out, sbitmap *bb_gen, sbitmap *bb_kill, int max_uid)

{

  /* Perform iterative dataflow:

      Initially, for all blocks, BB_OUT = BB_GEN.

      For each block,

        BB_IN  = union over predecessors of BB_OUT(pred)

        BB_OUT = (BB_IN - BB_KILL) + BB_GEN

     Iterate until the bb_out sets stop growing.  */

  int i;

  int changed;

  sbitmap bb_in = sbitmap_alloc (max_uid);

  for (i = 0; i < n_basic_blocks; i++)

    sbitmap_copy (bb_out[i], bb_gen[i]);

  changed = 1;

  while (changed)

    {

      changed = 0;

      for (i = 0; i < n_basic_blocks; i++)

        {

          sbitmap_union_of_preds (bb_in, bb_out, i);

          changed |= sbitmap_union_of_diff_cg (bb_out[i], bb_gen[i],

                                               bb_in, bb_kill[i]);

        }

    }

  sbitmap_free (bb_in);

}

static void

link_btr_uses (btr_def *def_array, btr_user *use_array, sbitmap *bb_out,

               sbitmap *btr_defset, int max_uid)

{

  int i;

  sbitmap reaching_defs = sbitmap_alloc (max_uid);

  /* Link uses to the uses lists of all of their reaching defs.

     Count up the number of reaching defs of each use.  */

  for (i = 0; i < n_basic_blocks; i++)

    {

      basic_block bb = BASIC_BLOCK (i);

      rtx insn;

      rtx last;

      sbitmap_union_of_preds (reaching_defs, bb_out, i);

      for (insn = BB_HEAD (bb), last = NEXT_INSN (BB_END (bb));

           insn != last;

           insn = NEXT_INSN (insn))