text: /* Basic block reordering routines for the GNU compiler.
     Copyright (C) 2000, 2001, 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 "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 */
    0                                     /* letter */
  };
  
  
  /* 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);
  
  		  if (note
  		      && INTVAL (XEXP (note, 0)) < REG_BR_PROB_BASE / 2
  		      && invert_jump (bb_end_insn,
  				      (e_fall->dest == EXIT_BLOCK_PTR
  				       ? NULL_RTX
  				       : label_for_bb (e_fall->dest)), 0))
  		    {
  		      e_fall->flags &= ~EDGE_FALLTHRU;
  #ifdef ENABLE_CHECKING
  		      gcc_assert (could_fall_through
  				  (e_taken->src, e_taken->dest));
  #endif
  		      e_taken->flags |= EDGE_FALLTHRU;
  		      update_br_prob_note (bb);
  		      e = e_fall, e_fall = e_taken, e_taken = e;
  		    }
  		}
  
  	      /* If the "jumping" edge is a crossing edge, and the fall
  		 through edge is non-crossing, leave things as they are.  */
  	      else if ((e_taken->flags & EDGE_CROSSING)
  		       && !(e_fall->flags & EDGE_CROSSING))
  		continue;
  
  	      /* Otherwise we can try to invert the jump.  This will
  		 basically never fail, however, keep up the pretense.  */
  	      else if (invert_jump (bb_end_insn,
  				    (e_fall->dest == EXIT_BLOCK_PTR
  				     ? NULL_RTX
  				     : label_for_bb (e_fall->dest)), 0))
  		{
  		  e_fall->flags &= ~EDGE_FALLTHRU;
  #ifdef ENABLE_CHECKING
  		  gcc_assert (could_fall_through
  			      (e_taken->src, e_taken->dest));
  #endif
  		  e_taken->flags |= EDGE_FALLTHRU;
  		  update_br_prob_note (bb);
  		  continue;
  		}
  	    }
  	  else
  	    {
  	      /* Otherwise we have some return, switch or computed
  		 jump.  In the 99% case, there should not have been a
  		 fallthru edge.  */
  	      gcc_assert (returnjump_p (bb_end_insn) || !e_fall);
  	      continue;
  	    }
  	}
        else
  	{
  	  /* No fallthru implies a noreturn function with EH edges, or
  	     something similarly bizarre.  In any case, we don't need to
  	     do anything.  */
  	  if (! e_fall)
  	    continue;
  
  	  /* If the fallthru block is still next, nothing to do.  */
  	  if (bb->aux == e_fall->dest)
  	    continue;
  
  	  /* A fallthru to exit block.  */
  	  if (e_fall->dest == EXIT_BLOCK_PTR)
  	    continue;
  	}
  
        /* We got here if we need to add a new jump insn.  */
        nb = force_nonfallthru (e_fall);
        if (nb)
  	{
  	  nb->il.rtl->visited = 1;
  	  nb->aux = bb->aux;
  	  bb->aux = nb;
  	  /* Don't process this new block.  */
  	  bb = nb;
  
  	  /* Make sure new bb is tagged for correct section (same as
  	     fall-thru source, since you cannot fall-throu across
  	     section boundaries).  */
  	  BB_COPY_PARTITION (e_fall->src, single_pred (bb));
  	  if (flag_reorder_blocks_and_partition
  	      && targetm.have_named_sections
  	      && JUMP_P (BB_END (bb))
  	      && !any_condjump_p (BB_END (bb))
  	      && (EDGE_SUCC (bb, 0)->flags & EDGE_CROSSING))
  	    REG_NOTES (BB_END (bb)) = gen_rtx_EXPR_LIST
  	      (REG_CROSSING_JUMP, NULL_RTX, REG_NOTES (BB_END (bb)));
  	}
      }
  
    /* Put basic_block_info in the new order.  */
  
    if (dump_file)
      {
        fprintf (dump_file, "Reordered sequence:\n");
        for (bb = ENTRY_BLOCK_PTR->next_bb, index = NUM_FIXED_BLOCKS;
  	   bb;
  	   bb = 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);
  	}
      }
  
    prev_bb = ENTRY_BLOCK_PTR;
    bb = ENTRY_BLOCK_PTR->next_bb;
    index = NUM_FIXED_BLOCKS;
  
    for (; bb; prev_bb = bb, bb = bb->aux, index ++)
      {
        bb->index = index;
        SET_BASIC_BLOCK (index, bb);
  
        bb->prev_bb = prev_bb;
        prev_bb->next_bb = bb;
      }
    prev_bb->next_bb = EXIT_BLOCK_PTR;
    EXIT_BLOCK_PTR->prev_bb = prev_bb;
  
    /* Annoying special case - jump around dead jumptables left in the code.  */
    FOR_EACH_BB (bb)
      {
        edge e;
        edge_iterator ei;
  
        FOR_EACH_EDGE (e, ei, bb->succs)
  	if (e->flags & EDGE_FALLTHRU)
  	  break;
  
        if (e && !can_fallthru (e->src, e->dest))
  	force_nonfallthru (e);
      }
  }
  
  /* Perform sanity checks on the insn chain.
     1. Check that next/prev pointers are consistent in both the forward and
        reverse direction.
     2. Count insns in chain, going both directions, and check if equal.
     3. Check that get_last_insn () returns the actual end of chain.  */
  
  void
  verify_insn_chain (void)
  {
    rtx x, prevx, nextx;
    int insn_cnt1, insn_cnt2;
  
    for (prevx = NULL, insn_cnt1 = 1, x = get_insns ();
         x != 0;
         prevx = x, insn_cnt1++, x = NEXT_INSN (x))
      gcc_assert (PREV_INSN (x) == prevx);
  
    gcc_assert (prevx == get_last_insn ());
  
    for (nextx = NULL, insn_cnt2 = 1, x = get_last_insn ();
         x != 0;
         nextx = x, insn_cnt2++, x = PREV_INSN (x))
      gcc_assert (NEXT_INSN (x) == nextx);
  
    gcc_assert (insn_cnt1 == insn_cnt2);
  }
  
  /* If we have assembler epilogues, the block falling through to exit must
     be the last one in the reordered chain when we reach final.  Ensure
     that this condition is met.  */
  static void
  fixup_fallthru_exit_predecessor (void)
  {
    edge e;
    edge_iterator ei;
    basic_block bb = NULL;
  
    /* This transformation is not valid before reload, because we might
       separate a call from the instruction that copies the return
       value.  */
    gcc_assert (reload_completed);
  
    FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
      if (e->flags & EDGE_FALLTHRU)
        bb = e->src;
  
    if (bb && bb->aux)
      {
        basic_block c = ENTRY_BLOCK_PTR->next_bb;
  
        /* If the very first block is the one with the fall-through exit
  	 edge, we have to split that block.  */
        if (c == bb)
  	{
  	  bb = split_block (bb, NULL)->dest;
  	  bb->aux = c->aux;
  	  c->aux = bb;
  	  bb->il.rtl->footer = c->il.rtl->footer;
  	  c->il.rtl->footer = NULL;
  	}
  
        while (c->aux != bb)
  	c = c->aux;
  
        c->aux = bb->aux;
        while (c->aux)
  	c = c->aux;
  
        c->aux = bb;
        bb->aux = NULL;
      }
  }
  
  /* Return true in case it is possible to duplicate the basic block BB.  */
  
  /* We do not want to declare the function in a header file, since it should
     only be used through the cfghooks interface, and we do not want to move
     it to cfgrtl.c since it would require also moving quite a lot of related
     code.  */
  extern bool cfg_layout_can_duplicate_bb_p (basic_block);
  
  bool
  cfg_layout_can_duplicate_bb_p (basic_block bb)
  {
    /* Do not attempt to duplicate tablejumps, as we need to unshare
       the dispatch table.  This is difficult to do, as the instructions
       computing jump destination may be hoisted outside the basic block.  */
    if (tablejump_p (BB_END (bb), NULL, NULL))
      return false;
  
    /* Do not duplicate blocks containing insns that can't be copied.  */
    if (targetm.cannot_copy_insn_p)
      {
        rtx insn = BB_HEAD (bb);
        while (1)
  	{
  	  if (INSN_P (insn) && targetm.cannot_copy_insn_p (insn))
  	    return false;
  	  if (insn == BB_END (bb))
  	    break;
  	  insn = NEXT_INSN (insn);
  	}
      }
  
    return true;
  }
  
  rtx
  duplicate_insn_chain (rtx from, rtx to)
  {
    rtx insn, last;
  
    /* Avoid updating of boundaries of previous basic block.  The
       note will get removed from insn stream in fixup.  */
    last = emit_note (NOTE_INSN_DELETED);
  
    /* Create copy at the end of INSN chain.  The chain will
       be reordered later.  */
    for (insn = from; insn != NEXT_INSN (to); insn = NEXT_INSN (insn))
      {
        switch (GET_CODE (insn))
  	{
  	case INSN:
  	case CALL_INSN:
  	case JUMP_INSN:
  	  /* Avoid copying of dispatch tables.  We never duplicate
  	     tablejumps, so this can hit only in case the table got
  	     moved far from original jump.  */
  	  if (GET_CODE (PATTERN (insn)) == ADDR_VEC
  	      || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC)
  	    break;
  	  emit_copy_of_insn_after (insn, get_last_insn ());
  	  break;
  
  	case CODE_LABEL:
  	  break;
  
  	case BARRIER:
  	  emit_barrier ();
  	  break;
  
  	case NOTE:
  	  switch (NOTE_LINE_NUMBER (insn))
  	    {
  	      /* In case prologue is empty and function contain label
  		 in first BB, we may want to copy the block.  */
  	    case NOTE_INSN_PROLOGUE_END:
  
  	    case NOTE_INSN_DELETED:
  	    case NOTE_INSN_DELETED_LABEL:
  	      /* No problem to strip these.  */
  	    case NOTE_INSN_EPILOGUE_BEG:
  	    case NOTE_INSN_FUNCTION_END:
  	      /* Debug code expect these notes to exist just once.
  		 Keep them in the master copy.
  		 ??? It probably makes more sense to duplicate them for each
  		 epilogue copy.  */
  	    case NOTE_INSN_FUNCTION_BEG:
  	      /* There is always just single entry to function.  */
  	    case NOTE_INSN_BASIC_BLOCK:
  	      break;
  
  	    case NOTE_INSN_REPEATED_LINE_NUMBER:
  	    case NOTE_INSN_SWITCH_TEXT_SECTIONS:
  	      emit_note_copy (insn);
  	      break;
  
  	    default:
  	      /* All other notes should have already been eliminated.
  	       */
  	      gcc_assert (NOTE_LINE_NUMBER (insn) >= 0);
  
  	      /* It is possible that no_line_number is set and the note
  		 won't be emitted.  */
  	      emit_note_copy (insn);
  	    }
  	  break;
  	default:
  	  gcc_unreachable ();
  	}
      }
    insn = NEXT_INSN (last);
    delete_insn (last);
    return insn;
  }
  /* Create a duplicate of the basic block BB.  */
  
  /* We do not want to declare the function in a header file, since it should
     only be used through the cfghooks interface, and we do not want to move
     it to cfgrtl.c since it would require also moving quite a lot of related
     code.  */
  extern basic_block cfg_layout_duplicate_bb (basic_block);
  
  basic_block
  cfg_layout_duplicate_bb (basic_block bb)
  {
    rtx insn;
    basic_block new_bb;
  
    insn = duplicate_insn_chain (BB_HEAD (bb), BB_END (bb));
    new_bb = create_basic_block (insn,
  			       insn ? get_last_insn () : NULL,
  			       EXIT_BLOCK_PTR->prev_bb);
  
    BB_COPY_PARTITION (new_bb, bb);
    if (bb->il.rtl->header)
      {
        insn = bb->il.rtl->header;
        while (NEXT_INSN (insn))
  	insn = NEXT_INSN (insn);
        insn = duplicate_insn_chain (bb->il.rtl->header, insn);
        if (insn)
  	new_bb->il.rtl->header = unlink_insn_chain (insn, get_last_insn ());
      }
  
    if (bb->il.rtl->footer)
      {
        insn = bb->il.rtl->footer;
        while (NEXT_INSN (insn))
  	insn = NEXT_INSN (insn);
        insn = duplicate_insn_chain (bb->il.rtl->footer, insn);
        if (insn)
  	new_bb->il.rtl->footer = unlink_insn_chain (insn, get_last_insn ());
      }
  
    if (bb->il.rtl->global_live_at_start)
      {
        new_bb->il.rtl->global_live_at_start = ALLOC_REG_SET (&reg_obstack);
        new_bb->il.rtl->global_live_at_end = ALLOC_REG_SET (&reg_obstack);
        COPY_REG_SET (new_bb->il.rtl->global_live_at_start,
  		    bb->il.rtl->global_live_at_start);
        COPY_REG_SET (new_bb->il.rtl->global_live_at_end,
  		    bb->il.rtl->global_live_at_end);
      }
  
    return new_bb;
  }
  
  /* Main entry point to this module - initialize the datastructures for
     CFG layout changes.  It keeps LOOPS up-to-date if not null.
  
     FLAGS is a set of additional flags to pass to cleanup_cfg().  It should
     include CLEANUP_UPDATE_LIFE if liveness information must be kept up
     to date.  */
  
  void
  cfg_layout_initialize (unsigned int flags)
  {
    initialize_original_copy_tables ();
  
    cfg_layout_rtl_register_cfg_hooks ();
  
    record_effective_endpoints ();
  
    cleanup_cfg (CLEANUP_CFGLAYOUT | flags);
  }
  
  /* Splits superblocks.  */
  void
  break_superblocks (void)
  {
    sbitmap superblocks;
    bool need = false;
    basic_block bb;
  
    superblocks = sbitmap_alloc (last_basic_block);
    sbitmap_zero (superblocks);
  
    FOR_EACH_BB (bb)
      if (bb->flags & BB_SUPERBLOCK)
        {
  	bb->flags &= ~BB_SUPERBLOCK;
  	SET_BIT (superblocks, bb->index);
  	need = true;
        }
  
    if (need)
      {
        rebuild_jump_labels (get_insns ());
        find_many_sub_basic_blocks (superblocks);
      }
  
    free (superblocks);
  }
  
  /* Finalize the changes: reorder insn list according to the sequence specified
     by aux pointers, enter compensation code, rebuild scope forest.  */
  
  void
  cfg_layout_finalize (void)
  {
    basic_block bb;
  
  #ifdef ENABLE_CHECKING
    verify_flow_info ();
  #endif
    rtl_register_cfg_hooks ();
    if (reload_completed
  #ifdef HAVE_epilogue
        && !HAVE_epilogue
  #endif
        )
      fixup_fallthru_exit_predecessor ();
    fixup_reorder_chain ();
  
  #ifdef ENABLE_CHECKING
    verify_insn_chain ();
  #endif
    FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
    {
      bb->il.rtl->header = bb->il.rtl->footer = NULL;
      bb->aux = NULL;
      bb->il.rtl->visited = 0;
    }
  
    break_superblocks ();
  
  #ifdef ENABLE_CHECKING
    verify_flow_info ();
  #endif
  
    free_original_copy_tables ();
  }
  
  /* Checks whether all N blocks in BBS array can be copied.  */
  bool
  can_copy_bbs_p (basic_block *bbs, unsigned n)
  {
    unsigned i;
    edge e;
    int ret = true;
  
    for (i = 0; i < n; i++)
      bbs[i]->flags |= BB_DUPLICATED;
  
    for (i = 0; i < n; i++)
      {
        /* In case we should redirect abnormal edge during duplication, fail.  */
        edge_iterator ei;
        FOR_EACH_EDGE (e, ei, bbs[i]->succs)
  	if ((e->flags & EDGE_ABNORMAL)
  	    && (e->dest->flags & BB_DUPLICATED))
  	  {
  	    ret = false;
  	    goto end;
  	  }
  
        if (!can_duplicate_block_p (bbs[i]))
  	{
  	  ret = false;
  	  break;
  	}
      }
  
  end:
    for (i = 0; i < n; i++)
      bbs[i]->flags &= ~BB_DUPLICATED;
  
    return ret;
  }
  
  /* Duplicates N basic blocks stored in array BBS.  Newly created basic blocks
     are placed into array NEW_BBS in the same order.  Edges from basic blocks
     in BBS are also duplicated and copies of those of them
     that lead into BBS are redirected to appropriate newly created block.  The
     function assigns bbs into loops (copy of basic block bb is assigned to
     bb->loop_father->copy loop, so this must be set up correctly in advance)
     and updates dominators locally (LOOPS structure that contains the information
     about dominators is passed to enable this).
  
     BASE is the superloop to that basic block belongs; if its header or latch
     is copied, we do not set the new blocks as header or latch.
  
     Created copies of N_EDGES edges in array EDGES are stored in array NEW_EDGES,
     also in the same order.
  
     Newly created basic blocks are put after the basic block AFTER in the
     instruction stream, and the order of the blocks in BBS array is preserved.  */
  
  void
  copy_bbs (basic_block *bbs, unsigned n, basic_block *new_bbs,
  	  edge *edges, unsigned num_edges, edge *new_edges,
  	  struct loop *base, basic_block after)
  {
    unsigned i, j;
    basic_block bb, new_bb, dom_bb;
    edge e;
  
    /* Duplicate bbs, update dominators, assign bbs to loops.  */
    for (i = 0; i < n; i++)
      {
        /* Duplicate.  */
        bb = bbs[i];
        new_bb = new_bbs[i] = duplicate_block (bb, NULL, after);
        after = new_bb;
        bb->flags |= BB_DUPLICATED;
        /* Add to loop.  */
        add_bb_to_loop (new_bb, bb->loop_father->copy);
        /* Possibly set header.  */
        if (bb->loop_father->header == bb && bb->loop_father != base)
  	new_bb->loop_father->header = new_bb;
        /* Or latch.  */
        if (bb->loop_father->latch == bb && bb->loop_father != base)
  	new_bb->loop_father->latch = new_bb;
      }
  
    /* Set dominators.  */
    for (i = 0; i < n; i++)
      {
        bb = bbs[i];
        new_bb = new_bbs[i];
  
        dom_bb = get_immediate_dominator (CDI_DOMINATORS, bb);
        if (dom_bb->flags & BB_DUPLICATED)
  	{
  	  dom_bb = get_bb_copy (dom_bb);
  	  set_immediate_dominator (CDI_DOMINATORS, new_bb, dom_bb);
  	}
      }
  
    /* Redirect edges.  */
    for (j = 0; j < num_edges; j++)
      new_edges[j] = NULL;
    for (i = 0; i < n; i++)
      {
        edge_iterator ei;
        new_bb = new_bbs[i];
        bb = bbs[i];
  
        FOR_EACH_EDGE (e, ei, new_bb->succs)
  	{
  	  for (j = 0; j < num_edges; j++)
  	    if (edges[j] && edges[j]->src == bb && edges[j]->dest == e->dest)
  	      new_edges[j] = e;
  
  	  if (!(e->dest->flags & BB_DUPLICATED))
  	    continue;
  	  redirect_edge_and_branch_force (e, get_bb_copy (e->dest));
  	}
      }
  
    /* Clear information about duplicates.  */
    for (i = 0; i < n; i++)
      bbs[i]->flags &= ~BB_DUPLICATED;
  }
  
  #include "gt-cfglayout.h"
  