Subversion Repositories openrisc

/* Basic block reordering routines for the GNU compiler.

   Copyright (C) 2000, 2001, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010

   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 3, 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 COPYING3.  If not see

<http://www.gnu.org/licenses/>.  */

#include "config.h"

#include "system.h"

#include "coretypes.h"

#include "tm.h"

#include "tree.h"

#include "rtl.h"

#include "hard-reg-set.h"

#include "obstack.h"

#include "basic-block.h"

#include "insn-config.h"

#include "output.h"

#include "function.h"

#include "cfglayout.h"

#include "cfgloop.h"

#include "target.h"

#include "ggc.h"

#include "alloc-pool.h"

#include "flags.h"

#include "tree-pass.h"

#include "df.h"

#include "vecprim.h"

/* Holds the interesting trailing notes for the function.  */

rtx cfg_layout_function_footer;

rtx cfg_layout_function_header;

static rtx skip_insns_after_block (basic_block);

static void record_effective_endpoints (void);

static rtx label_for_bb (basic_block);

static void fixup_reorder_chain (void);

static void change_scope (rtx, tree, tree);

void verify_insn_chain (void);

static void fixup_fallthru_exit_predecessor (void);

static tree insn_scope (const_rtx);

rtx

unlink_insn_chain (rtx first, rtx last)

{

  rtx prevfirst = PREV_INSN (first);

  rtx nextlast = NEXT_INSN (last);

  PREV_INSN (first) = NULL;

  NEXT_INSN (last) = NULL;

  if (prevfirst)

    NEXT_INSN (prevfirst) = nextlast;

  if (nextlast)

    PREV_INSN (nextlast) = prevfirst;

  else

    set_last_insn (prevfirst);

  if (!prevfirst)

    set_first_insn (nextlast);

  return first;

}

/* Skip over inter-block insns occurring after BB which are typically

   associated with BB (e.g., barriers). If there are any such insns,

   we return the last one. Otherwise, we return the end of BB.  */

static rtx

skip_insns_after_block (basic_block bb)

{

  rtx insn, last_insn, next_head, prev;

  next_head = NULL_RTX;

  if (bb->next_bb != EXIT_BLOCK_PTR)

    next_head = BB_HEAD (bb->next_bb);

  for (last_insn = insn = BB_END (bb); (insn = NEXT_INSN (insn)) != 0; )

    {

      if (insn == next_head)

        break;

      switch (GET_CODE (insn))

        {

        case BARRIER:

          last_insn = insn;

          continue;

        case NOTE:

          switch (NOTE_KIND (insn))

            {

            case NOTE_INSN_BLOCK_END:

              gcc_unreachable ();

              continue;

            default:

              continue;

              break;

            }

          break;

        case CODE_LABEL:

          if (NEXT_INSN (insn)

              && JUMP_TABLE_DATA_P (NEXT_INSN (insn)))

            {

              insn = NEXT_INSN (insn);

              last_insn = insn;

              continue;

            }

          break;

        default:

          break;

        }

      break;

    }

  /* It is possible to hit contradictory sequence.  For instance:

     jump_insn

     NOTE_INSN_BLOCK_BEG

     barrier

     Where barrier belongs to jump_insn, but the note does not.  This can be

     created by removing the basic block originally following

     NOTE_INSN_BLOCK_BEG.  In such case reorder the notes.  */

  for (insn = last_insn; insn != BB_END (bb); insn = prev)

    {

      prev = PREV_INSN (insn);

      if (NOTE_P (insn))

        switch (NOTE_KIND (insn))

          {

          case NOTE_INSN_BLOCK_END:

            gcc_unreachable ();

            break;

          case NOTE_INSN_DELETED:

          case NOTE_INSN_DELETED_LABEL:

            continue;

          default:

            reorder_insns (insn, insn, last_insn);

          }

    }

  return last_insn;

}

/* Locate or create a label for a given basic block.  */

static rtx

label_for_bb (basic_block bb)

{

  rtx label = BB_HEAD (bb);

  if (!LABEL_P (label))

    {

      if (dump_file)

        fprintf (dump_file, "Emitting label for block %d\n", bb->index);

      label = block_label (bb);

    }

  return label;

}

/* Locate the effective beginning and end of the insn chain for each

   block, as defined by skip_insns_after_block above.  */

static void

record_effective_endpoints (void)

{

  rtx next_insn;

  basic_block bb;

  rtx insn;

  for (insn = get_insns ();

       insn

       && NOTE_P (insn)

       && NOTE_KIND (insn) != NOTE_INSN_BASIC_BLOCK;

       insn = NEXT_INSN (insn))

    continue;

  /* No basic blocks at all?  */

  gcc_assert (insn);

  if (PREV_INSN (insn))

    cfg_layout_function_header =

            unlink_insn_chain (get_insns (), PREV_INSN (insn));

  else

    cfg_layout_function_header = NULL_RTX;

  next_insn = get_insns ();

  FOR_EACH_BB (bb)

    {

      rtx end;

      if (PREV_INSN (BB_HEAD (bb)) && next_insn != BB_HEAD (bb))

        bb->il.rtl->header = unlink_insn_chain (next_insn,

                                              PREV_INSN (BB_HEAD (bb)));

      end = skip_insns_after_block (bb);

      if (NEXT_INSN (BB_END (bb)) && BB_END (bb) != end)

        bb->il.rtl->footer = unlink_insn_chain (NEXT_INSN (BB_END (bb)), end);

      next_insn = NEXT_INSN (BB_END (bb));

    }

  cfg_layout_function_footer = next_insn;

  if (cfg_layout_function_footer)

    cfg_layout_function_footer = unlink_insn_chain (cfg_layout_function_footer, get_last_insn ());

}

/* Data structures representing mapping of INSN_LOCATOR into scope blocks, line

   numbers and files.  In order to be GGC friendly we need to use separate

   varrays.  This also slightly improve the memory locality in binary search.

   The _locs array contains locators where the given property change.  The

   block_locators_blocks contains the scope block that is used for all insn

   locator greater than corresponding block_locators_locs value and smaller

   than the following one.  Similarly for the other properties.  */

static VEC(int,heap) *block_locators_locs;

static GTY(()) VEC(tree,gc) *block_locators_blocks;

static VEC(int,heap) *locations_locators_locs;

DEF_VEC_O(location_t);

DEF_VEC_ALLOC_O(location_t,heap);

static VEC(location_t,heap) *locations_locators_vals;

int prologue_locator;

int epilogue_locator;

/* Hold current location information and last location information, so the

   datastructures are built lazily only when some instructions in given

   place are needed.  */

static location_t curr_location, last_location;

static tree curr_block, last_block;

static int curr_rtl_loc = -1;

/* Allocate insn locator datastructure.  */

void

insn_locators_alloc (void)

{

  prologue_locator = epilogue_locator = 0;

  block_locators_locs = VEC_alloc (int, heap, 32);

  block_locators_blocks = VEC_alloc (tree, gc, 32);

  locations_locators_locs = VEC_alloc (int, heap, 32);

  locations_locators_vals = VEC_alloc (location_t, heap, 32);

  last_location = -1;

  curr_location = -1;

  curr_block = NULL;

  last_block = NULL;

  curr_rtl_loc = 0;

}

/* At the end of emit stage, clear current location.  */

void

insn_locators_finalize (void)

{

  if (curr_rtl_loc >= 0)

    epilogue_locator = curr_insn_locator ();

  curr_rtl_loc = -1;

}

/* Allocate insn locator datastructure.  */

void

insn_locators_free (void)

{

  prologue_locator = epilogue_locator = 0;

  VEC_free (int, heap, block_locators_locs);

  VEC_free (tree,gc, block_locators_blocks);

  VEC_free (int, heap, locations_locators_locs);

  VEC_free (location_t, heap, locations_locators_vals);

}

/* Set current location.  */

void

set_curr_insn_source_location (location_t location)

{

  /* IV opts calls into RTL expansion to compute costs of operations.  At this

     time locators are not initialized.  */

  if (curr_rtl_loc == -1)

    return;

  curr_location = location;

}

/* Get current location.  */

location_t

get_curr_insn_source_location (void)

{

  return curr_location;

}

/* Set current scope block.  */

void

set_curr_insn_block (tree b)

{

  /* IV opts calls into RTL expansion to compute costs of operations.  At this

     time locators are not initialized.  */

  if (curr_rtl_loc == -1)

    return;

  if (b)

    curr_block = b;

}

/* Get current scope block.  */

tree

get_curr_insn_block (void)

{

  return curr_block;

}

/* Return current insn locator.  */

int

curr_insn_locator (void)

{

  if (curr_rtl_loc == -1)

    return 0;

  if (last_block != curr_block)

    {

      curr_rtl_loc++;

      VEC_safe_push (int, heap, block_locators_locs, curr_rtl_loc);

      VEC_safe_push (tree, gc, block_locators_blocks, curr_block);

      last_block = curr_block;

    }

  if (last_location != curr_location)

    {

      curr_rtl_loc++;

      VEC_safe_push (int, heap, locations_locators_locs, curr_rtl_loc);

      VEC_safe_push (location_t, heap, locations_locators_vals, &curr_location);

      last_location = curr_location;

    }

  return curr_rtl_loc;

}

static unsigned int

into_cfg_layout_mode (void)

{

  cfg_layout_initialize (0);

  return 0;

}

static unsigned int

outof_cfg_layout_mode (void)

{

  basic_block bb;

  FOR_EACH_BB (bb)

    if (bb->next_bb != EXIT_BLOCK_PTR)

      bb->aux = bb->next_bb;

  cfg_layout_finalize ();

  return 0;

}

struct rtl_opt_pass pass_into_cfg_layout_mode =

{

 {

  RTL_PASS,

  "into_cfglayout",                     /* name */

  NULL,                                 /* gate */

  into_cfg_layout_mode,                 /* execute */

  NULL,                                 /* sub */

  NULL,                                 /* next */

  0,                                    /* static_pass_number */

  TV_NONE,                              /* tv_id */

  0,                                    /* properties_required */

  PROP_cfglayout,                       /* properties_provided */

  0,                                    /* properties_destroyed */

  0,                                    /* todo_flags_start */

  TODO_dump_func,                       /* todo_flags_finish */

 }

};

struct rtl_opt_pass pass_outof_cfg_layout_mode =

{

 {

  RTL_PASS,

  "outof_cfglayout",                    /* name */

  NULL,                                 /* gate */

  outof_cfg_layout_mode,                /* execute */

  NULL,                                 /* sub */

  NULL,                                 /* next */

  0,                                    /* static_pass_number */

  TV_NONE,                              /* tv_id */

  0,                                    /* properties_required */

  0,                                    /* properties_provided */

  PROP_cfglayout,                       /* properties_destroyed */

  0,                                    /* todo_flags_start */

  TODO_dump_func,                       /* todo_flags_finish */

 }

};

/* Return scope resulting from combination of S1 and S2.  */

static tree

choose_inner_scope (tree s1, tree s2)

{

   if (!s1)

     return s2;

   if (!s2)

     return s1;

   if (BLOCK_NUMBER (s1) > BLOCK_NUMBER (s2))

     return s1;

   return s2;

}

/* Emit lexical block notes needed to change scope from S1 to S2.  */

static void

change_scope (rtx orig_insn, tree s1, tree s2)

{

  rtx insn = orig_insn;

  tree com = NULL_TREE;

  tree ts1 = s1, ts2 = s2;

  tree s;

  while (ts1 != ts2)

    {

      gcc_assert (ts1 && ts2);

      if (BLOCK_NUMBER (ts1) > BLOCK_NUMBER (ts2))

        ts1 = BLOCK_SUPERCONTEXT (ts1);

      else if (BLOCK_NUMBER (ts1) < BLOCK_NUMBER (ts2))

        ts2 = BLOCK_SUPERCONTEXT (ts2);

      else

        {

          ts1 = BLOCK_SUPERCONTEXT (ts1);

          ts2 = BLOCK_SUPERCONTEXT (ts2);

        }

    }

  com = ts1;

  /* Close scopes.  */

  s = s1;

  while (s != com)

    {

      rtx note = emit_note_before (NOTE_INSN_BLOCK_END, insn);

      NOTE_BLOCK (note) = s;

      s = BLOCK_SUPERCONTEXT (s);

    }

  /* Open scopes.  */

  s = s2;

  while (s != com)

    {

      insn = emit_note_before (NOTE_INSN_BLOCK_BEG, insn);

      NOTE_BLOCK (insn) = s;

      s = BLOCK_SUPERCONTEXT (s);

    }

}

/* Return lexical scope block locator belongs to.  */

static tree

locator_scope (int loc)

{

  int max = VEC_length (int, block_locators_locs);

  int min = 0;

  /* When block_locators_locs was initialized, the pro- and epilogue

     insns didn't exist yet and can therefore not be found this way.

     But we know that they belong to the outer most block of the

     current function.

     Without this test, the prologue would be put inside the block of

     the first valid instruction in the function and when that first

     insn is part of an inlined function then the low_pc of that

     inlined function is messed up.  Likewise for the epilogue and

     the last valid instruction.  */

  if (loc == prologue_locator || loc == epilogue_locator)

    return DECL_INITIAL (cfun->decl);

  if (!max || !loc)

    return NULL;

  while (1)

    {

      int pos = (min + max) / 2;

      int tmp = VEC_index (int, block_locators_locs, pos);

      if (tmp <= loc && min != pos)

        min = pos;

      else if (tmp > loc && max != pos)

        max = pos;

      else

        {

          min = pos;

          break;

        }

    }

  return VEC_index (tree, block_locators_blocks, min);

}

/* Return lexical scope block insn belongs to.  */

static tree

insn_scope (const_rtx insn)

{

  return locator_scope (INSN_LOCATOR (insn));

}

/* Return line number of the statement specified by the locator.  */

location_t

locator_location (int loc)

{

  int max = VEC_length (int, locations_locators_locs);

  int min = 0;

  while (1)

    {

      int pos = (min + max) / 2;

      int tmp = VEC_index (int, locations_locators_locs, pos);

      if (tmp <= loc && min != pos)

        min = pos;

      else if (tmp > loc && max != pos)

        max = pos;

      else

        {

          min = pos;

          break;

        }

    }

  return *VEC_index (location_t, locations_locators_vals, min);

}

/* Return source line of the statement that produced this insn.  */

int

locator_line (int loc)

{

  expanded_location xloc;

  if (!loc)

    return 0;

  else

    xloc = expand_location (locator_location (loc));

  return xloc.line;

}

/* Return line number of the statement that produced this insn.  */

int

insn_line (const_rtx insn)

{

  return locator_line (INSN_LOCATOR (insn));

}

/* Return source file of the statement specified by LOC.  */

const char *

locator_file (int loc)

{

  expanded_location xloc;

  if (!loc)

    return 0;

  else

    xloc = expand_location (locator_location (loc));

  return xloc.file;

}

/* Return source file of the statement that produced this insn.  */

const char *

insn_file (const_rtx insn)

{

  return locator_file (INSN_LOCATOR (insn));

}

/* Return true if LOC1 and LOC2 locators have the same location and scope.  */

bool

locator_eq (int loc1, int loc2)

{

  if (loc1 == loc2)

    return true;

  if (locator_location (loc1) != locator_location (loc2))

    return false;

  return locator_scope (loc1) == locator_scope (loc2);

}

/* Rebuild all the NOTE_INSN_BLOCK_BEG and NOTE_INSN_BLOCK_END notes based

   on the scope tree and the newly reordered instructions.  */

void

reemit_insn_block_notes (void)

{

  tree cur_block = DECL_INITIAL (cfun->decl);

  rtx insn, note;

  insn = get_insns ();

  if (!active_insn_p (insn))

    insn = next_active_insn (insn);

  for (; insn; insn = next_active_insn (insn))

    {

      tree this_block;

      /* Avoid putting scope notes between jump table and its label.  */

      if (JUMP_TABLE_DATA_P (insn))

        continue;

      this_block = insn_scope (insn);

      /* For sequences compute scope resulting from merging all scopes

         of instructions nested inside.  */

      if (GET_CODE (PATTERN (insn)) == SEQUENCE)

        {

          int i;

          rtx body = PATTERN (insn);

          this_block = NULL;

          for (i = 0; i < XVECLEN (body, 0); i++)

            this_block = choose_inner_scope (this_block,

                                         insn_scope (XVECEXP (body, 0, i)));

        }

      if (! this_block)

        continue;

      if (this_block != cur_block)

        {

          change_scope (insn, cur_block, this_block);

          cur_block = this_block;

        }

    }

  /* change_scope emits before the insn, not after.  */

  note = emit_note (NOTE_INSN_DELETED);

  change_scope (note, cur_block, DECL_INITIAL (cfun->decl));

  delete_insn (note);

  reorder_blocks ();

}

/* Link the basic blocks in the correct order, compacting the basic

   block queue while at it.  This also clears the visited flag on

   all basic blocks.  If STAY_IN_CFGLAYOUT_MODE is false, this function

   also clears the basic block header and footer fields.

   This function is usually called after a pass (e.g. tracer) finishes

   some transformations while in cfglayout mode.  The required sequence

   of the basic blocks is in a linked list along the bb->aux field.

   This functions re-links the basic block prev_bb and next_bb pointers

   accordingly, and it compacts and renumbers the blocks.  */

void

relink_block_chain (bool stay_in_cfglayout_mode)

{

  basic_block bb, prev_bb;

  int index;

  /* Maybe dump the re-ordered sequence.  */

  if (dump_file)

    {

      fprintf (dump_file, "Reordered sequence:\n");

      for (bb = ENTRY_BLOCK_PTR->next_bb, index = NUM_FIXED_BLOCKS;

           bb;

           bb = (basic_block) bb->aux, index++)

        {

          fprintf (dump_file, " %i ", index);

          if (get_bb_original (bb))

            fprintf (dump_file, "duplicate of %i ",

                     get_bb_original (bb)->index);

          else if (forwarder_block_p (bb)

                   && !LABEL_P (BB_HEAD (bb)))

            fprintf (dump_file, "compensation ");

          else

            fprintf (dump_file, "bb %i ", bb->index);

          fprintf (dump_file, " [%i]\n", bb->frequency);

        }

    }

  /* Now reorder the blocks.  */

  prev_bb = ENTRY_BLOCK_PTR;

  bb = ENTRY_BLOCK_PTR->next_bb;

  for (; bb; prev_bb = bb, bb = (basic_block) bb->aux)

    {

      bb->prev_bb = prev_bb;

      prev_bb->next_bb = bb;

    }

  prev_bb->next_bb = EXIT_BLOCK_PTR;

  EXIT_BLOCK_PTR->prev_bb = prev_bb;

  /* Then, clean up the aux and visited fields.  */

  FOR_ALL_BB (bb)

    {

      bb->aux = NULL;

      bb->il.rtl->visited = 0;

      if (!stay_in_cfglayout_mode)

        bb->il.rtl->header = bb->il.rtl->footer = NULL;

    }

  /* Maybe reset the original copy tables, they are not valid anymore

     when we renumber the basic blocks in compact_blocks.  If we are

     are going out of cfglayout mode, don't re-allocate the tables.  */

  free_original_copy_tables ();

  if (stay_in_cfglayout_mode)

    initialize_original_copy_tables ();

  /* Finally, put basic_block_info in the new order.  */

  compact_blocks ();

}

/* Given a reorder chain, rearrange the code to match.  */

static void

fixup_reorder_chain (void)

{

  basic_block bb;

  rtx insn = NULL;

  if (cfg_layout_function_header)

    {

      set_first_insn (cfg_layout_function_header);