Subversion Repositories openrisc_me

/* Basic block reordering routines for the GNU compiler.

   Copyright (C) 2000, 2001, 2003, 2004, 2005, 2007 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 "vecprim.h"

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

rtx cfg_layout_function_footer, 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 set_block_levels (tree, int);

static void change_scope (rtx, tree, tree);

void verify_insn_chain (void);

static void fixup_fallthru_exit_predecessor (void);

static tree insn_scope (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_LINE_NUMBER (insn))

            {

            case NOTE_INSN_BLOCK_END:

              last_insn = insn;

              continue;

            case NOTE_INSN_DELETED:

            case NOTE_INSN_DELETED_LABEL:

              continue;

            default:

              continue;

              break;

            }

          break;

        case CODE_LABEL:

          if (NEXT_INSN (insn)

              && JUMP_P (NEXT_INSN (insn))

              && (GET_CODE (PATTERN (NEXT_INSN (insn))) == ADDR_VEC

                  || GET_CODE (PATTERN (NEXT_INSN (insn))) == ADDR_DIFF_VEC))

            {

              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_LINE_NUMBER (insn))

          {

          case NOTE_INSN_BLOCK_END:

          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_LINE_NUMBER (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) *line_locators_locs;

static VEC(int,heap) *line_locators_lines;

static VEC(int,heap) *file_locators_locs;

static GTY(()) varray_type file_locators_files;

int prologue_locator;

int epilogue_locator;

/* During the RTL expansion the lexical blocks and line numbers are

   represented via INSN_NOTEs.  Replace them by representation using

   INSN_LOCATORs.  */

unsigned int

insn_locators_initialize (void)

{

  tree block = NULL;

  tree last_block = NULL;

  rtx insn, next;

  int loc = 0;

  int line_number = 0, last_line_number = 0;

  const char *file_name = NULL, *last_file_name = NULL;

  prologue_locator = epilogue_locator = 0;

  block_locators_locs = VEC_alloc (int, heap, 32);

  block_locators_blocks = VEC_alloc (tree, gc, 32);

  line_locators_locs = VEC_alloc (int, heap, 32);

  line_locators_lines = VEC_alloc (int, heap, 32);

  file_locators_locs = VEC_alloc (int, heap, 32);

  VARRAY_CHAR_PTR_INIT (file_locators_files, 32, "file_locators_files");

  for (insn = get_insns (); insn; insn = next)

    {

      int active = 0;

      next = NEXT_INSN (insn);

      if (NOTE_P (insn))

        {

          gcc_assert (NOTE_LINE_NUMBER (insn) != NOTE_INSN_BLOCK_BEG

                      && NOTE_LINE_NUMBER (insn) != NOTE_INSN_BLOCK_END);

          if (NOTE_LINE_NUMBER (insn) > 0)

            {

              expanded_location xloc;

              NOTE_EXPANDED_LOCATION (xloc, insn);

              line_number = xloc.line;

              file_name = xloc.file;

            }

        }

      else

        active = (active_insn_p (insn)

                  && GET_CODE (PATTERN (insn)) != ADDR_VEC

                  && GET_CODE (PATTERN (insn)) != ADDR_DIFF_VEC);

      check_block_change (insn, &block);

      if (active

          || !next

          || (!prologue_locator && file_name))

        {

          if (last_block != block)

            {

              loc++;

              VEC_safe_push (int, heap, block_locators_locs, loc);

              VEC_safe_push (tree, gc, block_locators_blocks, block);

              last_block = block;

            }

          if (last_line_number != line_number)

            {

              loc++;

              VEC_safe_push (int, heap, line_locators_locs, loc);

              VEC_safe_push (int, heap, line_locators_lines, line_number);

              last_line_number = line_number;

            }

          if (last_file_name != file_name)

            {

              loc++;

              VEC_safe_push (int, heap, file_locators_locs, loc);

              VARRAY_PUSH_CHAR_PTR (file_locators_files, (char *) file_name);

              last_file_name = file_name;

            }

          if (!prologue_locator && file_name)

            prologue_locator = loc;

          if (!next)

            epilogue_locator = loc;

          if (active)

            INSN_LOCATOR (insn) = loc;

        }

    }

  /* Tag the blocks with a depth number so that change_scope can find

     the common parent easily.  */

  set_block_levels (DECL_INITIAL (cfun->decl), 0);

  free_block_changes ();

  return 0;

}

struct tree_opt_pass pass_insn_locators_initialize =

{

  "locators",                           /* name */

  NULL,                                 /* gate */

  insn_locators_initialize,             /* execute */

  NULL,                                 /* sub */

  NULL,                                 /* next */

  0,                                    /* static_pass_number */

  0,                                    /* tv_id */

  0,                                    /* properties_required */

  0,                                    /* properties_provided */

  0,                                    /* properties_destroyed */

  0,                                    /* todo_flags_start */

  TODO_dump_func,                       /* todo_flags_finish */

};

/* For each lexical block, set BLOCK_NUMBER to the depth at which it is

   found in the block tree.  */

static void

set_block_levels (tree block, int level)

{

  while (block)

    {

      BLOCK_NUMBER (block) = level;

      set_block_levels (BLOCK_SUBBLOCKS (block), level + 1);

      block = BLOCK_CHAIN (block);

    }

}

/* Return sope 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 insn belong to.  */

static tree

insn_scope (rtx insn)

{

  int max = VEC_length (int, block_locators_locs);

  int min = 0;

  int loc = INSN_LOCATOR (insn);

  /* 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 line number of the statement specified by the locator.  */

int

locator_line (int loc)

{

  int max = VEC_length (int, line_locators_locs);

  int min = 0;

  if (!max || !loc)

    return 0;

  while (1)

    {

      int pos = (min + max) / 2;

      int tmp = VEC_index (int, line_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 (int, line_locators_lines, min);

}

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

int

insn_line (rtx insn)

{

  return locator_line (INSN_LOCATOR (insn));

}

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

const char *

locator_file (int loc)

{

  int max = VEC_length (int, file_locators_locs);

  int min = 0;

  if (!max || !loc)

    return NULL;

  while (1)

    {

      int pos = (min + max) / 2;

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

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

        min = pos;

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

        max = pos;

      else

        {

          min = pos;

          break;

        }

    }

   return VARRAY_CHAR_PTR (file_locators_files, min);

}

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

const char *

insn_file (rtx insn)

{

  return locator_file (INSN_LOCATOR (insn));

}

/* 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_P (insn)

          && (GET_CODE (PATTERN (insn)) == ADDR_VEC

              || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC))

        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 ();

}

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

static void

fixup_reorder_chain (void)

{

  basic_block bb, prev_bb;

  int index;

  rtx insn = NULL;

  if (cfg_layout_function_header)

    {

      set_first_insn (cfg_layout_function_header);

      insn = cfg_layout_function_header;

      while (NEXT_INSN (insn))

        insn = NEXT_INSN (insn);

    }

  /* First do the bulk reordering -- rechain the blocks without regard to

     the needed changes to jumps and labels.  */

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

       bb != 0;

       bb = bb->aux, index++)

    {

      if (bb->il.rtl->header)

        {

          if (insn)

            NEXT_INSN (insn) = bb->il.rtl->header;

          else

            set_first_insn (bb->il.rtl->header);

          PREV_INSN (bb->il.rtl->header) = insn;

          insn = bb->il.rtl->header;

          while (NEXT_INSN (insn))

            insn = NEXT_INSN (insn);

        }

      if (insn)

        NEXT_INSN (insn) = BB_HEAD (bb);

      else

        set_first_insn (BB_HEAD (bb));

      PREV_INSN (BB_HEAD (bb)) = insn;

      insn = BB_END (bb);

      if (bb->il.rtl->footer)

        {

          NEXT_INSN (insn) = bb->il.rtl->footer;

          PREV_INSN (bb->il.rtl->footer) = insn;

          while (NEXT_INSN (insn))

            insn = NEXT_INSN (insn);

        }

    }

  gcc_assert (index == n_basic_blocks);

  NEXT_INSN (insn) = cfg_layout_function_footer;

  if (cfg_layout_function_footer)

    PREV_INSN (cfg_layout_function_footer) = insn;

  while (NEXT_INSN (insn))

    insn = NEXT_INSN (insn);

  set_last_insn (insn);

#ifdef ENABLE_CHECKING

  verify_insn_chain ();

#endif

  delete_dead_jumptables ();

  /* Now add jumps and labels as needed to match the blocks new

     outgoing edges.  */

  for (bb = ENTRY_BLOCK_PTR->next_bb; bb ; bb = bb->aux)

    {

      edge e_fall, e_taken, e;

      rtx bb_end_insn;

      basic_block nb;

      edge_iterator ei;

      if (EDGE_COUNT (bb->succs) == 0)

        continue;

      /* Find the old fallthru edge, and another non-EH edge for

         a taken jump.  */

      e_taken = e_fall = NULL;

      FOR_EACH_EDGE (e, ei, bb->succs)

        if (e->flags & EDGE_FALLTHRU)

          e_fall = e;

        else if (! (e->flags & EDGE_EH))

          e_taken = e;

      bb_end_insn = BB_END (bb);

      if (JUMP_P (bb_end_insn))

        {

          if (any_condjump_p (bb_end_insn))

            {

              /* If the old fallthru is still next, nothing to do.  */

              if (bb->aux == e_fall->dest

                  || e_fall->dest == EXIT_BLOCK_PTR)

                continue;

              /* The degenerated case of conditional jump jumping to the next

                 instruction can happen for jumps with side effects.  We need

                 to construct a forwarder block and this will be done just

                 fine by force_nonfallthru below.  */

              if (!e_taken)

                ;

              /* There is another special case: if *neither* block is next,

                 such as happens at the very end of a function, then we'll

                 need to add a new unconditional jump.  Choose the taken

                 edge based on known or assumed probability.  */

              else if (bb->aux != e_taken->dest)

                {

                  rtx note = find_reg_note (bb_end_insn, REG_BR_PROB, 0);