X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Fcfgbuild.c;h=692fea8a17b3d87b1e7e6ef9b8a1f28228eb120c;hb=3e426b86d2ef51d0abcee1ec27167a3d9bfe3037;hp=d6e96e78d6c117eb4e0d29b86093a72dbc7c10b8;hpb=0060a7fe39397e95ce7dfcf871898c54b4489d9d;p=pf3gnuchains%2Fgcc-fork.git

diff --git a/gcc/cfgbuild.c b/gcc/cfgbuild.c
index d6e96e78d6c..692fea8a17b 100644
--- a/gcc/cfgbuild.c
+++ b/gcc/cfgbuild.c
@@ -1,12 +1,13 @@
 /* Control flow graph building code for GNU compiler.
    Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
-   1999, 2000, 2001 Free Software Foundation, Inc.
+   1999, 2000, 2001, 2002, 2003, 2004, 2005, 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 2, or (at your option) any later
+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
@@ -15,26 +16,14 @@ 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, 59 Temple Place - Suite 330, Boston, MA
-02111-1307, USA.  */
-
-/* find_basic_blocks divides the current function's rtl into basic
-   blocks and constructs the CFG.  The blocks are recorded in the
-   basic_block_info array; the CFG exists in the edge structures
-   referenced by the blocks.
-
-   find_basic_blocks also finds any unreachable loops and deletes them.
-
-   Available functionality:
-     - CFG construction
-         find_basic_blocks
-     - Local CFG construction
-         find_sub_basic_blocks
- */
+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"
@@ -44,124 +33,102 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA
 #include "output.h"
 #include "function.h"
 #include "except.h"
-#include "toplev.h"
+#include "expr.h"
+#include "diagnostic-core.h"
 #include "timevar.h"
+#include "sbitmap.h"
 
-#include "obstack.h"
-static int count_basic_blocks		PARAMS ((rtx));
-static void find_basic_blocks_1		PARAMS ((rtx));
-static rtx find_label_refs		PARAMS ((rtx, rtx));
-static void make_edges			PARAMS ((rtx, int, int, int));
-static void make_label_edge		PARAMS ((sbitmap *, basic_block,
-						 rtx, int));
-static void make_eh_edge		PARAMS ((sbitmap *, basic_block, rtx));
-
-/* Count the basic blocks of the function.  */
+static void make_edges (basic_block, basic_block, int);
+static void make_label_edge (sbitmap, basic_block, rtx, int);
+static void find_bb_boundaries (basic_block);
+static void compute_outgoing_frequencies (basic_block);
+
+/* Return true if insn is something that should be contained inside basic
+   block.  */
 
-static int
-count_basic_blocks (f)
-     rtx f;
+bool
+inside_basic_block_p (const_rtx insn)
 {
-  register rtx insn;
-  register RTX_CODE prev_code;
-  register int count = 0;
-  int saw_abnormal_edge = 0;
-
-  prev_code = JUMP_INSN;
-  for (insn = f; insn; insn = NEXT_INSN (insn))
+  switch (GET_CODE (insn))
     {
-      enum rtx_code code = GET_CODE (insn);
-
-      if (code == CODE_LABEL
-	  || (GET_RTX_CLASS (code) == 'i'
-	      && (prev_code == JUMP_INSN
-		  || prev_code == BARRIER
-		  || saw_abnormal_edge)))
-	{
-	  saw_abnormal_edge = 0;
-	  count++;
-	}
-
-      /* Record whether this insn created an edge.  */
-      if (code == CALL_INSN)
-	{
-	  rtx note;
-
-	  /* If there is a nonlocal goto label and the specified
-	     region number isn't -1, we have an edge.  */
-	  if (nonlocal_goto_handler_labels
-	      && ((note = find_reg_note (insn, REG_EH_REGION, NULL_RTX)) == 0
-		  || INTVAL (XEXP (note, 0)) >= 0))
-	    saw_abnormal_edge = 1;
-
-	  else if (can_throw_internal (insn))
-	    saw_abnormal_edge = 1;
-	}
-      else if (flag_non_call_exceptions
-	       && code == INSN
-	       && can_throw_internal (insn))
-	saw_abnormal_edge = 1;
-
-      if (code != NOTE)
-	prev_code = code;
+    case CODE_LABEL:
+      /* Avoid creating of basic block for jumptables.  */
+      return (NEXT_INSN (insn) == 0
+	      || !JUMP_P (NEXT_INSN (insn))
+	      || (GET_CODE (PATTERN (NEXT_INSN (insn))) != ADDR_VEC
+		  && GET_CODE (PATTERN (NEXT_INSN (insn))) != ADDR_DIFF_VEC));
+
+    case JUMP_INSN:
+      return (GET_CODE (PATTERN (insn)) != ADDR_VEC
+	      && GET_CODE (PATTERN (insn)) != ADDR_DIFF_VEC);
+
+    case CALL_INSN:
+    case INSN:
+    case DEBUG_INSN:
+      return true;
+
+    case BARRIER:
+    case NOTE:
+      return false;
+
+    default:
+      gcc_unreachable ();
     }
+}
+
+/* Return true if INSN may cause control flow transfer, so it should be last in
+   the basic block.  */
 
-  /* The rest of the compiler works a bit smoother when we don't have to
-     check for the edge case of do-nothing functions with no basic blocks.  */
-  if (count == 0)
+bool
+control_flow_insn_p (const_rtx insn)
+{
+  switch (GET_CODE (insn))
     {
-      emit_insn (gen_rtx_USE (VOIDmode, const0_rtx));
-      count = 1;
+    case NOTE:
+    case CODE_LABEL:
+    case DEBUG_INSN:
+      return false;
+
+    case JUMP_INSN:
+      /* Jump insn always causes control transfer except for tablejumps.  */
+      return (GET_CODE (PATTERN (insn)) != ADDR_VEC
+	      && GET_CODE (PATTERN (insn)) != ADDR_DIFF_VEC);
+
+    case CALL_INSN:
+      /* Noreturn and sibling call instructions terminate the basic blocks
+	 (but only if they happen unconditionally).  */
+      if ((SIBLING_CALL_P (insn)
+	   || find_reg_note (insn, REG_NORETURN, 0))
+	  && GET_CODE (PATTERN (insn)) != COND_EXEC)
+	return true;
+
+      /* Call insn may return to the nonlocal goto handler.  */
+      if (can_nonlocal_goto (insn))
+	return true;
+      break;
+
+    case INSN:
+      /* Treat trap instructions like noreturn calls (same provision).  */
+      if (GET_CODE (PATTERN (insn)) == TRAP_IF
+	  && XEXP (PATTERN (insn), 0) == const1_rtx)
+	return true;
+      if (!cfun->can_throw_non_call_exceptions)
+	return false;
+      break;
+
+    case BARRIER:
+      /* It is nonsense to reach barrier when looking for the
+	 end of basic block, but before dead code is eliminated
+	 this may happen.  */
+      return false;
+
+    default:
+      gcc_unreachable ();
     }
 
-  return count;
+  return can_throw_internal (insn);
 }
 
-/* Scan a list of insns for labels referred to other than by jumps.
-   This is used to scan the alternatives of a call placeholder.  */
-static rtx
-find_label_refs (f, lvl)
-     rtx f;
-     rtx lvl;
-{
-  rtx insn;
-
-  for (insn = f; insn; insn = NEXT_INSN (insn))
-    if (INSN_P (insn) && GET_CODE (insn) != JUMP_INSN)
-      {
-	rtx note;
-
-	/* Make a list of all labels referred to other than by jumps
-	   (which just don't have the REG_LABEL notes).
-
-	   Make a special exception for labels followed by an ADDR*VEC,
-	   as this would be a part of the tablejump setup code.
-
-	   Make a special exception to registers loaded with label
-	   values just before jump insns that use them.  */
-
-	for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
-	  if (REG_NOTE_KIND (note) == REG_LABEL)
-	    {
-	      rtx lab = XEXP (note, 0), next;
-
-	      if ((next = next_nonnote_insn (lab)) != NULL
-		       && GET_CODE (next) == JUMP_INSN
-		       && (GET_CODE (PATTERN (next)) == ADDR_VEC
-			   || GET_CODE (PATTERN (next)) == ADDR_DIFF_VEC))
-		;
-	      else if (GET_CODE (lab) == NOTE)
-		;
-	      else if (GET_CODE (NEXT_INSN (insn)) == JUMP_INSN
-		       && find_reg_note (NEXT_INSN (insn), REG_LABEL, lab))
-		;
-	      else
-		lvl = alloc_EXPR_LIST (0, XEXP (note, 0), lvl);
-	    }
-      }
-
-  return lvl;
-}
 
 /* Create an edge between two basic blocks.  FLAGS are auxiliary information
    about the edge that is accumulated between calls.  */
@@ -169,14 +136,9 @@ find_label_refs (f, lvl)
 /* Create an edge from a basic block to a label.  */
 
 static void
-make_label_edge (edge_cache, src, label, flags)
-     sbitmap *edge_cache;
-     basic_block src;
-     rtx label;
-     int flags;
+make_label_edge (sbitmap edge_cache, basic_block src, rtx label, int flags)
 {
-  if (GET_CODE (label) != CODE_LABEL)
-    abort ();
+  gcc_assert (LABEL_P (label));
 
   /* If the label was never emitted, this insn is junk, but avoid a
      crash trying to refer to BLOCK_FOR_INSN (label).  This can happen
@@ -191,78 +153,107 @@ make_label_edge (edge_cache, src, label, flags)
 
 /* Create the edges generated by INSN in REGION.  */
 
-static void
-make_eh_edge (edge_cache, src, insn)
-     sbitmap *edge_cache;
-     basic_block src;
-     rtx insn;
+void
+rtl_make_eh_edge (sbitmap edge_cache, basic_block src, rtx insn)
 {
-  int is_call = (GET_CODE (insn) == CALL_INSN ? EDGE_ABNORMAL_CALL : 0);
-  rtx handlers, i;
+  eh_landing_pad lp = get_eh_landing_pad_from_rtx (insn);
 
-  handlers = reachable_handlers (insn);
+  if (lp)
+    {
+      rtx label = lp->landing_pad;
 
-  for (i = handlers; i; i = XEXP (i, 1))
-    make_label_edge (edge_cache, src, XEXP (i, 0),
-		     EDGE_ABNORMAL | EDGE_EH | is_call);
+      /* During initial rtl generation, use the post_landing_pad.  */
+      if (label == NULL)
+	{
+	  gcc_assert (lp->post_landing_pad);
+	  label = label_rtx (lp->post_landing_pad);
+	}
 
-  free_INSN_LIST_list (&handlers);
+      make_label_edge (edge_cache, src, label,
+		       EDGE_ABNORMAL | EDGE_EH
+		       | (CALL_P (insn) ? EDGE_ABNORMAL_CALL : 0));
+    }
 }
-/* Identify the edges between basic blocks MIN to MAX.
 
-   NONLOCAL_LABEL_LIST is a list of non-local labels in the function.  Blocks
-   that are otherwise unreachable may be reachable with a non-local goto.
+/* States of basic block as seen by find_many_sub_basic_blocks.  */
+enum state {
+  /* Basic blocks created via split_block belong to this state.
+     make_edges will examine these basic blocks to see if we need to
+     create edges going out of them.  */
+  BLOCK_NEW = 0,
+
+  /* Basic blocks that do not need examining belong to this state.
+     These blocks will be left intact.  In particular, make_edges will
+     not create edges going out of these basic blocks.  */
+  BLOCK_ORIGINAL,
+
+  /* Basic blocks that may need splitting (due to a label appearing in
+     the middle, etc) belong to this state.  After splitting them,
+     make_edges will create edges going out of them as needed.  */
+  BLOCK_TO_SPLIT
+};
+
+#define STATE(BB) (enum state) ((size_t) (BB)->aux)
+#define SET_STATE(BB, STATE) ((BB)->aux = (void *) (size_t) (STATE))
+
+/* Used internally by purge_dead_tablejump_edges, ORed into state.  */
+#define BLOCK_USED_BY_TABLEJUMP		32
+#define FULL_STATE(BB) ((size_t) (BB)->aux)
+
+/* Identify the edges going out of basic blocks between MIN and MAX,
+   inclusive, that have their states set to BLOCK_NEW or
+   BLOCK_TO_SPLIT.
 
-   BB_EH_END is an array indexed by basic block number in which we record
-   the list of exception regions active at the end of the basic block.  */
+   UPDATE_P should be nonzero if we are updating CFG and zero if we
+   are building CFG from scratch.  */
 
 static void
-make_edges (label_value_list, min, max, update_p)
-     rtx label_value_list;
-     int min, max, update_p;
+make_edges (basic_block min, basic_block max, int update_p)
 {
-  int i;
-  sbitmap *edge_cache = NULL;
-
-  /* Assume no computed jump; revise as we create edges.  */
-  current_function_has_computed_jump = 0;
+  basic_block bb;
+  sbitmap edge_cache = NULL;
 
   /* Heavy use of computed goto in machine-generated code can lead to
      nearly fully-connected CFGs.  In that case we spend a significant
      amount of time searching the edge lists for duplicates.  */
-  if (forced_labels || label_value_list)
-    {
-      edge_cache = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
-      sbitmap_vector_zero (edge_cache, n_basic_blocks);
+  if (forced_labels || cfun->cfg->max_jumptable_ents > 100)
+    edge_cache = sbitmap_alloc (last_basic_block);
 
-      if (update_p)
-	for (i = min; i <= max; ++i)
-	  {
-	    edge e;
-	    for (e = BASIC_BLOCK (i)->succ; e ; e = e->succ_next)
-	      if (e->dest != EXIT_BLOCK_PTR)
-	        SET_BIT (edge_cache[i], e->dest->index);
-	  }
-    }
-
-  /* By nature of the way these get numbered, block 0 is always the entry.  */
-  cached_make_edge (edge_cache, ENTRY_BLOCK_PTR, BASIC_BLOCK (0), EDGE_FALLTHRU);
+  /* By nature of the way these get numbered, ENTRY_BLOCK_PTR->next_bb block
+     is always the entry.  */
+  if (min == ENTRY_BLOCK_PTR->next_bb)
+    make_edge (ENTRY_BLOCK_PTR, min, EDGE_FALLTHRU);
 
-  for (i = min; i <= max; ++i)
+  FOR_BB_BETWEEN (bb, min, max->next_bb, next_bb)
     {
-      basic_block bb = BASIC_BLOCK (i);
       rtx insn, x;
       enum rtx_code code;
-      int force_fallthru = 0;
+      edge e;
+      edge_iterator ei;
+
+      if (STATE (bb) == BLOCK_ORIGINAL)
+	continue;
 
-      if (GET_CODE (bb->head) == CODE_LABEL
-	  && LABEL_ALTERNATE_NAME (bb->head))
+      /* If we have an edge cache, cache edges going out of BB.  */
+      if (edge_cache)
+	{
+	  sbitmap_zero (edge_cache);
+	  if (update_p)
+	    {
+	      FOR_EACH_EDGE (e, ei, bb->succs)
+		if (e->dest != EXIT_BLOCK_PTR)
+		  SET_BIT (edge_cache, e->dest->index);
+	    }
+	}
+
+      if (LABEL_P (BB_HEAD (bb))
+	  && LABEL_ALT_ENTRY_P (BB_HEAD (bb)))
 	cached_make_edge (NULL, ENTRY_BLOCK_PTR, bb, 0);
 
       /* Examine the last instruction of the block, and discover the
 	 ways we can leave the block.  */
 
-      insn = bb->end;
+      insn = BB_END (bb);
       code = GET_CODE (insn);
 
       /* A branch.  */
@@ -270,21 +261,13 @@ make_edges (label_value_list, min, max, update_p)
 	{
 	  rtx tmp;
 
-	  /* Recognize exception handling placeholders.  */
-	  if (GET_CODE (PATTERN (insn)) == RESX)
-	    make_eh_edge (edge_cache, bb, insn);
-
 	  /* Recognize a non-local goto as a branch outside the
 	     current function.  */
-	  else if (find_reg_note (insn, REG_NON_LOCAL_GOTO, NULL_RTX))
+	  if (find_reg_note (insn, REG_NON_LOCAL_GOTO, NULL_RTX))
 	    ;
 
-	  /* ??? Recognize a tablejump and do the right thing.  */
-	  else if ((tmp = JUMP_LABEL (insn)) != NULL_RTX
-		   && (tmp = NEXT_INSN (tmp)) != NULL_RTX
-		   && GET_CODE (tmp) == JUMP_INSN
-		   && (GET_CODE (PATTERN (tmp)) == ADDR_VEC
-		       || GET_CODE (PATTERN (tmp)) == ADDR_DIFF_VEC))
+	  /* Recognize a tablejump and do the right thing.  */
+	  else if (tablejump_p (insn, NULL, &tmp))
 	    {
 	      rtvec vec;
 	      int j;
@@ -307,23 +290,12 @@ make_edges (label_value_list, min, max, update_p)
 		  && GET_CODE (XEXP (SET_SRC (tmp), 2)) == LABEL_REF)
 		make_label_edge (edge_cache, bb,
 				 XEXP (XEXP (SET_SRC (tmp), 2), 0), 0);
-
-#ifdef CASE_DROPS_THROUGH
-	      /* Silly VAXen.  The ADDR_VEC is going to be in the way of
-		 us naturally detecting fallthru into the next block.  */
-	      force_fallthru = 1;
-#endif
 	    }
 
 	  /* If this is a computed jump, then mark it as reaching
-	     everything on the label_value_list and forced_labels list.  */
+	     everything on the forced_labels list.  */
 	  else if (computed_jump_p (insn))
 	    {
-	      current_function_has_computed_jump = 1;
-
-	      for (x = label_value_list; x; x = XEXP (x, 1))
-		make_label_edge (edge_cache, bb, XEXP (x, 0), EDGE_ABNORMAL);
-
 	      for (x = forced_labels; x; x = XEXP (x, 1))
 		make_label_edge (edge_cache, bb, XEXP (x, 0), EDGE_ABNORMAL);
 	    }
@@ -332,65 +304,84 @@ make_edges (label_value_list, min, max, update_p)
 	  else if (returnjump_p (insn))
 	    cached_make_edge (edge_cache, bb, EXIT_BLOCK_PTR, 0);
 
+	  /* Recognize asm goto and do the right thing.  */
+	  else if ((tmp = extract_asm_operands (PATTERN (insn))) != NULL)
+	    {
+	      int i, n = ASM_OPERANDS_LABEL_LENGTH (tmp);
+	      for (i = 0; i < n; ++i)
+		make_label_edge (edge_cache, bb,
+				 XEXP (ASM_OPERANDS_LABEL (tmp, i), 0), 0);
+	    }
+
 	  /* Otherwise, we have a plain conditional or unconditional jump.  */
 	  else
 	    {
-	      if (! JUMP_LABEL (insn))
-		abort ();
+	      gcc_assert (JUMP_LABEL (insn));
 	      make_label_edge (edge_cache, bb, JUMP_LABEL (insn), 0);
 	    }
 	}
 
-      /* If this is a sibling call insn, then this is in effect a
-	 combined call and return, and so we need an edge to the
-	 exit block.  No need to worry about EH edges, since we
-	 wouldn't have created the sibling call in the first place.  */
-
+      /* If this is a sibling call insn, then this is in effect a combined call
+	 and return, and so we need an edge to the exit block.  No need to
+	 worry about EH edges, since we wouldn't have created the sibling call
+	 in the first place.  */
       if (code == CALL_INSN && SIBLING_CALL_P (insn))
 	cached_make_edge (edge_cache, bb, EXIT_BLOCK_PTR,
-		   EDGE_ABNORMAL | EDGE_ABNORMAL_CALL);
+			  EDGE_SIBCALL | EDGE_ABNORMAL);
 
       /* If this is a CALL_INSN, then mark it as reaching the active EH
 	 handler for this CALL_INSN.  If we're handling non-call
 	 exceptions then any insn can reach any of the active handlers.
-
 	 Also mark the CALL_INSN as reaching any nonlocal goto handler.  */
-
-      else if (code == CALL_INSN || flag_non_call_exceptions)
+      else if (code == CALL_INSN || cfun->can_throw_non_call_exceptions)
 	{
 	  /* Add any appropriate EH edges.  */
-	  make_eh_edge (edge_cache, bb, insn);
+	  rtl_make_eh_edge (edge_cache, bb, insn);
 
-	  if (code == CALL_INSN && nonlocal_goto_handler_labels)
+	  if (code == CALL_INSN)
 	    {
-	      /* ??? This could be made smarter: in some cases it's possible
-		 to tell that certain calls will not do a nonlocal goto.
-
-		 For example, if the nested functions that do the nonlocal
-		 gotos do not have their addresses taken, then only calls to
-		 those functions or to other nested functions that use them
-		 could possibly do nonlocal gotos.  */
-	      /* We do know that a REG_EH_REGION note with a value less
-		 than 0 is guaranteed not to perform a non-local goto.  */
-	      rtx note = find_reg_note (insn, REG_EH_REGION, NULL_RTX);
-	      if (!note || INTVAL (XEXP (note, 0)) >=  0)
-		for (x = nonlocal_goto_handler_labels; x; x = XEXP (x, 1))
-		  make_label_edge (edge_cache, bb, XEXP (x, 0),
-				   EDGE_ABNORMAL | EDGE_ABNORMAL_CALL);
+	      if (can_nonlocal_goto (insn))
+		{
+		  /* ??? This could be made smarter: in some cases it's
+		     possible to tell that certain calls will not do a
+		     nonlocal goto.  For example, if the nested functions
+		     that do the nonlocal gotos do not have their addresses
+		     taken, then only calls to those functions or to other
+		     nested functions that use them could possibly do
+		     nonlocal gotos.  */
+		  for (x = nonlocal_goto_handler_labels; x; x = XEXP (x, 1))
+		    make_label_edge (edge_cache, bb, XEXP (x, 0),
+				     EDGE_ABNORMAL | EDGE_ABNORMAL_CALL);
+		}
+
+	      if (flag_tm)
+		{
+		  rtx note;
+		  for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
+		    if (REG_NOTE_KIND (note) == REG_TM)
+		      make_label_edge (edge_cache, bb, XEXP (note, 0),
+				       EDGE_ABNORMAL | EDGE_ABNORMAL_CALL);
+		}
 	    }
 	}
 
       /* Find out if we can drop through to the next block.  */
-      insn = next_nonnote_insn (insn);
-      if (!insn || (i + 1 == n_basic_blocks && force_fallthru))
+      insn = NEXT_INSN (insn);
+      e = find_edge (bb, EXIT_BLOCK_PTR);
+      if (e && e->flags & EDGE_FALLTHRU)
+	insn = NULL;
+
+      while (insn
+	     && NOTE_P (insn)
+	     && NOTE_KIND (insn) != NOTE_INSN_BASIC_BLOCK)
+	insn = NEXT_INSN (insn);
+
+      if (!insn)
 	cached_make_edge (edge_cache, bb, EXIT_BLOCK_PTR, EDGE_FALLTHRU);
-      else if (i + 1 < n_basic_blocks)
+      else if (bb->next_bb != EXIT_BLOCK_PTR)
 	{
-	  rtx tmp = BLOCK_HEAD (i + 1);
-	  if (GET_CODE (tmp) == NOTE)
-	    tmp = next_nonnote_insn (tmp);
-	  if (force_fallthru || insn == tmp)
-	    cached_make_edge (edge_cache, bb, BASIC_BLOCK (i + 1), EDGE_FALLTHRU);
+	  if (insn == BB_HEAD (bb->next_bb))
+	    cached_make_edge (edge_cache, bb, bb->next_bb, EDGE_FALLTHRU);
 	}
     }
 
@@ -398,288 +389,76 @@ make_edges (label_value_list, min, max, update_p)
     sbitmap_vector_free (edge_cache);
 }
 
-/* Find all basic blocks of the function whose first insn is F.
+static void
+mark_tablejump_edge (rtx label)
+{
+  basic_block bb;
 
-   Collect and return a list of labels whose addresses are taken.  This
-   will be used in make_edges for use with computed gotos.  */
+  gcc_assert (LABEL_P (label));
+  /* See comment in make_label_edge.  */
+  if (INSN_UID (label) == 0)
+    return;
+  bb = BLOCK_FOR_INSN (label);
+  SET_STATE (bb, FULL_STATE (bb) | BLOCK_USED_BY_TABLEJUMP);
+}
 
 static void
-find_basic_blocks_1 (f)
-     rtx f;
+purge_dead_tablejump_edges (basic_block bb, rtx table)
 {
-  register rtx insn, next;
-  int i = 0;
-  rtx bb_note = NULL_RTX;
-  rtx lvl = NULL_RTX;
-  rtx trll = NULL_RTX;
-  rtx head = NULL_RTX;
-  rtx end = NULL_RTX;
-
-  /* We process the instructions in a slightly different way than we did
-     previously.  This is so that we see a NOTE_BASIC_BLOCK after we have
-     closed out the previous block, so that it gets attached at the proper
-     place.  Since this form should be equivalent to the previous,
-     count_basic_blocks continues to use the old form as a check.  */
-
-  for (insn = f; insn; insn = next)
+  rtx insn = BB_END (bb), tmp;
+  rtvec vec;
+  int j;
+  edge_iterator ei;
+  edge e;
+
+  if (GET_CODE (PATTERN (table)) == ADDR_VEC)
+    vec = XVEC (PATTERN (table), 0);
+  else
+    vec = XVEC (PATTERN (table), 1);
+
+  for (j = GET_NUM_ELEM (vec) - 1; j >= 0; --j)
+    mark_tablejump_edge (XEXP (RTVEC_ELT (vec, j), 0));
+
+  /* Some targets (eg, ARM) emit a conditional jump that also
+     contains the out-of-range target.  Scan for these and
+     add an edge if necessary.  */
+  if ((tmp = single_set (insn)) != NULL
+       && SET_DEST (tmp) == pc_rtx
+       && GET_CODE (SET_SRC (tmp)) == IF_THEN_ELSE
+       && GET_CODE (XEXP (SET_SRC (tmp), 2)) == LABEL_REF)
+    mark_tablejump_edge (XEXP (XEXP (SET_SRC (tmp), 2), 0));
+
+  for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
     {
-      enum rtx_code code = GET_CODE (insn);
-
-      next = NEXT_INSN (insn);
-
-      switch (code)
+      if (FULL_STATE (e->dest) & BLOCK_USED_BY_TABLEJUMP)
+	SET_STATE (e->dest, FULL_STATE (e->dest)
+			    & ~(size_t) BLOCK_USED_BY_TABLEJUMP);
+      else if (!(e->flags & (EDGE_ABNORMAL | EDGE_EH)))
 	{
-	case NOTE:
-	  {
-	    int kind = NOTE_LINE_NUMBER (insn);
-
-	    /* Look for basic block notes with which to keep the
-	       basic_block_info pointers stable.  Unthread the note now;
-	       we'll put it back at the right place in create_basic_block.
-	       Or not at all if we've already found a note in this block.  */
-	    if (kind == NOTE_INSN_BASIC_BLOCK)
-	      {
-		if (bb_note == NULL_RTX)
-		  bb_note = insn;
-		else
-		  next = flow_delete_insn (insn);
-	      }
-	    break;
-	  }
-
-	case CODE_LABEL:
-	  /* A basic block starts at a label.  If we've closed one off due
-	     to a barrier or some such, no need to do it again.  */
-	  if (head != NULL_RTX)
-	    {
-	      create_basic_block_structure (i++, head, end, bb_note);
-	      bb_note = NULL_RTX;
-	    }
-
-	  head = end = insn;
-	  break;
-
-	case JUMP_INSN:
-	  /* A basic block ends at a jump.  */
-	  if (head == NULL_RTX)
-	    head = insn;
-	  else
-	    {
-	      /* ??? Make a special check for table jumps.  The way this
-		 happens is truly and amazingly gross.  We are about to
-		 create a basic block that contains just a code label and
-		 an addr*vec jump insn.  Worse, an addr_diff_vec creates
-		 its own natural loop.
-
-		 Prevent this bit of brain damage, pasting things together
-		 correctly in make_edges.
-
-		 The correct solution involves emitting the table directly
-		 on the tablejump instruction as a note, or JUMP_LABEL.  */
-
-	      if (GET_CODE (PATTERN (insn)) == ADDR_VEC
-		  || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC)
-		{
-		  head = end = NULL;
-		  n_basic_blocks--;
-		  break;
-		}
-	    }
-	  end = insn;
-	  goto new_bb_inclusive;
-
-	case BARRIER:
-	  /* A basic block ends at a barrier.  It may be that an unconditional
-	     jump already closed the basic block -- no need to do it again.  */
-	  if (head == NULL_RTX)
-	    break;
-	  goto new_bb_exclusive;
-
-	case CALL_INSN:
-	  {
-	    /* Record whether this call created an edge.  */
-	    rtx note = find_reg_note (insn, REG_EH_REGION, NULL_RTX);
-	    int region = (note ? INTVAL (XEXP (note, 0)) : 0);
-
-	    if (GET_CODE (PATTERN (insn)) == CALL_PLACEHOLDER)
-	      {
-		/* Scan each of the alternatives for label refs.  */
-		lvl = find_label_refs (XEXP (PATTERN (insn), 0), lvl);
-		lvl = find_label_refs (XEXP (PATTERN (insn), 1), lvl);
-		lvl = find_label_refs (XEXP (PATTERN (insn), 2), lvl);
-		/* Record its tail recursion label, if any.  */
-		if (XEXP (PATTERN (insn), 3) != NULL_RTX)
-		  trll = alloc_EXPR_LIST (0, XEXP (PATTERN (insn), 3), trll);
-	      }
-
-	    /* A basic block ends at a call that can either throw or
-	       do a non-local goto.  */
-	    if ((nonlocal_goto_handler_labels && region >= 0)
-		|| can_throw_internal (insn))
-	      {
-	      new_bb_inclusive:
-		if (head == NULL_RTX)
-		  head = insn;
-		end = insn;
-
-	      new_bb_exclusive:
-		create_basic_block_structure (i++, head, end, bb_note);
-		head = end = NULL_RTX;
-		bb_note = NULL_RTX;
-		break;
-	      }
-	  }
-	  /* Fall through.  */
-
-	case INSN:
-	  /* Non-call exceptions generate new blocks just like calls.  */
-	  if (flag_non_call_exceptions && can_throw_internal (insn))
-	    goto new_bb_inclusive;
-
-	  if (head == NULL_RTX)
-	    head = insn;
-	  end = insn;
-	  break;
-
-	default:
-	  abort ();
-	}
-
-      if (GET_CODE (insn) == INSN || GET_CODE (insn) == CALL_INSN)
-	{
-	  rtx note;
-
-	  /* Make a list of all labels referred to other than by jumps.
-
-	     Make a special exception for labels followed by an ADDR*VEC,
-	     as this would be a part of the tablejump setup code.
-
-	     Make a special exception to registers loaded with label
-	     values just before jump insns that use them.  */
-
-	  for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
-	    if (REG_NOTE_KIND (note) == REG_LABEL)
-	      {
-		rtx lab = XEXP (note, 0), next;
-
-		if ((next = next_nonnote_insn (lab)) != NULL
-			 && GET_CODE (next) == JUMP_INSN
-			 && (GET_CODE (PATTERN (next)) == ADDR_VEC
-			     || GET_CODE (PATTERN (next)) == ADDR_DIFF_VEC))
-		  ;
-		else if (GET_CODE (lab) == NOTE)
-		  ;
-		else if (GET_CODE (NEXT_INSN (insn)) == JUMP_INSN
-			 && find_reg_note (NEXT_INSN (insn), REG_LABEL, lab))
-		  ;
-		else
-		  lvl = alloc_EXPR_LIST (0, XEXP (note, 0), lvl);
-	      }
+	  remove_edge (e);
+	  continue;
 	}
+      ei_next (&ei);
     }
-
-  if (head != NULL_RTX)
-    create_basic_block_structure (i++, head, end, bb_note);
-  else if (bb_note)
-    flow_delete_insn (bb_note);
-
-  if (i != n_basic_blocks)
-    abort ();
-
-  label_value_list = lvl;
-  tail_recursion_label_list = trll;
 }
 
+/* Scan basic block BB for possible BB boundaries inside the block
+   and create new basic blocks in the progress.  */
 
-/* Find basic blocks of the current function.
-   F is the first insn of the function and NREGS the number of register
-   numbers in use.  */
-
-void
-find_basic_blocks (f, nregs, file)
-     rtx f;
-     int nregs ATTRIBUTE_UNUSED;
-     FILE *file ATTRIBUTE_UNUSED;
-{
-  int max_uid;
-  timevar_push (TV_CFG);
-
-  basic_block_for_insn = 0;
-
-  /* Flush out existing data.  */
-  if (basic_block_info != NULL)
-    {
-      int i;
-
-      clear_edges ();
-
-      /* Clear bb->aux on all extant basic blocks.  We'll use this as a
-	 tag for reuse during create_basic_block, just in case some pass
-	 copies around basic block notes improperly.  */
-      for (i = 0; i < n_basic_blocks; ++i)
-	BASIC_BLOCK (i)->aux = NULL;
-
-      VARRAY_FREE (basic_block_info);
-    }
-
-  n_basic_blocks = count_basic_blocks (f);
-
-  /* Size the basic block table.  The actual structures will be allocated
-     by find_basic_blocks_1, since we want to keep the structure pointers
-     stable across calls to find_basic_blocks.  */
-  /* ??? This whole issue would be much simpler if we called find_basic_blocks
-     exactly once, and thereafter we don't have a single long chain of
-     instructions at all until close to the end of compilation when we
-     actually lay them out.  */
-
-  VARRAY_BB_INIT (basic_block_info, n_basic_blocks, "basic_block_info");
-
-  find_basic_blocks_1 (f);
-
-  /* Record the block to which an insn belongs.  */
-  /* ??? This should be done another way, by which (perhaps) a label is
-     tagged directly with the basic block that it starts.  It is used for
-     more than that currently, but IMO that is the only valid use.  */
-
-  max_uid = get_max_uid ();
-#ifdef AUTO_INC_DEC
-  /* Leave space for insns life_analysis makes in some cases for auto-inc.
-     These cases are rare, so we don't need too much space.  */
-  max_uid += max_uid / 10;
-#endif
-
-  compute_bb_for_insn (max_uid);
-
-  /* Discover the edges of our cfg.  */
-  make_edges (label_value_list, 0, n_basic_blocks - 1, 0);
-
-  /* Do very simple cleanup now, for the benefit of code that runs between
-     here and cleanup_cfg, e.g. thread_prologue_and_epilogue_insns.  */
-  tidy_fallthru_edges ();
-
-#ifdef ENABLE_CHECKING
-  verify_flow_info ();
-#endif
-  timevar_pop (TV_CFG);
-}
-
-/* Assume that someone emitted code with control flow instructions to the
-   basic block.  Update the data structure.  */
-void
-find_sub_basic_blocks (bb)
-     basic_block bb;
+static void
+find_bb_boundaries (basic_block bb)
 {
-  rtx insn = bb->head;
-  rtx end = bb->end;
+  basic_block orig_bb = bb;
+  rtx insn = BB_HEAD (bb);
+  rtx end = BB_END (bb), x;
+  rtx table;
   rtx flow_transfer_insn = NULL_RTX;
   edge fallthru = NULL;
-  basic_block first_bb = bb;
-  int i;
 
-  if (insn == bb->end)
+  if (insn == BB_END (bb))
     return;
 
-  if (GET_CODE (insn) == CODE_LABEL)
+  if (LABEL_P (insn))
     insn = NEXT_INSN (insn);
 
   /* Scan insn chain and try to find new basic block boundaries.  */
@@ -687,68 +466,41 @@ find_sub_basic_blocks (bb)
     {
       enum rtx_code code = GET_CODE (insn);
 
-      switch (code)
+      /* In case we've previously seen an insn that effects a control
+	 flow transfer, split the block.  */
+      if ((flow_transfer_insn || code == CODE_LABEL)
+	  && inside_basic_block_p (insn))
 	{
-	case BARRIER:
-	  if (!flow_transfer_insn)
-	    abort ();
-	  break;
-
-	/* On code label, split current basic block.  */
-	case CODE_LABEL:
 	  fallthru = split_block (bb, PREV_INSN (insn));
 	  if (flow_transfer_insn)
-	    bb->end = flow_transfer_insn;
+	    {
+	      BB_END (bb) = flow_transfer_insn;
+
+	      /* Clean up the bb field for the insns between the blocks.  */
+	      for (x = NEXT_INSN (flow_transfer_insn);
+		   x != BB_HEAD (fallthru->dest);
+		   x = NEXT_INSN (x))
+		if (!BARRIER_P (x))
+		  set_block_for_insn (x, NULL);
+	    }
+
 	  bb = fallthru->dest;
 	  remove_edge (fallthru);
 	  flow_transfer_insn = NULL_RTX;
-	  if (LABEL_ALTERNATE_NAME (insn))
+	  if (code == CODE_LABEL && LABEL_ALT_ENTRY_P (insn))
 	    make_edge (ENTRY_BLOCK_PTR, bb, 0);
-	  break;
-
-	case INSN:
-	case JUMP_INSN:
-	case CALL_INSN:
-	  /* In case we've previously split an insn that effects a control
-	     flow transfer, move the block header to proper place.  */
-	  if (flow_transfer_insn)
-	    {
-	      fallthru = split_block (bb, PREV_INSN (insn));
-	      bb->end = flow_transfer_insn;
-	      bb = fallthru->dest;
-	      remove_edge (fallthru);
-	      flow_transfer_insn = NULL_RTX;
-	    }
-
-	  /* We need some special care for those expressions.  */
-	  if (code == JUMP_INSN)
-	    {
-	      if (GET_CODE (PATTERN (insn)) == ADDR_VEC
-		  || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC)
-		abort();
-	      flow_transfer_insn = insn;
-	    }
-	  else if (code == CALL_INSN)
-	    {
-	      rtx note;
-	      if (nonlocal_goto_handler_labels
-		  && (!(note = find_reg_note (insn, REG_EH_REGION, NULL_RTX))
-		      || INTVAL (XEXP (note, 0)) >= 0))
-		flow_transfer_insn = insn;
-	      else if (can_throw_internal (insn))
-		flow_transfer_insn = insn;
-	      else if (SIBLING_CALL_P (insn))
-		flow_transfer_insn = insn;
-	      else if (find_reg_note (insn, REG_NORETURN, 0))
-		flow_transfer_insn = insn;
-	    }
-	  else if (flag_non_call_exceptions && can_throw_internal (insn))
-	    flow_transfer_insn = insn;
-	  break;
-
-	default:
-	  break;
 	}
+      else if (code == BARRIER)
+	{
+	  /* __builtin_unreachable () may cause a barrier to be emitted in
+	     the middle of a BB.  We need to split it in the same manner as
+	     if the barrier were preceded by a control_flow_insn_p insn.  */
+	  if (!flow_transfer_insn)
+	    flow_transfer_insn = prev_nonnote_insn_bb (insn);
+	}
+
+      if (control_flow_insn_p (insn))
+	flow_transfer_insn = insn;
       if (insn == end)
 	break;
       insn = NEXT_INSN (insn);
@@ -758,43 +510,47 @@ find_sub_basic_blocks (bb)
      return and barrier, or possibly other sequence not behaving like
      ordinary jump, we need to take care and move basic block boundary.  */
   if (flow_transfer_insn)
-    bb->end = flow_transfer_insn;
+    {
+      BB_END (bb) = flow_transfer_insn;
+
+      /* Clean up the bb field for the insns that do not belong to BB.  */
+      x = flow_transfer_insn;
+      while (x != end)
+	{
+	  x = NEXT_INSN (x);
+	  if (!BARRIER_P (x))
+	    set_block_for_insn (x, NULL);
+	}
+    }
 
   /* We've possibly replaced the conditional jump by conditional jump
      followed by cleanup at fallthru edge, so the outgoing edges may
      be dead.  */
   purge_dead_edges (bb);
 
-  /* Now re-scan and wire in all edges.  This expect simple (conditional)
-     jumps at the end of each new basic blocks.  */
-  make_edges (NULL, first_bb->index, bb->index, 1);
+  /* purge_dead_edges doesn't handle tablejump's, but if we have split the
+     basic block, we might need to kill some edges.  */
+  if (bb != orig_bb && tablejump_p (BB_END (bb), NULL, &table))
+    purge_dead_tablejump_edges (bb, table);
+}
 
-  /* Update branch probabilities.  Expect only (un)conditional jumps
-     to be created with only the forward edges.  */
-  for (i = first_bb->index; i <= bb->index; i++)
+/*  Assume that frequency of basic block B is known.  Compute frequencies
+    and probabilities of outgoing edges.  */
+
+static void
+compute_outgoing_frequencies (basic_block b)
+{
+  edge e, f;
+  edge_iterator ei;
+
+  if (EDGE_COUNT (b->succs) == 2)
     {
-      edge e,f;
-      basic_block b = BASIC_BLOCK (i);
-      if (b != first_bb)
-	{
-	  b->count = 0;
-	  b->frequency = 0;
-	  for (e = b->pred; e; e=e->pred_next)
-	    {
-	      b->count += e->count;
-	      b->frequency += EDGE_FREQUENCY (e);
-	    }
-	}
-      if (b->succ && b->succ->succ_next && !b->succ->succ_next->succ_next)
+      rtx note = find_reg_note (BB_END (b), REG_BR_PROB, NULL);
+      int probability;
+
+      if (note)
 	{
-	  rtx note = find_reg_note (b->end, REG_BR_PROB, NULL);
-	  int probability;
-
-	  if (!note)
-	    continue;
-	  probability = INTVAL (XEXP (find_reg_note (b->end,
-						     REG_BR_PROB,
-						     NULL), 0));
+	  probability = INTVAL (XEXP (note, 0));
 	  e = BRANCH_EDGE (b);
 	  e->probability = probability;
 	  e->count = ((b->count * probability + REG_BR_PROB_BASE / 2)
@@ -802,12 +558,78 @@ find_sub_basic_blocks (bb)
 	  f = FALLTHRU_EDGE (b);
 	  f->probability = REG_BR_PROB_BASE - probability;
 	  f->count = b->count - e->count;
-	}
-      if (b->succ && !b->succ->succ_next)
-	{
-	  e = b->succ;
-	  e->probability = REG_BR_PROB_BASE;
-	  e->count = b->count;
+	  return;
 	}
     }
+
+  if (single_succ_p (b))
+    {
+      e = single_succ_edge (b);
+      e->probability = REG_BR_PROB_BASE;
+      e->count = b->count;
+      return;
+    }
+  guess_outgoing_edge_probabilities (b);
+  if (b->count)
+    FOR_EACH_EDGE (e, ei, b->succs)
+      e->count = ((b->count * e->probability + REG_BR_PROB_BASE / 2)
+		  / REG_BR_PROB_BASE);
+}
+
+/* Assume that some pass has inserted labels or control flow
+   instructions within a basic block.  Split basic blocks as needed
+   and create edges.  */
+
+void
+find_many_sub_basic_blocks (sbitmap blocks)
+{
+  basic_block bb, min, max;
+
+  FOR_EACH_BB (bb)
+    SET_STATE (bb,
+	       TEST_BIT (blocks, bb->index) ? BLOCK_TO_SPLIT : BLOCK_ORIGINAL);
+
+  FOR_EACH_BB (bb)
+    if (STATE (bb) == BLOCK_TO_SPLIT)
+      find_bb_boundaries (bb);
+
+  FOR_EACH_BB (bb)
+    if (STATE (bb) != BLOCK_ORIGINAL)
+      break;
+
+  min = max = bb;
+  for (; bb != EXIT_BLOCK_PTR; bb = bb->next_bb)
+    if (STATE (bb) != BLOCK_ORIGINAL)
+      max = bb;
+
+  /* Now re-scan and wire in all edges.  This expect simple (conditional)
+     jumps at the end of each new basic blocks.  */
+  make_edges (min, max, 1);
+
+  /* Update branch probabilities.  Expect only (un)conditional jumps
+     to be created with only the forward edges.  */
+  if (profile_status != PROFILE_ABSENT)
+    FOR_BB_BETWEEN (bb, min, max->next_bb, next_bb)
+      {
+	edge e;
+	edge_iterator ei;
+
+	if (STATE (bb) == BLOCK_ORIGINAL)
+	  continue;
+	if (STATE (bb) == BLOCK_NEW)
+	  {
+	    bb->count = 0;
+	    bb->frequency = 0;
+	    FOR_EACH_EDGE (e, ei, bb->preds)
+	      {
+		bb->count += e->count;
+		bb->frequency += EDGE_FREQUENCY (e);
+	      }
+	  }
+
+	compute_outgoing_frequencies (bb);
+      }
+
+  FOR_EACH_BB (bb)
+    SET_STATE (bb, 0);
 }